“Properties of the Bucket Brigade Algorithm”, 1985 (; backlinks):
The bucket brigade algorithm is designed to solve the apportionment of credit problem for massively parallel, message-passing, rule-based systems. The apportionment of credit problem was recognized and explored in one of the earliest important works in machine learning (1959).
In the context of rule-based systems it is the problem of deciding which of a set of early acting rules should receive credit for “setting the stage” for later, overtly successful actions. In the systems of interest here, in which rules conform to the standard condition/action paradigm, a rule’s overall usefulness to the system is indicated by a parameter called its strength.
Each time a rule is active, the bucket brigade algorithm modifies the strength so that it provides a better estimate of the rule’s usefulness in the contexts in which it is activated…under the bucket brigade algorithm only some of the satisfied rules are activated. Each satisfied rule makes a bid based in part on its strength, and only the highest bidders become active (thereby posting the messages specified by their action parts). The size of the bid depends upon both the rule’s strength and the specificity of the rule’s conditions.
…The profitability of any chain of consumers thus depends upon their relevance to the ultimate consumer. Stated more directly, the profitability of a classifier depends upon its being coupled into sequences leading to payoff.
…One of the most important consequences of the bidding process is the automatic emergence of default hierarchies in response to complex environments. For rule-based systems a “default” rule has two basic properties:
It is a general rule with relatively few specified properties and many “don’t cares” in its condition part, and
when it wins a competition it is often in error, but it still manages to profit often enough to survive.
It is clear that a default rule is preferable to no rule at all, but, because it is often in error, it can be improved. One of the simplest improvements is the addition of an “exception” rule that responds to situations that cause the default rule to be in error. Note that, in attempting to identify the error-causing situations, the condition of the exception rule specifies a subset of the set of messages that satisfy the default rule. That is, the condition part of the exception rule refines the condition part of the default rule by using additional identifying bits (properties). Because rule discovery algorithms readily generate and test refinements of existing strong rules, useful exception rules are soon added to the system.
…An appropriate rule discovery algorithm, such as a genetic algorithm, will soon couple more detailed rules to the epoch-marking rule. And, much as in the generation of a default hierarchy, these detailed rules can give rise to further refined offspring. The result is an emergent plan hierarchy going from a high-level sketch through progressive refinements yielding ways of combining progressively more detailed components (rule clusters) to meet the particular constraints posed by the current state of the environment. In this way a limited repertoire of rules can be combined in a variety of ways, and in parallel, to meet the perpetual novelty of the environment.