QUICK START

This library contains Java source and class files implementing the Latent Dirichlet Allocation [1] and Hierarchical Dirichlet Process [2] topic models.  The models can be accessed through the command-line or through a simple Java API.  Also included is a subset of the 20 Newsgroup dataset [3] and results of experiments done on the dataset to confirm the correct operation of the topic models.

To access the library via the command line, the form is:

java -jar tm-0.1.jar <flags/arguments>

Running with the -h flag prints out help and parameter defaults (also included in the USAGE section below).

For example, to run CVHDP using the default parameters on the 20 Newsgroup training and held-out datasets with 40 topics, 300 variational inference iterations, and a single final log-likelihood estimate, try:

java -jar tm-0.1.jar -m 1 -k 40 -i 300 -it 20ngtrain.mat -ie 20ngtest.mat -e 1 -ol - 

To access the library via the Java API, refer to the com.pawjaw.linalg.MatrixBuilder or com.pawjaw.linalg.Matrix classes to store your data and then instantiate com.pawjaw.topics.CGLDA for collapsed Gibbs sampling LDA or com.pawjaw.topics.CVHDP for collapsed variational inference HDP.  The com.pawjaw.topics.Main class can also be used from within Java to automate reading data and writing results.

WHAT'S INCLUDED

Please see Java source code for implementation and source reference document details.

- Collapsed gibbs sampling Latent Dirichlet Allocation topic model
- Collapsed variational inference Hierarchical Dirichlet Process topic model
- Sparse matrix data structure and routines
- Special functions (e.g. Psi and Gamma functions, Dirichlet parameter estimation)
- 20 Newsgroup subset - 1,000 documents from each of the comp.os.ms-windows.misc, rec.autos, rec.sport.baseball, sci.space, and talk.politics.misc newsgroups, stop words removed, words < 3 characters removed, words stemmed, normalized IDF thresholds of 0.2 to 0.8 used to select stems to retain

USAGE

Here are the command-line arguments and parameter defaults available in the com.pawjaw.topics.Main interface.

    -h|--help: display help

    -v|--verbosity: verbosity, 0 = quiet, 1 = errors, 2 = info/errors, requires integer argument, default value 2

    -m|--topic-model: topic model to use, 0 = CGLDA, 1 = CVHDP, requires integer argument

    -it|--training-matrix: input training count data file in "row col count" sparse matrix text format (first row/col = 0, documents in columns), requires string argument

    -ie|--test-matrix: input test count data file for held-out log-likelihood calculations in "row col count" sparse matrix text format  (first row/col = 0, document in columns), requires string argument

    -id|--dict: input dictionary file with one word per line corresponding to each row in data matrices in text format, requires string argument

    -opm|--phi-matrix: output phi topic-word mixture file for each word (row) and topic (column) in dense matrix text format, requires string argument

    -otm|--theta-matrix: output theta document-topic mixture file for each topic (row) and document (column) in dense matrix text format, requires string argument

    -ol|--lls: output held-out log-likelihood file one line per estimate in text format, requires string argument

    -on|--nks: output token topic assignment count file for each estimate (row) and topic (column) in dense matrix text format, requires string argument

    -oc|--timing: output timing file, requires string argument

    -op|--params: output parameter file, requires string argument

    -ot|--top-topic-word: output top topic words file one line for each topic (row), words separated by tabs sorted by descending phi value, requires string argument

    -tt|--top-topic-word-count: number of words to display per topic in top-topic-word file, requires positive (greater than zero) integer argument, default value 20

  CGLDA:

    -ib|--beta-matrix: input Dirichlet alpha parameters file to specify CGLDA beta prior parameter for each word (row) and topic (column) in dense matrix text format, requires string argument

    -k|--topics: number of topics (CGLDA) or topic truncation threshold (CVHDP), requires positive (greater than zero) integer argument

    -l|--samples: number of estimates to use from Gibbs sampling phase, requires positive (greater than zero) integer argument

    -q|--sample-freq: number of Gibbs iterations between estimate sampling, requires positive (greater than zero) integer argument, default value 1

    -e|--estimates: number of log-likelihood calculations to record, requires non-negative (greater than or equal to zero) integer argument, default value 1

    -n|--burnin: number of burnin iterations, requires non-negative (greater than or equal to zero) integer argument, default value 1

    -as|--alpha-sum: uniform Dirichlet alpha parameter, gets divided by number of topics (prior on theta, document-topic mixture), requires positive (greater than zero) double-precision number argument, default value 1.0

    -b|--beta: uniform Dirichlet alpha parameter (prior on phi, topic-word mixture), requires positive (greater than zero) double-precision number argument, default value 0.01

  CVHDP:

    -k|--topics: number of topics (CGLDA) or topic truncation threshold (CVHDP), requires positive (greater than zero) integer argument

    -i|--iterations: number of variational iterations, requires positive (greater than zero) integer argument

    -e|--estimates: number of log-likelihood calculations to record, requires non-negative (greater than or equal to zero) integer argument, default value 1

    -t|--threads: number of threads to use for variational inference, requires positive (greater than zero) integer argument, default value 1

    -g|--group-tokens: 0 = calculate variational posterior for each token, 1 = for each word, requires boolean (true/false/0/1) argument, default value true

    -eb|--e-beta: expectation of beta (prior on phi, topic-word mixture), requires positive (greater than zero) double-precision number argument, default value 100.0

    -gb|--g-beta: geometric expectation of beta (prior on phi, topic-word mixture), requires positive (greater than zero) double-precision number argument, default value 100.0

    -aa|--a-alpha: Gamma shape parameter for prior on alpha (prior on theta, document-topic mixture), requires positive (greater than zero) double-precision number argument, default value 3.0

    -ba|--b-alpha: Gamma scale parameter for prior on alpha (prior on theta, document-topic mixture), requires positive (greater than zero) double-precision number argument, default value 5.0

    -ab|--a-beta: Gamma shape parameter for prior on beta (prior on phi, topic-word mixture), requires positive (greater than zero) double-precision number argument, default value 3.0

    -bb|--b-beta: Gamma scale parameter for prior on beta (prior on phi, topic-word mixture), requires positive (greater than zero) double-precision number argument, default value 5.0

    -ag|--a-gamma: Gamma shape parameter for prior on gamma (prior on pi, topics), requires positive (greater than zero) double-precision number argument, default value 6.0

    -bg|--b-gamma: Gamma scale parameter for prior on gamma (prior on pi, topics), requires positive (greater than zero) double-precision number argument, default value 8.0

    -at|--a-tau: uniform Dirichlet alpha parameter for prior on tau, gets divided by vocabulary size (prior on phi, topic-word mixture), requires positive (greater than zero) double-precision number argument, default value 40.0

DATASET

A subset of the 20 Newsgroup dataset [3] is included based on the experiments done in [2].  1,000 documents from each of the comp.os.ms-windows.misc, rec.autos, rec.sport.baseball, sci.space, and talk.politics.misc newsgroups are included in the 20ngtrain.mat and 20ngtest.mat files.  Rows in the files correspond to features (selected word stem tokens) and columns correspond to documents.  The columns are grouped so that the first thousand corresponds to comp.os.ms-windows.misc documents, the second thousand to rec.autos documents, and so on.  The 20ngtrain.mat file contains 90% of the tokens in each document and the 20ngtest.mat file contains 10% of the tokens randomly held-out.  Feature selection was done by removing stop words and words < 3 characters, stemming words, and using a normalized IDF threshold of 0.2 to 0.8 to finally select stems to retain (see the selectRowsByNIdf com.pawjaw.linalg.Matrix routine).  Final number of features (word stems) is 8,033.  The file 20ngdict contains the stemmed words (one per line) in the same order as they are used in the rows of the 20ngtrain.mat and 20ngtest.mat files.  The .mat files are in "row column count" sparse matrix format that is easily imported/exported to or from Matlab or Octave.  The com.pawjaw.linalg.Matrix class contains routines to read and write these sparse matrix formats as well as a dense matrix text format also used by Matlab/Octave.  Please note that the routines in this package index rows and columns starting at zero whereas Matlab/Octave indices rows and columns starting at one.

EXAMPLES

Use CVHDP; use 20ngtrain.mat, 20ngtest.mat, and 20ngdict for training, test (held-out log-likelihood), and dictionary input files respectively; use maximum 120 topics; produce 20 log-likelihood estimates; run 100 variational inference iterations; use 2 threads; use standard output, timing, counts, and top_words for log-likelihood estimates, timing results, topic-token assignment counts, and topic-word top words output files respectively; set Gamma shape and scale distribution parameters to 1 and 2 respectively for the prior on the gamma; and set verbosity to display errors and info:

java -jar tm-0.1.jar -m 1 -it 20ngtrain.mat -ie 20ngtest.mat -id 20ngdict -k 120 -e 20 -i 100 -t 2 -ol - -oc timing -on counts -ot top_words -ag 1 -bg 2 -v 2

Use CGLDA; 20ngtrain.mat; use 40 topics; 50 burnin iterations; 200 Gibbs sampler estimates at a frequency of 1; use topic_words and document_topics as the output files for the topic-word (phi) and document-topic (theta) matrices respectively; output timing results to standard output; and set verbosity to quiet

java -jar tm-0.1.jar -m 0 -it 20ngtrain.mat -k 40 -n 50 -l 200 -q 1 -opm topic_words -otm document_topics -oc - -v 0

EXPERIMENTS

To verify the correctness of the CVHDP implementation and compare the results against CGLDA, experiments were performed similar to those conducted in [2] using a similar 20 Newsgroup database subset.  The specific objectives included comparing the predictive power of CVHDP against CGLDA using held-out log-likelihood, investigating the impact on held-out log-likelihood of the topic-truncation method described in [2] for CVHDP, investigating the model selection properties of CVHDP, and comparing the human-intepretability of topics discovered by both models.

Tests were run using 20, 40, 80, and 120 topics (CGLDA) / topic-truncation thresholds (CVHDP).  Up to 12,000 steps were used for the Gibbs sampler or variational inference routines.  Steps are defined as in [2] to be the number of iterations of the sampler or inference routines multiplied by the number or maximum number of topics.  Figure 1 shows the log-likelihood of the held-out dataset (10% of the data) after training on the primary dataset (90% of the data) using 12,000 steps.  Figure 2 shows the evolution of the predictive capability of the models during training.  Results shown are the averages of 10 randomly initialized restarts.  Standard deviation across the restarts was negligible.

The following observations were made.  A) In every case, CGLDA showed greater predictive capability than CVHDP (i.e. CGLDA had higher log-likelihood given the same number of topics / maximum topics) ranging from a difference of < 0.1 at K = 20 to > 0.3 at K = 120.  B) CVHDP reached convergence faster than CGLDA in terms of number of steps even if the log-likelihood at convergence was lower.  C) Log-likelihood evolution was not strictly monotonic for CVHDP while it was for CGLDA.  D) Increasing number of topics (CGLDA) or maximum number of topics (CVHDP) strictly improved the log-likelihood score for CGLDA but in some cases decreased the score of CVHDP.

Compared with [2], observations (A), (C), and (D) were mostly inconsistent, while observation (B) was consistent.  In a few instances in [2], it seems that CGLDA did produce higher log-likelihood than CVHDP and that increasing the maximum number of topics for CVHDP did not improve the log-likelihood score.  Because the feature selection method used on the 20 Newsgroup dataset in [2] is not published in detail, and because various approximations and parameter assumptions were needed for implementation, it is not possible to draw any conclusive comparisons against the results of the experiments in [2].  Access to the CVHDP code used in [2] was not available for side-by-side comparison.

To investigate the model selection properties of CVHDP, Figures 3.1 and 3.2 compare the evolution of topic/token assignments during training.  It is clear to see that CGLDA tries to use all topics more or less equally throughout training whereas CVHDP shows a marked tendency to focus assignments on a small group of topics.  Though Figures 3.1 and 3.2 show training at 120 topics, experiments at lower topics showed the same tendency of CVHDP to focus around a small group of topics.  In other words, the topic truncation limit in CVHDP did not seem to affect the ultimate number of topics used by CVHDP until some lower limit of topics.  Also unshown in the figures was the impact on different hyperparameter initializations for CVHDP.  Changing various hyperparameters did not seem to produce dramatic differences in the number of topics used by CVHDP.  Apparently the "rich get richer" / stick-breaking paradigm of CVHDP can empirically translate to a narrow concentration of topics utilized for token assignment largely unaffected by the maximum number of available topics or small differences in hyperparameter initialization.

It is unclear whether this paradigm actually reveals the true number of topics.  Intuitively, the true number of topics and distribution over words would not include duplicates and would somehow capture semantically significant and independent concepts.  One would also conceive that topics at multiple resolutions would be included such that big-picture high-level concepts shared amongst many documents as well as narrow highly-focused concepts shared amongst few documents would appear.  Even though HDP is not hierarchical in the way in which topics directly relate to each other, it does appear that topics at different resolutions are discovered (based on the significant non-uniformity of the topic-token assignment counts shown in Figure 3.2).  Tables 1.1 and 1.2 show the top-20 word stems (ranked by descending probability in topic-word mixture matrix phi) for the top-30 topics (ranked by descending count of topic-token assignments at convergence).  A subjective evaluation of the human-interpretability and model selection capabilities of both models can be conducted by examining and comparing these two tables.

REFERENCES

[1] I. Porteous, D. Newman, A. Ihler, A. Asuncion, P. Smyth, and M. Welling. Fast collapsed Gibbs sampling for Latent Dirichlet Allocation. SIGKDD, 2008;
[2] Y. W. Teh, K. Kurihara, and M. Welling. Collapsed variational inference for HDP. NIPS, 2007.
[3] J. Rennie. 20 Newsgroups data set. http://people.csail.mit.edu/jrennie/20Newsgroups/.

LICENSE

Copyright 2011 Brad Block, Pawjaw, LLC. (brad@pawjaw.com).  The contents of this distribution are free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.  The contents of this distribution are made available in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.  You should have received a copy of the GNU General Public License in this distribution.  If not, see <http://www.gnu.org/licenses/>.
