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

числа базисных (например, пороговых) элементов эти функции мо­ гут быть реализованы, то окажется, что из всех 22” возможных функ­

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

меньше 2™2). Но самое интересное заключается в том, что, хотя поч­ ти все функции сложные, построить (просто выписать в виде табли­ цы значения во всех 2п точках) сложную функцию чрезвычайно трудно. Во всяком случае, уже для п = 7 нет примеров сложной функции.

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

Если при любом «разумном» определении сложности окажется, что сложные функции составляют подавляющее большинство всех функций, то гипотеза «мир. прост» становится чрезвычайно содержа­ тельной. Вопросы исследования сложности математических объек­ тов в настоящее время являются чрезвычайно актуальными [20, 37].

Кглаве IX

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

симации применена для минимизации функционала

с выпуклыми по а при любом фиксированном z функциями потерь Q (z, а). Результаты для этого частного случая могут быть полу­ чены из общих теорем о сходимости процессов процедуры стохасти­ ческой аппроксимации. Однако здесь приведены доказатель­ ства сходимости для этого частного процесса процедуры стохасти­ ческой аппроксимации непосредственно в том виде, в каком они были получены Б. М. Литваковым [44]. Аналогичные резуль­ таты получены и Ю. М. Ермольевым [27]. Вообще же для рас­ смотренного случая известно [26], что если Q (z, а) — одноэкстре­ мальная функция, то при определенных условиях процедура стоха­

стохастической аппроксимации гарантирует достижение лишь ло­ кального минимума.

данным является одной из основных задач статистики. Известные методы решения этой задачи распадаются на два типа: параметри­ ческие и непараметрические методы.

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

Непараметрические методы не связаны с предположением о виде функции распределения. Они основаны на реализации одной из двух идей:

1) восстановление плотности распределения вероятностей (в этом случае достаточна гипотеза о гладкости функции плотности распределения вероятностей);

2) восстановление вероятностей определенного множества со­ бытий.

Методы восстановления функции плотности распределения ве­ роятностей предлагались Е. Парзеном [88], Н. Н. Ченцовым [69], М. А. Айзерманом, Э. М. Браверманом, Л. И. Розоноэром [1]. По­ следние авторы рассматривали эту задачу в связи с проблемой обу­ чения распознаванию образов в вероятностной постановке. Однако восстановление плотности распределения вероятностей требует зна­ чительного объема выборки. Это особенно существенно в многомер­ ном случае, когда для восстановления плотности распределения часто необходима длина выборки во много раз большая, чем 2П, где п — размерность пространства.

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

Если класс состоит всего из одного события, то вопрос стоит о сходимости частоты к вероятности для одного фиксированного со­ бытия. Ответ на этот вопрос был получен еще в XVIII веке Яковом Бернулли (сходимость почти наверное установлена Э. Борелем одно­ временно с введением этого понятия).

Случай конечного числа событий принципиального интереса не представляет, так как равномерная сходимость частот к вероятностям здесь легко следует из закона Бернулли.

В 30-е годы особое внимание уделялось равномерной сходимости эмпирических кривых распределения к функциям распределения. В 1933 году В. И. Гливенко доказал [79], что имеет место равномер­ ная сходимость эмпирических кривых к функциям распределения для произвольной функции распределения. В том же году А. Н. Кол­ могоров для непрерывной функции распределения F(x) установил следующую асимптотическую оценку [83]:

где ?і (х) = V1 {I: | < ж} — эмпирическая кривая распределения,

ОО

Дальнейшие уточнения были получены II. В. Смирновым [59]. Он исследовал также уклонение эмпирических кривых, построен­ ных по двум независимым выборкам, при неизменном распределе­ нии [59]. Как сказано в основном тексте, исследование близости эмпирических кривых к функциям распределения равносильно исследованию равномерной близости частот к вероятностям по классу событий вида

{£ : I < *}■

Разумеется, из равномерной близости эмпирических кривых к функциям распределения следует равномерная близость частот к вероятностям и в более широких классах событий (но не для всех событий!).

Таким образом, интерес исследований 30—40-х годов к равно­ мерной сходимости ограничивался одномерным случаем, что, види­ мо, связано с ограниченностью вычислительных возможностей того времени. После появления быстродействующих вычислительных машин стали возможными новые методы обработки статистических данных, например, такие, которые применяются в задачах обучения распознаванию. В связи с этим возникла необходимость предельно обобщить теорему Гливепко и выяснить, насколько широк может быть класс событий, чтобы еще имела место равномерная сходимость частот к вероятностям, и как изменяется скорость такой сходимо­ сти с расширением класса. Ответы на эти вопросы получены нами в работах [18, 19] и составляют предмет изложения глав X, XI и XII. Полученные оценки не так точны, как оценки Колмогоро­ ва — Смирнова для близости эмпирических кривых к функциям распределения. Вопрос получения асимптотически точных оце­ нок остается пока открытым.

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

К главе XIII

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

Вряде работ оценивается достаточная длина выборки в случае гипотезы о нормальном распределении классов [55].

Вработе [16] мы исходим из предположения, что классы заведо­ мо безошибочно разделимы одним из N заданных решающих правил.

При этом оказалось, что достаточная длина обучающей выборки оце­ нивается сверху:

^ ln N — ln Г|

^дост ^ _ in (1 _ е) >

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

Случай, когда разделяемые множества могут быть заключены в параллелепипед с гранями, параллельными осям координат, рас­ сматривал Б. М. Курилов [39].

У. Хайлимен [81] предлагал для оценки достаточной длины обучения в классе линейных решающих правил вспользоваться обычным биномиальным распределением. Этот путь является лож­ ным, так как при этом не учитывается требование равномерной бли­ зости оценок риска к их истинному значению по всему классу решаю­ щих правил. Этим путем можно вывести конечные оценки длины обучения для сколь угодно емких классов решающих правил, что неверно.

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

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

Вопрос о равномерной по параметру сходимости средних к ма­ тематическим ожиданиям возник в связи с исследованием эффектив­ ности оценок максимального правдоподобия. Упомянутый резуль­ тат Л. Ле-Кама [85] получен им на основе идей А. Вальда [96]. Ре­ зультат, основанный на сведении к равномерной сходимости частот к вероятностям, получен в [19]. Оба условия являются лишь доста­ точными и не перекрывают друг друга. Необходимых и достаточных условий равномерной сходимости средних к математическим ожида­ ниям пока нет.

К главе XIV

Метод обобщенного портрета был предложен в 1963 году в ра­ ботах [13, 15]. Позже [17] было показано, что построение обобщенно­ го портрета эквивалентно отысканию максимума неположительно определенной квадратичной формы в положительном квадранте, а