第一章 基础知识

绪论

什么是机器学习？维基百科上给出的一句话定义是：Machine learning is a field of study that gives computers the ability to learn from data without being explicitly programmed. 赋予计算机从数据中学习的能力，从而避免显式编程。所谓显式编程，就是平常编写程序的过程：给出一段代码使得计算机严格按照代码完成指令操作，而所谓隐式编程，类似于人类学习知识的过程：在课堂上学习知识，通过归纳、推理、演绎等方法，做到举一反三。现在的机器学习过程往往是喂入一些数据，通过某些学习算法，得到一个预测或者假设。

机器学习概念最早是 1959 年由 Arthur Samuel 在《Some Studies in Machine Learing Using the Game of Checkers》中提出的，他在文中使用了机器学习方法来下西洋跳棋 Checkers。这一过程中使用了自我博弈 self-play 的技术（这就是一种强化学习方法），当时就可以打败人类棋手。

机器学习的另一种经典定义是在 1997 年由 Tom Mitchell 在《Machine Learning》书中提出的。所谓学习就是：针对某项任务 Task，通过从过去的经验 Experience 中学习，最终的目的是提高性能 Performance。这也是学习的三要素：任务 T、经验 E 和性能 P。在计算机科学中，经验往往以数据的形式存在，学习任务往往以学习算法的形式存在，而性能就是该算法的性能。

在 2015 年时，Tom Mitchell 和 Michael Jordan 在《Science》上发表了封面文章《Machine Learning: Trends, perspectives, and prospects》，给出了机器学习更加细致的描述：机器学习是计算机科学和统计学的交叉学科，同时也是人工智能和数据科学的基础。

image

例如，计算科学发展到高级阶段就是研究“机器能否思考”这样一个问题——图灵议题，显然，会思考的机器当然也会学习，因此首先要从 Computing Machine 上升到 Learning Machine。而 AI 中的子方向，如视觉、NLP 都需要用到机器学习。

机器学习技术的应用：

• 社交媒体：用户画像，情感分析，垃圾过滤
• 交通服务：安全监控，空域管理
• 金融服务：趋势交易，量化投资，欺诈检测，投资组合管理
• 健康服务：药物研发，疾病诊断，机器人手术
• 电子商务：顾客服务，产品推荐，广告投放
• 虚拟助手：智慧代理，自然语言处理，元宇宙
• 计算广告学：假设我们要投放广告，那么投放什么样的广告，用户才最容易点击？广告投放一直是互联网产品盈利的主要模式。谷歌使用的就是逻辑斯蒂回归模型，输入是某个广告，输出是是否点击。同时谷歌还融入了知识图谱。
• 计算机博弈：DeepMind 的 AlphoGo 在围棋领域打败了人类冠军。主要使用了强化学习和深度学习。http://deepmind.com/research/alphago
• 控制领域：目前来说还是传统控制/优化做的比较好，主要也是使用强化学习方法。https://www.bostondynamics.com
• 医学图像识别：将肺部 CT 图输入到模型中，可以输出是否为病例以及病灶区域：深度学习。另一种是将人体各项指标数据（数值型/关系型数据）输入到模型中，可以输出决策准则判断是否为病例：机器学习/决策树。以及上述两种学习方法的融合：高维的图像数据用神经网络处理，关系型数据用统计学习处理。

神经网络中没有什么数学工具，讲究的是信号的逐层变换。统计学习中就有比较多的统计学知识，用决策树/近邻模型/超平面实现。近年来，机器学习逐渐演变为统计学习和深度学习两个分支。我们这门课主要讲统计学习。

基本框架

举个例子：垃圾邮件过滤。这是一个经典的文本挖掘任务，从邮件文本中获取信息，判断是否为垃圾邮件。因此，输入信息就是一封邮件，包括了 标题、日期、收件人、主题 等等；输出信息就是一个标签：是垃圾邮件/不是垃圾邮件。如果我们只是写简单的正则表达式来过滤垃圾邮件的话，那么就是一个显式编程。如果我们按照这种方式来喂给计算机数据：对于每封邮件，我们自行判断是否为垃圾邮件，并打上标签，也许写了 500 封（500 条训练数据）之后。可能第 501 封，计算机就会自行判断其是否为垃圾邮件——隐式编程。

那么如何进行这种隐式编程呢？首先我们要做 特征提取（传统机器学习模型无法直接处理千变万化的邮件文本，需要把它们变换成一个统一的特征；深度学习模型可以做）对于每封邮件，我们需要提取它的特征，例如以下 4 个特征和 1 个标签：

Category	Spam
FracOfAlpha	0.5
Sent at midnight	True
Subjects len	6
Contains ‘dollar’	True

这样我们就得到了机器学习的一个形式化框架：$\mathit{x}\in {\mathbb{R}}^d$

• 输入：$d$ 维特征向量：$\mathit{x}\in {\mathbb{R}}^d$，表示邮件的特征
• 输出：标量：$y=\{0,1\}$，二分类问题中，0 表示 Not-spam，1 表示 Spam
• 目标函数：真值函数：$f:\mathcal{X}\to \mathcal{Y}$，表示输入到输出的一个理想模型/真实函数，在这个函数的作用下，对于所有的数据，它可以尽量输出最为准确的结果。比如人脑就是一个真值函数，虽然它也会误判，但是我们的机器学习模型只要能达到人脑的准确率，我们就认为任务完成！那我们怎么得到这个真值函数呢？好比牛顿当年做实验推导 $F=ma$ 时，就是通过实验数据，发现和这个公式拟合得很好，因此就得出了这个物理公式。
• 数据：$N$ 条训练样本/数据：$({\mathit{x}}_1,y_1),\cdots ,({\mathit{x}}_N,y_N)$，包括输入和输出信息。
• 假设：$h:\mathcal{X}\to \mathcal{Y}$，也是输入空间到输出空间的一个映射，但是它不一定是对的，它只是针对训练数据表现最好的假设。显然假设函数和真值函数往往不一致，这和自洽的物理学不同。也就是说，机器学习可以在那些无法求得/不存在假设函数的领域有比较好的表现。

image

首先，我们并不知道目标函数 $f$ 长什么样，因此我们一般可以假设它是某种形式，比如假设它是线性模型，因此所有的线性函数构成的线性函数族，称为我们的假设空间 $\mathcal{H}$。我们从假设空间中需要找到一个假设函数 $h$，使得它和我们的目标函数最接近：与 $N$ 条样本符合程度最高。这个过程就叫做学习算法 $\mathcal{A}$。学习算法就是从假设空间中找到和样本尽量接近的假设函数 $h$，并将其作为输出。这个过程就是学习最自然、最基本的一个过程。这就是学习问题的两大核心要素：假设空间和学习算法。它们统称为学习模型。

问题：如果某个假设函数 $h$ 在训练数据集上和样本完全一致，那么它是不是就最接近我们的目标函数 $f$ 呢？显然不是，那是拟合 Fitting，不是学习 Learning。为什么呢？这里先卖个关子，不过答案可以先说：因为拟合得到的函数 $h$ 可能会过于复杂，与实际目标函数 $f$ 有较大差异。

假设空间

假设空间 Hypothesis Space $\mathcal{H}$ 就是从输入空间 $\mathcal{X}$ 到输出空间 $\mathcal{Y}$ 的映射的集合。确定假设空间就能得到候选函数，我们再从这些候选函数中通过学习算法得到最优的假设函数。

因此我们希望假设空间中的假设函数具有一些优良性质，我们将其称为正则性 regularity：

• 连续性 Continuity
• 光滑性 Smoothness：可以求导
• 简单性 Simplicity：线性函数 > 二次函数

例如二维空间中的线性超平面，就是一个假设空间：

image

显然可以找到某个最好的超平面，完美分开红蓝两类——如何学习？

损失函数

想要找到最好的假设函数，我们首先要介绍损失函数 loss function 的概念。

所谓最好，就是和样本符合程度最高，因此我们将模型的预测值 $h(\mathit{x})$ 和真实值 $y$ 之间的差距定义为损失函数 $\ell :\mathcal{Y}\times \mathcal{Y}\to {\mathbb{R}}_{+}$，它是一个二元函数。如果预测正确，损失函数为 $0$，没有损失；如果预测错误，那么损失函数值就是预测错误的惩罚。

我们已经学过了两种不同的损失函数：均方误差损失，常用于回归问题；01 损失，是一个示性函数，常用于分类问题：

$$\begin{array}{c}\ell (y,h(\mathit{x}))=(y-h(\mathit{x}){)}^2(\mathrm{Regression})\\ \ell (y,h(\mathit{x}))=\mathbf{1}[y\ne h(\mathit{x})](\mathrm{Classification})\end{array}$$

有了损失函数后，我们可以刻画我们的假设函数 $h$ 在所有 $m$ 条训练样本上的总体的一致性：将所有样本的损失函数值相加，将其称为经验误差/训练误差：最优的假设函数就是使得训练误差达到最小值：

$$\widehat{ϵ}(h)=\underset{\theta }{min}\sum _{i=1}^m\ell (h_{\theta }({\mathit{x}}_i),y_i)$$

这其中需要注意的是， $h_{\theta }({\mathit{x}}_i)$ 是以 ${\mathit{x}}_i$ 作为输入，以 $\theta$ 作为未知参数。例如二维线性超平面中，参数就是超平面的法向量，对应的 $h_{\theta }({\mathit{x}}_i)$ 就是输入向量与法向量的内积。而求解最小值对应的参数 $\theta$ 可以直接求关于参数 $\theta$ 的导数，令导数为零即可（费马定理）。

框架总结

因此所有的机器学习问题都需要考虑以下几个问题：

• 假设空间是什么？即从什么形式的函数族中取得假设函数？
• 损失函数是什么？针对不同的问题有不同的损失函数。
• 如何求这个优化问题？求导还是梯度下降？

对于不同的问题，以上都有不同的形式。例如，对于机器学习的四大范式 Paradigm：