In this paper we introduce simple classifiers as an example of how to use the data dependent hypothesis class framework in \cite{Can02a} to explore the performance/computation trade--off in the classifier design problem. We demonstrate that simple classifiers have many remarkable properties. For example they possess computationally efficient learning algorithms with favorable bounds on estimation error, admit kernel mappings, are particularly well suited to boosting, and are fully parallelizable. In addition they are robust to the choice of learning problem which we demonstrate with the error minimization, Neyman--Pearson and min--max problems. Our experiments with synthetic and real data suggest that simple classifiers are competitive with powerful alternative methods.
A. Cannon, J. Howse, D. Hush, and C. Scovel, Simple Classifiers. Los Alamos National Laboratory Technical Report LA-UR-03-0193, 2003. [ Abstract | PostScript (639 KB) | PDF (535 KB) ]
