Knowledge-Based Systems in Artificial Intelligence (McGraw-Hill advanced computer science series)

Rating:
Summary: Of historical importance
Review: The AM machine, developed by Doug Lenat in 1976 in his Phd dissertation, was designed to invent mathematical concepts and engage in making mathematical conjectures in elementary set theory and number theory. In the first article of this book, and the only one that will be reviewed here, Lenat summarizes AM in the context of the theme of the book. The AM machine is not viewed anymore as being interesting (no pun intended), but readers who have an interest in automated mathematical discovery should read this article, both for its insights and because of its historical importance. Many of the approaches to automated mathematical discovery that came after AM were very similar to it, both in terms of the form of the reasoning patterns and the use of extensive knowledge bases in mathematics.

As Lenat describes it in his article, AM began with 115 elementary concepts such as sets and "bags", and was able to arrive at concepts such as "subset" and "disjoint set". It was also able to formulate concepts in number theory such as prime numbers and highly composite numbers. A concept in AM is given a "frame representation", where each frame has 25 "facets" and can have multiple entries for each facet. The facets could be definitions, algorithms, or examples of a concept, or generalizations or specializations of a concept, or conjectures involving a particular concept. A collection of tasks acting on a facet of a concept, and ordered by "interestingness," were then processed by AM. A task performs a particular action on the facet by searching through its knowledge base of 242 heuristics. AM then chooses the appropriate heuristic(s) for the task, and then performs any subtasks that are suggested by the heuristic(s).

A weighting scheme, consisting of an assignment of a numerical value, is applied to concepts, the individual facets, and the actions on concepts. This scheme is used to judge whether a concept, facet, or action is "interesting" in some sense. A formula is then used to calculate the "worth" of a task, this formula being dependent on a weighted sum of these numerical values and the actual number of reasons it counted for the judgment of "interestingness". The knowledge base of heuristics in AM included a collection of heuristics to be used for deciding the interestingness of a concept. One of these heuristics was that a concept is interesting if there are interesting conjectures about it. A concept is considered uninteresting if no examples or at best only a few examples of it can be found, even after repeated attempts by AM.

Several questions arise when considering the discovery process utilized by AM. One obvious one concerns the originality of the discoveries which it made. Were the concepts truly discovered or were they hidden behind the scenes in the elementary concepts? For example, was the idea of a subset already encoded in the elementary concepts? Frequently, a human was called upon to recognize the "rediscovery" of the concept of subset, but was this really necessary? Would AM have eventually discovered the concept of a subset, if given sufficient time? This brings up the general question as to whether a human could at all times be capable of serving as a tutor or advisor to the machine. What if the concepts are too obscure or complex for human understanding or able to be assimilated by a human on a reasonable time scale? In addition, a result might be interesting from the viewpoint of the machine, but be vacuous or completely uninteresting from a human standpoint. Should then the machine be thought of as being uncreative when this occurs? In the actual use of AM, the users were able to manipulate AM to make it reason in a particular direction. On the other hand, this issues would not be troubling if viewed from the standpoint of another machine who might be doing the "coaching". Receiving help from a human or otherwise may be viewed as a bias term for the learning/discovery process. This also would take into account the fact that research in mathematics does not take place in isolation, but instead in a "community of mathematicians".

Another issue concerns the need for doing proofs in mathematics. Typically, a result, in particular an interesting result, would not be judged as such unless there was a proof given for it. This of course excludes conjectures, which are generated quite frequently in the actual practice of mathematical discovery. The making of conjectures is thus certainly thought of as something that a machine purporting to be engaged in mathematical discovery should be able to do. However, it should also be expected to do proofs of some of the discovered concepts. Proofs however were never generated by the AM machine. Does this mean that it was not exhibiting true creativity? From another standpoint, it would be advantageous for AM to be able to engage in the construction of proofs, since, as every human mathematician knows, the actual proof of a mathematical result can frequently inspire more mathematical ideas and conjectures. Thus the construction of proofs would make AM more effective as an automated discovery machine.