Discourse as a Knowledge Resource for Sentence Disambiguation

1 Introduction

In natural language processing, knowledge resources are indispensable for disambiguating input sentences, and a large quantity of such resources is necessary to improve the accuracy of sentence analysis. However, construct­ ing knowledge resources from hand-coded data requires enormous amounts of time and human resources, and thus leads to a knowledge acquisition bottleneck. Much research has been devoted to developing methods for re­ solving ambiguities by using large quantities of knowl­ edge resources that can be acquired semi-automatically from on-line texts [Brown et al., 1991; Gale et al., 1992; Hindle and Rooth, 1993; Jensen and Binot, 1987; Na­ gao, 1990; Utsuro et al., 1992; Uramoto, 1991]. Yet, in the day-to-day operation of a practical natural language processing system, such as a machine translation sys­ tem, it is inevitable that a new text will contain various ambiguities that cannot be resolved with the knowledge contained in the system. Moreover, a knowledge resource tends to be less effective for a text in a new domain.

On the other hand, a consistent text itself contains rich resources of information that can be used to re­ solve ambi~uities within its sentences. As shown by Gale et al. lGale et al., 1992] and Nasukawa [Nasukawa, 1993], polysemous words within the same discourse tend to have the same word sense with a probability of over 95%, and the accuracy of word sense disambiguation can be improved by applying discourse constraints in such a manner that each polysemous word in a discourse takes the same word sense. Kinoshita et al. [Kinoshita et al., 1993] and Nasukawa [Nasukawa, 1993] have reported that co-occurrence between words extracted from a text improves the accuracy with which attachment ambigui­ ties in the text are resolve9,. Furthermore, information extracted from discourse by means of a simple algorithm makes it easier to select the correct antecedent of a pro­ noun from among candidate noun phrases, as shown by Nasukawa [Nasukawa, 1994].

In this paper, we study the potential usefulness of in­ formation extracted from discourse, in contrast to infor­ mation stored in knowledge bases, and develop a method based on a simple algorithm that resolves ambiguities in sentences by using information extracted from discourse together with information stored in knowledge bases.

In the next section, we examine a couple of features of discourse information that allow more accurate sen­ tence analysis than is possible with information stored in knowledge bases. Then, in the third section, we pro­ pose a framework of natural language processing that extracts information from a discourse and disambiguates each sentence in the discourse by using the discourse in­ formation together with information stored in knowledge bases. Finally, in the fourth section, we give the results of experiments on the use of our framework to resolve structural ambiguities.

2 Information extracted from discourse

In this section, we examine two features in discourse that are applicable to sentence disambiguation, and compare the information extracted from discourse with the infor­ mation stored in knowledge bases, in terms of its effec­ tiveness for sentence disambiguation.

2.1 Discourse constraint and discourse preference

The first feature we discuss in this section is the "dis­ course constraint" that polysemous words within a dis­ course have the same word sense. According to Gale et al. [Gale et al., 1992] and Nasukawa [Nasukawa, 1993], there is a high probability (98% according to Gale et al.) that polysemous words within the same discourse actually carry the same word sense. If this discourse constraint is assumed to hold, a result of word sense dis­ ambiguation applied in one sentence can be shared with all the morphologically identical words within the dis­ course.

Since a valid word-sense disambiguation cannot always be made for every word appearing in a text, this proce­ dure of sharing the results of word-sense disambiguation improves the total accuracy of word-sense disambigua­ tion. For example, if a polysemous word appears alone in a title a heading, or a list item, there is no way to disambig~ate its word sense except by referring to infor­ mation in other sentences.

The second feature is "discourse preference," namely, a tendency for each word to modify or be modified by similar words within a discourse. During our analysis of computer manuals, we noticed that the same collocation patterns appeared frequently. For example, a collocation pattern in which the noun cursor occurred as t_he sub­ ject of the verb move appeared more than five times on one page of a computer manual. By assuming discourse preference, we obtain another clue on how to improve the accuracy of sentence analysis. For example, consider the following sentences extracted from a computer manual:

• (2.1) Type your user name on the user line.
• (2.2) You probably typed it on the line correctly, but ...

Sentence (2.2) actually comes immediately after the ~en­ tence (2.1) in the manual. In sentence (2:1), the mo~1fiee of the prepositional phrase on the user lzne can be e1ther Type or your user name, but in sentence (2.2) on the line uniquely modifies typed; therefore, by applying the discourse preference that the noun line tends to modify the verb type with the preposition on, we can resolve the structural ambiguity of sentence (2.1). Furthermore, the candidates for the antecedent of the pronoun it in sentence (2.2) are your user name and the user line in sentence (2.1), since both of them satisfy syntactic con­ straints. To select the actual antecedent, we can apply discourse preference, and thus your user name is pre­ ferred as an object of the verb type, since a collocation pattern in which your user name is the object of the verb type appears in sentence (2.1).

2.2 Comparison with information stored in knowledge bases

In this paper, we assume that

• A general natural language processing system holds one or more knowledge bases that contain informa­ tion for sentence disambiguation.
• ' Data are initially stored in the knowledge bases and updated through day-to-day operations.
• Multiple knowledge bases may be provided, to im­ prove the accuracy of disambiguation by supplying appropriate information for various domains.

With the aim of relieving the knowledge acquisition bottleneck, we consider an example-based approach to sentence disambiguation, in which disambiguation is based on information extracted from on-line texts. For example, a sentence analyzer called SENA [Uramoto, 1991] analyzes a sentence and extracts "word-to-word relationships" that basically consist of both a modi­ fier word and a modifiee word along with a marker of the relation between them (such as preposition, case marker, and so on), and prefers an attachment can­ didate that matches word-to-word relationships in its knowledge base (in this case, an example-base). Word­ to-word relationships can be extracted from on-line t exts semi-automatically with a little human interven­ tion to eliminate ambiguities in the data [Nagao, 1990; Uramoto, 1991]. Within the framework of the example­ based approach, it is easy to correct a specific disam­ biguation error by adding hand-coded word-to-word re­ lationships, and an additional set of hand-coded word­ to-word relationships may easily improve the accuracy with which sentences in a specific text can be disam­ biguated. However, a knowledge base that contains only word-to-word relationships has a disadvantage in its cov­ erage [Uramoto, 1994]. Since the vocabulary, as well as the usage of specific words, varies from text to text, de­ pending on the writer and the topic, improving the cov­ erage of word-to-word relationships in a practical domain is an important issue in the area of example-based sys­ tems. However, it may reduce the particularity of some word-to-word relationships such as those extracted from an idiomatic expression in which the modifier-modifiee relationship may not be general.

On the other hand, information extracted from a dis­ course contains some ideal features that can be applied to each sentence in the discourse. A sentence to be dis­ ambiguated and the discourse share the same writer and the same topic; thus, information extracted from a dis­ course is more reliable for disambiguating a sentence in­ side the discourse than information in a knowledge base. However, the discourse cannot be the only resource for sentence disambiguation because

• , Not all ambiguities can be covered by information extracted from the discourse.
• ' Information extracted from the discourse may itself contain ambiguities.
• Correct information may not always be extracted from the discourse, because of ellipses and analysis failures, and for various other reasons.

Examples of these reasons are provided in Section 4, along with the results of experiments on com~_>uter ~nan­ uals. To improve the accuracy of sentence disambigua­ tion, we propose to use information extracted from dis­ course together with information stored in knowledge bases. The next section describes the framework of our method.

3 Framework for using discourse information

In this paper, we focus on structural ambiguities rather than any of the other ambiguities in sentences, such as word sense ambiguities, since information extracted from discourse can resolve structural ambiguities with­ out being supplemented by other information, and the effects of discourse information can be evaluated sep­ arately from those of information stored in knowledge bases. Resolution of other ambiguities, such as selection of a word sense for a polysemous word, requires informa­ tion initially stored in knowledge bases, and discourse information is applied in such a manner that infornla­ tion extracted from knowledge bases is circulated within the discourse. In this section, therefore, we briefly de­ scribe a framework for using information extracted from discourse to disambiguate a sentence by focusing on its structural ambiguities.

3.1 Extraction of discourse information

The first step of our framework is to extract information from a discourse, while the second step is to resolve the ambiguities in each sentence of the discourse.

In the first step, each sentence in the whole text given as a discourse is processed by a syntactic parser, and the position of each instance of every lemma and its modifiee-modifier relationships with other content words in the parser output are stored as discourse infornla­ tion. In accumulation of discourse information, prefer­ ence scores are given for each definite modifiee-modifier relationship, such as the modification of type by on the line in sentence (2.2), and lower scores are given for each ambiguous modifiee-modifier relationship, such as the possible modification of Type by on the user line in sentence (2.1) .

Table 1 shows an example of such information ex­ tracted from the text of a computer manual consisting of sentences such as:

A server shares resources with other worksta­ tions on the LAN.

In this table, scores of 10 for each definite modifiee­ modifier relationship and 3 for each ambiguous modifiee­ modifier relationship are assigned. Thus the sentence above yielded preference scores of 10 for server modifying share as a subject, 3 for workstation possibly modifying share with the preposition with, and so on.

3.2 Structural disambiguation

To resolve structural ambiguities, the discourse informa­ tion is referred to for each modifiee candidate. If the same modifiee-modifier relationship, that is, the same collocation pattern, is found in the discourse informa­ tion, the score of the collocation is extracted and added to the candidate's preference value. In order to improve the coverage of the discourse information, an on-line syn­ onym dictionary [Collins, 1984) is consulted so that a collocation pattern can be checked with a synonym in one side of the collocation (either the modifiee or the modifier). The score, after being multiplied by a weight­ ing value, is then added to its preference value of the candidate. For example, to select the verb see as the modifiee of the prepositional phrase, for information, in the sentence See "Where to Look for Additional Task Infor­ mation" in "Up and Running" for information on which books to use, a collocation pattern in which for instruction modifies see extracted from a later sentence in the same discourse (11 sentences after the sentence above):

For instructions, see "Up and Running, "

is referred to, since instruction is defined as a synonym of information in the on-line synonym dictionary [Collins, 1984).

In addition to the dictionary information, coordinate structures in discourse information are referred to, and the coordinated words are also treated as synonyms in examining collocation patterns. For example, in the sen­ tence

In the MVS environment, the product runs un­ der TSO/E, GIGS, and IMS,

TSO/E, GIGS, and IMS are coordinated and thus treated as synonyms in the same discourse.

Information on word-to-word relationships stored in knowledge bases also provides preference scores, in addi­ tion to those given by the discourse information, and a score is added to the preference value of each candidate modifiee. After evaluation of the preference value for each candidate modifiee, the candidate with the highest preference is selected.

4 Results and discussion

After implementing our framework on an English­ to-Japanese machine translation system called Shalt2 [Takeda et al., 1992), we processed a large number of technical documents such as patents, technical letters, and, in particular, computer manuals. The results were encouraging, and we found some interesting phenomena that should be taken into account when information ex­ tracted from discourse is used along with information stored in knowledge bases.

4.1 Coverage

The coverage of information used for structural disam­ biguation is shown in Figure 1. The figure reflects the results of disambiguating all the sentences in a computer manual consisting of 791 consecutive sentences by chang­ ing the size of the discourse from 10 to 791 sentences. Ex­ cept for the result of referring to the whole 791 sentences as a discourse, all the results indicate the averages of the results obtained by referring to each of several sample areas as a discourse. For example, to obtain data for the case in which the size of a discourse is 20 sentences, we examined 32 areas each consisting of 20 sentences, such as the 1st sentence to the 20th, the 51st to the 70th, and the 701st to the 720th.

In this experiment, we disambiguated the modifiees of structurally ambiguous phrases such as prepositional phrases, present and past participle clauses, relative clauses, and to-infinitive clauses. In Figure 1, (A) indi­ cates the percentage of cases in which either the modifier word or one of the modifiee candidate words was found in the discourse information. In other words, at least one of the words related to a resolution of a structural ambiguity was repeated in the discourse in a percent­ age of cases . indicated by (A); this shows that many of the words were repeated within a relatively small area of the text. To be precise, more than 80% of the words were used more than once within 100 sentences. (B) shows the percentage of cases in which some preference values were given to any of the candidate modifiees on the basis of information extracted from the discourse. However, the assignment of preference values does not imply that a valid disambiguation has been carried out, since identical values may be assigned to different can­ didates. (C) indicates the percentage of cases in which discourse information allowed a preferable candidate to be discriminated. The percentage of cases in which the information stored in the knowledge base provided pref­ erence scores is shown by (D). Our knowledge base con­ tains more than 57,000 rules on word-to-word relation­ ships extracted from almost 10,000 sentences in various computer manuals and technical documents, and some broader coverage rules such as the one that prefers a prepositional phrase with to to modify a verb go. As shown in the figure, about 40% of structural ambiguities can be resolved with information extracted from the dis­ course, provided the discourse contains more than 200 consecutive sentences.

To determine whether an input text should consist of consecutive sentences, we combined 100 consecutive sentences from three different parts of the manual exam­ ined in the previous experiments on coverage - say the

1st sentence to the lOOth, the 301st to the 400th, and the 601st to the 700th - and resolved ambiguities in the resulting 300-sentence text by using our method. The results are shown in Table 2. A text whose sentences are not consecutive does not provide as much information as one of the same size whose sentences are consecutive. The table indicates that consecutive sentences form a co­ herent discourse and that our framework is much more effective for a text that has a single discourse.

4.2 Improvement of accuracy

We analyzed the results of disambiguating prepositional phrases in various texts. Such phrases account for about two-thirds (67.4% according to our analysis) of struc­ tural ambiguities.

In one experiment, 351 sentences from two chapters of a computer manual were disambiguated, with 70 to 100 sentences of a chapter being handled at a time. These sentences contained fifty-six ambiguous preposi­ tional phrases. The success rate 1 with a default rule that prefers innermost attachment turned out to be 53.6%. The success rate with information extracted from the discourse was 75.0% without the use of information on synonyms. The hit rate of the discourse informa­ tion, namely, the percentage of instances in which the discourse information on modifiee-modifier relationships contributed to the selection of the correct modifiee, was 35.6%, while in 82.1% of all cases, discourse informa­ tion was provided by words morphologically identical to those in the prepositional phrase. Through the use of an on-line synonym dictionary [Collins, 1984], the hit rate of the discourse information was raised to 42.9% and the success rate was improved to 82.1 %. In comparison, the success rate of the example-based approach for the same text was 67.9%, and the hit rate of the example-base in­ formation was 17.9%. Thus, the discourse information on modifiee-modifier relationships extracted from sen­ tences in the same discourse was actually effective for structural disambiguation.

In another experiment, we disambiguated all of the 218 sentences in a chapter of a computer manual, han­ dling 50 to 60 sentences at a time. The success rate obtained with the information extracted from the dis­ course, as well as synonym information and information stored in knowledge bases, was 82.6%. The hit rate for the discourse information alone was 38.4%, while the hit rate for the knowledge base information alone was 20.2%. However, information extracted from the discourse sup­ ported a wrong candidate modifiee in 19.4% of the cases in which effective information was provided, while infor­ mation stored in the knowledge base supported a wrong candidate modifiee in only 13.6% of such cases.

1 The percentage of instances in which the correct modifiee was selected.

Finally, we disambiguated the last 300 sentences of the computer manual that we used as a sample for analyzing the coverage of information in structural disambiguation as described in the previous subsection. By disambiguat­ ing 300 sentences in the discourse at a time, we increased the hit rate of the discourse information to slightly over 40%. The hit rate of the knowledge base information in this text was about 65%, since some data in the knowl­ edge base had been added or refined manually by looking at the first one hundred sentences in the same manual. In this case, the information in the knowledge base was much more reliable than the discourse information, and the primary success rate of 81.2% was raised to 90.6% by attaching more weight to preference scores given on the basis of information in the knowledge base.

4.3 Causes of failures

As is indicated by the results of the abovementioned ex­ periments on accuracy, correct information may not al­ ways be extracted from the discourse. Failures may re­ sult from ellipses in a source text, faulty analyses, and various other causes.

For example, the sentence

• (4.1) You can sign off your AS/400 session in one of the following ways:

is followed by itemized phrases such as

• ( 4.2) Using option 90 (Sign off) from the AS/400 Main Menu.

In ( 4.2), the modifiee of the prepositional phrase from the Main Menu is ambiguous. In disambiguating this phrase, information extracted from ( 4.4), which followed sentence ( 4.3), was applied.

• ( 4.3) Select one of the following options:
• (4.4) Option 90 (Sign off) from the AS/400 Main Menu.

In this case, the ellipsis contained in ( 4.4) caused our syntactic parser to recognize Option 90 as the modifiee of from the AS/400 Main Menu, and as a result our method incorrectly selected option 90 rather than Using as the modifiee of from the Main Menu in ( 4.2).

4.4 Complementary application of ambiguous information

In the course of our analysis of the results of disambigua­ tion, we observed many cases in which a combination of ambiguous information resolved ambiguities.

For example, the following three sentences were ex­ tracted from the same chapter of a computer manual:

• (4.5) The system displays message EKC0246A on the MTO console.
• ( 4.6) The messages are normally displayed on the MTO console,
• ( 4. 7) The messages are normally displayed by GIGS on the MTO console

In sentences (4.5) and (4.7), the modifiee of on the MTO console is ambiguous; however, a correct modifiee can­ didate, displayed, can be selected without relying on the information contained in sentence ( 4.6), since both sen­ tences ( 4.5) and ( 4. 7) provide preference scores for the candidate modifier-modifiee relationship of on the MTO console and displayed, so that the total score for dis­ played being modified by on the MTO console exceeds the preference score for message EKC0246A being mod­ ified by on the MTO console and the preference score for GIGS being modified by on the MTO console.

5 Conclusion

We have proposed a framework for using information ex­ tracted from discourse, together with information stored in knowledge bases, to improve the accuracy of sentence disambiguation.

Needless to say, the effectiveness of this method is highly dependent on the source text; nevertheless, the approach is effective in technical documents, such as computer manuals or patent documents, where words are used consistently in order to avoid ambiguity, and where identical collocation patterns are frequently repeated in detailed descriptions of target objects or procedures.

The results of implementing our method were encour­ aging. Discourse information covered about 40% of the structural ambiguities in computer manuals, when the discourse consisted of more than 200 consecutive sen­ tences, and it improved the accuracy of structural disam­ biguation. Moreover, use of information extracted from discourse was effective for processing a text in a new do­ main, whereas no support wa.S provided in this case by information stored in a system's knowledge bases. How­ ever, since the discourse information itself contains am­ biguities and errors, it may reduce the accuracy; thus, in­ formation stored in a knowledge base should be weighted according to how closely the knowledge base is related to the source text.

In this framework, discourse can be compared with short-term memory, whereas a knowledge base can be compared with long-term memory; as in humans, infor­ mation from both memories plays an important role in the interpretation of sentences. When a system contains enough information in its knowledge base to be able to interpret each sentence in an input text, it can rely on that information. However, for interpreting sentences in a text dealing with a new type of subject matter, infor­ mation extracted from the discourse is more reliable.

Acknowledgements

We would like to thank Michael McDonald for invaluable help in proofreading this paper.