Winnow算法

Winnow和Perceptron的Mistake Bound算法很相似，都是一种Online Learning的算法，主要区别在于其更新方式的不同。

Winnow算法的基本设定如下:

Input: A sequence of training examples (x1,y1),(x2,y2),⋯, 其中xi∈Rn,yi∈{−1,1}

1. 初始化: w0=1∈Rn, θ=n
2. 对于每一个训练样本(xi,yi):
   1. 使用wt和θ进行预测: y′=sgn(wTtxi−θ)
   2. 如果yi=+1而y′=−1，则:
      • 对于wt中所有xi不为零的权重进行更新: wt=2wt
   3. 如果yi=−1而y′=+1，则:
      • 对于wt中所有xi不为零的权重进行更新: wt=wt2
3. 返回最终的权重

我们可以看到，Winnow算法的框架和Perceptron的Mistake Bound是非常接近的，只不过Perceptron是加法式更新，而Winnow是乘法式更新。

适用问题

从上述的算法流程中，我们可以看到，Winnow算法每次更新时，只更新部分的权重，提高那些有正影响的权重，而降低那些有负影响的权重。 因此，对于那些维度(n)很大，但实际真正有影响力的维度(k)却很小(k≪n)的问题，Winnow应该是一个更好的选择。 在这里，我们能给出Winnow算法的Mistake Bound: Winnow算法的Mistake Bound是k(1+logn)

Winnow的Mistake Bound

基本设定:

• 对任意的训练数据(xi,yi):我们假设xi∈{0,1}n,yi∈{0,1}

在上述这个假设下，我们就来证明Winnow的Mistake Bound.

就像算法所描述的，要证明Winnow的Mistake Bound，我们需要考虑两方面的内容:

1. Winnow在正例上犯错次数的界,我们用m+表示
2. Winnow在负例上犯错次数的界,我们用m−表示

则，整体的Mistake Bound就是m−+m+.

在正例上犯错

根据Winnow的更新法则，每一次在正例上犯错，相应的权重都会提高2倍，而预测标准则是sgn(wTtx−θ). 这就说明，对于任意一个有影响力的特征来说，它最多会被提高1+logn次。 某个有影响力的特征被提高1+logn次之后，它就不会再犯错了(此时该权重已经大于θ)。

因为一共有k个具有影响力的特征，因此我们就能得到m+=k(1+logn).

在负例上犯错

在负例上的犯错次数就比较麻烦了，我们需要一些技巧。

令TWt表示在第t步时，所有权重的和，也即TWt=n∑iwti.

在正例上犯错

如果在t步时，算法在正例上犯错了，我们可以很容易得到: TWt+1<TWt+n. 因此，TW的整体的增量小于nm+.

在负例上犯错

如果在t步时，算法在负例上犯错了，我们就能得到:WTt+1<TWt−n2. 因此，TW的整体减量小于n2m−.

因为TW0=n,则最终我们能得到:

整体的Mistake Bound

所以整体的犯错次数是:

也就是说，Winnow算法的Mistake Bound是O(klogn).

参考资料

• Vivek Srikumar教授的课件
• Avrim Blum的算法笔记

更新日志

• 2016年10月12日完成初稿并发布

Share on: Twitter ❄ Facebook ❄ Email

---

---