Winnow算法

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

Winnow算法的基本设定如下:

Input: A sequence of training examples $(x_1,y_1),(x_2,y_2),\cdots$, 其中$x_i\in R^n,y_i\in \{-1,1\}$

初始化: $w_0=1\in R^n$, $\theta = n$
对于每一个训练样本$(x_i,y_i)$:
1. 使用$w_t$和$\theta$进行预测: $y^{'}=sgn(w_t^Tx_i - \theta)$
2. 如果$y_i=+1$而$y^{'}=-1$，则:
  - 对于$w_t$中所有$x_i$不为零的权重进行更新: $w_t=2w_t$
3. 如果$y_i=-1$而$y^{'}=+1$，则:
  - 对于$w_t$中所有$x_i$不为零的权重进行更新: $w_t=\frac{w_t}{2}$
返回最终的权重

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

适用问题

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

Winnow的Mistake Bound

基本设定:

对任意的训练数据$(x_i,y_i)$:我们假设$x_i\in \{0,1\}^n, y_i\in \{0,1\}$

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

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

Winnow在正例上犯错次数的界,我们用$m^{+}$表示
Winnow在负例上犯错次数的界,我们用$m^{-}$表示

则，整体的Mistake Bound就是$m^{-}+m^{+}$.

在正例上犯错

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

因为一共有$k$个具有影响力的特征，因此我们就能得到$m^{+}=k(1+\log n)$.

在负例上犯错

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

令$TW_t$表示在第$t$步时，所有权重的和，也即$TW_t=\sum\limits_{i}^n w_{ti}$.

在正例上犯错

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

在负例上犯错

如果在$t$步时，算法在负例上犯错了，我们就能得到:$WT_{t+1}<TW_t - \frac{n}{2}$. 因此，$TW$的整体减量小于$\frac{n}{2}m^{-}$.

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

$$ 0 < TW_t < n+nm^{+}-\frac{n}{2}m^{-} \Rightarrow m^{-} < 2(1+m^{+}) $$

整体的Mistake Bound

所以整体的犯错次数是:

$$ m^{+} + m^{-} < m^{+} + 2(1+m^{+}) = 3m^{+} + 2 < 3k(1+\log n) + 2 $$

也就是说，Winnow算法的Mistake Bound是$O(k\log n)$.

参考资料

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

更新日志

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

Flyaway is the owner of this blog.

So what do you think? Did I miss something? Is any part unclear? Leave your comments below

Comments

Winnow算法及其Mistake Bound