PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Rule Discovery for Labeling Text Data

Sainyam Galhotra, Behzad Golshan, Wang-Chiew Tan

arXiv:2005.06133v1cs.DBcs.LG

TL;DR

Weak-supervision approaches require expert-written rules or labeled subsets, which can be tedious or infeasible to collect when positives are rare. Darwin starts from a seed labeling function or positive sentences and iteratively proposes candidate heuristics in a hierarchy for annotator feedback. Verifying 50 heuristics suggested by Darwin is enough to achieve an F1-score of 0.80.

  • Problem

    Weak-supervision approaches require expert-written rules or labeled subsets, which can be tedious or infeasible to collect when positives are rare.

    Source: §1 · pp. 1–2

  • Method

    Darwin starts from a seed labeling function or positive sentences and iteratively proposes candidate heuristics in a hierarchy for annotator feedback.

    Source: THE Darwin SYSTEM · p. 4

  • Results

    Verifying 50 heuristics suggested by Darwin is enough to achieve an F1-score of 0.80.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Darwin is demonstrated on intent classification, entity-type detection, and relation-extraction labeling tasks.

    Source: §1 · p. 2

    UniversalSearch scans all hierarchy heuristics and may overfit without enough positives; LocalSearch can require many traversals when the seed differs from precise rules.

    Source: §3.4 · p. 6, §3.5 · p. 7

Abstract

from arXiv · show

Creating and collecting labeled data is one of the major bottlenecks in machine learning pipelines and the emergence of automated feature generation techniques such as deep learning, which typically requires a lot of training data, has further exacerbated the problem. While weak-supervision techniques have circumvented this bottleneck, existing frameworks either require users to write a set of diverse, high-quality rules to label data (e.g., Snorkel), or require a labeled subset of the data to automatically mine rules (e.g., Snuba). The process of manually writing rules can be tedious and time consuming. At the same time, creating a labeled subset of the data can be costly and even infeasible in imbalanced settings. This is due to the fact that a random sample in imbalanced settings often contains only a few positive instances. To address these shortcomings, we present Darwin, an interactive system designed to alleviate the task of writing rules for labeling text data in weakly-supervised settings. Given an initial labeling rule, Darwin automatically generates a set of candidate rules for the labeling task at hand, and utilizes the annotator's feedback to adapt the candidate rules. We describe how Darwin is scalable and versatile. It can operate over large text corpora (i.e., more than 1 million sentences) and supports a wide range of labeling functions (i.e., any function that can be specified using a context free grammar). Finally, we demonstrate with a suite of experiments over five real-world datasets that Darwin enables annotators to generate weakly-supervised labels efficiently and with a small cost. In fact, our experiments show that rules discovered by Darwin on average identify 40% more positive instances compared to Snuba even when it is provided with 1000 labeled instances.

1. INTRODUCTION

Labeled text data is costly to create, while weak-supervision frameworks depend on expert-written rules or labeled examples that can be scarce in imbalanced corpora. Darwin interactively proposes rules for annotators to verify and supports varied labeling tasks.

1. INTRODUCTION

  • Existing approaches can require tedious expert rule-writing, miss useful rules, or depend on labeled subsets that are costly to collect when positives are rare.Random samples may contain too few positive instances to make automatic rule inference feasible.Source: §1 · pp. 1–2
  • Darwin asks experts to verify suggested heuristics rather than manually write rules, and requires less expert supervision than Snorkel and Babble labble.Snorkel requires experts to write rules, while Babble labble asks them to explain label assignments.Source: §1 · p. 2
  • Darwin starts from a seed rule, proposes candidate rules with matching examples, and adapts its next suggestions based on annotator feedback.Annotators answer whether each rule is useful for capturing positives.Source: §1 · p. 2
  • Darwin supports labeling functions specified by context-free grammars, from phrase matching to conditions over dependency parse trees.Its contributions also include discovering patterns through similarity and overlap between rule-matched sentences and parallel rule evaluation by different annotators.Source: §1 · p. 2
  • 50 heuristics suggested by Darwin achieve an F1-score of 0.80, and Darwin is designed to find rules even when the candidate space is exponentially large.The introduction also reports theoretical approximation guarantees.Source: §1 · p. 2
  • Darwin is demonstrated on intent classification, entity-type detection, and relation extraction tasks.The introduction also states that experiments compare its ability to generate labeled examples using a limited number of questions.Source: §1 · pp. 2–3

2. PRELIMINARIES&PROBLEMDEFINI-TION

Darwin represents labeling heuristics as derivations from context-free grammars and seeks high recall under a limited oracle-query budget. The problem is NP-hard, and the framework supports both lexical and syntactic rule patterns.

2. PRELIMINARIES&PROBLEMDEFINI-TION

  • The search space consists of heuristic types specified by grammars, and the objective balances the recall of their combined coverage against a finite query budget.The paper also records classifier F-score as an experimental measure alongside recall.Source: §2 · pp. 3–4
  • A heuristic grammar is a context-free grammar, and a labeling heuristic is one of its derivations that covers the sentences satisfying it.Coverage is the number of sentences matched by the heuristic.Source: §2 · p. 3
  • Darwin’s default grammars pair TokensRegex for lexical patterns with TreeMatch for syntactic patterns over dependency parses.TreeMatch uses And, Child, and Descendant operations, and can express more complex heuristics than the cited rule-mining frameworks Snuba or Babble labble.Source: §2 · p. 3
  • An oracle receives a heuristic and examples from its coverage, then answers YES or NO on whether it is adequately precise.The theoretical oracle is assumed to answer correctly, although annotators may err in practice.Source: §2 · p. 3
  • Darwin seeks to maximize the recall of the union of selected heuristics’ coverage while limiting oracle queries; the stated problem is NP-hard.The paper assumes users consider a heuristic precise at a precision of at least 0.8 and relies on de-noising techniques rather than optimizing heuristic precision.Source: §2 · p. 4

THE Darwin SYSTEM

Darwin iteratively discovers labeling heuristics from a seed rule or positive examples, using an index, a candidate hierarchy, classifier estimates, and annotator feedback. Its components organize candidates and guide which heuristics to query.

THE Darwin SYSTEM

  • Darwin starts from seed labeling functions or positive instances, refines a classifier as data grows, and uses semantic generalization and local rule changes to discover heuristics.Its outputs include generated heuristics, discovered positive instances, and a classifier trained on labeled data.Source: THE Darwin SYSTEM · p. 4

3.1 Indexing the Input Corpus

  • The corpus index compactly represents heuristics matched by sentences, enabling fast lookup; it is built by merging each sentence’s derivation sketch.Index construction is linear in the number of sentences under a fixed limit on derivation rules and supports parallel construction across corpus parts.Source: §3.1 · p. 5

3.2 Heuristic-Hierarchy Generation

  • Hierarchy generation arranges promising candidates by subset/superset relationships, while cleanup removes heuristics that add no newly discovered positives.The candidates are drawn from the exponentially large space of possible heuristics.Source: §3.2 · pp. 5–6, §3.2.1 · p. 6

3.2.1 Candidate Generation

  • Candidate generation greedily selects heuristics with high coverage over discovered positives, using the index’s coverage counts to find promising candidates.Additional constraints can promote diversity in derivation rules, index level, or covered instances.Source: §3.2.1 · p. 6

3.3 Hierarchy Traversal

  • Traversal ranks heuristics by expected positive-instance gain, estimated with classifier probabilities, and offers local, global, or combined search strategies.LocalSearch explores neighbors of previously useful heuristics, whereas UniversalSearch selects the highest-benefit candidate globally; HybridSearch combines the strategies.Source: §3.3 · p. 6

3.4 LocalSearch

LocalSearch explores nearby heuristics, while UniversalSearch considers candidates across the hierarchy; HybridSearch switches between their strategies. The paper reports that HybridSearch performs well across dataset types, and feedback updates classifier and heuristic scores.

3.4 LocalSearch

  • LocalSearch selects beneficial candidates near previously verified heuristics, expanding toward parents after approval and children after rejection.It may require many steps when the seed is far from other precise heuristics, and does not exploit overlap between different heuristics’ coverage sets.Source: §3.4 · pp. 6–7

3.5 UniversalSearch

  • UniversalSearch evaluates heuristics across the hierarchy and selects the highest-benefit candidate, but can be inefficient and overfit when positives are scarce.With too few positive instances, it may fail to use hierarchy structure to find heuristics structurally similar to the seed.Source: §3.5 · p. 7

3.6 HybridSearch

  • HybridSearch performs well across dataset types, using hierarchy structure when classifier noise hurts and UniversalSearch’s generalization when LocalSearch stalls.It switches between the two strategies after a configurable number of unsuccessful attempts; the default threshold τ is 5.Source: §3.6 · p. 7

3.7 Score Update

  • After each oracle query, Darwin retrains the classifier, reevaluates heuristic scores, and, when feedback is positive, updates positives and generates new candidates.Source: §3.7 · p. 8

3.8 Theoretical Analysis

Under assumptions on the heuristic hierarchy and classifier, UniversalSearch provides a constant approximation to the optimal number of positives identified within a query budget. The analysis bounds heuristic scores and uses them to compare candidate heuristics.

Theoretical Analysis

  • At least αP_OPT positives are identified within query budget b under the stated hierarchy assumptions, with a constant-approximation guarantee.The hierarchy has O(n) heuristics, each with minimum coverage Ω(log n); the theorem gives the guarantee with probability 1 − o(1).Source: §3.8 · p. 8
  • With coverage |C_r| = c log n, a heuristic’s benefit score is at least (1 − ϵ)θβ′|C_r| with probability 1 − 2/n^4.The model assumes positive sentences exceed score θ with probability β and negative sentences do so with probability β′.Source: §3.8 · p. 8
  • With coverage |C_r| = c log n, a heuristic’s score is at most (1 + ϵ)(β + (1 − θ)(1 − β))|C_r| with probability 1 − 2/n^4.The expected score is at most (β + (1 − θ)(1 − β))|C_r|.Source: §3.8 · p. 8
  • When C_1 has more positives than C_2, UniversalSearch scores r_1 higher if |C_1|/|C_2| ≥ α, with probability 1 − 4/n^4.A heuristic is considered for benefit calculation only when its precision p_r exceeds constant γ.Source: §3.8 · p. 8
  • HybridSearch combines UniversalSearch’s holistic view with LocalSearch’s local generalization, but is slightly less efficient than either.UniversalSearch may not perform optimally in early iterations when training data is limited and its classifier assumption may not hold.Source: §3.8 · p. 9

4. EXPERIMENTS

Darwin is evaluated on five real-world datasets for positive-instance coverage and the quality of classifiers trained on its labels. Across the experiments, it identifies positives with fewer seed examples than Snuba, produces stable classifiers, and supports efficient rule verification.

4.1 Experimental Setup

  • The experiments evaluate five diverse real-world datasets spanning entity extraction, relationship extraction, and intent classification, measuring positive-instance coverage and classifier performance.Baselines include Snuba, HighP, active learning, and keyword sampling; HighC is also described as a coverage-maximizing baseline.Source: §4.1 · p. 9

4.2 Comparison with Snuba

  • With random seeds, Darwin(HS) identifies most positives from fewer than 25 sentences, whereas Snuba requires at least 200 for directions and 1000 for musicians.With expert-sampled positives, Snuba requires at least 100 positive samples in musicians; biased seeds containing neither “shuttle” nor “composer” further limit Snuba’s coverage, while Darwin(HS) generalizes across seed sizes.Source: §4.2 · p. 10

4.3 Rule Coverage

  • Darwin(HS) reaches coverage of 0.8 using fewer than 120 oracle queries in most cases, while other techniques perform less consistently.Cause-effect is the exception; under the stated crowd-label cost assumptions, more than 80% of positive labels cost $7.20.Source: §4.3 · p. 10

4.4 Quality of the Classifier

  • Darwin(HS) dominates other techniques in classifier quality across datasets, with Darwin’s food-intent F-score at 0.84 versus the 0.54 maximum reported by.Darwin classifiers also exceed 0.8 F-score for Travel and Career, versus ’s reported maximum of 0.58 for those intents.Source: §4.4 · p. 11

4.5 Additional Experiments

  • On professions, an optimization reduces HybridSearch and UniversalSearch runtime from 2 hours 45 minutes to 65 minutes by skipping many classifier evaluations.Index generation takes under 5 minutes, and hierarchy generation takes under 15 minutes for a 100K corpus.Source: §4.5 · p. 11
  • Adding Snorkel usually does not improve classifier results because Darwin’s rules already have good coverage and low noise, though it can help on directions.The experiment compares classifiers trained directly on Darwin’s labels with noise-aware classifiers trained using those rules.Source: §4.5 · p. 12, Table 2 · p. 12
  • Crowd annotators produced fewer than 10 false-positive responses among 69 positive heuristics, and 100 queries required under 40 minutes of human effort.Annotators took 23 seconds per heuristic on average; showing more examples can lower error, and queries can be parallelized.Source: §4.5 · p. 12

5. RELATED WORK

Darwin addresses rule discovery in weak supervision, complementing systems that use external knowledge or de-noise labels. It differs from existing rule-writing and rule-verification tools by supporting user-selected grammars and generating candidate rules itself.

Weak Supervision

  • Darwin is designed for settings without additional information sources, where annotators must write rules and there is limited work on facilitating discovery of high-quality rules.Distant-supervision methods infer labels from external knowledge bases [21], while Snuba mines rules from labeled data.Source: §5 · p. 12
  • Unlike Babble Labble [6], which transforms natural-language explanations into rules in one internal language, Darwin lets experts choose a rule language suited to the task.Babble Labble simplifies rule writing by having annotators explain why a data point received a label.Source: §5 · p. 12

Crowdsourcing Frameworks

  • Darwin’s discovered rules can be passed to de-noising systems such as Snorkel [12] and Coral [16], while CrowdGame verifies rules from a pre-existing manageable set.Darwin instead generates promising rules from a grammar, and crowd-based rule verification can be modeled as its oracle.Source: §5 · p. 12

6. CONCLUSION

Darwin compiles semantic and syntactic corpus patterns into a hierarchy of candidate heuristics for annotator verification. Experiments cover labeling tasks including intent classification, entity extraction, and relationship extraction.

6. CONCLUSION

  • Darwin organizes candidate heuristics generated from corpus patterns into a hierarchy that helps select rules for annotator verification across a range of labeling tasks.The conclusion describes the system as an interactive end-to-end approach for identifying precise text-labeling rules.Source: §6 · p. 12

A. PROOF OF LEMMA 4

The supplied proof passage introduces an expected-score calculation for a heuristic function.

A. PROOF OF LEMMA 4

  • The proof introduces the expected score of a heuristic function.The passage does not supply further proof steps.Source: A. PROOF OF LEMMA 4 · p. 14

B. PROOF OF LEMMA 5

The proof scores a heuristic by summing its sentence-level terms, then uses Hoeffding’s inequality to bound that score.

B. PROOF OF LEMMA 5

  • Heuristic r’s score is the sum of X_s over sentences s in C_r.The proof says the score’s expected value is calculated in Lemma 4.Source: B. PROOF OF LEMMA 5 · p. 14
  • Hoeffding’s inequality bounds the average of X_s over C_r by a threshold involving β and θ.The stated probability is greater than 1 − 2/n^4.Source: B. PROOF OF LEMMA 5 · p. 14
  • The threshold is (1 + ϵ)(β + (1 − θ)(1 − β)) for the average over C_r.The proof states this upper bound holds with probability greater than 1 − 2/n^4.Source: B. PROOF OF LEMMA 5 · p. 14

C. PROOF OF LEMMA 6

The proof compares a lower bound on one heuristic’s benefit with an upper bound on a competing heuristic’s score to establish a score ordering.

C. PROOF OF LEMMA 6

  • The calculated benefit of h1 is at least (1 − ϵ)θβ′|C_r1| with probability 1 − 2/n^4.The proof derives this bound using Lemmas 3 and 5.Source: C. PROOF OF LEMMA 6 · p. 14
  • The score of r2 is at most (1 + ϵ)(β + (1 − θ)(1 − β))|C_r2| with probability 1 − 2/n^4.The proof uses this upper bound alongside h1’s benefit bound.Source: C. PROOF OF LEMMA 6 · p. 14
  • When the stated bound for h1 exceeds the bound for r2, the proof concludes score(r1) > score(r2).The comparison is given as an inequality in the proof.Source: C. PROOF OF LEMMA 6 · p. 14

D. ADDITIONAL EXPERIMENTS

The additional experiments test Darwin(HS)’s sensitivity to traversal settings, seed rules, candidate counts, and classifier training. They report similar performance across the tested variations, with a time-cost trade-off for larger τ.

Sensitivity to HybridSearch’s traversal parameters

  • Darwin(HS) performs similarly across varying τ, while larger τ can make candidate evaluation time-consuming.Larger τ makes HybridSearch rely on its classifier to evaluate all rule candidates for more steps; solution quality improves slightly on the musicians dataset.Source: D. ADDITIONAL EXPERIMENTS · p. 14, Figure 12 · p. 14

Sensitivity to seed rule

  • 8 queries let Darwin generalize the sentence-level seed rule before its performance became similar to the other seed rules.The experiment reports similar performance for three seed-rule types on the musicians dataset.Source: D. ADDITIONAL EXPERIMENTS · p. 14

Sensitivity to number of generated candidates

  • Generating 10K candidates per iteration helped identify precise rules, while performance remained similar across different candidate counts.The candidates are high-coverage rules organized into an index; increasing index size can reduce efficiency.Source: D. ADDITIONAL EXPERIMENTS · p. 14, Figure 13 · p. 14

Sensitivity to classifier quality

  • Darwin(HS) performance was robust to classifier changes when measuring oracle queries needed to label at least 75% of positive sentences.The experiment varied neural-network training epochs; more epochs tended to increase overfitting on the training data.Source: D. ADDITIONAL EXPERIMENTS · pp. 14–15, Figure 14 · p. 15
Loading 2005.06133v1…