美国最大婚恋交友网站eHarmony的机器学习实践

转自：http://www.csdn.net/article/2015-03-19/2824267

上周，我去洛杉矶参加了一个机器学习的meetup，一位主讲是eHarmony公司（美国最大的婚恋交友网站之一，通过性格测试来进行婚恋匹配的模式——百度百科）的Jon Morra，他着重分享了机器学习（machine learning）在他们的在线交友平台中的应用。机器学习技术应用的深度和广度给我留下了深刻的印象，他们居然能够应用到大多数人都能遇到的问题——寻找爱情上！

这是演讲视频的下载。

核心问题

在线约会的核心问题有太多的可挑选对象。为了防止用户无所适从，我们需要提供智能匹配。简单来说，你需要评估一下不同人们之间的“约会相容性（dating compatibility）”矩阵，从而建立一些匹配，这些匹配能够最大可能的使得约会成功。

如果这个爱情距离矩阵很小，你可以轻松的算出匹配，然后就能够给每一个人一个最佳匹配。比如，你可以用匈牙利算法来解决这一分配问题。然而，当我们处理数以百万计的用户量的时候，计算爱情距离矩阵就不现实了，并且我们的匹配也不是完美的，所以我们需要提供多个匹配。

John提供了一个“三级跳”的方法来解决这些问题：

1. 根据相容性分级来减少潜在匹配池。相容性分级由用户提交的心理自测结果以及性取向、年龄、所在地等构成。
2. 基于统计数据、文本功能、视觉功能等来计算潜在匹配之间的相似性（affinity）。
3. 基于相似性，就可以找到最佳的匹配，然后通过日常电子邮件发送给用户。

相容性分级

第一部分是最简单的：根据一些调查和从心理学的角度来看，人与人之间或多或少是具有相容性的。相容性分级既包括单人的人格特质也包含了人与人之间的二元特质——也就是相似性（similarity）。

相容性结果也使用了性别偏好、年龄段和所在地等因素进行了过滤。第一步通过硬阈值消除了大量的不兼容的匹配。这样就把爱情距离矩阵转换成了更加易于处理的不含0元素的矩阵。我私下揣摩，这样也可能导致创建一些小分组，比如基于所在地的分组等，这些分组可以为后续的并行运算做准备。

相似性计算

相似性分值是两个用户愿意交流的概率。这个分值是基于逻辑回归模型训练得到的。训练数据包括了一些日志，这里面记载了两个用户是否曾经给对方传递过个人资料。训练通过Vowpal Wabbit来完成，这是一个听起来挺可怕，但是功能强大的机器学习包，可以在TB级别上做线性和逻辑回归模型的在线训练。

你的特征关系到你的生死；eHarmony公司采用经典的特征，如网站使用率统计数据、文本特征（我猜测是bag-of-words模型）和照片数量等，这些数据从成对的用户中提取得到。我认为训练矩阵也包括了相似的特征，比如相容性等级。有趣的是，最近eHarmony公司也涉足了照片分析。

John首先展示了使用Viola-Jones探测器提取图像特征（比如脸部区/图片区）的例子。无处不在的Viola-Jones检测器采用级联分类器存根来检测一副图像中是否包含了人脸，它在OpenCV中有具体实现。这个分类器使用了类Haar特征，这种特征可以使用积分图像进行高效的计算，同时，分类器使用AdaBoost算法进行训练。

Face Parts检测器

然后，John展示了使用Face Parts检测器进行检测的一些结果，这部分内容我不懂，但是效果还是相当惊人的。Face Parts 包含的思想是，一个人脸可以看出是由多个部件构成的，这些部件可以放置到一个树形结构中。部分匹配（可以看成一个图形的一部分如果识别成眉毛，那么这种识别可以用一个分值来表示）通过计算模板和特征集的高斯直方图（HOG）的点积得到。

Face Parts

各个部分通过一些“弹簧”连接起来，所有弹簧的弹性决定了这种连接方式的能量——能量越低，配置就越好。外观和结构分数的加权和确定了一个特定的连接的“良好”程度。

由于弹簧模型使用了特殊的树形结构，所以所有连接的良好程度可以使用消息传递算法来进行评估和最大化。由于允许使用一些额外的树形结构——比如，一个用于前脸，一个用于轮廓——所以姿势估计、检测以及标志性的检测都可以使用相同的步骤来完成。相当不错。

训练是用结构化SVM学习方法的最大边界的设置来完成的。一旦模型训练完成，它就会使用eHarmony的脸部数据集进行评估，各种特征会从图像中提取出来：像脸的宽度和高度的比率，是否展示了乳沟等。Jon实现了一个高效的版本，并且将它开源，放置在GitHub上。

我的理解是，这些特征没有在相似性模型中进行双向性的编码：比如，它没有尝试把有胡子的家伙跟展示乳沟的女士进行匹配。相反，这些单向性的特征都是决定了你吸引别人进行交往的能力。

那么，下一步，你有多让人喜欢从而收到交流邀请就是很重要的了。这时候，匹配就用来使得每个人都开心了。

潜在相似性匹配

最后，我们必须给用户最佳匹配。系统设置了每个人有6到10个匹配对象，它使用了CS2算法来最大化有向无环图中的流——相匹配的人的相似性分数总和。

一个非常有趣的发展前沿——不是现在在用的——是根据人们的个人资料来给他们提供恰当的匹配数量。有些人喜欢更多的选择，而有些人，比如内向的人，或许更喜欢少一点的。

如果事先不知道一个人是喜欢多的还是少的，那么怎么给他提供一个更合适的匹配数量呢？一种解决方法是：一个月内，每天都给他一些随机数量的匹配，然后挑出他最常用的交往数量作为他的最佳匹配数字。但是使用这种策略，我们会不会浪费了太多的时间呢？

其实这个问题是变相的经典多臂匪徒问题（multi-armed bandit problem）。你面对许多个单臂匪徒——数学理想化的 老 虎 机，每个机器具有一定的但是未知的概率能中奖。每次试验中，你挑一个赌博机，并得到了回报。问题是，怎样在一定时间周期内获取最大化的收益，也就是说，最小化遗憾。这就需要深度和广度的一种平衡。

一种不太理想，但仍然非常快速和有效的策略称为UCB策略，它说的是你应该挑选那个上限信心索引最大的机器。所以在这种情况下部署UCB策略，可以迅速找到一个用户的最佳匹配的数目。

在这里，我们还有更多的数据可以利用——我们知道用??户的基本信息。这个问题就可以在具有上下文的匪徒问题框架下处理——经典匪徒问题+特征回归。在Yahoo!上有一篇非常不错的文章，它通过实验演示了如何使用UCB策略来生成带上下文的匪徒问题，强烈建议感兴趣的读者参阅。

总结

这一天的参与值得吗？John特别提到了发表在PNAS的一篇文章，文章提到，通过网上交友而完成的婚姻比线下的婚姻具有更高的满意度；在交友网站中，eHarmony公司拥有最好的婚姻满意度。

尽管该文件所依据的调查由eHarmony公司自己来完成的，但是统计结果看起来是可信的，并且PNAS是一本相当好的杂志。

当然，我们不能排除自我选择的偏见，也就是说如果有人想通过选择某个特定网站来进行约会，那么，如Aziz Ansari所指出的：视频下载。

原文链接：MACHINE LEARNING IN ONLINE DATING （编译/Fashionxu 审校/happytofly 责编/周建丁）