GHK algorithm
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The GHK algorithm (Geweke, Hajivassiliou and Keane)[1] is an importance sampling method for simulating choice probabilities in the multivariate probit model. These simulated probabilities can be used to recover parameter estimates from the maximized likelihood equation using any one of the usual well known maximization methods (Newton's method, BFGS, etc.). Train[2] has well documented steps for implementing this algorithm for a multinomial probit model. What follows here will apply to the binary multivariate probit model.
Consider the case where one is attempting to evaluate the choice probability of Pr(𝐲𝐢|𝐗𝐢𝜷,Σ) where 𝐲𝐢=(y1,...,yJ), (i=1,...,N) and where we can take j as choices and i as individuals or observations, 𝐗𝐢𝜷 is the mean and Σ is the covariance matrix of the model. The probability of observing choice 𝐲𝐢 is
- Pr(𝐲𝐢|𝐗𝐢𝜷,Σ)=∫AJ⋯∫A1fN(𝐲i∗|𝐗𝐢𝜷,Σ)dy1∗…dyJ∗Pr(𝐲𝐢|𝐗𝐢𝜷,Σ)=∫𝟙y∗∈AfN(𝐲i∗|𝐗𝐢𝜷,Σ)d𝐲i∗
Where A=A1×⋯×AJ and,
- Aj={(−∞,0]yj=0(0,∞)yj=1
Unless J is small (less than or equal to 2) there is no closed form solution for the integrals defined above (some work has been done with J=3[3]). The alternative to evaluating these integrals closed form or by quadrature methods is to use simulation. GHK is a simulation method to simulate the probability above using importance sampling methods.
Evaluating Pr(𝐲𝐢|𝐗𝐢𝜷,Σ)=∫𝟙y∗∈AfN(𝐲i∗|𝐗𝐢𝜷,Σ)d𝐲i∗ is simplified by recognizing that the latent data model 𝐲𝐢∗=𝐗𝐢𝜷+ϵ can be rewritten using a Cholesky factorization, Σ=CC′. This gives 𝐲𝐢∗=𝐗𝐢𝜷+Cηi where the ηi terms are distributed N(0,𝐈).
Using this factorization and the fact that the ηi are distributed independently one can simulate draws from a truncated multivariate normal distribution using draws from a univariate random normal.
For example, if the region of truncation 𝐀 has lower and upper limits equal to [a,b] (including a,b = ±∞) then the task becomes
- a<y1∗<ba<y2∗<b⋮⋮⋮a<yJ∗<b
Note: 𝐲𝐢∗=𝐗𝐢𝜷+Cηi, substituting:
- a<x1β1+c11η1<ba<x2β2+c21η1+c22η2<b⋮⋮⋮a<xJβJ+∑k=1JcJ,kηk<b
Rearranging above,
- a−x1β1c11<η1<b−x1β1c11a−(x2β2+c21η1)c22<η2<b−(x2β2+c21η1)c22⋮⋮⋮a−(xJβJ+∑k=1J−1cJ,kηk)cJ,J<ηJ<b−(xJβJ+∑k=1J−1cJ,kηk)cJ,J
Now all one needs to do is iteratively draw from the truncated univariate normal distribution with the given bounds above. This can be done by the inverse CDF method and noting the truncated normal distribution is given by,
- u=Φ(x−μσ)−Φ(a−μσ)Φ(b−μσ)−Φ(a−μσ)
Where u will be a number between 0 and 1 because the above is a CDF. This suggests to generate random draws from the truncated distribution one has to solve for x giving,
- x=σF−1(u∗(F(β)−F(α))+F(α))+μ
where α=a−μσ and β=b−μσ and F is the standard normal CDF. With such draws one can reconstruct the 𝐲𝐢∗ by its simplified equation using the Cholesky factorization. These draws will be conditional on the draws coming before and using properties of normals the product of the conditional PDFs will be the joint distribution of the 𝐲𝐢∗,
- q(𝐲𝐢∗|𝐗𝟏𝜷,Σ)=q(y1∗|𝐗𝟏𝜷,Σ)q(y2∗|y1∗,𝐗𝟏𝜷,Σ)…q(yJ∗|y1∗,…,yJ−1∗,𝐗𝟏𝜷,Σ)
Where q(⋅) is the multivariate normal distribution.
Because yj∗ conditional on yk, k<j is restricted to the set A by the setup using the Cholesky factorization then we know that q(⋅) is a truncated multivariate normal. The distribution function of a truncated normal is,
- ϕ(x−μσ)σ(Φ(b−μσ)−Φ(a−μσ))
Therefore, yj∗ has distribution,
- q(𝐲𝐢∗|𝐗𝐢𝜷,Σ)=1c11ϕ1(yj∗−x1βc11)(Φ1(b−x1βc11)−Φ1(a−x1βc11))×⋯×1cJJϕJ(yJ∗−(xJβ+cJ1η1+cJ2η2+⋯+cJJ−1ηJ−1)cJJ)(ΦJ(b−(xJβ+cJ1η1+cJ2η2+⋯+cJJ−1ηJ−1)cJJ)−ΦJ(a−(xJβ+cJ1η1+cJ2η2+⋯+cJJ−1ηJ−1cJJ))=∏j=1J1cjjϕj(yj∗−∑k=1k<jcjkηkcjj)∏j=1J(Φj(b−∑k=1k<jcjkηkcjj)−Φ(a−∑k=1k<jcjkηkcjj))
where ϕj is the standard normal pdf for choice j.
Because yj|{yk<j∗}∗∼N(𝐗𝐢𝜷+∑k=1k<jcjkηk,cjj2) the above standardization makes each term mean 0 variance 1.
Let the denominator ∏j=1JΦj(b−∑k=1k<jcjkηkcjj)−Φ(a−∑k=1k<jcjkηkcjj)=∏j=1Jljj and the numerator ∏j=1J1cjjϕj(yj∗−∑k=1k<jcjkηkcjj)=fN(𝐲𝐢∗|𝐗𝐢𝜷,Σ) where fN(⋅) is the multivariate normal PDF.
Going back to the original goal, to evaluate the
- Pr(𝐲𝐢|𝐗𝐢𝜷,Σ)=∫AjfN(𝐲i∗|𝐗𝐢𝜷,Σ)dyj∗
Using importance sampling we can evaluate this integral,
- Pr(𝐲𝐢|𝐗𝐢𝜷,Σ)=∫AjfN(𝐲i∗|𝐗𝐢𝜷,Σ)dyj∗=∫AjfN(𝐲i∗|𝐗𝐢𝜷,Σ)q(𝐲𝐢∗|𝐗𝐢𝜷,Σ)q(𝐲𝐢∗|𝐗𝐢𝜷,Σ)dyj∗=∫AjfN(𝐲i∗|𝐗𝐢𝜷,Σ)fN(𝐲i∗|𝐗𝐢𝜷,Σ)∏j=1Jljjq(𝐲𝐢∗|𝐗𝐢𝜷,Σ)dyj∗=𝔼𝐪(∏j=1Jljj)
This is well approximated by 1S∑s=1S∏j=1Jljj.
References
edit edit source- ^ Hajivassiliou, Vassilis (1994). "CLASSICAL ESTIMATION METHODS FOR LDV MODELS USING SIMULATION" (PDF). Handbook of Econometrics. doi:10.1016/S1573-4412(05)80009-1.
- ^ Train, Kenneth (2003). Discrete Choice Methods With Simulation. Cambridge University Press.
- ^ Greene, William (2003). Econometric Analysis. Prentice Hall.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1336794192 under CC BY-SA 4.0; modifications have been made.