PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning from Rules Generalizing Labeled Exemplars

Abhijeet Awasthi, Sabyasachi Ghosh, Rasna Goyal, Sunita Sarawagi

arXiv:2004.06025v2cs.LGcs.CLstat.ML

TL;DR

Labeled data is often unavailable or costly to collect, despite the importance of clean task-specific instance labels for reliable results. The method couples rules with labeled exemplars and jointly trains a classifier and latent rule-coverage distributions using a soft implication loss. Across five tasks, the method outperformed all eight compared methods overall; on Question, it gained 11.7 points over Only-L versus 0.3 for the best existing method.

  • Problem

    Labeled data is often unavailable or costly to collect, despite the importance of clean task-specific instance labels for reliable results.

    Source: §1 · p. 1

  • Method

    The method couples rules with labeled exemplars and jointly trains a classifier and latent rule-coverage distributions using a soft implication loss.

    Source: §1 · pp. 1–2, §2 · p. 2, §2.1 · p. 4

  • Results

    Across five tasks, the method outperformed all eight compared methods overall; on Question, it gained 11.7 points over Only-L versus 0.3 for the best existing method.

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

  • Takeaways & Limitations

    Coupled exemplars provide supervision about correct rule firings, helping denoise rules while the trained classifier uses them for improved accuracy.

    Source: §5 · p. 9

    The noise model assumes rule-induced errors arise from overgeneralization and that a smaller neighborhood around exemplars has zero noise.

    Source: §2 · p. 2

Abstract

from arXiv · show

In many applications labeled data is not readily available, and needs to be collected via pain-staking human supervision. We propose a rule-exemplar method for collecting human supervision to combine the efficiency of rules with the quality of instance labels. The supervision is coupled such that it is both natural for humans and synergistic for learning. We propose a training algorithm that jointly denoises rules via latent coverage variables, and trains the model through a soft implication loss over the coverage and label variables. The denoised rules and trained model are used jointly for inference. Empirical evaluation on five different tasks shows that (1) our algorithm is more accurate than several existing methods of learning from a mix of clean and noisy supervision, and (2) the coupled rule-exemplar supervision is effective in denoising rules.

1 INTRODUCTION

The paper proposes coupling rules with labeled exemplars to combine coarse rule supervision with instance-level labels. It targets rule overgeneralization by learning rule coverage jointly with the classifier, and reports stronger results than existing methods across five tasks.

1 INTRODUCTION

  • Humans pair labeled instances with rules they generalize from them, making coupled rule-exemplar supervision a natural collection paradigm.Rules offer cheap coarse-grained supervision, while labeled instances provide expensive fine-grained supervision.Source: §1 · p. 1
  • Rule-induced labels can be noisier than instance labels because rules may overgeneralize beyond the examples that prompted them.The sentiment and slot-filling examples illustrate rules mislabeling unseen text.Source: §1 · pp. 1–2
  • The approach models whether each rule correctly covers an instance, jointly trains that coverage with the classifier, and uses denoised rules at inference.The authors evaluate the paradigm on five tasks spanning question classification, spam detection, sequence labeling, and record classification.Source: §1 · p. 2
  • Experiments across five tasks spanning question classification, spam detection, sequence labeling, and record classification show that the proposed supervision paradigm enables synergy between rule-level and instance-level supervision and performs much better than several recent frameworks.Source: §1 · p. 2

2 TRAINING WITH RULES AND EXEMPLARS

The method learns a classifier alongside rule-specific coverage distributions, treating rules as noisy generalizations of labeled exemplars. A soft implication constraint uses predicted coverage to determine when rule labels should supervise the classifier.

2 TRAINING WITH RULES AND EXEMPLARS

  • The formal setup uses labeled examples with optional rule associations and unlabeled instances; rules may overlap or assign conflicting labels.The goal is to train a classifier using both data sets while learning systematic rule noise rather than relying only on consensus labels.Source: §2 · p. 2
  • A latent Bernoulli coverage variable marks whether a rule's label is trusted for each covered instance; zero flags suspected overgeneralization and abstains.A separate network predicts coverage probabilities, which can restrict a rule's firing region.Source: §2 · pp. 2–3
  • Figure 1 illustrates overgeneralized rules and revised boundaries that exclude wrongly covered examples while retaining useful unlabeled points.The example depicts labeled points, unlabeled points, and true labels across a two-dimensional instance space.Source: §2 · p. 3, Figure 1 · p. 3

2.1 HOW WE JOINTLY LEARN Pθ AND Pjφ

  • Exemplars provide sure coverage labels, and covered instances with conflicting human labels provide sure negative coverage labels.For agreeing labels, coverage is not required to be one; when exemplars are sparse, a noise-tolerant loss regularizes toward more rule firings.Source: §2.1 · p. 3
  • The negative implication loss penalizes high predicted coverage when the classifier assigns low probability to the rule's label, while low coverage withdraws that rule supervision.Figure 2 plots the log probability against the classifier's label probability and the rule network's coverage probability.Source: §2.1 · pp. 3–4, Figure 2 · p. 4
  • Applying the implication constraint to each rule-label pair subsumes the need for a separate constraint between conflicting rules.The final objective combines the implication probability with ordinary likelihood terms.Source: §2.1 · p. 4
  • ImplyLoss consistently performed best among the tested constraint methods, including posterior regularization and co-training.The authors also report that it is much better than eight other methods and gains over Only-L on all datasets.Source: §2.1 · p. 4
  • The system uses a shared embedding, a classifier network, and a rule network; at inference, it combines classifier scores with labels from rules predicted to cover the instance.The paper describes this as soft voting, with denoised rules providing higher-precision labels than the original rules.Source: §2.1 · p. 4

3 EXPERIMENTS

Across five datasets, ImplyLoss outperformed the compared methods and improved over Only-L; diagnostics report rule precision above 91% after denoising.

3 EXPERIMENTS

  • The experiments cover five datasets across text classification, sequence labeling, and record classification, with rules obtained manually, from public sources, or automatically.Dataset and rule statistics are summarized in Table 1.Source: §3 · pp. 4–5, Table 1 · p. 5

3.1 COMPARISON WITH DIFFERENT METHODS

  • ImplyLoss beats all eight comparison methods and improves over Only-L on every dataset; on Question, its gain is 11.7 points versus 0.3 for the best existing method.Table 2 compares the methods across five datasets; higher is better.Source: Table 2 · p. 6, §3.1 · p. 7
  • After suppressing rule labelings predicted as outside true coverage, precision exceeds 91% on every dataset and rises from 64% to 98% on Question.More labelings are suppressed on datasets with noisier rules, such as Question compared with SMS.Source: §3.1 · p. 8, Figure 3 · p. 8
  • ImplyLoss performs better than L2R when Census rules have low precision, after high-precision rules are successively removed.The original Census rules have higher precision and coverage; the paper attributes ImplyLoss's advantage with low-precision rules to its denoising.Source: §3.1 · p. 8, Figure 4 · p. 8
  • Removing exemplar-rule supervision from the coverage likelihood usually lowers ImplyLoss performance, though it still surpasses most Table 2 methods.The ablation drops the likelihood term that marks a rule as firing on its exemplars.Source: §3.1 · p. 8, Table 3 · p. 8
  • As the labeled set grows on Question while the number of rules stays fixed, the performance gap between ImplyLoss and the compared methods narrows.The plot compares ImplyLoss with Only-L, L+Usnorkel, and Posterior Regularization.Source: §3.1 · p. 8

4 RELATED WORK

Prior work addresses noisy labels, clean-plus-noisy supervision, and logical rules, while this paper treats rules as noisy and corrects them jointly with the classifier.

4 RELATED WORK

  • Most noise-robust losses assume noise is input-independent given the true label, whereas this model treats noise as systematic and instance-dependent.The cited examples include MAE, Generalized Cross Entropy, and Ramp loss.Source: §4 · pp. 8–9
  • Unlike rule-based network methods that assume correct rules, this approach corrects noisy rules while using them to improve the classifier.The paper also contrasts its rule-specific cleaning with methods that use rules as-is.Source: §4 · p. 9
  • For clean-plus-noisy supervision, prior approaches use clean validation data, select low-loss examples, transform noisy labels, or learn an instance-independent confusion matrix.This paper instead uses rule-specific latent coverage variables and an implication loss that withdraws label supervision when predicted coverage is low.Source: §4 · p. 9
  • Posterior regularization and Ratner et al. (2016) are compared as rule-learning approaches; the latter weights black-box rules, while this model learns nonlinear rule boundaries.The paper reports superior performance against both approaches in its experiments.Source: §4 · p. 9

5 CONCLUSION

The conclusion presents coupled rule-exemplar supervision and joint rule denoising as a way to use rules and labeled instances together, reporting better results than generic noise-tolerant learning on five datasets.

5 CONCLUSION

  • Coupled rule-exemplar supervision combines the scalability of top-level rules with the quality of instance-level labels.The authors describe this paired supervision as natural because people inspect examples when coding rules.Source: §5 · p. 9
  • The training algorithm jointly denoises rules with latent coverage variables and constrains the classifier through a soft implication on the true label.The denoised rules and trained classifier are used jointly for inference.Source: §5 · p. 9
  • Across five datasets, the rule-specific denoising algorithm performed better than generic noise-tolerant learning.The authors identify deployment on other applications with scarce human supervision as future work.Source: §5 · p. 9
  • Code and experiment data are available in the project repository.The paper provides the repository address in its reproducibility statement.Source: §5 · p. 9

A POSTERIOR REGULARIZATION METHOD

The method couples a classifier and rule-coverage models through a joint distribution constrained so that a firing rule’s label agrees with the instance label.

A POSTERIOR REGULARIZATION METHOD

  • For an instance covered by rule Rj, the joint distribution constrains a firing coverage variable rj=1 to the rule’s label ℓj.Coverage variables are fixed at zero for rules that do not cover the instance.Source: A POSTERIOR REGULARIZATION METHOD · p. 13
  • A classifier models Pθ(y|x), while a separate network with parameters φ models each rule’s coverage probability Pjφ(rj|x).The singleton marginals of joint Q are tied to these learned distributions.Source: A POSTERIOR REGULARIZATION METHOD · p. 13
  • The objective combines labeled-data log-likelihoods, KL terms matching Q to the learned marginals, and a weighted soft-constraint penalty.The likelihood terms train the classifier and coverage models on their respective labeled data.Source: A POSTERIOR REGULARIZATION METHOD · p. 13
  • Training alternates between computing corrected Q marginals and updating θ and φ to match Q using stochastic gradients.The Q step uses current model distributions and requires no neural optimization; the procedure follows posterior regularization and resembles EM.Source: A POSTERIOR REGULARIZATION METHOD · pp. 13–14
  • Algorithm 1 summarizes the loop: obtain classifier and rule-coverage distributions, compute Q marginals, then update θ and φ.The algorithm processes a random batch drawn from U ∪ L.Source: A POSTERIOR REGULARIZATION METHOD · p. 14

A.1 PROOF: ALTERNATING SOLUTION FOR OPTIMIZATION OBJECTIVE IN EQN 12

The appendix derives an alternating solution by optimizing the joint distribution Q and then the model parameters with Q fixed.

A.1 PROOF: ALTERNATING SOLUTION FOR OPTIMIZATION OBJECTIVE IN EQN 12

  • The derivation treats each Q(y,r) as an optimization variable subject to normalization, represented with a Lagrange multiplier.It rewrites the KL terms as a combined KL(Q; Pθ,φ).Source: §A.1 · p. 14
  • Setting the derivative with respect to Q(y,r) to zero yields its solution, with marginals computed by message passing.The text identifies this solution as Equation 13.Source: §A.1 · p. 14
  • With Q fixed, the optimal updates for Pθ and Pjφ are described as straightforward, and their proof is omitted.Source: §A.1 · p. 14

B LIST OF RULES

The appendix lists sample rules for four task types, with firing conditions based on regex matches, Boolean clauses, or word-list matches.

B LIST OF RULES

  • TREC Question Classification rules fire when a regex matches.The appendix provides sample rules for this task.Source: Table 4 · p. 15
  • Spam Classification rules fire when a regex matches.The appendix provides sample rules for this task.Source: Table 5 · p. 15
  • Census-dataset rules fire when all clauses are true.The appendix provides sample rules for this task.Source: Table 6 · p. 15
  • MIT-R rules fire when a regex matches or a sentence contains a word from the provided word lists.The appendix provides sample rules for this task.Source: Table 7 · p. 16

C HYPERPARAMETERS

The appendix reports the training protocol and provides hyperparameter tables for several methods and datasets, including L2R.

C HYPERPARAMETERS

  • Models used Adam with default β1, β2, and ϵ, dropout of 0.8 keep probability, and up to 100 epochs with validation-based early stopping.The best validation-set model was evaluated on the test set, and each experiment used 10 random initializations.Source: C HYPERPARAMETERS · p. 17
  • Table 8 lists hyperparameters by method and dataset, with batch size abbreviated bs and learning rate abbreviated lr.Only-L used a smaller batch size because its labeled set L was smaller.Source: Table 8 · p. 17
  • Table 9 lists the meta-learning rate, learning rate, and batch size used for L2R across datasets.The cited L2R method is Ren et al. (2018b).Source: Table 9 · p. 17
Loading 2004.06025v2…