PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Dependency Structures for Weak Supervision Models

Paroma Varma, Frederic Sala, Ann He, Alexander Ratner, Christopher Ré

arXiv:1903.05844v1stat.MLcs.LG

TL;DR

Learning dependencies among noisy weak-supervision sources is challenging without ground-truth labels. This paper uses robust PCA to learn those dependencies, showing improved sample-complexity rates and better performance than independence-based methods on real-world tasks.

  • Problem

    Weak-supervision sources can have dependencies that are difficult to specify manually, so learning them from source labels without ground truth is a key challenge.

    Source: §1 · p. 1, §2 · p. 2

  • Method

    The method decomposes the observable sources’ inverse covariance matrix with robust PCA to recover a sparse dependency structure and a low-rank component.

    Source: §1 · p. 1

  • Results

    Across relation extraction and image classification tasks, the method outperforms conditional-independence approaches by up to 4.64 F1 points.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Under stated conditions, required unlabeled data can scale sublinearly or logarithmically with the number of sources, and the logarithmic rate matches the optimal supervised rate.

    Source: §1 · p. 2

    In the general latent-variable setting, some dependency graphs cannot be distinguished from observed sources alone, even with arbitrarily many samples.

    Source: §5 · p. 9

Abstract

from arXiv · show

Labeling training data is a key bottleneck in the modern machine learning pipeline. Recent weak supervision approaches combine labels from multiple noisy sources by estimating their accuracies without access to ground truth labels; however, estimating the dependencies among these sources is a critical challenge. We focus on a robust PCA-based algorithm for learning these dependency structures, establish improved theoretical recovery rates, and outperform existing methods on various real-world tasks. Under certain conditions, we show that the amount of unlabeled data needed can scale sublinearly or even logarithmically with the number of sources $m$, improving over previous efforts that ignore the sparsity pattern in the dependency structure and scale linearly in $m$. We provide an information-theoretic lower bound on the minimum sample complexity of the weak supervision setting. Our method outperforms weak supervision approaches that assume conditionally-independent sources by up to 4.64 F1 points and previous structure learning approaches by up to 4.41 F1 points on real-world relation extraction and image classification tasks.

1 Introduction

The introduction presents learning dependencies among noisy labeling sources as a challenge for weak supervision and proposes a sparse-structure-aware robust PCA method. It reports improved sample-complexity rates and better real-world task performance than independence-based and prior structure-learning approaches.

1 Introduction

  • Generative models combine noisy labels from sources such as heuristics and knowledge bases, infer probabilistic labels, and use them to train a downstream discriminative model.Hand labeling large datasets is a bottleneck, especially when domain expertise is required.Source: §1 · p. 1
  • Correlated sources make accuracy estimation difficult, while manually specifying dependencies is prohibitive and statistical learning usually requires ground-truth labels.Prior weak-supervision structure learning requires Ω(m log m) samples and does not exploit structural sparsity.Source: §1 · p. 1
  • The method decomposes the observable sources’ inverse covariance into a sparse structure component and a low-rank component caused by marginalizing over the latent true label.This robust PCA approach improves on prior methods’ Ω(m) sample requirement under common weak supervision conditions.Source: §1 · p. 1
  • Figure 1 depicts source-dependency graphs, with an edge from every λi to latent Y; m counts sources and dmax is a source’s maximum degree.The figure shows example structures the method aims to learn.Source: Figure 1 · p. 2
  • Under certain conditions, sample complexity is sublinear in m, and a dominant correlated-source cluster yields Ω(d^2 log m), matching the optimal supervised rate.The effective rank can be unboundedly smaller than the covariance matrix’s true rank.Source: §1 · pp. 1–2
  • Up to 4.64 F1 points over conditionally independent sources and 4.41 F1 points over existing structure learning approaches are reported across real-world tasks.The tasks span relation extraction and image classification.Source: §1 · p. 2

2 Background

The background describes weak supervision as combining noisy source labels without requiring ground-truth labels, then motivates learning dependencies because sources can be correlated. It situates the paper’s matrix-wise approach among prior structure-learning methods and states assumptions used in the setup.

2 Background

  • Generative models combine noisy weak-supervision labels to infer probabilistic training labels, which can train a downstream discriminative model.The paper focuses on settings that require no labeled data.Source: §2 · pp. 2–3
  • Dependencies arise when sources share inputs, knowledge bases, or ontology subtrees, making manual specification difficult at scale and motivating learning from source labels without ground truth.The examples include distant-supervision sources using similar information from one knowledge base.Source: §2 · p. 2
  • Prior structure-learning work includes node-wise regression, inverse-covariance methods, and robust-PCA-like latent-variable methods; this paper targets the weak-supervision setting.The background identifies Ravikumar et al., Chandrasekaran et al., Meng et al., and Wu et al. among these approaches.Source: §2 · p. 2
  • Bach et al. [2] use ℓ1-regularized node-wise pseudo-likelihood with Ω(m log m) samples, whereas this paper uses a matrix-wise method that scales with graph sparsity d.The cited sample complexity does not depend on maximum dependency degree d.Source: §2 · p. 2
  • The model is a Markov random field over noisy sources and latent Y, with an edge for source pairs that are conditionally dependent given Y and the other sources.For simplicity, the paper assumes binary X and Y, while stating that results extend easily.Source: §2 · p. 3
  • The setup assumes a singleton separator set, grouping sources into connected clusters; after learning dependencies, prior methods can estimate source accuracies and dependency parameters.The assumption is motivated by sources sharing data resources, heuristics, or primitives.Source: §2 · p. 3

3 Learning Structures in the Weak Supervision Regime

The paper frames weak-supervision structure learning as recovering a sparse dependency graph from noisy source labels despite an unobserved true label. It adapts robust PCA to separate this graph structure from the latent-label contribution, then specifies identifiability and implementation steps.

3 Learning Structures in the Weak Supervision Regime

  • The paper’s goal is to recover graph G from noisy source labels without observing latent true label Y.The section then develops the objective, robust PCA background, and adaptation to weak supervision.Source: §3 · p. 3

3.1 Structure Learning Objective

  • O is a permutation of a block-diagonal matrix with s blocks, one for each source cluster, each no larger than (d + 1) × (d + 1), where d is the maximum dependency degree.Source: §3.1 · p. 4
  • Because Y is hidden, the observed inverse covariance combines a sparse graph-structured component KO with rank-one zzT from marginalizing over Y, motivating robust PCA.The inverse covariance of observed labels is estimated from their empirical covariance.Source: §3.1 · p. 4

3.2 Robust PCA

  • Robust PCA separates a matrix into low-rank and sparse parts, but recovery requires identifiability conditions preventing either component from also fitting the other’s structure.The paper describes these conditions through transversality and quantities governing alignment with coordinate axes and spread of the low-rank component.Source: §3.2 · p. 4

3.3 Adapting Robust PCA for Weak Supervision

  • The weak-supervision adaptation treats KO as sparse and zzT as rank one; its decomposition is unique when the stated identifiability condition holds.The condition is expressed using extreme source accuracies and source correlations, with µ(Ω(KO))ξ(T(zzT)) < 1.Source: §3.3 · p. 5
  • The implementation solves the robust PCA objective, thresholds small entries of the recovered sparse matrix, and passes its remaining nonzero entries as dependencies to the generative model.The method is implemented with standard convex solvers.Source: §3.3 · p. 5

4 Analysis

The analysis uses effective-rank conditions to sharpen recovery guarantees for weak-supervision structure learning and derives an information-theoretic lower bound on its additional sample cost versus supervised learning.

4.1 Controlling the Covariance Estimation Error

  • The analysis requires control of spectral-norm covariance estimation error and uses effective rank, which can be much smaller than true rank, for sharper concentration inequalities.The latent-setting objective includes a nuclear-norm regularizer, making a spectral-norm error bound necessary.Source: §4 · p. 6, §4.1 · p. 6

4 Analysis

  • The information-theoretic lower bound characterizes additional sample cost versus supervised learning, which can be unbounded in general latent settings but is reasonably small for weak supervision.Source: §4 · p. 6

4.2 Conditions on the Effective Rank & Main Results

  • Under SBD, n = Ω(d^2 m^τ) samples suffice; under SSB, n = Ω(d^2(1 + τ) log m) suffice, each with recovery probability at least 1 − m^-τ.The SSB rate matches the supervised optimal rate d^2 log m.Source: §4.2 · pp. 6–7
  • SBD corresponds to mild eigenvalue decay across source blocks with a limit on cluster count, whereas SSB corresponds to a dominant strong voting block.Under SBD, the number of clusters is s = O(m^(τ/2)/log m) and re(ΣO) = O(m^τ/log m).Source: §4.2 · pp. 6–7

5 Information-Theoretic Lower Bound

The section derives information-theoretic sample-complexity lower bounds by comparing graph collections in supervised and latent-variable settings. It shows why the fully general latent case can be unidentifiable and focuses its bound on weak supervision, where the added sample cost is limited in a stated regime.

5 Information-Theoretic Lower Bound

  • In the general latent-variable case, two graphs can be indistinguishable from observed sources even with any number of samples, so structure recovery is not always possible.The example differs only in whether the latent label connects to λ1 or λ2, while only those sources are observed.Source: §5 · p. 9, Figure 2 · p. 9
  • The analysis therefore restricts attention to weak supervision, where the latent label Y is connected to every source, and quantifies the lower-bound cost of that setting.The section characterizes the additional sample requirement relative to the supervised case.Source: §5 · pp. 8–9
  • The lower-bound strategy compares graph collections using Fano-style arguments: closer graphs require more samples to distinguish, and the latent setting is compared with the supervised setting.The construction adapts a graph collection used for the supervised lower bound to the latent-variable weak-supervision case.Source: §5 · p. 9
  • As θ approaches zero, the relative weak-supervision sample cost is bounded by 2, corresponding to no more than twice as many samples as in the unsupervised case.The passage identifies this as the regime of interest as d and m grow, when θ must approach zero to avoid exponential sample complexity.Source: §5 · pp. 9–10

6 Experimental Results

Across real-world tasks, modeling learned dependencies improves discriminative-model performance over independence and prior structure learning; synthetic simulations also favor the proposed method under both studied conditions. The experiments evaluate labels generated by weak-supervision models and include tasks from image classification to relation extraction.

6 Experimental Results

  • The evaluation compares majority vote, an independence-assuming generative model, and a generative model using learned dependencies, followed by a discriminative model trained on their labels.The reported metric is test-set performance of the same discriminative model across baselines and the proposed approach.Source: §6 · p. 10, §6.1 · p. 10

6.1 Real-World Tasks

  • Recovering dependencies among weak supervision sources improves performance by up to 4.64 F1 points over assuming independence and up to 4.41 F1 points over dependencies learned by an existing structure-learning method.Source: §6 · p. 10
  • The real-world benchmarks span Bone Tumor X-ray classification, CDR relation detection, IMDb plot classification, and MS-COCO person classification, using varied weak-supervision sources and task-specific models.Sources include heuristics, decision trees, distant supervision, and regular expressions; the task models include logistic regression, LSTMs, and GoogLeNet.Source: §6.1 · pp. 10–11
  • The real-world tasks show a 3.80-point average F1 improvement over independence, with task-specific gains over Bach et al. [2] on MS-COCO, Bone Tumor, and IMDb.The reported gains over Bach et al. [2] are 4.41 F1 points on MS-COCO, 4.13 on Bone Tumor, and 2.48 on IMDb.Source: §6.1 · p. 11

6.2 Simulations

  • In simulations with 200 sources, the method outperforms Bach et al. [2] under both SSB and SBD; under SSB it recovers structure from roughly log m to roughly m samples.The Figure 3 caption marks n < m as the shaded region and reports a significant advantage under SSB, while neither method works well there without SSB.Source: §6.2 · p. 11, Figure 3 · p. 11

7 Conclusion

The conclusion presents robust PCA as a way to learn dependencies among weak-supervision sources and improve theoretical recovery rates. It reports sublinear or logarithmic data requirements under conditions and empirical gains over independence-based and prior structure-learning methods.

7 Conclusion

  • The method improves over standard linear sample complexity, requiring sublinear or logarithmic amounts of unlabeled data in the number of sources under certain conditions.Under certain conditions, it matches the information-theoretic optimal lower bound in the supervised case.Source: §7 · p. 11
  • Empirically, the method outperforms traditional structure-learning approaches by up to 4.41 F1 points and methods that assume independence by up to 4.64 F1 points.Source: §7 · p. 12

A Glossary & Extended Related Work

The related-work discussion contrasts matrix-wise and node-wise structure learning and situates the paper among weak-supervision and latent-variable methods. It highlights the paper’s discrete weak-supervision setting and its use of sparsity information to characterize effective rank.

Extended Related Work

  • The discussion distinguishes node-wise neighborhood recovery from matrix-wise methods that use inverse covariance, and the appendix includes a glossary of paper notation.The cited examples include Bach et al. [2] for node-wise methods and graphical Lasso for matrix-wise methods.Source: A Glossary & Extended Related Work · p. 14, Table 3 · p. 15
  • Prior robust-PCA approaches include Gaussian latent-variable structure learning and later loss-function or assumption changes; the cited works lead to an Ω(m) rate.Compared with Meng et al., this work treats discrete model selection in weak supervision and characterizes effective rank using sparsity parameters, rather than leaving it as a measured parameter.Source: A Glossary & Extended Related Work · pp. 15–16
  • Unlike Bach et al. [2], whose maximum degree includes latent-variable links and yields an Ω(m log m) rate, this work measures degree over observed sources to obtain potentially sublinear or logarithmic rates.The paper says the observed-source degree can be much smaller than m, allowing rates to scale with model sparsity.Source: A Glossary & Extended Related Work · p. 16

B Proofs

The proofs establish sample-complexity guarantees and an information-theoretic lower bound for weak-supervision structure learning, while examining limitations under singleton-separator assumptions. They also extend robust PCA structure learning to unobserved separator interactions and state a conjectured sharper bound for a restricted ensemble.

Effective Rank

  • Under the stated source-block conditions, the effective rank of the observed-source covariance estimate is bounded by a constant times d.The proof uses this bound to obtain concentration guarantees for estimating the covariance matrix.Source: B Proofs · p. 18

Remainder of the Proof

  • The proof replaces linear sample scaling with m^τ samples under source block decay and log m under the strong source block condition.These are sublinear and logarithmic alternatives, respectively, to scaling linearly in m.Source: B Proofs · p. 19

Lower Bound

  • For minimax-style lower bounds on graph-encoded distributions, the analysis constructs an ensemble of hypotheses and controls pairwise divergence; Fano’s lemma requires pairwise KL control, using symmetric KL divergence.Source: B Proofs · p. 21

Conjecture on Singleton Separator Set Dense Ensemble

  • For d > 3, removing one edge from a dense clique ensemble creates a separator of size d − 2, violating the singleton separator set assumption.The paper contrasts this with a conjectured dense ensemble that satisfies the assumption.Source: B Proofs · p. 22

Proofs

  • The authors conjecture that using Gs in Ensemble 2 of SW would yield a similar bound for the more restricted singleton-separator-set ensemble, sharpening Theorem 2.The conjecture concerns control over E[λs, λd+s].Source: B Proofs · p. 23

Beyond Singleton Separator Sets

  • When singleton separators do not hold, Σ−1 is not graph-structured, but an augmented generalized covariance matrix is, enabling robust PCA structure recovery.The augmentation adds variables in the separator set; the proposed approach recovers structure using Σ−1 as input.Source: B Proofs · p. 23
  • Ω(d^2 log m) sample complexity is achieved when the second condition holds, extending Loh and Wainwright [18] to graphs with one non-singleton separator set.The separator interaction λsλt is treated as a latent variable, allowing Algorithm 1 to be used when the graph structure is unknown.Source: B Proofs · p. 23

C Extended Experimental Details

The section compares the method with Varma et al. [40], which infers dependencies from weak-supervision source code without data. The method reports better F1 performance and learns additional dependencies on some tasks.

Extended Experimental Details

Loading 1903.05844v1…