SVM

  • 机器学习-SVM

  • 资料来源:

    http://www.bilibili.com/video/BV1pE411v7yF?p=16
    http://zh.wikipedia.org/zh-cn/%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA

  • 更新

    1
    2020.11.22 初始

导语

机器学习课一堆的 svm 作业,上课根本听不懂啊..无奈..

强烈推荐去看一下,mit 人工智能公开课-16 支持向量机,非常好的讲明白了 svm 原理.

本文尝试把 svm 的证明说明白

前提

考研高数的条件极值求法-拉格朗日乘数(子)法

SVM

svm 全名 support vector machine ,中文名 支持向量机.

简略概况 svm

  • 一个分类器
  • 求可以以最大间隔分离数据集的超平面

线性可分

$\vec w$ 垂直于超平面,$\vec u$ 是样本集任意向量

$\vec w \cdot \vec u \geq c$ 是 $\vec u$ 在 $\vec w$ 方向的投影.

$\vec w \cdot \vec u \geq c$ 假设 $c = -b$ 则有 $\vec w \cdot \vec u -b \geq 0$

我们人为规定

  • 所有正例有 $\vec w \cdot \vec x_+ - b \geq 1$ [^1] 正例 $y = 1$.
  • 对于所有反例有 $\vec w \cdot \vec x_- - b \leq -1$[^2],反例 $y = -1$.

公式 1 2 左乘 $y_i$.

  • 正例反例结果相同 $y_i(\vec w \cdot \vec x_+ - b) \geq 1$
  • 再化简有 $y_i(\vec w \cdot \vec x_+ - b) -1 \geq 0$[^3] (约束条件)
  • 对于样本集距离超平面最近的向量(支持向量)有 $y_i(\vec w \cdot \vec x_+ - b) -1 = 0$

宽度: $(\vec{x_+} - \vec{x_-}) \cdot \frac {\vec w}{|\vec w|}$ [^4]-> MAX

$\frac {\vec w}{|\vec w|}$ 单位法向量

正例 $y_i = 1$ -> 公式[^3] -> $\vec w \cdot \vec x_+ - b = 1$ -> $\vec w \cdot \vec x_+ = 1-b$

反例 $y_i = -1$ -> 公式[^3] -> $-\vec w \cdot \vec x_- - b = 1$ -> $-\vec w \cdot \vec x_- = 1+b$

带回公式[^4] ->
$$
(\vec{x_+} - \vec{x_-}) \cdot \frac {\vec w}{|\vec w|} = \frac {(\vec{x_+} - \vec{x_-}) \cdot \vec w }{|\vec w|}
= \frac {1-b + 1-b }{|\vec w|} = \frac {2}{|\vec w|}
$$

求公式[^4] max -> $\frac {2}{|\vec w|}$ max -> $|\vec w|$ min

为了方便可以将 $|\vec w|$ min -> $\frac{1}{2} |\vec w|^2$ min (极值)

约束条件有了,求极值 -> 拉格朗日乘数法.

反例

$$

$$

$\vec w \cdot \vec x + b = y_i (y_i = \pm 1)$

核函数

实例

公式

[^1]:$\vec w \cdot \vec u -b \geq 0$
[^2]:$\vec w \cdot \vec x_- - b \leq -1$
[^3]:$y_i(\vec w \cdot \vec x_+ - b) -1 \geq 0$
[^4]: $(\vec{x_+} - \vec{x_-}) \cdot \frac {\vec w}{|\vec w|}$