Abstract

Statistical classification is traditionally studied using probability, decision theory, information theory, and optimisation. We show that classification problems also possess a natural combinatorial and topological structure. Given a binary classification problem, we introduce the notion of a decision-sufficient feature set, namely a collection of features that preserves the optimal Bayes decision rule. Rather than focusing on a single optimal feature subset, we study the entire family of decision-sufficient feature sets. We prove that this family forms an order filter in the Boolean lattice of feature subsets and that its complement forms an abstract simplicial complex. Consequently, every classification problem canonically determines a topological object, called the decision complex, the faces of whichh correspond to feature subsets that fail to preserve optimal decisions. This viewpoint leads naturally to three invariants: the decision core, the decision dimension, and the decision complex. General structural results are established, and a complete characterisation is obtained for Gaussian-discriminant models. In that setting, the decision core coincides with the support of the discriminant vector, yielding explicit formulae for the decision core and decision dimension. These results establish a new connection between statistical decision theory and combinatorial topology.

Keywords