Machine Intelligence 1 (1967) (eds N. Collins and D. Michie) Oliver & Boyd, Edinburgh Machine Intelligence 2 (1968) (eds E. Dale and D. Michie) Oliver & Boyd, Edinburgh (1 and 2 published as one volume in 1971 by Edinburgh University Press) (eds N. Collins, E. Dale, and D. Michie) Machine Intelligence 3 (1968) (ed. CLARENDON PRESS - OXFORD 1991 Oxford University Press, Walton Street, Oxford 0X2 6DP Oxford New York Toronto Delhi Bombay Calcutta Madras Karachi Petaling Jaya Singapore Hong Kong Tokyo Nairobi Dar es Salaam Cape Town Melbourne Auckland and associated companies in Berlin lbadan Oxford is a trade mark of Oxford University Press Published in the United States by Oxford University Press, New York C J. E. Hayes, D. Michie, and E. Tyugu, 1991 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior permission of Oxford University Press British Library Cataloguing in Publication Data Machine intelligence. ISBN 0-19-853823-5 Library of Congress Cataloging in Publication Data Machine intelligence 12: towards an automated logic of human thought /edited by J. E. Hayes, D. Michie, and It is a pleasure to contribute an introduction to this twelfth volume of the international Machine Intelligence series. My own work has, at times, cast me in the scientific roles of experimenter, instrumentation designer, and administrator.

Duce uses a set of transformations of propositional Horn clauses which successively compress the example material on the basis of generalizations and the addition of new terms. In the following descriptions of three of the six Duce operators, lower-case Greek letters stand for conjunctions of propositional symbols.

Perhaps the most promising and yet most difficult application of machine learning is in the area of scientific discovery: 'the most technically gripping challenge,... will be how to spread the computer wave from the front end of the scientific process, the telescopes, microscopes,... spark chambers, and the like, back to recognition and reasoning processes by which the chaos of data is finally consolidated into orderly discovery' (Michie 1982). For scientific discovery, machine learning is viewed as a tool to aid working scientists in forming theories from data.

They produce one set of rules from one set of data and have no memory which permits them to add to a knowledge base by further learning. Incremental learning systems remember the concepts which they have learned and can use them for further learning and problem solving. Some examples are, CONFUCIUS (Cohen 1978) and Marvin (Sammut 1981). These programs build a model of their task environment through successive learning experiences which require interaction with the environment. The task that we consider in this paper involves a program learning to control an agent in a reactive environment. This is an environment where changes occur in response to actions. Agents other than the learner may be present. As an agent accumulates experience, it constructs a world model or theory of behaviour which can be used to predict the outcome f Present address: Department of Computer Science, University of New South Wales, Sydney, Australia.

In this paper we will be concerned with such reasoning in its most general form, that is, in inferences that are defeasible: given more information, we may retract them. The purpose of this paper is to introduce a form of non-monotonic inference based on the notion of a partial model of the world. We take partial models to reflect our partial knowledge of the true state of affairs. We then define non-monotonic inference as the process of filling in unknown parts of the model with conjectures: statements that could turn out to be false, given more complete knowledge. To take a standard example from default reasoning: since most birds can fly, if Tweety is a bird it is reasonable to assume that she can fly, at least in the absence of any information to the contrary. We thus have some justification for filling in our partial picture of the world with this conjecture. If our knowledge includes the fact that Tweety is an ostrich, then no such justification exists, and the conjecture must be retracted.

A problem simplification approach that generates heuristics for constraint-satisfaction problems ' 125 R. DECHTER and J. PEARL 7. The relation between programming and specification languages with particular reference to Anna 157 A. D. MCGETTRICK and J. G. STELL LOGIC PROGRAMMING TOOLS AND APPLICATIONS 8. YAPES: yet another PROLOG expert system Decision trees and multi-valued attributes 305 J. R. QUINLAN 14. RuleFactory: a new inductive learning shell 319 S. RENNER 15.

It provides inference and explanation facilities, and incorporates a novel form of plausible inference. YAPES is a specialized interpreter for logic programs. Figure 1 illustrates its top level structure. A PROLOG interpreter (or compiler) executes such programs consisting of sets of Horn clauses, a form of first-order logic. The YAPES system also executes such programs, as well as programs in an extended version of Horn clause logic which uses certainties as truth values, rather than just true and false.

Recognition of three-dimensional objects, puzzle solving, electronic circuit analysis and truth-maintenance systems are examples of such problems, and these are normally solved by various versions of backtrack search. In this work we show how advice can be automatically generated to guide the order in which the search algorithm assigns values to the variables, so as to reduce the amount of backtracking. The advice is generated by consulting relaxed models of the subproblems created by each value-assignment candidate. The relaxed problems are chosen to yield backtrack-free solutions, and the information retrieved from these models induces a preference order among the choices pending in the original problem.