接第二部分 Advanced Learning Algorithms

Machine learning development process

这一部分将学习开发机器学习系统的过程。

(机器学习开发的迭代)Iterative loop of ML development

开发机器学习系统的过程：

首先决定系统的总体架构是什么，这意味着选择机器学习模型以及决定使用什么数据。然后根据这些决定来训练模型。第一次训练一个模型时，几乎永远不会像想要的那样工作，因此需要实施一些诊断，比如查看算法的偏差和方差以及错误分析(error analysis)，然后根据诊断结果做出提高算法性能的决定，比如扩大神经网络、更改正则化参数 λ 、添加更多的训练数据、使用更多的特征或使用更少的特征。然后使用改进后的体系结构再进行这个循环，并且通常需要通过多次迭代，直到获得想要的算法性能。

---

下面看一个“构建垃圾邮件分类器(spam classification)”学习算法的例子：

错误分析(error analysis)

运行诊断以选择下一步如何提高算法性能，诊断方法中偏差和方差是最重要的方法，其次就是错误分析方法。

假设 $m_{cv}=500$(有500个交叉验证样例)，学习算法错误分类了500个交叉验证样例中的100个，错误分析(error analysis)过程是指手动查看这100个样例，并试图深入了解算法出错的地方。

错误分析(error analysis)常用的方法是从交叉验证集中找到一组错误分类的样例，并尝试将它们分组为共同的主题或共同的属性或共同的特征。

比如注意到很多被错误分类的垃圾邮件是药品销售，对错误分类样例进行分组，有21个药物垃圾邮件。有3个是“故意拼写错误”。有7个异常邮件路径。18个“窃取密码”的钓鱼邮件。有5个嵌入图片的垃圾邮件(嵌入图片的垃圾邮件使得学习算法更难进行分类)。【这些分组类别可以重叠，比如一封邮件可以属于多个分组，既属于药物垃圾邮件，又属于“故意拼写错误”，钓鱼邮件】

最终这些分组中数量最多的似乎是个大问题，因此应该优先解决大问题，这能使学习算法的性能显著提升。

这里仅有100个错误分类样例，如果有更多比如有1000个错误分类样例，这时如果没有时间查看所有错误分类样例，可以随机抽取大约100个错误分类样例。

在这个例子中错误分类样例中“药物垃圾邮件”是最多的，因此优先解决这个问题能给学习算法性能带来显著提升。此时如果要添加更多数据，这时应该添加更多的药物垃圾邮件数据，以便学习算法更好地识别药物垃圾邮件，而不是添加全部类型的垃圾邮件数据。或者添加一些与药物相关的特征，以便学习算法更好地识别药物垃圾邮件。

解决了“药物垃圾邮件”再来解决错误分类样例中第二多的钓鱼邮件。此时如果要添加更多数据，这时应该添加更多的钓鱼垃圾邮件数据，以便学习算法更好地识别钓鱼垃圾邮件，而不是添加全部类型的垃圾邮件数据。或者添加一些与钓鱼链接URL相关的特征，以便学习算法更好地识别钓鱼垃圾邮件。

---

训练“垃圾邮件分类器”模型时，第一次训练完模型并没有像想象中那样工作，可能会有多种想法提高学习算法的性能：

通过上面的例子可知，偏差和方差诊断以及错误分析对于决定下一步对模型进行哪些更改带来的提升更大非常有帮助。

错误分析(error analysis)的局限性是容易解决人类擅长的问题，因为需要手动的查看错误分类样例的内容并进行分组。而对于人类不擅长的问题，错误分析会更难，比如试图预测某人会点击网站上哪些广告，人类很难预测某人会点击哪些广告，因此对于这个例子来说，错误分析会比较难。

添加数据(Adding data)

在「添加数据」这一部分将学习一些技巧，用于添加数据或收集更多数据，有时也能为学习算法创建更多数据。

在训练机器学习算法时，总是希望有更多的训练数据，因此想获取所有内容的更多数据。但是尝试获取所有类型的更多数据可能既缓慢又昂贵，相反，添加数据的另一种方法是只添加最有可能提升学习算法性能的数据，上一部分的「错误分析」可以帮助分析哪些类型的数据是最有可能提升算法性能的(优先解决大问题)。【当然如果有方法能添加更多的所有类型的数据，那更好】

---

针对数据集为图像、音频的，有一种技术可以显著增加这种训练集大小，这种技术称为数据增强(data augmentation)：用现有的训练样例创建新的训练样例。

如果你创建的学习算法要识别 A-Z 的字母图像。从已有训练集中选择一张图片A，通过旋转、放大、缩小、改变对比度、左右翻转等方法扭曲图像，这些扭曲后的图像仍然是字母A，而不是其他字母，从而获得新的训练样例。

数据增强(data augmentation)是通过扭曲现有图像生成新的训练样例，因此这种方法也可以提高算法的准确性，使算法能应对不同情况。

还可以在字母A上放一个网格，通过引入网格的随机扭曲，可以得到更丰富的字母A示例库。并将其添加到训练集中提供给学习算法，使学习算法更稳健。

---

这种数据增强方法也适用于“语音识别”。

训练集中有一段原始音频，可以将原始音频分别与不同的噪音背景进行合成从而生成新的训练示例，同样这种方法不仅可以提供更多的训练样例，也能使学习算法更稳健，在不同情况下都能准确识别。

---

数据增强并不是盲目的对已有训练样例进行扭曲，对已有训练样例所做的扭曲应该是测试集中存在的类型(或者说数据增强得到的东西应该与测试集中的东西非常相似)，这样才能增加学习算法的稳健性。比如对字母A进行扭曲可以通过旋转、放大、缩小、改变对比度、左右翻转等方法，因为这些扭曲后的图像在测试集中存在(或者说在生活中是经常见到的)，而如果对字母A进行上下翻转进行扭曲，这显然有些不合理，因为倒着的字母A在测试集中不存在(或者说在生活中极少见到倒着写的字母A)，因此这种扭曲是没有意义的。

---

数据合成(data synthesis)，可以从头开始构建全新的训练样例(不是修改已有训练样例，而是创建全新样例)。

以照片OCR(OCR，optical character recognition。识别图片中的文本)为例：

照片OCR任务的一个步骤是看这些小图像，并识别中间的字母。为此任务创建人工数据的一种方法是在计算机的文本编辑器中使用不同的字体编写随机文本，使用不同颜色、不同对比度的字体截屏，就可以得到右边那样的合成数据。(左边是拍摄的真实照片中提取的数据；右边是人工合成的数据)。【编写代码给特定应用程序进行数据合成可能需要大量工作，但这样可以为应用程序生成大量数据，并提高学习算法的性能】

数据合成(data synthesis)方法最有可能应用于计算机视觉，而较少应用于其他程序。

---

机器学习系统或AI系统=code(algorithm/model)+data。在过去，大多数研究人员会固定数据集，专注研究算法或模型。而今天，我们可以使用线性回归、逻辑回归、神经网络、决策树等强大算法或模型，这些算法已经非常好并且适用于许多应用程序；因此，专注于设计算法使用的数据会更有成效。

迁移学习：使用其他任务中的数据(Transfer learning:using data from a different task)

有一些应用程序没有那么多数据，并且很难获得更多数据。迁移学习(transfer learning)可以从几乎不相关的任务中获取数据用于该应用程序，从而提升算法性能。

神经网络有时可以使用不同任务的数据让算法做得更好，但这并不适用于所有事情，但当它适用时，它会非常强大。

对于没有那么多数据的应用程序，迁移学习(transfer learning)是一种很棒的技术，可以让你使用来自不同任务的数据来帮助你的应用程序。

迁移学习(transfer learning)工作原理：

假设要进行“手写数字识别0-9”，但没有那么多手写数字的训练数据。
假设你找到了一个非常大的数据集，其中包含一百万张图片，拥有猫、狗、汽车、人等一千个类别。然后可以在这个一百万张图片的大型数据集上训练神经网络，将图像 X 作为输入，并学习识别这1000个类别。(假设在该大型数据集上训练的神经网络有5层)
要应用迁移学习，那就需要复制训练好的神经网络，所有的隐藏层(包括隐藏层参数)都一样，但对于输出层需要进行修改。原神经网络输出层有1000个神经元(输出1000个类别)，在“手写数字识别0-9”中要将输出层该为10个神经元(输出10个类别)。输出层的参数不能复制过来，因为输出层已经修改了(原输出层有1000个神经元，现输出层仅有10个神经元)，需要从头开始训练输出层参数。
在迁移学习中要复制所有隐藏层及其参数，以这些参数为起点(初始值)运行优化算法如梯度下降或Adam优化算法。
训练复制后的神经网络有两种方式：

1. 只训练输出层参数。
2. 训练神经网络中的所有参数(隐藏层和输出层)，但隐藏层参数的初始化值是复制过来的参数。

如果有一个非常小的训练集，那么方式1会好些；如果有一个稍微大点的训练集，那么方式2会好些。

以上举例的方法就是迁移学习，因为是通过学习识别猫、狗、人等其他类别，希望它已经为处理图像输入的早期层学习了一些合理的参数集。然后通过将这些参数转移到新的神经网络，新的神经网络从一个更好的地方开始训练参数，这样就可以学习的更好更快。

迁移学习的步骤：

1. 首先在大型数据集上训练
2. 然后在较小的数据集上进一步调整参数

第1步称为监督预训练(supervised pre-training)：在非常大的数据集(如一百万张完全不相关任务的图像)上训练神经网络。
第2步称为微调(fine tuning)：获取预训练中的参数作为初始值，然后进一步运行梯度下降或Adam优化算法以微调权重以适应目标数据集。

迁移学习的好处是你并不需要进行监督预训练，对于很多神经网络，已经有研究人员在大型数据集上训练了神经网络(预训练模型)并将其发布在Internet上供任何人下载和使用。只需要下载这些预训练的神经网络，然后将输出层替换为自己的输出层并只训练输出层参数或训练神经网络中的所有参数(隐藏层和输出层)即可。只需要在预训练神经网络上进行微调就可以快速得到一个在你的任务上表现良好的神经网络。

---

为什么迁移学习有用？(怎么可能通过识别猫、狗、汽车和人等类别获得的参数来帮助你“识别手写数字”这样不同的东西？)

简单解释一下：如果训练神经网络来检测图像中的不同对象，那么神经网络的第一层可能会学习检测图像中的边缘(edges)(认为是图像中用于检测边缘的低级特征)。然后神经网络的下一层学习将边缘组合在一起以检测角点(corners)，神经网络的下一层可能已经学会检测一些更复杂的东西比如通用形状。这样通过学习检测大量不同的图像，神经网络学习了检测非常通用的特征：边缘、角落、基本形状，这对于其他计算机视觉任务很有用，比如“手写数字识别”。

注意：
使用迁移学习时的预训练模型的输入类型必须与你的任务输入类型是一样的。(如果你的任务是计算机视觉任务，输入的是图像，那么你需要的是在图像数据上进行预训练的神经网络。如果你的任务是“语音识别系统”，输入的是音频，那么你需要的是在音频数据上进行预训练的神经网络。其他类型的任务亦是如此)

---

迁移学习的两个步骤：

1. 下载预训练神经网络，其参数已在与你的任务具有相同输入类型的大型数据集上进行了预训练。
2. 根据你自己的数据进一步训练/微调。
   
   如果你听过GPT-3、BERT或在ImageNet上预训练的神经网络，这些都是在非常大型的文本数据集或图像数据集上进行预训练，然后可以在其他应用程序中对其进行微调。(这些都是预训练的成功应用)

迁移学习实际上就是使用预训练模型，这经常使用。

机器学习项目的完整周期(full cycle of a machine learning project)

构建机器学习系统时，训练模型只是难题的一部分。

以“语音识别”为例说明一个机器学习项目的全周期：

机器学习的第一步是确定项目范围(决定项目是什么以及想做什么)。第二步收集数据。第三步训练模型，并根据错误分析(error analysis)迭代改进模型；在开始训练模型并进行错误分析或偏差、方差诊断后可能会返回以收集更多数据，或者只是收集更多特定类型的数据以提高学习算法的性能。绕着这个循环几次，直到模型足够好，然后在生产环境中部署。第四步部署，之后还需要接着监控系统的性能并维护系统以防止性能变差。部署后发现并没有像想象中那样工作，可以回去改进训练模型，也可以回去收集更多的数据。(如果你有权使用生产环境中产生的数据，那么就可以将其投入到训练集中改进模型，从而不断提高系统性能)

---

下面讨论在生产环境中部署的细节：
在训练了一个机器学习模型后，部署该模型的一种常见方法是在服务器中采用你的机器学习模型，将该服务器称为推理服务器(inference server)，调用你的机器学习模型进行预测。然后，你的团队实现了一个移动应用程序(Mobile app)，比如社交应用程序，那么当用户与应用程序交谈时，应用程序可以进行API调用(API call)，将输入特征送到推理服务器，推理服务器根据输入特征进行推理，将预测值送回应用程序。这是应用程序调用API和推理服务器工作的常用方法。

为了实现应用程序调用API将输入特征送入推理服务器，推理服务器再将预测值返回应用程序需要软件工程(software engineering)编写代码：
根据应用程序为少数用户服务器还是为百万用户服务(规模)来编写代码以保证可靠和有效。在用户同意的情况下记录输入特征x与预测值 $\hat{y}$。这些记录对监控系统有帮助。(比如在2024年诺贝尔化学奖刚公布时，我询问GPT 2024诺贝尔化学奖得主，它给我的反馈是2024年诺贝尔化学奖还未公布。当我把2024年诺贝尔化学奖得主名单及其论文发给GPT后它给出了正确答案。这就是模型的数据库还未更新，监控系统能够弄清楚数据何时发生变化以及算法何时变得不那么准确，然后重新训练模型，执行模型更新以用新模型替换旧模型)

在机器学习中有一个不断发展得领域：MLOps(machine learning operations，机器学习操作)，指如何系统地构建、部署和维护机器学习系统，用以确保机器学习模型可靠、可拓展、对模型进行更新。

公平、偏见与伦理(fairness,bias and ethics)

现在机器学习正在影响数以亿计的人，如果你正在构建一个影响人们的机器学习系统，你需要确保你的系统相当公平、没有偏见、并遵守道德。

先来看一些出现“偏见”的机器学习系统：

1. hiring tool that discriminates against women(歧视女性的招聘工具)。
2. facial recognition system matching dark skinned individuals to criminal mugshots(面部识别系统更容易将深色皮肤的人与罪犯的面部照片相匹配)。
3. biased bank loan approvals(有偏见的银行贷款审批)。
4. toxic effect of reinforcing negative stereotypes(强化负面刻板印象的毒性效应)。

除了偏见和不公平对待问题外，还存在机器学习算法的负面用例：

1. deepfale(深度造假。比如未经允许伪造视频)。
2. spreading toxic/incendiary speech through optimizing for engagement(针对特定用户传播有毒/煽动性言论)。
3. generating fake content for commercial or political purposes(为商业或政治目的制造虚假内容)。
4. using ML to build harmful products, commit fraud etc(利用机器学习制造有害产品，进行欺诈等)。

一些建议用于创建更少偏见、更公平、更符合道德规范的机器学习系统：

1. get a diverse team to brainstorm things that might go wrong, with emphasis on possible harm to vulnerable groups(组建一个多元化的团队来集思广益可能会出错的事情，并强调可能造成的伤害)。
2. carry out literature search on standards/guidelines for your industry(对你所在行业的标准/指南进行文献检索)。
3. audit systems against possible harm prior to deployment(在部署系统之前，审计系统以防止可能的危害)。
4. develop mitigation plan(if applicable), and after deployment, monitor for possible harm(制定缓解计划（如果适用），并在部署后监测可能的危害)。【一个简单的缓解计划是回滚到认为相当公平的早期系统。在部署后继续监控危害，以便可以触发缓解计划并迅速采取行动。比如在退出自动驾驶之前制定了缓解计划，以防万一汽车发生事故，可以立即执行缓解计划，而不是让汽车发生事故，才在事后争先恐后地弄清楚该怎么做】

Skewed datasets

这一部分会学习精确度(precision)和召回率(recall)这两个衡量学习算法的指标。

倾斜数据集的误差指标(Error metrics for skewed datasets)

如果你正在开发一个机器学习算法，其中正例(positive example)与负例(negative example)的比例非常倾斜，与50%：50%相去甚远，那么通常的误差指标($J_{train}$,$J_{cv}$,$J_{test}$)效果不好。

举例说明：
假设正在训练二分类模型来检测一种罕见病患者。如果存在疾病则 y = 1, 否则 y = 0。

假设你的学习算法在测试集上达到了1%的误差，那么你的诊断正确率为99%，这似乎是一个很好的结果。但是如果这是一种罕见病，y = 1非常罕见，如果在人群中只有0.5%的人患有这种疾病，那么如果将你的学习算法更改为print(y=0)，即令它始终预测 y = 0，这实际上有0.5%的误差(99.5%的准确度)，这样来看这个愚蠢的算法优于你的学习算法。但显然print(y=0)不是有用的，它永远不会预测任何人患有这种疾病。

因此对于这样的倾斜数据集(正例(positive example)与负例(negative example)的比例非常倾斜)，仅使用误差($J_{train}$,$J_{cv}$,$J_{test}$)来判断算法的性能是不行的，我们会引入另外的指标精确率(precision)和召回率(recall)。

---

y = 1是罕见的类别，例如想要检测的罕见疾病。
评估“预测罕见类别”算法性能，可以构建混淆矩阵(confusion matrix)：一个2×2矩阵。
矩阵的顶部写下实际的类(actual class)：1、0。矩阵的左边写下预测的类(predicted class)：1、0，即你的学习算法在给定的例子上预测了什么。
为了评估学习算法在交叉验证集或测试集上的表现，会计算出每个的数量。比如假设有100个交叉验证示例，其中有15个示例学习算法predicted class=1，且actual class=1；有5个示例学习算法predicted class=1，而actual class=0；有10个示例学习算法predicted class=0，而actual class=1；有70个示例学习算法predicted class=0，且actual class=0。

• 将actual class=1且predicted class=1称为True positive(TP)，因为预测是positive并且实际上也是positive。
• 将actual class=0且predicted class=0称为True negative(TN)，因为预测是negative并且实际上也是negative。
• 将actual class=0且predicted class=1称为False positive(FP)，因为预测是positive而实际上是negative。
• 将actual class=1且predicted class=0称为False negative(FN)，因为预测是negative而实际上是positive

精确度(precision)定义为：在预测患病的人中实际患病人数所占的比例(在所有预测为positive的示例中，实际上是positive的示例所占的比例)。
精确度(precision)的计算公式：
$$\frac{Truepositive}{\#predictedpositive}=\frac{Truepositive}{Truepositive+Flasepositive}=\frac{TP}{TP+FP}$$

召回率(recall)定义为：在实际患有疾病的人中预测患病的人所占的比例(在实际上是positive的示例中，预测为positive的示例所占的比例)。
召回率(recall)的计算公式：
$$\frac{Truepositive}{\#actualpositive}=\frac{Truepositive}{Truepositive+Flasenegative}=\frac{TP}{TP+FN}$$

精确度(precision)和召回率(recall)越高越好。

在这个例子中精确度=0.75，我们说这个算法有75%的精确度，在它认为患有这种罕见病的患者中有75%是真实患病的(75%是预测正确的)。在这个例子中召回率=0.6。【当学习算法说一个人患病时，这个人患病的可能性为75%；同时在患病的人中，学习算法诊断这个人患病的可能性是60%】

【“召回”一词源于：如果有一组患病的群体，那么在所有患病的人中进行“召回”测量，你会准确诊断出有多少人患有该病】

精确率和召回率将帮助检测学习算法是否一直打印y=0，尤其是召回率，因为如果算法一直预测为0，那么True positive(TP)=0，那么召回率(recall)=0。
一般来说，零精度或零召回率的学习算法不是有用的算法。

应该确保精确率和召回率都相当高，这样能确保学习算法是有用的。

精确率与召回率的权衡(trading off precision and recall)

精确度(precision)和召回率(recall)越高越好。因此我们当然都喜欢具有高精确度和高召回率的学习算法。

但事实证明在实践中，精确度和召回率之间往往需要权衡取舍。这部分将学习如何在权衡中选择一个好的点。

如果使用逻辑回归进行预测，那么逻辑回归模型将输出 0~1 之间的数(表示 y = 1的概率)。如果我们给逻辑回归设置一个阈值(threshold)【通常阈值设置为0.5】，那么逻辑回归将输出 y = 1(f ≥ 阈值)，y = 0(f < 阈值)。

但是如果我们想当非常有信心时才预测 y = 1(对应的应用场景是只有当非常有信心时才预测患有疾病，因为一旦预测患有疾病时，不得不将患者接受有害且昂贵的治疗。当然这个前提是这个疾病即使没有治疗后果也不是那么糟糕)。在这种情况下我们可以设置一个更高的阈值(threshold)，比如说设置为0.7，当 f ≥ 0.7时输出 y = 1(我们预测 y = 1时至少有70%的把握)。通过提高阈值，即当非常有信心时才预测 y = 1，这意味着精确度(precision)会提高。提高阈值(threshold)会提高精确度(precision)，但会降低召回率(recall)。

如果我们的应用场景是患者的治疗危害性不大且费用不高，但是如果不治疗后果很糟糕，那么这时我们会想避免漏掉病例，这时可以降低阈值(threshold)，比如说设置为0.3，当 f ≥ 0.3 时输出 y = 1，f < 0.3 时输出 y = 0。通过降低阈值，召回率(recall)会提高。降低阈值(threshold)会提高召回率(recall)，但会降低精确度(precision)。

因此可以通过调整阈值(threshold)在精确度(precision)和召回率(recall)之间进行权衡。

---

选择阈值并不能通过使用交叉验证集来完成，因为经过训练集、交叉验证集已经选择出了阈值。

对于许多应用程序，需要手动选择阈值以权衡精确度和召回率。

可以使用 F1 分数(F1 score)来权衡精确度和召回率。
假设现在训练了三种不同的算法并且得到了对应的精确度和召回率的值，那么如何选出最好的算法呢？

• 将精确度和召回率结合在一起的一种方式是取两者的平均值，但这并不是一种好方法，强烈不推荐。
• 另一种将精确度和召回率结合在一起的方式是F1 分数(F1 score)：结合了精确度和召回率，但它更强调值更低的那个(事实证明，如果算法的精确度非常低或召回率非常低，那么这个算法是没有用的)。
  
  F1 分数(F1 score)的计算公式(precision：P；recall：R)：
  $$F1score=\frac{1}{\frac{1}{2}(\frac{1}{P}+\frac{1}{R})}=2\frac{PR}{P+R}$$

【拓展：F1 score实际上就是数学中的调和平均数，其更强调值更小的那个】

推荐使用 F1 score 来权衡精确度和召回率。选择 F1 score 最大的那个即可。

Decision Trees

决策树模型(Decision Tree Model)

为了解释决策树的工作原理，这里使用“猫分类”示例作为运行示例(根据一些特征区分动物是否是猫)。比如这些特征是耳朵形状(ear shape)、面部形状(face shape)、是否有胡须(whiskers)。耳朵形状有“尖尖的(pointy)”，“耷拉的(floppy)”；面部形状有“圆的(round)”，“非圆的(not round)”；胡须分为有胡须和没有胡须。

输入特征X也是“离散的”。且这里的输入特征X每个分量的值只有两种：0、1。(当然也会有两个以上的“离散值”，后面还会学习“连续值”)。

下面这可能是在上面的数据集上训练决策树学习算法后获得的模型示例。这个模型的工作方式是如果有一个新的测试示例，会从树的根节点开始判断。

这里展示了一个特定的决策树模型。树中最顶层的节点称为“根节点”，中间层的称为“决策节点”，底部的称为“叶子节点”。

当然还有其他的决策树模型：

在上面这些不同的决策树模型中，有些做得很好，而有些做得很差。

决策树学习算法的工作是从所有可能的决策树模型中尝试选择一个希望在训练集上表现良好的模型，更进一步希望在交叉验证集和测试集上也可以做的很好。

学习过程(learning process)

下面是给定训练集构建决策树的全过程。

决策树学习算法的第一步是决定在根节点使用什么特征(具体实现决定使用哪个特征的算法后面会学习)。假设在根节点使用“耳朵形状”，因此使用“耳朵形状”对训练集进行拆分。

第二步是只关注左分支、右分支；决定使用什么特征。

在构建决策树的过程中，我们做了几个关键决定(在算法期间的各个步骤中)。
第一个关键决定：如何为每个节点选择特征以对训练集进行拆分。
为节点选择的特征对训练集进行拆分时应尽量提高纯度(maximize purity)。

第二个关键决定：什么时候停止拆分？(有以下几种策略)

• 当一个节点全部是同一类别时停止拆分。
• 当再分裂节点时会导致超过树的最大深度(depth)，此时停止拆分。
  • 限制决策树深度的原因是确保决策树不会变得太大和笨重，同时保证树比较小可以让它不容易过拟合。
• 当优先级分数的改变(the improvements in the priority score)低于某个阈值(threshold)时停止拆分。
  • 当一个节点拆分后纯度(purity)下降带来的收益低于某个阈值时就不应该进行拆分。这样可以保证树比较小，降低过拟合。
• 当节点的示例数低于某个阈值(threshold)时也可以决定停止拆分。
  • 同样这样做的目的是保证树比较小，降低过拟合。
    
    树的最大深度是一个可以指定的参数。在决策树中，节点的深度定义为从根节点到特定节点的跳数。根节点的深度=0(跳数=0)，根节点下面一层深度=1(跳数=1)。
    

Decision Tree Learning

测量纯度(Measuring purity)

熵(entropy)函数是衡量一组数据纯度的指标。

这里还以“猫分类”为例，定义 $p_1$ 是猫(正例，positive example)所占的比例。(猫(正例)是 y = 1，因此这里使用下标1)。

熵(entropy)函数表示为 $H(p_1)$，对应的曲线图如左面所示，其中横轴是 $p_1$，纵轴是熵的值。

定义 $p_1$ 是猫(正例，positive example)所占的比例。(猫(正例)是 y = 1，因此这里使用下标1)。定义 $p_0$ 是“不是猫”(反例，negative example)所在的比例。因此有 $p_0=1-p_1$。

熵(entropy)函数$H(p_1)$的方程(注意这里 log 以 2 为底：$lo{g}_2$)：
$$H(p_1)=-p_{1}lo{g}_2(p_1)-p_{0}lo{g}_2(p_0)=-p_{1}lo{g}_2(p_1)-(1-p_1)lo{g}_2(1-p_1)$$

熵(entropy)函数$H(p_1)$对应的图像就是左边的曲线。(这里 log 以 2 为底：$lo{g}_2$，只是为了让这条曲线的最大值=1，如果 log 以 e 为底：$ln$，那么只是垂直缩放这个函数，它仍然可以工作，但是曲线的最大值≠1，效果没有那么好)。

如果 $p_1=0或p_0=0$则会出现 $0lo{g}_2(0)=0$。(根据高等数学知识，这个式子等于0)

熵(entropy)函数$H(p_1)$的方程在形式上有点类似逻辑回归的损失函数，这两个公式看起来如此相似实际上是有数学原理的。

熵(entropy)函数是衡量一组数据纯度的指标。【熵(entropy)函数从 0 开始，上升到 1 ，然后又回到 0 】。还有其他像熵(entropy)函数一样的函数，从 0 开始，上升到 1 ，然后又回到 0；比如在一些开源软件包中有被称为 Gini 标准(Gini criteria)的东西，这就是一个类似熵(entropy)函数一样的函数，其对构建决策树也有效。

熵(entropy)函数通常适用大多数应用程序，因此这里只学习熵(entropy)函数。

选择拆分信息增益(Choosing a split:Information Gain)

在构建决策树时，决定在节点上拆分哪个特征将取决于选择哪个特征可以最大程度地减少熵(最大化纯度)。在决策树学习(decision tree learning)中，熵的减少称为信息增益(information gain)。这部分将学习如何计算信息增益，从而决定为节点选择哪个特征进行拆分。

还是以“猫分类”为例(有10个训练示例)，下面决定为决策树的根节点选择哪个特征进行拆分。

下面我们将选择特征拆分可以最大程度地减少熵(最大化纯度)。事实证明，查看这些熵值并进行比较，不如取各自的加权平均值。【“有很多示例且具有高熵”比“有少数示例且具有高熵”更糟糕，这就是为什么要取加权平均值】

计算完各自的加权平均值后，选择值最小的那个。

在实际构建决策树的方式中，我们会对这些公式进行更改，以遵循决策树构建中的惯例，但结果是一样的。在实际构建决策树的方式，我们不仅计算这个加权平均值，还要计算与没有拆分相比熵的减少值。如果在根节点处没有拆分，那么根节点处的 $p_1=0.5$，$H(0.5)=1$。
我们实际用来选择拆分的方式是计算 “根节点的熵 - 左右分支熵的加权平均值”，这就是由于拆分导致的熵的减少值，称为信息增益(information gain)。我们要选择信息增益最大的。

为什么要计算熵的减少值即信息增益，而不是只使用左右分支熵的加权平均值？——事实证明，决定不再进一步拆分的停止标准之一就是熵的减少值即信息增益是否太小(小于某个阈值)。在熵的减少值即信息增益小于阈值时就可以停止拆分，保证树比较小，防止过拟合。

在上面的例子中，在根节点选择“耳朵形状”特征进行拆分会导致熵的减少值(信息增益)最大。

熵的减少值(信息增益)的正式定义/公式：
$w^{left}$是上一层中进入左分支示例数的比例，$w^{right}$是上一层中进入右分支示例数的比例。
$p_1^{left}$是左分支中猫(正例，positive example，y = 1)的比例。$p_1^{right}$是右分支中猫(正例，positive example，y = 1)的比例。
$p_1^{root}$是根节点中猫(正例，positive example，y = 1)的比例。

熵的减少值(信息增益)的公式(根节点的熵 - 左右分支熵的加权平均值)：
$$Informationgain=H(p_1^{root})-(w^{left}H(p_1^{left})+w^{right}H(p_1^{right}))$$

为决策树节点选择最高信息增益的那个特征。这将最大程度地提高左右分支的纯度。

整合(Putting it together)

让我们在决策树中每个节点处使用信息增益选择拆分哪个特征。

构建决策树的全过程：

1. 从树的根节点处的所有训练示例开始，计算所有可能特征的信息增益，并选择要拆分的特征，从而提供最高的信息增益。
2. 根据所选特征将数据集拆分为两个子集，创建树的左右分支并将训练示例发送到左右分支上。
3. 在树的左右分支上重复拆分过程，直到满足停止条件。
   
   停止拆分的条件在「学习过程」部分。

下面还是通过“猫分类”的例子看一下上面这个过程是如何工作的：
这实际上就是递归(recursive)算法，在根部构建决策树的方式是通过在左右分支构建其他较小的决策树。(在查看决策树的代码实现时会看到对递归算法的引用)

决策树的最大深度参数有许多不同的可能选择，一些开源库中会有很好的默认选择供使用。【决策树的最大深度越大，构建的决策树越大，这有点像拟合更高阶的多项式或训练更大的神经网络，它让决策树学习更复杂的模型，会将非常复杂的函数拟合到训练集上，这会增加过拟合的风险。】【同样，类似于在交叉验证集上选择线性回归中的正则化参数 λ ，也可以在交叉验证集上选择合适的决策树最大深度参数。(事实上现在的开源库中提供了更好的方法选择合适的决策树最大深度参数)】

独热编码One-hot(Using one-hot encoding of categorical features)

在前面举的例子中每个特征都是离散值且只有两种可能取值。如果特征可以取两个以上可能的离散值，这时需要使用独热编码(one-hot encoding) 解决这样的问题。

同样还是以“猫分类”为例，只不过这时的数据集发生了一些变化，“耳朵形状”特征变成了尖的(pointy)、耷拉的(floppy)、椭圆的(oval)，即有三种可能；“面部形状”特征和“是否有胡须”特征没有改变，都还是两种。此时特征仍然是离散值，但有特征可以取两个以上可能的值。

此时当决策树节点拆分“耳朵形状”特征时会出现三个子分支，将数据分成三个子集：

独热编码(one-hot encoding) ：如果一个分类特征可以取 k 个可能的值，那么将创建 k 个只能取值 0 或 1 的二进制特征进行替换。

但如果采用独热编码(one-hot encoding) ，为该数据集创建决策树时仍可以遵循前面的方法，仅创建两个分支。根据独热编码(one-hot encoding)的方法，这里“耳朵形状”特征可以取三个可能的值，为此创建三个只能取 0、1 的二进制特征进行替换。在这个例子中将“耳朵形状”特征替换为三个新特征：“是否是尖耳朵”、“是否是耷拉耳朵”、“是否是椭圆耳朵”；这样新特征只能取 0、1；这时的问题就又变为了每个特征仅能取两个可能的离散值的情况，又可以用前面的方法创建决策树。

可以看到采用独热编码(one-hot encoding)使用新特征替换后，新特征中有且仅有一个取值为 1 ，其他的取值为 0。这就是为什么这种方法称为“独热编码(one-hot encoding)”的原因：其中一个特征将始终取值 1 ，即热特征(hot feature)，因此得名独热编码(one-hot encoding)。

使用“独热编码(one-hot encoding)”对分类特征进行编码的思路同样适用于神经网络。将“面部特征”用 0、1表示；将“是否有胡须”用0、1表示。这样3个新特征加上原有的2个特征共5个特征都可以用0、1表示，就可以作为输入特征向量送入神经网络。

连续值特征(continuous valued features)

下面学习修改决策树以使用连续值特征。

同样使用“猫分类”的例子，在原来数据集的基础上添加了“重量大小”特征，这是一个连续值特征。(一般来说猫比狗轻，尽管有些猫比狗重，但“重量大小”仍可以作为一个判断依据)。

假设现在在根节点处拆分“体重大小”特征可以带来最大的信息增益，那么根节点应选择“体重大小”特征，但“体重大小”特征是连续值，如何拆分呢？
如图是“体重大小”特征的数据分布图，“是猫”对应y=1；“不是猫”对应y=0。根据“体重大小”≤阈值(threshold)来进行拆分。在对其进行拆分时应尝试多个不同的阈值，然后选择一个最好的(信息增益最大的)。

一般情况下会根据此特征的值对所有示例进行排序，并取排序后每两个示例中点的值作为阈值(例示例特征值是1，3，5，7，9；那么阈值分别尝试取2，4，6，8)，然后计算信息增益，并选择一个能提供最高信息增益的阈值。最后拿此信息增益与其他特征的信息增益进行比较，决定在节点处拆分哪个特征。

回归树(Regression Trees)

前面仅讨论了决策树，即预测离散类别的分类。如果是回归问题，要预测一个数字，这时可以用决策树的泛化——回归树。

这里使用前面“猫分类”例子中的数据集，只不过与前面预测“是不是猫”不同，这里要预测的是“体重”，即要预测的是一个数字，因此这是回归问题。

回归树叶节点如何预测一个数字：
现在已经构建了一颗树。回归树要解决的问题是对于一个新示例，回归树预测的“体重值”是多少？——回归树将根据训练示例中“体重”的平均值进行预测。

如何构建回归树以预测一个数字：
与构建决策树一样，需要决定在节点处拆分哪个特征。假设现在要从头开始构建回归树，要决定在根节点处拆分哪个特征。在构建决策树时尽可能减少熵，这是对分类问题的纯度度量；而在构建回归树时尽可能减少方差(variance)。
与决策树一样，在构建回归树时也应计算左右子树方差的加权平均值。($w^{left}$、$w^{right}$分别代表进入左右子树的训练示例数)。为节点选择拆分特征时应选择具有最小加权平均值的方差。同样，与决策树计算信息增益(熵的减少值)一样，对其再进行修改以计算方差的减少值；选择最大方差减少值的特征进行拆分。为根节点选择了拆分特征后再递归的进行左右子树特征选择，直到达到停止拆分的条件。

Tree ensembles

使用多个决策树(Using multiple decision tress)

使用单个决策树的缺点之一是该决策树对训练数据中的微小变化高度敏感，解决方案是构建多个决策树——树集成(Tree ensembles)。

举例说明“使用单个决策树的缺点之一是该决策树对训练数据中的微小变化高度敏感”：

因此更常见的做法是训练多个决策树，组成集合——树集成。

对于新示例，应该将其放到决策树集合中的每个决策树上运行，然后每个决策树进行“投票”(少数服从多数)决定最终预测分类。

使用决策树集合后每棵树都会进行“投票”，因此一个树的改变并不会对最终预测有较大影响，这就避免了“使用单个决策树的缺点之一是该决策树对训练数据中的微小变化高度敏感”这个缺点，使得算法更加健壮。

那么如何构建决策树集合呢？——关键技术是使用统计学中的有放回抽样。

有放回抽样(Sampling with replacement)

使用有放回抽样技术构建决策树集合：
构建多个随机训练集，这些训练集与原始训练集略有不同。假设原始训练集中有10个训练示例，如左边所示。右边是创建的一个新的随机训练集，其中示例数与原始训练集示例数一样，其中的训练示例是从原始训练集中有放回的抽取10个。

(根据有放回抽样方法获得的随机训练集中可能会出现相同训练示例，这没关系)

随机森林(Random forest algorithm)

使用多个随机训练集构建树集成算法(tree ensemble algorithm)，这里先学习随机森林算法(Random forest algorithm)，是一种强大的树集合算法，比使用单个决策树效果更好。

生成树集合的方法：
假设原始训练集有 m 个训练示例。那么会使用有放回抽样从原始训练集生成 b 个随机训练集(示例数与原始训练集示例数相同)，在每个随机训练集上各自训练一个决策树。b 的大小选择建议使用64~228中的值，一般使用 b=100。
将 b 设置的更大不会损害性能，但超过某个点后，最终会得到收益递减的结果，而且当 b 远大于100左右时，实际上并没有变得更好。
在随机训练集上生成的决策树也称为袋装决策树(bagged decision tree)，因为随机训练集是从原始训练集中进行有放回抽样获得的(假定原始训练集放在一个包中，从包中进行有放回抽样)，这也是为什么使用字母 b 的原因。

对刚才上面的方法再做一个小修改，可以将算法从反向决策树算法更改为随机森林算法。上面的方法存在的问题是在随机训练集上生成的决策树根节点特征可能是相似，进而导致下面的节点也相似，也就是说这个过程还不够随机、平均。

做的修改是：
在每个节点选择拆分特征时，如果此时有 n 个特征可用，那么随机的从中挑选 k 个特征(k < n)，然后从这 k 个特征中选择最高信息增益的特征作为节点拆分特征。当 n 很大时(n 是几十甚至数百)，k 通常的选择是 $k=\sqrt{n}$，这种技术往往应用于具有大量特征的问题。

修改后的算法就是随机森林算法，比单个决策树更强大。 (使用有放回抽样生成的随机训练集会探索数据的许多微小变化，并且通过修改后的算法会尽可能生成不同的决策树。因此训练集任何微小变化都不太可能对整个随机森林算法的整体输出产生大影响)

XGBoost

目前决策树或决策树集成最常用的实现方式是XGBoost，它运行速度快，开源且易于使用，已被应用于许多商业应用程序。

XGBoost的工作原理：
在前面提到的随机森林算法基础上再进行修改。在随机森林算法中生成 b 个随机训练集是从原始训练集中进行有放回抽样，且是等概率的。XGBoost算法生成 b 个随机训练集时并不是等概率的从原始训练集中进行有放回抽样，而是更高概率的有放回抽取到那些在前面生成的决策树中错误分类的示例。(这种叫刻意练习。背诵文章时更多的精力背那些不熟悉的部分会更快的背诵全篇。更多的精力放到错误分类的示例上那么下一次会表现得更好)

至于XGBoost“更高概率选择错误分类得示例”的实现过程是相当复杂的，但是可以通过开源库直接使用。

XGBoost(eXtreme Gradient Boosting，极端梯度提升)。XGBoost开源且有效，同时有一个很好的默认拆分标准和停止拆分标准，并且内置了正则化以防止过拟合。(在机器学习算法比赛如Kaggle比赛中，XGBoost是一种常用的算法。XGBoost算法和深度学习算法是赢得此类比赛最多的两种算法)

顺便说一下，XGBoost会不同的训练示例分配了不同的方法，因此使用XGBoost算法实际上并不会生成很多随机训练集，这使得它比有放回抽样更有效。

在代码中使用XGBoost：
左边是分类问题；右边是回归问题。

Conclusion

何时使用决策树(When to use decision trees)

决策树(决策树集成)和神经网络都是非常强大的算法，如何选择使用哪一个？

下面看一下各自的优缺点。
决策树(决策树集成)：

• 适用于表格数据，也称结构化数据。(如果数据集是表格，那么决策树值得考虑。例如在“房价预测”例子中的训练集可能就是由输入特征和输出标签构成的表格，用于分类或回归任务，这时就可以用决策树)
• 非常不建议在非结构化数据上使用决策树。(非结构化数据如图像、音频、文本)【神经网络更适合处理非结构化数据】
• 决策树一大优势是训练速度非常快。
• 小型决策树是可解释的。

如果决定使用决策树(决策树集成)，通常使用XGBoost进行实现。(决策树集成要比单个决策树计算成本高)

神经网络：

• 适用所有类型的数据，包括表格等结构化数据、非结构化数据(图像、音频、文本等)以及结构化和非结构化混合数据。
• 缺点是神经网络的训练速度比决策树慢。
• 神经网络的优点包括可以与迁移学习(预训练)一起工作。
• 更容易将多个神经网络串在一起形成一个更大的机器学习系统。(将多个神经网络串在一起也可以使用梯度下降将它们一起训练；而对于决策树来说，每次只能训练一个决策树)