Early Active Learning via Robust Representation and Structured Sparsity

1 Introduction

In many machine learning tasks, data and label collections are time-consuming and costly. Thus, it is desired to find ways to minimize the number of data points to be labeled, i.e. carefully select the data points that should be labeled by users. Recent research on active learning has been reasonably successful in handling the problem of selecting examples to be labeled. Typically, the active learning algorithms choose which data points should be labeled and added to the training set. In other words, a learner begins with a small set of labeled data, selects a few informative data from the unlabeled data, and queries for labels from an oracle. The goal is to reduce the total labeling cost incurred to train an accurate supervised learning model.

∗Corresponding Author. This work was partially supported by NSF CCF-0830780, CCF-0917274, DMS-0915228, IIS-1117965.

In most cases, the active learning methods build upon notions of uncertainty in classification. For example, the informative data points that are most likely to be misclassified should be considered to be the most informative and will be selected for supervision; on the other hand, the representative data points that capture the most important natural properties of data points (e.g. manifold, clustering structures, etc.) should also be selected. Starting from these two different statistical uncertainty point of views, the existing active learning approaches can be categorized into two groups. The first group methods query the most informative data points, such as uncertainty sampling [Lewis and Catlett, 1994; Balcan et al., 2007], query by committee [Seung et al., 1992; Freund et al., 1997], and optimal experimental design [Lindley, 1956; Flaherty et al., 2005]. The other group methods target to select the data points with representative information, such as transductive experimental design [Yu et al., 2006] and clustering based method [Nguyen and Smeulders, 2004; Nie et al., 2012].

The active learning algorithms in both categories solve the experimental design problem at different stages. The first category methods prefer to choosing the uncertain or hard to be predicted data, but need determine them by a large number of labeled samples to avoid the samples bias. Thus, such methods should be used during the mid-stage of experiments, i.e. after enough labeled samples are collected. At the early stage of experiments, because we have a small number (or even none) of labeled data, the representative data points are desired to be selected for supervision.

In this paper, we focus on the early active learning strategies, i.e. solving the early stage experimental design problem. The Transductive Experimental Design (TED) method was proposed to select the data points via a least square loss function and ridge regularization [Yu et al., 2006]. However, the TED objective leads to an NP-hard problem, and was approximated by a sequential optimization problem with slow greedy algorithm [Yu et al., 2006]. Meanwhile, the least square loss function used in TED objective is sensitive to data outliers, thus the TED method is not suitable for the realworld applications with large noise.

To solve these two deficiencies, we propose a novel robust active learning approach using the structured sparsityinducing norms to relax the NP-hard objective to the convex formulation. A new robust active learning loss function is introduced to selected the representative data insensitive to the effect of outliers. The structured sparse regularization is utilized to select the representative data points that have nonzero weights during the sparse representations of different data (the non-representative data points typically have small weights or even zero, when they are used to represent other samples). A new optimization method is derived to solve our non-smooth objective with efficient procedure. Our algorithm has the closed form solution in each iteration with proved global convergence. Compared to previous greedy algorithm [Yu et al., 2006], our new optimization method is much more efficient. We evaluate our method using several benchmark data sets. All experimental results show our method outperforms other state-of-the-art active learning methods.

Notations. In this paper, matrices are written as boldface uppercase letters and vectors are written as boldface lowercase letters. Given a matrix M = {mij}, we denote its i-th row, j-th column as mi , mj . The ℓ2-norm of a vector v is defined as ||v||2 = √vT v. The ℓ2,1-norm of a matrix is defined as ‖M‖2,1 = ∑ni=1 √∑mj=1 m2ij = ∑ni=1 ∥∥mi∥∥2 . For consistency, the quasi-norm ℓ2,0-norm of a matrix M is defined as the number of the nonzero rows of M.

2 Active Learning via Structured Sparsity-Inducing Norms

Given unlabeled data X = [x1, x2, · · · , xn] ∈ Rd×n , the task of active learning is to select m (m < n) samples for labeling by user, such that the potential performance is maximized when trainingwith the fixedmlabeled samples. In early stage experimental design, the early active learning methods usually select the representative data points to maximize the efficiency of training process. Such a problem can be formulated as the Transductive Experimental Design (TED) problem [Yu et al., 2006] to solve:

The key idea of TED is to select the samples that can best represent the whole data using a linear representation. Therefore, the selected samples can be considered to be the most representative and informative data points since the other data points are highly linearly related to the selected samples.

However, Eq. (1) leads to a difficult combinatorial optimization problem (NP-hard). Thus, the TED problem was approximated by a sequential optimization problem and solved by an inefficient greedy optimization approach. On the other hand, the TED objective minimizes the least square error, hence it is sensitive to the data outliers. To solve these two deficiencies, we formulate the early active learning problem using the structured sparsity-inducing norms and propose a new robust formulation with efficient optimization algorithm.

Using the ℓ2,0-norm, we formulate the problem in Eq. (1) as:

We propose a more concise objective as following:

However, solving this problem is NP-hard because of the ℓ2,0norm. Recent theoretical progress shows that ‖A‖2,1 is the minimum convex hull of ‖A‖2,0 , and when A is row-sparse enough, one can always minimize ‖A‖2,1 to obtain the same result of minimizing ‖A‖2,0 . Therefore, Eq. (3) can be relaxed to the following convex optimization problem 1 :

The first term in Eq. (4) is the loss of the representation, and the second term in Eq. (4) is the ℓ2,1-norm regularization on A to obtain row-sparse solution of A. The loss used in Eq. (4) is a squared loss, which is very sensitive to data outliers, thus we propose to solve the following problem:

which can be written into a matrix format:

In our new objective, where the ℓ2,1-norm is applied to the loss function, the ℓ1-norm is imposed among data points and the ℓ2-norm is used for features. As a result, the effects of data outliers are reduced and the robustness of active learning is improved.

After obtaining the optimal A in Eq. (6), we can sort the rows of A by the row-sum values of the absolute A in the decreasing order. Therefore, the active learning task can be performed by selecting the m samples corresponding to the top m rows of A. As the proposed active learning method is based on robust representation and structured sparsity, we call our active learning method as RRSS for short.

3 Optimization Algorithm and Analysis

Although the problem (6) is convex, it is difficult to be solved since two non-smooth terms are involved. In this section, we will derive an efficient algorithm to solve the problem (6), and give a theoretical analysis to show that the algorithm will converge to the globally optimal solution.

3.1 AlgorithmDerivation

Taking the derivative of Eq. (6) w.r.t A, and setting the derivative to zero, we have 2 :

1 Recently, we observed an equivalent formulation of Eq.(4) in [Yu et al., 2008] with different motivation.

2 When xi - Xai = 0, we can regularize uii as uii = 1 2√‖xi-Xai‖22+ς . Similarly, when ai = 0, vii =

1 2√‖ai ‖22+ς . Then the derived algorithm can be proved to minimize

where U is a diagonal matrix with the i-th diagonal element as uii = 1 2‖xi-Xai‖2 , and V is a diagonal matrix with the i-th diagonal element as vii = 1 2‖ai ‖2 . Then for each i(1 ≤ i ≤ n), we have

and then ai can be calculated by

Note that U and V both are dependent on A and thus is also unknown variables, we propose an iterative algorithm to solve this problem. The detailed algorithm is described in Algorithm 1. In the following, we will prove that the algorithm will converge to the global optimal solution to the problem (6).

Input: The data matrix X ∈ Rd×n .

Initialize A ∈ Rn×n ;

while not converge do

1. Calculate the diagonal matrix U, where the i-th diagonal element of U is uii = 1 2‖xi-Xai‖2 . Calculate the diagonal matrix V, where the i-th diagonal element of V is vii = 1 2‖ai ‖2 . ; 2. For each i(1 ≤ i ≤ n), update ai by ai = uii(uiiXT X +γV)-1XT xi ; end Output: The matrix A ∈ Rn×n .

Algorithm 1: The algorithm to solve the problem (6).

3.2 AlgorithmConvergence Analysis

First, we introduce a lemma as follows:

Lemma 1 ([Nie et al., 2010]) For any vectors ˜a and a, we

Next, we prove the convergence of our algorithm in the following theorem:

Theorem 1 Algorithm 1 decreases the objective value in each iteration.

Proof: Suppose the updated A is ˜A. According to the step 2 in Algorithm 1, we know that

Thus we have

According to the definitions of U and V, we have

According to the Lemma 1, we have the following two inequalities:

Summing Eq. (11)-(13) in the two sides, we arrive at

Therefore, the algorithm decreases the objective value in each iteration. □

Denote f(M) = T r((X - XM)U(X - XM)T ) + γTr(MT VM). In the convergence, we know f( ˜A) = f(A). Note that ˜A = argmaxMf(M), thus A = argmaxMf(M). Note that ∂f(A) ∂A = 0 is exactly the Eq. (7), thus A, U and V will satisfy the Eq. (7) in the convergence. As the problem (6) is a convex problem, satisfying the Eq. (7) indicates that A is a global optimum solution to the problem (6). Therefore, the Algorithm 1 will converge to the global optimum of the problem (6). Because we have closed form solution in each iteration, our algorithm converges very fast.

4 Kernel Extension

The proposed method in the previous section can be easily extended to the kernel version for active learning or we can simply use a general kernelization framework [Zhang et al., 2010] to achieve the kernel version. Let φ : Rd → H be a kernel mapping from the original space to the kernel space, where H is a reproducing Kernel Hilbert Space (RKHS) induced by a kernel function K(x, z) = φ(x)T φ(z). Then φ(X) = [φ(x1), φ(x2), ..., φ(xn)], and the problem (6) in the kernel space becomes:

Given the data matrix X = [x1, x2, · · · , xn] ∈ Rd×n , we denote the kernel matrix by K ∈ Rn×n , where the (i, j)-th element of K is kij = φ(xi)T φ(xj). The algorithm to solve the problem (15) is very similar to the Algorithm 1, and the detailed algorithm is described in Algorithm 2.

5 Experimental Results

We empirically evaluate the proposed RRSS method, as well as its kernelized version, K-RRSS method. We first demonstrate the effectiveness of the proposed methods on a challenging synthetic data set. Then we study their performances in both single-label and multi-label classification tasks.

5.1 Experiment on AChallenging Synthetic Data

We first give an experimental result on a challenging synthetic data to validate the effectiveness of the proposed active learning algorithm. The synthetic data are generated from six subspaces of the original 500-dimension space. The dimensions of the six subspaces are 10, 12, 14, 16, 18, 20, respectively. The numbers of data generated from the six subspaces are 25, 30, 35, 40, 45, 50, respectively, which are relatively small to the dimensions. Furthermore, we add noise of 20% perturbation on the generated subspaces data. Thus the 500dimensional data are distributed on six subspaces with different dimensions, different numbers and high noises. Separating such a high dimensional, high noised and small sampled data from the six subspaces is a very challenging task, which can be seen from the 10-nearest-neighbor similarity graph of the data in Figure 1(a). The cluster structure is obscure and can not be discerned from the similarity graph on the original data. Figure 1(b) shows the learned matrix A in Eq. (6) by Algorithm 1, and Figure 1(c) shows the selected top 20 rows of A, the numbers of the selected samples from the six subspaces are 1, 2, 3, 3, 4, 7. The result clearly indicates the effectiveness of the proposed active learning algorithm.

5.2 Improved Single-Label Classification

We evaluate the proposed methods in single-label classification tasks, in which each data point belongs to one and only one class. We experiment with the following four broadly used single-label data sets: Yale face image data [Georghiades et al., 2001], USPS, BinAlpha [Belhumeur et al., 1997], and Coil20 [Nene et al., 1996].

Yale face database contains 165 grayscale images in GIF format of 15 individuals. There are 11 images per subject, one per different facial expression or configuration.

USPS database is a handwritten digit database. We randomly pick up 2000 images, 200 for each digit, from the database for our experiments.

BinAlpha data set contains 26 binary hand-written alphabets and we randomly select 30 images for every alphabet.

Coil20 database contains 20 objects. The images of each objects were taken 5 degrees apart as the object is rotated on a turntable and each object has 72 images. The size of each image is 32 × 32 pixels, with 256 grey levels per pixel.

Experimental setups. We conduct our experiments as following. For each data set, we first randomly select 50% of the data points as candidate samples for training, from which we employ the compared active learning methods to select a certain number of samples to request human labeling. Using the selected samples and their queried labels as training data, we learn a classification model, by which we classify the other 50% data points. The latter is considered as test data. We repeat every test case for 50 times and report the average classification performances.

We compare our methods against the following two baseline methods including: (1) random sample selection method that randomly selects data points from a given data set to query labels; (2) K-means sample selection method, where we perform K-means clustering and select the data points that are most close to the K centroids. The former is equivalent to traditional passive learning, while the latter is to seek the most representative samples of a data set. We also compare our method against two related active learning methods including (3) transductive experimental design (TED) method [Yu et al., 2006] and (4) QUIRE method [Huang et al., 2010]. The former is closely related to our method, and the latter is a very recent method that has demonstrated state-of-the-art performance.

We construct a Gaussian kernel from the candidate data points of each data set, i.e., K(xi, xj) = exp (-α‖xi -xj‖2), as input for TED method, QUIRE method, and the proposed K-RRSS method. Prior to experiments, for each data set we use support vector machine (SVM) (linear kernel) to seek the optimal parameter α of the Gaussian kernel and the optimal tradeoff parameter of the three methods via a standard 5-fold cross-validation using the candidate data in the range of {10-5 , . . . , 1, . . . , 105}, where we select 50% of the training data of each of the 5 trails to learn the SVM classifier.

We learn SVM and transductive SVM [Joachims, 1999] classifiers, by which we classify the test data points. The former is one of the most widely used supervised single-label classification method, while the latter is an established semisupervised method extended from the former. Again, Gaussian kernel is used, where we set C = 1 and use the fine tuned γ in the sample selection process.

Experimental results. The classification accuracies by SVMs trained with different amount of samples selected by the compared methods for each of the four data sets are shown in Figure 2. A first glance at the results shows that the proposed methods consistently outperform the compared methods, sometimes very significantly, which demonstrate their effectiveness in selecting useful training samples in singlelabel classification. By a more careful observation, we can see that the proposed K-RRSS method is always better than its counterpart using vector input (equivalent to using linear kernel), i.e., RRSS method, which is consistent with their mathematical formulations in that kernel could make the data more discriminative in the mapped feature spaces. Moreover, the performance curves of the two proposed methods climb to saturation in a much faster way than the compared methods. That is, when the number selected samples is small, our methods are more effective in selecting the most useful data points to train an classifier with high accuracy. Because human annotation is often expensive in real world applications, this adds to the practical value of the proposed methods. Finally, the performances of the active learning methods including ours are generally superior to the passive learning method that randomly selects samples for label query, which confirms the values of active learning.

Table 1 show the classification results using transductive SVMs trained with the top 10% selected samples by the compared methods on each data set. We conduct this experiment because semi-supervised learning is another way to improve the classification performance by exploiting unlabeled data, which could work with active learning and reinforce each other. Again, our methods demonstrate better performances, which confirms their effectiveness from another perspective.

5.3 ImprovedMulti-Label Classification

Now we evaluate the proposed approach in multi-label classification tasks, in which one single data point could be associated with more than one class label. Multi-label classification is more general, though more challenging, than single-label classification, therefore it is more close to real world applications. One of the most successful application of multi-label classification is image annotation, because one picture usually contains more than one object of interest. We evaluate the proposed methods on the following three multi-label benchmark image data sets: TRECVID 2005, MSRC, and PASCAL VOC 2010.

TRECVID 2005 data set contains 137 broadcast videos (74523 sub-shot) from 13 different programs. Following previous work [Wang et al., 2009], we randomly sample the data such that each concept has at least 100 images.

MSRC data set contains 591 images with 23 classes. Around 80% of the images are annotated with at least one classes and around three classes per images on average.

PASCAL VOC 2010 data set [Everingham et al., ] contains 13321 images with 20 classes. We randomly select images, such that at least 100 images are selected for each class, which leads to 1864 images used in our experiments.

Following prior computer vision studies, for these three image data sets, we divide each image into 64 blocks by a 8 × 8 grid and compute the first and second moments (mean and variance) of each color band to obtain a 384-dimensional vector as features.

Experimental setups. We follow the same experimental setups as in single label classification, i.e., we randomly split a data set into two parts with equal size, and use one half as candidate pool and the other as test data. We still use the six compared methods as before to select images with the same settings. Upon the top 20% selected images and their queried labels, we classify the test images using the multi-label kNearest Neighbor (Mk-NN) method [Zhang and Zhou, 2007], which is a lazy learning method without a training process.

Multi-label classification is more complicated than singlelabel classification, therefore it requires more metrics to evaluate the classification performance. We employ the following five widely used multi-label performance metrics to assess the classification results: Hamming loss, one-error, coverage, rank loss and average precision. We refer readers to [Zhang and Zhou, 2007] for detailed definitions of these performance metrics. For the first four metrics, the smaller is better (denoted as ↓ in Table 2); while for the last one, the bigger is better (denoted as ↑ in Table 2).

Experimental results. The average classification performances on the three multi-label image data sets over 50 repeats are reported in Table 2. The results show that the proposed methods are again better than the compared methods, which demonstrate the effectiveness of our methods in selecting training images for multi-label data.

We further examine the average number of labels associated with the selected training images by the compared methods, which are listed in Table 3. Compared to the average numbers of labels associated with the images in the original data sets, the randomly selected images have about the same numbers of labels as the original data, while the images selected by the active learning methods, including ours, have greater average label numbers than the original data. Because the more labels a data point associated with in multi-label settings, the more information it conveys [Wang et al., 2010], the results in Table 2 provide a concrete evidence that sample selection by active learning methods do improve the informativeness of the data. Because the average number of labels associated with the selected training images by our K-RRSS

method is greatest, it is the most effective method in selecting content rich images for multi-label image classification.

6 Conclusion

In this paper, we proposed a novel active learning method to solve the early stage experimental design problem. Instead of using the traditional least square loss function, we introduce the robust sparse representation based active learning loss function. As a result, the data points selected by our method are insensitive to the outliers. The l2,1-norm based structured sparse regularization is utilized to select the most representative data points that have large weights in the sparse representations of other data points. We performed the empirical studies on both single-label and multi-label classification tasks. In all experimental results, our new approach outperforms other related active learning methods.