MULLEN@SUMEX-AIM.ARPA (07/24/84)
From: Juanita Mullen <MULLEN@SUMEX-AIM.ARPA>
[Forwarded from the Stanford SIGLUNCH distribution by Laws@SRI-AI.]
DATE: Friday, July 27, 1984
LOCATION: Chemistry Gazebo, between Physical & Organic Chemistry
TIME: 12:05
SPEAKER: Tom Dietterich
Heuristic Programming Project
Stanford University
TOPIC: Learning About Systems That Contain State Variables
It is difficult to learn about systems that contain state variables
when those variables are not directly observable. This talk
formalizes this learning problem and presents a method called the
iterative extension method for solving it. In the iterative extension
method, the learner gradually constructs a partial theory of the
state-containing system. At each stage, the learner applies this
partial theory to interpret the I/O behavior of the system and obtain
additional constraints on the structure and values of its state
variables. These constraints can be applied to extend the partial
theory by hypothesizing additional internal state variables. The
improved theory can then be applied to interpret more complex I/O
behavior. This process continues until a theory of the entire system
is obtained. Several sufficient conditions for the success of this
method will be presented including (a) the observability and
decomposability of the state information in the system, (b) the
learnability of individual state transitions in the system, (c) the
ability of the learner to perform synthesis of straight-line programs
and conjunctive predicates from examples and (d) the ability of the
learner to perform theory-driven data interpretation. The method is
being implemented and applied to the problem of learning UNIX file
system commands by observing a tutorial interaction with UNIX.