The Frame Problem (2004)(plato.stanford.edu)
plato.stanford.edu
The Frame Problem (2004)
https://plato.stanford.edu/entries/frame-problem/
11 comments
Heh. Reminds me of one of Lewis Carroll's sylogisms:
[Here is another opportunity, gentle Reader, for playing a trick on your innocent friend. Put the proposed Syllogism before him, and ask him what he thinks of the Conclusion.
He will reply “Why, it’s perfectly correct, of course! And if your precious Logic-book tells you it isn’t, don’t believe it! You don’t mean to tell me those tourists need to run? If I were one of them, and knew the Premisses to be true, I should be quite clear that I needn’t run—and I should walk!”
And you will reply “But suppose there was a mad bull behind you?”
And then your innocent friend will say “Hum! Ha! I must think that over a bit!”
You may then explain to him, as a convenient test of the soundness of a Syllogism, that, if circumstances can be invented which, without interfering with the truth of the Premisses, would make the Conclusion false, the Syllogism must be unsound.]
Premise A: "No one, who means to go by the train and cannot get a conveyance, and has not enough time to walk to the station, can do without running";
Premise B: "This party of tourists mean to go by the train and cannot get a conveyance, but they have plenty of time to walk to the station".
Does the conclusion "This party of tourists need not run" hold?
[Here is another opportunity, gentle Reader, for playing a trick on your innocent friend. Put the proposed Syllogism before him, and ask him what he thinks of the Conclusion.
He will reply “Why, it’s perfectly correct, of course! And if your precious Logic-book tells you it isn’t, don’t believe it! You don’t mean to tell me those tourists need to run? If I were one of them, and knew the Premisses to be true, I should be quite clear that I needn’t run—and I should walk!”
And you will reply “But suppose there was a mad bull behind you?”
And then your innocent friend will say “Hum! Ha! I must think that over a bit!”
You may then explain to him, as a convenient test of the soundness of a Syllogism, that, if circumstances can be invented which, without interfering with the truth of the Premisses, would make the Conclusion false, the Syllogism must be unsound.]
People always look at me weird when I confidently answer "maybe" to real world instances of this kind of scenario.
It's always the same "if this is true, then that, so because this is true, then that must be true." and I say "maybe" and defend with "Your premise might be situationally correct, but we've no way of knowing whether it's True." followed by some such Bulls, though I usually use "what if they got hit by a car".
It's always the same "if this is true, then that, so because this is true, then that must be true." and I say "maybe" and defend with "Your premise might be situationally correct, but we've no way of knowing whether it's True." followed by some such Bulls, though I usually use "what if they got hit by a car".
> resolved this well enough. Opinions?
Not at all resolved. If anything it is worse than before as we begin to understand it better, and now there are different versions of it that cover representation, relevance, epistemics. Pivoting "away" from logic just relocates it again. Arguably the whole challenge of neurosymbolics is (still) getting a persistent sidecar for logic bolted onto something like a language model. We actually have fairly decent autoformalizers (!!) and we still can't make that work very well in general.
From one perspective, the frame problem is pretty closely related to the "binding problem", causal reasoning and ramifications in general, and relevance is central to all. We have good pure formalisms for relevance, epistemics, and do-logic too. But we can't get language models to drive them very well, and language models alone are terrible at trying to do this sort of thing natively (see distractor sensitivity, mediated causality and multi-hop reasoning with implicit bridges).
Neurosymbolics probably is the key, but until there's more traffic between old-school and new we're facing the same old problems. When/if there's real progress.. I think we'd know. It may or may not be AGI-complete but the improvements for things like long-horizon and truly out-of-distribution planning would probably be immediate, obvious, and jaw dropping
Not at all resolved. If anything it is worse than before as we begin to understand it better, and now there are different versions of it that cover representation, relevance, epistemics. Pivoting "away" from logic just relocates it again. Arguably the whole challenge of neurosymbolics is (still) getting a persistent sidecar for logic bolted onto something like a language model. We actually have fairly decent autoformalizers (!!) and we still can't make that work very well in general.
From one perspective, the frame problem is pretty closely related to the "binding problem", causal reasoning and ramifications in general, and relevance is central to all. We have good pure formalisms for relevance, epistemics, and do-logic too. But we can't get language models to drive them very well, and language models alone are terrible at trying to do this sort of thing natively (see distractor sensitivity, mediated causality and multi-hop reasoning with implicit bridges).
Neurosymbolics probably is the key, but until there's more traffic between old-school and new we're facing the same old problems. When/if there's real progress.. I think we'd know. It may or may not be AGI-complete but the improvements for things like long-horizon and truly out-of-distribution planning would probably be immediate, obvious, and jaw dropping
Thanks for the reply and pointers.
The intro to TFA> To most AI researchers, the frame problem is the challenge of representing the effects of action in logic without having to represent explicitly a large number of intuitively obvious non-effects. But to many philosophers, the AI researchers' frame problem is suggestive of wider epistemological issues. Is it possible, in principle, to limit the scope of the reasoning required to derive the consequences of an action? And, more generally, how do we account for our apparent ability to make decisions on the basis only of what is relevant to an ongoing situation without having explicitly to consider all that is not relevant?
Near as I can tell separation logic (suitably generalised/tamed/adapted to suit the system of interest/tools in use) addresses all these concerns. I'm not claiming it solves every last variant of the frame problem that anyone has ever considered; just that it seems to address the classical concerns about modularly specifying the effects of actions.
Take, for instance, the last question: separation logic models this by explicitly splitting the state (of the system of interest) into "relevant" and "not relevant" via separating conjunction (etc) and the suggestively-named "Frame" axiom takes care to preserve the "not relevant" part.
This partially addresses epistemics too, but I see that an action may affect things that I am not aware of. Though perhaps that is more of a modelling issue than a linguistic one.
I have no clue what does and does not work well with LLMs -- I'm just talking about explicit symbolic representation and (computer assisted/mechanised) reasoning; GOFAI but from a program logic perspective. Are you claiming that separation logic is unusable by LLMs? Or that it isn't helpful for capturing some essential aspects of framing in real-world problems?
The intro to TFA> To most AI researchers, the frame problem is the challenge of representing the effects of action in logic without having to represent explicitly a large number of intuitively obvious non-effects. But to many philosophers, the AI researchers' frame problem is suggestive of wider epistemological issues. Is it possible, in principle, to limit the scope of the reasoning required to derive the consequences of an action? And, more generally, how do we account for our apparent ability to make decisions on the basis only of what is relevant to an ongoing situation without having explicitly to consider all that is not relevant?
Near as I can tell separation logic (suitably generalised/tamed/adapted to suit the system of interest/tools in use) addresses all these concerns. I'm not claiming it solves every last variant of the frame problem that anyone has ever considered; just that it seems to address the classical concerns about modularly specifying the effects of actions.
Take, for instance, the last question: separation logic models this by explicitly splitting the state (of the system of interest) into "relevant" and "not relevant" via separating conjunction (etc) and the suggestively-named "Frame" axiom takes care to preserve the "not relevant" part.
This partially addresses epistemics too, but I see that an action may affect things that I am not aware of. Though perhaps that is more of a modelling issue than a linguistic one.
I have no clue what does and does not work well with LLMs -- I'm just talking about explicit symbolic representation and (computer assisted/mechanised) reasoning; GOFAI but from a program logic perspective. Are you claiming that separation logic is unusable by LLMs? Or that it isn't helpful for capturing some essential aspects of framing in real-world problems?
Challenging questions for short answer format! But there's a pattern with this stuff that's always mostly the same. Specialist logics work great on the happy path, but when you dig into it, they always work because of a bunch of simplifying assumptions that keep us within a zone that's sound/complete/decidable.
Roughly speaking GOFAI usually "solves" the frame problem only to the extent it accepts hard limits on the domain of discourse, which trade has bad consequences for expressiveness and/or the ability to update things like axioms and beliefs. We tolerate this because if we don't then we're off the happy path and basically doomed. Then time passes, we forget that we agreed to tradeoffs and float the idea of possible generalizing/taming/adapting ;)
Not expert enough on SL to really connect the dots, and it's complicated by the fact that the BI family is a weird place that is in some sense neither monotonic nor non-monotonic. Two main issues though. The first is the applicability thing, because lots of stuff just will not allow clean partitions anyway (back to causal and ramifications). Even in the restricted domain of program-logic, if we're talking side-effects and outside the world of theorem provers or something, the real domain is causal logic anyway, plus all the irreducible difficulties of distributed consensus, etc. The second issue is the partition itself, which is fine if you bring it with you, but it has to be discovered otherwise. For problems of unknown structure, I'm guessing that immediately puts you in the position of looking at the exploding space of all possible partitions. Adding an algebraic operator makes for very clean notation but in practice you can't just wave away how difficult that actually is, if it's even decidable in general (and I'm guessing it's not).
Turing/Godel/Tarski will all have their due.. so back to the argument for hybrid systems. Heuristics can prune a search space, but what can't be decided ultimately needs some kind of intuition. Which isn't to say that we don't need all kinds of sophisticated heuristics and backtracking and the rest, but just that we need everything we can get for hard problems. Another way of looking at it, GOFAI and new-wave AI are both pretty bad at generalizing but since this happens in ways that are sort of complementary, we can get a lot of leverage by combining them.
Roughly speaking GOFAI usually "solves" the frame problem only to the extent it accepts hard limits on the domain of discourse, which trade has bad consequences for expressiveness and/or the ability to update things like axioms and beliefs. We tolerate this because if we don't then we're off the happy path and basically doomed. Then time passes, we forget that we agreed to tradeoffs and float the idea of possible generalizing/taming/adapting ;)
Not expert enough on SL to really connect the dots, and it's complicated by the fact that the BI family is a weird place that is in some sense neither monotonic nor non-monotonic. Two main issues though. The first is the applicability thing, because lots of stuff just will not allow clean partitions anyway (back to causal and ramifications). Even in the restricted domain of program-logic, if we're talking side-effects and outside the world of theorem provers or something, the real domain is causal logic anyway, plus all the irreducible difficulties of distributed consensus, etc. The second issue is the partition itself, which is fine if you bring it with you, but it has to be discovered otherwise. For problems of unknown structure, I'm guessing that immediately puts you in the position of looking at the exploding space of all possible partitions. Adding an algebraic operator makes for very clean notation but in practice you can't just wave away how difficult that actually is, if it's even decidable in general (and I'm guessing it's not).
Turing/Godel/Tarski will all have their due.. so back to the argument for hybrid systems. Heuristics can prune a search space, but what can't be decided ultimately needs some kind of intuition. Which isn't to say that we don't need all kinds of sophisticated heuristics and backtracking and the rest, but just that we need everything we can get for hard problems. Another way of looking at it, GOFAI and new-wave AI are both pretty bad at generalizing but since this happens in ways that are sort of complementary, we can get a lot of leverage by combining them.
>how do we account for our apparent ability to make decisions on the basis only of what is relevant to an ongoing situation without having explicitly to consider all that is not relevant?
I don't think we really have such an ability. Hence microplastics.
I don't think we really have such an ability. Hence microplastics.
Your comment blows my mind a bit. Of course we do! Here I am, having decided to blithely parade my ignorance here without any concern whatsoever for what is relevant (what the implications may be) ...
... but on the other hand I think you're saying that we can never fully account for all the relevant stuff or what it entails for any number of reasons, not the least being that we don't know (and can't know) what all the consequences are.
And yet we still need to make decisions, and winnow what we base those on.
... but on the other hand I think you're saying that we can never fully account for all the relevant stuff or what it entails for any number of reasons, not the least being that we don't know (and can't know) what all the consequences are.
And yet we still need to make decisions, and winnow what we base those on.
If I understand it correctly, more advanced logics (based around state transitions) doesn't have this problem (TLA+ etc.)
Another way around this is that things that aren't coherent enough to be described by a finite set of inertial propositions simply aren't perceivable.
tl;dr: Since the AI people have lost interest in the frame problem (because they think they can ignore it like the new wave folks, work around it like Fodor, or like Shanahan, think of it as solved) the philosophers would like it back please.
At least some of the problem was due to people unnecessarily restricting themselves to first-order logic for knowledge representation, as advocated by John McCarthy [2].
[1] https://en.wikipedia.org/wiki/Separation_logic
[2] see e.g. https://www-formal.stanford.edu/jmc/concepts.pdf