Year: 2021

Abstract:
Similarity-based clustering methods separate data into clusters according to the pairwise similarity between the data, and the pairwise similarity is crucial for their performance. In this paper, we propose Clustering by Discriminative Similarity (CDS), a novel method which learns discriminative similarity for data clustering. CDS learns an unsupervised similarity-based classifier from each data partition, and searches for the optimal partition of the data by minimizing the generalization error of the learnt classifiers associated with the data partitions. By generalization analysis via Rademacher complexity, the generalization error bound for the unsupervised similarity-based classifier is expressed as the sum of discriminative similarity between the data from different classes. It is proved that the derived discriminative similarity can also be induced by the integrated squared error bound for kernel density classification. In order to evaluate the performance of the proposed discriminative similarity, we propose a new clustering method using a kernel as the similarity function, CDS via unsupervised kernel classification (CDSK), with its effectiveness demonstrated by experimental results.

text: Similarity-based clustering methods separate data into clusters according to the pairwise similarity between the data, and the pairwise similarity is crucial for their performance. In this paper, we propose Clustering by Discriminative Similarity (CDS), a novel method which learns discriminative similarity for data clustering. CDS learns an unsupervised similarity-based classifier from each data partition, and searches for the optimal partition of the data by minimizing the generalization error of the learnt classifiers associated with the data partitions. By generalization analysis via Rademacher complexity, the generalization error bound for the unsupervised similarity-based classifier is expressed as the sum of discriminative similarity between the data from different classes. It is proved that the derived discriminative similarity can also be induced by the integrated squared error bound for kernel density classification. In order to evaluate the performance of the proposed discriminative similarity, we propose a new clustering method using a kernel as the similarity function, CDS via unsupervised kernel classification (CDSK), with its effectiveness demonstrated by experimental results.

heading: 1 INTRODUCTION
text: Similarity-based clustering methods segment the data based on the similarity measure between the data points, such as spectral clustering (Ng et al., 2001), pairwise clustering method (Shental et al., 2003), K-means (Hartigan & Wong, 1979), and kernel K-means (Schölkopf et al., 1998). The success of similarity-based clustering highly depends on the underlying pairwise similarity over the data, which in most cases are constructed empirically, e.g. by Gaussian kernel or the K-NearestNeighbor (KNN) graph. In this paper, we model data clustering as a multiclass classification problem and seek for the data partition where the associated classifier, trained on cluster labels, can have low generalization error. Therefore, it is natural to formulate data clustering problem as a problem of training unsupervised classifiers: a classifier can be trained upon each candidate partition of the data, and the quality of the data partition can be evaluated by the performance of the trained classifier. Such classifier trained on a hypothetical labeling associated with a data partition is termed an unsupervised classifier.
We present Clustering by Discriminative Similarity (CDS), wherein discriminative similarity is derived by the generalization error bound for an unsupervised similarity-based classifier. CDS is based on a novel framework of discriminative clustering by unsupervised classification wherein an unsupervised classifier is learnt from unlabeled data and the preferred hypothetical labeling should minimize the generalization error bound for the learnt classifier. When the popular Support Vector Machines (SVMs) is used in this framework, unsupervised SVM (Xu et al., 2004) can be deduced. In this paper, a similarity-based classifier motivated by similarity learning (Balcan et al., 2008; Cortes et al., 2013), is used as the unsupervised classifier. By generalization analysis via Rademacher complexity, the generalization error bound for the unsupervised similarity-based classifier is expressed as sum of pairwise similarity between the data from different classes. Such pairwise similarity, parameterized by the weights of the unsupervised similarity-based classifier, serves as the discriminative similarity. The term “discriminative similarity” emphasizes the fact that the similarity is learnt so as to improve the discriminative capability of a certain classifier such as the aforementioned unsupervised similarity-based classifier.

heading: 1.1 CONTRIBUTIONS AND MAIN RESULTS
text: Firstly, we present Clustering by Discriminative Similarity (CDS) where discriminative similarity is induced by the generalization error bound for unsupervised similarity-based classifier on unlabeled data. The generalization bound for such similarity-based classifier is of independent interest, which is among the few results of generalization bounds for classification using general similarity functions (Section B.1 of the appdendix). When the general similarity function is set to a Positive SemiDefinite (PSD) kernel, the derived discriminative similarity between two data points xi,xj is SKij = 2(αi + αj − λαiαj)K(xi − xj), where K can be an arbitrary PSD kernel and αi is the kernel weight associated with xi. With theoretical and empirical study, we argue that SKij should be used for data clustering instead of the conventional kernel similarity corresponding to uniform kernel weights. In the case of binary classification, we prove that the derived discriminative similarity SKij has the same form as the similarity induced by the integrated squared error bound for kernel density classification (Section A of the appendix). Such connection suggests that there exists informationtheoretic measure which is implicitly equivalent to our CDS framework for unsupervised learning, and our CDS framework is well grounded for learning similarity from unlabeled data.
Secondly, based on our CDS model, we develop a clustering algorithm termed Clustering by Discriminative Similarity via unsupervised Kernel classification (CDSK) in Section 5. CDSK uses a PSD kernel as the similarity function, and outperforms competing clustering algorithms, including nonparametric discriminative similarity based clustering methods and similarity graph based clustering methods, demonstrating the effectiveness of CDSK. When the kernel weights {αi} are uniform, CDSK is equivalent to kernel K-Means (Schölkopf et al., 1998). CDSK is more flexible by learning adaptive kernel weights associated with different data points.

heading: 1.2 CONNECTION TO RELATED WORKS
text: Our CDS model is related to a class of discriminative clustering methods which classify unlabeled data by various measures on discriminative unsupervised classifiers, and the measures include generalization error (Xu et al., 2004) or the entropy of the posterior distribution of the label (Gomes et al., 2010). Discriminative clustering methods (Xu et al., 2004) predict the labels of unlabeled data by minimizing the generalization error bound for the unsupervised classifier with respect to the hypothetical labeling. Unsupervised SVM is proposed in Xu et al. (2004) which learns a binary classifier to partition unlabeled data with the maximum margin between different clusters. The theoretical properties of unsupervised SVM are further analyzed in Karnin et al. (2012). Kernel logistic regression classifier is employed in Gomes et al. (2010), and it uses the entropy of the posterior distribution of the class label by the classifier to measure the quality of the hypothetical labeling. CDS model performs discriminative clustering based on a novel unsupervised classification framework by considering similarity-based or kernel classifiers which are important classification methods in the supervised learning literature. In contrasts with kernel similarity with uniform weights, the induced discriminative similarity with learnable weights enhances its capability to represent complex interconnection between data. The generalization analysis for CDS is primarily based on distribution free Rademacher complexity. While Yang et al. (2014a) propose nonparametric discriminative similarity for clustering, the nonparametric similarity requires probability density estimation which is difficult for high-dimensional data, and the fixed nonparametric similarity is not adaptive to complicated data distribution.
The paper is organized as follows. We introduce the problem setup of Clustering by Discriminative Similarity in Section 3. We then derive the generalization error bound for the unsupervised similarity-based classifier for CDS in Section 4 where the proposed discriminative similarity is induced by the error bound. The application of CDS to data clustering is shown in Section 5. Throughout this paper, the term kernel stands for the PSD kernel if no special notes are made.

heading: 2 SIGNIFICANCE OF CDSK OVER EXISTING DISCRIMINATIVE AND SIMILARITY-BASED CLUSTERING METHODS
text: Effective data similarity highly depends on the underlying probabilistic distribution and geometric structure of the data, and these two characteristics leads to “data-driven” similarity, such as (Zhu et al., 2014; Bicego et al., 2021; Ng et al., 2001; Shental et al., 2003; Hartigan & Wong, 1979;
Schölkopf et al., 1998) and similarity based on geometric structure of the data, such as the subspace structure (Sparse Subspace Clustering, or SSC in (Elhamifar & Vidal, 2013)). Note that the sparse graph method, ℓ1-Graph (Yan & Wang, 2009), has the same formulation as SSC. Most existing clustering methods based on data-driven or geometric structure-driven similarity suffer from a common deficiency, that is, the similarity is not explicitly optimized for the purpose of separating underlying clusters. In particular, the Random Forest-based similarity (Zhu et al., 2014; Bicego et al., 2021) is extracted from features in decision trees. Previous works about subspace-based similarity (Yan & Wang, 2009; Elhamifar & Vidal, 2013) try to make sure that only data points lying on or close to the same subspace have nonzero similarity, so that data points from the same subspace can form a cluster. However, it is not guaranteed that features in the decision trees are discriminative enough to separate clusters, because the candidate data partition (or candidate cluster labels) do not participate in the feature or similarity extraction process. Note that synthetically generated negative class are suggested in (Zhu et al., 2014; Bicego et al., 2021) to train unsupervised random forest, however, the synthetic labels are not for the original data. Moreover, it is well known that the existing subspace learning methods only obtain reliable subspace-based similarity with restrictive geometric assumptions on the data and the underlying subspaces, such as large principal angle between intersecting subspaces (Soltanolkotabi & Candes, 2012; Elhamifar & Vidal, 2013).
Therefore, it is particularly important to derive similarity for clustering which meets two requirements: (1) discriminative measure with information such as cluster partition is used to derive such similarity so as to achieve compelling clustering performance; (2) it requires less restrictive assumptions on the geometric structure of the data than current geometric structure-based similarity learning methods, such as subspace clustering (Yan & Wang, 2009; Elhamifar & Vidal, 2013).
Significance. The proposed discriminative similarity of this paper meets these two requirements. First, the discriminative similarity is derived by the generalization error bound associated with candidate cluster labeling, and minimizing the objective function of our optimization problem for clustering renders a joint optimization of discriminative similarity and candidate cluster labeling in a way such that the similarity-based classifier has small generalization error bound. Second, our framework only assumes a mild classification model in Definition 3.1, which only requires an unknown joint distribution over data and its labels. In this way, the restrictive geometric assumptions are avoided in our method. Compared to the existing discriminative clustering methods, such as MMC (Xu et al., 2004), BMMC (Chen et al., 2014), RIM (Gomes et al., 2010), and the other discriminative clustering methods such as (Huang et al., 2015; Nguyen et al., 2017), the optimization problem of CDSK with discriminative similarity-based formulation is much easier to solve and it enjoys convexity and efficiency in each iteration of coordinate descent described in Algorithm 1. In particular, as mentioned in Section D of the appendix, the first step (11) of each iteration can be solved by efficient SVD or other randomized large-scale SVD methods, and the second step (12) of each iteration can be solved by efficient SMO (Platt, 1998). Moreover, the optimization problems in these two steps are either convex or having closed-form solution. In contrast, MMC requires expensive semidefinite programming. RIM has to solve a nonconvex optimization problem and its formulation does not guarantee that the trained multi-class kernelized logistic regression has low classification error on candidate labeling, which explains why it has inferior performance compared to our method. The discriminative Extreme Learning Machine (Huang et al., 2015) trains ELM using labels produced by a simple clustering method such as K-means, and the potentially poor cluster labels by the simple clustering method can easily result in unsatisfactory performance of this method. The discriminative Bayesian nonparametric clustering (Nguyen et al., 2017) and BMMC (Chen et al., 2014) require extra efforts of sampling hidden variables and tuning hyperparameters to generate the desirable number of clusters (or model selection), which could reduce the effect of discriminative measures used in these Bayesian nonparametric methods.

heading: 3 PROBLEM SETUP
text: We introduce the problem setup of the formulation of clustering by unsupervised classification. Given unlabeled data {xl}nl=1 ⊂ Rd, clustering is equivalent to searching for the hypothetical labeling which is optimal in some sense. Each hypothetical labeling corresponds to a candidate data partition. Figure 1 illustrates four binary hypothetical labelings which correspond to four partitions of the data, and the data is divided into two clusters by each hypothetical labeling.
The discriminative clustering literature (Xu et al., 2004; Gomes et al., 2010) has demonstrated the potential of multi-class classification for clustering problem. Inspired by the natural connection between clustering and classification, we proposes the framework of Clustering by Unsupervised Classification which models clustering problem as a multi-class classification problem. A classifier is learnt from unlabeled data with a hypothetical labeling, which is associated with a candidate partition of the unlabeled data. The optimal hypothetical labeling is supposed to be the one such that its associated classifier has the minimum generalization error bound. To study the generalization bound for the classifier learnt from hypothetical labeling, the concept of classification model is needed. Given unlabeled data {xl}nl=1, a classification model MY is constructed for any hypothetical labeling Y = {yl}nl=1 as follows.
Definition 3.1. The classification model corresponding to the hypothetical labeling Y = {yl}nl=1 is defined as MY = (S, F ). S = {xl, yl}nl=1 are the labeled data by the hypothetical labeling Y , and S are assumed to be i.i.d. samples drawn from the some unknown joint distribution PXY , where (X,Y ) is a random couple, X ∈ X ⊆ Rd represents the data in some compact domain X , and Y ∈ {1, 2, ..., c} is the class label of X , c is the number of classes. F is a classifier trained on S. The generalization error of the classification model MY is defined as the generalization error of the classifier F in MY .
The basic assumption of CDS is that the optimal hypothetical labeling minimizes the generalization error bound for the classification model. With f being different classifiers, different discriminative clustering models can be derived. When SVMs is used as the classifier F in the above discriminative model, unsupervised SVM (Xu et al., 2004) is obtained.
In Balcan et al. (2008), the authors proposes a classification method using general similarity functions. The classification rule measures the similarity of the test data to each class, and then assigns the test data to the class such that the weighed average of the similarity between the test data and the training data belonging to that class is maximized over all the classes. Inspired by this classification method, we now consider using a general symmetric and continuous function S : X × X → [0, 1] as the similarity function in our CDS model. We propose the following hypothesis,
hS(x, y) = ∑
i : yi=y
αiS(x,xi). (1)
In the next section, we derive generalization bound for the unsupervised similarity-based classifier based on the above hypothesis, and such generalization bound leads to discriminative similarities for data clustering. When S is a PSD kernel, minimizing the generalization error bound amounts to minimization of a new form of kernel similarity between data from different clusters, which lays the foundation of a new clustering algorithm presented in Section 5.

heading: 4 GENERALIZATION BOUND FOR SIMILARITY-BASED CLASSIFIER
text: In this section, the generalization error bound for the classification model in Definition 3.1 with the unsupervised similarity-based classifier is derived as a sum of discriminative similarity between the data from different classes.

heading: 4.1 GENERALIZATION BOUND
text: The following notations are introduced before our analysis. Let α = [α1, . . . , αn]⊤ be the nonzero weights that sum up to 1, α(y) be a n × 1 column vector representing the weights belonging to
class y such that α(y)i is αi if y = yi, and 0 otherwise. The margin of the labeled sample (x, y) is defined as mhS (x, y) = hS(x, y) − argmaxy′ ̸=yhS(x, y′), the sample (x, y) is classified correctly if mhS (x, y) ≥ 0. The general similarity-based classifier fS predicts the label of the input x by fS(x) = argmaxy∈{1,...,c}hS(x, y). We then begin to derive the generalization error bound for fS using the Rademacher complexity of the function class comprised of all the possible margin functions mhS . The Rademacher complexity (Bartlett & Mendelson, 2003; Koltchinskii, 2001) of a function class is defined below:
Definition 4.1. Let {σi}ni=1 be n i.i.d. random variables such that Pr[σi = 1] = Pr[σi = −1] = 12 . The Rademacher complexity of a function class A is defined as
R(A) = E{σi},{xi} [ sup h∈A ∣∣∣∣∣ 1n n∑
i=1
σih(xi) ∣∣∣∣∣ ] . (2)
In order to analyze the generalization property of the classification rule using the general similarity function, we first investigate the properties of general similarity function and its relationship to PSD kernels in terms of eigenvalues and eigenfunctions of the associated integral operator. The integral operator (LSf)(x) = ∫ S(x, t)f(t)dt is well defined. It can be verified that LS is a compact operator since S is continuous. According to the spectral theorem in operator theory, there exists an orthonormal basis {ϕ1, ϕ2, . . .} of L2 which is comprised of the eigenfunctions of LS , where L2 is the space of measurable functions which are defined over X and square Lebesgue integrable. ϕk is the eigenfunction of LS with eigenvalue λk if LSϕk = λkϕk. The following lemma shows that under certain assumption on the eigenvalues and eigenfunctions of LS , a general symmetric and continuous similarity can be decomposed into two PSD kernels.
Lemma 4.1. Suppose S : X × X → [0, 1] is a symmetric continuous function, and {λk} and {ϕk} are the eigenvalues and eigenfunctions of LS respectively. Suppose ∑ k≥1 λk|ϕk(x)|2 < C for some
constant C > 0. Then S(x, t) = ∑ k≥1 λkϕk(x)ϕk(t) for any x, t ∈ X , and it can be decomposed as the difference between two positive semi-definite kernels, that is, S(x, t) = S+(x, t) − S−(x, t), with
S+(x, t) = ∑
k : λk≥0
λkϕk(x)ϕk(t), S −(x, t) = ∑ k:λk<0 |λk|ϕk(x)ϕk(t). (3)
We now use a regularization term to bound the Rademacher complexity for the classification rule using the general similarity function. Let Ω+(α) = c∑
y=1 α(y)
⊤ S+α(y) and Ω−(α) =
c∑ y=1 α(y) ⊤ S−α(y) with [S+]ij = S+(xi,xj) and [S−]ij = S−(xi,xj). The space Hy of all the hypothesis hS(·, y) associated with label y is defined as
HS,y = {(x, y)→ ∑
i : yi=y
αiS(x,xi) : α ≥ 0,1⊤α = 1,Ω+(α) ≤ B+ 2 ,Ω−(α) ≤ B−2}
for 1 ≤ y ≤ c, with positive number B+ and B− which bound Ω+ and Ω− respectively. Let the hypothesis space comprising all possible margin functions be HS = {(x, y) → mhS (x, y) : hS(x, y) ∈ HS,y}. We then present the main result in this section about the generalization error of unsupervised similarity-based classifier fS .
Theorem 4.2. Given the discriminative model MY = (S, fS), suppose Ω+(α) ≤ B+ 2, Ω−(α) ≤ B− 2, supx∈X |S+(x,x)| ≤ R2, supx∈X |S−(x,x)| ≤ R2 for positive constants B+, B− and R. Then with probability 1 − δ over the labeled data S with respect to any distribution in PXY , under
the assumptions of Lemma 4.1, the generalization error of the general classifier fS satisfies
R(fS) =Pr [Y ̸= fS(X)]
≤R̂n(fS) + 8R(2c− 1)c(B+ +B−)
γ √ n
+
( 16c(2c− 1)(B+ +B−)R2
γ + 1 )√ log 4δ 2n ,
(4)
where R̂n(fS) = 1n n∑
i=1
Φ ( hS(xi,yi)−argmaxy′ ̸=yhS(xi,y ′)
γ
) is the empirical loss of fS on the labeled
data, γ > 0 is a constant and Φ is defined as Φ(x) = min {1,max{0, 1− x}}. Moreover, if γ ≥ 1, the empirical loss R̂n(fS) satisfies
R̂n(fS) ≤ 1− 1
nγ n∑ i,j=1 αi + αj 2 S(xi,xj) + 1 nγ n∑ 1≤i<j≤n 2(αi + αj)S(xi,xj)1Iyi ̸=yj . (5)
The indicator function 1IE in (5) is 1 if event E is true, and 0 otherwise. Remark 4.3. Lemma E.3 in the Appendix shows that the Rademacher complexity ofHS is bounded in terms of B+ and B−, and that is why these two quantities appear on the RHS of (4). In addition, when S is a Positive Semi-Definite (PSD) kernel K, it can be verified that S− ≡ 0, S = S+. Remark 4.4. When the decomposition S = S+ − S− exists and S+, S− are PSD kernels, S is the kernel of some Reproducing Kernel Kreı̆n Space (RKKS) (Mary, 2003). Ong et al. (2004) and Loosli et al. (2016) analyzed the problem of learning SVM-style classifiers with indefinite kernels from the Kreı̆n space. However, their work does not show when and how an indefinite and general similarity function can have PSD decomposition, as well as the generalization analysis for the similarity-based classifier using such general indefinite function as similarity measure. Our analysis deals with these problems in Lemma 4.1 and Theorem 4.2. It should be emphasized that our generalization bound is of independent interest in supervised learning, because it is among the few results of generalization bounds using general similarity-based classifier. Section B.1 shows that the our bound is a principled result with strong connection to established generalization error bound for Support Vector Machines (SVMs) or Kernel Machines.

heading: 4.2 CLUSTERING BY DISCRIMINATIVE SIMILARITY
text: We let
Ssimij = 2(αi + αj)S(xi,xj)− 2λαiαjS+(xi,xj)− 2λαiαjS−(xi,xj) (6) be the discriminative similarity between data from different classes, which is induced by the generalization error bound (4) for the unsupervised general similarity-based classifier fS . Minimizing the bound (4) motivates us to consider the optimization problem that minimizes R̂n(fS) + λ ( Ω+(α) +
Ω−(α) ) . Replacing R̂n(fS) by its upper bound in (5), we consider the following problem,
min α,Y n∑ 1≤i<j≤n Ssimij 1Iyi ̸=yj − n∑ i,j=1 αi + αj 2 S(xi,xj) + λ(α ⊤S+α+α⊤S−α)
s.t. α ≥ 0,1⊤α = 1,Y = {yi}ni=1, (7)
where λ > 0 is the weighting parameter for the regularization term Ω+(α) + Ω−(α). Note that we do not set λ to 16c(2c−1)R 2+8 √ 2R(2c−1)c√
2γ exactly matching the RHS of (4), because λ controls
the weight of the regularization term which bounds the unknown complexity of the function class HS . Note that (7) encourages the discriminative similarity Ssimij between the data from different classes small. The optimization problem (7) forms the formulation of Clustering by Discriminative Similarity (CDS).
By Remark 4.3, when S is a PSD kernel K, S− ≡ 0, S = S+, Ssimij reduces to the following discriminative similarity for PSD kernels:
SKij = 2(αi + αj − λαiαj)K(xi − xj), 1 ≤ i, j ≤ n, (8)
and SKij is the similarity induced by the unsupervised kernel classifier by the kernel K.
Without loss of generality, we set K = Kτ (x) = exp(−∥x∥ 2 2
2τ2 ) which is the isotropic Gaussian kernel with kernel bandwidth τ > 0, and we omit the constant that makes integral of K unit.
When setting the general similarity function to kernel Kτ , CDS aims to minimize the error bound for the corresponding unsupervised kernel classifier, which amounts to minimizing the following objective function
min α∈Λ,Y={yi}ni=1 n∑ 1≤i<j≤n SKij 1Iyi ̸=yj − n∑ i,j=1 αi + αj 2 Kτ (xi − xj) + λα⊤Kα, (9)
where SKij is defined in (8) with K = Kτ . K ∈ Rn×n and Kij = Kτ (xi − xj). λ is tuned such that SKij ≥ 0, e.g. λ ≤ 2. In Section A, it is shown that the discriminative similarity (8) can also be induced from the perspective of kernel density classification by kernel density estimators with nonuniform weights. It supports the theoretical justification for the induced discriminative similarity in this section.

heading: 5 APPLICATION TO DATA CLUSTERING
text: In this section, we propose a novel data clustering method termed Clustering by Discriminative Similarity via unsupervised Kernel classification (CDSK) which is an empirical method inspired by our CDS model when the similarity function is a PSD kernel K = Kτ . In accordance with the CDS model in Section 4.2, CDSK aims to minimize (9). However, problem (9) involves minimization with respect to discrete cluster labels Y = {yi} which is NP-hard. In addition, it potentially results in a trivial solution which puts all the data in a single cluster due to the lack of constraints on the cluster balance. When Y is a binary matrix where each column is a membership vector for a
particular cluster, n∑
1≤i<j≤n SKij 1Iyi ̸=yj = 1 2Tr(Y ⊤LKY). Therefore, (9) is relaxed in the proposed
optimization problem for CDSK below:
min α∈Λ,Y∈Rn×c
1 2 Tr(Y⊤LKY)− n∑ i,j=1 αi + αj 2 Kτ (xi − xj) + λα⊤Kα s.t. Y⊤DKY = Ic,
(10)
where Λ = {α : α ≥ 0,1⊤α = 1}, SKij = SKij , LK = DK − SK is the graph Laplacian computed with SK , DK is a diagonal matrix with each diagonal element being the sum of the corresponding
row of SK : [DK ]ii = n∑
j=1
SKij , Ic is a c × c identity matrix, c is the number of clusters. The
constraint in (10) is used to balance the cluster size. This is because minimizing (9) without any constraint on the cluster size results in a trivial solution where all data points form a single cluster. Inspired by spectral clustering (Ng et al., 2001), the constraint Y⊤DKY = Ic used in CDSK prevents imbalanced data clusters.
Problem (10) is optimized by coordinate descent. In each iteration of coordinate descent, optimization with respect to Y is performed with fixed α, which is exactly the same problem as that of spectral clustering with a solution formed by the smallest c eigenvectors of the normalized graph Laplacian (DK)−1/2LK(DK)−1/2; then the optimization with respect to α is performed with fixed Y, which is a standard constrained quadratic programming problem. The iteration of coordinate descent proceeds until convergence or the maximum iteration number M is achieved. Each iteration solves two subproblems, (11) and (12). The algorithm of CDSK is described in Algorithm 1. Furthermore, Section C in the appendix explains the theoretical properties of the coordinate descent algorithm for problem (10).
The baseline named SC-NS performs spectral clustering on the nonparametric similarity proposed in Yang et al. (2014a). The baseline named SC-MS first constructs a similarity matrix between data denoted by W, where Wij = Kτ (xi − xj), then optimize the kernel bandwidth h by minimizing
Algorithm 1 Clustering by Discriminative Similarity via unsupervised Kernel classification (CDSK)
Input: Unlabeled dataset {xl}nl=1, parameter λ, maximum iteration number M . for t← 1 to M do
With fixed α, solve
min Y∈Rn×c
Tr(Y⊤LKY) s.t. Y⊤DKY = Ic, (11)
With fixed Y, solve
min α∈Λ,
Tr(Y⊤LKY)− n∑
i,j=1
αi + αj 2 Kτ (xi − xj) + λα⊤Kα
s.t. Y⊤DKY = Ic, (12)
end for Perform K-Means Clustering on rows of Y to obtain the clustering result.
∑ i ∥xi− 1di ∑ j Wijxj∥2 where di = ∑ j Wij . SC-MS then performs spectral clustering on W with the kernel bandwidth h obtained from the optimization.
To demonstrate the advantage of the proposed parametric discriminative similarity, we compare CDSK to various baseline clustering methods. SC stands for Spectral Clustering, which is the best performer among spectral clustering with similarity matrix set by Gaussian kernel (SCK), spectral clustering with similarity matrix set by a manifold-based similarity learning method (SC-MS) (Karasuyama & Mamitsuka, 2013), and spectral clustering with similarity matrix set by the nonparametric discriminative similarity (SC-NS) in (Yang et al., 2014a). In SC-MS, Gaussian kernel is used as data similarity, and the parameters of the diagonal covariance matrix is optimized so as to minimize the data reconstruction error term. SC-NS minimizes nonparametric kernel similarity between data across different clusters, which is the same objective as that of kernel K-Means (Schölkopf et al., 1998), so its performance is the same as kernel K-Means. Please refer to Section 2 for discussion about other baselines.
Datasets. We conduct experiments on the Yale face dataset, UCI Ionosphere dataset, the MNIST handwritten digits dataset and the Georgia Face dataset. The Yale face dataset has face images of 15 people with 11 images for each person. The Ionosphere data contains 351 points of dimensionality 34. The Georgia Face dataset contains images of 50 people, and each person is represented by 15 color images with cluttered background. COIL-20 dataset has 1440 images of size 32 × 32 for 20 objects with background removed in all images. The COIL-100 dataset contains 100 objects with 72 images of size 32 × 32 for each object. CMU PIE face data contains 11554 cropped face images of size 32× 32 for 68 persons, and there are around 170 facial images for each person under different illumination and expressions. The UMIST face dataset is comprised of 575 images of size 112 × 92 for 20 people. CMU Multi-PIE (MPIE) data (Gross et al., 2010) contains 8916 facial images captured in four sessions. The MNIST handwritten digits database has a total number of 70000 samples of dimensionality 1024 for digits from 0 to 9. The digits are normalized and centered in a fixed-size image. The Extended Yale Face Database B (Yale-B) dataset contains face images for 38 subjects with 64 frontal face images taken under different illuminations for each subject. CIFAR-10 dataset consists of 50000 training images and 10000 testing images in 10 classes, and each image is a color one of size 32× 32, and we perform data clustering using all the training and testing images. We also use the miniImageNet dataset used in (Vinyals et al., 2016) to evaluate the potential of clustering methods. MiniImageNet consists of 60, 000 color images of size 84×84 with 100 classes, and each class has 600 images. MiniImageNet is known to be more complex than the CIFAR-10 dataset, and we perform clustering on the 64 classes in miniImageNet which are used for few-shot learning, so 38, 400 images are used for clustering. For every clustering method involving randomness such as K-Means clustering, we report the average performance of running it for 10 times.
Performance Measures and Tuning λ by Cross Validation. We use Accuracy (AC) and Normalized Mutual Information (NMI) (Zheng et al., 2004) as the performance measures. The results of
different clustering methods are shown in Table 1 in the format of AC(NMI). Except for SC-MS, the kernel bandwidth in all methods is set as the variance of the pairwise Euclidean distance between the data. λ is the weight for the regularization term in our derived generalization bound. As explained in Section B.1 of the appendix, λ plays the same role as the weight in the regularization term of SVMs or Kernel Machines. Following the common practice in the literature of SVM or Kernel Machines, λ can be tuned by Cross-Validation (CV). While this is an unsupervised learning task and these is no labeled data for CV, we still developed a well-motivated CV procedure. Following the practice in (Mairal et al., 2012), we randomly sampled 10% of the given data as the validation data, then perform CDSK on the validation data. The best λ is chosen among the discrete values between [0.05, 05] with a step of 0.05 which minimizes the average entropy of the obtained embedding matrix
Y ∈ Rn×c by Algorithm 1, where the average entropy is compute as 1n n∑
i=1
entropy(softmax(Yi)).
This is because we would like to choose λ which renders the most confident clustering embedding. We perform CDSK on all the datasets using this tuning strategy and observe improved performance as shown in the above two tables. For clustering methods involving random operations, the average performance over 10 runs is reported.
Computational Complexity. Suppose the optimization of CDSK comprises M iterations of coordinate descent. The first subproblem (11) in Algorithm 1 takes O(n2c) steps using truncated Singular Value Decomposition (SVD) by Krylov subspace iterative method. We adopt Sequential Minimal Optimization (SMO) (Platt, 1998) to solve the second subproblem (12), which takes roughly O(n2.1) steps as reported in Platt (1998). Therefore, the overall time complexity of CDSK is O(Mcn2 +Mn2.1). M is set to 20 throughout all the experiments.

heading: 6 CONCLUSION
text: We propose a new clustering framework termed Clustering by Discriminative Similarity (CDS). CDS searches for the optimal partition of the data where the associated unsupervised classifier has minimum generalization error bound. Under this framework, discriminative similarity is induced by the generalization error bound for unsupervised similarity-based classifier, and CDS minimizes discriminative similarity between different clusters. It is also proved that the discriminative similarity can be induced from kernel density classification. Based on CDS, we propose a new clustering
method, CDS via unsupervised kernel classification (CDSK), and demonstrate its effectiveness in data clustering.

heading: A CONNECTION TO KERNEL DENSITY CLASSIFICATION
text: In this section, we show that the discriminative similarity (8) can also be induced from kernel density classification with varying weights on the data, and binary classification is considered in this section. For any classification model MY = (S, f) with hypothetical labeling Y and the labeled data S = {xi, yi}ni=1, suppose the joint distribution PXY over X × {1, 2} has probabilistic density function p(x, y). Let PX be the induced marginal distribution over the data with probabilistic density function p(x). Robust kernel density estimation methods (Girolami & He, 2003; Kim & Scott, 2008; Mahapatruni & Gray, 2011; Kim & Scott, 2012) suggest the following kernel density estimator where the kernel contributions of different data points are reflected by different nonnegative weights that sum up to 1:
p̂(x) = τ0 n∑ i=1 αiKτ (x− xi),1⊤α = 1,α ≥ 0, (13)
where τ0 = 1(2π)d/2hd . Based on (13), it is straightforward to obtain the following kernel density estimator of the density function p(x, y):
p̂(x, y) = τ0 ∑
i:yi=y
αiKτ (x− xi). (14)
Kernel density classifier is learnt from the labeled data S and constructed by kernel density estimators (14). Kernel density classifier resembles the Bayes classifier, and it classifies the test data x based on the conditional label distribution P (Y |X = x), or equivalently, x is assigned to class 1 if p̂(x, 1) − p̂(x, 2) ≥ 0, otherwise it is assigned to class 2. Intuitively, it is preferred that the decision function r̂(x,α) = p̂(x, 1) − p̂(x, 2) is close to the true Bayes decision function r = p(x, 1) − p(x, 2). Girolami & He (2003); Kim & Scott (2008) propose to use Integrated Squared Error (ISE) as the metric to measure the distance between the kernel density estimators and their true counterparts, and the oracle inequality is obtained that relates the performance of the L2 classifier in Kim & Scott (2008) to the best possible performance of kernel density classifier in the same category. ISE is adopted in our analysis of kernel density classification, and the ISE between the decision function r̂ and the true Bayes decision function r is defined as
ISE(r̂, r) = ∥r̂ − r∥2L2 = ∫ Rd (r̂ − r)2dx. (15)
The upper bound for the ISE ISE(r, r̂) also induces discriminative similarity between the data from different classes, which is presented in the following theorem. Theorem A.1. Let n1 = ∑ i=1 1Iyi=1 and n2 = ∑ i=1 1Iyi=2. With probability at least 1 − 2n2 exp ( −
2(n − 1)ε2 ) − 2n exp ( − 2nε2 ) over the labeled data S, the ISE between the decision function
r̂(x,α) and the true Bayes decision function r(x) satisfies
ISE(r̂, r) ≤ τ0 n ÎSE(r̂, r) + τ1K(α) + 2τ0 ( 1 n− 1 + ε ) , (16)
where
ÎSE(r̂, r) = 4 ∑
1≤i<j≤n
(αi + αj)Kτ (xi − xj)1Iyi ̸=yj − n∑
i,j=1
(αi + αj)Kτ (xi − xj), (17)
K(α) = α⊤(K√2h)α− 4 ∑
1≤i<j≤n
αiαjK√2h(xi − xj)1Iyi ̸=yj , (18)
and K√2h is the gram matrix evaluated on the data {xi}ni=1 with the kernel K√2h.
Let λ1 > 0 be a weighting parameter, then the cost function ÎSE + λ1K(α), designed according to the empirical term ISE(r̂, r) and the regularization term K(α) in the ISE error bound (16), can be expressed as
ÎSE + λ1K(α) ≤ ∑
1≤i<j≤n
Siseij 1Iyi ̸=yj − n∑
i,j=1
(αi + αj)Kτ (xi − xj) + λ1α⊤K√2hα,
where the first term is comprised of sum of similarity between data from different classes with similarity Siseij = 4(αi + αj − λ1αiαj)Kτ (xi − xj), and Siseij is the discriminative similarity induced by the ISE bound for kernel density classification. Note that Siseij has the same form as the discriminative similarity SKij (8) induced by our CDS model, up to a scaling constant and the choice of the balancing parameter λ. The proof of Theorem A.1 is deferred to Section E.3.

heading: B MORE EXPLANATION ABOUT THE THEORETICAL RESULTS IN
text: SECTION 4.1

heading: B.1 THEORETICAL SIGNIFICANCE OF THE BOUND (4)
text: To the best of our knowledge, our generalization error bound (4) is the first principled result about generalization error bound for general similarity-based classifier with strong connection to the established generalization error bound for Support Vector Machines (SVMs) or Kernel Machines.
We now explain this claim. When the similarity function S is a PSD kernel function, we have S− ≡ 0, S = S+ as explained in Remark 4.3. As a reminder, S is the general similarity function used in the similarity-based classification, and S+, S− are PSD kernel functions, and it is proved that S can be decomposed by S = S+−S− under the mild conditions of Lemma 3.1. It follows that we can set Ω−(α) = 0 and B− = 0. Plugging B− = 0 in the derived generalization error bound for the general similarity-based classification (4), we have
Prob [Y ̸= fS(X)] ≤ R̂n(fS) + 8R(2c− 1)cB+
γ √ n
+
( 16c(2c− 1)B+R2
γ + 1 )√ log 4δ 2n . (19)
According to its definition, Ω+(α) = c∑
y=1 α(y)
⊤ Sα(y) because S = S+. We define B := B+.
Because Ω+(α) ≤ B+2 as mentioned in Theorem 3.2, B satisfies c∑
y=1 α(y)
⊤ Sα(y) ≤ B2. As a
result, when S is a PSD kernel function, inequality (19) becomes
Prob [Y ̸= fS(X)] ≤ R̂n(fS) + 8R(2c− 1)cB
γ √ n
+
( 16c(2c− 1)R2B
γ + 1 )√ log 4δ 2n , (20)
with c∑
y=1 α(y)
⊤ Sα(y) ≤ B2.
Note that the bound (20) is in fact the generalization error bound for supervised learning when using S as the similarity function in the similarity-based classification. At the end of this subsection, we
provide a lemma proving that c∑
y=1 α(y)
⊤ Sα(y) ≤ B2 ⇒ α⊤Sα ≤ cB2, where c is the number of
classes.
Now we compare the generalization error bound (20) to the established generalization error bound for Kernel Machines in (Bartlett & Mendelson, 2003, Theorem 21) for the case that c = 2 with notations adapted to our analysis. The bound in (Bartlett & Mendelson, 2003, Theorem 21) is for binary classification, which is presented as follows:
Prob [Y ̸= fS(X)] ≤ R̂n(fS) + 4 √ RB
γ √ n +
( 8
γ + 1
)√ log 4/δ
2n ,α⊤Sα ≤ B2. (21)
Comparing our generalization error bound (2) with c = 2 to the max-margin generalization error bound (21), it can be easily seen that the two bounds are equivalent up to a constant scaling factor. In fact, our bound (2) is more general which handles multi-class classification. Lemma B.1. When S is a PSD kernel, then c∑
y=1 α(y)
⊤ Sα(y) ≤ B2 ⇒ α⊤Sα ≤ cB2.
Proof. Let H be the Reproducing Kernel Hilbert Space associated with the PSD kernel function S, and H is also called the feature space associated with S. We use ⟨·, ·⟩H to denote the inner product in the feature space H. Then we have S(xi,xj) = Sij = ⟨Φ(xi),Φ(xj)⟩H where Φ is the feature
mapping associated withH. Because α = c∑
y=1 αy , it can be verified that
α⊤Sα = n∑
i=1 n∑ j=1 αiαjSij = ⟨ n∑ i=1 αiΦ(xi), n∑ j=1 αjΦ(xj)⟩ ≤ c c∑
y=1 ⟨ey, ey⟩H, where ey =∑
i : yi=y
αyiΦ(xi). It follows that α ⊤Sα ≤ c c∑ y=1 α(y) ⊤ Sα(y) ≤ cB2.

heading: B.2 TIGHTNESS OF THE BOUND
text: Note that the generalization error Pr [Y ̸= f(X)] is bounded by R̂n(f) = 1 n n∑ i=1 Φ (hS(xi,yi)− ∑ y ̸=yi hS(xi,y) γ ) in Theorem 4.2. The underlying principle behind this bound and all such bounds in the statistical machine learning literature such as Bartlett & Mendelson (2003) is the following property about empirical process (adjusted using our notations):
R(H) ≤ Ex,y sup h∈H |Ex,yR̂n(f)−Rn(f)| ≤ 2R(H), (22)
where Ex,y indicates expectation with respect to random couple (x, y) ∼ PXY , and PXY is a joint distribution in a discriminative model MY = (S, f). (22) is introduced in the classical properties of empirical process in Gine & Zinn (1984). By Lemma E.2 of this paper, with probability at least 1− δ over the data {xi}ni=1 i.i.d.∼ PXY ,
R(H) ≤ (2c− 1)c√ n B + √ 2Bc(2c− 1) √ ln 2δ 2n = O( B√ n ) (23)
for some constant B. It follows from (22), (23), and concentration inequality (such as McDiarmid’s inequality) that for each sufficiently large n, with large probability, suph∈H |Ex,yR̂n(f) − Rn(f)| is less than O( B√
n ). Therefore, we can bound the expectation of the empirical loss, i.e. Ex,yR̂n(f),
tightly using the empirical loss Rn(f) uniformly over the function spaceH.

heading: C THEORETICAL PROPERTIES OF THE COORDINATE DESCENT ALGORITHM
text: IN SECTION 5
In this subsection, we give a detailed explanation about the theoretical properties of the coordinate descent algorithm presented in Section 5. We first explain how the objective function of CDSK (10)
is connected to the objective function (9) developed in our theoretical analysis. It should be emphasized that (9) cannot be directly used for data clustering since it cannot avoids the trivial solution where all the data are in a single cluster. We adopt the broadly used formulation of normalized
cut and use c∑
k=1
cut(Ak,Āk) vol(Ak) to replace ∑ i<j SKij 1Iyi ̸=yj in (9), leading to the following optimization
problem:
min α∈Λ,Y={yi}ni=1 c∑ k=1 cut(Ak, Āk) vol(Ak) − n∑ i,j=1 αi + αj 2 Kτ (xi − xj) + λα⊤Kα ≜ Q̄(α,Y), (9’)
where {A}ck=1 are c data clusters according to the cluster labels {yi}, Āk is the complement of Ak, cut(A,B) = ∑ xi∈A,xj∈B SKij , vol(A) = ∑ xi∈A,1≤j≤n SKij . We have the following theorem, which can be derived based on Theorem 4.1 in the work of multi-way Cheeger inequalities (Lee et al., 2012). Theorem C.1. minα∈Λ,Y c∑
k=1
cut(Ak,Āk) vol(Ak)
≲ c∑
t=1 σt(L
nor), where Lnor is the normalized graph
Laplacian Lnor = (DK)−1/2LK(DK)−1/2, a ≲ b indicates a < Cb for some constant C and σt(·) indicates the t-th smallest singular value of a matrix.
Based on Theorem C.1, we resort to solve the following more tractable problem, that is,
min α∈Λ k∑ t=1 σt(L nor)− n∑ i,j=1 αi + αj 2 Kτ (xi − xj) + λα⊤Kα ≜ Q(α), (9”)
because Q (9”) is an upper bound for Q̄ (9’) up to a constant scaling factor. It can be verified that problem (10) is equivalent to (9”), and (9”) is the underlying optimization problem for data clustering in Section 5. The following proposition shows that the iterative coordinate descent algorithm in Section 5 reduces the value of Q at each iteration.
Proposition C.2. The coordinate descent algorithm for problem (10) reduces the value of the objective function Q(α) at each iteration.
Proof. Let Q′(α,Y) ≜ Tr(Y⊤LKY) − n∑
i,j=1
αi+αj 2 Kτ (xi − xj) + λα ⊤Kα, and we use su-
perscript to denote the iteration number of coordinate descent. At iteration m, after solving the subproblems (11) and (12), we have Q′(α(m),Y(m)) = Q(α(m)). At iteration m + 1, by solving the subproblems (4) and (3) in order again, we have Q′(α(m+1),Y(m+1)) = Q(α(m+1)). Because of the nature of coordinate descent, Q′(α(m+1),Y(m+1)) ≤ Q′(α(m),Y(m)), it follows that Q(α(m+1)) ≤ Q(α(m)).
Based on Proposition C.2, the iterations of coordinate descent are similar to that of EM algorithms and they reduce the value of Q, where Y plays the role of latent variable for EM algorithms.

heading: D MORE DETAILS ABOUT THE EXPERIMENTS

heading: D.1 PHYSICAL MEANING OF ADAPTIVE WEIGHTS IN DISCRIMINATIVE SIMILARITY
text: Figure 2 illustrates the importance of the adaptive weights α in the discriminative similarity, as well as the illustration of the learned discriminative similarity.
As illustrated in Figure 2(a), the adaptive weights α help reduce similarity between data close to cluster boundary, which is difficult for kernel similarity with uniform weights such as that for kernel K-means. Figure 2(b) illustrates the desirable block-diagonal structure of the proposed discriminative similarity on a dataset used for experiments.

heading: D.2 CONVERGENCE OF THE OBJECTIVE FUNCTION
text: The value of the objective function (9), that is, Q in equation (9”) with respect to the iteration number of coordinate descent on the Yale-B dataset is illustration in Figure 3.

heading: D.3 COMPUTATIONAL COMPLEXITY AND RUNNING TIME
text: Table 3 shows the time complexity of CDSK and baseline methods. Here sparse graph-based methods include ℓ1-Graph (Elhamifar & Vidal, 2013), SMCE (Elhamifar & Vidal, 2011), and Lap-ℓ1Graph (Yang et al., 2014b). Decision tree-based methods include RAG (Zhu et al., 2014) and RatioRF (Bicego et al., 2021). Maximum margin-based methods include MMC (Xu et al., 2004) and BMMC (Chen et al., 2014). T in sparse graph-based methods indicates the number of iterations for proximal gradient descent. T in decision tree-based methods means the number of decision trees trained for data clustering, which is typically set to be very large number. T in K-Means is the number of iterations for K-Means. DT is the time complexity of training a decision tree, which is O(vn log n) where v is the number of features in the decision tree. The minimum time complexity for each group of baselines is reported, and the running time of different clustering algorithms on MNIST and Yale-B is shown in Table 3.

heading: D.4 MORE DETAILS ABOUT OPTIMIZATION OF CDSK
text: The optimization of CDSK comprises M iterations of coordinate descent, wherein each iteration solves the following two subproblems.
1) With constant α, min
Y∈Rn×c Tr(Y⊤LKY) s.t. Y⊤DKY = Ic, (24)
2) With constant Y,
min α∈Λ,
Tr(Y⊤LKY)− n∑
i,j=1
αi + αj 2 Kτ (xi − xj) + λα⊤Kα
s.t. Y⊤DKY = Ic, (25)
The first subproblem (24) takesO(n2c) steps using truncated Singular Value Decomposition (SVD) by Krylov subspace iterative method. We adopt Sequential Minimal Optimization (SMO) (Platt, 1998) to solve the second subproblem (25), which takes roughly O(n2.1) steps as reported in (Platt, 1998). SMO is an iterative algorithm where each iteration of SMO solves the quadratic programming (25) with respect to only two elements of the weights α, so that each iteration of SMO can be performed efficiently. Therefore, the overall time complexity of CDSK is O(Mcn2 +Mn2.1).

heading: E PROOFS

heading: E.1 PROOF OF LEMMA 4.1
text: Before stating the proof of Lemma 4.1, we introduce the famous spectral theorem in operator theory below. Theorem E.1. (Spectral Theorem) Let L be a compact linear operator on a Hilbert spaceH. Then there exists in H an orthonormal basis {ϕ1, ϕ2, . . .} consisting of eigenvectors of L. If λk is the eigenvalue corresponding to ϕk, then the set {λk} is either finite or λk → 0 when k → ∞. In addition, the eigenvalues are real if L is self-adjoint.
Recall that the integral operator by S is defined as
(LSf)(x) =
∫ S(x, t)f(t)dt,
and we are ready to prove Lemma 4.1.
Proof of Lemma 4.1. It can be verified that LS is a compact operator. Therefore, according to Theorem E.1, {ϕk} is an orthogonal basis of L2. Note that ϕk is the eigenfunction of LS with eigenvalue λk if LSϕk = λkϕk.
With fixed x ∈ X , we then have∣∣∣∣ m+ℓ∑ k=m λkϕk(x)ϕk(t) ∣∣∣∣ ≤ ( m+ℓ∑ k=m |λk||ϕk(x)|2 ) 1 2 · ( m+ℓ∑ k=m |λk||ϕk(t)|2 ) 1 2
≤ √ C ( m+ℓ∑ k=m |λk||ϕk(x)|2 ) 1 2 .
It follows that the series ∑ k≥1 λkϕk(x)ϕk(t) converges to a continuous function ex uniformly on t. This is because ϕk = LSϕkλk is continuous for nonzero λk.
On the other hand, for fixed x ∈ X , as a function in L2, S(x, ·) = ∑ k≥1 ⟨S(x, ·), ϕk⟩ϕk = ∑ k≥1 λkϕk(x)ϕk(·).
Therefore, for fixed x ∈ X , S(x, ·) = ∑ k≥1 λkϕk(x)ϕk(·) = ex(·) almost surely w.r.t the Lebesgue
measure. Since both are continuous functions, we must have S(x, t) = ∑ k≥1 λkϕk(x)ϕk(t) for any
t ∈ X . It follows that S(x, t) = ∑ k≥1 λkϕk(x)ϕk(t) for any x, t ∈ X .
We now consider two series which correspond to the positive eigenvalues and negative eigenvalues of LS , namely ∑ k : λk≥0 λkϕk(x)ϕk(·) and ∑ k:λk<0 |λk|ϕk(x)ϕk(·). Using similar argument, for fixed x, both series converge to a continuous function, and we let
S+(x, t) = ∑
k : λk≥0
λkϕk(x)ϕk(t),
S−(x, t) = ∑
k:λk<0
|λk|ϕk(x)ϕk(t).
S+(x, t) and S−(x, t) are continuous function in x and t. All the eigenvalues of S+ and S− are nonnegative, and it can be verified that both are PSD kernels since
n∑ i,j=1 cicjS +(xi,xj) = n∑ i,j=1 cicj ∑
k : λk≥0
λkϕk(xi)ϕk(xj)
= ∑
k : λk≥0
λk n∑ i,j=1 cicjϕk(xi)ϕk(xj)
= ∑
k : λk≥0
λk( n∑ i=1 ciϕ(xi)) 2 ≥ 0.
Similarly argument applies to S−. Therefore, S is decomposed as S(x, t) = S+(x, t)− S−(x, t).

heading: E.2 PROOF OF THEOREM 4.2
text: Lemma E.3 will be used in the Proof of Theorem 4.2. The following lemma is introduced for the proof of Lemma E.3, whose proof appears in the end of this subsection. Lemma E.2. The Rademacher complexity of the classHS satisfies
R(HS) ≤ (2c− 1) c∑
y=1
R(HS,y). (26)
Lemma E.3. Define Ω+(α) = c∑
y=1 α(y)
⊤ S+α(y) and Ω−(α) = c∑ y=1 α(y) ⊤ S−α(y). When
Ω+(α) ≤ B+2,Ω−(α) ≤ B−2 for positive constant B+ and B−, supx∈X |S+(x,x)| ≤ R2, supx∈X |S−(x,x)| ≤ R2 for some R > 0, then with probability at least 1 − δ over the data {xi}ni=1, the Rademacher complexity of the classHS satisfies
R(HS) ≤ R(2c− 1)c(B+ +B−)√
n + 2c(2c− 1)(B+ +B−)R2 √ ln 2δ 2n . (27)
Proof of Lemma E.3 . According to Lemma 4.1, S is decomposed into two PSD kernels as S = S+−S−. Therefore, the are two Reproducing Kernel Hilbert SpacesH+S andH − S that are associated with S+ and S− respectively, and the canonical feature mappings in H+S and H − S are ϕ
+ and ϕ−, with S+(x, t) = ⟨ϕ+(x), ϕ+(t)⟩H+K and S
−(x, t) = ⟨ϕ−(x), ϕ−(t)⟩H−K . In the following text, we will omit the subscripts H+K and H − K without confusion.
For any 1 ≤ y ≤ c,
hS(x, y) = ∑
i : yi=y
αiS(x,xi) = ⟨w+, ϕ+(x)⟩ − ⟨w−, ϕ−(x)⟩
with ∥w+∥2 = α(y)⊤S+α(y) ≤ B+2 and ∥w−∥2 = α(y)⊤S−α(y) ≤ B−2. Therefore,
HS,y ⊆ H̃S,y = {(x, y)→ ⟨w+, ϕ+(x)⟩ − ⟨w−, ϕ−(x)⟩,
∥w+∥2 ≤ B+2, ∥w−∥2 ≤ B−2}, 1 ≤ y ≤ c,
and R(HS,y) ⊆ R(H̃S,y). Since we are deriving upper bound for R(HS,y), we slightly abuse the notation and letHS,y represent H̃S,y in the remaining part of this proof.
For x, t ∈ Rd and any hS ∈ HS,y , we have
|hS(x)− hS(t)| = |⟨w+, ϕ+(x)⟩ − ⟨w−, ϕ−(x)⟩ − ⟨w+, ϕ+(t)⟩+ ⟨w−, ϕ−(t)⟩| = |⟨w+, ϕ+(x)− ϕ+(t)⟩+ ⟨w−, ϕ−(t)− ϕ−(x)⟩| ≤ B+∥ϕ+(x)− ϕ+(t)∥+B−∥ϕ−(x)− ϕ−(t)∥)
≤ (B+ +B−) √ S+(x,x) + S+(t, t) + 2 √ S+(x,x)S+(t, t)
≤ 2R2(B+ +B−).
We now approximate the Rademacher complexity of the function class HS,y with its empirical version R̂(HS,y) using the sample {xi}. For each 1 ≤ y ≤ c, Define E(y){xi} = R̂(HS,y) =
E{σi} [ suphS(·,y)∈HS,y ∣∣∣ 1n n∑ i=1 σihS(xi, y) ∣∣∣], then c∑ y=1 R(HS,y) = E{xi} [ c∑ y=1 E (y) {xi} ] , and
sup x1,...,xn,x ′ t ∣∣∣E(y)x1,...,xt−1,xt,xt+1,...,xn − E(y)x1,...,xt−1,x′t,xt+1,...,xn ∣∣∣ = sup
x1,...,xn,x ′ t
∣∣∣∣∣E{σi} [
sup hS(·,y)∈HS,y
∣∣∣ 1 n n∑ i=1 σihS(xi, y) ∣∣∣− sup hS(·,y)∈HS,y ∣∣∣ 1 n ∑ i ̸=t σihS(xi, y) + hS(x ′ t, y) n ∣∣∣]∣∣∣∣∣ ≤ sup
x1,...,xn,x ′ t
E{σi} [∣∣∣∣ sup hS(·,y)∈HS,y ∣∣∣ 1 n n∑ i=1 σihS(xi, y) ∣∣∣− sup hS(·,y)∈HS,y ∣∣∣ 1 n ∑ i ̸=t σihS(xi, y) + hS(x ′ t, y) n ∣∣∣∣∣∣∣ ]
≤ sup x1,...,xn,x ′ t E{σi}
[ sup
hS(·,y)∈HS,y
∣∣∣∣∣∣∣ 1n n∑
i=1
σihS(xi, y) ∣∣∣− ∣∣∣ 1
n ∑ i ̸=t σihS(xi, y) + hS(x ′ t, y) n ∣∣∣∣∣∣∣ ]
≤ sup x1,...,xn,x ′ t E{σi}
[ sup
hS(·,y)∈HS,y
∣∣∣∣ 1n n∑
i=1
σihS(xi, y)− ( 1 n ∑ i ̸=t σihS(xi, y) + hS(x ′ t, y) n )∣∣∣∣ ]
= sup xt,x ′ t E{σi}
[ sup
hS(·,y)∈HS,y
∣∣∣∣hS(xt, y)n − hS(x ′ t, y) n ∣∣∣∣ ]
≤ 2R 2(B+ +B−)
n .
It follows that ∣∣∣ c∑ y=1 E (y) x1,...,xt−1,xt,xt+1,...,xn − c∑ y=1 E (y) x1,...,xt−1,x ′ t,xt+1,...,xn ∣∣∣ ≤ 2R2(B++B−)cn . According to the McDiarmid’s Inequality,
Pr [∣∣ c∑
y=1
R̂(HS,y)− c∑
y=1
R(HS,y) ∣∣ ≥ ε] ≤ 2 exp (− nε2 2(B+ +B−)2R4c2 ) . (28)
Now we derive the upper bound for the empirical Rademacher complexity:
c∑ y=1 R̂(HS,y) = c∑ y=1 E{σi}  sup hS∈HS,y ∣∣∣∣ 1n n∑ i=1 n∑ j=1 σihS(xi) ∣∣∣∣  (29)
≤ 1 n c∑ y=1 E{σi}
[ sup
∥w+∥≤B+,∥w−∥≤B− ∣∣∣∣ n∑ i=1 σi ( ⟨w+, ϕ+(xi)⟩ − ⟨w−, ϕ−(xi)⟩ )∣∣∣∣ ]
≤ 1 n c∑ y=1 E{σi}
[ B+∥
n∑ i=1 σiϕ +(xi)∥+B−∥ n∑ i=1 σiϕ −(xi)∥
]
= B+c
n E{σi}
[ ∥
n∑ i=1 σiϕ +(xi)∥
] + B−c
n E{σi}
[ ∥
n∑ i=1 σiϕ −(xi)∥
]
≤ B +c
n
√√√√E{σi} [ ∥
n∑ i=1
σiϕ+(xi)∥2 ] + B−c
n
√√√√E{σi} [ ∥
n∑ i=1
σiϕ−(xi)∥2 ]
≤ B +c
n √√√√ n∑ i s+(xi,xi) + B−c n √√√√ n∑ i s−(xi,xi) ≤ Rc√ n (B+ +B−).
By Lemma E.2, (28) and (29), with probability at least 1− δ, we have
R(HS) ≤ (2c− 1) c∑
y=1
R(HS,y) ≤ R(2c− 1)c(B+ +B−)√
n + 2c(2c− 1)(B+ +B−)R2 √ ln 2δ 2n .
(30)
Proof of Theorem 4.2 . According to Theorem 2 in Koltchinskii & Panchenko (2002), with probability 1− δ over the labeled data S with respect to any distribution in P , the generalization error of the kernel classifier fS satisfies
R(fS) ≤ R̂n(fS) + 8
γ R(HS) +
√ ln 2/δ
2n , (31)
where R̂n(fS) = 1n n∑
i=1
Φ( mhS (xi,yi)
γ ) is empirical error of the classifier for γ > 0. Due to the facts
that mhS (x, y) = hS(xi, yi)− argmaxy′ ̸=yihS(xi, y ′), α is a positive vector and S is nonnegative, we have mhS (x, y) ≥ hS(xi, yi) − ∑
y ̸=yi hS(xi, y). Note that Φ(·) is a non-increasing function, it
follows that
Φ( mhS (xi, yi)
γ ) ≤ Φ
(hS(xi, yi)− ∑ y ̸=yi hS(xi, y)
γ
) . (32)
Applying Lemma E.3, (4) holds with probability 1 − δ. When γ ≥ 1, it can be verified that∣∣∣hS(xi, yi)− ∑ y ̸=yi hS(xi, y) ∣∣∣ ≤ c∑ y=1 hS(xi, y) ≤ n∑ i=1 αi = 1 ≤ γ for all (xi, yi), so that
Φ (hS(xi, yi)− ∑ y ̸=yi hS(xi, y)
γ
) ≤ 1−
h(xi, yi)− ∑
y ̸=yi h(xi, y) γ . (33)
Note that when hS(xi, yi) − ∑
y ̸=yi hS(xi, y) ≥ 0, then 1γ
[ hS(xi, yi)−
∑ y ̸=yi hS(xi, y)
] ∈ [0, 1] so
that Φ (hS(xi,yi)− ∑ y ̸=yi hS(xi,y)
γ
) = 1− h(xi,yi)− ∑ y ̸=yi h(xi,y) γ . If hS(xi, yi)− ∑
y ̸=yi hS(xi, y) < 0, we
have Φ (hS(xi,yi)− ∑ y ̸=yi hS(xi,y)
γ
) ≤ 1 ≤ 1− h(xi,yi)− ∑ y ̸=yi h(xi,y)
γ . Therefore, (33) always holds.
By the definition of R̂n(fS), (32), and (33), (5) is obtained.
Remark E.4. It can be verified that the image of the similarity function S in Lemma 4.1 and Theorem 4.2 can be generalized from [0, 1] to [0, a] for any a ∈ R, a > 0 with the condition γ ≥ 1 replaced by γ ≥ a. This is because LS is a compact operator for continuous similarity function S : X × X → [0, a], and
∣∣∣hS(xi, yi)− ∑ y ̸=yi hS(xi, y) ∣∣∣ ≤ c∑ y=1 hS(xi, y) ≤ a. Furthermore, given a
symmetric and continuous function S : X ×X → [c, d], c, d ∈ R, c < d, we can obtain a symmetric and continuous function S′ : X ×X → [0, 1] by setting S′ = S−ab−a , and then apply all the theoretical results of this paper to CDS with S′ being the similarity function for the similarity-based classifier.
Proof of Lemma E.2. Inspired by Koltchinskii & Panchenko (2002), we first prove that the Rademacher complexity of the function class formed by the maximum of several hypotheses is bounded by two times the sum of the Rademacher complexity of the function classes that these hypothesis belong to. That is,
R(Hmax) ≤ 2 k∑
y=1
R(HS,y), (34)
whereHmax = {max{h1, . . . , hk} : hy ∈ HS,y, 1 ≤ y ≤ k} for 1 ≤ k ≤ c− 1. If no confusion arises, the notations ({σi}, {xi, yi}) are omitted in the subscript of the expectation operator in the following text, i.e. E{σi},{xi,yi} is abbreviated to E. According to Theorem 11 of Koltchinskii & Panchenko (2002), it can be verified that
E{σi},{xi,yi} ( sup h∈Hmax ∣∣∣∣ 1n n∑
i=1
σihS(xi) ∣∣∣∣ )+
≤ k∑
y=1
E{σi},{xi,yi} ( sup h∈HS,y ∣∣∣∣ 1n n∑
i=1
σihS(xi) ∣∣∣∣ )+ .
Therefore,
R(Hmax) = E{σi},{xi,yi}
[ sup
h∈Hmax
∣∣∣∣ 1n n∑
i=1
σihS(xi) ∣∣∣∣ ]
≤ E{σi},{xi,yi}
[( sup
h∈Hmax
1
n n∑ i=1
σihS(xi) )+]
+E{σi},{xi,yi}
[( sup
h∈Hmax − 1 n n∑ i=1
σihS(xi) )+]
= 2E{σi},{xi,yi}
[( sup
h∈Hmax
1
n n∑ i=1
σihS(xi) )+]
≤ 2 k∑
y=1
E{σi},{xi,yi}
[( sup
h∈HS,y
1
n n∑ i=1
σihS(xi) )+]
≤ 2 k∑
y=1
E{σi},{xi,yi}
[ sup
h∈HS,y
∣∣∣∣∣ 1n n∑
i=1
σihS(xi) ∣∣∣∣∣ ] = 2 k∑ y=1 R(HS,y). (35)
The equality in the third line of (35) is due to the fact that−σi has the same distribution as σi. Using this fact again, (34), we have
R(HS) = E{σi},{xi,yi}
[ sup
mhS∈HS
∣∣∣∣ 1n n∑
i=1
σimhS (xi, yi) ∣∣∣∣ ]
= E{σi},{xi,yi}
[ sup
mhS∈HS
∣∣∣∣ 1n n∑
i=1
σi c∑ y=1 mhS (xi, y)1Iy=yi ∣∣∣∣ ]
≤ c∑
y=1
E{σi},{xi,yi}
[ sup
mhS∈HS
∣∣∣∣ 1n n∑
i=1
σimhS (xi, y)1Iy=yi ∣∣∣∣ ]
≤ 1 2n c∑ y=1 E{σi},{xi,yi}
[ sup
mhS∈HS ∣∣∣∣ n∑ i=1 σimhS (xi, y)(21Iy=yi − 1) ∣∣∣∣ ]
+ 1
2n c∑ y=1 E{σi},{xi}
[ sup
mhS∈HS ∣∣∣∣ n∑ i=1 σimhS (xi, y) ∣∣∣∣ ]
= 1
n c∑ y=1 E{σi},{xi}
[ sup
mhS∈HS ∣∣∣∣ n∑ i=1 σimhS (xi, y) ∣∣∣∣ ] . (36)
Also, for any given 1 ≤ y ≤ c,
1 n E{σi},{xi}
[ sup
mhS∈HS ∣∣∣∣ n∑ i=1 σimhS (xi, y) ∣∣∣∣ ]
= 1
n E{σi},{xi}
[ sup
hS(·,y)∈HS,y,y=1...c ∣∣∣∣ n∑ i=1 σihS(xi, y)− σiargmaxy′ ̸=yhS(xi, y′) ∣∣∣∣ ]
≤ 1 n E{σi},{xi}
[ sup
hS(·,y)∈HS,y ∣∣∣∣ n∑ i=1 σihS(xi, y) ∣∣∣∣ ]
+ 1
n E{σi},{xi}
[ sup
hS(·,y′)∈H′S,y,y′ ̸=y ∣∣∣∣ n∑ i=1 σiargmaxy′ ̸=yhS(xi, y ′) ∣∣∣∣ ]
≤ 1 n E{σi},{xi}
[ sup
hS(·,y)∈HS,y ∣∣∣∣ n∑ i=1 σihS(xi, y) ∣∣∣∣ ] + 2 n ∑ y′ ̸=y E{σi},{xi} [ sup hS(·,y′)∈H′S,y ∣∣∣∣ n∑ i=1 σihS(xi, y ′) ∣∣∣∣ ] .
(37)
Combining (36) and (37),
R(HS) ≤ c∑
y=1
1 n E{σi},{xi}
[ sup
hS(·,y)∈HS,y ∣∣∣∣ n∑ i=1 σihS(xi, y) ∣∣∣∣ ]
+ c∑ y=1 c∑ y=1 2 n ∑ y′ ̸=y E{σi},{xi}
[ sup
hS(·,y′)∈H′S,y ∣∣∣∣ n∑ i=1 σihS(xi, y ′) ∣∣∣∣ ]
= (2c− 1) c∑
y=1
E{σi},{xi}
[ sup
hS(·,y)∈HS,y
∣∣∣∣ 1n n∑
i=1
σihS(xi, y) ∣∣∣∣ ]
= (2c− 1) c∑
y=1
R(HS,y). (38)

heading: E.3 PROOF OF THEOREM A.1
text: Proof. According to definition of ISE,
ISE(r̂, r) = ∫ Rd (r̂ − r)2dx = ∫ Rd r̂(x,α) 2 dx− 2 ∫ Rd r̂(x,α)r(x)dx+ ∫ Rd r(x) 2 dx. (39)
For a given distribution, ∫ Rd r(x)
2 dx is a constant. By Gaussian convolution theorem,∫
Rd r̂(x,α)
2 dx = τ1 2∑ y=1 α(y) ⊤ (K√2h)α (y) − τ1 ∑ 1≤i<j≤n 2αiαjK√2h(xi − xj)1Iyi ̸=yj , (40)
where τ1 = 1(2π)d/2(√2h)d . Moreover,∫ Rd r̂(x,α)r(x)dx
= ∫ Rd p̂(x, 1)p(x, 1)dx+ ∫ Rd p̂(x, 2)p(x, 2)dx− ∫ Rd p̂(x, 1)p(x, 2)dx− ∫ Rd p̂(x, 2)p(x, 1)dx.
(41)
Note that
1
τ0 ∫ Rd p̂(x, 1)p(x, 1)dx = ∑
j : yj=1
∫ Rd αjKτ (x− xj)p(x, 1)dx,
we then use the empirical term
∑ i : i̸=j αjKτ (xi−xj)1Iyi=1 n−1 to approximate the integral ∫ Rd αjKτ (x −
xj)p(x, 1)dx. Since E{xi,yi}i̸=j
[ ∑ i : i̸=j αjKτ (xi−xj)1Iyi=1
n−1
] = ∫ Rd αjKτ (x − xj)p(x, 1)dx, and
bounded difference holds for
∑ i : i̸=j αjKτ (xi−xj)1Iyi=1
n−1 , therefore,
Pr ∣∣∣∣ ∑ i : i̸=j αjKτ (xi − xj)1Iyi=1 n− 1 − ∫ Rd αjKτ (x− xj)p(x, 1)dx ∣∣∣∣ ≥ αjε  ≤ 2 exp (− 2(n− 1)ε2). It follows that with probability at least 1− 2n1 exp ( − 2(n− 1)ε2 ) , where ni is the number of data points with label i,
∣∣∣∣ ∑ i,j : i ̸=j,yi=yj=1 αjKτ (xi − xj) n− 1 − 1
τ0 ∫ Rd p̂(x, 1)p(x, 1)dx ∣∣∣∣ ≤ ∑ j : yj=1 αjε. (42)
Similarly, with probability at least 1− 2n2 exp ( − 2(n− 1)ε2 ) ,
∣∣∣∣ ∑ i,j : i ̸=j,yi=yj=2 αjKτ (xi − xj) n− 1 − 1
τ0 ∫ Rd p̂(x, 2)p(x, 2)dx ∣∣∣∣ ≤ ∑ j : yj=2 αjε. (43)
It follows from (42) and (43) that with probability at least 1− 2n exp ( − 2(n− 1)ε2 ) ,
∣∣∣∣ ∑ i,j : i ̸=j,yi=yj αjKτ (xi − xj) n− 1 − 1
τ0 ∫ Rd ( p̂(x, 1)p(x, 1) + p̂(x, 2)p(x, 2) ) dx ∣∣∣∣ ≤ ε. (44) In the same way, with probability at least 1− 2n exp ( − 2nε2 ) ,
∣∣∣∣ ∑ i,j : yi ̸=yj αjKτ (xi − xj) n − 1
τ0 ∫ Rd ( p̂(x, 1)p(x, 2) + p̂(x, 2)p(x, 1) ) dx ∣∣∣∣ ≤ ε. (45) Based on (44) and (45), with probability at least 1− 2n2 exp ( − 2(n− 1)ε2 ) − 2n exp ( − 2nε2 ) ,
ISE(r̂, r) ≤ 2τ0
∑ i,j : yi ̸=yj αjKτ (xi − xj)
n − 2τ0
∑ i,j : i ̸=j,yi=yj αjKτ (xi − xj)
n− 1
+ τ1 2∑ y=1 α(y) ⊤ (K√2h)α (y) − τ1 ∑ 1≤i<j≤n 2αiαjK√2h(xi − xj)1Iyi ̸=yj + 2τ0ε
≤ 4τ0
∑ 1≤i<j≤n (αi + αj)Kτ (xi − xj)1Iyi ̸=yj
n − τ0
n∑ i,j=1 (αi + αj)Kτ (xi − xj)
n
+ τ1 2∑ y=1 α(y) ⊤ (K√2h)α (y) − τ1 ∑ 1≤i<j≤n 2αiαjK√2h(xi − xj)1Iyi ̸=yj + 2τ0( 1 n− 1 + ε).
(46)
The conclusion of this theorem can be obtained from (46).

Review summaries:
This paper proposes a clustering algorithm by learning from the weighted similarity of each data partition. More precisely, the authors propose an unsupervised framework which aims to minimize an objective of a similarity-based classifier. Then, the upper bound of excess risk of this classifier is provided by Rademacher complexity. They show that the weighted kernel similarity is a special case of the general framework, and they apply it to discriminative clustering by iteratively optimizing the class labels and the weights of similarity. Finally, experiments are conducted to verify the effectiveness of the proposed algorithm.

This paper proposes a new discriminative clustering framework by learning an unsupervised classifier from unlabeled data. An unsupervised classifier is learned from every hypothetical data partition, and the optimal data partition is then regarded as the partition corresponding to the minimum generalization error bound of the unsupervised classifier. The authors use a similarity-based classifier as the unsupervised classifier in this framework and derive its generalization error bound as the sum of discriminative similarity between different clusters. The proposed algorithm, CDS via unsupervised kernel classification (CDSK), then minimizes the between-cluster discriminative similarity. Extensive experimental results with the comparison with a broad range of baselines confirm the superior performance of the proposed algorithm.

This paper proposes a new clustering framework called Clustering by Discriminative Similarity (CDS). CDS learns an unsupervised similarity-based classifier from each data partition, and searches for the optimal partition of the data by minimizing the generalization error of the learnt classifiers associated with the data partitions. In contrasts with kernel similarity with uniform weights, the induced discriminative similarity with learnable weights enhances its capability to represent complex inter-connection between data. Based on CDS, CDSK is proposed as a new clustering method, with its effectiveness demonstrated by experimental results.