Lifted Inference: Normalizing Loops by Evaluation

Many loops in probabilistic inference map almost every individual in their domain to the same result. Running such loops symbolically takes time sub-linear in the domain size. Using normalization by evaluation with first-class delimited continuations, the authors lift inference procedures to reap this speed-up without interpretive overhead. To express nested loops, they use multiple control delimiters for meta-circular interpretation. To express loops over a power-set domain, they convert nested loops over a subset to unnested loops.