深度学习到底是「实验科学」还是「理论科学」？能否称为「算法」？ 第1页

举一个比较general的machine learning，而不是deep learning的例子：

早在1933年一篇叫做On the likelihood that one unknown probability exceeds another in view of the evidence of two samples的paper中 William Thompson 介绍里一种heuristic的方法叫做probability matching的方法来做sampling。有点类似于你有k个广告，每个广告有一个根据历史数据所学到的click through rate(CTR)的distribution ，然后你想决定下一个request来的时候我display什么广告。于是作者拍脑袋一想，不如我们根据每个广告的distribution中sample出一个数字，然后按照生成数字最高的那个广告来推荐给customer。一个很明显的好处是，刚开始数据量小的时候，对每个广告的distribution估计的variance比较高，那每个广告都有较大机会被recommend (exploration)。等着有越来越大的evidence表面某个广告的CTR比较高的时候，variance变低了，这样就更可能sample出empirical performance最好的那个广告 (exploitation)。但在那个阶段的实验还非常少 (毕竟还处于非常早期，应用主要还是在data很有限的clinical trial之类的)，然后也没有任何理论支持这个的reward比别的方法更高。后来渐渐这个方法以作者的名字命名成了Thompson Sampling(TS)。

然后直到2011年， Chapelle & Li 的paper：An Empirical Evaluation of Thompson Sampling又把TS带入了大家的视野。由于这个时候计算广告已经很广泛被应用了。Chapelle & Li 在雅虎的news article推荐中实验TS之后发现performance比别的bandit的方法像UCB整体表现更佳。而实际应用中往往reward都是以delayed batch的模式得到的，TS这种按照prob来display一个广告的方法也更容易被应用，从而TS越来越多的被用在推荐中。但是并没有人给它提供理论的support。

直到2012和2013年，在Microsoft Research India做postdoc/researcher的Prof. Shipra Agrawal在两篇非常著名的bandit的paper：Thompson Sampling for Contextual Bandits with Linear Payoffs, Analysis of Thompson Sampling for the Multi-armed Bandit Problem给出了TS在contextual bandit和non-contextual bandit中证明了它的regret比较低 (log(T) regret for non-contextual, sqrt(T) for contextual linear bandit)才真正的彻底解决这个问题。

所以你退回到2011年问TS的方法是实验科学还是理论科学，那必然更像是实验科学，完全是heuristic的想法，只是实验表现很好。就像今天的deep learning一样，很多的算法并不知道为啥表现好 (当然会有一些intuition像self attention就非常的intuitive，但并没有理论支持)。但相信在未来，一定会有researcher不断的完善理论，从而使得它变的更像是理论科学。毕竟在1933年的某个月黑风高的夜晚，当Prof. Thompson拍大腿提出这个方法的时候，绝对想不到在80年之后才有人给出了理论证明并且在推荐领域被广泛的应用着。

顺便做个广告：Prof. Agrawal (Prof. @UColumbia IEOR)现在在amazon做Amazon Scholar经常会有合作，然后Li也最近离开Google加入Amazon，有兴趣合作的欢迎加入Amazon。