放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

基于HMM2-Trigram字符序列标注的中文分词器Java实现

目录

谈起基于Character-Based Generative Model的中文分词方法,普遍的印象是在Bakeoff上的成绩好,对OOV的识别率高。HanLP中实现的CRF分词器其实就是这种原理的分词器,然而CRF分词缺点也是很明显的:

一)模型体积大占内存。一个可供生产环境用的CRF模型至少使用前中后3个字符的组合做特征模板,在一两百兆的语料上训练,模型体积至少上百兆(有的分词器用gzip压缩过,看起来稍小),加载后更耗资源。HanLP原本使用DAT储存CRF中的特征函数,然而内存实在吃不消,降级为BinTrie后才维持了100MB的体积。

二)速度慢。相较于基于词语的BiGram分词器,一个拖速度的地方是特征函数的查询次数多、速度慢,另一个弱点则是概率图的节点更多(4倍文本长度个节点,4是bmes标签的个数),于是跑Viterbi的速度也慢下来了。

三)无法修改。有时候用户对分词结果不满意,却无法方便地修正它。据我所知,只有基于词语的NGram词典和词频词典可以轻松修改,包括CRF在内的其他模型都需要重新训练,或者修改代码。

有读者问我HanLP为什么选择基于字符的HMM-BiGram作为主要的分词方法,我回答后觉得不够满意,所以利用一天的时间实现了一个基于HMM2-TriGram字符序列标注的分词器,与其他分词器(CRF分词器基于词语的HMM-BiGram分词器做个直观的比较,以飨读者。

毕竟水平有限,文章中有关术语可能不准确,欢迎提出宝贵意见。

二阶HMM

二阶HMM对应三阶文法模型,两个称呼的阶数相差一个,经常搞混。如果一篇文章用BiGram、二维转移矩阵做二阶隐马分词,那就不用看了。

不同于一阶HMM,二阶HMM中每个状态的概率都与前两个状态有关。

t3是当前状态,同理定义t1和t2。

训练

训练其实就是以3个顺序词语为一个视窗,统计123-Gram的频次。

/**
 * 让模型观测一个句子
 * @param wordList
 */
public void learn(List<Word> wordList)
{
    LinkedList<char[]> sentence = new LinkedList<char[]>();
    for (IWord iWord : wordList)
    {
        String word = iWord.getValue();
        if (word.length() == 1)
        {
            sentence.add(new char[]{word.charAt(0), 's'});
        }
        else
        {
            sentence.add(new char[]{word.charAt(0), 'b'});
            for (int i = 1; i < word.length() - 1; ++i)
            {
                sentence.add(new char[]{word.charAt(i), 'm'});
            }
            sentence.add(new char[]{word.charAt(word.length() - 1), 'e'});
        }
    }
    // 转换完毕,开始统计
    char[][] now = new char[3][];   // 定长3的队列
    now[1] = bos;
    now[2] = bos;
    tf.add(1, bos, bos);
    tf.add(2, bos);
    for (char[] i : sentence)
    {
        System.arraycopy(now, 1, now, 0, 2);
        now[2] = i;
        tf.add(1, i);   // uni
        tf.add(1, now[1], now[2]);   // bi
        tf.add(1, now);   // tri
    }
}

有了tri的频次,按照二阶隐马的概率最大化公式:

原本就可以计算的,然而按照Thorsten Brants的说法,由于数据的稀疏性,导致tri-gram的实例数目不够,无法达到令人满意的效果。所以他提出了TnT(Trigrams'n'Tags)标注器,将uni和bi补充进来起平滑作用:

其中三个系数,可以通过如下算法在线性时间内计算出来:

HanLP中对应如下代码:

/**
 * 观测结束,开始训练
 */
public void train()
{
    double tl1 = 0.0;
    double tl2 = 0.0;
    double tl3 = 0.0;
    for (String key : tf.d.keySet())
    {
        if (key.length() != 6) continue;    // tri samples
        char[][] now = new char[][]
                {
                        {key.charAt(0), key.charAt(1)},
                        {key.charAt(2), key.charAt(3)},
                        {key.charAt(4), key.charAt(5)},
                };
        double c3 = div(tf.get(now) - 1, tf.get(now[0], now[1]) - 1);
        double c2 = div(tf.get(now[1], now[2]) - 1, tf.get(now[1]) - 1);
        double c1 = div(tf.get(now[2]) - 1, tf.getsum() - 1);
        if (c3 >= c1 && c3 >= c2)
            tl3 += tf.get(now);
        else if (c2 >= c1 && c2 >= c3)
            tl2 += tf.get(now);
        else if (c1 >= c2 && c1 >= c3)
            tl1 += tf.get(now);
    }

    l1 = div(tl1, tl1 + tl2 + tl3);
    l2 = div(tl2, tl1 + tl2 + tl3);
    l3 = div(tl3, tl1 + tl2 + tl3);
}

这部分详细的理论请参考《TnT — A Statistical Part-of-Speech Tagger .pdf》。

标注

转移矩阵是三维的,在实现的时候(主要参考了snownlp的Python代码),采用了动态计算的方式计算转移概率:

/**
 * 求概率
 * @param s1 前2个状态
 * @param s2 前1个状态
 * @param s3 当前状态
 * @return 序列的概率
 */
double log_prob(char[] s1, char[] s2, char[] s3)
{
    double uni = l1 * tf.freq(s3);
    double bi = div(l2 * tf.get(s2, s3), tf.get(s2));
    double tri = div(l3 * tf.get(s1, s2, s3), tf.get(s1, s2));
    if (uni + bi + tri == 0)
        return inf;
    return Math.log(uni + bi + tri);
}

有了转移概率,之后就可以Viterbi解码了。

由于转移概率与前两个状态有关,所以需要为每个状态准备一个二维的dp数组(原Python代码用了一个dict存路径,虽然代码短,但运行起来真的奇慢无比),另外加上状态本身的下标,dp数组一共3维:

// link[i][s][t] := 第i个节点在前一个状态是s,当前状态是t时,前2个状态的tag的值
int[][][] link = new int[charArray.length][4][4];

不过,第一个字和第二字有些特殊,它们的前2个状态不存在,越界了。所以这时候特殊处理,使用bos状态替代不存在的状态计算概率:

// 第一个字,只可能是bs
for (int s = 0; s < 4; ++s)
{
    double p = (s == 1 || s == 2) ? inf : log_prob(bos, bos, new char[]{charArray[0], id2tag[s]});
    first[s] = p;
}

// 第二个字,尚不能完全利用TriGram
for (int f = 0; f < 4; ++f)
{
    for (int s = 0; s < 4; ++s)
    {
        double p = first[f] + log_prob(bos, new char[]{charArray[0], id2tag[f]}, new char[]{charArray[1], id2tag[s]});
        now[f][s] = p;
        link[1][f][s] = f;
    }
}

从第三个字开始就好办了:

// 第三个字开始,利用TriGram标注
double[][] pre = new double[4][4];
for (int i = 2; i < charArray.length; i++)
{
    // swap(now, pre)
    double[][] _ = pre;
    pre = now;
    now = _;
    // end of swap
    for (int s = 0; s < 4; ++s)
    {
        for (int t = 0; t < 4; ++t)
        {
            now[s][t] = -1e20;
            for (int f = 0; f < 4; ++f)
            {
                double p = pre[f][s] + log_prob(new char[]{charArray[i - 2], id2tag[f]},
                                                new char[]{charArray[i - 1], id2tag[s]},
                                                new char[]{charArray[i],     id2tag[t]});
                if (p > now[s][t])
                {
                    now[s][t] = p;
                    link[i][s][t] = f;
                }
            }
        }
    }
}

循环结束后,now矩阵中对应16条路径的最终得分,从中挑出得分最高的那一条,通过link数组还原该路径:

double score = inf;
int s = 0;
int t = 0;
for (int i = 0; i < 4; i++)
{
    for (int j = 0; j < 4; j++)
    {
        if (now[i][j] > score)
        {
            score = now[i][j];
            s = i;
            t = j;
        }
    }
}
for (int i = link.length - 1; i >= 0; --i)
{
    tag[i] = id2tag[t];
    int f = link[i][s][t];
    t = s;
    s = f;
}
return tag;

二阶HMM分词

bmes合并

有了标签,合并就很简单了。我采用了正向合并的方式:

char[] tag = model.tag(sentence);
List<Term> termList = new LinkedList<Term>();
int offset = 0;
for (int i = 0; i < tag.length; offset += 1, ++i)
{
    switch (tag[i])
    {
        case 'b':
        {
            int begin = offset;
            while (tag[i] != 'e')
            {
                offset += 1;
                ++i;
                if (i == tag.length)
                {
                    break;
                }
            }
            if (i == tag.length)
            {
                termList.add(new Term(new String(sentence, begin, offset - begin), null));
            }
            else
                termList.add(new Term(new String(sentence, begin, offset - begin + 1), null));
        }
        break;
        default:
        {
            termList.add(new Term(new String(sentence, offset, 1), null));
        }
        break;
    }
}

return termList;

你可能会很奇怪,怎么只看到了b和e标签,s和m标签在哪里呢?

这是因为,HMM标注的结果不一定是合法的(甚至连CRF的标注结果都不一定合法),所谓的不合法,指的是可能出现bbse这种不闭合的现象。如果严格按照b开始,m入栈,e出栈的逻辑来是会出问题的。

直观评测

我一直很反对用封闭测试集测成绩,同时我又拿不到较好的开放测试集,所以只是从直观的结果做一个评测:

HanLP.Config.ShowTermNature = false;    // 关闭词性显示
Segment segment = new HMMSegment();
String[] sentenceArray = new String[]
        {
                "HanLP是由一系列模型与算法组成的Java工具包,目标是普及自然语言处理在生产环境中的应用。",
                "高锰酸钾,强氧化剂,紫红色晶体,可溶于水,遇乙醇即被还原。常用作消毒剂、水净化剂、氧化剂、漂白剂、毒气吸收剂、二氧化碳精制剂等。", // 专业名词有一定辨识能力
                "《夜晚的骰子》通过描述浅草的舞女在暗夜中扔骰子的情景,寄托了作者对庶民生活区的情感",    // 非新闻语料
                "这个像是真的[委屈]前面那个打扮太江户了,一点不上品...@hankcs",                       // 微博
                "鼎泰丰的小笼一点味道也没有...每样都淡淡的...淡淡的,哪有食堂2A的好次",
                "克里斯蒂娜·克罗尔说:不,我不是虎妈。我全家都热爱音乐,我也鼓励他们这么做。",
                "今日APPS:Sago Mini Toolbox培养孩子动手能力",
                "财政部副部长王保安调任国家统计局党组书记",
                "2.34米男子娶1.53米女粉丝 称夫妻生活没问题",
                "你看过穆赫兰道吗",
                "乐视超级手机能否承载贾布斯的生态梦"
        };
for (String sentence : sentenceArray)
{
    List<Term> termList = segment.seg(sentence);
    System.out.println(termList);
}

// 测个速度
String text = "江西鄱阳湖干枯,中国最大淡水湖变成大草原";
System.out.println(segment.seg(text));
long start = System.currentTimeMillis();
int pressure = 1000;
for (int i = 0; i < pressure; ++i)
{
    segment.seg(text);
}
double costTime = (System.currentTimeMillis() - start) / (double)1000;
System.out.printf("HMM2分词速度:%.2f字每秒\n", text.length() * pressure / costTime);
// 与其他分词器作比较
System.gc();
DemoBasicTokenizer.main(null);
System.gc();
DemoHighSpeedSegment.main(null);

结果

速度

HMM2分词速度:             22172.95字每秒
BasicTokenizer分词速度: 1785145.04字每秒
SpeedTokenizer分词速度:17241379.31字每秒

同一台机器(AMD A10-5800K)上,其他分词器的速度要快很多。(注:由于HMM2模型很大,所以跑这个例子必须给足内存)

效果

HMM2:
[HanLP是由一系列, 模型, 与, 算法, 组成, 的, Java工具, 包, ,, 目标, 是, 普及, 自然, 语言, 处理, 在, 生产, 环境, 中, 的, 应用, 。]
[高锰酸钾, ,, 强氧化剂, ,, 紫红色, 晶体, ,, 可, 溶于, 水, ,, 遇乙醇, 即, 被, 还原, 。, 常, 用作, 消毒, 剂, 、, 水, 净化剂, 、, 氧化剂, 、, 漂白剂, 、, 毒气, 吸收, 剂, 、, 二氧化碳, 精制剂, 等, 。]
[《, 夜晚, 的, 骰子, 》, 通过, 描述, 浅, 草, 的, 舞女, 在, 暗夜, 中, 扔骰子, 的, 情景, ,, 寄托, 了, 作者, 对庶民, 生活区, 的, 情感]
[这个, 像, 是, 真的, [, 委屈, ], 前面, 那个, 打扮, 太, 江, 户, 了, ,, 一点, 不, 上品, ., ., ., @, hankcs]
[鼎泰丰, 的, 小笼, 一点, 味道, 也, 没有, ., ., ., 每样, 都, 淡淡, 的, ., ., ., 淡淡的, ,, 哪, 有, 食堂, 2A, 的, 好次]
[克里斯蒂娜·克罗尔, 说, :, 不, ,, 我, 不是, 虎妈, 。, 我, 全家, 都, 热爱, 音乐, ,, 我, 也, 鼓励, 他们, 这么, 做, 。]
[今日, APPS, :, Sago Mini Toolbox培养, 孩子, 动手, 能力]
[财政部, 副部长, 王保安, 调任, 国家, 统计局, 党组, 书记]
[2, ., 34, 米, 男子, 娶, 1, ., 53, 米, 女, 粉丝,  称夫妻, 生活, 没问题]
[你, 看过, 穆赫, 兰, 道, 吗]
[乐, 视, 超级, 手机, 能否, 承载, 贾布斯, 的, 生态, 梦]
对比DemoCRFSegment的输出:
[HanLP, 是, 由, 一系列, 模型, 与, 算法, 组成, 的, Java, 工具包, ,目标, 是, 普及, 自然, 语言, 处理, 在, 生产, 环境, 中, 的, 应用, 。]
[高锰酸钾, ,强氧化剂, ,紫红色, 晶体, ,可, 溶于, 水, ,遇, 乙醇, 即, 被, 还原, 。常, 用作, 消毒剂, 、, 水, 净化剂, 、, 氧化剂, 、, 漂白剂, 、, 毒气, 吸收剂, 、, 二氧化碳, 精制剂, 等, 。]
[《, 夜晚, 的, 骰子, 》, 通过, 描述, 浅草, 的, 舞女, 在, 暗夜, 中, 扔, 骰子, 的, 情景, ,寄托, 了, 作者, 对, 庶民, 生活区, 的, 情感]
[这个, 像, 是, 真的, [, 委屈, ], 前面, 那个, 打扮, 太, 江户, 了, ,一点, 不, 上品, ., ., ., @, hankcs]
[鼎泰丰, 的, 小笼, 一点, 味道, 也, 没有, ., ., ., 每样, 都, 淡淡的, ., ., ., 淡淡的, ,哪, 有, 食堂, 2, A, 的, 好次]
[克里斯蒂娜·克罗尔, 说, :, 不, ,我, 不是, 虎妈, 。我, 全家, 都, 热爱, 音乐, ,我, 也, 鼓励, 他们, 这么, 做, 。]
[今日, APPS, :, Sago,  , Mini,  , Toolbox, 培养, 孩子, 动手, 能力]
[财政部, 副部长, 王保安, 调任, 国家, 统计局, 党组, 书记]
[2.34, 米, 男子, 娶, 1.53, 米, 女, 粉丝,  , 称, 夫妻, 生活, 没问题]
[你, 看过, 穆赫兰道, 吗]
[乐, 视, 超级, 手机, 能否, 承载, 贾布斯, 的, 生态, 梦]

可以看出从分词效果来看,HMM2分词器倾向于将未知的单字粘合到一起,显然HMM没有CRF那么聪明,很多地方都粘错了。

结论

无论是从速度还是效果来看,我都认为二阶HMM不适合用来分词。CRF由于效果突出,所以在对速度要求不高的场合还有一点用武之地,但是二阶HMM显然是个尴尬的角色。更不用提一阶HMM的效果了,那些执着于“单字发射概率”的分词器,应当向高阶HMM乃至CRF发展。这就是我对基于字符标注的中文分词器的一点浅显看法,欢迎指正。

关于HanLP

HanLP目前的分词器架构如下:

HanLP希望做成所有分词器的超集,通过比较各种分词算法、各种NLP模型、各种数据结构,最终得出一个趋向于完美的汉语言处理工具。欢迎大家fork,提出宝贵意见!

Reference

TnT — A Statistical Part-of-Speech Tagger .pdf

Which is More Suitable for Chinese Word Segmentation the Generative Model or the Discriminative One.pdf

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 基于HMM2-Trigram字符序列标注的中文分词器Java实现

分享到:更多 ()

评论 11

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #7

    作者你好,麻烦问一下,发射概率是已经包含在转移概率之中了吗

    2个月前 (05-04)回复
  2. #6

    作者你好, 我看到你的hanlp中的 基于viterbi的最短路径分词算法, 那个算weight的公式是怎么来的, 有参考论文么? 谢谢

    A.Zhang9个月前 (09-19)回复
    • 《基于二元语法的N-最大概率中文粗分模型》《基于贝叶斯网络的二元语法中文分词模型》《用基于词的二元模型消解交集型分词歧义》,第三篇作者是文学院的因此写得比较浅显易懂。

      辰刚5个月前 (01-25)回复
      • 人家说的是什么插值公式,你说的那几篇文章除了第一篇讲到简单线性插值还沾得到上边外,其他的好像没提及!瞎说

        It-is-written-彬3个月前 (03-19)回复
        • 首先,人家说的不是“插值“公式,而是完整的路径权重计算公式。其次第一篇文章的路径计算公式不同于viterbi分词,是我的错误。第三,后两篇文章都提到了路径计算和用低阶插值。第四,HanLP和ANSJ用低阶模型插值部分的公式并不正确,经过多次查阅Jelinek-Mercer插值方法并结合分词实验,发现公式并不准确,但是能解决一些特殊分词问题,如“修改稿件”。

          辰刚2周前 (06-09)回复
  3. #5

    群主 有个小问题,分词器架构下的那么多分词模块 最后怎么整合得出分词结果的?

    阿卜杜拉_Snake11个月前 (08-15)回复
  4. #4

    博主 我现在也在研究 能不能交流一下 现在正在看哥伦比亚大学的一个NLP视频 还有宗成庆的 但是实现感觉挺困难 求交流啊

    贝壳鸟1年前 (2016-05-28)回复
  5. #3

    博主 你也太牛了吧

    贝壳鸟1年前 (2016-05-28)回复
  6. #2

    楼主。请收下我的膝盖!

    嘿嘿2年前 (2015-06-17)回复
  7. #1

    在微博私信中提出来的一些疑惑,没想到博主这样有心,大赞! [赞]

    ZhouYC_CS2年前 (2015-05-08)回复
    • 不客气,我也学到TnT这个标注模型 [嘻嘻]

      hankcs2年前 (2015-05-08)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机