To address the challenges of minimizing the future misclassification rate of a predictor, Lanckriet et al. [1] proposed minimax probability machines (MPMs) based on the minimax approach to build binary classifiers, which minimize the upper bounds of the misclassification rate in a worst-case scenario using all possible class conditional distributions and their moments (mean and covariance). They used empirical estimates for the value of the moments because true moments are not known in practice.

In this paper, the authors extend the approach of Lanckriet et al. and present high-probability MPM, taking into consideration the uncertainty in empirical moments and their deviation from true moments and incorporating the same into the minimax principle.

The authors employ a statistical approach to observe the differences while considering the true moments and the estimated moments to compute the probability of a random vector being correctly placed by a decision boundary based on Mahalanobis distance and convex set properties. They then compute high-probability bounds on the differences and introduce a function based on regularization factor and input weights, which incorporates the uncertainty to find an optimal linear decision boundary.

To map the approach to higher dimensions and find an optimal hyper plane, which minimizes the misclassification rate, the authors reformulate the minimax problem in terms of a kernel function that satisfies Mercer’s condition.

The authors test the approach extensively using the data sets from the UC Irvine Machine Learning Repository and the toy data set (used in Lanckriet et al. [1]) and obtain better accuracy over the approach used in Lanckriet et al. and two other popular binary classification algorithms (namely Fisher’s discriminant analysis and support vector machines).

The paper would be of core interest for practitioners of machine learning and deep learning techniques for solving hard recognition/classification problems.