A Review on Quantification Learning <s> ORDINAL QUANTIFICATION <s> Machine learning methods for classification problems commonly assume that the class values are unordered. However, in many practical applications the class values do exhibit a natural order--for example, when learning how to grade. The standard approach to ordinal classification converts the class value into a numeric quantity and applies a regression learner to the transformed data, translating the output back into a discrete class value in a post-processing step. A disadvantage of this method is that it can only be applied in conjunction with a regression scheme. ::: ::: In this paper we present a simple method that enables standard classification algorithms to make use of ordering information in class attributes. By applying it in conjunction with a decision tree learner we show that it outperforms the naive approach, which treats the class values as an unordered set. Compared to special-purpose algorithms for ordinal classification our method has the advantage that it can be applied without any modification to the underlying learning scheme. <s> BIB001 </s> A Review on Quantification Learning <s> ORDINAL QUANTIFICATION <s> This paper promotes a new task for supervised machine learning research: quantification - the pursuit of learning methods for accurately estimating the class distribution of a test set, with no concern for predictions on individual cases. A variant for cost quantification addresses the need to total up costs according to categories predicted by imperfect classifiers. These tasks cover a large and important family of applications that measure trends over time.The paper establishes a research methodology, and uses it to evaluate several proposed methods that involve selecting the classification threshold in a way that would spoil the accuracy of individual classifications. In empirical tests, Median Sweep methods show outstanding ability to estimate the class distribution, despite wide disparity in testing and training conditions. The paper addresses shifting class priors and costs, but not concept drift in general. <s> BIB002 </s> A Review on Quantification Learning <s> ORDINAL QUANTIFICATION <s> Many business applications track changes over time, for example, measuring the monthly prevalence of influenza incidents. In situations where a classifier is needed to identify the relevant incidents, imperfect classification accuracy can cause substantial bias in estimating class prevalence. The paper defines two research challenges for machine learning. The `quantification' task is to accurately estimate the number of positive cases (or class distribution) in a test set, using a training set that may have a substantially different distribution. The `cost quantification' variant estimates the total cost associated with the positive class, where each case is tagged with a cost attribute, such as the expense to resolve the case. Quantification has a very different utility model from traditional classification research. For both forms of quantification, the paper describes a variety of methods and evaluates them with a suitable methodology, revealing which methods give reliable estimates when training data is scarce, the testing class distribution differs widely from training, and the positive class is rare, e.g., 1% positives. These strengths can make quantification practical for business use, even where classification accuracy is poor. <s> BIB003 </s> A Review on Quantification Learning <s> ORDINAL QUANTIFICATION <s> Sentiment classification has become a ubiquitous enabling technology in the Twittersphere, since classifying tweets according to the sentiment they convey towards a given entity (be it a product, a person, a political party, or a policy) has many applications in political science, social science, market research, and many others. In this paper we contend that most previous studies dealing with tweet sentiment classification (TSC) use a suboptimal approach. The reason is that the final goal of most such studies is not estimating the class label (e.g., Positive, Negative, or Neutral) of individual tweets, but estimating the relative frequency (a.k.a. "prevalence") of the different classes in the dataset. The latter task is called quantification, and recent research has convincingly shown that it should be tackled as a task of its own, using learning algorithms and evaluation measures different from those used for classification. In this paper we show, on a multiplicity of TSC datasets, that using a quantification-specific algorithm produces substantially better class frequency estimates than a state-of-the-art classification-oriented algorithm routinely used in TSC. We thus argue that researchers interested in tweet sentiment prevalence should switch to quantification-specific (instead of classification-specific) learning algorithms and evaluation measures. <s> BIB004 </s> A Review on Quantification Learning <s> ORDINAL QUANTIFICATION <s> In recent years there has been a growing interest in text quantification, a supervised learning task where the goal is to accurately estimate, in an unlabelled set of items, the prevalence (or "relative frequency") of each class c in a predefined set C. Text quantification has several applications, and is a dominant concern in fields such as market research, the social sciences, political science, and epidemiology. In this paper we tackle, for the first time, the problem of ordinal text quantification, defined as the task of performing text quantification when a total order is defined on the set of classes; estimating the prevalence of "five stars" reviews in a set of reviews of a given product, and monitoring this prevalence across time, is an example application. We present OQT, a novel tree-based OQ algorithm, and discuss experimental results obtained on a dataset of tweets classified according to sentiment strength. <s> BIB005
To the best of our knowledge, only one algorithm has been proposed to tackle ordinal quantification problems. Recently, BIB005 propose the idea of exploiting the apparently good performance of PCC (see Section 6.4) for sentiment quantification BIB004 to build a ordinal quantification model composed by a collection of binary PCC's arranged in a decision tree. This method, called Ordinal Quantification Trees (OQT), is also based on the decomposition proposed by BIB001 for ordinal classification. Given a ordinal quantification training set, with a set of clases { 1 , . . . , l }, OQT learns l − 1 binary PCC, in which each probabilistic classifier j separates two group of classes: { 1 , . . . , j } from { j+1 , . . . , l }. For instance, if l = 5, then four binary probabilistic classifiers are learned: (i) The method has two main procedures: (1) To arrange the binary probabilistic classifiers in the tree. OQT follows the classical divideand-conquer strategy for building a decision tree: OQT places at the root of the tree the binary PCC model with best quantification accuracy, measured in terms of KLD using a separate validation set. The process is repeated recursively for the left branch and for the right branch until all l − 1 PCC models are arranged. Figure 5 shows an example with five classes. (2) To compute the prevalence for each class. Given a test set, T , for each example, x i , we compute first the probabilities of belonging to each class, and then we compute the average probability for each class over all the examples x i ∈ T . The key step is how to compute, for a testing example, the probability of each class. The posterior probability for a class is 74:31 calculated in a recursive, hierarchical way: We have to multiply the posterior probability returned for all the models that lie in the path from the root to the leaf representing such class. For instance, to compute the probability of belonging to class 3 in the OQT in Figure 5 , we just need to multiply Notice that the order of the models on the tree is crucial in this computation. The same models arranged differently in the tree produce a different set of probabilities for the set of classes. BIB002 BIB003 introduces several methods for cost quantification. Most of them are adaptations of his methods for binary quantification. He focuses on estimating the total cost of the positive class, denoted as S, and the approach followed is the one described in Section 2.3, that is, first the method estimates the average cost of the positive class C + , and then multiply it by the number of positives examples predicted using a binary quantifier/classifier over a test set T :