Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


Глава VI. МЕТОД УПОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА

§ 1. О критериях оценки качества алгоритмов

До сих пор мы интересовались только тем, каким условиям должен удовлетворять алгоритм, чтобы обеспечить машине способность обучаться. Были рассмотрены рекуррентные алгоритмы. Оказалось, что они требуют достаточно большой обучающей последовательности. Поэтому была рассмотрена их модернизация, которая заключалась в запоминании обучающей последовательности и многократном ее использовании. Суть этой модернизации состояла в том, что задача решалась методом минимизации эмпирического риска. Были найдены условия, при которых алгоритмы минимизации эмпирического риска приводят к успеху, и тем самым получена возможность строить различные алгоритмы, способные обучаться распознаванию образов. Какой же алгоритм выбрать теперь для решения конкретных задач? Какой из алгоритмов обучения распознаванию образов будет лучше работать на выборках фиксированной длины ?

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

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

.

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

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

Сравнивать качество двух алгоритмов – значит сравнивать две функции распределения. Если одна из функций расположена не ниже другой (так, как на рис. 13), то выбор может быть сделан однозначно.

111-1.jpg

Рис. 13.

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

111-2.jpg

Рис. 14.

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

.

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

Обозначим через  алгоритм обучения, а через  конкретную задачу; тогда качество алгоритма , решающего задачу обучения распознавания образов  на выборках длины , можно записать как функцию двух переменных .

Итак, определено, как должно измеряться качество  для любой фиксированной задачи . Далее следует договориться, как измерять качество алгоритма, предназначенного для решения класса задач .

Разрешению этой трудности посвящена теория статистических решений. В этой теории для сравнения различных алгоритмов предлагаются следующие три критерия:

a) критерий Байеса,

б) критерий минимакса,

в) критерий минимакса потерь.

Критерий Байеса предлагает вычислять для каждого алгоритма среднее по множеству всех задач качество. Для этого надо знать закон, который указывал бы, с какой вероятностью придется решать ту или иную задачу, т. е. знать функцию распределения . Тогда критерий Байеса определяется так:

.

Критерий минимакса наиболее осторожен. Он предлагает оценивать качество алгоритма как качество решения наиболее неблагоприятной для данного алгоритма задачи. При таком критерии, напротив, совершенно не принимается во внимание, какова вероятность того, что на практике придется решать эту неблагоприятную задачу. Поэтому может оказаться так, что качество алгоритма определяет задача, которая на практике никогда не встретится. Иначе говоря, этот критерий конструируется так:

.

Критерий минимакса потерь предполагает минимизацию наибольшей величины потери качества, которая возникает из-за применения данного алгоритма для решения разных задач по сравнению с применением оптимального для каждой из задач алгоритма. Иначе говоря, критерий минимакса потерь конструируется по правилу:

.

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

Рассмотрение оптимальных алгоритмов начнем с исследования алгоритмов, оптимальных по минимаксному критерию.

 



<< ПредыдущаяОглавлениеСледующая >>