支持向量机（SVM）

• SVM是一种监督学习二元分类器，通过核函数将线性不可分变成线性可分，同时在实践中也是小样本学习效果最好的算法。

支持向量

• 关于线性分类的概念请参考逻辑回归，对于不同的分类器可能会得到不同的拟合结果，例如

  

  上图中是三个分类器得到的决策边界，对于蓝色和黄色分类器，不能将正负类别分开，拟合能力较弱，同时对于黑色分类器来说，其不仅可以达到分类效果，还满足距离两个类别的最近样本最远。而这两个类别中离决策边界最近的样本我们称其为支持向量，其与决策边界之间的距离称为margin。

  当从二维扩展到多维空间时，决策边界将变成一个超平面，我们同样是寻找满足下面条件的拟合结果：

  1. 两类样本分别在超平面的两侧；
  2. 最大化支持向量与超平面之间的距离。

• 对于一个超平面我们可以用如下线性方程来描述

  $$\boldsymbol{w}^T\boldsymbol{x} + b = 0$$

  同时在$n$维空间中，点$\boldsymbol{x} = (x_1, x_2, \dots, x_n)$到这个平面的距离为

  $$d = \frac{|\boldsymbol{w}^T\boldsymbol{x} + b|}{\Vert \boldsymbol{w}\Vert}$$

  其中$\Vert \boldsymbol{w}\Vert = \sqrt{w_1^2+w_2^2+\cdots+w_n^2}$，我们可以设支持向量到超平面的距离为$d$，其他样本到超平面的距离大于$d$。为了方便我们将正向类别定义为$y=1$，负向类别定义为$y=-1$，此时我们得到超平面的一个约束

  $$\begin{cases} \frac{\boldsymbol{w}^T\boldsymbol{x} + b}{\Vert \boldsymbol{w}\Vert} \ge d &,y=1\\ \frac{\boldsymbol{w}^T\boldsymbol{x} + b}{\Vert \boldsymbol{w}\Vert}\le -d &, y=-1 \end{cases}$$

  同时我们两边乘以$\Vert \boldsymbol{w}\Vert$变成

  $$\begin{cases} \boldsymbol{w}^T\boldsymbol{x} + b \ge \Vert \boldsymbol{w}\Vert d &,y=1\\ \boldsymbol{w}^T\boldsymbol{x} + b\le -\Vert \boldsymbol{w}\Vert d &, y=-1 \end{cases}$$

  因为$\Vert \boldsymbol{w}\Vert d$是正数，我们可以移走或者说令其等于1简化算式（这对后续的优化没有影响），并且合并两个算式，得到

  $$y(\boldsymbol{w}^T\boldsymbol{x} + b)\ge 1$$

  由于该式恒大于0，故有$y(\boldsymbol{w}^T\boldsymbol{x} + b) = |\boldsymbol{w}^T\boldsymbol{x} + b|$，所以之前的距离公式可以改为

  $$d = \frac{y(\boldsymbol{w}^T\boldsymbol{x} + b)}{\Vert w\Vert}$$

  而我们的目标则是最大化这个距离，同时对于支持向量有$y(\boldsymbol{w}^T\boldsymbol{x} + b)=1$，所以最大化的目标为

  $$\gamma = \max(\frac{2}{\Vert \boldsymbol{w}\Vert})$$

  乘2的目的和MSE中乘2类似，不影响性质的情况下简化后续的运算。

  

• 同时这里还可以进一步转换将目标变为求

  $$\min(\frac{1}{2}\Vert \boldsymbol{w}\Vert)$$

  去除掉除法，同时为了去除模长的根号可以再添加一个平方变为

  $$\min(\frac{1}{2}\Vert \boldsymbol{w}\Vert^2)$$

  其中$y^{(i)}(\boldsymbol{w}x^{(i)} + b)\ge 1$

决策树

• 决策树是一个树形结构，每个非叶节点表示一个特征属性的测试（也就是条件），每个分支代表这个特征属性在某个值域上的输出（也就是满足某条件的下一步），每个叶节点存放一个类别。对于待预测数据，从根节点开始根据节点的条件选择不同的分支直到到达叶子节点，得到其预测类别。

  由上述对决策树的定义我们可以直到决策树也是一个用于分类的监督学习模型，当然我们依然可以使用决策树进行回归，此时称为回归决策树，叶子节点上输出数值而不是类别标签。

  决策树和kNN算法一样，理解起来非常直观易懂，例如下面是一个现实生活中决策树的例子

• 我们会发现所谓决策，就是对数据进一步提纯，将其分裂成两个不同的集合，不断进行这个过程直到得出最终结果。

  显然样本最终属于什么类别取决于节点中的各个分支，我们当然可以人为的构建决策树，但是如何让模型从数据特征空间中构建出决策树，才是机器学习要干的事。

kNN算法

• kNN（k-Nearst Neighbors）也叫k近邻算法是一种监督学习模型，其定义很简单，如果一个样本特征空间中的$k$个最邻近的样本中大多数属于某个类别，则该样本也属于这个类别，也就是“近朱者赤，近墨者黑”。

  这是ML中最基本的算法之一，但是模型并不需要从样本特征空间中学习到什么东西，而是直接计算样本的相似度来确定待预测样本应该与哪些训练样本标签保持一致。

逻辑回归

• 虽然叫做回归，但逻辑回归实际上是一个分类模型，至于为啥叫回归据我搜索的资料是历史遗留的命名问题。

二分类问题

• 首先我们需要了解一下什么是分类，在分类问题中，我们将尝试预测一个样本是否属于某一个类，对于最简单的分类问题也就是二元分类问题，它将包含两个类（正和负），我们将因变量可能属于的类分别称为正向类和负向类，例如$y^{'} = 0$代表负向，$y^{'} = 1$代表正向，故对于此我们要求模型的输出$h_\theta(x)$满足$0\le h_\theta(x) \le 1$。

  如果我们使用线性回归无法满足我们的要求，它的输出可能会很大，而对于逻辑回归将永远输出一个$0$到$1$之间的结果。当然我们可以定义$h_\theta(x)\ge 0.5$时，$y^{'}=1$，反之$h_\theta(x)<0.5$时，$y^{'}=1$，这使得输出值满足我们的要求，但是我们来查看如下数据。

  例如对于图例，我们按照上述规则使用拟合直线对后续点进行分类，其中黄色点是我们的分解点，显然这个拟合直线可以完成我们的要求，对于样本为正的的点，其预测值都大于$0.5$也代表为正，样本为负的点，其预测值都小于$0.5$代表负。但是如果我们观察到了一个新的样本，可能会使拟合直线变成如下情况

  此时我们发现再使用$0.5$作为阈值已经不再合适。此时我们将引入逻辑回归来解决此类问题。

线性回归

• 机器学习中的线性回归（Linear Regression）来自于统计学中的方法，入门篇中我们了解到回归就是使用现有数据预测后续值，而机器学习中的线性回归就是让计算机通过训练数据得出一个线性模型，例如对于数据集$D=\{(x_i,y_i)\}$，我们想要通过训练模型得到$x_i$和$y_i$之间的线性关系，从而能够预测未知的$x_j$对应的$y_j$值。

  显然对于这个问题，我们在数学上可以直接使用最小二乘法之类的方法得到一条拟合直线，而在ML中则有所不同，在这里我们假设最终得到的线性函数为$h$（代表hypothesis），它是一个从$x$到$y$的映射，则可以记为：

  $$h_\theta(x) = \theta_0 + \theta_1 x$$

  其中$x$是输入变量，$\theta_i$是由模型输出的系数。