软间隔SVM的形式如下：
$$ \min\limits_{b,w}\frac{1}{2}||w||^2+C\sum\limits_{i=1}^{n}\xi_i\\ \begin{aligned} s.t. \quad y_i(w^Tx_i+b)\ge 1-\xi_i &,i = 1,2...,n\\ \end{aligned} $$
根据约束的定义，可以推出：惩罚值$\xi_i$在$y_i(w^Tx_i+b)\ge 1$的时候等于0(也就是不仅仅分类正确了，还在分类边界外)，而在$y_i(w^Tx_i+b)< 1$的时候则是$1-y_i(w^Tx_i+b)$(只要没有在分类边界外，即使分类对了，还是会有惩罚)
那么，可以推出，$\xi_i=\max(1-y_i(w^Tx_i+b),0)$
于是软间隔SVM的公式就可以变成这样：
$$ \min_{b,w}\frac{1}{2}w^Tw+C\cdot\sum\limits_{i=1}^N\max(1-y_i(w^Tx_i+b),0) $$
$\max(1-y_i(w^Tx_i+b),0)$的图片如下图中紫色的线：
假设$s=w^Tx+b$
- 紫色的线叫做合页损失函数(Hinge Loss)(因为像是要把书合起来的样子)$\max(1-ys,0)$
- 黑色的线叫做0-1损失函数(zero-one loss)$[ys]<0$
- 黄色的线是逻辑斯蒂回归(logistic regression)的损失$\log_2(1+exp(-ys))$
上图是他们的对比图。可以看出，合页损失函数是0-1损失函数的上限，而且是凸上限(convex upper bound)。而且合页损失函数与LogReg有很大的相似度。
当$ys\rightarrow+\infty$，合页损失函数=0，LogReg的损失趋近于$0$；
而当$ys\rightarrow-\infty$，合页损失函数=$1-ys$，LogReg的损失趋近于$-ys$，由于$ys$趋近于无限大，合页损失函数中的$1$就无所谓了。所以他们都趋近于$-ys$。
所以，其实软间隔SVM实际上与L2正则化的LogReg(L2-regularized Logistic Regression)是做相同的事情。
Kernel Logistic Regression
所以既然有这么大的相似性，如果直接用软间隔SVM代替LogReg不是很好吗？这种方法确实可以，但是使用了软间隔SVM代替LogReg，就会丧失LogReg的一些优点特性(比如最大似然学习等等)。
于是，工程上通常先训练一个SVM，用它的解$(w,b)$作为LogReg的初值$w_0$，再用LogReg进行学习。然而，这个方法其实与直接跑LogReg没什么区别。
所以怎么融合SVM与LogReg的优点呢？
首先，做一个SVM，得到一个解
$$ w^T\Phi(x)+b_{SVM} $$
那么在这上面加两个自由度，来对其进行放缩和平移：
$$ A\cdot (w^T\Phi(x)+b_{SVM})+B $$
$A$是放缩，$B$是平移。再在$A,B$两个参数上做LogReg训练调整它们，就可以更吻合最大似然的需求，同时获得SVM与LogReg的优点。通常，如果SVM做的不错，$A>0$，而$B\approx 0$。
所以，新的LogReg问题是这样的：
$$ \min_{A,B}\frac{1}{N}\sum\limits_{i=1}^N\log\Bigg( 1+\exp\Bigg(-y_i\Big(A\cdot (w^T_{SVM}\Phi(x_i)+b_{SVM})+B\Big) \Bigg) \Bigg) $$
用梯度下降(Gradient Descent)，随机梯度下降(Stochastic Gradient Descent)等等，都可以解这个问题。
如果我真的就想在核函数转换的特征上计算LogReg，而不使用软间隔SVM算呢？
核函数为什么work？是因为最佳的$w$，$w_*^T=\sum\limits_{i=1}^N\beta_i\Phi(x_i)$，所以$w_*^T$是特征$\Phi(x_i)$的线性组合。
而预测新的$x$时，计算的是$w_*^Tx=\sum\limits_{i=1}^N\beta_iK(x_i,x)$。
其实LogReg其实也有这个性质，通过梯度下降，$W_{LogReg}=\sum\limits_{i=1}^N(a_iy_i)x_i$其实也可以是特征的线性组合。
既然都是特征的线性组合，不如直接把它们带进公式里，原始的LogReg公式如下：
$$ \min_{A,B}\frac{\lambda}{N}\|w\|^2+\frac{1}{N}\sum\limits_{i=1}^N\log\Bigg(1+\exp\Big(-y_iw^T\Phi(x_i)\Big)\Bigg) $$
用特征的线性组合代替$w$后的LogReg公式如下：
$$ \min_{\beta}\frac{\lambda}{N}\sum_{i=1}^N\sum_{j=1}^N\beta_i\beta_jK(x_i,x_j)+\frac{1}{N}\sum\limits_{i=1}^N\log\Bigg(1+\exp\Big(-y_i\sum\limits_{j=1}^N\beta_jK(x_i,x_j)\Big)\Bigg) $$
所以，只要解出$\beta$就OK了。这是一个没有条件的最佳化问题，这就叫做核逻辑斯蒂回归(Kernel Logistic Regression)
Kernel Ridge Regression
与此同理，我们也可以创建基于核函数的岭回归(Kernel Ridge Regression)。
岭回归是回归分析加上L2正则，它的原始公式如下：
$$ \min_{w}\frac{\lambda}{N}\|w\|^2+\frac{1}{N}\sum_{i=1}^N(y_i-w^Tx^i)^2 $$
式子的第一项为正则项，是泛化惩罚，第二项则是原始的损失函数。
最优的解仍然是这些特征的线性组合$w_*=\sum_{i=1}^N\beta_ix_i$，所以按照上面处理LogReg的思路，可以把求$w$变成求$\beta$，并且用上核函数，所以公式变成了下面这样：
$$ \min_{\beta}\frac{\lambda}{N}\sum_{i=1}^N\sum_{j=1}^N \beta_i\beta_jK(x_i,x_j)+\frac{1}{N}\sum_{i=1}^N(y_i-\sum_{j=1}^N\beta_jK(x_i,x_j))^2 $$
如果用矩阵的方式表示，就会简单很多：
$$ E_{aug}(\beta)=\frac{\lambda}{N}\beta^TK\beta+\frac{1}{N}\Big( \beta^TK^TK\beta-2\beta^TK^Ty+y^Ty \Big) $$
上面第二项拆解过程是因为
$$ \begin{aligned} \Big(y_i-\sum_{j=1}^N\beta_jK(x_i,x_j)\Big)^2&=\|y-K\beta\|^2\\ &=\beta^TK^TK\beta-2\beta^TK^Ty+y^Ty \end{aligned} $$
而$E_{aug}(\beta)$对$\beta$求偏导，则得到：
$$ \begin{aligned} E_{aug}(\beta)&=\frac{2}{N}(\lambda K^T\beta+K^TK\beta-K^Ty)\\ &=\frac{2}{N}K^T\big( (\lambda I+K)\beta-y \big) \end{aligned} $$
让梯度变为0，那么可知$\beta=(\lambda I+K)^{-1}y$。如果$\lambda>0$，这个解一定存在，因为合法的Kernel一定是半正定的，加上$\lambda$之后，一定是个可逆的矩阵。
求出解的计算复杂度为$O(N^3)$，虽然理论上存在解，但是计算复杂度很高。原本的岭回归的$w=(\lambda I+X^TX)^{-1}X^Ty$，矩阵大小是$d\times d$($d$是特征数)。而基于核的岭回归的$\beta$则是$N\times N$。因为毕竟使用的是Kernel，自由度当然更高。
下一篇，将解决计算复杂度的问题，并推出基于SVM的回归。