机器学习在搜索和推荐中的应用

By 王扉@小米

今天的互联网上，各种各样的信息浩如烟海，不胜其扰的信息消费者需要更有效的手段来区分精华和糟粕，找到所需要的。方法多种多样，但归根结底，本质上可归为两类：要么是搜索，要么是推荐。

所谓搜索是指，根据输入的用户查询，找到某种程度上相关的物品，比如网页、视频、音乐、文档等。和搜索不同，推荐通常不需要明确的用户查询，而是分析用户画像、当前场景等，主动展示给用户可能感兴趣的物品。

面对互联网的海量信息，无论是搜索，还是推荐，所要处理的数据都是规模巨大的。从架构上看，必须采用大规模分布式处理，从算法上看，必定是数据驱动的，因此结合分布式计算的机器学习方法在今天的搜索引擎和推荐系统中有较多的应用。

机器学习在搜索中的应用

排序学习

搜索结果排序是搜索引擎最核心的构成部分，很大程度上决定了搜索引擎的质量好坏及用户接受与否。给定用户查询，将检索到的网页或文档进行排序，这依赖于搜索引擎所采用的检索模型。关于检索模型的研究，从信息检索学科建立之初就一直是研究重点，到目前为止，已经提出了多种各异的模型，例如布尔模型、向量空间模型、概率模型、语言模型及最近几年兴起的机器学习排序算法。

搜索引擎的核心是判断哪些文档是和用户需求相关的，并按照相关程度排序输出，所以相关度计算是将用户查询和文档内容进行匹配的过程，而检索模型就是用来计算内容相关度的理论基础及核心部件[1]。

利用机器学习技术来对搜索结果进行排序，这是最近几年非常热门的研究领域。从机器学习的角度，将排序问题形式化为监督学习的问题，将文档表示为特征向量，其中特征表示文档与查询语句的匹配程度或文档的重要度，基于标注数据学习一个排序模型[8]。现在最常用的方法是LambdaMart [2]。该方法将排序问题转换为二类分类问题，利用Boosting算法优化学习目标函数。其最大特点是不显示地定义损失函数，而定义损失函数的梯度函数，以解决排序损失函数不易优化的问题。其他代表的排序学习方法还有GBRank [3]、LogisticRank [4]等。

此外在实际产品中，因为搜索排序需要处理的文档规模巨大，一般还会分成几个阶段来处理。以Yahoo的搜索为例[4]，搜索排序分成3个阶段，首先是召回（Recall），这个阶段要处理的文档规模是全部文档，所以一般是在索引里直接根据文档中是否含有检索词来快速处理，再结合简单线性机器学习模型进行打分。第二阶段是核心排序（Core Ranking），会用比较复杂的机器学习模型对召回的文档进行打分排序，抽取的特征也更多，这一步的打分通常是可以分布式的，打分时只需要考虑每个文档和查询词的相关性，不需要考虑文档之间的相互影响。第三阶段是上下文相关的重排（Contextual Reranking），这时需要考虑整个结果集的特征，只能在集中节点上计算，无法分布式处理，但能对结果排序做进一步的调优。

网页重要度学习

网页重要度学习旨在计算出每个网页的重要度，排序时将重要的网页尽量排在前面。传统的网页重要度计算基于超链接与PageRank算法。直观上，有许多链接指向的网页重要，网页的重要度可以通过链接在网上传播；PageRank用马尔可夫模型实现这一直观。可以认为最近提出的BrowseRank算法[5]是PageRank算法的扩展与补充。BrowseRank首先根据用户行为数据构建用户浏览图。然后再在用户浏览图上定义连续时间马尔可夫过程，用其平稳分布表示网页的重要度。直观上，用户在网页上平均停留时间越长，网页就越重要；转移到网页的次数越高，网页就越重要。基于用户的互联网使用行为数据，BrowseRank能够更好地计算网页重要度。

语义匹配学习

查询语句与网页的相关性靠两者的匹配程度决定，匹配结果直接影响搜索结果。比如，查询“ny times”应与含有“new york times”的网页匹配。理想的匹配应该是语义上的匹配，而不是关键字上的匹配。匹配学习的目的在于将字面上并不相同，但语义相同的查询语句与网页匹配上，将语义相关的网页排在搜索结果的前面。代表的方法有翻译模型[6]、隐空间模型[7]、以及深度学习模型[4]。日志数据中记录了用户点击。比如用户搜索“ny”，因为既含有“ny”又含有“new york”的网页会被搜到，所以两者通过用户搜索中的点击得以联系。隐空间模型方法基于点击数据将查询语句与网页投影到隐空间，在隐空间中学习到查询语句与网页之间的相似度，也就是匹配关系，进而能对新的查询语句与网页的匹配程度作出判断。比如，学到“ny”与“new york”的相似度，判断“ny times”与“new york times”是可以匹配的。

机器学习在推荐中的应用

以谷歌为代表的搜索引擎可以让用户通过搜索关键词找到自己需要的信息。但是，搜索引擎需要用户主动提供准确的关键词来寻找信息，因此不能解决用户的很多其他需求，比如当用户无法找到准确描述自己需求的关键词时，搜索引擎就无能为力了。

和搜索引擎一样，推荐系统也是一种帮助用户快速发现有用信息的工具。和搜索引擎不同的是，推荐系统不需要用户提供明确的需求，而是通过分析用户的历史行为给用户的兴趣建模，从而主动给用户推荐能够满足他们兴趣和需求的信息。因此，从某种意义上说，推荐系统和搜索引擎对于用户来说是两个互补的工具。搜索引擎满足了用户有明确目的时的主动查找需求，而推荐系统能够在用户没有明确目的的时候帮助他们发现感兴趣的新内容[9]。

用户行为学习

基于用户行为分析的推荐算法是个性化推荐系统的重要算法，学术界一般将这种类型的算法称为协同过滤（collaborative filtering）算法。顾名思义，协同过滤就是指用户可以齐心协力，通过不断地和网站互动，使自己的推荐列表能够不断过滤掉自己不感兴趣的物品，从而越来越满足自己的需求。用户行为在个性化推荐系统中一般分两种——显性反馈行为（explicit feedback）和隐性反馈行为（implicit feedback）。显性反馈行为包括用户明确表示对物品喜好的行为。很多网站都使用了5分的评分系统来让用户直接表达对物品的喜好，但也有些网站使用简单的“喜欢”或者“不喜欢”按钮收集用户的兴趣。

和显性反馈行为相对应的是隐性反馈行为。隐性反馈行为指的是那些不能明确反应用户喜好的行为。最具代表性的隐性反馈行为就是页面浏览行为。用户浏览一个物品的页面并不代表用户一定喜欢这个页面展示的物品，比如可能因为这个页面链接显示在首页，用户更容易点击它而已。相比显性反馈，隐性反馈虽然不明确，但数据量更大。

用机器学习的方法来理解用户的隐性反馈行为，再进行排序打分，是这几年研究比较多的，代表方法有BPR [10]。BPR（Bayesian Personalized Ranking）的基本思想是用机器学习的方法，直接根据用户的隐式反馈来优化推荐物品的排序。它使用物品对（item pairs）作为训练集来优化物品间的排序，而不是给单个物品打分。一般机器学习方法，需要正反例来进行训练。但是在隐式反馈下，只有正例被观察到，如物品被点击、浏览、购买等，并没有明确的反例。如果直接把那些没有用户行为的物品作为反例，则其中可能会把用户潜在感兴趣的物品错误标成反例，影响学习效果。通过把物品对作为训练集，并把排序而不是打分作为优化目标，可以避免这个问题。

用户标签学习

最简单的基于标签推荐算法是，首先找到一个用户的常用标签，再统计具体这些标签的物品推荐给用户。通过适当惩罚热门标签和热门物品，可以提高算法的效果。还可以对标签集合进行扩展，比如话题模型。扩展的本质是对每个标签找到和它相似的标签，如同义词。也可以从数据统计中计算标签的相似度。更加理论化和系统化的算法，参见基于图的推荐算法。

基于标签的推荐系统其最大好处是可以利用标签做推荐解释，还可以让用户自己选择感兴趣的标签，来调整推荐结果。一些研究结果： 1、用户对标签的兴趣对帮助用户理解为什么给他推荐某个物品更有帮助； 2、物品的标签相关度对于帮助用户判定被推荐物品是否符合他当前的兴趣更有帮助； 3、客观事实类标签比主观感受类标签对用户更有作用。

Linkedin在他们的推荐系统中使用了一种Virtual Profile的方法，根据用户和物品之间的交互行为选择生成正反例，再通过对正反例的学习获得Virtual Profile，从而丰富了标签，取得了比一般协同过滤方法更好的效果[11] [12]。

候选集排序学习

对于不同推荐算法触发出来的候选集，只是根据算法的历史效果决定算法产生的item的位置显得有些简单粗暴，同时，在每个算法的内部，不同item的顺序也只是简单的由一个或者几个因素决定，这些排序的方法只能用于第一步的初选过程，最终的排序结果需要借助机器学习的方法，使用相关的排序模型，综合多方面的因素来确定。

非线性模型能较好的捕捉特征中的非线性关系，但训练和预测的代价相对线性模型要高一些，这也导致了非线性模型的更新周期相对要长。反之，线性模型对特征的处理要求比较高，需要凭借领域知识和经验人工对特征做一些先期处理，但因为线性模型简单，在训练和预测时效率较高。因此在更新周期上也可以做的更短，还可以结合业务做一些在线学习的尝试。

最近的趋势是使用类似搜索learning to rank的方法来解决推荐里候选集排序的问题，本质上是类似的，代表方法有LRHR[13]。LRHR（Learning to Rank for Hybrid Recommendation）把推荐系统中的用户和物品分别用向量来表示，再采用RankSVM方法对推荐候选集进行排序，取得了不错的效果。

参考文献

[1] 张俊林，这就是搜索引擎：核心技术详解，电子工业出版社，2015

[2] CJC Burges, From RankNet to LambdaRank to LambdaMART: An Overview, Microsoft Research Technical Report, 2010

[3] Z. Zheng, K. Chen, G. Sun, and H. Zha, A Regression Framework for Learning Ranking Functions Using Relative Relevance Judgments, SIGIR, 2007

[4] Dawei Yin, et al., Ranking Relevance in Yahoo Search, KDD, 2016

[5] Liu, et al., BrowseRank: Letting Users Vote for Page Importance, SIGIR, 2008

[6] Gao, et al., Click-through-based Translation Models for Web Search: from Word Models to Phrase Models, CIKM, 2010

[7] Wu, et al., Learning Query and Document Similarities from Click-through Bipartite Graph with Metadata, Microsoft Research Technical Report, 2011

[8] 李航，搜索与机器学习，中国计算机学会技术动态第52期人工智能专题，2012

[9] 项亮，推荐系统实践，北京图灵文化发展有限公司，2012

[10] S. Rendle , et al., BPR: Bayesian Personalized Ranking from Implicit Feedback, UAI, 2009

[11] H. Liu, et al., Generating Supplemental Content Information Using Virtual Profile, RECSYS, 2013

[12] H. Liu, et al., Improving The Discriminative Power of Inferred Content Information Using Segmented Virtual Profile, RECSYS, 2014

[13] J. Sun, et al., Learning to Rank for Hybrid Recommendation, CIKM, 2012