6.3. Бейесовские оптимальные процедуры классификации, основанные на динамическом программировании

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

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

где — последовательность из 1 членов, содержащая и имеющая в качестве члена пару Отметим, что — целое число от 1 до Если правой частью в (9) служит верхняя строка, то решение заключается в отнесении объекта к классу в противном случае измерения продолжаются. К сожалению, для нахождения оптимальной процедуры обработки последовательности измерений длины надо найти оптимальную процедуру для всех последовательностей длины которые можно получить из первоначальной последовательности. Этот случай отражен нижней строкой в (9). В худшем возможном случае для определения оптимальной процедуры может потребоваться рассмотреть оптимальную процедуру для всех возможных последовательностей наблюдений длины или меньше. Это может оказаться нелегким делом. Предположим для простоты, что число принимаемых значений для всех измерений одинаково и равно Число возможных последовательностей

Таблица 6.1 (см. скан) Число возможных последовательностей описаний как функция числа измерений и числа значений каждого измерения

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