非线性假设能够更好的建立分类模型，更好的拟合现实数据，但当特征量太多时非线性的计算量会非常的大，普通的逻辑回归模型不能有效地处理这么多的特征，支持向量机可以有效的解决此类的非线性问题。
支持向量机（Support Vector Machine）是一种二类分类模型：基本模型定义为特征空间上的间隔最大的线性（或非线性）分类器，学习策略便是间隔最大化，将问题最终转化为一个凸二次规划问题的求解。

2.5.1 了解支持向量机

线性分类起源：

逻辑回归：将特性的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。因此使用Sigmoid函数将自变量映射到(0,1)上，映射后的值被认为是属于y=1的概率：

$$h_θ (x)=g(z)=g(θ^T X)=\frac {1}{1+e^{-θ^T X}}=
\begin{cases}
    1\ \ \ \ \ \ 若y=1希望h_θ (x)≈1,θ^T X≫0 )     \\
    0\ \ \ \ \ \ 若y=0希望h_θ (x)≈0,θ^T X≪0)
\end{cases}
$$

线性分类函数：将结果标签$y=0$和$y=1$替换为$y=-1, y=1$，然后将$θ_1 x_1+θ_2 x_2+⋯θ_n x_n$替换成$W^T X$，将$θ_0$替换成$b$:

 $$g(z)=g(W^T X+b)=\frac {1}{1+e^{W^T X+b}}=
\begin{cases}
    1\ \ \ \ \ \ \ 若y=1,W^T X+b≫0\    \\
    -1\ \ \ \ \ \ 若y=0,W^T X+b≪0) 
\end{cases}
$$

线性函数在一维空间里就是一个点，在二维空间里就是一条直线，三维空间里就是一个平面，如果不关注空间的维数，这种线性函数还有一个统一的名称“超平面”。

线性分类器：

描述：给定一些数据点，它们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类。若用$x$表示数据点，用$y$表示类别（y可以取1或者-1代表两个类），一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面，其方程表示为： $W^T X+b=0$

直观理解：

假设有一个二维平面，平面上有两种不同的数据，分别用圈和叉表示，假设可以用一条直线将这两类数据分开，这条直线就相当于一个超平面，超平面一边的数据点所对应的y全是-1，另一边所对应的$y$全是1。
这个超平面可以用分类函数$f(x)=w^T x+b$表示，当$f(x)=0$时，$x$便是位于超平面上的点，而$f(x)>0$的点对应$y=1$的数据点，$f(x)<0$的点对应$y=-1$的点。
在进行分类的时候，遇到一个新的数据点$x$，将$x$代入$f(x)$中，如果$f(x)<0\$则将x的类别赋为-1，如果\$f(x)>0$则将x的类别赋为1。
直观而言这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以得寻找有着最大间隔的超平面。

函数间隔：

$γ ̂=y(w^T x+b)=yf(x)$

在超平面$w^T x+b=0$确定的情况下，$|w^T x+b|$能够表示点$x$到距离超平面的远近.
通过观察$w^T x+b$的符号与类标记$y$的符号是否一致可判断分类是否正确，可以用$y(w^T x+b)$的正负性来判定或表示分类的正确性。
超平面$(w,b)$关于所有样本点$ (x^{(i)} , y^{(i)}) $的函数间隔最小值，便为超平面关于训练数据集T的函数间隔： $γ ̂=min_{i=1,2…n} γ ̂^{(i)}$

几何间隔：

$γ ̃=γ ̂/‖w‖$

函数间隔存在的问题：若成比例的改变$w$和$b$（如将它们改成$2w$和$2b$），则函数间隔的值$f(x)$却变成了原来的2倍，虽然此时超平面没有改变。
几何间隔就是函数间隔除以$‖w‖$，而且函数间隔$y(w^T x+b)=yf(x)$实际上就是$|f(x)|$，几何间隔$|f(x)|⁄‖w‖ $才是直观上的点到超平面的距离。

大间距分类器：

描述：当超平面离数据点的“间隔”越大，分类的确信度也越大。所以，为了使得分类的确信度尽量高，需要让所选择的超平面能够最大化这个“间隔”值。这个间隔就是图中Gap的一半。

公式推导：最大间隔分类器的目标函数可以定义为

$$
    \begin {cases}
    max_i γ ̃= max_i γ ̂/‖w‖ \\
    γ ̂^{(i)} = y^{(i)} (w^T x^{(i)}+b)≥γ ̂\ \ \ \ \ \  (i=1,…n)
    \end {cases}
$$
为了方便推导和优化，令γ ̂=1，且这样做对目标函数的优化没有影响：
$$
    \begin {cases}
    max_i\ γ ̃= max\ 1/‖w‖ =min\ ⁡   w^2    \\
    γ ̂^{(i)} = y^{(i)} (w^T x^{(i)}+b)≥1 \ \ \ \ \  (i=1,…n)
    \end {cases}
$$

直观理解：中间的实线便是寻找到的最优超平面，其到两条虚线边界的距离相等，这个距离便是几何间隔$γ ̃$，两条虚线间隔边界之间的距离等于$2γ ̃$，而虚线间隔边界上的点则是支持向量。由于这些支持向量刚好在虚线间隔边界上，所以它们满足$y(w^T x+b)=1$，而对于所有不是支持向量的点，则显然有$y(w^T x+b)>1$

2.5.2 支持向量机推导

逻辑回归代价函数：

$Cost(h_θ (x),y)=-y logh_θ (x)-(1-y) log(1-h_θ (x))\\ =-y log(1/(1+e^{-θ^T X} ))-(1-y)log(1-1/(1+e^{-θ^T X}))$ $\begin {cases} 若y=1，希望Ζ=θ^T X≫0：Cost(h_θ (x),y)=-log(1/(1+e^{-θ^T X} )) \\ 若y=0，希望Ζ=θ^T X≪0：Cost(h_θ (x),y)=- log(1-1/(1+e^{-θ^T X})) \end {cases}$

支持向量机代价函数：

由逻辑回归到支持向量机，修改代价函数曲线如下：

$h_θ (x)= \begin {cases} 1\ \ \ \ \ if\ Ζ= θ^T X≥1 \\ 0\ \ \ \ \ if Ζ= θ^T X<-1 \end {cases}$ $min_θ C ∑_{i=1}^m (y^{(i)} cost_1 (θ^T x^{(i) } )+(1-y^{(i)}) cost_0 (θ^T x^{(i)})) + \frac {1}{2} ∑_{j=1}^n θ_j^2$

支持向量机可以看作是大间距分类器：若C非常大，则最小化代价函数的时候，将会很希望找到一个使第一项为0 的最优解：$y^{(i)} cost_1 (θ^T x^{(i) } )+(1-y^{(i)}) cost_0 (θ^T x^{(i)})≈0$

训练样本$y=1$，需要找到一个$θ$，使得$θ^T x≥1$； $y=0$，需要找到一个$θ$，使得$θ^T x≤-1$。
当求解这个优化问题的时候，会得到一个非常有趣的决策边界。 $y^{(i)} cost_1 (θ^T x^{(i) } )+(1-y^{(i)}) cost_0 (θ^T x^{(i)})≈0\\ → min\ 1/2 ∑_{j=1}^n θ_j^2$

关于C值选择：

$C$不要设置太大，当 $C$不是非常非常大时，可忽略掉一些异常点的影响，得到更好的决策界
$C≈1/λ$：$C$较大时，相当于$λ $较小，可能会导致过拟合，高方差。$C$较小时，相当于$λ $较大，可能会导致低拟合，高偏差。

2.5.4 核函数

什么是核函数？

SVM在处理非线性分类边界问题时，通过选择一个核函数，将数据映射到高维空间，来解决在原始空间中线性不可分的问题。

在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。将$γ ̂^{(i)} = y^{(i)} (w^T x^{(i)} + b)≥1\ \ \ \ \ (i=1,…n)$中的$x$换为高维空间。

核函数解决非线性分类边界问题的思路：

给定一个训练实例$x$，利用x的各个特征与预先选定的地标 $ ι^{(1)}, ι^{(2)}, ι^{(3)} $ 的近似程度来选取新的特征$f_1,f_2,f_3$
$f_1=similarity(x,ι^{(1)})$ $f_2=similarity(x,ι^{(2)})$ $f_3=similarity(x,ι^{(3)})$
$similarity(x,ι^{(i)} )$就是核函数，选择一核函数，记为$K(x,ι^{(i)})$，利用核函数模型计算新特征，若选用的核函数为高斯核函数，则：
$f_1=similarity(x,ι^{(1)})=K(x,ι^{(1)})=exp(-||x-ι^{(1)}||^2/(2σ^2 ))$ $f_2=similarity(x,ι^{(2)})=K(x,ι^{(2)})=exp(-||x-ι^{(2)}||^2/(2σ^2 ))$ $f_3=similarity(x,ι^{(3)})=K(x,ι^{(3)})=exp(-||x-ι^{(3)}||^2/(2σ^2 ))$

含义：若$x≈ι^{(1)}，f_1≈1$；若$x\ \ far \ \ from \ \ \ ι^{(1)},f_1≈0$ 随着$x$的改变$ f $值改变的速率受到$ σ^2$的控制。
$\$ σ^2\$$

核函数实现支持向量机新特性：

选择地标：通常是根据训练集的数量选择地标的数量，即如果训练集中有$m$个实例 $ (x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}) ,…, (x^{(m)}, y^{(m)}) $ ，则选取$m$个地标，并且令： $ι^{(1)} = x^{(1)}, ι^{(2)} = x^{(2)} ,…, ι^{(m)} = x^{(m)}$ ,得到的新特征是建立在原有特征与训练集中所有其他特征之间距离的基础之上。

计算新的特征向量：对于特定的训练实例 $x^{(i)}$计算新的特征向量 $f^{(i)}$

$$
    f^{(i)}=
    \begin {cases}
        f_0^{(i)}=1     \\
        f_1^{(i)}=similarity(x^{(i)},ι^{(1)} )  \\
        f_2^{(i)}=similarity(x^{(i)},ι^{(2)} )  \\
        ... \\
        f_i^{(i)}=similarity(x^{(i)},ι^{(i)} )=e^0=1  \\
        ... \\
        f_m^{(i)}=similarity(x^{(i)},ι^{(m)} )  \\
    \end {cases}
$$

SVM代价函数：

$min_θ C∑_{i=1}^m (y^{(i)} cost_1 (θ^T f^{(i) } )+(1-y^{(i)}) cost_0 (θ^T f^{(i)})) + 1/2 ∑_{j=1}^n θ_j^2$

在具体实施过程中，需要对最后的归一化项进行些微调整：$∑_{j=1}^{n=m} θ_j^2 =θ^T θ$
根据不同的核函数选择矩阵$M$：$θ^T Mθ$代替$θ^T θ$，简化计算。
理论上讲，可以在逻辑回归中使用核函数，但使用$M$来简化计算的方法不适用与逻辑回归，因此计算将非常耗费时间。

2.5.5 使用支持向量机

最小化支持向量机的代价函数可以使用现有的软件包，如liblinear，libsvm 等.

选择支持向量机求解代价函数参数$θ$，需要做的工作：

选择合适的代价函数中的参数C：

$C$较大时，相当于$λ $较小，可能会导致过拟合，高方差。
$C$较小时，相当于$λ $较大，可能会导致低拟合，高偏差。

选择合适的核函数：核函数需要满足Mercers定理，才能被支持向量机的优化软件正确处理

线性核函数（无核函数）：当$θ^T x≥0$时，预测$y=1 $。当不需要采用非常复杂的核函数，或训练集特征非常多，实例非常少的时候，可以采用这种不带核函数的支持向量机。
高斯核函数：
- 需要选择合适的$σ$：$σ$较大时，导致高方差；$σ$较小时，导致高偏差。
- 需要进行特征缩放： $||x-ι||^2=(x_1-ι_1)^2+(x_2-ι_2)^2+⋯+(x_n-ι_n)^2$
多项式核函数（Polynomial Kernel）：</br>$f=similarity(x,ι)=K(x,ι)=(x^T ι+constant)^{degree}$
字符串核函数（String kernel）、卡方核函数（chi-square kernel）、直方图交集核函数（histogram
```
 intersection kernel）
```

支持向量机多类分类问题：

多类分类问题：若一共有$k$个类，则需要$k$个模型，以及$k$ 个参数向量$θ$。
同样也可以训练$k$个支持向量机来解决多类分类问题。但是大多数支持向量机软件包都有内置的多类分类功能，只要直接使用即可。