With the exception of CLS, the evolutionary strategy advocated by Michalski (1985) and others (e.g., Schlimmer & Fisher, 1986; Simon, 1969) is reflected in the learning systems of Section 3.2. Each system limits computational requirements by making local changes to the knowledge base in response to misclassified observations. Over a sequence of observations, the knowledge base evolves into a set of concepts that consistently (or optimally) classify observations.
It is informative to view incremental learning in terms of a dominant AI paradigm: search. In particular, Mitchell (1982) has characterized a number of learning systems in terms of their search strategies (e.g., breadth-first, depth-first). Viewed as a search task, each of the systems of Section 3.2 maintains exactly one copy of the knowledge base throughout learning. As such, they eliminate the possibility of chronological backtracking as a mechanism for resolving inconsistencies. Rather, they rely on a control strategy much like hill climbing, which is computationally economical, but without chronological backtracking this strategy can lead to well-known problems (Rich, 1983). To avoid these problems, a belief revision-like process of dependency-directed backtracking (Doyle, 1979) is employed to modify only those portions of the knowledge base that cause apparent problems.
CLS, incremental AQ, and GEM insist on perfect consistency between the environment and knowledge base. As such, they invoke dependency-directed backtracking with each classification, albeit inefficiently by TMS standards. In contrast, STAGGER and ID4 are motivated by the assumption that perfect consistency may not be realizable. Rather, optimal (perhaps perfect) prediction accuracy is the goal. Backtracking is not invoked following each misclassification, but only after some body of evidence suggests that such a move is warranted. STAGGER demonstrates that this strategy also allows the system to distinguish and track environmental changes. Viewed from a larger context, ID4 and STAGGER try to minimize the backtracking requirements of a problem-solving system that would depend on their learned knowledge (cf. Figure 1). This view also fits COBWEB, which dynamically identifies default values.
Limited experimentation (Reinke & Michalski, 1986; Schlimmer & Fisher, 1986) suggests that a hill-climbing/local-revision strategy approximates search-intensive systems in terms of concept quality, without the associated overhead of maintaining multiple copies of the knowledge base or of having to `recompute' consistent portions of the knowledge base. Fisher (1987b, c) and Schlimmer (1987a) explicitly point to the effectiveness of this incremental strategy on computational grounds. Langley, Gennari, and Iba (1987) and Shrager (1987) imply that similar strategies model many aspects of human learning.