§ 6. Алгоритмы построения разделяющей гиперплоскости

В этом параграфе мы рассмотрим два алгоритма построения разделяющей гиперплоскости — алгоритм 11-1 и алгоритм 11-2.

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

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

Модификация 1. При этой модификации алгоритм строит для заданного обобщенный портрет.

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

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

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

Обобщенный портрет строится путем максимизации соответствующей квадратичной формы в положительном квадранте методом сопряженных градиентов (см. § 3).

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

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

где параметр алгоритма

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

Если окажется, что во всех группах нет векторов, удовлетворяющих (11.30), то есть обобщенный портрет всей обучающей последовательности.

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

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

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

Модификация 2. При этой модификации алгоритм строит оптимальную разделяющую гиперплоскость. Оптимальная разделяющая гиперплоскость также строится итерациями.

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

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

Если при этом окажется, что выполнены неравенства

где в правых частях неравенства минимум и максимум вычисляются только по векторам обучающей последовательности, входящим в рабочую группу, 8 62 параметры алгоритма (обычно

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

Так продолжается до тех пор, пока либо однажды не выполнятся оба неравенства, либо окажется, что разделение невозможно заданная величина).

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

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

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

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

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

Специфика алгоритма заключается в определении элемента, «наиболее препятствующего разделению». В качестве

такого элемента при построении обобщенного портрета определяется вектор который в момент «останова» доставлял наибольший вклад в величину

т. е. вектор для которого достигается максимум величины

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

В конце концов, исключив векторов, программа 11-2 разделит оставшееся множество векторов, построив разделяющую гиперплоскость Согласно же оценке (11.2) вероятность правильной классификации с помощью построенной гиперплоскости оценится величиной