Hierarchical Pruning of Deep Ensembles with Focal Diversity

Most of the existing ensemble learning studies can be summarized into three broad categories. The first category builds ensemble teams by training a set of member models, represented by bagging (Breiman, 1996), boosting (Breiman et al., 1998) and random forests (Breiman, 2001). In practice, it has led to large ensemble teams of tens to hundreds of member models, such as the commonly-used random forests. The second category is to leverage diversity measurements to compare and select high quality ensemble teams whose member models can complement each other to improve the ensemble predictive performance without requiring model training. Ensemble diversity can be evaluated using pairwise or non-pairwise diversity measures, represented by Cohen’s Kappa (CK) (McHugh, 2012) and Binary Disagreement (BD) (Skalak, 1996) for pairwise metrics and Kohavi-Wolpert Variance (KW) (Kohavi and Wolpert, 1996; Kuncheva and Whitaker, 2003) and Generalized Diversity (GD) (Partridge and Krzanowski, 1997) for non-pairwise metrics. Early studies (Kuncheva and Whitaker, 2003; Tang et al., 2006) have reported that it is challenging to use these diversity metrics for evaluating the performance quality of ensemble teams. Some recent studies (Fort et al., 2020; Liu et al., 2019; Wu et al., 2021, 2020) discussed inherent problems of using these diversity metrics to measure ensemble diversity in terms of failure independence and provided guidelines for improving the ensemble diversity measurement. This paper contributes to this second category by leveraging focal ensemble diversity metrics for effective pruning of deep ensembles. The third category covers the ensemble consensus methods for aggregating member model predictions and producing the ensemble prediction, such as soft voting (model averaging), majority voting and plurality voting (Ju et al., 2017) or learn to combine algorithms (Liu, 2011; Wu et al., 2020).

We summarize the three categories of related studies in Table 1. These three categories are complementary. To develop an ensemble team for improving prediction performance, we can employ one of the two ways to obtain an ensemble of member models: (1) training multiple models together using an ensemble learning algorithm, such as bagging, boosting, or random forest; and (2) training multiple models independently in parallel and employ a voting method to produce ensemble consensus based predictions. Most of the early studies before 2015 in the first two categories (Caruana et al., 2004; Banfield et al., 2005; Tsoumakas et al., 2009; Martínez-Muñoz et al., 2009; Lazarevic and Obradovic, 2001) focused on ensemble pruning for traditional machine learning models. Until recently, we have observed several research endeavors on deep neural network ensembles, most of which centered on training multiple networks jointly, such as diversity based weighted kernels (Chow and Liu, 2021; Bian et al., 2020; Yin et al., 2014) and leveraging deep ensembles to strengthen the robustness and resilience of a single deep neural network under adverse situations (Liu et al., 2019; Wei et al., 2020; Wei and Liu, 2021; Chow et al., 2019; Chow and Liu, 2021; Wu et al., 2021, 2023). However, to the best of our knowledge, very few studies have brought forward solutions to efficient deep ensemble pruning to improve prediction performance and reduce ensemble execution cost.

We compare our focal diversity powered hierarchical ensemble pruning approach and early studies using ensemble diversity for ensemble pruning in Table 2. Our focal diversity promotes fair comparison of ensemble diversity among the ensembles of the same size $S$ and leverages the focal model concept, focal negative correlation, and averaging of multiple focal negative correlation scores to obtain accurate ensemble diversity measurements. We will provide a detailed description of focal diversity powered hierarchical pruning in Section 3 and demonstrate that our hierarchical pruning approach can be effectively applied to both deep neural network ensembles and ensembles of traditional machine learning models in Section 5.

This paper presents a holistic approach to efficient deep ensemble pruning. Given a large deep ensemble of $M$ member networks, we propose a hierarchical ensemble pruning framework, denoted as HQ, to efficiently identify high quality ensembles with lower cost and higher accuracy than the entire ensemble of $M$ networks. Our HQ framework combines three novel ensemble pruning techniques. First, we leverage focal ensemble diversity metrics (Wu et al., 2021) to measure the failure independence among member networks of a deep ensemble. The higher focal diversity score indicates the higher level of failure independence among member networks of a deep ensemble, that is higher complementary capacity for improving ensemble predictions. Our focal diversity metrics can precisely capture such correlations among member networks of an ensemble team, which can be used to effectively guide ensemble pruning. Second, we present a novel hierarchical ensemble pruning method powered by focal diversity metrics. Our hierarchical pruning approach iteratively identifies subsets of member networks with low diversity, which tend to make similar prediction errors, and then prunes them out from the entire ensemble team. Third, we perform focal diversity consensus voting to combine multiple focal diversity metrics for ensemble pruning, which further refines the hierarchical ensemble pruning results by a single focal diversity metric. Comprehensive experiments are performed on four popular benchmark datasets, CIFAR-10 (Krizhevsky and Hinton, 2009), ImageNet (Russakovsky et al., 2015), Cora (Lu and Getoor, 2003) and MNIST (Lecun et al., 1998). The experimental results demonstrate that our focal diversity based hierarchical pruning approach is effective in identifying high quality deep ensembles with significantly smaller sizes and better ensemble accuracy than the entire deep ensemble team.

Our focal diversity metrics are designed to provide more accurate measurements of failure independence of the member networks in a deep ensemble team, including both pairwise (F-CK and F-BD) and non-pairwise (F-GD and F-KW) diversity metrics. Unlike traditional ensemble diversity evaluation approaches, which randomly select samples from the validation set to evaluate ensemble diversity, our focal diversity measurements draw random negative samples from $NegSampSet(F_{f})$ based on a specific focal model $F_{f}$ on which the focal model $F_{f}$ makes prediction errors and then calculate the focal negative correlation score. For a given deep ensemble of $S$ member networks, each of the $S$ member networks will serve as the focal model ($F_{f}$) to draw negative samples. Therefore, we have a total of $S$ focal negative correlation scores, where each corresponds to a member network serving as the focal model. Then we obtain the focal diversity score for this deep ensemble of $S$ member networks through the (weighted) average of $S$ focal negative correlation scores. The focal model concept is motivated by ensemble defense against adversarial attacks (Chow et al., 2019; Wei and Liu, 2021), where the attack victim model is protected in a defense ensemble team. The focal model can be viewed as the victim model to evaluate the failure independence of other member models to this focal model in an ensemble team, i.e., the focal negative correlation score. Thus, the ensemble diversity score for this ensemble of size $S$ can be computed as the (weighted) average of $S$ focal negative correlation scores by taking each member model as a focal model to mitigate the bias in diversity evaluation using only one focal model. Our preliminary results have demonstrated promising performance of the focal diversity metrics in capturing the failure independence of the member networks of a deep ensemble team (Wu et al., 2020, 2021; Wu and Liu, 2021).

In general, our focal diversity metrics compare the ensemble diversity scores among the ensembles of the same size $S$, randomly draw negative samples from each focal model ($F_{f}$, i.e., $NegSampSet(F_{f})$) and calculate the focal diversity score as the average of $S$ focal negative correlation scores by taking each member model as the focal model. Algorithm 1 gives a skeleton of calculating the focal diversity scores for all the candidate sub-ensembles in $EnsSet$. For each team size $S$ (Line 6$\sim$30), we follow two general steps to calculate the focal diversity scores for each ensemble. First, for each member model $F_{f}$, let $EnsSet(F_{f},S)$ denote all candidate ensembles of size $S$, each containing the focal model $F_{f}$. We first compute the focal negative correlation score for each ensemble in $EnsSet(F_{f},S)$ with the negative samples randomly drawn from the focal model $F_{f}$ ($NegSampSet(F_{f})$) and store them in $D(Q,S,F_{f})$ (Line 10$\sim$14). Then, in order to make them comparable across different member models ($F_{f}$), we scale $D(Q,S,F_{f})$ into $[0,1]$ and store them in $\overline{D}(Q,S,F_{f},T_{i})$ for each ensemble team $T_{i}$ (Line 15$\sim$18). Second, for each candidate sub-ensemble ($T_{i}$) of size $S$, we perform a weighted average of the scaled focal negative correlation scores $\overline{D}(Q,S,F_{f}=T_{i}[j],T_{i})$ associated with each of its focal (member) model $F_{f}=T_{i}[j]$ to obtain the focal diversity score. The weight is calculated with the corresponding rank of the accuracy of the member model ($T_{i}[j]$) in the ensemble team ($T_{i}$), i.e., the member models with higher accuracy will have higher weights (Line 21$\sim$29). In addition, we subtract the CK value from 1 when using the CK formula (McHugh, 2012) to present the consistent view that high diversity values correspond to high ensemble diversity.

We show a visual comparison between our focal diversity metric F-GD in Figure 1b and the baseline GD metric in Figure 1a for CIFAR-10. Here the baseline mean threshold based ensemble pruning method is used for both F-GD and GD diversity metrics. Compared to the GD based ensemble pruning, the F-GD powered pruning obtains better ensemble pruning results and identifies a larger portion of sub-ensembles (on the right side of the vertical red dashed line) with ensemble accuracy above the reference accuracy of 96.33% (horizontal black dashed line).

When the focal diversity metrics are used in our hierarchical pruning algorithm with a desired team size $S_{d}$, we only calculate the diversity scores for the ensembles of size $2\sim S_{d}$ by replacing $M-1$ with $S_{d}$ in Line 6 of Algorithm 1 to reduce the computation cost. Compared to the baseline diversity metrics, our focal diversity score computation takes about 1.2$\sim$2.4$\times$ the time of the baseline diversity score computation for all candidate sub-ensembles in $EnsSet$. The computation of all focal diversity metrics can be finished in several seconds on MNIST, CIFAR-10 and Cora and in several minutes on ImageNet (see Table 16). Given that our focal diversity metrics significantly outperform the baseline diversity metrics in capturing the failure independence of a group of member models, it is beneficial and worthwhile to use our focal diversity metrics to measure the ensemble diversity and identify high quality sub-ensembles. In addition, our hierarchical pruning can effectively prune out about 80% of the ensemble teams in $EnsSet$, which also compensates for the increased computation time of the focal diversity metrics, making our entire solution very efficient.

We show the baseline mean threshold based ensemble pruning results using our focal diversity F-BD and F-GD in the 3rd and 5th columns of Table 6 for CIFAR-10 and Table 7 for ImageNet. Both F-BD and F-GD (optimized) substantially outperform the baseline BD and GD based ensemble pruning, as measured by the accuracy range of the selected sub-ensembles in $GEnsSet$, precision and recall. For the other two diversity metrics, CK and KW, we observed similar performance improvements of using our focal diversity metrics, F-CK and F-KW, in the baseline ensemble pruning. Even though our focal diversity metrics can significantly improve the baseline mean threshold based ensemble pruning method, achieving very high recall of over 95%, we can still enhance the 63.53% precision of F-BD and 53.90% precision of F-GD for CIFAR-10 and the 41.93% precision of F-BD and 36.75% precision of F-GD for ImageNet to more accurately identify high-quality sub-ensembles. In addition, the baseline mean threshold based ensemble pruning examines every sub-ensemble in $EnsSet$ with high computational cost. These observations have motivated us to explore new methods to enhance ensemble pruning efficiency and accuracy.

Our focal diversity metrics reveal some anti-monotonicity property: a superset of a low diversity ensemble has also low diversity. Specifically, a low focal diversity score for an ensemble team, e.g., $F_{0}F_{2}$, often implies insufficient ensemble diversity, that is a high correlation of its member models in making similar prediction errors, making the member models highly redundant for a large superset ensemble team, such as $F_{0}F_{1}F_{2}$. Hence, those large ensembles that contain a small sub-ensemble with low diversity (e.g., $F_{0}F_{2}$), such as $F_{0}F_{1}F_{2}$, $F_{0}F_{2}F_{3}$, $F_{0}F_{1}F_{2}F_{3}$, and $F_{0}F_{1}F_{2}F_{4}$ tend to have lower ensemble diversity than other ensembles with the same size and more diverse member models. Therefore, when we identify a sub-ensemble with low ensemble diversity, these large ensembles that are the supersets of this sub-ensemble can be preemptively pruned out, which motivates our hierarchical ensemble pruning approach. The pseudo code is given in Algorithm 2. Overall, our hierarchical pruning is an iterative process of composing and selecting deep ensembles for a desired ensemble team size $S_{d}$. First, we start the hierarchical pruning process with the ensembles of size $S=2$, that is $|EnsSet(S=2)|=\binom{M}{2}=10(10-1)/2=45$ candidate ensemble teams. Second, for a given focal diversity metric, we rank candidate ensembles of size $S$, such as $S=2$, by their focal diversity scores ($q_{i}$), prune out the bottom $\beta$ percentage of ensembles with low focal diversity scores, and add them into $pruneSet$ as the pruning targets (Line 17$\sim$19). Here, a dynamic $\beta$ can be configured to accommodate the concrete number of candidate ensembles and diversity score distribution. A conservative strategy is recommended to set a small $\beta$, e.g., by default $\beta=10\%$. Third, we preemptively prune out all subsequent ensemble teams with a larger size $S+1$ that contain one or more pruned sub-ensembles in $pruneSet$ (Line 7$\sim$16). By iterating through these pruning steps, our hierarchical pruning can efficiently identify high quality sub-ensembles of the desired team size $S_{d}$ and add them into $GEnsSet(Q,S_{d})$.

We present a hierarchical ensemble pruning example on ImageNet in Figure 2. With $M=10$, we have all 10 member networks on the top, followed by all sub-ensembles of size $S=2$. For each tier, we add one additional network to the candidate ensemble teams of size $S~{}(2\leq S<S_{d})$ and place these extended ensembles of size $S+1$ in the next tier until $S=S_{d}$, where the ensembles of the desired team size $S_{d}$ will be placed in the last tier. Meanwhile, for each pruned ensemble, such as $F_{0}F_{2}$, our hierarchical pruning algorithm will preemptively cut off these branches of candidate ensemble teams that contain this pruned ensemble, i.e., all ensembles that are supersets of $F_{0}F_{2}$, marked by the red cross in Figure 2. This way of building ensemble teams allows us to compose high quality sub-ensembles and strategically remove the ensembles with low diversity. As the example in Figure 2 shows that our hierarchical pruning indeed can effectively prune out these ensemble teams with low diversity and low accuracy, such as $F_{0}F_{1}F_{2}$, $F_{0}F_{2}F_{3}$, $F_{0}F_{1}F_{2}F_{3}$ and $F_{0}F_{1}F_{2}F_{4}$, and avoid exploring those unpromising branches.

We first apply our F-BD and F-GD hierarchical ensemble pruning algorithms on CIFAR-10 to prune the entire deep ensemble of 10 member networks by setting $\beta=10\%$ and $S_{d}=5$. Figure 3 visualizes the ensemble pruning results, where the black and red dots denote the pruned and selected ensemble teams respectively. Three interesting observations should be highlighted. First, for our focal diversity metrics, including F-BD and F-GD, the ensemble teams with high focal diversity scores tend to have high ensemble accuracy, especially when we compare the ensemble teams of the same size $S$, e.g., $S$=3, 4, 5, which is an important property to guide ensemble pruning. Second, our hierarchical ensemble pruning approach can effectively identify these ensemble teams with insufficient ensemble diversity by their low focal diversity scores. The effectiveness of our hierarchical pruning can be attributed to two factors. On the one hand, our focal diversity powered hierarchical pruning encourages more fair comparison of focal diversity scores among these ensembles of the same size $S$. Comparing to Figure 1b showing all possible ensembles of mixed team sizes, Figure 3 shows much clearer correlation between the focal diversity score and ensemble accuracy for the ensembles of the same size $S=3,~{}4,~{}5$. On the other hand, our focal diversity metrics can more precisely capture the failure independence of member networks of a deep ensemble with some anti-monotonicity property, ensuring that the focal diversity based ensemble pruning is highly accurate and efficient. Third, the time and space complexity of the hierarchical pruning algorithm and pruned ensemble execution cost can be ultimately bounded by the desired team size $S_{d}$. For example, we recommend setting the desired ensemble team size $S_{d}$ up to $50\%\times M$, which allows our hierarchical pruning to effectively find these sub-ensembles that offer on par or improved ensemble accuracy over the entire ensemble of $M$ member networks and have a substantially smaller team size, such as one third or one half of $M$ with a significant cost reduction in ensemble execution. Finally, for Figure 3c and 3f, all the selected sub-ensembles (red dots) with the desired team size $S_{d}=5$ provide higher ensemble accuracy than the reference accuracy of 96.33% for CIFAR-10, which leads to 100% precision of our hierarchical pruning with F-BD and F-GD. We observe similar ensemble pruning results using the other two focal diversity metrics, F-CK and F-KW.

For an ensemble team of size $S$, following (TUMER and GHOSH, 1996; Wu et al., 2021), we can derive the added error for its ensemble prediction $E_{add}^{avg}$ using model averaging ($avg$) as the ensemble consensus method as Formula (1) shows.

where $E_{add}$ is the added error of a single network and $\delta$ is the expected average correlation of all member networks in the ensemble. Therefore, the ideal scenario is when all member networks in an ensemble team of size $S$ are diverse. They can learn and predict with uncorrelated errors (failure independence), i.e., $\delta\leq 0$. Then a simple model averaging method can significantly reduce the overall prediction error by at least $S$ times. Meanwhile, the worst scenario happens when errors of individual networks are highly correlated with $\delta=1$. For example, when all $S$ member networks are perfect duplicates, the error of the ensemble is identical to the initial error without any improvement. In practice, given that it is challenging to directly measure the correlation $\delta$, many ensemble diversity metrics are proposed to quantify the correlation among member networks of an ensemble team. Our focal diversity metrics can significantly improve ensemble diversity measurement, and they are closely correlated to the ensemble prediction performance, which can be directly leveraged for identifying high-quality ensemble teams.

The deep neural network model is typically trained to minimize a cross-entropy loss and output a probability vector to approximate posteriori probabilities for the corresponding classes. Let $f_{i}(\textbf{x})$ denote the ith element in the probability vector of a classifier $F$ for input x, which predicts the probability of class $i$. The classifier $F$ will output the predicted label $c$ with the highest probability for input x, that is $c=argmax_{1\leq i\leq C}f_{i}(\textbf{x})$.

The robustness of a classifier $F$ can be assessed based on its ability to maintain consistent prediction for a given input x under input perturbation ($\mu$), such as the noise from adversarial samples. When the magnitude of the input perturbation $\mu$ remains within a certain bound, the prediction made by the classifier $F$ remains unaffected. We can leverage such a bound to compare the level of robustness of different classifiers, where a higher bound indicates a higher level of robustness. In Theorem 1, we introduce the concept of robustness bound ($R$) and formally show that this bound fulfills the aforementioned requirement.

We first introduce Lemma 2 on Lipschitz continuity below and then show the formal proof of Theorem 1.

For a deep neural network $F_{k}$, we have its robustness bound as Formula (9) shows.

Let $g_{j}^{k}(\textbf{x})=f_{c}^{k}(\textbf{x})-f_{j}^{k}(\textbf{x})$, we have the robustness bound as Formula (10) shows.

Given $S$ networks, combining their predictions with model averaging ($avg$), we have the ith element in the combined probability vector as $f_{i}^{avg}(\textbf{x})=\frac{1}{S}\sum_{k=1}^{S}f_{i}^{k}(\textbf{x})$ corresponding to the robustness bound as the following Formula (11) shows.

Assume the minimum of the robustness bound can be achieved with the prediction result $c$ and $j$ for each model $F^{k}$ including the ensemble $F^{avg}$ as Formula (12) shows.

where $g_{j}^{k}(\textbf{x})=f_{c}^{k}(\textbf{x})-f_{j}^{k}(\textbf{x})$ and $g_{j}^{avg}(\textbf{x})=\frac{1}{S}\sum_{k=1}^{S}g_{j}^{k}(\textbf{x})$.

We can then derive Theorem 3 that states $\exists~{}k,1\leq k\leq S,R^{k}\leq R^{avg}$, where the equal sign corresponds to the case that all member networks are the perfect duplicates. This theorem further indicates that the ensembles of high diversity can improve the robustness of individual member networks.