PaperlayerView exact revision on arXiv

Source-linked AI summary

Data Programming: Creating Large Training Sets, Quickly

Alexander Ratner, Christopher De Sa, Sen Wu, Daniel Selsam, Christopher Ré

arXiv:1605.07723v3stat.MLcs.AIcs.LG

TL;DR

Large labeled training sets are expensive or unavailable, motivating a programmatic alternative. The paper introduces data programming, in which noisy labeling functions are combined through a generative model and used for noise-aware discriminative training. It reports improved relation-extraction performance, including a 2.34-point average F1 gain over distant supervision and a 5.98-point gain over an LSTM baseline.

  • Problem

    Large hand-labeled training sets often do not exist and can be prohibitively expensive because they require domain experts.

  • Method

    Users write noisy labeling functions, whose outputs are modeled generatively to estimate supervision quality and support noise-aware discriminative training.

  • Results

    2.34 F1 points was the average improvement over distant supervision, while LSTM-generated features gained 5.98 F1 points over a state-of-the-art LSTM baseline.

  • Takeaways & Limitations

    Data programming can generate large labeled training sets, work with automatic feature generation, and may be easier for domain experts to use.

  • Takeaways & Limitations

    The theoretical guarantees rely on assumptions including correct generative-model specification, conditional sufficiency of labeling-function outputs, and bounded generalization risk.

Abstract

from arXiv · show

Large labeled training sets are the critical building blocks of supervised learning methods and are key enablers of deep learning techniques. For some applications, creating labeled training sets is the most time-consuming and expensive part of applying machine learning. We therefore propose a paradigm for the programmatic creation of training sets called data programming in which users express weak supervision strategies or domain heuristics as labeling functions, which are programs that label subsets of the data, but that are noisy and may conflict. We show that by explicitly representing this training set labeling process as a generative model, we can "denoise" the generated training set, and establish theoretically that we can recover the parameters of these generative models in a handful of settings. We then show how to modify a discriminative loss function to make it noise-aware, and demonstrate our method over a range of discriminative models including logistic regression and LSTMs. Experimentally, on the 2014 TAC-KBP Slot Filling challenge, we show that data programming would have led to a new winning score, and also show that applying data programming to an LSTM model leads to a TAC-KBP score almost 6 F1 points over a state-of-the-art LSTM baseline (and into second place in the competition). Additionally, in initial user studies we observed that data programming may be an easier way for non-experts to create machine learning models when training data is limited or unavailable.

1 Introduction

Data programming addresses the cost and scarcity of expert-labeled training data by letting users specify noisy supervision strategies as labeling functions and modeling their outputs generatively. The framework supports conflicting sources, theoretical scaling comparable to supervised learning, and strong empirical results.

  • Motivation and framework: Data programming lets users express weak supervision as labeling functions that generate large, noisy, and potentially overlapping training labels.Labeling functions can encode knowledge bases, annotator behavior, domain patterns, or dictionaries.
  • Motivation and framework: A generative model combines and denoises labeling-function outputs by learning their accuracies despite conflicts.The method is designed to automate integration of supervision sources with different quality and scope.
  • Theory: Under stated conditions, the method achieves the same asymptotic scaling as supervised learning while using a fixed number of labeling functions.Its scaling depends on the amount of unlabeled data.
  • Usability motivation: Initial usability feedback suggested that writing labeling functions may be easier for users than selecting features for models.The proposed workflow shifts effort toward generating sufficiently large training sets for automatically generated features.
  • Empirical validation: 2.34 F1 points was the average improvement over distant supervision, including a would-be winning 2014 TAC-KBP score.Using LSTM-generated features produced a 5.98-point F1 gain over a state-of-the-art LSTM baseline and would have placed second.

2 Related Work

Data programming extends ideas from distant supervision, crowdsourcing, co-training, boosting, and noisy-label learning by combining multiple noisy supervision sources and explicitly modeling their dependencies. Its setting differs from crowdsourcing by emphasizing a small number of labeling functions covering much of the dataset.

  • Distant supervision: Distant supervision programmatically maps knowledge-base relations to corpus examples, while data programming generalizes this idea to broader supervision sources.Prior extensions model patterns through multiple-instance, discriminative, or generative approaches.
  • Crowdsourcing: Data programming models labeling-function accuracy without ground-truth labels and supports dependencies that are unnatural for human-only crowdsourcing.Its model captures the independent crowdsourcing setting while allowing user-supplied relationships between labelers.
  • Crowdsourcing: Unlike crowdsourcing’s many labelers labeling small subsets, data programming uses a small set of labeling functions that label large portions of the dataset.This distinguishes the scale and coverage regime of the two approaches.
  • Co-training: Compared with co-training, data programming needs no labeled set, allows more than two views, and explicitly models dependencies between views.Co-training relies on two conditionally independent views.
  • Boosting: Compared with boosting, data programming does not explicitly require labeled data and supports richer dependency structures among heuristic classifiers.Boosting combines weak classifiers in a supervised setting, whereas related variants use unlabeled data and accuracy constraints.
  • Noisy labels: Data programming addresses the more general case of multiple noisy labeling functions that can conflict and depend on one another.This extends standard label-noise settings involving a single noise process or classifier.

3 The Data Programming Paradigm

Data programming replaces example-by-example labeling with domain heuristics encoded as labeling functions, then learns a generative model of their noisy outputs and trains a noise-aware discriminative model. The framework supports independent and dependent labeling functions, with theoretical guarantees under explicit assumptions.

  • Problem setting: Data programming targets settings lacking affordable expert labels, sufficiently specific knowledge bases, or stable application specifications.These constraints motivate a simple, scalable, and adaptable supervision approach.
  • Labeling functions: Users provide heuristic labeling functions λ_i: X 7→ {−1, 0, 1}, which label subsets of examples and abstain elsewhere.A vector λ collects the outputs of m labeling functions.
  • Labeling functions: Labeling functions may combine structured knowledge bases, heuristics, or hybrids, with differing coverage and accuracy.The example uses a high-accuracy knowledge-base rule, a broader lower-accuracy heuristic, and a hybrid function.
  • Independent model: The independent model assigns each labeling function coverage and accuracy parameters and estimates them by maximum likelihood from unlabeled data.The observed labeling-function outputs are modeled as generated from latent class labels.
  • Noise-aware training: A noise-aware empirical loss then trains the discriminative model using the learned generative parameters.For linear models, this produces a logistic-regression optimization problem solved with stochastic gradient descent.
  • Theory: The guarantees require correct generative-model specification, conditional sufficiency of labeling-function outputs, and bounded generalization risk.The theorem is stated under these assumptions and for m ≥ 2000 in its simplified form.
  • Theory: The theorem establishes bounds on expected parameter error and generalization risk, with the full result giving m = O(1) labeling functions and |S| = ˜O(ϵ^-2) examples.This matches the asymptotic scaling of methods using labeled data.

4 Handling Dependencies

The paper extends data programming to model dependencies among labeling functions, using dependency graphs and factor graphs to improve denoising while preserving favorable statistical efficiency.

  • Dependency representation: Dependency modeling can improve accuracy when labeling functions develop clear dependencies during system construction.Users specify this dependency knowledge through the dependency graph.
  • Dependency representation: Dependency graphs encode four common relationships among labeling functions: similar, fixing, reinforcing, and exclusive.These relationships describe agreement, error correction, reinforcement, and mutual exclusion patterns.
  • Dependency representation: Dependent labeling functions are modeled with a factor graph whose factors combine base label relationships with dependency-specific constraints.The dependency graph supplies additional factors beyond those in the independent model.
  • Learning with dependencies: Stochastic gradient descent with Gibbs sampling learns the generative parameters and the noise-aware discriminative model in the dependent setting.The method provides accuracy bounds under conditions analogous to those used for independent labeling functions.
  • Statistical guarantees: |S| = ˜O(ϵ^-2) unlabeled examples suffice to achieve error O(ϵ), matching the asymptotic scaling of supervised learning methods.The richer dependency structures incur a computational penalty but do not reduce statistical efficiency.

5 Experiments

Experiments evaluate data programming across relation extraction tasks, automatic feature generation, and user productivity. The results report consistent gains over ordered if-then-return supervision and improvements with LSTM-generated features.

  • Experimental goals: The evaluation tests data programming across three real-world relation extraction applications, LSTM-based automatic feature generation, and domain-expert usability.These experiments target effectiveness, compatibility with learned features, and productivity for non-experts.
  • Relation extraction: Data programming improves F1 by an average of 2.34 points over the if-then-return approach across applications.The evaluation uses blind hand-labeled sets, and the reported result includes a would-be winning 2014 TAC-KBP score.
  • Relation extraction: Performance gains persist across applications with different labeling-function sets, including settings with small m and relatively limited conflict and overlap.Coverage, overlap, and conflict summarize the amount and disagreement of generated supervision.
  • Dependency effects: 2.3 F1 points were gained on disease mention extraction when developers supplied dependencies within the data programming framework.The task was written from scratch using data programming.
  • Automatically generated features: A 3.12-point F1 improvement over the if-then-return baseline and a 5.98-point improvement over a state-of-the-art LSTM were reported on 2014 TAC-KBP News.The same experiment also reported a 9.79-point precision boost over the if-then-return approach.
  • Usability study: The usability study involved bioinformatics researchers building a disease-tagging system during a hackathon without access to a labeled training set.The study examined whether iterating on labeling functions was more productive than iterating on features for users without ML expertise.

6 Conclusion and Future Work

The paper introduces data programming for generating large labeled training sets and demonstrates its use with automatic feature generation and domain-expert workflows.

  • Conclusion: Data programming is presented as a new approach to generating large labeled training sets.The paper also identifies imaging and structured prediction as future application areas.
  • Conclusion: The authors report high-quality results with automatic feature generation and anecdotal evidence that the framework may be easier for domain experts to use.They propose exploring the approach on tasks limited by a lack of high-quality supervised datasets.

A General Theoretical Results

The paper formalizes data programming as a generative label model and derives a procedure that estimates its parameters before training a noise-aware discriminative model. Under stated distributional and feasibility assumptions, the analysis bounds parameter error and generalization risk.

  • Model and goals: Data programming models labeling-function values and class labels with a maximum-entropy distribution parameterized by θ.The parameter space Θ is assumed feasible, and the paper seeks estimates θ̂ and ŵ for the label model and regularized logistic model.
  • Model and goals: The analysis assumes labels are conditionally independent of features given labeling-function outputs, the relationship between outputs and labels belongs to the model family, and features are bounded.These assumptions connect the label model to the downstream prediction problem.
  • Downstream learning: The downstream stage minimizes a noise-aware empirical loss using the recovered label-model parameters rather than treating generated labels as clean.In practice, the optimization algorithm may be stochastic gradient descent.
  • Estimation procedure: Algorithm 1 uses stochastic updates based on samples from the label model, projects parameters onto Θ, and then computes the downstream parameter ŵ.The algorithm requires a dataset, step size, and initial parameter, and uses fresh sampled label-model quantities in its update.
  • Guarantees: Theorem A.1 bounds expected parameter error and expected risk when the data-programming specification satisfies the stated conditions and the dataset is sufficiently large.The appendix theorem is identified as equivalent in conclusions and assumptions to Theorem 2 in the main body, while allowing a more general sufficient-statistics function.

B Theoretical Results for Independent Model

For conditionally independent labeling functions, the paper specializes its general theory to explicit sufficient statistics and derives bounds under feasible-parameter and sample-size conditions. In the stated regime, the appendix establishes concrete parameter-error and risk guarantees.

  • Independent model: The independent model uses labeling-function values Λ∈{−1,0,1}^m and class labels Y∈{−1,1}, with sufficient statistics involving Λ_iY and Λ_i^2.This gives the independent label model a concrete parameterization for the theoretical analysis.
  • Assumptions: The independent-model corollary requires a feasible specification, conditions (13)–(16), a specified step size, and a dataset meeting the stated size requirement.The result is presented as a corollary to the general theorem.
  • Assumptions: β_i≥0.3 and 0.8≤α_i≤0.9, equivalently 0.6≤γ_i≤0.8, define the parameter regime used for the stated corollary.These inequalities are the body-of-paper conditions referenced in the appendix discussion.
  • Guarantees: m=2000 is sufficient for the corollary to hold with the stated bound.The passage specifies the number of labeling functions but the displayed bound itself is not included in the supplied text.
  • Guarantees: The independent-model proof reduces Theorem 1 to Corollary B.1.The appendix states that proving the corollary suffices to establish the theorem from the paper body.

C Proof of Theorem A.1

The proof of Theorem A.1 combines curvature, stochastic-gradient, and noise-aware-loss arguments. These components yield bounds on label-model parameter estimation and downstream expected risk under the theorem’s assumptions.

  • Proof structure: The proof represents the label model as a maximum-entropy distribution over labeling-function values λ and class labels y.The sufficient-statistics representation uses h(λ,y) with bounded coordinates.
  • Curvature: Strong concavity of the maximum-likelihood objective J follows from assumptions on the feasible parameter set and an unbiased estimator based on full samples.The argument uses Fisher information and establishes curvature parameter c over Θ.
  • Optimization: Stochastic gradient descent on J yields a bound on expected parameter-estimation error when updates use unbiased samples, an appropriate step size, and enough iterations.The corresponding lemma assumes J is strongly concave with parameter c.
  • Noise-aware learning: The downstream analysis replaces the ideal expected loss with a noise-aware loss based on the estimated label-model parameter θ̂.The empirical noise-aware objective is minimized in practice and is equal to the target loss only in expectation.
  • Conclusion: Theorem A.1 combines the parameter-error and risk analyses to bound both expected parameter error and expected risk.Its proof invokes the stochastic-gradient lemma for estimation and the downstream loss lemma for risk.

D Proofs of Lemmas

The lemma proofs establish the mathematical ingredients behind data programming’s guarantees: curvature of the label-model objective, convergence of stochastic optimization, and transfer from estimated noise parameters to downstream risk.

  • Label-model geometry: For maximum-entropy label models, the Hessian of the objective is related to covariance of sufficient statistics and Fisher information.The proof derives the second derivative through covariance identities.
  • Label-model geometry: An unbiased full-sample estimator and a covariance bound imply that J is strongly concave over the feasible set Θ.The proof applies the Cramér–Rao bound and scales Fisher information by the number of independent samples.
  • Optimization: Under strong concavity, stochastic gradient descent contracts toward θ* up to an error controlled by the update schedule and sampling noise.The proof tracks expected distance to the optimum through successive iterates.
  • Risk transfer: The downstream risk proof uses conditional independence of y and features given labeling functions to relate the target loss to the noise-aware loss.The argument then bounds the difference between these losses and propagates label-model estimation error to expected risk.
  • Risk transfer: The final risk bound follows by combining the loss comparison with optimization and parameter-estimation bounds.The proof uses expectation identities, the mean value theorem, norm bounds, and the empirical optimization guarantee.

E Proofs of Results for the Independent Model

The independent-model appendix derives moment and covariance properties for sufficient statistics, then applies concentration and feasibility results to bound parameter error and expected risk under stated conditions.

  • The independent model uses Λ ∈ {−1, 0, 1}^m and Y ∈ {−1, 1}, with sufficient statistics including Λ_iY and Λ_i^2.
  • Lemmas establish expected values, covariances, conditional covariances, and feasibility properties for the sufficient statistics.
  • The proof combines covariance bounds with Lemma E.5 and concentration arguments to verify the assumptions needed for the main theorem.
  • Under the corollary’s conditions on the independent specification, labeling-function count, step size, and dataset size, expected parameter error and expected risk are bounded.
  • The remaining assumptions are inherited directly from the corollary, allowing Theorem A.1 to yield the stated result.

G.2 Synthetic Experiments

The synthetic experiments compare data programming with an optimally ordered if-then-return oracle and majority vote, while also testing whether modeling labeling-function dependencies matters.

  • Synthetic experiments use labeling functions with constant coverage β = 0.1 and accuracies drawn from Uniform(µα − 0.25, µα + 0.25), with µα = 0.75.
  • The experiments use 1000 normally drawn features with mean correlation 0.5 to the true label class.
  • DP-Pipelined is compared with an optimally ordered if-then-return oracle and simple majority vote.
  • A dependency experiment adds dependent labeling functions to 50 independent functions and compares dependency-aware modeling with an independent model.
Loading 1605.07723v3…