MENU

基于Noisy Channel Model和Viterbi算法的词性标注问题

February 25, 2020 • Read: 6790 • 数据挖掘与机器学习阅读设置

给定一个英文语料库,里面有很多句子,已经做好了分词,/前面的是词,后面的表示该词的词性并且每句话由句号分隔,如下图所示

对于一个句子S,句子中每个词语$w_i$标注了对应的词性$z_i$。现在的问题是,再给定一个句子S‘,生成每个词$w'_i$的词性$z'_i$

也就是要求使得概率$P(Z|S)$最大的$Z$,由贝叶斯定理可得

$$ \begin{aligned} P(Z|S)&=\frac{P(S|Z)P(Z)}{P(S)}\\ &\propto P(S|Z)·P(Z)\\ &=P(w_1,w_2,...,w_N|z_1,z_2,...,z_N)·P(z_1,z_2,...,z_N)\\ &=\prod_{i=1}^{N}P(w_i|z_i)·P(z_1)P(z_2|z_1)···P(z_N|z_{N-1})\\ &=\prod_{i=1}^{N}P(w_i|z_i)·P(z_1)\prod_{j=2}^NP(z_j|z_{j-1}) \end{aligned} $$

其中,倒数两行的公式推导过程中,使用了如下两个假设:

  1. HMM假设,即$w_i$仅与$z_i$相关,与其它所有单词或词性相互独立。因此$P(w_1,...,w_N|z_1,...,z_N)$可化简为$\prod_{i=1}^{N}P(w_i|z_i)$
  2. 假设Language Model为bigram。因此$P(z_1,...,z_N)$可写成$P(z_1)P(z_2|z_1)···P(z_N|z_{N-1})$,即$P(z_1)\prod_{j=2}^NP(z_j|z_{j-1})$

由于整个式子存在大量的概率连乘,最终可能导致浮点数下溢,为了避免这种情况,我们可以采用取对数的方法,将乘变加,基于上述思想,式子结果最终转化为

$$ \begin{aligned} P(Z|S)&=\log(\prod_{i=1}^{N}P(w_i|z_i)·P(z_1)\prod_{j=2}^NP(z_j|z_{j-1})\\ &=\sum_{i=1}^N\log(P(w_i|z_i))+\log P(z_1)+\sum_{j=2}^N\log P(z_j|z_{j-1}) \end{aligned} $$

确定参数

最终的概率函数中包含三个可变参数,下面分别解释其含义

第一个参数:$A=P(w_i|z_i)$

参数$A$表示,在给定词性$z_i$的情况下,其对应的单词是$w_i$的条件概率,即所有被标记为词性$z_i$的单词中,单词$w_i$的占比

$$ P(w_i|z_i)=\frac{词性为z_i的w_i的数量}{词性为z_i的单词总数} $$

举例来说,假设现在先给定词性NN(名词),其中对应单词是apple的概率肯定要高于eat,即$P(\text{apple}\mid \text{NN})>P(\text{eat}\mid \text{NN})$

为了后面计算方便,我们把参数$A$的取值空间存放在一个N行M列的矩阵中,其中N为语料库中不同词性的数量,M为语料库中不同单词的数量。矩阵的每一行表示一个词性,每一列表示一个单词,矩阵元素$a_{ij}$表示在所有词性为$i$的单词中,单词$j$的占比(即条件概率),由此可知,同一行中所有所有概率之和为1,即$\sum_{j=1}^Ma_{ij}=1$

计算矩阵A很简单,首先定义一个大小为$N\times M$的全0矩阵,然后遍历语料库中的每一行单词/词性,将矩阵对应中对应的"当前遍历到的词性"行和"当前遍历到的单词"列位置的数值加1

最后进行归一化,因为到目前为止矩阵中存的是count,而我们需要的probability,所以用每个元素除以所在行元素之和即可。最终得到的参数$A$矩阵的一般形式如下图所示

第二个参数:$\pi=P(z_i)$

参数$\pi$表示句首词性是$z_i$的概率,即计算所有在句首的词性中$z_i$的占比

$$ P(z_i)=\frac{句首词性是z_i的数量}{句首词性总数量} $$

举例来说,一般句首是NN(名词)的概率要高于VB(动词),即$P(\text{NN})>P(\text{VB})$

参数$\pi$的取值范围可以保存在一个长度为$N$的向量中,$N$为语料库中不同词性的数量。可以推知,此向量的元素之和为1,即$\sum_{i=1}^NP(i)=1$

首先用0初始化向量$\pi$,长度为$N$。然后遍历语料库中的每一行单词/词性,判断当前单词是否在句首,判断的依据是看前一个单词是否是句号、感叹号、问号等终止性标点符号。如果是句首,则取出当前词性,并将向量中对应"当前遍历到的词性"位置的数值加1

最后进行归一化,用每个元素除以向量所有元素之和,即得到占比(概率)

第三个参数:$B=P(z_i|z_{i-1})$

参数$B$表示给定前驱词性为$z_{i-1}$,当前词性为$z_i$的条件概率,即计算在前驱词性为$z_{i-1}$的(前驱词性,当前词性)组合对中,当前词性为$z_i$的组合对的占比

$$ P(z_i|z_{i-1})=\frac{当前词性为z_{i-1}且前驱词性为z_i的\text{bigram}数量}{前驱词性为z_i的\text{bigram}总数} $$

举例来说,对于给定的前驱词性VB(动词),当前词性为NN(名词)的概率要高于VB(动词),即$P(\text{NN}|\text{VB})>P(\text{VB}|\text{VB})$

参数$B$是一个$N\times N$的矩阵,$N$为语料库中不同词性的数量。矩阵的行表示前驱词性,列表示当前词性,矩阵元素$b_{ij}$表示前驱词性为$i$时,当前词性为$j$的条件概率,由此可知同一行中所有元素之和为1,即$\sum_{j=1}^Nb_{ij}=1$

矩阵$B$的计算很简单,首先定义一个大小为$N\times N$的全0方阵。然后遍历语料库,统计词性序列的bigram,将方阵中对应的"前驱词性"行和"当前词性"列位置的数值加1

最后进行归一化,用每个元素除以所在行元素之和,即得到所在行占比(概率)

tag2id, id2tag = {}, {} # tag2id: {"VB":0,...}, id2tag: {0:"VB",...}
word2id, id2word = {}, {}

for line in open('traindata.txt'):
    items = line.split('/')
    word, tag = items[0], items[1].rstrip() # 去掉换行符
    
    if word not in word2id:
        word2id[word] = len(word2id)
        id2word[len(id2word)] = word
    if tag not in tag2id:
        tag2id[tag] = len(tag2id)
        id2tag[len(id2tag)] = tag

N = len(tag2id) # number of tags
M = len(word2id) # number of words
print(N, M)

# define pi, A, B
import numpy as np

pi = np.zeros(N) # pi[i] 表示tag i出现在句子开头的概率, vector
A = np.zeros((N, M)) # A[i][j] 表示给定tag i, 出现word j的概率, matrix
B = np.zeros((N, N)) # B[i][j] 表示前一个是tag i, 后一个是tag j的概率, matrix

pre_tag = -1 # 记录前一个tag的id
for line in open('traindata.txt'):
    items = line.split('/')
    wordid, tagid = word2id[items[0]], tag2id[items[1].rstrip()]
    if pre_tag == -1: # 这意味着是句子的开始
        pi[tagid] += 1
        A[tagid][wordid] += 1
        pre_tag = tagid
    else: # 不是句子开头
        A[tagid][wordid] += 1
        B[pre_tag][tagid] += 1
        
    if items[0] == '.':
        pre_tag = -1
    else:
        pre_tag = tagid

        
# normalize
pi /= sum(pi) # probability
for i in range(N):
    A[i] /= sum(A[i])
    B[i] /= sum(B[i])

计算最优解

通过前面的分析,我们已经确定了三个参数及其取值空间,接下来可以用暴力枚举的方法测试出使得目标函数最大的参数取值,但时间复杂度太高,不建议采用

通过分析,我们发现这是一个最优化问题,而且问题的求解可以分为$T$个步骤($T$为测试集的文本长度),每个步骤求解方式相同,符合动态规划算法的应用场景

$$ score=\sum_{i=1}^T\log P(w_i|z_i)+\log P(z_1)+\sum_{j=2}^T\log P(z_j|z_{j-1}) $$

我们的目标是对于给定的文本$S=w_1w_2...w_T$,给这$T$个单词分别赋予一个词性(有$N$个可选词性),使得score的值最大。score的计算过程描述如下

图中黑点给出了一个示例的标记方案(如同一条路径):

  • $w_1$被标记为$pos_2$
  • $w_2$被标记为$pos_1$
  • $w_3$被标记为$pos_3$
  • ...
  • $w_T$被标记为$pos_T$

该路径的score值为

$$ \begin{aligned} score &= \log P(w_1|pos_2)+\log P(pos_2)\\ &+\log P(w_2|pos_1)+\log P(pos_1|pos_2)\\ &+\log P(w_3|pos_3)+\log P(pos_3|pos_1)\\ &+...\\ &+\log P(w_T|pos_1)+\log P(pos_1|pos_3) \end{aligned} $$

从上式可以看出,score的求解过程分为$T$个步骤,每个步骤有$N$种选择。因为我们可以定义一个$T\times N$的二维数组DP,为了描述的方便,我们假设数组的下标从0开始,其中元素DP[i][j]表示从第一个单词开始,当计算到第$i$个单词(第$i$步)且将词性标记为$j$时的最优路径(最大概率)

状态转移方程为

$$ \begin{aligned} DP[i][j]=\max(&\\ &dp[i-1][0]+\log B[0][j]+\log A[j][w_i在词典中的下标],\\ &dp[i-1][1]+\log B[1][j]+\log A[j][w_i在词典中的下标],\\ &dp[i-1][2]+\log B[2][j]+\log A[j][w_i在词典中的下标],\\ &...\\ &dp[i-1][N-1]+\log B[N-1][j]+\log A[j][w_i在词典中的下标],\\ ) \end{aligned} $$

最终答案(最大的概率值),就是max(DP[T-1][0],DP[T-1][1],...,DP[T-1][N-1])。但是光有概率不够,我们还需要记录,这个概率是通过怎样的路径过来的,这个路径就是每个词的词性。因此我们还需要另外建立一个$T\times N$的二维数组,用于记录最优的词性选择路径

viterbi算法部分的代码如下

def log(v):
    if v == 0:
        return np.log(v + 0.0000001)
    return np.log(v)

def viterbi(x, pi, A, B):
    """
    x: user input string/sentence
    pi: initial probability of tags
    A: 给定tag,每个单词出现的概率
    B: tag之间的转移概率
    """
    x = [word2id[word] for word in x.split(" ")]
    T = len(x)
    dp = np.zeros((T, N))
    path = np.array([[0 for x in range(N)] for y in range(T)]) # T*N
    for j in range(N): # basecase for dp algorithm
        dp[0][j] = log(pi[j]) + log(A[j][x[0]])
    
    for i in range(1, T): # every words
        for j in range(N): # every tags
            dp[i][j] = -9999999
            for k in range(N): # 从每个k可以到达j
                score = dp[i-1][k] + log(B[k][j]) + log(A[j][x[i]])
                if score > dp[i][j]:
                    dp[i][j] = score
                    path[i][j] = k
    # print best tag sequence
    best_seq = [0] * T # best_seq = [1, 5, 0, 3, 55, ...]
    # step1: 找出最后一个单词的词性
    best_seq[T-1] = np.argmax(dp[T-1]) # 求出最大值所在下标
    
    # step2: 通过从后往前的循环以此求出每个单词的词性
    for i in range(T-2, -1, -1):
        best_seq[i] = path[i + 1][best_seq[i + 1]]
        
    # step3: print
    for i in range(len(best_seq)):
        print(id2tag[best_seq[i]])

# Test
x = "Social Security number , passport number and details about the services provided for the payment"
viterbi(x, pi, A, B)
Last Modified: August 2, 2021
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

4 Comments
  1. brill brill

    你是学院还是老师阿? 我觉得你的博客写的很好

    1. mathor mathor

      @brill我是学生

    2. brill brill

      @mathor我也在入门nlp,能加个好友讨论么?

    3. mathor mathor

      @brill可以,我qq739616037