📔
国科大模式识别与机器学习笔记 2023
  • 课程概况
  • 第一章 概述
    • 1.1 概述
  • 第二章 生成式分类器
    • 2.1 模式识别与机器学习的目标
    • 2.2 正态分布模式的贝叶斯分类器
    • 2.3 均值向量和协方差矩阵的参数估计
    • 附 第二章作业
  • 第三章 判别式分类器
    • 3.1 判别式分类器与生成式分类器
    • 3.2 线性判别函数
    • 3.3 广义线性判别函数
    • 3.4 Fisher线性判别
    • 3.5 感知器算法
    • 3.6 可训练的确定性分类器的迭代算法
    • 3.7 势函数法
    • 3.8 决策树
    • 附 第三章作业
  • 第四章 特征选择和提取
    • 4.1 模式类别可分性的测度
    • 4.2 特征选择
    • 4.3 离散K-L变换
    • 附 第四章作业
  • 第五章 统计机器学习
    • 5.1 机器学习简介
    • 5.2 统计机器学习
  • 第六章 有监督学习
    • 6.1 有监督学习
    • 6.2 回归任务
    • 6.3 分类问题
    • 附 第六章作业
  • 第七章 支持向量机
    • 7.1 线性支持向量机
    • 7.2 核支持向量机
    • 7.3 序列最小优化算法
    • 附 第七章作业
  • 第八章 聚类
    • 8.1 基本概念
    • 8.2 经典聚类算法
    • 附 第八章作业
  • 第九章 降维
    • 9.1 基本概念
    • 9.2 维度选择
    • 9.3 维度抽取
  • 第十章 半监督学习
    • 10.1 基本概念
    • 10.2 半监督学习算法
  • 第十一章 概率图模型
    • 11.1 PGM简介
    • 11.2 有向图模型（贝叶斯网络）
    • 11.3 无向图模型（马尔科夫随机场）
    • 11.4 学习和推断
    • 11.5 典型概率图模型
    • 附 第十一章作业
  • 第十二章 集成学习
    • 12.1 简介
    • 12.2 Bagging
    • 12.3 Boosting
    • 附 第十二章作业
由 GitBook 提供支持
在本页
  • 7.1.1 间隔
  • 一、函数间隔
  • 二、几何间隔
  • 三、最优间隔分类器
  • 7.1.2 拉格朗日对偶性
  • 一、一般情况
  • 二、对偶问题
  • 三、原始问题和对偶问题的关系
  • 四、KKT条件
  • 7.1.3 线性SVM
  • 一、最优间隔分类器的对偶解
  • 二、线性可分SVM的求解过程
  • 7.1.4 非线性可分SVM
  • 本文中的绘图代码：
  • 参考

这有帮助吗？

在GitHub上编辑
  1. 第七章 支持向量机

7.1 线性支持向量机

7.1.1 间隔

一、函数间隔

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

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

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

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

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

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

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

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

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

二、几何间隔

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

其中，点B可以表示为：

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

由于点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 = 0wT(xi−∥w∥2​γiw​)+b=0

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

γ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)γi=yi((∥w∥2​w​)Txi+∥w∥2​b​)

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

γ=min⁡iγi, i=1,…,N\gamma = \min_i \gamma^i,\ i=1,\dots,Nγ=imin​γi, i=1,…,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}γi=∥w∥2​γ^​i​γ=∥w∥2​γ^​​

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

几何间隔具有不变性

三、最优间隔分类器

假设数据是线性可分的

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

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

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}γ,w,bmax​ s.t. ​γyi((∥w∥2​w​)Txi+∥w∥2​b​)≥γ,i=1,…,N​​

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

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}γ,w,bmax​ s.t. ​∥w∥2​γ^​​yi(wTxi+b)≥γ^​,i=1,…,N​​

进一步简化问题，令几何间隔为单位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}w,bmin​ s.t. ​21​∥w∥22​yi(wTxi+b)≥1,i=1,…,N​​

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

7.1.2 拉格朗日对偶性

一、一般情况

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

\begin{align} &\min_{w} \quad f(w) \nonumber \\ &\begin{array} {r@{\quad} l@{\quad}l} s.t. &g_i(w)\leq0, &i=1,\dots,k \\ &h_i(w) = 0, &i=1,\dots,l \end{array} \end{align}

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

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)L(w,α,β)=f(w)+i=1∑k​αi​gi​(w)+i=1∑l​βi​hi​(w)

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

那么考虑对于www的函数：

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

这里下标P表示原始问题

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

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

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

那么如果考虑最小问题：

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)}wmin​θP​(w)=wmin​α,β;αi​≥0max​L(w,α,β)

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

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

为原始问题的值

二、对偶问题

定义：

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

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

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)α,β;αi​≥0max​θD​(α,β)=α,β;αi​≥0max​wmin​L(w,α,β)

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

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}α,βmax​s.t.​θD​(α,β)=α,βmax​ wmin​ L(w,α,β)αi​≥0,i=1,…,k​​

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

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

为对偶问题的值

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

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

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^*d∗=α,β;αi​≥0max​wmin​L(w,α,β)≤wmin​α,β;αi​≥0max​L(w,α,β)=p∗

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

四、KKT条件

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

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

它的充分必要条件是以下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∂w∂L(w∗,α∗,β∗)​=0αi∗​gi​(w∗)=0,i=1,…,kgi​(w∗)≤0,i=1,…,kαi∗​≥0hi​(w∗)=0,i=1,…,l

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

7.1.3 线性SVM

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

  • 输入：线性可分的数据集S={(xi,yi),i=1,…,N}S=\{(\mathbf x^i,y^i),i=1,\dots,N\}S={(xi,yi),i=1,…,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,bmin​ s.t. ​21​∥w∥22​yi(wTxi+b)≥1,i=1,…,N​​

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

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

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

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

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

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,Ngi​(w)=−yi(wTxi+b)+1≤0,i=1,…,N

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

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

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

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

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

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]L(w,b,α)=21​∥w∥22​−i=1∑N​αi​[yi(wTxi+b)−1]

那么它的对偶问题为：

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

记对偶问题的最优值为d∗d^*d∗，令偏导数等于0，求解w∗\boldsymbol w^*w∗和b∗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}​∵ ∂w∂​L(w,b,α)=w−i=1∑N​αi​yixi=0∴w∗=i=1∑N​αi​yixi∂b∂​L(w,b,α)=i=1∑N​αi​yi=0​​

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

θ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θD​(α)=i=1∑N​αi​−21​i,j=1∑N​yiyjαi​αj​(xi)Txj

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

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

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

\begin{align} &\max_{\boldsymbol \alpha}\quad \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 \nonumber \\ &\begin{array} {r@{\quad} l@{\quad}l} s.t. & \alpha_i \geq0 &i=1,\dots,N \\ &\sum\limits_{i=1}^N\alpha_iy^i = 0 \end{array} \end{align}

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

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∗=i=1∑N​αi∗​yixib∗=yj−i=1∑N​αi∗​yi(xi)Txj​​

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

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

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

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

7.1.4 非线性可分SVM

假设

本文中的绘图代码：

import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC

X = np.array([[3, 3], [4, 3], [1, 1], [1, 0], [0, 1.8]])
y = np.array([1, 1, -1, -1, -1])

svm = SVC(kernel='linear')
svm.fit(X, y)

w = svm.coef_[0]
b = svm.intercept_[0]

plt.scatter(X[:, 0], X[:, 1], c=['b' if label == 1 else 'orange' for label in y])
ax = plt.gca()
x_lim = ax.get_xlim()
y_lim = ax.get_ylim()

# 创建网格以绘制分离超平面
xx = np.linspace(-1, 5, 30)
yy = np.linspace(-1, 5, 30)
YY, XX = np.meshgrid(yy, xx)
xy = np.vstack([XX.ravel(), YY.ravel()]).T
Z = svm.decision_function(xy).reshape(XX.shape)

# 绘制分离超平面和间隔边界
ax.contour(XX, YY, Z, colors='k', levels=[-1, 0, 1], alpha=0.5,
           linestyles=['--', '-', '--'])
# 高亮显示支持向量
ax.scatter(svm.support_vectors_[:, 0], svm.support_vectors_[:, 1], s=100,
           linewidth=1, facecolors='none', edgecolors='r')
plt.show()

参考

https://www.kaggle.com/code/alaapdhall/custom-svm-with-numpy-vs-sklearn

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

最后更新于1年前

这有帮助吗？