Loading... # Data Mining - Week4, SVM ## 4.1 间隔与支持向量 给定样本集 $D$, 分类学习基本思想是在样本空间中找到一个划分超平面, 将不同样本分开. 划分超平面可以通过线性方程表示: $$ w^Tx+b=0 $$ > 与 $y$ 无关, 是特征空间中的一条线. 将超平面可以记为 $(w, b)$, 则样本空间任意点到超平面 $(w, b)$ 的距离为 $$ r =\frac{\lvert w^Tx+b \rvert}{\lVert w \rVert} $$ 根据缩放变换, 将超平面上的点标记为 $1$; 之下的点标记为 $-1$. (即让 $|w^Tx+b|=1$) $$ \begin{cases} w^Tx_i+b \geq +1, y_i=+1 \\ w^Tx_i+b \leq -1, y_i=-1 \\ \end{cases} $$ 距离超平面**最近**的训练样本使上式的等号成立, 这些样本点称为`支持向量(Support vector)`. 两个异类的支持向量到超平面的距离和被称为 `间距(margin)`: $$ \gamma = \frac{2}{\lVert w \rVert} $$ 找到最大间隔的划分超平面, 就是找到满足约束的 $w$ 和 $b$, 使 $\gamma$ 最大. $$ \begin{aligned} &\min_{w,b} \frac{1}{2} \lVert w \rVert^2 \\ & \text{s.t.} y_i(w^Tx_i+b) \geq 1, i=1,2,3,\ldots,m. \end{aligned} \tag{4.1} $$ 即 `支持向量机(Support Vector Machine, SVM)` 的基本型. ## 4.2 对偶问题 式4.1使凸二次规划问题, 可以直接进行求解, 但复杂度较高. 对式4.1使用拉格朗日乘子法可以得到 `对偶问题(Dual Problem)`, 对式4.1的每个约束添加拉格朗日乘子 $\alpha_i \geq 0$, 问题可以写成: $$ L(w,b,\alpha)=\frac{1}{2}\lVert w \rVert ^2 + \sum^m_{i=1}\alpha_i(1-y_i(w^Tx_i+b)) $$ > 式4.1到上面的式子并非拉格朗日乘子法, 因为4.1是个不等式, 需要满足KKT条件 令 $L$ 对 $w,b$ 求偏导: $$ w=\sum^m_{i=1} \alpha_i y_i x_i $$ $$ 0 = \sum^m_{i=1} \alpha_i y_i $$ 代入 $L$ 消去 $w, b$. 得到了式4.1的对偶问题 $$ \max_\alpha \sum^m_{i=1} \alpha_i - \frac{1}{2} \sum^{m}_{i=1}\sum^{m}_{j=1} \alpha_i \alpha_j y_i y_j x_i^T x_j $$ > 运算过程: > > $$ > \begin{aligned} L(w,b,\alpha) &= \frac{1}{2}\lVert w \rVert ^2 + \sum^m_{i=1}\alpha_i(1-y_i(w^Tx_i+b)) \\ &= \frac{1}{2} w^Tw + \sum_i \alpha_i(1-y_i(w^Tx_i+b)) \\ &= \frac{1}{2} (\sum_i \alpha_i y_i x_i)^T (\sum_i \alpha_i y_i x_i) + \sum_i \alpha_i(1-y_i(\sum_j \alpha_j y_j x_j)^Tx_i+b) \\ &= \sum \alpha_i - \frac{1}{2} (\sum_i \alpha_i y_i x_i)^T (\sum_i \alpha_i y_i x_i) \\ &= \sum \alpha_i - \frac{1}{2} \sum^{m}_{i=1}\sum^{m}_{j=1}\alpha_i \alpha_j y_i y_j x_i^T x_y \end{aligned} > $$ 解出 $\alpha$ 即可求出 $w, b$ 得到模型. $$ \begin{aligned} f(x) &= w^Tx+b \\ &= \sum_{i=1}^m \alpha_i y_i x_i^T x + b \end{aligned} \tag{4.2} $$ 对训练样本 $(x_i, \hat{y_i})$, 总有 $\alpha_i=0$ 或 $y_if(x_i)=1$ - 若 $\alpha_i=0$, 则不会对 $f(x)$ 有任何的影响 - 若 $y_if(x_i)=1$, 则对应的样本点在最大间隔上, 是一个支持向量. 因此支持向量的大部分训练样本无需保留, 最终模型仅与支持向量有关. 求解式子4.2可以使用 `SMO算法` 求解 ## 4.3 核函数 4.1 和 4.2假设了训练样本是线性可分的. 若无法可分, 则需要将原始的二位空间映射到一个合适的三维空间. > 如果原始空间是有限维, 则一定存在一个高维空间使样本可分 可以设 $\phi(x)$ 是 $x$ 映射后的特征向量, 通常计算 $\phi(x)$ 是很困难的, 可以通过 `核函数(kernal function)` 来避开障碍, 例如: $$ \kappa(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle = \phi(x_i)^T\phi(x_j) $$ 这时候的对偶问题就会变为: $$ \max_\alpha \sum^m_{i=1} \alpha_i - \frac{1}{2} \sum^{m}_{i=1}\sum^{m}_{j=1} \alpha_i \alpha_j y_i y_j \kappa(x_i, x_j) $$ 原分类函数会变为: $$ f(x) = \sum^n_{i=1}\alpha_i y_i \kappa(x_i, x_j) + b $$ 因此, 在线性不可分问题中, 核函数的选择成了支持向量机的最大变数, 若选择了不合适的核函数, 则意味着将样本映射到了一个不合适的特征空间, 则极可能导致性能不佳. 同时, 核函数需要满足以下这个必要条件  yinwei核函数的构造十分困难, 通常我们都是从一些常用的核函数中选择:  核函数有以下几种特性: 1. 核函数 $\kappa_1$, $\kappa_2$ 对于任意正数 $\gamma_1$, $\gamma_2$ 的线性组合 $\kappa_1 \gamma_1+\kappa_2 \gamma_2$ 也是核函数 2. 核函数 $\kappa_1$, $\kappa_2$ 的直积 $\kappa_1 \bigotimes \kappa_2 = \kappa_1(x,z)\kappa_2(x,z)$ 也是核函数 3. 核函数 $\kappa_1$, 对于任意函数 $g(x)$, $\kappa(x,z) = g(x)\kappa_i(x,z)g(z)$ 也是核函数 #### 2.4 软间隔支持向量机 之前都是假定样本集在样本空间中是线性可分的, 但是通常现实任务很难确定合适的核函数使其线性可分. 即使恰好找到了核函数也有可能造成过拟合. 缓解问题的一个办法是允许向量机在一些样本上出错. - `硬间隔(Hard margin)`: 所有样本必须划分成功; - `软间隔(Soft margin)`: 允许某些样本不满足约束, 即 $y_i(w^Tx_i+b) \geq 1$ 在最大化间隔的同时, 应当使不满足的样本尽可能的少. 优化目标可以写为 $$ \min_{w, b} \frac{1}{2} \lVert w \rVert^2 + C \sum_{i=1}^m l(y_i(w^Tx_i+b) - 1)\tag{2.3} $$ > $l(z)$ 为损失函数, 常见的损失函数有: > > - 0/1损失 > - hinge损失 > - 指数损失 > - 对率损失 - 当 $C$ 为无穷大时, 所有样本均满足约束条件 - 当 $C$ 取有限值时, 允许部分样本出现误差(不满足约束) 更通常的, 将式2.3写成 $$ \min_{f} \Omega(f)+C\sum^m_{i=1} l(f(x_i),y_i) $$ 其中: - $\Omega(f)$ 称为 `结构风险(structural risk)`, 用于描述模型 $f$ 的某些性质 - $\sum^m_{i=1} l(f(x_i),y_i)$ 称为 `经验风险(expirical risk)`, 用于描述数据的契合程度 - $C$ 用于对两者进行折中 最后修改：2021 年 10 月 21 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏