机器学习技法笔记01-----线性SVM支持向量机

写的文章发给老师看得到回复里面有：去看看机器学习基础知识～
最近，嗯，来一波机器学习基础～

机器学习技法主要介绍特征转换（Feature Transforms）的三个方向：
1）Embedding Numerous Features:Kernel Models
解决如何选择特征转换以及复杂度的问题
介绍SVM
2）Combining Predictive Features: Aggregation Models
找出比较具有预测性质的特征并将其结合起来
介绍AdaBoost
3）Distilling Implicit Features: Extraction Models
找出（学出）隐藏特征
介绍Deep Learning

第一讲：Linear Support Vector Machine

原理：

噪声是造成过拟合的主要原因，测量误差也是一种噪声，下图三对测量误差的容忍度更强，能容忍最多的误差，即线离点越远，就是越好的分割边界。
也可以用第二行的方式，分隔的区域越宽越好。

公式推导：

算法的目标是要找出一条能分隔两类点的线（上图中的灰色区域，一条宽线），使其宽度达到最大，公式表述如下，其中margin表示“留白”，即上图中灰线的宽度：
$\max_{\bm{w}} \qquad margin(\bm{w})\quad\quad\quad\quad\quad\quad\quad\quad\quad \\subgect\ to \qquad \bm{w}\ classifies\ every\ (\bm{x_{n}}, y_{n})\ correctly\\ \quad \qquad \qquad \qquad margin(\bm{w}) = \min_{n=1,...,N} distance(\bm{x_{n}, w})$wmax​margin(w)subgect tow classifies every (xn​,yn​) correctlymargin(w)=n=1,...,Nmin​distance(xn​,w)
由于$y_{n}$yn​和$\bm{w_Tx_{n}}$wT​xn​同号，所以上面公式可写成：
$\max_{\bm{w}} \qquad margin(\bm{w}) \quad\quad\quad\quad\quad\quad\quad\quad\quad \\ subgect\ to \qquad every\ y_{n}\bm{w^Tx_{n}} > 0 \quad\quad\quad\quad\quad\quad\quad\quad\quad \\ \ \ \ \ \qquad\qquad\quad margin(\bm{w}) = \min_{n=1,...,N} distance(\bm{x_{n}, w})$wmax​margin(w)subgect toevery yn​wTxn​>0    margin(w)=n=1,...,Nmin​distance(xn​,w)
上面distance即点到分割线的距离。
算法的目标是找到一组参数w，使margin的值最大。
下面首先探讨如何计算上面公式中的距离部分：$distance(\bm{x_{n}, w})$distance(xn​,w)。距离的计算方法以及公式推导过程如下：
这里添加w0和x0，为了便于区分，将w0表示为b，距离公式转化成如下形式：$distance(\bm{x_{n}, w},b)$distance(xn​,w,b)，因此可知h(x) = sign($\bm{w^{T}x}$wTx+b)
问题：问什么要加w0和x0？
视频中的说法是要“把x垫的高一点，塞一个x0，令x0为一个正数1，对应也塞一个w0”，为什么要做这个操作？
是对于$y = WX + b$y=WX+b这样的公式，如果没有b，那么要求直线y必须经过原点，而对于我们的预测问题没必要加这样的限制，直线可以相对于原点有任意的偏移值b，b的取值要求是使y达到最小。

计算点x到平面的最短距离（垂直距离）的推导过程：
这里假设平面上的两个点$x'，x''$x′，x′′

经过上面的计算过程，可以得到公式:
$distance(\bm{x,w},b) = \frac {1}{||\bm{w}||}|\bm{w^Tx}+b|$distance(x,w,b)=∣∣w∣∣1​∣wTx+b∣
为找到完美的平面(即两种类别的分隔面)，需满足点到该平面的距离最小。 由于$y_{n}(\bm{w^Tx_{n}}+b)>0$yn​(wTxn​+b)>0，距离公式可写成：
$distance(\bm{x,w},b) = \frac {1}{||\bm{w}||}y_{n}(\bm{w^Tx_{n}}+b)$distance(x,w,b)=∣∣w∣∣1​yn​(wTxn​+b)
那么我们的问题可以转化成：
$\max_{\bm{w},b} \qquad margin(\bm{w},b) \quad\quad\quad\quad\quad\quad\quad\quad \\ subgect\ to \qquad every\ y_{n}(\bm{w^Tx_{n}}+b) > 0 \quad\quad\quad\quad\quad\quad \\ \qquad\quad\qquad\quad\quad\quad margin(\bm{w},b) = \min_{n=1,...,N} \frac {1}{||\bm{w}||}y_{n}(\bm{w^Tx_{n}}+b)$w,bmax​margin(w,b)subgect toevery yn​(wTxn​+b)>0margin(w,b)=n=1,...,Nmin​∣∣w∣∣1​yn​(wTxn​+b)

进一步简化上式，原理是空间中有很多向量都是可以通过放缩的方式用同一个向量表示的，如3wx+3b=0和wx+b=0。
使用上面的原理，将公式放缩，令
$\min_{n=1,...,N} y_{n}(\bm{w^Tx_{n}}+b)=1$n=1,...,Nmin​yn​(wTxn​+b)=1
那么：$margin(\bm{w},b)=\frac{1}{||w||}$margin(w,b)=∣∣w∣∣1​
这样简化之后，最开始的公式就可以写成：
$\max_{\bm{w},b} \qquad \frac{1}{||w||} \qquad\qquad\qquad\qquad\qquad\quad \\ subgect\ to \qquad every\ y_{n}(\bm{w^Tx_{n}}+b) > 0 \qquad\qquad\quad \\ \min_{n=1,...,N} y_{n}(\bm{w^Tx_{n}}+b)=1$w,bmax​∣∣w∣∣1​subgect toevery yn​(wTxn​+b)>0n=1,...,Nmin​yn​(wTxn​+b)=1
进一步化简为：
$\max_{\bm{w},b} \ \frac{1}{||w||} \ \ subgect\ to \ \min_{n=1,...,N} y_{n}(\bm{w^Tx_{n}}+b)=1$w,bmax​ ∣∣w∣∣1​  subgect to n=1,...,Nmin​yn​(wTxn​+b)=1
如下图所示，对于$\min_{n=1,...,N} y_{n}(\bm{w^Tx_{n}}+b)=1$n=1,...,Nmin​yn​(wTxn​+b)=1
可以把上面这个公式转化成$y_{n}(\bm{w^Tx_{n}}+b)>=1$yn​(wTxn​+b)>=1。
对于这样转化的理由，视频中给出的解释似乎有点绕，个人觉得可以这样理解：
个人觉得上面的公式的写法有点容易造成误解，写的仔细一代点是这样的：$\max_{\bm{w},b} \ \frac{1}{||w||} \ \ subgect\ to \ （\min_{n=1,...,N} y_{n}(\bm{w^Tx_{n}}+b)）=1$maxw,b​ ∣∣w∣∣1​  subgect to （minn=1,...,N​yn​(wTxn​+b)）=1
也就是说，对于所有的（x，y），w和b的取值都应该满足使最小的$y_{i}(w^Tx_{i}+b)$yi​(wTxi​+b)的值为1，也就是$y_{n}(\bm{w^Tx_{n}}+b)>=1$yn​(wTxn​+b)>=1了。
所以公式转化为：
$\max_{\bm{w},b} \ \frac{1}{||w||} \ \ subgect\ to \ \ y_{n}(\bm{w^Tx_{n}}+b)>=1 \ for \ all \ n$w,bmax​ ∣∣w∣∣1​  subgect to  yn​(wTxn​+b)>=1 for all n
再做一点变换，将上面公式转化成更方便求解的形式：
（min x 与 min 1/2x是一样的意思）
$\min_{\bm{w},b} \ \frac{1}{2}\bm{w^Tw} \ \ subgect\ to \ \ y_{n}(\bm{w^Tx_{n}}+b)>=1 \ for \ all \ n$w,bmin​ 21​wTw  subgect to  yn​(wTxn​+b)>=1 for all n
使用上述公式找到w和b，即可得到最胖的分割线，用于后续的分类。

支持向量机（Support Vector Machine，SVM）的相关概念：

支持向量（Support Vector）：下图中分割区域边界上的点称为支撑向量，可以理解为是这些点支撑起这个灰色的分割区域。（准确的说边界的这些点是支撑向量的候选人Candidate）
Support Vector Machine：称为Machine是因为，可以将该过程看成一种方法，来找出分割区域。

如何求解

公式
$\min_{\bm{w},b} \ \frac{1}{2}\bm{w^Tw} \ \ subgect\ to \ \ y_{n}(\bm{w^Tx_{n}}+b)>=1 \ for \ all \ n$w,bmin​ 21​wTw  subgect to  yn​(wTxn​+b)>=1 for all n
称为“标准问题”，即要找到分割线1所要解决的问题，计算该问题的步骤如下：

对于公式
$\min_{\bm{w},b} \ \frac{1}{2}\bm{w^Tw} \ \ subgect\ to \ \ y_{n}(\bm{w^Tx_{n}}+b)>=1 \ for \ all \ n$w,bmin​ 21​wTw  subgect to  yn​(wTxn​+b)>=1 for all n
当问题变复杂时，很难手动的用上述的解题步骤求出最优解。实际上该问题属于二次规划问题（quadratic programming），该问题可以理解成线性规划的进阶版。将问题表示称二次规划的标准形式，就更方便解决：
如下图所示：
二次规划：最小化u向量的二次函数，系数为Q矩阵， 一次项为p。
找出一个工具QP(这种工具一般matlab之类的里面有)，将所有内容放进去，该工具可以得出问题的最优解u。

解题步骤：

$x_{n}$xn​对应线性问题，$z_{n}$zn​对应非线性问题。

这是一个吐槽：CSDN的latex公式居然用不了格式对齐？还是我的用法不对呢，为了格式好看可把我累坏了。