Hermann Cain

绕过拉格朗日乘子法理解SVM

设输入是x，模型是f，输出是$\hat y$理想的loss是

$$
L(f) = \sum_n\delta(g(x^n)\neq \hat y^n)
$$

但是没法微分，所以使用函数l做一个逼近：

$$
L(f) = \sum_n l(f(x^n), \hat y^n)
$$

常见的l有均方误差、交叉熵等。Hinge Loss的定义是$\sum_n max(0,1-\hat y^n f(x))$

模型是$f(x)=w^Tx$，其中$w=[w_i,b],x=[x_i,1]$；损失函数是Hinge Loss；和逻辑回归的差别只是损失函数。

考虑损失函数$L(f) = \sum_n max(0,1-\hat y^n f(x))+\lambda ||w||_2$，令$max(0,1-\hat y^n f(x)) = \epsilon^n$，最小化损失就要最小化$\epsilon^n$，即

$$\hat y^n f(x) >= 1-\epsilon^n$$

将$\epsilon^n$称为松弛因子。

从几何角度上来说，SVM就是找一个分隔平面，使该平面距离两类点的最小距离（即间隔）最大。有松弛因子的SVM叫做软间隔SVM。

对损失函数进行梯度下降的计算：

$$
\frac{\partial L}{\partial w} = \frac{\partial L}{\partial f}\frac{\partial f}{\partial w}= \frac{\partial L}{\partial f}x
$$

$$
w \gets w - \eta \sum \frac{\partial L}{\partial f}x
$$

分析梯度下降的式子，因为使用的是Hinge Loss，梯度很多是0，所以不是所有的x都对参数更新有贡献。剩下的对参数有贡献的x，就是支持向量。

几何上，支持向量就是决定了间隔的样本点

再看梯度下降的式子，可以发现最终的w实际上是x的线性函数，可以表示为$w=\sum \alpha_n x^n = X\bold \alpha$。于是模型可以表示为

$$
f(x)=\bold\alpha^T X^Tx=\sum \alpha_n(x^n\cdot x)=\sum \alpha K(x^n,x)
$$

$K(x^n,x)$就是核函数。于是问题转化为求$\alpha$使得loss最小。而核函数的存在则让我们在求解$\alpha$的时候不需要再去关注x，只需要关注K的结果就足以，即所谓的核技巧。

核技巧是一种泛化能力很强的转换特征的方法（另一种常见的特征转换方法是神经网络）。

几何上，当样本点线性不可分时，使用核函数K将x映射到高维空间，变得线性可分，找到超平面$\alpha$。这种方法比我们自己设计特征映射要容易得多。

常用的核函数有很多种（线性、多项式、高斯、拉普拉斯、sigmoid等），也可以自己定义，只要满足Mercer准则（半正定）就可以，这里不再赘述。

SVM进行多分类有两种方法：

SVM适合小样本，因为求解支持向量的过程对时间和空间要求较高。
SVM受噪音影响较大，因为支持向量数量本来就少。

吴恩达选取核函数的经验：