什么算法适合这种简单的机器学习问题？

Question

我有一个我认为是一个简单的机器学习问题.

这是基本问题:我反复给出一个新对象和一个关于该对象的描述列表.例如:new_object:'bob'new_object_descriptions : ['tall','old','funny']. 然后,我必须使用某种机器学习来查找具有10个或更少相似描述的先前处理的对象,例如,past_similar_objects : ['frank','steve','joe']. 接下来,我有一个算法可以直接测量这些对象是否确实类似于bob,例如correct_objects : ['steve','joe']. 然后给分类器进行成功匹配的反馈训练.然后这个循环重复一个新对象.这是伪代码:

Classifier=new_classifier()

while True:
    new_object,new_object_descriptions = get_new_object_and_descriptions()
    past_similar_objects = Classifier.classify(new_object,new_object_descriptions)
    correct_objects = calc_successful_matches(new_object,past_similar_objects)
    Classifier.train_successful_matches(object,correct_objects)

但是,有一些规定可能限制可以使用的分类器:

• 将有数百万个对象放入此分类器中,因此分类和培训需要能够很好地扩展到数百万个对象类型,并且仍然很快.我认为这取消了类似垃圾邮件分类器的资格,这种分类器只适用于两种类型:垃圾邮件或非垃圾邮件.(更新:如果这是一个问题,我可以将其缩小到数千个对象而不是数百万个.)

• 再次,当数百万个物体被分类时,我更喜欢速度,而不是准确性.

• 更新:分类器应根据过去训练的反馈返回10个(或更少)最相似的对象.没有这个限制,一个明显的作弊将是分类器可以只返回所有过去的对象:)

为此目的,什么是体面的,快速的机器学习算法？

注意:calc_successful_matches距离度量计算起来非常昂贵,这就是为什么我使用快速机器学习算法来尝试在实际进行昂贵的计算之前猜测哪些对象将会关闭.

Answer 1

一种似乎符合您要求的算法(可能与统计学家John建议的类似)是语义哈希.基本思想是它训练一个深层次的信念网络(一种神经网络,有些人称之为"神经网络2.0",现在是一个非常活跃的研究领域)来创建一个对象描述列表的哈希值.二进制数使得数字之间的汉明距离对应于相似的对象.由于这只需要按位操作,因此它可以非常快,并且由于您可以使用它来创建最近邻风格的算法,因此它自然地推广到非常多的类.这是非常好的先进技术.缺点:理解和实施并不简单,需要进行一些参数调整.作者在这里提供了一些Matlab代码.一种更容易实现的算法,与此密切相关的是Locality Sensitive Hashing.

既然你说你有一个昂贵的距离函数,你想快速近似,我想起了另一个非常有趣的算法,Boostmap.这个使用增强来创建一个快速度量,它近似于计算度量的昂贵.在某种意义上,它与上述想法类似,但所使用的算法是不同的.本文的作者有几篇关于相关技术的论文,这些论文都非常好(在顶级会议上发表)你可能想要查看.

Answer 2

您可以使用向量空间模型（http://en.wikipedia.org/wiki/Vector_space_model）。我认为您想要学习的是如何在考虑两个对象描述向量彼此之间的接近程度时对术语进行加权，例如根据简化的互信息。这可能非常有效，因为您可以从术语散列到向量，这意味着您不必比较没有共享特征的对象。然后，朴素模型将具有每个术语的可调整权重（这可以是每个向量的每个术语，每个总体的术语，或两者）以及阈值。向量空间模型是一种广泛使用的技术（例如，在 Apache Lucene 中，您可能可以使用它来解决此问题），因此您将能够通过进一步的搜索找到很多相关信息。

让我根据您的示例给出一个非常简单的表述。给定鲍勃：['高'，'老'，'有趣']，我检索

弗兰克：['年轻'，'矮，'有趣'] 史蒂夫：['高'，'老'，'脾气暴躁'] 乔：['高'，'老']

因为我正在维护一个来自 funk->{frank,...}、tall->{steve, joe,...} 和 old->{steve, joe,...} 的哈希值

我计算诸如总体互信息之类的东西：共享标签的权重/鲍勃标签的权重。如果该重量超过阈值，我会将其包含在列表中。

训练时，如果我犯了错误，我会修改共享标签。如果我的错误包括弗兰克，我会减少有趣的权重，而如果我犯了错误，不包括史蒂夫或乔，我会增加高和老的权重。

您可以根据需要使其变得复杂，例如通过包含术语连词的权重。