PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning the Structure of Generative Models without Labeled Data

Stephen H. Bach, Bryan He, Alexander Ratner, Christopher Ré

arXiv:1703.00854v2cs.LGstat.ML

TL;DR

Curating labeled data is expensive, and automatically selecting a generative model’s dependency structure from weak supervision is difficult because true labels are latent. The paper proposes ℓ1-regularized marginal pseudolikelihood structure learning without labels, achieving sublinear identification requirements and strong empirical improvements over maximum likelihood and existing applications.

  • Problem

    Dependency structure affects inferred labels, but existing approaches rely on user-specified structure and latent true labels make automatic selection challenging.

  • Method

    The method maximizes each supervision source’s ℓ1-regularized marginal pseudolikelihood, marginalizing latent-label uncertainty and selecting dependencies with nonzero weights.

  • Results

    100× faster than maximum likelihood, the method selects 1/4 as many extraneous correlations and improves existing information extraction applications by 1.5 average F1 points.

  • Takeaways & Limitations

    Sublinear unlabeled-data requirements and improved real-world application performance support automatically learning accurate generative-model structures with minimal user intervention.

  • Takeaways & Limitations

    The recovery guarantees assume a feasible parameter set contains the true model.

Abstract

from arXiv · show

Curating labeled training data has become the primary bottleneck in machine learning. Recent frameworks address this bottleneck with generative models to synthesize labels at scale from weak supervision sources. The generative model's dependency structure directly affects the quality of the estimated labels, but selecting a structure automatically without any labeled data is a distinct challenge. We propose a structure estimation method that maximizes the $\ell_1$-regularized marginal pseudolikelihood of the observed data. Our analysis shows that the amount of unlabeled data required to identify the true structure scales sublinearly in the number of possible dependencies for a broad class of models. Simulations show that our method is 100$\times$ faster than a maximum likelihood approach and selects $1/4$ as many extraneous dependencies. We also show that our method provides an average of 1.5 F1 points of improvement over existing, user-developed information extraction applications on real-world data such as PubMed journal abstracts.

1. Introduction

The paper addresses automatic structure learning for generative models trained from weak supervision, where dependency choices affect inferred labels but true labels are unavailable. It proposes an unlabeled-data estimator with theoretical and empirical evidence of efficient, accurate structure selection.

  • Motivation: Labeled data collection is expensive and often requires specialized expertise, motivating generative models that synthesize labels from weak supervision sources.Weak sources include heuristics, knowledge bases, and noisy classifiers.
  • Motivation: Dependency structure affects inferred labels, while assuming conditional independence can misjudge supervision-source accuracy.Users cannot generally specify the correct structure because dependencies vary across datasets.
  • Method: The proposed estimator learns generative-model dependencies without labeled training data by maximizing ℓ1-regularized marginal pseudolikelihood.It selects dependencies whose estimated weights are nonzero and marginalizes uncertainty about latent class labels.
  • Theory: Sublinear unlabeled-data requirements suffice to identify the true structure for a broad class of models.The analysis connects recovery to having enough better-than-random supervision sources to estimate latent labels.
  • Evaluation: 100× faster than maximum likelihood, the method also selects 1/4 as many extraneous correlations at comparable recall.These results come from experiments comparing the proposed method with considering all possible dependencies during parameter learning.
  • Evaluation: The method improves existing user-developed information extraction applications by an average of 1.5 F1 points on real-world data.The evaluated data include PubMed abstracts and hardware specification sheets.

2. Background

The paper frames weak supervision as latent-label generative modeling: labeling functions produce noisy outputs, and their parameters and dependencies are estimated from unlabeled observations. Automatically identifying dependencies is necessary because latent labels make structure learning challenging and exhaustive modeling does not scale.

  • Weak supervision: Data programming represents weak supervision sources as labeling functions that may label data points or abstain.A generative model estimates their accuracies and dependencies, then infers distributions over latent true labels for downstream discriminative training.
  • Latent-label model: Each data point has an unobserved true label, while observed labeling-function outputs provide values in {−1, 0, 1}.The three values correspond to false, abstaining, and true.
  • Latent-label model: The baseline conditionally independent model assumes labeling-function outputs are independent given the true label and includes accuracy dependencies.The model generates the observed outputs from the latent labels.
  • Parameter learning: Parameters are estimated by minimizing the negative log marginal likelihood of the observed labeling-function-output matrix.Stochastic gradient descent provides a straightforward optimization procedure for the likelihood objective.
  • Structure-learning challenge: Automatic structure identification is needed because users must otherwise specify dependencies, while latent labels make structure learning difficult.Exhaustively modeling dependencies requires Gibbs-sampling-based gradient estimation and becomes expensive as possible dependencies grow.

3. Structure Learning without Labels

The proposed structure-learning approach extends the generative model with dependency factors, then uses sparse marginal pseudolikelihood optimization to select relevant dependencies without sampling-based gradient approximations. It optimizes each labeling function in turn and retains sufficiently large parameter estimates.

  • Model structure: The generalized factor graph represents correlations and higher-order dependencies among labeling-function outputs for each data point and latent label.Dependency types and index tuples specify which labeling functions participate in each factor.
  • Learning challenge: Latent labels make joint structure estimation difficult, while the number of possible dependencies grows at least quadratically with the number of labeling functions.Joint parameter learning requires Gibbs sampling to estimate gradients, limiting scalability.
  • Learning objective: The method optimizes each labeling function’s marginal pseudolikelihood conditioned on the others and uses ℓ1 regularization to induce sparsity.The regularized objective is designed to scale across many potentially irrelevant dependencies.
  • Learning objective: Conditioning on the other labeling functions makes the gradient computable in polynomial time without sampling or variational approximations.The gradient is expressed as a difference between sufficient-statistic expectations under two conditioning settings.
  • Structure selection: Dependencies with sufficiently large parameter magnitudes are selected after optimizing each labeling function in turn.The resulting dependency pairs are added to the estimated structure.
  • Optimization procedure: Algorithm 1 uses stochastic gradient descent with closed-form single-data-point gradients and incremental processing of observations.Its implementation uses thresholding and regularization to control sparsity, with fixed step size, epoch count, and truncation frequency in experiments.

4. Analysis

The analysis establishes guarantees for recovering the exact dependency structure from unlabeled data, including a sublinear sample rate for models with only accuracy and pairwise correlation dependencies. It also states the assumptions behind these guarantees and contrasts them with supervised structure-learning rates.

  • Recovery guarantees: O(n log n) unlabeled samples suffice for exact recovery when only accuracy and pairwise correlation dependencies are possible.This is the corollary for a useful restricted model class.
  • Analysis strategy: Unlike supervised analyses, the unsupervised estimation problem is nonconvex, so prior convex-duality arguments do not carry over.The analysis instead reasons about reaching a parameter region where the latent labels can be estimated well enough to approach the true model.
  • Assumptions: The guarantees require a feasible parameter set containing the true model, identifiable dependency contributions, and nonzero parameters bounded away from zero.The dependency condition requires each labeling function's dependencies to improve estimation relative to omitting them.
  • Recovery guarantees: For general dependencies, the recovery rate can scale with the number of possible dependencies because higher-order dependencies may connect the true label to many labeling functions.The general rate is therefore not directly comparable to pairwise Ising-model analyses.
  • Comparison: Compared with supervised guarantees, the unsupervised rate depends on the maximum possible dependencies affecting a variable rather than only the true model's maximum degree.The supervised rate is tighter for very sparse models, although the paper reports that both guaranteed rates are pessimistic.

5. Experiments

Experiments show that structure learning recovers dependencies with favorable sample scaling, runs much faster than maximum likelihood, and improves weak-supervision applications. It also identifies correlations among noisy labeling functions that independent models mishandle.

  • 5.1. Sample Complexity: The method’s practical sample complexity scales logarithmically in the number of labeling functions n.Experiments found aligned recovery curves across different n values.
  • 5.1. Sample Complexity: The method’s practical sample complexity scales linearly in d*, the maximum number of dependencies affecting any labeling function.Increasing d* produced recovery curves consistent with the sample-size prediction.
  • 5.2. Comparison with Maximum Likelihood: Structure learning is 100× faster than maximum likelihood because it avoids sampling variables to estimate the gradient.The comparison used a maximum-likelihood routine based on stochastic gradient descent and Gibbs sampling.
  • 5.2. Comparison with Maximum Likelihood: Even when tuned for better recall, maximum pseudolikelihood returns 1/4 as many extraneous correlations as maximum likelihood.The paper attributes the improved accuracy to computing each data-point gradient exactly rather than estimating it with Gibbs sampling.
  • 5.3. Real-World Applications: Learning correlation structure improves real-world information extraction by an average of 1.5 F1 points over the conditionally independent model.The evaluation covered Disease Tagging, Chemical-Disease, and Device Polarity applications using weak supervision.
  • 5.4. Accelerating Application Development: Structure learning identifies correlated random labeling functions in the Chemical-Disease task, preventing them from outvoting real labeling functions.An independent model instead becomes more confident that the random noise is accurate.

6. Related Work

Prior structure-learning work studied labeled settings, graphical models, and latent-variable Bayesian networks, while weak-supervision research addressed noisy labels and accuracy estimation without gold labels.

  • Structure learning: Structure learning has been extensively studied for generalized linear and graphical models using ℓ1-regularized estimators.The cited work includes lasso-based estimators for linear models and analogous regularized estimators for Gaussian graphical models.
  • Structure learning: Other approaches learn graphical-model structures through grafting and information bottleneck methods for Bayesian networks with latent variables.
  • Weak supervision: Weak-supervision research includes distant supervision, multi-instance learning, hierarchical topic models, and crowdsourcing methods for noisy or unlabeled supervision.

7. Conclusion and Future Directions

The paper concludes that automatically learning generative-model structure improves data-programming results and is substantially faster than maximum likelihood, while leaving sharper guarantees for higher-order dependencies open.

  • Conclusion: Learning generative-model structure enables higher-quality data-programming results.
  • Conclusion: The proposed structure-learning method is 100× faster than a maximum likelihood approach.
  • Future directions: A remaining question is whether the guarantee for higher-order dependencies can be tightened to match the pairwise case.Preliminary experiments indicate similar convergence rates in practice.

A. Proofs

The appendix supplies proofs for Theorem 1 and Corollary 2, organizing the arguments into an outline, theorem proof, corollary proof, and supporting lemmas.

  • Proof organization: The appendix provides proofs for Theorem 1 and Corollary 2 from the main text.
  • Proof organization: Section A.1 outlines the proof and states several lemmas.
  • Proof organization: Sections A.2–A.4 prove Theorem 1, derive Corollary 2 from it, and establish the stated lemmas.

A.1.1. OUTLINE OF THEOREM 1 PROOF

The proof outline establishes strong convexity, controls the gradient at the true parameter, and uses convergence plus truncation to recover the exact sparsity structure with high probability.

  • Convexity and concentration: The negative marginal log-pseudolikelihood is strongly convex under condition (7).The proof derives the gradient and Hessian of each term before establishing strong convexity.
  • Convexity and concentration: Under condition (6), the gradient at the true parameter θ∗ is small with high probability.
  • Structure recovery: Running SGD until convergence and then truncating recovers the exact sparsity structure with high probability.The argument first bounds the distance between the empirical minimum and θ∗, then proves correct sparsity recovery.

A.1.2. LEMMA STATEMENTS

The lemmas establish that marginal pseudolikelihood isolates dependencies involving each labeling function or the true label, is strongly convex on those parameters, and supports exact structure recovery guarantees.

  • Objective structure: The objective is independent of parameters for dependencies outside those incident on λj or y.This reduction isolates the relevant parameter subset for each labeling function.
  • Objective structure: Under condition (7), the objective is strongly convex on parameters in Θj, with strong-convexity parameter c.The same property is stated for the empirical negative log-pseudolikelihood objective.
  • Recovery analysis: The optimization procedure recovers the exact sparsity structure with a bounded failure probability when the stated conditions, sample size, step size, epochs, and truncation requirement hold.The guarantee is obtained by combining gradient control with strong convexity and a union bound over dependencies.
  • Recovery guarantees: An unlabeled dataset of the theorem’s specified size recovers the exact dependency structure with probability at least 1 −δ.The result applies under conditions (6), (7), and (8).
  • Recovery guarantees: When only accuracy and correlation dependencies are possible, the corresponding corollary also guarantees exact recovery with probability at least 1 −δ.In this setting, each labeling function participates in fewer than 2n relevant dependencies.
  • Recovery analysis: The gradient at the true parameter is controlled using bounded, zero-mean independent terms and concentration arguments involving Azuma’s inequality and a union bound.The dependency values lie in [−1, 1], yielding absolute bounds of 2 for the terms used in the concentration analysis.
Loading 1703.00854v2…