感知机

1957年由Rosenblatt提出，是神经网络与支持向量机的基础。

感知机是根据输入实例的特征向量x对其在进行二类分类的线性分类模型：

f (x) = s i g n (w x + b)

$f(x)=sign(wx+b)$

感知机模型对应于输入空间（特征空间）中的分离超平面wx+b=0

感知机学习的策略是极小化损失函数：

m i n w, b L (w, b) = - 1 N \sum i = 1 N y i (w x i + b)

$min_{w,b}L(w,b) = - \frac{1}{N} \sum_{i=1}^{N} y_i(wx_i+b)$

这里写图片描述

损失函数对应于误分类点到分离超平面的总距离 （几何间隔）：

- 1 | | w | | \sum i = 1 N y i (w x i + b)

$- \frac{1}{||w||} \sum_{i=1}^{N} y_i(wx_i+b)$

感知机学习算法是误分类驱动的的、基于随机梯度下降的对损失函数的最优化算法，有原始形式和对偶形式。
当训练数据集线性可分时，感知机是收敛的

算法：

1. 选取初值w0, b0
2. 训练集中选取数据（xi, yi）
3. if yi(w·xi+b) <= 0：
     w := w + \alpha yixi
     b := b + \alpha yi
4. 转至2，知道训练集中没有误分类点

支持向量机

优：泛化错误率低、计算开销不大、结果易解释

缺：对参数调节和核函数的选择敏感

线性可分：可以用一条直线将两组数据分开。

超平面：将数据集分隔开的直线或平面称为超平面（hyperplane），也就是分类的决策边界。

间隔：希望找到离分隔超平面最近的点，确保它们离超平面的距离尽可能远。点到分隔面的距离称为间隔。

支持向量：离分隔超平面最近的那些点。

间隔最大化

回顾点到直线的距离公式：

d = | A x 0 + B y 0 + C 0 A 2 + B 2 - - - - - - - \sqrt |

$d = |\frac{Ax_0+By_0+C_0}{\sqrt{A^2+B^2}}|$

划分超平面用如下线性方程式描述：

w T x + b = 0

$w^T x + b = 0$
则样本空间中任意点x到超平面(w,b)的距离可写为

r = | w T x + b | | | w | |

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

线性可分、硬间隔最大化

m i n w, b 1 2 | | w | | 2

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

s . t . y i (w T x i + b) \geq 1, i = 1, 2, . . ., m

$s.t. \qquad y_i(w^Tx_i+b) \ge 1, \qquad i=1,2,...,m$

二次规划的对偶问题是：

m i n 1 2 \sum i = 1 N \sum j = 1 N α i α j y i y j (x i \cdot x j) - \sum i = 1 N α i

$min \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j(x_i \cdot x_j) - \sum_{i=1}^{N} \alpha_i$

s . t . \sum i = 1 N α i y i = 0

$s.t. \qquad \sum_{i=1}^{N} \alpha_i y_i = 0$

α i \geq 0, i = 1, 2, . . ., m

$\alpha_i \ge 0, \qquad i=1,2,...,m$

通过求解对偶问题学习线性可分支持向量机，即首先求解对偶问题的最优值\alpha，然后求最优值w、b，得出分离超平面和分类决策函数。

线性不可分、软间隔最大化

松弛变量：用来允许有些数据点可以处于分隔面的错误一侧。

线性不可分意味着某些样本点(xi,yi)不能满足函数间隔大于等于1的约束条件。为了解决这个问题，可以对每个样本点（xi,yi）引入一个松弛变量，使函数间隔加上松弛变量大于等于1.

m i n w, b, ξ i 1 2 | | w | | 2 + C \sum i = 1 m ξ i

$min_{w,b, \xi_i} \frac{1}{2} ||w||^2 + C \sum_{i=1}^m \xi_i$

s . t . y i (w T x i + b) \geq 1 - ξ i

$s.t. \qquad y_i(w^Tx_i+b) \ge 1- \xi_i$

ξ i \geq 0, i = 1, 2, . . ., m

$\xi_i \ge 0, \qquad i=1,2,...,m$

C称为惩罚参数，C大时对误分类的惩罚大，意味着不愿放弃离群点，正则化小。

对偶问题是：

m i n 1 2 \sum i = 1 N \sum j = 1 N α i α j y i y j (x i \cdot x j) - \sum i = 1 N α i

$min \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j(x_i \cdot x_j) - \sum_{i=1}^{N} \alpha_i$

s . t . \sum i = 1 N α i y i = 0

$s.t. \qquad \sum_{i=1}^{N} \alpha_i y_i = 0$

0 \leq α i \leq C, i = 1, 2, . . ., m

$0 \le \alpha_i \le C, \qquad i=1,2,...,m$

支持向量回归（support Vector Regression）

支持向量回归假设我们能容忍 f(x)与y之间最多有 \xi 的偏差，即仅当f(x)与y之间的差别绝对值大于 \xi 时才计算损失。相当于以f(x)为中心构建了一个宽带为2\xi的间隔带，若训练样本落入此间隔带，则认为是被预测正确的。

核函数（Kernel）

核方法或核技巧会将数据从一个低维空间映射到一个高维空间，可以将一个在低维空间中的非线性问题转换成高维空间下的线性问题来求解。

\phi(x)表示将x映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为：

f (x) = w T ϕ (x) + b

$f(x) = w^T \phi(x) + b$
设想一个函数，特征空间的内积等于它们在原始样本空间中通过函数k(.,.)计算的结果：

k (x i, x j) = < ϕ (x i), ϕ (x j) > = ϕ (x i) T ϕ (x j)

$k(x_i, x_j) = <\phi(x_i), \phi(x_j)> = \phi(x_i)^T \phi(x_j)$

线性核
多项式核
径向基核函数（高斯核）
拉普拉斯核
Sigmoid核

k(.,.)是定义在输入空间上的对称函数，k是核函数当且仅当对于任意数据D={x1,x2,…,xm}，“核矩阵”（kernel matrix）K总是正定的。

核函数的线性组合也是核函数
核函数的积也是核函数
任意函数乘核函数也是核函数

核技巧强大的原因：

能够使用保证有效收敛的凸优化技术来学习非线性模型，我们认为\phi是固定的，仅优化\alpha，即优化算法可以将决策函数视为不同空间中的线性函数。
核函数k的实现方法通常比直接构建\phi(x)再算点积高效很多。

序列最小优化（Sequential Minimal Optimization, SMO）

支持向量机试图通过求解一个二次优化问题来最大化分类间隔。过去，训练支持向量机常采用复杂且低效的二次规划求解方法。John Platt于1998年引入了SMO算法，通过每次优化2个alpha值来加快SVM的训练速度。

特点：不断将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，知道所有变量满足KKT条件为止。

《机器学习实战》 6
《统计学习方法》 2 7
《机器学习》 5 6
《支持向量机导论》
《深度学习》 5.7.2 P89

原文链接：https://blog.csdn.net/Shingle_/article/details/81953524