2 Probabilistic Programming
| #lang roulette/example/disrupt/safe | package: roulette |
Given the omnipresent nature of probability and its centrality to science, programming, and countless other endeavors, it is only natural that it has found its way into our programming languages. Such programming languages are called probabilistic programming language: these are programming languages that denote probability distributions. Our main goal in this session is to learn the foundations of using the Roulette probabilistic programming language to solve answer questions about probabilistic scenarios.
Roulette is still under active development and it is likely that during the course of the semester we will ship some updates. Please give us feedback!
2.1 Basic Programming in Roulette
Once you’ve installed Roulette, you can start using the language by putting #lang roulette/example/disrupt/safe at the top of your Racket file. At its core, Roulette is an extension to Racket that adds the ability to program with first-class probability distributions. This means that probability distributions are themselves values that can be programmed with and manipulated just like any other data type such as numbers or functions.
This is best illustrated by example. Here is your first Roulette program:
> (flip 1/3)
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│#t │1/3 │
│#f │2/3 │
└─────┴───────────┘
The (flip 1/3) function creates a probability distribution on the values #t and #f: it says that #t has probability 1/3, and #f has probability 2/3. The probability distribution is rendered as a probability table similar to what we saw in the first session.
With only this primitive we can already write some very interesting probabilistic programs because Roulette has all the features of Racket that we covered in the first session (and more!). For example, we can branch on the value of a flip:
> (if (flip 1/5) 10 20)
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│20 │4/5 │
│10 │1/5 │
└─────┴───────────┘
Note that, in the above example, we can branch on the value of a random Boolean just like how we branch on a normal non-random Boolean. This lets us put probability distributions on numbers.
Now, we can compute with probability distributions on numbers just like how we do with normal numbers:
> (define my-num-dist (if (flip 1/5) 10 20)) > (+ my-num-dist 5)
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│25 │4/5 │
│15 │1/5 │
└─────┴───────────┘
Now we can program with probabilities: probability distributions suffuse the entire language and we can program with them flexibly. For example, here we can write some simple programs that manipulate probability distributions on lists:
> (define my-list (if (flip 1/3) (list 1 2) (list 3 4 5))) > my-list
┌────────┬───────────┐
│Value │Probability│
├────────┼───────────┤
│'(1 2) │1/3 │
│'(3 4 5)│2/3 │
└────────┴───────────┘
> (length my-list)
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│2 │1/3 │
│3 │2/3 │
└─────┴───────────┘
We see in the above example that we can easily place a probability distribution on lists, and then ask for the length.
It can get a bit tedious to build probability distributions over sets of values, so Roulette provides a helper function to quickly accomplish this:
> (make-categorical '((a . 1/3) (b . 1/3) (c . 1/3)))
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│'c │1/3 │
│'b │1/3 │
│'a │1/3 │
└─────┴───────────┘
2.1.1 Running a Roulette program by hand
Probabilistic programs can be quite tricky to understand, so it will be important for us to develop tools for reasoning about them. Roulette programs take a sequence of steps of simplification they finishing running under all possible random choices. Each time a random choice is encountered, the computation branches into the different possible random outcomes.
Concretely, we can run the simple program (flip 1/3) by hand as follows:
(flip 1/3) --> {(1/3, #t), (2/3, #f)}
We read the arrow --> as "steps to". Each step simplifies the program a little bit by evaluating one more part of it. We read the above diagram as saying "the program (flip 1/3) steps to the set of pairs (1/3, #t) and (2/3, #f)."
Let’s run this program by hand:
> (or (flip 1/3) (flip 1/8))
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│#t │5/12 │
│#f │7/12 │
└─────┴───────────┘
This one is a bit tricker because there are multiple steps of simplification. We will evaluate the first argument to the or first:
(or (flip 1/3) (flip 1/8)) |
--> (or {(1/3, #t), (2/3, #f)} (flip 1/8)) |
Now we can keep taking steps of simplification by simplifying the righthand side:
(or {(1/3, #t), (2/3, #f)} (flip 1/8)) |
--> (or {(1/3, #t), (2/3, #f)}, {(1/8, #t), (7/8, #f)}) |
Now we are ready to evaluate the or. We can do this by broadcasting the or function over the values, as follows:
(or {(1/3, #t), (2/3, #f)}, {(1/8, #t), (7/8, #f)}) |
--> {(1/3*1/8, (or #t #t)), (1/3*7/8, (or #t #f)) |
(2/3*1/8, (or #t #t)), (2/3*7/8, (or #t #f))} |
= {(5/12, #t), (7/12, #f)} |
We will make this process of running probabilistic programs by hand more formal later, but for now, it will be a useful tool for us for understanding what probabilistic programs are meant to do.
2.1.2 Selecting a uniformly random list element
Let’s build some more complicated probability distributions out of this simpler one: let’s aim to construct a uniformly random distribution on elements of a list. We will call this function (list-uniform l). For example, we want the following behavior:
> (list-uniform (list 'a 'b 'c)) ┌─────┬───────────┐ │Value│Probability│ ├─────┼───────────┤ │'a │1/3 │ │'b │1/3 │ │'c │1/3 │ └─────┴───────────┘
We can build this function by iterating through each element of the list one at a time and flipping a coin to decide whether or not to output that element. Let’s see it in action:
; list-uniform : list 'a -> 'a ; Outputs a uniform random distribution on elements of a list. ; Precondition: list is not empty. Raises an error if this is violated.
> (define (list-uniform l) (if (empty? l) '() (if (flip (/ 1 (length l))) (first l) (list-uniform (rest l))))) > (list-uniform (list 'a 'b 'c))
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│'c │1/3 │
│'b │1/3 │
│'a │1/3 │
└─────┴───────────┘
That worked like we expected! But, you might have a bit of trouble understanding why it works just by staring at it. So, to get better intuition, run it by hand.
2.2 Population dynamics
Probabilistic programming languages are a powerful problem-solving tool: we can translate realistic scenarios into probabilistic programs and use them to solve our problems. To see an example, let’s go back to the genetic heritability example from the prior lecture.
Recall that there are 3 possible genotypes for whether a pea plant was green or yellow:
BB, which expresses as a green phenotype;
Bb, which expresses as a green phenotype;
bb, which is a yellow phenotype.
We can write a simple program that tells us the phenotype for a genotype:
> (define (phenotype g) (cond [(or (equal? g 'BB) (equal? g 'Bb)) "green"] [(equal? g 'bb) "yellow"]))
Then, we can define the distribution on inherited genotypes for two parents as a probabilistic program:
> (define (child-genotype p1 p2) (cond [(and (equal? p1 'BB) (equal? p2 'BB)) 'BB] [(and (equal? p1 'BB) (equal? p2 'Bb)) (list-uniform (list 'BB 'BB 'Bb 'Bb))] [(and (equal? p1 'BB) (equal? p2 'bb)) 'Bb] [(and (equal? p1 'Bb) (equal? p2 'BB)) (list-uniform (list 'BB 'BB 'Bb 'Bb))] [(and (equal? p1 'Bb) (equal? p2 'Bb)) (list-uniform (list 'BB 'Bb 'Bb 'bb))] [(and (equal? p1 'Bb) (equal? p2 'bb)) (list-uniform (list 'Bb 'Bb 'bb 'bb))] [(and (equal? p1 'bb) (equal? p2 'Bb)) (list-uniform (list 'Bb 'Bb 'bb 'bb))] [(and (equal? p1 'bb) (equal? p2 'BB)) 'Bb] [(and (equal? p1 'bb) (equal? p2 'bb)) 'bb])) > (child-genotype (if (flip 1/2) 'Bb 'bb) 'BB)
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│'BB │1/4 │
│'Bb │3/4 │
└─────┴───────────┘
Now, we can model a fun scenario. Suppose we have have two populations of peas with the following genotypes:
> (define population1 (list 'BB 'Bb 'BB 'bb)) > (define population2 (list 'bb 'Bb 'Bb))
Now suppose we want to find out: if I choose 1 random pea plant from population1 to breed with one random pea plant from population2, what is the probability that I get a green plant? We can answer that with the following program:
> (define plant1 (list-uniform population1)) > (define plant2 (list-uniform population2)) > (define child (child-genotype plant1 plant2)) > child
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│'BB │5/24 │
│'Bb │13/24 │
│'bb │1/4 │
└─────┴───────────┘
> (phenotype child)
┌──────┬───────────┐
│Value │Probability│
├──────┼───────────┤
│green │3/4 │
│yellow│1/4 │
└──────┴───────────┘
This has gotten pretty tricky! Hopefully, now you can see how you can build fairly interesting probability distributions quickly by chaining together smaller and simpler ones.
2.3 Cryptography and the one-time pad
Cryptography relies heavily on randomness to ensure secrecy and integrity of messages. In this example, we’ll see how to encode a simple but important cryptographic protocol in Roulette: the one-time pad.
A one-time pad is a classic example of a simple cryptographic encryption scheme. The core idea of a one-time pad is quite simple: The cryptographic key is a uniformly-random chosen list of bits. We can define this as:
> (define key (list (flip 1/2) (flip 1/2) (flip 1/2)))
Then, the user chooses a message they want to encrypt with this secret key. This is called the cleartext. The message also has to be bits: here we choose (list #t #t #f) as our message.
> (define cleartext (list #t #t #f))
Now the interesting part: to encrypt this cleartext using our uniformly random key, we exclusive-or each bit of the cyphertext with one bit of the key. To see why this works, observe that if you exclusive-or a random coin flip with any Boolean, the result is random noise!
> (xor #t (flip 1/2))
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│#t │1/2 │
│#f │1/2 │
└─────┴───────────┘
> (xor #f (flip 1/2))
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│#t │1/2 │
│#f │1/2 │
└─────┴───────────┘
The result of encryption is called the cyphertext. An adversary observing the cyphertext cannot determine what the cleartext was, so this encryption scheme is secure. We can implement the full encryption strategy by simply exclusive-oring each bit of the cleartext with the key:
> (define (enc key cleartext) (if (= (length key) 0) '() (cons (xor (first key) (first cleartext)) (enc (rest key) (rest cleartext))))) > (enc key cleartext)
┌───────────┬───────────┐
│Value │Probability│
├───────────┼───────────┤
│'(#f #t #t)│1/8 │
│'(#t #f #f)│1/8 │
│'(#t #f #t)│1/8 │
│'(#f #f #t)│1/8 │
│'(#f #t #f)│1/8 │
│'(#t #t #f)│1/8 │
│'(#t #t #t)│1/8 │
│'(#f #f #f)│1/8 │
└───────────┴───────────┘
Now of course, encryption is useless without decryption. Thankfully, decryption of a one-time pad is easy: you simply exclusive-or the cyphertext with the key again. For instance:
> (define my-key (flip 1/2)) > (define my-cleartext #t) > (define my-cyphertext (xor my-cleartext my-key)) > (xor my-cyphertext my-key) #t
In other words, encryption is also decryption. So, we can do a full encryption-decryption cycle by calling enc twice:
> (enc (enc key cleartext) key) '(#t #t #f)
2.4 Independent Learning
Complete the following exercises on your own:
2.4.1 Uniform range
Write a function uniform-range low high that takes two integers low and high and outputs a uniform distribution on [low, high). For example:
> (uniform-range 3 6)
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│3 │1/3 │
│4 │1/3 │
│5 │1/3 │
└─────┴───────────┘
> (uniform-range -1 3)
┌─────┬───────────┐
│Value│Probability│
├─────┼───────────┤
│0 │1/4 │
│1 │1/4 │
│2 │1/4 │
│-1 │1/4 │
└─────┴───────────┘
2.4.2 Choose two
Write a function called choose2 l that, given a list l, outputs a pair of two elements of l chosen uniformly at random without replacement. For example,
> (choose2 (list 1 2 3)) ┌──────────┬───────────┐ │Value │Probability│ ├──────────┼───────────┤ │'(1 2) │1/3 │ │'(1 3) │1/3 │ │'(2 3) │1/3 │ └──────────┴───────────┘ > (choose2 (list "a" "b" "c")) ┌───────────┬───────────┐ │Value │Probability│ ├───────────┼───────────┤ │'("a" "b") │1/3 │ │'("a" "c") │1/3 │ │'("b" "c") │1/3 │ └───────────┴───────────┘
You can use the list-ref helper function to look up an element in a list at a particular index.