Контекстно-зависимая классификация

9.1. Постановка задачи

Рассмотренные ранее задачи предполагали, что нет зависимости между различными классами, т.е. имея вектор $$x$$ из класса $$\Omega_i$$, мы могли получить следующий вектор из любого класса. Далее мы будем предполагать зависимость классов, т.е. классификация каждого нового вектора осуществляется в зависимости от классификации предыдущих векторов. Выбор класса, к которому следует отнести вектор, зависит от его собственного значения, значений других векторов, существующих отношений между различными классами.

Такие задачи возникают во многих приложениях: распознавание речи, обработка изображений и др.

Эта классификация называется контекстно-зависимой.

Отправной точкой является Байесовский классификатор. Но зависимость между различными классами требует более общей формулировки проблемы. Общая информация, которая присутствует в векторах, требует, чтобы классификация была выполнена с использованием всех векторов одновременно и также была организованна в той же последовательности, в которой получена в экспериментах. Поэтому мы будем называть вектор признаков наблюдением, выстроенным в последовательность $$x_1,x_2,\ldots,x_N$$ из $$N$$ наблюдений.

9.2. Байесовский классификатор

Пусть $$X=(x_1,x_2,\ldots,x_N)$$ – последовательность $$N$$ наблюдений и $$\omega_i,\; i=1,2,\ldots,M$$ – классы, в которые эти вектора можно классифицировать. Пусть также $$\Omega_i=(\omega_{i_1},\omega_{i_2},\ldots,\omega_{i_N})$$ – одна из возможных последовательностей соответствия классов последовательности наблюдений, где $$i_k\in\{1,2,\ldots,M\}$$, $$k=1,2,\ldots,N$$. Общее число таких последовательностей классов $$\Omega_i$$ есть $$M^N$$. Задача заключается в том, чтобы решить, к какой последовательности классов отнести последовательность наблюдений. Это эквивалентно отнесению $$x_1$$ к $$\omega_{i_1}$$, $$x_2$$ к $$\omega_{i_2}$$ и т.д.

Подходом к решению проблемы является рассмотрение каждой конкретной последовательности $$X$$ как расширенного вектора признаков на $$\Omega_i,\;i=1,2,\ldots,M^N$$ как на возможных классах. В данном случае Байесовское правило$$P(\Omega_i|X)>P(\Omega_j|X),\text{ при } i\neq j$$ эквивалентно$$P(\Omega_i)p(X|\Omega_i)>P(\Omega_j)p(X|\Omega_j),\text{ при } i\neq j.$$

9.3. Модель Марковской цепи

Одна из наиболее используемых моделей, описывающих зависимость классов, является правило Марковской цепи. Если $$\omega_1,\omega_2,\ldots,\omega_N$$ есть последовательность классов, то Марковская модель предполагает, что$$P(\omega_{i_k}|\omega_{i_{k-1}},\omega_{i_{k-2}},\ldots,\omega_{i_1})=P(\omega_{i_k}|\omega_{i_{k-1}})$$

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

Другими словами, даны наблюдения $$x_{k-1},x_{k-2},\ldots,x_1$$, принадлежащие классам $$\omega_{i_{k-1}},\omega_{i_{k-2}},\ldots,\omega_{i_1}$$ соответственно. Вероятность того, что наблюдение $$x_k$$ на шаге $$k$$ принадлежит классу $$\omega_{i_k}$$, зависит только от того класса, к которому принадлежит наблюдение $$x_{i_{k-1}}$$ на шаге $$k-1$$.$$P(\Omega_i)=P(\omega_{i_1},\omega_{i_2},\ldots,\omega_{i_N})= P(\omega_{i_N}|\omega_{i_{N-1}},\omega_{i_{N-2}},\ldots,\omega_{i_1})\cdot P(\omega_{i_{N-1}}|\omega_{i_{N-2}},\omega_{i_{N-3}},\ldots,\omega_{i_1})\cdot\ldots\cdot P(\omega_{i_1})$$ или$$P(\Omega_i)=P(\omega_{i_1},\omega_{i_2},\ldots,\omega_{i_N})= P(\omega_{i_1})\cdot\prod_{k=2}^N P(\omega_{i_k}|\omega_{i_{k-1}})$$

Сделаем два общих предположения:

Это означает, что зависимость существует только на последовательности, в которой классы встречаются, но внутри классов наблюдений "подчиняются" собственным правилам. Таким образом, получаем, что$$P(X|\Omega_i)=\prod_{k=1}^N p(x_k|\omega_{i_k})$$

Комбинируя (9.1) и (9.2), получаем Байесовское правило в виде следующего утверждения.

Байесовское правило: для последовательности наблюдений векторов $$X=(x_1,x_2,\ldots,x_N)$$ проводим их классификацию в соответствующие последовательности классов $$\Omega_i=(\omega_{i_1},\omega_{i_2},\ldots,\omega_{i_N})$$ так, чтобы величина$$p(X|\Omega_i)\cdot P(\Omega_i)=P(\omega_{i_1})\cdot p(x_1|\omega_{i_1})\cdot\prod_{k=2}^N P(\omega_{i_k}|\omega_{i_{k-1}})\cdot p(x_k|\omega_{i_k})$$ была максимальной.

Поиск требует вычисления последнего выражения для каждого $$\Omega_i$$, $$i=1,2,\ldots,M^N$$, что, в свою очередь, требует $$O(NM^N)$$ умножений, а это очень много. Но существуют пути экономии вычислений. Если в $$\Omega_i$$ и $$\Omega_j$$ отличаются только последние классы, т.е. $$\omega_{i_k}=\omega_{j_k}$$, при $$k=1,2,\ldots,N-1$$ и $$\omega_{i_N}\neq\omega_{j_N}$$, то большая часть вычислений дублируется.

9.4. Алгоритм Витерби (Viterbi)

Пусть задано $$N$$ столбцов; каждая точка в столбце соответствует одному из $$M$$ возможных классов $$\omega_1,\omega_2,\ldots,\omega_M$$ ; столбцы соответствуют наблюдениям $$x_k,\;k=1,2,\ldots,N$$. Стрелками обозначены переходы от одного класса к другому в последовательности получения наблюдений. Каждая последовательность классов $$\Omega_i$$ соответствует конкретному маршруту последовательных переходов. Каждый переход от $$i$$ -го класса к $$j$$ -му характеризуется вероятностью $$P(\omega_j|\omega_i)$$, которая предполагается известной. Предположим, что эти вероятности одинаковы для всех $$k$$. Далее предположим, что условные вероятности – плотности $$p(x_k|\omega_i)$$, $$k=1,2,\ldots,N$$, $$i=1,2,\ldots,M$$ – также известны. Тогда задача максимизации (9.3) ставится как поиск последовательности переходов.

Пусть $$\widetilde{d}(\omega_{i_k},\omega_{i_{k-1}})=P(\omega_{i_k}|\omega_{i_{k-1}})\cdot p(x_k|\omega_{i_k})$$ – цена, связанная с переходом $$(\omega_{i_{k-1}},\omega_{i_k})$$. Начальное условие при $$k=1$$ есть $$\widetilde{d}(\omega_{i_1},\omega_{i_0})=P(\omega_{i_1})\cdot p(x_1|\omega_{i_1})$$. Учитывая данные предположения, получаем общую формулу, которую нужно оптимизировать:$$\widetilde{D}=\prod_{k=1}^N\widetilde{d}(\omega_{i_k},\omega_{i_{k-1}})$$ или, логарифмируя, имеем$$\ln(\widetilde{D})=\sum_{k=1}^N\ln\widetilde{d}(\omega_{i_k},\omega_{i_{k-1}})= \sum_{k=1}^N d(\omega_{i_k},\omega_{i_{k-1}})=D$$ Используем принцип Беллмана:$$D_{\max}(\omega_{i_k})=\max_{i_{k-1}=1,2,\ldots,M} \left[ D_{\max}(\omega_{i_{k-1}})+d(\omega_{i_k},\omega_{i_{k-1}}) \right], \text{ при }D_{\max}(\omega_{i_0})=0.$$ Обозначим через$$\omega_{i_N}^*=\arg\max_{\omega_{i_N}}D_{\max}(\omega_{i_n})$$

Получаем обратный ход для вычисления $$\omega_{i_k}^*$$. Получаем число операций $$O(NM^2)$$, что существенней меньше $$O(NM^N)$$. Данная процедура динамического программирования известна как алгоритм Витерби.

9.5. Скрытые Марковские модели

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

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

НММ есть в основе своей конечный автомат, который генерирует строку наблюдений – последовательность векторов наблюдений $$x_1,x_2,\ldots,x_N$$. Таким образом, НММ содержит $$k$$ состояний, и строка наблюдений получается как результат последовательных переходов из одного состояния $$i$$ в другое состояние $$j$$. Нам подходит так называемая модель "машины Моора", в соответствии с которой наблюдения получаются как результаты (выходы) из состояний на прибытие (по переходу) в каждом состоянии.

Пример. НММ с тремя состояниями. Стрелки обозначают переходы. Такая модель может соответствовать короткому слову с тремя различными стационарными частями, например, для слова "оса".

Модель предоставляет информацию о последовательных переходах между состояниями $$P(i|j),\;i,j=1,2,3$$. Такой тип НММ известен как "слева-направо", поскольку индекс состояний определяется выделенным числом фонем в одном слове. В действительности, несколько состояний (обычно 3 или 4) используется для каждой фонемы.