Tagging Problems and Hidden Markov Models

概述

对于一个句子，我们要做的是给每一个单词打上词性标记，比如句子the dog saw a cat对应的tag sequence是D N V D N，这个句子的长度是5，对应的输入\(x_1=the,x_2=dog,x_3=saw,x_4=the,x_5=cat\)，用\(y_1y_2...y_n\)来表示tagging model的output，对应上面的有\(y_1=D,y_2=N,y_3=V,...\)。匹配句子\(x_1...x_n\)的tag sequence \(y_1...y_n\)的问题叫做 sequence labeling problem 或者是 tagging problem。

POS Tagging and Named-Entity Recognition

前面讲到的就是POS Tagging，其有两大挑战，第一个是tagging的歧义问题，因为一个单词有可能是动词又有可能是名词；第二个是词库中的单词有限，导致训练例子中的单词可能在词库中没有出现，然后是Named-Entity Recognition，notes中提到的实体有PERSON,LOCATION,COMPANY。但是对这一块的讲解非常少，所以这里就不提了[后期如果有用会补上吧。]

Generative Models

这里主要是讲解隐马尔可夫模型应用在tagging问题上，这里以\(x^{(i)}\)作为句子，\(y^{(i)}\)作为对应的标签，我们的目的是在语料库集合\(Y,y \in Y\)中找到最符合句子\(x^{(i)}\)的标签\(y^{(i)}\)，即如下： \[ f(x)=arg \, \max_{y\in Y}\,\,p(y|x) \] 那么如何对于给定的\(x^{(i)}\)，在Y中找到最优的y呢，即如何求解\(p(y|x)\)呢，这里我们将上式转换一下，用贝叶斯公式求解： \[ p(y|x)=\frac{p(y)p(x|y)}{p(x)} \] 由于对于x而言，求解全部y的概率，因此p(x)可以看成常数，也就是求下面的最大值对应的y： \[ f(x)=arg \,\, \max_y p(y)p(x|y) \]

Generative Tagging Models

对于单词集\(V\)，标记集\(K\)，定义\(S\)为sequence/tag-sequence对\(<x_1...x_n,y_1...y_n>\)，对于\(x_i \in V,y_i \in K\)，有如下要求： \[ for\,\,any\,\, <x_1...x_n,y_1...y_n> \in S\\ p(x_1...x_n,y_1...y_n) >=0\\ \sum_{<x_1...x_n,y_1...y_n> \in S} p(x_1...x_n,y_1...y_n)=1 \]

那么对于给定的一个生成标记模型，从序列\(x_1...x_n\)中标记出序列\(y_1...y_n\)被定义如下： \[ f(x_1...x_n)=arg\,\, \max_{y_1...y_n}\,\,p(x_1...x_n,y_1...y_n) \]

Trigram Hidden Markov Models

这里是Trigram，也就是说序列中\(y_i\)只与\(y_{i-1}\)和\(y_{i-2}\)有关。

给出下面两个参数 ：

参数\(q(s|u,v)\)：对于任意的trigram\((u,v,s)\)，其中\(s \in K \cup \{STOP\}, u,v \in K \cup \{*\}\)，其概率\(q(s|u,v)\)可由在看到s在bigram \((u,v)\)后的概率。

参数\(e(x|s)\)：对于任意\(x \in V, s \in K​\)这个值可以表示为看见观测值x配对s的概率。

那么之前概率\(p(x_1...x_n,y_1...y_{n+1})\)可以表示如下： \[ p(x_1...x_n,y_1...y_{n+1})=p(y_1...y_{n+1})p(x_1...x_n|y_1...y_{n+1})\\ =\prod_{i=1}^{n+1} q(y_i|y_{i-2},y_{i-1}) \prod_{i=1}^{n} e(x_i|y_i) \]

这里有\(y_{n+1}=STOP，y_0=y_{-1}=*\)。 那么为什么上面这个公式成立呢，这里是有一些假设的，这里使用随机变量序列\(X_1...X_n\)和\(Y_1...Y_n\)，其中n为序列的长度，假设\(X_i\)可以取集合\(V\)中的任意的值，\(Y_i\)可以取集合\(K\)中任意一个标记，那么上式可以被定义为： \[ P(X_1=x_1...X_n=x_n,Y_1=y_1...Y_{n+1}=y_{n+1})\\ =\prod_{i=1}^{n+1}P(Y_i=y_i|Y_{i-2}=y_{i-2},Y_{i-1}=y_{i-1})\prod_{i=1}^{n}P(X_i=x_i|Y_i=y_i) \] 这里第一个连乘是没有问题的，但是第二个连乘是怎么得到的呢，下面一步步分析 这里先讲一下概率模型\(P(X_1=x_1...X_n=x_n)\)的求解，如下： \[ P(X_1=x_1...X_n=x_n) =P(X_n=x_n|X_1=x_1...X_{n-1}=x_{n-1})P(X_1=x_1...X_{n-1}=x_{n-1}) \] 其中\(P(X_1=x_1...X_{n-1}=x_{n-1})\)

\[ =P(X_{n-1}=x_{n-1}|X_1=x_1...X_{n-2}=x_{n-2})P(X_1=x_1...X_{n-2}=x_{n-2}) ... P(X_1=x_1, X_2=x_2)=P(X_2=x_2|X_1=x_1)P(X_1=x_1) \] 这样上面可以表示如下： \[ P(X_1=x_1...X_n=x_n)=\prod_{i=1}^{n}P(X_i=x_i|X_1=x_1...X_{i-1}=x_{i-1}) \] 那么下面这个公式就知道怎么变来的了吧 \[ P(X_1=x_1...X_n=x_n|Y_1=y_1...Y_{n+1}=y_{n+1})\\ =\prod_{i=1}^{n}P(X_i=x_i|X_1=x_1...X_{i-1}=x_{i-1},Y_1=y_1...Y_{n+1}=y_{n+1}) \] 这里做了一个假设，变量\(X_i\)独立于之前的观测变量\(X_1...X_{i-1}\)和状态变量\(Y_1...Y_{i-1},Y_{i+1}...Y_{n+1}\) ，当被给出变量\(Y_i\)时。那么上面的式子就变为： \[ \prod_{i=1}^{n}P(X_i=x_i|X_1=x_1...X_{i-1}=x_{i-1},Y_1=y_1...Y_{n+1}=y_{n+1})\\ =\prod_{i=1}^{n}P(X_i=x_i|Y_i=y_i) \]

Estimating the Parameters of a Trigram HMM

这里定义一下\(c(s \to x)\)为在语料库中标签s和单词x匹配的次数，那么上述的两个参数在语料库中的最大似然估计如下： \[ q(s|u,v)=\frac{c(u,v,s)}{c(u,v)}\\ e(x|s)=\frac{c(s \to x)}{c(s)} \] 同样对于在语料库中\(q(s|u,v)\)为0的情况，我们用上一章中讲到的解决，对于\(e(x|s)\)为0的情况，也就是说在语料库中没有出现该单词，这里notes中给出一种解决办法就是使用伪词(pseudo-words)[这块没有细看，后期用到再补]

Decoding with HMMs: the Viterbi Algorithm

那么知道如何求解\(q(s|u,v)\)和\(e(x|s)\)，我们又知道 \[ p(x_1...x_n,y_1...y_{n+1})== \prod_{i=1}^{n+1} q(y_i|y_{i-2},y_{i-1}) \prod_{i=1}^{n} e(x_i|y_i) \] 而我们的原始问题是发现一组使概率值最大的序列\(y_1...y_{n+1}\)，即： \[ arg\,\, \max_{y_1...y_n}\,\,p(x_1...x_n,y_1...y_n) \] 这里举个例子，对于输入的句子the dog barks ，假设标记集为\(K=\{D,N,V\}\)，那么可能的标记序列\(y_1y_2y_3y_4\)可以是下面任意一种：

D	D	D	STOP
D	D	N	STOP
D	D	V	STOP
D	N	D	STOP
...

对于\(|K|=3\)时，有27种可能，如果计算这\(3^3=27\)种情况中的每一种，找出概率最大的那个序列，显然是不太现实的，我们需要用一种更为简化的方法来解决这个问题。

下面的维特比算法就给出这样一种解决办法，可以将时间复杂度由\(O(|K|^n)\)缩小到\(O(n|K|^3)\)，使用的方法是动态规划，就是对一个长度为n的句子分解，给定初始条件，给出通项公式，即求长度为i的子句最大概率下对应的子标记和长度为i-1的子句最大概率下对应的子标记的关系，这样就可以求出长度为n的原句最大概率下对应的标记。

VITERBI ALGORITHM

输入的句子是\(x_1...x_n\)，对任意的\(k\in \{1...n\}\) ，任意的序列\(y_{-1},y_{0},y_{1}...y_{k}\)，且\(y_i \in K , y_{-1}=y_0=*\)，定义如下函数： \[ r(y_{-1},y_0,y_1,...,y_k)=\prod_{i=1}^{k}q(y_i|y_{i-2},y_{i-1})\prod_{i=1}^{k}e(x_i|y_i) \] 这里举个例子如下： \[ p(x_1...x_n,y_1...y_{n+1})=r(*,*,y1,...,y_n) q(STOP|y_{n-1},y_n) \] 继续，定义\(K_{-1}=K_{0}=\{*\}\)和\(K_k=K\,\,for\,\,k \in \{1...n\}\),定义\(S(k,u,v)\)为序列\(y_{-1},y_{0},y_1,...,y_{k}\) 的集合，其中\(u \in K_{k-1}, v \in K_{k},y_{k-1}=u,y_k=v\)，定义： \[ \pi(k,u,v)= \max_{<y_{-1},y_0,y_1,...,y_k> \in S(k,u,v)} r(y_{-1},y_0,y_1,...,y_k) \] 给定初始条件：\(\pi(0,*,*)=1\)

给定通项公式： \[ \pi(k,u,v)=\max_{w \in K_{k-2}}\big(\pi(k-1,w,u)q(v|w,u)e(x_k|v)\big) \] 算法如下：

代码实现

# -*- coding: utf-8 -*-
# state 存放隐藏序列，sunny 0 rainy 1
# obser 存放观测序列  0 1 2 对应 walk shop clean
# start_p 是初始概率，0元素对应sunny的初始概率 1元素对应rainy的概率
# transition_p 转移概率矩阵 2*2 行为初始状态  列为新状态
# emission_p 发射概率矩阵 2*3 行为隐藏状态  列为可观测状态

# 迭代过程，每次只需要记录第t个时间点 每个节点的最大概率即可，后续计算时直接使用前序节点的最大概率即可
def compute(obser, state, start_p, transition_p, emission_p):
    # max_p 记录每个时间点每个状态的最大概率，i行j列，（i,j）记录第i个时间点 j隐藏状态的最大概率
    max_p = [[0 for col in range(len(state))] for row in range(len(obser))]
    # path 记录max_p 对应概率处的路径 i 行 j列 （i,j）记录第i个时间点 j隐藏状态最大概率的情况下 其前驱状态
    path = [[0 for col in range(len(state))] for row in range(len(obser))]
    # 初始状态(1状态)
    for i in range(len(state)):
        # max_p[0][i]表示初始状态第i个隐藏状态的最大概率
        # 概率 = start_p[i] * emission_p [state[i]][obser[0]]
        max_p[0][i] = start_p[i] * emission_p[state[i]][obser[0]]
        path[0][i] = i
    # 后续循环状态(2-t状态)
    # 此时max_p 中已记录第一个状态的两个隐藏状态概率
    for i in range(1, len(obser)):  # 循环t-1次，初始已计算
        max_item = [0 for i in range(len(state))]
        for j in range(len(state)):  # 循环隐藏状态数，计算当前状态每个隐藏状态的概率
            item = [0 for i in state]
            for k in range(len(state)):  # 再次循环隐藏状态数，计算选定隐藏状态的前驱状态为各种状态的概率
                p = max_p[i - 1][k] * emission_p[state[j]][obser[i]] * transition_p[state[k]][state[j]]
                # k即代表前驱状态 k或state[k]均为前驱状态
                item[state[k]] = p
            # 设置概率记录为最大情况
            max_item[state[j]] = max(item)
            # 记录最大情况路径(下面语句的作用：当前时刻下第j个状态概率最大时，记录其前驱节点)
            # item.index(max(item))寻找item的最大值索引，因item记录各种前驱情况的概率
            path[i][state[j]] = item.index(max(item))
        # 将单个状态的结果加入总列表max_p
        max_p[i] = max_item
    #newpath记录最后路径
    newpath = []
    #判断最后一个时刻哪个状态的概率最大
    p=max_p[len(obser)-1].index(max(max_p[len(obser)-1]))
    newpath.append(p)
    #从最后一个状态开始倒着寻找前驱节点
    for i in range(len(obser) - 1, 0, -1):
        newpath.append(path[i][p])
        p = path[i][p]
    newpath.reverse()
    return newpath


if __name__ == '__main__':
    #   隐状态
    hidden_state = ['rainy', 'sunny']
    #   观测序列
    obsevition = ['walk', 'shop', 'clean']
    state_s = [0, 1]
    obser = [0, 1, 2]
    #   初始状态，测试集中，0.6概率观测序列以sunny开始
    start_probability = [0.6, 0.4]
    #   转移概率，0.7：sunny下一天sunny的概率
    transititon_probability = [[0.7, 0.3], [0.4, 0.6]]
    #   发射概率，0.4：sunny在0.4概率下为shop
    emission_probability = [[0.1, 0.4, 0.5], [0.6, 0.3, 0.1]]
    result = compute(obser, state_s, start_probability, transititon_probability, emission_probability)
    for k in range(len(result)):
        print(hidden_state[int(result[k])])