基于图错误的IsA关系检测在大规模词汇分类中的应用外文翻译资料

英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

基于图错误的IsA关系检测在大规模词汇分类中的应用

Abstract

知识库（KB）在人工智能中起着重要作用。人工和自动构建网络级知识库已经付出了很多努力。与手动构建的KB相比，自动构建的KB更宽，但噪声更多。在本文中，我们研究提高自动构建的网络规模知识库的质量问题，特别是isA关系的词汇分类。我们发现这些分类法通常包含循环，这些循环通常是由不正确的isA关系引入的。受这一观察的启发，我们引入两种模型来检测来自周期的不正确的isA关系。第一个通过提取有向无环图来消除循环，另一个通过将节点分组到不同的级来消除循环。我们在Probase上实现了我们的模型，Probase是一种先进的自动构建的网络分类法。在处理了数千万个关系之后，我们的模型以91％的准确度消除了74,000个错误关系。

Introduction

机器智能依赖于手动或自动构建的各种知识库。手动构建的知识库的例子包括WordNet（Miller 1995）和Cyc（Lenat and Guha 1989），自动构建的知识库包括KnowItAll（Etzioni et al。2004），NELL（Mitchell et al。2015）和Probase（Wu等，2012）。人工构建的知识库高度精确，但规模有限，而自动构建的知识库覆盖率高，准确度相对较低。

本文的目标是设计算法来检测和消除自动构建的知识库中的错误。特别是，我们关注词汇分类法，这是一种主要由isA关系组成的重要类型的知识库，例如苹果是一种水果，其中“isA”是指地名关系。分类法很重要，因为它们将实例映射到概念，从而使机器在理解文本时获得泛化和专业化的能力。因此，分类法，尤其是那些覆盖范围较大的机器生成的分类法，已被广泛用于各种文本理解任务。因此，检测并消除分类法中的错误对于提高机器智能至关重要。

在这项工作中，我们使用最先进的数据驱动分类标准Probase（Wu et al。2012）作为分类清理的一个例子。虽然我们专注于Probase，但我们的解决方案适用于其他数据驱动的分类法。 Probase包含1600万个isA关系，这些关系通过主要使用Hearst句法模式（Hearst 1992）从17亿个网页中自动提取。在Probase中，每个isA关系与在网络语料库中观察到的频率相关联。据报道，Probase的准确率为92％（Wu et al。2012），低于WordNet。表1显示了Probase中的一些错误。大多数错误是由语料库中的错误或信息提取算法造成的错误引起的。例如，在下面的句子“......使巴黎如激动人心的城市”中出现一个错字（应该是an），通过使用诸如提取模式的算法导致令人兴奋的城市isA Paris的提取。

表1: 在probase里不正确的isA关系的例子

为了解决这个问题，我们需要首先检测这个问题，恶意是分类学中的一种关系。这个问题有两种天真的方法。

bull;使用频率。低频率的关系可能是可疑的，因为由拼写错误或算法提取问题引入的关系在语料库中很少被观察到。然而，isA关系的频率信息本身遵循具有长尾的幂律分布，这意味着大多数有误差或无误差的关系都具有低频率。例如，Probase中约700万条边缘的频率为1。但是我们的样本测试表明其中78％是正确的。因此，我们不能简单地将低频率的所有关系识别为可疑边缘。

bull;使用外部知识。另一种方法是采用可用的外部知识库来消除冲突并提高分类的质量。但是，一些知识库如Probase有许多其他许多知识库中不存在的具体概念。因此，外部知识库中将缺少实例与特定概念的成员关系。例如，Probase有270万个概念，Yago只有48万个类型，DBpedia只有700个类型。由于Probase概念覆盖与外部知识库之间存在巨大差距，因此无法使用它们来发现Probase中的冲突。

在本文中，我们建议使用结构信息。手动和自动构建的分类法之间的主要区别在于它是否是有向无环图（DAG），即分类中没有周期。图1说明了一个DAG分类法，其中许多特定实体（如iphone 6，nexus 5，shanghai）位于较低级别，而更抽象的概念（如事物，概念和对象）位于较高级别。

图1：一个理想的分类示例

Probase的主要周期来源是：

bull;歧义：单词或短语可能有多种感觉，这些感觉在Probase中没有区别。因此，单词可能指的是Microsoft Word，它是一种软件（作为一个实体），或者其字面含义是一个抽象的概念。因此，两个词是软件和软件是一个词是正确的，存在于Probase中。这两个关系构成一个循环。

bull;错误的关系：错误的关系可能被提取出来，例如激动人心的城市是巴黎，这会导致一个循环（如图2所示）。

周期是定位可疑关系的重要来源。我们分别抽取了大小为2和3的整个Probase循环中的100个，并将它们与分别随机抽样大小为2和3（有或没有循环）的100个子图的空模型进行比较。然后我们手工判断每个子图是否包含错误的isA关系。我们报告z-分数，其显示了来自周期和空模型的样本之间的偏差程度。结果如表2所示。我们可以看到，大多数循环包含错误的isA关系，这在统计学上是显着的，因为相应的随机子结构趋向于具有较少数量的错误的isA关系并且z分数足够大。我们还举例说明了图2中具有错误关系的循环。

图2：循环的例子

表2：Probase里循环的数据

受上述观察的启发，我们使用循环消除方法来识别错误的isA关系。尽管之前已经研究过这个问题，但由于以下挑战，现有解决方案无法应用：

1.首先，枚举图中的所有周期在计算上很难。在最糟糕的情况下，图中的周期数是指数。用于检测图中所有周期的暴力枚举方法在网络规模的数据驱动分类法中计算上是禁止的。

2.其次，并不是所有的周期关系都是错误的。因此我们需要一个度量来量化可信度，以确定哪个关系是错误的。

为了克服上述挑战，我们探索了两种方法，并为每个模型提出了一个有效的解决方案。第一个目标是从给定的图中提取DAG，为此我们提出了一种有效的方法（最大反馈弧集合：MFAS），以最小化去除边缘的可信度度量。另一种方法将问题建模为将分级（整数）分配给分类中的每个节点，以便特定概念或实例具有较低级别，而抽象概念具有较高级别。因此，我们可以消除高层节点的边缘（抽象概念）到低级别节点（特定实体）是错误的关系。 总之，我们做出了以下贡献：

首先，我们表明循环是在数据驱动分类法中发现错误的isA关系的好指标。

其次，我们提出了基于图的模型以及他们的算法解决方案，以找出循环中错误的isA关系。

第三，我们通过处理真实的网络级分类来验证我们的解决方案。

基于DAG分解的模型

理想的分类标准是无周期的，并且具有前一节讨论的DAG结构。这激励我们通过DAG分解框架来模拟我们的问题（参见定义1）。因此，错误isA关系的识别等同于非循环子图的识别。

定义1（DAG分解）给定一个有向图G（V，E），找到G的子图D（V，ED），使得D是非循环的并且q（ER）被最小化，其中ER = E \ ED和q ER）是ER的惩罚函数。

由于ED和ER是相辅相成的，因此我们可以将注意力集中在ER的评估上。总的来说，我们希望ER中的大多数成员确实是错误的，而不会有误报。因此，定义q（ER）的一般原则是ER中每个成员的可信度的总和。因此，最小化q（ER）是找到最可疑的isA关系而不去除高度可靠的边的适当目标。

MFAS模型和算法

定义q（ER）的一种方式是，当w（e）是边的可信度时。也就是说，ER中所有边的可信得分的总和。形式化问题在Def 2中。该模型是一个加权最小反馈弧集问题（加权MFAS问题），它是一个经典的NP-Hard问题（Even et al。1998）。

定义2（MFAS）给定一个加权有向图G（V，E），其中每个边与一个权重w（e）相关联，找到一个边的子集ERsube;E，使得（1）D（V，E \ ER）是一个DAG和（2）权重之和）被最小化。

由于问题是NP-Hard，我们专注于有效的近似算法。具体来说，我们提出了一个贪心算法：重复查找一个循环，并删除所有重量最低的边，直到剩余图中没有循环。显然，得到的图必须是DAG。但是，太多的边缘可能已被移除，因此移除的边缘的累积重量远离最佳值。 Demetrescu等人（Demetrescu和Finocchi 2003）提出了一个微妙的启发式来改进它。该算法有两个步骤。第一步与基本贪婪策略相同。在第二步中，它检查边缘以边缘重量的降序逐一去除。 对于删除的每个边缘，它会尝试将边缘添加回图形，并判断是否通过添加创建了一个循环。 如果不是，则边缘被加回。 显然，该算法删除较少的边缘来生成DAG，而不是基本的贪婪算法。 实际上，已证明这种改进的算法实现了lambda;-近似，其中lambda;是图中最长周期的长度。 该算法的时间复杂度为O（nm）（Demetrescu and Finocchi 2003），其中n是节点的数量，m是图中边缘的数量。

表3：Wf的效率 图3：Ph的效率

可信度度量

我们的下一步是定义边权重来量化可信度。首先，我们给出一个在Probase中使用频率作为isA关系的基本度量。然后我们提出如何改进这一指标。

基本度量：频率回想一下，Probase中的每个isA关系X isA Y与在语料库中观察到isA关系的频率相关联。我们使用wf（e）来表示边e的频率。直觉上，更大的权重意味着更高的可信度。例1说明了这一点。我们的实证研究表明，wf有效描述了isA关系的可信度。我们在Probase中分别从一些频率范围内随机采样50个边缘，然后手动判断它们的正确性。表3显示较大的频率意味着较高的可信度。

例1中国的频率是Probase中的一个国家是10,723，这意味着有10,723个包

全文共15151字，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[12314]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

您可能感兴趣的文章

• 使用金属伪影减少算法从 CT 数据生成的数字模型的准确性外文翻译资料
• 彩色光流外文翻译资料
• 云环境下基于虚拟机配置文件针对DDOS攻击的最优网络攻击探测方法外文翻译资料
• 监控大视频数据分析中的模糊逻辑: 综述、挑战和研究方向外文翻译资料
• PeopleSoft人力资源管理系统实施外文翻译资料
• 图像绗缝的纹理合成与转移外文翻译资料
• 管理云中的资源:Chrome扩展到OpenStack外文翻译资料
• 一种基于凸显区域检测和SPBVM的美学QR码新算法外文翻译资料
• 微信小程序-所有你需要知道外文翻译资料
• Java核心技术卷II高级特性外文翻译资料