Discriminative Bayesian Nonparametric Clustering

1 Introduction

Clustering is an exploratory data analysis task commonly encountered in machine learning and data mining. The ideal goal of clustering is to group data points into clusters in such a way that data points within a cluster are similar (minimize intra-distance) and at the same time, clusters are as separated as possible (maximize inter-distance). Separated clusters often result in distinct and more interpretable clusters and the number of clusters are smaller. Previous work has argued that discriminative clustering is desirable in various tasks, e.g., subspace selection analysis [De la Torre and Kanade, 2006; Ye et al., 2008], computer vision [Joulin et al., 2010], unsupervised regression [Krause et al., 2010] and factor modeling [Henao et al., 2014].

As the number of clusters is often unknown and growing over time, modern Bayesian nonparametric (BNP) clustering methods have the advantages of automatically identifying the suitable number of clusters - most popular models include the Dirichlet process mixture models (DPM) [Ferguson, 1973;

Antoniak, 1974; Sethuraman, 1994; Ghahramani, 2012]. While DPM and models alike have been successful, they are strictly generative and the clustering outcomes favor the similarity of data points within a cluster, but do not explicitly model the discrimination among clusters. We consider in this paper discriminative clustering [Kaski et al., 2005; Ye et al., 2008; Krause et al., 2010; Chen et al., 2014] under the formalism of Bayesian nonparametrics where data points in the same cluster not only promote to be similar, but also be discriminated from other data points from other clusters.

To achieve this goal, we propose a general framework called the discriminative Bayesian nonparametric clustering. In our framework, the joint strength of BNP clustering and discriminative modeling is achieved by enforcing the latent cluster indices resulted from BNP clustering process to be consistent with the discriminative decisions or labels predicted by the Bayesian discriminative model. This allows our models to have a clear generative process and the flexibility to choose discriminative loss functions, e.g., logistic loss (as in logistic regression) or hinge-loss (as in SVM). Using the proposed framework, we develop two novel unsupervised discriminative BNP variants: the discriminative Dirichlet process mixtures (DDPM) for i.i.d data, and the discriminativestate infinite HMMs (DIH) for sequential data. For inference, our posterior nicely turns out to be similar to the Chinese restaurant process in DPM but with an additional (discriminative) likelihood ratio term. To efficiently handle the discriminative loss function, we employ data-augmentation sampling technique proposed in [Polson et al., 2011; Polson et al., 2013]. Together, our inference procedure reduces to an efficient data-augmentation Gibbs-sampler.

The idea of learning a latent structure to solve the problem of a supervised discriminative task has been investigated before (e.g., [Zhu et al., 2014; Li et al., 2014; Chen et al., 2014]). These works were built on the regularized posterior Bayesian principle, introducing constraints into (generative) Bayesian models for classification tasks, as well as for supervised sequential labeling problems [Zhang et al., 2014]. In contrast, our work focuses purely on unsupervised tasks for both i.i.d and sequential data.

Among others, the closest work to ours is the DP Maxmargin GMM [Chen et al., 2014]. This regularized model combines a multi-class setting with a standard posterior of a Bayesian nonparametric clustering models for i.i.d data. In contrast, our model is derived by directly enforcing consistency between a generative BNP component with a probabilistic discriminative one. Furthermore, our model can readily incorporate any discriminative loss such as the logistic loss or the hinge-loss by turning them into likelihood; it also simplifies the inference procedure. Lastly, beyond the work of [Chen et al., 2014], our discriminative-state infinite HMMs is designed to handle sequential data.

To demonstrate the benefit of our models, we experiment with two different tasks in two domains: image clustering (for clustering task) and dynamic location clustering from user WiFi usage (for sequential state-space clustering task). Our experimental results demonstrate that the additional discriminative aspect of our models offers important benefits: not only that it discovers more discriminative clusters, it also enhances the quality of clustering in comparison with the traditional generative BNP models.

2 Data Augmentation

We first briefly review the data augmentation method for Bayesian discriminative models [Polson et al., 2011; Polson et al., 2013] which has received great interest recently [Nguyen et al., 2016a; Nguyen et al., 2016b]. Let xi ∈ RD be a feature vector and yi ∈ {-1, 1} be a corresponding observed label.

2.1 Bayesian Support Vector Machine

Minimizing the regularized Hinge-loss objective function for a standard SVM L (h;C) = � N i=1 2max {1 - yih T xi , 0} + C||h ||2 2 (where h is the vector of coefficient parameters and C > 0 is the regularization hyper-parameter) is equivalent to a MAP estimation for the following pseudo-posterior distribution parameterized by h due to the monotonic property of the exponential ˆhMAP = argmax p(h | x,y,C) where

h

Thus, p(yi | xi,h) � exp {-2max (1-yih T xi,0)} can be viewed as the likelihood and p(h | C) � exp {-C||h||2 2} as a prior distribution over h; this is a Gaussian form, i.e., p (h | C) = N (m0, S0) with mean m0 = 0 and S0 = wI where w= 1 2C .

In a Bayesian setting, we would like to sample from Eq. (1). However, the likelihood term renders it difficult to achieve this goal. The key idea from [Polson et al., 2011] is to augment each data point xi with an auxiliary variables li > 0 so that the individual likelihood term can be written as

The term inside the integral can then be viewed as the joint distribution p(yi,li | xi,h) (over which marginalizing li will recover the likelihood for yi). Thus, the posterior p(h | x,y,C) can be viewed as the marginal from a joint posterior with the auxiliary variables

Gibbs sampling can now be used on this joint posterior by sequentially sampling h given li and vice versa.

3 Discriminative BNP Clustering

We present the proposed discriminative clustering in this section. We first describe our framework for exchangeable data, and then for sequential data, which extend the Dirichlet process mixture (DPM) [Antoniak, 1974] and the infinite hidden Markov model (iHMM) [Beal et al., 2002] with discriminative power.

3.1 Discriminative DPM

Fig. 1 presents the graphical model representation for our proposed discriminative Dirichlet process mixture (DDPM). We start with the set of N data points {x1, . . . ,xN} assumed to be exchangeable where xi ∈ RD . Our goal is to cluster them into K clusters through the indicators zi. The number of active clusters K is unknown and will be determined given the data setting. Given the concentration parameter a > 0, we generate the infinite mixing proportion p ∼ Stick(a) and

the cluster label for each data point zi iid ∼ Mult(p), ∀i = 1, .., N. Then, we randomly draw a collection of topic atoms as fk iid ∼ H(w) and the corresponding data observation xi ∼ F (fzi ). This part of the model is identical to a DPM [Antoniak, 1974]. To introduce discrimination, for each cluster, we randomly generate the hyperplane hk iid ∼ N (m0,S0) whose purpose is to separate cluster k from the other clusters. For each data point, we further introduce the random vector yi = [yi1, ...,yiK,yiKnew ]. Each variable yik ∈ {1,-1} has two parents xi and hk (cf. Fig. 1) where yik = 1 indicates that xi lies in the positive half of hk so that p(yik | xi,hk)

In a traditional discriminative setting, during training yi∗ will be observed as a one hot encoding 1 of the label; and during testing the predicted value is computed as ˆk = argmax p(yik = 1 | xi,hk).

k However, our model is unsupervised, therefore y is not observed. To connect and ensure the consistency of the generative and the discriminative components in our model, we additionally introduce the consistency variable ci. Specifically, ci =1 if yi and zi are consistent in the sense that yizi =1

1 One hot vector has the usual form [0,...,1,...0] while this one has the form [-1,...1,...-1].

and yil =-1,∀l ̸= zi and ci = 0 otherwise. To force the consistency between yi and zi, ci is clamped to 1. As a result, the variable yi will be equated to the one-hot encoding of zi. Hence, there is a dual view of yi: (a) as the hidden mixture component that the data point xi is assigned to, and (b) as the target for separation by the discriminative component (either a Bayesian SVM or a Bayesian LR).

Given ci = 1 and zi = k, we can rewrite the discriminative likelihood for simplicity as p (yi∗ = [-1, ..., 1(k), ...,-1] | xi, zi = k, h, ci = 1) =

where Z = � K+1 l=1 p(yil =-1 | xi,hl). For a new cluster, we

sample hk from its prior.

The introduction of the consistency variable ci is the most crucial part of our model as it provides the glue between the generative and the discriminative components. The truthvalue conveyed by ci (true or false) simply reflects whether the generative component is consistent with the discriminative component. Viewing this way, it is natural to clamp ci to true since the generative and the discriminative components are then forced to be consistent. There is also a rejectionsampling semantic for our model where the ci is obtained randomly, but only those samples where ci = 1 are retained.

Posterior inference

We use collapsed and augmented Gibbs sampler for posterior inference where we integrate out p and fk under conjugacy property. Note that all probabilities are conditioned on ci = 1, and hence yi∗ is a one hot encoding of zi. Thus, we do not need to sample yi∗ when zi is known.

The variables which need to be sampled include zi, li, ∀i = 1, ...,N and the discriminative hyperplane hk,∀k = 1, ...,K. Particularly, we provide the posterior inference of li and hk for two discriminative cases of SVM and LR, respectively.

Sampling hk. Given data points in cluster k {xi | zi = k} and data points in other clusters {x j | z j ̸= k}, the conditional distribution of the discriminative hyperplane hk (with the prior distribution hk ∼N (m0,S0)), is

Using data augmentation technique (cf. Sec. 2), the conditional distribution of hk has the form N (hk | mN,SN). For discriminative setting with SVM, we have S-1 N = m0S-1 0 + � N i=1 xi x T i li and mN =SN (� N i=1 li+1 li xiyik ). For LR case, S-1 N = m0S-1 0 +� N i=1 lixix T i and mN =SN (� N i=1 1 2 xiyik + S-1 0 m0 ). To sample hk ∼ N (mN,SN), we compute S-1 N from the data, but not SN. To avoid computational inefficiency of matrix inversion, we compute mN by solving the system of linear equations with the complexity of O (D 2.376 ) [Ambainis and Filmus, 2014] where D is the feature dimension.

Sampling li. We sample the auxiliary variable as follows: l -1 i ∼ IG (∣∣1-x T i hzi ∣∣-1 ,1) for SVM and li ∼ PG (1, x T i hzi ) for LR.

Sampling zi. Using the graphical model for DDPM in Fig. 1, the conditional distribution for sampling zi is p(zi = k | ci =1,x,z-i,h,y,a,H) � p(zi = k | z-i,a,xi,x-i,H) p(yi∗ | ci =1,zi = k,hk,xi)

The first term corresponds to a standard Chinese restaurant process (CRP). The second term is the similarity likelihood, reflecting the similarity of xi w.r.t. other data points

{x j | z j = k,∀ j ̸= i} in cluster k. Here, we utilize the conjugacy property to integrate out the parameter fk. The final term is the discriminative likelihood of the observation xi (defined in Eq. (3)) which is high if xi lies on the positive half of hk and low vice versa.

3.2 Discriminative-state Infinite HMM

The iHMM [Beal et al., 2002], also known as the HDP-HMM [Teh et al., 2006], is developed to identify the suitable number of states (clusters) for sequential data. Based on the HDPHMM and the discriminative clustering framework proposed earlier, we develop the discriminative-state infinite hidden Markov model (DIH) to perform discriminative clustering on sequential data. The use of Markov property ensures that the temporal dynamics nature of the data is taken into consideration. We again introduce the variables yik, ci for each observation (cf. Fig. 1 Right) and the discriminative hyperplane hk for capturing the discrimination between clusters.

Sampling zi. We follow Eq. (5) to derive the posterior inference over zi as follows p(zi = k | .) �

The first term is the discriminative likelihood, defined in Eq. (3) where yik = 1 only at zi = k and yil = -1 otherwise. The second term is the similarity likelihood of the observation xi in cluster k where the atom component fzi is integrated out. The third term is the CRP for Markov transition p(zi = k | z-i,a,b)

where ni, j is the number of transitions from state i to state j and ni,∗ is for all transitions from state i.

Sampling li and hk. Similar to the approach presented in Section 3.1 for DDPM.

4 Experiments

We aim to illustrate that our models can reasonably estimate the unknown number of discriminative clusters and improve the clustering performance.

Experimental setup. All experiments are running in the same Windows machine Core i7, 16GB of RAM. The implementation of the proposed model and the baselines are in Matlab. Throughout the experiments, the prior distribution for hk is set as p(hk | m0,S0) ∼N (0,I). We use symmetric Dirichlet with parameter 0.01. We set the hyperparameters as a,g ∼Gamma(1,1), then we resample them in each iteration (for robustness) following the approaches presented in [Escobar and West, 1995; Teh et al., 2006].

To have a good initialization for each discriminative models, in the first 10 iterations of the collapsed Gibbs sampler, we run our proposed models without using discriminative property. We call our discriminative DPM with SVM (DDPM-S) and with LR (DDPM-L). Similarly, DIH-S and DIH-L refer to the two variants of discriminative state iHMM. For evaluation, the clustering scores are measured using 10 independent runs, for each run we record the results from the last 5 Gibbs samples to reduce the sensitivity of MCMC.

4.1 DDPM for Data Clustering

We conduct experiments for DDPM on synthetic linear-shape Gaussian 2D data and image clustering task where the data include a collection of i.i.d. observations.

Synthetic experiment

We offer a simple illustration to understand the advantage of discriminative clustering (against the standard clustering methods) in Fig. 2. DDPM-S and DDPM-L recover correctly K = 2 clusters while DPM cannot recover the true clusters. Both DDPM and DPM use Gaussian likelihood to encourage the similarity of data points within a cluster. In addition, the discriminative hyperplane hk in DDPM helps to separate data points in the k-th cluster to be away from other clusters. This property makes the algorithm converge to a fewer number of clusters while gaining better clustering performance. We note that if we exhaustively tune the covariance of the Gaussian distribution, DPMmight estimate these clusters correctly; whereas our model achieves this with minimum effort.

Image clustering

We evaluate DDPM on image clustering using NUS Wide (K=13, N=3411, D=500), Fifteen Scenes (K=15, N=2245, D=128) and MNIST (K=10, N=1000, D=784) datasets where K is the number of true cluster, N is the number of data points and D is the feature dimension. We use SIFT histogram as a feature which is assumed to follow Multinomial distribution [Nguyen et al., 2014; Nguyen et al., 2015].

We compare our models with the existing methods:

DPM [Antoniak, 1974]: we use the same configuration with our proposed model.

MMGM [Chen et al., 2014]: Since Gaussian-Wishart for high dimensional count data of SIFT vectors is not effective, we use Multinomial-Dirichlet likelihood.

DPmeans [Kulis and Jordan, 2012]: We follow [Kulis and Jordan, 2012] method to select l using farthest-first heuristic where the expected number of cluster is set to 17 to estimate l . This yields l = 5690.

K-means, GMM and AP [Frey and Dueck, 2007]: We use Matlab built-in function with Euclidean distance. As Kmeans and GMM require the number of clusters provided in advance, we vary the number of clusters from 10 to 25, then report the mean and standard deviation.

Table 1 shows the clustering results. DP-means [Kulis and Jordan, 2012] achieves much lower scores than DPM and DDPM in clustering quality. DP-means uses small-variance asymptotic analysis and uses the mean of the data to represent a center. This trade-off assumption makes the DP-means deterministic as traditional k-means, hence run faster, but it degrades the clustering performance. GMM and Kmeans require the number of clusters provided in advance. To have a fair comparison with other BNP approaches which can identify the suitable number of clusters, we vary the number of clusters used in GMM and Kmeans, then report the mean and standard deviation. Our discriminative models consistently achieve the best clustering quality as they outperform the other baselines in all NMI and F1-score. Among our two discriminative variants, DDPM-S with the hinge loss performs slightly better than DDPM-L with the logistic loss.

Our model also outperforms MMGM in clustering accuracy (cf. Table 1) and computationally more efficient. MMGM [Chen et al., 2014] requires heavier computation than our models due to its max-margin multiclass formulation that uses the Reused Algorithm to jointly estimate two variables: the best and the second best label assignments. The complexity is hence roughly quadratic in the number of current clusters O (K 2 ), while sampling zi in our model only takes O(K).

Model analysis

We study the sensitivity of our discriminative model through the parameter S0 which plays an interesting role in controlling our model discriminative property. Let S0 = w×I for w>0. As w→0 (cf. Eq. (4)),∀k, hk approaches zero; hence there is no effect of discrimination, and our model reduces to the standard generative model of DPM. As w increases, the norm of h is also likely to increase, making the discrimination effect stronger.

We vary the value of w and measure performance on the NUS Wide dataset. As can be seen from Fig. 3, the NMI score increases as soon as a small discriminative factor is introduced (w = 10-6 ). In terms of the number of clusters, when we force our model to be more discriminative, our DDPM tends to get less clusters, reducing K from 19 to 17. We also notice the robustness of our model in the choice of S0. For a wide range of w ∈ [10-6 ,10 1 ], our model consistently obtains better performance than the DPM.

4.2 DIH for Time-Series Analysis

We evaluate the proposed discriminative-state iHMM using sequential data on location dynamic discovery from the MDC dataset [Laurila et al., 2012]. We pick three users, denoted as A, B and C. Each user has the WiFi access points recorded overtime using a smart phone.

We aim to discover the sequence of routine locations of each user. Each inferred location is represented in our model a state or a cluster of WiFi usage patterns. The clustering performance is then measured using the ground truth provided. We compare discriminative-state iHMM (DIH-S and DIH-L) with the iHMM, as well as models for i.i.d. data (DDPM and DPM). Our main competitor is the iHMM [Beal et al., 2002] which utilizes the Markov property to exploit the sequential dependency and can identify the suitable number of clusters for time series data.

The clustering performance is reported in Table 2. The results show that our discriminative-state iHMMs consistently outperforms the standard iHMM. The DIH-S performs slightly better than DIH-L, and is generally the best method against all the baselines.

We further illustrate the advantage of our discriminative models by visualizing how the clustering performance (F1score) improves as a function of CPU times in Fig. 4. Since our method might take longer time in each Gibbs iteration comparing to the iHMM, to have a fair comparison, we take the time spent per iteration into the assessment. We observe that our discriminative iHMM take less time to achieve a sufficiently good and stable clustering result. Although not definitive, this behavior suggests that the augmented Gibbs sampler developed for our discriminative iHMM is mixing just as well as the collapsed Gibbs sampler on iHMM, if not faster.

5 Conclusion

Extending current generative nonparametric Bayesian clustering models, we proposed a novel framework for discriminative Bayesian nonparametric clustering. Our framework introduces a discriminative component into the existing generative models by enforcing consistency between the generative clusters and the self-induced discriminative labels. This results in two new discriminative BNP clustering models: discriminative DPM and discriminative-state iHMM suitable for i.i.d. and sequential data respectively. By employing a recent data-augmented Gibbs sampler technique for Bayesian probabilistic discriminative classification models (i.e., SVM and LR), we further developed an efficient inference algorithms for our models. Under the new framework, we automatically identify the (unknown) number of clusters while encouraging the similarity within a cluster as well as the separation between the clusters. Experiments with image clustering and sequential WiFi data clustering tasks demonstrated that our model consistently improved in clustering quality compared to existing methods. To scale up this framework, our future work is readily applicable to use recent advances in scalable inference for BNP such as stochastic variational techniques.

Acknowledgements

This work was partially supported by the Australian Research Council (ARC) and the CoE in Machine Learning and Big Data.