Decoding问题可被我们描述为：
\[\begin{equation} \hat{I} = \arg\max_{I} P(I|O,\lambda) \end{equation}\]| 也就是在给定观察序列的情况下，寻找最大概率可能出现的隐概率状态序列。也有人说Decoding问题是预测问题，但是实际上这样说是并不合适的。预测问题应该是，$P(o_{t+1} | o_1,\cdots,o_t)$和$P(i_{t+1} | o_1,\cdots,o_t)$，这里的$P(i_{1},\cdots,i_t | o_1,\cdots,o_t)$看成是预测问题显然是不合适的。 |
Decoding Problem}
下面我们展示一下Hidden Markov Model的拓扑模型：
\[\begin{figure}[H] \centering \includegraphics[width=.5\textwidth]{微信图片_20200109224115.png} \caption{Hidden Markov Model的拓扑模型} \label{fig:my_label_1} \end{figure}\]这里实际上就是一个动态规划问题，这里的动态规划问题实际上就是最大概率问题，只不过将平时提到的最大距离问题等价于最大概率问题，理论上都是一样的。每个时刻都有$N$个状态，所有也就是从$N^T$个可能的序列中找出概率最大的一个序列，实际上就是一个动态规划问题，如下图所示：
\[\begin{figure}[H] \centering \includegraphics[width=.5\textwidth]{微信图片_20200109225254.png} \caption{Decoding的动态规划问题} \label{fig:my_label_1} \end{figure}\]我们假设：
\[\begin{equation} \delta_t(i) = \max_{i_1,\cdots,i_{t-1}} P(o_1,\cdots,o_t,i_1,\cdots,i_{t-1},i_t=q_i) \end{equation}\]这个等式是什么意思呢？也就是当$t$个时刻是$q_i$，前面$t-1$个随便走，只要可以到达$q_i$这个状态就行，而从中选取概率最大的序列。我们下一步的目标就是在知道$\delta_t(i)$的情况下如何求$\delta_t(i+1)$，那么这样就能通过递推来求得知道最后一个状态下概率最大的序列。$\delta_t(i+1)$的求解方法如下所示：
\[\begin{figure}[H] \centering \includegraphics[width=.35\textwidth]{微信图片_20200109230705.png} \caption{根据$\delta_t(i)$求解$\delta_t(i+1)$的方法示意图} \label{fig:my_label_1} \end{figure}\]所以，
\[\begin{equation} \begin{split} \delta_{t+1}(j) = & \max_{i_1,\cdots,i_{t}} P(o_1,\cdots,o_{t+1},i_1,\cdots,i_{t},i_{t+1}=q_j) \\ = & \max_{i_1,\cdots,i_{t}} \delta_t(i)\cdot a_{ij}\cdot b_j(o_{t+1}) \\ \end{split} \end{equation}\]这就是Viterbi算法，但是这个算法最后求得的是一个值，没有办法求得路径，如果要想求得路径，我们需要引入一个变量：
\[\begin{equation} \varphi_{t+1}(j) = \arg\max_{1\leq i \leq N}\delta_t(i)\cdot a_{ij}\cdot b_j(o_{t+1}) \end{equation}\]这个函数用来干嘛的呢？他是来记录每一次迭代过程中经过的状态的index。这样我们最终得到的${ \varphi_1,\varphi_2,\cdots,\varphi_T }$，就可以得到整个路径了。
FEATURED TAGS
Linear
Regression
Math
Basis
Exponential
Family
Distribution
Classification
Bayes
Background
Inference
Conclusion
Feedforward
Neural
Network
Support
Vector
Machine
Margin
and
Solution
Weak
Duality
Kernel
Method
of
Function
Probability
Graph
Markov
Variational
Algorithm
Belief
Process
Introduction
Gaussian
Expectation
Maximization
Mixture
Model
Chain
Monte
Carlo
Sampling
Hidden
Learning
Kalman
Filter
Conditional
Random
Field
Boltzmann
Deep
Generative
Adversarial
Reinforcement
Blog
docker
cuda
Agent
LLM
multimodel
RAG
文档智能
