词性标注

pos Tagging

S={今天,学习,NLP}通过已知单词,的词性,当给出一个新的句子,求解最后一个单词的词性是什么?

对上面的公式进行转化,求最优解问题

实现步骤:

• step1:A,B,pi
• step2:viterbi

tag2id,id2tag={},{}  # map tag to id:{"VB":0,"NNp":1,...}  id2tag:{0,"VB",..}
word2id,id2word = {},{} # ,aps word to id 

for line in open('traindata.txt'):
    items = line.split('/')
    word,tag =items[0],items[1].strip()  # 抽取每一行单词和词性
    
    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
        
M = len(word2id)  # M代表词典的大小
N = len(tag2id)  # N词性的中种类个数 

import numpy as np

pi = np.zeros(N) # 每个词出现在句子中第一个位置的概率
A = np.zeros((N,M)) # A[i][j]:给定tag i,出现单词j的概率
B = np.zeros((N,N))  # B[i][j]:之前状态变量i,之后转换成N;

prev_tag = ""  # 类似状态
for line in open('traindata.txt'):
    items = line.split("/")
    wordId,tagId=word2id[items[0]],tag2id[items[1].rstrip()]
    if prev_tag =="": # 这意味着句子的开始
        pi[tagId]+=1
        A[tagId][wordId]+=1
    else: # 如果不是句子的开头
        A[tagId][wordId]+=1
        B[tag2id[prev_tag]][tagId]+=1
        
    if items[0]=='.': # 
        prev_tag=""
    else:
        prev_tag=items[1].strip()
    
pi=pi/sum(pi)

for i in range(N):
    A[i]/=sum(A[i])
    B[i]/=sum(B[i])

对于上面的公式
w_i:单词;Z_i:词性;
可以使用二维矩阵进行描述该情景

A矩阵(N x M)

M: of words
N: of tags

pi

B(N x N)

对于常规操作,这个矩阵对应的素偶有路径,时间复杂度是O(M*N*N)
为了降低时间复杂度,这里才有了viterbi算法的出现

按照句子划分traindata.txt

给定单词,词性矩阵,对于每一个单词来说

• 对于第一个单词:P(词性)+P(单词1|词性)
• 对于第一个单词:P(当前词性|上一个词性)+P(单词i|当前词性)

观察上面的推到发现和之前推到的公式是一样的

因此可以使用动态规划的方法,来进行求解,生成原矩阵大小的新矩阵d[i][j], 那么则有下面的公式

相当于从最后一列中找到最大的,然后在到前一个着最大的

维特比算法得代码实现

维特比算法
给定w_1,w_2,…,求出Z_1,Z_2,….

z=argamx\sum_{i=1}^{T}logP(w_i|Z_i)+log(P(Z_1))+\sum_{t=2}^{T}logP(Z_t|Z_t)

def viterbi(x,pi,A,B):
    """
    x:user input string/sentence  x""I like palying soccer
    pi:initeial probality of tags
    A:给定tag,每个单词出现的概率
    B:tag之间的转移概率
    """
    x=[word2id[word] for word in x.split(" ")]   # x:[2345,7543,2345,...]
    T =len(x)
    
    dp=np.zeros((T,N))   # dp[i][j]:w1,w2,w3,w4...,假设wi的tag是第i个tag
    
    # 记录路径
    ptr=np.array([[0 for x in range(N)] for y in range(T)]) # T*N
    # ptr=np.zeros((T,N),dtype=np.int32)
    
    #     第一列
    for j in range(N): # basecase for DP算法
        dp[0][j] = log(pi[j])+log(A[j][x[0]])
        
    for i in range(1,T): # 每个单词
        # TODO: 以下几行代码可以写成一行(vectorize的操作,会使得效率变高)
        for j in range(N): # 每个词性
            dp[i][j]=-99999
            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
                    ptr[i][j]=k
    # decoding:把最好的结果打印出来
    best_seq=[0]*T  # best_seq=[1,3,5,2,23,4,...]
    # step1: 找出对应最后的一个单词的词性
    best_seq[T-1] = np.argmax(dp[T-1])
    
    # step2:通过从后面到前循环来依次求出每个单词的词性
    for i in range(T-2,-1,-1): # T-2,T-3,...1,0
        best_seq[i] = ptr[i+1][best_seq[i+1]]  # 注意,当前的ptr是存在下一个节点上的
        
    # 到目前为止,best_seq存放了对英语x的 词性序列
    for i in range(len(best_seq)):
        print(id2tag[best_seq[i]])

测试用例

x="I like English everyday"
viterbi(x,pi,A,B)