第2章
机器学习中的数学基础

2.1　微分学

2.1.1　链式求导法则

“链式求导法则”简称“链式法则（Chain Rule）”，是微积分学中非常重要的用于求复合函数导数的一条法则，其应用范围可以说相当广泛。

这条法则的定义如下。

如果u=g(x)在点x处可导，并且y=f(u)在点u处可导，则复合函数y=f(g(x))在点x处也可导，且其导
数为f＇(u)和g＇(x)的乘积。

它的表达式如下。

（f（g（x）））′=f′（g（x））g′（x）

也有如下的表达方式。

举个例子来说，如果y=e3x，需要求。

可以将y分解为y=eu，以及u=3x，这样一来，就可以应用复合函数求导法则了，计算过程如下。

在后续章节的学习中，在不少场合下都需要与导数打交道，因而建议读者复习高等数学的相关章节，做好知识储备。

2.1.2　对数函数求导

在后续强化学习章节中将使用到针对对数函数的求导知识，因而本节对此先做一个简单的介绍。假设有如下函数：

log（f（x））

如何计算它所对应的导数呢？

其实只要应用2.1.1节的链式法则即可得出。

设y=log（f（x）），u=f（x），那么根据复合函数的求导规则：

2.1.3　梯度和梯度下降算法

梯度（Gradient）是微积分中的一个概念——它代表的是某一个函数在某一点能产生最大变化率（正向增加，逆向减少）的方向导数。这样阐述读者可能觉得比较晦涩，我们以现实生活中的爬山为例子来做个类比。假设某人当前在某座山的某个位置，理论上他的下一步迈脚方向可以有N种选择。那么他应该如何做才能尽快到达山顶呢？梯度在这种情况下就可以发挥作用了——只要沿着它所指引的方向就一定是当前状态下的最佳选择（下山也是类似的，只是方向相反）。不过需要特别指出的是，如果函数本身是凸函数，那么梯度得到的有可能是局部最优解（可以想象一下在“崇山峻岭”中，我们很可能只是爬上了当前所处的“局部最高”的山峰）。

理解了梯度的概念后，那么梯度下降（Gradient Descent）算法就很好解释了。简单而言，它就是求解Gradient值的一类算法。它的核心实现步骤如下所述。

（1）计算各网络参数与计算损失函数（Loss Function）之间的梯度，实际上就是衡量各参数对精度损失的影响程度。

（2）朝着梯度值下降的方向更新各网络参数。

（3）循环往复直至达到结束条件。

虽然核心原理是类似的，但随机梯度也有多种演进版本，比如Batch GD、Mini-batch GD、SGD（Stochastic Gradient Descent，随机梯度下降）、Online GD等。而且这些版本之间的差异多数在于对样本集的选取和处理方式的不同。

假设我们的样本集合是：

Data=｛（x₁，y₁），（x₂，y₂），…，（x_N，y_N）｝

毋庸置疑，最理想的方案当然是在每次的迭代中都利用所有Data集来计算Loss Function。然而现实情况是我们有的时候没有办法做到这一点，例如，受限于计算资源等。因而如果实际考虑的样本数量是M，那么：

当M==1时就是SGD；

当M==N时就是Batch GD；

当M>1且M<N时就是Mini-batch GD。

如表2-1所示，从不同维度对上述几种GD算法进行横向比较。

表2-1　几种GD算法的比较

在实际的训练过程中，可以根据不同GD算法的优缺点来选择最适合自己的实现。

2.2　线性代数

2.2.1　向量

1．向量的定义

向量（Vector）是不少机器学习算法的基础之一，比如SVM（Support Vector Machine）。因而本节的内容中，将对它的基础概念做一个较为详细的阐述。

向量又被称为几何向量、矢量等，在数学领域是指具有大小和方向的量。与之相对的没有方向的量是数量。如图2-1所示是一个向量范例。

图2-1　向量OA

我们可以把如图2-1所示的向量表示为

所以如果要形象地表示它的话，向量其实就是从原点出发的一条线段。

2．向量大小和方向

如图2-2所示，既然向量带有大小和方向，那么应该如何计算这两个数值呢？

图2-2　向量的大小

还是以向量OA为例，它的大小在数学上通常被表示为

‖OA‖

计算过程如下。

更一般的表达方式如下。

向量的方向也是通过向量来表示的。比如对于如下向量：

V=（V₁，V₂）

如图2-3所示，它的方向向量表示如下。

图2-3　向量的方向

因为，且，所以上面的方向向量等价于：

d=（cos（θ），cos（α））

接下来通过scikit-learn库来编写一个用于计算向量大小和方向的代码范例。

（1）计算向量大小。

import numpy as np
v = [3,4]
np.linalg.norm(v) # 5.0

（2）计算向量方向。

import numpy as np
def direction(v):
return v/np.linalg.norm(v)
v = np.array([3,4])
w = direction(v)
print(w)

输出结果如下。

方向向量的范数总是等于1，比如：

0.62+0.82

=1

对此也可以从公式上加以证明。

因为方向向量：

d=（cos（θ），cos（α））

所以：

3．向量和

假设有如下两个向量：

v₁=（x₁，y₁）

v₂=（x₂，y₂）

那么它们的向量之和计算如下。

v₁+v₂

=（x₁+x₂，y₂+y₂）

从几何的角度来看，如图2-4所示。

图2-4　向量之和

如图2-4所示，向量之和可以通过如下步骤来计算得到。

（1）将向量平移至公共原点（如果需要的话）。

（2）以向量作为平行四边形的两条边，得到一个平行四边形。

（3）从公共原点出发的对角线，就是向量之和。

计算向量之和的Python范例代码如下。

输出结果如下。

4．向量点积

向量点积也被称为数量积，有几何定义和代数定义两种形式。

1）点积的几何定义

假设有两个向量x和y，那么点积的几何定义如下。

x⋅y=‖x‖‖y‖cos（θ）

其中，θ是两个向量之间的夹角，如图2-5所示。

图2-5　向量点积

所以当θ取不同值时，向量点积公式会有所差异，例如：

当θ等于0°时：

x⋅y=‖x‖‖y‖

当θ等于90°时：

x⋅y=0

当θ等于180°时：

x⋅y=-‖x‖‖y‖

2）点积的代数定义

假设x和y向量：

x=（x₁，x₂）

y=（y₁，y₂）

那么点积的代数定义如下：

x⋅y=x₁y₁+x₂y₂

相信读者在了解了点积的几何定义和代数定义后会有这样的疑问——它们之间有什么联系和区别呢？

简单来讲，它们其实是等价的。下面就来做一个简单的推导，如图2-6所示。

图2-6　点积代数定义的推导

图2-6中引入了两个新的角度变量来辅助推导，即α和β。

对于n维向量的点积，更一般的计算公式如下。

本节的最后，还是通过scikit-learn包来编写一个计算向量点积的程序，同样也分为几何定义和代数定义两种类型。

（1）向量点积的几何定义计算范例。

代码片段如下。

输出结果如下。

（2）向量点积的代数定义计算范例。

代码片段如下。

输出结果如下。

从这个例子中，也可以清楚地看到几何定义和代数定义下的两种向量点积确实是等价的。

2.2.2　矩阵拼接

在机器学习的数据集处理过程中，可能会经常遇到需要矩阵拼接的情况。对于很多新手来讲，类似vstack、hstack这些numpy基础操作难免有些“晦涩难懂”，因而在本节做一个统一的介绍。

1．stack

首先是numpy提供的stack函数，函数原型如下。

numpy.stack(arrays, axis=0)

官方对它的解释是：

Join a sequence of arrays along a new axis.（沿一个新轴连接一系列数组。）

从这句话可以看到，它用于将一个数组序列（每个数组的shape必须一致）按照一个新的维度（由第二个参数axis指定）来进行堆叠合并——意味着会比原数组增加一个维度，比如一维变成二维，二维变成三维等。这样描述可能有些抽象，下面结合几个实例进行分析。

import numpy as np
a = np.array([1, 2, 3])
b = np.array([2, 3, 4])
print(np.stack((a, b)))

在这个例子中，stack的第一个参数是（a，b），代表由a和b组成的数组序列；第二个参数没有显式提供，所以实际采用的是默认值0，表示第一个维度（另外，如果axis=-1的话表示最后一个维度）。

所以上述的np.stack（（a，b））表示“将a和b数组序列，沿着第一个维度进行堆叠合并”。换句话说，新增的维度是第一维，然后将a和b合并起来，不难得出最后的结果是：

同理，如果是同一个数组序列，采用axis=-1的话：

import numpy as np
a = np.array([1, 2, 3])
b = np.array([2, 3, 4])
print(np.stack((a, b), axis=-1))

那么表示“将a和b数组序列，沿着第二个维度进行堆叠合并”，所以a和b分别输出1和2，2和3，以及3和4，组成了新的二维数组。

2．split

有“合”必有“分”，它们都是数据处理中比较基础的操作类型。其中常用的切分函数是split，原型如下。

numpy.split(ary, indices_or_sections, axis=0)

这个函数简单来讲就是把一个数组分成多个子数组。其中：

●　ary：用于切分的数组。

●　indices_or_sections：从名称可以看出来，这个参数有两种类型，其一是整数N，表示平均切分为N个子数组；其二是一维数组，代表了切分点。

●　axis：沿着axis所指定的轴来进行切分，默认值为0。

以下面代码段为例：

import numpy as np
x = np.arange(9.0)
sp = np.split(x, 3)
print(sp)

其中，arange用于生成等差数组，默认起始点为0，步进为1（都可以省略），因而arange（9.0）其实表示的是：

在这个例子中，split的第二个参数是整数，也就是说，它的目的是平均切分x这个数组，所以得到的是如下结果。

那么如果遇到无法均分的数组呢？比如将x改为

x = np.arange(8.0)
sp = np.split(x, 3)

此时执行程序会导致如下错误。

再来看第二个范例：

import numpy as np
x = np.arange(8.0)
sp = np.split(x, [3, 5, 6, 10])
print(sp)

在这个例子中，split的第二个参数是一维数组，用于指定3、5等“分隔点”，因而得到的结果如下。

3．concatenate

单词concatenate的字面意思是“把（一系列事件、事情）联系起来”，用在数组操作上指的是（官方文档描述）：

Join a sequence of arrays together.（将一系列数组连接在一起。）

它的函数原型如下。

numpy.concatenate((a1, a2, …), axis=0)

其中，a1，a2，…代表一系列的array_like（即除了axis维度外，它们的shape必须要保持一致，否则会出错）；axis和前面的讲解类似，指的是“The axis along which the arrays will be joined”，默认值为0。

可以参考下面的一维数组concatenate范例。

import numpy as np
x = np.array([1, 2, 3])
y = np.array([3, 2, 1])
print(np.concatenate([x, y]))

输出结果为：

二维数组concatenate范例（axis=0）：

import numpy as np
d = np.array([[1, 2, 3],[4, 5, 6]])
print(np.concatenate([d, d]))

上述concatenate的第二个参数没有特别指定，所以采用的是默认值0，即第一维。输出结果如下。

二维数组concatenate范例（axis=1）：

import numpy as np
d = np.array([[1, 2, 3],[4, 5, 6]])
print(np.concatenate([d, d],1))

输出结果如下。

4．vstack

接下来分析vstack函数，它的原型如下。

numpy.vstack(tup)

官方文档中对vstack的描述是：

Stack arrays in sequence vertically (row wise).

大意：按顺序垂直堆叠阵列（按行排列）。

通过比较上述这句话与stack中定义语句的差异，至少可以看出：

（1）vstack并不特意增加一个维度。

（2）vstack的合并堆叠方向是垂直的，即沿着垂直方向。

下面以实际范例来理解vstack以及它的用法。

import numpy as np
x = np.array([1, 2, 3])
y = np.array([[9, 8, 7],[6, 5, 4]])
# vertically stack
vs = np.vstack([x, y])
print(vs)

输出结果如下。

5．hstack

与vstack相似的还有一个hstack，它的原型如下。

numpy.hstack(tup)

官方文档对它的描述同样很简洁：

Stack arrays in sequence horizontally (column wise).

大意：按顺序水平堆叠阵列（按列排列）。

说明它与vstack的区别在于堆叠方向不同。

下面通过实际范例来学习一下hstack的用法。

二维数组的hstack：

import numpy as np
x = np.array([[1, 2, 3],[4, 5, 6]])
y = np.array([[9, 8, 7],[6, 5, 4]])
# hstack
hs = np.hstack([x, y])
print(hs)

输出结果如下。

根据hstack的要求，参与stack的对象的维度必须保持一致（当然，除了axis参数指定的维度以外）。例如下面的范例：

x = np.array([[1, 2, 3]])
y = np.array([[9, 8, 7],[6, 5, 4]])
# hstack
hs = np.hstack([x, y])
print(hs)

可以看到x和y的维度不一致，这将会导致如下错误。

而如果调整一下数据：

x = np.array([[1, 2],[4, 5]])
y = np.array([[9, 8, 7],[6, 5, 4]])

显然调整后的x和y的维度仍然不一致，但因为并不影响hstack的操作过程，所以可以得到正确的结果。

另外，细心的读者可能已经看出concatenate和vstack/hstack有一些相似性——没错，事实上它们之间确实有非常紧密的关联，这一点从numpy源代码实现中可以得到验证。

（1）hstack关键源码：

（2）vstack关键源码：

还可以通过下面的代码段来验证。

import numpy as np
a = np.array([[1, 2], [3, 4]])
b = np.array([[5, 6], [7, 8]])
print("concatenate with axis =0:")
print(np.concatenate((a, b), axis=0))
print("concatenate with axis =1:")
print(np.concatenate((a, b), axis=1))
print("vstack:")
print(np.vstack((a, b)))
print("hstack:")
print(np.hstack((a, b)))

输出结果如下。

2.2.3　特征值和特征向量

每个人都有自己的特征，比如有的人“满腹经纶”，有的人是运动天才，而有的人则是情歌王子，等等。那么对于矩阵来说，它们是否也具备某种特征，这些特征又应该怎么衡量呢？

下面先来看特征值（Eigenvalues）和特征向量（Eigenvectors）的定义。

##特征值和特征向量定义
假设A是n阶矩阵，如果存在一个n维非零向量X和常数λ使得：
AX = λX
那么称λ为矩阵A的特征值，X为矩阵A的一个特征向量。

举个例子来说，假设有矩阵A：

以及向量X：

因为

所以根据前面的定义可知，X为矩阵A的特征向量，其特征值为1。

再分析一下特征值和特征向量的几何意义。AX=λX这个式子可以直译为“向量X乘以矩阵A，和向量X乘以一个常数λ是等价的”，更进一步地讲就是“一个特征向量X，和它对应的矩阵做变换时，只需要改变大小值（拉伸了λ），但却不用改变方向”，如图2-7和图2-8所示。

图2-7　特征值和特征向量的几何含义（矩阵变换前）

图2-8　特征值和特征向量的几何含义（矩阵变换后）

参考上述描述，可以看到，如果分别针对向量1、2和3执行针对下列矩阵A的变换操作：

那么变换后的图形显示，向量1和向量2并没有改变自己的原有方向（向量2比原来扩大3倍，向量1保持不动），而向量3既改变了大小，同时方向也变了。所以在这个范例中，向量1和向量2是矩阵A的特征向量。

顺便提一下，Eigenvectors是一个合成词。其中，Eigen在德语中的意思是“明确的”，也算是一个比较贴切的名字。

2.2.4　仿射变换

仿射变换（Affine Transformation）也称为仿射映射，是一种经典的坐标变换方式。我们知道，在图像领域，几何变换（Geometric Transformations）模型无非就是用于描述输入和输出图像之间变化的“拟合关系”（这一点和机器学习模型也是类似的）。比如下面列出的就是常见的一些几何变换以及针对它们的描述。

（1）刚体变换（Rigid Transformation）。如果经过几何变换后，图形中两点间的距离仍能保持不变，那么称之为刚体变换。由它的定义可知，刚体变换仅局限于镜像、旋转和平移，如图2-9所示。

图2-9　刚体变换图例

（2）投影变换（Projective Transformation）。投影变换是从向量空间映射到自身空间的一种线性变换，如图2-10所示。

图2-10　投影变换图例

（3）仿射变换（Affine Transformation）。这是本节的重点，接下来做重点介绍。我们可以从以下两个角度来定义和理解仿射变换。

①变换过程。

从变换的实际操作过程来理解的话，仿射变换就是：

线性变换+平移

换句话说，仿射变换是指针对一个几何向量空间进行一次线性变换以及平移变换后所得到的另一个向量空间，可以简单表示为

当然还可以增加一个维度，得到如下等价的表示法。

②变换性质。

仿射变换作为众多几何变换中的一种，它具有什么典型性质呢？

●　共线性（collinearity）：多个点如果在同一条线上，那么变换后它们仍然在同一条线上。

●　平行性（parallelism）：平行的线在变换后仍然保持平行。

●　长度比例（ratios of lengths）：线的比例保持不变。

……

仿射变换可以通过如下一系列原子操作（以及它们所对应的Affine Matrix）来组合完成。

●　Scale：缩放操作。其对应的Affine Matrix形如：

●　Reflection：镜像操作。其对应的Affine Matirx形如：

●　Rotation：旋转操作。其对应的Affine Matrix形如：

●　Shear：剪切变换。其对应的Affine Matrix形如：

●　Translation：平移变换。其对应的Affine Matrix形如：

图2-11直观地描述了仿射变换的效果。

图2-11　仿射变换图例

后续章节中还会接触到仿射变换，建议读者结合起来阅读。

2.3　概率论

概率论（Probability Theory）是研究随机现象规律和事件发生可能性的一个数学分支，在金融学、经济学、统计学、计算机等多个学科领域都有广泛的应用。另外，由于机器学习存在很多探索性实验，因而也和概率学理论有着紧密的关联。

概括而言，概率论通过随机变量、几何概率、概率分布、随机过程、极限理论、马尔可夫过程等核心理论，揭示了偶然随机事件在大量重复实验中所呈现出的各种规律。

2.3.1　概率分布

概率分布（Probability Distributions）是概率论中的重要组成部分，简单来讲，它表述了随机实验中各种可能结果（Outcomes）发生的可能性。例如，抛硬币时出现正、反两面结果的可能性，理论上都是0.5。概率分布通常可以被划分为两大类型，即离散型概率分布（Discrete Probability Distribution）和连续型概率分布（Continuous Probability Distribution）。

它们都涉及如下几个基本概念。

（1）随机变量（Random Variable）。

（2）随机事件（Random Event）。

（3）概率（Probability）。

（4）概率分布种类（Probability Distribution）。

概率论作为一门学科，在多年的发展历史中积累了非常丰富的理论基础和实践经验。本节主要讲解与机器学习强相关的一些概率论知识，读者有需要的话，还可以自行查找相关书籍资料来做扩展阅读。

1．随机事件和概率

自然界既存在确定性现象（例如水加热到100℃时会沸腾），同时也有很多随机现象（例如抛硬币时有可能正面朝上，也有可能反面朝上）。随机现象的每一次实验结果都具有不确定性，我们把它的每一次结果称为基本事件，或者样本点。那么全部的样本点就组成了样本空间。例如，掷骰子出现的点数的样本空间为｛1，2，3，4，5，6｝。

不难理解，基本事件是不可再分解的事件，而某些事件可以由基本事件复合而成——我们称之为随机事件，也简称为事件。例如，掷骰子实验中，规定事件Event1为点数大于3的情况，那么Event1=｛4，5，6｝。

在基本事件和随机事件的基础上，再来进一步了解概率的定义。简而言之，概率是用于衡量事件发生可能性的统计指标。如果从实验的角度来看，可以做这样的定义。针对随机现象的多次重复实验中，如果某事件E发生的频率随着实验次数的增加稳定在某个常数p附近，那么称事件E发生的概率为P（E）=p。例如，只要实验次数达到一定规模，那么掷骰子得到1～6的任何一个数的概率理论上都将是1/6。

2．随机变量

随机变量（Random Variable）是对随机实验结果的一种量化表示。举个具体的例子，假设我们在做产品抽样质量检测时，采取“有放回”的方式进行，在抽取n次后计算质量不合格产品的数量X，那么这个变量X在事先是不知道的，它取决于实验结果。换句话说，它是对实验结果的量化表示，因而在这个范例中X就是随机变量。

根据随机实验的不同，随机变量也有不同的分类。总的来说，可以把随机变量做如下分类。

随机变量

|---离散型随机变量

|---非离散型随机变量

|---连续型随机变量

|---混合型随机变量

如果随机变量的可能值是有限的，并且以确定的概率存在，那么就是离散型随机变量。例如，射击运动员不停射击直到中靶为止，那么射击次数就是离散型的随机变量。

连续型随机变量也很好理解。例如，工厂生产的同一类型螺丝理论上应该是同等长度的，但受限于工艺等原因，它们不可能完全一样——通常是在标准值附近浮动，例如，140mm±2mm。如果以生产出来的螺丝长度作为随机变量，那么它就是连续型的，并且符合一定的概率分布。

3．概率分布

离散型随机变量的概率分布可以参考如下定义。

如果离散型随机变量R的所有可能值是r₁，r₂，…，r_n，那么

P｛R=r_k｝=p_k（k=1，2，…，n）

称为随机变量R的概率分布，有时也简称为分布列或者分布律。

离散型随机变量的概率分布有很多种类型，常见的有二项分布、伯努得分布（又名两点分布或0-1分布）、泊松分布等。下面以两点分布为例来做介绍。

如果随机变量的概率分布满足如下条件：

P{R = k} = pkq1-k, k=0, 1 （0<p<1, p+q = 1）

那么称之为两点分布。换句话说，这种情况下实验结果只有两种可能性，比如射击是否上靶、天气预报是否下雨，等等。

连续型随机变量的情况稍微复杂一些，首先需要了解概率密度函数，它的定义如下。

如果存在某函数f（x），使得随机变量x在任一（a，b）区间的概率可以表示为，那么这一随机变量x就是连续型的随机变量，且f（x）是它的概率密度函数。显然，根据场景的不同，f（x）也有很多种类型，包括但不限于：指数分布、均匀分布、正态分布等。以正态分布（又名高斯分布）为例，它是由德国数学家Moivre在18世纪提出来的，其所对应的概率密度函数为

其中，M是位置参数，σ为尺度参数。当这两个参数的值分别为0和1时，正态分布也称为标准的正态分布。

总的来说，随机变量和概率分布是研究未知事件规律性的利器，它们在强化学习、深度学习等多种机器学习方法中都会有所涉及，因而建议读者结合起来分析研究。

2.3.2　先验／后验概率

概率（Probability）和似然（Likelihood）是两个容易混淆的概念，从单词释义的角度来说，它们都带有“可能性”的意味。不过它们在定义上是有显著区别的，我们借用一下Wikipedia提供的如下描述。

概率的定义：

Probability is the measure of the likelihood that an event will occur.

大意：概率是针对一个事件发生的可能性的度量。

似然的定义：

In statistics, a likelihood function (often simply the likelihood) is a function of the parameters of a statistical model given data.

大意：在统计学中，似然函数（通常简称似然）是给定数据的统计模型参数的函数。

而它们之间的区别在于：

Probability is used before data are available to describe plausibility of a future outcome, given a value for the parameter. Likelihood is used after data are available to describe plausibility of a parameter value.

大意：概率是在数据可用之前被用来描述未来结果的合理性、给定参数的值。似然在数据可用后被用来描述参数值的合理性。

也就是说，概率表达的是在某些参数已知的条件下，预测接下来在观测过程中发生某些结果的可能性；而似然则多少有点儿“相反”，它是指在某些结果已经发生的情况下，对参数所进行的估计。

相信不少读者会觉得这和先验概率（Prior Probability）和后验概率（Posterior Probability）相当类似。先验概率是指预测某件事情发生的可能性，体现的是“由因求果”的关系；而后验概率则是指事情已经发生了，要去推测出它的产生是由于某因素导致的可能性大小，反映的是“执果求因”的关系。

仅从定义上来理解可能有点儿抽象，因而接下来再结合一个实例帮助读者更好地梳理它们之间的关系。

假设现在抛一枚带有正反面的硬币，并观测结果是正面还是反面。如果硬币最终出现正面和反面的概率都是0.5，表示如下：

p_H=0.5

p_T=0.5

那么很显然连续抛两次硬币，都为正面朝上的概率为：

P（HH，p_H=0.5）=0.5×0.5=0.25

现在换一种思路：假设已经知道了连续抛两次硬币的结果都是正面朝上，那么p_H=0.5的似然性有多大？也就是：

L（p_H|HH）=P（HH|p_H=0.5）=0.25

换句话说，如果投两次硬币的结果都是正面朝上，那么p_H值为0.5的似然性为0.25。

上面出现的L即为似然函数（likelihood function）。不难发现，它满足如下表达式：

L（θ|ΗΗ）=P（ΗΗ|p_H=θ）=θ2

这里的似然函数最大值是多少呢？因为变量0≤θ≤1，所以最大值就是1了。此时表达的意思是——如果投一枚硬币正面朝上的概率（p_H）为1（这当然只能说是假设，估计不存在这样的硬币），那么最有可能出现投两次均为正面朝上的情况。

这同时也引出了最大似然估计的定义，在后续再进行专门的介绍。

2.3.3　最大似然估计

最大似然估计（Maximum Likelihood Estimation，MLE），又被译为极大似然估计或者最大概似估计等，是由德国数学家Gauss于1821年提出，并由英国统计学家和生物进化学家R. A. Fisher发展壮大的一种求估计的手段。

假设似然函数定义如下：

lik（θ）=f_D（x₁，x₂，…，x_n|θ）

其中，f_D代表的是事件的概率分布的密度函数，表示分布参数。如果可以找到一个使得似然函数的取值达到最大的值，那么它就被称为函数的最大似然估计。

下面援引Wikipedia上的一个范例。假设有三种类型的硬币放在盒子里，因为制作工艺不同它们抛出后正面朝上的概率分别为p_H=1/3，p_H=1/2，p_H=2/3。某次实验中共抛出硬币80次，最后统计出正面朝上共49次，反面朝上共31次，现在要通过最大似然估计求出哪种类型硬币的可能性最大。

这三种类型硬币对应的似然值分别为：

可见第三种硬币的可能性最大，换句话说，p的最大似然估计是2/3。

2.3.4　贝叶斯法则

贝叶斯法则（Bayes' theorem/Bayes theorem/Bayesian law）也称为贝叶斯定理或者贝叶斯规则、贝叶斯推理等，简单而言，它是英国学者贝叶斯于18世纪提出来的一个数学公式。公式本身并不复杂，如下。

其中：

●　P（A|B）是指B已经发生的情况下A的条件概率，也由于得自B的取值而被称作A的后验概率。

●　P（A）是A的先验概率（或边缘概率）。

●　P（B|A）是指A已经发生的情况下B的条件概率，也由于得自A的取值而被称作B的后验概率。

●　P（B）是B的先验概率（或边缘概率）。

上述释义中出现了前面也涉及过的先验概率和后验概率，这里再举一个例子来加深读者的印象。我们知道，如果一个人淋了雨，那么他有可能会感冒，那么：

P（感冒）是先验概率。

P（感冒|淋雨）是指淋雨已经发生的情况下，此人会感冒的条件概率，称为感冒的后验概率。

接下来简单推导一下贝叶斯公式。

首先，根据条件概率可知，当事件B发生的情况下事件A的条件概率是：

同理，当事件A发生的情况下事件B的条件概率是：

或者换一种表达形式就是：

P（A∩B）=P（B|A）×P（A）

这样一来，不难得出：

另外，贝叶斯公式也可以被理解为

后验概=（可能性×先验概率）／标准化常量

下面再引用Wikipedia上的一个吸毒者检测范例，来解释贝叶斯公式有哪些潜在的实用意义。

假设一个常规的检测结果的敏感度与可靠度均为99%，即吸毒者每次检测呈阳性（+）的概率为99%。而不吸毒者每次检测呈阴性（-）的概率为99%。从检测结果的概率来看，检测结果是比较准确的，但是贝叶斯定理却揭示了一个潜在的问题——假设某公司对全体雇员进行吸毒检测，已知0.5%的雇员吸毒。那么请问每位检测结果呈阳性的雇员吸毒的概率有多高？

我们假设D代表的是雇员吸毒事件，N为雇员不吸毒事件，“+”为检测呈阳性事件。那么可以得出：

（1）P（D）代表雇员吸毒的概率，不考虑其他情况，该值为0.005。因为公司的预先统计表明该公司的雇员中有0.5%的人吸食毒品，所以这个值就是D的先验概率。

（2）P（N）代表雇员不吸毒的概率，显然，该值为0.995，也就是1-P（D）。

（3）P（+|D）代表吸毒者阳性检出率，这是一个条件概率，由于阳性检测准确性是99%，因此该值为0.99。

（4）P（+|N）代表不吸毒者阳性检出率，也就是出错检测的概率，该值为0.01，因为对于不吸毒者，其检测为阴性的概率为99%，因此，其被误检测成阳性的概率为1-0.99=0.01。

（5）P（+）代表不考虑其他因素的影响的阳性检出率。该值为0.0149或者1.49%。可以通过全概率公式计算得到：此概率=吸毒者阳性检出率（0.5%×99%=0.495%）+不吸毒者阳性检出率（99.5%×1%=0.995%）。P（+）=0.0149是检测呈阳性的先验概率。用数学公式描述为

P（+）=P（+，D）+P（+，N）=P（+|D）P（D）+P（+|N）P（N）

根据上述描述，可以计算出某人检测呈阳性时确定是吸毒的条件概率P（D|+）：

换句话说，尽管吸毒检测的准确率高达99%，但贝叶斯定理告诉我们：如果某人检测呈阳性，其吸毒的概率只有大约33%，不吸毒的可能性比较大。假阳性高，则检测的结果并不可靠。

2.4　统计学

2.4.1　数据的标准化和归一化

在数据统计领域，通常需要对原始数据做标准化和归一化处理。

数据的标准化（Standardization），通俗地讲，就是把原始数据按照一定的比例进行缩放，使它们落入一个更小的特定区间范围的过程。标准化有多种实现方法，其中常用的是z-score，其表达式如下。

其中，μ代表的是数据样本的均值，σ则是样本的标准差。采用z-score处理后的数据均值为0且标准差为1。

而数据的归一化（Normalization），简单而言是把原始数据按照一定的处理规则，使它们成为落入（0，1）区间的小数。归一化的表达式如下。

因而从缩小数据的角度来看，可以认为归一化和标准化的目标是非常相似的。

归一化的核心作用之一在于消除不同量纲对于最终结果的影响，或者说让不同量纲的变量具备可比性。举个例子来说，假设有两个变量x₁和x₂，其中，x₁的范围是（20 000，200 000），而x₂的范围则是（0，1）。这种情况下，如果把这两个变量绘制出来，会发现基本上就是一条直线。换句话说，x₂的变化范围在x₁的“世界”里显得“微不足道”，因而在参与机器学习的过程中很可能会被毫不留情地“忽略”掉了。归一化就可以解决这类问题，它使得各种变量可以站在同一条起跑线上，从而保证结果的正确性。

与归一化类似，标准化也同样具备去除量纲的作用。不过标准化的另一个特点在于不会改变原始数据的分布，这是它和归一化的一个显著区别。比如前述所举两个变量的例子，经过归一化后它们的图形就不是类似一条直线了，而标准化则不会导致这种转变。使用者应该根据自己的实际诉求来选择更适合自己的实现方式。

2.4.2　标准差

标准差（Standard Deviation，SD）又称为均方差，是反映数据离散程度的一种常用量化形式。它的计算公式并不复杂，如下。

简单来讲，标准差就是各个数据减去它们平均值的平方和，除以数据个数后再开根号得到的。

举个例子来说，有以下两组数据：

数据A｛0，5，7，9，14｝

数据B｛5，6，7，8，9｝

虽然它们的平均值都是7，但是后者从数据分布上来看“更为集中”，因而根据SD的计算公式可知它的标准差更小。

2.4.3　方差和偏差

偏差（Bias）和方差（Variance）是机器学习过程中两个常用的指标，本节对它们做统一的讲解。

（1）偏差。简单而言，偏差就是预测值与真实值之间的差距。

（2）方差。和偏差不同，方差是指预测值的分散程度。

如果把这两个指标形象地描绘出来，如图2-12所示。

图2-12　偏差和方差示意图

假设靶心是真实值，实心圆点是预测值，那么图2-12中的4个子图就代表了高／低情况下的偏差和方差指标的实际表现。例如，左上角各个实心圆点都围绕在靶心周围，因而偏差较小；但同时各个实心圆点又相对分散，因而方差较大。

2.4.4　协方差和协方差矩阵

前面所述的方差可以说是协方差（Covariance）的一种特例——后者可以用于衡量两个变量之间的误差，而方差则只有一个变量。通俗地讲，协方差就是两个变量在变化过程中它们的同步情况——即是属于同向变化还是反向变化？

（1）假如变量A变大，同时变量B变小，就说明它们是反向变化（负相关）的，此时协方差的值为负数。

（2）与上述情况相反，如果变量A变大的同时变量B也变大，说明它们是同向变化（正相关）的，此时协方差的值为正数。

协方差的标准公式如下。

也就是对于X和Y这两个变量，首先求得每一时刻的X值与其均值之差，以及Y值与其均值之差的乘积和（共n个时刻），然后再取平均值。

下面这个范例展示的是两个变量为正相关的情况。可以看到在同一时期，它们之间的变化方向是完全一致的，如图2-13所示。

图2-13　协方差为正相关时的情况

了解了协方差后，它的矩阵形式也就不难理解了。因为协方差只是针对两个变量的，那么当我们面对大于二维的问题时该怎么办呢？此时自然而然地就想到矩阵或许可以给出有效的答案，即

C_n×n=（c_i，j，c_i，j=cov（Dim_i，Dim_j））

譬如针对三维数据集的例子，它的协方差矩阵表达式为

协方差是后续机器学习数据降维理论（如PCA）相关章节的基础，因而建议读者结合起来阅读。

2.5　最优化理论

2.5.1　概述

最优化理论是数学的一个分支，它主要研究的是在满足某些条件限制下，如何达到最优目标的一系列方法。最优化理论的应用范围相当广泛，所涉及的知识面也很宽，并不是简单的一两章就可以涵盖的——因而本节的讲解重点在于和后续章节中强相关的一些最优化基础理论，从而为读者的进一步学习扫清障碍。

根据所选分类角度的不同，可以把最优化问题划分为多种类型。例如，从限制条件的角度，最优化问题通常被分为下面三种类型。

●　没有约束条件的优化问题（Unconstrained Optimization Problem）。

●　等式约束条件下的优化问题（Equality Constraint Optimization Problem）。

●　不等式约束条件下的优化问题（Inequality Constraint Optimization Problem）。

接下来针对上述三种类型分别进行讲解。

（1）没有约束条件的优化问题。

这是最简单的一种最优化问题，即在没有任何限制条件下实现最大值或者最小值（最小值和最大值实际上是可以互相转换的）的求解。

例如，对于求解f（x）=x2函数最小值的问题，可以表示为

从图2-14中不难看出，它的最小值是当x=0时，此时函数取值为0。

图2-14　无限制条件下的极值范例

总的来说，这种情况下的最优解通常可以通过求导数的方式来获得。

对于带有限制条件的最优解问题，也可以再细分为两种情况——即equality和inequality contraint，简单而言就是等式和不等式约束的区别。

（2）等式约束条件下的优化问题。

例如，前面所讲述的f（x）=x2函数，可以增加一个等式约束，这样一来问题就变成了：

其中，“subject to”后面紧跟着的就是限制条件了。

如图2-15所示，在这个限制条件下，当x=2时f（x）可以取得最小值，对应函数值为4。

当然，也可以同时要求多个等式约束，例如：

图2-15　带有一个等式约束的最优解

不过多个限制条件有可能出现无解的情况，例如：

这一点在提出限定条件时需要特别注意。

（3）不等式约束条件下的优化问题。

与等式相对应的是不等式，后者也同样不难理解——它代表的是限定条件为不等式时的情况。

例如，下面是圆形函数的不等式限定条件。

另外，等式约束和不等式约束还可以同时出现，共同作为某个最优解问题的限制条件。举例如下。

针对不同的限定条件，最优解问题的解决策略也会有所差异。

概括来说，有如下几个核心点。

（1）等式限定条件。

拉格朗日乘子法（Lagrange Multiplier）是将等式约束“隐含”到最大值／最小值求解过程中的关键理论基础。

（2）不等式限定条件。

除了拉格朗日乘子法以外，对于不等式约束条件下的最优化问题，还需要借助于另一个理论——KKT（Karush-Kuhn-Tucher）。

在接下来的几节中，将首先基于若干范例来引出这些理论的应用场景，让读者有一个“感性”的认识。然后再尽量“抽丝剥茧”地详细分析隐藏在它们背后的基础原理以及各种公式的推导过程。

2.5.2　函数等高线

在讲解拉格朗日乘子法和KKT之前，首先来补充一些基础知识，即什么是函数等高线，以及它的一些核心应用。

地理学科上的等高线指的是高程海拔相等的相邻各个点所组成的闭合曲线。按照百度百科上的描述，即“把地面上海拔高度相同的点连成的闭合曲线，并垂直投影到一个水平面上，并按比例缩绘在图纸上，就得到等高线。等高线也可以看作不同海拔高度的水平面与实际地面的交线，所以等高线是闭合曲线。在等高线上标注的数字为该等高线的海拔”，如图2-16所示。

图2-16　等高线示例

从地理学上的等高线，还可以引申出函数的等高线。其实并不难理解，比如对于函数f（x₁，x₂），它的等高线可以被表述为如下形式。

f（x₁，x₂）=c

这样一来，如果针对上述公式取微分值，那么可以得到：

另外，业界有多个库函数可以提供非常便捷的API来帮助我们快速绘制出函数的等高线，比如matplotlib。范例代码如下。

输出的效果如图2-17所示。

图2-17　绘制等高线

等高线可以帮助我们从几何角度来分析拉格朗日乘子法及KKT的原理，因而对后续学习有不小的促进作用，建议读者自行编写代码来加深理解。

2.5.3　拉格朗日乘子法

约瑟夫·拉格朗日（Joseph-Louis Lagrange，1736—1813）相信读者都不会陌生，他是法国著名的数学家和物理学家。Lagrange的一生著作颇丰，而且横跨数学、天文学、力学等多个领域（据悉，他的“主业”是数学，而在其他学科上的涉猎则是他为了证明数学威力而从事的“副业”），比如拉格朗日中值定理、微分方程、数论等。

以拉格朗日命名的拉格朗日乘子法，是求解等式约束化问题（Equality Constraint Optimization Problem）最为重要的理论依据之一（求解不等式约束化问题通常还依赖于KKT，2.5.4节中将做详细阐述）。

拉格朗日乘子法虽然是大学时期高等数学课程的一个知识点，不过为了让读者可以“零基础”学习本章内容，还是有必要简单地做一下复习。

接下来引用同济大学出版的《高等数学》一书中的一道习题，来逐步引导出拉格朗日乘子法以及它的相关应用。

问题：求表面积为a2而体积为最大的长方体的体积问题。

假设长方体的三条棱的长分别为x、y和z，那么体积V=xyz。又因为要求面积为a2，所以还有一个附加条件：

2（xy+yz+xz）=a2

换句话说，这个问题可以表述为：

如何求解呢？

针对这个问题其实有一个比较简易的解决方案，即根据约束条件，用x和y来表示z，然后应用到V函数中。具体过程如下。

将上述公式代入前面的V函数，可以得到

这样一来，约束条件自然而然地就被“隐含”到V函数中了，而且通过这种简易的办法还降低了变量个数。遗憾的是，并不是所有条件约束下的极值问题都这么简单直接——我们需要一种更为通用的解决方案，这就是拉格朗日乘子法了。

它的定义如下。

拉格朗日乘子法：要找函数z=f（x，y）在附加条件φ（x，y）=0下的可能极值点，可以先作拉格朗日函数

L（x，y）=f（x，y）+αφ（x，y）

将上述L函数分别针对x和y求一阶偏导数，并使它们为零，同时结合约束条件可得

上述方程组有3个函数，3个变量，因而可以分别解出x、y和α。由此得到的（x，y）就是函数f在附加条件φ（x，y）=0下的可能极值点。

拉格朗日乘子法还可以推广到多变量（≥2）和多约束条件（≥2）的情况下。例如，如果要求解4个变量的函数u

u=f（x，y，z，t）

在两个附加条件

φ（x，y，z，t）=0

ψ（x，y，z，t）=0

下的极值，那么可以先构造出如下拉格朗日函数：

L（x，y，z，t）=f（x，y，z，t）+αφ（x，y，z，t）+μψ（x，y，z，t）

然后通过如下的方程组：

求解得到极值点（x、y、z、t），以及对应的α和µ参数。

还是以前面长方体最大体积的问题为例，应用拉格朗日乘子法来求解的过程如下。

首先构造拉格朗日函数：

分别针对几个参数求偏导数，可得：

由上述方程组，不难求解得到：

所以最大的体积。

另外，还可以从几何意义上来理解拉格朗日乘子法。

如图2-18所示（引用自Wikipedia），包含一个目标函数（最大值／最小值）f（x，y）和一个约束函数g（x，y）=c，或者按照之前的表述方式即是：

不难理解，函数f和g有以下三种可能的关系。

（1）不相交。

（2）相交不相切。

（3）相交且相切。

图2-18　拉格朗日乘子法几何释义

由于需要满足g（x，y）=0的条件，所以寻找的潜在极值只能在这条线上。进一步来讲，上述三种关系最有可能出现极值的是哪一个呢？

不相交的关系首先可以被排除掉，因为这种情况通常意味着无解。

对于相交但不相切的情况，只要沿着g线移动，那么一定可以走到比当时相交点更高或者更低的等高线上。换句话说，只有当g（x，y）和f（x，y）=d产生相切关系时，才有可能出现极值点。这样一来就得到：

▽［f（x，y）+λ（g（x，y）-c）］=0

可以看到上述参与求导的函数就是前面讲解的拉格朗日函数了。

拉格朗日乘子法在机器学习领域应用广泛，比如本书后续章节中将会讲解到的SVM（支持向量机）就是以此为理论基础构建的，建议读者可以结合起来阅读。

2.5.4　拉格朗日对偶性

我们发现不少参考资料在讲解KKT时并没有提及拉格朗日对偶性，或者把这两者完全割裂开来阐述，这可能会让初学者产生或多或少的疑惑——例如，对偶性和KKT到底是什么关系，它们对于约束条件下的最优解都有什么样的贡献，等等。

有鉴于此，本书作者觉得有必要言简意赅地为读者先铺垫一下对偶性的相关知识，以便读者们在学习KKT时既可以“知其然，知其所以然”，同时还能“触类而旁通”。

如果从目标函数和约束条件的角度来分析，那么大致可以有如下几种分类。

（1）线性规划。

当目标函数和约束条件都为线性函数的时候，称之为线性规划。这是相对容易求解的优化问题。

（2）二次规划。

如果目标函数是二次函数，而约束条件为线性函数，那么这种最优化问题通常被称为二次规划。

（3）非线性规划。

如果目标函数和约束条件都是非线性函数，那么这类最优化问题就被称为非线性规划问题。

对于线性规划问题，它们都会有一个与之相对应的对偶问题。那么什么是对偶问题呢？对此Wikipedia上给出了很好的释义，引用如下。

“In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem. However in general the optimal values of the primal and dual problems need not be equal. Their difference is called the duality gap. For convex optimization problems, the duality gap is zero under a constraint qualification condition.”

大意：在数学优化理论中，对偶或对偶原理是从原问题及对偶问题两个角度来看待优化问题的一种指导原则。对偶问题的解提供了原（极）问题的解的下界。不过一般情况下，原问题和对偶问题的最优值不必相等——他们的差异被称为二元差距。对于凸优化问题，在约束限定条件下对偶间隙为零。

上述这段话明确指出了对偶问题的如下几个核心点。

（1）原始问题（Primal Problem）和对偶问题（Dual Problem）。

对偶性（Duality）就像是从两个不同角度来看待同一个问题一样，它们分别被称为原始问题和对偶问题。

（2）对偶性的意义。

通常对偶性的一个重要意义，在于它可以借助更容易获得的对偶问题答案，来间接得到（或者接近）原始问题的答案，从而简化问题的解决方案——甚至有的时候，原始问题是无解的。

（3）对偶间隙（Duality Gap）。

因为对偶问题并不总是可以完全等价于原始问题，所以它们之间可能会存在对偶间隙。最理想的情况是这个Gap=0，此时又称之为强对偶（Strong Duality）；反之如果Gap!=0，那么就是弱对偶（Weak Duality）。

现在读者应该很清楚了，对偶性是降低某些艰深问题的复杂度，从而达到“歼灭”目标的有效手段。

1．最优化问题的标准形式（Optimization Problem in the Standard Form）

最优化问题的标准形式表述需要综合考虑多个等式、不等式约束条件下的最优解，下面所示的是学术界常见的一种表述手段。

minimize f（x）

subject to c_i（x）≤0，i=1，2，3，…，k

h_j（x）=0，j=1，2，3，…，l

针对上述最优化问题，我们定义Lagrangian L：

其中，α_i被称为与第i个不等式限制c_i（x）≤0相关联的拉格朗日乘子法；同理，β_j被称为与第j个等式限制h_j（x）=0相关联的拉格朗日乘子法；α和β的专业术语则是对偶变量（Dual Variables）或者拉格朗日乘子法向量。

2．原始问题：最小-最大化问题（Primal Problem：Min-Max）

拉格朗日对偶的原始问题是在前述标准表述上的一种改进。

我们引入另一个函数θ，它的定义如下。

其中，函数的下标p是Primal的缩写。

由此可以得出一个非常重要的结论，即θ和前面表述的标准问题是等价的——相信读者心里已经有一个大大的问号了，如何得出这样的结论？

证明如下。

（1）当x满足最优化问题的约束条件时。

换句话说，x必须同时满足下面的等式和不等式条件：

c_i（x）≤0，i=1，2，3，…，k

h_j（x）=0，j=1，2，3，…，l

由于c_i（x）≤0且α≥0，所以：

α_ic_i（x）≤0

换句话说，它的最大值只能是0。

另外，因为h_j（x）=0，所以：

β_jh_j（x）=0

这样一来，不难得出：

进一步来说，可以得到：

（2）当x不满足最优化问题的约束条件时。

当x不满足约束条件时，也就是说存在：

任何一个i使得c_i（x）>0或者

任何一个j使得h_j（x）!=0

毫无疑问，在这种情况下：

综上所述，可以得到：

论题得证。

那么费这么大的周折利用原始问题来表述问题的原因是什么呢？其实它的好处是非常明显的，简单来讲就是可以有效地将约束条件“隐藏”进函数中，让我们摆脱原始问题无从下手的“尴尬”。

这种将“无形问题”化解为“有形问题”的形式就是Min-Max，如下。

或者也被称为广义拉格朗日函数的极小极大问题。

为了表述方便，通常用如下的p*来代表原始问题的最优值：

3．对偶问题：最大-最小化问题（Dual Problem：Max-Min）

假定有另外一个θ_D，它的定义如下：

如果针对它求极大值，即：

那么上式就是广义拉格朗日函数的极大极小问题。

当然，也可以按照前面的问题表述方式，把它定义为

和前面的p*类似，我们将对偶问题的最优值表示为d*：

与原始问题和对偶问题相关的有多个定理，例如：

如果原始问题和对偶问题都有最优值，则：

证明如下（参考《统计学习方法》一书中的附录C）。

根据θ_D和θ_p的定义，可以得到：

换句话说就是：

θ_D（α，β）≤θ_p（x）

又因为原始问题和对偶问题都有最优值，所以，

所以，

4．弱对偶（Weak Duality）

从前面的讲解中我们知道，有如下的关系：

d*≤p*

所以说，d*是p*的下边界（Lower Bound，见图2-19）。值得一提的是，这个不等式对于任意的最优化问题（即使它不是凸优化问题）都是成立的。

另外，p*-d*在最优化问题中代表的是针对原始问题的最佳对偶间隙（Optimal Duality Gap of the Original Problem），它具备如下特性。

（1）非负数。由于d*≤p*，所以很自然的有p*-d*≥0。

（2）值越小，表示d*越接近原始问题的最优解。

如果它们不相等，那么就是弱对偶了；而最理想的情况就是它们的差为0的时候。此时就是强对偶关系了，可以参见下面的讲解。

图2-19　下边界

5．强对偶（Strong Duality）

如果满足下面的等式

d*=p*

也就是说对偶间隙是0，那么就说它们具备了强对偶关系。

在最优化理论中，强对偶关系显然不会在所有问题中都成立。不过根据Convex optimization中的论述，如果原始问题满足：

式中的f₀，…，f_m均为凸函数（Convex）的话，那么这种情况下的最优化问题通常（注意：也不是绝对的）就会满足强对偶关系。

那么有没有强对偶一定存在的情况呢？

答案是肯定的，而且还不止一种——比如Slater's condition，或者后续将重点介绍的KKT都是。

Slater's condition是以Morton L. Slater命名的，它是强对偶的一个充分条件（注意：非必要条件）。简单而言，它是指满足如下条件的问题。

∃x₀∈D：f_i（x₀）<0，i=1，…，m; h_i（x₀）=0，i=1，…，p

读者可以注意看下上述f_i（x）与原始问题中的约束条件不太一样，后者使用的是≤，而前者则是＜。换句话说，就是Slater's condition要求更为严格。

接下来再分析一下KKT条件。

2.5.5　KKT

前面几节已经学习了如何利用拉格朗日乘子法来解决等式约束条件下的最优化问题，而且也补充了拉格朗日对偶性等基础知识，接下来就可以进一步学习不等式情况下的最优解问题了。

KKT（Karush-Kuhn-Tucker）就是上述问题的答案——简单来讲，KKT是以三个人的名字组成的几个约束。其中，Harold W. Kuhn和Albert W. Tucker在1951年发表了这个适用于不等式约束条件的约束，所以它又被称为Kuhn-Tucker Conditions。只不过后来人们又发现William Karush其实在更早的1939年就已经在他的硕士论文中阐述了完全一致的观点了，所以就成了现在大家所熟知的Karush-Kuhn-Tucker Conditions（KKT）了。

KKT是在满足一些有规则的条件下，一个非线性规划问题具备最优化解法的必要和充分条件。它也可以被理解为广义的拉格朗日乘子法——换句话说，当不存在不等式约束条件时，那么它和前面所讲述的拉格朗日乘子法就是等价的。

接下来通过几个范例来逐步引导读者学习和理解KKT条件。

1．范例1

那么f（x）函数的等高线如图2-20所示。

图2-20　f（x）的等高线

（引用自KTH DD3364 Course，下同）

从f（x）函数的表达式不难看出，它在没有限定条件情况下的最小值产生于x₁和x₂分别取0时，也就是如图2-20所示的原点中心（此时f为0）。

再来看一下不等式限定函数g（x），如图2-21所示。

图2-21　不等式限定函数g（x）

很显然，这个例子中的g（x）所描述的有效区域（Feasible Region）正好可以覆盖无限定条件下的f函数极小值点，所以说限定条件实际上没有产生有效的约束作用。

2．范例2

此时f（x）函数的等高线如图2-22所示。

图2-22　f（x）的等高线

因为g（x）没有变化，所以还是沿用之前的图例。这样一来，它与f（x）的关系如图2-23所示。

图2-23　g（x）限定条件和f（x）

范例2和范例1的一个重要区别在于，它的g（x）的有效区域并不覆盖无限制条件下的f（x）的最小值。换句话说，f（x）的最小值需要考虑g（x）这个约束条件。

那么这个极值点会发生在什么地方呢？

从上面的等高线图例，结合前面的分析不难得出结论——这个极值点会发生在g（x）=0与f（x）=c相切的地方。

也就是说，满足如下条件：

-∇_xf（x*）=λ∇_xg（x*）

且λ>0，如图2-24所示。

图2-24　范例2的极值点

3．范例3

这个范例中的A是可以调整的，根据A的不同会有如图2-25所示的两种情况。

图2-25　范例3示意图

（引用自MIT公开课材料）

接下来带着对上述几个范例的“感性认识”，再从数学角度分析KKT条件。

首先直接给出KKT的几个条件。

假设最优化问题表述如下。

minimize f（x）

subject to g_i（x）0，i=1，2，3，…，m

h_j（x）=0，1，2，3，…，l

那么KKT给出了x*为最优解的必要条件。特别注意：问题本身还需要满足一些前提条件，KKT才成立，这些前提条件可以参见下面正则条件（Regularity Conditions）中的描述。

1．必要条件（Necessary Conditions）

一共有如下4个必要条件。

（1）平稳性（Stationarity）：

（2）原始可行性（Primal Feasibility）：

（3）对偶可行性（Dual Feasibility）：

（4）互补松弛量（Complementary Slackness）：

µ_ig_i（x*）=0，i=1，…，m

2．正则条件（Regularity Conditions）

正则条件或者约束规范（Constraint Qualifications），是KKT成立的前提条件，如表2-2所示。

表2-2　正则条件

上述的正则条件是怎么来的呢？

为了描述方便，我们对最优化问题做了一下简化，如下。

根据前面的分析，我们知道最优解有以下两种可能性。

（1）可能性1：内生解（Interior Solution）。

在这种可能性下，最优解x*满足g（x*）<0，也就是在范例1和范例3左侧看到的情况。

（2）可能性2：边界解（Boundary Solution）。

在这种可能性下，最优解x*满足g（x*）=0，也就是在范例2和范例3右侧看到的情况。

当处于内生解情况下时，事实上不等式约束问题就退化成无约束条件的最优解问题了。所以此时x*必然满足：

∇f=0且λ=0

而当处于边界解情况下时，不等式约束就变成了等式g（x）=0，换句话说，和之前的拉格朗日乘子法一致了。

根据在范例2中的分析，此时存在λ使得：

∇f=-λ∇g

又因为∇f指向的是可行区域的内部，同时∇g指向的是可行区域的外部，这就意味着λ必然满足：

λ0≥

这样一来根据上述针对内生解和边界解的分析，不难得出如下等式是成立的。

λg（x）=0

最后来小结一下，可以看到KKT几个条件都已经覆盖到了。

（1）平稳性（Stationarity）：

∇f=-λ∇g

（2）原始可行性（Primal Feasibility），即：

g（x）≤0

（3）对偶可行性（Dual Feasibility），即：

λ≥0

（4）互补松弛量（Complementary Slackness），即：

λg（x）=0

当然，为了让读者容易理解，这里举的例子只有一个不等式约束条件，所以KKT条件看上去也比较简单——但万变不离其宗，如果将它们扩展到标准的最优化问题，那么就可以得到前面给出的通用KKT条件了。

另外，上述讨论的只是x*作为最优解的必要条件，相信读者对于它的充分条件也很感兴趣。

3．充分条件

在某些场景下，前述的必要条件也是最优解的充分条件——但更常见的情况是还需要补充一些额外的信息才能构成充分条件，比如业界比较有名的Second Order Sufficient Conditions（SOSC）。

SOSC的简单定义如下：

对于平滑且非线性（smooth，non-linear）的优化问题，假设x*，λ*，μ*是通过KKT找到的局部最小值（Local Minium）。同时，μ*满足严格的互补性，对于满足下式且不等于0的所有s：

以下等式成立：

那么以上就是SOSC充分条件。限于篇幅这里不展开细节讨论，有兴趣的读者可以自行查阅相关资料做进一步分析。

讨论了充分条件和必要条件后，再来结合例子看下如何利用它们来解决实际的最优化问题。为了保持连贯性，仍以本节的范例3来作为分析对象，如下。

subject to x₁+x₂+x₃+x₄=1

x₄≤A

首先定义下面的函数

根据前面的分析，这个范例问题对应的KKT条件为

如何解这些式子呢？

从式（2-1）的求导中不难得出

换句话说就是

根据式（2-2）可以得到

也就是说

所以代入式（2-6）～式（2-9）就可以消去λ了，得到新的式子

同时通过这些新的式子就可以满足式（2-2）的约束了。

再从式（2-3）可以得到

x₄≤A

为了描述方便，把式（2-4）和式（2-5）再重新编下号，得到

这样一来就把最初KKT的几个条件用式（2-10）～式（2-16）来表示了。接下来需要根据A的不同取值来做细化分析。

（1）的情况。

因为，即

同时根据式（2-15）的μ≥0，可知式（2-14）

是成立的——换句话说，满足式（2-15）就隐含了满足式（2-14）。

然后再来分析式（2-16），它的成立有以下两种可能性。

①x₄=A。

根据式（2-10）～式（2-13），不难理解

这样一来

而且在这个场景下，所以x₄=A不成立。

②μ=0。

这样一来就只能是μ=0了。此时可以得出

同时根据J函数定义，可以得到它的最小值也刚好是。

（2）的情况。

当时，由式（2-14）可知

这和式（2-15）是一致的。

另外，式（2-16）的成立同样有两种可能性，即x₄=A或者μ=0。

因为

这样一来

所以x₄=A具备可能性。此时根据式（2-13）可得

换句话说，式（2-16）的两种可能性是等价的。然后其他变量也就不难求解出来了，而且最终结果和时的情况完全一致，即

且。

（3）的情况。

这是以上三种情况中较为复杂的一种。

先从式（2-16）成立的两种可能情况入手，即x₄=A或者μ=0。

①μ=0。

假设μ=0成立，那么

又因为，所以

这显然与式（2-14）矛盾，所以这个情况不可行。

②x₄=A。

如果x₄=A，那么根据式（2-13）

由于，所以

满足式（2-15）。

同时，

满足式（2-14）。

另外，

所以可以得出J的最小值是：

综上所述，J的最优化问题可以概括如下。

值得一提的是，后续章节中将重点分析的SVM就是基于KKT条件来获取最优解的。而且由于SVM的特殊性，它的最优值和KKT条件的解法完全一致。对此学术界在很早以前就已经有论述了，比如Bell实验室的Chrisopher J. C. Burges在其论文“A Tutorial on Support Vector Machines for Pattern Recognition”中有如下的描述：

“...This rather technical regularity assumption holds for all support vector machines, since the constraints are always linear. Furthermore, the problem for SVMs is convex (a convex objective function, with constraints which give a convex feasible region), and for convex problems (if the regularity condition holds), the KKT conditions are necessary and sufficient for w, b, α to be a solution (Fletcher, 1987). Thus solving the SVM problem is equivalent to finding a solution to the KKT conditions.”

大意：因为约束总是线性的，所以这种相当技术性的规律性假设适用于所有支持向量机。此外，支持向量机是凸问题（一个凸目标函数，凸可行区域）。而且对于凸问题（如果规则条件成立），KKT条件是“w，b，α是问题解”的充分必要条件（Fletcher，1987）。因此，解决SVM问题等价于找到KKT条件的解。

有兴趣的读者可以下载并阅读上述论文来做详细分析。

2.6　其他

2.6.1　训练、验证和测试数据集

对于机器学习领域的新人来说，训练集（Training Set）、验证集（Validation Set）和测试集（Testing Set）是比较容易混淆的几个概念。相信很多新手都会有这样的疑惑，为什么需要划分这么多集合，它们有什么区别和联系呢？

统计学教授Brian Ripley曾在其1996年的著作Pattern Recognition and Neural Networks中针对这几种数据集做了定义，引用如下。

●　Training Set: A set of examples used for learning, which is to fit the parameters [i.e., weights] of the classifier.

●　Validation Set: A set of examples used to tune the parameters [i.e., architecture, not weights] of a classifier, for example to choose the number of hidden units in a neural network.

●　Test Set: A set of examples used only to assess the performance [generalization] of a fully specified classifier.

所以简单来说，它们的作用分别如下。

训练集：用于训练分类器模型的参数，比如权重。

验证集：用于确定分类器的网络结构或者控制与分类器复杂度相关的参数，例如，网络层中的隐藏单元数。

测试集：前两者都会影响模型的形成。测试集则用于对最终选择出的最优模型进行性能等方面的评估。

当然，并不是任何时候都需要细化成三种数据集，另外一种常见的组合是训练集加测试集，如图2-26所示。

那么为什么要划分这么多类型呢？其实可以反过来回答这个问题，即如果不划分的话可能会发生什么情况？

图2-26　数据集组合形式

想象一下，如果直接将所有数据集都用于训练，那么只要模型足够复杂就一定可以达到很高的准确率，但这肯定不是最佳结果——因为这样生成的模型已经过份适应了数据集的特征，包括其中的一些“噪声”，所以很容易产生过拟合（参见后续的分析）的问题。

既然需要将原始数据集进行重组（比如划分为训练集和测试集），具体应该怎么操作呢？

1．Hold-out方法

这是最简单的一种重组方式，即将原始数据集直接拆分成两部分，分别作为训练集和测试集，如图2-27所示。

图2-27　Hold-out Method

这种方法的优点是显而易见的——简单高效。但也正是由于这种简单性，使得这样划分出来的数据集对于最终的模型准确率波动很大，或者说相当“随机”，如图2-28所示。

图2-28　Hold-out Method的缺点（图片来源于网络）

图2-28右侧是利用Hold-out Method产生十种不同的训练集和测试集后，得到的机器模型的MSE值（均方误差）。从中可见，要想得到好的模型和参数就有点儿“靠运气”了。所以说，Hold-out Method并不是一个稳定可靠的数据集划分方法。

2．Leave-One-Out Cross Validation（LOO-CV）

为了克服Hold-out Method的缺点，聪明的人们就想到了能不能“平等”地对待所有数据项呢？答案是肯定的，它其实就是交叉验证（Cross Validation，简写为CV）。不过CV也有多种具体类型，限于篇幅本书选择其中两个最常见的版本进行讲解。

和Hold-out中一劳永逸地将数据“一分为二”，然后它们之间就“老死不相往来”的做法不同，LOO-CV是将整个过程分为n轮——每一轮都只把一个数据项作为测试集，而其他剩余数据全部划为训练集，如图2-29所示。

图2-29　LOO-CV示意图

由此可见，LOO-CV的处理过程对于所有数据项理论上都是“公平”的，避免了训练集随机划分带来的波动性。当计算MSE时，是对n轮的结果取平均值，公式如下。

3．K-fold Cross Validation（K-CV）

虽然LOO-CV对于所有数据的公平性比较强，但分为n轮来处理难免带来效率的下降，因而就有了另一种较为折中的办法，即K-CV。

顾名思义，K-CV就是每次不再只考虑一个，而是以k个数据项作为测试集（常见的k取值是5或者10）。它的核心处理步骤如下。

Step1：将整个数据集划分为k份。

Step2：每次从k份中选择不重复的一份作为测试集，剩余部分成为训练集。

Step3：重复k次。

不难理解，前述的LOO-CV其实是k=n时的K-CV特例。它的MSE是将k次的MSE取平均，如下。

很多研究表明，当k=5和10时，K-CV的效果和LOO-CV较相近，如图2-30所示。

图2-30　不同k取值下的K-CV表现

因而可以优先选择5或者10作为k值。

2.6.2　过拟合和欠拟合

机器学习中常见的两个问题，就是过拟合（Overfitting）和欠拟合（Underfitting）。它们对于模型的影响是比较大的，因而我们希望可以尽量消除或者减少这两种情况。

1．什么是过拟合和欠拟合

过拟合或者过度拟合，简而言之就是在拟合数据模型的过程中使用了过多的参数。理论上讲，只要模型足够复杂，那么就可以完美适配所有的训练数据集，甚至包括其中的一些“噪声”。这样和前面学习到的奥卡姆剃刀是相悖的，导致的后果就是模型本身的泛化能力很弱，模型的准确率得不到很好的提升。

下面结合一个例子来讲解。假设要从一组猫的训练数据中学习到如何识别猫，模型已经学习到了如下特征。

●　猫有两只耳朵。

●　猫有一个鼻子。

●　猫有胡须。

●　猫有尾巴。

……

另外，因为训练数据集提供的猫样本恰巧都是（或者大部分都是）白色的，所以学习算法又得出了如下的结论。

●　猫必须是白色的。

很显然，此时就出现了过拟合的情况——猫的颜色并不仅限于白色，因而白色对于这个场景而言是一种“噪声”。换句话说，如果用这个模型来做黑猫的识别，那么必然会出现错误的结果。

与之相对，欠拟合指的是模型没有很好地捕捉到训练数据集中的特征，或者说对变量的考虑不足导致的准确率不够好的情况。仍然以前面识别猫的范例来说，如果只得到如下一些简单的特征：

●　猫有两只耳朵。

●　猫有一个鼻子。

●　猫有尾巴。

那么显然它根本没有正确区分出猫、狗，甚至猴子、老鼠等都具备这些特征的动物。因而可以预想得到，由此得到的模型的准确率肯定不会太好。

读者也可以参考如图2-31所示，直观感受一下过拟合和欠拟合的区别。

图2-31　过拟合和欠拟合对比图（图片来源于网络）

2．判断过拟合和欠拟合的方法

如何判断过拟合和欠拟合呢？

从项目实践经验来看，有如下建议。

1）过拟合

如果模型在训练数据集上的预测结果很好，但在测试数据集上的表现却并不理想，或者说两者有较大差距，那么我们有理由怀疑模型发生了过拟合现象。

2）欠拟合

如果模型不仅在训练数据集上的预测结果不好，而且在测试数据集上的表现也不理想，也就是说两者的表现都很糟糕，那么我们有理由怀疑模型发生了欠拟合现象。

判断过拟合和欠拟合的方法如表2-3所示。

表2-3　判断过拟合和欠拟合的简单办法

2.6.3　奥卡姆的剃刀

奥卡姆的剃刀（Occam's Razor）是一个有意思的问题解决法则，一般将其归功于14世纪的逻辑学家William of Occam（1287—1347）——不过事实上它可以追溯到更早的时间，比如John Duns Scotus（1265—1308），Robert Grosseteste（1175—1253），Maimonides（Moses ben-Maimon，1138—1204），甚至更早之前的Aristotle（公元前384—322）。相信读者对Aristotle（亚里士多德）不会陌生，他在Posterior Analytics中曾经有过如下的论述：

“We may assume the superiority ceteris paribus [other things being equal] of the demonstration which derives from fewer postulates or hypotheses.”

大致意思即：在其他条件均相同的情况下，可以假设“前提（postulates）或者假定（hypotheses）更少的表述（demonstration）的优先级更高”。

目前已有的资料显示，Occam曾在他的《伦巴第人彼得语注》中做出了如下表述：

“Numquam ponenda est pluralitas sine necessitate.”

直译为英文是“Plurality must never be posited without necessity”。

另外，奥卡姆的剃刀还有一个流传更广泛的表述“entia non sunt multiplicanda praeter necessitatem”（其英文直译为“entities must not be multiplied beyond necessity”），而且这个版本并不来源于Occam本人的论著或者文章（注：这里需要从英文的角度，自己体会一下上面两个语句之间的差异，本书不直译为中文的原因在于可能会遗漏其中的“精髓”）。

我们不去细究为什么会产生上述“扑朔迷离”的关系，也不纠结为什么人们将这条原则归功于Occam本人。可以肯定的是，奥卡姆的剃刀原则在人类文明的发展历程中确实发挥了积极的作用。它所透露出的“如无必要，勿增实体”的简单有效原则，就像一把剃刀一样“剪除”了学术或者工业界的很多空洞无物的“累赘”，因而也让它在多个学科领域中得到广泛的传播和应用。例如，在医学领域，医学家会涉及名为诊断简约化原则（Diagnostic Parsimony）的言论，它的核心思想是医生在诊断时应该尽可能给出符合所有症状的最简单的病因。

在过去几百年间，曾经有不少学者试图从逻辑学、经验主义或者概率论等多个方向上来论证奥卡姆的剃刀原则。当然，奥卡姆的剃刀原则本身并不是公理或者理论准则，它更多的是被科学家们作为启发法引用而存在的。另外，并非任何场景下的最简化方案都是最佳的——因为“一刀切”的做法不是这条原则的本意，还需要“具体问题具体分析”。

2.6.4　信息熵

Entropy，即“熵”的概念来源于热力学，它是用于衡量系统混乱程度的重要参数之一。信息熵（Information Entropy）则由著名的信息论之父——C. E. Shannon（香农）提出来，是用于描述信息不确定度的一个概念。由此可见，两个“熵”之间并没有直接的关联（当然，它们也有类似的地方。比如都是为了解决特定体系的量化问题；而且某种程度上它们都致力于面向“无序”或者不确定性的衡量）。

Information Entropy在Wikipedia上的定义是：

“Information entropy is defined as the average amount of information produced by a stochastic source of data. The measure of information entropy associated with each possible data value is the negative logarithm of the probability mass function for the value.”

大意：信息熵定义为随机数据源产生的平均信息量。与每个可能的数据值相关联的信息熵的度量，是该值的概率质量函数的负对数。

从这段话的描述中，可以得到以下关键点。

（1）信息熵和随机变量有关系。

（2）信息熵是“信息”的平均量，所以又被称为“平均自信息量”。

（3）信息熵和概率分布有关系。

（4）信息熵是对不确定性的度量。

不过理论性的概念看上去非常晦涩难懂，因而我们可以举一些生活中的范例来帮助读者更好地理解它的本质是什么。

信息熵既然是衡量“不确定性”的，那么首先就会想到：如何理解“不确定性”呢？另外，信息本身应该是具备某种“价值”的。那么如何衡量信息的价值大小，或者通俗地讲就是“哪些信息量大哪些信息量小”的问题。

如果仔细思考一下，或许可以得出以下几点粗浅想法。

（1）随机结果越多的事件，其不确定性应该越高。

这一点不难理解。比如我现在手上有一个桃子，你告诉我说“这个桃子里面一定有桃核”。地球人都知道桃子里面有桃核，因而对于我来说这就相当于是一句“废话”——换句话说，因为事件本身只有一种可能性，并没有不确定的因素，所以这个信息的价值就很低了。

而如果你告诉我明天会下雨，记得带伞，那么这个信息对我而言就很有价值了——因为天气的变数很多，明天既可能是晴天，也可能下大雨，甚至下冰雹，所以这样的事件具备足够的不确定性。

（2）概率越小的其信息量越高。

反之，概率越高的其信息量越低。当概率达到1时，那么就相当于随机结果值只有一种，这种情况下系统就是确定性的。例如，“某某地区发生百年一遇的大地震”本身是一个小概率事件，因而其信息量比“抛一枚硬币正面朝上”（概率是50%）要高得多。

（3）信息的价值应该体现在它“消除不确定性”的能力上。

我们先解释一下什么是消除不确定性。比如教室里有300个位置，我开始的时候并不知道小明会选择哪个座位；这个时候如果你提供“小明是一个好学生，他喜欢靠前的位置以便更好地听课”，那么显然这个信息降低了“小明会坐在哪个位置”的不确定性，因而它是有价值的；如果又有人进一步提供了“小明已经在第1排第3列的地方占了个座，而且他一般都是坐在这个位置”，那么前述问题的答案基本上已经浮出水面了——换句话说，后者对于不确定性的消除能力更大，因而信息量也就更多。

了解了信息量和信息熵的概念后，接下来可以引出信息熵的标准公式了。在香农的定义中，信息熵H是针对离散随机变量X的如下表述。

其中，b的取值可能是2，或者e，及10。

那么这个公式是否符合前述的几点思考呢？

（1）对于只有一种可能性的系统，也就是i=1的情况，很明显P（x）=1，那么

H（X）=-1×log（1）=0

也就是说，它不存在信息熵，不具备不确定性。

（2）而对于概率值<1的情况，显然：

logP（x）<0，-logP（x）>0

且P（x）值越小，-logP（x）的值越大。

因而也符合前面第2点的设想。

同时公式中是对所有logP（x）求和，意味着可能性越多，其信息熵理论上越大。

所以综合来看，H（x）公式确实可以很好地表述一个系统的不确定性。

另外，信息熵还具备如下一些特性。

（1）Continuity（连续性）。也就是说，概率值的小幅波动对于信息熵的影响应该是微小的。

（2）Symmetry（对称性）。公式中x的排列顺序，不应该对信息熵的值产生影响，表述如下。

Η_n（p₁，p₂，…）=Η_n（p₂，p₁，…）

（3）Maximum（熵的最大值）。信息熵应该在所有可能值同等概率的情况下达到最大值，换句话说，此时不确定性最高（请注意和信息量的大小区分开来）。

最后来计算一个实际范例中的信息熵值。理论上，一枚硬币在抛掷后出现正面和反面的概率都是0.5，即它的信息熵为

可以看到此时是信息熵的极值。

但如果说我们面对的是一枚处理过的硬币，它出现正面和反面的概率分别是0.7/0.3，那么此时的信息熵就变成：

按照前面的分析，因为两种可能性概率不再均等，所以它的不确定性或者说信息熵自然就降下来了。

信息熵的概念在机器学习的多种算法中都有应用，比如随机树中的ID3算法就是基于它来实现的。建议读者可以结合本书后续章节的内容来学习和理解。

2.6.5　IOU

IOU（Intersection-Over-Union）是图像目标识别（Object Detection）中的一个参数，它指的是预测模型得出的目标窗口和人工标记的窗口的交叉率，公式如下。

其中，GroundTruth是指“真实的情况”，DetectionResult则是指模型所给出的预测结果。二者的交集除以它们的并集得到的即是IOU。

如图2-32所示为一个范例。

图2-32　IOU范例

如图2-32所示的是针对“猫”的IOU范例。左下方框代表的是GroundTruth，它完美给出了“猫”在图片中的位置；右上方框代表的是DetectionResult，可以看到预测结果与真实值有一定偏差。

不难理解，最理想的IOU发生在预测窗口和人工标记窗口完全重叠的时候，此时IOU=1。

2.6.6　NMS

NMS是Non-Maximun Suppression的缩写，它的中文通常被直译为“非极大值抑制”。NMS是不少目标识别框架中经常会用到的一个算法（参见本书后续章节中的讲解），不过只从名字读者可能还无法直接理解它的作用。假设有如下一个目标识别场景，如图2-33所示。

图2-33　目标识别场景示例

图2-33中一共有3个方框，它们旁边的数字表示检测到CAT的概率，分别为0.9、0.8和0.7。虽然这几个方框都含有猫的图像，但对于目标识别算法来说，最终的输出结果应该只有唯一的bounding box。这就涉及如何针对多个窗口进行处理，以得到最佳结果的过程——NMS之所以叫作“非极大值抑制”，主要原因在于它处理窗口的方式就是“扬长避短”。

NMS的核心处理逻辑并不复杂，下面以上面这个示例为例说明步骤。

Step1：先选出概率最高的方框，即A。

Step2：选出与上述方框相交的矩形框，即B和C。

Step3：分别计算A与这些方框的IOU值。

Step4：设定一个阈值（比如0.5），将大于阈值的方框丢弃掉（即抑制），只保留小于阈值的方框。

经过上述处理流程，本范例最终只保留下了A方框，从而得到唯一最佳的边界框（Bounding Box）。

2.6.7　Huffman树

Huffman树，经常也被称为最优二叉树，是不少自然语言处理（NLP）模型的理论基础（比如word2vec背后的CBOW和skp-gram模型），因而建议读者把后续的NLP章节和本节结合起来阅读。

最优二叉树简单而言是指带权路径长度最短的树，换句话说，权值大的节点通常离树根节点更近一些；反之则会更远一些。下面的阐述中会首先从范例入手，再从中引出最优二叉树的理论，以便帮助读者深入浅出地理解这一关键算法。

范例：编写程序，判断某人的跳远成绩属于不及格、及格、中等、良好还是优秀，所采用的标准如表2-4所示。

表2-4　判定标准

最简单的实现方式，可能就是直接根据标准的顺序来做判断，类似于：

如果利用二叉树来表述上述这种实现方式，具体过程如图2-34所示。

图2-34　二叉树表述1

从功能实现上来看，这样的处理过程并没有太大的问题。不过读者可以思考一下，从计算效率的角度来衡量，它是最佳方案吗？

假设需要评判的一批跳远成绩的分布，如图2-35所示。

图2-35　成绩的概率分布情况

可以看到，“中等”“良好”等成绩占据了“大半个江山”，但是它们在二叉树中需要经过3次以上的判断才能够得到真正的处理；而处理次数最少的“不及格”只占到8%的份额——换句话说，这样的二叉树结构并不能获得最佳的计算效率。

例如，图2-36所示的二叉树结构明显就比第一种效率要高。

所以我们自然会问：有什么理论基础可以支撑我们得到最优结果吗？

Huffman树应运而生。这其中涉及如下几个基础概念。

1．路径和路径长度

二叉树中两个节点之间经过的分支数目称为它们的路径长度。

图2-36　二叉树表述2

2．带权路径长度

如果给树中的节点分配一个权值，那么该节点到树根的路径长度与其权值之积，称为带权路径长度。

3．二叉树的带权路径长度

一棵有n个带权值叶子节点的二叉树，其带权路径长度计算公式为

其中，w和l分别代表节点的权值和路径长度。

Huffman树或者说最优二叉树指的就是带权路径长度最小的二叉树。

有不少方法都可以构造出最优二叉树，比较经典的是Huffman算法——这个“贪心”算法很简洁，相对而言也比较通俗易懂，因而这里就不做详细阐述了。

另外，最优二叉树还有很多其他影响深远的应用，比如通信和计算机信息处理领域的Huffman编码——因为和后面章节中将讲解到的NLP算法有些关联，这里也一并做下介绍。

假设在数据通信中需要发送一串字符“We need to send out a message”，那么该如何编码呢？可以看到这句话中出现了a、d、e、g、m、n、o等若干个字符，要区分它们并不难，最多只要用到几个bit就可以（比如00000代表a，00001代表d等）——这种编码方式称为等长编码。虽然它也是一种有效的通信解决方案，但从效率上考量显然不是最佳的。这其中的核心原因在于：

（1）所有字符等长编码，会造成不必要的浪费。

（2）未充分考虑字符的出现概率。

我们可以通过二叉树来解决这些问题。

为了保证每一个字符编码都不是其他字符的前缀编码（否则就无法区分开字符了。例如，把a编码为01，把b编码为011，那么当遇到011时就会产生“歧义”），每个字母只能出现在叶子节点上。同时可以引入Huffman算法来充分考虑字符的概率分布。具体而言，字符出现的概率就是它的节点对应的权值大小。根据前面的学习，这样产生的二叉树中频率越小的离树根越远，而频率高的则靠近树根。

由此设计出来的编码方式就是Huffman编码。如图2-37所示就是这个范例的一种编码结果，供读者参考。

图2-37　Huffman编码范例

在图2-37中，圆圈中表示的是字符出现的次数；空心圆圈代表字符（叶子节点），实心圆圈表示的是非叶子节点；叶子节点旁边的是它所表示的字符。另外，细心的读者可能已经发现图2-37中同时遵从“权值小的作为左节点，且在分支上表示为0”的约定。当然，这种约定的具体内容是可以根据实际需要进行调整的。