Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 193
Скачиваний: 4
5 10. УПОРЯДОЧЕНИИ ПО ЭМПИРИЧЕСКИМ ОЦЕНКАМ |
145 |
Пусть теперь дано к точек хъ . . . , x k и Ти . . . , Т |
— |
всевозможные разбиения этих точек на два класса; р (ГЛ)— расстояние между выпуклыми оболочками классов при разбиении Th.
Тот факт, что условие I выполняется для всякого Tit можно записать так:
min р (Ті) > 2р/.
І
Тогда число d не превосходит максимальное число к (к ^
п + 1 ), |
при котором еще |
выполняется |
неравенство: |
||||||
I (к) = |
шах |
min р (71*) |
2р = |
D |
(6.12) |
||||
Ѵ Г |
|||||||||
|
|
Х и ...,Х^ |
І |
|
|
|
|
||
|
|
|
\X i\< D ß . |
|
|
||||
Из соображения симметрии ясно, что |
|
|
|||||||
|
|
I (к) = |
max |
m inp^i), |
|
||||
|
|
|
Xj,..., Xfc |
і |
|
|
|||
|
|
|
I |
Х}\ |
< D / 2 |
|
|
||
достигается, когда xt, . . . , |
хк располагаются в вершинах |
||||||||
правильного (к—1)-мерного |
симплекса, вписанного в шар |
||||||||
радиуса DI2, |
а Т — разбиение на два подсимплекса раз- |
||||||||
мерности |
к---- 1 для четных к и два подсимплекса размер- |
||||||||
fe_ I |
Д._ß |
|
|
|
|
|
|
||
ности —Г)— и |
для нечетных к. При этом путем эле- |
||||||||
dt |
|
dt |
|
|
|
|
|
|
|
ментарных расчетов может быть найдено, что |
|||||||||
|
В |
|
|
|
для четных к, |
|
|||
/(*) = |
/ к — 1 |
|
|
|
|
(6.13) |
|||
|
|
|
|
|
|
||||
|
в —------- -— |
|
для нечетных |
kß> 1. |
|||||
|
|
к — і |
У к + І |
|
|
|
|
||
Начиная с к |
2, для всех к справедливо |
|
|||||||
|
|
/ |
(к) < D |
1 |
|
(6.14) |
|||
|
|
Ѵк=Ъ ' |
|
||||||
146 Гл. VI. МЕТОДЫ УПОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА
Из (6.12) и (6.14) следует, что г не превосходит величины
<3 < |
£ + |
2. |
|
(6.15) |
Окончательно, учитывая, |
что |
разбиение осуществляется |
||
гиперплоскостью, имеем |
|
|
|
|
d-< min |
г + |
2, п + |
1 |
(6.16) |
и соответственно |
|
|
|
|
TV< |
1,5 |
I L |
|
|
|
|
d\ • |
|
|
Оценка величины TV завершает |
доказательство |
обеих |
||
теорем. |
|
|
|
|
Эти теоремы дают возможность вычислить доверитель ные интервалы оценок качества правила класса S t при решении задачи обучения распознаванию образов в общей детерминистской постановке.
Приравнивая правые части (6.10) и (6.11) к величине
т] и разрешая соответствующие |
уравнения |
относительно |
|
е, найдем |
d (ln 21 — ln d -|- 1) — ln T)/5 |
|
|
|
(6.17) |
||
|
|
I |
|
|
|
|
|
для общего случая и |
|
|
|
0 |
d (ln 21 — ln d + |
1) — ln T)/2 |
(6.18) |
ß -- Li |
... .... _ |
- - ............ |
|
для детерминистского случая. В формулах (6.17) и (6.18) d равно минимальному значению двух величин: п + 1 и
[ І И + 2= 1+ 2-
Таким образом, с вероятностью 1 — т] для всех ре шающих правил F (X, а) класса S t справедливы соотно шения
Р (а) < Раыа(а) + 2 У d (1п 2/-" I * * + * > -ln |
(6.19) |
при решении задачи в общей постановке и
Р (а) < 2 d*1п 21~ 1аd + ^ ~ ln |
(6.20) |
в детерминистской постановке.
§ 11. |
О Б ОПТИМАЛЬНОЙ СОВОКУПНОСТИ ПРИЗНАКОВ |
147 |
||||
Существование |
оценок |
(6.19) и |
(6.20) позволяет |
|||
построить у |
упорядоченную |
процедуру 4 минимизации |
||||
риска. |
|
|
|
|
|
|
Для детерминистской постановки задача состоит в том, |
||||||
чтобы |
так |
отнести |
элементы рабочей |
выборки |
к пер |
|
вому и второму классам, чтобы, во-первых, разделение множества векторов первого и второго классов, со стоящих из элементов обучающей и рабочей последова тельностей, было возможно, а во-вторых, расстояние ме жду выпуклыми оболочками объединенных множеств бы ло бы максимальным (по сравнению с другими варианта ми разделения рабочей выборки на два класса). При этом качество полученного решающего правила оценивается
спомощью функционала (6.20).
Вобщем случае проводится индексация не только ра бочей выборки, но и переиндексация элементов обучаю щей последовательности. При этом количество переиндексированных векторов задает число ошибочных классифи каций материала обучения. Задача состоит в том, чтобы так индексировать рабочую выборку и переиндексировать обучающую последовательность, чтобы минимизировать функционал (6.19).
§ 11. О выборе оптимальной совокупности признаков
Соображения предыдущего параграфа указывают на то, что при построении конечно-оптимальных решающих правил следует учитывать не только число ошибок на обучающей последовательности и размерность выбирае мого подпространства, но и относительное расстояние ме жду проекциями классов на подпространство.
Для того чтобы учесть все эти особенности, рассмот рим двухступенчатую схему упорядочения класса решаю щих правил. Пусть сначала задана ранжировка системы признаков. Как и ранее, разобъем класс S линейных ре шающих правил на вложенные подклассы S t так, что в подкласс S t попадают правила, использующие только первые і признаков, т. е. работающие в подпростран стве E t.
Рассмотрим сначала задачу в детерминистской поста новке. Пусть дана обучающая выборка хѵ . . . , Х{. Алго ритмы первого уровня, используя упорядоченный поиск,
148 ГЛ. VI. МЕТОДЫ УПОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА
выберут каждый в своем классе Si из числа безошибочных решающих правил правило F (х, а) (если оно есть) с мак симальным р. Процедура второго уровня должна выбрать наилучшее из предложенных первым уровнем решающих правил.
Теперь естественно принять в качестве критерия выбо ра величину доверительного интервала
d (Е.) (In 21 — la d (ЕЛ + 1) — ln rj/2 |
(6.20') |
|||
8 = 2 — - |
1 |
‘ |
------- — , |
|
где |
/ D(E.) |
|
\ |
|
d (Ei) = |
+ |
|
||
min ( 4p ^ |
2, i -f- 1 j . |
|
||
Здесь как величина D (Ei) , так и р (Е{) зависят от под пространства E t, поскольку и расстояние между выпук лыми оболочками классов и их диаметры изменяются при проектировании в подпространство. Процедура вто рого уровня должна выбрать то решающее правило из числа предложенных первым уровнем, для которого оцен ка (6.20') минимальна.
Оценка доверительного интервала (6.20') меняется, вообще говоря, не монотонно с ростом размерности под пространства. Поэтому выбранное процедурой второго уровня подпространство может содержать больше при знаков, чем минимально необходимо для разделения классов.
Описанная процедура эквивалентна упорядоченному поиску при одноступенчатом упорядочении, определенном следующим образом.
К первому классу относятся либо все те решающие правила, которые либо производят разделение в подпро странстве, заданном первым признаком, либо такие, ко торые характеризуются числом
/Г Л*(Я,) |
+ 2, |
і - f - 1 |
< 2. |
|
[ *Р2(Щ |
||||
|
|
|
Ко второму классу относятся разделяющие гиперплоско сти, которые либо производят разделение в подпрост ранстве, заданном первыми двумя признаками, либо
