§ 3. Критерий минимакса потерь

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

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

.

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

,

где  – качество решающего правила  для задачи , и следовательно,

– это качество наилучшего для данной задачи решающего правила из класса .

Таким образом, потери оценивают степень «недоученности», тогда как  – это тот процент ошибок, который неизбежен даже при идеальной обученности.

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

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

.

Положив , перейдем к математическому ожиданию; получим, учитывая, что ,

.

Следовательно,

.

С другой стороны, можно установить        оценку снизу (см. приложение)

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

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

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

Вообще для данного алгоритма  и задачи  средний риск (т. е. качество) распадается на три составляющие:

.

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

Величина  зависит только от задачи распознавания. Величина  зависит уже от класса , но не зависит от алгоритма обучения. Потери же  зависят от задачи, класса  и конкретного алгоритма обучения.