Active Learning Based on Local Representation

1 Introduction

In many applications, expensive human actions are required to collect label information. To reduce the cost of labeling, active learning methods are designed to choose the most informative examples (i.e., improve the classifier the most) to label for training, which have been shown to benefit many real world applications such as image retrieval [Gosselin and Cord, 2008], image and video classification [Yan et al., 2003; Qi et al., 2008], object categorization [Kapoor et al., 2010] and document summarization [He et al., 2012] and so on.

There has been a long history of research on active learning in machine learning community [Chapelle, 2005; Freund et al., 1997]. Traditional active learning research usually considers obtaining labels to maximize some measure of predictive power or model accuracy. The most widely used measures include uncertainty sampling [Settles, 2009; Tong and Koller, 2002], estimated error reduction [Roy and McCallum, 2001] and variance reduction [Cai and He, 2012].

Recently, some researchers consider the active learning process from a perspective of data reconstruction. Transductive Experimental Design (TED) [Yu et al., 2006] selects the points that the original data space can be reconstructed in a global way where each data point is linearly reconstructed by using all of the selected data points. However, given a target point, it is more reasonable to reconstruct it by using only its nearest neighbors since the points far away from the target point have little or even negative effect for the reconstruction.

In this paper we propose a novel method, called Active Learning via Neighborhood Reconstruction (ALNR) to select the most informative points by exploring the local geometrical structure of data space directly. Specifically, each data point can be reconstructed by only using the selected points in its neighborhood. Two important regularization penalties are considered in the objective function to incorporate the locality information and enforce the sparsity of the coefficients for final reconstruction separately. Furthermore, we propose an efficient two-stage iterative scheme to solve the final optimization problem. Firstly, the optimization problem can be factored into several subproblems based on blockwise coordinate descent method. And then, by pre-defining a special tree-structure, we demonstrate that each subproblem equals to a structured sparsity-inducing regularized problem, which can be solved via a primal-dual approach efficiently. Experimental results on both synthetic and real world data sets show that our proposed ALNR indeed has better performance than other state-of-the-art active learning approaches.

The rest of this paper is organized as follows. In Sections 2, we provide a brief review of the related work about the active learning method and structured sparsity-inducing regularization. Our algorithm is introduced in section 3 and we describe the two-step iterative optimization scheme to solve the final optimization problem in the section 4. A variety of experimental results are presented in Section 5. Finally, we provide some concluding remarks in Section 6.

Notations: Let X = [x1, ..., xn] be the set of data points, where each xi ∈ Rd corresponding to a data point. Unless specifically mentioned, we use X to represent both the matrix and set {xi}. And let Z = [z1, ..., zm] ⊂ X be the set of m selected points. For any vector a = (a1, a2, . . . , ad)T ∈ Rd , the l2 norm is defined as ‖a‖2 = √∑ni=1 |a2i |, and the supnorm of a is defined as ‖a‖∞ = max 1≤i≤d |ai|.

2 Background

The work most related to our approach is the the Transductive Experimental Design (TED) [Yu et al., 2006], whose key idea is to minimize the average predictive variance of the estimated regularized linear regression function. In a geometrical view, this is equivalent to find m representative data samples Z = [z1, ..., zm] ⊂ X that span a linear space to retain most of the information of X, which can be formulated as follows

where α is the regularization parameter controlling the amount of shrinkage. To solve this problem, a suboptimal sequential greedy algorithm to select the m representative points one by one was proposed [Yu et al., 2006] and a nongreedy algorithm is also designed for the convex relaxation of problem (1). Cai et al. further proposed to choose the samples in the data manifold adaptive kernel space based on the convex TED [Cai and He, 2012]. Their experimental results showed that the incorporation of the locality information can improves the performance of active learning process. Other active learning works related to our work include Simple Margin method [Tong and Koller, 2002] and LLRActive [Zhang et al., 2011].

In sparse coding literature, the structured sparsity-inducing regularization has been introduced to enforce the sparsity in the feature vector with the consideration of the structure of the features [Roth and Fischer, 2008; Yuan and Lin, 2006]. This topic recently has attracted many researchers' attention. By assuming disjoint groups structure of features, the group lasso model was proposed to enforce sparsity on the pre-defined groups of features [Bach, 2008]. Furthermore, this model has been extended to allow groups that hierarchical as well as overlapping [Zhao et al., 2009; Kim and Xing, 2010; Liu and Ye, 2010]. Considering the possible non-smoothness of the structured regularization, a series of optimization methods are also proposed to solve such problems efficiently [Jenatton et al., 2011; Qin and Goldfarb, 2012].

3 The Objective Function

From formulation (1), we can see that TED reconstructs each point via a linear combination of all the selected points. Geometrically speaking, it is more reasonable to approximate xi by the linear combination of only its neighbors to capture the local geometrical information of data. The recent theoretical works in machine learning [Yu et al., 2009; Wang et al., 2010] have shown that the learning performance can be significantly enhanced if the local geometrical structure is exploited. For any selected point zj ∈ Z, we denote function d(zj, xi) to be the distance between zj and xi, where d(·, ·) can be any distance such as Euclidean distance and geodesic distance. Intuitively, the smaller d(zj, xi) is (zj is closer to xi), the greater effect zj should have for the local reconstruction of xi and vice versa.

Motivated by these facts, we propose a new novel method called Active Learning via Neighborhood Reconstruction (ALNR) to select the most informative points. For each point xi, we claim that the corresponding reconstruction should be built mainly over its neighborhood. By penalizing the coefficients of the reconstruction, we formulate our objective function as follows

where aji is the j-th element of vector ai and μ is a regularization parameter. In the objective function (2), the first term ‖xi - Zai‖22 means that xi should be close to its physical approximation Zai, and the second term ∑mj=1 |aji|d(zj , xi) restricts the reconstruction of xi to be localized.

Unfortunately, the optimization problem (2) is a combinatorial problem. The optimal representative data set for xi is usually not optimal for other points. To get the reconstructions of all the data points, we would have to search over an exponential number of possible sets to determine the unique optimal Z.

Considering this difficulty, we firstly relax the problem (2) by assuming that all the data points are selected to be representative points, i.e., Z = X. In this case, we transform problem (2) to a special case of sparse coding problem [Xie et al., 2010], which can be formulated as follows

where ‖ · ‖F stands for the Frobenius norm of matrices. Since our target is to choose themmost informative points, the corresponding coefficients of linear reconstructions on these m selected points must have larger weights and the weights of each data point on other n -m points should be as small as possible. Notice that the l-th row of matrix A reflects the importance of the point xl in the linear reconstruction of original data space. This is equivalent to require the optimal solution A should be sparse enough in rows. And the m most informative rows of A are exactly corresponding to the finally selected m representative data points of the whole data set X.

To enforce the sparsity of the row vectors of the final optimal solution A, we propose to utilize the sup-norm ‖ · ‖∞ to penalize each row vector. Sup-norm has the effect of "grouping" the elements in vector such that they can achieve zeros simultaneously. For simplicity, we define weight matrix D ∈ Rn×n , where Dij = d(xi, xj). We further denote vector ˜ai ∈ Rn where ˜aTi is the i-th row vector of matrix A and ˜aij to be the j-th element of vector ˜ai, i.e. ˜aij = aji. Then we can reformulate our final objective function as follows

where μ and λ are two positive trade-off parameters to control the degree of penalty.

Once the optimal solution [˜a1, ˜a2, . . . , ˜an] of the original optimization problem (4) is obtained, we rank all the data points according to the value of ‖˜as‖∞(s = 1, 2, . . . , n) in descending order and the top m points are selected.

4 OptimizationMethod

In this section, we discuss how to solve the optimization problem (4). Although the two regularizations in the objective function are both convex individually, the main challenge is how to deal with them simultaneously. Notice that the objective function is separable, we propose a two-stage iterative optimization scheme to solve problem (4), where the original problem is factored into n subproblems based on blockwise coordinate descent method in the first step and each subproblem can be solved by using structured optimization techniques efficiently in the last step.

4.1 Blockwise Coordinate Descent

Recall that the ˜ai in problem (4) represents the coefficient vector of the i-th sample reconstructing all the n samples, we call ˜ai a block. Since the objective function is separable, the blockwise coordinate descent method consists of simultaneously updating the coefficients within each block while holding all the others fixed, then cycling through this process. Therefore, if the current estimates are ˜ai, i = 1, ..., n, then ˜ai is updated by the following subproblems:

where the first term f(˜ai) = ‖Ri - xi˜aTi ‖2F and Ri = X - ∑ j̸=i xj˜aTj denotes the partial residual matrix. And the second term Φ(˜ai) = ∑nj=1 μ|˜aij |Dij + λ‖˜ai‖∞ is the penalty for each subproblem.

If the trade off parameter μ = 0, the penalty term Φ(˜ai) turns into the general sup-norm. Then the problem in (5) decouples into a sup-norm penalized least squares regression problem. It has been shown that there exists a closed form solution for this type of problem [Liu et al., 2009]. However, when μ ̸= 0, the penalty term Φ(˜ai) has a more complex structure, which leads a much more sophisticated situation than before. So the most critical part in our optimization is how to deal with Φ(˜ai) in subproblem (5) efficiently.

4.2 Geometrical Interpretation of Φ

In this subsection, we show that the penalty term Φ(˜ai) actually can be described as a hierarchical sparsity-inducing regularization with a predefined tree-structured set of groups, which can be defined as follows

Definition 4.1. (Tree-structured set of groups [Jenatton et al., 2011]) A set of groups G = {g}g∈G is said to be treestructured in {1, . . . , n}, if ⋃g∈G g = {1, . . . , n} and for all g, h ∈ G,

For such a set of groups, there exists a (non-unique) total order relation ⪯ such that

Based on this definition, given a tree-structured set of groups G = {g}g∈G, for any vector b ∈ Rn , the hierarchical sparsity-inducing regularization is defined as follows

where b|g ∈ Rn whose coordinates are equal to those of b for indices in the group g, and 0 otherwise. Specifically, ‖ · ‖ stands for the l∞ or l2 norm, and (ωg)g∈G denotes some predefined weights. By the theoretical analysis of [Zhao et al., 2009], when penalizing by Ω, some of the vectors b|g are set to zero for some g ∈ G, which leads the desired effect of structured sparsity.

With the notations of tree-structured set G and its associated hierarchical sparsity-inducing regularization, we construct a two-layer tree-structure of groups (see Figure 1) for the specific configuration of Φ(˜ai) in subproblem (5) . The root node in the first layer is assigned with the group gn+1 = {1, 2, . . . , n}, and the n leaf nodes in the second layer are assigned with the group gj = {j} separately, j = 1, . . . , n. It is easy to check that the set M = {g1, g2, . . . , gn+1} is a treestructured set of groups according to the Definition 4.1. Then the associated hierarchical sparsity-inducing regularization of M can be formulated as

where the weights are set to be

According to the definition of ˜ai|gj , it is obvious to see that

Based on above results, we can find that

Algorithm 1 Active Learning based on Neighborhood Reconstruction

Input:

• The candidate data set: X = [x1, x2, . . . , xn]
• The number of selected points: m
• The parameters: μ, λ and N

Output:

• The set of m selected points Z
• 1: Compute the weight matrix D.
• 2: for k = 1, . . . ,N do
• 3: for i = 1, . . . , n do
• 4: Compute the weights of Φ(˜ai) according to (8).
• 5: Update ˜ak+1 i as in (15) until convergence.
• 6: end for
• 7: end for
• 8: Rank the data points according to ‖˜as‖∞ (s = 1, . . . , n) in descending order, and return the top m data points.

So penalty term Φ(˜ai) is just the hierarchical sparsityinducing regularization of the tree-structured set M.

4.3 Proximal Method for Subproblem (5)

Recall the fact that in the objective function F(˜ai) of problem (5), f(˜ai) is convex and differentiable whereas the penalty term Φ(˜ai) is convex and nondifferentiable with respect to ˜ai. We propose to solve the problem (5) by using proximal method [Nesterov, 2007; Beck and Teboulle, 2009], which has been widely applied for its outstanding ability to deal with large-scale, possibly nonsmooth problems.

Proximal method solves the problem (5) iteratively. Firstly, for any t > 0, in the k-th iteration, the proximal method constructs an approximation of F(˜ai) at the current estimate ˜aki as follows

Then, we update ˜ak+1 i as the unique minimizer of Q(˜ai, ˜aki ):

Notice that Φ(˜ai) is the hierarchical sparsity-inducing regularization associated with tree-structured set of groups M and the dual norm of sup-norm is l1 norm, the problem (11) can be solved via a primal-dual approach based on the theoretical work of Jenatton et al. Specifically, the detailed formulation of the dual problem of (11) can be described in the following theorem.

Theorem 4.1. [Jenatton et al., 2011] Let us consider the following problem

where ξ = [ξg1 , ξg2 , . . . , ξgn+1 ] ∈ Rn×(n+1) and ξgj,l denotes the l-th coordinate of the vector ξgj ∈ Rn . Then the problem (11) and (12) are dual to each other and strong duality holds. In addition, the pair of primal-dual variables {˜a∗i , ξ ∗ } is optimal if and only if ξ ∗ is a feasible point of the optimization problem (12), and

and for ∀gj ∈M

where Πtwj (·) stands for the orthogonal projection onto the ball of the l1 norm with radius tωj.

Based on this theorem, the blockwise coordinate ascent method is used to solve the dual problem (12) efficiently. For each gj ∈ M, we update the vector ξgj and keep other dual variables fixed. Then the primal variable ˜ak+1 i and dual variable ξgj are updated alternatively as follows

This process is repeated until a stable ˜ak+1 i is obtained. Based on the recent theoretical work of structured optimization method, the optimal ˜ak+1 i can be obtained exactly with only one iterations over all the groups of M [Jenatton et al., 2011].

Overall, we summarize the complete procedure in Algorithm 1, whose convergence can be guaranteed by the blockwise coordinate descent method.

5 Experiments

To demonstrate the effectiveness of our proposed algorithm, we evaluate and compare four active learning methods:

• Random Sampling method which randomly selects points from the data set. This method is used as the baseline for active learning.
• Simple Margin method which selects the points closest to the current decision boundary of the SVM classifier as the most informative ones [Tong and Koller, 2002].
• Transductive Experimental Design (TED) is proposed in [Yu et al., 2006].

• Active Learning based onNeighborhoodReconstruction (ALNR) proposed in this paper. The data is first clustered by a simple spectral clustering method. Then for any two data points x, y, the dissimilarity measure d(x, y) is set to be the geodesic distance between x and y when x and y are in a same cluster, and d(x, y) is set to be ∞ when x and y are in different clusters.

We note that all the methods use linear SVM with squared hinge loss function as the base classification method.

5.1 Toy examples

In this subsection, we apply the active learning algorithms on two synthetic data sets to give an intuitive idea of how ALNR performs differently from TED. The synthetic data sets are described as follows

• Two-circle data set (Figure 2): There are two circles, each contains 200 points.
• Two-moon data set (Figure 2): There are two moons, each contains 200 points.

Then we apply TED and ALNR to select the most informative points on the two synthetic data sets. The results are shown in Figure 2. The points selected by each active learning algorithm are marked as solid blue dots. Compared with TED, the points selected by ALNR can better represent the original data set. This is because ALNR can better capture the nonlinear structure of the data by incorporating the important local geometrical information into the objective function (4).

5.2 Face Recognition

In this subsection, we investigate the performance of the different active learning algorithms by using them to solve the face recognition problem on Yale face database.

Yale face database contains 165 gray scale images of 15 individuals. There are 11 images per subject, including variations in lighting condition (left-light, center-light, right-light), facial expression (normal, happy, sad, sleepy, surprised, and wink), and with/without glasses. All the images are manually aligned and cropped. The size of each cropped image is 32×32 pixels, with 256 gray levels per pixel. Thus each image is represented as a 1024-dimensional vector. So face recognition is a classification problem in a 1024-dimensional Euclidean Space. Figure 3 shows some sample images from the Yale face database.

The evaluations are conducted with 10 randomly generated subsets of the original data set. The average classification accuracy is computed over these 10 tests. For each test, 10 images from each class are randomly chosen to form the data set. Therefore, there are 150 (15×10) face images per test, and each active learning algorithm is applied to select a given number ω = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50} of training samples. The unselected samples are used as the testing data.

Figure 4 shows the average classification accuracy versus the number of training (selected) samples of different active learning algorithm on Yale face database. It can be seen that, for all compared algorithms, the classification accuracy increases with the size of training examples. And our proposed ALNR has the best performance over all the size of train examples. It is worthwhile to note that ALNR performs especially good when the number of training examples is limited which is very common in the practical applications. Our experimental results also demonstrate that the local geometrical information can greatly improve the performance of active learning process.

5.3 Parameter Selection

There are two essential parameters, μ and λ, in our ALNR algorithm, where parameter μ is used to control the locality and λ is used to control the degree of sparsity. In our previous experiments, we simply set λ = 0.5, μ = 1. In this subsection, we examine how the average performance of ALNR varies with the parameters μ and λ separately. We conduct 10 random tests as in the last subsection and the number of selected training examples ω is set to be 30. When λ is fixed to be 0.5, the impact of μ for average performance is shown in Figure 5, where we can see ALNR can achieve consistent good performance with μ varying from 0.4 to 1.8. And Figure 6 shows the experimental results with μ fixed to be 1 and λ varying from 0 to 1, where ALNR always has a good performance with different λ.

6 Conclusion

In this paper, we propose a novel method called Active Learning via Neighborhood Reconstruction (ALNR) to select the most representative points from a local reconstruction perspective. The reconstruction of each data point is mainly conducted over the selected points only in its neighborhood. In this way, we incorporate the important local geometrical information into the active learning process. An efficient twostage iterative scheme is also proposed for the final optimization problem. Experimental results on two synthetic and one real world data sets show the effectiveness of our approach. It is interesting to explore how to accelerate ALNR for real world applications in our following work.

Acknowledgments

This work is supported by National Basic Research Program of China (973 Program) under Grant 2012CB316400 and National Natural Science Foundation of China (Grant No: 61125203, 61222207, 61233011, 90920303).