COMP 150-05 Probabilistic Programming Languages

PLEASE NOTE THAT THE FIRST DAY OF CLASS WILL BE HELD SEPTEMBER 8th

BACKGROUND

In the real world, events are uncertain. To reason about uncertain events, we compute with probability (and also statistics). Over the past 20 years, people who write probabilistic computations have increasingly designed, built, and used special-purpose, probabilistic programming languages. The popularity of this approach can be seen in the long list of such languages used in industry and in research: AutoBayes, Alchemy, Blaise, BLOG, BUGS, Church, Csoft, FACTORIE, Figaro, Fun, HANSEI, HBC, IBAL, Lambda-circle, Probabilistic cc, PFP, and Probabilistic Scheme.

To give you the flavor of the kind of problem these languages are intended to solve, here is a sketch of a probabilistic program:

• There is a 30% chance of rain
• There is a 50% chance of irrigation
• If it rains, there is a 90% chance the grass will be wet
• If irrigation is turned on, there is an 80% chance the grass will be wet
• There is a 10% chance that the grass will be wet from an unknown cause

It is easy to write an interpreter that can run this program forward and answer the question "what is the probability that the grass is wet." This is not interesting. The interesting thing to do is to take this program and ask, "given that I see the grass is wet, what is the probability that it rained?" (Answer: about 47%). The interesting computations involve inference, which reasons backwards from effects to causes:

• Given the words in this message, what is the probability that it is spam?
• Given the bits in this scanned image, what is the probability that it is the cover page of bkolta01's final exam?
• Given a set of sonar echoes, what is the most likely location of my robot?
• Given a sequence of French words, what is the most likely English translation?
• Given a set of tournament results, what is the most likely ranking of the tournament players?

Most of the languages listed above have been designed and implemented by people whose primary expertise is machine learning, not programming languages. The goals of the course are:

• To understand what is going on in these languages, and in particular, to learn how much of the diversity is essential and how much is gratuitous
• To learn what kinds of inference algorithms have been embodied in probabilistic programming languages, and what sorts of problems those algorithms are good at solving
• To learn how to use one of these languages well enough to solve a problem
• To get some idea of the foundational theory on which the languages are based, and in particular, to use the theory as a tool to help identify potential weak spots or limitations in probabilistic languages

The exact balance between theory and implementation will be adjusted to suit the needs and interests of those students who enroll in the course.

The pace of the course will be relatively slow. The course will be designed to help students achieve one or two goals in depth, not to give a breathless survey of the entire field. The course will limit itself to just four languages: Lambda-circle, Fun, BLOG, and Church. These languages are intrinsically interesting and form a diverse set. Most important, there is good source material: relatively accessible papers, and in the case of Church, an online textbook with exercises.

Class will meet twice a week and will proceed in three phases:

1. In the first phase, we will review relevant material from COMP 105 (Programming Languages), and we will have a short "crash course" in probability.
2. In the second phase, we will read and discuss primary sources about probabilistic programming languages, starting with Lambda-circle and Fun.
3. In the third phase, we will support students in the planning and execution of class projects.

Each student is expected to undertake one project for the semester. Projects may be undertaken alone or in teams of any size. Any project related to probabilistic programming language is acceptable. Ideas might include:

• Building a proof-of-concept application around a probabilistic program
• Building a proof-of-concept implementation of a probabilistic language
• Developing a type system or program analysis that can be applied to probabilistic programs
• Developing formal semantics for probabilistic languages---possibilities might include an extension of an existing semantics, a new semantics for an existing language, or a new language design with formal semantics

Grades will be based on class participation and on a contribution to an engaging project. There will be no examinations. To earn credit for class participation, students will be expected to engage in class discussion about readings and problems. We may also occasionally agree to solve small programming problems or probability problems outside of class and to come to class prepared to share our solutions. Such problems will be developed only when both students and instructor agree that such problems are needed in order to help us meet our goals. Such problems will count toward class participation but will not otherwise be graded.