Feasibility Study for Ellipsis Resolution in Dialogues by Machine-Learning Technique

Kazuhide Yamamoto, Eiichiro SumitaACL 1998

TL;DR

This paper explores using machine learning, specifically decision trees, to automatically resolve missing grammatical elements (ellipses) in Japanese dialogues. They demonstrate that this approach can achieve high accuracy, particularly for indirect objects, and identify key factors like topic dependency and grammatical case that influence resolution performance.

What Problem Does This Paper Address?

In many languages, including Japanese, subjects, objects, and other grammatical roles can be omitted from sentences when they are understood from context. This is known as ellipsis. For machine translation and natural language processing tasks like information extraction, resolving these ellipses is crucial because target languages (like English) often require explicit mention of these elements. While theoretical approaches like centering theory exist, they struggle with complex sentences. Empirical approaches have been proposed, but often require manual effort in scoring or constraint selection. This paper aims to address the challenge of automatically and accurately resolving various types of ellipses in Japanese dialogues using a data-driven, machine-learning technique.

Methods

The core of this paper's approach is the application of a machine-learning algorithm to build a decision tree for ellipsis resolution. Specifically, they use the C4.5 algorithm, a well-known classifier that generates binary decision trees. The process involves:

  1. Feature Engineering: Identifying and selecting relevant attributes (features) that help predict the missing grammatical element. These attributes are categorized into:
  2. Exophoric information: Speaker's social role (e.g., customer/clerk).
  3. Topic-dependent information: Predicates and their semantic categories.
  4. Topic-independent information: Functional words expressing tense, modality, etc. They also consider positional information for these attributes relative to the target predicate.

  5. Decision Tree Training: Using a corpus of Japanese dialogues, they train the C4.5 algorithm to construct a decision tree. This tree acts as the actual ellipsis resolver.

  6. Evaluation: The performance of the trained decision trees is evaluated using F-measure, a metric that combines precision and recall.

Datasets

  • Training and Test Data: The primary dataset used is a corpus of Japanese dialogues. The authors mention utilizing the ATR travel arrangement corpus for specific experiments on topic dependency.
  • Data Size Experiment: They trained decision trees with varying numbers of dialogues (25, 50, 100, 200, 400) and tested on 100 unseen dialogues containing 1685 subject ellipses.
  • Topic Dependency Experiment: Fifty dialogues were randomly chosen from the corpus for each of four topic categories (hotel reservation, service inquiry, other hotel arrangements, other travel arrangements) for training. The same 100 unseen dialogues from the training-size experiment were used for testing.
  • Surface Case Experiment: 300 training dialogues and 100 unseen test dialogues were used to evaluate performance across different grammatical cases.

Key Insights and Ideas

  • Machine Learning for Ellipsis Resolution is Feasible: The study demonstrates that a machine-learning approach, specifically decision trees, can effectively resolve various types of ellipses in Japanese dialogues, achieving high accuracy.
  • Topic Dependency Matters: Performance significantly improves when the training data's topic aligns with the test data's topic. This suggests that for optimal performance, training should be focused on relevant topics, or a broad range of topics should be covered if the topic is unknown.
  • Grammatical Case Influences Attribute Importance: The attributes most crucial for resolving ellipses vary depending on the grammatical case (e.g., 'ga', 'wo', 'ni'). This highlights the need for case-specific considerations in feature selection.
  • Topic-Independent Attributes Become More Important with More Data: As the amount of training data increases, more general, topic-independent attributes (like certain auxiliary verbs) become more prominent in the decision trees.
  • Compact Trees Lead to Better Performance: Shallower decision trees generally correlate with better resolver performance, suggesting that simpler models are more effective at characterizing ellipsis types.

Key Results

  • High Accuracy Achieved: The proposed method achieved a resolution accuracy of 91.7% for indirect objects ('ni' case) and 78.7% for subjects with verb predicates ('ga(v.)' case).
  • Performance Improves with Data Size: Accuracy consistently increases with the number of training dialogues, though the rate of improvement decelerates. The authors suggest that around 10^4 to 10^5 training samples might be sufficient for this task, with an expected performance ceiling of 80-85%.
  • Topic-Specific Training Yields Higher Accuracy: When training and test topics coincide, accuracy is significantly higher. For example, training on the 'R' (Other travel arrangements) topic yielded the highest accuracy (69.9%) when tested on 'R' samples.
  • 'ni' Case Resolution is Particularly Effective: The 'ni' case (indirect object) showed satisfactory performance, likely because indirect objects often refer to exophoric persons, which the decision tree approach is well-suited to handle.
  • 'wo' Case Ellipses are Often Anaphoric: Over 90% of 'wo' case ellipses were tagged as anaphoric, suggesting that while their resolution might be complex, their anaphoric nature can be readily identified.

Limitations and Future Work

  • Data Size and Performance Plateau: While performance improves with data, it appears to plateau, suggesting a limit to the current approach's effectiveness. Further improvement might require more sophisticated features or different modeling techniques.
  • Focus on Exophoric Ellipses: The paper primarily focuses on exophoric ellipses (those referring to entities outside the immediate sentence) and does not delve into resolving the antecedents of endophoric ellipses (those referring to entities within the discourse).
  • Limited Scope of Attributes: While a range of attributes were explored, future work could investigate more sophisticated features, including deeper semantic information or discourse-level context.
  • Applicability to Other Languages: The authors suggest that the approach could be applicable to other languages with similar ellipsis phenomena, such as Korean.
  • Contextual Ellipses: The paper acknowledges that many ellipses in spoken dialogues are anaphoric, particularly in the 'wo' case. Future work will explore contextual ellipses more deeply.

Summary updated

BibTeX
@inproceedings{yamamoto1998feasibility,
  author = {Kazuhide Yamamoto and Eiichiro Sumita},
  title = {{Feasibility Study for Ellipsis Resolution in Dialogues by Machine-Learning Technique}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1998},
}
Figure