HMM隐马尔可夫模型（HiddenMarkovmodel），HMM是一种非常流行的序列模型，广泛应用于语音识别等领域，也可以用于词性标注等文本问题和实体识别。时间序列数据时间序列数据（timeseriesdata）可以认为是沿着时间维度变化的数据，比如股票价格、温度、语音、文本等，时间序列数据的长度是不确定的。例如，如果两个人说同一句话，有些人可能会说得更快，而另一些人可能会说得更慢。所以当我们对这种数据应用逻辑回归或SVM时，实际上会丢失一些数据。图片、人的特征等非时序数据，我们在使用的时候，它的维度是固定的。时间序列模型包括传统机器学习角度的HMM和CRF，以及深度学习角度的RNN和LSTM。HMM模型介绍上图是一个经典的HMM模型结构，由上层的隐变量和下层的观测值组成。隐变量之间的传递称为状态转移，隐变量与观察值之间的传递称为状态生成，因此也是一种生成模型。你可以看到这个模型是一个有向的、生成的模型。HMM是一种概率图形模型。在\(t=1\)时刻：\(z_1\)表示一个状态，但是它有多个状态，说明每个状态都有对应的概率\(z_1\)到\(z_2\)，说明状态，从前一个状态到下一个状态的转移也有一个对应的概率\(z_1\)到\(x_1\)，说明在这个状态下产生了一个值，这个值也有不同的值（通常可以分为连续值和离散值），在这个状态下有一个相应的概率产生这个值。从上面的介绍不难知道HMM模型主要存在三个问题：一是在模型参数已知的情况下，对于任意的观察序列，推导出其背后的状态转移序列，这个问题也称为推理或解码。例如，如果这个序列用于语音识别，那么我们可以根据我们听到的音乐或人声来推断他说了哪些词或句子。第二个是给定观测值，我们预测或者估计整个模型的参数。第三种是计算一系列观测值的边际概率。应用示例词性标注（POS）当我们的问题变成词性标注时，我们关心的是：给定一个句子，知道观察（词）\（x_1到x_n\）是什么词性。可知本例中\(z_i\)是一个离散值。接下来，看看我们的三个主要问题：给定我们的句子，我们需要推导出其中每个单词的词性。这个问题也叫推理或译码问题（怎么解，维特比算法）。给定一句话后，我们如何估计模型的参数。\(p(x_1x_2...x_n)\)的概率是多少请看上面第二个问题的详细解释：参数\(\theta=(A,B,\pi)\)，A代表的部分speech转移概率（transitionprobability）：A是状态转移概率矩阵，也叫转移概率。我们需要知道，状态之间的转换并不是随机发生的，而是更有可能转移到其他状态。\(A_{m\timesm}\)，m表示词性（状态）的种类数，每行表示一个词性（状态），每行加起来为1。矩阵中的每个点表示从前一个词性（状态）转移到下一个词性（状态）的概率。B是生成概率（emissionprobability）：在\(z_1\)状态下，我们生成的词\(w_1\)是一定的词性概率，可以表示为概率矩阵\(B_{m\timesv}\),m表示词性的种类数，v表示词库的大小，每行表示每个词性对应词库中每个词的概率，各词性之和行是1。矩阵中的每个点代表在特定状态（在这种情况下是单词的词性）下看到观察结果（在这种情况下是单词）的概率。值得注意的是，生成的值也可以是连续值。对于连续变量，我们不能把它们写成矩阵的形式。在这种情况下，我们应该使用高斯混合（GMM）模型来处理它们。\(\pi\)表示某个词性（状态）出现在句子中第一个词（观测值）的概率：可以理解为\(\pi\)是一个初始化数组，即\(\pi=[\pi_1,\pi_2...\pi_i...\pi_m]\),在这个模型中和为1,\(x\to\theta\),这个过程叫做预测,参数估计;\(x\toz\)，这个过程称为infer，基于解决Viterbi算法预测的推理/解码问题：给定\(\theta=(A,B,\pi)\),\(x\)Sequence,deduce\(z\)tips：一般给一个问题，我们应该能想到最笨的方法，然后基于这个方法进行思考和优化。这是一般的解题过程。简单方法：假设我们的\(z_i\in\{a,b,c}\)，那么我们可以写出所有的状态转移序列，然后根据下面的公式（1）计算似然概率$$p(z_1))p(z_2|z_1)p(z_3|z_2)...p(z_{n-1}|z_n)p(x_1|z_1)p(x_2|z_2)...p(x|z_n)\标签{1}$$我们可以用上面的公式（1）来计算所有状态转移序列的似然概率，但是缺点也很明显，就是计算的时间复杂度是指数级的，计算量很大大，所以我不得不考虑其他更有效的方法，例如动态规划。动态规划算法适用于一开始的那种指数复杂度。但是我通过存储中间过程来减少计算量，这是动态规划的核心。维特比算法就是这样一种算法。但实际上维特比算法在这里有效还有其他因素，那就是像HMM这样的模型是有限制的。限制是我们的隐变量\(z_i\)只会跟前面的隐变量\(z_{i-1}\)相连，只有这样才能大大减少计算量。假设如果我们的\(z_i\)满足网络图或者完全图，即每个节点都与其他节点相连，即使我们使用维特比算法也不能减少计算量。维特比算法下面是维特比计算过程中的流程图：\(1-m\)表示每个隐藏变量可以取的状态，共有\(m\)种，\(z_1-z_n\)表示隐藏variables,也对应时间\(t\)现在用上图来考虑我们的问题，给定一个序列\(x_i\)，我们需要确定最好的\(z_i\)，也就是我们需要确定上图中红线这样标示的最佳路径。当我们的路径确定了，我们的\(z_i\)也就确定了。下面我们来看看如何计算这样一条路径的概率：$$\begin{equation}\begin{split}probability&=p(z_1=2)\cdotp(x_1|z_1=2)\cdotp(z_2=1|z_1=2)\cdot\\&p(x_2|z_2=1)\cdot...\cdotp(z_n=j|z_{n-1}=j+1)\cdotp(x_n|z_n=j)\end{split}\end{equation}\tag{2}$$其中，整个概率计算公式其实就是由这三部分组成，1其实就是参数\(\pi\)，2就是transitionprobability,3是一个Observationmodel，刚好对应参数\(\theta\)。接下来，使用递归公式：定义\(\delta_k(i)\):=在时间k\(\delta_{k+1}(j)\)结束于状态i的最佳路径的分数仅与前一个一个状态是相关的，蓝色虚线表示可能的传递路径，计算方法如下：$$\delta_{k+1}(j)=max\left\{\begin{array}{c}\delta_{k}(1)+log(p(z_{k+1}=j|z_k=1))+log(p(x_{k+1}=j|z_{k+1}=j))\\\delta_{k}(2)+log(p(z_{k+1}=j|z_k=2))+log(p(x_{k+1}=j|z_{k+1}=j))\\......\\\\delta_{k}(m)+log(p(z_{k+1}=j|z_k=m))+log(p(x_{k+1}=j|z_{k+1}=j))\tag{3}\end{array}\right.$$递归公式总结为：$$\delta_{k+1}(j)=max_i[\delta_{i}(m)+log(p(z_{k+1}=j|z_k=i))+log(p(x_{k+1}=j|z_{k+1}=j))]\tag{4}$$其中，\(j\in[1,m],i\in[1,m],k+1\in[1,n]\),时间复杂度为\(O(n\cdotm^2)\)整个过程从上到下，从左到右计算（填表），最后一列为\([\delta_{n}(1),\delta_{n}(2)..\delta_{n}(m)]\),大选择est数作为我们最优路径的终点，然后可以通过回溯确定最终路径。在计算过程中，需要一个栈来记录路径上的节点。算法到此结束，但实际上，我们在这个过程中得到的是局部最优，而不是全局最优。要想得到全局最优，还需要其他算法（比如贪心算法，但是时间成本非常大）。HMMForward/BackwardAlgorithm中的ParameterEstimationForward/Backward算法在HMM参数估计中起着重要的作用。也就是说，在估计HMM参数的过程中，会用到Forward/Backward算法的结果。Forward/Backward算法是计算\(p(z_k|x)\)Forward是计算\(p(z_k,x_{1:k})\)Backward是计算\(p(x_{k+1:n}|z_k)\)通过贝叶斯我们可以重写$$p(z_k|x)=\frac{p(z_k,x)}{p(x)}\varproptop(z_k,x)\tag{5}$$无论这里的\(z_k\)取什么值，都有这样一个概率为\(p(x)\)，或者说其实这里的\(p(x)\)等价于一个常量项。$$\begin{equation}\begin{split}p(z_k,x)=&p(x_{k+1:n}|z_k,x_{1:k})\cdotp(z_k,x_{1:k})\\=&p(x_{k+1:n}|z_k)\cdotp(z_k,x_{1:k})\tag{6}\end{split}\end{equation}$$\(x_{1:k}\)条件独立于\(x_{k+1:n}\)公式（6）的结果正是Forward/BackwardForward算法的结果，为了计算\(p(z_k,x_{1:k})\),可以穷举，也可以用动态规划求递归公式。当然，动态规划一般用于这种关系。所以我们要求这样一个递归公式：$$p(z_k,x_{1:k})=something\cdotp(z_{k-1},x_{1:k-1})\tag{7}$$So,$$\begin{equation}\begin{split}p(z_k,x_{1:k})=&\sum_{z_{k-1}}p(z_{k-1},z_k,x_{1:k})\\=&\sum_{z_{k-1}}p(z_{k-1},x_{1:k-1})\cdotp(z_k|z_{k-1},x_{1:k-1})\cdotp(x_k|z_k,z_{k-1},x_{1:k-1})\\=&\sum_{z_k-1}p(z_{k-1},x_{1:k-1})\cdotp(z_k|z_{k-1})\cdotp(x_k|z_k)\tag{8}\end{split}\end{方程}$$式(8)中：\(x_{1:k-1}\)和\(z_k\)是条件独立的，所以可以删除\(z_{k-1},x_{1:k-1}\)和\(x_k\)是条件独立的，所以删到这里就可以了。我们写出了递归关系。如果我们将\(p(z_k,x_{1:k})\)表示为\(\alpha(z_k)\)，那么递归公式可以重新表示为：$$\alpha_k(z_k)=\sum_{z_{k-1}}\alpha_{k-1}(z_{k-1})\cdotp(z_k|z_{k-1})\cdotp(x_k|z_k)\tag{9}$$$$\alpha(z_1)=p(z_1,x)=p(z_1)\cdotp(x_1|z_1)=\pi\cdotB\tag{10}$$BackwardalgorithmBackward算法从后面计算forward，与Forward算法相反。同理，我们要求这样一个递归公式：$$p(x_{k+1:n}|z_k)=something\cdotp(x_{k+2:n}|z_{k+1})\tag{11}$$$$\begin{方程}\begin{split}p(x_{k+1:n}|z_k)=&\sum_{z_{k+1}}p(x_{k+1:n},z_{k+1}|z_k)\\=&\sump(x_{k+2:n}|z_{k+1},x_{k+1},z_k)\cdotp(x_{k+1}|z_{k+1},z_k)\cdotp(z_{k+1}|z_k)\\=&\sump(x_{k+2:n}|z_{k+1})\cdotp(x_{k+1}|z_{k+1})\cdotp(z_{k+1}|z_k)\end{split}\end{equation}\tag{12}$$式(12)中，\(x_{k+1},z_k\)和\(x_{k+2:n}\)是条件独立的，所以可以删除\(z_k\)和\(x_{k+1}\)条件是独立的，所以可以删除。我们写出了递归关系。如果我们将\(p(x_{k+1:n}|z_k)\)表示为\(\beta(z_k)\)，则递归公式可以重新表示为：$$\beta_k(z_k)=\sum_{z_{k+1}}\beta_k(z_{k+1})\cdotp(x_{k+1}|z_{k+1})\cdotp(z_{k+1}|z_k)\tag{13}$$ok，至此准备工作就绪，Forward算法，Backward算法将正式Incomplete，CompleteCase用于HMM的参数估计。在正式进入HMM参数估计之前，我们先来看一个更简单的情况，即我们可以观察到样本数据中的x和z。这时候参数估计就变得异常简单，只需要从数据上统计即可。Completecase:x,z都知道IncompleteCase:只知道xCompleteCaseIncompleteCase在complete的情况下，参数估计很简单，那么在incomplete的情况下如何估计呢？因为在不完全的情况下我们没有观察到变量z，所以不能简单的做统计。那么，怎么做呢？答案是：Expectation（期望）在HMM中，有两类变量，一类是模型本身的参数，一类是隐变量z。并且很难同时估计这两类参数，所以一种方法是：把一组变量当作常量（constant），从而估计另一组变量，依此类推。具体来说，将模型参数视为常数，估计变量z；将z视为常数并估计模型参数；将模型参数视为常数，估计变量z；将z视为常数，估计模型参数，重复直至收敛。这里我们用到一个算法，EM算法，用于估计两个未知数，在机器学习算法中经常用到，比如K近邻。例如，在此示例中，\(\theta={\pi,A,B}\)和参数\(z\)。EM算法流程是估计\(z\)，估计\(theta\)，估计\(z\)，估计\(\theta\)...，直到收敛。EM算法$$\mathop{argmax}_{\theta}[E_{z|x,\theta}lnp(x,z|\theta)]\tag{14}$$将式(14)分为两部分steps:E-step:求\(Z\)的期望M-step:Maximize\(lnp(x,z|\theta)\)一、二步依次循环，直到收敛算法过程可以表示as:while(notconverged):computez(expectation)updatepi,A,BHMMparametersolutionestimation\(\pi\)estimationBestimationAconditionalprobabilityandexpectedprobabilityestimation,standardizedsummaryHMM的推理过程其实就是预测对于序列的处理，要用到维特比算法维特比算法实际上是一种动态规划算法。HMM的参数估计实际上是一个模型训练过程。它需要估计三个不同的参数。HMM的参数估计过程使用EM算法，EM算法的结果取决于初始化结果。不同的初始化很可能会带来不同的效果。未完待续...这是个人学习笔记，不能用于其他用途！
