Distribution-Aware Online Classifiers

1 Introduction

In tasks that require huge number of real-time classifiers, online learning is the only viable option. For example, realtime classification of status/micro-blog updates of millions of social network users requires a personalized online classifier to be maintained for every user [Li et al., 2010]. An online learning algorithm updates its decision boundary incrementally after processing each sample. Given a sample, it will first classify it, so called making a prediction. The quantitative difference in the prediction and true label is computed as the loss, which is then used to adjust the classifier weights. The goal is to maximize the correctness of future predictions.

The classical Perceptron [Block, 1962; Novikoff, 1962], Second-order Perceptron (SOP) [Cesa-Bianchi et al., 2005], suite of Passive-Aggressive (PA) algorithms [Crammer et al., 2006] and its second order variants Confidence-Weighted (CW) learning [Dredze et al., 2008] and Adaptive Regularization Of Weight vectors (AROW) [Crammer et al., 2009b], all belong to the same family of online algorithms, which perform well for a variety of real-time applications. However, except for the Second-order Perceptron, these online learning algorithms do not explicitly account for the distribution of the data [Cesa-Bianchi et al., 2005]. PA algorithms that use the squared Euclidean distance work well for data with spherical distributions. However, for hyper-ellipsoidal data distributions, performance can be poor. In fact, PA assumes data to be spherically distribution. To overcome this deficiency, we propose using the Mahalanobis distance measure in place of the Euclidean distance in PA, and call the new approach the Passive Aggressive Mahalanobis (PAM) algorithm. PAM update equations bear a close resemblance to that of the CW, which took a different route by assuming that the weights are normally distributed with a mean vector and covariance matrix. However, PAM is different from CW in its update criterion. CW minimizes the differences between the new and old weight distribution whereas PAM simply maintains the original PA goal by minimizing the weight vector differences adjusted by the weight covariance.

2 RelatedWork

Online linear classification algorithms have been studied for close to 50 years, starting with the Perceptron [Block, 1962; Novikoff, 1962]. Recently, there has been a renewed interest in Perceptron-like algorithms such as the Secondorder Perceptron [Cesa-Bianchi et al., 2005] and the PassiveAggressive (PA) algorithm [Crammer et al., 2006], with the latter incorporating the margin maximizing criterion of modern machine learning algorithms. Algorithms that improved upon the PA algorithm include the Confidence-Weighted (CW) linear classification [Dredze et al., 2008] and its latest version, the CW algorithm for multi-class classification [Crammer et al., 2009a]. CW assumes that the weight at each time step is Gaussian distributed with a mean vector and covariance matrix. As such, the weight vector is updated by minimizing the Kullback-Leibler divergence between the new and old weight distributions.

There is also a related class of Bandit algorithms [Kakade et al., 2008], whose learning process is similar to the Perceptron algorithm. However, in the prediction phase, the Bandit algorithm does not know the true label of the instance. The Bandit algorithm is actually more realistic with respect to real-world online tasks like micro-blog classification, since in practice the real class label is not known after each prediction unless the user constantly validates every prediction.

Other online learning algorithms use the Newton weight update method, including the LaRank and the OLaRank algorithms [Bordes et al., 2007; 2008]. Some are inspired by support vector machines [Cortes and Vapnik, 1995] and the Huller algorithm [Bordes and Bottou, 2005].

3 Passive-AggressiveMahalanobis

The online binary classification framework in this section follows the PA algorithm formulation [Crammer et al., 2006].

3.1 Online Learning

Online learning operates on a sequence of data with time stamps. At time step t, the algorithm process an example xt ∈ Rn by first predicting its label ˆ yt ∈ {-1,+1}. After prediction, it computes the loss ℓ(yt, ˆ yt) which is the difference between its prediction and the revealed true label yt ∈ {-1,+1}. The loss is then used to update the weight with respect to some criterion. The goal is to achieve a margin of at least 1. So on a certain round if the margin is less than 1, the algorithm suffers a loss. The loss can be modeled using the hinge-loss function, which equals to zero when the margin exceeds 1, as shown below.

Passive Aggressive Algorithms

The overall objective of online learning is to minimize the cumulative loss over the entire sequence of examples. Crammer [Crammer et al., 2006] formulated it as an optimization problem and derived three versions of the PA algorithms as follows. First, the optimization problem is formulated as follows.

Crammer updates the weight vector wt+1 at each round as

Second, to allow for incorrect predictions, a slack variable ξ was introduced into the optimization problem (2) with two penalties; linear and quadratic. The weight update equation to the soft-margin problem has the same form as that of (3), but with the weight coefficient τt defined as follows.

The three flavors were named PA, PA-I, and PA-II respectively.

Confidence Weighted Learning

Using a probabilistic approach, the confidence-weighted (CW) online learning algorithm learns a Gaussian distribution of weights with mean vector μ and covariance matrix Σ. The weight distribution is updated by minimizing the KullbackLeibler divergence between the new weight distribution and the old one while ensuring that the probability of correct classification is greater than a threshold as follows.

where Pr denote the point probability. This optimization problem has a closed form solution:

where αt = -(1+2φMt)+√(1+2φMt)2-8φ(Mt-φVt) 4φVt , βt = 2αtφ 1+2αtφVt , Vt = xTt Σtxt, Mt = yt(μt · xt), and φ is a confidence parameter depending on η.

3.2 HardMargin PAM

PAM is similar to PA, except for its use of the Mahalanobis distance measure in place of the Euclidean distance measure. The new optimization problem is defined as follows.

where Σt-1 is the covariance matrix of the weight vector distribution at round t1. Solving the above problem, we have,

Finally, we obtain the hard margin Mahalanobis PassiveAggressive (PAM) algorithm as shown in Algorithm 1.

3.3 Soft Margin PAM

Extending PAM to deal with misclassified samples, we introduce the slack variable ξ as follows.

where C is the positive aggressiveness constant, which controls the aggressiveness of each update step. The bigger the C, the larger the update. We thus have the following solution.

By defining a different objective function that changes quadratically with the slack variable ξ, we have the following optimization problem.

Solving the above problem, we have the following result.

Algorithm 1 Passive-Aggressive Mahalanobis (PAM)

Input:

C = positive aggressiveness parameter

Output:

None

Process:

• 1: Initialize Σ0 ← I; w1 ← 0;
• 2: for t = 1, 2, . . . do
• 3: Receive instance xt ∈ Rn
• 4: Predict ˆ yt = sign(wt · xt)

• 7: if ℓt > 0 then

10: end if

• 11: end for

The two updates are named PAM-I and PAM-II, respectively. Both share the same general form wt+1 = wt + τtytΣt-1xt, with a different update step as follows.

and

3.4 Covariance Matrix Estimation

We describe a way to approximate the covariance matrix Σ over the weight vector w. Consider the evolution of the objective function starting at t = 0 and Σ0 = I. At round T , we have the loss function 1 -yTwT ·xT wherewT is the weight vector at round T . Denoting y as a vector [y1, y2, . . . , yT ] and X = [x1x2 . . . xT ] as a matrix of column input vectors. We can write the PAM weight update as,

Multiplying the above equality by XT , we have,

Multiplying the above equality by (XT X)-1 , we have,

Assuming an i.i.d. noise model, we can write y = Xw + e, where e is an error vector. Substituting y into the above equality, we have,

The covariance matrix of wT has the form,

or

Since, the PAM weights are updated to achieve a margin of at least 1, we can assume that E[eeT ] = σ2 I. The covariance matrix can be approximated as follows.

Following the work of [Cesa-Bianchi et al., 2005], we can write,

Applying the Sherman-Morrison formula to (9), we have,

From Equation (9), we can conclude that Σ-1 t ⪰ Σ-1 t-1 and Σt ⪯ Σt-1. Like the PA family, all three PAM algorithms share the same weight update equation, differing only in the update rate τt, as shown in Algorithm 1. In fact, the PAMII weight update resembles that of Adaptive Weight Regularization [Crammer et al., 2009b] (AROW). The difference between PAM-II and AROW is that PAM-II does not explicitly regulate the update of the covariance matrix Σt. PAM was primarily motivated by adding a data noise model to PA, while AROW and CW started out by assuming a distribution of weights. The end results are very similar, differing only in the update rates.

Ma et al. [Ma et al., 2010] examined in depth several strategies to estimate the covariance matrix efficiently, along with their practical implications specifically for CW, but which can be used for any second-order learning algorithms, including PAM. In this paper, we will not focus on the practical issue of computing the covariance, but instead measure the classification performances of both CW and PAM assuming that a full covariance matrix is available and feasible.

3.5 PAMError Analysis

In this section we provide several theoretical results for PAM, omitting the proofs due to lack of space.

Theorem 1 (Relative Loss Bound) Given a sequence of M examples [(x1, y1), . . . , (xM, yM)], any weight vector u ∈ Rn, and loss ℓ∗t = 0 for all t, the cumulative relative loss of PAM is upper bounded by

where U is the set of indices for examples leading to the weight updates andXUXTU = ∑t∈U xtxTt .

Theorem 2 (PAM-I Mistake Bound) Given a sequence of examples [(x1, y1), . . . , (xM, yM)] and any weight vector u ∈ Rn, the number of mistakes made by PAM-I is upper bounded by

where C is a positive aggressiveness parameter.

Theorem 3 (PAM-II Loss Bound) Given a sequence of examples [(x1, y1), . . . , (xM, yM)] and any weight vector u ∈ Rn, the cumulative relative loss of PAM-II is upper bounded by

In [Crammer et al., 2006], the squared upper loss bound of the PA algorithm was defined as ‖u‖2 (max |x|)2 . This bound depends only on the norm of weight vector u. It does not consider the input data distribution while the upper bound of the PAM algorithm depends on both the norm of u and uT XUXTU u, the data spectral term. We know that the second term is finite and bounded by the maximal eigenvalues of the matrix XUXTU . Another term in the loss bound of the PAM-I and the PAM-II algorithms is xTt Σtxt, which is a trade-off factor between the hinge-loss term and the data spectral term. In CW learning, the matrix Σt is called the confidence, which decreases monotonically with observed data. We also have Σ0 = I therefore we always have xTt Σtxt ≤ xTt xt, which causes the data spectral term to increase with the hinge-loss quantity. However, it is very difficult to compare the upper loss bounds of the two families because both depends on the input distribution.

4 Performance Evaluation

A total of 8 datasets were used including two binary classification datasets (CRX and BUPA datasets from UCI [Asuncion and Newman, 2007]), two binary web datasets (WebKB and Twitter Sentiment), and two multi-class datasets (USPS and MNIST). For the multi-class datasets, one random class out of C classes was selected as positive, and a negative class of equal size was generated by sampling (the same number of samples as the positive class) from the remaining C - 1 classes. Where applicable, all experiments were repeated 10 times with different randomizations, and the average results shown/plotted. Results on the twitter dataset was single-run, since the data are deterministically ordered and binary.

4.1 Cumulative Error Rate

We use the standard cumulative error rate, which is the ratio of mistakes over the total number of examples. To ensure a fair comparison of our proposed algorithms with the original Passive-Aggressive algorithms, we grid-searched the optimal aggressiveness parameter C in all PA-based algorithms. To be fair, we compare our PAM-I and PAM-II with the original PA-I and PA-II, respectively. We excluded the PA results as it performed worse than the PA-I and PA-II [Crammer et al., 2006]. For brevity, we only show the cumulative error rate comparisons between PA-II, PAM-II, and CW here.

The cumulative error rates on the two binary datasets are shown in Figure 1. For BUPA, all three algorithms started off with similar loss, but PAM-II starts to pull away from the pack after 60 examples, and consistently exhibit lower logmistake rate thereafter. For CRX, PAM-II leads after iteration 30, with an overall lower mistake rate thereafter.

Figure 2 shows the cumulative error rates on the two letter recognition datasets. PAM-II performed better right from the start, but not significantly better overall because the negative class in this case is heterogenous (formed by a uniform equalsized sample of the non-positive class);better results can be expected in a one-of classification.

The WebKB dataset contains 1051 web documents from two classes, each with two views. We tested all algorithms only on the textual view, with results shown in Figure 3. Again, PAM achieved consistently lower log-mistake rate, widening the gap with increasing number of examples.

4.2 Classification Accuracy

In practice, classification performance in terms of F-measure is typically more important than cumulative error rates. The positive (+) and negative (-) class F-measures for all 5 datasets are listed in Table 1 with the best results in bold. PAM-II consistently outperform other algorithms, including CW. Although, CW performed better than the original PA-I and PA-II, it still falls a little behind PAM. For BUPA, PAM-II is more than 2% better than CW. PAM-II achieved the largest winning margin against on CRX+, where it is more than 11% better than PA-II, and 2% better than CW. Overall, PAM-II beats CW only by a marginal 1-2%. Again, the positive class improvements over PA-II are significantly better because it is much more homogeneous compared to the artificially consolidated negative class.

4.3 OnlineMicroblog Data

To illustrate the utility of online algorithms, we apply them to learn emotions from real-life micro-blogs. The Twitter 1 sentiment dataset [Li et al., 2010] is a collection of micro-blogs (tweets) written by 6 users. Each tweet is manually labeled as emotional (positive) or non-emotional (negative). An online model was applied to each user's tweets in chronological sequence. Each model was initialized to some randomweights; after it classifies an incoming tweet, the tweet's true label is revealed to update the model weights, and the online classification/learning continues until the last tweet is predicted.

From the individual loss plots in Figure 4, PAM-II again consistently outperformed the other algorithms. However, the advantage of PAM-II depends very much on the dataset. For instance, for user DenyceLawton (c), PAM-II did significantly better than the others but for another user CarlaMedina (b), PAM-II performed only marginally better. On closer examination, we found that CarlaMedina writes equally frequently in Spanish and English. Since our human labeler is not Spanish literate, a large portion of the tweets have been labeled incorrectly. For example, Spanish emotions were not properly labeled, labeled emotional tweets contain a mix of Spanish and English with English terms acting as the decisive factor. As a result, the labeling for user CarlaMedina is very noisy. Another consequence of not knowing the language is the highly imbalanced class distribution, with user CarlaMedina having the smallest raw count of 250 positive (emotional) labeled samples. Specifically, users AudreyWalker, CarlaMedina, DenyceLawton, IheartBrooke, RealMichelleW, and SabrinaBryan have 15.5%, 19.4%, 41.6%, 18.9%, 17.0%, and 17.4% positive tweets respectively. For PAM-II, this means that the model would have very little chance to make a wrong prediction and significantly adjusting its weight; an occasional positive sample would cause the margin to be reduced. For such a case, PAM does not benefit much from considering the sample distribution, since the covariance matrix would account for a far smaller number of samples.

1 http://twitter.com

For CarlaMedina, PAM II started to decisively outperform CW only after around 250 samples, by when it should have seen approximately 50 (19.4% of 250) positive samples, assuming a uniform class distribution. For other marginal users like AudreyWalker (483 positive, PAM wins after 40 samples), RealmichelleW (495 positive, PAM wins after 100), and SabrinaBryan (551 positive, PAM wins after 200), who all have around 500 total raw positive tweets, their cumulative PAM loss rates were all able to pull away from the competitor earlier than CarlaMedina (342 positive, PAM wins after 250), simply because they have a larger number of positive tweets.

5 Conclusion

We proposed PAM, a generalization of the PassiveAggressive algorithms [Crammer et al., 2006] that takes into account the data spectral properties. PAM was evaluated on several datasets and found to consistently outperform other online algorithms, including its cousin Confidence Weighted (CW) learning. Results on online classification tasks have shown an average of 4% to 12% improvements in F1-measure. We have also validated the practicality and superiority of PAM on a real-world twitter emotion classification dataset.

Compared to PA, PAM runs slower because it needs to compute the covariance matrix, which scales quadratically with the number of features. To solve this problem, we can deploy the approximate version of the PAM algorithm by calculating the diagonal matrix in the same way as the CW algorithm [Dredze et al., 2008; Ma et al., 2010].

We are currently extending the PAM family of algorithms for multi-class and structural data problems. We are also refining the analytical error loss bounds of PAM, so as to stipulate the data conditions for which PAM will be decisively superior and vice-versa. For future work, we would also want to evaluate extensively the practical performances of AROW versus PAM-II, given their similarities in the weight update equations. In particular, we want to find out if the adaptive update of the covariance matrix in AROW is superior to PAM-II's static covariance update approach.

Acknowledgement

This research was supported in part by Singapore Ministry of Education's Academic Research Fund Tier 1 grant RG 30/09.