Part1-支持向量机

优化目标

逻辑回归的另类观点

逻辑回归：

\(h_\theta(x)=\frac{1}{1+e^{-\theta^Tx}}\)，

如果y=1，我们想要\(h_\theta(x)\approx 1,\theta^Tx \gg0\)

如果y=0，我们想要\(h_\theta(x)=0,\theta^Tx \ll 0\)

对于单个样本的代价：\(-(y\log h_\theta(x) + (1-y)\log(1-h_\theta(x)))\\=-y\log\frac{1}{1+e^{-\theta^Tx}}-(1-y)\log(1-\frac{1}{1+e^{-\theta^Tx}})\)

对于y=1，会得到这样一条曲线：

可以看到，当\(z\)值很大时，也就是当\(\theta^Tx\)很大时，函数对应的值会变得非常小，也就是说它对代价函数的的影响很小，这也就解释了为什么逻辑回归在看见\(y=1\)这样的样本时，会将\(\theta^Tx\)设成一个很大的值，因为它在代价函数中对应的这一项值会非常小。

为了构建支持向量机，下面我们要做是就是从这个代价函数(\(-\log \frac{1}{1+e^{-z}}\) )开始，然后进行少量修改，结果如图：

不难想到，它和逻辑回归的效果很相似，事实上，这会使支持向量机拥有计算上的优势，并使得之后优化问题变得简单，更容易解决，

还有一种情况，当y=0时，与y=1类似，如图：

支持向量积(SVM)

逻辑回归：

\(\min_\theta \frac{1}{m}[\sum_{i=1}^my^{(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\)

支持向量积：

\(\min_\theta \frac{1}{m}\sum_{i=1}^my^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})+\frac{\lambda}{2m}\sum_{i=0}^n \theta_j^2\)

其中\(cost_1\)和\(cost_0\)表示上述改动后的图对应的代价函数

其可以看作于\(\min_\theta A+\lambda B \rightarrow \min_\theta CA+B(可以想象成C=\frac{1}{\lambda})\)，但两个表达式并不是相等的，而是当\(C=\frac{1}{\lambda}\)时，两个函数的优化目标是一样的，于是：

\(\min_ \theta C\sum_{i=1}^m[y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})]+\frac{1}{2}\sum_{i=1}^n\theta_j^2\)

这也就是SVM学习得到的参数

而与逻辑回归不同的是，支持向量积并不会输出概率，相对的，我们得到的是通过优化这个代价函数得到的一个参数\(\theta\)，而支持向量积所做是进行一个直接的预测，预测y是0或1

\(h_\theta(x)=\left\{ \begin{align} &1,\theta^Tx \ge 0 \\ &0,其它 \end{align} \right.\)

这就是SVM的假设函数形式

直观上对大间隔的理解

有时人们会将支持向量积称为大间距分类器，接下来，要学习的就是直观的对这个大间距进行理解。

支持向量积(Support Vector Machine,SVM)

\(\min_ \theta C\sum_{i=1}^m[y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})]+\frac{1}{2}\sum_{i=1}^n\theta_j^2\)

对应的左图为:\(cost_1(z)\)，右图为\(cost_0(z)\)

如果\(y=1\)，则我们想要\(\theta^Tx \ge 1(而不仅仅是\ge0)\)

如果\(y=0\)，则我们想要\(\theta^Tx \le -1(而不仅仅是<0)\)

SVM决策边界

\(\min_ \theta C\sum_{i=1}^m[y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})]+\frac{1}{2}\sum_{i=1}^n\theta_j^2\)

如果\(C\)非常非常大，则当最小化优化目标时，我们就希望能找到一个值，使得第一项(\(\sum_{i=1}^m[y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})]\))等于0，

而当\(y^{(i)}=1\)时，\(\theta^Tx^{(i)} \ge 1\)；

当\(y^{(i)}=0\)时，\(\theta^Tx^{(i)} \le -1\)

线性可分情况：

如图，有这样一个数据集，其中有正样本，也有负样本，这些数据线性可分

例如，可以用绿色这条决策边界将正样本和负样本分开，但它看上去不是非常自然；但是SVM则会选择图中黑色线对应的决策边界，这条边界比绿色的就要好得多，这条黑色的决策边界鲁棒性更好，能更好地分开样本和负样本。从数学上来说，这条黑色边界拥有更大的距离，如图中两条蓝色线，可以发现黑色的决策边界和训练样本的最小距离比绿色线对应的要更大一些。

因此，这个距离叫做支持向量机的间距(margin)，这使得SVM具有鲁棒性，因为它在分离数据时会尽量用大的间距去分离。

因此，支持向量机有时被称为大间距分类器(Large margin classifier)

存在异常值的大间距分类器

现在这个大间距分类器是在常数C被设的非常大的情况下得出的，而SVM实际上要比这个大间距的视图更加复杂。尤其是如果只使用大间距分类器时，这时的学习算法对异常点会非常敏感。

如图，在这样一个异常点的影响下，就会将决策边界从这条黑色线变成紫色线，这可能并不是一个好的结果，但如果不把C设置得那么大，那么最后得到的可能就还是这条黑色的线。

可以想象类比为：\(C\)相当于\(\frac{1}{\lambda}\)，当C非常大时，就是\(\lambda\)非常小，就会在分类时，容易导致过拟合，而当\(C\)没那么大时，\(\lambda\)就会相对合适，就可以一定程度上避免过拟合

大间隔分类器背后的数学原理

向量内积

开始前，先复习一下向量内积

例：

\(u=\left[ \begin{matrix} u_1 \\ u_2 \end{matrix} \right]\),\(v=\left[ \begin{matrix} v_1 \\ v_2 \end{matrix} \right]\)

则\(u\)和\(v\)的内积为：\(u^Tv\)

\(u\)和\(v\)对应的图如图：

则可以得出向量\(u\)的范数(向量的欧几里得长度)：\(|| u || =\sqrt{u_1^2+u_2^2}\)

那么，如何计算\(u\)和\(v\)的内积？

将向量\(v\)投影到向量\(u\)上，如图，然后测量图中对应的红色线长度(p)，则\(p\)就是向量\(v\)在向量\(u\)上的投影长度或者说量，并且此处的\(p\)是有符号的，如果\(v\)和\(u\)夹角大于\(90^\circ\)，则\(p\)就是小于0的

即：\(u^Tv=p\cdot||u||=u_1v_1+u_2v_2(p \in \mathbb R)\)

SVM决策边界

SVM中的优化目标函数：\(\min_\theta \frac{1}{2}\sum_{j=1}^n\theta_j^2\)

\(\theta^Tx^{(i)} \ge 1,如果y^{(i)}=1\)

\(\theta^Tx^{(i)} \le -1,如果y^{(i)}=0\)

为理解方便进行以下简化：先忽略截距(\(\theta_0=0\))，为画图方便设置特征数为2(n=2)

则优化目标函数可以写作：\(\min_\theta\frac{1}{2}\sum_{j=1}^n\theta_j^2 =\frac{1}{2}(\theta_1^2+\theta_2^2)=\frac{1}{2}(\sqrt{\theta_1^2+\theta_2^2})^2=\frac{1}{2}||\theta||^2\)

且\(\theta=\left[\begin{matrix} \theta_1 \\ \theta_2 \end{matrix} \right]或\theta=\left[\begin{matrix}\theta_0 \\ \theta_1 \\ \theta_2 \end{matrix} \right](\theta_0=0)\)

然后再考虑\(\theta^Tx^{(i)}\)和前面向量内积中的\(u^Tv\)类比，则\(\theta\)类比\(u\)，\(x^{(i)}\)类比\(v\)，则将\(x^{(i)}\)对应的向量投影到\(\theta\)对应的向量上，就会得到一个投影\(p^{(i)}\)，则\(\theta^Tx^{(i)}=p^{(i)}||\theta||=\theta_1x_1^{(i)}+\theta_2x_2^{(i)}\)

这就意味着，这两种条件即：\(\theta^Tx^{(i)} \ge 1或\le -1\)可以换种方法表述，即：\(p^{(i)}\cdot ||\theta|| \ge 1或\le -1\)

所以，将其写入优化目标函数后，得出结果如下：

\(\min_\theta \frac{1}{2}\sum_{j=1}^n \theta_j^2\)

\(s.t. \begin{align} &p^{(i)}\cdot||\theta|| \ge 1,如果y^{(i)}=1 \\ & p^{(i)}\cdot||\theta|| \le -1,如果y^{(i)}=0 \end{align}\)

现在看如图的训练样本，为方便，继续简化\(\theta_0=0\)。

则SVM的选择，一种选择是如图中绿色对应的线，这个决策边界并不是一个好的选择，因为它的间距很小，为什么SVM不会选择它？对应这种参数选择，可以看出，\(\theta\)实际上是与决策边界\(90^\circ\)正交的(因为边界处\(\theta^Tx=0\))，如图，\(x^{(1)}\)和\(x^{(2)}\)对应投影为\(p^{(1)}\)和\(p^{(2)}\),这两个投影线段都会非常短，我们会发现，这些\(p^{(i)}\)都是非常小的数，而我们观察优化目标函数，就会发现以\(y^{(i)}=1\)为例，\(p^{(i)}\cdot||\theta|| \ge 1\)，如果这里的\(p^{(i)}\)特别小，那就意味着需要\(||\theta||\)非常大，同样的，对于负样本，也是一样，然而，优化目标函数要做的是找一个\(\theta\)来使得\(\frac{1}{2}||\theta||^2\)足够小，因此这对于\(\theta\)而言并不是一个好的方向。

而如果SVM选择了如图中蓝色的边界，则会有很大的不同，此时得出的投影\(p^{(1)}\)和\(p^{(2)}\)就比之前大许多，此时的对于\(p^{(i)}\cdot ||\theta|| \ge 1\)，由于\(p^{(i)}\)比较大，则\(||\theta||\)可以小一点，这样，就与优化目标函数保持一致了。

这样就意味着，SVM通过选择第二种决策边界，可以使得参数\(||\theta||\)变小得多，来达到优化目标函数的目的，这也就是为什么SVM会选择第二种决策边界的假设，这也就是SVM是如何产生大间距分类现象的原理。

而\(\theta_0 \ne 0\)时，也是类似的，结果仍然会产生大间距分类。

核函数

非线性决策边界

如图，如果有一个像这样的训练集，希望拟合一个非线性的决策边界，来区别正负实例，一种办法是构造一个复杂的多项式特征的集合，如\(\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x_1x_2+\theta_4x_1^2+\theta_5x_2^2+\cdots \ge 0\)

为了说明另一种方法，先引入新的符号，可以把假设函数看成用\(\theta_0+\theta_1f_1+\theta_2f_2+\cdots\)计算的决策边界，\(f_1,f_2,\cdots\)就是新的特征变量，即\(f_1=x_1,f_2=x_2,f_3=x_1x_2,\cdots\)

是否有一个不同的或更好的特征选择方法呢？

首先，手动选取一些点，然后将这些点称为\(l^{(1)},l^{(2)},l^{(3)}\),并将它们叫做标记(landmark)，然后这样定义新的特征：

给定一个实例\(x\)：定义\(f_1=similarity(x,l^{(1)})=exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2})\)，similarity为一种相似度的度量，即度量训练样本\(x\)与第一个标记的相似度。

同理\(f_2=similarity(x,l^{(2)})=exp(-\frac{||x-l^{(2)}||^2}{2\sigma^2})\)

这个相似度函数用数学术语说就是一个核函数，上述所用的核函数(\(exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2})\))实际上是高斯核函数(Gaussian kernel)，实际上通常我们用\(K(x,l^{(i)})\)代替\(similarity(x,l^{(i)})\)

核和相似度

先来看第一个标记，即标记\(l^{(1)}\)

\(f_1=similarity(x,l^{(1)})=exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2})=exp(-\frac{\sum_{j=1}^n (x_j-l_j^{(1)})^2}{2\sigma^2})\)

假设x与其中一个标记点非常接近，\(x \approx l^{(1)}\)：

则这个欧氏距离以及这个分子就会接近于0，因此\(f_1\)就是个简单的特征，将会接近\(exp(-\frac{0^2}{2\sigma^2}) \approx 1\)

相反地，如果\(x\)离\(l^{(1)}\)很远，则\(f_1=exp(-\frac{(large\ number)^2}{2\sigma^2})\approx 0\)

例：

\(l^{(1)}=\left[ \begin{matrix} 3 \\ 5 \end{matrix} \right],f_1=exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2})\)

\(\sigma^2=1\)

如果对特征画图，则如图：

这个曲面高度是\(f_1\)的值，那么横轴则分别对应\(x_1,x_2\)

当\(\sigma^2=0.5\)时，对应的如图：

当\(\sigma^2=3\)时，对应的如图：

上述是对特征的定义，接下来看看我们能得到什么样的预测函数。

给定一个训练样本x，我们准备计算出三个特征变量，即\(f_1,f_2,f_3\)，如果\(\theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3 \ge 0\)，则预测值将等于1。

如：我们假定我们已经找到了一个学习算法，并且假设已经得到了这些参数的值\(\theta_0=-0.5,\theta_1=1,\theta_2=1,\theta_3=0\)

如果有一个训练实例\(x\)接近于\(l^{(1)}\)，如图中紫色的点，则我们会有\(f_1\)接近于1(\(f_1 \approx 1\))，又因为\(x\)离\(l^{(2)},l^{(3)}\)都很远，所以\(f_2 \approx 0,f_3 \approx 0\)，则\(\theta_0+\theta_1*1+\theta_2*0+\theta_3*0=-0.5+1=0.5 \ge0\)，因此这个点预测的值是1

现在假设选择另一个点，如图中蓝色对应的，则\(f_1,f_2,f_3 \approx 0\)，于是\(\theta_0+\theta_1f_1+\cdots \approx-0.5<0\)，因此预测的y值是0

我们最后会得到这个预测函数的判别边界，如图所示，在这个红色边界里面，预测的y值等于1，在外面预测的y值等于0，这就是我们如何定义标记点和核函数来训练出非常复杂的非线性决策边界方法。

选择标记(landmarks)

我们在上述中说到了选择标记点的过程，例如\(l^{(1)},l^{(2)},l^{(3)}\)，使我们能定义相似度函数也称为核函数如：\(f_i=similarity(x,l^{(i)})=exp(-\frac{||x-l^{(i)}||^2}{2\sigma^2})\)，这使我们能构造一个预测函数\(y=1，如果\theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3 \ge 0\)，但是，我们从哪里得到这些标记点？而且我们有时需要更多的标记点，而不仅仅是我们选的这三个。

因此，在实际应用时，在给定学习问题中，怎么选取标记点？我们的数据集中有一些正样本和一些负样本，我们的想法是将选取样本点，我们拥有的每个样本点，只需要直接使用它们，直接将训练样本作为标记点如图：

这样得到m个标记\(l^{(1)},l^{(2)},\cdots,l^{(m)}\)，即每个标记点都和一个样本点的位置相对应，这样还不错，因为这说明特征函数基本上是在描述每一个样本距离，样本集中其它样本的距离，具体的这个过程大致如下：

给定\((x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\cdots,(x^{(m)},y^{(m)})\)

选择\(l^{(1)}=x^{(1)},l^{(2)}=x^{(2)},\cdots,l^{(m)}=x^{(m)}\)

这样，当给定样本\(x\)时:

\(f_1=similarity(x,l^{(1)})\)

\(f_2=similarity(x,l^{(2)})\)

\(\cdots\)

组成\(f=\left[ \begin{matrix}f_0\\ f_1\\f_2\\\cdots\\f_m \end{matrix} \right]\)\(f_0=1\)

对于训练样本\((x^{(i)},y^{(i)})\)

\(x^{(i)} \rightarrow \begin{matrix} f_1^{(i)}=sim(x^{(i)},l^{(1)}) \\ f_2^{(i)}=sim(x^{(i)},l^{(2)}) \\ \cdots \\ f_m^{(i)}=sim(x^{(i)},l^{(m)}) \end{matrix}\)，其中\(f_i^{(i)}=sim(x^{(i)},l^{(i)})=exp(-\frac{0}{2\sigma^2})=1\)

将这些合并成一个向量：

\(f^{(i)}=\left[ \begin{matrix}f_0^{(i)}\\ f_1^{(i)}\\f_2^{(i)}\\\cdots\\f_m^{(i)} \end{matrix} \right]\)，然后作为输入

带核支持向量积

假设：给定\(x\)，计算特征\(f \in \mathbb R^{(m+1)}\)

预测：如果\(\theta^Tf \ge 0\)，则\(y=1\)

训练：\(\min_\theta C \sum_{i=1}^m y^{(i)} cost_1(\theta^Tf^{(i)})+(1-y^{(i)})cost_0(\theta^Tf^{(i)})+\frac{1}{2}\sum_{j=1}^n \theta_j^2\)

在实际应用中，最后这一项(\(\frac{1}{2}\sum_{j=1}^n\theta_j^2\))会有所不同

\(\sum_j\theta_j^2\)这一项可以被重写为：\(\theta^T\theta\)，如果忽略\(\theta_0\)的话，\(\theta=\left[\begin{matrix} \theta_1 \\ \cdots \\ \theta_m \end{matrix} \right]\)

大多数SVM在实现时，其实是用\(\theta^TM\theta\)(\(M\)是依赖于核函数的某个矩阵)替换掉\(\theta^T\theta\)的

SVM参数选择

\(C(=\frac{1}{\lambda})\)

对于C比较大时：偏差小，方差大(类似小的\(\lambda\)的结果)

对于C比较小时：偏差大，方差小(类似大的\(\lambda\)的结果)

\(\sigma^2\)

对于\(\sigma^2\)偏大时：高斯核函数倾向于变得相对平滑，则特征\(f_i\)会变化的比较平缓，这也就会导致较高的偏差和较低的方差

对于\(\sigma^2\)偏小时：高斯核函数倾向于变得相对不平滑，则特征\(f_i\)会变化的比较剧烈，这也就会导致较低的偏差和较高的方差

使用SVM

尽管我们在使用SVM的过程中，不会去自己实现，而是使用现有的包，但也需要做几件事儿：

参数C的选择
核的选择(如果是没有核函数，则对应的是线性内核函数)
- 当特征数量大而训练集样本很小的时候，则使用线性内核函数是一个合理的设置
- 对于内核函数的第二个选择，可以使用高斯函数，需要选择\(\sigma^2\)参数，如果特征数量小而训练集样本数很大时，则使用高斯函数是一个不错的选择
- 其它核函数(如多项式核函数、字符串核函数、卡方核函数、直方相交核函数)

如何选择使用逻辑回归还是SVM呢？

如果有大量的特征，远大于m，就可能如文本分类问题，特征矩阵维度非常大，且训练集个数很少，则通常使用逻辑回归，或者使用不带核的SVM或线性核函数

而如果n较小，m大小适中，如：n可能是1-1000之间的数，m可能是从10到10000中的任何一个数值，则通常使用使用高斯核函数的SVM

如果n较小，而m较大，如：n可能是1-1000之间的数，而m可能是50000甚至上百万，这样，通常选择手动创建更多的特征变量，然后使用逻辑回归或不带核的SVM

神经网络可能可以对于大多数设置都有较好的效果，但或许训练会很慢