23.4.2 Information Ordering in Multi-Document Summarization

The second stage of an extractive summarizer is the ordering or structuring of information, where we must decide how to concatenate the extracted sentences into a coherent

order. Recall that in single document summarization, we can just use the original article ordering for these sentences. This isn't appropriate for most multiple document applications, although we can certainly apply it if many or all of the extracted sentences happen to come from a single article.

For sentences extracted from news stories, one technique is to use the dates associated with the story, a strategy known as chronological ordering. It turns out that pure chronological ordering can produce summaries which lack cohesion; this problem can be addressed by ordering slightly larger chunks of sentences rather than single sentences; see Barzilay et al. (2002).

Perhaps the most important factor for information ordering, however, is coherence. Recall from Ch. 21 the various devices that contribute to the coherence of a discourse. One is having sensible coherence relations between the sentences; thus we could prefer orderings in summaries that resulting in sensible coherence relations between the sentences. Another aspect of coherence has to do with cohesion and lexical chains; we could for example prefer orderings which have more local cohesion. A final aspect of coherence is coreference; a coherence discourse is one in which entities are mentioned in coherent patterns. We could prefer orderings with coherent entity mention patterns.

All of these kinds of coherence have been used for information ordering. For example we can use lexical cohesion as an ordering heuristic by ordering each sentence next to sentences containing similar words. This can done by defining the standard tf-idf cosine distance between each pair of sentences and choosing the overall ordering that minimizes the average distance between neighboring sentences Conroy et al. (2006), or by building models of predictable word sequences across sentences (Soricut and Marcu, 2006).

Coreference-based coherence algorithms have also made use of the intuitions of Centering. Recall that the Centering algorithm was based on the idea that each discourse segment has a salient entity, the focus. Centering theory proposed that certain syntactic realizations of the focus (i.e. as subject or object) and certain transitions between these realizations (e.g., if the same entity is the subject of adjacent sentences) created a more coherent discourse. Thus we can prefer orderings in which the transition between entity mentions is a preferred one.

For example in the entity-based information approach of Barzilay and Lapata (2005, 2007), a training set of summaries is parsed and labeled for coreference. The resulting sequence of entity realizations can be automatically extracted and represented into an entity grid. Fig. 23.19 shows a simplified version of a parsed summary and the extracted grid. A probabilistic model of particular entity transitions (i.e. $ \{S, O, X, -\} $ can then be trained from the entity grid. For example the transitions $ \{X, O, S, S\} $ for the head word Microsoft exemplify the fact that new entities in a discourse are often introduced first in oblique or object position and then only later appear in subject position. See Barzilay and Lapata (2007) for details.

A general way to view all of these methods is as assigning a coherence score to a sequence of sentences via a local coherence score between pairs or sequences of sentences; a single general transition score between sentences could then combine lexical coherence and entity-based coherence. Once we have such a scoring function, choosing an ordering which optimizes all these local pairwise distances is known to be quite difficult. The task of finding the optimal ordering of a set of sentences given

a set of pairwise distances between the sentences is equivalent to very hard problems like Cyclic Ordering and the Traveling Salesman Problem. $ ^{2} $ Sentence ordering is thus equivalent to the difficult class of problems known as NP-complete. While difficult to solve exactly, there are a number of good approximation methods for solving NP-complete problems that have been applied to the information ordering task. See Althaus et al. (2004), Knight (1999), Cohen et al. (1999), Brew (1992) for the relevant proofs and approximation techniques.

| 1 | [The Justice Department]_ $ S $ is conducting an [anti-trust trial]_ $ O $ against [Microsoft Corp.] $ _{{X}} $ | Department Trial | Microsoft Markets Products Brands |

| --- | --- | --- | --- |

| 2 | [Microsoft]_ $ O $ is accused of trying to forcefully buy into [markets]_ $ X $ where [its own products]_ $ S $ are not competitive enough to unseat [established brands]_ $ O $ | 1 | S |

| 3 | [The case]_ $ S $ resolves around [evidence]_ $ O $ of [Microsoft]_ $ S $ aggressively pressuring [Netscape]_ $ O $ into merging [browser software]_ $ O $ | 2 | - |

| 4 | [Microsoft]_ $ S $ claims [its tactics]_ $ S $ are commonplace and good economically. | 3 | - |

| | | 4 | - |

| | | 4 | - |

| | | 4 | - |

| | | | |

In the models described above, the information ordering task is completely separate from content extraction. An alternative approach is to learn the two tasks jointly, resulting in a model that both selects sentences and orders them. For example in the HMM model of Barzilay and Lee (2004), the hidden states correspond to document content topics and the observations to sentences. For example for newspaper articles on earthquakes, the hidden states (topics) might be strength of earthquake, location, rescue efforts, and casualties. They apply clustering and HMM induction to induce these hidden states and the transitions between them. For example, here are three sentences from the location cluster they induce:

(23.36) The Athens seismological institute said the temblor's epicenter was located 380 kilometers (238 miles) south of the capital.

(23.37) Seismologists in Pakistan's Northwest Frontier Province said the temblor's epicenter was about 250 kilometers (155 miles) north of the provincial capital Peshawar.

(23.38) The temblor was centered 60 kilometers (35 miles) northwest of the provincial capital of Kunming, about 2,200 kilometers (1,300 miles) southwest of Beijing, a bureau seismologist said.

The learned structure of the HMM then implicitly represents information ordering facts like the mention 'casualties' prior to 'rescue efforts' via the HMM transition probabilities.

In summary, we've seen information ordering based on chronological order, based on coherence, and an ordering that is learned automatically from the data. In the next section on query-focused summarization we'll introduce a final method in which information ordering can be specified according to an ordering template which is predefined advance for different query types.

Sentence Realization

While discourse coherence can be factored in during sentence ordering, the resulting sentences may still have coherence problems. For example, as we saw in Ch. 21, when a referent appears multiple times in a coreference chain in a discourse, the longer or more descriptive noun phrases occur before shorter, reduced, or pronominal forms. But the ordering we choose for the extracted sentences may not respect this coherence preference.

For example the boldfaced names in the original summary in Fig. 23.20 appear in an incoherent order; the full name U.S. President George W. Bush occurs only after the shortened form Bush has been introduced.

(23.39) Use the full name at the first mention, and just the last name at subsequent mentions.

One possible way to address this problem in the sentence realization stage is to apply a coreference resolution algorithm to the output, extracting names and applying some simple cleanup rewrite rules like the following:

(23.40) Use a modified form for the first mention, but remove appositives or premodifiers from any subsequent mentions.

The rewritten summary in Fig. 23.20 shows how such rules would apply; in general such methods would depend on high-accuracy coreference resolution.

Figure 23.20 Rewriting references, from Nenkova and McKeown (2003)

Recent research has also focused on a finer granularity for realization than the extracted sentence, by using sentence fusion algorithms to combine phrases or clauses from different sentences into one new sentence. The sentence fusion algorithm of Barzilay and McKeown (2005) parses each sentence, uses multiple-sequence alignment of the parses to find areas of common information, builds a fusion lattice with overlapping information, and creates a fused sentence by linearizing a string of words from the lattice.

23.5 BETWEEN QUESTION ANSWERING AND SUMMARIZATION: QUERY-FOCUSED SUMMARIZATION

As noted in at the beginning of this chapter, most interesting questions are not factoid questions. User needs require longer, more informative answers than a single phrase can provide. For example, while a DEFINITION question might be answered by a short phrase like “Autism is a developmental disorder” or “A caldera is a volcanic crater”, a user might want more information, as in the following definition of water spinach:

Water spinach (ipomoea aquatica) is a semi-aquatic leafy green plant characterized by long hollow stems and spear-shaped or heart-shaped leaves which is widely grown throughout Asia as a leaf vegetable. The leaves and stems are often eaten stir-fried as greens with salt or salty sauces, or in soups. Other common names include morning glory vegetable, kangkong (Malay), rau muong (Vietnamese), ong choi (Cantonese), and kong xin cai (Mandarin). It is not related to spinach, but is closely related to sweet potato and convolvulus.

Complex questions can also be asked in domains like medicine, such as this question about a particular drug intervention:

In children with an acute febrile illness, what is the efficacy of single-medication therapy with acetaminophen or ibuprofen in reducing fever?

For this medical question, we'd like to be able to extract an answer of the following type, perhaps giving the document id(s) that the extract came from, and some estimate of our confidence in the result:

Ibuprofen provided greater temperature decrement and longer duration of antipyresis than acetaminophen when the two drugs were administered in approximately equal doses. (PubMedID: 1621668, Evidence Strength: A)

Questions can be even more complex, such as this one from the Document Understanding Conference annual summarization competition:

Where have poachers endangered wildlife, what wildlife has been endangered and what steps have been taken to prevent poaching?

Where a factoid answer might be found in a single phrase in a single document or web page, these kinds of complex questions are likely to require much longer answers which are synthesized from many documents or pages.

For this reason, summarization techniques are often used to build answers to these kinds of complex questions. But unlike the summarization algorithms introduced above, the summaries produced for complex question answering must be relevant to some user question. When a document is summarized for the purpose of answering some user query or information need, we call the goal query-focused summarization or sometimes just focused summarization. (The terms topic-based summarization and user-focused summarization are also used.) A query-focused summary is thus really a kind of longer, non-factoid answer to a user question or information need.

One kind of query-focused summary is a snippet, the kind that web search engines

like Google return to the user to describe each retrieved document. Snippets are query-focused summaries of a single document. But since for complex queries we will want to aggregate information from multiple documents, we'll need to summarize multiple documents.

Indeed, the simplest way to do query-focused summarization is to slightly modify the algorithms for multiple document summarization that we introduced in the previous section to make use of the query. For example, when ranking sentences from all the returned documents in the content selection phase, we can require that any extracted sentence must contain at least one word overlapping with the query. Or we can just add the cosine distance from the query as one of the relevance features in sentence extraction. We can characterize such a method of query-focused summarization as a bottom-up, domain-independent method.

An alternative way to do query-focused summarization is to make additional use of top-down or information-extraction techniques, building specific content selection algorithms for different types of complex questions. Thus we could specifically build a query-focused summarizer for the kinds of advanced questions introduced above, like definition questions, biography questions, certain medical questions. In each case, we use our top-down expectations for what makes a good definition, biography, or medical answer to guide what kinds of sentences we extract.

For example, a definition of a term often includes information about the term's genus and species. The genus is the hypernym or superordinate of the word; thus a sentence like The Hajj is a type of ritual is a genus sentence. The species gives important additional properties of the term that differentiate the term from other hyponyms of the genus; an example is “The annual hajj begins in the twelfth month of the Islamic year”. Other kinds of information that can occur in a definition include synonyms, etymology, subtypes, and so on.

In order to build extractive answers for definition questions, we'll need to make sure we extract sentences with the genus information, the species information, and other generally informative sentences. Similarly, a good biography of a person contains information such as the person's birth/death, fame factor, education, nationality and so on; we'll need to extract sentences with each of these kinds of information. A medical answer that summarizes the results of a study on applying a drug to a medical problem would need to contain information like the problem (the medical condition), the intervention (the drug or procedure), and the outcome (the result of the study).

Fig. 23.21 shows some example predicates for definition, biography, and medical intervention questions.

In each case we use the information extraction methods of Ch. 22 to find specific sentences for genus and species (for definitions), or dates, nationality, and education (for biographies), or problems, interventions and outcomes (for medical questions). We can then use standard domain-independent content selection algorithms to find other good sentences to add on to these.

A typical architecture consists of the four steps shown in Fig. 23.22 from the definition extraction system of Blair-Goldensohn et al. (2004). The input is a definition question T, the number N of documents to retrieve, and the length L of the answer (in sentences).

The first step in any IE-based complex question answering system is information retrieval. In this case a handwritten set of patterns is used to extract the term to be defined from the query $ T(H_{ij}) $ and generate a series of queries that are sent to an IR engine. Similarly, in a biography system it would be the name that would be extracted and passed to the IR engine. The returned documents are broken up into sentences.

In the second stage, we apply classifiers to label each sentence with an appropriate set of classes for the domain. For definition questions, Blair-Goldensohn et al. (2004) used of four classes: genus, species, other definitional, or other. The third class,

other definitional, is used to select other sentences that might be added into the summary. These classifiers can be based on any of the information extraction techniques introduced in Ch. 22, including hand-written rules, or supervised machine learning techniques.

In the third stage, we can use the methods described in the section on generic (non-query-focused) multiple domain summarization content selection to add additional sentences to our answer that might not fall into a specific information extraction type. For example for definition questions, all the sentences that are classified as other definitional are examined, and a set of relevant sentences is selected from them. This selection can be done by the centroid method, in which we form a TF-IDF vector for each sentence, find the centroid of all the vectors, and then choose the K sentences closest to the centroid. Alternatively we can use a method for avoiding redundancy, like clustering the vectors and choosing the best sentence from each cluster.

Because query-focused summarizers of this type or domain-specific, we can use domain-specific methods for information ordering as well, such as using a fixed hand-built template. For biography questions we might use a template like the following:

(23.43) is . She was born on in . She . . .

The various sentences or phrases selected in the content selection phase can then be fit into this template. These templates can also be somewhat more abstract. For example, for definitions, we could place a genus-species sentence first, followed by remaining sentences ordered by their saliency scores.

23.6 SUMMARIZATION EVALUATION

As is true for other speech and language processing areas like machine translation, there are a wide variety of evaluation metrics for summarization, metrics requiring human annotation, as well as completely automatic metrics. $ ^{3} $

As we have seen for other tasks, we can evaluate a system via extrinsic (task-based) or intrinsic (task-independent) methods. We described a kind of extrinsic evaluation of multi-document summarization in Sec. 23.4, in which subjects were asked to perform time-restricted fact-gathering tasks, and were given full documents together with either no summaries, human summaries, or automatically generated summaries to read. The subjects had to answer three related questions about an event in the news. For query-focused single-document summarization (like the task of generating web snippets), we can measure how different summarization algorithms affect human performance at the task of deciding if a document is relevant/not-relevant to a query by looking solely at the summary.

The most common intrinsic summarization evaluation metric is an automatic method called ROUGE, Recall-Oriented Understudy for Gisting Evaluation (Lin and Hovy,

2003; Lin, 2004). ROUGE is inspired by the BLEU metric used for evaluating machine translation output, and like BLEU, automatically scores a machine-generated candidate summary by measuring the amount of N-gram overlap between the candidate and human-generated summaries (the references).

Recall that BLEU is computed by averaging the number of overlapping N-grams of different length between the hypothesis and reference translations. In ROUGE, by contrast, the length of the N-gram is fixed; ROUGE-1 uses unigram overlap, while ROUGE-2 uses bigram overlap. We'll choose to define ROUGE-2; the definitions of all the other ROUGE-N metrics follow. ROUGE-2 is a measure of the bigram recall between the candidate summary and the set of human reference summaries:

$$ ROUGE2=\frac{\sum\limits_{S\in\{ReferenceSummaries\}}\sum\limits_{bigram\in S}Count_{match}(bigram)}{\sum\limits_{S\in\{ReferenceSummaries\}}\sum\limits_{bigram\in S}Count(bigram)} $$

The function $ \text{Count}_{\text{match}}(\text{bigram}) $ returns the maximum number of bigrams that co-occur in the candidate summary and the set of reference summaries. ROUGE-1 is the same but counting unigrams instead of bigrams.

Note that ROUGE is a recall-oriented measure, where BLEU is a precision-oriented measure. This is because the denominator of $ (23.44) $ is the total sum of the number of bigrams in the reference summaries. By contrast, in BLEU the denominator is the total sum of the number of N-grams in the candidates. Thus ROUGE is measuring something like how many of the human reference summary bigrams are covered by the candidate summary, where BLEU is measuring something like how many of the candidate translation bigrams occurred in the human reference translations.

Variants of ROUGE include ROUGE-L, which measure the longest common subsequence between the reference and candidate summaries, and ROUGE-S and ROUGE-SU which measure the number of skip bigrams between the reference and candidate summaries. A skip bigram is a pair of words in their sentence order, but allowing for any number of other words to appear between the pair.

While ROUGE is the most commonly applied automatic baseline, it is not as applicable to summarization as similar metrics like BLEU are to machine translation. This is because human summarizers seem to disagree strongly about which sentences to include in a summary, making even the overlap of humans with each other very low.

This difference in which sentences humans choose to extract has motivated human evaluation methods which attempt to focus more on meaning. One metric, the Pyramid Method, is a way of measuring how many units of meaning are shared between the candidate and reference summaries, and also weights the units of meaning by importance; units of meaning which occur in more of the human summaries are weighted more highly. The units of meaning are called Summary Content Units (SCU), which are sub-sentential semantic units which roughly correspond to propositions or coherent pieces of propositions.

In the Pyramid Method, humans label the Summary Content Units in each reference and candidate summary, and then an overlap measure is computed.

Let's see an example from Nenkova et al. (2007) of how two SCUs are labeled in sentences from six human abstracts. We'll first show sentences from the human summaries indexed by a letter (corresponding to one of the 6 human summaries) and a number (the position of the sentence in the human summary):

A1. The industrial espionage case involving GM and VW began with $ \underline{\text{the hiring of Jose Ignacio Lopez, an employee of GM}} $ subsidiary Adam Opel, $ \underline{\text{by VW}} $ as a production director.

B3. However, $ \underline{\text{he left GM for VW}} $ under circumstances, which along with ensuing events, were described by a German judge as "potentially the biggest-ever case of industrial espionage".

C6. $ \underline{\text{He left GM for VW}} $ in March 1993.

D6. The issue stems from the alleged $ \underline{\text{recruitment of GM's}} $ eccentric and visionary Basque-born procurement chief $ \underline{\text{Jose Ignacio Lopez}} $ de Arriortura and seven of Lopez's business colleagues.

E1. On March 16, 1993, with Japanese car import quotas to Europe expiring in two years, renowned cost-cutter, $ \underline{\text{Agnacio Lopez De Arriortura, left his job}} $ as head of purchasing $ \underline{\text{at General Motor's Opel}} $, Germany, $ \underline{\text{to become Volkswagen's}} $ Purchasing and Production director.

F3. In March 1993, $ \underline{\text{Lopez}} $ and seven other $ \underline{\text{GM}} $ executives $ \underline{\text{moved to VW}} $ overnight.

The annotators first identify similar sentences, like those above, and then label SCUs. The underlined and italicized spans of words in the above sentences result in the following two SCUs, each one with a weight corresponding to the number of summaries it appears in (6 for the first SCU, and 3 for the second):

SCU1 (w=6): Lopez left GM for VW

A1. the hiring of Jose Ignacio Lopez, an employee of GM ... by VW

B3. he left GM for VW

C6. He left GM for VW

D6. recruitment of GMs . . . Jose Ignacio Lopez

E1. Agnacio Lopez De Arriortura, left his job . . . at General Motors Opel

... to become Volkswagen's ... director

F3. Lopez ... GM ... moved to VW

SCU2 (w=3) Lopez changes employers in March 1993

C6. in March, 1993

E1. On March 16, 1993

F3. In March 1993

Once the annotation is done, the informativeness of a given summary can be measured as the ratio of the sum of the weights of its SCUs to the weight of an optimal summary with the same number of SCUs. See the end of the chapter for more details and pointers to the literature.

The standard baselines for evaluating summaries are the random sentences baseline and the leading sentences baseline. Assuming we are evaluating summaries of length N sentences, the random baseline just chooses N random sentences, while the

leading baseline chooses the first N sentences. The leading sentences method, in particular, is quite a strong baseline and many proposed summarization algorithms fail to beat it.

23.7 SUMMARY

The dominant models of information retrieval represent the meanings of documents and queries as bags of words.

• The vector space model views documents and queries as vectors in a large multi-dimensional space. In this model, the similarity between documents and queries, or other documents, can be measured by the cosine of the angle between the vectors.

• The main components of a factoid question answering system are the question classification module to determine the named-entity type of the answer, a passage retrieval module to identify relevant passages, and an answer processing module to extract and format the final answer.

• Factoid question answers can be evaluated via mean reciprocal rank (MRR).

• Summarization can be abstractive or extractive; most current algorithms are extractive.

• Three components of summarization algorithms include content selection, information ordering, and sentence realization.

• Current single document summarization algorithms focus mainly on sentence extraction, relying on features like position in the discourse, word informativeness, cue phrases, and sentence length.

• Multiple document summarization algorithms often perform sentence simplification on document sentences.

• Redundancy avoidance is important in multiple document summarization; it is often implemented by adding a redundancy penalization term like MMR into sentence extraction.

• Information ordering algorithms in multi-document summarization are often based on maintaining coherence.

• Query-focused summarization can be done using slight modifications to generic summarization algorithms, or by using information-extraction methods.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

Luhn (1957) is generally credited with first advancing the notion of fully automatic indexing of documents based on their contents. Over the years Salton's SMART project (Salton, 1971) at Cornell developed or evaluated many of the most important notions in information retrieval including the vector model, term weighting schemes, relevance feedback, and the use of cosine as a similarity metric. The notion of using inverse

document frequency in term weighting is due to Sparck Jones (1972). The original notion of relevance feedback is due to Rocchio (1971).

An alternative to the vector model that we have not covered is the probabilistic model originally shown effective by Robinson and Sparck Jones (1976). See Crestani et al. (1998) and Chapter 11 of Manning et al. (2008) on probabilistic models in information retrieval.

Manning et al. (2008) is a comprehensive modern text on information retrieval. Good but slightly older texts include Baeza-Yates and Ribeiro-Neto (1999) and Frakes and Baeza-Yates (1992); older classic texts include Salton and McGill (1983) and van Rijsbergen (1975). Many of the classic papers in the field can be found in Sparck Jones and Willett (1997). Current work is published in the annual proceedings of the ACM Special Interest Group on Information Retrieval (SIGIR). The US National Institute of Standards and Technology (NIST) has run an annual evaluation project for text information retrieval and extraction called the Text REtrieval Conference (TREC) since the early 1990s; the conference proceedings from TREC contain results from these standardized evaluations. The primary journals in the field are the Journal of the American Society of Information Sciences, ACM Transactions on Information Systems, Information Processing and Management, and Information Retrieval.

Question answering was one of the earliest tasks for NLP systems in the 1960's and 1970's (Green et al., 1961; Simmons, 1965; Woods et al., 1972; Lehnert, 1977), but the field lay dormant for a few decades until the need for querying the Web brought the task back into focus. The U.S. government-sponsored TREC (Text REtrieval Conference) QA track began in 1999 and a wide variety of factoid and non-factoid systems have been competing in annual evaluations since then. See the references in the chapter and Strzalkowski and Harabagiu (2006) for a collection of recent research papers.

Research on text summarization began with the work of Luhn (1958) on extractive methods for the automatic generation of abstracts, focusing on surface features like term frequency, and the later work of Edmunson (1969) incorporating positional features as well. Term-based features were also used in the early application of automatic summarization at Chemical Abstracts Service (Pollock and Zamora, 1975). The 1970s and 1980s saw a number of approaches grounded in AI methodology such as scripts DeJong (1982), semantic networks Reimer and Hahn (1988), or combinations of AI and statistical methods Rau et al. (1989).

The work of Kupiec et al. (1995) on training a sentence classifier with supervised machine learning led to many statistical methods for sentence extraction. Around the turn of the century, the growth of the Web led naturally to interest in multi-document summarization and query-focused summarization.

There have naturally been a wide variety of algorithms for the main components of summarizers. The simple unsupervised log-linear content selection algorithm we describe is simplified from the SumBasic algorithm of Nenkova and Vanderwende (2005), Vanderwende et al. (2007b) and the centroid algorithm of Radev et al. (2000) and Radev et al. (2001). A number of algorithms for information ordering have used entity coherence, including Kibble and Power (2000), Lapata (2003), Karamanis and Manurung (2002), Karamanis (2003), Barzilay and Lapata (2005, 2007). Algorithms for combining multiple cues for coherence and searching for the optimal ordering include Althaus et al. (2004), based on linear programming, the genetic algorithms of

Mellish et al. (1998) and Karamanis and Manurung (2002), and the Soricut and Marcu (2006) algorithm, which uses A* search based on IDL-expressions. Karamanis (2007) showed that adding coherence based on rhetorical relations to entity coherence didn't improve sentence ordering. See Lapata (2006, 2003), Karamanis et al. (2004), Karamanis (2006) on methods for evaluating information ordering.

Sentence compression is a very popular area of research. Early algorithms focused on the use of syntactic knowledge for eliminating less important words or phrases Grefenstette (1998), Mani et al. (1999), Jing (2000). Recent research has focused on using supervised machine learning, in which a parallel corpus of documents together with their human summaries is used to compute the probability that particular words or parse nodes will be pruned. Methods include the use of maximum entropy Riezler et al. (2003), the noisy channel model and synchronous context-free grammars (Galley and McKeown, 2007; Knight and Marcu, 2000; Turner and Charniak, 2005; Daumé III and Marcu, 2002), Integer Linear Programming Clarke and Lapata (2007), and large-margin learning McDonald (2006). These methods rely on various features, especially including syntactic or parse knowledge Jing (2000), Dorr et al. (2003), Siddharthan et al. (2004), Galley and McKeown (2007), Zajic et al. (2007), Conroy et al. (2006), Vanderwende et al. (2007a), but also including coherence information Clarke and Lapata (2007). Alternative recent methods are able to function without these kinds of parallel document/summary corpora (Hori and Furui, 2004; Turner and Charniak, 2005; Clarke and Lapata, 2006).

See Daumé III and Marcu (2006) for a recent Bayesian model of query-focused summarization.

For more information on summarization evaluation, see Nenkova et al. (2007), Passonneau et al. (2005), and Passonneau (2006) for details on the Pyramid method, van Halteren and Teufel (2003) and Teufel and van Halteren (2004) on related semantic coverage evaluation methods, and Lin and Demner-Fushman (2005) on the link between evaluations for summarization and question answering. A NIST program starting in 2001, the Document Understanding Conference (DUC), has sponsored an annual evaluation of summarization algorithms. These have included single document, multiple document, and query-focused summarization; proceedings from the annual workshop are available online.

Mani and Maybury (1999) is the definitive collection of classic papers on summarization. Sparck Jones (2007) is a good recent survey, and Mani (2001) is the standard textbook.

The task of paraphrase detection is an important task related to improving recall in question answering and avoiding redundancy in summarization, and also very relevant for tasks like textual entailment. See Lin and Pantel (2001), Barzilay and Lee (2003), Pang et al. (2003), Dolan et al. (2004), Quirk et al. (2004) for representative papers on techniques for detecting paraphrases.

Another task related to information retrieval and summarization is the text categorization task, which is to assign a new document to one of a pre-existing set of document classes. The standard approach is to use supervised machine learning to train classifiers on a set of documents that have been labeled with the correct class. A very important application of text categorization is for spam detection.

EXERCISES

23.1 Do some error analysis on web-based question answering. Choose 10 questions and type them all into two different search engines. Analyze the errors (e.g., what kinds of questions could neither system answer; which kinds of questions did one work better on; was there a type of question that could be answered just from the snippets, etc).

23.2 Read Brill et al. (2002) and reimplement a simple version of the AskMSR system.

Agichtein, E. and Gravano, L. (2000). Snowball: Extracting relations from large plain-text collections. In Proceedings of the 5th ACM International Conference on Digital Libraries.

Althaus, E., Karamanis, N., and Koller, A. (2004). Computing locally coherent discourses. In ACL-04.

Attar, R. and Fraenkel, A. S. (1977). Local feedback in full-text retrieval systems. Journal of the ACM, 24(3), 398–417.

Baeza-Yates, R. and Ribeiro-Neto, B. (1999). Modern Information Retrieval. ACM Press, New York.

Barzilay, R. and Elhadad, M. (1997). Using lexical chains for text summarization. In Proceedings of the ACL Workshop on Intelligent Scalable Text Summarization, pp. 10–17.

Barzilay, R., Elhadad, N., and McKeown, K. R. (2002). Inferring strategies for sentence ordering in multidocument news summarization. Journal of Artificial Intelligence Research, 17, 35–55.

Barzilay, R. and Lapata, M. (2005). Modeling local coherence: an entity-based approach. In ACL-05, pp. 141–148.

Barzilay, R. and Lapata, M. (2007). Modeling local coherence: an entity-based approach. Computational Linguistics. To appear.

Barzilay, R. and Lee, L. (2003). Learning to paraphrase: an unsupervised approach using multiple-sequence alignment. In HLT-NAACL-03, pp. 16–23.

Barzilay, R. and Lee, L. (2004). Catching the drift: Probabilistic content models, with applications to generation and summarization. In HLT-NAACL-04, pp. 113–120.

Barzilay, R. and McKeown, K. R. (2005). Sentence fusion for multidocument news summarization. Computational Linguistics, 31(3), 297–328.

Blair-Goldensohn, S., McKeown, K. R., and Schlaikjer, A. H. (2004). Answering definitional questions: A hybrid approach. In Maybury, M. T. (Ed.), New Directions in Question Answering, pp. 47–58. AAAI Press.

Brew, C. (1992). Letting the cat out of the bag: generation for shake-and-bake mt. In COLING-92, pp. 610–616.

Brill, E., Dumais, S. T., and Banko, M. (2002). An analysis of the AskMSR question-answering system. In EMNLP 2002, pp. 257–264.

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.

Carbonell, J. and Goldstein, J. (1998). The use of mmr, diversity-based reranking for reordering documents and producing summaries. In SIGIR 1998, pp. 335–336.

Clarke, J. and Lapata, M. (2006). Models for sentence compression: A comparison across domains, training requirements and evaluation measures. In COLING/ACL 2006, pp. 377–384.

Clarke, J. and Lapata, M. (2007). Modelling compression with discourse constraints. In EMNLP/CoNLL 2007, Prague, pp. 667–677.

Cohen, W. W., Schapire, R. E., and Singer, Y. (1999). Learning to order things. Journal of Artificial Intelligence Research, 10, 243–270.

Conroy, J. M., Schlesinger, J. D., and Goldstein, J. (2006). Classy tasked based summarization: Back to basics. In DUC06.

Crestani, F., Lemas, M., Rijsbergen, C. J. V., and Campbell, I. (1998). "Is This Document Relevant? ... Probably": a survey of probabilistic models in information retrieval. ACM Computing Surveys, 30(4), 528–552.

Crouch, C. J. and Yang, B. (1992). Experiments in automatic statistical thesaurus construction. In SIGIR-92, Copenhagen, Denmark, pp. 77–88. ACM.

Daumé III, H. and Marcu, D. (2002). A noisy-channel model for document compression. In ACL-02.

Daumé III, H. and Marcu, D. (2005). Induction of word and phrase alignments for automatic document summarization. Computational Linguistics, 31(4), 505–530.

Daumé III, H. and Marcu, D. (2006). Bayesian query-focused summarization. In COLING/ACL 2006, Sydney, Australia.

DeJong, G. F. (1982). An overview of the FRUMP system. In Lehnert, W. G. and Ringle, M. H. (Eds.), Strategies for Natural Language Processing, pp. 149–176. Lawrence Erlbaum, New Jersey.

Dolan, W. B., Quirk, C., and Brockett, C. (2004). Unsupervised construction of large paraphrase corpora: exploiting massively parallel news sources. In COLING-04.

Dorr, B., Zajic, D., and Schwartz, R. (2003). Hedge trimmer: a parse-and-trim approach to headline generation. In HL-NAACL Workshop on Text Summarization, pp. 1–8.

Dunning, T. (1993). Accurate methods for the statistics of surprise and coincidence. Computational Linguistics, 19(1), 61–74.

Echihabi, A., Hermjakob, U., Hovy, E. H., Marcu, D., Melz, E., and Ravichandran, D. (2005). How to select an answer string?. In Strzalkowski, T. and Harabagiu, S. (Eds.), Advances in Textual Question Answering. Kluwer.

Edmunson, H. (1969). New methods in automatic extracting. Journal of the ACM, 16(2), 264–285.

Erkan, G. and Radev, D. R. (2004). Lexrank: Graph-based centrality as salience in text summarization. Journal of Artificial Intelligence Research (JAIR), 22, 457–479.

Frakes, W. B. and Baeza-Yates, R. (1992). Information Retrieval: Data Structures and Algorithms. Prentice Hall.

Galley, M. and McKeown, K. R. (2007). Lexicalized Markov grammars for sentence compression. In NAACL-HLT 07, Rochester, NY, pp. 180–187.

Goldstein, J., Mittal, V., Carbonell, J., and Kantrowitz, M. (2000). Multi-document summarization by sentence extraction. In Proceedings of the ANLP/NAACL Workshop on Automatic Summarization.

Green, B. F., Wolf, A. K., Chomsky, C., and Laughery, K. (1961). Baseball: An automatic question answerer. In Proceedings of the Western Joint Computer Conference 19, pp. 219–224. Reprinted in Grosz et al. (1986).

Grefenstette, G. (1998). Producing intelligent telegraphic text reduction to provide an audio scanning service for the blind. In AAAI 1998 Spring Symposium on Intelligent Text Summarization, pp. 102–108.

Hachey, B. and Grover, C. (2005). Sentence extraction for legal text summarization. In IJCAI-05, pp. 1686–1687.

Harabagiu, S., Pasca, M., and Maiorano, S. (2000). Experiments with open-domain textual question answering. In COLING-00, Saarbrücken, Germany.

Hori, C. and Furui, S. (2004). Speech summarization: an approach through word extraction and a method for evaluation. IEICE Transactions on Information and Systems, 87, 15–25.

Hovy, E., Hermjakob, U., and Ravichandran, D. (2002). A question/answer typology with surface text patterns. In HLT-01.

Hovy, E. H. and Lin, C.-Y. (1999). Automated text summarization in SUMMARIST. In Mani, I. and Maybury, M. T. (Eds.), Advances in Automatic Text Summarization, pp. 81–94. MIT Press.

Jing, H. (2000). Sentence reduction for automatic text summarization. In ANLP 2000, Seattle, WA, pp. 310–315.

Jing, H. (2002). Using hidden Markov modeling to decompose human-written summaries. Computational Linguistics, 28(4), 527–543.

Karamanis, N. (2003). Entity Coherence for Descriptive Text Structuring. Ph.D. thesis, University of Edinburgh.

Karamanis, N. (2006). Evaluating centering for sentence ordering in two new domains. In HLT-NAACL-06.

Karamanis, N. (2007). Supplementing entity coherence with local rhetorical relations for information ordering. Journal of Logic, Language and Information. To appear.

Karamanis, N. and Manurung, H. M. (2002). Stochastic text structuring using the principle of continuity. In INLG 2002, pp. 81–88.

Karamanis, N., Poesio, M., Mellish, C., and Oberlander, J. (2004). Evaluating centering-based metrics of coherence for text structuring using a reliably annotated corpus. In ACL-04.

Kibble, R. and Power, R. (2000). An integrated framework for text planning and pronominalisation. In INLG 2000, pp. 77–84.

Knight, K. (1999). Decoding complexity in word-replacement translation models. Computational Linguistics, 25(4), 607–615.

Knight, K. and Marcu, D. (2000). Statistics-based summarization - step one: Sentence compression. In AAAI-00, pp. 703–710.

Krovetz, R. and Croft, W. B. (1992). Lexical ambiguity and information retrieval. ACM Transactions on Information Systems, 10(2), 115–141.

Kupiec, J., Pedersen, J., and Chen, F. (1995). A trainable document summarizer. In SIGIR 1995, pp. 68–73.

Lapata, M. (2003). Probabilistic text structuring: experiments with sentence ordering. In ACL-03, Sapporo, Japan, pp. 545–552.

Lapata, M. (2006). Automatic evaluation of information ordering. Computational Linguistics, 32(4), 471–484.

Lehnert, W. G. (1977). A conceptual theory of question answering. In IJCAI-77, pp. 158–164. Morgan Kaufmann.

Li, X. and Roth, D. (2002). Learning question classifiers. In COLING-02, pp. 556–562.

Li, X. and Roth, D. (2005). Learning question classifiers: The role of semantic information. Journal of Natural Language Engineering, 11(4).

Lin, C.-Y. (2004). ROUGE: A package for automatic evaluation of summaries. In ACL 2004 Workshop on Text Summarization Branches Out.

Lin, C.-Y. and Hovy, E. (2000). The automated acquisition of topic signatures for text summarization. In COLING-00, pp. 495–501.

Lin, C.-Y. and Hovy, E. H. (2003). Automatic evaluation of summaries using N-gram co-occurrence statistics. In HL-NAACL-03, Edmonton, Canada.

Lin, D. and Pantel, P. (2001). Discovery of inference rules for question-answering. Natural Language Engineering, 7(4), 343–360.

Lin, J. and Demner-Fushman, D. (2005). Evaluating summaries and answers: Two sides of the same coin?. In ACL 2005 Workshop on Measures for MT and Summarization.

Lin, J. (2007). An exploration of the principles underlying redundancy-based factoid question answering. ACM Transactions on Information Systems.

Luhn, H. P. (1957). A statistical approach to the mechanized encoding and searching of literary information. IBM Journal of Research and Development, 1(4), 309–317.

Luhn, H. P. (1958). The automatic creation of literature abstracts. IBM Journal of Research and Development, 2(2), 159–165.

Mani, I. (2001). Automatic Summarization. John Benjamins.

Mani, I. and Bloedorn, E. (1999). Summarizing similarities and differences among related documents. Information Retrieval, 1(1-2), 35–67.

Mani, I., Gates, B., and Bloedorn, E. (1999). Improving summaries by revising them. In ACL-99, pp. 558–565.

Mani, I. and Maybury, M. T. (1999). Advances in Automatic Text Summarization. MIT Press.

Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press.

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

Marcu, D. (1995). Discourse trees are good indicators of importance in text. In Mani, I. and Maybury, M. T. (Eds.), Advances in Automatic Text Summarization, Cambridge, MA, pp. 123–136. MIT Press.

Marcu, D. (1999). The automatic construction of large-scale corpora for summarization research. In SIGIR 1999, Berkeley, CA, pp. 137–144.

Marcu, D. (Ed.). (2000). The Theory and Practice of Discourse Parsing and Summarization. MIT Press.

McDonald, R. (2006). Discriminative sentence compression with soft syntactic constraints. In EACL-06.

McKeown, K. R., Passonneau, R., Elson, D., Nenkova, A., and Hirschberg, J. (2005). Do summaries help? A task-based evaluation of multi-document summarization. In SIGIR 2005, Salvador, Brazil.

Mellish, C., Knott, A., Oberlander, J., and O'Donnell, M. (1998). Experiments using stochastic search for text planning. In INLG 1998, pp. 98–107.

Monz, C. (2004). Minimal span weighting retrieval for question answering. In SIGIR Workshop on Information Retrieval for Question Answering, pp. 23–30.

Moore, R. C. (2004). On log-likelihood-ratios and the significance of rare events. In EMNLP 2004, Barcelona, pp. 333–340.

Nenkova, A. and Vanderwende, L. (2005). The Impact of Frequency on Summarization. Tech. rep. MSR-TR-2005-101, Microsoft Research, Redmond, WA.

Nenkova, A. and McKeown, K. R. (2003). References to named entities: a corpus study. In HLT-NAACL-03, pp. 70–72.

Nenkova, A., Passonneau, R., and McKeown, K. R. (2007). The pyramid method: Incorporating human content selection variation in summarization evaluation. ACM TSLP, 4(2).

Norvig, P. (2005). The gettysburgh powerpoint presentation. http://norvig.com/Gettysburg/.

Pang, B., Knight, K., and Marcu, D. (2003). Syntax-based alignment of multiple translations: extracting paraphrases and generating new sentences. In HLT-NAACL-03, pp. 102–109.

Pasca, M. (2003). Open-Domain Question Answering from Large Text Collections. CSLI.

Passonneau, R. (2006). Measuring agreement on set-valued items (masi) for semantic and pragmatic annotation. In LREC-06.

Passonneau, R., Nenkova, A., McKeown, K. R., and Sigleman, S. (2005). Applying the pyramid method in duc 2005. In In Proceedings of the Document Understanding Conference (DUC'05).

Pollock, J. J. and Zamora, A. (1975). Automatic abstracting research at Chemical Abstracts Service. Journal of Chemical Information and Computer Sciences, 15(4), 226–232.

Porter, M. F. (1980). An algorithm for suffix stripping. Program, 14(3), 130–127.

Quirk, C., Brockett, C., and Dolan, W. B. (2004). Monolingual machine translation for paraphrase generation. In EMNLP 2004, pp. 142–149.

Radev, D., Blair-Goldensohn, S., and Zhang, Z. (2001). Experiments in single and multi-document summarization using MEAD. In DUC-01, New Orleans, LA.

Radev, D. R., Jing, H., and Budzikowska, M. (2000). Summarization of multiple documents: clustering, sentence extraction, and evaluation. In ANLP-NAACL Workshop on Automatic Summarization, Seattle, WA.

Rau, L. F., Jacobs, P. S., and Zernik, U. (1989). Information extraction and text summarization using linguistic knowledge acquisition. Information Processing and Management, 25(4), 419–428.

Reimer, U. and Hahn, U. (1988). Text condensation as knowledge base abstraction. In CAIA-88, pp. 14–18.

Ravichandran, D. and Hovy, E. (2002). Learning surface text patterns for a question answering system. In ACL-02, Philadelphia, PA, pp. 41–47.

Riezler, S., King, T. H., Crouch, R., and Zaenen, A. (2003). Statistical sentence condensation using ambiguity packing and stochastic disambiguation methods for Lexical-Functional Grammar. In HLT-NAACL-03, Edmonton, Canada.

Robinson, S. E. and Sparck Jones, K. (1976). Relevance weighting of search terms. Journal of the American Society for Information Science, 27, 129–146.

Rocchio, J. J. (1971). Relevance feedback in information retrieval. In The SMART Retrieval System: Experiments in Automatic Indexing, pp. 324–336. Prentice Hall.

Salton, G. (1971). The SMART Retrieval System: Experiments in Automatic Document Processing. Prentice Hall.

Salton, G. and Buckley, C. (1990). Improving retrieval performance by relevance feedback. Information Processing and Management, 41, 288–297.

Salton, G. and McGill, M. J. (1983). Introduction to Modern Information Retrieval. McGraw-Hill, New York, NY.

Sanderson, M. (1994). Word sense disambiguation and information retrieval. In SIGIR-94, Dublin, Ireland, pp. 142–151. ACM.

Schütze, H. and Pedersen, J. (1995). Information retrieval based on word senses. In Proceedings of the Fourth Annual Symposium on Document Analysis and Information Retrieval, Las Vegas, pp. 161–175.

Siddharthan, A., Nenkova, A., and McKeown, K. R. (2004). Syntactic simplification for improving content selection in multi-document summarization. In COLING-04, p. 896.

Simmons, R. F. (1965). Answering English questions by computer: A survey. Communications of the ACM, 8(1), 53–70.

Soricut, R. and Marcu, D. (2006). Discourse generation using utility-trained coherence models. In COLING/ACL 2006, pp. 803–810.

Sparck Jones, K. (1972). A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation, 28(1), 11–21.

Sparck Jones, K. (2007). Automatic summarising: The state of the art. Information Processing and Management, 43(6), 1449–1481.

Sparck Jones, K. and Willett, P. (Eds.). (1997). Readings in Information Retrieval. Morgan Kaufmann, San Francisco, CA.

Strzalkowski, T. and Harabagiu, S. (Eds.). (2006). Advances in Open Domain Question Answering. Springer.

Teufel, S. and van Halteren, H. (2004). Evaluating information content by factoid analysis: human annotation and stability. In EMNLP 2004, Barcelona.

Teufel, S. and Moens, M. (2002). Summarizing scientific articles: experiments with relevance and rhetorical status. Computational Linguistics, 28(4), 409–445.

Turner, J. and Charniak, E. (2005). Supervised and unsupervised learning for sentence compression. In ACL-05, pp. 290–297.

van Halteren, H. and Teufel, S. (2003). Examining the consensus between human summaries: initial experiments with factoid analysis. In HLT-NAACL-03 Workshop on Text Summarization.

van Rijsbergen, C. J. (1975). Information Retrieval. Butterworths, London.

Vanderwende, L., Suzuki, H., Brockett, C., and Nenkova, A. (2007a). Beyond sumbasic: Task-focused summarization with sentence simplification and lexical expansion. Information Processing and Management, 43(6), 1606–1618.

Vanderwende, L., Suzuki, H., Brockett, C., and Nenkova, A. (2007b). Beyond sumbasic: Task-focused summarization with sentence simplification and lexical expansion. Information Processing and Management, Special issue on summarization, 43(6).

Voorhees, E. M. (1998). Using WordNet for text retrieval. In Fellbaum, C. (Ed.), WordNet: An Electronic Lexical Database, pp. 285–303. MIT Press.

Voorhees, E. M. and Harman, D. K. (2005). TREC: Experiment and Evaluation in Information Retrieval. MIT Press.

Woods, W. A., Kaplan, R. M., and Nash-Webber, B. L. (1972). The lunar sciences natural language information system: Final report.. BBN Report 2378.

Zajic, D., Dorr, B., Lin, J., and Schwartz, R. (2007). Multicandidate reduction: Sentence compression as a tool for document summarization tasks. Information Processing and Management, 43(6), 1549–1570.

24

C: I want you to tell me the names of the fellows on the St. Louis team.

A: I'm telling you. Who's on first, What's on second, I Don't Know is on third.

C: You know the fellows' names?

A: Yes.

C: Well, then, who's playing first?

A: Yes.

C: I mean the fellow's name on first.

A: Who.

C: The guy on first base.

A: Who is on first.

C: Well what are you asking me for?

A: I'm not asking you – I'm telling you. Who is on first.

Who's on First – Bud Abbott and Lou Costello's version of an old burlesque standard.

The literature of the fantastic abounds in inanimate objects magically endowed with sentence and the gift of speech. From Ovid's statue of Pygmalion to Mary Shelley's Frankenstein, Cao Xue Qin's Divine Luminescent Stone-in-Waiting to Snow White's mirror, there is something deeply touching about creating something and then having a chat with it. Legend has it that after finishing his sculpture of Moses, Michelangelo thought it so lifelike that he tapped it on the knee and commanded it to speak. Perhaps this shouldn't be surprising. Language itself has always been the mark of humanity and sentence, and conversation or dialogue is the most fundamental and specially privileged arena of language. It is certainly the first kind of language we learn as children, and for most of us, it is the kind of language we most commonly indulge in, whether we are ordering curry for lunch or buying spinach, participating in business meetings or talking with our families, booking airline flights or complaining about the weather.

This chapter introduces the fundamental structures and algorithms in conversational agents. Conversational agents most often communicate via speech rather than

text, and so they are also known as spoken dialogue systems, or spoken language systems. These programs communicate with users in spoken natural language in order to make travel arrangements, answer questions about weather or sports, route telephone calls, act as a general telephone assistant, or perform even more sophisticated tasks.

Many of these tasks involve telephony, and also involve mobile situations where a large screen and keyboard may not be available (Cohen and Oviatt, 1994). Applications relating to the domain of travel are thus very common. Indeed travel planning and management has been a key concern of dialogue systems since the early influential GUS system for planning airline travel (Bobrow et al., 1977). More recently, a number of spoken language systems for booking airline flights were built under the Air Traffic Information System (ATIS) (Hemphill et al., 1990) and Communicator (Walker, 2001) programs. We will use this travel domain as an example throughout the chapter (as we used it to discuss grammar rules for parsing ATIS sentences in Ch. 12). Fig. 24.1 shows a sample dialogue from a Communicator system, taken from Xu and Rudnicky (2000).

Another promising domain is automatic call routing. A call routing system directs incoming calls in a telephone call center, transferring the call to the appropriate human. Call routing dialogue systems generally begin by asking the user open-ended questions like How may I help you? (Gorin et al., 1997), or How may I direct your call? (Chu-Carroll and Carpenter, 1999). Fig. 24.2 shows sample conversations from the AT&T How May I Help You (HMIHY) system (Gorin et al., 1997).

A somewhat different domain, which is very far from the telephony area, is automatic tutoring systems. Fig. 24.3 shows part of a dialogue from the ITSPOKE dialogue system (Litman and Silliman, 2004), which uses the Why2-Atlas text-based tutoring

system as its tutoring backend (VanLehn et al., 2002).

Sec. 24.1 starts out with a summary of facts about human conversation, including the idea of turns and utterances, speech acts, grounding, dialogue structure, and conversational implicature. The next few sections introduce the components of spoken language systems and some evaluation metrics. We then turn in Sec. 24.5 and Sec. 24.6 to the more sophisticated information-state and Markov decision processes models of conversational agents, and we conclude with some advanced topics like the BDI (belief-desire-intention) paradigm.

24.1 PROPERTIES OF HUMAN CONVERSATIONS

Conversation between humans is an intricate and complex joint activity. Because of the limitations of our current technologies, conversations between humans and machines are vastly simpler and more constrained than these human conversations. Nonetheless,

less, before we attempt to design a conversational agent to converse with humans, it is crucial to understand something about how humans converse with each other.

In this section we discuss some properties of human-human conversation that distinguish it from the kinds of (text-based) discourses we have seen so far. The main difference is that conversation is a kind of joint activity between two (or more) interlocutors. This basic fact has a number of ramifications; conversations are built up out of consecutive turns, each turn consists of joint action of the speaker and hearer, and the hearer makes special inferences called conversational implicatures about the speaker's intended meaning.