C-SVM求解

C-SVM的实质是在原始特征空间或者变换空间寻找一个最优超平面，能把两类样本集很好的分开，这个最优超平面的最优是“最大间隔”+“最少错分样本数目”的折中。 LS-SVM的实质也是寻找一个最优超平面，能把两类样本集很好的分开，但这个最优超平面所在的最优分类间隔的两个超平面是这样确定的：某类样本侧的超平面间隔关于该类样本的距离平方和最小。

因此基于不同的“最优”标准，就得到了不同的目标函数，因此尽管都是在寻找最优超平面，但因标准不一样，所以找到的超平面也不一样。

对于C-SVM来说，最优超平面仅有占据训练样本少数比例的支持向量所决定；而LS-SVM的最优超平面是由所有训练样本共同决定的。

LIBSVM: A Library for Support Vector Machines 这是libsvm官方文档

目标函数###

SVM软间隔原始形式

$$\min \frac 12 W^TW + C \sum_{i=1}^n \xi(w,x_i,y_i)$$

• 当损失函数 $\xi(w,x_i,y_i) = \max(0,(1-y_iwx_i))$时就叫做L1-SVM,

• 当损失函数 $\xi(w,x_i,y_i) = \max(0,(1-y_iwx_i))^2$时就叫做L2-SVM。

对偶函数统一形式###

$$\min_{\alpha} \frac{1}{2} \alpha^T Q \alpha - e^T\alpha \\ subject to \quad 0 \le \alpha_i \le U , \forall i \\ e^T \text{为单位列向量} \\ Q = Q' + D , Q'_{ij}=y_iy_j<x_i,x_j> , D\text{为对角阵}$$

也可以从对偶形式定义：

• 对于L1-SVM: $D_{ii}=0 \quad \And\And \quad U=C$

• 对于L2-SVM: $D_{ii}=1/(2C) \quad \And\And \quad U=+\infty$

Coordinate Descent Method###

$$\alpha_i^{k+1} = \arg \min f(\alpha_1^{k+1},\cdots,\alpha_{i-1}^{k+1},\varepsilon,\alpha_{i+1}^k,\cdots,\alpha_n^k)$$

额，不知道怎么算法排版，后再排 然后对单维度进来牛顿法求解，

ADMM###

$$f = \frac 1n \sum_{i=1}^n(\max\{1-y_i w^T x_i,0\} + \frac {\lambda}{2n} ||w||^2) \\ f = \frac 1{n/2} \sum_{i=1}^{n/2}(\max\{1-y_i w_1^T x_i,0\} + \frac {\lambda}{2n} ||w_1||^2) + \frac 1{n/2} \sum_{i=n/2+1}^{n}(\max\{1-y_i w_2^T x_i,0\} + \frac {\lambda}{2n} ||w_2||^2) \qquad w_1=w_2\\$$

参考佳文####

SVM学习——Coordinate Desent Method