（计算机系统结构专业论文）基于table布局和隐马尔可夫模型的web自由文本信息抽取.pdf

浙江人学硕七学位论文摘要 摘要 互联网的数据变得越来越庞大，如何自动地从中抽取信息从而减轻人类的阅 读理解负担变得越来越价值。互联网的网页中主要包含三种类型的文本一结构 化文本，半结构化文本，自由文本。本文设计的系统从w 曲页面提取自由文本并 从中抽取出结构化信息：它以w 曲为数据源，从聚焦搜索抓取的主题网页库中取 得某一主题的网页，提取网页正文，并进一步判定网页正文的自由文本属性，利 用该主题类型的信息抽取训练模型对自由文本提取目标信息，最后存入结构化信 息存储系统中供后续应用程序的查询使用。根据大多数网页布局基于t a b l e 标 签布局这一情况，本文提出了基于t a b l e 布局的分块和网页冗余信息检测与移 除算法一对于一个h 俐l 文档，提取网页中的所有t a b l e 元素，构成一个简 化的t a b l e 树型模型。根据t a b l e 节点的结构，样式及内容相似性，进行分块， 聚类，从而提取网页模版。另外，由于网页中的自由文本通常表现为比较连续的 文本字符串，而半结构化信息通常存放在m m l 的t a b l e ，u l ，0 l 等结构中，本 文提出了一种网页正文的自由文本识别算法，通过对网页正文进行分段处理后计 算各文本段的离散程度，来判断网页正文是否为自由文本或半结构化文本。最后 本文提出了一种利用基于p o s 的隐马尔可夫模型从自由文本中抽取信息的方法。 关键词信息抽取，w e b 自由文本提取，模版检测，t a b l e 分块，隐马尔可夫模型 浙江大学硕t 学位论文 a b s t r a c t t h ee x d o n e n t i a li n c r e a s eo ft h ei n f o n 呛t i o no nt h ew o r l dw i d ew e bi sn o w m k i n ga u t o m t i cw e bi n f o r m t i o ne x t r a c t i o nap r a c t i c a ln e c e s s i t yt o r e d u c eh u l n a ne f f o r t si nr e a d i n ga n du n d e r s t a n d i n gt h e m t h et e x to nw e b p a g e sc a ng e n e r a l l yb ec l a s s i f i e di n t ot h r e ec a t e g o r i e s ：s t r u c t u r e dt e x t ， s e m i s t r u c t u r e dt e x t8 n df r e et e x t t h es y s t e mp r e s e n t e di nt h i sp a p e r a i m st oe x t r a c tw e bp a g ei n f o r m a t i o ni nt w os t e p s ：e x t r a c t i n gf r e et e x t f r o mt h ew e ba n de x t r a c t i n gi n f o r m t i o nf r 伽t h ee x t r a c t e df r e et e x t t h e e x t r 8 c t i o np r o c e s ss t a r t sw i t haf o c u s e dt o p i c a lc r 鲫l e rw h i c hc 0 1 l e c t s w e bp 8 9 e so fac e r t a i nt o p i c t h ep a g e sa r et h e ni n s p e c t e da g a i nf o rf r e e t e x t sa n dat r a i n e di i l o d e li su s e dt oe x t r a c ti n f o r m a t i o na n ds t o r et h e s t r u c t u r e dr e s u l t si n t oad a t a b a s ef o r1 a t e ru s e m o s tw e bs i t e su s et a b l e t a gt 0 髓n a g et h ec o n t e n t sa n d1 a y o u to fp a g e s ，t h e r e f o r e ， t h i sp a p e r p r o p o s e sa na l g o r i t h mt od e t e c ta n dr 伽o v en o i s yi n f o r 腿t i o no faw e bp a g e w i t hf 0 1 1 0 w i n gs t e p s ： e x t r a c t i n g t a b l ee l e m e n t sf r 伽h t m lt e x t s ， c o n s t r u c t i n gan e ws i m p l i f i e dt r e es t r u c t u r ea n db l o c k i n g ，c l u s t e r i n ga n d e x t r a c t i n gp a g et e m p l a t e sa c c o r d i n gt ot h es i m il a r i t yb e t w e e np a g e s b e s i d e s 。 f r e et e x t si nw e bp a g e sa r es e q u e n c ec h a r a c t e r sw h i l e s e m i s t r u c t u r e dt e x t sa r ei nt a g s1 i k et a b l e ， o l ， u le t c ，s ot h i sp 8 p e r p r o p o s e sa n o t h e ra l g o r i t h mt oi d e n t i f yw h e t h e rt h ec o n t e n to faw e bp a g e i sf r e et e x to rs e m i s t r u c t u r e dt e x ta c c o r d i n gt ot h ed e g r e eo fd i s c r e t i o n o ft e x ts e g m e n t si nt h ec o n t e n to ft h ep a g e i nt h ee n d ，t h i sp a p e rp r o p o s e s a na p p r o a c ht oe x t r a c ti n f o r 髓t i o nf r o mf r e et e x tu s i n gf o sb a s e dh i d d e n m a r k o vm o d e l k e ”m r 出 i n f o 瑚t i o ne x t r a c t i o n ，f r e e bt e x te x t r a c t i o n ， t e m p l a t e d e t e c t i o n ， t a b l eb l o c k s ，h i d d e nm a r k o vm o d e l “ 浙江大学硕i 学位论文 图目录 图目录 图1 1 全球网站数目统计( 1 9 9 5 8 _ 2 0 0 7 4 ) l 图1 2 中国互联网网页总数( 2 0 0 1 2 0 0 6 ) 2 图1 3 中国互联网网页总字节数( 2 0 0 1 2 0 0 6 ) 2 图3 1 网页自由文本信息抽取系统架构图1 9 图3 2w 曲信息抽取处理流程2 0 图3 - 3 主题搜索的主要流程2 l 图3 4n u t c h 主题搜索截图2 2 图4 1 网页冗余信息示例2 7 图4 2 网页链接模型3 l 图4 - 3 树的映射3 5 图5 1 待t a b l e 分块处理网页举例3 9 图5 2 基于t a b l e 的d o m 结构4 3 图5 3 新浪新闻模版与正文4 7 图5 4 新华网模版与正文4 8 图5 5 模版检测精确度比较4 9 图7 1h 删举例( 论文的头部信息) 6 4 图7 2l c t c l a s 应用程序进行分词和词性标注的界面6 5 图7 3 正面模型6 8 图7 4 负面模型一6 9 图7 - 5 时间元素抽取结果比较7 0 图7 6 人物元素抽取结果比较7 l 图7 7 场合元素抽取结果比较7 l 图7 8 事件元素抽取结果比较7 2 图7 9 使用l l l k e 查看抽取的信息。7 3 v i 浙江大学硕学位论文 表目录 表5 1 模版检测运行时问比较 表5 2r 1 r d m 精确度比较 表5 3r t d m 计算时问比较 表目录 表6 1 实验数据集 表6 2 自由文本识别正确度( r o 9 ) 。 表6 3 自由文本识别正确度( r = o 8 ) 。 表7 1 训练模型标签 5 7 5 8 5 8 浙江大学硕上学位论文 第l 章绪论 第l 章绪论 1 1 课题背景 随着计算机的普及以及互联网的迅猛发展，大量的信息以电子文档的形式出 现在人们面前。 目前全球互联网的网页总数已经达到千亿数量级，域名总数过亿，而且有效网 站也超过了5 千万个。 1 h t t p ：，n e w s n e i c m f i c o m a 砖i l i v w d b - s a v e i ：飘玎w i y h t l l 2 中国互联网络信息中心( c l l i n a i n t 锄e t n 咖o r l ( i n f o r m a t i o n c e n t 呻，官方网站访 问地址：h t t p ：伽帆锄i c 瞅c i l ， j 浙江大学硕士学位论文第l 章绪论 图l - 2 中国互联网网页总数( 2 0 0 l 一2 0 0 6 ) 图1 3 中国互联网网页总字节数( 2 0 0 l 一2 0 0 6 ) 面对如此庞大的信息量，虽然目前已经诞生很多比较成熟的商业搜索引擎， 但是这些搜索引擎提供的仍然是以文档为主的信息源，不是信息本身，更加不是 知识为了应对信息爆炸带来的严重挑战，迫切需要一些自动化的工具帮助人们 从海量信息中迅速找到真正需要的信息。比如，从经济新闻中抽取出公司发布新 产品的情况：公司名、产品名、发布时间、产品性能等；从新闻报道中抽取出恐 怖事件的详细情况：时间、地点、作案者、受害者、袭击目标、使用的武器等； 2 浙江大学硕士学位论文第l 章绪论 从病人的医疗记录中抽取出症状、诊断记录、检验结果、处方等等。 信息抽取( i l l f 0 彻a t i e x t r a 简o n ) 的研究正是在这种背景下产生的。 1 2 信息抽取的概念 信息抽取( i n f o 瑚t i o ne x t r a c t i o n ) 是从非结构化并且机器可读的文本中自 动提取结构化或者半结构化信息的一种信息获取方法。它是计算机科学的一个分 支语言工程的一个子学科它旨在利用计算机科学中如编译原理，人工智能 等方法和技术来解决某一特定领域的非结构化文本的信息自动提取问题。它是从 一段文本中抽取指定的一类信息并将其形成结构化的数据填入一个数据库中供 用户查询使用的过程。信息抽取系统的主要功能是从文本中抽取出特定的事实信 息( f a c t u a li n f o m t i o n ) 通常，被抽取出来的信息以结构化的形式描述，可 以直接存入数据库中，供用户查询以及进一步分析利用。 删c ( m e s s a g eu n d e r s t a n d i n gc o n f e r e n c e ) 定义的文本提取如下： 从纯文本字符串形式的文本中提取信息并进行处理，将其放入标记着可填入 信息类型的槽中。 信息抽取从结构化或半结构化的文本中提取结构化信息。输入信息抽取系统 的是原始文本，输出的是固定格式的信息点。信息点从各种各样的文档中被抽取 出来，然后以统一的形式集成在一起。这就是信息抽取的主要任务。 信息抽取技术并不试图全面理解整篇文档，只是对文档中包含相关信息的部 分进行分析。至于哪些信息是相关的，那将由系统设计时定下的领域范围而定。 信息抽取技术对于从大量的文档中抽取需要的特定事实来说是非常有用的 互联网上就存在着这么一个文档库。在网上，同一主题的信息通常分散存放在不 3 w i k i p c d i a ：h i f o r m a t i 戗t r a c t i o n ( i e ) i 8at y p eo f i n l o 咖a t i o n 删r i c v a lw h o g o a l i st oa u t o m a t i c a l l ve x 咖c ts 打u d 【i 】i 、e do r 翻砌s n l l c t l l f o di n f o n n a t i 矗砌l m s h u c t u 棚 m a c h i n 争f e a d a b l ed o 咖蜘t s ni sa s l i b _ d i s c i p l i n eo f l 锄g i l a g ee i l 百i 懈耐n 岛ab r a n c h o f m p u 衙s c i c e 4 m u 0 7l n 佃m a t i e x 岫c i i t 破d 娟n 蹦。几b c f d e f i n 硒伽o f i n l 洲堋e x 删伽1 h s i 【： i n f o 肋a t i e x 仃a c t i o ni nt l i es e n s eo f t h em e s s a g eu n d a s 1 舳d i n zc o n f 柏1 c e sh 够 b e t r a d i t i o n a l l vd e f i n c da st h ee x t r a c d o no f i i l f b 瑚a l i 伽丘砌at e x ti nt l l et b 肌o f 蛔【ts m n g s 锄dp f o c c s s c dt e ) 【ts 仃i n g sw l l i c ha 托p l a c c di i i t os l o t sl 西e i e dt oi 1 1 d i c a t et h e b n do f i n i - o n n a t i o nt l l a tc a nf i um 唧 3 浙江大学硕上学位论文第1 章绪论 同网站上，表现的形式也各不相同。若能将这些信息收集在一起，用结构化形式 储存，那将是有益的。 由于网上的信息载体主要是文本，所以，信息抽取技术对于那些把因特网当 成是知识来源的人来说是至关重要的。信息抽取系统可以看作是把信息从不同文 档中转换成数据库记录的系统。因此，成功的信息抽取系统将把互联网变成巨大 的数据库。 信息抽取原来的目标是从自然语言文档中找到特定的信息，是自然语言处理 领域特别有用的一个子领域。所开发的信息抽取系统既能处理含有表格信息的结 构化文本，又能处理自由式文本( 如新闻报道) 。i e 系统中的关键组成部分是一系 列的抽取规则或模式，其作用是确定需要抽取的信息。网上文本信息的大量增加 导致这方面的研究得到高度重视。 1 3 信息抽取的历史 从自然语言文本中获取结构化信息的研究最早开始于2 0 世纪6 0 年代中期，这 被看作是信息抽取技术的初始研究，它以两个长期的、研究性的n l p ( 自然语言处 理项目) 为代表 从2 0 世纪8 0 年代末开始，信息抽取研究蓬勃开展起来，这主要得益于消息理 解系列会议( 咖c ，m e s 8 a g eu n d e r s t a n d i n gc o n f e r e n c e ) 的召开。正是m u c 系列会 议使信息抽取发展成为自然语言处理领域一个重要分支，并一直推动这一领域的 研究向前发展。 从1 9 8 7 年开始到1 9 9 8 年，删c 会议共举行了七届，它由美国国防高级研究 计划委员会( d a r p a ，t h ed e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 资助。 姗c 的显著特点并不是会议本身，而在于对信息抽取系统的评测只有参加信 息抽取系统评测的单位才被允许参加删c 会议。在每次删c 会议前，组织者首先 向各参加者提供样例消息文本和有关抽取任务的说明，然后各参加者开发能够处 理这种消息文本的信息抽取系统。在正式会议前，各参加者运行各自的系统处理 给定的测试消息文本集合。由各个系统的输出结果与手工标注的标准结果相对照 4 浙江大学硕士学位论文 第l 章绪论 得到最终的评测结果。最后才是所谓的会议，由参与者交流思想和感受。后来， 这种评测驱动的会议模式得到广泛推广，如1 9 9 2 年开始举行的文本检索会议 t r e c s 等。 从历次m u c 会议，可以清楚地看到信息抽取技术发展的历程。 首届删c 会议于1 9 8 7 年5 月举行，基本上是探索性的，没有明确的任务定义，也 没有制定评测标准 删c 一2 于1 9 8 9 年5 月举行，开始有了明确的任务定义，规定了模板以及槽的填 充规则，抽取任务被明确为一个模板填充的过程。 删c 一3 于1 9 9 1 年5 月举行，定义的抽取模板由1 8 个槽组成。从删c 一3 开始引入正 式的评测标准，其中借用了信息检索领域采用的一些概念，如召回率和准确率等。 m u c - 4 于1 9 9 2 年6 月举行，抽取模板变得更复杂，总共出2 4 个槽组成。从这次 会议开始州c 被纳入t i p s t e r 文本项目。 删c 5 于1 9 9 3 年8 月举行，除英语外，姗c 一5 还对同语信息抽取系统进行了测试。 在本次会议上，组织者尝试采用平均填充错误率( e r r ，e r r o rp e rr e s p o n s ef i l l ) 作为主要评价指标。删c 一5 的模板和槽填充规范是m u c 系列评测中最复杂的。 删c 一5 引入了嵌套的模板结构。信息抽取模板不再是扁平结构( f l a ts t r u c t u r e ) 的单个模板，而是借鉴面向对象和框架知识表示的思想，由多个子模板组成。模 板中每个槽的取值除了可以是文本串( 如公司名) 、格式化串( 如将同期、时间、 金额等文本描述转化为某种规范形式) 、有限集合中的元素( 如组织类型可以分为 公司、政府部门，研究机构等) 外，还可以是指向另一个子模板的指针。 m u c 一6 于1 9 9 5 年9 月举行，删c 一6 的评测更为细致，强调系统的可移植性以及对 文本的深层理解能力。除了原有的场景模板( s c e n a r i ot e m p l a t e s ) 填充任务外， 又引入三个薪的评测任务：命名实体( n 锄e de n t i t y ) 识别、共指( c o r e f e r e n c e ) n n p ：，仃c c m s t 暨0 v ， t i p s t e r 文本项目( 1 1 t t p ： n 啊i t l 血s t g o v i a u i 8 9 4 0 2 ，r e l a t c dp r o i e c t s t i p s t e f 口由 美国国防高级研究计翔委员会组织，1 为1 年开始实旌，1 9 9 9 年秋天终止。该项 目致力于推动和促进提高文本处理技术水平，重点是文档检索( d o c 啪e n t d e t e c t i o n ) 、信息抽取( i n f o n n a t i o ne x 仃a c t i o n ) 、自动文摘( s u m m 赫z a t i ) 等技术， 共分三个阶段实施。 浙江大学硕士学位论文第1 章绪论 关系确定、模板元素( t e m p l a t ee 1 e 嘴n t ) 填充等。 最后一届删c 会议硼i c 一7 于1 9 9 8 年4 月举行除删卜6 已有的四项评测任务 外，m u c 一7 又增加了一项新任务一模板关系任务，它意在确定实体之间与特定 领域无关的关系2 l u c 系列会议对信息抽取这一研究方向的确立和发展起到了巨大的推动作用。 m u c 定义的信息抽取任务的各种规范以及确立的评价体系已经成为信息抽取研究 事实上的标准。 近几年，信息抽取技术的研究与应用更为活跃。在研究方面，主要侧重于以 下几方面：利用机器学习技术增强系统的可移植能力、探索深层理解技术、篇章 分析技术、多语言文本处理能力、w e b 信息抽取( w r a p p e r ) 以及对时闻信息的处理 等等。在应用方面，信息抽取应用的领域更加广泛，除自成系统以外，还往往与 其他文档处理技术结合建立功能强大的信息服务系统。 目前，除了强烈的应用需求外，正在推动信息抽取研究进一步发展的动力主 要来自美国国家标准技术研究所( n i s t ) 组织的自动内容抽取( a c e ，a u t o 嬲t i c c o n t e n te x t r a c t i o n ) 评测会议，。这项评测旨在开发自动内容抽取技术以支持对 三种不同来源( 普通文本，由自动语音识别a s r 得到的文本、由光学字符识别o c r 得到的文本) 的语言文本的自动处理，研究的主要内容是自动抽取新闻语料中出 现的实体、关系、事件等内容，即对新闻语料中实体、关系、事件的识别与描述。 最近一次评测( a c ep h a s e2s 咖e re v a l u a t i o n ) 主要有两大任务：实体识别与 跟踪( e d t ，e n t i t yd e t e c t i o na n dt r a c k i n g ) 、关系识别与描述( r d c ，r e l a t i o n d e t e c t i o na n dc h a r a c t e r i z a t i o n ) 。a c e2 0 0 7e v a l u a t i o n 将继续2 0 0 3 秋季的评 测任务( 包括英文的e d t ，r d c ，中文的e 叮，r d c 以及阿拉伯语的e d t ) 。 与m u c 相比，目前的a c e 评测不针对某个具体的领域或场景，采用基于漏报( 标 准答案中有而系统输出中没有) 和误报( 标准答案中没有而系统输出中有) 为基础 的一套评价体系，还对系统跨文档处理( c r o s s d o c u 咐n tp r o c e s s i n g ) 能力进行 评测。这一新的评测会议将把信息抽取技术研究引向新的高度。 7 h t l p ：，w w w i h n i s l g o v ，i a 矾9 4 0 l m 嘲，a 耐 6 浙江大学硕上学位论文第1 章绪论 中文信息抽取方面的研究起步较晚，主要的研究工作集中在对中文命名实体 的识别方面，在设计实现完整的中文信息抽取系统方面还处在探索阶段。其中， i n t e l 中国研究中心的z h a n gy i _ m i n 和z h o uj o ef 等人在a c l 一2 0 0 0 上演示了他们 开发的一个抽取中文命名实体以及这些实体间相互关系的信息抽取系统，该系统 利用基于记忆的学习( m b l ，m e l l l o r y b a s e dl e a r n i n g ) 算法获取规则用以抽取命名 实体及它们之间的关系0 3 。 1 4 本文研究目标与内容 互联网的数据变得越来越庞大，如何自动地从中抽取信息从而减轻人类的阅 读理解负担变得越来越迫切本文设计了一个从某一主题的w e b 页面提取自由文 本并从中抽取信息的解决方案。这个系统主要包括两个功能，一个是w e b 页面的 自由文本信息提取，一个是自由文本的信息抽取。 本文的创新点与主要贡献在于： 1 根据大多数网页布局基于t a b l e 标签布局这一情况，本文提出了基于 t a b l e 布局的分块和网页冗余信息检测与移除算法。对于一个h t m l 文档， 提取网页中的所有t a b l e 元素，构成一个简化的t a b l e 树型模型。然后 在这个简化的树型模型基础之上，检测同一网站网页之闯在结构，样式 及内容上的相似性，对网页进行分块，聚类，从而提取网页模版。简化 后的模型大大减少了计算量，提高了系统效率，能够较好地满足大规模 w e b 信息抽取系统。 2 根据网页中的自由文本通常表现为比较连续的文本字符串，而半结构化 信息通常存放在h t m l 的t a b l e ，u l ，0 l 等结构中的情况，本文提出了一种 网页正文的自由文本识别算法。根据t a b l e 等标签结构将文本分段，并 判断连续文本所占的比重，就可以较好地区分网页主要内容是否为连续 自由文本。所以本文提出了一种区分自由文本的算法，通过对网页正文 进行分段处理后计算各文本段的离散程度，来判断网页正文是否为自由 文本或半结构化文本。 7 浙江丈学硕十学位论文 第l 章绪论 3 在i c r c l a s 中文分词和词性标注的基础之上，本文提出了利用基于p o s ( p a n - o e s d c h ) 的隐马尔可夫模型从自由文本中抽取信息的方法。 4 另外，本文设计了一个从互联网中抽取网页自由文本信息的系统。本文 提出的系统以霄e b 为数据源，从聚焦搜索抓取的主题网页库中取得某一 主题的网页，提取网页正文，并迸一步判定网页正文的自由文本属性， 利用该主题类型的信息抽取训练模型对自由文本提取目标信息，最后存 入结构化信息存储系统中供后续应用程序的查询使用。 本文的主要内容如下： 第2 章主要讲述了信息抽取的理论基础和相关技术 第3 章主要讲述了本文提出的w e b 自由文本信息抽取系统的设计与架构。 第4 章主要讲述了网页自由文本提取的必要性和研究现状及不足。 第5 章主要讲述了基于t a b l e 布局的模版检测与移除算法，从而提取网页正 文内容。 第6 章主要讲述了区分自由文本的识别算法。 第7 章主要讲述了利用基于p o s 的隐马尔可夫模型从自由文本抽取信息的方 法。 第8 章是总结和展望。 最后是本文的参考文献和致谢。 1 5 本章小节 本章作为本文的绪论章节讲述了本文的研究背景，阐述了信息抽取的概念， 回顾了信息抽取的历史，并对本文的主要研究目标和内容作了概述。 浙江大学硕上学位论文 第2 章理论基础和相关技术 第2 章理论基础和相关技术 2 1 信息抽取 信息抽取是一个以未知文本为输入，并以固定格式，无歧义的数据为输出的 一个信息处理过程。输出的数据可以直接用来展示给用户，或者存入数掘库以备 后续分析，另外还可以被用于信息获取( i n f o 珊t i o nr e t r i e v e ，i r ) 系统的 索引过程 2 1 1 信息抽取与信息获取的区别 与信息抽取密切相关的一项研究是信息检索，但信息抽取与信息检索存在差 异，主要表现在三个方面： 目的不同。信息检索系统主要是从大量的文档集合中找到与用户需求相关的 文档列表；而信息抽取系统则旨在从文本中直接获得用户感兴趣的事实信息。 技术不同。信息检索系统通常利用统计及关键词匹配等技术，把文本看成词 的集合( b a g so fw o r d s ) ，不需要对文本进行深入分析理解；而信息抽取往往 要借助自然语言处理技术，通过对文本中的句子以及篇章进行分析处理后才能完 成。 适用领域不同。由于采用的技术不同，信息检索系统通常是领域无关的，而 信息抽取系统则是领域相关的，只能抽取系统预先设定好的有限种类的事实信 息。 另一方面，信息检索与信息抽取又是互补的。为了处理海量文本，信息抽取 系统通常以信息检索系统( 如文本过滤) 的输出作为输入；而信息抽取技术又可 以用来提高信息检索系统的性能。二者的结合能够更好地服务于用户的信息处理 需求。 相比于信息获取系统，信息抽取系统利弊兼有。信息抽取系统更加与知识紧 9 浙江大学硕士学位论文 第2 章理论基础和相关技术 密相关( k n o w l e d g ei n t e n s i v e ) 因而也更难构建，构建难度同时也与领域和场景的 不同而也有所不同。与人工阅读相比，信息抽取还是不够精确。信息抽取比信息 获取需要更多的计算。然而，在需要处理许多文本信息的应用中，信息抽取比信 息获取更高效，因为信息抽取可以减少很多花费在文本分析上的时间另外，在 结果需要在多种语言展示的情况下，由于具有固定格式，无歧义的本质使得信息 抽取的数据具有更完备的可翻译特性。 2 1 2 信息抽取的主要任务 2 1 2 1 命名实体识别 命名实体识别( n a m e de n t i t yr e c o g n i t i o n ，n e ) 是最为基础的类型，此类信 息抽取需要系统能够识别出实体名，并将相应的实体名进行归类。删c 测评识别 并抽取出人名，组织名，日期，时间，地点，以及某种类型的数字表达式( 如货 币数量，百分数) ，并在文本中对这些信息进行标注。n e 具有非常直接的实用价 值，在对文本中的名称、地点、开期等进行标注之后，即提供了对这些信息进行 检索的可能。对于许多语言处理系统，n e 都是其中一个很重要的组件。 2 1 2 2 模板元素构建 模板元素构建( t e m p l a t ee l e m e n tc o n s t r u c t i o n ，t e ) 将特定的描述信息与实 体联系起来。它需要从文本的任何地方将与组织、人物或其它实体相关的基本信 息抽取出来，并将这些信息作为实体的属性进行聚集，形成实体对象。在删c 评 测中，t e 系统需要能够从文本中抽取特定类型的实体信息，并将这些信息填写到 预先定义的小型的属性模板之中。例如对人物实体的模板元素抽取，需要信息抽 取系统能够抽取出预先定义的人物的名称、职务、国籍等属性。 2 1 2 3 参照同指识别 参照同指识别( c o r e f e r e n c er e s 0 1 u t i o n c 0 ) 涉及在进行n e 或t e 任务时， 分析实体在文本中不同地方出现的情况，以及实体在不同场合与其它实体之间的 关系，从而从文本中标识出对同一实体的不同表达方式。c o 可以将散布在文本中 1 0 浙江大学硕士学位论文第2 章理论基础和相关技术 不同地方的同一实体的描述信息连接起来，为创建t e 和s t ( 见下文) 打下基础。 2 1 2 4 模板关系构建 模板关系构建( t 鲫p l a t er e l a t i o nc o n s t r u c t i o n ，t r ) 需要在t e 的基础之上 标识出模板元素之间的关系。t r 是删c - 7 定义的一项新任务，需要抽取模板元素 之间的相互关系。例如： 职员和组织之间的关系( e m p l o y e e - o f ) 产品和生产企业之间的关系( p r o d u c t _ o f ) 以及公司和地区之问的关系( 1 0 c a t i o n _ o f ) 2 1 2 5 情节模板创建 情节模板创建( s c e n a r i ot e m p l a t ep r o d u c t i o n ，s t ) 抽取某一事件中的事件 信息并将事件信息与某个组织、人物或其它实体相关联。s t 需要标识出特定事件 及事件的相关属性，包括将事件中的各个实体填充到事件的相应角色中，通过各 个对象之间的关系，能够还原出整个事件的“原型”。 2 2 隐马尔可夫模型 2 2 1 隐马尔可夫模型的由来 1 8 7 0 年，俄国有机化学家v 1 a d i m i rv m a r k o v n i k o v 第一次提出马尔科夫模 型。但由于缺乏优化马尔可夫模型参数的方法，早期基于马尔可夫链的语言模型 直到二十世纪六十年代末期才开始研究，之后迅速地被应用于语言处理领域“1 。 隐马尔可夫模型作为数字信号的一种统计模型，今天正在各个领域中获得广 泛应用。它的理论基础，是在1 9 7 0 年前后由b a u m 等人建立起来的，随后由c i l u 的b a k e r 和i 阴的j e li n e k 等人将其应用到语言识别之中。 目前h 删被广泛应用于语音识别，机器视觉( 人脸检测，机器人足球) ，图象 处理( 图象去噪，图象识别) ，生物医学分析，以及信息抽取等许多领域。 2 2 2 妞k o v 过程和m a r k o v 链 马尔可夫过程是具有无后效性的随即过程。即t - 时刻所处状态概率只和t r 浙江丈学硕叶：学位论文第2 章理论摹础和相关技术 a 隹篡：v 并且有o 如i j 1 ， 嘞= l ；l 由于k 步转移概率p 。，( k ) 可由转移概率a 。，得到，因此，描述m a r k o v 链的最重 要数据就是转移概率矩阵a 。但a 矩阵还决定不了初始分布，即由a 求不出q 。= o - 的概率，这样，完全描述m a r k o v 链，除a 矩阵之外，还必须引进初始概率矢量， 其中 氕- = p ( q f e t ) ，1 i 剑，显然有。如- 1 ，乃= l f 实际中，r k o v 链的每一状态可以对应于一个可观测到的物理事件。比如天 气预测中的雨、晴、雪等。那么这时它可称之为天气预报的m a r k o v 链模型，根 1 2 浙江大学硕上学位论文第2 章理论草础和相关技术 据这个模型，可以算出各种天气( 状态) 在某一时刻出现的概率。 2 2 3 i 删的基本概念 舢是在m a r k o v 链的基础之上发展起来的，由于实际问题比m a r k o v 链模型 所描述的更为复杂，观察到的事件并不是与状态一一对应，而是通过一组概率分 布相联系，这样的模型就称为删。它是一个双重随机过程。其中之一是m a r k o v 链，这是基本随即过程，它描述状态的转移。另一个随机过程描述状态和观察值 之间的统计对应关系。这样，站在观察者的角度，只能看到观察值，不像m a r k o v 链模型中的观察值和状态一一对应。因而称之为“隐”m a r k o v 模型，即m 附。 更确切地讲，舢提供了一种基于训练数据的概率自动构造识别系统的技术 一个嗍包含两层：一个可观察层和一个隐藏层，可观察层是待识别的观察序列， 隐藏层是一个马尔可夫过程，即是一个有限状态机，其中每个状态转移都带有转 移概率蚴 一个h 删可以看成一个五元组 s ，v ，a ，b ，n ： s = s ，s z ，”js - l v ： v 一，v 2 ，”jv - a = a 。j = p ( q 。+ i = s j lq 。= s i ) ，l i ，j ! 水 b = b j ( u ) = p ( v la tt iq 。= s j ) ，1 鲥剑，1 氢剑) = 。= p ( q t = s 。) ，1 i ! 剑 其中s 是状态集，共有n 个状态： v 是词汇集，共有m 个可能的输出单词： a 是n n 的状态转移矩阵，a i j 表示从状态s 。转换到状态s ，的概率： b 是n m 的释放概率矩阵， b ，( u ) 表示在状态b ，时释放单词v 。的概率： n 是初始状态概率集合，。是第i 个状态作为初始状态的概率。 2 2 4 珈眦的基本算法 h 删有三种经典算法：前向一后向算法( f o r w a r db a c k w a r da l g o r i t h m ) 、 浙江大学硕学位论文 第2 章理论基础和相关技术 v i t e r b i 算法和b a u m _ w e l c h 算法。 2 2 5 前向一后向算法 前向一后向算法是用来计算给定一个观察序列o = 0 。如，o t 以及一个模型 九= ( 兀，a ，b ) 时，由模型九产生出的0 概率p ( o 九) 。算法的计算量在n 可数量级。 前向算法 定义前向变量为 q ( f ) = 户( d l ，d 2 ，0 ：，吼= 只a ) l s f r 初始化 q ( f ) = 乃岛( q ) l f r 递归 q + l ( ，) = 【q ( f h 磅( q “) l s f 丁一1 ，l s - ，s - i 终结 p ( d z ) = 坼( f ) l 。l 后向算法 定义后向变量为 屈( f ) = p ( o ：一l ，o ：一2 ，d r ，吼= 只a ) l s f r l 初始化 屏( f ) = l1 气f r 递归 屈( f ) = 口f 岛( d f + 1 ) 尼+ i ( ，) f = r 一1 ，r 一2 ，1 ，1 f j * 1 终结 p ( d 名) = 届o ) 1 4 浙江丈学硕上学位论文 第2 章理论草础和相关技术 2 2 6 v i t e r b i 算法 v i t e r b i 算法解决了给定一个观察值序列，o = o 倪，o r 以及一个模型 护( 霸a ，b ) 时，在最佳意义上确定一个状态序列q = q ，q 2 。，q t + 的问题。“最佳” 的意义有很多种，由不同的定义可以得到不同的结论。这里讨论的最佳意义上的 状态序列q ，是指使p ( q ，0 i 九) 2 最大时确定的状态序列q 。 算法叙述如下： 定义6 。( i ) 为时刻t 时沿一条路径q ，q r ”q t 且q t = o ，产生出o 。0 2 ，o 。的 最大概率，即有 m a x 6 t ( i ) = p ( q ，q 2 q 。q 。= o 。，o 。，也，o 。a ) 那么，求取最佳状态序列q 的过程为 初始化 点( f ) = 一岛( 0 i ) ，l s i ! ；n 仍( o = o 1 s i n 递归 4 ( j ) 2 罂搿4 一l ( f ) 口f 】q ( q ) ，2 s f l l _ ， 织( j ) = a r g m a 赳4 一i ( f ) 口f 】， 2 s f l 1 _ ， 终结 p 2 恐紧 磊o ) 】) g ；= 鹕m a ) 【西( f ) 】 l 对f 状态序列求取 z = 仍“( 破1 ) ， f = r 一1 ，r 一2 ，l 2 2 7 b a u 旷w e l c h 算法 b a u 玎r w e l c h 算法主要解决h 咖训练，即h m m 参数估计问题。即给定一个观察 值序列o = o 。q ，0 r ，该算法能确定一个模型护( 筇，a b ) ，使得p ( 0 九) 最大由 在前向一后向算法中定义的前向和后向变量，有： 浙江大学硕上学位论文第2 章理论摹础和相关技术 p ( o ”= 吒“) 口# 屯( q 。) 屈+ ，l s ，s r l 扣- j ，l b a u m - 1 c h 算法利用递归的思想，使得p ( 0 九) 局部极大，最后得到模型参数 九= ( 氕，a b ) 定义备( i ，j ) 为给定训练序列0 和模型丸时，时刻t 时r k o v 链所处于o 。状态 和时刻t + 1 为e 。状态的概率，即 t 。( i ，j ) = p ( 0 ，q 。：0 i q 。+ i _ 0 j 九) 可以推导出： e t ( i ，j ) = q ( f ) 6 ，( q + 。) 屈。( _ ，) p ( o 九) 那么，时刻t 时m a r k o v 链处于0 。状态的概率为： ( i ，j ) = p ( o ，q t ：o i 九) = 六( f ，力 j l 2 口，( f ) 屈( o p ( d ，a ) 因此，艺鼻( o 表示从o 。状态转移出去的次数的期望值，丽艺六( f ，d 表示从o 状态转移到0 ，状态的次数的期望值。由此导出b a u m 一l c h 算法中的重估 ( r e e 8 t i 腿t i o n ) 方式嘲： 万，= 鼻( f ) 一磊以力 = 等：广 毒( d 点 i = 等坐l 参( 力 h 姗参数护( 冗，a ，b ) 的求取过程为，根据观察值序列0 和选取的初始模型 驴( 再凡b ) ，由重估公式得到一组新参数万，唧，这样就得到了一个新的模 型 a = ( 石，么，口) 可以证明p ( d 五) p ( d ，即由重估