Diversifying Convex Transductive Experimental Design for Active Learning

1 Introduction

In many machine learning tasks, we need to collect the training data and manually annotate them by domain experts. This process is usually time consuming and expensive. Active learning [Settles, 2009] is a machine learning technique that selects the most informative samples for labeling and uses them as training data. It has been widely explored in the machine learning community for its capability of reducing human annotation effort.

Convex Transductive Experimental Design (CTED) [Yu et al., 2008] is one of the most representative active learning methods and has received increasing attention in recent years. It uses a data reconstruction framework to select informative samples for labeling, where the informativeness of each sample is measured by its capacity to reconstruct the target data set. Based on the data reconstruction framework, several methods were developed. [Zhen and Yeung, 2010] proposed supervised experimental design, which can leverage label information if it is available. [Nie et al., 2013; Zhu and Fan, 2015] employed robust loss functions to measure the reconstruction error to develop methods which are insensitive to outliers. [Cai and He, 2012] incorporated manifold structure into this framework via manifold adaptive kernels. [Hu et al., 2013] performed active learning via neighbourhood reconstruction to select samples by exploring the local data structure. These methods have achieved promising performance in text classification [Yu et al., 2008; Cai and He, 2012] and other multimedia data classification tasks [Nie et al., 2013; Hu et al., 2013; Zhu and Fan, 2015].

⇤Corresponding author

Observe that the data reconstruction framework assigns each sample a score, which indicates the sample's capacity to reconstruct the target data set, and all the samples are ranked based on these scores. Then the top ranked ones are selected for labeling. Similar samples may get similar ranking scores, because these similar ones have similar capacity for data reconstruction. As a result, the set of selected (i.e., top ranked) samples may well contain samples which are mutually similar. This is definitely undesired. Since the process of data labeling is usually time consuming and expensive, the budget for data labeling is always limited. To maximize our benefit, it is desired to select those informative samples containing complementary information, i.e., highly similar ones are excluded.

The above analysis motivates us to study the diversity problem with existing data reconstruction based active learning methods. In particular, we propose to enhance CTED with diversity mechanism by imposing a diversity regularizer over sample selection. The diversity regularizer makes use of a similarity matrix among samples to ensure that if two samples are informative but highly similar, only one of them gets a high ranking score. A main challenge in applying the diversity regularizer is to define a good similarity matrix. One direct way to obtain the similarity matrix is to pre-define it using the original data. Then it is fixed and used as an input to the diversity regularizer. If the pre-defined similarity matrix is not good, the effectiveness of the diversify regularizer will be limited. To obtain a reliable similarity matrix and seamlessly integrate diversity into CTED, we embed similarity matrix learning into CTED by leveraging a data representation extracted from the reconstruction matrix of CTED. As we will discuss later, this data representation reflects the role of each sample in the data reconstruction process. Therefore, similarity matrix built on this representation can well characterize the similarities among samples in terms of their capacity for reconstruction. The involvement of the diversity regularizer makes the obtained optimization problem hard to solve. We find an equivalent problem which is easier to optimize and derive an alternating minimization procedure to solve it. We perform extensive experiments on several benchmark data sets. Experimental results based on two classifiers all demonstrate that, with diversification, our method (i.e., Diversified CTED) significantly improves CTED and consistently outperforms the state-of-the-art methods in the literature.

2 RelatedWork

The goal of active learning is to label as little data as possible, to achieve a certain classification performance, therefore saving considerable annotation cost for training a good learner [Settles, 2009]. One representative active learning algorithm is to select samples with maximum uncertainty of labels measured by the distance from the classification boundary [Tong and Koller, 2002; Lewis and Catlett, 1994; Balcan et al., 2007; Yang et al., 2014]. Another popular approach is query by committee, where a number of distinct classifiers are generated and a sample having the most disagreement among these classifiers in predicting the label is selected for labeling [Freund et al., 1997; Seung et al., 1992]. When selecting samples, these methods need a pretrained classifier, which means they need some initially labeled data. Another line of research works aim to select samples in unsupervised setting. Clustering based active learning methods were proposed in [Nguyen and Smeulders, 2004; Nie et al., 2012]. [Chattopadhyay et al., 2012; 2013] proposed an active learning method based on Maximum Mean Discrepancy (MMD)[Borgwardt et al., 2006], with the goal of minimizing the difference in the marginal probability distribution between the selected samples and remaining ones. Data reconstruction based active learning methods, such as CTED [Yu et al., 2008] and ARSS [Zhu and Fan, 2015], are also typical methods in this category.

In this paper, our focus is on solving the diversity issue of the data reconstruction based active learning methods. Particularly, we solve this problem on the base of CTED and show that, with diversification, the sample selection power of CTED can be significantly improved. The developed techniques can also be used to other data reconstruction based active learning methods.

3 Preliminaries

We summarize the notations and the definition of norms used in this paper. Matrices are written as boldface uppercase letters and vectors are written as boldface lowercase letters. For an arbitrary matrix M, we denote its i-th row, j-th column and (i↪ j)-th entry as mi , mj and mij, respectively. The `p-norm of the vector v 2 Rn is defined as ♣♣v♣♣p = (Pni=1 ♣vi♣p ) 1p . The Frobenius norm of the matrix M 2 Rn⇥m is defined as ♣♣M♣♣F = qPni=1 Pmj=1 m2ij . MT is the transpose of M and Tr(M) is the trace of M. We use I to denote the identity matrix with proper size.

Denote X 2 Rd⇥n as an unlabeled data set, where xi 2 Rd⇥1 is the i-th sample. The goal of active learning is to select a subset Z 2 Rd⇥m (m < n) from X, such that the selected samples can improve the classifier the most if they are labeled and added to the training set. Since our work is based on Convex Transductive Experimental Design (CTED), we first review CTED in the next subsection.

3.1 Convex Transductive Experimental Design

Transductive Experimental Design (TED) [Yu et al., 2006] aims at selecting a subset Z 2 Rd⇥m from the original unlabeled data set X 2 Rd⇥n such that a function f trained on Z has the smallest predictive variance on a given testing set. The optimization problem of TED is

where ♣Z♣ = m means that Z contains m samples and θ is a tuning parameter. In order to solve the NP-hard optimization problem in Eq. (1), [Yu et al., 2006] proposed a sequential algorithm, which selects one sample each time. The obtained result is suboptimal [Yu et al., 2008]. To tackle this issue, Convex Transductive Experimental Design (CTED) was further proposed in [Yu et al., 2008]. The optimization problem of CTED is

where aij is the (i↪ j)-th entry of A, and γ is a nonnegative trade-off parameter. As shown in Eq. (2), CTED utilizes a data reconstruction framework to select informative samples for labeling. The matrix A contains reconstruction coefficients and b is the sample selection vector. The `1-norm makes b to be sparse. In this way, the values corresponding to less informative samples tend to be zero. Large value of bi indicates the i-th sample has a large impact on the reconstruction. After solving the optimization problem in (2), CTED ranks all samples based on bi(i = 1↪ 2↪ ▷▷▷↪ n) in descending order, and select the top ranked ones for labeling.

Under this data reconstruction framework, several methods have been proposed [Cai and He, 2012; Nie et al., 2013; Zhen and Yeung, 2010; Zhu and Fan, 2015; Hu et al., 2013]. For example, [Cai and He, 2012] incorporated manifold information into this framework. [Zhu and Fan, 2015] employed robust loss functions to measure reconstruction error to handle outliers in data. These methods have shown effectiveness in text classification and other multimedia data classification tasks. All these methods select informative samples via a same mechanism, i.e., assigning ranking scores to samples and selecting top ranked ones.

As discussed above, similar samples may get similar ranking scores, since these similar ones have similar capacity for reconstruction. As a result, the set of top ranked samples may well contain similar samples which convey overlapped information. Given limited data labeling budget, if we can exclude mutually similar samples and select ones with complementary information, the performance of these methods could be improved. In this paper, we develop techniques to solve this problem based on CTED.

4 Diversifying Convex Transductive Experimental Design

In this section, we propose to diversify the selected samples to improve CTED, i.e., highly similar samples are excluded. We first introduce a similarity matrix S 2 Rn⇥n to model the pairwise similarities among all the samples, such that larger value of sij means higher similarity between the i-th sample and the j-th one, and smaller value indicates their similarity is lower. Intuitively, if two samples are highly similar to each other, they tend to convey very similar information. In this case, we intend the two samples not to be selected together. To realize this, we enhance CTED with a diversity regularizer by extending Eq. (2) to the following optimization problem

FromEq. (3), we can see that if sij is large (i.e., the i-th sample and the j-th one are highly similar), bi and bj cannot be large at the same time. This constraint guarantees that highly similar samples would not have higher scores in sample selection at the same time.

The effectiveness of the diversity regularizer in Eq. (3) highly relies on the quality of the similarity matrix S. Properly defining a good S is the key for improving CTED by encouraging diversity of selected samples. A direct way to define S is to pre-calculate it based on the original data. Note that once the similarity matrix is defined, it is fixed in the following sample selection step. If the fixed similarity matrix is not well defined, the effectiveness of the diversity regularizer will be limited. To obtain a faithful similarity matrix and seamlessly incorporate diversity into CTED, we propose to embed similarity matrix learning into CTED via properly leveraging the special structure of the data reconstruction framework.

We observe that, the data reconstruction matrix A encodes relations among samples. Let us take a look at the i-th row of A, i.e., ai , which corresponds to the i-th sample. aij means the j-th sample's reconstruction coefficient based on the i-th sample. And ai encodes the reconstruction coefficients of all the samples based on the i-th one. The i-th row of A (i.e., ai ) can be treated as a data representation which reflects the role of the i-th sample for data reconstruction. If i-th and j-th samples are similar in terms of their capacity for reconstruction, they tend to have similar ai and aj . Therefore, we use sij = ai (aj )T ♣♣ai ♣♣2♣♣aj ♣♣2 to characterize the similarity between the i-th sample and j-th one. This similarity measure directly reflects the similarity relationship among samples in terms of their ability for reconstruction. Based on the above analysis, we define a novel and effective diversity regularizer and use it to regularize CTED. We get the following optimization problem of Diversified CTED (DCTED for short)

Note that the similarity matrix in Eq. (4) is adaptively updated in the learning process. We do not need to predefine a similarity matrix. This nice property makes our model very practical in real world applications. Our empirical studies also suggest that this diversity term is more effective than the one with a predefined similarity matrix. The involvement of the diversity regularizer makes the optimization problem in Eq. (4) hard to solve. In the next section, we derive an effective algorithm to solve it.

5 Optimization

The optimization problem in Eq. (4) involves two groups of variables, i.e., A and b. It is hard to solve due to the complex structure of the diversity term. We first reformulate this problem. Let A = diag(s)bA, where diag(s) is a diagonal matrix whose diagonal elements are formed by the vector s. The i-th element (i.e., si) of s is the `2-norm of the i-th row of A. Therefore, ♣♣bai ♣♣2 = 1. The problem in Eq. (4) can be reformulated as

s▷t▷ bi ≥ 0↪ si ≥ 0↪ ♣♣bai ♣♣2 = 1↪ i = 1↪ 2↪ ▷▷▷↪ n (5) Note that we can replace Pnj=1 ba2ij as 1. We keep it in Eq .(5) to better illustrate the relationship between the optimization problems in Eq. (4) and (5).

Theorem 1 The optimization problem in Eq. (5) is equivalent to the one in Eq. (4).

Proof 1 If (A⇤ ↪ b⇤ ) is the solution of the problem in Eq. (4), then h(A⇤ ↪ b⇤ )  h(A↪ b). Let A⇤ = diag(s⇤ )bA⇤ , where s⇤i is the `2-norm of the i-th row of A⇤ , we get k(bA⇤ ↪ s⇤ ↪ b⇤ ) = h(A⇤ ↪ b⇤ ). For (bA↪ s↪ b), it is easy to get k(bA↪ s↪ b) = h(A↪ b) ≥ h(A⇤ ↪ b⇤ ) = k(bA⇤ ↪ s⇤ ↪ b⇤ ). This means (bA⇤ ↪ s⇤ ↪ b⇤ ) is the solution of the problem in Eq. (5). Therefore, if we have the solution of the problem in Eq. (4), we can readily to get the solution of the problem in Eq. (5). Similarly, if we have the solution of Eq. (5), we can also readily to get the solution of Eq. (4). Therefore, the optimization problem in Eq. (5) is equivalent to the one in Eq. (4).

In next, we derive an alternating minimization algorithm to solve the problem in Eq. (5).

5.1 Update bA

s▷t▷ ♣♣bai ♣♣2 = 1↪ i = 1↪ 2↪ ▷▷▷↪ n We derive an algorithm to update bA based on projected gradient descent to decrease the objective value of Eq. (6). Denote the gradient of f(bA) as rf(bA). Then, bA is updated as bA = bA - θrf (bA) (7) where θ is the step size. Since bA should satisfies ♣♣bai ♣♣2 = 1, we achieve this by projecting each row of bA to the unit sphere. We need to search the step size to ensure the objective value is non-increasing under the updating rule of bA. 5.2 Update b

The subproblemw.r.t. b is

The optimization problem is convex w.r.t. bi when the other elements of b fixed. The subproblemw.r.t. bi is

where mij is the (i↪ j)-th entry of M = bAbAT . Set the derivative w.r.t. bi as zero, we get

It is easy to check that there exists positive solution of Eq. (10), which means the constraint bi ≥ 0 can be satisfied. We choose the positive solution to update bi.

5.3 Update s

The subproblemw.r.t. s is

The optimization problem is convex w.r.t. si when other elements of s fixed. We can find s⇤i which leads the derivative w.r.t. si to be zero. However, s⇤i may be negative. Therefore, we update si as

Algorithm 1 The Optimization Algorithm for Diversified CTED

Input: X, γ, and ↵ Output: Sort all the samples according to bi (i = 1↪ 2↪ ▷▷▷↪ n) and select the top m ranked ones

• 1: Initialize bA, s and b randomly 2: repeat
• 6: until Convergence
• 3: Update bA by Projected Gradient Descent 4: Update b by solving Eq. (10) 5: Update s by Eq. (12)

We summarize the whole procedure to solve the optimization problem in Eq. (5) as Algorithm 1. Since updating bA decreases the objective value of the optimization problem in Eq. (5) and solving b and s also decrease it, therefore the updating rules decrease the objective value of the optimization problem in Eq. (5). As the optimization problem in Eq. (5) is non-negative and lower bounded, therefore Algorithm 1 converges. Since the optimization problem in Eq. (5) is not convex w.r.t. all the variables simultaneously, different initializations of these variables may lead Algorithm 1 converges to different values. For simplicity, we initialize these variables randomly. Our empirical studies show that Algorithm 1 works well with this simple initialization strategy.

6 Experiments

Following a same experimental protocol in [Yu et al., 2008], we perform classification experiments on five benchmark data sets to demonstrate the effectiveness of the proposed method (i.e., Diversified CTED) and give analysis on the experimental results. We also perform experiments to study the effects of the parameters.

6.1 Datasets

We conduct the experiments on 5 publicly available data sets, including 2 digit recognition data sets (i.e., USPS [Wu and Sch¨olkopf, 2006] and MNIST [Liu et al., 2010]), 2 text data sets (i.e., WebKB [Wang et al., 2011] and Newsgroup [Yu et al., 2005]) and one face data set (i.e., ORL [Cai et al., 2006]). The details of these data sets are summarized in Table 1.

6.2 Experimental Setup

Similar with [Yu et al., 2008], we conduct the experiments in the following way. For each data set, we randomly select 50% of the data samples to construct a candidate set, from which each of the comparing active learning methods is adopted to select a given number m(= 10↪ 20↪ 30↪ ▷▷▷↪ 100) of samples. We train a classifier on the selected samples and their labels, and then predict the labels of the remaining 50% data samples. We use the classification accuracy on these 50% data samples to measure the performance of these comparing active learning methods. To avoid the bias of classifier, we choose two classifiers, i.e., SVM with linear kernel and K Nearest Neighbour (KNN) classifier, to predict the class labels. All the experiments are repeated 10 times and the average prediction accuracy is reported.

To evaluate the effectiveness of the proposed Diversified CTED (DCTED for short), we compare DCTED with the following closely related methods, including distribution matching via Maximum Mean Discrepancy (MMD) [Chattopadhyay et al., 2012], Convex Transductive Experimental Design (CTED) [Yu et al., 2008], Active Learning via Neighbourhood Reconstruction (ALNR) [Hu et al., 2013], and Accelerated Robust Subset Selection (ARSS) [Zhu and Fan, 2015]. We also compare DCTED with the method corresponding to Eq. (3). This method leverages a pre-defined and fixed similarity matrix. We denote this method as DCTEDf . For DCTEDf , we use gaussian function and linear function to define the pairwise similarities among samples and report the best result DCTEDf can achieve. The results of random selection are also reported. To fairly compare the above algorithms, we tune the parameters for all these methods from a large range of ¶10-3 ↪ 10-2 ↪ ▷▷▷↪ 103 ♦. We will give the sensitive analysis of the parameters of DCTED later in this section.

6.3 Experimental Results

We first show the comparisons between the original CTED method and Diversified CTED to investigate whether encouraging diversity can improve the performance of CTED. The experimental results are shown in Tables 2, 3, 4, 5 and 6. The first column of these tables indicate the number of selected samples and C, Df and D indicate CTED, DCTEDf and DCTED. Each table contains the results based on SVM and KNN classifier. In the reported results, the best one and those having no significant difference (i.e., p > 0▷05 according to t-test) with the best one are marked in bold. We have the following observations: 1) SVM achieves better performance than KNN classifier in most cases. 2) By encouraging diversity, both DCTEDf and DCTED significantly outperform CTED in most cases. Let us take the USPS data set as an example. When the number of selected samples is 10, DCTEDf and DCTED achieve the accuracy of 0.747 and 0.785, which improve the original CTED method by 29.2% and 35.81%. We also observe that, the original CTED method needs 40 samples to achieve 0.76 while DCTED method only needs 10 samples to achieve 0.785. This indicates that, the set of selected samples by DCTED is more informative since highly similar samples are excluded. 3) DCTED outperforms DCTEDf in most cases. This verifies the effectiveness of DCTED, which adaptively updates the similarity matrix defined on a new data representation. DCTED is more preferable in practice since it does not need to predefine the similarities among samples.

Now we show the comparisons with the state-of-the-art active learning methods. Due to the space limit, we report the averaged results over different number of selected samples. The results are shown in Tables 7 and 8. From the tables, we see that active learning methods achieve better performance than random selection in most cases. Our method (DCTED) outperforms the other comparing methods on these datasets.

6.4 Parameter Study

Now we study the effects of parameters. Compared with the original CTED method, our DCTED method introduces a new hyper parameter, i.e., ↵. It is interesting to investigate how this parameter affects the performance of DCTED. To illustrate the effects of ↵, we fix the number of selected samples as 50. For CTED, we report the best performance it achieves. For our method, i.e., DCTED, we vary the value of ↵ in [10-3 ↪ 10-2 ↪ ▷▷▷↪ 103 ] and report the corresponding results. Same as the setting in the previous subsection, the experiments are repeated 10 times with different data partitions and the average results are reported. The results are shown in Figs. 1 and 2. The results in these two figures show that our method (i.e., DCTED) achieves better performance than CTED in a wide range of ↵. This again verifies that, the ability of CTED can be improved by imposing diversity on sample selection. We also observe that, the performance of DCTED generally becomes better when the value of ↵ increases. In a certain value of ↵, DCTED achieves the best performance. If we continue to increase the value of ↵, the performance of DCTED starts to decrease. The reason is that, when ↵ is too large, the diversity regularizer will dominate the objective function and the reconstruction part has little effects on sample selection, leading to select samples which do not have good capacity for data reconstruction.

7 Conclusion

In this paper, we proposed to enhance CTED with diversity mechanism by imposing a diversity regularizer over sample selection. Our proposed method, i.e., Diversified CTED, can select informative samples with complementary information and exclude highly similar ones which convey overlapped information. Extensive experimental results demonstrated that, with diversification, Diversified CTED significantly improves CTED and consistently outperforms the state-of-the-art active learning methods.

Acknowledgments

We would like to thank the anonymous reviewers for their helpful comments and suggestions. This work is supported in part by China National 973 program 2014CB340301 and NSFC grant 61379043, 61502289.