texai.org

On the SourceForge project site, I just released the Spreading Activation Java library. It is a generally useful component of the English dialog system, in which spreading activation elaborates a discourse context by activating relevant concepts that are linked via the knowledge base to one or more concepts explicitly mentioned in an utterance.

The spreading activation library is a Java class that performs the operation of spreading activation on a directed graph of nodes. 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. Activation may originate from alternate paths, identified by markers, and terminate when two paths reach the same node.

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

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 from more than one path.

Click on the image for a full-sized version.

In this illustration, 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.5. The decay factor was 0.85. Four cycles of spreading activation have occurred. Color hue and saturation indicate different activation values.

Java Implementation
There are three classes in this library:

• Node.java
• Link.java
• SpreadingActivationGraph.java

Node
Instances of this class are uniquely identified by their label. During the spreading activation process, nodes contain the activation value and optional marker.

Link
Instances of this class form the directed links between a source node and target nodes. When constructed, each link contains the target node object and the weight to apply to apply during the spreading activation process. Links are contained by a list kept in the source node.

SpreadingActivationGraph
One or more instances of this class are constructed by the application to perform spreading activation on their contained graphs. The primary data structure of the graph is a node dictionary in which the keys are the node labels and the values are the associated nodes. Firing of the nodes is conducted by concurrent NodeFiringWorker instances. Experiments demonstrate a 30% speedup using two threads on a dual core CPU vs one thread on the same CPU. The number of NodeFiringWorker threads defaults to the number of CPU cores in the host. See the API Javadoc for constructor and method descriptions.

Examples
See the test class SpreadingActivationGraphTest.java for API examples.

Unit Tests
The script run-tests.sh in the scripts directory performs all the tests on Linux using JUnit 4.x.