Abstract
In the early development of machine learning, most algorithms were designed to model "pure functions"—systems where a specific input consistently produces the same output. However, real-world computational and biological systems often possess internal state variables that are unobservable to an external learner. This paper, originally presented at the 1984 AAAI proceedings, introduces the Iterative Extension Method, a framework for inferring these hidden states by iteratively refining a partial theory of the system's behavior.
Introduction
By 1984, machine learning research had made significant strides in pattern recognition and function mapping. Yet, a major gap remained: how can a machine learn the behavior of a system like a text editor or an operating system, where the result of a command depends entirely on previous interactions? To a learner unaware of internal state, such systems appear inconsistent or even random. For example, in a UNIX environment, the command rm file might succeed or fail depending on the current directory and file permissions—variables that may not be explicitly visible in every transaction.
Thomas Dietterich proposed that instead of attempting "one-shot" learning from a batch of data, a learner should build a model incrementally. By using current knowledge to interpret new data, the learner can hypothesize the existence of hidden variables to resolve contradictions in its observations.
The Iterative Extension Method
The core of this research is the Iterative Extension Method, a greedy algorithm that constructs a system theory through successive refinement. The process follows five primary stages:
- Initial Theory ($T_0$): The learner begins with a null or extremely basic theory of the system.
- Theory-Driven Interpretation: The learner applies its current partial theory to a training trace (a sequence of inputs and outputs). It attempts to infer what the hidden state variables must have been at each step to make the observed behavior consistent with the theory.
- Gap Identification: The learner identifies specific data points or transitions that the current theory cannot explain.
- Heuristic Hypothesis Generation: To bridge these gaps, the system employs specific heuristics to suggest new state variables or procedural logic:
- Constant-Change-Constant: If behavior shifts from one steady state to another, the learner assumes a state variable has changed.
- Toggle Rule: If the same input consistently flips the system between two distinct behaviors, the learner hypothesizes a boolean "toggle" variable.
- Information Flow: If a value provided as an input appears as an output much later in the trace, the learner assumes the system contains a variable to store that specific value.
- Refinement ($T_{i+1}$): The new variable is integrated into the theory, and the process repeats until the theory accounts for the entire training trace.
Experimental Evaluation
The method was evaluated using two distinct simulations designed to test its ability to reverse-engineer hidden logic.
The Checking Account Simulation
The first test involved a PASCAL-like program simulating a bank account. The system managed a balance and a hidden LIMIT variable (an overdraft limit). While the LIMIT was never directly outputted, it governed whether certain transactions were approved. Through the Iterative Extension Method, the learner successfully inferred the existence of the LIMIT variable and the logic of the OK command, which modified that limit, solely by observing I/O pairs.
The UNIX Tutorial Trace (EG System)
The second evaluation utilized a system called EG to learn the behavior of the UNIX file system. The learner was provided with a "seed" theory (basic knowledge of ls and type) and the syntax of various commands. It then observed a tutorial trace of 13 commands, including mv, cp, rm, and mkdir. By applying its heuristics, EG successfully modeled how these commands modified the hidden directory structure, effectively learning the procedural theory for the file system's state transitions.
Discussion and Key Insights
Dietterich’s work highlighted several critical concepts for state-based learning:
- Learning as an Iterative Loop: Knowledge is not just the end product of learning but a tool used during the learning process to unlock more complex data.
- State Decomposability: The method relies on the assumption that the system is decomposable—meaning parts of the system can be isolated and learned without being obscured by unrelated side effects.
- Occam’s Razor in State Discovery: The algorithm follows a greedy minimization approach, attempting to explain the maximum amount of behavior with the minimum number of new state variables.
Limitations and Future Directions
Despite its success, the 1984 study identified several limitations. The method is highly sensitive to the structure of the training data; it requires a "tutorial-style" sequence where concepts are introduced progressively rather than a random set of interactions. Furthermore, reasoning backward through a partial program to infer state values can lead to a combinatorial explosion of possible interpretations, limiting the method's scalability.
Dietterich concluded by suggesting that future systems should move from passive observation to active experimentation. By allowing the learner to generate its own inputs to test specific hypotheses about hidden states, the ambiguity of the training trace could be significantly reduced.
Conclusion
"Learning About Systems That Contain State Variables" remains a foundational text in the transition from simple supervised learning to the modeling of complex, dynamic environments. It demonstrated that even hidden, internal complexities could be systematically unmasked through iterative hypothesis generation and heuristic reasoning.
Summary updated