[Из песочницы] Распознавание образов. Метод потенциальных фунций

Здравствуйте, я давно читаю Хабрахабр и часто мне попадались статьи про нейронные сети, в частности про однослойный перцептрон. Но пока еще мне не встретилась статья про другие виды распознающих функций перцептронного вида. Как следует из названия статьи данный вид распознающих функций называется методом потенциальных функций.

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

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

Основные понятия

Изображение — отображение объекта на воспринимающие органы. То есть, описание объекта, как множество признаков. Часто объект представляется в виде вектора. Если множество признаков постоянное, то объект отождествляется с его изображением.

Образ (класс) — подмножество множества объектов или изображений.

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

Краткое описание

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

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



Физическая интерпретация

Представим n-мерное метрическое пространство, где n — количество признаков, необходимых для описания объекта.

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

Тогда в областях, где преобладают объекты класса W1 будет положительный потенциал, и наоборот.

Фактически, каждому объекту из обучающей выборки присваивается заряд, который «притягивает» классифицируемый объект к соответствующему классу.

Потенциальная функция

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

Потенциальную функцию будем обозначать, как K(x,xk), где xk, k=1..m — это один из объектов(векторов) из обучающей выборки.

Обычно, в качестве потенциальной функции используют симметрическую функцию, двух переменных — X и Xk.

Например, K(x,xk) = exp {-a || x-xk||^2 }

Решающая функция. Кумулятивный потенциал.

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

Кумулятивный потенциал находится следующим образом:

Условиями прекращения работы алгоритма будет безошибочное определение L0 объектов, подряд. Где L0 — число, заданное пользователем. Задается оно в зависимости от того, какое качество работы алгоритма требуется, исходя из следующих фактов:

p — вероятность совершения ошибки после предъявления Lk выборочных объектов.

Тогда для любых e>0 и a>0, вероятность того, что p<e, будет больше, чем 1-a, если

L0> log (ea) / log (1-e)

Вывод. Достоинства и недостатки.

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

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

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

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

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

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.