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

This paper addresses the problem of combining a fixed set of binary classifiers into a single, more accurate ensemble model. Unlike traditional boosting or bagging methods that build classifiers sequentially or on resampled data, this study focuses on optimizing the linear combination of a pre-existing list of classifiers. The authors propose a method to structure the training data using a truth table, which partitions the dataset into $2^m$ equivalence classes based on the agreement or disagreement of $m$ classifiers. This approach reduces the complexity of the empirical risk minimization problem from one dependent on the number of training examples ($n$) to one dependent only on the number of classifiers ($m$).

By generalizing the concept of classification-calibrated functions to $m$ dimensions, the authors establish sufficient conditions for the existence and uniqueness of a global minimum for the convexified empirical risk. For the specific case of three classifiers, the paper provides an exhaustive classification of configurations that lead to unique solutions, infima, or non-unique minima. Furthermore, the authors derive explicit analytical formulas for optimal weights when using Exponential (Boost) and Logistic (Logit) loss functions, effectively bypassing the need for iterative numerical optimization. They also introduce the concept of $\phi$-frontiers to evaluate the stability of the resulting classifier and the quality of the underlying data.

This work provides a rigorous mathematical foundation for ensemble learning that moves beyond black-box iterative optimization. By transforming the training set into a truth table, the authors make it possible to analytically determine the optimal combination of classifiers and identify when a unique optimal solution is impossible to achieve. This is particularly useful for practitioners who need to understand the stability of their ensemble models and diagnose whether poor performance stems from the classifier set itself or the inherent quality of the training data.