Large Margin Classification

Optimization Objective

此小节主要讲了SVM的cost function是怎么来的。SVM(Support Vector Machine)是一种类似于Logistic Regression的分类算法。Andrew通过Logistic Regression的cost function来引申出了SVM的cost function，如下图：

1.1-cost function

1.2-SVM cost function

• 首先用cost₀(θ^Tx)和cost₁(θ^Tx)替换原先的cost function
• 其次，去掉1/m，因为这个乘数不影响最终θ的值
• 用C来代替λ，相当于各项都乘以1/λ
  另外，在优化这个cost function的时候，我们会使得中括号中的项为0(根据我们的cost function的图形可以看出，优化成功的结果就是使得cost(z)为0)，所以我们优化的目标就转化为如下公式
  
  1.3-optimize objective
  
  图中红框圈出的就是我们的优化目标，其中红色箭头指向的是限定条件

Large Margin Intuition

这节主要讲了直觉上large margin是怎么回事，主要是decision bounary两边会有margin，如下图：

2.1-large margin

Mathematics behind large margin classification

此小节主要讲了SVM背后的数学原理。
首先，讲了向量内积(vector inner product)的知识，假设我们有两个向量u和v, 那么它们的inner product就是u^Tv，从这里也可以看出向量内积是一个实数，我们可以通过如下方式计算向量内积：

3.1-vector inner product

u^Tv = P · ||u|| = u1v1 + u2v2
其中P是向量v在向量u上投影的长度， ||u||是向量u的长度，这里需要注意P是一个有符号数，当其夹角>90° 且<270°时，P为负。

然后，结合图1.3我们的优化目标，可以看出要想满足我们的优化条件就会使得decision boundary有较大的margin，如下图推导过程：

3.2-SVM Decision Boundary

上图中有些错误：首先第二个限定条件应该是y(i)=0; 另外，右下角图应该是满足条件P(i)||θ|| >= 1

从图中可以看出为了满足我们的优化目标，即θ的长度越小越好，还要符合限定条件，那么结论就是p越大越好，即当y=1时，p长度越大，||θ||就可以使用相对较小的值来满足p⁽ⁱ⁾·||θ|| >= 1, 这样就会使得1/2 ||θ||²越小；同样道理y=0也是希望p的长度越大越好。

这里有个问题，就是为啥θ向量一定是垂直于decision boundary的？另外，如果不是线性可分的，那么如何使得其限定条件能满足呢？比如在y(i)=1的情况下，如果p(i)<0，这种情况就无法满足p(i)·||θ|| >=1

第二个问题在接下来的Kernels章节得到了回答，即如果是非线性可分的情况下，我们需要引入polynomial function来使得decision bounary变为曲线的，而在接下来的章节，我们会发现，最终使用的是新引入的feature，而非直接将原有的feature相乘。具体参考后面的章节。

Kernels

Kernels I

首先，Andrew引入了一个非线性问题的示例，使用之前Linear Regression的知识，我们可以想象出需要引入polynomial function来解决此类问题。实际上我们可以理解为引入了新的Feature（比如将x1*x2作为一个新的feature f1），但是，实际上我们是否有更好的引入新的feature的方法呢？原因之一就是使用polynomial方法的计算量会非常大，而且这个变量本身的含义也不是很清楚，因此这就是我们接下来要引入kernel的原因。下图展示了如何引入新的feature：

4.1-kernel

• 图中我们选取了三个点，分别记做l⁽¹⁾,l⁽²⁾,l⁽³⁾,这三个点我们称之为landmarks

• 新的feature记做f₁,f₂,f₃, 实际上是与x的相似度，所以我们使用similarity(x, l)来表示，空间中两个点的相似度我们改如何表示和计算呢？这里我们使用了所谓的高斯核(Gaussian Kernels)，这个函数中其中一部分就是使用欧几里得距离来表示两点之间的距离（某种程度上就是近似度），如下图所示：
  

  4.2-欧几里得距离

• exp表示e的多少次方，其中A为(0,1)点，其图形如下：

  
  
  4.3-以e为底的指数函数

由上图我们可得出如下的结论：

4.4-kernels and similarity

即如果两点距离很大，那么这个新的feature f就会接近于0，如果距离很小，f就会接近于1，而 𝞼 可以调节这种相似度的影响大小，如果𝞼越大，即分母越大，那么分子（即距离）的变化影响就减小了，相反，如果𝞼很小，那么分子的微小变化也会很明显甚至会被放大，也就是对距离变化越敏感，可以通过下图从直觉上理解：

4.5-𝞼影响

1. landmark是如何选出来的，是随机的么？
2. 除了Gaussian Kernel还有其它什么核函数？
   下面的章节就是解决这些问题的。

Kernels II

首先要解决的就是如何选择landmark的问题，如前所述，本质上就是根据相似的点来进行预测，那么我们完全可以将所有的样本点作为landmark，想象在空间中布满了样本点，然后我们看要预测的点离哪个样本点近，我们就预测跟那个样本的y值相同。如下图所示：

5.1-choose landmarks

如上图所示，假设我们有m个样本，那么就意味着我们会有m个landmark，这也意味着我们会新增m个feature（实际上如果算上f0=1的话应该是m+1个new features)，如下图所示：

5.2-get new features

需要注意的是由于欧几里得距离是一个标量，因此最终组成新的f是一个m+1维的vector。另外，我们将不再直接使用x进行预测，而是使用新生成的f进行计算并预测。

然后，我们再回过头来看下之前的训练目标，即min(cost function)， 如下图所示：

5.3-new cost function

需要注意的是:

• 原先的x被替换成了f， 即θ^Tx⁽ⁱ⁾被替换成了θ^Tf⁽ⁱ⁾
• 原先的正则式sum(θ²_j)被替换成了θ^Tθ，然后可以进一步变换为θ^TMθ(主要是为计算方便)

SVM In Practice

这一节主要讲了如何在实践中使用SVM。通常，我们都会使用现成的软件包来帮助我们实现，但在这个过程中我们仍然需要做两件事：

1. 选择C parameter

2. 选择Kernel函数
   具体如下：

   
   
   6.1-use SVM SW package

• 一般的，对于feature数量较大(n比较大），样本数量较小时(m较小)我们采用Linear Kernels实际上等于不用任何Kernels，即不会做任何映射，你也可以认为是x->x的映射
• 或者当n较小，m较大时，我们就可以采用Gaussian kernel，本质上是增加了feature形成了更高维的函数空间。在使用Gaussian kernel的时候，我们需要选择𝞼

当使用Gaussian Kernel的时候，我们一般也需要实现x->f的kernel映射函数，如下图所示：

6.2-kernel function

• 一般的，当我们实现了这个Kernel函数后，软件包会自动帮我们将x映射到多个f
• 我们需要做feature scaling，以便让所有的feature的影响在一个量级内。

另外，除了上述的linear kernel 和Gaussian kernel之外还有一些kernel可能会被用到，但是一般的，它们都需要符合Mercer' Theorem

6.3-other kernels

对于多分类问题，一般情况下，软件包都已经内置了多分类方法，可以直接调用。另一方面，如果没有提供，我们可以使用之前在Logistic regression中使用的one-vs-other方法

6.4-multi-class classification

最终，我们可以看到在解决分类的问题时，我们会有多种选择，那么如何选择这些不同的算法呢？

6.5-choose algorithm

• 通常会根据feature的数量以及样本的数量来做出选择
• 神经网络适用于几乎所有的情况，唯一的问题是训练的时候会比较慢