The problem of expensive chunks and its solution by restricting expressiveness.


"Chunking, a simple experience-based learning mechanism, is Soar's only learning mechanism. Chunking creates new items of information, called chunks, based on the results of problem-solving and stores them in the knowledge base. These chunks are accessed and used in appropriate later situations to avoid the problem-solving required to determine them. It is already well-established that chunking improves performance in Soar when viewed in terms of the subproblems required and the number of steps within a subproblem. However, despite the reduction in number of steps, sometimes there may be a severe degradation in the total run time. This problem arises due to expensive chunks, i.e., chunks that require a large amount of effort in accessing them from the knowledge base. They pose a major problem for Soar, since in their presence, no guarantees can be given about Soar's performance.In this article, we establish that expensive chunks exist and analyze their causes. We use this analysis to propose a solution for expensive chunks. The solution is based on the notion of restricting the expressiveness of the representational language to guarantee that the chunks formed will require only a limited amount of accessing effort. We analyze the tradeoffs involved in restricting expressiveness and present some empirical evidence to support our analysis."Machine Learning, 5, 299-348.

Empirical Explorations with the Logic Theory Machine: A Case Study in Heuristics


This is a case study in problem-solving, representing part of a program of research on complex information-processing systems. We have specifieda system for finding proofs of theorems in elementary symbolic logic, and by programming a computer to these specifications, have obtained empirical data on the problem-solving process in elementary logic. The program is called the Logic Theory Machine (LT); it was devised to learn how it is possible to solve difficult problems such as proving mathematical theorems, discovering scientific laws from data, playing chess, or understanding the meaning of English prose.The research reported here is aimed at understanding the complexp rocesses (heuristics) that are effective in problem-solving. Hence, we are not interested in methods that guarantee solutions, but which require vastamounts of computation. Rather, we wish to understand how a mathematician, for example, is able to prove a theorem even though he does not know when he starts how, or if, he is going to succeed.Proceedings of the Western Joint Computer Conference, 15:218-239. Reprinted in Feigenbaum and Feldman, Computers and Thought (1963).