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

І26 ГЛ. VI. МЕТОДЫ УПОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА

§ 4. Критерий Байеса

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

ДвміесаИ) = 2 Рапр(Г)'Я/(А Т ) .

т

Следующая схема реализует оптимальную по критерию

где Рапр ( Т ) — априорная вероятность задачи Т .

Здесь Рт {х, о) — распределение, соответствующее за­

3. Наконец, строится решающее правило F (х), ра­ ботающее следующим образом:

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

§ 5. УПОРЯДОЧЕНИЕ КЛАССОВ РЕШАЮЩИХ ПРАВИЛ 127

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

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

§ 5. Упорядочение классов решающих правил

Последнее замечание предыдущего параграфа можно записать следующим образом. Пусть Q — множество всех возможных задач. Тогда из этого множества может быть выделена система вложенных подмножеств

такая, что вероятность Р (Qt) встретить задачу из Qt об­ разует систему неравенств

Суть замечания состоит в том, что при переходе от Qt к Qi+i количество задач должно резко возрастать, в то вре­ мя как величины

АРі = Р (Qi+1) - Р (Qt)

монотонно уменьшаются.

Задание системы вложенных множеств (6.1) и вероят­ ностей (6 .2 ) составляют априорные сведения о тех зада­ чах, которые предстоит решать.

128 ГЛ. VI. МЕТОДЫ УПОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА

Огрубление байесовой стратегии обучения мы начнем с того, что будем использовать априорную информацию, заданную не двумя условиями (6 .1 ) и (6 .2 ), а одним усло­ вием (6 .1 ), полагая, что АP t уменьшаются. Особенностью байесовой стратегии является то, что она с большим весом

стратегию можно понимать как некоторую квазибайесо­ ву стратегию.

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

Назовем такую стратегию методом упорядоченной ми­

эмпирический риск. Если найденное решающее правило оценивается как неудовлетворительное, то ищется пра­ вило, минимизирующее эмпирический риск в классе S 2, и т. д. Процедура поиска оканчивается, когда будет най­ дено удовлетворительное решающее правило.

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

В первом случае выбирается правило, минимизирую­ щее эмпирический риск лишь в классе функций S t d S, в то время как во втором случае правило минимизирует эмпирический риск в S.

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

130 ГЛ. VI. МЕТОДЫ УПОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА

Правило, минимизирующее (6.4), обеспечивает мини­ мальную гарантированную величину вероятности оши­ бочной классификации.

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

§ 7. Несмещенность оценки скользящего контроля

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

F (X; хъ (ох; . . . ; х и сог)

решающее правило, найденное по выборке длины I, через

Р ( ^ і і а>1, • • • ) (üi) —

= § (сі ”- Fl(*г, *^1»eij, . . • , Xj, сог))а dP (x, со)

*) Процедура скользящего контроля, вероятно, впервые была предложена М. Н. Вайнцвайгом.