本科毕业分别快一年又半载,一声召唤,激情犹在。

12.30接到通知,12.40的校车,12.53的地铁,1.19的南京南,时间点环环相扣,一路小跑,只是为了一句说走就走的相聚。

聚于苏州,就先来说说这个城市吧。第二次来到这个城市,之前表姐陪着逛过金鸡湖,当时是夏天去的,晚风徐来,湖波荡漾,甚是醉人,于是对苏州就有了非常美好的印象。这一次,虽然停留的时间依然的短暂,但是真正体会到了那句令人向往的嘉誉–“上有天堂,下有苏杭”。有桥,有水,有人家,有繁华的高楼大厦,亦有古色古香的亭阁园林,生活在这里的人们应该会很享受吧!对了,对了,我觉着最重要的是这里还有很多特色小吃的店,比如玑哥带我们去的珍珠饭店,在一个导航都找了半天的小巷子里面(估计主要因为是三外地人吧,囧),里面的陈设也就很普通的酒家饭店那种,可是菜却都很有特色,看起来很漂亮,吃起来很酥口的松鼠桂鱼,味道类似于东北菜锅包肉的古老肉,还有一个家常豆腐之类的小菜,让我感到豆腐原来也可以这么好吃,啊,不能再说啦,口水又要下来啦,直接上个图吧~(吃到一半才才想起来,这么好吃一定要拍个照纪念一下!)

好吃的

好吃的

晚上,吃完饭去玑哥学校旁边找了个落脚的地方,在独墅湖那边,等去到那边,才真正感觉到这同样是上学,环境差距怎么能这么大!吃喝玩乐设施一应俱全,好吧,这样的安排其实一点都不好,学生还怎么能安心的学习呢!哈哈,只能这样自我欺骗的自我安慰一下吧。

第二天,为了赶时间,我们比较仓促的逛了狮子林,果然名不虚传,一个看起来不大的假山,我们愣是逛了3+遍,才成功找到正确的出口Orz,不多说了,结论:值得一游!直接上图吧

好玩的
好玩的
好玩的
好玩的
好玩的
好玩的

谈完了观感,来聊一聊人吧!应君,玑哥都是毕业分别之后的第一次再聚,老班长应君一个海南的小伙,为了媳妇选择留在北京奋斗,玑哥,辞掉工作,闭关考研,来到科大,亦是牛逼!本科四年住在门对门,一起生活与成长,已是熟络到快透了,但是一年不见,一坐下来,聊得竟没有停顿,仿佛想要知道一切关于他们这一年里发生的事情。应君在首都,想要做VR,现在在公司里也快能独挡一面,工资在一年里亦有了翻倍,但是也不得不抱怨一下这北京令人“绝望”的雾霾,还有那高的可以上天的房价,玑哥,经历了考研,看淡一切,忙碌着研一的众多课程,还在课余坚持刷Leetcode,自学机器学习,准备这明年3、4月份的实习,当然,也不忘了时刻准备着撩妹纸~有欢,有喜,一年多的时光里,大家都各自经历了很多,你一句我一言,仿佛在短短的几个小时里拥有了三段不同的经历,或许这就是别后重聚的美妙之处吧。再一次,短暂的相聚,分别又是在转瞬之间,但是,大家都在自己想要追求的目标的路上前行着,一切还是那么的值得憧憬,期待着下一次的再聚。

好基友
好基友
好基友

最后,特别鸣谢老班长的真诚召唤与玑哥的盛情款待,让这一次说走就走的相聚成为了美好的回忆。

在机器学习里面,如何避免过拟合是一个永恒的话题,缓解该问题的一个有效方法就是在损失函数后面加上一个规则化项,而对于规则化项的不同选择便会带来不同的效果,下面就对他们进行简单的对比介绍。

$L_p$范数

常见$L_p$范数规则化的表达式为:

$$||x||_p=\left (\sum_{i=1}^n|x_i|^p\right )^{\frac{1}{p}}$$

对于这些范数的表达,先给两个比较经典的图一起来感受一下:

different norms

Minkowski3

根据上面两个图,我们不难发现,当$p \leq 1$时,图形不是光滑的,在某些点是不可微的,而正是这一属性可以给解带来稀疏性,同时,我们也可以看出此时p值越小,解的稀疏性也就越大,极限情况便是$p=0$时,稀疏性达到最大,便是熟知的$L_0$范数,但是,由于此时,函数是离散的,不太好优化,所以,通常选择与其解近似的$L_1$范数来达到稀疏解的要求。当$p \geq 1$时,从图像中明显可以看出来,他们变得越来越光滑,相应的其约束的解也会变得相对平滑,也就不再具有稀疏性了,不过,通常$L_2$范数的性能会更好一点,因为毕竟解的分布范围比较的广,更加的泛化。

鉴于这些范数有着各自不同的优缺点,有学者便想着将他们组合起来,以达到更加丰富的效果。

mixed norms

对于混合范数的研究已经有很多成果了,比如比较经典的Group LassoElitist Lasso。这里先给自己挖一个大坑,后面有时间看一看这两篇文章~~~下面,我将从一个关于mixed norm的应用来切入,探究一下其奇特的效果。

文章标题

Multiple Indefinite Kernel Learning with Mixed Norm Regularization (ICML‘09)

主要内容

这篇文章主要解决的是一个关于多核学习的问题,作者没有按照通用的思路,只在核函数的维度,来考虑不同核函数组合带来的效果,而是另辟蹊径,同时在样本和核函数两个维度去考虑,这也为引入 mixed norm 埋下了伏笔。

注:
多核学习问题的通用思路为:多核核函数的线性组合,然后将这组合之后的核代入到原SVM问题
核函数线性组合:$$K(x, x’) = \sum_{m=1}^M d_m K_m(x, x’)$$
优化目标:
\begin{align}
\min_{f_m, b, \xi, d} &\quad \frac{1}{2}\sum_m |f_m|_{\mathcal{H}_m}^2 + C\sum_i\xi_i \\
s.t. &\quad y_i \sum_m f_m(x_i) + y_i b \geq 1 -\xi_i \quad \forall i \\
&\quad \xi_i \geq 0 \\
&\quad \sum_m d_m = 1, d_m \geq 0
\end{align}
(引用自Simple MKL)

本文作者直接构造的核函数组合的形式为:

$$\mathcal{F}_S = \left \{x \to \sum_{i,t=1}^{n,\tau} \alpha_{it} k_t(x_i, x): \alpha\in\mathbb{R}^{n\tau}, k_t \in \mathcal{K} \right \}$$

其中,$\mathcal K = \{ k1, k2, \cdots , k_\tau\}$表示候选核函数集合。同时,作者也将该形式作为其最终预测的判别函数,即判别函数为$sign(f(x))$, $f\in \mathcal{F}_S$.

因此,作者得到了其待优化的目标函数:
$$\min_{\alpha\in\mathbb{R}^{n\tau}}\quad \sum_{i=1}^n |1-y_ik_i^T\alpha|_+^2 + \frac{\lambda}{q} ||\alpha||_{pq;r}^q$$
这里,目标函数主要可以分两段来看,前半段为loss function,一个squared hinge loss,后半段为regularization term,即 mixed norm. 其中,mixed norm的具体形式为:
$$||\alpha||_{pq;1} = \left [\sum_{i=1}^n \left [ \sum_{t=1}^\tau |\alpha_{it}|^p\right ]^{q/p}\right ]^{1/q}$$
$$||\alpha||_{pq;2} = \left [\sum_{t=1}^\tau \left [ \sum_{i=1}^n |\alpha_{it}|^p\right ]^{q/p}\right ]^{1/q}$$
(注意,两个式子的求和顺序是不一样的!)

对于这两个式子,文章中2.3节给出了详细的分析,并给出了四个简图来说明。
difference of mixed norms
对这四幅图简单的分析:

  • 第一幅图的mixed norm参数为$p=1,q=2$,表示在核函数的维度上具有稀疏性,样本维度上不单独具有,即对于不同的样本,其对应的核函数组合可以体现出不同的稀疏性。
    $$||\alpha||_{12;1} = \left [\sum_{i=1}^n \left [ \sum_{t=1}^\tau |\alpha_{it}| \right ]^{2}\right ]^{1/2}$$

  • 第二幅图 $p=2,q=1$,表示在核函数的维度上不具有单独的稀疏性,而是通过样本维度的稀疏性来传递到核函数组合整体上的稀疏,即对于样本维度而言,通过1范数来达到了稀疏性,当某个样本被选择稀疏表达,那么与该样本相关的所有核函数组合便都具有了稀疏性。
    $$||\alpha||_{21;1} = \left [\sum_{i=1}^n \left [ \sum_{t=1}^\tau |\alpha_{it}|^2\right ]^{1/2}\right ]^{1}$$

  • 第三幅图 $p=1,q=2$, 与第一幅图类似,表示在样本维度具有稀疏性,核函数维度不具有,即对于不同的核函数,其对应的所有涉及到的样本可以体现出不同的稀疏性(核内稀疏不同)。
    $$||\alpha||_{12;2} = \left [\sum_{t=1}^\tau \left [ \sum_{i=1}^n |\alpha_{it}| \right ]^{2}\right ]^{1/2}$$

  • 第四幅图 $p=2,q=1$,与第二幅图类似,表示在样本维度上不具有单独的稀疏性,而是通过核函数维度的稀疏性来传递到样本维度的稀疏,即对于核函数组合的维度而言,通过1范数来达到了稀疏性,当某一核函数被选择稀疏表达,那么与该核函数相关的所有样本的$\alpha$就都变得稀疏了。
    $$||\alpha||_{21;2} = \left [\sum_{t=1}^\tau \left [ \sum_{i=1}^n |\alpha_{it}|^2\right ]^{1/2}\right ]^{1}$$

文章中表明,$||\cdot||_{12;r}$与Elitist Lasso相关,$||\cdot||_{21;r}$与Group Lasso相关。

对于这个优化问题的求解,作者运用了proximal algotithm来求解,由于与本主题无关,详细的求解方法可以参考论文。

最后,作者在$Titanic$数据集上进行了实验,并给出了与上面图类似的关于稀疏性的实验结果图:
experiments on titanic dataset
这里对实验结果的分析就不再赘述了,文章中给出了详细的分析。

小评

首先,这篇paper的作者在给出了一种比较巧妙的方法来解决多核学习的问题,没有按照常规思路从原始的SVM问题出发,通过对偶化来引入核函数,而是直接以核函数的组合来作为评价函数,同时,从样本和核函数组合两个维度进行了考虑,这也为后面引入混合函数做好了准备。总之,想法还是挺新颖的!不过,也有一些问题吧,其一,这个题目是Multiple Indefinite Kernel Learning,但是全篇只有在conclusion部分提到了Indefinite Kernel的问题,所以,给人一种全篇都在跑题的感觉Orz~,虽然,核函数是不定的时候,该模型也能work,但是好歹在实验的时候搞个不定的核吧!(仅个人看法~)其二,对于实验而言,发现Titanic数据集上线性核居然比高斯核效果要好,回头实验一把看看!还有就是多核的意义应该主要体现在了对于核函数的自动选择,而不再需要人为的靠经验选择了,与单核相比,实验精度并不一定会有提升。所以,对于多核学习的研究,应该重点放在对模型的改进,或是新思路的探讨吧,最后只需要与多核方法进行比较就可以了。

references

  1. Multiple Indefinite Kernel Learning with Mixed Norm Regularization
  2. Simple MKL

Backgrounds

首先,直入主题,SVM原问题模型:

\begin{align}
\min_{w, b} \quad & \frac{1}{2} |w|^2 + C\sum_{i=1}^n\eta_i\\
s.t. \quad & y_i (w^T \phi(x_i)+b) \geq 1-\eta_i,\\
& \eta_i\geq 0, \quad i=1,2,…,n
\end{align}

接着,我们对原模型求Lagrange对偶问题,并对$w,b$分别求偏导,置为0,得到结果带到对偶问题中得到对应的对偶问题:

\begin{align}
\min_{\alpha} \quad & \frac{1}{2} \alpha^T Q \alpha - e^T \alpha \\
s.t. \quad & y\alpha = 0,\\
& 0 \leq \alpha_i\leq C, \quad i=1,2,…,n
\end{align}
其中$Q_{i,j}=y_iy_jK(x_i, x_j)$.

到这里,我们得到的问题就是一个凸二次规划问题。通常我们可以用通用的优化工具包来求解,但是当样本规模很大时,一方面核矩阵会变得非常的大(核的维度与样本个数相关),其实对于工业界而言百万级的数据量是正常的,而这对于svm来说是很可怕的,所以这也是svm在工业界用的很少的主要原因;另一方面需要求解的变量也会随之增加,求解的时效性也是一个问题。所以,这个时候就产生了很多针对SVM问题的优化方法,比如著名的SMO算法!其实,关于SMO算法,是一类方法的一种极限情况,这一类方法的主要思想是:首先,我们从问题的本身出发,对于SVM原问题与其对偶问题,通常情况下,两者的解之间是存在一个对偶间隔的,只有当两者的对偶间隔消失时,对偶问题的解才与原问题的解是等价的,而对偶间隔的消失的充要条件是对偶问题的解都满足KKT条件,所以,大家就想,我们是不是可以判断对偶问题的解是否都满足了KKT条件来间接判断我们的目标是否已最小化。于是,这一类方法就是通过不断更新部分的$\alpha$来使他们都满足KKT条件。在每一次的更新中,都是选择一部分的$\alpha$来更新,这样就能很有效的减少了核矩阵的规模(只需要选择与这些$\alpha$相关的核矩阵值就可以)。这一类方法通常被称为Decomposition Methods.

Decomposition Methods

Decompositon methods通常将需要求解的$\alpha$分解成两个部分:一个inactive部分,一个active部分(这一部分称为working set)。具体的算法流程为:

while the optimality conditions are violated

  1. select q variables for the working set B. The remaining (l-q) variables are fixed at their current value.
  2. decompose problem and solve QP-subproblem: optimize $W(\alpha)$ on B.
    terminate and return $\alpha$

根绝上面的算法流程,我们主要需要完成两个任务:

  1. 找到合理的working set
  2. 求解分解后的子问题
    下面逐个进行介绍。

分解后的子问题

对于这个问题,我们可以通过对偶问题的KKT条件来推导得到。

对偶问题的KKT条件:
\begin{align}
& g(\alpha) + (\lambda^{eq} \textbf{y} - \lambda^{lo} + \lambda^{up}) = 0 \\
\forall i \in [1,…,n]: \quad & \lambda_i^{lo}(-\alpha_i) = 0\\
\forall i \in [1,…,n]: \quad & \lambda_i^{up}(\alpha_i - C) = 0\\
& \lambda^{lo} \geq \textbf{0} \\
& \lambda^{up} \geq \textbf{0} \\
& \alpha^T\textbf{y} = 0 \\
& 0 \leq\alpha \leq C\textbf{1}
\end{align}
其中$g(\alpha)$是对偶问题目标函数关于$\alpha$的偏导数。$g(\alpha) = -\textbf{1} + Q \alpha$。

根据decomposition methods的算法,我们将$\alpha$分解为两个set:
$$\alpha =
\begin{vmatrix}
\alpha_B \\
\alpha_N
\end{vmatrix}
$$
其中,$\alpha_B$是active set,即为需要更新的set;$\alpha_N$是inactive set,即为暂时固定的set。那么对应的$\textbf{y}, Q$分解为:
$$\textbf{y}=
\begin{vmatrix}
\textbf{y}_B\\
\textbf{y}_N
\end{vmatrix}
$$
$$Q =
\begin{vmatrix}
Q_{BB} & Q_{BN} \\
Q_{NB} & Q_{NN}
\end{vmatrix}
$$
由于$Q$ 是对称的,所以这里有$Q_{BN} = Q_{NB}^T$.将上面分解的形式代入到对偶问题中得到:
\begin{align}
\min_{\alpha} \quad & - \alpha_B^T(\textbf{1} - Q_{BN} \alpha_N) + \frac{1}{2}\alpha^T_B Q_{BB} \alpha_B + \frac{1}{2}\alpha^T_N Q_{NN} \alpha_N - \alpha_N^T \textbf{1} \\
s.t. \quad & \alpha_B^Ty_B + \alpha_N^T y_N = 0 \\
& 0\leq \alpha \leq C \textbf{1}
\end{align}
这里由于$\alpha_N$是固定的,所以$\frac{1}{2}\alpha^T_N Q_{NN} \alpha_N$ 和 $\alpha_N^T \textbf{1}$都是固定的值,可以省去。所以上式可以化简为:
\begin{align}
\min_{\alpha} \quad & \frac{1}{2}\alpha^T_B Q_{BB} \alpha_B - \alpha_B^T(\textbf{e}_B - Q_{BN} \alpha_N) \\
s.t. \quad & \alpha_B^Ty_B + \alpha_N^T y_N = 0 \\
& 0 \leq (\alpha_B)_i \leq C, \quad i = 1,\cdots, q
\end{align}
此时,我们需要求解上面一个缩小版的对偶问题,来更新$\alpha_B$。这样就解决了数据量很大时不能求解的问题。

合理的working set的选择

对于working set的选择,我们的目标是希望选择一个working set使得当前的迭代能够让目标函数有尽量大的下降。Zoutendijk (1970)提出了一个一阶近似的方法。他的思想主要是找到一个下降最陡峭的可行方向集$d$,其中仅有$q$个非零元素。那个对这些非零$d$对应的点即表示该轮被选中的working set中的元素。
优化目标:
\begin{align}
\min \quad & V(d) = g(\alpha^{(t)})^T\textbf{d} \\
s.t. \quad & \textbf{y}^T\textbf{d} = 0 \\
& d_i \geq 0 \quad \forall i:\alpha_i = 0\\
& d_i\leq 0 \quad \forall i: \alpha_i = C \\
& -\textbf{1} \leq \textbf{d} \leq \textbf{1} \\
& |{d_i : d_i\neq 0}| = q
\end{align}
其中,$\alpha^{(t)}$表示第t轮的$\alpha$值。下面的前三个约束确保了下降的方向是沿着对偶问题中的等式约束进行投影的,并且遵循了active bound constraints.倒数第二个约束对d进行了规范化,确保优化问题well-posed.最后一个约束确保了这个求解的方向只能包含q个激活变量。这里需要约束$q$是一个偶数。

这一选择working set的方法最早是由Joachims(1998)提出,后来Change等人(2000)指出上面最后一个约束并不是总是满足,因此将其改成了:
$$|{d_i : d_i\neq 0}| \leq q$$
这也是SVM开源工具包 $\text{SVM}^{light}$ 的求解方案。

至此, 这里decomposition methods的两个任务就都介绍完了。当然,或许对于working set的选择,还是会感到很迷惑,不知道为什么要这么选择,下面我就依照PALAGI et al.里面的讲解思路来复述一下。

首先,对于一个满足条件的$\alpha$,我们可以表示出其对应的上下界的集合:

$$L(\alpha) = \{i:\alpha_i=0\},\quad U(\alpha) = \{i:\alpha_i=C\}$$

对于一个可行解 $\alpha^*$ ,必存在一个标量 $\lambda^*$ ,结合上面对偶问题的KKT条件,我们有:

$$
(\nabla f(\alpha^*))_i + \lambda^* y_i =
\begin{cases}
\geq 0 & \text{if} \quad i \in L(\alpha^*) \\
\leq 0 & \text{if} \quad i \in U(\alpha^*) \\
= 0 & \text{if} \quad i \notin L(\alpha^*)\cup U(\alpha^*)
\end{cases}
$$

注:
这里根绝上面对偶问题的KKT条件:
\begin{align}
& g(\alpha) + (\lambda^{eq} \textbf{y} - \lambda^{lo} + \lambda^{up}) = 0 \\
\forall i \in [1,…,n]: \quad & \lambda_i^{lo}(-\alpha_i) = 0\\
\forall i \in [1,…,n]: \quad & \lambda_i^{up}(\alpha_i - C) = 0\\
& \lambda^{lo} \geq \textbf{0} \\
& \lambda^{up} \geq \textbf{0} \\
\end{align}
所以,当$i \in L(\alpha^*)$时,有$\alpha_i=0$.所以,$\lambda^{lo}$可以是任意正值,且$\lambda_i^{up}=0$,那么我们有$g(\alpha) + \lambda^{eq} \textbf{y} = \lambda^{lo} \geq 0$,这就是上式的第一条结论。后面两个可以类似的推导得到。

根据上面结论,我们可以变换一种写法:
$$L^-(\alpha) = {i\in L(\alpha): y_i\lt 0}, \quad L^+(\alpha) = {i\in L(\alpha): y_i \gt 0}$$
$$U^-(\alpha) = {i\in U(\alpha): y_i\lt 0}, \quad U^+(\alpha) = {i\in U(\alpha): y_i \gt 0}$$

随之,我们就可以得到一个关于Optimality Conditions的定理:

$$\lambda^*\geq -\frac{(\nabla f(\alpha^*))_i}{y_i} \quad \forall i \in L^+(\alpha^*)\cup U^-(\alpha^*)$$

$$\lambda^*\leq -\frac{(\nabla f(\alpha^*))_i}{y_i} \quad \forall i \in L^-(\alpha^*)\cup U^+(\alpha^*)$$

$$\lambda^* = -\frac{(\nabla f(\alpha^*))_i}{y_i} \quad \forall i \notin L(\alpha^*)\cup U(\alpha^*)$$

对应的,我们可以将上面定理中条件定义成:
$$R(\alpha) = L^+(\alpha^*)\cup U^-(\alpha^*) \cup {i: 0 \lt \alpha_i \lt C}$$
$$S(\alpha) = L^-(\alpha^*)\cup U^+(\alpha^*) \cup {i: 0 \lt \alpha_i \lt C}$$
其中,$R(\alpha)$被称为”bottom“ 候选集,$S(\alpha)$被称为”Top“候选集。这其实也就是选择working set元素的一个指导。

根据上面的一个定理,我们可以得到另一个定理:
对于可行解$\alpha^*$,其中,$i\in R(\alpha^*), j\in S(\alpha^*)$,必然不会存在如下的形式
$$-\frac{(\nabla f(\alpha^*))_i}{y_i} \gt -\frac{(\nabla f(\alpha^*))_j}{y_j}$$

接着,对于每一对$i \in R(\alpha),j \in S(\alpha)$,方向$d$有:
$$d_i = \frac{1}{y_i}, \quad d_j = -\frac{1}{y_j}, \text{and} \quad d_l \leq 0 \quad \text{for} \quad l\neq i,j$$

另外,我们可以定义:
$$\mathcal I(\alpha) = \left \{ i: i=\arg \max_{t\in R(\alpha)} - \frac{\nabla f(\alpha)_t}{y_t} \right \}$$
$$\mathcal J(\alpha) = \left \{ j: j=\arg \max_{t\in S(\alpha)} - \frac{\nabla f(\alpha)_t}{y_t} \right \}$$

最终,我们可以得到选择working set的算法:
working set selection algorithm

后序改进的工作

对于SVM优化问题的探讨,在2000年左右是一个高峰,有点类似现在deeplearning,基于这一个想法的相关改进工作也产生了很多的论文,其中,主要基于两个方向,一个是对分解子问题的改进,另一个就是对working set选择的改进。

对于分解子问题的改进:

  1. shrinking:由于通常Support Vector是少量的,其中由于noise的因素,某些$\alpha_i$会到约束的上界$C$(这些点被称为”bounded support vectors”),假设先验的知道哪些点是BSV,那么我们就可以将这些点固定为$C$,这样,子问题就会进一步的缩小规模。Joachims 的工作
  2. 关于 $\text{SVM}^{light}$ 的工作的渐进收敛性的证明,需要基于如下的假设:
    $$\min_{I:|I|\leq q}\quad (eig_{\min}(Q_{II})) \gt 0$$
    其中,$I$是一个样本子集index,$Q_{II}$为分界后的子矩阵。这一要求能够使得目标函数是强凸的,以满足定理证明的需要。后续的researcher将其进行了改进,应用了一个proximal point的技术,在目标函数后面添加了一项:$\tau|\alpha_B - \alpha_B^k|^2$.具体的证明可以参考Palagi et al.

对于working set选择的改进

  1. 前面的方法运用的是一阶信息,Fan et al.运用了二阶的信息

References

  1. Working set selection using second order information for training support vector machines
  2. On the convergence of a modified version of SVM light algorithm
  3. Making Large-Scale SVM Learning Practical
  4. On the Convergence of the Decomposition Method for Support Vector Machines
  5. Combining DC Algorithms (DCAs) and Decomposition Techniques for the Training of Nonpositive–Semidefinite Kernels
  6. The Analysis of Decomposition Methods for Support Vector Machines

Hexo搭建博客目前已经非常流行了,各种教程在网上可以找到一大推,但是,由于不是B/S类型的,对于异地更新博文就比较麻烦了,需要预先搭建相关的环境,另外由于版本的更新还会遇到各种问题,最近就因为重装了一下系统,需要重新搭建环境也就淌过了不少的坑,现在总结下来以备忘。

新机器环境搭建

首先,就像刚开始搭建hexo一样,我们需要安装node.js和git的环境,去相关主页上下载最新的安装包傻瓜式安装即可。

  1. node.js环境安装

  2. git环境安装

这里需要注意,关于github的配置,需要将新机器的SSH公钥添加到github的[Account settings -> SSH Keys -> Add SSH Key]中去。首先,在本地为git配置用户名和邮箱

1
2
git config --global user.email "heimingx@gmail.com"
git config --global user.name "Heimingx"

接着生成密钥:

1
ssh-keygen -t rsa -C "heimingx@gmail.com"

一路回车,通常会在/.ssh/目录下生成两个文件id_rsa和id_rsa.pub,将id_rsa.pub文件中的内容复制到github的key文本框中。

最后,我们可以通过

1
ssh -T git@github.com

来验证一下。

Hexo安装和博客的clone

首先,我们在准备存放blog的文件夹内执行clone命令,将事先在github上单独存储的所有blog文件clone到本地。

注:这里我们可以在github上另建一个单独的Repository来存储博客的所有原始文件,一方面保存,另一方面方便异地更新。

1
git clone https://github.com/HeimingX/hexoblog

然后,我们需要安装hexo,在该文件夹下执行安装命令

1
npm install hexo-cli -g

接着,安装hexo的相关插件

1
npm install hexo --save

可以通过

1
hexo -v

来检查是否安装成功。

此时,通常应该就OK了,可以尝试一系列熟悉的hexo命令来进行创作博文了。

踩过的坑

在上面的操作都按部就班的完成之后,我们通常可以执行hexo的相关命令了,但是,不知道什么原因,其他的命令都可以顺利执行,本地也能起Server预览,唯独hexo deploy不行,报错:

1
2
3
4
5
6
7
bash: /dev/tty: No such device or address
error: failed to execute prompt script (exit code 1)
fatal: could not read Username for 'https://github.com': Invalid argument
FATAL Something's wrong. Maybe you can find the solution here: http://hexo.io/docs/troubleshooting.html
Error: bash: /dev/tty: No such device or address
error: failed to execute prompt script (exit code 1)
fatal: could not read Username for 'https://github.com': Invalid argument

在网上查了很多相关的资料,发现也有同学遇到过之类的问题,不过给出的答案比较多,一一试了也木有能够解决。最终,我的解决方案是修改了本地的_config.yml文件的deploy配置。

1
2
3
4
deploy:
type: git
repository: git@github.com:Heimingx/Heimingx.github.io.git
branch: master

之前的repository配置的是 https://github.com/Heimingx/Heimingx.github.io.git,具体的原因还有待探究。
这里改完之后,就可以顺畅的操作各种hexo命令了,另外发现还不需要每次都输入用户名和密码了,虽然第一反应是不安全,不过这样也方便了很多,毕竟每次输密码还是挺烦的。

references

  1. hexo 3.0 为什么无法部署到github上
  2. hexo d 的问题
  3. hexo 你的博客

在ML中,通常通过L1范数约束来达到稀疏性,而对于L1范数约束的求解常用的解法是内点法,这种算法虽然通用,但是针对这一问题有其效率的问题,最近在阅读到一篇文章专门研究在欧式空间下投影到Simplex上的做法,这里总结下来以备忘。

model 1: Euclidean Projection onto the Simplex

首先确定一下要求解的模型:
$$\min_w \frac{1}{2}|w-v|^2_2\quad s.t. \quad \sum_{i=1}^nw_i = z, w_i \geq 0$$

:这里啰嗦一句,上式中的$v$便是我们在欧式空间中待投影的向量,而$w$便是我们要求解的在simplex上与$v$对应的那个向量

下面需要对这个模型进行求解,常用套路便是对上式求Lagrange问题:
$$L(w, \zeta) = \frac{1}{2}|w-v|^2 + \theta(\sum_{i=1}^n w_i - z) - \zeta \cdot w, \theta\in\mathbb R, \zeta\in \mathbb R_+^n$$

上式对$w$求偏导得到:
$$\frac{dL}{dw_i}=w_i-v_i+\theta-\zeta_i=0$$

这里运用到Lagrange变量的性质:当$w_i\gt 0$的时候,我们一定有$\zeta_i = 0$。因此,当$w_i\gt 0$时,我们有
$$w_i = v_i - \theta + \zeta_i = v_i - \theta$$

接着,在一篇文章中(Shalev-Shwartz & Singer, 2006)给出了一个Lemma:对于原始模型,如果有$v_s\gt v_j$,那么当$w_s=0$时,就一定有$w_j=0$。

注:这里其实揭示了$w$与$v$之间的关系,而下面正是巧妙的运用了这个关系解析的求得了$w$.

根据上面的这个Lemma,我们首先定义一个$\rho$,这里$\rho$表示最终的最优解$w$中大于0的个数,因此有

$$\sum_{i=1}^n w_i = \sum_{i=1}^{\rho} w_i = \sum_{i=1}^{\rho}(v_i - \theta) = z$$

因此,$\theta = \frac{1}{\rho} (\sum_{i=1}^{\rho} v_i - z)$.那么,最终的$w$可以得到

$$w_i = \max\{v_i - \theta, 0\}$$

接下来,我们需要确定的就是上式中的$\rho$了,同样文章(Shalev-Shwartz & Singer, 2006)中给出了求$\rho$的方法:
对于给定的$v$,按照降序来重新排列得到新的序列$\mu$,那么与之对应的$\rho$有以下公式:
$$\rho(z,\mu)=\max\{j\in[n]:\mu_j - \frac{1}{j}(\sum_{r=1}^j \mu_r - z) > 0\}$$

那么到这里,这个Model的解析解就得到了。

model 2: Euclidean Projection onto the ℓ1-Ball

首先确定一下要求解的模型:
$$\min_w \frac{1}{2}|w-v|^2_2\quad s.t. \quad |w|_1 \leq z$$

在这里,我们可以明确两点:

  1. 对于给定的$v$,其对应的1范数应该满足$|v|_1\gt z$,要不然最优的$w$便是$v$本身.

  2. 基于1,最优的$w$应该在约束集的边界上取得,因此,可以将原Model中的约束换成$|w|_1 = z$

同时, 这里模型与上面的一个的差异就在于对于$w$的约束不再是大于0了,而是最终的1范数在一个区间内。但是,对于非零的$w$与其对应的$v$之间存在一个巧妙的关系就是:$w_iv_i\geq 0$.(这里就不放证明了,可以自行参考论文)

根据上面的这个关系,我们可以先认为设定$u_i = |v_i|$, 可以将原模型变换成:
$$\min_{\beta\in\mathbb R^n}|\beta-u|_2^2 \quad s.t. \quad |\beta|_1 = z \quad \text{and}\quad \beta \geq 0$$
这里的模型就与第一个一样了,然后再求得$\beta$之后,我们就可以得到与之对应的$w_i = sign(v_i)\beta_i$.

references

  1. Efficient Projections onto the ℓ1-Ball for Learning in High Dimensions(ICML’08)
  2. Efficient learning of label ranking by soft projections onto polyhedra(JMLR’06)

研究生一年级主要都在做不定核SVM的优化,在这一领域大概从2003年开始就有学者不断的提出各种idea来做这个问题,这里做个简要的总结,方便后续的研究。

首先,对于不定核的研究主要可以分为两大类:

  1. spectrum approximation
  2. directly focus on the indefinite kernel

Spectrum Approximation

这里主要有两种思想,一种是直接改变手动改变谱,另一种是学习出一个正定的核矩阵

Spectrum Transformation

谱变换,直接去手动改变不定核矩阵,转换成正定核矩阵之后再用经典的SVM来解决相应的问题。

  1. Denoise:$f(\lambda)=\max(0,\lambda)$
  2. Flip: $f(\lambda)=|\lambda|$
  3. Diffusion: $f(\lambda)=e^{\beta \lambda}$
  4. shift: $f(\lambda)=\lambda + \eta$

这些方法都是认为负特征值为noise,显然,这一方法太粗暴了,而且现实中很多应用产生的就是一个不定的相似矩阵,此时就不能简单的认为复特征值都是noise了。

Kernel Approximation

这个方法的主旨思想是:将对偶形式SVM的求解与正定核的近似放到同一个式子里面去优化。

\begin{align}
\max_{\alpha\in \mathbb R^d} \min_{K\in \mathbb R^{d \cdot d}} & \quad \alpha^T e - \frac{1}{2}\alpha^T YKY\alpha + \rho ||K-K_0||^2_F \\
s.t. & \quad \alpha^T y = 0 \\
& \quad 0\leq \alpha \leq C \\
& \quad K \geq 0
\end{align}

其中,$K_0$是已知的不定核矩阵,$K$是要求解的近似矩阵(半正定)。

这一模型是由Luss在Support vector machine classification with indefinite kernels_nips’07中提出,后续有很多学者基于此进行了优化方面的改进。比如Ye老师的Training SVM with indefintie kernels_ICML’08,以及Yihua Chen et al. 的Learning Kernels from Indefinite Similarities.其中,后者是从原问题出发(运用表示定理引入核函数)来求解的,文章中也说明了原问题与对偶问题求解的等价性。

然后基于这一思想,Gu and Guo又提出了一个很新颖的方法,将kernel PCA成功的引入到了kernel approximation里面,将不定核降维到一个低维空间中,使得此时对应矩阵变为正定的,然后在此空间中进行训练分类器。(这个方法的巧妙之处在于,用核函数就是一个升维的过程,企图在一个高维空间中能够找到一个线性可分的分类器,但是不巧的是升维之后,我们面临的核矩阵是不定的了,因此常用的凸优化方法就失效了,然后,这个方法就运用kernel PCA方法来对这个高维空间进行降维处理,尝试在降维后的空间中找到一个低维正定的表示)
具体的模型:
\begin{align} \\
\min_{W,w,b,\xi} & \quad \frac{1}{2}w^Tw+C\sum_i \xi_i+\rho |\phi - WW^T\phi|_F^2 \\
s.t. & \quad y_i(w^TW^T\phi(:,i)+b)\geq1-\xi_i, \xi_i\geq 0 \\
& \quad W^TW = I_d
\end{align}

其中,$||\phi - WW^T\phi||_F^2$表示KernelPCA,结合SVM的Lagrange对偶+kernelPCA的变换得到
\begin{align} \\
\max_\alpha \min_V & \quad \alpha^T e - \frac{1}{2}\alpha^T Y K_0 V V^T K_0 Y \alpha -\rho \cdot tr(V^TK_0K_0V) \\
s.t. & \quad \alpha \cdot diag(Y)=0; \\
& \quad 0\leq \alpha \leq C \\
& \quad V^TK_0 V = I_d \\
& \quad K_0 V V^T K_0 \geq 0
\end{align}

其中,最后一条约束表示在低维空间中的核矩阵,为正定的,并且只要$V$是实值向量,就能够保证最后一个约束满足。
这篇文章:Learning svm classifiers with indefinite kernels发在AAAI’12上,并获得了当年的best paper,赞!但是,在我自己代码实现的过程中也发现了一些弊端:

  1. 要求矩阵K和M的逆,所以他们的特征值不能有0.
  2. 要预先判断K的正特征值个数,所以当K的正特征值很少的时候(接近负定),PCA的降到的维度就会受到相应的影响,那么最终的分类精度也就会受到影响了。

Directly Focus on the Indefinite Kernel

这一大类里面方法还是挺迥异的,主要有SMO-type SVM,1-norm SVM, SVM in krein等一系列方法。

SMO-type SVM

这一方法提出的比较早,在03年由林轩田和林智仁共同完成。文章主要基于sigmoid核的不同核参数的组合来讨论的,然后对SMO算法进行了稍微的改动以适用于不定核的求解,这一算法已集成到他们开源的软件LibSVM中,只要用’-t 4’的参数设置他就能自动调用相关算法来求解该问题。
另外,这一算法主要是基于对偶形式的不定核SVM问题来求解的,因此,由于核矩阵的不定性,在应用Lagrange对偶化时就不能忽略对偶间隔的问题。同时,我们的实验结果也验证了这一想法,SMO-type SVM方法的效果并不理想,与谱分解的结果相近。

1-norm SVM

这一方法还是挺巧妙的,他避开了在目标函数中产生不定核矩阵的做法,而是直接利用1-norm的形式,并通过强制要求核前面的组合系数大于0,将原来的1-norm svm转换成了一个Linear Programming。

\begin{align} \\
\min_{\lambda, \xi, b} & \quad \sum_j |\lambda_j| + C \sum_{i=1}^m \xi_i \\
s.t. & \quad y_i \cdot (b + \sum_j \lambda_j \cdot h_j(x_i)) \geq 1 - \xi_i \\
& \quad \xi_i \geq 0
\end{align}

强制规定$\lambda\geq 0$后,得到

\begin{align} \\
\min_{\lambda, \xi, b} & \quad \sum_{i=1}^m ||\lambda_i||_1 + C \sum_{i=1}^m \xi_i \\
s.t. & \quad Q \lambda + b y \geq 1 - \xi \\
& \quad \lambda, \xi \geq 0
\end{align}

同时,文章中对于这一形式也从相似函数的角度给出了解释,不过并没有很清楚的给出具体的推导化简的公式,是如何从相似函数间隔最大的公式推导到最后的LP问题的。另外,由于他上面对$\lambda$的强制要求,有点与对偶svm中的Lagrange乘子$\alpha$相似,因此,可能存在对偶间隔的问题。在实验过程中,1-norm的效果有点不太稳定,时好时坏,可能跟数据集有关吧。

SVM in Krein

这个方法是从Reproducing Kernel Krein Space(RKKS)出发,不再是求解一个minimization problem,而是求解一个stabilization problem。
具体模型:
\begin{align}\\
stab_{f\in\mathcal K, b\in \mathbb R} & \quad \frac{1}{2}\langle f, f\rangle_{\mathcal K}\\
s.t. & \quad \sum_{i=1}^l \max(0, 1-y_i(f(x_i)+b))\leq \tau
\end{align}

根据不定核在krein空间中的性质:$f_{\mathcal K}=f_+ + f_-$, $\langle f, f\rangle_{\mathcal K}= \langle f_+, f_+\rangle_{\mathcal H^+} - \langle f_-, f_-\rangle_{\mathcal H^-}$. 得到

\begin{align}\\
\min_{f_+\in\mathcal H^+, b\in \mathbb R} \max_{f_-\in \mathcal H^-} & \quad \frac{1}{2}\langle f_+, f_+\rangle_{\mathcal H^+} - \frac{1}{2}\langle f_-, f_-\rangle_{\mathcal H^-}\\
s.t. & \quad \sum_{i=1}^l \max(0, 1-y_i(f(x_i)+b))\leq \tau
\end{align}

将上面的与max相关的部分转换成min的形式:

\begin{align}\\
\min_{f_+\in\mathcal H^+, f_-\in \mathcal H^-, b\in \mathbb R} & \quad \frac{1}{2}\langle f_+, f_+\rangle_{\mathcal H^+} + \frac{1}{2}\langle f_-, f_-\rangle_{\mathcal H^-}\\
s.t. & \quad \sum_{i=1}^l \max(0, 1-y_i(f(x_i)+b))\leq \tau
\end{align}

从$f_+$和$f_-$,可以构造一个正的Hilbert space($\tilde{\mathcal K}$),有$\tilde f = f_+ + f_-$和$\langle \tilde{f}, \tilde{f} \rangle_{\tilde{\mathcal K}} = \langle f_+, f_+\rangle_{\mathcal H^+} + \langle f_-, f_-\rangle_{\mathcal H^-}$,带到上面的公式有

\begin{align}\\
\min_{\tilde{f} \in \tilde{\mathcal K}, b\in \mathbb R} & \quad \frac{1}{2}\langle \tilde{f}, \tilde{f}\rangle_{\tilde{\mathcal K}}\\
s.t. & \quad \sum_{i=1}^l \max(0, 1-y_i(\tilde{f}(x_i)+b))\leq \tau
\end{align}

此时,就将原来的不定核问题转变成了一个凸问题,然后运用Lagrange对偶化得到:
\begin{align}
\max_{\tilde{\alpha}} & \quad -\frac{1}{2}\tilde{\alpha}^T\tilde{G}\tilde{\alpha} + \tilde{\alpha}^T\textbf{1}\\
s.t. & \quad \tilde{\alpha}^T \textbf{y} = 0\\
& \quad 0\leq \tilde{\alpha}_i\leq C
\end{align}

到这里,求解上面的这个凸对偶问题就可以得到$\tilde{\alpha}$,然后再设法找到对应的RKKS中的解就可以了。因此,文章中给出了如何将等价的RKHS中的点映射到RKKS中去(第3.3.1节)。具体做法是$\tilde{\alpha} = P \alpha$.

svm in krein的确是很不错的,从上面的理论推导来看还是很完善的,在我们的实验上来看也是很不错的,在大多数数据集上都能有很好的效果。

References

  1. Chen, J., and Ye, J. 2008. Training svm with indefinite kernels.In Proceedings of the Twenty-fifth International Conference on Machine Learning, 136–143. Helsinki, Finland: ACM.
  2. Alabdulmohsin, I. M.; Gao, X.; and Zhang, X. 2014. Support vector machines with indefinite kernels. In Proceedings of the Sixth Asian Conference on Machine Learning, volume 39, 32–47. Nha Trang, Vietnam: JMLR.org.
  3. Chen, Y.; Gupta, M. R.; and Recht, B. 2009. Learning kernels from indefinite similarities. In Proceedings of the Twenty-sixth International Conference on Machine Learning, 145–152. Montreal, Quebec, Canada: ACM.
  4. Gu, S., and Guo, Y. 2012. Learning svm classifiers with indefinite kernels. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 942–948. Toronto, Ontario, Canada.: AAAI Press.
  5. Lin, H.-T., and Lin, C.-J. 2003. A study on sigmoid kernels for svm and the training of non-psd kernels by smo-type methods. Neural Computation 1–32.
  6. Loosli, G.; Canu, S.; and Ong, C. S. 2016. Learning svm in kreˇın spaces. IEEE Transactions on Pattern Analysis and Machine Intelligence 38(6):1204–1216.
  7. Luss, R., and d’Aspremont, A. 2008. Support vector machine classification with indefinite kernels. In The Twenty-First Conference on Neural Information Processing Systems,953–960. Vancouver, British Columbia, Canada.: Curran Associates, Inc.
  8. Wu, G.; Chang, E. Y.; and Zhang, Z. 2005. An analysis of transformation on non-positive semidefinite similarity matrix for kernel machines. In Proceedings of the Twentysecond International Conference on Machine Learning, volume 8. Citeseer.

今天花了一整天的时间看了一篇关于Multiple kernel Learning的综述文章,他是以Visual object recognition作为应用背景来分析的。文章:Multiple Kernel Learning for Visual Object Recognition:A Review,发在TPAMI’14.

文章的出发点是发现在多篇文章中关于MKL的阐述是有冲突的(文章中表1&2):

  1. 在有些文章中说MKL方法优于平均核权重的MKL方法[8,39,48],而另一些文章中却给出了相反的结论[13,24,30,31]。
  2. MKL与single kernel SVM之间的比较
  3. L1-MKL与Lp-MKL之间的比较
  4. 不同MKL方法在的computational efficiency的比较,由于不同文章中的实验结果评价不一致,比如有些是以迭代步数作为收敛的衡量,而有些是以消耗的时间作为衡量[11,30],有些基于支持向量的个数[8,47]
    其实,这主要跟相关文章中的实验设置、核函数的数量及数据集有关,在这篇文章的实验部分给出了详细的分析。

MKL方法围绕两类问题展开:

  1. 利用不同的MKL形式来提高分类精度
  2. 利用不同的优化方法来提升MKL的学习效率

Overview of MKL

  • 另一篇关于MKL的综述:[32]M. Gönen and E. Alpaydin, “Multiple kernel learning algorithms,” J. Mach. Learn. Res., vol. 12, pp. 2211–2268, Jul. 2011.

  • MKL的首次提出:[33]G. Lanckriet, N. Cristianini, P. Bartlett, and L. E. Ghaoui, “Learning the kernel matrix with semi-definite programming,” J. Mach. Learn. Res., vol. 5, pp. 27–72, Jan. 2004.

  • SMO for MKL:

  1. [9]S. Vishwanathan, Z. Sun, N. Ampornpunt, and M. Varma, “Multiple kernel learning and the SMO algorithm,” in Proc. NIPS, Nottingham, U.K., 2010, pp. 2361–2369.
  2. [16]F. R. Bach, G. R. G. Lanckriet, and M. I. Jordan, “Multiple kernel learning, conic duality, and the SMO algorithm,” in Proc. 21st ICML, New York, NY, USA, 2004.
  • L1-norm MKL: [34]S. Sonnenburg, G. Rätsch, and C. Schäfer, “A general and efficient multiple kernel learning algorithm,” in Proc. NIPS, 2006, pp. 1273–1280.

  • Lp-norm MKL:

  1. [10]M. Kloft, U. Brefeld, S. Sonnenburg, and A. Zien, “lp-Norm multiple kernel learning,” J. Mach. Learn. Res., vol. 12, pp. 953–997, Mar. 2011.
  2. [31]R. Tomioka and T. Suzuki, “Sparsity-accuracy trade-off in MKL,” in Proc. NIPS Workshop Understanding Multiple Kernel Learning Methods, 2009.
  3. [40]F. Yan, K. Mikolajczyk, J. Kittler, and A. Tahir, “A comparison of L1 norm and L2 norm multiple kernel SVMs in image and video classification,” in Proc. Int. Workshop CBMI, 2009.
  • negative entropy based MKL: [30]Z. Xu, R. Jin, S. Zhu, M. Lyu, and I. King, “Smooth optimization for effective multiple kernel learning,” in Proc. AAAI Artif. Intell., 2010.

  • mixed norms MKL:

  1. [35]M. Kowalski, M. Szafranski, and L. Ralaivola, “Multiple indefinite kernel learning with mixed norm regularization,” in Proc. 26th ICML, Montreal, QC, Canada, 2009, pp. 545–552.
  2. [15]C. Longworth and M. J. Gales, “Multiple kernel learning for speaker verification,” in Proc. ICASSP, Las Vegas, NV, USA, 2008, pp. 1581–1584.
  3. [72]V. Sindhwani and A. C. Lozano, “Non-parametric group orthogonal matching pursuit for sparse learning with multiple kernels,” in Proc. NIPS, 2011, pp. 414–431.
  • Bregman divergence: [9]S. Vishwanathan, Z. Sun, N. Ampornpunt, and M. Varma, “Multiple kernel learning and the SMO algorithm,” in Proc. NIPS, Nottingham, U.K., 2010, pp. 2361–2369.

  • theoretical studies show that L1 norm will result in a small generalization error:

  1. [36]C. Cortes, M. Mohri, and A. Rostamizadeh, “Generalization bounds for learning kernels,” in Proc. 27th ICML, Haifa, Israel, 2010.
  2. [37]Z. Hussain and J. Shawe-Taylor, “A note on improved loss bounds for multiple kernel learning,” CoRR abs/1106.6258, 2011.
  • a nonlinear combination of base kernels: [non-convex optimization problems]
  1. [12]M. Varma and B. R. Babu, “More generality in efficient multiple kernel learning,” in Proc. 26th ICML, New York, NY, USA, Jun. 2009, pp. 1065–1072. [polynomial combination]
  2. [23]J. Saketha Nath et al., “On the algorithmics and applications of a mixed-norm based kernel learning formulation,” in Proc. NIPS, 2009.
  3. [28]C. Cortes, M. Mohri, and A. Rostamizadeh, “Learning non-linear combinations of kernels,” in Proc. NIPS, 2009, pp. 396–404.[polynomial combination]
  4. [44]J. Aflalo, A. Ben-Tal, C. Bhattacharyya, J. S. Nath, and S. Raman, “Variable sparsity kernel learning,” J. Mach. Learn. Res., vol. 12, pp. 565–592, Feb. 2011.
  5. [45]F. Bach, “Exploring large feature spaces with hierarchical multiple kernel learning,” in Proc. NIPS, 2009.
  6. [17]D. P. Lewis, T. Jebara, and W. S. Noble, “Nonstationary kernel combination,” in Proc. 23rd ICML, New York, NY, USA, 2006, pp. 553–560.
  • an instance-dependent linear combination: [non-convex optimization problems]
  1. [6]J. Yang, Y. Li, Y. Tian, L. Duan, and W. Gao, “Group-sensitive multiple kernel learning for object categorization,” in Proc. 12th ICCV, Kyoto, Japan, 2009.
  2. [46]J. Yang, Y. Li, Y. Tian, L.-Y. Duan, and W. Gao, “Per-Sample multiple kernel approach for visual concept learning,” EURASIP J. Image Video Process., vol. 2010, pp. 1–13, Jan. 2010.
  3. [47]M. Gönen and E. Alpaydin, “Localized multiple kernel learning,” in Proc. 25th ICML, New York, NY, USA, 2008.
  • subgradient descent (SD) algorithms: [43]A. Rakotomamonjy, F. Bach, Y. Grandvalet, and S. Canu, “SimpleMKL,” J. Mach. Learn. Res., 9(11), pp. 2491–2521, 2008.

  • semi-infinite linear programming (SILP) based algorithm: [50]S. Sonnenburg, G. Rätsch, C. Schäfer, and B. Schölkopf, “Large scale multiple kernel learning,” J. Mach. Learn. Res., vol. 7, pp. 1531–1565, Jul. 2006.

  • SD优于SILP:

  1. [8]Z. Xu, R. Jin, H. Yang, I. King, and M. R. Lyu, “Simple and efficient multiple kernel learning by group lasso,” in Proc. 27th ICML, Haifa, Israel, 2010
  2. [41]A. Rakotomamonjy, F. Bach, S. Canu, and Y. Grandvalet, “More efficiency in multiple kernel learning,” in Proc. 24th ICML, Corvallis, OR, USA, 2007.
  3. [42]Z. Xu, R. Jin, I. King, and M. R. Lyu, “An extended level method for efficient multiple kernel learning,” in Proc. NIPS, 2009, pp. 1825–1832.
  • SILP优于SD:[11]M. Kloft et al., “Efficient and accurate lp-norm multiple kernel learning,” in Proc. NIPS, 2009, pp. 997–1005.

relationship to other approaches

  • feature selection:
  1. [51]H. Liu and L. Yu, “Toward integrating feature selection algorithms for classification and clustering,” IEEE Trans. Knowl. Data Eng., vol. 17, no. 4, pp. 491–502, Apr. 2005.
  2. [52]F. R. Bach, “Consistency of the group Lasso and multiple kernel learning,” J. Mach. Learn. Res., vol. 9, pp. 1179–1225, Jun. 2008.[group lasso]
  • metric learning: [53]T. Hertz, “Learning distance functions: Algorithms and applications,” Ph.D. dissertation, Hebrew Univ. Jerusalem, Jerusalem, Israel, 2006.

  • kernel alignment: [54]N. Cristianini, J. Kandola, A. Elisseeff, and J. Shawe-Taylor, “On kernel-target alignment,” in Proc. NIPS, 2002, pp. 367–373.

  • parametric kernel learning:

  1. [55]O. Chapelle, J. Weston, and B. Schölkopf, “Cluster kernels for semi-supervised learning,” in Proc. NIPS, 2003, pp. 585–592.
  2. [56]R. I. Kondor and J. Lafferty, “Diffusion kernels on graphs and other discrete structures,” in Proc. ICML, 2002, pp. 315–322.
  • non-parametric kernel learning:[high computational cost]
  1. [54]
  2. [57]J. Zhuang, I. W. Tsang, and S. C. H. Hoi, “SimpleNPKL: Simple non-parametric kernel learning,” in Proc. 26th ICML, Montreal, QC, Canada, 2009.
  3. [58]B. Kulis, M. Sustik, and I. Dhillon, “Learning low-rank kernel matrices,” in Proc. 23rd ICML, Pittsburgh, PA, USA, 2006, pp. 505–512.
  • semi-supervised and unsupervised kernel learning:
  1. [54]
  2. [56]
  3. [59]S. C. H. Hoi and R. Jin, “Active kernel learning,” in Proc. 25th ICML, Helsinki, Finland, 2008, pp. 400–407.
  • multi-label MKL based on OvA:
  1. [74]L. Tang, J. Chen, and J. Ye, “On multiple kernel learning with multiple labels,” in Proc. IJCAI, 2009.
  2. [22]S. Bucak, R. Jin, and A. Jain, “Multi-label multiple kernel learning by stochastic approximation: Application to visual object recognition,” in Proc. NIPS, 2010, pp. 325–333.
  3. [75]A. Zien and S. Cheng, “Multiclass multiple kernel learning,” in Proc. 24th ICML, Corvallis, OR, USA, 2007.
  4. [48]S. Ji, L. Sun, R. Jin, and J. Ye, “Multi-label multiple kernel learning,” in Proc. NIPS, 2009.

MKL optimization techniques: two groups

  • group 1: directly solve the primal problem or the dual problem
  1. [33]
  2. [16]
  3. [30]
  4. [9]
  • group 2: solve the convex-concave optimization problem by alternating between two steps: the step for updating the kernel combination weights and the step for solving the SVM classifier for the given combination weights.
  1. [50] SILP problem
  2. [43] simpleMKL: Subgradient Descent approaches for MKL; MKL-GL
  3. [12] MKL-SD
  4. [39] K. Gai, G. Chen, and C. Zhang, “Learning kernels with radiuses of minimum enclosing balls,” in Proc. NIPS, 2010, pp. 649–657. [MKL-SD]
  5. [23] MKL-MD (a mirror descent method)
  6. [42] MKL-level (an extended level method)
  7. [10] MKL-GL (group lasso)
  • online learning algorithms for MKL: process one training example at each iteration
  1. [78] R. Jin, S. C. H. Hoi, and T. Yang, “Online multiple kernel learning: Algorithms and mistake bounds,” in Proc. Int. Conf. ALT, Canberra, ACT, Australia, 2010, pp. 390–404.
  2. [21] L. Jie, F. Orabona, M. Fornoni, B. Caputo, and N. Cesa-Bianchi, “OM-2: An online multi-class multi-kernel learning algorithm,” in Proc. IEEE CVPRW, San Francisco, CA, USA, 2010, pp. 43–50.

experiments:

three datasets: Caltech 101; Pascal VOC 2007; a subset of ImageNet

AVG: average kernel approach

classification performance

  1. MKL和AVG都优于单核 SVM
  2. 当训练集样本很小时(每类有10或20个样本),与AVG相比,L1-MKL性能最差,Lp-MKL与AVG相当;当训练集样本量增大到一定程度时(每类有30个样本),L1-MKL的性能明显优于其他方法
  3. 不同的分类算法在迭代过程中的精度变化不一样(文章中图3)
    • simpleMKL迭代很小的步数就收敛了,但是在线性搜索步需要很多迭代,因此总的耗时却很大
    • MKL-SILP震荡比较明显,这由于其贪婪的本质,每次总是选择the most violated constraints 来优化
      mean average precision for MKLs

Number of kernels vs classification accuracy

文章中实验的做法:先用L1-MKL来得到所有kernel的权重并排序,然后通过逐步加入权重有序的核来验证MKL方法的性能。(文章中图4)
Change in MAP score with respect to the number of base kernels
上图表明随着核的数量的增加,L2-MKL和AVG方法的精度反而下降了,这表明后面加入的一些week kernels起到的是坏作用,而L1-MKL方法到一定程度之后,就饱和了,精度变化不大了,从另一方面来说,L1-MKL更加的鲁棒。

computational efficiency

实验结果:
Total Training Time (Secs), Number of Iterations, and Total Time Spent on Combining the Base Kernels (Secs) for Different MKL Algorithms vs Number of Training Examples
上表表明

  1. 与L1-MKL方法相比,Lp-MKL需要很小的步数,主要原因在于Lp-MKL拥有光滑的目标函数,更方便优化。
  2. 大量的时间主要花费在kernel matrix的组合上,而对于不同的L1-MKL方法而言,差异主要体现在他们在迭代过程中的稀疏性的体现。比如MKL-SILP在优化过程中就产生了稀疏解,因此其实最有效的wrapper algorithm,而SimpleMKL就不用有这样的性质了,所以需要更多的时间。

evaluation of sparseness

明显L1-MKL是具有很好的稀疏性的,而AVG和Lp-MKL就不具有稀疏性了。

reference

  1. Multiple Kernel Learning for Visual Object Recognition:A Review
  2. 作者的个人主页, 里面提供了与本文相关的代码及一些作者的个人信息。

好久没有更新了,这阵子是大忙+大闲,大忙的时候啥杂活都不想干,大闲的时候是什么正事都不想干,于是一直拖到了九月底终于静下来好好做个总结了。

大忙是在刚开学那会,赶AAAI的due,初稿其实在暑假刚开始就写好了,不过一直等到了开学才开始修改工作,其实一开始写完自我感觉还可以,不过改完发现已经完全不一样了(囧)。在改论文的过程中,算是经历了各种蛋疼的煎熬的时刻吧,不过在这里得感激我们非常nice的薛老板,往往总是一个下午一个下午的去改论文,非常耐心的去看每一句话,去核对每个单词,有时候我临时遇到不能理解的地方还要打电话打扰老板,老板总是很和蔼的去解答,遇到这样的老板还是感觉挺幸运哒!当然,我也收获了很多,大概能够掌握写这一类的科技文章的套路吧,比如文章一定一定要突出你的核心思想(或者说是文章的贡献吧),所有的语句组织都得围绕这个核心思想,不能有给PC引起歧义的语句出现,然后,就是想方设法的让PC get到你的创新点。可能是我第一次写的缘故吧,反正introduction部分就花了好久的时间去改,一开始就是从其他相关文章里面直接巴拉下来粘上去的,逻辑很零碎,然后,一稿一稿的去改,而且在跟老板交流的过程中,对其他一些相关的对比算法也有了更进一步的理解,算是一种意外的收获吧。然后,对于Latex工具还是很赞的,强大格式编排,可以让你专注于内容的写作,必然是各种写作的首选利刃。论文虽然是投了,中或者是不中就看命吧,今年好像投稿量都接近3k了,而且,现在做svm的也不是很多了,听老板说好像专门做不定核的就我们一篇,还是有点小忐忑的,不过我想这也正常,毕竟现在这deeplearning正火,很多研究都往dl上靠,前期老板还传了一篇deep kernel learning 的文章,瞄了一眼是用高斯过程做的,貌似跟dl木有太大关系吧~然后,我想,其实对于不定核的研究已经有不少很不错的工作了,而且个人觉得svm in krein的框架的确是很牛逼,在各种数据集上的效果都不错,而且他的理论推导及给出的解释也还完善,只是可能他的出发点就是在这个非凸问题上去找一个鞍点,对于传统的凸优化而言,这样的结果显得有些单薄,但是对于不定核的非凸问题是不是给出一个鞍点就已经足够了呢?虽然在我们的文章中,这也是我们认为的缺点之一吧,不过还是持保留意见吧。对了,在论文的最后时刻,找到了一篇将不定核svm用于文本分类的文章,是发在AAAI’16上,他论文里面用的模型直接是Luss最早提出的模型,所以,顿时感觉不定核还是有其用武之地的,只是我们木有发现而已,所以,我想作为小硕还是找些应用场景做做比较好,对于深入的理论研究还是有点吃力的。在论文工作结束之后,紧接着就参加了今年的研究生数模(我会说是由于不要参赛费,而且参加还有补助才参加的么~),我们做的是B题,其实是一种特殊要求的特征选择类问题,一开始我们尝试用分类结果作为依据,用随机森林来做,并根据给出的Feature的Feature importance来选择特征,不过最后发现一方面随机森林的随机性太大了,精度与Feature importance前后差异太大了,另一方面,精度最高才接近60%,这有点不能接受,我折腾了快两天才选择放弃这一想法,心情也low到了极点,不过这个时刻就要感谢团队里的小伙伴了,倩汶在看一篇专门针对基因致病位点的文章里面提到了一系列的方法,于是我就是尝试了一个MDR的方法,它通过暴力搜索的方式,遍历求解每一种位点组合与疾病的关联度,并找到每一类位点组合中的最相关的作为输出,可想而知,对于题目给出的有9k个位点特征的情况下,遍历一个三位点组合就是$C_{9k}^3$了,所以只能作为一种对比算法吧。然后阿发那边一直用他的思路去做,特别是最后一问,他俩合作用multi-label的方法去做,还是很赞的!可能由于我们前三天做的比较安逸吧,最后还的通宵写论文,总之,也是有不少收获吧!然后我想这可能是我最后一次数模了吧,还记得本科刚开始是跟着淼哥和芳芳姐做,然后和老刘一起参加了不少,也从他们身上学到了很多,这些宝贵的经历都记录了我成长的过程,我想这些都会是我美好回忆的一部分吧。关于科研我想还有几点是需要注意的,因为研一刚开始那会,真的是什么都不懂,然后摸索着去看论文,实现代码,debug,调参等等,这些都需要耐心和理性的分析,尤其是对论文的阅读不能有想当然的部分,一定要仔仔细细的看,或许对于有些定理的证明不能一开始掌握的很好,但是多读之后一定会有收获的(满满的鸡汤,但是好像事实又总是这样的!)

研究生的生活的确跟本科生的生活不一样了,不再像本科生那样一味的学习书本知识,为了一份不错的成绩单,而是有了一个自己的方向,生活中的大部分时间也从宿舍转义到了实验室,实验室就像我们的另一家,于我而言,我们现在的这个家很温馨,很活力,而且发展也很迅速,因为现在两个实验室都快坐不下了!研究生一年级的时候,在师兄师姐的带领下,参加了各种各样的团建活动,学会了打德州,打uno,还有现在我非常迷的狼人杀,生活算是丰富多彩吧,这充分体现了学习好与娱乐多并不冲突,而且从这些娱乐活动中,能够让你学到一些在学术中学不到的东西,比如与人的交流啊,逻辑的推理啊,常识的学习啊等等吧,总之,学习是永无止境的,只是针对学什么而已吧。

关于感情方面,感觉自己还是不太善于表达吧,貌似内心戏太足了,所以,我想还是应该大胆的去表达吧,喜欢就是喜欢,哪怕只是曾经喜欢,说出来大家都释然了,可以继续寻找适合自己属于自己的那份感情。

研究生剩下来的时间其实并不多了,到了明年这个时候,我们应该都在忙于寻找下一个落脚的地方,所以,为了能够在明年的这个时候多一些泰然少一些局促,研二这一年真的需要静下心来好好的规划规划了。目下能及的是,发现敲了一年MATLAB之后,发现自己蛋疼的只会写MATLAB了,所以,接下来的一段时间我想好好把C++再重拾起来,做一些算法题,实现一些machinelearning的方法,然后,Python的话也是要不断的练习的,现在的想法也是实现一些ml的方法吧。至于科研,我想首先把多不定核学习的给解决了,然后有可能找到一个应用场景做一下吧。这里只是简单的提一下吧,后面还是需要详细的规划一下的。国庆快要到了,整个暑假基本上都呆在了学校,所以国庆回家多呆几天陪陪爸妈。嗯,就这样吧,国庆快乐!

本节主要讲了一些关于神经网络的学习与评估方面的知识。

Gradient checks

  1. 使用中心化公式:
    $$\frac{df(x)}{dx} = \frac{f(x+h)-f(x-h)}{2h}$$

  2. 使用相对误差来比较两者的差异:
    $$relative \ error = \frac{|f’_a-f’_n|}{\max(|f’_a|,|f’_n|)}$$

在实际的计算中,对于relative error(re)的评价,主要分一下几种情况:
1) $re > 1e-2$: 出错
2) $1e-2 > re > 1e-4$ : 不舒服
3) $1e-4 > re$: 当函数有不可导点存在时,这样的精度时OK的;但如果没有不可导点时,这个精度还是太高了
4) $1e-7 > re$: OK

课程中还讲解了很多细节的地方:

  1. 编程时,要使用双精度来作为变量的声明与定义
  2. 目标函数中不可导导致的梯度检查出现问题,需要额外关注,使用少量数据点来解决这一问题
  3. 谨慎设置步长 h
  4. 网络“预热”后再检查
  5. 不让正则化吞没了数据的损失
  6. 在做梯度检查时,记得关闭Dropout和数据扩张(augmentations)
  7. 检查少量的维度

Before learning: sanity checks Tips/Tricks

  1. 寻找特定状况下的正确损失值
    比如CIFAR-10数据集,对于Softmax分类器,初始的期望损失值为2.302,这是因为一个样本被判定为某个个类别(共10个类别)的概率是0.1,所以 $-\ln(0.1) = 2.302$
    对于Weston Watkins SVM,假设所有边界都被越多,则损失值为9.

  2. 提高正则化强度时导致损失值变大

  3. 对于小数据子集过拟合

Babysitting the learning process

检查整个的学习过程,与周期相关的性能指标
这里的周期衡量了在训练中每个样本数据都被观察过次数的期望,周期与数据的批尺寸有关

指标有如下一些:

  1. 损失函数: 损失值
  2. training set和validation set的准确率,可以防止过拟合
  3. 权重更新比例: 大概 $1e-3$ 左右
    code:

    1
    2
    3
    4
    5
    6
    #assume parameter vector W and its gradient vector dW
    param_scale = np.linalg.norm(W.ravel())
    update = -learning_rate*dW # simple SGD update
    update_scale = np.linalg.norm(update.ravel())
    W += update # the actual update
    print update_scale / param_scale # want ~1e-3
  4. 检查每层的激活数据及梯度分布

  5. 如果是图像数据,可以将第1层可视化来判断网络的学习情况

Parameter updates

  1. 普通的更新方法(一阶方法): $x += - learning\_rate * dx$
  2. 动量更新(momentum):
    解释:损失值可以理解为是山的高度(高度的势能:$U = mgh$)
    用随机数字初始化参数等同于在某个位置给质点设定初始速度为0,质点的力与梯度的潜在能量有关($F=-\nabla U$),质点所受的力就是损失函数的(负)梯度,又$F=ma$,所以(负)梯度与质点加速度成比例
    更新公式:

    1
    2
    3
    # Momentum update
    v = mu * v - learning_rate * dx # integrate velocity
    x += v # integrate position

    v 初始化为0,超参mu(一般设为0.9)可以通过交叉验证来确定[0.5, 0.9, 0.95, 0.99]

  3. Nesterov 动量
    Nesterov动量与普通动量有些许不同,最近变得比较流行。在理论上对于凸函数它能得到更好的收敛,在实践中也确实比标准动量表现更好一些。

    Nesterov动量的核心思路是,当参数向量位于某个位置 $x$ 时,观察上面的动量更新公式可以发现,动量部分(忽视带梯度的第二个部分)会通过 mu * v 稍微改变参数向量。因此,如果要计算梯度,那么可以将未来的近似位置 x + mu * v 看做是“向前看”,这个点在我们一会儿要停止的位置附近.因此,计算 x + mu * v 的梯度而不是“旧”位置x的梯度就有意义了.

    可以通过下图来感受一下:
    momentum and Nesterov momentum update
    对应的更新公式为:

    1
    2
    3
    4
    x_ahead = x + mu * v
    # evaluate dx_ahead (the gradient at x_ahead instead of at x)
    v = mu * v - learning_rate * dx_ahead
    x += v

    然而在实践中,人们更喜欢和普通SGD或上面的动量方法一样简单的表达式。通过对x_ahead = x + mu * v使用变量变换进行改写是可以做到的,然后用x_ahead而不是x来表示上面的更新。也就是说,实际存储的参数向量总是向前一步的那个版本。x_ahead的公式(将其重新命名为x)就变成了:

    1
    2
    3
    v_prev = v # back this up
    v = mu * v - learning_rate * dx # velocity update stays the same
    x += -mu * v_prev + (1 + mu) * v # position update changes form
  4. 学习率退火
    当一个模型的学习率很高时,系统功能过大,参数向量就会无规律地跳动,不能够稳定到损失函数更深更窄的部分去。

    对于学习率的变化,主要有三种方式:
    1)随步数衰变
    2)指数衰减 $\alpha = \alpha_0 e^{-k t}$
    3) $1/t$衰减:$\alpha = \alpha_0 / (1 + kt)$

    在实际运用中,通常使用随步数衰减的Dropout

  5. 二阶方法
    牛顿法: $x \leftarrow x - [H f(x)]^{-1} \nabla f(x)$
    其中 $H f(x)$ 表示损失函数的局部曲率,它能够让最优化过程在曲率小的时候大步前进,曲率小的时候,小步前进

  6. 逐参数适应学习率方法
    前面讨论的所有方法都是对学习率进行全局地操作,并且对所有的参数都是一样的。学习率调参是很耗费计算资源的过程,所以很多工作投入到发明能够适应性地对学习率调参的方法,甚至是逐个参数适应学习率调参。很多这些方法依然需要其他的超参数设置,但是其观点是这些方法对于更广范围的超参数比原始的学习率方法有更良好的表现。在本小节我们会介绍一些在实践中可能会遇到的常用适应算法:

    Adagrad

    1
    2
    3
    # Assume the gradient dx and parameter vector x
    cache += dx**2
    x += - learning_rate * dx / (np.sqrt(cache) + eps)

    注意,变量cache的尺寸和梯度矩阵的尺寸是一样的,还跟踪了每个参数的梯度的平方和。这个一会儿将用来归一化参数更新步长,归一化是逐元素进行的。注意,接收到高梯度值的权重更新的效果被减弱,而接收到低梯度值的权重的更新效果将会增强。有趣的是平方根的操作非常重要,如果去掉,算法的表现将会糟糕很多。用于平滑的式子eps(一般设为1e-4到1e-8之间)是防止出现除以0的情况。Adagrad的一个缺点是,在深度学习中单调的学习率被证明通常过于激进且过早停止学习。

    RMSprop
    是一个非常高效,但没有公开发表的适应性学习率方法。有趣的是,每个使用这个方法的人在他们的论文中都引用自Geoff Hinton的Coursera课程的第六课的第29页PPT。这个方法用一种很简单的方式修改了Adagrad方法,让它不那么激进,单调地降低了学习率。具体说来,就是它使用了一个梯度平方的滑动平均:

    1
    2
    cache = decay_rate * cache + (1 - decay_rate) * dx**2
    x += - learning_rate * dx / (np.sqrt(cache) + eps)

    在上面的代码中,decay_rate是一个超参数,常用的值是[0.9,0.99,0.999]。其中x+=和Adagrad中是一样的,但是cache变量是不同的。因此,RMSProp仍然是基于梯度的大小来对每个权重的学习率进行修改,这同样效果不错。但是和Adagrad不同,其更新不会让学习率单调变小。

    Adam
    Adam是最近才提出的一种更新方法,它看起来像是RMSProp的动量版。简化的代码是下面这样:

    1
    2
    3
    m = beta1*m + (1-beta1)*dx
    v = beta2*v + (1-beta2)*(dx**2)
    x += - learning_rate * m / (np.sqrt(v) + eps)

    注意这个更新方法看起来真的和RMSProp很像,除了使用的是平滑版的梯度m,而不是用的原始梯度向量dx。论文中推荐的参数值eps=1e-8, beta1=0.9, beta2=0.999。在实际操作中,我们推荐Adam作为默认的算法,一般而言跑起来比RMSProp要好一点。但是也可以试试SGD+Nesterov动量。完整的Adam更新算法也包含了一个偏置(bias)矫正机制,因为m,v两个矩阵初始为0,在没有完全热身之前存在偏差,需要采取一些补偿措施。建议读者可以阅读论文查看细节,或者课程的PPT。

    课程中给出两个动图来显示不同的学习率下优化性能的比较:
    Contours of a loss surface and time evolution of different optimization algorithms
    A visualization of a saddle point in the optimization landscape, where the curvature along different dimension has different signs

Hyperparameter optimization

  1. 实现
    一个具体的设计是用仆程序持续地随机设置参数然后进行最优化。在训练过程中,仆程序会对每个周期后验证集的准确率进行监控,然后向文件系统写下一个模型的记录点(记录点中有各种各样的训练统计数据,比如随着时间的损失值变化等),这个文件系统最好是可共享的。在文件名中最好包含验证集的算法表现,这样就能方便地查找和排序了。然后还有一个主程序,它可以启动或者结束计算集群中的仆程序,有时候也可能根据条件查看仆程序写下的记录点,输出它们的训练统计数据等。

  2. 比起交叉验证最好使用一个验证集

  3. 超参数范围:
    学习率 : learning_rate = 10 ** uniform(-6, 1)

  4. 随机搜索优于网格搜索
    Random Search for Hyper-Parameter Optimization中说“随机选择比网格化的选择更加有效”,而且在实践中也更容易实现

  5. 对于边界上的最优值要小心

  6. 从粗到细地分阶段搜索
  7. 贝叶斯超参数最优化

Evaluation

模型的集成

  1. 同一个模型,不同的初始化
  2. 在交叉验证中发现最好的模型
  3. 一个模型设置多个记录点
  4. 在训练的时候跑参数的平均值
    模型集成的一个劣势就是在测试数据的时候会花费更多时间。最近Geoff Hinton在“Dark Knowledge”上的工作很有启发:其思路是通过将集成似然估计纳入到修改的目标函数中,从一个好的集成中抽出一个单独模型。

references

  1. CS231n:Neural Networks Part 3: Learning and Evaluation
  2. 知乎:CS231n课程笔记翻译:神经网络笔记3(下) 翻的很棒!