§ 2. Алгоритм, решающий задачу

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

где - потенциальная функция, которая выбирается в соответствии с рекомендациями, сформулированными в главе III.

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

Выбор числовой последовательности определим следующим правилом: на шаге алгоритма

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

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

Сравнивая выражение (5) с общей формулой (10) главы II, замечаем, что в рассматриваемом случае «помеха» а функция

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

При появлении первой точки строится функция первое приближение искомой разделяющей функции следующим образом:

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

В случаях а) и б) знак множества, которому принадлежит точка и знак совпадают, т. е. «ошибки нет». В этих случаях принимается

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

в случае г)

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

Построенное после шагов приближение можно записать следующим образом:

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

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

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

В спрямляющем пространстве каждой точке соответствует бесконечномерный вектор с компонентами Множествам пространства X соответствуют два непересекающихся множества в спрямляющем пространстве; им приписываются те же наименования.

Если в пространстве X существует разделяющая функция, представимая разложением

такая, что

то в спрямляющем пространстве существует проходящая через начало координат разделяющая плоскость с направляющим вектором с

где такая, что

Отобразим множество В симметрично относительно начала координат, т. е. заменим все векторы на Полученное таким образом отображенное множество назовем В и рассмотрим объединенное множество В (рис. 12, жирная линия).

Рис. 12

Условия разделимости множества плоскостью с направляющим вектором с запишутся теперь в виде

при

т. е. множества разделяются этой плоскостью, если объединенная область лежит по одну сторону от нее, и наоборот.

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

Функция определенная в соответствии с (7), может быть интерпретирована в спрямляющем пространстве как скалярное произведение двух векторов с координатами соответственно:

Тогда, учитывая (9) и определение М, формулу для приближения в спрямляющем пространстве можно переписать так:

где 2 означает суммирование по тем точкам из последовательности М, показ которых в процессе обучения привел к «исправлению ошибки».

Удалим теперь из последовательности точек М все точки, которые не приводили к «исправлению ошибки», а оставшиеся точки, требовавшие «исправления ошибки», перенумеруем подряд, обозначая их вновь через Они образуют последовательность М. Тогда выражение (10) можно записать так:

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

где компонента вектора

Условие, при котором должно быть произведено «исправление ошибки» в точке имеет вид

Поэтому из равенства (11) следует, что «исправление ошибки» произойдет, если

Теперь можно описать алгоритм на «геометрическом языке». При появлении первой точки из последовательности М применение алгоритма означает построение

в спрямляющем пространстве плоскости

с направляющим вектором (рис. 13).

Если следующая точка из М лежит в том полупространстве, куда направлен направляющий вектор построенной плоскости, то «ошибки нет»; положение плоскости и ее направляющий вектор в этом случае не изменяются, и производится следующий показ.

Рис. 13.

Рис. 14.

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

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

точка окажется в полупространстве, противоположном направляющему вектору.

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

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

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

где определяется по формуле (5),

Эта процедура рекуррентно определяет коэффициенты приближения разделяющей плоскости.

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

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