Semi-automated classification for multi-label open-ended questions
Section 3. Multi-label classification

• Previous
• Next

Consider a set of possible output labels $L=\left\{\mathrm{1,}\mathrm{2,}\dots \mathrm{,}L\right\}.$ In multi-label classification, each instance with a feature vector $x\in R^d$ is associated with a subset of these labels. Equivalently, the subset can be described as $Y\mathrm{<mo>=</mo>}\left(y_1\mathrm{,}{y}_2\mathrm{,}\dots ,y_L\right),$ where $y_i\mathrm{<mo>=</mo>}1$ if label $i$ is associated with the instance, and $y_i\mathrm{<mo>=</mo>}0$ otherwise. A multi-label classifier $h$ learns from training data to predict $h\left(x\right)\mathrm{<mo>=</mo>}\widehat{Y}\mathrm{<mo>=</mo>}\left({\widehat{y}}_1\mathrm{,}{\widehat{y}}_2\mathrm{,}\dots ,{\widehat{y}}_L\right)$ for a given $x.$

Next, we review some common multi-label algorithms and their relationship to an evaluation criterion, subset accuracy.

3.1  Evaluating multi-label algorithms in semi-automated classification

Evaluating the classification of a text answer into a single label is straightforward: the label is either correct or not and accuracy refers to the percentage of correctly classified answers; equivalently, error refers to the percentage of misclassified answers. For answers that are classified into multiple labels, there are several ways to combine the accuracy of each single label to an overall evaluation measure for the set of multiple labels. These evaluation measures include subset accuracy, Hamming loss, F-measure and log loss. For a predicted set of multiple labels, subset accuracy is 1 if all of the $L$ labels are correctly predicted and 0 otherwise. Hamming loss evaluates the fraction of misclassified labels. F-measure is the harmonic mean of precision and recall and log loss evaluates the uncertainty of the prediction averaged over the labels when a probability score for each label is given.

In this paper we develop a methodology for subset accuracy (equivalently, in terms of loss, 0/1 loss). This is a strict metric because a zero score is given even if all labels are correctly classified except one. However, subset accuracy is appropriate for semi-automated classification because if an algorithm has difficulty classifying even a single label, the entire observation needs to be manually classified. That is, automated classification shall be conducted only if the model is highly confident in the entire predicted label set.

Because subset accuracy requires that all labels are simultaneously correctly classified, we are interested in finding the label set $Y^{*}$ that maximizes the joint probability conditional on a text answer $x\text{:}$

$$Y^{*}\mathrm{<mo>=</mo>}{\text{argmax}}_{Y}P\left(Y|x\right)\mathrm{<mo>=</mo>}{\text{argmax}}_{Y}P\left(y_1\mathrm{,}\dots ,y_L|x\right)\mathrm{.}$$

In the next section we discuss common approaches to estimating the joint probability proposed in the machine learning community.

3.2  Multi-label approaches that optimize subset accuracy

Various approaches have been proposed for predicting multi-label outcomes. Since we use subset accuracy as the evaluation measure, we focus on methods that aim to maximize the joint conditional distribution.

The simplest approach, called Binary Relevance (BR), transforms a multi-label problem into separate binary problems. That is, BR constructs a binary classification model for each label independently. For an unseen observation, the prediction set of labels is obtained simply by combining the individual binary results. In other words, the predicted label set is the union of the results predicted from the $L$ binary models. If each of the binary models produces probability outcomes, BR can produce an estimate for $P\left(y_1|x\right)P\left(y_2|x\right)\dots P\left(y_L|x\right).$ Note that this coincides with the joint probability $P\left(y_1\mathrm{,}\dots ,y_L|x\right)$ if the labels are independent (conditional on $x).$ This implies that the product of the probabilities obtained by BR will estimate $P\left(y_1\mathrm{,}\dots ,y_L|x\right)$ accurately only if the labels are conditionally independent. The joint probability may be inaccurate if the labels are substantially correlated given $x.$

Another approach tailored for subset accuracy is Label Powerset learning (LP). This approach transforms a multi-label classification into a multi-class (i.e., multinomial) problem by treating each unique label set $Y$ that exists in the training data as a single class. For example, when $L=3$ there could be up to $2^3$ classes $c_i,$ $\left(i\mathrm{<mo>=</mo>}\mathrm{1,}\dots ,8\right)$ observed in the training data. Then any algorithm for multi-class problems can be applied using the transformed $c_i$ classes. Training a multi-class classifier takes into consideration dependencies between labels. For a new observation, LP predicts the most probable class (i.e., the most probable label set). If an algorithm for multi-class data gives probabilistic outputs (some algorithms classify without computing probabilities), LP directly estimates the class probabilities (i.e., the joint probability $P(Y|x)).$ However, this approach cannot estimate the joint probability for any label set unseen in the training data. As a consequence, if the true label set of the new observation is an unseen observation the prediction cannot be correct. Another drawback of LP is that the number of classes in the transformed problem can increase exponentially (up to $2^L$ number of classes). This can be problematic when L is large since each combination of labels may be present in just one or a few observations in the training data which makes the learning process difficult.

A third approach to multi-label learning is Classifier Chains (CC) (Read, Pfahringer, Holmes and Frank, 2009, 2011). As in binary relevance, in CC also a binary model is fit for each label. However, CC fits the binary models sequentially and uses the binary label results obtained from previous models as additional predictors in subsequent models. That is, the model for the $i^{\text{th}}$ label $y_i$ uses $x$ and $y_1\mathrm{,}\dots ,y_{i-1}$ as features. (For example, the model for $y_1$ uses $x$ as features, the model for $y_2$ uses $x$ and $y_1$ as features and so on.) Passing label information between binary classifiers allows CC to take label dependencies into account. In the prediction stage, CC successively predicts the labels one at a time. The prediction results of the previous labels are used for predicting the next label in the chain.

This idea is extended to Probabilistic Classifier Chains (PCC) (Dembczyński et al., 2010). PCC explains CC using a probabilistic model. Specifically, the conditional joint distribution can be described as

$$P\left(y_1\mathrm{,...,}{y}_L|x\right)\mathrm{<mo>=</mo>}P\left(y_1|x\right){\displaystyle \prod _{j\mathrm{<mo>=</mo>\; 2}}^L}P\left(y_j|y_1\mathrm{,}\dots ,y_{j-1}\mathrm{,}x\right)(3.1)$$

and PCC estimates the probabilities $P\left(y_1|x\right),P\left(y_2|x\mathrm{,}{y}_1\right),\dots ,P\left(y_L|x\mathrm{,}{y}_1\mathrm{,}{y}_2\mathrm{,}\dots ,y_{L-1}\right).$

PCC finds the label set that maximizes the right hand side of equation (3.1). However, there is no closed-form solution for finding the label set. A few different solutions have been suggested. Dembczyński et al. (2010) used an exhaustive search (ES) that considers all possible combinations. However, an exhaustive search may not be practical when $L$ is large, because the number of possible combinations $\left(2^L\right)$ increases exponentially. To overcome this problem, optimization strategies based on the uniform cost search (UCS) (Dembczyński, Waegeman and Hüllermeier, 2012) and the $A^{*}$ algorithm (Mena, Montañés, Quevedo and Del Coz, 2015) have been proposed. First, the estimated joint conditional probability may be represented by a probability binary tree. Then a search algorithm finds the optimal path (in our case, the path that gives the highest joint probability) from the root and the terminal node. Compared with ES, UCS substantially reduces the computational cost for PCC to reach the label set with the highest joint probability (Dembczyński et al., 2012).

In theory, when applying the product rule, the order of the categories $y_1\mathrm{,}\dots ,y_L$ does not matter. For example, both $P\left(y_1|x\right)P\left(y_2|y_1\mathrm{,}x\right)$ and $P\left(y_2|x\right)P\left(y_1|y_2\mathrm{,}x\right)$ equal to $P\left(y_1\mathrm{,}{y}_2|x\right).$ In practice, the two chains may lead to different estimates. This means the performance of PCC may be affected by the order of the labels in the chain.

To alleviate the influence of the category order, an ensembling approach (EPCC) (Dembczyński et al., 2010) that combines multiple probabilistic chains has been proposed. First $m$ PCC models are trained where each PCC model is based on a randomized order of the labels. In the prediction stage, the average conditional joint probability over the $m$ PCC models is computed for each possible label set. Then the predicted label set is the label set with the highest average predicted probability. Let ${\widehat{P}}_j\left(Y|x\right)$ be the conditional joint probability estimated by the $j^{\text{th}}$ PCC model. The ensemble strategy predicts the label set $\widehat{Y}$ such that

$$\widehat{Y}\mathrm{<mo>=</mo>}{\text{argmax}}_Y\frac{{\displaystyle {\sum }_{j\mathrm{<mo>=</mo>\; 1}}^m{\widehat{P}}_j\left(Y|x\right)}}{m}\mathrm{.}$$

Note that EPCC does not combine the predicted label sets but conditional joint probabilities. To find the highest average probability from $m$ PCC models, all individual probabilities are required and this forces us to use ES to compute the conditional joint probability for all $2^L$ label combinations from all $m$ PCC models. Hence, although EPCC reduces the problem of influence of label order, the method will not be useful if the problem deals with a large number of labels or when $m$ is large. To reduce the computational cost for combining multiple PCC models, we propose a new approach to ensembling the PCC models in the next section.

• Previous
• Article main page
• Next