hansei-ve-suite

Tue May 20 10:56:40+0200 2025

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License

Table of contents

Variable elimination optimization
test/exponential: pass
test/var-elimination: pass
test/bucket: pass
test/bucket/generic: pass

Tests summary

scheme code

((ran 4) (failed 0))

1. Variable elimination optimization

In this document we report some tests about the following technique,

❝
The optimization of reification followed by (partial) flattening and reflection gives rise to the inference technique known as variable elimination[1]. Its benefit is demonstrated by the following example, computing the XOR of n coin tosses.

Oleg Kiselyov

This trick transform a stochastic function a -> b to a generally faster function:

ocaml code

let variable_elim f arg = reflect (exact_reify (fun () -> f arg))

According to the idea shown in [2], using symbolic manipulation, we show that the probability of XOR of 10 coin tosses to be tail is

512 p^{10} - 2560 p^{9} + 5760 p^{8} - 7680 p^{7} + 6720 p^{6} - 4032 p^{5} + 1680 p^{4} - 480 p^{3} + 90 p^{2} - 10 p + 1

provided that head has probability $p$ to appear in each toss. Moreover, the coefficients are the 10th row of a known sequence [3].

2. `test/exponential`: pass

scheme code

(define (test/exponential _)
  (define result
    (probcc-reify/exact
      (let loop ((p 'p) (n 10))
        (cond ((equal? 1 n) (probcc-coin p))
              (else
               (let1 (r (loop p (sub1 n)))
                     (not (equal? (probcc-coin p) r))))))))
  (⊦= expected result))

scheme code

((eta 1.606) (memory #(6291456 1203288 1048576)) (stdout "") (stderr ""))

3. `test/var-elimination`: pass

scheme code

(define (test/var-elimination _)
  (define (flipxor-model p)
    (letrec ((loop (λ (n)
                       (cond ((equal? 1 n) (probcc-coin p))
                             (else
                              (let1 (r ((probcc-variable-elimination loop) (sub1 n)))
                                    (not (equal? (probcc-coin p) r))))))))
      loop))
  (define res (probcc-reify/exact ((flipxor-model 'p) 10)))
  (⊦= expanded-expected res))

scheme code

((eta 0.059) (memory #(6291456 1200640 1048576)) (stdout "") (stderr ""))

4. `test/bucket`: pass

scheme code

(define (test/bucket _)
  (define (flipxor-model p)
    (letrec ((loop (λ-probcc-bucket
                     (n)
                     (cond ((equal? 1 n) (probcc-coin p))
                           (else
                            (let1 (r (loop (sub1 n)))
                                  (not (equal? (probcc-coin p) r))))))))
      loop))
  (define res (probcc-reify/exact ((flipxor-model 'p) 10)))
  (⊦= expanded-expected res))

scheme code

((eta 0.068) (memory #(6291456 1200720 1048576)) (stdout "") (stderr ""))

5. `test/bucket/generic`: pass

This test generalizes the previous one in the sense that each coin has a different probability for head; in particular, the exact inference for the XOR of 5 such coins yields that tail has probability:

- a (2 b - 1) (2 c - 1) (2 d - 1) (2 e - 1) + b (2 c - 1) (2 d - 1) (2 e - 1) - 4 c d e + 2 c d + 2 c e - c + 2 d e - d - e + 1

provided that coin's heads have probabilities $a$ , $b$ , $c$ , $d$ and $e$ , respectively.

scheme code

(define (test/bucket/generic _)
  (define flipxor-model
    (letrec ((loop (λ-probcc-bucket
                     (n)
                     (cond ((null? (cdr n)) (probcc-coin (car n)))
                           (else
                            (let1 (r (loop (cdr n)))
                                  (not (equal? (probcc-coin (car n)) r))))))))
      loop))
  (define res (probcc-reify/exact (flipxor-model '(a b c d e))))
  (⊦= '(((V #f)
           (Plus 1
                 (Times -1 c)
                 (Times -1 d)
                 (Times 2 c d)
                 (Times -1 e)
                 (Times 2 c e)
                 (Times 2 d e)
                 (Times -4 c d e)
                 (Times b
                        (Plus -1 (Times 2 c))
                        (Plus -1 (Times 2 d))
                        (Plus -1 (Times 2 e)))
                 (Times -1
                        a
                        (Plus -1 (Times 2 b))
                        (Plus -1 (Times 2 c))
                        (Plus -1 (Times 2 d))
                        (Plus -1 (Times 2 e)))))
          ((V #t)
           (Plus c
                 d
                 (Times -2 c d)
                 e
                 (Times -2 c e)
                 (Times -2 d e)
                 (Times 4 c d e)
                 (Times -1
                        b
                        (Plus -1 (Times 2 c))
                        (Plus -1 (Times 2 d))
                        (Plus -1 (Times 2 e)))
                 (Times a
                        (Plus -1 (Times 2 b))
                        (Plus -1 (Times 2 c))
                        (Plus -1 (Times 2 d))
                        (Plus -1 (Times 2 e))))))
        res))

scheme code

((eta 0.04) (memory #(6291456 1337360 1048576)) (stdout "") (stderr ""))

References

[1] Dechter, Rina. Bucket elimination: A unifying framework for probabilistic inference.
[2] Symbolic manipulation in Hansei: a new view on the wet grass model.
[3] A082137: Square array of transforms of binomial coefficients, read by antidiagonals.