22.2.1 Supervised Learning Approaches to Relation Analysis

Supervised machine learning approaches to relation detection and classification follow a scheme that should be familiar by now. Texts are annotated with relations chosen from a small fixed set by human analysts. These annotated texts are then used to train systems to reproduce similar annotations on unseen texts. Such annotations indicate the text spans of the two arguments, the roles played by each argument and the type of the relation involved.

The most straightforward approach breaks the problem down into two sub-tasks: detecting when a relation is present between two entities and then classifying any detected relations. In the first stage, a classifier is trained to make a binary decision as to whether or not a given pair of named entities participate in a relation. Positive examples are extracted directly from the annotated corpus, while negative examples are generated from within-sentence entity pairs that are not annotated with a relation.

function FINDRELATIONS(words) returns relations

relations←nil

entities←FINDENTITIES(words)

forall entity pairs $ \langle e1,e2\rangle $ in entities do

if RELATED?(e1,e2)

relations←relations+CLASSIFYRELATION(e1,e2)

Figure 22.13 Finding and classifying the relations among entities in a text.

In the second phase, a classifier is trained to label the relations that exist between candidate entity pairs. As discussed in Ch. 6, techniques such as decision trees, naive Bayes or MaxEnt handle multiclass labeling directly. Binary approaches based on discovering separating hyperplanes such as SVMs solve multiclass problems by employing a one-versus-all training paradigm. In this approach, a set of classifiers are trained where each classifier is trained on one label as the positive class and all the other labels as the negative class. Final classification is performed by passing each instance to be labeled to all of the classifiers and then choosing the label from the classifier with the most confidence, or returning a rank ordering over the positively responding classifiers. Fig. 22.13 illustrates the basic approach for finding and classifying relations among the named entities within a discourse unit.

As with named entity recognition, the most important step in this process is to identify surface features that will be useful for relation classification (Zhou et al., 2005). The first source of information to consider are features of the named entities themselves.

• Named entity types of the two candidate arguments

• Concatenation of the two entity types

• Head words of the arguments

• Bag of words from each of the arguments

The next set of features are derived from the words in the text being examined. It is useful to think of these features as being extracted from three locations: the text between the two candidate arguments, a fixed window before the first argument, and a fixed window after the second argument. Given these locations, the following word-based features have proven to be useful.

• The bag of words and bag of bigrams between the entities

• Stemmed versions of the same

• Words and stems immediately preceding and following the entities

• Distance in words between the arguments

• Number of entities between the arguments

Finally, the syntactic structure of a sentence can signal many of the relationships among any entities contained within it. The following features can be derived from various levels of syntactic analysis including base-phrase chunking, dependency parsing and full constituent parsing.

• Presence of particular constructions in a constituent structure

• Chunk base-phrase paths

Bags of chunk heads

• Dependency-tree paths

• Constituent-tree paths

Tree distance between the arguments

One method of exploiting parse trees is to create detectors that signal the presence of particular syntactic constructions and then associate binary features with those detectors. As an example of this, consider the sub-tree shown in Fig. 22.14 that dominates the named entities American and AMR Inc. The NP construction that dominates these two entities is called an appositive construction and is often associated with both part-of and a-kind-of relations in English. A binary feature indicating the presence of this construction can be useful in detecting these relations.

This method of feature extraction relies on a certain amount of a priori linguistic analysis to identify those syntactic constructions that may be useful predictors of certain classes. An alternative method is to automatically encode certain

| Entity-based features | |

| --- | --- |

| $ Entity_{1} $ type | ORG |

| $ Entity_{1} $ head | airlines |

| $ Entity_{2} $ type | PERS |

| $ Entity_{2} $ head | Wagner |

| Concatenated types | ORGPERS |

| Word-based features | |

| Between-entity bag of words | { a, unit, of, AMR, Inc., immediately, matched, the, move, spokesman } |

| Word(s) before $ Entity_{1} $ | NONE |

| Word(s) after $ Entity_{2} $ | said |

| Syntactic features | |

| Constituent path | $ NP \uparrow NP \uparrow S \uparrow S \downarrow NP $ |

| Base syntactic chunk path | $ NP \rightarrow NP \rightarrow PP \rightarrow NP \rightarrow VP \rightarrow NP \rightarrow NP $ |

| Typed-dependency path | Airlines $ \leftarrow_{subj} matched \leftarrow_{comp} said \rightarrow_{subj} Wagner $ |