Credit apportionment in rule-based systems: Problem analysis and algorithm synthesis.

Abstract

A rule-based system will be robust and intelligent if it is able to learn domain knowledge and adapt to its environment. These learning and adaptation processes can be guided by the system's past experience. In many cases, a rule-based system can obtain such experience through feedback (called payoffs) from the environment. The problem of apportioning these payoffs (representing credit or blame) to every rule in a rule-based system is called the credit-apportionment problem. In its pursuit to solve the credit-apportionment problem in rule-based systems (strictly speaking, in a subset of rule-based systems), this dissertation first develops a framework for the credit-apportionment process, which provides a formal basis for the problem analysis and algorithm synthesis. The framework includes (1) a system-environment model, which integrates the effects of payoffs with other relevant parts of a rule-based system to model various internal and external activities of the rule-based system and (2) principles of usefulness, which define the inherent usefulness of rule actions and provide the semantic aspect of the credit-apportionment process. Furthermore, this framework formulates the credit-apportionment problem as a problem of estimating and approximating the inherent usefulness from payoffs. Based on the framework, two criteria for the appropriateness of credit-apportionment algorithms have been identified. Furthermore, a bottom-up method has been developed for analyzing these algorithms under the criteria. This method starts the analysis of a credit-apportionment algorithm on a set of "building blocks" of patterns of credit-apportionment (syntactic representation of the credit-apportionment problem) and then extends the results to more and more complicated patterns. Using the bottom-up method, this dissertation has analyzed the bucket-brigade-like approach in solving the credit-apportionment problem. The analysis concluded that the bucket-brigade-like approach (i) is appropriate in solving local level credit-apportionment problems, but (ii) is inappropriate in solving global level credit-apportionment problems. Finally, a new credit-apportionment algorithm, the context-array bucket-brigade algorithm, has been developed. This algorithm improves the performance of the bucket-brigade-like approach in solving the global level credit-apportionment problems, while preserving the advantages of the approach in solving local level problems.