Deductive Modeling of Human Cognition

Goran Hagert

Department of Psychology Uppsala University Sweden

Deductive analysis (DA) is Presented as an aR'roach to the sttrly and simulation of human cognitive processes. M is CXll'!p)Sed of a psycho­ logical theory and a lll:!thodology that can sheed light on mental phenomenas. The cognitive theorv is ent>edded in the problem space aoo the control structure hypotheses. The methodology consists of logical derivatioos of ~ter m:X!els from an abstract specificatioo. 'I1le item-recognitioo task and the three-term series task are analyzed for p.Jrpose of illustratioo. Several aspects of human oognitioo in these environments are discussed. It is argued that M brings new notioos to the sttrly of human cognitioo, for instance, to design sets of m:X!els an~ to distinguish between empirically equivalent nrrlels.

I INl'KlXX:l'ICN

We will present and discuss a few new aspects of sttrlying cognitive processing. They were called Deductive Analysis (M) in <5> and this type of deductive m:X!eli.ng is further developed here. The main aspect of M is cognitive simulation, so it beloogs to one of the main stream; in psychol<XJY. 'nlus, our goal is to design programs that can simulate hlll\an thinking, and one such program is a cognitive m:X!el. 'I1le hypothesis that the architec­ ture of mioo can be viewed as a syntJol mani1;0lating system or ;m informatioo processing system (IPS) <U> is related to our deductive m:X!elinq. There are t."-'0 other hypotheses about mirrl as an IPS­ structure. The problem space <11,12> and the control structure hypotheses <10>, respectively.

Our deductive analysis gives a method for oesigning CCITp.lter m:X!els, in particular, thi.s means that models of thought are derived, in logic, from an abstract model specification. ~is specification is abstract in the sense that it only contains a precise definition of the model. No information about representation and execution is explicit in the specification. Such issues have to be specified on the way toward the design and implementati.oo of a model, i.e., ouring the derivatioo.

II a::niTTIVE 'l'HFX:RY

The problem space hypothesis states that problem solving, decisioo processes, as well as reasoning, are search processes through a problem space. Each state in the space contains a set of Sten-Ake Tarnlurrl UPMAIL

Department of Conp.Jting Science !Jppsala Uni.versity Sweden

symbol structures which correspood to what the problem solver knows about the problem at a parti­ cular time. A new state is generated by m:X!ifying the symbol structures. 'I1le successive series of knowledge states that the problem solver passes is not a rarmn series, rut is generated by a strategy that the problem solver is following.

This is the general idea of the problem space hypothesis. The particular details of the con­ structioo of a space and the search through it depends on the task and on the person who solves ~t. For instance, if the task is simple, as i.n the ttem-recognitioo task <16> ·and the three-term se­ ries task <8>, the process of constructing a prob­ lem space is trivial. 'I1le task is easily assimi­ lated to the krnwledge of the problem solver . A pe~son will probably also generate a strategy qu1ckly and execute i.t imnediately ;md the time to solution is short. In contrast, the Tower of H;moi. puzzle and the Missionaries and Cannibal_s problem are exanples where a hlll\an problem solver may have troubles in constructing a relevant problem space aoo a strategy. The time to solution will, of course, be looger compared to simple tasks.

. _we will be restricted to cognitive processes tn sunple task environments. The general character­ ization of such processes is that the task is easily assimilated. This means that the person is able to represent and uooerstand the task quickly.

Given a conceptual framework in which mental events are viewe~ as search processes through problem spaces and gui~ by strategies, it can be asked how this strategy is organized ano executed.

This is the problem about control structure.

. We are currently ~eveloping DA in simple envtronments, where we think of a strategy as composed of a set of goals. The goals are achieved by operations. Let us show a sirrple abstract example of a strategy.

Assume that the goal-state OOAL can be reached

by a means-ends analysis using the operator::

(1)

which means that St.JB(l)ALl and surow..2 have to be attained to reach OOAL. To solve the t...u subgoals, which are our new state we neec'l some operators:

SUEcr)ALl can be attained by activating the operators called Pl and P2, whereras SUBGOAL2 can be resolved by calling Pl, P3 and P4. Each operator call may lead to an operator that transforms a state to a new state or leaves a state without change. The latter case means that a subgoaJ has been solve-1, and we write:

This example illustrates the simplest form of the language that we will use in developing DA. It is a subset of first-order logic, called Horn clauses <10>. As a consequence, it is possible to read the first expression above as: GOAL is true if SUBGOALl and SUBGOAL2 are true. In order to run Horn clauses we have to specify how the formulas are executed. There are many ways to execute a set of Horn clauses <9>.

We shall discuss three aspects of our method. First, we take up the task analysis or the identi­ fication of POSsible goals and operators, secondly, the derivation am execution of strategies in dif­ ferent problem spaces, and thirdly, the empirical evaluation or the comparisons between silnulations ann empirical observaticns.

A. Task analysis

We think of a task analysis as an identifi­ cation of goals that can be involved in a solution to a particular task. It means also that the set of goals, or a subset of them, is specified in a model specificaticn. Each specification contains a set of possible simulation models that are abstractly but precisely defined. A model specification leaves several aspects Lmspecified. For example, the representational format that goals and procedures operate on is not defined. Therefore, no r'lecisicn can be mooe about how to manipulate informaticn.

Design issues:

• 1 Representational format: How is internal information represented?
• 2 Operational assumptions: How is information manipulated?
• 3 Operational mode: How is each operaticn transformed? How is a transformaticnal time fLIDCtion defined for an operation?
• 4 Operational order: How is the set of opera­ tions organized?
• 5 Operational rule: How is the entire set of operations transformed? HeM is this time fLmction defined?

Fig. 1 Five . issues on the design of models.

Fig. 1 oontains a list of issues not included in a nmel specification . Hypotheses have to be formulated on each of the five design issues to Umplement a computer model. There may exist several different hypotheses on each issue, for example, on internal information formats. Consequently, this step can be as Ump0rtant as the specification since the hypotheses on the design issues iooirectl.y restrict the set of possible models. In short, the specification and hypotheses contain a set of possible simulation models, i.e., a set of pairs of problem space and strategy.

B. Derivatioo and silll.llation

The task analysis leads to a model specifica­ tion and a set of hypotheses about the design issues. we write them in first order predicate logic. These statements about mental processing in the given task danain can usually not be rLID as simulations, they do not constitute a computational model. To reach a form that represents mental {tlenanenas and is cxxnputable we may have to trans­ late the specification into a set of more basic stat~ts. In . DA it is carried out by logical derivation, in particular, we use a natural deduc­ tive system of Gentzen type <4>. Such a system has been used for formal program devel~nt in <6>. However, in this context we are not interested in automatic deductioo, although developments in that area may influence DA.

An abstract specification consists of a precise definition of a set of goals. A derivation means that all the aspects, which are left LID­ specified are successively defined by design hypotheses. For instance, a specification does not contain any specified representatioo, so we can introduce an assumption on mental representation. There are, of course, several such hypotheses, leading to different derivation paths. When one representation has been introduced we have defined a problem space. The next steps in the derivation involve the strategy that will be used in that space. Again, there may be several ways to define a strategy, since the specification does not contain any information about it.

At each derivation step we use a logical inference rule, so a derived simulation model is a logical consequence of the specification. This property is rarely satisfied for simulation models.

The result of a derivation is a set of statements that form a cognitive model. The model includes both a problem space and a strategy to use in that space. When the statements are Horn clauses we can rLID them in a t~ manner by Prolog <14,18>, in this way we get our simulations automatically.

c. ~irical evaluatioos

The models are logical oonsequences of the specification, rut it remains to see if they are empirically true. It may not be the case that they constitute problem spaces and/or strategies that people spontaneously use in the particular task environment. A model may have properties not shared by the hl.lllail cogni.tive system, or properties that may be learned. 'nlus, we have to evaluate them by comparing the results from the simulations by empirical observations.

The simulations contain two types of data: reaction times and traces. In addition, we kNJW which representation each model is working on so, in fact, we have three differ~nt types of data. Mental representations are, however, impossible to use, at least with the type of. empirical methods used today.

When evaluations have been made it is possible to compare the models that can reproduce the empirical observations with those that cannot. These comparisons result in an identification of the problem spaces and/or strategies that people do not use. It is also possible to compare the successful models with each other to see what problem spaces anrl/or strategies people do use. These models share properties in the form of design hypotheses that are empirically or functionally equivalent. Til is CXlltPll' ison may also show types of data that could distinguish them further.

Two simple task environments will be used for illustration. The first task is a very simple one and called the item-recognition task <16>. The other ta~k is called the three-term series task <8>.

A. The item-recognition task

In this task a person is instructed to memorize a list of symbols, for example, letters or digits. The memorized list is called the positive set. The person is then presented with a probe symbol shortly after a ready signal. The task is to answer "yes" if the probe syml:x:>l is a member of the positive set, and "no" otherwise. The size of the pas i ti ve set in terns of number of symbols is usually varied from 1 to 7. Til is task has been

investigated a number of times <16>.

Even if the task is simple, a person who is trying to solve the task needs to do sanething mentally. There are at least four intermediate states before an answer is given. Following our terminology there are four subgoals to attain before an answer can be reached <16>.

1. The encoding goal is a process where the external probe is perceived by the person and transformed to an internal symbol in memory. Hence, there must be an operation called ENCODE from an external probe to an internal representation of that probe.
2. To solve the task the person must in some way oompare the probe with the symbols in the positive set. 'nlus, there must exist an operation from the probe and the set to a note that signals a match or a mismatch. 'nlis operation is called a:H>ARE.
3. The note from the seconn subqoal has to be examined. EXAMINE is an operation from the note to an internal answer.
4. The person has to translate the internal answer into an external action. 'nlis is the O:EIJ)[)E operation.

In propositional logic ·...e can write a simpl e speci f.ication

SOLVE <-- ENOODE & crMPARE & EXAMINE & D'EXX>DE ( 5)

which we read as: to attain SOLVE (the qoalstate) resolve EN(D)E and crMPARE and EXAMINE and DEOJOE. This is an insufficient specification for our rurpose so ~ reformulate it. The goal-state can be attaineil if the probe is enccx:led and j_f the positive set is empty the answer is "oo"; otherwi_se compare the pnobe with elements in the set, and examine the note. Finally transform the answer into action. In predicate logic we write

Vp' Vs Ea' (SOLVE(p',s) =a'<-- (6)

Ep En Ea (ENOODE(p') p &

(s = ni.l & a = "oo" & DEXXDE(a) = a') v (COMPARE(p,s) = n & EXAMINE(n) = a & DEXXX>E(a) =a')))

This is an abstract model specification because it leaves several aspects unspecified. For instance, what is <Xl-1PARE? How is the information (the positive set) represented, etc.,. The aspects that are not specified can be foond in the design issues. We have included five issues in Fig. 1. It may be possible to extend the list further, but for our present purpose it is sufficient.

Different hypotheses can be formulated on each of the design issues. Let us start with a repre­ sentation of the positive set. At least two formats can be suggested, simple-list and d-list, respec­ tively <1,17>. The positive set is representen as a simple-list if and only if the set is empty or constructed of a proposition element(e) ani! a simple-list <5> . Formally,

Vset (simple-list(set) <--> set = nil v (7 ) Ee Eset' (set = e.set' & element(e) & simple- list(set')) )

So far , we have formulated two hypotheses · Four issues remain. For instance, the second issue concerns how information is manipulated. Given a simple-list format of the positive set membership can be defined either by an operation from the beginning of the list or from the end, correspond­ ing to the notions of stack and queue, respective­ ly. For a stack an element e is a member of a list set if and only if there exists another element x and a list y where element e is equal to element x or is a member of list y.

VeVset(~ e set <--> ExEv(set x.y & (8) element(x) & simple-list(y) & (e = x v e e y)))

The thi.rd issue is operational mode. This issue is particulary relevant for the a:H'ARE goal. At least two different modes are possible. It can r:perate i.n either an exhaustive roode, or it can be self-terminatinq. Thus, we can postulate two hypotheses about c:x:MPARE <5>.

The fourth issue concerns operational. order. The four subgoal s are corp.~ ted by four operators ann in this simple example, the order is given. H<:Mever, .i.t should be pointed out that this may rx>t be the case in another environment. Tl'lis issue al"la includes timing assunt>tions which we will return to belCM.

The fifth issue concerns the global control of a program that, for example, can be in a serial or parallel] ordering. It also includes timing as­ sumptions. We assume an operationaJ ~:ule cor­ responding to a serial top-down execution as e.g., in Prolog.

In sumnary, we have formulated two hypotheses about representation, two about manipulation two about operational roode, one about operational order, and one about the operational rule. The first six are particulary relevant for the deriva­ tions and the remaining ones for the simulations.

We focus on psychological rx>tions and can thus for reasons of space leave out formal derivations <6>, but we shall outline the general structure. For each goal in the specification we derive a set of operations 1Jv using our nesign hypotheses. We assume a representation e.g., the simple-list format, and also a modifier, for instance, the stack hypothesis. Then we assume the roode of the operation, for example, a self-terminating roode. 'l'he resulting set is Model-l. Bv substituting one hypothesis by another, we can derive a second set Monel-2. In this way we can derive six simulation models 1iffering in at least one cognitive aspect, but satisfyi11g the roodel specification.

In Fig. 2 we sumnarize the derivations in a deduction tree.

As can be seen in Fig. 2, two of the six models correspond to two different strategies within the same problem space, whereas the other four are strategies in arx>ther space. Fig. 3 shows Model-l that uses a simple-list representation ann searches the positive set exhaustively by a stack modifier.

We have arrived at six computable models from a specification by task analysis and deduction.

Specification (7)

Deduction

Model-l

SOLVE(p' ,nil,a) <-- m<DDE(p' ,p) & DEOJDE(OO,a)

SOLVE(p' ,s,a') <- FNOJDE(p' ,p) & CXMPARE(p,s,n) &

EXAMINE(n,a) & DECODE(a,a')

m<DDE(p' ,p)

c:x:MPARE(p,nil,n) <-- n=l v n=O

c:x:MPARE(p,p.s,l) <- COMPARE(p,s,l)

CXMPARE(p,e.s,O) <- COMPARE(p,s,O)

COMPARE(p,e.s,n) <- COMPARE(p,s,n)

EXAMINE (1, YES)

EXAMlNE (0, 00)

DECODE(YES, say(YES))

DEOJDE(OO, say(OO))

Fig. 3. Model-l in Horn clauses.

The six roodels are programs that can solve the item-recognition task. Timing assunt>tions on design issues 3 and 5 make it possible to collect reaction time data and trace data in the simulations, in which we assume a simple additative function i.e., time is added linearly both within an operation and between operaticns. The particular estimates used in the simulations, the reasons for each timing assunt>tion, as well as a discussion of the em­ pirical evaluations can be found in <5>.

We want to point out that M makes it possible to be precise in the empirical evaluation. Data that distinguish the roodels can be understcx:x1 in tenrs of the design hypotheses. Furthermore, it is possible to identify types of data that could distinguish empirically equivalent models. In Fig. 4 we illustrate these points.

B. The three-term series task

In our second example of DA we will analyze the three-term series task introduced by Piaget <13>. The subiect is given two premises that describe the relations between three obiects. For instance, "Adam i.s shorter than Bob" and "Bob is shorter than Carl". Tl'le task is to answer a question e.g., "wiD is tallest". This task has also been investigated a number of times <8,15>.

As a first step for irlentification of possible problem spaces and strategies we define subgoals. 'I\.o of them are obvious the EN<rrlE and DEXJ)[)E goals. There are at least foor other goals that can be resolved for a solution. Below, a task premise allways refers to the external string of words, whereas a cognitive propositi~ refers to the mental representation of a string.

1. A qoal that may be involved is a SERIATE goal, proposed, in different terms by <7>. This goal means that the objects in the two premises are in­ tegrated into a spatial series or image. It can operate differently depending on the relations in the task premises. For example, the goal may be attained more easily if the series is built fran right to left, rather than from left to right <2>.

Hence, there may exist several different operators for catp.~ting this goal. SERIATE will rlepend on representation, nodifiers, and node of execution. There is at least one operation from a proposition and a sedes (which can be empty) to a new extended series.

1. The subgoal PARSE means that a proposition is further processed. For example, assume that the first premise is: "A is not taller than B". The goal F.N<:mE may then deliver a proposition "(IDI' (TALL A B))" to merrory. Given this proposition PARSE may produce the structure " (Sfi)R'I't B , Sfi)RT A)". The goal PARSE processes the linguistic content of a proposition such as markedness versus unmarkP.dness and negations into structured propo­ sitions <15>. However, there are several ways to catpJte the PARSE goal, but at least one operat ion exists from a proposition to a deep-structure.
2. Another goal is ELIMINATE, which successively deletes objects that are no answers <3>. Suppose that the question is " (Sfi)R'I't x) ", where x is a variable, and a proposition is "(SIDRT A B)", then ELIMINATE nodifies the first proposition to "(Sfi)R'I't A)". ELIMINATE has to be catp.~te-1 by an operator from a proposition and a questi_on to an obiect or a proposition.
3. From an internal series or a set of deep­ structures, FIND is a goal that looks for an answer. The comoutation of this goal depends on representational format and accessing possibilities in that format. There has to be at least one operation from a question and a set (of objects or deep-structures) to an internal answer.

Let us first use propositional logic to formulate a nodel specification

We read this formula as: a goal-state SOLVE follows from ENCDOE and either ELIMINATE or use the goals

PARSE or SERIATE and FIND, and DEXDJE the answer.

We can readily transform (10) as follows

In this way we have derived four formulas from the specification that have simpler psychological oon­ tent, but each of them is an abstract characteriz­ ation of cognitive processes. Unfortunately, pro­ positional logic is not enough for charaterizing these processes properly so again we take up predicate logic for this purpose.

Vs' Va' (SOLVE(s') =a' <-- (14) task-premise(s') & an~wer(a') & Ex Ed Ey Eil Ei2 Ea (EN<DDE (s') = x & (proposition(x) v questioo(x)) & ((((PARSE(x) = d & deep-structures(d)) v ( y = x v y = d & series(il) & series(i2) & SERIATE(y,il) = i2)) & FIND(x,i2) = a & questioo(x) & answer(a)) v ELIMINATE(x,y) = a & question(x) & propositioo(y) & answer(a)) & DEOOOE(a) =a'))

We have to rewrite the formulas in (10)-(13) in predicate logic to characterize the cognitive processes. Each of them is a specificatioo, and they satisfy the formula in (14).

Next we have to define our design hypotheses about e.g., proposition(x), question(x), series(x), tow these are manipulated, and how the operations are executed.

The derivatioos lead to four sets of simula­ tion nodels all differing in at least one aspect. Each nodel is (i) a logical oonsequence of the nodel specification and (ii) follows from one of the derived specifications ((10)-(13)). At the most abstract level and at the lowest level, t.he dif­ ference between two nodels is explicit. A nodel oonstitutes a problem space and a strategy to use in that space and it is a problem solver in the present danai.n. Dnpirical studies that consider individual differences can distinguish between these nodels am also stow the properties of them that are not empirically true. Thus, DA oould isolate properties of the cognitive system.

The cognitive theory of DA - the problem space and the control structure hypotheses - was deve­ loped by Newell ::md Simon <12>. We have introduced a characterization of cognitive functioning in sLmple task environments, where processes are viewed as top-down driven and canposed of goals an<'l operators. Together they form a strategy which is executed within a problem space defined by the goals and the particular representatioo they are

working on.

we want to compare models and to describe their similarities as well as their differences. We think that the ability to reason about and above models is a necessary component in the study of thinking. This is a reason for chcosing logic as language rather than, for exanple, producticn system:;. I.Qgic i.s the language we use both at the abstract specificaticn level and at the lower modeling level. Also, the relation between a specification and particular mcnels is precise and explicit since we <ierive the simulation models .i.n the same language.

The approach we are developing has a potential to capture individual differences, rather than some sort of average behavior. It i.s the purpose of DA to design several models that can be evaluated agai~st empirical data. It is also possible to compare empiricallY supported models with those that cannot reproduce empirical observaticns. Such comparisons will yield the properties within the models that have no cogni.ti.ve reality. E)npirical and functional equivalences between models reflect the rich variation in human cognition, but in DA the differences between them is still explicit and can be further analyzed.

• <1> Clark, K. and Tarnlund, S-A. "A First Order Theory of Data and Programs." In Proc. IFIP77. North-Holland, Amsterdam, 197~
• <2> DeSoto, c. B., Lcndon, M. & Handel, S. "Social Reasoning and Spatial Paralogic." Journal of Personality and Social Psychology, 2, (1965) 513-521.
• <3> Da1aldson, M. A Study of Children's Thinking. London: Tavistock Publications, 1963.
• <4> C~tzen, G. Investigations into Logical Deduction. In M. E. Szabo (Ed.) The collected papers of Gerhard Gentzen. Amsterdam: North­ Holland, 1969, 13-75.
• <5> Hagert, G. & Tarnl.und, S-A. Deductive analysis of cognitive processing: A first example. WOrking Papers from the Cognitive Seminar, Department of Psychology, University of Stockholm, No. 5, 1979.
• <6> Hansson, A. & Tarnlund, Progranrning Calculus." In Tokyo, Japan, August, 1979. S-A. "A Natural Proc · IJCAI-79 ,
• <7> Htmter, I. M. L. "The Solving of Three-Term Series Problems. The British Journal of Psychol~, 48 (1957) 286-298.
• <8> Johnson-Laird, P. N. "The Three-Term Series Problem." Cognition, 1 (1972) 57-82.
• <9> K~alski, R. "Predicate Logic as Progranrning Language." In Proc. IFIP-74, North-Holland, Amsterdam, 197~
• <10> Newell, A. Production Systems: r.t:rlels of Ccntrol Structures. In w. G. Chase (Ed.) Visual Informaticn Processing. New York: Academic Press, 1973.
• <11> Newell, A. "Reasoning, Problem Solving and Decision Processes: The Problem Space as a Fundamental Category." Department of Conputer Science, Carnegie-Mellon University, Report No. 133, 1979.
• <12> Newell, A. and Silron, H. A. Hl.UIIan Problem Solving. Engl~ Cliffs, New Jersey: Prentice-Hall, 1972.
• <13> Piaget, Child. 1928. J. JOOgment and Reasoning Lcndon: Rootledge and Kegan in the Paul,
• <14> Roossel, P. "PR)I.D:;: Manual de Reference et ti'Utilizati.on." Group d'Intelligence Artificielle, Marseille, 1975.
• <15> Sternberg, R. J. "Representation and Process in Transitive Inference." Department of Psychology,. Yale University, Technical Report 12, 1978.
• <16> Sternberg, S. "Menory Scanning: New Findings and Current Controversies." Psychological Review, 27, (1975) 1-32.
• <17> Tarnlund, s-A. An Axiomatic Data Base Theory. In H. Gallaire and J. Minker (Eds.) t§1ic and Data Bases. New York: Plenum Press, 9 B.
• <18> Warren, D. "A user's guide to the oa::-10 Prolog system." Department of Artificial Intelligence, University of Edinburgh, 1975.