[Home] [Tech Library]

5. EURISKO and markets

To apply EURISKO to set theory, for example, one would start it with a set of object-level heuristics representing basic concepts of set theory (such as set equality and union), meta-heuristics for creating plausible new concepts out of old ones (e.g., by removing a conjunct from a predicate to weaken it), and meta-heuristics that attempt to capture a sense of what is mathematically interesting (such as an unexpected coincidence). EURISKO's predecessor, AM, started with exactly this, and was able to discover (and judge interesting) in turn: whole numbers, addition, multiplication, factorization, primality, and Goldbach's conjecture.

(There has been some controversy over the sense in which AM can be said to have discovered these concepts, and whether it is a reproducible result. For a discussion of these issues, see [III]. Also, note that many of these results have been reproduced by Ken Haase's EURISKO-like program, CYRANO [22].)

In AM, meta-heuristics mutated and judged object-level-heuristics, but did not themselves evolve under each others' influence. This was changed in EURISKO: here both kinds of heuristics exist at the same level of the system and can operate on each other freely. This enabled the mechanisms of variation (including the representation language) and the selective pressures to evolve and adapt with the rest of the system.

5.1. Parasitic loops During a run of EURISKO, however, one meta-heuristic rose to the maximum interestingness value merely by listing itself as a creator of whatever heuristics were judged interesting. As a "creator" of such interesting heuristics, it was itself judged interesting. Lenat reports that EURISKO has, when run for long periods, consistently invented ways to enter infinite loops of one sort or another. This problem may be viewed as the evolution of parasites, of systems that consume resources while returning nothing of value.

Lenat has limited this problem by hand-tuning sets of meta-heuristics, and by placing certain meta-heuristics on a frozen meta-level protected from evolutionary modification. But doing this can solve the problem of parasitism only if all entities which assign interestingness are placed in this frozen meta-level. A major part of the system is thus unable to evolve beyond its initial design, and hence unable to adapt to unforeseen changes within the system. This type of solution loses much of the flexibility sought in the move from AM to EURISKO.

"Interestingness" is a standard of value which can be used to claim system resources; if evolving meta-heuristics are allowed to assert value-and hence to generate claims from nothing-then parasites can evolve. If direct self-reward is forbidden, jointly self-rewarding "conspiracies" would spontaneously arise. For example, if a heuristic is consistently being judged interesting by a particular meta-heuristic, it is an ESS for it to discover some way to feed some of the resulting resources back to that meta-heuristic, that is, to find a way to pay a "kickback" to a judge (not to influence the judge in its favor, but to increase a favorable judge's influence). This problem can also be seen as a "tragedy of the commons" [23]: processing resources are the commons, and since the cost of using them (in terms of forgone alternative uses, etc.) is borne almost exclusively by others, each entity has an incentive to gobble resources wantonly.

5.2. Conservation laws This dilemma can be avoided by imposing restrictions on value-assertion at a simple, foundational level, rather than restricting valuation to a static set of complex heuristics. How can this be accomplished? Biology and markets both have locally-conserved quantities (matter, energy, currency) that are measures of success, and both systems have steadily generated new, genuinely interesting results. Sterile self-reinforcement cannot lead to success, because it cannot bring in resources. This principle can be applied to EURISKO-like systems.

An attractive approach is reward based on a locally-conserved currency, used to pay for services and computational resources. This inhibits parasitism through stable foundations which themselves embody no knowledge of heuristics (other than this argument). In such a system, a heuristic must pay for processing and for services provided by other heuristics. Non-productive loops of mutually-rewarding heuristics then go broke, since (by conservation of currency) a group of heuristics can only gain net funds by receiving them from a solvent entity outside the group-an entity that, presumably, either receives or expects to receive some valuable service. A productive entity may unwittingly support an unproductive process, but competitive pressures will help weed out this behavior.

The elimination of unsupported, non-productive entities by letting them go broke is a robust result of a foundational constraint, not a chancy result of hand-tuned heuristics. It achieves its robustness and universality in the same manner as many physical principles: it relies on a conservation law, and hence is independent of subsystem boundaries and system structure.

5.3. A market-based EURISKO? Market mechanisms suggest how a EURISKO-like system could operate without level boundaries or protected sets of supervisory heuristics. In a system of this sort, when a heuristic is invoked it charges the user enough to pay the costs of providing service, plus a royalty that rewards the heuristic's creators. As users learn to make discriminating choices, heuristics will compete to maximize their performance per unit of system resources consumed. Meta-heuristics that create new heuristics will earn royalties from their creations to the extent that these creations prove useful. Where several heuristics are responsible for creating a given heuristic, they can be viewed as its "stockholders", splitting royalties (or dividends) according to a prior contractual agreement.

Rules for negotiating the terms of such agreements can themselves evolve; the proper division of rewards will itself be rewarded, since it will lead to the evolution of better subsystems. Being able to evolve better division of rewards is important for a capable learning system (see the discussion of genetic algorithms and connectionism in Appendix II of [I]).

The above has outlined how money circulates among heuristics, and how it is ultimately used to pay for processing resources. Where does this flow of money originate? The next section answers this first by re-introducing a protected meta-level, though one that avoids the above problems, and then by explaining how to remove this meta-level as well.

5.4. External funders and open systems In a closed, market-based EURISKO-like system, heuristics pay for the storage space and processor time they use; the funds collected are then recycled to fund computation. If entities external to the economic system control the re-introduction of funds, then the heuristics within the system will be selected for their effectiveness in solving the problem of meeting the criteria for funds allocation. Ultimately, these criteria represent the problem being posed to the system; they could be simple contingent rewards for solving problems.

The funding agency is outside the system, and so not subject to heuristic evolution. It might seem equivalent to Lenat's protected meta-level, but, unlike EURISKO, a system of this sort can contain a fully-capable set of evolving meta-heuristics. The external funders reward only end results; meta-heuristics inside the system can act as internal investors, accelerating the adaptation of the system to the externally-defined goals. Investors and the activities in which they invest all participate in the same one-level market system. Use of this sort of meta-level avoids freezing the criteria for judging intermediate results, or for judging the judges of intermediate results (this resembles suggestions for funding scientific research [24]).

The unobjectionable role of the external funding agency is clear when the system is considered as part of a broader economy, in which external human users provide the funding and hence the feedback. The evolution of programs is ultimately guided by human judgment of what constitutes good performance [VI]; in a market-based, EURISKO-like system, the "super- visory" heuristics that judge other heuristics would themselves be judged by people. This supervisory position entails no special privilege; it results from their role as entities directly funded by users. The EURISKO experience may also be viewed in this light. Lenat's protected meta-heuristics were not really immune from evolution: Lenat himself varied and selected them with respect to the behaviors they encouraged, and allocated physical processors to those versions of EURISKO which he judged more promising.

In a distributed system consisting of EURISKO-like nodes subcontracting to each other, the external funding agency of any one node can consist of other nodes (of course, this principle does not require separate machines). In an open computational market-one using real dollars and connected to the human market-participating humans may be thought of as the ultimate meta-heuristics. They will be the ultimate source and drain for the flow of funds in the system, and will be the ultimate source of variation (at least initially). However, they are in no sense protected meta-heuristics. The flow of real money, and the provision of actually useful software services, will provide an incentive for humans to work to make the system more useful, and for them to buy the useful services being offered (see "Agoric Systems in the Large" in [I]).

[Home] [Tech Library]