Deep Learning with Nonparametric Clustering

Introduction

Clustering methods, such as k-means, Gaussian mixture model (GMM), spectral clustering and non-parametrical Bayesian methods, have been widely used in machine learning and data mining. Among various clustering methods, nonparametric Bayesian model is one of promising approaches for data clustering, because of its ability to infer the model complexity from the data automatically. To mine clusters or patterns from data, we can group them based on some notion of similarity. In general, calculating the clustering similarity is dependent on the features describing data. Thus, feature representation is vital for successful clustering. Just as common for other clustering methods, the presence of noisy and irrelevant features can degrade clustering performance, making feature representation an important factor in cluster analysis. Moreover, different features may be relevant or irrelevant in the high dimensional data, suggesting the need for feature learning.

Recent advances in deep learning have attracted great attention in dimension reduction and classification problems . The advantages of deep learning are that they give mappings which can capture meaningful structure information in the code space and introduce bias towards configurations of the parameter space that are helpful for unsupervised learning . More specifically, it learns the composition of multiple non-linear transformations (such as stacked restricted Boltzmann machines), with the purpose to yield more abstract and ultimately more useful representations . In addition, deep learning with gradient descent scales linearly in time and space with the number of train cases, which makes it possible to apply to large scale data sets .

Unfortunately, little work has been done to leverage the advantages of deep learning for unsupervised clustering problems. Moreover, unsupervised clustering also presents a challenge in the deep learning framework, compared to supervised methods in the final fine-tuning process. Another important research topic in clustering analysis is how to adapt model complexity for increasing volumes in the era of big data . However, most approaches are generative models and have restrictions on the prior base measures.

In this paper, we are interested in clustering problems and propose a deep belief network (DBN) with nonparametric clustering. This approach is an unsupervised clustering method, inspired by the advances in unsupervised feature learning with DBN, as well as nonparametric Bayesian models . On the one hand, clustering performance depends heavily on data representation, which implies the need for feature learning in clustering. On the other hand, while the nonparametric Bayesian model can perform model selection and data clustering, it is intractable for non-conjugate prior; furthermore, it may not perform well on high-dimensional data, especially in terms of space and time complexity. Thus, we propose the deep learning with nonparametric maximum margin model for clustering analysis. Essentially, we first pre-train DBN for feature learning and dimension reduction. Then, we will learn the clustering weights discriminatively with nonparametric maximum margin clustering (NMMC), which can be updated online efficiently. Finally, we fine-tune the model parameters in the deep belief network. Refer to Fig. (1) for visual understanding to our model. Hence, our framework can handle high-dimensional input features with nonlinear mapping, and cluster large scale data sets with model selection using the online nonparametric clustering method.

Our contributions can be mainly summarized as: (1) leveraging unsupervised feature learning with DBN for clustering analysis; (2) a discriminative approach for nonparametric clustering under maximum margin framework. The experimental results show advantages of our model over competitive baselines.

Related work

Clustering has been an interesting research topic for decades, including a wide range of techniques, such as generative/discriminative and parametric/nonparametric approaches. As an discriminative method, maximum margin clustering (MMC) treats the label of each instance as a latent variable and uses SVM for clustering with large margins. However, they either cannot learn parameters online efficiently or need to define the number of clusters like other clustering approaches, such as k-means, Gaussian mixture model (GMM) and spectral clustering. Considering the weakness of parametric models mentioned above, many nonparametric methods have been proposed to handle the model complexity problems. One of the widely used nonparametric models for clustering is Dirichlet process mixture (DPM) . DPM can learn the number of mixture components without specified in advance, which can grow as new data come in. However, the behavior of the model is sensitive to the choice of prior base measure $G_{0}$. In addition, DPM of Gaussians need to calculate mean and covariance for each component, and update covariance with Cholesky decomposition, which may lead to high space and time complexity in high-dimensional data. Unsupervised feature learning with deep structures was first proposed in for dimension reduction. Later, this unsupervised approach was developed into semi-supervised embedding and supervised mapping scenarios. Many other supervised approaches also exploit deep learning for feature extraction and then learn a discriminative classifier with objectives, e.g., square loss , logistic regression or support vector machine (SVM) for classification in the code space. The success behind deep learning is that it can learn useful information for data visualization and classification . Thus, it is desirable to leverage deep learning for clustering analysis, because the performance for clustering depends heavily on data representation. Unfortunately, little attention has been paid to leveraging deep learning for unsupervised clustering problems.

A recent interesting approach is the implicit mixture of RBMs . Instead of modeling each component with Gaussian distribution, it models each component with RBM. It is formulated as a third-order Boltzmann machine with cluster label as the hidden variable for each instance. However, it also requires the number of clusters specified as input.

In this paper, we are interested in deep learning for unsupervised clustering problems. In our framework, we take advantage of deep learning for representation learning, which is helpful for clustering analysis. Moreover, we take an discriminative approach, namely nonparametric maximum margin clustering to infer model complexity online, without the prior measure assumption as DPM.

Deep learning with nonparametric maximum margin clustering

In this section, we will first review RBM and DBN for feature learning. Then, we will introduce nonparametric maximum margin clustering (NMMC) method given the feature learned from DBN. Finally, we will fine-tune our model given the clustering labels for the data.

And we can compute the following conditional likelihood:

A Deep Belief Network (DBN) is composed of stacked RBMs learned layer by layer greedily, where the top layer is an RBM and the lower layers can be interpreted as a directed sigmoid belief network , shown in Fig. (1). Suppose the DBN used here has L layers, and the weight for each layer is indicated as ${\bf W}_{i}$ for $i=\{1,..,\textrm{L}\}$. Specifically, we think RBM is a 1-layer DBN, with weight ${\bf W}_{1}$. Thus, DBN can learn parametric nonlinear mapping from input ${\bf v}$ to output ${\bf x}$, $f:{\bf v}\rightarrow{\bf x}$. For example, for 1-layer DBN, we have ${\bf x}=\textrm{logistic}({\bf W_{1}}^{T}{\bf v}+{\bf c})$. After we learn the representation for the data, we use NMCC for clustering analysis to model the data distribution.

2 Nonparametric maximum margin clustering

Nonparametric maximum margin clustering (NMMC) is a discriminative clustering model for clustering analysis. Given the nonlinear mapping with DBN, we can first map the original training data $\mathcal{D}=\{{\bf v}_{i}\}_{i=1}^{N}$ into codes $\mathcal{X}=\{{\bf x}_{i}\}_{i=1}^{N}$ in the embedding space. Then, with ${\bf\mathcal{X}}=\{{\bf x}_{i}\}_{i=1}^{N}$ and its the cluster indicators ${\bf z}=\{z_{i}\}_{i=1}^{N}$, we propose the following conditional probability for nonparametric clustering:

where $K$ is the number of clusters, $p({\bf x}_{i}|\boldsymbol{\theta}_{z_{i}})$ is the likelihood term defined in Sec. 3.2.1 and $p(\boldsymbol{\theta}_{k})$ can be thought as the Gaussian prior for $k=[1,...,K]$. Note that the prior $p(\boldsymbol{\theta}_{k})$ will be used in the maximum margin learning in Eq. (12). $p({\bf z})=\frac{\Gamma(\alpha)\prod_{k=1}^{K}\Gamma(n_{k}+\alpha/K)}{\Gamma(n+\alpha)\Gamma(\alpha/K)^{K}}$ is the symmetric Dirichlet prior, where $n_{k}$ is the number of element in the cluster $k$, and $\alpha$ is the concentration parameter.

Recall that Dirichlet process mixture (DPM) is the widely used nonparametric Bayesian approach for clustering analysis and model learning, specified with DP prior measure $G_{0}$ and $\alpha$. As a joint likelihood model, it has to model $p(\mathcal{X})$, which is intractable for non-conjugate prior. The essential difference between our model and DPM is that we maximize a conditional probability, instead of joint probability as in DPM . Moreover, our approach is a discriminative clustering model with component parameters learned under maximum margin framework.

To maximizing the objective function in Eq. (4), we hope the higher within-cluster correlation and lower correlation between different clusters. Given ${\bf z}$, we will need to learn $\{\boldsymbol{\theta}_{k}\}_{k=1}^{K}$ to keep each cluster as compact as possible, which in turn will help infer better $K$. In other words, to keep the objective climbing, we need higher likelihood $p({\bf x}_{i}|\boldsymbol{\theta}_{z_{i}})$ with higher correlation within-cluster, which can be addressed with discriminative clustering. Given the component parameters, $\{\boldsymbol{\theta}_{k}\}_{k=1}^{K}$, we need to decide the label for each element for better $K$. For each round (on the instance level), we use Gibbs sampling to infer $z_{i}$ for each instance ${\bf x}_{i}$, which in turn can be used to estimate $\{\boldsymbol{\theta}_{k}\}_{k=1}^{K}$ with online maximum margin learning. For each iteration (on the whole dataset), we also update $\alpha$ with adaptive rejection sampling .

Given the data points ${\bf\mathcal{X}}=\{{\bf x}_{i}\}_{i=1}^{N}$ and its the cluster indicators ${\bf z}=\{z_{i}\}_{i=1}^{N}$, the Gibbs sampling involves iterations that alternately draw samples from conditional probability while keeping other variables fixed. For each indicator variable $z_{i}$, we can derive its conditional posterior as follows:

In our conditional likelihood model, we define the following likelihood for instance ${\bf x}_{i}$

where $\lambda$ is a regularization constant to control weights between the two terms above. By default, the prediction function should be proportional to $\operatornamewithlimits{arg\,max}_{k}({\bf x}_{i}^{T}\boldsymbol{\theta}_{k})$, for $k\in[1,K]$. In other words, higher correlation between ${\bf x}_{i}$ and $\boldsymbol{\theta}_{k}$ indicates higher probability that ${\bf x}_{i}$ belongs to cluster $k$, which further leads to higher objective in Eq. (4). In our likelihood definition, we also subtract $\lambda||\boldsymbol{\theta}_{k}||^{2}$ in Eq. (9), which can keep the maximum margin beneficial properties in the model to separate clusters as far away as possible. Another understanding for the above likelihood is that Eq. (9) satisfies the general form of exponential families, which are functions solely of the chosen sufficient statistics . Thus, such probability assumption in Eq. (9) make it general to real applications.

Plug Eq. (9) into Eq. (8), we get the final Gibbs sampling strategy for our model

We will introduce online maximum margin learning for component parameters $\{\boldsymbol{\theta}_{k}\}_{k=1}^{K}$ in Sec 3.2.2. For the newly created cluster, we assume $\boldsymbol{\theta}_{K+1}$ is sampled from multivariate t-distribution.

2.2 Online maximum margin learning

We follow the passive aggressive algorithm (PA) below in order to learn component parameters in our discriminative model with maximum margins .

Following the passive aggressive (PA) algorithm , we optimize the objective function:

where the $l_{2}$ norm of $\mathbf{\Theta}$ on the right hand size can be thought as Gaussian prior in Eq. (4). If there’s loss, then the updates of PA-1 has the following closed form

3 Fine-tuning the model

Having determined the number of clusters and labels for all training data, we can take the fine-tuning process to refine the DBN parameters. Note that the objective function in Eq. (12) takes the $l_{1}$ hinge loss as in . Thus, one possible way is that we can take the sub-gradient and backpropagate the error to update DBN parameters. In our approach, we employ another method and only update the top layer weights ${\bf W}_{\textrm{L}}$ and $\mathbf{\Theta}$ in the deep structures. This fine-tuning process is inspired by the classification RBM for model refining. Basically, we assume the top DBN layer weight ${\bf W}_{\textrm{L}}$ and SVM weight $\mathbf{\Theta}$ can be combined into a classification RBM as in by maximizing the joint likelihood $p({\bf x},z)$ after we infer the cluster labels for all instances with NMMC. Note that there is mapping from SVM’s scores to probabilistic outputs with logistic function , which can maintain label consistency between the SVM classifier and the softmax function. Thus, the SVM weight $\mathbf{\Theta}$ can be used to initialize the weight of the softmax function in the classification RBM. After the fine-tuning process, we can $\max_{z}p(z|{\bf v})$ for $z\in[1,K]$ to label the unknown data ${\bf v}$. For 1-layer DBN, we can get the following classification probability:

where $d_{z}$ for $z\in[1,K]$ is the bias of clustering labels, and $c_{j}$ for $j\in[1,n]$ are biases of the hidden units. Note that $\mathbf{\Theta}$ has been reshaped into $n\times K$ matrix before updating in the fine-tuning process. For the deep neural network with more than one layer, we first project ${\bf v}$ into the coding space ${\bf x}$, then use the above equation for classification.

In our algorithm, we only fine-tune in the top layer because of the following reasons: (1) the objective function in Eq. (4) with deep feature learning is non-convex, which can be easily trapped into local minimum with L-BFGS ; (2) if there was clustering error in the top layer, it could be easily propagated in the backpropagation stage; (3) To only update the top layer can effectively handle the overfitting problem.

Experimental Results

In order to analyze our model, we performed clustering analysis on two types of data: images and documents, and compared our results to competitive baselines. For all experiments, including pre-training and fine-tuning, we set the learning rate as 0.1, the maximum epoch to be 100, and used CD-1 to learn the weights and biases in the deep belief network. We used the adjusted Rand Index to evaluate all the clustering results.

Clustering on MNIST dataset: The MNIST datasethttp://yann.lecun.com/exdb/mnist/ consists of $28\times 28$-size images of handwriting digits from through $9$ with a training set of 60,000 examples and a test set of 10,000 examples, and has been widely used to test character recognition methods. In the experiment, we randomly sample 5000 images from the training sets for parameter learning and 1000 examples from the testing sets to test our model. After learning the features with DBN in the pre-training stage, we used NMMC for clustering, with setting $\alpha=4$, $\lambda=15$ and $C=0.001$. In the experiment, $\lambda$ plays a vital role on the final number of clusters. Higher $\lambda$, larger number of clusters generated. To make an fair comparison, we basically tuned parameters to keep the number of generated clusters close to the groundtruth in the training stage. For example, in the MNIST experiment, we keep it around 5 to 20 in the training set for both NMMC and DPM. The results from baselines such as k-means and GMM should be conceived as upper bound (specify the number of clusters $K=10$).

The clustering performance of our method (DBN+NMMC) is shown in Table (1), where “pre-train” and “fine-tune” indicate how the accuracy changes before and after the fine-tuning process for the same parameter setting on the same dataset. The results with 2-layer DBN in Table (1) demonstrate that our method significantly outperforms baselines. It also shows that fine-tuning process can greatly improve accuracy, especially on the testing data. In Table (1), we think the largest train/test difference for the least complex model is caused by biases between before and after finetuning. In other words, the fine-tuning step can learn better biases via classification RBM and improve testing performance. We also visualize how the weights change before and after the fine-tuning process in Fig. (2).

We also evaluate how the depth and dimensionality of deep structures influence clustering accuracy. Fig. 3(a) shows how adjusted Rand Index changes with the number of dimensions for 1-layer DBN (or RBM), and it demonstrates that higher dimensionality does not mean higher performance. In Fig. 3(a), we can see fine-tuning severely hurt performance on the training set on higher dimension coding space, we guess it is caused by overfitting problem in the complex model. In other words, the wrong clustering prediction will deteriorate the clustering performance even further through fine-tuning. That makes sense because we treat the wrong labeling as the correct one in the fine-tuning stage. It also verifies that it is reasonable by just fine-tuning the model in the top layer, instead of the whole network, with the purpose to reduce the overfitting problem. Fig. 3(b) shows that given the 100 hidden nodes in the top layer, how the performance changes with the depth of DBN structure. It seems that the deeper complex model cannot guarantee better performance.

To verify whether our NMMC is effective for data clustering and model selection, we also compare our NMMC to DPM given the same DBN for feature learning. The results in Fig. (4) demonstrates that NMMC outperforms DPM significantly and also shows that our NMMC can always converge after 100 iterations. The time complexity comparison between our method and DPM is shown in Fig. 5 in the DBN projection space. It shows that our method is significantly efficient, compared to DPM. To manifest how effective our method is, we also show the upper bound DBN+GMM, with 2 layers $n=$ in Table (1). It shows that features learned with DBN are helpful for clustering, compared to raw data. It also shows that our method yields better clustering results than the upper bound.

Clustering on 20 newsgroup: We also evaluated our model on 20 newsgroup datasets for document categorization. This document dataset has 20 categories, which has been widely used in text categorization and document classification. In the experiment, we tested our model on the binary version of the 20 newsgroup datasethttp://www.cs.toronto.edu/~larocheh/public/datasets/20newsgroups/20newsgroups_{train,valid,test}_binary_5000_voc.txt. We used the training set for training and tested the model on the testing dataset. After we learned features in the DBN, we used NMMC for clustering, with setting $\alpha=4$, $\lambda=30$ and $C=0.001$. To make an fair comparison, we basically took a similar setting as in the MNIST dataset, for both NMMC and DPM in order to generate the number of clusters which is comparable for both methods. Baselines such as k-means and GMM should be thought of as upper bound because they need to specify the number of clusters $K=20$.

The clustering performance of our method (DBN+NMMC) on 20 newsgroups is shown in Table. (2). It also demonstrates that the fine-tuning process can greatly improve accuracy, especially on the testing data. Although our model cannot beat baselines on the training set, our model can achieve better evaluation performance on the testing set (better than GMM and k-means on the raw data clustering). To verify whether our NMMC is effective for data clustering and model selection, we also compare our NMMC to DPM given the same DBN for feature learning. The results in Fig. (6) demonstrate that NMMC outperforms DPM remarkably. To test how time complexity changes with respect to the number of dimensions in the projected space, we tried different coding spaces and compared our method with DPM, with results shown in Fig. 5. Again, it demonstrates our method is more efficient in practice.

To sum up, our model can converge well after 100 iterations from the experiments above. Moreover, the fine-tuning process in our model can greatly improve the performance on the test sets. Thus, it also shows that the parameters learned with NMMC can be embedded well in the deep structures.

Conclusion

Clustering is an important problem in machine learning and its performance highly depends on data representation. And, how to adapt the model complexity with data also pose a challenge. In this paper, we propose a deep belief network with nonparametric maximum margin clustering. This approach is inspired by recent advances of deep learning for representation learning. As an unsupervised method, our model leverages deep learning for feature learning and dimension reduction. Moreover, our approach with nonparametric maximum margin clustering (NMMC) is a discriminative clustering method, which can adapt model size automatically when data grows. In addition, the fine-tuning process can incorporate NMMC well in the deep structures. Thus, our approach can learn features for clustering and infer model complexity in an unified framework. We currently use DBN instead of deep autoencoders for fast feature learning because the latter is time-consuming for dimension reduction. In future work, we will explore deep autoencoders to learn better feature representation for clustering analysis. Another interesting topic to be explored is how to optimize the depth of deep learning structures in order to improve clustering performance.

References