20.7.4 Evaluating Distributional Word Similarity

Distributional similarity can be evaluated in the same ways as the saurus-based similarity; we can compare intrinsically to human similarity scores, or we can evaluate it extrinsically as part of end-to-end applications. Besides word sense disambiguation and malapropism detection, similarity measures have been used as a part of systems for the grading of exams and essays (Landauer et al., 1997), or taking TOEFL multiple-choice exams (Landauer and Dumais, 1997; Turney et al., 2003).

Distributional algorithms are also often evaluated in a third intrinsic way: by comparison with a gold-standard thesaurus. This comparison can be direct with a single thesaurus (Grefenstette, 1994; Lin, 1998a) or by using precision and recall measure against an ensemble of thesauri (Curran and Moens, 2002). Let S be the set of words that are defined as similar in the thesaurus, by being in the same synset, or perhaps sharing the same hypernym, or being in the hypernym-hyponym relation. Let $ S' $ be the set of words that are classified as similar by some algorithm. We can define precision and recall as:

$$ precision=\frac{\left|S\cap S^{\prime}\right|}{\left|S^{\prime}\right|}recall=\frac{\left|S\cap S^{\prime}\right|}{\left|S\right|} $$

Curran (2003) evaluated a number of distributional algorithms using comparison with the sauri and found that the Dice and Jaccard methods performed best as measures

of vector similarity, while t-test performed best as a measure of association. Thus the best metric weighted the associations with t-test, and then used either Dice or Jaccard to measure vector similarity.

20.8 HYPONYMY AND OTHER WORD RELATIONS

Similarity is only one kind of semantic relation between words. As we discussed in Ch. 19, WordNet and MeSH both include hyponymy/hypernymy, as do many thesauruses for other languages, such as CiLin for Chinese (?). WordNet also includes antonymy, meronymy, and other relations. Thus if we want to know if two senses are related by one of these relations, and the senses occur in WordNet or MeSH, we can just look them up. But since many words are not in these resources, it is important to be able to learn new hypernym and meronym relations automatically.

Much work on automatic learning of word relations is based on a key insight first articulated by Hearst (1992), that the presence of certain lexico-syntactic patterns can indicate a particular semantic relationship between two nouns. Consider the following sentence extracted by Hearst from the Groliers encyclopedia:

(20.54) Agar is a substance prepared from a mixture of red algae, such as Gelidium, for laboratory or industrial use.

Hearst points out that most human readers will not know what Gelidium is, but that they can readily infer that it is a kind of (a hyponym of) red algae, whatever that is. She suggests that the following lexico-syntactic pattern

$$ NP_{0}{~such~as~}NP_{1}\{,NP_{2}\ldots,(and|or)NP_{i}\},i\geq1 $$

implies the following semantics

$$ \forall N P_{i},i\geq1,\mathrm{h y p o n y m}(N P_{i},N P_{0}) $$

allowing us to infer

hyponym(Gelidium, red algae)

| $ NP\{,NP\} * \{,\} $ (and or) other $ NP_{{H}} $ | ... temples, treasuries, and other important civic buildings. |

| --- | --- |

| $ NP_{{H}} $ such as $ \{NP,\} $ (or |and) NP | red algae such as Gelidium |

| such $ NP_{{H}} $ as $ \{NP,\} $ (or |and) NP | works by such authors as Herrick, Goldsmith, and Shakespeare |

| $ NP_{{H}} $ {,} including $ \{NP,\} $ (or |and) NP | All common-law countries, including Canada and England |

| $ NP_{{H}} $ {,} especially $ \{NP,\} $ (or |and) NP | ... most European countries, especially France, England, and Spain |

Fig. 20.14 shows five patterns Hearst (1992, 1998) suggested for inferring the hyponym relation; we've shown $ NP_{H} $ as the parent/hyponym. There are a number of other attempts to extract different WordNet relations using such patterns; see the history section for more details.

Of course, the coverage of such pattern-based methods is limited by the number and accuracy of the available patterns. Unfortunately, once the obvious examples have been found, the process of creating patterns by hand becomes a difficult and slow process. Fortunately, we've already seen the solution to this kind of problem. We can find new patterns using bootstrapping methods that are common in information extraction (Riloff, 1996; Brin, 1998), and are also key to the Yarowsky method described earlier in Sec. 20.5.

The key insight for the use of bootstrapping in relational pattern discovery is that with a large corpus we can expect that words involved in a relation to show up with many different patterns that express that same relation. Therefore, in theory at least, we need only start with a small number of precise patterns to acquire a set of seed words involved in a given relation. These words can then be used to query a large corpus for sentences containing both terms in some kind of dependency relation; new patterns can then be extracted from these new sentences. The process can be repeated until the pattern set is large enough.

As an example of this process, consider the terms “red algae” and “Gelidium” discovered earlier using Hearst’s simple pattern set. Among the results of a simple Google search using these as query terms is the following example:

One example of a red algae is Gelidium.

Removing the seed words from such a sentence and replacing them with simple wildcards is the crudest kind of pattern generation. In this case, submitting the pattern "One example of a * is *" to Google currently yields nearly 500,000 hits, including the following example:

One example of a boson is a photon.

We can also extract slightly more sophisticated patterns by parsing the extracted sentences and putting wildcards into the parse tree.

The key to the success of bootstrapping approaches is to avoid the semantic drift that tends to occur as part of repeated applications of bootstrapping. The further we get from the original set of seed words or patterns the more likely it is that we'll come across patterns with meanings quite different from what we set out to discover. We'll see methods for dealing with this drift when we discuss bootstrapping for information extraction in Ch. 22.

An alternative to bootstrapping is to use large lexical resources like WordNet as a source of training information, in which each WordNet hypernym/hyponym pair tells us something about kinds of words are in this relation, and we train a classifier to help find new words that exhibit this relation.

This hyponym learning algorithm of Snow et al. (2005), for example, relies on WordNet to help learn large numbers of weak hyponym patterns, and then combine them in a supervised classifier in 4 steps:

1. Collect all pairs of WordNet noun concepts $ c_i $, $ c_j $ that are in the hypernym/hyponym relation.

2. For each noun pair, collect all sentences (in a 6 million word corpus) in which both nouns occur.

4. Use the large set of patterns as features in an logistic regression classifier

3. Parse the sentences and automatically extract every possible Hearst-style lexico-syntactic pattern from the parse tree

5. Given a pair of nouns in the test set, extract features and use the classifier to determine if the noun pair is related by the hypernym/hyponym relation or not.

Four of the new patterns automatically learned by this algorithm include:

NP_{H} like NP

NP is a NP_{H}

NP_{H} called NP

NP, a NP_{H} (appositive):

Snow et al. (2005) then showed good hypernym detection performance by using each of these patterns as a weak feature combined by a logistic regression classifier.

Another way to use WordNet to help address the hypernym problem is to model the task as choosing the place to insert unknown words into an otherwise complete hierarchy. It is possible to do this without using lexico-syntactic patterns. For example, we can use a similarity classifier (using distributional information, or morphological information) to find the words in the hierarchy that are most similar to an unknown word, using an approach like K-Nearest-Neighbors, and insert the new word there (Tseng, 2003). Or we can treat the task of hypernym labeling as a labeling task like named-entity tagging. Ciaramita and Johnson (2003) take this approach, using as tags 26 supersenses, from the 26 broad-category ‘lexicographer class’ labels from WordNet (person, location, event, quantity, etc). They use features such as surrounding part-of-speech tags, word bigram and trigram features, spelling and morphological features, and apply a multiclass perceptron classifier.

Finding meronyms seems to be harder than hyponyms; here are some examples from Girju et al. (2003):

The car's mail messenger is busy at work in the mail car as the train moves along.

Through the open side door of the car, moving scenery can be seen.

Meronyms are hard to find because the lexico-syntactic patterns that characterize them are very ambiguous. For example the two most common patterns indicating meronymy are the English genitive constructions $ [NP_1\ of\ NP_2] $ and $ [NP_1 $'s $ NP_2 $], which also express many other meanings such as possession; see Girju et al. (2003, 2006) for discussion and possible algorithms.

Learning individual relations between words is an important component of the general task of thesaurus induction. In thesaurus induction, we combine our estimates of word similarity with our hypernym or other relations to build an entire ontology or thesaurus. For example the two-step thesaurus induction algorithm of Caraballo (1999, 2001) first applies a bottom-up clustering algorithm to group together semantically similar words into an unlabeled word hierarchy. Recall from Sec. 20.10 that in agglomerative clustering, we start by assigning each word its own cluster. New clusters are then formed in a bottom-up fashion by successively merging the two clusters that are most similar; we can use any metric for semantic similarity, such as one of the distributional metrics described in the previous section. In the second step, given the

unlabeled hierarchy, the algorithm uses a pattern-based hyponym classifier to assign a hypernym label to each cluster of words. See the history section for more recent work on thesaurus induction.

20.9 SEMANTIC ROLE LABELING

The final task we'll discuss in this chapter links word meanings with sentence meanings. This is the task of semantic role labeling, sometimes called thematic role labeling, case role assignment or even shallow semantic parsing. Semantic role labeling is the task of automatically finding the semantic roles for each predicate in a sentence. More specifically, that means determining which constituents in a sentence are semantic arguments for a given predicate, and then determining the appropriate role for each of those arguments. Semantic role labeling has the potential to improve performance in any language understanding task, although to date its primary applications have been in question answering and information extraction.

Current approaches to semantic role labeling are based on supervised machine learning and hence require access to adequate amounts of training and testing materials. Over the last few years, both the FrameNet and PropBank resources discussed in Ch. 19 have played this role. That is, they have been used to specify what counts as a predicate, to define the set of roles used in the task and to provide training and test data. The SENSEVAL-3 evaluation used Framenet, while the CONLL evaluations in 2004 and 2005 were based on PropBank.

The following examples show the different representations from the two efforts. Recall that FrameNet (20.62) employs a large number of frame-specific frame elements as roles, while PropBank (20.63) makes use of a smaller number of numbered argument labels which can be interpreted as verb-specific labels.

[You] can't [blame] [the program] [for being unable to identify a processor] COGNIZER TARGET EVALUEE REASON

[The San Francisco Examiner] issued [a special edition] [around noon yesterday] ARG0 TARGET ARG1 ARG M-TMP

A simplified semantic role labeling algorithm is sketched in Fig. 20.15. Following the very earliest work on semantic role analysis (Simmons, 1973), most work on semantic role labeling begins by parsing the sentence. Publicly available broad-coverage parsers (such as Collins (1996) or Charniak (1997)) are typically used to assign a parse to the input string. Fig. 20.16 shows a parse of (20.63) above. The resulting parse is then traversed to find all predicate-bearing words. For each of these predicates the tree is again traversed to determine which role, if any, each constituent in the parse plays with respect to that predicate. This judgment is made by first characterizing the constituent as a set of features with respect to the predicate. A classifier trained on an appropriate training set is then passed this feature set and makes the appropriate assignment.

Let's look in more detail at the simple set of features suggested by Gildea and Jurafsky (2000, 2002), which have been incorporated into most role-labeling systems. We'll

extract them for the first NP in Fig. 20.16, the NP-SBJ constituent the San Francisco Examiner.

• The governing predicate, in this case the verb issued. For PropBank, the predicates are always verbs; FrameNet also has noun and adjective predicates. The predicate is a crucial feature, since both PropBank and FrameNet labels are defined only with respect to a particular predicate.

• The phrase type of the constituent, in this case NP (or NP-SBJ). This is simply the name of the parse node which dominates this constituent in the parse tree. Some semantic roles tend to appear as NPs, others as S or PP, and so on.

• The head word of the constituent, Examiner. The head word of a constituent can be computed using standard head rules, such as those given in Ch. 12 in

Fig. ??. Certain head words (e.g. pronouns) place strong constraints on the possible semantic roles they are likely to fill.

• The head word part-of-speech of the constituent, NNP.

• The path in the parse tree from the constituent to the predicate. This path is marked by the dotted line in Fig. 20.16. Following (Gildea and Jurafsky, 2000), we can use a simple linear representation of the path, NP↑S↓VP↓VBD. ↑ and ↓ represent upward and downward movement in the tree respectively. The path is very useful as a compact representation of many kinds of grammatical function relationships between the constituent and the predicate.

• The voice of the clause in which the constituent appears, in this case active (as contrasted with passive). Passive sentences tend to have strongly different linkings of semantic roles to surface form than active ones.

• The binary linear position of the constituent with respect to the predicate, either before or after.

• The sub-categorization of the predicate. Recall from Ch. 12 that the subcategorization of a verb is the set of expected arguments that appear in the verb phrase. We can extract this information by using the phrase structure rule that expands the immediate parent of the predicate; VP $ \rightarrow $ NP PP for the predicate in Fig. 20.16.

Many other features are generally extracted by semantic role labeling systems, such as named entity tags (it is useful to know if a constituent is a LOCATION or PERSON, for example), or more complex versions of the path features (the upward or downward halves, whether particular nodes occur in the path), the rightmost or leftmost words of the constituent, and so on.

We now have a set of observations like the following example, each with a vector of features; we have shown the features in the order described above (recall that most observations will have the value NONE rather than e.g., ARG0, since most constituents in the parse tree will not bear a semantic role):

ARG0: [issued, NP, Examiner, NNP, NP↑S↓VP↓VBD, active, before, VP → NP PP]

Just as we saw for word sense disambiguation, we can divide these observations into a training and a test set, use the training examples in any supervised machine learning algorithm, and build a classifier. SVM and Maximum Entropy classifiers have yielded good results on this task on standard evaluations. Once trained, the classifier can be used on unlabeled sentences to propose a role for each constituent in the sentence. More precisely, an input sentence is parsed and a procedure similar to that described earlier for training is employed.

Instead of training a single stage classifier, some role labeling algorithms do classification in multiple stages for efficiency:

• Pruning: to speed up execution, some constituents are eliminated from consideration as possible roles, based on simple rules

• Identification: a binary classification of each node as an ARG to be labeled or a NONE.

• Classification: a one-of-N classification of all the constituents that were labeled as ARG by the previous stage.

There are a number of complications that all semantic role labeling systems need to deal with. Constituents in FrameNet and PropBank are required to be non-overlapping. Thus if a system incorrectly labels two overlapping constituents as arguments, it needs to decide which of the two is correct. Additionally, the semantic roles of constituents are not independent; since PropBank does not allow multiple identical arguments, labeling one constituent as an ARG0 would greatly increase the probability of another constituent being labeled ARG1. Both these problems can be addressed by the two-stage approaches based on lattice or N-best rescoring discussed in Ch. 9: having the classifier assign multiple labels to each constituent, each with a probability, and using a second global optimization pass to pick the best label sequence.

Instead of using parses as input, it is also possible to do semantic role labeling directly from raw (or part-of-speech tagged) text by applying the chunking techniques used for named entity extraction or partial parsing. Such techniques are particularly useful in domains such as bioinformatics where it is unlikely that syntactic parsers trained on typical newswire text will perform well.

Finally, semantic role labeling systems have been generally evaluated by requiring that each argument label must be assigned to the exactly correct word sequence or parse constituent. Precision, recall, and F-measure can then be computed. A simple rule-based system can be used as a baseline, for example tagging the first NP before the predicate as ARG0 and the first NP after the predicate as ARG1, and switching these if the verb phrase is passive.

20.10 ADVANCED: UNSUPERVISED SENSE DISAMBIGUATION

Let's briefly return to the WSD task. It is expensive and difficult to build large corpora in which each word is labeled for its word sense. For this reason, unsupervised approaches to sense disambiguation are an exciting and important research area.

In unsupervised approaches, we don’t use human-defined word senses. Instead, the set of ‘senses’ of each word are created automatically from the instances of each word in the training set. Let’s introduce a simplified version of the methods of Schütze’s (Schütze, 1992b, 1998) on unsupervised sense disambiguation. In Schütze’s method, we first represent each instance of a word in the training set by distributional context feature-vectors that are a slight generalization of the feature vectors we defined in Sec. 20.7. (It is for this reason that we turned to unsupervised sense disambiguation only after introducing word similarity.)

As in Sec. 20.7 we will represent a word $w$ as a vector based on frequencies of its neighboring words. For example for a given target word (type) $w$, we might select 1000 words that occur most frequently within 25 words of any instance of $w$. These 1000 words become the dimension of the vector. Let's define $f_{i}$ to mean the frequency with which word $i$ occurs in the context of word $w$. We define the word vector $\vec{w}$ (for a given token (observation) of $w$) as:

$$ \vec{w}=\left(f_{1},f_{2},f_{3},\cdots,f_{1000}\right) $$

So far this is just a version of the distributional context we saw in Sec. 20.7. We can also use a slightly more complex version of the distributional context. For example, Schuetze defines the \textit{context vector} of a word w not as this first-order vector, but instead by its \textit{second order co-occurrence}. That is, the context vector for a word w is built by taking each word x in the context of w, for each x computing its word vector $ \vec{x} $, and then taking the centroid (average) of the vectors $ \vec{x} $.

Let's see how we use these context vectors (whether first-order or second-order) in unsupervised sense disambiguation of a word w. In training, we'll need only 3 steps:

1. For each token $ w_i $ of word w in a corpus, compute a context vector $ \vec{c} $.

2. Use a clustering algorithm to cluster these word token context vectors $ \vec{c} $ into a predefined number of groups or clusters. Each cluster defines a sense of w.

3. Compute the vector centroid of each cluster. Each vector centroid $ \vec{s}_j $ is a sense vector representing that sense of w.

Since this is an unsupervised algorithm we won't have names for each of these 'senses' of w; we just refer to the jth sense of w.

Now how do we disambiguate a particular token t of w? Again we have three steps:

1. Compute a context vector $ \vec{c} $ for t as discussed above.

2. Retrieve all sense vectors $ s_{j} $ for w.

3. Assign t to the sense represented by the sense vector $ s_{j} $ that is closest to t.

All we need is a clustering algorithm, and a distance metrics between vectors. Fortunately, clustering is a well-studied problem with a wide number of standard algorithms that can be applied to inputs structured as vectors of numerical values (Duda and Hart, 1973). A frequently used technique in language applications is known as agglomerative clustering. In this technique, each of the N training instances is initially assigned to its own cluster. New clusters are then formed in a bottom-up fashion by successively merging the two clusters that are most similar. This process continues until either a specified number of clusters is reached, or some global goodness measure among the clusters is achieved. In cases where the number of training instances makes this method too expensive, random sampling can be used on the original training set (Cutting et al., 1992) to achieve similar results.

How can we evaluate unsupervised sense disambiguation approaches? As usual, the best way is to do extrinsic or in vivo evaluation, in which the WSD algorithm is embedded in some end-to-end system. Intrinsic evaluation can also be useful, though, if we have some way to map the automatically derived sense classes into some handlabeled gold standard set, so that we can compare a hand-labeled test set with a set labeled by our unsupervised classifier. One way of doing this mapping is to map each sense cluster to a pre-defined sense by choosing the sense that (in some training set) has the most word tokens overlapping with the cluster. Another is to consider all pairs of words in the test set, testing for each whether both the system and the hand-labeling put both members of the pair in the same cluster or not.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

Word sense disambiguation traces its roots to some of the earliest applications of digital computers. We saw above Warren Weaver's (1955) suggestion to disambiguate a word by looking at a small window around it, in the context of machine translation. Other notions first proposed in this early period include the use of a thesaurus for disambiguation (Masterman, 1957), supervised training of Bayesian models for disambiguation (Madhu and Lytel, 1965), and the use of clustering in word sense analysis (Sparck Jones, 1986).

An enormous amount of work on disambiguation has been conducted within the context of early AI-oriented natural language processing systems. While most natural language analysis systems of this type exhibited some form of lexical disambiguation capability, a number of these efforts made word sense disambiguation a larger focus of their work. Among the most influential efforts were the efforts of Quillian (1968) and Simmons (1973) with semantic networks, the work of Wilks with Preference Semantics Wilks (1975c, 1975b, 1975a), and the work of Small and Rieger (1982) and Riesbeck (1975) on word-based understanding systems. Hirst's ABSTY system (First and Charniak, 1982; Hirst, 1987, 1988), which used a technique based on semantic networks called marker passing, represents the most advanced system of this type. As with these largely symbolic approaches, most connectionist approaches to word sense disambiguation have relied on small lexicons with hand-coded representations (Cottrell, 1985; Kawamoto, 1988).

Considerable work on sense disambiguation has been conducted in the areas of Cognitive Science and psycholinguistics. Appropriately enough, it is generally described using a different name: lexical ambiguity resolution. Small et al. (1988) present a variety of papers from this perspective.

The earliest implementation of a robust empirical approach to sense disambiguation is due to Kelly and Stone (1975) who directed a team that hand-crafted a set of disambiguation rules for 1790 ambiguous English words. Lesk (1986) was the first to use a machine readable dictionary for word sense disambiguation. Wilks et al. (1996) describe extensive explorations of the use of machine readable dictionaries. The problem of dictionary senses being too fine-grained or lacking an appropriate organization has been addressed with models of clustering word senses Dolan (1994), Peters et al. (1998), Chen and Chang (1998), Mihalcea and Moldovan (2001), Agirre and de Lacalle (2003), Chklovski and Mihalcea (2003), Palmer et al. (2004), McCarthy (2006), Navigli (2006), Snow et al. (2007); corpora with clustered word senses for training clustering algorithms include Palmer et al. (2006) and OntoNotes (Hovy et al., 2006).

Modern interest in supervised machine learning approaches to disambiguation began with Black (1988), who applied decision tree learning to the task. The need for large amounts of annotated text in these methods led to investigations into the use of bootstrapping methods (Hearst, 1991; Yarowsky, 1995). The problem of how to weigh and combine disparate sources of evidence is explored in Ng and Lee (1996), McRoy (1992), and Stevenson and Wilks (2001).

Among the semi-supervised methods, more recent models of selectional prefer-

ence include Li and Abe (1998), Ciaramita and Johnson (2000), McCarthy and Carroll (2003), Light and Greiff (2002). Diab and Resnik (2002) give a semi-supervised algorithm for sense disambiguation based on aligned parallel corpora in two languages. For example, the fact that the French word catastrophe might be translated as English disaster in one instance and tragedy in another instance can be used to disambiguate the senses of the two English words (i.e. to choose senses of disaster and tragedy that are similar). Abney (2002, 2004) explores the mathematical foundations of the Yarowsky algorithm and its relation to co-training. The most-frequent-sense heuristic is an extremely powerful one, but requires large amounts of supervised training data. McCarthy et al. (2004) propose an unsupervised way to automatically estimate the most frequent sense, based on the thesaurus similarity metrics defined in Sec. 20.6.

The earliest attempt to use clustering in the study of word senses is due to Sparck Jones (1986). Zernik (1991) successfully applied a standard information retrieval clustering algorithm to the problem, and provided an evaluation based on improvements in retrieval performance. More extensive recent work on clustering can be found in Pedersen and Bruce (1997) and Schütze (1997, 1998).

A few algorithms have attempted to exploit the power of mutually disambiguating all the words in a sentence, either by multiple passes (Kelly and Stone, 1975) to take advantage of easily disambiguated words, or by parallel search (Cowie et al., 1992; Veronis and Ide, 1990).

Recent work has focused on ways to use the web for training data for word sense disambiguation, either unsupervised (Mihalcea and Moldovan, 1999) or by using volunteers to label data (Chklovski and Mihalcea, 2002).

Resnik (2006) describes potential applications of WSD. One recent application has been to improve machine translation Chan et al. (2007), Carpuat and Wu (2007).

Agirre and Edmonds (2006) is a comprehensive edited volume that summarizes the state of the art in WSD. Ide and Veronis (1998a) provide a comprehensive review of the history of word sense disambiguation up to 1998. Ng and Zelle (1997) provide a more focused review from a machine learning perspective. Wilks et al. (1996) describe dictionary and corpus experiments, along with detailed descriptions of very early work.

The models of distributional word similarity we discussed arose out of research in linguistics and psychology of the 1950's. The idea that meaning was related to distribution of words in context was widespread in linguistic theory of the 1950's; even before the well-known Firth (1957) and Harris (1968) dictums discussed earlier, Joos (1950) stated that

the linguist's 'meaning' of a morpheme...is by definition the set of conditional probabilities of its occurrence in context with all other morphemes'

The related idea that the meaning of a word could be modeled as a point in a Euclidean space, and that the similarity of meaning between two words could be modeled as the distance between these points, was proposed in psychology by Osgood et al. (1957). The application of these ideas in a computational framework was first made by Sparck Jones (1986), and became a core principle of information retrieval, from whence it came into broader use in speech and language processing.

There are a wide variety of other weightings and methods for word similarity. The largest class of methods not discussed in this chapter are the variants to and details of the information-theoretic methods like Jensen-Shannon divergence, KL-divergence

and $ \alpha $-skew divergence that we briefly introduced (Pereira et al., 1993; Dagan et al., 1994, 1999; Lee, 1999, 2001); there are also other metrics from Hindle (1990) and Lin (1998a). Alternative paradigms include the co-occurrence retrieval model (Weeds, 2003; Weeds and Weir, 2005). Manning and Schütze (1999, Chapter 5 and 8) give collocation measures and other related similarity measures. A commonly used weighting is weighted mutual information (Fung and McKeown, 1997) in which the pointwise mutual information is weighted by the joint probability. In information retrieval the TF/IDF weight is widely used, as we will see in Ch. 23. See Dagan (2000), Mohammad and Hirst (2005), Curran (2003) and Weeds (2003) for good summaries of distributional similarity.

An alternative vector space model of semantic similarity, Latent Semantic Indexing (LSI) or Latent Semantic Analysis (LSA), uses singular value decomposition to reduce the dimensionality of the vector space with the intent of discovering higher-order regularities (Deerwester et al., 1990). We have already discussed Schütze (1992b), another semantic similarity model based on singular value decomposition.

There is a wide variety of recent literature on other lexical relations and thesaurus induction. The use of distributional word similarity for thesaurus induction was explored systematically by Grefenstette (1994). A wide variety of distributional clustering algorithms have been applied to the task of discovering groupings of semantically similar words, including hard clustering (Brown et al., 1992), soft clustering (Pereira et al., 1993), as well as new algorithms like Clustering By Committee (CBC) (Lin and Pantel, 2002). For particular relations, Lin et al. (2003) applied hand-crafted patterns to find antonyms, with the goal of improving synonym-detection. The distributional word similarity algorithms from Sec. 20.7 often incorrectly assign high similarity to antonyms. Lin et al. (2003) showed that words appearing in the patterns from X to Y or either X or Y tended to be antonyms. Girju et al. (2003, 2006) show improvements in meronym extraction by learning generalizations about the semantic superclasses of the two nouns. Chklovski and Pantel (2004) used hand-built patterns to extract fine-grained relations between verbs such as strength. Much recent work has focused on thesaurus induction by combining different relation extractors. Pantel and Ravichandran (2004), for example, extend Caraballo's algorithm for combining similarity and hyponymy information, while Snow et al. (2006) integrate multiple relation extractors to compute the most probable thesaurus structure. Recent work on similarity focuses on the use of the Web, for example relying on Wikipedia Strube and Ponzetto (2006), Gabrilovich and Markovitch (2007); this Web-based work is also closely related to unsupervised information extraction; see Ch. 22 and references like Etzioni et al. (2005).

While not as old as a field as word similarity or sense disambiguation, semantic role labeling has a long history in computational linguistics. The earliest work on semantic role labeling (Simmons, 1973) first parsed a sentence using an ATN parser. Each verb then had a set of rules specifying how the parse should be mapped to semantic roles. These rules mainly made reference to grammatical functions (subject, object, complement of specific prepositions), but also checked constituent-internal features such as the animacy of head nouns.

Statistical work in the area revived in 2000 after the FrameNet and PropBank project had created databases large enough and consistent enough to make training and testing possible. Many popular features used for role labeling are defined in Gildea and

Jurafsky (2002), Chen and Rambow (2003), Surdeanu et al. (2003), Xue and Palmer (2004), Pradhan et al. (2003, 2005).

To avoid the need for huge labeled training sets, recent work has focused on unsupervised approaches for semantic role labeling (Swier and Stevenson, 2004).

The semantic labeling work described above focuses on labeling each sentence token in a corpus with semantic roles. An alternative approach to semantic role labeling focuses on lexicon learning, using unsupervised learning on a corpus to learn the kinds of semantic classes a verb can belong to in terms of its possible semantic roles or argument alternation patterns (Stevenson and Merlo, 1999; Schulte im Walde, 2000; Merlo and Stevenson, 2001; Merlo et al., 2001; Grenager and Manning, 2006).

EXERCISES

20.1 Collect a small corpus of example sentences of varying lengths from any newspaper or magazine. Using WordNet, or any standard dictionary, determine how many senses there are for each of the open-class words in each sentence. How many distinct combinations of senses are there for each sentence? How does this number seem to vary with sentence length?

20.2 Using WordNet, or a standard reference dictionary, tag each open-class word in your corpus with its correct tag. Was choosing the correct sense always a straightforward task. Report on any difficulties you encountered.

20.3 Using the same corpus, isolate the words taking part in all the verb-subject and verb-object relations. How often does it appear to be the case that the words taking part in these relations could be disambiguated using only information about the words in the relation?

20.4 Between the words eat and find which would you expect to be more effective in selectional restriction-based sense disambiguation? Why?

20.5 Using your favorite dictionary, simulate the Original Lesk word overlap dis-

ambiguation algorithm described on page 11 on the phrase Time flies like an arrow.

Assume that the words are to be disambiguated one at a time, from left to right, and

that the results from earlier decisions are used later in the process.

20.6 Build an implementation of your solution to the previous exercise. Using WordNet, implement the Original Lesk word overlap disambiguation algorithm described on page 11 on the phrase Time flies like an arrow.

20.7 Implement and experiment with a decision-list sense disambiguation system. As a model, use the kinds of features shown in Figure 20.2. Use one of the publicly available decision-list packages like WEKA (or see Russell and Norvig (1995) for more details on implementing decision-list learning yourself). To facilitate evaluation of your system, you should obtain one of the freely available sense-tagged corpora.

20.8 Evaluate two or three of the similarity methods from the publicly available Wordnet::Similarity package (Pedersen et al., 2004). You might do this by

hand-labeling some word pairs with similarity scores and seeing how well the algorithms approximate your hand labels.

20.9 Implement a distributional word similarity algorithm that can take different measures of association and different measures of vector similarity. Now evaluate two measures of association and two measures of vector similarity from Fig. 20.13. Again, you might do this by hand-labeling some word pairs with similarity scores and seeing how well the algorithms approximate your hand labels.

Abney, S. P. (2002). Bootstrapping. In ACL-02.

Abney, S. P. (2004). Understanding the Yarowsky algorithm. Computational Linguistics, 30(3), 365–395.

Agirre, E. and de Lacalle, O. L. (2003). Clustering wordnet word senses. In RANLP 2003.

Agirre, E. and Edmonds, P. (Eds.). (2006). Word Sense Disambiguation: Algorithms and Applications. Kluwer.

Atkins, S. (1993). Tools for computer-aided corpus lexicography: The Hector project. Acta Linguistica Hungarica, 41, 5–72.

Banerjee, S. and Pedersen, T. (2003). Extended gloss overlaps as a measure of semantic relatedness. In IJCAI 2003, pp. 805–810.

Black, E. (1988). An experiment in computational discrimination of English word senses. IBM Journal of Research and Development, 32(2), 185–194.

Brin, S. (1998). Extracting patterns and relations from the World Wide Web. In Proceedings World Wide Web and Databases International Workshop, Number 1590 in LNCS, pp. 172–183. Springer.

Brown, P. F., Della Pietra, V. J., de Souza, P. V., Lai, J. C., and Mercer, R. L. (1992). Class-based n-gram models of natural language. Computational Linguistics, 18(4), 467–479.

Bruce, R. and Wiebe, J. (1994). Word-sense disambiguation using decomposable models. In Proceedings of the 32nd ACL, Las Cruces, NM, pp. 139–145.

Budanitsky, A. and Hirst, G. (2001). Semantic distance in WordNet: An experimental, application-oriented evaluation of five measures. In Proceedings of the NAACL 2001 Workshop on WordNet and Other Lexical Resources, Pittsburgh, PA.

Budanitsky, A. and Hirst, G. (2006). Evaluating wordnet-based measures of lexical semantic relatedness. Computational Linguistics, 32(1), 13–47.

Caraballo, S. A. (1999). Automatic construction of a hypernym-labeled noun hierarchy from text. In ACL-99, College Park, MD. ACL.

Caraballo, S. A. (2001). Automatic Acquisition of a hypernym labeled noun hierarchy from text. Ph.D. thesis, Brown University.

Carpuat, M. and Wu, D. (2007). Improving statistical machine translation using word sense disambiguation. In EMNLP/CoNLL 2007, Prague, Czech Republic, pp. 61–72.

Chan, Y. S., Ng, H. T., and Chiang, D. (2007). Word sense disambiguation improves statistical machine translation. In ACL-07, Prague, Czech Republic, pp. 33–40.

Charniak, E. (1997). Statistical parsing with a context-free grammar and word statistics. In AAAI-97, Menlo Park, pp. 598–603. AAAI Press.

Chen, J. N. and Chang, J. S. (1998). Topical clustering of MRD senses based on information retrieval techniques. Computational Linguistics, 24(1), 61–96.

Chen, J. and Rambow, O. (2003). Use of deep linguistic features for the recognition and labeling of semantic arguments. In EMNLP 2003, pp. 41–48.

Chklovski, T. and Mihalcea, R. (2003). Exploiting Agreement and Disagreement of Human Annotators for Word Sense Disambiguation. In RANLP 2003.

Chklovski, T. and Mihalcea, R. (2002). Building a sense tagged corpus with open mind word expert. In ACL-02 Workshop on Word Sense Disambiguation: Recent Successes and Future Directions, pp. 116–122.

Chklovski, T. and Pantel, P. (2004). Verb ocean: Mining the Web for fine-grained semantic verb relations. In EMNLP 2004, pp. 25–26.

Church, K. W. and Hanks, P. (1989). Word association norms, mutual information, and lexicography. In Proceedings of the 27th ACL, Vancouver, B.C., pp. 76–83. ACL.

Church, K. W. and Hanks, P. (1990). Word association norms, mutual information, and lexicography. Computational Linguistics, 16(1), 22–29.

Ciaramita, M. and Johnson, M. (2000). Explaining away ambiguity: learning verb selectional preference with Bayesian networks. In COLING-00, pp. 187–193. ACL.

Ciaramita, M. and Johnson, M. (2003). Supersense tagging of unknown nouns in WordNet. In EMNLP-2003, pp. 168–175. ACL.

Collins, M. (1996). A new statistical parser based on bigram lexical dependencies. In ACL-96, Santa Cruz, California, pp. 184–191.

Cottrell, G. W. (1985). A Connectionist Approach to Word Sense Disambiguation. Ph.D. thesis, University of Rochester, Rochester, NY. Revised version published in the same title by Pitman in 1989.

Cowie, J., Guthrie, J. A., and Guthrie, L. M. (1992). Lexical disambiguation using simulated annealing. In COLING-92, Nantes, France, pp. 359–365.

Curran, J. R. (2003). From Distributional to Semantic Similarity. Ph.D. thesis, University of Edinburgh.

Curran, J. R. and Moens, M. (2002). Improvements in automatic thesaurus extraction. In Proceedings of the ACL-02 workshop on Unsupervised Lexical Acquisition, Philadelphia, PA, pp. 59–66. ACL.

Cutting, D., Karger, D. R., Pedersen, J., and Tukey, J. W. (1992). Scatter/gather: A cluster-based approach to browsing large document collections. In SIGIR-92, Copenhagen, Denmark, pp. 318–329. ACM.

Dagan, I. (2000). Contextual word similarity. In Dale, R., Moisl, H., and Somers, H. (Eds.), A Handbook of Natural Language Processing: Techniques and applications for the processing of language as text. Marcel Dekker.

Dagan, I., Lee, L., and Pereira, F. C. N. (1999). Similarity-based models of cooccurrence probabilities. Machine Learning, 34(1–3), 43–69.

Dagan, I., Marcus, S., and Markovitch, S. (1993). Contextual word similarity and estimation from sparse data. In Proceedings of the 31st ACL, Columbus, Ohio, pp. 164–171.

Dagan, I., Pereira, F. C. N., and Lee, L. (1994). Similarity-base estimation of word cooccurrence probabilities. In Proceedings of the 32nd ACL, Las Cruces, NM, pp. 272–278.

Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., and Harshman, R. (1990). Indexing by latent semantic analysis. Journal of the American Society of Information Science, 41, 391–407.

Diab, M. and Resnik, P. (2002). An unsupervised method for word sense tagging using parallel corpora. In ACL-02, pp. 255–262. ACL.

Dolan, W. B. (1994). Word sense ambiguation: Clustering related senses. In COLING-94, Kyoto, Japan, pp. 712–716. ACL.

Duda, R. O. and Hart, P. E. (1973). Pattern Classification and Scene Analysis. John Wiley and Sons, New York.

Etzioni, O., Cafarella, M., Downey, D., Popescu, A., Shaked, T., Soderland, S., Weld, D., and Yates, A. (2005). Unsupervised named-entity extraction from the web: An experimental study. Artificial Intelligence, 165(1), 91–134.

Fano, R. M. (1961). Transmission of information; A statistical theory of communications. MIT Press.

Firth, J. R. (1957). A synopsis of linguistic theory 1930–1955. In Studies in Linguistic Analysis. Philological Society, Oxford. Reprinted in Palmer, F. (ed.) 1968. Selected Papers of J. R. Firth. Longman, Harlow.

Fung, P. and McKeown, K. R. (1997). A technical word and term translation aid using noisy parallel corpora across language groups. Machine Translation, 12(1-2), 53–87.

Gabrilovich, E. and Markovitch, S. (2007). Computing Semantic Relatedness using Wikipedia-based Explicit Semantic Analysis. In IJCAI-07.

Gale, W. A., Church, K. W., and Yarowsky, D. (1992a). Work on statistical methods for word sense disambiguation. In Goldman, R. (Ed.), Proceedings of the 1992 AAAI Fall Symposium on Probabilistic Approaches to Natural Language.

Gale, W. A., Church, K. W., and Yarowsky, D. (1992b). Estimating upper and lower bounds on the performance of word-sense disambiguation programs. In Proceedings of the 30th ACL, Newark, DE, pp. 249–256.

Gale, W. A., Church, K. W., and Yarowsky, D. (1992c). One sense per discourse. In Proceedings DARPA Speech and Natural Language Workshop, pp. 233–237. Morgan Kaufmann.

Gaustad, T. (2001). Statistical corpus-based word sense dis-

ambiguation: Pseudowords vs. real ambiguous words. In

ACL/EACL 2001 – Student Research Workshop, pp. 255–262.

ACL.

Gildea, D. and Jurafsky, D. (2000). Automatic labeling of semantic roles. In ACL-00, Hong Kong, pp. 512–520.

Gildea, D. and Jurafsky, D. (2002). Automatic labeling of semantic roles. Computational Linguistics, 28(3), 245–288.

Girju, R., Badulescu, A., and Moldovan, D. (2006). Automatic discovery of part-whole relations. Computational Linguistics, 31(1).

Girju, R., Badulescu, A., and Moldovan, D. (2003). Learning semantic constraints for the automatic discovery of part-whole relations. In HLT-NAACL-03, Edmonton, Canada, pp. 1–8. ACL.

Gould, S. J. (1980). The Panda's Thumb. Penguin Group, London.

Grefenstette, G. (1994). Explorations in Automatic Thesaurus Discovery. Kluwer, Norwell, MA.

Grenager, T. and Manning, C. D. (2006). Unsupervised Discovery of a Statistical Verb Lexicon. In EMNLP 2006.

Harris, Z. S. (1968). Mathematical Structures of Language. John Wiley.

Hearst, M. A. (1991). Noun homograph disambiguation. In Proceedings of the 7th Annual Conference of the University of Waterloo Centre for the New OED and Text Research, Oxford, pp. 1–19.

Hearst, M. A. (1992). Automatic acquisition of hyponyms from large text corpora. In COLING-92, Nantes, France.

Hearst, M. A. (1998). Automatic discovery of wordnet relations. In Fellbaum, C. (Ed.), Wordnet: An Electronic Lexical Database. MIT Press.

Hindle, D. (1990). Noun classification from predicate-argument structures. In Proceedings of the 28th ACL, Pittsburgh, PA, pp. 268–275. ACL.

Hirst, G. (1987). Semantic Interpretation and the Resolution of Ambiguity. Cambridge University Press.

Hirst, G. (1988). Resolving lexical ambiguity computationally with spreading activation and polaroid words. In Small, S. L., Cottrell, G. W., and Tanenhaus, M. K. (Eds.), Lexical ambiguity resolution: Perspectives from psycholinguistics, neuropsychology, and artificial intelligence, pp. 73–108. Morgan Kaufmann.

Hirst, G. and Budanitsky, A. (2005). Correcting real-word spelling errors by restoring lexical cohesion. Natural Language Engineering, 11, 87–111.

First, G. and Charniak, E. (1982). Word sense and case slot disambiguation. In AAAI-82, pp. 95–98.

Hovy, E. H., Marcus, M. P., Palmer, M., Ramshaw, L. A., and Weischedel, R. (2006). Ontonotes: The 90% solution. In HLT-NAACL-06.

Ide, N. M. and Veronis, J. (Eds.). (1998a). Computational Linguistics: Special Issue on Word Sense Disambiguation, Vol. 24. MIT Press.

Ide, N. M. and Véronis, J. (1998b). Introduction to the special issue on word sense disambiguation. Computational Linguistics, 24(1), 1–40.

Jaccard, P. (1908). Nouvelles recherches sur la distribution florale. Bulletin de la Société Vaudoise des Sciences Naturelles, 44, 223–227.

Jaccard, P. (1912). The distribution of the flora of the alpine zone. New Phytologist, 11, 37–50.

Jiang, J. J. and Conrath, D. W. (1997). Semantic similarity based on corpus statistics and lexical taxonomy. In ROCLING X, Taiwan.

Joos, M. (1950). Description of language design. Journal of the Acoustical Society of America, 22, 701–708.

Katz, J. J. and Fodor, J. A. (1963). The structure of a semantic theory. Language, 39, 170–210.

Kawamoto, A. H. (1988). Distributed representations of ambiguous words and their resolution in connectionist networks. In Small, S. L., Cottrell, G. W., and Tanenhaus, M. (Eds.), Lexical Ambiguity Resolution, pp. 195–228. Morgan Kaufman.

Kelly, E. F. and Stone, P. J. (1975). Computer Recognition of English Word Senses. North-Holland, Amsterdam.

Kilgarriff, A. (2001). English lexical sample task description. In Proceedings of Senseval-2: Second International Workshop on Evaluating Word Sense Disambiguation Systems, Toulouse, France, pp. 17–20.

Kilgarriff, A. and Palmer, M. (Eds.). (2000). Computing and the Humanities: Special Issue on SENSEVAL, Vol. 34. Kluwer.

Kilgarriff, A. and Rosenzweig, J. (2000). Framework and results for English SENSEVAL. Computers and the Humanities, 34(1-2).

Krovetz, R. (1998). More than one sense per discourse. In Proceedings of the ACL-SIGLEX SENSEVAL Workshop.

Kullback, S. and Leibler, R. A. (1951). On information and sufficiency. Annals of Mathematical Statistics, 22, 79–86.

Landauer, T. K. and Dumais, S. T. (1997). A solution to Plato's problem: The Latent Semantic Analysis theory of acquisition, induction, and representation of knowledge. Psychological Review, 104, 211–240.

Landauer, T. K., Laham, D., Rehder, B., and Schreiner, M. E. (1997). How well can passage meaning be derived without using word order: A comparison of latent semantic analysis and humans. In COGSCI-97, Stanford, CA, pp. 412–417. Lawrence Erlbaum.

Landes, S., Leacock, C., and Tengi, R. I. (1998). Building semantic concordances. In Fellbaum, C. (Ed.), WordNet: An Electronic Lexical Database, pp. 199–216. MIT Press.

Leacock, C. and Chodorow, M. S. (1998). Combining local context and WordNet similarity for word sense identification. In Fellbaum, C. (Ed.), Wordnet: An Electronic Lexical Database, pp. 265–283. MIT Press.

Leacock, C., Towell, G., and Voorhees, E. (1993). Corpus-based statistical sense resolution. In Proceedings of the ARPA Human Language Technology Workshop, pp. 260–265.

Lee, L. (1999). Measures of distributional similarity. In ACL-99, pp. 25–32.

Lee, L. (2001). On the effectiveness of the skew divergence for statistical language analysis. In Artificial Intelligence and Statistics, pp. 65–72.

Lesk, M. E. (1986). Automatic sense disambiguation using machine readable dictionaries: How to tell a pine cone from an ice cream cone. In Proceedings of the Fifth International Conference on Systems Documentation, Toronto, CA, pp. 24–26. ACM.

Li, H. and Abe, N. (1998). Generalizing case frames using a thesaurus and the MDL principle. Computational Linguistics, 24(2), 217–244.

Light, M. and Greiff, W. (2002). Statistical models for the induction and use of selectional preferences. Cognitive Science, 87, 1–13.

Lin, D. (1998a). Automatic retrieval and clustering of similar words. In COLING/ACL-98, Montreal, pp. 768–774.

Lin, D. (1998b). An information-theoretic definition of similarity. In ICML 1998, San Francisco, pp. 296–304.

Lin, D. (2007). Dependency-based word similarity demo. http://www.cs.ualberta.ca/~lindek/demos.htm.

Lin, D. and Pantel, P. (2002). Concept discovery from text. In COLING-02, pp. 1–7.

Lin, D., Zhao, S., Qin, L., and Zhou, M. (2003). Identifying synonyms among distributionally similar words. In IJCAI-03, pp. 1492–1493.

Madhu, S. and Lytel, D. (1965). A figure of merit technique for the resolution of non-grammatical ambiguity. Mechanical Translation, 8(2), 9–13.

Manning, C. D. and Schütze, H. (1999). Foundations of Statistical Natural Language Processing. MIT Press.

Masterman, M. (1957). The thesaurus in syntax and semantics. Mechanical Translation, 4(1), 1–2.

McCarthy, D. (2006). Relating wordnet senses for word sense disambiguation. In Proceedings of ACL Workshop on Making Sense of Sense.

McCarthy, D. and Carroll, J. (2003). Disambiguating nouns, verbs, and adjectives using automatically acquired selectional preferences. Computational Linguistics, 29(4), 639–654.

McCarthy, D., Koeling, R., Weeds, J., and Carroll, J. (2004). Finding predominant word senses in untagged text. In ACL-04, pp. 279–286.

McRoy, S. (1992). Using multiple knowledge sources for word sense discrimination. Computational Linguistics, 18(1), 1–30.

Merlo, P. and Stevenson, S. (2001). Automatic verb classification based on statistical distribution of argument structure. Computational Linguistics, 27(3), 373–408.

Merlo, P., Stevenson, S., Tsang, V., and Allaria, G. (2001). A multilingual paradigm for automatic verb classification. In ACL-02, pp. 207–214.

Mihalcea, R. and Moldovan, D. (2001). Automatic generation of a coarse grained WordNet. In NAACL Workshop on WordNet and Other Lexical Resources.

Mihalcea, R. and Moldovan, D. (1999). An automatic method for generating sense tagged corpora. In Proceedings of AAAI, pp. 461–466.

Miller, G. A. and Charles, W. G. (1991). Contextual correlates of semantics similarity. Language and Cognitive Processes, 6(1), 1–28.

Miller, G. A., Leacock, C., Tengi, R., and Bunker, R. T. (1993). A semantic concordance. In Proceedings ARPA Workshop on Human Language Technology, pp. 303–308. ACL.

Mohammad, S. and Hirst, G. (2005). Distributional measures as proxies for semantic relatedness. Submitted.

Nakov, P. I. and Hearst, M. A. (2003). Category-based pseudowords. In HLT-NAACL-03, Edmonton, Canada. ACL.

Navigli, R. (2006). Meaningful clustering of senses helps boost word sense disambiguation performance. In COLING/ACL 2006, pp. 105–112.

Ng, H. T. and Lee, H. B. (1996). Integrating multiple knowledge sources to disambiguate word senses: An exemplar-based approach. In ACL-96, Santa Cruz, CA, pp. 40–47. ACL.

Ng, H. T. and Zelle, J. (1997). Corpus-based approaches to semantic interpretation in NLP. AI Magazine, 18(4), 45–64.

Osgood, C. E., Suci, G. J., and Tannenbaum, P. H. (1957). The Measurement of Meaning. University of Illinois Press, Urbana, IL.

Palmer, M., Dang, H. T., and Fellbaum, C. (2006). Making fine-grained and coarse-grained sense distinctions, both manually and automatically. Natural Language Engineering, 13(2), 137–163.

Palmer, M., Babko-Malaya, O., and Dang, H. T. (2004). Different sense granularities for different applications. In HLTNAACL Workshop on Scalable Natural Language Understanding, Boston, MA, pp. 49–56.

Palmer, M., Fellbaum, C., Cotton, S., Delfs, L., and Dang, H. T. (2001). English tasks: All-words and verb lexical sample. In Proceedings of Senseval-2: Second International Workshop on Evaluating Word Sense Disambiguation Systems, Toulouse, France, pp. 21–24.

Palmer, M., Ng, H. T., and Dang, H. T. (2006). Evaluation of wsd systems. In Agirre, E. and Edmonds, P. (Eds.), Word Sense Disambiguation: Algorithms and Applications. Kluwer.

Pantel, P. and Ravichandran, D. (2004). Automatically labeling semantic classes. In HLT-NAACL-04, Boston, MA.

Patwardhan, S., Banerjee, S., and Pedersen, T. (2003). Using measures of semantic relatedness for word sense disambiguation. In Proceedings of the Fourth International Conference on Intelligent Text Processing and Computational Linguistics, pp. 241–257. Springer.

Pedersen, T. and Bruce, R. (1997). Distinguishing word senses in untagged text. In EMNLP 1997, Providence, RI.

Pedersen, T., Patwardhan, S., and Michelizzi, J. (2004). WordNet::Similarity – Measuring the relatedness of concepts. In HLT-NAACL-04.

Pereira, F. C. N., Tishby, N., and Lee, L. (1993). Distributional clustering of English words. In Proceedings of the 31st ACL, Columbus, Ohio, pp. 183–190.

Peters, W., Peters, I., and Vossen, P. (1998). Automatic sense clustering in EuroWordNet. In LREC-98, Granada, Spain, pp. 447–454.

Pradhan, S., Hacioglu, K., Ward, W., Martin, J., and Jurafsky, D. (2003). Semantic role parsing: Adding semantic structure to unstructured text. In Proceedings of the International Conference on Data Mining (ICDM-2003).

Pradhan, S., Ward, W., Hacioglu, K., Martin, J., and Jurafsky, D. (2005). Semantic role labeling using different syntactic views. In ACL-05, Ann Arbor, MI. ACL.

Quillian, M. R. (1968). Semantic memory. In Minsky, M. (Ed.), Semantic Information Processing, pp. 227–270. MIT Press.

Resnik, P. (1995). Using information content to evaluate semantic similarity in a taxonomy. In International Joint Conference for Artificial Intelligence (IJCAI-95), pp. 448–453.

Resnik, P. (1996). Selectional constraints: An information-theoretic model and its computational realization. Cognition, 61, 127–159.

Resnik, P. (1997). Selectional preference and sense disambiguation. In Proceedings of ACL SIGLEX Workshop on Tagging Text with Lexical Semantics, Washington, D.C., pp. 52–57.

Resnik, P. (1998). Wordnet and class-based probabilities. In Fellbaum, C. (Ed.), WordNet: An Electronic Lexical Database. MIT Press.

Resnik, P. (2006). Word sense disambiguation in nlp applications. In Agirre, E. and Edmonds, P. (Eds.), Word Sense Disambiguation: Algorithms and Applications. Kluwer.

Riesbeck, C. K. (1975). Conceptual analysis. In Schank, R. C. (Ed.), Conceptual Information Processing, pp. 83–156. American Elsevier, New York.

Riloff, E. (1996). Automatically generating extraction patterns from untagged text. In AAAI-96, pp. 117–124.

Rivest, R. L. (1987). Learning decision lists. Machine Learning, 2(3), 229–246.

Rubenstein, H. and Goodenough, J. B. (1965). Contextual correlates of synonymy. Communications of the ACM, 8(10), 627–633.

Russell, S. and Norvig, P. (1995). Artificial Intelligence: A Modern Approach. Prentice Hall.

Schulte im Walde, S. (2000). Clustering verbs semantically according to their alternation behaviour. In COLING-00, Saarbrücken, Germany, pp. 747–753.

Schütze, H. (1992a). Context space. In Goldman, R. (Ed.), Proceedings of the 1992 AAAI Fall Symposium on Probabilistic Approaches to Natural Language.

Schütze, H. (1992b). Dimensions of meaning. In Proceedings of Supercomputing '92, pp. 787–796. IEEE Press.

Schütze, H. (1997). Ambiguity Resolution in Language Learning: Computational and Cognitive Models. CSLI Publications, Stanford, CA.

Schütze, H. (1998). Automatic word sense discrimination. Computational Linguistics, 24(1), 97–124.

Simmons, R. F. (1973). Semantic networks: Their computation and use for understanding English sentences. In Schank, R. C. and Colby, K. M. (Eds.), Computer Models of Thought and Language, pp. 61–113. W.H. Freeman and Co., San Francisco.

Small, S. L., Cottrell, G. W., and Tanenhaus, M. (Eds.). (1988). Lexical Ambiguity Resolution. Morgan Kaufman.

Small, S. L. and Rieger, C. (1982). Parsing and comprehending with Word Experts. In Lehnert, W. G. and Ringle, M. H. (Eds.), Strategies for Natural Language Processing, pp. 89–147. Lawrence Erlbaum.

Snow, R., Jurafsky, D., and Ng, A. Y. (2005). Learning syntactic patterns for automatic hypernym discovery. In Saul, L. K., Weiss, Y., and Bottou, L. (Eds.), NIPS 17, pp. 1297–1304. MIT Press.

Snow, R., Jurafsky, D., and Ng, A. Y. (2006). Semantic taxonomy induction from heterogenous evidence. In COLING/ACL 2006.

Snow, R., Prakash, S., Jurafsky, D., and Ng, A. Y. (2007). Learning to merge word senses. In EMNLP/CoNLL 2007, pp. 1005–1014.

Sparck Jones, K. (1986). Synonymy and Semantic Classification. Edinburgh University Press, Edinburgh. Republication of 1964 PhD Thesis.

Stevenson, M. and Wilks, Y. (2001). The interaction of knowledge sources in word sense disambiguation. Computational Linguistics, 27(3), 321–349.

Stevenson, S. and Merlo, P. (1999). Automatic verb classification using distributions of grammatical features. In EACL-99, Bergen, Norway, pp. 45–52.

Strube, M. and Ponzetto, S. P. (2006). WikiRelate! Computing semantic relatedness using Wikipedia. In AAAI-06, pp. 1419–1424.

Surdeanu, M., Harabagiu, S., Williams, J., and Aarseth, P. (2003). Using predicate-argument structures for information extraction. In ACL-03, pp. 8–15.

Swier, R. and Stevenson, S. (2004). Unsupervised semantic role labelling. In EMNLP 2004, pp. 95–102.

Tseng, H. (2003). Semantic classification of Chinese unknown words. In ACL-03, pp. 72–79. ACL.

Turney, P., Littman, M., Bigham, J., and Shnayder, V. (2003). Combining independent modules to solve multiple-choice synonym and analogy problems. In Proceedings of RANLP-03, Borovets, Bulgaria, pp. 482–489.

Vasilescu, F., Langlais, P., and Lapalme, G. (2004). Evaluating variants of the lesk approach for disambiguating words. In LREC-04, Lisbon, Portugal, pp. 633–636. ELRA.

Veronis, J. and Ide, N. M. (1990). Word sense disambiguation with very large neural networks extracted from machine readable dictionaries. In COLING-90, Helsinki, Finland, pp. 389–394.

Weaver, W. (1949/1955). Translation. In Locke, W. N. and Boothe, A. D. (Eds.), Machine Translation of Languages, pp.

15–23. MIT Press. Reprinted from a memorandum written by Weaver in 1949.

Weeds, J. (2003). Measures and Applications of Lexical Distributional Similarity. Ph.D. thesis, University of Sussex.

Weeds, J. and Weir, D. (2005). Co-occurrence retrieval: a general framework for lexical distributional similarity. Computational Linguistics, 31(4), 439–476.

Wilks, Y. (1975a). An intelligent analyzer and understander of English. Communications of the ACM, 18(5), 264–274.

Wilks, Y. (1975b). Preference semantics. In Keenan, E. L. (Ed.), The Formal Semantics of Natural Language, pp. 329–350. Cambridge Univ. Press.

Wilks, Y. (1975c). A preferential, pattern-seeking, semantics for natural language inference. Artificial Intelligence, 6(1), 53–74.

Wilks, Y. (1978). Making preferences more active. Artificial Intelligence, 11(3), 197–223.

Wilks, Y., Slator, B. M., and Guthrie, L. M. (1996). Electric Words: Dictionaries, Computers, and Meanings. MIT Press.

Wu, Z. and Palmer, M. (1994). Verb semantics and lexical selection. In Proceedings of the 32nd ACL, Las Cruces, NM, pp. 133–138.

Xue, N. and Palmer, M. (2004). Calibrating features for semantic role labeling. In EMNLP 2004.

Yarowsky, D. (1994). Decision lists for lexical ambiguity resolution: Application to accent restoration in Spanish and French. In Proceedings of the 32nd ACL, Las Cruces, NM, pp. 88–95. ACL.

Yarowsky, D. (1995). Unsupervised word sense disambiguation rivaling supervised methods. In ACL-95, Cambridge, MA, pp. 189–196. ACL.

Yarowsky, D. (1997). Homograph disambiguation in text-to-speech synthesis. In van Santen, J. P. H., Sproat, R., Olive, J. P., and Hirschberg, J. (Eds.), Progress in Speech Synthesis, pp. 157–172. Springer.

Yuret, D. (2004). Some experiments with a Naive Bayes WSD system. In Senseval-3: Third International Workshop on the Evaluation of Systems for the Semantic Analysis of Text.

Zernik, U. (1991). Train1 vs. train2: Tagging word senses in corpus. In Lexical Acquisition: Exploiting On-Line Resources to Build a Lexicon, pp. 91–112. Lawrence Erlbaum.

21 COMPUTATIONAL DISCOURSE

Gracie: Oh yeah... and then Mr. and Mrs. Jones were having matrimonial trouble, and my brother was hired to watch Mrs. Jones.

George: Well, I imagine she was a very attractive woman.

Gracie: She was, and my brother watched her day and night for six months.

George: Well, what happened?

Gracie: She finally got a divorce.

George: Mrs. Jones?

Gracie: No, my brother's wife.

George Burns and Gracie Allen in The Salesgirl

Orson Welles' movie Citizen Kane was groundbreaking in many ways, perhaps most notably in its structure. The story of the life of fictional media magnate Charles Foster Kane, the movie does not proceed in chronological order through Kane's life. Instead, the film begins with Kane's death, (famously murmuring "Rosebud"), and is structured around flashbacks to his life inserted among scenes of a reporter investigating his death. The novel idea that the structure of a movie does not have to linearly follow the structure of the real timeline made apparent for 20th century cinematography the infinite possibilities and impact of different kinds of coherent narrative structures.

But coherent structure is not just a fact about movies, or works of art. Up to this point of the book, we have focused primarily on language phenomena that operate at the word or sentence level. But just like movies, language does not normally consist of isolated, unrelated sentences, but instead of collocated, structured, coherent groups of sentences. We refer to such a coherent structured group of sentences as a discourse.

The chapter you are now reading is an example of a discourse. It is in fact a discourse of a particular sort: a monologue. Monologues are characterized by a speaker (a term which will be used to include writers, as it is here), and a hearer (which, analogously, includes readers). The communication flows in only one direction in a monologue, that is, from the speaker to the hearer.

After reading this chapter, you may have a conversation with a friend about it, which would consist of a much freer interchange. Such a discourse is called a dialogue, specifically a human-human dialogue. In this case, each participant periodically takes

turns being a speaker and hearer. Unlike a typical monologue, dialogues generally consist of many different types of communicative acts: asking questions, giving answers, making corrections, and so forth.

You may also, for some purposes, such as booking an airline or train trip, have a conversation with a computer conversational agent. This use of human-computer dialogue for human-computer interaction, or HCI has properties that distinguish it from normal human-human dialogue, in part due to the present-day limitations on the ability of computer systems to participate in free, unconstrained conversation.

While many discourse processing problems are common to these three forms of discourse, they differ in enough respects that different techniques have often been used to process them. This chapter focuses on techniques commonly applied to the interpretation of monologues; techniques for conversational agents and other dialogues will be described in Ch. 24.

Language is rife with phenomena that operate at the discourse level. Consider the discourse shown in example (21.1).

The Tin Woodman went to the Emerald City to see the Wizard of Oz and ask for a heart. After he asked for it, the Woodman waited for the Wizard's response.

What do pronouns such as he and it denote? No doubt the reader had little trouble figuring out that he denotes the Tin Woodman and not the Wizard of Oz, and that it denotes the heart and not the Emerald City. Furthermore, it is clear to the reader that the Wizard is the same entity as the Wizard of Oz, and the Woodman is the same as the Tin Woodman.

But doing this disambiguation automatically is a difficult task. This goal of deciding what pronouns and other noun phrases refer to is called coreference resolution. Coreference resolution is important for information extraction, summarization, and for conversational agents. In fact, it turns out that just about any conceivable language processing application requires methods for determining the denotations of pronouns and related expressions.

There are other important discourse structures beside the relationships between pronouns and other nouns. Consider the task of summarizing the following news passage:

First Union Corp is continuing to wrestle with severe problems. According to industry insiders at Paine Webber, their president, John R. Georgius, is planning to announce his retirement tomorrow.

We might want to extract a summary like the following:

First Union President John R. Georgius is planning to announce his retirement tomorrow.

In order to build such a summary, we need to know that the second sentence is the more important of the two, and that the first sentence is subordinate to it, just giving background information. Relationships of this sort between sentences in a discourse are called coherence relations, and determining the coherence structures between discourse sentences is an important discourse task.

Since coherence is also a property of a good text, automatically detecting coherence relations is also useful for tasks that measure text quality, like automatic essay

grading. In automatic essay grading, short student essays are assigned a grade by measuring the internal coherence of the essay as well as comparing its content to source material and hand-labeled high-quality essays. Coherence is also used to evaluate the output quality of natural language generation systems.

Discourse structure and coreference are related in deep ways. Notice that in order to perform the summary above, a system must correctly identify First Union Corp as the denotation of their (as opposed to Paine Webber, for instance). Similarly, it turns out that determining the discourse structure can help in determining coreference.

Coherence

Let's conclude this introduction by discussing what it means for a text to be coherent. Assume that you have collected an arbitrary set of well-formed and independently interpretable utterances, for instance, by randomly selecting one sentence from each of the previous chapters of this book. Do you have a discourse? Almost certainly not. The reason is that these utterances, when juxtaposed, will not exhibit coherence. Consider, for example, the difference between passages (21.4) and (21.5).

(21.4) John hid Bill's car keys. He was drunk.

(21.5) ?? John hid Bill's car keys. He likes spinach.

While most people find passage (21.4) to be rather unremarkable, they find passage (21.5) to be odd. Why is this so? Like passage (21.4), the sentences that make up passage (21.5) are well formed and readily interpretable. Something instead seems to be wrong with the fact that the sentences are juxtaposed. The hearer might ask, for instance, what hiding someone's car keys has to do with liking spinach. By asking this, the hearer is questioning the coherence of the passage.

Alternatively, the hearer might try to construct an explanation that makes it coherent, for instance, by conjecturing that perhaps someone offered John spinach in exchange for hiding Bill's car keys. In fact, if we consider a context in which we had known this already, the passage now sounds a lot better! Why is this? This conjecture allows the hearer to identify John's liking spinach as the cause of his hiding Bill's car keys, which would explain how the two sentences are connected. The very fact that hearers try to identify such connections is indicative of the need to establish coherence as part of discourse comprehension.

In passage (21.4), or in our new model of passage (21.5), the second sentence offers the reader an EXPLANATION or CAUSE for the first sentence. These examples show that a coherent discourse must have meaningful connections between its utterances, connections like EXPLANATION that are often called coherence relations and will be introduced in Sec. 21.2.

Let's introduce a second aspect of coherence by considering the following two texts from Grosz et al. (1995a):

a. John went to his favorite music store to buy a piano.

b. He had frequented the store for many years.

c. He was excited that he could finally buy a piano.

d. He arrived just as the store was closing for the day.

(21.7) a. John went to his favorite music store to buy a piano.

b. It was a store John had frequented for many years.

c. He was excited that he could finally buy a piano.

d. It was closing just as John arrived.

While these two texts differ only in how the two entities (John and the store) are realized in the sentences, the discourse in (21.6) is intuitively more coherent than the one in (21.7). As Grosz et al. (1995a) point out, this is because the discourse in (21.6) is clearly about one individual, John, describing his actions and feelings. The discourse in (21.7), by contrast, focuses first on John, then the store, then back to John, then to the store again. It lacks the ‘aboutness’ of the first discourse.

These examples show that for a discourse to be coherent it must exhibit certain kinds of relationships with the entities it is about, introducing them and following them in a focused way. This kind of coherence can be called entity-based coherence, we will introduce the Centering model of entity-based coherence in Sec. 21.6.2.

In the rest of the chapter we'll study aspects of both discourse structure and discourse entities. We begin in Sec. 21.1 with the simplest kind of discourse structure: simple discourse segmentation of a document into a linear sequence of multiparagraph passages. In Section 21.2, we then introduce more fine-grained discourse structure, the coherence relation, and give some algorithms for interpreting these relations. Finally, in Section 21.3, we turn to entities, describing methods for interpreting referring expressions such as pronouns.

21.1 DISCOURSE SEGMENTATION

The first kind of discourse task we examine is an approximation to the global or high-level structure of a text or discourse. Many genres of text are associated with particular conventional structures. Academic articles might be divided into sections like Abstract, Introduction, Methodology, Results, Conclusion. A newspaper story is often described as having an inverted pyramid structure, in which the opening paragraphs (the lede) contains the most important information. Spoken patient reports are dictated by doctors in four sections following the standard SOAP format (Subjective, Objective, Assessment, Plan).

Automatically determining all of these types of structures for a large discourse is a difficult and unsolved problem. But some kinds of discourse structure detection algorithms exist. This section introduces one such algorithm, for the simpler problem of discourse segmentation; separating a document into a linear sequence of subtopics. Such segmentation algorithms are unable to find sophisticated hierarchical structure. Nonetheless, linear discourse segmentation can be important for information retrieval, for example, for automatically segmenting a TV news broadcast or a long news story into a sequence of stories so as to find a relevant story, or for text summarization algorithms which need to make sure that different segments of the document are summarized correctly, or for information extraction algorithms which tend to extract information from inside a single discourse segment.

In the next two sections we introduce both an unsupervised and a supervised algorithm for discourse segmentation.