바움-웰치 알고리즘

전기공학, 통계 컴퓨팅 및 생물정보학에서 바움-웰치 알고리즘은 숨겨진 마르코프 모델(HM)의 알려지지 않은 파라미터를 찾는 데 사용되는 전자파 알고리즘의 특수한 경우로, 전진 알고리즘을 사용하여 기대 단계를 위한 통계를 계산한다.

역사

더 바움-웰치 알고리즘은 발명가 레오나드 E. 바움과 로이드 R의 이름을 따서 명명되었다. 웰치. 이 알고리즘과 히든 마코프 모델은 바움과 그의 동료들이 1960년대 말과 1970년대 초 국방분석연구소에 기고한 일련의 기사에서 처음 설명되었다.^[1]HMMs의 첫 번째 주요 적용 분야 중 하나는 언어 처리 분야였다.^[2]1980년대에 HMHs는 생물학적 시스템과 정보, 특히 유전 정보의 분석에 유용한 도구로 부상하고 있었다.^[3]그들은 그 이후로 게놈 서열의 확률론적 모델링에서 중요한 도구가 되었다.^[4]

설명

숨겨진 마르코프 모델은 "숨겨진" 변수와 관측된 이산 랜덤 변수의 집합의 결합 확률을 설명한다.(i - 1)번째 숨김 변수가 주어진 i번째 숨김 변수는 이전의 숨김 변수와 독립적이라는 가정에 의존하고 있으며, 현재 관측 변수는 현재 숨김 상태에만 의존한다.

더 바움-Welch 알고리즘은 잘 알려진 전자파 알고리즘을 사용하여 관측된 형상 벡터 집합이 주어진 숨겨진 마르코프 모델의 파라미터의 최대우도 추정치를 찾는다.

$X{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$ 가능한$$ $값{\displaystyle }$(즉, 총 N ${\displaystyle N}$ 상태가$$ $있다고{\displaystyle }$ 가정함)을 갖는 이산형 숨겨진 랜덤 변수가 되도록$$ 한다.$P{\displaystyle ({}_{}}$ ${\displaystyle t_{}}$ ${\displaystyle {}_{}}$ X ${\displaystyle t_{}}$- ${\displaystyle 1_{}}$) ${\displaystyle P(X_{t}\mid X_{t-1})$가 시간 $t{\displaystyle }$ ${\displaystyle t}$과(와) 무관하다고 가정하며$,$ 이는 시간 독립적 확률적 전환 매트릭스의 정의로 이어진다.

${\displaystyle A=\{a_{ij}\}\}=P(X_{t}=j\mid X_{t-1}=i).}$

초기 상태 분포($예{\displaystyle }$: t${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle t=1$는 다음에 의해 제공됨

${\displaystyle \pi _{i}=P(X_{1}=i).}$

관측 변수 $Y{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$는 $K$ ${\displaystyle K}$ 가능한 값 중 하나를 취할 수 있다$$.우리는 또한 "숨겨진" 상태가 시간 독립적이라고 가정한다.상태 $X{\displaystyle {}_{}}$ ${\displaystyle t_{}}$= ${\displaystyle j}$ ${\displaystyle X_{t}=j}$에 대한 $시간{\displaystyle }$t {\$displaystyle t}$에서 특정 관측치 ${\displaystyle y_{}}$ ${\$의 확률은 다음과$$ 같다.

${\displaystyle b_{j}(y_{i})=P(Y_{t}=y_{t}=y_{i}\mid X_{t}=j).}$

$Y{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$ 및$$ ${\displaystyle X_{}}$ t ${\$ $X_$${t}$의 가능한 모든 값을 고려하여$$$N{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle K}$ ${\displaystyle$ N$\\times K}$ $행렬$ B${\displaystyle }$=${\displaystyle }${${\displaystyle {bj}_{}{}_{}}$ $){b_{j}(y_{i})$를 구한다.$\}}}$여기서$$ $b{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$는 가능한 모든 상태에 속하며$$ $y{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$는 모든 관측치에 속한다$$.

관측 순서는 $Y{\displaystyle }$= (${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= y ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{Y\mathrm{}}_{}}$ ${\displaystyle {}_{}}$= y ${\displaystyle {2\mathrm{}}_{}}$, ${\displaystyle \dots ,}$ ${\displaystyle Y_{}}$ ${\displaystyle {}_{}}$= y ${\displaystyle T_{}}$) ${\displaystyle Y=(Y_{1}=y_{1}},$ {1},$Y_{2}=y_{2},\ldots,Y_{T}=y_{T$

따라서 우리는 숨겨진 마코프 체인을 $\theta {\displaystyle }$=${\displaystyle }$(${\displaystyle A,}$ ${\displaystyle B,}$ $){\displaystyle \theta$ = $(A,B,\pi )}$로 설명할 수 있다$.$더 바움-Welch algorithm finds a local maximum for ${\displaystyle \theta ^{*}=\operatorname {arg\,max} _{\theta }P(Y\mid \theta )}$ (i.e. the HMM parameters ${\displaystyle \theta }$ that maximize the probability of the observation).^[5]

알고리즘.

임의의 초기 조건을 사용하여$$ $\theta {\displaystyle }$=${\displaystyle }$( ${\displaystyle A,}$ B${\displaystyle ,}$ ${\displaystyle \pi }$) ${\displaystyle \theta =(A,B,\pi )}$을(를) 설정하십시오.또한 매개변수가 사용 가능한 경우 매개변수에 대한 사전 정보를 사용하여 설정할 수 있다. 이것은 알고리즘의 속도를 높이고 원하는 로컬 최대값으로 조종할 수 있다.

전진 절차

Let ${\displaystyle \alpha _{i}(t)=P(Y_{1}=y_{1},\ldots ,Y_{t}=y_{t},X_{t}=i\mid \theta )}$, the probability of seeing the observations ${\displaystyle y_{1},y_{2},\ldots ,y_{t}}$ and being in state ${\displaystyle i}$$$ $시간{\displaystyle }$ t ${\displaystyle t}$에$.$이는 다음과 같이 반복적으로 발견된다.

1. ${\displaystyle \pi _{i}(1)=\pi _{i}b_{i}(y_{1}),}$
2. ${\displaystyle \alpha _{i}(t+1)=b_{i}(y_{t+1})\sum _{j=1}^{N}\alpha _{j}(t)a_{ji}.}$

이 시리즈는 기하급수적으로 0으로 수렴되기 때문에 알고리즘은 더 긴 시퀀스에 대해 숫자로 밑돌게 된다.^[6]단, 약간 수정된 알고리즘에서는 포워드의$$ $\alpha {\displaystyle }$ ${\displaystyle \alpha }$과(와) 아래의 후진 절차의$$ $\beta {\displaystyle }${\$displaystyle$ \$beta }$을(를) 스케일링하여 이를 방지할 수 있다.

후진 절차

$\beta {\displaystyle {}_{}}$ ${\displaystyle i_{}}$( ${\displaystyle t}$)${\displaystyle }$= P${\displaystyle }$(${\displaystyle Y_{}}$ t${\displaystyle {}_{}}$+ ${\displaystyle 1_{}{}_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$+ 1${\displaystyle {}_{}}$,${\displaystyle }$… ,${\displaystyle }$Y ${\displaystyle T_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle T_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$= i ,${\displaystyle \theta }$) ${\displaystyle \beta$ \beta $_{i}(t)=P(Y_{t+1}=y_{t+1},\ldots,Y_{T}=}y_${{T}y_{{{{{}}}}}y_$}$y_}}}}}y_{{{{{{{{{{{}}}}}}}}}}}}}}}$T}\mid X_{t}=i,\teta )}$은(는) 종료 부분 시퀀스 $y{\displaystyle {}_{}}$ ${\displaystyle t_{}}$+ ${\displaystyle 1_{}}$,${\displaystyle {}_{}\dots ,}$ y ${\displaystyle T_{}}$ ${\$의 확률이다.$T}}$ 시간 $t{\displaystyle }$ ${\displaystyle t}$에서 시작 $상태{\displaystyle }$ i ${\displaystyle i}$을(를) 지정$.$ $\beta {\displaystyle {}_{}}$ i${\displaystyle {}_{}}$( ${\displaystyle t_{}}$) ${\displaystyle \beta _{i}(t)$을 다음과$$ 같이 계산한다.

1. ${\displaystyle \beta _{i}(T)=1,}$
2. ${\displaystyle \beta \{i}(t)=\sum _{j=1}^{N}\beta_{ij}b_{j}(y_{t+1}).}$

갱신하다

베이즈의 정리에 따라 우리는 이제 임시 변수를 계산할 수 있다.

${\displaystyle \gamma _{i}(t)=P(X_{t}=i\mid Y,\tta )={\frac {P(X_{t}=i,Y\mid \teta )}{P(Y\mid \teta )}}}}}={\frac {\frac _{i}(t)\beta _{i}(t)}{\sum _{j=1}^{j}(t)\j},}},},}$

즉, 관측된 시퀀스$$ $Y{\displaystyle }$ ${\displaystyle Y}$ 및 매개 변수 $\theta {\displaystyle }$ ${\displaystyle \theta}$이(가) $지정$된$$시간 t {\$displaystyle$ t$}$에서 $상태{\displaystyle }$ i ${\displaystyle i}$에 있을 확률임

${\displaystyle \xi_{ij}(t)=P(X_{t}=i,X_{t+1}=j\mid Y,\tta )={\frac(X_{t}=i,X_{t+1}=j,Y\mid \theta )}{P(Y\mid \theta )}}={\frac {\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})}{\sum _{k=1}^{N}\sum _{w=1}^{N}\alpha _{k}(t)a_{kw}\beta _{w}(t+1)b_{w}(y_{t+1})}},}$

관측된 시퀀스 $Y{\displaystyle }$ ${\displaystyle y}$과(와$$$)$ ${\displaystyle \mathrm{파라미터}}$ $\theta {\displaystyle }$ ${\$displaystyle t$}$및 $t{\displaystyle }$+ 1 ${\displaystyle t+1}$에서 각각 $상태{\displaystyle }$ i ${\displaystyle i}$과 j ${\$$displaystyta }$에 있을 확률이다$.$

$\gamma {\displaystyle {}_{}}$ ${\displaystyle i_{}}$( ${\displaystyle t}$) ${\displaystyle \gamma _{i}(t)}$과 $\xi {\displaystyle {}_{}}$ ${\displaystyle i_{}}$ j ${\displaystyle {}_{}t)}$의 분모는 같다$$$;$ $\theta {\displaystyle }$ ${\$$displaystyle$ $\$$xi _{ij}(t$$)}$의 매개변수가 주어지는$$ $관측치{\displaystyle }$ Y ${\\$$displaystystyle$ Y$}$의 확률을 나타낸다$.$

숨겨진 Markov 모델 $\theta {\displaystyle }$ ${\displaystyle \theta }$의 매개 변수를 이제 업데이트할 수 있다$$.

• ${\displaystyle \pi _{i}^{*}=\filename _{i}(1),}$

즉, $상태{\displaystyle \mathrm{}}$ $i{\displaystyle }$ ${\displaystyle$ i}에서$$시간 1 ${\displaystyle 1}$에 사용된 예상 빈도 입니다$.$

• ${\displaystyle a_{ij}^{*}={\frac {\sum _{t=1}^{T-1}\xi _{ij}(t)}{\sum _{t=1}^{T-1}\gamma _{i}(t)},},},}$

즉, 상태 i에서 상태 j로의 전환이 예상된 총 전환 횟수와 비교된다.명확히 하자면, 상태 i에서 벗어난 전환의 수는 다른 상태 j로의 전환을 의미하는 것이 아니라 자신을 포함한 어떤 상태로의 전환을 의미한다.이는 t = 1 ~ t = T - 1의 순서로 상태 i가 관측되는 횟수와 동일하다.

• ${\displaystyle b_{i}^{*}{*}(v_{k})={\frac {\sum_{t=1}^{T}1_{t_{t}=v_{k}}\gamma _{i}}}{t=1}^{\sum _{t=1}^{{{}}}}}}}}}}}}}}}}}}}}}}}}}}^{{{{}}}}}}}}}}}}T}\감마 _{i}(t)},}$

어디에

${\displaystyle 1_{y_{t}=v_{k}}={\prease}1&{\text}{{t}=v_{k},\0&{\text}}\case}}}}}}$

표시기 함수로서 b${\displaystyle {}_{}^{}}i{\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ($v$ k ) {\$displaystyle$$b_$${i}^{*}(v_{k}})$는 상태 $i{\displaystyle }$ ${\$displaystyle $v_{k$$\}$에서 예상되는 총 횟수에 걸쳐$$ 출력 관측치가 ${\displaystyle {vk}_{}}$ ${\$$displaystystyle v_${k$}}}}}}$과 동일한 횟수임$$.

이 단계들은 이제 원하는 수준의 수렴이 이루어질 때까지 반복적으로 반복된다.

참고: 특정 데이터 세트를 오버핏할 수 있다.즉, ( ∣ )> ( ∣ $){\displaystyle P ($Y$\mid \theta _{\text${final$})>P (Y\mid \theta _{\text{true$알고리즘도 글로벌 최대값을 보장하지는 않는다.

다중 시퀀스

The algorithm described thus far assumes a single observed sequence ${\displaystyle Y=y_{1},\ldots ,y_{N}}$. However, in many situations, there are several sequences observed: ${\displaystyle Y_{1},\ldots ,Y_{R}}$. In this case, the information from all of the observed sequences must be used in the update of the parameters ${\displaystyle A}$, ${\displaystyle \pi }$, and ${\displaystyle b}$. Assuming that you have computed ${\displaystyle \gamma _{ir}(t)}$ and ${\displaystyle \xi _{ijr}(t)}$ for each sequence ${\displaystyl$$e y_{1,r},\ldots ,y_{N_{r},r$ 이제 매개변수를 업데이트할 수 있다.

• ${\displaystyle \pi _{i}^{*}={\frac {\sum _{r=1}^{R}\감마 _{ir}(1){R}}}}}}$
• ${\displaystyle a_{ij}^{*}={\frac {\sum _{r=1}^{R}\sum _{t=1}^{T-1}\xi _{ijr}(t)}{\sum _{r=1}^{R}\sum _{t=1}^{T-1}\gamma _{ir}(t)}},}$
• ${\displaystyle b_{r=1}^{{k}}={\frac {\sum _{r=1}^{R}\sum _{t=1}^{T}1_{t}=1}{t}}=v_{k}}}}}\gamma _{\sum _{r=1}{t=1}^}}^}T}\감마 _{ir}(t)},}$

어디에

${\displaystyle 1_{y_{tr}=v_{k}}}={\prease}1&{\text}{{t}}{{text}}{r}=v_{k}}\0&{\text}\end{case}}}}}}}}$

지시함수다.

예

우리가 매일 정오에 달걀을 수집하는 닭을 가지고 있다고 가정합시다.이제 닭이 채집을 위해 알을 낳았는지 아닌지는 숨겨진 몇 가지 알려지지 않은 요인에 달려 있다.그러나 우리는 (단순히) 닭이 알을 낳는지 여부에 영향을 미치는 두 개의 상태 중 하나에 항상 닭이 있고, 이 상태는 전날의 상태에만 의존한다고 가정할 수 있다.이제 우리는 초기 시작점의 상태를 알 수 없고, 두 상태 사이의 전환 확률을 알 수 없으며, 닭이 특정한 상태를 부여받은 달걀을 낳을 확률을 알 수 없다.^[7][8]우선 우리는 전환과 배출 매트릭스를 추측한다.

전이 상태 1 상태 2 상태 1 0.5 0.5 상태 2 0.3 0.7

배출 노 에그스 달걀 상태 1 0.3 0.7 상태 2 0.8 0.2

이니셜 상태 1 0.2 상태 2 0.8

그런 다음 일련의 관측치를 취한다(E = 달걀, N = 없음): N, N, N, N, N, E, E, N, N, N

이는 일 간에 관찰된 일련의 전환(NN, NN, NN, NN, NN, NE, EE, EN, NN, NN)을 제공한다.

다음 단계는 새로운 전환 행렬을 추정하는 것이다.For example, the probability of the sequence NN and the state being ${\displaystyle S_{1}}$ then ${\displaystyle S_{2}}$ is given by the following, ${\displaystyle P(S_{1})*P(N S_{1})*P(S_{1}\rightarrow S_{2})*P(N S_{2}).$$}$

관측순서	상태가 S ${\displaystyle {1\mathrm{}}_{}}$ ${\$}이고$$ S $2{\displaystyle {}_{}}$ {\$displaystyle S_{2$}}인 경우 해당 시퀀스를 관측할 가장 높은 확률	해당 시퀀스를 관측할 수 있는 가장 높은 확률
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${\displaystyle S_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${\displaystyle S_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${\displaystyle S_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${\displaystyle S_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}
NE	0.006 = 0.2 * 0.3 * 0.5 * 0.2	0.1344	${\displaystyle S_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$
EE	0.014 = 0.2 * 0.7 * 0.5 * 0.2	0.0490	${\displaystyle S_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$
EN	0.056 = 0.2 * 0.7 * 0.5 * 0.8	0.0896	${\displaystyle S_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${\displaystyle S_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}
NN	0.024 = 0.2 * 0.3 * 0.5 * 0.8	0.3584	${\displaystyle S_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}
합계	0.22	2.4234

따라서 S ${\$}에서$$ S ${\displaystyle 2_{}}$까지${\$}}회$$ 전환에 대한 새로운 추정치는 $현재{\displaystyle \frac{\mathrm{}}{}}$0.${\displaystyle \frac{22.4234}{}}$=${\displaystyle 0.0908}$ ${\frac {0.222}{2.4234}}=0.0908}($다음 표에서 "의사 확률"이라고 한다).그런$$ 다음 $S{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}} ~ S$$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$ $S_{1$ $S$ {\$displaystyle S_{$2}} ~ S ${\displaystyle {2\mathrm{}}_{}}$ ${\$displaystyle S_{1}$$및$$ S ${\displaystyle {1\mathrm{}}_{}}$ ${\$} 변환$$$$ 확률을 계산하여 1에 추가한다.이는 업데이트된 전환 매트릭스를 제공한다.

이전 전환 매트릭스 상태 1 상태 2 상태 1 0.5 0.5 상태 2 0.3 0.7

새 전환 행렬(의사 확률) 상태 1 상태 2 상태 1 0.0598 0.0908 상태 2 0.2179 0.9705

새 전환 매트릭스(정상화 후) 상태 1 상태 2 상태 1 0.3973 0.6027 상태 2 0.1833 0.8167

다음으로, 우리는 새로운 배출 매트릭스를 추정하고자 한다.

관측된 시퀀스	해당 시퀀스를 관측할 수 있는 가장 높은 확률 E가 $S{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}에서 왔다고 가정할 경우		해당 시퀀스를 관측할 수 있는 가장 높은 확률
NE	0.1344	${\displaystyle S_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$	0.1344	${\displaystyle S_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$
EE	0.0490	${\displaystyle S_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$	0.0490	${\displaystyle S_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$
EN	0.0560	${\displaystyle S_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}	0.0896	${\displaystyle S_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}
합계	0.2394		0.2730

$S{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$배출량에서$$ 오는 E의 새로운 추정치는 현재 0${\displaystyle \frac{.2394}{}}$ ${\displaystyle \frac{0.2730}{}}$= 0.${\displaystyle 2769}$ ${\displaystyle {\frac$ {$0.2394}{0.2730}}=0.8769}$이다$.$

이를 통해 각각의 관측된 시퀀스에 대한 확률을 더함으로써 알고리즘에 위에서 설명한 대로 방출 행렬을 계산할 수 있다.그런 다음 N이 $S{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}에서 왔는지, N과$$ E가 ${\displaystyle {S\mathrm{}}_{}}$ 2 ${\$}}에서 왔는지 반복하고$$ 정상화한다.

이전 배기 매트릭스 노 에그스 달걀 상태 1 0.3 0.7 상태 2 0.8 0.2

새 배기 매트릭스(추정) 노 에그스 달걀 상태 1 0.0404 0.8769 상태 2 1.0000 0.7385

새 배기 매트릭스(정상화 후) 노 에그스 달걀 상태 1 0.0441 0.9559 상태 2 0.5752 0.4248

초기 확률을 추정하기 위해 우리는 모든 시퀀스가 숨겨진 상태 ${\displaystyle {S\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$ ${\$}로 시작하고$$ 가장 높은 확률을 계산한 다음 ${\displaystyle {S\mathrm{}}_{}}$ 2 ${\$}}에 대해 반복한다고 가정한다$.$ 다시 우리는 정상화한 다음 업데이트된 초기 벡터를 제공한다.

마지막으로 우리는 결과 확률이 만족스럽게 수렴될 때까지 이러한 단계를 반복한다.

적용들

음성인식

히든 마르코프 모델은 제임스 K의 음성 인식에 처음 적용되었다. 1975년 ^[9]베이커연속 음성 인식은 HMM에 의해 모델링된 다음 단계에 의해 발생한다. 형상 분석은 먼저 음성 신호의 시간적 및/또는 스펙트럼 특성에 대해 수행된다.이것은 관측 벡터를 생성한다.그런 다음 이 특성은 음성 인식 장치의 모든 시퀀스와 비교된다.이러한 단위는 음운, 음절 또는 전체 단어 단위가 될 수 있다.조사 경로를 제약하기 위해 어휘소 해독 시스템을 적용하므로, 시스템의 어휘소(단어 사전)에 있는 단어만 조사한다.어휘소 해독과 유사하게, 시스템 경로는 문법과 구문의 규칙에 의해 더욱 제약을 받는다.마지막으로 의미분석을 적용하고 시스템이 인식된 발언을 출력한다.많은 HMM 응용 프로그램이 음성 인식에 대한 제한은 현재의 상태가 이전 시간 단계의 상태에만 의존한다는 것이다. 이는 의존성이 종종 지속 기간에 여러 시간 단계이기 때문에 말하기에 비현실적이다.^[10]더 바움-웰치 알고리즘은 음성 합성 분야에서 사용되는 HMM을 해결하는 데에도 광범위한 응용을 가지고 있다.^[11]

암호해석

더 바움-웰치 알고리즘은 숨겨진 정보나 소음이 많은 정보를 해독하는 데 HMMs의 파라미터를 추정하는 데 자주 사용되며, 결과적으로 암호해석에도 자주 사용된다.데이터 보안에서 관찰자는 전송의 모든 매개변수를 알지 못한 채 데이터 스트림에서 정보를 추출하고자 한다.이것은 채널 인코더 역 엔지니어링을 수반할 수 있다.^[12]MHMs and 그 결과 Baum-Welch 알고리즘은 또한 암호화된 VoIP 통화에서 구문을 식별하는 데 사용되었다.^[13]또한 HMM 암호 분석은 캐시 타이밍 데이터의 자동화된 조사를 위한 중요한 툴이다.키 값과 같은 중요한 알고리즘 상태의 자동 검색을 허용한다.^[14]

생물정보학 응용 프로그램

유전자 찾기

프로카리오틱

GLIMMER(Gene Locator and Interpolated Markov ModelER) 소프트웨어는 친핵 DNA에서 코딩 영역을 식별하는 데 사용된 초기 유전자 조사 프로그램이었다.^[15][16] GLYMER은 인터폴화된 마코프 모델(IMM)을 사용하여 코딩 영역을 식별하고 코딩되지 않은 DNA와 구분한다.이번 출시(GLIMMER3)는 번역 개시 사이트 예측과 관련해 이전 버전보다 구체성과 정확도가 높아져 원핵생물에서 확인된 유전자에 비해 평균 99%의 정확도를 보였다.^[17]

진핵의

GENSCAN 웹서버는 최대 100만 개의 염기서열(1Mbp)까지 진핵 서열을 분석할 수 있는 유전자 로케이터다.^[18]GENSCAN은 DNA 부위의 세 가지 주기적인 다섯 번째 순서인 일반 비균형 마르코프 모델을 이용한다.또한 이 모델은 서로 다른 등골에서 발생하는 유전자 밀도와 구조(예를 들어 인트론 길이)의 차이를 설명한다.대부분의 통합 유전자 탐색 소프트웨어(GENSCANs 출시 당시)는 입력 시퀀스가 정확히 하나의 유전자를 포함하고 있다고 가정했지만, GENSCAN은 부분적, 완전적 또는 복수의 유전자(또는 아예 유전자가 존재하지 않는)가 존재하는 일반적인 경우를 해결한다.^[19]GENSCAN은 주석이 달린 데이터베이스에 비해 90%의 정확도와 80%의 특수성으로 exon 위치를 정확하게 예측하는 것으로 나타났다.^[20]

복사 번호 변동 탐지

CNV(복사 번호 변이)는 인간에게 게놈 구조 변동의 풍부한 형태다.이산값 이변량 HMM(dbHM)을 사용하여 염색체 영역을 영향을 받지 않는 영역, 삭제, 중복 및 4개의 전환 상태 등 7개의 구별되는 상태에 할당했다.Baum-Welch를 사용하여 이 모델을 풀면서 마이크로 어레이 실험을 통해 CNV 중단점의 위치를 약 300bp까지 예측할 수 있는 능력을 입증했다.^[21]이 분해능의 크기는 이전에 가능했던 것보다 서로 다른 CNV와 모집단 간에 더 정밀한 상관관계를 가능하게 하여 CNV 모집단 주파수의 연구를 가능하게 한다.또한 특정 CNV에 대한 직접적인 상속 패턴을 입증했다.

구현

• 어코드.NET in C#
• ghmm C 라이브러리, 이산형 및 연속형 방출을 모두 지원하는 Python 바인딩.
• 줄리아를 위한 HMMBase 패키지.
• R용 RHmm 패키지의 HMFit 기능.
• MATLAB의 음트레인
• 러스트의 러스트비오

참고 항목

• 비테르비 알고리즘
• 히든 마르코프 모델
• 전자파 알고리즘
• 최대우도
• 음성인식
• 생물정보학
• 암호해석

참조

외부 링크

• 생물정보학에서 HMM 방법과 소프트웨어에 대한 포괄적인 검토 – 프로파일 Hidden Markov 모델
• Baum의 초기 HMM 출판물:
  • 마르코프 체인의 확률론적 함수의 통계적 해석에서 나타나는 극대화 기법
  • 마르코프 공정의 확률적 기능에 대한 통계적 추정과 생태학적 모델에 대한 적용과의 불평등
  • 유한상태 마르코프 체인의 확률론적 기능에 대한 통계적 추론
• 알고리즘을 효율적으로 구현하는 방법을 설명하는 Welch의 Shannon 강의:
  • 히든 마르코프 모델과 바움-Welch 알고리즘, IEEE 정보 이론 협회 뉴스레터, 2003년 12월.
• 바움-바움의 대안Welch 알고리즘, Viterbi 경로 계산 알고리즘:
  • Davis, Richard I. A.; Lovell, Brian C.; "열차와 시험 및 조건 번호 기준을 사용한 HMM 앙상블 훈련 알고리즘 비교 및 평가", 패턴 분석 및 적용, 제6권, 제4권, 페이지 327–336, 2003.
• Forward-Backward 알고리즘을 교육하기 위한 대화형 스프레드시트(스프레드 시트 및 단계별 워크스루 포함 기사)
• 바움-바움 공식 유래웰치 알고리즘
• 바움-바움 구현웰치 알고리즘