8.1 个体与集成 def【集成学习】： 通过构建并结合多个学习器来完成学习任务，有时也被称作“多分类器系统”(multi-classifier system)、“基于委员会的学习”(committee-based learning)等。 集成学习的一般结构： 先生成一组“个体学习器”，然后用某种方法把它们结合起来，最后输出结果。 个体学习器： 通常采用现有的方法，如，C4.5决策树算法、BP神经网络算法。 个体学习器的分类： 同质 homogenous：个体学习器采用的方法相同。如，“神经网络集成”中全是神经网络、“决策树集成”中全是决策树。此时，个体学习器对应的算法称为“基学习算法”(base learning algorithm)。 异质 heterogenous：个体学习器采用的方法不同。如，同时包含决策树和神经网络。此时，个体学习器称为“组件学习器”(component learner)或直接称为个体学习器。 集成学习的性能： 集成学习通过结合多个学习器，其泛化性能常优于单个学习器。 弱学习器【常指泛化性能略优于随机猜测的学习器。如，在二分类问题上精度略高于50%的学习器。】的集成效应尤其明显，很多集成学习的理论研究都是针对弱学习器进行的。基学习器有时也被称作弱学习器。 理论上，弱学习器集成可获得较好的泛化性能。但是实际中，为了使用较少的个体学习器、或重用关于常见学习器的经验，人们通常选用较强的学习器、 如何获得比单一学习器更优的泛化性能？ 方法：选用“投票法” voting （少数服从多数）产生。 要求：个体学习器有一定的“准确性”（学习器不能太坏），且“多样性”diversity（学习器要有差异）。 举一个例子🌰： 在二分类任务中，假定三个分类器在三个测试样本上的表现如图8.2所示，其中√表示分类正确，×表示分类错误。集成学习的结果采用“投票法”产生。 在图8.2(a)中，每个分类器都只有66.6%的精度，但集成学习的精度达到100%； 在图8.2(b)中，三个分类器无差别，集成后性能没有提高； 在图8.2©中，每个分类器的精度为33.3%，集成学习的结果更糟。 分析： 考虑二分类问题$y \in {-1, +1}$和真实函数$f$，假定基分类器的错误率为$\epsilon$，即对每个基分类器，有 假设集成通过简单投票法结合$T$个基分类器，若有超过半数的基分类器正确，则集成分类就正确： 假设基分类器的错误率相互独立，则由Hoeffding不等式可知，集成的错误率为 上式表明，随着集成中个体分类器数目T的增大，集成的错误率将指数级下降，最终趋向于零。 基学习器的误差独立性： 1. 基学习器是为了解决同一个问题训练出来的，显然不互相独立； 2. 个体学习器的“准确性”和“多样性”本身存在冲突（一般，准确性高时，增加多样性就会牺牲准确性）； 3. 如何产生并结合“好而不同”的个体学习器，是集成学习研究的核心。 集成学习方法分类： 序列化方法： 个体学习器间存在强依赖关系、必须串行生成。 代表方法：Boosting。 并行化方法： 个体学习器间不存在强依赖关系、可同时生成。 代表方法：Bagging，随机森林 Random Forest。 8.

7.1 贝叶斯决策论 Bayesian decision theory 定义： 贝叶斯决策论是概率框架下实施决策的基本方法。对分类任务来说，在所有相关概率都已知的理想情形下，贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优类别标记。 举例：多分类任务 符号： $N$：类别数目，即$\cal{Y} = {c_1,c_2, \cdots, c_N}$； $λ_{ij}$：将真实标记为$c_j$的样本误分类为$c_i$所产生的损失； 样本$\boldsymbol{x}$上的“条件风险”(conditional risk)：基于后验概率$P(c_i|\boldsymbol{x})$可获得将样本分类为$c_i$所产生的期望损失(expected loss) 决策论中将“期望损失”称为“风险”(risk)。 学习目标： 寻找判定准则$h\, : \, \cal{X} \mapsto \cal{Y}$以最小化总体风险 贝叶斯判定准则Bayes decision rule： 为最小化总体风险，只需为每个样本选择能使条件风险$R(c|\boldsymbol{x})$最小的类别标记，即 符号： $h^\star$：贝叶斯最优分类器(Bayes optimal classifier)； $R(h^\star)$：与$h^\star$对应的总体风险，贝叶斯风险(Bayes risk)； $1-R(h^\star)$：分类器能达到的最好性能（模型精度的理论上限）。 具体来说，若目标是最小化分类错误率： 误判损失$λ_{ij}$： 条件风险： 最小化分类错误率的贝叶斯最优分类器： 即对每个样本$\boldsymbol{x}$，选择能使后验概率$P(c|\boldsymbol{x})$最大的类别标记。 使用贝叶斯判定准则的第一步：获得后验概率$P(c\, | \, \boldsymbol{x})$ 现实任务中常常难以直接获得； 只能基于有限的训练样本集合尽可能准确估计后验概率。 估计后验概率的方法： 判别式模型 discriminative models：给定$\boldsymbol{x}$，通过直接建模$P(c|\boldsymbol{x})$来预测$c$。如，决策树、BP神经网络、支持向量机。 生成式模型 generative models：先对联合概率分布$P(\boldsymbol{x},c)$建模，再由此获得$P(c|\boldsymbol{x})$。考虑 基于贝叶斯定理，$P(c|\boldsymbol{x})$可写为 符号：

6.1 间隔与支持向量 划分： 给定训练样本集$D = {(x_1, y_1), (x_2, y_2), \cdots, (x_m,y_m)}, \, y_i \in {-1,+1}$，分类学习最基本的想法就是在样本集D所在的样本空间中寻找一个划分超平面，能将不同类别的样本划分开。 从图6.1中可以看出，存在多个划分超平面能将两类训练样本分开。那么那种最佳？直观上，我们会选择最中间的那个平面，因为：该划分平面对训练样本局部扰动的“容忍”最性好。（泛化能力最强） 举一个例子，由于训练集的局限性或噪声的因素，训练集外的样本可能比图6.1中的训练样本更接近两个类的分隔界，这将使许多划分超平面对新样本分类错误，而中间的红色超平面受影响最小。换言之，红色划分超平面产生的分类结果是最鲁棒（robust）的，对新样本的泛化能力最强。 用线性方程描述划分超平面 在样本空间中，划分超平面可通过如下线性方程来描述： 符号： 法向量：$\boldsymbol{w}=(w_1;w_2;\cdots,w_d)$，决定超平面的方向 位移项：$b$，决定超平面与原点之间的距离 超平面: 被法向量和位移决定，记做$(\boldsymbol{w}, b)$。 样本空间任意点x到超平面$(\boldsymbol{w}, b)$的距离： 假设超平面$(\boldsymbol{w}, b)$能将训练样本正确分类，即对于$(x_i, y_i) \in D$，若$y_i=+1$，则有$\boldsymbol{w}^T \boldsymbol{x}_i +b > 0$；若$y_i=-1$，则有$\boldsymbol{w}^T \boldsymbol{x}_i +b < 0$。令 1️⃣支持向量 support vector： 如图6.2所示，距离超平面最近的这几个训练样本使(6.3)的等号成立，它们被称作“支持向量”。 2️⃣间隔 margin： 两个异类支持向量到超平面的距离之和： 每个样本点对应一个特征向量。 3️⃣最大间隔( maximum margin )的划分超平面——SVM基本型： 找到满足式(6.3)中约束的参数$\boldsymbol{w}$和$b$，使得$\gamma$最大，即 为了最大化间隔$\gamma$，仅需最大化$||\boldsymbol{w}||^{-1}$，等价于最小化$||\boldsymbol{w}||^2$。于是，上述最优化问题可重写为 这就是支持向量机(Support Vector Machine, SVM)的基本型。 间隔貌似仅与w有关，但事实上b通过约束隐式地影响着w的取值，进而对间隔产生影响。 6.2 对偶问题 dual problem——SVM求解 求解式(6.

5.1 神经元模型 神经网络 neureal networks： 神经网络是由具有适应性的简单单元组成的广泛并行互联网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应 [Kohonen, 1988]。 机器学习中的神经网络指“神经网络学习”，或者说，是机器学习与神经网络这两个学科领域的交叉部分。 M-P神经元模型： 概念： 神经元 neuron：神经网络中最基本的成分是神经元模型，即上述定义中的“简单单元”。在生物神经网络中，每个神经元与其他神经元相连。 阈值 threshold：当神经元兴奋时，就会向相连的神经元发送化学物质，从而改变这些神经元内的电位；如果某神经元的电位超过了一定的“阈值”（在“平静”状态下，神经元也是有电位的，受刺激后其电位会发生变化，可能上升也可能下降），那么它就会被激活，即“兴奋”起来，向其他神经元发送化学物质。 连接 connection：每个神经元接受与其相连神经元传递的信号时，要通过一个个带权重的连接进行传递。 激活函数 activation function： （1）神经元收到的总输入值与其阈值进行比较，再通过“激活函数”处理产生神经元的输出。 （2）最理想的激活函数是“阶跃函数”，它将输入值映射为输出为“0”或“1”；“1”对应于神经元兴奋，“0”对应于神经元抑制。但阶跃函数不连续、不光滑，实际中常用“Sigmoid函数”（亦称挤压函数 squashing function）作为激活函数。 把许多个神经元按照一定层次结构连接起来，就得到了神经网络。 “模拟生物神经网络”是认知科学技术对神经网络所做的一个类比阐释。 例如10个神经元两两连接，则有100个参数；90个连接权和10个阈值。（注意连接是有方向的。每个神经元和其他9个神经元连接，共有9*10=90个连接权；每个神经元接受来自其他9个神经元的信号，其自身有1个阈值，共有1*10个阈值。） 5.2 感知机 perceptron 与多层网络 1️⃣感知机：—— 解决线性可分问题 由两层神经元组成，如图5.3所示，输入层的两个神经元（不是M-P神经元，非功能性神经元，没有激活函数）接受外界输入信号后传递给输出层，输出层是M-P神经元（亦称“阈值逻辑单元” threshold logic unit）。 功能神经元：有激活函数的神经元。 感知机实现逻辑运算“与”、“或”、“非”： 注意到$y=f(\sum_i w_i x_i - \theta)$，假定$f$是图5.2中的阶跃函数，有 感知机学习规则（权重$w_i$及阈值$θ$的学习方法）： 统一权重及阈值：阈值θ可看做一个固定输入为$-1.0$的“哑结点” (dummy node)所对应的连接权重$w_n+1$。 规则：对训练样例$(\boldsymbol{x}, y)$，若当前感知机的输出为$\hat{y}$，则感知机权重将做如下调整： 若感知机对训练样例$(\boldsymbol{x}, y)$预测正确，即$y=\hat{y}$，则感知机不发生变化；否则，根据错误程度进行权重调整。 符号： $\mu \in (0,1)$ ，学习率 learning rate，通常设置为一个小正数，如$0.1$； $x_i$是$\boldsymbol{x}$对应于第$i$个输入神经元的分量。 感知机的特性：

4.1 基本流程 适用任务：分类，以二分类为例 什么是决策树： 基于树形结构来进行决策的一种处理过程； 经过该处理过程后形成的“决策树”，即决策流程。 决策树分解： 先判断什么（父决策），后判断什么（子决策），最后导向什么（最终决策，对应判断结果）； 属性划分：每个“决策问题”都是对样本“属性”的划分； 范围缩小：每个“决策结果”导出的下一步决策都在上一决策的范围内； 举一个🌰，挑西瓜的决策树 如图，一棵决策树包含 一个根结点——第一个决策问题，包含全部样本 若干内部结点——决策问题，包含经根节点划分后的部分样本 若干叶结点——决策结果，包含的部分样本均属于同一类别 从根节点到每个叶节点的路径对应了一个判定测试序列。 原则： 分而治之 divide-and-conquer 基本流程： 说明： 14. 从A中去掉a* 递归返回情形： (1)【Step 03】当前结点包含的样本均属于同一类，无需划分； (2)【Step 06】当前属性集为空(属性都用完了)，或者所有样本在属性集中取值相同，无法划分； (3)【Step 12】当前结点包含的样本集合为空，不能划分。 举🌰：挑西瓜，样本{色泽；根蒂；敲声；甜度；纹理；触感；……) (1) 常见 (2) 属性用完：当前结点的样本均为{色泽=青绿；根蒂=蜷缩；敲声=浊响}，类别为(好,坏,好,好,好,坏)，N(好)>N(坏)，则划分为“好瓜”。 取值相同：当前结点的样本{色泽=青绿；根蒂=(蜷缩, 蜷缩,蜷缩,蜷缩 )| (好,坏,好,好)}，划分属性A为“根蒂”，样本D在A上的属性值均为“蜷缩”，N(好)>N(坏)，所以均划分为“好”。 (3)上一步结点样本{色泽=青绿；根蒂=(蜷缩, 蜷缩,蜷缩)| (好，坏，好)}，原A={色泽，根蒂}，且在上一步已使用“色泽”属性划分，此时用“根蒂”划分，根蒂={硬挺, 蜷缩, 稍蜷} 情形2、3的处理： (2)把当前结点标记为叶结点，类别设定为该结点所含样本最多的类别. (3)把当前结点标记为叶结点，类别设定为其父节点所含类别最多的类别. 情形2、3的区别： (2) 利用当前结点的后验分布. (3) 把父节点的样本分布作为当前结点的先验分布. 4.

3.1 基本形式 给定由$d$个属性描述的样本$\boldsymbol{x}=(x_1,x_2,\cdots,x_d)^{\top}$，其中$x_i$是$\boldsymbol{x}$在第$i$个属性上的取值，线性模型视图习得一个通过属性的线性组合来进行预测的函数，即 $$f(\boldsymbol{x}) = w_1 x_1 + w_2 x_2 + \cdots + w_d x_d +b$$ 用向量形式表示为 $$f(\boldsymbol{x}) = \boldsymbol{w}^{\top} \boldsymbol{x} + \boldsymbol{b}$$ 其中，$\boldsymbol{w} = (w_1,w_2,\cdots, w_d)^{\top}$。模型由$ \boldsymbol{w}$和$ \boldsymbol{b}$确定。 特点： 形式简单，易于建模，但蕴含着机器学习中一些重要的基本思想； 许多功能强大的非线性模型(nonlinear model)可在线性模型的基础上引入层级结构或者高维映射得到； ω直观表示出各属性的重要性，易于解释（有很好的可解释性 comprehensibility）。 例子：若在西瓜问题中学得“f好瓜(x) = 0.2 • x色泽+ 0.5 • x根蒂+ 0.3 • x敲声+ 1”，则意味着可通过综合考虑色泽、根蒂和敲声来判断瓜好不好，其中根蒂最要紧，而敲声比 色泽更重要. 3.2 线性回归 linear regression 目的： 习得一个线性模型尽可能准确的预测实值输出标记，即 $f(\boldsymbol{x}_i) = \boldsymbol{w}^{\top} \boldsymbol{x}_i + \boldsymbol{b}$，使$f(\boldsymbol{x})_i \simeq y_i $ 符号说明： 数据集 $D = {(\boldsymbol{x}_1,y_1), (\boldsymbol{x}_2,y_2), \cdots, (\boldsymbol{x}_m,y_m)}$.

2.1 经验误差与过拟合 基本概念： 错误率 error rate：分类错误的样本数占总样本数的比例。如，在m个样本中有a个样本分类错误，则错误率E=a/m。 精度 accuracy：精度=1-错误率。如，续上，精度=1 - a/m。 误差 error：学习器的实际预测输出与样本真实值之间的差异。 训练误差 training error / 经验误差 empirical error：学习器在训练集上的误差。 泛化误差 generalization error：学习器在新样本（除训练集之外的样本）上的误差。 过拟合 overfitting / 过配：学习器把训练样本学得“太好”了，很可能把训练样本特有的性质当做所有潜在样本具有的一般性质，以致于泛化性能下降。学习器学习能力过于强大。 欠拟合 underfitting / 欠配：学习器对样本的普遍性质尚未学习完全。学习器的学习能力不足。 机器学习的目标： * 学习的泛化误差小，即学习器对新样本的预测效果好。 过拟合是机器学习面临的关键障碍，只能“缓解”不可“避免” 过拟合是机器学习面临的关键障碍，各类学习算法都带有一些针对过拟合的措施；然而必须认识到，过拟合无法彻底避免，我们能做的只是“缓解”，或者说减小其风险。关于这一点，可以大致这样理解：机器学习面临的问题通常是NP难甚至更难，而有效的学习算法必然是在多项式时间内运行完成的，若可彻底避免过拟合，则通过经验误差最小化就能获得最优解，这就意味着我们构造性地证明了“P=NP”；因此，只要相信“P≠NP”，过拟合就不可避免。 2.2 评估方法 在现实任务中，我们往往有多种算法可以选择，甚至对同一个算法，当使用不同的参数配置时，也会产生不同的模型。“选什么样的模型、使用哪种参数配置？”就是机器学习中的“模型选择”( model selection )问题。自然地，理想的解决方案是对不同算法、不同参数配置的模型进行评估，选择泛化误差最小的那个模型。但泛化误差无法直接获取，而经验误差由于过拟合的存在不适合作为评判标准。那么，在现实任务中应该如何选择呢？ “测试误差”近似“泛化误差” 概念： * 测试集 testing set：从样本真实分布中独立同分布采样得到的样本的集合。 注意：测试集应尽量与训练集互斥，即测试集中应尽量不出现训练集中已有的样本。 原因：测试集越是和训练集接近，其测试效果越没有说服力。如，老师上课讲了10道例题，考试时考的就是这10道原封不动的例题，自然没有办法测试出学生的真实水平，反映不出学生学得好不好。训练样本相当于练习题、例题，测试样本相当于考试题。老师都希望学生在学习上能够“举一反三”，就像我们希望训练的模型泛化能力强一样。 测试误差 testing error：训练好的学习器对测试集中样本的预测值与测试集样本的真实值的误差。 但是，实际情况中，我们往往只有一个数据集。若全用来训练学习器，就没有多余的数据用来测试。同时，我们也很难保证在一样的条件下在总体中重新采样，获得新的样本。为了解决既要训练又要测试的问题，我们通常用一定的方法将数据集D划分为训练集S和测试集T，用于训练和测试模型。 2.2.1 留出法 hold-out 方法： 直接将数据集D划分为两个互斥的集合，训练集S和测试集T。 T ∪ S = D 且，T ∩ S = ∅。 举🌰： 以二分类任务为例，假定D包含1000个样本，将其划分为S包含700个样本，T包含300个样本。用S进行训练后，如果模型在T上有90个样本分类错误，那么其错误率为$(90⁄300)×100%=30%$，相应的，精确度为$1-30%=70%$。

1.1 引言——什么是“机器学习”（machine learning） 走在街上看天气、买西瓜的一天 —— 我们根据自己的经验对未知的事情做出了预测或判断 机器学习——将信息输入机器，由机器产生模型，从而对未知的事情做出预判 机器学习是研究“学习算法”的学问 1.2 基本术语 关于数据样本 数据集 data set：一组描述不同个体的各种属性信息的集合 示例 instance / 样本 sample：一个个体、事件、对象。如，一个西瓜，一个机场。 属性 attribute / 特征 feature：反映事件或对象在某方面的表现或者性质的事项。如，色泽，敲声，是否成熟。 属性值 attribute value：属性的取值。如，颜色——红、黄、蓝… 属性空间 attribute space / 样本空间 sample space / 输入空间：属性张成的空间。如，把西瓜的“色泽”“根蒂”“敲声”作为三个坐标轴，则它们张成一个用于描述西瓜的三维空间。 特征向量 feature vector：示例在属性空间中的另一种叫法。续上，在该三维空间中，每个西瓜都可以用一个向量表示，空间中每一个点都对应一个向量坐标，即“特征向量”。 维数 dimensionality：在某数据集中，一个对象的属性的个数。续上上，西瓜数据集的维数 = 3，因为有三个不同的属性。 关于模型习得 学习 learning / 训练 training：从数据中学习，通过某种算法得到模型的过程。如，从西瓜的特征里学习，得到预测西瓜是不是好瓜的模型。 训练数据 training data：输入进机器，用来得到模型的数据。如上，一些西瓜的“色泽”“根蒂”“敲声”属性及其取值。 训练样本 training sample：训练数据中的每一个样本。如上，每一个西瓜都是一个训练样本。 训练集 training set：训练样本组成的集合。如上，一堆西瓜。 假设 hypothesis：学得模型对应了关于数据的某种潜在规律。如，学得的模型可以通过西瓜的某些特征，判断西瓜是不是好瓜。 真相/真实 ground-truth：续上，事物的潜在规律本身。如，好瓜的真实规律。 学习器 learner：习得的模型的另一称呼。 关于预测 ( prediction )模型