Extreme Multiclass Classification Criteria

Abstract

We analyze the theoretical properties of the recently proposed objective function for efficient online construction and training of multiclass classification trees in the settings where the label space is very large. We show the important properties of this objective and provide a complete proof that maximizing it simultaneously encourages balanced trees and improves the purity of the class distributions at subsequent levels in the tree. We further explore its connection to the three well-known entropy-based decision tree criteria, i.e., Shannon entropy, Gini-entropy and its modified variant, for which efficient optimization strategies are largely unknown in the extreme multiclass setting. We show theoretically that this objective can be viewed as a surrogate function for all of these entropy criteria and that maximizing it indirectly optimizes them as well. We derive boosting guarantees and obtain a closed-form expression for the number of iterations needed to reduce the considered entropy criteria below an arbitrary threshold. The obtained theorem relies on a weak hypothesis assumption that directly depends on the considered objective function. Finally, we prove that optimizing the objective directly reduces the multi-class classification error of the decision tree.

1. Introduction

This paper focuses on the multiclass classification setting, where the number of classes is very large. The recent widespread development of data-acquisition web services and devices has helped make large data sets, such as multiclass data sets, commonplace. Straightforward extensions of the binary approaches to the multiclass setting, such as the one-against-all approach [1], which for each data point computes a score for each class and returns the class with the maximum score, do not often work in the presence of strict computational constraints as their running time often scales linearly with the number of labels k. On the other hand, the most computationally efficient approaches for multiclass classification are given by $\mathcal{O}(logk)$ train/test running time [2]. This running time can naturally be achieved by hierarchical classifiers that build the hierarchy over the labels.

This paper considers a hierarchical multiclass decision tree structure, where each node of the tree contains a binary classifier h from some hypothesis class $\mathcal{H}$ that sends an example reaching that node to either left ($h(x)\le 0$) or right ($h(x)>0$) child node depending on the sign of $h(x)$ (each node has its own splitting hypothesis). The test example descends from the root to the leaf of such tree guided by the classifiers lying on its path, and is labeled according to the label with the highest frequency amongst the training examples that were reaching the leaf that it descended to. The tree is constructed and trained in a top-down fashion, where splitting the data in every node of the tree is done by maximizing the following objective function recently introduced in the literature [3] (along with the algorithm (we refer the reader to the referenced paper for the algorithm’s details), called LOMtree, optimizing it in an online fashion):

$$J(h):=2\sum _{i=1}^k|{\pi }_{i}P(h(x)>0)-\underset{P(h(x)>0|i){\pi }_i}{\underbrace{P(h(x)>0,i)}}|,$$

(1)

where $x\in \mathcal{X}\subseteq {\mathbb{R}}^d$ are the data points (each with a label from the set $\{1,2,\dots ,k\}$), ${\pi }_i$ denotes the proportion of label i amongst the examples reaching a node, and probabilities $P(h(x)>0)$ and $P(h(x)>0|i)$ denote the fraction of examples reaching a node for which $h(x)>0$, marginally and conditional on class i respectively. The objective measures the dependence between the split and the class distribution. Note that it satisfies $J(h)\in [0,1]$ and, as implied by its form, maximizing it encourages the fraction of examples going to the right from class i to be substantially different from the background fraction for each class i. Thus for a balanced split (i.e., $P(h(x)>0)=0.5$), the examples of class i are encouraged to be sent exclusively to the left ($P(h(x)>0|i)=0$) or right ($P(h(x)>0|i)=1$) refining the purity of the class distributions at subsequent levels in the tree. The LOMtree algorithm effectively maximizes this objective over hypotheses $h\in \mathcal{H}$ in an online fashion with stochastic gradient descent (SGD) and obtains good-quality multiclass tree predictors with logarithmic train and test running times. Despite that, this objective and its properties (including the relation to the more standard entropy criteria) remain largely ununderstood. Its exhaustive analysis is instead provided in this paper.

Our contributions are the following:

• We provide an extensive theoretical analysis of the properties of the considered objective and prove that maximizing this objective in any tree node simultaneously encourages balanced partition of the data in that node and improves the purity of the class distributions at its children nodes.
• We show a formal relation of this objective to some more standard entropy-based objectives, i.e., Shannon entropy, Gini-entropy and its modified variant, for which online optimization schemes in the context of multiclass classification are largely unknown. In particular we show that i) the improvement in the value of entropy resulting from performing the node split is lower-bounded by an expression that increases with the value of the objective and thus ii) the considered objective can be used as a surrogate function for indirectly optimizing any of the three considered entropy-based criteria.
• We present three boosting theorems for each of the three entropy criteria, which provide the number of iterations needed to reduce each of them below an arbitrary threshold. Their weak hypothesis assumptions rely on the considered objective function.
• We establish the error bound that relates maximizing the objective function with reducing the multi-class classification error.
• Finally, in the Appendix A we establish an empirical connection between the multiclass classification error and the entropy criteria and show that Gini-entropy most closely resembles the behavior of the test error in practice.

The main theoretical analysis of this paper is kept in the boosting framework [4] and relies on the assumption that the objective function can be weakly optimized in the internal nodes of the tree. This weak advantage is amplified in the tree leading to hierarchies achieving any desired level of entropy (either Shannon entropy, Gini-entropy or its modified variant). Our work adds new theoretical results to the theory of multiclass boosting. Note that the multiclass boosting is largely ununderstood from the theoretical perspective [5] (we refer the reader to [5] for comprehensive review of the theory of muticlass boosting).

The paper is organized as follows: related literature is discussed in Section 2, the theoretical properties of the objective $J(h)$ are shown in Section 3, the main theoretical results are presented in Section 4, and finally the mathematical properties of the entropy criteria and the proofs of the main theoretical results are provided in Section 5. Conclusions (Section 6) end the paper. Appendix A contains basic numerical experiments (Appendix A.1) and additional proofs (Appendix A.2).

2. Related Work

The extreme multiclass classification problem has been addressed in the literature in different ways. We discuss them here, putting emphasis on the ones that build hierarchical predictors as these techniques are the most relevant to this paper. Only a few authors [2,3,6,7,8] simultaneously address logarithmic time training and testing. The methods they propose are either hard to apply in practical problems [7] or use fixed tree structures [6,8]. Furthermore, an alternative approach based on using a random tree structure was shown to potentially lead to considerable underperformance [3,9]. At the same time, for massive datasets making multiple passes through the data is computationally costly, which justifies the need for developing online approaches, where the algorithm streams over a potentially infinitely large data set (online approaches are also plausible for non-stationary problems). It is unclear how to optimize standard decision tree objectives, such as Shannon or Gini-entropy, in this setting (early attempt was recently proposed [2] for Shannon entropy). One of the prior works to this paper [3] introduces an objective function which enjoys certain advantages over entropy criteria. In particular, it can be easily and efficiently optimized online. The authors however present an incomplete theoretical analysis and leave a number of open questions, which this paper instead aims at addressing. The algorithms for incremental learning of classification with decision trees also include some older works [10,11,12], which split any node according to the outcome of the node split-test based on the values of selected attributes of the data examples reaching that node. These approaches are different from the one in this paper, where the node split is performed according to the value of the learned (e.g., with SGD) hypothesis computed for the entire vector of attributes of the data examples reaching that node.

Other tree-based approaches include conditional probability trees [13] and clustering methods [9,14,15] ([9] was later improved in [16]), but they allow training time to be linear in the label complexity. The remaining techniques for multiclass classification include sparse output coding [17], variants of error correcting output codes [18], variants of iterative least-squares [19], and a method based on guess-averse loss functions [20].

Finally note that the conditional density estimation problem is also challenging in the large-class settings and in this respect remains parallel to the extreme multiclass classification problem [21]. In the context of conditional density estimation problem, there have also been some works that use tree structured models to accelerate computation of the likelihood and gradients [8,22,23,24]. They typically use heuristics based on using ontologies [8], Huffman coding [24], and various other mechanisms.

3. Theoretical Properties of the Objective Function

In this section we describe the objective function introduced in Equation (1) and provide its theoretical properties. The proofs are deferred to the Appendix. We first introduce the definitions of the concept of balancedness and purity of the node split.

Definition 1 (Purity and balancedness).

The hypothesis $h\in \mathcal{H}$ induces a pure split if $\alpha :={\sum }_{i=1}^k{\pi }_{i}min(P(h(x)>0|i),P(h(x)<0|i))\le \delta$, where $\delta \in [0,0.5)$, and α is called the purity factor.

The hypothesis $h\in \mathcal{H}$ induces a balanced split if $\beta :=P(h(x)>0)\in [c,1-c]$, where $c\in (0,0.5]$, and β is called the balancing factor.

A partition is perfectly pure if $\alpha =0$ (examples of the same class are sent exclusively to the left or to the right). A partition is called perfectly balanced if $\beta =0.5$ (equal number of examples are sent to the left and to the right). The notions of balancedness and purity are conveniently illustrated in Figure 1, where it is shown that the purity criterion helps to refine the choice of the splitting hypothesis from among well-balanced candidates.

Next, we show the first theoretical property of the objective function $J(h)$ that characterizes its behavior at the optimum ($J(h)=1$).

Lemma 1.

The hypothesis $h\in \mathcal{H}$ induces a perfectly pure and balanced partition if and only if $J(h)=1$.

For some data sets however there exist no hypotheses producing perfectly pure and balanced splits. We next show that increasing the value of the objective leads to more balanced splits.

Lemma 2.

For any hypothesis h and any distribution over data examples the balancing factor β satisfies $\beta \in \left[0.5(1-\sqrt{1-J(h)}),0.5(1+\sqrt{1-J(h)})\right]$.

We refer to the interval to which $\beta$ belongs to as $\beta$-interval. Thus the larger (closer to 1) the value of $J(h)$ is, the narrower the $\beta$-interval is, leading to more balanced splits at the extremes of this interval ($\beta$ closer to $0.5$).

This result combined with the next lemma implies that, at the extremes of the $\beta$ interval, the value of the upper-bound on the purity factor decreases as the value of $J(h)$ increases (since $J(h)$ gets closer to 1 and the balancing factor $\beta$ gets closer to $0.5$ at the extremes of the $\beta$ interval). The recovered splits therefore have better purity ($\alpha$ closer to 0).

Lemma 3.

(Lemma 1 in [3]). For any hypothesis h and any distribution over data examples the purity factor α and the balancing factor β satisfy $\alpha \le min\left\{(2-J(h))/4\beta -\beta ,0.5\right\}$.

Note that the equality condition in Lemma 3 is achieved when $P(h(x)>0|i)=P(h(x)<0|i)=0.5$ (and thus, $\alpha =0$, $\beta =0.5$, and $J(h)=0$).

We thus showed that maximizing the objective in Equation (1) in each tree node simultaneously encourages trees that are balanced and whose purity of the class distributions is gradually improving when moving from the root to a subsequent tree levels. Lemmas 2 and 3 are illustrated in Figure 2.

In the next section we show that the objective $J(h)$ is related to the more standard decision tree entropy-based objectives and that maximizing it leads to the reduction of these criteria. We consider three different entropy criteria in this paper. The theoretical analysis relies on the boosting framework and depends on the weak learning assumption. Three different entropy-based criteria lead to three different theoretical statements, where we bound the number of splits required to reduce the value of the criterion below given level. The bounds we obtain, and their dependences on the number of classes (k), critically depend on the strong concativity properties of the considered entropy-based objectives.

4. Main Theoretical Results

4.1. Notation

We first introduce notation. Let $\mathcal{T}$ denote the tree under consideration. ${\pi }_{l,i}$’s denote the probabilities that a randomly chosen data point x drawn from $\mathcal{P}$, where $\mathcal{P}$ is a fixed target distribution over $\mathcal{X}$, has label i given that x reaches node l (note that ${\sum }_{i=1}^k{\pi }_{l,i}=1$), t denotes the number of internal tree nodes, ${\mathcal{L}}_t$ denotes the set of all tree leaves at time t, and $w_l$ is the weight of leaf l defined as the probability a randomly chosen x drawn from $\mathcal{P}$ reaches leaf l (note that ${\sum }_{l\in {\mathcal{L}}_t}{w}_l=1$). We study a tree construction algorithm where we recursively find the leaf node with the highest weight, and choose to split it into two children. Consider the tree constructed over t steps where in each step we take one leaf node and split it (thus the number of splits is equal to the number of internal nodes of the tree) ($t=1$ corresponds to splitting the root, thus the tree consists of one node (root) and its two children (leaves) in this step). We measure the quality of the tree at any given time t with three different entropy criteria:

• Shannon entropy $G_t^e$:

  $$G_t^e=\sum _{l\in {\mathcal{L}}_t}{w}_l\sum _{i=1}^k{\pi }_{l,i}ln\left(\frac{1}{{\pi }_{l,i}}\right)$$
• Gini-entropy $G_t^g$:

  $$G_t^g=\sum _{l\in {\mathcal{L}}_t}{w}_l\sum _{i=1}^k{\pi }_{l,i}(1-{\pi }_{l,i})$$
• Modified Gini-entropy $G_t^m$:

  $$G_t^m=\sum _{l\in {\mathcal{L}}_t}{w}_l\sum _{i=1}^k\sqrt{{\pi }_{l,i}(\mathcal{C}-{\pi }_{l,i})},$$

  where $\mathcal{C}$ is a constant such that $\mathcal{C}>2$.

These criteria are the natural extensions of the criteria used in the context of binary classification [25] to the multiclass classification setting (note that there is more than one way of extending the entropy-based criteria from [25] to the multiclass classification setting, e.g., the modified Gini-entropy could as well be defined as $G_t^m={\sum }_{l\in {\mathcal{L}}_t}{w}_l{\sum }_{i=1}^k\sqrt{{\pi }_{l,i}(\mathcal{C}-{\pi }_{l,i})}$, where $\mathcal{C}\in [1,2]$. This and other extensions will be investigated in future works). We will next present the main results of this paper, which will be followed by their proofs. We begin with introducing the weak hypothesis assumption.

4.2. Theorems

Definition 2 (Weak Hypothesis Assumption).

Let m denote any internal node of the tree $\mathcal{T}$, and let ${\beta }_m=P(h_m(x)>0)$ and $P_{m,i}=P(h_m(x)>0|i)$. Furthermore, let $\gamma \in {\mathbb{R}}^{+}$ be such that for all m, $\gamma \in (0,min({\beta }_m,1-{\beta }_m)]$. We say that the weak hypothesis assumption is satisfied when for any distribution $\mathcal{P}$ over $\mathcal{X}$ at each node m of the tree $\mathcal{T}$ there exists a hypothesis $h_m\in \mathcal{H}$ such that $J(h_m)/2={\sum }_{i=1}^k{\pi }_{m,i}|P_{m,i}-{\beta }_m|\ge \gamma$.

The weak hypothesis assumption says that in every node of the tree we are able to recover a hypothesis from $\mathcal{H}$ which corresponds to the value of the objective that is above 0 (thus the corresponding split is “weakly” pure and “weakly” balanced).

Consider next any time t and let n be the heaviest leaf at time t that we split and its weight $w_n$ be denoted by w for brevity. Similarly, let h denote the regressor at node n (shorthand for $h_n$). We denote the difference between the contribution of node n to the value of the entropy-based objectives in times t and $t+1$ as

$${\Delta }_t^e:=G_t^e-G_{t+1}^e;{\Delta }_t^g:=G_t^g-G_{t+1}^g;{\Delta }_t^m:=G_t^m-G_{t+1}^m.$$

Then the following lemma holds (the proof in provided in Section 5):

Lemma 4.

Under the Weak Hypothesis Assumption, the change in entropies occuring due to the node split can be bounded as

$${\Delta }_t^e\ge \frac{wJ{(h)}^2}{8{(1-\gamma )}^2};{\Delta }_t^g\ge \frac{wJ{(h)}^2}{4k{(1-\gamma )}^2};{\Delta }_t^m\ge \frac{{(\mathcal{C}-2)}^2}{{\mathcal{C}}^3}·\frac{wJ{(h)}^2}{4k{(1-\gamma )}^2}.$$

Clearly, maximizing the objective $J(h)$ improves the entropy reduction. The considered objective can therefore be viewed as a surrogate function for indirectly optimizing any of the three considered entropy-based criteria, for which efficient online optimization strategies are largely unknown but highly desired in the multiclass classification setting. To be more specific, the standard packages for binary classification trees, such as CART [26] and C4.5 [27], require running a brute force search to find a partition at every node of the tree from a set of all possible partitions that leads to the biggest improvement of the entropy-based criterion of interest [25]. This is prohibitive in case of the multiclass problem. $J(h)$ however can be efficiently optimized with SGD instead.

We next state the three boosting theoretical results captured in Theorems 1–3. They guarantee that the top-down decision tree algorithm which optimizes $J(h)$ in each node will amplify the weak advantage, captured in the weak learning assumption, to build a tree achieving any desired level of entropy (either Shannon entropy, Gini-entropy or its modified variant).

Theorem 1.

Under the Weak Hypothesis Assumption, for any $\alpha \in [0,2lnk]$, to obtain $G_t^e\le \alpha$ it suffices to make $t\ge {\left(\frac{2lnk}{\alpha }\right)}^{\frac{4{(1-\gamma )}^2}{{\gamma }^2{log}_{2}e}lnk}$ splits.

Theorem 2.

Under the Weak Hypothesis Assumption, for any $\alpha \in [0,2\left(1-\frac{1}{k}\right)]$, to obtain $G_t^g\le \alpha$ it suffices to make $t\ge {\left(\frac{2\left(1-\frac{1}{k}\right)}{\alpha }\right)}^{\frac{2{(1-\gamma )}^2}{{\gamma }^2{log}_{2}e}(k-1)}$ splits.

Theorem 3.

Under the Weak Hypothesis Assumption, for any $\alpha \in [\sqrt{\mathcal{C}-1},2\sqrt{k\mathcal{C}-1}]$, to obtain $G_t^m\le \alpha$ it suffices to make $t\ge {\left(\frac{2\sqrt{k\mathcal{C}-1}}{\alpha }\right)}^{\frac{2{(1-\gamma )}^2{\mathcal{C}}^3}{{\gamma }^2{(\mathcal{C}-2)}^2{log}_{2}e}k\sqrt{k\mathcal{C}-1}}$ splits.

Finally, we provide the error guarantee in Theorem 4. Denote $y(x)$ to be a fixed target function with domain $\mathcal{X}$, which assigns the data point x to its label, and let $\mathcal{P}$ be a fixed target distribution over $\mathcal{X}$. Together y and $\mathcal{P}$ induce a distribution on labeled pairs $(x,y(x))$. Let $t(x)$ be the label assigned to data point x by the tree. We denote as $ϵ(\mathcal{T})$ the error of tree $\mathcal{T}$, i.e., $ϵ{(\mathcal{T}):=}_{x\sim \mathcal{P}}\left[{\sum }_{i=1}[t(x)=i,y(x)\ne i]\right]$

Theorem 4.

Under the Weak Hypothesis Assumption, for any $\alpha \in [0,1]$, to obtain $ϵ(\mathcal{T})\le \alpha$ it suffices to make $t\ge {\left(\frac{2lnk{log}_{2}e}{\alpha }\right)}^{\frac{4{(1-\gamma )}^2}{{\gamma }^2{log}_{2}e}lnk}$ splits.

Remark 1.

The main theorems show how fast the entropy criteria or the multi-class classification error drop as the tree grows and performs node splits. These statements therefore provide a platform for comparing different entropy criteria and answer two questions: 1) for a fixed $\alpha ,\gamma ,\mathcal{C}$, and k, which criterion is reduced the most with each split? and 2) can the multi-class error match the convergence speed of the best entropic criterion? Hence, it can be noted that the Shannon entropy has the most advantageous dependence on the label complexity, since the bound scales only logarithmically with k, and thus achieves the fastest convergence. Simultaneously, the multi-class classification rate matches this advantageous convergence rate and also scales favorably (logarithmically) with k. Finally, even though the weak hypothesis requires only slightly favorable γ, i.e., $\gamma >0$, in practice when constructing the tree one can optimize J in every node of the tree, which effectively pushes γ to be as high as possible. In that case γ becomes a well-behaving constant in the above theorems, ideally equal to $1/2$, and does not negatively affect the split count.

We next discuss in details the mathematical properties of the entropy-based criteria, which are important to prove the above theorems.

5. Proofs

5.1. Properties of the Entropy-Based Criteria

Each of the presented entropy-based criteria has a number of useful properties that we give next, along with their proofs. We first give bounds on the values of the entropy-based functions. As before, let w be the weight of the heaviest leaf in the tree at time t.

5.1.1. Bounds on the Entropy-Based Criteria

Lemma 5.

The Shannon entropy function $G_t^e$ at time t is bounded as $0\le G_t^e\le (t+1)wlnk$.

Lemma 6.

The Gini-entropy function $G_t^g$ at time t is bounded as $0\le G_t^g\le (t+1)w\left(1-1/k\right)$.

Lemma 7.

The modified Gini-entropy function $G_t^m$ at time t is bounded as $\sqrt{\mathcal{C}-1}\le G_t^m\le (t+1)w\sqrt{k\mathcal{C}-1}$.

The upper-bounds in Lemmas 5–7 are tight, where the equalities hold for the special case when ${\forall }_{i\in \{1,\dots ,k\},l\in {\mathcal{L}}_t}{\pi }_{l,i}=1/k$, e.g., when each internal node of the tree produce a perfectly pure and balanced split.

5.1.2. Strong Concativity Properties of the Entropy-Based Criteria

So far we have been focusing on the time step t. Recall that n is the heaviest leaf at time t and its weight $w_n$ is denoted by w for brevity. Consider splitting this leaf to two children $n_0$ and $n_1$. For ease of notation let $w_0=w_{n_0}$ and $w_1=w_{n_1}$, $\beta =P(h_n(x)>0)$ and $P_i=P(h_n(x)>0|i)$, and furthermore let ${\pi }_i$ and h be the shorthands for ${\pi }_{n,i}$ and $h_n$, respectively. Recall that $\beta ={\sum }_{i=1}^k{\pi }_i{P}_i$ and ${\sum }_{i=1}^k{\pi }_i=1$. Notice that $w_0=w(1-\beta )$ and $w_1=w\beta$. Let $\mathit{\pi }$ be the k-element vector with $i^{th}$ entry equal to ${\pi }_i$. Finally, let ${\tilde{G}}^e(\mathit{\pi })={\sum }_{i=1}^k{\pi }_{i}ln\left(\frac{1}{{\pi }_i}\right)$, ${\tilde{G}}^g(\mathit{\pi })={\sum }_{i=1}^k{\pi }_i(1-{\pi }_i)$, and ${\tilde{G}}^m(\mathit{\pi })={\sum }_{i=1}^k\sqrt{{\pi }_i(1-{\pi }_i)}$. Before the split the contribution of node n to resp. $G_t^e$, $G_t^g$, and $G_t^m$ was resp. $w{\tilde{G}}^e(\mathit{\pi })$, $w{\tilde{G}}^g(\mathit{\pi })$, and $w{\tilde{G}}^m(\mathit{\pi })$. Note that ${\pi }_{n_0,i}=\frac{{\pi }_i(1-P_i)}{1-\beta }$ and ${\pi }_{n_1,i}=\frac{{\pi }_i{P}_i}{\beta }$ are the probabilities that a randomly chosen x drawn from $\mathcal{P}$ has label i given that x reaches nodes $n_0$ and $n_1$ respectively. For brevity, let ${\pi }_{n_0,i}$ and ${\pi }_{n_1,i}$ be denoted respectively as ${\pi }_{0,i}$ and ${\pi }_{1,i}$. Let ${\mathit{\pi }}_0$ be the k-element vector with $i^{th}$ entry equal to ${\pi }_{0,i}$ and let ${\mathit{\pi }}_1$ be the k-element vector with $i^{th}$ entry equal to ${\pi }_{1,i}$. Notice that $\mathit{\pi }=(1-\beta ){\mathit{\pi }}_0+\beta {\mathit{\pi }}_1$. After the split the contribution of the same, now internal, node n changes to resp. $w((1-\beta ){\tilde{G}}^e({\mathit{\pi }}_0)+\beta {\tilde{G}}^e({\mathit{\pi }}_1))$, $w((1-\beta ){\tilde{G}}^g({\mathit{\pi }}_0)+\beta {\tilde{G}}^g({\mathit{\pi }}_1))$, and $w((1-\beta ){\tilde{G}}^m({\mathit{\pi }}_0)+\beta {\tilde{G}}^m({\mathit{\pi }}_1))$. We can compute the difference between the contribution of node n to the value of the entropy-based objectives in times t and $t+1$ as

$$\begin{array}{c}\hfill {\Delta }_t^e=G_t^e-G_{t+1}^e=w\left[{\tilde{G}}^e(\mathbf{\pi })-(1-\beta ){\tilde{G}}^e({\mathbf{\pi }}_0)-\beta {\tilde{G}}^e({\mathbf{\pi }}_1)\right],\end{array}$$

(2)

$$\begin{array}{c}\hfill {\Delta }_t^g=G_t^g-G_{t+1}^g=w\left[{\tilde{G}}^g(\mathbf{\pi })-(1-\beta ){\tilde{G}}^g({\mathbf{\pi }}_0)-\beta {\tilde{G}}^g({\mathbf{\pi }}_1)\right],\end{array}$$

(3)

$$\begin{array}{c}\hfill {\Delta }_t^m=G_t^m-G_{t+1}^m=w\left[{\tilde{G}}^m(\mathbf{\pi })-(1-\beta ){\tilde{G}}^m({\mathbf{\pi }}_0)-\beta {\tilde{G}}^m({\mathbf{\pi }}_1)\right].\end{array}$$

(4)

The next three lemmas, Lemmas 8–10, describe the strong concativity properties of the entropy, Gini-entropy and modified Gini-entropy, which can be used to lower-bound ${\Delta }_t^e$, ${\Delta }_t^g$, and ${\Delta }_t^m$ (Equations (2)–(4) correspond to a gap in the Jensen’s inequality applied to the strongly concave function).

Lemma 8.

The Shannon entropy function ${\tilde{G}}^e$ is strongly concave with respect to $l_1$-norm with modulus 1, and thus the following holds ${\tilde{G}}^e(\mathit{\pi })-(1-\beta ){\tilde{G}}^e({\mathit{\pi }}_0)-\beta {\tilde{G}}^e({\mathit{\pi }}_1)\ge \frac{1}{2}\beta (1-\beta ){\parallel {\mathit{\pi }}_0-{\mathit{\pi }}_1\parallel }_1^2$.

Lemma 9.

The Gini-entropy function ${\tilde{G}}^g$ is strongly concave with respect to $l_2$-norm with modulus 2, and thus the following holds ${\tilde{G}}^g(\mathit{\pi })-(1-\beta ){\tilde{G}}^g({\mathit{\pi }}_0)-\beta {\tilde{G}}^g({\mathit{\pi }}_1)\ge \beta (1-\beta ){\parallel {\mathit{\pi }}_0-{\mathit{\pi }}_1\parallel }_2^2$.

Lemma 10.

The modified Gini-entropy function ${\tilde{G}}^m$ is strongly concave with respect to $l_2$-norm with modulus $\frac{2{(\mathcal{C}-2)}^2}{{\mathcal{C}}^3}$, and thus the following holds ${\tilde{G}}^m(\mathit{\pi })-(1-\beta ){\tilde{G}}^m({\mathit{\pi }}_0)-\beta {\tilde{G}}^m({\mathit{\pi }}_1)\ge \frac{{(\mathcal{C}-2)}^2}{{\mathcal{C}}^3}\beta (1-\beta ){\parallel {\mathit{\pi }}_0-{\mathit{\pi }}_1\parallel }_2^2$.

Figure 3 illustrates different entropy criteria normalized to the $[0,1]$ interval.

5.2. Proof of Lemma 4 and Theorems 1–3

We finally proceed to proving all three boosting theorems, Theorems 1–3. Lemma 4 is a by-product of these proofs.

Proof. 

For the Shannon entropy it follows from Equation (2), Lemmas 5 and 8 that

$$\begin{array}{cc}\hfill {\Delta }_t^e& \ge \frac{1}{2}w\beta (1-\beta ){\parallel {\mathbf{\pi }}_0-{\mathbf{\pi }}_1\parallel }_1^2\hfill \\ & =\frac{1}{2}\frac{w}{\beta (1-\beta )}{\left(\sum _{i=1}^k\left|{\pi }_i(P_i-\beta )\right|\right)}^2\hfill \\ & =\frac{wJ{(h)}^2}{8\beta (1-\beta )}\hfill \\ & \ge \frac{J{(h)}^2{G}_t^e}{8\beta (1-\beta )(t+1)lnk}\hfill \\ & \ge \frac{{\gamma }^2{G}_t^e}{2{(1-\gamma )}^2(t+1)lnk},\hfill \end{array}$$

(5)

where the last inequality comes from the fact that $1-\gamma \ge \beta \ge \gamma$ (see the definition of $\gamma$ in the weak hypothesis assumption) and $J(h)\ge 2\gamma$ (see weak hypothesis assumption). For the Gini-entropy criterion notice that from Equation (3), Lemmas 6, 9, and A4 it follows that

$$\begin{array}{cc}\hfill {\Delta }_t^g& \ge w\beta (1-\beta )\parallel {\mathbf{\pi }}_0-{\mathbf{\pi }}_1{\parallel }_2^2\hfill \\ & \ge \frac{1}{k}w\beta (1-\beta ){\parallel {\mathbf{\pi }}_0-{\mathbf{\pi }}_1\parallel }_1^2\hfill \\ & \ge \frac{{\gamma }^2{G}_t^g}{{(1-\gamma )}^2(t+1)(k-1)},\hfill \end{array}$$

(6)

where the last inequality is obtained similarly as the last inequality in Equation (5). And finally for the modified Gini-entropy it follows from Equation (4), Lemmas 7, 10, and A4 that

$$\begin{array}{cc}\hfill {\Delta }_t^m& \ge w\frac{{(\mathcal{C}-2)}^2}{{\mathcal{C}}^3}\beta (1-\beta ){\parallel {\mathbf{\pi }}_0-{\mathbf{\pi }}_1\parallel }_2^2\hfill \\ & \ge \frac{1}{k}w\frac{{(\mathcal{C}-2)}^2}{{\mathcal{C}}^3}\beta (1-\beta ){\parallel {\mathbf{\pi }}_0-{\mathbf{\pi }}_1\parallel }_1^2\hfill \\ & \ge \frac{{\gamma }^2{G}_t^m}{\frac{{\mathcal{C}}^3}{{(\mathcal{C}-2)}^2}{(1-\gamma )}^2(t+1)k\sqrt{k\mathcal{C}-1}},\hfill \end{array}$$

(7)

where the last inequality is obtained as before.

Clearly the larger the objective $J(h)$ is at time t, the larger the entropy reduction ends up being. Let

$$\begin{array}{c}{\eta }^e=\frac{2\sqrt{2}\gamma }{(1-\gamma )\sqrt{lnk}},{\eta }^g=\frac{4\gamma }{(1-\gamma )\sqrt{k-1}},\hfill \\ {\eta }^m=\frac{4\gamma }{(1-\gamma )\sqrt{\frac{{\mathcal{C}}^3}{{(\mathcal{C}-2)}^2}k\sqrt{k\mathcal{C}-1}}}.\hfill \end{array}$$

(8)

For simplicity of notation assume ${\Delta }_t$ corresponds to either ${\Delta }_t^e$, or ${\Delta }_t^g$, or ${\Delta }_t^m$, and $G_t$ stands for $G_t^e$, or $G_t^g$, or $G_t^m$. Thus ${\Delta }_t>\frac{{\eta }^2{G}_t}{16(t+1)}$, and we obtain

$$G_{t+1}\le G_t-{\Delta }_t<G_t-\frac{{\eta }^2{G}_t}{16(t+1)}=G_t\left(1-\frac{{\eta }^2}{16(t+1)}\right).$$

One can now compute the minimum number of splits required to reduce $G_t$ below $\alpha$, where $\alpha \in [0,1]$, from this recurrence inequality. Assume ${log}_2(t+1)\in {\mathbb{Z}}^{+}$.

$$\begin{array}{cc}\hfill G_{t+1}& \le G_t\left(1-\frac{{\eta }^2}{16(t+1)}\right)\hfill \\ & =G_1\left(1-\frac{{\eta }^2}{16·2}\right)\left(1-\frac{{\eta }^2}{16·3}\right)\cdots (1-\frac{{\eta }^2}{16·(t+1)})\hfill \\ & =G_1\left(1-\frac{{\eta }^2}{16·2}\right)\prod _{t^{{}^{\prime }}=3}^4\left(1-\frac{{\eta }^2}{16·t^{{}^{\prime }}}\right)\cdots \hfill \\ & \prod _{t^{{}^{\prime }}=(2^r/2)+1}^{2^r}\left(1-\frac{{\eta }^2}{16·t^{{}^{\prime }}}\right)\cdots \prod _{t^{{}^{\prime }}=(2^{{log}_2(t+1)}/2)+1}^{2^{{log}_2(t+1)}}\left(1-\frac{{\eta }^2}{16·t^{{}^{\prime }}}\right),\hfill \end{array}$$

where $r=\{2,3,\cdots ,{log}_2(t+1)\}$. Recall that

$$\begin{array}{c}\prod _{t^{{}^{\prime }}=(2^r/2)+1}^{2^r}\left(1-\frac{{\eta }^2}{16·t^{{}^{\prime }}}\right)\le \prod _{t^{{}^{\prime }}=(2^r/2)+1}^{2^r}\left(1-\frac{{\eta }^2}{16·2^r}\right)\hfill \\ ={\left(1-\frac{{\eta }^2}{16·2^r}\right)}^{2^r/2}\le e^{-{\eta }^2/32},\hfill \end{array}$$

where the last step follows from Lemma A5. Also note that by the same lemma $\left(1-\frac{{\eta }^2}{16·2}\right)\le e^{-{\eta }^2/32}$. Thus,

$$G_{t+1}\le G_1{e}^{-{\eta }^2{log}_2(t+1)/32}.$$

(9)

Therefore to reduce $G_{t+1}\le \alpha$ (where $\alpha$’s are defined in Theorems 1–3) it suffices to make $t+1$ splits such that ${log}_2(t+1)\ge ln{\left(\frac{G_1}{\alpha }\right)}^{\frac{32}{{\eta }^2}}$ splits. Since ${log}_2(t+1)=ln(t+1)·{log}_2(e)$, where $e=exp(1)$. Thus,

$$ln(t+1)\ge ln{\left(\frac{G_1}{\alpha }\right)}^{\frac{32}{{\eta }^2{log}_2(e)}}\iff t+1\ge {\left(\frac{G_1}{\alpha }\right)}^{\frac{32}{{\eta }^2{log}_2(e)}}.$$

(10)

Recall that by resp. Lemmas 5–7 we have resp. $G_1^e\le 2lnk$, $G_1^g\le 2(1-\frac{1}{k})$, $G_1^g\le 2\sqrt{k\mathcal{C}-1}$. We consider the worst case setting (giving the largest possible number of split) thus we assume $G_1^e=2lnk$, $G_1^g=2(1-\frac{1}{k})$, and $G_1^g\le 2\sqrt{k\mathcal{C}-1}$. Combining that with Equations (8) and (10) yields statements of the main theorems. □

5.3. Proof of Theorem 4

We next proceed to directly proving the error bound. Recall that ${\pi }_{l,i}$ is the probability that the data point x corresponds to label i given that x reached l, i.e., ${\pi }_{l,i}=P(y(x)=i|x\mathrm{reached}l)$. Let the label assigned to the leaf be the majority label and thus lets assume that the leaf is assigned to label i if and only if the following is true ${\forall }_{\begin{array}{c}z=\{1,2,\cdots ,k\}\\ z\ne i\end{array}}{\pi }_{l,i}\ge {\pi }_{l,z}$. Therefore we can write that

$$\begin{array}{cc}\hfill ϵ(\mathcal{T})=& P(t(x)\ne y(x))\hfill \\ \hfill =& \sum _{l\in {\mathcal{L}}_t}{w}_{l}P(t(x)\ne y(x)|x\mathrm{reached}l)\hfill \end{array}$$

(11)

Let $i_l$ be the majority label in leaf l, thus ${\forall }_{\begin{array}{c}z=\{1,2,\cdots ,k\}\\ z\ne i_l\end{array}}{\pi }_{l,i_l}\ge {\pi }_{l,z}$. We can continue as follows

$$\begin{array}{cc}\hfill ϵ(\mathcal{T})=& \sum _{l\in {\mathcal{L}}_t}{w}_{l}P(t(x)\ne i_l|x\mathrm{reached}l)\hfill \\ \hfill =& \sum _{l\in {\mathcal{L}}_t}{w}_l(1-{\pi }_{l,i_l})\hfill \\ \hfill =& \sum _{l\in {\mathcal{L}}_t}{w}_l(1-max({\pi }_{l,1},{\pi }_{l,2},\cdots ,{\pi }_{l,k})\hfill \end{array}$$

(12)

Consider again the Shannon entropy $G(\mathcal{T})$ of the leaves of tree $\mathcal{T}$ that is defined as

$$\begin{array}{ccc}\hfill G_t^e& =& \sum _{l\in {\mathcal{L}}_t}{w}_l\sum _{i=1}^k{\pi }_{l,i}ln\frac{1}{{\pi }_{l,i}}\hfill \\ \hfill G_t^e& =& \frac{1}{lo{g}_{2}e}\sum _{l\in {\mathcal{L}}_t}{w}_l\sum _{i=1}^k{\pi }_{l,i}{log}_2\frac{1}{{\pi }_{l,i}}\hfill \end{array}$$

Note that

$$\begin{array}{cc}\hfill G_t^e=& \frac{1}{lo{g}_{2}e}\sum _{l\in {\mathcal{L}}_t}{w}_l\sum _{i=1}{\pi }_{l,i}{log}_2\frac{1}{{\pi }_{l,i}}\hfill \\ \hfill \ge & \frac{1}{lo{g}_{2}e}\sum _{l\in {\mathcal{L}}_t}{w}_l\sum _{\begin{array}{c}i=1\\ i\ne i_l\end{array}}{\pi }_{l,i}{log}_2\frac{1}{{\pi }_{l,i}}\hfill \\ \hfill \ge & \frac{1}{lo{g}_{2}e}\sum _{l\in {\mathcal{L}}_t}{w}_l\sum _{\begin{array}{c}i=1\\ i\ne i_l\end{array}}{\pi }_{l,i}\hfill \\ \hfill =& \frac{1}{lo{g}_{2}e}\sum _{l\in {\mathcal{L}}_t}{w}_l(1-max({\pi }_{l,1},{\pi }_{l,2},\cdots ,{\pi }_{l,k}))\hfill \\ \hfill =& \frac{1}{lo{g}_{2}e}ϵ(\mathcal{T}),\hfill \end{array}$$

(13)

where the last inequality comes from the fact that ${\forall }_{\begin{array}{c}i=\{1,2,\cdots ,\}\\ i\ne i_l\end{array}}{\pi }_{l,i}\le 0.5$ and thus ${\forall }_{\begin{array}{c}i=\{1,2,\cdots ,\}\\ i\ne i_l\end{array}}\frac{1}{{\pi }_{l,i}}\in [2;+\infty ]$ and consequently ${\forall }_{\begin{array}{c}i=\{1,2,\cdots ,\}\\ i\ne i_l\end{array}}{log}_2\frac{1}{{\pi }_{l,i}}\in [1;+\infty ]$.

6. Conclusions

This paper aims at introducing theoretical tools, encapsulated in the boosting framework, that enable the comparison of different multi-class classification objective functions. The multi-class boosting is largely ununderstood from the theoretical perspective [5]. We provide an exhaustive theoretical analysis of the objective function underlying the recently proposed LOMtree algorithm for extreme multi-class classification and explore the connection of this objective to entropy-based criteria. We show that optimizing this objective simultaneously optimizes Shannon entropy, Gini-entropy and its modified variant, as well as the multi-class classification error. We expect that discussed tools can be used to obtain theoretical guarantees in the multi-label [28,29,30] and memory-constrained settings (we will explore this research direction in the future). We also consider extensions to different variants of the multi-class classification problem [31,32] and multi-output learning tasks [33,34]. We thus plan to build a unified theoretical framework for understanding extreme classification trees.