3
$\begingroup$

I'm using multinomial probit to estimate some parameters, and I keep seeing references to the fact that MNP was considered computationally "intractible" relative to binomial probit up until the early 21st century. The question is: why? I get that adding variables makes things take longer (I've got a background in CS), but for the life of me I can't see why estimation should be any worse than, say, $O(n^3)$ in the "nomial-ness" of the model. That is, when you add a new choice, you can update your simulations based on transformations of the joint error terms, and from there it's binomial probit with a couple indicators thrown in. Is there something deeper going on in the background that I'm not taking into consideration?

Many thanks, Kyle

Improve this question
$\endgroup$
3
  • $\begingroup$ Really 21st century 2000 and onward? Not 20th, 1900 and onward? Could you please cite these references. I think this is a misquote. $\endgroup$
    – mpiktas
    Commented Dec 15, 2010 at 8:24
  • $\begingroup$ @mpiktas 1900 and onward seems unlikely as the standard probit model dates from 1934/5. What's computationally tractable depends on the available algorithms as well as the available computing power, so 2000 onward seems believable to me. $\endgroup$
    – onestop
    Commented Dec 15, 2010 at 9:35
  • $\begingroup$ @mpiktas, @onestop has it more or less right. The particular example is from a 1993 paper I was reading which used the explicit phrase, "intractible." I've since closed the PDF, but the history of computation intuitively seems to support my characterization. $\endgroup$
    – kyle
    Commented Dec 17, 2010 at 7:14

2 Answers 2

Reset to default
4
$\begingroup$

It boils down to how you feel about assuming the Independence of Irrelevant Alternatives (IIA) as an assumption about choice behaviour. So the first thing to do is look that up.

Multinomial logit assumes IIA and multinomial probit does not. The computational price of not assuming it is what gets expensive. Almost any econometrics text will cover the details, but assuming you already understand logistic regression, the intuitive picture is this:

In latent variable formulation, logistic regression models need to integrate over a latent distribution to get the probability of a 1 rather than a 0. In choice modelling contexts this is thought of as the expected utility of choosing 1 rather than 0, although we only see the final (stochastic) choice.

A similar situation arises when there are multiple choices. If we are happy to assume IIA, that is: that a third choice does not affect your relative preferences over two existing choices, then the integrals are separable and straightforward. If you are not happy to assume IIA (and that can be reasonable when the new choice is a plausible substitute for one of the existing ones) then you will have to estimate an arbitrary (unobserved) covariance structure over all the options and then do the multidimensional integrations to get your choice probabilities out. It is these integrations or replacements for them that cause the computational problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, that's helpful. I'd combine this with @onestop's response for a full answer -- looking into the GHK algorithm provides the math behind what you're explaining. That is, while multidimensional integrals are hard, it doesn't necessarily seem to me that they'd cause extreme issue: we tend to simulate these things anyway, so adding another dimension is just generating one more set of random draws. Looking at how GHK smooths this process, though, helps demonstrate why it takes some time (I think). $\endgroup$
    – kyle
    Commented Dec 17, 2010 at 7:18
3
$\begingroup$

The currently popular method of fitting multinomial probit models is maximum simulated likelihood using the Geweke–Hajivassiliou–Keane algorithm (Geweke 1989; Hajivassiliou and McFadden 1998; Keane and Wolpin 1994). So the algorithm dates from the late 1990s. If you've thought up a more efficient method I suggest you submit it to Econometrica.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.