Semantic Tagging using a Probabilistic Context Free Grammar

Michael Collins, Michael Collins 0001, Scott MillerVLC @ COLING 1998

TL;DR

This paper introduces a statistical approach for "semantic tagging" – identifying key information like job titles and people involved in management succession events within sentences. Their novel Probabilistic Context-Free Grammar (PCFG) model achieves high accuracy (up to 87.8%) with limited resources, outperforming traditional rule-based systems and simpler finite-state models.

What Problem Does This Paper Address?

Information Extraction (IE) systems aim to pull structured data from unstructured text. A crucial first step in IE is "semantic tagging," which involves identifying specific events and their participants within a sentence. The authors focus on the management succession domain, where the goal is to extract who took a position, who left it, and what the position was. Traditional IE systems often rely on hand-coded rules, which are time-consuming to develop, require significant expertise, and are difficult to adapt to new domains. This paper addresses the need for a more robust, data-driven, and adaptable machine learning approach to this sentence-level semantic tagging task.

Methods

The core of the paper is a statistical model based on a Probabilistic Context-Free Grammar (PCFG). Unlike simpler finite-state models that make a Markov assumption (each tag depends only on the previous one), the PCFG allows for a more flexible and richer representation of the dependencies between different parts of the sentence and the semantic roles they play.

Here's a breakdown of their approach:

  • Probabilistic Context-Free Grammar (PCFG): The model uses a PCFG to define the probability of generating a sequence of semantic tags (like IN, OUT, POST, INDICATOR) and associated words. This allows for modeling complex relationships that finite-state models struggle with, such as the dependence of indicator words on the template type and the order of slots.
  • Tree Structure Derivation: The PCFG grammar is designed to generate a tree structure that represents the semantic tagging. This structure is deterministically derived from annotated training sentences, where slots and indicators are explicitly marked.
  • Leaf Categories: The model uses a set of pre-terminal labels (leaf categories) that go beyond just the core slots (IN, OUT, POST) and indicator (IND). These include labels for noise words (PREN, POSTN, NOISE), prepositions (I.Prep, O.Prep, P.Prep), and the indicator itself (IND(class)).
  • CKY Algorithm: A variant of the CKY dynamic programming algorithm is used for efficient decoding, allowing the model to find the most likely parse tree (and thus the most likely semantic tagging) for a given sentence.
  • Limited Resources: A key advantage is that the system requires only a part-of-speech tagger and a morphological analyzer, making it relatively lightweight compared to systems needing full syntactic parsers.

Datasets

The authors trained their model on 563 sentences and tested it on 356 sentences. These sentences were sourced from the "Who's News" section of the Wall Street Journal, a corpus rich in management succession events. The annotation for this data was part of a larger effort that also included coreference resolution and complete output template generation, providing a comprehensive ground truth.

Key Insights and Ideas

  • PCFG Superiority over Finite-State Models: The paper strongly argues that for semantic tagging, a PCFG offers a significantly better parameterization than finite-state models. This is because PCFGs can capture more complex dependencies, such as the relationship between indicator words and the specific slots being filled, and the variable ordering of these slots.
  • Data-Driven Rule Induction: The PCFG grammar rules are not hand-coded but are learned automatically from annotated training data. This makes the system adaptable to new domains with minimal manual effort, as long as labeled data is available.
  • Handling Multiple Indicators: The paper addresses a practical challenge: sentences often contain multiple indicators for different events. Their solution is to transform such sentences into multiple single-event sentences for training and testing, a simple yet effective preprocessing step.
  • Importance of Contextual Information: The model's success hinges on capturing contextual cues. For instance, the choice of indicator word is highly dependent on the template (e.g., "named" for {I,P} vs. "succeed" for {I,O,P}), and prepositions often signal specific slots.

Key Results

The model achieved impressive results on the management succession task:

  • Accuracy:
    • 77.5% accuracy when partial slot matches are considered incorrect.
  • 87.8% accuracy when partial slot matches are considered correct.
  • F-Measure: An F-measure of 82.6% (with partial matches scored at 0.5) and 87.8% (with partial matches scored at 1.0) was reported.
  • Training Data: The model was trained on a relatively small dataset of 560 sentences.
  • Resource Efficiency: The system requires only a POS tagger and morphological analyzer, demonstrating efficiency in terms of required linguistic resources.

Limitations and Future Work

  • False Positives: The current model assumes that test sentences are marked with indicators that have one or more slots. The paper acknowledges that a more robust system would need to handle "false positives" – potential indicators that don't actually signal an event. Future work could involve word-sense disambiguation or extending the model to include an "empty template" option.
  • Syntactic Parsing: The authors note that a significant portion of errors fall into the "semantically plausible but syntactically impossible" category. They suggest that integrating a full syntactic parser or a system that jointly recovers syntactic structure and semantic labels (like BBN's SIFT system) could drastically improve performance.
  • Complete IE Task: This work focuses solely on sentence-level semantic tagging. The authors propose extending the framework to encompass the entire IE pipeline, including coreference resolution and template merging, by developing an "information production" model that mirrors how text is generated.

Summary updated

BibTeX
@inproceedings{collins1998semantic,
  author = {Michael Collins and Michael Collins and Scott Miller},
  title = {{Semantic Tagging using a Probabilistic Context Free Grammar}},
  booktitle = {VLC @ COLING},
  year = {1998},
}

Loading related content...

Figure