Coursera平台 Andrew Ng《Machine Learning》课程SVM一章（第7周）学习笔记。
对SVM的初步理解：一种二类分类模型，在特征空间上使类到边界间隔最大。
从 Logistic Regression 到 Support Vector Machine
对 Logistic Regression，我们有：
$$
g(z) = h_\theta(x) = \frac{1}{1 + e^{-\theta^Tx}}
$$
$$
z = \theta^Tx
$$
预测“1”当$h_\theta(x)\ge 0.5$或$z\ge 0$时；
预测“0”当$h_\theta(x)\lt 0.5$或$z\lt 0$时。
训练过程：
$$
\min\limits_\theta\frac{1}{m}\left[\sum\limits_{i=1}\limits^{m}y^{(i)}\left(-\log h_\theta\left(x^{(i)}\right)\right)+\left(1-y^{(i)}\right)\left(-\log\left(1-h_\theta\left(x^{(i)}\right)\right)\right)\right]+\frac{\lambda}{2m}\sum\limits_{j=1}\limits^{n}\theta_j^2
$$
对SVM，当$y=1$时，我们希望代价函数为$cost_1(z)$，当$z\ge 1$时，$cost_1(z)=0$；当$y=0$时，我们希望代价函数为$cost_0(z)$，当$z\le -1$时，$cost_0(z)=0$。
利用$cost_1$和$cost_0$得到新的代价函数：
$$
\frac{1}{m}\left[\sum\limits_{i=1}\limits^{m}y^{(i)}cost_1(z)+(1-y^{(i)})cost_0(z)\right]+\frac{\lambda}{2m}\sum\limits_{j=1}\limits^{n}\theta_j^2
$$
可取：
$$
cost_1(\theta^Tx^{(i)})=-\log h_\theta(x^{(i)})
$$
$$
cost_0(\theta^Tx^{(i)})=-\log (1-h_\theta(x^{(i)}))
$$
消去$m$和第二项中的$\lambda$，则训练过程为：
$$
\min\limits_\theta C\sum\limits_{i=1}\limits^{m}\left[y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})\right] + \frac{1}{2}\sum\limits_{j=1}\limits^{n}\theta_j^2
$$
训练过程以$\pm 1$为依据，预测“1”当$\theta^Tx\ge 0$时，预测“0”当$\theta^Tx\lt 0$时。
最大间隔分类器
SVM可以尝试发现一个与样本数据集有最大间隔的分类边界。考虑SVM的训练过程：
$$
\min\limits_\theta C\sum\limits_{i=1}\limits^{m}\left[y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})\right] + \frac{1}{2}\sum\limits_{j=1}\limits^{n}\theta_j^2
$$
如果我们找到了对应的参数$\theta$，使得$y=0$和$y=1$时上式的左边一项都尽量为0（即$y=0$时$\theta^Tx\le -1$，$y=1$时$\theta^Tx\ge 1$），则上式变为：
$$
\min\limits_\theta \frac{1}{2} \sum\limits_{j=1}\limits^{n}\theta_j^2
$$
s.t.$\theta^Tx^{(i)}\ge 1$ if $y^{(i)}=1$, $\theta^Tx^{(i)}\le -1$ if $y^{(i)}=0$
取向量$\vec\theta$和$\vec{x^{(i)}}$：
$$
\vec\theta = \left(\begin{matrix} \theta_0 \ \theta_1 \ \theta_2 \ \vdots \ \theta_n \end{matrix}\right),\vec{x^{(i)}} = \left(\begin{matrix} 1\x^{(i)}_1 \ x^{(i)}_2 \ \vdots \ x^{(i)}_n \end{matrix}\right)
$$
对于$y=1$一类，其“边缘”（接近分界）的数据，有$\theta^Tx^{(i)}=1$（取临界值），或$\vec\theta \vec{x^{(i)}}=1$。
又：$\min\limits_\theta \frac{1}{2}\sum\limits_{j=1}\limits^{n}\theta_j^2=\min\limits_\theta \frac{1}{2} \left|\left|\vec\theta\right|\right|^2$
故判定边界（以$\vec\theta$为法向量）与$x^{(i)}$间隔最大。
对于$y=0$一类，同理。
核函数
核函数可用于构建非线性的分类模型，用于计算新的特征。
选定“地标”(landscape)$l^{(1)},l^{(2)},l^{(3)}, \cdots$，给定训练实例$x$，计算$x$与$l^{(i)}$的“相似程度”作为新的特征$f_i$，$i=1,2,3,\cdots$。
此时的SVM决策边界为$\theta^Tf$，其中
$$
f=\left( \begin{matrix} 1 \ f_1 \ f_2 \ \vdots \ f_n \end{matrix} \right)
$$
高斯核函数
$$
f_i=similarity(x,l^{(i)})=\exp\left(-\frac{||x-l^{(i)}||^2}{2\sigma}\right)
$$
当$x$接近$l^{(i)}$时，$f_i\approx 1$；当$x$远离$l^{(i)}$时，$f_i\approx 0$。
当$\theta^Tf\ge 0$时预测“1”；当$\theta^Tf\lt 0$时预测“0”。
$l^{(i)}$的获取
设$m$为训练集的大小。
- 给出${x^{(i)},y^{(i)}},i=1,2,\cdots,m$
- 选择$l^{(i)}=x{(i)},i=1,2,\cdots,m$
- 给出训练实例$x$，计算$f_i=similarity(x,l^{(i)}),i=1,2,\cdots,m$
具有核函数的SVM
其训练过程为：
$$
\min\limits_\theta C \sum\limits_{i=1}\limits^{m} \left[y^{(i)}cost_1(\theta^Tf^{(i)}) + (1-y^{(i)})cost_0(\theta^Tf^{(i)})\right] + \frac{1}{2}\sum\limits_{j=1}\limits^{m}\theta_j^2
$$
其中，
$$
f^{(i)}= \left( \begin{matrix} 1 \ f^{(i)}_1 \ \vdots \ f^{(i)}_m \end{matrix} \right) \in \mathbb{R}^{m+1} , f^{(i)}_i=1
$$
SVM的参数选择与应用
SVM参数选择：
- $C$较大，相当于$\lambda$较小，可能导致过拟合，high variance。
- $C$较小，相当于$\lambda$较大，可能导致欠拟合，high bias。
- $\sigma$较大，导致high bias。
- $\sigma$较小，导致high variance。
使用SVM，需要选择参数$C$，选择核函数（常用高斯核函数（需要选择参数$\sigma$）、无核函数（“线性核函数”））。
Logistic Regression 与 SVM 比较
设$m$为训练集大小，$n$为特征数。
一些普遍的准则：
- 如果$n$（相较于$m$）很大，通常使用逻辑回归，或采用带线性核函数的SVM。
- 如果$n$较小，$m$中等大小（如$n$为1000，$m$为10000），采用带高斯核函数的SVM。
- 如果$n$较小，$m$较大，直接使用SVM会较慢。需要创建、增加更多的特征，然后使用逻辑回归，或带线性核函数的SVM。
神经网络在上述情况下表现较好，但计算较慢。选择SVM主要在于其代价函数是凸函数，不存在局部最小非全局最小的情况。