Search from Qb:
- STEP 3.A:
- Pop the next node from Qb into a variable x. If Qb is empty, no more relations exist, so terminate with failure.
- STEP 3.B:
- If some neighbor y of x has label a, then a relation between A and B has been found. Create a list describing this relation as follows:
- STEP 3.B.i:
- Set z := x.
- STEP 3.B.ii:
- Append z to the end of the list. If z == B, then skip to step 3.B.iii. Otherwise let z = D(z) and repeat step 3.B.ii.
- STEP 3.B.iii:
- Set z := y.
- STEP 3.B.iv:
- Prepend z to the front of the list. If z == A, then skip to step 3.B.v. Otherwise let z = D(z) and repeat step 3.B.iv.
- STEP 3.B.v:
- The list has been completed. If you wish to find more relations, continue to 3.C. Otherwise, terminate with success.
- STEP 3.C:
- Set D(y) := x for all unlabeled neighbors y of x. Label these neighbors b, and add them to Qb. Return to step 2.
Empirical Results
Collins and Quillian, and others (Conrad 1972) offer empirical data that suggests this model mimics the reaction time for human verification of relations. For example, verification of the statement "Canaries can sing" is faster than that of the statement "Canaries have skin" for both humans and Quillian's model.
In Quillian's model, this time difference is easy to explain, as the following diagram suggests.
________ _________
| Animal |---->| hasSkin |
|________| |_________|
|
subclass
|
\|/
________ _________
| Bird |---->| canSing |
|________| |_________|
|
subclass
|
\|/
________
| Canary |
|________|
Here canSing is an attribute of the node Bird, while hasSkin is an attribute of the node Animal. The attribute canSing is accessed first since Bird is closer to Canary (in terms of the standard definition of distance on a graph--the number of edges between nodes) than Animal is.
We leave it to the reader to decide what this suggests about the possibility of hierarchical structure in human memory.
Bibliography
- Cohen, P. R. and Feigenbaum, E. A., "Article XI.E.1: Quillian's Semantic Memory System", The Handbook of Artificial Intelligence Volume 3 , pg 36-41, 1982.
- Collins, A. M. and Quillian, M. R., "Retrieval Time From Semantic Memory", Journal of Verbal Learning and Verbal Behaviour , Volume 8, pg 240-247, 1969.
- Collins, A. M. and Quillian, M. R., "How to Make a Language User", in E. Tulving and W. Donaldson (eds.), Organization and Memory , 1972.
- Conrad, C., "Cognitive Economy in Semantic Memory", Journal of Experimental Psychology , Volume 92, pg 149-154, 1972.
- Quillian, M. R., "Semantic Memory", in M. Minsky (ed.), Semantic Information Processing ,1968.