13

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

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

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 距离度量的计算成本非常高，这就是为什么我使用快速机器学习算法来尝试在我实际进行昂贵的计算之前猜测哪些对象会接近。

4

6 回答 6

9

一种似乎满足您的要求的算法（并且可能类似于 John the Statistician 的建议）是语义散列. 基本思想是，它训练一个深度信念网络（一种神经网络，有些人称之为“神经网络 2.0”，目前是一个非常活跃的研究领域）来创建一个对象描述列表的散列到二进制数，使得数字之间的汉明距离对应于相似的对象。由于这只需要按位运算，它可以非常快，并且由于您可以使用它来创建最近邻风格的算法，它自然可以推广到非常多的类。这是非常好的最先进的东西。缺点：理解和实现并不容易，需要一些参数调整。作者在这里提供了一些 Matlab 代码。一种更容易实现且与该算法密切相关的算法是局部敏感哈希。

既然您说您想要快速逼近一个昂贵的距离函数，我想起了另一个非常有趣的算法，Boostmap。这个使用提升来创建一个快速度量，该度量接近计算成本高昂的度量。在某种意义上它与上面的想法相似，但使用的算法不同。这篇论文的作者有几篇关于相关技术的论文，质量都很好（发表在顶级会议上），你可能想看看。

于 2010-03-26T02:21:55.110 回答
3

你真的需要一个机器学习算法吗？你的相似度指标是什么？你提到了对象数量的维度，那么每个人的特征集的大小呢？是否有最大数量的特征类型？我可能会尝试这样的事情：

1) 有一个字典映射特征到名为 map 的名称列表

对于每个人 p

对于 p 中的每个特征 t

地图[t].add(p);

2）然后当我想找到最近的人时，我会拿我的字典并创建一个新的临时字典：

字典映射名称到计数称为 cnt

对于我感兴趣的人的每个特征 t

对于 map[t] 中的每个人 p

cnt[p]++;

那么计数最高的条目最接近

这里的好处是地图只创建一次。如果每个人的特征很小，而可用特征的类型很大，那么算法应该很快。

于 2010-03-26T01:05:19.690 回答
3

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

让我根据你的例子给出一个非常简单的表述。给定 bob：['tall','old','funny']，我检索

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

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

我计算了类似整体互信息的东西：共享标签的权重/鲍勃标签的权重。如果该权重超过阈值，我会将它们包含在列表中。

训练时，如果我犯了错误，我会修改共享标签。如果我的错误是包括坦率，我会因为搞笑而减轻体重，而如果我因为不包括史蒂夫或乔而犯了错误，我会增加身高和老年人的体重。

您可以根据需要将其设置为复杂的，例如通过包含术语连词的权重。

于 2010-03-25T23:38:00.333 回答
2

SVM 非常快。特别是用于 Python 的LIBSVM提供了非常体面的支持向量机用于分类的实现。

于 2010-03-26T00:12:00.403 回答
1

你所描述的有点类似于Locally Weighted Learning算法，它给定一个查询实例，它围绕相邻实例在本地训练一个模型，该模型由它们到查询实例的距离加权。

Weka (Java) 在weka.classifiers.lazy.LWL中有一个实现

于 2010-03-26T02:27:12.940 回答
1

该项目以两个显着的方式偏离了典型的分类应用：

  • 而不是输出新对象被认为属于的类（或者可能输出这些类的数组，每个类都有概率/置信度），“分类器”提供了一个“足够接近”的“邻居”列表新对象。
  • 对于每个新的分类，一个独立于分类器的目标函数提供正确的“邻居”列表；然后使用更正后的列表（分类器提供的列表的子集？）来训练分类器

第二点背后的想法可能是提交给分类器并且与当前对象相似的未来对象应该得到更好的“分类”（与一组更正确的先前看到的对象相关联），因为正在进行的训练会重新执行与正（正确）匹配的连接，同时削弱与分类器最初出错的对象的连接。

这两个特征带来了不同的问题。
- 输出是对象列表而不是“原型”（或类别标识符）这一事实使得难以扩展，因为到目前为止看到的对象数量增长到问题中建议的数百万个实例。
- 训练是基于分类器找到的匹配子集完成的这一事实，可能会引入过度拟合，从而分类器可能对它偶然没有加权的特征（维度）变得“盲目”作为重要/相关，在培训的早期部分。（关于负责生成“正确”对象列表的目标函数，我可能假设太多了）

可能，缩放问题可以通过一个两步过程来处理，第一个分类器，基于 K-Means 算法或类似的东西，这将产生整个对象集合（先前看到的对象）的一个子集作为合理匹配对于当前对象（有效地过滤掉 70% 或更多的集合）。然后将根据向量空间模型（如果特征维度基于因素而不是值）或其他一些模型来评估这些可能的匹配。这个两步过程的基本假设是对象集合将有效地暴露集群（它可能只是相对均匀地分布在各个维度上）。

随着先前看到的对象的大小增加，进一步限制要评估的候选者数量的另一种方法是删除附近的重复项并仅与其中一个进行比较（但在结果中提供完整的重复项列表，假设如果新对象接近这个近似重复类的“代表”，该类的所有成员也将匹配）

过度拟合的问题更难处理。一种可能的方法是[有时]将对象随机添加到分类器通常不包括的匹配列表中。可以根据它们与新对象的距离相对距离添加额外的对象（即，添加相对较近的对象的可能性更大）

于 2010-03-26T01:28:30.937 回答