精选博客系列｜将基于决策树的Ensemble方法用于边缘计算

在即将到来的边缘计算时代，越来越需要边缘设备执行本地快速训练和分类的能力。事实上，无论是手机上的健康应用程序、冰箱上的传感器还是扫地机器人上的摄像头，由于许多原因，例如需要快速响应时间、增强安全性、数据隐私，甚至考虑到盈利能力，通常都需要进行本地计算。

无论是以什么方式进行机器学习，对于此类设备来说，具有异构性、有限的连接和有限的硬件资源是一个持续存在的、我们必须解决的挑战。事实上，人们经常面临着矛盾的需求，边缘设备必须在本地执行大量的计算、存储和通信，同时还要遵守如有限的内存、网络连接和计算的资源限制。这通常是由于时间或功率限制以及增加的数据和可用信息量。

这里，我们重点讨论利用基于决策树的Ensemble方法进行计算和内存高效的本地（即设备上）训练和分类，这是处理表格数据的实际标准。

---

基于决策树的Ensemble方法

事实上，基于树的Ensemble方法，例如随机森林（RF）和XGBoost，由于其健壮性、易用性和泛化性，经常用于对表格数据进行分类。反过来，分类任务通常用作许多应用域中的子例程，例如金融、欺诈检测、医疗保健和入侵检测。因此，这种方法的效率和精度与效用之间的权衡至关重要。

让我们特别关注随机森林和XGBoost，并了解它们的优势：

• 随机森林可以说是最流行的bagging方法，它使用数据的随机子样本来生长每个决策树，从而生成不同且弱相关的树。然后，使用多数票确定分类。随机森林有几个优点，包括健壮性、快速训练、处理不平衡数据集的能力、嵌入式特征选择、处理缺失的、分类的和连续的特征，以及高级人工分析或法规要求的、任何时候的可解释性。

• XGBoost是一种著名且流行的boosting算法，它在每次迭代时都会生成一个小的决策树（例如，具有8–32个终端节点）。每个这样的树都是为了减少以前树的错误分类。XGBoost分享了随机森林的大部分优点，并且由于其可控偏差，通常可以实现更高的精度。

然而，这些方法也带来了一些与资源相关的缺点：

• 随机森林往往受内存限制，分类速度较慢。此外，由于随机森林占用大量内存，因此通常无法部署在内存有限的边缘设备上，而这些设备通常需要执行分类任务。

• XGBoost模型通常比随机森林需要更少的内存，但它们是计算密集型的，导致训练速度较慢。

我们解决了随机森林和XGBoost的资源消耗缺点。特别的是，我们引入了一种新的混合方法，该方法继承了bagging和boosting方法的良好特性，具有可比较的机器学习性能，同时大大提高了资源效率。

数据集中的冗余

众所周知，机器学习模型的资源消耗与用于训练的数据集的大小高度相关。因此，减少数据集大小是可取的。因此，我们想提出以下问题：

• 数据集中的所有数据实例对于基于树的ensemble模型的训练是否同样重要？

• 如果没有，我们应该如何在训练期间区分数据实例以节省资源？这将如何影响分类？

事实上，数据集通常包含许多简单的（例如90%）数据实例，因为它们很容易识别，因此很容易分类；以及罕见或更独特的数据实例，因此更难分类。

直观地说，如果在培训之前可以进行这种区分，那么应该能够利用这些知识来节省资源，而不会对准确性产生重大影响。其中一个想法是在培训期间使用较少的“简单”数据实例。面临的挑战是如何制定这样的计划，并以有效的方式这样做。

RADE–资源高效的异常检测模型

数据集只有两个类，其中大多数实例是正常的或良性的（例如99%）。

RADE以以下方式利用上述观察结果：它首先使用整个数据集构建一个小（粗粒度）模型。然后，它使用该模型对用于训练的所有数据实例进行分类。正确分类且具有高度可信度的实例被标记为简单实例（通常是大多数正常实例），而所有其他实例都被标记为困难实例（通常为大多数异常实例）。

如图所示，RADE引入了一种高级体系结构，只要粗粒度模型及其分类提供了有意义的分类置信水平，就可以与不同的分类模型一起使用。

直观地说，由于粗粒度模型足以正确分类简单的查询，所以我们只剩下困难查询。利用这些，我们构建了两个专家（细粒度）模型，用于处理与粗粒度模型的分类结果有关的两种不同情况：细粒度模型1负责（低置信度）正常分类和细粒度模型2用于（低置信度）异常分类。这些模型可能具有比粗粒度模型更大的内存占用需求，但明显低于基于整体的树模型。

训练效率

如前所述，RADE分两个阶段进行训练。首先，使用整个数据集训练粗粒度模型。由于我们使用的是一个小模型，所以这个训练阶段相对较快。然后，我们使用粗粒度模型对整个训练数据集进行分类，并根据所得到的分类和置信度，生成两个数据子集用于训练细粒度模型。由于我们只使用训练数据的子集（例如10%）训练每个细粒度模型，所以这个训练阶段也相对较快。

分类效率

RADE的分类也有两个阶段。首先，根据粗粒度模型对实例进行分类。如果得到的分类置信度较高（例如0.9），则完成分类。否则，根据粗粒度模型分类结果，由其中一个细粒度模型转发查询以进行重新分类。这意味着RADE的分类时间等于仅由粗粒度模型提供服务的分类，以及由粗粒度和细粒度模型提供的分类时间的加权平均值。直觉上，因为目的是为了只通过粗粒度模型（例如90%）服务大多数查询，平均分类时间预计将比标准的整体模型显著改进。

Duet–资源高效的多类分类模型

RADE是为二进制分类设计的，因此使用两个细粒度模型。就多类分类用例而言，扩展RADE的体系结构并不是一个可扩展的解决方案，因为它需要K类的K个细粒度模型，因此需要一个新的体系结构。

为此，我们开发了Duet。Duet遵循RADE的原则，即使用粗粒度模型，该模型在整个数据集上经过训练，并对简单的查询进行分类。然而，与RADE不同，Duet只使用单个细粒度分类器，该分类器在训练数据集的子集上进行训练，并对困难（低置信度）查询进行分类。

Duet的高级体系结构如图所示。从本质上讲，它使用了两个分类器：一个小型bagging分类器（随机森林），提供有意义的分类置信度、受控方差和内存限制，另一个boosting分类器（XGBoost），提供受控偏差和计算限制。总的来说，与单例分类器相比，Duet引入了一种不同且通常更好的系统/机器学习性能的权衡。

Duet的主要问题是如何确定boosting分类器的训练数据子集。

在这种情况下，使用RADE中的置信度指标是不够的，因为我们有一个多维问题。因此，我们使用类概率分布向量（通过粗粒度模型）来确定实例对训练过程的重要性。

对于六个类别的分类任务，考虑两个具有相同（第一）分类置信度的分类结果。第一个在两个类别上的概率（几乎）相等（例如[0.5，0.5，0，0，0,0]），第二个在正确类别上概率较高，而在所有剩余类别上概率低得多（例如[0.5,0.1，0.1，0.1,0.1，0.1]）。显然，第一个查询比较困难，可能更有利于增强分类器的训练。

为了捕获此属性，我们定义了一个新的度量标准–可预测性这是由欧几里得距离函数给出的，该函数测量得到的类概率分布向量相对于实例的真实标签与完美分布向量之间的距离。完美分布向量在正确标签（即类）中的概率应为1。

请注意，可预测性是训练过的bagging分类器和训练数据集的具体度量，因此是Duet训练过程中的一个集成步骤。此外，使用可预测性不同于仅依赖于数据集属性的采样方法（例如，分层采样，它保留了每个类的实例百分比）。

进一步的潜力

上述设计原则可能适用于其他机器学习领域。虽然Duet主要使用可预测性度量来降低训练和分类过程的计算成本，但可以使用可预测度度量来减少训练数据集的大小，从而降低存储和通信成本。

此外，RADE和Duet还可能适用于分布式学习。例如，参与方可以联合训练一个粗粒度模型，然后使用该模型从本地数据集中选择子集，最后使用这些子集训练全局细粒度模型。

这里的挑战是确定参与方选择其子集的标准。例如，一种高级方法是使用安全计算来收集有关全局训练数据的一些统计信息。这样的统计数据可能会使每个参与者选择更好的子集，总的来说，对于细粒度模型的分布式训练，这样有更高的训练价值。

内容来源｜公众号：VMware 中国研发中心