Кельберт М.Я., Сухов Ю.М. Вероятность и статистика в примерах и задачах. Том 2. Марковские цепи как отправная точка теории случайных процессов и их приложения

Подождите немного. Документ загружается.

520 Глава 3. Статистика цепей Маркова с дискретным временем

сти для неслучайной модели (вариант а)), 4 возможности для наполовину

случайной модели (вариант б)) и (по существу) одна возможность для

полностью случайной модели (вариант в)). У вас есть также основания

верить, что цепь стационарна, т. е.

—

это инвариантное распределение

= (

3, 1

)

В итоге переходная матрица P определяется параметром p, пробега

ющим отрезок [0, 1

2], а для q мы имеем возможности, указанные выше,

а именно а), б) и в). Тройка ( , P, b) в контексте этого примера рассмат

ривается как

модель

; если функция b случайна, то, возможно, удобнее

говорить о тройке ( , P, Q), где Q представляет набор вероятностей для

случайных величин b(X

), . . . , b(X

Например, состояния A, B и C могут соответствовать определенным

согласным звукам в (идеализированной) задаче автоматического распозна

вания речи. Некоторые из этих согласных могут быть распознаны четко,

в то время как другие труднее по их спектрограммам отделить одну от

другой.

Предположим, что вы хотите сравнить два отдельных семейства моде

лей:

а) семейство моделей с детерминированной (т. е. неслучайной) функци

ей b, обозначенной Z

дет

= (

P, b

дет

)

, где

дет

(A)

дет

(B)

1 и b

дет

(C)

и б) полностью случайную модель, обозначенную Z

сл

( , P, Q), где

сл

(

)

(

1 с вероятностью q

0 с вероятностью 1

−

? =

A, B, C независимо друг от друга

и q

, q

Итак, вычислим суммарные функции правдоподобия:

дет

( ; Z

дет

)

−

[1(

1, x

A или B)

0, x

C)]

(3.7.1)

сл

( ; Z

сл

)

−

(1(

0) [(1

−

)1(x

A или B)

−

)1(x

C)]

1) [q

1(x

A или B)

1(x

C)]). (3.7.2)

(Мы опустили множитель

в правых частях равенств (3.7.1) и (3.7.2), по

скольку он равен 1

3 и не играет никакой роли в наших рассуждениях и вы

§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей 521

числениях.) Для заданного функция L

дет

—

полином степени n перемен

ной p

∈

[0, 1

2], в то время как L

сл

—

полином от переменных p

∈

[0, 1

и q

, q

∈

[0, 1]. Конечно, если нет дополнительных ограничений на q

и q

, то полином L

сл

—

это продолжение L

дет

(или, если угодно, L

дет

—

это сужение L

сл

, которое получается при q

1, q

0). Однако если

имеются дополнительные условия, например q

, q

∈

−

, q

)

⊂

[0, 1], то

сравнение двух полиномов становится нетривиальным.

Итак, мы максимизируем оба полинома и получаем оптимальные мо

дели

∗

дет

( )

argmax

дет

( ; Z

дет

) и Z

∗

сл

( )

argmax

p, q

сл

( ; Z

сл

). (3.7.3)

Затем мы сравниваем оптимальные значения

дет

( ; Z

дет

) и L

сл

( ; Z

сл

);

максимальное из них определяет лучшую подгонку (для заданной цепоч

ки

). Аналогичную процедуру можно провести для любого варианта из

перечисленных выше типов а)

—

в) функции b.

Замечание 3.7.2. Необходимо принимать во внимание то, что моде

ли со слишком большим числом параметров (например, с произвольной

переходной (s

матрицей P и произвольным семейством вероятностей

Q) могут привести к

чересчур подогнанной

(

overﬁtted

) модели Z

∗

( );

это может породить нежелательную неустойчивость, при которой Z

∗

( )

будет слишком сильно меняться вместе с изменением цепочки

. Поэто

му желательно использовать любую

побочную информацию

, доступную

в возможной модели, и включать ее в задачи максимизации правдоподобий.

Пример 3.7.3. Рассмотрим ц.м.д.в. (X

), с тремя состояниями и пере

ходной (3

матрицей P

). Известно, что диагональные переходные

вероятности нулевые: p

0, i

1, 2, 3. Далее, предположим, что мы

знаем начальное состояние X

1 и состояние X

3, но не знаем

состояний в моменты времени 1, 2 и 3. Запишем суммарную функцию прав

доподобия; в этом примере она равна сумме правдоподобий, подсчитанных

на тех выборочных векторах x









∈ {

1, 2, 3

}

, которые совместимы

с имеющимся ограничением (т. е. с x

1, x

3):

L(P

1, X

(4)

; (3.7.4)

522 Глава 3. Статистика цепей Маркова с дискретным временем

это полиномиальная функция переменных p

. Следуя философии макси

мального правдоподобия, мы должны максимизировать L(P

1, X

3) по P

) на множестве

oﬀ

diag

; см. соотношение (3.1.11). Оценка

максимального правдоподобия P

∗

мп

может быть получена во внутренней

точке или на границе. В общем случае задача отыскания точной о.м.п.

становится сложной с вычислительной точки зрения; вмешиваются и дру

гие факторы, поэтому желательно иметь в своем арсенале

приемлемые

приближенные методы.

Как будет показано, задача построения приближения оценки пере

ходных вероятностей p

, 1

i, j

3, может быть (корректно) решена

с помощью итераций некоторого преобразования. Более точно, положим

∂

L(P

1, X

, 1

i, j

3. (3.7.5)

где знаменатель задается формулой

1, X

∂

L(P

1, X

. (3.7.6)

В частности,

1, X

и т. д. Итерации этого преобразования задают решение с допустимой точ

ностью.

В примерах 3.7.1 и 3.7.3 намечены основные направления нашего ис

следования. См. также [K]. Одно направление относится к

зашумленным

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

принимаемые цепью, но сами состояния подвержены шуму, который при

водит к их искажению. Этот случай можно назвать задачей фильтрации

с.м.м. Второе направление соответствует случаю, когда цепь доступна для

наблюдения только в некоторые избранные моменты времени. Этот слу

чай назовем задачей интерполяции с.м.м. Методы, используемые в этих

случаях, имеют сходство, но в то же время и различаются в некоторых

существенных аспектах.

§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей 523

Рассмотрим вначале общую постановку задачи фильтрации с.м.м. Нам

задан вектор наблюдаемых значений









, называемый обучаю-

щей последовательностью или обучающей выборкой, где

, . . . ,

принимают значения в множестве

{

1, . . . ,

κ}

. Это означает, что мы знаем,

что произошло событие

{

b(X

), . . . ,

b(X

)

}

. Однако b остается

неизвестной функцией

{

1, . . . , s

} → {

1, . . . ,

κ}

, возможно, случайной.

Более точно, предположим, что для любого x

значения b(X

) условно независимы при заданном X

x, (3.7.7)

и положим

P (b(X

)

, j

1, . . . , s, k

1, . . . ,

, (3.7.8)

где q

1 для всех j

∈

I. Неслучайная функция b появляется,

когда q

равны 0 или 1 (понятно, что не более одного q

может быть равно

1 для заданного j). В случае безошибочного наблюдения мы имеем s

= κ

и q

. Совокупность вероятностей q

обозначим Q (по способу своего

задания они образуют стохастическую (s

×κ

)

матрицу). Будем называть их

вероятностями шума. Тройку ( , P, Q) назовем (скрытой марковской)

моделью (с шумом, не имеющим памяти) и обозначим, как и прежде, Z.

Предположим, что задано множество

моделей (т. е. троек Z

( , P, Q)), и весь анализ проводится на этом множестве

Наиболь

шее

такое множество соответствует ситуации

без ограничений

Задача фильтрации с.м.м. (также известная из литературы как задача

обучения, или оценивания для с.м.м. с шумом) состоит в том, чтобы найти

наиболее правдоподобную

модель Z

∗

(

∗

, P

∗

, Q

∗

), максимизирующую

суммарную функцию правдоподобия L( ; Z) по Z

∈ Z

для заданного :

; Z) :

P (b(X; Z)

)

P (X

x; Z)

i i

0 0

−

i i

. (3.7.9)

Здесь и ниже P (

; Z) означает распределение вероятностей, порожденное

моделями Z (т. е. ц.м.д.в. (

, P), соответствующей выборке X и независи

мым наблюдениям b(X

) с вероятностями шума Q

)). Иногда будем

использовать также альтернативное обозначение P

524 Глава 3. Статистика цепей Маркова с дискретным временем

Таким образом, нас интересует тройка Z

∗

МП

= (

∗

МП

, P

∗

МП

, Q

∗

МП

)

, за

данная соотношением

∗

МП

argmax

∈Z

(

b(X)

; Z

)

, (3.7.10)

где b(X) обозначает (случайный) вектор





b(X

)

b(X

)





. (Индекс МП соответ

ствует максимуму правдоподобия.)

На практике отыскание точки максимума Z

∗

в соотношении (3.7.10)

часто является затруднительным, особенно когда числа s и

велики,

а на множество

налагаются многочисленные ограничения. Поэтому

существует обширная литература, посвященная обсуждению различных

алгоритмических методов, задающих аппроксимации значения Z

∗

. Этот

вопрос мы обсудим как в данном, так и в следующем параграфах.

Пример 3.7.4. Задача фильтрации с.м.м. без ограничений возникает,

когда пара (

, P) пробегает множество

, определенное равенством (3.1.5),

а матрица Q

—

множество

размерности s(

κ −



) : q



Соответственно положим

U = R

× P

= Λ

× P

(3.7.11)

и примем во внимание, что задача без ограничений соответствует Z

∈ U

Задача фильтрации стационарной с.м.м. без ограничений будет соответ

ствовать паре ( , P) с матрицей P, пробегающей множество

из соот

ношения (3.1.8), и с матрицей Q, пробегающей множество

В задаче без ограничений множество

можно снабдить метрикой (рас

стоянием), полагая

dist(Z, Z

)



(

−

)

i,j

−

)

j,k

−

)



где Z

( , P, Q), Z

(

, P

, Q

) и

(

), P

), Q

(

), P

), Q

). Иными словами, это евклидова метрика

в пространстве

s(s

+κ

)

, суженная на

. Мы используем эту метрику

в § 3.9.

§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей 525

Пример задачи фильтрации с.м.м. с ограничениями возникает, когда

матрица P пробегает множество

oﬀ

diag

из равенства (3.1.11) или множе

ство

симм

из равенства (3.1.12). В первом случае

Z = Λ × P

oﬀ

diag

×P

а во втором

Z = Λ ×P

симм

× P

Мы будем работать с выборочными векторами x









, имеющими

положительные вероятности P (X

x; Z), при заданной модели Z; а есте

ственным предположением, которому мы будем везде следовать, будет то,

что множество этих векторов

X ⊆

одно и то же для всех рассматри

ваемых моделей Z

∈ Z

. Например, рассмотрим вышеупомянутую задачу

фильтрации с ограничениями, где P

∈ P

oﬀ

diag

, т. е. случай, когда переходная

матрица P

) ц.м.д.в. не позволяет повторять состояния подряд (это

значит, что p

0 для любых состояний i

1, . . . , s), но позволяет любые

другие переходы для любой модели Z

( , P, Q)

∈ Z

(см. пример 3.7.3.

В этом случае

состоит из всех векторов x

∈

с x

−

, i

1, . . . , n.

Более того, предположим, что для любой модели Z

∈ Z

и любой

обучающей последовательности

, появившейся в виде значения b(X) (т. е.

P (b(X)

; Z)

0), выполнено условие

P (X

b(X)

; Z)

0 тогда и только тогда, когда x

∈ X

. (3.7.12)

Далее, положим t

= #X

. Удобно пронумеровать цепочки x

∈

X номе

рами l

1, . . . , t (в любом порядке) и записать x(l)





(l)





для l

цепочки. Тогда при заданном Z

( , P, Q) положим

( ; Z)

P (b(X)

, X

x(l); Z)

(l)

−

(l)x

(l)

. (3.7.13)

Таким образом, u

( ; Z) задает вероятность пересечения

{

x(l)

} ∩{

b(X)

= }

в модели Z.

Теорема 3.7.5. Предположим, что заданы такая модель Z

∈ U

и такая обучающая последовательность , что u

( ; Z)

0 хотя

бы для одного l (т. е. выполнено неравенство P (b(X)

; Z)

0).

Тогда при условии (3.7.12), для любой модели

∈ U

выполняется

526 Глава 3. Статистика цепей Маркова с дискретным временем

неравенство

P (b(X)

;

P (b(X)

; Z)

U(Z, Z; )

−

U(Z,

Z; )

P (b(X)

; Z)

, (3.7.14)

где

U(Z, Z;

)

[

−

( ; Z) ln u

( ; Z)] (3.7.15)

U(Z,

Z; )

[

−

( ; Z) ln u

( ;

Z)]. (3.7.16)

Мы следуем здесь соглашению о том, что

−

( ; Z) ln u

( ; Z)

0, если u

( ; Z)

−

( ; Z) ln u

( ;

= +∞

, если u

( ; Z)

0, но u

( ;

и, таким образом, все слагаемые в суммах из соотношений (3.7.15),

(3.7.16) неотрицательны.

Д о к а з а т е л ь с т в о немедленно следует из примера 3.6.7 при n

t, a

, b

. Действительно, условие теоремы эквивалентно

неравенству

−

ln u

)



где u

( ; Z) и

( ;

Z).

Значит, если для заданного и Z можно найти модель

Z, для которой

правая часть неравенства (3.7.14) положительна, то получим

улучшен

ную

модель в смысле большего значения правдоподобия.

Таким образом, нас интересует задача минимизации функции

U(Z,

Z; ), определенной в соотношении (3.7.16), по переменным

∈ Z

для заданной модели Z

∈ Z

и заданной обучающей последовательности

. В общем случае минимизатор, конечно, будет зависеть от Z и (и от

выбора множества

§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей 527

Для решения этой задачи удобно использовать матрицу подсчета пе

реходов. Как и в § 3.4, при заданных i, j

1, . . . , s и l

1, . . . , t пусть

(l)

—

это число переходов i

→

j в цепочке x(l):

(l)

1(x

−

(l)

i, x

(l)

j). (3.7.17)

Далее, положим

(l)

1(x

(l)

j). (3.7.18)

Кроме того, при заданной обучающей последовательности

и k

1, . . . ,

обозначим через n

(l) (

(l, )) число моментов времени, в которые

в цепочке x(l) было зафиксировано значение k при истинном состоянии j:

(l)

1(x

(l)

k). (3.7.19)

Наконец, обозначим

(l), c

(l) и d

(l); (3.7.20)

здесь мы вновь записываем u

( ; Z) для модели Z

( , P, Q)

∈ Z

Таким образом, e

, c

и d

являются функциями модели Z и последова

тельности

Возвращаясь к соотношению (3.7.16), перегруппируем слагаемые в вы

ражении для U(Z,

Z; ) согласно появлениям начальных состояний i,

переходам i

→

j и зафиксированным значениям k. В результате получаем,

что для

(

Q) имеют место равенства

U(Z,

Z; )



−

(l)

−

(l) ln

−

(l) ln



= −

−

. (3.7.21)

Единственный глобальный минимум по

Z выражения в правой части

равенства (3.7.21) достигается в точке

∗

(

∗

), где

(

∗

(

∗

) и

∗

(

∗

) задаются формулами

∗



, j

1, . . . , s, (3.7.22)

528 Глава 3. Статистика цепей Маркова с дискретным временем

∗



, i, j

1, . . . , s (3.7.23)

∗



, j

1, . . . , s, k

1, . . . ,

. (3.7.24)

Читатель должен иметь в виду, что вероятности

∗

являются

функциями модели Z и последовательности

Значит, если модель

∗

принадлежит

, то она обеспечивает

усовер

шенствование

модели Z в этом классе. Например, в примере 3.7.3, где

переходная матрица P имеет все нулевые диагональные элементы p

переходная матрица

∗

(

∗

) из соотношения (3.7.23) сохраняет то же

свойство.

Знаменатели соотношений (3.7.22), (3.7.24) можно упростить. В самом

деле, заметим, что

(l)

P (b(X)

; Z)

(число посещений состояния j до момента времени n),

где E

обозначает математическое ожидание по мере P

. Используя эти

равенства, можно переписать соотношения (3.7.22)

–

(3.7.24) в компактной

форме:

∗

(b(X)

∗



∗

. (3.7.25)

В общем случае нам необходимо решить задачу с ограничениями

минимизировать правую часть (3.7.21) по

Z для заданного Z

при условии, что

∈ Z

. (3.7.26)

Это наводит на мысль о следующем

обучающем

алгоритме: при заданной

начальной модели Z

(0)

∈ Z

и обучающей последовательности решить за

дачу (3.7.26), получив, таким образом, улучшенную модель Z

(1)

∗

∈ Z

§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей 529

Затем повторить это для Z

(1)

и , и т. д. Предположим, что минимизатор

(N)

, полученный в результате N итераций, сходится к пределу:

lim

→∞

(N)

(

∞

)

∈ Z

. (3.7.27)

Тогда Z

(

∞

)

можно рассматривать как

наилучшую подгонку

модели, на

которую способен этот алгоритм.

Возникают следующие вопросы. 1. Существует ли предел Z

(

∞

)

в соот

ношении (3.7.27) (для всех или некоторых начальных моделей Z

(0)

)? 2.

Если предел Z

(

∞

)

в соотношении (3.7.27) существует, совпадает ли он

со значением, где достигается максимум Z

∗

МП

из соотношения (3.7.10)?

Как было отмечено, эти вопросы стали поводом для появления обширной

литературы, охватывающей ряд важных приложений. Некоторые из ре

зультатов в этом направлении обсуждаются в § 3.9. Сейчас мы хотели бы

привести список относящихся к этой теме работ Леонарда Баума, которого

многие считают создателем теории с.м.м. (вместе с Ллойдом Уэлчем):

Baum, L.E. An inequality and associated maximization technique in

statistical estimation for probabilistic functions of Markov processes. In:

Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, CA,

1969; dedicated to the memory of T.S. Motzkin). New York: Academic Press,

1972, pp. 1

–

Baum, L.E., Petrie, T., Soules, G. Weiss, N. A maximization technique

occurring in the statistical analysis of probabilistic functions of Markov chains.

Annals Math. Statist., 41 (1970), 164

–

171.

Baum, L.E., Sell, G.R. Growth transformations for functions on manifolds.

Paciﬁc Journ. Math., 27 (1968), 211

–

227.

Baum, L.E., Eagon, J.A. An inequality with applications to statistical

estimation for probabilistic functions of Markov processes and to a model for

ecology. Bull. Amer. Math. Soc., 73 (1967), 360

–

363.

Baum, L.E., Petrie, T. Statistical inference for probabilistic functions of

ﬁnite state Markov chains. Annals Math. Statist., 37 (1966), 1554

–

1563.

Алгоритм, приведенный выше, называют обучающим алгоритмом

Баума

—

Уэлча; его привлекательность заключается в простоте (а потому

и в практичности) решения задачи (3.7.26) для различных множеств

, что

и продемонстрировали формулы (3.7.22)

–

(3.7.25).

Удобно связать с равенствами (3.7.22)

–

(3.7.25) отображение

U → U

множества

(см. (3.7.11)) в себя

: Z

( , P, Q)

7→

∗

(

∗

), (3.7.28)

которое мы назовем преобразованием Баума

—

Уэлча для фильтрации

(без ограничений). (При этом формулы (3.7.22)

–

(3.7.25) будут переписаны

530 Глава 3. Статистика цепей Маркова с дискретным временем

в различных (эквивалентных) формах, поясняющих различные аспекты

отображения

.) Преобразование

будет особенно полезным для задачи

(3.7.26), где оно переводит изначальное множество моделей

в себя:

(

)

⊆ Z

Вышеупомянутые вопросы 1 и 2 (для задачи фильтрации без ограничений)

касаются итераций

преобразования

. Непосредственным следствием

теоремы 3.7.5 является следующее утверждение

Пример 3.7.6. Докажите, что любая точка Z

∗

МП

, определенная в фор

муле (3.7.10), является неподвижной точкой отображения

∗

МП

)

∗

МП

. (3.7.29)

Решение. В самом деле, если

∗

МП

)

∗

МП

, то P (b(X)

∗

МП

))

P (b(X)

, Z

∗

МП

Chariots of

, Chariots of

(Из серии

Фильмы, которые не вышли на большой экран

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

с ц.м.д.в. (X

) с пространством состояний I

= {

1, . . . , s

}

и матрицей

вероятностей перехода P

). В нашей постановке задачи матрица P

полностью определяет модель; предположим для простоты, что начальное

распределение

известно. Предположим также, что цепь наблюдаема

в (целые) моменты времени 0

. . .

n; обозначим T

= {

, . . . , t

}

. Соответственно пусть X









и x









. При

заданном y









∈

пусть y



обозначает сужение









. Затем

определим суммарное правдоподобие:

L(P

)

∈

−

1(y



)

∈

i,j

1(y



), (3.7.30)

Ср. с названием фильма

Chariots of Fire

§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей 531

где

(y)

1(y

−

i, y

j), r

(y)

1(y

i);

ср. с соотношениями (3.7.17), (3.7.18). Задача интерполяции состоит

в отыскании точек максимума P

∗

МП

(

∗

МП

)) на заданном множестве

Y ⊆ P

(см. (3.1.7)):

∗

МП

argmax

∈Y

L(P

). (3.7.31)

Как и ранее, если

Y = P

, получаем задачу без ограничений, а если

—

правильное

подмножество в

, то речь идет о задаче с ограничениями.

Дальнейшее обобщение (не рассматриваемое здесь) возникнет, если ис

пользовать более общее условие X

∈

, X

∈

, . . . , X

∈

, где A

. . . , A

—

подмножества пространства состояний I.

Здесь мы столкнемся с рядом трудностей, подобных тем, которые воз

никают в задаче фильтрации с.м.м.: точки максимума P

∗

МП

в соотношении

(3.7.31) трудно найти, и они очень чувствительны к выбору множества

содержащего априорную информацию о модели. Поэтому ищется прибли

женное решение, которое может быть получено достаточно явным образом.

Осуществим это построение, определив матрицу

P с элементами

i, j

1, . . . , заданными в виде

∂

L(P

)

∂

L(P

)

, (3.7.32)

где суммарное правдоподобие L(P

) задается формулой (3.7.30).

Очевидно,

P зависит от P и x

P(P, x

). Для заданной выборки x

формула (3.7.32) определяет отображение

(

= Π

)) на множестве

: P

)

7→

(

), (3.7.33)

которое называется преобразованием Баума

—

Уэлча для задачи интерпо

ляции с.м.м.

Здесь уместно сделать два замечания.

I. Предположим, что t

0, t

1, . . . , t

k, т. е. цепь наблюдаема

в последовательные моменты времени 0, . . . , k. Тогда x

становится вы

борочным вектором x









∈

и правая часть равенства (3.7.32)

532 Глава 3. Статистика цепей Маркова с дискретным временем

задает матрицу, которая не зависит от P, а зависит лишь от x

. Более

точно, в этом случае формула (3.7.32) задает вероятности

, равные

эмпирическим (или относительным) частотам

(

)) переходов i

→

в выборке x



)



−

), i, j

1, . . . , s. (3.7.34)

Геометрически это означает, что преобразование

Баума

—

Уэлча перево

дит любую матрицу P

∈ P

в матрицу

(

) эмпирических частот:

(P)

F, P

∈ P

Значит, в этом случае матрица

F является единственной неподвижной

точкой преобразования (3.7.33), и если повторить процедуру (3.7.32) (т. е.

итерировать отображение (3.7.33)), то в результате опять получим матри

цу

II. Если ц.м.д.в. (X

) состоит из н.о.р.с.в., то формула (3.7.32) задает

как эмпирические (относительные) частоты

) посещений

состояния j выборкой x

. Формально





−

, j

1, . . . , s, (3.7.35)

где

)

1(x

j).

В этом случае мы забываем о состояниях, в которых цепь побывала между

точками t

, . . . , t

, и вычисляем частоты посещений каждого состояния

1, . . . , s, основываясь на доступных данных. Иначе говоря, каждая

матрица P

), строки которой являются повторениями фиксированного

стохастического вектора (или, что эквивалентно, элементы которой p

постоянны вдоль каждого столбца), переводится отображением

в мат

рицу

G эмпирических частот

(которая, очевидно, удовлетворяет тому

же свойству). Геометрически это означает, что матрицы

(

) всегда

образуют семейство неподвижных точек преобразования Баума

—

Уэлча

Пример 3.7.7. Докажите замечания I и II.

Решение. Оба равенства (3.7.34) и (3.7.35) получаем из соотношения

(3.7.32) путем дифференцирования.

§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей 533

Примечательно то, что итерации преобразования

из соотноше

ния (3.7.33) ведут к увеличению значения суммарного правдоподобия

L(P

), определенного формулой (3.7.30).

Теорема 3.7.8. Для любой переходной матрицы P

), множе-

ства моментов времени T

= {

, t

, . . . , t

}

, упорядоченных так, что

. . .

n, и любой выборочной цепочки x









имеет место неравенство

(P)

)

L(P

). (3.7.36)

Более того, равенство в (3.7.36) достигается тогда и только тогда,

когда

(P)

Д о к а з а т е л ь с т в о. Основная идея доказательства

—

алгебраиче

ская. При заданном x

функции

7→

L(P

) и P

7→

(P)

)

являются однородными многочленами переменных p

в том смысле, что

оба выражения L(P

) и L(

(P)

)

—

это суммы одно

членов фиксированной (совокупной) степени, равной t

1. Более того,

эти одночлены входят в сумму с коэффициентами 0 или 1 (см. (3.7.30)).

Теорема 3.7.8 будет следствием более общей теоремы 3.7.10, сформулиро

ванной и доказанной далее для таких многочленов. См. вышеупомянутую

статью Л. Баума и Дж. Игона, где такие рассуждения были проведены

впервые.

Прежде чем перейти к теореме 3.7.10, нам хотелось бы обратиться

к знаменитой теореме Эйлера об однородных функциях. Функция n дей

ствительных переменных f(x

, x

, . . . , x

) называется однородной сте-

пени d, если для любого действительного a выполняется равенство

f(ax

, ax

, . . . , ax

)

f(x

, x

, . . . , x

). (3.7.37 а)

Теорема Эйлера утверждает, что для любой дифференцируемой однородной

функции справедливо равенство

∂

df. (3.7.37 б)

Пример 3.7.9. Предполагая наличие свойства (3.7.37 а), докажите ра

венство (3.7.37 б).

534 Глава 3. Статистика цепей Маркова с дискретным временем

Указание. Продифференцируйте f(ax

, ax

, . . . , ax

) по a. Затем из

формулы (3.7.37 а) получите, что

f(ax

, ax

, ..., ax

)

∂

f(ax

, ..., ax

)

−

f(x

, x

, .. . , x

Наконец, положите a

Теперь мы готовы сформулировать и доказать теорему 3.7.10.

Теорема 3.7.10. Пусть даны целые числа q и q

, где i

1, . . . ,

q. Будем работать с массивами (неотрицательных) переменных p

1, . . . , q, j

1, . . . , q

, которые обозначим P. Рассмотрим замкну-

тое множество

размерности

−

1), заданное равенством

D =



1, i

1, . . . , q, j

1, . . . , q



. (3.7.38 а)

Далее, пусть P

7→

Z(P), P

)

—

однородный многочлен степени

d переменных p

, i

1, . . . , q, j

1, . . . , q

, с неотрицательными

коэффициентами. При заданном P

)

∈ D

пусть

(P)

(

(P)

)

означает точку из множества

, для которой

(P)

∂



∂



−

. (3.7.38 б)

Тогда Z(

(P))

Z(P) за исключением того случая, когда

(P)

Д о к а з а т е л ь с т в о. Вначале введем некоторые обозначения. Пусть

(

) означает массив неотрицательных целых чисел

, где i

1, . . . , q, j

1, . . . , q

. Для заданного массива P

)

∈ D

кратко

обозначим произведение

через [P] . Далее, c

0 означает

коэффициент многочлена Z(P) при одночлене вида [P] :

Z(P)

c [P] .

Используя эти обозначения, можно записать

(P)

[P]

. (3.7.39)

§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей 535

Мы хотим доказать, что

Z(P)

c [P]

[

(P)

]

c [

(P)]

(P)), (3.7.40)

и проанализировать, когда будет достигаться равенство.

С этой целью представим Z(P) в виде

Z(P)

(

(P)

)

[P]



(P)



. (3.7.41)

и применим неравенство Гёльдера



f g











при p

1 и q

d, в результате чего получим

Z(P)



(

(P)

)





c [P]



(P)





(Z(

(P)))



c [P]



(P)





. (3.7.42)

(Здесь для второго множителя мы использовали тот факт, что ([P]

)

[P]

.) Поскольку многочлен Z однородный и

536 Глава 3. Статистика цепей Маркова с дискретным временем

можно использовать неравенство

между геометрическим

и арифметическим средними при

1 и вывести отсюда, что

c [P]



(P)



c [P]



(P)



Теперь используя равенство (3.7.39), получим, что

c [P]



(P)





[P]



[P]





c [P]

[P]





[P]

. (3.7.43)

Выполняя преобразования, мы поменяли порядок конечных сумм. Для

каждой пары (i, j) отношение в скобках равно 1, и в силу соотношения

(3.7.38 а) мы получаем, что

1 для любого i. Поэтому все выраже

ние в правой части (3.7.43) принимает вид

[P]

∂

. (3.7.44)

Значит, по теореме Эйлера выражение (3.7.44) равно

c [P]

Z(P).

Таким образом, мы получили следующую оценку для второго множи

теля в правой части неравенства (3.7.42):



c [P]



(P)





Z(P).

Соответственно неравенство (3.7.42) принимает вид

Z(P)

(Z(

(P)))

(Z(P))

что эквивалентно неравенству (3.7.40).

§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей 537

Наконец, Z(

(P))

Z(P), если

(P)

P, что следует из неравенства

(3.7.42) и тех фактов, что а) неравенство между геометрическим и ариф

метическим средним становится равенством тогда и только тогда. когда

все числа z

равны между собой, б) неравенство Гёльдера становится

равенством тогда и только тогда, когда f и g пропорциональны. Но

равенство всех z

означает, что отношение

(P)

является постоянной,

и эта постоянная должна равняться 1 в силу соотношения (3.7.38 а). Тогда

б) также имеет место.

Мы видим, что итерации преобразования Баума

—

Уэлча

строго уве

личивают суммарное правдоподобие L(P

), если только мы не

достигли неподвижной точки. Но функция P

7→

L(P

) равно

мерно ограничена сверху для P

∈ P

. Поэтому предположим, что исходное

распределение

—

это P

∈ P

, и пусть P

(N)

—

это

(0)

), т. е. результат

кратного применения преобразования

. Тогда предел

lim

→∞

(0)

) (3.7.45)

всегда существует. Однако вопросы, аналогичные вопросам 1 и 2 для

преобразования

(см. выше), остаются открытыми. 1. Сходится ли сама

матрица P

(N)

к пределу P

(

∞

)

, когда N

→ ∞

? Если да, то P

(

∞

)

должна быть

неподвижной точкой преобразования

, причем значение L(P

(

∞

)

должно совпадать с пределом (3.7.45). В общем случае последователь

ность



(N)



может иметь более одной предельной точки в множестве

(т. е. пределы могут существовать на различных подпоследовательностях



)



), но каждая предельная точка будет неподвижной точкой пре

образования

. 2. Будет ли предел P

(

∞

)

(или предельная точка) точкой

максимума функции L(P

) (локального или глобального)? 3. Для

заданной задачи с ограничениями для матрицы P

∈ Y

лежит ли точка P

(

∞

)

в множестве

? В общем случае эти вопросы не имеют простых ответов

и требуют кропотливого анализа.

Замечание 3.7.11. Несмотря на свои прекрасные свойства, величины

∗

имеют серьезный недостаток: они вычисляются для заданной моде

ли Z, т. е. не являются функциями только обучающей последовательности

. Поэтому их нельзя назвать несмещенными и состоятельными оценками

величин

, p

и q

Завершим данный параграф таким замечанием: теорема 3.7.10 позво

ляет установить, что преобразование

(см. (3.7.28)) также увеличивает

суммарное правдоподобие:

Теорема 3.7.12. Для любого начального распределения

(

переходной матрицы P

) и совокупности вероятностей шумов

538 Глава 3. Статистика цепей Маркова с дискретным временем

), определяющих модель Z

( , P, Q), и для любой обучающей

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









имеет место неравенство

;

(Z))

L( ; Z). (3.7.46)

Более того, равенство в формуле (3.7.46) достигается тогда

и только тогда, когда

(Z)

Пример 3.7.13. Докажите теорему 3.7.12.

Указание. Возможны два альтернативных доказательства: либо с ис

пользованием теоремы 3.7.5, либо с помощью теоремы 3.7.10.

§ 3.8. Скрытые марковские модели, II. Обучающий алгоритм Баума

—

Уэлча 539

§ 3.8. Скрытые марковские модели, II.

Обучающий алгоритм Баума

—

Уэлча

Desperately Seeking Smoothness

(Из серии

Фильмы, которые не вышли на большой экран

Начнем с обсуждения процедуры сглаживания в задаче фильтрации

с.м.м. За этим термином стоит следующий подход. Перед началом про

цедуры перед нами имеется неизвестная модель, представленная точкой

( , P, Q)

∈ Z

или, образно говоря, функцией

, равной нулю

вне Z

и имеющей

пик

в точке Z. При заданной обучающей последовательно

сти









процедура позволяет нам рассмотреть семейство моделей

∗

(

∗

), совместимое с , где

∗

(Z, ),

∗

(Z, )

∗

(Z, ) изменяются вместе с изменением Z. Иными словами, мы

переходим к

распределенным

, или

сглаженным

объектам, представ

ленным функциями на множестве

. Формально возникает отображение

7→

∗

; см. (3.7.28). (Конечно, однократное применение этой процедуры

еще не решит задачи оценивания неизвестной с.м.м., но оно является

шагом в направлении такого оценивания. Основным объектом, нахождение

которого является целью данного параграфа, является результат итераций

преобразования

Итак, предположим, что зафиксирована обучающая последователь

ность









для случайной цепочки X









, порожденной ц.м.д.в.

). Это значит, что мы будем работать с условными вероятностями при

условии, что b(X)

, где b(X)





b(X

)

b(X

)





. Для заданных 0

положим

(m, n)

i, X

b(X)

) (3.8.1)

(m, n)

b(X)

)

(m, n),

(0, n). (3.8.2)

Ср. с названием фильма

Desperately Seeking Susan

(одна из первых знаменитых ролей

Мадонны).