預測單詞詞性
詞性标注
pos Tagging
S={今天,學習,NLP}
通過已知單詞,的詞性,當給出一個新的句子,求解最後一個單詞的詞性是什麼?
\[\begin{aligned}P(Z|S)
&=P(S|Z)·P(Z) \\
&=P(w_1w_2...w_N|Z_1Z_2...Z_N)P(Z_1Z_2...Z_n)\\
&=\prod_{i=1}^{n}·P(w_i|Z_i)·P(Z_1)·P(Z_2|Z_1)·P(Z_3|Z_2)...P(Z_n|Z_{n-1})
\end{aligned}
\]
對上面的公式進行轉化,求最優解問題
\[\begin{aligned} \hat{Z}
&=argmaxP(Z|S) \\
&=argmax\prod_{i=1}^nP(W_i|Z_i)·P(Z_i)·\prod_{t=2}^nP(Z_t|Z_{t-1}) \\
&=argmaxlog(\prod_{i=1}^nP(W_i|Z_i)·P(Z_i)·\prod_{t=2}^nP(Z_t|Z_{t-1})) \\
&=argmax\prod_{i=1}^nlogP(W_i|Z_i)+logP(Z_i)+log\prod_{t=2}^nP(Z_t|Z_{t-1})
\end{aligned}
\]
實作步驟:
- 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
N x M
M: of words
N: of tags
| 句子 | w_1 | w_2 | ... |
|---|---|---|---|
| 名詞 | | | ... |
| 動詞 | | | ... |
pi
| header 1 | 名詞 | 動詞 | ... |
|---|---|---|---|
| | | ... |
B( N x N
N x N
| 詞性 | n | v | ... |
|---|---|---|---|
| n. | | | ... |
| v. | | | ... |
對于正常操作,這個矩陣對應的素偶有路徑,時間複雜度是
O(M*N*N)
為了降低時間複雜度,這裡才有了
viterbi
算法的出現
按照句子劃分
traindata.txt
給定單詞,詞性矩陣,對于每一個單詞來說
- 對于第一個單詞:P(詞性)+P(單詞1|詞性)
- 對于第一個單詞:P(目前詞性|上一個詞性)+P(單詞i|目前詞性)
\[\begin{aligned}score(n)
& =logP(n)+log(w_1|n) \tag{第個單詞的score} \\
& =logP(v|n)+logP(w_2|v) \\
& =log(adj|v)+logP(w_3|adj)
\end{aligned}
\]
觀察上面的推到發現和之前推到的公式是一樣的
是以可以使用動态規劃的方法,來進行求解,生成原矩陣大小的新矩陣
d[i][j]
, 那麼則有下面的公式
\[\begin{aligned}dp[i][j]=
& dp[i-1][0]+logP(adj|n)+logP(w_i|adj) \\
& +dp[i-1][1]+logP(adj|v)+logP(w_i|adj) \\
& +dp[i-2][1]+logP(adj|adj)+logP(w_i|adj) \\
& +...
\end{aligned}
\]
相當于從最後一列中找到最大的,然後在到前一個着最大的
\[[w_1...w_T]==>dp[T][0],dp[T][1]...dp[T][N]
\]
維特比算法得代碼實作
維特比算法
給定
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)