#### 词性标注
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
```python
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
句子 | w_1|w_2|...
---|---|---|---
名词 | `w_1`单词对应`n.`的概率|`w_2`单词对应`n.`的概率|...
动词 | `w_2`单词对应`v.`的概率|`w_2`单词对应`v.`的概率|...
##### pi
header 1 | 名词|动词|...
---|---|---|---
`w_1`| `w_1`对应`n.`的概率|`w_1`对应`v.`的概率|...
##### B(`N x N`)
词性 | n|v|...
---|---|---|---
n. | `n.`前面是`n.`的概率|`n.`前面是`v.`的概率|...
v. | `n.`前面是`v.`的概率|`v.`前面是`v.`的概率|...
对于常规操作,这个矩阵对应的素偶有路径,时间复杂度是`O(M*N*N)`
为了降低时间复杂度,这里才有了`viterbi`算法的出现
按照句子划分`traindata.txt`
给定单词,词性矩阵,对于每一个单词来说
- 对于第一个单词:P(词性)+P(单词1|词性)
- 对于第一个单词:P(当前词性|上一个词性)+P(单词i|当前词性)
$$
\begin{aligned}score(n)
& =logP(n)+log(w_1|n) \\
& =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`,....
```math
z=argamx\sum_{i=1}^{T}logP(w_i|Z_i)+log(P(Z_1))+\sum_{t=2}^{T}logP(Z_t|Z_t)
```
```python
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]])
```
测试用例
```python
x="I like English everyday"
viterbi(x,pi,A,B)
```
