21.1.3 Evaluating Discourse Segmentation

Discourse segmentation is generally evaluated by running the algorithm on a test set in which boundaries have been labeled by humans. The performance of the algorithm is computed by comparing the automatic and human boundary labels using the WindowDiff (Pevzner and Hearst, 2002) or $ P_{k} $ (Beeferman et al., 1999) metrics.

We generally don’t use precision, recall and F-measure for evaluating segmentation because they are not sensitive to near misses. Using standard F-measure, if our algorithm was off by one sentence in assigning each boundary, it would get as bad a score as an algorithm which assigned boundaries nowhere near the correct locations. Both WindowDiff and $ P_k $ assign partial credit. We will present WindowDiff, since it is a more recent improvement to $ P_k $.

WindowDiff compares a reference (human labeled) segmentation with a hypothesis segmentation by sliding a probe, a moving window of length $ k $, across the hypothesis segmentation. At each position in the hypothesis string, we compare the number of reference boundaries that fall within the probe $ (r_i) $ to the number of hypothesized boundaries that fall within the probe $ (h_i) $. The algorithm penalizes any hypothesis for which $ r_i \neq h_i $, i.e. for which $ |r_i - h_i| \neq 0 $. The window size $ k $ is set as half the average segment in the reference string. Fig. 21.2 shows a schematic of the computation.

More formally, if $ b(i,j) $ is the number of boundaries between positions i and j in a text, and N is the number of sentences in the text:

$$ \mathrm{WindowDiff}(ref,hyp)=\frac{1}{N-k}\sum_{i=1}^{N-k}(|b(ref_{i},ref_{i+k})-b(hyp_{i},hyp_{i+k})|\neq0) $$

WindowDiff returns a value between 0 and 1, where 0 indicates that all boundaries are assigned correctly.

21.2 TEXT COHERENCE

The previous section showed that cohesive devices, like lexical repetition, can be used to find structure in a discourse. The existence of such devices alone, however, does not satisfy a stronger requirement that a discourse must meet, that of being coherent. We briefly introduced coherence in the introduction. In this section we offer more details on what it means for a text to be coherent, and computational mechanisms for determining coherence. We will focus on coherence relations and reserve entity-based coherence for discussion in Sec. 21.6.2.

Recall from the introduction the difference between passages (21.14) and (21.15).

John hid Bill's car keys. He was drunk.

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

COHERENCE RELATIONS

The reason (21.14) is more coherent is that the reader can form a connection between the two utterances, in which the second utterance provides a potential CAUSE or EXPLANATION for the first utterance. This link is harder to form for (21.15). The possible connections between utterances in a discourse can be specified as a set of coherence relations. A few such relations, proposed by Hobbs (1979), are given below. The terms $ S_{0} $ and $ S_{1} $ represent the meanings of the two sentences being related.

Result: Infer that the state or event asserted by $ S_{0} $ causes or could cause the state or event asserted by $ S_{1} $.

(21.16) The Tin Woodman was caught in the rain. His joints rustled.

Explanation: Infer that the state or event asserted by $ S_{1} $ causes or could cause the state or event asserted by $ S_{0} $.

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

Parallel: Infer $p(a_{1}, a_{2}, \ldots)$ from the assertion of $S_{0}$ and $p(b_{1}, b_{2}, \ldots)$ from the assertion of $S_{1}$, where $a_{i}$ and $b_{i}$ are similar, for all $i$.

(21.18) The Scarecrow wanted some brains. The Tin Woodman wanted a heart.

Elaboration: Infer the same proposition P from the assertions of $ S_{0} $ and

(21.19) Dorothy was from Kansas. She lived in the midst of the great Kansas prairies.

Occasion: A change of state can be inferred from the assertion of $ S_{0} $, whose final state can be inferred from $ S_{1} $, or a change of state can be inferred from the assertion of $ S_{1} $, whose initial state can be inferred from $ S_{0} $.

(21.20) Dorothy picked up the oil-can. She oiled the Tin Woodman's joints.

We can also talk about the coherence of an entire discourse, by considering the hierarchical structure between coherence relations. Consider passage (21.21).

(21.21) John went to the bank to deposit his paycheck. (S1)

He then took a train to Bill's car dealership. (S2)

He needed to buy a car. (S3)

The company he works for now isn't near any public transportation. (S4)

He also wanted to talk to Bill about their softball league. (S5)

Intuitively, the structure of passage (21.21) is not linear. The discourse seems to be primarily about the sequence of events described in sentences S1 and S2, whereas sentences S3 and S5 are related most directly to S2, and S4 is related most directly to S3. The coherence relationships between these sentences result in the discourse structure shown in Figure 21.3.

Each node in the tree represents a group of locally coherent clauses or sentences, called a discourse segment. Roughly speaking, one can think of discourse segments as being analogous to constituents in sentence syntax.

Now that we've seen examples of coherence, we can see more clearly how a coherence relation can play a role in summarization or information extraction. For example, discourses that are coherent by virtue of the Elaboration relation are often characterized by a summary sentence followed by one or more sentences adding detail to it, as in passage (21.19). Although there are two sentences describing events in this passage, the Elaboration relation tells us that the same event is being described in each. Automatic labeling of the Elaboration relation could thus tell an information extraction or summarization system to merge the information from the sentences and produce a single event description instead of two.