A Direct Local Search Method and its Application to a Markovian Model
Abstract
While the hidden mixture transition distribution (HMTD) model is a powerful framework for the description, analysis, and classification of longitudinal sequences of continuous data, it is notoriously difficult to estimate because of the complexity of its solution space. In this paper, we explore how a new heuristic specifically developed for the HMTD performs compared to different standard optimization algorithms. This specific heuristic can be classified as a hill-climbing method, and different variants are proposed, including a jittering procedure to escape local maxima and measures to speed up the convergence.Different popular approaches are used for comparison, including PSO, SA, GA, NM, L-BFGS-B, and DE. The same HMTD model was optimized on different datasets and the results were compared in terms of both fit to the data and estimated parameters. Even if the complexity of the problem implies that no one algorithm can be considered as an overall best, our heuristic performed well in all situations, leading to useful solutions in terms of both fit and interpretability.References
Bendtsen, C. (2012) pso: Particle swarm optimization. R package version 1.0.3. Available on https://cran.r-project.org/web/packages/pso/index.html.
Berchtold A. (2001) Estimation in the mixture transition distribution Model. Journal of Time Series Analysis 22(4): 379-397.
Berchtold, A. (2003) Mixture transition distribution (MTD) modeling of heteroscedastic time series. Computational statistics and data analysis 41(3): 399-411.
Berchtold, A. and Raftery, A. (2002) The mixture transition distribution model for high-order Markov chains and non-Gaussian time series. Statistical Science 17(3): 328-356.
Bolano D. and Berchtold A. (2016) General framework and model building in the class of Hidden Mixture Transition Distribution models. Computational Statistics and Data
Analysis 93: 131-145.
Byrd, R. H., Lu, P., Nocedal, J. and Zhu, C. (1995) A limited memory algorithm for bound constrained optimization. SIAM Journal on Scientific Computing 16(5): 1190-1208.
Cerny, V. (1985) Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications 45:41-51.
Elbeltagi, E., Hegazy, T. and Grierson, D. (2005) Comparison among five evolutionary- based optimization algorithms. Advanced Engineering Informatics 19: 43-53.
Fang, L., Chen, P. and Liu S. (2007) Particle swarm optimization with simulated an- nealing for TSP. Proceedings of the 6th WSEAS International Conference on Artificial Intelligence, Knowledge Engineering and Data Bases (AIKED 07).
Holland, J. H. (1992) Genetic algorithms. Scientific American, 267(1): 66-72.
Kennedy, J. and Eberhart, R. (1995) Particle swarm optimization. Proceedings of IEEE International Conference on Neural Networks IV: 1942-1948.
Kirkpatrick, S., Gelatt Jr, C. D. and Vecchi, M. P. (1983) Optimization by simulated annealing. Science 220: 671-680.
Matsumoto, M. and Nishimura, T. (1998) Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation 8(1): 3-30.
Mercer, R.E. and Sampson, J.R. (1978) Adaptive search using a reproductive metaplan. Kybernetes 7(3): 215-228.
Mullen, K., Ardia, D., Gil, D., Windover, D. and Cline, J. (2011) DEoptim: an R package for global optimization by differential evolution. Journal of Statistical Software 40(6): 1-26.
Nelder, J.A. and Mead, R. (1965) A simplex method for function minimization. Computer Journal 7: 308-313.
Premalatha, K. and Natarajan, A.M. (2009) Hybrid PSO and GA for global maximization. International Journal of Open Problems in Computer Science and Mathematics 2(4): 597-608.
Pukkala, T. and Kurttila, M. (2005) Examining the performance of six heuristic optimisation techniques in different forest planning problems. Silva Fennica 39(1):67-80.
R Core Team (2015) R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria. URL: https://www.R-project.org/.
Rabiner, L. (1989) A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE 77(2): 257-286.
Raftery, A. (1985) A model for high-order Markov chains. Journal of the Royal Statistical Society, series B 47(3): 528-539.
Ryden, T. (2008) EM versus Markov chain Monte Carlo for estimation of hidden Markov models: a computational perspective. Bayesian Analysis 3(4): 659-688.
Scott, S. (2002) Bayesian methods for hidden Markov models. Journal of the American Statistical Association 97: 337-351.
Scrucca, L. (2013) GA: A package for genetic algorithms in R. Journal of Statistical Software 53(4).
Shi, Y. and Eberhart, R.C. (1998) A modifed particle swarm optimizer. Proceedings of IEEE International Conference on Evolutionary Computation 69-73.
Singer, S. and Nelder, J. (2009) Nelder-Mead algorithm. Scholarpedia 4(7): 2928.
Srinivas, M. and Patnaik, L. (1994) Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transactions on System, Man and Cybernetics 24(4):656-667.
Storn, R. and Price, K. (1997) Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization 11: 341-359.
Xiang, Y., Gubian, S., Suomela, B. and Hoeng J. (2013) Generalized simulated annealing for global optimization: the GenSA package. The R Journal 5(1).
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
