Nested fixed point maximum likelihood estimator (NFXP)¶
Description: Nested loop MLE estimator. Combining Newton-Kantorovich iterations with gradient based likelihood maximization. Structural estimation of Rust bus engine replacement model.
Maximum likelihood estimator (MLE)¶
Maximum likelihood estimator is applicable when the model yields a probability distribution for the observable data
- Let $ L(x,\theta) $ denote the distribution (pdf) of the observables $ x $ implied by the model with parameter vector $ \theta $
- Let $ Z_n = (z_i,\dots,z_n) $ denote the data, consisting of $ n $ independent observations (random sample)
MLE and MSM are two main estimation methods for dynamic economic models
Likelihood function¶
- If $ L(x,\theta) $ is a discrete distribution then $ L(x,\theta) $ computed at the data point gives the probability of observing the given data point exactly
- If $ L(x,\theta) $ is a continuous distribution then $ L(x,\theta) $ computed at the data point is analogous to the probability of observing the given data point
Likelihood function is
$$ \mathcal{L}_n(\theta) = L(Z_n,\theta) = \prod_{i=1}^n L(z_i,\theta) $$Definition of MLE estimator¶
$$ \hat{\theta}_{MLE} = \arg\max_{\theta \in \Theta} \, \prod_{i=1}^n \underset{\mathcal{L}(z_i,\theta)}{\underbrace{L(z_i,\theta)}} = \arg\max_{\theta \in \Theta} \mathcal{L}_n(\theta) $$$$ \hat{\theta}_{MLE} = \arg\max_{\theta \in \Theta} \, \sum_{i=1}^n \underset{\ell(z_i,\theta)}{\underbrace{\log L(z_i,\theta)}} = \arg\max_{\theta \in \Theta} \ell_n(\theta) $$- $ \theta \in \Theta $ is parameter space
- $ Z_n = (z_1,\dots,z_n) $ is observed data
Asymptotic properties of MLE¶
- Consistency: $ \; \hat{\theta}_{MLE} \xrightarrow{\mathcal{P}} \theta_0 $
- Asymptotic normality: $ \; \sqrt{n} ( \hat{\theta}_{MLE} - \theta_0 ) \xrightarrow{\mathcal{D}} N(0,\mathcal{I}(\theta_0)^{-1}) $
- Asymptotic efficiency: MLE approaches the smallest possible variance (Cramér-Rao bound) for unbiased estimator when $ n \rightarrow \infty $
- Functional invariance: MLE of $ \gamma_0 = g(\theta_0) $ is given by $ g(\hat{\theta}_{MLE}) $ if $ g(\cdot) $ is continuously differentiable function
Asymptotic variance of MLE estimator¶
$$ \sqrt{n} ( \hat{\theta}_{MLE} - \theta_0 ) \xrightarrow{\mathcal{D}} N(0,\mathcal{I}(\theta_0)^{-1}) \Leftrightarrow \sqrt{\mathcal{I}_n(\theta_0)} ( \hat{\theta}_{MLE} - \theta_0 ) \xrightarrow{\mathcal{D}} N(0,1) $$- variance is given by the inverse of the Fisher information, computed from pdf $ L(x,\theta_0) $
- alternatively, Fisher information matrix can be computed from log-likelihood function $ \ell_n(\theta_0) $ of $ n $ i.i.d. random variables in place of data $ Z_n $
Estimating Fisher information¶
- Fisher information depends on model pdf $ L(x,\theta_0) $, hardly computable
- Can be consistently estimated due to LLN: $ -\tfrac{1}{n} \sum_i^n \frac{\partial^2}{\partial\theta \partial\theta} \ell(z_i,\theta) \xrightarrow{P} \mathcal{I}(\theta_0) $
- This gives observed Fisher information
- Plugging in the estimate $ \hat{\theta} = \hat{\theta}_{MLE} $ in we have
Information equality¶
- similar to the two equivalent definitions for the expected Fisher information, for the observed Fisher information it holds (assuming $ \theta_0 $ in a scalar)
- let parameter $ \theta \in \mathbb{R}^K $ be a vector with $ K $ elements
- need to adjust both second order derivative and the square of the first order derivative
- the square in RHS originates in the calculation of variance of $ \frac{\partial \ell_n(\theta_0)}{\partial\theta} $
Outer product of gradients¶
- consider vector random variable $ \tilde{X} = (\tilde{X}_1,\dots,\tilde{X}_K)^{T} $, so $ \tilde{X} $ is column-vector $ K \times 1 $
- expectation of $ \tilde{X} $ is given by the $ K \times 1 $ vector $ \mathbb{E}\tilde{X} $
- $ K \times K $ variance-covariance matrix $ \Sigma $ of $ \tilde{X} $ is given by the expectation of the outer product $ \otimes $
- variances of the elements of $ \tilde{X} $ are on the main diagonal of $ \Sigma $, whereas the off-diagonal elements contain covariances $ cov(\tilde{X}_i,\tilde{X}_j) $ for all $ i \ne j $
Information matrix equality¶
- let $ H(\ell_n(\theta_0)) = \frac{\partial^2}{\partial\theta \partial\theta} \ell_n(\theta_0) $ denote the $ K \times K $ Hessian matrix of $ \ell_n(\theta_0) $
- let $ \nabla f(\theta) = \frac{\partial}{\partial\theta} f(\theta) $ denote the gradient of $ f(\theta) $, $ K \times 1 $ vector
- let $ \nabla\ell(Z_n, \theta_0) = \big( \frac{\partial}{\partial\theta} \ell(z_1,\theta_0),\dots,\frac{\partial}{\partial\theta} \ell(z_n,\theta_0) \big) $ denote the $ K \times n $ matrix of gradients of $ \ell(z_i,\theta_0) $ stacked for all $ i $
Then we have the information matrix equality
$$ \begin{eqnarray} \hat{\mathcal{J}}_n(\theta_0) = - H(\ell_n(\theta_0)) &=& \sum_{i=1}^n \nabla\ell(z_i, \theta_0) \otimes \nabla\ell(z_i, \theta_0)^{T} \\ &=& \nabla\ell(Z_n, \theta_0) \otimes \nabla\ell(Z_n, \theta_0)^{T} \end{eqnarray} $$- where parameter $ \theta \in \mathbb{R}^K $ is a vector with $ K $ elements
Summary and conclusion¶
$$ \hat{\theta}_{MLE} = \arg\max_{\theta \in \Theta} \, \sum_{i=1}^n \underset{\ell(z_i,\theta)}{\underbrace{\log L(z_i,\theta)}} = \arg\max_{\theta \in \Theta} \ell_n(\theta) $$- $ \theta \in \Theta $ is parameter space
- $ Z_n = (z_1,\dots,z_n) $ is observed data
Berndt-Hall-Hall-Hausman (BHHH) algorithm¶
$$ H(\ell_n(\theta)) = - \nabla\ell(Z_n, \theta) \otimes \nabla\ell(Z_n, \theta)^{T} $$- information matrix equality gives an approximation of the Hessian of the log-likelihood function $ \ell_n(\theta_0) $
- can be used in quasi-Newton optimization method! $ \Rightarrow $ BHHH algorithm
- outer product of gradients result in semi-definite matrix for every $ \theta $ so even if the approximation is not accurate, it will never point Newton iteration in the wrong direction
- search of appropriate step size in the direction found by approximated Hessian is part of the algorithm to ensure global convergence
📖 E.K. Berndt, B.H. Hall, R.E. Hall and J.A. Hausman, 1974 “Estimation and inference in nonlinear structural models”
Back to Rust bus engine replacement model of Harold Zurcher¶
The only model in the course which satisfies the requirements for MLE.
See videos 28, 29 and 44 for the setup and the code base.
Bellman equation(s)¶
- in standard value function space
- in expected value function space
- $ x $ is discretized mileage
- $ \varepsilon $ is the vector of i.i.d. EV1 shocks
- $ d \in \{0,1\} = \{\text{keep},\text{replace}\} $
Zurcher’s preferences¶
$$ u(x_{t},d_t,\theta_1)=\left \{ \begin{array}{ll} -RC-c(0,\theta_1) & \text{if }d_{t}=\text{replace}=1 \\ -c(x_{t},\theta_1) & \text{if }d_{t}=\text{keep}=0 \end{array} \right. $$- $ RC $ = replacement cost
- $ c(x,\theta_1) $ = cost of maintenance with preference parameters $ \theta_1 $
Transition matrix for mileage¶
- If not replacing ($ d=0) $
- If replacing ($ d=1 $), transition probabilities are given by the first row
Choice probabilities¶
Once the fixed point is found, the policy function is given by the optimal choice probability $ P(d|x) $ which has the logit structure due to assumption EV:
$$ P(0|x) = \frac{\exp[ u(x,0) + \beta EV(x,0) ]}{\sum_{d\in \{0,1\}} \exp[u(x,d) + \beta EV(x,d)]} $$$$ P(0|x) = \frac{1}{1 + \exp[u(x,1) - u(x,0) + \beta EV(x,1) - \beta EV(x,0)]} $$Where we are so far¶
- for every value of structural parameters $ \theta = (RC,\theta_1,\theta_20,\dots,\theta_20,\beta) $
- we can solve the model fast using NK iterations within the polyalgorithm
- based on the solution $ EV_\theta(x,d) $ can form choice probabilities $ P(\text{keep}|x,\theta) $ and $ P(\text{replace}|x,\theta) $
Next: given the data on mileage ($ x $) and choices ($ d $), can form likelihood function $ L(x,d,\theta) $, and proceed with maximum likelihood estimation
Data¶
- Harold Zurcher’s Maintenance records of 162 busses in 8 groups
- Monthly observations of mileage on each bus (odometer reading)
- Data on maintenance operations:
- Routine periodic maintenance (i.e. brake adjustment)
- Replacement or repair at time of failure
- Major engine overhaul and/or replacement (the focus of the paper)
Data $ (x_{i,t},d_{i,t}) $ where $ x_{i,t} $ is discretized mileage (bin indexes), and $ d_{i,t} $ is the observed choice at this mileage for each bus $ i $ in each month $ t $
Likelihood function¶
$$ \mathcal{L}_n(\theta, EV_\theta) = \prod_{i=1}^{162}\prod_{t=2}^{T_i} P(d_{i,t}|x_{i,t}) \pi(x_{i,t}|x_{i,t-1},d_{i,t-1}) $$$$ \ell_n(\theta,EV_\theta) = \log \mathcal{L}_n(\theta,EV_\theta) = \sum_{i=1}^{162}\sum_{t=2}^{T_i} \big ( \log P(d_{i,t}|x_{i,t}) + \log \pi(x_{i,t}|x_{i,t-1},d_{i,t-1}) \big) $$MLE estimator¶
$$ \hat{\theta} = \arg\max_\theta \ell_n(\theta, EV_{\theta}) $$Unconstrained optimiztion, but retires the computation of $ EV_{\theta} $ for each value of parameter $ \theta $
Nested loop¶
Outer loop = Hill-climbing algorithm
- Log-likelihood function $ \ell_n(\theta,EV_{\theta}) $ is maximized with respect to $ \theta $
- Quasi-Newton algorithm with BHHH approximation of Hessian
- Each evaluation of $ \ell_n(\theta,EV_{\theta}) $ requires solution for the fixed point $ EV_{\theta} $
Inner loop = Fixed point algorithm
- Solver for the fixed point of the Bellman operator $ EV_{\theta} = \Gamma(EV_{\theta}) $
- Successive approximations (VFI) + Newton-Kantorovich iterations in a polyalgorithm
Important details¶
- Performance: gradient based Newton method to maximize likelihood
- Analytical gradients: using implicit function theorem and chain rule for the outer loop, and Fréchet derivative for the inner loop
- Use BHHH: outer product of gradient approximation for Hessian
- Numerical stability: recenter logsum and choice probabilities
- Further info: NFXP manual (see further learning resources)
Analytical gradient of the likelihood function¶
$$ \frac{\partial}{\partial \theta} \ell_n(\theta,EV_\theta) = \sum_{i=1}^{162}\sum_{t=2}^{T_i} \big ( \frac{\partial}{\partial \theta} \log P(d_{i,t}|x_{i,t}) + \frac{\partial}{\partial \theta} \log \pi(x_{i,t}|x_{i,t-1},d_{i,t-1}) \big) $$- straightforward with multiple application of chain rule
- the key point is expressing derivatives of the expected value function $ \frac{\partial EV_{\theta}}{\partial \theta} $, which is done with Banach space version of implicit function theorem, applied to the fixed point equation
- $ \Gamma_{\theta}(\cdot) $ is the (finite approximation of) Bellman operator in expected function space
- $ \frac{\partial \Gamma_{\theta}}{\partial EV_{\theta}} $ is the (finite approximation of) Fréchet derivative
Implementation¶
zurcherclass fully implements the inner loop (see video 44)- need to write the outer loop: likelihood function optimizer, and calculator for standard errors of the estimates
Alternative implementation: ruspy module Maximilian Blesch and the computational economics group at the University of Bonn
https://ruspy.readthedocs.io/en/latest/index.html https://github.com/OpenSourceEconomics/ruspy
Further learning resources¶
- 📖 Adda Cooper “Dynamic Economics” pp. 83-85
- Note on Information Matrix Equality http://web.econ.ku.dk/munk-nielsen/notes/noteInformationMatrix.pdf
- Matlab implementation of full solver and Rust estimator (NFXP) https://github.com/dseconf/DSE2019/tree/master/02_DDC_SchjerningIskhakov
- 📖 John Rust (1987, Econometrica) “Optimal Replacement of GMC Bus Engines: An Empirical Model of Harold Zurcher”
- NFXP manual with detailed instructions on Fréchet derivative in Rust model
- RusPy package https://ruspy.readthedocs.io/en/latest/index.html