Spreading activation

Spreading activation

Spreading activation is a method for searching associative networks, neural networks, or semantic networks. The search process is initiated by labeling a set of source nodes (e.g. concepts in a semantic network) with weights or "activation" and then iteratively propagating or "spreading" that activation out to other nodes linked to the source nodes. Most often these "weights" are real values that decay as activation propagates through the network. When the weights are discrete this process is often referred to as marker passing. Activation may originate from alternate paths, identified by distinct markers, and terminate when two alternate paths reach the same node.

Spreading activation models are used in cognitive psychology[1][2] to model the fan out effect.

Spreading activation can also be applied in information retrieval,[3][4] by means of a network of nodes representing documents and terms contained in those documents.

Contents

Algorithm

A directed graph is populated by Nodes[ 1...N ] each having an associated activation value A [ i ] which is a real number in the range [ 0.0 ... 1.0]. A Link[ i, j ] connects source node[ i ] with target node[ j ]. Each link has an associated weight W [ i, j ] usually a real number in the range [0.0 ... 1.0].[5]

Parameters:

  • Firing threshold F, a real number in the range [0.0 ... 1.0]
  • Decay factor D, a real number in the range [0.0 ... 1.0]

Steps:

  1. Initialize the graph setting all activation values A [ i ] to zero. Set one or more origin nodes to an initial activation value greater than the firing threshold F. A typical initial value is 1.0.
  2. For each unfired node [ i ] in the graph having an activation value A [ i ] greater than the node firing threshold F:
  3. For each Link [ i , j ] connecting the source node [ i ] with target node [ j ], adjust A [ j ] = A [ j ] + (A [ i ] * W [ i, j ] * D) where D is the decay factor.
  4. If a target node receives an adjustment to its activation value so that it would exceed 1.0, then set its new activation value to 1.0. Likewise maintain 0.0 as a lower bound on the target node's activation value should it receive an adjustment to below 0.0.
  5. Once a node has fired it may not fire again, although variations of the basic algorithm permit repeated firings and loops through the graph.
  6. Nodes receiving a new activation value that exceeds the firing threshold F are marked for firing on the next spreading activation cycle.
  7. If activation originates from more than one node, a variation of the algorithm permits marker passing to distinguish the paths by which activation is spread over the graph
  8. The procedure terminates when either there are no more nodes to fire or in the case of marker passing from multiple origins, when a node is reached from more than one path. Variations of the algorithm that permit repeated node firings and activation loops in the graph, terminate after a steady activation state, with respect to some delta, is reached, or when a maximum number of iterations is exceeded.

See also

Examples

In this example, spreading activation originated at node 1 which has an initial activation value of 1.0 (100%). Each link has the same weight value of 0.9. The decay factor was 0.85. Four cycles of spreading activation have occurred. Color hue and saturation indicate different activation values.

Notes

  1. ^ Collins, Allan M.; Loftus, Elizabeth F., "A spreading-activation theory of semantic processing", Psychological Review. 1975 Nov Vol 82(6) 407-428 [1]
  2. ^ John R. Anderson. "A spreading activation theory of memory." Journal of Verbal Learning and Verbal Behavior, 1983
  3. ^ S. Preece, A spreading activation network model for information retrieval. PhD thesis, University of Illinois, Urbana-Champaign, 1981.
  4. ^ Fabio Crestani. "Application of Spreading Activation Techniques in Information Retrieval". Artificial Intelligence Review, 1997
  5. ^ Boosting item keyword search with spreading activation Aswath, D.; Ahmed, S.T.; Dapos;cunha, J.; Davulcu, H., Web Intelligence, 2005. Proceedings. The 2005 IEEE/WIC/ACM International Conference on Volume , Issue , 19-22 Sept. 2005 Page(s): 704 - 707

References

  • Nils J. Nilsson. "Artificial Intelligence: A New Synthesis". Morgan Kaufmann Publishers, Inc., San Francisco, California, 1998, pages 121-122
  • Rodriguez, M.A., " Grammar-Based Random Walkers in Semantic Networks", Knowledge-Based Systems, 21(7), 727-739, doi:10.1016/j.knosys.2008.03.030, 2008.

External links

  • JMaPSS The Java Marker-Passing Search Service, a relevance search engine employing a family of marker-passing algorithms based on spreading activation theory.
  • Texai An open source project to create artificial intelligence that provides a Java spreading activation class library.

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Spreading Activation Network — Aktivierungsausbreitung Das Modell von Collins und Loftus zur Aktivierungsausbreitung (Spreading Activation Network) findet in der Sprachpsychologie und beim semantischen Priming seine Anwendung und dient zur Veranschaulichung der Prozesse, die… …   Deutsch Wikipedia

  • Interactive activation model — Das mentale Lexikon (lateinisch mens, „Denken“, „Verstand“, „Geist“ und altgriechisches Neutrum λεξικόν, lexikón, „das Wort betreffend“, von λέξις, léxis, „Rede“, „Wort“ und dem zugehörigen Verb λέγειν, légein, „sammeln“, „sprechen“, „[auf… …   Deutsch Wikipedia

  • Memory errors — Memory gaps and errors refer to the incorrect recall, or complete loss, of information in the memory system for a specific detail and/or event. Memory errors may include remembering events that never occurred, or remembering them differently from …   Wikipedia

  • Connectionism — is a set of approaches in the fields of artificial intelligence, cognitive psychology, cognitive science, neuroscience and philosophy of mind, that models mental or behavioral phenomena as the emergent processes of interconnected networks of… …   Wikipedia

  • Semantic memory — refers to the memory of meanings, understandings, and other concept based knowledge unrelated to specific experiences. The conscious recollection of factual information and general knowledge about the world,cite web… …   Wikipedia

  • Recall (memory) — Recollection redirects here. For other uses, see Recollection (disambiguation). Recall in memory refers to the retrieval of events or information from the past. Along with encoding and storage, it is one of the three core processes of memory.… …   Wikipedia

  • Priming (psychology) — Priming is an implicit memory effect in which exposure to a stimulus influences a response to a later stimulus. It can occur following perceptual, semantic, or conceptual stimulus repetition. For example, if a person reads a list of words… …   Wikipedia

  • Artikulatorische Ebene — Das mentale Lexikon (lateinisch mens, „Denken“, „Verstand“, „Geist“ und altgriechisches Neutrum λεξικόν, lexikón, „das Wort betreffend“, von λέξις, léxis, „Rede“, „Wort“ und dem zugehörigen Verb λέγειν, légein, „sammeln“, „sprechen“, „[auf… …   Deutsch Wikipedia

  • Einsetzungsregel — Das mentale Lexikon (lateinisch mens, „Denken“, „Verstand“, „Geist“ und altgriechisches Neutrum λεξικόν, lexikón, „das Wort betreffend“, von λέξις, léxis, „Rede“, „Wort“ und dem zugehörigen Verb λέγειν, légein, „sammeln“, „sprechen“, „[auf… …   Deutsch Wikipedia

  • Inneres Lexikon — Das mentale Lexikon (lateinisch mens, „Denken“, „Verstand“, „Geist“ und altgriechisches Neutrum λεξικόν, lexikón, „das Wort betreffend“, von λέξις, léxis, „Rede“, „Wort“ und dem zugehörigen Verb λέγειν, légein, „sammeln“, „sprechen“, „[auf… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”