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.

Hw11 is posted

Lecture 22: Document Coherence

Documents are not just collections of sentences.  Sentences serve purposes, and well-written document puts its sentences together well.

There are (at least) two notions of "well":

• Coherence: This is what makes a text meaningful.  This is the idea that the semantic interpretation of the sentences in a text should fit together into a larger picture.
  
  
• Cohesion: This is what makes a text hang together.  This is the idea that sentences help you understand the relationship between what came before and what is coming later.

Coherence includes things like anaphor and coreference, as well as things that tie the text together to the real world, like presuppositions and implications.  Cohesion includes things like lexical repetition, topical repetitions, elipsis, etc.


This is a lot like syntax/semantics.  A document can be cohesive but still make no sense.  This is like syntax.  On the other hand, a document can be meaningful, but still not feel like the sentences go together properly.  This is like semantics.

TextTiling is an algorithm/model for discovering cohesive subparts (despite what the original paper says).  This is basically a partitioning problem.  We're given a text as a sequence of sentences, and we want to break it into pieces, each of which is internally cohesive.  The algorithm looks roughly like:

• For each sentence, collect all the word (stems) that occur in that sentence.
• Define the similarity between any two token sequences (subsequences of the text) as the cosine similarity between their stem vectors.
• For each position i in the text, compute the similarity between the block i-21:i-1 and i:i+20.  (20 is arbitrary.)

We can now plot the similarities between blocks as we move through sentences, versus how people thing texts should be divided:

We then define the splits as the points where the similarities drop below some threshold.

One major (linguistic) weakness of this approach is its inability to handle synonymy, etc.  When we talk about lexical repetition for cohesion, we also typically include things like "train / car / engine" even though their not the same word.

Argumentative Zoning is more of a coherence-type model (though it's not precisely clear that it's only in one of the two categories). It is primarily a model for research papers, where we talk about the role that each sentence plays in a paper.  Like TextTiling, the model is also flat: a document is just a sequence of sentences and we're going to assign each sentence to a class.  The three major classes are { Background, Other, Own }.

The original approach to AZ is to annotate data, and then train a classifier.  The features used break down into a handful of categories:

• explicit structure (where is this sentence in the document)
• relative location (what %age through the document is this sentence)
• citation (to self versus to others)
• syntax (tense, aspect, voice, negation, etc.)
• semantic (type of verb, etc.)
• content (word overlap with title, etc.)

Overall, the results suggest that it's fairly easy to find OWN stuff, but relatively difficult to figure out what the other parts are.

There has been a lot of interesting work in this area since then, including things like sentiment analysis of citations, better features, better learning, etc...

Lecture 21: Local Discourse Context

Coreference analysis means figuring out the meaning of pronouns in sentences like: "John saw him in the mirror" versus "John saw himself in the mirror."  That's anaphor resolution.  More generally, "John saw Bill and said 'My friend, you look lovely today.'" we need to figure out that My=John and friend=Bill.

Generally we care about three "mention" types:

• Pronouns (he, she, it, I, etc...)
• Proper nouns (John, Bill, Congress, the White House, etc...)
• Common nouns (the soccer player, the man, etc.)

Not all pronouns are coreference, as in pleonastic it: "It is raining" but most are.

There are lots of signals of coreference:

• Apposition: "John, mayor of Tinyville, is happy."  Here, it's pretty clear that John=mayor
  
• Syntactic structure with pronouns/-self.  "John saw him" versus "... himself"
  
• Gender / number / type agreement.  "He" is probably not "Mary" and "him" is probably not "players".  Similarly, "he" is probably not "the White House".  (Mr. and Mrs. are helpful here.)
  
• Locality.  "He" probably refers back to a nearby referent, not something far away.
  
• Discourse focus.  New entities are likely to transition from being objects to being subjects, not the other way around.
  
• Sub/super-string matching.  "Bill Clinton" and "Clinton" are likely coreferent.
  
• New entities are often introduced with indeterminant NPs ("a player") and then later with determinant NPs
  
• World knowledge: sometimes we just know that Obama is the President

In general, matches between different mention types work as follows:

• Named to named: very easy, 95% accuracy just using substring matching
• Named to pronoun: pretty easy, 85-90% using Hobbs' heuristics, locality and gender
• Named to common: very hard (often need world knowledge)
• Common to common: very hard (often need lexical semantics)
• Common to pronoun: don't bother -- do common to named and named to pronoun

Basic algorithms for coreference resolution treat it as a binary classification problem: are these two mentions coreferent or not.  (That is, after we've done mention detection ala named entity recognition.)  Some issues with this approach:

• You then need to go back and fix things up to make sure that transitivity is enforced; or use left-to-right search
  
• Number of -ve examples >> number of +ve examples; often subsample the negatives
  
• These decisions aren't independent

Some things that make life difficult:

• Metonymy: when we say "the White House" meaning "Obama"
  
• Common nouns that aren't mentions of an entity: "This life is wonderful"
  
• Quantified pronouns: "Every man loves his mother" (might or might not be coreferent)
  
• World knowledge

My general feeling about world knowledge is that if it's commonly known it might not be stated (eg., we won't always see "Obama, President of the US, ...") but if it's not commonly known it will be made really obvious (eg., "Joe Shmoe, soccer player for the team").  We can, however, mine this common knowledge using the sorts of techniques we talked about last week.