Цепи Маркова (1121219), страница 83
Текст из файла (страница 83)
. . , s и l = 1, . . . , t пустьfij (l) — это число переходов i → j в цепочке x(l):fij (l) =гдеU(Z, Z; ) =tXl=1иb )=U(Z, Z;tXl=1b .[−ul ( ; Z) ln ul ( ; Z)](3.7.15)Далее, положим(3.7.16)−ul ( ; Z) ln ul ( ; Z) = 0, если ul ( ; Z) = 0,b = +∞, если ul ( ; Z) > 0, но ul ( ; Z)b = 0,−ul ( ; Z) ln ul ( ; Z)и, таким образом, все слагаемые в суммах из соотношений (3.7.15),(3.7.16) неотрицательны.Д о к а з а т е л ь с т в о немедленно следует из примера 3.6.7 при n =bl . Действительно, условие теоремы эквивалентно= t, al = ul , bl = uнеравенствуlnl=1bulul>"tXl=1(ul ln bul − ul ln ul)#tX(3.7.17)ul ,l=1bгде ul = ul ( ; Z) и bul = ul ( ; Z).b для которойЗначит, если для заданного и Z можно найти модель Z,правая часть неравенства (3.7.14) положительна, то получим «улучшенную» модель в смысле большего значения правдоподобия.Таким образом, нас интересует задача минимизации функцииb ), определенной в соотношении (3.7.16), по переменным Zb ∈ZU(Z, Z;для заданной модели Z ∈ Z и заданной обучающей последовательности.
В общем случае минимизатор, конечно, будет зависеть от Z и(и отвыбора множества Z).(3.7.18)Кроме того, при заданной обучающей последовательности и k = 1, . . . , κобозначим через njk (l) (= njk (l, )) число моментов времени, в которыев цепочке x(l) было зафиксировано значение k при истинном состоянии j:njk (l) =nX1(xm (l) = j,m(3.7.19)= k).m=0Наконец, обозначимиl=1tP1(xm−1 (l) = i, xm (l) = j).rj (l) = 1(x0 (l) = j).Мы следуем здесь соглашению о том, чтоtPnXm=1[−ul ( ; Z) ln ul ( ; Z)]527ej =tXul rj (l),l=1cij =tXul fij (l) и djk =l=1tXul njk (l);(3.7.20)l=1здесь мы вновь записываем ul = ul ( ; Z) для модели Z = ( , P, Q) ∈ Z .Таким образом, ej , cij и djk являются функциями модели Z и последовательности .Возвращаясь к соотношению (3.7.16), перегруппируем слагаемые в выb ) согласно появлениям начальных состояний i,ражении для U(Z, Z;переходам i → j и зафиксированным значениям k.
В результате получаем,b = (b, P,b Q)b имеют место равенствачто для Zb )=U(Z, Z;sts Xκs XXXXbul − ln x0 (l) −njk (l) ln bqjk −fij (l) ln bpij =l=1=−j=1 k=1sXj=1ej ln bj −s XκXj=1 k=1djk ln bqjk −i=1 j=1ss XXi=1 j=1bij .cij ln p(3.7.21)b выражения в правой частиЕдинственный глобальный минимум по Z∗bb∗, Qb ∗), где b = (b∗),равенства (3.7.21) достигается в точке Z = (b∗ , Pib ∗ = (pb ∗ = (bb∗ij) и QPq∗jk) задаются формуламиXsb∗ = ejei , j = 1, . . . , s,(3.7.22)ji=1528Глава 3. Статистика цепей Маркова с дискретным временемbp∗ijиbq∗jk = djk= cijXκXscim , i, j = 1, .
. . , s(3.7.23)m=1djk , j = 1, . . . , s, k = 1, . . . , κ .(3.7.24)k=1j=1ej =st XXrj (l) =l=1 j=1tXul = P (b(X) = ; Z)l=1иnj :=κXdjk = E Z (число посещений состояния j до момента времени n),k=1где E Z обозначает математическое ожидание по мере P Z . Используя этиравенства, можно переписать соотношения (3.7.22) – (3.7.24) в компактнойформе:b∗ = ej / P Z (b(X) = ), pb∗ij = cijjXsm=1cim и bq∗jk = djk /nj .(3.7.25)В общем случае нам необходимо решить задачу с ограничениямиb для заданного Zминимизировать правую часть (3.7.21) по Zb ∈ Z.при условии, что Z(3.7.26)Это наводит на мысль о следующем «обучающем» алгоритме: при заданнойначальной модели Z (0) ∈ Z и обучающей последовательности решить заb∗ ∈ Z.дачу (3.7.26), получив, таким образом, улучшенную модель Z (1) = Z529Затем повторить это для Z (1) и , и т. д.
Предположим, что минимизаторZ (N) , полученный в результате N итераций, сходится к пределу:lim Z (N) = Z (∞) ∈ Z .b∗ij и bЧитатель должен иметь в виду, что вероятности b∗j , pq∗jk являютсяфункциями модели Z и последовательности .b ∗ принадлежит Z , то она обеспечивает «усоверЗначит, если модель Zшенствование» модели Z в этом классе. Например, в примере 3.7.3, гдепереходная матрица P имеет все нулевые диагональные элементы p ii = 0,b ∗ = (pb∗ij) из соотношения (3.7.23) сохраняет то жепереходная матрица Pсвойство.Знаменатели соотношений (3.7.22), (3.7.24) можно упростить.
В самомделе, заметим, чтоsX§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепейN→∞(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 instatistical 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–8.Baum, L.E., Petrie, T., Soules, G. Weiss, N. A maximization techniqueoccurring 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.Pacific Journ.
Math., 27 (1968), 211–227.Baum, L.E., Eagon, J.A. An inequality with applications to statisticalestimation for probabilistic functions of Markov processes and to a model forecology. Bull. Amer. Math. Soc., 73 (1967), 360–363.Baum, L.E., Petrie, T.
Statistical inference for probabilistic functions offinite state Markov chains. Annals Math. Statist., 37 (1966), 1554 –1563.Алгоритм, приведенный выше, называют обучающим алгоритмомБаума—Уэлча; его привлекательность заключается в простоте (а потомуи в практичности) решения задачи (3.7.26) для различных множеств Z , чтои продемонстрировали формулы (3.7.22) – (3.7.25).Удобно связать с равенствами (3.7.22) – (3.7.25) отображение Φ : U → Uмножества U (см.
(3.7.11)) в себяb ∗ = (b∗ , Pb∗, Qb ∗),Φ : Z = ( , P, Q) 7→ Z(3.7.28)которое мы назовем преобразованием Баума—Уэлча для фильтрации(без ограничений). (При этом формулы (3.7.22) – (3.7.25) будут переписаны530Глава 3. Статистика цепей Маркова с дискретным временемв различных (эквивалентных) формах, поясняющих различные аспектыотображения Φ.) Преобразование Φ будет особенно полезным для задачи(3.7.26), где оно переводит изначальное множество моделей Z в себя:Φ (Z) ⊆ Z .Вышеупомянутые вопросы 1 и 2 (для задачи фильтрации без ограничений)касаются итераций ΦN преобразования Φ.
Непосредственным следствиемтеоремы 3.7.5 является следующее утверждениеПример 3.7.6. Докажите, что любая точка Z∗МП , определенная в формуле (3.7.10), является неподвижной точкой отображения Φ:Φ (Z∗МП) = Z∗МП .(3.7.29)Решение. В самом деле, если Φ (Z∗МП) 6= Z∗МП , то P (b(X) =Φ (Z∗МП)) > P (b(X) = , Z∗МП).,Chariots of Φ, Chariots of Π5(Из серии «Фильмы, которые не вышли на большой экран».)Перейдем теперь к задачам интерполяции с.м.м. Вновь будем работатьс ц.м.д.в. (Xm) с пространством состояний I = {1, . .
. , s} и матрицейвероятностей перехода P = (pij). В нашей постановке задачи матрица Pполностью определяет модель; предположим для простоты, что начальноеизвестно. Предположим также, что цепь наблюдаемараспределениев (целые) моменты времени 0 = t0 < t1 < . . . < tk 6 n; обозначим T = Xt 0x t0Xt kx tk= {t1 , . . .
, tk }. Соответственно пусть XT = ... и xT = ... . При y0yt 0.n+1заданном y = .. ∈ Iпусть y T обозначает сужение ... . Затемynyt kопределим суммарное правдоподобие:L(P | XT = xT) =Xy∈In+1y0nYm=1pym−1 ym 1(yT = xT) ==sX Yy∈In+1 i,j=15 Ср.с названием фильма «Chariots of Fire».ri fiji pij 1(y T= xT),(3.7.30)§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепейгдеfij = fij (y) =nXm=15311(ym−1 = i, ym = j), ri = ri (y) = 1(y0 = i);ср. с соотношениями (3.7.17), (3.7.18). Задача интерполяции состоит∗∗в отыскании точек максимума PМП(= PМП(xT)) на заданном множествеY ⊆ P (см. (3.1.7)):∗PМП= argmax L(P | XT = xT).(3.7.31)P∈YКак и ранее, если Y = P , получаем задачу без ограничений, а если Y —«правильное» подмножество в P , то речь идет о задаче с ограничениями.Дальнейшее обобщение (не рассматриваемое здесь) возникнет, если использовать более общее условие X0 ∈ A0 , Xt1 ∈ A1 , .
. . , Xtk ∈ Ak , где A1 ,. . . , Ak — подмножества пространства состояний I.Здесь мы столкнемся с рядом трудностей, подобных тем, которые воз∗никают в задаче фильтрации с.м.м.: точки максимума P МПв соотношении(3.7.31) трудно найти, и они очень чувствительны к выбору множества Y ,содержащего априорную информацию о модели.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
