{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

Assignment 3

\n", "\n", "

Due: Tue 28 Jan 2020 Midnight

\n", "Natural Language Processing - Fall 2021 Michael Elhadad\n", "

\n", "This assignment covers the topic of syntactic parsing.\n", "Submit your solution in the form of a Jupyter notebook (ipynb) file.\n", "\n", "

Content

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "

Question 1: Designing CFGs for NLP

\n", "\n", "NLTK provides library support to read CFGs from string representation, and parse sentences given a CFG using different \n", "parsing algorithms (either top-down or bottom-up). In this question, we manually develop a grammar to support \n", "increasingly complex phenomena in English syntax. The following code provides the starting point:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Parsing 'John left'\n", " [ * John left]\n", " S [ 'John' * left]\n", " R [ NP * left]\n", " S [ NP 'left' * ]\n", " R [ NP IV * ]\n", " R [ NP VP * ]\n", " R [ S * ]\n", "(S (NP John) (VP (IV left)))\n", "Parsing 'John eats bread'\n", " [ * John eats bread]\n", " S [ 'John' * eats bread]\n", " R [ NP * eats bread]\n", " S [ NP 'eats' * bread]\n", " R [ NP TV * bread]\n", " S [ NP TV 'bread' * ]\n", " R [ NP TV NP * ]\n", " R [ NP VP * ]\n", " R [ S * ]\n", "(S (NP John) (VP (TV eats) (NP bread)))\n" ] } ], "source": [ "import nltk\n", "from nltk import CFG\n", "\n", "sg = \"\"\"\n", "S -> NP VP\n", "VP -> IV | TV NP\n", "NP -> 'John' | \"bread\"\n", "IV -> 'left'\n", "TV -> 'eats'\n", "\"\"\"\n", "g = CFG.fromstring(sg)\n", "\n", "# Bottom-up parser\n", "sr_parser = nltk.ShiftReduceParser(g, trace=2)\n", "\n", "# Parse sentences and observe the behavior of the parser\n", "def parse_sentence(sent):\n", " tokens = sent.split()\n", " trees = sr_parser.parse(tokens)\n", " for tree in trees:\n", " print(tree)\n", "\n", "parse_sentence(\"John left\")\n", "parse_sentence(\"John eats bread\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this toy grammar, the following non-terminals are used:\n", "\n", "\n", "\n", "

Question 1.1: Extend a CFG to support Determiners, Number agreement, Countable/Mass nouns, Pronouns and Dative Constructions

\n", "\n", "Extend the CFG so that the following sentences can be parsed:\n", "
\n",
    "    John left\n",
    "    John loves Mary\n",
    "    They love Mary\n",
    "    They love her\n",
    "    She loves them\n",
    "    Everybody loves John\n",
    "    A boy loves Mary\n",
    "\tThe boy loves Mary\n",
    "\tSome boys love Mary\n",
    "    John gave Mary a heavy book\n",
    "    John gave it to Mary\n",
    "\tJohn likes butter\n",
    "\tJohn moves a chair\n",
    "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

1.1.1 Determiners and Count/Mass Nouns

\n", "\n", "Determiners in English come before common nouns.\n", "Proper nouns cannot have a determiner. (We ignore cases such as \"The Petersons came by tonight for a visit.\")\n", "

\n", "Some determiners can only be used for singular nouns (\"a\"), others only for plural nouns (\"many\") and others with either plural or singular (\"the\").\n", "

\n", "Some common nouns are called \"uncountable\" or mass nouns (e.g., \"butter\").\n", "Mass nouns cannot appear in plural and cannot have counting determiners.\n", "Other nouns are countable nouns. They can be used in the plural and can be modified by counting determiners.\n", "

\n", "Extend the grammar to support countable and uncountable nouns with the corresponding restrictions on determiners and plural.\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

1.1.2 Pronouns

\n", "\n", "Pronouns in English are characterized by the following morphological attributes:\n", "\n", "Make sure the appropriate form of pronouns are used in each of the possible contexts.\n", "Do you need to encode gender in the grammar? Explain why.\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

1.1.3 Subject/Verb Agreement

\n", "

\n", "Make sure subject and verb agree in number.\n", "

\n", "\n", "\n", "

1.1.4 Over-generation

\n", " \n", "Check whether your grammar overgenerates by giving an example of ungrammatical sentence that it recognizes as grammatical.\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

Question 1.2: Extend a CFG to support Coordination and Prepositional Phrases

\n", "\n", "\n", "

1.2.1 Support Prepositional Phrases

\n", "\n", "Extend the grammar so that it can parse the following sentences:\n", "\n", "
\n",
    "John saw a man with a telescope\n",
    "John saw a man on the hill with a telescope\n",
    "\n",
    "Mary knows men and women\n",
    "Mary knows men, children and women\n",
    "\n",
    "John and Mary eat bread\n",
    "John and Mary eat bread with cheese\n",
    "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

1.2.2 Support Coordination

\n", " \n", "What is the number of a coordination such as \"John and Mary\"?\n", "

\n", "What is the number of a coordination such as \"John or Mary\"?\n", "

\n", "\"John or the children\"?\n", "

\n", "Propose (without implementing) ways to support such variations.\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

1.2.3 Overgeneration

\n", "\n", "Demonstrate ways in which your grammar over-generates. Explain your observations.\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

\n", "\n", "

Question 2: Learning a PCFG from a Treebank

\n", "\n", "\n", "

Question 2.1: Random PCFG Generation

\n", "\n", "Consider the PCFG datatype implementation provided in NLTK.\n", "

\n", "Consider the module nltk.parse.generate.\n", "It contains a function generate(grammar) which given a CFG grammar produces all the sentences the grammar can produce.\n", "Naturally, this may produce an infinite number of sentences if the grammar is recursive." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1. the man slept\n", " 2. the man saw the man\n", " 3. the man saw the park\n", " 4. the man saw the dog\n", " 5. the man saw a man\n", " 6. the man saw a park\n", " 7. the man saw a dog\n", " 8. the man walked in the man\n", " 9. the man walked in the park\n", " 10. the man walked in the dog\n" ] } ], "source": [ "import itertools\n", "from nltk.grammar import CFG\n", "from nltk.parse import generate\n", "\n", "demo_grammar = \"\"\"\n", " S -> NP VP\n", " NP -> Det N\n", " PP -> P NP\n", " VP -> 'slept' | 'saw' NP | 'walked' PP\n", " Det -> 'the' | 'a'\n", " N -> 'man' | 'park' | 'dog'\n", " P -> 'in' | 'with'\n", "\"\"\"\n", "grammar = CFG.fromstring(demo_grammar)\n", "\n", "for n, sent in enumerate(generate.generate(grammar, n=10), 1):\n", " print('%3d. %s' % (n, ' '.join(sent)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

2.1.1 PCFG_Generate

\n", "\n", "Write a new function pcfg_generate(grammar) which will\n", "generate a random tree from a PCFG according to its generative\n", "probability model. In other words, your task is to write a sample\n", "method from the PCFG distribution.\n", "

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

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

\n", "\n", "Note: you must generate according to the PCFG distribution - not just randomly.\n", "To this end, you should use the method generate() from the\n", "NTLK ProbDistI interface.\n", "Specifically, you should use the\n", "nltk.probability.DictionaryProbDist\n", "class to represent the probability distribution of mapping an LHS non-terminal to one of the possible RHS." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(Name,)\n", "(Det, N)\n", "(Name,)\n" ] } ], "source": [ "from nltk.grammar import Nonterminal\n", "from nltk.grammar import toy_pcfg2\n", "from nltk.probability import DictionaryProbDist\n", "\n", "productions = toy_pcfg2.productions()\n", "\n", "# Get all productions with LHS=NP\n", "np_productions = toy_pcfg2.productions(Nonterminal('NP'))\n", "\n", "dict = {}\n", "for pr in np_productions: dict[pr.rhs()] = pr.prob()\n", "np_probDist = DictionaryProbDist(dict)\n", "\n", "# Each time you call, you get a random sample\n", "print(np_probDist.generate())\n", "\n", "print(np_probDist.generate())\n", "\n", "print(np_probDist.generate())\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

\n",
    "Function Specification\n",
    "\n",
    "pcfg_generate(grammar) -- return a tree sampled from the language described by the PCFG grammar\n",
    "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

2.1.2 Generate 1,000 Trees

\n", "\n", "Generate 1,000 random trees using nltk.grammar.toy_pcfg2 - store the resulting trees in a file \"toy_pcfg2.gen\"." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

2.1.3 Gather Rules Frequency for all Non-Terminals

\n", " \n", "Compute the rules frequency distribution of each non-terminal and pre-terminal in the generated corpus.\n", "You can look at the code of nltk.induce_pcfg(root, productions) to see how this can be done.\n", "You should construct one distribution per non-terminal." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

2.1.4 Compute KL-Divergence between a priori and generated parameters

\n", " \n", "For each distribution, compute the KL-divergence between the MLE estimation of the probability\n", "distribution constructed on your test corpus and toy_pcfg2.\n", "The MLE estimation is obtained by applying the MLEProbDist estimator to the observed empirical frequency distribution.\n", "KL-divergence (Kullback-Leibler divergence\n", "also known as relative entropy) estimates the difference between two distributions.\n", "

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

\n", "\n", "Explain your observations." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

Question 2.2: Learn a PCFG from a Treebank

\n", "\n", "In this question, we will learn a PCFG from a treebank with different\n", "types of tree annotations. We start from a subset of 200 trees from\n", "the Penn Treebank (which is distributed by NLTK\n", "in the corpus named \"treebank\" - the NLTK version contains about 4,000 trees).\n", "

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

2.2.1 Induce_PCFG

\n", "\n", "At this stage, we learn the PCFG \"as is\" -- without Chomsky Form Normalization -- but with \"simplified\" tags. \n", "That is, we must use a function to simplify all tags in the tree (non-terminal and terminal): " ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[Tree('S', [Tree('NP-SBJ', [Tree('NP', [Tree('NNP', ['Pierre']), Tree('NNP', ['Vinken'])]), Tree(',', [',']), Tree('ADJP', [Tree('NP', [Tree('CD', ['61']), Tree('NNS', ['years'])]), Tree('JJ', ['old'])]), Tree(',', [','])]), Tree('VP', [Tree('MD', ['will']), Tree('VP', [Tree('VB', ['join']), Tree('NP', [Tree('DT', ['the']), Tree('NN', ['board'])]), Tree('PP-CLR', [Tree('IN', ['as']), Tree('NP', [Tree('DT', ['a']), Tree('JJ', ['nonexecutive']), Tree('NN', ['director'])])]), Tree('NP-TMP', [Tree('NNP', ['Nov.']), Tree('CD', ['29'])])])]), Tree('.', ['.'])])]\n", "(S\n", " (NP-SBJ\n", " (NP (NNP Pierre) (NNP Vinken))\n", " (, ,)\n", " (ADJP (NP (CD 61) (NNS years)) (JJ old))\n", " (, ,))\n", " (VP\n", " (MD will)\n", " (VP\n", " (VB join)\n", " (NP (DT the) (NN board))\n", " (PP-CLR (IN as) (NP (DT a) (JJ nonexecutive) (NN director)))\n", " (NP-TMP (NNP Nov.) (CD 29))))\n", " (. .))\n" ] } ], "source": [ "from nltk.corpus import LazyCorpusLoader, BracketParseCorpusReader\n", "\n", "def simplify_functional_tag(tag):\n", " if '-' in tag:\n", " tag = tag.split('-')[0]\n", " return tag\n", "\n", "treebank = LazyCorpusLoader('treebank/combined', BracketParseCorpusReader, r'wsj_.*\\.mrg')\n", "\n", "# Raw form\n", "print(treebank.parsed_sents()[:1])\n", "\n", "# Pretty print\n", "print(treebank.parsed_sents()[0])\n", "\n", "# we need to transform the tree to remove NONE tags and simplify tags." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We want all tags of the form \"NP-SBJ-2\" to be simplified into \"NP\". We also want to filter out \"NONE\" elements from the treebank. \n", "You must find the best way to perform NONE filtering on the trees. (NONE elements appear in the original Penn Treebank for example in the case of relative clauses.)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n",
    "pcfg_learn(treebank, n)\n",
    "-- treebank is the nltk.corpus.treebank lazy corpus reader\n",
    "-- n indicates the number of trees to read\n",
    "-- return an nltk.PCFG instance\n",
    "
\n", "\n", "Use the following code as a starting point:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "from nltk.grammar import Production\n", "from nltk import Tree, Nonterminal\n", "\n", "def get_tag(tree):\n", " if isinstance(tree, Tree):\n", " return Nonterminal(simplify_functional_tag(tree.label()))\n", " else:\n", " return tree\n", "\n", "def tree_to_production(tree):\n", " return Production(get_tag(tree), [get_tag(child) for child in tree])\n", "\n", "def tree_to_productions(tree):\n", " yield tree_to_production(tree)\n", " for child in tree:\n", " if isinstance(child, Tree):\n", " for prod in tree_to_productions(child):\n", " yield prod" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

2.2.2 Data Exploration and Validation

\n", "\n", "Explore the following properties of the learned PCFG:\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

Question 2.3: Induce a PCFG in Chomsky Normal Form

\n", "\n", "\n", "

2.3.1 PCFG_CNF_Learn

\n", "\n", "Implement pcfg_cnf_learn\n", "\n", "We now want to learn a PCFG in Chomsky Normal Form from the treebank, with simplified tags, and with filtered NONE elements.\n", "The strategy is to convert the trees in the treebank into CNF, then to induce the PCFG from the transformed trees.\n", "Use the function chomsky_normal_form in nltk.treetransforms to convert the trees. \n", "Pay attention to NONE filtering. Use horizontal Markov annotation and parent annotation:\n", "\n", "\n", "chomsky_normal_form(tree, factor='right', horzMarkov=1, vertMarkov=1, childChar='|', parentChar='^')\n", "\n", "\n", "
\n",
    "pcfg_cnf_learn(treebank, n)\n",
    "-- treebank is the nltk.corpus.treebank lazy corpus reader (simplified tags)\n",
    "-- n indicates the number of trees to read\n",
    "-- return an nltk.PCFG in CNF\n",
    "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

2.3.2 Data Exploration

\n", "\n", "How many productions are learned from the CNF trees? How many interior nodes were in the original treebank, and in the CNF treebank?\n", "\n", "Compare the CNF and non-CNF figures (ratios). What do you conclude?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

Question 2.4: Test CFG Independence Assumptions

\n", "\n", "We want to test the CFG hypothesis that a node expansion is independent from its location within a tree.\n", "

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

\n", "

\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

\n", "\n", "

Question 3: Building and Evaluating a Simple PCFG Parser

\n", "\n", "In this question, we will construct a Viterbi parser for the PCFG induced in Question 2 and perform evaluation of this statistical parser. \n", "

\n", "\n", "\n", "

Question 3.1: Build a Parser

\n", "\n", "\n", "

3.1.1 Dataset Split

\n", " \n", "Split the NLTK treebank corpus into 80% training (about 3,200 trees) and 20% (about 800 trees) testing sets.\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

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

\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

3.1.3 Viterbi Parser

\n", " \n", "Construct a ViterbiParser using this PCFG grammar.\n", "Test the parser on a few sentences." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

Question 3.2: Evaluate the Parser

\n", "\n", "Your task is to compute the ParsEval metric for the constituent-based parse trees on the test dataset of our treebank. \n", "Report the following metrics:\n", "
    \n", "
  1. Precision\n", "
  2. Recall\n", "
  3. F-measure\n", "
  4. Labelled Precision\n", "
  5. Labelled Recall\n", "
  6. Labelled F-Measure\n", "
\n", "\n", "Where precision and recall are computed over \"constituents\" between the parsed trees and the treebank trees: a constituent is a triplet \n", "(interior_node, first_index, last_index) - where first_index is the index of the first word in the sentence covered by the interior node,\n", "and last_index that of the last word (that is, [first_index, last_index] is the yield of the interior node).\n", "

\n", "\n", "In labelled precision and recall we count that 2 constituents match if they have the same label for the interior node. \n", "For unlabelled metrics, we just compare the first and last indexes. \n", "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.\n", "

\n", "\n", "You can read more on this metric in the following references:\n", "

    \n", "
  1. An assignment on parsing evaluation by Scott Farrar includes detailed explanation and examples on how the metric is computed.\n", "
  2. Evalb software: this is the C program used in all standard evaluations of constituent parsers (by Satoshi Sekine and Michael Collins).\n", "
  3. Evalb in Java for those who prefer reading Java over C - is part of the Stanford CoreNLP package.\n", "
\n", "\n", "The specific steps to follow are:\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

Question 3.3: Accuracy per Distance

\n", "\n", "In general, parsers do a much better job on short constituents than long ones. \n", "Draw a plot of the accuracy of constituents per constituent length. \n", "The length of a constituent (node, first, last) is last-first+1. \n", "For a given constituent length X, accuracy is the number of constituents \n", "of length X in the parsed tree that are accurate divided by the total number of constituents of length X." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "

Question 3.4: Accuracy per Label

\n", "\n", "Report accuracy of constituents per label type (S, SBAR, NP, VP, PP etc).\n", "For each node type, report number of occurrences and accuracy. \n", "Note: report accuracy per node type WITHOUT Chomsky Normal Form modification.\n", "For example, if the CNF of the tree generated a non-terminal NP^S, we should count this as NP for this question." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "END" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.0" } }, "nbformat": 4, "nbformat_minor": 4 }