Fast Meta-Learning for Adaptive Hierarchical Classifier
Design
Gerrit J.J. van den Burg1

Alfred O. Hero2

1

2

Econometric Institute, Erasmus University Rotterdam, The Netherlands
Electrical Engineering and Computer Science, University of Michigan, USA

arXiv:1711.03512v1 [cs.LG] 9 Nov 2017

November 10, 2017

Abstract
We propose a new splitting criterion for a meta-learning approach to multiclass
classifier design that adaptively merges the classes into a tree-structured hierarchy of increasingly difficult binary classification problems. The classification tree is
constructed from empirical estimates of the Henze-Penrose bounds on the pairwise
Bayes misclassification rates that rank the binary subproblems in terms of difficulty of classification. The proposed empirical estimates of the Bayes error rate are
computed from the minimal spanning tree (MST) of the samples from each pair of
classes. Moreover, a meta-learning technique is presented for quantifying the onevs-rest Bayes error rate for each individual class from a single MST on the entire
dataset. Extensive simulations on benchmark datasets show that the proposed hierarchical method can often be learned much faster than competing methods, while
achieving competitive accuracy.
Keywords: classifier performance, meta-learning, multiclass classification, hierarchical classifier, classifier comparison

1

Introduction

The Bayes error rate (BER) is a central concept in the statistical theory of classification.
It represents the error rate of the Bayes classifier, which assigns a label to an object
corresponding to the class with the highest posterior probability. By definition, the
Bayes error represents the smallest possible average error rate that can be achieved by
any decision rule (Wald, 1947). Because of these properties, the BER is of great interest
both for benchmarking classification algorithms as well as for the practical design of
classification algorithms. For example, an accurate approximation of the BER can be
used for classifier parameter selection, data dimensionality reduction, or variable selection. However, accurate BER approximation is difficult, especially in high dimension,
and thus much attention has focused on tight and tractable BER bounds. This paper
proposes a model-free approach to designing multiclass classifiers using a bias-corrected
BER bound estimated directly from the multiclass data.
There exists several useful bounds on the BER that are functions of the classdependent feature distributions. These include information theoretic divergence measures such as the Chernoff α-divergence (Chernoff, 1952), the Bhattacharyya divergence
(Kailath, 1967), or the Jensen-Shannon divergence (Lin, 1991). Alternatively, arbitrarily tight bounds on performance can be constructed using sinusoidal or hyperbolic

1

approximations (Avi-Itzhak and Diep, 1996, Hashlamoun et al., 1994). These bounds
are functions of the unknown class-dependent feature distributions.
Recently, Berisha et al. (2016) introduced a divergence measure belonging to the
family of f -divergences which tightly bounds the Bayes error rate in the binary classification problem. The bounds on the BER obtained with this measure are tighter than
bounds derived from the Bhattacharyya or Chernoff bounds. Moreover, this divergence
measure can be estimated nonparametrically from the data without resorting to density
estimates of the distribution functions. Inspired by the Friedman-Rafsky multivariate
runs test (Friedman and Rafsky, 1979), estimation is based on computing the Euclidean
minimal spanning tree (MST) of the data, which can be done in approximately O(n log n)
time. In this paper we propose improvements to this estimator for problems when there
are unequal class priors and apply the improved estimator to the adaptive design of a
hierarchical multiclass classifier. Furthermore, a fast method is proposed for bounding
the Bayes error rate of individual classes which only requires computing a single minimal spanning tree over the entire set of samples. Thus our proposed method is faster
than competing methods that use density plug-in estimation of divergence or observed
misclassification rates of algorithms, such as SVM or logistic regression, which involve
expensive parameter tuning.
Quantifying the complexity of a classification problem has been of significant interest (Ho and Basu, 2002) and it is clear that a fast and accurate estimate of this
complexity has many practical applications. For instance, an accurate complexity estimator allows the researcher to assess a priori whether a given classification problem is
difficult to classify or not. In a multiclass problem, a pair of classes which are difficult
to disambiguate could potentially be merged or could be designated for additional data
collection. Moreover, an accurate estimate of the BER could be used for variable selection, an application that was explored previously in Berisha et al. (2016). In Section 3
further applications of the BER estimates to multiclass classification are presented and
evaluated.
There are many methods available for the design of multiclass classification algorithms, including: logistic regression (Cox, 1958); support vector machines (Cortes and
Vapnik, 1995); and neural networks (McCulloch and Pitts, 1943). It is often the case
that classifier performance will be better for some classes than for others, for instance
due to sample imbalance in the training set. Often classifier designs apply weights to
the different classes in order to reduce the effect of such imbalances on average classifier
accuracy (Lu et al., 1998, Qiao and Liu, 2009). We take a different and more general approach that incorporates an empirical determination of the relative difficulties of
classifying between different classes. Accurate empirical estimates of the BER are used
for this purpose. A multiclass classifier is presented in Section 4 that uses MST-based
BER estimates to create a hierarchy of binary subproblems that increase in difficulty
as the algorithm progresses. This way, the classifier initially works on easily decidable
subproblems before moving on to more difficult multiclass classification problems.
The paper is organized as follows. The theory of the nonparametric Bayes error
estimator of Berisha et al. (2016) will be reviewed in Section 2. We will introduce a bias
correction for this estimator, motivate the use of the estimator for multiclass classification, and discuss computational complexity. Section 3 will introduce applications of the
estimator to meta-learning in multiclass classification. A novel hierarchical classification
method will be introduced and evaluated in Section 4. Section 5 provides concluding
remarks.

2

2

An Improved BER Estimator

Here the motivation and theory for the estimator of the Bayes error rate is reviewed,
as introduced by Berisha et al. (2016). An improvement on this estimator is proposed
for the case where class prior probabilities are unequal. Next, the application of the
estimator in multiclass classification problems is considered. Finally, computational
considerations and robustness analyses are presented.

2.1

Estimating the Bayes Error Rate

Consider the binary classification problem on a dataset D = {(xi , yi )}i=1,...,n , where
xi ∈ X ⊆ Rd and yi ∈ {1, 2}. Denote the multivariate density functions for the two
classes by f1 (x) and f2 (x) and the prior probabilities by p1 and p2 = 1−p1 , respectively.
The Bayes error rate of this binary classification problem can be expressed as (Fukunaga,
1990)
Z
Pe (f1 , f2 ) =

min {p1 f1 (x), p2 f2 (x)} dx.

(1)

Recently, Berisha et al. (2016) derived a tight bound on the BER which can be
estimated directly from the data without a parametric model for the density or density
estimation. This bound is based on a divergence measure introduced by Berisha and
Hero (2015), defined as
"Z
#
1
(p1 f1 (x) − p2 f2 (x))2
DHP (f1 , f2 ) =
dx − (p1 − p2 )2 ,
(2)
4p1 p2
p1 f1 (x) + p2 f2 (x)
and called the Henze-Penrose divergence, as it is motivated by an affinity measure defined
by Henze and Penrose (1999). In Berisha and Hero (2015) it was shown that (2) is a
proper f -divergence as defined by Csiszár (1975).
Estimation of the Henze-Penrose (HP) divergence is based on the multivariate runs
test proposed by Friedman and Rafsky (1979) and convergence of this test was studied
by Henze and Penrose (1999). Let Xk = {xi ∈ X ⊆ Rd : yi = k} with k ∈ {1, 2} denote
multidimensional features from two classes. Define the class sample sizes nk = |Xk |,
k ∈ {1, 2}. Let the combined sample be denoted by X = X1 ∪X2 where n = |X| = n1 +n2
is the total number of samples from both classes. Define the complete graph G over X
as the graph connecting all n nodes {xi }ni=1 with edge weights |ekj | = kxk − xj k equal
to Euclidean distances. The Euclidean minimal spanning tree that spans X, denoted
by T , is defined as the subgraph of G that is both connected and whose sum of edge
weights is the smallest possible. The Friedman-Rafsky test statistic equals the number
of edges in T that connect an observation from class 1 to an observation from class 2
and is denoted by R1,2 .
Building on the work by Henze and Penrose (1999), Berisha et al. (2016) show that
if n1 → ∞ and n2 → ∞ in a linked manner such that n1 /(n1 + n2 ) → δ ∈ (0, 1) then,
1−

nR1,2
→ DHP (f1 , f2 )
2n1 n2

a.s.

(3)

Thus, the number of cross connections between the classes in the Euclidean MST is
inversely proportional to the divergence between the respective probability density functions of these classes.
Finally, the HP-divergence can be used to bound the Bayes error rate, Pe (f1 , f2 ),
following Theorem 2 of Berisha et al. (2016)
p
1
1
uHP (f1 , f2 ) ≤ Pe (f1 , f2 ) ≤ 21 − 12 uHP (f1 , f2 ),
(4)
2 − 2
3

0.6

0.6
BER, p = 0.15

P̂e , p = 0.33
PBC , p = 0.33

0.4
0.3
0.2
0.1
0

P̂e , p = 0.15
PBC , p = 0.15
BER, p = 0.33

0.5
Error Probability

0.5
Error Probability

BER, p = 0.15

P̂e , p = 0.15
PBC , p = 0.15
BER, p = 0.33

P̂e , p = 0.33
PBC , p = 0.33

0.4
0.3
0.2
0.1

0

1

2
3
Distance

4

0

5

(a) without bias correction

0

1

2
3
Distance

4

5

(b) with bias correction

Figure 1: Illustration of the estimates of the Bayes error rate for two different values
of the prior probability p and for spherical bivariate Gaussian distributions with increasing separation between the classes as measured by Euclidean distance between the
class means, kµ1 − µ2 k. We compare the true BER, the Bhattacharyya bound (PBC )
requiring the true class distributions, and the HP-estimator (P̂e ) based on an empirical
sample. Figures (a) and (b) show the estimates for p = 0.15 and p = 1/3, respectively
with and without the proposed bias correction of the HP-estimator. The HP-estimator
was implemented using n = 1000 samples (n1 = pn and n2 = n − n1 ) and averaged over
200 trials.
where
uHP (f1 , f2 ) = 4p1 p2 DHP (f1 , f2 ) + (p1 − p2 )2 .
Averaging these bounds yields an estimate of the BER given by
p
P̂e (f1 , f2 ) = 21 − 41 uHP (f1 , f2 ) − 14 uHP (f1 , f2 ).

(5)

(6)

In the following, this estimator will be referred to as the HP-estimator of the BER.

2.2

A modified HP-estimator for unequal class priors

To illustrate the performance of the HP-estimator, and to motivate the proposed modification, consider a binary classification problem where the samples are drawn from two
independent bivariate Gaussian distributions with equal covariance matrices. For this
example the BER and associated bounds can be computed exactly (Fukunaga, 1990).
In Figure 1a we compare the BER, the HP-estimator of the BER (6) and the popular
Bhattacharyya bound on the BER (Bhattacharyya, 1946, Kailath, 1967). Figure 1a
shows that the HP-estimator is closer to the true BER than the Bhattacharyya bound.
This result was illustrated by Berisha et al. (2016) for the case where p1 = p2 and is
confirmed here for the case where p1 6= p2 .
However, Figure 1a also shows that a significant bias occurs in the HP-estimate of
the BER when the distance between classes is small. Considering that Pe (f1 , f2 ) =
4

min{p1 , p2 } if f1 → f2 , the solution of the equation P̂e (f1 , f2 ) = min{p̂1 , p̂2 } for R1,2
suggests a bias corrected version of the HP-estimate:1
0
R1,2
= min{γ, R1,2 },

(7)

with
γ = 2n min{p̂1 , p̂2 } − 43 n + 14 n

p
9 − 16 min{p̂1 , p̂2 },

(8)

where p̂1 = n1 /n and p̂2 = n2 /n are estimates of the true prior probabilities. Figure 1b
shows the effect of this bias correction on the accuracy of the HP-estimator. As can
be seen, the bias correction significantly improves the accuracy of the HP-estimator for
when the class distributions are not well separated.

2.3

Multiclass classification

Here we apply the HP-estimate to multiclass classification problems by extending the
bias corrected HP-estimator to a multiclass Bayes error rate. The original multiclass
HP-estimator has been defined by Wisler et al. (2016) and we show how the framework
can be applied to hierarchical multiclassifier design.
Consider a multiclass problem with K classes with xi ∈ X ⊆ Rd and yi ∈ {1, . . . , K},
with
P prior probabilities pk and density functions fk (x) for k = 1, . . . , K such that
k pk = 1. Then, the BER can be estimated for each pair of classes using the biascorrected HP-estimator P̂e (fk , fj ) using (7). The binary classification problem with the
largest BER estimate is defined as most difficult.
Recall that the largest BER that can be achieved in a binary classification problem
with unequal class priors is equal to the value of the smallest prior probability. This
makes it difficult to compare empirical estimates of the BER when class sizes are imbalanced. To correct for this, the HP-estimator for pairwise classification BERs can be
normalized for class sizes using
P̂e0 (fk , fl ) =

P̂e (fk , fl )
.
min{p̂k , p̂l }

(9)

This normalization places the HP-estimate in the interval [0, 1] and makes it possible to
more accurately compare the BER estimates of different binary problems.
In practice it can also be of interest to understand how difficult it is to discriminate
each individual class. By reducing the multiclass problem to a One-vs-Rest classification
problem, it is straightforward to define a confusion rate for a given class k. This represents the fraction of instances that are erroneously assigned to class k and the fraction
of instances which are truly from class k that are assigned to a different class. Formally,
define the confusion rate for class k as
|{i : ŷi = k, yi 6= k}| + |{i : ŷi 6= k, yi = k}|
Ck (y, ŷ) =
,
(10)
n
with ŷi the predicted class for instance i. Recall that the Bayes error rate is the error
rate of the Bayes classifier, which assigns an instance x to class k = arg maxl pl fl (x).
Hence, the BER for a single class k equals the error of assigning to a class l 6= k when
the true class is k and the total error of assigning to class k when the true class is c 6= k,
thus
Z
Z
X
Pe,k =
pk fk (x) dx +
pc fc (x) dx
(11)
c6=k

max{pl fl (x)}≥pk fk (x)
l6=k

max{pl fl (x)}<pk fk (x)
l6=k

1
This correction can readily be derived by using the fact that 1 −
under the same conditions as for (3).

5

2R1,2
n

→ uHP (f1 , f2 ), which holds

·10−4
1
2
3
5
7
11

2.5

Variance

2
1.5
1
0.5
0
0

1

2

3

4

5

Distance

Figure 2: Variance of the HP-estimator of the BER for varying number of orthogonal
MSTs as a function of the separation between the classes. Results are based on 500
repetitions of a binary classification problem with n = 1000, d = 2, p1 = 0.33, where
class distributions are bivariate spherical Gaussians with different means.
We make two observations about this One-vs-Rest Bayes error rate (OvR-BER).
First, the OvR-BER for class k is smaller than the sum of the binary BERs for the
problems involving class k (see Appendix A). Second,
the OvR-BER can be estimated
S
using the Henze-Penrose divergence with R(Xk , l6=k Xl ), which yields the estimate P̂e,k .
A computational advantage of using the OvR-BER in multiclass problems is that the
MST only has to be computed only
S once on the set X, since the union of Xk and ∪l6=k Xl
is equal to X. Therefore, R(Xk , l6=k Xl ) can be computed for all k from the single MST
on X by keeping track of the labels of each instance.

2.4

Computational Considerations

The construction of the minimal spanning tree lies at the heart of the HP-estimator of
the BER, so it is important to use a fast algorithm for the MST construction. Since
the HP-estimator is based on the Euclidean MST the dual-tree algorithm by March
et al. (2010) can be applied. This algorithm is based on the construction of Borůvka
(1926) and implements the Euclidean MST in approximately O(n log n) time. For larger
datasets it can be beneficial to partition the space into hypercubes and construct the
MST in each partition.
A simple way to improve the robustness of the HP-estimator is to use multiple
orthogonal MSTs and average the number of cross-connections (Friedman and Rafsky,
1979). Computing orthogonal MSTs is not straightforward in the dual-tree algorithm
of March et al. (2010), but is easy to implement in MST algorithms that use a pairwise
distance matrix such as that of Whitney (1972). Figure 2 shows the empirical variance
of the HP-estimator for different numbers of orthogonal MSTs as a function of the
separation between the classes. As expected, the variance decreases as the number of
orthogonal MSTs increases, although the benefit of including more orthogonal MSTs
also decreases when adding more MSTs. Therefore, 3 orthogonal MSTs are typically
used in practice.

6

0

1

2

3

4

5

6

7

8

9

0

0

0

1

1

2

2

3

3

4

4

5

5

6

6

7

7

8

8

9

9
(a)

1

2

3

4

5

6

7

8

9

(b)

Figure 3: Heat maps illustrating the difficulty of distinguishing between different handwritten digits in the MNIST dataset of LeCun et al. (1998). Brighter squares correspond
to higher values. In (a) the heat map of the BER estimates on the training data is shown.
In (b) the heat map is shown of the 82 misclassifications made by LeNet-5 on the test
data (LeCun et al., 1998). From (a) it can be readily identified that the numbers 3 and
5 are difficult to distinguish, as well as 4 and 9. Easy to distinguish number pairs are
for instance 6 and 7, and 0 and 1. This pattern is reflected in the results on the test
data shown in (b).

3

Meta-Learning of optimal classifier accuracy

Applying the HP-estimator to meta-learning problems creates a number of opportunities
to assess the difficulty of a classification problem before training a classifier. For example, given a multiclass classification problem it may be useful to know which classes
are difficult to distinguish from each other and which classes are easy to distinguish.
Figure 3a shows an illustration of this for handwritten digits in the well-known MNIST
dataset (LeCun et al., 1998). This figure shows a heat map where each square corresponds to an estimate of the BER for a binary problem in the training set. From this
figure it can be seen that the digits 4 and 9 are difficult to distinguish, as well as the
digits 3 and 5. This information can be useful for the design of a classifier, to ensure for
instance that higher weights are placed on misclassifications of the more difficult number
pairs if correct classification of these pairs is of importance to the end-task. In Figure 3b
a similar heat map is shown based on misclassified instances of LeNet-5 (LeCun et al.,
1998) on the test set. This figure shows the symmetric confusion matrix based on the
82 misclassified instances. As can be seen, this figure closely corresponds to the heat
map on the training data, which confirms the predictive accuracy of the HP-estimator
for real data.
Another example of the accuracy of the BER estimates for multiclass classification
problems is given in Figure 4. In this figure, OvR-BER estimates P̂e,k and class accuracy scores Ck (y, ŷ) are shown for the Chess dataset (n = 28056, d = 34, K = 18)
obtained from the UCI repository (Bache and Lichman, 2013). This dataset was split
into a training dataset (70%) and a test dataset (30%) and the OvR-BER estimates
were computed on the training dataset. These estimates are compared with the class
error rates obtained from out-of-sample predictions of the test dataset using GenSVM
(Van den Burg and Groenen, 2016). This figure shows that the OvR-BER estimates are
accurate predictors of classification performance. The classes that are relatively difficult
7

class error rate

0.2
0.15
0.1
0.05
0

1

2

3

4

5

6

7

8 9 10 11 12 13 14 15 16 17 18
class index
Ck (y, ŷ)
P̂e,k

Figure 4: OvR-BER estimates and test set error rates for each class in the Chess
dataset. It can be seen that for most classes the OvR-BER estimate is an accurate
predictor for test set performance. For classes where there is a difference between the
BER and the test set error the BER generally gives a lower bound on the test set
performance. Test set results were obtained with the GenSVM classifier (Van den Burg
and Groenen, 2016).
to classify may benefit from increasing misclassification weights.
The BER estimates can also be applied to feature selection and, in particular, to
the identification of useful feature transformations of the data. A feature selection
strategy based on forward selection was outlined in Berisha et al. (2016). At each
feature selection stage, this algorithm adds the feature which gives the smallest increase
in the BER estimate. Berisha et al. (2016) show that this feature selection strategy
quickly yields a subset of useful features for the classification problem.
Because the BER estimate is a fast and asymptotically consistent estimate of a
bound on classification performance, it is easy to try a number of potential feature
transformations and use the one with the smallest BER estimate in the classifier. This
can be useful both for traditional feature transformations such as PCA (Pearson, 1901)
and Laplacian Eigenmaps (Belkin and Niyogi, 2003), but also for commonly used kernel
transformations in SVMs. For a researcher this can significantly reduce the time needed
to train a classifier on different transformations of the data. In a multiclass setting where
the One-vs-One strategy is used, one can even consider a different feature transformation
for each binary subproblem. When using a unified classification method one can consider
feature transformations which reduce the average BER estimate or the worst-case BER
estimate.
Note that a feature transformation which reduces the dimensionality of the dataset
without increasing the BER estimate can be considered beneficial, as many classification
methods are faster for low-dimensional datasets. For instance, applying PCA with 2
components on the Chess dataset only slightly increases the BER estimates for two
classes, while remaining the same for the other classes. Thus, a classifier will likely
achieve comparable accuracy with this transformed dataset, but will be much faster to
train since the dimensionality can be reduced from d = 34 to d = 2.

4

Hierarchical Multiclass Classification

In this section a novel hierarchical multiclass SVM classifier is introduced which is based
on uncertainty clustering. The BER estimate can be considered a measure of the irre-

8

1

1

cut
7

2

7

2

cut
6

3

5

4

6

V

V0

(a)

3

cut

5

4

V1

(b)

Figure 5: Illustration of the min-cut procedure for a multiclass classification problem
with K = 7 classes. The first cut in (a) splits the vertices in the set V into two sets, V0
and V1 , which are used in a binary classifier. Figure (b) illustrates the next step where
both V0 and V1 are split further by cuts in the complete graph for each subset.
ducible uncertainty of a classification problem, as a high BER indicates an intrinsically
difficult problem. This can be used to construct a tree of binary classification problems
that increase in difficulty along the depth of the tree. By fitting a binary classifier (such
as an SVM) at each internal node of the tree, a classification method is obtained which
proceeds from the easier binary subproblems to the more difficult binary problems.
Similar divide-and-conquer algorithms have been proposed (Frank and Kramer, 2004,
Schwenker and Palm, 2001, Takahashi and Abe, 2002, Tibshirani and Hastie, 2007, Vural
and Dy, 2004, among others). See Lorena et al. (2008) for a review. These approaches
often apply a clustering method to create a grouping of the dataset into two clusters,
repeating this process recursively to form a binary tree of classification problems. In
Lorena and De Carvalho (2010) several empirical distance measures are used as indicators of separation difficulty between classes, which are applied in a bottom-up procedure
to construct a classification tree. Finally, in El-Yaniv and Etzion-Rosenberg (2010) the
Jensen-Shannon divergence is used to bound the BER with inequalities from Lin (1991)
and a classification tree is constructed using a randomized heuristic procedure. Unfortunately, the Jensen-Shannon divergence implementation requires parametric estimation
of distribution functions. Moreover, for the equiprobable case the upper bound on the
BER obtained with the Jensen-Shannon divergence can be shown to be less tight than
that obtained with the HP-divergence (see Appendix B). Because of this, these estimates
of the BER may be less accurate than those obtained with the proposed HP-estimator.
To construct the hierarchical classification tree a complete weighted graph G =
(V, E, w) is created where the vertices correspond to the classes and the weight of the
edges equals the HP-estimate for that binary problem. Formally, let V = {1, . . . , K},
E = {(i, j) : i, j ∈ V, i 6= j} and define the edge weight w(e) for e ∈ E as w(e) =
w(i, j) = P̂e0 (fi , fj ). In the HP-estimator P̂e0 (fi , fj ) the bias correction (7) and the
normalization (9) are used. By recursively applying min-cuts to this graph a tree of
binary classification problems is obtained which increase in difficulty along the depth
of the tree. Min-cuts on this weighted graph can be computed using for instance the
method of Stoer and Wagner (1997). Figure 5 illustrates this process for a multiclass
classification problem with K = 7.
9

V
{1, 2, 3, 4, 5, 6, 7}
V0
{2, 3, 4}
V00
{2}

V1
{1, 5, 6, 7}
V01
{3, 4}

V010
{3}

V10
{1, 7}
V011
{4}

V100
{1}

V11
{5, 6}
V101
{7}

V110
{5}

V111
{6}

Figure 6: Illustration of the tree induced by the graph cutting procedure illustrated in
Figure 5, for a hypothetical problem with K = 7 classes. Each dashed line in the tree
indicates a point where a binary classifier will be trained.
The tree construction can be described formally as follows. Starting with the complete weighted graph with vertices V , apply a min-cut algorithm to obtain the disjoint vertex sets V0 and V1 such that V0 ∪ V1 = V . This pair of vertex sets then
forms a binary classification problem with datasets X0 = {xi ∈ X : yi ∈ V0 } and
X1 = {xi ∈ X : yi ∈ V1 }. Recursively applying this procedure to the sets V0 and
V1 until no further splits are possible yields a tree of binary classification problems, as
illustrated in Figure 6.
In the remainder of this section the results of an extensive simulation study are presented, which aims to evaluate the performance of this hierarchical classifier on multiclass
classification problems. The classifier that will be used in each binary problem in the
tree will be a linear support vector machine, but in practice any binary classifier could
be used in the algorithm. The implementation of the hierarchical classifier based on the
linear binary SVM will be called SmartSVM.2
The experimental setup is comparable to that used in Van den Burg and Groenen
(2016), where a nested cross-validation (CV) approach is used to reduce bias in classifier
performance (Stone, 1974). From each original dataset 5 independent training and test
datasets are generated. Subsequently, each classification method is trained using 10
fold CV on each of the training datasets. Finally, the model is retrained on the entire
training dataset using the optimal hyperparameters and this model is used to predict
the test set. In the experiments 16 datasets are used of varying dimensions from which
80 independent test sets are constructed. The train and test datasets were generated
using a stratified split, such that the proportions of the classes correspond to those in
the full dataset. Table 1 shows the descriptive statistics of each of the datasets used.
Datasets are collected from the UCI repository (Bache and Lichman, 2013) and the
KEEL repository (Alcalá et al., 2010).
SmartSVM will be compared to five other linear multiclass SVMs in these experiments. Three of these alternatives are heuristic methods which use the binary SVM
as underlying classifier, while two others are single-machine multiclass SVMs. One of
the most commonly used heuristic approaches to multiclass SVMs is the One vs. One
(OvO) method (Kreßel, 1999) which solves a binary SVM for each of the K(K − 1) pairs
of classes. An alternative is the One vs. Rest (OvR) method (Vapnik, 1998) in which
2

The SmartSVM classifier and the meta-learning and BER estimation techniques presented in the
previous sections have been implemented in the smartsvm Python package, available at: https://
github.com/HeroResearchGroup/SmartSVM.

10

Table 1: Dataset summary statistics for the datasets used in the experimental study.
The final two columns denote the size of the smallest and the largest class, respectively.
Datasets marked with an asterisk are collected from the KEEL dataset repository, all
others are from the UCI repository.
Dataset
abalone
fars*
flare
kr-vs-k
letter
nursery
optdigits
pageblocks
pendigits
satimage
segment
shuttle
texture*
wine red
wine white
yeast

Instances
4177
100959
1066
28056
20000
12960
5620
5473
10992
6435
2310
58000
5500
1599
4898
1479

Features
8
338
19
34
16
19
64
10
16
36
19
9
40
12
12
8

Classes
20
7
6
18
26
4
10
5
10
6
7
6
11
5
6
9

min nk
14
299
43
27
734
330
554
28
1055
626
330
23
500
18
20
20

max nk
689
42116
331
4553
813
4320
572
4913
1144
1533
330
45586
500
681
2198
463

a binary SVM is solved for each of the K − 1 binary problems obtained by separating
a single class from the others. The directed acyclic graph (DAG) SVM was proposed
by Platt et al. (2000) as an extension of the OvO approach. It has a similar training
procedure as OvO, but uses a different prediction strategy. In the OvO method a voting
scheme is used where the class with the most votes from each binary classifier becomes
the predicted label. In contrast, the DAGSVM method uses a voting scheme where
the least likely class is voted away until only one remains. Finally, two single-machine
multiclass SVMs are also compared: the method by Crammer and Singer (2002) and
GenSVM (Van den Burg and Groenen, 2016).
All methods are implemented in either C or C++, to ensure that speed of the methods
can be accurately compared. The methods that use a binary SVM internally are implemented with LibLinear (Fan et al., 2008). LibLinear also implements a fast solver for the
method by Crammer and Singer (2002) using the algorithm proposed by Keerthi et al.
(2008). For SmartSVM the Bayes error rates and the corresponding classification tree
were calculated once for each training dataset as a preprocessing step. For most datasets
the BERs were computed based on 3 orthogonal MSTs using the algorithm of Whitney
(1972). For the two largest datasets (fars and shuttle) the BER was computed based on
a single MST using the algorithm of March et al. (2010). Computing these MSTs was
done in parallel using at most 10 cores. In the results on training time presented below
the training time of SmartSVM is augmented with the preprocessing time.
The binary SVM has a cost parameter for the regularization term, which is optimized
using cross validation. The range considered for this parameter is C ∈ {2−18 , 2−16 , . . . , 218 }.
The GenSVM method has additional hyperparameters which were varied in the same
way as in the experiments of Van den Burg and Groenen (2016). All experiments were

11

Table 2: Total training time per dataset in seconds, averaged over the 5 nested CV folds.
Minimal values per dataset are underlined. As can be seen, SmartSVM is the fastest
method on 10 out of 16 datasets.
Dataset
abalone
fars
flare
krkopt
letter
nursery
optdigits
pageblocks
pendigits
satimage
segment
shuttle
texture
winered
winewhite
yeast

C&S
13332
158242
467.5
86000
31684
2267
88.0
523.4
2499
5184
377.1
7658
588.1
706.4
2570
1209

DAG
146.5
3108
7.0
728.4
407.3
74.7
20.0
26.8
30.2
74.7
7.1
570.8
34.5
12.3
59.2
16.7

GenSVM
86787
205540
501.7
56554
44960
1363
31615
2001
6591
2563
1542
14618
14774
542.7
2570
1138

OvO
134.3
2866
6.5
680.4
381.5
68.7
18.5
25.2
28.5
70.0
7.0
561.9
32.8
11.1
55.1
15.3

OvR
214.4
5630
8.2
1388
1805
94.9
24.3
48.6
151.3
188.4
18.7
1996
69.6
18.3
70.9
24.2

SmartSVM
75.0
3158
5.0
664.0
652.1
56.8
10.9
27.6
53.7
74.5
5.4
832.0
19.3
8.8
36.7
13.2

performed on the Dutch National LISA Compute Cluster using the abed utility.3
The experiments are compared on training time and out-of-sample predictive performance. Table 2 shows the results for training time, averaged over the 5 nested cross
validation folds for each dataset. As can be seen SmartSVM is the fastest method on
10 out of 16 datasets. This can be attributed to the smaller number of binary problems
that SmartSVM needs to solve compared to OvO and the fact that the binary problems
are smaller than those solved by OvR. The OvO method is the fastest classification
method on the remaining 6 datasets. The single-machine multiclass SVMs by Crammer
and Singer (2002) and Van den Burg and Groenen (2016) both have larger computation
times than the heuristic methods. Since GenSVM has a larger number of hyperparameters, it is interesting to look at the average time per hyperparameter configuration as
well. In this case, GenSVM is on average faster than Crammer and Singer (2002) due
to the use of warm starts (see Appendix C for additional simulation results).
Classification performance of the methods is reported using the adjusted Rand index
(ARI) which corrects for chance (Hubert and Arabie, 1985). Use of this index as a classification metric has been proposed previously by Santos and Embrechts (2009). Table 3
shows the predictive performance as measured with the ARI. As can be seen, SmartSVM
obtains the maximum performance on two of the sixteen datasets. However, SmartSVM
outperforms One vs. One on 3 datasets and outperforms One vs. Rest on 10 out of 16
datasets. The OvO and OvR methods are often used as default heuristic approaches
for multiclass SVMs and are respectively the default strategies in the popular LibSVM
(Chang and Lin, 2011) and LibLinear (Fan et al., 2008) libraries. Since SmartSVM is
often faster than these methods, our results indicate a clear practical benefit to using
SmartSVM for multiclass classification.
3

See https://github.com/GjjvdBurg/abed.

12

Table 3: Out-of-sample predictive performance as measured by the adjusted Rand index.
Although SmartSVM doesn’t often achieve the maximum performance, there are several
datasets for which SmartSVM outperforms One vs. One, or differs from the maximum
performance in only the second or third decimal.
Dataset
abalone
fars
flare
krkopt
letter
nursery
optdigits
pageblocks
pendigits
satimage
segment
shuttle
texture
winered
winewhite
yeast

5

C&S
0.0788
0.8127
0.4274
0.1300
0.6173
0.8279
0.9721
0.7681
0.9068
0.7420
0.9013
0.9275
0.9936
1.0000
1.0000
0.2595

DAG
0.0898
0.8143
0.6480
0.1988
0.6991
0.8175
0.9854
0.7335
0.9566
0.7652
0.9000
0.8543
0.9950
1.0000
1.0000
0.2540

GenSVM
0.0895
0.8085
0.6687
0.1779
0.5909
0.8303
0.9732
0.6847
0.8971
0.7403
0.8812
0.8887
0.9888
0.9985
0.9998
0.2521

OvO
0.0898
0.8146
0.6496
0.2022
0.7118
0.8157
0.9850
0.7353
0.9597
0.7672
0.8982
0.8543
0.9947
1.0000
1.0000
0.2587

OvR
0.0791
0.8134
0.4084
0.1512
0.5155
0.8095
0.9686
0.6696
0.8607
0.7107
0.8354
0.6925
0.9865
0.8369
0.8131
0.2433

SmartSVM
0.0595
0.8115
0.6544
0.1585
0.4533
0.8138
0.9640
0.7214
0.8817
0.7607
0.8986
0.8038
0.8977
1.0000
1.0000
0.2088

Discussion

In this work the practical applicability of nonparametric Bayes error estimates to metalearning and hierarchical classifier design has been investigated. For the BER estimate
introduced by Berisha et al. (2016) a bias correction was derived which improves the
accuracy of the estimator for classification problems with unequal class priors. Furthermore, a normalization term was proposed which makes the BER estimates comparable
in multiclass problems. An expression of the OvR-BER was given which represents the
exact Bayes error for a single class in the multiclass problem and it was shown that this
error can be efficiently estimated using the HP-estimator as well. A robustness analysis
of the HP-estimator was performed which showed the benefit of using orthogonal MSTs
in the estimator.
There are many potential applications of the BER estimates to meta-learning problems. Above, several possibilities were explored including the prediction of which pairs of
classes are most difficult to distinguish and which individual classes will yield the highest
error rate. Preliminary experiments with feature transformations were also performed,
which showed that the BER estimates can be a useful tool in determining beneficial
transformations before a classifier is trained.
Based on the weighted graph of pairwise BER estimates, a hierarchical multiclass
classification method was proposed. The classifier uses a top-down splitting approach
to create a tree of binary classification problems which increase in difficulty along the
depth of the tree. By using a linear SVM for each classification problem, a hierarchical
multiclass SVM was obtained which was named SmartSVM. Extensive simulation studies
showed that SmartSVM is often faster than existing approaches and yields competitive
predictive performance on several datasets.
Note that the SmartSVM classifier is only one example of how the BER estimates
13

can be used to construct better classification methods. As discussed in Section 3, BER
estimates could also be used to define class weights in a multiclass classifier. Moreover,
the min-cut strategy used for SmartSVM may not be the optimal way to construct the
classification tree. Evaluating different approaches to constructing classification hierarchies and other applications of the BER estimates to multiclass classification problems
are topics for further research.

Acknowledgements
The computational experiments of this work were performed on the Dutch National LISA
Compute Cluster, and supported by the Dutch National Science Foundation (NWO).
The authors thank SURFsara (www.surfsara.nl) for the support in using the LISA
cluster. This research was partially supported by the US Army Research Office, grant
W911NF-15-1-0479 and US Dept. of Energy grant DE-NA0002534.

A

One vs. Rest Bayes Error Rate

In this section bounds for the One vs. Rest Bayes error rate will be derived, which
measures the error of the Bayes classifier in correctly identifying an individual class.
Definition 1 (OvR-BER). Let f1 , f2 , . . . , fK and p1 , p2 , . . . , pK denoteP
density functions
and prior probabilities for the classes 1 through K respectively, with c pc = 1. Then,
the Bayes error rate between a class k and the remaining classes is given by
Z
Z
X
Pe,k =
pk fk (x) dx +
pc fc (x) dx.
(12)
c6=k

max{pl fl (x)}≥pk fk (x)
l6=k

max{pl fl (x)}<pk fk (x)
l6=k

Below it will be shown that the OvR-BER can
S be bounded using the FriedmanRafsky statistic in the One-vs-Rest setting, R(Xk , l6=k Xl ). Let the mixture distribution of the classes l 6= k be given by
P
l6=k pl fl (x)
gk (x) = P
,
(13)
l6=k pl
P
S
with prior probability pg = l6=k pl . Then Xgk = l6=k Xl can be seen as a draw from
this mixture distribution. By Theorem 2 of Berisha et al. (2016) it holds that
Z
p
1
1
u(fk , gk ) ≤ min{pk fk (x), pg gk (x)} dx ≤ 12 − 12 u(fk , gk ).
(14)
2 − 2
The following theorem relates this error to the OvR-BER defined above.
Theorem 2. The error rate between class k and the mixture distribution without class
k is bounded from above by the OvR-BER,
Z
Qe,k = min{pk fk (x), pg gk (x)} dx ≤ Pe,k .
(15)
Proof. Note that

Z
Qe,k =

Z
pk fk (x) dx

pk fk (x)≤pg gk (x)

+

pg gk (x) dx.

pk fk (x)>pg gk (x)

14

(16)

To simplify the notation, introduce the sets
n
o
T = x ∈ Rd : pk fk (x) ≤ pg gk (x)


d
S = x ∈ R : pk fk (x) ≤ max{pl fl (x)}

(17)

and denote their respective complements by T 0 and S 0 . Then,
Z
Z
pg gk (x) dx
pk fk (x) dx +
Qe,k =
0
T
T
Z
Z
pg gk (x) dx.
pk fk (x) dx +
Pe,k =

(19)

l6=k

P

l6=k

pl fl (x) ≤ maxl6=k pl fl (x) it holds that S ⊆ T and T 0 ⊆ S 0 . Hence,

Z

Z
pk fk (x) dx =

Z
pk fk (x) dx +

T

pk fk (x) dx
Z

Z
pg gk (x) dx =

T0

(21)

T \S

S

Z
S0

(20)

S0

S

Since pg gk (x) =

(18)

pg gk (x) dx +

S 0 \T 0

pg gk (x) dx

However, the sets T \ S and S 0 \ T 0 both equal


d
U = x ∈ R : max{pl fl (x)} < pk fk (x) ≤ pg gk (x) ,
l6=k

(22)

(23)

so it follows that
Z
Qe,k = Pe,k +
U

pk fk (x) dx −

Z
U

pg gk (x) dx ≤ Pe,k

(24)

by definition of the set U .
This provides a lower bound for Pe,k in terms of u(fk , gk ). What remains to be
shown is that Pe,k has an upper bound in terms of u(fk , gk ). No such bound has yet
been found. However, the following result can be presented which does bound Pe,k from
above.
Theorem 3. For a single class k the OvR-BER is smaller than or equal to the sum of
the pairwise BER estimates involving class k.
Proof. Recall that the OvR-BER for class k is given by
Z
X
Pe,k =
pk fk (x) dx +

Z

pc fc (x) dx,
c6=k
pk fk (x)>max{pl fl (x)}

pk fk (x)≤max{pl fl (x)}
l6=k

(25)

l6=k

and denote the sum of the pairwise BERs involving k as Fe,k given by,
XZ
Fe,k =
min{pk fk (x), pc fc (x)} dx

(26)

c6=k

=

X

Z

pk fk (x) dx
c6=k
pk fk (x)<pc fc (x)
15

+

X

Z

pc fc (x) dx.
c6=k
pk fk (x)>pc fc (x)

(27)

Then comparing the first term of Fe,k with that of Pe,k shows
Z
X Z
pk fk (x) dx,
pk fk (x) dx ≥
c6=k
pk fk (x)<pc fc (x)

(28)

pk fk (x)≤max{pl fl (x)}
l6=k

since the area of integration on the left is larger than on the right. Similarly,
X Z
X Z
pc fc (x) dx
pc fc (x) dx ≥

(29)

c6=k
pk fk (x)>max{pl fl (x)}

c6=k
pk fk (x)>pc fc (x)

l6=k

for the same reason. This completes the proof.

B

Jensen-Shannon Bound Inequality

In this section a proof is given for the statement that the Henze-Penrose upper bound
on the Bayes error rate is tighter than the Jensen-Shannon upper bound derived by Lin
(1991). Before presenting the proof, the following lemma is presented.
Lemma 4. For x, y > 0 it holds that


y
x
4 log(2)xy
x log 1 +
+ y log 1 +
≥
.
x
y
x+y


Proof. Let t =

y
x

(30)

and multiply both sides by 1t + 1 > 0, then the inequality reduces to




1
1
+ 1 log (1 + t) + (1 + t) log 1 +
≥ 4 log(2).
(31)
t
t

Denote the left hand side by f (t). The proof will now proceed by showing that f (t) ≥
f (1) = 4 log(2) for all t > 0. The derivatives of f (t) are given by


1
log(1 + t)
2 log(1 + t) − t
f 0 (t) = log 1 +
−
and
f 00 (t) =
.
(32)
t
t2
t3
Write the numerator of f 00 (t) as g(t) such that
g(t) = 2 log(1 + t) − t,

and

g 0 (t) =

1−t
.
1+t

(33)

Then it is clear that g 0 (t) > 0 for 0 < t < 1 and g 0 (t) < 0 for t > 1. Furthermore
limt→0+ g(t) = 0 and limt→∞ g(t) = −∞. Thus, it follows that g(t) increases on 0 <
t < 1 and decreases for t > 1. Let t = α > 1 be such that g(α) = 0, then g(t) > 0 for
0 < t < α and g(t) < 0 for t > α.
From this it follows that f 00 (t) > 0 for 0 < t < α and f 00 (t) < 0 for t > α. Hence,
f 0 (t) is increasing on 0 < t < α and decreasing for t > α. Moreover, limt→0+ f 0 (t) = −∞
and f 0 (1) = 0. Thus, it follows that f 0 (t) is negative on 0 < t < 1, positive for t > 1,
and attains a maximum at t = α after which it decreases to limt→∞ f 0 (t) = 0. Since
limt→0+ f (t) = ∞ it follows that f (t) is decreasing on 0 < t < 1 and increasing for
t > 1.

16

Definition 5 (Kullback-Leibler Divergence). For probability density functions f1 (x)
and f2 (x) the Kullback-Leibler divergence is given by
Z
f1 (x)
DKL (f1 kf2 ) = f1 (x) log2
dx,
(34)
f2 (x)
Kullback and Leibler (1951).
Definition 6 (Jensen-Shannon Divergence). According to El-Yaniv et al. (1998) the
Jensen-Shannon divergence for two probability density functions f1 (x) and f2 (x) with
prior probabilities p1 and p2 , can be stated in terms of the Kullback-Leibler divergence
as
JS(f1 , f2 ) = p1 DKL (f1 kM ) + p2 DKL (f2 kM )
(35)
with M (x) = p1 f1 (x) + p2 f2 (x) the mixture distribution and p2 = 1 − p1 .
Theorem 7. For p1 = p2 = 21 the Henze-Penrose upper bound on the BER is tighter
than the Jensen-Shannon upper bound of Lin (1991),
Pe (f1 , f2 ) ≤

1
2

− 12 uHP ≤ 12 J,

(36)

where J = H(p1 ) − JS(f1 , f2 ) with H(p1 ) the binary entropy and JS(f1 , f2 ) the JensenShannon divergence.
Proof. First, note that with p1 = p2 = 21 the binary entropy H(p1 ) = H( 12 ) = 1. Second,
for the equiprobable case it holds that
Z
f1 (x)f2 (x)
1
1
dx.
(37)
2 − 2 uHP (f1 , f2 ) =
f1 (x) + f2 (x)
The Jensen-Shannon upper bound can be written as
Z
Z
2f1 (x)
2f2 (x)
1
1
1
1
f1 (x) log2
dx − 4 f2 (x) log2
dx
2J = 2 − 4
f1 (x) + f2 (x)
f1 (x) + f2 (x)
Z
Z
2f1 (x)
dx
= 41 f1 (x) + f2 (x) dx − 14 f1 (x) log2
f1 (x) + f2 (x)
Z
2f2 (x)
1
− 4 f2 (x) log2
dx
f1 (x) + f2 (x)


Z
2f1 (x)
1
= 4 f1 (x) 1 − log2
dx
f1 (x) + f2 (x)


Z
2f2 (x)
1
+ 4 f2 (x) 1 − log2
dx
f1 (x) + f2 (x)




Z
f2 (x)
f1 (x)
1
= 4 f1 (x) log2 1 +
+ f2 (x) log2 1 +
dx
f1 (x
f2 (x)
By Lemma 4 it follows that




f2 (x)
f1 (x)
4f1 (x)f2 (x)
f1 (x) log2 1 +
+ f2 (x) log2 1 +
≥
,
f1 (x
f2 (x)
f1 (x) + f2 (x)
and therefore
1
2J

≥

1
4

Z

4f1 (x)f2 (x)
dx =
f1 (x) + f2 (x)

17

1
2

− 12 uHP (f1 , f2 ).

(38)
(39)

(40)
(41)
(42)

(43)

(44)

Table 4: Average training time per hyperparameter configuration in seconds, averaged
over the 5 nested CV folds. Minimal values per dataset are underlined.
Dataset
C&S
DAG GenSVM
OvO
OvR SmartSVM
abalone
702
7.712
254
7.067 11.282
3.960
fars
8329
164
601
151
296
184
flare
24.606
0.369
1.467
0.344
0.431
0.263
krkopt
4526 38.337
165 35.813 73.053
35.627
letter
1668 21.438
131 20.076 94.977
34.454
nursery
119
3.932
3.985
3.617
4.994
3.133
optdigits
4.630
1.053
92.441
0.971
1.278
0.590
pageblocks 27.550
1.408
5.852
1.326
2.559
1.504
pendigits
132
1.589
19.273
1.498
7.965
2.872
satimage
273
3.931
7.494
3.685
9.918
3.942
segment
19.846
0.376
4.509
0.370
0.985
0.285
shuttle
403 30.042
42.744 29.571
105
43.928
texture
30.954
1.816
43.200
1.727
3.665
1.028
winered
37.179
0.646
1.587
0.586
0.966
0.465
winewhite
135
3.115
7.514
2.903
3.732
1.954
yeast
63.655
0.877
3.327
0.807
1.272
0.699

C

Additional Simulation Results

In this section some additional simulation results are presented for the SmartSVM experiments presented in Section 4. Table 4 shows the average time per hyperparameter
configuration for each of the methods. This is especially useful for comparing GenSVM
(Van den Burg and Groenen, 2016) with the other methods, as it has a larger set of
hyperparameters to consider.
A commonly used tool to summarize results of simulation experiments is to use rank
plots (Demšar, 2006). For each dataset the methods are ranked, with the best method
receiving rank 1 and the worst method receiving rank 6 (since there are 6 methods in
this experiment). In case of ties fractional ranks are used. By averaging the ranks over
all datasets, a visual summary of the results can be obtained. Figures 7a, 7b and 7c
show these average ranks for predictive performance, total training time, and average
training time respectively.
The ordering of OvO and SmartSVM in the rank plots for training time may seem
counterintuitive, considering that SmartSVM is more often the fastest method. This
can be explained by the fact that in the cases where SmartSVM is slower than OvO it
is usually also slower than DAG. In contrast, where SmartSVM is the fastest method
OvO is usually the second fastest method. Because of this, SmartSVM obtains a slightly
higher average rank than OvO.

18

OvO

1.0

1.5

DAG

2.0

C&S

2.5

GenSVM

3.0

3.5

SmartSVM

4.0

4.5

OvR

5.0

5.5

6.0

(a) Predictive performance
OvO

1.0

SmartSVM

1.5

2.0

DAG

2.5

OvR

3.0

3.5

C&S

4.0

4.5

5.0

GenSVM

5.5

6.0

(b) Total training time
OvO

1.0

1.5

SmartSVM

2.0

DAG

2.5

OvR

3.0

3.5

4.0

GenSVM

4.5

5.0

C&S

5.5

6.0

(c) Average training time

Figure 7: Rank plots of classifier performance in the simulation study. Figure (a) shows
the average ranks for out-of-sample predictive performance as measured by the ARI.
Figures (b) and (c) respectively show the average ranks for total training time and
average training time per hyperparameter configuration.

References
Alcalá, J., Fernández, A., Luengo, J., Derrac, J., Garcı́a, S., Sánchez, L., and Herrera, F.
Keel data-mining software tool: data set repository, integration of algorithms and experimental analysis framework. Journal of Multiple-Valued Logic and Soft Computing,
17(2-3):255–287, 2010.
Avi-Itzhak, H. and Diep, T. Arbitrarily tight upper and lower bounds on the bayesian
probability of error. IEEE Transactions on Pattern Analysis and Machine Intelligence,
18(1):89–91, 1996.
Bache, K. and Lichman, M. UCI machine learning repository. 2013.
Belkin, M. and Niyogi, P. Laplacian eigenmaps for dimensionality reduction and data
representation. Neural computation, 15(6):1373–1396, 2003.
Berisha, V. and Hero, A. Empirical non-parametric estimation of the Fisher information.
Signal Processing Letters, IEEE, 22(7):988–992, 2015.
Berisha, V., Wisler, A., Hero, A., and Spanias, A. Empirically estimable classification
bounds based on a nonparametric divergence measure. IEEE Transactions on Signal
Processing, 64(3):580–591, 2016.
Bhattacharyya, A. On a measure of divergence between two multinomial populations.
Sankhyā: The Indian Journal of Statistics, 7(4):401–406, 1946.
Borůvka, O. O jistém problému minimálnı́m. Práce Moravské Pridovedecké Spolecnosti,
3:37–58, 1926.
Chang, C. and Lin, C. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):27:1–27:27, 2011.
19

Chernoff, H. A measure of asymptotic efficiency for tests of a hypothesis based on the
sum of observations. The Annals of Mathematical Statistics, 23(4):493–507, 1952.
Cortes, C. and Vapnik, V. Support-vector networks. Machine Learning, 20(3):273–297,
1995.
Cox, D. The regression analysis of binary sequences. Journal of the Royal Statistical
Society. Series B (Methodological), 20(2):215–242, 1958.
Crammer, K. and Singer, Y. On the algorithmic implementation of multiclass kernelbased vector machines. The Journal of Machine Learning Research, 2(Dec):265–292,
2002.
Csiszár, I. I-divergence geometry of probability distributions and minimization problems.
The Annals of Probability, 3(1):146–158, 1975.
Demšar, J. Statistical comparisons of classifiers over multiple data sets. The Journal of
Machine Learning Research, 7(Jan):1–30, 2006.
El-Yaniv, R. and Etzion-Rosenberg, N. Hierarchical multiclass decompositions with
application to authorship determination. arXiv preprint arXiv:1010.2102, 2010.
El-Yaniv, R., Fine, S., and Tishby, N. Agnostic classification of markovian sequences.
In: Advances of Neural Information Processing Systems 10, pp. 465–471. MIT Press,
1998.
Fan, R.E., Chang, K.W., Hsieh, C.J., Wang, X.R., and Lin, C.J. LIBLINEAR: A
library for large linear classification. The Journal of Machine Learning Research,
9(Aug):1871–1874, 2008.
Frank, E. and Kramer, S. Ensembles of nested dichotomies for multi-class problems.
In: Proceedings of the 21st International Conference on Machine Learning, pp. 39–46.
ACM, 2004.
Friedman, J. and Rafsky, L. Multivariate generalizations of the Wald-Wolfowitz and
Smirnov two-sample tests. The Annals of Statistics, 7(4):697–717, 1979.
Fukunaga, K. Introduction to Statistical Pattern Recognition. Academic Press, 1990.
Hashlamoun, W., Varshney, P., and Samarasooriya, V. A tight upper bound on the
bayesian probability of error. IEEE Transactions on Pattern Analysis and Machine
Intelligence, 16(2):220–224, 1994.
Henze, N. and Penrose, M. On the multivariate runs test. Annals of statistics, 27(1):290–
298, 1999.
Ho, T. and Basu, M. Complexity measures of supervised classification problems. IEEE
Transactions on Pattern Analysis and Machine Intelligence, 24(3):289–300, 2002.
Hubert, L. and Arabie, P. Comparing partitions. Journal of Classification, 2(1):193–218,
1985.
Kailath, T. The divergence and Bhattacharyya distance measures in signal selection.
IEEE Transactions on Communication Technology, 15(1):52–60, 1967.

20

Keerthi, S., Sundararajan, S., Chang, K.W., Hsieh, C.J., and Lin, C.J. A sequential
dual method for large scale multi-class linear SVMs. In: Proceedings of the 14th ACM
SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.
408–416. 2008.
Kreßel, U. Pairwise classification and support vector machines. In: B. Schölkopf, C.J.C.
Burges, and A.J. Smola, editors, Advances in Kernel Methods, pp. 255–268. MIT
Press, 1999.
Kullback, S. and Leibler, R. On information and sufficiency. The Annals of Mathematical
Statistics, 22(1):79–86, 1951.
LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient-based learning applied to
document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.
Lin, J. Divergence measures based on the shannon entropy. IEEE Transactions on
Information Theory, 37(1):145–151, 1991.
Lorena, A. and De Carvalho, A. Building binary-tree-based multiclass classifiers using
separability measures. Neurocomputing, 73(16):2837–2845, 2010.
Lorena, A., De Carvalho, A., and Gama, J. A review on the combination of binary
classifiers in multiclass problems. Artificial Intelligence Review, 30(1):19–37, 2008.
Lu, Y., Guo, H., and Feldkamp, L. Robust neural learning from unbalanced data samples. In: Proceedings of the IEEE International Joint Conference on Neural Networks,
volume 3, pp. 1816–1821. IEEE, 1998.
March, W., Ram, P., and Gray, A. Fast Euclidean minimum spanning tree: algorithm,
analysis, and applications. In: Proceedings of the 16th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining, pp. 603–612. ACM, 2010.
McCulloch, W. and Pitts, W. A logical calculus of the ideas immanent in nervous
activity. The Bulletin of Mathematical Biophysics, 5(4):115–133, 1943.
Pearson, K. On lines and planes of closest fit to systems of points in space. The London,
Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(11):559–572,
1901.
Platt, J., Cristianini, N., and Shawe-Taylor, J. Large margin DAGs for multiclass
classification. In: S.A. Solla, T.K. Leen, and K. Müller, editors, Advances in Neural
Information Processing Systems 12, pp. 547–553. MIT Press, 2000.
Qiao, X. and Liu, Y. Adaptive weighted learning for unbalanced multicategory classification. Biometrics, 65(1):159–168, 2009.
Santos, J. and Embrechts, M. On the use of the adjusted rand index as a metric
for evaluating supervised classification. In: Proceedings of the 19th International
Conference on Artificial Neural Networks: Part II, pp. 175–184. Springer-Verlag, 2009.
Schwenker, F. and Palm, G. Tree-structured support vector machines for multi-class
pattern recognition. In: International Workshop on Multiple Classifier Systems, pp.
409–417. Springer, 2001.
Stoer, M. and Wagner, F. A simple min-cut algorithm. Journal of the ACM, 44(4):585–
591, 1997.
21

Stone, M. Cross-validatory choice and assessment of statistical predictions. Journal of
the Royal Statistical Society. Series B (Methodological), 36(2):111–147, 1974.
Takahashi, F. and Abe, S. Decision-tree-based multiclass support vector machines. In:
Neural Information Processing, 2002. ICONIP’02. Proceedings of the 9th International Conference on, volume 3, pp. 1418–1422. IEEE, 2002.
Tibshirani, R. and Hastie, T. Margin trees for high-dimensional classification. Journal
of Machine Learning Research, 8(Mar):637–652, 2007.
Van den Burg, G. and Groenen, P. GenSVM: A generalized multiclass support vector
machine. Journal of Machine Learning Research, 17(225):1–42, 2016.
Vapnik, V. Statistical learning theory. Wiley, New York, 1998.
Vural, V. and Dy, J. A hierarchical method for multi-class support vector machines. In:
Proceedings of the 21st International Conference on Machine Learning, pp. 105–112.
ACM, 2004.
Wald, A. Foundations of a general theory of sequential decision functions. Econometrica,
15(4):279–313, 1947.
Whitney, V. Algorithm 422: minimal spanning tree. Communications of the ACM,
15(4):273–274, 1972.
Wisler, A., Berisha, V., Wei, D., Ramamurthy, K., and Spanias, A. Empiricallyestimable multi-class classification bounds. In: 2016 IEEE International Conference
on Acoustics, Speech and Signal Processing (ICASSP), pp. 2594–2598. IEEE, 2016.

22

