An insight from computer science was that information storage can be characterized in terms of a data structure and the processes that operate on it. In applying this idea, cognitive psychology and artificial intelligence adopted the traditional data structures used in computer science (e.g., lists, trees, stacks, hash tables, etc.). Cognitive modellers would use the data structures and access processes which were familiar to them and appeared most suited to the task at hand. This choice of data structure was not always driven by the properties of the human memory system even though the properties of human memory are in some respects radically different from those of traditional computer memories. For example, many contemporary models of human memory use variations on a theme of direct access to memories (Hintzman, 1986, Humphreys, Bain, & Pike, 1989; Metcalfe, 1990; Murdock, 1982; Raaijmakers & Shiffrin, 1981). Such theories also allow the same cues to be used in different ways. A new viewpoint is emerging from these models with aspects of what had previously been regarded as reasoning and other higher order cognitive processes being attributed to memory access processes (Halford, Wilson, Guo, Wiles, & Stewart, in press; Wiles, Halford, Stewart, Humphreys, Bain, & Wilson, in press).
In this target article we describe data structures and memory access processes from a "human memory" perspective. Our two starting points are: (a) Marr's (1982) three levels for understanding an information processing device and (b) The standard experimental paradigms used to demonstrate the power and the complexity of human memory.
Marr argued that a complete understanding of an information processing device requires theories at each of three levels. The highest level is an abstract computational theory of the task. A theory at this level must specify the informational content of the inputs and outputs and the goal of the computation. The second level must specify the structure or form of the input and output information and the algorithm which transforms the input representations into the output representation. (Note that explicit mathematical theories or computer simulations are commonly referred to as "computational" theories in cognitive psychology, but we will refer to them as algorithmic-level theories.) The third level is the specification of the physical implementation of the representations and algorithm.
Before presenting our computational-level theory we discuss how Marr's ideas about specifying the informational content and the goal of the computation can be applied to human memory (1.1). We then discuss how a computational-level theory can be interpreted (1.2), and how we chose the tasks (1.3). After presenting our theory (2), we discuss how we chose the data structures and the access processes (3.1) and how the theory can be extended to new tasks (3.2). We then discuss applications to memory theory and research and how the theory can be invalidated (4). Finally, we discuss how the theory can be used in modelling higher cognitive processes (5).
1.1 The Information Available and the Goal of the Task
The first of Marr's (1982) levels is where the information that enters into a computation and the goal of the computation are specified. In human memory tasks information can be equated with what is made available by the test environment (e.g., the experimenter supplied cues and the experimental instructions indicating which cues and memories are relevant) or by the subject (e.g. subject supplied cues and self instructions). Besides the information made available at the time of testing the information abstracted from the study episode and the previous learning history of the subject must be specified. Does the task require information about the occurrence of a single item or a pair of items in a list? Does it require information about a pairwise relationship between two words (e.g., table and chair are associated), a particular relationship between two words (e.g., hot is the antonym of cold), or perceptual information linking a string of graphemes to a memorial item.
There is a precedent in the memory literature for specifying the goal of the computation, although it has not been thought of in these terms. Tulving's (1972) distinction between episodic and semantic memory is widely regarded as being extremely useful when applied to tasks, but there are substantial doubts about its applicability to memories or memory systems (see the BBS commentary on Tulving 1984). We think researchers intuitively appreciated the episodic/semantic distinction as a reflection of the fact that different memory tasks have different goals, but the distinctions usefulness is largely independent of the way it is implemented and a distinction between memory systems is only one of many ways it can be implemented.
1.2 Interpreting a Computational Level Theory
A computational-level theory specifies the inputs, outputs, and goal of a task. This answers the question of what is the computation and each task specification can be considered as a function in its own right. However, our goal is to go beyond computational-level theories for individual tasks by showing how each task specification can be composed of simpler functions. We identify a finite set of functions (computational primitives) out of which all other functions can be composed. Once identified they can be used to describe or propose hypotheses about an indefinite number of tasks. This goal is in keeping with Marr's suggestion that a computational-level theory can provide information about the logical structure of the computation. This paper accordingly shows that there is enough structure in a limited set of tasks to allow parsimonious and plausible computational primitives to emerge. It is also possible to propose that computational primitives are directly represented at the algorithmic level. We do not wish to discourage this view; it provides an important source of hypotheses about the similarities and differences between tasks. The reification of tasks or task components as memories or memory components has a long history in theories of human and animal memory (e.g., classical conditioning vs. instrumental conditioning, short-term memory vs. long-term memory, implicit memory vs. explicit memory, etc.). However, at several points we will be pointing out some of the pitfalls in this view.
Although Marr's ideas about a computational-level theory is also the starting point for Anderson and Milson's (1989) rational analysis, their conclusion is very different, because we are answering a different question. Anderson and Milson adopted the standard memory access assumption in cognitive psychology and artificial intelligence (access is simply the retrieval of memory traces) and focussed on the question of why access occurs. Their answer was that human memory has adapted to the environment in which it operates. In contrast, we focus on the question of what computation is performed and conclude that there is more to memory than trace retrieval. Both of these questions (What is the computation? and Why is it appropriate?) are part of Marr's concept of a computational-level theory.
1.3 Choosing the Tasks
A specification of the input/output relationship for a task can also be considered a definition of what constitutes a correct response for that task. This is clearly a foundational issue for any memory theory although it may appear trivial given the tasks we have chosen. It was so as to achieve near unanimous agreement about the goal of the task that we chose laboratory tasks as the second of our starting points. From the use of laboratory experiments memory researchers have learned, with considerable effort, that they cannot isolate current learning from previous learning. Nonsense syllables are not really nonsense and learning and/or retention and/or retrieval are all heavily influenced by the knowledge subjects bring to the laboratory. In what is probably a related finding, a naive subject will retain 80% of a recently acquired list over a 24 hour interval, but an experienced subject who has previously learned many other lists in the laboratory will retain only 20% over the same interval (Underwood, 1957). Some examples of the power of the human memory system come from list discrimination experiments where subjects can readily separate the information learned in two different lists(Anderson & Bower, 1972 ) and from transfer paradigms such as AB-ABr (McCullers, 1965) which is formally equivalent to an exclusive-or problem. In more recent work it has been shown that there are important differences between word and part-word cues (Nelson & McEvoy, 1979; Roediger, Weldon, Stadler, & Riegler, 1992) and that instructions to use a cue (e.g., a word or a part of a word) to recall a memory from a particular episode can produce a very different outcome from instructions to complete the part-word or to free associate to the word (Graf, Squire, & Mandler, 1984; Richardson-Klavehn & Bjork, 1988).
There have also been many insights about memory tasks. From a contemporary perspective these insights may seem obvious, but that was not true a few years earlier. Through the work of Murdock (1974), Norman (1966), and Norman and Wickelgren (1965) amongst others, memory researchers learned to distinguish between single item recognition, pair recognition, and recall. As we have already indicated, Tulving (1972) taught memory researchers to think differently about free associating to a cue and using it to recall a word that occurred in a specified list. Bain and Humphreys (1989) built on a substantial body of earlier work when they emphasized the role played by instructions about the relevant list or episode. In constructing our computational-level theory we propose a representation and a small set of computational primitives which suffice to specify the goals of a large number of tasks. This involves an interaction between the tasks chosen and the computational primitives proposed. As our ideas about the computational primitives became more definite, our choice of tasks changed to convey the role of the primitives more fully. Some insight into our preliminary thinking about the choice of tasks and primitives can be derived from the task analysis proposed by Humphreys et al. (1989b). We will also discuss the choice of computational primitives in section 3.1.
Some specific criteria for task selection were formulated as we proceeded with the construction of our theory. We decided to exclude tasks which involved multiple retrieval such as free recall and analogies. Our feeling was that once we had identified the basic retrieval functions we could then use them to construct theories for the multiple-retrieval tasks. Tasks were also excluded when they did not have clear inputs and goals. We only chose tasks where the test instructions specified the inputs and told the subject rather directly what to do. We thereby excluded tasks such as repetition priming in which the experimenter is investigating the effects of a prior study opportunity although the test instructions make no mention of this prior experience. This criterion also excluded tasks such as recall in response to an adjective and a noun, where the instructions do not inform subjects whether they should recall a word that is related to one cue, to both cues, or to the cues in combination. Finally, tasks were excluded where extra details about the decision process would have complicated the task specifications without illuminating the access processes. This criterion excluded forced choice item recognition.
2. A PARTIAL DESCRIPTION OF THE STRUCTURES AND PROCESSES INVOLVED IN MEMORY ACCESS
The issues to be discussed here include (1) notation, (2) specifying inputs and outputs, (3) data structures, (4) computational primitives and (5) functional specifications of the tasks.
2.1 Definitions
In Table 1 we present our notation and we define the inputs to memory tasks (contexts, relations, and words) and the outputs from the same tasks (words and decisions). We also define two data structures, M and L, and five functions (NotEmpty, Choose, Retrieve, Compatible, and Intersection) for accessing the information stored in those structures. These functions are the computational primitives for this level of the theory. They are primitives in the sense that they are computational mechanisms (or processes), they are limited in number, and all other functions are constructed out of these primitives. In introducing these primitives, we will describe a range of possible implementations in order to convey the basic concept.
----------------------------------------------------
Insert Table 1 about here
----------------------------------------------------
2.1.1 Inputs and outputs. The inputs to the memory tasks are sets of items. At times we will distinguish between contexts, relations, and words. The outputs from tasks such as recall and perceptual identification are singleton sets of items and the outputs from such tasks as recognition and lexical decision are decisions. At this level we represent these inputs and outputs as symbols or names (e.g., a context list, a relation isa, words a and b and decisions yes or no).
2.2 Data Structures
2.2.1 Relations, contexts, and words. The first data structure (M) contains bindings between items (relations, contexts, and words). In this notation, a binding is simply a set of items. We will argue that different types of bindings suffice for different tasks. We focus on two types of bindings in particular. The first is a pairwise binding linking two items {x,y}. The second is a 3-way binding. We are concerned with two examples of 3-way bindings. The first links a context and a pair of words {list,a,b}. The second links two words and a relationship {relation, a, b}.
In representing a 3-way binding in this fashion we intend to allow any solution to the problem of binding three elements provided that it preserves the identity of the individual components. For example, some solutions to the context binding problem derived from models of memory which assume the separate storage of memories include: (a) assignment of a unique identifier to every pair of items in a list (Anderson, 1983), (b) storing features derived from the context and from both items in a separate memory for every occurrence of a pair of items in a context (Flexser & Tulving, 1978), and (c) storing a unique image for every occurrence of a pair of items in a context (Raaijmakers & Shiffrin, 1981). Other examples, derived from models of memory which assume that memories are superimposed, include: (a) using the tensor product of the three vectors which represent the context and the two items (Humphreys, et al., 1989b), b) using the convolution of the same three vectors (Weber & Murdock, 1989), and c) multiplying the activation values of the context and the items to form a unique representation of the pair of items in that context (Sloman & Rumelhart, 1992). Anderson and Bower's (1973) use of labelled associations is an example of a 3-way binding between a relation and a pair of words.
In including context in our data structure we are simply providing a language for specifying that some tasks require the use of information about the study list or episode. Context is often reified as a tag (Anderson & Bower, 1972) or a cue (Humphreys, et al., 1989b). The context required for short-term memory paradigms could also be implemented as a special structure in which the last list is stored along with processes which direct when the memory system should or should not use that structure. Nor is context necessarily a unitary construct.
2.2.2 Perceptual Stimuli and Words. The second data structure (L) consists of bindings between perceptual stimuli and the representations of the words in the data structure M. Our intention is to provide a language in which we can differentiate between bindings between physical stimuli and words and bindings between words. There is also a physical input when the experimenter reinstates a context by reminding subjects of the list they learned last week or asks them to recall a word which is in a particular relationship with another word. We do not attempt to provide a language for discussing these physical inputs, however, because we do not have a theory of how physical and conceptual inputs combine to reinstate contexts and to specify relations.
2.3 Computational Primitives
As we mentioned above, the computational primitives are processes that form the basis for all memory operations. Like the basic instruction set of a computer, they can be combined in many ways to produce more complex functions.
2.3.1 Is the Output a Word or a Decision? The first two functions are NotEmpty and Choose. These are used to differentiate between tasks which require a decision as an output (recognition, and lexical decision) and those which require a word as an output (recall and perceptual identification). NotEmpty is a function used for making decisions. It takes a set as an input and outputs yes if the input set is not empty and no if it is empty. Choose takes a set as an input and if the input set is not empty it outputs one element of the input set. The Choose and NotEmpty functions could be implemented as a series of search and decision operations that might be describable in a flowchart. In Chappell and Humphreys (1994) they are implemented in a single settling of an artificial neural network.
The Choose and NotEmpty functions are logically required if we are going to map inputs onto outputs. That is, they are an essential part of a definition of what constitutes a correct response. In our formal system, they are also defined very generally. For example, the Choose function indicates that the output must be an element of the input set, but not how that element is selected. When defined in this very general way these functions simply serve as a reminder that a model is incomplete until a solution to the problem of producing an output has been proposed. Such a reminder has at times been needed. For example, Tulving required some persuasion before he acknowledged that recognition and recall would require different conversion operations (Tulving, 1983). It should also serve as a reminder that neurophysiological explanations of memory are not complete until an explanation as to how a response is made is provided.
2.3.2 Retrieval from M. Elements that have been stored in the data structure M can be retrieved in several ways, depending on the number and type of cues available. The Retrieve function accepts sets (either contexts LIST, relations RELATION, words A, or a combination) and the data structure M as inputs. An important distinction is whether the input set is a set of singleton sets or a set of higher order sets such as doubletons. For example, if the input consists of sets of doubleton sets ( e.g., a context and word cue, LISTxA) the output of the Retrieve function will be the set of all items which occur in a binding with an instance of the context set and an instance of the cue set. If the input consists of a set of singleton sets the output of the Retrieve function will be the set of all items which occur in a binding with an element of the input set. Note that if the input set contains a context list, and the binding {list,a,b} is in memory, both a and b will be in the output. Similarly, if the input set contains a word a, and the binding {list,a,b} is in memory, then both list and b will be in the output. Our primary concern was to retrieve the components in a 3-way binding ({list,a,b}) by cuing with a pair of cues ({list,a}) or with any of the component cues (list or a).
By allowing the input to be a multi item set, we can accommodate the situation where the instructions do not differentiate between two or more contexts. The use of multi item sets is also inherent in the use of superimposed memories and we wished to allow for this possibility (van Gelder, 1991).
2.3.3 Going from a perceptual stimulus to a word. The Compatible function takes a set of perceptual stimuli P and the data structure L as inputs, and outputs a set of words. The output is the set of words that are bound to any of the perceptual stimuli in P. When the physical stimulus is an intact word the output should consist of a singleton set (i.e., the word itself). When the input is a word stem or ending the output should be the set of all words in the subject's vocabulary that share that stem or ending. We would also expect the outcome to contain more than one word when the input is a physically degraded stimulus. It is also possible, even when a word fragment uniquely specifies a word, that the functional stimulus will be a portion of the fragment. Under these conditions the Compatible function could still produce a multi item set. The reasons for having sets of perceptual stimuli as potential inputs (rather than individual stimuli) and sets of items as potential outputs are similar to the reasons given for the Retrieve function.
Tulving and Schacter's (1990) ideas about a perceptual representational system provide a starting point for one way to implement the Compatible function. In this approach the perceptual representational system would accept the physical input and transform it into a representation which could then be passed on to the memory system. Humphreys et al.'s (1989b) proposal that a distributed memory (an artificial neural network) maps peripheral codes onto central codes provides a starting point for a very different implementation in which an artificial neural net would be taught to map strings of graphemes onto memory representations. The Compatible function is then defined as the mapping between inputs and outputs produced by the trained network.
2.3.4 Intersecting two sets. The final computational primitive is
Intersection. This function finds the intersection of sets which are made available by the Retrieve and the Compatible functions. An intersection function is very common in memory theories though it is not always acknowledged that the proposed algorithm is computing an intersection. For example, searching a list to see whether a list member is related to a cue, or generating associates of a cue followed by an attempt to determine whether the generated instance was a member of the study list are implementations of an intersection function using search processes. These ideas are preserved in such contemporary theories as Jacoby and Hollingshead (1990) and Nelson, Schreiber, and McEvoy (1992). The SAM framework can also be used to compute an intersection (Humphreys, Wiles, & Bain, 1993; Raaijmakers & Shiffrin, 1981). The theories for semantic priming proposed by Becker (1980), Marslen-Wilson (1987), and Norris (1986) all involve the computation of an intersection between a set of items which are compatible with (elicited by) the physical stimulus and a set of items which are semantically related to the prime. Wiles, Humphreys, Bain, & Dennis (1991) have discussed a variety of ways to compute an intersection using artificial neural networks and Chappell and Humphreys (1994) have used the computation of an intersection in an artificial neural network as part of a model for single item recognition and cued recall.
2.4 Functional Specifications
The functional specifications for a task indicate its inputs and goal (the input/output relationship). The specification of the input/output relationship consists of the series of computational primitives that are required. Each of these is identified by an abbreviation of the task name. The functional specifications for the five episodic and five semantic tasks are given in Table 2.
---------------------------------------
Insert Table 2 about here
---------------------------------------
2.5 AB-ABr Learning
In AB-ABr learning subjects study two lists of pairs. The cue and the target terms are the same in list 2 as they were in list 1, but they are re-paired (e.g., the pairs in list 1 are pen book, cot pole, and top road, while the pairs in list 2 are pen pole, cot road, and top book). Subjects can be given the cue term and asked to recall either the list-1 or the list-2 target. The inputs required by the task AB-ABr are the context (information about which list is relevant), the perceptual stimulus (the cue), and the data structures L and M. The output is a word and the goal is to recall a word which was paired with that cue in that context. Our specification of the relationship between the inputs and output starts with the transformation of the perceptual stimulus into a representation of the cue. To do this, the Compatible function is applied to the perceptual stimulus. Since this stimulus is generally intact and is not degraded the output should be a singleton set (the representation of the cue). However, to increase the generality of our notation, in this and in all of the other tasks, we allow for the possibility that the inputs to and the outputs from these functions are multiitem sets.
One example of where this generality would be needed in AB-ABr learning is when the instructions do not differentiate between two or more contexts. The next step is to use the representation of the cue and the context to retrieve the target. This is accomplished by using the Retrieve function. The input to this function is a doubleton set, consisting of a context and a representation of the cue. The use of a doubleton set, as an input to the Retrieve function, provides the ability to utilize just the information stored in 3-way or higher order bindings. That is, the only items retrieved are those which ocur in a binding with both cues. Thus, the output from Retrieve is the set of all items which were paired with that cue in that context. Because more than one item may occur in the output of Retrieve, the Choose function is applied.
A 3-way binding between the context, the cue, and the target must be
present in some form in any algorithmic-level theory which performs AB-ABr learning. However, this does not mean that we must necessarily reify the concept of a 3-way binding. For example, consider the situation where a subject will study the pairs AB,CD in list 1 and AD,CB in list 2. Now, at the time of study, provide the subjects or encourage them to select mediators M1 for AB in list 1 and M2 for AD in list 2. Both M1 and M2 are preexisting associates of A. In addition, require B to be a preexisting associate of M1 and D to be a preexisting associate of M2. In addition, assume that M1 becomes associated with the list-1 context and M2 becomes associated with the list-2 context. To recall the list-1 target paired with A , first recall M1 by finding the intersection between the associates of A and the items (including mediators) which occurred in or during list 1. Then find the intersection between the associates of M1 and the items which occurred in or during list 1. The preexisting pairwise associations along with the sequence of retrievals produces a 3-way binding between the context, the cue, and the target, but the 3-way binding is not directly represented in the memory structure M.
2.6 List Specific Pair Recognition
In list specific pair recognition (LSPR), the subject studies at least two lists of pairs. After each list the subject can be asked to discriminate between the pairs which occurred in that list and pairs which did not occur in that list (e.g., a pair from a previous list or a pair formed from two words which were studied in different pairs in the current list) or to recognize pairs which occurred in the earlier lists. The inputs to this task are the context, the two perceptual stimuli, and the data structures L and M. The goal is to say yes if the pair occurred in the context specified by the instructions. We have provided two specifications of the relationship between the inputs and the output. It is possible that one of these actually describes how the task is performed. If so it should be possible to distinguish empirically between these alternatives. The existence of alternative specifications may also indicate that the task is capable of being performed in different ways.
The first specification of the relationship between the inputs and the output starts with the application of the Compatible function to both perceptual stimuli. This produces representations of the two words in the test pair. Then the doubleton set consisting of the context plus one of the cue terms serves as the input to the Retrieve function. The output is the set of all items which occur in a binding with both the context and the cue. The output set is then intersected with the representation of the other member of the test pair. Because a decision is required, the NotEmpty function is applied. In addition, we have specified that either member of the test pair may be teamed with the context to serve as the input to the Retrieve function.
The second specification of the relationship between the inputs and the output also starts with the application of the Compatible function to the perceptual inputs. Then the doubleton set consisting of the representations of the two cues serves as the input to the Retrieve function. The output is the set of all items (this includes contexts) which occur in a binding with both cues. The output of the Retrieve function is then intersected with the set of contexts and the NotEmpty function is applied. In the first specification we used one pair member and the context to retrieve the other pair member. In the other we used the two members of a pair to retrieve the context.
2.7 Cued Recall with an Extralist Associate
In cued recall with an extralist associate (CREA) subjects study lists of single words and are then given preexisting associates of the studied words to serve as recall cues (e.g., the subject has studied the word chair in a list and is then given the word table, a word which elicits chair in free association, as a cue). The inputs to CREA are the same as the inputs to AB-ABr, the output is a single word, and the goal is to recall the word which occurred in the context and is related to the cue. Thus the goal differs between CREA and AB-ABr.
Our specification of the relationship between the inputs and the output starts with the application of the Retrieve function to the context. The output is the set of all items which are bound to the context. This set of items is then intersected with the set which has been produced by first applying the Compatible function to the perceptual stimulus and then applying the Retrieve function. The Compatible function produces the set of items which are bound to the perceptual stimulus. In practice, the output should be a singleton set because the cue is intact and not degraded. The application of the Retrieve function then produces the set of items which are bound to the cue in any context or relation and we then find the intersection between the set of items which are bound to the context and the set of items which are bound to the cue. In other words, we retrieve all the items in a list and then take the intersection of that set and the set of all the items associated with the cue. Since the intersection may contain more than one item, the Choose function is applied.
CREA does not require a 3-way binding. Instead, it can utilize pairwise bindings to find the intersection between two sets. However, it is possible to find the intersection by using a 3-way binding. That is, it has been suggested that subjects implicitly generate the cue while studying the target (Raaijmakers & Shiffrin, 1981). If a 3-way binding linking the target, the implicitly generated cue, and the context is stored, and if humans possess the appropriate retrieval mechanism then this mechanism could be used to retrieve the item which was in the list and was associated with the cue. The point here is that when we characterize the computation as an intersection we are describing the function not the mechanism. This function can be computed via general purpose mechanisms (search and decision processes), via a specialized mechanism (a direct access intersection), or by the "fine tuning" of processes that are normally used to compute another function.
2.8 Cued Recall with a Partword Cue
In cued recall with a partword cue (CRPWC ) subjects study a list of words and are then given part of a word (a stem, ending, or fragment) to serve as a recall cue for one of the words. The inputs to the CRPWC task are the same as for the two previous cued recall tasks and the output is also a single word. The goal of the task is to complete the cue with a word which was in the list. In the two previous tasks, the perceptual stimulus is intact and nondegraded so in general the output of the Compatible function will be a singleton set. In CRPWC, the perceptual stimulus is part of a word and we would expect the output of the Compatible function to be a multi item set (all the words which can be created by completing the partword cue). In addition to applying the Compatible function to the perceptual stimulus, the Retrieve function is applied to the context. The output is the set of all items which are bound to the context. This set of items is then intersected with the set which has been produced by applying the Compatible function to the perceptual stimulus. Again, there may be more than one item in the intersection of these two sets so the Choose function is used.
2.9 List Specific Item Recognition
In list specific item recognition (LSIR) subjects study more than one list of words. After each list they can be asked to discriminate between the words which did or did not occur on that list and those which did and did not occur in a prior list. The inputs to the LSIR task are the same as in the three previous recall tasks, consisting of the context, the perceptual stimulus, and the data structures M and L. The output is a decision and the goal is to determine whether a test item occurred in the specified list. As with LSPR, we present two alternative specifications for the task. Again, the existence of alternative specifications may be taken as hypotheses as to how the task is actually performed or it may indicate that different subjects perform the task in different ways.
In the first specification the Retrieve function is applied to the context. The output will be the set of items which occurred in that context. This set is then intersected with the set of items which are bound to the perceptual stimulus in L. Since this will generally be a singleton set in practice we would expect far less noise in the LSIR task than in the CRPWC task. The NotEmpty function is then applied to the set of items in the intersection. In this specification, LSIR differs from CRPWC only in the application of this last function (NotEmpty vs. Choose) and in the differences introduced by having an intact-nondegraded perceptual stimulus as opposed to a partword perceptual stimulus. It differs from CREA in the application of the last function and in how the output of the Compatible function is treated. In CREA the Retrieve function is applied to the output of the Compatible function before the result is intersected with the set of items produced by the context cue (the study list). The intent of this sequence (Compatible first followed by Retrieve) is to produce the set of items associated with the cue). In LSIR, the output of the Compatible function receives no further processing before the intersection operation. The intent of this is simply to produce a representation of the cue.
In the second specification, the Compatible function is applied to the perceptual stimulus. The output of this function then serves as the input to the Retrieve function. The output from this function is the set of all items (including contexts) which occur in a binding with the cue. This output is then intersected with the context or contexts specified by the instructions. The difference between these two specifications is that in the first the context is used to retrieve the words in the study list and in the second the test cue is used to retrieve the contexts in which it has occurred.
2.10 Relational Retrieval
In relational retrieval (RR), a subject is asked to recall to a word and a relationship cue ("What is the antonym of hot?"). The inputs to the RR task are the perceptual stimulus corresponding to the cue, the relationship, and the data structures L and M. The goal is to produce a word which is in the specified relationship to the cue.
Our specification of the relationship between the inputs and the outputs starts with the Compatible function. The inputs to this function are the perceptual stimulus P and the data structure L. The output is the set of all words which are compatible with one of the elements of P. Since P is generally a singleton set, this will simply be a representation of the cue. Next the Retrieve function is applied. The inputs to this function are a set of doubleton sets and the memory structure M. Each of the doubleton sets consists of a word and a relation. The output of the Retrieve function is the set of words which occur in a binding with both a word and a relation. Because more than one word may occur in the output of this function the Choose function is applied.
2.11 Perceptual Identification
In perceptual identification (PID), a degraded physical stimulus which corresponds to a word is presented and the subject is asked to identify which word has been presented. The inputs to the PID task are the target perceptual stimulus P and the data structures M and L. The goal of the task is to produce an instance of a word which is compatible with the perceptual stimulus of the target.
Our specification of the relationship between the inputs and output starts with the formation of a doubleton set consisting of {wordxisa}. This doubleton set along with the memory structure M serves as the input to the Retrieve function. The output is the set of all words "known" to the subject (the contents of the subject's "lexicon"). This set is then intersected with the set produced by applying the Compatible function to the target perceptual stimulus P. Since the target perceptual stimulus is degraded the output may contain more than one representation. Because the intersection may contain more than one item the Choose function is applied.
Although we have specified that the Retrieve function is used to retrieve the set of all words there is no necessity to think of this as involving the same kind of access operations as are involved in retrieving a taxonomic category. In fact, the most common way to implement the retrieval of the set of all words in perceptual identification and lexical decision is to assume a separate mental lexicon and a process which allows the subject to consult this lexicon. Our specification of an involvement of a knowledge of the expected output (words) in the access process merely serves as a reminder that any algorithmic-level theory must include mechanisms/processes to insure that the output is a word and not something else (e.g., a number or nonsense word). Of course, in a direct access intersection model it is possible that the mechanisms/processes involved in accessing the set of all words are the same as those involved in accessing a taxonomic category. That is, the concept of a mental lexicon reflects a functional requirement, but it does not have to be reified.
2.12 Lexical Decision
In lexical decision (LD) a string of graphemes or phonemes is presented (the target) and the subject is asked to make a decision about whether or not the target is a word. The inputs to the LD task are the target perceptual stimulus P and the data structures M and L. The goal of the task is to say yes if the target is in the set of all words "known" to the subject and no otherwise. In the specification, the doubleton set consisting of wordxisa is formed. This doubleton set along with the memory structure M serves as the input to the Retrieve function. The output is the set of all words "known" to the subject. This set is then intersected with the set produced by applying the Compatible function to the target perceptual stimulus P. LD differs from PID in that the target perceptual stimulus is intact and nondegraded. Thus we would generally expect that the output of the Compatible function would be a singleton set. The final step is to apply the NotEmpty function to the intersection.
2.13 Combining Semantic and Rime Information
In combining semantic and rime information (CSRI), the subject answers questions such as "What is the name of a mythological being which rhymes with ost?"(Rubin and Wallace, 1989). The inputs are two perceptual stimuli corresponding to the lexical item which is the category name P and the rime information Q, and the data structures L and M. The output is a word and the goal is to produce a word which is compatible with the physical stimulus and is a member of the category. The specification of the input/output relationship starts with the application of the Compatible function to the perceptual stimulus corresponding to the cue and to the data structure L. Then a doubleton set is formed consisting of the output of the Compatible function and the relation isa. This doubleton set then serves as the input to the Retrieve function. This produces the set of all items which are instances of that category. Then the Compatible function is applied to the perceptual stimulus corresponding to the rime information. This produces the set of all words which are bound to that perceptual stimulus in the data structure L. The next step is to take the intersection of these two sets. The final step is to apply the Choose function to select a word from the intersection.
2.14 Judging Prime Target Similarity
In the task of judging prime target similarity (JPTS) the prime is badly degraded and the subject has to say whether the prime and the target are the same (Bernstein & Welch, 1991). The inputs to this task are the perceptual stimuli corresponding to the prime and the target and the data structure L. The output is a decision and the goal of the computation is to say yes if the target is the same as the prime. The specifications for the task start with the application of the Compatible function to the two perceptual stimuli. Since the prime perceptual stimulus is badly degraded the output is expected to be a multi item set. However, the target is intact and non-degraded so the output is likely to be a singleton set. Next, the Intersection function is used to find the intersection between the two sets. Finally the, NotEmpty function is applied to make a decision.
3 Selecting the Data Structures and Primitives and Extending the Specifications
In this section, we will first discuss the selection of the data structures and computational primitives. In doing this, we acknowledge that some arbitrary choices had to be made. Nevertheless, we argue that the assumption that human memory is associative in conjunction with the 10 tasks we have chosen provide substantial constraints on possible computational primitives. We then briefly discuss how we could extend our specifications to other tasks. In doing this, we also acknowledge that we will have to slightly modify our decision functions (Choose and NotEmpty) and introduce new kinds of items (e.g., images). Nevertheless, it appears that our access processes will suffice to explain the input/output mapping for a very large number of tasks.
3.1 Selecting the Data Structures and Access Processes
The data structure M together with the Retrieve function constitutes a generic associative memory. Although it is not possible to prove that human and/or animal memories are associative it is possible to argue that associative ideas have been far more productive than other approaches. This productivity is the reason we started with an associative memory. The most important consequence of our assumption that memory is associative is that we specify that items, not bindings (traces), are retrieved. We also chose to represent bindings as unordered rather than ordered sets. This choice simplifies the notation for the tasks we have considered, but it provides some constraints on how we can represent the access to ordered lists. However, it does not seem to have any other important consequences.
There are some other features of our associative memory which are not arbitrary. Our analyses of AB-ABr learning and relational recall constitute arguments for the need to include higher order (at least 3-way) bindings in human associative memory. We also allowed retrieval from these higher order bindings given any non- empty subset of cues. Humphreys, et al. (1989b) argued that using a single cue to retrieve information stored in 3-way bindings was necessary in order to generalize across episodic memories. It is also necessary in order to recognize a single item after studying pairs of items. Allowing retrieval to any nonempty subset is simply a generalization of these arguments. Allowing multi item sets to potentially serve as inputs and outputs is also an attempt to specify as general a memory as possible.
In spite of its generality, the Retrieve function will not suffice if two cues are required and if those cues only enter into pairwise bindings with the target. Because in cued recall with an extralist associate a 3-way binding may not be available (the cue is not studied with that target in that setting) and because the calculation of an intersection is so common in models of episodic and lexical access, we proposed an Intersection function as a supplement to the Retrieve function. In addition, a Compatible function is a logical requirement of any theory of episodic or lexical access. That is, there must be some mechanism or process that transforms the physical stimulus into a memorial representation. However, it is only in recent years that there have been suggestions that the processes/mechanisms needed to implement a Compatible function would play a relatively direct role in episodic memory. For example, Humphreys et al. (1989b; Wiles & Humphreys, 1993) suggested that weight changes in a neural network mapping peripheral modality specific representations onto central representations were responsible for the modality effects in both direct and indirect retrieval tasks. Roediger, et al.'s (1992) explanation for the same effects in terms of a match between the processing operations employed at study and test also seems consistent with our Compatible function.
Issues of parsimony, however, were more important than the arguments put forward by Humphreys et al. (1993) and Roediger et al. (1992). Given that a Compatible function is a logical necessity and given an Intersection function and a Retrieve function there is no need to postulate any further access process. In addition, we believe that the proposed specifications are a simple and plausible way to utilize the three access processes in order to map inputs onto outputs. There is, of course, a need for decision functions, but the ones we have proposed (Choose and NotEmpty) are somewhat arbitrary and will undergo modification in new applications.
3.2 Extending the Specifications to New Tasks
We first consider analogy, which is an example of the kind of multiple-retrieval task we excluded from our original pool of tasks. Then, we examine picture naming which requires us to postulate bindings between a perceptual stimulus and an image and between an image and a label. Finally, we examine animal recognition which requires a slight modification to our decision functions.
Halford et al. (in press) have proposed a theory for analogies using a tensor product framework. Wiles et al. (in press) have shown that this is the same mathematical formalism as used by Humphreys et al. (1989b). Since our computational-level theory was designed to be consistent with the Humphreys et al theory, amongst other theories, it is not surprising that the Halford et al. theory is also consistent with our data structures and computational primitives. We will illustrate the use of these primitives by describing how we would solve an analogy of the form "Man is to house as dog is to what?" (man:house::dog: ? ).
We assume that 3-way bindings containing two arguments and a relation (e.g., LIVES (man, house), BUILDS(man, house), etc) are stored in the data structure, M. In Halford et al's case, M is a rank 3 tensor. The first inputs to the Retrieve function will be the doubleton set {manxhouse}. The output will be the set of all relationships between man and house. The next input to the Retrieve function will be a set of doubleton sets ({RELATIONSHIPxdog}). This time the output will be a set of items which are in the same relationship to dog as house is to man. The Choose function is then applied to produce a unique item, which completes the mapping. In picture naming we assume that there is a need to differentiate between the representation of a picture and the label that is commonly applied to that picture. However, we do not want to assume that these are necessarily different forms of representation. We do this by assuming bindings between images and labels in the data structure, M and between physical stimuli and images in the data structure, L. To name a picture we apply the Compatible function to the physical input. This produces the image or possibly a set of images (e.g., the physical stimulus may have been degraded). The image then serves as the input to the Retrieve function and the output is the label or possibly a set of labels. At this point we have a choice. If we assume that information about the required response is not playing a functional role we can simply apply the Choose function. However, in perceptual identification we assumed that information about the required output (a word) was playing a functional role. If we made the comparable assumption in picture naming we would retrieve the set of all picture names. We would then take the intersection between the set of labels produced by the physical stimulus and the set of all picture names and then apply the Choose function. These alternative specifications are not the result of ambiguity in our data structures and computational primitives but rather are inherent in the task itself (or possibly, our understanding of the task).
It has been suggested that monkeys, amongst other animals, can learn to approach or avoid whenever they encounter a familiar (previously encountered) stimulus (Gaffan, 1974; Humphreys, Bain, & Burt, 1989). To accommodate this kind of task we have to modify the NotEmpty function so that it produces an internal recognize (the set is not empty) or notrecognize (the set is empty) memory state. We would then attach the approach or avoidance response to this internal recognize or notrecognize memory state. To be more specific, we will describe the sequence of functions required if the animal is to approach a stimulus that has been encountered in any situation. Humphreys et al. (1989a) referred to this task as generic recognition as opposed to list specific recognition.
We assume that there is a binding between the approach response and the recognize memory state and/or between the avoidance response and the notrecognize memory state. Furthermore, we assume that there is a binding between the physical stimulus and a memorial representation for items that have previously been encountered, but that there are no bindings for items which have not previously been encountered. When a physical stimulus is encountered the Compatible function is applied. If this stimulus has been previously encountered the output will be an element of M. If the stimulus has not been previously encountered the output will be the empty set. Then, the modified NotEmpty function is applied. If a memorial representation exists, the output will be recognize. If a memorial representation does not exist, the output will be notrecognize. This output is then used as the input to the Retrieve function, the output of which will be an approach or avoidance response.
4 Applications to Theory and Research in Human Memory
As we have already shown, the theory serves to clarify several
contentious issues. These include the binding problem in episodic memory, the role of input pathways in both episodic and semantic (lexical) memory, the importance of information about the study list or episode in episodic memory, the role of the mental lexicon in perceptual identification and lexical access, and the ubiquitous calculation of an intersection in theories of episodic and lexical access. Our preliminary extension to animal memory also suggests that it may be possible to describe human and animal tasks in the same terms. A common way of describing these tasks would seem to be a prerequisite if we are going to have animal models of human amnesias and other disorders.
In addition, the theory provides what can be described as weak constraints. When these are used in conjunction with other weak constraints such as Feldman and Ballard's (1982) 100 step rule and constraints derived from studies of the localization of brain function, the result can be a strong constraint on potential algorithmic-level theories. An example of the possibility of combining weak constraints is presented in 4.1.
Our computational-level theory also produces a multidimensional classification of these memory tasks. This classification can be used to ask such questions as whether a similar computational requirement implies similar retrieval dynamics or similar neurological underpinnings. The principle reason we believe that our classification will be useful in this regard is that it already subsumes two of the most popular classifications. Our distinction between tasks where an episodically defined input set is playing a functional role, and tasks where it does not, divides tasks along the same lines as does Graf and Schacter's (1985) distinction between implicit and explicit memory tasks. Similarly, our analysis of where the Compatible function would have an effect on performance (the use of a partword or degraded word as a cue) corresponds to tasks which have been assumed to be heavily reliant on a match between perceptual processing at study and test (Jacoby, 1983; Roediger et al., 1992). In addition, we distinguish between explicit conceptual tasks which require a 3-way binding (AB-ABr learning, and list specific pair recognition) and explicit conceptual tasks which do not (cued recall with an extralist associate and single item recognition). There are differences between these tasks (Humphreys, et al., 1989b, 1993) and there is some evidence that the tasks which require a 3-way binding are especially difficult for amnesics and animals with hippocampal lesions to learn (Humphreys, et al., 1989a; Sutherland & Ruddy, 1989). We will provide an example where our task analysis suggests new experiments not suggested by traditional thinking (4.1).
At times our computational-level theory suggests mechanistic explanations for human performance. Although we intended the theory to be used in this fashion, it should not be assumed that the mechanistic explanation is part of the computational- level theory. Mechanistic explanations which appear to emerge from our computational-level theory are actually generalizations over plausible implementations. A valid generalization of this kind would be highly desirable, but the assumptions need to be made explicit. In 4.2 and 4.3 we will illustrate the problems involved in formulating this kind of broad generalization.
We then turn to the question of whether our theory is falsifiable. We note that a computational theory is a theory of the task, not a performance theory. Strictly speaking, it cannot be falsified by behavioral or neuropsychological data. However, it is possible to propose specific hypotheses about the computational primitives, and these hypotheses are falsifiable by such data. At times this gap between task component and memory component may seem negligible or easily ignored, but it is there and cannot be discounted. In addition, when specifications for new tasks are proposed, testable questions may emerge. Finally, the utility of the multidimensional task classification that our specifications produce can also be assessed.
4.1 Extending a Neuropsychological Investigation of List Specific Item Recognition
Parkin, Leng, and Hunkin (1990) compared the performance of diencephalic and temporal lobe amnesics on a list specific item recognition task using short lists and short retention intervals. On the first list, subjects studied pictures from a larger set and were then given a test in which they had to discriminate between presented and nonpresented pictures. On subsequent tests a new study list was formed by randomly sampling from the set of pictures. Again, subjects were asked to discriminate between the pictures studied on the most recent list and all other pictures. Both groups performed at near ceiling levels on the first list. However, on the remaining lists the diencephalic amnesics were not as accurate as were the temporal lobe amnesics. The interchange between targets and distractors from list to list largely rules out a non- contextual strength component such as familiarity (Mandler, 1980) or perceptual fluency (Jacoby & Dallas, 1981). Instead, the relatively better performance of the temporal lobe amnesics suggests that they had some ability to use information about list membership in this situation.
Given these results, the question a neuropsychologist faces is what task or tasks will provide additional information about the similarities and differences between these two groups of amnesics. The distinctions between implicit and explicit memory and between data driven and conceptually driven processing are silent on this issue because they do not address the list-specific tasks. In contrast, our task analysis suggests that list specific item recognition is similar to cued recall with an extralist associate and with a partword cue. Furthermore, the analysis suggests that AB-ABr learning and list- specific pair recognition are different, in that they require a 3-way binding. One problem in applying our computational-level theory in this fashion is that alternative specifications are possible for list specific item recognition. In the two specifications provided, a single cue, either context or item, served as the input to the Retrieve function. If we assume that traces, not items, are retrieved, another alternative is possible. That is, the retrieval of a binding, using some or all of the cues present in that binding, is implicit in theories in which memory traces are retrieved (e.g., Flexser & Tulving, 1978). In such a theory the retrieval of a 2-way binding using both elements of the binding (list specific item recognition) appears to be very similar to the retrieval of a 3-way binding using two elements from that binding (AB-ABr learning). These assumptions about trace access probably lie behind intuitions that item recognition and paired associate learning should be affected similarly in human amnesias.
We can think of these alternative specifications as alternative hints about algorithmic-level mechanisms. A comparison of performance between diencephalic and temporal lobe amnesics on the suggested tasks should also provide hints about algorithmic-level mechanisms. When results from the neuropsychological investigation are combined with our analysis of alternative task specifications, the result may be a strong constraint on theories of human memory.
4.2 The Encoding Specificity Principle
The encoding specificity principle is an attempt to make a general algorithmic- level statement about the access process. Although it is not specifically acknowledged, the 1973 version seems to assume a specific form of representation: we assume that what is stored about the occurrence of a word in an experimental list is information about the specific encoding of that word in that context in that situation. This information may or may not include the relation the target has with some other word in the semantic system. If it does, that other word may be an effective retrieval cue. If it does not, the other word cannot provide access to the stored information because its relation to the target word is not stored" (Tulving & Thomson, 1973, p. 359). In contrast, the 1983 version appears to be an attempt to characterize the access process independently of the representation of the inputs. "We could now say that recollection of an event, or a certain aspect of it, occurs if and only if properties of the trace of the event are sufficiently similar to the properties of the retrieval information" (Tulving, 1983, p. 223).
Our task analysis is not a general algorithmic-level statement, but it does provide a starting point for the making of such statements. That is, it tells us that there are three different kinds of retrieval tasks in episodic memory. AB-ABr learning requires a 3- way binding. Cued recall with an extralist associate does not require a 3-way binding because it can utilize pairwise bindings between cues and their associates and context and the study list. To use these pairwise bindings would also require the ability to compute an intersection between two sets. List-specific item recognition can use an intersection and the ability to take a physical stimulus and elicit a representation of the target.
We have directly implemented this task analysis in our attempts to model human memory using artificial neural networks with distributed representations. In doing this, we have proposed that three distinct retrieval processes correspond to these three different kinds of tasks. One process utilizes a 3-way binding between context, the cue, and the target (Humphreys, et. al. 1989b). A second process is parasitic on the recognition process (Chappell & Humphreys, 1994). In this model, the target word elicits its representation and the context cue elicits the representations of all the list items. An intersection between these two sets is computed and the NotEmpty and Choose functions are implemented by the convergence process in an auto-associative memory. Generally, the auto-associative memory will converge to the target word (a yes decision) or to a null state where there are no active units (a no decision). However, if a word in the list is similar to, but not identical with, the target, the auto- associative memory may converge to the list word instead of the target. The third process utilizes pairwise bindings between a cue and its associates and between context and the list items (Chappell & Humphreys, in press; Humphreys, et al, 1993). The cue elicits a composite representation of the words associated with it and the context elicits a composite representation of the list items. The intersection between these two sets is then computed.
What our task analysis does not tell us is: (a) Whether there is a specialized retrieval process for utilizing a 3-way binding; (b) Whether cued recall with an extralist associate is solved by an intersection mechanism or by the "fine tuning" of some other kind of mechanism; (c) whether if an intersection mechanism is involved, it is a search or direct access process; or (d) whether a target in recognition can really retrieve a similar word. However, the task analysis does provide us with a well defined starting point in our attempt to come to these kind of general conclusions.
In contrast, the encoding specificity principle does not provide a well defined starting point. A direct access intersection using pairwise bindings appears to be incompatible with the 1973 version. An intersection using a search process (generate recognize), however, may not be incompatible with the 1973 version. In addition, the direct access intersection may or may not be incompatible with the 1983 version. In our opinion, both versions of the encoding specificity principle have appealed to researchers and theorists who have shared Tulving's implicit assumptions about representation/process. That is, the encoding specificity principle in conjunction with these shared assumptions constrains possible mechanisms. Without these shared assumptions, however, it provides very little constraint on possible mechanisms. It should thus be regarded as either a very weak generalization about plausible algorithmic-level mechanisms or as a specific algorithmic-level proposal. Furthermore, to be really useful in the latter role the implicit assumptions would have to be made explicit.
4.3 Do List Length and Cue Set Size Effects Follow from the Intersection of Multiitem Sets?
We have specified that cued recall with an extralist associate involves the computation of an intersection between the associates of the list and the items in the study list. Empirical results show that cued recall decreases with increases in the number of studied items, the list-length effect (Watkins, 1981), and with the number of associates of a cue, the cue-set-size effect (Nelson, et al., 1992). Given these results, it is tempting to conclude that the list-length and cue-set-size effects are a direct consequence of the need to intersect multi item sets. Such a conclusion would be very powerful and useful, but it is not an implication of the computational-level theory. Instead, it represents a generalization over all plausible ways of computing an intersection between multi item sets.
In our opinion, such a generalization is plausible, but we have found it difficult to construct a compelling argument. Nevertheless, the nature of the argument that is needed is known. We can examine specific implementations to see whether increases in set size increase the amount of noise in the intersection. We should also be able to recognize a counterexample if one is produced. In this case, the computational-level theory is serving as the foundation on which to construct the kind of broad characterization of algorithmic-level mechanisms Tulving attempted in his formulation of the encoding specificity principle.
4.4 Invalidating a Computational Level Theory
A computational-level theory is a theory or specification of the task, not a performance theory. As such ,it cannot be invalidated by trying to derive a performance prediction and comparing that prediction to data. In addition, a computational-level theory cannot be invalidated by showing that alternative primitives could have been used. To invalidate our theory would require an argument showing that either the goals of the tasks are wrong, our identification of inputs and outputs is wrong, or our computational primitives do not serve to map the inputs onto the outputs. The formal language used in our theory allows others to verify that our primitives serve to map the inputs onto the outputs. In addition, as we have indicated, we chose tasks where the instructions clearly specified the inputs and directed the subject as to how they should be used. This was designed to insure that there would be widespread agreement about the inputs and goals.
When we propose specifications for new tasks where the input/output mapping is not as clear, we frequently have a testable question. For example, the proposal that information about the nature of the output required (e.g., "The stimuli are all pictures of common objects.") is playing a functional role in picture naming is testable. All that is required is a comparison between a pure list (all of the degraded stimuli are easily nameable pictures) and a mixed list (e.g., some of the degraded stimuli are easily named symbols or traffic signs). If performance is better with a pure list than with a mixed list then there is reason to believe that information about the nature of the output is playing a role.
It is also possible to propose specific falsifiable hypotheses about the computational primitives. These include: (a) The processes/mechanisms used to implement the Compatible function play a relatively direct role in memory access. (b) The memory access process in cued recall with an extralist associate differs from the memory access process in AB-ABr learning. (c) With respect to retrieval dynamics and brain localization, list specific item recognition is more similar to cued recall with a partword cue than it is similar to AB-ABr learning or list specific pair recognition. (d) The intersection process/mechanism in lexical access shares components with the intersection process/mechanism in episodic access.
More generally, our computational-level theory produces a multidimensional classification scheme for a large variety of tasks. As with other forms of classification, it is difficult to conclude that it is wrong, but it should be possible to conclude whether or not it is useful. One possibility is that the analysis of new tasks will require us to postulate a large number of new access processes. Another possibility is that we will decide that our computational primitives are too general to be of much help in illuminating the similarities and differences amongst memory tasks. In both of these cases we would conclude that the theory was not useful and should be discarded.
5 Applications to the Modelling of Higher Cognition
Clarification of contentious issues, weak constraints, suggestions for further experimentation, hints about mechanism, and the possibility of a common language to describe human and animal tasks are useful. Memory researchers and theorists may have hoped for something more, however. There is more, but it is not for the memory researcher and theorist. In constructing his theory, Marr started with a knowledge of the input representation, that is, the physics of light and the optics of the eye determine the representation on the retina. There are no comparable constraints on the inputs in memory or other areas of higher cognition. Without such constraints, we are forced to characterize the computation in very general terms. As a consequence, what we have produced is more of a formalization of previous insights than it is a novel reconceptualization of human memory.
What we have produced is a characterization of the functions computed by the human memory system. Furthermore, we have done it using a formal language instead of the ambiguous metaphorical terminology that is used so frequently in the memory literature. In addition, we have stripped away all the details about task and material variables that make the memory literature so difficult for the nonspecialist. As a result, any cognitive modeller who wishes to use human-like memory functions in a model of higher cognitive processes (e.g., analogies, reasoning, etc.) or in the construction of a robot can do so without having to be concerned with details about how humans implement these functions. That is, cognitive modellers can use the data structures and primitive operations specified in Table 1 instead of traditional computer based data structures and processes such as exact storage and search.
The following is a summary of the characteristics of the data structures and access processes we have proposed. Human memory is associative, but it operates over sets rather than unique items. The data structures can be characterized as sets of sets. A binding between items is a set of two or more items. The memory for a list of items would be a set of such sets. Memory storage takes the form of adding a set (i.e., a binding) to a memory structure. Access to information in memory is via five access/decision processes. (1) The set of words bound to a physical stimulus can be retrieved (Compatible). (2) The set of items bound to one or more other items can be retrieved (Retrieve). (3) The intersection between two sets can be computed (Intersection). (4) An element can be selected from a set (Choose). (5) A decision about whether a set is empty can be made (NotEmpty). An essential feature of all of these primitives is that they take as input sets of items and, with the exception of the last two, they can produce multi item sets.
The data structures and access processes we have proposed are different from the data structures and access processes assumed in traditional models of artificial intelligence and cognitive psychology. Their inclusion in a model of higher cognition will shift the boundary between cognition and memory and produce different kinds of cognitive theories.
Anderson, J. R. (1983). The architecture of cognition. Cambridge MA: Harvard University Press
Anderson, J. R. & Bower, G. H. (1972). Recognition and retrieval processes in free recall. Psychological Review, 79, 97-123.
Anderson, J. R. & Bower, G. H. (1973). Human associative memory Washington D. C.: V. H. Winston & Sons
Anderson, J. R. & Milson, R. (1989). Human memory: An adaptive perspective. Psychological Review, 96, 703-720.
Bain, J.D., & Humphreys, M.S. (1989). Instructional reinstatement of context: The forgotten prerequisite. In K. McConkey and A. Bennett (Eds.), Proceedings of the XXIV International Congress of Psychology, Vol. 3. Elsevier.
Becker, C. A. (1980). Semantic context effects in visual word recognition: An analysis of semantic strategies. Memory & Cognition, 8, 493-512.
Bernstein, I. H. & Welch, K. R. (1991). Awareness, false recognition, and the Jacoby-Whitehouse effect. Journal of Experimental Psychology: General, 120, 324-328.
Chappell, M. & Humphreys, M. S. (1994). An auto-associative neural network for sparse representations: Analysis and application to models of recognition and cued recall. Psychological Review, 101, 103-128.
Feldman, J. A., & Ballard, D. H. (1982). Connectionist models and their properties. Cognitive Science, 6, 205-254.
Flexser, A. L. & Tulving, E. (1978). Retrieval independence in recognition and recall. Psychological Review, 85, 153-171.
Gaffan, D. (1974). Recognition impaired and association intact in the memory of monkeys after transection of the fornix. Journal of Comparative and Physiological Psychology, 86, 1100-1109.
Graf, P. & Schacter, D. (1985) Implicit and explicit memory for new associations in normal and amnesic subjects. Journal of Experimental Psychology: Learning, Memory, and Cognition, 11, 501-518.
Graf, P., Squire, L. R., & Mandler, G. (1984). The information that amnesic patients do not forget. Journal of Experimental Psychology: Learning, Memory, and Cognition, 10, 164-178.
Halford, G. S., Wilson, W. H., Guo, J., Wiles, J., & Stewart, J. E. M. (in press). Connectionist implications for processing capacity limitations in analogies. In K. J.
Holyoak & J. Barnden (Eds.). Advances in connectionist and neural computation theory, Vol. 2. (ppxxx), Analogical Connections. Norwood, NJ: Ablex
Hintzman, D. L. (1986). Schema abstraction in a multiple trace memory model. Psychological Review, 93, 429-445.
Humphreys, M. S., Bain, J. D. & Burt, J. S. (1989a). Episodically unique and generalized memories: Applications to human and animal amnesics. In S.
Lewandowsky, J. C. Dunn & K. Kirsner (Eds.) Implicit memory: Theoretical Issues. (pp. 139-158).L. Erlbaum Associates: Hillsdale, NJ.
Humphreys, M. S., Bain, J. D. & Pike, R. (1989b). Different ways to cue a coherent memory system: A theory for episodic, semantic and procedural tasks. Psychological Review, 96, 208-233.
Humphreys, M. S., Wiles, J., & Bain, J. D. (1993) Memory retrieval with two cues: Think of intersecting sets. In D. E. Meyer and S. Kornblum (Eds.) Attention and Performance XIV: Synergies in Experimental Psychology, Artificial Intelligence, and Cognitive Neuropsychology--A Silver Jubilee (pp xxxx). Cambridge, MA: MIT Press.
Jacoby, L. L. (1983). Remembering the data: Analyzing interactive processes in reading, Journal of Verbal Learning and Verbal Behavior, 22, 485-508.
Jacoby, L. L. & Dallas, M. (1981). On the relationship between autobiographical memory and perceptual learning. Journal of Experimental Psychology: General, 110, 21-38.
Jacoby, L. L. & Hollingshead, A. (1990). toward a generate/recognize model of performance on direct and indirect tests of memory. Journal of Memory and Language, 29, 433-454.
Mandler, G. (1980). Recognizing: The judgment of previous occurrence. Psychological Review, 87, 252-271.
Marr, D. (1982). Vision: A computational investigation into the human representation and processing of visual information. New York: W. H. Freeman and Co.
Marslen-Wilson, W. D. (1987). Functional parallelism in spoken word-recognition. Cognition, 25, 71-102.
McCullers, J. C. (1965). Type of associative interference in verbal paired-associate learning. Journal of Verbal Learning and Verbal Behavior, 4, 12-16.
Metcalfe, J. (1990). Composite holographic associative recall model (CHARM) and blended memories in eyewitness testimony. Journal of Experimental Psychology: General, 119, 145-160.
Murdock, B. B. (1974). Human memory: Theory and data. Maryland: Erlbaum.
Murdock, B. B. (1982). A theory for the retrieval and storage of item and associative information. Psychological Review, 89, 609-626.
Nelson, d. L. & McEvoy, C. L. (1979). Effects of retention interval and modality on sensory and semantic trace information. Memory & Cognition, 7, 257-262.
Nelson, D.L., Schreiber, T. A., & McEvoy, C. L. (1992). Processing implicit and explicit representations. Psychological Review, 99, 322-348.
Norman, D. A. (1966). Acquisition and retention in short-term memory. Journal of Experimental Psychology, 72, 369-381.
Norman, D. A. & Wickelgren, W. A. (1965). Short-term recognition memory for single digits and pairs of digits. Journal of Experimental Psychology, 70, 479-489.
Norris, D. (1986). Word recognition: Context effects without priming. Cognition, 22, 93-136.
Parkin, A. J., Leng, N. R. C., & Hunkin, N. M. (1990). Differential sensitivity to context in diencephalic and temporal lobe amnesia. Cortex, 26, 373-380.
Raaijmakers, J. G. W., & Shiffrin, R. M. (1981). Search of associative memory. Psychological Review, 88, 93-134.
Richardson-Klavehn, A. & Bjork, R. A. (1988). Measures of memory. Annual Review of Psychology, 39, 475-543.
Roediger, H. L. III, Weldon, M. S., Stadler, M. L., & Riegler, G. L. (1992). Direct comparison of two implicit memory tests: Word fragment and word stem completion. Journal of Experimental Psychology: Learning, Memory, and Cognition, 18, 1251-1269.
Rubin, D. C. & Wallace, W. T. (1989). Rhyme and reason: Analysis of dual retrieval cues. Journal of Experimental Psychology: Learning, Memory, and Cognition, 15, 698-709.
Sloman, S. A. & Rumelhart, D. E. (1992). Reducing interference in distributed memories through episodic gating. In A. F. Healy, S. M. Kosslyn and R. M.
Shiffrin (Eds.) From learning theory to cognitive theory Essays in honor of William K. Estes Volume 1. (pp. xxx) Hillsdale, N. J.: Erlbaum
Sutherland, R. W. & Ruddy, J. W. (1989). Configural association theory: The role of the hippocampal formation in learning, memory, and amnesia. Psychobiology, 17, 129-144.
Tulving, E. (1972). Episodic and semantic memory. In E. Tulving & W. Donaldson (Eds.), Organization of memory (pp. 382-404). New York: Academic Press.
Tulving, E. (1983). Elements of episodic memory. New York: Oxford University Press.
Tulving, E. & Schacter, D. L. (1990). Priming and human memory systems. Science, 247, 301-396.
Tulving, E. & Thomson, D. M. (1973). Encoding specificity and retrieval processes in episodic memory. Psychological Review, 80, 352-373.
Underwood, B. J. (1957). Interference and forgetting. Psychological Review, 64, 49- 60.
van Gelder, T. (1991). Representation in connectionist models. In W. Ramsey, D. Rumelhart, & S. Stich (Eds.) Philosophy and connectionist theory. (pp. 33-59), Hillsdale NJ: Erlbaum.
Watkins, M. J. (1981).Human memory and the information processing metaphor. Cognition, 10, 331-336.
Weber, E. U. & Murdock B. B. (1989). Priming in a distributed memory system: Implications for models of implicit memory. In S. Lewandowsky, J. C. Dunn & K. Kirsner (Eds.) Implicit memory: Theoretical Issues. (pp. 87-98). Hillsdale, N. J.: Erlbaum.
Wiles, J., Halford, G. S., Stewart, J. E. M., Humphreys, M. S., Bain, J. D., & Wilson, W. H. (in press). Tensor models: A creative basis for memory retrieval and analogical mapping in T Dartnell (Ed.). Artificial Intelligence and Creativity, Kluwer Academic Publishers, Dordrecht.
Wiles, J., & Humphreys, M. S. (1993) Using artificial neural networks to model implicit and explicit memory. In P. Graf & M. Masson (Eds.) Implicit Memory: New directions in cognition, development, and neuropsychology, (pp. 141-166). Erlbaum: Hillsdale, New Jersey
Wiles, J., Humphreys, M. S., & Bain, J. D., & Dennis, S. J. (1991) Direct memory access using two cues: Finding the intersection of sets in a connectionist model. In R. P. Lippman, J. E. Moody, and D. S. Touretzky (Eds.), Advances in Neural Information Processing Systems 3. (pp. 635-641)San Mateo, CA: Morgan Kaufman.
Author Notes
This paper was supported by a Grant No. AC8932304 from the Australian Research Council to the first two authors and by a Commonwealth Postgraduate Scholarship to S. Dennis. We would like to thank Doug Nelson for his helpful comments. Portions of this paper were presented at the 1991 meetings of the Psychonomic Society, San Francisco California, and the 1992 meetings of the Mathematical Psychology Society, Stanford California. Send correspondence to Michael S. Humphreys, Department of Psychology, the University of Queensland, QLD 4072 Australia, e-mail mh@psych.psy.uq.oz.au
Table 1 Notation, definitions of inputs and outputs, data structures and computational primitives.
Standard Notation
in means "element of" E means "there exists" 0 is the "empty set" # is "undefined" < is "subset of" v means "or" ^ means intersection U means union
Inputs and Outputs
x and y are items (words, relations, contexts, etc.). They are singleton sets. X and Y are sets of items.
XxY = {x U y | x in X and y in Y} X-Y = {x | x in X and x in Y}
a and b are words. They are singleton sets.
The name relation stands for a singleton set of a binary relation such as antonymof, or isa. RELATION is a set of relations.
list is a context, information about the time place or circumstances in which the learning occurred (a singleton set). LIST is a set of contexts.
S is a set of sets of items. s is an element of S, it can be a singleton set or a doubleton or higher order set.
I is the set of all items.
p, q are perceptual stimuli (singleton sets) and P and Q are sets of perceptual stimuli. The output from tasks such as single item recognition and lexical decision is a decision, yes or no.
The output from tasks such as recall and perceptual identification is a singleton set of items.
Data Structures
k M is a subset of the power set of I (M < I ). m is an element of M. It is a binding between items. For example, a binding which records the occurrence of a pair of words in a context would be {list,a,b}
L is the set of bindings between perceptual stimuli and the words which are compatible with those stimuli ({{p,a}})
Computational Primitives
The NotEmpty primitive takes a set and returns Yes if the set contains an element and No if it does not
NotEmpty (X) = Yes, X != 0
No, X = 0
The Choose primitive is designed to choose an element from a set. When the set is not empty it returns a singleton set. In the case where the set is empty the result is undefined.
Choose (X) = x, x in X and X != 0
#, X = 0
The Retrieve primitive takes a set of sets, and the memory structure M. It returns the set of items which are in a binding with any element of the input set.
Retrieve(S, M) = {x | E s in S, m in M where s < m and x in m - s}
The Compatible primitive takes a physical stimulus and returns the set of words which are bound to that stimulus.
Compatible(P,L) = {a | E p in P and {p,a} in L}
The Intersection primitive finds the intersection between two sets.
X ^ Y = {x | x in X and x in Y}
Table 2 Formal Specifications for five episodic and five semantic (lexical) tasks.
Episodic Memory Tasks
AB-ABr Learning
AB-ABr (LIST,P, L,M) = Choose(Retrieve(LISTxCompatible(P,L), M))
List Specific Pair Recognition (LSPR)
P and Q refer to the two members of the test pair
Alternative 1
LSPR(LIST,P,Q,L,M) =
NotEmpty(Retrieve(LISTxCompatible(P,L),M) ^ Compatible(Q,L)) v
NotEmpty(Retrieve(LISTxCompatible(Q,L),M) ^ Compatible(P,L))
Alternative 2
LSPR(LIST,P,Q,L,M) =
NotEmpty(Retrieve(Compatible(P,L)xCompatible(Q,L),M) ^ LIST)
Cued Recall with an Extralist Associate (CREA)
CREA(LIST,P,L,M) = Choose(Retrieve(LIST, M) ^
Retrieve(Compatible(P,L),M))
Cued Recall with a Part Word Cue(CRPWC)
CRPWC(LIST,P,L,M) = Choose(Retrieve(LIST, M) ^ Compatible(P,L))
List Specific Item Recognition (LSIR)
Alternative 1
LSIR(LIST,P,L,M) = NotEmpty(Retrieve(LIST, M) ^ Compatible(P,L))
Alternative 2
LSIR(LIST,P,L,M) = NotEmpty(Retrieve(Compatible(P,L),M) ^ LIST)
Semantic (Lexical) Memory Tasks
Relational recall (RR)
RR(RELATION,P,L,M) = Choose(Retrieve(Compatible(P,L)xRELATION,M))
Perceptual Identification (PID)
PID(P,L,M) = Choose(Retrieve(word x isa,M) ^ Compatible(P,L))
Lexical Decision (LD)
LD(P,L,M) = NotEmpty(Retrieve(word x isa,M) ^ Compatible(P,L))
Combining Semantic and Rime Information (CSRI)
P is the perceptual stimulus corresponding to the lexical item which is the name of the category and Q is the perceptual stimulus corresponding to the rime information.
CSRI(P,Q,L,M) = Choose(Retrieve(Compatible(P,L) x isa,M) ^
Compatible(Q,L))
Judging Prime Target Similarity (JPTS)
P refers to the prime and Q to the target
JPTS(P,Q,L) = NotEmpty(Compatible(P,L) ^ Compatible(Q,L))