Active Online Classification via Information Maximization

1 Introduction

In the online classification paradigm, a classifier observes instances in a sequential manner. After each observation, the classifier predicts the class label of the observed instance and receives as feedback the correct class label. The online classifier may then update its prediction mechanism, presumably improving the accuracy of future predictions [4]. To motivate our derivation we consider a stream of instances of cooccurrence data, each labeled with one or more labels out of a set of Nl possible labels. Let Nf denote the number of distinct features in our data, and let C denote a co-occurrence matrix with Nf rows and Nl columns, such that C(i, k) indicates the number of occurrences of the i-th feature in all instances associated with the k-th label. If the assigned labels indeed represent distinct classes, one may expect an approximated block structure in C, where each block consists of features representative of a particular class. For example, this expectation underlies most text classification schemes under the standard bag of words model.

A natural route to quantify the statistical signal in C is via the mutual information [3] embodied in a matrix P, which is the normalized form of C, denoted henceforth Ifl. This information quantifies the average number of bits revealed Koby Crammer Department of Electrical Engineering The Technion Haifa, Israel koby@ee.technion.ac.il over the label identity while observing a particular feature in a given instance. If each label is characterized by a set of distinct features, we expect that C will have an approximated block structure, and correspondingly that Ifl will be relatively high. The current work exploits precisely this intuition. Specifically, given a training set of labeled instances, the goal of a classification scheme is to properly label the remaining test set instances. The above discussion implies that if one constructs C based on the entire data where the test set instances are properly labeled, a relatively clear structure will emerge, with an associated relatively high Ifl value. In contrast, if the test set instances are poorly labeled, the resulting C will have little structure, if any, as the wrong labels over the test set will smear the statistical signal arising from the training set. Correspondingly, a relatively low Ifl value will be observed. Thus, our starting point here is to cast supervised classification as labeling the test set instances so to maximize the mutual information, Ifl. Importantly, this information should be estimated via a co-occurrence matrix, C, constructed out of the labeled training instances along with the test set instances and their predicted labels. In Fig. 1 we present simulation results over real world data that support this proposed formulation.

∗ Present affiliation: Yahoo Research, New York.

Various algorithms can be derived to find labellings that aim to maximize If l. Here, we focus on a simple online learning strategy [4]. Specifically, we examine the matrix C which is constructed using the instances scanned thus far and their associated labels. Given a new instance, x, the algorithm performs Nl trials, simulating the addition of x to the construction of C where it is labeled with each of the Nl possible labels; the particular label resulting with an updated matrix C with an associated maximal information Ifl will be predicted as x's label.

In classical online learning, once a label is predicted the true label is revealed and the prediction mechanism is updated accordingly. This setup is not suitable if the cost of each true label is relatively high. In the active learning paradigm this issue is addressed via selective sampling techniques in which the label is queried only if the relevant prediction is relatively uncertain [11; 14; 2; 12]. Our framework can naturally embody this intuitive principle. Specifically, we examine the loss in Ifl due to assigning x with the second best label, and demonstrae how this loss estimates prediction uncertainty. We further use this information loss in two practically important scenarios. First, in order to abstain highly uncertain predictions so to increase precision at the cost of recall reduction. Second, in asking for instances' labels only if the associated prediction is considered highly uncertain. We demonstrate the validity of our approach for the task of text classification over real world corpora. Comparisons with state-of-the-art online classification schemes [17; 10; 5; 9; 6; 7] suggest that in spite of its simplicity, our proposed method is comparable or superior to these alternative methods.

2 Classification via information maximization

Let F be a discrete random variable with Nf possible values that represent the set of distinct features in our data, {f1....fNf }. Let X be a random variable with Nx possible values that represent the set of Nx instances in our data, {x1...xNx }. Let n(fi, xj) be the number of occurrences of the i-th feature in the j-th instance. Then, ignoring the order of the features observed in xj, as done, e.g., in the standard bag of words model [18], we obtain that the empirical probability of observing fi in xj is

Further, for brevity we assume a uniform prior, P(xj) = 1/Nx, ending up with an estimation of the joint distribution, P (fi, xj ) = P (xj )P (fi|xj ). Next, we denote by L a random variable with Nl possible values that represent the distinct labels, {l1...lNl }. The assignment of xj with a label lk can be represented via P (lk|xj ) = 1 while P (lk′ |xj ) = 0 ∀ k′ ̸= k. 1

1 Clearly, it is also possible to represent the assignment of xj with more than one label. Nonetheless, for brevity purposes we limit our derivation to the case where each instance is solely assigned with one label.

Considering the joint distribution over all variables mentioned, we haveP (fi, xj , lk) = P (fi, xj )P (lk|xj ) (2)

where we used P(lk|xj, fi) = P(lk|xj), namely that instance identity, xj, solely determines its label. Given this formulation we have

where j ∈ lk denotes P(lk|xj) = 1. It is further easy to verify that under this formulation

where n(k) denotes the number of instances assigned with the k-th label, lk. Given P(fi, lk), one can quantify the dependency between the features and the labels via the mutual information [3]

Our motivating underlying assumption is that each label, or class, is characterized by a set of distinct features. Hence, we expect an approximated block-structure in P(fi, lk); correspondingly, Ifl is expected to be relatively high. Importantly, Ifl can be estimated over the training set labeled instances, as well as test set instances for which the label is predicted. Accurate predictions are expected to even sharpen the statistical dependency observed between F and L over the training set, resulting with relatively high Ifl values. In contrast, poor predictions are expected to smear the statistical dependency between F and L, resulting with relatively low Ifl values. Here, we propose to turn this intuitive understanding over its head, and to predict the labels of the test set instances such that Ifl will be maximized.

3 An online learning setup

Various algorithms can be derived to predict labels aiming to maximize Ifl. Here, we focus on online classification. Under this paradigm, at any given time point, only one instance is examined and its label is predicted. In classical online learning, once a prediction is provided, the true label is revealed, and accordingly the learning model and the prediction loss are updated [4]. In our context, this corresponds to a situation where Nx instances were already scanned, and the label of each was predicted and then revealed. Next, a new instance, xN + x , is encountered, where for conciseness of notation we used N + x = Nx + 1. Let lk be the tentative label predicted for xN + x , and further denote PN + x ≡ P (fi|xN + x ). Observing xN + x requires to update the probabilistic model and we use the superscript + to distinguish between components of the probabilistic model estimated before and after observing xN + x . First, if before observing xN + x we had P(xj) = 1/Nx ∀ j, after observing xN + x we have P +(xj) = 1/N + x . Similarly, n+(k′ ) = n(k′ ) ∀ k′ ̸= k, while n+(k) = n(k) + 1. In addition, we have

Finally, using Eq. 4 it is easy to verify that P +(fi|lk′ ) = P (fi|lk′ ) ∀ k′ ̸= k; in contrast, after little algebra, for lk we obtain

where we used ∑j∈lk P(fi|xj) = n(k)P(fi|lk), as can be derived from Eq. 4. In particular, the online update rules in Eq. 6 and Eq. 7 imply that once xN + x is assigned with a particular label, updating P(f, l) is straightforward and has linear complexity of O(Nf ).

3.1 Online assignment rule to maximize Ifl

In a straightforward approach one may simulate assigning xN + x with each possible label, find all the associated joint distributions, and eventually assign xN + x with the label for which Ifl is maximized. This process involves Nl simulation trials, each with a complexity of O(NfNl) for estimating Ifl. Thus, the overall complexity will be O(N 2 l Nf). However, a more efficient approach arises from the analogy between the problem at hand and the problem of unsupervised clustering via sequential informationmaximization [21]. Specifically, in that earlier work, the goal is to cluster instances such that the information between the obtained clusters and the features is maximized. If we identify each cluster with a particular label in our setup, we see that the problems are in perfect analogy, except for two important differences. First, in [21] it is assumed that the entire data is available in advance; in contrast, here we assume an online learning setup that in particular requires updating P (f, l) after encountering each new instance. Second, in [21] the focus is on unsupervised clustering, while here we expand this framework for supervised classification where labels are exploited during the classification process. Nonetheless, using the analogy between the two problems, we observe that assigning xN + x with a label such that Ifl will be maximized is equivalent to assigning in [21] a singleton cluster that consists solely of xN + x to one of the existing clusters so to maximize the information between the clusters and the features. Adapting the derivation in [21] to our needs, we conclude that the assignment that locally maximizes Ifl is given by

where JS stands for the Jensen-Shannon divergence [16], defined by

where in our case π1 = n(k′ )/(n(k′ )+1), π2 = 1/(n(k′ )+ 1), p1 = P(f|lk′ ), p2 = PN + x , ¯ p = π1p1 + π2p2, and KL(p(y)‖q(y)) = ∑y p(y) log(p(y)/q(y)) is the KL divergence [3]. In short, to maximize Ifl one should assign xN + x with the label lk for which the conditional distribution P(f|lk) is most similar to PN + x in terms of Eq. 8. Since the complexity of estimating the JS divergence is O(Nf), the overall complexity of predicting the label of a new instance is O(NlNf ).

3.2 Estimating prediction uncertainty

Properly estimating the uncertainty associated with a prediction is practically useful in various scenarios. In order to address this issue we adopt a simple Best-versus-Second-Best approach (cf. [12]). Specifically, given an incoming instance, xN + x , we denote by lk1 the label for which Eq. 8 is minimized, namely the predicted label. We further denote by lk2 the second best label, namely the label for which Eq. 8 is minimized over all k ̸= k1. Thus, the loss in Ifl due to assigning xN + x with the second best label is given by

A relatively high g(xN + x ) value implies that lk1 is clearly distinguished from all other labels for xN + x , namely the prediction is relatively certain. Conversely, low g(xN + x ) implies that at least two labels are hard to distinguish as potential assignments for xN + x , hence high uncertainty should be associated with the prediction. Finally, instead of considering g(xN + x ) directly, we consider a normalized form, reflecting our intuition that prediction uncertainty should gradually decrease as the prediction mechanism being exposed to more instances. Specifically, we define the uncertainty associated with the label predicted for xN + x via

We found this simple definition to work well in practice. Nonetheless, other definitions could certainly be exploited.

3.3 Algorithms

We define three algorithms that rely on the derivation above. The first, denoted oMaxI, is using the classical online learning paradigm. Given a stream of instances, the label of each incoming instance, xj, is predicted using Eq. 8; next, the true label is revealed and used to update P(f, l) via Eq. 6 and Eq. 7. The second algorithm, denoted oAbMaxI, is exploiting the uncertainty score, Eq. 12, to abstain relatively uncertain predictions. Specifically, a spurious "abstain" class is defined, and xj is classified to this class if and only if the associated u(xj) score is greater than some pre-specified threshold, denoted u∗ . In this algorithm as well, after each prediction the true label is revealed and P(f, l) is updated accordingly. The underlying motivation is that by abstaining relatively uncertain predictions one may increase classification precision at the cost of reducing the associated classification recall. The single input parameter, u∗ , may be thought of as a knob to control the precision/recall trade-off. Finally, in the third algorithm, denoted oAcMaxI, we exploit u(xj) within the active-learning paradigm. Specifically, the true label of xj is requested and revealed if and only if u(xj) is greater than some pre-specified threshold, denoted u∗ , that now represents a knob to control training set size. High u∗ value implies a stringent threshold, leading to a low rate of requesting the true label. Conversely, low u∗ value will result with a high rate of requesting the true label. In any event, due to the division by (N + x )2 in Eq. 12 the obtained uncertainty scores are expected to gradually decrease, leading to a decreasing rate of asking for the true label, given that u∗ is fixed. A Pseudo-code describing all three proposed algorithms is given in Fig. 2.

4 Experimental Design

4.1 Datasets and run details

We demonstrate the performance of our approach over the task of text classification. Our medium size datasets consisted of the 20NG corpus [13], the Reuters-21578 corpus 2 , and a subset of the RCV1 corpus [15], denoted as subRCV1. Following the pre-processing of these datasets reported in [21], we had for the 20NG corpus Nx = 16, 323, Nf = 2, 000, Nl = 20; for the Reuters-21578 corpus Nx = 8, 796, Nf = 2, 000, Nl = 10; and for the subRCV1 corpus Nx = 22, 463, Nf = 2, 000, Nl = 10. In addition, we considered two large corpora. First, all documents in the entire RCV1 corpus [15] associated with the

2 Originally downloaded from www.daviddlewis.com/resources/testcollections/reuters21578/

50 most frequent topics; thus, for this corpus we had Nx = 804, 414, Nf = 5, 000, Nl = 50. And second, a large subset of the pages collected from the USA government ".gov" domain provided by the TREC conference [8], for which we had Nx = 695, 017, Nf = 5, 000, Nl = 50. In all five datasets the words were selected through feature selection by information gain, where the information examined is the information in the words-documents count matrix [21]. Importantly, this standard feature selection scheme is completely unsupervised and does not involve any usage of documents' labels. However, we note that this feature selection assumes access to the entire corpus of documents, which is not valid in real world online text classification. To somewhat address this concern, in the RCV1 corpus the 5000 words were selected based on the words-documents counts matrix constructed only from the first 20, 000 documents in the corpus, that are typically used as the training set for this corpus [15]. Finally, we note that the Reuters-21578 corpus and the RCV1 corpus are multi-labeled. In particular, in our RCV1 data, each document was assigned with ≈ 3 different labels. For the oAbsMaxI and the oAcMaxI algorithms we used u∗ = 0.001 for the three medium size datasets, and u∗ = 0.0001 for the two large datasets. For all datasets and algorithms, the reported results are averaged over 10 runs using 10 different random permutations of documents order.

4.2 Benchmark algorithms

We compare the performance of our algorithms in terms of macro-averaged F1 [24] to the performance of several stateof-the-art online learning algorithms. These include, the wellknown Perceptron algorithm [17; 10], the Passive-Aggressive (PA) algorithm [5], and a multi-class version of the recently proposed AROW algorithm [6; 7]. For all three algorithms we reduced multi-class multi-label learning into a binary update by comparing the highest-scoring negative label with the lowest-scoring positive label. For multi-class problems for the Perceptron algorithm, this is often called Kesler's construction [19]. We denote these algorithms via Per, PA, and AR, respectively. Several recent works have demonstrated the high performance of these methods over various online text classification tasks [9; 7]. For each algorithm we tested two variants - one using the current linear model for the next prediction, and another one using the average of all previous models, which may help in averaging out noise [10]. This latter option is denoted with a suffix Avg in Section 5. In a pilot study we tried to normalize the counts vector representing each document under the L2-norm and found it has no significant impact on the quality of the results, hence we used the raw counts as input in the reported results. In addition, for the PA and the AR algorithms we first optimally tuned the algorithm's trade-off parameter to guarantee high performance of these algorithms. In the medium-size datasets this tuning was done using half of the documents along with their labels. In the large datasets it was done using 10,000 randomly selected documents along with their labels. Obviously, this tuning implies that these benchmark algorithms were using additional valuable information that may be hard to obtain in practice. Finally, to gain some perspective regarding the effectiveness of our active-learning variant, oAcMaxI, we implemented an uncertainty-sampling option [14] for each of the benchmark algorithms, in the spirit of [2], as explained below.

5 Experimental Results

5.1 Online learning results

In Table 1 we present the macro-averaged F1 results for all the examined online algorithms. Evidently, oMaxI was superior to the benchmark algorithms in three datasets, and inferior in two datasets - Reuters and gov, especially with respect to the AR algorithm. However, while for oMaxI we have relatively robust performance over all datasets examined, for the AR algorithm we have very low performance over the RCV1 data, due to its low recall results, presumably since these data are highly multi-labeled. In contrast, oMaxI performs well even on these data, although by construction it classifies each document to a single class. Thus, we conclude that the proposed oMaxI algorithm may at the least be considered comparable to the benchmark state-of-the-art algorithms we examined. In addition, it is important to bear in mind that the performance of the PA and AR algorithms rely on tuning their trade-off parameter, using many labeled documents. In fact, preliminary results of these algorithms with no tuning were substantially inferior. In contrast, the oMaxI algorithm requires no tuning, which is a practically important advantage.

5.2 Prediction Accuracy vs. Prediction Uncertainty

We considered the relation between our uncertainty score definition and the associated classification accuracy. To that end, we estimated u(xj) per document using Eq. 12 during the runs of the oMaxI algorithm. Next, we divided all documents in each run into 10 equally populated groups according to their u(xj) scores, and estimated the macro-averaged precision and recall [24] obtained within each group. In Fig. 3 we present these results for the gov data. Similar results were obtained for the other datasets. As depicted in the figure, as the median uncertainty score found in each group is decreasing, the associated precision and recall are increasing, supporting the validity of Eq. 12 as a strategy to estimate prediction uncertainty.

5.3 Results in Abstain mode

In the oAbMaxI algorithm a document is classified to a spurious "abstain" class if and only if u(xj) > u∗ where u∗ is a pre-specified threshold. We experimented with this algorithm over the three medium-size datasets with u∗ = 0.001, and over the two large datasets with u∗ = 0.0001. In Table 2 we present the obtained macro-averaged precision and recall [24]. As expected, the results of this algorithm are typically higher in terms of precision, while lower in terms of recall. If we estimate the precision and recall without considering the documents assigned to the "abstain" class, this tendency is even more dominant, as evident in the row entitled oAbMaxI ∗ . In addition, in light of the results depicted in Fig. 3 we conclude that the single input parameter, u∗ , may be used as a knob to control precision/recall trade-off.

5.4 Results in Active Learning mode

In the oAcMaxI algorithm the true label is requested if and only if u(xj) > u∗ where u∗ is again a pre-specified threshold. For comparison, we implemented an uncertaintysampling variant [14] for each of the benchmark algorithms, based on the technique proposed in [2]. Specifically, given an incoming document the algorithm requests the true label with probability b/(b +Δ), where Δ is the difference between the highest- and the second-highest prediction score and b > 0 is a pre-specified parameter controlling the number of requested labels. The learning model is then updated sequentially only with respect to documents for which the true label was obtained. For the oAcMaxI algorithm we used u∗ = 0.001

for the three medium-size datasets, and u∗ = 0.0001 for the two large datasets. For each of the benchmark algorithms we tried b = 0.001, 0.01, 0.1, 1.0, 10.0, 50.0, 100.0 in each dataset and we report the results for the b value for which the obtained training set size was roughly the same to that used by the oAcMaxI algorithm.

In Table 3 we present the obtained macro-averaged F1. In parenthesis we report the fraction of documents for which the true label was requested. For comparison, we repeat the results of the oMaxI algorithm that requests the true label after each prediction. First, we notice that the F1 results of the oAcMaxI algorithm are approximately the same as those obtained by the oMaxI algorithm that requests the true label after each prediction. The most extreme example is for the RCV1 corpus in which selectively asking for < 4% of the labels is sufficient for the oAcMaxI algorithm to performwell. In contrast, for the benchmark algorithms we see a more significant reduction in F1 as selective sampling is employed; e.g., in the subRCV1 data for the ARAvg algorithm - mainly due to reduction in precision; or in the 20NG data for the PA and AR algorithms, mainly due to reduction in recall. To further examine the effectiveness of the oAcMaxI algorithm we made an additional run over the RCV1 data while setting a more stringent uncertainty threshold of u∗ = 0.001. Correspondingly, the algorithm requested the true label for < 1% of the documents, but nonetheless obtained macro-averaged precision and recall of 72 and 37, respectively (F1=49). Remarakabely, these results are still clearly superior to the results of all the benchmark online algorithms over these data, although these algorithms requested and exploited the true label after each and every prediction. Finally, from a practical perspective, one obviously can correct classification errors once the true label is revealed. Hence, it is meaningful to estimate the precision and recall only for documents for which the true label was not requested. These results are presented in the row entitled oAcMaxI ∗ . As expected, we see that F1 performance are improved in this mode. In other words, we obtain higher classification accuracy for documents for which our algorithm estimated its prediction as relatively certain.

6 Discussion

We presented a classification scheme which is based on a simple principle of assigning the test set with labels so to maximize the information in the obtained co-occurrence matrix of features vs. labels. We further described a simple heuristic to estimate the uncertainty associated with each prediction and outlined three concrete algorithms. A classical online classification algorithm; an algorithm that abstains highly uncertain predictions; and an active-learning algorithm that requests the true label if and only if the prediction is considered relatively uncertain. Our experimental results suggest that the proposed algorithms are comparable or superior to state-of-the-art online classification methods.

The current work is inspired by the Information Bottleneck (IB) method [23; 22] and in particular by the sequential IB algorithm [21]. Here, we expand this earlier work in three dimensions. We show that the notion of information maximization can be exploited for supervised classification. We derive the probabilistic framework and update rules that allow utilizing these ideas in the context of online learning. And finally, we propose a simple strategy to estimate prediction uncertainty and demonstrate its utility in abstaining uncertain predictions and within the active-learning paradigm.

It seems worth pursuing the performance of our approach in batch mode, where the algorithm can continue to cycle over the instances while aiming to improve classification accuracy. In addition, the definition of our prediction uncertainty score, in Eq. 12, calls for a more rigorous understanding, as we intend to investigate in future research.

Acknowledgments

The authors thank Shai Fine for insightful discussions. This research was supported in part by the Israeli Science Foundation grant ISF-1567/10. KC is a Horev Fellow, supported by the Taub Foundations.