Optimization Online


An Extension of a Minimax Approach to Multiple Classification

Tomonari Kitahara (kitahara***at***ml.me.titech.ac.jp)
Shinji Mizuno (mizuno***at***me.titech.ac.jp)
Kazuhide Nakata (knakata***at***me.titech.ac.jp)

Abstract: When the mean vectors and the covariance matrices of two classes are available in a binary classification problem, Lanckriet et al.\ \cite{mpm} propose a minimax approach for finding a linear classifier which minimizes the worst-case (maximum) misclassification probability. We extend the minimax approach to a multiple classification problem, where the number $m$ of classes could be more than two. Assume that the mean vectors and the covariance matrices of all the classes are available, but no further assumptions are made with respect to class-conditional distributions. Then we define a problem for finding linear classifiers which minimize the worst-case misclassification probability $\bar \alpha$. Unfortunately, no efficient algorithms for solving the problem are known. So we introduce the maximum pairwise misclassification probability $\bar \beta$ instead of $\bar \alpha$. It is shown that $\bar \beta$ is a lower bound of $\bar \alpha$ and a good approximation of $\bar \alpha$ when $m$ or $\bar \alpha$ are small. We define a problem for finding linear classifiers which minimize the probability $\bar \beta$ and show some basic properties of the problem. Then the problem is transformed to a parametric Second Order Cone Programming problem (SOCP). We propose an algorithm for solving it by using properties of the problem. We conduct preliminary numerical experiments and confirm that classifiers computed by our method work very well to benchmark problems.

Keywords: multiple classification, minimax approach, second order cone programming

Category 1: Applications -- Science and Engineering (Data-Mining )

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation: Department of Industrial Engineering and Management, Tokyo Institute of Technology, 2006.


Entry Submitted: 06/18/2006
Entry Accepted: 06/18/2006
Entry Last Modified: 03/11/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society