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

Выбирая первые варианты реализации этапов (2-5) будетполучена следующая общая формула для вычисления оценок объекта S за классы K j ,j=1,2,…,l.mj1j (S )   B (S , S ) .(m j  m j 1 )  m j 11 A(1.15)При выборе системы опорных множеств согласно вариантам a) или b) прямоевычисление оценок (1.15) представляется весьма трудоемким (при вычислении оценок(1.15) согласно a) требуетсяmC nkвычислений значений функции близости). Вдействительности нет необходимости выполнения всех данных вычислений, посколькупри многих вариантах реализации этапов 2-5 и различных системах опорных множествсуществуют эффективные комбинаторные формулы вычисления оценок.Например, при использовании в качестве системы опорных множеств  A = { :   k} ивариантов a) выполнения этапов (2-5), справедлива формула j S  где d ( S , S i ) 1Cdk ( S ,Si ) ,(m j  m j 1 ) SiK j : x (S )  x (S )   ,  1,2,..., ni(1.16).При использовании вариантов a) выполнения этапов (2-5) и b) для первого этапа,справедлива формула j S  1(2 d ( S ,Si )  1) .(m j  m j 1 ) SiK j(1.17)Другие, более сложные и общие способы определения этапов (1-5), а такжесоответствующие им эффективные формулы вычисления оценок, приведены в /25, 26/.1.3.4.

Оптимизация многопараметрических моделей распознавания.43Процесс распознавания во многих моделях вычисления оценок предполагаетзнание числовых параметров модели (веса признаков, веса эталонов, пороговыепараметры, и т.п.). Их значения могут быть выбраны непосредственно пользователемисходя из содержательных или эвристических соображений, поскольку многие параметрыимеют естественную интерпретацию. Основным же подходом к их вычислению являетсяпроцесс обучения или оптимизации модели. Желаемым результатом в обоих случаяхявляется нахождение таких значений параметров, при которых будет обеспечена высокаяточность распознавания.Поиск значений параметров, как процесс «обучения с учителем», используется внейросетевых подходах, методе потенциальных функций, построении линейныхразделяющих гиперплоскостей.

Применяется следующая общая схема обучения. Задаютсяначальные значения параметров (например, случайные из некоторого интервала).Алгоритму предъявляется один из обучающих объектов, класс которого известен. Еслиобъект распознается правильно, предъявляется для распознавания следующий объект.Если объект классифицируется неправильно, происходит коррекция параметров «внужном направлении». Процесс продолжается до достижения стабилизации работыалгоритма, когда последующее обучение не уменьшает общее число ошибок наобучающей выборке.Более общая постановка процесса «настройки» алгоритмов связана с решениемстандартной оптимизационной задачи оптимизации модели.Пустьдано{ A( y}, y  D}параметрическоемножествораспознающихи на нем определен числовой функционалТребуется найти такой алгоритм ( A)алгоритмовкачества алгоритма.A*  { A} , который доставляет экстремум функционалу: ( A*)  extr  ( A) .A{ A}Так, например, модель вычислении оценок со способами выполнения этапов (а,а,с,а,а,с)является следующим параметрическим семейством алгоритмов:{ Ak (k ,  , p,  ,  , c1 , c2 ),1  k  0, k  целое,   0,1  p  0,1    0, c1  c2 }Стандартная постановка проблема оптимизации параметрической модели распознаваниясостоит в следующем.Пусть задана таблица контрольных объектовT ' nql , аналогичная таблицеобучения, т.е.

состоящая из разбитых на l классов m числовых строк – признаковыхописаний объектов44S 'i  ( x1 ( S 'i ), x2 ( S 'i ),..., xn ( S 'i )) , ait'  xt ( Si' )(1.18)Для определенности считаем, чтоS 'i  K j , i  q j 1  1, q j 1  2,..., q j , q0  0, ql  q.S 'i  K j ,1,Пусть  ij  0, S 'i  K j .Обозначим ijA   j ( S 'i ).Определение 2. Стандартным функционалом качества распознавания называетсяфункционал  ( A) 1 q l ij   ijA .ql i 1 j 1В статистической теории распознавания данный критерий называют эмпирическимриском. Очевидными эквивалентными ему вариантами являются «доля правильныхответов» или «число правильных ответов».Постановка задачи оптимизации моделей распознавания может быть записана втерминах систем неравенств.

Для простоты ограничимся случаем двух классов и моделью(а,а,с,а,а,а) вычисления оценок.УсловиемправильногораспознаваниянекоторогоконтрольногообъектаS 'i  K jявляется выполнение неравенства 1 ( Si' )  2 ( Si' ) , если объект из первогокласса, и2 ( Si' )  1 ( Si' ) , если объект из второго класса. Тогда число правильнораспознанных объектов при некотором варианте выбора параметров модели будет равночислу выполненных неравенств системы.1 ( Si' )  2 ( Si' ) , i  1,2,..., m1 ,2 ( Si' )  1 ( Si' ) , i  m1  1, m1  2,..., m .Учитывая,p1 , p 2 ,... p nчтооценки 1 ,  2 ,... m ,иявляютсябилинейнымиформамиотпараметровзадача оптимизации модели может быть сформулированаследующим образом: «Найти максимальную совместную подсистему системы (1.19) инекоторое ее решение, удовлетворяющие соответствующим ограничениям на параметрымодели».mn b (k ,  ) p j 1 i 1tijij 0 , t  1,2,..., q .(1.19)Данная задача является сложной оптимизационной задачей даже для частногослучаялинейнойсистемы,когдав(1.19)фиксированыk , 1 ,  2 ,... n , p1 , p2 ,...

pn , или параметры k , 1 ,  2 ,... n ,  1 ,  2 ,... m .илипараметры45Фундаментальные теоретические результаты, связанные с исследованием задачи поискамаксимальных совместных подсистем, получены в Уральском Университете (Мазуров,Хачай) /43/. Комбинаторные алгоритмы для задач малой размерности созданы в ВЦ РАНКатериночкиной Н.Н. /34/ В системе «РАСПОЗНАВАНИЕ» используется эвристическийалгоритм,основанныйнарелаксационномспуске.Оптимизациястандартногофункционала качества как последовательность вспомогательных оптимизационных задачв пространстве параметров  при фиксированных p, и пространстве p,  , прификсированных  , рассматривалась в /82/.1.3.5. Статистическое взвешенное голосование.Процедура статистически взвешенного голосования по системам подобластейпризнакового пространства лежит в основе метода распознавания образов «Статистическивзвешенные синдромы» (СВС).

Процедура статистически взвешенного голосованияиспользуется при прогнозировании произвольных стохастических функций, зависящих отнабора непрерывных прогностических переменных и принимающих значения изнекоторого подмножества точек действительной оси.~Пусть Y - прогнозируемая функция, Q - система подобластей многомерного~признакового пространства, S y -обучающая выборка, представляющая собой множествообъектов вида ( y j , x j ) , где y j - значение функции Y , а x j - соответствующий векторзначенийпрогностическихпеременных.Процедурастатистически взвешенного~голосования предназначена для построения по системе подобластей Q и обучающей~~выборке S y детерминировано зависящей от прогностических переменных функции Y ,~которая достаточно сильно коррелирована с Y . Назовем данную функцию Y взвешеннойоценкой функцииY .

Пусть-некоторая точка в многомерном признаковом~~пространстве, принадлежащая к подобластям q1 , , q p из Q . Значение функции Y вxточке x вычисляется по формуле (1.20)p~Y ( x) w yi 1piiwi 1,(1.20)iгде yi - среднее значение функции Y на объектах обучающей выборки из подобласти q i ,wi -так называемый вес i -ой подобласти. Метод вычисления весов подобластей,основанный на максимизации специального функционала правдоподобия, был предложен46в работе /56/.

В результате была получена следующая формула для расчета весов:wi ~1 mi, где mi -число объектов из S y с описаниями x , попавшими в подобластьd i mi i  1q i ; d i - дисперсия функции Y в подобласти q i ;  i - коэффициент детерминированностиd iфункции Y на подобласти q i , который определяется как отношение  i , гдеdid i =  { [x( )]  M(Y | Qi )}2 P(d ) - дисперсия на подобласти q i функции  (x) , котораяQiопределяется равенством  (x)  M (Y | x) .

Коэффициент детерминированности возрастаетс уменьшением доли случайной составляющей в зависимости функции Y от x внутриподобласти q i .В методе СВС в качестве оценок за классыK1 ,..., K lдля некоторогораспознаваемого объекта S выступают рассчитанные с помощью процедуры взвешенногоголосования взвешенные оценки индикаторных функций классов 1 ( S ),..., l ( S ) .

При этомв качестве подобластей голосования используются так называемые синдромы.Под синдромом мы в данном случае понимаем подобласть в пространствепрогностических признаков, внутри которой содержание объектов одного из классовзначительно отличается от среднего содержания по выборке.1.4. Алгебраический подход для решения задач распознавания и прогноза1.4.1. Этапы развития теории распознавания и классификации по прецедентам.Анализ истории развития теории распознавания и исследование существующих подходовпозволяют выделить три основных этапа в ее развитии.1. Первый этап характеризуется появлением разнообразных эвристических методов иалгоритмов как универсальных, предназначенных для решения широкого спектра задач,так и специальных, ориентированных на обработку информации заданного типа. С ихпомощью решались прикладные задачи в самых различных областях человеческойдеятельности.Примерамиуспешныхчастныхалгоритмовявляютсяалгоритмы«ближайший сосед», «тестовый алгоритм», «алгоритм Кора», дискриминант Фишера, имногие другие.2.