American Institute of Mathematical Sciences

Advanced
January  2008, 9(1): 1-10. doi: 10.3934/dcdsb.2008.9.1

Bayesian online algorithms for learning in discrete hidden Markov models

Roberto C. Alamino 1, and  Nestor Caticha 2,

1. 

Neural Computing Research Group, Aston University, Main Building, Birmingham, B7 4ET, United Kingdom
2. 

Instituto de Física, Universidade de São Paulo, CP 66318, São Paulo, SP, CEP 05389-970, Brazil

Received  August 2006 Revised  September 2007 Published  October 2007

We propose and analyze two different Bayesian online algorithms for learning in discrete Hidden Markov Models and compare their performance with the already known Baldi-Chauvin Algorithm. Using the Kullback-Leibler divergence as a measure of generalization we draw learning curves in simplified situations for these algorithms and compare their performances.
Keywords: HMM, generalization error, online algorithm, Bayesian algorithm..
Mathematics Subject Classification: Primary: 68T05; Secondary: 60J20, 62F1.
Citation: Roberto C. Alamino, Nestor Caticha. Bayesian online algorithms for learning in discrete hidden Markov models. Discrete and Continuous Dynamical Systems - B, 2008, 9 (1) : 1-10. doi: 10.3934/dcdsb.2008.9.1
[1]

Aude Hofleitner, Tarek Rabbani, Mohammad Rafiee, Laurent El Ghaoui, Alex Bayen. Learning and estimation applications of an online homotopy algorithm for a generalization of the LASSO. Discrete and Continuous Dynamical Systems - S, 2014, 7 (3) : 503-523. doi: 10.3934/dcdss.2014.7.503
[2]

Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial and Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185
[3]

Tan Bui-Thanh, Omar Ghattas. A scalable algorithm for MAP estimators in Bayesian inverse problems with Besov priors. Inverse Problems and Imaging, 2015, 9 (1) : 27-53. doi: 10.3934/ipi.2015.9.27
[4]

Ruiqi Yang, Dachuan Xu, Yicheng Xu, Dongmei Zhang. An adaptive probabilistic algorithm for online k-center clustering. Journal of Industrial and Management Optimization, 2019, 15 (2) : 565-576. doi: 10.3934/jimo.2018057
[5]

Zongwei Chen. An online-decision algorithm for the multi-period bank clearing problem. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2783-2803. doi: 10.3934/jimo.2021091
[6]

Orazio Muscato, Wolfgang Wagner. A stochastic algorithm without time discretization error for the Wigner equation. Kinetic and Related Models, 2019, 12 (1) : 59-77. doi: 10.3934/krm.2019003
[7]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269
[8]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial and Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057
[9]

Ran Ma, Lu Zhang, Yuzhong Zhang. A best possible algorithm for an online scheduling problem with position-based learning effect. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021144
[10]

Liping Zhang, Soon-Yi Wu, Shu-Cherng Fang. Convergence and error bound of a D-gap function based Newton-type algorithm for equilibrium problems. Journal of Industrial and Management Optimization, 2010, 6 (2) : 333-346. doi: 10.3934/jimo.2010.6.333
[11]

Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117
[12]

Hatim Tayeq, Amal Bergam, Anouar El Harrak, Kenza Khomsi. Self-adaptive algorithm based on a posteriori analysis of the error applied to air quality forecasting using the finite volume method. Discrete and Continuous Dynamical Systems - S, 2021, 14 (7) : 2557-2570. doi: 10.3934/dcdss.2020400
[13]

Xiaojun Zhou, Chunhua Yang, Weihua Gui. State transition algorithm. Journal of Industrial and Management Optimization, 2012, 8 (4) : 1039-1056. doi: 10.3934/jimo.2012.8.1039
[14]

Eliana Pepa Risma. A deferred acceptance algorithm with contracts. Journal of Dynamics and Games, 2015, 2 (3&4) : 289-302. doi: 10.3934/jdg.2015005
[15]

Jonathan Newton, William H. Sandholm. Stochastic dynamics and Edmonds' algorithm. Journal of Dynamics and Games, 2021  doi: 10.3934/jdg.2021029
[16]

François Béguin. Smale diffeomorphisms of surfaces: a classification algorithm. Discrete and Continuous Dynamical Systems, 2004, 11 (2&3) : 261-310. doi: 10.3934/dcds.2004.11.261
[17]

Ali Fuat Alkaya, Dindar Oz. An optimal algorithm for the obstacle neutralization problem. Journal of Industrial and Management Optimization, 2017, 13 (2) : 835-856. doi: 10.3934/jimo.2016049
[18]

Elena Beretta, Markus Grasmair, Monika Muszkieta, Otmar Scherzer. A variational algorithm for the detection of line segments. Inverse Problems and Imaging, 2014, 8 (2) : 389-408. doi: 10.3934/ipi.2014.8.389
[19]

Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027
[20]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control and Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

2021 Impact Factor: 1.497

Tools

Metrics

  • PDF downloads (68)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy