5.12. ОБОБЩЕНИЯ ДЛЯ СЛУЧАЯ МНОГИХ КЛАССОВ

5.12.1. МЕТОД КЕСЛЕРА

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

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

где х снова ставится в соответствие если для

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

Одним из преимуществ такого определения является то, что, несколько видоизменив неравенства (89), можно свести задачу для многих классов к случаю двух классов. Предположим на минуту,

что так что выражение (89) принимает вид

Это множество (с — 1) неравенств можно интерпретировать как требование существования обмерного весового вектора

который бы правильно классифицировал все -мерных выборок

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

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

5.12.2. ПРАВИЛО ПОСТОЯННЫХ ПРИРАЩЕНИЙ

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

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

Тогда правило постоянных приращений для коррекции примет вид

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

Для каждой выборки существуют выборок (правило их формирования описано в предыдущем пункте). В частности, для вектора у, удовлетворяющего неравенствам (91), существует вектор

удовлетворяющий условию

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

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

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

5.12.3. ОБОБЩЕНИЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ

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

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

Отсюда немедленно вытекают два следствия. Первое: если несколько изменить постановку задачи, то она будет звучать так: найти весовой вектор который является решением в смысле минимума квадрата ошибки уравнений

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

причем выборки, помеченные символом юг, включают в себя строки Далее обозначим через А матрицу размера весовых векторов

и через В матрицу размера

где все элементы В; являются нулевыми, за исключением элементов столбца, равных 1. Тогда след квадратичной матрицы ошибок будет минимален при решении

где, как обычно, есть псевдообращение матрицы

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

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

Доказательство этого результата можно получить, если распространить на рассматриваемый случай метод, использованный в п. 5. 8. 3. Следуя сложившейся традиции, предоставим сделать это читателю в качестве самостоятельного упражнения.