Flexible information retrieval: some research trends

Mathware & Soft Computing 7 (2000), 1-15 1 Flexible information retrieval: some research trends Gabriella Pasi ITC-CNR, Via Ampère 56, 20131 Milano [email protected] Abstract In this paper some research trends in the field of Information Retrieval are presented. The focus is on the definition of flexible systems, i.e. systems that can represent and manage the vagueness and uncertainty which is characteristic of the process of information searching and retrieval. In this paper the application of soft computing techniques is considered, in particular fuzzy set theory. Keywords: information retrieval, flexible query language, personalized document indexing. . 1 Introduction The huge quantity of multimedia information on the World Wide Web raises the need for efficient and effective systems that support an easy access to the information items relevant to specific users’ needs. The activity aimed at locating on the WWW some relevant information is a very hard one: the users who access the network looking for something relevant to their needs can be seen as travellers opening a door on a wild forest, which has to be explored to the aim of reaching a (more or less) known destination. The users approaching the World Wide Web can access the big amount of available and mostly unknown information in different ways, which are also related to the purposes of their search. The most immediate approach is to directly navigate through the web sites by means of a chain of links found in the pages; in this way a formal expression of information needs is not necessary. However, when some specific information is searched, this point and click access paradigm is unpractical, and the effectiveness of the results strongly depends on the starting page. The increasing efforts aimed at defining effective systems that help users to access information relevant to their needs witness the importance of this research field. The most known systems belonging to this category are Information Retrieval Systems G. Pasi 2 (on the web, the search engines) [13,26,30]. When using an IRS the users have to explicitly specify their needs by a formal expression of a query language through a set of constraints that the relevant information items must satisfy. The aim of an IRS is to estimate the relevance of information items on the basis of a comparison of the formal representation of the items with the formal user’s query. The activity of these systems is based then on the solution of a decision-making problem: how to identify the information items that correspond to the users’ information preferences (i.e. relevant to their information needs)? What the users expect from an IRS is a list of the relevant information items ordered according to their preferences. The IRS acts then as an intermediary in this decision process: it “tries” to simulate the decision process that the user would personally undertake. To activate this automatic process the user has to formally communicate to the IRS her/his information needs, which are then analyzed by the system to the aim of selecting the information items satisfying them. The information items have to be formally represented to allow their automatic comparison with the formal user query. This representation problem is a very complex task pervaded by uncertainty and vagueness: the users’ expression of information needs is often uncertain and vague, the formal representation of the documents’ informative content introduces a loss of information and as a consequence is characterized by uncertainty about the real semantics of the documents’ information content. The effectiveness of an IRS is therefore crucially related to the system’s flexibility, intended as its capability to deal with the vagueness and uncertainty of the retrieval process, and to learn the user’s concept of relevance through an adaptive behaviour. Commercially available IRSs generally ignore these aspects; they oversimplify both the representation of the documents’ content and the user-system interaction. Some important research efforts are aimed at defining systems tolerant to imprecision and uncertainty in the elicitation of users’ preferences and able to learn them through an interactive and adaptive behaviour [1,4,6,10,11]. A big deal of research is being done in the area of intelligent information agents [23]. The aim of this paper is to synthetically present some approaches to the modeling of flexibility with respect to the previous mentioned aspects: the representation of information items and the definition of access method tolerant to vagueness and uncertainty in the specification of users’ information needs. In section 2 some approaches to model flexibility in IRSs are presented. In section 3 some applications of fuzzy set theory to model the vagueness and imprecision of the retrieval activity are synthesized. In section 4, a recent research approach to define personalized indexing mechanisms is analyzed. Finally, in section 5 some research approaches aimed at modelling flexible query languages are presented. Flexible information retrieval: some research trends 3 2 Modelling flexible Information Retrieval Systems Information Retrieval (IR) aims at defining systems able to provide a fast and effective content-based access to a large amount of stored information [24,26,30]. Information can be of any kind: textual, visual, or auditory, although most actual IR systems (IRS) store and enable the retrieval of only textual information organized in documents. A user accesses the IRS by formulating a query, which the IRS evaluates to the aim of retrieving all documents which it estimates relevant to the query. The problem of identifying the information relevant to specific needs is a decisionmaking problem: when someone analyzes a huge amount of information items he/she has to decide which ones are relevant to his/her needs. The information items constitute the alternatives on which an evaluation process has to be performed to the aim of identifying the relevant ones [31]. An Information Retrieval System plays the role of an automatic intermediary in this decision process: its main objective is to estimate the items relevant to a specific user request: this requires a formal representation of both information items and user queries. The main components of these systems are: a collection of information items, a query language which allows the expression of selection criteria synthesizing the users’ needs, and a matching mechanism which estimates the relevance of information items to queries (see Figure 1). The input of these systems is constituted by a user query; their output is usually an ordered list of selected items, which have been estimated relevant to the information needs expressed in the user query. Figure 1: scheme of a system for the storage and retrieval of information The ultimate aim of an IRS is then to estimate the relevance of documents to users' information needs. This is a very hard and complex task, since it is pervaded with imprecision and uncertainty. FORMAL REPRESENTATION OF INFORMATION ITEMS U SER QUERY ITEMS Estimated relevant Q UERY F ORMULATION M ECHANISM M ATCHING G. Pasi 4 Most of the existing IRSs offer a very simple modeling of IR, which privileges the efficiency at the expenses of the effectiveness. By formulating a query the user communicates to the system her/his preferences, on the basis of which an utility function can be defined and evaluated by the system (estimate of the alternatives’ utility) [12]. A crucial aspect affecting the effectiveness of the system is related to the characteristics of the query language, which should represent in the more accurate and faithful way the user’s information needs. The available query languages are based on keyword specifications, and do not allow to express uncertainty and vagueness in the specification of constraints that the relevant information items must satisfy [26,30]. Another important aspect which affects the effectiveness of IRSs is related to the way in which the information items are formally represented; the documents’ representations are extremely simple, based on keywords extraction and weighting; moreover the IRSs generally produce a unique representation of documents for all users, not taking into account the each user looks at a document content in a personalized way, by emphasizing some subparts with respect to others. This adaptive view of the document is not modelled. Another important aspect is related to the fact that on the WWW some standard for the representation of semi-structured information are becoming more and more employed (such as XML); for this reason it is important to exploit their structure in order to represent the information they contain. A promising direction to improve IRSs is to model the concept of partiality intrinsic in the IR process and to make the systems adaptive, i.e.able to “learn” the users' concept of relevance. In recent years big efforts have been devoted to the attempt to improve the performance of IR systems, and the research has explored many different directions to the aim of modelling the vagueness and uncertainty that invariably characterize the management of information [6,10,11]. A first research direction aims at defining methods of analysis of the natural language [28]. The main limitation of this approach is the level of deepness of the analysis of the language, and its consequent range of applicability: a satisfying interpretation of the documents’ meaning needs a too large number of decision rules even in narrow application domains. A second research direction is more general: its objective is to define retrieval models which deal with imprecision and uncertainty in the retrieval process. The most long standing set of approaches belonging to this class goes under the name of Probabilistic IR [9,30]. The aim of Probabilistic IR is to develop ad hoc models able to cope with the uncertainty of the retrieval process. However, there is another set of approaches receiving increasing interest that aim at applying techniques for dealing with vagueness and uncertainty. This set of approaches goes under the name of Soft Information Retrieval. The expression Soft Computing (SC) was introduced by Lotfi Zadeh as a synergy of methodologies useful to solve problems using some form of intelligence that divert from traditional computing. The principal constituents of SC are: fuzzy logic, neural networks, probabilistic reasoning, and evolutionary Flexible information retrieval: some research trends 5 computing, which in turn subsume belief networks, genetic algorithms, parts of learning theory, multivalued logics. As each of these methodologies allows to singularly representing imprecision, uncertainty and learning, it is frequently advantageous to employ these them in combination, rather than exclusively. SC differs from conventional (hard) computing in that, unlike hard computing, it is tolerant to imprecision, uncertainty, partial truth, and approximation. Because of these properties, SC can provide very powerful tools for IR. In [10] some techniques and applications of Soft Computing in Information Retrieval are presented. Genetic Algorithms have been mainly applied to IR for improving document representation and indexing, and for defining relevance feedback mechanisms [10,15]. Evidential and Probabilistic Reasoning in IR has been mainly applied for defining IR models. There have also been some applications of techniques like Rough Set Theory and Multivalued Logics [11]. Neural networks have been used in the context of IR to design and implement IRSs that are able to adapt to the characteristics of the IR environment, and in particular to the user’s interpretation of relevance [11,21]. In [11] some approaches concerning the application of connectionist approaches to the IR are analyzed. In particular, the two most important paradigms of learning used in the NN field are analyzed: the supervised learning and the unsupervised learning techniques. A supervised learning procedure is a process which incorporates an “external teacher”. This means that the teacher specifies the desired output of the NN. During the learning phase the NN adapts the values of the weights on the connections in order to obtain the desired output [27]. In unsupervised learning procedures the NN does not receive any teaching or learning feedback, but it is left to learn by itself. This procedure is also often referred to as “self-organization” because the process relies only upon local information and internal control to learn by capturing regularities in the stream of input patterns. For these reasons, unsupervised learning has been used in IR mainly for documents or terms clustering and classification. In IR, documents or terms can be clustered in related groups so that, once identified a relevant one, retrieval of associated documents or terms can be facilitated. In [11] some approaches in this class of applications are reviewed. Fuzzy set theory has been extensively applied to extend IR to model some aspects of the vagueness and subjectivity characterizing the retrieval process. In the next section the main applications of fuzzy set theory to IR are synthetically reviewed. 3 Fuzzy modelling of Information Retrieval To the aim of defining flexible IRS, fuzzy set theory has been successfully employed to the following aims: 1. to deal with the imprecision and subjectivity that characterize the indexing process; G. Pasi 6 2. to manage the user's vagueness in query formulation; 3. to deal with discriminated answers reflecting the partial relevance of the documents with respect to queries; 4. to soften the associative mechanisms, such as thesauri and documents’ clustering, which are often employed to extend the functionality of the basic IR scheme. A survey of fuzzy extensions of IRSs and of fuzzy generalizations of the Boolean IR model can be found in [6,14]. Fuzzy generalizations of the Boolean model have been defined to the aim of defining IRSs able to produce discriminated answers in response to users' queries. In fact, Boolean IRSs apply an exact matching between a Boolean query and the representation of each document, defined as a set of index terms. They partition the archive of items into two sets: the relevant documents and the irrelevant ones. As a consequence of this crisp behaviour, they are liable to reject relevant items as a result of too restrictive queries, and to retrieve useless material in reply to general queries [26]. To the aim of softening the Boolean IR model, fuzzy set theory has been applied at distinct levels. In documents’ indexing some fuzzy techniques have been applied to the aim of providing more specific and personalized representations of documents' information content than those generated by the existing indexing procedures. In section 4, the fuzzy interpretation of the weighted document representation is introduced, and a fuzzy indexing model of documents structured in logical sections (such as XML documents) is presented. This model can be tuned by users on the basis of their personal criteria for interpreting the content of documents [4]. Also an indexing procedure for HTML documents is shortly described [19]. Fuzzy set theory has also been employed for defining flexible query languages, able to capture the vagueness of user needs as well as to simplify the user system interaction. This aim has been pursued at two levels: through the definition of soft selection criteria (soft constraints), which allow the specification of the distinct importance of the search terms. Query languages based on numeric query term weights with different semantics have been first proposed as an aid to define more expressive selection criteria [7,14]. Then, an evolution of these approaches has been defined, which introduces linguistic query weights, specified by fuzzy sets such as important or very important, in order to express the distinct importance of the query terms [2]. Another level of flexibility concerns the definition of soft aggregation operators of the selection criteria, characterized by a parametric behaviour which can be set between the two extremes AND and OR adopted in the Boolean language. In [3] the Boolean query language has been generalized by defining aggregation operators as linguistic quantifiers such as at least k or most of. These extensions are presented in section 5. As it happens with search engines, the incorporation of a weighted document representation in a Boolean IRS is a sufficient condition to improve the system with Flexible information retrieval: some research trends 7 a document ranking ability. As a consequence of this extension the exact matching applied by a Boolean system can be softened to a partial matching mechanism, evaluating the degree of satisfaction of the user's query for each document retrieved. This value is called the Retrieval Status Value (RSV), and can be used for ranking documents. However, as it will be seen in section 4, more flexible indexing functions can remarkably improve the systems’ effectiveness. The main idea is to explicitly model an indexing strategy that adapts the formal document representation to the user personalized view of documents’ information contents. Fuzzy "knowledge based" models [14,16], and fuzzy associative mechanisms based on thesauri or clustering techniques [14,17,18] have been defined in order to cope with the incompleteness characterizing either the representation of documents or the users' queries. In [17] a wide range of methods for generating fuzzy associative mechanisms is illustred. Fuzzy thesauri and pseudothesauri can be used to expand the set of index terms of documents with new terms by taking into account their varying significance in representing the topics dealt with in the documents; the degree of significance of the associated terms depends on the strength of the associations with the documents' descriptors. An alternative use of fuzzy thesauri and pseudothesauri is to expand each of the search terms in the query with associated terms, by taking into account their distinct importance in representing the concepts of interest; the varying importance is dependent on the associations’ strength with the search terms. Fuzzy clustering can be used to expand the set of the documents retrieved by a query with associated documents; their degrees of association with respect to the documents originally retrieved influence their Retrieval Status Value. 4 Personalized indexing in IR The production of effective retrieval results depends on both subjective factors, such as the users' ability to express their information needs in a query, and the characteristics of the Information Retrieval System. A component of IRSs which plays a crucial role in determining their effectiveness is the indexing mechanism, which has the aim of generating a formal representation of the contents of the information items (documents’ surrogates). The most used automatic indexing procedures are based on term extraction and weighting: the documents are represented by means of a collection of index terms with associated weights (the index term weights); an index term weight expresses the degree of significance of the index term as a descriptor of the document information content [25,26,29]. The vector space model, the probabilistic models and fuzzy models adopt a weighted document representation [26,30]. The automatic computation of the index term weights is based on the occurrences count of a term in the document and in the whole archive [26,30]. In this case the indexing function computes for each G. Pasi 8 document d and each term t a numeric value, by means of a function F; an example of definition of the function F is the following, in which the index term weight is proportional to the frequency of term t in the document d, and inversely proportional to the frequency of the term in the documents of the archive: F(d,t) = tfdt × g(IDFt) (1) where: • tfdt is a normalized term frequency which can be defined as: tfd = OCCdt/MAXOCCd; OCCdt the number of occurrences of t in d, and MAXOCCd is the number of occurrences of the most frequent term in d; • IDFt is an inverse document frequency which can be defined as: IDFt = log(N/NDOCt), where N is the total number of documents in the archive and NDOCt is the number of documents indexed by t, g is a normalizing function. The computation of IDFt is particularly costly in the case of large collections which are updated online. The definition of such a function F is based on a quantitative analysis of the text which makes it possible to model the qualitative concept of significance of a term in describing the information carried by the text. The adoption of weighted indexes allows for an estimate of the relevance or of a probability of relevance of the documents to the considered query [26,30]. Based on such an indexing function and by maintaining the Boolean query language, the first fuzzy interpretation of an extended Boolean model has been to adopt a weighted document representation and to interpret it as a fuzzy set of terms [8]. From a mathematical point of view this is a quite natural extension: the concept of the significance of index terms in describing the information content of a document can then be naturally described by adopting the function F (such as the one defined in (1)) as the membership function of the fuzzy set representing a document. Formally, a document is represented as a fuzzy set of terms: Rd = Σt∈Tµd(t) / t in which the membership function is defined as µd: D × T → [0,1]. In this case µd(t) = F(d,t), i.e. the membership value is obtained by the indexing function F. Through this extension of the document representation, the evaluation of a Boolean query produces a numeric estimate of the relevance of each document to the query, expressed by a numeric score, called the Retrieval Status Value (RSV), which is interpreted as the degree of satisfaction of the constraints expressed in a query. The weighted representation of documents based on the F indexing function has the limitation of not taking into account that a term can play a different role within a text, according to the distribution of its occurrences. Let us think for example at scientific papers organised into the sections title, authors, abstract, introduction, references, etc. (this kind of structure can be explicitly defined by means of the XML language). An occurrence of a term in the title has a distinct informative role than an occurrence in the references. Moreover, indexing procedures based on the F function defined in (1) behave as a black box producing the same document Flexible information retrieval: some research trends 9 representation for all users; this enhances the system’s efficiency but implies a severe loss of effectiveness. In fact, when examining a document structured in logical sections the users have their personal views of the document’s information content; according to this view in the retrieval phase they would naturally privilege the search in some subparts of the documents’ structure, depending on their preferences. This last consideration outlines the fact that relevance judgments should be driven by a user’s interpretation of the document’s structure, and supports the idea of dynamic and adaptive indexing [1,4,5]. By adaptive indexing we intend personalized indexing procedures which take into account the users’ indications to interpret the document contents and to “build” their synthesis on the basis of this interpretation. It follows that if an archive of semi-structured documents is considered (e.g. XML documents), flexible indexing procedures should be defined by means of which the users are allowed to direct the indexing process by explicitly specifying some constraints on the document structure (preference elicitation on the structure of a document). This preference specification should be exploited by the matching mechanism to the aim of privileging the search within the most preferred sections of the document, according to the users’ indications. The user/system interaction can then generates a personalized document representation, which is distinct for distinct users [1,4,5]. In [5] a user adaptive indexing model has been proposed, based on a weighted representation of semi-structured documents that can be tuned by users according to their search interests to generate their personal document representation in the retrieval phase. The considered documents may contain multimedia information with different structures. A document is represented as an entity composed of sections (such as title, authors, introduction, references, in the case of a scientific paper). The model is constituted by a static component and by an adaptive query-evaluation component; the static component provides an a priori computation of an index term weight for each logical section of the document. The formal representation of a document is a fuzzy binary relation defined on the cartesian product T × S (where T is the set of index terms and S is the set of identifiers of the documents’ sections): with each pair <section, term>, a significance degree in [0,1] is computed, expressing the significance of the term in the document section. The adaptive component is activated by the user in the phase of query formulation and provides an aggregation strategy of the n index term weights (where n is the number of sections) into an overall index term weight. The aggregation function is defined on the basis of a two level interaction between the system and the user. At the first level the user expresses preferences on the document sections, outlining those that the system should more heavily take into account in evaluating the relevance of a document to a user query. This user preference on the document structure is exploited to enhance the computation of index term weights: the importance of index terms is strictly related to the importance for the user of the logical sections in which they appear. G. Pasi 16 [34] R.R. Yager, (1988) On Ordered Weighted Averaging Aggregation Operators in Multicriteria Decision Making, IEEE Trans. on Systems Man and Cybernetics, 18, 1, 183-190.