Assignment 3

Due: Tue 11 Jan 2016 Midnight

This assignment covers the topic of syntactic parsing. Submit your solution in the form of an iPython notebook (ipynb) file. The following notes on PCFG in NLTK (notebook source) contain useful code to start this assignment.

Content

1. Q1: Learning a PCFG from a Treebank
1. Q1.1 Random PCFG Generation
2. Q1.2 Learn a PCFG from a Treebank
3. Q1.3 Induce a PCFG in Chomsky Normal Form
4. Q1.4 Test CFG Independence Assumptions
2. Q2: Building and Evaluating a Simple PCFG Parser
1. Q2.1 Build a Parser
2. Q2.2 Evaluate the Parser
3. Q2.3 Accuracy per Distance
4. Q2.4 Accuracy per Label
5. Q2.5 Using the Universal Tagset

Question 1: Learning a PCFG from a Treebank

Question 1.1: Random PCFG Generation

import itertools
from nltk.grammar import CFG
from nltk.parse import generate

demo_grammar = """
  S -> NP VP
  NP -> Det N
  PP -> P NP
  VP -> 'slept' | 'saw' NP | 'walked' PP
  Det -> 'the' | 'a'
  N -> 'man' | 'park' | 'dog'
  P -> 'in' | 'with'
"""
grammar = CFG.fromstring(demo_grammar)

for n, sent in enumerate(generate.generate(grammar, n=10), 1):
        print('%3d. %s' % (n, ' '.join(sent)))
		
  1. the man slept
  2. the man saw the man
  3. the man saw the park
  4. the man saw the dog
  5. the man saw a man
  6. the man saw a park
  7. the man saw a dog
  8. the man walked in the man
  9. the man walked in the park
 10. the man walked in the dog

Generation works top down: pick the start symbol of the grammar, then randomly choose a production starting from the start symbol, and add the RHS as children of the root node, then expand each node until you obtain terminals. The result should be a tree and not a sentence.

The generated parse trees should exhibit the distribution of non-terminal distributions captured in the PCFG (that is, the generation process should sample rules according to the weights of each non-terminal in the grammar).

Note: you must generate according to the PCFG distribution - not just randomly. To this end, you should use the method generate() from the NTLK ProbDistI interface. Specifically, you should use the nltk.probability.DictionaryProbDist class to represent the probability distribution of mapping an LHS non-terminal to one of the possible RHS.

from nltk.grammar import Nonterminal
from nltk.grammar import toy_pcfg2
from nltk.probability import DictionaryProbDist

productions = toy_pcfg2.productions()

# Get all productions with LHS=NP
np_productions = toy_pcfg2.productions(Nonterminal('NP'))

dict = {}
for pr in np_productions: dict[pr.rhs()] = pr.prob()
np_probDist = DictionaryProbDist(dict)

# Each time you call, you get a random sample
print(np_probDist.generate())
(Det, N)

print(np_probDist.generate())
(Name,)

print(np_probDist.generate())
(Name,)

Function Specification

pcfg_generate(grammar) -- return a tree sampled from the language described by the PCFG grammar

Validation

• Generate 1,000 random trees using nltk.grammar.toy_pcfg2 - store the resulting trees in a file "toy_pcfg2.gen".
• Compute the frequency distribution of each non-terminal and pre-terminal in the generated corpus. You can look at the code of nltk.induce_pcfg(root, productions) to see how this can be done. You should construct one distribution per non-terminal.
• For each distribution, compute the KL-divergence between the MLE estimation of the probability distribution constructed on your test corpus and toy_pcfg2. The MLE estimation is obtained by applying the MLEProbDist estimator to the observed empirical frequency distribution. KL-divergence (Kullback-Leibler divergence also known as relative entropy) estimates the difference between two distributions.

  Read some precisions on handling diverging KL computations when the support of the 2 distributions p and q are not identical.

• Explain your observations.

Question 1.2: Learn a PCFG from a Treebank

In this question, we want to induce a PCFG from the treebank and investigate its properties. For reference, NLTK provides a function called induce_pcfg in the nltk.grammar module. It starts from a set of productions and constructs a weighted grammar with the MLE estimation of the production distributions.

Function specification

from nltk.corpus import LazyCorpusLoader, BracketParseCorpusReader

def simplify_functional_tag(tag):
    if '-' in tag:
        tag = tag.split('-')[0]
    return tag

treebank = LazyCorpusLoader('treebank/combined', BracketParseCorpusReader, r'wsj_.*\.mrg')

print(treebank.parsed_sents()[:1])
-- we need to transform the tree to remove NONE tags and simplify tags.

pcfg_learn(treebank, n)
-- treebank is the nltk.corpus.treebank lazy corpus reader
-- n indicates the number of trees to read
-- return an nltk.PCFG instance

from nltk.grammar import Production
from nltk import Tree, Nonterminal

def get_tag(tree):
    if isinstance(tree, Tree):
        return Nonterminal(simplify_functional_tag(tree.label()))
    else:
        return tree

def tree_to_production(tree):
    return Production(get_tag(tree), [get_tag(child) for child in tree])

def tree_to_productions(tree):
    yield tree_to_production(tree)
    for child in tree:
        if isinstance(child, Tree):
            for prod in tree_to_productions(child):
                yield prod

Data Exploration and Validation

1. How many productions are learned from the trees? How many interior nodes were in the treebank?
2. Draw a plot of the distribution of productions according to their frequency (number of rules with frequency 1, 2, ...). What do you observe?
3. If you induce a PCFG from 200 trees, and another one from 400 trees - compare the distribution of the rules you learn.

Question 1.3: Induce a PCFG in Chomsky Normal Form

pcfg_cnf_learn(treebank, n)
-- treebank is the nltk.corpus.treebank lazy corpus reader (simplified tags)
-- n indicates the number of trees to read
-- return an nltk.PCFG in CNF

1. How many productions are learned from the CNF trees? How many interior nodes were in the original treebank, and in the CNF treebank?
2. Compare the CNF and non-CNF figures (ratios). What do you conclude?

Question 1.4: Test CFG Independence Assumptions

For the treebank before CNF transformation, report the following statistics, for the expansions of the NP category:

• Compute the distribution of the RHS given the NP LHS for all NPs in the treebank. Draw a histogram plot.
• Compute the same distribution only for NPs that appear directly below a S node (any variant of S in the Penn treebank tagset). Draw a histogram plot.
• Compute the same distribution only for NPs that appear directly below a VP node (any variant of VP in the Penn Treebank tagset). Draw a histogram plot.
• Compare the distributions above. Use KL-divergence.
• Conclude: does the data in the treebank confirm the CFG hypothesis for each configuration (original trees, annotated CNF trees)? (How do you calibrate the values of the KL-divergence to decide that 2 values are similar?)

Question 2: Building and Evaluating a Simple PCFG Parser

Question 2.1: Build a Parser

Learn a PCFG over the Chomsky Normal Form version of this treebank.

Construct a ViterbiParser using this PCFG grammar.

Question 2.2: Evaluate the Parser

1. Precision
2. Recall
3. F-measure
4. Labelled Precision
5. Labelled Recall
6. Labelled F-Measure

In labelled precision and recall we count that 2 constituents match if they have the same label for the interior node. For unlabelled metrics, we just compare the first and last indexes. Make sure you compare the trees from the treebank after they have been simplified: for example, S-TPC-1 must be compared with S and ADVP-TMP with ADVP, and -NONE- nodes have been eliminated.

You can read more on this metric in the following references:

1. An assignment on parsing evaluation by Scott Farrar includes detailed explanation and examples on how the metric is computed.
2. Evalb software: this is the C program used in all standard evaluations of constituent parsers (by Satoshi Sekine and Michael Collins).
3. Evalb in Java for those who prefer reading Java over C - is part of the Stanford CoreNLP package.
4. Evalc-GUI in Java: in addition to computing the metrics, this package shows the trees that are compared and highlights graphically the differences in each pair.

Question 2.3: Accuracy per Distance

Question 2.4: Accuracy per Label

Question 2.5: Working with the Universal Tagset [Optional]

Report on the number of rules induced with your new annotation scheme before and after CNF transformation. Use parent and Markov annotations (chomsky_normal_form(tree, factor='right', horzMarkov=2, vertMarkov=2, childChar='|', parentChar='^')).

Report the accuracy of the learned Viterbi parser with the Universal annotations. Compare your results with the data provided in Improved PCKY (by Scott Farrar).