支持向量机

已知点(2,3)、(4,5),求经过这两点的直线

法1:按照《如何求直线方程

\[
k=\frac{5-3}{4-2}=1
\]

\[
\begin{align*}
y &=x+b \\
3 &= 2+b\\
b &= 1
\end{align*}
\]

所以直线为y=x+1,或x-y+1=0。

法2:按照《已知直线上两点求直线的一般式方程

A=5-3=2
B=2-4=-2
C=3*4-5*2=2

所以直线为2x-2y+2=0。

疑问:法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)}\),称为直线的法向量。

已知直线\((3,4)\cdot \vec{x}-1=0\),求证\(\vec{w}=\overrightarrow{(3,4)}\)为该直线的法向量。

设\(P_1=(x_1,y_1)\)、\(P_2=(x_2,y_2)\)在直线上,则有\((3,4)\cdot (x_1,y_1)-1=0\),\((3,4)\cdot (x_2,y_2)-1=0\)。

向量\(\overrightarrow{P_1P_2}=(x_2-x_1,y_2-y_1)\)。

\[\begin{align*}
\overrightarrow{P_1P_2}\cdot \vec{w} &= (x_2-x_1,y_2-y_1) \cdot (3,4)\\
&= 3x_2-3x_1+4y_2-4y_1\\
&= 3x_2+4y_2 -(3x_1+4y_1) \\
&= 1 – 1 \\
&= 0
\end{align*}\]

所以\(\vec{w}\)为直线的法向量。

若有直线\(\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\)。
求直线3x+4y-1=0相对于点(3,4)的单位函数距离式。

解:

\(d=\frac{3\times 3+4\times 4 -1}{\sqrt{3^2+4^2}}=\frac{24}{5}\),称此为点到直线的几何距离。

根据定义,设单位函数距离式为\(3nx+4ny-n=0\),\(\)。

\[\begin{align*}
9n+16n-n =& 1 \\
n =& \frac{1}{24}
\end{align*}\]

所以,求直线3x+4y-1=0相对于点(3,4)的单位函数距离式为\(\frac{1}{8}x+\frac{1}{6}y-\frac{1}{24}=0\)。

已知直线Ax+By+C=0是相对于点(3,4)的单位函数距离式,请画出该直线。注:按照上面的讲解,该直线有无穷多个,画出有特征的几个即可。

解:

用Mathematica,分四种条件计算。

anchorPoint = {3, 4};
k = Table[Tan[x], {x, 0, 2 Pi, 0.3}];
ContourPlot[ Evaluate[ 
  Union[ Map[ {w1, 1}.{x, y} + b == 0 /.  FindInstance[{ {w1, 1}.anchorPoint + b == 1, # == w1/1}, {w1, b}, Reals][[1]] &, k],             
	 Map[ {w1, 1}.{x, y} + b == 0 /.  FindInstance[{ {w1, 1}.anchorPoint + b == -1, # == w1/1}, {w1, b}, Reals][[1]] &, k],
	 Map[ {1, w2}.{x, y} + b == 0 /.  FindInstance[{ {1, w2}.anchorPoint + b == 1, # == 1/w2}, {w2, b}, Reals][[1]] &, Table[Tan[x], {x, 0.1, 2 Pi, 0.3}]],
	 Map[ {1, w2}.{x, y} + b == 0 /.  FindInstance[{ {1, w2}.anchorPoint + b == -1, # == 1/w2}, {w2, b}, Reals][[1]] &, Table[Tan[x], {x, 0.1, 2 Pi, 0.3}]]]],
 {x, 1, 5}, {y, 2, 6}, 
 Epilog -> {Blue, PointSize@Large, Point[anchorPoint]} , ContourStyle -> Black ]

如图可见,若x或y的系数为1,相对于点(3,4)的单位函数距离式必穿过(2,4)、(4,4)、(3,3)、(3,5)其中一点。

ContourPlot[ Evaluate[ 
  Union[Map[ {w1, 2}.{x, y} + b == 0 /. FindInstance[{ {w1, 2}.anchorPoint + b == 1, # == w1/1}, {w1, b}, Reals][[1]] &, k],
	Map[ {w1, 2}.{x, y} + b == 0 /. FindInstance[{ {w1, 2}.anchorPoint + b == -1, # == w1/1}, {w1, b}, Reals][[1]] &, k],
	Map[ {2, w2}.{x, y} + b == 0 /. FindInstance[{ {2, w2}.anchorPoint + b == 1, # == 1/w2}, {w2, b}, Reals][[1]] &, Table[Tan[x], {x, 0.1, 2 Pi, 0.3}]],
	Map[ {2, w2}.{x, y} + b == 0 /. FindInstance[{ {2, w2}.anchorPoint + b == -1, # == 1/w2}, {w2, b}, Reals][[1]] &, Table[Tan[x], {x, 0.1, 2 Pi, 0.3}]] ]],
 {x, 2, 4}, {y, 3, 5}, 
 Epilog -> {Blue, PointSize@Large, Point[anchorPoint]}  , ContourStyle -> Black ]

如图可见,若x或y的系数为2,相对于点(3,4)的单位函数距离式必穿过(2.5,4)、(3.5,4)、(3,3.5)、(3,4.5)其中一点。

以此类推,相对于点(3,4)的单位函数距离式必不穿过(3,4),必穿过(m,4)、(3,n)其中一点。

更进一步,相对于点(3,4)的单位函数距离式可穿过平面上除(3,4)外的任意一点。

第一层

现有样本集合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\)。

\[\begin{equation}
f(\vec{w})=\frac{1}{2}\left \| \vec{w} \right \|^2
\label{目标函数}
\end{equation}\]

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

所以最小化\(\frac{1}{2}\left \| \vec{w} \right \|^2\)时的约束条件为

\[\begin{equation}
\forall x_i,y_i \quad y_i(\vec{w}\cdot \vec{x_i}+b)\geqslant 1
\label{原始限制条件}
\end{equation}\]

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

第二层

拉格朗日函数

拉格朗日函数非常简单,非常简单,非常简单!!!重要的事情说三遍。不要看到天书般的名词就害怕了。

若有原始问题

\[
\underset{x}{\min}\ f(x) \qquad
\text{满足}
c_i(x)\leqslant 0 \forall i\in \{1,2,\cdots, N\}
\]

,则拉格朗日函数把以上两式合并起来

\[
L(x,\boldsymbol{\alpha})=f(x)+\sum_{i=1}^{N}\alpha_ic_i(x)
\]

\[
(\alpha_i \geqslant 0 \ \forall i \in \{1,2,\cdots, N\})
\]

注意,上面\(\boldsymbol{\alpha}\)是粗体,表示一个集合。

没了,是不是非常简单!!!

假设\(c_u(x)\)不满足条件,即\(c_u(x)>0\),我们都可以通过调整\(\alpha_u \ (\alpha_u>0)\),令\(L(x,\boldsymbol{\alpha}) \rightarrow +\infty\)。

但是如果满足满足原始问题的限制条件,拉格朗日函数退化为\(L(x,\boldsymbol{\alpha})=f(x)\)。

拉格朗日函数是不是既精妙又简单!!!

通过上面的分析我们知道,拉格朗日函数一不小心就会出现正无穷,我们来试试求它的最小值。

首先,通过改变\(\boldsymbol{\alpha}\)最大化\(L(x,\boldsymbol{\alpha})\),测试是否有点不符合约束条件。

然后,在满足约束条件的情况下,改变x,求拉格朗日函数的最小值。以上过程可表示为

\[
\underset{x}{\min}\ \underset{\boldsymbol{\alpha}}{\max} \ L(x,\boldsymbol{\alpha})
\]

这叫做拉格朗日极小极大问题

我们再看极小极大问题的对偶问题——极大极小问题

\[
\underset{\boldsymbol{\alpha}}{\max} \ \underset{x}{\min}\ L(x,\boldsymbol{\alpha})
\]

极小极大问题和极大极小问题被认为是等价的,证明从略。

现在,将公式\eqref{原始限制条件}变形

\[\begin{align}
\forall x_i,y_i \quad & & y_i(\vec{w}\cdot \vec{x_i}+b) & \geqslant 1 \notag \\
& & -y_i(\vec{w}\cdot \vec{x_i}+b) & \leqslant -1 \notag \\
& & -y_i(\vec{w}\cdot \vec{x_i}+b)+1 & \leqslant 0 \label{拉格朗日不等式} \\
\end{align}\]

于是公式\(\eqref{目标函数}\)符合拉格朗日函数的目标函数形式,公式\(\eqref{拉格朗日不等式}\)符合拉格朗日函数的不等式形式。将它们代入拉格朗日函数,得

\[
\begin{align}
L(x,\boldsymbol{\alpha}) =& \frac{1}{2}\left \| \vec{w} \right \|^2-\sum_{i=1}^{N}\alpha_i (y_i(\vec{w}\cdot \vec{x_i}+b)-1) \notag \\
=& \frac{1}{2}\left \| \vec{w} \right \|^2-\sum_{i=1}^{N}\left(\alpha_i y_i \vec{w}\cdot \vec{x_i} +\alpha_i y_i b-\alpha_i \right) \label{拉格朗日展开式} \\
\end{align}
\]

求\(f(\vec{w})\)的最小值变成了求L的最小值。当L取最小值时,L对\(\vec{w}\)和b的偏导数必为0,即

\[\begin{gather}
\frac{\partial L}{\partial \vec{w}}=\vec{w} – \sum_{i=1}^{N}\alpha_i y_i\vec{x_i}=0 \notag \\
\vec{w} = \sum_{i=1}^{N}\alpha_i y_i\vec{x_i} \label{w偏导数} \\
\frac{\partial L}{\partial b}= \sum_{i=1}^{N}\alpha_i y_i=0 \label{b偏导数} \\
\end{gather}\]

把\(\eqref{w偏导数}\text{、}\eqref{b偏导数}\)反代回\(\eqref{拉格朗日展开式}\),得

\[
\begin{align*}
L(x,\boldsymbol{\alpha}) =& \frac{1}{2}\left \| \color{Red}{ \vec{w}} \right \|^2-\sum_{i=1}^{N}\left(\alpha_i y_i \vec{w}\cdot \vec{x_i} +\alpha_i y_i b-\alpha_i y_i \right) & \text{红色部分为应用公式\eqref{w偏导数}} \\
=& \frac{1}{2}\left ( \color{Red}{\sum_{i=1}^{N}\alpha_i y_i\vec{x_i}} \right )^2-\sum_{i=1}^{N} \left( \alpha_i y_i\color{Red}{\vec{w}}\vec{x_i} +\alpha_iy_ib-\alpha_i \right) \\
=& \frac{1}{2}\left ( \sum_{i=1}^{N}\alpha_i y_i\vec{x_i} \right )^2-\sum_{i=1}^{N} \left( \alpha_i y_i\left( \color{Red}{ \sum_{i=1}^{N}\alpha_i y_i\vec{x_i}} \right)\vec{x_i} \right) – b\color{Blue}{\sum_{i=1}^{N}\alpha_iy_i} + \sum_{i=1}^{N}\alpha_i & \text{蓝色部分为应用公式\eqref{b偏导数}} \\
=& \frac{1}{2}\left ( \sum_{i=1}^{N}\alpha_i y_i\vec{x_i} \right )^2-\sum_{i=1}^{N} \left( \alpha_i y_i\vec{x_i}\left( \sum_{i=1}^{N}\alpha_i y_i\vec{x_i} \right) \right) – b\times \color{Blue}{0} + \sum_{i=1}^{N}\alpha_i \\
=& \frac{1}{2}\left ( \sum_{i=1}^{N}\alpha_i y_i\vec{x_i} \right )^2-\left( \sum_{i=1}^{N}\alpha_i y_i\vec{x_i} \right)\sum_{i=1}^{N} \left( \alpha_i y_i\vec{x_i} \right) + \sum_{i=1}^{N}\alpha_i \\
=& \frac{1}{2}\left ( \sum_{i=1}^{N}\alpha_i y_i\vec{x_i} \right )^2-\left( \sum_{i=1}^{N}\alpha_i y_i\vec{x_i} \right)^2 + \sum_{i=1}^{N}\alpha_i \\
=& \sum_{i=1}^{N}\alpha_i – \frac{1}{2}\left ( \sum_{i=1}^{N}\alpha_i y_i\vec{x_i} \right )^2\\
\end{align*}
\]

参考资料

https://zhuanlan.zhihu.com/p/31886934

https://blog.csdn.net/v_JULY_v/article/details/7624837

https://zhuanlan.zhihu.com/p/24638007

https://zhuanlan.zhihu.com/p/34811858

若有原始问题

\[
\underset{x}{\min}\ f(x) \qquad
\text{满足}
\begin{cases}
c_i(x)\leqslant 0 & \forall i\in \{1,2,\cdots, N\} \\
h_j(x)= 0 & \forall j\in \{1,2,\cdots, L\}
\end{cases}
\]

,则拉格朗日函数把以上三式合并起来

\[
L(x,\boldsymbol{\alpha},\boldsymbol{\beta})=f(x)+\sum_{i=1}^{N}\alpha_ic_i(x)+\sum_{j=1}^{L}\beta_jh_j(x)
\]

\[
\alpha_i \geqslant 0 \ \forall i \in \{1,2,\cdots, N\}
\]

\[
-\infty < \beta_j <+\infty \ \forall j \in \{1,2,\cdots, L\}
\]

注意,上面\(\boldsymbol{\alpha},\boldsymbol{\beta}\)是粗体,表示一个集合。

没了,是不是非常简单!!!

从观察可知,拉格朗日函数要求\(\alpha\)大于0,而对\(\beta\)没有要求。

假设\(c_u(x)\)不满足条件,即\(c_u(x)>0\),我们都可以通过调整\(\alpha_u \ (\alpha_u>0)\),令\(L(x,\boldsymbol{\alpha},\boldsymbol{\beta}) \rightarrow +\infty\)。

假设\(h_v(x)\)不满足条件,即\(h_v(x)\neq 0\),我们都可以通过调整\(\beta_v \ (\beta_v \text{无范围限制})\),令\(L(x,\boldsymbol{\alpha},\boldsymbol{\beta}) \rightarrow +\infty\)。

但是如果满足满足原始问题的限制条件,拉格朗日函数退化为\(L(x,\boldsymbol{\alpha},\boldsymbol{\beta})=f(x)\)。

拉格朗日函数是不是既精妙又简单!!!

通过上面的分析我们知道,拉格朗日函数一不小心就会出现正无穷,我们来试试求它的最小值。

首先,通过改变\(\boldsymbol{\alpha},\boldsymbol{\beta}\)最大化\(L(x,\boldsymbol{\alpha},\boldsymbol{\beta})\),测试是否有点不符合约束条件。

然后,在满足约束条件的情况下,改变x,求拉格朗日函数的最小值。以上过程可表示为

\[
\underset{x}{\min}\ \underset{\boldsymbol{\alpha},\boldsymbol{\beta}}{\max} \ L(x,\boldsymbol{\alpha},\boldsymbol{\beta})
\]

这叫做拉格朗日极小极大问题

我们再看极小极大问题的对偶问题——极大极小问题

\[
\underset{\boldsymbol{\alpha},\boldsymbol{\beta}}{\max} \ \underset{x}{\min}\ L(x,\boldsymbol{\alpha},\boldsymbol{\beta})
\]

极小极大问题和极大极小问题被认为是等价的,证明从略。

从观察可知,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 \|\)。

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

对任意一点\((\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}\)为单位向量。


   [ + ]

1. . 直线. 维基百科. [2019-02-28].
2. 单位函数距离式这个名字是我自创的。

发表评论

电子邮件地址不会被公开。

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)