问题定义

有一个训练集和,这个集合将每个句子(s)的词(w)标注了词性(z),根据这些数据集学习一个词性标注模型,给出一个新句子,能够将句子里的词标注出词性

image

模型定义

我们利用noisy channel model , bayes方法定义问题, 我们的目标是学习到模型
$\hat{Z} = argmax P(Z|S)$
s表示句子,z表示标注序列.
我们可根据bayes公式化简为

那么,我们可以通过训练集合学习到 $A,\pi,B$ , 再根据维特比算法学习隐式的标注序列.

模型的求解

image.png

$A$ : 是词性i下出现对应单词i的条件概率矩阵
$B$ :状态转移矩阵, 词性i-1下出现词性i的概率
$\pi$ :是每个词性的出现的概率向量

那么求解方式就是利用维特比算法流程, 公式计算的例子:

image.png

注意上式中的 $A,B,\pi$ 的计算方法, 图中的矩阵是 $B$ 是伟特比计算最优路径的基础矩阵

动态规划递推式

B矩阵

整体的步骤为:

根据bayes推到的目标函数,找到递推式子;
按照时序T(词序)填充B矩阵每个链路的值,
同时计算到达T的T-1的最优路径, 并记录下是从T-1中哪个词性(Ni)到达的T
根据记录的路径得到最优解.

def viterbi(x, pi, A, B):
    """
    x: user input string/sentence: x: "I like playing soccer"
    pi: initial probability of tags
    A: 给定tag, 每个单词出现的概率
    B: tag之间的转移概率
    """
    x = [word2id[word] for word in x.split(" ")]  # x: [4521, 412, 542 ..]
    T = len(x)
    
    dp = np.zeros((T,N))  # dp[i][j]: w1...wi, 假设wi的tag是第j个tag
    ptr = np.array([[0 for x in range(N)] for y in range(T)] ) # T*N
    # TODO: ptr = np.zeros((T,N), dtype=int)
    
    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): # 每个单词
        for j in range(N):  # 每个词性
            # TODO: 以下几行代码可以写成一行（vectorize的操作， 会使得效率变高）
            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
                    ptr[i][j] = k
    
    # decoding: 把最好的tag sequence 打印出来
    best_seq = [0]*T  # best_seq = [1,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-1,... 1, 0
        best_seq[i] = ptr[i+1][best_seq[i+1]]
        
    # 到目前为止, best_seq存放了对应于x的 词性序列
    for i in range(len(best_seq)):
        print (id2tag[best_seq[i]])

那么伟特比算法与贪心算法的区别?