Relative efficiency appraisal of discrete choice modeling algorithms using small-scale maximum likelihood estimator through empirically tailored computing environment

It is common practice to carry out mathematical modeling for transportation planning, design, and operation by using readily available commercial software packages. Generally, the estimation processes are embedded in the software while developing the software package. This leads to constraints for users due to lack of information on the underlying analytical procedure for the model parameter estimation. This practice also applies to discrete choice model parameter estimation. There has been a general consensus that transportation modellers do not need to put extra efforts to come up with tailored computer codes dedicated solely for their unique modelling need. This may work in most cases; however, it may fail to work for very specific cases. In this context, the lack of flexibility in the computing environment could be exemplified through a situation, where the researchers choose ‘non-linear-in-parameters’ specification. Commercial packages cannot handle such a specification, and thus, the researcher might be forced to write a specific computer code dedicated only for that work [1, 2].

Advances in statistical computing language are readily available and could be applied as modeling base to all estimation procedures in a systematic way. A number of suitable computing languages for model estimation have improved significantly over the past years from, when reliance was almost exclusively on commercial software. As the statistical computing language of modeling has evolved significantly, more sophisticated modeling procedures could now be tailored by researchers in accordance with the level of transport modeling analysis. In an effort to relax limitations of software, researchers are strongly encouraged to use their own modeling computer codes [3]. On the basis of a clear understanding of analytical procedures that are repeatedly taking place during the estimation processes, researchers would be able to use different estimation algorithms and empirically modify/improve some portions of estimation processes. Eventually, with diverse numerical experiments, this repetitive task will help in proposing a new advanced/improved estimation procedure based on certain performance criterion.

Additionally, transportation researchers have not paid much attention on how to go beyond the limitation of using commercial packages in terms of carrying out entire modelling procedures with tailored computing environments [4]. This purpose is pursued in this research with a small scale discrete choice model, namely the binary logit model. The main objective of this research is to implement all analytical procedures involved in discrete choice modelling with visual basic application (VBA) and to present results of numerical experiments solely through possible tailored modeling. The other objectives of this research are (a) to identify the factors affecting the model estimation performance and (b) to suggest potential research topics related to custom-built modeling.

This section presents a binary logit choice function derived from the multinomial logit (MNL) choice function. The binary logit model is used as the target choice function for experimentation in this research. The derivation procedure adopted here helps in understanding not only the model’s limitations but also the conceptual background based on which the model is built. Consequently, researchers can differentiate MNL from other types of discrete choice models with utmost clarity and may try with a variety of experimental model estimation trials. Based on the research by Train [3] and Ben-Akiva and Lermans [5], the algebraic manipulation to get a final logit choice function is described here in details. MNL model, which is a prototype model of discrete choice models, is formulated based on the random utility concept. The probability that any alternative in C _n is chosen by decision makers can be formulated as in Eq. 1. C _n is actual choice set that the decision maker (n) can consider in the given choice situation.where P _n (i) is the probability of choosing a alternative i by decision maker n; U _ni and U _nj are representative utility of the alternatives i and j of the decision n, ∀j ∊ C _n , i ≠ j indicates comparison of all alternatives except for the same alternative. Based on assumption, the utility can be divided into systematic and random parts (shown in Eq. 2). where S _ni is the systematic (or deterministic, observable, constant) part of the representative utility of alternative i when faced by decision maker n and is observable to a researcher, and R _ni is the random (unobservable, error) part of the representative utility of alternative i when faced by decision maker n and is unobservable to a researcher. Usually, various discrete choice models are derived from Eq. (3), which depends on the mathematical distribution (e.g., Gumbel Type I, and Weibull, etc.)that the random component (R _ni, R _nj ) follows. Therefore, using density function of Gumbel Type I (or Weibull), the density for each random parts relation is shown in Eq. 4 and the cumulative distribution is presented in Eq. 5.

In Eq. (3), if R _ni is not known, then the choice probability of P _n (i) is a cumulative distribution, whose value is determined at S _ni – S _nj  + R _ni , as given in Eq. (5).where R _nj is distributed independently for all alternatives, i ≠ j and it is logical that the Eq. 3 means that the choice probability is the product of the individual value of cumulative distribution obtained using Eq. 6. Equation 7 presents this function.

As mentioned earlier, R _ni is unknown and is assumed to have a distribution. By integration of P _n (i)|R _ni , P _n (i) will be determined as shown in Eq. 8.

Some more algebraic interpolations need to be made to reach the final form of logit choice function. The remained processes are given below:

The Eq. (13) can be simplified as follows:

Let \( e^{{ - R_{ni} }} = Z, \) and after differentiating with respect to R _ni , it becomes \( - e^{{ - R_{ni} }} \text{d}R_{ni} = \text{d}Z \). It is noted that if R _ni  → ∞ then, Z → ∞, if R _ni  → ∞ then Z → 0. Replacing these terms in Eq. 15, the final logit choice function is obtained as below (See Eq. 18).

The final form of probabilistic MNL model consists of two parts. The denominator represents the total utility of all the alternatives considered in the choice set and theutility of a particular alternative is given in the numerator. The binary logit model is utilized as numerical experimental base in this research, which can be simplified from Eq. 18 by assuming that only two alternatives are available in the mode choice market. Assuming two alternatives (auto and transit) are available; the Eq. 18 can be simplified into the binary logit choice formulation as shown in Eq. 19, where S _na and S _nt are the systematic part of the representative utility of alternative auto and transit, respectively.

In off-the-shelf software application for modeling, the software primarily enables a researcher to find the optimal set of parameter estimates under a given estimation algorithm, where, estimation factors are prefixed by the vendor. However in custom-built modeling environments, finding parameter estimates typically depends on iteration method predefined earlier in chosen estimation algorithm. Furthermore, to make the estimation operational, a researcher will be directed to input initial estimation factors which would affect the overall estimation performance at the initial stage of estimation. These factors include step size and convergence criterion. Six algorithms are applied to experimentally estimate parameters with a given model specification in the binary logit choice model framework. It is noticed during the course of this research, that the iteration method involved in each six algorithms mutates each other than updating process of approximate Hessian. Therefore, we discussed in detail the role of estimation factors including the estimation method based on the Newton–Raphson (NR) algorithm in the following paragraphs.

Newton–Raphson algorithm uses the real Hessian matrix in its estimation routine by employing true Hessian values generated from the second-derivative of log-likelihood function. The computations for obtaining real Hessian matrix are expensive and costly. Moreover, majority of work associated with the analytical derivation of log-likelihood function are extensive, nevertheless it is very useful [4]. In this research, the mathematical relationships for the real Hessian matrix are formulated by means of direct analytical derivatives from the given log-likelihood function (Eq. 25) and the final form of matrix is provided through the Eqs. 29‐31. Translating estimation procedures into computer codes involves: 1) understanding the fundamental iteration rule for Newton–Raphson algorithm, and 2) separating the functionality of estimation procedures into independent, interchangeable modules. The estimation method of Newton–Raphson employed in this research can be derived by taking the second order Taylor’s approximation of LL(β _t + 1) around LL(β _t ) and the details are as follows. The Taylor’s series expansion of f(x) around f(x ₀) can be written as below [4].

The above function can be shortened by taking the second-order approximation of Taylor’s series as shown below:

It should be noted that f(x) is LL(β _t + 1) and f(x ₀) is LL(β _t ) in Eq. (34). Based on the Eq. (35), the maximization value of β _t + 1 can be found by setting \( \frac{{\partial LL(\beta_{t + 1} )}}{{\partial \beta_{t + 1} }} = 0 \). The first derivatives with respect to β _t + 1 results in

Consequently, by solving the Eq. 36 for the value of β _t + 1, the iteration rule of Newton–Raphson is represented by the following formula:where β _t is the parameter estimates after t iterations, β _t + 1 is the parameter estimates after t + 1 iterations, λ is the step size, ( −H _tReal ^NR )⁻¹ is the inverse of the negative real Hessian matrix in iteration t, G _t is a vector of gradient in iteration t, ( −H _tReal ^NR )⁻¹ G _t is the search direction of the function in iteration process. Stated more simply, β _t + 1 which is (t + 1) th parameter estimates is equal to β _t which is tth parameter estimates plus negative inverse Hessian multiplied by gradient. A way of the estimation method of other five algorithms considered in this research can be found in detail in the previous study conducted by Roh and Khan [4], Train [3], and Green [6].

In this study, both H _tReal ^NR and G _t are the average value of the Hessian and gradient. The Hessian and gradient are calculated at each step and continuously updated till the convergence. Based on the fact that the log-likelihood function of logit probability is always globally concave [7], the following paragraph explains how parameters are searched during iteration process from the initial guessing points to final convergence of parameter estimates.

The “the direction to follow” concept in the context of iteration method is shown in Fig. 1. G _t is the slope of the log-likelihood function and H _tReal ^NR shows the change in slope of the log-likelihood function. In cases of global concave function, H _tReal ^NR is always negative and thus (H _tReal ^NR )⁻¹ is also negative. The negative of this negative Hessian, −(H _tReal ^NR )⁻¹ G _t is positive. Therefore, the direction of −(H _tReal ^NR )⁻¹ G _t depends entirely on the sign of G _t . If the G _t is positive, β _t moves to the right direction (Fig. 1a), otherwise, β _t moves to the left direction (Fig. 1b) according to the iteration rule seen in Eq. 37. Its step size is given by a researcher at the initial stage of iteration and its magnitude is given by the term, λ( −H _tReal ^NR )⁻¹ G _t , included in the iteration rule. In either case, β _t is moved to the best value that maximizes the log-likelihood function.

The step size implied by λ( −H _tReal ^NR )⁻¹ G _t is decreased, if the curvature represented by −(H _tReal ^NR )⁻¹ has a large value in its magnitude (Fig. 2a); otherwise, the step size is increased (Fig. 2b).

For understanding “step size” in the context of iteration method, it is useful to know the maximization of LL(β):(LL(β) = A + Bβ + Cβ ²), and it’s convergence to maximum. In the case of quadratic function, the optimum value can be obtained with one iteration [3]. However, the problem is that most LL(β) are not quadratic in nature and they require more than one iteration to attain the optimum. This problem can be solved by choosing an appropriate initial step size, and hence minimizing the iteration number and convergence time. The step size determination is explained in the subsequent paragraph.

The computer codes developed for this research worked successfully within the simulated discrete choice model estimation environments. The values of parameter estimates of the model are compared with true value [5] and it is found that the values of parameter estimates are closer in magnitude across six algorithms. This means that the computer codes developed for this empirical estimation worked on right estimation track. The parameter estimates for six algorithms are presented in Table 1 with different step sizes, which λ shows the best performance in a given convergence criterion: CR = 10⁻⁴. It can also be noted that all estimation procedures involved in discrete choice modelling are completely translated into tailored computer estimation codes. The purpose of this research is to get in-depth understanding of calculation mechanism underlying in discrete choice modeling, not to develop a model. Therefore, statistical explanations of parameters are not within the scope of this research.

The relative performances of algorithms are compared by using the three performance measures: number of iteration, iteration time, and convergence time. In the first case, we chose different convergence criteria and the second case is involved with different initial guesses of the parameter values. After applying various step sizes along with the iteration rule, the experimental runs that converged successfully are selected and summarized.

Before presenting experiment results, overall convergence characteristics of six algorithms is presented using 3D convergence surface as shown in Fig. 5. Only a run showing the best performance for each algorithm is depicted in 3D convergence surface. Variation of log-likelihood values for all observations in each iteration are continuously saved in server until the estimation process is terminated. Unique convergence behaviour of estimation algorithms determined by Hessian updating mechanism prefixed in each algorithm can be clearly demonstrated. Log-likelihood values are presented on Z-axis; the number of iterations is on X-axis, and observation numbers for estimation sample are on Y-axis (Fig. 5b). In Fig. 5a, log-likelihood value is calculated for each observation from the first iteration and it showed the same value (−0.693147181). This value resulted from the assumption that all parameter values are zero in the initial stage of estimation in the model specification. NR, as shown in Fig. 5a, shows the most simple convergence behaviour in terms of small number of iteration (X-axis), meaning that short convergence time. The log-likelihood value for NR was stared with −14.55609079 and converged with the value of −6.166042212 at 6th run. Algorithms performance for DFP and BFGS are shown in Fig. 5e, f respectively. It can be easily seen, that their convergence pattern are similar in terms of both the number of iterations and convergence time. BHHH and BHHH-2 are presented in Fig. 5b, c respectively and are also very similar in their convergence behaviour. These similarities are the result of using almost same iterative process in terms of updating approximate Hessian matrix. SN shown in Fig. 5d, showed similar performance with BHHH and BHHH-2.

Discrete choice analysis has been of interest to researchers in many diverse disciplines for consumer’s choice behaviour prediction. Particularly, in transportation domain, there have been many applications of discrete choice modeling techniques to predict the behaviour of users consuming transportation systems or services. However, almost all research associated with discrete choice modeling focuses only on the interpretation of the estimated results or on the efforts to find policy implications in model parameters to support decision making process. Furthermore, almost all types of discrete choice models are carried out using commercial statistical packages. In the earlier generation of discrete choice modeling, it was common practice to follow instructions of a selected specific computer package. However, as the choice model specification becomes more complicated and custom-built modeling is increasingly in demand, researchers working in the modeling domain are challenged to go beyond the first generation modeling practices. Nonetheless, there is a lack of literature available to research on estimation algorithms as well as important components in it. Although, some literatures on this may be available in econometric field [8‐10], they are not directly related to the concerns of transportation modellers. Also, these studies have a different theoretical base, which puts some constraints to write the computer codes for transportation modeling application.

Several factors that dominate estimation performance are detected through this experimental model estimation. These are: (a) convergence criterion; (b) initial guessing of starting points. In this research a convergence criterion of \( \left[ {\frac{1}{k}\sum\nolimits_{k = 1}^{k} {(\beta_{t + 1,k} - \beta_{t,k} )^{2} } } \right]^{1/2}, \) is used, which is generally accepted convergence criterion in many literatures [8, 9]. Based on the results, some important aspects might be considered in more elaborated research associated with custom-built modeling. Possibly, potential research extensions are noted below.

(a) Different mathematical formulations for stopping criterion may be tried and different level of stopping accuracy such as \( \left[ {\frac{1}{k}\sum\nolimits_{k = 1}^{k} {(\beta_{t + 1,k} - \beta_{t,k} )^{2} } } \right]^{1/2} < 10^{ - 6} \), 10⁻⁷ can be adopted to make a significant difference in model estimation performance. This issue should be revisited in the future work.

(b) When researchers have to make a guess on initial parameters starting points in custom-built modeling, it would be time saving to make an initial guess of model’s parameters fairly close to true values on the first trial. However almost all choices of initial guess of parameters set up by researchers are not the actual parameter estimates of the given model. In this context, it is a challenge for researchers to be more organized in choosing a vector of parameters, which may be a critical subject in custom-built modeling. This suggests that initial guessing of parameters can affect a model estimation performance to a high extent in terms of iteration numbers, convergence time and so on. A similar research study was reported by Liu and Mahmassani [11] that uses an empirical model estimation process for obtaining parameters of a probit model. They use the genetic algorithm for making a guess of initial parameter estimates. The authors of this paper have demonstrated that initial guessing of parameter can have significant effect on overall model estimation performance. All these issues addressed here are note worthy for future extension of research reported in this paper.