MetaPAD: Meta Pattern Discovery from Massive Text Corpora

背景

传统的文本序列挖掘方法已经公开了大量的序列集合，但是很少有方法能够提取出具有语义类型的任意序列。

Hearst patterns使用诸如“NP such as NP, NP, and NP”挖掘上下为关系;TextRunner和ReVerb对其词汇模式中的类型信息一无所知；NELL[8]学习基于一组固定的预设关系来提取名词短语对，这些关系具有实体类型：如country:president→$Country×$Politician;

一个例外是PATTY提出地SQL模式，依赖于句法分析器，并利用来自知识库或类型系统的类型信息，是在单个句子的解析树上用两个类型实体之间的最短路径自动生成的。但SOL-模式在从大规模文本语料库中挖掘类型文本模式时有三个限制，如下所示。

image

一个好的文本文本应该是信息丰富的、自身包含上下文信息。PATTY中的依赖分析失去了围绕实体的丰富上下文，例如句子1中“Barack Obama”旁边的“president”和句子2中的“president”和“prime_minister”。此外，SOL 模式仅限于两个实体之间的依赖路径，但不表示诸如$Digit表示“55”和$ Month $; Day$Year之类的数据类型。此外，解析过程代价高昂：它的复杂度是句子长度的三次方，这对于新闻和科学语料库来说代价太高，因为它们都有很长的句子。我们期待一种针对海量语料库的文本挖掘方法。
其次，为了处理模式稀疏性，为了扩展知识库和问答系统，需要对同义文本模式进行识别和分组，并对它们抽取的信息进行聚合。如图1所示，country：president 和person：age两个同义模式组。然而，找到这些同义模式组的过程是非常重要的。应考虑多方面的信息：（1）同义词应共享相同的实体类型或数据类型；（2）即使对于同一实体（如巴拉克奥巴马），也应允许对其进行不同的分组和概括（如<United States, Barack Obama> vs. <Barack Obama, 55>）；（3）共享词（如“president”）或语义相似的上下文词语（如“age”和“-year-old”）可能在同义模式分组中发挥重要作用。PATTY在对同义模式进行分组时不探索多方面的信息，因此不能聚合这样的提取。
第三，文本模式中的实体类型应该是精确的。在不同的模式中，即使同一个实体也可以在不同的类型级别上进行类型化。例如，实体“Barack Obama”应该在由第1-2句生成的模式中以细粒度（Politician）输入，在由第3-4句生成的模式中以粗粒度（Person）输入。然而，PATTY并没有寻找合适的实体类型粒度。

定义（Meta Pattern）:是指实体类型（例如，$ Person，$ Politician，$Country）或数据类型（例如，$Digit，$Month，$Year）、单词（例如，“politician”，“age”）或短语（例如，“prime minister”）的频繁、具有信息性和精确的子序列，可能还有标点符号（例如，“，”，“（”），作为一个整体特定语境中的语义单位。

为什么要挖掘元模式和同义元模式分组？-因为将元模式挖掘和分组为同义组可能有助于信息提取并将非结构化数据转换为结构。例如，我们从一个新闻语料库中得到一句话，“President Blaise Compaore´’s government of Burkina Faso was founded …”，如果我们发现了元模式““president $Politician’s government of $Country”，我们就可以识别并分类一个新的实体（即“Blaise Compaore´”$Politician和““Burkina Faso”作为$Country），以前的研究需要人类在语言规则方面的专业知识或大量的标注数据学习。如果我们将模式与同义模式（如“$Country president $Politician”）组合，我们可以将事实元组<Burkina nafaso, president, Blaise Compaore´>合并到属性类型<country:president>的大量事实集合中.

为了系统地解决元模式挖掘和同义模式分组的难题，我们开发了一个称为MetaPAD（Meta Pattern Discovery）的新框架。我们的MetaPAD没有处理每一个单独的句子，而是利用大量的句子中丰富的模式来表示大量实例的属性或关系。首先，MetaPAD使用高效的顺序模式挖掘生成元模式候选，具有丰富的领域无关上下文特征的用于直观的想法（例如，频率、信息性）学习一个质量评估函数来评估候选模式，然后通过评估引导的上下文感知分割挖掘高质量元模式。其次，MetaPAD将同义元模式的分组过程作为一项学习任务来制定，并通过集成实体类型、数据类型、模式上下文和提取的实例等多个方面的特征来解决这个问题。第三，MetaPAD检查从每个元模式组中提取的实体的类型分布，并寻找模式t最合适的类型级别。这包括自上而下和自下而上的方案，它们遍历类型本体以获得模式的精确性。

元模式挖掘

数据预处理: Harnessing Typing Systems

为了找到文本类型的元模式，我们采用了一种有效的文本挖掘方法，将一个语料库预处理成一个细粒度类型语料库，输入步骤如下，分成3步：

以 U.S. President Barack Obama and Prime Minister Justin Trudeau of Canada met in … 为例子

使用一个短语挖掘方法，将一个句子分解成短语、单词和标点符号，这样就可以找到比PATTY中频繁项集挖掘的频繁n-grams更多的真实短语，如“barack obama”, “prime minister”。
我们使用基于远程监控的方法来联合识别实体及其粗粒度类型（即$Person，$Location和$Organization）。
采用细粒度的实体类型系统来区分2级本体和112种实体类型（如$Polotical，$Country，$Company）；我们进一步使用一组语言规则区分6种数据类型（包括$Digit，$DigitUnit，$DigitRank，$Month，$Day，$Year）。其中，
$DigitUnit: “percent”, “%”, “hundred”, “thousand”, “million”, “billion”, “trillion”…，

$DigitRank: “first”, “1st”, “second”, “2nd”, “44th”…

现在我们有了一个细粒度的、类型化的语料库，它由元模式中定义的相同类型的标记组成：实体类型、数据类型、短语、单词和标点符号。

image

问题定义

Problem（Meta Pattern Discovery）：给定一个细粒度的、类型化的大量句子的语料库 $C=[...,S,...]$ ，而且每个句子都被表示为 $S=t_1t_2...t_n$ ，其中 $t_k \in \mathcal T \cup \mathcal P \cup \mathcal M$ ， $t_k$ 是第 k 个token， $\mathcal T$ 是实体类型和数据类型的集合， $\mathcal P$ 是短语和单词的集合。 $\mathcal M$ 是标点符号的集合。任务是找到寻找高质量的同义元模式分组。一个元模式 $mp$ 是来自 $\mathcal T \cup \mathcal P \cup \mathcal M$ 集合的token的子序列。一个同义元模式分组表示为 $\mathcal MPG =[...,mp_i,...,mp_j..]$ ，其中每一对模式，如 $mp_i$ 和 $mp_j$ ，是同义的。

什么样的模式才是一个高质量的元模式呢？在这里，我们把句子当做一系列的标记。已有的序列模式挖掘算法在事务序列数据库中挖掘满足单个度量（最小支持阈值）的频繁子序列。然而，对于文本序列数据，我们提出的文本模式元模式的质量应该像短语挖掘一样，按照以下四个标准来评估。

例子. 一个模式的质量评估标准如下：（前一个模式的质量高于后一个模式）

频率：“$DigitRank president of $ Country” vs.“young president of $Country”；
完整性：“$Country president $Politician” vs. “$Country president”、“$Person's wife,$Person” vs. “$Person's wife”；
信息性：“$Person's wife,$Person”vs.“$Person and Person”；
精确性：“$Country president $Politician” vs. “$Location president $Politician”，“$$Person's wife,$Person” vs. “$Politician's wife,$Person”，“population of $Location” vs. “population of $Country”。

什么才是同义的元模式呢？事务数据集中的频繁序列模式集合是巨大的；来自大量语料库的元模式数目也是巨大的。由于在自然语言中表达相同或相似含义有多种方式，许多元模式可能具有相同或几乎相同的含义。示例如图1所示。对同义元模式进行分组有助于从不同的句子中提取大量的不同模式。总的抽取的信息的类型分布可以帮助我们调整组中的元模式以获得精确性。

MetaPAD 框架

MetaPAD的框架分为3个部分。

它开发了一种上下文感知的分割方法，以确定子序列的边界，并生成元模式的频率、完整性和信息性。
它将同义元模式分组。
对于每个同义模式组，它会根据适当的粒度调整实体类型的级别，以具有精确的元模式。

image

通过上下文感知算法生成元模式

候选模式生成

我们采用标准的频繁序列模式挖掘算法来寻找满足最小sup阈值的模式候选。实际上，可以设置最大模式长度ω来限制模式中的token数量。与非常长的句子的句法分析不同，我们的元模式挖掘探索的模式结构是局部的，但仍然具有广泛的上下文：在我们的实验中，我们设置ω=20。

元模式质量评估

考虑到大量的候选模式可能很混乱（例如，“of $Country” and“$political and”），理想情况是用很少的训练标签来评估候选模式的质量，但具有挑战性。根据质量标准，我们引入了一组丰富的上下文特征如下，并训练一个分类器，以估计质量函数 $Q(mp)\in [0，1]$ ，其中mp是一个候选元模式：

频率：一个好的元模式 $mp$ 应该在给定类型的预料中有着足够的出现此书 $c(mp)$
一致性：如果由于偶然性，token组合的频率明显高于预期，则元模式 $mp$ 具有良好的一致性。为了从统计学上解释这种一致性，我们考虑了一个空假设：语料库是由一系列独立的伯努利试验产生的。假设语料库中的token数是L，可以假定它相当大。在我们的零假设下，一对子模式 $<mp_l,mp_r>$ 的期望频率是

<centor> $\mu_0(c(<mp_l,mp_r>))= L\cdot p(mp_l)\cdot p(mp_r)$ </centor>

其中 $p(mp)=\frac {c(mp)}{L}$ ，是模式的经验概率。使用Z指数来衡量一对子模式 $<mp_l,mp_r>$ 构成语料库中作为mp的最佳搭配

<centor> $Z(mp)=\mathop{max}\limits_{<mp_l,mp_r>=mp} \frac{c(mp)-\mu_0(c(<mp_l,mp_r>))}{\sigma <mp_l,mp_r>}$ </centor>

其中 $\sigma<mp_l,mp_r>$ 表示频率的标准差，Z指数较高的表明模式在上下文中充当一个完整的语义单位：其组成的子模式高度相关。
信息性：一个好的模式 $mp$ 应该具有上下文信息。我们检查不同类型的token（例如，类型、单词、短语、非停用词、符号）的计数。例如，模式“$Person's wide$Person”是“wife”的上下文信息，而“$Person was born in $City”是“born in”的意思，而“$Person,$Digit,”也是两种不同类型和两个逗号的信息。
完整性：我们使用模式候选（例如“$Country president $Politician”）和其子模式（例如“$Country president”）的频率之间的比率。如果比率很高，候选模式很可能是完整的。我们还使用了候选模式的频率与其父模式频率之间的比率。如果比率很高，候选模式很可能是不完整的。此外，我们期望元模式不受停用词的限制。例如，“$Country president $Politician”和“$Country president and”都没有受限
覆盖范围：一个好类型的模式可以提取多个实例。例如，$Politician类型在模式“Politician's healthcare law”中仅指一个实体“巴拉克奥巴马”，因此在语料库中的覆盖率太低。

我们训练了一个基于随机森林的分类器，用以学习具有上述丰富上下文特征集合的元概率质量函数 $Q(mp)$ 。我们的实验表明，使用100个元模式标签可以达到与使用300个标签相似的精度和召回率。请注意，学习结果可以转移到其他领域：低质量的模式“$Politician and $Country”和“$Bacteria and $Antibiotics”的特征相似；高质量的patterns“$Politician is president of $Country”和“$Bacteria is resistant to$Antibiotics”的特征相似。

使用 $Q(.)$ 和反馈上下文感知分割

利用模式质量函数 $Q(.)$ 从丰富的上下文特征集合中学习，提出了一种自下而上的分割算法，以构造高质量分数的最佳分割。如图4所示，我们使用 $Q(.)$ 来确定分段的边界：我们以“$Country president $political”作为元模式，因为质量分数高；我们不选择候选模式“and prime_minister_$political of $Country”，因为其质量分数低。
由于 $Q(mp)$ 是用包括原始频率 $c(mp)$ 在内的特征来学习的，因此质量分数可能被高估或低估：原则是每一个token的出现应该只分配给一个模式，但是原始频率可以多次对这个token计数。幸运的是，在分割之后，我们可以将频率校正为 $c_r(mp)$ ，例如在图4中，分割避免了高估频率/质量的“$Politicion and prime_minister $Politician”（见表1）。
一旦频率特征被提取出来，我们就用 $c(mp)$ 作为反馈重新学习质量函数 $Q(.)$ ，并用它重新分割语料库。这可能是一个迭代过程，但我们发现只需要一次迭代，结果收敛。算法1显示了细节。

image

算法1

image

同义元模式分组

对于同一种关系，可能有许多元模式。如果我们对所有这些元模式进行分组，我们就可以从大量的语料库中聚合所有这些关系的提取。PATTY对它们基于依赖路径的SOL模式的同义模式有一个狭义的定义：如果两个模式从语料库中生成相同的提取集，那么它们就是同义的。在这里，我们开发了一种学习方法来整合三个方面的信息：（1）模式中的实体/数据类型，（2）模式中的上下文单词/短语，以及（3）模式提取的信息，以将元模式分配到组中。我们的方法基于以下三个假设（见图5）：

A1：同义元模式必须有相同的实体或者数据类型，像元模式“$Person's age is $Digit” 和“$Person's wife is $Person”；

A2：如果两个元模式具有相同的上下文单词或短语，那么他们很可能是同义的，像模式“$Country president $Politician”和“president $ Politician of $Country”有同样的单词“president”；

A3：如果两个模式抽取出更多相同的信息，它们更可能是同义的，像“$Person's age is $Digit”和“$Person, $Digit”都抽取出<Barack Obama，55>。

image

由于事先无法知道有多少组，我们建议先构造一个模式-模式图，其中每个模式之间的边满足A1，并且预测为同义的模式。然后使用图团体检测技术将所有的团作为同义元模式分组。在这团 $\mathcal MPG = [...,mp_i,...mp_j...]$ 中，每一对模式 $(mp_i,mp_j)$ 是同义的。

对于图的构建，我们训练了一个支持向量回归机学习基于A2和A3的一对pattern的以下特征：（1）每个模式拥有的和共享的单词，非停用词，短语数量；（2）两个模式非停用单词或短语之间的最大相似性得分；（3）每个模式抽取的信息和共同抽取的信息。其中，单词/短语之间的相似性由其word2vec嵌入的余弦相似性表示。

调整实体类型以提高精度

给定一组同义的元模式，我们希望这些模式是精确的：需要确定模式中实体类型的级别以获得适当的粒度。由于同义元模式的分组过程，我们从大量的抽取信息的集合中获得了丰富的实体类型分布。

如图所示，给定一个实体类型的本体（如$Location,$Country,$State,$City..., $Person:$Artist,$Athlete,$Politician, ...），对于同义模式组“president $Person of $Location”，“$Location's president $Person”和“Location president $Person”，这些模式里的实体类型，$Location $Person是否恰当能够确保这些模式是精确的。如果我们观察这些模式提取中实体的类型分布，很明显，$Location的大多数实体在细粒度级别上被键入$Country（例如，“United States”）或$Ethnicity（例如，“Russian”），而$Person的大多数实体也具有细粒度类型$Politician。因此，与“$Location总统$Person”相比，“$Country总统$Politician”和“$Ethnicity总统$Politician”这两个细粒度的元模式更加精确；

image

我们对同义群中的其他元模式也有相同的主张。另一方面，对于同义元模式组person：age，我们可以看到大多数实体在粗粒度级别上被输入为$Person，而不是$Athlete或$Politician。所以模式中的实体类型最好是$Person。根据这一观察，给定元模式组中的实体类型T，我们提出了一个称为graininess的度量，它定义为T类型的实体的分数，这些实体可以细化为T的子类型：

$g(T)=\frac{\sum_{T' \in subtype\_of(T)}num\_entity(T')}{\sum_{T' \in subtype\_of(T)\cup\{T\}}num\_entity(T')}$

如果 $g(T)$ 比阈值 $\theta$ 更高，我们就选择更深层的细粒度类型的类型本体。

假设我们已经使用粒度度量在元模式组中确定了适当的类型级别。然而，并不是每一个级别的类型都可以用来构造精确的元模式。例如，我们可以从图6中看到总统的模式，$Location的很少实体被输入为$City，$Person的很少实体被输入为$Artist。与$Country、$Ethnicity和$Politician相比，这些细粒度类型处于相同的级别，但对提取的信息支持太少。我们把他们排除在元模式组之外。基于这一思想，对于实体类型T，我们提出了另一个度量，称为支持，它定义为T类型的实体数与T的同级类型的最大实体数之比：

$s(T)=\frac{num\_entity(T)}{max_{T' \in sibling-type \_ of(T)\cup{T}} num\_entity(T')}$

如果 $s(T)$ 比阈值 $\gamma$ 更高，我们在元模式分组中考虑类型 $T$ ，否则丢弃它。

利用这两个度量，我们开发了一个自顶向下的方案，首先对粗粒度类型的元模式进行分段和同义模式分组，然后检查细粒度类型是否有意义，以及模式是否可以拆分到细粒度级别；我们还开发了一个自下而上的方案，该方案首先处理细粒度类型的元模式，然后检查模式是否可以合并到粗粒度级别。

实验

数据集

APR：美联社和路透社2015年的新闻；
TWT：2015年6月至2015年9月通过Twitter API收集的推文；
CVD：PubMed数据库中有关心血管疾病的论文标题和摘要。

image

新闻和生物医学论文语料库中经常出现长句，这对文本模式挖掘具有很大的挑战性。例如，PATTY中的句法依赖分析部分具有单个句子长度的三次计算复杂度。我们的MetaPAD中的预处理技术采用了与外部数据库的远程监督，用于实体识别和细粒度类型。对于一般的语料库，比如新闻和推文，我们使用DBpedia和Freebase；对于生物医学语料库，我们使用公共MeSH数据库。

实验设置

我们在实验中执行两项任务。第一个任务是从大量语料库中发现类型化的文本模式，并将这些模式组织成同义组。在模式质量和同义模式群质量上，我们与目前最先进的SOL模式综合集挖掘方法PATTY进行了比较。由于类型化文本模式没有标准的基本事实，我们报告了对这三个数据集的大量定性分析。

第二个任务是提取<实体、属性、值>（EAV）元组信息。对于竞争方法从新闻和推特中生成的每个同义模式集，如果合适的话，我们将其分配给表3中集合中的一个属性类型。我们从提取中收集5621个EAV元组，将它们标记为true或false，最后，我们得到3345个真正的EAV元组。我们有2400个从APR中提取的正确的EAV元组和2090个从TWT中提取正确的元组。它们的大多数都不在现存的知识库中，我们正在探索从新的文本语料库中提取的新内容。

image

我们从精确度和召回率两个方面来评估性能。精确度定义为预测的EAV元组中为真的比值。召回率被定义为，标记为真的EAV元组的部分被预测为真EAV元组的比值。我们使用（1）F1分数，即精确性和召回率的调和平均值，以及（2）精确性召回曲线下的面积（AUC）。所有值都在0到1之间，值越大表示性能越好。在第二个任务中，除了PATTY之外，元组提取的竞争性方法有：Ollie[37]是一个开放的IE系统，它可以提取具有句法和词汇模式的关系元组；ReNoun[40]通过带注释的语料库学习“S-A-O”模式，如“S A, O”和“A of S is O”。两个方法都忽略实体类型信息。我们开发了四种MetaPAD替代品，如下所示：

MetaPAD-T：只进行分割，实体类型粗粒度；
MetaPAD-TS：基于MetaPAD-T的同义分组等其他3个MetaPAD的核心组件
MetaPAD-B：只进行分割，实体类型细粒度
MetaPAD-BS：基于MetaPAD-B的同义分组等其他3个MetaPAD的核心组件

阈值设置：

最长的pattern长度： $\omega = 20$

graininess指数： $\theta = 0.8$

support指数： $\gamma = 0.1$

文本模式挖掘实验结果

image

如图所示：两种属性coutry: president，company:ceo

meta pattern来自于类型化语料，而不是句法依赖分树中的最短路径；因此这些模式可以保留丰富，广泛的上下文信息；
meta pattern拥有具有高质量的信息性、完整性等等，使用者很容易就能知道为什么这个pattern作为完整的语义单元被提取；
尽管像“$Politician was elected as the president of $Country”这样的模式数量少而且长，但是它们可以分类到与其同义模式一组中，这样对于一个实体属性的所有抽取都可以聚合到一个集合里。这就是为什么MetaPAD可以成功地发现像Burkina Faso这样地小国地总统，和新创公司地CEO；
MetaPAD从并不存在于现有知识库的新的语料中发现了丰富地person: data_of_birth 信息，这是因为MetaPAD不仅仅使用实体类型信息，而且使用数据类型信息，像$Month$Day$Year。

表4显示我们的MetaPAD还可以从生物医学领域发现同义元模式组和提取。如果没有对特定领域知识的大量注释，我们可以找到$Treatment可以治疗什么$Disease和什么$Bacteria对什么$Antibiotics有抵抗力的所有模式。

image

下图显示了PATTY从这四个句子生成的SOL模式语法集。首先，依赖路径失去了第一个示例中的“president”和最后一个示例中的“ceo”等实体周围的丰富上下文。其次，SOL模式synset不能对真正同义类型的文本模式进行分组。我们可以看到生成元模式并将它们分组为同义簇的优势。在简介部分中，我们还展示了MetaPAD可以为属性类型(如person：age和person：date_of_birth)找到包含丰富上下文信息的元模式。

image

EAV元组抽取结果

除了直接比较挖掘同义类型文本模式的质量外，我们还应用了不同系统的模式Ollie、ReNoun和PATTY，从两个通用语料库APR(news)和TWT(tweets)中提取元组信息。

表6总结了每个文本模式系统从新闻和tweet数据集中提取的元组信息的比较结果。图8展示了精确召回曲线，进一步证明了MetaPAD方法的有效性。我们的观察和分析如下。

image

总的来说，MetaPAD-TS和MetaPAD-BS在两个数据集上都比baseline要好。
MetaPAD-T和MetaPAD-B仅仅分割而没有分组就比PATTY要好。
MetaPAD-TS and MetaPAD-BS比起MetaPAD-T and MetaPAD-B要好一些，说明了分组和调整实体类型层级是有效的。
在tweet数据集上。很多人物地点组织实体都没有办法进行细粒度的划分，所有MetaPAD-T(S)比起MetaPAD-B(S)要好。而新闻数据包含大量可以细分粒度的实体，所以MetaPAD-B(S)表现更好。

MetaPAD在所有类型的属性抽取上都比其他方法要好，虽然不能提高非常多。

image

效率

image

具体来说，对于31G的tweet数据，MetaPAD不到2小时，而PATTY需要Stanford parser需要7.3小时，Ollie需要28.4小时。注意，对于包含许多长句的较小的新闻数据，PATTY需要更多的时间，10.1小时。

MetaPAD: 从大量文本语料库中发现元模式

MetaPAD: 从大量文本语料库中发现元模式

背景

相关工作

开放域信息抽取工具

属性抽取工具

其他信息抽取工具

元模式挖掘

数据预处理: Harnessing Typing Systems

问题定义

MetaPAD 框架