Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf

3G2 ГЛ. XV. АЛГОРИТМЫ МЕТОДА ОБОБЩ ЕННОГО ПОРТРЕТА

классу, вектор х относится ко второму классу, если вектор X принадлежал ко второму классу.

Разделим теперь множество векторов {х} на два клас­ са с помощью гиперплоскости

(х, ф) = с.

В пространстве размерности т этому разделению соответ­ ствует разделение векторов {ж} с помощью гиперповерх­ ности, составленной из кусков гиперплоскостей с направ­ ляющими векторами и ф2 (вектор тр3 коллинеарен ш-мерному вектору, образованному первыми т координа­

тами вектора тф).

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

Классификация векторов с помощью построенной раз­ деляющей поверхности, образованной кусками гиперплос­ костей, происходит по следующему правилу.

Сначала по вектору х и первой разделяющей гипер­ плоскости вычисляется вектор %. Затем в новом простран­

(х, ф) < с.

Алгоритм ОП-3 включает в себя как составную часть ОП-2.

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

впространстве минимального числа признаков

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

Так же как и две предыдущие задачи, эта задача в прин­ ципе может быть точно решена, однако точное ее решение

5. АЛГОРИТМЫ , МИНИМИЗИРУЮЩИЕ ЧИСЛО ПРИЗНАКОВ 363

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

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

Таким образом, поиск минимального подпространства определяется введенным понятием «наименее информатив­ ный признак». Определим его следующим образом. Пусть

ми оболочками будет р (Е п).

Рассмотрим теперь пространство Еп~\{к), образованное п — 1 признаком (исключен признак к). В этом простран­ стве могут быть построены выпуклые оболочки множеств

{х} и {%} (векторы X и х суть проекции векторов х и я на подпространство Еп-\ (к)) и вычислено расстояние между выпуклыми оболочками. Пусть оно равно р (Е^-^к)). Если расстояние между оболочками больше р0, то будем считать, что в этом пространстве возможно построение разделяю­ щей гиперплоскости, в противном случае будем пола­

— р (Еп^к)). Эта величина показывает, насколько умень­ шится расстояние между выпуклыми оболочками векто­ ров в пространстве Еп-.х(к) (с исключением к-то признака). Будем считать тот признак наименее информативным,

364 ГЛ. XV. АЛГОРИТМЫ МЕТОДА ОБОБЩ ЕННОГО ПОРТРЕТА

с удалением которого расстояние между выпуклыми обо­ лочками уменьшается на минимальную величину.

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

Расстояние между выпуклыми оболочками определяет­ ся по формуле

— _2_

р- к г

где ф — обобщенный портрет, соответствующий оптималь­ ному к0. Однако, даже несмотря на то, что для поиска «наименее информативного признака» происходит п раз вычислять расстояние между выпуклыми оболочками, такой способ исключения признака не является чрезмер­ но трудоемким.

Удобно проводить поиск наименее информативного из признаков по следующей схеме.

Сначала в пространстве Е п (п признаков) строится оп­ тимальная разделяющая гиперплоскость и определяется расстояние между выпуклыми оболочками двух множеств (это делается с помощью соответствующей модификации программы ОП-1). Пусть ф — найденный обобщенный портрет, ах, . . ., <ха; ßlt . . ., ßb — соответствующие ко­ эффициенты разложения вектора ф по информативным векторам обучающей последовательности.

Спроектируем вектор ф и векторы обучающей последо­ вательности на подпространство Еп^р ). Для этого доста­ точно в те разряды ячеек, где записаны значения р-й координаты вектора ф и векторов х, (ж), заслать нули.

Затем построим оптимальную разделяющую гипер­ плоскость в подпространстве Еп_х(р) (также с помощью ОП-1). Однако за начальные условия следует брать не

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

Программа ОП-4 использует как составную часть про­ грамму ОП-1.

Алгоритм ОП-5 используется для поиска минималь­ ной размерности, в котором разделяющая гиперплос­ кость делит обучающую последовательность, совершая не более t ошибок (t — параметр алгоритма). Структура алгоритма ОП-5 аналогична структуре алгоритма ОП-4. Разница заключается лишь в том, что алгоритм ОП-4 пре­ кращает поиск соответствующего подпространства, когда выясняется, что построение разделяющей гиперплоскости становится невозможным, в то время как алгоритм ОП-5 исключает t векторов, «препятствующих» построению разделяющей гиперплоскости, и только после этого пре­ кращает поиск минимального подпространства.

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

Алгоритм ОЛ-6 реализует идею упорядоченной мини­ мизации риска при построении гиперплоскости, разделяю­ щей два множества векторов {х} и {х} (см. главу VI). С помощью этого алгоритма строится гиперплоскость, раз­ деляющая два множества векторов в подпространстве Е т исходного пространства Е п, в котором достигается минимум величины

где т — размерность подпространства Е т, D — диаметр векторов в Е т, р — расстояние между выпуклыми обо­ лочками векторов в Е т, h — число векторов, участвовав­ ших в разложении вектора с ненулевым весом.

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

366 гл . XV. АЛГОРИТМЫ МЕТОДА ОБОБЩ ЕННОГО ПОРТРЕТА

Пусть в начальный момент ситуация описывается и-мерным бинарным вектором, который образован раз­ бивкой т параметров на градации (і-й параметр имеет qt градаций). На каждом шаге алгоритм ищет такой спо­ соб «объединения» соседних градаций одного параметра, чтобы максимально увеличить величину критерия d. Для этого в векторах обучающей последовательности вместо координат тг и тг+1 (обе координаты соответствуют различным градациям одного параметра) определяется новая координата т* по правилу

т* = тгV тг+і>

т. е. координата т* принимает значение единица, если одна из координат тгили тг+1 равна единице, нуль, если одновременно тг и тг+1 равны нулю. Если в результате многократного объединения градаций параметр кодиру­ ется только одной градацией, то он исключается из рас­ смотрения (кодировка параметра одной градацией в слу­ чае, если исходная кодировка проводилась рассмотренным в § 1 способом, означает, что всегда значение этой единст­ венной градации будет равна единице). Для каждого па­ раметра возможны qt — 1 способов объединения.

Таким образом, для установления одного оптималь-

т

ного «объединения» проводится 2 (?г — 1) построений оп-

г—1

тимальных разделяющих гиперплоскостей (построение оптимального обобщенного портрета необходимо для по­ строения критерия d).

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

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

векторы, соответствующие векторам xl t . . ха\%іі • • •» ®ь>