LibRec 每周算法：parameter-free contextual bandits (SIGIR'15)

个性化推荐系统中有个两个经典问题：冷启动问题和EE问题。

• 冷启动问题，主要是用户冷启动问题，顾名思义，当面对新用户时，如何知道用户的兴趣爱好。

• EE问题，即Exploit－Explore问题，Exploit(开采)目的是要迎合用户确定的感兴趣信息，而Explore（探索）则是探索用户潜在的新兴趣，防止用户因过多的相同推荐物品而感到厌烦。

可以看出，Bootstrap和Explore是相互矛盾的，Exploit目的是提供用户明确的感兴趣信息，而Explore则可能导致推荐系统会提供用户不感兴趣的信息，但Explore可以提升长期利益，利于系统的良性发展。

一个主要的方法是通过多臂赌博机（Multi-armed Bandit）算法来解决这两个问题。多臂赌博机指的是赌徒去赌场中摇赌博机，赌场中多个外表相同的赌博机，但每个赌博机赢钱的概率不一样，赌徒不知道每个摇赌博机赢钱概率分布，问题是每次如何选择哪个摇赌博机可以做到最大化收益呢？这个问题与推荐系统非常类似：用户对不同类别的内容感兴趣程度不同，推荐系统需要推荐用户哪些内容使得推荐效果最大化。具体的关于Bandit算法可以参考博文[1]进行了解。

然而，经典的Bandit算法，例如LinUCB[2]，ε-greedy[3], Thompson sampling[4]等，一般都需要超参数来调节平衡Exploit和Explore，因此超参数的设置好坏对模型性能有重大的影响。

SIGIR’15的这篇文章通过自助抽样法（bootstrap）来解决这一问题，不需要先验或者参数来平衡Exploit和Explore。

Tang, Liang, et al. "Personalized recommendation via parameter-free contextual bandits." Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2015.

bootstrap（自助抽样法）是一种从给定训练集中有放回的均匀抽样，也就是说，每当选中一个样本，它等可能地被再次选中并被再次添加到训练集中。集成学习中一个重要的模型，bagging，就是利用bootstrap对训练集重采样，然后训练多个分类器，来降低模型预测的方差。而我们知道，模型的泛化误差是偏差、方差与噪声之和。因此bagging模型能够最终降低泛化误差，模型具有较强的鲁棒性。利用bootstrap得到样本，然后进行模型参数估计，一方面样本是从原始数据中得到，与原始数据分布相似，符合Exploit的要求，另外一方面因为是采样，与原始数据还是不完全一样，从而得到的分布不一样，这样Explore的功能也达到了。

因为离线的bootstrap需要之前的所有观测数据进行抽样，并抽样的次数与之前的所有观测数据大小相同，不适用实时的在线推荐，因此该文使用了一种在线的自助抽样法（online bootstrap）[5]。它通过泊松分布来产生一个整数作为样本抽到的次数，达到在线抽样的目的。最终的基于online bootstrap的Bandit算法如下表示：

为了保证每次试验是相互独立的，文中还在每个臂中维持了一个独立的抽样集合，大小为B。每次收到context x， 首先对每个臂从B个集中随机得到相关向量θ（line 1-4），然后摇臂得到最大的收益。最后根据收益结果，利用online bootstrap，对该臂中样本相关向量集合进行更新（line 8-15）。

总结，该文使用了在线自助抽样算法进行模型参数训练，在不需要特定超参数的前提下达到平衡Exploit和Explore的目的，论文实验中也表明该方法具有相对稳定的推荐性能，而其他bandit模型需要小心的设置先验参数才能得到较好的结果。

参考文献

[1] Bandit算法与推荐系统，http://geek.csdn.net/news/detail/195714

[2] L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual-bandit approach to personalized news article recommendation. In WWW, pages 661–670. ACM, 2010.

[3] M. Tokic. Adaptive ε-greedy exploration in reinforcement learning based on value differences. In KI 2010: Advances in Artificial Intelligence, pages 203–210. 2010.

[4] O. Chapelle and L. Li. An empirical evaluation of thompson sampling. In NIPS, pages 2249–2257, 2011. 

[5] N. C. Oza and S. Russell. Online bagging and boosting. In IEEE international conference on Systems, man and cybernetics, volume 3, pages 2340–2345, 2005.