支持向量机

疑问：法1和法2求出来的是同一条直线吗？

当然是相同的，法2的直线两边同除以2就得到法1的直线了。

根据维基百科 ^[1] . 直线 . 维基百科. [2019-02-28]. ，直线可以用Ax+By+C=0来表示。

但这种表示形式不是唯一的。若限制\(A\geqslant 0\)，及A、B、C最大公约数为1，则可以直线用唯一形式来表示。

若把直线方程Ax+By+C=0用向量形式表示，则有\(\vec{w}\cdot \vec{x}+C=0\)。但这种表示形式也不是唯一的。对于一维直线，\(\vec{w}=\overrightarrow{(A, B)}\)，称为直线的法向量。

若有直线\(\vec{w} \cdot \vec{x}+b=0\)，点\(x_0\)为直线外一点，则点\(x_0\)相对于\(\vec{w}^\top\vec{x}+b=0\)的 单位函数距离式 ^[2] 单位函数距离式这个名字是我自创的。 为\(\vec{w_0}\cdot \vec{x}+b_0=0\)，且\(\vec{w_0}\cdot \vec{x_0}+b_0=1\)。

第一层

现有样本集合X，每一个样本\(x_i\)有类别\(y_i\)。支持向量机处理的是二分类问题，所以设\(y_i\)可以取两个值，传统上，设\(y_i\in \{+1, -1 \}\)。

支持向量机求的是能把所有点正确分类，且对所有点距离最远的超平面。

设该超平面为\(\vec{w}\cdot \vec{x}+b=0\)。

设有点\(p_1,p_1,\cdots, p_N\)，求离决侧面距离最近的点，离决侧面的距离是多少？

\[

d_{\text{min}}=\underset{1\leqslant n\leqslant N}{\min}\frac{y_n(\vec{w}\cdot \vec{x_n}+b)}{\left \| w \right \|}

\]

上式解释一下，通过变化n，令\(\frac{y_n(\vec{w}\cdot \vec{x_n}+b)}{\left \| w \right \|}\)最小。n代表了该点的序号。设该点为\(p_{\text{min}}\)。

但是决策面本身的性质要求它与所有点的距离最大，换句话说，决策面到离其最近的点的距离最大，即

\[

\begin{align}

& \underset{\vec{w},b}{\max}\ d_{\text{min}} \notag \\

=& \underset{\vec{w},b}{\max}\left\{ \underset{n}{\min}\left[\frac{y_n(\vec{w}\cdot \vec{x_n}+b)}{\left \| w \right \|}\right] \right\} \label{maxmin} \\

\end{align}

\]

上式解释一下，通过变化\(\vec{w}\)和b，令\(d_{\text{min}}\)最大。

若把超平面为\(\vec{w}\cdot \vec{x}+b=0\)看成关于\(p_{\text{min}}\)的单位函数距离式，则有\(d_{\text{min}}=\frac{1}{\left \| w \right \|}\)

等式\(\eqref{maxmin} \)可化简为\(\underset{\vec{w},b}{\max}\left( \frac{1}{\left \| w \right \|} \right)\)，相当于\(\underset{\vec{w},b}{\min}\left( \left \| w \right \| \right)\)

考虑到\(\left \| \vec{w} \right \|=\sqrt{\sum w_i^2}\)，我们改为最小化\(\left \| \vec{w} \right \|^2\)

考虑到对\(\left \| \vec{w} \right \|^2\)求导会产生系数2，我们改为最小化\(\frac{1}{2}\left \| \vec{w} \right \|^2\)。

从观察可知，l仅由两个不同类得边界分割面所穿过得点决定，如上图的1个X，两个O。两个不同类得边界分割面所穿过得点称为 支持向量 。

所有的支持向量\(x_i\)到超平面l的距离都相同，可设为d。

由定理1，始终存在w和b，令

\[\begin{equation}

\forall x_i \quad \left|\vec{w}^\top\vec{x_i}+b\right|=1

\label{绝对值1}

\end{equation}\]

。

考虑到每个\(x_i\)都有分类\(y_i\)，且\(y_i\in \{+1, -1 \}\)。可做如下假设

\[

\begin{equation}

y_i=\begin{cases}

+1 & \text{若 } \vec{w}^\top\vec{x_i}+b\geqslant 1\\

-1 & \text{若 } \vec{w}^\top \vec{x_i}+b <1 \\

\end{cases}

\label{y的分类}

\end{equation}

\]

可以对公式\(\eqref{y的分类}\)进行归一化处理，得

\[

y_i(\vec{w}^\top\vec{x_i}+b)\geqslant 1

\]

根据《向量复习》，任意一点到该决策面的距离为 \(d=\frac{\left| \vec{w}^\top\vec{x} \right |}{\left \| \vec{w} \right \|}\)。对于支持向量\(x_i\)，则有

\[\begin{equation}

d=\frac{1}{\left \| \vec{w} \right \|}

\end{equation}\]

为了最大化d，需要最小化\(\left \| \vec{w} \right \|\)。

有人会说了，这个最小化问题非常简单，\(w=\begin{bmatrix}0\\ 0\\ \vdots \\ 0 \end{bmatrix}\)就最小了。不过，你忘了我们有约束条件。最小化\(\frac{1}{2}\left \| \vec{w} \right \|^2\)的同时，还必须保证所有点正确分类呀。

所以最小化\(\frac{1}{2}\left \| \vec{w} \right \|^2\)时的约束条件为\(\forall x_i,y_i \quad y_i(\vec{w}^\top\vec{x_i}+b)\geqslant 1\)。

如果你读到现在，恭喜你，你已经打通了SVM第一层！

第二层

怎么把“能把所有点正确分类”用数学表示呢？

对任意一点\((\vec{x_i},y_i)\)，将\(x_i\)代入l，

当然，如果写成

\[

y_i=\begin{cases}

+1 & \text{ 若} \vec{w}^\top\vec{x_i}+b\leqslant 0 \\

-1 & \text{ 若 } \vec{w}^\top\vec{x_i}+b>0

\end{cases}

\]

也可以。只是\(\vec{w}\)的符号相反而已。

通过放大缩小\(\vec{w}\)和\(\vec{b}\)，可以对公式\(\eqref{y的分类}\)进行归一化处理，得

若对公式\(\eqref{y的分类}\)进行简单合并，得到的是\(y_i(\vec{w}^\top\vec{x_i}+b)\geqslant 0\)。待办：使用此公式进行推导。

如果该决策面能对所有点进行正确分类，则一定有\(\forall (\vec{x_i},y_i),\ y_i(\vec{w}^\top\vec{x_i}+b)\geqslant 1\)

如果限制\(A\geqslant 0\)，且\(A^2+B^2=1\)，也可以把直线用唯一形式来表示。

若限制\(\vec{w}\)正规化为单位向量，即\(\left\| \vec{w} \right\|=1\)，则可以把直线用唯一形式来表示。 注意 ，因为\(\vec{w}\)正规化了，C也会改变。 注意 ，本文将通篇使用向量形式来表示直线（和超平面），并要求\(\vec{w}\)为单位向量。