Category Archives: Uncategorized

In the previous post, I showed how to compute the approximate objective function for regularization.  I implemented such a harness in R with some real data from one of my runs to prototype it.  Directly using nlm seems to work in fits and starts, perhaps because the optimization routine does not use gradients.  The next step then is to compute the gradients.   The gradient of the zero’th order term is where and .  

The second order term is where it gets hard.  Taking the derivative by parts, we get . To compute , we use the derivation in the previous post to show that this is equal to .

I implement all this in R and it seems to converge erratically.  Further more, the “converged” values perform worse than the not fitting at all.   So to summarize results:

• Both and perform best without any M-Step fitting.
• when the first is unfit but the second is fit.
• when both are fit or both are unfit.

This is all very peculiar.  In order to ameliorate the fitting process, I collapsed the parameter space so that so that there are two parameters.   This seems to converge ok, and give results comparable to without fitting for .  When I do the similar parameter collapsing in it performs worse.

In summary, it seems like across the board not fitting is still the best.

Currently there are two regularization penalties, and this is sort of a hack.  Ideally, we’d want to stick with one that is consistent across methods.  This involves simulating additional non-links.   In other words, we want to add to the likelihood we wish to optimize, where is drawn from a distribution of our choosing.  Note that this becomes equivalent to , where .   This is intractable to do exactly so we use the same old Taylor trick.  

This is very important: first-order is NOT enough.  To see why this is, consider that what a first order approximation really says is that you can replace a set of points with their mean.  Well, if you did this in logistic regression for all the 0’s and all the 1’s you’d get a single point for the 0’s and a single point for the 1’s, i.e., complete separability.  And therefore your estimates will diverge.

So what are the ingredients to a second-order approximation?  We first need to compute the gradients of the partition function: , , .  The other thing we need is the variance of .  Note that since variance is shift invariant, we can just compute the variance of .  

We can expand this by .  Typically, covariance has two forms, one for when and when for when .  For convenience, we will denote the first and the latter .  Then this can be rewritten as .  

At this point we need to make about the distribution of .  We will assume that where .  .    Consequently, .

On to the next term: .  Using common properties of the Dirichlet, . This yields .

Finally, notice that .

Below I asked the question of why an approximation which is more accurate seems to be performing worse than one which is more haphazard.  The two methods differ in two principal ways:

• The approximate gradient computed during the E-step.  
• The optimization of the parameters in the M-step.

In the E-step they differ mainly in how they push a node’s topic distribution toward its neighbors’.  With the simple but incorrect method, the gradient is proportional to while the correct method gives .  Intuitively, the last method tells us that the closer we are to the right answer, the less we need to push. 

I futzed with the code to make it so that we push more like the incorrect method, but this didn’t seem to affect the results.  I suspect that is always pretty small so this doesn’t have much of an impact.  Then I tried changing the M-Step.  In particular, I tried removing the M-Step fitting with .  It turns out that this “fit” performs about as well as .  Examining the fits shows that under is consistently smaller than for .  Why is this?  I hypothesize that the L2 regularization penalty is causing this to fail.  Having to determine the optimal penalty is a pain; I originally added this term because the fits were diverging.  Perhaps the right thing to do is figure out why they were diverging in the first place.

It is a good idea to always make sure to make experiments exactly reproducible.  Sometimes in the heat of a paper deadline, a bunch of experiments are run with different parameter settings and what not and a few months down the road one might be hard pressed to remember exactly how you got those numbers.  I’ve learned this the hard way so for the last few submissions I’ve always tried to make sure something in the CVS encodes the precise settings necessary.

Last night, while looking up what I did, I rediscovered that alpha is important sometimes.  Not so much because of scale, but because of the distribution over topics it reports.  My experience is that fitting alpha in an EM context rarely works; it either totally messes up your inference or it just reproduces the alpha that you fed in initially.  But I did get into the habit of having the model fit and spit out alpha after the very last iteration of EM, just get some idea of what the topic distributions look like.

Usually you get something which is pretty uniform over your K topics.  But sometimes you don’t.  In old-fashioned LDA, this usually happens when you have too many topics.  With models such as RTM, you can also get this effect because your graph manifold may have cliques of different sizes.  In these cases, when you’re computing predictive word likelihood of an empty document, you are liable to perform much worse than baseline if you assume a symmetric Dirichlet prior rather than one which reflects the topic distribution on your training set.

The central challenge of variational methods is usually computing expectations of log probabilities.  In the case of the RTM, this is where .

The first term is linear and so is easy enough, the second is problematic though.  One approach is to use a Taylor approximation.  The issue then becomes choosing the point around which to center the approximation.  The partition function above really has two regimes: for small , but for large .  The solution that the delta method uses is to center it at the mean . But does this give us any real guarantee that we won’t be better off by centering it elsewhere? 

I couldn’t really answer this question analytically, so I decided to experiment.  I sampled using settings typical of the corpora I look at.  Turns out that the first order approximation at the mean is really good because the variance on z is really low when you have enough words.

That of course brings up another question.  Why does doing the “correct” () thing not work as well as the “incorrect” () approximation?