4.4.3. Обобщение на случай k классов

В задаче с несколькими классами множество Y (и X) разбивается на подмножеств Множество будет называться линейно отделимым матрицей весовых векторов тогда и только тогда, когда

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

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

(1) Пусть — начальная матрица. Как и раньше, W будет нулевой матрицей, хотя это и не обязательно.

(2) Как и раньше, определим последовательность Рассмотрим любой вектор и пусть — класс, которому он принадлежит. Наблюдение будет классифицироваться матрицей Матрица вычисляется по следующим правилам.

(2а) Если классификация верна, то

(26) Если классификация ошибочна, то найдется по крайней мере одно число , для которого

Для каждого и каждого такого положим

Как и раньше, можно было бы в (95) и (96) заменить на но для простоты записи мы этого делать не будем.

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

Пусть будет множеством -мерных векторов, построенных из так, чтобы вектор линейно содержащий содержал элементы матрицы в определенном порядке. Чтобы получить такое множество, используется каждый вектор для определения векторов в Возьмем Векторы построенные из у, обозначим Каждый вектор состоит из блоков, каждый из которых имеет компонент, причем

а) -й блок вектора совпадает с компонентами вектора у,

б) -й блок вектора совпадает с компонентами вектора —у,

в) все остальные компоненты вектора равны нулю.

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

По предположению матрица существует. Мы будем искать вектор составленный из векторов (строк матрицы ). Алгебраически

для Тогда для каждого вектора

поскольку если линейно отделяется матрицей то

Теперь обратим этот процесс, и пусть известно, что линейно содержит

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

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