_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005).pdf), страница 6

Разделяющиефункции ищутся в виде полиномов степени не выше k , где k задается заранее иливычисляется одновременно с коэффициентами. Степень k полинома (1.8) определяетсямаксимальной суммой степеней параметров xi в отдельных слагаемых (1.8)nni 1i , j 1f ( x)  a0   ai xi   aij xi x j nai , j ,k 1x x j xk  ...(1.8)ijk iz1  1, z2  x1 , z3  x2 ,..., zn1  xn , zn2  x1 , zn3  x1 x2 ,..., zt  xi x j xk ,...2Обозначивзадачасводится к построению линейной разделяющей функции f (z )  a t z в спрямляющемпространстве размерности N относительно переменных ( z1 , z2 ,..., z N ) .1.2.3. Метод потенциальных функций.Метод основан на аналогии с задачами электростатики. Рассмотрим случай двухклассов.

Предполагается, что каждый элемент обучающей выборки Si первого классаимеет положительный «заряд» +qi а элемент Sj второго класса - отрицательный заряд –qj. Объекты первого класса создают «потенциал» + qi K ( S , Si ) в каждой точке S пространствапризнаковых описаний, а объекты второго класса – потенциал - qi K ( S , Si ) . Здесь K ( S , Si )является величиной потенциала, создаваемого в точке S единичным зарядом. Тогдазначение потенциальной функции в точке S определяется какg (S )  q K (S , S )   q K (S , S ) .SiK1iiSiK 2iiПри классификации некоторого объекта S вычисляется значение потенциальной функцииg (S ) .

Классификация проводится согласно решающему правилу26 1, g ( S )  0, ( S )  , g ( S )  0, 0, g ( S )  0.AВ качестве основных требований к виду функций K ( S , Si ) предъявляются следующие два:1. K ( Si , Si )  max K ( Si , S ) ;S2.

K ( S , Si )  K ( S , S j ) приS j  S  Si  S(т.е. K ( S , Si ) монотонно убывает приSi  S   ).Распространенными примерами выбора K ( S , Si ) являются следующие:1. K ( S , Si ) 2 2  S  Si2. K ( S , Si )  exp(122, где σ - числовой параметр;S  Si ) ;22Таким образом, для классификации достаточно выбрать конкретный вид функции и задатьнеизвестные значения параметров  , q1 , q2 ,..., qm .Вычисление значений параметров q1 , q2 ,..., qm при фиксированном σ (а следовательно ифункции g (S ) ) осуществляется в процессе обучения согласно правилу коррекции (1.9) /2/.Пусть на некотором шаге имеется функция g (S ) .

Для классификации предъявляетсянекоторый объект Si обучающей выборки. Если результат классификации правильный,предъявляется для классификации следующий объект обучающей выборки. Есликлассификация является неправильной, осуществляется коррекция функцииg (S )согласно правилу (1.9) . g ( S )  K ( S , Si ), g ( Si )  0,g * (S )   g ( S )  K ( S , Si ), g ( Si )  0,Si  K1 ,Si  K 2 .(1.9)Объекты обучающей выборки предъявляются, например, циклически или в случайномпорядке.

Процесс обучения продолжается до достижения безошибочного распознаваниявсех объектов обучающей выборки полученной функцией g (S ) или «стабилизации» достижения ситуации, когда среднее число ошибок перестает уменьшаться за заданноечисло итераций.27K1Sig(x)>0g(x)=0g(x)<0Рис.4. Примеры возможной коррекции функции g (S ) при условии g ( Si )  0 , S i  K 2 .На рис.4 проиллюстрирована коррекция потенциальной функции g (S ) (множество точекg (S ) =0 изображено жирной линией) при предъявлении некоторого объекта из второгокласса, неправильно классифицируемого данной функцией. Функция g * ( S ) будетотличаться от g (S ) практически лишь в окрестности Si (участки заметного отличияотмечены пунктирами). При повторном предъявлении Si потенциальная функция можетправильно классифицировать объект (жирный пунктир) или опять неправильно.

Вовтором случае (тонкий пунктир), тем не менее, коррекция g (S ) будет сделана «в нужнуюсторону» , g * ( Si )  g ( Si ) /2, 19/.1.2.4. Нейросетевые модели распознавания.Данные алгоритмы являются попыткой моделирования способности человеческогомышления, в частности, способности обучаться и решать задачи распознавания попрецедентам. Они основаны на достижениях биологии и медицины - простейших моделяхчеловеческого мозга, созданных в середине прошлого века. Биологический мозграссматривается как множество элементарных элементов - нейронов, соединенных друг сдругоммногочисленнымисвязями.Нейроныбываюттрехтипов:рецепторы(принимающие сигналы из внешней среды и передающие другим нейронам), внутренниенейроны (принимающие сигналы от других нейронов, преобразующие их и передающиедругим нейронам) и реагирующие нейроны (принимающие сигналы от нейронов ивырабатывающие сигналы во внешнюю среду).28Рассмотрим простейшую и наиболее распространенную модель человеческогомозга, ориентированную на решение задач распознавания – искусственную многослойнуюнейронную сеть.Элементарной ячейкой нейронной сети является модель искусственного нейрона (рис.

5).Входw1x1x2w2Выход y=f(Z)w3Zx3…xNwNРис. 5. Модель искусственного нейронаКаждый внутренний или реагирующий нейрон имеет множество входных связей(синапсов), по которым поступают сигналы от других внутренних нейронов илирецепторов, и одну выходящую связь (аксон).

Каждая связь имеет некоторый «вес» wi .При поступлении на вход нейрона совокупности сигналов x1 , x2 ,..., xN они «усиливаются»с соответствующими весами w1 , w2 ,..., wN . Нейрон переходит в состояние, числовая оценкаNкоторого вычисляется как Z   wi xi . Величина выходного сигнала вычисляется какi 1f (Z ) , где f - активационная функция. Примеры активационных функций приведены нарис. 6-9.10y1xРис. 6.

Функция единичного скачка0yxРис. 7. Единичный скачок с линейнымпорогом2911yy0x0-1Рис.8.Гиперболическийf(x)=th(x)тангенсРис.9.xФункциясигмоидаf(x)=1/(1+exp(-ax))Нейрон считается «возбужденным», если выходной сигнал отличен от нуля, а величинаNy  f ( wi xi ) характеризует степень возбуждения. Вид функций и область их измененияi 1отражают априорные представления о функционировании биологических нейронов:величина возбуждения зависит монотонно от состояния, ограничена снизу и сверху, иN«сильно» меняется в небольшом интервале значений Z   wi xi .i 1Наиболеепростыми,распространеннымииисследованнымиявляютсямногослойные нейронные сети прямого действия.

Общий вид подобной сети изображенна рис. 10. Сеть состоит из N слоев, каждые слой состоит из ni нейронов, каждый нейронj-го уровня связан с каждым нейроном j+1 – го уровня. Фиктивный нулевой слой состоитиз n входных нейронов, на каждый из которых подается значение некоторого признакаxi . Результатами классификации являются выходные значения нейронов N -го слоя.Распознаваемый объект S поступает на 0-й слой. Далее поступивший сигнал(признаковое описание) последовательно преобразуется по слоям согласно заданнымфиксированным весам синаптических связей и выбранной активационной функции. Еслиy Nj ( S ), j  1,2,..., l , есть значение j-го нейрона выходного слоя, то информационный векторрезультатов классификации S вычисляется согласно (1.10) 1,A j ( S )   , 0,y Nj ( S )  0,y Nj ( S )  0,y Nj ( S )  0.(1.10)30x10-й слойi+1-й слойi-й слойN-й слойy1Nx2…x3y2N………wijk1ylNxnwni i n1i1Рис.10.

Структурная схема нейронной классифицирующей сети прямого действияЗначения неизвестных весовых коэффициентов находятся в результате процессаобучения сети. Начальные значения весовых коэффициентов задаются случайно. Объектыобучения последовательно поступают на вход сети. Если предъявленный объектклассифицируется правильно, коэффициенты остаются прежними и на вход сетипоступает следующий объект.

Если при классификации объекта происходит ошибка,весовые коэффициенты изменяются определенным образом. Для однослойной сети онименяются согласно простой итерационной формуле подобно используемой в методепотенциальныхфункций.Длямногослойнойсетииспользуютсяспециальныерекуррентные формулы пересчета весовых коэффициентов от последнего уровня допервого (метод «обратного распространения ошибки»). Обучение заканчивается, еслиизменение коэффициентов не приводит к дальнейшему уменьшению суммарного числаошибок на обучающей выборке /57/.1.2.5. Решающие деревья.Методы распознавания, основанные на построении решающих деревьев, относятсяк типу логических методов.

В данном классе алгоритмов распознавание объектаосуществляется как прохождение по бинарному дереву из корня в некоторую висячуювершину. В каждой вершине вычисляется определенная логическая функция. Взависимости от полученного значения функции происходит переход далее по дереву влевую или правую вершину следующего уровня. Каждая висячая вершина связана с31одним из классов, в который и относится распознаваемый объект, если путь по деревузаканчивается в данной вершине.Бинарным корневым деревом (БД) называется дерево, имеющее следующие свойства:а) каждая вершина (кроме корневой ) имеет одну входящую дугу;б) каждая вершина имеет имеет либо две, либо ни одной выходящей дуги.Вершины, имеющие две выходящие дуги, называются внутренними, а остальные –терминальными или листьями.Пусть задано N предикатов   y1  P1 ( S ), y2  P2 ( S ),..., y N  PN ( S ) , определенных намножестве допустимых признаковых описаний {S}, именуемые признаковымипредикатами.