Цепи Маркова (1121219), страница 82
Текст из файла (страница 82)
Конечно, если нет дополнительных ограничений на q 1и q2 , то полином Lсл — это продолжение Lдет (или, если угодно, Lдет —это сужение Lсл , которое получается при q1 = 1, q2 = 0). Однако еслиимеются дополнительные условия, например q 1 , q2 ∈ (q− , q+) ⊂ [0, 1] , тосравнение двух полиномов становится нетривиальным.Итак, мы максимизируем оба полинома и получаем оптимальные моделиZ∗дет ( ) = argmax Lдет ( ; Zдет) и Z∗сл ( ) = argmax Lсл ( ; Zсл).p, q1 ,q2p(3.7.3)Затем мы сравниваем оптимальные значенияLдет ( ; Zдет) и Lсл ( ; Zсл);максимальное из них определяет лучшую подгонку (для заданной цепочки ). Аналогичную процедуру можно провести для любого варианта изперечисленных выше типов а) — в) функции b.Замечание 3.7.2.
Необходимо принимать во внимание то, что модели со слишком большим числом параметров (например, с произвольнойпереходной (s × s)-матрицей P и произвольным семейством вероятностейQ) могут привести к «чересчур подогнанной» («overfitted») модели Z∗ ( );это может породить нежелательную неустойчивость, при которой Z ∗ ( )будет слишком сильно меняться вместе с изменением цепочки .
Поэтому желательно использовать любую «побочную информацию», доступнуюв возможной модели, и включать ее в задачи максимизации правдоподобий.Пример 3.7.3. Рассмотрим ц.м.д.в. (Xm), с тремя состояниями и переходной (3 × 3)-матрицей P = (pij). Известно, что диагональные переходныевероятности нулевые: pii = 0, i = 1, 2, 3. Далее, предположим, что мызнаем начальное состояние X0 = 1 и состояние X4 = 3, но не знаемсостояний в моменты времени 1, 2 и 3. Запишем суммарную функцию правдоподобия; в этом примере она равна сумме правдоподобий, подсчитанных x0слL ( ; Zсл) =nXYxpxi−1 xi (1(i=1+ (1 − q2)1(xi = C)] + 1(iiна тех выборочных векторах x = ... ∈ {1, 2, 3}5 , которые совместимы= 0) [(1 − q1)1(xi = A или B) += 1) [q1 1(xi = A или B) + q2 1(xi = C)]).x4с имеющимся ограничением (т.
е. с x0 = 1, x4 = 3):(3.7.2)(Мы опустили множитель x0 в правых частях равенств (3.7.1) и (3.7.2), поскольку он равен 1/3 и не играет никакой роли в наших рассуждениях и вы-(4)L(P | X0 = 1, X4 = 3) = p13 = p212 p21 p23 ++ p13 p31 p12 p23 + p12 p23 p31 p13 + p12 p223 p32 + p213 p32 p21 ;(3.7.4)это полиномиальная функция переменных pij . Следуя философии максимального правдоподобия, мы должны максимизировать L(P | X 0 = 1, X4 == 3) по P = (pij) на множестве Poff-diag ; см. соотношение (3.1.11). Оценка∗может быть получена во внутреннеймаксимального правдоподобия Pмпточке или на границе. В общем случае задача отыскания точной о.м.п.становится сложной с вычислительной точки зрения; вмешиваются и другие факторы, поэтому желательно иметь в своем арсенале «приемлемые»приближенные методы.Как будет показано, задача построения приближения оценки переходных вероятностей pij , 1 6 i, j 6 3, может быть (корректно) решенас помощью итераций некоторого преобразования.
Более точно, положимpijbij =p∂L(P∂ pij| X0 = 1, X4 = 3)Ξ (P | X0 = 1, X4 = 3)Ξ (P | X0 = 1, X4 = 3) =k=1,1 6 i, j 6 3.(3.7.5)(3.7.6)В частности,2p212 p21 p23 + p12 p223 p32 + p12 p31 p12 p23 + p12 p23 p31 p13,Ξ (P | X0 = 1, X4 = 3)b13 =pРассмотрим вначале общую постановку задачи фильтрации с.м.м.
Нам 0= ... , называемый обучаю-задан вектор наблюдаемых значенийnщей последовательностью или обучающей выборкой, где 0 , . . . , nпринимают значения в множестве {1, . . . , κ}. Это означает, что мы знаем,что произошло событие { 0 = b(X0), . . . , n = b(Xn) }. Однако b остаетсянеизвестной функцией {1, . . . , s} → {1, .
. . , κ}, возможно, случайной.Более точно, предположим, что для любого xзначения b(Xi) условно независимы при заданном X = x,P (b(Xi) = k|Xi = j) = qjk , j = 1, . . . , s, k = 1, . . . , κ ,где qjk > 0,∂pikL(P | X0 = 1, X4 = 3) = 2p212 p21 p23 +∂ pik+ p12 p223 p32 + 2p13 p31 p12 p23 + 2p12 p23 p31 p13 + 2p213 p32 p21 .bp12 =523(3.7.7)и положимгде знаменатель задается формулой3X§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепейГлава 3.
Статистика цепей Маркова с дискретным временем522p13 p31 p12 p23 + p12 p23 p31 p13 + 2p213 p32 p21Ξ (P | X0 = 1, X4 = 3)и т. д. Итерации этого преобразования задают решение с допустимой точностью.В примерах 3.7.1 и 3.7.3 намечены основные направления нашего исследования. См. также [K] . Одно направление относится к «зашумленным»наблюдениям, когда у нас зафиксированы все состояния, последовательнопринимаемые цепью, но сами состояния подвержены шуму, который приводит к их искажению. Этот случай можно назвать задачей фильтрациис.м.м. Второе направление соответствует случаю, когда цепь доступна длянаблюдения только в некоторые избранные моменты времени.
Этот случай назовем задачей интерполяции с.м.м. Методы, используемые в этихслучаях, имеют сходство, но в то же время и различаются в некоторыхсущественных аспектах.κPk=1(3.7.8)qjk = 1 для всех j ∈ I. Неслучайная функция b появляется,когда qjk равны 0 или 1 (понятно, что не более одного qjk может быть равно1 для заданного j). В случае безошибочного наблюдения мы имеем s = κи qij = ij . Совокупность вероятностей qjk обозначим Q (по способу своегозадания они образуют стохастическую (s ×κ) -матрицу). Будем называть ихвероятностями шума. Тройку ( , P, Q) назовем (скрытой марковской)моделью (с шумом, не имеющим памяти) и обозначим, как и прежде, Z.Предположим, что задано множество Z моделей (т.
е. троек Z == ( , P, Q)), и весь анализ проводится на этом множестве Z . «Наибольшее» такое множество соответствует ситуации «без ограничений».Задача фильтрации с.м.м. (также известная из литературы как задачаобучения, или оценивания для с.м.м. с шумом) состоит в том, чтобы найти«наиболее правдоподобную» модель Z∗ = ( ∗ , P∗ , Q∗), максимизирующуюсуммарную функцию правдоподобия L( ; Z) по Z ∈ Z для заданного :L( ; Z) := P (b(X; Z) = ) =XP (X = x; Z)nYq xii=i=0x=Xxx0 q x00nYpxi−1 xi qxi i .(3.7.9)i=1Здесь и ниже P ( · ; Z) означает распределение вероятностей, порожденноемоделями Z (т. е.
ц.м.д.в. ( , P), соответствующей выборке X и независимым наблюдениям b(Xj) с вероятностями шума Q = (qjk)). Иногда будемиспользовать также альтернативное обозначение P Z .524Глава 3. Статистика цепей Маркова с дискретным временемТаким образом, нас интересует тройка Z∗МП = (данная соотношением∗МП ,∗PМП, Q∗МП ), за-Z∗МП = argmax P (b(X) = ; Z) ,(3.7.10)Z∈Zb(X0)где b(X) обозначает (случайный) вектор ... .
(Индекс МП соответb(Xn)ствует максимуму правдоподобия.)На практике отыскание точки максимума Z∗ в соотношении (3.7.10)часто является затруднительным, особенно когда числа s и κ велики,а на множество Z налагаются многочисленные ограничения. Поэтомусуществует обширная литература, посвященная обсуждению различныхалгоритмических методов, задающих аппроксимации значения Z ∗ . Этотвопрос мы обсудим как в данном, так и в следующем параграфах.Пример 3.7.4. Задача фильтрации с.м.м. без ограничений возникает,когда пара ( , P) пробегает множество R, определенное равенством (3.1.5),а матрица Q — множество Ps,κ размерности s(κ − 1)κX= Q = (qjk) : qjk > 0,qjk = 1 .Соответственно положим(3.7.11)U = Rs × Ps,κ = Λs × Ps × Ps,κи примем во внимание, что задача без ограничений соответствует Z ∈ U .Задача фильтрации стационарной с.м.м.
без ограничений будет соответствовать паре ( , P) с матрицей P, пробегающей множество P in из соотношения (3.1.8), и с матрицей Q, пробегающей множество P s,κ .В задаче без ограничений множество U можно снабдить метрикой (расстоянием), полагаяdist(Z, Z0) =j( j − 0j) 2 +Пример задачи фильтрации с.м.м.
с ограничениями возникает, когдаматрица P пробегает множество Poff-diag из равенства (3.1.11) или множество Pсимм из равенства (3.1.12). В первом случае Z = Λ × Poff-diag × Ps,κ ,а во втором Z = Λ × Pсимм × Ps,κ . Xi,j(pij − p0ij) 2 +Xj,k(qjk − q0jk) 2Мы будем работать с выборочными векторами x = ... , имеющимиxnположительные вероятности P (X = x; Z), при заданной модели Z; а естественным предположением, которому мы будем везде следовать, будет то,что множество этих векторов X ⊆ I n одно и то же для всех рассматриваемых моделей Z ∈ Z .
Например, рассмотрим вышеупомянутую задачуфильтрации с ограничениями, где P ∈ Poff-diag , т. е. случай, когда переходнаяматрица P = (pij) ц.м.д.в. не позволяет повторять состояния подряд (этозначит, что pii = 0 для любых состояний i = 1, . . . , s), но позволяет любыедругие переходы для любой модели Z = ( , P, Q) ∈ Z (см. пример 3.7.3.В этом случае X состоит из всех векторов x ∈ I n с xi−1 6= xi , i = 1, . . . , n.Более того, предположим, что для любой модели Z ∈ Z и любойобучающей последовательности , появившейся в виде значения b(X) (т. е.P (b(X) = ; Z) > 0), выполнено условиеP (X = x | b(X) = ; Z) > 0 тогда и только тогда, когда x ∈ X .
(3.7.12)k=1X525x0Ps,κ§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей 1/ 2,где Z = ( , P, Q), Z0 = ( 0 , P0 , Q0) и = ( j), P = (pij), Q = (qjk), 0 == ( 0j), P0 = (p0ij), Q0 = (q0jk). Иными словами, это евклидова метрикав пространстве Rs(s+1+κ) , суженная на U . Мы используем эту метрикув § 3.9.Далее, положим t = #X . Удобно пронумеровать цепочки x ∈ X номеx0 (l)рами l = 1, . . .
, t (в любом порядке) и записать x(l) = ... для l-йxn (l)цепочки. Тогда при заданном Z = ( , P, Q) положимul ( ; Z) = P (b(X) = , X = x(l); Z) ==x0 (l) qx0 (l)0nYpxj−1 (l)xj (l) qxj (l) j .(3.7.13)j=1Таким образом, ul ( ; Z) задает вероятность пересечения{X = x(l) } ∩ {b(X) = }в модели Z.Теорема 3.7.5. Предположим, что заданы такая модель Z ∈ Uи такая обучающая последовательность , что ul ( ; Z) > 0 хотябы для одного l (т.
е. выполнено неравенство P (b(X) = ; Z) > 0).b ∈ U выполняетсяТогда при условии (3.7.12), для любой модели Z526Глава 3. Статистика цепей Маркова с дискретным временемнеравенствоbb )P (b(X) = ; Z)U(Z, Z; ) − U(Z, Z;>,P (b(X) = ; Z)P (b(X) = ; Z)ln(3.7.14)§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепейДля решения этой задачи удобно использовать матрицу подсчета переходов. Как и в § 3.4, при заданных i, j = 1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
