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

В работах М.Айзермана, Э.Бравермана, Л.Розоноэра в журнале "АиТ"(Автоматика и телемеханика) 1964; №6,9,12; "АиТ" №11,1965; а также Айзерман М.А., Бравеман Э.М., Розоноэр Л.Н. Проблема обучения машин распознаванию внешних ситуаций - В сб.: Самообучающиеся автоматические системы, Наука,1966 , были разработаны и исследованы алгоритмы распознавания, в основу которых положены так называемые потенциальные функции. Предлагаемые авторами алгоритмы базируются на основной гипотезе о характере функций, разделяющих множества, соответствующие разным образам.

1.7.1. Геометрическая интерпретация метода

Для упрощения, но без ограничения общности, рассмотрим задачу РО для двух классов , .
Будем считать, что в пространстве входных описаний каждому входному изображению S(x) соответствует единственная точка пространства X. Допустим, что классы и не пересекаются. Это означает, что в пространстве входных описаний X существует, по крайней мере, одна функция, которая полностью разделяет множества изображений, принадлежащих разным образам. Эта функция должна принимать значения в точках, соответствующих изображениям образа и для . В общем случае таких разделяющих функций может быть много. В процессе обучения распознающей системе последовательно предъявляют изображения, которым соответствуют точки пространства X. При этом известно, к какому классу или принадлежат предъявляемые изображения. Метод потенциальных функций связан со следующей процедурой. При показе (предъявлении) в ходе обучения некоторого изображения , которому соответствует точка в пространстве X, с ним связывается функция , заданная на всем пространстве X и зависящая от как от параметра. Такая функция называется потенциальной. Обучающей последовательности и точкам пространства X соответствует последовательность потенциальных функций , которая используется для построения разделяющей функции при помощи определяющих правил. Правила формирования функций должны быть такими, чтобы по мере увеличения числа предъявленных изображений функция стремилась бы к одной из разделяющих функций.

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

. (1)

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

. (1а)

Однако нам желательно, чтобы разделяющая функция (согласно (1)) разлагалась в ряд с конечным числом членов N. Из этого следует, что разделяющие функции в пространстве X должна быть достаточно гладкими и не иметь большого числа экстремумов в малой области. Используя (1) можно ввести в рассмотрение N-мерное пространство Z, на которое отображается исходное пространство X. Каждой точке пространства X ставится в соответствие точка пространства Z согласно соотношению , i=1,2..N.

В силу условия (1) разделяющая функция отражается в линейную функцию в пространстве Z и обладает следующим свойством:

. (2)

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

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

В качестве потенциальной функции принимается скалярная функция двух векторных аргументов вида

, (3)

где - линейно-независимая система функций; - действительные числа, отличные от 0 для всех i; - точка, появляющаяся в ходе обучения.

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

. (4)

Далее пусть после i-го предъявления построен потенциал .

На следующем (i+1)-м шаге обучения показывается точка . В результате возможны 4 случая:

1. 
2. (5)
3. 
4. 

В случаях 1 и 2 алгоритм правильно классифицирует изображение . В этом случае принимается

. (6)

В 3 и 4 случаях имеется ошибка классификации и необходима коррекция потенциальной функции.

Для случая 3 принимаем (7)

Для случая 4 принимаем (8)

Построенный после i-го шага потенциал можно записать следующим образом:

(9)

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

В работах авторов было разработано несколько алгоритмов РО, основанных на методе потенциальных функций.

Различие между вариантами алгоритма сводится в основном к выбору законов коррекции разделяющей функции от шага к шагу.

Первый алгоритм.

Будем считать, что построена функция , а на (i+1)-м шаге предъявлена т. , для которой известно действительное (требуемое) значение функции . Оно сообщается учителем. Тогда функция строится по следующему правилу:

, (10)

где - действительное значение разделяющей функции в т.;

- любая последовательность чисел, удовлетворяющая следующим условиям:

Например, .

Сходимость алгоритма обосновывается следующей теоремой, доказательство которой см. [Айзерман М.А., Бравуман Э.М., Метод потенциальных функций в задаче восстановления характеристики функционального преобразователя по случайно наблюдаемым токам, АиТ, № 12,1964].

Теорема 1. Пусть - последовательность независимых случайных точек из X, а – последовательность вероятностей их появления.

Пусть – функция, удовлетворяющая условию (1)

(1)

Тогда последовательность функций (i=1,2,..), определяемых рекуррентными соотношениями (10) при удовлетворяет условию:

. (11)

Второй алгоритм.

Как и прежде, полагаем .

, (12)

где - произвольная положительная константа, удовлетворяющая условию:

, (13)

где - действительное значение разделяющей функции на т. .

Сходимость этого алгоритма подтверждается следующей теоремой:

Теорема 2. Пусть выполняются те же условия, что и в теореме 1. Тогда последовательность функций (i=1,2,..), определяемых рекуррентным соотношением (12) при удовлетворяет условиям:

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

по формулам

1. , j=1,2,…,n (15)
2. , j=1,2,…,n (16)

Данные алгоритмы являются алгоритмами статистической оптимизации, частными случаями метода СКГ. Описанным алгоритмам можно дать удобную геометрическую интерпретацию используя для этого процесс обучения. Будем считать, что в пространстве X существует разделяющая поверхность , представимая разложением (1), причем такая, что выполняются условия (2). Тогда в спрямляющем пространстве существует проходящая через начало координат разделяющая плоскость с направляющим вектором V:

, такая что

. (17)

Отобразив множество симметрично относительно начала координат, получим множество , где - отображение множества . (См. рис.1)

Рис.1

Множества и разделимы плоскостью с направляющим вектором V () при условии, что

.

Другими словами множества и разделяются этой плоскостью при условии, что объединенная область V лежит по одну сторону от нее. Поставим в соответствие последовательность М точек из пространства X, принадлежащих множествам и , и последовательность М точек из . Потенциальная функция (3) может быть представлена в спрямляющем пространстве Z как скалярное произведение двух векторов

и . (18)

Тогда выражения (3) для потенциальной функции можно представить в следующем виде:

. (19)

Теперь выражение (9) можно переписать так:

. (20)

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

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

. (20а)

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

Исправление ошибки в т. будет происходить при условии .

На основании этого можно утверждать, что (k+1)-е исправление ошибки произойдет, если

. (21)

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

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

(22)

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

Рис 2

Сходимость алгоритма потенциальных функций и условие его остановки.

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

Теорема 3 Пусть М – произвольная бесконечная последовательность точек пространства X, принадлежащих множествам и . Предположим, что существует функция такая, что:

(24)

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

где . (25)

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

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

Теорема 4. Пусть множества и в пространстве X таковы, что существует разделяющая функция, удовлетворяющая условию (24), представимая разложением (1). Пусть функция ограничена при . Предположим, что появление изображений из обучающей последовательности суть независимые случайные события и, каким бы ни было n, к n-му шагу алгоритма имеется строго положительная вероятность исправления ошибки при условии, что к этому шагу не произошло полного разделения множеств V₁ и V₂ . Тогда с вероятностью, равной 1, для каждой реализации алгоритма найдется такое конечное число m, что

(26)

Т.е. процесс разделения множеств с вероятностью P=1 осуществляется за конечное число шагов.