considerations of inductive approximation based on finite samples. In this paper we attempt to decompose multi-class problems into hierarchically ordered collections of binary problems so as to minimize the Bayes error of the entire construction.

## 2.1. The Jensen-Shannon (Js) Divergence

Let P1 and P2 **be two distributions over some finite** set X, and let π = (π1, π2**) be their priors. Then, the**
Jensen-Shannon (JS) divergence (?) of P1 **and and** P2 with respect to the prior π is JSπ(P1, P2) = H(π1P1 + π2P2) − π1H(P1) − π2(P2),
(1)
where H(·**) is the Shannon entropy. It can be shown**
that JSπ(P1, P2**) is non-negative, symmetric, bounded** (by H(π**)) and it equals zero if and only if** P1 ≡ P2.

According to (?) the JS-divergence was first introduced by (?**) as a dissimilarity measure for random**
graphs. Setting Mπ = π1P1 + π2P2 **it is easy to see**
(?**) that**

$JS(P_{1},P_{2})=\pi_{1}D_{KL}(P_{1}||M_{\pi})+\pi_{2}D_{KL}(P_{2}||M_{\pi})$,
(2)
where DKL(·||·**) is the Kullback-Leibler divergence** (?). The average distribution Mπ **is called the** mutual source of P1 and P2 (?**) and it can be easily shown**
that

$$M_{\pi}=\arg\min_{Q}\pi_{1}D_{KL}(P_{1}||Q)+\pi_{2}D_{KL}(P_{2}||Q).\tag{3}$$

That, is the mutual source of P1 and P2 **is the closest**
to both of them simultaneously in terms of the KLdivergence. Like the KL-divergence the JS-divergence has a number of important roles in statistics and pattern recognition. In particular, the JS-divergence, compared against a threshold is an optimal statistical test in the Neyman-Pearson sense (?**) for the** *twosample problem* (?).

## 2.2. Jensen-Shannon Bounds On The Bayes Error

Lower and upper bounds on the binary Bayes error are given by (?). Again, let π = (π1, π2**) be the priors** and p1, p2**, the class conditionals, as defined above.**
Let p(error**) be the Bayes error. Set** J = H(π) −
JSπ(p1, p2) with H(π**) denoting the binary entropy.**

## Theorem 1 (Lin)

$${\frac{1}{4}}J^{2}\leq p(e r r o r)\leq{\frac{1}{2}}J\qquad\qquad(4)$$

These bounds are generalized to k **classes in a straightforward manner. Considering a multiclass problem**
with k classes and class-conditionals p1, . . . , pk and priors π = (π1, . . . , πk**), the Bayes error is given by**

$$p(error_{k})=\int_{x}p(x)(1-\max\{p(C_{1}|x),\ldots,p(C_{k}|x)\})dx.$$  Now setting $J_{k}=H(\pi)-JS_{\pi}(p_{1},\ldots,p_{k})$ we have 

## Theorem 2 (Lin)

$$\frac{1}{4(k-1)}J_{k}^{2}\leq p(e r r o r_{k})\leq\frac{1}{2}J.\qquad\qquad(5)$$
$$)-\pi_{2}(I$$
$\frac{1}{4}$  . 
Given the true class-conditional, these JS bounds on the Bayes error can be efficiently computed using either (1) or (2) (or their generalized forms).

## 3. Bounds On The Bayes Error Of Hierarchical Decompositions

In this section we provide bounds on the Bayes error of hierarchical decompositions. The bounds are obtained using a straightforward application of the binary bounds of Theorem 1. We begin with a more formal description of hierarchical decompositions. Consider a multi-class problem with k **classes** C =
C1, . . . , Ck, and let T = (V, E**) be any full binary tree**
with k **leaves, one for each class. For each node** v ∈ V
we map a label set ℓ(v) ⊆ C which is defined as follows. Each leaf v (of the k **leaves) is mapped to a**
unique class (among the k classes). If v **is an internal**
node whose left and right children are vL and vR, respectively, then ℓ(v) = ℓ(vL) ∪ ℓ(vR**). Given the tree**
T and the mapping ℓ **we decompose the multi-class**
problem by constructing a binary classifier hv **for each**
internal node v of T such that hv is trained to discriminate between classes in ℓ(vL) and classes in ℓ(vR**). In**
the case of hard classifiers hv(x) ∈ {±1} and we identify '−1' with 'L' and '+1' with 'R**'. In the case of soft**
classifiers, hv(x) ∈ [0, 1] and we identify 0 with 'L**' and**
1 with 'R'. Since there are k **leaves there are exactly**
k − **1 binary classifiers in the tree. The training set of** each classifier is naturally determined by the mapping ℓ. Given a sample x whose label (in C**) is unknown, one** can think of a number of "decoding" schemes that combine the individual binary classifiers. When considering hard binary classifiers a natural choice to aggregate the binary decisions is to start from the root r and apply its associated classifier hr. If hr(x) = −1 we go to rL and otherwise we go to rR**, etc. This**
way we continue until we reach a leaf and predict for x this leaf's associated (unique) class. In the case of