Received: from ics.uci.edu by paris.ics.uci.edu id aa23710; 2 Sep 94 14:25 PDT Received: from ics.uci.edu by q2.ics.uci.edu id aa14459; 2 Sep 94 14:25 PDT To: ML-LIST: ; Subject: Machine Learning List: Vol. 6 No. 24 Reply-to: ml@ics.uci.edu Date: Fri, 02 Sep 1994 13:56:52 -0700 From: Michael Pazzani Message-ID: <9409021425.aa14459@q2.ics.uci.edu> Machine Learning List: Vol. 6 No. 24 Friday, September 2, 1994 Contents: MLnet-Archive at GMD New version of the LMDT algorithm available ILP-94 Detailed Program (Int.WS Inductive Logic Programming) When does Expected Gen. Perf. = 0 ? Generalization and Kolmogorov complexity PhD/Master Scholarship available Graduate Scholarship in New Zealand for machine learning research 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/ or N.Z where X and N are the volume and number of the issue; ID: anonymous PASSWORD: URL- http://www.ics.uci.edu/AI/ML/Machine-Learning.html ---------------------------------------------------------------------- Date: Fri, 2 Sep 1994 14:53:38 +0200 From: Marcus Luebbe Subject: MLnet-Archive at GMD This is the "What's New" page of the MLnet-Archive at GMD (FTP: ftp.gmd.de/ml-archive/, WWW: ftp://ftp.gmd.de/ml-archive/README.html) showing you the new arrivals of the last period: 08/24/94 Consultant-2, the MLT advice-giving system Version 2.2, March 12, 1993 Consultant-2 is the sub-system of the MLT which guides the user in selecting a suitable algorithm for a particular purpose. Additionally, once a tool is selected, Consultant-2 assists the user in making good use of the tool for his task. Consultant-2 contains knowledge about algorithms available in the MLT, their capabilities, limitations etc. Additionally, Consultant-2 contains related information to help the user understand the use of available algorithms. Consultant-2 acquires a description of the user's application primarily by asking questions about what the user is trying to do, the data available, required output etc. As these questions are answered, the relative suitability of all the algorithms is displayed in the form of a bar chart. A glossary contains descriptions of terminology used in the system; the user can access this glossary at any stage. placed in MLT:software (ftp-directory: ml-archive/MLT/public/software/Consultant) 08/24/94 - WWW page for MLnet installed, - newsletter from MLnet in MAC-PostScript format available, - Policy Statement, the first year annual report and a list of Nodes from MLnet in MAC-PostScript format available Please remember the other software systems offered by the MLnet Machine Learning archive: - Mobal - Consultant - Clint - Filp - Foil6.1 - Golem - Index - Miles - and the ML-Program-Library "ml-archive@gmd.de" ------------------------------ Date: Mon, 22 Aug 94 14:00 EST From: BRODLEY@coins.cs.umass.edu Subject: New version of the LMDT algorithm available We have created a new version of the Linear Machine Decision Tree (LMDT) algorithm. LMDT is an algorithm that creates decision trees in which each test node is a linear machine. Decision tree algorithms such as ID3 and C4.5 are limited to axis-parallel splits of the instance space; whereas trees created by LMDT can split the space using hyperplanes of any orientation. This message includes information on how to obtain LMDT, a list of articles that describe the LMDT algorithm, and a list of recent changes. To obtain a copy of LMDT or any of the articles listed below, please send mail to brodley@cs.umass.edu References: Utgoff, P. E., & Brodley, C. E. (1991) Linear Machine Decision Trees, University of Massachusetts Technical Report 91-10 Brodley C. E. & Utgoff P. E., (1992) Multivariate versus Univariate Decision Trees, University of Massachusetts Technical Report 92-8. Brodley C. E. & Utgoff P. E., (to appear) Multivariate Decision Trees, Machine Learning, Kluwer. Changes to Algorithm: 8/94 Changed the weight training algorithms to run thermal training 10 times, it picks the set of weights that allow the LM to maximize the selection criterion (information-gain or accuracy). This eliminates some of the instance-order effects of LMDT (by trying 10 different random orders). 8/94 Added the capability to have LMDT NOT discard features (default is to discard) 8/94 Added the capability for the user to choose accuracy as a selection criterion (default is information-gain ratio). ------------------------------ Subject: ILP-94 Detailed Program (Int.WS Inductive Logic Programming) Date: Mon, 22 Aug 94 14:43:34 +0200 From: Stefan.Wrobel@gmd.de This is the detailed program of ILP-94 workshop. Registration is still possible - just send E-Mail to ilp-94@gmd.de to get all the necessary infos. ============================================================================= ILP-94 Fourth International Workshop on Inductive Logic Programming 12.-14.September 1994, Bad Honnef/Bonn Preliminary Program (Papers and Posters) ============================================================================= Monday, 12. 9. 9:00-10:15 Invited Talk: The Art of ILP Applications Katharina Morik 10:15-10:45 Coffee Break 10:45-12:15 Mutagenesis: ILP experiments in a non-determinate biological domain A. Srinivasan, S. Muggleton, R. King, M. Sternberg GRDT: Enhancing Model-Based Learning for Its Application in Robot Navigation V. Klingspor Inductive Metalogic Programming A. Hamfelt, J.F. Nilsson 12:15-14:00 Lunch 14:00-15:30 Specialization of Logic Programs by Pruning SLD-Trees H. Bostroem, P. Idestam-Almquist MILP-a stochastic approach to Inductive Logic Programming M. Kovacic Inductive Learning of Characteristic Concept Descriptions W. Emde 15:30-16:00 Coffee Break 16:00-17:30 Poster/Demo Session 17:30-18:00 Break 18:00-20:00 Project Meetings ============================================================================= Tuesday, 13.9. 9:00-10:15 Invited Talk: ILP: An Alternative View Lorenza Saitta 10:15-10:45 Coffee Break 10:45-12:15 A Learnability Model for Universal Representations S. Muggleton, D. Page First-order jk-clausal Theories are PAC-Learnable L. De Raedt, Saso Dzeroski An Efficient Subsumption Algorithm for Inductive Logic Programming J.-U. Kietz, M. Luebbe 12:15-14:00 Lunch 14:00-16:00 Learning Clauses by Tracing Derivations F. Bergadano, D. Gunetti Induction of Maximally General Clauses Consistent with Integrity Constraints M. Sebag, C. Rouveirol Effective Algorithmic Debugging for Inductive Logic Programming J. Paakki, T. Gyimothy, T. Horvath The Arguments of Newly Invented Predicates in ILP I. Stahl, I. Weber 16:00-16:30 Coffee Break 16:30-17:30 ILP community meeting 17:30-17:45 Break 17:45-... Evening Program/Dinner ============================================================================= Wednesday, 14.9. 9:00-10:15 Invited Talk: Inductive Reasoning Paul Vitanyi 10:15-10:45 Coffee Break 10:45-12:15 Inductive Logic Programming and Philosophy of Science P. Flach Self-Saturation of Definite Clauses S. Muggleton, D. Page A Note on Ideal Refinement Operators in Inductive Logic Programming P. van der Laag, S.-H. Nienhuys-Cheng 12:15-14:00 Lunch 14:00 Departure/Sightseeing ============================================================================= Posters to be presented during poster session Learning to Recognise Hand-printed Chinese Characters using Inductive Logic Programming A. Amin, C.P. Chen, C. Sammut, K.C. Sum Learning stage transition rules with Indlog R. Camacho Applications of a logical discovery engine L. Dehaspe, W. Van Laer, L. De Raedt Finite Element Mesh Design: An Engineering Domain for ILP Application B. Dolsak, I. Bratko, A. Jezernik Pruning Methods for Rule Learning Algorithms J. Fuernkranz Relational Learning by Heuristic Evaluation of Ground Data Z. Markov ILP and Automatic Programming: Towards Three Approaches L. Popelinsky, P. Flener, O. Stepankova A Bidirectional search for clauses E. Siou Rulebase Stratification: An approach to theory restructuring E. Sommer A three-tiered Confidence Model for Revising Logical Theories I. Weber, B. Tausend ============================================================================= ------------------------------ Date: Tue, 23 Aug 94 15:24:50 EDT From: spears@aic.nrl.navy.mil Subject: When does Expected Gen. Perf. = 0 ? In response to Dave Wolpert: >> (Gordon and Spears) >>... permitting the teacher to label the test set examples by >>flipping a coin ... we don't believe a distribution meeting (this) >>criterion is what we encounter in the world. (Wolpert) >These comments are missing the point. Nobody said the uniform >distribution is what we encounter in this real world/universe. This comment misses our point. We never stated that anyone believes the universe has a uniform distribution. In our most recent message we stated that Diana and I care about expected GP (EGP), and that EGP can only be 0 if the universe fits a certain class of distributions (not just uniform). >Rather such a distribution can been (sic) *used*, to prove that every >learning algorithm must fail just as readily as it can succeed. Actually, such a distribution (class) MUST be used, to prove that expected GP is zero. That is our only point. In response to Rob Holte: (Holte) >We would probably all prefer to have a law about expected performance, >A question about expected generalization accuracy that COULD be asked is: >under what sorts of distributions do all learning systems have >an expected generalization accuracy of exactly 0 ? Yes, some of us do prefer this. Our last message on ML-List addressed this issue. Since it may have been missed in the flurry of messages, let us reiterate: "Actually, there are infinitely many possible distributions that yield zero EGP. In a nutshell you will get zero EGP for every learner L over all test cases iff each test case is equally likely to be positive or negative. For the sake of brevity we omit our proof, although we will be happy to mail it to anyone who is interested." "If the distribution does not meet the above criterion, there exist learners that can exhibit positive or negative expected generalization performance." As we've stated before, we'd be glad to be corrected if this is wrong. William Spears Diana Gordon ------------------------------ From: Juergen Schmidhuber Subject: Generalization and Kolmogorov complexity Message-Id: <94Aug30.105332met_dst.42322@papa.informatik.tu-muenchen.de> Date: Tue, 30 Aug 1994 10:53:18 +0200 Concerning the recent discussion on ``conservation laws'', ``nfl theorems'', and other statements expressing that (in general) generalization is impossible: This is my second attempt to draw attention to the fact that such statements appear to be obvious from the perspective of Kolmogorov complexity theory. Clearly, the mutual algorithmic information between almost all computable training sets and corresponding test sets is essentially zero (ignoring an additive constant independent of the problem). In the ``general case'', we cannot expect generalization. Many complexity theoreticians would be astonished if they knew that this provoked so many comments on this mailing list. As was noted by others, our universe is not an instance of the ``general case'' - perhaps because the universe itself is run by a short algorithm. Most problems encountered in the real world appear to have solutions whose algorithmic complexity is low when compared to most solution candidates. The following report makes use of this. DISCOVERING PROBLEM SOLUTIONS WITH LOW KOLMOGOROV COMPLEXITY AND HIGH GENERALIZATION CAPABILITY Technical Report FKI-194-94 (23 pages) Juergen Schmidhuber Fakultaet fuer Informatik Technische Universitaet Muenchen 80290 Muenchen, Germany August 1994 Many machine learning algorithms aim at finding ``simple'' rules to explain training data. The expectation is: the ``simpler'' the rules, the better the generalization on test data (--> Occam's razor). Most practical implementations, however, use measures for ``simplicity'' that lack the power, universality and elegance of those based on Kolmogorov complexity and Solomonoff's algorithmic probability. Likewise, most previous approaches (especially those of the ``Bayesian'' kind) suffer from the problem of choosing appropriate priors. This paper addresses both issues. It first reviews some basic concepts of algorithmic complexity theory relevant to machine learning, and how the Solomonoff-Levin distribution (or universal prior) deals with the prior problem. The universal prior leads to a probabilistic method for finding ``algorithmically simple'' problem solutions with high generalization capability. The method is based on ` Levin complexity (a time-bounded generalization of Kolmogorov complexity) and inspired by Levin's optimal universal search algorithm. With a given problem, solution candidates are computed by efficient ``self-sizing'' programs that influence their own runtime and storage size. The probabilistic search algorithm finds the ``good'' programs (the ones quickly computing algorith- mically probable solutions fitting the training data). Simulations focus on the task of discovering ``algorithmically simple'' neural networks with low Kolmogorov complexity and high generalization capability. It is demonstrated that the method, at least in certain cases where it is computationally feasible, can lead to generalization results unmatchable by previous neural net algorithms. The final part of the paper concerns extensions designed for incremental learning. To obtain a copy, do: unix> ftp 131.159.8.35 Name: anonymous Password: (your email address, please) ftp> binary ftp> cd pub/fki ftp> get fki-194-94.ps.gz ftp> bye unix> gunzip fki-194-94.ps.gz unix> lpr fki-194-94.ps.gz Alternatively, check out http://papa.informatik.tu-muenchen.de/mitarbeiter/schmidhu.html There will be a revised version of this report. Comments welcome! Juergen Schmidhuber ------------------------------ From: Nikola Kasabov Date: Tue, 23 Aug 1994 09:34:21 GMT+1200 Subject: PhD/Master Scholarship available University of Otago, New Zealand Department of Information Science PhD/MSc Scholarship available Topic: "Methods and Tools for Building Adaptable Speech Interfaces to Conventional and Fuzzy Databases" A graduate from Information Science, Computer Science or Electrical Engineering is sought to work on a PhD or a Master dissertation as part of a research project in the Department of Information Science. The project aims at developing a methodology and a software environment which include neural networks and fuzzy rule-based systems for building adaptable speech interfaces to existing standard or fuzzy databases. Neural networks will be used for low-level speech recognition. Fuzzy rule-based systems will be used for language understanding and for querying a database. Desirable is knowledge on information processing and contemporary information methods and techniques, including neural networks and fuzzy systems; programming skills in C, C++ and database languages; experience in working with PC and other computer environments; good knowledge of spoken English. The work is expected to commence not later than 1 June 1995. A PhD Scholarship would be for up to three years at an annual emolument of NZ$12,000 plus tuition fees at the level payable to a New Zealand student. An Award offered to a Master candidate would be for one year at the emolument of NZ$6,000 plus tuition fees at the level payable to a New Zealand student. More details about the research are available from Dr. Nik Kasabov (Phone: +64 3 479 8319, Fax: +64 3 479 8311, email: nkasabov@otago.ac.nz). Applications, quoting the postgraduate research topic (under number 10 in the list of Otago Research Scholarships and Awards for 1995) close with the Registry on the 1st of October 1994. Application forms are available from Miss E H A Knight , Scholarship Officer, phone: +64 3 479 8077, Fax: +64 3 474 1607, email: ann@gandalf.otago.ac.nz. These forms should be completed and forwarded to Miss E H A Knight, Scholarship Officer, University of Otago, P.O. Box 56, Dunedin, New Zealand. ------------------------------ Date: Wed, 24 Aug 1994 17:03:04 +1200 From: "Ian H. Witten" Subject: Graduate Scholarship in New Zealand for machine learning research The Computer Science Department at the University of Waikato in New Zealand is offering two new scholarships for study and research at the postgraduate level leading to a Doctoral degree. These prestigious scholarships are designed to strengthen and diversify our graduate student body, and should prove attractive to computer science students from other universities. They are partially funded by money from the Waikato Machine Learning research project. One scholarship is in the area of machine learning, broadly interpreted. The other is unrestricted and will be used to support research in any area of Computer Science. Applicants should have a good Honours or Masters degree in computer science or a closely allied subject. Duties include up to six hours per week of assigned teaching or research support work. The remaining time is to be spent on research and study associated with the graduate degree being sought. The scholarships will be for 12 months in the first instance, but will be extended for up to three years subject to satisfactory performance in both the degree program and the assigned work. The total value of each scholarship is NZ $22,500 per annum. Scholarship holders are require to register for a doctoral degree, and this figure includes an allowance for fees and a small allowance for expenses associated with thesis preparation. Citizens of Australia, France, and Germany pay the same fees as New Zealanders; the amount for next year is not set yet but is expected to remain close to NZ $2,800 per year. Citizens of other countries pay overseas student fees of around NZ $17,000 per year; these scholarships are not intended for such applicants unless they provide evidence of sufficient additional funding to support themselves during the period of study. Informal enquiries should be directed to the attention of John Cleary at postgrad-info@waikato.ac.nz. Applications, covering academic qualifications, grades obtained, relevant experience, and research directions, should be directed to Bronwyn Webster, Department of Computer Science, University of Waikato, Hamilton, New Zealand (bronwyn@waikato.ac.nz). Applicants should arrange for two referees to forward reports directly to the university. Official University application forms for graduate study will be sent to applicants at an appropriate stage of the proceedings. Consideration of applications will commence on 15 September 1994 and continue until both positions have been filled. ------------------------------ End of ML-LIST (Digest format) ****************************************