algorithm - 三面骰子的隐马尔可夫模型

Question

我被教导 HMM 并给出了这个家庭作业问题。我理解了其中的一部分，但我不确定它是否正确。问题是:

Consider a different game where the dealer is not flipping a coin, but instead rolling a three-sided die with labels 1, 2, and 3. (Try not to think about what a three-sided die might look like.) The dealer has two loaded dice D1 and D2. For each die Di, the probability of rolling the number i is 1/2, and the probability of each of the other two outcomes is 1/4. At each turn, the dealer must decide whether to (1) keep the same die, (2) switch to the other die, or (3) end the game. He chooses (1) with probability 1/2 and each of the others with probability 1/4. At the beginning the dealer chooses one of the two dice with equal probability.

• Give an HMM for this situation. Specify the alphabet, the states, the transition probabilities, and the emission probabilities. Include a start state start, and assume that the HMM begins in state start with probability 1. Also include an end state end.

• Suppose that you observe the following sequence of die rolls: 1 1 2 1 2 2. Find a sequence of states which best explains the sequence of rolls. What is the probability of this sequence? Find the answer by completing the Viterbi table. Include backtrack arrows in the cells so you can trace back the sequence of states. Some of the following facts may be useful:

  log2(0) = −∞
  log2(1/4) = −2
  log2(1/2) = −1
  log2(1) = 0

• There are actually two optimal sequences of states for this sequence of die rolls. What is the other sequence of states?

如果我在第一部分没有错，我必须在这里做一些事情 http://en.wikipedia.org/wiki/Hidden_Markov_model#A_concrete_example但我没有得到从概率 1 开始的假设。

此外，我不确定在问题的第二部分我必须为 Viterbi 表做什么。如果有人能给我一些提示或线索，那就太好了。

Answer 1

假设您的起始概率是一个: 在 HMM 中，您要么有一个固定的起始状态，要么有一个所有状态的概率分布，它说明从状态 X 开始的可能性有多大。假设给定状态的起始概率为 1 等于第一个备选方案。

维特比算法: 在维特比矩阵中，第 i 行通常对应于第 i 个状态，第 j 列对应于您发出的符号的长度 j 的前缀。在每个条目中 (i,j) 是您已经看到前缀 j 并且您处于状态 i 的最大概率。

对于回溯，您需要跟踪每个 (i,j)-cell，其中最大前体参与了 (i,j)-cell 的计算。如果您有此信息，您可以从最后一列中具有最高值的单元格回溯到开头。反转这个回溯，你就得到了你的维特比路径。