Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 179
Скачиваний: 4
§ 4. |
ЧАСТНЫЙ СЛУЧАЙ |
95 |
В теореме важно, |
что достаточная длина |
обучающей |
последовательности лишь логарифмически зависит от числа событий в классе N.
Число решающих правил является весьма гру бой характеристикой разнообразия класса решающих правил (такая характеристика, например, никак не учи тывает, состоит ли класс из одних и тех же или «близких» элементов или же он состоит из существенно «различных» функций). Однако качественные выводы, которые можно
сделать |
из этой |
оценки, |
довольно |
хорошо отра |
||
жают существо |
дела — чем меньше |
емкость класса, тем |
||||
меньшей может |
быть длина |
обучающей |
последователь |
|||
ности. |
Наоборот, |
чем универсальнее обучающееся ус |
||||
тройство, тем большая информация |
необходима ему для |
|||||
обучения. |
|
|
|
|
|
|
Используя формулу (5.6), можно получать достаточные оценки длин обучающих последовательностей для различ ных алгоритмов, реализующих метод минимизации эм пирического риска. Так может быть получена оценка длины обучающей последовательности для персептрона с памятью (метод обучения с циклическим повторением обучающей последовательности). Для этого достаточно оценить число N различных решающих правил персеп трона. Для бинарного спрямляющего пространства число
различных векторов не превосходит 2т . Существует 22"*
способов разделения 2т векторов |
на |
два класса. |
Однако персептрон делит множество |
векторов не всеми |
|
способами, а только с помощью линейных |
дискриминант |
|
ных функций. |
|
|
Число различных способов разделений с помощью линейных дискриминантных функций N значительно мень
ше чем 22"1- |
|
2т2, и тогда, соглас |
Ниже будет показано, что N < |
||
но теореме, оценка достаточной |
длины обучающей по |
|
следовательности будет |
равна |
|
j |
т2 — In г) |
’ |
1 ~ |
2р |
|
т. е. обучающая последовательность пропорциональна тг (сразу же заметим, что эта оценка завышена; ниже будет показано, что справедлива оценка I ~ т).
96 |
ГЛ. V. МИНИМИЗАЦИЯ ЭМПИРИЧЕСКОГО РИСКА |
§ 5. Оценка числа различных линейных разделений векторов
Итак, оценим количество способов, которыми с по мощью гиперплоскостиіможно^разделить на два класса I векторов % , . . . , ж, в пространстве размерности т.
Заметим, что |
в соответствие каждому вектору |
X — (ж1, . . ., ж” ) |
пространства X может быть поставлена |
гиперплоскость |
m |
|
|
|
|
2 |
М 1= о, |
|
|
|
|
і=і |
|
|
проходящая |
через |
нуль |
в |
пространстве Л векторов |
|
X = (А-л, |
. . ., Хт) и |
наоборот, |
каждому вектору X в прос |
||
транстве |
X |
может быть поставлена в соответствие гипер |
|||
плоскость, |
проходящая |
через начало координат, |
|||
ТП
2 М = о.
і=і
Таким образом, I векторам х1, . . ., хі в пространстве Л ставится в соответствие I гиперплоскостей (рис. 11). Наше утверждение состоит в том, что число различ ных разделений векторов равно числу компонент, на которые эти I гиперплоскостей разбивают m-мерное про странство Л.
§ 5. ОЦЕНКА ЧИСЛА ЛИНЕЙНЫХ РАЗДЕЛЕНИЙ |
97 |
В самом деле, поставим в соответствие каждой гипер плоскости в пространстве X вектор К пространства А, равный направляющему вектору гиперплоскости. При этом непрерывному вращению разделяющей гиперплос кости в X, не изменяющему разделение точек хг, . . х,, соответствует в А непрерывная траектория движения точки X внутри одной из компонент пространства.
Оценим теперь, на какое число компонент могут раз- . бить то-мерное пространство I гиперплоскостей, проходя- ' щих через начало координат. Обозначим через Ф (т, I)
максимальное число компонент, на которое I гипер плоскостей делят пространство размерности т, и определим рекуррентную процедуру поиска числа ком понент.
Очевидно, что в одномерном случае справедливо
Ф (1, I) = 2.
Одна гиперплоскость делит пространство размерно сти т на две части, т. е. справедливо
Ф (т, 1) = 2.
Пусть известно, что I — 1 гиперплоскость Tlt . . ., Гг_г делит нг-мерное пространство не более чем на Ф (т, I — 1) компонент. Добавим новую гиперплоскость Гг. Если эта гиперплоскость проходит через одну из «старых» компо нент, то она дробит ее надвое. В противном случае старая компонента сохраняется. Таким образом, при проведении
гиперплоскости Гг число компонент |
увеличится на столь |
|||
ко, сколько |
компонент окажется |
разделено |
надвое. |
|
В свою очередь |
каждая такая компонента К і |
оставляет |
||
на Г*следА{ |
f) |
Гг. Число таких следов в точности равно |
||
числу компонент, на которое гиперплоскости Гь . . ., Г;_! дробят новую гиперплоскость Г;. Поскольку размерность Г; равна т — 1, число следов не превосходит Ф (т — 1,
I - 1).
Таким образом, мы получим следующее рекуррентное
уравнение: |
|
|
Ф (т, I) — Ф (т, I — 1) + |
Ф {т — 1,1 — 1), |
|
Ф (т, 1) = |
2, |
(5.7) |
Ф (1, I) = |
2. |
|
4 В. Н. В апник, А. Я. Ч ервоненкис
9? ГЛ. V. МИНИМИЗАЦИЯ ЭМПИРИЧЕСКОГО РИСКА
Решением уравнения (5.7) является выражение
m—1 |
|
|
2 2 С?—1» |
если |
т ^.1, |
Ф (т, I) — І=0 |
если |
т^>1. |
2г, |
Нам, однако, удобнее будет пользоваться не этой формулой, а ее оценкой сверху (см. главу X)
,771-1
ф К г) < 3 (7^гТ )Г’
или даже более грубой оценкой
Ф (т, I) < Г .
Число различных бинарных векторов не превосходит 2т и, следовательно, справедлива еще более грубая оцен ка числа различных разделяющих гиперплоскостей:
N < Ф (т, 2т) < 2т\
Эта-то оценка используется для получения оценки длины обучающей последовательности.
Подставляя оценку N в (5.6), получаем
7 _ |
тг — In г) |
|
1 — |
2р |
’ |
т. е. длина обучающей последовательности должна быть пропорциональна т2‘.
Как уже отмечалось, число различных решающих правил является слишком грубой характеристикой клас са. Уже простейшие классы решающих правил содержат бесконечное число элементов. Например, если только в персептроне спрямляющее пространство не бинарное, то число различных гиперплоскостей, разделяющих точки этого пространства, бесконечно. Для такого класса ре шающих правил проблема возможности замены миними зации среднего риска минимизацией его эмпирической оценки оставалась открытой и, как уже отмечалось, сво дилась к исследованию обобщенной теоремы Гливенко.
$ 6. УСЛОВИЯ РАВНОМЕРНОЙ сходимости |
99 |
§ 6. Условия равномерной сходимости частот появления событий к их вероятностям
Обобщение теоремы Гливенко и построение теории равномерной сходимости частот появления событий к их вероятностям стали возможны благодаря введению более тонкой меры разнообразия класса функций, чем число функций в классе. Вот как она определяется.
Пусть задана система Q решающих функций F (ж, а). Рассмотрим класс событий
А (а) = {ж : F (ж, а) = 1}.
Рассмотрим, далее, выборку жх, . . ., жг. Известно, что, вообще говоря, эта выборка может быть разделена на два класса 2' способами. Однако нас будут интересовать толь ко те способы разделения выборки, которые могут быть реализованы с помощью решающих правил F (ж, а). Чдсло таких разделений зависит как от класса решающих правил, так и от состава выборки. Будем обозначать это число
As (жх, . . ., х{).
Так как хъ . . ., жг — случайная и независимая вы борка, то число разделений — величина случайная, т. е. случайной величиной будет As (жх, . . ., жг).
Разнообразие класса решающих правил будем изме нять величиной математического ожидания lg2 As (жІ5 ...
. . ., жi). Эту величину будем называть энтропией класса S
решающих правил на выборках длины I и обозначать
HS(l) = М {lg2 А« (ж,, . . ., ж,)}. |
(5.8) |
Оказывается, что для существования равномерной сходимости частот ѵ (а) появления событий к их вероят ностям Р (а) по классу событий S необходимо и доста точно, чтобы последовательность
H s (1) |
Н s (2) |
H s (Z) |
1 > |
2 ’ ' • • ’ |
I ’ ' " |
стремилась к нулю при неограниченном увеличении длины
выборки I. Стремление к нулю отношения Н ^ означа
ет, что класс решающих правил состоит из «не слишком
4#
100 ГЛ. V. МИНИМИЗАЦИЯ ЭМПИРИЧЕСКОГО РИСКА
разнообразного множества функций». Доказательство этих утверждений дано в главах X и XI.
Как и всякие исчерпывающие условия, приведенные необходимые и достаточные условия равномерной сходи мости частот появления событий к их вероятностям ис пользуют довольно тонкие понятия. На практике проверка таких условий представляет значительные трудности. В нашем случае трудности связаны с тем, что характер распределения неизвестен, в то время как проверке под вергается свойство энтропии, которая конструктируется с помощью распределения Р (х).
Поэтому для использования на практике условий равномерной сходимости целесообразно из данных усло вий получить более грубые достаточные условия, которые не зависели бы от свойств распределения Р (х). Такие условия могут быть получены абстрагированием от свойств распределения. Иначе говоря, на практике нас будут ин тересовать те условия, которым должен удовлетворять класс решающих правил, чтобы при любой функции рас пределения можно было гарантировать существование равномерной сходимости.
Огрубление необходимых и достаточных условий за ключается в том, что вместо энтропии функции F (х , а) рассматривается логарифм функции
ms (I) = max As (хи .. ., xt),
Xi....
где максимум определяется по всем возможным выборкам длины I. Функцию ms (I) назовем функцией роста класса
F (х, а).
Функция роста построена так, что она не зависит от распределения Р (х), и, кроме того, всегда выполняется неравенство
lg2 ms (I) > Hs (l).
Теперь, если окажется, что величина
i g a m s (l)
I
стремится к нулю с ростом /, то отношение
HS(l)
I
I 7. СЙОЙСТВА ФУНКЦИИ POCfA |
101 |
и подавно устремится к нулю. Поэтому условие
lim > - 7 S(I) = О г-*=о L
является достаточным условием существования равно мерной сходимости. Это условие может быть легко про верено для различных классов решающих правил.
§ 7. Свойства функции роста
Функция роста класса решающих правил имеет про стой смысл: она равна максимальному числу способов разделения I точек на два класса с помощью решающих правил F (X, а).
В главе X будет показано, что функция роста обладает одним замечательным свойством, которое дает возмож
ность ее легко оценивать: она либо тождественно равна 21,
Іп~
либо мажорируется степенной функцией 1,5 —-----т-т-, где |
|
( П |
1)1 |
п — минимальное число, при котором нарушается равен-
ство ms (I) = 21.
В первом случае для любого I найдется комбинация точек хг, . . ., Хі такая, что ее можно разбить всеми воз можными способами на два класса с помощью решающих правил F (х, а).
Во втором случае это не всегда возможно. Существует максимальное число точек п — 1, которое еще разбива ется всеми возможными способами с помощью правил F (X, а), но уже никакие п точек этим свойством не обла дают. Оказывается, что при этом функция роста мажори руется степенной функцией с показателем роста п — 1.
Число п — 1, таким образом, может служить мерой разнообразия решающих правил в классе Q. Мы будем называть его емкостью класса £2 (при ms (I) = 2' считаем емкость бесконечной).
Нетрудно убедиться, что, если емкость класса конечна) всегда имеет место равномерная сходимость частот к ве роятностям. В самом деле, при этом
lim |
i g ^ - < |
l i m |
(" - |>lg, ^ 1'5 = О |
г-*» |
1 |
I—юо |
1 |
и достаточное условие выполнено.
