Learning Acyclic Probabilistic Circuits Using Test Paths
Dana Angluin, James Aspnes, Chen Jiang, David Eisenstat, Lev Reyzin · 2008
We define a model of learning probabilistic acyclic circuits using value injection queries, in which fixed values are assigned to an arbitrary subset of the wires and the value on the single output wire is observed. We adapt the approach of using test paths from the Circuit Builder algorithm [AACW06] to show that there is a polynomial time algorithm that uses value injection queries to learn acyclic Boolean probabilistic circuits of constant fan-in and log depth. We establish upper and lower bounds on the attenuation factor for general and transitively reduced Boolean probabilistic circuits of test paths versus general experiments. We give evidence that a polynomial time learning algorithm using general value injection experiments may not in general do much better than one using test paths. For probabilistic circuits with alphabets of size three or greater, we show that the test path lemmas from [AACW06, AACR07] fail utterly. To overcome this obstacle, we introduce function injection queries, in which the values on a wire may be mapped to other values rather than just to themselves or constants, and prove a generalized test path lemma for this case.