FRAME PROBLEM

A conundrum known as the frame problem within artificial intelligence concerns the application of knowledge about the past to draw inferences about the future. It requires distinguishing those properties that change across time against a background of those properties that do not, which thus constitute a frame (Charniak and McDermott 1985). From the point of view of philosophy it appears to be a special case of the problem of induction, which requests justification for drawing inferences about the future based on knowledge of the past. David Hume, in particular, suggested that one's expectations about the future are no more than habits of the mind and doubted that knowledge relating the future to the past was possible.

Bertrand Russell, a twentieth-century student of Hume's eighteenth-century problem, observed that this problem cannot be resolved merely by stipulation or by postulating that the future will be like the past. That the future will be like the past in every respect may be significant but it is also false. That the future will be like the past in some respect may be true but it is also trivial. The problem is to discover those specific respects in which the future will be like the past that provide justification for inferences to some outcomes rather than others, under the same initial conditions. That in turn suggests that the frame problem, like the problem of induction, depends for its solution on a defensible theory of natural laws that supplies a basis for linking the future to the past.

Background

The first mention of a problem by this name was by John McCarthy and Patrick J. Hayes, who advanced a solution—the situational calculus—that depends on making assumptions about "the complete state of the universe at an instant of time," where "the laws of motion determine, given a situation, all future situations" (1969, p. 477). The reference to time raises concerns with relativity but, more important, not every feature of the universe makes a difference to every other feature at a later time. If one draws a distinction between global and local situations, where global concerns the complete state of the universe at a time and local only specific parts thereof, then local situations may prove tractable even if global situations should prove to be intractable.

Other characterizations of the problem include keeping track of the consequences of an action, including changes that they entail for representations of the world (Hayes 1973), and as a process of updating databases in response to changes that occur in the world (Barr and Feigenbaum 1981). Some claim it is not the problem of justifying inferences but of finding appropriate ways to express them (Hayes 1991), while others discuss the importance of the problem in relation to robots (Dennett 1984). As Robert Hadley notices, researchers in artificial intelligence tend to adopt narrower definitions of the problem, while philosophers tend to take the frame problem "to include any problem whose solution is presupposed by a solution to the narrow problem" (1988, p. 34). Some authors characterize the problem as less about knowledge than about knowledge representation.

Worlds of Robots

The connection between actions, representations, and the problem of change arises in part from the desire to provide artificial human beings (or robots) with the directional capabilities to navigate their way around the world. If those robots act on the basis of maps—where the term is being used as a generic characterization for internal representations—then it becomes important to distinguish between permanent and transient features of those maps, which makes database updating important. And because robots may bring about changes in their environment through interaction, it becomes important to revise those maps to reflect those changes, to maintain the current relevance of those internal representations, where these concerns converge.

The same connections, however, also obtain for human beings as other things that act on the basis of beliefs as their internal representations of the world. When those beliefs are sufficiently accurate and complete, actions taken based on them may be expected to be more appropriate and less likely to fail than would otherwise be the case. Insofar as the frame problem revolves around knowledge of when things are going to change and when they are not going to change, it possesses general significance for natural humans and for artificial humans alike. Beliefs are true when they correspond to reality (as the way things are or as everything that is the case), and when they correspond to reality they provide an appropriate foundation for human action as well as for robotic behavior.

The suggestion has been made that the frame problem concerns common sense as a product of everyday experience in interacting with the world, based on the fact that often the course of events conforms to one's expectations (Hayes 1991, p. 72). The existence of habits of the mind, however, does not resolve the problem with respect to justifying those habits on the basis of experience in the past nor explain how one's beliefs about the future ought to be represented. Presumably, the problem of knowledge must be resolved to have knowledge to represent. The kind of knowledge that holds promise for solving these problems derives from studying those features of the world that remain constant across time as the objects of scientific inquiries rather than as the products of common sense. These properties are known as the laws of nature.

Laws of Nature

Laws of nature, unlike laws of society, cannot be violated or changed and require no enforcement. They must be distinguished from what are called accidental generalizations, which may be true as correlations that describe the history of the world but which could be violated and changed. If every Ferrari during the world's history happened to be red, then the generalization "all Ferraris are red" would be true, but it would not be a law, since there are processes and procedures, such as repainting a Ferrari, that would render it false. For a generalization to be lawlike, its falsity must be logically possible but not physically possible, precisely because there are no processes or procedures that could separate an attribute from its reference property, even though the possession of that attribute is not true merely as a matter of definition.

There appear to be several species of natural laws, including simple laws of nomic form and causal laws of different kinds (Fetzer 1981, 1990). That gold is malleable and that matches are ignitable are examples of simple laws, provided that those attributes are permanent. The selling price of gold, by comparison, at $500 an ounce, for example, is a transient attribute. These laws characterize properties that are possessed at one and the same time and do not explicitly imply changes across time. If the property of being malleable is a permanent property of gold, however, then gold has the causal properties that define malleability, including assuming different shapes at subsequent times as an effect of different forces at prior times. Thus, simple laws entail causal counterparts.

Causal Kinds

The conception advanced by McCarthy and Hayes (1969), according to which complete states of the universe determine subsequent complete states according to laws of motion, presumes that those laws are exclusively deterministic, where given a complete state of the universe S1 at time t1, one and only one complete successor state S2 is physically possible at t2. Gottfried Wilhelm Leibniz and Pierre Simon de Laplace advanced similar conceptions. However, if any of the parts of the world are governed by causal processes that are indeterministic (or probabilistic), more than one successor state, S2, S3, …, Sn may be physically possible at time t2. Simple examples may include flips of coins, tosses of dice, and draws of cards from decks, but that depends on the specificity of the conditions attending those events.

Draws of cards from decks, for example, are ontically deterministic in the sense that, given specific arrangements of the cards in the deck, one and only one specific card can be drawn. These draws are epistemically indeterministic in the sense that, as long as one adheres to the rules of the game, one does not know the specific arrangements and is consequently unable to predict the outcome. The situation is different with the laws of radioactive decay, however. For example, an atom of polonium-218 has a half-life of 3.05 minutes, which means that, during any specific 3.05 minute interval, it has a probability of decay of one-half. This implies that, for collections of polonium atoms, one can expect that, during any 3.05-minute interval, about half will decay without knowing which ones.

Types of Systems

Atoms of polonium-218 are closed systems for which there are no other properties that make any difference to their probability of decay than the length of temporal interval. Neither the weather, the day of the week, the presence or absence of observers—none of these factors affect the strength of this probability. In the case of flips of coins, tosses of dice, and draws of cards from decks there are other properties, such as the precise angular momentum imparted to a coin when flipped, which make it predictable with greater and greater precision, where condition F is relevant to outcome O under conditions C when it makes a difference to the probability outcome O, given C. Increasingly precise specifications of the relevant conditions that affect outcomes thus allow instances of epistemic indeterminism to be established as ontically deterministic.

The probabilities of outcome depend on and vary with the complete sets of factors that are present on any specific occasion. When coins are bent, dice are loaded, or decks are stacked, the probabilities of various outcomes are no longer what they would have been under normal conditions. It follows that the truth of a lawlike sentence depends on taking into account the presence or absence of every property whose presence or absence makes a difference to the outcome on any specific occasion, which has been called the requirement of maximal specificity (Fetzer 1981, 1990). Closed systems are systems that satisfy this requirement, which is why their behavior across time can be systematically anticipated on the basis of corresponding maximally specific causal laws.

Prediction

For closed systems, it is therefore possible to predict—either invariably or probabilistically—precisely how that system will behave over an interval of time t to t* (when those properties are instantiated at time t and the outcome occurs at t*), so long as the laws of systems of that kind are known. When either (1) the laws of systems of that kind are not known or (2) the description available for that system is not closed, however, then precisely how that system would behave over a corresponding interval of time t to t* cannot be predicted with—invariable or probabilistic—confidence, because essential information remains unknown. In those cases the frame problem cannot be solved; but, even given knowledge of those kinds, the representation problem remains.

Indeed, there are at least two dimensions to the problem, where the first concerns whether the system under consideration qualifies as an open or as a closed system in relation to the outcome of interest. In either case, one needs to have predicates in one's language to describe each of its relevant properties. The second concerns whether or not the system under consideration, even if it happens to be a closed system, requires a finite or an infinite set of predicates for its complete description. When the complete description of states of the universe requires infinitely many predicates, for example, because infinitely many properties need to be described relative to successive states of the universe, there are no solutions to frame problems for global situations. Those are restricted to closed systems appropriately describable by finite sets of predicates.

Semantic Issues

McCarthy and Hayes (1969) consider hypothetical situations that concern what would happen if specific events were to occur (such as the situation that would arise if Mr. Smith sold his car to Mrs. Jones, who has offered $250 for it). These situations are properly represented by subjunctive conditionals (concerning what would be the case, if something were the case) and counterfactuals (as subjunctive conditionals with false antecedents). However, this implies that, even envisioned primarily as a problem of representation, the solution to the frame problem entails solving some of thorniest issues in philosophical logic concerning intensional conditionals and possible-world semantics. A plausible solution involves distinguishing ordinary-language subjunctives from scientific conditionals elaborated in recent research (Nute 1975; Fetzer and Nute 1979, 1980).

The semantics that appears most appropriate for scientific conditionals and lawlike sentences is a form of maximal-change semantics rather than one of the varieties of minimal-change semantics proposed by Robert Stalnaker (1968) and by David Lewis (1979). Thus, while their semantics depend on assuming that possible worlds that differ from the actual world are as similar to the actual world as they could be, apart from the specific features being varied, the semantics assumed here—for the sake of exploring representational aspects of the frame problem—permits possible worlds to differ from the actual world in all respects except those specified by their maximally specific reference-property descriptions and the permanent properties that attend them. Subjunctives are true provided that, in every world in which their antecedents are true, their consequents are also true or would be true with constant probabilities.

Logical Form

An intensional calculus for the representation of lawlike sentences and causal conditionals of deterministic and probabilistic strength affords a possible framework for resolving the problem of representation (Fetzer and Nute 1979, 1980). Suppose that matches of kinds defined by chemical composition M are such that, when they are dry D, struck in fashion S, in the presence of oxygen O, then they light L. That could justify the lawlike claim, for every match x of kind M that is D and O, S-ing x at t1 would invariably bring about its L-ing at t2. That maximally specific antecedent could equally well be represented by various alternative formulations that included the same complete sets of relevant conditions, since adding oxygen when the other properties were present, for example, would bring about the outcome just as the striking of the match, when those other properties were present, would bring it about.

Employing the double arrow, ___ ⇒ …, as the subjunctive conditional sign and the causal double arrow, ___ n⇒ …, as the (probabilistic) causal conditional sign—where values of n range over u for deterministic cases and p (from zero to one) for probabilistic cases—then these lawlike relations could be formalized by means of a generalized conditional, (x)(t)[(Mxt & Dxt & Oxt) ⇒ (Sxt u⇒ Lxt*)], which would be read, "For all x and all t, if x were M and D and O at t, then S-ing x at t would bring about (invariably) L-ing x at t*" (where t* is a specific interval after t). An instance of this generalization for a specific object c at a specific time t1 would have the following logical form, (Mct1 & Dct1 & Oct1) ⇒ (Sct1 u⇒ Lct2), which would have logically equivalent variations, such as (Mct1 & Dct1 & Sct1) ⇒ (Oct1 u⇒ Lct2), and so on.

Scorekeeping

The conception of conversational scorekeeping was introduced by Lewis (1973) as a helpful technique for keeping track of assumptions that have been made within the context of an ordinary conversation. Donald Nute (1980), for example, discusses its application relative to conditionals that occur during ordinary language conversations. Suppose, for example, that, at one point in their conversation, Bill and Hillary agree that either she will run for the Senate (again) or she will run for president. If they later conclude that she is not going to run for the presidency, they are entitled to infer that she is going to run for the Senate, even if that conversation occurs weeks later, assuming the premise has not been withdrawn.

Analogously, for a computerized system with the capacity for the representation of conditionals, such as LISP or Prolog, for example, developing programs that reflect the laws of systems that interest project managers should be relatively straightforward. No matter when specific data enters the program and regardless of the specific order in which it is received, once the antecedent of the conditional has been satisfied, the program draws the inference with deterministic certainty or probabilistic confidence that an outcome of kind O either has occurred or may be expected to occur, given the temporal parameters that apply. The function cond in LISP, for example, appears to be appropriately adaptable for this purpose (Wilensky 1984, Fetzer 1991). Hayes (1991) raises the objection that cond supports inferences of the form modus ponens but not of the form modus tollens, but that is sufficient for deriving predictions.

Implementation

It appears to be the case that the frame problem can be solved, at least in principle, for closed systems involving only finite sets of relevant properties. Whether or not it can be solved in practice, of course, depends on the state of science and one's knowledge of systems and laws of the kind under consideration. The solution that has been presented here, of course, presupposes an account of the nature of laws of which Hume would not have approved. Hume adopted an epistemic principle that precluded inference to the existence of properties and relations, including lawful and causal connections, that are not directly accessible to experience. His narrow form of inductivism cannot justify inferences to the existence of laws by contrast with mere correlations. Fortunately, a more robust epistemology based on inference to the best explanation accommodates the discovery of natural laws, where hypotheses are empirically testable by means of severe attempts to refute them (Fetzer 1981, 1990).

In spite of his emphasis on the representational aspect of the frame problem, even Hayes (1991) acknowledges that a theory of causation is a necessary condition for its solution. During the course of their review of a recent collection of studies of the frame problem, Selmer Bringsjord and Chris Welty (1994) suggest that the frame problem presupposes a solution to the problem of induction, which agrees with the position presented here. Whether or not the frame problem can be solved depends on whether or not the problem of induction can be solved, which in turn depends on deep issues in ontology and epistemology. If the considerations outlined earlier are well founded, however, then the problem of induction and the frame problem are both capable of successful resolution, even including its representational dimensions.

See also Artificial Intelligence; Computationalism; Connectionism; Induction; Laws of Nature.

Bibliography

Barr, Avron, and Edward A. Feigenbaum. The Handbook of Artificial Intelligence. Vol. 1. Reading, MA: Addison-Wesley, 1981.

Bringsjord, Selmer, and Chris Welty. "Navigating through the Frame Problem." AI Magazine (Spring 1994): 69–72.

Charniak, Eugene, and Drew McDermott. Introduction to Artificial Intelligence. Reading, MA: Addison-Wesley, 1985.

Dennett, Daniel. "Cognitive Wheels: The Frame Problem in AI." In Minds, Machines, and Evolution, edited by Christopher Hookaway, 129–151. New York: Cambridge University Press, 1984.

Fetzer, James H. Artificial Intelligence: Its Scope and Limits. Dordrecht, Netherlands: Kluwer Academic, 1990.

Fetzer, James H. "The Frame Problem: Artificial Intelligence Meets David Hume." In Reasoning Agents in a Dynamic World: The Frame Problem, edited by Kenneth M. Ford and Patrick J. Hayes, 55–69. Greenwich, CT: JAI Press, 1991.

Fetzer, James H. Scientific Knowledge. Dordrecht, Netherlands: D. Reidel, 1981.

Fetzer, James H., and Donald Nute. "A Probabilistic Causal Calculus: Conflicting Conceptions." Synthese 44 (1980): 241–246.

Fetzer, James H., and Donald Nute. "Syntax, Semantics, and Ontology: A Probabilistic Causal Calculus." Synthese 40 (1979): 453–495.

Hadley, Robert. Review of The Robot's Dilemma: The Frame Problem in Artificial Intelligence, edited by Z. Pylyshyn. Canadian Philosophical Reviews 8 (1988): 33–36.

Hayes, Patrick J. "Commentary on 'The Frame Problem': Artificial Intelligence Meets David Hume." In Reasoning Agents in a Dynamic World: The Frame Problem, edited by Kenneth M. Ford and Patrick J. Hayes, 71–76. Greenwich, CT: JAI Press, 1991.

Hayes, Patrick J. "The Frame Problem and Related Problems in Artificial Intelligence." In Artificial and Human Thinking, edited by Alick Elithorn and David Jones, 45–59. New York: Elsevier, 1973.

Lewis, David. "Scorekeeping in a Language Game." Journal of Philosophical Logic 8 (1979): 339–359.

McCarthy, John, and Patrick J. Hayes. "Some Philosophical Problems from the Standpoint of Artificial Intelligence." In Machine Intelligence 4, edited by Bernard Meltzer and Donald Michie, 463–502. New York: American Elsevier, 1969.

Nute, Donald. "Conversational Scorekeeping and Conditionals." Journal of Philosophical Logic 9 (1980): 153–166.

Nute, Donald. "Counterfactuals and the Similarity of Worlds." Journal of Philosophy 72 (1975): 773–778.

Pylyshyn, Zenon W., ed. The Robot's Dilemma: The Frame Problem in Artificial Intelligence. Norwood, NJ: Ablex, 1987.

Stalnaker, Robert. "A Theory of Conditionals." In American Philosophical Quarterly Supplementary Monograph No. 2, 98–112. Oxford, U.K.: Basil Blackwell, 1968.

Wilensky, Robert. LISPcraft. New York: Norton, 1984.

James H. Fetzer (2005)