2
$\begingroup$

I am working on a model that I am fitting to a medium-sized dataset ($\approx 300,000$ observations). The likelihood I have derived is a mixture model of some Beta distributions which also has the convolution of two Betas. This makes the evaluation of the log-likelihood function slow. The likelihood function has nine variables I am optimizing over. This makes even a coarse grid search very computationally slow, even if I parallelize it. A grid search of just four values per parameter requires $4^9=262,144$ evaluations of the log-likelihood, and still does not give particularly great starting parameters for the optimization. I then use the best set of parameters from the grid search as my starting guess in the actual optimization (optim in R using the L-BFGS-B method as many parameters need to be non-negative or bounded between 0 and 1). Does anyone know of a better and/or faster way to do an MLE over a large number of parameters?

$\endgroup$
1

2 Answers 2

3
$\begingroup$

Consider subsampling your observations, you dont need to use all 300,000 observations to estimate 9 parameters. That is an incredibly large amount of data for a fairly low dimensional parameter vector. If you picked a sub-sample of (say) 10,000 observations then you could minimise this partial likelihood instead which will be a lot faster, and the minimum is probably going to be close to the true minimum using all the data (so you can then use the minimum you find as an initial value for the full minimisation using all the data). If you do this using multiple sub-samples then it might even help you find different local minimas (but are you sure that your likelihood is really highly multimodal? Because with 300,000 observations and only 9 parameters I would expect it to be very sharply peaked).

Better yet, just use stochastic gradient descent instead, where you process the observations one-at-a-time rather than in batch: https://en.wikipedia.org/wiki/Stochastic_gradient_descent

$\endgroup$
9
  • $\begingroup$ I don't think this is good set of advice for this problem. First of all, no need to subsampling. With subsampling you loose information, sure that you can estimate 9 parameters with far less samples (you could go all the way down to 9+1), but the more samples, the more precise the result will be. 300k parameters should with no problem fit RAM of desktop PC & the computation time should take not more then minutes, so no reason why the size should be problem. $\endgroup$
    – Tim
    Jun 24, 2020 at 6:23
  • $\begingroup$ Moreover, yes, mixture models are multimodal by design, there is no single true minimum. Also SGD is not the best choice of algorithm. First of all, it is not the most efficient optimization algorithm in general. Second, for mixtures there are specialised algorithms (like E-M) that are known to work better. $\endgroup$
    – Tim
    Jun 24, 2020 at 6:25
  • $\begingroup$ Hi Tim, I think you misunderstood my suggestion. The point of using subsampling is to get a good initial value for the full minimisation problem. I.e. to find an estimate of theta which is likely to be close to the true minimum, and then use this as the initial condition for optimisation when using the full 300,000 observations. $\endgroup$
    – James
    Jun 24, 2020 at 16:57
  • $\begingroup$ There is no reason why EM would be superior to stochastic gradient descent in a mixture model context when the number of observations is large, since so much computational effort in EM is being 'wasted' by using the full set of observations to produce overly accurate estimates of quantities which will already be precisely estimated using only a small subset of the data. As such, SGD will be able to run hundreds of thousands of iterations in the time it takes EM to run a single iteration. I would expect SGD to perform better for this reason, but its data-set dependent. $\endgroup$
    – James
    Jun 24, 2020 at 17:06
  • 2
    $\begingroup$ papers.nips.cc/paper/… arxiv.org/pdf/0712.4273.pdf (note that these are both discussing stochastic vs batch EM. If I was the OP personally then I'd first try vanilla SGD to see how well it performed since its trivial to implement, and only think about implementing stochastic EM if it didnt work well. But with 300000 observations I'd definitely be using some kind of stochastic/minibatch algorithm, if the likelihood is taking too long to evaluate) $\endgroup$
    – James
    Jun 24, 2020 at 18:55
2
$\begingroup$

Unless for trivial problems, of simple hyperparameter tuning, nobody uses grid search as an optimization algorithm. Mixture of beta distributions is parametrized by continuous parameters, so there is infinitely many values of the parameters, and their combinations, that you would need to check. This would not end in finite time if using grid search.

There is a whole branch of mathematics devoted to optimization and a number of algorithms for optimizing different functions. In R there are build-in optim and optimize functions, while in python there is scipy.optimize.minimize that provide the most popular optimization algorithms. Those algorithms take the function that you want to minimize and find the values for you. However, please take time to read the documentation first and read about the algorithms, since those functions implement many different algorithms, where some are known to work better for some classes of problems, then others.

As for mixture, the most popular algorithm for fitting mixtures is E-M algorithm, in fact, the linked Wikipedia page uses Gaussian mixture as an example illustrating the algorithm.

Since you do not seem to be familiar with optimization, I'd recommend to start with learning more about it. There's a handbook Algorithms for Optimization by Kochenderfer and Wheeler and recorded Stanford lectures by Stephen Boyd, that could serve as a nice introduction.

$\endgroup$
2
  • $\begingroup$ You are correct in that I am not familiar with the algorithms used in optimization, but I think you misunderstood me. I am using a grid search to only get a good starting guess for my optimization (I am using optim in R for the actual optimization). Without the grid search, optim is falling into many local minimums (negative log-likelihood function) and failing to find the global minimum as it is a complicated likelihood. I question was there a better way to do this? I have thought about writing an EM algorithm, but didn't know how much it would help/speed it up. $\endgroup$ Jun 23, 2020 at 23:01
  • $\begingroup$ @DrunkDeriving I wouldn't expect grid search to help in here, mixture models just have many local optimas because of the nature of mixture distribution that is build of different distributions, so has many peaks. That is why there are specialized algorithms like E-M for that, the general optimization algorithms are likely to fail in here. $\endgroup$
    – Tim
    Jun 24, 2020 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.