Online Optimization Methods for the Quantification Problem
Open Access
- 13 August 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1625-1634
Abstract
The estimation of class prevalence, i.e., of the fraction of a population that belongs to a certain class, is an important task in data analytics, and finds applications in many domains such as the social sciences, market research, epidemiology, and others. For example, in sentiment analysis the goal is often not to estimate whether a specific text conveys a positive or a negative sentiment, but rather to estimate the overall distribution of positive and negative sentiments, e.g., in a certain time frame. A popular way of performing the above task, often dubbed quantification, is to use supervised learning in order to train a prevalence estimator from labeled data. In the literature there are several performance metrics for measuring the success of such prevalence estimators. In this paper we propose the first online stochastic algorithms for directly optimizing these quantification-specific performance measures. We also provide algorithms that optimize hybrid performance measures that seek to balance quantification and classification performance. Our algorithms present a significant advancement in the theory of multivariate optimization; we show, via a rigorous theoretical analysis, that they exhibit optimal convergence. We also report extensive experiments on benchmark and real data sets which demonstrate that our methods significantly outperform existing optimization techniques used for these performance measures.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Class distribution estimation based on the Hellinger distanceInformation Sciences, 2013
- Pegasos: primal estimated sub-gradient solver for SVMMathematical Programming, 2010
- Transfer estimation of evolving class priors in data stream classificationPattern Recognition, 2010
- A Method of Automated Nonparametric Content Analysis for Social ScienceAmerican Journal of Political Science, 2009
- Cutting-plane training of structural SVMsMachine Learning, 2009
- Quantifying counts and costs via classificationData Mining and Knowledge Discovery, 2008
- Verbal Autopsy Methods with Multiple Causes of DeathStatistical Science, 2008
- Evaluation of different biological data and computational classification methods for use in protein interaction predictionProteins: Structure, Function, and Bioinformatics, 2006
- Virtual Screening of Molecular Databases Using a Support Vector MachineJournal of Chemical Information and Modeling, 2005
- Information Theory and Statistics: A TutorialFoundations and Trends® in Communications and Information Theory, 2004