The computer system described below gives assistance in finding synonyms in a way which represents a considerable improvement on the manual use of the thesaurus mentioned above. We then explore other ways of utilising the semantic classification available in a concept-based thesaurus.

4. Automatic synonym generation

We have implemented a synonym-generation program synonym based on our thesaurus [ref 12] The Roget Environment (Synonym Generation), G. M. Gwei, %R Internal report, Computer Science Group, Nottingham University (Dec. 1984) In this section we describe some design considerations and features of the implementation.

4.1. Searching mechanism

By definition, variants of the same stem have similar meanings. Consequently, it is sufficient to establish a similarity in the meanings of any two variants from two separate stems to establish synonymy between the stems concerned. For example, it would be na\*:ive to preclude the synonyms of angular from those of angle. Less obvious examples include leaving out the synonyms of encode while considering codify, or solar while dealing with sun.

The printed version of Roget's Thesaurus contains an index to facilitate searching. We obtained from publishers Longman the actual body of the thesaurus (a file of size approximately 3 Mbytes) without the index supplied in the printed version. The generation of a full inverted index was non-trivial, but the end result was a much more comprehensive index than that in the printed copy of the thesaurus.

The search phase involves heuristics for deriving acceptable words and phrases from any given input. The heuristics rules (see [ref 13] for details) include:

For example, given malfunctionithe heuristics for prefixes would automatically include nonfunctioning, not functioning etc as search terms. Similarly, prefixes such as be-, en-, a- etc which mainly introduce other parts of speech can simply be added to a given word to form others. The rules for deriving other parts of speech through suffix manipulation (see Appendix) are based on an associative model derived from Porter's [ref 14] An algorithm for suffix stripping, M. F. Porter, Program 14; 3; pp 130-137 (July 1980) algorithm on word conflation. After manipulating prefixes and suffixes of an input term, all resulting terms are sorted, and each term is then searched from the inverted index. Any derived term not found in the search is discarded. As an example, starting with the call synonym code, the prefix routine would suggest the list in Table 2.

Using the suffix rules, the system would search and display all acceptable suffix derivations from the terms in Table 2 that can be found in the inverted index. All phrases beginning with any of the acceptable terms would also be given in the display. Table 3 shows the display that would be obtained for the word code as parameter.

Each number corresponds to a paragraph of the thesaurus in which the term on the left appears; it will be observed that a given term may be found in several paragraphs, and that a given paragraph may appear against several terms.

Seven of the terms in Table 3 arise from the use of affixes (prefixes and suffixes), and two terms are common phrases beginning with the word code. A summary of the effect of acceptable affixes and phrases on the most ambiguous words in the thesaurus is shown in Table 4.

4.2. Additional information to help users

In manual usage of Roget, a user looks at headwords to decide which paragraph is most relevant. In our computer implementation, we wish to provide users with more help via the use of relevance and confidence measures. These measures depend on the number of occurrences, the degree of suffix/prefix manipulation used in deriving the term for each occurrence, and whether the occurrence is a phrase containing a derivation or the derivation by itself. To compare the relevance measures, we assign a value to each of the derived terms according to the procedure used in its derivation. The value assigned to each derivation depends on the error associated with the affix (prefix or prefix) used; these error values were obtained by experimenting on the separate affix categories [ref 15] The experiment yielded error values which approximate the probability that the use of a given affix would result in a word with a different morphological root. Given $"Error" sub aff$, the percentage error associated with a given affix category, the value given to a term found after using that affix would be The value assigned to a phrase containing any derivation is half the value associated with the derivation alone \(em we assumed a 50% chance that other words in the phrase may change the meaning of a given word.

To guide the user in choosing pertinent paragraphs we opted to summarise the values from the search as follows.

If Max is the highest individual score obtained in a search phase, and

The relevance value for a paragraph determines its ordering among all the paragraphs considered, while the confidence value for a paragraph is a measure of the certainty of its meaning (relative to the word given).

In addition to the factors above, we opted to also display the headwords of all the paragraphs considered. Each headword gives the user an instant idea of the concept covered by the corresponding paragraph. It also allows the user to mentally discard irrelevant paragraphs.

Continuing with the output of the command synonym code, the information in Table 5 is displayed to the user after the evaluation of the relevance and confidence values. Thus, paragraph 525 on Concealment, with a relative relevance of 100%, and a confidence of 100%, is considered to be the most relevant (for synonyms to code). The user might however see a more pertinent headword that better matches his/her original context. The choice is left open with this interactive method.

4.3. Contextual synonymy

As depicted in Figure 1 (section 3), many terms have more than one reference corresponding to distinct meanings and separate parts of speech. In requesting synonyms to a term, a user may not be interested in all potential meanings of the term (polysemy!). The headword information in Table 5 can enable a user to choose synonyms of the desired meaning (from the pertinent paragraphs). However, in this mode of operation the amount of information displayed can be bulky \(em especially when several derivations of the term exist or for words with high ambiguity factors (as shown in Table 4).

Bulky output can be avoided by specifying the context within which to locate synonyms. Before requesting synonyms to a polysemous term, a user may already know some simple and common characteristics associated with the meaning desired. Such characteristics can include the following.

These characteristics (which are all exploited in Roget's classification) can be used to discard less relevant concepts while searching for synonyms. For example, mathematics can be specified as a context parameter for synonyms to set using the command

synonym set -c mathematics

The number of paragraphs considered would now be reduced to 3 (on "NUMERATION","TRUTH", and "REASONING") as opposed to 233 potential paragraphs (Table 4) for set. In this mode, synonym searches for the input parameter as before (but hidden); assigns weights to found paragraphs as above; carries out a similar procedure for an exact antonym of the input (if one exists and can be derived); performs a similar procedure for the context delimiter and its exact antonym; and combines the weights arising from the separate terms using a set of coefficients. The coefficients approximate the relationships (revealed by Roget's classification) that exist between the given parameter and the context term. The relationships considered are approximated by values as indicated in Table 6.

The non-negative values approximate the degree by which the context parameter testifies a particular meaning of the given term, and the negative values approximate the degree by which the context parameter rejects a particular meaning. For example, the call

synonym code -c computer

would list only synonyms from paragraph 62 on "Arrangement: reduction to order". In the background however, 12 paragraphs would be considered for code (Table 3), 2 for decode, 8 for computers, and none for the antonyms to computers. Using the coefficients above to combine the separate weights would result in the rejection of all the other paragraphs except paragraph 62 (in which a meaning overlap between the terms occurs).

In summary, the heuristics for deriving antonyms operate as follows.

In any of the steps above, suffixes can also be manipulated. For example, useless would also be considered as a pure antonym to useful.

5. Disambiguating polysemous words within natural language context

In a typical utterance, just one of the potential meanings of a polysemous word is intended. Disambiguation is the process of determining that intended meaning.

Many of the approaches reported in the literature use other words that co-occur with the polysemous word in an utterance to disambiguate. Milne's [ref 16] Resolving Lexical Ambiguity in a Deterministic Parser, R. Milne, Computational Linguistics 12; 1; (1986) approach makes use of syntactic tokens and morphological analysis to assign the right part of speech to ambiguous words. Lesk [ref 17] M. E. Lesk, Automatic Sense Disambiguation Using Machine Readable Dictionaries: How to Tell a Pine Cone from an Ice Cream Cone, Proceedings of 1986 ACM SIGDOC conference %C Toronto Canada (June 1986) counts the overlaps in the dictionary definitions of the keywords in an utterance, and chooses the definition(s) with the highest overlaps as the intended meaning for the ambiguous word(s). Schank [ref 18] Identification of Conceptualizations Underlying Natural Language, R. Schank, Computer Models of Thought and Language %I W. H. Freeman and Co %C San Francisco (1973) conceptualises by using any characteristics of other words in a sentence that can discard some of the meanings associated with the ambiguous word in context. Jones [ref 19] Synonymy and Semantic Classification, K. Sparck Jones, %R Ph.D. Thesis, Cambridge University %C England (1964) argues that semantic affinity usually exists between the words used in any discourse, thus disambiguation can be achieved by adopting the meaning(s) that recur(s) among the words used in the discourse.

5.1. Adopted approach

Whilst reading, a human reader usually disambiguates word meanings by using the context within which the words appear. We can extend the synonym command to attempt word disambiguation in a similar manner. That is, by developing a method of choosing context parameters from an utterance, synonym can be made to search for the meaning (paragraph headword) of a given term demarcated by the context parameters (as in section 4.3).

The selection of context parameters from any utterance operates as follows.

Keyword clues

Human readers can be assisted in understanding any written utterance by external circumstances; but good writers do not rely on this extra-ordinary ability. Many utterances contain most of the information required in their interpretation, i.e. the words used in any inherently ambiguous words. However, some of words are more likely to be context delimiters than others. For example, in an utterance such as

time flies\u\d like an arrow

the word an is less likely to be a useful context clue in the disambiguation of the word flies. Thus, such words can be eliminated from the utterance while searching for context clues. After the elimination of unclassified words, each of the remaining words can potentially be used as the context parameter; or some of the keywords may be more significant than others; or a combination of some of the words may jointly prescribe the context parameter. In an utterance such as

the man with reading glasses loves wine

for example, reading is more significant in determining the intended meaning of glasses than any of the other words \(em omitting the word reading from the utterance can have a drastic effect on the disambiguation of the word glasses, even to human readers. From utterances of this type, it seems likely that where more than one potential context parameter prevails, those closer (in sequence) to the ambiguous word may be more significant. This significance is approximated in our model by

Direct clues

Many documents (especially technical documents) contain direct clues to help human readers disambiguate. Typical disambiguation clues in Roget's Thesaurus which we have used include the following.

Any of these clues can potentially shorten the disambiguation process \(em whenever a direct clue is found it takes precedence over all other clues that may be present. However, if no relationship can be established between the clue and any meaning associated with the ambiguous word, all other keywords would be taken as clues (as above).

The role of unclassified words

In some utterances, unclassified words can be the main source of semantic clues. Our approach utilises such clues in the following ways.

5.2. Performance \(em using the disambiguation model

The disambiguation program was tested on a sample of 400 sentences \(em each sentence contained at least one polysemous word. The sentences were chosen from examples cited in the literature on disambiguation and suggestions from colleagues. Table 7 shows some of the sentences alongside with the performance of the program on each sentence. The program diagnosed the intended meaning correctly in 304 sentences (76%); reported the absence of adequate clues in 76 (19%) sentences; and reported the wrong meaning in 25 sentences (5%). Of the meanings diagnosed incorrectly, 80% contained at least one other polysemous word. On average, it took 2 seconds to disambiguate a word in a sentence context.

Note: "*" indicates the word being disambiguated in each sentence.

To justify the existence of direct clues, we used the collection of all descriptive names for commands in the Unix operating system (in the file /usr/lib/whatis on Unix 4.2BSD). The results obtained are summarised in Table 8. In the light of the experiment, 69% of the occurrence of the special characters "/" ,"(" and ")", and the special conjunctions "or" and "and" can be justifiably used as disambiguation clues for polysemous words.

5.3. Comparison of the approach with others

The approach above relies on the co-occurrence of word derivations in a synonym group; in a concept paragraph; or in any of a set of reciprocally related paragraphs (all on similar abstract concepts) of Roget's Thesaurus. The approach compares with other disambiguation schemes in the following ways.

bottle, bowl, glass 194 (cup)
glassful, bumper
toss off one's glass, drain one's glass, knock it back
raise one's glass, pledge 876 (toast)
refill one's glass 633 (replenish)

the old man's glasses were filled with sherry

(which is also cited in Schank's paper) \(em sherry also occurs in paragraph 301.

synonym group
same paragraph
group of inter-related paragraphs
cross-referenced paragraphs
unrelated paragraphs
antonymous paragraphs

Our approach also weights the clues given by each word in an utterance (depending on the position of the word relative to the ambiguous word). Such consideration is absent from any of the approaches cited above.

6. Possible applications of the Roget tools

We use the word environment here to represent a computer system into which the Roget-based commands described above have been built.

6.1. Helping authors choose appropriate terms

The synonym generation process described in section 4 above can be used to simplify an author's task of finding the most relevant term to express a given concept. A suitable combination of flags would present an author with a small set of apposite alternatives; and it is even possible to accept incorrect English as in misfunction and suggests correct alternatives (such as dysfunction, functionless, malfunction, not function, no function, nonfunctional, nonfunctioning) by utilising the embedded heuristics. Thus the system can diagnose that a given user word is incorrect, can determine what the user probably intended, and can suggest terms which are more likely to correctly express that intention, without losing the root word from the user.

The disambiguation routines can also be used on an authoring package in the following ways.

• (i) warn that function has a high ambiguity factor (equal to 6);
• (ii) disambiguate "function" in the context of the specified sentence;
• (iii) suggest the following synonyms (with corresponding ambiguity factors).
  
  ceremony (3)
  function (6)
  occasion (7)
  do (13)

• On this basis, ceremony is suggested as a less ambiguous alternative for the word function in the sentence.

6.2. Towards computer understanding of word meanings

An obvious goal of all natural language systems is to represent word meanings on computers. This process can be an adjunct (or preprocessor) to any package which analyses users' terms. For human understanding, an ordinary dictionary would be used. Unfortunately, it will be very difficult to instruct a computer to consult and analyse meanings from dictionaries in the same way as humans. However, if the universe of discourse can be represented by a set of concepts in a similar way to Roget, and if the set is complete, then meanings can be represented in terms of these concepts.

6.3. Applications in conversational interfaces

Most computer systems that provide some form of conversation usually do so with a limited and predefined vocabulary. Such systems can be improved by building a synonym front end [ref 24] A Flexible Synonym Interface with application examples in CAL and Help Enviro, nments. G. M. Gwei, E. Foxley, The Computer Journal 30; pp 551-557 6; (1987) (also see Wilensky et al [ref 25] Talking to UNIX in English: An overview of UC, R. Wilensky, Y. Arens, D. Chin, Communications of the ACM 27; 6; pp 574-593 (1984) for an example). The front end can recognise synonyms from any user by consulting the synonym command to convert the terms in the user's query into terms which are known by the original package. In this way, the user can enjoy a great flexibility in vocabulary in addition to the facilities offered by the package.

This method can also be used in non-interactive environments. For example, a routine that performs script marking in a tutorial system by searching for keywords (see Gwei [ref 26] Towards Automatic Teaching, G. M. Gwei, %R MSc. Thesis, University of Aston in Birmingham (Sept. 1983) for example) can be modified to consult synonym first. Thus marking would involve searching users' responses for synonyms to keywords of a model answer (for further details see Gwei [ref 27] ).

7. Conclusions

The possibilities offered by the above developments are wide-ranging and offer many new facilities. The major drawback at the moment in the use of the system as an authoring tool in a technical or research environment is that the thesaurus on which this work has been based is too general purpose for technical use; there is a need for additional thesaurus paragraphs representing technical concepts related to the subject area involved. Many technical areas use words from ordinary English, but with very specific technical meanings; this usage needs to be reflected by a technical thesaurus. Roget was chosen simply because of its availability. Even with the context considerations above, terms used in a specific technical context have little chance of being treated correctly. It is easy to imagine one computer system in which erase and delete were identical operations, but another system in which the first merely erased the contents of the file, and the second actualit would be necessary to develop domain specific thesauri as replacements for, or as add-ons to, the generalised environment above.

A lesser drawback of the present system, which could be overcome by a more careful implementation, arises because the searching mechanism above performs prefix and suffix manipulation only on the first and the last word of a phrase respectively. This results in the omission of some potentially acceptable phrases. For example, starting with "pay off", any paragraph containing "pays off" or "paying off" should be given a reasonable measure. Such derivations or inflexions are not considered by the present searching mechanism.

The prefix and suffix manipulation routine does not handle all irregularities of inflexion in English grammar. For example, the system above cannot derive went from go, nor sought from seek. The inability to derive valid but peculiar variants of some words can lead to inaccurate ordering of the paragraphs under consideration. Thus a paragraph containing a word such as went but no other variant of the verb go would wrongly be omitted if go were the input word. Such problems can be tackled by developing more sophisticated heuristics which involve the sources and derivation routes of such words.

Software availability

The software developed as part of the above project relies heavily on our on-line copy of Roget's thesaurus. Longman are unwilling at the moment to allow it to be distributed to any other site. If readers know of a more freely available thesaurus, we would be happy to amend the software to use it, and then to distribute the system.

Acknowledgements

We wish to express our appreciation to: Longman for supplying us with an on-line version of Roget's Thesaurus; Dave Allsopp who contributed ideas to the options for the package; Andy Cheese and Mary Gwei, who both made useful comments on the original draft of this paper; and to various members of the Computer Science Department who contributed in one form or another.

Notes

APPENDIX : Deriving other parts of speech from a given root

The various inflexions (and some suffixal derivations) of a given word can be derived via considerations which include the following.

This outline can guide the search for a given word (and its variants) from a list of words in a lexicon/dictionary; the search should accept only those terms derivable via any of the schemes above. By storing a list of valid suffixes both requirements (1) and (2) can be achieved. All the considerations above can be facilitated by a procedure involving the details in Table 9 below.

In conjunction with the above, other forms of a word can be derived by using prefixes as follows:

References

1: Automatic Information Organisation and Retrieval, G. Salton, %I McGraw-Hill %C New York (1968)
2: Synonymy and Semantic Classification, K. Sparck Jones, %R Ph.D. Thesis, Cambridge University %C England (1964)
3: Agricola Terram Dimovit Aratro, M. Masterman, R. Needham, K. Sparck Jones, B. Mayoh, %R ML 92, Cambridge Language Unit %C Cambridge, England (1957)
4:
5: Ingredients of intelligent user interfaces, E. L. Rissland, International Journal of Man-Machine Studies 21; pp 377-388 (1984)
6: Talking to UNIX in English: An overview of UC, R. Wilensky, Y. Arens, D. Chin, Communications of the ACM 27; 6; pp 574-593 (1984)
7: A Flexible Synonym Interface with application examples in CAL and Help Enviro, nments. G. M. Gwei, E. Foxley, The Computer Journal 30; pp 551-557 6; (1987)
8: Towards Automatic Teaching, G. M. Gwei, %R MSc. Thesis, University of Aston in Birmingham (Sept. 1983)
12: The Roget Environment (Synonym Generation), G. M. Gwei, %R Internal report, Computer Science Group, Nottingham University (Dec. 1984)
13:
14: An algorithm for suffix stripping, M. F. Porter, Program 14; 3; pp 130-137 (July 1980)
15:
16: Resolving Lexical Ambiguity in a Deterministic Parser, R. Milne, Computational Linguistics 12; 1; (1986)
17: M. E. Lesk, Automatic Sense Disambiguation Using Machine Readable Dictionaries: How to Tell a Pine Cone from an Ice Cream Cone, Proceedings of 1986 ACM SIGDOC conference %C Toronto Canada (June 1986)
18: Identification of Conceptualizations Underlying Natural Language, R. Schank, Computer Models of Thought and Language %I W. H. Freeman and Co %C San Francisco (1973)
19: Synonymy and Semantic Classification, K. Sparck Jones, %R Ph.D. Thesis, Cambridge University %C England (1964)
20: Resolving Lexical Ambiguity in a Deterministic Parser, R. Milne, Computational Linguistics 12; 1; (1986)
21: M. E. Lesk, Automatic Sense Disambiguation Using Machine Readable Dictionaries: How to Tell a Pine Cone from an Ice Cream Cone, Proceedings of 1986 ACM SIGDOC conference %C Toronto Canada (June 1986)
22: Identification of Conceptualizations Underlying Natural Language, R. Schank, Computer Models of Thought and Language %I W. H. Freeman and Co %C San Francisco (1973)
23: Synonymy and Semantic Classification, K. Sparck Jones, %R Ph.D. Thesis, Cambridge University %C England (1964)
24: A Flexible Synonym Interface with application examples in CAL and Help Enviro, nments. G. M. Gwei, E. Foxley, The Computer Journal 30; pp 551-557 6; (1987)
25: Talking to UNIX in English: An overview of UC, R. Wilensky, Y. Arens, D. Chin, Communications of the ACM 27; 6; pp 574-593 (1984)
26: Towards Automatic Teaching, G. M. Gwei, %R MSc. Thesis, University of Aston in Birmingham (Sept. 1983)
27:

Notes converted from troff to HTML by an Eric Foxley shell script, email errors to me!