Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 185
Скачиваний: 4
§ 1. О КРИТЕРИЯХ ОЦЕНКИ КАЧЕСТВА АЛГОРИТМОВ Ц 9
мы определили выше как
Jf?(a) = \ (со — F (х, а * ) ) 2 dP (х , со).
Но поскольку выбор решающего правила зависит от слу
чайно составленной обучающей последовательности соь ...
ссгсог, величина Р (а) будет |
||
случайной, зависящей от той |
||
или иной реализации обучаю |
||
щей |
последовательности. |
|
Случайная величина наибо |
||
лее полно характеризуется сво |
||
ей |
функцией |
распределения. |
В нашем случае |
качество алго |
|
ритма, решающего фиксирован ную задачу на выборках длины I, будет определяться функцией распределения качества р(Р(а)).
Сравнивать качество двух алгоритмов — значит сравни
вать две функции распределения. Если одна из функций расположена не ниже другой (так, как на рис. 13), то выбор может быть сделан однозначно. При таком распо
|
ложении |
кривых |
для любых |
|||
|
двух точек с равными ордина |
|||||
|
тами абсцисса точки первой кри |
|||||
|
вой лежит левее абсциссы точ |
|||||
|
ки второй кривой. Это значит, |
|||||
|
что для любого уровня надеж |
|||||
|
ности первый алгоритм гаран |
|||||
|
тирует |
достижение |
меньшего |
|||
|
значения функционала и пото |
|||||
|
му лучше второго. |
Однако воз |
||||
|
можны |
и |
такие расположения |
|||
Рис. 14. |
функций распределения качест |
|||||
|
ва |
двух |
|
алгоритмов, |
как на |
|
|
рис. |
14. |
|
|
|
|
Вэтом случае для одного уровня надежности (р —
—1 —т1г) оказывается предпочтительнее первый алгоритм,
адля другого (р = 1 — %) предпочтение должно быть
отдано второму. Таким образом, сравнивать между собой функции распределения качества алгоритмов, решающих некоторую задачу Р (х , о) на выборках длины I, можно
120 ГЛ. VI. МЕТОД УПОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА
только при фиксированном уровне надежности. Это соз дает некоторые неудобства, поэтому будем иногда харак теризовать качество алгоритма не функцией распределе ния р, (Р (а)), а математическим ожиданием качества
Я = J -Р (а) dp (Р (а))-
Теперь для решения предложенной задачи на выборках длины I будем считать тот алгоритм лучшим, для которого соответствующая величина математического ожидания меньше.
Обозначим через А алгоритм обучения, а через Т кон кретную задачу; тогда качество алгоритма А, решающего задачу обучения распознавания образов Т на выборках длины I, можно записать как функцию двух переменных
Ri(A, Т).
Итак, определено, как должно измеряться качество R i ( A , Т ) для любой фиксированной задачи Т . Далее сле дует договориться, как измерять качество алгоритма, предназначенного для решения класса задач { Т } .
Разрешению этой трудности посвящена теория стати стических решений. В этой теории для сравнения различ ных алгоритмов предлагаются следующие три критерия:
а) критерий Байеса, б) критерий минимакса,
в) критерий минимакса потерь.
Критерий Байеса предлагает вычислять для каждого алгоритма среднее по множеству всех задач качество. Для этого надо знать закон, который указывал бы, с какой вероятностью придется решать ту или иную зада чу, т. е. знать функцию распределения Р (Т). Тогда критерий Байеса определяется так:
^Байеса (А) = $ R i ( А , Т ) dP ( Т ) .
Критерий минимакса наиболее осторожен. Он пред лагает оценивать качество алгоритма как качество ре шения наиболее неблагоприятной для данного алгоритма задачи. При таком критерии, напротив, совершенно не принимается во внимание, какова вероятность того, что на практике придется решать эту неблагоприятную за дачу. Поэтому может оказаться так, что качество алго ритма определяет задача, которая на практике никогда
§ 2. МИНИМАКСНЫЙ КРИТЕРИЙ |
121 |
не встретится. Иначе говоря, этот критерий конструирует ся так:
#мм (4) = max R[ {А, Т).
т
Критерий минимакса потеръ предполагает минимиза цию наибольшей величины потери качества, ко торая возникает из-за применения данного алгоритма для решения разных задач по сравнению с применением опти мального для каждой из задач алгоритма. Иначе говоря, критерий минимакса потерь конструируется по правилу:
#м.п (-4) = max (R, {А , Т ) — min R, (А, Т)).
т |
А |
Эта глава посвящена сравнению различных алгорит мов обучения распознаванию образов. В ней будут рас смотрены оптимальные с точки зрения различных крите риев алгоритмы, установлена близость алгоритмов, ми нимизирующих эмпирический риск, к оптимальным с точки зрения минимаксного критерия и критерия минимакса потерь. Однако алгоритмы, оптимальные по этим двум критериям, не столь интересны, как алгоритмы, оптими зирующие критерий Байеса. Построение же оптимальных по критерию Байеса алгоритмов — задача, практически неосуществимая из-за чрезвычайно громоздких вычис лений. Поэтому представляют интерес квазибайесовы про цедуры, которые сохраняют ценные свойства байесовых процедур, но не столь громоздки. В этой главе будут рас смотрены алгоритмы упорядоченной минимизации риска, которые реализуют такие процедуры.
Рассмотрение оптимальных алгоритмов начнем с ис следования алгоритмов, оптимальных по минимаксному критерию.
§ 2. Минимаксный критерий
Как было указано выше, в этом случае алгоритмы срав ниваются по тому, как они решают наихудшую для себя задачу. Используя этот критерий для выбора оптимально го алгоритма, мы будем сействовать наиболее осторожно. Следует отметить, что применение этого критерия бессмыс ленно в случае, когда на круг решаемых задач заранее не наложено ограничений. Дело в том, что всегда
122 ГЛ. VI. МЕТОД УП ОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА
существуют задачи, которым не может обучиться никакой алгоритм (например, если Р (со | ж), независимо от х, равно 0,5 при о) = 1 и при со = 0), и именно эти задачи и будут наиболее неблагоприятными для всякого алгоритма обу чения, а потому все алгоритмы будут оценены одинаково. Если же круг задач заранее ограничен, минимаксный критерий может представлять интерес.
Пусть, например, заранее известно, что все задачи та ковы, что для каждой из них в классе S существует без ошибочное разделяющее правило (детерминистский слу чай). Тогда, как установлено в предыдущей главе, для лю бой задачи алгоритм А, основанный на минимизации эм пирического риска, с вероятностью, превышающей 1 — т), построит по обучающей последовательности длины I решающее правило с качеством не хуже
|
|
п |
1 1 1 21 |
\ Ни |
|
|
|
е = 2 |
|
I |
|
|
|
|
|
|
|
где |
п — показатель функции |
роста класса S.. Полагая |
|||
т] = |
i ß |
и переходя к математическому ожиданию, |
полу |
||
чим, |
что |
|
|
|
|
|
|
min R t (А, Т) < |
2 _"(1п 21-1-п " + Л + - 1 + ^ . |
|
|
|
|
А |
|
1 |
|
для любой задачи Т рассматриваемого типа. |
|
||||
Следовательно, |
|
|
|
||
min max Rt (А, Т) < |
2 ге(> 2г~ Іп” + ^) + 1 +1я2* |
_ |
|||
|
А |
Т |
|
1 |
|
С другой стороны, как показано в приложении, сущест вует и оценка снизу:
min max Д, (Л, Т) ;>
ат
[ |
/ |
1 \г |
, |
если Z < n, |
|
0,5 ^1— —j_—j |
|||
I |
|
_ 1 Г т )г^ |
0’2т т г ’ |
еслиг> и- |
Таким образом, в этом случае любой алгоритм, осно ванный на минимизации эмпирического риска, довольно близок к минимаксному. Кроме того, при конечном п
I 3. КРИТЕРИЙ МИНИМАКСА ПОТЕРЬ |
12â |
минимакс стремится к нулю при I -> оо, но тем медленнее, чем больше п.
Отметим, что непосредственное конструирование оп тимального с точки зрения минимаксного критерия алго ритма обучения для заданного круга задач,—вообще гово ря, проблема чрезвычайно сложная и, вероятно, не благодарная.
§ 3. Критерий минимакса потерь
Рассмотренный в предыдущем параграфе критерий тре бует предварительного явного выделения определенного круга задач. Это не всегда удобно. Чаще ситуация такова, что задан определенный класс решающих правил S и рассчитывают на задачи, для которых в этом классе есть «достаточно хорошие» разделяющие правила. Критерий минимакса потерь позволяет не определять явно, что зна чит «достаточно хорошие» правила.
Идея этого критерия состоит в следующем. Для задан ного набора алгоритмов Q потери л определяются как раз ность между качеством данного алгоритма А для данной задачи и качеством наилучшего для этой задачи алгорит ма из набора Q:
n(A,T) = R t (А, Т) - min Rt {А, Т).
А<=Q
В дальнейшем будем считать, что Q состоит из всевозмож ных алгоритмов обучения, выбирающих решающие пра вила из класса S. Тогда, как нетрудно убедиться,
я (И, Т) = R t (А, Т) — min Р (ос, Т),
a e S
где Р (a, Т) — качество решающего правила F (х, а) для задачи Т, и следовательно,
min Р (a, Т) аes
—- это качество наилучшего для данной задачи решающе го правила из класса S.
Таким образом, потери оценивают степень «недоучен ное™», тогда как min/*(a, Т) — это тот процент ошибок,
a e s
который неизбежен даже при идеальной обученности.
124 ГЛ. VI. МЕТОДЫ УПОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА
Максимум потерь определяется как потери на наибо лее неблагоприятной с этой точки зрения задаче. Заме тим, что в случае минимаксного критерия задача счи тается «плохой», если выбранный алгоритм дает большое число ошибок на экзамене независимо от того, сущест вует ли вообще в данном наборе алгоритм, который хо рошо решает задачу. В случае же минимакса потерь за дача считается «плохой», если выбранный алгоритм работает плохо, но существует другой алгоритм из данного набора, который эту конкретную задачу решает хорошо.
Результаты предыдущей главы могут быть применены для оценки сверху величины минимакса потерь алгорит мов, минимизирующих эмпирический риск. В соответ ствии с оценкой (5.11) для любой задачи распознавания алгоритм А, основанный на минимизации эмпирического риска, с вероятностью 1 — ц выберет решающее правило, отличающееся от оптимального в классе S не более чем на
_ |
0 -| f |
re (Іа 2/ — ln re -(- 1) ■ ln г|/5 |
г - |
z у |
Г=1 |
Положив т( = у, перейдем к математическому ожиданию;
получим, учитывая, что Р (а) < 1 ,
я (Л, ТX 2 У ^ I - ^ J L + Л + ,1а Ы
Следовательно,
min max я (А, Г) < 2 У п (In 21 — ln re -f- 1) -f- ln 5/
АТ I
Сдругой стороны, можно установить оценку снизу (см. приложение)
min max я (А, Т) > < |
0,5е п , |
если |
I |
n, |
0,25+ |
если |
n |
I <( 21, |
|
А Т |
|
|
|
|
. P - f c 1 |
- ® ' f ( l » , |
если I 2n, |
|
і з. Кр и т е р и й м и н и м а к с а п о т е р ь |
125 |
для алгоритмов А , выбирающих разделяющее правило из класса S, и любых задач распознавания.
Таким образом, алгоритмы, минимизирующие эмпи рический риск, оказываются довольно близкими к опти мальным по критерию минимакса потерь. Очевидно, что минимакс потерь при конечном п стремится к нулю при I -> оо. Если же функция роста ms (I) = 2г, то максималь ные потери вообще не убывают с ростом I, оставаясь рав ным 0,5, т. е. обучение не происходит.
Как было показано в главе V, величина п, входящая как в верхнюю, так и в нижнюю оценку минимакса по терь, является мерой объема класса S. Таким образом, минимакс потерь тем больше, чем шире класс решающих правил, из которого осуществляется выбор. Это несколь ко парадоксальное заключение легко понять, если учесть, что мы фактически рассматриваем только такие задачи,
для которых в |
классе S есть решающее правило, удов |
|
летворительно |
разделяющее классы. Это значит, что |
|
с увеличением |
класса |
S расширяется и круг задач, из |
которого выбирается |
наиболее трудная для данного |
|
алгоритма.
Вообще для данного алгоритма А и задачи Т средний риск (т. е. качество) распадается на три составляющие:
R (А, Т) = я (А, Т) + А, (Т, S ) + Д2 (Т).
Здесь Д2 — это неизбежная составляющая риска, которая остается даже при использовании самого лучшего решаю щего правила для данной задачи, выбранного без всяких ограничений. Величина Дх + Д2 определяет качество наи лучшего решающего правила в классе S', таким образом, Дг — это потери, связанные с ограничением, заставляю щим выбирать правило только из класса S (в детерминист ской постановке Д2 + Дх = 0). Наконец, я — это потери в смысле, определенном выше; они отражают то, насколь ко решающее правило, выбираемое алгоритмом А в ходе обучения, близко к оптимальному в классе S.
Величина Д2 (Т) зависит только от задачи распознава ния. Величина Дх (Т, А) зависит уже от класса S, но не зависит от алгоритма обучения. Потери же я [А, Т) за висят от задачи, класса S и конкретного алгоритма обу чения.
