GrASP: A Library for Extracting and Exploring Human-Interpretable Textual Patterns

an open-source Python tool that learns human-readable text patterns (sequences of linguistic attributes) separating two sets of texts, plus a web viewer for them

Piyawat Lertvittayakumjorn, Leshem Choshen, Eyal Shnarch, Francesca Toni · LREC 2022 · 2022

• arXiv
• PDF
• HTML
• Hugging Face
• alphaXiv
• DOI
• ACL Anthology
• Semantic Scholar
• Publisher
• Project page
• Code
• Demo

In one sentence

GrASP is an open-source Python library and web exploration tool that learns human-interpretable textual patterns — sequences of conjoined linguistic attributes such as part-of-speech, hypernym and sentiment tags — distinguishing a positive from a negative set of texts.

Abstract

Data exploration is an important step of every data science and machine learning project, including those involving textual data. We provide a novel language tool, in the form of a publicly available Python library for extracting patterns from textual data. The library integrates a first public implementation of the existing GrASP algorithm. It allows users to extract patterns using a number of general-purpose built-in linguistic attributes (such as hypernyms, part-of-speech tags, and syntactic dependency tags), as envisaged for the original algorithm, as well as domain-specific custom attributes which can be incorporated into the library by implementing two functions. The library is equipped with a web-based interface empowering human users to conveniently explore data via the extracted patterns, using complementary pattern-centric and example-centric views: the former includes a reading in natural language and statistics of each extracted pattern; the latter shows applications of each extracted pattern to training examples. We demonstrate the usefulness of the library in classification (spam detection and argument mining), model analysis (machine translation), and artifact discovery in datasets (SNLI and 20Newsgroups).

Questions this paper answers

is there software that finds recurring word patterns in a labelled text dataset, beyond counting words?

which open-source library extracts human-readable linguistic attribute patterns from labelled text corpora?

how do I explore a labelled text collection at the pattern level instead of by word frequency?

I want to inspect what distinguishes my positive and negative examples — is there a ready-made pattern-mining tool I can install?

GrASP fills a gap in textual data exploration tooling, where most tools for text analyze data only at the word or n-gram level. GrASP instead learns and displays recurring generalizable patterns that match tokens by linguistic attributes rather than surface form.
Holds for: Positioning as of 2022, per the authors' survey of exploration tools, pattern-based search engines (which require an expert to write the patterns) and rule-based extraction systems; built-in attributes are English-only.

The GrASP library is the first publicly released implementation of the GrASP pattern-extraction algorithm, which was proposed by Shnarch et al. in 2017 without a public implementation.
Holds for: As of the 2022 LREC publication, and about implementations of that specific algorithm; the authors report finding no public tools for other pattern-learning algorithms either.

if you delete training examples that contain misleading shortcut phrases, does the model do better on data from elsewhere?

does filtering artifact-matching training instances improve out-of-distribution accuracy and macro F1 on a 20Newsgroups-to-Religion transfer?

how do I use pattern-flagged spurious cues to clean a training set for better generalization?

should I drop artifact-matched examples from my training data if I care about performance on a different distribution?

Removing 20Newsgroups training examples matched by GrASP-flagged artifact patterns raised out-of-distribution accuracy on the Religion test set from 0.674 to 0.725. Macro F1 rose from 0.682 to 0.739, versus a size-matched sample of the original data.
Holds for: Christianity vs. Atheism+Religion(misc) with a 1D CNN over 300-dimensional GloVe embeddings, average of 5 runs with SD up to 0.06. The larger class was downsampled and patterns kept at precision ≥75% before a human flagged artifacts.

Filtering out examples matched by GrASP artifact patterns left in-domain 20Newsgroups performance essentially unchanged, at 0.800 accuracy and 0.804 macro F1 versus 0.810 and 0.818 for the size-matched unfiltered sample.
Holds for: Christianity vs. Atheism+Religion(misc) with a 1D CNN and GloVe embeddings, average of 5 repetitions with SD 0.01–0.03; the in-domain gap is within one SD.

does throwing away training examples with shortcut phrases cost accuracy on the original test set?

what is the in-domain accuracy and macro F1 penalty from artifact-pattern-based training set filtering on 20Newsgroups?

if I remove artifact-matched examples, am I trading away in-domain accuracy to get it?

Filtering out examples matched by GrASP artifact patterns left in-domain 20Newsgroups performance essentially unchanged, at 0.800 accuracy and 0.804 macro F1 versus 0.810 and 0.818 for the size-matched unfiltered sample.
Holds for: Christianity vs. Atheism+Religion(misc) with a 1D CNN and GloVe embeddings, average of 5 repetitions with SD 0.01–0.03; the in-domain gap is within one SD.

how much reading does a person have to do to decide which extracted phrase patterns are misleading shortcuts?

how many candidate high-precision patterns does an annotator have to review to identify dataset artifacts in a 20Newsgroups topic task?

how do I get a human to sort mined patterns into meaningful signal versus dataset artifact?

how many patterns should I budget for an annotator to label as artifacts before I start filtering?

In the 20Newsgroups artifact use case, GrASP produced 133 patterns at precision ≥75%. A human annotator using the web exploration tool flagged 40 of the 133 as semantically irrelevant to the task and therefore likely artifacts.
Holds for: One annotator, Christianity vs. Atheism+Religion(misc), after downsampling the majority class; no inter-annotator agreement or annotation-time measurement is reported.

do the giveaway phrases people found in the Stanford natural language inference data show up as automatically mined patterns?

can pattern mining over SNLI entailment and contradiction hypotheses recover known hypothesis-only annotation artifacts, and at what precision?

how do I check whether my crowdsourced inference hypotheses contain label-revealing cues?

would running pattern extraction on SNLI hypotheses tell me anything the artifact papers did not already report?

Applied to 10K SNLI entailment and 10K contradiction hypotheses, GrASP recovered known annotation artifacts with added structure. Examples include an entailment pattern of noun + 'be' + a hypernym of 'outside' at 97% precision, and negative-sentiment verbs correlating with contradiction at 75.7% precision.
Holds for: Hypothesis-only subsets of SNLI entailment vs. contradiction, 200 patterns and alphabet size 200, information gain as selection criterion, patterns kept only at precision ≥75%; precisions are on the training subset, not a held-out split.

can you describe what makes a sentence easy or hard to translate using recurring patterns?

what does pattern extraction over the top and bottom quartiles of WMT19 English-German quality-estimation data reveal about easy versus hard source inputs?

how do I characterize which source sentences my translation system will struggle with?

if I mine patterns from quality-estimation scores, will I get a usable profile of hard-to-translate input or only of easy input?

Using the top and bottom 25% of WMT19 English-German quality-estimation sentences as positive and negative sets, GrASP found 60 patterns with precision ≥80% for easy-to-translate inputs. Only 16 patterns above 60% precision were found for hard inputs, indicating challenging inputs are more diverse.
Holds for: 13K automatically translated sentences from one MT model judged by human quality scores, default GrASP hyperparameters, 100 patterns output; recall of the high-precision positive patterns ranges from 5% to 35%, and the data mixes Reviews and IT domains.

GrASP patterns over WMT19 English-German quality-estimation data independently surfaced translation difficulties already documented in the literature. GrASP dedicated a pattern to the lemma 'be' and found an adjective-noun-noun pattern capturing structural ambiguity such as 'new blog entry'.
Holds for: Qualitative agreement with prior MT analysis for a single MT model on WMT19 en-de quality-estimation data; the patterns were selected by the authors as illustrative, with no systematic recall over the set of known hurdles.

does automatic pattern mining find the same cues in argumentative sentences that experts already knew about?

on a topic-dependent argument mining corpus, which extracted pattern is most indicative of argumentative sentences?

how do I check that a pattern-extraction run on argument mining data agrees with known expert indicators?

can I trust mined patterns as a sanity check by seeing whether they rediscover established argument indicators?

On the topic-dependent argument mining corpus of 4,065 training and 1,720 test topic-sentence pairs, GrASP's most indicative pattern was the word 'that' in its preposition sense. That matches the known expert indicator of argumentative content.
Holds for: Information gain as selection criterion, 100 patterns, up to 2 gaps allowed, built-in attributes plus a custom binary attribute for lexicon membership of argumentative words; no downstream classification accuracy is reported.

how can a single rule match two spam texts that have almost no words in common?

what does an attribute-sequence pattern over sentiment, part-of-speech and gap constraints look like on an SMS spam corpus?

how do I write or find a pattern that generalizes across differently-worded spam messages?

will mined patterns actually group paraphrased spam together, or just cluster shared keywords?

A single GrASP pattern groups 3 SMS spam messages that share almost no words, such as "awarded a SiPix Digital Camera" and "WIN a FREE Bluetooth Headset". That pattern is a positive-sentiment word followed closely by a determiner and then a proper noun.
Holds for: Illustrative examples from the SMS spam dataset used throughout the paper; no coverage or precision figure is measured for this pattern.

if a tool outputs patterns full of linguistic tags, how does a non-linguist read them?

how are extracted attribute patterns with hypernym and POS constraints converted into natural-language descriptions?

how do I present mined linguistic patterns to annotators or domain experts who do not know POS tags?

can I hand pattern-mining output to teammates without linguistics training and expect them to interpret it?

The GrASP library translates each extracted pattern into an English sentence via templates, so readers without linguistic training can interpret patterns. It renders [[HYPERNYM:communication.n.02], [POS:NUM]] as "A type of communication (n), closely followed by a number".
Holds for: Template-based translation of the built-in English attributes; custom attributes require the user to implement their own explanation function, and no user study of comprehension is reported.

what extra features does the released pattern-mining library have compared with the algorithm first described in 2017?

which extensions does the GrASP library add to the 2017 algorithm — custom attributes, selection criteria, gap limits, coverage thresholds?

how do I plug in my own domain attributes or change how mined patterns are ranked?

can I adapt the library's pattern-selection criterion to my own dataset instead of using the default?

The GrASP library extends the original 2017 algorithm with user-pluggable pattern-selection criteria and domain-specific custom attributes added by implementing 2 functions. It also adds a limit on gaps between matched tokens that overrides the window size, and a minimum-coverage threshold.
Holds for: The released library's API and hyperparameters; the original algorithm ranked patterns by information gain only, and no experiment isolates the benefit of each added parameter.

what does the browser-based viewer for mined text patterns actually display?

what report views does the GrASP web interface render, and how do pattern-centric and example-centric views differ?

how do I browse mined patterns alongside the examples they match and the words they highlight?

if I have patterns and matched examples from my own extractor, can I use the web viewer to inspect them?

The GrASP web tool renders 4 linked report views, 2 pattern-centric and 2 example-centric. The pattern-centric views give a sortable table of all patterns with coverage, precision, recall and F1 plus the examples each pattern matches, while the example-centric views highlight matched words per example.
Holds for: Flask-based tool consuming the JSON exported by the GrASP library; it can also display output from other pattern-extraction algorithms if formatted into the required JSON schema.

Claims and scope

• The GrASP library is the first publicly released implementation of the GrASP pattern-extraction algorithm, which was proposed by Shnarch et al. in 2017 without a public implementation.
  Scope: As of the 2022 LREC publication, and about implementations of that specific algorithm; the authors report finding no public tools for other pattern-learning algorithms either.
• GrASP fills a gap in textual data exploration tooling, where most tools for text analyze data only at the word or n-gram level. GrASP instead learns and displays recurring generalizable patterns that match tokens by linguistic attributes rather than surface form.
  Scope: Positioning as of 2022, per the authors' survey of exploration tools, pattern-based search engines (which require an expert to write the patterns) and rule-based extraction systems; built-in attributes are English-only.
• Removing 20Newsgroups training examples matched by GrASP-flagged artifact patterns raised out-of-distribution accuracy on the Religion test set from 0.674 to 0.725. Macro F1 rose from 0.682 to 0.739, versus a size-matched sample of the original data. (Table 2)
  Scope: Christianity vs. Atheism+Religion(misc) with a 1D CNN over 300-dimensional GloVe embeddings, average of 5 runs with SD up to 0.06. The larger class was downsampled and patterns kept at precision ≥75% before a human flagged artifacts.
• Filtering out examples matched by GrASP artifact patterns left in-domain 20Newsgroups performance essentially unchanged, at 0.800 accuracy and 0.804 macro F1 versus 0.810 and 0.818 for the size-matched unfiltered sample. (Table 2)
  Scope: Christianity vs. Atheism+Religion(misc) with a 1D CNN and GloVe embeddings, average of 5 repetitions with SD 0.01–0.03; the in-domain gap is within one SD.
• In the 20Newsgroups artifact use case, GrASP produced 133 patterns at precision ≥75%. A human annotator using the web exploration tool flagged 40 of the 133 as semantically irrelevant to the task and therefore likely artifacts. (Section 6)
  Scope: One annotator, Christianity vs. Atheism+Religion(misc), after downsampling the majority class; no inter-annotator agreement or annotation-time measurement is reported.
• Applied to 10K SNLI entailment and 10K contradiction hypotheses, GrASP recovered known annotation artifacts with added structure. Examples include an entailment pattern of noun + 'be' + a hypernym of 'outside' at 97% precision, and negative-sentiment verbs correlating with contradiction at 75.7% precision. (Section 6)
  Scope: Hypothesis-only subsets of SNLI entailment vs. contradiction, 200 patterns and alphabet size 200, information gain as selection criterion, patterns kept only at precision ≥75%; precisions are on the training subset, not a held-out split.
• Using the top and bottom 25% of WMT19 English-German quality-estimation sentences as positive and negative sets, GrASP found 60 patterns with precision ≥80% for easy-to-translate inputs. Only 16 patterns above 60% precision were found for hard inputs, indicating challenging inputs are more diverse. (Section 5)
  Scope: 13K automatically translated sentences from one MT model judged by human quality scores, default GrASP hyperparameters, 100 patterns output; recall of the high-precision positive patterns ranges from 5% to 35%, and the data mixes Reviews and IT domains.
• GrASP patterns over WMT19 English-German quality-estimation data independently surfaced translation difficulties already documented in the literature. GrASP dedicated a pattern to the lemma 'be' and found an adjective-noun-noun pattern capturing structural ambiguity such as 'new blog entry'. (Section 5)
  Scope: Qualitative agreement with prior MT analysis for a single MT model on WMT19 en-de quality-estimation data; the patterns were selected by the authors as illustrative, with no systematic recall over the set of known hurdles.
• On the topic-dependent argument mining corpus of 4,065 training and 1,720 test topic-sentence pairs, GrASP's most indicative pattern was the word 'that' in its preposition sense. That matches the known expert indicator of argumentative content. (Section 4)
  Scope: Information gain as selection criterion, 100 patterns, up to 2 gaps allowed, built-in attributes plus a custom binary attribute for lexicon membership of argumentative words; no downstream classification accuracy is reported.
• A single GrASP pattern groups 3 SMS spam messages that share almost no words, such as "awarded a SiPix Digital Camera" and "WIN a FREE Bluetooth Headset". That pattern is a positive-sentiment word followed closely by a determiner and then a proper noun. (Table 1)
  Scope: Illustrative examples from the SMS spam dataset used throughout the paper; no coverage or precision figure is measured for this pattern.
• The GrASP library translates each extracted pattern into an English sentence via templates, so readers without linguistic training can interpret patterns. It renders [[HYPERNYM:communication.n.02], [POS:NUM]] as "A type of communication (n), closely followed by a number". (Section 2)
  Scope: Template-based translation of the built-in English attributes; custom attributes require the user to implement their own explanation function, and no user study of comprehension is reported.
• The GrASP library extends the original 2017 algorithm with user-pluggable pattern-selection criteria and domain-specific custom attributes added by implementing 2 functions. It also adds a limit on gaps between matched tokens that overrides the window size, and a minimum-coverage threshold. (Section 2)
  Scope: The released library's API and hyperparameters; the original algorithm ranked patterns by information gain only, and no experiment isolates the benefit of each added parameter.
• The GrASP web tool renders 4 linked report views, 2 pattern-centric and 2 example-centric. The pattern-centric views give a sortable table of all patterns with coverage, precision, recall and F1 plus the examples each pattern matches, while the example-centric views highlight matched words per example. (Figures 1-4)
  Scope: Flask-based tool consuming the JSON exported by the GrASP library; it can also display output from other pattern-extraction algorithms if formatted into the required JSON schema.

Common misreadings

• GrASP is not a new pattern-learning algorithm: the algorithm dates from Shnarch et al. 2017, and the LREC 2022 contribution is the first public implementation, its extensions and a web exploration tool.
• The 20Newsgroups filtering experiment shows that GrASP helps a human find artifacts, not that automatic pattern-based deletion is the best debiasing method; the authors chose to delete all matched examples for simplicity.
• GrASP patterns are not regular expressions over surface strings: tokens are matched by conjunctions of linguistic attributes such as part-of-speech, hypernym, dependency and sentiment tags, which is what lets one pattern cover very different word sequences.
• The out-of-distribution improvement on the Religion test set is an average of 5 runs with standard deviations up to 0.06, so it should not be read as a tight or guaranteed 5-point gain.
• GrASP requires two labelled sets of texts, a positive and a negative one; the unsupervised single-list setting of GrASP lite is listed as future work, not implemented in the released library.
• The built-in attributes are English-specific even though the algorithm and viewer are language-agnostic; applying GrASP to another language requires the user to write custom attributes.

Terminology in this paper

GrASP pattern

A sequence of slots, each a conjunction of linguistic attributes (e.g. [[SENTIMENT:pos], [POS:det], [POS:propn]]), matching tokens that appear in that order within a window and optionally with a bounded number of gaps between them.

Alphabet (in GrASP)

The set of token-level attributes retained after scoring, from which multi-slot patterns are greedily composed; its size is a hyperparameter of the GrASP library.

Pattern-centric report

A view of extracted patterns organised by pattern: level 1 lists every pattern with its coverage, metric score, precision, recall and F1, and level 2 lists the positive and negative training examples one pattern matches.

Example-centric report

A view of extracted patterns organised by training example: level 1 lists all examples with words matched by positive, negative or both kinds of patterns highlighted, and level 2 lists all patterns matching one example.

Dataset artifact

A token or phrase that is irrelevant to a classification task but frequently appears in examples of some classes, letting a trained model exploit a spurious correlation that does not generalise out of distribution.

Custom attribute

A user-defined token annotation added to GrASP by subclassing CustomAttribute and implementing 2 functions, one extracting the attribute from an input text and one producing its natural-language explanation.

How to cite

@inproceedings{DBLP:conf/lrec/Lertvittayakumjorn22,author       = {Piyawat Lertvittayakumjorn and
                  Leshem Choshen and
                  Eyal Shnarch and
                  Francesca Toni},
  editor       = {Nicoletta Calzolari and
                  Fr{\'{e}}d{\'{e}}ric B{\'{e}}chet and
                  Philippe Blache and
                  Khalid Choukri and
                  Christopher Cieri and
                  Thierry Declerck and
                  Sara Goggi and
                  Hitoshi Isahara and
                  Bente Maegaard and
                  Joseph Mariani and
                  H{\'{e}}l{\`{e}}ne Mazo and
                  Jan Odijk and
                  Stelios Piperidis},
  title        = {GrASP: {A} Library for Extracting and Exploring Human-Interpretable
                  Textual Patterns},
  booktitle    = {Proceedings of the Thirteenth Language Resources and Evaluation Conference,
                  {LREC} 2022, Marseille, France, 20-25 June 2022},
  pages        = {6093--6103},
  publisher    = {European Language Resources Association},
  year         = {2022},
  url          = {https://aclanthology.org/2022.lrec-1.655},
  timestamp    = {Mon, 10 Oct 2022 16:57:52 +0200},
  biburl       = {https://dblp.org/rec/conf/lrec/Lertvittayakumjorn22.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

References

See the full reference list in the paper.