Neyman-Pearson and minimax learning

In binary classification there are two types of errors, and in many applications these may have very different costs. We consider two learning frameworks that address this issue: minimax classification, where we seek to minimize the maximum of the false alarm and miss rates, and Neyman-Pearson (NP) classification, where we seek to minimize the miss rate while ensuring the false alarm rate is less than a specified level $\alpha$. We study the training of support vector machine (SVM) classifiers with respect to the minimax and Neyman-Pearson criteria. In principle, these criteria can be optimized in a straightforward way using a cost-sensitive SVM. In practice, however, because these criteria require especially accurate error estimation, standard techniques for tuning SVM parameters, such as cross-validation, can lead to poor classifier performance. To address this issue, we first prove that the usual cost-sensitive SVM, here called the $2C$-SVM, is equivalent to another formulation called the $2\nu$-SVM. We then leverage a characterization of the $2\nu$-SVM parameter space to develop a simple but powerful approach to error estimation based on smoothing. In an extensive experimental study we demonstrate that smoothing significantly improves the accuracy of cross-validation error estimates, leading to dramatic performance gains. Furthermore, we propose coordinate descent strategies that offer significant gains in computational efficiency, with little to no loss in performance.

Authors: Mark Davenport, Richard Baraniuk, Clayton Scott

Publications: Thesis (2007), SSP (2007), ICASSP (2006)

Related research at Rice