🚀 go-pugleaf

   J van Brakel: THE COMPLETE DESCRIPTION OF THE FRAME PROBLEM.
                 Book Review of Ford & Hayes (1991)

-----------------------------------------------------------------------
psycoloquy.92.3.60.frame-problem.2.vanbrakel   Sunday, November 1, 1992
ISSN 1055-0143                (33 paragraphs, 23 references, 485 lines)
PSYCOLOQUY is sponsored by the American Psychological Association (APA)
		Copyright 1992 J. van Brakel

          THE COMPLETE DESCRIPTION OF THE FRAME PROBLEM
       	Book Review of Ford & Hayes on the Frame-Problem

                 J. van Brakel
                 Department of Philosophy
                 University of Utrecht
                 P.O. Box 80.126
                 3508 TC Utrecht (Netherlands)
                 telephone -31.3402.43912
                 telefax -31.30.532816
                 brakel@phil.ruu.nl

0.1  This is primarily a critical discussion of Ford & Hayes (1991; for
PSYCOLOQUY Summary, see Hayes 1992), taking into account other recent
literature on the frame problem. [References to chapters and pages
in the Ford & Hayes volume are given in square brackets.]

1.0  THE FAMILY OF FRAME PROBLEMS.

1.1  If an event (for example, one brought about by an action, in order
to achieve a goal) occurs in the real world, we may ask (either with
respect to knowledge or belief):

   [A] Which things (facts, etc.) change and which don't? (Most don't.)

       More specifically:

       [A1] What are the necessary and sufficient conditions for an
       event to occur (an action to be performed successfully, a plan
       to be carried out)? and

       [A2] What (potential) changes are brought about by the event?
       (What are its consequences?)

   [B] How can [A] be represented?

   [C] How can/do we reason about [A]?

1.2  These questions, I suggest, constitute the family of frame
problems (including the persistence problem, temporal projection
problem, inertia problem, qualification problem, ramification problem,
extended prediction problem, installation problem, planning problem,
holism problem, relevance problem, and so on), covering all definitions
in Ford & Hayes (1991) [Ford and Hayes: x; Brown: 1; Fetzer: 55;
Hayes: 72; Goodwin and Trudel: 87; Haugh: 106f, 122; Morgenstern: 134,
168; Nutter: 173f; Perlis: 190; Sandewall: 206; Stein: 220; Tenenberg:
232, 252; Weber: 259; Weld:  275f] and most of the many definitions in
Brown (1987) and Pylyshyn (1987). Part of the confusion about the frame
problem is its family resemblance character. The best approximation
to my own characterisation that I have found is Brown's (1987, v): "The
frame problem... is the problem of describing in a computationally
reasonable manner what properties persist and what properties change as
actions are performed." This leaves out [A1], which could be added to
Brown's terminology as the qualification problem.

1.3  Why is the frame problem a difficult one? Because "things are just
normally quiet and uninteresting" [Hayes: 72]; because "a certain trick we
have just observed is flat impossible" (Dennett 1987). "There is too much
information about change to consider at any given time" [Nutter: 176].
"There is no end to the ways things might happen unexpectedly" [Hayes: 73].
This is the case, even apart from "technical" problems such as "explicit
representation of concurrent events and multiagency" [Tenenberg 241].

1.4  The family of frame problems is more or less closely related to "the
general problem of stating `laws of motion' which adequately describe the
world" [Ford and Hayes: x]; the prediction problem [Tenenberg: 232]; the
induction problem [Fetzer: 55]; "the general problem of default reasoning"
[Perlis: 190]; "the larger, and uglier, counterfactual validity problem"
[Stein: 225]; the "Frame* Problem" for natural language understanding,
learning, and analogical reasoning [Nutter: 177]; and other problems.

1.5  I won't go into the details of trying to separate the frame
problem from these other problems except to make a brief remark about
the problem of induction. I tend to side with Hayes [71-76], in his
exchange with Fetzer [55-70, 77-86]. The frame problem is not the
problem of induction in disguise: "even if we had the laws of science
given to us by an angel on tablets of bronze, the frame problem would
still be there" [Hayes: 75]. The same point is made by Dennett (1987):
Having access to absolutely justified true probabilistic knowledge is
of little use to a robot who has to make a plan to save its spare
battery if it does not know how to apply this knowledge to the task at
hand. Nevertheless, the conflict about the relation between the frame
problem and the induction problem is more indicative of the nature of
the frame problem than a substantial substantive symptom in its own
right: Philosophers tend to concentrate on [A], which is definitely
related to the induction problem; Hayes concentrates on [B]; and
knowledge engineers who have to deliver tomorrow concentrate on [C].

2.0  THE PROBLEM OF COMPLETE DESCRIPTION.

2.1  There seems to be general consensus that "a definition of the
`frame problem' is harder to come by than the Holy Grail" [Stein: 219].
Still, I believe that questions [A] - [C] formulated above are quite
straightforward. Nevertheless, Dennett (1987) and Hayes (1987) are
right to stress that the frame problem is a deep one, not "the sort of
glitch the hackers will sort out by themselves" (Hayes 1987), "of
interest mainly to a fringe group" (McDermott 1987). Perhaps the
problem is even deeper than they think.

2.2  The very difficulty of formulating it illustrates the frame
problem: The frame problem is a special case of the PROBLEM OF
COMPLETE DESCRIPTION (PCD). It is, in general, not possible to specify
the necessary and sufficient conditions for something: not for the
style of a work of an artist, not for the application of a concept or a
rule, not for the occurrence of a particular event. Of course, it is
possible to propose conventional definitions specifying necessary and
sufficient conditions for, say, the use of a word, but we cannot step
outside these definitions and give definitions for all the words that
are used in the definitions (or the metalanguage). There are of course
physical laws which are said to relate events in a necessary way. But
laws (or other universal statements) cannot be applied to concrete
events without the addition of unspecified ceteris paribus conditions.

2.3  The problem is not only that we don't know HOW to give a complete
description (of, say, what is relevant for a particular action in a
particular situation in view of a particular goal). We really don't
even know what we mean by "giving a complete description."

2.4  The problem of giving a complete description has lurked behind the
frame problem from its very inception in 1969 when the complete state
of the universe at an instant of time was invoked by McCarthy and Hayes
to solve it [Fetzer: 78]; and implicit or "intuitive" awareness of it
can be found in many places in Ford & Hayes (1991): "Haugh,
Morgenstern, Tenenberg, and Weld [all four are contributors to the
volume] each point out that there is an implicit assumption that the
agent doing the reasoning has complete knowledge of all the relevant
facts" [Ford and Hayes: xii]. "Typical proposals assume omniscience
about such things as successful action attempts, causal laws,
`intervening' events, fact changes, 'motivated' event occurrences, and
`potential causes' [Haugh: 105]. "The everyday world... is too complex
for any creature to fully axiomatize its behavior" [Perlis: 191];
"humans do not solve the general problems of relevance and change,
because they are unsolvable" [Nutter: 176]. "Approaches that depend on
the ability to enumerate the infinite number of qualifications are
doomed to failure" [Weld: 277]. "[I]t is notoriously impossible to list
all the possible but unusual conditions that might obtain while being
consistent with a simple description of a situation" [Hayes: 73]. (Cf
also [Fetzer: 57, 62; Perlis: 191; Tenenberg: 235f; Weber:  263].) It is
rare to find an explicit denial of the PCD. An example is Lenat and
Feigenbaum (1991: 246) who exclaim: "one need never IN PRINCIPLE throw
up one's hands and say `you just had to be there, I can't describe
it!'"

3.0  OSTRICHES, RELEVANCE, AND DOMAIN-MODULARITY.

3.1  A theoretical solution to the frame problem in the sense of
providing and manipulating a complete description is impossible. But
what about a practical solution? Ordinary human beings don't seem to
suffer very much, if at all, from the frame problem: "people in their
everyday thinking DO solve the frame problem" [Hayes: 72; cf Fetzer:
80; Nutter: 172].

3.2  Broadly speaking, there are three ways of dealing with the PCD in
a pragmatic way. The first approach is to deny it (the ostrich policy).
This view cannot be refuted because all problems encountered in
solving it are simply relegated "to the proverbial FUTURE WORK
category" [Etherington, Kraus, and Perlis: 52]. The second approach is
to recognise it, after a fashion, but think that one can break out of
it by using heuristics or a panacea like relevance or salience. The
third approach is to recognise the PCD but assume that it does not
exist for specific domains.

3.3  The ostrich approach is best illustrated with some straight
quotations (in each case the first quotation is from the introduction
or summary of the contribution, the second from the discussion or
conclusion).

3.31  Morgenstern: "we show how an existing nonmonotonic temporal logic,
Motivated Action Theory, can be extended to handle both problems"
[133] but "we cannot express problems in which agents plan to combine
their partial knowledge in order to perform some action" [160].

3.32  Etherington, Kraus, and Perlis: "a proper foundation for the frame
problem must rest on a theory of nonmonotonic reasoning" [43], but "[w]e
are not proposing to present an adequate treatment of the general [frame]
problem but merely illustrate that our approach can avoid difficulties
associated with indeterminate clippings" [51].

3.33  Haugh: "A particular situation-calculus-type theory... is
presented... that solves the frame problem without omniscience
assumptions" [105] but "[t]he particular formulation presented... will
require some extensions before it will fully constitute such a
solution. In particular, it will need extensions to handle
ramifications, event-event causation, continuous change, and the
qualification problem" [122].

3.4  Various "heuristics" have been proposed to permit a big leap
forward, for example, "to simply minimize unjustified changes" [Haugh:
115; cf Morgenstern: 152], but this presupposes the solution of the PCD
[cf Fetzer:  60; Haugh: 106, 122; Tenenberg: 237; Weber: 260-264]. It
has been further suggested that the frame problem can be reduced "to
the problem of choosing the appropriate reference class" [Tenenberg:
245; cf Fetzer: 62; Goodwin and Trudel: 95; Tenenberg: 231], but this
merely pushes the problem ahead: How do we determine "the APPROPRIATE
reference class for the probability assertions of interest" [Tenenberg:
253, emphasis added]? More seriously, such approaches appeal to our
intuitions about what is appropriate, justified, etc. This is question
begging, because one way of formulating the frame problem is as the
problem of how to model our intuitions. Invoking something's having to
be "appropriate" [Perlis: 189; Tenenberg: 231, 245, 253; Weld: 275,
283], "relevant" [Ford and Hayes: xii; Fetzer:  62, 80; Nutter: 182;
Stein: 220ff; Weber: 269], "salient" [Nutter: 183], or "intuitive" for
that matter, is useless as a contribution to solving the frame problem.
The problem is just pushed ahead.

3.5  Consider Nutter, who writes: "The key issues in dealing with the
Frame Problem and with frame problems in general are neither
qualification nor ramification nor persistence, neither uncertainty nor
belief revision nor causal relevance, neither time nor logic nor
including enough information... The key issues are relevance, salience,
and a rich enough sense of context, and the key mechanism is focus of
attention" [175f]. But at the end of his chapter he says: "The primary
untouched issue here is how our system decides what initial nodes and
arc types to put into the context. This is a general problem for AI
which surfaces over and over... It would be difficult to overestimate
its complexity" [186]. Although it has been said that "Fodor misuses
the term `frame problem' in at least three different ways" (Hayes
1987), Fodor (1987) is perhaps at least partly right when he writes
that "the frame problem is [that of] saying what a `real property' is."
What is at issue here is that the choice of "the right primitives" is
not a trivial matter but the core of the issue. As Dunn (1989)
correctly points out: "relevance logic can no more tell us which are
the relevant atomic properties, than can classical logic tell us which
are the true atomic propositions... it is up to the database creator to
decide which predicates are relevant." But how is the database creator
to do this [cf Goodwin and Trudel: 90; Sandewall: 212; Weld: 276]?

3.6  The third way of dealing with the PCD is to dispute "The Myth of
Domain-Independent Persistence" [Weber: 259]. This is the approach of
Weber, who says that the "omniscience assumption is only valid in very
restricted domains" [263; cf Fetzer: 60-63]. The appeal to "context
limitation through salience" [Nutter: 186] might also be taken as a
form of domain restriction. In practice, domain restriction and
heuristics are usually combined. For example, Holland, Holyoak, Nisbett
and Thagard (1986), responding to Fodor's worries, write: "a processing
mechanism of the sort we favor circumvents the problem of the potential
relevance of everything in the knowledge store by PRAGMATICALLY
SELECTING limited areas of information to explore... By tending to fire
the strongest and most GOAL-APPROPRIATE rules, a constrained search
through the space of RELEVANT information can be carried out." It's the
phrases that I've emphasised that worry me (and would, I presume, worry
Fodor as well). But most practical AI researchers would not find much
wrong here and would conclude with Lormand (1990), after discussing
views of philosophers like Dennett and Fodor on the frame problem: "why
should we suppose that it is a PROBLEM?" In fact, in not seeing a
problem, Lormand is making two important assumptions: [i] the choice of
primitive terms is straightforward; [ii] descriptions can be carried
out independently for each domain. It is because these assumptions seem
so "plausible" or "intuitively" correct that there doesn't seem to be a
PCD. But these assumptions are incorrect (van Brakel 1991).

4.0  LOGICISM, PHYSICALISM, CONNECTIONISM.

4.1  I have been rather cynical about the approaches referred to in the
previous section because I think they all show insufficient awareness
of the general problem of the impossibility of giving a complete
description. It remains true, however, that humans do manage. How do
they do so? Perhaps we have to reconsider some basic assumptions
underlying all approaches to the frame problem. The assumptions are, of
course, those of logicism (Kirsh 1991a):

   (1) Modelling propositional knowledge and conceptualisation is
       essential for intelligence.

   (2) Cognition can be studied separately from perception and motor
       output.

   (3) The kinematics of knowledge is linguistic.

   (4) The statics and dynamics of knowledge can be studied separately
       from learning, psychological development and evolution.

   (5) There is one architecture.

I take it that all contributions in Ford & Hayes meet these
five criteria (or at least four of them).

4.2  From such a perspective the PCD is not considered relevant. It is
assumed that the frame problem can be solved in a piecemeal way.
Logicists can acknowledge that, say, (2) and (4) might be disputable in
principle, yet because of the primacy of the linguistic character of
knowledge theirs is the best approach to the problem. But perhaps the
ways humans (or evolution for that matter) have solved the frame
problem in a practical sense do not live up to this kind of modular and
piecemeal approach. Perhaps the piecemeal approach works, at least for
a while, in some areas, but not for "solving" human behaviour. Perhaps
"[t]he frame problem is an artifact of viewing perception as input to
cognition, suggesting that input is predigested and exists apart from
the process of behaving, and that memory is a special storage for
descriptions of the world which are matched against rules that describe
behaviors" (Clancey 1989: n18).

4.3  What about other approaches? First consider physicalism. Even if
we allow externalism (what philosophers of mind call "wide content"),
there MUST be a physical explanation of how humans do it. There MUST
exist at least one practical solution to the frame problem, because
humans use it. But "`common sense' (or `ordinary') knowledge is not
enough to provide [it]... What is required is the kind of knowledge we
only possess when we have discovered those causal laws whose operation
governs the processes and outcomes concerning us" [Fetzer: 58]. This is
also the argument of Ross (1990), whose reasoning is as follows:
Induction works in practice, but we can't formalise it. Everything that
is not completely deductive may accordingly fail to be formalizable.
Even when something is deductive, in the general case, not everything
that is true can be proved. Hence, as it were, theoretical solutions
are excluded a priori.

4.4  But, to repeat, induction works in practice. So, by analogy, there
must be a practical solution to the frame problem. During human
evolution, "nature" has hit on a practical solution to the frame
problem. We have to find the PHYSICAL description of how humans do it:
"What we must do as AI researchers, then, is reproduce our structural
architecture" (Ross 1990). Of course, this "solution" is of no direct
practical use for AI (perhaps it even denies the relevance of AI). And
there is a further problem: the distinction between a complete physical
description and a complete commonsense description. It is not
self-evident that there is a type-type correlation between physical and
commonsense descriptions of what is going on.

4.5  What about connectionism? At first blush it seems better suited to
solving the frame problem: it might provide a more natural connection
to perceptual input and to getting knowledge by learning. Also the "old
problem of how to retrieve relevant information is transformed by the
realization that it does not have to be `retrieved'" (Churchland 1989:
195). However, it seems to me that current work on connectionist models
makes the same assumptions as logicism about separate domains
characterised by "natural" primitive terms. (Think of nets, taught or
self-taught, that learn to separate cats and dogs.)

5.0  THE PERVASIVENESS OF HOLISM.

5.1  A proper assessment of the holism issue is crucial to evaluating
the possibility of practical solutions to the frame problem. Here I can
only set a few pointers. First, the subworlds of separate domains are
not the same as isolated physical systems that can later be put
together using a few rules to make the whole. Subworlds are local
"representations" of a whole they presuppose (Dreyfus and Dreyfus 1990).

5.2  Second, it is often said that daily knowledge is extensive, but
not deep. This is a mistake, because the cognitive and subcognitive
levels cannot be separated. There is no a priori way to formalise
judgements of association strengths, neologisms, jokes, epitaphs, etc.
It is only good enough if it is identical to a complete human being
(French 1989). (Think of a robot with eyes on its knees.)

5.3  Third, there is a fundamental difference between knowing a part of
something and partly knowing something. As an example, consider Maloney
(1991: 57): "FULLY understanding any given concept is holistic and
requires knowing how that concept fits in with other concepts we may
have. But that should not blind us to the fact that understanding a
concept is a matter of degree." This is wrong, however. Maloney
considers the complete description of a concept as something that is
given, passing over variations across time, conversations, or persons.
He compares the "limited knowledge" of scripts with the limited
knowledge of small children (about chairs, for example) but he ignores
the fact that children's knowledge of chairs is built up starting from
"intimate" relations with chairs. This relational knowledge has little
to do with the descriptive knowledge in a "chair"-script. He also
passes over the fact that knowledge of chairs, as acquired by children,
is part of a moral form of life (in which chairs play some role).

5.4  The only piecemeal approach to holism seems to be that of Brooks
(1991). He argues that it is better to use the world as its own model.
Human intelligence is too "complicated" for it to be possible to cut it
up in the right pieces to study and model. His "mobots" consist of
several layers which operate in parallel; each layer has its own "goal"
and its own visual input, but there is no "total" observation of the
environment. There is representation in the sense of covariation, but
not symbolic, conceptual representation. The lingering questions are,
of course: Will this bring us anything more than the intelligence of a
spider? What about learning? How will the evolutionary jump to
conceptual knowledge be made (cf Kirsh 1991b)? But these mobots really
exist in their world.

6.0  CONCLUSIONS.

6.1  All variants of the frame problem are special cases of the problem
of complete description (PCD): It is impossible to give the necessary
and sufficient conditions for something (e.g. for the occurrence of an
event, the definition of a concept).

6.2  It is a mistake to talk about the frame problem as primarily
concerning acting, reasoning, or justifying; it's a problem of
description in the first place. (The notorious robots who didn't manage
to save their spare batteries were not suffering from the frame
problem. Perhaps their designers were.)

6.3  There is no theoretical solution to the frame problem. The quest
for a theoretical solution presupposes the possibility of a complete
description. The latter idea is incoherent, but this is of little
relevance for AI:  Humans also manage without a theoretical solution.

6.4  It is a mistake to suggest that folk knowledge is broad but not
deep. It is deep in the sense of its holistic relation to the
subcognitive level. This undermines the theoretical intelligibility of
a piecemeal approach. Domain-restricted theoretical solutions to the
frame problem are not possible because each part presupposes the whole.

6.5. The extent to which a practical solution might be feasible (in
certain contexts) increases, in principle, in the direction: logicism,
logicism + learning, connectionism, mobotics. Practical "total"
solutions cannot be excluded: new forms of (artificial) life are
possible. Practical instruments are of course always possible. Whether
they are useful depends on the form of life in which they are put to use.

REFERENCES.

Boden, M.A. (ed.) (1990) The Philosophy of Artificial Intelligence.
Oxford:  Oxford University Press.

Brooks, R.A. (1991) Intelligence without representation. Artificial
Intelligence 47: 139-159.

Brown, F.M. (ed.) (1987) The Frame Problem in Artificial Intelligence.
Los Altos CA: Kaufmann.

Churchland, P.M. (1989) A Neurocomputational Perspective. Cambridge MA:
The MIT Press.

Clancey, W.J. (1991) The frame of reference problem in the design of
intelligent machines. In Architectures for Intelligence: The
Twenty-Second Carnegie Symposium on Cognition (K. vanLehn, ed.).
Hillsdale NJ: Lawrence Erlbaum, pp. 357-424.

Dennett, D. (1987) Cognitive wheels: The frame problem of AI. In:
Pylyshyn (1987) 41-64; also in Boden (1990) 147-170.

Dreyfus, H.L. and S.E. Dreyfus (1990) Making a mind versus modelling
the brain: Artificial intelligence back at a branch-point. in Boden
(1990) 309-333.

Dunn, J.M. (1989) The frame problem and relevant predication. In:
Knowledge Representation and Defeasable Reasoning (H. Kyburg et al.,
eds.). Dordrecht: Kluwer.

Fodor, J.A. (1987) Modules, frames, fridgeons, sleeping dogs, and the
music of spheres. In: Pylyshyn (1987) 139-149.

Ford, K.M. and P.J. Hayes (1991) Reasoning Agents in a Dynamic World:
The Frame Problem, Greenwich: JAI Press.

French, R.M. (1990) Subcognition and the limits of the Turing test.
Mind 99: 53-65.

Hayes, P.J. (1987) What the frame problem is and isn't. In: Pylyshyn
(1987) 123-138.

Hayes, P.J. (1992) Summary of "Reasoning Agents in a Dynamic World: The
Frame Problem" (Ford & Hayes 1991, Eds.) PSYCOLOQUY 3(59) frame-problem.1

Holland, J.H., K.J. Holyoak, R.E. Nisbett and P.T. Thagard, Induction:
Processes of Inference, Learning, and Discovery. Cambridge MA: The MIT
Press.

Kirsh, D. (1991a) Foundations of AI: the big issues. Artificial
Intelligence 47: 3-30.

Kirsh, D. (1991b) Today the earwig, tomorrow man?, Artificial
Intelligence 47: 161-184.

Lenat, D.B. and E.A. Feigenbaum (1991) On the thresholds of knowledge.
Artificial Intelligence 47: 185-250.

Lormand, E. (1990) Framing the frame problem. Synthese 82: 353-374.

Maloney, J.C. (1990) The Mundane Matter of Mental Language. Cambridge:
Cambridge University Press.

McDermott, D. (1987) We've been framed: Or, why AI is innocent of the
frame problem. In: Pylyshyn (1987) 113-122.

Pylyshyn, Z.W. (ed.) (1987) The Robot's Dilemma. Norwood NJ: Ablex
Publishing Co.

Ross, D. (1990) Against positing central systems in the mind.
Philosophy of Science 57: 297-312.

Van Brakel, J. (1991) Meaning, prototypes and the future of cognitive
science. Minds and Machines 1: 233-257.