11.CRF.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第11章 条件随机场\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1．概率无向图模型是由无向图表示的联合概率分布。无向图上的结点之间的连接关系表示了联合分布的随机变量集合之间的条件独立性，即马尔可夫性。因此，概率无向图模型也称为马尔可夫随机场。\n",
    "\n",
    "概率无向图模型或马尔可夫随机场的联合概率分布可以分解为无向图最大团上的正值函数的乘积的形式。\n",
    "\n",
    "2．条件随机场是给定输入随机变量$X$条件下，输出随机变量$Y$的条件概率分布模型， 其形式为参数化的对数线性模型。条件随机场的最大特点是假设输出变量之间的联合概率分布构成概率无向图模型，即马尔可夫随机场。条件随机场是判别模型。\n",
    "\n",
    "3．线性链条件随机场是定义在观测序列与标记序列上的条件随机场。线性链条件随机场一般表示为给定观测序列条件下的标记序列的条件概率分布，由参数化的对数线性模型表示。模型包含特征及相应的权值，特征是定义在线性链的边与结点上的。线性链条件随机场的数学表达式是\n",
    "$$\n",
    "P(y | x)=\\frac{1}{Z(x)} \\exp \\left(\\sum_{i, k} \\lambda_{k} t_{k}\\left(y_{i-1}, y_{i}, x, i\\right)+\\sum_{i, l} \\mu_{l} s_{l}\\left(y_{i}, x, i\\right)\\right)\n",
    "$$\n",
    "\n",
    "其中，\n",
    " $$\n",
    "Z(x)=\\sum_{y} \\exp \\left(\\sum_{i, k} \\lambda_{k} t_{k}\\left(y_{i-1}, y_{i}, x, i\\right)+\\sum_{i, l} \\mu_{l} s_{l}\\left(y_{i}, x, i\\right)\\right)\n",
    "$$\n",
    "\n",
    "4．线性链条件随机场的概率计算通常利用前向-后向算法。\n",
    "\n",
    "5．条件随机场的学习方法通常是极大似然估计方法或正则化的极大似然估计，即在给定训练数据下，通过极大化训练数据的对数似然函数以估计模型参数。具体的算法有改进的迭代尺度算法、梯度下降法、拟牛顿法等。\n",
    "\n",
    "6．线性链条件随机场的一个重要应用是标注。维特比算法是给定观测序列求条件概率最大的标记序列的方法。\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例11.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numpy import *#引用numpy中所有的函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24.532530197109345\n",
      "24.532530197109352\n"
     ]
    }
   ],
   "source": [
    "#这里定义T为转移矩阵列代表前一个y(ij)代表由状态i转到状态j的概率,Tx矩阵x对应于时间序列\n",
    "#这里将书上的转移特征转换为如下以时间轴为区别的三个多维列表，维度为输出的维度\n",
    "T1 = [[0.6, 1], [1, 0]]\n",
    "T2 = [[0, 1], [1, 0.2]]\n",
    "#将书上的状态特征同样转换成列表,第一个是为y1的未规划概率，第二个为y2的未规划概率\n",
    "S0 = [1, 0.5]\n",
    "S1 = [0.8, 0.5]\n",
    "S2 = [0.8, 0.5]\n",
    "Y = [1, 2, 2]  #即书上例一需要计算的非规划条件概率的标记序列\n",
    "Y = array(Y) - 1  #这里为了将数与索引相对应即从零开始\n",
    "P = exp(S0[Y[0]])\n",
    "for i in range(1, len(Y)):#遍历标记序列\n",
    "    P *= exp((eval('S%d' % i)[Y[i]]) + eval('T%d' % i)[Y[i - 1]][Y[i]])#根据公式计算线性链条件随机场条件概率\n",
    "print(P)#查看\n",
    "print(exp(3.2))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例11.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "非规范化概率 24.532530197109345\n"
     ]
    }
   ],
   "source": [
    "#这里根据例11.2的启发整合为一个矩阵\n",
    "F0 = S0\n",
    "F1 = T1 + array(S1 * len(T1)).reshape(shape(T1))\n",
    "F2 = T2 + array(S2 * len(T2)).reshape(shape(T2))\n",
    "Y = [1, 2, 2]  #即书上例一需要计算的非规划条件概率的标记序列\n",
    "Y = array(Y) - 1#将数与索引相对应\n",
    "\n",
    "P = exp(F0[Y[0]])#初始非规范化概率\n",
    "Sum = P#同时赋值给Sum\n",
    "for i in range(1, len(Y)):\n",
    "    PIter = exp((eval('F%d' % i)[Y[i - 1]][Y[i]]))\n",
    "    P *= PIter\n",
    "    Sum += PIter\n",
    "print('非规范化概率', P)#查看"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第11章条件随机场-习题\n",
    "\n",
    "### 习题11.1\n",
    "&emsp;&emsp;写出图11.3中无向图描述的概率图模型的因子分解式。\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/11-1-Maximal-Clique.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图11.3 无向图的团和最大团</div></center>"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**  \n",
    "&emsp;&emsp;图11.3表示由4个结点组成的无向图。图中由2个结点组成的团有5个：$\\{Y_1,Y_2\\},\\{Y_2,Y_3\\},\\{Y_3,Y_4\\},\\{Y_4,Y_2\\}$和$\\{Y_1,Y_3\\}$，有2个最大团：$\\{Y_1,Y_2,Y_3\\}$和$\\{Y_2,Y_3,Y_4\\}$，而$\\{Y_1,Y_2,Y_3,Y_4\\}$不是一个团，因为$Y_1$和$Y_4$没有边连接。  \n",
    "&emsp;&emsp;根据概率图模型的因子分解定义：将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作。公式在书中(11.5)，(11.6)。  \n",
    "$$P(Y)=\\frac{\\Psi_{(1,2,3)}(Y_{(1,2,3)})\\cdot\\Psi_{(2,3,4)}(Y_{(2,3,4)})}{\\displaystyle \\sum_Y \\left[ \\Psi_{(1,2,3)}(Y_{(1,2,3)})\\cdot\\Psi_{(2,3,4)}(Y_{(2,3,4)})\\right]}$$"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题11.2\n",
    "\n",
    "&emsp;&emsp;证明$Z(x)=a_n^T(x) \\cdot \\boldsymbol{1} = \\boldsymbol{1}^T\\cdot\\beta_1(x)$，其中$\\boldsymbol{1}$是元素均为1的$m$维列向量。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**  \n",
    "**第1步：**证明$Z(x)=a_n^T(x) \\cdot \\boldsymbol{1}$  \n",
    "根据条件随机场的矩阵形式：$$(M_{n+1}(x))_{i,j}=\\begin{cases}\n",
    "1,&j=\\text{stop}\\\\\n",
    "0,&\\text{otherwise}\n",
    "\\end{cases}$$根据前向向量的定义：$$\\alpha_0(y|x)=\\begin{cases}\n",
    "1,&y=\\text{start} \\\\\n",
    "0,&\\text{otherwise}\n",
    "\\end{cases}$$  \n",
    "$\\begin{aligned}\n",
    "\\therefore Z_n(x) \n",
    "&= \\left(M_1(x)M_2(x){\\cdots}M_{n+1}(x)\\right)_{(\\text{start},\\text{stop})} \\\\\n",
    "&= \\alpha_0(x)^T M_1(x)M_2(x){\\cdots}M_n(x) \\cdot 1\\\\\n",
    "&=\\alpha_n(x)^T\\cdot \\boldsymbol{1}\n",
    "\\end{aligned}$  \n",
    "\n",
    "-----\n",
    "\n",
    "**第2步：**证明$Z(x)=\\boldsymbol{1}^T \\cdot \\beta_1(x)$  \n",
    "根据条件随机场的矩阵形式：$$(M_{n+1}(x))_{i,j}=\\begin{cases}\n",
    "1,&j=\\text{stop}\\\\\n",
    "0,&\\text{otherwise}\n",
    "\\end{cases}$$根据后向向量定义：$$\\beta_{n+1}(y_{n+1}|x)=\n",
    "\\begin{cases}\n",
    "1,& y_{n+1}=\\text{stop} \\\\\n",
    "0,& \\text{otherwise}\n",
    "\\end{cases}$$  \n",
    "$\\begin{aligned}\n",
    "\\therefore Z_n(x)\n",
    "&= (M_1(x)M_2(x) \\cdots M_{n+1}(x))_{(\\text{start},\\text{stop})} \\\\\n",
    "&= (M_1(x)M_2(x) \\cdots M_n(x) \\beta_{n+1}(x))_{\\text{start}} \\\\\n",
    "&=(\\beta_1(x))_{\\text{start}} \\\\\n",
    "&=\\boldsymbol{1}^T \\cdot \\beta_1(x)\n",
    "\\end{aligned}$  \n",
    "综上所述：$Z(x)=a_n^T(x) \\cdot \\boldsymbol{1} = \\boldsymbol{1}^T \\cdot \\beta_1(x)$，命题得证。  "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题11.3\n",
    "&emsp;&emsp;写出条件随机场模型学习的梯度下降法。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**  \n",
    "条件随机场的对数极大似然函数为：$$L(w)=\\sum^N_{j=1} \\sum^K_{k=1} w_k f_k(y_j,x_j)-\\sum^N_{j=1} \\log{Z_w(x_j)}$$梯度下降算法的目标函数是$f(w)=-L(w)$  \n",
    "目标函数的梯度为：$$g(w)=\\nabla{f(w^{(k)})}=\\left(\\frac{\\partial{f(w)}}{\\partial{w_1}},\\frac{\\partial{f(w)}}{\\partial{w_2}},\\cdots,\\frac{\\partial{f(w)}}{\\partial{w_k}}\\right)$$其中$$\\begin{aligned}\n",
    "\\frac{\\partial{f(w)}}{\\partial{w_i}}\n",
    "&= -\\sum^N_{j=1} w_i f_i(y_j,x_j) + \\sum^N_{j=1} \\frac{1}{Z_w(x_j)} \\cdot \\frac{\\partial{Z_w(x_j)}}{\\partial{w_i}}\\\\\n",
    "&= -\\sum^N_{j=1}w_if_i(y_j,x_j)+\\sum^N_{j=1}\\frac{1}{Z_w(x_j)}\\sum_y(\\exp{\\sum^K_{k=1}w_kf_k(y,x_j))}w_if_i(y,x_j)\n",
    "\\end{aligned}$$  \n",
    "根据梯度下降算法：  \n",
    "1. 取初始值$w^{(0)} \\in \\mathbf{R}^n$，置$k=0$  \n",
    "2. 计算$f(w^{(k)})$  \n",
    "3. 计算梯度$g_k=g(w^{(k)})$，当$\\|g_k\\|<\\varepsilon$时，停止迭代，令$w^*=w^{(k)}$；否则令$p_k=-g(w^{(k)})$，求$\\lambda_k$，使$$\n",
    "f(w^{(k)}+\\lambda_k p_k)=\\min_{\\lambda \\geqslant 0}{f(w^{(k)}+\\lambda p_k)}$$  \n",
    "4. 置$w^{(k+1)}=w^{(k)}+\\lambda_k p_k$，计算$f(w^{(k+1)})$  \n",
    "当$\\|f(w^{(k+1)})-f(w^{(k)})\\| < \\epsilon$或$\\|w^{(k+1)}-w^{(k)}\\| < \\epsilon$时，停止迭代，令$w^*=w^{(k+1)}$  \n",
    "5. 否则，置$k=k+1$，转(3)."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题11.4\n",
    "\n",
    "参考图11.6的状态路径图，假设随机矩阵$M_1(x),M_2(x),M_3(x),M_4(x)$分别是\n",
    "$$M_1(x)=\\begin{bmatrix}0&0\\\\0.5&0.5\\end{bmatrix} ,\n",
    "M_2(x)=\\begin{bmatrix}0.3&0.7\\\\0.7&0.3\\end{bmatrix}$$\n",
    "$$\n",
    "M_3(x)=\\begin{bmatrix}0.5&0.5\\\\0.6&0.4\\end{bmatrix},\n",
    "M_4(x)=\\begin{bmatrix}0&1\\\\0&1\\end{bmatrix}$$\n",
    "求以$start=2$为起点$stop=2$为终点的所有路径的状态序列$y$的概率及概率最大的状态序列。\n",
    "\n",
    "**解答：**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[[0, 0], [0.5, 0.5]], [[0.3, 0.7], [0.7, 0.3]], [[0.5, 0.5], [0.6, 0.4]], [[0, 1], [0, 1]]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np#导入处理数据或矩阵的库\n",
    "\n",
    "# 创建随机矩阵\n",
    "M1 = [[0, 0], [0.5, 0.5]]#二维矩阵\n",
    "M2 = [[0.3, 0.7], [0.7, 0.3]]\n",
    "M3 = [[0.5, 0.5], [0.6, 0.4]]\n",
    "M4 = [[0, 1], [0, 1]]\n",
    "M = [M1, M2, M3, M4]#三维矩阵\n",
    "print(M)#查看"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[array([2, 1, 1, 1, 2]), array([2, 1, 1, 2, 2]), array([2, 1, 2, 1, 2]), array([2, 1, 2, 2, 2]), array([2, 2, 1, 1, 2]), array([2, 2, 1, 2, 2]), array([2, 2, 2, 1, 2]), array([2, 2, 2, 2, 2])]\n"
     ]
    }
   ],
   "source": [
    "# 生成路径\n",
    "path = [2]#路径以start=2为起点\n",
    "for i in range(1, 4):\n",
    "    paths = []#初始化路径列表\n",
    "    for _, r in enumerate(path):#同时遍历路径的索引和值\n",
    "        temp = np.transpose(r)#交换坐标轴\n",
    "        paths.append(np.append(temp, 1))\n",
    "        paths.append(np.append(temp, 2))\n",
    "    path = paths.copy()#复制路径\n",
    "\n",
    "path = [np.append(r, 2) for _, r in enumerate(path)]\n",
    "print(path)#查看路径"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[([2, 1, 2, 1, 2], 0.21), ([2, 2, 1, 1, 2], 0.175), ([2, 2, 1, 2, 2], 0.175), ([2, 1, 2, 2, 2], 0.13999999999999999), ([2, 2, 2, 1, 2], 0.09), ([2, 1, 1, 1, 2], 0.075), ([2, 1, 1, 2, 2], 0.075), ([2, 2, 2, 2, 2], 0.06)]\n"
     ]
    }
   ],
   "source": [
    "# 计算概率\n",
    "pr = []#初始化路径及概率列表\n",
    "for _, row in enumerate(path):#同时遍历路径的索引和值\n",
    "    p = 1#每次循环概率重置为1\n",
    "    for i in range(len(row) - 1):\n",
    "        a = row[i]#当前行数\n",
    "        b = row[i + 1]#下一个的行数\n",
    "        p *= M[i][a - 1][b - 1]#根据公式计算概率\n",
    "    pr.append((row.tolist(), p))#将得到的概率及其路径添加到列表中\n",
    "pr = sorted(pr, key=lambda x: x[1], reverse=True)#按照列表维度进行排序，从大到小\n",
    "print(pr)#查看结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "以start=2为起点stop=2为终点的所有路径的状态序列y的概率为：\n",
      "    路径为：2->1->2->1->2 概率为：0.21\n",
      "    路径为：2->2->1->1->2 概率为：0.175\n",
      "    路径为：2->2->1->2->2 概率为：0.175\n",
      "    路径为：2->1->2->2->2 概率为：0.13999999999999999\n",
      "    路径为：2->2->2->1->2 概率为：0.09\n",
      "    路径为：2->1->1->1->2 概率为：0.075\n",
      "    路径为：2->1->1->2->2 概率为：0.075\n",
      "    路径为：2->2->2->2->2 概率为：0.06\n",
      "概率[0.21]最大的状态序列为: 2->1->2->1->2\n"
     ]
    }
   ],
   "source": [
    "# 打印结果\n",
    "print(\"以start=2为起点stop=2为终点的所有路径的状态序列y的概率为：\")\n",
    "for path, p in pr:#遍历所有路径及概率，对结果依次打印\n",
    "    print(\"    路径为：\" + \"->\".join([str(x) for x in path]), end=\" \")\n",
    "    print(\"概率为：\" + str(p))\n",
    "print(\"概率[\" + str(pr[0][1]) + \"]最大的状态序列为:\",\n",
    "      \"->\".join([str(x) for x in pr[0][0]]))#打印最大状态序列结果"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "参考代码：https://blog.csdn.net/GrinAndBearIt/article/details/79229803\n",
    "\n",
    "本文代码更新地址：https://github.com/fengdu78/lihang-code\n",
    "\n",
    "习题解答：https://github.com/datawhalechina/statistical-learning-method-solutions-manual\n",
    "\n",
    "中文注释制作：机器学习初学者公众号：ID:ai-start-com\n",
    "\n",
    "配置环境：python 3.5+\n",
    "\n",
    "代码全部测试通过。\n",
    "![gongzhong](../gongzhong.jpg)"
   ]
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}