Статистические методы распознавания.

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

P = sum[ p (i)·prob(D (x)+ i | x классу i)]

где m - число классов,

p (i) = prob (x принадлежит классу i) - априорная вероятность принадлежности произвольного образа x к i -му классу (частота появления образов i -го класса),

D (x) - функция, принимающая классификационное решение (вектору признаков x ставит в соответствие номер класса i из множества {1,2,..., m }),

prob(D (x) не равно i | x принадлежит классу i) - вероятность события " D (x) не равно i " при выполнении условия принадлежности x классу i, т.е. вероятность вынесения ошибочного решения функцией D (x) для данного значения x, принадлежащего i -му классу.

Можно показать, что вероятность неправильной классификации достигает минимума, если D (x)= i в том и только в том случае, если p (x | i)· p (i)> p (x|j)· p (j), для всех i+j, где p (x|i) - плотность распределения образов i -го класса в пространстве признаков.

Согласно приведенному правилу точка x относится к тому классу, которому соответствует максимальное значение p (i) p (x|i), т.е. произведение априорной вероятности (частоты) появления образов i -го класса и плотности распределения образов i -го класса в пространстве признаков. Представленное правило классификации называется байесовским, т.к. оно следует из известной в теории вероятности формулы Байеса.

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

Каждый входной сигнал представляет собой 0 или 1. В результате передачи сигнала на выходе канала появляется величина x, на которую налагается Гауссовский шум с нулевым средним значением и дисперсией б.

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

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

p(1)=a/1000, p(2)=b/1000.

Т.к. шум является гауссовским, т.е. подчиняется нормальному (гауссовскому) закону распределения, то плотностьраспределения образов первого класса в зависимости от значения x, или, что тоже самое, вероятность получения на выходе величины x при подаче на входе сигнала 1 определяется выражением

p (x ¦1) =(2piб)^-1/2exp(-(x -1)²/(2б²)),

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

p (x ¦2)= (2piб)^-1/2exp(- x ²/(2б²)),

Применение байесовского решающего правила приводит к выводу, что передан сигнал класса 2, т.е. передан ноль, если

p (2) p (x ¦2) > p (1) p (x ¦1)

или, более конкретно, если

b exp(- x ²/(2б²)) > a exp(-(x -1) ²/(2б²)),

Поделив левую часть неравенства на правую, получим

(b / a) exp((1-2 x)/(2б²)) >1,

откуда после логарифмирования находим

1-2 x > 2б² ln(a/b)

или

x < 0.5 - б² ln(a/b)

Из полученного неравенства следует, что при a=b, т.е. при одинаковых априорных вероятностях появления сигналов 0 и 1, образу присваивается значение 0 когда x <0.5, а значение 1, когда x >0.5.

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

Так при a/b =2.71 (что соответствует в 2.71 раза более частой передаче единиц) и б²=0.1, образу присваивается значение 0, если x <0.4, и значение 1, если x >0.4. Если информация об априорных вероятностях распределения отсутствует, то могут быть использованы статистические методы распознавания, в основу которых положены иные, отличные от байесовского, правила классификации.

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

9. Структурно-лингвистический подход к задаче распознавания графических образов. Пример.