机器学习

写在前面：

本文采用的教程为【合集】十分钟 机器学习 系列视频 《统计学习方法》（上）_哔哩哔哩_bilibili

参考书籍为《统计学习方法 第二版》李航著

感谢上述作者做出的贡献

机器学习方法的基本分类

监督学习

监督学习（Supervised Learning）是指从标注数据中学习预测模型的机器学习问题，其本质是学习输入到输出的映射的统计规律。下面来简单介绍一下监督学习的基本概念

输入空间（Input Space）：输入的所有可能取值的集合

实例（Instance）：每一个具体的输入，通常由特征向量（Feature Vector）表示

特征空间（Feature Space）：所有特征向量存在的空间

输出空间：输出的所有可能取值的集合

• 监督学习的基本假设：X 和 Y 具有联合概率分布P（ X , Y ）
• 监督学习的目的：学习一个输入到输出的映射，这一模型以模型表示
• 模型的形式：条件概率分布P（Y | X）或决策函数Y = $f(x)$

监督学习的流程如下图所示：

无监督学习

无监督学习（Unsupervised Learning）是指从无标注数据中学习预测模型的机器学习问题，其本质是学习数据中的统计规律或潜在结构。

比较：

无监督学习的流程如下图所示：

机器学习的三要素

模型

假设空间（Hpothesis Space）：所有可能的条件概率分布或决策函数，用 $\mathcal{F}$ 表示。

策略

常见的损失函数

策略的作用：

算法

监督学习算法

无监督学习算法

模型的评估与选择

测试误差与训练误差

还记得上文提到的监督学习的流程图吗

模型的拟合是否好坏？

可以通过训练集计算训练误差来进行衡量

模型的预测效果是否好坏？

可以通过测试集来衡量

训练误差

所有的样本点都来自训练集，训练误差是计算了样本的平均值

测试误差

所有样本点来自测试集，每个样本点计算它的损失所得到的平均值叫作测试误差。

过拟合与模型选择

过拟合

过拟合（Over-Fitting）：学习所得模型包含参数过多，出现对已知数据预测很好，但对未知数据预测很差的现象。

正则化与交叉验证

正则化

正则化项

交叉验证

通过训练集得到的模型放入验证集中，得到预测误差最小的那个，即为最优模型

如果数据不充足该怎么办呢？

简单交叉验证

随机将数据分为两个部分，即训练集和数据集

S折交叉验证

随机将数据分为$\mathcal{S}$个互不相交、大小相同的子集，其中以$\mathcal{S}\mathcal{-}\mathcal{1}$个子集作为训练集，余下的子集作为测试集。

泛化能力

泛化误差

泛化误差上界(Generalization Error Bound)：指泛化误差的概率上界。两种学习方法的优劣，通常通过他们的泛化误差上界进行比较。

性质：

• 样本容量的函数：当样本容量增加时，泛化上界趋于0
• 假设空间容量的函数：假设空间容量越大，模型就越难学，泛化误差上界就越大

对于一个二分类问题：

生成模型和判别模型

生成模型

由数据学习联合分布概率$\mathcal{P}\mathcal{(}\mathcal{X}\mathcal{,}\mathcal{Y}\mathcal{)}$,然后求出P(Y | X )作为预测模型，即生成模型（Generative Model）：

$$P(Y\mid X)=\frac{P(X,Y)}{P(X)}$$

典型的生成模型：朴素贝叶斯法、隐马尔可夫模型

注：输入和输出变量要求为随机变量$P(Y\mid X)$

判别模型

由数据直接学习决策函数f（X）或者条件分布概率模型$P(Y\mid X)$作为预测模型，即判别模型（Discriminative Model）

典型的判别模型：K近邻法、感知机、决策树等

注：不需要输入和输出变量均为随机变量

感知机

感知机是二类分类的线性模型,属于判别模型.感知机学习旨在求出将训练数据进行线性划分的分离超平面.是神经网络和支持向量机的基础.

模型介绍

• 输入空间：$\mathcal{X}\subseteq {\mathbf{R}}^n$; 输入：$x={(x^{(1)},x^{(2)},\cdots ,x^{(n)})}^T\in \mathcal{X}$

• 输出空间：$\mathcal{Y}=+1,-1$; 输出：$y \in \mathcal{Y} $

• 感知机：

$$f(x)=\mathrm{sign}(w\cdot x+b)=\{\begin{array}{ll}+1,& w\cdot x+b\ge 0\\ -1,& w\cdot x+b<0\end{array}$$

其中，$w={(w^{(1)},w^{(2)},\cdots ,w^{(n)})}^T\in {\mathbf{R}}^n$称为权值（Weight），$b\in \mathbf{R}$称为偏置（Bias），$w\cdot x$表示内积

​ $w\cdot x=w^{(1)}{x}^{(1)}+w^{(2)}{x}^{(2)}+\cdots +w^{(n)}{x}^{(n)}$

• 假设空间：$\mathcal{F}=\{f\mid f(x)=w\cdot x+b\}$

几何意义

wx+b对应于特征空间中的一个分离超平面S,其中w是S的法向量,b是S的截距.S将特征空间划分为两个部分,位于两个部分的点分别被分为正负两类。

流程图

学习策略

感知机模型要求数据必须是线性可分的

策略

找到一个最优的超平面，将数据完整的划分成正类和负类

距离是如何计算的呢？

损失函数

误分类点$x_i$到$\mathbf{S}$的距离：

$$-\frac{1}{\parallel w\parallel }{y}_i(w\cdot x_i+b)$$

所有误分类点$x_i$到$\mathbf{S}$的距离：

$$-\frac{1}{\parallel w\parallel }\sum _{x_i\in M}{y}_i(w\cdot x_i+b)$$

当M中的误分类点越少，则总距离越短。当没有误分类点时，M代表的是空集

损失函数：

$$L(w,b)=-\sum _{x_i\in M}{y}_i(w\cdot x_i+b)$$

算法

对上文得到的损失函数求偏导得到梯度：

$${\mathrm{\nabla }}_{w}L(w,b)=-\sum _{x_i\in M}{y}_i{x}_i;{\mathrm{\nabla }}_{b}L(w,b)=-\sum _{x_i\in M}{y}_i$$

参数更新：

算法流程（原始形式）

（1）选取初始值$w_0,b_0$;

（2）于训练集中随机选取数据$(x_i,y_i)$;

（3）若$y_i(w\cdot x_i+b)\le 0$,

​ $w\leftarrow w+\eta y_i{x}_i;b\leftarrow b+\eta y_i$

(4)转（2），直到训练集中没有误分类点。

例题

要求出分离超平面，就是要将上文定义的所有损失函数的平均最小化，从而确定参数w，b

故本题的学习问题为：

$$\underset{w,b}{\arg min}L(w,b)=\underset{w,b}{\arg min}[-\sum _{x_i\in M}{y}_i(w\cdot x_i+b)]$$

注：采用不同的误分类点的顺序，所得到的分离超平面顺序也是不同的

K近邻法

线性回归模型

引入

假设你想根据房子的大小来预测房子的价格，图中每个小十字架代表一栋房子，蓝色的直线为单变量线性回归模型。

学习过程：

• 将训练集中的房屋价格喂给学习算法
• 学习算法工作，输出一个函数，用h表示
• h表示hypothesis，代表的是学习算法的解决方案或者函数。
• h根据输入的x值得到y值，因此h是x到的y的一个函数映射
• 可能的表达式：$h_{\theta }(x)={\theta }_0+{\theta }_{1}x$，只有一个特征或者出入变量，称为单变量线性回归问题

代价函数

现有一个包含输入特征x和输出目标y的训练集，现要用来拟合这个训练集的模型是这个线性函数$f_{w,b}(x)=wx+b$

$w,b$是模型的参数，或称为系数和权重。

引入：如何衡量一条线与训练数据的拟合程度？

为此我们构建一个代价函数(cost function)，在不同的机器学习模型中，我们可能会引用不同的代价函数，在单变量线性回归模型中我们引用平方误差代价函数

$$J(w,b)=\frac{1}{2m}\sum _{i=1}^m(f_{w,b}(x^{(i)})-y^{(i)}{)}^2$$

通过绘制出等高线图可以看出来，必定存在某个点，使得代价函数最小，即：可以看出在三维空间中存在一个使得J(θ0,θ1)最小的点。

梯度下降

概念：梯度下降是一个用来求函数最小值的算法，它在机器学习中常常用来优化损失函数。

引入：假设你站在山顶想要以最快的速度下山，你该怎么做？

解决方法：先360°环顾四周，然后选择一条最陡的路前进一小步，停下来，重复之前的动作，直至到达山底为止。

tips：根据选择参数的不同，起点的位置也不相同，这使得每次规划的路线都不相同。

梯度下降的算法公式为：

$$\begin{gathered} w=w-\alpha \frac{\partial }{\partial w}J(w,b) \\ b=b-\alpha \frac{\partial }{\partial b}J(w,b) \end{gathered}$$

对$w$赋值，使得$J(w)$按照梯度下降最快的方向进行，一直迭代下去，最终得到局部最小值。$w$决定了当前变量的位置，起始位置不同得到的导数也不同。

学习率：α是学习率，它决定了我们沿着能让代价函数下降程度最大的方向向下迈出的步子有多大。

• 学习率太小：收敛速度慢需要很长的时间才会到达全局最低点
• 学习率太大：可能越过最低点，甚至可能无法收敛

用于线性回归的梯度下降

让我们来整体回顾一下之前学到的三部分内容

这种梯度下降的算法称之为批量梯度下降算法，主要特点：

• 在梯度下降的每一步中，我们都用到了所有的训练样本
• 在梯度下降中，在计算微分求导项时，我们需要进行求和运算,需要对所有m个训练样本求和

多维特征

我们继续利用本章的房价模型，与之前不同的是增加了更多的特征，比如：房间楼层、房间数量、地理位置等，构成了一个含有多个变量的模型。

$x_j$：第几个特征列表

$n$：代表的是特征的数量

${\overrightarrow{x}}^{(i)}$:包含第i个训练示例的所有特征的向量。例：${\overrightarrow{x}}^{(2)}=$ $ \left[ \begin{matrix} 1416 & 3 & 2 &40 \ \end{matrix} \right] \tag{5}$

$x_j^{(i)}$：表示的是第i个训练实例的第j个特征；i表示行，j表示列

则多变量的线性回归模型表示为：

$$f_{\overrightarrow{x},b}(\overrightarrow{x})=\overrightarrow{w}\cdot \overrightarrow{x}+b=w_1{x}_1+w_2{x}_2+w_3{x}_3+...+w_n{x}_n+b$$

用于多元回归的梯度下降法

与单变量线性回归类似，在多变量线性回归中，构建一个代价函数，则这个代价函数是所有建模误差的平方和，即：

支持向量机算法（Support Vector Machine）

引入

要解决的问题：1.什么样的决策边界才是最好的呢？

​ 2.特征数据本身如果就很难分，怎么办呢？

​ 3.计算复杂度怎么样？能实际应用吗？

决策边界：选出离样本点尽可能远的区域，样本点离决策边界越远，说明分类的效果越好

tips：这里谈论的训练集是线性可分的

目标：SVM尝试寻找一个最优的决策边界距离两个类别的最近的样本最远

距离与数据定义

距离（性能指标）：最近的一个雷到决策边界的距离是多少？

支持向量机是一种监督算法，即我们需要对数据进行处理

数据标签的定义：

数据集：（$x_1,y_1$）（$x_2,y_2$）...（$x_n,y_n$）

y为样本的类别（标签）：当X为正例时候$y=+1$，当X为负例时候$y=-1$

决策方程：$y(x)=w^T\varphi (x)+b$(其中$\varphi (x)$是对数据做了变换，$w$是一个向量，b是一个常数)，即$y_{i} \cdot y(x_{i})>0 $

目标函数推导

通俗解释：找到一个线（即确定参数w和b），使得离该线最近的点（雷区）能够最远

将距离公式化简可得

$$distance=\frac{y_i(w^T\cdot \varphi (x_i)+b)}{\parallel w\parallel }$$

拉格朗日算子法求解

应用拉格朗日乘子法（在约束条件下求极值的方法）求解，将求解极大值问题转换成极小值问题

对偶性：$mi{n}_{w,b}ma{x}_{\alpha }L(w,b,\alpha )->max\alpha mi{n}_{w,b}L(w,b,\alpha )$

在求得$\alpha$的极大值后，则其（添负号）转换为求极小值后，最终的目标函数为：

$$\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)-\sum _{j=1}^n{\alpha }_i$$

求得目标函数后将数据代入目标函数，再分别对${\alpha }_1,{\alpha }_2...{\alpha }_n$求偏导然后得到了$\alpha$的值，之后将$\alpha$的值带入上式$w=...$，即可求得$w，b$

通过上述推导，我们可以得到如下结论：

$w,b$的值只依赖于训练数据中对应 ${\alpha }_i$>0 的样本点，其他的点对 $w,b$没有影响，我们将训练数据中对应于 ${\alpha }_i>0$ 的点成为支持向量。

软间隔(soft-margin)优化

软间隔：之前的方法要求要把两类点完全分得开，这个要求有点过于严格了，有时候数据中有一些噪声点，如图中左上方有一个离群的白点

为了解决该问题我们引入一个松弛因子

$$y_i(w\cdot x_i+b)\ge 1-{\xi }_i$$

由此我们得到一个新的目标函数

核函数的作用

引入

我们所谓的核函数映射是，直接在低维空间进行内积，把低维空间的结果映射到高维空间中。

常用的核函数为高斯核函数：

$$K(X,Y)=exp\{-\frac{\parallel X-Y{\parallel }^2}{2{\sigma }^2}\}$$