词汇链相关概念及常用算法学习篇

1.  词汇链的基础概念

2.  WordNet

3.  传统词汇链构造方法

       词汇链可以用无向带权图G(V,E)来表示,其中:(1)V为顶点包含词汇及其语义信息,语义信息由同义词集表示;(2)E表示边集,边表示顶点间的语义关系;(3) 若顶点u与v存在语义关系,当且仅当存在边e=(u,v),同时e还附带一个权值,表示具体的语义关系。词汇链构造算法就是要构造词汇链的图表示结构.

       WordNet是由美国由美国普林斯顿大学心理学家、语言学家们共同研发的在线词汇参考系统,是传统的词典信息与现代计算机技术以及心理语言学的研究成果有机结合的产物。最显著的特征就是它是以单词的含义而不是单词的拼写形式来组织词汇信息的。WordNet包含4种开放词类：名词、动词、形容词和副词。名词在词典存储中是按主题的等级层次组织的,动词按各种搭配关系来组织,形容词和副词以N维超空间组织。

       同义词集由一组相关的同义词组成,同义词集是对它所包含词语的词义的一种表示方式。如果一个词语出现在多个同义词集中,则这个词语有多个词义,并且它出现的每一个同义词集表示它的一种词义。

      WordNet的基本单元是同义词集（Synset），同义词集正是WordNet用来表示词义的。例如，WordNet中的关于board两个同义词集：

       Synset1：{board,plank,(a stout  length of sawn timber）}

       Synset2:{board, committee , (a group with supervisory powers)}

       注:圆括号中的是该同义词集的定义.

       这表示，Synset1是board的一种词义，即a stout  length of sawn timber，结实长板的意思；Synset2是board的另一种词义：a group with supervisory powers，管理委员会的意思。plank与board是同义词，都含有长板的意思，而committee与board也是同义词，都含有管理委员会的意思。

         同义词集合之间是以一定数量的关系类型相关联的,如上下位关系、整体部分关系、继承关系等。         目前,利用WordNet计算词汇间语义关系都是针对名词的。在WordNet中,名词是按照等级层次组织的,所有的名词同义词集根据上下位关系组成一棵层次树。WordNet中的名词关系主要有以下三种关系：（1）上下位关系,它是一种基于词位对的有限等级,在这种词位对中一个词位是另一个词位的次类；（2）整体部分关系,表示词语间组成与被组成的关系；（3）反义关系,表示词语词义相反。

       词汇链构造算法实际上是为文本构造图型的词汇链数据结构,它需要完成两部分工作:(1)创建顶点。顶点关键字是词语的字符串表示,顶点还应包含词语的词义信息,用中的同义词集表示,因此词汇链算法同时应该为词语选择词义。(2)创建边。边表示词语间的词义关系,因此词汇链还需计算词语间的词义关系。值得注意的是,最终的词汇链结果中将包含若干条词汇链,每一条链代表着一个文本的主题,这也是为什么词汇链可以用于分析文本主题结构的原因。在词汇链算法中,我们通常会提到候选词语集及当前词语的概念.

候选词语集：它是指词汇链的处理对象,是一系列词语的集合。它是通过对文本进行预处理,抽取出其中的名词而组成的。用符号WS{w1,w2,...,wn}表示。也称WS为wi的上下文。

当前词语：指算法正在处理的词语，用符号W表示。

       超强关联：指两个词语完全相同。

       强关联：可以分为三种情况：（1）两个词共同出现在同一个同义词集中；（2）两个词的同义词集中的某两个集合存在着             某 种直接的语义关系同义、反义、上下位等；（3）如果有一个是短语或是复合词,而另一个词的某个同义词集中的词就包含         在短语或是复合词中,在这种关系中我们并不考虑这种包含是一种什么样的关系。

       中等关联：当在WordNet中存在着一种路径连接着两个词，两个词间距设定为一个窗口,一般取三个句子,并且这种路径的长           度  通常限制在一之间,如果不在这个范围之内就不是这种关系了。

       词汇链构造算法需要为词语选择一条合适的链,选择的标准就是与该词语的语义关系最强的词汇链,而那个拥有最强语义关系的词义就被选为该词的词义。常见的词汇链的构造算法有两种：Hirst算法和Barzilay算法。

Hirst算法采用“贪心”的策略,每一步根据已处理词的词义为当前词语选择一条词义关系最密切的链,将该词加入该链,并选择导致发生最密切关系的词义作为该词的词义,加入该链后,同时计算该词与其他顶点间的语义关系,在这个算法中,词义一经确定,就不再改变。算法具体步骤如下：

（1）对文本进行切分,取文本的名词集合作为候选词语集WS{w1,w2,...,wn}；

（2）初始化词汇链集，初始集为空，用词表示。

（3）顺序处理每个词语，设当前词语为W.

       若chains非空，chains={chain1，chain2，...，chainm}.计算W与chains中所有chain的语义关系，设W与chaini之间的语义关系为chains中最强，且此时W所取得词义为Syn，则在chaini中加新的顶点（W，Syn），同时计算顶点（W，Syn）与chaini其他顶点间的语义关系，并将语义关系的值保存在边中。 若chains为空,或者如果该词语与任何词汇链都不存在语义关系,则新建一条词汇链,该词汇链仅包含当前词语。

       Barzilay算法认为采用贪心算法,容易导致词义选择的错误,影响对文本的主题分析,进而影响文摘的质量,因此他提出了新的算法。一该算法的思想就是考虑词语所有的词义,根据一定的规则确定一种最合适的解释,而每一种解释都对应着一种词汇链,此算法考虑词语词义的所有可能的组合,并在全局范围内选优。       对于候选词语集WS{w1,w2,...,wn},每个词有若干词义,为每个词语选择一个确定的词义,相当为这个词集选择一个解释。Barzilay算法,考虑了所有可能的解释,并根据一定的标准,在整个上下文内,为这个词集选择一个最优的解释。解释与词汇链之间存在一一对应的关系。Barzilay算法用组件来表示一个解释以及其所对应的词汇链。算法每处理一个词语就用当前词语的所有词义扩展当前的所有组件,当最终所有的组件都被构造出来之后,选择组件中词汇链的边数最多的链为最终的结果。Barzilay词汇链构造算法步骤如下：

（1）对文本进行切分,取文本的名词集合作为候选词语集WS{w1,w2,...,wn}；

（2）顺序处理每个词语，设当前词语为W。若W为第一个词，则初始化组件集合CS，此时CS集合中的每一个组件包含该词的一个词义。否则，设W的词义集合为S{syn1,syn2,...,synm}，用S扩展CS中的每个组件.

（3）当所有的词语处理完后,计算组件的分数,组件的分数等于组件中词汇链的边数,取分数最高的组件作为最后的结果。

      组件的数目是词的数目的指数函数,如果将所有的组件都构造出来,最终的组件的数量可能过于巨大,因此在构造的过程中,可以对组件进行适当的裁剪,即时去除不合适的组件,从而降低处理的空间