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

Практические применения аппарата СММ основано на методах решения трех следующих проблем:

1.Распознавание речевого высказывания, моделируемого СММ

2.Сегментация (Алгоритм Витерби)

3.Обучение (оценка параметров) СММ по выборке данных

91

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

Распознавание

Пусть Марковская цепь первого порядка из N состояний

aij

P[qt

j | qt

1 i],1 i, j N

задается переходными вероятностями

, вектором начальных вероятностейP[q s ], 1 i N

,

и

i

1

i

вероятностями порождения наблюдаемых символов

bj

(k) P[ot

vk

| qt

j], 1

j

N, 1

k

M

O. (o1 ,o2 ,...,oT )

. Все это – модель

T

t

t

Для любой последовательностиP(O | q, с)конечнымP(o | qчислом, )

состоянийP(O | q, ) bq (o1 ) bq

(o2 ) ... bq

(oT )

t 1

1

,

2

T

вероятность генерации O Марковской

P(q | )

q

aq q

aq

q

...aq

q

цепью может быть вычислена как

P(O | )

1

1 2

2

3

T 1

T

,

P(O, q

| )

P(O | q, )P(q |

)

P(O | q, )P(q | )

илиq

q

1

q q

b

q

2

)...a

q

q

b

q

T

)

по всем q

b

1

(o )a

1 2

2

(o

T 1

T

T

(o

1

. Вероятность

q1 ,q2 ,...,qT

88

последовательности состояний q -

.

, а

Тогда

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

Прямая процедура вычисления

1. Инициализация

1 (i) i bi (o1 )	1 i N
2. Индукция				1 t T 1
N
t 1 ( j) t (i)aij		bj (ot 1 )		1 j N
i 1
3. Завершение
N
P(O | ) T (i)
i 1					ij	- вероятность
Здесь произведение t			(i)a
совместного
				o1 , o2		,...,ot	в момент времени
появления наблюдений
t и
достижения состояния j в момент времени (t+1)
через				(времениo )			t . Суммируем t 1	( j)
состояние i в моментb									88
произведение			j		t 1

по всем возможным в момент времени t состояниям

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

Прямая процедура вычисления

88

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

Алгоритм Витерби

Нахождение наилучшей единственной
	q (q , q				,..., q		T	)			для
последовательности состояний			1	2						)
		O (o ,o				,...,o			T
данной последовательности наблюдений1 2
. Для этого определяется предыдущее значение
вероятностиt ( j) max P(q1q2 ...qt 1 , qt i,o1 ,o2 ,...,ot		| )
q1 ,q2 ,...,qt 1										,
наибольшее значение вероятности вдоль некоторого
пути в момент t, которое вычислено для первых t
наблюденийt 1 t иij закончившеесяj t 1		в состоянии i. По
( j) max (i)a	b (o )
индукции
i
	( j)	. Для нахождения
				состояний
оптимальной последовательностиt
необходимо сохранять путь, который максимизирует 88
это выражение. Для этого вводится массив											.

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

Алгоритм Витерби

1.	Инициализация					(i) 0
	1(i) ibi (o1) 1 i; N				1
							;
2.	Рекурсия	(i)aij		bj (ot ) t ( j) arg max				t 1 (i)aij		2 t T
	t ( j) max t 1									1 j N
	1 i N						; 1 i N
3.P*Завершениеmax T (i) q *T arg max							T (i)
	1 i N	;		1 i N				;
4.
	Запоминание пути
	q *t t 1 (qt 1 )	t T		1,T 2,...,1

88

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

Оценка параметров

Введем величину t					(i, j)		- вероятность нахождения в
состоянии i в момент времени t, и в состоянии j в
момент времени t+1, при условии наличия данной
модели			и конкретной последовательности
состояний(i, j) P(q				O. i,Тоq	есть:j | O, )
е			t	t	1					, тогда:
		P(qt i, qt 1			j,O, )
t (i, j)								t (i)aij bj (ot 1 ) t 1 ( j)
				P(O | )						P(O | )
			t (i)aij bj (ot 1 ) t 1 ( j)							.
		N	N
		t (i)aij bj (ot 1 ) t 1 ( j)
		i 1	j 1

88

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

Оценка параметров

Тогда вероятность нахождения в состоянии i в момент

	времени t, при условии последовательности
	наблюдений O и модели как:
				N
	t (i) t (i, j)					.
	T 1			j 1
		t		(i)	- ожидаемое число переходов из
	состояния i в
	t 1				случае последовательности наблюдений
	T 1
	t
	O.			(i, j)

t 1

- ожидаемое число переходов из	88
состояния i в
состяние j в случае

последовательности

, либо

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

Оценка параметров

И, наконец, новые значения модели:

aij

b

j 1 (i)

T 1

t (i, j)

t 1

T 1

t (i)

t 1

T

t ( j)

t 1

j (k) ot vk T

t ( j)

t 1

Далее, либо процедура

продолжается (в том смысле,P(O | ) чтоP(O | )

).

88

Стандартный СММ распознаватель

•Включает предобработку, сегментацию,
ЛПК-анализ и векторное квантование
•Тестовая последовательность уменьшается
до наблюдаемой последовательности {O},
состоящей из кодов векторов кодовой книги,
которые наилучшим образом соответствуют
ЛПК-векторам последовательности
•Алгоритм Витерби определяет для каждого
индивидуального слова СММ, вероятность
того, что наблюдаемая последовательность
была сгенерирована данным словом СММ
•Решающее правило или выбирает слово,
чья модель имеет наибольшую вероятность,
как распознанное слово, или выдает
перечень кандидатов слов, упорядоченный
по их вычисленной вероятности	92