2001年,美国劳工部受命建立一个网站,帮助人们在美国各地的社区学院、大学和组织中找到继续教育的机会。该部门希望其网站支持对地点、日期、时间、先决条件、教师、主题领域和课程描述进行字段布尔搜索。最终,它也有兴趣挖掘其新数据库中的模式和教育趋势。这是一个主要的数据集成项目,旨在每三个月从数万个个体机构自动收集详细的结构化信息。
第一个也是最大的问题是,许多数据甚至以半结构化形式都不可用,更不用说规范化、结构化形式了。虽然一些较大的组织有内部课程列表数据库,但几乎没有组织公开提供对其数据库的接口。唯一普遍可用的公共接口是为人类浏览而设计的网页。不幸的是,正如预期的那样,每个组织都使用了不同的文本格式。其中一些网页包含二维文本表格;许多其他网页为每个课程提供了一系列程式化的段落;还有一些网页用一个段落的英语散文包含了关于每个课程的所有信息。
因此,这项任务需要从以二维布局和自由散文混合格式化的英语中提取结构化信息——这是一项艰巨的技术挑战,但最终成功地解决了。关于解决方案的更多细节将在后面介绍,但首先,让我们将这个问题放在上下文中。
2005年10月刊的文章讨论了半结构化数据的问题——数据以XML或CSV(逗号分隔值)表格形式松散格式化,未规范化,在不同的模式中,可能还存在重复记录的噪声。但是,世界上大部分信息甚至比这更不结构化——它以所谓的“自然语言文本”形式存在——书面英语和其他语言,存在于网页、公司备忘录、新闻文章、研究报告、电子邮件、博客和历史文档中。
这些文本文档可以被现代搜索引擎有效地搜索和排序,但是字段搜索、基于范围或基于连接的结构化查询、数据挖掘和决策支持通常需要更详细和细粒度的处理。锁定在自然语言中的信息必须首先转换为结构化、规范化的数据库形式。
信息提取旨在做到这一点——它是从非结构化或松散格式化的文本中填充数据库的字段和记录的过程。因此(如图1所示),它可以被视为数据挖掘的先导:信息提取从非结构化或松散结构化的文本中填充数据库;然后数据挖掘发现该数据库中的模式。信息提取涉及五个主要的子任务(如图2所示)
从历史上看,信息提取最常用于新闻文章,从中提取组织、地点和个人姓名并相互关联,但最近信息提取已应用于许多文本格式,包括网页、政府报告、科学文章、电子邮件和法律文件。信息提取有许多引人注目的应用,包括美国劳工部的继续教育课程提取。以下是一些其他应用
一些简单的提取任务可以通过编写正则表达式来解决。对于格式规则性足够的中等复杂文本源的提取,可以通过手动调整的编程规则来准确解决。例如,如果您想从 Amazon.com 的网页中提取书名和作者姓名,您可以依赖于它们以完全一致的格式出现(标题在蓝色栏下方,以粗体显示;作者在下方以超链接显示,前面是单词 by),并编写一个相当简单的 Perl 脚本,大约需要 30 到 60 分钟,使用这些格式规则就可以完成这项工作。但是,如果您还想从 BarnesandNoble.com 和数千家其他书商那里收集信息,您将不得不为每个书商编写新的规则——然后每次其中一个卖家更改其网页布局时,都必须重写这些规则。
当没有人力资源来进行这种级别的规则编写(和持续重写)时,或者当格式线索不可靠或不存在时,信息提取必须依赖于语言本身——单词、词序、语法——也可能与存在的任何微弱、不规则的格式线索相结合。例如,前面描述的美国劳工部的任务就属于这一类。手动调整规则编写的方法有时用于这种情况(并且已被 ClearForest Corporation 和 SRA International 等公司成功使用);然而,随着语言模式变得更加微妙,随着英语用法的例外情况堆积如山,以及随着规则之间越来越多的相互作用,规则编写可能会变得极其复杂。此类系统包含数千条书面规则,这些规则之间存在微妙的相互联系,使得编辑规则极其容易出错,这并不罕见。
在过去的十年中,统计和机器学习方法在信息提取中的使用发生了革命性的变化。这些方法自动调整其自身的规则或参数,以最大化在一组由人工正确标记的示例文本上的性能。换句话说,您不必尝试手动调整复杂的提取规则,而是通过自己执行提取任务,向机器展示在特定示例文本上应该做什么。然后,机器从这些示例中概括出来,适当地调整其自身的规则和参数。对于复杂的提取任务,可能需要许多示例(数百或数千个),但标记数据通常仍然比手动调整规则容易得多,并且可以由技能较低的兼职人员完成。在许多情况下,机器学习比人工调整的方法获得更高的准确率。
其中一些机器学习方法使用决策树或 if-then-else 规则。在系统中使用机器学习来创建基于格式的提取器(称为包装器)时,通常会遵循这种方法,如 Amazon.com 示例中所述。越来越流行的是机器学习方法,这些方法使用大量相对简单的输入特征,但为这些特征分配微妙交互的实值权重。例如,单词 said 是一个弱指标,表明人名可能即将出现。这些方法分配一个权重,其中“前一个单词是 said”特征投票支持下一个单词是人名;然后,通过结合来自许多此类适当加权、弱指示性特征的证据,可以做出非常准确的提取决策。
具有简单特征的一种这样的统计模型是 HMM(隐马尔可夫模型)——一种在状态转换上具有概率并在每个状态单词发射上具有概率的有限状态机。在 20 世纪 90 年代,HMM 开始广泛用于从英语散文中提取信息。机器的状态被分配给不同的数据库字段,与单词序列相关的最高概率状态路径指示单词的哪些子序列属于这些数据库字段。
最近,人们对将有限状态机的优势与更复杂的功能相结合产生了兴趣——条件概率模型(包括最大熵马尔可夫模型和条件随机场)使这种前景成为可能。这些模型在信息提取竞赛中名列前茅(例如,BioCreative 竞赛,旨在从生物信息学研究论文中提取蛋白质名称)。条件随机场已被用于整合信息提取的更多阶段,不仅包括分段和分类,还包括规范化和去重,使用的模型超出了有限状态机。
美国劳工部的课程提取问题由一家名为 WhizBang Labs 的公司使用多种机器学习组件的组合来解决。为了找到可能包含课程列表的网页,文本分类与网络爬虫结合使用。统计语言建模方法假设了不同字段的分段和分类,这些字段也被放入一个分类器中,该分类器负责对一个课程与另一个课程进行粗粒度分段。然后使用一种称为范围学习的方法,从每个页面动态学习格式(类似包装器)规则性,而无需人工干预。逻辑回归分类器用于完成关联和去重阶段。(未使用条件随机场只是因为它们尚未开发出来。)最终,该项目被认为是成功的——数据以足够的准确率提取出来,因此可以将其直接存入网站的结构化数据库中。
自动化提取方法的准确率差异很大,具体取决于文本输入的规则性和所用提取方法的强度。从格式化、高度规则的数据库生成的网页(例如 Amazon.com 上的网页)中提取信息可以做到完美准确。从其他有些规则的文本(例如邮政地址块或研究论文引文)中提取信息的准确率通常在 90% 多的中到高水平。对于从标准新闻文章中提取人名、公司名和地名,90% 多的中等准确率现在已成为标准。(然而,从网页中提取这些实体名称更困难,准确率在 80% 左右。)蛋白质名称的提取更困难,因为它们的命名方案更不规则;最近一次竞赛的准确率在 80% 左右。
提取的关联阶段的成功通常更困难,因为正确的最终答案还需要对所有应关联的字段进行正确的分段和分类。此外,在许多领域(例如新闻文章)中,某些关联或关系的证据可能需要理解英语用法和含义的复杂细微之处。新闻报道中关系提取的准确率通常在 60% 左右。
另一方面,当需要处理的字段更多时,去重的性能通常更高。新闻文章中实体名称的去重准确率通常在 70% 或 80% 左右。多字段研究论文引文的去重准确率在 90% 以上。
除了超规则或微不足道的应用程序之外,任何应用程序都不可能达到完美的准确率——人类语言的细微之处和例外情况太深刻了。要求完美准确率的信息提取客户应该被提醒,现有的手动实践也充满了错误。例如,典型的医院患者联系记录和公司数据库充满了排版错误和重复项。即使当付费专家(语言学家)的任务是标记文本(用于训练机器学习提取器)时,他们对同一文档的结果也存在惊人的差异;多个人工标记新闻文章以获取实体关系的结果之间的一致性通常最多只有 70%。在许多情况下,自动化方法和人工处理的协同组合可以产生最佳的准确率和吞吐量。
越来越多的信息提取解决方案正在商业化。如果您正在考虑使用其中一种,以下是一些您应该问自己和供应商的问题
您还应该考虑开源解决方案和内部开发。免费的信息提取系统包括 GATE (http://gate.ac.uk/ie/annie.html)、MALLET (http://mallet.cs.umass.edu)、MinorThird (http://minorthird.sourceforge.net) 和 Road Runner (http://www.dia.uniroma3.it/db/roadRunner)。还有其他用于文档分类 (http://www.cs.cmu.edu/~mccallum/bow/) 以及文档检索和匹配 (http://lucene.apache.org, http://www.lemurproject.org/indri) 的开源解决方案。
信息提取在过去十年中取得了很大进展,进一步的研究和工业创造力继续推动着这一进展。提取正在应用于越来越复杂的问题,并且正在设计得更加复杂,但易于非技术最终用户使用。积极的研究趋势包括以下内容
估计不确定性,管理多重假设。 正如已经讨论的那样,提取永远不会完全准确,当最终答案是级联处理步骤的结果时,就会出现一些最具问题性的后果,错误会累积到高得无法使用的程度。人们越来越关注维护从一个步骤到另一个步骤的多个提取假设的方法,并使用概率信息来组合假设。这种方法不是让错误累积,而是实际上允许后续处理步骤纠正早期步骤中犯的错误。这些方法将提高关联和关系提取的准确率,并实现提供更深入分析并将提取直接与数据挖掘集成的新应用。
更轻松的训练,半监督学习,交互式提取。 机器学习方法通常提供最准确的提取器,但收集必要的训练数据可能非常耗时和乏味——特别是如果急躁的最终用户是数据标记人员。半监督机器学习的新研究通过巧妙地(有些人会说几乎神奇地)利用大量未标记数据来提高学习效率,从而减少了所需的标记数据量。此外,称为“交互式信息提取”的方法从不完善的自动标记数据开始,然后通过突出显示低置信度字段来更快地进行手动更正,此外,使用软约束在人工更正一个字段后自动更正其他字段。
本文主要讨论了构建结构化数据库的传统信息提取。然而,当目标是主题趋势分析或大型文档集合的粗略摘要时,一个有趣的替代方案是使用文本提取和数据挖掘的松散混合。这些方法利用任何可用的有限结构化信息(例如电子邮件消息的日期、发送者和接收者,或仅文档边界),然后使用足够鲁棒的数据挖掘技术直接对与此有限结构相关的原始文本进行操作。
例如,潜在狄利克雷分配是一种文档聚类方法,它提供了文档集合中讨论的主题的鸟瞰图(主题由自动发现的突出关键字集合表示)。作者-接收者-主题模型 给出了大型电子邮件集合的主题摘要,识别与不同主题相关的突出发送者和接收者,并识别此电子邮件社交网络中具有相似角色的人员。例如,给定电子邮件消息正文中的文本,以及“收件人”、“发件人”和“抄送”标题中的人员,作者-接收者-主题模型自动发现一组主题,这些主题总结了社交网络内的通信,以及谁与谁谈论了哪些主题。此模型的应用之一是在大型公司中寻找专家。
组主题模型 发现的是组而不是角色,并且已用于通过挖掘美国参议院 16 年的投票记录以及相应法案的文本来识别主题和志同道合的立法者之间的关联。克莱因伯格的词突发算法自动检测随时间变化的趋势;例如,当应用于美国总统国情咨文演讲的文本时,它显示单词 slaves 从 1859 年到 1863 年爆发,单词 atomic 从 1947 年到 1959 年爆发,而 inflation 从 1971 年到 1980 年爆发。Intelliseek.com 已将类似的方法应用于博客的趋势分析。
万维网是世界上最大的知识库,并且正在不断地由数百万人进行扩充和维护。然而,它以一种旨在供人类阅读的形式存在,而不是以数据库形式存在,数据库形式具有可以被计算机轻松操作和理解的记录和字段。尽管语义网前景广阔,但英语和其他自然语言文本的使用将继续成为 Web、电子邮件、新闻文章和其他地方进行通信和知识积累的主要媒介。
最终,我们将达到几乎任何问题的答案都可以在网上找到的程度,但我们将不得不浏览越来越多的材料才能找到它。改进搜索工具的下一步将是从文档的关键字搜索过渡到更高级别的查询:搜索命中将是对象(例如人或公司)而不是仅仅是文档的查询;结构化并返回从多个页面集成和综合的信息的查询;以及以自然语言问题(“美国前三位女参议员是谁?”)陈述并以简洁的回答回答的查询。
互联网革命的前半部分包括创建用于轻松数据共享的广域网,使人类能够访问巨大的知识和服务存储库。互联网革命的后半部分尚未到来。当机器可以访问这个巨大的知识库时,它就会发生,因此我们能够在其上执行模式分析、知识发现、推理和半自动决策。信息提取将是使这一切成为可能的解决方案的关键部分。
ANDREW McCALLUM 是马萨诸塞大学阿默斯特分校的副教授,也是信息提取与合成实验室的主任。他曾任职 WhizBang Labs 公司的研发副总裁,该公司利用机器学习技术从网络中提取信息。在 1990 年代后期,他曾在 Justsystem Pittsburgh 研究中心担任研究科学家,在那里他率先创建了 CORA,这是一个早期的研究论文搜索引擎,使用机器学习进行网络爬取、提取、分类和引文分析。他在卡内基梅隆大学担任博士后研究员,并在 1995 年于罗切斯特大学获得博士学位。他是《机器学习研究期刊》的行动编辑。在过去的 10 年里,McCallum 一直活跃于统计机器学习在文本领域的应用研究,尤其是在信息提取、文档分类、有限状态模型、半监督学习和社交网络分析方面。(www.cs.umass.edu/mccallum)。
原始材料
达特茅斯学院计算机科学系 2006 年秋季课程列表
CS121 Java 编程
MWF 1330-1430, Sutton
入门课程,涵盖条件语句、
迭代和 I/O。无先修课程要求。
CS383 人工智能
TuTh 1030-1200, Cash
逻辑、搜索、贝叶斯网络、机器学习
和机器人技术。需要先修 CS245。
CS392 计算语言学
WF 1500-1630, Quass
涵盖 N-grams、隐马尔可夫模型、解析、
和翻译。先修课程为 CS383 和 Stat202。
与 Ling380 交叉列出。
达特茅斯学院语言学系
2006 年秋季课程列表
Ling101 语言学导论由 Wei Li 博士在 Smith Hall 202 房间授课。本课程介绍音韵学、形态学、常用语法模式。上课时间为每周一和
周三上午 10:30 至中午 12:00。
Ling380 计算语言学,由 Dallan 博士授课
Quass 在 Sutton 102 房间授课,本课程涵盖 N-grams、
隐马尔可夫模型、解析和机器翻译。上课时间为每周三和周五下午 3 点至 4:30。您必须先修读 CS383 和 Stat202。与 CS392 交叉列出。
Appelt, D. E., Hobbs, J. R., Bear, J., Israel, D., Kameyama, M., Kehler, A., Martin, D., Myers, K., and Tyson, M. 1995. 《第六届信息理解会议 (MUC-6) 会议论文集》。Morgan Kaufmann 出版社。
Blei, D., Bagnell, D., and McCallum, A. 2002. 基于作用域的学习及其在信息提取和分类中的应用。《不确定性人工智能 (UAI)》。
Blei, D., Ng, A., and Jordan, M. 2003. 潜在狄利克雷分布。《JMLR 3:》 993–1022.
Bruninghaus, S., and Ashley, K. D. 2001. 利用信息提取方法改进法律案例文本的表示。《第八届国际人工智能与法律会议论文集》。
Carreras, X., Marques, L., and Padro, L. 2002. 使用 Adaboost 的命名实体抽取。《CoNLL-2002 会议论文集》: 167–170.
Craven, M., DiPasquo, D., Freitag, D., McCallum, A., Mitchell, T., Nigam, K., and Slattery, S. 1998. 从万维网中学习提取符号知识。《第十五届人工智能全国会议 (AAAI-98) 会议论文集》: 509–516.
Culotta A., and McCallum, A. 2005. 减少结构化预测任务的标注工作量。《AAAI》。
Freitag, D. 1998. 从 HTML 中提取信息:通用学习方法的应用。《第十五届人工智能会议 (AAAI-98) 会议论文集》: 517–523.
Freitag. D. 1998. 非正式领域信息提取的机器学习。博士论文,卡内基梅隆大学。
Haghighi, A., Toutanova, K., and Manning, C. D. 2005. 语义角色标注的联合模型。《第九届计算自然语言学习会议》: 173–176.
Kushmerick, N., Weld, D., and Doorenbos, R. 1997. 信息提取的包装器归纳。《第十五届国际人工智能会议论文集》: 729-735.
Lawrence, S. 2001. 在线还是隐形?《自然》 411(6837): 521.
McCallum, A., Nigam, K., Rennie, J., and Seymore, K. 2000. 利用机器学习自动化构建互联网门户。《信息检索期刊 3:》 127–163.
McCallum, A., and Wellner, B. 2004. 应用于名词共指的身份不确定性的条件模型。《神经信息处理系统 (NIPS)》。
McDonald, R., and Pereira, F. 2005. 使用条件随机场识别文本中的基因和蛋白质提及。《BMC 生物信息学 6》(增刊 1)。
Miller, S., Guinness, J., and Zamanian, A. 2004. 使用词簇和判别训练进行名称标记。《HLT-NAACL 会议论文集》。
Minkov, E., Wang, R., and Cohen, W. 2004. 从电子邮件中提取个人姓名:将命名实体识别应用于非正式文本。准备中;http://www.cs.cmu.edu/ wcohen/pubs-x.html。
Muslea, I., Minton, S., and Knoblock, C. 1998. Stalker:用于半结构化、基于 Web 的信息源的学习提取规则。《AAAI 人工智能与信息集成研讨会论文集》。
Ng, V., and Cardie, C. 2002. 改进机器学习方法以解决共指消解问题。《第四十届计算语言学协会年会会议论文集》。
Pasula, H., Marthi, B., Milch, B., Russell, S., and Shpitser, I. 2002. 身份不确定性和引文匹配。《神经信息处理系统进展》。
Pinto, D., McCallum, A., Lee, X., and Croft, W. B. 2003. 文本分类中分类器的组合。《提交至 SIGIR ’03:《第二十六届国际 SIGIR 信息检索研究与开发会议论文集》》。
Ray, S., and Craven, M. 2001. 在隐马尔可夫模型中表示句子结构以进行信息提取。《第十七届国际人工智能联合会议论文集》。Morgan Kaufmann 出版社。
Soderland, S. 1997. 学习从万维网中提取基于文本的信息。《第三届国际知识发现与数据挖掘会议论文集》。
Sutton, C., and McCallum, A. 2005. 用于迁移学习的条件随机场的组合。《自然语言处理经验方法》。
Yeh, A., Morgan, A., Colosimo, M., and Hirschman, L. 2005. BioCreative 任务 1a:基因提及查找评估。《BMC 生物信息学 6》(增刊 1)。
Zelenko, D., Aone, C., and Richardella, A. 2003. 关系提取的核方法。《机器学习研究期刊 3》: 1083–1106.
最初发表于 Queue 第 3 卷,第 9 期—
在 数字图书馆 中评论这篇文章
Alon Halevy - 为什么你的数据无法混合
当独立的各方为同一领域开发数据库模式时,它们几乎总是彼此大相径庭。这些差异被称为语义异构性,它也出现在多个 XML 文档、Web 服务和本体中——或者更广泛地说,只要存在多种结构化数据主体的方式。半结构化数据的存在加剧了语义异构性,因为半结构化模式一开始就更加灵活。为了使多个数据系统相互协作,它们必须理解彼此的模式。
Natalya Noy - 从混乱中理出秩序
对于过去十年在人类和机器可处理的在线信息量方面带来了“大爆炸”,可能没有什么争议。它所刺激的趋势(以及许多其他趋势)中有两个是:首先,已经转向比以前存储大部分电子数据的传统集中式关系数据库更灵活和流动的(半结构化)模型;其次,今天可用的信息实在太多了,人类无法处理,我们真的需要机器的帮助。
C. M. Sperberg-McQueen - XML <和半结构化数据>
词汇表设计者可以要求 XML 数据完全规则,也可以允许少量或大量变化。在极端情况下,XML 词汇表可以有效地表示除了所有格式良好的 XML 所需的规则之外,根本没有其他规则。由于 XML 语法仅记录存在的内容,而不是可能存在的所有内容,因此稀疏数据不会使 XML 表示显得笨拙;XML 存储系统通常构建为优雅地处理稀疏数据。
Adam Bosworth - 从网络中学习
在过去的十年中,我们看到了计算领域的一场革命,它在范围和影响方面超越了迄今为止所见的一切,而且也超越了我们对构成“好”和“坏”计算的思考方式。