Acquiring Hyponymy Relations from Web Documents

Keiji Shinzato, Kentaro TorisawaNAACL 2004

TL;DR

This paper introduces a novel method for automatically extracting "is-a" (hyponymy) relationships from web documents, moving beyond traditional pattern-matching approaches. By leveraging HTML structure, document frequencies, and semantic similarity, the method achieves higher precision and can discover relationships missed by existing techniques, particularly with limited data.

What Problem Does This Paper Address?

Automatically identifying hyponymy relations (e.g., "a Toyota is a car," "a novel is a type of book") is crucial for many Natural Language Processing (NLP) tasks like information retrieval, question answering, and knowledge base construction. Existing methods often rely on specific linguistic patterns (e.g., "NP such as NP") which are infrequent in real-world text, limiting their coverage. This paper aims to overcome this limitation by developing a more robust method that can extract hyponymy relations from a wider range of expressions, even when these explicit patterns are absent.

Methods

The proposed acquisition algorithm consists of four main steps:

  1. Extraction of Hyponym Candidates from Itemizations: The core idea here is to leverage the structure of HTML documents. The method identifies lists and itemized sections (like <ul> and <li> tags) and treats the items within these lists as potential hyponyms that share a common hypernym. For example, in a list of car manufacturers, "Toyota," "Honda," and "Nissan" are extracted as hyponym candidates.
  2. Selection of a Hypernym Candidate using DF and IDF: For each set of hyponym candidates (an HCS), the method searches for a common hypernym. It downloads documents containing these hyponyms and uses statistical measures like Document Frequency (DF) and Inverse Document Frequency (IDF) to score potential hypernym nouns. A noun that appears frequently in documents related to the hyponyms but is relatively rare in the general web corpus is favored. This step aims to generalize across multiple hyponyms.
  3. Ranking of Hypernym Candidates and HCSs by Semantic Similarity: To filter out non-hypernyms that might be statistically associated (e.g., "price" for "Toyota" and "Honda"), this step computes semantic similarity. It uses co-occurrence vectors derived from verb argument structures in parsed texts to represent both the hyponym candidates and potential hypernyms. The similarity is measured using cosine similarity. Pairs with higher semantic similarity are ranked higher.
  4. Application of Heuristic Rules: Finally, several heuristic rules are applied to refine the results:
  5. Rule 1: Discards pairs where the hypernym candidate appears in fewer documents than the sum of its hyponyms.
  6. Rule 2: Filters out cases where the hypernym candidate is a substring of a hyponym but not a suffix, or if it's a suffix but not shared by a sufficient portion of the HCS.
  7. Rule 3: Specifically handles place names, replacing hypernyms like "Japan" for "Kyoto" and "Tokyo" with the more general "place name."

Datasets

  • Global Document Set: Approximately 1.00 × 10⁶ HTML documents (1.26 GB without HTML tags) were used as a general corpus to calculate IDF scores.
  • Local Document Sets: For each HCS, the top 100 documents (or fewer if less were found) from search engine rankings were downloaded.
  • Test Set: 2,000 HCSs were randomly selected from the extracted HCSs for evaluation.
  • Development Set: Approximately 4,000 HCSs were used to develop the algorithm and heuristic rules.
  • Japanese Newspaper Corpora: Data from Yomiuri, Mainichi, and Nikkei newspapers (1987-2001, 1991-1999, 1983-1990 respectively; 3.01 GB total) were used for verb-noun co-occurrence analysis.

Key Insights and Ideas

  • Leveraging HTML Structure is Powerful: Itemized lists in HTML provide a surprisingly rich source of hyponym candidates, even without explicit linguistic patterns. This is a key departure from prior work.
  • DF/IDF for Generalization: Using document frequencies (DF/IDF) helps in selecting hypernyms that are broadly associated with a set of hyponyms, rather than being overly specific to one.
  • Semantic Similarity is Crucial for Precision: Statistical association alone isn't enough. Semantic similarity measures are essential to filter out spurious relationships and improve the accuracy of identified hypernyms.
  • Heuristics are Necessary for Refinement: While the core method is strong, specific heuristic rules are vital for handling edge cases, particularly with place names and substring relationships, leading to a significant boost in precision.
  • "tf" vs. "df" for Hypernym Selection: The paper found that using DF for hypernym selection (Step 2) performed better than using term frequency (tf) within local documents.

Key Results

  • The proposed method achieved a precision of about 75% for 701 hyponym candidates (approximately 5% of all candidates) and 61% for 1398 hyponym candidates (about 10% of all candidates) when considering the top-ranked pairs.
  • Each step of the algorithm (Steps 2, 3, and 4) contributed to improved accuracy.
  • The method demonstrated effectiveness in acquiring a significant number of hypernyms that alternative methods could not, especially when using a limited amount of text (e.g., 100 documents per hyponym candidate).
  • The DF-based approach for hypernym selection (Step 2) outperformed a TF-based alternative.

Limitations and Future Work

  • Precision vs. Recall: The paper focuses on precision, and while it achieves good results, it acknowledges that a significant portion of potential hypernym-hyponym pairs are discarded (e.g., only the top 200 pairs out of 2,000 were considered in some evaluations).
  • Multi-word Hypernyms: The current method primarily extracts single-word hypernyms (e.g., "company"). The authors express interest in extending the method to handle multi-word hypernyms like "automobile manufacturer" for richer information.
  • Comparison with More Texts: The authors note that the performance gap with some alternative methods (like lexicosyntactic patterns) might shrink if those methods were given significantly more text, but this is computationally challenging.
  • Combining Methods: Exploring optimal ways to combine the proposed method with other techniques is suggested as future work.

Summary updated

BibTeX
@inproceedings{shinzato2004acquiring,
  author = {Keiji Shinzato and Kentaro Torisawa},
  title = {{Acquiring Hyponymy Relations from Web Documents}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2004},
}
Figure