## WSDM 2017精选论文

数据挖掘和机器学习应用的顶级会议The Tenth ACM International Conference on Web Search and Data Mining （WSDM 2017）今年2月已经在英国剑桥圆满举行。正值 WSDM 十周年，会议上对 WSDM 的发展进行了回顾和展望。纵观过去十年的发展，WSDM 已经成长为学术圈和工业界都十分倚重的经典跨界会议。不像 KDD、WWW 或者
 SIGIR，WSDM 因为从最开始就由不少工业界的学术领导人发起并且长期引领，所以十分重视工业界的学术成果的展现。有不少经典的工业界文章在过去十年里，都是通过 WSDM 发表的。今年也不例外，因为 WSDM 的论文涵盖非常广泛的主题，而且一般的读者很难从浩如烟海的文献中即刻抓取到有用信息，这里笔者从80篇会议文章中精选出5篇有代表性的文章，为读者提供思路。

#### Unbiased Learning-to-Rank with Biased Feedback

**概要：这篇文章获得了 WSDM 2017最佳论文。在实际生产中，我们大量获得的是 “有偏差”（Biased）的数据。那么，如何从这些 “有偏差”的数据中，进行“无偏差”（Unbiased）的机器学习就成为了过去很长一段时间以来，实际生产中非常急迫解决的问题。本文探讨了解决这个问题的一种思路。**

这篇文章来自康奈尔大学的 Thorsten Joachims 以及他的学生。Thorsten 在上一个十年的学术研究中，因为开发 SVMLight 而名声显赫。他也是最早思考如何利用用户反馈数据进行排序模型（Ranking Model）训练的学者。那么，这篇获奖论文主要是要解决一个什么样的问题？其实，这篇文章要尝试解决的问题在学术和工业界的应用中非常普遍，可以说是一个困扰学者和普通的工程人员已久的问题。那就是，如何从“有偏差”用户反馈数据中，训练“无偏差”的排序模型。为什么用户反馈数据会“有偏差”？道理很简单，用户在和系统交互的时候，受到各方面因素的干扰，从而只对部分信息进行了反馈而忽略了其他信息。

比如，在搜索引擎里，因为排版的因素，用户可能仅仅对排名靠前的几个文档进行查看，而彻底忽略排名靠后的所有文档，即便这些文档其实可能是相关的。另外一个更加常见的“偏差”则是由现在的“作业系统”（Production System）引起的。“作业系统”往往根据现有的算法或者模型选择出了用户可能最偏好的少部分文档，而大多数文档用户则没有可能见到，和前面情况一下，即便这些文档有可能是十分相关的。于是，用户的反馈就受到了现在系统的影响，而后面的机器学习很有可能仅能从现在系统偏好中改进，而有可能无法提升到全局最优的情况。

传统中，很多学者和从业人员已经意识到了直接使用用户“有偏差”反馈的数据，特别是点击数据，会产生问题。但是很长一段时间来，大家并没有找到如何系统地解决这个问题。Thorsten 首先在这篇文章中提出了基于 Inverse Propensity Scoring（IPS）的 Partial-Info Learning-to-Rank。这部分内容其实并没有太多的新意，不过是把从 Multi-armed Bandit 领域用 IPS 来做 Unbiased Offline Evaluation 的思路借鉴过来。不过文章指出了一个核心问题，那就是如何来估计这些 Propensity Probability，其实也就是当前系统选择各个文档的概率。传统上，特别是以前的 Unbiased Offline Evaluation 基于随机产生文档顺序，因此这些 Propensity Probability 都是 Uniform 分布的。但这样的设计在现实中是不可能的，因为Uniform分布的文档，用户体验会变得很差。那么，这篇文章则是要直击这个痛点。

这篇文章采取了这样一个思路，文章假设现在系统的“偏差”可以通过一个 Position-based Click Model with Click Noise（PCMCN）来解释。简单说来 PCMCN 就是来对用户查看一个排序文档进行建模，从而达到可以 Propensity Probability 能够被方便预测，这么一个目的。为了能够 PCMCN，作者们还提出了一个基于交换两个位置文档的实验方法，用于收集数据。值得肯定的是，仅仅交换两个位置文档的方法，相比于以前的 Uniform 的方法，要更加注重用户体验。文章的实验部分展示了在人工数据以及真实系统中的表现。总体说来，能够对“有偏差”的用户数据建模，比直接利用这些数据，训练的模型效果要来的好得多。这篇文章非常值得推荐系统、搜索引擎等方面的研究和工程人员精读。

#### Real-Time Bidding by Reinforcement Learning in Display Advertising

**摘要：传统中，Real-Time Bidding（RTB）把 Bidding 考虑成为静态的决策过程。这篇文章，则是把 Reinforcement Learning（强化学习）引入到 RTB 的应用中，从而提高 RTB 的效率和整体效果。**

这篇文章的作者团队来自上海交大和伦敦大学学院（University College London）。此文是继强化学习被应用到搜索和推荐领域之后，又一个把强化学习应用到一个重要领域的尝试。与推荐和搜索不同的是，RTB 因为其实时性，更加讲究能够对于一个决策过程进行动态调整，从而能够提供最优的解决方案。目前大多数 Bidding 算法或者是策略（Strategy）的核心问题，就是他们都是静态的一个决策过程。那么，这篇文章的主要思路就是用 Markov Decision Process（MDP）来对 RTB 进行建模。

MDP 的一般建模，需要三个必备元素，那就是 State、Action 和 Reward。这里，State 是一个（当前时间，剩余预算，当前 Feature Vector）三元组；Action 则是以 State 为输入，输出一个少于当前预算的 Bid；Reward 在这篇文章里定义为在当前 Feature Vector 为输入情况下的点击率（CTR）或者是0（没有赢得 Auction 的情况）。MDP 除了这三个要素以外，一般还需要定义从每一个状态跳转另外状态的转移概率。文章中，转移概率是一个 Feature Vector 的概率分布和市场价格分布的一个乘积。市场价格分布取决于现在的 Feature Vector 和当前的 Bid 价格。整个 MDP 的布局设置好以后，RTB 的问题就转换成为了如何在 MDP 中找到最优 Action 的决策问题。和传统的 MDP 一样，文章介绍了通过 Value Iteration 的方式来找到最佳的 Value 函数，然后通过找到的 Value 函数，来找到最佳的 Bidding 策略。

然而，这样的方法，只适合在比较小规模的数据上，原因是第一个阶段的得到最佳 Value 函数的步骤太过于耗时。文章介绍了一种在大规模数据上的思路，通过小数据来学习 Value 函数的表达，然后应用到大规模数据上。文章在两个数据集上做了实验，一个是 PinYou 的数据，另一个是 YOYI 的数据，数量都算是当前比较大的 RTB 数据集了。从实验结果上来看，采用 MDP 的方法能够比其他方法大幅度有效提高 CTR，以及各项指标。除了在这两个数据集上的结果以外，这篇文章还在 Vlion DSP 的线上系统进行了评测，在 CTR 基本和以前方法持平的情况下，CPM 和 eCPC 都更加有效。总之，这篇文章对于希望探索强化学习在广告或者是推荐以及搜索等领域的应用有着一定的借鉴意义。从目前的情况来看，算法依然比较复杂，而且 Value 函数的逼近可能有不小的性能损失。另外，参考文献部分十分详尽，对于想了解 RTB 的朋友来说，是一个不可多得的言简意赅的介绍。

#### Learning Sensitive Combinations of A/B Test Metrics

**摘要：在线 A/B 实验最大的困扰就是所需要观测的指标（Metric）常常需要很长时间观测到统计意义的变化抑或需要很多的用户数量。这篇文章就是要尝试解决这么一个问题，探讨如何通过 Variance Reduction 的办法来让寻找到的 Metrics 能够更加容易观测，并且和用户的指标相匹配。**
 
这篇文章来自俄罗斯搜索引擎团队 Yandex。近几年以来，Yandex 的研究人员已经陆续发表了一系列的文章来推动在线 A/B 实验的研究和实践。这篇文章是要解决什么问题呢？在 A/B 在线测试中，我们希望观测到的指标有方向性，能够告诉我们用户的喜好变化；同时，我们也希望这个指标能够很容易观测，不需要大量的数据长时间观察。文章提出了这么一个假设，那就是我们能否通过数据以及历史信息，学习到一组指标的组合，使得这个学习到的结果满足上述条件？Yandex 通过对8个关键指标的建模，使得学习到的指标达到了3.42倍的“敏感度”（Sensitivity），相比于之前的指标而言，也就是达到了约11倍的
 Sample Size 的削减，可以说效果非常显著。那么，这篇文章的作者是如何做的呢？

首先，每一个实验单元（可以是一个用户，一个 Session 或者一个 Query）都被一个
 Feature Vector 所描述。这里的Feature Vector，有可能就是我们已知的指标本身。那么，整个问题的设置就成为了，学习一个这些 Feature Vector 的线性组合，使得学习到的新指标对于未来的实验，更加具有“敏感度”。文章中，作者讨论了多种定义“敏感度”的方法，而最终采用的是通过z-score来衡量。这样的选择，非常接近普通的 t-test 的需要。也就使得这篇文章的实用度更加广泛。如果来解这么一个优化问题就成为了文章下一个重点。文章简单介绍采用 Geometric 的方法来接这个优化问题的思路，并且也探讨了一下这种方法和 Linear Discriminant Analysis 的联系。

然而作者们认为这个思路并不适合大多数的情况，于是文章介绍了一个基于标准优化算法的思路。也就是，利用定义的“敏感度” z-score，作为衡量两个实验结果的“距离函数”，最终的目标函数是包括这么三个部分：1. 尽量让已知A/B有效果的实验里的距离不减少；2. 尽量让已知的 A/A 实验的结果不变化；3. 尽量分离已知A/B实验效果不明显的结果。当然，这个目标函数是 Non-Convex 的，不过文章依然使用了L-BFGS来解这个优化问题。从实验来说，作者们用了118个历史实验数据来学习这个函数，得到的效果都是学习到的指标能够更好地指导实验的结果，同时采用学习到的指标能够大幅度降低需要达到统计意义效果明显（Statistically Significant）的数据量，这对于真实的工业环境来说是非常有意义的方法。这篇文章建议所有工业界的读者精读。

#### Recurrent Recommender Networks

**摘要：如何把深度学习和推荐系统相结合是最近一两年来推荐系统领域学者比较关心的问题，这篇文章探讨了如何把 LSTM-Autoregression 模型和推荐系统结合的例子，在真实的数据中达到了更好的效果。**

这篇文章来自卡内基梅隆大学 Alex Smola 的实验室以及 Google 研究院的 Amr Ahmed，阵容可谓非常强大。从传统的概率图模型（Probabilistic Graphical Model）的角度来说，要想能够对时间信息（Temporal）进行有效建模，则必须采用
 Sequential Monte Carlo 等其他办法。这些办法往往计算非常复杂而且极易出错。所以，这篇文章希望通过 RNN 来帮助这样的建模场景。文章希望能够用 RNN 来对现在的观测值以及模型参数的时间变化进行统一建模。

当然，另外一个比较好的选择就是 LSTM。这篇文章采用了 LSTM。有了时间的变化以后，在单一时间的 Rating Prediction，则是用户方面信息和物品（文章中采用的是电影）信息的点积，非常类似传统的矩阵分解模式。有一个小改动的地方来自于最后的预测结果是一个与时间有关的变化和与实践无关变量的一个分解。这一点主要是为了让不同时间段的变化都能够被模型解释。这样看似简单一个模型最大的问题其实是优化算法，如果使用简单的 Back-propagation，计算量则会很大。这篇文章采用了一个叫 Subspace Descent 的方法，使得优化算法本身能够比较便捷。在实验中，文章比较了 TimeSVD++ 以及之前提出的 AutoRec，在 IMDB 和 Netflix 的数据集上都有显著的提高。当然，从比较大的角度来看，这篇文章的意义其实非常有限，主要是最近类似思路的文章其实已经有不少，并且从学术贡献来看，这篇文章完全解答了如何用深度学习和推荐系统结合的更佳的根本问题，适合熟悉推荐系统的读者快速阅读。

#### Learning from User Interactions in Personal Search via Attribute Parameterization

**摘要：传统的基于机器学习的排序模型训练都是依赖于从大量的用户数据得到训练数据。而这篇文章要解决一个比较极致的问题，那就是如果模型需要应用到一个用户的时候，如何采集有效的训练数据并且训练一个有效的模型。 **

这篇文章来自 Google 的个人搜索团队，所有作者都是信息检索界响当当的学者。Marc Najork 之前来自微软硅谷研究院，曾是《ACM Transaction on Web》的主编。微软硅谷研究院解散之后来到 Google。而 Donald Metzler、Xuanhui Wang 以及Michael Bendersky都是信息检索界大牛 W. Bruce Croft 的得意门生。

这篇文章是要解决所谓个人搜索（Personal Search）的问题。个人搜索，顾名思义，也就是对个人的文档进行搜索（比如电子邮件、文本文件、图片、资料等）。由于这样特殊的产品需求，传统的很多方法都不能够直接适用。另外一个特殊的需求是，由于涉及到用户的个人隐私，不能够盲目把不同用户的信息交互到一起。要解决这些问题，这篇文章提供了这样一个基本思路，那就是把用户的 Query 以及文档都映射到一个 Attribute 的空间。在这个空间里，所有的信息都可以跨用户横向比较。

那么，下面的问题就是我们如何把这些信息给映射到这个 Attribute 的空间。作者们采用了构建一个图（Graph）的做法。在这个图上有四个类型的节点：文档、Query、文档的 Attribute 和 Query 的 Attribute。两种节点之间的链接是通过 Feature Function 来定义的。这一点很像 Markov Random Field 的构建。这也难怪作者之一的 Donald Metzler 曾经是提倡使用这类模型的主要推手。

在定义 Feature Graph 之后，作者们提出了两种思路来使用 Feature Graph，一种就是直接用机器学习的方法；另一种则是手工方法和机器学习方法的混合。这篇文章采用了第二种方法，因为这样在一个生产系统中可能更加稳定。从整体上来看，整个技术层面并不复杂，不过这里的思路相对来说比较新颖。同时，作者还提到了如何从点击数据中提取有效的训练数据。在最后的实验方面，作者们展示了提出的这种方法的有效性。不过，值得一提的是，因为数据集和整个问题的特殊性，这篇文章并没法和很多其他方法进行公平比较。所以，文章值得对搜索和信息检索研究有兴趣的读者泛读。