《电子商务 E-business》阅读文献：application of spreading activation techniques in information retrieval

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 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 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 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

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 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 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 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 requirements 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 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 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 Figure1. 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 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 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￾ing 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

458 E CRESTANI Figure 3. An example of a Semantic Network. The term Semantic Networks has been used in a far more general sense in the knowledge representation literature than what has been described above, and for what concerns IR, researchers have often used the term Semantic Network to refer to an Associative Network. This is a generic network of information items in which information items are represented by nodes, and links express sometimes undefined and unlabeled associative relations among information items. In modern IR, where statistical techniques are used in the indexing phase to associate weights to index terms, the relationships among information items are sometimes weighted, so adding to the network a measure of the strength of associations. In Section 5 we will report a few examples of the kind of Associative Networks used in IR. Semantic or Associative Networks are usually processed by means of a technique called Spreading Activation that will be explained in the next 4. Associative Retrieval using Spreading Activation Historically speaking, SA was not the first associative processing paradigm to be used in IR. Studies on Associative Retrieval date as early as the 60s and had their origins in statistical studies of associations among terms and/or documents in a collection. The "associative linear retrieval model"is one of these earliest models based on the concept of associative retrieval. Thi model, in its basic idea(Salton, 1968), consists of expanding the orig- inal query using statistically determined term-term, term-document, and document-document associations. This technique is based on the assump-

458 F. CRESTANI Figure 3. An example of a Semantic Network. The term Semantic Networks has been used in a far more general sense in the knowledge representation literature than what has been described above, and for what concerns IR, researchers have often used the term Semantic Network to refer to an Associative Network. This is a generic network of information items in which information items are represented by nodes, and links express sometimes undefined and unlabeled associative relations among information items. In modern IR, where statistical techniques are used in the indexing phase to associate weights to index terms, the relationships among information items are sometimes weighted, so adding to the network a measure of the strength of associations. In Section 5 we will report a few examples of the kind of Associative Networks used in IR. Semantic or Associative Networks are usually processed by means of a technique called Spreading Activation that will be explained in the next section. 4. Associative Retrieval using Spreading Activation Historically speaking, SA was not the first associative processing paradigm to be used in IR. Studies on Associative Retrieval date as early as the 60s and had their origins in statistical studies of associations among terms and/or documents in a collection. The “associative linear retrieval model” is one of these earliest models based on the concept of associative retrieval. This model, in its basic idea (Salton, 1968), consists of expanding the orig￾inal query using statistically determined term–term, term–document, and document–document associations. This technique is based on the assump-

APPLICATION OF SPREADING ACTIVATION TECHNIQUES IN IR 459 tion that there exists statistically determinable relations among terms, amon documents. and among documents and terms. These associations can be represented in a similarity matrix. Quantitative evaluations of similarity between terms, for example, can be obtained by means of statistical analy of term co-occurrence in documents. Associations between documents based on a quantitative evaluation of their respective similarity, can be obtained evaluating similarities in the terms assignments to documents or by means of citations and other bibliographic indicators. There are many heavy assumptions on this model and more recent studies(Preece, 1981 Salton and Buckley, 1988) have lead to the conclusion that effective term expansion methods valid for a variety of different collections are difficult to generate. Moreover, IR systems based on this approach have shown a lack of consistent improvements in the effectiveness. This result can have various motivations. First, the similarities statistically derived from some pairs of documents, or some pairs of terms, may be valid only locally in the partic- ular" environment(or application domain) from which they are obtained. Second, most practical methods for computing the document associations are based on the assumption that the terms or the documents are originally uncor related, i.e. independent of each other. Such assumption is no more accepted in many of the new research directions of IR. Recently, these models of associative retrieval has been revised using the SO-called Spreading Activation Model, which is based on supposed mecha nisms of human memory operations. Originated from psychological studies (see for example(Rumelhart and Norman, 1983)) it was first introduced in Computing Science in the area of Artificial Intelligence to provide a process- ing framework for Semantic Networks. Its use has been praised and criticised but it is currently adopted in many different areas such as: Cognitive Science, Databases, Artificial Intelligence, Psychology, Biology, and lately to IR. The basic SA model has, however, been subject to various enhancements in order to make it more suitable to various application areas and the way it is used in IR is quite different from the original formulation in the area of psychology In the following three sections the SA model will be described in deptl ection 4. 1 will describe the"pure"SA model, which consists in the sole use of the associative nature of a network representation as a search controlling structure In Section 4.2 some more search controlling structures will be added in order to give preference to particular associations. Section 4.3 will show how the search controlling structure can be used in a interactive way using external feedback

APPLICATION OF SPREADING ACTIVATION TECHNIQUES IN IR 459 tion that there exists statistically determinable relations among terms, among documents, and among documents and terms. These associations can be represented in a similarity matrix. Quantitative evaluations of similarity between terms, for example, can be obtained by means of statistical analy￾sis of term co-occurrence in documents. Associations between documents, based on a quantitative evaluation of their respective similarity, can be obtained evaluating similarities in the terms assignments to documents or by means of citations and other bibliographic indicators. There are many heavy assumptions on this model and more recent studies (Preece, 1981; Salton and Buckley, 1988) have lead to the conclusion that effective term expansion methods valid for a variety of different collections are difficult to generate. Moreover, IR systems based on this approach have shown a lack of consistent improvements in the effectiveness. This result can have various motivations. First, the similarities statistically derived from some pairs of documents, or some pairs of terms, may be valid only locally in the partic￾ular “environment” (or application domain) from which they are obtained. Second, most practical methods for computing the document associations are based on the assumption that the terms or the documents are originally uncor￾related, i.e. independent of each other. Such assumption is no more accepted in many of the new research directions of IR. Recently, these models of associative retrieval has been revised using the so-called Spreading Activation Model, which is based on supposed mecha￾nisms of human memory operations. Originated from psychological studies (see for example (Rumelhart and Norman, 1983)) it was first introduced in Computing Science in the area of Artificial Intelligence to provide a process￾ing framework for Semantic Networks. Its use has been praised and criticised, but it is currently adopted in many different areas such as: Cognitive Science, Databases, Artificial Intelligence, Psychology, Biology, and lately to IR. The basic SA model has, however, been subject to various enhancements in order to make it more suitable to various application areas and the way it is used in IR is quite different from the original formulation in the area of psychology. In the following three sections the SA model will be described in depth. Section 4.1 will describe the “pure” SA model, which consists in the sole use of the associative nature of a network representation as a search controlling structure. In Section 4.2 some more search controlling structures will be added in order to give preference to particular associations. Section 4.3 will show how the search controlling structure can be used in a interactive way using external feedback

460 E CRESTANI Figure 4. The network structure of a SA model 4. 1. The pure Spreading Activation model The SAmodel in its"pure" form is quite simple. It is made up ofa conceptually simple processing technique on a network data structure The network data structure consists of nodes connected by links, as depicted in Figure 4 Nodes model objects or features of objects of the"real world"to be represented They are usually labelled with the name of the objects they intend to represent. Links model relationships between nodes and they can be labelled and/or weighted. The connectivity pattern reflects the relation- ships between objects and/or features of objects of the "real world"to be represented. a links usually has a direction, a label, and/or a weight assigned according to a specific direction. This representation structure is very similar to a Semantic Network, but it is more general than the definition of Semantic Network given in Section 3. It could represent a Semantic Network, but also a more generic Associative Network The processing technique is defined by a sequence of iterations like the one hematically described in Figure 5. Each iteration is followed by another iteration until halted by the user or by the triggering of some termination condition. an iteration consists of 2. termination check What distinguish the pure Sa model from other more complex models is the sequence of actions which composes the pulse. a pulse is made up of three phases

460 F. CRESTANI Figure 4. The network structure of a SA model. 4.1. The pure Spreading Activation model The SA model in its “pure” form is quite simple. It is made up of a conceptually simple processing technique on a network data structure. The network data structure consists of nodes connected by links, as depicted in Figure 4. Nodes model objects or features of objects of the “real world” to be represented. They are usually labelled with the name of the objects they intend to represent. Links model relationships between nodes and they can be labelled and/or weighted. The connectivity pattern reflects the relation￾ships between objects and/or features of objects of the “real world” to be represented. A links usually has a direction, a label, and/or a weight assigned according to a specific direction. This representation structure is very similar to a Semantic Network, but it is more general than the definition of Semantic Network given in Section 3. It could represent a Semantic Network, but also a more generic Associative Network. The processing technique is defined by a sequence of iterations like the one schematically described in Figure 5. Each iteration is followed by another iteration until halted by the user or by the triggering of some termination condition. An iteration consists of: 1. one or more pulses; 2. termination check. What distinguish the pure SA model from other more complex models is the sequence of actions which composes the pulse. A pulse is made up of three phases: 1. preadjustment;

APPLICATION OF SPREADING ACTIVATION TECHNIQUES IN IR pre-adjustment satisfied Figure 5. The pure SA model In the preadjustment and postadjustement phases, which are optional, some form of activation decay can be applied to the active nodes. These phases are used to avoid retention of activation from pre ol both activation of single nodes and the overall activation of the network They implement a form of loss of interest" in nodes that are not continually ctivated The spreading phase consists on a number of passages of activation weaves from one node to all other nodes connected to it. There are many ways of spreading the activation over a network(for a overview see(Preece, 1981)) In its more simple form, on a single unit level, SA consists first in the computation of the unit input using this formula J1=∑O where Ii is the total input of node j O; is the output of unit i connected to node wij is a weight associated to the link connecting node i to node

APPLICATION OF SPREADING ACTIVATION TECHNIQUES IN IR 461 Figure 5. The pure SA model. 2. spreading; 3. postadjustment. In the preadjustment and postadjustement phases, which are optional, some form of activation decay can be applied to the active nodes. These phases are used to avoid retention of activation from previous pulses, enabling to control both activation of single nodes and the overall activation of the network. They implement a form of “loss of interest” in nodes that are not continually activated. The spreading phase consists on a number of passages of activation weaves from one node to all other nodes connected to it. There are many ways of spreading the activation over a network (for a overview see (Preece, 1981)). In its more simple form, on a single unit level, SA consists first in the computation of the unit input using this formula: Ij = X i Okwij where: Ij is the total input of node j; Oi is the output of unit i connected to node j; wij is a weight associated to the link connecting node i to node j

E CRESTANI The input and the weight are usually real numbers, however their numer- ical type is determined by the specific requirements of the application to be modelled. In particular, they can be binary values(0 or 1), excitatory/ inhibitory values(+l or-1), or they can be real values indicating the strength of the relation between nodes. Usually the first two of these options are used in connection with networks with labelled links like for examples Semantic Networks, where the semantic value of the relation represented by the link determines, in the context of the application, the value to be associated to the link. The last option is mainly used for Associative Networks, where there is only one generic type of association that need to be weighted After a node has computed its input value, its output value must be deter- mined. The numerical type of the output of a node is also determined by the requirements of the application. The two most used cases being the binary active/non-active type(0 or 1)and the real value type. In Sa models there is usually no distinction between"activation"or"output of a unit. The activa tion level of a unit is its output value. This is usually computed as a function of the input value O;=f(1) There are many different functions that can be used in the evaluation of the output, some examples are depicted in Figure 6. The most commonly used function to the above formula in the case of binary value units give. esol 'o function in pure SA models is the threshold function. It is used to determin the node has to be considered active or not. The application of the threshold 01kj where kj is the threshold value for unit The threshold value of the activation function is application dependent and can vary from node to node, therefore the notation k; for the unit threshold has been used After the node has computed its output value, it fires it to all the nodes connected to it, usually sending the same value to each of them Pulse after pulse, the activation spreads over the network reaching nodes that are far from the initially activated ones. After a determined number of pulses has been fired a termination condition is checked. If the condition is verified than the sa process stops, otherwise it goes on for another series of pulses. SA is therefore iterative, consisting of a sequence of pulses and termination checks The result of the sa process is the activation level of nodes reached at termination time. The interpretation of the level of activation of each node

462 F. CRESTANI The input and the weight are usually real numbers, however their numer￾ical type is determined by the specific requirements of the application to be modelled. In particular, they can be binary values (0 or 1), excitatory/ inhibitory values (+1 or -1), or they can be real values indicating the strength of the relation between nodes. Usually the first two of these options are used in connection with networks with labelled links like for examples Semantic Networks, where the semantic value of the relation represented by the link determines, in the context of the application, the value to be associated to the link. The last option is mainly used for Associative Networks, where there is only one generic type of association that need to be weighted. After a node has computed its input value, its output value must be deter￾mined. The numerical type of the output of a node is also determined by the requirements of the application. The two most used cases being the binary active/non-active type (0 or 1) and the real value type. In SA models there is usually no distinction between “activation” or “output” of a unit. The activa￾tion level of a unit is its output value. This is usually computed as a function of the input value: Oj = f (Ij ) There are many different functions that can be used in the evaluation of the output, some examples are depicted in Figure 6. The most commonly used function in pure SA models is the threshold function. It is used to determine if the node j has to be considered active or not. The application of the threshold function to the above formula in the case of binary value units gives: Oj =  0 Ij kj where kj is the threshold value for unit j. The threshold value of the activation function is application dependent and can vary from node to node, therefore the notation kj for the unit threshold has been used. After the node has computed its output value, it fires it to all the nodes connected to it, usually sending the same value to each of them. Pulse after pulse, the activation spreads over the network reaching nodes that are far from the initially activated ones. After a determined number of pulses has been fired a termination condition is checked. If the condition is verified than the SA process stops, otherwise it goes on for another series of pulses. SA is therefore iterative, consisting of a sequence of pulses and termination checks. The result of the SA process is the activation level of nodes reached at termination time. The interpretation of the level of activation of each node