Coursea-吴恩达-machine learning学习笔记（十二）【week 7之Support Vector Machines】

逻辑回归的代价函数如下：
J(θ)=minθ1m[∑i=1my(i)(−log(hθ(x(i))))+(1−y(i))(−log(1−hθ(x(i))))]+λ2m∑j=1nθ2j$J(\theta )=\underset{\theta }{min}\frac{1}{m}[\sum _{i=1}^m{y}^{(i)}(-log(h_{\theta }(x^{(i)})))+(1-y^{(i)})(-log(1-h_{\theta }(x^{(i)})))]+\frac{\lambda }{2m}\sum _{j=1}^n{\theta }_j^2$

对于支持向量机来说：
将−log(hθ(x(i)))$-log(h_{\theta }(x^{(i)}))$替换为cost1(θTx(i))$cos{t}_1({\theta }^T{x}^{(i)})$，如下图：

将−log(1−hθ(x(i)))$-log(1-h_{\theta }(x^{(i)}))$替换为cost0(θTx(i))$cos{t}_0({\theta }^T{x}^{(i)})$，如下图：

去掉1m$\frac{1}{m}$常量以及正则项的λ$\lambda$参数，转而在第一项前加上C$C$系数，则得到支持向量机的代价函数：
J(θ)=minθC[∑i=1my(i)cost1(θTx(i))+(1−y(i))cost0(θTx(i))]+12∑j=1nθ2j$J(\theta )=\underset{\theta }{min}C[\sum _{i=1}^m{y}^{(i)}cos{t}_1({\theta }^T{x}^{(i)})+(1-y^{(i)})cos{t}_0({\theta }^T{x}^{(i)})]+\frac{1}{2}\sum _{j=1}^n{\theta }_j^2$

假设函数：

不同于逻辑回归输出概率，支持向量机的假设函数直接预测y$y$的取值。

根据cost1(θTx(i))$cos{t}_1({\theta }^T{x}^{(i)})$及cost0(θTx(i))$cos{t}_0({\theta }^T{x}^{(i)})$的坐标图，为了最小化支持向量机(SVM)的代价函数，需满足以下条件：

支持向量机不仅正确地区分输入的正负样本，还加入了一个安全的间距因子，因此具有鲁棒性，也称其为大间距分类器。

在支持向量机的代价函数中：

• C$C$值如果设置很大，支持向量机易受到异常点的影响；
• C$C$值如果设置很小，支持向量机会忽略异常点的影响。

设存在两个二维向量：

则向量的内积：u⋅v=uT∗v=p∗∥u∥=u1∗v1+u2∗v2$u\cdot v=u^T\ast v=p\ast \Vert u\Vert =u_1\ast v_1+u_2\ast v_2$
p$p$是向量v$v$投射到u$u$上的长度，∥u∥$\Vert u\Vert$是向量u$u$的长度=u21+u22−−−−−−√$=\sqrt{u_1^2+u_2^2}$
p$p$是带符号的，若u$u$与v$v$在坐标系内的夹角为θ(0⩽θ⩽π)$\theta (0⩽\theta ⩽\pi )$，则u⋅v=∥u∥∗∥v∥∗cosθ$u\cdot v=\Vert u\Vert \ast \Vert v\Vert \ast cos\theta$

当支持向量机的代价函数中，C$C$取值较大时，为了最小化代价函数，我们会找到令∑i=1my(i)cost1(θTx(i))+(1−y(i))cost0(θTx(i))$\sum _{i=1}^m{y}^{(i)}cos{t}_1({\theta }^T{x}^{(i)})+(1-y^{(i)})cos{t}_0({\theta }^T{x}^{(i)})$为0$0$的最优解，则目标函数变为

进行如下简化：特征数n$n$设为2，令θ0=0${\theta }_0=0$
目标函数可写作：12(θ21+θ22)=12(θ21+θ22−−−−−−√)2=12∥θ∥2$\frac{1}{2}({\theta }_1^2+{\theta }_2^2)=\frac{1}{2}(\sqrt{{\theta }_1^2+{\theta }_2^2}{)}^2=\frac{1}{2}\Vert \theta {\Vert }^2$
θTx(i)=p(i)⋅∥θ∥=θ1x(i)1+θ2x(i)2${\theta }^T{x}^{(i)}=p^{(i)}\cdot \Vert \theta \Vert ={\theta }_1{x}_1^{(i)}+{\theta }_2{x}_2^{(i)}$
则条件变为：

p(i)$p^{(i)}$为x(i)$x^{(i)}$投射到θ$\theta$的长度，θ$\theta$向量与分界线垂直。
由于目标函数是令12∥θ∥2$\frac{1}{2}\Vert \theta {\Vert }^2$尽可能小，同时要满足条件

所以p(i)$p^{(i)}$应尽可能大。
这就是支持向量机(SVM)能有效产生大间距分类的原因。

Kernel$Kernel$(核函数)：

如上图所述，如果想拟合一条非线性的判别边界来区分正负样本，有两种方法：

方法1：
构造多项式特征变量，如果θ0+θ1x1+θ2x2+θ3x1x2+θ4x21+θ5x22+⋯>0${\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2+{\theta }_3{x}_1{x}_2+{\theta }_4{x}_1^2+{\theta }_5{x}_2^2+\cdots >0$，则预测y=1$y=1$。

方法2：
只定义三个特征变量x0,x1,x2$x_0,x_1,x_2$，其中x0=1$x_0=1$，可忽略，如下图所示，用x1,x2$x_1,x_2$作为坐标轴，手动选取三个点作为l(1),l(2),l(3)$l^{(1)},l^{(2)},l^{(3)}$：

给出样本x$x$，新的特征变量定义如下：

similarity$similarity$函数即为Kernel$Kernel$函数，此处为高斯核函数，可用k(x,l(i))$k(x,l^{(i)})$表示。
以f1$f_1$为例：
f1=similarity(x,l(1))=exp(−∥x−l(1)∥22σ2)=exp(−∑j=1n(xj−l(1)j)22σ2)$f_1=similarity(x,l^{(1)})=exp(-\frac{\Vert x-l^{(1)}{\Vert }^2}{2{\sigma }^2})=exp(-\frac{\sum _{j=1}^n(x_j-l_j^{(1)}{)}^2}{2{\sigma }^2})$，忽略x0$x_0$
如果x≈l(1)$x\approx l^{(1)}$(即x$x$离l(1)$l^{(1)}$很近)：f1≈exp(−022σ2)≈1$f_1\approx exp(-\frac{0^2}{2{\sigma }^2})\approx 1$
如果x$x$离l(1)$l^{(1)}$很远：f1≈exp(−(large Number)22σ2)≈0$f_1\approx exp(-\frac{(largeNumber{)}^2}{2{\sigma }^2})\approx 0$
之前画的每一个点对应一个新的特征变量。

本例中，假设函数为：当θ0+θ1f1+θ2f2+θ3f3⩾0${\theta }_0+{\theta }_1{f}_1+{\theta }_2{f}_2+{\theta }_3{f}_3⩾0$时，预测y=1$y=1$
假设已得到θ0=−0.5,θ1=1,θ2=1,θ3=0${\theta }_0=-0.5,{\theta }_1=1,{\theta }_2=1,{\theta }_3=0$，可以发现，样本离l(1)$l^{(1)}$或l(2)$l^{(2)}$很近时，即f1=0$f_1=0$或f2=0$f_2=0$时，y=1$y=1$

如何选择l(1),l(2),l(3)⋯$l^{(1)},l^{(2)},l^{(3)}\cdots$？
设给定m$m$个训练样本(x(1),y(1)),(x(2),y(2)),⋯,(x(m),y(m))$(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\cdots ,(x^{(m)},y^{(m)})$
选择l(1)=x(1),l(2)=x(2),⋯,l(m)=x(m)$l^{(1)}=x^{(1)},l^{(2)}=x^{(2)},\cdots ,l^{(m)}=x^{(m)}$
f1=similarity(x,l(1))f2=similarity(x,l(2))⋯$$\begin{gathered} f_1=similarity(x,l^{(1)}) \\ {f}_2=similarity(x,l^{(2)}) \\ \cdots \end{gathered}$$
则特征向量f=⎡⎣⎢⎢⎢f1f2⋯fm⎤⎦⎥⎥⎥$f=\left[\begin{array}{c}{f}_1\\ f_2\\ \cdots \\ f_m\end{array}\right]$，可添加f0=1$f_0=1$
对于支持向量机：给定样本集x$x$，计算特征向量f∈Rm+1$f\in R^{m+1}$
如果θTf⩾0${\theta }^{T}f⩾0$，预测y=1$y=1$

如何得到θ$\theta$？
minθC[∑i=1my(i)cost1(θTf(i))+(1−y(i))cost0(θTf(i))]+12∑j=1nθ2j$\underset{\theta }{min}C[\sum _{i=1}^m{y}^{(i)}cos{t}_1({\theta }^T{f}^{(i)})+(1-y^{(i)})cos{t}_0({\theta }^T{f}^{(i)})]+\frac{1}{2}\sum _{j=1}^n{\theta }_j^2$
此处n=m$n=m$
∑j=1nθ2j$\sum _{j=1}^n{\theta }_j^2$也可写作θTθ${\theta }^T\theta$(忽略θ0${\theta }_0$)，为了提升计算效率，改写成θTmθ${\theta }^{T}m\theta$，m$m$为样本数。
不建议自己写最小化代价函数的代码，应使用成熟软件包。

高斯核函数中σ$\sigma$参数的影响：
例：l(1)=[35]$l^{(1)}=\left[\begin{array}{c}3\\ 5\end{array}\right]$，f1=exp(−∥x−l(1)∥22σ2)$f_1=exp(-\frac{\Vert x-l^{(1)}{\Vert }^2}{2{\sigma }^2})$
当σ2=1${\sigma }^2=1$时：

x=[35]$x=\left[\begin{array}{c}3\\ 5\end{array}\right]$时，为最高点f1=1$f_1=1$，x$x$取值离该点越远，f1$f_1$越趋近于0$0$。

当σ2=0.5${\sigma }^2=0.5$时：

随着x$x$取值远离l(1)$l^{(1)}$，f1$f_1$取值的下降趋势加快。

当σ2=3${\sigma }^2=3$时：

随着x$x$取值远离l(1)$l^{(1)}$，f1$f_1$取值的下降趋势减缓。

使用支持向量机时，参数C$C$的影响：

• C$C$取值较大，低偏差，高方差。(对应λ$\lambda$取值小)
• C$C$取值较小，高偏差，低方差。(对应λ$\lambda$取值大)

使用支持向量机时，参数σ2${\sigma }^2$的影响：

• σ2${\sigma }^2$取值较大，特征向量fi$f_i$越平滑，高偏差，低方差
• σ2${\sigma }^2$取值较小，特征向量fi$f_i$越陡峭，低偏差，高方差

使用SVM软件包求解参数θ$\theta$(如：liblinear,libsvm$liblinear,libsvm$)：
步骤一：选择参数C$C$
步骤二：选择核函数：

1. 选择No kernel$Nokernel$(也叫线性核函数)
   如果θTx⩾0${\theta }^{T}x⩾0$，预测y=1$y=1$
   当存在n$n$个特征值，m$m$个样本，n$n$很大，m$m$很小，此时，适合使用线性核函数。
2. 高斯核函数，fi=exp(−∥x−l(i)∥22σ2),l(i)=x(i)$f_i=exp(-\frac{\Vert x-l^{(i)}{\Vert }^2}{2{\sigma }^2}),l^{(i)}=x^{(i)}$
   需选择参数σ2${\sigma }^2$
   当存在n$n$个特征值，m$m$个样本，n$n$很小，m$m$很大时，适合用高斯核函数。
   如果选择高斯核函数，需要实现一个核函数：
   functionf=kernel(x1,x2)$functionf=kernel(x_1,x_2)$
   f=exp(−∥x1−x2∥22σ2)$f=exp(-\frac{\Vert x_1-x_2{\Vert }^2}{2{\sigma }^2})$
   return$return$
   其中，f$f$代表f(i)$f^{(i)}$，x1$x_1$代表x(i)$x^{(i)}$，x2$x_2$代表l(j)=x(j)$l^{(j)}=x^{(j)}$
   在使用高斯函数前，需要做特征归一化，避免单一特征值对f$f$的影响过大。
   注意：不是所有的相似度函数similarity(x,l)$similarity(x,l)$都是有效的核函数，需要满足默塞尔定理，确保软件包可以使用大量优化方法并快速得到参数θ$\theta$。
   可能会遇到的其他核函数：
   1)多项式核函数：k(x,l)=(xTl+constant)degree$k(x,l)=(x^{T}l+constant{)}^{degree}$，当x,l$x,l$都是严格非负数时使用；
   2)字符串核函数：当输入为文本或其他类型字符串时使用；
   3)卡方核函数；
   4)直方图交叉核函数。

如果有k$k$个类别的话，一般使用内置函数，否则，训练k$k$个SVM，每个SVM将1$1$类与其他类区分开。

逻辑回归与SVM对比：
n$n$为特征值数量，m$m$为训练样本数

• 如果相对于m$m$，n$n$很大(如n=10000,m=10∼1000$n=10000,m=10\sim 1000$)
  使用逻辑回归，或SVM使用线性核函数；
• 如果n$n$很小，m$m$中等大小(如n=1∼1000,m=10∼10000$n=1\sim 1000,m=10\sim 10000$)
  选择SVM使用高斯核函数；
• 如果n$n$很小，m$m$很大(如n=1∼1000,m=50000+$n=1\sim 1000,m=50000+$)
  增加更多特征值，使用逻辑回归或SVM不带核函数。

对于所有情况，一个设计的很好的神经网络可能会非常有效，但训练起来很慢。

SVM优化函数是凸函数，总能找到全局最小值，或接近它的值。