支持向量机 (Support Vector Machine, SVM)
目标函数
Logistic Regression:
$$\begin{equation}\begin{split}\min\{{1\over m}\sum_{i=1}^m{\{y^{(i)}[-log(h_\theta(x^{(i)}))]+(1-y^{(i)})[-log(1-h_\theta(x^{(i)}))]\}}\\+ {\lambda \over 2m}\sum_{j=1}^n\theta_j^2\}\end{split}\end{equation}$$
Support Vector Machine (with linear kernel):
$$\begin{equation}\min\{C\sum_{i=1}^m{\{y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})\}}+ {1\over2}\sum_{j=1}^n\theta_j^2\}\end{equation}$$
cost_1(左)和cost_0(右)函数的大致图像
支持向量与间隔
在样本空间中,划分超平面可通过如下线性方程来描述:
$$ \begin{equation}\vec{w}\cdot\vec{x}+b=0 \end{equation} $$
其中$\vec{w}=(w_1,w_2,\dots,w_d)$为超平面法向量；$b$为偏移项，决定超平面与原点之间的距离；
显然划分超平面可以被法向量$\vec{w}$和偏移项$b$唯一确定；并且易知$\Theta=(b, w_1,w_2,\dots,w_d)$.
假设超平面$\vec{w}\cdot\vec{x}+b=0$能将训练样本正确分类（即样本完全正确地由该超平面分割），令
$$ \begin{equation}\left\{\begin{array}{lr} \boldsymbol{w}\cdot \boldsymbol{x^{(i)}}+b \geq +1, \space\space y^{(i)}=+1 \\\boldsymbol{w}\cdot \boldsymbol{x^{(i)}}+b\leq-1, \space \space y^{(i)}=-1/0 \end{array} \right.\end{equation} $$
两个异类支持向量到超平面的距离之和为
$$ \begin{equation}\gamma={2\over ||\vec{w}||}\end{equation} $$
SVM需要在满足(23)式的条件下使得间隔最大化，也就是通过
$$ \begin{equation}\min_{\vec{w},b}{{1\over2}||\vec{w}||^2},\space\space\space\text{s.t. (23) for i = 1,2,\dots,m} \end{equation} $$
最终得到
$$ \begin{equation} f(\vec{x})=\vec{w}\cdot\vec{x}+b\end{equation} $$
核函数
现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面：
对于这样的问题，可以将样本从原始空间映射到一个更高维度的新空间，使得这个样本在新空间内线性可分。幸运的是，如果原始空间的维度有限，那么这样的高维新空间一定存在$\phi(\vec{x})$。
$$ \begin{equation} f(\vec{x})=\vec{w}\cdot\phi(\vec{x})+b\end{equation} $$
可以通过求解其对偶问题(不必知道如何得到下面公式)：
$$ \begin{equation}\max_{\vec{\alpha}}{\sum_{i=1}^m\alpha_i-{1\over2}\sum_{i=1}^m\sum_{j=1}^m}\alpha_i\alpha_jy^{(i)}y^{(j)}\phi(\boldsymbol{x^{(i)}})\phi(\boldsymbol{x^{(j)}})\end{equation} $$
其中$\vec{w}=\sum_{i=1}^m\alpha_iy^{(i)}\phi(\boldsymbol{x^{(i)}})$，$\sum_{i=1}^{m}\alpha_iy^{(i)}=0$.
求解(28)需要涉及到计算$\phi(\boldsymbol{x^{(i)}})\phi(\boldsymbol{x^{(j)}})$，这通常是困难的，但是如果存在函数$\kappa$：
$$ \begin{equation}\kappa(\boldsymbol{x^{(i)}}, \boldsymbol{x^{(j)}})=\phi(\boldsymbol{x^{(i)}})\cdot\phi(\boldsymbol{x^{(j)}})\end{equation} $$
计算$\phi(\boldsymbol{x^{(i)}})\phi(\boldsymbol{x^{(j)}})$可以通过计算核函数$\kappa(\boldsymbol{x^{(i)}}, \boldsymbol{x^{(j)}})$间接获得，代入(28)求解$\vec{\alpha}$；
最终得到
$$ \begin{equation} f(\vec{x})=\vec{w}\cdot\phi(\vec{x})+b=\sum_{i=1}^m\alpha_iy^{(i)}\phi(\boldsymbol{x^{(i)}})\phi({\vec{x}})+b=\vec{w}’\phi({\vec{x}})+b\end{equation} $$
其中$\vec{w}’=(w’_1,w’_2,\dots,w’_m)=(\alpha_iy^{(1)}\phi(\boldsymbol{x^{(1)}}),\alpha_iy^{(2)}\phi(\boldsymbol{x^{(2)}}),\dots,\alpha_iy^{(m)}\phi(\boldsymbol{x^{(m)}}))$;
且$\Theta’=(b, w’_1,w’_2,\dots,w’_m)=(b,\alpha_iy^{(1)}\phi(\boldsymbol{x^{(1)}}),\alpha_iy^{(2)}\phi(\boldsymbol{x^{(2)}}),\dots,\alpha_iy^{(m)}\phi(\boldsymbol{x^{(m)}}))$.