  Algorithms for solving the linear classification problem have a long history,
dating back at least to 1936 with linear discriminant analysis. For linearly
separable data, many algorithms can obtain the exact solution to the
corresponding 0-1 loss classification problem efficiently, but for data which
is not linearly separable, it has been shown that this problem, in full
generality, is NP-hard. Alternative approaches all involve approximations of
some kind, including the use of surrogates for the 0-1 loss (for example, the
hinge or logistic loss) or approximate combinatorial search, none of which can
be guaranteed to solve the problem exactly. Finding efficient algorithms to
obtain an exact i.e. globally optimal solution for the 0-1 loss linear
classification problem with fixed dimension, remains an open problem. In
research we report here, we detail the rigorous construction of a new
algorithm, incremental cell enumeration (ICE), that can solve the 0-1 loss
classification problem exactly in polynomial time. We prove correctness using
concepts from the theory of hyperplane arrangements and oriented matroids. We
demonstrate the effectiveness of this algorithm on synthetic and real-world
datasets, showing optimal accuracy both in and out-of-sample, in practical
computational time. We also empirically demonstrate how the use of approximate
upper bound leads to polynomial time run-time improvements to the algorithm
whilst retaining exactness. To our knowledge, this is the first,
rigorously-proven polynomial time, practical algorithm for this long-standing
problem.
