（计算机软件与理论专业论文）中文命名实体的识别方法研究及其实现.pdf

ab s t r a c t ab s t r a c t n a m e d e n t i ty r e c o g n it i o n i s o n e o f t h e r e s e a r c h f o c u s e s i n n a t u r a l l a n g u a g e p r o c e s s i n g . i t i s u s e d w i d e ly i n i n f o r m a t i o n r e t r i e v a l , i n f o r m a t i o n e x t r a c t i o n a n d m a c h i n e t r a n s l a t i o n . o p p o s i t e t o t h e g r e a t s u c c e s s g a i n e d i n e n g l i s h n a m e d e n t i ty r e c o g n i t i o n , c h i n e s e n a m e d e n t i ty r e c o g n i t i o n s t i l l h a s m a n y p r o b l e m s t o r e s e a r c h t h e m a in p u r p o s e o f t h i s p a p e r i s t o h a v e a f a s t s t e p r e s e a r c h o n c h i n e s e n a m e d e n t i ty r e c o g n i t i o n . m a x i m u m e n t r o p y m o d e l h a s a w i d e u s a g e i n n a t u r a l l a n g u a g e p r o c e s s i n g , a n d a l s o g a i n s g o o d p e r f o rma n c e s . t h i s p a p e r f i r s t d i s c u s s a b o u t h o w t o a p p l y m a x i m u m e n t r o p y m o d e l t o c h i n e s e n a m e d e n t i ty r e c o 列t i o n . t h e n , t h i s p a p e r t a l k s a b o u t t h e i m p l e m e n t a t i o n o f m a x i m u m e n t r o p y mo d e l i n c h i n e s e n a m e d e n t i t y r e c o g n it i o n , in c l u d i n g t h e f e a t u r e s , f e a t u r e s e l e c t i o n , m o d e l t r a in i n g a n d t e s t t e x t d e c o d i n g . a s ma x i m u m e n t r o p y mo d e l n e e d s t o m i n e t r a i n i n g d a t a f o r u s e f u l r u l e s , i t i s r e s t r i c t e d b y t h e t r a i n i n g d a t a , a n d c a n n o t fi n d t h e r u l e s n o t p r e s e n t i n t h e t r a i n i n g d a t a . f o r e x a m p l e , s o m e i m p o r t a n t p h r a s e s m a y r e p e a t m a n y t i m e s i n a d o c u m e n t , a n d s o m e o f t h e s e r e p e a t e d p h r a s e s a r e n a m e d e n t i t i e s . t h i s p a p e r a p p l ie s t h i s r e p e a t e d p h r a s e i n f o r m a t i o n t o c h i n e s e n a m e d e n t i ty r e c o g n i t i o n , a n d c o m b i n e s t h e r e p e a t e d p h r a s e i n f o r m a t i o n a n d m a x i m u m e n t r o p y mo d e l i n t o a h y b r i d m o d e l f o r c h i n e s e n a m e d e n t ity r e c o g n i t i o n . f in a l l y , t h i s p a p e r t e s t s t h i s n e w h y b r i d m o d e l o n t h e d a t a s e t o f m e t - 2 c o n f e r e n c e . t h e t e s t r e s u l t s h o w s t h a t t h i s n e w h y b r i d m o d e l o u t p e r f o r m s t h e s i m p l e x ma x i m u m e n t r o p y mo d e l . k e y wo r d s : c h i n e s e n a m e d e n t i ty r e c o g n i t i o n ; ma x i m u m e n t r o p y ; r e p e a t e d p h r a s e i n f o r m a t i o n ; mu t u a l i n f o r ma t i o n 南 学 学 位 论 文 电 子 版 授 权 使 用 协 宝 义 ( 清将此协议书装订于论文首 页) 论 一文 中 文 i-毛 k t * ij i r 别 巧 1 研 灾 叭实 -,t 系 本 人 在 南开大学工作和学习期间创作完成的作品，并已通过论文答辩 本人系本作品的唯一作者 ( 第一作者)，即著作权人。现本人同意将本作品收 录于 “ 南开大学博硕士学位论文全文数据库”。本人承诺:己 提交的学位论文电子 版与印刷版论文的内容一致，如因不同而引起学术声誉 丘 的损失由木人自负。 本人完全了解 南开大学图书馆关于保存、使用学位论文的管理办法。同意 南开大学图书馆在下述范围内免费使用本人作品的电子版: 本作品呈交当年，在校园网 胜 提供论文目 录检索、文摘浏览以及论文全文部分 浏览服务 ( 论文前1 6 页)。 公开级学位论文全文电子版于提交1 年后， 在校园网上允 许读者浏览并下载全文。 注:本协议书对于 “ 非公开学位论文”在保密期限过后同样适用。 院 系 所 名 称 : a息 牲术 杆 - (! 叱 作 者 签 名 :r ?, 碟 学 号 :0 初3 6 7 日 期 : 2 0 0 7 年夕月2 9日 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定，同意如下 各项内 容: 按照学 校要求提交学位论文的印刷本和电 子版本;学校有权保存学 位论文的印 刷本和电 子版，并采用影印、缩印、扫描、数字化或其它手段保存 论文; 学校有权提供目 录检索以及提供本学位论文全文或者部分的阅 览服务; 学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电 子版; 在 不以 赢利为目 的的 前提下，学校可以适当复制论文的部分或全部内容用于学术 活动。 学 位 论 文 作 者 签 名 : a 宝 琪 2 0 0 7年夕 月聪日 经指导教师同意，本学位论文属于保密，在年解密后适用本授权书。 指导教师签名:学位论文作者签名: 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 内部 5 年 ( 最长5 年，可少于5 年) 秘密*1 0 年 ( 最长 1 0 年，可少于 1 0 年) 机密2 0 年 ( 最长 2 0 年，可少于 2 0 年) 南开大学学位论文原创性声明 本人郑重声明:所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、己 公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均己在文中以明确方式标明。本学 位论文原创性声明的 法律责任由本人承担。 学 位 论 文 作 者 签 名 :昊 雪 敢 2 001年 夕月邓 日 第一章引言 第一章引言 本章主要介绍命名实体识别相关概念， 以 及国内外相关领域的研究现状 ( 英 文命名实体的 识别方法，中 文命名实 体的 识别方 法) 。 最后介绍了本文的具体 工 作和本文的结构。 第一节相关研究背景 随着计算机技术的飞速发展和互联网的普及，人类的知识正以指数级的速 度增长。互联网 无疑是一个人类知 识的巨大海洋. 然而 互联网上的知识并不是 存在于结构化的数据中，绝大多数都是用 h t ml语言描述的半结构化数据，有 的甚至完全是纯文本的形式。如何从这些非结构性数据中抽取出期望的知识， 则是信息抽取的主要工作。 信息抽取的主要工作就是从非结构文本 ( 包括文本，网页等数据)中抽取 出感兴趣的信息。 信息 抽取主要包含有两方面的 工作，一方面就是命名实 体的 识别，另一方面就是识别出这些实体之间的关系. 命名实体 ( n a m e d e n t i t y n e ) 是文本中 基本的 信息单 元， 一般来说， 命名 实体包括下面的几类:人名、地名、组织名、时间、金钱、日期等。 而命名实体识别的工作则是在文本中识别出 这些命名实 体，是一种属于计 算语言学范畴中的任务。 命名实体 识别被广泛应用于下面领域d l , .更准确的机器翻译， 如果没有准确地识别出命名实体，而只是按单个词 来翻译的话，必然翻译的质量会很差 . 书籍的自 动索引 . 新闻网站或 在线杂志可以 把人名， 或公司名 用特殊字体自 动显示出 来 . 作为更复杂的 信息 抽取工 作的必 要的 前期准备 . 更准确的搜索引擎 命名实 体识别 在这些应用中， 一般都处于 其处理流程的 第一个步骤. 命名 实体识别的准确率，很大程度上会影响后面的处理，所以，命名实体识别在应 第一章引言 用中具有很重要的地位。 而且，近些年来，对于命名实体识别的研究得到了广泛的关注，一方面是 因为它的应用及其广泛，另一方面，也是各种相关会议的举行更加推动了相关 研究的开展。 国际上 的关于命名实体识别任务的 会议主要有: m u c - 6 , m u c - 7 , c o nl l - 2 0 0 2 , c o n l l - 2 0 0 3 , m e t - 2等。其中me t - 2会议的任务是针对中文和 日 文的命名实体识别， m e t - 2 会议和以 英文命名实体 识别为任务的mu c - 7 会议 是同步举行的121 。 这些会议 对促进命名实 体识别的研究 起到了巨大的 作用。 第二节英文命名实体识别相关研究 近些年来， 命名实体识别取得了迅速的发展， 尤其是在英文领域，更是 取 得了非常高水平的 研究成果。以c o n l l - 2 0 0 3 会议 的参赛结果来看，参赛的 1 6 对选手中最好的 成绩己 经达到了8 8 . 9 9 % 的准 确度，8 8 . 5 4 %的召回率， 8 8 . 7 6 % 的 f 一 综合值3 1 英文命名实体识别 的研究方法主 要是分 为以 下两 大类: 一类是人工 编写 规则的方法。 基于这 种方 法的系统更多的是依靠领域专家 来人工地编写规则，它 在很大程度上依赖于设计 者的 直觉。基于规则建立的命 名 实 体 识 别 系 统 典 型 的 是 美 国 纽 约大 学 的p ro te u s 命 名 实 体 识 别 系 统 。 这种方法的优点是: 1 . 如果 有足够优秀的语言专家， 就可获得 很复杂的规则， 识别效果就会 很 好。 2 .识别出来的 结果是人工可以 清楚 理解的，明白 为什么该词语会被识别出 来， 便于 通过分析结果来改善系 统。 这种方法的缺点是: 1 .人员成本高，过分 依赖于 语言专家。 2 .不适用于新领域，当移植到其它领域时， 还需要为该新领域重新设 计规 则。 3 .系统的识别能力，跟语言学家的制定规则的能力有关。 4 .有些规则很难用正则表达式或计算机语言来表达。 另一类是基于机器学习的 方法。因 为其利于移植性和便于维护性，基于 机 器学习的命名实体识别方法近些年来得到了 广泛的 关注，是命名实体识别领 域 第一章引言 的研究重点。 主要的 研究方法有:隐藏马 尔可夫模型 ( h i d d e n m a r k o v m o d e l . h m m) 、 和最 大 嫡 模型( m a x i m u m e n t r o p y m e ) 。 把隐藏马尔可夫模型用于 命 名实 体 识别的 相应典型系统是b b n的i d e n t i f i n d e r 系 统5 1 ; 把最大嫡模 型用 于 命 名 实 体 识 别 的 代 表 系 统 则 是 美 国 纽 约 大 学 的m e n e 系 统 16 1 基于机器学习的命名实体识别系统的优点是: 1 .不像基于规则的系统那样需要大量的语言学家的参与， 大大节省了成本。 2 . 具有更好的鲁棒性，更容易移植到其它领域. 3 .通常能发现一些语言专家发现不了的规则。 该方法的缺点则是: 1 .需要大量的人工标注好的训练样本集， 这需要大量的工作。 2 .当训练样本集不充足的时候，系统的表现可能会很差. 3 . 虽然基于机器学习的系统更容易开发一些，但是，这些系统的输出结果 是很难被人所读懂的。这就意味着，相对更难通过分析输出结果来提高 系统表现。 另外，值得一提的是，这个领域研究的一种趋势是几种方法的结合，从 c o n l l - 2 0 0 3 会议的总结上来看， 可以 发现结合不同方法的复合型系统能取得更 优 秀 的 识 别 表 现 3 1 。 第三节中文命名实休识别相关研究 与英文命名实体识别领域的最近的飞速发展，和其取得的成绩相比，中文 的命名实体识别还只是处于起步阶段，还很不成熟. 分析其原因，发现中文和英文在语言自 身方面有很大的区别，中文比英文 在结构和语法方面都要复杂一些。就命名实体识别领域，主要表现为: i . 在英文的句子中，单词与单词之间是由空格分隔的，单词之间有明 确的 界限。而在中文的句子中，并没有空格来分隔，单词之间没有明 确的界 限，而且甚至，中文中都没有单词这个明确的概念。所以，中文在处理 的时候要比英语做更多的工作。 2 .在英文中，有大小写的概念， 尤其是在表达一些命名实体的时候，英文 中通常会把命名实体名字中的所有首字母都大写。而中文中则没有这些 大小写形式，也没有明显的命名实体的提示信息。 第一章引言 3 ， 中文的命名实体一般都比 英文的长，所以处理的时候，需要考虑的上下 文环境就需要比英文时候的更长。 因为以 上的因素， 可以 说，中文的 命名实 体识别比 英文的复杂度更高一 些。 r a n s u n 等基于类别的语言模型用到了中文命名实体识别中， 并加入了一些 启发性 信息 来改 进模型7 l 。 参考文 献18 中 则 把一个基于规则的 知识表达工具 i n f o m a p 融 入 到 最 大 嫡框架me 中 ， 构 成了 一 个复 合的 系 统。 参 考 文 献 19 1 中 则 把 基于 代 理 ( a g e n t ) 的 方 法引 入了 命 名 实 体识 别 领域， 采用多 代理 协商 的 方 式 来 解决 命 名实 体识别问 题。 参考文献 11 0 1 中 将s v m和最大嫡相结合 来对中 文组 织名 进行 识 别， 采 取了 后界 判断 和 前 部 标 注 相 结 合的 方 式。 参考 文 献 1 1 12 1 则 分别 把 最大嫡模型应用于中文命名实体识别和中文人名识别. 第四节本文的来源和创新 从c o n l l - 2 0 0 3 会议的报告来看， 最大嫡模型相对更适合于处理命名实体识 别问 题， 在参赛的1 6 对选手中，有5 对选手使用了最大嫡模型。而且从竞赛的 结果来看， 英文的命名实体识别竞赛的前三名和德语的命名实体识别竞赛的前 两名都采用了最大嫡的方法。所以本文首先选用了最大嫡模型来构成本文的中 文命名实体识别系统的一部分，在本文中详细探讨了怎样把最大嫡模型用在中 文的命名实体识别中。虽然国内己 经有人将最大嫡模型用于中文的命名实体识 别 1 1 0 1 1 1 1 12 1 ， 但是本文的创新主 要是 将词 语重 现信息结合最大嫡 模型而 形成的 复 合方法，并不是单一的使用最大嫡模型;而且本文更加深入的探讨了 如何在实 际中实现最大嫡模型。 另外，当考虑是否采用中文分词和中文词性标示系统时， 本文首先考虑了 下面三方面原因:一、由于中文分词技术，和中文词性标示技术还不是非常成 熟，如果基于这些技术，则这些步骤中产生的错误，必然会影响到后续步骤处 理的准确度。二、也由于中文的分词系统和词性标示系统，或相关的标示好的 语料库还不是很多，尤其是可以免费获得的高质量的资源就更少了，严重限制 了采用这些技术的可能。三、 对于网上可以找的分词系统，和词性标识系统， 比 如 : 比 较 著 名的 计算 所汉 语 词 法 分 析 系 统i c t c l a s 1 ， 本身己 经 融 入了 多 种 功能，包括有:中文分词、词性标注、命名实体识别。如果本文原型系统中使 用这些结果来做预处理的话，就体现不出本文自己的工作了。 第一章引言 所以，本文尽量避开了中文分词、和中文词性标示的操作，而采用了一种 类似的非常简单的分词操作，只是对那些出现在本文自己定义的词典中的词语 ( 词典参见4 .2 节) 进行分词。 但对于没有出 现在词典中的其它汉字， 本文则将 每一个汉字当作一个词语来处理。本文中的分词操作并不是一般意义上的把每 一个句子的每一个可能的词语都分出来，而只是为了后面的命名实体识别时能 减小搜索空间。而对于中文词性标示，本文的系统则没有利用它。 在对基于机器学习的方法进行分析的时候，本文发现对于机器学习系统来 说， 如果训练样本集中并未发现相关的规律，则当进行测试样本标注操作时， 就会漏掉测试文本所特有的一些信息。比如:一般在一篇文档中，有些组织名、 人名、地名等信息会重复出现，比如下面的这段文字: “ 美国摩托罗拉公司招聘高级业务经理. 美国摩托罗拉公司创立于1 9 2 8 年， 是提供集成通信解决方案和嵌入式电子解决方案的全球领导者。 ” “ 美国摩托罗拉公司”在这两句话中就出现了两次。如果一篇文档的长度 很长， 那么，这种重复出现的复合词就会更多。本文就是将这种词语重复出 现 的信息 ( 以下简称词语重现信息) ，应用到中文命名实体的识别上。本文的处理 思路是将这种词语重现信息结合到最大嫡模型中，以补充一些最大嫡模型所不 能发现的信息。两种方法形成的复合原型系统，一方面利用训练样本集中的规 律来发现命名实体 ( 最大嫡模型) ，另一方面可利用当前测试文本中的词语重现 信息来发现命名实体，从而使系统达到更好的识别表现. 另外，本文对中文命名实体识别的 研究对象主要有:人名、 地名和组织名。 而对于时间， 金钱，日 期这些命名实体，因为其结构比较简单，可以用自 动机 来实现，所以本文中没有对它们进行研究. 本文的主要创新如下: 将词语重现信息用于进行中文命名实体识别， 与最大嫡模型相结合来提 高标注结果的准确度。 从特征、 特征选择、 模型训练和测试文本标注几个方面， 详细的探讨了 如何将最大嫡模型应用于中文命名实体识别。 第五节论文的结构 第一章引言 本文的结构如下: 第一章 前言: 介绍了 命名实体识别的 背景， 英文命名实体识别的 相关研究， 和中文命名实体识别的相关研究，并提出了本文的算法的思想来源和创新，最 后描述了本文的结构. 第二章 最大嫡模型: 对最大墒原理进 行了 介绍，以 及相关的一些 概念。然 后简单介绍了一下最大嫡模型的参数估计和最大嫡模型的优点。 第 三章 词语重现信息: 对如何利用词 语重复出现的 这种信息来进行中文 命名实体识别进行了探讨. 第四章原型系统架构:描述了本文原型系统的系统架构。 第五章 相关实验:从特征出现次数阀值的选择， 模型训练的 迭代次数， 词语重现信息的利用几个角度，进行了实验及分析. 第六章总结与展望:在总结本文工作的基础上，对未来的研究方向作了 进一步的展望。 第二章 最大 嫡模型 第二章最大嫡模型 信息论中的最大嫡原理是 首先由e . t . j a y n e s 在 1 9 5 7 年提出来的。 最大 嫡原 理指出，当需要对某一个随机事件的概率分布进行预测的时候，预测应该在满 足所有己知的约束条件的前提下，对任何未知的情况都不做任何主观假设.在 这 种情况 下， 概率分布最均匀， 预测的风险最小。因为这时概率分布的信息嫡 最大，所以这种模型被称为 “ 最大嫡模型” 。 最大 嫡模型最早由a d a m l . b e r g e r 等人在 1 9 %年引入到了自 然语言处 理领 域 1 4 1 。从那以后最大嫡原理 便在自 然语言处理领域得到了 广泛的关注，被用于 自 然语言处 理领域的各 个方面 1 4 1 5 1 。 从 c o n l l - 2 0 0 3 会议的 参赛结果来看， 最 大嫡模型取得了很好的成绩3 1 第一节基本概念 本节将介 绍最大嫡模型中的 几个最基本概念:特征、 约束、参数，以 及它 们的理 论基础d 4 1 p 5 1 p 1 2 . 1 . 1 问题的描述 自 然语言 处理中的很多问 题，都可以 描述为一 种分类问 题:通过观察当前 的 某些上下文环境x e x， 来预测正确的语言学类别y ( = y. 也就是要构造一个 分 类器x - 3 . y 。 这个分类器可以 通过条件概率分布a y i x ) 来表示，即 在已 知上 下文环 境x 的 条件下，输出 为类别y 的 概率。 这个条件概率分布函数爪川x ) 就 是解决问题的 一个模型 ( m o d e l ) . 本文的中文命名实体识别问题可以 描述为 :在一篇文档中， 找出 其中的人 名、地名、组织名。为了使这个问题能够表示为一个分类问题，本文首先定义 分类器的输出， 即y ， 对于要预 测的 每一个命名实体类别v ( v可以为人名、 地 名 或 者 组 织 名) ， 定 义 四 个类 别 ， 分 别为 : v开 始， v继 续， v结 束 ， v唯 一 拿 地 名 举 例， 如 果当 前 词 语自 身 构 成了 整 个 地 名， 则 它的 类别 输出 为“ 地 名 _ 唯 一” ， 如果当前 词语只是整 个地名的一部分，则 根据当前词 语在整个地名中的 位 置来 输出 它的 类别:如果当前词 语是整个地名的开始词 语时，则 输出为 “ 地 名_ 第二 章 最大 嫡模型 开 始” ; 如果是整个地名的 结束单 词时，则 输出为 “ 地 名_ 结束” :而如果位于中 间 位置时， 则输出 为“ 地名 继续” 。 除了 这 1 2 个输出 外， 外加一 个类别“ o t h e r , 表 示当前词语不属于上面的1 2 个类别中的任意一个。然后， 定义x 为当前 词语 的上下文 环境，通常来 说，x 的 上下文环境就是和它在同 一个句子的其它词语。 所以，问题就转化为: 在测试 文档中 ，对于 每一个词语， 根据其所在的上 下文环境x ，输出当 前词语的 命名实 体类别y ( y 为 上面1 3 个类别中的一个) . 2 . 1 . 2 训练样本集 为了能了 解某个随机过程，需要首先收集关于这个随机过程的大量的 训练 样 本(x r. y l ) ( x v y x ) ， (x ,y ) 。 这 些样 本 一 般 来自 于 历史 真 实 数 据， 或 者是由该领域专家人工标示好的， 有了 这些训练样本， 就可以 计算出 每一个( x , y ) 的经 验概率分布p ( x , y ) 了: c _ .， “._ _二_ . _、 二。 ， _ p ( x , y ) ， 份， ( 其甲，q。 代表x 和y 共问出 现的7 x w) 刀, 2 . 1 .3 特征 对一个随机过程的训练样本集的研究，实际上是为了 能利用这个样本集里 的信息，来对这个随机过程以 后的行为 进行预测。 也就是预测当 输入的上下文 环 境 为x 时 ， 随 机 事 件输 出 为 类 别y 的 概 率是 多 少 。 这 就是 寻 找 一 个 能 描 述 这 个 样 本 集的 模 型抓 y l x ) 构 造 这 个 模型 的 最 基 本 单元 是 训 练 样 本 集 上 的 一系 列 统 计值。 举例来说，在进行命名实体识别的时候， 如果当 前单词是 “ 公司” ，那么当 前 单词的类别输出 很可能是“ 组织名 _ 结束” 。 为了能表示这样一个事实:当 前单词为， 公司”时， 类别输出为: “ 组织名 结束” 。本文引 进了下面的二 值指示函 数: i f y = .组 织 名 _ 结 束 “ a n d 当 前 词 语 为 公司 其他情况 i工u zlesse - 、，产 y 了 x 了t毛 f 这个指示函数f在训练样本集中的数学期望值， 正是 本文感兴趣的 那些统 计值之一。 指示函数f 在训练 样本中的经验数学期望值为: 第二章 最大墒模型 p ( f ) 二 艺f ( x , y )p ( x , y ) ( 2 . 1 ) 这些二值的 指示函 数f 被 称为 特征函 数 ( f e a t u r e f u n c t i o n ) ， 或简称为 特征 ( f e a t u r e ) . 2 . 1 .4 约束 当发现一些统计值比 较有用后， 可以 通过使统计模型p ( y l x ) 在以 后的 预测 过 程中， 来遵循这些统计 值， 从而 达到 遵循训练样本 集的目 的。 则函 数f 关于 统计模型的数学期望值为: a f ) 二 艺p(x)ay i x ) f ( x , y ) ( 2 .2 ) 其中 ， p ( x ) 是x 在训 练 样 本中 的 经 验概 率 分 布。 为了 使 得 统 计 模型ay i x ) 遵 循 这 些 统 计 值， 限 制 这 个 数 学 期 望 值a d与f 在 训 练 样 本中 的 经 验数 学期望 值 一样，也就是: p ( f ) 二 p u) ( 2 . 3 ) 艺p(x)ay i x ) f ( x , y ) = 艺p ( x , y ) f ( x , y ) ( 2 . 4 ) 公 式 ( 2 .3 ) 在 最大 嫡 模 型 中 被 称为 约束 等 式( c o n s t r a in t e q u a t io n ) ， 或者 简 称为 约束 ( c o n s t r a i n t ) 。 通过 使得统计 模型a y i x ) 遵守 ( 2 . 3 ) 的 约束， 去除 了那些不符合训练样本集的模型，减少了合法的统计模型的数量。 2 . 1 . 5 最大嫡原理 假设已 经得出 了n 个 特 征函 数关 ， 通过 使得 统 计 模 型 遵 循 所 有的 公式( 2 .3 ) 中 的 约束， 可以 得到一系列 符合 这些限 制的 概率 模型p ， 记 这些符合约束的 所 有模型的集合为c。一般来说c中有无数个元素，怎样选择一个最能代表训练 样本集的那个概率模型，就是最大嫡原理的应用了。 关于条 件概率分 布ay l x ) 的 条件嫡的 数学 表达为: h ( p ) 二 一 艺p ( x ) p ( y i x ) lo g a y i x ) ( 2 . 5 ) 最大墒原理就是:在由所有符合约束的概率分布构成的集合c中，选择那 第二章 最大嫡模型 个使得嫡h ( p ) 的取值最大的概率分布: p = a r g m a x h ( p ) 户 以: ( 2 石) 通过证明，可以知道在约束形成的 集合c中， 有且只有一个概率模型p 使 得嫡h ( p ) 最大。 2 . 1 .6 最大嫡原理的参数形式 最大 嫡原理实 质上 提出了 一 个约束 优化问 题: 找出 使得a h ( p ) 最大的 那 个 p . e c.但是不幸的是对于 ( 2 . 6 ) 形式的 最大嫡问 题，并不能找出明确的解决 方法， 所以，引入了下面这个间接的解决方法. 这个方法应用了约束优化理论 中的拉格朗日乘子的方法。 1 . 把原始的 约束优 化问 题 ( 2 .6 ) 称为 原问 题 ( p r im a l p r o b l e m ) . 2 . 对 于 每一 个 特征厂 ， 引 进一 个参 数a( 拉 格朗日 乘 子) ， 并定 义 拉格朗日 函数a ( p , 幻为: a ( p , a ) 二 h ( p ) 十 艺a ( p ( f ,) 一 xu, ) ( 2 . 7 ) 3 .固定兄 不变，计算拉格朗日函数a ( p , a ) 对于所有概率模型 最 大 值。 p * 为a ( p , a ) 取得 最 大 值时 的p 值， 而 p ( a ) 则为 值: p 的 无约束的 a ( p , 幻的最大 p x = a r g m a x a ( p , a ) ( 2 名) 甲 ( 几 ) 二 a ( 八， 又 ) 4 ( 幻被称为是对偶函 数 确的得到: ( 2 .4 ) ( d u a l f u n c t i o n ) . p x 和t ( a ) 都可以 通过计算来明 p a y i x ) y ( a ) = 一 z a ( x ) i p ( x ) e x p ( 艺a ,f ( x , y ) ) lo g z , ( x ) + 艺 a ,p ( p ( 2 . 1 0 ) ( 2 . 1 1 ) 其中，z x ( x ) 是一个规范化因子，使得满足概率和为 1这个限制，即 艺 y p , ( y i x ) 一 1 第二章 最大嫡模型 z ( x ) = 艺 e x p ( 艺a f ( x y ) ) ( 2 . 1 2 ) 4 .最后，提出了一个对偶优化问题:找到 .i = a r g m a x 甲 ( 几 ) ( 2 . 1 3 ) 拉格朗日乘子理论中的k u h n - t u c k e r 定理指出， 在一定的假设条件下， 原问 题 ( 2 .6 ) 和对偶问题 ( 2 . 1 3 ) 是非常相关的。 也就是说当计算出对偶问题 ( 2 . 1 3 ) 的厂以 后 ， 由( 2 . 1 0 ) 求 出 的p a . 就 是 原 问 题( 2 .6 ) 的 解。 至此，最大嫡问题可以通过其对偶的参数形式进行解决。 第二节参数估计 参数估计的过程， 就是计算每一个特征f的参数厂的过程。常见的参数算 法有: 由 d a r r o c h和 r a t c l i ff在 1 9 7 2年提出来的 g i s ( g e n e r a l i z e d i t e r a t i v e s c a l in g ) 算法0 1 1 6 1 在g i s 基 础 一 进 行 改 进的i i s ( i m p r o v e d i te r a t i v e s c a li n g ) 算 法 1 n l - b f g s 优化算法 ( l i m i t e d - m e m o ry v a r i a b l e m e t r i c ) a卜 m a l o u f 在2 0 0 2 年 对常见的最大嫡参 数 估计 算法进行了比 较测试0 8 1 在本文所使用的最大嫡工具包中，包含有 g i s和 l - b f g s两种参数估计方 法0 9 1 第三节最大嫡模型的优点 最大 嫡模型的 优点主要有: 1 1 5 1 1 .准确率高， 在自 然语言处理领域， 最大嫡模型被广泛的应用于解决各种问题， 比如:单词词性标示、 句子边界检查、 语法树构建、命名实体识别等问题。 而且在这些领域都有很好的表现。 2 .最大嫡模型的特征的建立不需要太多的语言学知识，一般只需要对它的上下 文环境问一些基本的问题即可.所以 最大嫡的 特征更加容易指定，并且更加 容易移植到其它领域。 3 .软件的可重用性，最大嫡模型的一般性，允许实验者把同样的一个参数估计 第二章最大嫡模型 工具包用于不同的任务。参数估计部分的代码是独立于具体任务的。本文中 就使用了一个最大嫡工具包来进行参数估计工作. 第三章词语重现信息 第三章词语重现信息 在同一篇文章中，有的词语会在文章中出现多次，这种词语重复出现的信 息，通常可以用来发现文章中的一些特殊规律。比如:通过对训练样本的观察， 会发现经常有一些重要的命名实体会重复的出 现，比如上一章中提到的例子: “ 美国 摩托罗拉公司招聘高级业务 经理。 美国摩托罗拉公司创立于1 9 2 8 年， 是提供集成通信解决方案和嵌入式电子解决方案的全球领导者。 ” 这篇文章是一篇招聘信息，文章中的招聘公司 “ 美国摩托罗拉公司”很有 可能会在文章中出现多次。但是，开始的时候， 并不知道 “ 美国摩托罗拉公司” 是一个词语， 而只能是以每一个汉字作为一个单元，一个一个的来处理。于是 便有以下的问题: 如何发现重复多次的复合词? 怎么判断这些复合词的各个构成部分的相关程度? 怎么判断这些复合词是独立的词，而不是另一个复合词的一部分? 发现了重复的复合词以后，如何判断它是否是一个命名实体? 本章的下面各节将一一回答这些问题。 第一节 基于a p r i o r i 改进算法的频繁复合词语发现 通过观察，本文发现查找重复出 现的 复合词的过程和数据挖掘中的关联规 则的发现比 较类似; 数据挖掘中的关联规则挖掘是去发现大量数据中项集之间的有趣的关联或 相关联系。比 如， 购物篮分析就是来发现顾客会经常同时购买哪些商品 2 0 1 而查找重复出现的复合词，则是找出那些频繁出现在一起的汉字，和关联 规则挖掘不同的地方是，这些汉字与汉字之间是有顺序的，只有顺序完全一致， 刁 能当作频繁复合词。 在关联规则挖掘中， a p i i o ri算法是一 种最有影响的挖掘布尔关联规则频繁 集的 算 法。 a p ri o ri 算法使用了 一 种逐 层搜索的 迭代方法， k 一 项 集用于 搜 索 ( k + l ) - 项集。 a p ri o ri算法给予下面 这种性质: 频繁 项集的 所有非空子集都 必 须也是 频 繁的2 0 第三章 词语重现信息 而在查找频繁复合词的时候，同样有类似的一种性质:在一篇文章中，一 个m个汉字的序列的出现次数，受限于它的每一个子序列的出现次数。于是， 本 文中 采 用了 参 考 文 献 2 11 中 提出 的 基 于a p r io r i 算 法 的 一 种高 效 率 的 、 改 进 的 实 现方法。 这种改进的算法基于下面这个限制: 对于n 个单词的序列， 只有它的前n - 1 个单词组成的序列， 和后n - 1 个单词 组成的 序列的出 现次数都大于一定的阀 值的时候， 才被处理， 否则， 则略过它. 首 先， 该 算 法需 要 先定 义一 个m i n f r e q u e n c y 一 般 为2 ) 阀 值。 然后，这个算法遍历一遍整个文本，并且这个算法只需要遍历一遍。遍历 时，除了记 录每一个单词的出现次数外， 这个算法还记录了 这个单词在文章中 出现的 所有位置 ( 比如:出现在第几行，和在这一行的第几个位置) 。当记录完 这个信息后， n 十1 个单词的序列可以 通过所以筛选后的n 个单词的序列的集合 来计算: ( 只 有大于m i n f r e q u e n c y 的 序列 才 会经过筛选) ， 过程如下: 1 .找 到 相 交的 两个n 长 度的 单 词 序列 . 比 如: 序列a = x z - 1 ， 而b . = z _ ,y 这两个序列相交，因为他们有公共部分。 2 .对于1 中的每一对相交的单词序列。 计算它们的位置的交集。 这个交集 定 义为: 在这个交 集中 的 每一 个 元素， 如果第 一 个序列a出 现 在文 档 的a 行b 位置， 则b会出 现 在a 行b 十 1 位 置。 也 就是 计算由a和b构 成 的 序列c 十 ， = x z . _ ,y出 现 的 所 有 位置。 3 .在由 第2 步计算出来的所有n +1 长度的序列中，忽略掉出现频率小于 m in f r e q u e n c y 的 序 列 . 持续上面的步骤， 直到不能 再产生任何n 十 1 长度的 序列为止。 ( 详细算法， 参考本文4 . 5 . 1 节) 经过上面步骤以后，将会把所有重复的复合词产生出 来，但是这些复合词 中有很大部分并没有意义，如何筛选则是下面两节的内容。 第二节 基于交互信息的复合词筛选 词语与词语的相关程度可以用信息理论中的交互信息 ( mu t u a l i n f o r m a t i o n ) 来衡量。 根 据f a n 。 在1 9 6 1 年的定 义: 如果 两 个点( 或单词) ，x 和y ，有 概率 p ( x ) 和p ( y ) 。 则 它 们的 交互 信 息m i ( x , y ) 可以 表 达为 : 第三章词语重现信息 m i ( x , y ) = la gax , y ) p ( x ) p 沙) 如 果 x 和 y 之 间 有 真 正 的 关 联 ， 则 e ,4 f7 的 联 合 概 率 a x , y ) 会 比 p ( x ) . p ( y ) 要 大得多，因此会有m i ( x , y ) 0 ，如果x 和y 之间没有明显的关系，则 a x , y ) 二 p ( x ) p 。 ) ， 于是 有m i ( x , y ) 二 0 。 如果x 和y 之间 是互补分 布， 则 会使 得 p ( x , y ) 比 p ( x ) p ( y ) 小 很 多 ， 于 是 m i (x , y ) 0 0 22 1 在 一 篇 文 档 中 ， 对 于 单 词 二 和 y 的 概 率 p ( x ) 和 p ( y ) 是 以 其 在 文 档 中 的 出 现 频率来衡量的，即用其出现的次数除以文档的总词数: p ( x ) =p ( y ) =加 9 ( y ) n ,_ , 则单词x 和y 之间的交互信息可以表示为: m i (x ,y ) = lo g 粤 乌 共= lo g pi x ) pi y i n ,o a , 加9 ( x , y ) 户e 9 ( x ) 夕e 9 ( y ) 有了词语相关度的衡量标准，就可以对第一节中抽取出来的频繁复合词进 行筛选了。只保留那些子词语之间交互信息值高的复合词，而对于那些子词语 之间交互信息值比较低的复合词，说明这些子词语并不是总是一起出 现， 这些 子词语在文档中的其它地方还单独出现了，所以，这个复合词可能并不是一个 完整的意思。 举例来说: “ 他是”这个复合词， 可能在文档中出 现了多次，但是这个词的 两个子词语 “ 他” 和 “ 是” 之间的关联度 ( 交互信息值) 并不高，因为 “ 他” 和“ 是” 还出现在了文档的其它地方， 比 如: “ 他说” ， 比如: “ 公司是” ， 所以，可以根据交互信息把这类的复合词去掉。 第三节基于覆盖度的复合词筛选 上节中的基于交互信息的复合词筛选，去掉了一些子词语相关度不高的复 合词。但是还有另外一类复合词，它们的子词语相关度很高，但它们本身仍不 能构成复合词，因为它们可能只是其它复合词的一部分。比如:本章例子中的 “ 摩托罗”这个复合词，在例子中也出现了两次，而且它的子词语的相关度很 高 ( 都是在一起出现的) 。但是它不应该算是一个完整的复合词。因为它是属于 第三章词语重现信息 更高层词 “ 摩托罗拉”的一部分。 对于 抽 取出 来的k 长 度的 复 合 词人， 定 义由 其作 为 子词 语 而 构成的k + l 长 度的复合词为它的父复合词。然后，就可以引入一个覆盖度的衡量值: i - e r t c o v e r a g e ( 凡) ， 如 果 把 在人的 父复 合 词 中 ， 出 现 频 率 最高的 那 个 父复 合 词 的出 现次数记为- a x f r e q ( p a r e n t s ( a , ) ) ， 则 i n v e r t c o