17 Aug

【中文分词系列】 1. 基于AC自动机的快速分词

前言:这个暑假花了不少时间在中文分词和语言模型上面,碰了无数次壁,也得到了零星收获。打算写一个专题,分享一下心得体会。虽说是专题,但仅仅是一些笔记式的集合,并非系统的教程,请读者见谅。

中文分词

关于中文分词的介绍和重要性,我就不多说了,matrix67这里有一篇关于分词和分词算法很清晰的介绍,值得一读。在文本挖掘中,虽然已经有不少文章探索了不分词的处理方法,如本博客的《文本情感分类(三):分词 OR 不分词》,但在一般场合都会将分词作为文本挖掘的第一步,因此,一个有效的分词算法是很重要的。当然,中文分词作为第一步,已经被探索很久了,目前做的很多工作,都是总结性质的,最多是微弱的改进,并不会有很大的变化了。

目前中文分词主要有两种思路:查词典字标注。首先,查词典的方法有:机械的最大匹配法、最少词数法,以及基于有向无环图的最大概率组合,还有基于语言模型的最大概率组合,等等。查词典的方法简单高效(得益于动态规划的思想),尤其是结合了语言模型的最大概率法,能够很好地解决歧义问题,但对于中文分词一大难度——未登录词(中文分词有两大难度:歧义和未登录词),则无法解决;为此,人们也提出了基于字标注的思路,所谓字标注,就是通过几个标记(比如4标注的是:single,单字成词;begin,多字词的开头;middle,三字以上词语的中间部分;end,多字词的结尾),把句子的正确分词法表示出来。这是一个序列(输入句子)到序列(标记序列)的过程,能够较好地解决未登录词的问题,但速度较慢,而且对于已经有了完备词典的场景下,字标注的分词效果可能也不如查词典方法。总之,各有优缺点(似乎是废话~),实际使用可能会结合两者,像结巴分词,用的是有向无环图的最大概率组合,而对于连续的单字,则使用字标注的HMM模型来识别。

点击阅读全文...

1 Jul

从Boosting学习到神经网络:看山是山?

前段时间在潮州给韩师的同学讲文本挖掘之余,涉猎到了Boosting学习算法,并且做了一番头脑风暴,最后把Boosting学习算法的一些本质特征思考清楚了,而且得到一些意外的结果,比如说AdaBoost算法的一些理论证明也可以用来解释神经网络模型这么强大。

AdaBoost算法

Boosting学习,属于组合模型的范畴,当然,与其说它是一个算法,倒不如说是一种解决问题的思路。以有监督的分类问题为例,它说的是可以把弱的分类器(只要准确率严格大于随机分类器)通过某种方式组合起来,就可以得到一个很优秀的分类器(理论上准确率可以100%)。AdaBoost算法是Boosting算法的一个例子,由Schapire在1996年提出,它构造了一种Boosting学习的明确的方案,并且从理论上给出了关于错误率的证明。

以二分类问题为例子,假设我们有一批样本$\{x_i,y_i\},i=1,2,\dots,n$,其中$x_i$是样本数据,有可能是多维度的输入,$y_i\in\{1,-1\}$为样本标签,这里用1和-1来描述样本标签而不是之前惯用的1和0,只是为了后面证明上的方便,没有什么特殊的含义。接着假设我们已经有了一个弱分类器$G(x)$,比如逻辑回归、SVM、决策树等,对分类器的唯一要求是它的准确率要严格大于随机(在二分类问题中就是要严格大于0.5),所谓严格大于,就是存在一个大于0的常数$\epsilon$,每次的准确率都不低于$\frac{1}{2}+\epsilon$

点击阅读全文...

22 Aug

【中文分词系列】 4. 基于双向LSTM的seq2seq字标注

关于字标注法

上一篇文章谈到了分词的字标注法。要注意字标注法是很有潜力的,要不然它也不会在公开测试中取得最优的成绩了。在我看来,字标注法有效有两个主要的原因,第一个原因是它将分词问题变成了一个序列标注问题,而且这个标注是对齐的,也就是输入的字跟输出的标签是一一对应的,这在序列标注中是一个比较成熟的问题;第二个原因是这个标注法实际上已经是一个总结语义规律的过程,以4tag标注为为例,我们知道,“李”字是常用的姓氏,一半作为多字词(人名)的首字,即标记为b;而“想”由于“理想”之类的词语,也有比较高的比例标记为e,这样一来,要是“李想”两字放在一起时,即便原来词表没有“李想”一词,我们也能正确输出be,也就是识别出“李想”为一个词,也正是因为这个原因,即便是常被视为最不精确的HMM模型也能起到不错的效果。

关于标注,还有一个值得讨论的内容,就是标注的数目。常用的是4tag,事实上还有6tag和2tag,而标记分词结果最简单的方法应该是2tag,即标记“切分/不切分”就够了,但效果不好。为什么反而更多数目的tag效果更好呢?因为更多的tag实际上更全面概括了语义规律。比如,用4tag标注,我们能总结出哪些字单字成词、哪些字经常用作开头、哪些字用作末尾,但仅仅用2tag,就只能总结出哪些字经常用作开头,从归纳的角度来看,是不够全面的。但6tag跟4tag比较呢?我觉得不一定更好,6tag的意思是还要总结出哪些字作第二字、第三字,但这个总结角度是不是对的?我觉得,似乎并没有哪些字固定用于第二字或者第三字的,这个规律的总结性比首字和末字的规律弱多了(不过从新词发现的角度来看,6tag更容易发现长词。)。

双向LSTM

点击阅读全文...

6 Sep

基于双向LSTM和迁移学习的seq2seq核心实体识别

暑假期间做了一下百度和西安交大联合举办的核心实体识别竞赛,最终的结果还不错,遂记录一下。模型的效果不是最好的,但是胜在“端到端”,迁移性强,估计对大家会有一定的参考价值。

比赛的主题是“核心实体识别”,其实有两个任务:核心识别 + 实体识别。这两个任务虽然有关联,但在传统自然语言处理程序中,一般是将它们分开处理的,而这次需要将两个任务联合在一起。如果只看“核心识别”,那就是传统的关键词抽取任务了,不同的是,传统的纯粹基于统计的思路(如TF-IDF抽取)是行不通的,因为单句中的核心实体可能就只出现一次,这时候统计估计是不可靠的,最好能够从语义的角度来理解。我一开始就是从“核心识别”入手,使用的方法类似QA系统:

1、将句子分词,然后用Word2Vec训练词向量;

2、用卷积神经网络(在这种抽取式问题上,CNN效果往往比RNN要好)卷积一下,得到一个与词向量维度一样的输出;

3、损失函数就是输出向量跟训练样本的核心词向量的cos值。

点击阅读全文...

12 Sep

【中文分词系列】 5. 基于语言模型的无监督分词

迄今为止,前四篇文章已经介绍了分词的若干思路,其中有基于最大概率的查词典方法、基于HMM或LSTM的字标注方法等。这些都是已有的研究方法了,笔者所做的就只是总结工作而已。查词典方法和字标注各有各的好处,我一直在想,能不能给出一种只需要大规模语料来训练的无监督分词模型呢?也就是说,怎么切分,应该是由语料来决定的,跟语言本身没关系。说白了,只要足够多语料,就可以告诉我们怎么分词。

看上去很完美,可是怎么做到呢?《2.基于切分的新词发现》中提供了一种思路,但是不够彻底。那里居于切分的新词发现方法确实可以看成一种无监督分词思路,它就是用一个简单的凝固度来判断某处该不该切分。但从分词的角度来看,这样的分词系统未免太过粗糙了。因此,我一直想着怎么提高这个精度,前期得到了一些有意义的结果,但都没有得到一个完整的理论。而最近正好把这个思路补全了。因为没有查找到类似的工作,所以这算是笔者在分词方面的一点原创工作了。

语言模型

首先简单谈一下语言模型。

点击阅读全文...

14 Oct

【理解黎曼几何】2. 从勾股定理到黎曼度量

黎曼度量

几何,英文名是Geometry,原意是大地测量。既然是测量,就必须有参考物,还有得知道如何计算距离。

有了参照物,我们就可以建立坐标系,把每个点的坐标都写下来,至于计算距离,我们有伟大的勾股定理:
$$ds^2 = dx^2 + dy^2 \tag{1} $$
但这里我们忽略了两个问题。

第一个问题是,我们不一定使用直角坐标系,如果使用极坐标,那么应该是
$$ds^2 = dr^2 + r^2 d\theta^2 \tag{2} $$
因此可以联想,最一般的形式应该是
$$ds^2 = E(x^1, x^2)(dx^1)^2 + 2F(x^1, x^2)dx^1 dx^2 + G(x^1, x^2)(dx^2)^2 \tag{3} $$
这里的$x^1,x^2$是广义坐标,使用上标而不是下标来标记序号,是为了跟传统的教材记号一致。那这公式是什么意思呢?其实很简单,正如我们没理由要求全世界都使用人民币一样,我们没必要要求世界各地都使用同一个坐标系,而更合理的做法是,每一处地方都使用自己的坐标系(局部坐标系),然后给出当地计算距离的方法。因此,上述公式正是说,在位置$(x^1, x^2)$处计算向量$(dx^1, dx^2)$的长度的公式(当地的勾股定理)是$ds^2 = E(x^1, x^2)(dx^1)^2 + 2F(x_1, x_2)dx^1 dx^2 + G(x^1, x^2)(dx^2)^2$。

点击阅读全文...

18 Oct

【理解黎曼几何】5. 黎曼曲率

现在我们来关注黎曼曲率。总的来说,黎曼曲率提供了一种方案,让身处空间内部的人也能计算自身所处空间的弯曲程度。俗话说,“不识庐山真面目,只缘身在此山中”,还有“当局者迷,旁观者清”,等等,因此,能够身处空间之中而发现空间中的弯曲与否,是一件很了不起的事情,就好像我们已经超越了我们现有的空间,到了更高维的空间去“居高临下”那样。真可谓“心有多远,路就有多远,世界就有多远”。

如果站在更高维空间的角度看,就容易发现空间的弯曲。比如弯曲空间中有一条测地线,从更高维的空间看,它就是一条曲线,可以计算曲率等,但是在原来的空间看,它就是直的,测地线就是直线概念的一般化,因此不可能通过这种途径发现空间的弯曲性,必须有一些迂回的途径。可能一下子不容易想到,但是各种途径都殊途同归后,就感觉它是显然的了。

怎么更好地导出黎曼曲率来,使得它能够明显地反映出弯曲空间跟平直空间的本质区别呢?为此笔者思考了很长时间,看了不少参考书(《引力与时空》、《场论》、《引力论》等),比较了几种导出黎曼曲率的方式,简要叙述如下。

点击阅读全文...

16 Nov

为什么勒贝格积分比黎曼积分强?

学过实变函数的朋友,总会知道有个叫勒贝格积分的东西,号称是黎曼积分的改进版。虽然“实变函数学十遍,泛函分析心泛寒”,在学习实变函数的时候,我们通常都是云里雾里的,不过到最后,在老师的“灌溉”之下,也就耳濡目染了知道了一些结论,比如“黎曼可积的函数(在有限区间),也是勒贝格可积的”,说白了,就是“勒贝格积分比黎曼积分强”。那么,问题来了,究竟强在哪儿?为什么会强?

黎曼

黎曼

勒贝格

勒贝格

这个问题,笔者在学习实变函数的时候并没有弄懂,后来也一直搁着,直到最近认真看了《重温微积分》之后,才有了些感觉。顺便说,齐民友老师的《重温微积分》真的很赞,值得一看。

本是同根生,相煎何太急?

点击阅读全文...