基于Noisy Channel Model和Viterbi算法的词性标注问题
- 2020 年 3 月 4 日
- 筆記
给定一个英文语料库，里面有很多句子，已经做好了分词，/前面的是词，后面的表示该词的词性并且每句话由句号分隔，如下图所示
对于一个句子S，句子中每个词语(w_i)标注了对应的词性(z_i)。现在的问题是，再给定一个句子S‘，生成每个词(w'_i)的词性(z'_i)
也就是要求使得概率(P(Z|S))最大的(Z)，由贝叶斯定理可得
[ begin{align*} 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{align*} ]
其中，倒数两行的公式推导过程中，使用了如下两个假设：
- HMM假设，即(w_i)仅与(z_i)相关，与其它所有单词或词性相互独立。因此(P(w_1,…,w_N|z_1,…,z_N))可化简为(prod_{i=1}^{N}P(w_i|z_i))
- 假设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{align*} 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}^Nlog(P(w_i|z_i))+logP(z_1)+sum_{j=2}^NlogP(z_j|z_{j-1}) end{align*} ]
确定参数
最终的概率函数中包含三个可变参数，下面分别解释其含义
第一个参数：(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(apple|NN)>P(eat|NN))
为了后面计算方便，我们把参数(A)的取值空间存放在一个N行M列的矩阵中，其中N为语料库中不同词性的数量，M为语料库中不同单词的数量。矩阵的每一行表示一个词性，每一列表示一个单词，矩阵元素(a_{ij})表示在所有词性为(i)的单词中，单词(j)的占比（即条件概率），由此可知，同一行中所有所有概率之和为1，即(sum_{j=1}^Ma_{ij}=1)
计算矩阵A很简单，首先定义一个大小为(Ntimes M)的全0矩阵，然后遍历语料库中的每一行单词/词性，将矩阵对应中对应的"当前遍历到的词性"行和"当前遍历到的单词"列位置的数值加1
最后进行归一化，因为到目前为止矩阵中存的是count，而我们需要的probability，所以用每个元素除以所在行元素之和即可
最终得到的参数(A)矩阵的一般形式如下图所示
第二个参数：(pi=P(z_i))
参数(pi)表示句首词性是(z_i)的概率，即计算所有在句首的词性中(z_i)的占比
[ P(z_i)=frac{句首词性是z_i的数量}{句首词性总数量} ]
举例来说，一般句首是NN(名词)的概率要高于VB(动词)，即(P(NN)>P(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的bigram数量}{前驱词性为z_i的bigram总数} ]
举例来说，对于给定的前驱词性VB(动词)，当前词性为NN(名词)的概率要高于VB(动词)，即(P(NN|VB)>P(VB|VB))
参数(B)是一个(Ntimes N)的矩阵，(N)为语料库中不同词性的数量。矩阵的行表示前驱词性，列表示当前词性，矩阵元素(b_{ij})表示前驱词性为(i)时，当前词性为(j)的条件概率，由此可知同一行中所有元素之和为1，即(sum_{j=1}^Nb_{ij}=1)
矩阵(B)的计算很简单，首先定义一个大小为(Ntimes 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}^TlogP(w_i|z_i)+logP(z_1)+sum_{j=2}^TlogP(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{align*} score &= logP(w_1|pos_2)+logP(pos_2)\ &+logP(w_2|pos_1)+logP(pos_1|pos_2)\ &+logP(w_3|pos_3)+logP(pos_3|pos_1)\ &+…\ &+logP(w_T|pos_1)+logP(pos_1|pos_3) end{align*} ]
从上式可以看出，score的求解过程分为(T)个步骤，每个步骤有(N)种选择。因为我们可以定义一个(Ttimes N)的二维数组DP，为了描述的方便，我们假设数组的下标从0开始，其中元素DP[i][j]表示从第一个单词开始，当计算到第(i)个单词（第(i)步）且将词性标记为(j)时的最优路径（最大概率）
状态转移方程为
[ begin{align*} DP[i][j]=max(&\ &dp[i-1][0]+logB[0][j]+logA[j][w_i在词典中的下标],\ &dp[i-1][1]+logB[1][j]+logA[j][w_i在词典中的下标],\ &dp[i-1][2]+logB[2][j]+logA[j][w_i在词典中的下标],\ &…\ &dp[i-1][N-1]+logB[N-1][j]+logA[j][w_i在词典中的下标],\ ) end{align*} ]
最终答案（最大的概率值），就是max(DP[T-1][0],DP[T-1][1],...,DP[T-1][N-1])。但是光有概率不够，我们还需要记录，这个概率是通过怎样的路径过来的，这个路径就是每个词的词性。因此我们还需要另外建立一个(Ttimes 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)
