可逐步训练的实体识别分类器

Question

我是一名语义网/自然语言处理研究人员，手头有一组稀疏记录，包含数字和非数字数据的混合体，这些数据代表了从简单英语句子中提取出的各种特征标注实体。

例如：

uid|features
87w39423|speaker=432, session=43242, sentence=34, obj_called=bob,favorite_color_is=blue
4535k3l535|speaker=512, session=2384, sentence=7, obj_called=tree,isa=plant,located_on=wilson_street
23432424|speaker=997, session=8945305, sentence=32, obj_called=salty,isa=cat,eats=mice
09834502|speaker=876, session=43242, sentence=56, obj_called=the monkey,ate=the banana
928374923|speaker=876, session=43242, sentence=57, obj_called=it,was=delicious
294234234|speaker=876, session=43243, sentence=58, obj_called=the monkey,ate=the banana
sd09f8098|speaker=876, session=43243, sentence=59, obj_called=it,was=hungry
...

一个实体可能会出现多次（但每次都有不同的UID），并且可能与其其他出现重叠。第二个数据集表示上述UID中哪些是绝对相同的。

例如：

uid|sameas
87w39423|234k2j,234l24jlsd,dsdf9887s
4535k3l535|09d8fgdg0d9,l2jk34kl,sd9f08sf
23432424|io43po5,2l3jk42,sdf90s8df
09834502|294234234,sd09f8098
...

我应该使用哪些算法来增量式地训练一个分类器，可以接受一组特征，并立即推荐N个最相似的UID以及这些UID实际上是否代表了同一实体的概率？可选地，我还想获得缺失功能的建议，以填充并重新分类以获得更确定的匹配。

我研究了传统的近似最近邻算法，例如FLANN和ANN，我认为它们不适合，因为它们不能进行可监督学习的训练，也通常不设计用于稀疏的非数值输入。

作为第一个非常天真的尝试，我考虑使用朴素贝叶斯分类器，将每个SameAs关系转换为一组训练样本。因此，对于每个具有B SameAs关系的实体A，我将遍历每个关系并进行如下训练：

classifier = Classifier()
for entity,sameas_entities in sameas_dataset:
    entity_features = get_features(entity)
    for other_entity in sameas_entities:
        other_entity_features = get_features(other_entity)
        classifier.train(cls=entity, ['left_'+f for f in entity_features] + ['right_'+f for f in other_entity_features])
        classifier.train(cls=other_entity, ['left_'+f for f in other_entity_features] + ['right_'+f for f in entity_features])

然后像这样使用它：

>>> print classifier.findSameAs(dict(speaker=997, session=8945305, sentence=32, obj_called='salty',isa='cat',eats='mice'), n=7)
[(1.0, '23432424'),(0.999, 'io43po5', (1.0, '2l3jk42'), (1.0, 'sdf90s8df'), (0.76, 'jerwljk'), (0.34, 'rlekwj32424'), (0.08, '09843jlk')]
>>> print classifier.findSameAs(dict(isa='cat',eats='mice'), n=7)
[(0.09, '23432424'), (0.06, 'jerwljk'), (0.03, 'rlekwj32424'), (0.001, '09843jlk')]
>>> print classifier.findMissingFeatures(dict(isa='cat',eats='mice'), n=4)
['obj_called','has_fur','has_claws','lives_at_zoo']

这种方法有多可行？最初的批量训练将非常缓慢，至少是O(N^2)，但增量训练支持将允许更快地进行更新。

有更好的方法吗？

- Cerin

---

有趣的问题，像往常一样 Cerin。当你说你想要逐步训练时，是指你获取更多实体数据、更多“sameas”数据还是两者都要？ - Stompchicken

Answer 1

我认为这更像是一个聚类问题而不是分类问题。你的实体是数据点，而sameas数据则是将实体映射到聚类的映射。在这种情况下，聚类是你的实体所指的不同“事物”。

你可能想看一下半监督聚类。一个简短的谷歌搜索找到了论文Active Semi-Supervision for Pairwise Constrained Clustering，它提供了一个增量/主动算法的伪代码，并使用监督来获取训练数据，指示哪些实体属于同一聚类或不属于同一聚类。你可以很容易地从你的sameas数据中得出这个结果，假设例如uid 87w39423和4535k3l535是明显不同的事物。

但是，为了使其工作，您需要基于数据中的特征提出距离度量。你有很多选择，例如你可以在特征上使用简单的汉明距离，但是这里度量函数的选择有点随意。我不知道任何选择度量的好方法，但也许当你考虑最近邻算法时，你已经研究过这个问题了。

您可以使用从聚类中心的距离度量来得出置信度分数。如果您想要实际的成员概率，则需要使用概率聚类模型，例如高斯混合模型。有很多软件可以进行高斯混合建模，但我不知道有哪些是半监督或增量的。

如果您想回答的问题是“给定一个实体，哪些其他实体可能指的是同一件事情？”，则可能有其他适当的方法，但我认为那不是您想要的。

- Stompchicken

---

这是一个有趣的想法。然而，我仍然认为这是一个分类问题，而不是聚类问题的原因在于，聚类通常试图将向量拟合到一个单一簇中，没有任何置信度分数。我想你可以使用距离度量来衡量一个向量与每个簇之间的距离，但我不确定这如何转化为概率。 - Cerin

@Cerin 那么，您的问题是希望得到某种成员信心分数，还是希望得到实际成员概率，或者您希望实体具有多个群集的成员资格？ - Stompchicken

@Cerin，即一个特定的实体可以真正地属于多个“事物”（就事实而言） - Stompchicken

好问题。我越想，监督聚类就等于分类。我想我正在寻找一个实体属于多个组/事物的例子。例如，“我的苹果”将属于一个代表属于我的特定苹果的“事物”，但它也可能属于另一个代表“水果”的“事物”，以及其他代表上位词/下位词的组。 - Cerin

我认为监督聚类算法很像生成式分类算法（例如朴素贝叶斯），但对于像逻辑回归这样的判别式算法来说则不太相似。然而，上述算法是半监督的，因此它会在未标记的示例上训练其模型。 - Stompchicken

Answer 2

你可能想要看一下这个方法：

"Large Scale Online Learning of Image Similarity Through Ranking" Gal Chechik, Varun Sharma, Uri Shalit 和 Samy Bengio，机器学习研究杂志（2010年）。[PDF] [Project homepage]

更多想法：

你所说的“实体”是什么意思？实体是指“obj_called”所指的东西吗？你是否使用“obj_called”的内容来匹配不同的实体，例如，“John”与“John Doe”相似？你是否使用句子之间的接近程度来表示相似的实体？映射的更大目标（任务）是什么？

- cyborg

---

在我的情况下，“实体”不是单一的文本片段。它更像是一个“虚拟”的对象，类似于聚类算法中的组概念。更大的目标是通过将在不同句子中定义对同一实体引用的属性链接在一起来更好地从自然语言中构建模型。即，我只是想更好地理解“实体识别”的主题。 - Cerin