监督学习越来越准，我为什么要写bandit问题

监督学习的典型场景

在涉猎bandit问题之前，监督学习是很好概括的：

步骤 1 刻画原始需求： 给用户推荐一道菜，结果只有两个：用户喜欢或者不喜欢

步骤 2 映射成监督学习（二分类）问题：给定特征向量x=(菜的类型：荤菜/素菜，顾客类型：性别、年龄性别，就餐时间：早/午/晚），预测顾客是否会接受这道菜，y=0或1

步骤 3 用历史数据训练模型：选择常用的监督模型Logistic Regression/GBDT/神经网络，从大量的历史数据(x, y)中学习模型的参数，给定x，预测y越准越好

步骤 4 部署上线做A/B Test：观测线上效果。

准确率并不是监督学习的全部

然而，上面的抽象并不是完整的，我们先从一个例子开始：

(千篇一律的新闻)现在的新闻客户端都使用了机器学习进行智能排序，你有没有跟我一样的体验：

某类型的新闻，你点击的越多，下次登录时就会看到的越多

看到的越多，点的机会也就越多

最后满眼的新闻都是千篇一律

借着这个例子，我们说说把现实问题映射到监督学习的过程中存在的坑：

历史数据的收集直接受到了算法影响，是有偏向性的：算法推荐了一个新闻，用户才有机会给出反馈，系统才会收集到反馈。但是还有千千万万的新闻是没推荐出来的，用户不知道它们好不好，系统也没机会收集那些新闻的反馈

正反馈是很容易获得的，负反馈却需要自己去猜：算法推荐了k个新闻，用户只点击其中的一个，这并不100%意味着是对剩下的新闻的否定：(1) 这个新闻没有被用户注意到，(2) 这个新闻用户也感兴趣喜欢，只是时间有限，这次没点

结论：既然历史数据是受算法影响的，用户又只提供了正反馈，那么根据历史数据训练就会不断强化自己去推荐已经推荐过的东西，使得模型陷入一个局部最优，潜在的好的东西迟迟得不到推荐。

为什么监督学习还能work

可是这么多年都是这么训练的，为什么也没见到大的问题？

特征工程时考虑到了泛化能力：新闻到底属于财经类还是娱乐类、用户的年龄、性别是什么，这些特征都是普遍适用的。一个用户、一个新闻，即使没有推荐过，我们也能依据它们的特征判断的八九不离十。但是，为了提高准确率，我们也会牺牲泛化能力，加入ID类特征，包括用户ID和物品ID。

冷启动问题得到了足够的重视，弥补了特征泛化能力不足的问题：一个新闻刚出现时，我们会有意识的采取手段确保他们能得到一定推荐。比如去看看新闻和用户已经点击过的新闻的相似性（基于内容去找关联）。

Bandit问题的核心

Bandit的研究总是需要回答2个核心问题：

如何预测点击率 p

Contextual Bandits使用了线性模型

当然也可以使用非线性模型，比如决策树、神经网络

如何衡量 p 的不确定性，按照对物品进行排序

UCB算法是Frequentist学派的代表，用置信区间来刻画

Thompson Sampling是Bayesian学派的代表，用概率分布来刻画

抓住了这个核心，我们看看之前的问题

冷启动有多冷：一条新闻只被推荐过几次，它的不确定性是很大的，表示这个新闻还很冷，按照对物品进行排序是很有可能把新闻推荐出来的

算法和用户反馈的关系：用户只会点击算法选中的新闻，

利用已有历史信息(Exploitation)：推荐高质量的新闻，确保用户当前的体验，也就是 p 值较高的那些新闻

勇于探索 (Exploration)：有些新闻才出来，或者用户以前没点击过，不确定性高，但如果推荐出来用户也有可能会喜欢，也就是高的那些新闻

如何平衡Exploitation和Exploration：我们是按照对物品进行排序的，是一个区间，如何在这个区间取值反映了我们对Exploitation v.s. Exploration的偏好

工业界中的实践

微软在几个月前launch了Decision Service：

Github开源实现：Microsoft/mwt-ds

这直接启发了我写“智能决策”系列，后续争取写一篇系统实现的文章来看看Bandit的研究怎么落地：）