Assignment 2


In class, we talked a bit about what collocations are. In this assignment, we will get some hands-on experience discovering them in a corpus, building on the work you did in the last assignment. Although the work in this assignment is relatively straightforward from an NLP point of view, it's pretty close to what some real political scientists have done, even recently, in text analysis; for example, see Monroe et al., Fightin’ Words: Lexical Feature Selection and Evaluation for Identifying the Content of Political Conflict, Political Analysis, 2008 16(4):372-403, and also this analysis of State of the Union addresses and references therein. (Although I haven't looked at it closely enough to judge its quality, you can find a python implementation of the Monroe et al. approach here.)

Bigram Association Scores

Here is a summary of three bigram association scores you might choose to use in assignment, with pointers to the discussions in the reading. There are some others discussed in the readings also but you are fine if you just look at these three.

Frequency. As discussed by Manning and Schuetze in Section 5.1, the frequency with which you see a bigram can be thought of as a score that is a first rough indicator of whether that bigram might be a collocation. (They also point out that high frequency gives you a lot of uninteresting word pairs that are not collocations, e.g. in the, although you can get more interesting and useful results out of frequency by limiting your attention to adject-noun and noun-noun patterns.)

Chi-squared. In class, we briefly discussed the chi-squared test statistic, which can be used in experiments where you're interested in the question of whether one binary variable (e.g. Male vs Female) affects another binary variable (e.g. whether a person earns more than $100K/year or not). In Manning and Schuetze, Section 5.3.3, Table 5.8 illustrates how the same idea can be applied to discovering collocations. In this example, the first binary variable is "the first word in a bigram is (or isn't) the word new", and the second variable is "the second word in a bigram is (or isn't) the word companies". Section 5.3.3 (specifically equation 5.7) shows how to calculate the chi-squared test statistic for a 2x2 table like Table 5.8; note that O11, O12, O21, and O22 refer to the cells in the upper left, upper right, lower left, and lower right of the 2x2 table, respectively. As you'll see in that discussion, the more extreme the chi-squared value, the less probable it is that this table (i.e. the counts related to this bigram) came about by chance, and therefore the more confidence we can have in rejecting the null hypothesis. So for any bigram, you can (a) construct a table like the one in Table 5.8, and then (b) compute chi-squared as in equation 5.7, and now you've got different score that you can interpret as indicating the extent to which the words in the bigram "go together" more than you'd expect by chance.

Pointwise Mutual Information (PMI). Manning and Schuetze's Section 5.4 shows you another very common way of analyzing bigrams to discover collocations. The intuition here is really simple. In the numerator is the observed probability that the two words occur together. In the denominator is the probability that they would occur together if the null hypothesis were true, i.e. that they were independent of each other, namely the product of their separate probabilities. This gives you a ratio of what you did observe in the corpus to what you would have observed (based on the unigram probabilities) if the null hypothesis were true. PMI is just the log of that ratio, so PMI > 0 means that the two words occur together more often than you'd expect by chance.

Corpora

Congressional speeches. The congressional speech corpus was created by Matt Thomas, Bo Pang, and Lillian Lee. It contains speeches made by politicians in the U.S. House of Representatives during debates over legislation and has been used in a variety of research papers. Conveniently, the corpus is already tokenized and lowercased for you, and the filename conventions make it very easy to identify particular subsets of the corpus. When you download the convote dataset v1.1 (9.8 Mb, tar.gz format) you will see that there are several different versions of the data in this archive; we are concerned only with the data_stage_three directory. For those with limited disk space, a way to extract just the directory of interest is: gunzip < convote_v1.1.tar.gz | tar xvf - convote_v1.1/data_stage_three

Each file in the data_stage_three directory contains a speech by a legislator. The filenames contain information about each speech. In the filename template, ###_@@@@@@_%%%%$$$_PMV:

Please use all the data available under the 3 directories ("development_set", "test_set" and "training_set").

State of the Union. Another interesting dataset is the set of State of the Union(SOTU) addresses of U.S. presidents. (Recall that in a Jan 15, 2016 blog post, Michael Heilman at Civis Analytics presented a simple analysis of State of the Union addresses primarily based on word frequencies. That posting contains a pointer to some other text-analytics research on the topic.) For our purposes here, let's restrict ourselves to the post-Reagan presidencies, i.e. Presidents Bush 1 (Republican), Clinton (Democrat), Bush 2 (Republican), and Obama (Democrat).

The task

The idea here is to use what we've learned in class (and what you've read about in M&S Chapter 5) to answer some interesting questions. Pick one of the two corpora above and answer the following:
  1. Very briefly, what approach did you take in terms of implementation? (Coding from scratch, using an existing toolkit; how you tokenized, stemming or lemmatization, etc.)

  2. What are the top 25 bigram collocations in this corpus, as measured automatically by frequency plus at least two other measures of association? It's fine to use chi-squared value and PMI as discussed above; however you are also welcome to try others like the t-test discussed by Manning and Schuetze, or the (log-)likelihood ratio (Section 5.3.4). In practice I'd say the two most common are either Positive PMI, which is just PMI but replacing any negative PMI with 0, or the log-likelihood ratio. A really good argument is made for the latter in Dunning 1993, which is one of my top several papers in computational linguistics as a great example of clear, well motivated, well argued, and empirically well demonstrated research.

  3. Same question, but limit your attention to speeches by Democrats.

  4. Same question, but limit your attention to speeches by Republicans.

  5. Discuss the advantages and limitations of the measures you used, illustrating using the sorted lists of collocations you obtained.

  6. Are there any interesting differences between what you found for Democrats and what you found for Republicans?

    Here's an example. When I used the Democratic congressional speeches as a corpus, and sorted all non-stopword bigrams by log-likelihood value, and did the same separately for Republicans, the phrase middle class ranked 16th for Democrats and 115th for Republicans; conversely, the phrase law enforcement ranked 28th for Republicans and 141st for Democrats. One could argue that this empirical observation is consistent with at least some characterizations of the priorities of the two political parties -- e.g. see discussions of the role that the phrase middle class had during the 2008 presidential debates, like this one.

    Identify contrasts of this kind and offer your thoughts on why they might or might not be meaningful. (If you're not particularly familiar with American politics -- or even if you are -- I recommend you talk with someone who is. Discussing your output with someone outside your technical specialty can be a really useful experience.)

  7. Finding some interesting contrasts by inspection is nice, but why should I trust your intuitions? For several examples of differences between Democrats and Republicans, make a statistical argument that the difference you're pointing out is a genuine difference supported by the data.

    For example, continuing the example above: having discovered that middle class might be an interesting phrase, I could use a chi-square test to show that the difference in the frequency of middle class among Democrats and Republicans is statistically significant. (Note that doing a chi-square test in this way, looking at a contingency table of {Democrat,Republican} x {middle_class, NOT middle_class}, is different from using chi-square to find an association between the word middle and the word class. Both cases involve a 2x2 contingency table, i.e. looking for evidence of an association between some binary variable A and a second variable B, but one case is looking for a lexical association between two words, and the other is looking for an association between a bigram and the party of the speaker using that bigram.)

    For full credit, be very explicit about the statistical hypothesis testing you're doing. For example, an explicit argument would (at least) explicitly describe null hypothesis H0, identify the test statistic, identify your choice for alpha (the cutoff for statistical significance), give the p-value, and present an argument for why we should draw the conclusions you want us to draw. (It's fine to use some of the same language I used in class.)

    You are welcome to use an on-line calculator or off-the-shelf code to do the statistical calculation if you'd like. Though you'll learn more if you do the calculation by hand at least once. :-) If you're thinking of using the chi-square test, note that there are problems using it when counts are small (see Problems in the chi-square test Wikipedia page). Depending on the counts, the likelihood ratio test may be a better choice. The classic formulation of that test for computational linguists is by Dunning (1993), but see also Moore (2004) for some more intuitive formulations (Figure 2) and an argument for using Fisher's Exact Test (typically viewed as intractable for large samples but Moore gives a number of optimizations that make it practical).

Ways to go about it

In terms of implementation,

You are welcome to work together. If you do so, turn in separate assignments (since the discussion parts will be different), even if you're turning in the same code, but identify who you worked with and who contributed what.

What to turn in

Recall from the course home page that the address for turning in assignments is ling773.sp2018@gmail.com, with "Assignment N" at the start of the subject line. Turn in assignments in PDF format, with assignment_N_firstname.lastname.zip (or .tar.gz) as the file name. (In this case N=2.) We will deduct 5% for not following these instructions. If you have any questions let us know.

Include:

Again, note that you are being graded on your writeup, not on the quality of your code. Yes, all other things being equal, clean and easily runnable code would be nice. But if you have the choice between spending more time experimenting with and thinking about the data you're looking at, versus more time making your code pretty and easy to run, please focus on the former and not the latter!

And, again, I strongly encourage you to talk to each other in person and/or on the class discussion board.

Extra credit (up to 10% of this assignment)

For people who find the above assignment relatively easy, I strongly recommend doing the extra credit.

Bigram statistics are, of course, just one way to identify expressions that might be useful or interesting. Consider some others.

  1. Repeat steps 1-6 above (excluding the hypothesis test in question 7) using one or more linguistically informed ways to identify multiword expressions/terms. These could include, for example, one or both of the following:

    If you have an alternative linguistically informed approach you'd like to try, ask me.

    For discussion of other methods for term identification see this survey of approaches from the EAGLES Preliminary Recommendations on Semantic Encoding, Sanfilippo et al. 1998.

  2. Compare and contrast what you found using the alternative technique(s) with what you found using bigram association scores (and with each other, if you tried more than one). Did it find anything interesting? Did you find anything interesting one way that was not uncovered the other way?