Anyway, here is the report. I'm posting this so that perhaps new students can see that things don't ever work the first time, faculty still have trouble getting their code to work, etc.
The progress of a research idea
============= DAY 1 =============
* Idea
Want to do a form of topic modeling, but where there is meta
information. There are ways to do this, eg., Supervised LDA or
Dirichlet-Multinomial Regression. These both operate on a *feature*
level. For some tasks, it is more natural to operate over a graph.
Along these lines, there's Pachinko Allocation, but this posits a
graph over the vocabulary, not over the documents. (Plus, it is a
DAG, which doesn't make sense for our application.)
Question: how can we augment a standard topic model (eg., LDA), with
an underlying graph, where we assume topics vary smoothly over the
graph?
* Technology
What technology exists for statistical modeling over graphs? Sounds
like a Markov Random Field. So let's marry topic models (LDA) with
MRFs, to give a "Topical Markov Random Field" (TMRF).
We think of LDA a generating documents by first choosing a topic
mixture \theta, and then choosing topics z=k for each word w, where w
is drawn from a multinomial \beta_k.
Where can a graph fit in this? The first idea is to put an MRF over
\theta.
* MRF over \theta
If we have an MRF over theta, then two issues arise. First, we almost
certainly can't collapse out theta as we might like. Okay, we'll live
with that.
Second, from an MRF perspective, what do the potential functions look
like?
The simplest idea is to use pairwise potentials of the form e^{-dist},
where dist is the distance between two thetas that touch on the
graph. What Distance metric should we use? We could use
Bhattacharyya, Hellinger, Euclidean, LogitEuclidean, etc. Let's start
with Hellinger.
What about a variance? We could have lengths in the graph that are
either latent or known. Let's say they're latent and our potentials
have the form e^{-dist/l}, where l is the length (so that if you're
far away, distance doesn't matter.
** Getting data together
We have about 1000 docs and three graphs over those docs. We get them
in a reasonable format and then subsample about 400 of the docs. We
do this both for speed and to make sure we don't overfit the model on
the data too much.
============= DAY 2 =============
** Implementation
We implement this with an option to use or not use graphs (so we can
tell if they're helping). We collapse out \beta, but not \theta in
both cases, and we compute log posteriors.
We run first on some simple test data (testW) from HBC and find that
it seems to be doing something kind of reasonable. We then run on
some real data and it puts everything in one cluster after about 20-30
Gibbs iterations.
Debugging: First, we turn off all graph stuff (sampling lengths) and
things are still broken. Then we initialize optimally and things are
still broken. Then we turn off resampling \theta and things are still
broken. The problem is that I'm using the collapsed \beta incorrectly
when sampling z. I fix it and things work as expected (i.e., not
everything goes in the same cluster).
** Evaluating
So now the code seems to be working, so we want to evaluate. We run a
model with an without a graph (where the graph is something we expect
will help). The posterior probabilities coming out of the two
different models are all over the place.
So we do the standard trick of holding out 20% of the data as "test"
data and then evaluating log likelihood on the test. Here, we do the
"bad" thing and just use 20% of the words in each document (so that we
already have \theta for all the documents). Not great, but easy to
implement. This time, no bugs.
At this point, it's a pain to recompile for every configuration change
and we'd like to be able to run a bunch of configs simultaneously. So
we add a simple command line interface.
In order to evaluate, we plot either posteriors or held-out
likelihoods (usually the latter) as a function of iteration using
xgraph (interacts nicely with the shell and I'm used to it).
Things now seem mixed. There's very little difference when you're not
using a graph between sampling \theta from the true posterior versus
using an MH proposal (this is good for us, since we have to use MH).
There is also little difference between the baseline LDA model and the
MRF models.
We turn off sampling of the lengths and just fix them at one. For the
three graphs we're trying, only one seems to be doing any better than
the baseline LDA model.
** Optimization
Now that we're running experiments, we find that things are taking way
too long to run. So we do some optimization. First, we cache the sum
of all \beta_k posteriors. This helps. Second, we flip \beta from
\beta_{k,w} to \beta_{w,k}, which we've heard helps. It doesn't. We
put it back the other way.
All the time is being spent in resample_z, so we waste a half day
trying to figure out if there's a way to only resample a subset of the
zs. For instance, track how often they change and only resample those
that change a lot (probabilistically). This hurts. Resampling those
with high entropy hurts. I think the issue is that there are three
types of zs. (1) those that change a lot because they have high
uncertainty but are rare enough that they don't really matter, (2)
those that change a lot and do matter, (3) those that just don't
change very much. Probably could do something intelligent, but have
wasted too much time already.
In order to really evaluate speed, we add some code that prints out
timing.
We do one more optimization that's maybe not very common. resample_z
loops over docs, then words, then topics. For each word, the loop
over topics is to compute p(z=k). But if the next word you loop over
is the same word (they are both "the"), then you don't need to
recompute all the p(z=k)s -- you can cache them. We do this, and then
sort the words. This gives about a 20% speedup with no loss in
performance (posterior or held-out likelihood).
** Evaluating again
Since we had some success fixing the lengths at 1, we try fixing them
at 20. Now that one graph is doing noticably better than the baseline
and the other two slightly better. We try 5 and 10 and 50 and nothing
much seems to happen. 20 seems like a bit of a sweet spot.
============= DAY 3 =============
** A more rigorous evaluation
Running with lengths fixed at 20 seems to work, but there's always
variance due to randomness (both in the sampling and in the 80/20
split) that we'd like to account for.
So we run 8 copies of each of the four models (8 just because we
happen to have an 8 core machine, so we can run them simultaneously).
Now, we require more complex graphing technology than just xgraph.
We'll probably eventually want to graph things in matlab, but for now
all we really care about it how things do over time. So we write a
small perl script to extract scores every 50 iterations (we've
switched from 200 to 300 just to be safe) and show means and stddevs
for each of the models.
While we're waiting for this to run, we think about...
* MRF over z?
Our initial model which may or may not be doing so well (we're waiting
on some experiments) assumes an MRF over \th. Maybe this is not the
best place to put it. Can we put it over z instead?
Why would we want to do this? There are some technological reasons:
(1) this makes the MRF discrete and we know much better how to deal
with discrete MRFs. (2) we can get rid of the MH step (though this
doesn't seem to be screwing us up much). (3) we no longer have the
arbitrary choice of which distance function to use. There are also
some technological reasons *not* to do it: it seems like it would be
computationally much more burdensome.
But, let's think if this makes sense in the context of our
application. We have a bunch of research papers and our graphs are
authorship, citations, time or venue. These really do feel like
graphs over *documents* not *words*.
We could turn them in to graphs over words by, say, connecting all
identical terms across documents, encouraging them to share the same
topic. This could probably be done efficiently by storing an inverted
index. On the other hand, would this really capture much? My gut
tells me that for a given word "foo", it's probably pretty rare that
"foo" is assigned to different topics in different documents. (Or at
least just as rare as it being assigned to different topics in the
same document.) Note that we could evaluate this: run simple LDA, and
compute the fraction of times a word is assigned it's non-majority
topic across all the data, versus just across one documents. I
suspect the numbers would be pretty similar.
The extreme alternative would be to link all words, but this is just
going to be computationally infeasible. Moreover, this begins to look
just like tying the \thetas.
So for now, we put this idea on the back burner...
* MRF over \theta, continued...
We're still waiting for these experiments to run (they're about half
of the way there). In thinking about the graph over z, though, it did
occur to me that maybe you have to use far more topics than I've been
using to really reap any benefits here. We begin running with 8, and
then bumped it up to 20. But maybe we really need to run with a lot
more.
So, I log in to two other machines and run just one copy with 50, 100,
150 and 200 topics, just for vanilla LDA. The larger ones will be
slow, but we'll just have to go do something else for a while...
============= DAY 4 =============
* MRF over \theta, re-continued...
Both experiments finish and we see that: (1) with 20 topics and
lengths fixed at 10, there is no difference between raw LDA and TMRF.
(2) More topics is better. Even 200 topics doesn't seem to be
overfitting. Going 20, 50, 100, 150, 200, we get hidden log
likelihoods of -1.43, -1.40, -1.38, -1.36, -1.36 (all e+06). The
significance (from the first experiments) seems to be around .002
(e+06), so these changes (even the last, which differs by 0.005) seem
to be real. Since we weren't able to overfit, we also run with 300
and 400, and wait some more...
...and they finish and still aren't overfitting. We get -1.35 and
-1.35 respectively (differing by about 0.004, again significant!).
This is getting ridiculous -- is there a bug somewhere? Everything
we've seen in LDA-like papers shows that you overfit when you have a
ton of topics. Maybe this is because our documents are really long?
** Model debugging
One thing that could be going wrong is that when we hide 20% of the
words, and evaluate on that 20%, we're skewing the evaluation to favor
long documents. But long documents are probably precisely those that
need/want lots of topics. Our mean document length is 2300, but the
std is over 2500. The shortest document has 349 words, the longest
has 37120. So, instead of hiding 20%, we try hiding a fixed number,
which is 20% of the mean, or 460.
============= DAY 5 =============
** Read the papers, stupid!
At this point, we've done a large number of evals, both with 20% hid,
and 460 words/doc hid (actually, the min of this and doclen/2), and
50-1600 (at *2) topics. We do actually see a tiny bit of overfitting
at 800 or 1600 documents.
Then we do something we should have done a long time ago: go back and
skim through some LDA papers. We look at the BNJ 2003 JMLR paper. We
see that one of the selling points of LDA over LSI is that
it *doesn't* overfit! Aaargh! No wonder we haven't been able to get
substantial overfitting.
However, we also notice something else: aside from dropping 50 stop
words (we've been dropping 100), on one data set they don't prune rare
words at all, and on the other they prune df=1 words only. We've been
pruning df<=5 or <=10 words (can't remember which). Perhaps what's
going on is that the reason the graphs aren't helping is just because
there vocabulary (around 3k) isn't big enough for them to make a
difference!
We recreate the text, pruning only the df=1 words. This leads to a
vocab of about 10k (which means inference will be ~3 times slower).
We run at 50, 100, 200 and 400 and we actualy see a tiny bit of
overfitting (maybe) on 400. We accidentally only ran 100 iterations,
so it's a bit hard to tell, but at the very least there's
no *improvement* for going from 200 topics to 400 topics. Strangely
(and I'd have to think about this more before I understand it),
running on the new text is actually about 5-20% *faster*, despite the
larger vocabulary!
** Re-running with graphs
At this point, we're ready to try running with graphs again. Despite
the fact that it's slow, we settle on 200 topics (this took about 3.5
hours without graphs, so we will be waiting a while). We also want to
run for more iterations, just to see what's going to happen: we do 200
again.
And again there's not much difference. One of the graphs seems to be
just barely one std above everyone else, but that's nothing to write
home about.
============= DAY 6 =============
* Abstracts only?
At this point, things are not looking so spectacular. Perhaps the
problem is that the documents themselves are so big that there's
really not much uncertainty. This is reflected, to some degree, by
the lack of variance in the predictive perplexities.
So we rebuild the data on abstracts only. This makes running
significantly faster (yay). We run 5 copies each of 10, 20, 40, 80,
160 and 320 topics. 40 is a clear winner. 80 and above overfit
fairly badly.
Now, we turn on graphs and get the following results (5 runs):
40-top-nog.default -69239.4 (86.2629700392932)
40-top-nog.auth -68920.0 (111.863756418243)
40-top-nog.cite -68976.4 (174.920839238783)
40-top-nog.year -69174.2 (133.769204228776)
If we compare default (not graphs) to auth (best), we see that we get
a 2-3 std separation. This is looking promising, FINALLY! Also, if
we plot the results, it looks like auth and cite really dominate.
Year is fairly useless.
It suggests that, maybe, we just need more data to see more of a
difference.
* Getting More Data
There are two ways we could get more data. First, we could crawl
more. Second, we could switch over to, say, PubMed or ACM. This
would work since we only need abstracts, not full texts. These sites
have nice interfaces, so we start downloading from ACM.
============= DAY 7 =============
Okay, ACM is a pain. And it's really not that complete, so we switch
over to CiteSeer (don't know why we didn't think of this before!). We
seed with docs from acl, cl, emnlp, icml, jmlr, nips and uai. We
notice that CiteSeer is apparently using some crappy PDF extractor (it
misses ligatures! ugh!) but it's not worth (yet!) actually
downloading the pdfs to do the extraction ourselves ala Braque. From
these seeds, we run 10 iterations of reference crawling, eventually
ending up with just over 44k documents. We extract a subset
comprising 9277 abstracts, and six graphs: author, booktitle,
citation, url, year and time (where you connect to year-1 and year+1).
The 9k out of 44k are those that (a) have >=100 characters
"reasonable" in the abstract and (b) have connections to at least 5
other docs in *all* the graphs. (We're no longer favoring citations.)
We then begin the runs again....
No comments:
Post a Comment