Efficient Reformulation of 1-Norm Ranking SVM

Daiki SUEHIRO  Kohei HATANO  Eiji TAKIMOTO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.3   pp.719-729
Publication Date: 2018/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2017EDP7233
Type of Manuscript: PAPER
Category: Artificial Intelligence, Data Mining
Keyword: 
bipartite ranking,  AUC,  Ranking SVMs,  

Full Text: PDF(492.1KB)
>>Buy this Article


Summary: 
Finding linear functions that maximize AUC scores is important in ranking research. A typical approach to the ranking problem is to reduce it to a binary classification problem over a new instance space, consisting of all pairs of positive and negative instances. Specifically, this approach is formulated as hard or soft margin optimization problems over pn pairs of p positive and n negative instances. Solving the optimization problems directly is impractical since we have to deal with a sample of size pn, which is quadratically larger than the original sample size p+n. In this paper, we reformulate the ranking problem as variants of hard and soft margin optimization problems over p+n instances. The resulting classifiers of our methods are guaranteed to have a certain amount of AUC scores.