In context of document classification, where in a corpus of documents their label tags are readily known, an opportunity lies in utilizing label information to learn document representation spaces with better discriminative properties. To this end, in this paper application of a Variational Bayesian Supervised Nonnegative Matrix Factorization (supervised vbNMF) with label-driven sparsity structure of coecients is proposed for learning of discriminative nonsubtractive latent semantic components occuring in TF-IDF document representations. Constraints are such that the components pursued are made to be frequently occuring in a small set of labels only, making it possible to yield document representations with distinctive label-specific sparse activation patterns. A simple measure of quality of this kind of sparsity structure, dubbed inter-label sparsity, is introduced and experimentally brought into tight connection with classification performance. Representing a great practical convenience, inter-label sparsity is shown to be easily controlled in supervised vbNMF by a single parameter.
As an essential step in machine learning applications which both eciency and quality of learning depend on, dimensionality reduction has become a well covered subject of research [MPH09] which produced archetipal linear methods with low-rank assumptions such as Principal Component Analysis (PCA) [Jol02] and Nonnegative Matrix Factorization (NMF) [LS99], as well as their kernelized and generally non-linear variants, to touch upon some. Originally they have been formulated as entirely unsupervised methods. However, in supervised and semisupervised learning applications, where labels of learning samples are readily available, it may be appealing to use this information to obtain lower-dimensional representations of data which not only attempt to preserve the original variance in the data, but also promise to deliver representation spaces with better discriminative properties. A well known representative which incorporates this desideratum is Fisher’s Linear Discriminant Analysis (FLD) [MK01]. In recent relevant literature there is a pronounced trend of using probabilistic generative models for this purpose. Probabilistic approaches to learning lie on a well developed mathematical apparatus which o↵ers flexible enough modeling of prior knowledge in form of graphical models, supported by well-known meta-algorithms for estimating model parameters. Of this family of algorithms, along with Probabilistic Latent Semantic Analysis (pLSA) [Hof99], a common probabilistically formulated baseline algorithm in text mining is Latent Dirichlet Allocation (LDA) [BNJ12] with its more recent discriminative modifications [BM07][LJSJ08], as well as probabilistic formulations of sparse NMF [Cem09] and their supervised counterparts [Ive14].
Sparse coding is known to result in ecient and robust representations which have proven suitable for applications such as data compression, denoising and missing data imputting [Mal99]. On the other hand, representations obtained discriminatively are suitable for classification purposes. Combining those two properties, the basis of this work is a probabilistically formulated method for sparse additive representations of data using nonnegative latent components which are of sparsity structure additionally driven by data labeling [Ive14]. In context of document classification, the decomposition is suitable for finding interpretable patterns of semantically related terms, with high discriminative potential. 1.1
Disregarding syntactic and semantic interrelations of words, the simplest and most often used intermediate form for document representation is bag-of-words; after tokenization, purification and stemming, frequency of relevant terms is determined for each document resulting in representations of documents as frequencies of particular terms. Models such as LDA have a natural interpretation when decomposing bag-of-words representations, while other approaches may benefit from TF-IDF weighting [RU11] which heuristically measures the importance of a term for a particular document in a specific corpus of documents. For a term with index ⌧ in ⌫ -th document, as a product of two measures, (1) (2) (3) tf idf⌫⌧ = tf⌫⌧ ⇤ idf⌧ , tf⌫⌧ =
#⌫⌧ maxt(#⌫t ) , where the number of occurences of term ⌧ in ⌫ -th document is denoted by #⌫⌧ , the number of documents in the corpus by N and the number of documents which contain term ⌧ at least once by n⌧ .
TF-IDF score is proportional to (normalized) frequency of a particular term in a document, but stunted by a measure of how rare this term occurs in the entire corpus,
Bag-of-words-based approaches to text mining are known to su↵er from problems of polysemy and synonymy of terms. These problems can be alleviated by representing documents in spaces of patterns of frequencies of semantically related terms rather than in the original space of term frequencies [DDF+90]. Luckily, algorithms for learning of such representations exist, of which perhaps the best known are pLSA formulations. Also assuming inherent nonnegativity in the data, NMF decompositions can be interpreted the same way as pLSA, revealing patterns of semantically related terms underlying the data. Furthermore, a specific connection worth mentioning is that a NMF formulation based on generalized KL-divergence minimizes the exactly same objective function as the original pLSA formulation does [GG05].
Nonnegativity is a reasonable assumption and a desireable bias when modeling either term frequencies or derived intermediate document representations such as TF-IDF. In general, NMF aims at decompositions in form of X⇡ T V , where X, T and V are all nonnegative matrices. Although the decomposition is nonunique in general, to some extent nonuniqueness may be compensated for by adding additional bias in the model, of which most prominent is sparsity of solution [LS99]. Sparsity is enforced in divergence-based NMF by di↵erent sparsity promoting regularizers, e.g. [Hoy04], and in probabilistic formulations by imposing sparse prior distributions on the coecients [Cem09]. Throughout this paper, in context of document representation for categorization purposes, X will be regarded as a collection of documents organized columnwise and represented by TF-IDF features, T as a low-rank collection of latent semantic components organized columnwise, and V as matrix of coecients when X is projected onto the space of latent semantic components T . In other words, each document is modeled as a strict superposition of the nonnegative latent semantic components. 2 2.1
The generative model [Ive14] assumes that each column of data x:⌧ is a result of latent components t:i consisting of independent gamma-distributed variables, interacting through linear mixing with coecients vi⌧ under Poissonian noise: p t⌫i a⌫ti , b⌫ti
= G t⌫i a⌫ti , b⌫ti , p (s⌫i⌧ |t⌫i , vi⌧ ) = P (s⌫i⌧ |t⌫i , vi⌧ ) p (x⌫⌧ |s⌫ :⌧ ) = x⌫⌧
X s⌫i⌧ i ! .
(4) (5) (6) Mixing coecients vi⌧ are assumed to be exponentially distributed with di↵erent scale parameters for di↵erent selections of label indicators z⌧ 2 L , formulated as mixtures of variables il with z⌧ as discrete numerical mixture selection variables, p (vi⌧ |z⌧ , i:) = G vi⌧ 1, X
(z⌧ l2L l) il1 ! Note that label indicators z⌧ are elements of a discrete set of (integer) numbers L for convenience of notation. Variables il1, representing expectations of magnitudes of coecient components i for all samples labeled as l are constrained by inverse-gamma priors, p il ail, bil = G il ail, bil .
Because inverse-gamma is a heavy-tailed distribution, by setting the probability mass to be concentrated around some small value, significantly larger values of il1 will occur rarely. Thus, such a prior imposes an additional bias to produce models having only a minority of indicators il1 with significantly large mean values on average, which, hierarchically propagating to activation coecients vi⌧ , constrain samples having the same label to have only a small shared subgroup of latent patterns significantly active.
Using compact notation (7) (8) p (X|S) = Y p (x⌫⌧ |s⌫ :⌧ )
⌫,⌧ p (S|T , V ) = Y p (s⌫ :⌧ |t⌫i , vi⌧ )
⌫,⌧ p T At, Bt = Y p(t⌫i |a⌫ti , b⌫ti )
⌫,i p ⇣V ⇤ , *z⌘ p ⇤ A , B = Y p (vi⌧ | i:, z⌧ )
i,⌧ = Y p i,l il ail, ail , joint distribution of the supervised NMF model can be written as p ⇣X, S, T , V , ⇤ At, Bt, A , B , *z⌘ = p (X|S) p (S|T , V ) p T At, Bt p ⇣V ⇤ , *z⌘ p ⇤ A , B .
(9) Linear mixing as described by (4), (5) and (6) is the same as in Poisson-gamma NMF [Cem09]. Equations (7) and (8) additionally formulate a sparsity structure abstracted from the level of data samples to the level of labels, making it possible to pursue decompositions with recognizable sparsity patterns characteristic of data samples which share the same label tag. (10) (11) 2.2
To give a concise outline of general treatment of learning by VB, let the observed variables be denoted by D, the hyperparameters of a model by H and both the unobserved variables and the model parameters by ⇥ . Minimization of discrepancy between posterior p (⇥ |D, H) (which is in general dicult to optimize directly, especially in a fully Bayesian manner) and an introduced instrumental approximation q(⇥ ) measured by Kullback-Liebler divergence gives rise to a lower bound on the posterior,
L = hln p (D, ⇥ |H)iq(⇥ ) + H [q(⇥ )] , where entropy of the probability density function in the argument is denoted by H [.]. Supposing that q(⇥ ) is of factorized form q(⇥ ) = Q↵ 2 C q(⇥ ↵ ), it can be shown that the iterative local updates at iteration (n+1) alternating over C in form of ! q(⇥ ↵ )(n+1) / exp hln p (D, ⇥ |H)i q(⇥ )(n) q(⇥ ↵ )(n) improve the lower bound (10) monotonically. Moreover, should the model be conjugate-exponential, for a fully factorized approximation, expressions in (11) neccessarily assume analytical forms [Win03].
To obtain convenient analytical forms of update equations of supervised vbNMF model defined by (9) the approximative distribution is chosen to be factorized as q (S, T , V , ⇤ ) = q (S) q (T ) q (V ) q (⇤ ), with shorthand notation q (S) = Q⌫,⌧ q (s⌫ :⌧ ), q (T ) = Q⌫,i q (t⌫i ), q (V ) = Qi,⌧ q (vi⌧ ) and q (⇤ ) = Qi,l q ( il). The variational Bayesian update expressions are obtained by specifying p (D, ⇥ |H) = p X, S, T , V , ⇤
At , Bt, Av, Bv together with
q (⇥ ) = q (S, T , V , ⇤ ) in (11). For computational convenience, optimization is done with respect to the lower bound (10) additionally relaxed using Jensen’s inequality, to finally yield the update expressions summarized in Table A1., where the iterative learning algorithm is presented using ecient matrix operations; the accompanying matrix forms of the variables, hyperparameters and variational parameters of the model are listed in the first column of the table. A more detailed treatment of the learning algorithm can be found in [Ive14]. 3
All experiments have been performed on 20Newsgroups1 dataset, bydate version split into training and test sets; rather than estimating the generalization error of classification by crossvalidation techniques, the underlying ambition is merely to explore peak potentials of classification using di↵erent representation spaces evaluated on a single train-test split in same conditions. 1 Available from Jason Rennie’s web Page, http://qwone.com/˜jason/20Newsgroups/
Experiments have been performed on 20Newsgroups dataset sorted by date wih duplicates and headers removed, with documents having multiple labels left out and preprocessed to obtain a bag-of-words representation. The dataset is split into a training set and a test set. To alleviate computational load, the set of features has been heuristically reduced to 10000 terms, based on maximum TFIDF score accross all documents. 3.2
Representation spaces in which consequently classification takes place which are taken under consideration are the ones obtained by PCA, Poisson-gamma unsupervised vbNMF [Cem09], and the supervised vbNMF, all decomposing the matrix of TF-IDF scores of the training set only. Having learned a specific space of reduced dimensionality, representation of the test set in this space is found by projection on the vector basis in case of PCA or by optimizing the matrix of coecients only using Poisson-gamma vbNMF formulation (i.e. the matrix of latent components is fixed to what has been learned in the training step) in case of both unsupervised and supervised vbNMF methods.
For Poisson-gamma vbNMF sparse decompositions have been pursued by fixing shape hyperparameters of the gamma distributed coecients to a value less than or equal to 1 throughout the entire run, while other hyperparameters (constrained to be the same for all elements of matrices T and V , a single one for each of the matrices) have been optimized automatically by maximization of the lower bound directly in a non-Bayesian manner [Cem09]. For supervised vbNMF, hyperparameters aLambda have been fixed and varied, while other hyperparameters have been left to the algorithm to optimize, by direct optimization as in [Cem09]. Specifically, following initialization, parameters are chosen to be all equal and fixed for a burn-in period of 10 iterations, not until after which they start to get optimized according to the algorithm in Table A1.
To accentuate the predictive potentials of the considered representation spaces by themselves, rather than in conjunction with a strong classifier, the classifier of choice is k-NN using cosine similarity metric, with k chosen heuristically as the square root of the cardinality of the training set.
Dimension of space of latent components has been varied as a parameter for all decomposition methods. Because at each run the NMF algorithms converge to some local minimum, to explore these local minima, for each parameter set they have been run 10 times with random initializations. 3.3
Metrics of classification performance used in the experiments are micro-averaged accuracy, defined as amicro =
Pl Nlcorrect
Pl Nlall , and macro-averaged accuracy,
amacro = L1 Xl NlNcolrarllect , where the number of correctly classified documents belonging to the l-th label is denoted by N correct, the number of documents belonging to l-th label in the l test split by N all and the number of labels by L. By averaging the accuracies l calculated separatedly for each of the labels, macro-averaged accuracy compensates for label-imbalance of test datasets.
As a measure of sparsity, Hoyer’s measure [Hoy04], based on ratio of l1 and l2 norms and originally introduced in context of NMF penalization, will be used. For a vector *x = [x1, ..., xn]T it is defined as
⇣*⌘ sparsity x = p n 1 1 p n
Pi |xi|
p(Pi xi2)
!
,
taking value of 1 in case only a single element is non-zero (maximum sparsity),
and a value of 0 if all elements are equal (minimum sparsity). For the purpose
of this paper, when referring to sparsity of matrices, matrix is assumed to be
vectorized first by appending its columns, then treating it as a vector according
to (
If labels in a document corpus are meaningfully assigned based on topics of documents, then meaningful discovered latent semantic components are expected to have specific patterns of occurence for documents belonging to a specific label. Using supervised vbNMF, those patterns are modeled as patterns in sparsity of coecients (i.e. in patterns of support of sparse coecients) that documents labeled the same have in common. To measure the consistency of occurence of sparsity patterns in labels, let a representation by coecients of N documents in I dimensional space be denoted by V 2 RIxN , i.e. n-th document is represented by coecient vector [ V ]:n, and let sums of coecient sets which share the same label be accumulated in matrix L 2 RIxL, where L is number of labels as [L]:l =
X [V ]:n,
n2 Nl
where n iterates over subset of document indices with the same label, Nl.
Now, inter-label sparsity can be introduced, defined as sparsity of matrix L.
The motivation behind (13) is that l0 norm of a sum of vectors with the same
sparsity pattern (same support) is the same as the exclusive l0 norm of such
vectors by themselves, and, the more those vectors deviate from the pattern (i.e.
when the vectors have di↵ering supports), the larger the l0 norm of the sum
will be. Note that the latter rationale holds exactly for l0 definition of sparsity,
while for more relaxed definitions of sparsity such as (
For comparison, as a baseline, classification results of PCA are plotted against the dimension of representation space on Fig. 1. For unsupervised vbNMF, micro-averaged accuracies averaged accross random initializations for di↵erent shape parameters with varying number of latent semantic components are shown in Fig. 2.
0.750
Compared to PCA, even with a larger dimension of representation space, vbNMF with sparsity constraints did not bring improvements on average, regardless of the degree of sparsity penalization. The explanation is that, even though sparse representation spaces may be good for clustering, natural clusters may di↵er greatly from labeling and consequently even be detrimental to classification applications [BM07] when compared to dense representations such as PCA. Better representations for classification purposes are expected to be found by introducing label information to the model, which in spaces obtained by supervised vbNMF (Fig. 3.) indeed manifested as a boost in classification performance. Both unsupervised vbNMF and supervised vbNMF consistently resulted in sparse decompositions. However, label-driven structure present in supervised vbNMF decompositions (engineered as to be the sole di↵erence in the experiments) is to be accounted for the beneficial e↵ect observed. Examples of sparsities accross labels according to (13) are visualized on on Fig. 4. for the sparse unsupervised vbNMF decomposition which produced peak micro-averaged accuracy of 0.5796 and on Fig. 5. for an arbitrarily chosen supervised variant with matching dimension. The supervised variant produced distinctive sparsity patterns accross labels, which is also reflected quantitatively on inter-label sparsity of the decomposition. 0.56
The connection between sparsity on the level of labels and classification performance is further explored using Fig. 6., showing data for all supervised representations obtained in the experiments. Variance of the scatter plot becomes tighter with increasing dimension of representation space, meaning that for a suciently large dimension of the decomposition, inter-label sparsity is indeed a good predictor for classification quality on this dataset.
Equally importantly, experiments show that in case of supervised vbNMF, interlabel sparsity can elegantly be controlled by a single parameter a alone, regardless of dimension: as illustrated by Fig. 7., a logarithmic increase of a is accompanied by a trend of growth of inter-label sparsity, only to be broken by too extreme regularizations, when tails of the prior have little mass. On the other hand, unsupervised vbNMF resulted in moderate levels of inter-label sparsity because sparsity structure is supported by the structure of data features only, with somewhat higher values in cases of very strong sparsity regularizations and an impractically small number of latent patterns.
Classification results using k-NN classifier with heuristically chosen k on representation spaces obtained by the three methods are summarized in Table 1., reporting peak value of its micro- and macro-averaged accuracies; for the set of parameters which yielded the peak performance, corresponding accuracies averaged accross the 10 random initializations together with minimal achieved accuracies are reported. On Fig. 3.b), showing smooth dependence of micro-averaged accuracy (averaged across random initializations) on an interesting range of a for a selection of dimensions, peak performance as entered in Table 1. can be seen marked.
To conclude the remarks on the experiments, it is worth mentioning that, if sparse representations are pursued, care is advised when choosing and optimiz0.75 0.45 0.75 Fig. 3. Supervised vbNMF classification results, averaged over 10 random initializations. a) Dependence on level of sparsity penalization, varying dimensions of representation spaces. b) Dependence on level of sparsity penalization, varying dimensions of representation spaces. Error bars represent maximum and minimum values among the random initializations. x-axis is shown on logarithmic scale. you,that,they,it,would windows,dos,os,drivers,mouse window,widget,display,application,motif university,fax,information,computer,research uk,ac,mit,server,sun uiuc,cso,he,runs,hit team,game,games,hockey,season stephanopoulos,president,mr,clinton,we space,nasa,gov,shuttle,dc scsi,drive,mb,disk,memory science,objective,exist,theory,values
rights,men,islam,sex,islamic price,sale,keyboard,reply,shipping org,government,isc,money,billion msg,tape,audio,navy,mil moon,lunar,earth,du,tek militia,moral,bear,right,arms launch,rochester,ti,commercial,adl
la,pts,period,vs,flyers key,encryption,chip,keys,clipper
jim,fbi,fire,koresh,sandvik israel,israeli,jews,jewish,arab insurance,ground,wire,circuit,neutral health,rate,rates,risk,seattle
he,she,her,was,were gun,guns,law,crime,firearms graphics,image,ftp,jpeg,pub
god,jesus,he,bible,his faq,list,anonymous,posting,mail entry,output,file,oname,max
ei,um,pa,em,el drugs,pain,drug,gang,iran disease,pitt,food,medical,patients
db,mov,ohio,acs,bh cd,sound,quality,radio,tv car,cars,engine,oil,speed brian,myers,dog,nec,mot
black,ra,cover,rob,art bike,dod,com,andrew,ride Fig. 4. Sparsity accross labels according to (13) for the unsupervised vbNMF decomposition with best classification performance; the more intense the tone of blue, the higher the sparsity. Each of the 40 latent semantic components is represented by its 5 most significant terms. Coecient sparsity is 0.6862, inter-label sparsity is 0.5784. you,that,they,it,not wpi,win,cci,rc,scope wire,ground,circuit,wiring,voltage
windows,dos,file,files,ms window,motif,widget,server,lib uiuc,cso,science,theory,larson tyre,magi,zoroastrians,ezekiel,dallas turkish,armenian,armenians,turkey,turks stephanopoulos,president,mr,jobs,tax space,nasa,launch,orbit,moon
scsi,mb,card,bus,mhz sale,shipping,condition,dos,price
msg,food,insurance,adl,health lebanese,israel,lebanon,water,israeli
la,pts,bos,period,vs key,des,ripem,keys,rsa israel,israeli,jews,arab,arabs islam,sandvik,drugs,islamic,sex
image,jpeg,gif,images,color hockey,team,game,season,nhl health,aids,hiv,cancer,medical
he,year,baseball,team,game gun,guns,firearms,militia,weapons graphics,pub,ftp,sgi,package
god,jesus,he,bible,church god,atheism,atheists,objective,morality fbi,fire,koresh,batf,compound entry,output,oname,file,printf encryption,clipper,government,chip,escrow
ei,um,el,di,pa drive,drives,disk,floppy,controller doctor,pain,pitt,candida,yeast
db,she,her,mov,he cwru,po,kk,cleveland,de cramer,men,clayton,sexual,homosexual
car,cars,engine,oil,dealer bike,dod,ride,motorcycle,bikes
apple,mac,lc,mouse,duo anonymous,internet,ftp,privacy,pub ac,uk,com,au,cs Fig. 5. Sparsity accross labels according to (13) for an arbitrarily chosen supervised vbNMF decomposition with 40 latent semantic components, each represented by its 5 most significant terms. Coecient sparsity is 0.8752, inter-label sparsity is 0.8578. 0.75 ing hyperparameters by non-Bayesian minimization of bound. Because sparse constraints both on matrices T and V act as two competing penalizations, useful decompositions are obtained more easily by constraining only one of the matrices to be sparse - either the matrix of latent components to obtain a parts-based representation, or the matrix of coecients to obtain a sparse representation of data. So, when optimizing the shape parameter of one of the matrices in such a manner next to a fixed hyperparameter of the other matrix which is to be made sparse, due to the automated (and, equally importantly, non-Bayesian) nature of the optimization the former may also come to describe a sparse distribution and in e↵ect impede the desired bias toward the desired type of sparsity.
averaged Mean 0.6330 Accuracy Dimension 200 Macro- [Min,Max] averaged Mean 0.6179 Accuracy Dimension 200 0.6 0.7 0.8 0.9 1.0
at Inter label Sparsity It has been well documented that using label information in low-rank representation learning is vital to obtain representations with good discriminative properties. In this context, applied to classification of a document corpus, a probabilistic learning algorithm which combines sparse coding and supervised learning has been presented.
To characterize advantages of using label information, two extreme cases have been juxtaposed, the presented supervised model and a fully unsupervised one, belonging to the same family, having the same noise model and using the same metaalgorithm for parameter learning.
A qualitative inspection motivated the introduction of the notion of inter-label sparsity, abstracting sparsity of coecients on the level of documents to sparsity on the level of document labels. Experiments point to a strong connection between the inter-label sparsity of the representation and the classification performance metrics. Furthermore, inter-label sparsity of decompositions obtained by supervised vbNMF can elegantly be controlled by a single parameter. However, even though sparsity and nonnegativity constraints intuitively seem appropriate and result in compact and interpretable document representations, a question remains whether there is any actual advantage in using sparse representations over dense ones as classification precursors.
As quality of representation spaces has been primarily addressed in this work, little regard has been given to quality of the classifier per se. Because it is reasonable to expect that a stronger classifier would result in even better classification results, it would be interesting to compare a well-tuned classifier in the representation spaces obtained by supervised vbNMF to state-of-the-art aproaches in the field, on benchmark datasets. Future work based on semi-supervised modifications of the model is considered, to make the model more flexible and applicable in more commonly occuring, semi-supervised, scenarios.
Acknowledgments This work was supported by the Croatian Ministry of Science, Education and Sports through the project ”Computational Intelligence Methods in Measurement Systems”, No. 098-0982560-2565.
Summary of the Learning Algorithm
Initialize variational parameters. t = 0.
⌫i hA i
il hB i
= ht⌫i i(t) i⌧ hL(vt)i i⌧ = hln vi⌧ i (t) hE(t)i i⌧
⌫ = h ili(t) = 1. .⇣1. .B ✓ ✓ Table A1. The learning algorithm in matrix form. Left column: observed variables, hyperparameters and variational parameters organized as matrices. Right column: the algorithm; by .⇤ and ./ elementwise matrix product and elementwise matrix division are denoted, respectively, and by 1 matrix of ones of appropriate dimensions.