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

Статистические методы основываются на минимизации вероятности ошибки классификации. Вероятность 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-2x > 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. Структурно-лингвистический подход к задаче распознавания графических образов. Пример.