0x442 Syntax

Constituent Tree Parsing

CFG

Ambiguities

  • coordination ambiguity: CFG cannot enforce agreement in the context. (e.g: koalas eat leaves and (barks))
  • prepositional phrase attachment ambiguity (e.g: I saw a girl (with a telescope))

Solution is to use PCFG to score all the derivations to encode how plausible they are

PCFG

Estimation

ML Estimation

$$P(X \to \alpha) = \frac{C(X \to \alpha)}{C(X)}$$

smoothing is helpful

Parsing

CKY

complexity is $O(n^3 |R|)$ where $n$ is the number of words and $|R|$ is the number of rules in the grammar

Horizontal Expansion

Vertical Expansion

Discriminative Rerankings

generate top-k candidates from the previous parser and rerank them with discriminative reranking might be helpful

Features

Classifiers