机器学习-3.硬间隔线性支持向量机

硬间隔线性支持向量机

支持向量机(Support Vector Machine, SVM)是 \(Cortes\)和\(Vapnik\)于1995年在 \(Machine \space Learning\) 期刊上提出的分类模型，在自然语言处理、计算机视觉以及生物信息中有着重要的应用。支持向量机的模型形式与感知机相同，但有别于感知机模型的是，支持向量机学习通过添加约束条件，能够得到最优的分离超平面。支持向量机学习的目标是找到一个线性超平面，能够最大程度地分离训练数据集中不同类别的数据点，并且在分离过程中最大化间隔，即数据点与决策边界之间的距离最大化。
根据处理的问题不同，支持向量机可大致分为硬间隔线性支持向量机、软间隔线性支持向量机，非线性支持向量机。本节主要介绍二分类问题下的硬间隔线性支持向量机。

基本思想

我们在之前已经介绍了感知机模型，它的模型形式是：

\[f(x) = sign(w^Tx+b)\]

其中，\(x \in \mathbb{R}^n; w \in \mathbb{R}^n, b \in \mathbb{R}\) 为模型参数。通过设置初始参数，利用梯度下降算法，我们可以得到模型参数\(\hat{w},\hat{b}\). 当我们设置不同的初始参数时，我们会得到不同的模型参数，即不同的分离超平面。现假设在二维情形下，我们得到了如图1所示的两个分离超平面\(S_1,S_2\)。

Image1: 感知机中分离超平面

在感知机学习中，超平面\(S_1\)与\(S_2\)均可以将训练数据集完全正确分类，这两个分离超平面并没有优劣可分，实际上，感知机学习得到的分离超平面为无数个。现在的问题是：感知机学习得到的众多分离超平面中，哪一个分离超平面是最优的？为了回答这个问题，我们先来思考一下图1中分离超平面\(S_1\)与\(S_2\)哪一个更好。相信大多数读者在直觉上都会认为分离超平面\(S_2\)要优于\(S_1\)，这个结论是正确的。通过进一步地分析，我们可以发现，训练数据集中的实例点到分离超平面\(S_1\)的最小距离要大于其到分离超平面\(S_2\)的最小距离，这使得分离超平面\(S_1\)的泛化能力要弱于分离超平面\(S_2\)，一些轻微的噪声扰动便有可能使得实例点越过分离超平面\(S_1\)，造成模型分类错误，如图1中的红色实例点所示，然而由于实例点距离分离超平面\(S_2\)的距离相对较远，噪声扰动并不容易使得实例点越过超平面\(S_2\)。因此，我们认为分离超平面\(S_2\)要优于分离超平面\(S_1\)。
硬间隔支持向量机的基本思想便来源于以上的思考，其基本思想为：当训练数据集线性可分时，在特征空间中寻找一个超平面，其能够将训练数据中的实例点完全正确分类，同时最大程度远离训练数据中的示例点。

模型

输入

输入空间: \(\mathcal{X} \in \mathbb{R}^n\).
输入实例: \(x = \begin{bmatrix} x^{(1)},x^{(2)},\dots,x^{(n)} \\ \end{bmatrix}^T \in \mathcal{X}\).

其中，输入空间\(\mathcal{X}\)为\(n\)维实数空间的子集，输入实例\(x\)为\(n\)维特征向量。

输出
由于我们只考虑二分类问题，因此实例点的类别只有正类与负类两种。

输出空间: \(\mathcal{Y} = \{ -1,+1 \}\)
输出实例: \(y \in \mathcal{Y}\).

其中，输出空间\(\mathcal{Y}\)为只包含+1，-1两个元素的集合，+1与-1分别代表二分类问题中的正类与负类。输出实例\(y\)代表相对应的输出实例\(x\)的类别。

数据集
支持向量机的训练数据集\(T_{train}\)为：

\[T_{train}=\{ (x_1,y_1),(x_2,y_2),\dots,(x_N,y_N) \}\]

其中，\(x_i \in \mathcal{X}=\mathbb{R}^{n},y_i \in \mathcal{Y}=\{+1,-1\},i=1,2,\dots,N\)，\(N\)表示训练数据的样本容量。需要注意的是，硬间隔线性支持向量机模型的前提假设为训练数据集\(T_{train}\)是线性可分的。

模型
支持向量机的模型形式与感知机相同，其模型形式为：

\[f(x) = sign(w^{T}x+b)\]

其中，\(w\)和\(b\)为感知机模型的参数，\(w \in \mathbb{R}^{n}\)为权重向量，\(b \in \mathbb{R}\)为偏置。\(sign(\cdot)\)为符号函数。硬间隔线性支持向量机为线性分类模型，属于判别模型。

假设空间
硬间隔线性支持向量机模型的假设空间为：

\[\mathcal{H} = \{f \vert f(x)=w^{T}x+b \}\]

与感知机模型相同，硬间隔线性支持向量机模型的假设空间实际上是特征空间中所有超平面的集合。

参数空间
令\(\theta=(w,b)\)，则模型的假设空间\(\mathcal{H}\)等价于参数空间\(\Theta\)：

\[\Theta=\{ \theta \vert \theta \in \mathbb{R}^{n+1} \}\]

策略

我们的目标是找到所有分离超平面中最优的一个超平面。首先，假设分离超平面为\(S=\{x \vert w^T x + b = 0\}\)，则实例点\(x_i\)到超平面\(S\)的距离为：

\[d(S,x_i)=\frac{|w^Tx_i+b|}{||w||}\]

由于硬间隔线性支持向量机假设训练数据集是线性可分的，因此分离超平面\(S\)能够将实例点完全正确分类。因此，当 \(w^Tx_i+b > 0\)时，有\(y_i=+1\)；当\(w^Tx_i+b<0\)时，有\(y_i=-1\)。则\(d(S,x_i)\)同样可以表示为：

\[\gamma_i=\frac{y_i(w^Tx_i+b)}{||w||}\]

我们称\(\gamma_i\)为实例点\(x_i\)到超平面\(S\)的几何间隔。
我们希望能够找到与训练数据集中的实例点距离最大的超平面，记 \(margin(T,S)\) 表示数据集\(T\)中的实例点到超平面\(S\)的最小距离：

\[margin(T_{train},S)=\min_{i=1,\dots,N} d(S,x_i)=\min_{i=1,\dots,N} \gamma_i=\min_{i=1,\dots,N} \frac{y_i(w^Tx_i+b)}{||w||}\]

我们使用 \(margin(T_{train},S)\) 来衡量训练数据集到超平面的距离，这种距离也称为\(hard-margin\)，即硬间隔。由于训练数据集\(T_{train}\)是给定的，因此 \(margin(T_{train},S)\) 实际上是由超平面的参数\(w,b\)决定的，不同的分离超平面对应着不同的\(margin\)距离，我们希望能够在所有分离超平面中找到与训练数据集距离最远的超平面，这个问题可以被描述为：

\[\max_{w,b} margin(T_{train},S)=\max_{w,b} \min_{i=1,\dots,N} \frac{y_i(w^Tx_i+b)}{||w||}\]

综上所述，寻找最优分离超平面的优化问题可以描述为最小几何间隔最大化问题(1)：

\[\begin{equation} \begin{split} & \max_{w,b} \min_{i=1,2,\dots,N} \quad \frac{1}{||w||}y_i(w^Tx_i+b) \\ & \space s.t. \quad y_i(w^Tx_i+b) > 0, \quad i=1,2,\dots,N\\ \end{split} \end{equation}\]

其中称\(y_i(w^Tx_i+b)\)为实例点\(x_i\)到超平面\(S\)的函数间隔；约束条件\(y_i(w^Tx_i+b) > 0\)保证了该优化问题的可行解集为能够将训练数据集正确分类的超平面的集合。确定最优分离超平面需要找到最小几何间隔对应的实例点，这些实例点被称为支持向量。
下面我们来对该优化问题做一些简化，通过分析我们可以得到：

\[\exists r > 0, \space s.t. \space \min_{i=1,\dots,N} y_i(w^Tx_i+b)=r\]

由于我们没有对\(w\)的长度进行限制，则同一个超平面可能对应这不同的参数值\(w,b\)，例如超平面\(S_1=\{x \vert w^Tx+b=0\}\)与超平面\(S_2=\{x \vert (2w)^Tx+(2b)=0\}\)在特征空间中表示同一个超平面。这样会造成，即使是同一个分离超平面，不同的参数值\(w,b\)会对应不同的\(r\)值。我们想要优化问题能够得到唯一一组确定的参数值\(w,b\)，我们可以给定\(w\)的模长，也可以固定\(r\)值，为了简化优化问题，我们固定\(r=1\)，此时优化问题(1)的约束条件可以转化为：

\[\min_{i=1,\dots,N} y_i(w^Tx_i+b)=1 \Leftrightarrow y_i(w^Tx_i+b) \ge 1, i=1,2,\dots,N\]

优化问题(1)中的目标函数可以转化为：

\[\max_{w,b} \min_{i=1,\dots,N} \frac{1}{||w||}y_i(w^Tx_i+b)=\max_{w,b}\frac{1}{||w||} \min_{i=1,\dots,N} y_i(w^Tx_i+b)=\max_{w,b} \frac{1}{||w||}\]

再简最大化问题转化为常见的最小化问题：

\[\max_{w,b} \frac{1}{||w||} \Leftrightarrow \min_{w,b} ||w|| \Leftrightarrow \min_{w,b} \frac{1}{2}w^Tw\]

综上所述，优化问题(1)可以转化为以下的优化问题(2)：

\[\begin{equation} \begin{split} & \min_{w,b} \quad \frac{1}{2}w^Tw \\ & \space s.t. \quad 1-y_i(w^Tx_i+b) \leq 0, \quad i=1,2,\dots,N \end{split} \end{equation}\]

通过求解优化问题(2)，我们便可以得到最优的分离超平面参数\((w^{*},b^{*})\)。可以证明在训练数据集线性可分的条件下，通过最小间隔最大化问题的求解，最优的分离超平面是唯一的。这部分证明将放在附录，有兴趣的读者可自行阅读。

Image2: 最优分离超平面

算法

通过前文的推导，我们得到的优化问题为问题(2)：

\[\begin{align*} & \min_{w,b} \frac{1}{2}w^Tw \\ & \space s.t. \space 1-y_i(w^Tx_i+b) \leq 0, \quad i=1,2,\dots,N \\ \end{align*}\]

该优化问题为凸二次规划问题，有\(N\)个约束条件。首先写出优化问题(2)的拉格朗日函数：

\[L(w,b,\lambda)=\frac{1}{2}w^Tw+\sum_{i=1}^{N}\lambda_i \left[ 1-y_i(w^Tx_i+b) \right]\]

\[\lambda = \begin{bmatrix} \lambda_1,\lambda_2,\dots,\lambda_N \end{bmatrix}^T,\lambda_i \ge 0, i=1,2,\dots,N\]

则优化问题(2)的无约束形式(3)为：

\[\begin{equation} \begin{split} & \min_{w,b} \max_{\lambda} \quad L(w,b,\lambda) \\ & \space s.t. \quad \lambda_i \ge 0, \quad i=1,2,\dots,N \\ \end{split} \end{equation}\]

则优化问题(2)的对偶问题(4)为：

\[\begin{equation} \begin{split} & \max_{\lambda} \min_{w,b} \quad L(w,b,\lambda) \\ & \space s.t. \quad \lambda_i \ge 0, \quad i=1,2,\dots,N \end{split} \end{equation}\]

因为原始问题(2)为凸二次规划问题，其满足强对偶关系，即：

\[\min_{w,b} \max_{\lambda} L(w,b,\lambda)=\max_{\lambda} \max_{w,b} L(w,b,\lambda)\]

首先来解决内部极大化问题：

\[\max_{w,b} L(w,b,\lambda)=\frac{1}{2}w^Tw+\sum_{i=1}^{N}\lambda_i \left[ 1-y_i(w^Tx_i+b) \right]\]

由费马定理可得：

\[\left \{ \begin{array}{lr} \frac{\partial L(w,b,\lambda)}{\partial w}=0 \Rightarrow w = \sum_{i=1}^{N}\lambda_{i}y_ix_i \\ \frac{\partial L(w,b,\lambda)}{\partial b}=0 \Rightarrow \sum_{i=1}^{N}\lambda_iy_i=0 \end{array} \right.\]

将其代入拉格朗日函数\(L(w,b,\lambda)\)得：

\[\begin{align*} L(w,b,\lambda) &= \frac{1}{2} \left( \sum_{i=1}^{N}\lambda_{i}y_ix_i \right)^{T}\left( \sum_{i=1}^{N}\lambda_{i}y_ix_i \right)-\sum_{i=1}^{N}\lambda_iy_i \left( \sum_{i=1}^{N}\lambda_{i}y_ix_i \right)^{T}x_i-b\sum_{i=1}^{N}\lambda_iy_i+\sum_{i=1}^{N}\lambda_i \\ &=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i \lambda_j y_iy_j (x_i^{T}x_j)-\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i \lambda_j y_iy_j (x_i^{T}x_j)+\sum_{i=1}^{N}\lambda_i \\ &= -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i \lambda_j y_iy_j (x_i^{T}x_j)+\sum_{i=1}^{N}\lambda_i \\ \end{align*}\]

则对偶问题(4)可以化为以下优化问题(5)：

\[\begin{equation} \begin{split} \min_{\lambda} \quad & \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_i \lambda_j y_iy_j (x_i^{T}x_j)-\sum_{i=1}^{N}\lambda_i \\ s.t. \quad & \lambda_i \ge 0, \quad i=1,2,\space,N \\ & \sum_{i=1}^{N}\lambda_i y_i=0 \end{split} \end{equation}\]

记 \(w^{*},b^{*}\) 为原始问题(2)的最优解，\(\lambda^{*}\) 为对偶问题(4)的最优解，其同时也是优化问题(5)的最优解。根据定理：原始问题及其对偶问题具备强对偶关系是原始问题与其对偶问题满足KKT条件的充要条件可知：

\[KKT条件: \left \{ \begin{array}{l} 1-y_i(w^{*} \cdot x_i+b^{*}) \leq 0 \\ \\ \lambda_i^{*}(1-y_i(w^{*} \cdot x_i+b^{*}))=0 \\ \\ \frac{\partial L(w,b,\lambda^{*})}{\partial w} |_{w=w^{*}}=0 \Rightarrow w^{*}=\sum_{i=1}^{N}\lambda^{*}_{i}y_ix_i \\ \\ \frac{\partial L(w,b,\lambda^{*})}{\partial b} |_{b=b^{*}}=0 \Rightarrow \sum_{i=1}^{N}\lambda^{*}_{i}y_i=0 \\ \\ \lambda^{*} \ge 0 \\ \end{array} \right.\]

其中，\(i=1,2,\dots,N\).以上关于凸二次规划、对偶关系、KKT条件等最优化知识会在附录中介绍，这里不多家阐述。
由\(KKT\)条件得到 \(w^{*}=\sum_{i=1}^{N}\lambda^{*}_{i}y_ix_i\)，现在来思考\(b^{*}\)如何用\(\lambda^{*}\)来表示。由于 \(\lambda_i^{*}(1-y_i(w^{*} \cdot x_i+b^{*}))=0\)，若 \(y_i(w^{*} \cdot x_i+b^{*}) > 1\)，则 \(\lambda_i^{*}=0\)，即在图2中位于间隔边界\(H_1,H_2\)两侧的实例点\(x_i\)对确定最优超平面\(S\)的参数\(w^{*},b^{*}\)不起作用；若 \(y_i(w^{*} \cdot x_i+b^{*}) = 1\)，则\(\lambda_i^{*}\)不一定为0，即在图2中位于间隔边界上的实例点\(x_i\)，也就是支持向量，对确定最优超平面\(S\)的参数\(w^{*},b^{*}\)起作用。此时可以解得：

\[b^{*}=y_j-\sum_{i=1}^{N}\lambda_i^{*}y_i(x_i^{T} \cdot x_j)\]

其中实例点\(x_j\)为某一个支持向量，由于\(b^{*}\)的值是固定的，因此代入不同的支持向量，得到的\(b^{*}\)的值是相同的，在实际计算中，我们一般在求解优化问题(5)得到的\(\lambda^{*}\)中选择一个正值分量\(\lambda_j > 0\)，使用其所对应的支持向量\(x_j\)来求解\(b^{*}\)。

硬间隔支持向量机算法

输入：训练数据集\(T_{train}=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}\)，其中\(x_i \in \mathcal{X}=\mathbb{R}^{n}，y \in \mathcal{Y}=\{-1,+1\},i=1,2,\dots,N\).
输出：最优分离超平面的参数\(w^{*},b^{*}\)，以及相应的分类模型\(f(x)=sign(w^{*} \cdot x+b^{*})\).
(1) 基于训练数据集\(T_{train}\)构造凸二次规划问题(6)：

解得该优化问题的最优解为：\(\lambda^{*}=\begin{bmatrix} \lambda_1^{*},\lambda_2^{*},\dots,\lambda_N^{*} \\ \end{bmatrix}^{T}\)

(2) 在最优解\(\lambda^{*}\)中选择一个正值分量\(\lambda_j > 0\)，取出其下标\(j\)对应的数据\((x_j,y_j)\)，基于\(KKT\)条件求解最优超平面的参数\(w^{*},b^{*}\)：

\[w^{*}=\sum_{i=1}^{N}\lambda_i^{*}y_ix_i\quad b^{*}=y_j-\sum_{i=1}^{N}\lambda_i^{*}y_i(x_i^{T} \cdot x_j)\]

(3) 得到相应的分类模型：

\[f(x) = sign(w^{*} \cdot x + b^{*})\]

基于Python的算法实现

导入所需要的Python包：

import math
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import cvxopt
from sklearn.utils import shuffle
from sklearn.svm import LinearSVC

基于numpy,pandas,cvxopt等的算法实现

首先我们来生成我们的训练数据集，为了便于进行可视化，我们依然选择在二维情况下构建数据集。由于硬间隔线性支持向量机假设训练数据集是线性可分的，我利用均匀分布在区域\(S_{p}=\{ (x_1,x_2) \vert x_1 \in (1,2), x_2 \in (3,4)\}\)产生了30个正类的实例点，在区域\(S_{n}= \{ (x_1,x_2) \vert x_1 \in (3,4), x_2 \in (1,2)\}\)产生了20个负类的实例点。以下是数据生成的代码：

# data generation
np.random.seed(520)
def data_generation(n,basepoint,ylabel):
    x1 = np.random.random((n,))+np.array([basepoint[0]]*n)
    x2 = np.random.random((n,))+np.array([basepoint[1]]*n)
    y = np.array([ylabel]*n)
    data = pd.DataFrame({"x1":x1,"x2":x2,"y":y})
    return data

# positive data
positivedata = data_generation(n=30,basepoint=(1,3),ylabel=1)
# negative data
negativedata = data_generation(n=20,basepoint=(3,1),ylabel=-1)
# train data
train_data = pd.concat([positivedata,negativedata])
train_data = shuffle(train_data)
train_data.index = range(train_data.shape[0])
train_data.head(5)

这50个实例点构成训练数据集，使用以下代码画出训练数据的散点图:

# train data scatter plot
plt.scatter(x=positivedata["x1"],y=positivedata["x2"],marker="o",c="green",label="positive data")
plt.scatter(x=negativedata["x1"],y=negativedata["x2"],marker="x",c="red",label="negative data")
plt.xlabel("x1")
plt.ylabel("x2")
plt.xlim((0,5))
plt.ylim((0,5))
plt.xticks(np.arange(0,5,0.5))
plt.yticks(np.arange(0,5,0.5))
plt.legend()

图3为训练数据集的可视化结果：

Image3: 训练数据集

从图3中可以很容易看出，训练数据集是线性可分的，满足硬间隔线性支持向量机的前提条件。下面我们来利用硬间隔线性支持向量机算法来求解最优超平面的参数\(w^{*},b^{*}\).
为了使用Python的cvxopt包来求救凸二次规划问题(6)，需要将问题(6)转化为矩阵形式，记：

\[\lambda = \begin{bmatrix} \lambda_1 \\ \lambda_2 \\ \vdots \\ \lambda_N \\ \end{bmatrix},\quad y = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_N \\ \end{bmatrix},\quad x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_N \\ \end{bmatrix}\]

则：

\[x \odot y = \begin{bmatrix} x_1y_1 \\ x_2y_2 \\ \vdots \\ x_Ny_N \\ \end{bmatrix},\qquad Gram(x \odot y) = \begin{bmatrix} (x_1y_1)^{T}(x_1y_1) & (x_1y_1)^{T}(x_2y_2) & \dots & (x_1y_1)^{T}(x_Ny_N) \\ (x_2y_2)^{T}(x_1y_1) & (x_2y_2)^{T}(x_2y_2) & \dots & (x_2y_2)^{T}(x_Ny_N) \\ \vdots & \vdots & & \vdots \\ (x_Ny_N)^{T}(x_1y_1) & (x_Ny_N)^{T}(x_2y_2) & \dots & (x_Ny_N)^{T}(x_Ny_N) \\ \end{bmatrix}\]

设：

\[P=Gram(x \odot y), \quad q=-1_{N}=\begin{bmatrix} -1 \\ -1 \\ \vdots \\ -1 \end{bmatrix}_{N \times 1}, \quad G = -I_{N}=\begin{bmatrix} -1 & 0 & \dots & 0 \\ 0 & -1 & \dots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \dots & -1 \\ \end{bmatrix}_{N \times N}\]

\[h = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix}_{N \times 1}, \quad A = y^{T}, \quad b=0\]

则凸二次规划问题(6)的矩阵形式为(7)：

\[\begin{equation} \begin{split} \min_{\lambda} \quad & \frac{1}{2} \lambda^{T}P\lambda+q^{T}\lambda \\ s.t. \quad & G\lambda \leq h \\ & A\lambda=b \\ \end{split} \end{equation}\]

利用硬间隔支持向量机算法来求解最优超平面的参数\(w^{*},b^{*}\)，以下是相应的代码：

# data matrix
train_X = train_data.iloc[:,[0,1]].values
train_y = train_data.iloc[:,2].values

# parameters solving
def HardMargin_SVM(X,y):
    Y = np.array([y]*X.shape[1]).T
    XdotY = X * Y
    n_samples = X.shape[0]
    Gram_Matrix = np.zeros((n_samples,n_samples))
    for i in range(n_samples):
        for j in range(n_samples):
            Gram_Matrix[i,j] = np.dot(XdotY[i],XdotY[j])
    
    P = matrix(Gram_Matrix).T
    q = matrix(-np.ones(n_samples))
    G = matrix(-np.eye(n_samples))
    h = matrix(np.zeros(n_samples))
    A = matrix(y.astype(float)).T
    b = matrix([0.0])

    lamda = np.array(solvers.qp(P,q,G,h,A,b)['x'])
    threshold = 1e-5
    lamda[lamda < threshold] = 0
    
    w_hat = np.round(np.sum(lamda*XdotY,axis=0),4)

    positive_index = np.where(lamda>0)[0][0]
    SV_x = X[positive_index]
    SV_y = y[positive_index]
    GM_xwithSVx = np.zeros(n_samples)
    for i in range(n_samples):
        GM_xwithSVx[i] = np.dot(X[i],SV_x)

    lamda = lamda.ravel()
    b_hat = round(SV_y - np.dot(lamda,y * GM_xwithSVx),4)

    return [w_hat,b_hat],lamda

theta,lamda = HardMargin_SVM(X=train_X,y=train_y)

解得最优超平面的参数为：

\[w^{*}=\begin{bmatrix} -0.8985 \\ 0.6889 \\ \end{bmatrix}, \quad b^{*}=0.4643\]

画出最优分离超平面\(S^{*}=\{x \vert w^{*} \cdot x + b^{*}=0\}\)：

# draw the Optimal Classification Hyperplane
w,b = theta[0],theta[1]
x1 = np.linspace(0,5,1000)
x2 = -(w[0]*x1+b)/w[1]
plt.figure(figsize=(8, 6))
plt.scatter(x=positivedata["x1"],y=positivedata["x2"],marker="o",c="green",label="positive data")
plt.scatter(x=negativedata["x1"],y=negativedata["x2"],marker="x",c="red",label="negative data")
plt.plot(x1,x2,c="blue",label="Optimal Classification Hyperplane")
plt.xlabel("x1")
plt.ylabel("x2")
plt.xlim((0,5))
plt.ylim((0,5))
plt.xticks(np.arange(0,5,0.5))
plt.yticks(np.arange(0,5,0.5))
plt.legend()

Image4: 最优分离超平面

分类模型：

\[f(x)=sign(w^{*} \cdot x + b^{*})\]

基于sklearn的算法实现

下面我们使用sklearn库来完成这个分类任务，我们依然使用前文生成的由30个正类实例点与20个负类实例点构成的训练数据集，使用sklearn.svm中的LinearSVC进行分类的代码为：

1
2
3

svm = LinearSVC(penalty="l2",C=1.0,loss='hinge')
svm.fit(train_X,train_y)
w,b = svm.coef_[0],svm.intercept_[0]

LinearSVC的一些主要参数为：

penalty: {'l1','l2'},default='l2'。设定惩罚项，SVC中默认为'l2'惩罚项，'l1'会导致稀疏的coef_向量。
loss: {'hinge', 'squared_hinge'}, default='squared_hinge'。设定损失函数，hinge是标准的SVM损失(如SVC类使用的)，而squared_hinge是hinge损失的平方。
dual: bool, default=True。选择算法来解决对偶或原始优化问题。当n_samples> n_features时，首选dual = False。
tol: float, default=1e-4。设置停止的条件。
C: float, default=1.0。正则化参数。正则化的强度与C成反比。必须严格设置为正的。

得到的最优分类超平面的参数为：

\[w^{*}=\begin{bmatrix} -0.8240 \\ 0.7860 \\ \end{bmatrix}, \quad b^{*}=0.0349\]

画出最优分离超平面\(S^{*}=\{x \vert w^{*} \cdot x + b^{*}=0\}\)：

Image4: 最优分离超平面

附录

关于凸优化的相关知识

基础概念

仿射集
设\(C\)为某一集合，若 \(\forall x_1,x_2 \in C, \theta \in \mathbb{R}, \theta x_1+(1-\theta)x_2 \in C\)，则称集合\(C\)为仿射集。

仿射函数
设有映射 \(f: \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}\)，若 \(f(x)=Ax+b, A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^{m}\)，则称映射\(f\)为仿射函数。

凸集
设\(C\)为某一集合，若 \(\forall x_1,x_2 \in C, \theta \in [0,1], \theta x_1+(1-\theta)x_2 \in C\)，则称集合\(C\)为凸集。

凸函数
一个函数\(f(x)\)被称为凸函数，如果它的定义域 \(dom f\) 为凸集，并且对 \(\forall x_1,x_2 \in dom f, \alpha \in [0,1]\)，有以下不等式成立：

\[f[\alpha x_1+(1-\alpha) x_2] \leq \alpha f(x_1)+(1-\alpha)f(x_2)\]

凸函数的一阶条件
设函数\(f(x)\)一阶可微，\(x \in \mathbb{R}^{n}\)，则\(f(x)\)为凸函数的充要条件为：\(dom \space f\)为凸集，且对\(\forall x,y \in dom \space f\)，有以下不等式成立：

\[f(y) \ge f(x)+\nabla f^{T}(x)(y-x)\]

凸函数的二阶条件
设函数\(f(x)\)二阶可微，\(x \in \mathbb{R}^{n}\)，则\(f(x)\)为凸函数的充要条件为：\(dom \space f\)为凸集，且对\(\forall x \in dom \space f\)，有\(\nabla^{2}f(x) \succeq 0\)，即\(Hessain\)矩阵半正定。

最优化问题
最优化问题的基本形式(7)：

\[\begin{equation} \begin{split} \min_{x} \quad & f(x) \\ s.t. \quad & m_{i}(x) \leq 0,\quad i=1,2,\dots,M \\ & n_{j}(x) = 0,\quad j=1,2,\dots,N \end{split} \end{equation}\]

\(x=\begin{bmatrix} x_1,x_2,\dots,x_n \end{bmatrix}^{T},x \in \mathbb{R}^{n}\) 称为优化变量(Optimization Variable).
\(f: \mathbb{R}^{n} \rightarrow \mathbb{R}\)，称为目标函数(Objective Function).
\(m_i: \mathbb{R}^{n} \rightarrow \mathbb{R}\)，称为不等式约束(Inequality Constraint).
\(n_j: \mathbb{R}^{n} \rightarrow \mathbb{R}\)，称为等式约束(Equality Constraint).
\(D = \left( dom \space f \right) \bigcap \{x \vert m_{i}(x) \leq 0,i=1,2,\dots,M\} \bigcap \{x \vert h_{j}(x) = 0,j=1,2,\dots,N\}\)，称为最优化问题的域(Domain)，\(x \in D\) 称为可行解(Feasible Solution).
\(p^{*} = \inf \{ f(x) \vert x \in D \}\)，称为最优化问题的最优值(Optimum).
\(f(x^{*})=p^{*}\)，称\(x^{*}\)为最优化问题的最优解(Optimal Solution).
\(X_{opt} = \{ x \vert x \in D,f(x)=p^{*} \}\)，称为最优化问题的最优解集(Optima Set).

凸优化问题
若在优化问题(7)中，目标函数\(f(x)\)为凸函数，不等式约束\(m_i(x)\)为凸函数，等式约束\(n_j(x)\)为仿射函数，则称该优化问题为凸优化问题。

对偶关系

拉格朗日函数
原问题(7)的拉格朗日函数为：

\[L(x,\lambda,\eta)=f(x)+\sum_{i=1}^{M}\lambda_i m_i(x)+\sum_{j=1}^{N}\eta_j n_j(x)\]

\[\lambda_i \ge 0, \quad i=1,2,\dots,M\]

原问题的无约束形式
原问题(7)的无约束形式(8)为：

\[\begin{equation} \begin{split} \min_{x} \max_{\lambda,\eta} \quad & L(x,\lambda,\eta) \\ s.t. \quad & \lambda_i \ge 0, \quad i=1,2,\dots,M \\ \end{split} \end{equation}\]

原问题(7)与其无约束形式(8)是等价的，现证明这个结论。
证明:
令\(h(x) = \max_{\lambda,\eta} L(x,\lambda,\eta)\),
若优化变量\(x\)不满足某个不等式约束\(m_i(x)\)，即 \(\exists i, m_i(x) > 0\),则有：

\[h(x)=\max_{\lambda,\eta} L(x,\lambda,\eta) \rightarrow +\infty\]

若优化变量\(x\)不满足某个等式约束\(n_j(x)\)，即 \(\exists j,n_j(x) \ne 0\)，则有：

\[h(x)=\max_{\lambda,\eta} L(x,\lambda,\eta) \rightarrow +\infty\]

若优化变量\(x\)满足所有的不等式约束\(m_i(x)\)与等式约束\(n_j(x)\),即 \(\forall i,j, m_i(x) \leq 0, n_j(x)=0\)，则有:

\[h(x) = \max_{\lambda,\eta} L(x,\lambda,\eta) < +\infty\]

\[\lambda_i = 0, \quad i=1,2,\dots,M\]

设集合\(S_1,S_2\)分别为：

\[S_1 = \{ x \vert \exists i,m_i(x) > 0 \} \cup \{ x \vert \exists j, n_j(x) \ne 0 \}\]

\[S_2 = \{ x \vert \forall i,j, m_i(x) \leq 0,n_j(x) = 0 \}\]

有:

\[S_1 \cup S_2 = \mathbb{R}^{n}, S_1 \cap S_2 = \emptyset\]

则无约束问题(8)可以写为

\[\min_{x} \max_{\lambda,\eta} L(x,\lambda,\eta) \Leftrightarrow \min_{x} h(x) = \left \{ \begin{array}{l} +\infty, & {x \in S_1}\\ c(x)<+\infty,& {x \in S_2}\\ \end{array} \right.\]

\[\Rightarrow \min_{x} \max_{\lambda,\eta} L(x,\lambda,\eta) \Leftrightarrow \min_{x \in S_2} h(x)=\min_{x \in S_2} f(x)\]

故原问题(7)与其无约束形式(8)等价。
证毕.

对偶问题
原问题(7)的拉格朗日对偶问题(9)为：

\[\begin{equation} \begin{split} \max_{\lambda,\eta} \min_{x} \quad & L(x,\lambda,\eta) \\ s.t. \quad & \lambda_i \ge 0, \quad i = 1,2,\dots,M \end{split} \end{equation}\]

弱对偶关系
原问题(7)与其对偶问题(9)满足弱对偶关系：

\[\max_{\lambda,\eta} \min_{x} L(x,\lambda,\eta) \leq \min_{x} \max_{\lambda,\eta} L(x,\lambda,\eta)\]

证明:
令：

\[A(\lambda,\eta)=\min_{x} L(x,\lambda,\eta),\quad B(x)=\max_{\lambda,\eta} L(x,\lambda,\eta)\]

\[\because \min_{x}L(x,\lambda,\eta) \leq L(x,\lambda,\eta) \leq \max_{\lambda,\eta} L(x,\lambda,\eta)\]

\[\Rightarrow A(\lambda,\eta) \leq B(x),\quad \forall \lambda,\eta, \forall x\]

\[\Rightarrow \max_{\lambda,\eta} A(\lambda,\eta) \leq \min_{x} B(x)\]

即：

\[\max_{\lambda,\eta} \min_{x} L(x,\lambda,\eta) \leq \min_{x} \max_{\lambda,\eta} L(x,\lambda,\eta)\]

证毕.

强对偶关系
若原问题(7)与其对偶问题(9)满足：

\[\max_{\lambda,\eta} \min_{x} L(x,\lambda,\eta) = \min_{x} \max_{\lambda,\eta} L(x,\lambda,\eta)\]

则称原问题(7)与其对偶问题(9)满足强对偶关系。

强对偶关系的几何理解
设原问题为仅有不等式约束的优化问题(10)：

\[\begin{equation} \begin{split} \min_{x} \quad & f(x) \\ s.t. \quad & m_{i}(x) \leq 0, \quad i=1,2,\dots,M \\ \end{split} \end{equation}\]

原问题(10)的拉格朗日函数为：

\[L(x,\lambda)=f(x)+\sum_{i=1}^{M}\lambda_i m_i(x)\]

若原问题与其对偶问题满足强对偶关系，则有：

\[\min_{x} \max_{\lambda} L(x,\lambda) = \max_{\lambda} \min_{x} L(x,\lambda)\]

鞍点的定义: 若 \(\exists (\hat{w},\hat{z})\)，使得：

\[\sup_{z} \inf_{w} f(w,z) =f(\hat{w},\hat{z})= \inf_{w} \sup_{z} f(w,z)\]

则称 \((\hat{w},\hat{z})\) 为 \(f(w,z)\) 的鞍点。由于 \(f(\hat{w},z)= \inf_{w} f(w,z), f(w,\hat{z})=sup_{z} f(w,z)\)，则以上等式也可以写成：

\[\sup_{z} f(\hat{w},z)=f(\hat{w},\hat{z})=\inf_{w} f(w,\hat{z})\]

Image: 鞍点

结合鞍点以及强对偶关系的概率，我们可以得出结论：原问题的拉格朗日函数存在鞍点是原问题与对偶问题满足强对偶关系的充要条件，且鞍点即为原问题与对偶问题的最优解。

KKT条件

下面来介绍如何判断原问题与对偶问题是否满足强对偶关系，以及如何求出相应的最优解。首先来介绍\(Slater\)条件。
\(Slater\)条件
若原问题(7)是凸问题，同时 \(\exists x \in relint(D)\)，使得约束满足：

\[\begin{split} & m_{i}(x) < 0, \quad i=1,2,\dots,M \\ & n_{j}(x) = 0, \quad j=1,2,\dots,N \\ \end{split}\]

则原问题与对偶问题满足强对偶关系。

注：\(relint(D)\) 表示原始凸问题的域的相对内部，即域内除了边界点以外的所有点。

\(Slater\)条件是一个充分不必要条件，若满足\(Slater\)条件，则强对偶一定成立，不满足\(Slater\)条件，强对偶也可能成立。大多数凸优化问题均满足\(Slater\)条件，即有强对偶性。
若我们已知原问题与对偶问题满足强对偶关系，如何求解出原问题以及对偶问题的最优解？下面我们来介绍凸优化中一个非常经典的理论——KKT条件。

KKT条件
设\(x^{*}\)为原始问题(7)的最优解，\(\lambda^{*},\eta^{*}\)为对偶问题(9)的最优解，且原始问题与对偶问题满足强对偶关系，则有以下四组条件成立：

\[KKT条件: \left \{ \begin{array}{l} m_{i}(x^{*}) \leq 0, h_{j}(x^{*}) = 0 &&(primal \space feasibility) \\ \\ \lambda^{*} \ge 0 &&(dual \space feasibility)\\ \\ \lambda^{*}m_{i}(x^{*})=0 &&(complementary \space slackness)\\ \\ \frac{\partial L(x,\lambda^{*},\eta^{*})}{\partial x} \vert_{x=x^{*}}=0 &&(stationarity)\\ \end{array} \right.\]

原问题、对偶问题的可行性条件，稳定性条件都很好理解，我们主要来推导一下互补松弛条件是如何得到的。
证明:
记 \(p^{*}\) 为原问题(7)的最优值，\(d^{*}\) 为对偶问题(9)的最优值，即：

\[p^{*}= \min_{x} f(x)=f(x^{*})\]

\[d^{*}=\max_{\lambda,\eta} \min_{x} L(x,\lambda,\eta) \triangleq \max_{\lambda,\eta} g(\lambda,\eta)=g(\lambda^{*},\eta^{*})\]

通过分析可得：

\[\begin{align*} d^{*} &= \max_{\lambda,\eta} \min_{x} L(x,\lambda,\eta) = \min_{x} \max_{\lambda,\eta} L(x,\lambda,\eta) = \min_{x} L(x,\lambda^{*},\eta^{*}) \\ &\leq L(x^{*},\lambda^{*},\eta^{*}) = f(x^{*})+\sum_{i=1}^{M}\lambda_{i}^{*}m_{i}(x^{*}) + \sum_{j=1}^{N}\eta_{j}^{*}n_{j}(x^{*}) \\ &\leq f(x^{*}) = p^{*} \end{align*}\]

由原问题与对偶问题满足强对偶关系可知：\(p^{*}=d^{*}\)，则以上式子中的小于等于号均取等号，故有：

\[\sum_{i=1}^{M}\lambda_{i}^{*}m_{i}(x^{*})=0 \Rightarrow \lambda^{*}m_{i}(x^{*})=0, \forall i\]

互补松弛条件成立，证毕.

对于一般的原问题，KKT条件是 \(x^{*},\lambda^{*},\eta^{*}\) 为最优解的必要条件，即只要 \(x^{*},\lambda^{*},\eta^{*}\) 为原问题及对偶问题的最优解，则一定满足KKT条件。
对于原问题为凸问题，KKT条件是 \(x^{*},\lambda^{*},\eta^{*}\) 为最优解的充要条件，即只要 \(x^{*},\lambda^{*},\eta^{*}\) 满足KKT条件，则其一定为原问题及对偶问题的最优解，反过来，只要 \(x^{*},\lambda^{*},\eta^{*}\) 为原问题及对偶问题的最优解，则其一定满足KKT条件。

凸二次规划

凸二次规划问题的基本形式为：

\[\begin{equation} \begin{split} \min_{x} \quad & \frac{1}{2} x^{T}Px+q^{T}x+r \\ s.t. \quad & Gx \leq h \\ & Ax=b \\ \end{split} \end{equation}\]

其中，\(x \in \mathbb{R}^{n}, P \in S_{+}^{n}\)，为对称正定矩阵；\(q,r \in \mathbb{R}^{n}; G \in \mathbb{R}^{M \times n}, h \in \mathbb{R}^{M}; A \in \mathbb{R}^{N \times n}, b \in \mathbb{R}^{N}\).
结论：凸二次规划问题满足强对偶关系。

硬间隔线性支持向量机的解是唯一的

结论: 如果训练数据集\(T_{train}\)完全线性可分，通过最小间隔最大化问题的求解，存在唯一的分离超平面可以将所有样本点完全分开。
证明:
(1) 存在性的证明：
由于训练数据集\(T_{train}\)完全线性可分，由线性可分的定义可知存在分离超平面 \(S = \{x \vert w \cdot x + b = 0\}\) 可将所有样本点完全正确分类。存在性得证。
(2) 唯一性的证明：
利用反证法来进行证明。假设优化问题(2)存在两个不同的最优解，分别记为\(w_{1}^{*},b_{1}^{*}\)和\(w_{2}^{*},b_{2}^{*}\)，意味着两个权值向量所对应的模都是最小值，记为\(a\)：

\[||w_{1}^{*}||=||w_{2}^{*}||=a\]

根据这两组参数可以构造一组新的参数：

\[w=\frac{w_{1}^{*}+w_{2}^{*}}{2}, \quad b=\frac{b_{1}^{*}+b_{2}^{*}}{2}\]

新构造的参数\(w\)的模长一定满足：

\[||w||= || \frac{w_{1}^{*}+w_{2}^{*}}{2} || \ge a\]

另一方面，由模长的三角不等式可得：

\[||\frac{w_{1}^{*}+w_{2}^{*}}{2}|| = ||\frac{1}{2}w_{1}^{*}+\frac{1}{2}w_{2}^{*}|| \leq \frac{1}{2}||w_{1}^{*}||+\frac{1}{2}||w_{2}^{*}||=a\]

从而有：

\[|| \frac{w_{1}^{*}+w_{2}^{*}}{2} ||=a\]

即：

\[||w||= \frac{1}{2}||w_{1}^{*}||+\frac{1}{2}||w_{2}^{*}||\]

由此发现，\(w_{1}^{*}\)和\(w_{2}^{*}\)在同一直线上：

\[w_{1}^{*}=\pm w_{2}^{*}\]

当\(w_{1}^{*}= w_{2}^{*}\)时，与假设矛盾；当\(w_{1}^{*}= -w_{2}^{*}\)时，违背了权重向量时非零向量的前提。唯一性得证。
证毕.

参考

[1] Book: 李航,统计学习方法(第2版)
[2] Book: 董平,机器学习中的统计思维(Python实现)
[3] Video: bilibili,简博士,支持向量机系列
[4] Video: bilibili,shuhuai008,支持向量机系列
[5] Video: bilibili,欧拉的费米子,凸优化理论-中科大凌青
[6] Blog: 知乎,Lauer,[凸优化笔记6]-拉格朗日对偶、KKT条件

机器学习

机器学习-3.硬间隔线性支持向量机

http://example.com/2023/10/24/机器学习-3-硬间隔线性支持向量机/

作者

喵老师

发布于

2023年10月24日

许可协议

深度学习-2-Paper:生成对抗网络GANs——深度学习二十年间最酷的idea! 上一篇

机器学习-2.感知机下一篇