《阿里云天池大赛赛题解析（深度学习篇）》学习笔记（2）实体识别

实体识别任务

实体通常可分三类：

1. 实体类：人名、机构名、地名等。
2. 时间类：时间、日期等。
3. 数字类：货币、百分比等。

动词为非实体。

• 英文实体识别工具：斯坦福NER（Named Entity Recognition，命名实体识别）。

• 中文实体识别工具：哈尔滨工业大学语言云。

  实体识别任务是一个序列标注（Sequence Tagging）任务。

BIOES数据标注方式

Begin/Intermediate/Other/End/Single。

开头/中间/非实体/结尾/单独。

传统机器学习方法

包括基于规则的方法、聚类方法与监督学习方法。

基础知识：概率图模型

监督学习方法。

使用图表示随机变量之间相互作用的一种概率模型。

每个节点代表一个随机变量。

每条边代表随机变量之间的直接关系。

一般分为有向图模型和无向图模型。

1. 有向图模型

   又称贝叶斯网络（Bayesian Network）。

   所有边均有向。

   边代表随机变量间的条件概率。

   图模型的联合分布概率：

   P ( x ) = P ( x 1 ) P ( x 2 ∣ x 1 ) P ( x 3 ∣ x 2 ) P ( x 4 ∣ x 2 ) P ( x 5 ∣ x 3 , x 2 ) P(x)=P(x_1)P(x_2|x_1)P(x_3|x_2)P(x_4|x_2)P(x_5|x_3,x_2) P(x)=P(x1​)P(x2​∣x1​)P(x3​∣x2​)P(x4​∣x2​)P(x5​∣x3​,x2​)

1. 无向图模型

   又称马尔可夫随机场（Markov Random Field，MRF）模型。

   图中所有边均无向。

   无向图模型的联合分布不能通过条件概率计算。

   首先，定义：

   团C：图中节点的一个子集，且该自己中的点是全链接的。

   最大团：如果子团无法通过增加一个节点变为更大的团，则该子团就被称为最大团。

   团势能 ϕ c \phi_c ϕc​：衡量团中变量的每一种可能的联合状态所对应的密切程度（非负）。

   无向图模型的联合概率分布定义为归一化的最大团团势能之积：

   P ( x ) = 1 Z ∏ c ϕ c ( x ) P(x)=\frac{1}{Z}\prod_c\phi_c(x) P(x)=Z1​c∏​ϕc​(x)

   Z = ∑ x ∏ c ϕ c ( x ) Z=\sum_x\prod_c\phi_c(x) Z=x∑​c∏​ϕc​(x)

   Z为归一化函数。

上图包含的最大团：（x1，x2，x3）与（x2，x4，x5）。

其联合分布概率可表示为：

P ( x ) = ∏ ( x 1 , x 2 , x 3 ) ∏ ( x 2 , x 4 , x 5 ) Z P(x)=\frac{\prod_{(x_1,x_2,x_3)}\prod_{(x_2,x_4,x_5)}}{Z} P(x)=Z∏(x1​,x2​,x3​)​∏(x2​,x4​,x5​)​​

通常而言，无向图模型联合概率求解的最大难点在于归一化函数的计算。

隐马尔可夫模型

Hidden Markov Model，HMM。一种生成式有向图模型。

隐藏状态，即BIOES标注序列。

观测，即输入的句子序列。

马尔可夫一词，源于马尔可夫随机过程：若随机变量X在t时刻的状态只与前一时刻t-1的状态有关，则称该随机变量的变化过程为马尔可夫随机过程。

HMM的两个假设：

1. 观测独立性假设：任意时刻的观测只依赖于该时刻的状态，与其他无关。

2. 一阶马尔可夫假设：任意时刻的状态只依赖于前一时刻的状态，与其他时刻的状态无关。

   生成式模型的本质是先学习联合概率分布P(X,Y)，再推断P(Y|X)，所以HMM的联合概率分布：

   P ( X , Y ) = P ( y 0 ) ∏ t = 1 n P ( y t ∣ y t − 1 ) P ( x t ∣ y t ) P(X,Y)=P(y_0)\prod_{t=1}^{n}P(y_t|y_{t-1})P(x_t|y_t) P(X,Y)=P(y0​)t=1∏n​P(yt​∣yt−1​)P(xt​∣yt​)

   P ( y 0 ) P(y_0) P(y0​)为初始概率矩阵， P ( y t ∣ y t − 1 ) P(y_t|y_{t-1}) P(yt​∣yt−1​)为转移矩阵， P ( x t ∣ y t ) P(x_t|y_t) P(xt​∣yt​)为观测矩阵。

   序列标注任务中，首先可根据训练集的输入序列和标注数据，通过极大似然估计，求这三个矩阵。

• 设由t-1时刻状态i转移到t时刻状态j的频数为A_ij，则状态转移概率的估计为： a i j = A i j ∑ j A i j a_{ij}=\frac{A_{ij}}{\sum_jA_{ij}} aij​=∑j​Aij​Aij​​
• 设状态为j，观测为k的频数为B_jk，则观测概率的估计为： b j k = B j k ∑ k = 1 B j k b_{jk}=\frac{B_{jk}}{\sum_{k=1}B_{jk}} bjk​=∑k=1​Bjk​Bjk​​

• 初始概率的估计为初始状态的频率。

  由Viterbi算法进一步解码求出 a r g m a x y P ( y ∣ x ) argmax_yP(y|x) argmaxy​P(y∣x)。

  Viterbi算法的本质：对于给定观测序列，寻找概率最大的隐藏状态序列，该问题可视为在有向无环图中寻找一条最大路径。

上图中，Viterbi算法即寻找S->T最大路径。

通常采用动态规划的思想求解最大路径问题，即遍历t-1时刻状态k转移到t时刻状态j的概率，并取最大值。

转移方程： D t , j = m a x ( D t , j , D t − 1 , k + Θ k j ) D_{t,j}=max(D_{t,j},D_{t-1,k}+\Theta_{kj}) Dt,j​=max(Dt,j​,Dt−1,k​+Θkj​)。

Θ k j \Theta_{kj} Θkj​为状态k转移到状态j的概率。

HMM计算方便快捷，常用于分词任务，如Jieba分词。

受一阶马尔可夫假设限制，HMM表达能力有限。

为此使用MEMM。

最大熵马尔可夫模型

Maximum Entropy Markov Models，MEMM。

一种判别式有向图模型。

判别式模型的本质是学习条件概率分布P(Y|X)，因此可将MEMM的条件概率分布写成：

P ( Y ∣ X ) = ∏ t P ( y t ∣ y t − 1 , x t ) P(Y|X)=\prod_tP(y_t|y_{t-1},x_t) P(Y∣X)=t∏​P(yt​∣yt−1​,xt​)

其中， P ( y t ∣ y t − 1 , x t ) P(y_t|y_{t-1},x_t) P(yt​∣yt−1​,xt​)采用最大熵模型直接建模：

P ( y t ∣ y t − 1 , x t ) = 1 Z e ∑ λ f ( x , y ) P(y_t|y_{t-1},x_t)=\frac{1}{Z}e^{\sum\lambda f(x,y)} P(yt​∣yt−1​,xt​)=Z1​e∑λf(x,y)

其中，Z为归一化函数；f(x,y)为人工定义的任意特征函数，lambda为该特征函数的权重，是待学习的参数。

可以先通过极大似然估计进行学习。

然后通过Viterbi算法进一步解码。

然而MEMM存在**标注偏置（Labeling Bias）**的问题。

由于归一化函数在累乘内部，是一种局部归一化。因此每次状态转换，都会倾向于选择拥有更少转移的状态。

为此使用CRF。

条件随机场模型

Conditional Random Field，CRF。

一种判别式无向图模型。

线性链式条件随机场模型的结构如图所示：

判别式模型的本质是学习条件概率分布P(Y|X)，因此根据无向图模型分布的定义，CRF条件概率分布为：

P ( Y ∣ X ) = 1 Z ∏ c ϕ c ( y c ∣ x ) P(Y|X)=\frac{1}{Z}\prod_c\phi_c(y_c|x) P(Y∣X)=Z1​c∏​ϕc​(yc​∣x)

ϕ ( y c ∣ x ) = e ∑ k λ k f k ( y t , y t − 1 , x t ) + μ k s k ( y t , x t ) \phi(y_c|x)=e^{\sum_k\lambda_kf_k(y_t,y_{t-1},x_t)+\mu_ks_k(y_t,x_t)} ϕ(yc​∣x)=e∑k​λk​fk​(yt​,yt−1​,xt​)+μk​sk​(yt​,xt​)

Z = ∑ y ∏ c ϕ c ( y c ∣ x ) Z=\sum_y\prod_c\phi_c(y_c|x) Z=y∑​c∏​ϕc​(yc​∣x)

其中， ϕ c ( y c ∣ x ) \phi_c(y_c|x) ϕc​(yc​∣x)为线性链式条件随机场中的团势函数（最大团为{y_t,x_t}）；Z为归一化函数；转移特征f_k和状态特征s_k为人工定义的特征函数；lambda与mu为权重，是待学习的参数。

与MEMM相同，先通过极大似然估计学习模型参数，然后通过Viterbi算法进一步解码。

线性链式CRF的Z是全局归一化函数，因此避免了标注偏置问题。

常用工具：CRF++。