Bengxy
Little steps lead to great distances.
Learning with Biased Feedback - 算法、偏差、马太与发现性
2019-08-20 Leave a comment

漫谈个性化场景下算法带来的Bias和马太效应。

在个性化算法大行其道的今天,人们在主流App上所接触的信息背后总有一套个性化算法在运作。个性化算法从海量的数据中,找到我们感兴趣的新闻、合适的商品、喜欢的音乐视频等。

从用户的隐式反馈(用户量、点击率、存留、回访)等指标上看,算法的效果振奋人心。毫无疑问的是,算法提升了人们获取信息的效率,我们不需要在一叠报纸中找自己关注的热点事件,也不需要在商场跑断腿。有了算法的帮助,合适的东西总是出现在App的第一坑位。

这是一件细思极恐的事情,算法知道我们的喜好,并决定了我们所见的内容。以至于许多算法”外行“提出了这样的问题[1]"Will AI Takeover Human?"

短期内我们不用担心美剧《West World》里AI起义推翻人类的事情,毕竟目前的Artificial Stupidity[2](人工愚蠢)距离那样的技术水平还太过遥远:D。不过我们或许应该担心:Will AI decide Human Mind?

漫谈

目前在线生效的个性化引擎,都遵循这样的范式:

image-20190816173737874

在这里,用户的行为与算法的迭代是一个闭环。用户每天在App上产生丰富的行为日志,算法从这些行为日志里学习用户的偏好、挖掘有价值的内容。当用户再次发起请求时,算法就会根据用户的行为历史,把个性化的、用户偏好的结果反馈给用户。用户再次浏览点击这些,生成更多日志,供算法再次优化。

这个迭代优化的过程乍看并没有什么不妥,算法可以及时获取用户的偏好,用户也可以及时得到反馈。但细想下来,就有问题了。

Problem 1: Learn From Existing Data

首先,模型只能从已有的数据集获取信息,所有的信息依赖于热度和协同,即经典的Popularity和Similarity问题[3]。这种统计学上的算法缺乏对未知数据的探索。而类似MAB或Reinforcement Learning的探索过程,要么还是依赖于现有数据尝试最Popular的节点或根据相似度寻找Similar节点从而保证精度,要么完全试错而带来较大的损失。

完全试错对于App来说试错的代价有多大?我们假设用户的一次完整的浏览约$N$个Item,平均的CTR为$\gamma$,每次点击平均可以为商家带来盈利$r$。那么用户一次浏览带来的利润$y$是:

$$ y = N \gamma r $$

而如果引入类似Reinforcement Learning的Exploration机制,仅对其中一个坑位的数据进行探索,假设探索商品的CTR为$\epsilon$,那么探索后的利润$\hat{y}$是:

$$\hat{y} = (N-1) \gamma r + \epsilon r $$

计算利润百分比$p$:

$$ p = \frac {\hat{y}}{y} = \frac{(N-1) \gamma + \epsilon }{N \gamma} $$

绝大多数真实情况下,这里探索的$\epsilon$ 和探索能力呈反比,对于独立性很强的探索,收益会很小。因此,公式可以近似于$p = \frac{N-1}{N}$,即:丢失了一个展示坑位。对于用户浏览坑位多的场景,$N$很大,那么这样的损失不明显,但如果N很小,比如$N=10$,意味着你将损失10%的收益。

Problem 2: Biased Feedback

对于上述范式的个性化引擎,前后两次模型的训练并不是独立的。这是一个随机过程问题,可以简化为下图的马尔科夫链。

image-20190820153002981

t-2时刻的模型,早早就把item X安排在了用户首页,当明天(t-1)用户到访,item X将出现在显眼的黄金坑位。毫无疑问,带着需求而来的用户大概率会点击,这样,一个正样本就产生了。它将回流到日志体系,用于t-1的模型训练。在这时,一个"优秀"的模型将感知到item X有很高的CTR,从而进一步将它用于第二天的展示。

在用户体验上,这表现为微博明星的热搜经久不衰,淘宝不小心点了东西就是满屏推荐,以及抖音视频里小姐姐的各种轰炸。

从模型上讲,上一次部署的模型决定了用户行为日志,进而决定本次训练的模型。 而从用户方面讲,这意味着算法是上帝,他决定了用户能看什么,能做什么。

探讨

有一些算法尝试消除这些bias,比如2017年获奖论文《Unbiased learning-to-rank with biased feedback》[4]。作者希望利用Multi-Armed-Bandit领域的Inverse Propensity Scoring来替换原先的指标做Evaluation。不过仅做这么多还不够,作者尝试对item做更多探索,不过如上文的Problem 1所述,以均匀分布的力度探索会带来极大的损失,因此,作者还用了一个模型单独对Position建模,并尝试用交换位置的方式,提升了上问Problem 1中定义的$\epsilon$值。

这是一个顺其自然的思路,既然展示的Position对效果有很大的影响,那我们一方面去学习Position对CTR的影响,另一方面把所有item放到同一个Position比较,或在online系统中,把近邻位置的做交换后对比效果。

这个解法在离线实验或线上都带来了显著提升,只是这样的解法似乎还是无法完全解决探索问题。Problem 1:Learn From Existing Data 或许在目前监督学习的体系下是无解的,期待一些强化学习的或迁移的策略给这个问题更多启示。

有趣的历史

2012年的Nature的那篇大作《Popularity versus similarity in growing networks》[4]开篇是这样的:

The principle that ‘popularity is attractive’ underlies preferential attachment, which is a common explanation…Here we show that popularity is just one dimension of attractiveness; another dimension is similarity.

Ops… 原来2012年以前人们普遍相信用Popularity进行偏好预估的原则(比如网页点击量、商品销量)。而这篇文章发现,原来基于Similarity也可以做Attractiveness预估,从而让更多长尾数据体现出价值。

如今我们对于Similarity的存在已经习以为常。上个时代,人们追逐热点,而这个时代,个性化成为代名词,那么下一个时代是什么?

也许发现性惊喜性是不错的努力方向,而这需要一个支点:算法对于更长尾的,甚至未有交互的数据,能否有一个框架能够容得下呢?

image-20190820163134008


  1. AI Takeover | 人工智能叛变 | 科幻中的AI产生自觉

  2. AI Stupidity | 人工愚蠢

  3. Papadopoulos, Fragkiskos, et al. “Popularity versus similarity in growing networks.” Nature 489.7417 (2012): 537.

  4. Joachims, Thorsten, Adith Swaminathan, and Tobias Schnabel. “Unbiased learning-to-rank with biased feedback.” Proceedings of the Tenth ACM International Conference on Web Search and Data Mining. ACM, 2017.

本文作者:Bengxy

本文采用署名-非商业性使用 4.0 国际 (CC BY-NC 4.0)协议

本文链接:http://blog.bengxy.com/posts/c6b93eea/

Machine Learning Rank 思考 Recommendation