Алгоритм Баума — Велша

14.04.2022

Алгоритм Баума — Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм прямого-обратного хода и является частным случаем обобщённого EM-алгоритма.

Алгоритм Баума — Велша оценки скрытой модели Маркова

Скрытая модель Маркова — это вероятностная модель множества случайных переменных { Y 1 , … , Y t , Q 1 , … , Q t } {displaystyle {Y_{1},;ldots ,;Y_{t},;Q_{1},;ldots ,;Q_{t}}} . Переменные Y t {displaystyle Y_{t}} — известные дискретные наблюдения, а Q t {displaystyle Q_{t}} — «скрытые» дискретные величины. В рамках скрытой модели Маркова есть два независимых утверждения, обеспечивающих сходимость данного алгоритма:

  • t {displaystyle t} -я скрытая переменная при известной ( t − 1 ) {displaystyle (t-1)} -ой переменной независима от всех предыдущих ( t − 1 ) {displaystyle (t-1)} переменных, то есть P ( Q t ∣ Q t − 1 , Y t − 1 , … , Q 1 , Y 1 ) = P ( Q t ∣ Q t − 1 ) {displaystyle P(Q_{t}mid Q_{t-1},;Y_{t-1},;ldots ,;Q_{1},;Y_{1})=P(Q_{t}mid Q_{t-1})} ;
  • t {displaystyle t} -е известное наблюдение зависит только от t {displaystyle t} -го состояния, то есть не зависит от времени, P ( Y t ∣ Q t , Q t − 1 , Y t − 1 , … , Q 1 , Y 1 ) = P ( Y t ∣ Q t ) {displaystyle P(Y_{t}mid Q_{t},;Q_{t-1},;Y_{t-1},;ldots ,;Q_{1},;Y_{1})=P(Y_{t}mid Q_{t})} .
  • Далее будет предложен алгоритм «предположений и максимизаций» для поиска максимальной вероятностной оценки параметров скрытой модели Маркова при заданном наборе наблюдений. Этот алгоритм также известен как алгоритм Баума — Велша.

    Q t {displaystyle Q_{t}} — это дискретная случайная переменная, принимающая одно из N {displaystyle N} значений ( 1 … N ) {displaystyle (1ldots N)} . Будем полагать, что данная модель Маркова, определённая как P ( Q t ∣ Q t − 1 ) {displaystyle P(Q_{t}mid Q_{t-1})} , однородна по времени, то есть независима от t {displaystyle t} . Тогда можно задать P ( Q t ∣ Q t − 1 ) {displaystyle P(Q_{t}mid Q_{t-1})} как независящую от времени стохастическую матрицу перемещений A = { a i j } = p ( Q t = j ∣ Q t − 1 = i ) {displaystyle A={a_{ij}}=p(Q_{t}=jmid Q_{t-1}=i)} . Вероятности состояний в момент времени t = 1 {displaystyle t=1} определяется начальным распределением π i = P ( Q 1 = i ) {displaystyle pi _{i}=P(Q_{1}=i)} .

    Будем считать, что мы в состоянии j {displaystyle j} в момент времени t {displaystyle t} , если Q t = j {displaystyle Q_{t}=j} . Последовательность состояний выражается как q = ( q 1 , … , q T ) {displaystyle q=(q_{1},;ldots ,;q_{T})} , где q t ∈ { 1 … N } {displaystyle q_{t}in {1ldots N}} является состоянием в момент t {displaystyle t} .

    Наблюдение Y t {displaystyle Y_{t}} в момент времени t {displaystyle t} может иметь одно из L {displaystyle L} возможных значений, y t ∈ { o 1 , … , o L } {displaystyle y_{t}in {o_{1},;ldots ,;o_{L}}} . Вероятность заданного вектора наблюдений в момент времени t {displaystyle t} для состояния j {displaystyle j} определяется как b j ( o i ) = P ( Y t = o i ∣ Q t = j ) {displaystyle b_{j}(o_{i})=P(Y_{t}=o_{i}mid Q_{t}=j)} ( B = { b i j } {displaystyle B={b_{ij}}} — это матрица L {displaystyle L} на N {displaystyle N} ). Последовательность наблюдений y {displaystyle y} выражается как y = ( y 1 , … , y T ) {displaystyle y=(y_{1},;ldots ,;y_{T})} .

    Следовательно, мы можем описать скрытую модель Маркова с помощью λ = ( A , B , π ) {displaystyle lambda =(A;,B,;pi )} . При заданном векторе наблюдений y {displaystyle y} алгоритм Баума — Велша находит λ ∗ = a r g max λ P ( y ∣ λ ) {displaystyle lambda ^{*}=argmax _{lambda }P(ymid lambda )} . λ ∗ {displaystyle lambda ^{*}} максимизирует вероятность наблюдений y {displaystyle y} .

    Алгоритм

    Исходные данные: λ = ( A , B , π ) {displaystyle lambda =(A,;B,;pi )} со случайными начальными условиями.

    Алгоритм итеративно обновляет параметр λ {displaystyle lambda } до схождения в одной точке.

    Прямая процедура

    Обозначим через α i ( t ) = p ( Y 1 = y 1 , … , Y t = y t , Q t = i ∣ λ ) {displaystyle alpha _{i}(t)=p(Y_{1}=y_{1},;ldots ,;Y_{t}=y_{t},;Q_{t}=imid lambda )} вероятность появления заданной последовательности y 1 , … , y t {displaystyle y_{1},;ldots ,;y_{t}} для состояния i {displaystyle i} в момент времени t {displaystyle t} .

    α i ( t ) {displaystyle alpha _{i}(t)} можно вычислить рекурсивно:

  • α i ( 1 ) = π i ⋅ b i ( y 1 ) ; {displaystyle alpha _{i}(1)=pi _{i}cdot b_{i}(y_{1});}
  • α j ( t + 1 ) = b j ( y t + 1 ) ∑ i = 1 N α i ( t ) ⋅ a i j . {displaystyle alpha _{j}(t+1)=b_{j}(y_{t+1})sum _{i=1}^{N}{alpha _{i}(t)cdot a_{ij}}.}
  • Обратная процедура

    Данная процедура позволяет вычислить β i ( t ) = p ( Y t + 1 = y t + 1 , … , Y T = y T ∣ Q t = i , λ ) {displaystyle eta _{i}(t)=p(Y_{t+1}=y_{t+1},ldots ,Y_{T}=y_{T}mid Q_{t}=i,lambda )} вероятность конечной заданной последовательности y t + 1 , … , y T {displaystyle y_{t+1},;ldots ,;y_{T}} при условии, что мы начали из исходного состояния i {displaystyle i} , в момент времени t {displaystyle t} .

    Можно вычислить β i ( t ) {displaystyle eta _{i}(t)} :

  • β i ( T ) = p ( Y T = y T ∣ Q t = i , λ ) = 1 ; {displaystyle eta _{i}(T)=p(Y_{T}=y_{T}mid Q_{t}=i,lambda )=1;}
  • β i ( t ) = ∑ j = 1 N β j ( t + 1 ) a i j b j ( y t + 1 ) . {displaystyle eta _{i}(t)=sum _{j=1}^{N}{eta _{j}(t+1)a_{ij}b_{j}(y_{t+1})}.}
  • Используя α {displaystyle alpha } и β {displaystyle eta } можно вычислить следующие значения:

    • γ i ( t ) ≡ p ( Q t = i ∣ y , λ ) = α i ( t ) β i ( t ) ∑ j = 1 N α j ( t ) β j ( t ) , {displaystyle gamma _{i}(t)equiv p(Q_{t}=imid y,;lambda )={frac {alpha _{i}(t)eta _{i}(t)}{displaystyle sum _{j=1}^{N}alpha _{j}(t)eta _{j}(t)}},}
    • ξ i j ( t ) ≡ p ( Q t = i , Q t + 1 = j ∣ y , λ ) = α i ( t ) a i j β j ( t + 1 ) b j ( y t + 1 ) ∑ i = 1 N ∑ j = 1 N α i ( t ) a i j β j ( t + 1 ) b j ( y t + 1 ) . {displaystyle xi _{ij}(t)equiv p(Q_{t}=i,;Q_{t+1}=jmid y,;lambda )={frac {alpha _{i}(t)a_{ij}eta _{j}(t+1)b_{j}(y_{t+1})}{displaystyle sum _{i=1}^{N}displaystyle sum _{j=1}^{N}alpha _{i}(t)a_{ij}eta _{j}(t+1)b_{j}(y_{t+1})}}.}

    Имея γ {displaystyle gamma } и ξ {displaystyle xi } , можно вычислить новые значения параметров модели:

    • π ¯ i = γ i ( 1 ) , {displaystyle {ar {pi }}_{i}=gamma _{i}(1),}
    • a ¯ i j = ∑ t = 1 T − 1 ξ i j ( t ) ∑ t = 1 T − 1 γ i ( t ) , {displaystyle {ar {a}}_{ij}={frac {displaystyle sum _{t=1}^{T-1}xi _{ij}(t)}{displaystyle sum _{t=1}^{T-1}gamma _{i}(t)}},}
    • b ¯ i ( o k ) = ∑ t = 1 T δ y t , o k γ i ( t ) ∑ t = 1 T γ i ( t ) . {displaystyle {ar {b}}_{i}(o_{k})={frac {displaystyle sum _{t=1}^{T}delta _{y_{t},;o_{k}}gamma _{i}(t)}{displaystyle sum _{t=1}^{T}gamma _{i}(t)}}.} ,

    где

    δ y t , o k = { 1 если  y t = o k , 0 иначе {displaystyle delta _{y_{t},;o_{k}}={egin{cases}1&{ ext{если }}y_{t}=o_{k},&{ ext{иначе}}end{cases}}}

    индикативная функция, и b i ∗ ( o k ) {displaystyle b_{i}^{*}(o_{k})} ожидаемое количество значений наблюдаемой величины, равных o k {displaystyle o_{k}} в состоянии i {displaystyle i} к общему количеству состояний i {displaystyle i} .

    Используя новые значения A {displaystyle A} , B {displaystyle B} и π {displaystyle pi } , итерации продолжаются до схождения.



    Имя:*
    E-Mail:
    Комментарий: