第1章
绪论

1.1 基本术语

解答

1. 1）对一个事件或对象的描述称为示例或样本（sample）.若数据使用表格形式表示，每一行为一个样例（example），每行中最后一个元素为标记（label），其他元素构成示例.例如：在表1.1的橘子数据集中，第一行由（大小=大；表皮=光滑；色泽=橙色；弹性=柔软；果蒂=扁平）构成了对编号为1的橘子的描述，该数据集一共有5个示例；在图1.1动物数据集中，每一张图像就是一个示例，该数据集一共有8个示例；在表1.2的电影评分数据集中，第一行（导演=张三；演员=小明；类型=谍战；票房=20；上映日期=2月）是一个示例，该数据集一共有5个示例；在表1.3的信号预测数据集中，第一行（星期=周二；均值=5.0；方差=0.3；天气=晴）是一个示例，该数据集一共有5个示例.

2）反映事件或对象在某方面的表现或性质的事项称为属性或特征（feature）.若数据使用表格形式表示，每一列对应一个属性，不同行在该列下的取值为属性值.在表1.1中，有5个属性，分别为“大小”“表皮”“色泽”“弹性”“果蒂”；在图1.1中，每张图可使用图像的长、宽、通道数进行描述，如果使用RGB格式对图像进行编码，图像可视为像素数据构成的矩阵（张量），其属性是像素的取值，表示对应位置的颜色（红、绿、蓝）强度等信息；在表1.2中，有5个属性，分别为“导演”“演员”“类型”“票房”“上映日期”；在表1.3中，有4个属性，分别为“星期”“均值”“方差”“天气”.

3）在属性上的取值称为属性值.例如：在表1.1中，属性“大小”上的取值可以为“大”或“小”，是离散值，表1.1中的所有属性都是离散的；在图1.1中，由于图像为彩色图像，如果使用RGB编码表示，像素点取值一般在0～255之间，如（224，135，157）形式的RGB三通道数值，因此该属性也可视为离散属性；在表1.2中，属性“导演”上的取值可以为“张三”“李四”“王五”，是离散的取值，属性“上映日期”的取值可以在12个月份中选取，也是离散的，而对属性“票房”的取值，可视为连续的数值；在表1.3中，属性“星期”上的取值可以为“周二”“周三”“周四”，而“均值”“方差”这两个统计量属性的取值为连续值.

2. 若预测（prediction）的目标是离散值，此类学习任务称为“分类”任务；若预测的目标是连续值，此类学习任务称为“回归”任务.表1.1的橘子数据集中，预测结果只有“是”和“否”，标记为离散值，故此任务为分类任务；图1.1的动物数据集中，预测结果为每张图像的离散标记（动物的类别），故此任务为分类任务；表1.2的电影评分数据集中，尽管评分是数值类型，但考虑到评分都是整数，标记仍为离散值，故此任务可视为分类任务；表1.3的信号预测数据集中，信号值为连续数值，故此任务为回归任务.

3. 针对上述数据集训练模型后，得到的模型对从未见过的示例也能进行正确的分类和回归，该能力称为模型的“泛化”能力.例如，所训练的模型在表1.1的数据集上能够正确分类表中的5个示例，当来了一个新的示例（大小=大；表皮=光滑；色泽=绿色；弹性=坚硬；果蒂=扁平）时，模型能够正确预测它是否为甜橘.类似地，对于剩余3个数据集，模型对新图像中的动物、新电影的评分以及新的观测信号值的预测效果，衡量了模型的泛化能力.

包括训练数据和测试数据.

4. 假设全体样本都服从一个分布（distribution），描述了整个样本空间（sample space）的性质，数据集中的每个样本都是独立地从这个分布中采样（sampling）得到的，即称为“独立同分布”.一般而言，可以认为对橘子、动物、电影评分的样本收集是满足独立同分布的.从独立性角度考虑，可能在某些情况下后一天的信号值依赖于前一天的信号值，造成不同的样本之间存在关联，不满足独立假设，此时对新信号值的预测要考虑该信号和历史信号值的依赖关系.从同分布角度考虑，如果观众的品位随时间变化，可能无法假设几年前的电影评分数据和本年度的评分数据服从同一分布.如何应对非独立同分布数据是开放环境下机器学习的重要挑战 ^{[ 1 ]} .

例如，使用教材第7章介绍的朴素贝叶斯分类器训练分类模型，连续或离散属性的建模方式不同.

习题注释 本题考查对机器学习中基本概念的理解，需要注意如何将实际任务转化为机器学习问题.例如，对于给定的数据集，需要判断任务的类型（是分类还是回归）、属性值的类型（是连续还是离散）.在实际应用中，这些定义往往并不那么“严格”.如对于电影评分数据集，可将“评分”视为连续数值，将该任务作为回归任务，也可以将“评分”视为离散数值，将该任务作为分类任务；属性“票房”既可作为连续属性，也可作为离散属性.值得一提的是，如电影评分预测这类类别标记具有顺序的分类问题（排序预测问题），也被称为有序回归（ordinal regression） ^{[ 2-3 ]} .

1.2 假设空间

解答

1. 表1.4中的西瓜共有两个属性，分别是“色泽”和“根蒂”.每个属性分别有2个取值，如“色泽”可取值为“青绿”或“乌黑”.参考教材1.3节中的计算方法，假设空间的大小为

（2+1）×（2+1）+1=10.

2. 版本空间指与训练集（training set）中的正例一致的假设集合.如果数据的假设空间较小，可以将所有可能的假设枚举出来，根据每个训练样例排除掉不符合的假设，剩下的假设集合即为版本空间.这一求解版本空间的方法也被称为“枚举消除”（list-then-eliminate）法 ^{[ 4 ]} .

需要注意在假设空间的计算过程中，“假设”（hypothesis）表示的是从输入属性到输出标记之间的一种关系，对于每一个属性，一个假设可取值为属性值，也可取值为通配符“*”，因此需要在计算中有“+1”的操作.

表1.5中枚举出了共10个假设，其中有3个和训练集吻合.因此，该数据集的版本空间为{（色泽=*；根蒂=蜷缩）；（色泽=青绿；根蒂=*）；（色泽=青绿；根蒂=蜷缩）}.

解答

1. 表1.6中的橘子共有5个属性，分别是“大小”“表皮”“色泽”“弹性”以及“果蒂”.每个属性的取值分别有2、3、4、3、2个.例如，“色泽”属性共有“橙色”“青绿”“绿色”“黄色”4个取值.所以假设空间的大小为

（2+1）×（3+1）×（4+1）×（3+1）×（2+1）+1=721.

同习题1.2，假设空间的计算也需要考虑由通配符构成的假设.

2. 当前数据集假设空间较大，如果仍使用“枚举消除法”，会十分耗时耗力.针对当前的问题，可使用一种“夹逼”的思路，维护两个集合 G 和 S ——其中 G 由通配符假设收缩，逐步排除和负例对应的假设，获得包含正例假设的最松范围（“上界”）；而集合 S 由任意一个正例假设开始，逐步扩张，使得能容纳更多的正例，获得包含正例假设的最紧范围（“下界”）.最终比较 S 和 G 则可得到版本空间.依次遍历各样例，具体步骤如下：

1）编号1：（大小=大）∧（表皮=光滑）∧（色泽=橙色）∧（弹性=柔软）∧（果蒂=扁平）为正例；初始化集合 G 包含通配符假设，初始化集合 S 包含和当前正例一致的假设.

此时 G 最松， S 最紧.

2）编号2：（大小=大）∧（表皮=粗糙）∧（色泽=青绿）∧（弹性=坚硬）∧（果蒂=凸起）为负例，不在集合 S 中，因此，集合 S 不变化，而需要减小 G 的范围，排除负例对应的假设，根据该样例的每个属性值更新集合 G .具体而言， G 当前是由通配符构成的假设，为了尽可能减小 G 的改动，引入基于单一属性的假设，使负例不包含在 G 中.首先考虑“大小”这一属性，由于编号为1和2的两个样例均具有属性值（大小=大），引入依赖于（大小=大）的假设无法排除负例.然后考虑“表皮”属性，由于编号1的正例样本中“表皮”属性取值为“光滑”，而当前负例样本中“表皮”属性取值为“粗糙”，因此可以在 G 中引入新假设，设置其他属性为通配符而仅通过“表皮=光滑”使其能够符合正例而排除负例.类似地，也可针对其他属性进行假设扩展以修改 G ，从而得到如下结果：此时，将编号2的样例代入，未能满足 G 中假设的条件，不会被判断为正例.

3）编号3：（大小=大）∧（表皮=粗糙）∧（色泽=橙色）∧（弹性=略软）∧（果蒂=扁平）为正例.一方面，需要对集合 S 进行合并，在 S 中增加该正例；另一方面，需要对集合 G 进行删减，去除和该正例不一致的假设.例如，当前正例的“表皮=粗糙”和 G 中依赖于“表皮=光滑”的假设不一致，因此删除 G 中对应假设；同时由于当前 S 的假设需要“表皮=光滑”，为囊括该正例，将 S 中的假设对“表皮”属性的取值置为通配符.

4）编号4：（大小=小）∧（表皮=破裂）∧（色泽=绿色）∧（弹性=柔软）∧（果蒂=扁平）为负例，可以根据该样例更新上一步得到的集合 G 中的第二种假设情况.

5）编号5：（大小=大）∧（表皮=光滑）∧（色泽=黄色）∧（弹性=柔软）∧（果蒂=扁平）为正例，据此对 S 和 G 进行更新.

此时所有样例都被遍历过一遍，且集合 G = S .因此，橘子数据集所对应的版本空间为{（大小=大；表皮=*；色泽=*；弹性=*；果蒂=扁平）}.

习题注释 版本空间的求解除了可以针对离散的假设空间外，也适用于连续的假设空间.如图1.2a所示，正负号分别表示正例和负例，规定假设为矩形框（框内为正例，框外为负例），虚线框展示了一个可能的假设（由于框内包含负例，因此该假设不在版本空间中）.本题中对版本空间的求解可归纳为候选消除算法（candidate elimination algorithm） ^{[ 4 ]} .该算法首先寻找一个版本空间 G ，使得不存在其他不在 G 中的假设能够使 G 扩张；同时寻找另一个具体的版本空间 S ，包含最少的满足样例的假设.而 G 和 S 的边界分别为最大泛化边界（maximally general boundary）和最大具体边界（maximally specific boundary），二者构成的区域即为版本空间，如图1.2d所示.算法流程可总结如下，对数据集中的所有样例：

1）初始化集合 G （或最大泛化边界，即最大泛化假设的集合的边界），所有属性上的取值都成立，用通配符“*”表示；

2）初始化集合 S （或最大具体边界，即最大具体假设的集合边界），所有属性上根据第一个正例样本取值；

3）当前样本为正例时，修改集合 S 中的特例假设，使其以最小的改变满足该正例样本，删去集合 G 中不符合该正例样本的泛化假设；

4）当前样本为负例时，修改集合 G 中的泛化假设，使其以最小的改变排除该负例样本，删去集合 S 中符合该负例样本的特例假设；

5）如果集合 G 和 S 中均只含有一个假设：如果它们相同，则得到结果；如果它们不同，则训练样例中存在不一致噪声，继续进行下一个样例的学习.

习题1.2和习题1.3主要考查对假设空间的理解，学习的过程就是根据有限的训练样例，在所有假设组成的空间中进行搜索的过程.可以看出，当假设空间大小不同时，版本空间的计算方式也有所不同.教材第12章对假设空间进行了进一步的讨论.

1.3 归纳偏好

解答

1. 机器学习算法一般都有自身的归纳偏好.如教材第6章介绍的支持向量机方法假设好的分类器应最大化分类间隔（margin）；而深度学习中的代表性方法如卷积神经网络（Convolutional Neural Network，CNN）具有局部性（locality）和空间不变性（spatial invariance）的归纳偏好，循环神经网络具有时序性（sequentiality）和时间不变性（time invariance）等归纳偏好 ^{[ 5 ]} .

深度神经网络的相关介绍见教材5.6节.

最常用的一种归纳偏好莫过于线性模型（linear model）中对分类器 w 的约束.如在岭回归（ridge regression）、支持向量机中，优化目标中包含 ，即在最小化训练集误差的同时，寻找范数最小的分类器 . 范数在一定程度上描述了参数的平滑性，避免分类器的参数取值过大 . 例如，对于两个维数（dimensionality）为4的线性分类器，其各维数的参数取值如表1.7所示：

在支持向量机的推导中， 一项来源于对间隔的最大化.

可以看出，第一个分类器的范数取值较小，各参数也较小，而第二个分类器的参数中存在一些较大的数值，不如第一个分类器平滑，在预测过程中可能造成预测结果出现较大的“抖动”.这一归纳偏好能够被反映在分类器的范数中.

2. 可从以下两个方面考虑设置归纳偏好：

1）若假设 i 能够正确判断的训练样例占训练集全集的比率为 ξ _i ，则选取 ξ _i 最大的假设；

2）若存在多个假设 i ₁ ， i ₂ ，…，其正确判断训练样例的比率相同， ，则由“奥卡姆剃刀”（Occam's razor）原则，选择其中最简单的假设.

习题注释 本题考查对归纳偏好的理解.任何一个有效的机器学习算法必有其归纳偏好，否则它将被假设空间中看似在训练集上“等效”的假设所迷惑，而无法产生确定的学习结果.归纳偏好并没有对错之分，然而好的归纳偏好大多数时候直接决定了算法能否取得好的性能.在训练样本少的场景中归纳偏好的选择尤为重要，在本书11.4节中将进一步探讨这一问题.

习题1.5相关符号的定义请参考教材1.4节.

解答

1. 首先回顾当使用“分类错误率”作为性能度量来评估分类器时NFL的证明方式.令 X 表示样本空间， X 表示训练集，希望学习的真实目标函数为 f .为了衡量泛化能力，需要计算模型针对非训练集的样本的预测能力.在当前算法产生的某个假设 h 下，如果 h （ x ）≠ f （ x ）则表示当前假设与真实目标不一致，计入误差：

其中 P （ x ）表示训练集外数据的分布.例如，数据服从均匀分布，共有5个样本，其中有2个样本在当前假设下预测的结果与真实结果不一致，则误差为2 / 5=0.4.若使用式（1.2）计算，则有0.2×1+0.2×1+0.2×0+0.2×0+0.2×0=0.4，得到同样的结果.

因此，算法 L _a 在给定 f 情况下的“训练集外误差”可表示为

P （ h|X ， L _a ）表示算法 L _a 基于训练集产生某个假设 h 的概率.NFL定理需要计算在所有可能的任务中“训练集外误差”的期望，假设 f 服从均匀分布，即计算

结合教材1.4节的推导， 的计算关键在于计算 在二分类问题（标记为0或1）中，函数空间为 ，即有 个假设.若样本空间 X =2，即有两个样本| x| ₁ 和 x ₂ ，则该函数空间的表示如图1.3所示 . 对于每个样本有两种映射结果，若空间中有| X| 个样本，则共有2 ^|X| =4种映射情况 . 在 f 服从均匀分布的情况下，有 P （ f ₁ ）= P （ f ₂ ）= P （ f ₃ ）= P （ f ₄ ）.假如当前的 h 对 x ₁ 的预测为1，即 h （ x ₁ ）=1，则图1.3中只有 f ₁ 和 f ₂ 与 h 的预测相同，即只有一半的 f 与 h 相同，故 P （ f （ x ）= h （ x ））=1 / 2.

依此类推， 假设所有可能的 f 均匀分布 ，有一半的 f 对 x 的预测与 h （ x ）不一致，故有

综上，可以得到

即NFL定理，算法在所有任务上的 期望性能 与算法本身无关！但是注意到，在进行上述推导时，有一个很重要的前提，即所有可能的目标函数 f 均匀分布.换句话来说，所有“问题”出现的机会相同，或所有问题同等重要.不同的机器学习方法都有它们各自的侧重.当样本有特征有缺失时，可以选用决策树（decision tree）；当需要快速高效并具有可解释性的简单模型时，可以选用线性模型.目前还有很多问题亟待大家去发现和解决，所以进行机器学习算法的研究是很有必要的.

2. 在二分类问题下，需证明损失函数具有如下性质，即任意性能度量 对正确分类和错误分类的得分应该为一个常数 C ，即

对于二分类问题来说，在不指定性能度量 时仅有四种情况，假设 （0，0）= ₁ ， （0，1）= ₂ ， （1，0）= ₃ ， （1，1）= ₄ .其中 ₁ ， ₂ ， ₃ ， ₄ 均为常数.则可得

对于每种情况，均考虑 f （ x ）=3和 f （ x ）=1两种情况.

在二分类的情况下，不考虑代价敏感（cost-sensitive）损失，则应有 ₁ + ₂ = ₃ + ₄ ，故式（1.7）中第二项为0.可得当前情况下 （ h （ x ）， f （ x ））= C .结合这一性质，NFL定理的推导变为

因此算法期望性能在任意性能度量下与当前算法无关.

1.4 矩阵、优化和概率分布

解答

1.证明 考虑到函数 f （ x ）= -x log x 是凹函数，即对于 t ∈[0，1]满足 f （ tx ₁ +（1 -t ） x ₂ ）≥ tf （ x ₁ ）+（1 -t ） f （ x ₂ ），由Jensen不等式（教材式（12.4）），有

为了使用Jensen不等式，在第一个等式中引入了 d ² 因子，使求和过程中权重之和为1.最后的等式应用了双随机矩阵 X 的性质 □

习题注释 本小题考查Jensen不等式的应用.Jensen不等式在机器学习的很多定理中出现，用于针对凸函数或凹函数的结果进行放缩，需要熟练掌握.矩阵统计量 H 的定义与信息熵（information entropy）一致，在第4章决策树习题4.2中将证明类似的性质.

本小题的证明过程是从夹逼的思路入手，通过证明左右均为1从而推导出谱半径为1 .

2.证明 由关于非负矩阵的广义Perron-Frobenius定理可知，对于非负矩阵 X 有

因为 X 是双随机矩阵，因此有 ρ （ X ）=1.同时注意到 X · 1 =1· 1 ，因此1是 X 的特征值 . □

1 表示取值全为1的向量 .

解答

1.证明

其中式（1.14）到式（1.15）的变换利用了正交矩阵的性质，即 VV ^⊥ = I _n ， UU ^⊥ = I _m ，其中 I _n 和 I _m 分别为大小为 n × n 与 m × m 的单位矩阵.而式（1.16）中等号成立的原因是利用了矩阵的迹的性质，即tr（ AB ）=tr（ BA ）.□

2.证明 令

则有

考虑该范数，此时 ‖AB‖ =2， ‖A‖|B‖ =1，不满足自相容条件.因此矩阵范数 不是自相容的矩阵范数.□

3. 要证明矩阵的F范数是自相容的，首先证明Cauchy不等式.

证明 设 a ， b ∈ ⁿ ，下面分两种情况讨论.

如果 a ， b 线性相关，则存在 k ∈ ，满足 a = k b ，将结果代入式（1.21），得到

如果 a ， b 线性无关，则定义 v ∈ ⁿ ，满足 ，因此 v 与 b 正交.将 a 的范数平方展开，由于 v 与 b 正交，有

类似勾股定理.

考虑范数非负性，有

基于向量的Cauchy不等式，下面证明矩阵的F范数是自相容的.

证明 设 A ∈ ^{m × n} ， B ∈ ^{n × p} ，则

在线性无关情况下证明Cauchy不等式时，用到的技巧是Gram-Schmidt正交化，将其应用到列满秩矩阵中，就得到了矩阵的QR分解，这一技巧也被广泛地应用于以最小二乘为目标函数的线性回归（linear regression）问题求解中.

其中不等号利用了上述Cauchy不等式的结论.□

除此以外，矩阵的自相容性也可通过如下方式证明.

证明

其中第二个等号利用了矩阵迹的定义.要证明上述结论，则只需证明

注意到（ A ^⊥ A ）和（ BB ^⊥ ）都是对称半正定矩阵.因此，它们可以被对角化，表示为

其中 U ， V 是正交矩阵，且 Σ _A ， Σ _B 是具有对应矩阵（ A ^⊥ A ）和（ BB ^⊥ ）非负特征值的对角矩阵.再次使用矩阵迹的定义，可以将式（1.27）的左式改写为

具有非负对角值的对角矩阵 D 应当具有以下性质：

1）在任何 D 的正交变换下，得到的矩阵都具有非负对角值 .

性质2的证明可以通过对矩阵迹的计算公式进行展开得到，其中tr（ MD ）的每一项均包含在tr（ M ）·tr（ D ）中.

2）如果 M 是具有非负对角值的方阵，则tr（ MD ）≤tr（ M ）·tr（ D ）.综合以上两个性质，可知

习题注释 易证Cauchy不等式可以推广到矩阵形式.利用类似的方式，本题中Cauchy不等式可推广到如下矩阵的形式（首先定义矩阵Frobenius内积）.

解答

矩阵的秩之间的关系为

证明 根据矩阵的秩的定义，可知rank（ A ）=rank（ A ^⊥ ）.构造两个线性方程组：

利用矩阵乘法的结合律，可以得到 A （ A ^⊥ x ）= 0 . 所以 A ^⊥ x =0 的解均为 AA ^⊥ x = 0 的解 . 将式（1.35）两边同时左乘 x ^⊥ ，可得

AA ^⊥ x = 0 的解均为 A ^⊥ x = 0 的解.因此， AA ^⊥ x = 0 和 A ^⊥ x = 0 具有相同的解空间，rank（ AA ^⊥ ）=rank（ A ^⊥ ）.同理，可以证明rank（ A ^⊥ A ）=rank（ A ），再结合rank（ A ）=rank（ A ^⊥ ），式（1.33）得证.此外，由于rank（ A ）≤min（ m ， d ），因此rank（ A ^⊥ A ）≤min（ m ， d ） . □

本题矩阵的性质在习题10.3对主成分分析（PCA）的讨论中有进一步应用.

解答

1. 随机变量 X 的累积分布函数 F _X （ x ）定义为

依式（1.40）可得

2. 根据式（1.40），有下式成立：

从本题的分析可以看出，即使已知随机变量之间的映射关系，其概率密度分布并不具备相同的映射关系，而需要通过累积分布函数进行推导.

对两边求导，可得

依据本小题的结论，求解概率密度函数时可考虑借助累积分布函数，再进行求导.

因此，随机变量 Y 对应的概率密度函数 f _Y （ y ）为

3.证明

易见式（1.38）和式（1.39）等价.□

由上述结论可知， 使用式（1.39）计算E[ Y ]：

由于式（1.46）第二项涉及了ln y 在 y 为∞时的取值，因此E[ Y ]不存在.

习题注释 概率密度函数的估计是机器学习后续内容中构造概率模型（probabilistic model）的重要一环.本题中对期望性质的证明技巧也可以辅助推导马尔可夫不等式（Markov Inequality），在机器学习理论推导中有广泛应用 ^{[ 7 ]} .对于第3小题的结论，请读者自行验证。

‖ x ‖ _M 定义了在度量 M 下的一种范数，本题证明了随机变量在该空间中范数的上界 .

证明 首先对 进行变换，通过矩阵迹的性质，得到

因此有

由于 是凹函数，式（1.48）利用了Jensen不等式.□

x ^⊥ Mx =tr（ x ^⊥ Mx ）成立是因为 x ^⊥ Mx 是标量，与自身的迹相等 . 再进一步利用tr（ AB ）=tr（ BA ）的性质进行变换.

参考文献

[1]ZHOU Z H.Open-environment machine learning[J].National Science Review, 2022, 9(8):nwac123.

[2]WINSHIP C, MARE R D.Regression models with ordinal variables[J].American Sociological Review, 1984, 49(4):512-525.

[3]GUTIÉRREZ P A, PÉREZ-ORTIZ M, SÁNCHEZ-MONEDERO J, et al.Ordinal regression methods:survey and experimental study[J].IEEE Transactions on Knowledge and Data Engineering, 2016, 28(1):127-146.

[4]MITCHELL T M.Machine learning, international edition[M].New York:McGraw-Hill, 1997.

[5]BATTAGLIA P W, HAMRICK J B, BAPST V, et al.Relational inductive biases, deep learning, and graph networks[J].arXiv preprint, 2018, arXiv:1806.01261.

[6]BRUALDI R A.Some application of doubly stochastic matrices[J].Linear Algebra and its Applications, 1988, 107:77-100.

[7]SHALEV-SHWARTZ S, BEN-DAVID S.Understanding machine learning:from theory to algorithms[M].Cambridge:Cambridge University Press, 2014. sKK8r4iqI0e115TW4/W4gQFaOiZLrcMn1dB/ED/QoXskpPr6Y6H8Lm0SAe5MCjgE