专栏首页Michael阿明学习之路条件随机场(Conditional Random Field,CRF)

条件随机场(Conditional Random Field,CRF)

1. 概率无向图模型

概率无向图模型(probabilistic undirected graphical model),又称为马尔可夫随机场(Markov random field),是一个可以由无向图表示的联合概率分布。

1.1 模型定义

图Graph包含顶点node、edge,无向图指的是边没有方向的图。

概率图模型指的是,图中的表示随机变量之间的概率依赖关系。

无向图表示的随机变量之间存在 成对马尔科夫性、局部马尔科夫性、全局马尔科夫性

  • 成对马尔可夫性 任意不相连的两个结点
u,v

分别对应随机变量

Y_u,Y_v

。其他所有结点为

O

, 对应随机变量组为

Y_O

。 成对马尔可夫性指:

\color{red}P(Y_u,Y_v|Y_O) = P(Y_u|Y_O)P(Y_v|Y_O)
  • 局部马尔可夫性
v

是无向图中任意一个结点,

W

是与

v

有连接的所有结点,

O

v

W

以外的其他所有结点。 局部马尔可夫性指:

\color{red}P(Y_v,Y_O|Y_W) = P(Y_v|Y_W)P(Y_O|Y_W)

P(Y_O|Y_W) > 0

时,上式等价于

\color{red}P(Y_v|Y_W) = P(Y_v|Y_W,Y_O)
  • 全局马尔可夫性 设结点集合
A,B

是图中被结点集合

C

分开的任意结点集合 全局马尔可夫性指:

\color{red}P(Y_A,Y_B|Y_C) = P(Y_A|Y_C)P(Y_B|Y_C)

上述成对的、局部的、全局的马尔可夫性定义是等价

1.2 概率无向图模型的因子分解

团与最大团 的定义: 任何两个结点均有连接的结点子集称为,若

C

是无向图的一个团,且不能再加进任何一个结点使其成为一个更大的团,则称

C

最大团(maximal clique)

例如,上图中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

没有边连接。

将概率无向图模型的联合概率分布表示为其 最大团 上的随机变量的函数的乘积形式的操作,称为 概率无向图模型的因子分解(factorization)

给定概率无向图模型,

C

是图

G

上的最大团,

Y_C

表示

C

对应的随机变量。那么,概率无向图模型的联合概率分布

P(Y)

可写作所有最大团

C

上的函数

\Psi(Y_C)

乘积形式:

\color{red}P(Y) = \frac{1}{Z} \prod\limits_C \Psi_C(Y_C),\quad 其中Z=\sum\limits_Y \prod\limits_C \Psi_C(Y_C)是规范化因子

函数

\Psi_C(Y_C)

称为势函数(potential function),通常定义为指数函数

\Psi_C(Y_C) = \exp \{-E(Y_C)\}

2. 条件随机场的定义与形成

2.1 条件随机场的定义

条件随机场:

X

Y

是随机变量,

P(Y|X)

是在给定

X

的条件下

Y

的条件概率分布。若随机变量

Y

构成一个无向图的马尔科夫随机场,即:

\color{red}P(Y_v|X,Y_\omega, \omega \neq v) = P(Y_v|X,Y_\omega,\omega \sim v)

左边表示,条件里是多个

Y_\omega

, 且

\omega \neq v

;右边是多个

Y_\omega

, 且

\omega

都与

v

相连。则称条件概率分布

P(Y|X)

为条件随机场。

线性链条件随机场:

\color{red}P(Y_i|X,Y_1,...,Y_{i-1},Y_{i+1},...,Y_n) = P(Y_i|X,Y_{i-1},Y_{i+1})\\ i=1,2,...,n(在i=1,n时只考虑单边)

则称条件概率分布

P(Y|X)

为线性链条件随机场。在标注问题中,

X

表示输入观测序列,

Y

表示对应的输出标记序列或状态序列。

2.2 条件随机场的参数化形式

根据上面,可以给出线性链条件随机场

P(Y|X)

的因子分解式,各因子是定义在相邻两个结点(最大团)上的势函数。在随机变量

X

取值为

x

的条件下,随机变量

Y

取值为

y

的条件概率具有如下形式:

\begin{aligned} \color{red}P(y|x) &\color{red}= \frac{1}{Z(x)} \exp \Bigg( \sum\limits_{i,k} \lambda_k t_k (y_{i-1},y_i,x,i) + \sum\limits_{i,l} \mu_ls_l(y_i,x,i)\Bigg)\\ 其中,Z(x) &= \sum\limits_y \exp \Bigg( \sum\limits_{i,k} \lambda_k t_k (y_{i-1},y_i,x,i) + \sum\limits_{i,l} \mu_ls_l(y_i,x,i)\Bigg) \end{aligned}

式中,

t_k,s_l

是特征函数,

\lambda_k,\mu_l

是对应权值。

Z(x)

是规范化因子。

\color{red} t_k

上的特征函数,称为转移特征,依赖于当前和前一个位置

\color{red} s_l

结点特征函数,称为状态特征,依赖于当前位置

\color{red} t_k, s_l

都依赖于位置,是局部特征函数。函数取值 1 或者 0

  • 条件随机场完全由
t_k,s_l

特征函数,

\lambda_k,\mu_l

对应权值 确定

  • 线性链条件随机场是对数线性模型(log linear model)

例题

设有一标注问题:输入观测序列

X=(X_1,X_2,X_3)

,输出标记序列

Y=(Y_1,Y_2,Y_3)

Y_1,Y_2,Y_3

取值于

\mathcal{Y} = \{1,2\}

.

假设特征

t_k,s_l

和对应权值

\lambda_k,\mu_l

如下:

\begin{aligned} t_1&=t_1(y_{i-1}=1,y_i=2,x,i), i=2,3 , \lambda_1=1, 特征函数取值为1 (其余条件取0)\\ t_2 &= t_2(y_1=1,y_2=1,x,2), \quad\quad \lambda_2=0.6\\ t_3 &= t_3(y_2=2,y_3=1,x,3) ,\quad\quad \lambda_3=1\\ t_4 &= t_4(y_1=2,y_2=1,x,2) ,\quad\quad \lambda_4=1\\ t_5 &= t_5(y_2=2,y_3=2,x,3) ,\quad\quad \lambda_5=0.2\\ s_1 &= s_1(y_1=1,x,1), \quad\quad\quad\quad\quad \mu_1=1\\ s_2 &= s_2(y_i=2,x,i), i=1,2 \quad\quad \mu_2=0.5\\ s_3 &= s_3(y_i=1,x,i), i=2,3 \quad\quad \mu_3=0.8\\ s_4 &= s_4(y_3=2,x,3), \quad\quad\quad\quad\quad \mu_4=0.5 \end{aligned}

对给定的观测序列

x

,求标记序列为

y=(y_1,y_2,y_3) = (1,2,2)

的非规范化条件概率(未除以规范化因子的条件概率)。

解: 由线性链条件随机场模型有:

\begin{aligned} P(y|x) &\propto \exp \Bigg( \sum\limits_{i,k} \lambda_k t_k (y_{i-1},y_i,x,i) + \sum\limits_{i,l} \mu_ls_l(y_i,x,i)\Bigg)\\ &= \exp \Bigg[\sum\limits_{k=1}^5 \lambda_k \sum\limits_{i=2}^3t_k (y_{i-1},y_i,x,i) + \sum\limits_{k=1}^4 \mu_k \sum\limits_{i=1}^3 s_k(y_i,x,i) \Bigg]\\ &= \exp (1+0.2+1+0.5+0.5) = \exp (3.2) \end{aligned}

2.3 条件随机场的简化形式

  • 统一
K_1

转移特征和

K_2

状态特征,

K=K_1+K_2

,记特征函数:

f_k(y_{i-1},y_i,x,i)=\left\{ \begin{aligned} t_k(y_{i-1},y_i,x,i), \quad\quad\quad\quad k=1,2,...,K_1 \\ s_l(y_i,x,i), \quad k=K_1+l; l=1,2,...,K_2 \end{aligned} \right.
  • 对转移和状态特征在各个位置
i

求和,记作:

f_k(y,x) = \sum\limits_{i=1}^n f_k(y_{i-1},y_i,x,i),k=1,2,...,K
\omega_k

表示特征

f_k(y,x)

的权值,即

\omega_k=\left\{ \begin{aligned} \lambda_k, \quad\quad\quad\quad\quad\quad k=1,2,...,K_1 \\ \mu_l, \quad k=K_1+l; l=1,2,...,K_2 \end{aligned} \right.
  • 条件随机场可表示为
P(y|x) = \frac{1}{Z(x)} \exp \sum\limits_{k=1}^K \omega_kf_k(y,x)\\ Z(x) = \sum\limits_y \exp \sum\limits_{k=1}^K \omega_kf_k(y,x)
\omega

表示权值向量,

\omega = (\omega_1,\omega_2,...,\omega_K)^T
F(y,x)

表示全局特征向量,即

F(y,x) = (f_1(y,x),f_2(y,x),...,f_K(y,x))^T
  • 条件随机场写成向量内积形式:
\color{red}P_\omega(y|x) = \frac{\exp (\omega \cdot F(y,x))}{Z_\omega(x)}, 其中Z_\omega(x)= \sum\limits_y\exp (\omega \cdot F(y,x))

2.4 条件随机场的矩阵形式

  • 在标记序列的两端添加首尾状态标记
y_0=start 、y_{n+1}=stop
  • 引进
M_i(y_{i−1},y_i|x) = \exp\sum \limits_{k=1}^K w_k f_k(y_{i−1},y_i,x,i),i=1,2,...,n+1

,对比2.2节的表达式,可见该式少了对位置

i

求和

  • 对每个位置创建一个
m*m

的方阵(m为状态的个数,行为

i-1

位置的状态,列为

i

位置的状态,值为

M_i(y_{i−1},y_i|x)

, 用矩阵

M_i(x) = [M_i(y_{i−1},y_i|x)]

来表示所有的情况)

  • 又因为
\prod\limits_i \Bigg[ \exp \Bigg(\sum\limits_{k=1}^K w_k f_k(y_{i−1},y_i,x,i) \Bigg)\Bigg] = \exp \Bigg(\sum\limits_{k=1}^K w_k\sum\limits_i f_k(y_{i−1},y_i,x,i) \Bigg)
  • 于是条件概率
\color{red}P_\omega(y|x) = \frac{1}{Z_\omega(x)} \prod\limits_{i=1}^{n+1} M_i(y_{i-1},y_i|x)
Z_\omega(x)

是规范化因子,是

n+1

个矩阵乘积的

(start,stop)

位置的元素,是路径

start,y_1,y_2,...,y_n,stop

所有可能的状态组合的非规范化概率之和。

\color{red} Z_\omega(x) = [M_1(x)M_2(x)\cdot\cdot\cdot M_{n+1}(x)]_{start,stop}

例题

假设有如下线性链条件随机场,观测序列

x

, 状态序列

y, \quad i=1,2,3,\quad n=3

, 标记

y_i \in \{1,2\}

, 假设

y_0 = start = 1, y_4 = stop = 1

,各个位置的随机矩阵

M_1(x),M_2(x),M_3(x),M_4(x)

求状态序列

y

start

为起点,

stop

为终点所有路径的非规范化概率及规范化因子。

解: 所有可能的路径有 8 条: 各路径的非规范化概率是:

a_{01}b_{11}c_{11},\quad a_{01}b_{11}c_{12},\quad a_{01}b_{12}c_{21},\quad a_{01}b_{12}c_{22}\\ a_{02}b_{21}c_{11},\quad a_{02}b_{21}c_{12},\quad a_{02}b_{22}c_{21},\quad a_{02}b_{22}c_{22}

规范化因子

Z_\omega(x) = [M_1(x)M_2(x) M_3(x)M_{4}(x)]_{1,1}\\ a_{01}b_{11}c_{11}+ a_{01}b_{11}c_{12}+ a_{01}b_{12}c_{21}+a_{01}b_{12}c_{22}+\\ a_{02}b_{21}c_{11}+ a_{02}b_{21}c_{12}+ a_{02}b_{22}c_{21}+a_{02}b_{22}c_{22}

矩阵其他3个位置为 0 。可见规范化因子恰好等于所有路径非规范化概率之和

3. 条件随机场的概率计算问题

  • 给定条件随机场
P(Y|X)

,输入序列

x

,输出序列

y
  • 计算条件概率
P(Y_i = y_i|x),\quad P(Y_{i-1} = y_{i-1},Y_i = y_i|x)

以及相应数学期望

类似HMM,引进前向-后向向量进行计算。

3.1 前向-后向算法

对每个位置

i = 0,1,...,n+1

,定义前向向量

\alpha_i(x)

\alpha_0(y|x)=\left\{ \begin{aligned} 1, \quad y=start\\ 0, \quad\quad\quad 否则 \end{aligned} \right.

递归公式:

\alpha_i^T(y_i|x) = \alpha_{i-1}^T(y_{i-1}|x)[M_i(y_{i-1},y_i|x)],\quad i=1,2,...,n+1

又可以表示为:

\color{red}\alpha_i^T(x) = \alpha_{i-1}^T(x)M_i(x)
\alpha_i(y_i|x)

表示在位置

i

的标记是

y_i

并且从 1 到

i

的前部分标记序列的非规范化概率,

y_i

可取的值有

m

个,所以

\alpha_i(x)

m

维列向量,

T

表示转置。

同样,对每个位置

i = 0,1,...,n+1

,定义后向向量

\beta_i(x)

\beta_{n+1}(y_{n+1}|x)=\left\{ \begin{aligned} 1, \quad y_{n+1}=stop\\ 0, \quad\quad\quad\quad 否则 \end{aligned} \right.
\beta_i(y_i|x) = [M_{i+1}(y_i,y_{i+1}|x)]\beta_{i+1}(y_{i+1}|x)

又可以表示为:

\color{red} \beta_i(x) = M_{i+1}(x) \beta_{i+1}(x)
\beta_i(y_i|x)

表示在位置

i

的标记是

y_i

并且从

i+1

n

的后部分标记序列的非规范化概率。

3.2 概率计算

根据前后向向量的定义,可知:

P(Y_i = y_i|x) = \frac{\alpha_i^T(y_i|x) \beta_i(y_i|x)}{Z(x)}\\ P(Y_{i-1}=y_{i-1},Y_i = y_i|x) = \frac{\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}\\ 其中,Z(x) = \alpha_n^T(x)\mathbf{1} = \mathbf{1}\beta_1(x),\mathbf{1}是元素均为1的m维列向量。

3.3 期望值的计算

  • 特征函数
f_k

关于条件分布

P(Y|X)

的数学期望

\begin{aligned} E_{P(Y|X)}[f_k] &= \sum_{y}P(y|x)f_k(y,x)\\ &= \sum_{y}P(y|x)\sum_{i=1}^{n+1} f_k(y_{i-1},y_i,x,i)\\ &= \sum_{i=1}^{n+1}\sum_{y_{i-1}y_i}f_k(y_{i-1},y_i,x,i)P(Y_{i-1}=y_{i-1},Y_i=y_i|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}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}\\ \end{aligned}

其中,

k=1,2,...,K

Z(x) = \alpha_n^T(x) \mathbf{1}
  • 假设边缘分布
P(X)

的经验分布为

\tilde P(X)

,特征函数

f_k

关于联合分布

P(X,Y)

的数学期望:

\begin{aligned} E_{P(X,Y)}[f_k] &= \sum_{x,y}P(x,y)f_k(y,x)\\ &= \sum_x\tilde P(x) \sum_{y}P(y|x)\sum_{i=1}^{n+1} f_k(y_{i-1},y_i,x,i)\\ &= \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}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)} \end{aligned}

其中,

k=1,2,...,K

Z(x) = \alpha_n^T(x) \mathbf{1}

通过一次前向扫描计算

\alpha_i,\quad Z(x)

,一次后向扫描计算

\beta_i

,可以计算所有的概率、特征的期望

4. 条件随机场的学习算法

学习方法包括极大似然估计正则化的极大似然估计

具体的优化实现算法有改进的迭代尺度法IIS梯度下降法拟牛顿法

看不懂(跳过)

5. 条件随机场的预测算法

给定条件随机场

P(Y|X)

和观测序列

x

,求条件概率最大的状态序列

y^*

。与 HMM 类似,使用维特比算法

由式

P_\omega(y|x) = \frac{\exp (\omega \cdot F(y,x))}{Z_\omega(x)}

可得:

\begin{aligned} y^* &= \argmax_y P_\omega(y|x)\\ &= \argmax_y \frac{\exp (\omega \cdot F(y,x))}{Z_\omega(x)}\\ &= \argmax_y \exp(\omega \cdot F(y,x))\\ &= \argmax_y (\omega \cdot F(y,x)) \end{aligned}
  • 预测问题变成求非规范化概率最大的最优路径问题:
\color{red}\max\limits_y (\omega \cdot F(y,x))

其中:

\begin{aligned} \omega &= (\omega_1,\omega_2,...,\omega_K)^T\\ F(y,x) &= (f_1(y,x),f_2(y,x),...,f_K(y,x))^T\\ f_k(y,x) &= \sum\limits_{i=1}^nf_k(y_{i-1},y_i,x,i),\quad k=1,2,...,K \end{aligned}

最优路径问题:

\color{red}\max\limits_y (\omega \cdot F(y,x)) = \max\limits_y \sum\limits_{i=1}^n\omega \cdot F_i(y_{i-1},y_i,x)

其中,

F_i(y_{i-1},y_i,x) = (f_1(y_{i-1},y_i,x,i),f_2(y_{i-1},y_i,x,i),...,f_K(y_{i-1},y_i,x,i))^T

是局部特征向量

维特比算法:

  • 先求出位置 1 的各个状态
j=1,2,...,m

的非规范化概率:

\delta_i(j) = \omega \cdot F_1(y_0 = start, y_1=j,x), \quad j=1,2,...,m
  • 求出到位置
i=2,3,...,n

的各个状态

l=1,2,...,m

的非规范化概率的最大值,同时记录最大路径

\delta_i(l) = \max\limits_{1 \leq j \leq m} \{ \delta_{i-1}(j) + \omega \cdot F_i(y_{i-1}=j, y_i=l,x) \}, \quad l=1,2,...,m
\Psi_i(l) = \argmax\limits_{1 \leq j \leq m} \{ \delta_{i-1}(j) + \omega \cdot F_i(y_{i-1}=j, y_i=l,x) \}, \quad l=1,2,...,m
i=n

时终止,求得非规范化概率最大值

\max\limits_y (\omega \cdot F(y,x)) = \max\limits_{1 \leq j \leq m} \delta_n(j)

,最优路径终点

y_n^* = \argmax\limits_{1 \leq j \leq m} \delta_n(j)
  • 由最优路径终点返回,
y_i^* = \Psi_{i+1}(y_{i+1}^*), \quad i = n-1,n-2,...,1
  • 求得最优路径
y^* = (y_1^*,y_2^*,...,y_n^*)^T

例题

设有一标注问题:输入观测序列

X=(X_1,X_2,X_3)

,输出标记序列

Y=(Y_1,Y_2,Y_3)

Y_1,Y_2,Y_3

取值于

\mathcal{Y} = \{1,2\}

.

假设特征

t_k,s_l

和对应权值

\lambda_k,\mu_l

如下:

\begin{aligned} t_1&=t_1(y_{i-1}=1,y_i=2,x,i), i=2,3 , \lambda_1=1, 特征函数取值为1 (其余条件取0)\\ t_2 &= t_2(y_1=1,y_2=1,x,2), \quad\quad \lambda_2=0.6\\ t_3 &= t_3(y_2=2,y_3=1,x,3) ,\quad\quad \lambda_3=1\\ t_4 &= t_4(y_1=2,y_2=1,x,2) ,\quad\quad \lambda_4=1\\ t_5 &= t_5(y_2=2,y_3=2,x,3) ,\quad\quad \lambda_5=0.2\\ s_1 &= s_1(y_1=1,x,1), \quad\quad\quad\quad\quad \mu_1=1\\ s_2 &= s_2(y_i=2,x,i), i=1,2 \quad\quad \mu_2=0.5\\ s_3 &= s_3(y_i=1,x,i), i=2,3 \quad\quad \mu_3=0.8\\ s_4 &= s_4(y_3=2,x,3), \quad\quad\quad\quad\quad \mu_4=0.5 \end{aligned}

求给定的观测序列

x

对应的最优标记序列

y^* = (y_1^*,y_2^*,y_3^*)

解:

  • 初始化
\delta_1(j) = \omega \cdot F_1(y_0 = start, y_1 = j, x), \quad j=1,2 \quad \quad \quad \quad \quad \quad \quad \quad \\ i=1, \quad \delta_1(1) = \mu_1s_1=1,\quad \delta_1(2) = \mu_2s_2 = 0.5 \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad
  • 递推
\begin{aligned} i=2\quad \delta_2(l) &=\max\limits_j \{\delta_1(j) + \omega \cdot F_2(j,l,x)\}\\ \delta_2(1) &= \max\{1+\lambda_2t_2 + \mu_3s_3,\quad 0.5+\lambda_4t_4 + \mu_3s_3\} = \max\{2.4,2.3\} = 2.4\\ &\quad\Psi_2(1) = 1\\ \delta_2(2) &= \max\{1+\lambda_1t_1 + \mu_2s_2,\quad 0.5+ \mu_2s_2\} = \max\{2.5,1\} = 2.5\\ &\quad\Psi_2(2) = 1\\ i=3 \quad \delta_3(l) &=\max\limits_j \{\delta_2(j) + \omega \cdot F_3(j,l,x)\}\\ \delta_3(1) &= \max\{2.4+ \mu_3s_3,\quad 2.5+\lambda_3t_3 + \mu_3s_3\} = \max\{3.2,4.3\} = 4.3\\ &\quad\Psi_3(1) = 2\\ \delta_3(2) &= \max\{2.4+\lambda_1t_1 + \mu_4s_4,\quad 2.5+\lambda_5t_5 + \mu_4s_4\} = \max\{3.9,3.2\} = 3.9\\ &\quad\Psi_3(2) = 1\\ \end{aligned}
  • 终止
\max\limits_y(\omega \cdot F(y,x)) = \max \delta_3(l) = \delta_3(1) = 4.3\\ y_3^* = \argmax\limits_l \delta_3(l) = 1
  • 返回
y_2^* = \Psi_3(y_3^*) = \Psi_3(1) = 2\\ y_1^* = \Psi_2(y_2^*) = \Psi_2(2) = 1

所以最优状态序列为

y^* = (y_1^*,y_2^*,y_3^*)=(1,2,1)

例题python代码

# -*- coding:utf-8 -*-
# Python 3.7
# @Time: 2020/2/6 20:42
# @Author: Michael Ming
# @Website: https://michael.blog.csdn.net/
# @File: ConditionalRandomField_viterbi.py
import numpy as np


def viterbi(s, t):
    time = len(s)
    y_state = [0, 1]  # 表示状态 1,2
    m = len(y_state)  # 状态数量
    y_star = np.zeros((time), dtype=np.int32)  # 最优路径
    delta = np.zeros((time, m))  # 最大概率矩阵(可以DP状态压缩)
    psi = np.zeros((time, m), dtype=np.int32)  # 记录最优路径

    # 初始化delta
    delta[0][0] = s[0][0]
    delta[0][1] = s[0][1]

    # 递推
    for i in range(1, time):
        for j in range(m):
            temp = [delta[i - 1][k] + s[i][j] + t[i][k][j] for k in range(m)]
            # i表示时间,从k状态转移到j状态
            psi[i][j] = np.argmax(temp)  # 返回最大值的下标
            delta[i][j] = temp[psi[i][j]]  # 最大的概率填入

    # 终止
    y_star[time - 1] = np.argmax(delta[time - 1])

    # 返回
    for i in range(time - 2, -1, -1):
        y_star[i] = psi[i + 1][y_star[i + 1]]
    return y_star, delta, psi


def crf_viterbi():
    # 状态特征
    s = np.array([[1, 0.5],
                  [0.8, 0.5],
                  [0.8, 0.5]])
    # 转移特征
    t = np.array([[[0, 0],
                   [0, 0]],  # 辅助,使得后面序号方便
                  [[0.6, 1],
                   [1, 0]],
                  [[0, 1],
                   [1, 0.2]]])
    y_star, delta, psi = viterbi(s, t)

    print("最优路径:", y_star + 1)  # +1表示所有的都+1,序号从1开始
    print("概率矩阵:\n", delta)
    psi[1:] += 1  # 序号从1开始,第0行没用
    print("Psi路径:\n", psi)


if __name__ == '__main__':
    crf_viterbi()

运行结果,与上面一致。

最优路径: [1. 2. 1.]
概率矩阵:
 [[1.  0.5]
 [2.4 2.5]
 [4.3 3.9]]
Psi路径:
 [[0 0]
 [1 1]
 [2 1]]

Process finished with exit code 0

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 感知机(Perceptron)

    感知机1957年由Rosenblatt(罗森布拉特)提出,是神经网络与支持向量机的基础。

    Michael阿明
  • LeetCode 306. 累加数(暴力回溯)

    一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。

    Michael阿明
  • 支持向量机(Support Vector Machines,SVM)

    线性可分SVM学习方法,对线性不可分训练数据是不适用的,怎么将它扩展到线性不可分,需要修改硬间隔最大化,使其成为软间隔最大化。

    Michael阿明
  • 轻量级Qt键盘-简拼输入

      字库加载在QMap<QString, QList<QPair<QString, QString>> >容器中。

    Qt君
  • 被问到傻傻不懂synchronized底层原理

    修饰实例方法,作用于当前实例加锁,进入同步代码前要获得当前实例的锁静态方法,作用于当前类对象加锁,进入同步代码前要获得当前类对象的锁修饰代码块,指定加锁对象,对...

    java乐园
  • 看完苹果2019新品发布会,你觉得苹果还有未来吗?

    苹果的新品发布会在9月11日如期而至,除了再次被调侃的“浴霸”造型之外,质疑其未来的声音继续不绝于耳。

    庄帅
  • Python 15.2 POP3 收取邮

    收取邮件就是编写一个MUA作为客户端,从MDA把邮件获取到用户的电脑或者手机上。收取邮件最常用的就是POP3协议。

    py3study
  • 渣渣菜鸡的蚂蚁金服面试经历(二)

    17、如果存取相同的数据,ArrayList 和 LinkedList 谁占用空间更大?

    zhisheng
  • 小朋友学C语言(14):分苹果(小学奥数题)

    题目 有两堆一样多的苹果,老师将第一堆苹果分给男生,每人4个,最后剩下6个。 老师又将第二堆苹果分给女生,每个5个,最后剩下5个。 已知男生比女生多1人。 求:...

    海天一树
  • 蓝桥杯 基础练习 数的读法

      Tom教授正在给研究生讲授一门关于基因的课程,有一件事情让他颇为头疼:一条染色体上有成千上万个碱基对,它们从0开始编号,到几百万,几千万,甚至上亿。   比...

    Debug客栈

扫码关注云+社区

领取腾讯云代金券