Методы распознавания образов

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

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

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

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

Если теперь допустить, что настолько мала, что внутри неё меняется незначительно, то

,

где - объём области , - точка внутри .

Тогда . Но , следовательно, .

Итак, оценкой плотности является величина

. (*)

Без доказательства приведём утверждение, что условия

и (**)

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

Этому условию удовлетворяет, например, .

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

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

, а .

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

2.2 Правило ближайшего соседа

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

.

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

2.3 Параметрическое оценивание распределений

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

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

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

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

,

из которой определяются оценки .

Для одномерного нормального закона

.

.

2.4 Метод максимума правдоподобия

Функция правдоподобия, введённая Фишером, выглядит следующим образом:

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

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

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

Справедлива следующая теорема (приводится без доказательства). Если существует для эффективная оценка , то уравнение правдоподобия имеет единственное решение. Это решение при сходится к истинному значению .

Всё это справедливо и при нескольких неизвестных параметрах. Например, для одномерного нормального закона

,

,

отсюда при .

,

отсюда .

Оценка называется несмещённой, если математическое ожидание оценки равно . Оценка является несмещённой. Действительно, поскольку - простой случайный выбор из генеральной совокупности, то и .

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

.

Следовательно,

Найдём математическое ожидание этой величины:

.

Так как дисперсия не зависит от значения , то выберем . Тогда

, , ,

где , - коэффициент корреляции между и (в данном случае он равен нулю, т.к. и не зависят друг от друга).

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

.

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

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

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

Особенно заметно упрощение процедуры распознавания по методу Байеса, если признаки принимают двоичные значения. В этом случае обучение состоит в построении следующей таблицы:

					...
					...
					...
					...
. . .	. . .	. . .	. . .	. . .	. . .	. . .
					...

Здесь , .

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

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

2.6 Распознавание при неизвестных априорных вероятностях образов

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

2.7 Минимаксный критерий

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

Алгоритмически одним из наиболее простых является метод Монте-Карло. Случайным образом раз выбираются векторы Тот вектор, при котором максимальная компонента принимает наименьшее значение, принимается для использования. Чем больше , тем выше вероятность "попадания" в ближайшую окрестность оптимального вектора . Возможен, конечно, и полный перебор вариантов, но он приемлем лишь при не очень большом числе возможных . В некоторых частных задачах может быть реализован аналитический подход к поиску . Рассмотрим случай с двумя образами (рис. 21).

Решение минимаксной задачи лежит на отрезке прямой Обозначим через область объектов первого образа, а через - второго. Ясно, что При этом средняя вероятность ошибок распознавания определяется величиной Построим график (рис. 22).

Рис. 21. Область решения задачи определения по минимаксному критерию

Очевидно, что при и =1. Между ними находятся значения, при которых, в том числе максимальное её значение. Допустим, что мы выбрали =. Тогда как функция истинного (но неизвестного) значения лежит на прямой, касательной к в точке, соответствующей =. При этом если истинное значение лежит левее точки (например, =), то фактическая средняя ошибка распознавания () окажется меньше, чем прогнозируемая при =. Зато если истинное значение =, то фактическая средняя ошибка () окажется существенно больше прогнозируемой. Аналогичные рассуждения можно привести и для правого склона кривой, положив, например, =. Лишь выбрав =, что соответствует максимуму кривой, мы гарантируем, что не превзойдёт , каково бы ни было истинное значение.

Рис. 22. Зависимость вероятности ошибки распознавания от

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

Обозначим через . Необходимо найти такое значение , при котором

где .

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

2.8 Критерий Неймана-Пирсона

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

Пусть требуется . Нужно решить задачу нахождения

.

Ясно, что решение удовлетворяет условию Действительно, при возрастает, то есть становится не минимально возможным, а при нарушается ограничение. Как и в минимаксном методе, найти аналитически удаётся лишь в простейших случаях.

2.9 Последовательные процедуры распознавания

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

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

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

Пусть и известны где Заметим, что если известно распределение то известны и все распределения меньшей размерности (так называемые маргинальные распределения). Например,



Пусть измерено признаков. Строим отношение правдоподобия Если , то объект относим к образу , если , то к образу . Если же , то измеряется признак и вычисляется отношение правдоподобия и т.д.

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

,

,

(нижний порог).

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

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

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

Для оптимальность процедуры не доказана.

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

2.10 Аппроксимационный метод оценки распределений по выборке

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

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



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

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

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

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

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

Нормальный закон, как известно, характеризуется вектором средних значений признаков и матрицей ковариаций. Особое место в ряде задач занимают нормальные законы с диагональными ковариационными матрицами (в компонентах признаки статистически независимы). При этом удаётся оптимизировать последовательную процедуру измерения признаков, даже если в восстановленном распределении признаки зависимы. Рассмотрение этого вопроса выходит за рамки курса. Интересующиеся могут обратиться к рекомендованной литературе [2].

Для облегчения понимания аппроксимационного метода будем рассматривать упрощённый вариант, а именно: одномерные распределения.

Итак,

где - для непрерывных признаков, - для дискретных признаков,

- вектор параметров базового распределения (компоненты),

- весовой коэффициент -й компоненты,

- математическое ожидание -й нормальной компоненты,

- среднеквадратическое отклонение -й нормальной компоненты,

- параметр -й биномиальной компоненты,

- число градаций дискретного признака,

- число сочетаний из по .

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

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

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

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

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

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

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

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

,

причём и стремится к нулю при .

Для одномерного нормального закона

.

Решая уравнение и , получим для -го шага

,

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

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

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

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

Воспользуемся мерой неопределённости К. Шеннона для поиска :

где - энтропия распределения ,

- знак математического ожидания,

- плотность вероятности значений непрерывных признаков.

При последовательном увеличении значений имеют место две тенденции:

уменьшение энтропии за счёт разделения выборки на части с уменьшающимся разбросом значений наблюдаемых величин внутри подвыборок (компонент смеси);

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

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

где - область определения ,

- область определения , - выборочные оценки и .

В соответствии с формулой Байеса

Рис. 23. Иллюстрация тенденций, формирующих

Если априорное распределение неизвестно, то целесообразно использовать равномерное распределение по всей области

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

Можно показать, что хорошо аппроксимируется нормальным законом с математическим ожиданием, равным - выборочному среднему, и дисперсией, равной выборочной дисперсии , умноженной на . Как видно из формулы, стремится к единице при , возрастает с уменьшением и накладывает ограничения на объём выборки (рис. 24).

Рис. 24. Зависимость поправочного коэффициента от объёма выборки N

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

Объём подвыборки для q-й компоненты смеси определяется по формуле .

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

Более подробное и углублённое изложение аппроксимационного метода желающие могут найти в рекомендованной литературе [2], [4].

2.11 Таксономия

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

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



Рис. 25. Объединение компонент смеси в таксоны

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

Естественно, объединять в один таксон следует те компоненты смеси, которые наименее разнесены в признаковом пространстве. Мерой разнесённости компонент может служить, например, мера Кульбака

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

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

Алгоритм ФОРЭЛЬ близок по своей сути к аппроксимации распределения смесью нормальных плотностей вероятностей значений признаков, причём матрицы ковариаций компонент смеси диагональны, элементы этих матриц равны между собой, распределения компонент отличаются друг от друга только векторами средних значений. Однако на одинаковый результат таксономии даже в этом случае можно рассчитывать лишь при большой разнесённости компонент смеси. Объединение нескольких смесей в один таксон по методике близко к эмпирическому алгоритму KRAB 2. Эти два подхода взаимно дополняют друг друга. Когда выборка мала и статистические методы неприменимы или малоэффективны, целесообразно использовать алгоритм KRAB, FOREL, KRAB 2. При большом объёме выборки эффективнее становятся статистические методы, в том числе объединение компонент смеси в таксоны.

2.12 Оценка информативности признаков

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

При решении задач распознавания решающим критерием является риск потерь и как частный случай - вероятность ошибок распознавания. Для использования этого критерия необходимо для каждого признака (группы признаков) провести обучение и контроль, что является достаточно громоздким процессом, особенно при больших объёмах выборок. Именно это и характерно для статистических методов. Хорошо, если обучение состоит в построении распределений значений признаков для каждого образа . Тогда, если нам удалось построить в исходном признаковом пространстве, распределение по какому-либо признаку (группе признаков) получается как проекция на соответствующую ось (в соответствующее подпространство) исходного признакового пространства (маргинальные распределения). В этом случае повторных обучений проводить не нужно, следует лишь оценить вероятность ошибок распознавания. Это можно осуществить различными способами. Рассмотрим некоторые из них.

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

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

В связи с этим представляют интерес другие меры информативности признаков, вычисляемые с меньшими затратами вычислительных ресурсов, чем оценка вероятности ошибок распознавания. Такие меры могут быть не связаны взаимооднозначно с вероятностями ошибок, но для выбора наиболее информативной подсистемы признаков это не столь существенно, так как в данном случае важно не абсолютное значение риска потерь, а сравнительная ценность различных признаков (групп признаков). Смысл критериев классификационной информативности, как и при детерминистском подходе, состоит в количественной мере "разнесённости" распределений значений признаков различных образов. В частности, в математической статистике используются оценки верхней ошибки классификации Чернова (для двух классов), связанные с ней расстояния Бхатачария, Махаланобиса. Для иллюстрации приведём выражение расстояния Махаланобиса для двух нормальных распределений, отличающихся только векторами средних и :

где - матрица ковариаций,

- транспонирование матрицы,

-1 - обращение матрицы.

В одномерном случае откуда видно, что тем больше, чем удалённее друг от друга и и компактнее распределения (меньше ).

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

Определим следующим образом среднюю информацию в пространстве для различения в пользу против :

При этом предполагается, что нет областей, где а , и наоборот.

Аналогично

Назовём расхождением величину

Чем расхождение больше, тем выше классификационная информативность признаков.

Очевидно, что при В других случаях Действительно, если , где в области справедливо , а в - , то причём и .

Легко убедиться, что если признаки (признаковые пространства) и независимы, то

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

Оказывается, что в этом конкретном случае расхождение равно расстоянию Махаланобиса

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

2.13 Иерархические системы распознавания

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

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

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

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

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

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

Рассмотрим статистический подход к распознаванию в двухуровневой иерархической системе (рис. 26). Пусть на первом уровне распознаются образы где - номер позиции в последовательности выдаваемой первой ступенью для распознавания на вторую ступень; - номер конкурирующего образа первой ступени на -й позиции в последовательности.

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

Здесь - априорная вероятность образа - вектор параметров, характеризующих объекты на входе первой ступени распознавания.

Рис. 26. Ориентированный граф, иллюстрирующий процесс распознавания в двухступенчатой системе

Если говорить о последовательности букв, то каждая из них распознаётся независимо от других, поэтому

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

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

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

.

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

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

Эффективность такого подхода для исправления ошибок первой ступени распознавания за счёт языковой избыточности подтверждена практическими испытаниями. Да это в некоторых случаях ясно и умозрительно. Например, при распознавании последовательности букв рассмотренный алгоритм уж точно обнаружит, а в большинстве случаев и исправит такие ошибки, как "гласная - твёрдый (мягкий) знак", "пробел - твёрдый (мягкий) знак", "мягкий знак - э" и ряд других.

Заключение

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

Рекомендуемая литература

Айзерман А.А., Браверман Э.М., Розоноэр Э.И. Метод потенциальных функций в теории обучения машин. - М.: Наука, 1970.

Волошин Г.Я., Бурлаков И.А., Косенкова С.Т. Статистические методы решения задач распознавания, основанные на аппроксимационном подходе. - Владивосток: ТОИ ДВО РАН, 1992.

Горелик А.Л., Скрипкин В.А. Методы распознавания. - М.: Высш. шк., 1977.

Дуда Р., Харт П. Распознавание образов и анализ сцен. - М.: Мир, 1976.

Загоруйко Н.Г. Методы распознавания и их применение. - М.: Сов. радио, 1972.

Загоруйко Н.Г., Ёлкина В.Н., Емельянов С.В., Лбов Г.С. Пакет прикладных программ ОТЭКС. - М.: Финансы и статистика, 1986.

Патрик Э. Основы теории распознавания образов. - М.: Сов. радио, 1980.

Фу К.С. Последовательные методы в распознавании образов и обучении машин. - М.: Наука, 1971.

Фу К.С. Структурные методы в распознавании образов. - М.: Мир, 1977.

Размещено на Allbest.ru