Fast and Three-rious: Speeding Up Weak Supervision with Triplet Methods

1. Introduction

• For a class of binary Ising models, triplets reduce accuracy and correlation estimation to closed-form systems linear in the number of sources.This decomposition targets parameter-estimation methods that can require multiple SGD iterations or full inverse covariance estimation.Source: §1 · pp. 1–2
• The end-model generalization error scales at the supervised-learning asymptotic rate, with analysis that accounts for model misspecification using KL divergence.The bound does not require the latent-variable model to exactly represent the underlying distribution.Source: §1 · p. 2
• The parameter-estimation approach can be sample optimal up to constant factors, supported by an information-theoretic minimax lower bound.Source: §1 · p. 2
• Across benchmark and video evaluations, FlyingSquid matches or exceeds prior accuracy (up to 4.9 F1 points), learns parameters 170 times faster on average for simpler structures, and up to 4,000 times faster on video tasks.The evaluations cover three benchmark datasets and four video analysis tasks.Source: §1 · p. 2
• The window-based online extension updates model parameters while generating labels and training an end model, outperforming majority vote by up to 15.7 F1 points.The authors also prove a downstream generalization result for this extension that accounts for distributional drift.Source: §1 · p. 2
• The authors release FlyingSquid as a PyTorch layer that learns source accuracies in the end model’s training loop.They state that the layer can integrate weak supervision off the shelf into standard training setups.Source: §1 · p. 2

2.1. Background: Weak Supervision

• Weak supervision combines noisy source votes into probabilistic labels for training a downstream classifier, without observing ground-truth labels.Sources can abstain as well as vote, allowing high-precision signals without requiring high recall.Source: §2.1 · p. 3

2.2. Problem Setup

• The learning setup applies m sources to n unlabeled examples, combines their votes into probabilistic labels, and trains a classifier without ground-truth labels.Each task has an unobserved binary label, and sources may vote or abstain on individual elements.Source: §2.2 · p. 3

2.3. Label Model

• A user-provided dependency graph specifies conditional relationships among sources and tasks, which the label model represents with a binary Ising model.The model uses junction-tree inference, with clique and separator marginals as its parameters; Figure 2 illustrates independent sources, dependent sources, and temporally related tasks.Source: §2.3 · pp. 3–4, Figure 2 · p. 3

3.1. Learning the Mean Parameters

• Triplets of conditionally independent observed variables let the method recover hidden-variable accuracies from observable pairwise agreements.Variables need not label the same task if they are conditionally independent given the relevant hidden label; estimates can be averaged across triplets.Source: §3.1 · pp. 4–5

3.2. Mapping to the Label Model Parameters

• The method converts estimated mean parameters into label-model marginals by computing clique expectations and applying a linear transformation.The resulting parameters are distributions over maximal cliques and separator sets.Source: §3.2 · p. 5

3.3. Weak Supervision in Online Learning

• For online learning, a rolling window lets the method update label-model parameters while interleaving estimation and end-model training.The online setting sees each sample once and may face distributional drift; window size can be adjusted to balance sampling noise and drift.Source: §3.3 · p. 5

• When sources abstain, the sampling-error bound includes a √r factor; for higher-order cliques, error scales with the largest clique size.If no sources abstain, the √r factor is absent.Source: §4 · p. 6
• Parameter estimation is sample optimal in n and m up to constant factors for certain graphical models, with tightness in the conditionally independent, non-abstaining case.The stated sampling-error analysis assumes dependency-graph cliques are limited to three vertices; for higher-order cliques, error scales with the largest clique size.Source: §4 · p. 6
• The generalization bound's sampling-error terms scale as O(1/√n), the same asymptotic rate as supervised approaches.The bound also includes a model-misspecification term when the underlying distribution cannot be represented by the graphical model.Source: §4 · p. 6
• Richer graphical models can reduce divergence from the data distribution but may require higher sample complexity, making model constraint selection important.Source: §4 · p. 6

5.1. Quality

• FLYINGSQUID achieves the same or higher end-model quality than previous weak-supervision frameworks across the evaluated tasks.Table 1 reports F1 scores and label-model training times, comparing FLYINGSQUID with traditional supervision, majority vote, data programming, and sequential data programming.Source: Table 1 · p. 7, §5.1 · p. 7
• The end model outperforms the label model in four of seven tasks by learning input features unavailable to the noisy sources.For Commercial, the end model detects subtler pixel-space features than the sources’ black-frame heuristic.Source: §5.1 · p. 7

5.3. Online Weak Supervision

• Up to 15.7 F1 points over majority vote and 36.5 F1 points over traditional supervision are reported for the online method.The traditional-supervision model sees only one pass over the relatively small labeled test set, while the other methods also train on weakly labeled data.Source: Table 2 · p. 8, §5.3 · p. 8

5.1. Quality

• Replacing abstentions with random votes degrades performance by 25.6 points, while random individual triplet assignments average 23.8 points below aggregated assignments.Individual assignments also produce substantial performance variance; the best can match FLYINGSQUID, while poor assignments perform significantly worse.Source: §5.1 · p. 8

5.2. Speedup

• 440 times faster than data programming on benchmark tasks and 4,000 times faster than sequential data programming on video tasks.The paper attributes the speedups to closed-form parameter estimation, compared with iterative SGD-based approaches.Source: §5.2 · p. 8

5.3. Online Weak Supervision

• Online learning often underperforms offline learning, but can outperform it when training data is sufficient or continued test-set training enables specialization.In synthetic experiments, offline learning performs better with limited drift; with large periodic drift, a recent-window online model can specialize to the shifts.Source: §5.3 · p. 8, Figure 3 · p. 9

Latent Variable Estimation

• Unlike general latent-variable algorithms that may require many iterations or an expensive power method, this work decomposes weak-supervision estimation into closed-form subproblems.The paper identifies expectation maximization, Gibbs sampling, and tensor decomposition as examples of iterative or expensive general techniques.Source: §6 · p. 9
• Compared with Joglekar et al. (2013), the method handles abstaining sources and develops downstream behavior characterizations; compared with Chaganty & Liang (2014), it is more specialized and avoids tensor decomposition.Joglekar et al. (2013) corresponds to a simplified version when sources are conditionally independent and do not abstain.Source: §6 · p. 9

Weak Supervision

• Recent weak-supervision frameworks integrate noisy sources, while methods for sequential dependencies largely rely on iterative SGD rather than closed-form latent-variable estimation.The cited methods include Ratner et al. (2016; 2018), Bach et al. (2017; 2019), and sequential approaches by Zhan et al. (2019), Sala et al. (2019), and Safranchik et al. (2020).Source: §6 · p. 9

Crowdsourcing

• Unlike crowdsourcing approaches that filter workers using gold tasks or assume worker independence, this setting estimates noisy-source accuracies without ground-truth data.The label model can also be applied directly to crowd workers, as in the Weather task.Source: §6 · p. 9

Online Learning

• For online learning, the method does not rely on a pretrained task-specific teacher and addresses distributional drift with a rolling window.The cited online-learning alternatives include student-teacher training, while the paper notes that model updates must account for domain shift.Source: §6 · p. 9

7. Conclusion

• FlyingSquid uses closed-form latent-variable estimation to match or exceed prior approaches’ quality while running orders of magnitude faster, and supports online learning with a novel layer.The authors also prove generalization and sampling error bounds and show the method can be sample optimal; future work includes structure learning and data augmentation.Source: §7 · p. 9

A. Extended Related Work

• Joglekar et al. (2013) offers confidence intervals and a super-voter technique as useful extension directions, while FlyingSquid focuses on non-binary abstains and downstream theoretical guarantees.The two approaches are equivalent in the basic no-abstain case when accuracy signs are non-negative.Source: A. Extended Related Work · p. 13
• Compared with Chaganty & Liang (2014), FlyingSquid specializes to Ising models for weak supervision, replacing tensor power iteration with a non-iterative closed-form solution.The passage notes that triplet methods can also estimate some parameters in more complex exponential-family models, potentially minimizing tensor iterations.Source: A. Extended Related Work · p. 13

C.1.1. PROOF OF PROPOSITION 1

• The proof establishes that viY(i) and vjY(i) are independent, the property that enables the triplet method.The proof covers both the case where Y(j) differs from Y(i) and the case where they are equal.Source: §C.1.1 · pp. 14, 17

C.1.2. HANDLING LARGER CLIQUES

• For odd-sized cliques of variables linked to one hidden variable, the product of their variables is independent of that hidden variable, enabling factorization for larger cliques.The proposition states that the product of vkY(C) over k in C is independent of Y(C) when |C| is odd.Source: §C.1.2 · p. 17

C.1.3. AUGMENTING THE DEPENDENCY GRAPH

• For abstaining sources, the augmentation maps each source to paired observed variables, computes triplets over half of them, and maps clique expectations back to source cliques.The resulting product probabilities and expectations can be linearly transformed into label-model parameters using an invertible system.Source: §C.1.3 · p. 20, §C.1.4 · p. 20

C.1.4. LINEAR TRANSFORMATION TO LABEL MODEL PARAMETERS

• For each source clique, the method maps observable or estimable probabilities rC to label-model parameters µC through AsµC = rC, with a recursive construction for cliques and separator sets.The entries of rC are computed from observable probabilities or estimated directly, with other entries factorized into known or estimated terms.Source: §C.1.4 · pp. 20, 22

C.1.5. RESOLVESIGNS

• RESOLVESIGNS selects accuracy signs by choosing, for each hidden variable, the sign assignment with non-negative total accuracy, assuming accuracies average above zero.For a single task, only two overall sign choices need checking.Source: §C.1.5 · p. 23

C.2. Extensions to More Complex Graphical Models

• For multiclass labels, the method applies its binary-class algorithm repeatedly through a one-versus-all reduction; with fewer than three independent subgraphs, it can recover accuracies using another independence property.This alternative can be inaccurate when the label mean is near zero and fails with singleton potentials; its use with two subgraphs requires Proposition 1, and with one requires no source singleton potentials.Source: §C.2 · p. 23
• With source singleton potentials, the triplet method recovers mean parameters if at least two conditionally independent subgraphs lack observed-variable singleton potentials; an alternative quadratic triplet method handles singleton potentials on every source.The alternative uses class-conditional probabilities and has a closed-form solution to its resulting nonlinear equations.Source: §C.2 · pp. 23–24

C.3. Online Algorithm

• In online learning, rolling-window averages of observable moments yield probabilistic labels for each arriving sample, allowing labeling and end-model training to be interleaved without retaining the sample.To address distributional drift, the method averages over a rolling window of size W, which can be optimized theoretically.Source: §C.3 · p. 24

C.3.1. THEORETICAL ANALYSIS

• The online sampling-error analysis finds an optimal window size, balancing estimation error from fewer samples against drift in older samples.A global minimum of sampling error as a function of W exists, so W can be set to minimize expected parameter error.Source: §C.3.1 · pp. 24–26
• The analysis models overall drift as combining intrinsic distributional drift, model misspecification, and parameter-estimation error.The online setting evaluates a model trained on past probabilistic labels against the true distribution at the current time step.Source: §C.3.1 · p. 26
• The online generalization result bounds next-sample classification error while accounting for model misspecification and parameter-estimation error.The theorem’s guarantee applies under a condition on distributional drift and misspecification.Source: §C.3.1 · p. 26
• With sufficiently small overall drift, the past-data end-model parametrization performs at most ϵ worse in error probability than the best parametrization on the next sample.The theorem’s window length decreases as model misspecification and sampling error increase.Source: §C.3.1 · pp. 26, 30

D.1. Proof of Theorem 1 (Sampling Error)

• The proof combines concentration inequalities for triplet-estimated accuracies and observable quantities into a sampling-error result for graphs with cliques of size at most three.The result concerns the sampling error for label-model parameters.Source: §D.1 · p. 30
• The accuracy-estimation lemma assumes recoverable signs, positive minimum accuracy, and sufficiently many samples.It estimates accuracies from a second-moment matrix computed over n samples.Source: §D.1 · p. 30
• Choosing triplets that exclude the lowest-accuracy source removes minimum-accuracy dependence for other sources, leaving one additive 1/amin term in the bound.The remark contrasts this with a previous 1/amin^5 dependence.Source: §D.1 · p. 32

Concentration inequalities on observable data

• For the second-moment error bound, the analysis partitions matrix terms by the dependency graph’s conditionally independent subgraphs.The bound is expressed over entries indexed by pairs of sources sharing an edge.Source: Concentration inequalities on… · p. 33
• The matrix concentration argument adapts a covariance-matrix result to second-moment matrices, using sub-Gaussian variables with bounded higher-order moments.The stated adaptation provides concentration for the second-moment matrix.Source: Concentration inequalities on… · p. 33
• The observable-data analysis estimates label-model parameters through probabilities associated with individual sources and pairs sharing an edge in the dependency graph.The section separately develops estimates for µi and µij from these observable quantities.Source: Concentration inequalities on… · p. 34

D.2. Proof of Theorem 2 (Information Theoretical Lower Bound)

• The lower-bound construction uses one hidden variable, m observed variables conditionally independent given it, and no abstaining sources.The family is parameterized by sign vectors with canonical parameters separated by δ√m in Hamming distance.Source: §D.2 · pp. 36–37
• The proof applies Assouad’s lemma to the constructed family to obtain a minimax-risk bound from its parameter separation.It first relates the separation to the L2 loss.Source: §D.2 · p. 37
• The proof bounds the KL divergence between neighboring distributions by 2δ² before substituting that bound into the minimax-risk expression.The neighboring distributions differ in one index of the sign vector.Source: §D.2 · pp. 37–38

D.3. Proof of Theorem 3 (Generalization Error)

• Because true labels are unavailable, the proof uses noise-aware loss under the label-model distribution and accounts for estimating its parameters from n samples.It distinguishes population-level parameters from empirical estimates and the corresponding empirical-loss minimizer.Source: §D.3 · p. 38
• The proof bounds loss differences by relating the true and label-model conditional distributions through total variation and conditional KL divergence.It uses the bounded-loss condition and Pinsker’s inequality; a corresponding lower bound is also derived.Source: §D.3 · p. 39
• The final generalization result includes conditional KL divergence, the minimum covariance eigenvalue, and empirical risk minimization error.The proof also states that mean-parameter estimation error is always less than label-model-parameter estimation error.Source: §D.3 · p. 39

E. Extended Experimental Details

• Timing measurements used an Intel Xeon E5-2690 v4 CPU and Tesla P100-PCIE-16GB GPU; dataset split sizes and end models are reported in Table 4.The extended experimental details also cover task data, supervision sources, and ablations.Source: E. Extended Experimental Details · p. 40

E.1. Dataset Details

• Table 4 reports each dataset’s train/dev/test split; dev and test have ground-truth labels, while training labels come from FlyingSquid or a baseline.Source: Table 4 · p. 40
• Spouse and Weather use Ratner et al. splits, Spam uses Snorkel2 splits, Interview and Basketball use Sala et al. splits, and Commercial uses Fu et al. splits.Source: §E.1 · p. 40
• Tennis Rally footage came from four professional matches, was downsampled to 1 FPS, and was split by contiguous match segments so dev and test share a distribution.Source: §E.1 · p. 40

E.2. Task-Specific End Models

• Previously used architectures include an LSTM for Spouse, logistic regression for Spam and Weather, and ImageNet-pretrained ResNets for video; Tennis Rally uses ResNet-50 on individual frames.The authors do not claim these end models achieve the best possible task performance; they compare relative improvements from weak supervision.Source: §E.2 · p. 40
• End-model and label-model baselines use prior-work hyperparameters, while FlyingSquid’s class balance and triplets are selected using development data.End-model learning rate and momentum may be chosen by a simple grid search.Source: §E.2 · p. 40

E.3. Supervision Sources

• Supervision sources are short Python functions; Spouse, Weather, and Spam use text heuristics such as word presence or absence and regex patterns.Source: §E.3 · p. 41
• Interview sources use face identity and transcript text, while Basketball sources use detected balls or people and spatial heuristics.Source: §E.3 · p. 41
• Commercial sources use pixel histograms and transcript patterns; Tennis Rally sources use pose, player positions, and frame color histograms.Source: §E.3 · p. 41

E.4. Ablation Studies

• The ablations compare random-vote replacement for abstains with augmenting Gdep, and one random triplet selection with aggregation across assignments.Source: §E.4 · p. 41
• Replacing abstentions with random votes causes a major degradation in end-model performance on the three benchmark tasks.Table 5 compares F1 scores for random-vote replacement and FlyingSquid.Source: §E.4 · p. 41
• Single random triplet assignments have large variance, while mean or median aggregation is more stable and outperforms random assignments on average.A good seed can match Weather or exceed Spouse performance, but a bad seed can perform much worse, including catastrophically.Source: §E.4 · p. 41
• For all tasks except Weather, mean and median aggregation have no difference in label-model performance; for Weather, the passage reports median aggregation as more accurate.The passage attributes Weather’s zero triplet F1 scores to high abstention and says positive scores make mean aggregation more robust to those zeros.Source: §E.4 · p. 42