Embedding Grammars

David Wingate, William Myers, Nancy Fulda, Tyler EtchartarXiv 2018 · arXiv

TL;DR

This paper introduces "embedding grammars," a hybrid framework that blends the structural precision of context-free grammars and regular expressions with the semantic generalization of word embeddings. By matching flexible regions in a continuous vector space rather than requiring exact string matches, it allows developers to write compact rules that automatically capture synonyms and related concepts without manual enumeration.

What Problem Does This Paper Address?

Traditional rule-based text processing tools, such as regular expressions (regex) and context-free grammars (CFGs), are staples in natural language processing for tasks like intent detection. However, they are inherently brittle because they operate purely at a structural level—words must match exactly.

If a developer wants to detect a compliment, they might write a regex like (you are) (beautiful|gorgeous|cute). If a user inputs "you are lovely," the match fails. To fix this, developers are forced to manually brainstorm and maintain exhaustive lists of synonyms. This creates a massive cognitive burden and limits the application's capability to the developer's explicit vocabulary. The authors address this challenge by injecting semantic awareness directly into structural grammars.

Methods

The authors propose replacing discrete terminal symbols (exact words) in a grammar with continuous subregions within a word embedding space. Instead of defining an exhaustive list of terms, a grammar designer provides a few exemplars. The system then automatically maps these exemplars into a vector space and constructs a matching region.

The paper outlines four potential techniques for defining these matching regions:

  1. Bounding Box: A naive approach taking the geometric bounding box of exemplars (yields poor results).
  2. Epsilon Ball: Finding the centroid of the exemplar set and matching any word within a predefined cosine distance ($\epsilon$).
  3. Covariance Subspace: Utilizing a Mahalanobis distance metric based on the empirical covariance of the exemplars.
  4. Neighbor Expansion: The most successful method, which creates an individual epsilon ball around each exemplar. This "many-bubbles" approach considers a token a match if it falls near any single exemplar.

The authors implemented this as a Python wrapper (regexv) that intercepts and expands queries before passing them to Python’s native re package. Multi-word phrases are handled compositionally by averaging the vectors of their individual words.

Datasets

The framework relies on pre-trained 300-dimensional fastText embeddings trained on a Wikipedia corpus. For evaluation and expansion generation, the authors utilized a vocabulary consisting of the 500,000 most common tokens in the English fastText corpus. No new benchmark datasets were introduced, as the paper focuses on a architectural proof-of-concept.

Key Insights and Ideas

  • The "Many-Bubbles" Superiority: Intuitively, one might expect that accounting for vector space geometry via a covariance subspace (Mahalanobis distance) would yield the best semantic regions. Surprisingly, the simpler "neighbor expansion" method performed significantly better in practice.
  • Syntax Acts as a Natural Filter: A common worry with semantic expansion is that it might introduce noise or grammatically incorrect words (e.g., expanding "mother" to "widowed" or "motherly"). However, the rigid structure of the surrounding grammar naturally filters these out, because human text rarely contains syntactically implausible phrases like "Your widowed was a hamster".
  • Vector Averaging for Phrases is Effective: Despite throwing away word order, simply averaging word vectors proved remarkably effective for phrase matching. For instance, combining the vectors for "clever" and "man" naturally yielded a vector highly similar to "genius".

Key Results

Using a strict cosine distance threshold of $\epsilon = 0.35$ to ensure strong semantic similarity, the authors demonstrated that embedding grammars successfully generalize simple rules into rich semantic patterns.

As shown in Figure 1, a grammar based on a famous Monty Python quote automatically expanded single exemplars like "mother", "hamster", and "elderberries" into broad, relevant categories of familial relationships, rodents, and fruits.

Figure 1: Sample regexv expansions obtained using the 500,000 most common tokens in the English- language fastText corpus. Matches were selected using the neighbor expansion method with ϵ=0.35.

Additionally, the compositional phrase matching aligned closely with human intuition. As detailed in the paper's experimental table, the phrase "a guy who knows everything" mapped closely to the exemplar "genius" (cosine distance of 0.5060) but remained distant from unrelated concepts like "porsche" (cosine distance of 0.7767).

Cosine distances between compositional phrase vectors and single-word exemplars.

Limitations and Future Work

  • The Antonym Problem: Because word embeddings group words based on contextual distribution, polar opposites (e.g., hot/cold, happy/sad, beautiful/ugly) frequently appear in identical contexts. Consequently, they fall within the same semantic regions, leading to potential false positives.
  • Polysemy: The current implementation lacks word-sense disambiguation and cannot inherently distinguish between different meanings of the same word (e.g., "bank" as a riverbank vs. a financial institution).
  • Future Directions: The authors propose extending this framework to Probabilistic Context-Free Grammars (PCFGs). By replacing hard boundary regions with "soft matches" (such as Gaussian distributions), embedding grammars could be integrated into fully probabilistic grammar learning algorithms.

Summary updated

Abstract

Classic grammars and regular expressions can be used for a variety of purposes, including parsing, intent detection, and matching. However, the comparisons are performed at a structural level, with constituent elements (words or characters) matched exactly. Recent advances in word embeddings show that semantically related words share common features in a vector-space representation, suggesting the possibility of a hybrid grammar and word embedding. In this paper, we blend the structure of standard context-free grammars with the semantic generalization capabilities of word embeddings to create hybrid semantic grammars. These semantic grammars generalize the specific terminals used by the programmer to other words and phrases with related meanings, allowing the construction of compact grammars that match an entire region of the vector space rather than matching specific elements.
BibTeX
@misc{wingate2018embedding,
  author = {David Wingate and William Myers and Nancy Fulda and Tyler Etchart},
  title = {{Embedding Grammars}},
  year = {2018},
  eprint = {1808.04891},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1808.04891},
}
Figure