  Obtaining enough labeled data to robustly train complex discriminative models
is a major bottleneck in the machine learning pipeline. A popular solution is
combining multiple sources of weak supervision using generative models. The
structure of these models affects training label quality, but is difficult to
learn without any ground truth labels. We instead rely on these weak
supervision sources having some structure by virtue of being encoded
programmatically. We present Coral, a paradigm that infers generative model
structure by statically analyzing the code for these heuristics, thus reducing
the data required to learn structure significantly. We prove that Coral's
sample complexity scales quasilinearly with the number of heuristics and number
of relations found, improving over the standard sample complexity, which is
exponential in $n$ for identifying $n^{\textrm{th}}$ degree relations.
Experimentally, Coral matches or outperforms traditional structure learning
approaches by up to 3.81 F1 points. Using Coral to model dependencies instead
of assuming independence results in better performance than a fully supervised
model by 3.07 accuracy points when heuristics are used to label radiology data
without ground truth labels.
