Mapping Multilingual Hierarchies Using Relaxation Labeling

Jordi Daudé, Lluís Padró, German Rigau

TL;DR

This paper presents a novel method for automatically linking existing lexical hierarchies across languages, specifically mapping Spanish taxonomy fragments to the English WordNet. By employing a constraint satisfaction algorithm called relaxation labeling, the approach achieves over 80% accuracy in identifying the correct English synsets for Spanish senses, even with significant ambiguity. This work offers a robust, generalizable technique for building richer, multilingual lexical resources.

What Problem Does This Paper Address?

The development of robust Natural Language Processing (NLP) applications increasingly relies on comprehensive, multilingual lexical and semantic resources. However, creating and maintaining these resources is a significant challenge. Existing efforts often focus on building large, single-language knowledge bases or attempting to link them using bilingual dictionaries. This paper tackles the problem of automatically merging already existing lexical hierarchies from different languages. Specifically, it addresses the challenge of accurately mapping senses from a Spanish taxonomy, derived from a monolingual dictionary, to the appropriate synsets within the English WordNet. This mapping is crucial for enabling cross-lingual NLP tasks and enriching existing knowledge bases.

Methods

The core of the paper's methodology is the application of Relaxation Labeling (RL), a constraint satisfaction algorithm. RL iteratively refines a "label assignment" for a set of variables by considering local information and compatibility constraints.

Here's how it's applied:

  • Variables: Each "sense" in the Spanish taxonomy is treated as a variable.
  • Labels: The possible labels for each Spanish sense are the WordNet synsets that contain a word which is a potential translation of the Spanish sense, as identified by a bilingual dictionary.
  • Constraints: The key innovation lies in the definition of constraints that guide the RL process. These constraints leverage the hypernym/hyponym relationships within both the Spanish taxonomy and WordNet. The algorithm increases the "weight" (confidence) of a connection between a Spanish sense and a WordNet synset if their respective hypernyms or hyponyms are also connected in a compatible way. Various types of constraints are defined (e.g., iie, iae, aae) to capture direct or indirect hyper/hyponym matches, allowing for recursive matching within one or both taxonomies.
  • Algorithm Flow:
    1. Initialize random weights for each possible sense-synset assignment.
  • Compute the "support" for each label (synset) based on the constraints and current weights of related variables.
  • Adjust weights: increase weights for labels with high support, decrease for low support.
  • Repeat until convergence (no significant weight changes).

This approach is novel in its systematic use of hierarchical relationships as constraints for mapping between distinct, pre-existing lexical structures.

Datasets

  • Spanish Taxonomies: Automatically acquired from a monolingual Spanish dictionary (DGILE). Experiments were conducted on both original taxonomies and modified versions (+top, no-senses) to test robustness.
  • English WordNet: The target lexical resource for mapping.
  • Bilingual Dictionaries: An integration of several sources was used to establish candidate translations between Spanish and English words. This multi-source dictionary contained approximately 124,949 translations.

The paper does not introduce new benchmark datasets but rather uses existing resources to evaluate its novel mapping technique.

Key Insights and Ideas

  • Leveraging Hierarchy is Powerful: The success of the method hinges on the observation that hypernym/hyponym relationships within taxonomies provide strong, albeit local, signals for cross-lingual mapping. Propagating these local signals through the RL algorithm leads to a globally consistent and accurate mapping.
  • Robustness to Noise: The method demonstrates resilience to noise introduced by the automatic acquisition of taxonomies and the inherent ambiguity of bilingual dictionaries (translating words, not senses). The RL framework can effectively filter out incorrect connections by favoring those that are structurally consistent.
  • Generalizability: While applied to Spanish-English mapping, the RL framework and the use of hierarchical constraints are generalizable to other language pairs and other types of lexical hierarchies.
  • Beyond Direct Matches: The use of "ancestor/descendant" constraints (aae, iae) is crucial for handling cases where direct hypernyms don't align perfectly, allowing for more flexible and accurate mappings.

Key Results

The paper reports an accuracy of over 80% for the mapping task.

  • Coverage: Table 3 shows that the aa* constraint set (allowing recursion on both sides) provides the highest coverage, meaning it can establish connections for a larger percentage of nodes. For example, in noun.communication, aa* covers 59% of nodes with bilingual connections.
  • Precision: Tables 4 and 5 present precision results. For polysemic words (words with multiple candidate translations), the precision for the TOK, FOK (well-built Spanish taxonomy, correctly assigned semantic file) case is high, reaching up to 90% for animal and 94% for food. Even when the Spanish taxonomy was wrongly assigned (TOK, FNOK), the algorithm could still achieve high precision by leveraging WordNet's global structure.
  • Average Polysemy: The average number of candidate connections per Spanish sense is 15.8, highlighting the challenge of disambiguation.

Limitations and Future Work

Limitations:

  • Noise in Input: The accuracy of the method is influenced by the quality of the automatically acquired Spanish taxonomies and the coverage/noise in the bilingual dictionaries.
  • Focus on Hyper/Hyponymy: The current constraints primarily rely on hyper/hyponym relationships.

Future Work:

  • Broader Constraint Set: Incorporate other lexical relationships like sibling, cousin, synonymy, and meronymy to further improve accuracy.
  • Enriching EuroWordNet: Apply the technique to enrich the Spanish part of EuroWordNet and potentially include other languages.
  • Inferring Candidates: Develop methods to infer candidate translations when bilingual dictionaries have low coverage.
  • Sense Disambiguation: Use the mapping to disambiguate senses within the Spanish taxonomy itself.
  • Updating Lexical Resources: The technique can be used to update existing lexical resources, such as mapping WN1.5 to WN1.6.

Summary updated

BibTeX
@inproceedings{daude1999mapping,
  author = {Jordi Daudé and Lluís Padró and German Rigau},
  title = {{Mapping Multilingual Hierarchies Using Relaxation Labeling}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {1999},
  url = {https://openreview.net/forum?id=ei7oH97Chl},
}

Loading related content...

Figure