支持向量机（Support Vector Machine, SVM）是一种二分类模型，其基本模型是定义在特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化。SVM 通过间隔最大化，可以使得模型对噪声更加鲁棒，从而提高模型的泛化能力。
和逻辑回归一样，支持向量机是一个二分类模型，且其也是个线性模型，即其分割超平面为
线性可分是指存在一个超平面可以将数据集完全分割开，即正类在超平面的一侧，负类在超平面的另一侧。
在下面我们将首先讨论线性可分情况下的支持向量机。再介绍线性不可分的情况。
在一切开始前，我需要先介绍一下点到（超）平面（后简称平面）的距离。
我们定义平面
我们想要知道怎么计算点
取平面任意一点
向量
令法向量
$$ \begin{align} \overrightarrow{PQ}\cdot \mathbf{n} &= |\overrightarrow{PQ}||\mathbf{n}|\cos \theta\
|\overrightarrow{PQ}|\cos \theta &= \frac{\mathbf{n}}{|\mathbf{n}|} \cdot \overrightarrow{PQ} \ \end{align} $$
因此则有：
$$ \begin{align} \text{dist}(Q, H) &= \frac{\mathbf{n}}{|\mathbf{n}|} \cdot \overrightarrow{PQ} \ &= \frac{\mathbf{w}}{||\mathbf{w}||} \cdot (\mathbf{q} - \mathbf{p})\ &= \frac{1}{||\mathbf{w}||} \cdot (\mathbf{w}^T\mathbf{q} - \mathbf{w}^T\mathbf{p})\ &= \frac{1}{||\mathbf{w}||} \cdot (\mathbf{w}^T\mathbf{q} + b - (\mathbf{w}^T\mathbf{p}+b))\ \because \quad& \mathbf{w}^T\mathbf{p}+b=0\ \therefore \quad \text{dist}(Q, H) &= \frac{1}{||\mathbf{w}||} \cdot (\mathbf{w}^T\mathbf{q} + b)\ &= \frac{\mathbf{w}^T\mathbf{q} + b}{||\mathbf{w}||}
\end{align}
$$
定义距离公式
我们定义间隔
我们定义所有点都被正确分类，即
即如果分类正确，$y_i(\mathbf{w}^T\mathbf{x}_i+b)>0$，如果分类错误，$y_i(\mathbf{w}^T\mathbf{x}_i +b )\leq0$。考虑
$$ \begin{align} {\mid \mathbf{w}^T\mathbf{x}_i + b\mid} &\rightarrow y_i(\mathbf{w}^T\mathbf{x}_i+b) > 0\
&\Downarrow\
\gamma_i &=\frac{\mid h(\mathbf{x}_i) \mid}{||\mathbf{w}||} \ &=\frac{y_i(\mathbf{w}^T\mathbf{x}_i+b)}{||\mathbf{w}||} \end{align} $$
最小化距离 $$ \begin{align} & \argmax_{\mathbf{w}, b}{\min_n \gamma_n}\ \text{where} &\quad \gamma_n = \frac{1}{||\mathbf{w}||}\ s.t. &\quad \forall (\mathbf{x}_i, y_i)\in \mathcal{D}.\quad y_i h(\mathbf{x}_i)>0 \end{align} $$
如果我们定义间距的物理距离为
$$ \begin{align} \gamma_i &= \frac{| \mathbf{w}^T\mathbf{x}i |}{|\mathbf{w}|} \ &\downarrow \ \gamma_i &= \frac{1}{|\mathbf{w}|} \end{align} $$ 因此可以改写问题 $$ \begin{align} & \argmax{\mathbf{w}, b}\left{\min_n \frac{1}{||\mathbf{w}||}\right}\ s.t. \quad& \forall (\mathbf{x}_i, y_i)\in \mathcal{D}.\quad y_i h(\mathbf{x}_i)>0 \end{align} $$
我们对
$$ \begin{align}
& \argmin_{\mathbf{w}, b}\left{\frac{1}{2}|| \mathbf{w} ||^2\right}\ s.t. \quad& \forall (\mathbf{x}_i, y_i)\in \mathcal{D}.\ &y_i(\mathbf{w}^T\phi(\mathbf{x}_i)+b)\geq1 \end{align} $$
考虑原问题
$$ \begin{align}
& \argmin_{\mathbf{w}, b}\left{\frac{1}{2}|| \mathbf{w} ||^2\right}\ s.t. \quad& \forall (\mathbf{x}_i, y_i)\in \mathcal{D}.\ &y_i(\mathbf{w}^T\phi(\mathbf{x}_i)+b)\geq1 \end{align} $$
我们可以定义一个惩罚函数
$$ \begin{align} & \argmin_{\mathbf{w}, b}\left{\frac{1}{2}|| \mathbf{w} ||^2 + g(\mathbf{w}, b)\right} \end{align} $$ 这样我们就可以把原问题转化为一个无约束问题。
我们首先改写约束条件：
这次改写使得约束条件变为了一个不等式，xxxxx
我们可以定义惩罚函数为
$$
\begin{align}
& g(\mathbf{w}, b) = \sum_{i=1}^N \alpha_i(1-y_i(\mathbf{w}^T\phi(\mathbf{x}_i)+b))\
s.t. \quad& \alpha_i \geq 0
\end{align}
$$
我们称
- 当
$\mathbf{x}_i$ 不是支持向量，即$\alpha_i = 0$ ，这个点对于最终的分类没有影响 - 当
$\mathbf{x}_i$ 是支持向量，即$\alpha_i > 0$ ，这个点对于最终的分类有影响
当
我们希望使得所有违反约束的点的惩罚尽可能大，即我们希望最大化这些惩罚，因此我们可以改写惩罚函数为：
xxxx $$ \begin{align} &\argmin_{\mathbf{w}, b}\left{\frac{1}{2}|| \mathbf{w} ||^2+ \max_\alpha\sum_{n=1}^N\alpha_n(1-y_n(\mathbf{w}^T\phi(\mathbf{x}_n)+b)) \right}\ s.t. \quad &y_n(\mathbf{w}^T\phi(\mathbf{x}_n)+b)\geq1\ &\alpha_n\geq0 \end{align} $$
我们对其进行求导，即
$$ \begin{align} \frac{\partial \mathcal{L}}{\partial \mathbf{w}} &= \mathbf{w} - \sum_{n=1}^N \alpha_n y_n \phi(\mathbf{x}n) = 0\ \mathbf{w} &= \sum{n=1}^N \alpha_n y_n \phi(\mathbf{x}n) \ \frac{\partial \mathcal{L}}{\partial b} &= -\sum{n=1}^N \alpha_n y_n = 0\ \end{align} $$
将
$$ \begin{align} &\argmax_\alpha \mathcal{L}(\alpha)=\sum^N_{n=1}\alpha_n- \frac{1}{2}\sum^N_{n=1}\sum^N_{m=1} \alpha_n\alpha_my_ny_m\phi(\mathbf{x}_n)^T\phi(\mathbf{x}_m)\
s.t.\quad &\alpha_n\geq 0\ &\sum^N_{n=1}a_ny_n=0 \end{align} $$
我们定义核函数
$$ \begin{align} &\argmax_\alpha \mathcal{L}(\alpha)=\sum^N_{n=1}\alpha_n- \frac{1}{2}\sum^N_{n=1}\sum^N_{m=1} \alpha_n\alpha_my_ny_m\kappa(\mathbf{x}_n, \mathbf{x}_m)\
s.t.\quad &\alpha_n\geq 0\ &\sum^N_{n=1}a_ny_n=0\ \text{where}\quad &\kappa(\mathbf{x}_n, \mathbf{x}_m)=\phi(\mathbf{x}_n)^T\phi(\mathbf{x}_m) \end{align} $$