Вероятностная задача распознавания

Введение

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

Задача распознавания

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

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

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

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

Основные понятия и определения

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

которые называются классами объектов. Над каждым объектом А производится N измерений, результаты которых  называются признаками данного объекта. Таким образом, каждый объект изображается вектором признаков  в N-мерном пространстве, которое называется пространством признаков.

На вход распознающей системы поступает последовательность векторов признаков соответствующих набору объектов А1, …, Аn,… из . Последовательность (1.1) называется обучающей последовательностью, или обучающей выборкой.

x1,…xn,…,xk = x(Ak) (1.1)

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

Постановку задачи можно еще более детализировать, рассматривая отдельно три случая: детерминированная задача распознавания, вероятностная задача распознавания и самообучение (автоматическая классификация). Остановимся подробнее на вероятностной задаче распознавания.

Вероятностная задача распознавания

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

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

Очевидно, распределение случайной величины  будет иметь плотность:

(этот факт следует из формулы полной вероятности).

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

Байесовским решающим правилом называется решающее правило, минимизирующее средний риск отнесения объектов k-го класса в i-й класс.

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

Рассмотрим один очень важный частный случай построения оптимального решающего правила. Пусть матрица потерь имеет вид:

Тогда оптимальное разбиение состоит из множеств:

что соответствует решающему правилу: х относится к если

 для всех  (1.2)

Итак, мы имеем вид решающего правила, минимизирующего функционал среднего риска.

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

- оценивание плотностей распределения,

- непосредственное восстановление параметров оптимального решающего правила.

Рассмотрим в отдельности оценивание плотностей распределения.

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

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