Solving Singularity Issues in the Estimation Of Discrete Choice Models
M Bierlaire, M Thémans, Ecole Polytechnique Fédérale de Lausanne, CH
We propose an estimation algorithm designed for overspecified discrete choice models, that such that not all parameters can be identified.
Discrete choice models play an important role in transportation analysis. The complexity of recent models, such as mixtures of multinomial logit (MNL) models or generalized extreme value (GEV) models, complicates the estimation procedure. Not only simulation is necessary to compute approximations of the probability models, but the log-likelihood function to maximize is highly nonlinear, non concave and ill-conditioned, producing slow convergence of optimization algorithms. Also, as detailed by Walker (2001), mixture of MNL models (such as heteroscedastic error component models) may not be identified, and the normalization condition may depend on the estimated value of the parameters. In this case, it is mandatory to estimate models which are structurally overspecified. For such models, whatever the data set, there is a singularity in the second
derivative matrix of the loglikelihood function, and the convergence can be very slow.
We propose to investigate the case of unconstrained optimization (maximum likelihood estimation without constraints on parameters) when an afine singularity arises in the objective function. We propose to perform an eigen-structure analysis on the second derivatives matrix of the objective function which allows us to characterize the subspace where the singularity lies. Once the singularity has been properly identified, we fix this singularity by adding constraints in order to better guide the algorithm towards a local solution of the optimization problem. It can be seen
as an artificial bending of the loglikelihood function in the subspace where it is flat.
As the identification of the singularity is an iterative process taking place within the optimization algorithm, those constraints producing the bending must be included "on-the-fly" during the optimization process.
This second part is achieved using trust-region based algorithms.
We present numerical results with the current version of our algorithms designed to solve singular unconstrained optimization problems. The presented algorithms are integrated in the BIOGEME software. The tests are performed on classical singular problems as well as on the estimation of various discrete choice models (involving singularity issues) using BIOGEME. Then we briefly address the convergence theory of the proposed optimization methods. We eventually discuss the future modifications to generalize our algorithms to deal with singular constrained optimization.
Association for European Transport