Information Processing & Management Vol. 25, No. 3, pp. 265-273, 1989
`Printed in Great Britain.
`
`0306-4573/89 $3.00 + .00
`Copyright © 1989 Pergamon Press pic
`
`AUTOMATIC THESAURUS CONSTRUCTION BY
`MACHINE LEARNING FROM RETRIEVAL SESSIONS*
`
`U. GtnTzer,f G. JUTTNER,t G. SEEGMULLER,§ and F. SARREt
`y+Department of Computer Science, Technical University of Munich, Postfach 202420, D-8000
`Miinchen 2, FRG, {Institute for Application Oriented Knowledge Processing, Ulm, FRG,
`and §Gesellschaft fiir Mathematik und Datenverarbeitung, Bonn, FRG
`
`(Received 27 May 1988: accepted in final form 15 September 1988)
`
`Abstract — Users of information retrieval systems (IRS) know and use manyrelationships
`between concepts a long time before these find their way into textbooks, printed thesauri,
`or classification schemes. We present here an IRS componentcalled TEGEN, which taps
`this expertise by automatically drawing conclusions from actual search behavior about
`possible thesaurus entries. This is done during an iterative knowledge acquisition pro-
`cess: only after explicit or implicit confirmation by other users of the IRS during the
`knowledge verification process, the results are incorporated into a thesaurus. TEGEN
`is written in PASCAL using a knowledge-based programming method. It uses the rela-
`tional database system IMF2 andis implemented at the Technical University of Munich
`and at the Leibniz Computer Center of the Bavarian Academy of Sciences.
`
`1. INTRODUCTION
`
`Information retrieval systems (IRS) enable searches to be carried out on a collection of doc-
`uments. During this process, the user receives information relevant to the questions that
`are of interest to him or her.
`The information retrieval (IR) is more successful if various concept relationships can
`be incorporated into a search request by means of a thesaurus. Examples of such concept
`relationships are: synonyms, related terms, broader and narrower terms, and inflected
`forms.
`Since the conventional manual methods of thesaurus generation are too costly and the
`automatic methods have not producedsufficiently good results to succeed in practice {1-
`3], we present in this article a thesaurus-generating system designated TEGEN, which pro-
`vides a method by which a thesaurus can largely be learned by a computer without major
`effort or expenditure.
`TEGENis implemented on top of a multilingual IRS with automatic (and rather
`crude) indexing, which is used by professionals and graduate students. In such an environ-
`ment a thesaurusis particularly helpful, namely:
`
`1. The primitive kind of automatic indexing we use extracts all nonstop words from
`titles and abstracts of documents. This means that a paperonartificial intelligence
`might be indexed by the term “kiinstliche Intelligenz” if it happens to be written
`in German or by “AI”if only this abbreviation occurred in the title. Furthermore,
`a paper on trees might be indexed by “tree” or “trees” (or “arbres” etc.). Without
`the use of a thesaurus, recall will be rather low.
`2. The thesaurus componentis used interactively during query sessions. Thus, the user
`has immediate contro! when modifying the query with the help of the thesaurus.
`3, Furthermore, in our environment—as in many others— gainsin recall are much
`more at a premium than precision, because professionals are very good at screening
`out irrelevant material, but cannot afford to overlook relevant things; therefore,
`even if one would use the thesaurus only for enlarging queries (with a correspond-
`ing loss in precision) this would be beneficial.
`
`*A shorter version of this article was presented at the conference “User-oriented Content-based Text and
`Image Handling” (RIAO88), MIT, Boston, MA, March 1988.
`
`265
`
`1
`
`EX1024
`EX1024
`
`

`

`266
`
`U. GUNTzER ef al.
`
`To summarize: If the indexing methodis rather primitive, then a good thesaurus can
`makeupforits deficiencies and achieves considerably better search results. But normally,
`if an IRS had adequate resources to create and maintain a good thesaurus, presumablyit
`could also index moreintelligently in the first place. The TEGEN system is intended to be
`a remedy to this dilemma. The intelligence of the user population exhibited during query
`sessions is tapped to construct a thesaurusreflecting expertise, interests, and even jargon
`of this population. Of course, it remains to be proven that a really good thesaurus can be
`generated this way.
`
`2, THE BASIC PRINCIPLES OF THE LEARNING PROCESS
`
`2.1 Learning by analyzing
`The learning process used by the TEGENsystem is called learning by analyzing. This
`is a refined variant of learning by observation in which, however, an additional feedback
`componentis used to verify the learning results.
`This learning process is based on the assumption that a large numberof users of an
`IRS possess expert knowledge in the field to which their research relates. In carrying out
`their IR, they adopt certain procedures to find the desired documents contained in the col-
`lection of data.
`The user searches are evaluated online to acquire information regarding significant
`concepts and their interrelationships simultaneously with the process of providing infor-
`mation concerning the relevant documents. Thus, the knowledge providing and theknowl-
`edge acquisition processes work cooperatively.
`TEGENobserves the searches carried out by its users and exploits the users’ expert
`knowledge. Probable semantic relationships among concepts are extracted online by means
`of acquisition rules from the syntax of a search request and from the responses of the user
`to certain reactions of the search system.
`At the beginning of the learning process, the thesaurus is almost empty and can give
`only very limited support to an IRS; its quality, however, increases with the number of
`qualified users and instances of use.
`
`2.2 Feedback from the user
`User searches are evaluated online by TEGENsince feedback from the user is neces-
`sary for two reasons:
`
`1. ambiguity of conclusions
`2. uncertainty of results.
`
`If the analysis of user searches is ambiguousas regards the conclusions to be drawn,
`the concept relationship is assigned by the user with the aid of explicit feedback. This
`means direct feedback from the user. The system asks questions to clarify the situation and
`expects these questions to be answered unambiguously.
`Analysis of the search behavior of a user can lead to the acquisition of uncertain or
`wrong thesaurus contents. For this reason, the intermediate results of learning may be
`accepted as final only when their validity has been established by a sufficiently large num-
`ber of verification processes on the basis of implicit or explicit feedback.
`Implicit feedback is feedback from the user without direct questions. Thesaurus con-
`tents that require clarification are integrated in the search dialogue of the user at suitable
`points and the user’s reactions to them are used for verification purposes.
`
`2.3 Architecture of the learning system
`Conceptrelationships, which are recognized as a result of the analysis of a user search,
`are designated intermediate results (URES) and are initially assigned an appropriate status.
`These relationships have to be verified by further users so that their validity can be finally
`
`2
`
`

`

`Automatic thesaurus construction
`
`267
`
`established. A learning intermediate result becomes a final result (FRES) whenthe veri-
`fication process is complete.
`Thus, TEGENconsists essentially of two parts: knowledge acquisition and knowledge
`verification. The knowledge acquisition process derives possible thesaurus contents as inter-
`mediate results from the user searches. The knowledge verification process checks these
`intermediate results and converts them into final results. The architecture of the learning
`IRS is shownin Fig. 1.
`The management of the IRES and the recording of the FRES is carried out by the
`thesaurus. This contains the relations SYNONYMS, RELATED TERMS, HOMONYMS,
`BASIC and INFLECTED FORMS, BROADER TERMS and NARROWER TERMS,
`NEGATIVELIST and POSITIVE LIST, and USEFUL PREFIXES.
`A few remarks concerningthese relations shall clarify their semantics. The relation
`SYNONYMScontains not only synonym pairs in the linguistic sense but also translations
`and abbreviations, e.g. the pairs (artificial intelligence, AI) and (artificial inteiligence,
`kiinstliche Intelligenz) would qualify for inclusions into the relation SYNONYMS. For
`multilingual information systems, the semiautomatic construction of translation tables (for
`at least those terms that are in actual use) is a great advantage.
`Therelation POSITIVE LIST contains the controlled vocabulary, i.e. those terms that
`have been used several times as search terms within queries. At a later stage we intend to
`use this list for indexing. The unary relation NEGATIVELIST contains stop wordslike
`“is”, “of”, “the”, and “der”.
`The relation USEFUL PREFIXES needs a special comment. It is designed to help
`the user when using truncation, e.g. “Datenba.” shall denote all terms starting with
`“Datenba .
`. ” like “Datenbank”, “Datenbanken”, etc. If the user truncates too early, too
`many documentswill be derived; if the user truncates too late, recall will be lost. To find
`an adequate truncation point, the user goes through a term character-by-character from
`the left to the right and sends these prefixes one after the other as queries to the system.
`As an example, we display the results of this method for the term “Datenbanksystem”(this
`is the German word for “database system”).
`
`User
`
`Document
`
`Information
`Rotrieval
`
`jax 77
`\N\\
`WNWG
`TU
`HOCCU0UD
`
`Database
`
`Fig. 1. Architecture of TEGEN.
`
`3
`
`

`

`268
`
`U. GUNTZER et al,
`
` Useful?
`
`Prefixes
`
`No. of documents retrieved
`
`—
`~
`no
`yes
`no
`yes
`no
`no!
`no
`yes
`no
`
`D.
`Da.
`Dat.
`Date.
`Daten.
`Datenb.
`Datenba.
`Datenban.
`Datenbank.
`Datenbanks.
`Datenbanksy.
`
`52,578
`17,050
`16,429
`2,182
`1,941
`523
`469
`445
`445
`186
`162
`
`As one can see, “Datenban.” is not a useful prefix. If “Datenb.” is not good enough
`(this depends on the rest of the query), then it will not be helpful to replace it by “Daten-
`ban.” The user will go on and eventually use “Datenbanks.” instead. Actually, the user will
`set the truncation point at those points, where a significant drop in the hit rate takes place
`or where the semantics changes, like between “Daten.” and “Datenb.”
`
`3. KNOWLEDGE ACQUISITION
`
`Acquisition of the intermediate results takes place by means of acquisition rules, which
`are represented in the form of production rules such as those frequently used for knowl-
`edge representation in expert systems [4-6].
`The rules can be classified into three different types, which we present in the follow-
`ing sections. Examples of rules implemented in our system are given.
`TEGENcurrently contains 29 sets of semantic rules with a total of about 300 produc-
`tion rules that are implemented in PASCALtogether with the rule interpreter. Experience
`gained in using the system will result in further acquisition rules.
`
`3.1 Indirect acquisition without feedback
`User searches allow an unambiguous conclusion to be drawn as regards a thesaurus
`content and this can accordingly be directly acquired without any query being directed at
`the user.
`
`Insofar as rules of this class are used to investigate a similarity relationship, these can-
`not be specified more precisely as SYNONYMS, RELATED TERMS, or INFLECTED
`FORMS without feedback from the user. In this class of rules, therefore, similarity rela-
`tionships are generally assigned to the relation RELATED TERMSandarespecified more
`closely in a further stage of the process.
`EXAMPLE.
`Rule 14: Restriction by means of a new search request
`Syntax:
`if
`(a) two or more search terms x, in a search request X are combined by OR
`and
`
`(b) x; occur as key words
`and
`(c) the search request X is combined in a further search request Y by AND or
`AND NOTwith further search terms );
`
`then
`
`all x; are accepted in pairs as learning IRES in the RELATED TERMS
`relation.
`
`Semantics of Rule 14. If the user restricts the combination of search terms by the oper-
`ators AND or AND NOTwith further search terms in a further search request, the
`search terms of the first search request, which are used to form the union, in general
`
`4
`
`

`

`Automatic thesaurus construction
`
`269
`
`have a conceptual relationship. The fact that the OR combination receives further con-
`ceptual treatment by wayof restriction is a strong indication that the terms x; have
`not been combined accidentally.
`Condition (b) of Rule 14 implies that the search terms are complete and sensible
`concepts even if truncated.
`
`EXAMPLE.
`
`xX: (BAUM OR BAEUME OR TREE OR TREES)
`Y: X AND (SUCHE OR SEARCH)
`produces similarity relationships among:
`BAUM, BAEUME, TREE, TREES.
`
`3.2 Indirect acquisition with feedback
`In this rule class, the conclusions regarding thesaurus contents are ambiguous; thesit-
`uation is clarified by explicit feedback. Similarity relationships can be unambiguously
`assigned to the different thesaurus relations on the basis of queries addressed to the user.
`EXAMPLE.
`Rule 25: New attempt in the case of AND combinations
`Syntax:
`if
`(a) a search request X consists of n search terms x; with n = 2
`and
`(b) the x; are combined by AND
`and
`({c) the search request X is repeated in search request Y but one of the search
`terms involved, x;, is replaced by the search term y
`and
`
`(d) the search request Y producesless results than X
`and
`
`(e) the user gets the results of Y printed
`and
`
`(f) .. . some further premise...
`
`then (1) ask the user, whether:
`(A) y is a narrower term of x;
`(B) y is a synonym ora translation of x;
`(C) x; is an inflected form of y
`(D) y is an inflected form of x;
`(E) an affinity relationship exists between x; and y
`(F) noneof this applies
`(2) in case (A)-(E), the pair (y,x;) is accepted
`as IRES in the appropriate thesaurusrelation.
`
`Semantics of Rule 25. If, after an unsuccessful search attempt in which two or more
`search terms were combined by AND, a fresh attempt is made and one of the search
`terms x; involved is replaced by a search term y, a conceptualrelationship generally
`exists between x, and y. If replacing x; by y producesless results and the useris satis-
`fied with the modification, because the results were printed, then it is rather likely that
`one has foundin y a term narrower than x, or related to x;. This relationship is clas-
`sified more precisely by queries addressed to the user.
`The precondition = 2 is necessary so that it can be seen that question Y is an
`emendation of question X.
`EXAMPLE.
`X: STORAGE METHOD AND INFORMATION RETRIEVAL
`Y: INVERTED LIST AND INFORMATION RETRIEVAL
`results, after query to user, in:
`INVERTEDLISTis a narrower term of STORAGE METHOD.
`
`5
`
`

`

`270
`
`U. GonTzeEret al.
`
`Of course, answering the question posed by the system requires some effort by the
`user. On the other hand, the question gives some hints about other possibilities to emend
`the query. Maybethe user has replaced x; by an inflected form and is reminded —when
`reading alternative (B)—that x; should also have been replaced by a synonym. In spite of
`the fact that the numberof hits appeared satisfactory to the searcher, there could be many
`other ways to improve the query. In this way, attention is drawn to the fact that thesau-
`rus supportis available, i.e. instead of being bothered the user might even be grateful for
`the interference by the system. In any case, the user can switch off the thesaurus compo-
`nent, e.g. if not ready to answerthe questions. But even if the user has no immediate ad-
`vantage for the actual query by answering the questions of TEGEN, every improvement
`of the thesauruswill be to the benefit of later searchers, i.e. the colleagues of the present
`user,
`
`Ourfirst experiences show that users are cooperative, but this acceptance question has
`to be evaluated carefully along the following lines:
`
`i. Anonymoussession history protocols are recorded and shall be evaluated manu-
`ally. There it can be seen how often users have asked the system for thesaurus help
`and, if users have left the thesaurus mode during a retrieval session (presumably
`feeling bothered), how many questions had been asked (and answered) and what
`wasthe last question.
`Because weanticipate that TEGEN would usually be used within an organiza-
`tion, the organization could makethis kind of cooperation by its members obliga-
`tory. We are thinking of trying this method for a limited period of time. Of course,
`users could react by no longer using the system atall or by answering at random.
`(Even then the verification procedure would prevent incorporation of random re-
`sults into the thesaurus.) This appears to be rather unlikely, but has to be verified
`empirically.
`2. Additionally, a questionnaire is designed to find out what the users think of the
`thesaurus and how taxing they feel the additional effort is. It is very well possible
`that some types of questions are more bothering than others. Then one might do
`without these special questions, especially if the corresponding rule was not very
`productive. This can be measured, because we record for every intermediate and
`every final learning result the rule numberresponsible for acquiring (or verifying)
`this bit of knowledge.
`
`3.3 Direct acquisition
`As a further possible method of generating learning intermediate results, the user is
`asked explicitly about thesaurus contents known to him orherif this can be done within
`the search dialogue at a point that is appropriate from a semantic point of view and with-
`out delaying the user.
`For this reason, this form of acquisition is used only if the user has previously indi-
`cated that he or she wishes thesaurus support (thesaurus mode).
`
`EXAMPLE.
`
`Rule 29: Direct acquisition of thesaurus contents
`Syntax:
`if (a) the thesaurus modeis set
`and
`(b) the user requires concepts that have relationship type ¢ with a search term x
`then (1) provide with x all previously verified concepts of this relationship type ¢
`(2) carry out verification of not yet finally established intermediate results
`of x in respect of this relationship type ¢
`(3) ask the user for further concepts y; that have a relationship of type ¢
`with x
`(4) for all y; shown, accept the pair (x, y;) as intermediate results into the
`thesaurus relation of this relationship type.
`
`6
`
`

`

`Automatic thesaurus construction
`
`271
`
`Semantics of Rule 29. By means of this acquisition rule, thesaurus contents are
`obtained directly from the user by means of questions and are entered into the thesau-
`rus as IRES.
`Actions (1) and (2) are important for the verification process and also motivate
`the user to add to the thesaurus content.
`
`Here the acceptance problem is muchless critical than in the last section. The useris
`asked for further concepts y; that have a relationship of type t with x. The user has to
`enter these terms anywayandis neither delayed nor bothered, because he or she presum-
`ably wants to include them into the actual query.
`
`4. KNOWLEDGE VERIFICATION
`
`4.1 Verification of the intermediate results
`In this second phase of the learning process, the knowledge and the behavior of the
`searchers are once again used to confirm or reject intermediate results and thus to assign
`them a validity status.
`For this purpose, learning attributes are allocated to the intermediate results within
`the thesaurus database; these learning attributes are initialized during the knowledge acqui-
`sition process and updated in the course of verification. These learning attributes include:
`
`Learning weight — indicates the degree of validity of a concept relationship as
`ascertained so far.
`
`Learning status—indicates the current state of the concept relationship within the
`learning process.
`Verification confirmation — indicates the numberof confirmations of an intermedi-
`ate result that have occurred so far.
`
`Verification rejection—records the numberof rejections of an intermediate result.
`
`Finally, the date of entry shows the calendar date on which an IRES was acquired.
`Since, in addition, the numberof the relevant acquisition rule is recorded for each
`intermediate result, TEGEN even possesses a mefalearning capability. Once TEGEN has
`been in use for any adequate period of time, it can be learned by checking this rule num-
`ber record, which acquisition rules have produced particularly good results.
`Abuse of TEGENis prevented by ensuring that no user is ever involved in the veri-
`fication of an intermediate result that was acquired by him/herself.
`
`4.2 Variables for controlling the learning process
`There are some further quantities that express relationships among the learningattri-
`butes and are used for controlling the learning process. The verification frequency h is de-
`termined by the sum of the verification confirmations and verification rejections. The
`learning step g determines the amount by which the learning weight is increased, or
`reduced, depending on user reactions. The acceptance value a is defined as the difference
`between the numberof verification confirmations and the numberof verification rejec-
`tions; it indicates whether an IRESis being accepted or rejected by a majority of users.
`Finally, the verification barrier s indicates how high the acceptance value must be for an
`IRESto befinally accepted.
`
`4.3 Generation of the final results
`In the course of the learning process, attempts are made to transform IRES, as far
`as possible automatically, into FRES so that they are available in the thesaurus.
`An intermediate result is converted into an established final result when the verifica-
`tion process has been carried out sufficiently often and thus the verification barrier s has
`been exceeded.
`A preliminary final result is obtained when the period of investigation corresponding
`to learning period / has elapsed and either the IRES hasnot been verified sufficiently often
`TPM 25:3-D
`
`7
`
`

`

`272
`
`U. GUNTZERefal.
`
`or the users have contrary views as to the validity of a concept relationship. Since in these
`cases an automatic decision is not possible, manual checking by an external expert is
`necessary.
`
`4.4 Learning targets and learning parameters
`In systems using TEGEN, various learning targets—such as a high learning rate, a
`large numberand high quality of automatically generated FRES, and a small numberof
`external manual checking processes ~ are laid down; to achieve these targets, several learn-
`ing parameters can beset.
`These learning parameters, which can be influenced from outside to a greater or lesser
`extent, include the number of users, their degree of expertise, the verification barrier s, and
`the /earning period |. The degree of expertise is determined by the homogeneity of the user
`group and also bytheir level of knowledge both in the specialized field (domain expertise)
`and relating to the search system (retrieval expertise).
`Since these learning parameters in part have opposite effects, it is necessary to carry
`out an experimentally based adaptation. For example, an increase in s will result in an
`increase in the quality of the automatically generated FRESsince a larger numberof users
`have to participate in the verification of an IRES so that their decision becomes morereli-
`able. However, the learning rate is simultaneously reduced and the number of manual
`checking processes is increased for the same learning period /.
`Atpresent, the value s is set to 5 in our system and the value / to 90 days. This means,
`for example, that a presumed thesaurusrelationship must have been confirmedfive times
`more often than it has been rejected beforeit is finally incorporated into the thesaurus as
`a final result. However, a preliminary decision is taken in any case after 90 days at the
`most.
`
`5, OUTLOOK
`
`TEGENis implemented in PASCAL on a CYBER 990 computer, applying knowl-
`edge-based programming methodson the basis of a conventional programminglanguage.
`By using these programming methods, it has been possible to show that their advantages
`(i.e. exploratory programming, easy maintenance) are also beneficial if a conventional pro-
`gramming language is used. Additionally, this solves the problems involved in connecting
`knowledge-based systems to conventional databases and other software systems.
`At present, TEGEN is being used within the documentretrieval system TUBIBMUE.
`Online searches on 130,000 documents of the Faculty of Mathematics and Computer Sci-
`ence of the Technical University of Munich are possible [7]. A thesaurus is being gener-
`ated in accordance with the methods described in this article and the final results are
`offered to the users to support their searches.
`It appears likely that term relationships that have been established by several expert
`users are in fact meaningful, but this has to be proved by a careful validation, e.g. it has
`to be validated, whether the methods implemented in fact create good thesaurusrelation-
`ships, especially whether the verification procedures exclude most invalid intermediate
`results from incorporation into the thesaurus without being too restrictive.
`This validation is planned as follows: as already mentioned in Section 3.2, TEGEN
`records for every intermediate and every final result the numberof the rule responsible for
`this result; even the complete verification and rejection history for every learning result is
`recorded. In this way, the quantitative productivity of the different rules can be easily mea-
`sured. Furthermore, it can automatically test whether the results produced by somerule
`were controversial during the verification process. Thus, the quality of a rule can beatleast
`partially measured.
`Finally, a manual evaluation of a representative part of the thesaurus by a commit-
`tee is indispensable. However, we are rather optimistic that this committee will draw the
`same conclusions as the researchers during the feedback phase of the verification process.
`The quantity and quality of the results generated depend on the tuning parameters
`
`8
`
`

`

`Automatic thesaurus construction
`
`273
`
`explained in Section 4.4 Appropriate values for these parameters can only be fixed
`empirically.
`The TEGENlearning system can be integrated into an IRS with a Boolean search
`interface at any time. Especially, it is possible (and advisable) to use an existing thesau-
`rus to “prime” the system. It should also be mentioned that this type of computer learn-
`ing will surely not remain limited to document retrieval systems.
`
`REFERENCES
`
`hodRe
`
`nar
`
`. Salton, G. Dynamic information and library processing. Englewood Cliffs, NJ: Prentice-Hall; 1975.
`. van Rijsbergen, C.J. Information retrieval, 2nd ed. London: Butterworths; 1978.
`. Foskett, D.J. Thesaurus. In: Dym, E.D., editor. Subject and information analysis. New York: Marcel Dek-
`ker; 1985: 270-317.
`. Davis, R.; King, J. An overview of production systems. In: Elcock, E.W.; Michie, D., editors. Machineintel-
`ligence, vol. 8. New York: John Wiley and Sons; 1977: 300-332.
`. McCalla, G.; CerCone, N. Approaches to knowledge representation. Computer, 16(10): 12-18; 1983.
`. Buchanan, B.G.; Shortliffe, E.H. Rule-based expert systems: The MYCIN experiment of the Stanford Heuristic
`Programming Project. Reading, MA: Addison Wesley; 1984.
`. Jiittner, G.; Landherr, G. Die bibliotheksverwaltungssysteme LRZBIBLIO und TUBIBMUE. LRZ-Bericht
`Nr. 8505, Miinchen; 1985.
`. Giintzer, U.; Jiittner, G.; Seegmiiller, G. TEGEN — Ein lernfahiges information retrieval system. In: Czap,
`H.; Galinsky, C., editors. Terminology and knowledge engineering. Proceedings ofthe first international con-
`gress on terminology and knowledge engineering; 1987; 323-337; Trier.
`
`9
`
`