More Web Proxy on the site http://driver.im/

research-article

Fast and Highly Scalable Bayesian MDP on a GPU Platform

Authors:

Sunil P. Khatri,

Cliff SzeAuthors Info & Claims

ACM-BCB '17: Proceedings of the 8th ACM International Conference on Bioinformatics, Computational Biology,and Health Informatics

Pages 158 - 167

https://doi.org/10.1145/3107411.3107440

Published: 20 August 2017 Publication History

Abstract

By employing the Optimal Bayesian Robust (OBR) policy, Bayesian Markov Decision Process (BMDP) can be used to solve the Gene Regulatory Network (GRN) control problem. However, due to the "curse of dimensionality", the data storage limitation hinders the practical applicability of the BMDP. To overcome this impediment, we propose a novel Duplex Sparse Storage (DSS) scheme in this paper, and develop a BMDP solver with the DSS scheme on a heterogeneous GPU-based platform. The simulation results demonstrate that our approach achieves a 5x reduction in memory utilization with a 2.4% "decision difference" and an average speedup of 4.1x compared to the full matrix based storage scheme. Additionally, we present the tradeoff between the runtime and result accuracy for our DSS techniques versus the full matrix approach. We also compare our results with the well known Compressed Sparse Row (CSR) approach for reducing memory utilization, and discuss the benefits of DSS over CSR.

References

[1]

John Asmuth and Michael L Littman 2011. Approaching Bayes-optimalilty using Monte-Carlo tree search Proceedings of the 21st International Conference on Automated Planning and Scheduling.

[2]

Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk Van Der Vorst 2000. Templates for the solution of algebraic eigenvalue problems: a practical guide. SIAM, Philadelphia, PA.

Digital Library

[3]

Nicole Bauerle and Ulrich Rieder 2009. MDP algorithms for portfolio optimization problems in pure jump markets. Finance and Stochastics Vol. 13, 4 (2009), 591--611.

[4]

Nicole Bauerle and Ulrich Rieder 2011. Markov decision processes with applications to finance. Springer Science & Business Media, New York, NY.

[5]

Richard Bellman. 1957. A Markovian decision process. Technical Report. DTIC Document.

[6]

Richard E Bellman and Stuart E Dreyfus 2015. Applied dynamic programming. Princeton university press, Princeton, New Jersey.

[7]

Oded Berman and Eungab Kim 1999. Stochastic models for inventory management at service facilities. Stochastic Models, Vol. 15, 4 (1999), 695--718.

[8]

Arthur Earl Bryson. 1975. Applied optimal control: optimization, estimation and control. CRC Press, Boca Raton, FL.

[9]

Xiaodong Cai, Juan Andrés Bazerque, and Georgios B Giannakis 2013. Inference of gene regulatory networks with sparse structural equation models exploiting genetic perturbations. PLOS Computational Biology Vol. 9, 5 (2013), e1003068.

[10]

Nir Friedman and Yoram Singer 1998. Efficient Bayesian parameter estimation in large discrete domains Proceedings of the 11th International Conference on Neural Information Processing Systems. MIT Press, 417--423.

Digital Library

[11]

Arthur Guez, David Silver, and Peter Dayan. 2012. Efficient Bayes-adaptive reinforcement learning using sample-based search Proceedings of Advances in Neural Information Processing Systems. 1025--1033.

Digital Library

[12]

Michael Hecker, Sandro Lambeck, Susanne Toepfer, Eugene Van Someren, and Reinhard Guthke. 2009. Gene regulatory network inference: data integration in dynamic models - a review. Biosystems, Vol. 96, 1 (2009), 86--103.

[13]

Arie Hordijk and L. C. M. Kallenberg 1979. Linear programming and Markov decision chains. Management Science, Vol. 25, 4 (1979), 352--362.

Digital Library

[14]

Ronald A Howard and James E Matheson 1972. Risk-sensitive Markov decision processes. Management science, Vol. 18, 7 (1972), 356--369.

[15]

Hawoong Jeong, Sean P Mason, A-L Barabási, and Zoltan N Oltvai 2001. Lethality and centrality in protein networks. Nature, Vol. 411, 6833 (2001), 41--42.

[16]

James John Martin. 1967. Bayesian decision problems and Markov chains. John Wiley & Sons, Hoboken, NJ.

[17]

Arnab Nilim and Laurent El Ghaoui 2005. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, Vol. 53, 5 (2005), 780--798.

Digital Library

[18]

Martin L Puterman. 2014. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, Hoboken, NJ.

[19]

Martin L Puterman and Moon Chirl Shin 1978. Modified policy iteration algorithms for discounted Markov decision problems. Management Science, Vol. 24, 11 (1978), 1127--1137.

Digital Library

[20]

Yousef Saad. 1989. Krylov subspace methods on supercomputers. Scientific and Statistical Computing Vol. 10, 6 (1989), 1200--1232.

Digital Library

[21]

Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM, Philadelphia, PA.

Digital Library

[22]

Brian Sallans and G. E. Hinton 2004. Reinforcement learning with factored states and actions. Journal of Machine Learning Research Vol. 5, Aug (2004), 1063--1088.

Digital Library

[23]

Ilya Shmulevich and Edward R Dougherty 2010. Probabilistic Boolean networks: the modeling and control of gene regulatory networks. SIAM, Philadelphia, PA.

Digital Library

[24]

Olivier Sigaud and Olivier Buffet 2013. Markov decision processes in artificial intelligence. John Wiley & Sons, Hoboken, NJ.

Digital Library

[25]

Jesper Tegner, M. K. Stephen Yeung, Jeff Hasty, and J. J. Collins 2003. Reverse engineering gene networks: integrating genetic perturbations with dynamical modeling. the National Academy of Sciences Vol. 100, 10 (2003), 5944--5949.

[26]

Denis Thieffry, Araceli M Huerta, Ernesto Pérez-Rueda, and Julio Collado-Vides 1998. From specific gene regulation to genomic networks: a global analysis of transcriptional regulation in Escherichia coli. Bioessays, Vol. 20, 5 (1998), 433--440.

[27]

Christopher J. C. H. Watkins and Peter Dayan 1992. Q-learning. Machine learning, Vol. 8, 3--4 (1992), 279--292.

Digital Library

[28]

Mohammadmahdi R Yousefi and Edward R Dougherty 2014. A comparison study of optimal and suboptimal intervention policies for gene regulatory networks in the presence of uncertainty. EURASIP Journal on Bioinformatics and Systems Biology, Vol. 2014, 1 (2014), 6.

[29]

He Zhou, Jiang Hu, Sunil P Khatri, Frank Liu, Cliff Sze, and Mohammadmahdi R Yousefi 2016. GPU acceleration for Bayesian control of Markovian genetic regulatory networks Proceedings of the 3rd International Conference on Biomedical and Health Informatic. IEEE, 304--307.

Cited By

Constantinescu DNavarro ACorbera FFernández-Madrigal JAsenjo R(2020)Efficiency and productivity for decision making on low-power heterogeneous CPU+GPU SoCsThe Journal of Supercomputing10.1007/s11227-020-03257-3Online publication date: 23-Mar-2020
https://doi.org/10.1007/s11227-020-03257-3
Zhou HKhatri SHu JLiu F(2019)A Memory-Efficient Markov Decision Process Computation Framework Using BDD-based Sampling RepresentationProceedings of the 56th Annual Design Automation Conference 201910.1145/3316781.3317748(1-6)Online publication date: 2-Jun-2019
https://dl.acm.org/doi/10.1145/3316781.3317748

Index Terms

Fast and Highly Scalable Bayesian MDP on a GPU Platform

Recommendations

A Memory-Efficient Markov Decision Process Computation Framework Using BDD-based Sampling Representation
DAC '19: Proceedings of the 56th Annual Design Automation Conference 2019

Although Markov Decision Process (MDP) has wide applications in autonomous systems as a core model in Reinforcement Learning, a key bottleneck is the large memory utilization of the state transition probability matrices. This is particularly problematic ...
Acceleration of GPU-based Krylov solvers via data transfer reduction

Krylov subspace iterative solvers are often the method of choice when solving large sparse linear systems. At the same time, hardware accelerators such as graphics processing units continue to offer significant floating point performance gains for ...
Algorithmic performance studies on graphics processing units

We report on our experience with integrating and using graphics processing units (GPUs) as fast parallel floating-point co-processors to accelerate two fundamental computational scientific kernels on the GPU: sparse direct factorization and nonlinear ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ACM-BCB '17: Proceedings of the 8th ACM International Conference on Bioinformatics, Computational Biology,and Health Informatics

August 2017

800 pages

ISBN:9781450347228

DOI:10.1145/3107411

General Chairs:
Nurit Haspel
University of Massachusetts Boston, USA
,
Lenore J. Cowen
Tufts University, USA
,
Program Chairs:
Amarda Shehu
George Mason University, USA
,
Tamer Kahveci
University of Florida, USA
,
Giuseppe Pozzi
Politecnico di Milano, Italy

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGBio: ACM Special Interest Group on Bioinformatics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 August 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

BCB '17

Sponsor:

SIGBio

BCB '17: 8th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics

August 20 - 23, 2017

Massachusetts, Boston, USA

Acceptance Rates

ACM-BCB '17 Paper Acceptance Rate 42 of 132 submissions, 32%;

Overall Acceptance Rate 254 of 885 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
132
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Constantinescu DNavarro ACorbera FFernández-Madrigal JAsenjo R(2020)Efficiency and productivity for decision making on low-power heterogeneous CPU+GPU SoCsThe Journal of Supercomputing10.1007/s11227-020-03257-3Online publication date: 23-Mar-2020
https://doi.org/10.1007/s11227-020-03257-3
Zhou HKhatri SHu JLiu F(2019)A Memory-Efficient Markov Decision Process Computation Framework Using BDD-based Sampling RepresentationProceedings of the 56th Annual Design Automation Conference 201910.1145/3316781.3317748(1-6)Online publication date: 2-Jun-2019
https://dl.acm.org/doi/10.1145/3316781.3317748

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents