§ 2. Минимаксный критерий

Как было указано выше, в этом случае алгоритмы сравниваются по тому, как они решают наихудшую для себя задачу. Используя этот критерий для выбора оптимального алгоритма, мы будем действовать наиболее осторожно. Следует отметить, что применение этого критерия бессмысленно в случае, когда на круг решаемых задач заранее не наложено ограничений. Дело в том, что всегда существуют задачи, которым не может обучиться никакой алгоритм (например, если , независимо от , равно 0,5 при  и при ), и именно эти задачи и будут наиболее неблагоприятными для всякого алгоритма обучения, а потому все алгоритмы будут оценены одинаково. Если же круг задач заранее ограничен, минимаксный критерий может представлять интерес.

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

,

где  – показатель функции роста класса . Полагая  и переходя к математическому ожиданию, получим, что

для любой задачи  рассматриваемого типа.

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

.

С другой стороны, как показано в приложении, существует и оценка снизу:

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

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