Artificial Intelligence Review 11: 453-482, 1997 453 c1997 Klnver Academic Publishers. Printed in the Netherlands. Application of Spreading Activation Techniques in Information Retrieval F CRESTANI Dipartimento di elettronica e Informatica, Universita di Padova, I-35131 Padova, Italy, email: fabio@dei umid. it Abstract. This paper surveys the use of Spreading Activation techniques on Semantic Networks in Associative Information Retrieval. The major Spreading Activation models are presented and their applications to Ir is surveyed. A number of works in this area are critically analyzed in order to study the relevance of Spreading Activation for associative IR. Key words: spreading activation, information storage and retrieval, semantic networks, This paper reviews the applications of Spreading Activation(SA)techniques on Semantic Networks in a very active research area: Information Retrieval (IR). The general motivation of this paper springs from past work in associ ative retrieval. The idea behind this form of information retrieval is that it is possible to retrieve relevant information by retrieving information that is " associated"with some information the user already retrieved and that know it to be relevant. The associations between information can either be static and already existing at the time of the query session or dynamic and determined at run time. In the first case. associations among information items (document or parts of documents, extracted terms, index terms, concepts, etc. created before the query session, and they make use of semantic relation- ships between these items, such as for example thesaurus-like relationships among index terms, bibliographic citations among documents, or statistical similarity among documents or terms. In the last case, instead, the system determines associations between information items through interaction with the user, for example by retrieving documents that are similar to documents the user points out to be relevant(this particular technique is called"relevance feedback", as it it will explained in Section 2). Both these techniques have been explored for quite sometime by the ir community and there are various examples of working systems using them. In this paper we will concentrate
Artificial Intelligence Review 11: 453–482, 1997. 453 c 1997 Kluwer Academic Publishers. Printed in the Netherlands. Application of Spreading Activation Techniques in Information Retrieval F. CRESTANI Dipartimento di Elettronica e Informatica, Universita di Padova, I-35131 Padova, Italy, ´ email: fabio@dei.unipd.it Abstract. This paper surveys the use of Spreading Activation techniques on Semantic Networks in Associative Information Retrieval. The major Spreading Activation models are presented and their applications to IR is surveyed. A number of works in this area are critically analyzed in order to study the relevance of Spreading Activation for associative IR. Key words: spreading activation, information storage and retrieval, semantic networks, associative information retrieval, information processing, knowledge representation. 1. Introduction This paper reviews the applications of Spreading Activation (SA) techniques on Semantic Networks in a very active research area: Information Retrieval (IR). The general motivation of this paper springs from past work in associative retrieval. The idea behind this form of information retrieval is that it is possible to retrieve relevant information by retrieving information that is “associated” with some information the user already retrieved and that is know it to be relevant. The associations between information can either be static and already existing at the time of the query session or dynamic and determined at run time. In the first case, associations among information items (document or parts of documents, extracted terms, index terms, concepts, etc.) are created before the query session, and they make use of semantic relationships between these items, such as for example thesaurus-like relationships among index terms, bibliographic citations among documents, or statistical similarity among documents or terms. In the last case, instead, the system determines associations between information items through interaction with the user, for example by retrieving documents that are similar to documents the user points out to be relevant (this particular technique is called “relevance feedback”, as it it will explained in Section 2). Both these techniques have been explored for quite sometime by the IR community and there are various examples of working systems using them. In this paper we will concentrate
E CRESTANI on the first technique, which is the one most commonly called Associative Re In associative Retrieval associations among information items are often represented as a network, where information items are represented by nodes and associations by links connecting nodes. The heuristic rule consisting in retrieving information associated to information already assessed as relevant is often implemented by means of a technique called Spreading Activation The purpose of this paper is to describe the different types of Spreading Activation used in the context of associative IR, and to report on past expe rience in developing and evaluating IR systems based on such technique At present there is a decrease of interest in this area of research. This is mainly due to the fact that it is very time consuming to set up a network of associations among information items when the size of the document collection is very large. There is a current tendency in IR to experiment with larger and larger document collections. Many papers at the last ACM SIGIR Conferences(e.g(Voorhees, 1994; Fujii and Croft, 1993))and the TREC initiative(Harman, 1993)are evident examples of this trend. Most of the original work in associative IR was performed with small document collec tions, and often the associations among the information items were set up manually or semi-automatically. This, of course, becomes impossible when the document collection is very large. However, nowadays more and more computing power is becoming available and its cost is rapidly decreasing making it possible to set up automatically associative networks for large document collections. We believe that this research area could return to be very active and that there is a lot to be learned from past experience. This survey paper tries to report about this past experience in a complete and critical way. Another more personal motivation for the paper is related to the authors most recent research which brought him to develop a conceptual model for Associative IR(Crestani and van Rijsbergen, 1993). The model is based on a three levels network structure, and it is general enough to enable the model- ling of any IR application. The model also enables the representation and use of application domain knowledge which could be used for the adaptation of the original user's query to the specific req nts of the application domain. The conceptual model can be implemented using various forms of network processing and three associative processing paradigms were consid ered Spreading Activation on a Semantic Network, Neural Networks, and Inference Networks. With the intention of surveying and studying what has already been done in IR using these processing paradigms, this paper focus on Spreading Activation, reviewing this processing paradigm and surveying its applications to associative IR. This is part of the authors research activity
454 F. CRESTANI on the first technique, which is the one most commonly called Associative Retrieval. In Associative Retrieval associations among information items are often represented as a network, where information items are represented by nodes and associations by links connecting nodes. The heuristic rule consisting in retrieving information associated to information already assessed as relevant is often implemented by means of a technique called Spreading Activation. The purpose of this paper is to describe the different types of Spreading Activation used in the context of associative IR, and to report on past experience in developing and evaluating IR systems based on such technique. At present there is a decrease of interest in this area of research. This is mainly due to the fact that it is very time consuming to set up a network of associations among information items when the size of the document collection is very large. There is a current tendency in IR to experiment with larger and larger document collections. Many papers at the last ACM SIGIR Conferences (e.g. (Voorhees, 1994; Fujii and Croft, 1993)) and the TREC initiative (Harman, 1993) are evident examples of this trend. Most of the original work in associative IR was performed with small document collections, and often the associations among the information items were set up manually or semi-automatically. This, of course, becomes impossible when the document collection is very large. However, nowadays more and more computing power is becoming available and its cost is rapidly decreasing, making it possible to set up automatically associative networks for large document collections. We believe that this research area could return to be very active and that there is a lot to be learned from past experience. This survey paper tries to report about this past experience in a complete and critical way. Another more personal motivation for the paper is related to the author’s most recent research which brought him to develop a conceptual model for Associative IR (Crestani and van Rijsbergen, 1993). The model is based on a three levels network structure, and it is general enough to enable the modelling of any IR application. The model also enables the representation and use of application domain knowledge which could be used for the adaptation of the original user’s query to the specific requirements of the application domain. The conceptual model can be implemented using various forms of network processing and three associative processing paradigms were considered: Spreading Activation on a Semantic Network, Neural Networks, and Inference Networks. With the intention of surveying and studying what has already been done in IR using these processing paradigms, this paper focus on Spreading Activation, reviewing this processing paradigm and surveying its applications to associative IR. This is part of the author’s research activity
APPLICATION OF SPREADING ACTIVATION TECHNIQUES IN IR 455 ongoing at the Computing Science Department of the University of Glasgow The main aim of the research is to develop a prototype of a interactive Ir system based on a network representation structure, which makes use of application domain knowledge acquired by interactions with users. The SA processing framework and some of its applications to IR are analysed in this paper with this purpose in mind The paper is structured as follows: Section 2 briefly explain the IR problem and what has been done so far to solve it, Section 3 explain what a Semantic Network is, and Section 4 describes the Spreading Activation technique and its variants, which is the most commonly used processing paradigm of Semantic Networks. The core of the paper lies in Section 5 that reports on a number of past experiences in using Spreading Activation in associative IR 2. The Information Retrieval problem Information Retrieval (for a good overview see(van Rijsbergen, 1979, Salton, 1989 Frakes and Baeza-Yates, 1992) is a science that aims to store and allow fast access to a large amount of information. This information can be of any kind: textual, visual, or auditory. An Information Retrieval System(IRS)is a computing tool which stores this information to be retrieved for future use. Most actual IR systems store and enable the retrieval of only textual information or documents. To give a clue to the size of the task, it must be noticed that often the collections of documents an irs has to deal with contain several thousands or even millions of documents A user accesses the irS by submitting a query, the Irs then tries to retrieve all documents that satisfy" the query. As opposed to database systems, and irS does not provide an exact answer but produce a ranking of documents that appear to contain some relevant information. Queries and documents are usually expressed in natural language and to be processed by the irS they are passed through a query and a document processors which breaks them into their constituents words. This process is called indexing, and in most modern IRS it is fully automatic. During indexing non-content-bearing words("the but,"and",etc. )are discarded, and suffixes are removed, so that what remains to represent query and documents are two lists of terms. These terms are often weighted using some statistical weighting schema that is meant to capture the importance of a term in representing the document or the query informative content(for an old but still very useful survey on weighti schema see(Robertson and Sparck Jones, 1976)). Document indexin performed off-line and document representation are stored in a inverted file", that is a file that reports for each term a weighted list of documents in which the term appear. Query indexing is performed on-line, using the
APPLICATION OF SPREADING ACTIVATION TECHNIQUES IN IR 455 ongoing at the Computing Science Department of the University of Glasgow. The main aim of the research is to develop a prototype of a interactive IR system based on a network representation structure, which makes use of application domain knowledge acquired by interactions with users. The SA processing framework and some of its applications to IR are analysed in this paper with this purpose in mind. The paper is structured as follows: Section 2 briefly explain the IR problem and what has been done so far to solve it, Section 3 explain what a Semantic Network is, and Section 4 describes the Spreading Activation technique and its variants, which is the most commonly used processing paradigm of Semantic Networks. The core of the paper lies in Section 5 that reports on a number of past experiences in using Spreading Activation in associative IR. 2. The Information Retrieval problem Information Retrieval(for a good overview see (van Rijsbergen, 1979; Salton, 1989; Frakes and Baeza-Yates, 1992)) is a science that aims to store and allow fast access to a large amount of information. This information can be of any kind: textual, visual, or auditory. An Information Retrieval System (IRS) is a computing tool which stores this information to be retrieved for future use. Most actual IR systems store and enable the retrieval of only textual information or documents. To give a clue to the size of the task, it must be noticed that often the collections of documents an IRS has to deal with contain several thousands or even millions of documents. A user accesses the IRS by submitting a query, the IRS then tries to retrieve all documents that “satisfy” the query. As opposed to database systems, and IRS does not provide an exact answer but produce a ranking of documents that appear to contain some relevant information. Queries and documents are usually expressed in natural language and to be processed by the IRS they are passed through a query and a document processors which breaks them into their constituents words. This process is called indexing, and in most modern IRS it is fully automatic. During indexing non-content-bearing words (“the”, “but”, “and”, etc.) are discarded, and suffixes are removed, so that what remains to represent query and documents are two lists of terms. These terms are often weighted using some statistical weighting schema that is meant to capture the importance of a term in representing the document or the query informative content (for an old but still very useful survey on weighting schema see (Robertson and Sparck Jones, 1976)). Document indexing is performed off-line and document representation are stored in a “inverted file”, that is a file that reports for each term a weighted list of documents in which the term appear. Query indexing is performed on-line, using the
E CRESTANI assessment Information Retrieval System Figure 1. a classical Information Retrieval system same procedure of document indexing so that the query representation can be compared using some similarity evaluation algorithms with the document representations. Good iR systems typically rank the matched documents so that those most likely to be relevant( those with the higher similarity with the query representation) are presented to the user first. Some retrieved docu- ments will be relevant (with varying degree of relevancy) and some will, unfortunately, be irrelevant. The user appraises those ones that he considers relevant and feeds them through a process called Relevance Feedback(rF) which modifies the original query to produce a new improved query and as a consequence a new ranking of documents. If the iR process is interactive this will go on until the user is happy of the resulting list of documents. An example of a such an IrS is depicted in Figurel In recent years big efforts have been devoted to the attempt to improve the performance of IR systems and research has explored many differ ent directions trying to use with profits results achieved in other areas. An area which attracts much attention in IR is Artificial Intelligence. so much that a new branch of IR called Intelligent IR (IIR) arised from these studies. A few directions of the research in IIR are reported in( Croft, 1987, Jacobs, 1992). Among them, the use of knowledge based techniques in IR has received a particular attention. The aim is to use application domain knowledge in the indexing, in the similarity evaluation, or to enrich the query representation. This last use seems particularly promising because it would nable to retrieve do ith terms not present in the query but relevant to the concepts expressed in the query. The most typical example of use of application domain knowledge in IR is depicted in Figure 2, where knowledge stored in a Knowledge Base is used to expand the original query formulation to include terms related to those originally used by the author
456 F. CRESTANI Figure 1. A classical Information Retrieval system. same procedure of document indexing so that the query representation can be compared using some similarity evaluation algorithms with the document representations. Good IR systems typically rank the matched documents so that those most likely to be relevant (those with the higher similarity with the query representation) are presented to the user first. Some retrieved documents will be relevant (with varying degree of relevancy) and some will, unfortunately, be irrelevant. The user appraises those ones that he considers relevant and feeds them through a process called Relevance Feedback (RF) which modifies the original query to produce a new improved query and as a consequence a new ranking of documents. If the IR process is interactive this will go on until the user is happy of the resulting list of documents. An example of a such an IRS is depicted in Figure1. In recent years big efforts have been devoted to the attempt to improve the performance of IR systems and research has explored many different directions trying to use with profits results achieved in other areas. An area which attracts much attention in IR is Artificial Intelligence, so much that a new branch of IR called Intelligent IR (IIR) arised from these studies. A few directions of the research in IIR are reported in (Croft, 1987; Jacobs, 1992). Among them, the use of knowledge based techniques in IR has received a particular attention. The aim is to use application domain knowledge in the indexing, in the similarity evaluation, or to enrich the query representation. This last use seems particularly promising because it would enable to retrieve documents indexed with terms not present in the query but relevant to the concepts expressed in the query. The most typical example of use of application domain knowledge in IR is depicted in Figure 2, where knowledge stored in a Knowledge Base is used to expand the original query formulation to include terms related to those originally used by the author
APPLICATION OF SPREADING ACTIVATION TECHNIQUES IN IR 457 Knowledge Base ordered Intelligent Informatlon Retrieval System Figure 2. An Intelligent Information Retrieval system Among the many formalisms that could be used to represent application domain knowledge for IR applications, Semantic Networks or other network representation structure seem quite promising. The use of a network repre- sentation structure makes this approach particularly appealing for associative IR. The most used network knowledge representation structure is a Semantic Network, that uses Spreading Activation as its processing paradigm. In the following two section we will explain what a Semantic Network is and how Spreading Activation on a Semantic Network works 3. Semantic Networks Since their introduction by Quillian in(Quillian, 1968), Semantic Networks have played a significant role in knowledge representation research. Accord to Quillian definition, Semantic Networks express knowledge in terms of concepts, their properties, and the hierarchical sub-superclass relationship between concepts. Each concept is represented by a node and the hierar- chical relationship between concept is depicted by connecting appropriate concept nodes via"is-a"or"instance-of links(Schiel, 1989). Nodes at the lowest level denote classes or categories of individuals while nodes at the higher levels denotes classes or categories of individuals. Concepts get more abstract as one moves up the is-a hierarchy. Properties are also represented by nodes, and the fact that a property applies to a concept is represented by connecting the property node and the concept node via an appropriate labelled link. Typically, a property is attached at the highest concept in the conceptual hierarchy to which the property applies, and if a property is attached to a node, it is assumed that it applies to all nodes that are descendants of that node. An example of a Semantic Network is depicted in Figure 3
APPLICATION OF SPREADING ACTIVATION TECHNIQUES IN IR 457 Figure 2. An Intelligent Information Retrieval system. Among the many formalisms that could be used to represent application domain knowledge for IR applications, Semantic Networks or other network representation structure seem quite promising. The use of a network representation structure makes this approach particularly appealing for associative IR. The most used network knowledge representation structure is a Semantic Network, that uses Spreading Activation as its processing paradigm. In the following two section we will explain what a Semantic Network is and how Spreading Activation on a Semantic Network works. 3. Semantic Networks Since their introduction by Quillian in (Quillian, 1968), Semantic Networks have played a significant role in knowledge representation research. According to Quillian definition, Semantic Networks express knowledge in terms of concepts, their properties, and the hierarchical sub-superclass relationship between concepts. Each concept is represented by a node and the hierarchical relationship between concept is depicted by connecting appropriate concept nodes via “is-a” or “instance-of” links (Schiel, 1989). Nodes at the lowest level denote classes or categories of individuals while nodes at the higher levels denotes classes or categories of individuals. Concepts get more abstract as one moves up the is-a hierarchy. Properties are also represented by nodes, and the fact that a property applies to a concept is represented by connecting the property node and the concept node via an appropriate labelled link. Typically, a property is attached at the highest concept in the conceptual hierarchy to which the property applies, and if a property is attached to a node, it is assumed that it applies to all nodes that are descendants of that node. An example of a Semantic Network is depicted in Figure 3