5.3.3. Алгоритм, основанный на минимизации среднеквадратичной ошибки

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

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

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

где все компоненты вектора положительны. Очевидно, что обе эти формулировки эквивалентны.

Рассмотрим функцию критерия

где обозначает модуль вектора Функция достигает своего минимального значения при выполнении условия (5.3.13). Поскольку эта функция зависит от

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

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

и

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

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

где

В формулах (5.3.18) и (5.3.19) обозначает индекс итерационной процедуры, — индекс компонент вектора и с — положительное корректирующее приращение, которое будет определено ниже.

Уравнение (5.3.19) можно представить в векторной форме:

где выражение определяет абсолютную величину каждой компоненты вектора . Из (5.3.17) и (5.3.18) следует, что

Положив

приходим к следующему алгоритму:

в остальных случаях произвольно,

В соотношениях (5.3.23) через обозначен вектор, компонентами которого являются абсолютные значения компонент вектора Отметим, что значение вектора также можно определить, используя соотношение

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

Пример, (а) Рассмотрим снова класс ем, содержащий образы и класс содержащий образы . Путем пополнения образов и умножения всех образов, входящих в класс на —1 получим матрицу

Обобщенная обратная матрица равна

Положив и применив алгоритм (5.3.23), получим

Так как

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

(б) Рассмотрим теперь классы эти классы не обладают линейной разделимостью. Положив , получим

То, что вектор отрицательный, означает отсутствие решения у неравенства

Скорость сходимости, отличающая НСКО-алгоритм, объясняется тем, что 1) изменение обоих векторов и производится на каждом шаге и 2) процедура является адаптивной схемой, учитывающей на каждом шаге итерации информацию о всех образах обоих классов.

Единственный явный недостаток применения НСКО-алгоритма связан с обращением матрицы Если, однако, размерность образов не очень велика, этот недостаток не вызывает особых проблем, так как при решении каждой задачи матрицу приходится обращать только один раз. К тому же обратную матрицу можно рекуррентно модифицировать при появлении новых строк (т. е. образов) в матрице X (Бодевиг [1956]).

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

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

Два основных алгоритма, построенных в данной главе, покрывают весь спектр алгоритмов, получаемых с помощью градиентного метода. Интерес они, однако, вызывают по разным причинам. Алгоритм перцептрона привлекает сравнительной простотой реализации и, как будет показано в § 5.4, возможностью непосредственного обобщения на случай разбиения на несколько классов. НСКО-алгоритм, с другой стороны, обладает критерием разделимости для случая двух классов. Естественно, за это качество алгоритма приходится платить его усложнением.

Хотя скорость сходимости и является важной характеристикой, но на ее основе трудно сформировать показатель качества

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