Optimal classification with multivariate losses

Nagarajan Natarajan, Oluwasanmi Koyejo, Pradeep Ravikumar, Inderjit S. Dhillon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Multivariate loss functions are extensively employed in several prediction tasks arising in Information Retrieval. Often, the goal in the tasks is to minimize expected loss when retrieving relevant items from a presented set of items, where the expectation is with respect to the joint distribution over item sets. Our key result is that for most multivariate losses, the expected loss is provably optimized by sorting the items by the conditional probability of label being positive and then selecting top k items. Such a result was previously known only for the F-measure. Leveraging on the optimality characterization, we give an algorithm for estimating optimal predictions in prac-tice with runtime quadratic in size of item sets for many losses. We provide empirical results on benchmark datasets, comparing the proposed algorithm to state-of-the-art methods for optimiz-ing multivariate losses.

Original languageEnglish (US)
Title of host publication33rd International Conference on Machine Learning, ICML 2016
EditorsKilian Q. Weinberger, Maria Florina Balcan
PublisherInternational Machine Learning Society (IMLS)
Pages2283-2295
Number of pages13
ISBN (Electronic)9781510829008
StatePublished - Jan 1 2016
Event33rd International Conference on Machine Learning, ICML 2016 - New York City, United States
Duration: Jun 19 2016Jun 24 2016

Publication series

Name33rd International Conference on Machine Learning, ICML 2016
Volume4

Other

Other33rd International Conference on Machine Learning, ICML 2016
CountryUnited States
CityNew York City
Period6/19/166/24/16

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Optimal classification with multivariate losses'. Together they form a unique fingerprint.

  • Cite this

    Natarajan, N., Koyejo, O., Ravikumar, P., & Dhillon, I. S. (2016). Optimal classification with multivariate losses. In K. Q. Weinberger, & M. F. Balcan (Eds.), 33rd International Conference on Machine Learning, ICML 2016 (pp. 2283-2295). (33rd International Conference on Machine Learning, ICML 2016; Vol. 4). International Machine Learning Society (IMLS).