PaperlayerView exact revision on arXiv

Source-linked AI summary

A* CCG Parsing with a Supertag and Dependency Factored Model

Masashi Yoshikawa, Hiroshi Noji, Yuji Matsumoto

arXiv:1704.06936v1cs.CL

TL;DR

CCG supertags resolve much syntactic ambiguity, but identical supertag sequences can still produce different attachments. The paper adds bi-LSTM-based dependency factors to A* parsing, preserving precomputable local scores and reporting state-of-the-art English and Japanese results.

  • Problem

    Category-only CCG parsing leaves attachment ambiguities that deterministic heuristics do not always resolve correctly.

  • Method

    The model jointly factors CCG categories and bilexical dependencies scored from bi-LSTM representations, enabling locally factored A* search.

  • Results

    The parser achieves state-of-the-art English and Japanese CCG parsing, including 88.8% labeled F1 and 94.0% unlabeled F1 on English CCGbank.

  • Takeaways & Limitations

    Explicit dependency structure resolves attachment ambiguities without sacrificing precomputation and efficient optimal A* inference.

  • Takeaways & Limitations

    The method uses approximate dependency training data because some CCGbank trees cannot be converted under the parser's rule set.

Abstract

from arXiv · show

We propose a new A* CCG parsing model in which the probability of a tree is decomposed into factors of CCG categories and its syntactic dependencies both defined on bi-directional LSTMs. Our factored model allows the precomputation of all probabilities and runs very efficiently, while modeling sentence structures explicitly via dependencies. Our model achieves the state-of-the-art results on English and Japanese CCG parsing.

1 Introduction

The paper extends locally factored A* CCG parsing by modeling bilexical dependencies alongside supertags, resolving residual attachment ambiguity while preserving efficient search. It reports best-so-far English results and a 10.0-point Japanese clause-dependency-accuracy gain over a simple baseline.

  • 1 Introduction: Dependency modeling resolves ambiguities that remain when multiple CCG parses share the same supertags.Figure 1 illustrates equally likely parses under the category-only model, while the dependency factors distinguish their structures.
  • 1 Introduction: Deterministic attachment heuristics can fail on structures such as “a house in Paris with a garden,” motivating explicit dependency modeling.The attach-low heuristic works empirically for English but does not always derive the correct parse.
  • 1 Introduction: The model jointly factors CCG categories and bilexical dependencies, predicting each word's head with a bi-LSTM-based bilinear model.This extends the supertag-prediction architecture to head prediction while retaining local factorization.
  • 1 Introduction: Unlike recursive alternatives, the model represents tree structure through dependencies without recomputing recursive networks during search.It therefore preserves the locally factored formulation that supports efficient A* inference.
  • 1 Introduction: 10.0 points in clause dependency accuracy separate the method from a simple Lewis et al. (2016) application on Japanese parsing.The paper motivates this experiment with Japanese's freer word order and case-marker-dominated structure.

2 Background

The background introduces supertag-factored A* CCG parsing, whose informative categories enable efficient chart search but leave attachment ambiguities when identical categories yield multiple trees. The paper addresses this limitation by adding directly scored dependency heads based on bi-LSTM representations.

  • 2 Background: Supertagging resolves much CCG structure because each category is highly informative about attachment decisions.The locally factored model assigns probabilities to word categories and searches over well-formed CCG trees.
  • 2 Background: A* parsing combines chart edges using inside and outside scores, exploring the edge with highest b(e) + a(e) priority until the goal edge is popped.The chart stores the highest-scoring derivation for each edge.
  • 2 Background: Precomputed unigram category distributions make A* search efficient, while admissibility and monotonicity guarantee that the first completed goal derivation is optimal.The outside heuristic is an upper bound on the true Viterbi outside score.
  • 2 Background: Category-only scores can assign equal priority to multiple trees, requiring attachment heuristics such as longer-dependency or low-attachment preferences.These heuristics cannot resolve every situation correctly.
  • 2 Background: The proposed dependency scores borrow graph-based neural dependency parsing and score each head choice directly from bi-LSTM outputs.Although first-order, the bi-LSTM conditions the predictions on the entire sentence and keeps head distributions precomputable.

3 Proposed Method

The model jointly factors CCG categories and bilexical dependencies while preserving efficient A* parsing through precomputable local distributions. Dependency scores are incorporated during chart combination and adjusted at the complete parse, with shared bi-LSTM representations producing supertag and head distributions.

  • 3.1 A* parsing with Supertag and Dependency Factored Model: The model defines each CCG tree using categories, dependency heads, and a derivation, then adds a unigram head-choice distribution to the locally factored supertag model.The dependency component scores each word’s head independently, enabling precomputation before search.
  • 3.1 A* parsing with Supertag and Dependency Factored Model: The inside score excludes the unresolved head score of a dependency subtree’s root, so a special unary rule corrects the final goal-edge mismatch.This adjustment aligns the complete parse score with the true model score.
  • 3.1 A* parsing with Supertag and Dependency Factored Model: A* search remains tractable because dependency terms are computed during chart expansion, with one dependency arc resolved at each combinatory rule.When two child edges combine, the parent inside score adds their scores and the dependency arc score determined by the rule’s head direction.
  • 3.2 Network Architecture: Shared bi-LSTM hidden vectors feed biaffine dependency-head and bilinear supertag transformations, allowing both distributions to condition on the entire sentence.The resulting probabilities can be precomputed before search, maintaining parsing efficiency.

4 CCG to Dependency Conversion

The paper converts CCG derivations into dependencies for training and inference using LEWISRULE, HEADFIRST, or HEADFINAL strategies. It also reports that HEADFIRST avoids component conflicts and yields higher English parsing scores than LEWISRULE, while Japanese uses a head-final rule.

  • 4 CCG to Dependency Conversion: The conversion rules serve both to create dependency training data and to extract one dependency arc at each combinatory rule during A* search.The paper compares the original LEWISRULE with simpler HEADFIRST and HEADFINAL alternatives.
  • 4 CCG to Dependency Conversion: LEWISRULE selects heads by combinatory-rule conditions, including special handling for forward rules, backward rules, punctuation removal, and conjunction.For Japanese, feature values are ignored when applying this rule to produce more natural structures.
  • 4 CCG to Dependency Conversion: Dependency extraction is incomplete for some CCGbank trees because the parser’s rule set mismatches the annotated grammar, so original CCGbank dependencies are used instead.The paper notes that rule names are also not explicitly annotated in English CCGbank.
  • 4 CCG to Dependency Conversion: HEADFIRST makes the left argument the head for English, whereas HEADFINAL always selects the right argument for Japanese’s head-final word order.These rules are motivated by the contrasting SVO and SOV ordering patterns.
  • 4 CCG to Dependency Conversion: HEADFIRST avoids conflicts between dependency and supertag predictions and produces higher English parsing scores than LEWISRULE.Fixing arc directions also makes head prediction easier and dependency predictions more reliable according to the paper.

5 Tri-training

The paper extends tri-training to jointly exploit unlabeled supertag and dependency information for English parsing. Its HEADFIRST-derived dependencies are easier for two dependency parsers to predict, supporting their use in silver-data construction.

  • 5 Tri-training: The extended tri-training procedure assigns dependency structures to Lewis et al.’s publicly available silver data containing high-quality supertags.Tri-training intersects outputs from two parsers on unlabeled data to create new silver training examples.
  • 5 Tri-training: The English training setup uses dependency data extracted from CCGbank, with dummy “none” labels because dependency labels are unavailable.The extraction strategy differs according to whether LEWISRULE or HEADFIRST dependencies are used.
  • 5 Tri-training: HEADFIRST dependencies achieve 94.9% unlabeled attachment score with RBGParser and 94.6% with lstm-parser, versus 93.8% and 92.5% for LEWISRULE dependencies.These development-set results suggest that HEADFIRST dependencies are easier to parse; the two parsers agree on more than 1.7 million sentences for both dependency types.
  • 5 Tri-training: Tri-training samples are downweighted by multiplying their loss by 0.4, while the supervised CCGbank training set is replicated 15 times.These settings reduce the relative effect of the silver data.

6 Experiments

Experiments show that dependency factors improve English CCG parsing while preserving efficient A* search, and substantially help Japanese parsing where supertags leave structural ambiguity.

  • Effect of Dependency: Adding dependency terms improves performance for both LEWISRULE and HEADFIRST on the English development set.The comparison contrasts dependency-aware models with supertag-factored models using attach-low heuristics.
  • Choice of Dependency Conversion Rule: HEADFIRST consistently outperforms LEWISRULE, while tri-training adds about 1.0 absolute point under both dependency conversion strategies.The results indicate that the simpler conversion strategy benefits from silver data similarly to LEWISRULE.
  • Excluding Normal Form Constraints: Without normal-form constraints, HEADFIRST produces 89 violating combinations versus 283 for LEWISRULE, and its CCGbank score rises from 86.6 to 86.8.The fixed rightward arc direction yields simpler structures and can implicitly enforce normal-form behavior.
  • Results on Test Set: 88.8% labeled F1 and 94.0% unlabeled F1 are achieved on English CCGbank with tri-training, exceeding neuralccg by 0.1 and 0.3 points.These are reported as the best F1 scores in English CCG parsing.
  • Efficiency Comparison: The parser processes over 7 times more sentences than neuralccg during A* search, although its supertagger is slower than neuralccg and EasySRL reimpl.Overall speed is faster than neuralccg but slower than EasySRL reimpl.
  • Japanese Parsing Results: Japanese parsing improves over the supertag-only baseline by 1.1 category-assignment points and 4.0 bunsetsu-dependency points with HEADFINAL dependencies.The supertag-only model reaches 81.5% attachment, while the dependency model addresses ambiguity remaining after supertagging.

7 Related Work

Related work uses dependencies to constrain or score lexicalized grammar parses, but this paper jointly searches over CCG derivations and dependency scores rather than committing to a one-best dependency structure.

  • Dependency-Based HPSG Parsing: Prior HPSG work uses predicted dependencies as soft constraints on rule applications or as features for supertag prediction.Sagae et al. (2007) constrain output-tree form, while Zhang et al. (2010) use dependency features to predict HPSG supertags.
  • Dependency-Based CCG Parsing: Some CCG parsers optimize dependencies directly, whereas this method selects a CCG derivation with a high dependency score rather than modeling dependencies alone.The objective therefore combines CCG derivation structure with dependency evidence.

8 Conclusion

The paper presents an A* CCG parser that jointly models CCG categories and dependency structure through local factors. This design resolves attachment ambiguities without deterministic heuristics while retaining efficient search and state-of-the-art English and Japanese performance.

  • The parser decomposes CCG-tree probability into local factors for CCG categories and dependency structure.
  • Explicit dependency modeling removes the need for deterministic heuristics to resolve attachment ambiguities.
  • Precomputable local probabilities let the parser efficiently find the optimal parse while achieving state-of-the-art performance on English and Japanese CCG parsing.
Loading 1704.06936v1…