Метод потенциальных функций

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

Рис. 8. Иллюстрация синтеза потенциальной функции в процессе обучения:

 – потенциальная функция, порождаемая одиночным объектом;

  – суммарная потенциальная функция, порождённая обучающей последовательностью

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

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

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

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

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

Структурные (лингвистические) методы

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

Рис. 9. Изображение (а) и его иерархическое структурное описание (б)

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

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

Рис. 10. Прямоугольник (а) и его непроизводные элементы (б)

На рис. 11 приведён более сложный пример структурного описания цифры 9.

Рис. 11. Изображение цифры 9 и его структурное описание

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

В качестве примера приведём фрагменты языка описания изображений PDL (Picture Description Language). Определены непроизводные элементы

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

головная точка примыкает к хвостовой точке ;

хвостовая точка примыкает к хвостовой точке ;

головная точка примыкает к головной точке ;

головная точка примыкает к головной точке и хвостовая точка примыкает к хвостовой точке .

На рис. 12 приведено выражение на языке PDL, описывающее букву .

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

Более детальную информацию о структурном подходе можно почерпнуть в рекомендованной для самостоятельных занятий литературе [9].

Рис. 12. Структурное описание буквы А на языке PDL