Extracting Relations from Text: From Word Sequences to Dependency Paths - Natural Language Processing and Text Mining - page 34

S 1 = Protesters seized several pumping stations , holding 127 Shell workers hostage .

S 2 =

Troops recently have raided churches , warning ministers to stop preaching .

Fig. 3.4. Sentences as dependency graphs.

these examples reveals that all relevant words form a shortest path betweenthe
twoentities in a graph structure whereedges correspond to relations betweena
word (head) and its dependents. For example, Figure 3.4 shows the full dependency
graphs fortwosentences fromthe ACE (AutomatedContent Extraction) newspa-
per corpus[12], in whichwords are representedas nodes and word-word dependen-
cies are representedas directed edges. A subset ofthese word-word dependencies
capture the predicate-argument relations present in thesentence. Arguments are
connectedto their targetpredicates eitherdirectlythroughanarc pointing to the
predicate('troops → raided'), or indirectlythroughapreposition orinfinitive par-
ticle ('warning ← to ← stop'). Othertypes ofword-word dependencies account for
modifier-head relationships present in adjective-noun compounds('several → sta-
tions'), noun-noun compounds('pumping → stations'), or adverb-verb constructions
('recently → raided').
Word-word dependencies are typically categorizedintwoclasses as follows:
• [Local Dependencies] These correspond tolocal predicate-argument (orhead-
modifier)constructionssuchas 'troops → raided', or 'pumping → stations' in
Figure 3.4.
• [Non-local Dependencies] Long-distance dependencies arise due to various
linguisticconstructionssuchascoordination,extraction, raising and control. In
Figure 3.4, among non-local dependencies are 'troops → warning', or 'ministers
→ preaching'.
AContext Free Grammar (CFG) parser can be usedtoextract local depen-
dencies, whichfor each sentence form a dependencytree. Mildly context sensitive
formalismssuchas Combinatory Categorial Grammar (CCG)[13] model word-word
dependencies more directly and can be usedtoextractboth local and long-distance
dependencies, giving rise to adirectedacyclicgraph, as illustratedinFigure 3.4.

3.3.1 The ShortestPath Hypothesis

If e 1 and e 2 are twoentities mentionedinthesamesentence such that theyare
observedto be in a relationship R , thenthecontribution ofthesentence dependency