SVM

支持向量机(SVM)推导

​ 支持向量机(SVM)是机器学习中经典的二分类模型,它通过找到一个最优的超平面,最大化正负样本的分类间隔,实现对数据的有效分类。本篇博客将从问题定义开始,逐步推导 SVM 的完整数学过程,包括优化目标、拉格朗日对偶理论、KKT 条件的应用和最终决策函数的构造。推导过程力求数学完备,同时以通俗语言讲解每一步推导背后的逻辑

​ 考虑输入空间 XXRN(N1)\mathbb{R}^N (N \geq 1) 的一个子集,输出空间为 Y={1,+1}Y = \{-1,+1\},目标函数为 f:XYf: X \to Y。二分类任务可以表述为:利用根据未知分布 DD 从样本空间 XX 独立同同分布采样得到的样本集合 S=((x1,y1),(x2,y2),,(xm,ym))S = ((x_1,y_1),(x_2,y_2), \ldots, (x_m,y_m)), 并且 f(xi)=yi,  i[1,m]f(x_i) = y_i, \forall\; i \in [1, m],我们希望从假设函数空间 HH 中找出一个最优的 hHh \in H,使得如下泛化误差最小:

RD(h)=PrxD[h(x)f(x)]R_D(h) = \Pr_{x \sim D} [h(x) \neq f(x)]

一个自然而简单的假设是目标函数为线性分类器,或者说是 NN 维空间中的超平面:

H={xsgn(wx+b):wRN,bR}H = \{ \mathbf{x} \mapsto sgn(\mathbf{w} \cdot \mathbf{x} + b): \mathbf{w} \in \mathbb{R}^N, b \in \mathbb{R}\}

具有上述形式的函数 hh 将超平面 wx+b=0\boldsymbol{w} \cdot \boldsymbol{x} + b = 0 两侧的点标注为 +1+11-1,因而上述学习问题被称为“线性分类问题”。

SVM——线性可分情形

​ 假设样本集合 SS 是线性可分的,即存在超平面完美地将样本集合中的正负样本分开。由于参数空间是连续的,必然存在无穷多个在样本集上完成分类任务的超平面。因此,我们可以选择一个最“好”的超平面,使得正负样本与超平面 之间具有最大边界。

主优化问题

​ 注意到对超平面的参数 (w,b)(\boldsymbol{w},b) 等比例放缩并不改变超平面的几何性质,因此可以通过适当的放缩使得 min(x,y)Swx+b=1\min_{(\boldsymbol{x},y) \in S} |\boldsymbol{w} \cdot \boldsymbol{x} + b|=1,放缩后的超平面称为 规范超平面。由定义可得,对样本中的任意 xi(i[1,m])x_i(i \in [1,m]),有 wxi+b1|\boldsymbol{w} \cdot \boldsymbol{x_i} + b| \geq 1。 从解析几何的结论可知,空间中任意一点 x0RNx_0 \in \mathbb{R}^N 到超平面 wx+b=0\boldsymbol{w} \cdot \boldsymbol{x} + b = 0 的距离为:

d=wx0+bwd=\frac{|\mathbf{w} \cdot \mathbf{x_0} + b|}{||\mathbf{w}||}

对于规范超平面,定义其边界大小 ρ\rho 为:

ρ=min(x,y)Swx+bw=1wsubject to:min(x,y)Swx0+b=1\rho = \min_{(\mathbf{x},y) \in S} \frac{|\mathbf{w} \cdot \mathbf{x} + b|}{||\mathbf{w}||} = \frac{1}{||\mathbf{w}||} \\ \text{subject to:} \min_{(x,y) \in S} |\mathbf{w} \cdot \mathbf{x_0} + b| = 1

​ 求取具有最大边界的超平面可以表述为如下优化问题:

\max_{\mathbf{w},b} && \frac{1}{||\mathbf{w}||} \nonumber\\ \text{subject to:} && y_i(\mathbf{w} \cdot \mathbf{x} + b) = 1, \forall\; i \in [1,m] \nonumber \\

等价于:

Optimization Problem:PA:{minw,b12w2subject to:yi(wx+b)=1,i=1,,m.\text{Optimization Problem:} \\ P_A: \left\{ \begin{aligned} & \min_{\mathbf{w},b} \frac{1}{2}||\mathbf{w}||^2\\ & \text{subject to:} \quad y_i(\mathbf{w} \cdot \mathbf{x} + b) = 1, \quad i = 1, \ldots, m. \end{aligned} \right.

如果直接使用这个条件:min(x,y)Swx0+b=1\min_{(x,y) \in S} |\boldsymbol{w} \cdot \boldsymbol{x_0} + b| = 1 会出现两个问题;

  1. 数值稳定性:在实际计算中,由于数值精度的原因,可能很难保证所有支持向量到超平面的距离严格等于 1/w1/||\boldsymbol{w}||
  2. 灵活性不足:如果数据不是完美线性可分的,或者我们希望引入软间隔来允许一些误分类,那么严格的等式约束就不适用了

因此,我们适当放宽约束条件,将优化问题改写为:

Optimization Problem:PB:{minw,b12w2=12wTwsubject to:yi(wx+b)1,i=1,,m.\text{Optimization Problem:} \\ P_B: \left\{ \begin{aligned} & \min_{\mathbf{w},b} \frac{1}{2}||\mathbf{w}||^2=\frac{1}{2}\mathbf{w}^T\mathbf{w}\\ & \text{subject to:} \quad y_i(\mathbf{w} \cdot \mathbf{x} + b) \ge 1, \quad i = 1, \ldots, m. \end{aligned} \right.

PA,PBP_A,P_B 等价性的证明:

  • 显然 PAP_A 的最优解是 PBP_B 的可行解,即 PBP_B 的可行解集大于 PAP_A 的可行解集
  • 因此证明 PBP_B 的最优解在 PAP_A 可行解集内部即可

反证法,若 PBP_B 的最优解不在 PAP_A 的可行解内部,设 (w,b)(\boldsymbol{w^*} , b^*)PBP_B 的最优解(不在 PAP_A 可行解内):

Let C=min(xn,yn)Syn(wxn+b)>1C>1C=min(xn,yn)Syn(wCxn+bC)=112w2>12w/C2\text{Let } \quad C=\min_{(x_n,y_n) \in S}y_n(\mathbf{w^*} \cdot \mathbf{x_n} + b^*) \gt 1 \Rightarrow C>1 \\ \Rightarrow C=\min_{(x_n,y_n) \in S}y_n(\frac{\mathbf{w^*}}{C} \cdot \mathbf{x_n} + \frac{b^*}{C}) =1 \\ \frac{1}{2}||\mathbf{w}^*||^2 \gt \frac{1}{2}||\mathbf{w}^*/C||^2

因此 (w,b)(\boldsymbol{w^*} , b^*) 并不为 PBP_B 的最优解,矛盾,因此 PBP_B 的最优解即为 PAP_A 的最优解

对于 $P_B$,显而易见,该优化问题的目标函数为凸函数,约束条件为线性不等式组,因而是典型的二次规划问题(QP),可以用成熟的求解器求解,也可以使用万能的梯度下降法求解

对偶优化问题

​ 对优化问题引入拉格朗日乘子 αi0,i[1,m]\alpha_i \geq 0, i \in [1,m],构造拉格朗日函数 $$L(\boldsymbol{w},b,\boldsymbol{\alpha}) = \frac{1}{2}||\boldsymbol{w}||^2 - \sum_{i=1}^{m}\alpha_i[y_i(\boldsymbol{w} \cdot \boldsymbol{x} + b)-1],$$ 得到原目标函数的对偶函数为

\begin{eqnarray} g(\mathbf{\alpha}) & = &\inf_{\mathbf{w},b} L(\mathbf{w},b,\mathbf{\alpha}) \nonumber\\ & = & \sum_{i=1}^{m}\alpha_i + \inf_{\mathbf{w}}\bigg\{\frac{1}{2}||\mathbf{w}||^2 - (\sum_{i=1}^{m}\alpha_i y_i\mathbf{x})\cdot\mathbf{w} \bigg\} + \inf_{b}\bigg\{- \sum_{i=1}^{m}\alpha_i y_ib\bigg\} \nonumber\\ & = & \left\{ \begin{array}{ll} \sum_{i=1}^{m}\alpha_i - \sum_{i,j=1}^{m}\alpha_i \alpha_j y_i y_j(\mathbf{x_i} \cdot \mathbf{x_j})& \text{if $\sum_{i=1}^{m}\alpha_i y_i = 0$}\\ -\infty & \text{else}\\ \end{array} \right. \end{eqnarray}

因而,对偶问题可以表述为:

\label{eqnarray:dual} \max_{\mathbf{\alpha}} && \sum_{i=1}^{m}\alpha_i - \sum_{i,j=1}^{m}\alpha_i \alpha_j y_i y_j(\mathbf{x_i} \cdot \mathbf{x_j})\\ subject\;to: && \sum_{i=1}^{m}\alpha_i y_i = 0 \nonumber\\ && \alpha_i \geq 0,\;\; i=1,\ldots,m \nonumber

对偶优化问题的目标函数为凸函数,约束条件为线性不等式组,也是典型的二次规划问题(QP)。

支持向量

由于原问题和对偶问题的不等式约束条件都是线性的,强对偶条件成立,故最优解满足KKT条件:

\begin{eqnarray} \label{eq:KKT1} \bigtriangledown_{\mathbf{w}}L = \mathbf{w}-\sum_{i=1}^{m} \alpha_i y_i \mathbf{x}_i = 0 &\Longrightarrow& \mathbf{w} = \sum_{i=1}^{m} \alpha_i y_i \mathbf{x}_i \\ \label{eq:KKT2} \bigtriangledown_{b}L = -\sum_{i=1}^{m} \alpha_i y_i = 0 &\Longrightarrow& \sum_{i=1}^{m} \alpha_i y_i = 0 \\ \label{eq:KKT3} \forall i, \alpha_i[y_i((\mathbf{w} \cdot \mathbf{x_i} + b)-1] = 0 &\Longrightarrow& \alpha_i = 0 \vee y_i(\mathbf{w} \cdot \mathbf{x_i} + b) = 1. \end{eqnarray}

从互补松弛条件(\ref{eq:KKT3})可知,若 xi\boldsymbol{x}_i 不是距离分离超平面最近的点,即 wxi+b1|\boldsymbol{w} \cdot \boldsymbol{x}_i + b| \neq 1,则必有 αi=0\alpha_i = 0。反映在等式 (\ref{eq:KKT1})中,说明上述 xi\boldsymbol{x}_i 对超平面方向的选择没有影响。因此,决定分离超平面方向 w\boldsymbol{w} 的只有那些使 yi(wxi+b)=1y_i(\boldsymbol{w} \cdot \boldsymbol{x}_i + b) = 1 成立的样本点,称这些点为 支撑向量

SVM——线性不可分情形

​ 在数据线性不可分时,无法找到参数 (w,b)(\boldsymbol{w},b) 使得 wxi+b\boldsymbol{w}\cdot\boldsymbol{x}_i+byiy_i 的符号一致,也就是说,对任意超平面 wx+b=0\boldsymbol{w}\cdot\boldsymbol{x}+b = 0,存在 xiS\boldsymbol{x}_i \in S 使得

\begin{equation} y_i[\mathbf{w}\cdot\mathbf{x}_i+b] < 1. \end{equation}

为此,我们引入松弛变量 ξi0\xi_i \geq 0,使得

\begin{equation} y_i[\mathbf{w}\cdot\mathbf{x}_i+b] \geq 1-\xi_i. \end{equation}

这样一来,主优化问题改写成:

\begin{eqnarray} \label{eqnarray:prime2} \min_{\mathbf{w},b} && \frac{1}{2}||\mathbf{w}||^2 + C\sum_{i=1}^{m}\xi_i^p\\ subject\;to: && y_i(\mathbf{w} \cdot \mathbf{x} + b) \geq 1-\xi_i, \nonumber \\ && \xi_i \geq 0. \; i\in [1,m] \nonumber \end{eqnarray}

下面只考虑 p=1p=1 时的情形

对偶优化问题

对优化问题(\ref{eqnarray:prime2})引入拉格朗日乘子 αi,βi0,i[1,m]\alpha_i,\beta_i \geq 0, i \in [1,m],构造拉格朗日函数 $$L(\boldsymbol{w},b,\boldsymbol{\xi},\boldsymbol{\alpha},\boldsymbol{\beta}) = \frac{1}{2}||\boldsymbol{w}||^2 + C\sum_{i=1}^{m}\xi_i - \sum_{i=1}^{m}\alpha_i[y_i(\boldsymbol{w} \cdot \boldsymbol{x} + b)-1+\xi_i] - \sum_{i=1}^{m}\beta_i\xi_i,$$ 得到原目标函数的对偶函数为

\begin{eqnarray} g(\mathbf{\alpha},\mathbf{\beta}) & = &\inf_{\mathbf{w},b,\mathbf{xi}} L(\mathbf{w},b,\mathbf{\xi},\mathbf{\alpha},\mathbf{\beta}) \nonumber\\ & = & \sum_{i=1}^{m}\alpha_i \nonumber\\ && + \inf_{\mathbf{w}}\bigg\{\frac{1}{2}||\mathbf{w}||^2 - (\sum_{i=1}^{m}\alpha_i y_i\mathbf{x})\cdot\mathbf{w} \bigg\} \nonumber\\ && + \inf_{b}\bigg\{- \sum_{i=1}^{m}\alpha_i y_ib\bigg\} \\ && + \inf_{\mathbf{\xi}}\bigg\{ \sum_{i=1}^{m}(C-\alpha_i-\beta_i)\xi_i\bigg\} \nonumber\\ & = & \left\{ \begin{array}{ll} \sum_{i=1}^{m}\alpha_i - \sum_{i,j=1}^{m}\alpha_i \alpha_j y_i y_j(\mathbf{x_i} \cdot \mathbf{x_j}), & \textrm{如果 $\sum_{i=1}^{m}\alpha_i y_i = 0$ 且 $\alpha_i+\beta_i = C$,}\\ -\infty, & \textrm{其他情况。}\\ \end{array} \right. \nonumber \end{eqnarray}

因而,对偶问题可以表述为:

\begin{eqnarray} \max_{\mathbf{\alpha}} && \sum_{i=1}^{m}\alpha_i - \sum_{i,j=1}^{m}\alpha_i \alpha_j y_i y_j(\mathbf{x_i} \cdot \mathbf{x_j}) \nonumber\\ subject\;to: && \sum_{i=1}^{m}\alpha_i y_i = 0 \nonumber\\ && \alpha_i + \beta_i = C, \nonumber \\ && \alpha_i \geq 0, \nonumber\\ && \beta_i \geq 0, \;\; i=1,\ldots,m \nonumber \end{eqnarray}

等价于:

\begin{eqnarray} \label{eqnarray:dual2} \max_{\mathbf{\alpha}} && \sum_{i=1}^{m}\alpha_i - \sum_{i,j=1}^{m}\alpha_i \alpha_j y_i y_j(\mathbf{x_i} \cdot \mathbf{x_j})\\ subject\;to: && \sum_{i=1}^{m}\alpha_i y_i = 0 \nonumber\\ && 0 \leq \alpha_i \leq C, \;\; i=1,\ldots,m \nonumber \end{eqnarray}

KKT条件

线性不可分问题的最优解满足如下KKT条件:

\begin{eqnarray} \label{eq:KKT21} \bigtriangledown_{\mathbf{w}}L = \mathbf{w}-\sum_{i=1}^{m} \alpha_i y_i \mathbf{x}_i = 0 &\Longrightarrow& \mathbf{w} = \sum_{i=1}^{m} \alpha_i y_i \mathbf{x}_i \\ \label{eq:KKT22} \bigtriangledown_{b}L = -\sum_{i=1}^{m} \alpha_i y_i = 0 &\Longrightarrow& \sum_{i=1}^{m} \alpha_i y_i = 0 \\ \label{eq:KKT23} \bigtriangledown_{\xi_i}L = C-\alpha_i-\beta_i = 0 &\Longrightarrow& \alpha_i + \beta_i = C \\ \label{eq:KKT24} \forall i, \alpha_i[y_i((\mathbf{w} \cdot \mathbf{x_i} + b)-1+\xi_i] = 0 &\Longrightarrow& \alpha_i = 0 \vee y_i(\mathbf{w} \cdot \mathbf{x_i} + b) = 1-\xi_i.\\ \label{eq:KKT25} \forall i, \beta_i\xi_i = 0 &\Longrightarrow& \beta_i = 0 \vee \xi_i = 0. \end{eqnarray}

结合 (\ref{eq:KKT23})和(\ref{eq:KKT24}),(\ref{eq:KKT25})可改写成:

\begin{equation} \alpha_i = C \vee y_i(\mathbf{w} \cdot \mathbf{x_i} + b) = 1. \end{equation}

这说明,对于 αi0\alpha_i \neq 0 对应的支撑向量 xi\boldsymbol{x}_i,要么正好落在边界平面上: yi(wxi+b)=1y_i(\boldsymbol{w} \cdot \boldsymbol{x_i} + b) = 1,要么其对应的 αi\alpha_i 正好等于CC。 \section{核函数} 从对偶问题 (\ref{eqnarray:dual})和 (\ref{eqnarray:dual2})发现,优化问题的目标函数只和样本点的内积 (xi,xj)(\boldsymbol{x}_i,\boldsymbol{x}_j) 有关。由此可以设想,把单纯的内积用某种二元函数 K(xi,xj)K(\boldsymbol{x}_i,\boldsymbol{x}_j) 替换,使其等效于在另一种维度的空间(称之为\textbf{特征空间})里做内积运算,这样或许能将原空间中的线性不可分问题变换成特征空间中的线性可分问题。 \paragraph{多项式核函数} 对常数 c>0c >0,定义 \texttt{d维多项式核函数}{} 为:

\begin{equation} \forall \mathbf{x,x'} \in \mathbb{R}^N, K(\mathbf{x,x'}) = (\mathbf{x}\cdot\mathbf{x'}+c)^d \end{equation}

高斯核函数

对常数 σ>0\sigma >0,定义 \texttt{高斯核函数}{} 或者 \texttt{径向基函数}{} 为:

\begin{equation} \forall \mathbf{x,x'} \in \mathbb{R}^N, K(\mathbf{x,x'}) = exp\big(-\frac{||\mathbf{x'}-\mathbf{x}||^2}{2\sigma^2}\big) \end{equation}

\paragraph{sigmoid核函数} 对常数 a,b0a,b \geq 0,定义 \texttt{sigmoid核函数}{} 为:

\begin{equation} \forall \mathbf{x,x'} \in \mathbb{R}^N, K(\mathbf{x,x'}) = tanh(a(\mathbf{x}\cdot\mathbf{x'})+b) \end{equation}

\begin{eqnarray} \label{eqnarray:kernel} \max_{\mathbf{\alpha}} && \sum_{i=1}^{m}\alpha_i - \sum_{i,j=1}^{m}\alpha_i \alpha_j y_i y_j K(\mathbf{x_i},\mathbf{x_j})\\ subject\;to: && \sum_{i=1}^{m}\alpha_i y_i = 0 \nonumber\\ && 0 \leq \alpha_i \leq C, \;\; i=1,\ldots,m \nonumber \end{eqnarray}