Распознавание неполных последовательностей, описываемых скрытыми марковскими моделями, в пространстве первых производных от логарифма функции правдоподобия | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. DOI: 10.17223/19988605/42/9

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

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

Recognition of incomplete sequences described by hidden Markov models using first derivatives of likelihood function log.pdf Теория скрытых марковских моделей (СММ) была представлена еще в 1970-х гг. Л. Баумом и его коллегами [1]. Изначально СММ применяли для распознавания речи. В конце 1980-х гг. СММ начали использовать в биоинформатике, например для обработки цепочек ДНК. Тем не менее наибольшую популярность СММ обрели после 1990-х гг., и данная тенденция продолжается и в настоящее время, что можно подтвердить частотой упоминания термина «hidden Markov model» в публикациях [2]. Однако в теории СММ остается малоизученная область, касающаяся вопросов применения СММ для анализа неполных данных. Данные вопросы являются актуальными, поскольку в сложных системах, например при приеме данных с космических и авиационных аппаратов, а также других источников, приходится иметь дело с потоками данных от различных датчиков в сложной помеховой обстановке, когда возможно пропадание информации или ее искажение. В настоящей работе рассматривается такой случай неполных данных, как наличие пропусков в распознаваемых последовательностях. Такие последовательности с пропусками будем называть неполными. В рассматриваемой ситуации пропуски не генерируются самим случайным процессом, описываемым СММ, а возникают в произвольных местах последовательностей за счет внешних условий. Данная статья является продолжением исследований по распознаванию последовательностей, описываемых СММ, проводимых на кафедре теоретической и прикладной информатики Новосибирского государственного технического университета [3]. Отличие проводимого исследования заключается в том, что распознаваемые последовательности могут содержать пропуски. 1. Описание скрытой марковской модели 1.1. Структура скрытой марковской модели Скрытой марковской моделью называют модель, описывающую случайный процесс, находящийся в каждый момент времени t е{1,..., T} в одном из N скрытых состояний s e{sx,..., s^ } и в новый момент времени переходящий в другое или в прежнее состояние согласно некоторым вероятностям переходов. Состояния считаются скрытыми, однако они проявляются в тех или иных особенностях наблюдаемых последовательностей. В данной работе рассматриваются СММ с непрерывной плотностью распределения наблюдений, когда в общем случае многомерные наблюдения - это векторы действительных чисел. Значения наблюдаемых величин при условии того, что СММ находится в конкретном скрытом состоянии, подчиняются некоторым вероятностным законам. В случае СММ с непрерывной плотностью распределения наблюдений эти вероятностные законы описываются функциями условной плотности распределений наблюдений. Рассмотрим параметры, которыми можно полностью задать конкретную СММ. Обозначим скрытое состояние, в котором находится описываемый СММ процесс в момент t, символом qt, многомерное наблюдение, которое он сгенерировал в момент времени t, - символом ot, а многомерное наблюдение, не привязанное к конкретному времени, - символом о. СММ с непрерывной плотностью распределения характеризуется вектором вероятностного распределения начального скрытого состояния П = = p(qi = Sj^j, i = 1,n}, матрицей вероятностей переходов из одного скрытого состояния в другое A = {aj = p (qt+1 = Sj | qt = si j, i, j = 1, n}, а также функциями условной плотности распределений многомерных наблюдений B = {bi (o j = f (o | q = si j, i = 1, N, o e Rz j [4]. В данной работе в качестве функций условной плотности распределения наблюдений рассматривается смесь многомерных норм мальных распределений: bt (o) = 2 Timg(o; vim, Sim ), i = 1,N, o e R , где M- число компонент в смеси m=1 для каждого скрытого состояния, Tim > 0 - вес m-й компоненты смеси в i-м скрытом состоянии M - ( Z Tim = 1, i = 1, N), цгт - математическое ожидание нормального распределения, соответствующего m=1 m-й компоненте смеси в i-м скрытом состоянии, Sim - ковариационная матрица нормального распределения, соответствующая m-й компоненте смеси в i-м скрытом состоянии, а g(о;Sim), о e Rz -функция плотности многомерного нормального распределения, т.е. g(o;vim, Sim) = промежуточные произведения, чтобы они не стремились к нулю. Эффективные методы масштабирования, которые практически не замедляют обучения, известны и приведены в [4]. Первая часть forward-backward алгоритма (ее достаточно для вычисления логарифма функции правдоподобия) производит вычисление отмасштабированных прямых вероятностей p({o^o2,...,ot},qt = st | A,), t = 1, T, i = 1,N, т.е. вероятностей того, что последовательность многомерных наблюдений {o, o2,..., ot} была порождена процессом, описываемым моделью А, и что данный процесс находился в скрытом состоянии Si в момент времени t. Алгоритм вычисления отмасштабированных прямых вероятностей и логарифма функции правдоподобия: 1) инициализация: a (i) = -Kb o), i = IN; (29) 2) индукция: , i = i, N, t = 1,T-1, N Z a; (j)a j=1 й*+1 (i) = bi(ot+l) (30) j2 где j = \,N, t = \,T-\ ■ (31) a; (j) = N _ ' E at(n) n=1 Определим параметр масштаба: ct = f ЕаДО -i t = l,T. (32) тогда i = 1, N, t = 1,T-1, at(i) = 1 Пcr af), i = 1,N, t = 1,T-1. r=1 Логарифм функции правдоподобия для последовательности наблюдений может быть вычислен с помощью параметров масштаба: т ln [ p (O|A )] = -Z ln Ct. (33) t=1 2. Распознавание неполных последовательностей, описываемых СММ Прежде чем производить распознавание неполных последовательностей, описываемых СММ, необходимо оценить параметры соответствующих СММ, т.е. обучить их. Вполне вероятно, что в реальной ситуации обучение придется также проводить на неполных последовательностях, соответственно, необходимо иметь алгоритмы обучения СММ по неполным последовательностям. Тем не менее в данной статье будет рассмотрен только вопрос распознавания неполных последовательностей. Вопрос обучения СММ на неполных последовательностях был рассмотрен автором в предыдущих работах [6, 7, 8], где был предложен алгоритм обучения СММ, основанный на маргинализации пропущенных наблюдений. 2.1. Распознавание неполных последовательностей с помощью маргинализации пропущенных наблюдений Как и ранее, будем называть неполной, или «дефектной», последовательностью такую последовательность O, в которой значение некоторых наблюдений не определено. Обозначим пропуск символом 0 . Тогда O = {ot еR*, t = 1,т}, R* = RZ ^{0}. Для получения алгоритма распознавания неполных последовательностей с помощью СММ необходимо прежде всего обратиться к формулам (29)-(33), по которым производится расчет прямых и обратных вероятностей. Видно, что вычисление значений b (О ) , i = 1, N, t = 1,T, в формулах (29)-(33), которые используются как в алгоритме обучения СММ, так и в алгоритме распознавания последовательностей, невозможно, если ot = 0, где символ 0 означает пропущенное наблюдение, так как не определено конкретное наблюдаемое значение, а значит, нельзя рассчитать значение b (ot) , которое соответствует данному наблюдению. Чтобы можно было использовать эти формулы в случае неполных последовательностей, нужно каким-то образом доопределить значение сомножителя b (0), i = 1, N, для тех прямых вероятностей, которые рассчитываются по отсутствующим в последовательности наблюдениям. a!t(i) = ctat(i), Предлагаемый в данной работе подход состоит в том, чтобы считать, что на месте пропуска могло стоять любое наблюдение из RZ [9]. Руководствуясь этой идеей, представим значение Ь (0), i = 1, N, как интеграл по всем возможным значениям пропущенного наблюдения: b (0) = J b (x) dx = 1, i = 1, N . Справедливость данного равенства обусловлена тем, что в один момент времени имеется только одно наблюдение x, а также тем, что bi(x) - условная плотность распределения наблюдения x в скрытом состоянии Si, i = 1, N. Руководствуясь теми же соображениями, определим значение плотности нормального распределения, входящего в смесь, для наблюдения-пропуска [9]: g(0,hm,) = Jg(x,Vim,)dx = 1, i = 1,N, m = 1,M . Теперь выражение bi(ot), i = 1,N, t = 1,T, определено для всех ot eR*, и формулы (29)-(33) расчета прямых и обратных вероятностей можно расширить на случай неполных последовательностей. Модифицированный алгоритм вычисления прямых вероятностей (отмасштабированный), используемый при распознавании неполных последовательностей: 1) инициализация: О1 = Л: i = 1, N: (0 =' яДЦ), иначе3 i = 1, N, t = 1, T-1. Ё а'(j)aj }=1 О+1 = Ёа'(j )aj j=1 b (oM) иначе, «г О') v ГТ7 7=1,TV, t = 1,7-1 • где a;0)= N Z a, (и) И=1 лю 1 Параметр масштаба вычисляется по формуле: -1 X о, (') • ' - !•/ . Логарифм функции прав i=1 доподобия вычисляется по формуле ln [p (OjX)] = -£ ln с, . t=1 Назовем описанный выше прием доопределения неизвестных величин «маргинализацией пропущенных наблюдений», так как здесь вычисляется маргинальное распределение b (0) , i = 1, N, для случайной величины 0, которая может принимать любое значение из множества RZ. Легко видеть, что с помощью процедуры маргинализации можно проводить распознавание неполных последовательностей по критерию МФП, поскольку необходимые формулы для вычисления логарифма функции правдоподобия доопределены на случай пропущенных наблюдений. 2.2. Распознавание неполных последовательностей в пространстве первых производных от логарифма функции правдоподобия Распознавание последовательностей, описываемых СММ, можно проводить не только с помощью критерия максимума функции правдоподобия. Ранее был разработан и успешно применен метод распознавания последовательностей в пространстве первых производных от логарифма функции правдоподобия того, что случайный процесс, описываемый СММ, сгенерировал распознаваемую последовательность, по различным параметрам СММ. Данный метод распознавания показал преимущество над критерием МФП в случаях близости СММ, описывающих классы, по параметрам, а также в условиях, когда СММ обучались на последовательностях, подверженных разного рода помехам [3]. Тем не менее случая полностью пропущенных наблюдений в последовательностях в данном исследовании не рассматривалось. Поскольку пропуски в наблюдениях также можно интерпретировать как своего рода помехи, то целесообразно исследовать применимость данного метода к анализу неполных последовательностей, описываемых моделями, обученными на неполных последовательностях. Далее приведено описание упомянутого выше метода. Для наглядности рассмотрим случай двух-классовой классификации. Для каждой последовательности наблюдений O принадлежность к одной из двух моделей будем определять с помощью значений производных по различным параметрам модели. {12 K) O , O ,..., O } и две СММ Xi и X2. Для каждой обучающей подInpjOW) ■ дп Ц д In p(O|X2) следовательности O из {O1, O3,..., OK } будет построен вектор вида I } д ш p(O|^2 дп ванные версии этих векторов объединяются вместе в обучающую матрицу X, в которой столбцы соответствуют признакам (производным по параметрам моделей), а строки - последовательностям наблюдений. Также составляется вектор правильных ответов Y = {y,...,yK} , где yK ^{1,2} - это номер СММ, которая соответствует случайному процессу, породившему Ok, k = 1, K . Затем производится обучение классификатора по методу опорных векторов с помощью обучающей матрицы X и вектора правильных ответов Y. Для распознавания строится аналогичный вектор для рассматриваемой последовательности O и определяется, к какой группе этот вектор ближе по методу опорных векторов [10]. Описанный двухклассовый случай легко обобщить на многоклассовый случай, используя стратегии «каждый против каждого» или «один против всех», часто применяемые для бинарных классификаторов. Далее приводится способ вычисления производных от логарифма функции правдоподобия по параметрам СММ [3]. Исходя из формулы (33), . Транспонирод In p(O|X)=_ K v-1 ck дп, дП k=1 Вычисление производной от параметра масштаба по некоторому параметру модели п производится следующим образом: дп г=1 дп Для вычисления г- _ ^ д.^ продифференцируем по шагам алгоритм вычисления прямых дп переменных с масштабом: Шаг 1: 8Ш=Ё*М1г 1 = Щ (36) дп д^П Г t 1 дск Л Z- ' (34) Шаг 2: Sat-1 (j) дп b (t )+i( N) aji )д^, даД О дп N Е j=1 n aji +aJ-( J )■ (37) дп ^kW-^La ГЛ + где ---+ дц дц da tA{j) - - -i = t = 2,T. дц dat(i) . Таким образом, для вычисления значений -, i = 1, Л', нам потребуется вычислить производдп да ные дп дп дп В случае недиагональной матрицы при вычислении производной по элементу ковариационной матрицы придется дифференцировать элементы обратной матрицы, поэтому будем рассматривать случай, когда матрицы Eim, i = 1, N, m = 1, M являются диагональными. ТТ Л За, (0 дЪЛ0 Sa-,- Далее приведен способ вычисления производных --- 5 -i--- 5 -J- для указанных значении дп дп дп параметра п (параметр п может принимать значения щ, ajj, xim, Rzim, Em, i, j = 1, N, m = 1, M, z = 1, Z ): да®. Jb> (1)i = j j=17N, (38) (39) (40) (41) (42) (43) дп j [0, i * j, j 3b, (t) 3п i Sa^i) да дЬ (t) S%1 3a„ i,i1 = 1,N, t = 1,T, m = 1,M, = 0, i, j = 1, N, t = 1,T, = 0, i, i1, j1 =1, N, ад = 0, i,ij, j1 = 1,N, t = 1,T, ("1, x = aij, i, j = 1, N, 3x I 0, x * atl дЬ(0= jg(Ot;Rm,lim), i = 4J, 44_TTr * -Гт ™_ГТ7 дт_ |0, i * i зь,- (1) . . П,-^^, i = i Sa^i) _ St,-„, Si,i,^ = 1,N, m = 1,M, (44) 0 i * i 1' Ot - Rim i = i 0,55Timg(Of ^Rim, Eim ) Sbi (t) Sr Timg(Ot ;Rim, Eim) „zz , i iJ, i,i1 = 1,N, t = 1, T, m = 1,M, z = 1, Z, (45) i,m 0 Sa1(i) _ Sr Sbi (t) SE ZZ, Zm A 0,5Timg (O ;Rim, Eim ) 0, Sbi (1) . . П--, i = i1, sRZm 0, i * i i,i1 = 1,N, m = 1,M, z = 1, Z, (46) 1' 2 Л 1 i = i i,i1 = 1,N, t = 1,T, m = 1,M, z = 1,Z, (47) i * i ( 2 2 \ Ot - Rim yZZ V Eim У db, (1) . . П--, i = и dZffJ 1 i, i1 = 1, N, m = 1,M, z = 1,Z. (48) 0, i £ ij, Формулы (34)-(48) можно доопределить на случай неполных последовательностей, воспользовавшись приемом маргинализации пропущенных наблюдений, описанным в предыдущем подразделе. Таким образом, в формулах (34)-(48) будем считать b,(0) = 1, i = 1,N, а g(0,ц;ш,2im) = 1, i = 1,N, m = 1,M , где символ 0 означает пропущенное наблюдение. К тому же будут внесены дополнительные изменения в формулу (45): Sa1 (i) SZ f 0,5Timg(ot,Zm ) Ot - м™ i = i1 и ot £! Sbt(t) Zz - < иначе, 0, i,ij = 1,N, t = 1,T, m = 1,M, z = 1, Z, и формулу (47): / Л 2 • z z » O - H-im у ZZ v Zim у 0,5Xfmg (Ot '^im' Zim ) i = ^ и ot =£0, 2 32 f„ иначе, 0, i, i = 1, N, t = 1,T, m = 1, M, z = 1, Z . 3. Результаты вычислительного эксперимента В данном разделе разработанный метод распознавания неполных последовательностей в пространстве первых производных от логарифма функции правдоподобия сравнивается с методом распознавания неполных последовательностей с помощью маргинализации пропущенных наблюдений. В качестве истинных СММ были взяты модели Xi и X2 со следующими характеристиками. Число скрытых состояний N = 3, количество компонент в смесях M = 3. Размерность векторов наблюдений Z = 2. Вектор распределения начального состояния: П = [1,0,0], матрица вероятностей переходов: "0,1 + ДА 0,7-ДА 0,2 А = 0,2 0,2 + ДА 0,6-ДА 0,8-ДА 0,1 0,1 + ДА веса компонентов смесей: Г0,3 + Дт 0,4 -Дт 0,3 ^ , i = 1, N, m = 1, M } 0,3 0,4 + Дт 0,3 -Дт 0,3 -Дт 0,4 0,3 + Дт V ' ' 'У (номеру строки соответствует номер скрытого состояния, а номеру столбца - номер компоненты смеси), векторы математических ожиданий компонент смесей: 1, M (0-Дм 0 + Дц)т (1 -Дм 1 + Дц)Т (2-Дм 2 + Дц)?Л (3-Дм 3 + Дм)Т (4-Дм 4 + Дм)Т (5-Дм 5 + Дм)Т (6-Дм 6 + Дм)T (7-Дм 7 + Дм)T (8-Дм 8 + Дм)т V У (номеру строки соответствует номер скрытого состояния, а номеру столбца - номер компоненты смеси), все ковариационные матрицы компонент смесей {2,от , i = 1, N, m = 1,M j были выбраны диагональными, значения всех элементов на диагонали были равны 0,1 + Ас. При этом у первой модели i = 1, N, m = ДА = 0, At = 0, Дц = 0, До = 0, а у второй модели ДА = 0,05, Дт = 0,05, Дц = 0,01, До = 0,01. Такой выбор параметров максимально усложняет задачу распознавания, поскольку случайные процессы, описываемые такими моделями, очень близки по свойствам и порождаемые ими последовательности трудно различить. С помощью каждой из моделей ^ и Х2 было сгенерировано K = 100 обучающих и тестовых последовательностей длиной T = 100, причем каждая из последовательностей содержала G пропусков (число G изменялось от 0 до 90 в ходе эксперимента) в случайных местах. С помощью обучающих неполных последовательностей были получены оценки моделей ^ и по алгоритму обучения СММ по неполным обучающим последовательностям, основанному на маргинализации пропущенных наблюдений [6, 7, 8]. Также с помощью производных от обучающих последовательностей и оценок СММ был обучен классификатор метода опорных векторов, гиперпараметры которого подобраны с помощью кросс-валидации по четырем блокам. Затем с помощью ^ и проводилось распознавание неполных тестовых последовательностей с помощью метода маргинализации пропущенных наблюдений по критерию максимума функции правдоподобия (сплошная линия) и с помощью первых производных от логарифма функции правдоподобия, используя метод опорных векторов в качестве классификатора (рис. 1, штриховая линия), причем использовались производные по всем параметрам моделей. Фиксировался процент верно распознанных последовательностей. На рис. 1 приведены усредненные результаты после 50 запусков описанного выше эксперимента с различными начальными значениями генератора случайных чисел. Маргинализация Производные Рис. 1. Зависимость процента верно распознанных тестовых последовательностей от доли пропусков в обучающих и тестовых последовательностях Как видно, метод распознавания, основанный на производных, начинает превосходить метод, основанный на маргинализации пропущенных наблюдений, начиная примерно с 20% пропусков в обучающих и тестовых последовательностях. При этом преимущество метода на основе производных увеличивается с увеличением процента пропусков, достигая 10% при 90% пропусков в последовательностях. Заключение В данной статье был предложен метод распознавания неполных последовательностей, который заключается в классификации последовательностей в пространстве признаков, образованном первыми производными от логарифма функции правдоподобия того, что случайный процесс, описываемый скрытой марковской моделью, сгенерировал распознаваемую неполную последовательность. Сравнительный анализ предложенного метода и разработанного автором ранее метода распознавания неполных последовательностей, основанного на маргинализации пропущенных наблюдений, показал, что предложенный метод позволяет достичь большего процента верно распознанных последовательностей, чем метод маргинализации, начиная с некоторого (в проведенном эксперименте - более 20%) процента пропусков в обучающих и тестовых последовательностях. Таким образом, предложенный метод может быть рекомендован к применению в условиях сильных помех, когда имеется много пропущенных данных, однако распознавание неполных последовательностей все же необходимо проводить.

Ключевые слова

скрытые марковские модели, машинное обучение, последовательности, пропущенные наблюдения, неполные данные, hidden Markov models, machine learning, sequences, missing observations, incomplete data

Авторы

ФИООрганизацияДополнительноE-mail
Уваров Вадим ЕвгеньевичНовосибирский государственный технический университетаспирант кафедры теоретической и прикладной информатикиuvarov.vadim42@gmail.com
Всего: 1

Ссылки

Baum L.E., Petrie T. Statistical inference for probabilistic functions of finite state Markov chains // The Annals of Mathematical Statistics. 1966. V. 37. P. 1554-1563.
Упоминания ключевого слова «hidden Markov models» между 1800 и 2008 годами : данные из Google Ngram Viewer. URL: http ://tinyurl.com/ gmq5 snv
Gultyaeva T.A., Popov A.A., Kokoreva V.V., Uvarov V.E. Classification of observation sequences described by Hidden Markov Models // Proc. of the Int. Workshop Applied Methods of Statistical Analysis Nonparametric approach AMSA-2015. Novosibirsk, Belokuriha, 14-19 Sep. 2015. P. 136-143.
Rabiner L.R. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition // Proc. of the IEEE. 1989. V. 77. P. 257-285.
Baum L.E., Egon J.A. An inequality with applications to statistical estimation for probabilistic functions of a Markov process and to a model for ecology // Bulletin of the American Meteorological Society. 1967. V. 73. P. 360-363.
Попов А.А., Гультяева Т.А., Уваров В.Е. Исследование подходов к обучению скрытых марковских моделей при наличии пропусков в последовательностях // Обработка информации и математическое моделирование : материалы Рос. науч.-техн. конф. Новосибирск, 21-22 апр. 2016. С. 125-139.
Popov A., Gultyaeva T., Uvarov V. A comparison of some methods for training hidden Markov models on sequences with missing observations // Proc. of 11th Int. Forum on Strategic Technology IF0ST-2016. 2016. V. 1. P. 431-435.
Попов А.А., Гультяева Т.А., Уваров В.Е. Исследование методов обучения скрытых марковских моделей при наличии пропусков в последовательностях // Актуальные проблемы электронного приборостроения (АПЭП-2016) : труды XIII международной конференции : в 12 т. Новосибирск, 2016. Т. 8: Моделирование и вычислительная техника. Информационные системы и технологии. С. 149-152.
Cooke M., Green P., Josifovski L., Vizinh A. Robust automatic speech recognition with missing and unreliable acoustic data // Speech Communication. 2001. V. 34, No. 3. P. 267-285.
Boser B.E.; Guyon I.M., Vapnik V.N. A training algorithm for optimal margin classifiers // Proc. of the fifth annual workshop on Computational learning theory - COLT '92. 1992. P. 144.
 Распознавание неполных последовательностей, описываемых скрытыми марковскими моделями, в пространстве первых производных от логарифма функции правдоподобия | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. DOI: 10.17223/19988605/42/9

Распознавание неполных последовательностей, описываемых скрытыми марковскими моделями, в пространстве первых производных от логарифма функции правдоподобия | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. DOI: 10.17223/19988605/42/9