{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这一节介绍CRF的概率计算问题（它是下一节参数估计的基础）：即在给定条件随机场参数$w$、特征函数$F(\\cdot)$、输入序列$x$以及输出序列$y$的情况下，计算条件概率$P(Y_i=y_i\\mid x),P(Y_{i-1}=y_{i-1},Y_i=y_i\\mid x)$以及相应数学期望。其实对于概率的动态规划求解在前面**CRF的矩阵形式**那小节已经做了简单介绍，这里再简单分析一下：   \n",
    "\n",
    "以$P(Y_i=y_i\\mid x)$为例，要计算该条件概率，需要对另外的$n-1$项：$y_1,y_2,...,y_{i-1},y_{i+1},...,y_n$做$\\sum$将其积掉，所以会有$n-1$个求和叠在一起：$\\sum\\sum\\cdots\\sum$，而它的每一个计算项即CRF的势函数又可以拆解为$n$个独立相乘的子项：$exp(W_i(y_{i-1},y_i\\mid x))$（见矩阵形式那一节），所以这一节的概率计算问题同之前的HMM本质是一样的问题，可以利用前向或者后向的方法，将需要被多次计算的项的结果缓存下来，下面就直接写前向后向算法的求解过程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一.前向后向算法\n",
    "\n",
    "#### 前向\n",
    ">（1）初始化$y=start$步：   \n",
    "\n",
    "$$\n",
    "\\alpha_0(x)=[1,1,...,1]^T\n",
    "$$   \n",
    "\n",
    ">（2）对$i=1,2,...,n+1$：   \n",
    "\n",
    "$$\n",
    "\\alpha_i^T(x)=\\alpha_{i-1}^T(x)M_i(x)\n",
    "$$   \n",
    "\n",
    "$\\alpha_i(x)$表示从前往后截止到位置$i$时，第$i$个位置的非规范化概率分布（即对前面$i-1$步求了积分），显然$Z(x)=\\alpha_n^T(x)\\hat{1}=\\alpha_{n+1}(x)[-1]$（假设$stop$的标签状态在第后一位），$\\hat{1}$表示元素均为1的列向量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 后向\n",
    ">（1）初始化$y=stop$步：   \n",
    "\n",
    "$$\n",
    "\\beta_{n+1}(x)=[1,1,...,1]^T\n",
    "$$   \n",
    ">（2）对$i=n,n-1,...,0$有：   \n",
    "\n",
    "$$\n",
    "\\beta_i(x)=M_{i+1}(x)\\beta_{i+1}(x)\n",
    "$$   \n",
    "\n",
    "$\\beta_i(x)$表示从后往前截止到位置$i$时，第$i$个位置的非规范化概率分布，同样$Z(x)=\\hat{1}^T\\beta_1(x)=\\beta_0(x)[0]$（假设$start$的标签状态在第0位）   \n",
    "\n",
    "类似于HMM，前向后向也可以结合起来：   \n",
    "\n",
    "$$\n",
    "Z(x)=\\alpha_i^T(x)\\beta_i(x),i=0,1,...,n+1\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二.概率计算\n",
    "有了前向后向算法，对于$P(Y_i=y_i\\mid x)$以及$P(Y_{i-1}=y_{i-1},Y_i=y_i\\mid x)$的计算就也很方便了\n",
    "#### $P(Y_i=y_i\\mid x)$的计算\n",
    "\n",
    "$$\n",
    "P(Y_i=y_i\\mid x)=\\frac{\\alpha_i(y_i\\mid x)\\beta_i(y_i\\mid x)}{Z(x)}\n",
    "$$  \n",
    "\n",
    "$\\alpha_i(y_i\\mid x)$表示$\\alpha_i(x)$中对应标签状态为$y_i$的非规范化概率，$\\beta_i(y_i\\mid x)$同理\n",
    "\n",
    "#### $P(Y_{i-1}=y_{i-1},Y_i=y_i\\mid x)$的计算\n",
    "$$\n",
    "P(Y_{i-1}=y_{i-1},Y_i=y_i\\mid x)=\\frac{a_{i-1}(y_{i-1}\\mid x)M_i(y_{i-1},y_i\\mid x)\\beta_i(y_i\\mid x)}{Z(x)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 三.期望值计算\n",
    "下一节，参数的估计中需要用到特征函数关于条件分布以及联合分布的期望，这里同样需要用到前向后向的求解结果\n",
    "\n",
    "#### 特征函数$f_k$关于条件分布$P(Y\\mid X)$的期望\n",
    "\n",
    "$$\n",
    "E_{y\\sim P(Y\\mid X)}[f_k]=\\sum_yP(y\\mid x)f_k(y,x)\\\\\n",
    "=\\sum_{i=1}^{n+1}\\sum_{y_{i-1},y_i}f_k(y_{i-1},y_i,x,i)\\frac{\\alpha_{i-1}(y_{i-1}\\mid x)M_i(y_{i-1},y_i\\mid x)\\beta_i(y_i\\mid x)}{Z(x)}\\\\\n",
    "k=1,2,...,K\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 特征函数$f_k$关于联合分布$P(X,Y)$的期望\n",
    "由于CRF是直接对$P(Y\\mid X)$建模的，所有对于$P(X)$是无法得知，假设在知道$\\tilde{P}(X)$的情况下：   \n",
    "\n",
    "$$\n",
    "E_{x,y\\sim P(X,Y)}[f_k]=\\sum_{x,y}P(x,y)\\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i)\\\\\n",
    "=\\sum_x\\tilde{P}(x)\\sum_yP(y\\mid x)\\sum_{i=1}^{n+1}f_k(y_{i-1,y_i,x,i})\\\\\n",
    "=\\sum_x\\tilde{P}(x)\\sum_{i=1}^{n+1}\\sum_{y_{i-1},y_i}f_k(y_{i-1},y_i,x,i)\\frac{\\alpha_{i-1}(y_{i-1}\\mid x)M_i(y_{i-1},y_i\\mid x)\\beta_i(y_i\\mid x)}{Z(x)}\\\\\n",
    "k=1,2,...,K\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 四.小结一下计算过程\n",
    "总结一下计算的流程：（代码放到后面一节参数的估计中实现）   \n",
    "\n",
    "（1）对所有$i=1,2,...,n+1$计算$M_i(x)$；   \n",
    "\n",
    "（2）在$M_i(x)$的基础上分别前向/后向扫描一次，得到$\\alpha_i(x)$与$\\beta_i(x)$以及$Z(x)$；   \n",
    "\n",
    "（3）最后在得到的$\\alpha_i(x),\\beta_i(x),M_i(x),Z(x)$的基础上计算条件概率以及数学期望"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}