An exact approach to maximize area under receiver operator characteristic curve for multi-instance learning

Abstract

The purpose of this study is to solve the multi-instance classi cation problem by directly maximizing the area under Receiver Operating Characteristic (ROC) curve (i.e., AUC). We derive a mixed integer linear programming model that produces the best possible hyperplane-based classi er for multi-instance classi cation. Our study sheds a light on the potential of hyperplane-based approaches, re ecting cross validation (CV) results for benchmark instances. As we maximize AUC directly, a hyperplane-based classi er can only coincidentally provide a better CV accuracy than those presented in this paper. Finally, we present how Kernel trick can be applied to produce nonlinear classi ers that maximize AUC.

Bu çalışmanın amacı çoklu örnek sınıflandırma problemini Alıcı İşletim Karakteristiği (ROC) eğrisi altındaki alanı (yani, AUC) doğrudan maksimize ederek çözmektir. Çok örnekli sınıflandırma için mümkün olan en iyi hiperdüzlem tabanlı sınıflandırıcıyı üreten karma bir tamsayı doğrusal programlama modeli türetilmiştir. Çalışmamız, kıyaslama örnekleri için çapraz doğrulama (CV) sonuçlarını yansıtan hiperdüze tabanlı yaklaşımların potansiyeline ışık tutmaktadır. Doğrudan AUC'yi en üst düzeye çıkardıkça, hiperdüze tabanlı bir sınıflandırıcı sadece şans eseri bu yazıda sunulanlardan daha iyi bir CV doğruluğu sağlayabilir. Son olarak, AUC'yi maksimize eden doğrusal olmayan sınıflandırıcılar üretmek için çekirdek püf noktasının nasıl uygulanabileceğini sunuyoruz.