Semi-supervised Max-margin Topic Model with Manifold Posterior Regularization

1 Introduction

Supervised topic models have been applied in various tasks by discovering latent topic structures and meanwhile predicting interpretable labels, including document classification [Zhu et al., 2012], image classification [Wang et al., 2009], etc. The popular models include supervised LDA (sLDA) [Blei and McAuliffe, 2007], discriminative LDA (DiscLDA) [Lacoste-Julien et al., 2008], Labeled LDA [Ramage et al., 2009] and max-margin LDA (MedLDA) [Zhu et al., 2012]. By incorporating document labels, supervised topic models can capture high-level information and provide guidance to predict meaningful latent topic patterns. However, human-labeling is often costly, especially for a large corpus, which limits the further applicability of the supervised topic models. It is imperative to incorporate a fraction of labeled documents with the massive unlabeled documents to conduct the latent topic modeling and document classification in a semi-supervised learning (SSL) manner [Chapelle et al., 2006].

∗The work is supported by National 973 Project (2013CB329403), NSFC Projects (Nos. 61620106010, 61621136008, 61332007, 61571261), the Youth Top-notch Talent Support Program and the Collaborative Project from MSRA.

Various efforts have been made to build semi-supervised topic models (SSTMs). For example, Zhuang et al. [2013] first learn an sLDA model by using labeled data only, then predict labels for the unlabeled documents using the learned sLDA, and finally refine the labels by solving a low-rank graph regularized problem. This method adopts a loose coupling between the classifier and the topic model, which leads to a waste of the unlabeled documents when learning topics. Lu et al. [2013] and Zhang et al. [2014] use both labeled and unlabeled documents in learning the latent topics; discriminative topic modeling (DTM) [Huh and Fienberg, 2012] trains an unsupervised manifold regularized PLSA model [Cai et al., 2009], and then builds a subsequent SVM classifier based on the learned topic representations. However, the unlabeled documents are not taken into consideration for these algorithms when building the classifiers, which restricts the classification performance.

Other semi-supervised topic models have been built based on some miscellaneous document supervision, such as the partially-labeled topic assignments [Ramage et al., 2011] or a complex hierarchical topic structure [Mao et al., 2012]. More recently, in some models with deep architectures, unlabeled documents are used for pre-training before using a supervised CNN [Johnson and Zhang, 2015] or LSTM [Johnson and Zhang, 2016]. However, the performance of deep models is largely depending on plenty of labeled documents.

1.1 Our Proposal

In this paper, we propose a semi-supervised topic model with manifold posterior regularization. Specifically, we introduce the manifold regularization to the posterior of a supervised topic model under the generic regularized Bayesian inference (RegBayes) [Zhu et al., 2014b] framework, such that the close samples in the bag-of-words feature domain would have the similar topic representation and predicted labels. We build a tight-coupling model that learns latent topics and classifiers with both labeled and unlabeled documents. With the tight coupling, our semi-supervised model jointly discovers discriminative topic representations and builds powerful classifiers.

However, the algorithms based on graph Laplacian regularization generally scale poorly with the data size. To address this issue, we present an efficient stochastic gradient Markov chain Monte Carlo (MCMC) to infer the model. In each iteration, only a small subset of the data is used, reducing the computational cost significantly.

In summary, our contributions are as follows

• We introduce manifold posterior regularization for latent topic models, which can incorporate both the labeled and unlabeled data via manifold learning;
• We build a Laplacian MedLDA model, a semisupervised max-margin topic model with manifold posterior regularization, under the RegBayes framework, such that the induced model has a tight coupling between the latent topic modeling and the max-margin classifier;
• We develop a stochastic gradient MCMC method for the efficient inference of our model.

We summarize the merits of our model in Table. 1, and compare it with the representative (topic) models.

2 Preliminaries

We review the manifold regularization method for semisupervised learning as well as the max-margin supervised topic model.

2.1 Manifold Regularization

The manifold regularization methodology was popularized in machine learning by Laplacian Eigenmap [Belkin and Niyogi, 2001], a representative dimensionality reduction method. Later on, manifold regularization has been used for semi-supervised learning (SSL) and served as a regularization term in existing empirical loss minimization schemes [Belkin et al., 2006]. Manifold regularization assumes that the learned manifolds should be smooth, which means nearby data pairs have similar prediction scores.

Specifically, for a set of training instances X = {xi}l+u i=1 , where xi ∈ Rd , we only have a part of the instance labels Y = {yi}li=1 , where yi ∈ {-1, 1}. The goal of SSL is to learn an unknown function f that can fit well to the observed labels while having nice properties on the unlabeled instances. In particular, the manifold regularization SSL solves the problem

where V is some loss function (e.g., squared loss or hinge loss), Ω(f) is a structural penalty of the classifier f, c1 and c2 are the regularization parameters, and the manifold regularization term is defined as ∑l+u i,j=1 (f(xi) - f(xj))2wij =

f ⊤Lf , which represents graph smoothness. The weight wij is a pairwise similarity between samples i and j; and L is the graph Laplacian which is analogous to the Laplace-Beltrami operator on manifolds. Particularly, this method is Laplacian SVM (LapSVM) [Belkin et al., 2006], when V is set as the hinge loss function max[0, 1 - yif(xi)].

2.2 MedLDA

Max-margin topic model [Zhu et al., 2012] is a popular supervised topic model, which can be formulated as a regularized Bayesian (RegBayes) method [Zhu et al., 2014b] with a max-margin posterior regularization. Specifically, MedLDA consists of two parts: 1) a latent Dirichlet allocation (LDA) model for modeling the latent topic structures of the corpus and 2) a max-margin classifier for predicting document labels.

LDA [Blei et al., 2003] is a hierarchical Bayesian model that uses an admixture of topics as a latent document representation. Let Φ = {Φk}Kk=1 be a set of K topics, in which each topic Φk is a multinomial distribution with a symmetric Dirichlet prior Dir(β) over a V -word vocabulary. For a single document i with Ni words, the generative process of the vanilla LDA is:

1. Draw a topic proportion θi ∼ Dir(α),
2. For each word n (1 ≤ n ≤ Ni):
3. (a) Draw a topic assignment zin ∼ Multinomial(θi),
4. (b) Draw a word win ∼ Multinomial(Φzin ).

Given a set of documents X = {xi}li=1 , we denote the collection of latent topic proportions as Θ = {θi}li=1 and topic assignments as Z = {zi}li=1 where xi = {win}Ni n=1 and zi = {zin}Ni n=1 .

MedLDA is a supervised model that builds a classifier on the latent topic representations and in this paper we use the Gibbs classifier formulation to define our model, which is proven to have good generalization performance [McAllester, 2003; Germain et al., 2009]. With the posterior samples of Z, we can get the average topic assignments of the words in document i as ¯ zi, with element ¯ zik = 1 Ni ∑Ni n=1 I(zin = k)1 . Then we predict the document label yi,

where η is the vector of classifier weights; and sgn(·) is the sign function. We define the corresponding expected hinge loss

1 I(·) is the indicator function that equals 1 if the predicate holds otherwise 0.

where we take expectation over q(η,Θ,Z,Φ) to consider the uncertainty of latent variables and ℓ(≥ 1) is the cost of making a wrong prediction. By optimizing a variationalreformulated objective, the MedLDA model solves the RegBayes problem:

where q is the target posterior distribution; L(·) is the variational objective of the vanilla topic model; c1 is the positive regularization parameter. In this way, we define the MedLDA model under the Gibbs classifier formulation, named Gibbs MedLDA. We refer readers to [Zhu et al., 2014a] for more details of Gibbs MedLDA.

By solving problem (4), we get the unnormalized posterior distribution as:

where ψ1 is the unnormalized likelihood of the supervised signal,

Inference can be implemented by Gibbs sampling with data augmentation [Zhu et al., 2014a], a fast Gibbs sampler [Zheng et al., 2015] and stochastic gradient MCMC method [Hu et al., 2017].

3 LaplacianMedLDA

We now formalize our Laplacian MedLDA (LapMedLDA) to learn latent topics and document classifiers with labeled and unlabeled documents. We also present a stochastic gradient MCMCmethod for fast inference.

3.1 Formulation of LaplacianMedLDA

For semi-supervised document classification, we have a set of partially-labeled documents {X= {xi}l+u i=1 , Y = {yi}li=1} and aim to infer the labels for unlabeled data. To incorporate the useful information of the unlabeled documents, we directly use the discriminant function score to build a regularization term R2(q). In the Gibbs classifier formulation, we take expectation over the target posterior q and define the manifold regularization loss as,

where wij denotes the pairwise similarity between the bagof-words vectors of documents i and j; L is the Laplacian matrix of the neighborhood graph derived from W = [wij]; f = ¯ Z ⊤η is the prediction score vector; and ¯ Z is the latent topic assignment matrix with the i-the column being ¯ zi. This regularization encourages that if two documents are close to each other on the graph, they should have similar latent representations and hence similar prediction labels.

We use the manifold regularization in Eqn. (7) as a posterior regularization term, yielding the following regularized Bayesian model:

where f is the discriminant function as in MedLDA; L is the variational objective for the vanilla topic model with both labeled and unlabeled documents; c2 is another positive regularization parameter; R1 and R2 are corresponding to the max-margin regularization and manifold regularization, respectively.

By solving the problem (8), we get the unnormalized posterior distribution of LapMedLDA as

where ψ2 is the unmormalized likelihood of the graph Laplacian:

Note the normalizing term for the above posterior distribution can be omitted in the Gibbs sampling and the stochastic gradient MCMC steps. LapMedLDA captures not only the max-margin supervision of the document labels but also the manifold structure of the documents. Compared with the previous work on the likelihood manifold regularized topic models [Cai et al., 2009; Huh and Fienberg, 2012], our manifold posterior regularization is more direct and has a tight coupling between the unlabeled data and the classifiers, which brings the better latent topic representation and classification performance.

Note that the latent modeling of Z can be regarded as a non-linear feature extractor from the raw bag-of-words feature, and it allows us to use the linear kernel for the RKHS hypothesis space. In this case, our model does not include any sensitive parameter, such as the polynomial order for the polynomial kernel and the scale parameter for the RBF kernel.

In particular, when c2 = 0, the manifold regularization is actually unused and unlabeled data is only used in the generative topic modeling. Our model degenerates to a naive version of semi-supervised max-margin topic model, which is called SS-MedLDA.

3.2 Stochastic Gradient MCMC for LapMedLDA

Due to the tight coupling of the max-margin loss and manifold regularization, previous Gibbs sampling methods with data augmentation [Zhu et al., 2014a] cannot be directly applied. Moreover, it is hard to store and compute the pairwise similarities of the neighborhood graph for large-scale datasets. Therefore, it is imperative to develop a fast inference method. In this section, we present a stochastic gradient MCMC method for LapMedLDA.

In each iteration, we first calculate the expectation of the latent topic assignments from the conditional distribution q(Z|W, Φ, η, L, α) and then use them to update the posterior parameter η and Φ via the stochastic gradient Riemannian MCMC.

To speed up the inference procedure, we collapse out Θ and get the collapsed generative distribution of our model as

where

Cik· is the number of words in document i that are assigned to topic k and Cikv is the number of word v in document i that are assigned to topic k. We draw posterior samples from the collapsed posterior distribution q(Φ, η|X, Y, α, β, L) and update η and Φ by turns. Using a randomly-drawn document subset ˜X, we get the unbiased noisy estimate of the gradients of the log posterior of Φ with respect to Φ as

and then we update the Φ using stochastic gradient Riemannian Langevin dynamics [Patterson and Teh, 2013].

Similarly, we also get the unbiased stochastic estimate of the log posterior gradient of η with respect to η as

where the subgradient ∂ ∂η logψ1(yi|zi, η) equals -c1¯ zi if ψ1(yi|zi, η) < 1 and 0 otherwise; we also calculate the stochastic gradient of ψ2 with respect to η, yielding ∂ ∂η logψ2 as

where the matrix subscript(s) # represent the matrix slicing with the indexes of the minibatch ˜X, either the onedimensional for Z or two-dimensional for L. Then, we use SGLD steps to update η [Welling and Teh, 2011].

Note that the matrix slice for L indicates that in each iteration, we only use part of the documents and their neighborhood information, which means that we use a subgraph in each iteration. This process will be detailed in Sec. 3.4.

To calculate the expectation of ¯ z to get the observed counts in the above posterior gradients, the Gibbs sampling iterations for the topic assignments of word n in document i is as

where zi,-n is the topic assignments of other documents, ¯ z∗ i is the average topic assignments ¯ zi after setting topic zin as k and C -n ik· is the number of words assignment as topic k in document i after removing word n.

3.3 Multi-Class Extension

In many applications, document labels are multi-class and we present a multi-class extension of our model. The multi-class hinge-loss ρ(yi, ¯ zi, η) is defined as [Crammer and Singer, 2001],

where f(y, ¯ zi) = η⊤ y ¯ zi, y ∈ {1, 2, · · · , γ}, η is a γ × K matrix and ηy is the y-th row of the matrix η. We now retain the LDA model part L(q) in the LapMedLDA model (Eqn. (8)), and give the multi-class regularizations (γ-class) as,

With the regularizations for the multi-class setting, we get the similar collapsed posterior as Eqn. (10) with the unnormalized pseudo likelihoods, ψ1(yi|zi, η) and ψ2 as,

The log-posterior gradient with respect to Φ are identical to that of the binary case. Now we give the subgradients of the unnormalized likelihood ψ1 with respect to η as,

where y∗ = argmaxy̸=y η⊤ ¯ zi. The subgradient of logψ2 with respect to η is identical to Eqn. (14) with η being a γ×K matrix. With the posterior stochastic gradients, we can use SGRLD and SGLD to sample Φ and η.

3.4 Graph Construction

For every data point pair, we first construct the pair-wise similarities using the cosine distances of the bag-of-word vectors and remain the r nearest neighbors. The similarities between two documents are defined as:

where ∆r(x) is the set of r nearest neighbors of x. Moreover, we further utilize the label information by adding the edges of documents in the same categories and removing the edges of documents in the different categories. For the practical useage, we choose the symmetric normalized Laplacian matrix to normalize the node degrees. Similiar graph construction methods were used in [Huh and Fienberg, 2012; Cai et al., 2009].

In the stochastic gradient MCMC method, we use one tiny minibatch in each iteration. For each minibatch, we extracted the corresponding subgraph that consists of the pair-wise similarities between the data instances in the minibatch. The merit of this method is that we do not need to build and store a large pair-wise graph in advance. Our subgraph construction is related to the online manifold regularization in the streaming setting [Goldberg et al., 2008].

4 Experiments

We now present the empirical results of our semi-supervised topic model. We first present the document classification performance and the efficiency analysis of our model. Then we show the qualitative analysis .

4.1 Datasets and Experimental Setup

We compare our model with several state-of-the-art document classification models. The involved supervised models are linear-SVM (SVM), MedLDA and LDA+SVM. These three methods use labeled documents and for LDA+SVM, unlabeled documents are also used in the generative topic model part. The involved semi-supervised models are transductive SVM (TSVM), Laplacian SVM (LapSVM), discriminative topic modeling (DTM), SS-MedLDA and LapMedLDA. The SVM, TSVM and LapSVM methods directly use the bag-ofword feature as the input features.

We consider a binary document set which consists of two subgroups of the 20Newsgroups data 2 , alt.atheism and talk.religion.misc. This sub-dataset consists of 856 training documents and 569 testing documents. Next we test the multi-class model on the Yahoo! News K-series 3 and the whole 20Newsgroups data. The 20Newsgroups and Yahoo! News K-series datasets have 18,274 and 2,340 documents respectively.

We use random label discards to construct a partially labeled corpus. At every single test, we randomly discard part of the training document labels, which follows a binomial distribution with a parameter called label ratio. For example, when label ratio is 0.1, we randomly discard every existing document with probability 0.9. All the testing accuracy performances are averaged over 100 repetitions.

Since the classification performance of MedLDA is insensitive to the hyper-parameters in a wide range [Zhu et al., 2014a] and we use the same hyper-parameter setting of MedLDA. For LDA-based models, we set α = 1, β = 1 and topic number K = 20. For MedLDA-based models, we set ℓ = 164 and c1 = 1. The parameter c2 is the regularization parameter for the manifold regularization which is chosen from {0.1, 0.01, 0.001} via 5-fold cross validation. The expectation of the topic assignments ¯Z are calculated with 5 samples and for graph construction, we set the nearest neighbor number as 10 for 20Newsgroups dataset and 5 for Yahoo news dataset. As we shall see in the sensitivity analysis, the performances of our model is insensitive to K, zloop and nearest neighborhood number used in the graph construction. For the stochastic gradient MCMC, the stepsizes for classifier weights η are AdaGrad stepsize [Duchi et al., 2011] and stepsizes for topic-word parameter Φ are set as 10 ∗ (1 + t/100)-0.6 at iteration t.

2 http://qwone.com/∼jason/20Newsgroups

3 http://www-users.cs.umn.edu/∼boley/ftp/PDDPdata/README.html

4.2 Classification Performance

We report the classification performance in Table. 2 for binary setting and Table. 3 for multi-class. We mark the best classification results as bold when the label ratio is lower than 0.5. We can see that our LapMedLDA generally performs best when there are a few labels (label ratio ≤ 0.5), indicating that the manifold regularization term captures the global manifold information. When the label ratio is larger than 0.5, semi-supervised models generally perform as good as supervised models.

It is worth stressing that in all the semi-supervised models, we use the inductive setting and all testing documents are not available during the training process. For semi-supervised models with latent topic variables, the latent topic assignments of the testing documents are predicted only with the topic-word parameter inferred from the training process. The prediction process uses either collapsed Gibbs sampling for LDA or EM-based optimization method for PLSA [Zhu et al., 2014a]. Please note that Huh et al. [2012] reported the results in a transductive setting, where the testing data features are seen during training.

4.3 Time Efficiency

To compare the efficiency of the algorithms, we show the training time of related models on the multi-class 20newsgroup dataset in Figure. 1. The red solid line (LapMedLDA) shows the training time of the stochastic sampler for LapMedLDA, the blue dotted line (MedLDA)

shows the training time of Gibbs sampler for MedLDA [Zhu et al., 2014a], the green dotted line shows the training time of SS-MedLDA and the black dash-dotted line(MedLDA(Stochastic)) shows the training time of the stochastic gradient MCMC for MedLDA [Hu et al., 2017]. It can be seen that, the stochastic samplers are faster than the Gibbs sampler. Comparing the results of the stochastic samplers, we can see that the adding manifold regularization only has a limited effect on the efficiency.

4.4 Qualitative Analysis

For the binary classification setting of 20news dataset, we show some latent topic patterns of the unlabeled documents in Table. 4. The left column shows the true category labels of the documents, 70 percent of which are actually discarded. We choose the salient topics of the two categories and show the average topic proportions and the representative words in the middle and the right columns. As can be seen that, with only a fraction of document labels, we still can learn salient latent topic(s) for each specific category.

We use the 2-dimensional t-SNE method [Maaten and Hinton, 2008] to get the visualization of the learned latent topics for multi-class 20news Dataset, where the 90 percent of labels are discarded. As can be seen in Figure. 2, by adding unlabeled data in the generative topic modeling part (from left to middle), the labeled data tend to be more concentrated. By adding the manifold regularization (from middle to right), unlabeled data tend to be more concentrated and tend to cluster around the labeled documents. This concentration indicates that with the posterior manifold regularization, our model learns more discriminative latent topics of the unlabeled documents and this is beneficial for the coupled classifiers.

4.5 Sensitivity Analysis

Figure. 3 shows that LapMedLDA is insensitive to the variation in the three parameters, the number of the nearest neighbors, the topic number and the number of collecting topic samples for calculating the expectation of ¯ z (Eqn. (15)).

5 Conclusions

We present a semi-supervised max-margin topic model with manifold regularization, named Laplacian MedLDA (LapMedLDA). By adopting a manifold posterior regularization term, our model jointly learns the latent topics and a related max-margin classifier for semi-supervised document classification. Under a tight coupling between topic modeling and the semi-supervised max-margin classifier, we learn discriminative topic representations and a powerful semi-supervised classifier via an efficient stochastic gradient MCMC method. Extensive experimental results show the effectiveness in the semi-supervised setting.