arXiv CSopen access

Analytical study of the optimal combination of binary classifiers based on classifiers-induced partitioning of the training set

Analytical study of the optimal combination of binary classifiers based on classifiers-induced partitioning of the training set Jean-Marc Brossier ∗ and Olivier Lafitte †

arXiv:2607.14889v1 [cs.LG] 16 Jul 2026

Abstract. This paper studies an optimal linear combination of binary classifiers based on a logical structuration of the dataset via truth tables. The given classifiers partition data into equivalence classes, allowing for a rigorous analysis of the convexified empirical risk through a multidimensional generalization of classification calibrated functions. We establish sufficient conditions for the existence and uniqueness of the (global) point of minimum of the convexified empirical risk for any list of classifiers (when the number of classifiers is large, there frequently could be no point of minimum). In the case of three classifiers, our analysis allows to list all the configurations leading to either a unique solution, infima or non-unique points of minimum. Furthermore, we derive explicit analytical formulae for optimal weights using Exponential (Boost) and Logistic (Logit) loss functions, bypassing iterative optimization. The stability of the resulting classifier and the analysis of data quality can be evaluated through the introduction of the notion of ϕ-frontiers. Key words. Ensemble learning, combination of binary classifiers, convex optimization, truth tables, classifiersinduced partitioning AMS subject classifications. 68T05, 26B25, 62H30

1. Introduction. For supervised classification problems, a way of building a good classifier is to construct a linear combination of less accurate ones that achieves a better accuracy on a given training set. Many algorithms combine weak classifiers (slightly better than a random guess) to build a strong classifier (that improves accuracy and robustness) by taking advantage of the diversity of weak classifiers. This kind of algorithms is referred to as ensemble Learning. Two major categories are Bagging and Boosting. Bagging algorithms (Bootstrap Aggregating) build multiple instances of the same classifier on bootstrap samples of the dataset and combines them (Bagging Predictors were introduced by L. Breiman [3], random forest [4] is a famous instance). Boosting algorithms combine several weak classifiers sequentially, with each new classifier focusing on the errors of the previous ones; the most well-known and first practical implementation is AdaBoost (Adaptive Boosting) proposed by Freund and Schapire [8–10]. See for example [1] (p.303) for a more recent presentation of abstract boosting with a predefined list of classifiers. Two well-known extensions are Gradient Boosting [11] and XGBoost [6]. Other types of ensemble learning algorithms include Stacking [17] that combines predictions from several heterogeneous models using a meta-classifier for the final prediction and voting [14] that combines predictions from different classifiers by majority Pmor weighted voting. This paper concerns the identification of a resulting classifier sign 1 βj hj from a linear ∗

CNRS, Univ. Grenoble Alpes, Grenoble-INP, GIPSA-lab, Grenoble, France. [email protected] † Université Sorbonne Paris Nord, LAGA, UMR 7539. IRL CNRS-CRM 3457. Université de Montréal. Canada. [email protected]. 1

2

J.-M. BROSSIER, O. LAFITTE

combination of classifiers in a given list (1.1)

Hm := {h1 , . . . , hm }

known a priori. In our setup, we consider only logical classifiers, that is binary functions hj from a set of features X to {−1, +1}. Optimality of the resulting classifier is understood to mean it minimizes a risk based on the 0/1 logical loss function as well as fairly general convexifications of it (using classification calibrated loss functions). Note that our study does not construct sequentially the hj and is thus different from boosting algorithms. Although the number of misclassified points, the logical 0/1 risk, is a natural choice, P β h is achieved at an infinite number of values of β := its minimum associated with m 1 j j (β1 , · · · , βm ) and thus cannot lead to a choice of a unique new classifier (it is an ill-posed problem in the sense of Hadamard). Moreover, in an optimization context, it is neither convex nor continuous, which is problematic from an algorithmic point of view. That is where the classification calibrated functions leading to a convexified risk are useful. In chapter 7 of [15] and [2], different choices of loss functions are used. In this paper, we generalize the convexified risk introduced by Bartlett [2] to a mdimensional convexified risk. It is an extension of the elementary three-classifier approach presented in [5, 13] where the examples were aggregated into a partition of 8 subsets associated to the correctness or incorrectness of the respective decisions of the three classifiers: each subset contains the examples which return a given answer (true or false) for each classifier, we called this structuring the truth table. This approach relates to the concept of partitioning the input space found in ”Mixture of Experts” [12] or ”Local Ensembles” strategies (see for example [18]), where the behavior of classifiers determines regions of interest. However, instead of training local models, we use this partitioning to aggregate the training set information into a ”truth table” of size 2m , extracting equivalence classes of indistinguishable examples. This partitioning is generalized here to m elementary classifiers, where one defines a truth table whose columns are associated to 2m distinct subsets of indistinguishable (for the given set of m classifiers) examples. Seen through this prism (see definition 2.1), knowledge of the training set reduces to 2m weighted examples: this structuring leads to a compression of the training set; the resulting reduction in complexity comes at the price of the loss of some information. Note also that this renders tractable the 0/1 risk by reducing the identification of the minimum of the risk to the minimum of at most 2m values, independently of the number of examples. A sort of partitioning according to the same decisions of a single given weak classifier the training set is used in the work of Schapire & Singer [16], but they do not mix different classifiers for the partitioning. Minimizing the convexified risk amounts to optimize a function with m variables βj and 2m parameters, independently of the number of examples n; it depends only on the proportion of examples in each subset. It is then possible to carry out a complete study of the cost function (both analytically and computationally) to determine the best combination of elementary classifiers. In particular, it becomes possible to establish sufficient, or necessary and sufficient

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

3

conditions for the existence and the uniqueness of a point of minimum, which to the best of our knowledge is new. When it is possible to calculate this point of minimum, we obtain directly and analytically the optimal weighting coefficients, i.e. the resulting classifier and the number of misclassified points. We can then study analytically the stability of the resulting decision via the introduction of ϕ-frontiers, that is when a small modification of the training set changes the decision. Furthermore, we characterize the quality of the data based on the sensitivity of the decision to the choice of the classification calibrated loss function. As an important byproduct, we show that there exist training sets and classifiers for which there are cases of existence and non uniqueness of the point of minimum and of non existence (the function has an infimum), hence no possibility of constructing an optimal classifier. Moreover, detecting these cases of infimum is numerically hard: different classical optimization packages (generally designed for α-convex functions) can indeed return different ”solutions” for the search of a minimum of a function that has an infimum. Remark that: (i) Our study is based upon the existence of examples for which contradictions occur between the classifiers chosen, this allows to get a new classifier which classifies correctly more examples. To our knowledge, this remark seems not to have been used before. (ii) Once the list of classifiers is fixed, we have no way to distinguish two elements of the training set which return the same decisions on all classifiers. Writing the convexified risk using the data structuring we propose is a way of setting the problem that opens up many possibilities, including: • identification of situations in which a unique minimum exists. We have a necessary and sufficient condition (hence an exhaustive inventory of these situations) in the case of three classifiers and sufficient condition in the general case, see sections 3.3 and 5.2, • identification of cases of non existence or non uniqueness of a point of minimum. In this case, different regularizations yield a unique point of minimum. However, this limit does not construct a suitable classifier and falls down in a category of ϕ-frontier points (the data are not of good quality as mentioned above). • compute analytically the point of minimum of the convexified cost function for different choices of the loss function in the case of three classifiers, • adding a classifier (section 2.2), which is straightforward with the proposed structure, and improves the performance of an existing classifier set. The paper is organized as follows: Section 2 of this paper describes the structuration of the data (the set of examples) according to the given family of classifiers (in a predefined list) and deduce an original form for the empirical risk. Section 3 describes and uses the convexified risk. In this section, we introduce a multidimensional generalization of the classification calibrated function of Bartlett et al [2]. This m generalization introduces a set of parameters α in R2+ of sum equal to one. In section 4, we give the equations of the unique point of minimum of the convexified

4

J.-M. BROSSIER, O. LAFITTE

risk, when it exists, which is function of α and which leads to the definition of frontiers i.e. hypersurfaces in the set of parameters α across which the resulting optimal classifier changes. Section 5 proposes an exhaustive study in the case of three classifiers. We list all the cases of infimum or of multiple minima (theorem 5.9). In particular • we get a complete list of cases for which the infimum is zero. • when we have a point of infimum, a regularization yields (of course) a unique point of minimum which corresponds to a β ⋆ with a large norme. We will see later that it corresponds to a corner point (an uncertain decision). For the loss functions x → e−x (boost) and x → log2 (1 + e−x ) (logit) we calculate the exact solution of the minimization problem and we use these results in section 6 to draw an image of the frontiers (hypersurfaces in the parameter α for which there is a change of decision when changing α) in a few cases. All these ideas rely on a way of structuring the data based on contradictions between classifiers, which is the aim of section 2. 2. Structuration of the data. In order to do this, we introduce the general notations for the supervised learning problem for two classes. 2.1. Notations and setup of the problem. We deal with supervised learning with X = Rd for space characteristics associated with two labels {−1, +1}, attached to two classes. The goal is to classify an object (decide if its label is ±1) from x ∈ X . A supervised algorithm uses S = {(xi , yi ), i = 1 . . . n} ⊂ X × {−1, +1} to estimate a classifier h : X → {−1, +1}. P The empirical risk of the classifier h on S writes n1 (xi ,yi )∈S 1yi h(xi )<0 . From now on, we consider aP family of classifiers Hm := {h1 , . . . , hm }. The empirical logical (0/1) for the classifier sign βj hj is thus the function from Rm to R given by 1 X m (2.1) RS,H 1yi (P βj hj )(xi )<0 . 1•<0 (β) := n (xi ,yi )∈S

Definition 2.1 (Truth table). The truth table of a family of classifiers Hm := {h1 , . . . , hm } is the partition of S in 2m classes associated to Hm , where each set of the partition groups the examples which return the same decision for all classifiers, the number of such examples is called an entry of the truth table. These entries can be replaced by proportions. Note that, throughout this paper, we call decision the correctness with respect to the expected result and not the actual value predicted by the classifier: for a classifier hj , one defines the decision Gj (xi , yi ) = yi hj (xi ), therefore we note +1 the correct decisions, such as Gj (xi , yi ) = +1. Two cases can occur which leads to interesting results: Definition 2.2. 1. A classifier is perfect if it returns the same decision for all examples. 2. Two classifiers are equivalent if they return the same decision for each example. Remark that in all this study, replacing a classifier by its negation does not change anything; in particular, in definition 2.2 we include the case of a classifier returning the wrong

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

5

decision for all examples and we also include the case of two classifiers contradictory on all examples.

Classifier h3

+, +, + +, +, + +, +, +

+, +, −

−, −, − −, +, +

+, −, −

+, +, − +, −, −

Classifier h2

+, −, −

+, −, +

+, +, − +, +, +

+, +, +

+, +, +

Classifier h1 +, +, +

Figure 1: 16 examples and 3 classifiers which yields the truth table 1. The label yi of blue squares is −1, the label of red circles is +1. Labels such as +, −, + mean G1 = +1, G2 = −1, G3 = +1: h1 is true, h2 is false, h3 is true.

2.2. Introductory example with one to three classifiers. We construct truth tables associated with S and with a set of three classifiers shown in figure 1. One classifier. For 1 classifier {h1 }: h1 separates all but 2 examples (figure 1). For this given set of 16 examples S and classifier h1 : ♯{G1 (xi , yi ) = −1} = 2 and ♯{G1 (xi , yi ) = +1} = 14, n = 16 = 2 + 14, where ♯A denotes the number of elements of the set A. This begins a binary classification tree associated with a truth table with two columns. Note that it corresponds to the root of the tree in figure 2. Two classifiers. For 2 classifiers {h1 , h2 }, each column of the truth table is split into two columns hence leading to a truth table with four columns whose sum of elements is n. Three classifiers. For 3 classifiers {h1 , h2 , h3 }, each column is associated with the set of points in S that match a given configuration ϵ = (ϵ1 , ϵ2 , ϵ3 ) ∈ {−1, 1}3 of the three classifiers, the column header provides the cardinal of this set: ♯{i : G1 (xi , yi ) = ϵ1 , G2 (xi , yi ) = ϵ2 , G3 (xi , yi ) = ϵ3 }. This corresponds to the leaves of the tree on figure 2. The construction of all the columns is shown in the binary tree in figure 2. The resulting truth table is shown in table 1. The structure of the tables are independent of the order in the list of classifiers.

6

J.-M. BROSSIER, O. LAFITTE

1 0 G1 −1 −1 G2 −1 −1 G3 −1 +1

0 1 G1 −1 −1 G2 +1 +1 G3 −1 +1

3 1 G1 +1 +1 G2 −1 −1 G3 −1 +1

1 1 G1 −1 −1 G2 −1 +1

3 7 G1 +1 +1 G2 +1 +1 G3 −1 +1

4 10 G1 +1 +1 G2 −1 +1

2 14 G1 −1 +1

Figure 2: Binary tree and values for the three classifiers of figure 1.

In the next section, we extend this structuration of the data to m classifiers, which yields a new insight on the examples of S. 2.3. The truth table as a partition of the dataset. For m classifiers, for each example (xi , yi ), the classifier hj can be true (ϵj = Gj (xi , yi ) = +1) or false (ϵj = −1). For each answer of the type (TFFTF...FT), we can group all the examples that return this answer. This defines the partition of S of definition 2.1. Two labelings are natural (table or tree): the first one relies on the global list {h1 , . . . , hm }, and the second one is associated with a tree and relies on the ordered list {h1 }, {h1 , h2 }, ..., {h1 , . . . , hm }. The mapping between the two labelings is straightforward (see (2.3)). The two different labelings we propose for the truth table are as follows: Labeling of the truth table for a list of classifiers. The answer of the m classifiers is given by ϵ = (ϵ1 , . . . , ϵm ) ∈ {−1, 1}m . To each ϵ one associates k(ϵ) :=

m X

2m−j

j=1

1 + ϵj . 2

This transformation is a bijection from {−1, +1}m to {0, 2m − 1}, whose reciprocal is denoted by k → ϵ(k). The truth table associated with (S, Hm ) is characterized by m αS,Hm = (α0S,Hm , . . . , α2S,H m −1 )

where S,Hm αk(ϵ) = αS,Hm (ϵ) =

♯{i : yi hj (xi ) = ϵj , ∀j} ♯S

P2m −1 S,Hm is the proportion (αkS,Hm ∈ Q+ and = 1) of examples of S in the logical k=0 αk configuration ϵ. Introduce the set of real positive parameters which is used in the sequel (2.2)

A

m

m = R2+ ∩ {

m −1 2X

k=0

αk = 1}.

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

7

The configuration αS,Hm belongs to Am . Note that in this section and in this labeling, α1 (for example) has different expressions depending on the choice of m. While we will mostly use the present notations in this paper, we introduce in the next paragraph a labeling which overcomes this notational problem. Tree structure labeling of the truth table. When m is given in advance, the labeling proposed in the previous subsection is natural. If one wants to refine the analysis by increasing the number of classifiers, an incremental labeling introduced in [7] for genealogical purposes in the 16th century, called later the SosaStradonitz numbering, is a very good choice which allows to label, independently of the number of classifiers, each class of the classification tree. This alternative labeling is illustrated in figure 3 (for example c4 = c8 + c9 , c6 = c12 + c13 , · · · ). c1 = 16

c2 = 14

c4 = 10 c8 q 7

c3 = 2

c5 = 4 c9 q 3

c10 q 1

c6 = 1 c11 q 3

c12 q 1

c7 = 1 c13 q 0

c14 q 0

c15 q 1

Figure 3: Alternative labeling of the classification tree

α0 c8 G1 −1 G2 −1 G3 −1 Cardinal 1

α7 c15 +1 +1 +1 7

α4 c12 +1 −1 −1 3

α3 c11 −1 +1 +1 1

α2 c10 −1 +1 −1 0

α5 α1 α6 c13 c9 c14 +1 −1 +1 −1 −1 +1 +1 +1 −1 1 0 3

Table 1: Truth table for the partition associated to the m = 3 classifiers and n = 16 examples P given in figure 1. Note that n = 16 = 15 c and αi = c8+i /n. i i=8

Proposition 2.3. We have the following properties: (i) The truth table is independent of the order of the list Hm := {h1 , . . . , hm }. (ii) When two classifiers hj , hk return the same answer for all examples, the partition generated by Hm has 2m−1 empty columns and the other columns return the partition generated by Hm \ hk . This is also the case when hk is the negation of hj . Proof. (i) for a permutation σ of the classifiers h1 , · · · , hm , there exists a matrix M (σ) of size 2m+1 ×

8

J.-M. BROSSIER, O. LAFITTE σ(H )

σ(H )

Hm ⊤ m 2m+1 such that (c1 m , · · · , c2m+1m )⊤ = M (σ)(cH 1 , · · · , c2m+1 ) . This does not change the structure of the problem. (ii) We can identify the cases where we have two equivalent classifiers or two contradictory classifiers: we check that the classifiers hp , hq , p < q are equivalent in the list {h1 , . . . , hm } with respect to the set of examples S if and only if, for all k such that ϵp (k) + ϵq (k) = 0, αk = 0 and two classifiers are contradictory if and only if, for all k such that ϵp (k) = ϵq (k), αk = 0. For example h1 and h3 are equivalent if and only if c9 = c11 = c12 = c14 = 0, h2 and h3 are contradictory if and only if c8 = c11 = c12 = c15 = 0. Note that, when there is a pair of classifiers which provide the same logical answer or the opposite one, we can suppress one of the two classifiers.

We can also perform the two following elementary operations: Adding a classifier hm+1 to the list {h1 , . . . , hm } (easy use of the Sosa-Stradonitz labeling). It corresponds to a splitting of each column of the truth table into two new columns. Let ϵ ∈ {−1, 1}m+1 . For ϵ′ ∈ {−1, 1}m , one has indeed nαS,Hm+1 ((ϵ′ , 1)) = ♯{i, (yi hj (xi ))j=1,...,m = ϵ′ , yi hm+1 (xi ) = 1} and nαS,Hm+1 ((ϵ′ , −1)) = ♯{i, (yi hj (xi ))j=1,...,m = ϵ′ , yi hm+1 (xi ) = −1}. Notice that αS,Hm (ϵ′ ) = αS,Hm+1 ((ϵ′ , −1)) + αS,Hm+1 ((ϵ′ , 1)) where (ϵ′ , ±1) describes {−1, 1}m+1 . Note that in the Sosa-Stradonitz notations for the nodes of the tree, this corresponds to splitting (2.3)

S,H

S,H

S,Hm m+1 m+1 m nαk(ϵ) = cS,H + c2k(ϵ)+1 . k(ϵ) = c2k(ϵ)

Removing a classifier from the list. We put the classifier we want to remove at the end of the list through the permutation σj of Hm exchanging hj and hm , and we obtain σ (H ) σj (Hm ) H \h for all l ∈ {1, · · · , 2m − 1}. cl m j = c2lj m + c2l+1 2.4. Rewriting the logical risk. For each β ∈ Rm one introduces, for ϵ ∈ {−1, +1}m , thus for k(ϵ) ∈ {0, · · · , 2m−1 − 1} (2.4)

Pm Xk(ϵ) (β) = j=1 ϵj βj = ϵ · β X2m −1−k(ϵ) (β) = −Xk(ϵ) ,

which leads to the definition of pairs of decisions: Definition 2.4 (pair). Let α = (α0 , . . . , α2m −1 ) ∈ Am . A pair with label kl ∈ 0 . . . 2m−1 − 1 is the couple (αkl , α2m −1−kl ) := (α(ϵ(kl )), α(−ϵ(kl ))) , P m−j ( 1+ϵj + 1−ϵj ) = 2m − 1, ∀ϵ ∈ {−1, 1}m . thanks to k(ϵ) + k(−ϵ) = m j=1 2 2 2

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

9

This defines Xk (β) for all k ∈ {0, · · · , 2m − 1}. For the sake of simplicity of notations, we will write Xk instead of Xk (β) throughout the paper. For example X0 = −β1 − β2 , X1 = −β1 + β2 , ..., of figure 9 follow this definition for m = 2. m m (β) = min RS,H As R1S,H 1•<0 is a union of some cones (for example, two different sectors in •<0 2 R or different infinite tetrahedrons in R3 ), there is no criterion to choose a precise value of β and, since different values of β may lead to the minimum value of the empirical risk, these different solutions could provide different answers on a new example. As examples returning the same answers for all the classifiers of Hm cannot be distinguished, the complexity depends only on m, which allows to rewrite the empirical risk as a sum on the partition of size 2m given by the truth table. In particular, the complexity does not grow when the number n of examples grows. Since the same value of ϵ is associated with all (xi , yi ) in one column of the truth table, m (β) can be rewritten on the columns of the truth table, each being characterized by RS,H 1 Gj (xi , yi ) = ϵj , ∀j: X X 1 X 1 m (β) = R1S,H 1(P βj Gj (xi ,yi ))<0 = 1ϵ·β<0 . •<0 n n m

(xi ,yi )∈S

ϵ∈{−1,1}

i:Gj (xi ,yi )=ϵj ,∀j

Counting all the examples in each column of the truth table, one has:   X X X ♯{i : Gj (xi , yi ) = ϵj , ∀j} 1  1ϵ·β<0 = 1ϵ·β<0 . n n m m ϵ∈{−1,1}

i:Gj (xi ,yi )=ϵj ,∀j

ϵ∈{−1,1}

The function of β is then characterized by the signs of all Xk : m RS,H 1•<0 (β) =

X

α

ϵ∈{−1,1}m

S,Hm

(ϵ)1ϵ·β<0 =

m −1 2X

αkS,Hm 1Xk <0 .

k=0

As ϵ(2m − k) = −ϵ(k), we pair αS,Hm (ϵ(k)) and αS,Hm (ϵ(2m − k)) associating Xk = X(ϵ(k)) (and −Xk = X(−ϵ(k))), k ∈ 0 · · · 2m−1 − 1 which yields, for β ∈ Rm \ ∪{Xk = 0}: m RS,H 1•<0 (β) =

2m−1 X−1

m αkS,Hm 1Xk <0 + α2S,H m −1−k 1Xk ≥0 .

k=0

This is the structuration of the data that we deal with from now on. Note that in this structuration, we deal with two different sets of signs: the signs of yi hj (xi ) = Gj (xi , yi ) in {−1, +1}m which relate to the set of examples and decisions and the signs of Xk , k = 0 · · · 2m−1 − 1 which separate regions of Rm . The classical method is to replace 1•<0 by ϕ(•) to convexify the logical risk in order to use the powerfulness of convex optimization tools. The convexified risk is denoted in the sequel (2.5)

m RS,H (β) = ϕ

2m−1 X−1 k=0

m αkS,Hm ϕ(Xk ) + α2S,H m −1−k ϕ(−Xk ).

10

J.-M. BROSSIER, O. LAFITTE

Note that, for m = 1, (2.6)

1 (β) = α0S,H1 ϕ(β1 ) + α1S,H1 ϕ(−β1 ) = α0S,H1 ϕ(β1 ) + (1 − α0S,H1 )ϕ(−β1 ). RS,H ϕ

3. General classification calibrated functions. The main tool used to study this convexified logical risk is the natural generalization of an object introduced by Bartlett et al [2]. This abstract object does not refer to any dataset. 3.1. The convexified ϕ-risk of Bartlett. This object is the generic conditional ϕ-risk1

(3.1)

(α ,1−α0 )

Cϕ 0

(β) = α0 ϕ(β) + (1 − α0 )ϕ(−β).

They deduced what they called optimal conditional ϕ-risk (α ,1−α0 )

H(α0 ) = inf Cϕ 0 R

(β),

and Bartlett al [2] (p.141) introduced a function β ⋆ (α0 ) from (0, 1) to R which is the arg min of H. They restricted their study to loss functions ϕ that are classification calibrated which is equivalent, in the case ϕ convex, to ϕ differentiable at 0 and ϕ′ (0) < 0. They used such functions to deduce results on the control of the generalized ϕ-risk by the empirical ϕ-risk ( [2], theorem 4, p.148). Note that the conditional ϕ-risk has a unique point of minimum for α0 (1 − α0 ) ̸= 0 hence H is well defined for α0 (1 − α0 ) ̸= 0. (0,1) (1,0) Note that when α0 ∈ {0, 1}, H(α0 ) = 0, but it is the infimum of Cϕ or Cϕ . In this study we use functions ϕ more regular than the classification calibrated functions introduced in section 2.2 of [2] and we generalize the notion of conditional ϕ-risk of [2] to the multidimensional case for loss functions which are classsification calibrated and at least C 1 . Definition 3.1 (regularly classification calibrated function). A function ϕ is said to be regularly classification calibrated if, in addition to being classification calibrated, it is of class C 1 , strictly convex, strictly decreasing (ϕ′ < 0), and of even part infinite at infinity. Note that this function satisfies ϕ′ → l at −∞, where l is strictly negative (possibly infinite). Three usual choices for ϕ are depicted on figure 4. A common choice in neural networks is x → ϕ(x) = hinge(x) = max(0, 1 − x). However, even if its local derivative is very simple, this function does not have the required properties: it is neither C 1 nor strictly convex. The two other functions of figure 4, x → exp(−x) and x → log2 (1 + e−x ), are regular C 1 and strictly convex and yield analytic results (see section 5). None of these functions has a minimum however their even part is infinite at infinity and thus has a minimum (see [2]). 1

The corresponding notation of Bartlett is Cη (α) = ηϕ(α) + (1 − η)ϕ(−α).

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

11

log2 (1 + exp(−x)) exp(−x) hinge(x)

1x<0

1 0

Figure 4: Classical classification calibrated functions ϕ. Note that hinge(x) ∼±∞ ln(2) log2 (1+ exp(−x)) (α ,1−α0 )

3.2. Generalization. One generalizes Cϕ 0 and 2m parameters α ∈ Am .

(β) to a function of m variables β ∈ Rm

Definition 3.2 (generic multidimensional ϕ-risk). Let ϕ be regularly classification calibrated (definition 3.1). A natural generalization to m variables of the generic conditional ϕ−risk of Bartlett et al [2] is the function of m variables P2m −1 αk ϕ(Xk ) Cα ϕ (β) = (3.2) P2k=0 m−1 −1 αk ϕ(Xk ) + α2m −1−k ϕ(−Xk ) = k=0 P with αk = 1. It is called in the sequel the generic multidimensional ϕ-risk, of parameter α. Remark that one may link the multidimensional ϕ-risk with the conditional ϕ-risk introduced by Bartlett [2] through (3.3)

Cα ϕ (β) =

2m−1 X−1

(η ,1−ηl )

(αl + α2m −1−l )Cϕ l

(Xl )

l=0

where ηl = αl /(αl + α2m −1−l ). 3.3. Existence and uniqueness of a point of minimum of Cαϕ . Unlike the one-dimensional ϕ-risk, the cases of unique point of minimum of the multidimensional ϕ-risk are less simple. However, a very simple sufficient condition on α (namely αj > 0, ∀j) implies existence and uniqueness of the point of minimum of the multidimensional ϕ-risk under the hypotheses of definition 3.1 (see lemma 3.9). We are then able to identify the sign of the corresponding Xk and the regions of stability of these signs. Recall that these signs are what is needed for constructing the resulting classifier when α is deduced from a truth table. 3.4. Regular points. Definition 3.3 (regular points in Am ). Assume ϕ satisfies definition 3.1. The 2m -uplet α ∈ Am is a regular point for ϕ when the function Cα ϕ has a unique point of minimum denoted by min ⋆ βϕ (α). It is the generalization of β (α0 ).

12

J.-M. BROSSIER, O. LAFITTE

min := The functions βϕmin and Xϕ,k m and α, and are continuous in α.

Pm

min m−1 − 1 depend only on ϕ, j=1 ϵj (k)(βϕ )j , k = 0 . . . 2

Note that the regularity of a point α is an intrinsic property (it does not depend on ϕ) and that it is true when all components of α are non zero. The latter comes from the fact that in this case, the function Cα ϕ is infinite at infinity. The former comes from the properties of ϕ. In the case m = 3, we propose an exhaustive study of all the points of A3 in section 5. This exhaustive study shows that, for m = 3, the condition α regular does not depend on ϕ satisfying definition 3.1. This exhaustive study is beyond our reach for larger values of m. We can still show that m + 1 non-zero coefficients at least are needed for the existence and uniqueness of a point of minimum. See lemma 3.4 that follows. Lemma 3.4. For all m ≥ 3, • If less than m + 1 coefficients are non-zero, there cannot be a unique point of minimum. Qm−1 • The condition α2m −1 k=0 Q α2k > 0 and all others are zero leads to a unique point of minimum. It is the case also for α0 m−1 k=0 α2m −1−2k > 0. These are cases of existence and uniqueness of the point of minimum Q for exactly m + 1 non-zero coefficients. • The condition α0 m−1 0 and all others are zero leads to an infimum. k=0 α2k > Q It is the case also for α2m −1 m−1 k=0 α2m −1−2k > 0. These are also cases of exactly m + 1 non-zero coefficients. Proof. • For the proof of the first item, it is enough to notice that {Xj , αj ̸= 0} is not a system of coordinates of Rm if {j : αj ̸= 0} is of cardinal less than m − 1, hence there cannot be uniqueness. When {j : αj ̸= 0} is of cardinal m and if {Xj , αj ̸= 0} is a system of coordinates of Rm , the function has an infimum equal to 0. When {j : αj ̸= 0} is of cardinal m and if {Xj , αj ̸= 0} is not a system of coordinates of Rm , there cannot be P uniqueness. P m−1

X

m−1

X

2k 2k • Owing to X0 = k=0 and X2m −1 = − k=0 , the function m−2 Pm−1 m−2 α0 ϕ(X0 )+ k=0 α2k ϕ(X2k ) has all its partial derivatives with respect to X2k strictly negative, hence no solution for the Euler equations: this function has an infimum which proves the second item. P • For the function α2m −1 ϕ(X2m −1 ) + m−1 k=0 α2k ϕ(X2k ), a possible point of minimum solves

F (X2m −1 ) := (m − 2)X2m −1 +

m−1 X

(ϕ′ )−1

k=0



 α2m −1 ϕ′ (X2m −1 ) = 0 α2k (m − 2)

α m −1 α m −1 ϕ′ (X2m −1 ) is α k2(m−2) l. If there exists a k such that this limit is > l, The limit of α k2(m−2) 2 2 α2m −1 ′ there exists X∗ such that α k (m−2) ϕ (X∗ ) = l, We choose the largest X∗ by inspection of 2

all such k and we call k0 one of the corresponding k. 2m−1 → X∗ , X2k0 solution of P When′ X α m −1 −1 ( α2m −1 ϕ′ (X ϕ′ (X2k0 ) = α k 2 (m−2) ϕ′ (X2m−1 ) goes to −∞, hence m−1 (ϕ ) 2m−1 )) → −∞ k=0 α k (m−2) 2 0

hence F → −∞ for X → X∗+ .

2

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

13

α m

−1 If α k2(m−2) l > l for all k, then X2m −1 → −∞ implies that, for all k, X2k goes to a finite limit. 2 Hence F → −∞ when X2m −1 → −∞. For the other limit X2m −1 → +∞, F goes to +∞. As F is continuous, strictly increasing, the existence and uniqueness of the solution of F (X) = 0 follows.

Remark that {X2k }0≤k≤m−1 is a system of coordinates in Rm , hence each βp is a linear combination of {X2k }0≤k≤m−1 . 3.4.1. General definitions and properties. Proposition 3.5. Assume α is a regular point in Am for ϕ regularly classification calibrated and that ϕ of class C 2 . min are of class C 1 on Am ∩ {α > 0 , ∀k}. The functions βϕmin and Xϕ,k k Proof. Assume α ∈ Am ∩ {αk > 0 , ∀k}. There exists a neighborhood of α included in ′ ′ Am ∩{αk > 0 , ∀k} such that Cα ϕ is strictly convex for α in this neighborhood, hence existence ′ and uniqueness of the point of minimum of Cα ϕ solving the Euler equations, the regularity of min min Xϕ,k and βϕ follows from the implicit functions theorem. Note that the point of minimum depends on ϕ, we enforce this property in the notation (unlike the notation proposed by Bartlett). Corollary 3.6. If α is a regular point in Am (definition 3.3), there exists a neighborhood of m α ∈ R2+ in which this definition holds. m If, for α, definition 3.3 does not hold, there exists a point in any neighborhood of α ∈ R2+ for which this definition holds. Proof. The property of having a unique point of minimum is an open property, that is there exists a neighborhood of a point where this property is true in which it is still true. If, for α, definition 3.3 does not hold, that means that some components of α are zero, hence any neighborhood of α contains a point α′ for which all components of α′ are non zero: case of existence of an unique minimum. The following definition allows a first glance at classification calibrated functions: Definition 3.7 (properties of pairs). • For k ≤ 2m−1 − 1, the pair k is full iff αk α2m −1−k > 0, the pair k is empty iff αk = α2m −1−k = 0, the pair k is trivial iff αk α2m −1−k = 0 and αk + α2m −1−k > 0. • A family k1 , · · · , km of m pairs is complete if all these pairs are full and if β → (Xk1 , · · · , Xkm ) is a bijection. Lemma 3.8. If at least one pair is full, the infimum of Cα ϕ is strictly positive. Proof. If a pair k is full, the multidimensional ϕ-risk Cα ϕ is always greater than (αk + α2m −1−k )H(

αk ) > 0. αk + α2m −1−k

Hence, if the infimum is zero, no pair is full. α

α m

2 −1−k k ( α +α m , ) k 2 −1−k αk +α2m −1−k m As ϕ > 0, for all β, Cα (β) ≥ (α + α )C (Xk ), hence the k 2 −1−k ϕ ϕ

result and the consequence on no full pair.

14

J.-M. BROSSIER, O. LAFITTE

A simple criterion for α to be regular (definition 3.3) for ϕ regularly classification calibrated (definition 3.1) is: Lemma 3.9. When ϕ is regularly classification calibrated (definition 3.1), a sufficient conα dition for Cα ϕ to have a unique point of minimum on {β : Cϕ (β) ≤ 1} is that there exists a sub-family of indexes in α which is complete. Proof. The proof of this lemma will provide as well the equations for finding the point of minimum β(α). m The function Cα ϕ is a function of Xk , k = 0 · · · 2 −1. The number of independent relations m m between Xk , k = 0 · · · 2 − 1 is equal to 2 − m because β ∈ Rm . Let k1 , · · · , km a set of indexes of independent coordinates generating full pairs. Then, according to (3.3) (3.4) m X X (ηk ,1−ηkl ) (η ,1−ηk ) α (αkl + α2m −1−kl )Cϕ l (αk + α2m −1−k )Cϕ k (Xk ). (Xkl ) + Cϕ (β) = l=1

k∈k / 1 ,··· ,km

P (ηkl ,1−ηkl ) (Xkl ) is infinite at infinThe function (Xk1 , · · · , Xkm ) → m l=1 (αkl + α2m −1−kl )Cϕ ity on Rm and is strictly convex on Rm . If one adds any positive strictly convex function to it, the two properties hold. Hence, the function Cα ϕ is infinite at infinity hence has a point of global minimum, and is strictly convex, hence this minimum is unique. This ends the proof of lemma 3.9. Note that one can have a unique point of minimum of the function Cα ϕ even if α does not satisfy the hypothesis of lemma 3.9 (see the first alinea of 3.4 and theorem 5.9 in the case m = 3 when 5 or 6 coefficients αj are non zero). Lemma 3.10. If, on the training set, two classifiers hp and hq are equivalent or if one classifier hq is perfect (definition 2.2), there is not existence and uniqueness of a point of minimum of the function Cα ϕ and the study reduces to the study of the m − 1 classifiers {h1 , · · · , hm } \ hq . Note that, in these two cases, half of the columns in the truth table are zero and no pair is full. Proof. In the case hp and hq equivalent, there exists a function K such that Cα ϕ (β) = K(βp + βq , β̃) where β̃ = {β1 , · · · , βm } \ {βp , βq }. If K has a unique point of minimum on Rm−1 then Cα ϕ has an infinite number of points of minimum. If K has an infimum, that is the same for Cα ϕ. α ˜q ˜q In the case hq perfect, Cϕ (β) = exp(−βq )Cα ϕ (β ) where β = β|βq =0 , hence 0 is the α infimum of Cϕ (βq → +∞). 4. The optimal combination of classifiers. We then provide a rigorous accurate analysis of the optimal combination of these classifiers for any convexified cost function2 satistifying definition 3.1. We obtain existence and Pmuniqueness results. A resulting classifier is x → sign j=1 βj hj (x) for any choice of β. The convexified empirical risk of false decision is (equation (2.5)) : 2

Note that this is the situation described in [1] (p.303) for ϕ = 1/ exp.

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

15

P m−1 m m (β) = 2k=0 −1 (αkS,Hm ϕ(Xk ) + α2S,H RS,H m −1−k ϕ(−Xk )). ϕ We are now ready to construct the optimal classifier associated with S, Hm for each function ϕ satisfying definition 3.1. Definition 4.1 (regular basis of classifiers). The classifiers Hm form a regular basis of classifiers for S if and only if αS,Hm is a regular point (see definition 3.3). min (αS,Hm ), The value of Xk associated with this unique point of minimum is denoted by Xϕ,k k = 0 . . . 2m−1 − 1. Remark 4.2. If S ′ ⊃ S and if Hm form a regular basis for S, it forms a regular basis for S ′ . In other words, if for a training set and a list of classifiers we obtain existence and uniqueness of a point of minimum of the empirical convex risk, we can add any number of examples without destroying this property but changing the point of minimum. Note that the notion of regular basis of classifiers is a notion associated with H and S while the notion of regular point α (definition 3.3) is not, it is only an abstract property of α. Theorem 4.3. Adopt the convention sign(0) = 1. S,Hm m When classifier (depending on ϕ) is h⋆ = Pm αmin is a regular point of A , the optimal min (αS,Hm )) for k = 0, . . . , 2m − 1. sign( j=1 βϕ,j hj ), which gives the decision sign(Xϕ,k Proof. This theorem is a straightforward consequence of proposition 3.5. We highlight that the case of three classifiers, studied thoroughly in theorem 5.9, present some interesting features: Remark 4.4. Having a complete sub family is a sufficient condition for existence and uniqueness of the point of minimum. It is not a necessary condition: see theorem 5.9, item (iii). Remark 4.5. There are cases where it is impossible to construct an optimal classifier whatever the convexification is. See theorem 5.9, items (ii), (iii), (iv). P Remark 4.6. Note that the resulting classifier sign( βj Gj ) does not change if one multiplies β by λ > 0, hence even the cases of infima can return a ”limit resulting classifier” by βl m m considering the limit β ⋆ of ||β when βl is a sequence such that RS,H (βl ) → inf RS,H . ϕ ϕ l || ⋆ However, β does not keep all the information contained in the truth table. Indeed, the limit value X ⋆ associated with β ⋆ is δji0 (all coordinates are zero except one). It is a corner point (see definition 6.1 below). 5. All you want to know on the case of at most three classifiers. We describe in a first subsection the combination of two classifiers, using both the 0/1 risk and the convexified one, and show that, in the case of two classifiers, the optimal combination yields the best classifier which can be the opposite of one of two classifiers considered. 5.1. The case of two classifiers. We consider now two classifiers h1 and h2 and study the classifier sign(β1 h1 + β2 h2 ). Note that, for each example (xi , yi ) ∈ S, we have yi sign[(β1 h1 +β2 h2 )(xi )] = sign[β1 yi h1 (xi )+β2 yi h2 (xi )] = sign[β1 G1 (xi , yi )+β2 G2 (xi , yi )]. Since yj ∈ {±1} and hj (·) ∈ {±1}, we have Gj (xi , yi ) ∈ {±1} and (β1 G1 + β2 G2 )(·) ∈ {±β1 ± β2 }.

16

J.-M. BROSSIER, O. LAFITTE

0/1 loss (Logical risk). Lemma 5.1 (Properties of the logical risk for two classifiers). The resulting classifier is the best of the four classifiers (h1 , h2 , −h1 , −h2 ). Proof in section A. Convexified risk. Lemma 5.2 (Properties of the convexified risk for two classifiers). (i) The convexified cost function has a unique point of minimum if and only if no column of the truth table is empty. This point of minimum, given in appendix A, returns a resulting classifier which gives the same answer on the set of examples S as for the 0/1 risk. min h + β min h ) depends on ϕ hence the risk of generalization This resulting classifier sign(β1,ϕ 1 2,ϕ 2 for new examples depends on ϕ. (ii) If only one column is empty, the convexified cost function has a strictly positive infimum. (iii) If two columns only are empty: (a) and if they do not belong to the same pair, the convexified cost function has zero as infimum. (b) and if they belong to the same pair, the convexified cost function has a non-unique minimum strictly positive. Proof. The convexified cost function is α0S,H2 ϕ(X0 ) + α3S,H2 ϕ(−X0 ) + α1S,H2 ϕ(X1 ) + α2S,H2 ϕ(−X1 ). i. If no column is empty, min (αS,H2 ) and αS,H2 ϕ(X ) + α0S,H2 ϕ(X0 ) + α3S,H2 ϕ(−X0 ) has a unique point of minimum Xϕ,0 1 1 min (αS,H2 ). The minimum of RS,Hm is strictly α2S,H2 ϕ(−X1 ) has a unique point of minimum Xϕ,1 ϕ positive. ii. If only one column is empty, two cases: min (αS,H2 ) is uniquely determined and X goes • If α0S,H2 or α3S,H2 is equal to zero, Xϕ,1 0 min (αS,H2 ) to infinity. The value of the infimum is α1S,H2 ϕ(X1 ) + α2S,H2 ϕ(−X1 ) at Xϕ,1 and is strictly positive. min (αS,H2 ) is uniquely determined and X goes • If α1S,H2 or α2S,H2 is equal to zero, Xϕ,0 1 min (αS,H2 ) to infinity. The value of the infimum is α0S,H2 ϕ(X0 ) + α3S,H2 ϕ(−X0 ) at Xϕ,0 and is strictly positive. iii. If two columns are empty, two cases (depending on which the two columns belong to the same pair or not): (a) If α1S,H2 = α3S,H2 = 0, the infimum of the function is zero (when X1 → +∞ and X0 → −∞). This is also the case when α0S,H2 = α2S,H2 = 0. min (αS,H2 ) is uniquely determined and the function does not (b) If α0S,H2 = α3S,H2 = 0, Xϕ,1 depend on X0 , hence there is a non-unique strictly positive minimum. This is also the case when α1S,H2 = α2S,H2 = 0.

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

17

Lemma 5.3. When a column is empty, there is an infimum (see lemma 5.1). The construction of a new classifier is undecidable. It corresponds to a situation on the frontier (see section 6). Proof. When there is an infimum, it is not mathematically possible to construct a unique solution of the optimization problem, hence a unique optimal classifier. Traditionally, one uses a regularization to overcome the problem. Three strategies are possible : (X ,X ∗ ) 1 - The first strategy is to consider the limit of the point ||(X00 ,X1∗ )|| when X0 → +∞. This 1

limit is (1, 0) and thus the limit of β is (− 21 , 21 ). However, one verifies that the sign of X1∗ determines a decision, information which is no longer present in the direction (− 12 , 21 ) (and the direction ( 21 , − 12 ) is equally possible). 2 - The second strategy is the regularization of the truth table. In this case one can either consider adding ϵ to the empty column of the truth table or adding ϵ to all elements of the truth table. The function we seek the (unique) minimum of is α0S,H2 ϕ(X0 ) + ϵϕ(−X0 ) + α1S,H2 ϕ(X1 ) + α2S,H2 ϕ(−X1 ). The unique point of minimum reads X0∗ = β ⋆ (

α0S,H2 α0S,H2 + ϵ

), X1∗ = β ⋆ (

α1S,H2 α1S,H2 + α2S,H2

),

Its limit when ϵ → 0 is then (β ⋆ (1), X1∗ ) = (+∞, X1∗ ) and for all ϵ > 0, it provides a value of (β1 , β2 ). When adding ϵ to all columns of the truth table, one obtains X0∗ = β ⋆ (

α0S,H2 + ϵ α0S,H2 + 2ϵ

), X1∗ = β ⋆ (

α1S,H2 + ϵ α1S,H2 + α2S,H2 + 2ϵ

).

This is an equivalent strategy, the limit is identical, as well as the resulting signs of X0∗ , X1∗ . 3 - The third strategy is to consider a quadratic regularization (called Tikhonov regularization). Then one studies 1 α0S,H2 ϕ(X0 ) + α1S,H2 ϕ(X1 ) + α2S,H2 ϕ(−X1 ) + ϵ(X02 + X12 ). 2 One obtains the Euler equations on the point of minimum of 1 α1S,H2 ϕ(X1 ) + α2S,H2 ϕ(−X1 ) + ϵX12 2 (which converges to X1∗ when ϵ → 0+ ) and on the point of minimum of α0S,H2 ϕ(X0 ) + 21 ϵX02 . For this point, the Euler equation is εX0 + α0S,H2 φ′ (X0 ) = 0 ⇐⇒

X0 α0S,H2 = − φ′ (X0 ) ε

18

J.-M. BROSSIER, O. LAFITTE

α0S,H2 X0 ∈ R∗− , X0 < 0, φ′ (X0 ) < 0 =⇒ ′ <0 ε φ (X0 )

for X0 < 0,

hence solutions are in (0, +∞). 0 For X0 → +∞, φ′ (X0 ) → 0− , φ′X (X0 ) → −∞. 0 For X0 → 0, φ′X (X0 ) → 0, there exists at least a solution of the Euler equation (and it is

unique thanks to coerciveness) denoted by X0 (−α0S,H2 /ε), which goes to +∞ when ε → 0+ . In all these strategies, after normalization we obtain a resulting classifier where one of the values of Xj is close to zero. In this particular case, the result is independent of the classification calibrated function. We observe already that the situation of the conditional ϕ-risk in R2 is more complicated than the one defined by Bartlett et al [2]: cases of infimum and cases of no unique minimum are present when α0S,H2 α1S,H2 α2S,H2 α3S,H2 = 0. More interesting results for the type of structure seen above appear with at least 3 classifiers: first of all, the necessary and sufficient condition to define βϕmin (α) is more complicated than α0 · · · α7 > 0 and this point of minimum does not return always the same answer on the set of examples S as for the logical risk, the optimal combination of the classifiers depends on ϕ. In the rest of this section, dedicated to the case of three classifiers, we perform a complete study of all the cases where there is a unique minimum, a non unique minimum and an infimum for the generical conditional ϕ-risk for any ϕ and, in the case of two particular functions ϕ, we calculate the point of minimum and we derive the equations of the frontiers (see definition 6.1). 5.2. The case of three classifiers. 0/1 loss (Logical risk). In the case of three classifiers, the empirical risk is: 3 RS,H 1•<0 (β) =

3 X

S,H3 αjS,H3 1Xj <0 + α7−j 1Xj ≥0 .

j=0

To each value of β = (β1 , β2 , β3 ) ∈ R3 corresponds the signs of Xi , thus the value of R1•<0 (β) in a finite list. Each element of the list corresponds to β in a region of R3 , which is the intersection of 4 half-spaces, because the empirical risk is piecewise constant, an infinite number of values of β returns the minimum value. S,H3

Convexified risk. The empirical convexified risk is (5.1)

3 RS,H (β) = ϕ

3 X

S,H3 αjS,H3 ϕ(Xj ) + α7−j ϕ(−Xj ).

j=0

This is the generic tridimensional conditional ϕ−risk where X0 = −β1 − β2 − β3 , X1 = −β1 − β2 + β3 , X2 = −β1 + β2 − β3 , X3 = −β1 + β2 + β3 .

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

19

The next two subsections describe the properties of the conditional ϕ-risk in R3 which is the relevant object to study the optimal combination of 3 classifiers. min (α) We first derive analytic formulae for the computation of the point of minimum βlogit when ϕ is the function logit, a single transcendental equation for the computation of the point min (α) when ϕ is the function boost. of minimum βboost

Secondly, we describe the necessary and sufficient condition to obtain a unique point of minimum of the conditional ϕ-risk in R3 , as well as the necessary and sufficient condition to get a non unique minimum (and of course all the cases of point of infimum can be deduced). 5.3. Formulae for the point of minimum for the generalized convexified ϕ-risk for boost and logit loss functions. The points of minimum are accounted for through a scalar equation which can even be solved analytically for the function logit. Let A = α0 α3 − α4 α7 + α0 α5 − α2 α7 + α0 α6 − α1 α7 + α3 α5 − α2 α4 + α3 α6 − α1 α4 + α5 α6 − α1 α2 , B = α0 α3 α5 + α0 α3 α6 + α3 α5 α6 + α1 α2 α4 + α1 α2 α7 + α2 α4 α7 + α0 α5 α6 + α1 α4 α7 , C = α0 α3 α5 α6 − α1 α2 α4 α7 , and define the function Γl (y, α) by (5.2)

Γl (y, α) = y 3 + Ay 2 + By + C

Let the function Γb (x, α) be given by

(5.3)

Γb (x, α) =

3 Y j=0

x + 2

! r  x 2 + αj α7−j . 2

Lemma 5.4. Assume that all the αj are non zero. The functions Γb and Γl are strictly increasing on their interval of definition. The equations Γl (y, α) = 0 and Γb (x, α) = α0 α3 α5 α6 have, respectively in their sets of definition, a unique solution denoted by yl (α) and xb (α). One has even an analytic3 formula for yl (α) using Cardan-Ferrari formulae. Proof. It comes from the monotony of Γb on R and the limits 0+ and +∞ at −∞ and +∞, and the monotony of Γl on I = (−min(α6 , α5 , α3 , α0 ), min(α1 , α2 , α4 , α7 )), with image R, the −y α2 −y α4 −y α7 −y latter coming from the following equivalent equation for yl (α): αα61 +y α5 +y α3 +y α0 +y = 1. Theorem 5.5. In the cases of logit and boost, for α0 · · · α7 > 0, the unique point of minimum of the generalized convexified ϕ-risk is given by the following formulae: • In the case of boost, the unique point of minimum is βb (α) = 12 (−X2b (α) − X1b (α), X3b (α) − X1b (α), X3b (α) − X2b (α)) where 3

Note for example that for α = (2/5, 1/20, 1/20, 1/20, 3/20, 1/20, 1/20, 1/5) the Cardan Formula for a positive discriminant returns the exact numerical value of the root of the polynomial Γl . Some cases need to go through complex values to calculate the 3 real roots of a polynomial of degree 3.

20

J.-M. BROSSIER, O. LAFITTE

 q b (α) 2 b (α) = ln( xb (α) +   ( x2α ) + αα16 ) X  1 2α6 6  q b (α) b (α) 2 . X2b (α) = ln( x2α + ( x2α ) + αα25 ) 5  q 5    X b (α) = ln(− xb (α) + ( xb (α) )2 + α3 ) 3

2α4

2α4

α4

• In the case of logit, the unique point of minimum is βl (α) = 21 (−X2l (α) − X1l (α), X3l (α) − X1l (α), X3l (α) − X2l (α)) where  α1 −yl (α) l    X1 (α) = ln α6 +yl (α) −yl (α) X2l (α) = ln αα52 +y . l (α)    X l (α) = ln α3 +yl (α) 3

α4 −yl (α)

The proof is given in appendix D. Remark 5.6. When α1 α3 α4 α5 α6 α7 > 0 and α0 = α2 = 0, the convexified cost has an infimum. If one uses the second strategy described in the proof of lemma 5.3, we consider the function Cϕα,reg : β → Cϕα (β) + κ(ϕ(X0 ) + ϕ(X2 )) where κ > 0. This function has an unique point of minimum βκ with X0,κ = O(ln κ), X1,κ = ln αα61 + O(κ), X2,κ = O(ln κ), X3,κ = ln αα43 + O(κ) and the point Xκ has not a finite limit when κ → 0+ . This result holds also if 1 one considers α⋆ = 1+8κ (α + (κ, · · · , κ)). 1 Proof. When α1 α3 α4 α5 α6 α7 > 0, denote by α̃ = 1+2κ (κ, α1 , κ, α3 , α4 , α5 , α6 , α7 ). There exists κ0 > 0 such that, for κ < κ0 (−min(α̃6 , α̃5 , α̃3 , α̃0 ), min(α̃1 , α̃2 , α̃4 , α̃7 )) ⊂ (−κ, κ). Recall that the polynomial Γl when α0 = α2 = 0 is Γl (y) = y 3 + Ay 2 + By. Denote by 5 α6 −α1 α4 α7 ) Γκl the one derived for α0 = α2 = κ is y 3 + A(κ)y 2 + B(κ)y + κ(α3 α(1+2κ) , where 4 6 +α1 α4 +α4 α7 +α5 α6 ) 5 +α6 −α1 −α4 −α5 ) and B(κ) = B+κ(α3 α5 +α3 α(1+2κ) . hence Γκl has A(κ) = A+κ(α3 +α(1+2κ) 2 3 a unique root of order κ which belongs to (−κ, κ), denoted by κz∗ (κ), this root being the value of α7 eX0,κ /(1 + eX0,κ ). Hence X0 = O(ln κ) goes to −∞ when κ → 0. The relations ∗ (κ) X3,κ = α3 −κz∗ (κ) , and eX2,κ = κ−κz∗ (κ) yield the limit of X announced. eX1,κ = αα16 −κz κ +κz∗ (κ) , e α4 +κz∗ (κ) α5 +κz∗ (κ) The same formulae yield an identical result for α⋆ . This regularization yields a result but β(κ) does not yield a bounded value of β at the limit. Remark that ||β(κ)|| → (− 12 , 0, − 12 , 0) as P κ → 0. However, the classifier resulting classifier G = βj (κ)Gj is not a separator: the signs in columns 1 and 6 are oppposite hence, for every small κ, neither G or −G is perfect.

Remark 5.7. We used here two Tikhonov-type regularizations adapted to our problem instead of the usual ℓ2 regularization on the norm of the vector β; the analysis is also possible with the usual regularization and the conclusion is identical. 5.4. Non-existence or non-uniqueness of the point of minimum for a general conditional ϕ-risk in R3 . In this paragraph, we consider α ∈ A3 (cf. (2.2)) and describe all the possible cases for non-existence or non-uniqueness for all loss functions satisfying definition 3.1 (as well as cases where the minimum is unique). Before describing all the cases, we would like to emphasise that the convexified risk does not necessarly have a unique point of minimum. There can be a point of infimum if 6 (out of 8) entries of α are non zero, let us give an example:

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

21

Remark 5.8. Let α1 α3 α4 α5 α6 α7 > 0 and ϕ be an arbitrary function satisfying definition 3.1, the generic multidimensional ϕ-risk α1 ϕ(X1 ) + α6 ϕ(−X1 ) + α3 ϕ(X3 ) + α4 ϕ(−X3 ) + α5 ϕ(X1 − X0 − X3 ) + α7 ϕ(−X0 ) has a strictly positive infimum, hence there is no combination of the 3 classifiers which minimizes the convexified risk. Proof. The partial derivative with respect to X0 of this function is −α5 ϕ′ (X1 −X0 −X3 )− α7 ϕ′ (X0 ) which can never be zero. Hence the Euler equations do not have a solution. The infimum is equal to min(α1 ϕ(X1 ) + α6 ϕ(−X1 )) + min(α3 ϕ(X3 ) + α4 ϕ(−X3 )) > 0. It is then interesting to investigate the cases where the convexified cost does not have a unique point of minimum, because in this case no algorithm can provide a solution to the minimization of the convexified cost function. Nevertheless, the implementation of an algorithm converges numerically (using a stopping criterion), hence returns a point. We provide a detailed analysis of all the cases where we have regular (cf. definition 3.3) points in A3 (cf. (2.2)). Theorem 5.9. We consider any loss function satisfying definition 3.1. (i) When 3 pairs are full and 0, 1 or 2 non zero elements in the fourth one, the point of minimum exists and is unique. (ii) When 1, 2 or 3 entries of α only are non-zero, there is an infimum (equal to zero) or a non-unique minimum (the latter occurs for only two non-zero entries, and in the same pair). (iii) The only cases of exactly 4 non-zero coefficients where there is existence and uniqueness of the point of minimum are α0 α3 α5 α6 > 0 or α1 α2 α4 α7 > 0. All other cases for exactly 4 non-zero coefficients return a zero infimum or a non-unique non-zero minimum. (iv) For 5 or 6 non-zero coefficients and no empty pair, the multidimensional ϕ-risk is bounded below by a strictly positive constant and the only cases of having a unique point of minimum are one of the previous cases α0 α3 α5 α6 > 0 or α1 α2 α4 α7 > 0 with any one or two additional elements. (v) For 5 non zero coefficients and one empty pair, the function has a non-zero infimum. The cases of an infimum equal to zero are obtained only in items (ii) and (iii). The following corollary is a consequence of theorem 5.9 by inspection of (iii) and (iv): Corollary 5.10. We consider any loss function satisfying definition 3.1. When no pair is empty, there exists a unique point of minimum if and only if α0 α3 α5 α6 > 0 or α1 α2 α4 α7 > 0. Proof. Items (i),(ii),(iv) are proven in appendix B. All cases of four entries non zero (item (iii)) are described here: 1. two pairs full: existence of multiple points of minima 2. one pair full and two non zero entries in two of the three others: infimum. For example α0 α7 α4 α2 > 0, for which X0 solves α0 ϕ′ (X0 ) = α7 ϕ′ (−X0 ), X3 → −∞, X2 → +∞ and the infimum is min[α0 ϕ(X0 ) + α7 ϕ(−X0 )]. 3. each pair contains a non zero element:

22

J.-M. BROSSIER, O. LAFITTE

(a) The two cases of minimum are α7 α4 α2 α1 > 0 and α0 α3 α5 α6 > 0 (It is a particular case of lemma 3.4(i)). In the first case (the second case is equivalent by changing β to −β), the function is α7 ϕ(−X1 − X2 − X4 ) + α1 ϕ(X1 ) + α2 ϕ(X2 ) + α4 ϕ(X4 ). The Euler equations are α7 ϕ′ (−X0 ) = α4 ϕ′ (X4 ), α7 ϕ′ (−X0 ) = α2 ϕ′ (X2 ), α7 ϕ′ (−X0 ) = α1 ϕ′ (X1 ). From the equality X0 = X1 +X2 +X4 and the values of X1 , X2 , X4 in term of X0 , we get the equation Z(X0 ) = 0 where Z(X0 ) = X0 → X0 − (ϕ′ )−1 [ αα71 ϕ′ (−X0 )] − (ϕ′ )−1 [ αα27 ϕ′ (−X0 )] − (ϕ′ )−1 [ αα74 ϕ′ (−X0 )]. As ϕ′ is strictly increasing, its reciprocal is strictly increasing and Z is strictly increasing. When X0 → −∞ its limit is −∞ because ααk7 ϕ′ (−X0 ) → 0− for all k hence (ϕ′ )−1 [ ααk7 ϕ′ (−X0 )] → +∞ for all k. When X0 → +∞, assume that l is the limit (element of [−∞, 0)) of ϕ′ at −∞. When X0 → +∞, ααk7 ϕ′ (−X0 ) → ααk7 l. The limitation (for the set of definition of (ϕ′ )−1 [.]) for X0 is ααk7 ϕ′ (−X0 ) > l. Hence, considering the smallest value of ααk7 , one gets X0∗ such that ϕ′ (−X0 ) = min( ααk7 l) (and X0∗ = −∞ when l = −∞), and the set of definition of Z is (−∞, X0∗ ), the limit when X0 → X0∗ is +∞. As Z is strictly increasing, there is a unique root to Z(X0 ) = 0, hence a unique solution for the Euler equations which is the unique point of minimum of the convexified risk. Remark that, for the boost loss, the value of the minimum is (α0 α1 α2 α4 )1/4 . (b) All other cases return a zero infimum: we consider the specific example α7 α4 α2 α6 > 0 for the proof (the proof of all other cases is similar). The function is α7 ϕ(−X1 − X2 + X3 ) + α4 ϕ(−X3 ) + α2 ϕ(X2 ) + α6 ϕ(−X1 ). Its derivative with respect to X1 is −α6 ϕ′ (−X1 ) − α7 ϕ′ (−X0 ) > 0, hence it has no root and there is no point of minimum. With X1 = −3n, X2 = n, X3 = −n → −X1 − X2 + X3 = n, the infimum is 0. We have the following proposition which proves that the non-existence of a point of minimum for the convexified cost is possible for any number m of classifiers. Proposition 5.11. Non existence of a unique point of minimum: (i) We have the implication: ”if, in a given list G1 , · · · , Gm there is one couple (Gi , Gj ) for which at least one column of its truth table is empty, then the convexified cost for the m classifiers does not have a unique point of minimum (it might be a non unique minimum or an infimum)”. (ii) This implication is an equivalence in the case m = 3. For example, if (G1 , G2 ) has an infimum, any additional classifier will yield an infimum, if (G1 , G2 ) has a unique minimum, it is enough to test (G1 , G3 ) and (G2 , G3 ). The proof of this proposition is postponed to section C. 6. Frontiers. Now we introduce the setup needed for studying the resulting classifier in an abstract way, in particular to control the sign of a given Xk , hence the stability of a given α. 6.1. Definition of a frontier and characterization of the contradictions. The curves {Xk (α) = 0} separate the decisions Xk > 0 and Xk < 0 and they are of interest, namely

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

23

identifying regions which return different decisions for two given loss functions. The are called ϕ-frontiers, and depend only on m, α and ϕ. Definition 6.1 (ϕ-frontier points). A ϕ-frontier point α is a regular point for ϕ with at least min (α) equals to zero. one of the values of Xϕ,k For m ≥ 3, a corner point of order p ≥ 2 for ϕ is a set of relations between the coordinates of α such that exactly p relations Xϕ,k1 = 0, . . . , Xϕ,kp = 0 hold simultaneously. As we have a complete study for two particular loss functions of the point of minimum of the convexified risk for 3 classifiers, we have analytical equations for the frontiers and a study of contradictory decisions. This is described below for α ∈ A3 . Let a, b, c, d be given by a = α0 − α7 , b = α1 − α6 , c = α2 − α5 , d = α3 − α4 . Recall that Γl and Γb are defined in (5.2) and (5.3). We have an explicit expression of the frontiers in the cases of logit and boost: Proposition 6.2. The equations of frontiers are, for logit, resp. for boost: • Γl (−a/2, α) = 0, resp. Γb (a, α) = α0 α3 α5 α6 for X0 = 0, • Γl (b/2, α) = 0, resp. Γb (−b, α) = α0 α3 α5 α6 for X1 = 0, • Γl (c/2, α) = 0, resp. Γb (−c, α) = α0 α3 α5 α6 for X2 = 0, • Γl (−d/2, α) = 0, resp. Γb (d, α) = α0 α3 α5 α6 for X3 = 0. See proof in appendix D. We have thus a complete description of the frontiers and a procedure to identify the minima by solving (either numerically for the boost loss function through a 1D Newton method or through Cardan formulae for logit). The choice of the logit function which is a regularized strictly convex version of the ReLU function could be profitable thanks to this. 6.2. The frontiers as a tool for understanding infima of the convexified cost. The traditional approach to study the cases of infima is by regularizing the strictly convex function. It has been shown in appendix A that all regularizations are equivalent. Authors then generally consider the limit direction of β. In this subsection, we show in two examples that it is closely related to the notion of frontiers. First example: 3 classifiers with 2 zero coefficients. In the case of the convexified cost of remark 5.8, we use the unique point of minimum of α1 ϕ(X1 ) + α6 ϕ(−X1 ) + α3 ϕ(X3 ) + α4 ϕ(−X3 ) + α7 ϕ(−X0 ) + ϵϕ(X0 ) + α5 ϕ(X1 − X0 − X3 ) + ϵϕ(−X1 + X0 + X3 ). The Euler equations in X1 , X3 , X0 are   α1 ϕ′ (X1 ) − α6 ϕ′ (X1 ) + α5 ϕ′ (X1 − X0 − X3 ) = ϵϕ′ (−X1 − X0 + X3 ) α3 ϕ′ (X3 ) − α4 ϕ′ (−X3 ) − α5 ϕ(X1 − X0 − X3 ) = −ϵϕ′ (−X1 + X0 + X3 )  −α7 ϕ′ (−X0 ) − α5 ϕ′ (X1 − X0 − X3 ) + ϵϕ′ (X0 ) = −ϵϕ′ (−X1 + X0 + X3 ) The limit when ϵ → 0 of −X0 is +∞, which yields the following relations for the limits of X1 and X3 :  α1 ϕ′ (X1 ) − α6 ϕ′ (X1 ) + 0 = 0 α3 ϕ′ (X3 ) − α4 ϕ′ (−X3 ) − 0 = 0 hence finite values of X1 and X3 . The limit of (X0 , X1 , X3 )/|(X0 , X1 , X3 )| is then (1, 0, 0), which corresponds to a frontier (as in the case of two classifiers in appendix A).

24

J.-M. BROSSIER, O. LAFITTE

Second example: 3 classifiers with 4 zero coefficients. For the function α1 ϕ(X1 ) + α6 ϕ(−X1 ) + α3 ϕ(X3 ) + α4 ϕ(−X3 ) + α7 ϕ(−X0 ) + α5 ϕ(X1 − X0 − X3 ) one easily checks that ∀(X1 , X3 ), α1 ϕ(X1 ) + α6 ϕ(−X1 ) + α3 ϕ(X3 ) + α4 ϕ(−X3 ) ≥ min α1 ϕ(X1 ) + α6 ϕ(−X1 ) + 1 3 α3 ϕ(X3 ) + α4 ϕ(−X3 ) := min = (α1 + α6 )H( α1α+α ) + (α3 + α4 )H( α3α+α ) (with equality at a 6 4 ∗ ∗ point (X1 , X3 ). One then show that, for X0 → −∞, α7 ϕ(−X0 ) + α5 ϕ(X1 − X0 − X3 ) → 0. Hence there exists a sequence which converges to the infimum of this function, equal to min. 3) This proves that √(X02 ,X1 ,X converges to (−1, 0, 0), and this defines β1lim , which is a 2 3 X0 +X1 +X3

frontier point. For the function α0 ϕ(X1 + X2 + X4 ) + α1 ϕ(X1 ) + α2 ϕ(X2 ) + α4 ϕ(X4 ), consider a sequence of the form X1 = N, X2 = θN, X4 = µN . For all θ ≥ 0, µ ≥p0, this sequence makes the function converge to 0 when N goes to +∞. Then (X1 , X2 , X4 )/ X12 + X22 + X42 converges to (1, θ, µ) hence the limit of the correspondding sequence is arbitrary, including (0, 1, 0) or (0, 0, 1). General case for 3 classifiers. For the general analysis, we begin to identify the pair fulls, which yield the value of the corresponding coordinates when the regularization is used. We then consider the other coordinates which go to infinity. The study of these cases correspond to the limits X0 → ∞, X1 → ∞, X2 → ∞, X3 → ∞, where one knows directly the limiting normalized value of X (δji ). (X0 , X1 ) → (∞, ∞), (X0 , X2 ) → (∞, ∞), (X0 , X3 ) → (∞, ∞), (X1 , X2 ) → (∞, ∞), (X1 , X3 ) → (∞, ∞), (X2 , X3 ) → (∞, ∞) where it is trickier and has to be studied separately. For example α7 ϕ(−X0 ) + α1 ϕ(X1 ) + 0ϕ(X0 ) + 0ϕ(−X1 ) + α2 ϕ(X2 ) + α5 ϕ(−X2 ) where X2 is determined and X0 → −∞, X1 → +∞, and the limiting value of the normalized version is X ∗ = (X0∗ , X1∗ , X2∗ ) = (r, 1, 0) thanks to X0ϵ = β ∗ (

α7 ϵ ), X 1 = β ∗ ( ) α7 + ϵ α1 + ϵ

β∗(

α7

)

and one has to study the limit r of β ∗ ( α7ϵ+ϵ ) when ϵ → 0+ . α1 +ϵ

6.3. Study of data of poor quality with two different classification calibrated functions. This analysis for the frontiers can even identify values of α for which at least one sign of the Xj calculated from the choice of the boost or logit functions disagree. We propose to use this idea to identify these cases explicitly thanks to the characterization of the sign of Xj for all j. Definition 6.3 (Data of poor quality). One says that the set {S, Hm } is of poor quality if there exists two functions ϕ1 and ϕ2 , regularly classification calibrated and an index l ∈ {0, · · · , 2m − 1} such that Xlϕ1 (αS,Hm )Xlϕ2 (αS,Hm ) < 0. In the case of 3 classifiers, we have exact analytic expressions without solving any equation, which will determine if two resulting classifiers are contradictory for at least one sign and for the two functions boost and logit: Lemma 6.4. If, for α = αS,H3 , at least one of the four real numbers (Γb (−b, α) − α0 α3 α5 α6 )Γl (b/2, α), (Γb (a, α) − α0 α3 α5 α6 )Γl (−a/2, α),

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

25

(Γb (−c, α) − α0 α3 α5 α6 )Γl (c/2, α), (Γb (d, α) − α0 α3 α5 α6 )Γl (−d/2, α) is positive, then the set of classified data S, H3 is of poor quality. (α0 +2x)(α3 +2x)(α5 +2x)(α6 +2x) Γl (x) Remark that ψ(x) := (α = 1+ (α7 −2x)(α4 −2x)(α , hence 7 −2x)(α4 −2x)(α2 −2x)(α1 −2x) 2 −2x)(α1 −2x) 1 1 the function ψ is strictly increasing on (− 2 min(α0 , α3 , α5 , α6 ), 2 min(α7 , α4 , α2 , α1 )) (thanks ′ (x) and ψ(x) > 0 on this interval). to the value of the logarithmic derivative ψψ(x) The functions Γl and Γb are thus both increasing. For the frontier X0 = 0, x = α0 −α7 = a and x(X0 ) = α0 e−X0 − α7 eX0 is strictly decreasing in X0 and y = 21 (α7 − α0 ) = −a/2, eX0 −α0 y(X0 ) = α71+e is strictly increasing in X0 . Hence, Γb (x(X0 ), α) is strictly decreasing in X0 X0 while Γl (y(X0 ), α) is strictly increasing in X0 . We deduce that Γb (x(0), α) = Γb (a, α) and Γl (y(0), α) = Γl (−a/2, α) of the same sign yield opposite signs for X0b (α) and X0l (α). The same procedure applies for X1 , X2 , X3 . This proves proposition 6.4. We illustrate this lemma in the figures 5, 6, 7. NotePthat in these figures, no value of α2 , α5 above the blue curve can be considered thanks to αi = 1 and αi > 0. In all figures, the red curves are the frontiers for boost, the black ones are the ones for logit, the domain between these two curves corresponds to sets of poor quality according to definition 6.3.

Figure 5: sign of X0 for two differents set of values of α0 , α1 , α3 , α4 , α6 .

6.4. A training set of poor quality. We identify a toy example where the value α corresponds to a region where the quantity Xj∗ has not the same sign when using logit and boost, hence not returning the same optimal decision. This example uses a training set, for three given weak classifiers, built to get this contradiction. Empirical Illustration of lemma 6.4 and ϕ-frontiers. Figure 8 provides an illustration of poor quality data (definition 6.3). In this two dimensional setup, the three base classifiers partition the input space into 8 logical configurations ϵ defining the truth table α. Within each region, the ensemble’s prediction is constant and dictated by the sign of Xk (β) = ϵ(k) · β. By deriving the optimal weights via theorem 5.5, the resulting decision boundaries for the logit and boost losses are plotted. As observed, the boundaries coincide in most regions but diverge to enclose specific geometric areas highlighted in red. These conflict zones correspond to the logical equivalence classes where the two optimal models output opposite decisions. For instance, the red regions in figure 8 correspond to the configurations ϵ = (−1, 1, −1) and its

26

J.-M. BROSSIER, O. LAFITTE

Figure 6: sign of X2 (left) and X3 (right) for the given set.

Figure 7: sign of X3 with a zoom (right) near the cusp.

negation (1, −1, 1), which are governed by the variable X2 . If one of the four products in lemma 6.4 is strictly positive — such as (Γb (−c, α) − α0 α3 α5 α6 )Γl (c/2, α) > 0 — it guarantees that the optimal roots for boost and logit fall on opposite sides of the threshold X2 = 0. In the feature space, this algebraic condition triggers the appearance of the red conflict zone associated with X2 . This confirms that poor quality data reflects an intrinsic ambiguity in the dataset’s logical distribution, forcing standard classification-calibrated losses to yield contradictory predictions. 7. Conclusions and perspectives. This paper introduced a novel framework for ensemble learning based on a logical structuration of the dataset via truth tables. This approach partitions the data into equivalence classes defined by the decisions of the elementary classifiers, leading to a compression of the training set information where the complexity depends on 2m rather than the number of examples n. This structure naturally supports hierarchical extensions, such as adding new classifiers. We generalized the theory of classification calibrated functions to the multidimensional setting. This theoretical framework allowed us to perform a rigorous analysis of the convexified empirical risk:

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

27

Figure 8: Illustration of lemma 6.4 (Data of poor quality). The two dimensional feature space is partitioned into 8 logical equivalence classes by three base classifiers (h1 : x = 0, h2 : y = 0, and h3 : x2 + y 2 = 1). The optimal ensemble decision boundaries for the logit loss (solid black line) and boost loss (dashed blue line) are plotted using the analytical weights derived in theorem 5.5. The red shaded areas represent the conflict zone where the two risks return opposite decisions. Lemma 6.4 predicts the existence of such conflicts.

• We established sufficient conditions for the existence and uniqueness of a global minimum for an arbitrary number of classifiers. • In the specific case of three classifiers, we provided an exhaustive classification of all possible configurations, identifying necessary and sufficient conditions for the existence and uniqueness of the solution, as well as characterizing cases leading to an infimum or non-unique minima. • We showed that the non-existence of a minimum is intrinsically linked to the lack of contradictions between classifiers on the training set (i.e., empty columns in the truth table). It yields unstability on decisions even when one uses the classical trick of Tikhonov regularization or when we add elements in empty columns. Furthermore, our analysis enabled the derivation of explicit analytical formulae for the optimal classifier weights in the case of three classifiers for the Exponential (boost) and Logistic (logit) loss functions, bypassing the need for iterative numerical optimization in these cases. The analytic result using Cardan formulae is obtained for m = 3 and the function logit. We note that our approach is ineffective for m large because, in this case, the convexified

28

J.-M. BROSSIER, O. LAFITTE

cost is likely to have an infimum (which again leads to unstability of decisions). Finally, we introduced the concept of ϕ-frontiers in the parameter space. These frontiers define the boundaries where the resulting classifier’s decision changes, allowing for a precise sensitivity analysis with respect to the choice of the loss function. This led to a criterion for identifying ”data of poor quality,” where different standard loss functions yield contradictory predictions. Perspectives include further investigation into the characterization of data quality based on the stability analysis or proving the conjecture that the remark of the case m = 3 in proposition 5.11 is true for all m. REFERENCES [1] F. Bach, Learning theory from first principles, MIT press, 2024. [2] P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe, Convexity, classification, and risk bounds, Journal of the American Statistical Association, 101 (2006), pp. 138–156, https://doi.org/10.1198/ 016214505000000907, https://doi.org/10.1198/016214505000000907, https://arxiv.org/abs/https:// doi.org/10.1198/016214505000000907. [3] L. Breiman, Bagging predictors, Machine learning, 24 (1996), pp. 123–140. [4] L. Breiman, Random forests, Springer, 45 (2001), pp. 5–32. [5] J. M. Brossier and O. Lafitte, Combining weak classifiers: a logical analysis, in 23rd International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2021, pp. 178– 181, https://doi.org/10.1109/SYNASC54541.2021.00038. [6] T. Chen and C. Guestrin, Xgboost: A scalable tree boosting system, Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, (2016), pp. 785–794. [7] M. Eytzinger, Thesaurus principum hac aetate in Europa viventium, Coloniae Agrippinae. : Apud Godefridum Kempensem., 1590, https://archive.org/details/thesaurusprincip00eytz. [8] Y. Freund, Boosting a weak learning algorithm by majority, Information and computation, 121 (1995), pp. 256–285. [9] Y. Freund and R. E. Schapire, Experiments with a new boosting algorithm, in ICML, Citeseer, 1996, pp. 148–156. [10] Y. Freund and R. E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of computer and system sciences, 55 (1997), pp. 119–139. [11] J. H. Friedman, Greedy function approximation: a gradient boosting machine, Annals of statistics, (2001), pp. 1189–1232. [12] R. A. Jacobs, M. I. Jordan, S. J. Nowlan, and G. E. Hinton, Adaptive mixtures of local experts, Neural computation, 3 (1991), pp. 79–87. [13] O. Lafitte and J.-M. Brossier, Combinaison optimale de classifieurs binaires :solution logique sans algorithme et minimisation de risques convexifiés, in GRETSI 2022. XXVIIIème Colloque Francophone de Traitement du Signal et des Images. Nancy., 6-9 Septembre 2022. [14] R. Polikar, Ensemble based systems in decision making, IEEE Circuits and systems magazine, 6 (2006), pp. 21–45. [15] R. E. Schapire and Y. Freund, Boosting. Foundations and Algorithms, The MIT Press, 2012. [16] R. E. Schapire and Y. Singer, Improved boosting algorithms using confidence-rated predictions, in Proceedings of the eleventh annual conference on Computational learning theory, 1998, pp. 80–91. [17] D. H. Wolpert, Stacked generalization, Neural networks, 5 (1992), pp. 241–259. [18] K. Woods, W. P. Kegelmeyer, and K. Bowyer, Combination of multiple classifiers using local accuracy estimates, IEEE transactions on pattern analysis and machine intelligence, 19 (1997), pp. 405– 410.

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

29

Appendix A. Proof of lemma 5.1. Proof. The sign of the resulting classifier is given by the signs of β1 + β2 and β1 − β2 . The false decision table is given by the sign of β1 G1 (xi , yi ) + β2 G2 (xi , yi ) for all i. The four possible configurations are: G1 −1 −1 +1 +1 G2 −1 +1 −1 +1 β1 G1 + β2 G2 −β1 − β2 −β1 + β2 +β1 − β2 +β1 + β2 hence we have Sectors (cf. figure 9) β1 + β2 > 0, β1 − β2 > 0 β1 + β2 > 0, β1 − β2 < 0 β1 + β2 < 0, β1 − β2 > 0 β1 + β2 < 0, β1 − β2 < 0

Number of errors of β1 h1 + β2 h2 ♯{G1= −1, G2= +1} + ♯{G1= −1, G2= −1} = ♯{G1= −1} ♯{G1= +1, G2= −1} + ♯{G1= −1, G2= −1} = ♯{G2= −1} ♯{G1= +1, G2= +1} + ♯{G1= −1, G2= +1} = ♯{G2= +1} ♯{G1= +1, G2= +1} + ♯{G1= +1, G2= −1} = ♯{G1= +1}

Line 4 X1 > 0

β2 Line 2 X1 > 0 X0 < 0

X0 > 0

X1 = 0 Line 1 X1 < 0

β1

X0 < 0 Line 3 X1 < 0 X0 > 0

X0 = 0

Figure 9: Sectors and frontiers for m = 2. X0 = −β1 − β2 , X1 = −β1 + β2 . Each sector corresponds to a line in the previous table.

Consider β1 , β2 such that the number of errors of the classifier sign(β1 h1 + β2 h2 ) is the smallest. According to the exhaustive choices of the table in figure 9, the smallest number of errors corresponds to one of the situations : smallest number of errors of G1 , smallest number of errors of G2 , smallest number of errors of NOT(G1 ), smallest number of errors of NOT(G2 ). The cases of equalities correspond to choosing indifferently one of the classifiers which present the smallest number of errors. The value of the unique point of minimum βϕmin (αS,H2 ) in lemma 5.2 is given by −

1 ⋆ αS,H2 αS,H2 1 αS,H2 αS,H2 (β ( S,H2 0 S,H2 ) + β ⋆ ( S,H2 1 S,H2 )), (β ⋆ ( S,H2 0 S,H2 ) − β ⋆ ( S,H2 1 S,H2 )) 2 2 α0 + α3 α1 + α2 α0 + α3 α1 + α2

using β ⋆ defined in section 3.2. Appendix B. Proof of theorem 5.9.

!

30

J.-M. BROSSIER, O. LAFITTE

Proof of (i). This is a direct consequence of lemma 3.9 for the case m = 3. Proof of (ii). For the case of three non-zero coefficients, the function is αi ϕ(Xi )+αj ϕ(Xj )+ αk ϕ(Xk ). Either Xi , Xj , Xk forms a system of coordinates in R3 , hence an infimum when Xi , Xj , Xk tends to +∞ or (i, j) is a pair (reordering indexes if needed) and it is enough to let Xk go to +∞. For the case of only one non-zero coefficient, we get an infimum. For the case of two non-zero coefficients, we get an infimum if they do not belong to the same pair; otherwise we get a non-unique minimum. Proof of (iv). We treat successively the case of 6 and 5 non-zero elements: (i) Consider the case of only 6 non-zero elements. Assume in addition that there are only 2 full pairs (the case of 3 full pairs is addressed in (i) of theorem 5.9). In this case, the functions listed below have a unique point of minimum and are the only ones in this case. We present this list by ordering the terms in the function beginning with the 2 full pairs. The non full pairs, characterized for example by the unknown Xj , j = 0 . . . 3, contain Xj and −Xj in the arguments of the two last terms using the relation X0 + X3 = X1 + X2 : j = 2 for example for the first function of the list below as it is written. The two last terms could also be written α2 ϕ(X0 + X3 − X1 ) + α4 ϕ(−X3 ) and j = 3. In the following array, the first column lists the full pairs considered. Pair (0, 1) Pair (0, 2) Pair (0, 3) Pair (1, 2) Pair (1, 3) Pair (2, 3)

α0 ϕ(X0 ) + α7 ϕ(−X0 ) + α1 ϕ(X1 ) + α6 ϕ(−X1 ) α0 ϕ(X0 ) + α7 ϕ(−X0 ) + α1 ϕ(X1 ) + α6 ϕ(−X1 ) α0 ϕ(X0 ) + α7 ϕ(−X0 ) + α2 ϕ(X2 ) + α5 ϕ(−X2 ) α0 ϕ(X0 ) + α7 ϕ(−X0 ) + α2 ϕ(X2 ) + α5 ϕ(−X2 ) α0 ϕ(X0 ) + α7 ϕ(−X0 ) + α3 ϕ(X3 ) + α4 ϕ(−X3 ) α0 ϕ(X0 ) + α7 ϕ(−X0 ) + α3 ϕ(X3 ) + α4 ϕ(−X3 ) α1 ϕ(X1 ) + α6 ϕ(−X1 ) + α2 ϕ(X2 ) + α5 ϕ(−X2 ) α1 ϕ(X1 ) + α6 ϕ(−X1 ) + α2 ϕ(X2 ) + α5 ϕ(−X2 ) α1 ϕ(X1 ) + α6 ϕ(−X1 ) + α3 ϕ(X3 ) + α4 ϕ(−X3 ) α1 ϕ(X1 ) + α6 ϕ(−X1 ) + α3 ϕ(X3 ) + α4 ϕ(−X3 ) α2 ϕ(X2 ) + α5 ϕ(−X2 ) + α3 ϕ(X3 ) + α4 ϕ(−X3 ) α2 ϕ(X2 ) + α5 ϕ(−X2 ) + α3 ϕ(X3 ) + α4 ϕ(−X3 )

+α2 ϕ(X2 ) + α4 ϕ(X0 − X1 − X2 ) +α5 ϕ(−X2 ) + α3 ϕ(−X0 + X1 + X2 ) +α1 ϕ(X1 ) + α4 ϕ(X0 − X1 − X2 ) +α6 ϕ(−X1 ) + α3 ϕ(−X0 + X1 + X2 ) +α1 ϕ(X1 ) + α2 ϕ(X0 + X3 − X1 ) +α6 ϕ(−X1 ) + α5 ϕ(−X0 + X1 − X3 ) +α0 ϕ(X0 ) + α3 ϕ(−X0 + X1 + X2 ) +α7 ϕ(−X0 ) + α4 ϕ(X0 − X1 − X2 ) +α0 ϕ(X0 ) + α5 ϕ(X1 − X0 − X3 ) +α7 ϕ(−X0 ) + α2 ϕ(−X1 + X0 + X3 ) +α0 ϕ(X0 ) + α6 ϕ(−X0 − X3 + X2 ) +α7 ϕ(−X0 ) + α1 ϕ(X0 + X3 − X2 )

When, in this array, one changes exactly one element of one of the two last pairs, one has an infimum. We treat only two examples, one in this list where there is a solution of the Euler equations (and hence a unique point of minimum as the function is strictly convex) and one where there is an infimum. • An example where there is an infimum is Cα (β) = α1 ϕ(X1 ) + α6 ϕ(−X1 ) + α3 ϕ(X3 ) + α4 ϕ(−X3 ) + α7 ϕ(−X0 ) + α5 ϕ(X1 − X0 − X3 ). Indeed, the derivative of this function with respect fo X0 writes −α7 ϕ′ (−X0 ) − α5 ϕ′ (X1 − X0 − X3 ) > 0, hence the Euler equations have no solution, hence no point of minimum. • An example where there is a minimum is Cα (β) = α1 ϕ(X1 ) + α6 ϕ(−X1 ) + α3 ϕ(X3 ) + α4 ϕ(−X3 ) + α0 ϕ(X0 ) + α5 ϕ(X1 − X0 − X3 ). The Euler equations write α1 ϕ′ (X1 )−α6 ϕ′ (−X1 )+α5 ϕ′ (X1 −X0 −X3 ) = 0, α3 ϕ′ (X3 )−

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

31

α4 ϕ′ (−X3 ) − α5 ϕ′ (X1 − X0 − X3 ) = 0, α0 ϕ′ (X0 ) − α5 ϕ′ (X1 − X0 − X3 ) = 0. Let a = α5 ϕ′ (X1 − X0 − X3 ). This system rewrites α1 ϕ′ (X1 ) − α6 ϕ′ (−X1 ) = −a, α3 ϕ′ (X3 ) − α4 ϕ′ (−X3 ) = a, α0 ϕ′ (X0 ) = a. Denote by l (possibly −∞) the limit of ϕ′ at −∞ and recall that the limit of ϕ′ at +∞ is zero. A necessary condition on a for the system on (X0 , X1 , X3 ) to have a solution is simultaneously to have −a ∈ (α1 l, −α6 l), a ∈ (α3 l, −α4 l), a ∈ (α0 l, 0), that is a ∈ (min(α0 , α3 , α6 )l, 0). Moreover, the limit, when a goes to 0, of X0 is −∞, the limit of X1 and X3 are finite numbers. Similarly, the limit when a → min(α0 , α3 , α6 )l of at least one of the values of X0 , −X1 , X3 is −∞, that is X1 − X0 − X3 go to +∞. One deduces X0 = (ϕ′ )−1 ( αa0 ), X1 = Bα1 ,α6 (−a), X3 = Bα3 ,α4 (a), where Bθ,τ is the reciprocal function of the strictly increasing function x → θϕ′ (x)−τ ϕ′ (−x). The function Bθ,τ is thus strictly increasing, and the equation for finding a is (B.1)

α5 ϕ′ (Bα1 ,α6 (−a) − (ϕ′ )−1 (

a ) − Bα3 ,α4 (a)) − a = 0. α0

The function in the left-hand side of (B.1) from (min(α0 , α3 , α6 )l, 0) onto R is strictly decreasing hence it has a unique root. (ii) Consider the case of five non zero elements. • if two pairs (i, j) are full, one additional element of the form αk ϕ(Xk ) one deduces Xi and Xj , and Xk → +∞ yields an infimum. • if one pair i is full, the three other pairs contain, each, only one element. We have cases of minimum and cases of infimum Case of minimum. Let us treat the first one. The function one minimizes is α0 ϕ(X0 ) + α7 ϕ(−X0 ) + α1 ϕ(X1 ) + α2 ϕ(X2 ) + α4 ϕ(X0 − X1 − X2 ). Euler system of equations is α0 ϕ′ (X0 )−α7 ϕ′ (−X0 )+α4 ϕ′ (X0 −X1 −X2 ) = 0, α1 ϕ′ (X1 )−α4 ϕ′ (X0 −X1 −X2 ) = 0, α2 ϕ′ (X2 )−α4 ϕ′ (X0 −X1 −X2 ) = 0. Introduce b = α4 ϕ′ (X0 − X1 − X2 ). One obtains X1 = (ϕ′ )−1 ( αb1 ), X2 = (ϕ′ )−1 ( αb2 ), X0 = Bα0 ,α7 (−b), which yields (B.2)

α4 ϕ′ (Bα0 ,α7 (−b) − (ϕ′ )−1 (

b b ) − (ϕ′ )−1 ( )) − b = 0. α1 α2

The function in the left-hand side of (B.2), from (α7 l, 0) onto R, is strictly decreasing hence has a unique root. As the 3-dimensional generic convexified cost is strictly convex, the solution is a point of minimum, hence the function has a unique minimum.

32

J.-M. BROSSIER, O. LAFITTE

Case of infimum. When one of the coefficients changes, there is an infimum. For example, consider (X0 , X1 , X2 ) → α0 ϕ(X0 ) + α7 ϕ(−X0 ) + α1 ϕ(X1 ) + α5 ϕ(−X2 ) + α4 ϕ(X0 − X1 − X2 ). The derivative with respect to X2 is −α5 ϕ′ (−X2 ) − α4 ϕ′ (X0 − X1 −X2 ) > 0 hence no solution to the Euler equations, there is an infimum. By inspection, we observe that ALL the cases of unique point of minimum described above contain at least either the indexes (0, 3, 5, 6) or (1, 2, 4, 7). This ends the proof of (iv) of theorem 5.9. □ Appendix C. Proof of proposition 5.11. 1. For the proof of the first item of proposition 5.11, assume we have a list of m classifiers and that the couple (Gi , Gj ) induces at least one column of its truth table empty. • If only one column is empty, without loss of generality, we assume that it is Gi = −1, Gj = +1, hence ♯{Gi = +1, Gj = +1} > 0, ♯{Gi = −1, Gj = −1} > 0, ♯{Gi = +1, Gj = −1} > 0 and ♯{Gi = −1, Gj = +1} = 0. Define the following subsets of S: S i+,j+ = {(xp , yp ) : Gi (xp , yp ) = +1, Gj (xp , yp ) = +1}, S i−,j− = {(xp , yp ) : Gi (xp , yp ) = −1, Gj (xp , yp ) = −1}, S i+,j− = {(xp , yp ) : Gi (xp , yp ) = +1, Gj (xp , yp ) = −1} i,j and the list of classifiers Hm−2 = Hm \{hi , hj }. Denote by X = βi +βj and Y = βi −βj . The multidimensional convexified ϕ-risk writes 2m−2 X−1

i,j S i+,j+ ,Hm−2

αk

i,j S i−,j− ,Hm−2

ϕ(X + Yk ) + αk

i,j S i+,j− ,Hm−2

ϕ(−X + Yk ) + αk

ϕ(Y + Yk )

k=0

P where Yk = m l=1,l̸=i,j ϵ(k)l βl . The derivative with respect to Y of this function returns 2m−2 X−1

i,j S i+,j− ,Hm−2 ′

αk

ϕ (Y + Yk ) < 0

k=0

Hence, there is no solution to the Euler equations for the convexified m − ϕ-risk, hence no point of minimum. • Assume that two columns of the truth table of Gi , Gj are empty. Two cases appear: the case of an infimum equals to zero and the case of a non-unique minimum. For these two classifiers, the case of non unique minimum is obtained when S i+,j− = ∅, the multidimensional convexified ϕ-risk is then 2m−2 X−1

i,j S i+,j+ ,Hm−2

αk

i,j S i−,j− ,Hm−2

ϕ(X + Yk ) + αk

ϕ(−X + Yk )

k=0

which depends only on m − 1 independent variables (it does not depend on Y ), hence even if there is a point of minimum, adding any value of Y also returns a point of minimum.

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

33

Existence and uniqueness of a point of minimum of the 3-dimensional generic convexified cost function is equivalent to having all the couples (G1 , G2 ), (G1 , G3 ), (G2 , G3 ) leading to a unique point of minimum of the 2-dimensional generic convexified cost function. 2. The proof of the second item of proposition 5.11 (Equivalence of ”no unique minimum for 3 classifiers” and ”one pair of these classifiers at least corresponds to a case of non-uniqueness”) consists in the study of all cases of non-uniqueness or existence of the point of minimum for 3 classifiers. (a) 6 non zero elements and 2 full pairs only. We describe two examples in detail, and all other cases in these two items are listed below each item without proof. For example, pick one truth table where the convexified ϕ−risk has an infimum, the truth table of G2 , G3 leads an infimum too: indeed α0 α7 α3 α4 α5 α1 α0 + α4 α7 + α3 α5 + α1 0 G1 −1 +1 −1 +1 +1 −1 −1 +1 −1 +1 → G2 G2 −1 +1 +1 −1 −1 −1 G3 −1 +1 +1 −1 G3 −1 +1 +1 −1 +1 +1 and we apply lemma 5.2. (b) five non zero elements. • if two pairs (i, j) are full, one additional element of the form αk ϕ(Xk ) one deduces Xi and Xj , and Xk → +∞ yields an infimum. For example, pick one truth table where the convexified ϕ−risk has an infimum, the truth table of G2 , G3 leads an infimum too: indeed α0 α7 α3 α4 α5 α0 + α4 α7 + α3 α5 0 G1 −1 +1 −1 +1 +1 −1 +1 −1 +1 → G2 G2 −1 +1 +1 −1 −1 G3 −1 +1 +1 −1 G3 −1 +1 +1 −1 +1 and we apply lemma 5.2. • if one pair i is full, the three other pairs contain, each, only one element. We have cases of minimum and cases of infimum i. Consider the following truth table, where there is a unique point of α0 α7 α4 α2 α1 G1 −1 +1 +1 −1 −1 . The three couples (G1 , G2 ), minimum G2 −1 +1 −1 +1 −1 G3 −1 +1 −1 −1 +1 (G1 , G3 ), (G2 , G3 ) each yield an unique point of minimum for the convexified cost function. ii. Consider the truth table, where the convexified cost function has an α0 α7 α4 α2 α6 G1 −1 +1 +1 −1 +1 infimum: . In this case both couples G2 −1 +1 −1 +1 +1 G3 −1 +1 −1 −1 −1 (G1 , G3 ) and (G2 , G3 ) yield an infimum. (c) four entries non zero • two pairs full: existence of multiple points of minima

34

J.-M. BROSSIER, O. LAFITTE

• In the case of one pair full and two non zero entries in two of the three others: the convexified cost function has an infimum. Consider the following α0 α7 α4 α2 G1 −1 +1 +1 −1 . example of truth table: G2 −1 +1 −1 +1 G3 −1 +1 −1 −1 The two couples (G1 , G3 ) and (G2 , G3 ) yield an infimum. • In the case where each pair contains a non zero element, we can have either an infimum or a minimum. α7 α4 α2 α1 G1 +1 +1 −1 −1 . i. Truth table leading to a minimum: G2 +1 −1 +1 −1 G3 +1 −1 −1 +1 The three couples (G1 , G2 ), (G1 , G3 ), (G2 , G3 ) each yield an unique point of minimum for the convexified cost function. α7 α4 α2 α6 G1 +1 +1 −1 +1 ii. Truth table leading to an infimum: . G2 +1 −1 +1 +1 G3 +1 −1 −1 −1 The three couples (G1 , G2 ), (G1 , G3 ), (G2 , G3 ) each yield an infimum for the convexified cost function. (d) Three entries are non zero: always a point of infimum. (e) Two entries are non zero: if it is in a pair, this yields a non unique point of minimum, if it is not in a pair, it yields an infimum equal to zero. (f) One entry is non zero: it yields an infimum equal to zero. In the last three cases, at least one column is empty for all pairs of classifiers. This ends the proof of the second item of proposition 5.11. □ Appendix D. Proof of theorem 5.5 and of proposition 6.2. • In the case of the boost loss function, the system of Euler equations that one has to solve is  −α0 e−X0 + α7 eX0 − α1 e−X1 + α6 eX1 = 0    −α0 e−X0 + α7 eX0 − α2 e−X2 + α5 eX2 = 0 α e−X0 − α7 eX0 − α3 e−X3 + α4 eX3 = 0    X0 0 +X3 e = eX1 +X2 . Denote by x = α0 e−X0 − α7 eX0 .This system writes p  α6 eX1 = x2 + p( x2 )2 + α1 α6 −α1 e−X1 + α6 eX1 = x         ( x2 )2 + α2 α5  −α2 e−X2 + α5 eX2 = x  α5 eX2 = x2 + p −α3 e−X3 + α4 eX3 = −x ↔ α4 eX3 = − x2 + p( x2 )2 + α3 α4   −X X   0 0 α e − α7 e = x   α7 eX0 = − x2 + ( x2 )2 + α0 α7     X0 0 +X3 e = eX1 +X2 eX0 +X3 = eX1 +X2 . p x x Plugging the four first relations in the last one, one deduces ( ( 2 )2 + α1 α6 )( x2 + + 2 p x p p ( 2 )2 + α2 α2 )α4 α7 = (− x2 + ( x2 )2 + α3 α4 )(− x2 + ( x2 )2 + α0 α7 )α6 α5 ,

ANALYTICAL STUDY OF THE OPTIMAL COMBINATION OF BINARY CLASSIFIERS

35

that is, multiplying by the conjugate expressions on the right hand side 4 Y x ( + 2

j=0

r  x 2 2

+ αj α7−j ) = α0 α3 α5 α6 .

The equation of the frontier X0 = 0 yields a = x, hence the required relation. The equation of the frontier X1 = 0 yields b = −x, the equation of the frontier X2 = 0 yields c = −x, the equation of the frontier X3 = 0 yields d = x, hence the results. eX0 −α0 • In the case of logit, consider a0 = ln 2(α0 ϕ′ (X0 ) − α7 ϕ′ (−X0 )) = α71+e , that is X0 α0 +a0 X 0 e = α7 −a0 . The equations for the point of minimum (X1 , X2 , X3 ) are    X1 α6 eX1 −α1 −a0  0 = −a0   eX1 = αα16 −a e = αα61 +a X1    1+e +a0 0    X  eX2 = α2 −a0  α5 e 2 −α2  eX2 = α2 −a0 = −a0 α5 +a0 α5 +a0 1+eX2 ⇔ ⇔ α +a 0  eX3 = αα34 +a  α4 eX3X−α3 = a0  eX3 = α34 −a00    −a0    X1 X2 1+e 3 α0 +a0 α −a α −a α4 −a0   X X 1 0 2 0 0 3  eX1 eX2 = eX0 eX3 . e e =e e α6 +a0 α5 +a0 α3 +a0 = α7 −a0 . The equation that one has to solve is thus (D.1) −(α1 −a0 )(α2 −a0 )(α4 −a0 )(α7 −a0 )+(α0 +a0 )(α3 +a0 )(α5 +a0 )(α6 +a0 ) = 0. P Using j αj = 1, one checks that this equation writes (D.2)

a30 + Aa20 + Ba0 + C = 0.

Replacing a0 by −a/2 for X0 = 0 or by b/2 for X1 = 0 or by c/2 for X2 = 0 or by −d/2 for X3 = 0, one obtains the equations of the frontiers Xj = 0.