两个故事

从前，网络的一头住着个挨踢男，另一头住着一小编。每天小编写一封垃圾邮件给挨踢男。苦命的挨踢男日日分析邮件设计过滤器来过滤垃圾邮件。但聪明的小编每天检查邮件有没有被挨踢男收到，不断增加更多的甜言蜜语来忽悠挨踢男。较量一直进行下去，挨踢男是否能摆脱小编的骚扰呢？

这个故事都属于博弈论里的重复游戏（repeated game），它是对在线学习（online learning）最贴切的刻画：数据不断前来，我们需根据当前所能得到的来调整自己的最优策略。

熟悉机器学习的稳拿可能注意到了在线学习与在机器学习（统计学习）里所讨论的（离线）学习的区别。前者认为数据的分布是可以任意的，甚至是为了破坏我们的策略而精心设计的，而后者则通常假定数据是服从独立同分布。这两种不同的假设带来不一样的设计理念和理论模型。

统计学习考虑算法所求得到的模型与真实模型的差距。数据由真实模型产生，如果能有无限数据、并在包含有真实模型的空间里求解，我们大概率能求得真实模型。但实际上我们只有有限数据，且只能考虑某类模型，因此很可能我们得不到真实解。所以，好的算法是能够用不多的数据来得到一个效果不错的模型。

在线学习的一个主要限制是当前只能看到当前的和过去的数据，未来是未知，有可能完全颠覆现在的认知。因此，对在线学习而言，它追求的是知道所有数据时所能设计的最优策略。同这个最优策略的差异称之为后悔（regret）：后悔没能一开始就选对最优策略。我们的希望是，时间一久，数据一多，这个差异就会变得很小。因为不对数据做任何假设，最优策略是否完美我们不关心（例如回答正确所有问题）。我们追求的是，没有后悔（no-regret）。

如果与统计学习一样对数据做独立同分布假设，那么在线学习里的最优策略就是在得知所有数据的离线学习所能得到最优解。因此在线学习可以看成是一种优化方法：随着对数据的不断访问来逐步逼近这个离线最优解。

很早以前优化界都在追求收敛很快的优化算法，例如牛顿迭代法。而最近learning的人却发现，好的优化算法很可能是坏的learning算法。这类算法虽然迭代一些次就能算出一个精度很高的解，但每一步都很贵，而且数据一大根本算不动。而向来被优化界抛弃的在线学习、随机优化算法（例如stochastic gradient descent），虽然收敛不快，不过迭代代价很低，更考虑到learning算法的解的精度要求不高，所以在实际应用中这些方法通常比传统的优化算法快很多，而且可以处理非常大的数据。

随便看看这些年ICML，NIPS，JMLR上online, stochastic关键字文章的数量就知道这类算法的大红大紫了。一个通常的规律是learning界火过的topic在computer vision，data mining等偏应用的方向上会接着火几年，所以肯定CVPR, ICCV, KDD之类会议上还会有茫茫多这类paper。因为最近一直在做这个topic，所以想乘自己知识还新，就自己的理解来谈谈它。希望能用通俗的语言为大家介绍这个topic，为国内learning界做做贡献。

当然，相对于老地主online learning，stochastic绝对是新贵。我会接下来谈这类算法，以及他们动辄数页的convergence rate的证明。我的另外一个topic是大规模矩阵的低秩近似，也算大规模机器里面的一个重要问题，我想有时间也来浅出一下。

下面是有公式的正文。

准确点的定义

我们把挨踢男都称之为learner，并从learner的角度来看问题。在t 时刻，learner收到问题x_t ，这可以是一封邮件，或者一个样本。learner然后从策略集\mathcal{H} 中选择一个策略h_t ，例如一个过滤器规则，或是一个线性分类器，并且对问题做出判断h_t(x_t) 。learner然后收到正确答案y_t 。

用损失函数\ell(h_t(x_t),y_t) 来衡量learner在t 时刻做出不正确判断时所遭受的损失，例如最常用的平方误差损失是(h_t(x_t)-y_t)^2 。为了方便起见，简记为\ell_t(h_t) 。那么在前T 轮learner遭受的总损失就是\sum_{t=1}^T\ell_t(h_t) 。记得我们说过用regret来衡量learner对一开始没能采用最优策略的后悔，记为R(T) ，有

\displaystyle R(T)=\sum_{t=1}^T\ell_t(h_t)-\min_{h\in\mathcal{H}}\sum_{t=1}^T\ell_t(h).

learner的目标就是每次挑不错的h_t 来使得R(T) 最小。一个自然的问题是，R(T) 可能小于0吗？好吧，是可以的。毕竟最优策略是要固定h ，而如果我们每次都能选很好的h_t 来适应问题(x_t,y_t) ，可能总损失会更小。但这非常难。因为我们是要定好策略h_t ，才能知道正确答案y_t 。如果这个问题和以前的很不一样，答案也匪夷所思，那么猜对它而且一直都猜对的概率很小。而对于最优策略来说，它能事先知道所有问题和答案，所以它选择的最优策略的总损失较小的可能性更大。所以，我们一般只是关心平均regretR(T)/T 是不是随着T 变大而变小。我们称一个online算法是不是no-regret，或者说online learnable的，意味着

\displaystyle \lim_{T\rightarrow\infty}\frac{R(T)}{T}\rightarrow 0.

这个定义不是很准确，因为问题x_t 是随机给的，所以这里我们要考虑最坏情况（小编写最狠的邮件）。为了符号的简单，就免去精确的数学定义了。（事实上，除非是统计人写的文章，优化或者机器学习的文章很多采用这种简单的写法）。

听专家的话

no-regret是不是很难达到呢？事实证明很多简单的算法都是no-regret。举个最经典的例子，假设我们有m 个专家，他们在每轮问题都会给出的答案。简单起见假设答案就两种，0和1。平方损失在这里就是0-1损失函数，答案正确损失为0，否则为1.

先考虑最简单的情况：假设至少有一个完美专家，她永远给出正确的答案。那么什么才是learner的好策略呢？最简单的很work：看多数专家怎么说罗。learner在时刻t 先挑出前t-1 轮一直是给正确答案的专家们，然后采用他们中多数人给出的那个答案。

此方法被称做Halving Algorithm。记C_t 是前t-1 轮一直是给正确答案的专家们的集合，|C_t| 是这些专家的个数。如果learner在时刻t 给出了错误的答案，那么意味着C_t 中大部分专家都给了错误答案，所以下一时刻learner参考的专家就会少一半，既|C_{t+1}|\le |C_t|/2 。因为完美专家的存在，所以|C_t| 不可能无限变小使得小于1，所以learner不能无限犯错。事实上，|C_t| 至多有\log_2(m) 次变小机会，所以learner最多有\log_2(m) 的损失。另一方面，最优策略当然是一直选中一位完美专家，总损失为0，所以regret的上界是个常数

\displaystyle R(T)\le \log_2(m).

现在考虑并没有传说中的完美专家存在的情况。这时维护C_t 的做法就不行了，我们使用一个稍复杂些的策略。记第i 个专家为e^i ，对其维护一个信任度w^i\in[0,1] ，且使得满足\sum_{i=1}^m w^i=1 。在t 时刻learner以w^i 的概率挑选专家e^i ，并用她的答案来做作为t 时刻的答案。

关键是在于如何调整信任度。直观上来说，对于在某一轮预测不正确的专家，我们需降低对她们的信任度，而对预测正确的，我们则可以更加的相信她们。一种常见的调整策略是基于指数的。我们先维护一个没有归一化（和不为1）的信任度u 。一开始大家都为1，u_0^i=1 . 在t 时刻的一开始，我们根据i 专家在上一轮的损失，记为\ell_{t-1}(e^i) ，来做如下调整：

\displaystyle u_{t}^i=u_{t-1}^i\exp(-\eta\ell_{t-1}(e^i)),

这里\eta 是学习率，越大则每次的调整幅度越大。然后再将u_t 归一化来得到我们要的分布：w_t^i=u_t^i/\sum_i u_t^i 。此算法被称之为Exponential Weights或者Weighted Majority。

基于指数的调整的好处在于快速的收敛率（它是强凸的），以及分析的简单性。我们有如下结论：如果选择学习率\eta=\sqrt{8\ln m/T} ，那么

\displaystyle R(T)\le \sqrt{\frac{T\ln m}{2}}.

证明先分析\sum_i u^i_{t}/\sum_i u^i_{t-1} ，其上界是关于最优策略的损失，下界是关于learner的损失，移项就得regret的上界（online/stochastic算法的收敛性分析大都走这种形似）。具体的证明这里略过，后面后补上文献。

一个值得讨论的问题是，设定最优学习率\eta 需要知道数据的总个数T ，而在实际的应用中一般不能知道样本到底会有多少。所以如果设定work的参数很trick。在以后的算法中还会遇到这类需要上帝之手设定的参数，而如何使得算法对这类控制速率的参数不敏感，或者有意的调整参数来控制算法的灵敏度，都是当前研究的热点。这是后话了。

另外一个值得注意的是，同前面存在完美专家的情况相比，regret的上界由\log_2 m 增到了\sqrt{T\ln m/2} 。这两者在实际的应用中有着很大差别。例如我们的目标是要使得平均regret达到某个数值以下，假设前一种方法取1,000个样本（迭代1,000次）就能到了，那么后一种算法就可能需要1,000,000个样本和迭代。这样，在时间或样本的要求上，前者明显优于后者。类似的区别在后面还会更多的遇到，这类算法的一个主要研究热点就是如何降低regret，提高收敛速度。

这次谈的都是online的经典算法。下回我们介绍convex online optimization，这与机器学习更相关。