Learning acyclic probabilistic circuits using test paths

Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat, and Lev Reyzin. Learning acyclic probabilistic circuits using test paths. Journal of Machine Learning Research, 10(Aug):1881–1911, 2009. An earlier version appeared in Twenty-First International Conference on Learning Theory (COLT), July 2008, pp. 169–179.


We define a model of learning probabilistic acyclic circuits using value injection queries, in which an arbitrary subset of wires is set to fixed values, and the value on the single output wire is observed. We adapt the approach of using test paths from the Circuit Builder algorithm (Angluin et al., STOC 2006) to show that there is a polynomial time algorithm that uses value injection queries to learn Boolean probabilistic circuits of constant fan-in and logarithmic depth. In the process, we discover that test paths fail utterly for circuits over alphabets of size greater than two and establish upper and lower bounds on the attenuation factor of test paths versus general experiments for general and transitively reduced Boolean probabilistic circuits. To overcome the limitations of test paths for non-Boolean alphabets, we introduce function injection queries, which allow the symbols on a wire to be mapped to other symbols rather than just to themselves or constants.


author = {Dana Angluin and James Aspnes and Jiang Chen and David Eisenstat and Lev Reyzin},
title = {Learning acyclic probabilistic circuits using test paths},
year = 2009,
journal = {Journal of Machine Learning Research},
pages = {1881--1911},
volume = 10,
number = {Aug}

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page