Paper Summary

summary

一文掌握机器学习算法工程师技术栈

1. 扎实的理论基础很重要：概率论+机器学习
2. 机器学习可以看做是建立在概率思维之上的一种对不确定世界的系统性思考和认知方式。
3. 机器学习模型的优化过程同时也可以看作是最小化数据集中信息量的过程。【比如决策树：每一次的split，至少要满足信息增益达到某个阈值，否则停止树的生长。】

浅谈影响推荐系统效果的一些因素

1. 影响推荐系统效果的一个很重要的原因是：“新用户（冷启动）问题”
2. 解决冷启动问题的方式有两种：“努力优化推荐系统的冷启动算法” & “努力将平台上的新用户转化为老用户”。
3. 第二种的效果要更好，这主要是因为冷启动算法的优化空间实在有限，而将其转为“热”用户之后，各种优化策略就都可以派上用场了。这也是一种可以在多种场景下借鉴的思路：将未知问题转化为已知问题，而不是创造新问题。

【翻译+批注】亚马逊推荐二十年

• 亚马逊ItemCF推荐系统的整体架构：
  离线计算item之间的相似度，存储一个推荐列表。当user购买了$item_i$时，将$item_i$对应的推荐列表实时select。
• 一个合理的“相关”定义，对推荐系统的帮助非常大：
  
  • “相关”可以表示多种含义，但在这里，我们可以将其模糊地定义为“买了一个物品的人具有超乎寻常的可能性（unusually likely）会买另外一个”所以，对于每个物品i1，我们希望得到所有购买了i1的用户会以超乎寻常的频率一起购买的i2。
  • 基于item进行协同过滤，计算出用户购买$item_i$相似度比较高的物品序列。同时计算购买了$item_i$的用户最有可能购买的item列表；（可以理解为UserCF） 暂时不知道是怎么做到的？
• 当前互联网环境是：物品数的变化频率 < 用户数的变化频率，itemCF比userCV更加顺应时代。
• 充分理解时间扮演的角色对于改进推荐系统质量有着重要的作用。
  
  • 当计算相关物品时，两个物品的相关性很大程度上依赖他们在时间间隔的长短。如果一个用户在买了一本书的五个月之后又买了一本书，那这两本书之间的相关性就要弱于两本在同一天内被购买的书的相关性。
  • 时间的方向性也比较有用。例如，用户会在买了相机之后买存储卡，而不是反过来。这告诉我们不应该给购买了存储卡的用户推荐相机。有时物品的购买具有序列性，例如书籍、电影和电视剧，那么推荐就应该给出你下一步想要做的东西。
  • 即使对于信息完备的用户，正确地使用时间信息对于推荐质量也有着重要影响。随着年龄的变化，之前的购买对于用户当前的兴趣的影响越来越小。
• 冷启动问题的拟解决
  
  • User维度的冷启动，个人的想法：
    
    • 现在越来越多的App在注册时候，需要手机号或者微信登陆或者微博登陆，在某种意义上就是为了解决冷启动的问题。
    • 当我们缺乏用户在这个产品的行为数据时，企图通过这种方式获取他的用户画像，基于UserCF或其它算法，做冷启动的推荐。
  • Item维度的冷启动，亚马逊的解决：
    
    • 借助E/E的方式来给予新商品足够的曝光机会。新闻和社交媒体这些易过期的物品在冷启动方面尤其具有挑战性，通常需要融合基于内容的算法（使用题目，主题和文本等）和基于行为的算法（使用购买，浏览和打分等）。
• 推荐的质量不仅取决于购买的时间，还取决于购买的内容。
  
  • 开发一种技术，能够识别哪些购买能提供有用的推荐而哪些应该被忽略。
• 推荐系统中多样性的重要性也是众所周知的。有时相比一个范围很窄的推荐列表，给出一些更多样的相关物品会更好。
• E&E 解决冷启动问题
  
  • 如何去尝试新用户的兴趣点，尝试到什么时候地步才算真正掌握了用户的兴趣，用户的兴趣发生改变如何灵活的调整推荐策略
  • E&E问题：Exploitation & Exploration
    
    • Exploit就是眼前的苟且，Explore就是诗和远方的田野。
    • Exploitation是守成，Exploration是去尝试新的可能性。
    • Exploitation：基于已知最好策略，开发利用已知具有较高回报的item（贪婪、短期回报）。可以充分利用已知高回报item，但容易陷于局部最优，错过潜在更高回报item的机会。
    • Exploration：不考虑曾经的经验，勘探潜在可能高回报的item（非贪婪、长期回报）。可以发现更好回报的item，但充分利用已有高回报item机会减少（如已经找到最好item）
  • 详见

推荐系统老司机的 $N$ 条经验

• 隐式反馈比显式反馈要爽
  
  • 隐式反馈，就是用户发出这些行为时并不是为了表达兴趣/态度，只是在正常使用产品而已，反之，显式反馈就是用户在做这个操作时就是要表达自己的态度，如评分，投赞成/反对票。
  • Xavier Amatriain列举了隐式反馈的以下好处：
    
    • 数据比显式反馈更加稠密。诚然，评分数据总体来说是很稀疏的，之前netflix的百万美元挑战赛给出的数据稀疏度大概是1.2%，毕竟评分数据是要消耗更多注意力的数据。
    • 隐式反馈更代表用户的真实想法，比如你不是很赞成川普的观点，但是还是想经常看到他的内容（以便吐槽他），这是显式反馈无法捕捉的。而人们在Quora上投出一些赞成票也许只是为了鼓励一下作者，或者表达一些作者的同情，甚至只是因为政治正确而投，实际上对内容很难说真正感兴趣。
    • 隐式反馈常常和模型的目标函数关联更密切，也因此通常更容易在AB测试中和测试指标挂钩。这个好理解，比如CTR预估当然关注的是点击这个隐式反馈。
    • 举个例子，IMDB的电影排名，对比一下用票房排名和用评分排名，票房其实是一种隐式反馈的量化，表示“看过”，而评分则是显式反馈。一些小众电影的评分比较少，在依靠评分排名时不太占优势，而依靠隐式反馈排名则会有所缓解。
  • 隐式反馈有个比较大的问题就是：
    
    • 短视。现在有很多手段来吸引用户点击，比如高亮的标题，还有一些“三俗”的图片，都会吸引用户点击，这种利用了人性弱点的隐式反馈，对平台的长期价值是有损的，所以也不能一味使用隐式反馈，而是需要隐式反馈和显式反馈结合使用，兼顾短期利益和长期价值。
• 深刻理解数据
  
  • 理解好了业务逻辑，才能理解好数据。
• 为模型定义好学习任务
  
  • 一个机器学习模型有三个因素构成：
    
    • 训练数据（隐式反馈或者显式反馈）
    • 目标函数（比如用户阅读一篇回答的概率）
    • 衡量指标（比如准确率或者召回率）
  • 假如现在有这么一个问题：用户的购物历史以及历史评分，去优化用户走进电影院看完一部电影并且给出高分的概率，NDCG作为模型的评价指标，4分以上作为正样本。这样就比较清晰的定义了学习任务的三元素：
    
    • 训练数据：用户购物历史和历史评分
    • 目标函数：用户走进电影院看完电影且给出高分的概率
    • 衡量指标：NDCG。
    • 如果定义评价指标时模糊不清，如不说明是4分以上的作为正样本的话，就失去了显式反馈的信息，失去了对平台长期利益的关注。
  • Quora的兴趣feed排序。
    
    • Quora的首页是结合了多个用户隐式反馈的排序模型，给每一种用户行为建立一个预测模型，预测它发生的概率，结合每一种行为带来的长期价值大小，然后加权，即期望价值。
    • 训练数据：用户的显式反馈和隐式反馈
    • 目标函数：一个story的展示价值，量化定义为用户行为的期望价值
    • 衡量指标：任何排序模型指标都可以
• 推荐可解释比精准更有意义
• 矩阵分解大法好
  
  • Xavier Amatriain很推崇Matrix Factorization，因为它既有监督学习，又有无监督学习。
  • 两种学习方法就这样结合在一个算法里：
    
    • 它可以用来降维，这部分通常是PCA这样的无监督学习算法承担的，矩阵分解得到的隐因子就是降维后的特征，可以直接作为其他学习算法的输入；
    • 它还可以做聚类，比如Non-negative Matrix Factorization就常常用来做聚类；
  • SVD就是一种回归，标准的监督学习。矩阵分解还有一些变种：ALS（交替最小二乘），SVD++（结合特征的SVD），FM（因子机），TF（张量分解）。
  • 总之，在推荐系统里，使劲压榨矩阵分解的效果。
• 推荐系统也不能免俗之特征工程，好的特征有以下特点：
  
  • 可复用。可复用就是说不止一个模型可以用，换个模型一样用。
  • 可转换。特征是既可以直接使用，也可以进行一些尺度转换的，比如对数转换等。
  • 可解释。特征的物理意义需要很清楚。
  • 可靠。特征出现异常的话需要能及时监控到，也要容易调试。
• 对你的推荐系统要了如指掌
  
  • 推荐系统里面，模型对于很多人来说都是黑盒子，甚至对于算法工程师自己来说也是黑盒子，并不太清楚某个东西为什么被推出来，某个东西为什么用户没买帐或者买帐。
  • 通常产品经理对推荐系统都有一定的预期，推荐的东西不能让他们理解，解释起来也比较麻烦，也是通常算法工程师和PM产生争端的原因所在。对于黑盒一般的模型，我们要能够做到可以回答任何人的任何问题。模型应该做到“可调试”（debuggability）。
  • 举个例子，一个决策树算法，从根节点开始，一步一步经过了哪些决策节点得到了最终的预测结果呢？如果有工具可以直观展现出来，我们就能知道哪些特征起了更重要的作用，是不是合理的。
  • Xavier 提到在Quora内部就有个工具，可以看到某个人的首页feed的每一个内容的分数，以及每个分数计算所依赖的特征，这样就很清楚知道为什么你“看到/没看到”某个人的回答或问题。
• 数据和模型是重要，但正确的演进路径更不容忽视。正确的演进路径：
  
  • 首先提出一个假设，可以通俗的说是对问题的一个猜想。
  • 针对这个假设，我们要选择用什么模型。
  • 模型选定后训练模型，离线测试，如果验证通过就要上AB测试，否则要么换个模型，要么重新审视一下你的假设是不是站得住脚；
  • 上AB测试，测试结果明显提升的话就上线，否则滚回去再看看最开始你那个假设是不是靠谱。
  • 这个过程有几个地方比较难：
    
    • 第一个就是离线模型评价指标的选择，不同的指标可能包含不同的意义，例如同样是Learn to rank的排序评价，MRR和NDCG这两个指标对于排序靠前的项目权重就会更大，而FCP（Fraction of Concordant Pairs）就更看重排序靠中间的项目。所以选择什么指标要仔细思考，离线评价表现好才有机会有必要上AB测试。
    • 第二个就是离线评价（通常是技术性或者学术性的，比如准确率）和在线产品指标（通常是商业性的，比如留存率）之间通常是存在鸿沟的。模型的离线评价效果可能很好，但是在线去测试，产品指标可能表现不好，可以离线的时候换一个与直接产品指标更相关的评价指标。
    • 第三个就是AB测试的时候一定注意要有一个总体评价指标（ Overall Evaluation Criteria），很多人（通常是产品经理）会同时关注一个AB测试的很多指标，点击率上去了，多样性又下去了，这种测试结果你很难说是该上线还是该下线，所以说需要一个 Overall Evaluation Criteria，如果你有多个目标，就想法把多个目标整合成一个数值指标，这样才能够最终决定AB测试是成功还是失败。 Overall Evaluation Criteria通常是更接近商业目标和平台长期价值的数值，要定义出来需要深度的思考。
    • 最后提一下，AB测试并不是唯一确定新算法是否上线的方式，还有一种方法是bandit算法，见专治选择困难症——bandit算法。

搜索、推荐和广告架构能统一吗？

• 搜索，推荐和广告本质上都在解决信息过载的问题，本质上都是在匹配，匹配用户的兴趣和需求（看成context）。
• 都可以抽象为以下三步：
  
  • 过滤候选（$filter$）
  • 排序候选（$ranking$）
  • 个性化输出（$personalization$）。
• 搜索广告是拿着query去获取候选广告，而联盟广告则是拿着用户标签去需求方获取广告候选。
• 三者在 filter 这一步上比较类似，主要的区别在于 ranking 上。
  
  • 推荐系统的ranking比较复杂，相关性只是很小的部分，根据推荐系统的产品形式不同，ranking时排序不同。通常推荐系统用CTR预估来融合各种召回策略得到的候选集，如果做得深入，还需要考虑Exploit－Explore问题。附加的约束则千变万化：电商中，当天买过的当天就不能再推了，新闻推荐里，重复的新闻不能再推了，某些场景需要推荐搭配，某些场景需要推荐相似，$top$ $N$ 推荐还需要考虑多样性，序列推荐要考虑前序和后续。
  • 广告系统的ranking更多是从经济学角度去看，通常CPC广告的排序方式是结合预估CTR、出价、广告质量三者一起考虑。
• personalization最被推荐系统看重，而且在某些场合，个性化一度成为推荐系统的代名词，然而个性化只是推荐系统的衡量指标之一而已，个性化的前提是信息够丰富and够垂直。

专治选择困难症——Bandit算法

• 一个赌徒，要去摇老虎机，走进赌场一看，一排老虎机，外表一模一样，但是每个老虎机吐钱的概率可不一样，他不知道每个老虎机吐钱的概率分布是什么，那么想最大化收益该怎么整？这就是多臂赌博机问题（Multi-armed bandit problem, MAB）。
• 推荐系统里很多问题都与它类似：
  
  • 假设一个用户对不同类别的内容感兴趣程度不同，那么我们的推荐系统初次见到这个用户时，怎么快速地知道他对每类内容的感兴趣程度？这就是推荐系统的冷启动。
  • 假设我们有若干广告库存，怎么知道该给每个用户展示哪个广告，从而获得最大的点击收益？是每次都挑效果最好那个么？那么新广告如何才有出头之日？
  • 我们的算法工程师又想出了新的模型，有没有比A/B test更快的方法知道它和旧模型相比谁更靠谱？
  • 如果只是推荐已知的用户感兴趣的物品，如何才能科学地冒险给他推荐一些新鲜的物品？
• 用Bandit算法解决冷启动的大致思路：
  
  • 用分类或者Topic来表示每个用户兴趣，也就是MAB问题中的臂（Arm），我们可以通过几次试验，来刻画出新用户心目中对每个Topic的感兴趣概率。
  • 如果用户对某个Topic感兴趣（提供了显式反馈或隐式反馈），就表示我们得到了收益，如果推给了它不感兴趣的Topic，推荐系统就表示很遗憾（regret）了。对“收益”的定义，直接影响着后面各Bandit的计算结果。可以将“收益”理解为：点击 or 特定行为（安装或注册或收藏等）
  • 如此经历“选择-观察-更新-选择”的循环，理论上是越来越逼近用户真正感兴趣的Topic的。
• 关于怎么衡量不同Bandit算法在解决多臂问题上的效果？首先介绍一个概念，叫做累积遗憾（regret）。
  
  
  • 首先，这里我们讨论的每个臂的收益非0即1，也就是伯努利收益。
  • 然后，每次选择后，计算和最佳的选择差了多少，然后把差距累加起来就是总的遗憾。
  • $w_B(i)$是第i次试验时被选中臂的期望收益， $w^*$是所有臂中的最佳那个，如果上帝提前告诉你，我们当然每次试验都选它，问题是上帝不告诉你，所以就有了Bandit算法。
  • 这个公式可以用来对比不同Bandit算法的效果：对同样的多臂问题，用不同的Bandit算法试验相同次数，看看谁的regret增长得慢。
• 常见的Bandit算法：
  
  • Thompson sampling算法，原理为：
    
    • 假设每个臂（臂 = item = offer）是否产生收益，其背后有一个概率分布，产生收益的概率为p
    • 我们不断地试验，去估计出一个置信度较高的“概率p的概率分布”就能近似解决这个问题了。
    • 怎么能估计“概率p的概率分布”？ 答案是假设概率p的概率分布符合beta(wins, lose)分布，它有两个参数: wins, lose。
    • 每个臂都维护一个beta分布的参数。每次试验后，选中一个臂，摇一下，有收益则该臂的wins增加1，否则该臂的lose增加1。
    • 选择臂的方式是：用每个臂现有的beta分布产生一个随机数b，选择所有臂产生的随机数中最大的那个臂去摇。
    • 使用Thompson sampling解决冷启动问题：
      
      • 用分类或者Topic来表示每个用户兴趣，我们可以通过几次试验，来刻画出新用户心目中对每个topic的感兴趣概率。
      • 如果用户对某个topic感兴趣，就表示我们得到了win，如果推给了它不感兴趣的topic，推荐系统就表示lose了。
      • 当一个用户来了，针对这个用户，我们用Thompson算法为每一个topic采样一个随机数，排序后，输出采样值top N 的推荐item。注意，这里略有改动，原始多臂问题每次只摇一个臂，我们这里一次摇N个臂。
      • 获取用户的反馈，比如点击。没有反馈则更新对应topic的lose值，点击了则更新对应topic的wins值。
  • Upper Confidence Bound(置信区间上界)
    
    • 先对每一个臂都试N遍（N为可接受的成本投入）
    • 每次选择以下值最大的那个臂
    • 
      （1）均值越大，标准差越小，被选中的概率会越来越大，起到了exploit的作用。试验次数多，Item的置信区间很窄，这是算法保守稳妥的部分。
      （2）同时哪些被选次数较少的臂也会得到试验机会，起到了explore的作用。试验次数少，Item置信区间很宽，这是算法冒险的部分。
      （3）为什么会这样：随着迭代轮数的增长，上界会远离均值
      随着被选择次数的增长，上界会靠近均值。
    • 观察选择结果，更新$t$和$T_j,_t$。（需要设定一个试验终止条件，即循环次数$t$。t=1时，没有均值和标准差可言。）
    • 加号前面是这个臂到目前的收益均值，后面的叫做bonus，
    • 本质上是均值的标准差，$t$是目前的试验次数，$T_j,_t$是这个臂被试次数。
  • 我们用10000次模拟试验的方式对比了其效果如下图：
    
  • 算法效果对比一目了然：UCB算法和Thompson采样算法显著优秀。
    至于你实际上要选哪一种Bandit算法，你可以选一种Bandit算法来选Bandit算法。

# Thompson sampling算法
choice = numpy.argmax(pymc.rbeta(1+self.wins, 1+self.trials-self.wins))
# numpy.argmax 返回沿轴axis最大值的索引。
array_1 = [1,2,3]
array_2 = [0,9,4]
a = np.array([array_1, array_2])
np.argmax(a, axis=0)  # 输出 array([0, 1, 1])
np.argmax(a, axis=1)  # 输出 array([2, 1])

少数人的智慧

• 先装逼地定义什么是「专家/Expert」：
  在一个特定的领域内，能对该领域内的条目给出深思熟虑的、一致的、可靠的评价（打分）。
• Expert-CF 大多数情况下与 NN-CF 效果相当。
• Expert-CF 的用户满意度更高。
• Expert-CF 的可用性之后，吸引人的是这个方法相对传统CF方法，能够带来的好处：
  
  • Data Sparsity，数据稀疏性
    专家的打分数据数据通常涵盖面更广，使用这个数据作推荐，解决了传统 CF 的数据稀疏问题。
  • Noise and Malicious Ratings，噪音及恶意打分
    专家的打分通常更加认真或是专业，解决了用户不小心打错分及恶意捣乱的问题。
  • Cold Start Problem，冷启动问题
    专家通常更加关注自己领域内的新事物，并能够更快地给出评价。
  • Scalability，可扩展性
    对于 (N-User, M-Item) 的推荐问题，传统 NN-CF 的算法复杂度是 O(N2M)，计算量很大。而Expert-CF方法可以大幅度降低计算成本。比如论文里的数据，169 experts vs. 500, 000 potential neighbors (Netflix database)。
  • Privacy，用户隐私
    基于Expert-CF方法，可以把一小撮专家打分数据下载到手机上，进行本地计算，然后得到推荐结果，而避免把过多的数据都存储在应用服务商的服务器上。
• 在大部分的场合，我们需要的并不是与自己相似的用户的推荐，而是与自己相似的专家的推荐。无论是看书、看电影、买手机、买笔记本，那批「行内人物」的观点往往是左右我们决定的主要因素。这个结论在个性化要求相对比较低的中国显得更为真实。