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)\):
- 使用\(w_t\)和\(\theta\)进行预测: \(y^{'}=sgn(w_t^Tx_i - \theta)\)
- 如果\(y_i=+1\)而\(y^{'}=-1\)，则:
- 对于\(w_t\)中所有\(x_i\)不为零的权重进行更新: \(w_t=2w_t\)
- 如果\(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\),则最终我们能得到:
整体的Mistake Bound
所以整体的犯错次数是:
也就是说，Winnow算法的Mistake Bound是\(O(k\log n)\).
参考资料
更新日志
- 2016年10月12日完成初稿并发布