软间隔与正则化

在现实中，训练数据集不一定能用超平面完全划分开，提出允许支持向量机在一些样本上出错，引入“软间隔”的概念。

要求所有样本都必须划分正确，称为“硬间隔”，软间隔允许某些样本不满足约束

$y_i(w^T x_i +b) \ge 1 \tag{1}$yi​(wTxi​+b)≥1(1)

当然，在最大化间隔的同时，不满足约束的样本尽可能少，于是优化目标可写为：

$min_{w,b} \frac{1}{2}||w||^2 + C\sum_{i=1}^m l_{0/1} (y_i(w^T x_i+b)-1) \tag{2}$minw,b​21​∣∣w∣∣2+Ci=1∑m​l0/1​(yi​(wTxi​+b)−1)(2)

其中 $C \gt 0$C>0 是一个常数，$l_{0/1}$l0/1​ 是0/1损失函数，即

KaTeX parse error: Got function '\newline' with no arguments as argument to '\begin{array}' at position 1: \̲n̲e̲w̲l̲i̲n̲e̲

当C无穷大时，公式（2）迫使所有样板满足公式（1），当C取有限值时，公式（2）允许一些样本不满足约束。

然而 $l_{0/1}$l0/1​ 非凸、非连续，数学性质不好，使得公式（2）不易求解，于是想到利用一些函数替代 $l_{0/1}$l0/1​ ，称为替代函数

若采用hinge损失，公式（2）变为

$min_{w,b} \frac{1}{2}||w||^2 + C\sum_{i=1}^m max (0,1 - y_i(w^T x_i+b)-1) \tag{4}$minw,b​21​∣∣w∣∣2+Ci=1∑m​max(0,1−yi​(wTxi​+b)−1)(4)

引入“松弛变量” $\xi_i \ge 0$ξi​≥0, 将公式（4）重写成
$min_{w,b} \frac{1}{2}||w||^2 + C\sum_{i=1}^m \xi_i \tag{5}$minw,b​21​∣∣w∣∣2+Ci=1∑m​ξi​(5)
$s.t. y_i(w^T x_i +b) \ge 1-\xi_i$s.t.yi​(wTxi​+b)≥1−ξi​

$\xi_i \ge 0$ξi​≥0

这就是软间隔支持向量机。

显然，公式（5）中每个样本对应一个松弛变量，用以表征该样本不满足约束公式（1）的程度。这是一个二次规划问题，可以通过拉格朗日乘子法求解，最终得到其对偶问题是

$max_{\alpha} \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^Tx_j \tag{6}$maxα​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​(6)

$s.t. \quad \sum_{i=1}^m \alpha_i y_i =0 , \quad 0 \le \alpha_i \le C$s.t.i=1∑m​αi​yi​=0,0≤αi​≤C

上式相比硬间隔对偶问题的唯一差别是对偶变量的约束不同，前者是 $0 \le \alpha_i \le C$0≤αi​≤C,后者是 $0 \le \alpha_i$0≤αi​。但公式（6）也可以用SMO算法求解。

正则化

不管替代损失函数用哪个，模型都有一个共同的特点：优化目标的第一项用来描述划分超平面的“间隔”大小，另一项 $\sum_{i=1}^m l(f(x_i), y_i)$∑i=1m​l(f(xi​),yi​) 用来表述训练集上的误差，写作更一般的形式：

$min_f \Omega(f) + C\sum_{i=1}^m l(f(x_i),y_i) \tag{7}$minf​Ω(f)+Ci=1∑m​l(f(xi​),yi​)(7)

其中 $\Omega(f)$Ω(f) 称为结构风险，用于描述模型 f 的某些性质，第二项 $C\sum_{i=1}^m l(f(x_i),y_i)$C∑i=1m​l(f(xi​),yi​) 称为经验风险，用于描述模型与训练数据的契合程度。C对二者进行折中。公式（7）称为“正则化”问题，$\Omega(f)$Ω(f) 称为正则化项，C称为正则化常数。$L_p$Lp​ 范数是常用的正则化项，其中 $L_2$L2​ 范数倾向于 w 的分量取值尽量均衡，即非零分量个数尽量稠密，$L_1$L1​ 和$L_0$L0​ 范数倾向于w的分量尽量稀疏，即非零分量个数尽量少。

内容太多，下面直接写结论

用于回归问题叫支持向量回归（SVR），SVR支持向量也是训练样本的一部分，即解具有稀疏性。

若不考虑偏移项b, 无论是SVM还是SVR，学得的模型总能表示成核函数的线性组合（（二）的公式（3））。基于核函数的方法叫做核方法，通过“核化”将线性学习器拓展为非线性学习器。

SVM针对的是二分类任务，进行拓展后可多分类。

核函数的选择没理论指导。

总评

SVM算法的主要优点有：

1. 解决高维特征的分类问题和回归问题很有效,在特征维度大于样本数时依然有很好的效果。

2. 仅仅使用一部分支持向量来做超平面的决策，无需依赖全部数据。

3. 有大量的核函数可以使用，从而可以很灵活的来解决各种非线性的分类回归问题。

4)样本量不是海量数据的时候，分类准确率高，泛化能力强。

SVM算法的主要缺点有：

1. 如果特征维度远远大于样本数，则SVM表现一般。

2. SVM在样本量非常大，核函数映射维度非常高时，计算量过大，不太适合使用。

3）非线性问题的核函数的选择没有通用标准，难以选择一个合适的核函数。

4）SVM对缺失数据敏感。

参考

周志华《机器学习》

https://www.cnblogs.com/pinard/p/6103615.html

https://www.cnblogs.com/pinard/p/6113120.html

李航《统计学习方法》