This program induces a deterministic arithmetic function from input-output examples.
(define (random-arithmetic-fn)
(if (flip 0.3)
(random-combination (random-arithmetic-fn)
(random-arithmetic-fn))
(if (flip)
(lambda (x) x)
(random-constant-fn))))
(define (random-combination f g)
(define op (uniform-draw (list + -)))
(lambda (x) (op (f x) (g x))))
(define (random-constant-fn)
(define i (sample-integer 10))
(lambda (x) i))
(define (sample)
(rejection-query
(define my-proc (random-arithmetic-fn))
(my-proc 2)
(and (= (my-proc 0) 2)
(= (my-proc 1) 3))))
(sample)
To induce stochastic functions, it can be useful to condition on the evidence – our input-output examples – having high marginal likelihood under the induced function:
(define (random-arithmetic-fn)
(if (flip 0.3)
(random-combination (random-arithmetic-fn)
(random-arithmetic-fn))
(if (flip)
(lambda (x) x)
(random-constant-fn))))
(define (random-combination f g)
(if (flip 0.5)
((lambda (op) (lambda (x) (op (f x) (g x))))
(uniform-draw (list + -)))
(lambda (x) (sample-integer 10))))
(define (random-constant-fn)
(define i (sample-integer 10))
(lambda (x) i))
(define (find-prob x xs ps)
(if (null? xs)
0.0
(if (equal? (first xs) x)
(first ps)
(find-prob x (rest xs) (rest ps)))))
(define (likelihood fn x)
(let ([dist (enumeration-query (define _ 1) (fn) #t)])
(find-prob x (first dist) (second dist))))
(define (sample)
(rejection-query
(define my-proc (random-arithmetic-fn))
(define (my-proc-likelihood x y)
(likelihood (lambda () (my-proc x)) y))
(my-proc 2)
(and (flip (my-proc-likelihood 0 2))
(flip (my-proc-likelihood 1 3)))))
(hist (repeat 100 sample))
This is semantically equivalent to conditioning on input-output examples directly, but can improve convergence rates when MCMC is used in the outer query.
References: