KDD Nuggets #6 -- November 11, 1993 Contents: * Wray Buntine: Interestingness via decision theory * Gregory Piatetsky-Shapiro: Tracking viewers for marketing databases * Gregory Piatetsky-Shapiro: PC AI Review of Tools for Data Mining * Saso Dzeroski: Book Announcement-Inductive Logic Programming The KDD Nuggets is an informal list for the dissemination of information relevant to Knowledge Discovery in Databases (KDD), such as announcements of conferences/workshops, tool reviews, publication announcements/reviews, application success/failure stories, interesting ideas, outrageous opinions, anecdotes, etc. If you have such a contribution, please email it to kdd%eureka@gte.com Mail requests to be added/deleted also to kdd%eureka@gte.com. -- Gregory Piatetsky-Shapiro -------------------------------------------------- From: Wray Buntine Subject: KDD Nuggets #5 -- Oct 28, 93 >Gregory Piatetsky-Shapiro: > > Interestingness is subjective Good point that's basically why I suggested utility as a measure utility is a subjective user-defined concept; ========== ============ we then use decision theory to help us retreive those things of maximum subjective benefit; this really just gives a calculus for reasoning about it, not a way of defining it -------------------------------------------------- From: Gregory Piatetsky-Shapiro (gps@gte.com) Subject: Tracking viewers for marketing databases From ComputerWorld, October 25, 1993, p. 104, article WHO IS WATCHING WHOM? NBC plans to track viewers for marketing database One powerful feature of interactive TV is that databases can be kept on consumer transactions, and that data can be used for targeted marketing campaigns. Even in today's analog TV world, that capability has not gone unnoticed. The NBC TV network, a New York unit of General Electric Co., will soon launch a program called "NBC Viewer Service", in which the announcer will invite viewers to dial a toll-free number to receive more information (such as catalogs or coupons) about products during a commercial break. The initiative allows NBC to provide advertisers with "qialified leads", while NBC keeps a database of the callers and sends them quarterly program guides with advertising. "The database that we assemble will be very valuable to us and our advertisers", says Alan Cohen, senior vice president of marketing. However, providers risk a consumer backlash if they carelessly sell the data to third parties or use the information in ways that consumers view as invasion of privacy. At least one interactive TV provider, Eon Corp. in Reston, VA, is already promising to keep its transactional data, such as consumer buying patterns, confidential. "We want consumers to know that [privacy] is part of our culture, that we won't be selling that information", says Bob Chiaramonte, vice president for IS and product engineering. -------------------------------------------------- From: Gregory Piatetsky-Shapiro (gps@gte.com) Subject: PC AI: Tools for Data Mining PC AI (Nov - Dec 1993), has an article: "Data Mining: Intelligent Technology Gets down to Business". It presents a hypothetical data mining problem and shows how seven commercial tools can be used to solve it. The tools, in alphabetical order, are: @Brain, NN (neural network) tool, Talon Development, 414-962-7246; AIM, abductive network tool, AbTech, 804-977-0686; BrainMaker, NN tool, California Scientific Software, 800-284-8112 Datalogic/R, rough set tool, Reduct Systems, 306-586-9408 Database Mining Workstation, NN-based tool, HNC, 619-546-8877 ModelWare, proprietary modeling algorithm, Teranet IA, 800-663-8611 N-train, stat. and NN tool, Scientific Consultant Services, 516-696-3333 The article describes some actual applications, including one where AIM is used to manage one of Fidelity equity mutual funds, with good results. The article would have been better if an actual data set was used for comparison instead of a hypothetical problem. -------------------------------------------------- From: Saso.Dzeroski@cs.kuleuven.ac.be (Saso Dzeroski) Subject: Book Announcement-Inductive Logic Programming Nada Lavrac and Saso Dzeroski, INDUCTIVE LOGIC PROGRAMMING: Techniques and Applications, Ellis Horwood (Simon & Schuster), 1994, 20+294 pp. Hardcover $53.95 / ISBN 0-13-457870-8 (Ellis Horwood Series in Artificial Intelligence) Keywords: artificial intelligence, applications, databases, deductive databases, induction, learning, logic, logic programming, machine learning, knowledge discovery in databases ORDERING INFORMATION: The book is available NOW and may be ordered via your usual bookseller or directly from Simon and Schuster International Group Campus 400, Maylands Avenue, Hemel Hempstead, Hertfordshire, HP2 7EZ, England Tel. orders (+44) 442 881 900, Fax orders (+44) 442 257 115 ABOUT THE BOOK: The book is an introduction to inductive logic programming (ILP), a research area at the intersection of inductive machine learning and logic programming. This field aims at a formal framework and practical algorithms for inductively learning relational descriptions in the form of logic programs. ILP is of interest to inductive machine learning researchers as it significantly extends the usual attribute-value respresentation and consequently enlarges the scope of machine learning applications; it is also of interest to logic programming researchers as it extends the basically deductive framework of logic programming with the use of induction. The book consists of four parts. Part I is an introduction to the field of ILP. Part II describes in detail several empirical ILP techniques and their implementations. Part III presents the techniques for handling imperfect data in ILP, whereas Part IV gives an overview of several ILP applications. The book serves two main purposes. On the one hand, it can be used as a course book on ILP since it provides an easy-to-read introduction to ILP (Chapters 1-3), an overview of empirical ILP systems (Chapter 4), discusses ILP as search of refinement graphs (Chapter 7), analyses the sources of imperfect/noisy data and the mechanisms for handling noise (Chapter 8) and gives an overview of several interesting applications of ILP (Chapter 14). On the other hand, the book is a guide/reference for an in-depth study of specific empirical ILP techniques, i.e., using attribute-value learners in an ILP framework and specialization techniques based on FOIL (Chapters 5-6,9-10) and their applications in medicine, mesh design and learning of qualitative models (Chapters 11-13). The book will be of interest to engineers, researchers and graduate students in the field of artificial intelligence and database methodology, in particular in machine learning, logic programming, software engineering, deductive databases, and knowledge discovery in databases. Basic knowledge of artificial intelligence and logic would be helpful, but is not a prerequisite. CONTENTS: Foreword (by Luc De Raedt) xi Preface xv PART I: INTRODUCTION TO ILP 1 Introduction 3 1.1 Inductive concept learning 3 1.2 Background knowledge 10 1.3 Language bias 11 1.4 Inductive logic programming 13 1.5 Imperfect data 15 1.6 Applications of ILP 17 2 Inductive logic programming 23 2.1 Logic programming and deductive database terminology 23 2.2 Empirical ILP 28 2.3 Interactive ILP 31 2.4 Structuring the hypothesis space 33 3 Basic ILP techniques 39 3.1 Generalization techniques 39 3.1.1 Relative least general generalization 40 3.1.2 Inverse resolution 43 3.1.3 A unifying framework for generalization 48 3.2 Specialization techniques 53 3.2.1 Top-down search of refinement graphs 53 3.2.2 A unifying framework for specialization 57 PART II: EMPIRICAL ILP 4 An overview of empirical ILP systems 67 4.1 An overview of FOIL 67 4.2 An overview of GOLEM 74 4.3 An overview of MOBAL 76 4.4 Other empirical ILP systems 77 5 LINUS: Using attribute-value learners in an ILP framework 81 5.1 An outline of the LINUS environment 81 5.2 Attribute-value learning 84 5.2.1 An example learning problem 84 5.2.2 ASSISTANT 85 5.2.3 NEWGEM 88 5.2.4 CN2 93 5.3 Using background knowledge in learning 95 5.3.1 Using background knowledge in attribute-value learning 95 5.3.2 Transforming ILP problems to propositional form 97 5.4 The LINUS algorithm 99 5.4.1 Pre-processing of training examples 100 5.4.2 Post-processing 102 5.4.3 An example run of LINUS 103 5.4.4 Language bias in LINUS 105 5.5 The complexity of learning constrained DHDB clauses 108 5.6 Weakening the language bias 111 5.6.1 The i-determinacy bias 111 5.6.2 An example determinate definition 113 5.7 Learning determinate clauses with DINUS 114 5.7.1 Learning non-recursive determinate DDB clauses 115 5.7.2 Learning recursive determinate DDB clauses 120 6 Experiments in learning relations with LINUS 123 6.1 Experimental setup 123 6.2 Learning family relationships 124 6.3 Learning the concept of an arch 126 6.4 Learning rules that govern card sequences 129 6.5 Learning illegal chess endgame positions 133 7 ILP as search of refinement graphs 137 7.1 ILP as search of program clauses 137 7.2 Defining refinement graphs 139 7.3 A MIS refinement operator 140 7.4 Refinement operators for FOIL and LINUS 141 7.4.1 Refinement operator for FOIL 141 7.4.2 Refinement operator for LINUS 144 7.5 Costs of searching refinement graphs 147 7.6 Comparing FOIL and LINUS 149 PART III: HANDLING IMPERFECT DATA IN ILP 8 Handling imperfect data in ILP 153 8.1 Types of imperfect data 153 8.2 Handling missing values 155 8.3 Handling noise in attribute-value learning 156 8.4 Handling noise in ILP 158 8.5 Heuristics for noise-handling in empirical ILP 162 8.6 Probability estimates 165 8.7 Heuristics at work 167 8.7.1 The training set and its partitions 167 8.7.2 Search heuristics at work 168 9 mFOIL: Extending noise-handling in FOIL 173 9.1 Search space 173 9.2 Search heuristics 176 9.3 Search strategy and stopping criteria 178 9.4 Implementation details 179 10 Experiments in learning relations from noisy examples 183 10.1 Introducing noise in the examples 184 10.2 Experiments with LINUS 185 10.3 Experiments with mFOIL 189 PART IV: APPLICATIONS OF ILP 11 Learning rules for early diagnosis of rheumatic diseases 199 11.1 Diagnostic problem and experimental data 200 11.2 Medical background knowledge 200 11.3 Experiments and results 203 11.3.1 Learning from the entire training set 205 11.3.2 Medical evaluation of diagnostic rules 206 11.3.3 Performance on unseen examples 210 11.4 Discussion 214 12 Finite element mesh design 217 12.1 The finite element method 217 12.2 The learning problem 219 12.3 Experimental setup 221 12.4 Results and discussion 223 13 Learning qualitative models of dynamic systems 227 13.1 Qualitative modeling 228 13.1.1 The QSIM formalism 228 13.1.2 The U-tube system 229 13.1.3 Formulating QSIM in logic 231 13.2 An experiment in learning qualitative models 233 13.2.1 Experimental setup 234 13.2.2 Results 236 13.2.3 Comparison with other ILP systems 238 13.3 Related work 239 13.4 Discussion 240 14 Other ILP applications 243 14.1 Predicting protein secondary structure 243 14.2 Modeling structure-activity relationships 247 14.3 Learning diagnostic rules from qualitative models 252 14.3.1 The KARDIO methodology 253 14.3.2 Learning temporal diagnostic rules 257 14.4 Discussion 262 Bibliography 263 Index 287