Tagging Problems and Hidden Markov Models

概述

对于一个句子,我们要做的是给每一个单词打上词性标记,比如句子the dog saw a cat对应的tag sequence是D N V D N,这个句子的长度是5,对应的输入$x_1=the,x_2=dog,x_3=saw,x_4=the,x_5=cat$,用$y_1y_2…y_n$来表示tagging model的output,对应上面的有$y_1=D,y_2=N,y_3=V,…$。匹配句子$x_1…x_n$的tag sequence $y_1…y_n$的问题叫做 sequence labeling problem 或者是 tagging problem。

POS Tagging and Named-Entity Recognition

前面讲到的就是POS Tagging,其有两大挑战,第一个是tagging的歧义问题,因为一个单词有可能是动词又有可能是名词;第二个是词库中的单词有限,导致训练例子中的单词可能在词库中没有出现,然后是Named-Entity Recognition,notes中提到的实体有PERSON,LOCATION,COMPANY。但是对这一块的讲解非常少,所以这里就不提了[后期如果有用会补上吧。]

Generative Models

这里主要是讲解隐马尔可夫模型应用在tagging问题上,这里以$x^{(i)}$作为句子,$y^{(i)}$作为对应的标签,我们的目的是在语料库集合$Y,y \in Y$中找到最符合句子$x^{(i)}$的标签$y^{(i)}$,即如下:
$$
f(x)=arg , \max_{y\in Y},,p(y|x)
$$
那么如何对于给定的$x^{(i)}$,在Y中找到最优的y呢,即如何求解$p(y|x)$呢,这里我们将上式转换一下,用贝叶斯公式求解:
$$
p(y|x)=\frac{p(y)p(x|y)}{p(x)}
$$
由于对于x而言,求解全部y的概率,因此p(x)可以看成常数,也就是求下面的最大值对应的y:
$$
f(x)=arg ,, \max_y p(y)p(x|y)
$$

Generative Tagging Models

对于单词集$V$,标记集$K$,定义$S$为sequence/tag-sequence对$<x_1…x_n,y_1…y_n>$,对于$x_i \in V,y_i \in K$,有如下要求:
$$
for,,any,, <x_1…x_n,y_1…y_n> \in S\
p(x_1…x_n,y_1…y_n) >=0\
\sum_{<x_1…x_n,y_1…y_n> \in S} p(x_1…x_n,y_1…y_n)=1
$$

那么对于给定的一个生成标记模型,从序列$x_1…x_n$中标记出序列$y_1…y_n$被定义如下:
$$
f(x_1…x_n)=arg,, \max_{y_1…y_n},,p(x_1…x_n,y_1…y_n)
$$

Trigram Hidden Markov Models

这里是Trigram,也就是说序列中$y_i$只与$y_{i-1}$和$y_{i-2}$有关。

给出下面两个参数 :

参数$q(s|u,v)$:对于任意的trigram$(u,v,s)$,其中$s \in K \cup {STOP}, u,v \in K \cup {*}$,其概率$q(s|u,v)$可由在看到s在bigram $(u,v)$后的概率。

参数$e(x|s)$:对于任意$x \in V, s \in K​$这个值可以表示为看见观测值x配对s的概率。

那么之前概率$p(x_1…x_n,y_1…y_{n+1})$可以表示如下:
$$
p(x_1…x_n,y_1…y_{n+1})=p(y_1…y_{n+1})p(x_1…x_n|y_1…y_{n+1})\
=\prod_{i=1}^{n+1} q(y_i|y_{i-2},y_{i-1}) \prod_{i=1}^{n} e(x_i|y_i)
$$

这里有$y_{n+1}=STOP,y_0=y_{-1}=*$。
那么为什么上面这个公式成立呢,这里是有一些假设的,这里使用随机变量序列$X_1…X_n$和$Y_1…Y_n$,其中n为序列的长度,假设$X_i$可以取集合$V$中的任意的值,$Y_i$可以取集合$K$中任意一个标记,那么上式可以被定义为:
$$
P(X_1=x_1…X_n=x_n,Y_1=y_1…Y_{n+1}=y_{n+1})\
=\prod_{i=1}^{n+1}P(Y_i=y_i|Y_{i-2}=y_{i-2},Y_{i-1}=y_{i-1})\prod_{i=1}^{n}P(X_i=x_i|Y_i=y_i)
$$
这里第一个连乘是没有问题的,但是第二个连乘是怎么得到的呢,下面一步步分析
这里先讲一下概率模型$P(X_1=x_1…X_n=x_n)$的求解,如下:
$$
P(X_1=x_1…X_n=x_n)
=P(X_n=x_n|X_1=x_1…X_{n-1}=x_{n-1})P(X_1=x_1…X_{n-1}=x_{n-1})
$$
其中$P(X_1=x_1…X_{n-1}=x_{n-1})$

$$
=P(X_{n-1}=x_{n-1}|X_1=x_1…X_{n-2}=x_{n-2})P(X_1=x_1…X_{n-2}=x_{n-2})

P(X_1=x_1, X_2=x_2)=P(X_2=x_2|X_1=x_1)P(X_1=x_1)
$$
这样上面可以表示如下:
$$
P(X_1=x_1…X_n=x_n)=\prod_{i=1}^{n}P(X_i=x_i|X_1=x_1…X_{i-1}=x_{i-1})
$$
那么下面这个公式就知道怎么变来的了吧
$$
P(X_1=x_1…X_n=x_n|Y_1=y_1…Y_{n+1}=y_{n+1})\
=\prod_{i=1}^{n}P(X_i=x_i|X_1=x_1…X_{i-1}=x_{i-1},Y_1=y_1…Y_{n+1}=y_{n+1})
$$
这里做了一个假设,变量$X_i$独立于之前的观测变量$X_1…X_{i-1}$和状态变量$Y_1…Y_{i-1},Y_{i+1}…Y_{n+1}$ ,当被给出变量$Y_i$时。那么上面的式子就变为:
$$
\prod_{i=1}^{n}P(X_i=x_i|X_1=x_1…X_{i-1}=x_{i-1},Y_1=y_1…Y_{n+1}=y_{n+1})\
=\prod_{i=1}^{n}P(X_i=x_i|Y_i=y_i)
$$

Estimating the Parameters of a Trigram HMM

这里定义一下$c(s \to x)$为在语料库中标签s和单词x匹配的次数,那么上述的两个参数在语料库中的最大似然估计如下:
$$
q(s|u,v)=\frac{c(u,v,s)}{c(u,v)}\
e(x|s)=\frac{c(s \to x)}{c(s)}
$$
同样对于在语料库中$q(s|u,v)$为0的情况,我们用上一章中讲到的解决,对于$e(x|s)$为0的情况,也就是说在语料库中没有出现该单词,这里notes中给出一种解决办法就是使用伪词(pseudo-words)[这块没有细看,后期用到再补]

Decoding with HMMs: the Viterbi Algorithm

那么知道如何求解$q(s|u,v)$和$e(x|s)$,我们又知道
$$
p(x_1…x_n,y_1…y_{n+1})==
\prod_{i=1}^{n+1} q(y_i|y_{i-2},y_{i-1}) \prod_{i=1}^{n} e(x_i|y_i)
$$
而我们的原始问题是发现一组使概率值最大的序列$y_1…y_{n+1}$,即:
$$
arg,, \max_{y_1…y_n},,p(x_1…x_n,y_1…y_n)
$$
这里举个例子,对于输入的句子the dog barks ,假设标记集为$K={D,N,V}$,那么可能的标记序列$y_1y_2y_3y_4$可以是下面任意一种:

1
2
3
4
5
D	D	D	STOP
D D N STOP
D D V STOP
D N D STOP
...

对于$|K|=3$时,有27种可能,如果计算这$3^3=27$种情况中的每一种,找出概率最大的那个序列,显然是不太现实的,我们需要用一种更为简化的方法来解决这个问题。

下面的维特比算法就给出这样一种解决办法,可以将时间复杂度由$O(|K|^n)$缩小到$O(n|K|^3)$,使用的方法是动态规划,就是对一个长度为n的句子分解,给定初始条件,给出通项公式,即求长度为i的子句最大概率下对应的子标记和长度为i-1的子句最大概率下对应的子标记的关系,这样就可以求出长度为n的原句最大概率下对应的标记。

VITERBI ALGORITHM

输入的句子是$x_1…x_n$,对任意的$k\in {1…n}$ ,任意的序列$y_{-1},y_{0},y_{1}…y_{k}$,且$y_i \in K , y_{-1}=y_0=$,定义如下函数:
$$
r(y_{-1},y_0,y_1,…,y_k)=\prod_{i=1}^{k}q(y_i|y_{i-2},y_{i-1})\prod_{i=1}^{k}e(x_i|y_i)
$$
这里举个例子如下:
$$
p(x_1…x_n,y_1…y_{n+1})=r(
,,y1,…,y_n) q(STOP|y_{n-1},y_n)
$$
继续,定义$K_{-1}=K_{0}={*}$和$K_k=K,,for,,k \in {1…n}$,定义$S(k,u,v)$为序列$y_{-1},y_{0},y_1,…,y_{k}$ 的集合,其中$u \in K_{k-1}, v \in K_{k},y_{k-1}=u,y_k=v$,定义:
$$
\pi(k,u,v)= \max_{<y_{-1},y_0,y_1,…,y_k> \in S(k,u,v)} r(y_{-1},y_0,y_1,…,y_k)
$$
给定初始条件:$\pi(0,
,*)=1$

给定通项公式:
$$
\pi(k,u,v)=\max_{w \in K_{k-2}}\big(\pi(k-1,w,u)q(v|w,u)e(x_k|v)\big)
$$
算法如下:

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# -*- coding: utf-8 -*-
# state 存放隐藏序列,sunny 0 rainy 1
# obser 存放观测序列 0 1 2 对应 walk shop clean
# start_p 是初始概率,0元素对应sunny的初始概率 1元素对应rainy的概率
# transition_p 转移概率矩阵 2*2 行为初始状态 列为新状态
# emission_p 发射概率矩阵 2*3 行为隐藏状态 列为可观测状态

# 迭代过程,每次只需要记录第t个时间点 每个节点的最大概率即可,后续计算时直接使用前序节点的最大概率即可
def compute(obser, state, start_p, transition_p, emission_p):
# max_p 记录每个时间点每个状态的最大概率,i行j列,(i,j)记录第i个时间点 j隐藏状态的最大概率
max_p = [[0 for col in range(len(state))] for row in range(len(obser))]
# path 记录max_p 对应概率处的路径 i 行 j列 (i,j)记录第i个时间点 j隐藏状态最大概率的情况下 其前驱状态
path = [[0 for col in range(len(state))] for row in range(len(obser))]
# 初始状态(1状态)
for i in range(len(state)):
# max_p[0][i]表示初始状态第i个隐藏状态的最大概率
# 概率 = start_p[i] * emission_p [state[i]][obser[0]]
max_p[0][i] = start_p[i] * emission_p[state[i]][obser[0]]
path[0][i] = i
# 后续循环状态(2-t状态)
# 此时max_p 中已记录第一个状态的两个隐藏状态概率
for i in range(1, len(obser)): # 循环t-1次,初始已计算
max_item = [0 for i in range(len(state))]
for j in range(len(state)): # 循环隐藏状态数,计算当前状态每个隐藏状态的概率
item = [0 for i in state]
for k in range(len(state)): # 再次循环隐藏状态数,计算选定隐藏状态的前驱状态为各种状态的概率
p = max_p[i - 1][k] * emission_p[state[j]][obser[i]] * transition_p[state[k]][state[j]]
# k即代表前驱状态 k或state[k]均为前驱状态
item[state[k]] = p
# 设置概率记录为最大情况
max_item[state[j]] = max(item)
# 记录最大情况路径(下面语句的作用:当前时刻下第j个状态概率最大时,记录其前驱节点)
# item.index(max(item))寻找item的最大值索引,因item记录各种前驱情况的概率
path[i][state[j]] = item.index(max(item))
# 将单个状态的结果加入总列表max_p
max_p[i] = max_item
#newpath记录最后路径
newpath = []
#判断最后一个时刻哪个状态的概率最大
p=max_p[len(obser)-1].index(max(max_p[len(obser)-1]))
newpath.append(p)
#从最后一个状态开始倒着寻找前驱节点
for i in range(len(obser) - 1, 0, -1):
newpath.append(path[i][p])
p = path[i][p]
newpath.reverse()
return newpath


if __name__ == '__main__':
# 隐状态
hidden_state = ['rainy', 'sunny']
# 观测序列
obsevition = ['walk', 'shop', 'clean']
state_s = [0, 1]
obser = [0, 1, 2]
# 初始状态,测试集中,0.6概率观测序列以sunny开始
start_probability = [0.6, 0.4]
# 转移概率,0.7:sunny下一天sunny的概率
transititon_probability = [[0.7, 0.3], [0.4, 0.6]]
# 发射概率,0.4:sunny在0.4概率下为shop
emission_probability = [[0.1, 0.4, 0.5], [0.6, 0.3, 0.1]]
result = compute(obser, state_s, start_probability, transititon_probability, emission_probability)
for k in range(len(result)):
print(hidden_state[int(result[k])])

   HMMTagging


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×