Introduction
In the field of Open Information Extraction (IE), systems extract millions of relational triples from the web, such as <George Washington, was born in, Virginia>. However, to transform this raw data into actionable knowledge, systems must understand the logical properties of these relations. A critical property is functionality: a relation is functional if a subject (arg1) maps to exactly one unique object (arg2). For example, "was born in" is functional, whereas "visited" is not.
Presented at EMNLP 2010, the LEIBNIZ system was developed to automatically identify functional relations in web text. By distinguishing functional from non-functional relations, LEIBNIZ enables more accurate contradiction detection and synonym resolution in natural language processing tasks.
The Challenge of Functionality
Identifying functionality automatically is surprisingly difficult due to several linguistic phenomena:
- Synonymy: "Windy City" and "Chicago" refer to the same entity but appear as different strings.
- Anaphora: A text might refer to a birthplace as "Virginia" and later as "a town."
- Ambiguity: Proper nouns like "Clinton" can refer to multiple distinct individuals.
- Type Restrictions: Functionality often depends on the data type. For instance, "published in" is functional for years but non-functional for languages.
The LEIBNIZ System Architecture
LEIBNIZ addresses these challenges by combining statistical distribution analysis with "clean" data from external knowledge bases. The system processes assertions extracted from a massive web corpus and validates them against structured data.
Algorithmic Components
The authors propose three distinct algorithmic approaches that culminate in the hybrid LEIBNIZ system:
1. Instance Based Counting (IBC)
This baseline approach uses heuristic rules to "clean" data (e.g., focusing on proper nouns) and performs equality checking to determine if different strings likely refer to the same entity. While simple, it struggles with the inherent noise of web text.
2. DISTRDIFF (Distributional Difference)
DISTRDIFF is a purely statistical approach that analyzes the "rank-frequency" distribution of objects for various subjects. Functional relations typically exhibit a sharp drop-off—usually only one object is observed—while non-functional relations have a flatter curve. The system uses KL-divergence to compare a relation's distribution against known "average" templates.
3. CLEANLISTS
This is the most successful component of the system. It intersects the noisy web corpus with "clean" entity lists from Freebase. By focusing on arguments that match known, typed entities (such as "Cities" or "Years"), it effectively bypasses the problems of synonymy and anaphora.
Key Results and Insights
LEIBNIZ represents a significant leap in performance over previous methods. It achieved an Area Under the Curve (AUC) of 0.88, compared to the 0.61 scored by the previous state-of-the-art system, AuContraire.
Key insights from the study include:
- Type-Dependency: Functionality is often a property of a typed relation rather than just a phrase. LEIBNIZ successfully identified that "was published in" is functional when the object is a Year but non-functional when it is a Language.
- Textual Functionality: Some relations are logically non-functional but appear functional in text because authors typically only mention the most prominent value (e.g., "collects").
- Hybrid Strength: LEIBNIZ uses CLEANLISTS for high precision and "backs off" to the statistical DISTRDIFF method when knowledge base data is insufficient.
Conclusion
By combining the breadth of web-scale extraction with the precision of structured knowledge bases, LEIBNIZ provides a robust framework for identifying functional relations. Future work may apply these principles to identify other relational properties, such as transitivity or symmetry, further enhancing the reasoning capabilities of Open IE systems.
Summary updated