Hidden Markov Models Training Using Hybrid Baum Welch - Variable Neighborhood Search Algorithm
Abstract
Hidden Markov Models (HMM) are used in a wide range of artifificial intelligence applications including speech recognition, computer vision, computational biology and fifinance. Estimating an HMM parameters is often addressed via the Baum-Welch algorithm (BWA), but this algorithm tends to convergence to local optimum of the model parameters. Therefore, optimizing HMM parameters remains a crucial and challenging work. In this paper, a Variable Neighborhood Search (VNS) combined with Baum-Welch algorithm (VNS-BWA) is proposed. The idea is to use VNS to escape from local minima, enable greater exploration of the search space, and enhance the learning capability of HMMs models. The proposed algorithm has entire advantage of combination of the search mechanism in VNS algorithm for training with no gradient information, and the BWA algorithm that utilizes this kind of knowledge. The performance of the proposed method is validated on a real dataset. The results show that the VNS-BWA has better performance fifinding the optimal parameters of HMM models, enhancing its learning capability and classifification performance.References
Velasco, A., James, B. T., Wells, V. D., Girgis, H. Z. (2019). Look4TRs: A de-novo tool for detecting simple tandem repeats using self-supervised hidden Markov models. Bioinformatics.
Pachter L, Alexandersson M, Cawley S (2002) Applications of generalized pair hidden Markov models to alignment and gene finding problems. J Comput Biol 9(2):389-399
Mao, S., Tao, D., Zhang, G., Ching, P. C., Lee, T. (2019). Revisiting Hidden Markov Models for Speech Emotion Recognition. ICASSP 2019
Han, S. Y., Liefbroer, A. C., Elzinga, C. H. (2019). Mechanisms of family formation: An application of Hidden Markov Models to a life course process. Advances in Life Course Research.
Singh, M., Kumar, S., Kumar, S., Garg, T. (2019). Credit Card Fraud Detection Using Hidden Markov Model. International Journal of Engineering and Computer Science, 8(11), 24878-24882.
Monir, E.A., Ouzineb, M., Benyacoub, B.: Multi dimensional Hidden markov model for credit scoring systems in Peer-To-Peer (P2P) lending. BDNT (2019). LNNS, vol. 81, pp. 73-83. Springer, Cham.
Ge-Er, T., Chang-Zheng, H., Jin, X., Xiao-Yi, J.: Customer credit scoring based on HMM/GMDH hybrid model. Knowl. Inf. Syst. 36(3), 731-747 (2013).
Baum L.E., Petrie T., Soules G. Weiss N., A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains, Ann. Math. Stat., Vol. 41, No. 1, pp. 164-171. (1970)
R. Thomsen, Evolving the topology of hidden Markov models using evolutionary algorithms, in: Proceedings of Parallel Problem Solving from Nature VII (PPSN-2002), 2002, pp. 861-870.
T.-Y. Chen, X.-D. Mei, J.-S. Pan, S.-H. Sun, Optimization of hmm by the tabu search algorithm., Journal Information Science and Engineering 20 (5) (2004) 949-957.
Aupetit, S., Monmarch´e, N., Slimane, M. (2006). Hidden Markov Models Training by a Particle Swarm Optimization Algorithm. Journal of Mathematical Modelling and Algorithms, 6(2), 175-193.
Hidden markov models training using population-based metaheuristics S Aupetit, N Monmarch´e, M Slimane - Advances in metaheuristics for hard optimization, (2007)
Kordnoori, S., Mostafaei, H., Behzadi, M. H. (2019). PSO Optimized Hidden Markov Model Performance Analysis for IEEE 802.16/WiMAX Standard. Wireless Personal Communications.
Li, Xiaolin, Marc Parizeau, and Rjean Plamondon. Training hidden markov models with multiple observations-a combinatorial method. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, no. 4: 371-377.(2000)
N. Mladenovic, P. Hansen, Variable neighborhood search, Computers and Operations Research 24 (1997) 1097-1100.
Hansen, P., Mladenovic, N., Perez, J.A.M.: Variables neighborhood search: methods and applications. Ann. Oper. Res. 175, 367-407 (2010)
Z. Amirgaliyeva, N. Mladenovic, R. Todosijevic, and D. Urosevic. Solving the maximum min-sum dispersion by alternating formulations of two different problems. European Journal of Operational Research, 2016.
Defryn and K. Sorensen. A fast two-level variable neighborhood search for the clustered vehicle routing problem. Computers and Operations Research, 2017. ISSN 0305-0548.
N. Amaldass, C. Lucas, N. Mladenovic, Variable neighbourhood search for Financial derivative problem, Yugoslav Journal of Operations Research 29 (2019) 359-373. .
Jose A. Moreno Perez, Pierre Hansen and Nenad Mladenovic, Parallel Variable Neighborhood Search. Parallel Metaheuristics: A New Class of Algorithms Chapter 11 (pages 247-266)
https://www.lendingclub.com/info/download-data.action
Siddiqi, N. (2017). Intelligent credit scoring: Building and implementing better credit risk scorecards (2nd ed.). Hoboken, NJ: Wiley.
G Navas-Palencia. Optimal binning: mathematical programming formulation (2020) http://arxiv.org/abs/2001.08025
- 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).
