skip to main content
article

A probabilistic language based upon sampling functions

Published: 12 January 2005 Publication History

Abstract

As probabilistic computations play an increasing role in solving various problems, researchers have designed probabilistic languages that treat probability distributions as primitive datatypes. Most probabilistic languages, however, focus only on discrete distributions and have limited expressive power. In this paper, we present a probabilistic language, called λο, which uniformly supports all kinds of probability distributions -- discrete distributions, continuous distributions, and even those belonging to neither group. Its mathematical basis is sampling functions, i.e., mappings from the unit interval (0.0,1.0] to probability domains.We also briefly describe the implementation of λο as an extension of Objective CAML and demonstrate its practicality with three applications in robotics: robot localization, people tracking, and robotic mapping. All experiments have been carried out with real robots.

References

[1]
http://www.acfr.usyd.edu.au/homepages/academic/enebot/dataset.htm. Australian Centre for Field Robotics, The University of Sydney.
[2]
P. Bratley, B. Fox, and L. Schrage. A guide to simulation. Springer Verlag, 2nd edition, 1996.
[3]
A. Doucet, N. de Freitas, and N. Gordon. Sequential Monte Carlo Methods in Practice. Springer Verlag, New York, 2001.
[4]
D. Fox, W. Burgard, and S. Thrun. Markov localization for mobile robots in dynamic environments. Journal of Artificial Intelligence Research, 11:391--427, 1999.
[5]
J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675--695, Dec. 1977.
[6]
M. Giry. A categorical approach to probability theory. In B. Banaschewski, editor, Categorical Aspects of Topology and Analysis, pages 68--85. Springer Verlag, 1981.
[7]
V. Gupta, R. Jagadeesan, and P. Panangaden. Stochastic processes as concurrent constraint programs. In 26th ACM POPL, pages 189--202. ACM Press, 1999.
[8]
M. Henrion. Propagation of uncertainty in Bayesian networks by probabilistic logic sampling. In J. F. Lemmer and L. N. Kanal, editors, Uncertainty in Artificial Intelligence 2, pages 149--163. Elsevier/North-Holland, 1988.
[9]
A. H. Jazwinski. Stochastic Processes and Filtering Theory. Academic Press, New York, 1970.
[10]
C. Jones. Probabilistic Non-Determinism. PhD thesis, Department of Computer Science, University of Edinburgh, 1990.
[11]
D. Koller, D. McAllester, and A. Pfeffer. Effective Bayesian inference for stochastic programs. In AAAI-97/IAAI-97, pages 740--747. AAAI Press, 1997.
[12]
D. Kozen. Semantics of probabilistic programs. Journal of Computer and System Sciences, 22(3):328--350, 1981.
[13]
D. J. C. MacKay. Introduction to Monte Carlo methods. In M. I. Jordan, editor, Learning in Graphical Models, NATO Science Series, pages 175--204. Kluwer Academic Press, 1998.
[14]
P. Martin-Löf. On the meanings of the logical constants and the justifications of the logical laws. Nordic Journal of Philosophical Logic, 1(1):11--60, 1996.
[15]
T. Mogensen. Roll: A language for specifying die-rolls. In V. Dahl and P. Wadler, editors, PADL 03, volume 2562 of LNCS, pages 145--159. Springer, 2002.
[16]
E. Moggi. Computational lambda-calculus and monads. In LICS-89, pages 14--23. IEEE Computer Society Press, 1989.
[17]
E. Moggi. Notions of computation and monads. Information and Computation, 93:55--92, 1991.
[18]
M. Montemerlo, N. Roy, and S. Thrun. CARMEN: Carnegie mellon robot navigation toolkit. http://www.cs.cmu.edu/~carmen/.
[19]
M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit. FastSLAM 2.0: An improved particle filtering algorithm for simultaneous localization and mapping that provably converges. In IJCAI-03. Morgan Kaufmann Publishers, Inc., 2003.
[20]
M. Montemerlo, W. Whittaker, and S. Thrun. Conditional particle filters for simultaneous mobile robot localization and people-tracking. In IEEE International Conference on Robotics and Automation (ICRA), 2002.
[21]
S. Park. A calculus for probabilistic languages. In TLDI 03, pages 38--49. ACM Press, 2003.
[22]
S. Park, F. Pfenning, and S. Thrun. A probabilistic language based upon sampling functions. Technical Report CMU-CS-04-173, School of Computer Science, Carnegie Mellon University, 2004.
[23]
A. Pfeffer. IBAL: A probabilistic rational programming language. In IJCAI-01, pages 733--740. Morgan Kaufmann Publishers, 2001.
[24]
F. Pfenning and R. Davies. A judgmental reconstruction of modal logic. Mathematical Structures in Computer Science, 11(4):511--540, 2001.
[25]
D. Pless and G. Luger. Toward general analysis of recursive probability models. In UAI-01, pages 429--436. Morgan Kaufmann Publishers, 2001.
[26]
N. Ramsey and A. Pfeffer. Stochastic lambda calculus and monads of probability distributions. In 29th ACM POPL, pages 154--165. ACM Press, 2002.
[27]
S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 1995.
[28]
N. Saheb-Djahromi. Probabilistic LCF. In Proceedings of the 7th Symposium on Mathematical Foundations of Computer Science, volume~64 of LNCS, pages 442--451. Springer, 1978.
[29]
S. Thrun. Probabilistic algorithms in robotics. AI Magazine, 21(4):93--109, 2000.
[30]
S. Thrun. Towards programming tools for robots that integrate probabilistic computation and learning. In ICRA-00. IEEE, 2000.
[31]
S. Thrun. Robotic mapping: A survey. In G. Lakemeyer and B. Nebel, editors, Exploring Artificial Intelligence in the New Millenium. Morgan Kaufmann, 2002.
[32]
G. Welch and G. Bishop. An introduction to the kalman filter. Technical Report TR95-041, Department of Computer Science, University of North Carolina - Chapel Hill, 1995.

Cited By

View all
  • (2024)A Logic of Knowledge and Justifications, with an Application to Computational TrustStudia Logica10.1007/s11225-024-10165-7Online publication date: 31-Dec-2024
  • (2023)Deterministic stream-sampling for probabilistic programming: semantics and verification2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS56636.2023.10175773(1-13)Online publication date: 26-Jun-2023
  • (2019)Lambda calculus and probabilistic computationProceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3470152.3470186(1-13)Online publication date: 24-Jun-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices
ACM SIGPLAN Notices  Volume 40, Issue 1
Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages
January 2005
391 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1047659
Issue’s Table of Contents
  • cover image ACM Conferences
    POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages
    January 2005
    402 pages
    ISBN:158113830X
    DOI:10.1145/1040305
    • General Chair:
    • Jens Palsberg,
    • Program Chair:
    • Martín Abadi
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 ACM 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 January 2005
Published in SIGPLAN Volume 40, Issue 1

Check for updates

Author Tags

  1. probabilistic language
  2. probability distribution
  3. robotics
  4. sampling function

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)9
  • Downloads (Last 6 weeks)0
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)A Logic of Knowledge and Justifications, with an Application to Computational TrustStudia Logica10.1007/s11225-024-10165-7Online publication date: 31-Dec-2024
  • (2023)Deterministic stream-sampling for probabilistic programming: semantics and verification2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS56636.2023.10175773(1-13)Online publication date: 26-Jun-2023
  • (2019)Lambda calculus and probabilistic computationProceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3470152.3470186(1-13)Online publication date: 24-Jun-2019
  • (2016)An Application of Computable Distributions to the Semantics of Probabilistic Programming LanguagesProceedings of the 25th European Symposium on Programming Languages and Systems - Volume 963210.1007/978-3-662-49498-1_14(337-363)Online publication date: 2-Apr-2016
  • (2015)Probabilistic Abstract InterpretationEssays Dedicated to Hanne Riis Nielson and Flemming Nielson on the Occasion of Their 60th Birthdays on Semantics, Logics, and Calculi - Volume 956010.1007/978-3-319-27810-0_6(111-139)Online publication date: 1-Oct-2015
  • (2014)UncertainACM SIGARCH Computer Architecture News10.1145/2654822.254195842:1(51-66)Online publication date: 24-Feb-2014
  • (2014)UncertainACM SIGPLAN Notices10.1145/2644865.254195849:4(51-66)Online publication date: 24-Feb-2014
  • (2013)A model-learner pattern for bayesian reasoningACM SIGPLAN Notices10.1145/2480359.242911948:1(403-416)Online publication date: 23-Jan-2013
  • (2013)Denotational Semantics for a Probabilistic Timed Shared-Variable LanguageUnifying Theories of Programming10.1007/978-3-642-35705-3_11(224-247)Online publication date: 2013
  • (2012)Probabilistic operational semantics for the lambda calculusRAIRO - Theoretical Informatics and Applications10.1051/ita/201201246:3(413-450)Online publication date: 22-Jun-2012
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media