Efficient Continuous-Time Markov Chain Estimation

Monir Hajiaghayi, Bonnie Kirkpatrick, Liangliang Wang, Alexandre Bouchard-Côté
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(1):638-646, 2014.

Abstract

Many problems of practical interest rely on Continuous-time Markov chains (CTMCs) defined over combinatorial state spaces, rendering the computation of transition probabilities, and hence probabilistic inference, difficult or impossible with existing methods. For problems with countably infinite states, where classical methods such as matrix exponentiation are not applicable, the main alternative has been particle Markov chain Monte Carlo methods imputing both the holding times and sequences of visited states. We propose a particle-based Monte Carlo approach where the holding times are marginalized analytically. We demonstrate that in a range of realistic inferential setups, our scheme dramatically reduces the variance of the Monte Carlo approximation and yields more accurate parameter posterior approximations given a fixed computational budget. These experiments are performed on both synthetic and real datasets, drawing from two important examples of CTMCs having combinatorial state spaces: string-valued mutation models in phylogenetics and nucleic acid folding pathways.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-hajiaghayi14, title = {Efficient Continuous-Time Markov Chain Estimation}, author = {Hajiaghayi, Monir and Kirkpatrick, Bonnie and Wang, Liangliang and Bouchard-Côté, Alexandre}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {638--646}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/hajiaghayi14.pdf}, url = {https://proceedings.mlr.press/v32/hajiaghayi14.html}, abstract = {Many problems of practical interest rely on Continuous-time Markov chains (CTMCs) defined over combinatorial state spaces, rendering the computation of transition probabilities, and hence probabilistic inference, difficult or impossible with existing methods. For problems with countably infinite states, where classical methods such as matrix exponentiation are not applicable, the main alternative has been particle Markov chain Monte Carlo methods imputing both the holding times and sequences of visited states. We propose a particle-based Monte Carlo approach where the holding times are marginalized analytically. We demonstrate that in a range of realistic inferential setups, our scheme dramatically reduces the variance of the Monte Carlo approximation and yields more accurate parameter posterior approximations given a fixed computational budget. These experiments are performed on both synthetic and real datasets, drawing from two important examples of CTMCs having combinatorial state spaces: string-valued mutation models in phylogenetics and nucleic acid folding pathways.} }
Endnote
%0 Conference Paper %T Efficient Continuous-Time Markov Chain Estimation %A Monir Hajiaghayi %A Bonnie Kirkpatrick %A Liangliang Wang %A Alexandre Bouchard-Côté %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-hajiaghayi14 %I PMLR %P 638--646 %U https://proceedings.mlr.press/v32/hajiaghayi14.html %V 32 %N 1 %X Many problems of practical interest rely on Continuous-time Markov chains (CTMCs) defined over combinatorial state spaces, rendering the computation of transition probabilities, and hence probabilistic inference, difficult or impossible with existing methods. For problems with countably infinite states, where classical methods such as matrix exponentiation are not applicable, the main alternative has been particle Markov chain Monte Carlo methods imputing both the holding times and sequences of visited states. We propose a particle-based Monte Carlo approach where the holding times are marginalized analytically. We demonstrate that in a range of realistic inferential setups, our scheme dramatically reduces the variance of the Monte Carlo approximation and yields more accurate parameter posterior approximations given a fixed computational budget. These experiments are performed on both synthetic and real datasets, drawing from two important examples of CTMCs having combinatorial state spaces: string-valued mutation models in phylogenetics and nucleic acid folding pathways.
RIS
TY - CPAPER TI - Efficient Continuous-Time Markov Chain Estimation AU - Monir Hajiaghayi AU - Bonnie Kirkpatrick AU - Liangliang Wang AU - Alexandre Bouchard-Côté BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-hajiaghayi14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 1 SP - 638 EP - 646 L1 - http://proceedings.mlr.press/v32/hajiaghayi14.pdf UR - https://proceedings.mlr.press/v32/hajiaghayi14.html AB - Many problems of practical interest rely on Continuous-time Markov chains (CTMCs) defined over combinatorial state spaces, rendering the computation of transition probabilities, and hence probabilistic inference, difficult or impossible with existing methods. For problems with countably infinite states, where classical methods such as matrix exponentiation are not applicable, the main alternative has been particle Markov chain Monte Carlo methods imputing both the holding times and sequences of visited states. We propose a particle-based Monte Carlo approach where the holding times are marginalized analytically. We demonstrate that in a range of realistic inferential setups, our scheme dramatically reduces the variance of the Monte Carlo approximation and yields more accurate parameter posterior approximations given a fixed computational budget. These experiments are performed on both synthetic and real datasets, drawing from two important examples of CTMCs having combinatorial state spaces: string-valued mutation models in phylogenetics and nucleic acid folding pathways. ER -
APA
Hajiaghayi, M., Kirkpatrick, B., Wang, L. & Bouchard-Côté, A.. (2014). Efficient Continuous-Time Markov Chain Estimation. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(1):638-646 Available from https://proceedings.mlr.press/v32/hajiaghayi14.html.

Related Material