hmm

hmm

1. Generation and Discreminent Model

• for input to labels

• 对于判别模型：条件概率分布

• 对于生成模型：联合概率分布

  • 其中表示先验，表示似然
  • where

• 预测：对于判别式模型

  ​ 对于生成式模型

2. Definition HMM

• HMM有两个独立性假设：

  • 观测序列之间是独立的 (A B 独立 有P(A, B) = P(A)P(B)，所以计算联合概率的时候才能用叠乘 )
  • 当前状态仅依赖于先前的状态

• Number of states = K, Number of observations = M

• ：Initial probabilities over states (K*K matrix)

• ：Transition probabilities (K*M matrix)

• Input , Output ​ that corresponds to

• Maximun a posterior inference(MAP inference)

• DP推导：

• 不用动态规划前，算法复杂度为​，即要遍历​的路径数量，使用动态规划后变为​，即对于每次迭代只需要计算k个联合概率，每个联合概率需要计算k次乘法，而迭代数为n次，所以时间复杂度如上

3. Vitebri Algorithm

• ​

• Initialization

  • for each hidden ​​​

• Recursion

  • for t = 2 to n, for each :
    • • 即t时刻隐藏状态j的联合概率为上一个状态转移的最大值所激发可见符号的概率
    • ​
      • 找到路径
  • End
• ​​
• for t=n-1 to 1(path back tracking)
  • $w^(t)=\psi_{w^(t+1)}(t+1)$
• end

4. Supervised learning details

• can be estimated separately just by counting

• s denotes label, x denotes word, n denotes the number of total words

• Initial prob

• Transition prob

• Emission prob

5. tri-gram markov

5.1 Vitebri Algorithm

• 每次需要计算k*k种组合的隐藏状态概率，每次计算需要k次乘法，最终复杂度为