Abstract
We define a class of probabilistic models in terms of an operator algebra of stochastic processes, and a representation for this class in terms of stochastic parameterized grammars. A syntactic specification of a grammar is formally mapped to semantics given in terms of a ring of operators, so that composition of grammars corresponds to operator addition or multiplication. The operators are generators for the time-evolution of stochastic processes. The dynamical evolution occurs in continuous time but is related to a corresponding discrete-time dynamics. An expansion of the exponential of such time-evolution operators can be used to derive a variety of simulation algorithms. Within this modeling framework one can express data clustering models, logic programs, ordinary and stochastic differential equations, branching processes, graph grammars, and stochastic chemical reaction kinetics. The mathematical formulation connects these apparently distant fields to one another and to mathematical methods from quantum field theory and operator algebra. Such broad expressiveness makes the framework particularly suitable for applications in machine learning and multiscale scientific modeling.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Mjolsness, E.: Stochastic process semantics for dynamical grammar syntax: an overview. In: Ninth International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, Florida, 4-6 January 2006
Preston, C.J.: Spatial birth-and-death processes. Bull. Int. Statist. Inst. 46(2), 371–391 (1977)
Lange, K.: Applied Probability. Section 96. Springer, Berlin Heidelberg New York (2004)
Snyder, D.L., Miller, M.I.: Random Point Processes in Time and Space. Wiley, New York (1991)
Athreyea, K.B., Ney, P.E.: Branching Processes. Dover, New York (1972)
Engel, K., Nagel, R.: One-parameter Semigroups for Linear Evolution Equations. Springer Graduate Texts in Mathematics 194, New York (2000)
Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco (1988)
Nodelman, U., Shelton, C., Koller , D.: Continuous time Bayesian networks. In: Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI), pp. 378–387. Morgan Kaufmann, San Francisco (2002)
Dean, T., Kanazawa, K.: A model for reasoning about persistence and causation. Comput. Intell. 5, 142–150 (1989)
Sanghai, S., Domingos, P., Weld, D.: Relational dynamic Bayesian networks. J. Artif. Intell. Res. 24, 759–797 (2005)
Milch, B., Marthi, B., Russell, S., Sontag, D.: BLOG: probabilistic models with unknown objects. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence, pp. 1352–1359 (2005)
St-Aubin, R., Friedman, J., Mackworth, A.K.: A formal mathematical framework for modeling probabilistic hybrid systems. In: Ninth International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, Florida, 4–6 January 2006
Prusinkiewicz, P., Lindenmeyer, A.: The Algorithmic Beauty of Plants. Springer, Berlin Heidelberg New York (1990)
Giavitto, J., Michel, O.: MGS: a programming language for the transformations of topological collections. LaMI – Universite d’ Evry Val d’Essonne. Technical Report 61–2001. Cited in May 2001
Prusinkiewicz, P., Hammel, M.S., Mjolsness, E.: Animation of plant development. Comput. Graph. SIGGRAPH ‘93. 351–360 (1993)
Mjolsness, E., Sharp, D.H., Reinitz, J.: A Connectionist Model of Development. J. Theor. Biol. 152(4), 429–454 (1991)
Phillips, A., Cardelli, L.: A Correct Abstract Machine for the Stochastic Pi-calculus. http://lucacardelli.name/Bibliography.htm Cited Sep 2006 (2006)
Petri, C.A.: Kommunikation mit Automaten. Dissertation, University of Bonn (1962)
Jensen, K.: Coloured Petri Nets I, II, III. Springer, Berlin Heidelberg New York (1997)
Genrich, H.: Predicate/Transition nets. Advances in Petri nets : APN 1, 208–247. (1986)
Haas, P.J.: Stochastic Petri Nets. Springer, Berlin Heidelberg New York (2006)
van Kampen, N.G.: Stochastic Processes in Physics and Chemistry. North-Holland, Amsterdam, The Netherlands (1981)
Reed, M., Simon, B.: Methods of Modern Mathematical Physics: Functional Analysis I. Academic, New York (1972)
Mattis, D.C., Glasser, M.L.: The uses of quantum field theory in diffusion-limited reactions. Rev. Mod. Phys. 70, 979–1001 (1998)
McLachlan, R.I., Quispel, G.R.: Splitting methods. Acta Numer. 11, 341–434 (2002)
Hatano, N., Suzuki, M.: Finding Exponential Product Formulas of Higher Orders. http://arxiv.org/pdf/math-ph/0506007. Cited in 2 Jun 2005 (2005)
Hall, B.C.: Lie Groups, Lie Algebras, and Representations: An Elementary Introduction, pp. 63–76. Springer, Berlin Heidelberg New York (2003)
Müser, M.H.: The path-integral Monte Carlo approach of rigid linear molecules in three dimensions. Mol. Simul. 17(131) (1996)
Dyson, F.: Phys. Rev. 75, 486 (1949)
Risken, H.: The Fokker–Planck Equation. Springer, Berlin Heidelberg New York (1984)
Gillespie, D.J.: A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. J. Comput. Phys. 2, 403–434 (1976)
Shachter, R.: Evaluating influence diagrams. Oper. Res. 33, 871–882 (1986)
Kanazawa, Koller, D., Russell, S.: Stochastic simulation algorithms for dynamic probabilistic networks. In: Proceedings of Uncertainty in Artificial Intelligence 95. http://citeseer.ist.psu.edu/kanazawa95stochastic.html (1995)
Mjolsness, E.: Variable-Structure Systems from Graphs and Grammars. UC Irvine School of Information and Computer Sciences, Irvine. UCI ICS TR# 05-09, http://computableplant.ics.uci.edu/papers/vbl-Struct_GG_TR.pdf (2005)
Ghahramani, Z.: Non-parametric Bayesian methods. In: The 21st Conference on Uncertainty in Artificial Intelligence (UAI 2005), University of Edinburgh, Edinburgh, Scotland, July 26th–July 29th 2005. http://www.gatsby.ucl.ac.uk/~zoubin/talks/uai05tutorial-b.pdf. Cited in Sep 06 (2006)
Geman, S., Geman, D.: Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. 6, 721–741 (1984)
MacQueen, J.B.: Some methods for classification and analysis of multivariate observations. In: Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability (1967)
Dempster, A., Laird, N., Rubin, D.: Maximum likelihood from incomplete data via the EM algorithm. J.R. Stat. Soc. Series B, 1–38 (1977)
Hart, C., et al.: A mathematical and computational framework for quantitative comparison and integration of large-scale gene expression data. Nucleic Acids Res. 33, 2580–2594 (2005)
Jönsson, H., et al.: An auxin-driven polarized transport model for phyllotaxis. Proc. Natl. 1900 Acad. Sciences USA, 103(5), 1633–1638. Retrieved 13 January 2006 from http://www.pnas.1901 org/cgi/content/abstract/103/5/1633 (2006)
Federl, P., Prusinkiewicz, P.: Solving differential equations in developmental models of multicellular structures expressed using L-systems. In: Bubak, M., van Albada, G., Sloot, P., Dongarra, J. (eds.) Proceedings of Computational Science. ICCS 2004, II. Lecture Notes in Computer Science, vol. 3037, pp. 65–72. Springer, Berlin Heidelberg New York (2004)
Jacquez, J.A., Simon, C.P.: The stochastic SI model with recruitment and deaths. I. Comparison with the closed SIS model. Math. Biosci. 117, 77–125 (1993)
Cenzer, D., Marek, V.W., Remmel, J.B.: Using logic programs to reason about infinite sets. In: Eighth International Symposium on Artificial Intelligence and Mathematics. http://rutcor.rutgers.edu/~amai/aimath04/accepted.html (2004)
Cuny, J., Ehrig, H., Engels, G., Rozenberg, G.: Graph Grammars and their Applications to Computer Science. Springer, Berlin Heidelberg New York (1994)
Mjolsness, E.: Symbolic neural networks derived from stochastic grammar domain models. In: Sun, R., Alexandre, R. (eds.) Connectionist Symbolic Integration. Erlbaum, Mahwah, NJ (1997)
Bhan, A., Mjolsness, E.: Static and dynamic models of biological networks. Complexity 11(6), 57–63 (2006)
Turing, A.M.: The chemical basis of morphogenesis. Phil. Trans. Roy. Soc. Lond. B237, 37–72 (1952)
Gor, V., Bacarian, T., Elowitz, M., Mjolsness, E.: Tracking cell signals in fluorescent images. In: Computer Vision Methods for Bioinformatics (CVMB) workshop, at Computer Vision and Pattern Recognition (CVPR). http://computableplant.ics.uci.edu/CVPR-2005.pdf. Cited in June 2005
Shapiro, B.E., et al.: Cellerator: extending a computer algebra system to include biochemical arrows for signal transduction simulations. Bioinformatics 19, 677–678 (2003)
Fracchia, F.D.: Integrating lineage and interaction for the visualization of cellular structures. In: Cuny, J., Ehrig, H., Engels, G., Rozenberg, G. (eds.) Graph Grammars and Their Application to Computer Science. Fifth International Workshop, Lecture Notes in Computer Science 1073, pp. 521–535. Springer, Berlin Heidelberg New York (1996)
Soloveichik, D., Cook, M., Winfree, E., Bruck, J. : Computation with Finite Stochastic Chemical Reaction Networks. manuscript (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mjolsness, E., Yosiphon, G. Stochastic process semantics for dynamical grammars. Ann Math Artif Intell 47, 329–395 (2006). https://doi.org/10.1007/s10472-006-9034-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-006-9034-1
Keywords
- stochastic processes
- operator algebra
- dynamical systems
- multiscale modeling
- probabilistic inference
- machine learning