Цепи Маркова (1121219), страница 84
Текст из файла (страница 84)
Поэтому ищется приближенное решение, которое может быть получено достаточно явным образом.b с элементами pbij ,Осуществим это построение, определив матрицу Pi, j = 1, . . . , заданными в видеpijbpij = Psk=1∂L(P∂ pijpik| XT = xT)∂L(P∂ pik,(3.7.32)| XT = xT)где суммарное правдоподобие L(P | XT = xT) задается формулой (3.7.30).b зависит от P и xT : Pb = P(P,bОчевидно, PxT). Для заданной выборки xTформула (3.7.32) определяет отображение Π (= Π (x T)) на множестве Ps :b = (pbij),Π : P = (pij) 7→ P(3.7.33)которое называется преобразованием Баума—Уэлча для задачи интерполяции с.м.м.Здесь уместно сделать два замечания.I.
Предположим, что t0 = 0, t1 = 1, . . . , tk = k, т. е. цепь наблюдаемав последовательные моменты времени 0, . . . , k. Тогда x T становится вы x0борочным векторомxk0= ... ∈ Ik+1 и правая часть равенства (3.7.32)xk532Глава 3. Статистика цепей Маркова с дискретным временемзадает матрицу, которая не зависит от P, а зависит лишь от x k0 .
Болееbij , равныеточно, в этом случае формула (3.7.32) задает вероятности pkbbэмпирическим (или относительным) частотам fij (= fij (x0)) переходов i → jв выборке xk0 :bij = bfij :=pXsl=1fil (xk0) −1fij (xk0), i, j = 1, . . . , s.(3.7.34)Геометрически это означает, что преобразование Π Баума —Уэлча перевоb = (bfij) эмпирических частот:дит любую матрицу P ∈ P в матрицу Fb P ∈ P.Π (P) = F,b является единственной неподвижнойЗначит, в этом случае матрица Fточкой преобразования (3.7.33), и если повторить процедуру (3.7.32) (т.
е.итерировать отображение (3.7.33)), то в результате опять получим матриbцу F.II. Если ц.м.д.в. (Xm) состоит из н.о.р.с.в., то формула (3.7.32) задаетbj (xT) посещенийbj = gbij как эмпирические (относительные) частоты gpсостояния j выборкой xT . Формально −1Xsbj :=bij = gpglgj , j = 1, . .
. , s,(3.7.35)l=1гдеgj = gj (xT) =kX1(xtl = j).l=0В этом случае мы забываем о состояниях, в которых цепь побывала междуточками t0 , . . . , tk , и вычисляем частоты посещений каждого состоянияj = 1, . . . , s, основываясь на доступных данных. Иначе говоря, каждаяматрица P = (pij), строки которой являются повторениями фиксированногостохастического вектора (или, что эквивалентно, элементы которой p ij = pjпостоянны вдоль каждого столбца), переводится отображением Π в матb эмпирических частот gbj (которая, очевидно, удовлетворяет томурицу Gb = (gbij) всегдаже свойству).
Геометрически это означает, что матрицы Gобразуют семейство неподвижных точек преобразования Баума —Уэлча Π.Пример 3.7.7. Докажите замечания I и II.Решение. Оба равенства (3.7.34) и (3.7.35) получаем из соотношения(3.7.32) путем дифференцирования.§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепей533Примечательно то, что итерации преобразования Π из соотношения (3.7.33) ведут к увеличению значения суммарного правдоподобияL(P | XT = xT), определенного формулой (3.7.30).Теорема 3.7.8.
Для любой переходной матрицы P = (pij), множества моментов времени T = {t0 , t1 , . . . , tk }, упорядоченных так, что x t00 = t0 < t1 < . . . < tk 6 n, и любой выборочной цепочки xT = ... x tkимеет место неравенствоL(Π (P) | XT = xT) > L(P | XT = xT).(3.7.36)Более того, равенство в (3.7.36) достигается тогда и только тогда,когда Π (P) = P.Д о к а з а т е л ь с т в о. Основная идея доказательства — алгебраическая. При заданном xT функцииP 7→ L(P | XT = xT) и P 7→ L(Π (P) | XT = xT)являются однородными многочленами переменных p ij в том смысле, чтооба выражения L(P | XT = xT) и L(Π (P) | XT = xT) — это суммы одночленов фиксированной (совокупной) степени, равной t k + 1. Более того,эти одночлены входят в сумму с коэффициентами 0 или 1 (см.
(3.7.30)).Теорема 3.7.8 будет следствием более общей теоремы 3.7.10, сформулированной и доказанной далее для таких многочленов. См. вышеупомянутуюстатью Л. Баума и Дж. Игона, где такие рассуждения были проведены.впервые.Прежде чем перейти к теореме 3.7.10, нам хотелось бы обратитьсяк знаменитой теореме Эйлера об однородных функциях. Функция n действительных переменных f(x1 , x2 , . .
. , xn) называется однородной степени d, если для любого действительного a выполняется равенствоf(ax1 , ax2 , . . . , axn) = ad f(x1 , x2 , . . . , xn).(3.7.37 а)Теорема Эйлера утверждает, что для любой дифференцируемой однороднойфункции справедливо равенствоnXi=1xi∂f = df.∂ xi(3.7.37 б)Пример 3.7.9.
Предполагая наличие свойства (3.7.37 а), докажите равенство (3.7.37 б).Глава 3. Статистика цепей Маркова с дискретным временемУказание. Продифференцируйте f(ax1 , ax2 , . . . , axn) по a. Затем изформулы (3.7.37 а) получите, чтоdf(ax1 , ax2 , . . . , axn) =danXi=1xi∂f(ax1 , . . . , axn) = dad−1 f(x1 , x2 , . . . , xn).∂ xiНаконец, положите a = 1.Теперь мы готовы сформулировать и доказать теорему 3.7.10.Теорема 3.7.10. Пусть даны целые числа q и qi , где i = 1, . . . ,q.
Будем работать с массивами (неотрицательных) переменных pij ,i = 1, . . . , q, j = 1, . . . , qi , которые обозначим P. Рассмотрим замкнуqP(qi − 1), заданное равенствомтое множество D размерностиi=1D=Xpij > 0,pil = 1, i = 1, . . . , q, j = 1, . . . , qi .§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепейZ(P) =Xc [P] =6XXqcc∂Z∂ pijXqipijj=1∂Z∂ pij −1.Z(P) =(3.7.38 а)(3.7.38 б)Тогда Z(Π (P)) > Z(P) за исключением того случая, когда Π (P) = P.Д о к а з а т е л ь с т в о.
Вначале введем некоторые обозначения. Пусть= ( ij) означает массив неотрицательных целых чисел ij , где i == 1, . . . , q, j = 1, . . . , qi . Для заданного массива P = (pij) ∈ D краткоq qiYY ijpij через [P] . Далее, c > 0 означаетобозначим произведениеi=1 j=1коэффициент многочлена Z(P) при одночлене вида [P] :Xc [P] .Z(P) =i=1 j=1YY.j=1ij [P]cij=i=1 j=1Xc [Π (P)] = Z(Π (P)),Xcq qiYY(Π (P) ij)iji=1 j=1× c!1/ (d+1)(3.7.40)d/d+1×q qi YY[P]i=1 j=11Π (P) ijij / (d+1)!.(3.7.41)и применим неравенство ГёльдераX X 1/ p X 1/ qpq6fg|f||g|при p = d + 1 и q = (d + 1) /d, в результате чего получимZ(P) 6Xcq qiYY(Π (P) ij)i=1 j=1×= (Z(Π (P)))X1/ (d+1)ij1/ (d+1)c [P]×q qi YYpiji=1 j=1Xc [P]ij /dΠ (P) ijq qi YYpiji=1 j=1i=1 j=1ij [P]Π (P) ij = Pqi Pc[Π (P) ij ]Π (P) ijd/ (d+1)ij /d=d/ (d+1).(3.7.42)(Здесь для второго множителя мы использовали тот факт, что ([P] ) d+1/d =p QqiQd= [P]pijij / .) Поскольку многочлен Z однородный иИспользуя эти обозначения, можно записатьPpijij 6qil=1Π (P) ij = pijq qiYYи проанализировать, когда будет достигаться равенство.С этой целью представим Z(P) в видеqiДалее, пусть P 7→ Z(P), P = (pij) — однородный многочлен степениd переменных pij , i = 1, .
. . , q, j = 1, . . . , qi , с неотрицательнымикоэффициентами. При заданном P = (pij) ∈ D пусть Π (P) = (Π (P) ij)означает точку из множества D , для которой535Мы хотим доказать, что(3.7.39)qipXXi=1 j=1534ijd= 1,536Глава 3. Статистика цепей Маркова с дискретным временемQ iPможно использовать неравенствоzi P6i zi между геометрическим=1 и вывести отсюда, чтои арифметическим средними при i > 0,iic [P]p qi YYpiji=1 j=1ij /d6Π (P) ijXqipXXc [P]XijΠ (P) ijdi=1 j=1 p ij.qiq1 XXdi=1 j=1Ppij Pij c[P]00ij c 0[P]00c00c0=0 [P] 0ijqiXXj0 =1[P]0ij0Pc0j0 =1ij piji=1 j=1qi PP[P]=cqiqXXd1X=Π (P) ijd p ij=iji=1 j=1qqiXXc [P]0ij0 [P]00.(3.7.43)0Выполняя преобразования, мы поменяли порядок конечных сумм. Длякаждой пары (i, j) отношение в скобках равно 1, и в силу соотношенияqiPpij = 1 для любого i.
Поэтому все выраже(3.7.38 а) мы получаем, чтоj=1ние в правой части (3.7.43) принимает видqiq1 XXXcd0000ij0 [P]0=i=1 j =11X∂Pp 0.d 0 ij ∂ pij0(3.7.44)ijЗначит, по теореме Эйлера выражение (3.7.44) равноPc [P] = Z(P).Таким образом, мы получили следующую оценку для второго множителя в правой части неравенства (3.7.42):Xc [P]q qi YYpiji=1 j=1Π (P) ijij /d6 Z(P).Соответственно неравенство (3.7.42) принимает видZ(P) 6 (Z(Π (P))) 1/ (d+1) (Z(P)) d/ (d+1) ,что эквивалентно неравенству (3.7.40).537Наконец, Z(Π (P)) > Z(P), если Π (P) 6= P, что следует из неравенства(3.7.42) и тех фактов, что а) неравенство между геометрическим и арифметическим средним становится равенством тогда и только тогда.
когдавсе числа zi равны между собой, б) неравенство Гёльдера становитсяравенством тогда и только тогда, когда f и g пропорциональны. Ноpijравенство всех zi означает, что отношениеявляется постоянной,Π (P) ijи эта постоянная должна равняться 1 в силу соотношения (3.7.38 а). Тогдаб) также имеет место.Мы видим, что итерации преобразования Баума —Уэлча Π строго увеличивают суммарное правдоподобие L(P | XT = xT), если только мы недостигли неподвижной точки. Но функция P 7→ L(P | X T = xT) равномерно ограничена сверху для P ∈ P .
Поэтому предположим, что исходноераспределение — это P0 ∈ P , и пусть P (N) — это ΠN (P (0) ), т. е. результатN-кратного применения преобразования Π. Тогда пределТеперь используя равенство (3.7.39), получим, чтоX§ 3.7. Скрытые марковские модели, I. Оценивание состояний марковских цепейlim L(ΠN (P (0) | XT = xT)N→∞(3.7.45)всегда существует. Однако вопросы, аналогичные вопросам 1 и 2 дляпреобразования Φ (см.
выше), остаются открытыми. 1. Сходится ли самаматрица P (N) к пределу P (∞) , когда N → ∞? Если да, то P (∞) должна бытьнеподвижной точкой преобразования Π, причем значение L(P (∞) |XT = xT)должно совпадатьс пределом (3.7.45). В общем случае последовательность P (N) может иметь более одной предельной точки в множестве Pпределымогут существовать на различных подпоследовательностях(т. е.P (Nm) ), но каждая предельная точка будет неподвижной точкой преобразования Π. 2.
Будет ли предел P (∞) (или предельная точка) точкоймаксимума функции L(P | XT = xT) (локального или глобального)? 3. Длязаданной задачи с ограничениями для матрицы P ∈ Y лежит ли точка P (∞)в множестве Y ? В общем случае эти вопросы не имеют простых ответови требуют кропотливого анализа.Замечание 3.7.11. Несмотря на свои прекрасные свойства, величиныb∗ij и bpq∗jk имеют серьезный недостаток: они вычисляются для заданной модели Z, т. е. не являются функциями только обучающей последовательности. Поэтому их нельзя назвать несмещенными и состоятельными оценкамивеличин i , pij и qjk .Завершим данный параграф таким замечанием: теорема 3.7.10 позволяет установить, что преобразование Φ (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
