（计算机应用技术专业论文）大规模网页中双语命名实体挖掘的研究与实现.pdf

人连理i ：人学硕十学位论文 摘要 大规模的双语命名实体库可以有效的改进机器翻译、跨语言检索等系统的性能。因 而f i i f 人提出了很多抓取双语命名实体的方法。早期的方法主要是从平行语料中进行抽 取，这类方法存在规模不足、领域局限、不能很好的处理新词等问题。随着互联网的飞 速发展，大量的网页包含了双语命名实体。并且由于互联网自身的多样性和实时性，以 及互联网上的双语命名实体覆盖面非常广泛，而且包含了大量的新词。因此，从互联网 上抽取双语命名实体己成为当今信息抽取领域罩的一个研究热点。 本文提出了一个从大规模网页中抽取双语命名实体的方法。方法主要利用了大规模 网页中的冗余信息。首先从大规模网页中抽取符合括弧模式的双语对：再利用中文分词 与后缀树结合的方法抽取候选互译对；之后利用基于s v m 的分类模型去判断候选互译 对是否为正确的双语命名实体；最后利用一套过滤算法对得到的双语命名实体进行有效 的过滤；最终得到正确率较高的双语命名实体集合。 本文设计和实现了基于上述方法的双语命名实体抽取系统，系统的输入是一个大规 模的网页集，集合中所有的网页均为中文网页；输出是中英文的双语命名实体集合。系 统分为4 个模块：( 1 ) 双语对抽取模块：( 2 ) 候选互译对抽取模块；( 3 ) 双语命名实体对 齐模块；( 4 ) 噪音过滤模块。双语对抽取模块从大规模网页中抽取符合括弧模式的双语 对，并对抽取到的双语对进行噪音过滤、修正、归一化等操作：候选互译对抽取模块， 首先对同一英文实体对应的多个中文串进行中文分词，然后根据分词结果利用后缀树抽 取候选翻译串，与该英文实体组成候选互译对；双语命名实体对齐模块，将对齐问题转 化为分类问题，采用支持向量机分类模型，并利用基于i b mm o d e ll 的翻译质量评测 模型和基于感知器的音译模型提供的特征，结合候选互译对在网页中的出现频度、以及 在后缀树中的频度等特征，来进行二值分类，从而判断出候选互译对是否为双语命名实 体；过滤模块，采用了翻译频度等信息进行了有效的过滤，并抽取出前导词翻译前缀反 馈给候选互译对抽取模块。 本文的主要贡献有：( 1 ) 提出了一套能从大量网页中抽取高质量双语命名实体的方 法；( 2 ) 有效的利用了已有的方法并进行有机的整合；通过实验证明，综合网页信息抽 取、中文分词、翻译模型、音译模型、分类模型、以及后续处理等模块，该框架可以获 得比同类方法更好的性能。 关键词：双语命名实体；数据挖掘；中文分词；跨语言检索；自然语言处理 人连理i ：人学硕十学位论文 r e s e a r c ha n di m p l e m e n t a t i o no fm i n i n gb i l i n g u a ln a m e de n t i t i e s f r o ml a r g e s c a l ew e bp a g e s a b s t r a c t l a r g es c a l eb i l i n g u a ln a m e de n t i t yc o r p u sc a ni m p r o v eal o tt h ep e r f o r m a n c eo ft h e s y s t e ml i k em a c h i n et r a n s l a t i o no rc r o s sl a n g u a g ei n f o r m a t i o nr e t r i e v a l s om a n ym e t h o d s a i m e dt om i n eb i l i n g u a ln a m e de n t i t i e sh a v eb e e np r o p o s e d t h ep r e v i o u sm e t h o d sm a i n l y u s e dt h eb i l i n g u a lc o r p u sa st h er e s o u r c e ；b u tt h e s em e t h o d sa r el i m i t e do ns c a l ea n dd i v e r s i t y , a n da l s oc a nn o th a n d l et h eo u to fv o c a b u l a r y ( o o v ) p r o b l e mw e l l a st h ew e b d e v e l o p i n g v e r yq u i c k l y , l o t so fw e bp a g e sc o n t a i nb i l i n g u a ln a m e de n t i t i e s ，a n dt h ew e ba l s oh a st h e a d v a n t a g eo nd i v e r s i t ya n dr e a l t i m e ；t h eb i l i n g u a ln a m e de n t i t i e sf r o mw e bc o m ef r o m v a r i e t yd o m a i n s ，a l s oi n c l u d ep l e n t yo fo o v s o ，h o wt om i n eb i l i n g u a ln a m e de n t i t i e sh a s b e e np a i dm o r ea t t e n t i o no nr e s e a r c h t h i sp a p e rp r o p o s e sam e t h o do nh o wt om i n eb i l i n g u a ln a m e de n t i t i e sf r o ml a r g es c a l e w e bp a g e s t h em e t h o dm a i n l yu s e st h er e d u n d a n ti n f o r m a t i o no fl a r g e - s c a l ew e bp a g e s f i r s t l y , e x t r a c tt h eb i l i n g u a ls t r i n gf r o ml a r g es c a l ew e bp a g e s ；s e c o n d l y , u s ec h i n e s ew o r d s e g m e n t a t i o na n ds u f f i xt r e et oe x t r a c tc a n d i d a t e so fb i l i n g u a lp a i r s ；t h i r d l y , u s et h em o d e l b a s e do ns v mt od e t e r m i n ew h i c hc a n d i d a t ei sb i l i n g u a ln a m e de n t i t y ；f i n a l l y , u s et h ep o s t p r o c e s s i n gm e t h o d st of i l t e rn o i s ea n db a dt r a n s l a t i o n s ，t h e ng e tt h ec o r r e c tb i l i n g u a ln a m e d e n t i t i e s t h i sp a p e rd e s i g n sa n di m p l e m e n t st h eb i l i n g u a ln a m e d e n t i t ym i n i n gs y s t e m t h ei n p u t o ft h es y s t e mi sas e to fl a r g es c a l ew e b p a g e sa n dt h eo u t p u ti st h ee x t r a c t e db i l i n g u a ln a m e d e n t i t i e s t h es y s t e mi sc o m p o s e do f4m o d u l e s ：( 1 ) b i l i n g u a ls t r i n ge x t r a c t i o n ；( 2 ) c a n d i d a t e b i l i n g u a lp a i re x t r a c t i o n ；( 3 ) b i l i n g u a ln a m e de n t i t ya l i g n m e n t ；( 4 ) p o s tp r o c e s s i n g c o n t r i b u t i o no ft h i ss t u d yc a nb es u m m a r i z e da sf o l l o w s ：( 1 ) a ni n t e g r a t i o nm i n i n g s c h e m ei sp r e s e n t e dt od i s c o v e r , e x t r a c ta n dv e r i f yt h eb i l i n g u a ln a m e de n t i t yw i t hh i g h q u a l i t yf r o mal a r g es c a l ew e bp a g es e t ；( 2 ) ac o m b i n a t i o no fp r e v i o u sm e t h o d sh a sb e e nm a d e ， a n dt h er e s u l t so ft h ee x p e r i m e n t ss h o wt h a to u rs c h e m eg a i n sh i g h e re x t r a c t i o np e r f o r m a n c e t h a np e r v i o u sa p p r o a c h e s k e yw o r d s ：b i l i n g u a ln a m e de n t i t y ；d a t am i n i n g ；c h i n e s ew o r ds e g m e n t a t i o n ；c r o s s l a n g u a g ei n f o r m a t i o nr e t r i e v a l ；n a t u r a ll a n g u a g ep r o c e s s i n g 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名：一 人连理l ：人学硕士研究生学伊论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题 作者签名： 导师签名： 人连理i ：人学硕十学伊论文 1 绪论 1 1研究背景 信息抽取是自然语言处理的一个最重要的任务。它的目的是从非结构化和半结构化 的文本中，找到用户想要的信息，这些信息包括命名实体、信息之间的关系以及用户想 要的知识等。信息检索的研究最早开始于2 0 世纪6 0 年代。早期的研究者试图从自由的 文本中抽取一些数据或信息。不久后，网络成为世界上信息获取的最大的数据源，越来 越多的研究者开始从事从网络中抽取信息。 随着互联网的飞速发展，万维网已经变成具有庞大数量且有多样性的在线文档资 源。越来越多的研究者丌始研究从网页中挖掘信息。搜索引擎成为网络环境中最强大的 工具。人们在搜索引擎中输入一个关键字，搜索引擎就会立刻返回与搜索关键字相关的 网页的链接。但是，人们可能只对网页中的相关信息感兴趣。这样的需求就得通过从网 页中直接挖掘相关信息的方法来解决。而网页不同于通常的自然语言文本，它一般是半 结构化的信息，甚至包含了很多的噪音，或者是人们不需要的信息，如广告、导航等。 这就使得从基于网页的信息抽取更为困难。 如何从网络中获得平行双语语料逐渐被人们所关注，并表现出了它的重要性。 平行双语语料库在机器翻译，跨语言信息检索中均起了至关重要的作用。大规模的 双语平行语料库可以明显的改善基于实例的机器翻译系统的性能；平行的双语语料还可 以提高跨语言信息检索系统的性能。 近年来，如何获得平行双语语料逐渐成为研究的热点，也被认为是自然语言处理的 一个重要任务。过去，平行语料的获取被认为是很困难的工作，因为可用的资源太少， 而且覆盖面又窄。但是，随着万维网的飞速发展，越来越多的双语资源出现在网络中， 几乎包括了所有的领域，而且资源也越来越丰富，这就为从网络中挖掘平行的双语语料 提供了一个广阔的平台。 所谓双语命名实体，是指来自两种不同语言且互译的命名实体。命名实体在语言中 往往传达着非常有用的信息1 1j 。在这罩命名实体不仅仅指人名、地名和机构名，它是一 个泛化的概念，也可以是两个互译的短语、短句等，也可以是一个缩略语的一种翻译， 如“i p c ”在可以被译为“国际货币基金组织”，只要互译且不是长句，本文均认为是双 语命名实体对。表1 1 显示了来自w e b 中各种各样的双语命名实体。 为了简化描述，本文在后续的论述中用双语实体来表示双语命名实体。而且论文中 出现的实体均是命名实体之意。 人规模网页中蚁语命名实体挖掘的研究与实现 1 2 研究意义 双语命名实体可以用在机器翻译，自然语言处理，跨语言信息检索，外语教学等诸 多方面。双语命名实体是传统双语词典的有效补充。由于本文只考虑了中英文两种语言， 因此，在下面的讨论中，如非特指，则几涉及双语命名实体均表示中英文双语命名实体。 表1 1w e b 中双语命名实体的多样性 t a b 1 1t h ed i v e r s i t yo fb i l i n g u a ln a m e de n t i t i e sf r o mt h ew e b 机器翻泽中，大规模的双语命名实体库能够较好的改进翻译质量。实验表明，机器 翻译的质量有对并行语料库的规模和质量有很强的依赖。尤其是在中英文翻译中，不仅 仅需要的是单方向的语料，而双向的( 汉英，英汉) 的语料史加备受关注。 人连理i ：人学硕十学伊论文 检索系统中，利用双语信息，可以提高检索的准确度和精准度。尤其是在跨语言检 索中，较大规模的平行语料往往能够给系统带来更好的影响。 双语命名实体对也能够帮助语言学习者更好的学习和运用一门语言。用户在英语阅 读中，往往会碰到一些特殊的短语或者缩略语，在传统的翻译中是无法找到对应的翻译 的。而互联网如此发达的今天，他们所要找的或许已经在网络上被人翻译过并作了标注 的。另外通过查找双语命名实体对，也能够帮助用户写出更地道的英语来。 1 3 研究现状 双语命名实体是指具有语义上等同关系的不同语言的表达。因为命名实体，尤其是 人名、地名、机构名，在语言中往往传达着非常有用的信息。因此，取得命名实体的翻 译等价对，对于多语言信息处理( 如机器翻译，跨语言信息检索与自动问答等) 有着非常重 要的意义1 2 1 。在过去的几年旱，一些处理跨语言的命名实体翻译等价对的方法，如双语 字典查找，音译模型等先后被提出1 3 。引，由于基于双语字典查找方法的字典有限覆盖性， 以及基于词或字的音译模型由于缺少考虑上下文有关信息，它们很多时候都不能得到令 人满意的结果。 另一种可行的方法是从平行语料库中自动抽取有关命名实体的翻译等价对。h u a n g 等1 6 j 提出了一种基于多特征代价最小的自动抽取命名实体翻译等价对的方法。他们的实 验表明，用他们提出的方法抽取命名实体的翻译等价对比以前的方法更加有效，并且， 当把抽取得到的翻译等价对加入到统计机器翻译系统时，翻译质量有了显著的提高。但 是，他们的抽取方法，一方面要求平行语料库中的源语言与目标语言中的命名实体都需 要预先标注，这样增加了工作量；另一方面当标注出现错误，特别是一种语言标注j 下确， 而另一种语言标注错误，他们的对齐模型无法纠正这个标注错误，这将严重地影响到最 后抽取的命名实体翻译等价对的证确率。 陈等1 2 j 提出了一种从只在源语言的语料库中进行有关命名实体翻译等价对的抽取方 法。先用h m m 词对齐模型对平行语料库进行对齐，然后基于对齐模型上的短语抽取技 术，先生成与源语言相对应的目标语言的候选命名实体翻译等价单位，然后对它们进行 三种置信度估计，最后综合得到与源语言命名实体最为匹配的目标语言命名实体翻译等 价单位。 上述的方法都是从已有的双语平行语料巾抽取双语命名实体对，缺点是，已有的语 料往往只是来自几个不i 川的领域，得到的数据则不具备多样性，不能涵盖所有的领域。 因为网络巾的数据具有多样性且是超大规模，那么如何利用网络资源来挖掘平行语料就 成了研究者关注的焦点。 人规模网页中舣语命乞实体挖掘的研究与实现 n i e 等人【7 j 试图自动发掘平行的w e b 文档，如英语与汉语、英语与法语等。利用存 在于w e b 中平行文本的常见组合来判别平行网页，如有共同的上级网页，相似的名字 等。尽管通过这种方法已经挖掘出了一些双语的语料，但是很难把陔方法扩展到其他语 言中去，如阿拉伯语。另外，这种方法只能挖掘出常见的短语之类的语料，对于那些专 有的短语，如命名实体、专门概念就变的束手无策了。 l u 等人【8 l 对n i e 的方法提出了扩展。方法是视两个来自不同语言网页且指向同一个 资源的锚文本1 为双语翻译对。有各种各样的多语言的锚文本会指向同一个网页。这种 方法可以抽取出已给定的实体的翻译。虽然有很高的精确率，但是却没有较高的覆盖率， 因为锚文本仅仅是网页信息的很小的一部分。 还有一些方法依赖于搜索引掣9 1 2 l ，这些方法的基本原理是，对于己给出的待查询 的源语言实体( 如英文实体) ，利用搜索引擎去查找与之对应的包含目标语言翻译的结果 并抽取出来，这种方法虽然新颖，但不够灵活，无法得到大规模的数据。 f a n 等【1 3 l 提出了从网络中挖掘双语翻译对的方法，该方法基于双语平行翻译对在网 上会集群式出现的特点，通过一个循坏迭代的挖掘方法自动从网络上发现，抽取高质量 的翻译对。首先利用种子数据从搜索引擎上获取包含子数据的网页，然后使用一个启发 式的评估方法从网页中发现平行双语对。对这些包含集群式出现的双语翻译对的信息区 域，自动构建抽取模板，然后，根据模板的抽取性能对模板进行排序，再利用排在前面 的模板进行翻译对的抽取。最后，再通过使用一个基于源语言和目标语言翻译相关性的 分类器，将高质量的翻译对提取出来。该方法利用迭代的方法同样不能保证较高的覆盖 率。 c a o 等1 1 4 】第一次提出了从大规模的单语言网页中挖掘英汉双语词典的方法，他们从 3 0 0 g b 的网页中挖掘出了1 6 1 ，1 1 7 个双语翻译对。该方法基于这样一种观察：许多中文 的命名实体总是和它对应的英文实体出现在一起。首先用预定义的模板抽取网页中候选 双语翻译串，通过统计的学习方法去识别其中互译的中英文翻译串。 本文的方法和c a o 的方法比较相似。也是从大规模的单语言网页中抽取出双语翻译 对，因为抽耿目的一些不同，本文称之为双语命名实体对。本文提出的方法在实体对齐 的模块中同样结合了意译和音译的两种方法。与之不同的是，本文采用了更多的特征并 且利用s v m 分类模型去判别候选双语命名实体对正确与否。本文同时提出了一种基于 子词的双层c r f s 中文分训方法，更好的解决了中文分词中的未登录词问题。而且设计 锚文奉指柏：链接中现的文本。 人连理i ：人学硕十学伊论文 了一个候选处理的模块，大大的提高了抽取结果的正确率。 1 4 本文的工作 本文对从w e b 挖掘双语命名实体的方法进行了研究。尝试利用大规模网页中的冗 余信息，即双语命名实体往往不是单独出现在w e b 中，而是出现在不同的网页中，且 出现在不同上下文里，基于这些冗余信息，首先抽取候选的互译对，然后利用对齐模型 判断候选互译对是否为正确的双语命名实体。 本文的工作可以归结为以下3 点： ( 1 ) 提出一套从大规模网页中挖掘双语命名实体的方法。方法首先从大规模网页中 抽取符合特定模式的双语串，对这些抽取出的大规模双语串进行过滤、修正以及排序后； 再通过中文分词与后缀树算法结合的方法抽取出候选的互译对；然后将双语命名实体对 齐问题转换为分类问题，对候选双语对进行二值分类来标注候选互译对是否为f 确的双 语命名实体，该过程采用了基于s v m 的分类模型，采用多特征融合的方法，用到了翻 译模型、音译模型提供的特征，对候选互译对进行分类；最后用一套过滤算法对分类得 到的双语命名实体进行过滤；最终得到高质量的双语命名实体。 ( 2 ) 设计并实现了基于本文所提方法的双语命名实体抽取系统。系统输入为一个大 规模的网页集，输出为高质量的双语命名实体。系统分为4 个模块：双语对抽取模 块；候选互译对抽取模块；双语命名实体对齐模块；噪音过滤模块。双语对 抽取模块从大规模网页中抽取符合括弧模式的双语对，并对抽取到的双语对进行噪音过 滤、修正、归一化操作；候选互译对抽取模块，首先对同一英文实体对应的多个中文串 进行中文分词，然后根据分词结果利用后缀树抽取候选翻译串，与该英文实体组成候选 互译对；双语命名实体对齐模块，基于s v m 模型，并利用基于i b mm o d e ll 的翻译 质量评测模型以及基于感知器的音译模型提供的特征，结合候选互译对在网页中的出现 频度、以及在后缀树中的频度等特征，来进行二值分类，从而判断出候选互译对是否为 双语命名实体；过滤模块，采用了翻译频度等信息进行了有效的过滤，并抽耿出前导词 翻译前缀反馈给候选互译对抽取模块。 ( 3 ) 对本文提出的方法进行了试验和评估。试验和评估采用了两种方法：基于维 基百科中双语命名实体的评价；以维基百科中的双语命名实体作为标准，来判断本文系 统得到的数据对维基百科中双语实体的覆盖率以及准确率。采用人工标注的数据对 最终得到的结果进行质量的评测。 人规模网页中舣诰命名实体挖掘的研究与实现 2从大规模网页中挖掘双语命名实体对 2 1问题描述 第1 章中讨论了双语命名实体的定义，考虑表2 1 中的双语对，其中的5 个双语对 均可以被认为是双语命名实体。所以本文描述的双语命名实体是一个泛化的定义，它不 仅仅指人名、地名、机构名，还可以包括电影名称、公司名、生物名、科技术语以及各 行各业的专业术语，甚至包括互译的短语等。 由于本文的研究仅包括了中文网页中挖掘中英文双语命名实体的情况，所以在本文 以后的描述中，除非特指，凡是提到双语命名实体之处均指中英文双语命名实体。也就 是说本文中描述的双语命名实体包含一个中文实体和一个与之互译英文实体，如“数码 视像接口 和“d i g i t a lv i s u a li n t e r f a c e ”。 表2 1 一些双语命名实体举例 t a b 2 1s o m ee x a m p l e so fb i l i n g u a ln a m e de n t i t i e s 英文中文 d i g i t a lv i s u a li n t e r f a c e w o r t h y s h a r p d i r e c tl a b o rc o s t d o wj o n e si n d u s t r i e sa v e r a g ei n d e x 数码视像接口 万信 夏普 直接劳动成本 道琼斯l ：业平均指数 本文在第1 章还讨论了双语命名实体在自然语言处理，跨语言信息检索等领域的重 要性。本文的目的是探讨如何从大规模网页中挖掘双语命名实体。区别以往的方法，本 文的方法是基于大规模的网页的，目的是利用大规模网页中双语命名实体会经常出现这 样的冗余信息，来抽取存在网页中的双语命名实体；另外，大规模网页还有覆盖面广， 信息及时等优点，这样就使我们能够获得更新、更全的双语命名实体。 如图2 1 所示，在很多中文网页中存在如下的现象，在中文的一些命名实体后面用 括号括起来它所对应的英文翻译。其中“i m f ”其实就是“国际货币基金组织”的翻译。 由此，假设这样的一种模式： c n t e r m ( e n t e r m ) ，该模式中 c n t e r m 表示一个中文的 命名实体， e n t e r m 表示一个英文的命名实体，它中间有一个“( ”，后面还有一个“) ”。 为了简化描述，在本文中，称这种模式为括弧模式。 由此可以推断，符合括弧模式的字符串均有可能是双语命名实体。 为了简化描述，本文定义以下术语： 人连理【：人学硕十学伊论文 双语串：本文称从括弧模式中抽取的字符串为双语串。 候选互译对：通过对双语串的修正、截断等操作，从中抽取出的、有可能互译的双 语串。 ii d f ： i ：l 准向巴基斯坦提供7 0 t e 美元贷款 h t t p ：l , t w w w s i n a c o r n ，c 1 32 0 0 8 年1 1 月2 5 8 1 6 ：1 2 中国网 一，一 中国网1 1 月2 5b 讯据巴基斯坦新闻报今天报道，( 国际货币基金组织( i 肛娆4 日称， 国际货币基金组织执行理事会已批准向巴基斯坦提供7 6 亿美元贷款这是世界金融危机发生 以来国际货币基金组织首次向亚洲国家提供救助资金 图2 1网页中存在于括弧模式下的舣语命名实体 f i g 2 1b i l i n g u a ln a m e de n t i t yi n c l u d e di np a r e n t h e t i c a lp a t t e r nf r o mw e bp a g e s 可以想象，互联网中有许多许多符合括弧模式的双语串。假设这样的一个集合，它 为互联网中所有的网页，那么可以利用这些网页抽取出符合括弧模式的所有双语串，来 抽取双语命名实体。把所有的双语串放到文件中，存储格式如下： e n t e r m l t c n t e r m l e n t e r m 2 t c n t e r m 2 e n t e r m 3 t c n t e r m 3 e n t e r m n t c n t e r m n 可以想象所有抽取出的双语串将会是一个很庞大的集合。 如果每一行诸如“ e n t e r m l t c n t e r m l ”为一条信息，又假设互联网中所有的中 文网页数量为1 0 亿，那么从所有网页中抽取到的结果将含有千万级别甚至上亿的信息。 显然，从这个结果集合中，能够推出如下的信息： ( 1 ) 每一条信息可能会重复多次。 ( 2 ) 一个英文串可能会对应几个不同的中文串。 ( 3 ) 一个中文串可能会对应几个不同的英文串。 ( 4 ) 有一些双语串本身就是双语命名实体。 ( 5 ) 有一些双语串通过去噪、修正后会成为币确的双语命名实体。 ( 6 ) 其中有很多条信息是噪音，并不是双语命名实体。 2 2 双语命名实体挖掘系统 系统的框架图如图2 2 所示。 人规模网页中双语命名实体挖掘的研究与实现 图2 2 舣语命名实体抽取系统框架图 f i g 2 2 f r a m e w o r ko fb i l i n g u a ln a m e d e n t i t ye x t r a c t i o ns y s t e m 本文的系统分为4 个部分： ( 1 ) 双语对的抽取 这旱的双语对指的是符合以下情况的字符串： 含有连续的汉字和连续的英文字符。 符合括弧模式。 在同一个页面中连续的串。 图2 1 中“国际货币基金组织( i m f ) 就是一个双语串。 因为我们处理的数据是h t m l 的网页，在抽取双语串之前，必须对网页进行解析， 从而得到网页的文本，就像浏览器中看到的网页一样。 对于一个输入的网页，首先需要经过预处理之后进行网页解析，网页解析的目的是 为了得到网页的纯文本；然后在进行括弧模式的双语串识别，同时记录下上下文的信息； 然后将抽取中的双语串放到同一个文件中，并保留相关信息。 ( 2 ) 候选互译对的抽取 候选互译对的抽取包含了两个步骤：第一步是中文分词，中文分词的目的是为了减 少噪音、提高识别精度；第二步利用后缀树，找到同一英文实体所对应的所有中文实体 的共同后缀，根据某一个后缀的出现频度来抽取候选互译对。 ( 3 ) 双语命名实体对齐 对于命名实体的对齐，本文采用了多特征融合的方法。采用了基于s v m 的对齐模 型，对于抽取得到的候选瓦译对，通过翻译模型、音译模型等提供的特征来判定候选互 译对是否为双语命名实体。所用到的模型将在本文后续章节中详细阐述。 ( 4 ) 后续处理 这一步是整个系统的后续处理部分。这罩所指的噪音，是那些显然没有互译性质的 人迮理l ：人学硕+ 学伊论文 双语对。因为考虑到网络中数据的复杂性，同时存在很多的噪音，必须有一个行之有效 的噪音去除方法，才能保证我们最后结果的精确率。同时，经过后续处理得到的数据还 可以对系统的实体对齐模型进行反馈，从而改善结果的质量。 2 3 难点分析 网络中存在各种各样的网页，它们最大的特点就是复杂，无法用一个统一的模板去 定义所有的网页，这就使得从网页中挖掘结果化的知识变的很困难。 而对于从大规模网页中挖掘双语命名实体对，最大的困难有4 点： ( 1 ) 如何从抽取出的大规模双语串中抽取出候选互译对。如果在抽取出的候选互译 对中没有正确的双语实体，那么后续的双语实体对齐模块就无法得到正确的结果。所以 这一步至关重要。例如“称为活动桌面( a c t i v ed e s k t o p ) ”，如何抽取出“活动桌面( a c t i v e d e s k t o p ) ”作为候选互译对便是这个问题的难点。 ( 2 ) 如何判别候选互译对为正确的双语命名实体，因为网页的复杂性，不能用一个 单一的模型去进行简单的分类。 ( 3 ) 如何选择一个行之有效的策略去过滤抽取过程中或结果中的噪音，因为很多网 页中都有广告、导航等，这些噪音会大大降低基于学习或统计模型系统的性能。 ( 4 ) 大规模数据的运算和处理，系统要处理几十亿的网页，这样的信息量是很大的， 如何保证处理速度的同时又能保证质量。 2 。4 相关知识与模型 2 4 1 感知器算法 模式识别是2 0 世纪6 0 年代初迅速发展起来的一门新兴学科，主要功能是通过设计 合适的分类器来判别各个模式所属的类别。本文所采用的分类器是线性判别函数。即对 于训练模式样本集缸】= x l ，x ：，吒一，_ ) ，x k 一阮。，x k ：，) ，m 类线性可分模式集 为刃= m ，w 2 ，) ，存在这样一个直线方程：dg ) = w 岱1 + w 2 x 2 + + 嵋尚+ w n + 1 作 为模式类别划分的依据。d 伍) 即为判别函数。 感知器一词是人们对一种分类学习机模型的称呼，最早的感知器模型是美国学者 f a n kr o s e n b l a t t 在1 9 5 7 年提出的。感知器训练算法是指通过对训练模式样本集的学习， 从而得到判别函数的系数解，产生线性可分的模式判别函数。该算法的优点是不需要对 各类模式的统计性质作任何假设，属于确定性方法。赏罚过程贯穿于感知器算法的始终， 是感知器算法的一个主要内容。其摹本概念是对正确分类的模式则“赏”，即权向量w 人规模网页中舣语命名实体挖掘的研兖与实观 不变；对错误分类的模式则“罚”，即将权向量w 加上一个正比于模式样本x 的分量。 下面来看一下加权向量的训练过程：先假定已获得训练样本集仁 - - i x l ，x 2 ，工k ，x 。) ， 其中每一个样本z 七，k = 1 ，n ，分属于类型，或类型，且类型属性是已知的。运 用感知器训练算法，通过模型的训练学习来调整判决函数中的加权向量，计算步骤如下： ( 1 ) 给定出始值：置k = 0 ，分别赋给每个权因子wi y ( o ( f = 1 ，2 ，m + 1 ) 较小的任意 值，并且选择系数a 的值。通常选0 h ，用w ( t + 1 ) 代替w ，用h 代替h ，继续迭代。 可以证明这个算法以概率为1 收敛于最优解，也就是说，是一个产生最少误分类的 算法。 2 。4 2 支持向量机模型 支持向量机是v v i p n i k 等根据统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，s l 0 提出 的一种新的机器学习方法，在解决小样本、非线性及高维模式识别i u j 题中表现出许多特 有的优势，已经在模式识别、函数逼近和概率密度估计等方面取得了良好的效果。支持 向量机从本质上讲是一种自仃向神经网络，根据结构风险最小化准则，在使训练样本分类 误差极小化的前提下，尽量提高分类器的泛化推广能力。从实施的角度，训练支持向量 人连理i ：人学硕十学伊论文 机的核心思想等价于求解一个线性约束的二次规划问题，从而构造一个超平面作为决策 平面，使得特征空间中两类模式之| b j 的距离最大，而且它能保证得到的解为全局最优解。 支持向量机实质上是一种基于统计学习理论和线性分类思想的学习方法，其中支持 向量是对分类有较好区分能力的样本点，这些支持向量可以构造出空隙最大的最优分类 超平面。 通过核函数变换的方法，支持向量机可将在低维空间无法线性分类的样本映射到高 维空间进行分类，很好得解决了有限数量样本的高维模型构造问题。支持向量机优于已 有机器学习方法一个重要方面是高维处理能力，即s v m 的学习误差不依赖于特性空间 的维数，不会出现其它机器学习方法的“过学习”现象。 应用s v m 解决自然语言处理中的文本分类、词性标注、短语识别【1 5 1 8 1 等问题，取 得令人满意的结果。 支持向量机最初是针对线性可分情况下的二类模式分类问题而提出的。给定观测样 本集s = ( ，y ，) ，瓴，y ，) cz 一1 ，+ l ，其中，zc 尺“称为输入空间或输入特征空间， ) ， 一1 ，+ 1 ) 是样本的类标记。分类的目的就是寻找一个分割超平面将j 下负两类样本完全 分开，如图2 3 所示。 设； m ，j + 6 ；o ，w 彤，b e r 是所有能够对s 完全正确分类( 经验风险为o ) 的超平 面的集合，其中，“是内积运算符。“完全正确分类”的意义是：任意一个由法向量w 和常数b 确定的分类超平面h ，它对样本集s 的分类结果为：，。 ( 2 1 ) 在所有的超平面中，最大间隔分类器要寻找的是一个最优超平面( o p t i m a l h y p e r p l a n e ) 。这个最优超平面是指满足两类的分类间隔( m a r g i n ) 最大的超平面。分类间 隔被定义为：每类距离超平面最近的样本到超平面的距离之和。此分类间隔可以经过如 下的计算得到：设h 为最优超平面，在h 两侧分别作一个经过距离h 最近的样本并且 平行与日的超平面，记为日l 和阮。这两个超平面的表达式分别为：t ：y = w 工+ 6 一l ， 冀2 ：y w x + b i - 1 。 显然，超平面h ：y ；w ，x + 6 0 仍然属于考。本文把超平面h l 和吼之问的距离称为 h 的“分类问隔”，并将h ，和俄称为h 的“问隔超平面”或者“j 只j 隔边界”。容易计 算，a 一而w i l = d + + d 。 所谓的“最火l 闩j 隔分类超平面”就是在f 确分类所有学习样本( 即满足约束条件 y i ( w x i + 6 ) 2 1 的前提下) ，使得分类间隔取最大值的超平面，例如图2 3 中的h 。 h 1蜍崦 若若仉仉 l s 6 b + + 人规模网页中议语命名实体挖掘的研究与实现 h2 g in2 1 1 i l 图2 3 线性可分的分类超平面 f i g 2 3 s k e t c hc h a r to fs v mi nt h ec a s eo fl i n e a rs e p a r a b l e ( 1 ) 线性的情况 依据前一小节的讨论，为了求解线性可分问题的最大间隔超平面，需要在满足约束 y ，m x i + 6 ) 1 的前提下最大化问隔，等价于如下的优化问题： m i n 割w i l 2 弘y i ( w x i 柏) 乩嘲， ( 2 2 ) 这是一个典型的线性约束的凸二次规划问题，它唯一确定了最大间隔分类超平面。 它的l a g r a n g e 函数是： 川= 抑1 2 一扣( y i ( 删- 1 ) ( 2 3 ) 其中，口，苫。是每个样本对应的l a g r a n g e 乘子。将函数l ( w ，b ，口) 关于w ，b 求其极小 值，由极值条件v b l ( w ，b ，a ) 一。和w , l ( w ，b ，口) = 0 得到： f y i c t ，；0 ( 2 4 ) 何 w = 罗c t , y ( 2 5 ) 筒 将式( 2 4 ) 和( 2 5 ) 式代入l a g r a n g e 函数l ( w ，b ，a ) ，并考虑w o l f e 对偶性质，得到优 化问题( 2 2 ) 的对偶问题，如公式( 2 6 ) 所示。 人连理i ：人学硕十学侮论文 叼x ，吉妻套y , y j c t i c t j ( x i x ，) + 善i 乜r s j a i 蓍耋乏三二， c 2 6 ， 可见，对偶问题仍然是线性约束的凸二次优化，存在唯一的最优解口。 根据约束优化问题的k a r u s h k u h n t u c k e r ( k k t ) 条f 牛1 1 9 1 ，优化式( 2 6 ) 取最优解a 宰 时应该满足如下的条件： d j ( y f ( w ，筋+ 6 + ) 一1 ) 一o ，i = 1 ，2 ，z ( 2 7 ) 从图2 3 中可以看出，由于只有少部分观测样本x i 满足矽藏+ 6 ) 一1 ，它们对应 的l a g r a n g e 乘子口t 0 ，而剩余的样本满足口z ；0 。本文称解a 的这种性质为“稀疏性”。 本文把口t 0 的观测样本称为“支持向量”，它们位于间隔边界h l 或飓上。结合 公式( 2 5 ) 和( 2 7 ) 可知，+ 和b + 均由支持向量决定。因此，最大间隔超平面，x i + 6 一0 完全由支持向量决定，而与剩余的观测样本无关。 这时，可以得到如下的最优决策函数或者分类器： f ( x ) = s g n ( w z + 6 ) = s g n ( 罗a 沙f ( z x f ) + 6 ) ( 2 8 ) v a p n i k 把公式( 2 8 ) 称为“线性硬间隔支持向量机l 2 0 】”，而公式( 2 2 ) 和( 2 6 ) 分别称 为它的原始优化问题和对偶优化问题。 另外，当样本线性不可分时，由于不存在使得分类间隔取正值的超平面，严格要 求所有样本被正确分类的“硬间隔”方法是行不通的。换句话说，必须适当松弛公式中 的约束条件。本文通过引入松弛变量参20 ，i = 1 ，z ，可以得到“软化 的新约束条件： y l ( ，x i + 6 ) 1 一亭f ，亭j20 ，i = 1 ，z ( 2 9 ) 显然，当争充分大时，样本( x i ，y r ) 总可以满足约束条件。但另一方面，和项罗参与 样本的分类错误相关并且体现了经验风险，必须限制它的大小。因此，得到“软化”后 的最大问隔分类器的优化问题： m 咄i n ；抄1 1 2 + c 善亭r 豇y 加肼m 1 亭，省洮一f ( 2 1 0 ) 其中，实常数c 0 称为“罚参数”，它在分类器的复杂度和经验风险之间进行权衡。 采用类似( 2 2 ) 至( 2 6 ) 的推导过程，可以得到式( 2 1 0 ) 的对偶优化问题。因而不再详细 给出对偶问题的具体形式。 ( 2 ) 非线性的情况 解决线性不可分类闯题的另外一个途径是用“超曲而”代替“超平面9 9 9 并寻找一 人规模网页中舣语命名实体挖掘的研究与实现 个能够币确分类所有观测样本的“最大间隔超曲面”。但是，“最大间隔超曲面”