The Cluster-Abstraction Model: Unsupervised Learning of Topic Hierarchies from Text Data

1 Introduction

Intelligent processing of text and documents ultimately has to be considered as a problem of natural language un­ derstanding. This paper presents a statistical approach to learning of language models for context-dependent word occurrences and discusses the applicability of this model for interactive information access. The proposed technique is purely data-driven and does not make use of domain-dependent background information, nor does it rely on predefined document categories or a given list of topics.

The Cluster-Abstraction Model (CAM) , is a statistical latent class or mixture model [McLachlan and Basford, 1988] which organizes groups of documents in a hierar­ chy. Compared to most state-of-the-art techniques based on agglomerative clustering (e.g., [Jardine and van Rijs­ bergen, 1971; Croft, 1977; Willett, 1988]) it has several advantages and additional features : As a probabilistic model the most important advantages are:

• a sound foundation in statistics and probabilistic inference
• a principled evaluation of generalization perfor­ mance for model selection,
• efficient model fitting by the EM algorithm,
• an explicit representation of conditional indepen­ dence relations.

Additional advantages are provided by the hierarchical nature of the model , namely :

• multiple levels of document clustering,
• discriminative topic descriptors for document groups,
• coarse-to-fine approach by annealing.

The following section will first introduce a non­ hierarchical probabilistic clustering model for docu­ ments, which is then extended to the full hierarchical model.

2 Probabilistic Clustering of Documents

Let us emphasize the clustering aspect by first in­ troducing a simplified, non- hierarchical version of the CAM which performs 'flat' probabilistic clustering and is closely related to the distributional clustering model [Pereira eta/., 1993] that has been used for word cluster­ ing and text categorization [Baker and McCallum, 1998]. Let d E V = {d( 1 ), .. . , d(I)} denote documents. and w E W = { w(l), ... , w(J )} denote words or word stems. Moreover let w d refer to the vector (sequence) of words Wdt constituting d. Word frequencies are summarized using count variables n(d, w) which indicate how often a word w occurred in a document d; n(d) = I:::w n(d, w) denotes the document length.

Following the standard latent class approach, it is as­ sumed that each document d belongs to exactly one clus­ ter cd E C = {cU) , ... , c(K)}, where the number of clus­ ters is assumed to be fixed for now. Introducing class conditional word distributions P(wic) and class prior probabilities P(c) (stacked in a parameter vector B), the model is defined by P( cd = c; B) = P( c) and

The factorial expression reflects conditional indepen­ dence assumptions about word occurrences in w d (bag­ of-words model) .

Starting from ( 1) the standard EM approach [Demp­ ster et al., 1977] to latent variable models is employed. In EM two re-estimation steps are alternated:

• an Expectation (E)-step for estimating the posterior probabilities of the unobserved clustering variables P( Cd = clw d; (}') for a given parameter estimate (}' ,
• a Maximization (M)-step , which involves maximiza­ tion of the so-called expected complete data log-like­ lihood for given posterior probabilities with respect to the parameters. \

The EM algorithm is known to incre'a.se the observed likelihood in each step, and converges to a (local) maxi­ mum under mild assumptions.

An application of Bayes' rule to (1) yields the follow­ ing E-step re-estimation equations for the distributional clustering model

The M-step stationary equations obtained by differenti­ ating C are given by

These equations are very intuitive: The posteriors P( cd = clw d; (}) encode a probabilistic clustering of doc­ uments, while the conditionals P( wlc) represent average word distributions for documents belonging to group c. Of course, the simplified flat clustering model defined by (1) has several deficits . Most severe are the lack of a multi-resolution structure and the inadequacy of the 'prototypical' distributions P(wlc) to emphasize discrim­ inative or characteristic words (they are in fact typically dominated by the most frequent word occurrences). To cure these flaws is the main goal of the hierarchical ex­ tension.

3 Document Hierarchies and Abstraction

3.1 The Cluster-Abstraction Model

Most hierarchical document clustering techniques utilize agglomerative algorithms which generate a cluster hier­ archy or dendogram as a by- product of successive cluster merging (cf. [Willett, 1988]). In the CAM we will use an explicit abstraction model instead to represent hierarchi­ cal relations between document groups. This is achieved by extending the 'horizontal' mixture model of the pre­ vious section with a 'vertical' component that captures the specificity of a particular word w in the context of a document d. It is assumed that each word occurrence Wdt has an associated abstraction node a, the latter be­ ing identified with inner or terminal nodes of the cluster hierarchy ( cf. Figure 1 (a)) .

To formalize the sketched ideas, additional latent vari­ able vectors ad with components adt are introduced which assign words in d to exactly one of the nodes in the hierarchy. Based on the topology of the nodes in the hierarchy the following constraints between the cluster variables cd and the abstraction variables adt are imposed:

The notation a i c will be used as a shortcut to refer to nodes a above the terminal node c in the hierarchy. Eq. (5) states that the admissible values of the latent abstraction variables adt for a particular document with latent class cd are restricted to those nodes in the hi­ erarchy that are predecessors of cd. This breaks the permutation-symmetry of the abstraction nodes as well as of the document clusters. An abstraction node a at a particular place in the hierarchy can only be utilized to "explain" words of documents associated with termi­ nal nodes in the subtree of a. A pictorial representation can be found in Figure 1 (b) : if d is assigned to c the choices for abstraction nodes for word occurrences Wdt are restricted to the 'active' (highlighted) vertical path. One may think of the CAM as a mixture model with a horizontal mixture of clusters and a vertical mixture of abstraction levels. Each horizontal component is a mixture of vertical components on the path to the root, vertical components being shared by different horizontal components according to the tree topology.

Generalizing the non-hierarchical model in (1), a probability distribution P(wla) over words is attached to each node (inner or terminal) of the hierarchy. After application of the chain rule, the complete data model (i.e., the joint probability of all observed and latent vari­ ables) can be specified in three steps P( cd = c; (}) = P( c), P(adt =alcd=c; (}) = P(alc, d), and

Note that additional document-specific vertical mixing proportions P( ale, d) over abstraction nodes above clus­ ter c have been introduced, with the understanding that P(alc, d) = 0 whenever it is not the case that a j c. If one makes the simplifying assumption that the same mixing proportions are shared by all documents assigned to a particular cluster (i.e., P(alc, d)= P(aic)), the so­ lution degenerates to the distributional clustering model since one may always choose P(alc) = Oac· However, we propose to use this more parsimonious model and fit P(aic) from held-out data (a fraction of words held out from each document), which is in the spirit of model interpolation techniques [Jelinek and Mercer, 1980] .

3.2 EM Algorithm

As for the distributional clustering model before, we will derive an EM algorithm for model fitting. The E-step requires to compute (joint) posterior probabilities of the form P(cd = c, adt = alwd; e) . After applying the chain rule one obtains:

The M-step re-estimation equations for the conditional word distributions are given by

where P(adt = aiwd; B) = L:cP(cd = clwd; B)P(adt = a lw d, cd = c; B). Moreover, we have the update equation (3) for the class priors P( c) and the formula

which is evaluated on the held-out data. Finally, it may be worth taking a closer look at the predictive word prob­ ability distribution P(wld) in the CAM which is given by

If we assume for simplicity that P( cd = clw d; B) = 1 for some c (hard clustering case), then the word probability of dis modeled as a mixture of occurrences from different abstraction levels a. This reflects the reasonable assump­ tion that each document contains a certain mixture of words ranging from general terms of ordinary language to highly specific technical terms and specialty words.

3.3 Annealed EM Algorithm

There are three important problems which also need to be addressed in a successful application of the CAM: First and most importantly, one has to avoid the prob­ lem of overfitting. Second, it is necessary to specify a method to determine a meaningful tree topology in­ cluding the maximum number of terminal nodes. And third, one may also want to find ways to reduce the sensitivity of the EM procedure to local maxima. An answer to all three questions is provided by a gener­ alization called annealed EM [Hofmann and Puzicha, 1998). Annealed EM is closely related to a technique known as deterministic annealing that has been applied to many clustering problems (e.g. [Rose et a/. , 1990; Pereira et a/., 1993)). Since a thorough discussion of annealed EM is beyond the scope of this paper, the the­ oretical background is skipped and we focus on a pro­ cedural description instead. The key idea in determin­ istic annealing is the introduction of a temperature pa­ rameter T E IR+ . Applying the annealing principle to the clustering variables, the posterior calculation in (7) is generalized by replacing n(d, w) in the exponent by n(d, w)jT. ForT > 1 this dampens the likelihood con­ tribution linearly on the log-probability scale and will in general increase the entropy of the (annealed) posterior probabilities. In annealed EM, T is utilized as a con­ trol parameter which is initialized at a high value and successively lowered until the performance on the held­ out data starts to decrease. Annealing is advantageous for model fitting, since it offers a simple and inexpen­ sive regularization which avoids overfitting and improves the average solution quality. Moreover, it also offers a way to generate tree topologies, since annealing leads through a sequence of so-called phase transitions, where clusters split. In our experiments, T has been lowered until the perplexity (i.e., the log-averaged inverse word probability) on held-out data starts to increase, which automatically defines the number of terminal nodes in the hierarchy. More details on this subject can be found in [Hofmann and Puzicha, 1998).

4 Results and Conclusion

All documents used in the experiments have been pre­ processed by word suffix stripping with a word stemmer . A standard stop word list has been utilized to elimi­ nate the most frequent words , in addition very rarely occurring words have also been eliminated. An exam-

(a) Verbatim

(b) Word 6lems

Introduces a large family of Boltzmann machines that can be trained by standard gradient descent. The networks can have one or more layers of hidden units, with tree-like connectivity. We show how to implement a supervised learning algorithm for these Boltzmann machines exactly, without resort to simulated or mean-field annealing. The stochastic averages that yield the gradients in weight space are computed by the technique of decimation. We present results on the problems of N-bit parity and the detection of hidden symmetries.

introduc larg famili boltzmann machin train standard gradient descent network layer hid­ den unit connect implem supervis learn algo­ rithm boltzmann machin exactli simul anneal stocha.st averag yield gradient weight space techniqu present result problem pariti detec hidden symmetri

(c) Ghost writer

level 1 paper model base new method gener process differ effect approach provid set studi develop author

level 2 function propos model error method input optim gener neural paramet paper obtain shown appli output

level 3 gener number set neural propos function perform method inform data given obtain approxim dynamic input

level 4 neural pattern rule number process recogni rate perform cla.ssif propos gener input neuron time properti data

level 5 converg neural optim method rule rate dynamic process pattern paramet studi statist condition adapt limit

level 6 perceptron exampl error gener rule onlin calcul deriv backpropag simp! output a.symptot solution separ unsupervis

level 7 error neural architectur perform entropi statist multilay activ backpropag gener number maximum pattern phase

level 8 teacher delta output introduc sampl replica decai nois projec carrel student temperatur gain dynamic predic

Figure 3: Group descriptions for exemplary inner nodes by most frequent words and by the highest probability words from the respective CAM node.

pie abstract and its index term representation is de­ picted in Figure 2 (a),(b). The experiments reported are some typical examples selected from a much larger number of performance evaluations. They are based on two datasets which form the core of our current pro­ totype system: a collection of 3609 recent papers with 'learning' as a titleword, including all abstracts of pa­ pers from Machine Learning Vol. 10-28 (LEARN), and a dataset of 1568 recent papers with 'cluster' in the title (CLUSTER).

The first problem we consider is to estimate the prob­ ability for a word occurrence in a text based on the sta­ tistical model. Figure 2 (c) shows the most probable words from different abstraction levels, which did not occur in the original text of Figure 2 (a). The abstrac­ tive organization is very helpful to distinguish layers with trivial and unspecific word suggestions (like 'paper') up to highly specific technical terms (like 'replica').

One of the most important benefits of the CAM is the resolution-specific extraction of characteristic key­ words. In Figure 4 and 6 we have visualized the top 6 levels for the dataset LEARN and CLUSTER, respec­ tively. The overall hierarchical organization of the doc­ uments is .very satisfying, the topological relations be­ tween clusters seems to capture important aspects of the inter-document similarities. In contrast to most multi­ resolution approaches the distributions at inner nodes of the hierarchy are not obtained by a coarsening pro­ cedure which typically performs some sort of averaging over the respective subtree of the hierarchy. The ab­ straction mechanism in fact leads to a specialization of the inner nodes. This specialization effect makes the probabilities P( wla) suitable for cluster summarization. Notice, how the low- level nodes capture the specific vo­ cabulary of the documents associated with clusters in the subtree below. The specific terms become automat­ ically the most probable words in the component dis­ tribution, because higher level nodes account for more general terms. To stress this point we have compared the abstraction result with probability distributions ob­ tained by averaging over the respective subtree. Figure 3 summarizes some exemplary comparisons showing that averaging mostly results in high probabilities for rather unspecific terms, while the CAM node descriptions are highly discriminative. The node-specific word distribu­ tion thus offer a principled and very satisfying solution to the problem of finding resolution-specific index terms for document groups as opposed to many circulating ad hoc heuristics to distinguish between typical and topical terms.

An example run for an interactive coarse-to-fine re­ trieval with the CLUSTER collection is depicted in Fig­ ure 5, where we pretend to be interested in documents on clustering for texture-based image segmentation. In a real interactive scenario, one would of course display more than just the top 5 words to describe document groups and use a more advanced shifting window ap­ proach to represent the actual focus in a large hierarchy. In addition to the description of document groups by inner node word distributions, the CAM also offers the possibility to attach prototypical documents to each of the nodes (the ones with maximal probability P(ald)), to compute most probable documents for a given query, etc. All types of information, the cluster summaries by

I

(locally) discriminant keywords , the keyword distribu­ tions over nodes, and the automatic selection of proto­ typical documents are particularly beneficial to support an interactive retrieval process. Due to the abstraction mechanism the cluster summaries are expected to be more comprehensible than descriptions derived by sim­ ple averaging. The hierarchy offers a direct way to refine queries and can even be utilized to actively ask the user for additional specifications.

Conclusion: The cluster-abstraction model is a novel statistical approach to text mining which has a sound foundation on the likelihood principle. The dual organization of document cluster hierarchies and key­ word abstractions makes it a particularly interesting model for interactive retrieval. The experiments carried out on small/medium scale document collections have emphasized some of the most important advantages. Since the model extracts hierarchical structures and sup­ ports resolution dependent cluster summarizations, the application to large scale databases seems promising.

Acknowledgments: Helpful comments of Jan Puzicha, Sebastian Thrun, Andrew McCallum, Tom Mitchell, Hagit Shatkay, and the anonymous reviewers are greatly acknowledged. Thomas Hofmann has been supported by a DAAD postdoctoral fellowship.