摘要：

  条件随机场（Conditional Random Field，CRF）是自然语言处理的基础模型，广泛应用于中文分词、命名实体识别、词性标注等标注场景。

下面通过一个小问题来引入：

  假设你有许多小明同学一天内不同时段的照片，从小明提裤子起床到脱裤子睡觉各个时间段都有（小明是照片控！）。现在的任务是对这些照片进行分类。比如有的照片是吃饭，那就给它打上吃饭的标签；有的照片是跑步时拍的，那就打上跑步的标签；有的照片是开会时拍的，那就打上开会的标签。问题来了，你准备怎么干？一个简单直观的办法就是，不管这些照片之间的时间顺序，想办法训练出一个多元分类器。就是用一些打好标签的照片作为训练数据，训练出一个模型，直接根据照片的特征来分类。例如，如果照片是早上6:00拍的，且画面是黑暗的，那就给它打上睡觉的标签;如果照片上有车，那就给它打上开车的标签。

这样可行吗？

  乍一看可以！但实际上，由于我们忽略了这些照片之间的时间顺序这一重要信息，我们的分类器会有缺陷的。举个例子，假如有一张小明闭着嘴的照片，怎么分类？显然难以直接判断，需要参考闭嘴之前的照片，如果之前的照片显示小明在吃饭，那这个闭嘴的照片很可能是小明在咀嚼食物准备下咽，可以给它打上吃饭的标签；如果之前的照片显示小明在唱歌，那这个闭嘴的照片很可能是小明唱歌瞬间的抓拍，可以给它打上唱歌的标签。所以，为了让我们的分类器能够有更好的表现，在为一张照片分类时，我们必须将与它相邻的照片的标签信息考虑进来。

这——就是条件随机场(CRF)大显身手的地方！

概念理解

成对马尔可夫性

设无向图G中的任意两个没有边连接的节点u,v ，其他所有节点为O，成对马尔可夫性指：给定$Y_O$的条件下，$Y_u$和$Y_v$条件独立

$$P\left(Y_u,Y_v\mid Y_O\right)=P\left(Y_u\mid Y_O\right)P\left(Y_v\mid Y_O\right)$$
局部马尔可夫性

设无向图G的任一节点v，W是与v有边相连的所有节点，O是v、W外的其他所有节点，局部马尔可夫性指：给定$Y_W$的条件下，$Y_v$和$Y_O$条件独立

$$P\left(Y_v,Y_O\mid Y_W\right)=P\left(Y_v\mid Y_W\right)P\left(Y_O\mid Y_W\right)$$

在 $P\left(Y_O/Y_W\right)>0$ 时, 等价地,
$$P\left(Y_v\mid Y_W\right)=P\left(Y_v\mid Y_W,Y_O\right)$$

全局马尔可夫性

设节点集合 $A,B$ 是在无向图 $G$ 中被节点集合C分开的任意节点集合, 全局马尔可夫性指：给定 $Y_C$ 的条件下, $Y_A$ 和 $Y_B$ 条件独立

$$P\left(Y_A,Y_B\mid Y_C\right)=P\left(Y_A\mid Y_C\right)P\left(Y_B\mid Y_C\right)$$

团和最大团

无向图G中任何两个结点均有边连接的结点子集称为团。若C是无向图G的一个团，并且不能再加进任何一个G的结点使其成为更大的一个团，则称此C为最大团。

CRF

条件随机场

设X和Y是随机变量, $P(Y\mid X)$ 是在给定 $X$ 的条件下Y的条件概率分布。若随机变量 $Y$ 构成一个有无向图 $G=(V,E)$ 表示的马尔可夫场, 即
$$P\left(Y_v\mid X,Y_w,w\ne v\right)=P\left(Y_v\mid X,Y_w,w\sim v\right)$$

对任意节点v都成立，则称 $P(Y\mid X)$ 是条件随机场。式中 $w\ne v$ 表示 $w$ 是除v以外的所有节点, $w\sim v$ 表示 $w$ 是与 $v$ 相连接的所有节点。

线性链随机场

对于线性链条件随机场来说，图G的每条边都存在于状态序列Y的相邻两个节点, 最大团 $C$ 是相邻两个节点的集合, X和Y有相同的图 结构意味着每个 $X_i$ 都与 $Y_i⟶$ 对应 ${}_0$
设 $X=\left(X_1,\dots ,X_n\right),Y=\left(Y_1,\dots ,Y_n\right)$ 均为线性链表示的随机变量序列, 若在给定随机变量序列 $X$ 的条件下, 随机变量序列 $Y$ 的 条件分布 $P(Y\mid X)$ 构成条件随机场，即满足马尔可夫性
$$\begin{gathered} P\left(Y_i\mid X,Y_1,\cdots ,Y_{i-1},Y_{i+1},\cdots ,Y_n\right)=P\left(Y_i\mid X,Y_{i-1},Y_{i+1}\right), \\ i=1,\cdots ,n其中当i取1或n时只考虑单边 \end{gathered}$$

则称 $P(Y\mid X)$ 为线性链条件随机场。在标注问题中 $X$ 表示输入观测序列, $Y$ 表示对应的状态序列。

参数化形式

设 $P(Y\mid X)$ 为线性链条件随机场，则在随机变量X取值为x的条件下，随机变量Y取值为y的条件概率具有如下形式：
$$P(y\mid 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]$$
其中$s_l\left(y_i,x,i\right)，l=1,2,\cdots ,L。$ $L是定义在该节点的节点特征函数的总个数，i是当前节点在序列的位置。$
$t_k(y_{i-1},y_i,x,i)，k=1,2,\cdots ,K。$$K是定义在该节点的局部特征函数的总个数，i是是当前节点在序列的位置。$

$$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]$$
上式是基本形式, 表示给定输入序列 $x,$ 对输出序列 $y$ 预闪的条件概率。 $t_k$ 是定义在边上的特征函数，称为转移特征, 依赖于当前和前一个 位置, $s_l$ 是定义在节点上的特征函数, 称为状态特征, 依赖于当前位置。 $t_k$ 和 $s_l$ 都依赖于位置, 是局部特征函数。通常都是0-1函数。线性链条件随机场也是对数线性模型(逻辑回归也是)。

【例子】

这里我们给出一个linear-CRF用于词性标注的实例，为了方便，我们简化了词性的种类。假设输入 的都是三个词的句子, 即 $X=\left(X_1,,X_2,,X_3\right),$ 输出的词性标记为 $Y=\left(Y_1,,Y_2,Y_3\right),$ 其中 Y ∈ { 1 ( Y \in\{1( Y∈{1( 名词 $),2(动词)\}$。

这里只标记出取值为1的特征函数如下：

求标记(1,2,2)的非规范化概率。

利用linear-CRF的参数化公式，我们有：

带入(1,2,2)有：

简化形式

设有 $K_1$ 个转移特征, $K_2$ 个状态特征, $K=K_1+K_2,$ 记
$$f_k\left(y_{i-1},y_i,x,i\right)=\{\begin{array}{l}{t}_k\left(y_{i-1},y_i,x,i\right)k=1,2,\cdots ,K_1\\ s_l\left(y_i,x,l\right)k=K_1+l;l=1,2,\cdots ,K_2\end{array}$$
然后, 对转移与状态特征在各个位置i求和, 记作
$$f_k(y,x)=\sum _{i=1}^n{f}_k\left(y_{i-1},y_i,x,i\right),k=1,2,\cdots ,K$$
用w ${}_k$ 表示特征 $f_k(y,x)$ 的权值, 即
$$w_k=\{\begin{array}{ll}{\lambda }_k,& k=1,2\cdots ,K_1\\ {\mu }_l,& k=K_1+l,l=1,2,\cdots ,K_2\end{array}$$
于是, 条件随机场可以表示为
$$p(y\mid x)=\frac{1}{Z_y(x)}\exp \sum _{k=1}^K{w}_k{f}_k(y,x)$$

矩阵形式

引进特殊的起点和和终点状态标记 $y_0=\mathrm{start},y_{n+1}=\mathrm{stop},$ 这是 $P_w(y\mid x)$ (简化形式)可以通过矩阵形式表示
对观测序列 $x$ 的每一个位置 $i=1,2,\cdots ,n+1,$ 定义一个m阶的矩阵(m是标记 $y_i$ 取值的个数 $)$
$$\begin{array}{rl}{M}_i(x)& =\left[M_i\left(y_{i-1},y_i\mid x\right)\right]\\ M_i\left(y_{i-1},y_i\mid x\right)& =\exp \left(W_i\left(y_{i+1,y_i\mid x}\right)\right)\\ W_i\left(y_{i+1},y_i\mid x\right)& =\sum _{k=1}^K{w}_k{f}_k\left(y_{i-1},y_i,x,i\right)\end{array}$$
这样，给定观测序列 $x,$ 相应标记序列y的非规范化概率可以通过该序列 $n+1$ 个矩阵适当元素的乘积 ${\prod }_{i=1}^{n+1}{M}_i\left(y_{i-1},y_i\mid x\right)$ 表示, 于 是条件概率 $P_w(y\mid x)$ 是
$$P_w(y\mid x)=\frac{1}{Z_w(x)}\prod _{i=1}^{n+1}{M}_i\left(y_{i-1},y_i\mid x\right)$$
其中, $Z_w(x)$ 是规范化因子, 是 $n+1$ 个矩阵的乘积的(start, stop)元素。
$$Z_w(x)={\left(M_1(x)M_2(x)\cdots M_{n+1}(x)\right)}_{\text{start},\text{stop}}$$
注意, $y_0=\mathrm{start}5y_{n+1}=stop$ 表示开始开始状态和终止状态, 规范化因子 $Z_w(x)$ 是以start为起点stop为终点通过状态的所有路径 $y_1{y}_2\cdots y_n$ 的非规范化概率 ${\prod }_{i=1}^{n+1}{M}_i\left(y_{i-1},y_i\mid x\right)$ 之和

CRF的概率计算问题

前向-后向算法

对每个指标$i=0,1,\cdots ,n+1$，定义前向向量${\alpha }_i(x)$
$${\alpha }_0(y|x)=\{\begin{array}{l}1，y=start\\ 0，否则\end{array}$$

$${\alpha }_i^T(x)={\alpha }_{i-1}^T(x)M_i(x)$$

${\alpha }_i\left(y_i\mid x\right)$ 表示在位置 $i$ 的标记是 $y_i$ 并且从 1 到 $i$ 的前 部分标记序列的非规范化概 率， $y_i$ 可取的值有 $m$ 个, 所以 ${\alpha }_i(x)$ 是 $m$ 维列向量。 同样，对每个指标 $i=0,1,\cdots ,n+1,$ 定义后向向量 ${\beta }_i(x)$ :
$$\begin{array}{rl}{\beta }_{n+1}\left(y_{n+1}\mid x\right)& =\{\begin{array}{ll}1,& y_{n+1}=\text{ stop }\\ 0,& \text{ 否则 }\end{array}\\ {\beta }_i\left(y_i\mid x\right)& =\left[M_{i+1}\left(y_i,y_{i+1}\mid x\right)\right]{\beta }_{i+1}\left(y_{i+1}\mid x\right)\end{array}$$
又可表示为
$${\beta }_i(x)=M_{i+1}(x){\beta }_{i+1}(x)$$
${\beta }_i\left(y_i\mid x\right)$ 表示在位置 $i$ 的标记为 $y_i$ 并且从 $i+1$ 到 $n$ 的后部分标记序列的非规范化概率。

概率计算

按照前向-后向向量的定义，很容易计算标记序列在位置 i 是标记 $y_i$ 的条件概率 和在位置 $i-1$ 与 $i$ 是标记 $y_{i-1}$ 和 $y_i$ 的条件概率:
$$P\left(Y_i=y_i\mid x\right)=\frac{{\alpha }_i^{\mathrm{T}}\left(y_i\mid x\right){\beta }_i\left(y_i\mid x\right)}{Z(x)}$$

$$P\left(Y_{i-1}=y_{i-1},Y_i=y_i\mid x\right)=\frac{{\alpha }_{i-1}^{\mathrm{T}}\left(y_{i-1}\mid x\right)M_i\left(y_{i-1},y_i\mid x\right){\beta }_i\left(y_i\mid x\right)}{Z(x)}$$

其中,
$$Z(x)={\alpha }_n^{\mathrm{T}}(x)1=1{\beta }_1(x)$$
1 是元素均为 1 的 m 维列向量。

期望值的计算

$P(Y\mid X)$ 的数学期望。
特佐聚数 $f_k$ 美于条件分布 $P(Y\mid X)$ 的数学期望是
$$\begin{array}{rl}{E}_{P(Y\mid X)}\left[f_k\right]=& \sum _{y}P(y\mid x)f_k(y,x)\\ =& \sum _{i=1}^{n+1}\sum _{y_{i-1}{y}_i}{f}_k\left(y_{i-1},y_i,x,i\right)\frac{{\alpha }_{i-1}^{\mathrm{T}}\left(y_{i-1}\mid x\right)M_i\left(y_{i-1},y_i\mid x\right){\beta }_i\left(y_i\mid x\right)}{Z(x)}\\ & k=1,2,\cdots ,K\end{array}$$
其中 ,
$$Z(x)={\alpha }_n^{\mathrm{T}}(x)1$$

$$\begin{array}{rlr}{E}_{P(X,Y)}\left[f_k\right]& =\sum _{x,y}P(x,y)\sum _{i=1}^{n+1}{f}_k\left(y_{i-1},y_i,x,i\right)& \\ & =\sum _x\tilde{P}(x)\sum _{y}P(y\mid x)\sum _{i=1}^{n+1}{f}_k\left(y_{i-1},y_i,x,i\right)& \\ & =\sum _x\tilde{P}(x)\sum _{i=1}^{n+1}\sum _{y_i-1y_i}{f}_k\left(y_{i-1},y_i,x,i\right)\frac{{\alpha }_{i-1}^T\left(y_{i-1}\mid x\right)M_i\left(y_{i-1},y_i\mid x\right){\beta }_i\left(y_i\mid x\right)}{Z(x)}& \\ & & k=1,2,\cdots ,K\end{array}$$

其中，
$$Z(x)={\alpha }_n^{\mathrm{T}}(x)1$$
假设经聚分布为 $\tilde{P}(X),$ 特征函数 $f_k$ 关于联合分布 $P(X,Y)$ 的数学期望是
$$\begin{array}{rlr}{E}_{P(X,Y)}\left[f_k\right]& =\sum _{x,y}P(x,y)\sum _{i=1}^{n+1}{f}_k\left(y_{i-1},y_i,x,i\right)& \\ & =\sum _x\tilde{P}(x)\sum _{y}P(y\mid x)\sum _{i=1}^{n+1}{f}_k\left(y_{i-1},y_i,x,i\right)& \\ & =\sum _x\tilde{P}(x)\sum _{i=1}^{n+1}\sum _{y_i-1y_i}{f}_k\left(y_{i-1},y_i,x,i\right)\frac{{\alpha }_{i-1}^T\left(y_{i-1}\mid x\right)M_i\left(y_{i-1},y_i\mid x\right){\beta }_i\left(y_i\mid x\right)}{Z(x)}& \\ & & k=1,2,\cdots ,K\end{array}$$
其中，
$$Z(x)={\alpha }_n^{\mathrm{T}}(x)1$$
  式 (11.34) 和式 (11.35) 是特征函数数学期望的一般计算公式。对于转移特征 $t_k\left(y_{i-1},y_i,x,i\right),k=1,2,\cdots ,K_1,$ 可以将式中的 $f_k$ 换成 $t_k:$ 对于状态特征，可以将 式中的 $f_k$ 换成 $s_i,$ 表示为 $s_{l}\left(y_{i}, x, i\right), k=K_{1}+l, l=1,2, \cdots, K_{2} $ 。

  有了式 (11.32)$\sim$ 式 $(11.35),$ 对于给定的观测序列 $x$ 与标记序列 $y,$ 可以通过一次 前向扫描计甘 ${\alpha }_i$ 及 $Z(x),$ 通过一次后向扫描计算 ${\beta }_i,$ 从而计算所有的概率和特征的 期望。

CRF的学习预测算法

迭代尺度法

输入: 特征函数 $t_1,t_2,\cdots ,t_{K_1},s_1,s_2,\cdots ,s_{K_2};$ 经验分布 $\tilde{P}(x,y)$
输出: 参数估计值 $\hat{w}$; 模型 $P_{\hat{w}}$
(1) 对所有 k ∈ { 1 , 2 , ⋯   , K } , k \in\{1,2, \cdots, K\}, k∈{1,2,⋯,K}, 取初值 $w_k=0$
(2) 对每一 k ∈ { 1 , 2 , ⋯   , K } k \in\{1,2, \cdots, K\} k∈{1,2,⋯,K} :
(a) 当 $k=1,2,\cdots ,K_1$ 时, 令 ${\delta }_k$ 是方程
$$\sum _{x,y}\tilde{P}(x)P(y\mid x)\sum _{i=1}^{n+1}{t}_k\left(y_{i-1},y_i,x,i\right)\exp \left({\delta }_{k}T(x,y)\right)=E_{\tilde{P}}\left[t_k\right]$$
的解;
当 $k=K_1+l,l=1,2,\cdots ,K_2$ 时, $,\hat{\Im }{\delta }_{K_1+l}$ 是方程
$$\sum _{x,y}\tilde{P}(x)P(y\mid x)\sum _{i=1}^n{s}_l\left(y_i,x,i\right)\exp \left({\delta }_{K_1+l}T(x,y)\right)=E_{\tilde{P}}\left[s_l\right]$$
的值，式中 $T(x,y)$ 由式 (11.38) 给出。
(b) 更新 $w_k$ 值: $w_k\leftarrow w_k+{\delta }_k$
据 $(x,y)$ 取值可能不同。为了处理这个问題，定义松己特征
$$s(x,y)=S-\sum _{i=1}^{n+1}\sum _{k=1}^K{f}_k\left(y_{i-1},y_i,x,i\right)\text{\hspace{1em}(11.39)}$$
式中 S 是一个常 数。选择足解大的常数 S 使得对训练数据集的所有数据 $(x,y)$, $s(x,y)⩾0$ 成立。这时特征.总数可取 $S_{\text{o }}$
由式 (11.36)，对于特移特征 $t_k,{\delta }_k$ 的更新方程是
$$\begin{array}{c}\sum \tilde{P}(x)P(y\mid x){\sum }_{i=1}^{n+1}{t}_k\left(y_{i-1},y_i,x,i\right)\exp \left({\delta }_{k}S\right)=E_{\hat{P}}\left[t_k\right]\end{array}\text{\hspace{1em}(11.40)}$$

$${\delta }_k=\frac{1}{S}\log \frac{E_{\tilde{P}}\left[t_k\right]}{E_P\left[t_k\right]}\text{\hspace{1em}(11.41)}$$

其中。
$$E_P\left(t_k\right)=\sum _x\tilde{P}(x)\sum _{i=1}^{n+1}\sum _{y_{i-1},y_i}{t}_k\left(y_{i-1},y_i,x,i\right)\frac{{\alpha }_{i-1}^{\mathrm{T}}\left(y_{i-1}\mid x\right)M_i\left(y_{i-1},y_i\mid x\right){\beta }_i\left(y_i\mid x\right)}{Z(x)}\text{\hspace{1em}(11.42)}$$
同样由式 (11.37)，对于状态特征 $s_l,{\delta }_k$ 的更新方程是
$$\begin{array}{c}\sum \tilde{P}(x)P(y\mid x){\sum }_{i=1}^n{s}_l\left(y_i,x,i\right)\exp \left({\delta }_{K_1+l}S\right)=E_{\bar{P}}\left[s_i\right]\end{array}\text{\hspace{1em}(11.43)}$$

$${\delta }_{K_1+l}=\frac{1}{S}\log \frac{E_{\tilde{P}}\left[s_l\right]}{E_P\left[s_l\right]}\text{\hspace{1em}(11.44)}$$

其中，
$$E_P\left(s_l\right)=\sum _x\tilde{P}(x)\sum _{i=1}^n\sum _{y_i}{s}_l\left(y_i,x,i\right)\frac{{\alpha }_i^T\left(y_i\mid x\right){\beta }_i\left(y_i\mid x\right)}{Z(x)}\text{\hspace{1em}(11.45)}$$
以上算法称为算法 S。在算法 S 中需要使常数 S 取足够大，这样一来，每步迭代
的增量向量会变大，算法收签会变慢。算法 T 试图解决这个问题。算法 T 对每个观测
字列 x 计算其特休总数最大值 $T(x)$ :

拟牛顿法

输入：特征函数 $f_1,f_2,\cdots ,f_n;$ 经验分布 $\tilde{P}(X,Y)$
输出: 最优参数值 $\hat{w}$; 最优模型 $P_{\hat{w}}(y\mid x)$ 。
(1)选定初始点 $w^{(0)},$ 取 $B_0$ 为正定对称矩阵, 置 $k=0$ o
(2) 计算 $g_k=g\left(w^{(k)}\right)$ 。若 $g_k=0,$ 则停止计算; 否则转 (3)
(3) 由 $B_k{p}_k=-g_k$ 求出 $p_k$
(4)一维搜索: 求 ${\lambda }_k$ 使得
$$f\left(w^{(k)}+{\lambda }_k{p}_k\right)=\underset{\lambda ⩾0}{\min }f\left(w^{(k)}+\lambda p_k\right)$$
(5) 置 $w^{(k+1)}=w^{(k)}+{\lambda }_k{p}_k$
(6) 计算 $g_{k+1}=g\left(w^{(k+1)}\right),$ 若 $g_{k+1}=0,$ 则停止计算; 否则, 按下式求出 $B_{k+1:}$
$$B_{k+1}=B_k+\frac{y_k{y}_k^{\mathrm{T}}}{y_k^{\mathrm{T}}{\delta }_k}-\frac{B_k{\delta }_k{\delta }_k^{\mathrm{T}}{B}_k}{{\delta }_k^{\mathrm{T}}{B}_k{\delta }_k}$$
其中
$$y_k=g_{k+1}-g_k,{\delta }_k=w^{(k+1)}-w^{(k)}$$
(7)置$k=k+1$，转(3)。

维特比算法

输入：模型特征向量 $F(y,x)$ 和权值向量 $w,$ 观测序列 $x=\left(x_1,x_2,\cdots ,x_n\right)$

输出：最优路径 $y^{\ast }=\left(y_1^{\ast },y_2^{\ast },\cdots ,y_n^{\ast }\right)$

(1)初始化
$${\delta }_1(j)=w\cdot F_1\left(y_0=\text{ start },y_1=j,x\right),j=1,2,\cdots ,m$$
(2) 递推。对 $i=2,3,\cdots ,n$
δ i ( l ) = max ⁡ 1 ⩽ j ⩽ m { δ i − 1 ( j ) + w ⋅ F i ( y i − 1 = j , y i = l , x ) } , l = 1 , 2 , ⋯   , m Ψ i ( l ) = arg ⁡ max ⁡ 1 ⩽ j ⩽ m { δ i − 1 ( j ) + w ⋅ F i ( y i − 1 = j , y i = l , x ) } , l = 1 , 2 , ⋯   , m \begin{array}{c} \delta_{i}(l)=\max _{1 \leqslant j \leqslant m}\left\{\delta_{i-1}(j)+w \cdot F_{i}\left(y_{i-1}=j, y_{i}=l, x\right)\right\}, \quad l=1,2, \cdots, m \\ \Psi_{i}(l)=\arg \max _{1 \leqslant j \leqslant m}\left\{\delta_{i-1}(j)+w \cdot F_{i}\left(y_{i-1}=j, y_{i}=l, x\right)\right\}, \quad l=1,2, \cdots, m \end{array} δi​(l)=max1⩽j⩽m​{δi−1​(j)+w⋅Fi​(yi−1​=j,yi​=l,x)},l=1,2,⋯,mΨi​(l)=argmax1⩽j⩽m​{δi−1​(j)+w⋅Fi​(yi−1​=j,yi​=l,x)},l=1,2,⋯,m​
(3) 终止
$$\underset{y}{\max }(w\cdot F(y,x))=\underset{1⩽j⩽m}{\max }{\delta }_n(j)$$

$$y_n^{\ast }=\arg \underset{1⩽j⩽m}{\max }{\delta }_n(j)$$

（4）返回路径
$$y_i^{\ast }={\Psi }_{i+1}\left(y_{i+1}^{\ast }\right),i=n-1,n-2,\cdots ,1$$
求得最优路径 $y^{\ast }=\left(y_1^{\ast },y_2^{\ast },\cdots ,y_n^{\ast }\right)$

代码实现

from numpy import *

#这里定义T为转移矩阵列代表前一个y(ij)代表由状态i转到状态j的概率,Tx矩阵x对应于时间序列
#这里将书上的转移特征转换为如下以时间轴为区别的三个多维列表，维度为输出的维度
T1 = [[0.6, 1], [1, 0]]
T2 = [[0, 1], [1, 0.2]]
#将书上的状态特征同样转换成列表,第一个是为y1的未规划概率，第二个为y2的未规划概率
S0 = [1, 0.5]
S1 = [0.8, 0.5]
S2 = [0.8, 0.5]
Y = [1, 2, 2]  #即书上例一需要计算的非规划条件概率的标记序列
Y = array(Y) - 1  #这里为了将数与索引相对应即从零开始
P = exp(S0[Y[0]])
for i in range(1, len(Y)):
    P *= exp((eval('S%d' % i)[Y[i]]) + eval('T%d' % i)[Y[i - 1]][Y[i]])
print(P)
print(exp(3.2))

Reference:

• https://www.jianshu.com/p/55755fc649b1
• https://www.cnblogs.com/weilonghu/p/11924962.html
• https://zhuanlan.zhihu.com/p/29989121