Experiments on the frame problem in induction
Ramón P. Otero · 2001
When describing the behavior of a dynamic system|or an agent interacting within an evolving domain|sometimes the formalism of choice is based on automata. To cope with these domains machine learning has a long trend on learning automata. Automata-based descriptions have good properties, namely, clear understanding of the formalism and ecient algorithms for inference. But there are also drawbacks: the diculty on extending a description and the huge size that is needed for actual domains. These drawbacks can be seems as a manifestation of low declarativeness. This gave rise to the introduction of action formalisms in which logic is used as the base formalism. Thanks to the properties of logic, the two mentioned drawbacks of automata are not present. The aim of action formalisms is nding a concise and highly modular description of the transition relation of the system. This task turned out not easy and several dicult problems have been identied, most prominently the frame problem. It is not easy to concisely represent in logic that the features of a system not aected by the current action must persist in the situation after performing the action. Only logics with nonmonotonic consequences have been able to solve the frame problem. The need to work within nonmonotonic formalisms might explain the few attention the ML community paid to learning action descriptions. Logic-based learning, ILP [2], would be a framework easily applicable to learning actions if it were dened for normal logic programs, i.e. including negation as failure. In this work we begin with an study on the relationship between the frame problem and its solutions, and ILP. Then we propose a framework for inducing action descriptions from an incomplete set of history narratives of the behavior of the system. This includes incomplete examples on the initial situation and missing examples along each narrative. This framework extends recent results on learning action [1], but also introduces a dierent