Глава XIV. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩЕЙ ГИПЕРПЛОСКОСТИ (МЕТОД ОБОБЩЕННОГО ПОРТРЕТА)

§ 1. Оптимальная разделяющая гиперплоскость

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

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

.

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

.

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

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

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

,                 (14.1)

а для любого вектора  – неравенство

.                (14.2)

В случае, когда выполняются (14.1) и (14.2), говорят также, что множество  отделимо от множества  гиперплоскостью

.

Определим для любого единичного вектора  две величины  и :

,

.

Согласно определению величин  и  всегда справедливы неравенства

 ,

 .

Ясно, что если

,                      (14.2')

то пара  – определяет гиперплоскость

,

отделяющую множество  от множества .

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

Будем выделять из множества разделяющих гиперплоскостей оптимальную.

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

,

и числом

.

Справедлива теорема

Теорема 14.1. Если два множества векторов разделимы гиперплоскостью, то существует единственная оптимальная разделяющая гиперплоскость.

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

Существование максимума следует из того, что функция  непрерывна, а множество  ограничено и замкнуто.

Допустим, что максимум достигается не на границе, а в некоторой точке , для которой . Тогда значение функции в точке  равно

,

откуда следует противоречие:

.

Остается показать единственность. Пусть максимум  достигается в двух граничных точках:  и . Тогда в силу выпуклости функции –  максимум должен достигаться и на всем отрезке, соединяющем  и , т. е. на внутренних точках множества , что по доказанному невозможно. Теорема доказана.

Геометрически величина  равна расстоянию между проекциями множеств  и  на направление  (рис. 23).

Рис. 23.

Вектор  задает такое направление, для которого эта величина максимальна. Сама же оптимальная разделяющая гиперплоскость

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

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