Assignment 6


This assignment is due at the start of class on Wednesday.

In class we talked about the formalization of parsers as deductive systems, as discussed by Shieber et al., Principles and Implementation of Deductive Parsing (see especially Sections 1-3). We also briefly talked about differences in memory use by different kinds of parsers, and how this might relate to human sentence processing. The latter is discussed in Resnik (1992), which makes the argument that human parsing uses a left corner parser, combining elements of top-down and bottom-up parsing, along with a composition operation that helps to minimize memory load. In this assignment, you'll look at this in more depth.

  1. Read Resnik (1992), Left-Corner Parsing and Psychological Plausibility. Write a brief summary of the argument it's making in your own words. (No more than 1-2 paragraphs. That means you need to summarize, not just try to repeat everything. The ability to summarize is a demonstration of your understanding.)

    (Although it's not particularly relevant for this assignment, note that augmented transition networks [ATNs], discussed in Section 2.2, are basically recursive transition networks with the added ability to execute procedures, e.g. to build and store structure, on the arcs.)

  2. Notice that the paper never actually gave a full description of its left-corner parser with composition in the form of a deductive scheme in the style of Shieber et al. -- i.e. item form, axioms, goal, inference rules. Formalize the parser on paper using a schema of that kind.

  3. Illustrate the steps the parser would take (in the same kind of format as the derivations in Shieber et al. on pages 9, 11, and 13) for the sentence "the man laughed" assuming the grammar contains rules
    S -> NP VP
    NP -> DET N
    VP -> VI
    VP -> VT NP
    VI -> laughed 
    VT -> saw
    N -> man
    N -> woman
    DET -> the
    

  4. Implement the parser in the programming language of your choice, using the agenda-driven, chart-based deduction procedure described in Shieber et al. Section 5 (see especially page 27). Turn in code with a README showing how to run it. You do not need to make the parser efficient -- if you implement a very simple strategy like depth-first search with backtracking and no redundancy-checking at all, that's ok. I don't care if your parser takes exponential time in the worst case. Also, you can implement just a recognizer if you like, rather than doing the extra bookkeeping to recover parse trees at the end. What your parser should do, though, is show the items that are added to the chart, similar to the derivations in Shieber et al. on pages 9, 11, and 13.

    Note that you do not necessarily need to code from scratch. It looks like the nltk.parse package, in particular the nltk.parse.chart module, might be useful if you like python. (See also www.nltk.org/howto/parse.html and Chapter 8 of the NLTK book.) I also imagine that implementations of Earley's algorithm in various languages could potentially be modified, e.g. this one or implementations listed on the Wikipedia Earley parser page. (Note that I have not looked at any of these to see if they're any good.)

    You might also find it useful to look at the discussion in Robert Moore (2004), Improved Left-Corner Chart Parsing for Large Context-Free Grammars, particularly Section 5. However, to avoid confusion note that there are a few different definitions of "left corner" floating around. For Resnik (1992) and purposes of this assignment, the left corner is a property of an individual rule; e.g. in the grammar above, the left corner of the rule S -> NP VP is NP. In the NLTK book and some other discussions of parsing, however, each non-terminal symbol has a set of left corners (often stored in a "left corner table" that is created ahead of parsing); e.g. for the grammar above, the left corners for VP are VI and VT. In still other discussions, the values in the left corner table are defined recursively: for example, in the grammar above, DET is a left corner of S (because DET is a left corner of NP and NP is a left corner of S). That's because (recursive) left corners can be used for filtering out edges that couln't possibly be useful before they're added to the chart. For example, if we're considering adding the dotted rule [S -> * NP VP, i, i] to the chart (where the asterisk indicates the dot), it's a waste of time if the word at position i has part-of-speech VT, since there's no possible tree rooted at S that could have a VT as its first word. So that kind of filtering can make parsing more efficient, which is the main focus of Moore's paper. But as I said, for this assignment I'm not worried about efficiency.

  5. Using your implemented parser with the grammar below, show the following:

    S -> A S B
    S -> C 
    S -> X S
    S -> S Y
    A -> a
    B -> b
    C -> c
    X -> x
    Y -> y
    

    Note: I have not actually implemented the left-corner parser with composition, so it's possible it will be harder than I expected. If implementing it is an unreasonable amount of work, please show you made a good faith effort (turn in incomplete code with a brief explanation), but you can still get the credit by supporting the arguments (a-c) on paper, rather than using your implementation.


Extra credit: getting hands-on with data using LDA and a parser (worth up to 20% of an assignment)

Topic models like LDA are usually defined in terms of words, but in actuality they really treat documents as bags of features, not necessarily bags of words. For example, Mimno talks about using phrases as features with MALLET.

In class we briefly talked about the idea that topic models might benefit from features that capture predicate-argument relationships, e.g. object(cut,taxes) might be a feature derived from many different phrasings (We need to cut more taxes, Taxes should be cut, etc.).

(a) Use an existing topic modeling package (e.g. MALLET, gensim, Segan) to run LDA (or another similar model if you prefer, e.g. LSA) on one of the corpora used in earlier assignments, e.g. Congressional speech, SOTU. (Feel free to modify the corpus, e.g. break long documents into paragraph-sized documents, if that would be useful.) Similar to the HMM assignment, where you experimented with different numbers of latent states, experiment with a few different numbers of latent topics (e.g. 10, 30, 50) and comment on the quality of the topics. Are some of them reasonably interpretable and coherent? What is the effect of having more vs. less latent topics available?

(b) Use an off the shelf parser, e.g. Stanford CoreNLP, to extract some syntactically relevant features that you couldn't easily get from just bigrams, such as verb-object, subject-verb. For Stanford CoreNLP you can use "enhanced (collapsed) dependencies", e.g. see below. Add these features to the documents they come from, and try LDA again as in part (a). How do the topics look now? Is there value in using the syntactic dependency relationships?

The parses below were obtained using the Stanford CoreNLP online demo. Note that there is enough information here that if you wanted to, you could collapse some surface syntactic roles to improve normalization and reduce data sparsity; for example, you could map nsubjpass to dobj and nmod:agent to nsubj.

Although Stanford CoreNLP is the whole package, including lots more besides parsing, it looks like a smaller download of just the Stanford parser is available at http://nlp.stanford.edu/software/lex-parser.shtml. Some other off the shelf parsers include spaCy, EmoryNLP's nlp4j (formerly ClearNLP), and MaltParser. There's also RelEx, which claims to have a greater degree of semantic normalization.

"The taxes were cut by the Republicans"

Enhanced dependencies

root ( ROOT-0 , cut-4 )
det ( taxes-2 , The-1 )
nsubjpass ( cut-4 , taxes-2 )
auxpass ( cut-4 , were-3 )
case ( Republicans-6 , by-5 )
nmod:agent ( cut-4 , Republicans-6 )


"The Republicans cut the taxes"

Enhanced dependencies

root ( ROOT-0 , cut-2 )
nsubj ( cut-2 , Republicans-1 )
det ( taxes-4 , the-3 )
dobj ( cut-2 , taxes-4 )