Destiny Project Notebook, Folio 4

I started a new sub-project today: the implementation of an associative memory class (cf. Thought and Memory, 17 Jan 1998). The associative memory class has a place to store knowledge items, some vocabulary tables that stand in the stead of some more complex language handler yet to be invented, and two association maps.

The one-element association map puts into a list all the ids of knowledge items that reference a subject.

The two-element association map maps a pair of subjects to a list of knowledge items that reference both ot those subjects.

As my first test case, I have created a belief: <the gods><created><me>.

The idea of a point of interest layer for the map has been around for a long time. The point of interest layer would be used to store the locations of cities, structures (e.g. castles, mines), or other locations that might serve as endpoints, waystations, or landmarks for path planning. The structure that would be best for such a layer has remained unclear, however, so the point of interest layer has not been implemented.

Recently, Bill and I have been talking about an "Almanac" that would store map knowledge (i.e. knowledge about the world) in the same form as it is stored for the individual entities. The distinction would be that the Almanac would be "true", whereas entities could have false knowledge, or be uncertain as to whether their knowledge is correct. In general, an entity's knowledge about the world will also be incomplete.

I am thinking now to combine these functions; that location could be an attribute of a subject which is a point of interest. This would allow the game engine itself to draw upon the benefits of associative memory to recall other attributes of the point of interest and its relationships to other map-related concepts. The point of interest layer will be subsumed into the Almanac, and the Almanac will be implemented as an associative memory.

I spent the month of February developing the associative memory classes and creating a GUI driver / test program for them. Among other accomplishments, used the test driver to create a knowledge set containing the "is-a" relationships of the game "Clue". Did quite a bit of thinking about how to traverse a knowledge net. One conclusion is that only a few kindds of relationships are useful in connecting knowledge items, "is", "is-a", "has-a" and their inverses being examples. Did not get to the point of implementing a traversal algorithm. Neither did I implement forgetting, even though it is a critical and differentiating feature of the memory model.

The associative memory work lead Bill to embark on a sub-project of defining and implementing classes to represent general expressions (both mathematical and logical). I contributed a function registry class as part of this effort. In March, it became clear that some class to represent a generic quantity would be essential to both the expression classes and to the earlier associative memory effort. Bill implemented a first draft of a quantity class. Based on this work, I created a more robust quantity class that also met the needs of associative memory and reasoning about maps and map objects.

During April, I completely re-wrote the quantity class again and fully documented the result while Bill and Julie were in Europe.

During May, I developed a class for working memory, the place where knowledge (and working suppositions) are fitted together with respect to a particular query against the associative memory. An ever-widening hypersphere of knowledge is recalled and placed in a knowledge graph, until all relevant knowledge has been recalled and filtered by the query constraints. Later, this class can be adapted to tasks other than answering queries, such as planning. See the documentation file for the Working Memory.

In the first two weeks of June, I continued developing the query-answering method of the working memory class. Realized that the existing associative graph class was not adequate to the task, as it only allowed one arc (relationship) between any pair of nodes (knowledge subjects).

From the last half of June until 10 July, Elsa and I prepared to go to Europe. 11 July to 9 August, we were in the British Isles and I did not work much on Destiny except to mark the changes to the graph class that would be needed to support multiple relationships (optionally "flavored") between any pair of nodes.

After returning from Europe, made the changes to the graph class, then began to retrofit the map path planning algorithms (which make extensive use of the graph class) to work properly with the new graph definition. Unfortunately, my use of templated class within templated class within templated class, coupled with the new graph class caused enough of a code explosion to prevent the map editor from compiling and linking. Spent the next two weeks of August defining concrete classes implementing specific templated types in an effort to reduce the complexity of the problem that the compiler had to deal with. This was eventually successful. Spent the last bit of August retrofitting the working memory class to use the new graph class.

Over the last week, I have modified the working memory class, adding the ability to form sets of candidates for variables present in the query, to form new associations whenever the candidate pool for a variable is defined or redefined, and to retrieve knowledge about an association that contains one or more variables. I have thought about, but not implemented, removing knowledge from the working memory when it is determined that a particular subject is no longer a candidate for a variable.

Implemented removal of subject nodes for subjects dropped from the candidate pools. There were two interesting wrinkles. One was the need to maintain a link between nodes and the reasons for their inclusion (supposition, concrete reference, candidate pool for variable, or an is-a link). Naturally, a particular node could serve any number of capacities in any combination of these categories. It is only appropriate to remove a node when it no longer serves any of these purposes, so these references need to be added and removed dynamically.

The other interesting wrinkle was the need to remove is-a references from nodes linked to the node about to be deleted (is-a targets from is-a relationships originating at the node to be deleted), and the concommittant desire to recursively delete any of those is-a targets which no longer had any references. This was accomplished by establishing a node deletion queue, with processing within the queue loop to remove is-a references and add the target nodes to the deletion queue.

With node deletion, the "ever-widening hypersphere of knowledge" (referred to in the notes for May) acquires the ability to prune itself as it grows. This is not so important for building the graph, where the candidate pool mechanism manages the growth of possibilities, but will become important when it comes time to put the information in the graph to use.

Steps to answering a question

1. Receiving the question.
2. Understanding the question, including recasting the question into a processable format.
3. Recalling knowledge applicable to the question.
4. Determining the available answers to the question (knowledge combinations which satisfy the question).
5. Determining the detail or specificity likely to be desired in the answer. This may involve assumptions about or determination of what the querant will want to do with the information and how specific an answer needs to be to satisfy the querant's purpose.
6. Selecting an answer from among those available.
7. Describing the selected answer, taking into account the assumptions and knowledge of the querant.
8. Transmitting the answer.

The foregoing assumes that one is inclined to be cooperative. If not, it is possible to simulate failure at any of the steps, from "I can't hear you", "I don't understand the question", pretending a lack of knowledge or substituting false knowledge, answering the question at a deliberately inappropriate level of detail, choosing the least helpful answer from among those available, describing the answer with a deliberately inappropriate set of assumptions, to simply keeping silent.

[Editor's Note: to understand the following, the reader should first have perused the white paper on the Working Memory with special attention to the manner in which queries are resolved.]

Implementing the working memory, it turned out that improving the determination of whether an item matches a query item by using is-a relationships was critical to success, but different from another critical procedure, namely augmenting a candidate pool using is-a relationships.

Consider the following knowledge base items

• <Elsa><owns><Bianca>
• <Bianca><is a><cat>
• <cat><is a><animal>

Now we ask the question

1. If, because of the costs related to the presence of other items in the knowledge base, the <owns> association is processed first, then the item <Elsa><owns><Bianca> will be recalled and <Bianca><%2>. The additional associations <%2><is a> and <%2><animal> will be added to the queue. Next, one of the associations based on query item 2 will be popped from the queue, and the associated items retrieved.
2. If the second association processed is <is a><animal> then the item <cat><is a><animal> is recalled. The comparison to determine whether the item matches the query will fail in the absence of is-a information because the first subject of the recalled item (<cat>) does not match any of the candidates for <%2> (the first subject of the query item). Candidates for <%2> include <Bianca> but not <cat>.
3. If, on the other hand the association processed is <%2><is a> then the item <Bianca><is a><cat> will be recalled. This will also fail to match the query, because the third subject of the recalled item (<cat>) does not match the third subject of the query item (<animal>).
4. Further, if the association processed is instead <%2><animal> then it is entirely possible that no items would match the association (no items would be recalled) and the entire query would fail. This is because any specific animal that is owned would be associated with some type of animal (dog, fish, etc.) and not directly with generic animal-ness. Because there would be few or none of this kind of association, the cost of processing this association would be low, so it would be processed in preference to the other two associations arising from query item 2.
5. Suppose instead that the initial association from query item 2 is processed before that from query item 1. (There are more ownership relationships than there are things that are animals.) In that case, the association <is a><animal> will recall the item <cat><is a><animal> and put <cat> in the candidate pool for <%2>. Based on the new definition of the pool for <%2>, a new association for query item 1 will be enqueued, namely <owns><%2>. The cost of this association cannot be worse than the initial association formed from query item 1 (which would require examination of all ownership knowledge), and almost certainly would be less.
6. The association <owns><%2> would be next examined. Unfortunately, the pool for <%2> has <cat>, not any specific cat. No knowledge items would be recalled, because any relevant ownership relationships would involve specific cats, not a generic <cat>. The pool for <%1> would be known to be empty, and the query would fail.

Taking the last example first [5, 6], we can resolve the difficulty either by changing the recall process to also recall associations in which the subjects are sub-classes of the stated concrete subject or of any of the candidates for a variable subject (and change the match criteria to pass those items) OR we can resolve the difficulty by augmenting candidate pools with all the sub-classes of the set of candidates (recursively determined, of course). The first solution would change step [6] to also recall (and apply) associations of <owns> with any type of cat and every specific cat. The second solution would change step [5] to also include in the candidate pool for <%2> all sub-classes of cat and all specific cats. While requiring a great deal of work, each of these is probably still less costly than examining all ownership relationships to determine whether any of their objects is a sub-class of <cat>. One advantage of augmenting the candidate pool is that the is-a relationships need to be processed once, whereas the other solution requires determining and using is-a information once to enhance the knowledge retrieval process and again when the recalled items are matched against the query item.

The general principle here is that if a candidate pool contains a subject which is really a class of subjects, that all subjects in the class should be considered to be part of the candidate pool. Problem [4] shows that this must also be extended to pools of one candidate, including concrete subjects. Under this interpretation, a candidate pool would be established for the concrete subject <animal> which would include <animal>and all its sub-classes. This would allow the necessary knowledge to be recalled using the association <%2><animal or sub-class thereof>, namely the item <Bianca><is a><cat>.

Under this principle, the processing of step [2] would be: the second association processed is <is a><animal or sub-class thereof> which recalls both <Bianca><is a><cat> and <cat><is a><animal>, but the pool for <%2> contains <Bianca> and not <cat>, so the item <cat><is a><animal> is discarded as not matching the query, while the item <Bianca><is a><cat> is accepted as matching the query and is added to the knowledge graph.

Similarly for step [3], the item <Bianca><is a><cat> will be recalled as before. The difference under the new principle is that the item will match the query item <%2><is a><animal or sub-class thereof> where it did not match <%2><is a><animal>.

In each of these last two cases [2, 3] the item <cat><is a><animal> either is discarded or is not recalled during processing of the respective associations, yet it clearly ought to be part of the final knowledge graph. Perhaps a good solution would be to place the items into the graph at the time that the candidate pool for <animal or sub-class thereof> is established. This would mean that the graph would start out with a lot of is-a information that would later be discarded, but it would also keep the state of the graph more consistent with the state of the pools.

8 September 1998

Have implemented the foregoing, and it seems to work well.

11 September 1998

It occurs to me that, contrary to part of the 7 September discussion, ownership need not be of specific subjects (or at least need not be of known subjects). "Jaime owns 3 cats" can be learned as:

                |-->     --|
Jaime -- owns --|-->     --|-- is a --> cat
                |-->     --|

where we know nothing about the three anonymous cats other than that Jaime owns them and that they are cats (and that they are distinct from one another). It seems a waste to reserve subjects for anonymous things, however. An alternative formulation would be a knowledge item of the form Noun - Relationship - Noun Class - Count [- Qualifier], such as either of <Jaime><owns><cat><3> or <Jaime><owns><cat><3><at least>.

19 September 1998

There's a problem with the implementation of pools for concrete subjects: when the query items are initially used to form associations, I am recalling all is-a information about the concrete subjects. I use the recalled items to form the candidate pools, and I am also placing the items in the graph. If the items are needed for the result, this is fine. If the is-a items pertain to sub-classes that are irrelevant, however, there is no trigger event that would cause the irrelevant item to be removed. There are a few possible solutions. One is to build the pools, but defer adding the knowledge to the graph until it is "needed" later.

The second is to manage the pools for concrete subjects as is done for pools for variables: when a candidate is not present in the items that can be recalled for a query item involving a pool, that candidate is removed from the pool and examined to determine whether it should be removed from the graph. Of course, a separate pool would need to be maintained for each occurance of the concrete subject since the pool would then be specific to its use in a particular query item. Consider, for example, "Who owns an animal who also has a son that owns an animal?" If pools are edited to correspond to recalled items, then the two occurances of "animal" will come to mean different things.

The third is to apply some postprocessing after the knowledge-assembling algorithm has run that removes nodes which are not on a path between endpoints of a graph of the query. This last might be necessary to remove unneeded suppositions, or suppositions could be checked explicitly at the end of the processing (i.e. not generically finding unused nodes, but only checking nodes appearing in suppositions).

Back to the Destiny documents

Back to the Previous Folio of the Notebook

Onward to the Next Folio of the Notebook