§ 8. Упорядочение по размерностям

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

Рассмотрим класс линейных решающих правил

.

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

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

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

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

.                   (6.6).

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

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

,

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

 .                 (6.7)

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

Как уже указывалось в главе V, оценка доверительного интервала (5.11) является пессимистической и достигается лишь в случае, когда вероятность ошибок близка к . Для решающих правил, оценки вероятностей ошибок которых малы , лучше пользоваться более тонким критерием (5.23):

вместо оценки (6.6) и аналогичным критерием

вместо (6.7). Эти критерии не столь наглядны, но зато более точны.