search
github编辑

7.1 线性支持向量机

hashtag
7.1.1 间隔

hashtag
一、函数间隔

对于一个训练样本(xi,yi)(\mathbf x^i,y^i)，它到(w,b)(\mathbf w,b)确定的超平面的函数间隔为：

γ^i=yi(wTxi+b)\hat{\gamma}^i = y^i(\mathbf w^T\mathbf x^i+b)

函数间隔与距离是正相关的

  • yi=1y^i=1，(wTxi+b)(\mathbf w^T\mathbf x^i + b)是一个大的正数

  • yi=−1y^i=-1，(wTxi+b)(\mathbf w^T\mathbf x^i + b)是一个比较小的负数

  • yi(wTxi+b)>0y^i(\mathbf w^T\mathbf x^i+b)>0，说明模型对样本的预测是正确的

  • 大的函数间隔→高的预测置信度

对于训练数据集S={(xi,yi), i=1,…,N}S = \{(\mathbf x^i,y^i),\ i=1,\dots,N\}，它的函数间隔定义为所有样本中最小的那个：

γ^=min⁡iγ^i, i=1,…,N\hat{\gamma} = \min_i \hat{\gamma}^i,\ i=1,\dots,N

hashtag
二、几何间隔

对于样本(xi,yi)(\mathbf x^i,y^i)，yi=1y^i=1，它到决策面的距离γi\gamma^i是线段AB的长度

其中，点B可以表示为：

xi−γiw∥w∥2\mathbf x^i - \frac{\gamma^i\mathbf w}{\Vert \mathbf w\Vert_2}

由于点B在决策边界上，即：

wT(xi−γiw∥w∥2)+b=0\mathbf w^T\left(\mathbf x^i - \frac{\gamma^i\mathbf w}{\Vert \mathbf w\Vert_2}\right) + b = 0

求解此方程可以得到样本(xi,yi)(\mathbf x^i,y^i)的几何间隔为：

γi=yi((w∥w∥2)Txi+b∥w∥2)\gamma^i = y^i\left(\left(\frac{\mathbf w}{\Vert\mathbf w\Vert_2}\right)^T\mathbf x^i + \frac{b}{\Vert\mathbf w\Vert_2}\right)

同样的，对于训练数据集S={(xi,yi), i=1,…,N}S = \{(\mathbf x^i,y^i),\ i=1,\dots,N\}，关于判别界面的几何间隔为：

γ=min⁡iγi, i=1,…,N\gamma = \min_i \gamma^i,\ i=1,\dots,N

函数间隔与几何间隔的关系：

γi=γ^i∥w∥2γ=γ^∥w∥2\gamma^i = \frac{\hat{\gamma}^i}{\Vert \mathbf w\Vert_2} \\ \gamma = \frac{\hat{\gamma}}{\Vert \mathbf w\Vert_2}

显然，若∥w∥2=1\Vert \mathbf w\Vert_2=1，则二者相等

几何间隔具有不变性

hashtag
三、最优间隔分类器

假设数据是线性可分的

给定一个训练集，一个自然的想法是试图找到一个使几何间隔最大化的决策边界，这表示对训练集的有可信的预测并且对训练数据的良好“拟合”

那么就需要最大化间隔，即：

max⁡γ,w,b γs.t. yi((w∥w∥2)Txi+b∥w∥2)≥γ,i=1,…,N\begin{align} \max_{\gamma,\mathbf w,b}\ &\gamma \nonumber \\ s.t.\ &y^i\left(\left(\frac{\mathbf w}{\Vert \mathbf w\Vert_2}\right)^T\mathbf x^i + \frac{b}{\Vert \mathbf w\Vert_2}\right)\geq\gamma,i=1,\dots,N \end{align}

可以将问题转化为几何间隔：

max⁡γ,w,b γ^∥w∥2s.t. yi(wTxi+b)≥γ^,i=1,…,N\begin{align} \max_{\gamma,\mathbf w,b}\ &\frac{\hat{\gamma}}{\Vert \mathbf w\Vert_2} \nonumber \\ s.t.\ &y^i(\mathbf w^T\mathbf x^i+b)\geq\hat\gamma,i=1,\dots,N \end{align}

进一步简化问题，令几何间隔为单位1：

min⁡w,b 12∥w∥22s.t. yi(wTxi+b)≥1,i=1,…,N\begin{align} \min_{\mathbf w,b}\ &\frac12\Vert\mathbf w\Vert_2^2 \nonumber \\ s.t.\ &y^i(\mathbf w^T\mathbf x^i+b)\geq1,i=1,\dots,N \end{align}

也就是说，在分类正确的情况下，样本到判别界面的距离应当大于单位1

hashtag
7.1.2 拉格朗日对偶性

hashtag
一、一般情况

对于一般的含有等式和不等式约束的最优化问题：

可以定义广义拉格朗日函数：

L(w,α,β)=f(w)+∑i=1kαigi(w)+∑i=1lβihi(w)L(w,\alpha,\beta) = f(w) + \color{blue}\sum_{i=1}^k \color{red}{\alpha_i} \color{blue}g_i(w) + \sum_{i=1}^l\color{red}{\beta_i} \color{blue}h_i(w)

上式中，αi\alpha_i和βi\beta_i分别是等式约束和不等式约束的拉格朗日乘子，并要求αi≥0\color{red}\alpha_i\geq0

那么考虑对于ww的函数：

θP(w)=max⁡α,β;αi≥0L(w,α,β)\theta_P(w) = \max_{\alpha,\beta;\alpha_i\geq0}{L(w,\alpha,\beta)}

这里下标P表示原始问题

假设存在wiw_i使得约束条件不成立（即gi(w)>0g_i(w)>0或hi(w)≠0h_i(w)\neq0），则可以通过令αi\alpha_i或βi\beta_i等于正无穷来使得θP(w)=+∞\theta_P(w)=+\infin

而若ww满足全部约束，显然可以有θP(w)=f(w)\theta_P(w) = f(w)，即：

θP(w)={f(w)w满足约束+∞其它\theta_P(w) = \begin{cases} f(w) & w满足约束 \\ +\infin & 其它 \end{cases}

那么如果考虑最小问题：

min⁡wθP(w)=min⁡wmax⁡α,β;αi≥0L(w,α,β)\min_{w}\quad\theta_P(w) = \min_{w}\max_{\alpha,\beta;\alpha_i\geq0}{L(w,\alpha,\beta)}

它与原始最优化问题是等价的，问题min⁡wmax⁡α,β;αi≥0L(w,α,β)\min\limits_{w}\max\limits_{\alpha,\beta;\alpha_i\geq0}{L({w,\alpha,\beta})}称为广义拉格朗日函数的极小极大问题。这样就将原始问题的最优解转化为了拉格朗日函数的极小极大问题。定义原始问题的最优值

p∗=min⁡xθP(w)p^* = \min_{x}\quad\theta_P(w)

为原始问题的值

hashtag
二、对偶问题

定义：

θD(α,β)=min⁡wL(w,α,β)\theta_D(\alpha,\beta) = \min_w\quad L(w,\alpha,\beta)

考虑最大化θD(α,β)\theta_D(\alpha,\beta)，即：

max⁡α,β;αi≥0θD(α,β)=max⁡α,β;αi≥0min⁡wL(w,α,β)\max_{\alpha,\beta;\alpha_i\geq0}\theta_D(\alpha,\beta) = \max_{\alpha,\beta;\alpha_i\geq0} \min_w\quad L(w,\alpha,\beta)

问题max⁡α,β;αi≥0min⁡wL(w,α,β)\max_{\alpha,\beta;\alpha_i\geq0} \min_w\quad L(w,\alpha,\beta)称为广义拉格朗日函数的极大极小问题。可以将广义拉格朗日函数的极大极小问题表示为如下约束：

max⁡α,βθD(α,β)=max⁡α,β min⁡w L(w,α,β)s.t.αi≥0,i=1,…,k\begin{align} \max_{\alpha,\beta}&\quad\theta_D(\alpha,\beta) = \max_{\alpha,\beta}\ \min_w\ L(w,\alpha,\beta) \nonumber \\ \text{s.t.}&\quad\alpha_i\geq0,i=1,\dots,k \end{align}

这一优化问题就称为原始问题的对偶问题，并定义对偶问题的最优解：

d∗=max⁡α,β;αi≥0θD(α,β)d^* = \max_{\alpha,\beta;\alpha_i\geq0}\theta_D(\alpha,\beta)

为对偶问题的值

hashtag
三、原始问题和对偶问题的关系

若原始问题和对偶问题都有最优解，则：

d∗=max⁡α,β;αi≥0min⁡wL(w,α,β)≤min⁡wmax⁡α,β;αi≥0L(w,α,β)=p∗d^* = \max_{\alpha,\beta;\alpha_i\geq0}\min_{w} L(w,\alpha,\beta) \leq \min_w \max_{\alpha,\beta;\alpha_i\geq0} L(w,\alpha,\beta) = p^*
circle-check

设w∗w^*和α∗\alpha^*，β∗\beta^*分别为原始问题和对偶问题的可行解，若d∗=p∗\color{red}d^*=p^*，则w∗w^*和α∗\alpha^*，β∗\beta^*分别是原始问题和对偶问题的最优解

hashtag
四、KKT条件

对于原始问题和对偶问题，假设f(w)f(w)和gi(w)g_i(w)是凸函数，hi(w)h_i(w)是仿射函数，并且不等式约束是严格执行的，即gi(w)<0g_i(w)<0，则存在w∗,α∗,β∗w^*,\alpha^*,\beta^*，使得ww是原始问题的解，α,β\alpha,\beta是对偶问题的解，且：

p∗=d∗=L(w∗,α∗,β∗)p^*=d^*=L(w^*,\alpha^*,\beta^*)

它的充分必要条件是以下Karush-Kuhn-Tucker（KKT）条件：

∂L(w∗,α∗,β∗)∂w=0αi∗gi(w∗)=0,i=1,…,kgi(w∗)≤0,i=1,…,kαi∗≥0hi(w∗)=0,i=1,…,l\frac{\partial L(w^*,\alpha^*,\beta^*)}{\partial w} = 0 \\ \color{red}{\alpha_i^*g_i(w^*)=0,\quad i=1,\dots,k} \\ g_i(w^*)\leq0,\quad i=1,\dots,k \\ \alpha_i^*\geq0 \\ h_i(w^*) = 0,\quad i=1,\dots,l

其中，上式中标红的部分称为KKT的对偶互补条件，总结下来就是：若强对偶（αi∗>0\alpha_i^*>0），则αi∗gi(w∗)=0\alpha_i^*g_i(w^*)=0

hashtag
7.1.3 线性SVM

支持向量：距分离超平面最近的样本

  • 输入：线性可分的数据集S={(xi,yi),i=1,…,N}S=\{(\mathbf x^i,y^i),i=1,\dots,N\}

  • 输出：判别函数及决策/判别界面

  • 最优化问题

min⁡w,b 12∥w∥22s.t. yi(wTxi+b)≥1,i=1,…,N\begin{align} \min_{\mathbf w,b}\ &\frac12\Vert\mathbf w\Vert_2^2 \nonumber \\ s.t.\ &y^i(\mathbf w^T\mathbf x^i+b)\geq1,i=1,\dots,N \end{align}

  • 分离超平面：(w∗)Tx+b∗=0(\mathbf w^*)^T\mathbf x + b^* = 0

  • 判别函数：fw,b(x)=sign((w∗)Tx+b∗)f_{\mathbf w,b}(\mathbf x) = sign((\mathbf w^*)^T\mathbf x + b^*)

circle-check

理论保证：对于线性可分的训练数据集，最大间隔分类器存在且唯一

hashtag
一、最优间隔分类器的对偶解

对于上面的最优化问题，其约束条件为：

gi(w)=−yi(wTxi+b)+1≤0,i=1,…,Ng_i(\mathbf w) = -y^i(\mathbf w^T\mathbf x^i+b) + 1 \leq 0,\quad i=1,\dots,N

由于KKT对偶互补条件为αi∗gi(w)=0\alpha_i^*g_i(w)=0，而在本问题中显然至少有一个αi≠0\alpha_i\neq0（证明略），因此满足KKT条件即要求：

gi(w∗)=0g_i(\mathbf w^*) = 0

而满足这一条件的样本就是支持向量，其距离到分离超平面的距离为单位1

circle-exclamation

支持向量的数量远小于样本数量，因此可以大大减少训练成本

将整个问题写为广义拉格朗日函数：

L(w,b,α)=12∥w∥22−∑i=1Nαi[yi(wTxi+b)−1]L(\boldsymbol w,b,\boldsymbol \alpha) = \frac12\Vert\boldsymbol w\Vert_2^2 - \sum_{i=1}^N\alpha_i[y^i(\boldsymbol w^T\boldsymbol x^i + b)-1]

那么它的对偶问题为：

θD(α)=min⁡w,bL(w,b,α)\theta_D(\boldsymbol \alpha) = \min_{w,b}L(\boldsymbol w,b,\boldsymbol \alpha)

记对偶问题的最优值为d∗d^*，令偏导数等于0，求解w∗\boldsymbol w^*和b∗b^*：

∵ ∂∂wL(w,b,α)=w−∑i=1Nαiyixi=0∴w∗=∑i=1Nαiyixi∂∂bL(w,b,α)=∑i=1Nαiyi=0\begin{align} &\because\ \frac{\partial}{\partial \boldsymbol w}L(\boldsymbol w,b,\boldsymbol \alpha) = \boldsymbol w - \sum_{i=1}^N\alpha_iy^i\boldsymbol x^i = 0 \nonumber \\ &\therefore \boldsymbol w^* = \sum_{i=1}^N\alpha_iy^i\boldsymbol x^i \\ &\quad\frac{\partial}{\partial b}L(\boldsymbol w,b,\boldsymbol \alpha) = \sum_{i=1}^N\alpha_iy^i = 0 \end{align}

带入拉格朗日函数，即有：

θD(α)=∑i=1Nαi−12∑i,j=1Nyiyjαiαj(xi)Txj\color{red}\theta_D(\boldsymbol \alpha) = \sum_{i=1}^N\alpha_i - \frac12\sum_{i,j=1}^Ny^iy^j\alpha_i\alpha_j(\boldsymbol x^i)^T\boldsymbol x^j

hashtag
二、线性可分SVM的求解过程

输入线性可分的训练数据集S={(xi,yi),i=1,…,N}S=\{(\boldsymbol x^i,y^i),i=1,\dots,N\}

首先通过求解对偶问题，得到拉格朗日乘子的最优解α∗\boldsymbol \alpha^*：

进而得到原问题的最优解：

w∗=∑i=1Nαi∗yixib∗=yj−∑i=1Nαi∗yi(xi)Txj\begin{align} &\color{red}{\boldsymbol w^* = \sum_{i=1}^N\alpha_i^*y^i\boldsymbol x^i} \nonumber \\ &\color{red}{b^* = y^j - \sum_{i=1}^N\alpha^*_iy^i(\boldsymbol x^i)^T\boldsymbol x^j} \end{align}

  • 分离超平面：(w∗)Tx+b∗=0(\boldsymbol w^*)^T\boldsymbol x + b^*=0

  • 判别函数：fw,b(w∗)Tx+b∗f_{\boldsymbol w,b}(\boldsymbol w^*)^T\boldsymbol x + b^*

circle-exclamation

  • 在计算w∗\boldsymbol w^*和b∗b^*时，只需要利用那些αi>0\alpha_i>0的那些样本（支持向量）来计算

  • 对偶技巧：只需要计算训练样本与输入特征的内积——(xi)Tx=xi⋅x(\boldsymbol x^i)^T\boldsymbol x = \boldsymbol x^i\cdot \boldsymbol x

hashtag
7.1.4 非线性可分SVM

假设

hashtag
本文中的绘图代码：

hashtag
参考

https://www.kaggle.com/code/alaapdhall/custom-svm-with-numpy-vs-sklearnarrow-up-right

上一页附 第六章作业下一页7.2 核支持向量机

最后更新于