Destiny Project

Working Memory

Introduction

A working memory is the part of the entity's memory that is used to assemble a network of knowledge items relevant to a specific task, such as answering a question about the entity's knowledge or formulating a plan to accomplish some action or achieve some state.

A working memory is always linked to the entity's store of knowledge, here called the "source memory", which is an associative memory or some class of memory derived from an associative memory. A working memory not only draws knowledge from the source memory, but relies on the vocabulary of the source memory rather than building its own.

Components

The main components of a working memory are the pointer to the source memory and an associated directed graph in which the network of related knowledge items is assembled and linked. Within the graph, subjects are represented as nodes, with arcs defined for relationships and attributes.

To relate the node ids of the graph to the subjects known to the source memory, two maps are defined. One to map subject ids to graph nodes, the other to map graph nodes to subject ids. These maps are used both to relate the working memory to its corresponding source and to determine whether a particular subject is known to (i.e. has already been inserted into) the graph.

Query

A query is a question about the entity's knowledge. A query can be thought of as another network of knowledge items, but with variables in the place of some of the subjects and relationships. For example, the query "Which engineers own white cars?" can be represented as the following network:

var1 -- owns -- var2 -- is a -- car
  |               |
  |               ----- has attribute color -- white
  |
  ----- has attribute profession -- var3 -- is a -- engineer

Alternatively, this can be represented as a series of knowledge items, again with variables in some of the places:

NRN: <var1><owns><var2>
NRN: <var2><is a><car>
NAV: <var2><color><white>
NAV: <var1><profession><var3>
NRN: <var3><is a><engineer>

At this stage, queries are defined pretty simply. In particular they have no disjunctions ("Which engineers own green or white cars?"). To achieve full representational power will require the use of the general expression class. In addition to disjunctions, we hope eventually to be able to answer counting questions ("How many engineers own white cars?") and existence questions ("Are there any engineers who own white cars?").

One other point is worthy of note. It is permissible to include as part of a query a knowledge item that does not reference any variables. If such an item is included, it is treated as a supposition. It is not learned by the source memory, but is used in arriving at an answer to the query. ("Assuming that a software engineer is an engineer, which engineers own white cars?")

Answering a Query

Clearing the Working Memory

The first step in answering a query is to clear the working memory. This means that the graph representing the network of knowledge is emptied, as are the maps that relate graph nodes and knowledge subjects.

Determining Associations from the Query

Each knowledge item making up the query is then examined. If the knowledge item represents an association between two concrete subjects (i.e. knowledge subjects which are not variables), then a two-subject association between those subjects is formed and stored in a list of such associations. If, instead, the item contains only one concrete subject, then a one-subject association is formed with that subject and stored. If the item contains no concrete subjects, it is skipped over at this time. If the item contains no variables, it is added to the knowledge network graph as a supposition. At this point, units associated with values are not considered as subjects.

Prioritization of Associations Based on Cardinality

For each one-subject association and two-subject association, the source memory is asked to count the number of associated knowledge items. The associations are then entered into a priority queue in which high priority is given to low-cardinality associations.

Adding Associated Knowledge

Associations are removed from the priority queue. It is first determined whether the knowledge item from the query from which the association was derived has already been satisfied. If so, the association is discarded, and the next association removed from the queue.

Otherwise, the source memory is asked to supply the associated knowledge items in its possession. Knowledge items which do not match the query item are discarded. Matching knowledge items are inserted into the knowledge network graph. In addition, as each new subject node is added, the source memory is asked to supply is-a relationships for that subject which are also added to the graph.

If the knowledge subjects being added represent the first definition of a pool of candidates for a particular variable (or two) then a list of candidates for the variable(s) is defined. This list includes subjects added through is-a relationships. New relationships are extracted from each unsatisfied query item which contains the variable, their cardinality is assessed, and they are added to the priority queue.

If the subjects being added represent a subsequent definition of a pool of candidates for a variable, then the subject ids are checked against the list of previous candidates. Items for which a new candidate is not in the pool of previous candidates are not inserted into the graph. In addition, nodes representing previous candidates are removed if they are not present in the new pool of candidate subjects. New relationships are extracted from each unsatisfied query item which contains the variable, their cardinality is assessed, and they are added to the priority queue.

Example

At this point, an example is probably in order. Leaving the engineers aside for the moment, the question to be answered is "Who owns white cars?"

query item type content
1 NRN <var1><owns><var2>
2 NRN <var2><is a><car>
3 NAV <var2><color><white>

The associations are extracted and quantified.

Suppose the source memory knows of 20,000 ownership relationships, 500 cars, and 3,500 white objects. Extracting and quantifying the relationships yields:

association cardinality satisfies item
<owns> 20,000 1
<is a><car> 500 2
<color><white> 3,500 3
Priority Queue
association cardinality satisfies item
<is a><car> 500 2
<color><white> 3,500 3
<owns> 20,000 1

These associations are inserted into the priority queue.

Because it has the lowest cardinality, the <is a><car> association is the first to be removed from the queue. Item 2 has not been satisfied yet, so all 500 car items are retrieved from the source memory. With the exception of 5 items like <car><is a><motor vehicle> (which are discarded because they do not match the query item), most of these items are inserted into the knowledge net. At the same time, a candidate pool for var2 is created with the subject ids of the 495 specific cars of which the source memory has knowledge. Query item 2 is marked as having been satisfied.

Because there is now a candidate pool for var2, we can assess the cardinality of the associations <owns><pool2>, <pool2><color> and <pool2><white> as the sums, respectively, of the cardinalities of all associations <owns><pool2n>, <pool2n><color> and <pool2n><white> over all candidate subjects in pool2. (There is no need to assess the cardinality of associations arising from query item 2 because that query item has been satisfied.)

association cardinality satisfies item comment
<owns><pool2> 746 1 many have more than one owner
<pool2><color> 507 3 a few have more than one color
<pool2><white> 234 3 relatively few are white
Priority Queue
association cardinality satisfies item
<pool2><white> 234 3
<pool2><color> 507 3
<owns><pool2> 746 1
<color><white> 3,500 3
<owns> 20,000 1

These associations are inserted into the priority queue.

The next association to be removed is <pool2><white>. Item 3 has not yet been satisfied, so the 234 items which match the association are retrieved from the source memory. Some of these are from items like <car113><interior color><white>, so do not match the query item. Because there is already a candidate pool for var2, the subjects corresponding to var2 from the 170 matching items are checked against pool2. None of the new 170 subjects are disqualified, so their items (all of the form <n><color><white>) are added to the graph, while 325 of the subjects in pool2 are disqualified and removed both from the graph and from pool2. Query item 3 is marked as satisfied.

Because we have a new definition of pool2, the var2 relationships from unsatisfied query items are extracted and their cardinality assessed.

association cardinality satisfies item comment
<owns><pool2> 220 1 many have more than one owner
Priority Queue
association cardinality satisfies item
<owns><pool2> 220 1
<pool2><color> 507 3
<owns><pool2> 746 1
<color><white> 3,500 3
<owns> 20,000 1

This association is inserted into the priority queue.

The next association to be removed is <owns><pool2>. Item 1 has not yet been satisfied, so the 220 items which match the association are retrieved from the source memory. All of these knowledge items match the query item because no candidate pool for var1 has yet been formed. Because there is already a candidate pool for var2, the subjects corresponding to var2 from the 220 matching items are checked against pool2. None of the new 220 subjects are disqualified, so their items (all of the form <m><owns>< pool2n >) are added to the graph, and none of the subjects in pool2 are disqualified. Query item 1 is marked as satisfied.

Although we have a new definition of pool1, there are no unsatisfied query items containing var1, so there are no new associations to be formed nor added to the queue.

Priority Queue
association cardinality satisfies item
<pool2><color> 507 3
<owns><pool2> 746 1
<color><white> 3,500 3
<owns> 20,000 1

The next association to be removed from the queue is <pool2><color>. This refers to query item 3, which has been satisfied, so it is discarded. In fact, all of the remaining associations on the queue are for query items which have been satisfied, so they are all quickly discarded. The queue being empty, the knowledge network graph now represents all the knowledge relevant to answering the question.

Constructing an Answer from the Knowledge Network Graph

This trivial process is left as an exercise for the reader.


Back to the Destiny documents