作者归档:老憨

非主流自然语言处理——遗忘算法系列(四):改进TF-IDF权重公式

Deep Learning Specialization on Coursera

一、前言

  前文介绍了利用词库进行分词,本文介绍词库的另一个应用:词权重计算。

二、词权重公式

  1、公式的定义
    定义如下公式,用以计算词的权重:
    权重公式
  2、公式的由来
    在前文中,使用如下公式作为分词的依据:
    公式推导
    任给一个句子或文章,通过对最佳分词方案所对应的公式进行变换,可以得到:
    公式推导
    按前面权重公式的定义,上面的公式可以理解为:一个句子出现的概率对数等于句子中各词的权重之和。
    公式两边同时取负号使权重是个正值。

三、与TF-IDF的关系

  词频、逆文档频率(TF-IDF)在自然语言处理中,应用十分广泛,也是提取关键词的常用方法,公式如下:
  tf-idf
  从形式上看,该公式与我们定义的权重公式很像,而且用途也近似,那么它们之间有没有关系呢?
  答案是肯定的。
  我们知道,IDF是按文档为单位统计的,无论文档的长短,统一都按一篇计数,感觉这个统计的粒度还是比较粗的,有没有办法将文本的长短,这个明显相关的因素也考虑进去呢,让这个公式更加精细些?
  答案也是肯定的。
  文章是由词铺排而成,长短不同,所包含的词的个数也就有多有少。
  我们可以考虑在统计文档个数时,为每个文档引入包含多少个词这样一个权重,以区别长短不同的文档,沿着这个思路,改写一下IDF公式:
  tf-idf
  我们用所有文档中的词做成词库,那么上式中:
  tf-idf
  综合上面的推导过程,我们知道,本文所定义的词权重公式,本质上是tf-idf为长短文档引入权重的加强版,而该公式的应用也极为简单,只需要从词库中读取该词词频、词库总词频即可。
  时间复杂度最快可达O(1)级,比如词库以Hash表存储。
  关于TF-IDF更完整的介绍及主流用法,建议参看阮一峰老师的博文《TF-IDF与余弦相似性的应用(一):自动提取关键词》。

四、公式应用

    词权重用途很广,几乎词袋类算法中,都可以考虑使用。常见的应用有:
     1、关键词抽取、自动标签生成
        作法都很简单,分词后排除停用词,然后按权重值排序,取排在前面的若干个词即可。
     2、文本摘要
        完整的文本摘要功能实现很复杂也很困难,这里所指,仅是简单应用:由前面推导过程中可知,句子的权重等于分词结果各词的权重之和,从而获得句子的权重排序。
     3、相似度计算
        相似度计算,我们将在下一篇文中单独介绍。

五、演示程序

  在演示程序显示词库结果时,是按本文所介绍的权重公式排序的。
  演示程序与词库生成的相同:
  特别感谢:王斌老师指出,本文公式实质上是TF-ICF。

六、联系方式:

  1、QQ:老憨 244589712
  2、邮箱:gzdmcaoyc@163.com

非主流自然语言处理——遗忘算法系列(三):分词

Deep Learning Specialization on Coursera

一、前言

  前面介绍了词库的自动生成的方法,本文介绍如何利用前文所生成的词库进行分词。

二、分词的原理

  分词的原理,可以参看吴军老师《数学之美》中的相关章节,这里摘取Google黑板报版本中的部分:
  分词原理
  从上文中,可以知道分词的任务目标:给出一个句子S,找到一种分词方案,使下面公式中的P(S)最大:
  分词原理
  不过,联合概率求起来很困难,这种情况我们通常作马尔可夫假设,以简化问题,即:任意一个词wi的出现概率只同它前面的词 wi-1 有关。
  关于这个问题,吴军老师讲的深入浅出,整段摘录如下:
  分词原理
  另外,如果我们假设一个词与其他词都不相关,即相互独立时,此时公式最简,如下:
  分词原理
  这个假设分词无关的公式,也是本文所介绍的分词算法所使用的。

三、算法分析

  问:假设分词结果中各词相互无关是否可行?
  答:可行,前提是使用遗忘算法系列(二)中所述方法生成的词库,理由如下:
  分析ICTCLAS广受好评的分词系统的免费版源码,可以发现,在这套由张华平、刘群两位博士所开发分词系统的算法中假设了:分词结果中词只与其前面的一个词有关。
  回忆我们词库生成的过程可以知道,如果相邻的两个词紧密相关,那么这两个词会连为一个粗粒度的词被加入词库中,如:除“清华”、“大学”会是单独的词外,“清华大学”也会是一个词,分词过程中具体选用那种,则由它们的概率来决定。
  也就是说,我们在生成词库的同时,已经隐含的完成了相关性训练。
  关于ICTCLAS源码分析的文章,可以参看吕震宇博文:《天书般的ICTCLAS分词系统代码》。
  问:如何实现分词?
  答:基于前文生成的词库,我们可以假设分词结果相互无关,分词过程就比较简单,使用下面的步骤可以O(N)级时间,单遍扫描完成分词:
  逐字扫描句子,从词库中查出限定字长内,以该字结尾的所有词,分别计算其中的词与该词之前各词的概率乘积,取结果值最大的词,分别缓存下当前字所在位置的最大概率积,以及对应的分词结果。
  重复上面的步骤,直到句子扫描完毕,最后一字位置所得到即为整句分词结果。
  3、算法特点
    3.1、无监督学习;
    3.2、O(N)级时间复杂度;
    3.3、词库自维护,程序可无需人工参与的情况下,自行发现并添加新词、调整词频、清理错词、移除生僻词,保持词典大小适当;
    3.4、领域自适应:领域变化时,词条、词频自适应的随之调整;
    3.5、支持多语种混合分词。

四、演示程序下载

  演示程序与词库生成的相同:

五、联系方式:

  1、QQ:老憨 244589712
  2、邮箱:gzdmcaoyc@163.com

非主流自然语言处理——遗忘算法系列(二):大规模语料词库生成

Deep Learning Specialization on Coursera

一、前言

  本文介绍利用牛顿冷却模拟遗忘降噪,从大规模文本中无监督生成词库的方法。

二、词库生成

    算法分析,先来考虑以下几个问题
    问:目标是从文本中抽取词语,是否可以考虑使用遗忘的方法呢?
    答:可以,词语具备以相对稳定周期重复再现的特征,所以可以考虑使用遗忘的方法。这意味着,我们只需要找一种适当的方法,将句子划分成若干子串,这些子串即为“候选词”。在遗忘的作用下,如果“候选词”会周期性重现,那么它就会被保留在词库中,相反如果只是偶尔或随机出现,则会逐渐被遗忘掉。
    问:那用什么方法来把句子划分成子串比较合适呢?
    答:考察句中任意相邻的两个字,相邻两字有两种可能:要么同属于一个共同的词,要么是两个词的边界。我们都会有这样一种感觉,属于同一个词的相邻两字的“关系”肯定比属于不同词的相邻两字的“关系”要强烈一些。
    数学中并不缺少刻划“关系”的模型,这里我们选择公式简单并且参数容易统计的一种:如果两个字共现的概率大于它们随机排列在一起的概率,那么我们认为这两个字有关,反之则无关。
    如果相邻两字无关,就可以将两字中间断开。逐字扫描句子,如果相邻两字满足下面的公式,则将两字断开,如此可将句子切成若干子串,从而获得“候选词”集,判断公式如下图所示:
    切片公式
    公式中所需的参数可以通过统计获得:遍历一次语料,即可获得公式中所需的“单字的频数”、“相邻两字共现的频数”,以及“所有单字的频数总和”。
    问:如何计算遗忘剩余量?
    答:使用牛顿冷却公式,各参数在遗忘算法中的含义,如下图所示:
    牛顿冷却公式的详情说明,可以参考阮一峰老师的博文《基于用户投票的排名算法(四):牛顿冷却定律》。
    牛顿冷却公式
    问:参数中时间是用现实时间吗,遗忘系数取多少合适呢?
    答:a、关于时间:
      可以使用现实时间,遗忘的发生与现实同步。
      也可以考虑用处理语料中对象的数量来代替,这样仅当有数据处理时,才会发生遗忘。比如按处理的字数为计时单位,人阅读的速度约每秒5至7个字,当然每个人的阅读速度并不相同,这里的参数值要求并不需要特别严格。
      b、遗忘系数可以参考艾宾浩斯曲线中的实验值,如下图(来自互联网)
    艾宾浩斯遗忘曲线
      我们取6天记忆剩余量约为25.4%这个值,按每秒阅读7个字,将其代入牛顿冷却公式可以求得遗忘系数:
    遗忘系数
      注意艾宾浩斯曲线中的每组数值代入公式,所得的系数并不相同,会对词库的最大有效容量产生影响。

二、该算法生成词库的特点

    3.1、无监督学习
    3.2、O(N)级时间复杂度
    3.3、训练、执行为同一过程,可无缝处理流式数据
    3.4、未登录词、新词、登录词没有区别
    3.5、领域自适应:领域变化时,词条、词频自适应的随之调整
    3.6、算法中仅使用到频数这一语言的共性特征,无需对任何字符做特别处理,因此原理上跨语种。
三、词库成熟度
  由于每个词都具备一个相对稳定的重现周期,不难证明,当训练语料达到一定规模后,在遗忘的作用下,每个词的词频在衰减和累加会达到平衡,也即衰减的速度与增加的速度基本一致。成熟的词库,词频的波动相对会比较小,利用这个特征,我们可以衡量词库的成熟程度。
四、源码(C#)、演示程序下载
  使用内附语料(在“可直接运行的演示程序”下可以找到)生成词库效果如下:
  演示程序
五、联系方式:
  1、QQ:老憨 244589712
  2、邮箱:gzdmcaoyc@163.com

非主流自然语言处理——遗忘算法系列(一):算法概述

Deep Learning Specialization on Coursera

一、前言

  这里“遗忘”不是笔误,这个系列要讲的“遗忘算法”,是以牛顿冷却公式模拟遗忘为基础、用于自然语言处理(NLP)的一类方法的统称,而不是大名鼎鼎的“遗传算法”!

  在“遗忘”这条非主流自然语言处理路上,不知不觉已经摸索了三年有余,遗忘算法也算略成体系,虽然仍觉时机未到,还是决定先停一下,将脑中所积梳理成文,交由NLP的同好们点评交流。

二、遗忘算法原理

  能够从未知的事物中发现关联、提炼规律才是真正智能的标志,而遗忘正是使智能生物具备这一能力的工具,也是适应变化的利器,“遗忘”这一颇具负能量特征的家伙是如何实现发现规律这么个神奇魔法的呢?

  让我们从巴甫洛夫的狗说起:狗听到铃声就知道开饭了。

  铃声和开饭之间并不存在必然的联系,我们知道之所以狗会将两者联系在一起,是因为巴甫洛夫有意的将两者一次次在狗那儿重复共现。所以,重复是建立关联的必要条件。

  我们还可以想像,狗在进食的时候听到的声音可能还有鸟叫声、风吹树叶的沙沙声,为什么这些同样具备重复特征声音却没有和开饭建立关系呢?

  细分辨我们不难想到:铃声和开饭之间不仅重复共现,而且这种重复共现还具备一个相对稳定的周期,而其他的那些声音和开饭的共现则是随机的。

  那么遗忘又在其中如何起作用的呢?

    1、所有事物一视同仁的按相同的规律进行遗忘;

    2、偶尔或随机出现的事物因此会随时间而逐渐淡忘;

    3、而具有相对稳定周期重复再现的事物,虽然也按同样的规律遗忘,但由于周期性的得到补充,从而可以动态的保留在记忆中。

  在自然语言处理中,很多对象比如:词、词与词的关联、模板等,都具备按相对稳定重现的特征,因此非常适用遗忘来处理。

三、牛顿冷却公式

  那么,我们用什么来模拟遗忘呢?

  提到遗忘,很自然的会想到艾宾浩斯遗忘曲线,如果这条曲线有个函数形式,那么无疑是模拟遗忘的最佳建模选择。遗憾的是它只是一组离散的实验数据,但至少让我们知道,遗忘是呈指数衰减的。

  另外有一个事实,有的人记性好些,有的人记性则差些,不同人之间的遗忘曲线是不同的,但这并不会从本质上影响不同人对事物的认知,也就是说,如果存在一个遗忘函数,它首先是指数形式的,其次在实用过程中,该函数的系数并不那么重要。

  这提醒我们,可以尝试用一些指数形式的函数来代替遗忘曲线,然后用实践去检验,如果能满足工程实用就很好,这样的函数公式并不难找,比如:退火算法、半衰期公式等。

  有次在阮一峰老师的博客上看关于帖子热度排行的算法时,其中一种方法使用的是牛顿冷却定律,遗忘与冷却有着相似的过程、简洁优美的函数形式、而且参数只与时间相关,这些都让我本能想到,它就是我想要的“遗忘公式”。

  在实践检验中,牛顿冷却公式,确实有效好用,当然,不排除有其他更佳公式。

四、已经实现的功能

  如果把自然语言处理比作从矿砂中淘金子,那么业界主流算法的方向是从矿砂中将金砂挑出来,而遗忘算法的方向则是将砂石筛出去,虽然殊途但同归,所处理的任务也都是主流中所常见。

  本系列文章将逐一讲解遗忘算法如何以O(N)级算法性能实现:

  1、大规模语料词库生成
    1.1、跨语种,算法语种无关,比如:中日韩、少数民族等语种均可支持
    1.2、未登录词发现(只要符合按相对稳定周期性重现的词汇都会被收录)
    1.3、领域自适应,切换不同领域的训练文本时,词条、词频自行调整
    1.4、词典成熟度:可以知道当前语料训练出的词典的成熟程度

  2、分词(基于上述词库技术)
    2.1、成长性分词:用的越多,切的越准
    2.2、词典自维护:切词的同时动态维护词库的词条、词频、登录新词
    2.2、领域自适应、跨语种(继承自词库特性)

  3、词权值计算
    3.1、关键词提取、自动标签
    3.2、文章摘要
    3.3、长、短文本相似度计算
    3.4、主题词集

五、联系方式:

  1、QQ:老憨 244589712

  2、邮箱:gzdmcaoyc@163.com