Advances in domain independent linear text segmentation
Freddy Y. Y. Choi
Artificial Intelligence Group
Department of Computer Science
Manchester
England
This paper describes a method for linear text segmentation which is twice as accurate and over seven times as fast as the state-of-the-art \cite{reynar_1998}. Inter-sentence similarity is replaced by rank in the local context. Boundary locations are discovered by divisive clustering.
paper.tex
\documentclass[]{article}
\usepackage{colacl}
\usepackage{graphicx}

\title{Advances in domain independent linear text segmentation}

\author{Freddy Y. Y. Choi\\
Artificial Intelligence Group\\
Department of Computer Science\\
University of Manchester\\
Manchester, England\\
{\it choif@cs.man.ac.uk}
}

\begin{document}
\maketitle

\begin{abstract}
This paper describes a method for linear text segmentation which is twice as accurate and over seven times as fast as the state-of-the-art \cite{reynar_1998}. Inter-sentence similarity is replaced by rank in the local context. Boundary locations are discovered by divisive clustering.
\end{abstract}

\section{Introduction}
%\subsection{Motivation}
Even moderately long documents typically address several topics or different aspects of the same topic. The aim of linear text segmentation is to discover the topic boundaries. The uses of this procedure include information retrieval \cite{hearst_plaunt_1993,hearst_1994,yaari_1997,reynar_1999}, summarization \cite{reynar_1998}, text understanding, anaphora resolution \cite{kozima_1993}, language modelling \cite{morris_hirst_1991,beeferman_et_al_1997} and improving document navigation for the visually disabled \cite{choi_2000iee}.

%\subsection{Overview}
This paper focuses on domain independent methods for segmenting written text. We present a new algorithm that builds on previous work by Reynar \cite{reynar_1998,reynar_1994}. The primary distinction of our method is the use of a ranking scheme and the cosine similarity measure \cite{rijsbergen_1979} in formulating the similarity matrix. We propose that the similarity values of short text segments is statistically insignificant. Thus, one can only rely on their order, or rank, for clustering.

\section{Background}
%\subsection{Segmentation methods}
Existing work falls into one of two categories, lexical cohesion methods and multi-source methods \cite{yaari_1997}. The former stem from the work of Halliday and Hasan \cite{halliday_hasan_1976}. They proposed that text segments with similar vocabulary are likely to be part of a coherent topic segment. Implementations of this idea use word stem repetition \cite{youmans_1991,reynar_1994,ponte_croft_1997}, context vectors \cite{hearst_1994,yaari_1997,kaufmann_1999,eichmann_et_al_1999}, entity repetition \cite{kan_et_al_1998}, semantic similarity \cite{morris_hirst_1991,kozima_1993}, word distance model \cite{beeferman_et_al_1997b} and word frequency model \cite{reynar_1999} to detect cohesion. Methods for finding the topic boundaries include sliding window \cite{hearst_1994}, lexical chains \cite{morris_1988,kan_et_al_1998}, dynamic programming \cite{ponte_croft_1997,heinonen_1998}, agglomerative clustering \cite{yaari_1997} and divisive clustering \cite{reynar_1994}. Lexical cohesion methods are typically used for segmenting written text in a collection to improve information retrieval \cite{hearst_1994,reynar_1998}. 

Multi-source methods combine lexical cohesion with other indicators of topic shift such as cue phrases, prosodic features, reference, syntax and lexical attraction \cite{beeferman_et_al_1997b} using decision trees \cite{miike_et_al_1994,kurohashi_nagao_1994,litman_passonneau_1995} and probabilistic models \cite{beeferman_et_al_1997,hajime_1997,reynar_1998}. Work in this area is largely motivated by the topic detection and tracking (TDT) initiative \cite{allan_et_al_1998}. The focus is on the segmentation of transcribed spoken text and broadcast news stories where the presentation format and regular cues can be exploited to improve accuracy.

%\subsection{The minimal topic segment}
%Previous studies have provided us with a set of constraints and suggestions about the nature of a topic but no clear definition. Some linguists believe the paragraph is a universal linguistic structure for representing a coherent textual segment \cite{longacre_1979,chafe_1979,kieras_1982}. Most segmentation algorithms consider only paragraph boundaries as potential topic boundaries \cite{hearst_1994,yaari_1997,heinonen_1998,kan_et_al_1998}. Yaari also suggested that it is counter to the author's intention to segment a paragraph. We disagree with this view. 

%Lets consider a topic as a text segment that presents a piece of information. In the context of passage retrieval, a relevant, or informative, passage may consists of only several sentences \cite{ponte_croft_1997}. Topic boundaries are not necessarily aligned with paragraph boundaries \cite{callan_1994,mittendorf_1994}. In discourse analysis, a clause is regarded as the smallest text unit with function or information \cite{mann_thompson_1988}. Thus, a paragraph break is merely a useful indicator of topic shift. We believe the sentence is a more appropriate elementary unit for linear segmentation.

\section{Algorithm}
Our segmentation algorithm takes a list of tokenized sentences as input. A tokenizer \cite{grefenstette_1994} and a sentence boundary disambiguation algorithm \cite{palmer_hearst_1994,reynar_ratnaparkhi_1997} or EAGLE \cite{reynar_1997b} may be used to convert a plain text document into the acceptable input format.

\subsection{Similarity measure}
Punctuation and uninformative words are removed from each sentence using a simple regular expression pattern matcher and a stopword list. A stemming algorithm \cite{porter_1980} is then applied to the remaining tokens to obtain the word stems. A dictionary of word stem frequencies is constructed for each sentence. This is represented as a vector of frequency counts.

Let $f_{i,j}$ denote the frequency of word $j$ in sentence $i$. The similarity between a pair of sentences $x,y$ is computed using the cosine measure as shown in equation \ref{eq:cosine}. This is applied to all sentence pairs to generate a similarity matrix.
\begin{equation}
sim(x,y) = \frac{\sum_{j} f_{x,j} \times f_{y,j}}{\sqrt{{\sum_{j} f_{x,j}^2} \times {\sum_{j} f_{y,j}^2}}}
\label{eq:cosine}
\end{equation}

Figure \ref{fig:simmatrix} shows an example of a similarity matrix\footnote{The contrast of the image has been adjusted to highlight the image features. }. High similarity values are represented by bright pixels. The bottom-left and top-right pixel show the self-similarity for the first and last sentence, respectively. Notice the matrix is symmetric and contains bright square regions along the diagonal. These regions represent cohesive text segments.

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.3\textwidth]{simMatrix.eps}
\end{center}
\caption{An example similarity matrix.}
\label{fig:simmatrix}
\end{figure}

\subsection{Ranking}
For short text segments, the absolute value of $sim(x,y)$ is unreliable. An additional occurrence of a common word (reflected in the numerator) causes a disproportionate increase in $sim(x,y)$ unless the denominator (related to segment length) is large. Thus, in the context of text segmentation where a segment has typically $< 100$ informative tokens, one can only use the metric to estimate the order of similarity between sentences, e.g. $a$ is more similar to $b$ than $c$.

Furthermore, language usage varies throughout a document. For instance, the introduction section of a document is less cohesive than a section which is about a particular topic. Consequently, it is inappropriate to directly compare the similarity values from different regions of the similarity matrix.

In non-parametric statistical analysis, one compares the rank of data sets when the qualitative behaviour is similar but the absolute quantities are unreliable. We present a ranking scheme which is an adaptation of that described in \cite{oneil_denos_1992}.

Each value in the similarity matrix is replaced by its rank in the local region. The rank is the number of neighbouring elements with a lower similarity value. Figure \ref{fig:rank} shows an example of image ranking using a $3 \times 3$ rank mask with output range $\{0,8\}$. For segmentation, we used a $11 \times 11$ rank mask. The output is expressed as a ratio $r$ (equation \ref{eq:rankRatio}) to circumvent normalisation problems (consider the cases when the rank mask is not contained in the image).

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.48\textwidth]{ranking.eps}
\end{center}
\caption{A working example of image ranking.}
\label{fig:rank}
\end{figure}

\begin{equation}
r = \frac{\textrm{\# of elements with a lower value}}{\textrm{\# of elements examined}}
\label{eq:rankRatio}
\end{equation}

To demonstrate the effect of image ranking, the process was applied to the matrix shown in figure \ref{fig:simmatrix} to produce figure \ref{fig:rankmatrix}\footnote{The process was applied to the original matrix, prior to contrast enhancement. The output image has not been enhanced.}. Notice the contrast has been improved significantly. Figure \ref{fig:rankillus} illustrates the more subtle effects of our ranking scheme. $r(x)$ is the rank ($1 \times 11$ mask) of $f(x)$ which is a sine wave with decaying mean, amplitude and frequency (equation \ref{eq:wave}).

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.3\textwidth]{rankMatrix.eps}
\end{center}
\caption{The matrix in figure \ref{fig:simmatrix} after ranking.}
\label{fig:rankmatrix}
\end{figure}

\begin{equation}
\begin{array}{rcl}
f(x) & = & g(x \times \frac{2 \pi}{200}) \\
&&\\
g(z) & = & \frac{1}{2}(e^{- z / 2} + \frac{1}{2} e^{- z / 2} (1 + \sin(10z^{0.7}))) \\
\end{array}
\label{eq:wave}
\end{equation}

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.48\textwidth]{rankIllus.eps}
\end{center}
\caption{An illustration of the more subtle effects of our ranking scheme.}
\label{fig:rankillus}
\end{figure}

\subsection{Clustering}
The final process determines the location of the topic boundaries. The method is based on Reynar's maximisation algorithm \cite{reynar_1998,helfman_1996,church_1993,church_helfman_93}. A text segment is defined by two sentences $i,j$ (inclusive). This is represented as a square region along the diagonal of the rank matrix. Let $s_{i,j}$ denote the sum of the rank values in a segment and $a_{i,j} = (j-i+1)^2$ be the inside area. $B = \{b_1,...,b_m\}$ is a list of $m$ coherent text segments. $s_k$ and $a_k$ refers to the sum of rank and area of segment $k$ in $B$. $D$ is the inside density of $B$ (see equation \ref{eq:insidedensity}).

\begin{equation}
D = \frac{\sum_{k=1}^{m} s_k}{\sum_{k=1}^{m} a_k}
\label{eq:insidedensity}
\end{equation}

To initialise the process, the entire document is placed in $B$ as one coherent text segment. Each step of the process splits one of the segments in $B$. The split point is a potential boundary which maximises $D$. Figure \ref{fig:split} shows a working example.

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.48\textwidth]{clustering.eps}
\end{center}
\caption{A working example of the divisive clustering algorithm.}
\label{fig:split}
\end{figure}

The number of segments to generate, $m$, is determined automatically. $D^{(n)}$ is the inside density of $n$ segments and $\delta D^{(n)} = D^{(n)} - D^{(n-1)}$ is the gradient. For a document with $b$ potential boundaries, $b$ steps of divisive clustering generates $\{D^{(1)},...,D^{(b+1)}\}$ and $\{\delta D^{(2)},...,\delta D^{(b+1)}\}$ (see figure \ref{fig:densityPlot} and \ref{fig:gradientPlot}). An unusually large reduction in $\delta D$ suggests the optimal clustering has been obtained\footnote{In practice, convolution (mask $\{1,2,4,8,4,2,1\}$) is first applied to $\delta D$ to smooth out sharp local changes} (see $n=10$ in figure \ref{fig:gradientPlot}). Let $\mu$ and $\nu$ be the mean and variance of $\delta D^{(n)}, n \in \{2,...,b+1\}$. $m$ is obtained by applying the threshold, $\mu + c \times \sqrt{\nu}$, to $\delta D$ ($c=1.2$ works well in practice).

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.48\textwidth]{density.eps}
\end{center}
\caption{The inside density of all levels of segmentation.}
\label{fig:densityPlot}
\end{figure}

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.48\textwidth]{gradient.eps}
\end{center}
\caption{Finding the optimal segmentation using the gradient.}
\label{fig:gradientPlot}
\end{figure}

\subsection{Speed optimisation}
\label{sec:speed}
The running time of each step is dominated by the computation of $s_k$. Given $s_{i,j}$ is constant, our algorithm pre-computes all the values to improve speed performance. The procedure computes the values along diagonals, starting from the main diagonal and works towards the corner. The method has a complexity of order $1\frac{1}{2} n^2$. Let $r_{i,j}$ refer to the rank value in the rank matrix $R$ and $S$ to the sum of rank matrix. Given $R$ of size $n \times n$, $S$ is computed in three steps (see equation \ref{eq:sumrank}). Figure \ref{fig:sumrank} shows the result of applying this procedure to the rank matrix in figure \ref{fig:split}.

\begin{equation}
\begin{array}{llcl}
1. & s_{i,i}   & = & r_{i,i} \\
   &           & \textrm{for}  & i \in \{1,...,n\} \\
2. & s_{i+1,i} & = & 2 r_{i+1,i} + s_{i,i} + s_{i+1,i+1} \\
   & s_{i,i+1} & = & s_{i+1,i} \\
   &           & \textrm{for} & i \in \{1,...,n-1\} \\
3. & s_{i+j,i} & = & 2 r_{i+j,i} + s_{i+j-1,i} +\\
   &           &   & s_{i+j,i+1} - s_{i+j-1,i+1} \\
   & s_{i,i+j} & = & s_{i+j,i} \\
   &           & \textrm{for} & j \in \{2,...,n-1\} \\
   &           &   & i \in \{1,...,n-j\} \\
\end{array}
\label{eq:sumrank}
\end{equation}

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.48\textwidth]{ranksum.eps}
\end{center}
\caption{Improving speed performance by pre-computing $s_{i,j}$.}
\label{fig:sumrank}
\end{figure}

\section{Evaluation}
The definition of a topic segment ranges from complete stories \cite{allan_et_al_1998} to summaries \cite{ponte_croft_1997}. Given the quality of an algorithm is task dependent, the following experiments focus on the relative performance. Our evaluation strategy is a variant of that described in \cite[71-73]{reynar_1998} and the TDT segmentation task \cite{allan_et_al_1998}. We assume a good algorithm is one that finds the most prominent topic boundaries.
 
\subsection{Experiment procedure}
An artificial test corpus of 700 samples is used to assess the accuracy and speed performance of segmentation algorithms. A sample is a concatenation of ten text segments. A segment is the first $n$ sentences of a randomly selected document from the Brown corpus\footnote{Only the news articles {\tt ca**.pos} and informative text {\tt cj**.pos} were used in the experiment.}. A sample is characterised by the range of $n$. The corpus was generated by an automatic procedure\footnote{All experiment data, algorithms, scripts and detailed results are available from the author.}. Table \ref{tbl:testCorpus} presents the corpus statistics.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
Range of $n$ & $3-11$ & $3-5$ & $6-8$ & $9-11$ \\
\hline
\# samples & 400 & 100 & 100 & 100 \\
\hline
\end{tabular}
\end{center}
\caption{Test corpus statistics.}
\label{tbl:testCorpus}
\end{table}

\begin{equation}
\begin{array}{l}
p(\textrm{error}|\textrm{ref},\textrm{hyp},k) = \\
\quad p(\textrm{miss}|\textrm{ref},\textrm{hyp},\textrm{diff},k)
p(\textrm{diff}|\textrm{ref},k) + \\
\quad p(\textrm{fa}|\textrm{ref},\textrm{hyp},\textrm{same},k)
p(\textrm{same}|\textrm{ref},k) \\
\end{array}
\label{eq:beefermanMetric}
\end{equation}

Speed performance is measured by the average number of CPU seconds required to process a test sample\footnote{All experiments were conducted on a Pentium II 266MHz PC with 128Mb RAM running RedHat Linux 6.0 and the Blackdown Linux port of JDK1.1.7 v3.}. Segmentation accuracy is measured by the error metric (equation \ref{eq:beefermanMetric}, fa $\to$ false alarms) proposed in \cite{beeferman_et_al_1999}. Low error probability indicates high accuracy. Other performance measures include the popular precision and recall metric (PR) \cite{hearst_1994}, fuzzy PR \cite{reynar_1998} and edit distance \cite{ponte_croft_1997}. The problems associated with these metrics are discussed in \cite{beeferman_et_al_1999}.

\subsection{Experiment 1 - Baseline}
Five degenerate algorithms define the baseline for the experiments. $B_n$ does not propose any boundaries. $B_a$ reports all potential boundaries as real boundaries. $B_e$ partitions the sample into regular segments. $B_{(r,?)}$ randomly selects any number of boundaries as real boundaries. $B_{(r,b)}$ randomly selects $b$ boundaries as real boundaries.

The accuracy of the last two algorithms are computed analytically. We consider the status of $m$ potential boundaries as a bit string ($1 \to$ topic boundary). The terms $p(\textrm{miss})$ and $p(\textrm{fa})$ in equation \ref{eq:beefermanMetric} corresponds to $p(\textrm{same}|k)$ and $p(\textrm{diff}|k) = 1 - p(\textrm{same}|k)$. Equation \ref{eq:bGen}, \ref{eq:bRanUnknown} and \ref{eq:bRanKnown} gives the general form of $p(\textrm{same}|k)$, $B_{(r,?)}$ and $B_{(r,b)}$, respectively\footnote{The full derivation of our method is available from the author.}. 

Table \ref{tbl:baseline} presents the experimental results. The values in row two and three, four and five are not actually the same. However, their differences are insignificant according to the Kolmogorov-Smirnov, or KS-test \cite{ks_test}.

\begin{equation}
p(\textrm{same}|k) = \frac{\textrm{\# valid segmentations}}{\textrm{\# possible segmentations}}
\label{eq:bGen}
\end{equation}

\begin{equation}
p(\textrm{same}|k,B_{(r,?)}) = \frac{2^{m-k}}{2^m} = 2^{-k}
\label{eq:bRanUnknown}
\end{equation}

\begin{equation}
\begin{array}{rcl}
p(\textrm{same}|k,m,B_{(r,b)}) & = & \frac{_{(m-k)}C_b}{_mC_b} \\
&&\\
_xC_y & = & \frac{x!}{y!(x-y)!} \\
\end{array}
\label{eq:bRanKnown}
\end{equation}
 
\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
      & 3-11 & 3-5 & 6-8 & 9-11 \\
\hline
$B_e$ & 45\% & 38\% & 39\% & 36\% \\
$B_n$ & 47\% & 47\% & 47\% & 46\% \\
$B_{(r,b)}$ & 47\% & 47\% & 47\% & 46\% \\
$B_a$ & 53\% & 53\% & 53\% & 54\% \\
$B_{(r,?)}$ & 53\% & 53\% & 53\% & 54\% \\
\hline
\end{tabular}
\end{center}
\caption{The error rate of the baseline algorithms.}
\label{tbl:baseline}
\end{table}

\subsection{Experiment 2 - TextTiling}
We compare three versions of the TextTiling algorithm \cite{hearst_1994}. $H94_{(c,d)}$ is Hearst's C implementation with default parameters. $H94_{(c,r)}$ uses the recommended parameters $k=6$, $w=20$. $H94_{(j,r)}$ is my implementation of the algorithm. Experimental result (table \ref{tbl:textTile}) shows $H94_{(c,d)}$ and $H94_{(c,r)}$ are more accurate than $H94_{(j,r)}$. We suspect this is due to the use of a different stopword list and stemming algorithm.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
      & 3-11 & 3-5 & 6-8 & 9-11 \\
\hline
$H94_{(c,d)}$ & 46\% & 44\% & 43\% & 48\% \\
$H94_{(c,r)}$ & 46\% & 44\% & 44\% & 49\% \\
$H94_{(j,r)}$ & 54\% & 45\% & 52\% & 53\% \\
\hline
$H94_{(c,d)}$ & 0.67s & 0.52s & 0.66s & 0.88s\\
$H94_{(c,r)}$ & 0.68s & 0.52s & 0.67s & 0.92s\\
$H94_{(j,r)}$ & 3.77s & 2.21s & 3.69s & 5.07s\\
\hline
\end{tabular}
\end{center}
\caption{The error rate and speed performance of TextTiling.}
\label{tbl:textTile}
\end{table}

\subsection{Experiment 3 - DotPlot}
Five versions of Reynar's optimisation algorithm \cite{reynar_1998} were evaluated. $R98$ and $R98_{(min)}$ are exact implementations of his maximisation and minimisation algorithm. $R98_{(s,cos)}$ is my version of the maximisation algorithm which uses the cosine coefficient instead of dot density for measuring similarity. It incorporates the optimisations described in section \ref{sec:speed}. $R98_{(m,dot)}$ is the modularised version of $R98$ for experimenting with different similarity measures.

$R98_{(m,sa)}$ uses a variant of Kozima's semantic similarity measure \cite{kozima_1993} to compute block similarity. Word similarity is a function of word co-occurrence statistics in the given document. Words that belong to the same sentence are considered to be related. Given the co-occurrence frequencies $f(w_i,w_j)$, the transition probability matrix $t$ is computed by equation \ref{eq:trans}. Equation \ref{eq:spread} defines our spread activation scheme. $s$ denotes the word similarity matrix, $x$ is the number of activation steps and $\textrm{norm}(y)$ converts a matrix $y$ into a transition matrix. $x=5$ was used in the experiment.

\begin{equation}
t_{i,j} = p(w_j|w_i) = \frac{f(w_i,w_j)}{\sum_j f(w_i,w_j)}
\label{eq:trans}
\end{equation}

\begin{equation}
s = \textrm{norm} \left(\sum_{i=1}^{x} t^i \right)
\label{eq:spread}
\end{equation}

Experimental result (table \ref{tbl:dotplot}) shows the cosine coefficient and our spread activation method improved segmentation accuracy. The speed optimisations significantly reduced the execution time.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
 & 3-11 & 3-5 & 6-8 & 9-11\\
\hline
$R98_{(m,sa)}$ & 18\% & 20\% & 15\% & 12\% \\
$R98_{(s,cos)}$ & 21\% & 18\% & 19\% & 18\% \\
$R98_{(m,dot)}$ & 22\% & 21\% & 18\% & 16\% \\
$R98$ & 22\% & 21\% & 18\% & 16\% \\
$R98_{(min)}$ & n/a & 34\% & 37\% & 37\% \\
\hline
$R98_{(s,cos)}$ & 4.54s & 2.24s & 4.36s & 6.99s\\
$R98$ & 29.58s & 9.29s & 28.09s & 55.03s\\
$R98_{(m,sa)}$ & 41.02s & 7.34s & 40.05s & 113.5s\\
$R98_{(m,dot)}$ & 46.58s & 9.24s & 42.72s & 115.4s\\
$R98_{(min)}$ & n/a & 19.62s & 58.77s & 122.6s\\
\hline
\end{tabular}
\end{center}
\caption{The error rate and speed performance of Reynar's optimisation algorithm.}
\label{tbl:dotplot}
\end{table}

\subsection{Experiment 4 - Segmenter}
We compare three versions of Segmenter \cite{kan_et_al_1998}. $K98_{(p)}$ is the original Perl implementation of the algorithm (version 1.6). $K98_{(j)}$ is my implementation of the algorithm. $K98_{(j,a)}$ is a version of $K98_{(j)}$ which uses a document specific chain breaking strategy. The distribution of link distances are used to identify unusually long links. The threshold is a function $\mu + c \times \sqrt{\nu}$ of the mean $\mu$ and variance $\nu$. We found $c = 1$ works well in practice.

Table \ref{tbl:segmenter} summarises the experimental results. $K98_{(p)}$ performed significantly better than $K98_{(j,*)}$. This is due to the use of a different part-of-speech tagger and shallow parser. The difference in speed is largely due to the programming languages and term clustering strategies. Our chain breaking strategy improved accuracy (compare $K98_{(j)}$ with $K98_{(j,a)}$).

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
 & 3-11 & 3-5 & 6-8 & 9-11\\
\hline
$K98_{(p)}$ & 36\% & 23\% & 33\% & 43\% \\
$K98_{(j,a)}$ & n/a & 41\% & 46\% & 50\% \\
$K98_{(j)}$ & n/a & 44\% & 48\% & 51\% \\
\hline
$K98_{(p)}$ & 4.24s & 2.57s & 4.21s & 6.00s \\
$K98_{(j)}$ & n/a & 21.43s & 65.54s & 129.3s \\
$K98_{(j,a)}$ & n/a & 21.44s & 65.49s & 129.7s \\
\hline
\end{tabular}
\end{center}
\caption{The error rate and speed performance of Segmenter.}
\label{tbl:segmenter}
\end{table}

\subsection{Experiment 5 - Our algorithm, $C99$}
Two versions of our algorithm were developed, $C99$ and $C99_{(b)}$. The former is an exact implementation of the algorithm described in this paper. The latter is given the expected number of topic segments for fair comparison with $R98$. Both algorithms used a $11 \times 11$ ranking mask.

The first experiment focuses on the impact of our automatic termination strategy on $C99_{(b)}$ (table \ref{tbl:c99}). $C99_{(b)}$ is marginally more accurate than $C99$. This indicates our automatic termination strategy is effective but not optimal. The minor reduction in speed performance is acceptable.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
 & 3-11 & 3-5 & 6-8 & 9-11\\
\hline
$C99_{(b)}$ & 12\% & 12\% & 9\% & 9\% \\
$C99$ & 13\% & 18\% & 10\% & 10\% \\
\hline
$C99_{(b)}$ & 4.00s & 1.91s & 3.73s & 5.99s \\
$C99$ & 4.04s & 2.12s & 4.04s & 6.31s \\
\hline
\end{tabular}
\end{center}
\caption{The error rate and speed performance of our algorithm, $C99$.}
\label{tbl:c99}
\end{table}

The second experiment investigates the effect of different ranking mask size on the performance of $C99$ (table \ref{tbl:c99mask}). Execution time increases with mask size. A $1 \times 1$ ranking mask reduces all the elements in the rank matrix to zero. Interestingly, the increase in ranking mask size beyond $3 \times 3$ has insignificant effect on segmentation accuracy. This suggests the use of extrema for clustering has a greater impact on accuracy than linearising the similarity scores (figure \ref{fig:rankillus}).

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
 & 3-11 & 3-5 & 6-8 & 9-11\\
\hline
$1 \times 1$ & 48\% & 48\% & 50\% & 49\% \\
$3 \times 3$ & 12\% & 11\% & 10\% & 8\% \\
$5 \times 5$ & 12\% & 11\% & 10\% & 8\% \\
$7 \times 7$ & 12\% & 11\% & 10\% & 8\% \\
$9 \times 9$ & 12\% & 11\% & 10\% & 9\% \\
$11 \times 11$ & 12\% & 11\% & 10\% & 9\% \\
$13 \times 13$ & 12\% & 11\% & 10\% & 9\% \\
$15 \times 15$ & 12\% & 11\% & 10\% & 9\% \\
$17 \times 17$ & 12\% & 10\% & 10\% & 8\% \\
\hline
$1 \times 1$ & 3.92s & 2.06s & 3.84s & 5.91s\\
$3 \times 3$ & 3.83s & 2.03s & 3.79s & 5.85s\\
$5 \times 5$ & 3.86s & 2.04s & 3.84s & 5.92s\\
$7 \times 7$ & 3.90s & 2.06s & 3.88s & 6.00s\\
$9 \times 9$ & 3.96s & 2.07s & 3.92s & 6.12s\\
$11 \times 11$ & 4.02s & 2.09s & 3.98s & 6.26s\\
$13 \times 13$ & 4.11s & 2.11s & 4.07s & 6.41s\\
$15 \times 15$ & 4.20s & 2.14s & 4.14s & 6.60s\\
$17 \times 17$ & 4.29s & 2.17s & 4.25s & 6.79s\\
\hline
\end{tabular}
\end{center}
\caption{The impact of mask size on the performance of $C99$.}
\label{tbl:c99mask}
\end{table}

\subsection{Summary}
Experimental result (table \ref{tbl:sum}) shows our algorithm $C99$ is more accurate than existing algorithms. A two-fold increase in accuracy and seven-fold increase in speed was achieved (compare $C99_{(b)}$ with $R98$). If one disregards segmentation accuracy, $H94$ has the best algorithmic performance (linear). $C99$, $K98$ and $R98$ are all polynomial time algorithms. The significance of our results has been confirmed by both t-test and KS-test.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
      & 3-11 & 3-5 & 6-8 & 9-11 \\
\hline
$C99_{(b)}$ & 12\% & 12\% & 9\% & 9\% \\
$C99$ & 13\% & 18\% & 10\% & 10\% \\
$R98$ & 22\% & 21\% & 18\% & 16\% \\
$K98_{(p)}$ & 36\% & 23\% & 33\% & 43\% \\
$H94_{(c,d)}$ & 46\% & 44\% & 43\% & 48\% \\
\hline
$H94_{(j,r)}$ & 3.77s & 2.21s & 3.69s & 5.07s\\
$C99_{(b)}$ & 4.00s & 1.91s & 3.73s & 5.99s \\
$C99$ & 4.04s & 2.12s & 4.04s & 6.31s \\
$R98$ & 29.58s & 9.29s & 28.09s & 55.03s\\
$K98_{(j)}$ & n/a & 21.43s & 65.54s & 129.3s \\
\hline
\end{tabular}
\end{center}
\caption{A summary of our experimental results.}
\label{tbl:sum}
\end{table}

\section{Conclusions and future work}
A segmentation algorithm has two key elements, a clustering strategy and a similarity measure. Our results show divisive clustering ($R98$) is more precise than sliding window ($H94$) and lexical chains ($K98$) for locating topic boundaries.

Four similarity measures were examined. The cosine coefficient ($R98_{(s,cos)}$) and dot density measure ($R98_{(m,dot)}$) yield similar results. Our spread activation based semantic measure ($R98_{(m,sa)}$) improved accuracy. This confirms that although Kozima's approach \cite{kozima_1993} is computationally expensive, it does produce more precise segmentation.

The most significant improvement was due to our ranking scheme which linearises the cosine coefficient. Our experiments demonstrate that given insufficient data, the qualitative behaviour of the cosine measure is indeed more reliable than the actual values.

Although our evaluation scheme is sufficient for this comparative study, further research requires a large scale, task independent benchmark. It would be interesting to compare $C99$ with the multi-source method described in \cite{beeferman_et_al_1999} using the TDT corpus. We would also like to develop a linear time and multi-source version of the algorithm.

\section*{Acknowledgements}
This paper has benefitted from the comments of Mary McGee Wood and the anonymous reviewers. Thanks are due to my parents and department for making this work possible; Jeffrey Reynar for discussions and guidance on the segmentation problem; Hideki Kozima for help on the spread activation measure; Min-Yen Kan and Marti Hearst for their segmentation algorithms; Daniel Oram for references to image processing techniques; Magnus Rattray and Stephen Marsland for help on statistics and mathematics.

\bibliographystyle{acl}
\bibliography{references}
\end{document}
paper.bbl
\begin{thebibliography}{}

\bibitem[\protect\citename{Allan \bgroup et al.\egroup }1998]{allan_et_al_1998}
James Allan, Jaime Carbonell, George Doddington, Jonathan Yamron, and Yiming
  Yang.
\newblock 1998.
\newblock Topic detection and tracking pilot study final report.
\newblock In {\em Proceedings of the DARPA Broadcast News Transcription and
  Understanding Workshop}.

\bibitem[\protect\citename{Beeferman \bgroup et al.\egroup
  }1997a]{beeferman_et_al_1997b}
Doug Beeferman, Adam Berger, and John Lafferty.
\newblock 1997a.
\newblock A model of lexical attraction and repulsion.
\newblock In {\em Proceedings of the 35th Annual Meeting of the ACL}.

\bibitem[\protect\citename{Beeferman \bgroup et al.\egroup
  }1997b]{beeferman_et_al_1997}
Doug Beeferman, Adam Berger, and John Lafferty.
\newblock 1997b.
\newblock Text segmentation using exponential models.
\newblock In {\em Proceedings of EMNLP-2}.

\bibitem[\protect\citename{Beeferman \bgroup et al.\egroup
  }1999]{beeferman_et_al_1999}
Doug Beeferman, Adam Berger, and John Lafferty.
\newblock 1999.
\newblock Statistical models for text segmentation.
\newblock {\em Machine learning, special issue on Natural Language Processing},
  34(1-3):177--210.
\newblock C. Cardie and R. Mooney (editors).

\bibitem[\protect\citename{Choi}2000]{choi_2000iee}
Freddy Y.~Y. Choi.
\newblock 2000.
\newblock A speech interface for rapid reading.
\newblock In {\em Proceedings of IEE colloquium: Speech and Language Processing
  for Disabled and Elderly People}, London, England, April. IEE.

\bibitem[\protect\citename{Church and Helfman}1993]{church_helfman_93}
Kenneth~W. Church and Jonathan~I. Helfman.
\newblock 1993.
\newblock Dotplot: A program for exploring self-similarity in millions of lines
  of text and code.
\newblock {\em The Journal of Computational and Graphical Statistics}.

\bibitem[\protect\citename{Church}1993]{church_1993}
Kenneth~W. Church.
\newblock 1993.
\newblock Char\_align: A program for aligning parallel texts at the character
  level.
\newblock In {\em Proceedings of the 31st Annual Meeting of the ACL}.

\bibitem[\protect\citename{Eichmann \bgroup et al.\egroup
  }1999]{eichmann_et_al_1999}
David Eichmann, Miguel Ruiz, and Padmini Srinivasan.
\newblock 1999.
\newblock A cluster-based approach to tracking, detection and segmentation of
  broadcast news.
\newblock In {\em Proceedings of the 1999 DARPA Broadcast News Workshop
  (TDT-2)}.

\bibitem[\protect\citename{Grefenstette and Tapanainen}1994]{grefenstette_1994}
Gregory Grefenstette and Pasi Tapanainen.
\newblock 1994.
\newblock What is a word, what is a sentence? problems of tokenization.
\newblock In {\em Proceedings of the 3rd Conference on Computational
  Lexicography and Text Research (COMPLEX'94)}, Budapest, July.

\bibitem[\protect\citename{Hajime \bgroup et al.\egroup }1998]{hajime_1997}
Mochizuki Hajime, Honda Takeo, and Okumura Manabu.
\newblock 1998.
\newblock Text segmentation with multiple surface linguistic cues.
\newblock In {\em Proceedings of COLING-ACL'98}, pages 881--885.

\bibitem[\protect\citename{Halliday and Hasan}1976]{halliday_hasan_1976}
Michael Halliday and Ruqaiya Hasan.
\newblock 1976.
\newblock {\em Cohesion in English}.
\newblock Longman Group, New York.

\bibitem[\protect\citename{Hearst and Plaunt}1993]{hearst_plaunt_1993}
Marti Hearst and Christian Plaunt.
\newblock 1993.
\newblock Subtopic structuring for full-length document access.
\newblock In {\em Proceedings of the 16th Annual International ACM/SIGIR
  Conference}, Pittsburgh, PA.

\bibitem[\protect\citename{Hearst}1994]{hearst_1994}
Marti~A. Hearst.
\newblock 1994.
\newblock Multi-paragraph segmentation of expository text.
\newblock In {\em Proceedings of the ACL'94}.
\newblock Las Crces, NM.

\bibitem[\protect\citename{Heinonen}1998]{heinonen_1998}
Oskari Heinonen.
\newblock 1998.
\newblock Optimal multi-paragraph text segmentation by dynamic programming.
\newblock In {\em Proceedings of COLING-ACL'98}.

\bibitem[\protect\citename{Helfman}1996]{helfman_1996}
Jonathan~I. Helfman.
\newblock 1996.
\newblock Dotplot patterns: A literal look at pattern languages.
\newblock {\em Theory and Practice of Object Systems}, 2(1):31--41.

\bibitem[\protect\citename{Kan \bgroup et al.\egroup }1998]{kan_et_al_1998}
Min-Yen Kan, Judith~L. Klavans, and Kathleen~R. McKeown.
\newblock 1998.
\newblock Linear segmentation and segment significance.
\newblock In {\em Proceedings of the 6th International Workshop of Very Large
  Corpora (WVLC-6)}, pages 197--205, Montreal, Quebec, Canada, August.

\bibitem[\protect\citename{Kaufmann}1999]{kaufmann_1999}
Stefan Kaufmann.
\newblock 1999.
\newblock Cohesion and collocation: Using context vectors in text segmentation.
\newblock In {\em Proceedings of the 37th Annual Meeting of the Association of
  for Computational Linguistics (Student Session)}, pages 591--595, College
  Park, USA, June. ACL.

\bibitem[\protect\citename{Kozima}1993]{kozima_1993}
Hideki Kozima.
\newblock 1993.
\newblock Text segmentation based on similarity between words.
\newblock In {\em Proceedings of ACL'93}, pages 286--288, Ohio.

\bibitem[\protect\citename{Kurohashi and Nagao}1994]{kurohashi_nagao_1994}
Sadao Kurohashi and Makoto Nagao.
\newblock 1994.
\newblock Automatic detection of discourse structure by checking surface
  information in sentences.
\newblock In {\em Processings of COLING'94}, volume~2, pages 1123--1127.

\bibitem[\protect\citename{Litman and Passonneau}1995]{litman_passonneau_1995}
Diane~J. Litman and Rebecca~J. Passonneau.
\newblock 1995.
\newblock Combining multiple knowledge sources for discourse segmentation.
\newblock In {\em Proceedings of the 33rd Annual Meeting of the ACL}.

\bibitem[\protect\citename{Miike \bgroup et al.\egroup }1994]{miike_et_al_1994}
S.~Miike, E.~Itoh, K.~Ono, and K.~Sumita.
\newblock 1994.
\newblock A full text retrieval system.
\newblock In {\em Proceedings of SIGIR'94}, Dublin, Ireland.

\bibitem[\protect\citename{Morris and Hirst}1991]{morris_hirst_1991}
J.~Morris and G.~Hirst.
\newblock 1991.
\newblock Lexical cohesion computed by thesaural relations as an indicator of
  the structure of text.
\newblock {\em Computational Linguistics}, (17):21--48.

\bibitem[\protect\citename{Morris}1988]{morris_1988}
Jane Morris.
\newblock 1988.
\newblock Lexical cohesion, the thesaurus, and the structure of text.
\newblock Technical Report CSRI 219, Computer Systems Research Institute,
  University of Toronto.

\bibitem[\protect\citename{O'Neil and Denos}1992]{oneil_denos_1992}
M.~A. O'Neil and M.~I. Denos.
\newblock 1992.
\newblock Practical approach to the stereo-matching of urban imagery.
\newblock {\em Image and Vision Computing}, 10(2):89--98.

\bibitem[\protect\citename{Palmer and Hearst}1994]{palmer_hearst_1994}
David~D. Palmer and Marti~A. Hearst.
\newblock 1994.
\newblock Adaptive sentence boundary disambiguation.
\newblock In {\em Proceedings of the 4th Conference on Applied Natural Language
  Processing}, Stuttgart, Germany, October. ACL.

\bibitem[\protect\citename{Ponte and Croft}1997]{ponte_croft_1997}
Jay~M. Ponte and Bruce~W. Croft.
\newblock 1997.
\newblock Text segmentation by topic.
\newblock In {\em Proceedings of the first European Conference on research and
  advanced technology for digital libraries}.
\newblock U.Mass. Computer Science Technical Report TR97-18.

\bibitem[\protect\citename{Porter}1980]{porter_1980}
M.~Porter.
\newblock 1980.
\newblock An algorithm for suffix stripping.
\newblock {\em Program}, 14(3):130--137, July.

\bibitem[\protect\citename{Press \bgroup et al.\egroup }1992]{ks_test}
William~H. Press, Saul~A. Teukolsky, William~T. Vettering, and Brian~P.
  Flannery, 1992.
\newblock {\em Numerical recipes in C: The Art of Scientific Computing},
  chapter~14, pages 623--628.
\newblock Cambridge University Press, second edition.

\bibitem[\protect\citename{Reynar and
  Ratnaparkhi}1997]{reynar_ratnaparkhi_1997}
Jeffrey Reynar and Adwait Ratnaparkhi.
\newblock 1997.
\newblock A maximum entropy approach to identifying sentence boundaries.
\newblock In {\em Proceedings of the fifth conference on Applied NLP},
  Washington D.C.

\bibitem[\protect\citename{Reynar \bgroup et al.\egroup }1997]{reynar_1997b}
Jeffrey Reynar, Breck Baldwin, Christine Doran, Michael Niv, B.~Srinivas, and
  Mark Wasson.
\newblock 1997.
\newblock Eagle: An extensible architecture for general linguistic engineering.
\newblock In {\em Proceedings of RIAO '97}, Montreal, June.

\bibitem[\protect\citename{Reynar}1994]{reynar_1994}
Jeffrey~C. Reynar.
\newblock 1994.
\newblock An automatic method of finding topic boundaries.
\newblock In {\em Proceedings of ACL'94 (Student session)}.

\bibitem[\protect\citename{Reynar}1998]{reynar_1998}
Jeffrey~C. Reynar.
\newblock 1998.
\newblock {\em Topic segmentation: Algorithms and applications}.
\newblock {Ph.D.} thesis, Computer and Information Science, University of
  Pennsylvania.

\bibitem[\protect\citename{Reynar}1999]{reynar_1999}
Jeffrey~C. Reynar.
\newblock 1999.
\newblock Statistical models for topic segmentation.
\newblock In {\em Proceedings of the 37th Annual Meeting of the ACL}, pages
  357--364.
\newblock 20-26th June, Maryland, USA.

\bibitem[\protect\citename{van Rijsbergen}1979]{rijsbergen_1979}
C.~J. van Rijsbergen.
\newblock 1979.
\newblock {\em Information Retrieval}.
\newblock Buttersworth.

\bibitem[\protect\citename{Yaari}1997]{yaari_1997}
Yaakov Yaari.
\newblock 1997.
\newblock Segmentation of expository texts by hierarchical agglomerative
  clustering.
\newblock In {\em Proceedings of RANLP'97}.
\newblock Bulgaria.

\bibitem[\protect\citename{Youmans}1991]{youmans_1991}
Gilbert Youmans.
\newblock 1991.
\newblock A new tool for discourse analysis: The vocabulary-management profile.
\newblock {\em Language}, pages 763--789.

\end{thebibliography}
