Detecting Subject Boundaries Within Text: A Language Independent Statistical Approach

Detecting Subject Boundaries Within Text: A Language Independent Statistical Approach Korin Richmond (kor:i.n©cogsc±. ed. ac. uk) Andrew Smith (aj s©cogsci, ed. ac. uk) (Joint Authorship) Centre for Cognitive Science 2 Buccleuch Place Edinburgh EH8 9LW SCOTLAND Einat Amitay (einat@cogsci. ed. ac. uk) Abstract We describe here an algorithm for detect- ing subject boundaries within text based on a statistical lexical similarity measure. Hearst has already tackled this problem with good results (Hearst, 1994). One of her main assumptions is that a change in subject is accompanied by a change in vo- cabulary. Using this assumption, but by introducing a new measure of word signif- icance, we have been able to build a ro- bust and reliable algorithm which exhibits improved accuracy without sacrificing lan- guage independency. 1 Introduction Automatic detection of subject divisions within a text is considered to be a very difficult task even for humans, let alone machines. But such subject di- visions are used in more complex tasks in text pro- cessing such as text summarisation. An automatic method for marking subject boundaries is highly de- sirable. Hearst (Hearst, 1994) addresses this prob- lem by applying a statistical method for detecting subjects within text. Hearst describes an algorithm for what she calls Text Tiling, which is a method for detecting subject boundaries within a text. The underlying assump- tion of this algorithm is that there is a high proba- bility that words which are related to a certain sub- ject will be repeated whenever that subject is men- tioned. Another basic assumption is that when a new subject emerges the choice of vocabulary will change, and will stay consistent within the subject boundaries until the next change in subject. These basic notions of vocabulary consistency within sub- ject boundaries lead to a method for dividing text based on calculating vocabulary similarity between two adjacent windows of text. Each potential subject boundary is identified and assigned a correspondence value based on the lexical similarity between two windows of text, one on ei- ther side of the subject boundary. The values for all potential boundaries are plotted on a graph, creating peaks and troughs. The troughs represent changes in vocabulary use and therefore, according to the underlying assumption, a change in subject. A divi- sion mark is inserted where a significant local min- imum is detected on the graph. Hearst measured approximately 80% success in detection of subject boundaries on some texts. We decided to adopt Hearst's underlying assump- tion that a change in subject will entail a change in vocabulary. Our aim was to make the algorithm as language independent and computationally expedi- ent as possible , while also improving accuracy and reliability. 47 I Preprocessing } STAGE I ¥ ICalculatc a significance 1 STAGE 2 value for each word J V ICalculate biased lexical] STAGE 3 correspondenfes J -v- I Smooth results 1 STAGE 4 ¥ I Insert breaks ] STAGE 5 Figure 1: Algorithm Structure. 2 Design The algorithm is divided into five distinct stages. Figure …

Content truncated to 500 words