机器什么时候能够学习？

作者: Boye0212 | 来源:发表于2020-08-11 19:57 被阅读0次

机器什么时候能够学习？
关于机器学习，你需要知道的三件事！
「干货」机器学习系统的结构
机器学习基石笔记：01 The Learning Problem
机器学习概念篇
机器学习入门
机器为什么能够学习？
机器什么时候可以学习？
机器学习基础
机器学习基石第七节

本系列是台湾大学资讯工程系林軒田（Hsuan-Tien Lin）教授开设的《机器学习基石》课程的梳理。重在梳理，而非详细的笔记，因此可能会略去一些细节。

该课程共16讲，分为4个部分：

机器什么时候能够学习？（When Can Machines Learn？）
机器为什么能够学习？（Why Can Machines Learn？）
机器怎样学习？（How Can Machines Learn？）
机器怎样可以学得更好？（How Can Machines Learn Better？）

本文是第1部分，对应原课程中的1-3讲。虽然第4讲在原课程中也放入了第1部分，但我认为它与后面第2部分的连贯性更强，因此移到后面。

本部分的主要内容：

介绍机器学习的概念与流程，并将它和其他几个相似的领域进行比较；
介绍感知机模型，说明普通的感知机学习算法PLA在什么条件下可以停下，如果不满足条件该怎么办；
列举机器学习的类别。

1 机器学习的概念

1.1 定义

机器学习的定义：improving some performance measure with experience computed from data。

什么时候可以用机器学习？有几个关键的地方：

确实存在一些需要学习的“潜在模式”，如预测下一次丢骰子的点数，就不能用机器学习；
没有简单的可编程的定义，如判断一张图像中是否包含了圆，就可以直接通过编程解决，不需要使用机器学习；
有一些关于要学习的模式的数据，如预测未来核能的滥用是否会导致地球毁灭，就不能用机器学习，因为没有历史数据。

1.2 组成部分

机器学习的实用定义如下图（灰字是以信用卡审批为例）：

可以看到，机器学习有以下几个要素：

未知的目标函数 $f: \mathcal X\rightarrow\mathcal{Y}$ ，在例中为理想的信用卡审批规则；
训练样本 $\mathcal{D}$ ，在例中为银行中信用卡审批的历史记录；
假设集 $\mathcal{H}$ ，在例中为一系列的候选规则；
学习算法 $\mathcal{A}$ ；
最终挑选出的假设 $g$ ，满足 $g\approx f$ ，在例中为最终“学习”出的规则。

机器学习的实用定义：使用数据计算出最接近于目标函数 $f$ 的假设 $g$ 。

1.3 和其他领域的关系

1.3.1 数据挖掘（DM）

数据挖掘：用（大）数据寻找感兴趣的性质。

如果这里所说的“感兴趣的性质”就是“接近目标函数的假设”，那么机器学习就等同于数据挖掘；
如果“感兴趣的性质”与“接近目标函数的假设”是相关的，那么数据挖掘可用来帮助机器学习，反之亦然；
传统的数据挖掘还关注在大数据库中的有效计算。

在现实中，很难区分ML和DM。

1.3.2 人工智能（AI）

人工智能：计算一些的有智能行为的东西。

如果 $g\approx f$ 就是那个有智能行为的东西，那么ML可用于实现AI。

如下棋，传统AI的做法是做博弈树，而ML的做法是从大量数据中进行学习。因此，机器学习是实现人工智能的一种途径。

1.3.3 统计学（Statistics）

统计学：使用数据对未知过程进行推断。

如果推断的结果就是 $g$ ， $f$ 是未知的，那么统计学就可以就用来实现机器学习；
传统的统计学聚焦于在数学假设下可证明的结果，而不太关注计算。

统计学为机器学习提供了很多有用的工具。

2 分类学习之感知机模型

2.1 PLA

这里介绍一个简单的分类模型：感知机（Perceptron）。

回顾上一节，在假设集 $\mathcal{H}$ 中，我们可以使用哪些假设？

在分类问题中，要预测的变量是正/负，或表示成 $+1$ / $-1$ 。我们可以对自变量做线性加权求和，然后设定一个阈值，若高于阈值，则分类为正，若低于阈值，则分类为负。若将“阈值”也看作在自变量中补入的常数项（ $\mathbb{w}$ 中补入对应的常数1），则这个模型可以写作 $h(x)=\text{sign}(\mathbf{w}^T\mathbf{x})$ 。

每一个 $\mathbb{w}$ ，都对应了一个假设。

那么，要如何从假设集 $\mathcal{H}$ 中找出最接近于目标函数的 $g$ 呢？也就是如何找出最好的 $\mathbb{w}$ ？

可以这样做，先任意设一个初始的 $\mathbf{w}_0$ （比如 $\mathbf{0}$ ），然后：

从该点开始，寻找错误分类的样本点，即找到满足 $\text{sign}(\mathbf{w}^T_t \mathbf{x}_{n(t)})\ne y_{n(t)}$ 的点 $(\mathbf{x}_{n(t)}, y_{n(t)})$ ；
利用找到的错误分类点对 $\mathbf{w}$ 进行更新，更新规则是： $\mathbf{w}_{t+1}\leftarrow\mathbf{w}_t +y_{n(t)}\mathbf{x}_{n(t)}$ 。
不断重复上述过程，直到找不出错误分类的点为止，最终得到要找的 $\mathbf{w}_{PLA}$ ，把它作为 $g$ 。

这就是感知机学习算法PLA（Perceptron Learning Algorithm）。更新规则的图示如下：

但是，以上算法仍然有不少问题：

该如何遍历所有的样本点？
它最终会停下来吗？需要满足什么条件？
停下来说明在样本 $\mathcal{D}$ 内已经没有错误了， $g\approx f$ ，那么在样本 $\mathcal{D}$ 外有用吗？
如果不满足使它能停下的条件怎么办？

2.2 PLA会停下吗？

PLA能停下来的必要条件是，存在一些 $\mathbf{w}$ 可以在 $\mathcal{D}$ 内不会犯错。这叫线性可分（linear separable）条件。那么，线性可分是PLA能停下来的充分条件吗？

答案是肯定的。证明的思路是，既然数据集线性可分，则一定存在某个 $\mathbf{w}$ 将样本完美分开，记为 $\mathbf{w}_f$ ，只需证明在经过有限次的迭代后的 $\mathbf{w}$ 和 $\mathbf{w}_f$ 的夹角的余弦的下限会超过1即可（因为余弦无法超过1，如果在经过特定次数的迭代后余弦的下限超过了1，说明在上一次迭代之后必定已经完成了完美的分类，无法找出错误分类的点进行迭代了），而余弦可以从分子（两个向量的内积）和分母（两个向量模的乘积）分别突破。具体证明如下：

因为 $\mathbf{w}_f$ 能完美分开数据集中的样本，即满足
$y_{n(t)}\mathbf{w}_f^T \mathbf{x}_{n(t)}\ge \min_n y_n \mathbf{w}_f^T \mathbf{x}_n \gt 0$

可令 $\min_\limits{n} y_n \dfrac{\mathbf{w}_f^T}{\Vert \mathbf{w}_f\Vert} \mathbf{x}_n=\rho$ ，则有

$\begin{aligned} \mathbf{w}_f^T\mathbf{w}_t &= \mathbf{w}_f^T(\mathbf{w}_{t-1}+y_{n(t-1)}\mathbf{x}_{n(t-1)})\\ &\ge \mathbf{w}_f^T\mathbf{w}_{t-1}+\rho\Vert\mathbf{w}_f\Vert\\ &\ge t\rho\Vert\mathbf{w}_f\Vert \end{aligned}$

而更新一定是在犯错的点处，所以触发第t次更新的样本一定满足 $y_{n(t-1)}\mathbf{w}^T_{t-1} \mathbf{x}_{n(t-1)}\le 0$ 。令 $R^2=\max_\limits{n} \Vert x_n\Vert^2$ （ $R>0$ ），则有

$\begin{aligned} \Vert\mathbf{w}_t\Vert^2 &= \Vert\mathbf{w}_{t-1}+y_{n(t-1)}\mathbf{x}_{n(t-1)}\Vert^2\\ &= \Vert\mathbf{w}_{t-1}\Vert^2+2y_{n(t-1)}\mathbf{w}^T_{t-1} \mathbf{x}_{n(t-1)}+\Vert\mathbf{x}_{n(t-1)}\Vert^2\\ &\le \Vert\mathbf{w}_{t-1}\Vert^2+\Vert\mathbf{x}_{n(t-1)}\Vert^2\\ &\le \Vert\mathbf{w}_{t-1}\Vert^2 + R^2\\ &\le t R^2 \end{aligned}$

接下来就看一看在经过 $T$ 次迭代后得到的 $\mathbf{w}_{T}$ ，它和 $\mathbf{w}_f$ 的夹角的余弦：
$\begin{aligned} &\dfrac{\mathbf{w}_f^T\mathbf{w}_{T}}{\Vert\mathbf{w}_f\Vert\Vert\mathbf{w}_{T}\Vert} \ge \dfrac{T\rho\Vert\mathbf{w}_f\Vert}{\Vert\mathbf{w}_f\Vert \sqrt{T R^2}}=\sqrt{T}\dfrac{\rho}{R} \end{aligned}$

而余弦必定小于1，因此必有迭代次数 $T\le \dfrac{R^2}{\rho^2}$ ，证明完毕。

从直觉上理解，PLA算法通过不断迭代，可以使得 $\mathbf{w}$ 越来越接近于 $\mathbf{w}_f$ 。

PLA算法的优点是简单、快、对任意维度的数据都可用，但缺点在于，一方面我们假设了数据集 $\mathcal{D}$ 是线性可分的，而现实中我们不知道是否真的如此，另一方面我们不知道它到底多久会停下，尽管在实践中算法往往很快停下。

2.3 Pocket算法

如果数据中有噪声，导致数据集不是线性可分的，怎么办？

当然，可以直接取 $\mathop{\arg\min}\limits_{w}\sum\limits_{n=1}^{N}{\mathbf{1}_{[y_n\ne \text{sign}(\mathbf{w}^T\mathbf{x}_n)]}}$ 作为 $\mathbf{w}_g$ ，但由于要一一遍历所有样本，这是个NP-hard问题。

那怎么办呢？可以对PLA做一些修改：

把当下找到的最佳 $\hat{\mathbf{w}}$ 先存起来，就好比放在口袋里；
在找到一个使 $\mathbf{w}_t$ 分类错误的样本之后，进行和PLA一样的更新，即 $\mathbf{w}_{t+1}\leftarrow\mathbf{w}_t +y_{n(t)}\mathbf{x}_{n(t)}$ ；
比较 $\mathbf{w}_{t+1}$ 和 $\hat{\mathbf{w}}$ 在整个数据集上谁犯的错误较少，若前者少，则将前者放入口袋，反之仍保留 $\hat{\mathbf{w}}$ 在口袋中；
不断循环，在经过一定次数的迭代后，停止上述过程，最终在口袋中的 $\hat{\mathbf{w}}$ 就取为 $g$ 。

由于始终有一个 $\hat{\mathbf{w}}$ 在口袋中，因此这种算法被称为Pocket算法。

3. 学习的分类

依据输出空间 $\mathcal{Y}$ 的不同来分：

二分类问题： $\mathcal{Y}$ 为 $+1$ 或 $-1$ ；
多分类问题： $\mathcal{Y}$ 有更多的类别；
回归： $\mathcal{Y}=\mathbb{R}$ 或 $\mathcal{Y}=[\text{lower}, \text{upper}]\subset\mathbb{R}$ ；
结构学习（Structured Learning）： $\mathcal{Y}$ 是某种结构，如学习出句子的结构等。

依据数据标签 $y_n$ 的不同来分：

监督（Supervised）学习：每个 $\mathbf{x}_n$ 都有对应的 $y_n$ ；
无监督（Unsupervised）学习，没有标签 $y_n$ ，如聚类、密度估计、离群点检测等；
半监督（Semi-supervised）学习：只有一小部分数据有标签，需要充分利用无标签数据，避免代价昂贵的手动打标签；
强化学习（Reinforcement Learning）： $y_n$ 被隐含在goodness $(\tilde{y}_n)$ 中。

依据 $f\Rightarrow (\mathbf{x}_n, y_n)$ 的不同来分：

Batch：所有的数据都是已知的；
Online：被动获取的序列数据；
Active Learning：通过策略不断主动询问某个 $\mathbf{x}_n$ 的 $y_n$ 是什么，来获得序列数据。

依据输入空间 $\mathcal{X}$ 的不同来分：

具体的（Concrete）特征： $\mathcal{X}\subseteq \mathbb{R}^d$ 的每个维度都有复杂的物理意义。
原始的（Raw）特征：只有简单的物理意义，如手写数字识别，特征是每个像素点的灰度，往往需要人或机器将它转换为具体的特征。
抽象的特征：没有或几乎没有物理意义，如打分预测系统， $\mathcal{X}$ 是用户id， $\mathcal{Y}$ 是对某部电影的评分，也需要做特征转换/抽取/构造。

我的公众号

机器什么时候能够学习？
本系列是台湾大学资讯工程系林軒田（Hsuan-Tien Lin）教授开设的《机器学习基石》课程的梳理。重在梳理，而...
关于机器学习，你需要知道的三件事！
摘要：MATLAB开发运营团队深度解析何为机器学习，什么时候使用机器学习，如何选择机器学习算法，MATLAB到底能...
「干货」机器学习系统的结构
机器学习系统是指能够在一定程度上实现机器学习的系统。机器学习系统能够从某个过程或环境的位置特征中学到有关信息，并且...
机器学习基石笔记：01 The Learning Problem
什么时候适合用机器学习算法？存在某种规则／模式，能够使性能提升，比如准确率；这种规则难以程序化定义，人难以给出...
机器学习概念篇
学习笔记整理如下：一、机器学习定义：广义概念：机器学习是一种能够赋予机器学习的能力以此让它完成直接编程无法完成...
机器学习入门
什么是机器学习从广义上来说，机器学习是一种能够赋予机器学习的能力以此让它完成直接编程无法完成的功能的方法。从实...
机器为什么能够学习？
本系列是台湾大学资讯工程系林軒田（Hsuan-Tien Lin）教授开设的《机器学习基石》课程的梳理。重在梳理，而...
机器什么时候可以学习？
Q：学习的最终目的是什么？A：学到去解决未知事物的能力。Q：机器学习的目的是什么？A：我们期望计算机能够在它没看过...
机器学习基础
机器学习一、基本概念 1.机器学习概念机器学习是一门能够让编程计算机从数据中学习的计算机科学和艺术。 2.为什...
机器学习基石第七节
转自：# The VC Dimension 前几节课着重介绍了机器能够学习的条件并做了详细的推导和解释。机器能够学...