英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
大规模词汇分类中基于图的错误IsA关系检测
摘 要
知识库（KB）在人工智能中起着重要作用。在手动和自动构建Web级知识库方面已经付出了很多努力。与手动构建的KB相比，自动构建的KB范围更广，但噪音更大。在本文中，我们研究了提高自动构建的Web规模知识库的质量的问题，特别是isA关系的Lexi-cal分类法。我们发现，这些税收规范通常包含周期，这些周期通常是由不正确的isA关系引入的。受此观察的启发，我们引入了两种模型来检测周期中不正确的isA关系。第一个通过提取有向无环图来消除循环，而另一个通过将节点分为不同级别来消除循环。我们在Probase（最先进的，自动构建的网络规模分类标准）上实现我们的模型。在处理了数百万个关系之后，我们的模型以91％的精度消除了74,000个错误关系。
介 绍
机器智能依赖于各种知识库，这些知识库是手动或自动构建的。手动构建的知识库示例包括WordNet（Miller 1995）和Cyc（Lenat and Guha 1989），自动构建的知识库示例包括KnowItAll（Etzioni et al。2004），NELL（Mitchell et al。2015）和Probase（Wu等人（2012）。手动构建的知识库非常精确，但是规模有限，而自动构建的知识库覆盖率很高，但准确性相对较低。
本文的目的是设计算法，以检测和消除自动构建的知识库中的错误。特别是，我们专注于词汇分类法，这是一种重要的知识库类型，主要由isA关系组成，例如apple isA fruit，其中“ isA”表示下位关系。分类法很重要，因为它们将实例映射到概念，从而使机器在理解文本时可以获得泛化和专业化的能力。因此，分类法，尤其是那些具有较大覆盖范围的机器生成的分类法，已被广泛用于各种文本理解任务中。因此，检测和消除分类法中的错误对于提高机器智能至关重要。
在这项工作中，我们以数据驱动的最新税收法规Probase（Wu等人，2012年）为例，对分类生物进行清洁。尽管我们专注于Probase，但我们的解决方案也适用于其他数据驱动的分类法。Probase包含1600万个isA关系，这主要是通过使用Hearst句法模式从17亿个网页中自动提取的（Hearst 1992）。在Probase中，每个isA关系都与网络语料库中观察到的频率相关联。据报道，Probase的准确性为92％（Wu等人，2012），低于WordNet。表1显示Probase中的一些错误。大多数错误是由语料库中的错误或信息提取算法中的错误引起的。例如，以下句子“ ...中有错字（应该是一个）”。使巴黎成为令人兴奋的城市”通过使用诸如模式的提取算法导致巴黎令人兴奋的城市的提取。
|
实体 isA 概念 |
实体 isA 概念 |
|
令人兴奋的城市 isA 巴黎 |
电池 isA 燃料电池 |
|
汽车 isA 铅酸蓄电池 |
原因 isA 海啸 |
|
音乐视频 isA youtube视频 |
甜 isA 葡萄糖 |
|
世界杯 isA 足球 |
葡萄 isA 紫色 |
|
学院 isA 篮球 |
果汁 isA 番茄 |
表1：Probase中不正确的isA关系的示例
为了解决这个问题，我们需要首先检测到分类学中的有害关系。对于这个问题有两种幼稚的方法。
- 使用频率。与低频的关系可能是可疑的，因为错别字或在语料库中很少观察到算法提取问题。但是，isA关系的频率信息本身遵循具有长尾巴的幂律分布，这意味着大多数带有或不带有错误的关系都具有较低的频率。例如，Probase中大约有700万个边缘的频率为1。但是我们的样本测试表明其中78％是正确的。因此，我们不能简单地将所有低频关系识别为可疑边缘。
- 使用外部知识。另一种方法是采用外部知识库可消除干扰并改善分类法的质量。然而，某些知识库（例如Probase）具有许多特定的概念，而在许多其他知识中却不存在边缘基地。结果，一个会员的会员关系
一个特定概念的实例将在外部知识库中丢失。例如，Probase有270万个概念，而Yago只有48万个类型，DB-pedia只有700种类型。由于Probase的概念覆盖范围和外部知识库之间的巨大差距，因此无法使用它们来查找Probase中的冲突。
在本文中，我们建议使用结构信息。手动和自动构建的分类法之间的主要区别在于，它是否是有向无环图（DAG），即分类法中没有循环。图1展示了DAG分类法，其中许多特定实体（例如iphone 6，nexus 5，shanghai）位于较低级别，而更抽象的概念（如物，概念，对象）位于较高级别。
图1：理想的分类示例
Probase中周期的主要来源是：
- 歧义：单词或短语可能具有多种含义，在Probase中没有区别。因此，Word可能是指Microsoft Word，它是一种软件（例如实体），或者其字面意思是抽象概念。因此，单词isA软件和软件isA单词都是正确的，并且存在于Probase中。这两个关系构成一个循环。
- 错误的isA关系：错误的isA关系可能是提取出来的，例如令人兴奋的城市isA巴黎，这会导致一个周期（如图2所示）。
周期是查找可疑关系的重要来源。我们分别采样了大小为2和3的整个Probase循环中的100个，并将它们与分别对大小为2和3的100个子图（带有或不带有循环）进行随机采样的空模型进行了比较。然后，我们手动判断每个子图是否包含错误的isA关系。
我们报告了z得分，该得分显示了偏离度-循环样本和空模型之间的关系。的结果如表2所示。我们可以看到大多数循环包含错误的isA关系，这在统计上是有意义的，因为相应的随机子结构倾向于具有较少数量的错误isA关系并且z得分足够大。我们还在图2中说明了具有错误关系的循环的示例。
表2：Probase中的周期统计
受以上观察的启发，我们使用循环消除方法来识别错误的isA关系。尽管以前已经研究过此问题，但是由于以下挑战，无法应用现有的解决方案：
1.首先，枚举图中的所有周期就是计算-盟友辛苦。在最坏的情况下，图中的循环数是指数级的。用于检测图中所有周期的蛮力枚举方法在网络规模的数据驱动分类法上具有计算上的优势。
2.其次，并不是所有的isA关系都循环错误。因此，我们需要一种量化可信度的指标，以确定哪种关系是错误的。
为了克服上述挑战，我们探索两种方法，并为每种模型提出有效的解决方案。第一个目标是从给定的图形中提取DAG，为此我们提出了一种有效的方法（最大反馈弧集：MFAS），以最大程度地减少移除边缘的可信赖度。另一种方法是将问题建模为在分类法中为每个节点分配级别（整数），这样特定概念或实例的级别较低，而抽象概念的级别较高。因此，由于错误的isA关系，我们可以消除从高级节点（抽象概念）到低级节点（特定实体）的边缘。总而言之，我们做出了以下贡献：
首先，我们证明周期是在数据驱动分类法中找到错误isA关系的良好指标。
其次，我们提出了基于图的模型及其算法解决方案，以找到错误的isA关系。
- 我们通过处理现实生活中的网络规模分类法来验证我们的解决方案。
基于DAG分解的模型
理想的分类法是无周期的，并且具有以下结构
如前一节所述的DAG。这促使我们通过DAG分解框架对问题进行建模（请参见Def 1）。因此，错误的isA关系的标识等同于非循环子图的标识。
定义1（DAG分解）给定有向图G（V，E），找到G的子图D(V,ED)，使得D是非循环的并且q(ER)最小，其中ER= E EDq(ER)是ER的惩罚函数。由于ED和ER是互为补充的，因此为了简化起见，我们仅关注ER的评估。总的来说，我们希望ER中的大多数成员是真正错误的isA关系，而没有误报。因此，定义q（ER）的一般原则是ER中每个成员的信任度之和。结果，在不删除高度可靠的边缘的情况下，最小化q（ER）是找到最可疑isA关系的适当目标。
MFAS模型和算法
定义q(ER)的一种方法是，当n w(e)是边e的可信赖度时，q(ER) = eisin;ER w(e)；w（e）。也就是说，总和ER中所有边缘的可信赖分数。形式化的问题在Def 2中。该模型是加权最小反馈电弧集问题（加权MFAS问题），这是经典的NP-Hard问题（Even等人，1998）。
定义2（MFAS）给定加权有向图
G（V，E），其中每个边缘与权重w（e）相关联，找到一个边缘子集ERsube;E，使得（1）D（V，E ER）是DAG，而（2）权重和ER（即 eisin;ER w(e)）为最小化。
由于问题是NP-Hard，因此我们将重点放在有效的近似算法上。具体来说，我们提出一种贪婪算法：重复查找一个循环并删除权重最低的所有边，直到剩余图形中没有循环为止。显然，结果图必须是DAG。但是，可能已去除了太多的边缘，从而使去除的边缘的累积重量与最佳值相差甚远。Demetrescu等。（Demetrescu和Finocchi 2003）提出了一种微妙的启发式方法来改进它。该算法有两个步骤。第一步与基本的贪婪策略相同。在第二步中，它以边缘权重的降序检查逐个删除的边缘。对于删除的每个边，它将尝试将边重新添加到图形中，并判断添加是否创建了循环。如果不是，则边缘重新添加。显然，与基本贪婪算法相比，该算法去除了更少的边缘以生成DAG。实际上，已证明该改进算法实现了lambda;逼近，其中lambda;是图中最长循环的长度。该算法的时间复杂度为O（nm）（Demetrescu and Finocchi 2003），其中n是节点数，m是图中的边数。
可信度指标
我们的下一步是定义边缘权重以量化信任度。首先，我们介绍一个基本指标，该指标将频率用于Probase中的isA关系。然后，我们提出了如何改进该指标的方法。
基本指标：频率回想一下Probase中每个isA关系X isA Y与在主体中观察到isA关系的频率相关。我们用wf（e）表示边缘e的频率。直观上，较大的权重意味着较高的可信度。示例1对此进行了说明。我们的经验研究表明，wf在表征isA关系的可信赖性方面是有效的。我们分别在Probase中从某些频率范围中随机抽取50个边缘，然后手动判断其正确性。表3显示，频率越高，意味着可信度越高。
示例1 Probase中china isA国家的频率为10723，这意味着存在10723个包含isA关系的语句。相反，令人兴奋的城市是巴黎的频率只有一个。显然，前者比后者更值得信赖。
改进的度量标准：使用同义数字但是，上述度量标准有一个明显的缺点：对于低频边缘，它的判别性较小。在频率为1的700万个边缘中，只有一小部分是错误的。因此，除了频率外，我们还需要整合更多的信号。
对数据驱动分类法的简单观察是，抽象概念总是有许多下义词（含义更具体的词），但是特定概念或实体总是没有或只有很少的下义词。示例2说明了这些事实。
示例2（同义词）在Probase中，概念有18,832个下位词。相比之下，像“激动人心的城市”这样更具体的概念有30个下义词，例如巴黎，伦敦，上海。而且，大多数特定实体（例如上海）都没有下义词。
因此，给定一个isA关系X isA Y，Y通常比X更抽象，并且Y的下位数应大于X的下位数。差异越大，边缘越值得信赖。更正式地说，假设hypo（X）为X的下义词的数量，我们定义Ph来表示对isA关系正确性的信念：
Ph
(X isA Y ) = log (1 hypo(Y ) /hypo(X) ) (1)
如果Ph值越大，则isA关系成立的可能性就越大。请注意，当hypo（X）= 0时，Ph是不确定的。但是，我们将在下一个小节中显示，我们只需要处理分类法中强连接的组件中的节点，这些节点的次值始终大于0。
我们将Ph与wf相乘，以得出等式2中的新指标wfh。显然，Ph起着修正因子的作用。我们使用它来区分具有相同频率的边缘。示例3说明了新指标的有效性。
wfh(e) = wf (<e
剩余内容已隐藏，支付完成后下载完整资料</e
资料编号：[237768]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
