Semi-Supervised Metric Learning Using Pairwise Constraints

1 Introduction

Distance metric is a key issue in many machine learning algorithms [Xiang et al., 2008]. Over the last few years, there has been considerable research on distance metric learning [Yang and Jin, 2006]. Many of the earlier studies optimize the metric with class labels for classification tasks [Lebanon, 1994; Hastie and Tibshirani, 1996; Zhang et al., 2003; Goldberger et al., 2004]. More recently, researchers have given much attention to distance learning for semisupervised algorithms and specially semi-supervised clustering algorithms. Since class label information is not generally available for clustering tasks, constraints are used as more natural supervisory information for these tasks. Pairwise similarity (positive) and dissimilarity (negative) constraints are the most popular kind of side information that has been used for semi-supervised clustering. However, other kinds of side information like relative comparisons (for example, x is closer to y than to z ) have also been

Saeed Bagheri Shouraki

Department of Electrical Engineering Sharif University of Technology bagheri-s@sharif.edu

considered in some studies [Schultz and Joachims, 2004; Kumar and Kummamuru, 2007].

Distance learning based on constraints has been studied by many researchers. [Klein et al., 2002] introduced one of the first distance learning methods for semi-supervised clustering. This method finds a distance metric according to the shortest path in a version of the similarity graph that has been altered by positive constraints. Some latter studies have considered a more popular approach that learns global Mahalanobis metrics from pairwise constraints. [Xing et al., 2003] proposed a convex optimization problem to learn a global Mahalanobis metric according to pairwise constraints. [BarÐHillel et al., 2005] devised a more efficient, non-iterative algorithm called Relevant Component Analysis (RCA) for learning a Mahalanobis metric. This method only incorporates positive constraints. An extension of the RCA method that can consider both positive and negative constraints has also been introduced [Yeung and Chang, 2006]. [Hoi et al., 2006] proposed Discriminative Component Analysis (DCA) method that uses the ratio of between chunklets and within chunklets convariance determinants as the objective function. Recently, [Xiang et al., 2008] introduced the trace ratio optimization problem as a more appropriate objective function. They have also provided a nice heuristic search to solve this problem. [Chang and Yeung, 2006] proposed a method that finds a locally linear metric using positive constraints. However, the objective function of this method has many local optima and the topology cannot be preserved well during this approach [Yeung and Chang, 2007]. [Chang et al., 2006] proposed a metric adaptation method. This method adjusts the location of data points iteratively, so that similar points tend to get closer and dissimilar points tend to move away from each other. As this method lacks an explicit transformation map, it cannot project new data points onto the transformed space straightforwardly [Chang et al., 2006]. In [Yeung and Chang, 2007], two kernel-based metric learning methods have been presented that have some limitations [Yeung and Chang, 2007].

Among the existing metric learning methods for semisupervised clustering, some of them [Xing et al., 2003; Yeung and Chang, 2006; Hoi et al., 2006; Xiang et al., 2008] can incorporate both positive and negative constraints for metric learning. But, none of these methods (that can consider both positive and negative constraints) have used the topological structure of data. Moreover, all of them find a linear transformation (or equivalently a Mahalanobis distance metric) according to pairwise constraints. In this paper, we formulate an objective function considering all data points along with pairwise similarity and dissimilarity constraints and generalize this objective function to learn a nonlinear transformation. We find the global optimum of the proposed objective function using the search algorithm introduced by [Xiang et al., 2008]. As our metric learning method can find nonlinear metrics and also it considers the topological structure of data, it shows higher capability compared with the existing methods.

The rest of this paper is organized as follows: In Section 2, a metric learning method considering both pairwise constraints and the intrinsic structure of data is proposed. In this section, first we introduce an optimization problem to find an appropriate linear metric and then we provide a nonlinear metric learning method as a special case of the kernelized version of our linear method. Section 3 presents experimental results on some synthetic and real-world data sets. Concluding remarks are given in the last section.

2 Proposed Metric Learning Approach

In this section, first we propose a metric learning method using pairwise constraints while considering the topological structure of data. Then, we introduce a non-linear extension of this method.

2.1 Linear metric learning

To find an appropriate metric, the manifold structure of data is incorporated along with pairwise (positive and negative) constraints in our method. We are given a set of data points 1 { } n i i X _ _ x and two sets including positive {( , ) | and are in the same class} i j i j P _ x x x x and negative {( , ) | and are in two different classes} i j i j D _ x x x x constraints. The optimization problem for the transformation T _ y W x is defined as:

Here, ( ) J W shows a penalty (regularizer) term that tries to preserve the topological structure of data during the transformation, and 0 ∈ ω balances between distances of similar pairs and the regularizer term. In (1), a metric T _ A WW is sought that makes distances between point pairs in D as large as possible while making a combination of distances between point pairs in P and the penalty term as small as possible. The constraint T _ W W I has also been considered to prevent improper solutions [Xiang et al., 2008; Hoi et al., 2006]. Based on T _ y W x , we can rewrite the optimization problem in (1) as:

Here, tr shows the trace operator, and w S and b S are defined as:

If we set 0 ∈ _ in (2), the problem becomes similar to the optimization problem introduced in [Xiang et al., 2008]. In (2), d d R W ζ ⋅ ∨ shows the transformation matrix (with d d ζ η ), where d and dζ denote the dimensionality of the input and the transformed space respectively. When d dζ _ , we have T T WW W W I _ _ which generates the Euclidean metric [Xiang et al., 2008] and thus we consider d d ζ ] .

To preserve the topological structure of data via the term ( ) J W in the objective function, we use the idea of Locally Linear Embedding (LLE) method [Roweis and Saul, 2000]. Indeed, we try to preserve the manifold structure of data by retaining locally linear relationships between close data points in the transformed space. Given the set of data points, a k -nearest neighbor graph models the relations between close data points. The optimal weight matrix * * [ ] ij s _ S providing minimal error for the linear reconstruction of data points from their neighbors is obtained according to:

where , . k i N x shows the set of k nearest neighbors of i x . This problem can be solved as a constrained least-squares problem [Roweis and Saul, 2000]. After finding the optimal weight matrix * S , we define the penalty term , . J W as:

where * * ( ) ( ) T _ 2 2 E I S I S and ≡ ← 1 2 , , , n _ Y y y y � . Thus, for T _ y W x , we have , . ( ) T T J tr _ W W XEX W where ≡ ← 1 2 , , , n _ X x x x � . In (6), , . J W denotes the locally linear reconstruction error of the transformed data points according to the weight matrix * S . Indeed, it reflects the assumption of preserving the geometrical structure of data in the transformed space.

By substituting (6) into (2), we have

This problem cannot be solved by eigenvalue decomposition approaches. However, we can use the search algorithm introduced in [Xiang et al., 2008] for optimizing the constrained trace ratio problem. Since the matrix E and consequently T w ∈ 0 S XEX are symmetric positive semi-definite matrices, the necessary condition of the introduced algorithm in [Xiang et al., 2008] is satisfied even when we consider the regularizer term in the objective function. Thus, we can use the heuristic search algorithm presented in [Xiang et al., 2008] to solve the proposed optimization problem and find the optimal transformation matrix * W or equivalently the optimal metric * * * ( ) T _ A W W .

2.2 Kernel-Based Metric Learning

In this section, first we introduce a kernelized version of our linear metric learning method presented in the above section and then we consider a special case of this kernelized method as the proposed kernel-based metric learning method. To perform our linear method in Reproducing Kernel Hilbert Space (RKHS), we consider the problem in a feature space F induced by a nonlinear mapping : d R F Α τ [Cai et al., 2007]. For a proper chosen Α , we can define an inner product on F using Mercer kernel ( ), ( ) ( , ) K Α Α ] {_ x y x y where (.,.) K is a positive semidefinite kernel function. Many choices for kernel functions that satisfy MercerÕs condition are possible such as polynomial, Gaussian, and exponential kernels.

In the kernel-based method, we apply the transformation matrix ≡ ← 1 2 , ,..., dζ _ W w w w consisting of orthonormal vectors Ψ β | 1,2,..., i F i d ζ ∨ _ w ( , , i j i j ⌠ ] {_ w w ) on ( ) F Α ∨ x via the transformation ( ) T Α _ y W x . This transformation performs a mapping from d R to d R ζ . To express the optimization problem in the kernel space, first we rewrite the problem in (1) as:

where

D U can also be defined similarly according to the set of negative constraints D . Let 1 2 [ ( ), ( ),..., ( )] n Α Α Α _ � x x x denotes the data points in the kernel space. As ( ) T Α _ y W x , we obtain the following optimization problem in the RKHS:

Since the vectors { | 1,2,..., } i F i d ζ ∨ _ w can be written as linear combinations of data points in the kernel space 1 2 ( ), ( ), , ( ) n Α Α Α x x x � 1 , there exist a matrix ≡ ← 1 2 , , , d ζ _ V v v v � such that _ W �V . Indeed, each n - dimensional vector i v contains coefficients required for computing i w from data points in the kernel space. Thus, we can rewrite (12) as:

where T _ K � � is the kernel matrix. Since D KU K and ( ) P ∈ 0 K U E K are positive semi-definite matrices, we can solve this optimization problem using the search algorithm introduced in [Xiang et al., 2008].

Unfortunately, for many kernel learning settings, the amount of supervisory information is typically very limmited [Yeung et al., 2007]. Allowing too much flexibility in the model while having limited supervisory information may lead to model over-fitting [Yeung et al., 2007]. Here, we restrict the transformation matrix W in (12) and revise the optimization problem for finding a smaller matrix. We limit the columns of matrix W such that they are calculated only from positively constrained data points (these data points are usually the most informative ones). Let 1 2 { , , , } m l l l x x x � be the set of data points appearing in positive constraints and m be the number of unique data points involved in positive constraints. If we restrict the columns of matrix W to linear combinations of 1 2 ( ), ( ), , ( ) m l l l Α Α Α x x x � , the transformation matrix W can be defined as ζ ζ _ W �V where ζ V is an m dζ ⋅ matrix and 1 2 [ ( ), ( ), , ( )] m l l l Α Α Α ζ _ � x x x � . In this case, we obtain the following optimization problem:

where 1 [ (., ),..., (., )] T m l l ζ ζ _ _ K � � K K . Also, we have ( ) T T T ζ ζ ζ ζ _ _ _ Y W � �V � V K . According to (14), we need to optimize a smaller matrix ζ V than V . We can use the heuristic search algorithm introduced in [Xiang et al.,

1 Using the search algorithm presented in [Xiang et al. 2008], the columns of W in (12) are obtained as eigenvectors of ( ( )) T D P Θ ∈ 2 0 � U U E � and these eigenvectors are linear combinations of 1 2 ( ), ( ), , ( ) n Α Α Α x x x � .

2008] to find the optimal matrix ζ V and then we compute the transformed data points accordingly T ζ ζ _ Y V K . We use the exponential kernel , . ( , ) exp K w _ 2 2 x y x y in our method.

3 Experimental Results

In this section, we explain experiments that we have conducted to compare our non-linear metric learning method with some existing methods. We measure the effectiveness of semi-supervised metric-learning algorithms by comparing clustering results obtained from using different metrics.

3.1 Comparison of Metrics

We compare our non-linear method with the metric learning algorithms introduced in [Xiang et al., 2008; Xing et al., 2003; Yeung and Chang, 2006], as they are the most effective methods considering both positive and negative constraints. We also include the LLMA algorithm [Chang and Yeung, 2006] in our evaluations. This algorithm is one of the most powerful metric learning methods that only use positive constraints (it provides a globally non-linear metric).

As in [Xing et al., 2003; Yeung and Chang, 2006; Chang and Yeung, 2006], we use the Euclidean distance (without metric learning) for the baseline comparison and apply the k-means clustering algorithm with different distance metrics to compare these metrics. Thus, the performance of our nonlinear metric learning algorithm is evaluated by comparing the following algorithms:

1. k-means without metric learning;
2. k-means with the metric learning method introduced in [Xiang et al., 2008];
3. k-means with the LLMA [Chang and Yeung, 2006] method for metric learning;
4. k-means with the extended RCA [Yeung and Chang, 2006] method for metric learning;
5. k-means with the metric learning method introduced in [Xing et al., 2003];
6. k-means with our non-linear metric learning method. k _ ,

The parameters of our algorithm are set to 10 2 d m ζ _ , and

The kernel parameter w of our method and the Gaussian window parameter of the LLMA method are specified as 2 [ ( 1)] x x i j i j w n n ∩ ] _ 2 0 ⎠ according to [Chang and Yeung, 2006] where we set 1.5 ∩ _ for our method. The number of nearest neighbors k of the LLMA has also been set to 10 k _ and the parameter Θ of this algorithm has been set to 0.2 Θ _ (this value provides better results than 5 Θ _ used in [Chang and Yeung, 2006]). For optimization in the LLMA algorithm, we used the spectral method. Finally, we set the reduced dimensionality of the method of [Xiang et al., 2008] to half of the dimensionality of the input space [Xiang et al., 2008].

As in [Yeung and Chang, 2006], we set nc P D _ _ for methods that use both positive and negative constraints. Since results depend on P and/or D sets, we generate 20 different P and/or D sets for each data set. Finally, we run the k-means algorithm 20 times with different random initializations for each P and/or D set.

3.2 Performance Measure

To evaluate the performance of clustering in our experiments, we employ the Rand index as the most widely used measure by semi-supervised metric learning algorithms. It shows how well the clustering results agree with the ground truth clusters [Chang and Yeung, 2006]. Let s n be the number of data pairs assigned to the same cluster, both in the ground truth and the resultant clustering (i.e., matched pairs) and d n be the number of data pairs assigned to different clusters both in the ground truth and the resultant clustering (i.e., mismatched pairs). The Rand index is defined as 2( ) / ( ( 1)) s d RI n n n n _ 0 2 [Xing et al., 2003] ( n denotes the number of data points). This index favors assigning data points to different clusters when there are more than two clusters [Xing et al., 2003]. Thus, we modify the Rand index as in [Xing et al., 2003] such that the matched pairs and mismatched pairs are assigned weights to give them equal chances of occurrence (0.5) [Chang and Yeung, 2006].

3.3 Experiments on Synthetic and UCI Data Sets

At first, we conduct experiments on three synthetic data sets displayed in Figure 1. In this figure, the data points that belong to the same class are shown with the same style. Figure 2 shows the results of applying different algorithms on these data sets as box-plots ( nc P D _ _ ). Although the LLMA algorithm gives good results on two out of the three synthetic data sets, our method performs well on all of them.

We then conduct further experiments on nine real-world data sets obtained from the Machine Learning Repository 2 of the University of California, Irvine (UCI): Soybean (47/35/4), Protein (116/20/6), Iris (150/4/3), Wine (178/13/3), Ionosphere (351/34/2), Boston housing (506/13/3), Breast cancer (569/31/2), Balance (625/4/3), and Diabetes (768/8/2). The numbers inside parentheses (n/d/c) show the number of data points n , the number of features d , and the number of classes c . Figure 3 shows the results of different algorithms on the nine UCI data sets. The number of constraints nc used for different data sets has been specified according to the numbers used in [Yeung and Chang, 2006; Chang and Yeung, 2006]. All of the data sets are normalized before use in the clustering algorithms (each feature is normalized to zero mean and unit standard deviation).

2 http://archive.ics.uci.edu/ml/

As we can see in Figure 3, our method generally provides better results than the other methods. By comparing the proposed method with [Xiang et al., 2008], the most recent metric learning method, we find that our method is clearly better than it for six out of the nine data sets and comparable with it for two of the data sets.

4 Conclusions and Future Works

In this paper, we introduced a novel metric learning method for semi-supervised clustering. The existing metric learning methods that can use both positive and negative constraints have not incorporated the geometrical structure of data. Additionally, they only provide linear metrics. The proposed method uses the topological structure of data along with positive and negative constraints to find an appropriate metric. We proposed a kernel-based method to find a non-linear metric that is usually more useful than linear metrics. Experimental results on synthetic and UCI data sets showed the superior performance of our algorithm. In the future, we will investigate other forms of kernel-based metric learning methods. We also intend to evaluate the performance of our method on other real-world applications.