硬件集成约简：CANOPY和HERALD

这几天看了老师发的两篇论文。这两篇论文有自己的系统，提供了很好的启发性集成修剪方法，可以很好的应用到芯片中。

本文是基于对原文的翻译和自己的理解。由于作者的理解有限，基础不扎实。欢迎批评和纠正本文的内容！

首先介绍第一篇论文：Ensemble Reduction via Logic Minimization。

决策树通常用作综合学习的基算法。在可穿戴设备中，决策树的自然二分类结构与数字电路本身的逻辑0和1相似&在移动终端的算法部署中，决策树通常被集成到FPGA芯片。然而，单棵决策树的效果并不特别理想，因此需要采用综合学习的方法来提高算法的精度和鲁棒性。在移动终端芯片中嵌入了大量的决策树(通常是在$10^1?10^2$数量级)，这需要大量的存储容量。同时，在计算中，也需要大量的能源消耗和计算资源。因此，在移动终端上进行集成修剪是必不可少的。本文提出了基于卡诺图的集成修剪方法，可以从底终端设备芯片结合，优化硬件层面的算法，并确保一定的精度和准确性。

卡诺图优化

在数字电路和逻辑设计中，给出一系列真值表，然后找出相应的逻辑表达值，我们通常使用卡诺图简化，给定的逻辑真值表如下：

x1	x2	x3	x4	y
0	0	0	0	0
0	0	0	1	0
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	1	0	1
0	1	1	1	0
1	1	0	0	1
1	0	0	1	0
1	0	1	0	1
1	0	1	1	0

表1 数据真值表

要求逻辑表达式$y(x_1,x_2,x_3,x_4)$，我们须列出卡诺图。行为x1x2的取值，列位x3x4的取值，中间值为y。其中，真值表中没有的表达式我们就设为“x"。

X1x2\x3x4	00	01	11	10
00	0	0	0	1
01	0	x	0	1
11	1	1	1	x
10	x	0	0	1

​ 表2 卡诺图

然后，我们用求逻辑最小项的方法求表达式，根据卡诺图我们可以在$x_1{x}_2=11$和$x_3{x}_4=10$处画两个圈，最后得到的逻辑表达式如下：
$$y=x_1{x}_2+x_3\overline{x_4}$$
对于算法，我们也可以这么表示。在这里，对于二分类问题，我们假设$m_1,m_2,m_3,m_4$就是4个基学习器，而$y_i$就是某一个样本$exampl{e}_i$的标签，$x_1,x_2,x_3,x_4$则是4个基学习器对该样本的预测。那么真值表中第一行$x_1,x_2,x_3,x_4=0000,y=0$就是针对某一个输入样本，四个基学习器对其分类的预测都是0，而其真实的标签为0。就组成了真值表中的一行，其他行以此类推。我们先看一看算法的伪代码：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-otaOd46S-1637774852675)(/Users/wumozhou/Documents/untitled folder/CANOPY.PNG)]

因为这是一个集成约减算法，因此输入还是一组集成，里面每一个$m_i$都是一个训练好的基学习器。当然，为了保证基学习器的多样性，在训练数据方面论文采用了Bagging的方法训练了一组集成，当然也可以通过各式各样的学习算法来训练。训练样本集$D_{train}$包括了所有的训练样本，形成的元组就是训练数据及其标签。算法的输出就是几个基学习器的逻辑表达式。

复杂度分析：模型数量为T，假设都是决策树，每个树的平均深度为$D$，样本数量为N，**这个算法的时间复杂度$O(NTD+N^2)$,**其中$NTD$来源于第1-3行，$N^2$来源于第1,7行。可见，在样本数量增加时，对集成修剪的训练更加困难。

算法解读：

[1-6]对于每一个输入样本，让所有的基学习器对这个样本的分类进行预测，组成一个编码向量${\hat{y}}_j=[{\hat{y}}_{j1},{\hat{y}}_{j2},...,{\hat{y}}_{jT}]$，再在末尾加上这个样本的真实标签，形成了一个编码向量。比如输入的第一个样本，四个基学习其对其的预测都是0，其真实标签也是0，那么这条编码向量则为00000.

[7-10]这里是什么意思呢？这是防止编码重复。假设这一行编码向量已经存在了，那么就不加入真值表了。比如说，对于第一个输入样本，完成的编码是00000，而第五个输入样本的编码也是00000，那么就不把这个编码加入真值表中。但可能还会有异常情况，比如又有一个输入样本，四个基学习器对其的预测是1010，真实标签为1，组成编码10101；而对于另一个输入样本，四个基学习器的预测也是1010，但是真实标签却是0.在这种情况下输入真值表的值为真实标签出现频率大的一方。不过在实验中，这种事情基本不可能发生。

[13]算法的核心，求得真值表后，通过逻辑最小化求得最简表达式。

最后，求得逻辑表达式之后，就只用保留几个被选中的模型，其他的模型就可以直接删去了。对于表2的集成约减，我们最后得到了函数$y=x_1{x}_2+x_3\overline{x_4}$，意为，给定一个样本，需要满足：第一、第二个基学习器都预测为正例，或者第三个学习器为正例，第四个学习器为负例。这样在集成后的结果才是正例。

我们先探讨一下，这个方法为什么能Work呢？对于二分类问题而言，我们通过Bagging训练了一个集成模型，里面有大量的基学习器，在这些基学习器的地位都等同的情况下，集成模型的分歧不一定会很强（因为这些模型都是根据同一个任务训练出来的算法）。那么就不能否认，模型之间就有一定的相似性。假设一个基学习器的效果可以被其他基学习器线性表示，那么，在投票法的情况下，我们就可以删去该基学习器。本篇论文就通过了逻辑最小化的方法找出了比较相似的模型，并将其删去，通过已存在基学习器的逻辑表达式用来代替整体的模型，这样也是合理的。同样，这也是一种非线性的组合函数，通过卡诺图的方法也能更好的揭示模型之间的相互联系，以及模型对不同样本的反应。在其中，将没有出现的真值设为“x"，也就是“不关心”，最后通过卡诺图的方法来给“x"赋值，同样也是一个一致性正则化的方法。

当然，CANOPY不仅能用于二分类问题的约简，也能用于多分类问题的约简。如果有第三、四个类别，只需要模型输出"00,01,10,11"即可。在约简中也将两个bit作为一个单位来逻辑最小化。

以上就是第一篇论文的主要内容，接下来介绍第二篇论文：Work-in-Progress: Hierarchical Ensemble Learning for Resource-Aware FPGA Computing，这是第一篇论文的强化版。第二篇论文提出了名为“HERALD”的框架，这是第一个可以支持将超过500个决策树集成到FPGA中去的框架。对于很多仅工作在软件层的算法，这无疑是一大进步。

上半篇文章我们介绍了CANOPY（树冠算法），这个算法还有一些缺点，缺点如下：

1. 训练时间随着初始模型池中树的增加而大量增加。（个人感觉似乎是线性的）
2. 准确率不如随机森林，其中在超过100棵树的情况下极为明显。（毕竟筛掉了太多的模型）
3. CANOPY没有在任何硬件上进行实际的评估。

而对于应用来说，现在多数的算法集成到FPGA中，都是先通过MATLAB\C\C++ 撰写源代码之后再通过编译器，最后集成到FPGA中，但这种方法也没有很好的利用FPGA的资源。另外绝大多数算法模型都需要特定的处理器和操作系统作为基础设施。HERALD自动实现了软件到硬件的转变。集成模型也可以被映射到基本的门控和跳变单元，最后嵌入至IOT设备。

HERALD包括以下四步：

1. 首先建立初始模型池，这里采用了CART算法训练决策树，这一步也是随机森林算法的一部分。
2. 森林通过特定的分块策略被平均分成K部分，分块策略会在后面讨论。
3. 在K个部分中的每一部分，使用集成约简（上文的CANOPY算法），获得新的子部分。
4. 在预测时，这K个部分分别对样本进行预测，最终结果由多数投票法决定。

接下来我们看看算法的伪代码：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1FK6Jp0F-1637774852676)(/Users/wumozhou/Documents/untitled folder/IMG.jpeg)]

在算法中，$RF$就是随机森林，其中的每一个基学习器$m_i$就是一棵树。数据集$D_{train}$，每一group的大小阈值$\theta$，选择策略$p$，分类策略的参数$\lambda$和最初子部分的大小$△$。

对于$partitionEnsemble$函数，这个函数输出K个group，每个group包含相同数量的树。$C{F}_k$是模型的结合函数。若每个group中的树数量少于阈值$\theta$,那么我们就简单的使用多数投票法作为这个group的预测函数，而数量多于阈值$\theta $的group，我们就采用CANOPY函数求得逻辑最小表达式，作为这个group的预测函数。我们可以从中看出，每一个group组成的随机森林$RF_k$都是总体森林$RF$的子集，并且所有group中森林组成并集也是总体森林的子集，满足$\abs{\cup_{k=1}^K RF_k}\leq \abs{RF}$。通常，在运用了约减算法之后，所有group中森林就算组成了并集，数量也会大大减小。输出的$G_k$就是每个group中的模型下表索引以及预测函数。而对于整个集成模型的预测，也是每一个group对输入样本进行预测，最后采用最大投票法得出最后对结果。

接下来填个坑，介绍一下 p a r t i t i o n E n s e m b l e partitionEnsemble pa元器件数据手册、IC替代型号，打造电子元器件IC百科大全！