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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 180

Скачиваний: 4

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
1 г (0 + 1lg2 X L + ft

$ 1. СПОСОБЫ ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ

347

принадлежности к тому или иному классу. Она равна

к

н ($) = — 2 р (* Iх) ^ 2 р (ІI х).

і= 1

Среднее значение по мере Р (х) энтропии вычисляется

так:

/С

II = ^ Н (х) Р (X) dx —2 \ р (г Iх) ^ 2 Р (£ I х) Р(х) dx.

1=1

Пусть теперь параметр х разбит на т градаций. Тогда средняя энтропия может быть записана в виде

/С X

 

 

 

Я (т) = — 2 2 P(i \хі) Р (i I

P (Xj).

(15.1)

i=l ;=l

 

 

 

Воспользуемся теперь формулой Байеса

 

р (* I =

10^(0

 

(15.2)

*(*і)

'

 

 

Подставляя (15.2) в (15.1), получим

Vi Vi

ГР to

I 0 Р (01

( т ) = - 2 2 Р ^ \ і ) Р { і ) ^ г

L

' J' J

1= 13=1

Подставляя теперь байесовы оценки Р (х} | і), Р (і), Р (х}), найденные по обучающей последовательности (см. главу III), получим

Н ( т) = -

’Ѵ

"V

т і ^

^

^ ПО + Т

 

і=1 j=l

w

/»,•(0 + 1

но + *

ПО +1

‘ к

L-\-x

 

1

(15.3)

L + ft

,.ч

. , I *

^

іs

/МО-И

J

 

 

=і

'

 

 

где 1(і) — число векторов і-го

класса в обучающей вы­

борке,

тj (і) — число векторов

і-го класса, у которых

 

к

 

X — Х}\

L — 2 /(І) — длина выборки.

і=і Формула (15.3) получена в предположении, что априор­

ные значения Р (xj ( і), Р (і) равновероятно распределены

348 Гл. XV. АЛГОРИТМЫ МЕТОДА ОБОБЩЕННОГО nO PTPEtA

на симплексах:

X

2 р ( ^ |і) = 1, Р {Х} IІ) > 0;

7=1

(15.4)

к

 

2 ^ ( 0 = i,

Р (і) > 0.

г—1

 

В более общем случае целесообразно рассмотреть фор­ мулу

Н( т) = -

■у

 

mj (0 + а 1(і) -f а

 

 

г=1

•

Ці )-\ -йг

X + ак lga X

 

 

 

 

ѵ7 1

'

 

 

 

 

 

mj (0 + а ^ г (0 + д ш

L + ат

(15.5)

 

 

 

I (t) 4 - a t

Z, -4- а 4 к

 

 

 

 

Wj(0 + a

 

 

 

 

 

2

 

 

 

 

 

г=1

 

 

где параметр а определяется характером априорной ин­ формации.

Реализация сформулированного принципа состоит в та­ ком подборе разбивки на градации, чтобы обеспечить ми­ нимум (15.5).

Алгоритм удобно реализовать в следующей форме: сначала разбить параметр на большое число градаций, а затем, «склеивая» соседние градации, добиваться мини­ мизации значения Я (т).

Можно оценить и количество информации J (у) о при­ надлежности объекта к тому или иному классу, которое несет сведение о значении параметра

J (т) =

Я апр — Я (Т),

где

к

 

 

I(0 ~4~а

я апр —

I (г) -)- а

L -(- ка lg2

£j “I- ко.

І=1

Часто разумно продолжать «склеивать» градации и пос­ ле достижения минимума по т функции Я (т), но лишь до тех пор, пока величина J (т) не уменьшится в 1 — е раз (е, так же как и а, — параметры алгоритма).

§ 2. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩЕЙ ГИПЕРПЛОСКОСТИ 349

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

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

Данный алгоритм имеет две модификации. В одной из них он позволяет найти обобщенный портрет при задан­

ном параметре к\ во второй мо­

 

дификации алгоритм

находит

 

оптимальную разделяющую ги­

 

перплоскость (см. главу XIV).

 

Алгоритм

строит плоскость, ре­

 

шая двойственную задачу, как

 

это было описано в предыдущей

 

главе. Однако часто длина обу­

 

чающей последовательности на­

 

столько велика, что обработка

 

сразу всего материала обучения

 

привела бы к задаче

слишком

 

высокой размерности.

Поэтому

 

обработка

обучающей последо­

 

вательности ведется итеративно.

 

На каждой итерации из обуча­

 

ющей последовательности выде­

Рис. 25. Блок-схема

ляется группа векторов, кото­

алгоритма ОП-1.

рую будем называть выделенной

 

группой,

строитсяj разделяю­

 

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

Затем из группы исключаются векторы,

которые входят

в разложение направляющего вектора

гиперплоскости

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

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

разделимость выделенной группы.

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

Б л о к ОГІ-1/1

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

Б л о к ОП-1/2

Этот блок ведает формированием выделенной группы векторов.

1. На первой итерации выделенная группа образуется из векторов первой группы, которая возникнет после раз­

биения материала

обучения блоком

ОП-1/1.

2. На очередной,

і-й, итерации, т.

е. при очередном об­

ращении к^блоку ОП-1/2, блок просматривает векторы первых і групп, если число і не превосходит число групп р, или весь материал обучения в противном случае. При этом к выделенной группе добавляются те векторы, кото­ рые неправильно опознаются с помощью решающего пра­ вила, построенного на предыдущей (і — 1)-й итерации, или опознаются правильно, но с недостаточным превы­ шением порога.

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

а) в случае построения обобщенного портрета вектор

заносится

в выделенную

группу,

если

 

или

(ж, ф)

1 — б и і б і ,

 

(гл Ф) > &+ S и s e x ,

 

 

 

где ф — обобщенный

портрет,

построенный

на пре­

дыдущей

итерации,

б

и к — заданные

параметры,

причем

 

 

 

 

 

1 — к

2

Смотрите также файлы