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

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

                     (6.1)

такая, что вероятность  встретить задачу из  образует систему неравенств

.                (6.2)

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

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

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

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

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

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

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

.

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

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

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

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

Для конструктивного задания алгоритмов метода упорядоченной минимизации риска необходимо определить:

1. Каков критерий выбора решающего правила (т. е. задать алгоритм второго уровня).

2. Как вводить упорядочение класса решающих правил .

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