/ Machine Learning

总结4-支持向量机

1. 成本函数

$$ \begin {split} J\left( \theta \right) &=C\sum _{i=1}^{m}\left[ y^{\left( i\right)}cost_{1}\left(\theta^{T} f^{\left( i\right)}\right)+\left( 1-y^{\left( i\right)}\right) cost_{0} \left(\theta^{T} f^{\left( i\right)}\right)\right]+\dfrac {1} {2}\sum _{j=1}^{n}\theta _{j}^{2}\\ f &= similarity(x, l) \end {split} $$

这里的C和逻辑回归中的λ的关系为 $C = \dfrac {1} {\lambda}$ 。

2. 优化

$$ \dfrac {1} {2}\sum _{j=1}^{n}\theta _{j}^{2} = \dfrac {1} {2}(\theta_{1}^{2}+\theta_{2}^{2}+ \cdots +\theta_{n}^{2})= \dfrac {1} {2}\left(\sqrt{\theta_{1}^{2}+\theta_{2}^{2}+ \cdots +\theta_{n}^{2}}\right)^2 = \dfrac {1} {2} \left( \left \| \theta \right \| \right)^2 $$
$$ \theta^{T} x^{\left( i\right)} = P^{(i)} \left \| \theta \right \| $$

3. 核函数 Kernels

给定x,计算新特征f,取决于临近值 $l^{(1)}, l^{(2)}, l^{(3)}$ 。

$$ \begin {split} f_{1} = similarity(x, l^{(1)})&=exp\left( -\dfrac {\left \| x-l^{(1)} \right \|^{2}} {2\sigma^{2}}\right)\\ if\ x \approx l^{(1)} \ then\ f1 &\approx 1\\ if\ x \ is \ far \ from \ l^{(1)} \ then\ f1 &\approx 0\\ \end {split} $$
σ越大坡度越缓,σ越大坡度越陡。
  • 参数 $C = \dfrac {1} {\lambda}$ :

C越大,Lower Bias,High Variance,过拟合。

C越小,Higher Bias,Low Variance,欠拟合。

  • 参数 $\sigma ^{2}$ :

$\sigma ^{2}$ 越大,Features $f_{i}$ 曲线更平缓,Higher Bias,Low Variance,欠拟合。

$\sigma ^{2}$ 越小,Features $f_{i}$ 曲线更陡峭,Lower Bias,High Variance,过拟合。

注:必须做特征缩放

3.1. Gaussian Kernel

上述就是高斯核函数

$$ f = similarity(x, l)=exp\left( -\dfrac {\left \| x-l \right \|^{2}} {2\sigma^{2}}\right) $$

3.2. No Kernel(Linear Kernel)

$$ \begin {split} &\because x=l\\ &\therefore -\dfrac {\left \| x-l \right \|^{2}} {2\sigma^{2}}=0\\ &\therefore f=1 \end {split} $$
$$ Predict\ y=1\ if\ \theta^{T}x \geq 0 $$

3.3. 其他核函数

必须满足:Mercer's Theorem 莫塞尔定理

这样才可以在SVM中有效的使用各种优化和求解θ。

  • Polynomial kernel 多项式核函数

    $$ K(x,l)=\left( x^{T}l+constant\right)^{degree} $$
    通常用于x和l都为非负时!
  • More esoteric 更深奥的:String Kernel 字符串核函数,Chi-square Kernel卡方核函数,histogram intersection kernel直方图交叉核函数,...

3.4. 计算

使用第三方库进行计算

LIBLINEAR (http://www.csie.ntu.edu.tw/~cjlin/liblinear/)

LIBSVM (http://www.csie.ntu.edu.tw/~cjlin/libsvm/)

SVMLight (http://svmlight.joachims.org/)

4. 函数选择

n = number of features ($x \in \mathbb{R}^{n+1}$),m = number of training examples

  • if n is Large(相对于m):例如:n=10000,m=10~1000

    使用逻辑回归或SVMs without a kernel(linear kernel)

  • if n is small,m中等大小:例如:n=1~1000 ,m=10~10000(50000)

    使用SVMs Gaussian Kernel

  • if n is small,m is Large:例如:n=1~1000或更多点 ,m=50000+

    Create/Add more features ,使用逻辑回归或SVMs without a kernel(linear kernel)

  • Neural network
    设计一个好的神经网络可以解决上述所有问题,但它训练起来可能会很慢。