-
推荐系统
[纯技术] 工作职位推荐系统的算法与架构
Indeed.com 每个月有两亿不同的访客，有每天处理数亿次请求的推荐引擎。在这篇文章里，我们将描述我们的推荐引擎是如何演化的，如何从最初的基于Apache Mahout建立的最简化可用行产品，到一个在线离线混合的成熟产品管道。我们将探索这些变化对产品性能指标的影响，以及我们是如何通过使用算法、架构和模型格式的增量修改来解决这些挑战的。进一步，我们将回顾在系统设计中的一些相关经验，相信可以适用于任何高流量的机器学习应用中。
从搜索引擎到推荐
Indeed的产品运行在世界各地的许多数据中心上。来自每个数据中心的点击流数据以及其他应用事件被复制到我们在奥斯丁数据中心的一个中心化的HDFS数据仓库中。我们在这个数据仓库上进行计算分析并且构建我们的机器学习模型。
我们的职位搜索引擎是简单而直观的，只有两个输入：关键字和地点。搜索结果页面展示了一个匹配的职位列表，并基于相关性进行了排序。搜索引擎是我们的用户发现职位的主要方式。
我们决定在搜索引擎之上加入职位推荐作为一个新的交互模式是基于以下几个关键原因：
Indeed上所有搜索的25%只指定了一个区域，并没有搜索关键字。有许多的求职者并不确定在他们的搜索中应该用什么关键字
当我们发送有针对性的推荐时，求职者的体验是个性化的
推荐可以帮助甚至最复杂的用户来发现额外的未被搜索所涵盖的职位
推荐为亚马逊带来了额外35%的销量为Netflix75%的内容阅览。很显然，推荐能提供额外的价值
推荐职位与推荐产品或者是电影有很显著的区别。这里列举了一些我们在构建推荐引擎时仔细考虑过的因素：
（职位）库存快速增长：我们每天要聚合计算几百万新的职位。可以推荐的职位的集合在不断变化
新用户：每天有几百万新的求职者访问我们的网站并开始他们的职位搜索。我们想要能够根据有限的用户数据生成推荐。
流动性：在indeed上一个职位的平均生命周期是30天左右。内容的更新十分重要，因为老的职位的需要非常可能已经被满足了
有限的供给关系：一个发布的职位通常只招一个的应聘者。这和书籍或者电影很不一样，并不是只要有库存就可以同时推荐给很多用户。如果我们过度推荐一个职位，我们可能会让雇主收到到上千个应聘申请的轰炸。
如何理解推荐算法
推荐是一个匹配问题。给定一个用户集合和一个物品集合，我们想要将用户匹配到他们喜欢的物品上。有两种高层次的方法可以达成这类匹配：基于内容的和基于行为的。它们各有优缺点，此外也有将两者结合起来从而发挥各自优势的方法。
基于内容的方法使用比如用户偏好设置、被推荐物品的特性之类的数据来决定最佳匹配。对于职位推荐来说，通过职位的描述中的关键字来匹配用户上传的简历中的关键字是一种基于内容的推荐方法。通过一个职位的关键字来找到其他看上去相似的职位是另外一种基于内容的推荐的实现方法。
基于行为的方法利用了用户的行为来生成推荐。这类方法是领域无关的，这意味着同样的算法如果对于音乐或者电影有效的话，也可以被应用在求职领域。基于行为的方法会遇到所谓的冷启动问题。如果你只有很少的用户活动数据，就很难去生成高质量的推荐。
Mahout协同过滤
我们从建立一个基于行为的推荐引擎开始，因为我们想要利用我们已有的求职用户和他们的点击数据，我们的首次个性化推荐尝试是基于Apache Mahout提供的基于用户间的协同过滤算法的实现。我们将点击流数据喂给一个运行在Hadoop集群上的Mahout构建器并产生一个用户到推荐职位的映射。我们建立一个新的服务使得可以运行时访问这个模型，且多个客户端应用可以同时访问这个服务来获取推荐的职位。
产品原型的结果和障碍
作为一个产品原型，基于行为的推荐引擎向我们展示了一步步迭代前进的重要性。通过快速建立起这个系统并将其展示给用户，我们发现这种推荐对于求职者来说是有用的。然而，我们很快就遇到了一些在我们的数据流上使用Mahout的问题：
模型构建器需要花大约18个小时的时间来处理Indeed网站2013年的点击流数据，这个数据量要比今日的数据小了三倍。
我们只能一天执行一个模型构造器，这意味着每天新加入的用户直到第二天为止看不到任何推荐。
几百万新汇总的职位在模型构造器再次运行之前是不能作为可见的推荐的。
我们产生的模型是一个很大的映射，大约占了50吉字节的空间，需要花费数个小时将其通过广域网从其生成的数据中心拷贝到全球各地的数据中心。
Mahout的实现的提供露了一些可配置参数，比如相似度阈值。我们可以调节算法的参数，但是我们想要测试整个不同的算法这样的灵活性。
为推荐实现最小哈希
我们先解决最重要的问题：构建器太慢了。我们发现在Mahout中的用户间相似度是通过在n^2复杂度下的用户间两两比较的来实现的。仅对于美国的网站用户来说（五千万的访问量），这个比较的数量将达到15 * 10^15次，这是难以接受的。而且这一计算本身也是批量处理的，新加一个用户或者一个新的点击事件就要求重新计算所有的相似度。
我们意识到推荐是一个非精确匹配问题。我们是在寻求方法来发现给定用户最相近的用户们，但是我们并不需要100%准确。我们找了一些估算相似度的方法，不需要准确的计算。
主要贡献者戴夫格里菲思从一篇谷歌新闻学术论文上看到了最小哈希方法。最小哈希（或者最小独立序列）允许近似计算杰卡德相似度。将这一方法应用到两个用户都点击过的职位上，我们发现两个用户有更多共同的职位点击，那么他们的杰卡徳相似度就越高。为所有的用户对计算杰卡徳相似度的复杂度是O(n^2)，而有了最小哈希后，我们可以将复杂度降到O(n)。
给定一个哈希函数h1, 一个项目集合的最小哈希被定义为将集合中所有项用该哈希函数分别哈希，然后取其中最小的值。由于方差太大，单个哈希函数不足以计算近似杰卡徳相似度。我们必须使用一个哈希函数族来合理地计算近似的杰卡徳距离。通过使用一个哈希函数族，最小哈希可被用来实现可调节杰卡徳相似度阈值的个性化推荐。
“挖掘海量数据集”，一个最近的由斯坦福大学教授莱斯科维克、拉贾罗曼和厄尔曼讲解的Coursera课程，非常详细的解释了最小哈希。他们书的第三章——“挖掘海量数据集”，解释了最小哈希背后的数学证明原理。
我们针对推荐的最小哈希的实现涉及到以下三个阶段：
1. 签名计算和集群分配
每一个求职者被映射到一个h个集群的集合，对应了一个哈希函数族H（下面的伪代码展示了这一过程）：
H = {H1, H2, ..H20}
for user in Users
for hash in H
minhash[hash] = min{x∈Itemsi| hash(x)}
这里H是一个包含h个哈希函数的族。这一步的最后，每一个用户被一个签名集合所代表，也即一个由h个值组成的集群。
2. 集群扩展
共享相同签名的用户被认为是相似的，他们的职位将为被互相推荐。因此我们从每一个在集群中的用户开始，用其所有的职位来扩展每个集群。
3.生成推荐
为了给一个用户生成推荐，我们将h个用户所在的集群中的职位并起来。然后我们除去任何用户已经访问过的职位，从而得到最后的职位推荐。
为新用户推荐职位
最小哈希的数学属性使得我们可以解决为新用户推荐职位的问题，并且可以向所有的用户推荐新的职位。当新的点击数据到来的时候，我们增量地更新最小哈希签名。我们也在内存中维护新职位和他们的最小哈希族的映射。通过在内存中保留这两部分数据，我们就可以在新用户点击了一些职位后为他们推荐职位。只要任何新发布的职位被点击访问过，它就可以被推荐给用户。
在转移到最小哈希方法后，我们有了一个混合的推荐模型，由一个在Hadoop上的构建的离线每日被更新的组件和一个由当日的点击数据组成、在内存缓存中实现的在线组件。这两个模型被整合起来用以计算每一个用户的最终推荐集合。在我们做了这些改变之后，每一个用户的推荐变得更加得动态，因为它们将随着用户点击感兴趣的职位的同时发生变化。
这些改变中我们认识到，我们可以在性能和准确度上做出权衡，用小的误差增加来换大的性能提升。我们也认识到可以将较慢的离线模型通过在线的模型进行补充，从而得到更新的推荐结果。
工程基础设施的影响
包含每一个用户到他们的推荐的映射的推荐模型是一个相当庞大的文件。由于职位对于每个国家来说都是本地的，我们首先尝试将我们的数据基于大约的地理边界进行分片。我们在每一块区域运行模型构造器，而不是在整个世界运行一个。每一个地区都有多个国家组成。举个例子，东亚地区包括为中国、日本、韩国、香港、台湾以及印度的推荐。
但是在分片之后，一些区域产生的数据仍然十分庞大，需要花好几个小时才能通过广域网从欧洲数据中心拷贝到奥斯丁的Hadoop集群。为了解决这个问题，我们决定增量的传输推荐数据，而不是一天一次。我们重用了连续先写日志(sequential write ahead logs)的方法，通过日志结构合并树来实现。这一方法已经在Indeed的其他大型产品应用中得到验证，比如我们的文档服务。
我们修改了我们的模型构建器，将推荐数据存储成小的分段，而不是产生一个单独庞大的模型文件。每一个段文件使用顺序输入输出，并且为快速复制做了优化。这些分段在远程数据中心运行推荐服务时将被重新组装成一个日志结构合并树。
这一基础架构的改变使得用户可以比之前快数个小时在远程的数据中心上看到他们新的推荐。从我们的A/B测试的结果来看，由用户更快的得到新职位推荐带来了30%的点击量提升。
这一改进展示了工程基础设施的改进与算法的改进带来的影响不相上下。
改进A/B测试的速度
建立起计算和更新推荐的管道只是一个开始。为了改进覆盖率和推荐质量，我们需要加快我们的A/B测试的速度。我们为了调整最后的推荐集合做了很多决策。这些决策包括，相似度阈值，每一个用户的推荐包含的职位数量，以及各种不同的用来过滤掉低质量推荐的方法。我们想要调节和优化计算推荐的各个方面，但是这需要逐个对算法的每个改进都构建新的模型。测试多个改进想法意味着处理用户请求的服务器上多倍的磁盘以内存占用。
我们开始通过传输计算推荐的单独组件而不是最终的结果来改进我们的A/B测试。我们改变了推荐服务来执行最后的计算，即通过将碎片整合起来，而不是简单的读取模型返回结果。重要的推荐子组件是每个用户的集群分配，从每一个集群到这个集群中的职位的映射以及一个对于每个用户来说包含不应该推荐给他们的职位的黑名单。我们修改了我们的构建器，来产生这些组件，并且修改了我们的服务，将他们在收到请求时组合起来从而返回最终的推荐列表。
通过实现这种架构上的改变，我们只传输那些在每一个A/B测试中改变的子组件。比如说，如果测试只调节了什么样的职位会从一个用户的推荐中除去，那么我们只需要传输这个测试组的黑名单。
这一改变改进了A/B测试的速度的数量级。我们能够在很短的时间内测试并验证多个可以改进推荐质量和覆盖率的想法。之前，由于设置环境的开销较大，我们平均每个季度只能测试一个模型中的改进，
我们的经验表明A/B测试的速度应该在设计大型机器学习系统时就被考虑进去。你能越快地将你的想法放在用户面前，那么你就能越快地在上面迭代。
这篇文章总结了我们在构建我们的推荐引擎时做出的一系列算法和架构上的改变。我们迭代地构建软件，我们从一个最简单原型开始，从中获取经验，并不断改进。这些改变带来的成果是职位推荐的点击增加从2014年初最简原型时的3%增长到了14%。
我们将继续精炼我们的推荐引擎。我们正在使用Apache Spark建立一个原型模型，建立一个模型集成组合，并精炼我们的优化参数来应对流行偏见问题。
Preetha Appan
Preetha Appan是Indeed的高级软件工程师，是高性能推荐搜索分布式系统的专家。她对Indeed的职位和简历搜索引擎的贡献包括，文本切分改进、查询扩展特性以及其他重要的基础设施和性能改进。她乐于并享受解决机器学习和信息检索方面的挑战性的问题。
来源：OReillyData
扫一扫 加微信
hrtechchina
