学习笔记： 机器学习经典算法-线性SVM（LinearSVM）

1、不适定问题

在解决分类问题时，通常根据算法模型在样本的特征空间内生成的决策边界来为样本分类提供依据。但对于许多现实的样本集来说，在其特征空间内可能会存许多满足分类要求的决策边界，也就是决策边界不唯一。

在逻辑回归中，求解样本特征空间的决策边界是通过定义一个概率函数$\sigma(t)$，根据概率函数建模形成了一个损失函数，再通过最小化损失函数来求解一条符合条件的决策边界，由于损失函数完全由采样数据所决定，所以求解的决策边界的不一定是面对实际情况的最优决策边界，也就是决策边界的泛化能力可能不足。

2、支撑向量机对不适定问题的解决方案

对于算法模型来说，最重要的问题是模型的泛化能力。对于分类模型来说也对应决策边界的泛化能力。一个好的决策边界，应该能够充分地分割样本的特征空间。所以就有对于这样一个 “好的决策边界” 定义为距样本空间内各类别簇的分布边缘都尽可能远，换而言之就是各类别簇距 decision_boundary 最近的一些点离 decision_boundary 最远。

不同于 逻辑回归 建模在于求一条符合条件的 decision_boundar ，支撑向量机（SVM，Support Vector Machine） 的主要思想是 寻找一个最优决策边界 ,该决策边界拥有充分的泛化能力，不仅能很好的划分训练数据，同时还能很好地应对实际要面对的数据。在SVM的数学理论里该最优决策边界定义为距离样本空间内各类别簇尽可能远的决策边界， 也就是 距离所有类别簇的最近样本最远的决策边界，这些距离决策边界最近的类别簇样本称为 支撑向量，它们最终决定了SVM算法 寻找的最优决策边界。

SVM 线性分类器类别

• Hard Margin SVM ，基于 SVM思想 的最原始分类器。
• Soft Margin SVM ，基于 Hard Margin SVM 的优化算法，添加了正则项。

3、Hard Margin SVM 的最优化问题

由于距离决策边界最近的类别簇样本，也就是 支撑向量 决定了最优决策边界。这个最优决策边界满足距离所有类别簇的最近样本最远。令支撑向量到决策边界的距离为 $d$,则有 SVM算法 在于最大化 $d$。首先根据解析几何，空间上任意点$x$ 到 决策边界所在超平面 $w^Tx + b = 0$ 的距离将描述为 $d = \frac {|w^Tx + b |}{\|w\|}$。

3.1 SVM 的约束条件

SVM 定义了支撑向量到决策边界的距离为 $d$，那么样本空间内任意样本点到决策边界的距离都将大于 $d$。同时决策边界应该从各样本簇中心划分样本空间，所以对于二分类 $y^{(i)} \in \{-1,1\}$，就有两个类别的样本到decision_boundary 的有向距离应满足：

• 对于边界上方的类别点，$\frac {w^Tx + b}{\|w\|} > d,\forall y^{(i)} = +1$
• 对于边界下方的类别点，$\frac {w^Tx + b}{\|w\|} < -d,\forall y^{(i)} = -1$
  
  联合变形为
  $$\left\{ \begin{array}{**lr**} \frac {w^Tx + b}{\|w\|d} >\ \ \ 1,\forall y^{(i)} = \ \ 1 \\ \frac {w^Tx + b}{\|w\|d} > -1,\forall y^{(i)} = -1 \end{array} \right.$$
  $\small {\bf 令\ \ \ } w_d = \frac {w}{\|w\|d},b_d = \frac {b}{\|w\|d}$ : $\small {\bf 得到 \ \ \ } \left\{ \begin{array}{**lr**} w_d^Tx + b_d >\ \ 1,\forall y^{(i)} = \ \ 1 \\ w_d^Tx + b_d < -1,\forall y^{(i)} = -1 \end{array} \right.$，

关于这变形后的直线 $w_d^T + b_d = \pm 1$ 的一些理解：

对于点法式描述的超平面解析方程式 $w^Tx + b = 0$ 中，常量 $b$ 与超平面距原点的实际偏移量$d$具如下关系 : $d = \frac {w^Tx_0}{\|w\|} = \frac {-b}{\|w\|}$，所以对空间内的超平面参考原点平移$+d$个单位后，解析方程式将描述为 $w^Tx + b - d\|w \| = 0 \rightarrow w^Tx + b = d\|w \|$。所以方程式 $w_d^T + b_d = \pm 1$ 本质描述了决策边界平移$\pm d$个单位后位于支撑向量上的两条平行直线。同时，对于原始的决策边界描述方程 $w^Tx + b = 0$，新方程 $w_d^Tx + b_d = 0$ 本质是原方程的线性缩放，描述的是同一个方程。所以对于最终的结果使用$w_d,b_d$来描述决策边界与使用$w ，b$等价。为了表述方便，再令$w = w_d, b = b_d$。

由于类别的识别标记被$\{-1,1\}$ 区分，结合$w = w_d, b = b_d$的换元，联合两描述式：
$$\left\{ \begin{array}{**lr**} w_d^Tx + b_d >\ \ 1,\forall y^{(i)} = \ \ 1 \\ w_d^Tx + b_d < -1,\forall y^{(i)} = -1 \end{array} \right. \rightarrow \left\{ \begin{array}{**lr**} w^Tx + b >\ \ 1,\forall y^{(i)} = \ \ 1 \\ w^Tx + b < -1,\forall y^{(i)} = -1 \end{array} \right. \rightarrow y^{(i)}(w^Tx + b) > 1$$
$\therefore$ SVM算法 搜索的最优决策边界到任意样本点的距离大于等于 $d$ 的关系就被描述为了 $y^{(i)}(w^Tx + b) > 1$；

3.2 SVM 的优化目标

SVM算法优化目标 即对于任意支撑向量，都有它到决策边界的距离$d$ 达到最大化，也即 $\max \frac {|w^Tx + b |}{\|w\|}$。 由于求得支撑向量上存在决策边界的偏移直线 $w^Tx + b = \pm 1$，所以将任意分类下的支撑向量代入直线再取绝对值的结果都是 $|w^Tx + b| = 1$,因此优化目标函数描述为
$$\max \frac {|w^Tx + b |}{\|w\|} \rightarrow \max \frac {1}{\|w\|} \rightarrow \min (\|w\|)$$
为了便于获取导数，对于取模最小值的函数进一步转换为 $\min (\|w\|) \rightarrow \min (\frac {1}{2}\|w\|^2)$

综上， Hard Margin SVM 搜索线性决策边界的最优化目标为：
基于约束 $\mathrm{s.t.} \ \ y^{(i)}(w^Tx + b) > 1$ 下的 $\min (\frac {1}{2}\|w\|^2)$ 求极值问题。

4、Soft Margin SVM 与 SVM 正则化

Hard Margin SVM 算法搜索的决策边界由于极度依赖两个类别内的支撑向量，所以就会很容易受到错误样本(极端样本，这类样本并不能代表一般情况)的影响。导致生成不理想的线性决策边界，也就是出现过拟合问题。所以通常只适用于具有强线性可分且采样良好数据集（意味着没有outlier出现）。

考虑现实生产情况下采集到样本往往都会出现 outlier 问题，因此Hard Margin SVM算法的易受极端样本影响的拟合 缺点 需要被进一步改进，来提高的泛化能力。
在 Hard Margin SVM 算法中，优化目标被条件 $\mathrm{s.t.} \ \ y^{(i)}(w^Tx + b) > 1$ 所约束，该约束本质是要求决策边界所在 $\pm d$ 范围的 Margin 区域内不能存在任何样本点。所以如果对这个条件进行宽松，缩小Margin Area 的范围，就可以适当地提高 SVM 模型的容错能力。因此，分别对数据集的每个样本点都添加上容错空间 $\zeta_i，\zeta_i \ge 0$，就有得到了基于 Hard Margin SVM 方法改进的 Soft Margin SVM 。

Soft Margin SVM 的约束条件为： $\mathrm{s.t.} \ \ y^{(i)}(w^Tx + b) > 1 - \zeta_i$ .

需要注意如果当 $\zeta$取无穷大，这个约束条件无论$w,b$取任意值都会永远成立。所以为了使添加到约束条件内的 宽松量 $\zeta$ 不会使约束条件失效，$\zeta$本身也需要被约束。它被添加到 Hard Margin SVM 的优化函数里进行最小化约束。

Soft Margin SVM 的优化目标 :$\min (\frac {1}{2}\|w\|^2 + \sum_{i=1}^{m}{\zeta_i})$

Soft Margin SVM 的正则化

• L1正则化 ： $\min (\frac {1}{2}\|w\|^2 + C\sum_{i=1}^{m}{\zeta_i})$ ，常量$C(C \ge0)$ 衡量了搜索决策边界时考虑容错的权值(也叫惩罚因子)。如果 $C \to +\infty$，最小化损失函数时$\zeta_i$只能趋于0，意味着要求模型的容错率最低，这也说明了 Hard Margin SVM 是非常严格的分类器，几乎没有容错空间。
• L2正则化 ： $\min (\frac {1}{2}\|w\|^2 + C\sum_{i=1}^{m}{\zeta_i^2} )$

  

  容错率权值$C$ 越大(左图)，生成的决策平面容错率越低；容错率权值$C$ 越小(右图)，生成的决策平面容错率越高，模型泛化能力提高；

=

5、scikit-learn 框架下的线性SVM

5.1 SVM 的特征归一化

SVM 算法的决策边界依赖于最大化 支撑向量到它的距离 $d$ ，如果特征量纲不一样，在具有大方差的特征方向上计算的距离 $d$ 将掩盖其它特征方向上距离，从而主导决策边界的生成。所以在实际应用时需要首先进行 数据的特征归一化。

5.2 sklearn 下的调用线性SVM

### Prepare data
import numpy as np
from sklearn import datasets
iris = datasets.load_iris()
from sklearn.model_selection import train_test_split
Train_X,Test_X,Train_Y,Test_Y = train_test_split(iris.data[iris.target < 2,:2],iris.target[iris.target < 2],test_size= 0.2,random_state=666)
### Scale data
from sklearn.preprocessing import StandardScaler
standardScaler = StandardScaler()
standardScaler.fit(Train_X)
Train_X_std = standardScaler.transform(Train_X)
Test_X_std  = standardScaler.transform( Test_X)
### SVM classifier
from sklearn.svm import LinearSVC  ### SVC-support_vector_cassifier, SVM分类器
svc = LinearSVC(C = 1e9) ### 减小模型的容错空间，使得正则化的权值C 尽可能大,该模型结果接近 Hard Margin SVM 
svc.fit(Train_X_std,Train_Y)

#### 获取决策边界所在方程 w^Tx+b =0
svc.coef_       ### w
svc.intercept_  ### b

        

          
        
        
        

          

          AI 代码解读
        
      
      

6、应用线性SVM求解非线性分类

非线性决策面的拟合本质是数据集添加多项式后在升维的特征空间内变得线性可分的结果。

### Prepare data
import numpy as np
from sklearn import datasets
X,y = datasets.make_moons(noise= 0.15,random_state=666)   ### 使用 datasets 生成含噪音的指定形状的测试数据

### show sample distribution
import matplotlib.pyplot as plt
plt.scatter(X[y == 0,0],X[y == 0,1])
plt.scatter(X[y == 1,0],X[y == 1,1])



### Polynomial Features
from sklearn.preprocessing import PolynomialFeatures,StandardScaler
from sklearn.svm import LinearSVC
from sklearn.pipeline import Pipeline
def PolynomialSVC(degree,C = 1.0):
    return Pipeline([
        ("Poly",PolynomialFeatures(degree = degree)),
        ("std_scaler",StandardScaler()),
        ("LinearSVC",LinearSVC(C = C))
    ])

poly_SVC = PolynomialSVC(degree = 1)
poly_SVC.fit(X,y)


### draw decision boundary
def plot_decision_boundary(model, axis):
    x0, x1 = np.meshgrid(
        np.linspace(axis[0], axis[1], int((axis[1]-axis[0])*100)).reshape(-1, 1),
        np.linspace(axis[2], axis[3], int((axis[3]-axis[2])*100)).reshape(-1, 1),
    )
    X_new = np.c_[x0.ravel(), x1.ravel()]
    y_predict = model.predict(X_new)
    zz = y_predict.reshape(x0.shape)

    from matplotlib.colors import ListedColormap
    custom_cmap = ListedColormap(['#EF9A9A','#FFF59D','#90CAF9'])
    plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)


plot_decision_boundary(poly_SVC, axis=[-1.5, 2.5, -1.0, 1.5])
plt.scatter(X[y==0,0], X[y==0,1])
plt.scatter(X[y==1,0], X[y==1,1])
plt.show()

        

          
        
        
        

          

          AI 代码解读
        
      
      

7、应用线性SVM求解回归问题

回归问题的本质在于找到一条直线或曲线能够最优地拟合 数据点，不同的回归算法差异主要是拟合策略的不同，如线性回归算法的拟合策略是使得找到的拟合直线与所有数据点的误差最小化($\min MSE$)。

SVM回归 的拟合策略与寻找最优决策边界的过程类似，它的回归策略提出对于一条回归直线，在这条直线上下偏移一个人为指定 $\epsilon$ 大小范围的 Margin Area 里期望包含尽可能多的数据点，这样的一条直线就是一条较好的拟合直线。
详细的SVM推导过程可参考博客 回归SVM的优化目标。

7.2 sklearn 下的SVM Regressor（SVR）

### Prepare data
import numpy as np
from sklearn import datasets
boston = datasets.load_boston()
from sklearn.model_selection import train_test_split
Train_X,Test_X,Train_Y,Test_Y = train_test_split(boston.data,boston.target,test_size= 0.2,random_state=666)

### Polynomial Features
from sklearn.preprocessing import PolynomialFeatures,StandardScaler
from sklearn.svm import LinearSVR
from sklearn.pipeline import Pipeline
def standardLinearSVR(epsilon = 0.1):
    return Pipeline([
        ("std_scaler",StandardScaler()),
        ("LinearSVR",LinearSVR(epsilon = epsilon))
    ])

SVR = standardLinearSVR(epsilon = .5)
SVR.fit(Train_X,Train_Y)
SVR.score(Test_X,Test_Y)

        

          
        
        
        

          

          AI 代码解读