Monthly Archives: December 2008

Let’s take a step back.  In a lot of applications (especially information retrieval), what you want is some mechanism (such as a predictive model) of generating scores associated with each possible outcome.  And then you measure the loss based on the score of the outcome you wanted versus the score on all other outcomes.   For example, let denote the th outcome and the score of the th outcome.   Then our goal is to optimize where is the “good” outcome.  For example, if we were searching for a needle in a haystack, would be the needle and we want to ensure that the score associated with the needle is much higher than the score associated with the hay.

where is the set of links of interest.   When we use as the link probability function, we can evaluate this quantity analytically:  Here,     The last sum is could be computationally difficult, except that we can rewrite it as where is the total number of possible links and  The gradient of this whole thing is easy enough to compute and we can throw the whole thing into our favorite optimizer using the log barrier method to ensure that doesn’t run away.  

So what happens you might wonder?  Well, for the data I have it becomes unstable and the probability of linkage when two nodes are at all similar approaches 1 and when they are not it approaches 0.  Thus, in practice the log probability becomes a large number minus a large number.  The intuition behind why this happens is a little like the intuition behind separation in regression.  If, on the balance, any covariate is predictive of the output, then it’s coefficient might as well get shoved to (negative) infinity.   Another perspective is by looking at the objective in terms of one covariate (one that governs the current outcome of interest); then where we have put in the denominator other outcomes which have the same response function as the outcome we care about.  No matter what we think about those other outcomes, the objective can be optimized by setting the score for all of these outcomes as high as possible.  

Wow, epic win using this method. But before we get too excited, we should remember that setting the parameters this way has a discriminative flavor. In particular, the word likelihood, that other thing we care about, actually goes down. In contrast to the “proper” generative approach, here you need to set the parameters differently for each task you want to participate in.

In the last post, I presented a comparison of different ways of doing prediction. A natural follow-up question is whether or not there are even better functions?  I observed in the last post that a straight line performs better than the logistic function which has a downward hump.  A natural set of functions to explore then has an upwards hump.   First let’s plot the two probability functions from the previous post along with several new ones (note the color scheme is different): 

Even more link probability functions

It’s worth mentioning that I’ve parameterized them in such a way so as to ensure that the endpoints all line up.  Let’s describe them and see how well they do:

Function	Label	Predictive Likelihood
		-11.4085
…		-11.402
…		-11.4003
	threshold	-11.7929
		-11.3968
		-11.4704
		-11.3747

As it happens, we actually do better by making the hump protrude upwards (i.e., making the function concave.). and both perform better than the previously proposed functions; is easy since it has a simple quadratic form. In other words, it could be a second approximation of something, but of what?   does a little bit better than that. Maybe we’re looking a posterior normality of log likelihoods?  If I knew the answer to this question, I think I’d be able to get a grip on a function which is actually justifiably better…

In the previous post I argued that the second order approximation is useful for prediction.  Let’s apply that to a model with links and see what happens. The random variable over which we take the expectation is now and the second order term is then where is the Hessian matrix.   We address each of these terms in turn.  

Let  Then and  Consequently, the entries of the Hessian are

 Now to compute the covariance.  Observe that by independence.  This can be rewritten as where and

I implemented this new approximation and here are the results.  

Inference method	Parameter estimation	Prediction method	Log likelihood (Higher is better)
	Regularized optimization	first order	-11.755
	Regularized optimization		-11.6019
	Fixed at 4,-3	first order	-11.5183
	Fixed at 4,-3		-11.4354
	Fixed at 4,-3	second order	-11.5192
	Fixed at 4,-3		-11.4352

Suckitude.  The only thing that really matters is

• Fix parameters.
• Use predictive model.

The rest doesn’t matter.  Why?  It might help to look at the plots of the link probability functions.  These are parameterized by and  We use a simplified model here where is assumed to be the same across all components.  In that case, the response is entirely a function of scalar,  I plot the values of the response against different values of this scalar.

Comparison of different link probability functions

Comparison of different link prediction functions (log)

The endpoints are the same but there’s a dip in the middle for  I suppose that although this function seems more “correct,” and is better able to lower the joint likelihood, the dip means that it is less aggressive in proposing positive links and is therefore worse at precision/recall type measures.  

So why not directly optimize the objective we care about?

I was a little bit sneaky in my previous post and the reason I say this will become apparent when I change the function being approximated.  Let’s break it down like this: there are three things we want to compare and And just to add a little more notation, let and

In the previous post, I focused on and I was comparing (3) against both (1) and (2) by virtue of (1) and (2) being equal for this choice of f.  I lamented that the approximation wasn’t so good.  We can try to ameliorate the situation by adding second order terms.  Let’s focus on going from (3) to (2).  (2) is generally the easiest to compute as you only have to evaluate f at one point.  (3) often occurs in the objective function of variational approximations.  Now the second order term here is   (Note that this gives you the result I posted a fe posts back regarding the 2nd order approximation of $\latex f_\pi$) Adding this term in leads to the following results (same methodology as before):

2nd order approximation of

2nd order approximation of

Note that here we do much better than before.  Except for a few errant cases we’re actually down almost an order of magnitude.  We should be happy that we’ve got the problem licked.  Ok, on to the next problem.  Suppose we want to compare (1) and (2).  Note that these are identical for by linearity.  But for they are not.  Again, (1) is easy to compute but (2) is usually what we want for a predictive probability.    The second order term here is simpler since we can disregard the log (as they appear on the outer most layer of both (1) and (2)):   Let’s run the same experiments again, except this time comparing (1) and (2) for only.  

Error using a 1st order predictive approximation

Error using a 2nd order predictive approximation

With a first order approximation, we get some pretty significant errors.  Using the second order approximation greatly reduces those errors (by an order of magnitude).  It seems like the 2nd order approximation is a good idea for this application.  Now the question is, will more accuracy here lead to a better performing model on real data?

In the previous post, I posed two questions.   I’ll answer the second first.

This question considers what would happen if the response function (any response function) were to depend only on a single latent variable.  To use the notation of the previous post, I’d write  Here I will be a little more general and allow to be multinomial rather than binomial.  The model presented in the previous post can then just be written as where with a slight abuse of notation I’m letting denote an indicator vector.  

So it turns out that we can just reduce any choice of to this construction by rewriting  For example, in the model presented several posts earlier, which means that we can represent this in the more general parameterization as   Thus the answer to the question is a non-starter; the previous post already answered it.

The other question asks what would happen if we took the previous post’s model, but made the response a function of instead of  In other words,   This looks pretty similar (in expectation) to the previous model except that is part of the model now rather than just a result of an expectation.  So, if we want to compute it works out to be the same.  But if we want to compute it’s different.  In terms of the original formulation, we are moving the logarithm across the expectation with respect to but NOT across the expectation with respect to  

Moving it as such, it does not have a simple closed form solution, so I can’t provide an analytic solution to the error incurred by moving the log inside the expectation.  However, I can empirically estimate this by sampling from where each is drawn according to a binomial distribution parameterized by  I then compute using this and take the mean over all samples (in this case, 100 samples were used for every point).  I compare this value to the value obtained by computing at the mean over these same samples.   This error is what I plot in the attached figure as a function of

Estimating the loss incurred by moving the log into the expectation.

I produce three series for different values of the number of draws from the binomial distribution used to create   I chose values of  This corresponds to the red line in the previous post.  One thing that is evident is that the error is much smaller.  You can think of the previous post’s curve as the case.  As increases, the covariance on decreases and the error drops.  This is rather comforting.  However, for reasonable values of the errors are still rather large: 0.10 may not seem like a lot in log likelihood, but that’s a lot larger that the difference between most techniques!