Classification of sequences with use hidden markov models in the conditions of the inexact task of their structure.pdf Скрытые марковские модели (СММ) широко используются в задачах моделирования различных процессов, демонстрируя при этом хорошие описательные способности. Построенные на обучающих выборках СММ используются также и для задач классификации. Однако на этих задачах СММ не всегда показывают необходимый уровень дискриминирующих свойств. В работе в качестве объектов классификации рассматривается множество смоделированных последовательностей, порожденных двумя близкими по своим параметрам СММ. Параметризация СММ проводится в соответствии с выбранной их структурой, под которой будем понимать число скрытых состояний и размер словаря наблюдаемых символов. В реальных ситуациях априорная информация о структуре СММ, как правило, отсутствует. Задача структурной идентификации в этом случае может быть поставлена, но на практике, как правило, она не решается в полном объеме. Рассматривается возможность использования традиционного классификатора на основе СММ, классификатора k ближайших соседей (kNN) и метода опорных векторов (SVM) в пространстве признаков, инициированных обученными скрытыми марковскими моделями в условиях их структурной неопределенности. 1. Постановка задачи СММ - это случайный процесс с ненаблюдаемой стационарной марковской цепью. СММ описывается следующими параметрами [1]: 1. Вектор вероятностей начальных состояний п = {п}, / = 1N, где п/ = P {qx = /}, qx - скрытое состояние в начальный момент времени t = 1; N -количество скрытых состояний в модели. 2. Матрица вероятностей переходов A = {ay.} , i, J = 1N , где a. = P{qt = j\qt — = i}, t = 2,T, где T - длина наблюдаемой последовательности. 3. Матрица вероятностей наблюдаемых символов выглядит следующим образом: B = {bi (t)}, i = W, где bi (t ) = P {ot\qt = i}, ot - символ, наблюдаемый в момент времени t = 1, T . Рассматривается случай, когда функция распределения вероятностей наблюдаемых символов описывается смесью нормальных распределений M _ , / \2 /- 2 _ b (t) = Jxy. ((ст. ) e-(o') ' 2, i = 1, n , t = 1,T , J=1 где т. - это вес J-й компоненты смеси в i-м скрытом состоянии, i = 1, N, J = 1, M, M - это количество смесей. Параметры и ст2 являются соответственно математическим ожиданием и дисперсией j-й компоненты смеси в i-м скрытом состоянии, i = 1, N , j = 1, M . Таким образом, СММ полностью описывается матрицей вероятностей переходов, а также вероятностями наблюдаемых символов и вероятностями начальных состояний: X = (A, B, п). В работе рассматривает поведение традиционного классификатора, основанного на отношении логарифмов функций правдоподобия, классификаторов kNN и SVM в условиях структурной неопределенности СММ. Один из возможных вариантов такой неопределенности заключатся в том, что исследователю точно не известно число скрытых состояний модели. Метод ближайших соседей основан на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежит большинство из его соседей - k ближайших к нему объектов обучающей выборки. Этот классификатор достаточно подробно описан, например в [2]. Основная идея метода опорных векторов - это перевод исходных векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с максимальным зазором в этом пространстве. Этот классификатор описан в [3]. 2. Пространства признаков В качестве пространств признаков, в которых производится классификация, рассматриваются пространства первых производных от логарифма функции правдоподобия по различным параметрам СММ. Приведем формулы для вычисления первых производных от логарифма функции правдоподобия по некоему параметру п (более подробно вывод формул приведен в [4-6]): d ln L (O |X) = * (т ) ^N дП k=11 t=i '' ^п/ где O = (O1, O2, ..., OK } , Ok - k-я наблюдаемая последовательность длиной T, K - количество последовательностей, ctk - параметр масштаба для последовательности Ok. В дальнейшем индекс k будем опускать для удобства. Учитывая, что ct t (i) J , формула для вычисления производной от па раметра масштаба по параметру п имеет вид dct = 2 у да t (i) 5п t i=1 5п ' где at (i), t = 1, T, i = 1, N, - так называемая прямая переменная с масштабом [6]. Для вычисления производных да t (i) да t (i) да t (i) x, z = 1, N , y = 1, M, ■xy дстлу daxz Ф. используются следующие формулы: 1 шаг. дп да t (i) дп дп [j а/ l Й дп ;г ( N 2 шаг. дп dd^ = п дШ, = i-N; дЬ (t +1) b (t)+ Ха!-1( j а V j=1 да' , (j) дс , даt ,(j) - t-1KJ' = t-1-(xt-1(j) +—ct-1, i = 1, N , t = 1, T -1. где дц дц дц в зависимости от аргумента п имеют вид дЬ (t) дп Производные ■((aim )-1 ^-цш ^ Sim (x,y) дЬ (t )=п. 8bt (t )=т 0t -Ц xy ■ = 0; = даxz дЦху гш 2 СТ2У ,(x, у ) = {0, если i = x и ш = y, 10, иначе; где Si (t )= Tm ^fMm ^ (x, y). xy 3. Результаты Исследования проводились при следующих условиях. Для моделирования последовательностей была выбрана цепь с N = 4 скрытыми состояниями. Рассматривалась задача двухклассовой классификации с моделями X и X2, определенными на одинаковых по структуре скрытых марковских цепях и различающимися только в матрицах переходных вероятностей. Параметры моделей будем отличать по их верхнему индексу. (0.2 0.5 0.3 0.05^ (n 1 ■ лA " «л A m ппЛ 0.2 0.25 0.5 0.05 ^ = 0.5 0.25 0.2 0.05 , = ,0.2 0.25 0.5 0.05, 0.2 + dA 0.5 - dA 0.3 0.05 0.2 0.25 + dA 0.5 - dA 0.05 0.5 - dA 0.25 0.2 + dA 0.05 0.2 0.25 0.5 0.05 AX1 = Параметры гауссовских распределений для модели ^ и Х2 выбирались одинаковыми для каждой модели. Параметр dA, который можно варьировать в определенных пределах, определял степень близости конкурирующих моделей. Таким образом, последнее скрытое состояние являлось своего рода шумовым: вероятность перейти в него и остаться в нем очень мала. Обучающие и тестовые последовательности моделировались по методу Монте-Карло. Для проведения экспериментов было сгенерировано по 5 обучающих наборов последовательностей для каждого класса. К каждому набору этих последовательностей моделировалось по 500 тестовых последовательностей. Результаты классификации усреднялись. Число скрытых состояний и количество компонент гауссовых смесей при моделировании последовательностей будем обозначать параметрами N и M, а параметры рабочих моделей, используемых при обучении и тестировании, - как Nl и Mi. На рис. 1 - 3 приведены графики, отражающие результаты классификации: - для kNN в пространстве первых производных от логарифма функции правдоподобия по элементам матрицы переходных вероятностей имеют пунктирную линию; - для SVM в этом же пространстве - имеют штриховую линию с короткими штрихами; - для SVM в объединенном пространстве (включаются все пространства по различным параметрам модели) - имеют штриховую линию с длинными штрихами; - графики для традиционного подхода - сплошную линию. ....... '/ . // ' W '/у / ' Л /й а 0,0 0 ,1 0 ,2 0 ,3 0 4 dA : а и II 1 в 0,0 0,1 0,2 0,3 0,4 dA 90 80 70 60 50 % f i ft if I б 90 80 70 60 50 0,0 0 ,1 0 ,2 0 ,3 0, 4 dA '■■ J / / / r I 1 1 1 г i 0,0 0,1 0,2 0,3 0,4 dA 90 80 70 60 50 J!?*"...... Т J ■ f i if II ч у в 0,0 0,1 0,2 0,3 0,4 dA 90 80 70 60 50 r i r 9 i i г 0,0 0,1 0,2 0,3 0,4 dA а -ЕЛ* V „...I*"'" Y У i-— —I_1_1_l_ —I_1_1_l_ 0,0 0,1 0,2 0 ,3 0 4 dA e V/ У >y t-r 1 t/ jLrr 0,0 0,1 0,2 0,3 0,4 dA -J б f. iT t f / } _l_l_l_l_ _l_l_l_l_ _i_i_i_i_ _i_i_i_i_ 0,0 0 ,1 0 ,2 0 ,3 0, 4 dA г Л / ff * ? У jS и 0,0 0,1 0,2 0,3 0,4 dA 90 80 70 60 50 I % 90 80 70 60 50 Рис. 1. Зависимость среднего процента верно классифицированных последовательностей от параметра близостей моделей dA при M = 2 и при Nl = M, = 2 (a); N, = M, = 3 (б); N, = M, = 4 (в); N, = M, = 6 (г) На рис. 1 приведены зависимости среднего процента верно классифицированных последовательностей от параметра близостей моделей dA для случая, когда моделирование производилось при N = 4 и M = 2. Для рабочих моделей при обучении и тестировании выбирались различные параметры N и M. На рис. 2 и 3 приведены аналогичные зависимости для M = 4 и M = 6 соответственно. По рис. 1 можно отметить, что уже при N{ = Ml = 3 у SVM- и kNN-классифика-торов наблюдаются примерно такие же результаты, как N{ = Ml = 6 , в то время как традиционный классификатор показывает худшие результаты. Аналогичная картина наблюдается и на рис. 2 и 3 при Nt = Mr = 4 . Таким образом, для классификации по производным, по всей видимости, не нужны особо точные оценки, в то время как для традиционного классификатора этот момент является критическим. Рис. 2. Зависимость разности среднего процента верно классифицированных последовательностей от параметра близостей моделей dA при M = 4 и при Nj =Mj = 2 (а); Nt =Mt = 3 (б); Nt =Mt = 4 (в); Nt =Mt = 6 (г) При увеличении параметра dA заметна общая тенденция к уменьшению выигрыша от использования классификаторов в пространстве производных. Это связано с тем, что традиционный классификатор при достаточном различии моделей уже сам показывает хорошие результаты, близкие к 100 %. В то же время анализ рис. 1 - 3 говорит о том, что чувствительность классификаторов kNN и SVM к ошибкам спецификации структуры СММ несколько ниже, чем у традиционного классификатора. Выигрыш от их использования составил: на рис. 1, а - до 14 %, на рис. 2, а - до 18 %, на рис. 3, в - до 40 %. Общая тенденция такова: чем меньше 90 80 70 60 50 I % 90 80 70 60 50 90 80 70 60 50 ( % 90 80 70 60 50 взято количество N и Mt, тем больший выигрыш в точности классификации можно получить, используя kNN или SVM. Рис. 3. Зависимость среднего процента верно классифицированных последовательностей от параметра близостей моделей dA при M=6 и при Nt =Mt = 2 (a); Nt = Mt = 3 (б); Nt = Mt = 4 (e); Nt = Mt = 6 (г) Традиционный классификатор показывает хорошие результаты, когда выбираются количества скрытых состояний и смесей N{ и Mt большие, чем истинные значения N и M. Таким образом, когда нет возможности провести структурную идентификацию СММ можно рекомендовать использовать классификатор kNN или SVM в пространстве первых производных от логарифма функции правдоподобия в силу их меньшей чувствительности к такой ошибки спецификации структуры как недобор числа скрытых состояний и компонент гауссовых смесей. При выборе пространства производных по тому параметру, по которому генерирующие последовательности модели отличаются, выигрыш в сравнении с использованием объединенного пространства, получается максимально 4 % (рис. 1, а), 3% (рис. 2, e), 6 % (рис. 3, б). Классификатор SVM всегда показывает лучшие результаты, чем kNN в пространстве первых производных по элементам матрицы переходных вероятностей: до 10 % (рис. 1, а), 16 % (рис. 2, б), 8 % (рис. 3, а). Кроме того, по рис. 2, а, б, 3, e видно, что kNN при некоторых значениях параметра dA проигрывает традиционному классификатору. Заключение Исследования показали, что в условиях структурной неопределенности использование классификатора k ближайших соседей и классификатора, основанного на методе опорных векторов, приводит к повышению качества классификации в сравнении с традиционным подходом, основанным на отношении логарифмов функций правдоподобия. При этом прирост процентов верной классификации в рассмотренной двухклассовой задаче в сравнении с традиционным подходом в ряде случаев может достигать 40 % как для kNN, так и для SVM. Последний показывает более точные результаты в сравнении с kNN. Максимальное улучшение достигает около 18 %.

Скачать электронную версию публикации