Last seminar of the semester: Michael Paul Dec 8, 11am

December 8: Michael Paul: Summarizing Contrastive Viewpoints in Opinionated Text

AVW 2120

Performing multi-document summarization of opinionated text has unique
challenges because it is important to recognize that the same
information may be presented in different ways from different
viewpoints. In this talk, we will present a special kind of
contrastive summarization approach intended to highlight this
phenomenon and to help users digest conflicting opinions. To do this,
we introduce a new graph-based algorithm, Comparative LexRank, to
score sentences in a summary based on a combination of both
representativeness of the collection and comparability between
opposing viewpoints. We then address the issue of how to automatically
discover and extract viewpoints from unlabeled text, and we experiment
with a novel two-dimensional topic model for the task of unsupervised
clustering of documents by viewpoint. Finally, we discuss how these
two stages can be combined to both automatically extract and summarize
viewpoints in an interesting way. Results are presented on two
political opinion data sets.
This project was joint work with ChengXiang Zhai and Roxana Girju.


Bio: Michael Paul is a first-year Ph.D. student of Computer Science at
the Johns Hopkins University and a member of the Center for Language
and Speech Processing. He earned a B.S. from the University of
Illinois at Urbana-Champaign in 2009. He is currently a Graduate
Research Fellow of the National Science Foundation and a Dean's Fellow
of the Whiting School of Engineering.

Lecture 25: Mapping Text to Actions

There has been a bunch of work recently on trying to automatically find relationships between language and the "real world", where "real world" actually often means some sort of simulated environment.  Here are a few papers along these lines:

• Fleischman, M. B. and Roy, D.  Intentional Context in Situated Language Learning.  Ninth Conference on Computational Natural Language Learning , Ann Arbor, MI. June 2005.
•  Learning to Connect Language and Perception [Abstract] [PDF]
  Raymond J. Mooney
  In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI), Senior Member Paper, Chicago, IL, pp. 1598-1601, July 2008.
•  S.R.K. Branavan, Harr Chen, Luke Zettlemoyer and Regina Barzilay
  "Reinforcement Learning for Mapping Instructions to Actions",
  Proceedings of ACL, 2009. Best Paper Award 
•  Learning semantic correspondences with less supervision.
  Percy Liang, Michael I. Jordan, Dan Klein.
  Association for Computational Linguistics and International Joint Conference on Natural Language Processing (ACL-IJCNLP), 2009. 
•  Adam Vogel and Dan Jurafsky. 2010. Learning to Follow Navigational Directions. In Proceedings of ACL-2010, Uppsala, Sweden. [PDF]

There are others, of course, but these five form a fairly diverse example set.  There's not much work on trying to use the real world, but robotics people like Nick Roy (at MIT) are trying to make headway on this problem.

In the first paper, which is the one we'll talk about most, the key idea is that of hierarchical plans, represented as a pcfg.  For instance we might have a rule "OfferCup -> PickUpCup MoveCup ReleaseCup", where each of the subactions might either be atomic (correspond to actual muscle movements) or might itself be broken down further.  (Qustion: how context free is this problem?)

The key ambiguity is due to the fact that actions do not select for exactly one interpretation, as in the Blicket example.

In this paper, they hand constructed a PCFG for actions and the key learning question was whether you could figure out the level of ambiguity automatically.  The basic idea is to look at relative frequencies of occurance between lexical items and nodes in the PCFG tree for the actions.

P4, grading rules

So P4 has been posted for a while.  It is "optional" in the sense that your project grades will be based on your best three out of four grades.  In particular, here's what will happen.

Suppose that your grades on P1, ..., P4 are a,b,c,d.  (If you don't do P4, then d=0.)

Let x = [ (a + b + c + d) - min { a, b, c, d } ] / 3

Then x is your average grade on your best three projects.


We will use x as your overall project grade (i.e., since each project is weighed equally, it will be like you got a score of x on all FOUR of them).

Lecture 24: Information Extraction

Information extraction is, roughly, the task of going from unstructured text (aka text) to structured data.  Think of it as mapping language to a database.

One of the more famous IE tasks is identifying terrorist events (specifically South American terrorist events) in documents.  For each event, we have to identify the victim(s), date, type of event (bombing, etc.), culprits, and so on.  These fields define our extraction template and our goal is to fill it up based on a document.  Of course some documents mention no terrorist events and some mention multiple.  And not all fields will be mentioned.  This data was available for the MUC (message understanding conference) competitions two decades ago and current approaches still only get about 50% accuracy!

One way of going about this problem is as a sequence labeling task, akin to NER.  Since you can imagine how this works, we'll talk about the other style of approach: pattern-based methods.

The idea of pattern-based approaches is that our system consists of a collection of extraction patterns, of the form "<Subj> was assassinated" => Victim.  These lexico-syntactic patterns tell us how and when to extract certain slots (aka fields) from text.  The expressiveness of patterns depends entirely on how much preprocessing you want to do, but usually some sort of syntactic processing is assumed.

The key question is: where do these patterns come from?  The trend in IE has been to move toward mostly unsupervised approaches that don't need large amounts of training data.  Successful approaches are akin to the Yarowsky algorithm for WSD.

Suppose we had labeled data, where for each document we have one (for simplicity) partially filled template.  We can go into the document and find occurrences of the strings in that template as the things we want to extract.  For each of these, we can find a bunch of extraction patterns that would potentially extract that string and collect them over the whole data set.  We now need to find the "best" ones.  A common metric is the "R log F" metric, which is simply the probability that a given pattern extracts the right slot, times log of the frequency of that pattern.  The "log F" term is in there because we want to make sure that we get good coverage.

Of course, you needn't start with labeled data.  You can start with small lists of slot fillers (eg., Al Queda as a perpetrator and so on) and bootstrap away.  As always, the quality of your seeds directly affects how well your algorithm works.

One can get even more unsupervised by doing the following.  Take a collection of documents that talk about terrorist events, and a collection of documents that don't.  Look for patterns in the terrorist events collection that are significantly more common there, than in the other collection.  Rank these by something like "R log F".  The top patterns there are often very good extraction patterns, but we don't know what they are supposed to extract.  Have a human look down the list of the top 100 and viola, you're done, and it only takes a few minutes.

Most approaches to IE fall into one of these two camps: sequence labeling or pattern based approaches.  It seems that sequence labeling approaches work well when most of the words in the text are extracted for something (i.e., turning free text citations into bibtex entries), but pattern based approaches work well for needle in a haystack problems.

There have been a few recent trends in IE:

1. Using Wikipedia infoboxes as training data
   
2. Trying to extract knowledge without pre-defined templates (akin to our discussion of mining world knowledge)
   

Lecture 23: Rhetorical Structure Theory

So far we've seen flat representations of discourse.  RST is an example of a hierarchical discourse representation.  Such as:

Here, we've broken some imagined text into 7 "units" and depicted the role of these units in the text.  As is implied by the title, this theory is mostly applicable to rhetoric, which is essentially persuasive language.

An RST structure is essentially a dependency tree over elementary discourse units (EDUs), where relations on the edges of the tree tell us the relationship between two EDUs.  In the above example, we're saying that EDUs 1-3 provide background to EDUs 4-7.  And so on down the tree.

For most relations, there is a distinction between the nucleus and satellite of that relation: basically this is just like headedness in syntax.  The nucleus contains the important stuff.

The relations in RST are given by communicative intent.  This is a big separation between RST and other theories of discourse.

Here is an example of the evidence relation:

• The program as published for the calendar year 1980 really works.
• In only a few minutes, I entered all the figures from my 1980 tax return and got a result which agreed with my hand calculations to the penny.

Here, the first sentence is the nucleus and the second is the satellite.  The evidence schema states (R=reader, W=writer, N=nucleus, S=satellite):

• constraints on N: R might not believe N to a degree satisfactory to W
• constraints on S: R believes S or will find it credible
• constrains on N+S: R's comprehending S increases R's belief of N
• the effect: R's belief of N is increased
• locus of effect: N

 Here's an example for concession:

• Concern that this material is harmful to health or the environment may be misplaced.
• Although it is toxic to certain animals,
• evidence is lacking that it has any serious long-term effect on human beings.

Here, the 2nd EDU is a concession to the 3rd EDU (note that 2 and 3 are both in the same sentence).  The concession schema looks like:

• constraints on N: W has positive regard for the situation presented in N
• constraints on S: W is not claiming that the situation presented in S doesn't hold
• constraints on N+S: W acknowledges a potential or apparent incompatibility between the situations presented in N and S; W regards the situations presented in N and S as compatible; recognizing that the compatibility between the situations presented in S and S increases R's positive regard for the situation presented in N
• the effect: R's positive regard for the situation presented in N is increased
• locus of effect: N and S

Here is the original list of relations from the Mann+Thompson paper, though others have been added over time:

• Circumstance
• Solutionhood
• Elaboration
• Background
• Enablement and Motivation
• Evidence and Justify
• Relations of Cause
• Antithesis and Concession
• Condition and Otherwise
• Interpretation and Evaluation
• Restatement and Summary
• Sequence
• Contrast

Spotting discourse effects is quite hard, which I have previously bemoaned.  In general, there are two tasks: splitting sentences into EDUs and then doing discourse parsing.  Unfortunately, the main foothold we have for both of these tasks are lexical cues.  (For EDU splitting, embedded S-BARs often, though don't always, indicate a new EDU.)

For instance, concession is often identified by the word "although."  And "Evidence" is often identified by "For instance."  And "Elaboration" is often identified by "And."  And so on.

One clever idea a few years ago was to try to mine lexical relations that are indicative of discourse structure.  For example, I can find all sentences that begin "for example" and look at that sentence, and the preceding sentence.  I can assume that this is an example of Evidence, and then look at features of those two sentences to try to figure out why this is an evidence relation.  Then, in the future, when I see sentences that don't have this lexical cue, I can apply whatever I've learned.

The hope is that if you mine contrast relations, you can find contrasting pairs like love/hate or iPhone/Android or whatever.  As was shown in the assigned paper for today, that didn't work particularly well.  My feeling is that lexical information is not "deep" enough to really get you to discourse except in very simple cases (see that post I linked to before).

P3 grading updated, deadline Wed 24th, 5p

Looks like I underestimated the difficulty of the gender classification.  I've adjusted the scoring to be easier on you.  The new scoring is:

• 35 < e < 37 : 10%
• 34 < e < 35 : 25%
• 33 < e < 34 : 32%
• 32 < e < 33 : 34%
• 31.5 < e < 32 : 36%
• 31 < e < 31.5 : 37%
• 30.5 < e < 31.0 : 38%
• 30 < e < 30.5 : 39%
• e < 30: 40%

Midterm solution is posted

See here.