---
schema_version: "library-reader-v1"
source_type: "original_book"
title: "智慧的疆界 从图灵机到人工智能"
author: null
edition: null
publisher: null
year: null
isbn: "9787111778004"
library_document_id: "cf76bc49-7e9b-4f42-bee8-3050a9fb9feb"
source_sha256: "a6e4d0c30c2781e62277891f79f33c2f62c58ae8db77453807229919f720b432"
pdf_physical_page_count: 456
pdf_physical_page_index_base: 0
range_start: 230
range_count: 10
html_url: "https://workshop.closeclaw.top/api/ai/read/cf76bc49-7e9b-4f42-bee8-3050a9fb9feb?start=230&limit=10"
markdown_url: "https://workshop.closeclaw.top/api/ai/read/cf76bc49-7e9b-4f42-bee8-3050a9fb9feb.md?start=230&limit=10"
previous_url: "https://workshop.closeclaw.top/api/ai/read/cf76bc49-7e9b-4f42-bee8-3050a9fb9feb.md?start=220&limit=10"
next_url: "https://workshop.closeclaw.top/api/ai/read/cf76bc49-7e9b-4f42-bee8-3050a9fb9feb.md?start=240&limit=10"
---

# 智慧的疆界 从图灵机到人工智能

> 页码规则：PDF_PHYSICAL_PAGE_INDEX 是从 0 开始的权威文件物理页索引；PRINTED_PAGE 是页面中识别出的印刷页码，可能为空，二者不得混用。

## PDF_PHYSICAL_PAGE_INDEX=230 | PRINTED_PAGE=215

$\mathrm { L } _ { 0 }$ 范数、 $\mathrm { L } _ { 1 }$ 范数、 $\mathrm { L } _ { 2 }$ 范数、迹范数、Frobenius 范数和核范数等不同类型的范数，都是数学和人工智能领域可能用到的，其中的三个“ $p$ 范数”特例，即 $\mathrm { L } _ { 0 }$ 范数、 $\mathrm { L } _ { 1 }$ 范数和 $\mathrm { L } _ { 2 }$ 范数在机器学习领域最为常用，笔者以这三个范数来介绍罚函数的内容。

$\mathrm { L } _ { 0 }$ 范数、 $\mathrm { L } _ { 1 }$ 范数和 $\mathrm { L } _ { 2 }$ 范数都是派生自“ $p$ 范数”的特例，为了稍后解释“正则化为什么能做特征选择”这个问题时有必要的知识储备，这里我们从几何意义的角度去了解 $p$ 范数的含义： $p$ 范数的本质也是长度的度量，对于不同 $p$ 取值的 $p$ 范数，其几何含义可理解为描绘该取值下空间中单位球（UnitBall，表示在空间中半径为 1 个单位的球面）的形状。最符合初等数学的直观认知是 $p$ 取值为 2 时的情况，此时在二维平面上单位球是一个圆形，在三维空间上单位球是一个正球体，更高维度也是类似的，单位球都是到原点距离为一个单位的点的全集， $p$ 等于 2 时的距离称为欧氏距离。在p 为其他值时单位球的变化如图 6-23 所示，请读者特别记住 $p$ 取值为 1 和 2 的单位球形状：菱形和圆形。

除了最符合我们日常空间几何概念的 $p = 2$ 表达的欧氏距离之外，还有$p = 0$ 时表达的是汉明距离， $p = 1$ 时表达的是曼哈顿距离等。尽管这些特殊距离都有各自的意义，但是 $p$ 范数的公式是统一而简洁的，如下所示：

$$
\begin{array} { r l } { \| x \| _ { p } } & { { } ( | x _ { 1 } | ^ { p } + | x _ { 2 } | ^ { p } + \dotsb + | x _ { n } | ^ { p } ) ^ { 1 / p } } \end{array}
$$

式中“ || ||”是范数符号。 $\mathrm { L } _ { 0 }$ 范数、 $\mathrm { L } _ { 1 }$ 范数和 $\mathrm { L } _ { 2 }$ 范数就是 $p$ 范数在 $p$ 取值

第 6 章 机器学习概览

215

## PDF_PHYSICAL_PAGE_INDEX=231 | PRINTED_PAGE=216

分别为 0、1、2 时的特例情况，替换后得出以下三种范数公式：

从公式上看， $\mathrm { L } _ { 1 }$ 范数是向量中各个元素的绝对值之和， $\mathrm { L } _ { 2 }$ 范数是向量中所有元素的平方之和再开方。把 $\mathrm { L } _ { 0 }$ 范数的公式写出来，会发现由于p 出现在分母上，零值是无意义的<sup>○一</sup>，而 $\mathrm { L } _ { 0 }$ 范数的真实含义是向量中非零元素的数量之和。

根据 $\mathrm { L } _ { 0 }$ 范数、 $\mathrm { L } _ { 1 }$ 范数和 $\mathrm { L } _ { 2 }$ 范数的公式，无论是非零计数、绝对值还是开平方，每一个参与公式计算的参数，无论其数值大小、正负都只会对计算结果产生非负的贡献，只是影响程度不同，所以这三个公式都符合“参数数量越多、参数值越大，输出结果就越大”这个特征，我们只要令罚函数${ } ^ { \ast } \thinspace \mathcal { Q } ( \pmb { w } ) = | | \pmb { w } | | _ { 0 } ^ { \phantom { \dagger } \prime \dagger } \ { } ^ { \mathcal { Q } } ( \pmb { w } ) = | | \pmb { w } | | _ { 1 } ^ { \phantom { \dagger } \prime \dagger }$ 或者 $\mathbf { \nabla } ^ { \ast } \mathcal { Q } ( \pmb { w } ) = | | \pmb { w } | | _ { 2 } ^ { \mathbf { \nabla } _ { | | } \mathbf { \nabla } _ { 2 } \mathbf { \xi } }$ ”，即可达到限制模型复杂度过高的目的。

不过，既然 $\mathrm { L } _ { 0 }$ 范数、 $\mathrm { L } _ { 1 }$ 范数、 $\mathrm { L } _ { 2 }$ 范数以及其他形式的范数是共存的，那说明它们在某些地方有自己的特长，这才有共存的意义，也从侧面说明罚函数使用不同的范数来实现，效果一定是有所差别的。下面我们就继续来看看这三个范数的使用场景和含义。

$\mathrm { L } _ { 1 }$ 范数的作用是“参数稀疏化”，由于这个特性， $\mathrm { L } _ { 1 }$ 范数还有个别名叫作“稀疏正则算子”（Lasso Regularization）。首先我们来解释什么叫“参数稀疏化”，数学上说一个向量“稀疏”是指它所包含的零元素的数量很多。 $\mathrm { L } _ { 0 }$ 范数的意义是计算非零参数的个数，所以它的稀疏性是最直接的，把 $\mathrm { L } _ { 0 }$ 范数作为目标函数的一部分，在最小化目标函数的过程中，其目标就自然带有尽可能获得零参数的倾向，但是由于最小化 $\mathrm { L } _ { 0 }$ 范数已被证明是一个 NP 完全问题，要付出极高的代价才有可能优化好，所以实践中并不适用。如果特别注重模型参数数量的话，可以用 $\mathrm { L } _ { 1 }$ 范数代替 $\mathrm { L } _ { 0 }$ 范数来实现稀疏化。 $\mathrm { L } _ { 0 }$ 范数的稀疏性从它的定义公式中就可以明显看出来，至于 $\mathrm { L } _ { 1 }$ 范数为什么也会有稀疏性，我们会在讲解完稀疏特性的意义之后，从几何意义的角度给出解释。

216

第三部分 第三波高潮

○一 严格来讲，p 在（0, 1）取值范围内定义的并不是范数，因为这违反了三角不等式（||x +y|| ≤ ||x|| + ||y||），因此 L<sub>0</sub> 范数不是真正的范数。

## PDF_PHYSICAL_PAGE_INDEX=232 | PRINTED_PAGE=217

稀疏性在机器学习中是很令人趋之若鹜的特性，它天然地解决了机器学习中的一对大难题：“自动特征选择”（Auto Feature Selection）和模型的“可解释性”（Interpretability）。前面我们遗留了“如何自动做特征选择”这个问题没有回答。特征选择之所以重要，是因为一般来说样本的大部分特征都和最终的输出没有什么关系，不对结果提供任何信息或者只提供极少量的信息。如果在最小化目标函数的时候考虑了这些额外的特征，虽然可以获得更小的训练偏差，但在预测新的样本时，这些无用的信息反而会干扰对结果的正确评价。稀疏规则化算子能天然地将模型中对结果影响小的参数权值置为零，这样就去掉了这些没有提供信息的特征，自动完成了特征选择。另一个青睐稀疏的理由是，将无关的特征置零后得到的简单模型更容易解释。这一点也很容易理解，譬如，假设要统计患某种疾病的概率，且我们收集到的数据样本有 1000 个特征，换句话说，我们需要寻找这 1000 个特征到底是怎样影响病人患上这种疾病的。如果通过 $\mathrm { L } _ { 1 }$ 范数正则化之后，最后学习到的模型只有很少的非零元素，譬如只有 5 个非零的系数，那么我们就有理由相信，这些对应的特征在患病分析上面提供的信息是巨大的，是决定性的。也就是说，患不患这种病基本只和这五个因素有关，那医生就好分析多了。但如果 1000 个参数都不为零，医生面对这 1000 个致病因素是无法通过模型来寻找和解释致病原因的。

$\mathrm { L } _ { 0 }$ 范数的定义本来就是零值越多，函数值便越小，它参与到目标函数之后，模型有稀疏性是很好理解的。而关于 $\mathrm { L } _ { 1 }$ 范数稀疏性的来源，我们就需要专门从几何角度去解释为什么它会具有这样的特性。

我们把前面的目标函数稍微改写一下，不直接加入罚函数，而是把“计算损失函数和罚函数总和极小值的最优解作为优化目标”，改写为“在罚函数不超过单位常量值 C的前提下求损失函数极小值的最优解作为优化目标”，即把损失函数和罚函数独立约束，形成如下形式：

$$
w ^ { * } \operatorname * { a r g m i n } _ { \boldsymbol { w } } \sum _ { i } \operatorname { L o s s } ( y _ { i } , f ( x _ { i } , \boldsymbol { w } ) ) , \mathcal { L } \boldsymbol { \mathcal { Y } } \dot { \mathcal { K } } : \mathcal { Q } ( \boldsymbol { w } ) \leqslant C
$$

以只有两个参数的简单情况为例，图 6-24 中的曲线是损失函数优化过程中的等值线，读者可将这里的“等值线”想象为地图中的“等高线”，这种等值线是把函数值相等的损失函数对应的参数 $\ w _ { 1 } , \ w _ { 2 }$ 组成的点连接起来，越接近中心线代表函数值越小，越接近外延线代表函数值越大。

第 6 章 机器学习概览

217

## PDF_PHYSICAL_PAGE_INDEX=233 | PRINTED_PAGE=218

假如没有罚函数的结果不能大于 C这个约束，损失函数的极小值就是等值线中最小的那一个或者多个点，即图 6-24 中函数图像中间的低谷，但是受限于 ${ } ^ {  } \mathcal { Q } ( w ) \leqslant C ^ { \prime \prime }$ 这个约束，损失函数并不能取到最小值，而是必须在符合罚函数约束的范围内找到损失函数能达到最小的那个点。回想一下前面对 $p$ 范数单位球图像的介绍，当 $p = 1$ 时 $p$ 范数的图像，即 $\mathrm { L } _ { 1 }$ 范数的图像在平面中是边长为 C的菱形。显而易见，在多数情况下（极值点在单位球之外），有约束时的极小值会出现在罚函数边缘与损失函数等值线的交点处，而且这个交点就是菱形的一个角。

在角上相交就意味着其中一个参数为零，这就是 $\mathrm { L } _ { 1 }$ 范数稀疏性的来源，而在更高维的情况下，除了角点之外，还有很多边会发生与等值线的第一次相交，产生稀疏性。相比之下， $\mathrm { L } _ { 2 }$ 范数就没有这样的性质，因为 $p = 2$ 时 $p$ 范数的单位球图像是个圆形，如图 6-25 所示。

由于没有菱形的角存在，所以第一次相交的地方出现在具有稀疏性的位置的概率就变得非常小了，这也从几何角度直观地解释了 $\mathrm { L } _ { 1 }$ 正则化能产生稀疏性而 $\mathrm { L } _ { 2 }$ 不能的原因。

L 范数是指向量各元素的平方和然后求平方根，它虽然没有稀疏性，却是一个比 $\mathrm { L } _ { 1 }$ 范数使用频率更高的范数，其应用场景不局限于机器学习，在各种科学领域都能看到它的身影。

218

第三部分 第三波高潮

○一 图片来源：https://www.coursera.org/learn/machine-learning。

## PDF_PHYSICAL_PAGE_INDEX=234 | PRINTED_PAGE=219

机器学习中， $\mathrm { L } _ { 2 }$ 范数也有两个别称，有的资料把用它的回归算法称作“岭回归”（Ridge Regression），有的资料叫它“权值衰减”（Weight Decay）。 $\mathrm { L } _ { 2 }$ 范数是用来解决机器学习中过拟合问题的主要手段之一，虽然 $\mathrm { L } _ { 1 }$ 范数也有一定的防止过拟合的作用，但如果以控制过拟合为目的， $\mathrm { L } _ { 2 }$ 范数的效果要比 $\mathrm { L } _ { 1 }$ 范数的效果好，因为 $\mathrm { L } _ { 2 }$ 范数相对于 $\mathrm { L } _ { 1 }$ 范数更平滑，换句话说，它更“温和”一些。在模型预测中， $\mathrm { L } _ { 2 }$ 范数往往比 $\mathrm { L } _ { 1 }$ 范数具有更好的预测特性，当遇到两个对预测有帮助的特征时， $\mathrm { L } _ { 1 }$ 范数倾向于选择一个更大的特征，而 $\mathrm { L } _ { 2 }$ 范数倾向于把两者结合起来。

总之， $\mathrm { L } _ { 1 }$ 范数、 $\mathrm { L } _ { 2 }$ 范数或者其他范数形式的正则化都是通过增加惩罚项，使得结果在偏差与方差之间取得平衡，从而使目标函数最小化来防止过拟合的。正则化是一种典型的、具有通用性的防止过拟合的方法，不过防止过拟合并不只有正则化这一种途径，不同的模型、策略中还有其他可行的办法，譬如神经网络中采用的 Dropout 就是根据神经网络特点设计的一种防止过拟合的技巧。

6.6.9 优化算法

目标函数一旦确定下来，就已经定下了采取何种模型的学习策略了，到这步，剩下的就是把模型中所有涉及的参数计算出来，归结为一个最优化的问题—求使得目标函数达到最小值时的参数数值解。机器学习中的优化算法就是为了求出这些参数数值解的算法。由于实践应用中，绝大多数情况下最优模型都是不存在解析解的，因此只能使用逐步逼近的计算方式来求数值解。同时，由于机器学习总是面对大量的训练样本，因此必须选择恰当的优化算法，才能确保找到全局的最优解，并且使得求解的过程足够高效。

第 6 章 机器学习概览

219

## PDF_PHYSICAL_PAGE_INDEX=235 | PRINTED_PAGE=220

在机器学习领域使用最广泛的优化算法是“梯度下降”（Gradient Descent）算法，它不仅广泛应用在传统的统计学习中，在神经网络和深度学习中也是一种常见的优化算法。在这一节，我们将以梯度下降算法为例，学习机器学习优化算法的原理和过程。

本节的邮件过滤系统实战是一个分类应用，在 6.6.5 节介绍损失函数时，我们提到了常用的平方损失函数，结合前面所讲的机器学习通式，要求解的目标函数如下所示：

$$
\boldsymbol { w } ^ { * } \quad \underset { w } { \operatorname { a r g m i n } } \frac { 1 } { n } \sum _ { i = 1 } ^ { n } \left( y _ { i } – f ( x _ { i } ) \right) ^ { 2 }
$$

在 6.6.6 节讲解模型选择时，我们又接触到了支持向量机，它要优化的是Hinge 损失函数，这时的目标函数形式如下：

$$
\boldsymbol { w } ^ { * } \ \underset { w } { \operatorname { a r g m i n } } \frac { 1 } { n } \sum _ { i = 1 } ^ { n } \operatorname* { m a x } ( 0 , \ 1 - \boldsymbol { w } ^ { \mathrm { T } } x _ { i } y _ { i } )
$$

其他形式的损失函数还有很多种，无论选择何种损失函数，模型训练最终都要解决如何求损失函数达到最小值时的系数向量这个共同的问题。梯度下降算法是最常用的迭代求解算法。“梯度”一词是微积分中的概念，数学上，对多元函数的参数求偏导数，把求得的各个参数的偏导数以向量的形式写出来就是梯度。这里把微积分中导数、偏导数和梯度的概念简单复习一下：当函数定义域和取值都在实数域时，导数可以表示函数曲线上的切线斜率，这是导数的几何意义，同时也代表了该函数在该点的瞬时变化率，这是导数的物理意义。如图 6-26 所示，对于一元函数，P 点的导数是当 x 变化一段很小的距离 $\Delta x$ 后，y 的变化量 $\Delta y$ 与 $\Delta x$ 的比值。

而对于多元函数，至少涉及两个自变量，也就是从曲线来到了曲面。曲线上的一点，其切线只有一条。但是曲面上的一点，其切线有无数条。偏导数是指多元函数沿坐标轴的变化率，如图 6-27 所示，在点 $( x _ { 0 } , y _ { 0 } )$ 上对x 的偏导数，就是指曲面被平面 $y = y _ { 0 }$ 所截得的曲面 $T _ { x }$ 在点M处的切线对x 轴的斜率。

220

第三部分 第三波高潮

## PDF_PHYSICAL_PAGE_INDEX=236 | PRINTED_PAGE=221

如果考虑多元函数沿任意方向的变化率的话，也可以使用相应的三角变换来求得偏导数，这称为在点 $( x _ { 0 } , y _ { 0 } )$ 的某个方向上的方向导数。方向导数代表了函数沿这个方向变化的快慢，所有方向导数中最大的那一个，即函数值下降最快的那一个，被称为“梯度”，负梯度方向就是函数值上升最快的方向。

第 6 章 机器学习概览

221

○一 图片来源：https://zh.wikipedia.org/wiki/ 微分。

## PDF_PHYSICAL_PAGE_INDEX=237 | PRINTED_PAGE=222

梯度有大小有方向，自然也是一个向量。依照梯度的定义，沿着梯度的正、负方向是最容易找到函数的最大值或者最小值的，因为这个方向的函数值变化最快。为求简单，前面的例子是一个简单的二维平面上的函数，对于三维或者更高维度的超平面，道理也是一样的。假如我们的函数定义在三维坐标系中，构成坐标轴的分别是参数 $\theta _ { 0 } , \ \theta _ { 1 }$ 以及函数 $J ( \theta _ { 0 } , \theta _ { 1 } )$ ，会更贴合我们日常身处三维现实世界的空间观。此时，对于函数 $J ( \theta _ { 0 } , \theta _ { 1 } )$ ，在点 $( \theta _ { 0 } , \theta _ { 1 } )$ 沿着正、负梯度向量的方向分别是函数值增大或者减小最快的地方，如图 6-28 所示，要寻找函数最小值，如同在一片凹凸不平的绵延深山中寻找那个地势最低的深谷谷底。

梯度下降算法就好比把我们随机传送到这片深山中的某处位置，我们的目的地是山下的深谷，由于我们并不知道下山的道路，因此决定走一步算一步，在每走到一个新位置的时候，先求得当前位置的梯度，以此作为行进的指导，然后沿着梯度的方向（这是当前位置最陡峭的方向），向下踏出下一步，到达下一个位置后继续求解这个新位置的梯度，再沿着最陡峭最快下山的方向踏出下一步。这样，保持固定的步长幅度，一步步地走下去，一直走到梯度值为零，从任何方向再踏一步都会比现在的位置更高的地方为止，这时就说明我们已经到了谷底了，这个过程可以用图 6-29 来直观表示。

222

第三部分 第三波高潮

○一 图片来源：Andrew Ng 的机器学习课程（https://class.coursera.org/ml-006）。

## PDF_PHYSICAL_PAGE_INDEX=238 | PRINTED_PAGE=223

向山下前进的方向由梯度决定，而每步行走的长度一般是人为选定的值，这个步长幅度被称为“学习速率”。行进中选择一个合理的学习速率很重要，如果学习速率过小，则会导致优化过程收敛速度很慢，需要踏出很多步、重复很多次梯度计算的过程，如果学习速率过大，则有可能阻碍收敛，如过大的步长，跨过了最低点，导致在低谷附近反复振荡。以下用伪代码来表述利用梯度下降算法求出最佳参数值的完整步骤：

第 6 章 机器学习概览

223

## PDF_PHYSICAL_PAGE_INDEX=239 | PRINTED_PAGE=224

如上面例子这样，通过梯度下降的方法走到一个全局极小值点仅是一种理想的情况，这里的“全局极小值”已经是一种简化，现实中，既不能保证算法走到的是“全局”极小值点，也不能保证全局只有“一个”极小值点。

试想一下，如果我们把随机传送的起始点的位置稍微调整一下，如图 6-29所示的另外一个起始点，根据相同的梯度下降算法，可能会得到另外一个最小值的结果，具体路径如图 6-30 所示。在理论上，全局有不止一个极小值完全是可能的。所幸对多数实际问题来说，情况都是相对简单的，往往只有一个全局极小值。

还有一种需要考虑的场景，可能确实存在一个全局的极小值，但是同时有大量的局部极小值，形象地说就是函数图像可能是“坑坑洼洼”的，这可能会导致我们无法顺利走到山下，而是走到某一个局部的洼地处徘徊，此时由于所有的方向都会令函数值增加，因此无法使用梯度下降的方法再继续前进了，如图 6-31 所示的函数图像就非常容易陷入某个局部极小值中。

从以上两个例子可以看出，纯粹的梯度下降算法并不能保证找到全局的最优解，得到的有可能只是一个局部最优解，不过由于实际问题中，许多目标函数天然是凸函数或者被精心设计成凸函数<sup>○一</sup>，只要损失函数是凸函数，局部最优解即为全局最优解，梯度下降算法得到的解就一定是全局最优解，所以，将目标函数设计为凸函数以及基于凸函数的优化技术，一直是机器学习的优化算法、策略算法关注的焦点。

224

第三部分 第三波高潮

下一段：[继续读取](https://workshop.closeclaw.top/api/ai/read/cf76bc49-7e9b-4f42-bee8-3050a9fb9feb.md?start=240&limit=10)