Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the construction of a K-class classifier using O(log K) binary classifiers, focusing on the performance limits when these classifiers are hyperplanes in a Gaussian setting. The authors derive explicit performance bounds for various decoding and dimensional scenarios, revealing how the combination of simple binary decisions can effectively classify multiple classes despite noise. Empirical simulations corroborate the theoretical findings, highlighting the robustness of the proposed approach in practical applications.
Combining simple binary classifiers can achieve sophisticated multiclass classification, but performance is fundamentally limited by noise and dimensionality.
We consider the problem of constructing a $K$-class classifier from the combination of $O(\log K)$ simple binary classifiers -- this is a natural paradigm to construct a sophisticated classifier in a distributed manner with each agent performing a relatively straightforward task. We study the fundamental performance limits of such a classifier when the corresponding binary classifiers are hyperplanes. For a stylized Gaussian setting where the $K$ class centers are independent Gaussian points in $\mathbb R^d$ and the observations are corrupted by Gaussian noise, we derive explicit performance bounds across several decoding and dimensional regimes. Extensive simulation experiments provide strong empirical validation of the presented theoretical results.