Memoization is a fundamental technique in computer science, providing the basis for dynamic programming. This paper explores using memoization to improve the performance of rejection sampling algorithms. It is shown that reusing values produced in previous samples and stored in a cache is beneficial. The paper goes on to explore the idea of recursive memoization, in which values are aggressively reused from the cache even in the process of computing a value to store in the cache. This leads to the values in the cache becoming dependent on each other, and therefore produces a biased sampler. However in practice this seems to be quite beneficial. Furthermore, we show that the error in the cache tends to zero in the long run. We demonstrate the usefulness of memoized sampling in a duplicate bridge simulation, and in experiments with probabilistic grammars.
Subjects: 3.4 Probabilistic Reasoning; 3. Automated Reasoning
Submitted: Apr 13, 2007