4.3. Уменьшение объема вычислений

4.3.1. Использование достаточных статистик.

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

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

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

где априорная вероятность для класса Конкретно, на шаге

на шаге

на первом шаге

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

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

Величина в действительности является риском усечения последовательного процесса. Надо отметить, что, аналогично изложенному в 1.4,

в случае функции потерь т. е. при

решающая процедура сводится к следующему: принимается решение если

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

4.3.2. Предположение о марковской зависимости.

Во многих задачах распознавания предположение о независимости замеров и игнорирование порядка измерений может привести к неприемлемому количеству ложных распознаваний.

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

При решении рекуррентного уравнения (4.1) уменьшение объема вычислений может быть достигнуто также

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

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

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

Тогда риск продолжения, согласно (4.1), вычисляется следующим образом:

Функциональное уравнение, определяющее марковскую последовательность замеров, приобретает вид

Уравнение (4.18) также может быть решено в обратном направлении при следующем условии завершения:

где

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