Решение задачи 1, распознавание

Наиболее простое решение состоит в том, чтобы посчитать вероятность появления последовательности наблюдений для каждой возможной последовательности состояний модели, а затем сложить эти вероятности. Пусть Q={Q₁,Q₂,…Q_s}- множество всех возможных последовательностей состояний той же длины, что последовательность O. Их число будет равно S=N^τ -1, где N – число состояний, τ – длина последовательности. Пусть i-я последовательность Q_i представляет ряд состояний {q_i1,q_i2,…,q_iτ}. Тогда для i-й последовательности состояний вероятность появления последовательности наблюдений O равна:

	τ		τ
P(O|Qi,λ)=	∏	P(oj|qij,λ)=	∏	bqij(oj)
	j=1		j=1

Вероятность же появления самой i-й последовательности состояний равна

	τ
P(Qi|λ)=πqi1	∏	a[qi,j-1,qi,j]
	j=2

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

	N^τ-1		N^τ-1		τ
P(O|λ)=	∑	P(O|Qi,λ) P(Qi|λ)=	∑	(πqi1 bqi1(o1)	∏	a[qi,j-1,qi,j] bqij(oj))
	i=1		i=1		j=2

Очевидно, что нам потребуется (2τ -1) N^τ умножений и N^τ -1 сложений, что уже для N=10 состояний и длины последовательности наблюдений τ=10 дает число вычислений, равное 19*10¹⁰+10¹⁰-1=2*10¹¹-1. Это очень много. К счастью, существуют более эффективные алгоритмы решения этой задачи. Наиболее известны два – алгоритм прямого хода и алгоритм обратного хода.

 

Алгоритм прямого хода.

Вводится переменная α_t(i) – вероятность того, что к моменту времени t система будет находиться в i-м состоянии, а последовательность порожденных ею до этого момента наблюдений равна о₁,о₂,…,o_t.

Алгоритм следующий.

1 шаг. Для всех i от 1 до N

α₀(i)=π_i b_i(o₁)

 

2 шаг. Для всех t от 1 до τ и для всех j от 1 до N

	N
αt(j) =[	∑	αt-1(i)aij] bj(ot)
	i=1

 

3 шаг.

	N
P(O|λ)=	∑	αt(i)
	i=1

 

Алгоритм обратного хода.

Вводится переменная τ_t(i) – вероятность того, что к моменту времени t система будет находиться в i-м состоянии, а последовательность порожденных ею после этого наблюдений равна о_t+1, о_t+2,…o_τ-1,o_τ

Алгоритм следующий.

1 шаг. Для всех i от 1 до N

β_τ(i)=1

 

2 шаг. Для всех t, идущих в обратном порядке от τ-1 до 1 и для всех i от 1 до N

	N
βτ(i)=	∑	aij bj(ot+1) βτ+1(j)
	j=1

 

3 шаг.

	N
P(O|λ)=	∑	πi bi(o1) β1(i)
	i=1

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

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

Построив кодовую книгу, мы должны настроить модель распознавания. Одна скрытая модель Маркова λ={A,B,π} ставится в соответствие некоторой распознаваемой единице речи, как правило, слову.

Фрагмент речи разбивается на отрезки, в течении которых параметры речи можно считать постоянными. Для каждого отрезка вычисляются характерные признаки и подбирается запись кодовой книги с наиболее подходящими характеристиками. Номера этих записей и образуют последовательность наблюдений O={o₁,o₂,…o_τ} для модели Маркова. Каждому слову словаря соответствует одна такая последовательность. Далее A – матрица вероятностей переходов из одного минимального отрезка речи (номера записи кодовой книги) в другой минимальный отрезок речи (номер записи кодовой книги). В – вероятности выпадения в каждом состоянии конкретного номера кодовой книги. В нашем случае?i=1 при i=0,?i=0 при i>0.

На этапе настройки моделей Маркова мы применяем алгоритм Баума-Уэлча для имеющегося словаря и сопоставления каждому из его слов матрицы A и B.

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