Title: UNSUPERVISED METRIC LEARNING VIA NONLINEAR FEATURE SPACE TRANSFORMATIONS

Abstract: In this paper, we propose a nonlinear unsupervised metric learning framework to boost of the performance of clustering algorithms. Under our framework, nonlinear distance metric learning and manifold embedding are integrated and conducted simultaneously to increase the natural separations among data samples. The metric learning component is implemented through feature space transformations, regulated by a nonlinear deformable model called Coherent Point Drifting (CPD). Driven by CPD, data points can get to a higher level of linear separability, which is subsequently picked up by the manifold embedding component to generate well-separable sample projections for clustering. Experimental results on synthetic and benchmark datasets show the effectiveness of our proposed approach over the state-of-the-art solutions in unsupervised metric learning.

1. INTRODUCTION:

Cluster analysis has broad applications in various disciplines. Grouping data samples into categories with similar features is an efficient way to summarize the data for further processing. In measuring the similarities among data samples, the Euclidean distance is the most common choice in clustering algorithms. Under Euclidean distance, feature components are assigned with the same weight, which essentially assumes all features are equally important across the entire data space. In practice, such setup is often not optimal. Learning a customized metric function from the data samples can usually boost the performance of various machine learning algorithms (Bellet et al., 2013) . While metric learning has been extensively researched under supervised (Xing et al., 2003; Weinberger & Saul, 2009; Wang et al., 2012; Noh et al., 2010) and semi-supervised settings (Peng et al., 2002; Domeniconi et al., 2001; Zhang et al., 2016; Niu et al., 2014) , unsupervised metric learning (UML) remains a challenge, in part due to the absence of ground-truth label information to define a learning optimality. In this paper, we focus on the problem of UML for clustering.

As the goal of clustering is to capture the natural separations among data samples, one common practice in the existing UML solutions is to increase the data separability and make the separations more identifiable for the ensuing clustering algorithm. Such separability gain can be achieved by projecting data samples onto a carefully chosen low-dimensional manifold, where geometric relationships, such as the pairwise distances, are preserved. The projections can be carried out linearly, as through the Principle Component Analysis, or nonlinearly, as via manifold learning solutions. Under the dimension-reduced space, clustering algorithms, such as K-means, can then be applied.

Recent years have seen the developments of UML solutions exploring different setups for the lowdimensional manifolds. FME (Nie et al., 2010) relies on the learning of an optimum linear regression function to specify the target low-dimensional space. Abou-Moustafa et al. (2013) model local sample densities of the data to estimate a new metric space, and use the learned metric as the basis to construct graphs for manifold learning. Application-specific manifolds, such as Grassmann space (Huang et al., 2015) and Wasserstein geometry (Seguy & Cuturi, 2015) , have also been studied. When utilized as a separate preprocessing step, dimensionality reduction UML solutions are commonly designed without considering the ensuing clustering algorithm and therefore cannot be fine-tuned accordingly.

AML (Ye et al., 2007) takes a different approach, performing clustering and distance metric learning simultaneously. The joint learning under AML is formulated as a trace maximization problem, and numerically solved through an EM-like iterative procedure, where each iteration consists of a data projection step, followed by a clustering step via kernel K-means. The projection is parameterized by an orthogonal, dimension-reducing matrix. A kernelized extension of AML was proposed in (Chen et al., 2007) . As the projection models are built on linear transformations, their capabilities to deal with complex nonlinear structures are limited.

UML solutions performing under the original input space have also been proposed. SSO (Jiang et al., 2011) learns a global similarity metric through a diffusion procedure that propagates smooth metrics through the data space. CPCM (Gupta et al., 2008) relies on the ratio of within cluster variance over the total data variance to obtain a linear transformation, aiming to improved data separability. As the original spaces are usually high-dimensional, UML solutions in this category tend to suffer from the local minima problem.

In light of the aforementioned limitations and drawbacks, we propose a new nonlinear UML framework in this paper. Our solution integrates nonlinear feature transformation and manifold embedding together to improve the data separability for K-means clustering. Our model can be regarded as a fully nonlinear generalization of AML, in which the transformation model is upgraded to a geometric model called Coherent Point Drifting (CPD) (Myronenko & Song, 2010a) . Data points are driven by CPD to reach a higher level of linear separability, which will be subsequently picked up by the manifold embedding component to generate well-separable sample projections. At the end, K-means is applied on the transformed, dimension-reduced embeddings to produce label predictions. The choice of CPD is with the consideration of its capability of generating high-order yet smooth transformations. The main contributions of this paper include the following.

• Our proposed fully nonlinear UML solution enhances data separability through the combination of CPD-driven deformation and spectral embeddings. • To the best of our knowledge, this is the first work that utilizes dense, spatial varying deformations in unsupervised metric learning. • The CPD optimization has a closed-form solution, therefore can be efficiently computed.

• Our model outperforms state-of-the-art UML methods on six benchmark databases, indicating promising performance in many real-world applications.

The rest of this paper is organized as follows. Section 2 describes our proposed method in detail. It includes the description of CPD model, formulation of our CPD based UML, optimization strategy and the approach to kernelize our model. Experimental results are presented in Section 3 to validate our solutions with both synthetic and real-world datasets. Section 4 concludes this paper.

2. UNSUPERVISED METRIC LEARNING THROUGH CPD TRANSFORMATIONS (CPD-UML):

Many machine learning algorithms have certain assumption regarding the distribution of the data to be processed. K-means always produces clustering boundaries of hyperplanes, working best for the data set made of linearly separable groups. For data sets that are not linearly separable, even they are otherwise well-separable, K-means will fail to deliver. Nonlinearly displacing the data samples to make them linearly separable would provide a remedy, and learning such a transformation is the goal of our design. The application of such a smooth nonlinear transformation throughout feature space (either input space or kernel space) would change pairwise distances among samples, which is equivalent to assigning spatially varying metrics in different areas of the data space.

In our framework, the CPD model is chosen to perform the transformation. Originally designed for regulating points matching, CPD moves the points U towards the target V by estimating an optimal continuous velocity function v(x) : R d → R d under Tikhonov regularization framework:

T [v] = 1 2 n i=1 [v i -(u i + v(u i ))] 2 + 1 2 λ||Lv|| 2

, where n is the number of samples in the dataset, and d is the data dimension. L represents a linear differentiation operator, and λ is the regularization parameter. The regularization term in CPD is a Gaussian low-pass filter. The optimal solution v(x) to matching U and V can be written in the matrix format as (Myronenko & Song, 2010b) :

EQUATION

where Ψ (size d × n) is the weight matrix for the Gaussian kernel functions, g(x i , x j ) = e -(x i -x j ) 2 2σ 2

. σ is the width of the Gaussian filter, which controls the smoothness level of the deformation field.

2.1. FORMULATION:

OF CPD-UML Let X = {x i | x i ∈ R d , i = 1, • • • , n}

denote a dataset. K-means clustering aims to partition the samples into K groups S = {S 1 , S 2 , ..., S K }, through the minimization of the following objective function:

min S J = K c=1 xi∈Sc ||x i -µ c || 2 where µ c = xi∈Sc x i /n c (2)

S c is the set of data samples in the c-th cluster. n c is the number of data instances in cluster S c , and µ c is the mean of S c .

Allowing samples to be moved, we intend to learn a spatial transformation to improve the performance of K-means clustering by making groups more linearly separable, as well as by harnessing the updated distance measure under the transformed feature space. Let x i be the initial location of an instance. Through the motion in Eqn. ( 1), x i will be moved to a new position x 1 i :

EQUATION

With Eqn. (3), Eqn.

(2) can be reformulated as:

EQUATION

Now

S 1 = {S 1 1 , S 1 2 , ..., S 1 K } is a partition of the transformed dataset. µ 1 c

is the mean vector of the instances in cluster S 1 c . Our proposed CPD based unsupervised metric learning (CPD-UML) is designed to learn a spatial transformation Ψ and a clustering S 1 at the same time. Eqn. (4) can be reformulated into a matrix format through the following steps. First, put the input dataset into a d-by-n data matrix. Second, define a Gaussian kernel function matrix for the CPD deformation as:

G = G(X, X) = {G(x 1 , X), G(x 2 , X), ..., G(x n , X)} (5)

The size of G is n-by-n. Third, let p be a vector of dimension n c -by-1 with all elements equal to one, then the mean of the data instances within a cluster S 1 c can be written as µ 1 c = S 1 c p/n c (Zha et al., 2001) . With these three formulations, and let E be a permutation matrix, Eqn. (4) can be rewritten as:

min S 1 ,Ψ J = K c=1 ||S 1 c -µ 1 c p T || 2 F = K c=1 ||S 1 c -S 1 c pp T /n c || 2 F S 1 = EX 1 = E(X + ΨG(X, X)) (6)

where X 1 is the transformed data matrix. Since ||A|| 2 F = trace(A T A), Eqn. ( 6) can be written in the form of the trace operation:

EQUATION

As trace(AB) = trace(BA), and p T p = n c , the J in Eqn. ( 7) can be further reformulated as:

EQUATION

Similar to (Zha et al., 2001) , we define a n-by-k orthonormal matrix Y as the cluster indicator matrix:

Y = [Y 1 , Y 2 , ..., Y K ] where Y c = (0, ...0, p, 0...0) T / √ n c (9)

With X 1 = X + ΨG(X, X) and the cluster indicator matrix in Eqn. ( 9), Eqn. ( 8) can be written into the following: min

EQUATION

To reduce overfitting, we add the squared Frobenius norm λ||Ψ|| 2 F = λtrace(Ψ T Ψ), to penalize any non-smoothness in the estimated transformations. λ is a regularization parameter. Finally, our nonlinear CPD-UML solution is formulated as a trace minimization problem, parameterized by Y and Ψ:

min Y,Ψ J = trace((X + ΨG) T (X + ΨG)) -trace(Y T (X + ΨG) T (X + ΨG)Y ) + λtrace(Ψ T Ψ) (11)

2.2. OPTIMIZATION STRATEGY:

To search for the optimal solutions of Y and Ψ, an EM-like iterative minimization framework is adopted to update Y and Ψ alternatingly. The transformation matrix Ψ is initialized with all 0 elements, and the cluster indicator is initialized with a K-means clustering result of the input data samples.

Optimization for Y With Ψ fixed, Eqn. ( 11) reduces to a trace maximization problem:

EQUATION

)

Since Y is an orthonormal matrix: Y T Y = I K , the spectral relaxation technique (Zha et al., 2001) can be adopted to compute the optimal Y . The solution is based on Ky Fan matrix inequalities below:

Theorem. (Ky Fan) If A be a symmetric matrix with eigenvalues

{λ 1 ≥ λ 2 ≥ ... ≥ λ n }. Let the corresponding eigenvectors be {v 1 , v 2 , ...v n }, then max Y T Y =I K trace(Y T AY ) = K i=1 λ i

where the optimal Y * is given by

Y * = [v 1 , v 2 , ...v K ]Q for any arbitrary orthogonal matrix Q.

This spectral relaxation solution can be regarded as a manifold learning method that projects data samples from the original d-dimensional space to a new K-dimensional space. In our case, the A matrix in Ky Fan Theorem takes the form of X T X. In implementation, we first compute the K largest eigenvectors of X T X, and then apply the traditional K-means method, under the induced K-dimensional space, to compute the cluster assignments.

Optimization for Ψ With the Y generated from Eqn. (12), Eqn. (11) becomes a trace minimization problem w.r.t. Ψ:

EQUATION

Through a careful investigation of the gradient and Hessian matrix of Eqn. (13), we found the J could be proved to a smooth convex function, with its Hessian w.r.t. Ψ being positive definite (PD) everywhere. Therefore, the only stationary point of J, where the gradient is evaluated to 0, locates the global minimum, and provides the optimal Ψ * . The convexity proof is given as follows.

Convexity proof of J w.r.t. Ψ: Firstly, we update J in Eqn. ( 13), through several straightforward derivation steps (the details are given in Appendix A), to an equivalent form:

J = trace(X T X) + 2trace(G T Ψ T X) + trace(ΨGG T Ψ T ) -trace(Y T X T XY ) -2trace(Y T G T Ψ T XY ) -trace(ΨGY Y T G T Ψ T ) + λtrace(ΨΨ T ) (14)

The gradient of J w.r.t. Ψ can then be computed as:

EQUATION

To facilitate the convexity proof, we rewrite this gradient equation as:

EQUATION

N is a matrix of size d × n. M is a symmetric matrix of size n × n, which can be proved positive definite, based on the theorem in (Horn & Johnson, 2012):

Theorem. "Suppose that A ∈ M m,n and B ∈ M n,m with m ≤ n. Then BA has the same eigenvalues as AB, counting multiplicity, together with an additional n -m eigenvalues equal to 0."

We know Y T * Y = I K , whose eigenvalues are all 1s. Then, according to this Theorem, the eigenvalues of Y Y T are 1s (multiplicity is K), and 0 (multiplicity is n -K). In the matrix M of Eqn. ( 16), I -Y Y T is a positive semidefinite matrix as it is symmetric and its eigenvalues are either 0 or 1. G is also positive definite because it is a kernel (Gram) matrix with the Gaussian kernel.

With G being symmetric PD and λ setting to be a positive number in our algorithm, the matrix M is guaranteed to be a PD matrix.

Expanding the gradient formulated in Eqn. ( 16) to individual elements of Ψ, it can be further written as:

EQUATION

With Eqn. (17), Eqn. ( 16) can be resized into a vector of size d × n. Then, the Hessian matrix of J w.r.t. Ψ can be calculated as below: 

H =                              M 11 ,

                             It is clear that H is a symmetric matrix with size (d * n) × (d * n).

The diagonal of H is composed by d repeating M matrices. Let z be any non-zero column vector with size (d * n) × 1. To prove H is a PD matrix, we want to show that z T H z is always positive. To this end, we rewrite z as [ z 1 , z 2 , ..., z d ], where z i is the sub-column of z with size n × 1. Then z T H z can be computed as:

z T H z = [ z T 1 M, z T 2 M, ..., z T d M ] z = z T 1 M z1 + z T 2 M z2 + ... + z T d M z d (18)

As M has been proved to be a PD matrix, each item in Eqn. ( 18) is positive. Therefore, the summation z T H z is also positive. Since z is an arbitrary non-zero column vector, this shows H is PD. With the Hessian matrix H being PD everywhere, the objective function J is convex w.r.t. Ψ. As a result, the stationary point of J makes the unique global minimum solution Ψ * . Let Eqn. ( 15) equal to 0, we get

EQUATION

The matrix M on the left is proved PD, thus invertible. The optimal solution of Ψ is given as: 

EQUATION

2.4. KERNELIZATION OF CPD-UML:

So far, we developed and applied our proposed CPD-UML under input feature spaces. However, it can be further kernelized to improve the clustering performance for more complicated data. A kernel principal component analysis (KPCA) based framework (Zhang et al., 2010) is utilized in our work. After the input data instances are projected into kernel spaces introduced by KPCA, CPD-UML can be applied under the kernel spaces to learn both deformation field and clustering result, in the same manner as it is conducted under the original input spaces.

3. EXPERIMENTAL RESULTS:

We performed experiments on a synthetic dataset and six benchmark datasets. Comparisons are made with state-of-the-art unsupervised metric learning solutions.

3.1. EXPERIMENTS ON SYNTHETIC DATASET:

The two-moon synthetic dataset1 was tested in the first set of experiments. It consists of two classes with 100 examples in each class. (see Fig. 1 ). All the samples were treated as unlabeled samples in the experiments. Both linear and kernel versions of our CPD-UML were tested.

Linear version CPD-UML In this experiment, our CPD-UML was applied in deforming the data samples to achieve better separability under the input space. The effectiveness of our approach is demonstrated by comparing with the base algorithm K-means. Kernel version CPD-UML In this set of experiments, various RBF kernels were applied on the two-moon dataset to simulate linearly non-separable cases under kernel spaces. The clustering results of kernel K-means with different RBF kernels (width = 4, 8, 16, 32) are shown in Fig. 2 (a) -2 (d). Colors and decision boundaries stand for the same meaning as those in Fig. 1 . Obviously, the performance of kernel K-means was getting worse with sub-optimal kernels, as in 2 (b), 2 (c) and 2 (d). Searching for an optimal RBF kernel requires cross-validation among many candidates, which could result in a large number of iterations. This procedure can be greatly eased by our kernel CPD-UML. The CPD transformation under kernel spaces provides a supplementary force to the kernelization to further improve the data separability, the same as it performs under the input space. Fig. 2 (f) -2 (h) demonstrate the effectiveness of our CPD-UML. Same RBF kernels as in Fig. 2 (b) -2 (d) were used, but better clustering results were obtained. The ability to work with sub-optimal kernels should also be regarded as a computational advantage of our model.

3.2. EXPERIMENTS ON BENCHMARK DATASETS:

Experimental Setup In this section, we employ six benchmark datasets to evaluate the performance of our CPD-UML. They are five UCI datasets2 : Breast, Diabetes, Cars, Dermatology, E. Coli and the USPS_20 handwritten data. Their basic information is summarized in Appendix B.

Both linear and kernel versions of our proposed approach were tested. For linear version, K-means method was used as the baseline for comparison. In addition, three unsupervised metric learning solutions, AML (Ye et al., 2007) , RPCA-OM (Nie et al., 2014) and FME (Nie et al., 2010) were utilized as the competing solutions. For kernel version, the baseline algorithm is kernel K-means. NAML (Chen et al., 2007) , the kernel version of AML is adopted. Since RPCA-OM and FME do not have their kernel version, the same kernelization strategy in 2.4 was applied to kernelize these two solutions. RBF kernels were applied for all kernel solutions.

Each dataset was partitioned into seen and unseen data randomly. Optimal cluster centers and parameters are determined by the seen data. Clustering performance is evaluated via the unseen data, which are labeled directly based on their distances away from the cluster centers. Similar setups have been used in (Nie et al., 2011; Huang et al., 2015) . In the experiments, we performed 3-fold cross validation, in which two folds were used as seen data and one fold as unseen data. In the competing solutions, the hyper-parameters were searched within the same range as in their publications. In our proposed approach, the regularization parameter λ and smooth parameter σ were searched from {10 0 ∼ 10 10 } and {2 0 ∼ 2 10 }, respectively. The RBF kernel width for all kernel methods is chosen from {2 -5 ∼ 2 10 }. Since the performance of tested methods depends on the initialization clusters, the clustering result of K-means was applied as the initialization clusters for all the competing solutions in each run. The performance of each algorithm was calculated over 20 runs.

Results:

We measured the performance using the ground truth provided in all six benchmark datasets. Three standard performance metrics were calculated: accuracy, normalized mutual information and purity. To better compare the tested methods in statistic, we conducted a Student's t-test with a p-value 0.05 between each pair of solutions for each dataset. The solutions were ranked using a scoring schema from (Wang et al., 2012) . Compared with other methods, an algorithm scores 1 if it performs significantly better than one opponent in statistic; 0.5 if there is no significant difference, and 0 if it is worse.

Tables 1, 2 and 3 summarize the clustering performance and ranking scores. The best performance is identified in Boldface for each dataset. It is evident that our CPD-UML outperforms other competing solutions in all three standard measurements with significant margins. Highest ranking scores in the performance tables are all achieved by our kernel version approach. In addition, significant improvements have been obtained by our proposed approach compared with the baseline algorithm K-means and kernel K-means. It is also noteworthy that, the linear CPD-UML achieved comparable results with the other competing methods using RBF kernels, which further demonstrates the effectiveness of our nonlinear feature space transformation.

4. CONCLUSIONS:

The proposed CPD-UML model learns a nonlinear metric and the clusters for the given data simultaneously. The nonlinear metric is achieved by a globally smooth nonlinear transformation, which improves the separability of given data during clustering. CPD is used as the transformation model because of its capability in deforming feature space in sophisticated yet smooth manner. Evaluations on synthetic and benchmark datasets demonstrate the effectiveness of our approach. Applying the proposed approach to other computer vision and machine learning problems are in the direction of our future research. A APPENDIX A

In section 2.2, we optimize the object function J in Eqn. ( 13) by computing its gradient and Hessian matrix w.r.t. Ψ. The Hessian matrix can be proved to be positive definite. The derivations from Eqn. (13) to Eqn. ( 14) is presented in this appendix. Eqn. ( 13) starts as: min Ψ J = trace((X + ΨG) T (X + ΨG))trace(Y T (X + ΨG) T (X + ΨG)Y ) + λtrace(Ψ T Ψ)

It can be expanded to:

EQUATION

As trace(A) = trace(A T ) for any matrix A, we get trace(X T ΨG) = trace(G T Ψ T X) and trace(Y T X T ΨGY ) = trace(Y T G T Ψ T XY ). With these two equations, Eqn. ( 21) becomes:

EQUATION

Through some simple matrix manipulations, as well as based on the fact that trace(AB) = trace(BA) for any matrix A and B, Eqn. ( 22) can be updated to Eqn. ( 14 

B APPENDIX B:

In section 3.2, we employ six benchmark datasets to evaluate the performance of our CPD-UML. They are five UCI datasets: Breast, Diabetes, Cars, Dermatology, E. coli and the USPS_20 handwritten data. Their basic information is summarized in Table 4 . 

:

http://manifold.cs.uchicago.edu/manifold_regularization/data.html

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

Figures and Tables:

M 12 , ..., M 1n , 0, ................................................, 0 M 21 , M 22 , ..., M 2n , 0, ................................................, 0 . . M n1 , M n2 , ..., M nn , 0, ................................................, 0 0, ...................., 0, M 11 , M 12 , ..., M 1n , 0, ...................., 0 0, ...................., 0, M 21 , M 22 , ..., M 2n , 0, ...................., 0 . . 0, ...................., 0, M n1 , M n2 , ..., M nn , 0, ..................., 0 • • • • • • 0, ................................................, 0, M 11 , M 12 , ..., M 1n 0, ................................................, 0, M 21 , M 22 , ..., M 2n . . 0, ................................................, 0, M n1 , M n2 , ..., M nn

Figure 1: (a) clustering result of K-means; (b) clustering result of CPD-UML; (c) and (d) show the deformation field of (b). Color figures are best viewed on screen. The clustering results of K-means and CPD-UML are shown in Fig. 1 (a) and 1 (b) respectively. The sample labels are distinguished using blue and red colors. The clustering results are shown using the decision boundary. It is obvious that K-means cannot cluster the two-moon data well due to the data's non-separability under the input space. Our CPD-UML, on the contrary, achieves a 99% clustering accuracy by making the data samples linearly separable via space transformations. The deformation field of Fig. 1 (b) in the input space is shown in Fig. 1 (c) and (d). It is evident that our nonlinear metric learning model can deform feature spaces in a sophisticated yet smooth way to improve the data separability.

Figure 2: First row: clustering results of kernel K-means with RBF kernels width = 4, 8, 16 and 32. Second row: results of kernel version CPD-UML with RBF kernels width = 4, 8, 16 and 32.

):J = trace(X T X) + 2trace(G T Ψ T X) + trace(ΨGG T Ψ T )trace(Y T X T XY ) -2trace(Y T G T Ψ T XY )trace(ΨGY Y T G T Ψ T ) + λtrace(ΨΨ T )

Accuracy

Table content: <table><tr><td>Algorithms</td><td>Breast</td><td>Diabetes</td><td>Cars</td><td>Dermatology</td><td>E. Coli</td><td>USPS20</td><td>Total Score</td></tr><tr><td>K-means</td><td>96.39 ± 0.34 (2.5)</td><td>96.42 ± 0.12 (3.5)</td><td>42.67 ± 0.35 (0.0)</td><td>69.64 ± 7.73 (4.5)</td><td>57.11 ± 3.23 (6.0)</td><td>62.29 ± 3.12 (3.0)</td><td>19.5</td></tr><tr><td>AML</td><td>96.34 ± 0.35 (1.5)</td><td>96.49 ± 0.09 (4.5)</td><td>43.67 ± 0.50 (1.5)</td><td>63.17 ± 3.07 (0.0)</td><td>58.87 ± 3.27 (6.0)</td><td>64.36 ± 3.93 (4.0)</td><td>17.5</td></tr><tr><td>RPCA-OM</td><td>96.54 ± 0.49 (3.5)</td><td>96.71 ± 0.31 (6.0)</td><td>43.81 ± 0.78 (1.5)</td><td>71.15 ± 4.50 (5.0)</td><td>58.55 ± 3.28 (6.0)</td><td>62.64 ± 3.87 (3.5)</td><td>25.5</td></tr><tr><td>FME</td><td>96.36 ± 0.30 (1.5)</td><td>96.57 ± 0.35 (4.5)</td><td>48.86 ± 2.11 (4.5)</td><td>77.72 ± 3.68 (8.0)</td><td>58.59 ± 3.54 (6.0)</td><td>66.27 ± 4.09 (6.0)</td><td>30.5</td></tr><tr><td>CPD-UML</td><td>97.06 ± 0.44 (8.5)</td><td>97.52 ± 0.19 (8.0)</td><td>45.33 ± 0.73 (3.0)</td><td>68.67 ± 7.48 (4.0)</td><td>57.01 ± 3.67 (5.5)</td><td>64.78 ± 3.64 (4.5)</td><td>33.5</td></tr><tr><td>Kernel K-means</td><td>96.56 ± 0.29 (4.0)</td><td>95.57 ± 0.13 (1.0)</td><td>61.71 ± 0.08 (6.0)</td><td>64.98 ± 2.02 (1.5)</td><td>55.04 ± 2.49 (3.0)</td><td>56.14 ± 4.98 (0.5)</td><td>16.0</td></tr><tr><td>NAML</td><td>96.56 ± 0.30 (4.0)</td><td>95.57 ± 0.15 (1.0)</td><td>62.13 ± 0.54 (7.0)</td><td>66.60 ± 2.01 (3.5)</td><td>49.62 ± 2.82 (0.5)</td><td>57.76 ± 3.82 (0.5)</td><td>16.5</td></tr><tr><td>r-RPCA-OM</td><td>96.76 ± 0.27 (6.5)</td><td>95.57 ± 0.14 (1.0)</td><td>49.55 ± 2.53 (4.5)</td><td>65.69 ± 3.75 (2.5)</td><td>52.72 ± 5.26 (2.0)</td><td>67.44 ± 4.29 (7.5)</td><td>24.0</td></tr><tr><td>r-FME</td><td>96.73 ± 0.25 (5.0)</td><td>96.79 ± 0.14 (6.5)</td><td>63.38 ± 1.51 (8.5)</td><td>79.45 ± 3.86 (8.0)</td><td>50.78 ± 2.53 (1.0)</td><td>68.13 ± 5.47 (7.5))</td><td>36.5</td></tr><tr><td>r-CPD-UML</td><td>96.95 ± 0.41 (8.0)</td><td colspan="5">97.75 ± 0.10 63.77 ± 1.52 80.37 ± 4.80 63.02 ± 2.74 68.58 ± 2.49 (9.0) (8.5) (8.0) (9.0) (8.0)</td><td>50.5</td></tr></table>

Normalized Mutual Information

Table content: <table><tr><td>Algorithms</td><td>Breast</td><td>Diabetes</td><td>Cars</td><td>Dermatology</td><td>E. Coli</td><td>USPS20</td><td>Total Score</td></tr><tr><td>K-means</td><td>76.10 ± 1.73 (2.5)</td><td>76.31 ± 0.63 (1.0)</td><td>18.17 ± 0.50 (5.5)</td><td>80.91 ± 4.96 (4.0)</td><td>56.77 ± 2.14 (7.5)</td><td>61.73 ± 1.49 (3.0)</td><td>23.5</td></tr><tr><td>AML</td><td>75.83 ± 1.80 (1.5)</td><td>76.58 ± 0.11 (1.5)</td><td>20.53 ± 0.77 (8.5)</td><td>79.15 ± 2.80 (3.0)</td><td>57.81 ± 2.07 (7.5)</td><td>62.51 ± 3.25 (3.5)</td><td>25.5</td></tr><tr><td>RPCA-OM</td><td>77.07 ± 2.52 (3.5)</td><td>77.88 ± 1.64 (5.5)</td><td>20.04 ± 0.64 (7.5)</td><td>82.27 ± 4.29 (6.0)</td><td>51.22 ± 2.42 (4.0)</td><td>60.78 ± 2.40 (2.5)</td><td>29.0</td></tr><tr><td>FME</td><td>75.93 ± 1.50 (1.5)</td><td>77.01 ± 1.77 (3.0)</td><td>19.45 ± 2.44 (8.0)</td><td>84.75 ± 3.58 (8.0)</td><td>56.73 ± 2.76 (7.5)</td><td>64.01 ± 2.73 (6.0)</td><td>34.0</td></tr><tr><td>CPD-UML</td><td>79.63 ± 2.35 (8.5)</td><td>83.31 ± 0.64 (8.0)</td><td>18.19 ± 0.51 (5.5)</td><td>79.46 ± 5.09 (4.0)</td><td>46.98 ± 8.29 (2.0)</td><td>61.12 ± 3.32 (2.5)</td><td>30.5</td></tr><tr><td>Kernel K-means</td><td>77.01 ± 1.58 (4.0)</td><td>77.06 ± 0.10 (3.5)</td><td>8.50 ± 0.05 (3.0)</td><td>74.65 ± 3.62 (0.0)</td><td>51.04 ± 1.76 (4.0)</td><td>59.48 ± 3.05 (1.5)</td><td>16.0</td></tr><tr><td>NAML</td><td>77.01 ± 1.58 (4.0)</td><td>77.06 ± 0.11 (3.5)</td><td>1.50 ± 0.95 (0.0)</td><td>79.86 ± 1.43 (3.0)</td><td>45.66 ± 4.03 (1.5)</td><td>60.87 ± 3.11 (2.5)</td><td>14.5</td></tr><tr><td>r-RPCA-OM</td><td>78.19 ± 1.50 (6.5)</td><td>77.08 ± 1.47 (3.5)</td><td>3.30 ± 1.90 (1.0)</td><td>79.84 ± 2.66 (3.5)</td><td>18.36 ± 1.85 (0.0)</td><td>66.12 ± 2.66 (8.0)</td><td>22.5</td></tr><tr><td>r-FME</td><td>77.95 ± 1.37 (5.0)</td><td>78.32 ± 0.79 (6.5)</td><td>6.38 ± 0.62 (2.0)</td><td>85.96 ± 3.17 (8.5)</td><td>49.74 ± 2.89 (3.5)</td><td>67.02 ± 3.76 (8.0)</td><td>33.5</td></tr><tr><td>r-CPD-UML</td><td>79.25 ± 2.43 (8.0)</td><td>85.76 ± 0.81 (9.0)</td><td>10.12 ± 2.26 (4.0)</td><td>81.46 ± 2.65 (5.0)</td><td>57.85 ± 2.18 (7.5)</td><td>65.34 ± 2.01 (7.5)</td><td>41.0</td></tr></table>

Purity Changshui Zhang, Feiping Nie, and Shiming Xiang. A general kernelization framework for learning algorithms based on kernel pca. Neurocomputing, 73(4):959-967, 2010. Pin Zhang, Bibo Shi, Charles D Smith, and Jundong Liu. Nonlinear metric learning for semi-supervised learning via coherent point drifting. In ICMLA, pp. 314-319. IEEE, 2016.

Table content: <table><tr><td>Algorithms</td><td>Breast</td><td>Diabetes</td><td>Cars</td><td>Dermatology</td><td>E. Coli</td><td>USPS20</td><td>Total Score</td></tr><tr><td>K-means</td><td>96.39 ± 0.34 (2.5)</td><td>96.42 ± 0.12 (3.5)</td><td>62.85 ± 0.36 (4.5)</td><td>81.36 ± 4.45 (4.0)</td><td>81.17 ± 1.58 (7.5)</td><td>69.78 ± 2.54 (3.5)</td><td>25.5</td></tr><tr><td>AML</td><td>96.34 ± 0.35 (1.5)</td><td>96.49 ± 0.09 (4.5)</td><td>62.91 ± 0.38 (4.5)</td><td>78.94 ± 1.81 (2.5)</td><td>81.39 ± 1.42 (7.5)</td><td>71.08 ± 4.32 (4.5)</td><td>25.0</td></tr><tr><td>RPCA-OM</td><td>96.54 ± 0.49 (3.5)</td><td>96.71 ± 0.31 (6.0)</td><td>63.85 ± 0.80 (7.0)</td><td>82.64 ± 3.85 (5.0)</td><td>74.50 ± 1.85 (2.5)</td><td>69.60 ± 3.58 (3.5)</td><td>27.5</td></tr><tr><td>FME</td><td>96.36 ± 0.30 (1.5)</td><td>96.57 ± 0.35 (4.5)</td><td>63.86 ± 1.07 (7.0)</td><td>85.27 ± 3.20 (8.0)</td><td>80.43 ± 2.11 (7.0)</td><td>72.68 ± 3.37 (7.0)</td><td>35.0</td></tr><tr><td>CPD-UML</td><td>97.06 ± 0.44 (8.5)</td><td>97.52 ± 0.19 (8.0)</td><td>63.10 ± 0.49 (4.5)</td><td>81.02 ± 4.45 (3.5)</td><td>74.88 ± 5.82 (3.5)</td><td>69.80 ± 3.61 (3.5)</td><td>31.5</td></tr><tr><td>Kernel K-means</td><td>96.56 ± 0.29 (4.0)</td><td>95.57 ± 0.13 (1.0)</td><td>62.16 ± 0.05 (1.0)</td><td>76.80 ± 1.94 (0.0)</td><td>76.03 ± 1.57 (4.0)</td><td>65.29 ± 4.29 (0.5)</td><td>10.5</td></tr><tr><td>NAML</td><td>96.56 ± 0.30 (4.0)</td><td>95.57 ± 0.15 (1.0)</td><td>62.21 ± 0.32 (1.0)</td><td>79.37 ± 1.02 (3.0)</td><td>70.90 ± 3.93 (1.0)</td><td>66.69 ± 3.38 (0.5)</td><td>10.5</td></tr><tr><td>r-RPCA-OM</td><td>96.76 ± 0.27 (6.5)</td><td>95.57 ± 0.14 (1.0)</td><td>62.29 ± 0.41 (1.0)</td><td>79.26 ± 2.16 (3.0)</td><td>52.84 ± 5.29 (0.0)</td><td>73.46 ± 2.95 (7.5)</td><td>19.0</td></tr><tr><td>r-FME</td><td>96.73 ± 0.25 (5.0)</td><td>96.79 ± 0.14 (6.5)</td><td>63.38 ± 1.76 (5.5)</td><td>85.44 ± 3.16 (8.0)</td><td>76.01 ± 2.62 (4.0)</td><td>72.77 ± 3.42 (7.0)</td><td>36.0</td></tr><tr><td>r-CPD-UML</td><td>96.95 ± 0.41 (8.0)</td><td colspan="5">97.75 ± 0.10 64.86 ± 0.85 85.59 ± 2.56 82.09 ± 1.74 74.44 ± 2.14 (9.0) (9.0) (8.0) (8.0) (7.5)</td><td>49.5</td></tr></table>

Six benchmark datasets used in experiments. Columns show the name, numbers of samples, attributes and classes of each dataset.

Table content: <table><tr><td>Datasets</td><td colspan="3"># Samples # Attributes # Classes</td></tr><tr><td>Breast</td><td>683</td><td>10</td><td>2</td></tr><tr><td>Diabetes</td><td>768</td><td>8</td><td>2</td></tr><tr><td>Cars</td><td>392</td><td>8</td><td>3</td></tr><tr><td>Dermatology</td><td>366</td><td>34</td><td>6</td></tr><tr><td>Ecoli</td><td>336</td><td>343</td><td>8</td></tr><tr><td>USPS20</td><td>1854</td><td>256</td><td>10</td></tr></table>

Peer review (iclr2018):
 This paper presents a scheme for unsupervised metric learning using coherent point drifting (CPD)-- the core idea is to learn a parametric model of CPD that shifts the input points such that the shifted points lead to better clustering in a K-Means setup. Following the work of Myronenko & Song, 2010, this paper uses a linear parametric model for the drift (in CPD) after mapping the input points to a kernel feature space using an RBF kernel. The CPD model is directly used within the KMeans objective -- the drift parameter matrix and the KMeans cluster assignment matrix are jointly learned using block-coordinate descent (BCD). The paper uses some interesting properties of the CPD model to derive an efficient optimization solver for the BCD subproblems. Experiments are provided on UCI datasets and demonstrate some promise. Pros: 1) The idea of using CPD for unsupervised metric learning is quite interesting 2) The exploration into the convexity of the CPD parameter learning -- although straightforward -- is also perhaps interesting. 3) The experiments show some promise. Cons: 1) Lacking motivation/Intuition The main motivation for the approach, as far as I understand, is to learn cluster boundaries for non-linear data -- where K-Means fails. However, it is unclear to me why would one need to use K-Means for non-linear data, why not use kernelized kmeans? The proposed CPD model also is essentially learning a linear transformation of the kernelized feature space. So in contrast to kernelized kmeans, what is the advantage of the proposed framework? I see there is an improvement in performance compared to kernelized kmeans, however, intuitively I do not see how that improvement comes from? Perhaps providing some specific examples/scenarios or graphic illustrations will help appreciate the method. 2) Novelty/Significance I think the novelty of this paper is perhaps marginal. The main idea is to directly use CPD from a prior work in a KMeans setup. There are a few parameters to be estimated in the joint learning objective, for which a block-coordinate descent strategy is proposed. The derivations are perhaps straightforward. As noted above, it is not clear what is the significance of this combination or how does it improve performance. As far as CPD goes, it looks to me that the performance depends heavily on the choice of the Gaussian RBF bandwidth parameter, and it is not clear to me how such a parameter can be selected in a unsupervised setting, when class labels are not available for cross-validation. The paper does not provide any intuitions on this front. 3) Technical details. There are a few important details that I do not quite follow in the paper. a) The CPD is originally designed for the point matching problem, and its parametric form (.Psi) is derived using a different a Tikhonov regularized regression model as described just above (1). The current paper directly uses this parametric form in a KMeans setup and solve the resultant problem jointly for the CPD parameter and the clustering assignment. However, it is not clear to me how the paper could use the optimal parametric form for Tikhonov regression as the optimum for the clustering problem. Ideally, I would think when formulating the joint optimization for the clustering problem, the optimal functional v(x) should also be learned/derived for the clustering problem, or some proof should be provided showing the functionals are the same. Without this, I am not convinced that the proposed formulation indeed learns the optimum drifts and the clusters jointly. b) The subproblem on Y (the assignment matrix) looks like a standard SVD objective. It is not clear why would it be necessary to resort to Ky Fan*s theorem for its optimal solution. c) The paper talks about manifold embedding in the abstract and in Sec. 2.2. However, it appears to be a straightforward dimensionality reduction (PCA) of data. If not, what is the precise manifold that is described here? d) Eq. 9, the definition of Y_c is incorrect and unclear. p is defined as a vector of ones, earlier. e) Although the assignment matrix Y has orthogonal columns, it is a binary matrix. If it is approximated by an orthonormal frame, how do you reduce it to a binary matrix? Does taking the largest values in each column suffice -- it does not look like so. However, in the paper, Y is relaxed to an orthonormal frame, which is estimated using PCA, the data points are then projected onto this low-dimensional subspace, and then k-means applied to get the Y matrix. The provided math does not support any of these steps. Thus, the technical exposition is imprecise and the solutions appear rather heuristic. f) The kernelized variant of the proposed scheme, described in Sec. 2.4 is missing important details. How precisely is the kernelization done? How is CPD extended to that setup and what would be the Gaussian kernel G in that case, and what does .Psi signify? g) Figure 2, it seems that kernel kmeans and the proposed CPD-UML show similar cluster boundaries for low-kernel widths. Why are the high kernel widths beneficial? 4) Experiments There is some improvement of the proposed method -- however overall, the improvements are marginal. The discussion is missing any analysis of the results. Why it works at times, how well it improves on kernelized kmeans, and why? What is the advantage over other competitive schemes, etc. In summary, while there is a minor novelty in connecting two separate ideas (CPD and UML) into a joint UML setup, the paper lacks sufficient motivations for proposing this setup (in contrast to say kernelized kmeans), the technical details are unconvincing, and the experiments lack sufficient details or analysis. Thus, I do not think this paper is ready to be accepted in its current form.