每周论文25

本周论文:

  1. Easy Samples First: Self-paced Reranking for Zero-Example Multimedia Search
  2. Self-Paced Learning with Diversity
  3. Self-paced dictionary learning for image classification
  4. Self-Paced Learning for Matrix Factorization
  5. Self-Paced Boost Learning for Classification

将self-paced learning用于reranking任务中。并且将self-paced learning更一般化,也即将原先的{0,1} weight扩展到实数域。

具体而言,原先的self-paced learning:

其中 $v\in\{0,1 \}$。后项的正则项为 $f(\mathbf{v} ; k)=-\frac{1}{k}|\mathbf{v}|_{1}=-\frac{1}{k} \sum_{i=1}^{n} v_{i}$

得出的解为:

而现在:
①线性,也即与loss是线性相关的:

得出的解为:

②log关系

解为:

③soft与hard的混合

解为:

也即,loss太小置为1,太大置为0.中间则是实数域。


[Self-Paced Learning with Diversity]

提出在self-paced learning中,不仅仅要选择简单的,还要增加diversity这一指标,使得模型不会overfitting到某个pattern上,同时diverse sample能够帮助模型学到更为comprehensive的知识。

由于self-paced learning没有先验知识,一开始接收到的某领域的sample,之后会倾向于一直选择该领域的sample,因为之前获取到该领域的sample,使得该领域的sample的loss相较其他领域的loss更低。这样就容易overfit到某个特定的pattern。为了解决这一问题,需要显式将diversity作为objective。

基于这一思想,有:
假设训练数据$\mathbf{X}=\left(\mathbf{x}_{1}, \cdots, \mathbf{x}_{n}\right) \in \mathbb{R}^{m \times n}$,分成b个group $\mathbf{X}^{(1)}, \cdots, \mathbf{X}^{(b)}$。weight vector为$\mathbf{v}=\left[\mathbf{v}^{(1)}, \cdots, \mathbf{v}^{(b)}\right]$,其中$\mathbf{v}^{(j)}=\left(v_{1}^{(j)}, \cdots, v_{n_{j}}^{(j)}\right)^{T} \in[0,1]^{n_{j}}$

因此objective function为:

其中新的regularization为$-|\mathbf{v}|_{2,1}=-\sum_{j=1}^{b}\left|\mathbf{v}^{(j)}\right|_{2}$,该regularization能够使模型尽量去选择不同group的sample。

当每个group只有一个sample时,公式退化为:

因此最终的算法:

思考:从diversity的角度确实很有道理,如果不是这篇文章我想不到diversity。作者对问题的认识很到位。


[Self-paced dictionary learning for image classification]

将self-paced learning用于dictionary learning(对该领域不了解)。

另一贡献是提出新的阈值更新公式:

保证第一轮有超过一半的example认定为easy。


[Self-Paced Learning for Matrix Factorization]

将self-paced learning用于矩阵分解,同时将hard weight改成soft weight。


[Self-Paced Boost Learning for Classification]

提出将boost和self-paced的思想结合在一起的算法。

Motivation

在监督学习中,有两个重要的原则:effectiveness和robustness。effectiveness专注于让模型分对,提高accuracy;而robustness则是减少noise或者confusing example的影响。
boosting算法则专注于effectiveness,因为渐进地专注于分错的example。但这样就容易使得模型缺少鲁棒性/泛化性。
self-paced learning则是从简单到难,这样可以通过稳步提高模型能力之后减少confusing/noise example对模型的影响,也即一开始就能够学习简单的pattern,而不会受到confusing/noise example所有的复杂pattern的影响。

boosting与self-paced有共通之处以及互补之处:
二者都是一个渐进的过程,从weak state到strong state。
boosting更考虑effectiveness,而SPL则更考虑robustness;boosting对不充分学习的样本施加负面抑制(不大懂意思,应该是说算法强调不充分学习的样本),而SPL正面鼓励简单易学的样本。boosting更专注于class之间的margin,尝试去拟合each sample,通过动态选择具有不同模式的简单样本;SPL更关注类内变化。
因此,boosting倾向于反映local的pattern,更加对noise敏感,而SPL则更加平滑,具有更强的鲁棒性。

将二者结合起来:positive encouragement (on reliable samples) and negative suppression (on misclassified samples)

方法

问题定义:训练数据$\left\{\left(x_{i}, y_{i}\right)\right\}_{i=1}^{n}$,其中$x_{i} \in \mathbb{R}^{d}$,$y_{i} \in\{1,2, \ldots, C\}$。

要学习一个映射$\tilde{y}(x)=\underset{r \in\{1, \ldots, C\}}{\operatorname{argmax}} F_{r}(x ; \Theta)$。而多分类的目标/loss function为:

$F$决定effectiveness;而$L$决定robustness

在boosting中:

其中$\left\{h_{j}(\cdot) \in \mathcal{H}\right\}_{j=1}^{k}$,$h_{j}(\cdot) : \mathbb{R}^{d} \rightarrow\{0,1\}$是weak classifier。$W$是分配给每个classifier的权重。

在boosting中加入SPL的思想,也即引导模型先学简单的再学难的:

其中$\left[H_{i j}\right]=\left[h_{j}\left(x_{i}\right)\right]$,$W=\left[w_{1}, \cdots, w_{C}\right] \in \mathbb{R}^{k \times C}$

将$L$具体化为logistics函数,$R(W)$是$l_{2,1} \text{-norm}$。则:

采用column generation method来解决上述公式(这段看不懂咋算出来的):

the future weak learners will put emphasis on samples that are both insufficiently learned currently and easily learned previously

也即是boosting与SPL的结合。

思考

boosting由于只能通过分对分错来给权重而不是根据loss,是粗粒度的,强调要解决难的;而SPL则是强调先学简单的,再解决难的不迟。二者巧妙互补。