{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "状态集合\\begin{align*} & Q=\\left\\{q_{1},q_{2},\\ldots ,q_{N}\\right\\}  \\quad \\left| Q\\right| =N \\end{align*}  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "观测集合\\begin{align*} & V=\\left\\{v_{1},v_{2},\\ldots ,v_{M}\\right\\} \\quad  \\left| V\\right| =M  \\end{align*}  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "状态序列\\begin{align*} & I=\\left\\{i_{1},i_{2},\\ldots ,i_{t},\\ldots,i_{T}\\right\\}  \\quad i_{t}\\in Q  \\quad \\left(t=1,2,\\ldots,T \\right)\\end{align*}  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "观测序列\\begin{align*} & O=\\left\\{o_{1},o_{2},\\ldots ,o_{t},\\ldots,o_{T}\\right\\}  \\quad o_{t}\\in V \\quad \\left(t=1,2,\\ldots,T \\right)\\end{align*}  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "状态转移矩阵 \\begin{align*} & A=\\left[a_{ij}\\right]_{N\\times N} \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在$t$时刻处于状态$q_{i}$的条件下，在$t+1$时刻转移到状态$q_{j}$的概率\\begin{align*} & a_{ij}= P\\left( i_{t+1}=q_{j}|i_{t}=q_{i}\\right) \\quad \\left(i=1,2,\\ldots,N \\right) \\quad \\left(j=1,2,\\ldots,M \\right)\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "观测概率矩阵\\begin{align*} & B=\\left[b_{j}\\left(k\\right)\\right]_{N\\times M} \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在$t$时刻处于状态$q_{i}$的条件下，生成观测$v_{k}$的概率\\begin{align*} & b_{j}\\left(k\\right)= P\\left( o_{t}=v_{k}|i_{t}=q_{j}\\right) \\quad \\left(k=1,2,\\ldots,M \\right) \\quad \\left(j=1,2,\\ldots,N \\right)\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "初始概率向量\\begin{align*} & \\pi =\\left( \\pi _{i}\\right)  \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在时刻$t=1$处于状态$q_{i}$的概率\\begin{align*} & \\pi_{i} =P\\left( i_{1}=q_{i}\\right) \\quad \\left(i=1,2,\\ldots,N \\right) \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "隐马尔科夫模型\\begin{align*} & \\lambda =\\left( A,B.\\pi \\right)  \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "隐马尔科夫模型基本假设：\n",
    "1. 齐次马尔科夫性假设：在任意时刻$t$的状态只依赖于时刻$t-1$的状态。\\begin{align*} & P\\left( i_{t}|i_{t-1},o_{t-1},\\ldots,i_{1},o_{1}\\right)=P\\left(i_{t}|i_{t-1}\\right) \\quad \\left(t=1,2,\\ldots,T\\right) \\end{align*}\n",
    "2. 观测独立性假设：任意时刻$t$的观测只依赖于时刻$t$的状态。\\begin{align*} & P\\left( o_{t}|i_{T},o_{T},i_{T-1},o_{T-1},\\ldots,i_{t+1},o_{t+1},i_{t},i_{t-1},o_{t-1},\\ldots,i_{1},o_{1}\\right)=P\\left(o_{t}|i_{t}\\right) \\quad \\left(t=1,2,\\ldots,T\\right) \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "观测序列生成算法:  \n",
    "输入：隐马尔科夫模型$\\lambda =\\left( A,B.\\pi \\right)$,观测序列长度$T$;  \n",
    "输出：观测序列$O=\\left\\{o_{1},o_{2},\\ldots ,o_{t},\\ldots,o_{T}\\right\\}$；\n",
    "1. 由初始概率向量$\\pi$产生状态$i_{1}$；\n",
    "2. $t=1$；\n",
    "3. 由状态$i_{t}$的观测概率分布$b_{j}\\left(k\\right)$生成$o_{t}$；\n",
    "4. 由状态$i_{t}$的状态转移概率分布$a_{i_{t}i_{t+1}}$生成状态$i_{t+1} \\quad \\left(i_{t+1}=1,2,\\ldots,N\\right)$；  \n",
    "5. $t=t+1$；如果$t<T$，转至3.；否则，结束。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "隐马尔科夫模型的3个基本问题：  \n",
    "1. 概率计算：已知$\\lambda =\\left( A,B.\\pi \\right)$和$O=\\left\\{o_{1},o_{2},\\ldots ,o_{t},\\ldots,o_{T}\\right\\} $，计算$P\\left(O| \\lambda \\right)$\n",
    "2. 学习：已知$O=\\left\\{o_{1},o_{2},\\ldots ,o_{t},\\ldots,o_{T}\\right\\}$，计算 $\\lambda^* =\\arg \\max P\\left( O|\\lambda \\right) $\n",
    "3. 预测（编码）：已知$\\lambda =\\left( A,B.\\pi \\right)$和$O=\\left\\{o_{1},o_{2},\\ldots ,o_{t},\\ldots,o_{T}\\right\\} $，计算 $I^* =\\arg \\max P\\left( I|O \\lambda \\right) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "前向概率 \\begin{align*} & \\alpha _{t}\\left( i\\right) =P\\left(o_{1},o_{2},\\ldots ,o_{t}, i_{t}=q_{i}| \\lambda \\right) \\end{align*}  \n",
    "给定模型$\\lambda$，时刻$t$部分观测序列为$o_{1},o_{2},\\ldots ,o_{t}$且状态为$q_{i}$的概率。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "前向概率递推计算\\begin{align*} & \\alpha _{t}\\left( i\\right) =P\\left(o_{1},o_{2},\\ldots ,o_{t}, i_{t}=q_{i}| \\lambda \\right)＝P\\left(i_{t}=q_{i},o_{1}^t \\right) \\\\ & =\\sum _{j=1}^{N}P\\left(i_{t-1}=q_{j},i_{t}=q_{i},o_{1}^{t-1},o_{t}\\right) \\\\ & =\\sum _{j=1}^{N}P\\left(i_{t}=q_{i},o_{t}|i_{t-1}=q_{j},o_{1}^{t-1}\\right)\\cdot P\\left(i_{t-1}=q_{j},o_{1}^{t-1} \\right) \\\\ & =\\sum _{j=1}^{N}P\\left(i_{t}=q_{i},o_{t}|i_{t-1}=q_{j}\\right)\\cdot \\alpha _{t-1}\\left( j\\right)\\\\ & =\\sum _{j=1}^{N}P\\left(o_{t}|i_{t}=q_{i},i_{t-1}=q_{j}\\right)\\cdot P\\left(i_{t}=q_{i}|i_{t-1}=q_{j}\\right)\\cdot \\alpha _{t-1}\\left( j\\right) \\\\ & =\\sum _{j=1}^{N}b_{i}\\left(o_{t}\\right)\\cdot a_{ji}\\cdot \\alpha _{t-1}\\left( j\\right)\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "概率计算\\begin{align*} & P\\left(O| \\lambda \\right) =P\\left(o_{1}^{T}| \\lambda\\right) \\\\ & = \\sum_{i=1}^{N}P\\left(o_{1}^{T},i_{T}=q_{i}\\right)\\\\ & = \\sum _{i=1}^{N}\\alpha _{T}\\left( i\\right)\\end{align*} "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "观测序列概率计算的前向算法：  \n",
    "输入：隐马尔科夫模型$\\lambda$,观测序列$O$;   \n",
    "输出：观测序列概率$P\\left(O| \\lambda \\right)$；\n",
    "1. 初值\\begin{align*} & \\alpha _{1}\\left( i\\right)= \\pi_{i}b_{i}\\left(o_{1}\\right) \\quad \\left(t=1,2,\\ldots,N\\right) \\end{align*}\n",
    "2. 递推  对$t=1,2,\\ldots,T-1$ \\begin{align*} & \\alpha _{t+1}\\left( i\\right) =\\sum _{j=1}^{N}b_{i}\\left(o_{t+1}\\right)\\cdot a_{ji}\\cdot \\alpha _{t}\\left( j\\right) \\quad \\left(t=1,2,\\ldots,N\\right) \\end{align*}\n",
    "3. 终止  \\begin{align*} & P\\left(O| \\lambda \\right)= \\sum _{j=1}^{N}\\alpha _{T}\\left( i\\right)\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "后向概率 \\begin{align*} & \\beta_{t}\\left( i\\right) =P\\left(o_{t+1},o_{t+2},\\ldots ,o_{T}| i_{t}=q_{i} \\lambda \\right) \\end{align*}  \n",
    "给定模型$\\lambda$，时刻$t$状态为$q_{i}$的条件下，从时刻$t+1$到时刻$T$的部分观测序列为$o_{t+1},o_{t+2},\\ldots ,o_{T}$的概率。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "后向概率递推计算\\begin{align*} & \\beta _{t}\\left( i\\right) =P\\left(o_{t+1},o_{t+2},\\ldots ,o_{T}| i_{t}=q_{i}, \\lambda \\right)＝P\\left(o_{t+1}^T |i_{t}=q_{i}\\right) \\\\ & =\\dfrac {P\\left(o_{t+1}^{T}, i_{t}=q_{i}\\right)} {P\\left(i_{t}=q_{i}\\right)}\\\\ & =\\dfrac {\\sum_{j=1}^{N} P\\left(o_{t+1}^{T},i_{t}=q_{i},i_{t+1}=q_{j}\\right)}{P\\left(i_{t}=q_{i}\\right)}\\\\ & =\\sum_{j=1}^{N} \\dfrac {P\\left(o_{t+1}^{T}|i_{t}=q_{i},i_{t+1}=q_{j}\\right) \\cdot P\\left(i_{t}=q_{i},i_{t+1}=q_{j} \\right)}{P\\left(i_{t}=q_{i}\\right)} \\\\ & = \\sum_{j=1}^{N} P\\left(o_{t+1}^{T}|i_{t+1}=q_{j}\\right) \\cdot \\dfrac {P\\left(i_{t+1}=q_{j}|i_{t}=q_{i}\\right)  \\cdot P\\left(i_{t}=q_{i} \\right)}{P\\left(i_{t}=q_{i} \\right)} \\\\ & = \\sum_{j=1}^{N} P\\left(o_{t+2}^{N},o_{t+1}|i_{t+1}=q_{j}\\right) \\cdot a_{ij} \\\\ & = \\sum_{j=1}^{N} P\\left(o_{t+2}^{T}|i_{t+1}=q_{j}\\right) \\cdot P\\left(o_{t+1}|i_{t+1}=q_{j}\\right) \\cdot a_{ij} \\\\ & = \\sum_{j=1}^{N} \\beta_{t+1}\\left(j\\right) \\cdot b_{j}\\left(o_{t+1}\\right) \\cdot a_{ij}\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "概率计算\\begin{align*} & P\\left(O| \\lambda \\right) =P\\left(o_{1}^{T}| \\lambda\\right) \\\\ & = \\sum_{i=1}^{N}P\\left(o_{1}^{T},i_{1}=q_{i}\\right)\\\\ & = \\sum_{i=1}^{N}P\\left(i_{1}=q_{i}\\right) \\cdot P\\left(o_{1}|i_{1}=q_{i}\\right)\\cdot P\\left(o_{2}^{T}|i_{1}=q_{i}\\right) \\\\ & = \\sum_{i=1}^{N} \\pi_{i} b_{i}\\left(o_{1}\\right) \\beta_{1}\\left(i\\right)\\end{align*} "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "观测序列概率计算的后向算法：  \n",
    "输入：隐马尔科夫模型$\\lambda$,观测序列$O$;   \n",
    "输出：观测序列概率$P\\left(O| \\lambda \\right)$；\n",
    "1. 初值\\begin{align*} & \\beta_{T}\\left( i\\right)= 1 \\quad \\left(t=1,2,\\ldots,N\\right) \\end{align*}\n",
    "2. 递推  对$t=T-1,T-2,\\ldots,1$ \\begin{align*} & \\beta_{t}\\left( i\\right) =\\sum_{j=1}^{N} \\beta_{t+1}\\left(j\\right) \\cdot b_{j}\\left(o_{t+1}\\right) \\cdot a_{ij} \\quad \\left(t=1,2,\\ldots,N\\right) \\end{align*}\n",
    "3. 终止  \\begin{align*} & P\\left(O| \\lambda \\right)= \\sum _{j=1}^{N}\\pi_{i} b_{i}\\left(o_{1}\\right)\\beta _{1}\\left( i\\right) \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$P \\left( O | \\lambda \\right)$的前向概率、后向概率的表示  \n",
    "\\begin{align*} \\\\ & P \\left( O | \\lambda \\right) ＝ P \\left( o_{1}^{T} \\right)\n",
    "\\\\ & ＝ \\sum_{i=1}^{N} \\sum_{j=1}^{N} P \\left( o_{1}^{t}, o_{t+1}^{T}, i_{t}=q_{i}, i_{t+1}=q_{j} \\right) \n",
    "\\\\ & ＝ \\sum_{i=1}^{N} \\sum_{j=1}^{N} P \\left( o_{1}^{t},  i_{t}=q_{i}, i_{t+1}=q_{j} \\right) P \\left( o_{t+1}^{T} | i_{t+1}=q_{j} \\right)\n",
    "\\\\ &  = \\sum_{i=1}^{N} \\sum_{j=1}^{N} P \\left( o_{1}^{t},  i_{t}=q_{i} \\right) P \\left( i_{t+1}=q_{j} | i_{t}=q_{i} \\right) P \\left( o_{t+1}^{T} | i_{t+1}=q_{j} \\right) \n",
    "\\\\ & = \\sum_{i=1}^{N} \\sum_{j=1}^{N} P \\left( o_{1}^{t},  i_{t}=q_{i} \\right) P \\left( i_{t+1}=q_{j} | i_{t}=q_{i} \\right) P \\left( o_{t+1} | i_{t+1}=q_{j} \\right) P \\left( o_{t+2}^{T} | i_{t+1}=q_{j} \\right)\n",
    "\\\\ & = \\sum_{i=1}^{N} \\sum_{j=1}^{N} \\alpha_{t} \\left( i \\right) a_{ij} b_{j} \\left( o_{t+1} \\right) \\beta_{t+1} \\left( j \\right) \\quad \\quad \\quad t=1, 2, \\cdots, T-1\\end{align*}  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定模型$\\lambda$和观测$O$，在时刻$t$处于状态$q_{i}$的概率\n",
    "\\begin{align*} \\\\ & \\gamma_{t} \\left( i \\right) = P \\left( i_{t}=q_{i} | O, \\lambda \\right) \n",
    "\\\\ & =  \\dfrac{ P \\left( i_{t}=q_{i}, O | \\lambda \\right) } { P \\left( O | \\lambda \\right) } \n",
    "\\\\ & = \\dfrac{ P \\left( i_{t}=q_{i}, O | \\lambda \\right) } { \\sum_{j=1}^{N} \\left( i_{t}=q_{i}, O | \\lambda \\right) }\n",
    "\\\\ & = \\dfrac{ P \\left( o_{1}^{t}, i_{t}=q_{i} \\right) P \\left( o_{t+1}^{T}| i_{t}=q_{i} \\right) } { \\sum_{j=1}^{N} P \\left( o_{1}^{t}, i_{t}=q_{i} \\right) P \\left( o_{t+1}^{T}| i_{t}=q_{i} \\right) }\n",
    "\\\\ & = \\dfrac{ \\alpha_{t} \\left( i \\right) \\beta_{t} \\left( i \\right)} { \\sum_{j=1}^{N}  \\alpha_{t} \\left( i \\right) \\beta_{t} \\left( i \\right) }\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定模型$\\lambda$和观测$O$，在时刻$t$处于状态$q_{i}$且在时刻$t+1$处于状态$q_{j}$的概率  \n",
    "\\begin{align*} \\\\ & \\xi_{t} \\left( i,j \\right) = P \\left( i_{t}=q_{i}, i_{t+1}=q_{j} | O ,\\lambda \\right) \n",
    "\\\\ & = \\dfrac{ P \\left( i_{t}=q_{i}, i_{t+1}=q_{j},O | \\lambda \\right) } { P \\left( O | \\lambda \\right) }\n",
    "\\\\ & = \\dfrac{ P \\left( i_{t}=q_{i}, i_{t+1}=q_{j}, O | \\lambda \\right) } { \\sum_{i=1}^{N} \\sum_{j=1}^{N}  P \\left( i_{t}=q_{i}, i_{t+1}=q_{j}, O|\\lambda \\right) } \n",
    "\\\\ & = \\dfrac{ \\alpha_{t} \\left( i \\right) a_{ij} b_{j} \\left( o_{t+1} \\right) \\beta_{t+1} \\left( j \\right) } { \\sum_{i=1}^{N} \\sum_{j=1}^{N}  \\alpha_{t} \\left( i \\right) a_{ij} b_{j} \\left( o_{t+1} \\right) \\beta_{t+1} \\left( j \\right)}\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在观测$O$下状态$i$出现的期望\\begin{align*} & \\sum_{t=1}^{T} \\gamma_{t} \\left( i \\right) =  \\sum_{t=1}^{T} P \\left( i_{t}=q_{i} | O, \\lambda \\right) \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在观测$O$下由状态$i$转移的期望\\begin{align*} & \\sum_{t=1}^{T－1} \\gamma_{t} \\left( i \\right) =  \\sum_{t=1}^{T－1} P \\left( i_{t}=q_{i} | O, \\lambda \\right) \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在观测$O$下由状态$i$转移到状态$j$的期望\\begin{align*} & \\sum_{t=1}^{T－1} \\xi_{t} \\left( i,j \\right) =  \\sum_{t=1}^{T－1} P \\left( i_{t}=q_{i}, i_{t+1}=q_{j} | O, \\lambda \\right) \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将观测序列作为观测数据$O$,将状态序列作为隐数据$I$，则应马尔科夫模型是含有隐变量的概率模型  \n",
    " \\begin{align*} & P \\left( O | \\lambda \\right) = \\sum_{I} P \\left( O | I, \\lambda \\right) P \\left( I | \\lambda \\right)\\end{align*}  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "完全数据\n",
    " \\begin{align*} & \\left( O, I \\right) = \\left(o_{1}, o_{2}, \\cdots, o_{T}, i_{1}, i_{2}, \\cdots, o_{T} \\right)\\end{align*}  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "完全数据的对数似然函数\n",
    "\\begin{align*} & \\log P \\left( O, I | \\lambda \\right) \\end{align*}  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$Q \\left( \\lambda, \\overline{\\lambda} \\right)$函数  \n",
    "\\begin{align*} \\\\& Q \\left( \\lambda, \\overline{\\lambda} \\right) = E_{I} \\left[ \\log P \\left( O, I | \\lambda \\right) | O, \\overline{\\lambda} \\right]\n",
    "\\\\ & = \\sum_{I} \\log P \\left( O, I | \\lambda \\right) P \\left( I | O, \\overline{\\lambda} \\right)\n",
    "\\\\ & = \\sum_{I} \\log \\dfrac{P \\left( O, I | \\lambda \\right) P \\left( O, I | \\overline{\\lambda} \\right) }{P \\left( O | \\overline{\\lambda} \\right)}\\end{align*}    \n",
    "其中，$\\overline{\\lambda}$是隐马尔科夫模型参数的当前估计值，$\\lambda$是隐马尔科夫模型参数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于对最大化$Q \\left( \\lambda, \\overline{\\lambda} \\right)$函数，$P \\left( O | \\overline{\\lambda} \\right)$为常数因子，  \n",
    "以及\\begin{align*} & P \\left( O, I | \\lambda \\right) = \\pi_{i_{1}} b_{i_{1}} \\left( o_{1} \\right) a_{i_{1}i_{2}} b_{i_{2}} \\left( o_{2} \\right) \\cdots a_{i_{T-1}i_{T}}b_{T}\\left( o_{T} \\right)\\end{align*}    \n",
    "所以求$Q \\left( \\lambda, \\overline{\\lambda} \\right)$函数对$\\lambda$的最大\\begin{align*} & \\lambda = \\arg \\max{Q \\left( \\lambda, \\overline{\\lambda} \\right) }\\Leftrightarrow \\arg\\max \\sum_{I} \\log P \\left( O, I | \\lambda \\right) P \\left( O, I | \\overline{\\lambda} \\right)\n",
    "\\\\ &  = \\sum_{I} \\log \\pi_{i_{1}} P \\left( O, I | \\overline{\\lambda} \\right) + \\sum_{I} \\left( \\sum_{t=1}^{T-1} \\log a_{i_{t}i_{t+1}} \\right) P \\left( O, I | \\overline{\\lambda} \\right) + \\sum_{I} \\left( \\sum_{t=1}^{T} \\log b_{i_{t}} \\left( o_{t} \\right) \\right) P \\left( O, I | \\overline{\\lambda} \\right)\\end{align*}    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对三项分别进行极大化：  \n",
    "1. \\begin{align*} & \\max \\sum_{I} \\log \\pi_{i_{1}} P \\left( O, I | \\overline{\\lambda} \\right) = \\sum_{i=1}^{N} \\log \\pi_{i_{1}} P \\left( O, i_{1}=i | \\overline{\\lambda} \\right)\n",
    "\\\\ & s.t. \\sum_{i=1}^{N} \\pi_{i} = 1 \\end{align*}   \n",
    "构造拉格朗日函数，对其求偏导，令结果为0 \\begin{align*} & \\dfrac{\\partial}{\\partial \\pi_{i}} \\left[ \\sum_{i=1}^{N} \\log \\pi_{i_{1}} P \\left( O, i_{1}=i | \\overline{\\lambda} \\right) + \\gamma \\left( \\sum_{i=1}^{N} \\pi_{i} - 1 \\right) \\right] = 0\\end{align*}  \n",
    "得\\begin{align*} & P \\left( O, i_{1} = i | \\overline{\\lambda} \\right) + \\gamma \\pi_{i} = 0\n",
    "\\\\ & \\sum_{i=1}^{N} \\left[ P \\left( O, i_{1} = i | \\overline{\\lambda} \\right) + \\gamma \\pi_{i} \\right] = 0\n",
    "\\\\ & \\sum_{i=1}^{N} P \\left( O, i_{1} = i | \\overline{\\lambda} \\right) + \\gamma \\sum_{i=1}^{N} \\pi_{i}  = 0\n",
    "\\\\ & P \\left( O | \\overline{\\lambda} \\right) + \\gamma  = 0\n",
    "\\\\ & \\gamma  = - P \\left( O | \\overline{\\lambda} \\right)\\end{align*}    \n",
    "代入$P \\left( O, i_{1} = i | \\overline{\\lambda} \\right) + \\gamma \\pi_{i} = 0$，得\n",
    "\\begin{align*} & \\pi_{i} = \\dfrac{P \\left( O, i_{1} = i | \\overline{\\lambda} \\right)}{P \\left( O | \\overline{\\lambda} \\right)}\n",
    "\\\\ & = \\gamma_{1} \\left( i \\right) \\end{align*}    \n",
    "2. \\begin{align*} \\\\ & \\max \\sum_{I} \\left( \\sum_{t=1}^{T-1} \\log a_{i_{t}i_{t+1}} \\right) P \\left( O, I | \\overline{\\lambda} \\right) = \\sum_{i=1}^{N} \\sum_{j=1}^{N} \\sum_{t=1}^{T-1} \\log a_{ij} P \\left( O, i_{t}=i, i_{t+1}=j | \\overline{\\lambda} \\right) \n",
    "\\\\ & s.t. \\sum_{j=1}^{N} a_{ij} = 1 \\end{align*}   \n",
    "得\\begin{align*} \\\\ & a_{ij} = \\dfrac{\\sum_{t=1}^{T-1} P \\left( O, i_{t}=i, i_{t+1}=j | \\overline{\\lambda} \\right)}{\\sum_{t=1}^{T-1} P \\left( O, i_{t}=i | \\overline{\\lambda} \\right)}\n",
    "\\\\ & = \\dfrac{\\sum_{t=1}^{T-1} \\xi_{t} \\left( i,j \\right) }{\\sum_{t=1}^{T-1} \\gamma_{t} \\left( i \\right)}\\end{align*}   \n",
    "3. \\begin{align*} \\\\ & \\max \\sum_{I} \\left( \\sum_{t=1}^{N} \\log b_{i_{t}} \\left( o_{t} \\right) \\right) P \\left( O, I | \\overline{\\lambda} \\right) = \\sum_{j=1}^{N} \\sum_{t=1}^{T} \\log b_{j} \\left( o_{t} \\right) P \\left( O, i_{t}=j | \\overline{\\lambda} \\right) \n",
    "\\\\ & s.t. \\sum_{k=1}^{M} b_{j} \\left( k \\right) = 1 \\end{align*}  \n",
    "得\\begin{align*} \\\\ & b_{j} \\left( k \\right) = \\dfrac{\\sum_{t=1}^{T} P \\left( O, i_{t}=j | \\overline{\\lambda} \\right) I \\left( o_{t} = v_{k} \\right)}{\\sum_{t=1}^{T} P \\left( O, i_{t}=j | \\overline{\\lambda} \\right)} \n",
    "\\\\ & = \\dfrac{ \\sum_{t=1,o_{t}=v_{k}}^{T} \\gamma_{t} \\left( j \\right)}{\\sum_{t=1}^{T} \\gamma_{t} \\left( j \\right)}\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Baum-Welch算法：  \n",
    "输入：观测数据$O = \\left( o_{1}, o_{2}, \\cdots, o_{T} \\right)$  \n",
    "输出：隐马尔科夫模型参数  \n",
    "1. 初始化  \n",
    "对$n=0$，选取$a_{ij}^{ \\left( 0 \\right) },b_{j} \\left( k \\right)^{\\left( 0 \\right)},\\pi_{i}^{\\left( 0 \\right)}$，得到模型$\\lambda^{\\left( 0 \\right)} = \\left( a_{ij}^{ \\left( 0 \\right) },b_{j} \\left( k \\right)^{\\left( 0 \\right)},\\pi_{i}^{\\left( 0 \\right)} \\right)$  \n",
    "2. 递推  \n",
    "对$n=1,2, \\cdots,$  \n",
    "\\begin{align*} \\\\ & a_{ij}^{\\left( n+1 \\right)} = \\dfrac{\\sum_{t=1}^{T-1} \\xi_{t} \\left( i,j \\right) }{\\sum_{t=1}^{T-1} \\gamma_{t} \\left( i \\right)} \n",
    "\\\\ & b_{j} \\left( k \\right)^{\\left( n+1 \\right)} = \\dfrac{ \\sum_{t=1,o_{t}=v_{k}}^{T} \\gamma_{t} \\left( j \\right)}{\\sum_{t=1}^{T} \\gamma_{t} \\left( j \\right)} \n",
    "\\\\ & \\pi_{i}^{\\left( n+1 \\right)} = \\dfrac{P \\left( O, i_{1} = i | \\overline{\\lambda} \\right)}{P \\left( O | \\overline{\\lambda} \\right)} \\end{align*}  \n",
    "其中，右端各值按观测数据$O = \\left( o_{1}, o_{2}, \\cdots, o_{T} \\right)$和模型$\\lambda^{\\left( n \\right)} = \\left( A^{\\left( n \\right)},B^{\\left( n \\right)},\\pi^{\\left( n \\right)} \\right)$计算。  \n",
    "3. 终止  \n",
    "得到模型$\\lambda^{\\left( n＋1 \\right)} = \\left( A^{\\left( n+1 \\right)},B^{\\left( n+1 \\right)},\\pi^{\\left( n+1 \\right)} \\right)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在时刻$t$状态为$i$的所有单个路径$\\left( i_{1}, i_{2}, \\cdots, i_{t} \\right)$中概率最大值  \n",
    "\\begin{align*} \\\\ & \\delta_{t} \\left( i \\right) = \\max_{i_{1}, i_{2}, \\cdots, i_{t-1}} P \\left(i_{t}=i, i_{t-1}, \\cdots, i_{1}, o_{t}, \\cdots, o_{1} | \\lambda \\right) \\quad \\quad \\quad i = 1, 2, \\cdots, N  \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "得递推公式\\begin{align*} \\\\ & \\delta_{t+1} \\left( i \\right) = \\max_{i_{1}, i_{2}, \\cdots, i_{t}} P \\left(i_{t+1}=i, i_{t}, \\cdots, i_{1}, o_{t+1}, \\cdots, o_{1} | \\lambda \\right) \n",
    "\\\\ & = \\max_{1 \\leq j \\leq N} \\left[ \\max_{i_{1}, i_{2}, \\cdots, i_{t-1}} P \\left( i_{t+1}=i, i_{t}=j, i_{t-1}, \\cdots, i_{1}, o_{t+1}, o_{t}, \\cdots, o_{1} | \\lambda \\right) \\right]\n",
    "\\\\ & = \\max_{1 \\leq j \\leq N} \\left[ \\max_{i_{1}, i_{2}, \\cdots, i_{t-1}} P \\left( i_{t+1}=i, i_{t}=j, i_{t-1}, \\cdots, i_{1}, o_{t}, o_{t-1}, \\cdots, o_{1} | \\lambda \\right) P \\left( o_{t+1} | i_{t+1}=i, \\lambda \\right)\\right]\n",
    "\\\\ & = \\max_{1 \\leq j \\leq N} \\left[ \\max_{i_{1}, i_{2}, \\cdots, i_{t-1}} P \\left( i_{t}=j, i_{t-1}, \\cdots, i_{1}, o_{t}, o_{t-1}, \\cdots, o_{1} | \\lambda \\right) P \\left( i_{t+1}=i | i_{t}=j, \\lambda \\right)P \\left( o_{t+1} | i_{t+1}=i, \\lambda \\right)\\right]\n",
    "\\\\ & =  \\max_{1 \\leq j \\leq N} \\left[ \\delta_{t} \\left( j \\right) a_{ji}\\right] b_{i} \\left( o_{t+1} \\right)\\quad \\quad \\quad i = 1, 2, \\cdots, N  \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在时刻$t$状态为$i$的所有单个路径$\\left( i_{1}, i_{2}, \\cdots, i_{t} \\right)$中概率最大值的路径的第$t-1$个结点\n",
    "\\begin{align*} \\\\ & \\psi_{t} \\left( i \\right) = \\arg \\max_{1 \\leq j \\leq N} \\left[ \\delta_{t-1} \\left( j \\right) a_{ji} \\right] \\quad \\quad \\quad i = 1, 2, \\cdots, N \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "维特比算法：  \n",
    "输入：模型$\\lambda = \\left( A, B, \\pi \\right)$和观测数据$O = \\left( o_{1}, o_{2}, \\cdots, o_{T} \\right)$   \n",
    "输出：最优路径$I^{*} = \\left( i_{1}^{*}, i_{2}^{*}, \\cdots, i_{T}^{*} \\right)$  \n",
    "1. 初始化  \n",
    "\\begin{align*} \\\\ & \\delta_{1} \\left( i \\right) = \\pi_{i} b_{i} \\left( o_{1} \\right) \\quad \\quad \\quad i = 1, 2, \\cdots, N\n",
    "\\\\ & \\psi_{1} \\left( i \\right) = 0  \\end{align*}  \n",
    "2. 递推  \n",
    "对$t=2,3, \\cdots, T$ \n",
    "\\begin{align*} \\\\ & \\delta_{t} \\left( i \\right) = \\max_{1 \\leq j \\leq N} \\left[ \\delta_{t-1} \\left( j \\right) a_{ji}\\right] b_{i} \\left( o_{t} \\right)\\quad \\quad \\quad i = 1, 2, \\cdots, N\n",
    "\\\\ & \\psi_{t} \\left( i \\right) = \\arg \\max_{1 \\leq j \\leq N} \\left[ \\delta_{t-1} \\left( j \\right) a_{ji} \\right] \\quad \\quad \\quad i = 1, 2, \\cdots, N  \\end{align*}  \n",
    "3. 终止\n",
    "\\begin{align*} \\\\ & P^{*} = \\max_{1 \\leq j \\leq N} \\delta_{T} \\left( i \\right)\n",
    "\\\\ & i_{T}^{*} = \\arg \\max_{1 \\leq j \\leq N} \\left[ \\delta_{T} \\left( i \\right) \\right] \\end{align*}  \n",
    "4. 最优路径回溯  \n",
    "对$t=T-1,T-2, \\cdots, 1$ \n",
    "\\begin{align*} \\\\ & i_{t}^{*} = \\psi_{t+1} \\left( i_{t+1}^{*} \\right) \\end{align*}  \n",
    "求得最优路径$I^{*} = \\left( i_{1}^{*}, i_{2}^{*}, \\cdots, i_{T}^{*} \\right)$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}