21.1.1 Unsupervised Discourse Segmentation

Let's consider the task of segmenting a text into multi-paragraph units that represent subtopics or passages of the original text. As we suggested above, this task is often called linear segmentation, to distinguish it from the task of deriving more sophisticated hierarchical discourse structure. The goal of a segmenter, given raw text, might be to assign subtopic groupings such as the ones defined by Hearst (1997) for the following 21-paragraph science news article called Stargazers on the existence of life on earth and other planets (numbers indicate paragraphs):

1-3 Intro - the search for life in space

4–5 The moon's chemical composition

6-8 How early earth-moon proximity shaped the moon

9–12 How the moon helped life evolve on earth

13 Improbability of the earth-moon system

14–16 Binary/trinary star systems make life unlikely

17–18 The low probability of nonbinary/trinary systems

19–20 Properties of earth's sun that facilitate life

21 Summary

An important class of unsupervised algorithms for the linear discourse segmentation task rely on the concept of cohesion (Halliday and Hasan, 1976). Cohesion is the use of certain linguistic devices to link or tie together textual units. Lexical cohesion is cohesion indicated by relations between words in the two units, such as use of an identical word, a synonym, or a hypernym. For example the fact that the words house, shingled, and I occur in both of the two sentences in (21.8ab), is a cue that the two are tied together as a discourse:

• Before winter I built a chimney, and shingled the sides of my house...

• I have thus a tight shingled and plastered house

In Ex. (21.9), lexical cohesion between the two sentences is indicated by the hypernym relation between fruit and the words pears and apples.

Peel, core and slice the pears and the apples. Add the fruit to the skillet.

There are also non-lexical cohesion relations, such as the use of anaphora, shown here between Woodhouses and them (we will define and discuss anaphora in detail in Sec. 21.6):

The Woodhouses were first in consequence there. All looked up to them.

In addition to single examples of lexical cohesion between two words, we can have a cohesion chain, in which cohesion is indicated by a whole sequence of related words:

Peel, core and slice the pears and the apples. Add the fruit to the skillet. When they are soft...

Coherence and cohesion are often confused; let's review the difference. Cohesion refers to the way textual units are tied or linked together. A cohesive relation is like

a kind of glue grouping together two units into a single unit. Coherence refers to the meaning relation between the two units. A coherence relation explains how the meaning of different textual units can combine to jointly build a discourse meaning for the larger unit.

The intuition of the cohesion-based approach to segmentation is that sentences or paragraphs in a subtopic are cohesive with each other, but not with paragraphs in a neighboring subtopic. Thus if we measured the cohesion between every neighboring sentence, we might expect a ‘dip’ in cohesion at subtopic boundaries.

Let's look at one such cohesion-based approach, the TextTiling algorithm (Hearst, 1997). The algorithm has three steps: tokenization, lexical score determination, and boundary identification. In the tokenization stage, each space-delimited word in the input is converted to lower-case, words in a stop list of function words are thrown out, and the remaining words are morphologically stemmed. The stemmed words are grouped into pseudo-sentences of length $ w = 20 $ (equal-length pseudo-sentences are used rather than real sentences).

Now we look at each gap between pseudo-sentences, and compute a lexical cohesion score across that gap. The cohesion score is defined as the average similarity of the words in the pseudo-sentences before gap to the pseudo-sentences after the gap. We generally use a block of k = 10 pseudo-sentences on each side of the gap. To compute similarity, we create a word vector b from the block before the gap, and a vector a from the block after the gap, where the vectors are of length N (the total number of non-stop words in the document) and the ith element of the word vector is the frequency of the word $ w_i $. Now we can compute similarity by the cosine (= normalized dot product) measure defined in Eq. (??) from Ch. 20, rewritten here:

$$ sim_{cosine}(\vec{b},\vec{a})=\frac{\vec{b}\cdot\vec{a}}{|\vec{b}||\vec{a}|}=\frac{\sum_{i=1}^{N}b_{i}\times a_{i}}{\sqrt{\sum_{i=1}^{N}b_{i}^{2}}\sqrt{\sum_{i=1}^{N}a_{i}^{2}}} $$

This similarity score (measuring how similar pseudo-sentences $i-k$ to $i$ are to sentences $i+1$ to $i+k+1$) is computed for each gap $i$ between pseudo-sentences. Let's look at the example in Fig. 21.1, where $k=2$. Fig. 21.1a shows a schematic view of four pseudo-sentences. Each 20-word pseudo-sentence might have multiple true sentences in it; we've shown each with two true sentences. The figure also indicates the computation of the dot-product between successive pseudosentences. Thus for example in the first pseudo-sentence, consisting of sentences 1 and 2, the word A occurs twice, B once, C twice, and so on. The dot product between the first two pseudosentences is $2\times1+1\times1+2\times1+1\times1+2\times1=8$. What is the cosine between these first two, assuming all words not shown have zero count?

Finally, we compute a depth score for each gap, measuring the depth of the ‘similarity valley’ at the gap. The depth score is the distance from the peaks on both sides of the valley to the valley; In Fig. 21.1(b), this would be $ (y_{a_1} - y_{a_2}) + (y_{a_3} - y_{a_2}) $.

Boundaries are assigned at any valley which is deeper than a cutoff threshold (such as $ \bar{s} - \sigma $, i.e. one standard deviation deeper than the mean valley depth).

Instead of using these depth score thresholds, more recent cohesion-based segmenters use divisive clustering (Choi, 2000; Choi et al., 2001); see the end of the chapter for more information.