机器学习-支持向量机

学习笔记机器学习

字数统计: 536阅读时长: 2 min

 2022/04/27  11

周志华西瓜书学习笔记

间隔与支持向量

超平面 $(w, b)$ ，样本空间任意一点 $x$ 到超平面的距离公式：

$r = \frac{| w^{⊤} x + b |}{| | w | |}$

分子表示点到超平面的有向距离，分母表示超平面法向量 $w$ 的范数（长度）。

对于二分类问题，给定一个训练样本集 $D = (x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{m}, y_{m}), y_{i} \in - 1, + 1$ . 假设超平面能够将训练样本正确分类，即对于 $(x_{i}, y_{i}) \in D$ ，若 $y_{i} = + 1$ ，则有 $w^{⊤} x_{i} + b > 0$ ；反之则小于0. 令

$w^{⊤} x_{i} + b \geq + 1, y_{i} = + 1$

$w^{⊤} x_{i} + b \leq - 1, y_{i} = - 1$

满足约束条件的距离超平面最近的这几个训练样本点被称为“支持向量” ；

两个边界之间的距离是 $Γ = \frac{2}{| | w | |}$ ，称为间隔。

我们要做的事情是找到满足约束条件的 $w$ 和 $b$ 参数，使得对应的间隔最大来划分超平面，根据间隔公式，我们只需要最大化 $| | w | |^{- 1}$ ，即最小化 $| | w | |^{2}$ ，即：

$min_{w, b} \frac{1}{2} | | w | |^{2}$

$s . t . y_{i} (ω^{⊤} x_{i} + b) \geq 1, i = 1, 2, \dots, m .$

使用拉格朗日乘子法得到其对偶问题，即为上述式子的每条约束添加拉格朗日乘子 $α_{i} \geq 0$ ，则问题可以改写为：

$L (ω, b, α) = \frac{1}{2} | | ω | |^{2} + \sum_{i = 1}^{m} α_{i} (1 - y_{i} (ω^{⊤} x_{i} + b))$

其中 $α = (α_{1}; α_{2}; \dots; α_{m})$ ，对 $ω$ 和 $b$ 求偏导并令偏导为0，可得到：

$ω = \sum_{i = 1}^{m} α_{i} y_{i} x_{i}$

$0 = \sum_{i = 1}^{m} α_{i} y_{i}$

将第一个式子代入拉格朗日函数消去w和b，再考虑第二个式子的约束条件，可得到原问题的对偶问题：

$max_{α} \sum_{i = 1}^{m} α_{i} - \frac{1}{2} \sum_{i = 1}^{m} \sum_{j = 1}^{m} α_{i} α_{j} y_{i} y_{j} x_{i}^{⊤} x_{j}$

$s . t . \sum_{i = 1}^{m} α_{i} y_{i} = 0, α_{i} \geq 0, i = 1, 2, \dots, m .$

Next Post

机器学习-集成学习
Previous Post

机器学习-决策树

CATALOG

1. 间隔与支持向量