4.4.2. Процедура обучения для двух классов

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

Алгоритм коррекции по ошибкам для двух классов

(1) Пусть — приближение, используемое для классификации

(3) При заданном нужно поступать согласно следующим правилам.

Случай 1:

Случай 2:

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

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

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

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

Преобразованный алгоритм для двух классов

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

В исходном алгоритме это соответствует случаям ошибочной классификации.

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

По предположению существует весовой вектор линейно содержащий Поэтому найдется такое положительное число а, что

Пусть будет этим весовым вектором, построенным после ошибки. Согласно алгоритму,

откуда

С помощью соотношения (80) можно установить нижнюю границу величины Применим неравенство Шварца (произведение квадратов двух векторов не меньше квадрата их скалярного произведения):

или

Объединяя (80) и (82), получаем

где — неизвестная постоянная, значение которой зависит от Нам не обязательно знать значение мы хотели лишь показать, что нижняя граница для пропорциональна

Теперь покажем, что верхняя граница для пропорциональна Согласно алгоритму,

Возведем обе части равенства (84) в квадрат:

Так как использование вектора привело к ошибке то и потому

Суммируя (86) для находим

Поскольку а все средние члены взаимно уничтожаются, остается

или, что эквивалентно,

Поскольку множество конечно, оно должно обладать наибольшим вектором. Так как длина этого вектора не меньше длины наибольшего вектора в

Объединяя (89) и (90), получаем

а с учетом (83) имеем

Это справедливо только тогда, когда

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

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