Основные определения курса «Распознавание Образов»

 

2й  этап. Построение графика количества найденных классов от размера гиперсферы и поиск участка, где изменение радиуса «долго» не приводило к изменению количества классов.

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

3й  этап. Считывание радиуса и центров гиперсфер соответсвующих варианту выбранному на предыдущем шаге из файла созданного на 1ом шаге. 

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

P(a) – вероятность наступления события а 

P(a,b) – вероятность того, что события а и b наступают одновременно. Если а и b – статистически независимые переменные, то P(a,b) = P(a)P(b) 

если события  зависимые, то P(a,b) = P(b,a) = P(a)*P(b|a) = P(b)*P(a|b) 

отметим, что  из этого равенства следует формула  Баеса: 

P(a|b) = P(b|a)*P(a)/P(b) 

то есть это  можно считать выводом формулы  Баеса для распознавания образов, если вместо a и b подставить соответствующие события, описанные ниже. 

P(a|b) – условная вероятность. Вероятность наступления события a, при условии что событие b наступило 

P(Ck,x) = P(x, Ck). Вероятность того что объект имеет признаки, заданные вектором х и при этом принадлежит классу Сk 

P(Ck|x) - вероятность того, что объект относится к классу Сk, при условии, что его признаки описываются вектором х. Также называется «апостериорная вероятность класса Ck», т.е. иными словами, вероятность после измерения величины х. 

P(x|Сk)  - вероятность того, что объект имеет признаки, описываемые вектором х, при условии что объект относится к классу Ck 

P(Ck) – вероятность того, что данный объект относится к классу Ck. Также называется «априорная вероятность класса Ck» 

P(x) – вероятность того, что признаки произвольного объекта из множества объектов задачи распознавания будут иметь вектор признаков х 

p(x) – функция плотности распределения случайной величины х.  

формула Баеса  для дискретных распределений 

P(Ck|x) = P(x|Ck)*P(Ck)/P(x) 

P(C1|x) + P(C2|x) + …  P(CM|x) = 1 (где М- число классов в задаче распознавания. Это очевидно, так как объект всегда принадлежит одному из классов в задаче распознавания) 

Подставляя в  эту формулу  формулу Баеса  получаем: 

P(x|C1)*P(C1)/P(x) + P(x|C2)*P(C2)/P(x) + … + P(x|CM)*P(CM)/P(x) = 1 

домножаем на P(x), эта вероятность очевидно не нулевая

получаем 

P(x|C1)*P(C1) + P(x|C2)*P(C2) + … + P(x|CM)*P(CM) = P(x) 

поэтому формулу  Баеса можно записать и без  P(x): 

P(Ck|x) = P(x|Ck)*P(Ck) /

      [P(x|C1)*P(C1) + P(x|C2)*P(C2) + … + P(x|CM)*P(CM)] 

Формула Баеса для непрерывных  распределений: 

P(Ck|x) = p(x|Ck)*P(Ck) /

      [p(x|C1)*P(C1) + p(x|C2)*P(C2) + … + p(x|CM)*P(CM)] 

Вывод для одномерного случая:

Последнее равенство  возможно, так как получается, что  выражение не зависит от dx. 

Матрица потерь: 

Uij - диагональные элементы означают бонус, который мы получаем за правильное распознавание, остальные элементы означают потери, которые мы понесем, если объект j распознаем как i.  

 

Пример матрицы  потерь:

Задача –  построить матрицу потерь для  системы «банк купюр». Система  распознает денежные купюры достоинством 10 100 и 1000 единиц и раскладывает по соответствующим полкам. Хранение каждой распознанной купюры обходится в 50 единиц. Поэтому после распознавания, все купюры достоинством 10 единиц уничтожаются. Купюры достоинством 1000 единиц нужно проверить на подлинность, что стоит 100 единиц. Несовпадение номиналов при провеке вызывает перепроверку всех купюр, которая стоит 1000 

 

итоговая матрица: 

 

Предположим система  выдает равные вероятности на все  три купюры (по 1/3). Какое нужно  принять решение чтобы минимизировать риск потерь (максимизировать выгоду)? 

Если примем решение, что это «10», то средний риск потерь (через мат. ожидание) =

0*1/3 + (-50)*1/3 + (-850)*1/3 = -900/3 = -300 

Если примем решение, что это «100», то средний  риск потерь (через мат. ожидание) =

-1040*1/3 + 50*1/3 + (-50)*1/3 = ~ - 347 

Если примем решение, что это «1000», то средний риск потерь (через мат. ожидание) =

-1140*1/3 + (-1050)*1/3 + 850*1/3 = ~ - 447 

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

Итак, решающее правило с учетом матрицы потерь можно записать так: 

arg max [U*p],

где U – матрица потерь, p – вектор решений классфикатора [P(C1|x)…P(CM|x)]^T, *-умножение матрицы на вектор 

Заметим, что  если матрица диагональная 

 

То arg max [U*p] = arg max p, т.е. выбирается решение, соответствующее максимальному выходу классификатора. 

Рандомизированное решающее правило. Определение см. в Metogy_r.doc, стр 38. 
 
 

Отказ от гипотезы о компактности. В статистических методах мы имеем дело с вероятностями событий (условными вероятностями принадлежности объектов к определенным классам при условии, что их признаки принимают определенные значения) и абстрагируемся от истинных причин принадлежности объектов к тем или иным классам. Мы не говорим о «расстоянии» между векторами признаков объектов в пространстве признаков.

Если детерминистические методы основаны на понятии «схожести» и расстоянии между объектами  классов, то статистические методы основаны на построении функций распределения.  

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

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

2 способа распознавания  по формуле Байеса. В первом случае моделируются распределения и с учетом априорных вероятностей вычисляются апостериорные вероятности. Во втором случае просто пространство признаков делится на области принятия решений. 

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

Статистическая  интерпретация метода к-ближайших соседей. Очень грубая оценка распределений дает: 

Пусть V – гиперсфера заданного радиуса в пространстве признаков, с центром в точке соответствующей вектору (х)  признаков распознаваемого объекта. 

Пусть Nk – число объектов класса k, попавших в гиперсферу V

TOTALk – число объектов класса k, попавших в обучающую выборку

TOTAL – общее число объектов в обучающей выборке

ALL in V – общее число объектов обучающей выборки, попавших в V 

p(x|Ck) ~ P(x in V | Ck) / V,  V->0 

P(x in V| Ck) ~ Nk (in V) / TOTALk                     если TOTALk ->inf 

P(Ck) ~ TOTALk / TOTAL                                  ~ Nk / ALL in V, V->inf 

p(x) = P(x in V) / V, V->0 ~ [ALL in V / TOTAL] / V 

P(Ck | x) = p(x | Ck) P(Ck) / p(x) ~ 

[Nk / (TOTALk*V)]*[TOTALk/TOTAL] * [V*TOTAL/[ALL in V]] = Nk/[ALL in V]  

То есть P(Ck|x) = Nk/[ALL in V] 

Заметим, что  

P(C1|x)+P(C2|x)+… = N1/[ALL in V] + N2/[ALL in V] +… = [ALL in V]/[ALL in V] = 1 

Получился метод к-ближайших соседей (к соседей заключенных в гиперкуб объемом V)

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

Если [ALL in V] = 1, то получается метод ближайшего соседа. 

Другие способы  оценки распределений: 

Параметрическая оценка нормального распределения: p(x|Ck) = Aexp(-(x-m)^2/g), где m – среднее для векторов признаков класса Ck, g – пропорциональна дисперсии, А – нормировочная константа (зависит от g). 

Последовательная процедура распознавания – если измерение признаков дорого обходится, можно решать задачу последовательно для n измерений пространства признаков n = 1…n(max). На каждом шаге оценивать разрешаюшую способность  

max P(Ck|x)

---------------------

max P(Cj|x) , j<>k 

Если разрешающая  способность превышает заданный порог (например 2 будет означать, что мы как минимум в 2 раза более уверены в одном из решений относительно любого другого), то принимается решение на этом шаге либо по максимальной вероятности либо исходя из матрицы потерь. В противном случае мы измеряем следующий признак до тех пор пока признаки не кончатся. Если разрешающий критерий не достигается при всех измеренных признаках необходимо принимать решение с теми вероятностями P(Ck|x), которые получились, либо вообще отказаться от принятия решения и выдать ответ «не могу решить задачу с требуемой точностью». 

Распознавание при неизвестных  априорных вероятностях. Самый простой способ – метод монте-карло. Подробности см. metogy.doc 

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