1.3 机器学习基本问题

机器学习的基本思想是通过从样本数据中提取所需信息构造一个有效的机器学习模型，并根据所建模型完成分类、回归、聚类等具体的机器学习任务。使用机器学习方法求解具体问题时需要面临一些基本问题。首先，是样本特征的提取问题：样本数据所包含的信息是多种多样的，不同的机器学习模型和任务所需的样本信息通常也各具特色，样本特征的提取问题要解决的是如何从样本数据中获取适当的信息以满足模型构造和完成机器学习任务的需要。其次，是机器学习规则构造的问题：规则是机器学习模型的基本构件或具体表现形式，不同的机器学习方式会采用与之相适应的不同类型的规则。演绎学习使用逻辑规则，归纳学习使用关联规则，统计学习和连接学习使用映射规则，要实现机器学习模型的构造就必须解决机器学习规则的构造问题。最后，是模型评估问题：对于已建的机器学习模型，必须对其进行性能评估以判定是否满足任务需求。因此，机器学习的基本问题主要是特征提取、规则构造和模型评估。本节主要讨论这三个基本问题及解决方法。

1.3.1 特征提取

机器学习中的样本信息由一组表征数据描述，例如，一幅彩色图像可用三个分别表示红、绿、蓝幅度值的矩阵进行表示，这三个矩阵就是这幅彩色图像的表征数据。样本表征数据虽然包含样本的所有信息，但数据量往往较大且存在一定的冗余，不便直接处理。因此，需要对样本的表征数据进行适当处理以获得机器学习和实际问题求解所需要的特定信息，这种处理过程通常称为样本的特征提取。具体地说，特征提取就是对机器学习任务所涉及的原始数据表征进行处理，得到一组具有特定意义的特征数据作为样本数据的优化描述，并以尽可能少的特征数据表达出尽可能多的信息，以方便后续的模型优化和任务求解。

特征提取一般包括如下两个基本步骤：

（1）构造出一组用于对样本数据进行描述的特征，即特征构造；

（2）对构造好的这组特征进行筛选或变换，使得最终的特征集合具有尽可能少的特征数目且包含尽可能多的所需样本信息。

对于任意给定的一个样本，其所有特征值构成的向量称为该样本的特征向量。对于经过特征提取的样本，通常使用特征向量代替表征向量以获得对样本数据的一种优化描述。

可针对不同的机器学习任务构造出相应的特征。例如，在自然语言理解领域通常用词袋特征或词频特征抽象地表达具体的文本特征。词袋特征忽略了文本中词语之间的上下文联系，而只考虑每个词语出现的次数，例如句子“我和哥哥都喜欢看电视剧。”和“哥哥还喜欢看篮球比赛。”可按照其中出现的词语构造如下词典：

{我：1；和：2；哥哥：3；都：4；喜欢看：5；电视剧：6；还：7；篮球比赛：8}

该词典中包含8个词语，每个词语都有唯一的索引，根据该词典可分别将上述两个句子转化为一个8维向量，即

（1，1，1，1，1，1，0，0）；（0，0，1，0，1，0，1，1）

向量中每个分量值表示该分量所对应词语在文本中出现的次数ω。例如，若将上述两句合并为一个文本“我和哥哥都喜欢看电视剧，哥哥还喜欢看篮球比赛。”则该文本对应的词袋特征可表示为（1，1，2，1，2，1，1，1）。

对于任意给定的一个文本，词典中各个词语在该文本中出现的次数及分布情况通常与该文本具体内容有着非常密切的关系，故可根据词袋特征对文本进行分类、聚类等处理。例如，对于如下三段文本。

文本1：“在非洁净的环境下生产的半导体工业产品合格率仅为10%～15%。显示屏生产线厂房项目总建筑面积178万平方米，5个核心厂房均各设一个洁净区，中建一局负责的切割与偏贴厂房洁净区最高洁净度要求为1000级，即要求洁净区域内每立方英尺存在0.5μm的微尘粒子不能超过1000颗。建成后，屏幕生产所用的切割片、涂色和背光板组装等系列设备将安放在此。而屏幕生产的最核心设备曝光机所在的阵列厂房洁净区对洁净等级的要求为100级甚至10级。此外，生产线车间对空气洁净度、温度、湿度、防静电、微振、光照度、噪声等都有严格的参数要求。”

文本2：“不同于其他厂房建设，所有进入洁净室的施工人员都要穿着洁净服，进入前需在更衣室吹掉灰尘，随时随地有专业人员打扫擦拭。洁净区建成后还要擦拭两遍，竣工前经十余项检测通过后才可搬入生产设备。目前，施工区域正在进行第一阶段的分层级地面打磨环氧和水电风管道安装工作。地面如果高低不平，会导致大量灰尘微粒的积压，一个细小的微粒都会直接导致产品报废，特别是洁净区域对平整度的要求近乎苛刻，1平方米内的地面高差最多2毫米。”

文本3：“公民科学素质水平是决定国家整体素质的重要指标，至少10%的公民具备科学素养是该国家成为创新型国家的重要节点。发布于2015年的第九次中国公民科学素质调查结果显示，我国具备科学素质的公民比例达到了6.20%。白希介绍说，改革开放以来，中国公民的科学素质稳步提升，但数据也反映出我国公众科学素质发展中一些不平衡、不充分的情况，下一步将进一步缩小差距，力争尽快赶上世界先进水平。”

可分别对这些文本提取词袋特征，得到如图1-20所示的词袋特征分布图。图中横坐标中每个点对应一个词语，纵坐标表示词语出现的次数，Para1、Para2、Para3分别为文本1、文本2和文本3的词袋特征分布。这里只统计文本中包含具体含义的实词部分，且将相同词根的词语统计为同一个词语，语气词和系动词等不含具体含义的虚词不纳入统计范围。有了图1-20所示的文本词袋特征，就可通过适当的聚类算法进行文本聚类，例如用k-均值聚类算法可得到聚类结果为：文本1和文本2聚为一类，文本3单独作为一类。

计算机视觉和视频图像处理领域常用特征有LBP特征、Canny特征等。LBP特征是一种图像纹理特征，表达的是物体表面具有缓慢或周期性变化的结构组织排列属性。LBP特征算子定义在3×3像素网格窗口中，设某个3×3窗口中像素灰度取值如图1-21中左半部分所示，则该窗口中心像素点的LBP值计算过程如下。

图1-20 三段文本的词袋特征分布

图1-21 LBP二进制编码意图

第一步：将周围像素点的取值与中心像素点的取值大小进行比较，若边缘像素点的取值大于中心像素点，则该点取值为1，否则取值为0，经过这一操作可将周围像素值转化为二进制编码，计算结果如图1-21中右边部分所示。

第二步：从左上角像素开始，按顺时针方向将LBP二进制编码组合成一个八位二进制数并将其转化为一个十进制数，即得到LBP码，例如图1-21窗口中LBP码的转化结果为

10011101₂=157

即该3×3窗口中心像素的LBP码为157。

第三步：重复上述步骤求得图像所有像素的LBP码，并将其作为LBP特征图。图1-22b为图1-22a所示图像的LBP特征图。

图1-22 图像的特征提取

a）原始图像 b）LBP特征图 c）Canny边缘特征

LBP特征是通过计算单个像素与其相邻像素之间的灰度关系得到的，由于相邻像素之间通常存在一定的相关性，故整幅图像各像素的LBP码之间也会存在一定的相关性，这使得LBP特征图能够表现出一定的全局纹理特征。

Canny特征主要表达图像的边缘信息，可用于确定图像中目标的轮廓和位置。由于图像中目标边缘的亮度有一定变化，边缘像素的梯度通常较大，所以Canny特征提取主要是根据梯度值和方向来寻找边缘像素。图1-22c为图1-22a所示图像的Canny边缘特征。

除了上述LBP纹理特征和Canny边缘特征之外，计算机视觉领域还可使用很多其他特征，例如，颜色直方图、Haar特征、SIFT特征等。这些特征都是人们基于对实际问题的分析而人工构造出来的。随着深度学习技术的不断发展，人们逐渐开始尝试让计算机根据任务的实际需求自动进行特征提取，深度卷积神经网络是一种最常用的特征自动提取模型。卷积神经网络是一种以层级连接方式构造的网络模型，该模型从第一个卷积层开始逐层对样本进行特征提取，模型后一层的特征提取基于前一层所提取的特征。图1-23表示卷积神经网络LeNet-5模型的特征提取过程，图中最下方的图片为模型的原始输入，越往上表示由越深的网络层所提取到的较高层特征。

图1-23 卷积神经网络自动提取特征示意图

与人工构造特征相比，机器自动提取的特征所包含的信息往往难以被人们理解，越高层的特征越抽象，但由于计算机自动提取的特征包含更多模型所需信息，因此使用这些自动提取的特征来解决实际问题通常能够得到更好的效果。

在特征构造完成之后，有时还需要对这些特征进行进一步的筛选或融合，剔除可能存在的与实际任务无关的信息或冗余信息。对特征进行筛选的过程称为特征选择。具体而言，对于由构造好的特征构成的特征集合D，特征选择的目标是寻找到D的某个子集D′，使得基于D′所建模型的性能与基于D所建模型的性能相当，并具有较低的模型优化计算量。通常使用子集搜索或相关性评估的方式实现对特征的选择。

子集搜索就是通过搜索特征集合D的所有子集并选择效果最好的子集作为最优特征子集。例如，某机器学习任务的特征集合为：

{Canny边缘特征，颜色直方图，Laplacian边缘特征，LBP纹理特征}

分别用该特征集合的每个子集进行模型训练，如果发现使用

{LBP纹理特征，颜色直方图，Laplacian边缘特征}

这一特征子集训练获得的模型性能最优，则该特征子集便为最优特征子集。

如果特征集合D中的元素个数较多，则子集搜索方法显然不可行。此时可用特征相关性评估的方式来确定最优子集。相关性评估方法的基本思想是使用某个统计量来评估单个特征与样本真实标记之间的相关性，并选择相关性较强的几个特征来构成近似的最优特征子集。

显然，与样本真实标记有较强相关性的特征通常能更好地帮助模型对样本的预测，而与样本真实标记相关性不大的特征通常只能提供较少的参考信息。相关性评估常用的统计量有χ²统计量、信息熵等，下面以χ²统计量为例简要介绍相关性评估的具体做法。

对于任意给定的某个样本特征，相关性评估方法首先假设某一特征与样本的真实标记值无关，然后对该假设进行假设检验，判断该假设是否成立。使用χ²统计量进行假设检验的方式被称为χ²检验。例如，假设H为某一特征与样本的真实标记值无关，则可通过样本数据的实际值A和在假设成立条件下的理论值T计算出如下χ²统计量

在假设H成立的条件下，实际值A和理论值T之间的差别应该较小，即χ²是一个较小的数，故当χ²的值超过某一阈值时，则可以拒绝假设，认为该特征与样本的真实标记值相关。

【例题1.2】对于一个二分类问题，其特征集合为

D={Canny边缘特征，颜色直方图，Laplacian边缘特征，LBP纹理特征}

将D中的各特征离散化为0或1这两种取值状态，特征与样本真实标记y之间的关系分别如表1-1～表1-4所示，试选出包含三个特征的最优特征子集。

表1-1 Canny边缘特征取值情况与真实标记y取值关系表

表1-2 颜色直方图取值情况与真实标记y取值关系表

表1-3 Laplacian边缘特征取值情况与真实标记y取值关系表

表1-4 LBP纹理特征取值情况与真实标记y取值关系表

【解】（1）假设H₀：Canny边缘特征与y不相关。在假设H₀成立的条件下，即Canny边缘特征与y不相关时，理论上y=-1的样本占总样本的比例约为27.89%，则理论上Canny边缘特征与y取值之间的关系应该满足表1-5中的关系，则可算出相应的χ²统计量

表1-5 理论上特征取值与真实标记y取值关系表

假设H₁：颜色直方图与y不相关。在假设H₁成立的条件下，理论上颜色直方图与y取值之间也应该满足表1-5中的关系，由此可算出相应的χ²统计量

假设H₂：Laplacian边缘特征与y不相关。在假设H₂成立的条件下，理论上Laplacian边缘特征与y取值之间也应该满足表1-5中的关系，可算出相应的χ²统计量

假设H₃：LBP纹理特征与y不相关。在假设H₃成立的条件下，理论上LBP纹理特征与y取值之间也应该满足表1-5中的关系，可算出相应的χ²统计量

根据上述统计量值的排序选择三个χ²统计量较小的特征来构成所需的最优特征子集D′，即有：D′={Laplacian边缘特征，颜色直方图，LBP纹理特征}。□

特征选择方式仅仅从原特征集合当中选择了几个特征组成特征子集，却并未改变其中的特征。事实上，除了特征选择之外，还可通过特征变换方式排除或减少特征集合中的特征所包含的无关或冗余信息。例如，通过某种投影映射方式对特征数据进行适当降维等操作，具体可参考有关LDA和PCA算法的相关内容。

1.3.2 规则构造

机器学习模型通常会根据样本的表征或特征信息来实现回归、分类、聚类等问题的求解，因此需要在样本表征或特征信息与模型输出之间建立一定的联系。机器学习模型通常以规则的形式表达这种联系，可将规则看成是机器学习模型的基本构件或具体表现形式。因此，规则构造是建立机器学习模型所必须解决的一个基本问题。不同的机器学习方式通常采用与之相适应的不同类型的规则。这些规则主要有用于演绎学习的逻辑规则、用于归纳学习的关联规则，以及用于统计学习和连接学习的映射规则。

演绎学习主要通过命题逻辑和谓词逻辑的演绎推理进行学习，使用假言三段论、排中律、矛盾律等逻辑规则进行演绎推理。演绎学习的理论基础完备、严谨，学习过程语义清晰、易于理解，但难以处理不确定性信息，对复杂问题的求解会出现难以解决的组合爆炸问题。因此，对于演绎学习，其规则构造的主要目标和难点是建立一套能有效处理不确定性信息的逻辑规则。对模糊性、随机性等不确定信息的处理局限是制约演绎学习发展的主要瓶颈。事实上，机器学习目前使用的基本策略是从样本或样例中学习，归纳学习、统计学习和连接学习已经成为机器学习的主流方式。下面着重分析讨论关联规则和映射规则的构造方法。

所谓关联规则，是指一类已指明条件蕴含关系的规则，故亦称为if-then规则。归纳学习的目标是采用适当方式从若干样例或样本中归纳总结出一组具有较好普适性的关联规则。这组关联规则的普适性主要表现为既符合已知样例或样本的性质，又能给新的示例或样本赋予较为合理的逻辑判断输出。

可用命题逻辑的蕴含式X→Y表示一个具体的关联规则，意为如果命题X成立，则命题Y成立。其中X称为前件或条件，Y称为后件或结论。由于关联规则具有明确的因果蕴含关系，故用关联规则构造的模型通常都具有很好的可解释性，便于分析和理解。

对所有已知样例或样本做出正确推断是对归纳学习所得关联规则的基本要求。也就是说，要求关联规则的正确推断涵盖或覆盖所有训练样本数据。由此设计出的关联规则构造算法称为序列覆盖算法。具体地说，序列覆盖算法递归地归纳出单条关联规则并逐步覆盖训练样本集中的正例，当训练样本集中所有正例均被已归纳的关联规则所覆盖时，此时对应的关联规则集就是所求规则集。然后按适当标准对所求规则进行排序，确定规则使用的优先级。

序列覆盖算法的关联规则的归纳构造主要通过对假设空间的搜索完成。下面结合表1-6所示数据简要介绍基于假设空间的关联规则搜索过程。表1-6是关于小张是否进行运动的相关数据集。若要根据该数据集归纳出小张是否进行户外运动的规则，最容易想到的方法是从最一般的规则前件ϕ开始对假设空间进行遍历搜索，逐步特化规则，最终获得所需规则，具体搜索过程如下：

表1-6 小张户外运动情况记录表

选择关联规则的后件为“是”，则搜索起始位置为ϕ→是，搜索空间如图1-24所示。首先搜索到的规则为“天气=晴朗→是”，则1、2、5号样例的属性取值与其前件一致，但1号样例不符合该规则的推断，故忽略该规则继续向后搜索。当搜索到关联规则“气温=舒适→是”时，2、4号样例的属性取值与其前件一致且均满足该规则的推断，故2、4号样例被这条关联规则所覆盖。将这条规则记录下来并删除2、4号样例，由此完成一条关联规则的归纳构造。递归上述关联规则的归纳构造过程可得两条关联规则，并且它们可以覆盖训练样本集中的所有正例。因此，这两条关联规则即为所求关联规则。最后，根据关联规则所覆盖的样例数目的大小对其进行排序，得到序列覆盖算法的计算结果：

气温=舒适→是

天气=晴朗，气温=不舒适，事务=无→是

假设某天的情况为（天气=阴雨，气温=舒适，事务=有），则可根据上述两条关联规则推断出小张会进行户外运动的结论。

图1-24 关联规则搜索空间

当样本属性个数或属性取值较多时，关联规则的搜索空间可能会变得很大，遍历搜索算法会因计算复杂度大幅上升而变得不可行。此时可用贪心搜索算法求得近似解，即每一次搜索都只朝着当前最优方向进行，从而有效地缩小搜索空间。基于贪心搜索的关联规则学习算法有很多，其中最具代表性的有CN2算法、AQ算法等，在此不再赘述。

在统计学习和连接学习领域，样本数据表征或特征与模型输出之间的关系通常表现为映射规则，即从输入空间到输出空间的映射函数，映射规则的构造过程其实就是确定映射函数的过程，而映射函数确定问题则可转化为求解目标函数最值的优化问题。因此，映射规则的构造主要是通过对目标函数进行优化的方式实现，基本步骤如下：

（1）根据求解问题的具体要求确定机器学习模型的基本类型或映射函数的基本结构；

（2）根据样本数据的具体形式和模型特点确定合适的模型优化标准，如经验风险最小化、结构风险最小化、类内距离最小化、类间距离最大化等；

（3）设计构造模型优化的目标函数；

（4）通过对目标函数进行最值优化获得所需映射函数，完成映射规则构造。

下面结合实例介绍统计学习映射规则构造的具体过程。

【例题1.3】表1-7为某公司部分职员的年龄（岁）和薪资（千元/月）数据，这些职员由公司管理人员和普通员工组成。试根据表中信息大致判断哪些职员为管理人员，哪些职员为普通员工。

表1-7 某公司职员年龄及薪资情况表

【分析】虽然表1-7中的数据并没有标注职位信息，但管理层职员通常年龄相对较大且薪资相对较高，故可用聚类方式求解。聚类的基本思想通过聚类算法将不带标注的样本聚合成适当的簇群。由于聚类的学习对象是不带标注的样本，无法使用基于误差的经验风险最小化或结构风险最小化原则，故聚类算法一般首先使用类内距离最小化原则来构造目标函数，然后对目标函数进行优化以确定映射规则。

【解】使用对表1-7中的样本数据进行聚类的方式求解。令X_i={a_i，e_i}表示表1-7中第i个职员的样本数据，其中a_i表示年龄，e_i表示薪资，由此建立如下聚类映射规则基本结构

其中，C_j表示第j个簇群（j=1，2）；Δ₁和Δ₂是待定的样本数据编号集合。

根据类内距离最小化原则确定如下目标函数

其中，u_j表示第j个簇群的聚类中心；表示u_j的年龄值；表示u_j的薪资值。

D为所有数据点与其所在聚类簇中心的距离之和，可以很好地表示聚类的类内距离。下面使用k-均值聚类算法对目标函数D进行优化，其中k表示簇群个数，本例中k=2。k-均值聚类的基本思路为：首先，任选两个点分别作为两个簇群的初始聚类中心；然后，将剩余数据根据其与聚类中心的距离划分到对应的簇中并根据所聚数据的均值更新聚类中心，递归上述过程直至聚类中心的位置不再变化（聚类中心收敛）即完成对目标函数的优化；最后，根据收敛的聚类中心生成聚类映射规则的具体形式。

令u₁=X₁={27，4.3}和u₂=X₂={47，6.3}，分别计算数据X₃，X₄，…，X₁₈到数据X₁，X₂之间的欧式距离，表1-8中的数据为计算结果。根据表1-8中的计算结果，将每个数据分别划入其与聚类中心距离较小的簇群中，可得如下划分

C₁：X₁，X₃，X₅，X₆，X₈，X₉，X₁₀，X₁₃，X₁₄，X₁₈

C₂：X₂，X₄，X₇，X₁₁，X₁₂，X₁₅，X₁₆，X₁₇

表1-8 第一轮类内距离计算

计算C_j中数据均值，并将该均值作为簇群C_j新的聚类中心，即将聚类中心更新为

u₁={26.8，4.41}， u₂={48.75，6.7125}

计算样本数据与上述聚类中心的距离，计算结果如表1-9所示。

依据表1-9中的计算结果，得到如下划分

C₁：X₁，X₃，X₅，X₆，X₈，X₉，X₁₀，X₁₃，X₁₄，X₁₈

C₂：X₂，X₄，X₇，X₁₁，X₁₂，X₁₅，X₁₆，X₁₇

表1-9 第二轮类内距离计算

此次划分与前次划分相同，聚类中心收敛，故算法结束，获得下标集合

Δ₁={1，3，5，6，8，9，10，13，14，18}； Δ₂={2，4，7，11，12，15，16，17}

由此得到聚类映射规则为

即第1、3、5、6、8、9、10、13、14、18号职员为普通员工，第2、4、7、11、12、15、16、17号职员为管理人员。□

对于统计学习分类任务映射规则的构造，其基本流程与上述聚类任务类似，只是在优化标准和目标函数的设计上有所差异。下面以线性可分的二分类任务为例来简要介绍分类映射规则构造的具体过程。设有训练样本集S={（X₁，y₁），（X₂，y₂），…，（X_n，y_n）}，其中每个样本由t个特征描述，分别为x₁，x₂…，x_t，y_i为样本的标注值且y_i∈Y={+1，-1}，i=1，2，…，n。现对上述分类任务构造映射规则，具体步骤如下。

第一步：确定机器学习模型的基本类型和映射函数的基本结构。使用支持向量机模型实现线性可分的二分类任务。支持向量机通过如下超平面实现样本数据的二分类

其中，w=（w₁，w₂，…，w_t）^T为参数向量；X=（x₁，x₂，…，x_t）^T为特征向量；b为偏置项。支持向量机的分类目标是将分类数据分置超平面的两侧，由此可得分类映射规则的基本形式为

其中，sgn（t）为阶跃函数。

第二步：确定合适的模型优化标准。支持向量机采用硬间隔最大化原则进行学习，即使得两类数据到分离超平面的距离最远。例如，对于图1-25中用实线和虚线表示的两个分离超平面，由于数据点距离实线超平面较远，故实线超平面的硬间隔较大。

图1-25 硬间隔大小示意图

第三步：设计构造模型优化的目标函数。根据硬间隔最大化原则，需要构造一个分离超平面，使得样本点到超平面的距离最大。令表示训练样本集S中任意给定的第i个示例，则不难得到X_i到分离超平面w^TX+b=0的几何间隔d_i为

令d=min{d₁，d₂，…，d_n}，则使得d最大的分离超平面即为所求。由此可得如下目标函数

；

显然，若按比例缩放w^T中的元素和偏置项b，则Y（w^TX+b）的值也会同比例缩放，但这并不会影响优化结果。故可令Y（w^TX+b）=1，则有d=1/‖w^T‖。由此可将约束条件简化为

另外，由于最大化1/‖/w^T‖与最小化‖w^T‖²等价，故可将目标函数转化为

第四步：采用适当优化计算方法对上述目标函数进行优化，求得最优参数w^*T和偏置项b^*，得到所求的分类映射规则f（X）=sgn（w^*TX+b^*），完成映射规则的构造。

连接学习映射规则的构造也遵从上述步骤，不过在选择模型时会选用连接学习模型，即神经网络模型。下面以三维特征向量的二分类问题为例，讨论其映射规则的构造过程。

第一步：确定机器学习模型的基本类型和映射函数的基本结构。选择包含一个隐含层的多层感知机作为分类模型，其网络结构如图1-26所示，其中每个圆圈代表一个神经元。由于特征向量维数为3，故输入层仅含三个输入神经元。

图1-26 一个隐含层的多层感知机

令为第ι层第i个神经元与第ι+1层第k个神经元之间的连接权重，为第ι层第i个神经元的偏置项，各层激活函数均为φ，则对于样本输入X=（x₁，x₂，x₃）^T，该模型两个隐含层神经元的输出h₁和h₂分别为

将上式表示为矩阵形式，则有

其中，w¹为输入层到隐含层的连接权重矩阵；b²为隐含层的偏置向量。同理可得该模型的输出f（X）为

其中，w²为隐含层到输出层的连接权重向量；h为隐含层的输出向量。

第二步：采用结构风险最小化原则模型优化标准，该原则是对经验风险最小化原则的一种改进。模型F在m元训练集G={（X₁，y₁），（X₂，y₂），…，（X_m，y_m）}上的结构风险定义为

其中，L为损失函数；K（F）为模型复杂程度；λ为非负系数。

第三步：根据结构风险最小化原则确定目标函数，使用0-1损失函数和L¹范数惩罚项构造如下目标函数

其中，I（C）在满足条件C时取1，否则取0。

第四步：采用适当优化计算方法对上述目标函数进行优化，解得w¹，w²，b²，的最优值w^*1，w^*2，b^*2，，由此得到所求的分类映射规则

目标函数的优化方法有很多，当目标函数较为简单时，可通过参数估计方式直接估计目标函数最小时所对应的参数值，当目标函数较为复杂而无法直接估计参数时，则可通过迭代逼近方式逐渐优化目标函数并确定参数，这里不再赘述。

1.3.3 模型评估

机器学习的目的是提升模型性能以满足学习任务的需求，对于训练完成的模型需要对其进行性能评估以评判机器学习是否实现了目标或目标实现的程度。因此，对已训练模型进行有效的性能评估是机器学习必须面对和解决的一个基本问题。如前所述，机器学习模型性能的优劣主要取决于其泛化性能，模型评估的基本策略是设法估算出模型的泛化误差并通过泛化误差评估模型泛化性能。直接计算模型泛化误差通常是一件非常困难的事情，故具体的模型评估实施过程中一般使用测试误差近似代替泛化误差，即在测试样本集上计算模型误差并将其作为泛化误差的近似替代。下面具体讨论模型性能评估的基本方法。

要实现对模型的有效评估，首先必须确定能够对模型性能进行有效度量的指标。假设f是一个任意给定的分类模型，T={（X₁，y₁），（X₂，y₂），…，（X_k，y_k）}是用于测试模型f的测试样本集，模型f对样本X_i的输出为。如果T的k个样本中有m个样本的模型输出与其标记值不一致，则可用0-1损失函数算得该模型的测试误差为

即为模型输出值与标记不一致的样本数占测试样本总数的比例，通常亦称为错误率e，即有

其中，I（C）为条件函数，即I（C）的值在满足条件C时取1，否则取0。

正确率a是分类正确的样本数占测试样本总数的比例，即有

正确率与错误率是面向分类任务模型最常用的两种性能度量标准。显然，对于任意一个分类模型，其正确率与错误率之和恒为1。

对于很多分类问题，仅用正确率和错误率对分类模型的评估是不全面的。例如，在计算机辅助诊断应用领域，对于输出空间Y={患有癌症，不患癌症}，假设只有1%的人患有癌症，若直接设置模型输出全部为不患癌症，则可将错误率控制在1%，但是这显然不是一个有效模型。因为该模型的主要目的是尽可能将患有癌症的示例找出来，将患有癌症的示例分类为不患癌症将会产生非常严重的后果。可用查准率和查全率来评价这类模型。

对于任意给定的一个二分类任务，通常会将其中某一类指定为正类，将另外一类指定为负类。令f为完成该二分类任务的分类模型，则可得如下四项基本统计指标：真正例数TP（f）、假正例数FP（f）、真反例数TN（f）和假反例数FN（f）。它们分别表示预测为正类且实际为正类的样例数、预测为正类且实际为负类的样例数、预测为负类且实际为负类的样例数，以及预测为负类且实际为正类的样例数。可根据这些指标算出模型f的查准率P（f）与查全率W（f），具体计算公式如下

根据查全率与查准率计算公式，不难看出P（f）和W（f）的取值有一定制约关系。例如，若想得到尽可能高的查准率P（f），则应尽可能地减少假正例。最简单的办法是将正例概率很高的样本作为预测正例且将其他样本均预测为反例，但这样做会提高假反例的数目，导致查全率W（f）降低。同理，若想提高查全率W（f），则有可能降低查准率P（f）。

利用查全率与查准率对模型进行性能度量时，难免会出现某个模型查全率高但查准率低而另一个模型查全率低但查准率高的情况，此时难以同时使用查全率与查准率指标对这两个模型进行性能对比。为此引入一个名为F₁值的指标解决这个问题。所谓模型f的F₁（f）值，是指该模型查全率与查准率的调和均值，即有

由此可得

F₁（f）值综合了查全率与查准率，当查全率与查准率都较高时，F₁（f）值也较高。因此，如果模型的F₁值越大，则认为该模型的性能越优良。

除了F₁值之外，还可以通过一种名为ROC曲线的函数图像直观表示两个模型的性能对比。对于任意给定的分类模型f，其ROC曲线表示该模型的真正例率TPR（f）和假正例率FPR（f）这两个变量之间的函数关系，其中，TPR（f）表示真正例数TP（f）占测试样本集中全部正例数的比例（即查全率）；FPR（f）表示假正例数FP（f）占测试样本集中全部假例数的比例，即有

显然，如果分类模型的真正例率TPR（f）接近于1且假正例率FPR（f）接近于0，则该模型具有比较好的分类性能。从图形上看，模型ROC曲线越靠近左上方，则该模型的性能就越好。图1-27表示三种不同模型的ROC曲线，由ROC曲线分布特点可知，模型2和模型3的性能优于模型1。模型2和模型3的性能在不同情况下各有优劣，可通过ROC曲线下方面积指标进一步比较它们的平均性能。ROC曲线下方面积指标称为AUC指标。在一般情况下，模型所对应的AUC值越大，则该模型的平均性能就越好。

图1-27 ROC曲线示意图

上述度量标准主要针对分类模型，下面进一步考察回归模型的性能度量标准。令f是任意给定的一个回归模型，T={（X₁，y₁），（X₂，y₂），…，（X_s，y_s）}是用于测试模型f的测试样本集合，是模型f对于样本X_i的输出。若用平方损失函数度量单个样本的回归误差，则可用均方误差（Mean Square Error，MSE）度量模型f关于测试集T的测试误差，即有

另一个常用回归模型的性能度量标准是决定系数。令y为测试样本集T中所有样本标记的均值，则模型f在T上的决定系数R²定义为

决定系数表达式中第二项的分子为模型f关于测试集T的误差平方和，分母则表示训练数据标记值的波动程度，二者相除可消除测试样本标记值的波动对模型性能的影响。对于给定的测试样本集T，如果模型f关于T的误差平方和越小，则其拟合效果就越好。故模型的决定系数越接近于1，则该模型的性能就越好。

有了模型的性能度量指标，就可采用适当方法对模型进行性能评估。模型评估需要使用测试样本集估计模型的泛化误差。如果将参与模型训练的样本作为测试样本用于对模型性能的评价，则会降低对模型泛化性能估计的准确性。因此，测试样本一般不能用于对模型的训练，需将整个数据样本集划分为互斥的训练样本集和测试样本集。基于对样本集的不同划分策略，形成留出法、交叉验证法和自助法等多种模型评估方法。

对于样本数据集D，最简单的划分方法是直接从D中随机划分出部分数据组成训练样本集S，剩下部分作为测试样本集T用于估计模型的泛化误差，这种方法称为留出法。为了保证留出法评估结果的可信度，通常要求训练集和测试集中的样本分布大致相同，从而避免因划分不当带来的偏差对模型评估结果的影响。

划分的随机性显然会给留出法的评估结果带来一定的波动，故仅用一次留出法的评估结果作为模型评估的最终结果是一种比较片面的做法，一般需要多次使用留出法对模型进行评估，并将这些评估结果的均值作为最终的评估结果。在实际的模型训练与测试过程中，训练样本数通常占数据集总样本数的2/3至4/5，其余样本组成测试集。这意味着对于一次性留出法评估，数据集D中有部分样本未能参与到训练过程当中。因此，一次性留出法的评估结果与直接使用D中全部样本进行训练的真实模型性能存在一定差别。显然，训练样本数占全部样本数的比例越高，这种差别就越小。

基于以上分析，K折交叉验证法将绝大多数样本用于训练。K折交叉验证法的基本思路为：首先将数据集D等分为K个子集D_i（i=1，2，…，K），然后依次保留其中一个子集作为测试集T，而将其余K-1个子集合进行合并后作为训练集S。令R_i（i=1，2，…，K）表示第i次的模型评估结果，则各次评估结果R_i的均值就是K折交叉验证法对模型的最终评估结果。

显然，在使用K折交叉验证法进行模型评估的过程中，数据集D的每个样本仅参与了一次测试过程以及K-1次模型训练过程。这意味着每次训练的训练集绝大部分是重叠的，当K值越大时，参与模型训练的样本数越多，得到的模型性能也就越接近于使用数据集D中所有样本进行训练所得到的模型性能，但此时用于测试的样本数较少，测试结果难以真实反映模型的实际的泛化性能。

留一法将每个样本单独作为一个划分，然后采样交叉验证的方式进行模型评估，它是K折交叉验证法的一个特例，也是一种经典的交叉验证法。假设数据集D包含n个样本，留一法则将D进行n等分，依据交叉验证的规则分别进行n次模型训练和测试，每次有n-1个样本参与模型训练、1个样本参与模型测试。最终评估结果亦为各次评估结果的均值。在D中样本数较多的情况下，使用留一法进行模型评估的计算成本较高。

5×2交叉验证法是另一种经典的交叉验证法，该方法使用基数相等的训练样本集和测试样本集进行模型评估，主要包括对样本数据的随机等分和对折这两种操作。所谓随机等分，就是将整个样本数据集合D随机地切分成样本数目相等的两个子集合，并将其中一个作为训练样本集，另外一个作为测试样本集。对折则是将样本数目相等的训练样本集和测试样本集进行性质对换，即将原来的训练样本集变成测试样本集、原来的测试样本集变成训练样本集。5×2交叉验证法对数据集合D进行五次随机等分和对折操作。令为第i次随机等分的第j个样本集合，则第一次随机划分后可得到、这两个样本子集，选择其中之一作为训练集，另一个作为测试集，由此得到了第一对训练集S₁和测试集T₁，对S₁和T₁进行对折操作便可得到第二对训练集S₂和测试集T₂，即有

由以上分析可知，5×2交叉验证法对数据集合D的一次随机等分和对折操作可以得到两对训练集和测试集，进行5次随机等分和对折则可得到10对训练集和测试集，表1-10给出了这10对训练集和测试集的具体产生过程。

表1-10 5×2交叉验证法训练集和测试集

显然，可进行更多次随机等分和对折操作以获得更多的训练集和测试集，但次数过多的随机等分会使样本子集之间具有很强的相关性，无法提供新的有助于模型评估的信息，却徒增模型评估的成本。在数据集D中样本数量较多的情况下，可以进行多次划分，建立多组相关性较小的数据集。因此，留出法和交叉验证法通常比较适用于样本数量较多的情形。

当D中样本数量较少时，可以采用一种名为自助法的方式构造训练集和测试集。自助法主要通过对D中样本进行可重复随机采样的方式构造训练集和测试集。具体地说，假设数据集D中包含n个样本，自助法会对数据集D中的样本进行n次有放回的采样，并将采样得到的样本作为训练样本生成一个含有n个样本的训练样本集S，所有未被得到的样本则作为测试样本构成测试集T。对于D中的任一样本，该样本在自助采样中未被采样的概率为

因此，在数据集D中样本数足够多的情况下，测试样本数约占总样本数的36.8%。值得注意的是，在通过自助法构造的训练集中，样本数量与整个数据集的样本数量相同，但其中可能包含重复样本，因此所获得的训练集的样本分布与整个数据集的样本分布不同，因此，通常只有在样本量较小、难以对数据集进行有效划分时，才使用自助法进行模型评估。

综上所述，在给定数据集D的情况下对机器学习模型进行模型评估，首先需要选择合适的性能度量指标对模型的性能进行度量，然后通过适当的模型评估方法计算出模型所对应的性能度量指标的具体取值，最后通过综合考察机器学习任务的具体特点和性能度量指标值来判定所训练模型是否满足机器学习任务的需求。