§ 4. Восстановление характеристической функции в классе линейных решающих правил

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

Теперь, для того чтобы задать алгоритмы упорядоченной минимизации риска, надо определить структуру на множестве функций

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

Рассмотрим сначала задачу распознавания образов.

Пусть задан класс линейных решающих правил

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

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

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

С достоверностью вероятность ошибочной классификации с помощью найденного решающего правила не

превосходит достигнутого минимума (8.26), т. е.

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

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

Структура (8.32) построена так, что Очевидно, что функция роста оценивается через функцию роста

Таким образом, метод упорядоченной минимизации риска на структуре (8.27) приведет к выбору функции минимизирующей по и функционал

Для найденного решения справедливо

Для обоих типов структур в качестве алгоритма выбора второго уровня может быть также использована процедура «скользящий контроль».

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

в нем решающее правило, минимизирующее эмпирический риск.

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

Таблица 1

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