文章目录
  1. 1. Spectrum Approximation
    1. 1.1. Spectrum Transformation
    2. 1.2. Kernel Approximation
  2. 2. Directly Focus on the Indefinite Kernel
  3. 3. SMO-type SVM
  4. 4. 1-norm SVM
  5. 5. SVM in Krein
  6. 6. References

研究生一年级主要都在做不定核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.