软间隔与正则化

我们一直假定训练样本在样本空间或特征空间中是线性可分的，但是现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分。

缓解该问题的一个方法就是允许向量机在一些样本上出错。

硬间隔（hard margin）要求所有的样本均满足约束，但是软间隔则是允许某些样本不满足约束 $$y_i(w^T{x}_i\text{wTxi}{w}^T{x}_i+b)\ge 1$$ 当然，在最大化间隔的同时，不满足约束的样子应尽可能小，于是，优化目标可以写成： $$\underset{w,b}{\min }\frac{1}{2}||w\text{w}w|{|}^2+C\sum {i=1}^m{\ell }_{0/1}(y_i(w^T{x}_i\text{wTxi}{w}^T{x}_i+b)-1)$$ 其中$C>0$是一个常数，${\ell }_{0/1}$是0/1损失函数 $${\ell }_{0/1}=\{\begin{array}{ll}1& ifz<0\\ 0& otherwise\end{array}$$ 当$C$为无穷大，使得所有样本均满足约束，当$C$取有限值时，允许一些样本不满足约束

然而${\ell }_{0/1}$非凸、非连续、数学性质不太好。通常用其他一些函数来代替${\ell }_{0/1}$。称为替代损失函数

常用的替代损失函数

hinge 损失：${\ell }_{hinge}(z)=\max (0,1-z)$指数损失(exponential loss)：${\ell }_{exp}(z)=\exp (-z)$对率损失（logistic loss）${\ell }_{log}(z)=log(1+\exp (-z))$

若采用hinge损失，则会变成： $$\underset{w,b}{\min }\frac{1}{2}||w\text{w}w|{|}^2+C\sum _{i=1}^m\max (0,1-y_i(w^t{x}_i\text{wtxi}{w}^t{x}_i+b))$$ 引入松弛变量（slack variables）${\xi }_i\ge 0$,则公式可以重新写成 $$\underset{w,b,{\xi }_i}{\min }\frac{1}{2}||w\text{w}w|{|}^2+C\sum _{i=1}^m{\xi }_i$$

$$\begin{gathered} s.t.y_i(w^T{x}_i\text{wTxi}{w}^T{x}_i+b)\ge 1-{\xi }_i \\ {\xi }_i\ge 0,i=1,2,\cdots ,m \end{gathered}$$

类似的，通过拉格朗日乘子法可得拉格朗日函数 $$\begin{array}{rl}L(w\text{w}w,b,\alpha ,\xi ,\mu )& =\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\xi }_i\\ & +\sum _{i=1}^m{\alpha }_i(1-{\xi }_i-y_i(w^T{x}_i\text{wTxi}{w}^T{x}_i+b))-\sum _{i=1}^m{\mu }_i{\xi }_i\end{array}$$ 其中${\alpha }_i\ge 0,{\mu }_i\ge 0$是拉格朗日乘子

令$L(w\text{w}w,b,\alpha ,\xi ,\mu \text{α,ξ,μ}\alpha ,\xi ,\mu )$对$w,b,{\xi }_i$的偏导为零可得： $$\begin{gathered} w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i \\ 0=\sum _{i=1}^m{\alpha }_i{y}_i \\ C={\alpha }_i+{\mu }_i \end{gathered}$$ 可得对偶问题 $$\begin{gathered} \underset{\alpha }{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\text{xiTxj}{x}_i^T{x}_j \\ s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0 \\ 0\le {\alpha }_i\le C,i=1,2,\cdots ,m \end{gathered}$$ 对于软间隔支持向量机，KKT条件要求 $$\{\begin{array}{l}{\alpha }_i\ge 0,{\mu }_i\ge 0\\ \\ y_{i}f(x_i)-1+{\xi }_i\ge 0\\ \\ {\alpha }_i(y_{i}f(x_i)-1+{\xi }_i)=0\\ \\ {\xi }_i\ge 0,{\mu }_i{\xi }_i=0\end{array}$$ 于是，对于任意训练样本（$x_i\text{xi}{x}_i,y_i$）,总有${\alpha }_i=0$或$y_{i}f(x_i\text{xi}{x}_i)=1-{\xi }_i$，若${\alpha }_i=0$，则该样本不会对$f(x)$有任何以你选哪个，若${\alpha }_i>0$，则必有$y_{i}f(x_i\text{xi}{x}_i)=1-{\xi }_i$，即样本是支持向量。若${\alpha }_i<C$，则${\mu }_i>0$，进而有${\xi }_i=0$,该样本恰在最大间隔边界上，若${\alpha }_i=C$，则有${\mu }_i=0$，此时若$\xi \le 1$则该样本落在最大间隔内部，若${\xi }_i>1$则样本被错误分类。

支持向量回归

给定训练样本$D=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_m,y_m)\},y_i\in \mathbb{R}$。希望学习得到回归模型，使得$f(x)$与$y$尽可能接近，$w,b$是待确定的模型参数。

支持向量回归（Support Vector Regression,SVR）假设我们容忍$f(x)$与$y$之间最多的有$ϵ$的偏差，即仅当$f(x)$与$y$之间的差别绝对值大于$ϵ$时才计算损失。

于是，SVR问题可形式化为 $$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\ell }_{ϵ}(f({x\text{x}x}_i-y_i))$$ 其中C为正则化常数，${\ell }_{ϵ}$是$ϵ$不敏感损失函数 $${\ell }_{ϵ}(z)=\{\begin{array}{ll}0& if|z|\le ϵ\\ |z|-ϵ& otherwise\end{array}$$ 引入松弛变量${\xi }_i$和$\widehat{{\xi }_i}$ $$\underset{w,b,{\xi }_i,\widehat{{\xi }_i}}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m({\xi }_i+\widehat{{\xi }_i})$$

$$\begin{array}{rl}s.t.& f(x_i)-y_i\le ϵ+{\xi }_i\\ & y_i-f(x_i)\le ϵ+\widehat{{\xi }_i}\\ & {\xi }_i\ge 0,\widehat{{\xi }_i}\ge 0,i=1,2\cdots m\end{array}$$ 通过引入拉格朗日乘子$\mu \ge 0,\widehat{{\mu }_i}\ge 0,{\alpha }_i\ge 0,\widehat{{\alpha }_i}\ge 0$,可以得到拉格朗日函数 $$\begin{array}{rl}& L(w,b,\alpha ,\hat{\alpha },\xi ,\hat{\xi },\mu ,\hat{\mu })\\ & =\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m({\xi }_i+{\hat{\xi }}_i)-\sum _{i=1}^m{\mu }_i{\xi }_i-\sum _{i=1}^m{\hat{\mu }}_i{\hat{\xi }}_i+\sum _{i=1}^m{\alpha }_i(f(x_i)-y_i-ϵ-{\xi }_i)\\ & +\sum _{i=1}^m{\hat{\alpha }}_i(y_i-f(x_i)-ϵ-{\hat{\xi }}_i)\end{array}$$ 可得到SVR的对偶问题 $$\begin{array}{rl}\underset{\alpha ,\hat{\alpha }}{\max }& \sum _{i=1}^m{y}_i({\hat{\alpha }}_i-{\alpha }_i)-ϵ({\hat{\alpha }}_i+\alpha )\\ & -\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m({\hat{\alpha }}_i-{\alpha }_i)({\hat{\alpha }}_j-{\alpha }_j)x_i^T{x}_j\text{xiTxj}{x}_i^T{x}_j\\ s.t.& \sum _{i=1}^m({\hat{\alpha }}_i-{\alpha }_i)=0\\ & 0\le {\hat{\alpha }}_i,{\alpha }_i\le C\end{array}$$ 需要满足的KKT条件 $$\{\begin{array}{l}{\alpha }_i(f(x_i\text{xi}{x}_i)-y_i-ϵ-{\xi }_i)=0\\ {\hat{\alpha }}_i(y_i-f(x_i\text{xi}{x}_i)-ϵ-{\hat{\xi }}_i)=0\\ {\alpha }_i{\hat{\alpha }}_i=0,{\xi }_i{\hat{\xi }}_i=0\\ (C-{\alpha }_i){\xi }_i=0\\ (C-\hat{\alpha }){\hat{\xi }}_i=0\end{array}$$ 可以看出，当且仅当$f(x_i\text{xi}{x}_i)-y_i-ϵ-{\xi }_i=0$时${\alpha }_i$能取非零值，当前仅当$y_i-f(x_i\text{xi}{x}_i)-ϵ-{\hat{\xi }}_i=0$s时${\hat{\alpha }}_i$能够取非零值。

则SVR的解形如 $$f(x\text{x}x)=\sum _{i=1}^m({\hat{\alpha }}_i-{\alpha }_i)x_i^T{x}_i\text{xiTxi}{x}_i^T{x}_i+b$$ 考虑特征映射形式，则形如 $$w\text{w}w=\sum _{i=1}^m({\hat{\alpha }}_i-{\alpha }_i)\varphi (x_i\text{xi}{x}_i)$$ 则SVR可以表示为 $$f(x\text{x}x)=\sum _{i=1}^m({\hat{\alpha }}_i-{\alpha }_i)\kappa (x,x_i\text{x,xi}x,x_i)+b$$ 其中$\kappa (x,x_j\text{x,xj}x,x_j)=\varphi (x_i\text{xi}{x}_i{)}^T\varphi ({x\text{x}x}_j)$为核函数

核方法

定理 令$\mathbb{H}$为核函数$\kappa$对应的再生核希尔伯特空间，$||h|{|}_{\mathbb{H}}$表示$\mathbb{H}$空间中关于$h$的范数，对于任意单调递增函数$\Omega :[0,\infty ]\to \mathbb{R}$和任意非负损失函数$\ell :{\mathbb{R}}^m\to [0,\infty ]$，优化问题 $$\underset{h\in \mathbb{H}}{\min }=\Omega (||h|{|}_{\mathbb{H}})+\ell (h(x_1),h(x_2),\cdots ,h(x_m))$$ 的解总可写为： $$h^{\ast }(x\text{x}x)=\sum _{i=1}^m{\alpha }_i\kappa (x,x_i\text{x,xi}x,x_i)$$ 表示定义对损失函数没有限制，对正则化项$\Omega$仅要求单调递增，甚至不要求$\Omega$是凸函数，意味着对于一般的损失函数和正则化项，优化问题的最优解可以表示为核函数的线性组合。

人们发展出一系列的基于核函数的学习方法。通过核化（引入核函数）将线性学习器扩展为非线性学习器。

我们先假设可通过某种映射（$\varphi :\mathcal{X}\to \mathbb{F}$）将样本映射到一个特征空间$\mathbb{F}$，然后在$\mathbb{F}$中执行线性判别分析，以求得KLDA的学习目标 $$\underset{w\text{w}w}{\max }J(w\text{w}w)=\frac{w^T{S}_b^{\varphi }w\text{wTSbϕw}{w}^T{S}_b^{\varphi }w}{w^T{S}_w^{b}w\text{wTSwbw}{w}^T{S}_w^{b}w}$$ 其中${S\text{S}S}_b^{\varphi }$和${S\text{S}S}_w^{\varphi }$分别为训练样本在特征空间$\mathbb{F}$中的类间散度矩阵和类内散度矩阵。令$X_i$表示第$i\in \{0,1\}$类样本的集合，其样本数为$m_i$，总样本数$m=m_0+m_1$，第i类样本在特征空间$\mathbb{F}$中的均衡为 $${\mu }_i^{\varphi }=\frac{1}{m}\sum _{x\in X_i}\varphi (x)$$ 两个散度矩阵分别为 $${S\text{S}S}_b^{\varphi }=({\mu }_1^{\varphi }-{\mu }_o^{\varphi })({\mu }_1^{\varphi }-{\mu }_o^{\varphi }{)}^T\text{(μ1ϕ−μoϕ)(μ1ϕ−μoϕ)T}({\mu }_1^{\varphi }-{\mu }_o^{\varphi })({\mu }_1^{\varphi }-{\mu }_o^{\varphi }{)}^T$$

$${S\text{S}S}_w^{\varphi }=\sum _{i=0}^1\sum _{x\in X_i}(\varphi (x)-{\mu }_i^{\varphi })(\varphi (x)-{\mu }_i^{\varphi }{)}^T$$

函数$h(x\text{x}x)$可写为 $$h(x\text{x}x)=\sum _{i=1}^m{\alpha }_i\kappa (x,x_i\text{x,xi}x,x_i)$$ 可以得到 $$w\text{w}w=\sum _{i=1}^m{\alpha }_i\varphi (x_i\text{xi}{x}_i)$$ 令$K\in {\mathbb{R}}^{m\times m}$ 为核函数$\kappa$所对应的核矩阵，$(K{)}_{ij}=\kappa (x_i,x_j)$。令$1_i\in \{1,0{\}}^{m\times 1}$为第i类样本的指示向量。 $$\begin{gathered} {\hat{\mu }}_0=\frac{1}{m_0}K{1}_0\text{K10}K{1}_0 \\ {\hat{\mu }}_1=\frac{1}{m_1}K{1}_1\text{K11}K{1}_1 \\ M\text{M}M=({\hat{\mu }}_0-{\hat{\mu }}_1)({\hat{\mu }}_0-{\hat{\mu }}_1{)}^T \\ N=K{K}^T-\sum _{i=0}^1{m}_i{\hat{\mu }}_i{\hat{\mu }}_i^T \end{gathered}$$ 等价为 $$\underset{\alpha }{\max }J(\alpha )=\frac{{\alpha }^{T}M\alpha }{{\alpha }^{T}N\alpha }$$