§ 2.2. Обучающиеся системы распознавания

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

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

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

Если признаки статистически независимы и функции условных плотностей распределения могут быть представлены в виде произведений:

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

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

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

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

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

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

Обучающая выборка может быть использована для определения в первом приближении условных плотностей распределения значений признака по классам (рис. 2.1).

Рис. 2.1

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

то вероятность ошибки распознавания будет минимальна (см. § 3.1):

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

Точность работы распознающего устройства, определяемая не равна предельно достижимой точности, ввиду того что в общем случае

отличаются от условных плотностей распределений соответствующих генеральной совокупности объектов первого и второго классов.

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

соответствующая скорректированным описаниям классов и также будет минимальна.

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

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

Каким условиям применительно к рассматриваемому примеру должна удовлетворять исходная выборка для того, чтобы процесс обучения протекал успешно?

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

Оценка математического ожидания значений признаков объектов класса полученной выборки

При достаточно большом величина приблизительно равна

истинному значению математического ожидания значений признаков объектов класса

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

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

Подставляя (2.30) и (2.31) в (2.29), получим

Новая оценка лучше исходной априорной оценки математического ожидания, если

или

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

Аналогичные рассуждения применительно к классу приводят к следующему соотношению, определяющему условия уточнения оценки математического ожидания значений признаков объектов класса

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

Рассмотрим формальную постановку задачи обучения. При этом заметим следующее. Вслед за появлением первых работ в области распознавания, в частности работ Ф. Розенблатта, посвященных перцептрону, различными авторами был разработан целый ряд алгоритмов обучения. Только в середине 60-х годов Я. 3. Цыпкин установил, что все эти алгоритмы могут быть получены по одной и той же схеме (4, 5]. Дальнейшее изложение процедуры обучения осуществляется в соответствии с этой схемой.

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

В целях наглядности изложения ограничимся классами т. е. ситуацией, носящей название дихотомии. К дихотомии можно последовательно свести и общий случай, когда число классов Обозначим разделяющую функцию через

где с неизвестный вектор параметров.

Разделяющая функция представлена, как следует из (2.36), в виде некоторой функции скалярного произведения векторов и с. Знаки разделяющей функции определяют области в -мерном признаковом пространстве соответствующие классам

Наличие обучающей выборки озволяет получить указания о принадлежности объектов классу или классу

Эти указания могут быть использованы для определения двух систем неравенств. Если с помощью разделяющей функции объект классифицируется правильно, то

а если ошибочно, то

В качестве меры уклонения от у выберем некоторую выпуклую функцию от разности у и у:

В процессе обучения предъявление объектов осуществляется случайным образом, вследствие этого и мера уклонения также случайна, поэтому в качестве меры, характеризующей,

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

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

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

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

Этап 2. На этом этапе текущая апостериорная информация, полученная в результате распознавания этих объектов, используется для уточнения значения вектора и получения такого его значения при котором достигается минимальное значение вероятности ошибочных решений задачи распознавания.

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

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

где - функционал вектора с, зависящий также от случайных реализаций процесса пространство вектора

Так как для каждой реализации случайный функционал, то математическое ожидание:

Если функционал — непрерывно дифференцируем по с, то необходимые условия экстремума (2.46) можно записать в виде уравнения

где

— градиент функционала по , а

— градиент случайного функционала по .

Если функционал выпуклый и имеет единственный экстремум, то условие (2.47) — необходимое и достаточное. В этом случае корень уравнения определяет оптимальное значение при котором функционал достигает экстремума.

В условиях полной априорной, информации плотность распределения известна, поэтому функционал можно выразить в явной форме, а оптимальное значение определить.

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

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

а непрерывный алгоритм обучения может быть записан так:

В (2.50) и квадратная -мерная матрица, полная или диагональная, элементы которой зависят от текущего момента времени . С течением времени элементы матрицы должны

стремиться к нулю, так как только при этом условии вектор с стремится к оптимальному значению с вероятностью единица.

Если диагональная матрица (полная матрица соответствует линейному преобразованию диагональной) и ее элементы равны друг другу:

единичная матрица), то алгоритмы обучения (2.50) и (2.51) представляют собой соответственно дискретные и непрерывные алгоритмы стохастической аппроксимации [5].

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

или

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

или

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

Возвратимся к исходной задаче обучения распознаванию объектов. Рассмотрим алгоритмы решения (2.46), заметив, что . Ограничивающее условие, накладываемое на поиск экстремума функционала соблюдается, в частности, в случае, если представляет собой конечную сумму:

или

где -соответственно -мерные векторы коэффициентов и линейно независимых функций; знак транспонирования.

Подставляя (2.58) в (2.46), получаем

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

где

Применяя к (2.61) дискретный алгоритм обучения (2 50) либо непрерывный алгоритм (2.51), соответственно получим:

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

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

Определим в первом приближении оценки:

На этом завершается первый этап работы.

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

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

где -оценка, полученная на предыдущем шаге (после распознавания объектов).

Если выбрано так, что

то последовательные оценки стремятся к величине в смысле среднего квадрата с вероятностью единица. На этом завершается второй этап работы.