순방향 및 Viterbi 알고리즘의 차이점은 무엇입니까?

먼저 약간의 배경 지식이 있으면 문제가 해결 될 수 있습니다. 약간.

HMM (Hidden Markov Models)에 대해 이야기 할 때 일반적으로 고려해야 할 3 가지 문제가 있습니다.

1. 평가 문제

   • 평가 문제는 특정 모델에서 특정 기호 시퀀스가 생성 될 확률은 얼마입니까?
   • 평가를 위해 순방향 알고리즘 또는 역방향 알고리즘 의 두 가지 알고리즘을 사용합니다 (순방향 알고리즘과 혼동하지 마십시오).
   • li>

2. 디코딩 문제

   • 디코딩 문제는 다음과 같은 질문에 답합니다. 일련의 기호 (관찰)와 모델이 주어지면 시퀀스를 생성 할 가능성이 가장 높은 상태 시퀀스는 무엇입니까?
   • 디코딩을 위해 Viterbi 알고리즘 을 사용합니다.

3. 학습 문제

   • 학습 문제는 질문에 답합니다. 모델 구조와 일련의 시퀀스가 주어지면 데이터에 가장 적합한 모델을 찾습니다. .
   • 이 문제에 대해 다음 3 가지 알고리즘을 사용할 수 있습니다.
     1. MLE (최대 가능성 추정)
     2. Viterbi 교육 (Viterbi 디코딩과 혼동하지 마십시오)
     3. Baum Welch = 정방향 알고리즘

요약하면 Viterbi 알고리즘을 사용하여 일련의 시퀀스에서 모델을 학습 할 때 디코딩 문제 및 Baum Welch / 앞뒤로.

Baum Welch 는 다음과 같은 방식으로 작동합니다.

훈련 시퀀스 세트의 각 시퀀스에 대해.

1. 순방향 알고리즘으로 순방향 확률 계산
2. 역방향 알고리즘으로 역방향 확률 계산
3. 모델의 전환에 대한 현재 시퀀스의 기여도를 계산하고 모델의 방출 확률에 대한 현재 시퀀스의 기여도를 계산합니다.
4. 새 모델 매개 변수 (시작 확률, 전환 확률, 방출 확률)를 계산합니다. )
5. 모델의 새 로그 가능성
6. 로그 가능성의 변경이 주어진 임계 값보다 작거나 최대 반복 횟수를 통과하면 중지합니다.

필요한 경우 Viterbi 디코딩에 대한 방정식과 훈련 알고리즘에 대한 전체 설명을 통해 알려 주시면 올바른 방향을 알려 드릴 수 있습니다.

댓글

• 안녕하세요. . 경로를 저장하면 전달 알고리즘을 사용하여 평가하는 동안 중복 디코딩에 Viterbi 알고리즘을 사용합니까?

앞으로 뒤로는 각 개별 상태 에 대한 한계 확률을 제공하고 Viterbi는 가장 가능성이 높은 상태 시퀀스 의 확률을 제공합니다. 예를 들어 HMM 작업이 매일 화창한 날씨와 비가 오는 날씨를 예측하는 것이라면 Forward Backward는 매일 “맑음”이 될 확률을 알려주고 Viterbi는 가장 가능성이 높은 화창한 / 비가 오는 날의 순서를 제공합니다. 이 순서의 확률입니다.

다음 두 슬라이드는 {2}에서 앞으로 나아갈 수있는 좋은 위치에 있습니다. -backward 및 Viterbi 알고리즘 : HMM과 함께 사용되는 다른 모든 일반적인 알고리즘 중 :

참고 :

• $ x $는 관측 된 방출이고, $ \ pi $는 HMM의 매개 변수입니다.
• 경로 = 일련의 방출
• 디코딩 = 추론
• 학습 = 교육 = 매개 변수 추정
• 일부 논문 (예 : {1})은 Baum–Welch가 순방향 알고리즘과 동일하다고 주장하지만 나는 agr ee with Masterfool 및 Wikipedia : Baum–Welch는 전진-후진 알고리즘을 사용하는 기대-최대화 알고리즘입니다. 또한 두 그림은 Baum–Welch와 순방향 알고리즘을 구별합니다.

참조 :

• {1} Lember, Jüri 및 Alexey Koloydenko. “숨겨진 마르코프 모델을위한 조정 된 Viterbi 훈련.” 베르누이 14, 아니. 1 (2008) : 180-206.
• {2} 6.047 / 6.878 Computational Biology : Genomes, Networks, Evolution (Fall 2012) Lecture 07-HMMs II (2012-09-29) http://stellar.mit.edu/S/course/6/fa12/6.047/courseMaterial/topics/topic2/lectureNotes/Lecture07_HMMsIIb_6up/Lecture07_HMMsIIb_6up.pdf (Manolis Kellis) :

모랏의 대답은 한 점에서 거짓입니다 : Baum -Welch는 HMM의 매개 변수를 학습시키는 데 사용되는 Expectation-Maximization 알고리즘입니다. 각 반복 동안 순방향-역방향 알고리즘을 사용 합니다. 순방향-역방향 알고리즘은 실제로 순방향 및 역방향 알고리즘의 조합입니다 : 한 번의 순방향 패스, 한 번의 역방향 패스. 그 자체로는 HMM의 매개 변수를 학습하는 데 사용되는 순방향 알고리즘이 아니라 평활화에만 사용됩니다. 상태 시퀀스의 한계 가능성을 계산합니다.

https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm

https://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm

@Yaroslav Bulatov가 정확한 답변을했습니다. 한 가지 예를 추가하여 앞뒤 알고리즘과 Viterbi 알고리즘의 차이

이 HMM (Wikipedia HMM 페이지에서)이 있다고 가정합니다. 참고, 모델은 이미 주어 졌으므로 여기에는 데이터 작업에 대한 학습 내용이 없습니다.

데이터가 길이 4 시퀀스라고 가정합니다. (Walk, Shop, Walk, Clean). 두 알고리즘이 서로 다른 것을 제공합니다.

• 앞으로 뒤로 알고리즘은 probabi를 제공합니다. 각 숨겨진 상태 . 여기에 예가 있습니다. 표의 각 열의 합계는 $ 1 $입니다.

몇 가지 데모 용 R 코드

library(HMM) # in education setting, # hidden state: Rainy and Sunny # observation: Walk, Shop, Clean # state transition P <- as.matrix(rbind(c(0.7,0.3), c(0.4,0.6))) # emission prob R <- as.matrix(rbind(c(0.1, 0.4, 0.5), c(0.6,0.3, 0.1))) hmm = initHMM(States=c("Rainy","Sunny"), Symbols=c("Walk","Shop", "Clean"), startProbs=c(0.6,0.4), transProbs=P, emissionProbs=R) hmm obs=c("Walk","Shop","Walk", "Clean") print(posterior(hmm,obs)) print(viterbi(hmm, obs))