Цепи Маркова (1121219), страница 85
Текст из файла (страница 85)
(3.7.28)) также увеличиваетсуммарное правдоподобие:= ( j),Теорема 3.7.12. Для любого начального распределенияпереходной матрицы P = (pij) и совокупности вероятностей шумов538Глава 3. Статистика цепей Маркова с дискретным временем§ 3.8. Скрытые марковские модели, II. Обучающий алгоритм Баума—УэлчаQ = (qjk), определяющих модель Z = ( , P, Q), и для любой обучающей § 3.8.
Скрытые марковские модели, II.Обучающий алгоритм Баума—Уэлча0= ... имеет место неравенствоDesperately Seeking Smoothness6последовательностиn(Из серии «Фильмы, которые не вышли на большой экран».)(3.7.46)Начнем с обсуждения процедуры сглаживания в задаче фильтрациис.м.м. За этим термином стоит следующий подход. Перед началом процедуры перед нами имеется неизвестная модель, представленная точкойZ = ( , P, Q) ∈ Z или, образно говоря, функцией Z , равной нулю «вне Z»и имеющей «пик» в точке Z. При заданной обучающей последовательно 0= ...
процедура позволяет нам рассмотреть семейство моделейстиnb ∗ = (b∗ , Pb∗, Qb∗ = Pb ∗ (Z, )b ∗), совместимое с , где b∗ = b∗ (Z, ), PZb ∗ (Z, ) изменяются вместе с изменением Z. Иными словами, мыb∗ = QиQпереходим к «распределенным», или «сглаженным» объектам, представленным функциями на множестве Z . Формально возникает отображение Φ:b ∗ ; см. (3.7.28). (Конечно, однократное применение этой процедурыZ 7→ Zеще не решит задачи оценивания неизвестной с.м.м., но оно являетсяшагом в направлении такого оценивания.
Основным объектом, нахождениекоторого является целью данного параграфа, является результат итерацийпреобразования Φ.)Итак, предположим, что зафиксирована обучающая последователь X00.= .. для случайной цепочки X = ...
, порожденной ц.м.д.в.XnnБолее того, равенство в формуле (3.7.46) достигается тогдаи только тогда, когда Φ (Z) = Z.Пример 3.7.13. Докажите теорему 3.7.12.Указание. Возможны два альтернативных доказательства: либо с использованием теоремы 3.7.5, либо с помощью теоремы 3.7.10.ностьL( ; Φ (Z)) > L( ; Z).539(Xm). Это значит, что мы будем работать с условными вероятностями приb(X0)условии, что b(X) =положими, где b(X) = ... . Для заданных 0 6 m 6 nb(Xn)eij (m, n) = P Z (Xm = i, Xm+1 = j | b(X) = )pepi (m, n) = P Z (Xm = i | b(X) = ) =sXj=1eij (m, n),p(3.8.1)ei = pei (0, n). (3.8.2)6 Ср.
с названием фильма«Desperately Seeking Susan» (одна из первых знаменитых ролейМадонны).Глава 3. Статистика цепей Маркова с дискретным временемОбозначим ul = P Z (b(X) = , X = x(l)), l = 1, . . . , t, и введемнормирующую постоянную для u1 , . . . , ut :11= tPP Z (b(X) = )l=1.bq∗jk =1(nPmnPm=1m=1, j = 1, . . . , s, k = 1, . . . , κ .(3.8.4)epj (m, n)Д о к а з а т е л ь с т в о. Начнем с очевидного наблюдения, заключающегося в том, что в силу соотношения (3.8.2) для любых j = 1, .
. . , sи k = 1, . . . , κ выполняется равенствоnX1(m= 1m= k) P Z (Xm = j | b(X) = ) =nX1(mm=1ej (m, n).= k) p(3.8.5)Наша следующая цель — проверить, что (ср. (3.7.20))djk = P Z (b(X) = )nX1(m=1m= k) P Z (Xm = j | b(X) = ).(3.8.6)Чтобы доказать соотношение (3.8.6), рассмотрим функцию выборкиx(l), l = 1, . . . , t:nX1(xm (l) = j,m= k),m=0задающую число моментов времени, в которые наблюдается пара j → kв выборке x(l) для заданного . ТогдаnXm= 1P Z (Xm = j, b(Xm) = k | b(X) = ) = Cepj (m, n) = Cnj ,что на самом деле очевидно. ПоэтомуC−1nP1(m= k)epj (m, n)m=1bq∗jk =C−1nPm=1.epj (m, n)Отсюда следует равенство (3.8.4).Подобным образом доказывается и следующий результат.b∗ij (= pb∗ij ( ))), в которых достигается миЛемма 3.8.2.
Значения pнимум в соотношениях (3.7.23) и (3.7.25), можно переписать в видеb∗ij =pnP−1m=1nP−1m=1epij (m, n), i, j = 1, . . . , s.tXl=1Значения b∗j (= b∗j ( ))), в которых достигается минимум в соотношениях (3.7.22) и (3.7.25), можно переписать в видеb∗ = pej (0, n), j = 1, . . .
, s.j(3.8.8)К сожалению, формулы (3.8.4), (3.8.7), (3.8.8) (так же каки (3.7.22) – (3.7.24)) не слишком полезны с вычислительной точки зрения.Как было отмечено в § 3.7, на практике процедура максимизации выполняется согласно алгоритму Баума—Уэлча (его также называют переоценкойпо Бауму—Уэлчу), последовательно улучшающей вероятности epij (m, n)ei (m, n) на каждой итерации.иpТеперь наша непосредственная цель — выписать сглаженные вероятности в терминах так называемых прямых и обратных переменных m (j)и m (j); см. формулу (3.8.9). Это даст нам эффективную с вычислительнойточки зрения форму переоценки по Бауму—Уэлчу. Для заданного m == 0, . .
. , n определим случайные цепочкиb(X0)z(l, j, k)ul = Cdjk ,(3.8.7)epi (m, n)l 7→ z(l, j, k) :=nXul= k)epj (m, n)m=1где постоянная C определена соотношением (3.8.3). Для завершения доказательства достаточно заметить, что знаменатель имеет вид(3.8.3)В леммах 3.8.1 и 3.8.2 формулы (3.7.22) – (3.7.24) переписаны в альтернативной, причем более удобной, форме.q∗jk (= bq∗jk ( ))), в которых достигается миЛемма 3.8.1. Значения bнимум в соотношениях (3.7.24) и (3.7.25), можно записать в виде541C=§ 3.8. Скрытые марковские модели, II. Обучающий алгоритм Баума—Уэлча540bm↑ (X) = ... и bm↓ (X) = b(Xm)b(Xm+1)....b(Xn)m=1nn−1Xeij (m, n) =p=Cn−1Xm=1P Z (Xm = i, Xm+1 = j | b(X) = ) =[P Z (b(X) =(3.8.9)m=1= j qj 0 , j = 1, . . .
, s,(3.8.11)Xsm (i)pij qj m+1 , j = 1, . . . , s, m = 1, . . . , n − 1,m+1 (j) =i=1n (j)= 1, j = 1, . . . , s,(3.8.13)=i=1sXm+1 (i)qim+1pji , j = 1, . . . , s, m = 0, . . . , n − 1.n−1X| Xm = i, Xm+1 = j) =m=1epij (m, n) =b∗ij =pm (i)bj ( m+1) m+1 (j).nP−1m=0m (i)pij bj ( m+1) m+1 (j).P Z (b(X) = )(3.8.16)nP−1m=1nP−1m=1epij (m, n)= pijepi (m, n)nP−1l=0l (i)bj ( l+1) l+1 (i).nP−1(3.8.17)l (i) l (i)l=0Далее, сглаженные начальные вероятности задаются формулами0 (j) 0 (j).P Z (b(X) = )b∗ = pej (0, n) =j(3.8.18)Наконец, для сглаженных вероятностей шумов мы имеем формулыbq∗jk =nP1((3.8.15)Д о к а з а т е л ь с т в о непосредственно следует из равенств (3.8.4).| Xm+1 = j).Наша следующая задача — получить эффективное с вычислительнойточки зрения выражение для p∗ij .
Комбинируя выражение (3.8.15) с леммой3.8.2, получим сглаженные переходные вероятностиm (i) m (i).P Z (b(X) = )m↓(X) =После суммирования получимepi (m, n) =| Xm = i) ×m↑m↓P Z (Xm = i) P Z (b(X) =(3.8.14)Уравнения (3.8.11), (3.8.12) задают прямую рекурсию для вероятностей ,в то время как (3.8.13), (3.8.14) задают обратную рекурсию для вероятностей .Лемма 3.8.3. Вероятность epi (m, n) из формулы (3.8.2) допускаетследующее представление:| Xm+1 = j) P Z (bm+1Таким образом, получаем, что(3.8.12)иm (j)× P Z (b(Xm+1) =0 (j)| Xm = i, Xm+1 = j) = P Z (bm↑ (X) =m= k)epj (m, n)m=1nPm=1=epj (m, n)nPm (j) m (j)По определению условной вероятности имеют место такие рекуррентные соотношения:P Z (b(X) =(3.8.10)= P Z (b(X) = , Xm = j).P Z (b(X) = ) | Xm = i, Xm+1 = j) P Z (Xm = i)pij ,где C — постоянная, заданная равенством (3.8.3).
Следующий шаг состоитв проверке, с использованием марковского свойства, того, чтоТогда имеет место равенствоm (j) m (j)n−1X| Xm = j).=Cm↓Xm = j),1(m= k)= P Z (bm↓ (X) =m↑ ,m=1nPm=1.m (j) m (j)m (j)= P Z (bm↑ (X) =m (j)| Xm = i, Xm+1 = j) P Z (Xm = i, Xm+1 = j)] =m=1Далее, определимn−1X= ... .mm+1Теперь, применяя формулу Байеса, запишемm↓543m↑= ...
и0§ 3.8. Скрытые марковские модели, II. Обучающий алгоритм Баума—УэлчаАналогичноГлава 3. Статистика цепей Маркова с дискретным временем542(3.8.19)зависящую от переменной Z (т. е. от начального выбора параметров с.м.м.,которую мы пытаемся выявить). В этой ситуации ключевой шаг — выполнение N-кратной итерации нашей процедуры (т. е. рассмотрение преобразования ΦN):Z(N)= Φ (Z(N−1)N(0)) = Φ (Z ), N = 1, 2, . . . ,L( ; Z (∞) ) = max[L( ; Z) : Z = ( , P, Q) ∈ U ] .(3.8.22)L( ; Z) =Тогда точку Z (∞) можно трактовать как «оценку» (точнее, о.м.п. Z∗о.м.п.)предоставляющую нам «наилучшую подгонку» с.м.м.
для заданной обучающей последовательности .С геометрической точки зрения, предел Z (∞) , если он существует,является неподвижной точкой отображения Φ. Мы видим, что анализнеподвижных точек Z∗ отображения Φ, и, в частности, условий сходимостиZ (N) = ΦN (Z) → Z∗ , является здесь принципиальным вопросом. Этотвопрос обсуждается в § 3.9.Прежде чем продвинуться дальше, обсудим (непосредственный) результат максимизации выражения (3.8.22) по переменным , P и Q, образующим модель Z. Запишем лагранжиан в видеXsj=1 XX XXsssκ++−1p−1lq−1,jiijjjki=1j=1j=1k=1∂L( ; Z) +∂ jsXpij > 0,pij = 1,∂L( ; Z) +∂ pijj=1qjk > 0,κX= 1,jj=1i∂L( ; Z) + lj = 0,∂ qjkqjk = 1,k=1= 0, j = 1, . . . , s,= 0, i, j = 1, .
. . , s,j = 1, . . . , s, k = 1, . . . , κ ,и задается уравнениямиj=(3.8.21)и определение предельной точки (точек) при N → ∞. В «хорошей» ситуации можно надеяться, что существует предел Z (∞) = limN→∞ ΦN (Z),не зависящий от начальной точки Z (0) (или зависящий от Z (0) «слабо»,т. е. Z (∞) меняется только при переходе от одной «области притяжения»к другой). Предположим дополнительно, что Z (∞) является глобальнойточкой максимума правдоподобия L( ; Z) = P (b(X) = ; Z), т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
