Copy Link
Add to Bookmark
Report
Machine Learning List Vol. 5 No. 24
Machine Learning List: Vol. 5 No. 24
Friday, November 26, 1993
Contents:
MachineLearning-Archive: Announcement and Call for Contributions
Book Announcement-Inductive Logic Programming
Employment opening: Siemens Corporate Research
Call for Papers: IEEE transactions on Systems, Man, and Cybernetics
Schlimmer and Hermens, Software Agents Article
Bergadano, Gunetti and Trinchero ILP paper
URGENT: DEADLINE CHANGE FOR WORLD CONGRESS
The Machine Learning List is moderated. Contributions should be relevant to
the scientific study of machine learning. Mail contributions to ml@ics.uci.edu.
Mail requests to be added or deleted to ml-request@ics.uci.edu. Back issues
may be FTP'd from ics.uci.edu in pub/ml-list/V<X>/<N> or N.Z where X and N are
the volume and number of the issue; ID: anonymous PASSWORD: <your mail address>
----------------------------------------------------------------------
Subject: MachineLearning-Archive: Announcement and Call for Contributions
Date: Wed, 10 Nov 93 14:54:33 +0100
From: Werner.Emde@gmd.de
MachineLearning-Archive: Announcement and Call for Contributions
The ML-archive ftp.gmd.de:/MachineLearning [129.26.8.90] contains a
growing collection of Machine Learning related papers, articles, tech
reports, data, and software with a particular focus on results
achieved by the European ESPRIT research projects "Machine Learning
Toolbox" (MLT) and "Inductive Logic Programming" (ILP), the European
Network of Excellence in Machine Learning (MLnet) and the Inductive
Logic Programming Pan-European Scientific Network (ILPnet).
For example, the archive presently contains
- the source code of Stephen Muggleton's and Cao Feng's learning sys-
tem Golem (in "/MachineLearning/ILP/public/software/golem"),
- a BibTex file with around 325 entries of articles related to ILP
("/MachineLearning/ILP/public/bib"),
- the knowledge acquisition and machine learning system MOBAL 2.2
for non-commercial academic use in
"/MachineLearning/ILP/public/software/Mobal"), and
- PROLOG implementations of basic machine learning algorithms (e.g.,
COBWEB, ID3, ARCH) ("/MachineLearning/general/ML-Program-Library").
This library is maintained by Thomas Hoppe (for more details, see
the README file in the subdirectory).
Here's how the anonymous FTP server works. To access or store material
on the server, use ftp to ftp.gmd.de, login ID "anonymous" and your
full E-Mail address as password. Change to directory
/MachineLearning, where the ML-related stuff is located. Remember,
when ftping compressed or compacted files (.Z) to use binary mode for
retrieving the files.
The directory structure is subject to change.
Please note: Wherever appropriate and possible, material has been
cross-indexed between the different subdirectories using symbolic
links.
You are invited to contribute your own software, papers etc. to the
ML-archive. If you have ML-related material, which might be relevant
for other researchers or potential users of Machine Learning
techniques, place it in one of the subdirectories of
"/ftp/incoming/Learning" AND also send mail to "ml-archive@gmd.de"
saying what you placed in "incoming". Our ml-archive manager Marcus
Luebbe will read these mails and install all contributions in the
proper place. As for papers, please send them in compressed
PostScript (.ps.Z) form. Please send us also a file with a plain text
bibliographic entry and, if possible, a corresponding BibTeX entry
with names of all authors, title, how and where the paper has been
published. As for software, please send both a compressed tarfile
containing your software and manuals as well as a README file
describing the software and its installation. Please let us know
which name to use for the subdirectory that stores your software.
Please, include the following statement in your mail:
COPYRIGHT CLEARANCE: I understand that the material I have
submitted will be made publicly available worldwide on an anoymous
FTP Server. I have made sure that this does not conflict with any
relevant copyrights on the material.
Please send questions and suggestions to:
ml-archive@gmd.de
------------------------------
Date: Thu, 11 Nov 93 16:26:16 +0100
From: Saso Dzeroski <Saso.Dzeroski@cs.kuleuven.ac.be>
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
------------------------------
Date: Thu, 18 Nov 1993 19:54:10 -0500
From: G Drastal <drastal@scr.siemens.com>
Subject: Employment opening: Siemens Corporate Research
CALL FOR RESUMES
Siemens Corporate Research
Learning Systems Department
Knowledge-Based Systems Group
This group will have a possible opening for a research scientist
starting in January, and we are soliciting applications now. The
position will be fulltime and permanent at the level of associate
research scientist up to senior research scientist, depending on
the applicant's background. Our group is involved with research
in machine learning that supports our mission to transfer novel
technology into the divisions of Siemens, in the U.S. and worldwide.
Applicants must have a Ph.D. in computer science and a record of
significant publications in machine learning, plus extraordinary
ability to communicate with scientists and engineers who are not
familiar with your own area of research. The ability to break
cryptographic codes, speak with dolphins, and to break cinderblock
with your bare hands is always helpful though not required.
Please send me your vita and one of your best papers, if you plan
to be available soon. Please use postal mail, not email or the phone
so that I can retain my sanity. Thanks,
George Drastal
Siemens Corporate Research
755 College Road East
Princeton, N.J. 08540
USA
------------------------------
Date: Mon, 22 Nov 1993 10:39:55 +0100
From: Marco DORIGO <mdorigo@ulb.ac.be>
Subject: Call for Papers: IEEE transactions on Systems, Man, and Cybernetics
Call For Papers:
Special issue of IEEE Transactions on Systems, Man and Cybernetics
(IEEE-SMC) on:
Learning Approaches to Autonomous Robots Control.
Guest Editor: Marco Dorigo
Submission deadline: May 20, 1994.
Recent research on control of autonomous robots (or agents) has
increasingly focused on the development and application of new learning
paradigms. This issue of robot control has been addressed in a number of
research areas including the following:
- Reinforcement learning (Q-learning, Classifier systems, etc.).
- Evolutionary Computation.
- Evolving neural nets.
- Neurocontrol and neurodynamics.
- Adaptive fuzzy systems.
- Artificial life.
The aim of the special issue of IEEE-SMC is to draw together current
research on a variety of these learning techniques (used and developed in
some or all of the above research fields) which have been applied to real
robots' control, as well as to discuss the implications this research has
on the design and development of robots in general. This includes the
following (not exhaustive) sub-topics:
- Learning approaches to stimulus-response robots.
- Learning approaches to robots acting in real environments.
- Supervised (that is, with a trainer) and unsupervised type of behavior
learning.
- Hierarchical architectures for learning robots.
- Trade-offs between learning and design.
- Interplay between reactive and reasoning type of robot activity in a
"learning perspective."
- Robustness of learning techniques to noisy environments and to unreliable
sensors and/or actuators.
- Ethologically inspired learning architectures for autonomous robots.
- Foundational analysis of interdependence among situated activity,
learning algorithms, and degree of environmental complexity.
- Cooperative learning robots.
Papers on research still in its "simulation" phase, that is, yet to be
implemented on real autonomous robots, will also be considered if it has
clear and relevant implications for still to come concrete realization.
To be considered for the special issue, five copies of each paper must be
received by the editor at the address below by May 20, 1994. The first page
should include a descriptive title, the names and addresses of all authors,
a brief abstract, and salient keywords. Submissions will be carefully
refereed for technical contribution, originality of the approach, practical
significance, and clarity of presentation (according to the standard IEEE
Transactions criteria), as well as salience to the topic of the special
issue.
Notifications will be sent by September 15, 1994, and final versions of
accepted papers will be due two months later.
Expected publication is mid-1995.
Marco Dorigo (Editor)
IRIDIA
Universite' Libre de Bruxelles
Avenue Franklin Roosvelt 50
CP 194/6 1050 Bruxelles
Belgium
tel. +32-2-6503167
fax +32-2-6502715
mdorigo@ulb.ac.be.
All prospective contributors should get in touch with the editor as soon as
possible, and in any case well before the submission deadline, in order to
receive more detailed information on the sort of research that the IEEE-SMC
special issue is expected to cover. Such responses will also help us with
the organization of reviews, and with last minute communications (such as
change of Editor's address).
Queries on any aspect of the above should also be directed to the
above address.
------------------------------
From: minton@ptolemy.arc.nasa.gov
Subject: Schlimmer and Hermens, Software Agents Article
Date: Mon, 15 Nov 1993 23:21:26 GMT
JAIR is pleased to announce the publication of the following article
by Schlimmer and Hermens. The article is accompanied by a Quicktime
demo of their system, contained in an on-line appendix. We believe
that this type of appendix represents an interesting new direction for
technical publications, and we hope you find it both exciting and
useful.
Schlimmer, Jeffrey C. and Hermens, Leonard A.
"Sofware Agents: Completing Patterns and Constructing User Interfaces",
Volume 1 (1993), pages 61-89.
Postscript: volume1/schlimmer93a.ps (1.1 Mbytes)
or volume1/schlimmer93a.ps.Z (compressed, 278K)
On-line Appendix: volume1/schlimmer93a-appendix.hqx (1.3 Mbytes)
Abstract: To support the goal of allowing users to record and retrieve
information, this paper describes an interactive note-taking system
for pen-based computers with two distinctive features. First, it
actively predicts what the user is going to write. Second, it
automatically constructs a custom, button-box user interface on
request. The system is an example of a learning-apprentice software-
agent. A machine learning component characterizes the syntax and
semantics of the user's information. A performance system uses this
learned information to generate completion strings and construct a
user interface.
Description of Demo: People like to record information. Doing this
on paper is initially efficient, but lacks flexibility. Recording
information on a computer is less efficient but more powerful. In our
new note taking software, the user records information directly on a
computer. Behind the interface, an agent acts for the user. To help,
it provides defaults and constructs a custom user interface.
The demonstration is a QuickTime movie of the note taking agent in
action. The file is a binhexed self-extracting archive. Macintosh
utilities for binhex are available from mac.archive.umich.edu.
QuickTime is available from ftp.apple.com in the dts/mac/sys.soft/quicktime.
(Editors note: We recognize that running the Quicktime movie
requires hardware that some readers may not have access to.)
The files are available via:
-- comp.ai.jair.papers (the postscript file is compressed and uuencoded here)
-- Anonymous FTP from either of the two sites below:
CMU: p.gp.cs.cmu.edu directory: /usr/jair/pub/volume1
Genoa: ftp.mrg.dist.unige.it directory: pub/jair/pub/volume1
-- automated email. Send mail to jair@cs.cmu.edu or jair@ftp.mrg.dist.unige.it
with the subject "autorespond", and the body "get volume1/schlimmer93a.ps"
-- JAIR Gopher server: At p.gp.cs.cmu.edu, port 70.
-- WWW: Although our HTML server is not running yet, you can access the
JAIR Gopher server through the Web. The server is listed, among other
places, in the main gopher directory at UMN under North America, USA,
Pennsylvania
For more information about JAIR, send electronic mail to
jair@cs.cmu.edu with the subject AUTORESPOND and the message body
HELP, or contact jair-ed@ptolemy.arc.nasa.gov.
------------------------------
From: minton@ptolemy.arc.nasa.gov
Subject: Bergadano, Gunetti and Trinchero ILP paper
Date: Tue, 23 Nov 1993 06:45:07 GMT
JAIR is pleased to announce the publication of the following article
by Francesco Bergadano, Daniele Gunetti and Umberto Trinchero:
Bergadano, F., Gunetti, D. and Trinchero, U.
"The Difficulties of Learning Logic Programs with Cut",
Volume 1 (1993), pages 91-107.
Postscript: volume1/bergadano93a.ps (185K)
Abstract: As real logic programmers normally use cut (!), an
effective learning procedure for logic programs should be able to deal
with it. Because the cut predicate has only a procedural meaning,
clauses containing cut cannot be learned using an extensional
evaluation method, as is done in most learning systems. On the other
hand, searching a space of possible programs (instead of a space of
independent clauses) is unfeasible. An alternative solution is to
generate first a candidate base program which covers the positive
examples, and then make it consistent by inserting cut where
appropriate. The problem of learning programs with cut has not been
investigated before and this seems to be a natural and reasonable
approach. We generalize this scheme and investigate the difficulties
that arise. Some of the major shortcomings are actually caused, in
general, by the need for intensional evaluation. As a conclusion, the
analysis of this paper suggests, on precise and technical grounds,
that learning cut is difficult, and current induction techniques
should probably be restricted to purely declarative logic languages.
------------------------------
Date: Wed, 3 Nov 93 11:38:56 CST
From: mwitten@chpc.utexas.edu
Subject: URGENT: DEADLINE CHANGE FOR WORLD CONGRESS
UPDATE ON DEADLINES
FIRST WORLD CONGRESS ON COMPUTATIONAL MEDICINE, PUBLIC
HEALTH, AND BIOTECHNOLOGY
24-28 April 1994
Hyatt Regency Hotel
Austin, Texas
Due to a confusion in the electronic distribution of
the congress announcement and deadlines, as well as
incorrect deadlines appearing in a number of society
newsletters and journals, we are extending the abstract
submission deadline for this congress to 31 December 1993.
We apologize to those who were confused over the differing
deadline announcements and hope that this change will
allow everyone to participate. For congress details:
To contact the congress organizers for any reason use any of the
following pathways:
ELECTRONIC MAIL - compmed94@chpc.utexas.edu
FAX (USA) - (512) 471-2445
PHONE (USA) - (512) 471-2472
GOPHER: log into the University of Texas System-CHPC
select the Computational Medicine and Allied Health
menu choice
ANONYMOUS FTP: ftp.chpc.utexas.edu
cd /pub/compmed94
(all documents and forms are stored here)
POSTAL:
Compmed 1994
University of Texas System CHPC
Balcones Research Center
10100 Burnet Road, 1.154CMS
Austin, Texas 78758-4497
SUBMISSION PROCEDURES: Authors must submit 5
copies of a single-page 50-100 word abstract clearly
discussing the topic of their presentation. In
addition, authors must clearly state their choice of
poster, contributed paper, tutorial, exhibit, focused
workshop or birds of a feather group along with a
discussion of their presentation. Abstracts will be
published as part of the preliminary conference
material. To notify the congress organizing committee
that you would like to participate and to be put on
the congress mailing list, please fill out and return
the form that follows this announcement. You may use
any of the contact methods above. If you wish to
organize a contributed paper session, tutorial
session, focused workshop, or birds of a feather
group, please contact the conference director at
mwitten@chpc.utexas.edu . The abstract may be submitted
electronically to compmed94@chpc.utexas.edu or
by mail or fax. There is no official format.
If you need further details, please contact me.
Matthew Witten
Congress Chair
mwitten@chpc.utexas.edu
------------------------------
End of ML-LIST (Digest format)
****************************************
