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

. (1.15)

При выборе системы опорных множеств согласно вариантам a) или b) прямое вычисление оценок (1.15) представляется весьма трудоемким (при вычислении оценок (1.15) согласно a) требуется вычислений значений функции близости). В действительности нет необходимости выполнения всех данных вычислений, поскольку при многих вариантах реализации этапов 2-5 и различных системах опорных множеств существуют эффективные комбинаторные формулы вычисления оценок.

Например, при использовании в качестве системы опорных множеств = и вариантов a) выполнения этапов (2-5), справедлива формула

, (1.16)

где .

При использовании вариантов a) выполнения этапов (2-5) и b) для первого этапа, справедлива формула

. (1.17)

Другие, более сложные и общие способы определения этапов (1-5), а также соответствующие им эффективные формулы вычисления оценок, приведены в /25, 26/.

1.3.4. Оптимизация многопараметрических моделей распознавания.

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

Поиск значений параметров, как процесс «обучения с учителем», используется в нейросетевых подходах, методе потенциальных функций, построении линейных разделяющих гиперплоскостей. Применяется следующая общая схема обучения. Задаются начальные значения параметров (например, случайные из некоторого интервала). Алгоритму предъявляется один из обучающих объектов, класс которого известен. Если объект распознается правильно, предъявляется для распознавания следующий объект. Если объект классифицируется неправильно, происходит коррекция параметров «в нужном направлении». Процесс продолжается до достижения стабилизации работы алгоритма, когда последующее обучение не уменьшает общее число ошибок на обучающей выборке.

Более общая постановка процесса «настройки» алгоритмов связана с решением стандартной оптимизационной задачи оптимизации модели.

Пусть дано параметрическое множество распознающих алгоритмов и на нем определен числовой функционал качества алгоритма. Требуется найти такой алгоритм , который доставляет экстремум функционалу: .

Так, например, модель вычислении оценок со способами выполнения этапов (а,а,с,а,а,с) является следующим параметрическим семейством алгоритмов:

Стандартная постановка проблема оптимизации параметрической модели распознавания состоит в следующем.

Пусть задана таблица контрольных объектов , аналогичная таблице обучения, т.е. состоящая из разбитых на l классов m числовых строк – признаковых описаний объектов

, (1.18)

Для определенности считаем, что

Пусть Обозначим

Определение 2. Стандартным функционалом качества распознавания называется функционал .

В статистической теории распознавания данный критерий называют эмпирическим риском. Очевидными эквивалентными ему вариантами являются «доля правильных ответов» или «число правильных ответов».

Постановка задачи оптимизации моделей распознавания может быть записана в терминах систем неравенств. Для простоты ограничимся случаем двух классов и моделью (а,а,с,а,а,а) вычисления оценок.

Условием правильного распознавания некоторого контрольного объекта является выполнение неравенства , если объект из первого класса, и , если объект из второго класса. Тогда число правильно распознанных объектов при некотором варианте выбора параметров модели будет равно числу выполненных неравенств системы.

,

, .

Учитывая, что оценки являются билинейными формами от параметров и , задача оптимизации модели может быть сформулирована следующим образом: «Найти максимальную совместную подсистему системы (1.19) и некоторое ее решение, удовлетворяющие соответствующим ограничениям на параметры модели».

, . (1.19)

Данная задача является сложной оптимизационной задачей даже для частного случая линейной системы, когда в (1.19) фиксированы или параметры , или параметры .

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

1.3.5. Статистическое взвешенное голосование.

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

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

, (1.20)

где - среднее значение функции на объектах обучающей выборки из подобласти , -так называемый вес -ой подобласти. Метод вычисления весов подобластей, основанный на максимизации специального функционала правдоподобия, был предложен в работе /56/. В результате была получена следующая формула для расчета весов: , где -число объектов из с описаниями , попавшими в подобласть ; - дисперсия функции в подобласти ; - коэффициент детерминированности функции на подобласти , который определяется как отношение , где = - дисперсия на подобласти функции , которая определяется равенством . Коэффициент детерминированности возрастает с уменьшением доли случайной составляющей в зависимости функции от внутри подобласти .

В методе СВС в качестве оценок за классы для некоторого распознаваемого объекта выступают рассчитанные с помощью процедуры взвешенного голосования взвешенные оценки индикаторных функций классов . При этом в качестве подобластей голосования используются так называемые синдромы.

Под синдромом мы в данном случае понимаем подобласть в пространстве прогностических признаков, внутри которой содержание объектов одного из классов значительно отличается от среднего содержания по выборке.

1.4. Алгебраический подход для решения задач распознавания и прогноза

1.4.1. Этапы развития теории распознавания и классификации по прецедентам.

Анализ истории развития теории распознавания и исследование существующих подходов позволяют выделить три основных этапа в ее развитии.

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

2. Второй этап связывают с разработкой на базе отдельных эвристических методов распознавания параметрических моделей и решением задач оптимизации моделей - поиска наилучших алгоритмов в пределах фиксированных моделей /25/. Данный этап связан с естественным желанием исследователя в максимально возможном обобщении метода распознавания, реализацией идеи параметрической подстройки метода под новые данные. К тому же обилие алгоритмов распознавания создало проблему их сравнения и автоматического выбора наилучшего из заданного множества. Приведенные в разделах 1.2, 1.3 основные подходы и представляют современные и достаточно хорошо изученные модели.