攻城狮成长日志(七):隐马尔可夫HMM,NER不得不说的秘密

隐马尔可夫模型与条件随机场,NER不得不说的秘密

命名实体识别简介
隐马尔可夫模型(HMM)
维特比算法
数据集及结果
总结
参考文献:

命名实体识别简介

命名实体识别（Named Entity Recognition，简称NER），又称作“专名识别”，是指识别文本中具有特定意义的实体，主要包括人名、地名、机构名、专有名词等。简单的讲，就是识别自然文本中的实体指称的边界和类别。

简单举个栗子来说,就是对于一句话 “我爱中华人民共和国”,命名实体识别需要做的是不仅能够对于将其分开成“我/爱/中华人民共和国”,相应的还要标示出“我”,“爱”,“中华人民共和国”等词的属性,例如:“我(名词)/爱(动词)/中华人民共和国(名词)”

命名实体识别对目前的NLP的工作有重要意义,例如分词,知识图谱的构建,提升分类器性能等方面发挥的了重要作用.大多数的命名实体识别既有基于机器学习的策略,也有采用当下火热的深度学习策略.

隐马尔可夫模型(HMM)

对于命名实体识别任务来说,隐马尔可夫模型把一个句子设想成一个对应的链状结构考虑,依旧以“我爱中华人民共和国”为例子,其构建的对应的模型如下:

可以看到,一句话被建模成了如上的一个概率图模型,注意这是一个有方向的概率图,同时可以看到,有转移概率和发射概率.这又是怎么回事呢?

其实,转移概率简单来说,就是从上一个词到下一个词的概率,比如上图的转移概率,假设对于t时刻的一个词 $W_t$ 公式就可写作:
$P(x_t)=P(x_t|x_{t-1})P(x_{t-1})$ $P(x_t|x_{t-1})=\frac{count(x_{t-1}\rightarrow x)}{count(x_{t-1})}$
注意这里涉及到一个对应的假设,即齐次马尔科夫性假设------隐藏的马尔科夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻t无关.

对应的发射概率也有一个对应的假设,即观测独立性假设--------假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他观测即状态无关.观测概率的公式可以表达如下:
$P(y_t)=P(y_t|x_t)P(x_t)$ $P(y_t|x_t)=\frac{count(x \rightarrow y)}{count(x)}$

紧接着我们呢将发射概率和转移概率相结合,就可以得到整个句子最后的公式了:
$P(x,y)=P(y_1|start)\prod_{t=1}^{L-1}P(y_{t+1}|y_t)P(end|y_t)\prod_{t=1}^LP(x_t|y_t)$

为此,要实现HMM算法,必须要有对应的两个矩阵,一个是发射概率矩阵,一个则是对应的转移概率矩阵.这显而易见了

class HMM(object):
    def __init__(self, N, M):
        """ 隐马尔可夫模型 :param N: 状态数即对应的隐藏标注种类 :param M: 观测数即对应的字数 """
        self.N = N
        self.M = M
        self.A = torch.zeros(N, M)  # 状态转移矩阵
        self.B = torch.zeros(N, M)  # 发射概率矩阵
        self.Pi = torch.zeros(N)  # 初始状态矩阵

    def train(self, word_lists, tag_lists, word2id, tag2id):
        """ 对应隐马的训练过程，其实是统计的过程 :param word_list: 列表，其中每个元素由字组成的列表，如 ['担','任','科','员'] :param tag_list: 列表，其中每个元素是由对应的标注组成的列表，如 ['O','O','B-TITLE', 'E-TITLE'] :param word2id: 将字映射为ID :param tag2id: 字典，将标注映射为ID :return: """

        assert len(word_lists) == len(tag_lists)  # 用于判断对应的每一个观测状态是否都有对应的隐藏状态

        # 统计概率转移矩阵
        for tag_list in tag_lists:
            # 统计状态转换矩阵
            seq_len = len(tag_list)
            for i in range(seq_len - 1):
                current_tagid = tag2id[tag_list[i]]
                next_tagid = tag2id[tag_list[i + 1]]
                self.A[current_tagid][next_tagid] += 1

            # 统计初始状态矩阵
            init_tag = tag_list[0]
            init_tagid = tag2id[init_tag]
            self.Pi[init_tagid] += 1

        # 估计发射概率矩阵
        for i in range(len(word_lists)):
            word_list = word_lists[i]
            tag_list = tag_lists[i]
            assert len(word_list) == len(tag_list)
            for j in range(len(word_list)):
                tag_list2id = tag2id[tag_list[j]]
                word_list2id = word2id[word_list[j]]
                self.B[tag_list2id][word_list2id] += 1

        # 避免为0，添上一个极小数
        self.A[self.A == 0] = 1e-10
        self.A = self.A / self.A.sum(dim=1, keepdim=True)

        self.Pi[self.Pi == 0] = 1e-10
        self.Pi = self.Pi / self.Pi.sum()

        self.B[self.B == 0] = 1e-10
        self.B = self.B / self.B.sum(dim=1, keepdim=True)

维特比算法

那当我们运用统计的力量,计算完之后,疑惑又来了,我们单纯有了两个对应的矩阵,我们怎么从这两个矩阵里面取出对应的序列呢?那就必须要用到维特比算法了.维特比算法本身并不复杂,但讲起来篇幅较长,这里就交给专业一点的人士来说明啦---->如何通俗地讲解 viterbi 算法？
同样我也很推荐上b站看一些网课什么的,更加的清晰易懂.~~(李宏毅老师讲得是真的好!还有)~~
HMM/CRF by李宏毅
或者是:
汉语自然语言处理-维特比算法与NER-命名实体识别-viterbi algorithm-HMM-CRF
这里我直接附上代码好啦:

    def decoding(self, word_list, word2id, tag2id):
        """ 维特比算法查找最佳的序列. :param word_lists: :param word2id: :param tag2id: :return: """
        # 将相乘转换成相加避免下溢
        logA = torch.log(self.A)
        logB = torch.log(self.B)
        logPi = torch.log(self.Pi)
        seq_len = len(word_list)
        # 初始化维特比矩阵，维度（状态数*序列长度)
        Viterbi = torch.zeros(self.N, seq_len)

        # 解码回溯时使用
        # backPoints[i, j]存储的是 标注序列的第j个标注为i时，第j-1个标注的id
        backPoints = torch.zeros(self.N, seq_len)

        # 计算初始的转换选择的概率为多少
        BT = logB.t()  # 将B转置
        start_wordid = word2id.get(word_list[0], None)
        if not start_wordid:
            # 如果该词不在字典中则默认发射概率为均值
            bt = torch.log(torch.ones(self.N) / self.N)
        else:
            # 否则计算对应的词id，同时获取对应的B中可能转移到初始词的所有隐藏状态bt
            bt = BT[start_wordid]
        # 所有初始隐藏状态出现概率Pi 再加上 从初始隐藏状态发射到对应词和字的概率.
        Viterbi[:, 0] = logPi + bt
        backPoints[:, 0] = -1

        # 递推公式: 维特比第step的tag_id的状态等于step-1步的所有隐藏状态,
        # 乘以step-1步隐藏状态转移到step步的条件概率，
        # 再乘以对应step步发射到对应词的条件概率
        # Viterbi[tag_id, step] = max(Viterbi[: , step-1] * self.A.T()[tag_id] * Bt[word]
        for step in range(1, seq_len):
            word_id = word2id.get(word_list[step], None)
            if not word_id:
                bt = torch.log(torch.ones(self.N) / self.N)
            else:
                bt = BT[word_id]
            for tag_id in range(len(tag2id)):
                max_prob, max_id = torch.max(Viterbi[:, step - 1] + logA[:, tag_id], dim=0)
                Viterbi[tag_id, step] = max_prob + bt[tag_id]
                backPoints[tag_id, step] = max_id

        # 找到最后的标签并回溯
        best_path_prob, best_path_pointer = torch.max(
            Viterbi[:, seq_len - 1], dim=0
        )

        best_path_pointer = best_path_pointer.item()
        best_path = [best_path_pointer]
        for back_step in range(seq_len - 1, 0, -1):
            best_path_pointer = backPoints[best_path_pointer, back_step]
            best_path_pointer = int(best_path_pointer.item())
            best_path.append(best_path_pointer)

        # 将标签转换成字词
        assert len(best_path) == seq_len
        id2tag = dict((id, tag) for tag, id in tag2id.items())
        tag_path = [id2tag[id] for id in reversed(best_path)]
        return tag_path

同时计算准确率的方式如下,值得注意的是,严格的准确率计算是需要同时考虑分别出来的实体的标签,以及对应的实体划分到的范围的,缺一不可,而这里我只实现了对划分出来的实体进行判断,这一步还有待改进.

    def Cal_Entity(self):
        # 计算对应的correctEntity,labelEntity,predictEntity三类实体的数目
        assert len(self.y) == len(self.label)
        for i in range(len(self.y)):
            assert len(self.y[i]) == len(self.label[i])
            # 逐个比对对应的标签状态
            tem_predict = self.Split(self.x[i], self.y[i])
            tem_label = self.Split(self.x[i], self.label[i])
            for e in tem_predict:
                if e in tem_label:
                    self.correctEntity += 1
            self.labelEntity += len(tem_label)
            self.predictEntity += len(tem_predict)
            
        def Split(self, x, y):
        # 精确匹配分割对应的实体集
        i = 0
        strings = []
        while i < len(y):
            string = ""
            if y[i][0] == 'B':
                # 匹配到开头则分割词
                while i < len(y) and y[i][0] != 'E':
                    string += x[i]
                    i += 1
                string += x[i]
            else:
                i += 1
            if string:
                strings.append(string)
        return strings
        
    def Accuracy(self):
        return self.correctEntity / self.predictEntity