PaperlayerView exact revision on arXiv

Source-linked AI summary

Variational inference for large-scale models of discrete choice

Michael Braun, Jon McAuliffe

arXiv:0712.2526v3stat.MEstat.COstat.ML

TL;DR

Heterogeneous discrete choice models make exact inference difficult, and existing approximate methods can be impractical for large data sets. This paper derives variational procedures for empirical Bayes and fully Bayesian inference in the mixed multinomial logit model. Simulations report negligible variational bias, competitive accuracy, and substantially lower computational cost than MCMC, supporting inference for larger data sets while recognizing limitations of factorized variational distributions.

  • Problem

    The mixed multinomial logit model requires approximate inference because its marginal likelihood is not available in closed form, while MCMC scaling is infeasible for large agent populations.

  • Method

    The paper derives deterministic variational procedures for empirical Bayes and fully Bayesian inference in the mixed multinomial logit model.

  • Results

    Simulations show negligible variational bias and very large computational speedups relative to MCMC for the random utility discrete choice model.

  • Takeaways & Limitations

    Variational methods permit inference for large heterogeneous discrete choice data sets that are difficult to analyze with MCMC.

  • Takeaways & Limitations

    Factorized variational distributions can be inadequate, motivating alternative variational approximations.

Abstract

from arXiv · show

Discrete choice models are commonly used by applied statisticians in numerous fields, such as marketing, economics, finance, and operations research. When agents in discrete choice models are assumed to have differing preferences, exact inference is often intractable. Markov chain Monte Carlo techniques make approximate inference possible, but the computational cost is prohibitive on the large data sets now becoming routinely available. Variational methods provide a deterministic alternative for approximation of the posterior distribution. We derive variational procedures for empirical Bayes and fully Bayesian inference in the mixed multinomial logit model of discrete choice. The algorithms require only that we solve a sequence of unconstrained optimization problems, which are shown to be convex. Extensive simulations demonstrate that variational methods achieve accuracy competitive with Markov chain Monte Carlo, at a small fraction of the computational cost. Thus, variational methods permit inferences on data sets that otherwise could not be analyzed without bias-inducing modifications to the underlying model.

1 Introduction

Heterogeneous discrete choice models require approximate inference because key integrals are generally unavailable in closed form, while MCMC becomes impractical at scale. The paper develops variational procedures for the mixed multinomial logit model and evaluates their accuracy and efficiency against MCMC.

  • Motivation: Heterogeneous models represent agent-specific preferences hierarchically, allowing information to be pooled across decision-makers.Each agent has an unseen preference vector, modeled as a draw from a population-level prior.
  • Inference challenge: In the random utility model, the marginal likelihood lacks a closed form, requiring approximate methods for empirical Bayes and fully Bayesian inference.The paper focuses on this inference problem in the mixed multinomial logit model.
  • Inference challenge: Monte Carlo integration requires the number of draws per agent to grow faster than the square root of the number of agents to match maximum-likelihood asymptotics.The stated growth requirement is infeasible for large-scale problems.
  • Scalability: MCMC becomes increasingly burdensome as the number of agents grows because more output must be collected and stored, even when interest centers on population parameters.Large heterogeneous models are therefore often analyzed using subsets of individuals or choice items, which can discard information and bias estimates.
  • Variational approach: Variational inference offers a deterministic alternative by maximizing a data-dependent lower bound over auxiliary parameters to obtain approximate posterior distributions.The fully Bayesian procedure approximates the joint posterior, whereas empirical Bayes yields a point estimate of the population hyperparameter and approximate individual posteriors.
  • Results: For the random utility model, simulations report negligible variational bias, very large computational speedups, and convergence that is easier to assess than MCMC.The variational representation also remains fixed in size while the MCMC representation grows with the number of draws.
  • Contribution: The paper derives variational algorithms for empirical Bayes and fully Bayesian inference in the mixed multinomial logit model, including a novel delta-method application for variational moments.The procedures are compared with MCMC using an extensive suite of simulated data sets.

2 The mixed multinomial logit model of discrete choice

The mixed multinomial logit model describes repeated choices using agent-specific preferences and population-level heterogeneity. It combines random-utility choice probabilities with a multivariate normal distribution over individual preference vectors, with empirical-Bayes or fully Bayesian population inference.

  • Choice data: Each agent encounters one or more choice events and selects among a finite set of items described by observed attributes.Choice outcomes are represented as categorical indicator vectors, and attribute values may vary across agents and events.
  • Random utility: The model uses a noisy linear utility function in item attributes, with agent-specific taste coefficients and an error term for unobserved utility.Agents are assumed to choose the item maximizing utility.
  • Random utility: Iid Gumbel Type 2 errors imply multinomial-logit choice probabilities, also known as a soft-max function.The resulting probabilities depend on the observed attributes and the agent-specific preference vector.
  • Population heterogeneity: Individual preference vectors are modeled as iid draws from a K-variate normal population distribution with mean ζ and covariance matrix 􀀀.The covariance matrix provides information about correlations among preferences across agents.
  • Population inference: Empirical Bayes estimates the population parameters by maximum marginal likelihood, whereas fully Bayesian inference assigns hyperpriors to ζ and 􀀀.The fully Bayesian specification uses conditionally conjugate normal and inverse-Wishart distributions.

3 Variational inference for the MML model

The paper approximates otherwise intractable posterior inference in the mixed multinomial logit model with variational distributions, for both empirical and hierarchical Bayes. It optimizes an evidence lower bound using coordinate updates that are convex, then extends the procedure to estimate top-level parameters or include them in the approximation.

  • Exact inference is intractable because the posterior-density integrals have no closed form, motivating a deterministic variational alternative to MCMC.
  • Variational inference selects the best member of a tractable family Q to approximate the true posterior, using the variational distribution wherever posterior calculations are needed.The approximation is measured with Kullback–Leibler divergence.
  • The optimal approximation yields the tightest lower bound on the marginal likelihood, so the algorithm maximizes the evidence lower bound rather than evaluating the intractable marginal likelihood directly.The evidence lower bound is denoted L(λ; ζ, 􀀀).
  • Variational empirical Bayes: For empirical Bayes, block coordinate ascent updates variational means and covariances through smooth, unconstrained convex optimization problems.The procedure alternates this variational step with optimization over the top-level parameters ζ and 􀀀, forming a variational EM algorithm.
  • Variational hierarchical Bayes: For hierarchical Bayes, the factorized variational family is extended to include ζ and 􀀀, while coordinate updates remain convex optimizations.The joint posterior is not factorized, but the variational approximation continues to use a family of factorized distributions.

4 Empirical results

The empirical study compares variational empirical Bayes, variational hierarchical Bayes, and MCMC across simulated mixed multinomial logit data sets. Variational methods match MCMC accuracy while converging substantially faster, especially as the number of agents grows.

  • Simulation design: 32 scenarios varied choice items, item attributes, agent counts, and population heterogeneity.The simulations used 3 or 12 choice items, 3 or 10 attributes, 250 to 25,000 agents, and low or high heterogeneity.
  • Inference procedures: VEB, VB, and MCMC were run on observable data from every simulated scenario.MCMC used 6,000 total iterations to generate 500 posterior draws, with 1,000 burn-in iterations and a 10:1 thinning ratio.
  • Accuracy measure: Total variation error measured the distance between each estimated and true predictive choice distribution.The metric equals the maximum difference in probabilities assigned to any choice-item subset.
  • Evaluation procedure: The accuracy comparisons used the median TV error across 25 random new attribute matrices as representative of a typical matrix.The authors report qualitatively similar results across the individual matrices checked.
  • Accuracy: There were no practical accuracy differences among VEB, VB, and MCMC, and all three achieved high accuracy across the data sets.TV error was larger for 12-item than 3-item scenarios, but remained on the same scale across procedures.
  • Speed: Variational methods converged faster than MCMC, with the gap increasing as the number of observed agents increased.For 25,000 agents with 12 items, 10 attributes, and high heterogeneity, MCMC took two days versus one hour for each variational method.

5 Discussion

Variational methods offer computationally efficient inference for heterogeneous discrete choice models when MCMC is infeasible, while retaining the underlying model rather than relying on subsampling or discarded modeling elements.

  • Variational methods enable estimation of hierarchical discrete choice models and can open Bayesian inference to resource-constrained applications.
  • For models with many heterogeneous units, variational methods appear to be the only viable option when resource constraints make MCMC intractable.
  • Variational methods are especially valuable when subsampling is ill-advised and large data sets are needed for reasonable hypothesis-testing power.
  • MCMC is untenable for some large-data models, whereas variational methods provide a computationally practical alternative.
  • When factorized variational distributions are inadequate, mixtures of normals or Dirichlet processes can be applied.
  • The authors recommend using MCMC when possible because it offers consistency guarantees absent from variational methods and has undergone decades of scrutiny.
  • The discussion advises against subsampling data or discarding key modeling elements merely to fit MCMC's time and resource constraints.

A Variational inference and parameter estimation

This section introduces notation used for variational inference and estimation procedures for the mixed multinomial logit model.

  • The appendix describes variational inference and estimation procedures for the mixed multinomial logit model.
  • A ≻0 denotes a positive-definite matrix, A ⪰0 a positive-semidefinite matrix, and |A| the determinant of A.
  • For a scalar function s and vector v, s(v) denotes the vector formed by applying s componentwise.

A.1 The empirical Bayes ELBO

The empirical Bayes ELBO is approximated because the expected log-sum-exp lacks a closed form, using zeroth- and first-order delta-method alternatives with different guarantees and accuracy.

  • The variational distribution is a product of normal distributions parameterized by variational means and covariance matrices.
  • The expected log-sum-exp has no closed form, so variational inference replaces the ELBO objective L with an approximate objective ˜L.
  • The zeroth-order approximation D0 applies Jensen's inequality to the expected log-sum-exp.
  • The first-order approximation D1 restricts the variational covariance matrix to be diagonal and uses a transformed diagonal parameter.
  • D1 does not preserve the guarantee that the optimized variational objective lower-bounds the marginal likelihood.
  • In simulations, D1 produced more accurate variational approximations to the posterior.

A.2 Empirical Bayes variational E-step

The empirical Bayes variational E-step uses block coordinate ascent and unconstrained convex optimization, with covariance parameterized through Cholesky factors to maintain positive semidefiniteness.

  • Block coordinate ascent maximizes the approximate objective over the variational parameters.
  • Each coordinate update solves a smooth, unconstrained convex optimization problem while satisfying the positive-semidefinite covariance requirement.
  • The mean update uses standard unconstrained convex optimization with an analytic gradient, whose structure resembles L2-regularized logistic regression.
  • Covariance matrices are replaced by Cholesky-factor products and optimized over unconstrained lower-triangular matrices.
  • The objective remains concave in the Cholesky factor, and the mean and covariance updates can be optimized jointly in a convex problem.
  • The empirical Bayes M-step includes Gaussian mean estimation and a closed-form covariance-related solution.
  • In the fully Bayesian model, prior distributions for the population parameters add entropy and cross-entropy terms to the variational objective.
  • The fully Bayesian updates are separately concave, and one variational parameter is computed once in advance and held fixed during optimization.

B An application of the delta method

The section applies the multivariate delta method to approximate a function of parameters and then derives the gradient needed to optimize that approximation.

  • The multivariate delta method is used to approximate a function f of a vector in R^K.
  • The approximation is expressed using a matrix x whose rows are the vectors x⊤ and a diagonal matrix defined by exp(σ).
  • The approximation includes the diagonal of the Hessian of f evaluated at µ and a Hadamard-product representation.
  • Optimizing the approximation over µ requires computing its gradient through an extensive but mechanical differential calculation.

C A convexity result

The section establishes concavity and convexity properties of the constituent terms, using composition results and matrix calculus to support a convexity result.

  • Concavity proof: The relevant function is concave on the set of full-rank n × n matrices.
  • Concavity proof: The proof analyzes the three constituent terms from left to right and uses fixed matrices M and P in the corresponding arguments.
  • Matrix calculus: The Hessian of g is represented with the order-n commutation matrix and the Kronecker product.
  • Matrix calculus: The commutation matrix is shown to be matrix positive-definite, supporting the negative-definiteness conclusion for the Hessian of g.
  • Matrix calculus: The vectorization identity vec ABC = (C⊤⊗A) vec B yields equation (50).
  • Concavity proof: The rightmost term in (48) is minus the log-sum-exp function composed with convex functions g_j, so it is concave.Each g_j is convex in t, and the composition argument extends the concavity conclusion from t to B.
Loading 0712.2526v3…