Extracting Word Sequence Correspondences with Support Vector Machines

Kengo Sato, Hiroaki SaitoCOLING 2002

TL;DR

This paper introduces a novel method for automatically extracting bilingual word sequence correspondences (translation pairs) from non-aligned parallel corpora using Support Vector Machines (SVMs). By leveraging a rich set of features and the generalization power of SVMs, the approach significantly reduces the manual effort required for creating translation dictionaries.

What Problem Does This Paper Address?

Creating comprehensive translation dictionaries for natural language processing tasks, especially machine translation, is a labor-intensive and time-consuming process. Manual creation is prone to inconsistencies and requires significant human effort. While automatic methods for extracting translation pairs from parallel corpora exist, many rely on sentence alignments, which are not always available or easy to obtain. This paper tackles the challenge of extracting these correspondences from non-aligned parallel corpora, aiming to make the process more efficient and broadly applicable.

Methods

The core of the proposed method lies in using Support Vector Machines (SVMs) for learning and extracting word sequence correspondences. SVMs are chosen for their strong generalization capabilities, resistance to overfitting, and ability to learn non-linear decision boundaries through kernel functions.

The process involves three main steps:

  1. Learning the Translation Model:
    • Training Data: Manually created positive (translation pairs) and negative (non-translation pairs) samples are generated from the training corpora.
  2. Feature Engineering: These samples are converted into feature vectors using a comprehensive set of features designed to capture various aspects of word sequences. These features include:
  3. Existing Translation Dictionary: Bilingual word pairs directly present in the candidate or co-occurring in the context.
  4. Word Count: Number of words in Japanese and English phrases.
  5. Part-of-Speech (POS): Ratios of nouns, verbs, adjectives, and adverbs.
  6. Constituent Words: Presence of specific content words.
  7. Neighbor Words: Words appearing immediately before or after the candidate phrase.
  8. SVM Training: An SVM classifier is trained on these feature vectors to learn the optimal parameters for distinguishing translation pairs from non-translation pairs.
  9. Making Candidate Translation Pairs:
    • Phrases are extracted from both Japanese and English sentences using parsing.
  10. Combinations of these phrases are formed to create a set of candidate translation pairs. This step does not require sentence alignment. To manage the combinatorial explosion, only noun and verb phrases within a certain word count limit are considered.
  11. Extracting Translation Pairs:
    • The candidate translation pairs are converted into feature vectors using the same features as in the training phase.
  12. These feature vectors are then fed into the trained SVM model. The SVM outputs a score (+1 or -1), classifying the candidate as either a translation pair or not.

The paper also details the mathematical formulation of SVMs, including the optimization problem, the role of Lagrange multipliers, slack variables for handling non-linearly separable data, and the use of kernel functions (specifically mentioning polynomial and Gaussian kernels) to map data into higher dimensions for non-linear separation.

Datasets

  • English Business Letter Example Collection: This collection, published by Nihon Keizai Shimbun Inc., was used as the parallel corpus. It contains Japanese and English sentences from business letters, with pre-marked translation pairs.
  • EDICT: A bilingual dictionary containing 94,511 word pairs was used for feature extraction.
  • Custom Lexicons: 1,009 Japanese and 890 English words that appeared more than 3 times in the training corpora were used for specific features.

The paper used 1,000 sentences for both training and testing. Candidate translation pairs were generated by parsing Japanese sentences with KNP and English sentences with Apple Pie Parser. Negative samples were randomly chosen from phrase combinations with fewer than 8 constituent words.

Key Insights and Ideas

  • SVMs for Non-Aligned Corpora: The paper demonstrates the effectiveness of SVMs in extracting translation pairs from non-aligned corpora, a significant advantage over methods requiring sentence alignments.
  • Rich Feature Set: The comprehensive set of features, especially those leveraging existing translation dictionaries (both direct matches and co-occurrences), proved crucial for high performance. This highlights the importance of incorporating external linguistic knowledge.
  • Contextual Clues are Important: Features related to co-occurring words in the context of a candidate pair (feature 1b) are shown to be highly effective, suggesting that the surrounding words provide valuable clues for translation.
  • Generalization Power: SVMs' ability to generalize well from limited training data and avoid overfitting is key to their success in this task.
  • Reducing Manual Effort: The method offers a practical way to significantly reduce the cost and labor associated with creating translation dictionaries.

Key Results

  • High Precision and Recall: The proposed method achieved an 81.1% precision rate and a 69.0% recall rate on the extracted translation pairs using Japanese and English parallel corpora.
  • Feature Importance: Removing features related to the translation dictionary (1a, 1b) caused the largest drop in precision. Removing features related to word count (2a, 2b) led to a significant drop in recall, suggesting their importance for coverage.
  • Scalability: The experiments showed that increasing the number of training samples improved recall, while increasing the size of the bilingual dictionary improved precision, up to a certain point.

Limitations and Future Work

  • Manual Sample Creation: The method still requires manual creation of positive and negative training samples, although the goal is to minimize this effort.
  • Candidate Generation: The candidate generation process can lead to a very large set of potential pairs, which might be computationally intensive. The paper limits this by considering only noun and verb phrases.
  • Future Work: The authors suggest that further improvements can be made by adding new features to the translation model, leveraging the statistical machine learning approach. They also note that once a translation model is learned, it doesn't need to be relearned for new samples, unlike some other methods.

Summary updated

BibTeX
@inproceedings{sato2002extracting,
  author = {Kengo Sato and Hiroaki Saito},
  title = {{Extracting Word Sequence Correspondences with Support Vector Machines}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2002},
}

Loading related content...

Figure