From hicks@cs.titech.ac.jp Sun Dec 10 20:33:55 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Sun, 10 Dec 95 20:33:51 -0600; AA10836 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Sun, 10 Dec 95 20:33:49 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa17591; 10 Dec 95 14:33:53 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa17589; 10 Dec 95 14:19:25 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa05363; 10 Dec 95 14:18:44 EST Received: from RI.CMU.EDU by B.GP.CS.CMU.EDU id aa12863; 10 Dec 95 9:26:14 EST Received: from [131.112.164.13] by RI.CMU.EDU id aa01211; 10 Dec 95 9:24:58 EST Received: by euclid.cs.titech.ac.jp (8.6.11+2.4W/3.2W-titmx-2.0g); Sun, 10 Dec 1995 23:24:29 +0900 Date: Sun, 10 Dec 1995 23:24:29 +0900 From: hicks@cs.titech.ac.jp Message-Id: <199512101424.XAA13664@euclid.cs.titech.ac.jp> To: mpp@watson.ibm.com, connectionists@cs.cmu.edu Cc: hicks@cs.titech.ac.jp In-Reply-To: Michael Perrone's message of Fri, 8 Dec 1995 19:27:29 -0500 (EST) <9512090027.AA26165@austen.watson.ibm.com> Subject: NFL Summary Micheal Perrone writes: > I think that the NFL results point towards what I feel are extremely > interesting research topics: > ... > Can we identify a set of assumptions that are equivalent to the > assumption that CV model selection improves generalization? CV is nothing more than the random sampling of prediction ability. If the average over the ensemble of samplings of this ability on 2 different models A and B come out showing that A is better than B, then by definition A is better than B. This assumes only that the true domain and the ensemble of all samplings coincide. Therefore CV will not, on average, cause a LOSS in prediction ability. That is, when it fails, it fails gracefully, on average. It cannot be consistently deceptive. (A quick note: Sometimes it is advocated that a complexity parameter be set by splitting the data set into training and testing, and using CV. Then with the complexity parameter fixed the whole data set can be used to train the other parameters. Behind this is an ASSUMPTION about the independence of the complexity from the other parameters. Of course it often works in practice, but it violates the principle in the above paragraph, so I do not count this as real CV here.) Two prerequisites exist to obtain a GAIN with CV 1) The objective function must be "compressible". I.e., it cannot be noise. 2) We must have a model which can recognize the structure in the data. This structure might be quite hard to see, as in chaotic signals. I think NFL says that on average CV will not obtain GAINful results, because the chance that a randomly selected problem and a randomly selected algorithm will hit it off is vanishingly small. (Or even any fixed problem and a randomly selected algorithm.) But I think it tells us something more important as well. It tells us that not using CV means we are always implicitly trusting our a priori knowledge. Any reasonable learning algorithm can always predict the training data, or a "smoothed" version of it. But because of the NFL theorem, this, over the ensemble of all algorithms and problems, means nothing. On average there will be no improvement in the off training set error. Fortunately, CV will report this fact by showing a zero correlation between prediction and true value on the off training set data. (Of course this is only the performance of CV on average over the ensemble of off training set datas; CV may be deceptive for a single off training set data.) Thus, we shouldn't think we can do away with CV unless we admit to having great faith in our prior. Going back to NFL, I think it poses another very interesting problem: Supposing we have "a foot in the door". That is, an algorithm which makes some sense of the data by showing some degree of prediction capability. Can we always use this prediction ability to gain better prediction ability? Is there some kind of ability to perform something like steepest descent over the space of algorithms, ONCE we are started on a slope? Is there a provable snowball effect? I think NFL reminds us that we are already rolling down the hill, and we shouldn't think otherwise. Craig Hicks Tokyo Institute of Technology From goldfarb@unb.ca Sun Dec 10 20:33:56 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Sun, 10 Dec 95 20:33:54 -0600; AA10842 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Sun, 10 Dec 95 20:33:51 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id ab17591; 10 Dec 95 14:35:26 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id ab17589; 10 Dec 95 14:19:27 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa05368; 10 Dec 95 14:19:16 EST Received: from RI.CMU.EDU by B.GP.CS.CMU.EDU id aa13054; 10 Dec 95 10:53:04 EST Received: from hermes.csd.unb.ca by RI.CMU.EDU id aa01309; 10 Dec 95 10:52:33 EST Received: from jupiter.sun.csd.unb.ca by unb.ca (8.6.12/950414-15:35) id LAA16186; Sun, 10 Dec 1995 11:52:30 -0400 Received: by jupiter.sun.csd.unb.ca (8.6.10/950215-16:05) id LAA03991; Sun, 10 Dec 1995 11:52:30 -0400 Date: Sun, 10 Dec 1995 11:52:29 -0400 (AST) From: Lev Goldfarb X-Sender: goldfarb@jupiter.sun.csd.unb.ca To: Michael Perrone Cc: Connectionists@cs.cmu.edu Subject: Re: NFL Summary In-Reply-To: <9512090027.AA26165@austen.watson.ibm.com> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII On Fri, 8 Dec 1995, Michael Perrone wrote: > NFL in a Nutshell: > ------------------ > If you make no assumptions about the target function [specifically, about the axiomatic structure of the sample space and the inductive generalization, i.e. which ones are the most general for the purpose] Strangely as it may sound at first, try to inductively learn the subgroup of some large group with the group structure completely hidden. No statistics will reveal the underlying group structure. Objects in the universe do have structure, especially when they have to be represented, as we have learned from the data types in computer science: TO REPRESENT AN OBJECT IS TO MAKE SOME ASSUMPTIONS ABOUT THE OPERATIONS RELATED TO ITS MANIPULATION. Cheers, Lev Goldfarb From XIAODONG@rivendell.otago.ac.nz Mon Dec 11 18:53:23 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Mon, 11 Dec 95 18:53:18 -0600; AA26498 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Mon, 11 Dec 95 18:53:14 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa18336; 11 Dec 95 0:03:45 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa18334; 10 Dec 95 23:49:13 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa05948; 10 Dec 95 23:48:49 EST Received: from CS.CMU.EDU by B.GP.CS.CMU.EDU id aa17427; 10 Dec 95 20:48:01 EST Received: from thorin.otago.ac.nz by CS.CMU.EDU id aa07988; 10 Dec 95 20:47:12 EST Received: from rivendell.otago.ac.nz by rivendell.otago.ac.nz (PMDF V4.2-11 #2617) id <01HYONVDN6PCLBVSXM@rivendell.otago.ac.nz>; Mon, 11 Dec 1995 14:46:22 +1300 Date: Mon, 11 Dec 1995 14:46:21 +1300 From: "Xiaodong Li, Otago University, New Zealand" Subject: Paper available "Connectionist Model Based on an Optical Thin-Film Model" To: connectionists@cs.cmu.edu Message-Id: <01HYONVDU5GYLBVSXM@rivendell.otago.ac.nz> X-Envelope-To: connectionists@cs.cmu.edu X-Vms-To: IN%"connectionists@cs.cmu.edu" Mime-Version: 1.0 Content-Transfer-Encoding: 7BIT FTP-host: archive.cis.ohio-state.edu FTP-filename:/pub/neuroprose/xli.thinfilm.ps.Z The file xli.thinfilm.ps.Z is now available for ftp from Neuroprose repository. Connectionist Learning Using an Optical Thin-Film Model (4 pages) Martin Purvis and Xiaodong Li Computer and Information Science University of Otago Dunedin, New Zealand ABSTRACT: An alternative connectionist architecture to the one based on the neuroanatomy of biological organisms is described. The proposed architecture is based on an optical thin-film multilayer model, with the thicknesses of thin-film layers serving as adjustable 'weights' for the computation. Inputs are encoded into the corresponding refractive indices of individual thin-film layers, while the outputs are typically measured by the overall reflection coefficients off the thin-film layers, at different wavelengths. The nature of the model and some example calculations (a pattern recognition and the classification on the iris data set) that exhibit behaviour typical of conventional connectionist architectures are described. This model has also been used in solving the XOR and 16 four-bit parity problems, and it has demonstrated comparable performance to that of a conventional feed-forward neural netwrok model using Back-propagation learning. This paper is also available at the proceeding of the Second New Zealand International Two-Stream Conference on Artificial Neural Nteworks and Expert Systems (ANNES'95), IEEE Computer Society Press, Los Almamitos, California, 1995, pp. 63-66. Comments are greatly appreciated. -- Xiaodong Li Email: Xiaodong@otago.ac.nz Http: http://divcom.otago.ac.nz:800/COM/INFOSCI/SECML/xdli/xiao.htm (Postscript file of this paper is also available here at my hoempage) From prechelt@ira.uka.de Mon Dec 11 18:53:27 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Mon, 11 Dec 95 18:53:21 -0600; AA26500 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Mon, 11 Dec 95 18:53:17 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa19161; 11 Dec 95 10:45:07 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa19159; 11 Dec 95 10:28:46 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa06395; 11 Dec 95 10:28:14 EST Received: from CS.CMU.EDU by B.GP.CS.CMU.EDU id aa24060; 11 Dec 95 7:19:50 EST Received: from iraun1.ira.uka.de by CS.CMU.EDU id aa10709; 11 Dec 95 7:19:03 EST Received: from ira.uka.de (actually i41s25.ira.uka.de) by iraun1.ira.uka.de with SMTP (PP); Mon, 11 Dec 1995 13:12:13 +0100 To: connectionists@cs.cmu.edu Subject: NN Benchmarking WWW homepage Date: Mon, 11 Dec 1995 13:11:32 +0100 From: Lutz Prechelt Message-Id: <"iraun1.ira.487:11.12.95.12.12.22"@ira.uka.de> The homepage of the very successful NIPS*95 workshop on benchmarking has now been converted into a repository for information about benchmarking issues: Status quo, methodology, facilities, and related info. I kindly ask everybody who has additional information that should be on the page (in particular sources or potential sources of learning data of all kinds) to submit that information to me. Other comments are also welcome. The URL is http://wwwipd.ira.uka.de/~prechelt/NIPS_bench.html The page is also still reachable over the benchmarking workshop link on the NIPS*95 homepage. Below is a textual version of the page. Lutz Lutz Prechelt (http://wwwipd.ira.uka.de/~prechelt/) | Whenever you Institut f. Programmstrukturen und Datenorganisation | complicate things, Universitaet Karlsruhe; D-76128 Karlsruhe; Germany | they get (Phone: +49/721/608-4068, FAX: +49/721/694092) | less simple. =============================================== Benchmarking of learning algorithms information repository page Abstract: Proper benchmarking of (neural network and other) learning architectures is a prerequisite for orderly progress in this field. In many published papers deficiencies can be observed in the benchmarking that is performed. A workshop about NN benchmarking at NIPS*95 addressed the status quo of benchmarking, common errors and how to avoid them, currently existing benchmark collections, and, most prominently, a new benchmarking facility including a results database. This page contains pointers to written versions or slides of most of the talks given at the workshop plus some related material. The page is intended to be a repository for such information to be used as a reference by researchers in the field. Note that most links lead to Postscript documents. Please send any additions or corrections you might have to Lutz Prechelt (prechelt@ira.uka.de). Workshop Chairs: Thomas G. Dietterich , Geoffrey Hinton , Wolfgang Maass , Lutz Prechelt [communicating chair] Terry Sejnowski Assessment of the status quo: * Lutz Prechelt. A quantitative study of current benchmarking practices. A quantitative survey of 400 journal articles of 1993 and 1994 on NN algorithms. Most articles used far too few problems during benchmarking. * Arthur Flexer. Statistical Evaluation of Neural Network Experiments: Minimum Requirements and Current Practice. Says that it is insufficient what is reported about the benchmarks and how. Methodology: * Tom Dietterich. Experimental Methodology Benchmarking types, correct statistical testing, synthetic versus real-world data, understanding via algorithm mutation or data mutation, data generators. * Lutz Prechelt. Some notes on neural learning algorithm benchmarking. A few general remarks about volume, validity, reproducibility, and comparability of benchmarking; DOs and DON'Ts. * Brian Ripley. What can we learn from the study of the design of experiments? (Only two slides, though). * Brian Ripley. Statistical Ideas for Selecting Network Architectures. (Also somewhat related to benchmarking.) Benchmarking facilities: * Previously available NN benchmarking data collections CMU nnbench, UCI machine learning databases archive, Proben1, StatLog data, ELENA data. Advantages of these: UCI is large and growing and popular, Statlog has largest and most orderly collection of results available (in a book, though), and Proben1 is most easy to use and best supports reproducible experiments. Elena and nnbench have no particular advantages. Disadvantages: UCI and Probem1 have too few and too unstructured results available, Proben1 is also inflexible and small, Statlog is partially confidential and neither data nor results collection are growing. * Carl Rasmussen and Geoffrey Hinton. DELVE: A thoroughly designed benchmark collection A proposal of data, terminology, and procedures and a facility for the collection of benchmarking results. This is the newly proposed standard for benchmarking NN (and other) learning algorithms. DELVE is currently still under construction at the University of Toronto. Other sources of data: (Thanks to Nici Schraudolph ) There is a large amount of game data about the board game Go available on the net. One starting point is here. Others are the Go game database project, and the Go game server. The database holds several hundred thousand games of Go and could for instance be used for advanced reinforcement learning projects. Last correction: 1995/12/11 Please send additions and corrections to Lutz Prechelt, prechelt@ira.uka.de. To NIPS homepage. To original homepage of this workshop. From mpp@watson.ibm.com Mon Dec 11 18:53:30 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Mon, 11 Dec 95 18:53:23 -0600; AA26506 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Mon, 11 Dec 95 18:53:21 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa19174; 11 Dec 95 10:55:49 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa19163; 11 Dec 95 10:29:36 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa06401; 11 Dec 95 10:28:44 EST Received: from CS.CMU.EDU by B.GP.CS.CMU.EDU id aa24644; 11 Dec 95 8:43:42 EST Received: from watson.ibm.com by CS.CMU.EDU id aa11039; 11 Dec 95 8:43:35 EST Received: from WATSON by watson.ibm.com (IBM VM SMTP V2R3) with BSMTP id 3523; Mon, 11 Dec 95 08:43:15 EST Received: from YKTVMV by watson.vnet.ibm.com with "VAGENT.V1.02 on VAGENT2" id 5541; Mon, 11 Dec 1995 08:43:15 EST Received: from austen.watson.ibm.com by yktvmv.watson.ibm.com (IBM VM SMTP V2Rx) with TCP; Mon, 11 Dec 95 08:43:14 EST Received: by austen.watson.ibm.com (AIX 3.2/UCB 5.64/950830) id AA25646; Mon, 11 Dec 1995 08:42:59 -0500 Message-Id: <9512111342.AA25646@austen.watson.ibm.com> Subject: Re: compressibility and generalization To: hicks@cs.titech.ac.jp Date: Mon, 11 Dec 1995 08:42:59 -0500 (EST) From: Michael Perrone Cc: connectionists@cs.cmu.edu In-Reply-To: <199512080049.JAA10560@euclid.cs.titech.ac.jp> from "hicks@cs.titech.ac.jp" at Dec 8, 95 09:49:53 am X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 831 [hicks@cs.titech.ac.jp wrote:] > PSS. What is anti-cross validation? Suppose we are given a set of functions and a crossvalidation data set. The CV and Anti-CV algorithms are as follows: CV: Choose the function with the best performance on the CV set. Anti-CV: Choose the function with the worst performance on the CV set. (And for this year's NIPS motif: Anti-EM: Dorothy? Dorothy? :-) Regards, Michael ------------------------------------------------------------------------- Michael P. Perrone 914-945-1779 (office) IBM - Thomas J. Watson Research Center 914-945-4010 (fax) P.O. Box 704 / Rm 36-207 914-245-9746 (home) Yorktown Heights, NY 10598 mpp@watson.ibm.com ------------------------------------------------------------------------- From hicks@cs.titech.ac.jp Tue Dec 12 20:56:39 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Tue, 12 Dec 95 20:56:34 -0600; AA12503 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Tue, 12 Dec 95 20:56:32 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa19756; 11 Dec 95 20:23:58 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa19754; 11 Dec 95 20:10:53 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa06671; 11 Dec 95 20:10:15 EST Received: from RI.CMU.EDU by B.GP.CS.CMU.EDU id aa05109; 11 Dec 95 20:02:14 EST Received: from euclid.cs.titech.ac.jp by RI.CMU.EDU id aa06815; 11 Dec 95 20:01:25 EST Received: by euclid.cs.titech.ac.jp (8.6.11+2.4W/3.2W-titmx-2.0g); Tue, 12 Dec 1995 10:01:05 +0900 Date: Tue, 12 Dec 1995 10:01:05 +0900 From: hicks@cs.titech.ac.jp Message-Id: <199512120101.KAA16136@euclid.cs.titech.ac.jp> To: mpp@watson.ibm.com, connectionists@cs.cmu.edu Cc: hicks@cs.titech.ac.jp In-Reply-To: "Michael Perrone"'s message of Mon, 11 Dec 1995 08:42:59 -0500 (EST) <9512111342.AA25646@austen.watson.ibm.com> Subject: compressibility and generalization "Michael Perrone" wrote: >[hicks@cs.titech.ac.jp wrote:] >> PSS. What is anti-cross validation? >Suppose we are given a set of functions and a crossvalidation data set. >The CV and Anti-CV algorithms are as follows: > CV: Choose the function with the best performance on the CV set. >Anti-CV: Choose the function with the worst performance on the CV set. case 1: * Either the target function is (noise/uncompressible/has no structure), or none of the candidate functions have any correlation with the target function.* In this case both Anti-CV and CV provide (ON AVERAGE) equal improvement in prediction ability: none. For that matter so will ANY method of selection. Moreover, if we plot a graph of the number of data used for training vs. the estimated error (using the residual data), we will (ON AVERAGE) see no decrease in estimated error. Since CV provides an estimated prediction error, it can also tell us "you might as well be using anti-cross validation, or random selection for that matter, because it will be equally useless". case 2: * The target (is compressible/has structure), and some the candidate functions are positively correlated with the target function.* In this case CV will outperform anti-CV (ON AVERAGE). By ON AVERAGE I mean the expectation across the ensemble of samples for a FIXED target function. This is different from the ensemble and distribution of target functions, which is a much bigger question. We known much already about about the ensemble of samples from a fixed target function. I am not avoiding the issue of the ensemble or distribution of target functions, but merely showing that we have 2 general cases, and that in both of them CV is never WORSE than anti-CV. It follows that whatever the distribution of targets is, CV is never worse (ON AVERAGE) than anti-CV. I don't believe this contradicts NFL in any way. It just clarifies the role that CV can play. Learning and monitoring prediction error go hand in hand. This is even more true for cases when the underlying function may be changing and the data has the form of an infinite stream. Craig Hicks Tokyo Institute of Technology From GIOIELLO@cres.it Wed Dec 13 17:21:15 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Wed, 13 Dec 95 17:21:13 -0600; AA00627 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Wed, 13 Dec 95 17:21:11 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa20013; 11 Dec 95 23:01:41 EST Received: by TELNET-1.SRV.CS.CMU.EDU id ab19999; 11 Dec 95 22:51:22 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa19990; 11 Dec 95 22:34:12 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa06712; 11 Dec 95 22:33:14 EST Received: from EDRC.CMU.EDU by B.GP.CS.CMU.EDU id aa06835; 11 Dec 95 22:22:52 EST Received: from cresa0.cres.it by EDRC.CMU.EDU id aa02384; 11 Dec 95 22:22:18 EST Received: from DECNET-MAIL (GIOIELLO@CRESH2) by cres.it (PMDF V5.0-4 #2463) id <01HYP9T0AFQO934ROD@cres.it> for Connectionists@cs.cmu.edu; Tue, 12 Dec 1995 01:13:43 +0100 Date: Tue, 12 Dec 1995 01:13:43 +0100 From: GIOIELLO Subject: A neural net based OCR demo for both Windows/DOS and Mac OS is available To: Connectionists@cs.cmu.edu Message-Id: <01HYP9T0BSPU934ROD@cres.it> X-Vms-To: IN::"Connectionists@cs.cmu.edu" X-Vms-Cc: GIOIELLO Mime-Version: 1.0 Content-Transfer-Encoding: 7BIT Dear Netters, An OCR demo for Mac OS is available at the following URL: ftp://ftpcsai.diepa.unipa.it/pub/demos/OCR-demo.cpt.hqx A Windows and DOS version is also available at the following URL: ftp://ftpcsai.diepa.unipa.it/pub/demos/OCR-Win.zip this latter version offers a more rich set of capabilities too. The OCR is based on a three-layer MLP. The conjugate gradient descent techniques were used while training the net. Training and test set were those of NIST. The related papers will be found at the following URL: ftp://ftpcsai.diepa.unipa.it/pub/papers/handwritten Several VLSI architectures to implement the OCR device using a digital implementation of the proposed MLP are also described in the papers. An overwiev of the activities we carry on can be found at the following URL: http://wwwcsai.diepa.unipa.it/research/projects/vlsinn/handcare/handcare.html Best Regards, Giuseppe A. M. Gioiello E-Mail: gioiello@diepa.unipa.it URL: http://wwwcsai.diepa.unipa.it/people/doctors/gioiello/gioiello.html From ernst@kuk.klab.caltech.edu Wed Dec 13 17:21:19 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Wed, 13 Dec 95 17:21:17 -0600; AA00633 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Wed, 13 Dec 95 17:21:14 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa21460; 12 Dec 95 19:26:16 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa21458; 12 Dec 95 19:08:17 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa07769; 12 Dec 95 19:07:44 EST Received: from CS.CMU.EDU by B.GP.CS.CMU.EDU id aa16642; 12 Dec 95 12:03:31 EST Received: from chamber.cco.caltech.edu by CS.CMU.EDU id aa27891; 12 Dec 95 12:02:33 EST Received: from gap.cco.caltech.edu by chamber.cco.caltech.edu with ESMTP (8.6.12/DEI:4.41) id JAA26620; Tue, 12 Dec 1995 09:02:09 -0800 Received: by gap.cco.caltech.edu (8.6.7/DEI:4.41) id JAA17928; Tue, 12 Dec 1995 09:02:07 -0800 To: mlist-connectionists@nntp-server.caltech.edu Path: nntp-server.caltech.edu!ernst From: Ernst Niebur Newsgroups: mlist.connectionists,sci.psychology.announce Subject: Training opportunities in Computational Neuroscience at Johns Hopkins University Date: 12 Dec 1995 17:02:22 GMT Organization: California Institute of Technology Lines: 95 Distribution: world Message-Id: Reply-To: niebur@jhu.edu Nntp-Posting-Host: kuk.klab.caltech.edu The Zanvyl Krieger Mind/Brain Institute at Johns Hopkins University is an interdisciplinary research center devoted to the investigation of the neural mechanisms of mental function and particularly to the mechanisms of perception: How is complex information represented and processed in the brain, how is it stored and retrieved, and which brain centers are critical for these operations? The Institute intends to significantly enhance its research program in Computational Neuroscience and encourages students with interest in this domain to apply for the graduate program in the Neuroscience department. Research opportunities exist in all of the laboratories of the Institute. Interdisciplinary projects, involving the student in more than one laboratory, are particularly encouraged. At present, MBI faculty include (listed with primary field of interest and methodology used): C. Ed Connor, PhD: Visual selective attention (electrophysiology in the awake behaving monkey). Stewart Hendry, PhD: Organization and plasticity of mammalian cerebral cortex (primate neuroanatomy). Steve S. Hsiao, PhD: Neurophysiology of tactile perception (electrophysiology in the awake behaving monkey). Kenneth O. Johnson, PhD: Neurophysiology of the somatosensory system (electrophysiology in the awake behaving monkey). Guy McKhann, MD (Director of MBI): Cognitive and neurologic outcomes after cardiac surgery; immunologic attack on peripheral motor axonal membranes in the human and experimental animal (neurology). Ernst Niebur, PhD: Theoretical Neuroscience (computational and mathematical modeling). Gian F Poggio, PhD: Analysis of Stereopsis and Texture (electrophysiology in the awake behaving monkey). Michael A. Steinmetz, PhD: Neurophysiological mechanisms in visual-spatial perception (electrophysiology in the awake behaving monkey). Ruediger von der Heydt, PhD: Neural mechanisms of visual perception (electrophysiology in the awake behaving monkey). Additional research opportunities exist in collaborative work with faculty in the Psychology Department (located next door to the Mind/Brain Institute), in particular with Drs. Howard Egeth (attention, perception, cognition), Michael Rudd (computational vision, psychophysics), Trisha Van Zandt (mathematical modelling, neural networks and memory), and Steven Yantis (visual perception, attention, mathematical modeling). All students accepted to the PhD program of the Neuroscience department receive full tuition remission plus a stipend at or above the National Institutes of Health predoctoral level. The Mind/Brain Institute is located on the very attractive Homewood campus in Northern Baltimore. Applicants should have a B.S. or B.A. with a major in any of the biological or physical sciences. Applicants are required to take the Graduate Record Examination (GRE), both the aptitude tests and an advanced test, or the Medical College Admission Test. Further information on the admission procedure can be obtained from the Department of Neuroscience: Director of Graduate Studies Neuroscience Training Program Department of Neuroscience The Johns Hopkins University School of Medicine 725 Wolfe Street Baltimore, MD 21205 Completed applications (including three letters of recommendation and either GRE scores or Medical College Admission Test scores) must be _received_ by January 1, 1996 at the above address. Candidates for whom this is impossible, or those who need additional information, should immediately contact Prof. Ernst Niebur The Zanvyl Krieger Mind/Brain Institute Johns Hopkins University 3400 N. Charles Street Baltimore, MD 21218 niebur@jhu.edu -- Ernst Niebur Krieger Mind/Brain Institute Asst. Prof. of Neuroscience Johns Hopkins University niebur@jhu.edu 3400 N. Charles Street (410)516-8643, -8640 (secr), -8648 (fax) Baltimore, MD 21218 From dhw@santafe.edu Wed Dec 13 17:21:24 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Wed, 13 Dec 95 17:21:22 -0600; AA00639 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Wed, 13 Dec 95 17:21:17 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id ab21460; 12 Dec 95 19:28:07 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id ab21458; 12 Dec 95 19:08:20 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa07774; 12 Dec 95 19:07:55 EST Received: from CS.CMU.EDU by B.GP.CS.CMU.EDU id aa22605; 12 Dec 95 17:29:07 EST Received: from [192.12.12.1] by CS.CMU.EDU id aa01410; 12 Dec 95 17:28:18 EST Received: from aztec.santafe.edu.santafe by sfi.santafe.edu (4.1/SMI-4.1) id AA00709; Tue, 12 Dec 95 15:25:06 MST Date: Tue, 12 Dec 95 15:25:06 MST From: David Wolpert Message-Id: <9512122225.AA00709@sfi.santafe.edu> To: Connectionists@cs.cmu.edu Subject: The last of a dying thread Some comments on the NFL thread. Huaiyu Zhu writes >>> 2. The *mere existence* of structure guarantees a (not uniformly-random) algorithm as likely to lose you a million as to win you a million, even in the long run. It is the *right kind* of structure that makes a good algorithm good. >>> This is a crucial point. It also seems to be one lost on many of the contributors to this thread, even those subsequent to Zhu's posting. Please note in particular that the knowledge that "the universe is highly compressible" can NOT, by itself, be used to circumvent NFL. I can only plead again: Those who are interested in this issue should look at the papers directly, so they have at least passing familiarity with the subject before disussing it. :-) ftp.santafe.edu, pub/dhw_ftp, nfl.1.ps.Z and nfl.2.ps.Z. Craig Hicks then writes: >>> However, I interpret the assertion that anti-cross validation can be expected to work as well as cross-validation to mean that we can equally well expect cross-validation to lie. That is, if cross-validation is telling us that the generalization error is decreasing, we can expect, on average, that the true generalization error is not decreasing. Isn't this a contradiction, if we assume that the samples are really randomly chosen? Of course, we can a posteriori always choose a worst case function which fits the samples taken so far, but contradicts the learned model elsewhere. But if we turn things around and randomly sample that deceptive function anew, the learned model will probably be different, and cross-validation will behave as it should. >>> That's part of the power of the NFL theorems - they prove that Hicks' intuition, an intuition many people share, is in fact wrong. >>> I think this follows from the principle that the empirical distribution over an ever larger number of samples converges to the the true distribution of a single sample (assuming the true distribution is stationary). >>> Nope. The central limit theorem is not directly germane. See all the previous discussion on NFL and Vapnik. >>>> CV is nothing more than the random sampling of prediction ability. If the average over the ensemble of samplings of this ability on 2 different models A and B come out showing that A is better than B, then by definition A is better than B. This assumes only that the true domain and the ensemble of all samplings coincide. Therefore CV will not, on average, cause a LOSS in prediction ability. That is, when it fails, it fails gracefully, on average. It cannot be consistently deceptive. Fortunately, CV will report this (failure to generalize) by showing a zero correlation between prediction and true value on the off training set data. (Of course this is only the performance of CV on average over the ensemble of off training set datas; CV may be deceptive for a single off training set data.) >>> This is wrong (or at best misleading). Please read the NFL papers. In fact, if the head-to-head minimax hypothesis concerning xvalidation presented in those papers is correct, xvalidation is wrong more often than it is right. In which case CV is "deceptive" more often (!!!) than not. Lev Goldfarb wrote >>> Strangely as it may sound at first, try to inductively learn the subgroup of some large group with the group structure completely hidden. No statistics will reveal the underlying group structure. >>> It may help if people read some of the many papers (Cox, deFinnetti, Erickson and Smith, etc., etc.) that prove that the only consistent way of dealing with uncertainty is via probability theory. In other words, there is nothing *but* statistics, in the real world. (Perhaps occuring in prior knowledge that you're looking for a group, but statistics nonetheless.) David Wolpert From wahba@stat.wisc.edu Wed Dec 13 18:38:52 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Wed, 13 Dec 95 18:38:50 -0600; AA01725 Received: from hera.stat.wisc.edu by lucy.cs.wisc.edu; Wed, 13 Dec 95 18:38:48 -0600 Date: Wed, 13 Dec 95 18:38:44 -0600 From: wahba@stat.wisc.edu (Grace Wahba) Message-Id: <9512140038.AA19603@hera.stat.wisc.edu> Received: by hera.stat.wisc.edu; Wed, 13 Dec 95 18:38:44 -0600 To: dhw@santafe.edu, ml@lucy.cs.wisc.edu Subject: Re: The last of a dying thread Cc: wahba@stat.wisc.edu **right, nothing *but* statistics!!! (g wahba, prof of statistics :->) From wray@ptolemy-ethernet.arc.nasa.gov Thu Dec 14 17:13:00 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Thu, 14 Dec 95 17:12:51 -0600; AA16437 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Thu, 14 Dec 95 17:12:48 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa22752; 13 Dec 95 17:39:15 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa22746; 13 Dec 95 17:12:41 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa08952; 13 Dec 95 17:11:55 EST Received: from CS.CMU.EDU by B.GP.CS.CMU.EDU id aa13005; 13 Dec 95 17:11:08 EST Received: from ptolemy-fddi1.arc.nasa.gov by CS.CMU.EDU id aa10334; 13 Dec 95 17:09:46 EST Received: from darush.arc.nasa.gov by ptolemy.arc.nasa.gov (4.1/) id for connectionists@CS.CMU.EDU; Wed, 13 Dec 95 14:06:42 PST Date: Wed, 13 Dec 95 14:06:42 PST From: Wray Buntine Message-Id: <9512132206.AA08307@ptolemy.arc.nasa.gov> To: connectionists@cs.cmu.edu Subject: one revised paper and NIPS slides by Buntine Dear Connectionists Please note the following two WWW resources. One, a forthcoming journal paper, and the other, slides from a NIPS'95 Workshop presentation. Also, please note my new address, email, and company. I am no longer at Heuristicrats. Wray Buntine Thinkbank, Inc. +1 (510) 540-6080 [voice] 1678 Shattuck Avenue, Suite 320 +1 (510) 540-6627 [fax] Berkeley, CA 94709 wray@Thinkbank.COM ============ Article URL: http://www.thinkbank.com/wray/graphbib.ps.Z (about 240Kb compressed) TITLE: A guide to the literature on learning probabilistic networks from data AUTHOR: Wray Buntine, Thinkbank JOURNAL: Accepted for IEEE Trans. on Knowledge and Data Eng., Final draft submitted. ABSTRACT: This literature review discusses different methods under the general rubric of learning Bayesian networks from data, and includes some overlapping work on more general probabilistic networks. Connections are drawn between the statistical, neural network, and uncertainty communities, and between the different methodological communities, such as Bayesian, description length, and classical statistics. Basic concepts for learning and Bayesian networks are introduced and methods are then reviewed. Methods are discussed for learning parameters of a probabilistic network, for learning the structure, and for learning hidden variables. The presentation avoids formal definitions and theorems, as these are plentiful in the literature, and instead illustrates key concepts with simplified examples. KEYWORDS: Bayesian networks, graphical models, hidden variables, learning, learning structure, probabilistic networks, knowledge discovery =========== Talk URL: http://www.thinkbank.com/wray/refs.html (and look under Talks for NIPS) TITLE: Compiling Probabilistic Networks and Some Questions this Poses. AUTHOR: Wray Buntine WORKSHOP: NIPS'95 Workshop on Learning Graphical Models ABSTRACT: Probabilistic networks (or similar) provide a high-level language that can be used as the input to a compiler for generating a learning or inference algorithm. Example compilers are BUGS (inputs a Bayes net with plates) by Gilks, Spiegelhalter, et al., and MultiClass (inputs a dataflow graph) by Roy. This talk will cover three parts: (1) an outline of the arguments for such compilers for probabilistic networks, (2) an introduction to some compilation techniques, and (3) the presentation of some theoretical challenges that compilation poses. High-level language compilers are usually justified as a rapid prototyping tool. In learning, rapid prototyping arises for the following reasons: good priors for complex networks are not obvious and experimentation can be required to understand them; several algorithms may suggest themselves and experimentation is required for comparative evaluation. These and other justifications will be described in the context of some current research on learning probabilistic networks, and past research on learning classification trees and feed-forward neural networks. Techniques for compilation include the data flow graph, automatic differentiation, Monte Carlo Markov Chain samplers of various kinds, and the generation of C code for certain exact inference tasks. With this background, I will then pose a number of research questions to the audience. =========== From bernabe@cnm.us.es Thu Dec 14 17:13:02 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Thu, 14 Dec 95 17:12:53 -0600; AA16439 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Thu, 14 Dec 95 17:12:50 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa22884; 13 Dec 95 19:38:02 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa22882; 13 Dec 95 19:24:58 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa09049; 13 Dec 95 19:24:35 EST Received: from CS.CMU.EDU by B.GP.CS.CMU.EDU id aa13312; 12 Dec 95 7:42:29 EST Received: from cnm1.cnm.us.es by CS.CMU.EDU id aa26057; 12 Dec 95 7:41:07 EST Received: from cnm12.cnm.us.es by cnm1.cnm.us.es (4.1/SMI-4.1) id AA17985; Tue, 12 Dec 95 13:39:42 +0100 Date: Tue, 12 Dec 95 13:39:41 +0100 From: "Bernabe Linares B." Message-Id: <9512121239.AA17985@cnm1.cnm.us.es> To: Connectionists-Request@cs.cmu.edu Subject: two papers in neuroprose FTP-host: archive.cis.ohio-state.edu FTP-file: pub/neuroprose/bernabe.art1-nn.ps.Z (30 pages, 257846 bytes) pub/neuroprose/bernabe.art1-vlsi.ps.Z (26 pages, 311686 bytes) The files "bernabe.art1-nn.ps.Z" and "bernabe.art1-vlsi.ps.Z" are now available for copying from the Neuroprose repository. They contain two papers which have been accepted for publication in the following journals: PAPER1: Journal: IEEE Transactions on VLSI Systems Title: "A Real-Time Clustering Microchip Neural Engine" File: bernabe.art1-vlsi.ps.Z PAPER2: Journal: Neural Networks Title: "A Modified ART1 Algorithm more suitable for VLSI Implementations" File: bernabe.art1-nn.ps.Z Authors: Teresa Serrano-Gotarredona and Bernabe Linares-Barranco Filiation: National Microelectronics Center (CNM), Sevilla, SPAIN. Sorry, no hardcopies available. Brief description of papers follows: -------------------------------------------------------------------- PAPER1: ------- File: bernabe.art1-vlsi.ps.Z, 26 pages, 311686 bytes. Title: "A Real-Time Clustering Microchip Neural Engine" Abstract This paper presents an analog current-mode VLSI implementation of an unsupervised clustering algorithm. The clustering algorithm is based on the popular ART1 algorithm [1], but has been modified resulting in a more VLSI-friendly algorithm [2], [3] that allows a more efficient hardware implementation with simple circuit operators, little memory requirements, modular chip assembly capability, and higher speed figures. The chip described in this paper implements a network that can cluster 100 binary pixels input patterns into up to 18 different categories. Modular expansibility of the system is directly possible by assembling an NxM array of chips without any extra interfacing circuitry, so that the maximum number of clusters is 18xM and the maximum number of bits of the input pattern is Nx100. Pattern classification and learning is performed in 1.8us, which is an equivalent computing power of 4.4x10^9 connections per second plus connection-updates per second. The chip has been fabricated in a standard low cost 1.6um double-metal single-poly CMOS process, has a die area of 1cm^2, and is mounted in a 120-pin PGA package. Although internally the chip is analog in nature, it interfaces to the outside world through digital signals, and thus has a true asynchronous digital behavior. Experimental chip test results are available, obtained through digital chip test equipment. Fault tolerance at the system level operation is demonstrated through the experimental testing of faulty chips. -------------------------------------------------------------------- PAPER2: ------- File: bernabe.art1-nn.ps.Z, 30 pages, 257846 bytes. Title: "A Modified ART1 Algorithm more suitable for VLSI Implementations" Abstract This paper presents a modification to the original ART1 algorithm [Carpenter, 1987a] that is conceptually similar, can be implemented in hardware with less sophisticated building blocks, and maintains the computational capabilities of the originally proposed algorithm. This modified ART1 algorithm (which we will call here ART1m) is the result of hardware motivated simplifications investigated during the design of an actual ART1 chip [Serrano, 1994, 1996]. The purpose of this paper is simply to justify theoretically that the modified algorithm preserves the computational properties of the original one and to study the difference in behavior between the two approaches. -------------------------------------------------------------------- ftp instructions are: % ftp archive.cis.ohio-state.edu Name : anonymous Password: ftp> cd pub/neuroprose ftp> binary ftp> get bernabe.art1-nn.ps.Z ftp> get bernabe.art1-vlsi.ps.Z ftp> quit % uncompress bernabe.art1-nn.ps.Z % uncompress bernabe.art1-vlsi.ps.Z % lpr -P bernabe.art1-nn.ps % lpr -P bernabe.art1-vlsi.ps These files are also available from the node "ftp.cnm.us.es", user "anonymous", directory /pub/bernabe/publications, files: "NN_art1theory_96.ps.Z" and "TVLSI_art1chip_96.ps.Z". Any feedback will be appreciated. Thanks, Dr. Bernabe Linares-Barranco National Microelectronics Center (CNM) Dept. of Analog Design Ed. CICA, Av. Reina Mercedes s/n, 41012 Sevilla, SPAIN. Phone: 34-5-4239923, Fax: 34-5-4624506, E-mail: bernabe@cnm.us.es From bishopc@helios.aston.ac.uk Thu Dec 14 17:13:03 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Thu, 14 Dec 95 17:12:55 -0600; AA16444 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Thu, 14 Dec 95 17:12:52 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa23905; 14 Dec 95 11:27:45 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa23902; 14 Dec 95 11:09:27 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa09755; 14 Dec 95 11:08:48 EST Received: from EDRC.CMU.EDU by B.GP.CS.CMU.EDU id aa16705; 13 Dec 95 21:09:59 EST Received: from hermes.aston.ac.uk by EDRC.CMU.EDU id aa11998; 13 Dec 95 21:08:56 EST Received: from email.aston.ac.uk by hermes.aston.ac.uk with SMTP (PP); Thu, 14 Dec 1995 02:14:27 +0000 Received: from synapse by email.aston.ac.uk with SMTP (PP) id <04529-0@email.aston.ac.uk>; Wed, 13 Dec 1995 19:56:44 +0000 Message-Id: <1400.9512131952@sun.aston.ac.uk> X-Mailer: exmh version 1.6.2 7/18/95 To: Connectionists@cs.cmu.edu Cc: bishopc@helios.aston.ac.uk Subject: New Book: Neural Networks for Pattern Recognition Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Wed, 13 Dec 1995 19:52:48 +0000 From: "Prof. Chris Bishop" Content-Length: 2781 -------------------------------------------------------------------- NEW BOOK -- NEW BOOK -- NEW BOOK -- NEW BOOK -- NEW BOOK -- NEW BOOK -------------------------------------------------------------------- "Neural Networks for Pattern Recognition" ----------------------------------------- Christopher M. Bishop (Oxford University Press) Full details at: http://neural-server.aston.ac.uk/NNPR/ This book provides the first comprehensive treatment of neural networks from the perspective of statistical pattern recognition. * 504 pages * 160 figures * 129 graded exercises * a self-contained introduction to statistical pattern recogniton * an extensive treatment of Bayesian methods * paperback and hardback editions * 300 references Contents: --------- 1. Statistical Pattern Recognition 2. Probability Density Estimation 3. Single-layer Networks 4. The Multi-layer Perceptron 5. Radial Basis Functions 6. Error Functions 7. Parameter Optimization Algorithms 8. Pre-processing and Feature Extraction 9. Learning and Generalization 10. Bayesian Techniques ***** Instructors wishing to use this text as the basis for a course may request a complimentary examination copy from the publishers. (USA: fax request to 212-726-6442 with brief description of the course) ***** Ordering information: --------------------- ISBN 0-19-853864-2 paperback 0-19-853849-9 hardback USA: 45 dollars paperback ---- 98 dollars hardback Credit card orders: Tel: 1-800-451-7556 (toll free) By post, send payment to: Order Dept. Oxford University Press 2001 Evans Road Cary, NC 27513 USA (3 dollars shipping for first copy, 1 dollar each thereafter) Canada: Tel: 1-800-387-8020 (toll free) ------- UK: 25 pounds paperback --- 55 pounds hardback Tel: 01536 454 534 (from the UK) Tel: +44 1536 454 534 (from abroad) By post, send payment to: CWO Department Oxford University Press Saxon Way West, Corby Northants NN18 9ES, UK (3.53 pounds postage) By fax: 01536 746 337 (from the UK) +44 1536 746 337 (from abroad) ---------------------------------------------------------------------- Prof. Christopher M. Bishop Tel. +44 (0)121 333 4631 Neural Computing Research Group Fax. +44 (0)121 333 4586 Dept. of Computer Science c.m.bishop@aston.ac.uk & Applied Mathematics http://neural-server.aston.ac.uk/ Aston University Birmingham B4 7ET, UK ---------------------------------------------------------------------- From lemm@LORENTZ.UNI-MUENSTER.DE Thu Dec 14 17:13:04 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Thu, 14 Dec 95 17:12:49 -0600; AA16435 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Thu, 14 Dec 95 17:12:46 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa22744; 13 Dec 95 17:27:40 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa22742; 13 Dec 95 17:11:39 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa08943; 13 Dec 95 17:11:27 EST Received: from RI.CMU.EDU by B.GP.CS.CMU.EDU id aa11817; 13 Dec 95 16:19:23 EST Received: from LORENTZ.UNI-MUENSTER.DE by RI.CMU.EDU id aa13892; 13 Dec 95 10:12:28 EST Received: by xtp141.uni-muenster.de (5.65/DEC-Ultrix/4.3) id AA13879; Wed, 13 Dec 1995 15:46:52 +0100 Date: Wed, 13 Dec 1995 15:46:52 +0100 From: Joerg_Lemm Message-Id: <9512131446.AA13879@xtp141.uni-muenster.de> To: Connectionists@cs.cmu.edu Subject: NFL and practice Some remarks to Craig Hicks arguments on crossvalidation and NFL in general from my point of view: One may discuss NFL for theoretical reasons, but the conditions under which NFL-Theorems hold are not those which are normally met in practice. 1.) In short, NFL assumes that data, i.e. information of the form y_i=f(x_i), do not contain information about function values on a non-overlapping test set. This is done by postulating "unrestricted uniform" priors, or uniform hyperpriors over nonumiform priors... (with respect to Craig's two cases this average would include a third case: target and model are anticorrelated so anticrossvalidation works better) and "vertical" likelihoods. So, in a NFL setting data never say something about function values for new arguments. This seems rather trivial under this assumption and one has to ask how natural is such a NFL situation. 2.) Information of the form y_i=f(x_i) is rather special and not what we normally have. There is much information which is not of this "single sharp data" type. (Examples see below.) There is absolutly no reason why information which depends on more than one f(x_i) should not be incorporated. (This can be done using nonuniform priors or in a way more symmetrical to "sharp data".) NFL just describes the situation in which we don't have any such information but much of the (then quite useless) "sharp data". But these sharp data are not less (maybe more) obscure as other forms of information. Information which is not of this "single sharp data" form but includes many or all f(x_i) to produce one answer normally induces correlations between target and generalizer if included into the generalizer. At the same time there is no real off training set anymore! Examples: 3) Informations like symmetries (even if only approximate), maxima, Fouriercomponents (and much, much more ...) involve more than one f(x_i). Fouriercomponents, for example, can be seen as sharp data but for different basisvectors, i.e. asking for momentum instead of location. This shows again, that the definition of "sharp data" corresponds to choosing a "basis of questions" and is no natural entity!!! 4) Real measurements (especially of continuous variables) normally do also NOT have the form y_i=f(x_i) ! They mostly perform some averaging over f(x_i) or at least they have some noise on the x_i (as small as you like, but present). In the latter case of "sharp" noise posing the same question several times gives you also an average of several (nearby) y with different x_i of the underlying true function. In both cases the averaging is equivalent to regularization for the "effective" function which we can observe!!! This shows that smoothness of the expectation (in contrast to uniform priors) is the result of the measurement process and therefore is a real phenomena for "effective" functions. There is no need to see it just as a subjective prior! (The same could be said on a quantummechanical level, but that's another story.) It follows that NFL results do NOT hold for the "effective" functions in such situations, even if assuming NFL for the underlying true functions. 5.) NFL again: Averaging or noise in the input space of the x_i requires a probability distribution in that space which can be defined independently from a specific function. Noise means that x_i is a random variable dependend from an actual question z_i, i.e. p(actual argument = x_i | question=z_i) and it is f(z_i) which we can observe. If you don't accept a given p(x_i|z_i), I am sure you can average over "all possible" of such relations with unrestricted "uniform" priors to find that it is impossible to obtain any information about any function without assuming a priori that you know something about what you are asking. This could be seen as another NFL-Theorem for questions: You do not even get informations about a single function value if you don't know (assume,define) a priori what you are asking! 6.) With respect to the underlying "true" function off-training set error itself, an important concept for NFL, is in general no longer a measurable quantity if input noise or averaging is present!! (For simplicity let's assume that noise or averaging includes all questions x_i. Then in the case of noise you only have a probability for the x_i to belong to the "true" training set and averaging includes all questions x_i.) So for the "true" functions there remains nothing NFL can say something about and for the "effective" functions NFL is not valid! To conclude: In many interesting cases "effective" function values contain information about other function values and NFL does not hold! The very special handling of "sharp data" in comparison to other information must be discussed for much more learning theories. Joerg Lemm (Institute for Theoretical Physics I, University of Muenster, Germany) From zhuh@helios.aston.ac.uk Fri Dec 15 12:33:01 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Fri, 15 Dec 95 12:32:56 -0600; AA28827 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Fri, 15 Dec 95 12:32:54 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa24324; 14 Dec 95 17:52:38 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa24322; 14 Dec 95 17:39:55 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa10004; 14 Dec 95 17:39:51 EST Received: from RI.CMU.EDU by B.GP.CS.CMU.EDU id aa00294; 14 Dec 95 13:15:24 EST Received: from [134.151.79.46] by RI.CMU.EDU id aa19580; 14 Dec 95 13:15:07 EST Received: from email.aston.ac.uk by hermes.aston.ac.uk with SMTP (PP); Thu, 14 Dec 1995 18:18:13 +0000 Received: from darwin by email.aston.ac.uk with SMTP (PP) id <23668-0@email.aston.ac.uk>; Thu, 14 Dec 1995 18:17:15 +0000 From: zhuh Date: Thu, 14 Dec 1995 18:12:43 +0000 Message-Id: <2237.9512141812@sun.aston.ac.uk> To: connectionists@cs.cmu.edu Subject: No free lunch for Cross Validation! X-Sun-Charset: US-ASCII Content-Length: 5656 Dear Colleagues, A little while ago someone claimed that Cross validation will benefit from the presence of any structure, and if there is no structure it does no harm; yet NFL explicitly states that a structure can be equally good or bad for any given method, depending on how they match each other; yet It was further claimed that they do not conflict with each other. I was quite curious and did the following five-minute experiment to find out which is correct. Suppose we have a Gaussian variable x, with mean mu and unit variance. We have the following three estimators for estimating mu from a sample of size n. A: The sample mean. It is optimal both in the sense of Maximum Likelihood and Least Mean Squares. B: The maximum of sample. It is a bad estimator in any reasonable sense. C: Cross validation to choose between A and B, with one extra data point. The numerical result with n=16 and averaged over 10000 samples, gives mean squared error: A: 0.0627 B: 3.4418 C: 0.5646 This clearly shows that cross validation IS harmful in this case, despite the fact it is based on a larger sample. NFL still wins! Many of you might jump on me at this point: But this is a very artificial example, which is not what normally occurs in practice. To this I have two answers, short and long. The short answer is from principle. Any counter-example, however artificial it is, clearly demolishes the hope that cross validation is a "universally beneficial method". The longer answer is divided in several parts, which hopefully will answer any potential criticism from any aspect: 1. The cross validation is performed on extra data points. We are not requiring it to perform as good as the mean on 17 data points. If it cannot extract more information from the one extra data point, a minimum requirement is that it keeps the information in the original 16 points. But it can't even do this. 2. The maximum of a sample is the 100 percentile. The median is the 50 percentile, which is in fact a quite reasonable estimator. Let us use a larger cross validation set (of size k), and replace B with a different percentile. The result is that, for the median, CV needs k>2 to work. For 70 percentile CV needs k>16. The required k increases dramatically with the percentile. 3. It is not true that we have set up a case in which cross validation can't win. There is indeed a small probability that a sample can be so bad that the sample maximum is even a better estimate than the sample mean. However to utilise such rare chances to good effect k must be at least several hundred (maybe exponential) while n=16. We know such k exists since k=infinity certainly helps. Yet to adopt such a method is clearly absurd. 4. Although we have chosen estimator A to be the known optimal estimator in this case, it can be replaced by something else. For example, both A and B can be some reasonable averages over percentiles, so that without detailed analysis it may appear doing cross validation might give a C which is better than both A and B. Such believes can be defeated by similar counter-examples. 5. The above scheme of cross validation may appear different from what is familiar, but here is a "practical example" which shows that it is indeed what people normally do. Suppose we have a random variable which is either Gaussian or Cauchy. Consider the following three estimators: A: Sample mean: It has 100% efficiency for Gaussian, and 0% efficiency for Cauchy. B: Sample median: It is 2/pi=63.66% efficient for Gaussian and 8/pi^2=81.06% efficient for Cauchy. C: Cross validation on an additional sample of size k, to choose between A and B. Intuitively it appears quite reasonable to expect cross validation to pick out the correct one, for most of the time, so that, if averaged over all samples, C ought to be superior to both A and B. But no!! This will depend on the PRIOR mixing probability of these two sub-models. If the variable is in fact always Gaussian, then we have just seen that if n=16, CV will be worse unless k>2. The same is even more true in the reversed order, since the mean is an essentially useless estimator for Cauchy. 6. In any of the above cases, "anti cross validation" would be even more disastrous. If you are not convinced by these arguments, or if you want to know more about efficiency, then maybe the following reference can help: Fisher, R.A.: Theory of statistical estimation, Proc. Camb. Phil. Soc., Vol. 122, pp. 700-725, 1925. If you are more or less convinced, I have the following speculation: Several centuries ago, the French Academy of Science (or is it the Royal Society?) made a decision that they would no longer examine inventions of "perpetual motion machines", on the ground that the Law of Energy Conservation was so reliable that it would defeat any such attempt. History proved that this was a wise decision, which assisted the effort of designing machines which utilise energy in fuel. Should we expect the same fate for "the universally beneficial methods" in the face of NFL? Should we put more effort in designing methods which use prior information? posterior information <= prior information + data information. -- Huaiyu Zhu, PhD email: H.Zhu@aston.ac.uk Neural Computing Research Group http://neural-server.aston.ac.uk/People/zhuh Dept of Computer Science ftp://cs.aston.ac.uk/neural/zhuh and Applied Mathematics tel: +44 121 359 3611 x 5427 Aston University, fax: +44 121 333 6215 Birmingham B4 7ET, UK From robert@fit.qut.edu.au Fri Dec 15 12:33:10 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Fri, 15 Dec 95 12:32:59 -0600; AA28833 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Fri, 15 Dec 95 12:32:56 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa24663; 14 Dec 95 21:27:30 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa24661; 14 Dec 95 21:17:44 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa10132; 14 Dec 95 21:17:28 EST Received: from RI.CMU.EDU by B.GP.CS.CMU.EDU id ac08610; 14 Dec 95 21:13:20 EST Received: from ocean.fit.qut.edu.au by RI.CMU.EDU id aa21085; 14 Dec 95 19:38:23 EST Received: (from robert@localhost) by ocean.fit.qut.edu.au (8.7.3/8.7.2) id KAA15975; Fri, 15 Dec 1995 10:24:10 +1000 (EST) Message-Id: <199512150024.KAA15975@ocean.fit.qut.edu.au> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Fri, 15 Dec 1995 10:24:04 +1000 To: connectionists@cs.cmu.edu From: Robert Andrews Subject: Rule Extraction Mailing List Cc: intcon@phoenix.ee.unsw.EDU.AU, EP-LIST@magenta.me.fau.edu, alife@cognet.ucla.edu, INDUCTIVE@hermes.csd.unb.ca, hybrid-list@cs.ua.edu, r.dybowski@miranda.umds.ac.uk X-Mailer: =-=-=-=-= RULE EXTRACTION FROM ARTIFICIAL NEURAL NETWORKS =-=-=-=-=-=-=-=- ANNOUNCEMENT OF MAILING LIST Rule Extraction from Artificial Neural Networks and the related field of Rule Refinement are topics of increasing interest and importance. This is to announce the formation of a moderated mailing list for researchers and students interested in these areas. If you are interested in becoming a subscriber to this list please send the following information by return mail: Name: Organisation/Institution: E-mail Address: =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- Mr Robert Andrews School of Information Systems robert@fit.qut.edu.au Faculty of Information Technology R.Andrews@qut.edu.au Queensland University of Technology +61 7 864 1656 (voice) GPO Box 2434 _--_|\ +61 7 864 1969 (fax) Brisbane Q 4001 / QUT Australia \_.--._/ http://www.fit.qut.edu.au/staff/~robert v =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- From C.Campbell@bristol.ac.uk Fri Dec 15 23:29:25 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Fri, 15 Dec 95 23:29:20 -0600; AA05771 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Fri, 15 Dec 95 23:29:17 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa24354; 14 Dec 95 18:01:52 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa24339; 14 Dec 95 17:46:13 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa10017; 14 Dec 95 17:45:40 EST Received: from CS.CMU.EDU by B.GP.CS.CMU.EDU id aa27986; 14 Dec 95 11:24:26 EST Received: from dira.bris.ac.uk by CS.CMU.EDU id aa16283; 14 Dec 95 11:23:45 EST Received: from zeus.bris.ac.uk by dira.bris.ac.uk with SMTP (PP); Thu, 14 Dec 1995 16:21:36 +0000 Received: by zeus.bris.ac.uk (950215.SGI.8.6.10/940406.SGI) for Connectionists@CS.CMU.EDU id QAA11250; Thu, 14 Dec 1995 16:21:26 GMT From: I C G Campbell Message-Id: <199512141621.QAA11250@zeus.bris.ac.uk> Subject: New Web Page (Bristol University, UK) To: Connectionists@cs.cmu.edu Date: Thu, 14 Dec 1995 16:21:26 +0000 (GMT) X-Mailer: ELM [version 2.4 PL21] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 635 The Neural Computing Research Group at Bristol University, UK has recently set up a WWW page describing their interests at: http://www.fen.bris.ac.uk/engmaths/research/neural/neural.html Our interests cover three main areas: theory of neural computation, modelling simple neurobiological systems and applications of neural computing in engineering. Collectively we have produced in excess of 100 publications related to neural computing in these topic areas. Further details about these publications, current research interests and research grants may be found on the above page. Merry Xmas Colin Campbell University of Bristol From l.s.smith@cs.stir.ac.uk Fri Dec 15 23:29:26 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Fri, 15 Dec 95 23:29:22 -0600; AA05775 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Fri, 15 Dec 95 23:29:19 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa25704; 15 Dec 95 8:46:04 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa25702; 15 Dec 95 8:35:08 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa10621; 15 Dec 95 8:34:43 EST Received: from CS.CMU.EDU by B.GP.CS.CMU.EDU id ab15773; 15 Dec 95 6:33:56 EST Received: from dosh.cs.stir.ac.uk by CS.CMU.EDU id aa23528; 15 Dec 95 5:12:42 EST Received: from katrine.cs.stir.ac.uk by dosh.cs.stir.ac.uk (8.6.12) with ESMTP id KAA28144; Fri, 15 Dec 1995 10:12:11 GMT Received: by katrine.cs.stir.ac.uk (8.6.12) id KAA27913; Fri, 15 Dec 1995 10:12:09 GMT Date: Fri, 15 Dec 1995 10:12:09 GMT From: "Dr L S Smith (Staff)" Message-Id: <19951215T101209Z.KAA27913@katrine.cs.stir.ac.uk> Received: by NeXT.Mailer (1.100) Received: by NeXT Mailer (1.100) To: Connectionists@cs.cmu.edu Subject: TR on generalization available Cc: lss@cs.stir.ac.uk Dear all: We have a new TR available by ftp from here: CCCN Technical report CCCN-21, December 1995. A Theoretical Study of the Generalization Ability of Feed-Forward Neural Networks. M J Roberts. By making assumptions on the probability distribution of the potentials in a feed-forward neural network we have derived lower bounds for the generalization ability of the network in terms of the number of training patterns. The results are consistent with simulations carried out on a simple geometrical function. The URL is ftp://ftp.cs.stir.ac.uk/pub/tr/cccn/TR21.ps.Z If you really can't access this hard copies are available, but only as a last resort. Dr Leslie S. Smith Dept of Computing and Mathematics, Univ of Stirling Stirling FK9 4LA Scotland lss@cs.stir.ac.uk (NeXTmail welcome) Tel (44) 1786 467435 Fax (44) 1786 464551 www http://www.cs.stir.ac.uk/~lss/ From lemm@LORENTZ.UNI-MUENSTER.DE Fri Dec 15 23:29:31 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Fri, 15 Dec 95 23:29:26 -0600; AA05785 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Fri, 15 Dec 95 23:29:24 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa26045; 15 Dec 95 15:41:17 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa26043; 15 Dec 95 15:32:34 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa10764; 15 Dec 95 15:31:47 EST Received: from RI.CMU.EDU by B.GP.CS.CMU.EDU id aa24815; 15 Dec 95 15:15:27 EST Received: from LORENTZ.UNI-MUENSTER.DE by RI.CMU.EDU id aa23671; 15 Dec 95 11:12:19 EST Received: by xtp141.uni-muenster.de (5.65/DEC-Ultrix/4.3) id AA24811; Fri, 15 Dec 1995 15:28:49 +0100 Date: Fri, 15 Dec 1995 15:28:49 +0100 From: Joerg_Lemm Message-Id: <9512151428.AA24811@xtp141.uni-muenster.de> To: Connectionists@cs.cmu.edu Subject: Re: NFL and practice Huaiyu Zhu responsed to >> One may discuss NFL for theoretical reasons, but >> the conditions under which NFL-Theorems hold >> are not those which are normally met in practice. and wrote >Exactly the opposite. The theory behind NFL is trivial (in some sense). >The power of NFL is that it deals directly with what is rountinely >practiced in the neural network community today. That depends on how you understand practice. E.g. in nearly all cases functions are somewhat smooth. This is a prior which exists in reality (for example because of input noise in the measuring process). And the situation would we hopeless if we would not use this fact in practice. (That is just what also NFL says.) But, if Huaiyu means that it is necessary to think about the priors in "practice" explicitly, then I fully aggree! But what I wanted to say is: WE DO HAVE "PRIORS" (BETTER SAY CORRELATIONS BETWEEN ANSWERS TO DIFFERENT QUESTIONS) IN MOST CASES and they are NOT obscure, but very often at least as well MEASUREABLE as "normal" sharp data y_i=f(x_i). Even more: situations without "priors" are VERY artificial. So if we specify the "priors" (and the lesson from NFL is that we should if we want to make a good theory) then we cannot use NFL anymore.(What should it be used for then?) >Joerg continued with examples of various priors of practical concern, >including smoothness, symmetry, positive correlation, iid samples, etc. >These are indeed very important priors which match the real world, >and they are the implicit assumptions behind most algorithms. > >What NFL tells us is: If your algorithm is designed for such a prior, >then say so explicitly so that a user can decide whether to use it. >You can't expect it to be also good for any other prior which you have >not considered. In fact, in a sense, you should expect it to perform >worse than a purely random algorithm on those other priors. Maybe the problem is that Huaiyu Zhu uses the word "PRIOR" for every information which is not of the sharp data form y_i=f(x_i). It suggests that we know something before starting our generalizer. NO, that is not the normal case!!! I mentioned many examples (like measurement with input noise) where "priors" are just normal information which should be used DURING learning like sharp data! (Sharp data might be even not available at all!) And of course using wrong "priors" is similar to using wrong sharp data. But I fully aggree that most algorithm uses "prior" information only implicitly and that there is a lot of theoretical work to do. In response to >> In many interesting cases "effective" function values contain information >> about other function values and NFL does not hold! Huaiyu Zhu continues >This is like saying "In many interesting cases we do have energy sources, >and we can make a machine running forever, so the natural laws against >`perpetual motion machines' do not hold." Indeed, it is a little bit like that, but a system without energy sources is a much better approximation for some real world systems compared to a world without "priors" (i.e. without correlated answers over different questions)! So the energy law is useful, but models for worlds without correlated information are NOT, except maybe that they tell us to include the correlation properly! Joerg Lemm (Institute for Theoretical Physics I, University of Muenster, Germany) From shastri@ICSI.Berkeley.EDU Fri Dec 15 23:29:32 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Fri, 15 Dec 95 23:29:28 -0600; AA05787 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Fri, 15 Dec 95 23:29:26 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa26405; 15 Dec 95 19:47:46 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa26403; 15 Dec 95 19:37:23 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa10870; 15 Dec 95 19:37:16 EST Received: from RI.CMU.EDU by B.GP.CS.CMU.EDU id aa26722; 15 Dec 95 16:35:53 EST Received: from icsia.ICSI.Berkeley.EDU by RI.CMU.EDU id aa25115; 15 Dec 95 16:34:30 EST Received: from kulfi.ICSI.Berkeley.EDU (shastri@kulfi.ICSI.Berkeley.EDU [128.32.201.148]) by icsia.ICSI.Berkeley.EDU (8.6.12/HUB+V8$Revision: 1.23 $) with ESMTP id NAA23673 for ; Fri, 15 Dec 1995 13:34:26 -0800 Received: from localhost (shastri@localhost) by kulfi.ICSI.Berkeley.EDU (8.6.12/1.8) with ESMTP id NAA06683 for ; Fri, 15 Dec 1995 13:34:24 -0800 Message-Id: <199512152134.NAA06683@kulfi.ICSI.Berkeley.EDU> X-Authentication-Warning: kulfi.ICSI.Berkeley.EDU: shastri owned process doing -bs To: connectionists@cs.cmu.edu Subject: Technical report --- negated knowledge and inconsistency Date: Fri, 15 Dec 1995 13:34:24 PST From: Lokendra Shastri Dealing with negated knowledge and inconsistency in a neurally motivated model of memory and reflexive reasoning. Lokendra Shastri and Dean J. Grannes TR-95-041 ICSI August 1995 Recently, SHRUTI has been proposed as a connectionist model of rapid reasoning. It demonstrates how a network of simple neuron- like elements can encode a large number of specific facts as well as systematic knowledge (rules) involving n-ary relations, quanti- fication and concept hierarchies, and perform a class of reasoning with extreme efficiency. The model, however, does not deal with negated facts and rules involving negated antecedents and consequents. We describe an extension of SHRUTI that can encode positive as well as negated knowledge and use such knowledge during reflexive reasoning. The extended model explains how an agent can hold inconsistent knowledge in its long-term memory without being ``aware'' that its beliefs are inconsistent, but detect a contradiction whenever inconsistent beliefs that are within a certain inferential distance of each other become co-active during an episode of reasoning. Thus the model is not logically omniscient, but detects contradictions whenever it tries to use inconsistent knowledge. The extended model also explains how limited attentional focus or action under time pressure can lead an agent to produce an erroneous response. A biologically signficant feature of the model is that it uses only local inhibition to encode negated knowledge. Like the basic model, the extended model encodes and propagates dynamic bindings using temporal synchrony. Key Words: long-term memory; rapid reasoning; dynamic bindings; synchrony; knowledge representation; neural oscillations; short-term memory; negation; inconsistent knowledge. ftp-server: ftp.icsi.berkeley.edu (128.32.201.55) ftp-file: /pub/techreports/1995/tr-95-041.ps.Z Lokendra Shastri International Computer Science Institute 1947 Center Street, Suite 600 Berkeley, CA 94704 http://www.icsi.berkeley.edu/~shastri ========================== Detailed instructions for retrieving the report: unix% ftp ftp.icsi.berkeley.edu Name (ftp.icsi.berkeley.edu:): anonymous Password: your_name@your_machine ftp> cd /pub/techreports/1995 ftp> binary ftp> get tr-95-041.ps.Z ftp> quit unix% uncompress tr-95-041.ps.Z unix% lpr tr-95-041.ps If your name server does not know about ftp.icsi.berkeley.edu, use 128.32.201.55 instead. All files in this archive can also be obtained through an e-mail interface in case direct ftp is not available. To obtain instructions, send mail containing the line `send help' to: ftpmail@ICSI.Berkeley.EDU As a last resort, hardcopies may be ordered for a small fee. Send mail to info@ICSI.Berkeley.EDU for more information. From cherkaue@lucy.cs.wisc.edu Fri Dec 15 23:29:34 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Fri, 15 Dec 95 23:29:30 -0600; AA05797 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Fri, 15 Dec 95 23:29:28 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa26424; 15 Dec 95 19:56:10 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa26407; 15 Dec 95 19:38:13 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa10876; 15 Dec 95 19:37:49 EST Received: from CS.CMU.EDU by B.GP.CS.CMU.EDU id aa29177; 15 Dec 95 19:03:51 EST Received: from mozzarella.cs.wisc.edu by CS.CMU.EDU id aa29724; 15 Dec 95 19:03:18 EST Received: (from cherkaue@localhost) by mozzarella.cs.wisc.edu (8.6.12/8.6.12) id SAA03324; Fri, 15 Dec 1995 18:03:15 -0600 Date: Fri, 15 Dec 1995 18:03:15 -0600 Message-Id: <199512160003.SAA03324@mozzarella.cs.wisc.edu> From: cherkaue@lucy.cs.wisc.edu To: connectionists@cs.cmu.edu Subject: Re: No free lunch for Cross Validation! Cc: cherkauer@mozzarella.cs.wisc.edu Content-Length: 1632 In reply to Huaiyu Zhu's message > ... > >A little while ago someone claimed that > Cross validation will benefit from the presence of any structure, > and if there is no structure it does no harm; > > ... > >Suppose we have a Gaussian variable x, with mean mu and unit variance. >We have the following three estimators for estimating mu from a >sample of size n. > A: The sample mean. It is optimal both in the sense of Maximum >Likelihood and Least Mean Squares. > B: The maximum of sample. It is a bad estimator in any reasonable sense. > C: Cross validation to choose between A and B, with one extra data point. > >The numerical result with n=16 and averaged over 10000 samples, gives >mean squared error: > A: 0.0627 B: 3.4418 C: 0.5646 >This clearly shows that cross validation IS harmful in this case, >despite the fact it is based on a larger sample. NFL still wins! You forgot D: Anti-cross validation to choose between A and B, with one extra data point. I don't understand your claim that "cross validation IS harmful in this case." You seem to equate "harmful" with "suboptimal." Cross validation is a technique we use to guess the answer when we don't already know the answer. You give technique A the benefit of your prior knowledge of the true answer, but C must operate without this knowledge. A fair comparison would pit C against D, not C against A. As you say: >6. In any of the above cases, "anti cross validation" would be even >more disastrous. Kevin Cherkauer Computer Sciences Dept. University of Wisconsin-Madison cherkauer@cs.wisc.edu From bastiane@irit.fr Fri Dec 15 23:29:39 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Fri, 15 Dec 95 23:29:24 -0600; AA05783 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Fri, 15 Dec 95 23:29:21 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa25944; 15 Dec 95 12:42:17 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa25942; 15 Dec 95 12:27:04 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa10702; 15 Dec 95 12:25:48 EST Received: from EDRC.CMU.EDU by B.GP.CS.CMU.EDU id aa19131; 15 Dec 95 9:29:40 EST Received: from [141.115.4.1] by EDRC.CMU.EDU id aa19013; 15 Dec 95 9:29:10 EST Received: from [141.115.8.6] (nomade.irit.fr [141.115.8.6]) by irit.irit.fr (8.6.10/8.6.12) with SMTP id PAA05193; Fri, 15 Dec 1995 15:07:57 +0100 Date: Fri, 15 Dec 1995 15:07:57 +0100 Message-Id: <199512151407.PAA05193@irit.irit.fr> X-Sender: bastiane@irit Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable To: NEURO1-L@UICVM.CC.UIC.EDU, neuron-request@CATTELL20.psych.upenn.edu, Connectionists@cs.cmu.edu, enns-list@dcs.kcl.ac.uk, neur-sci@dl.ac.uk, comp-neuro@smaug.bbb.caltech.edu, frog-net@rana.usc.edu, cogni-info@univ-lyon1.fr, neuropl@plearn.edu.pl From: bastiane@irit.fr Subject: Call for papers for DYNN'96 Cc: doyon@cict.fr, Manuel.Samuelides@supaero.fr CALL FOR PAPERS FOR DYNN'96 International workshop on NEURAL NETWORKS DYNAMICS AND PATTERN RECOGNITION. Toulouse - France =20 12 and 13 of March 1996 Organized by ONERA-CERT Sponsored by DRET of French MOD, US Air Force Scientific Research= and Pole Universitaire Europeen de Toulouse. Organizers: Manuel SAMUELIDES (ONERA-CERT), Bernard DOYON (INSERM), Gregory TARR (US AF), Simon THORPE (CNRS). Practical Information: Emmanuel DAUCE (dauce@cert.fr) *********************** OBJECTIVES OF THE WORKSHOP. *************************** This workshop is designed to allow information exchange and discussion between theoretical scientists working on models of neuronal dynamics= and engineersnners who are looking for efficient devices to process sensor information. Continuous activation state units as well as Integrate and Fire neurons= =20 or oscillators are elementary components of Dynamical Neural Networks. Attractor neural networks as well as transitory data-driven dynamics= will be considered. The common features between these models is the conversion of spatial information into spatio-temporal data flow which allows= specific processing. Mathematical models involved use dynamical systems and stochastic= processes. They will be compared to the results of numerical simulations and= the latest neuro-physiological data concerning the dynamics of biological neural= nets. The main aim of the workshop is to encourage significant advances= concerning the dynamics of biologically plausible neural networks and their= applications to pattern recognition. *********************** ORGANIZATION OF THE WORKSHOP. ***************************** Scheduled talks will take place on the 12th and the 13 th of March.= There will be invited talks as well as submitted contributions. About 24 talks= of 30 minutes will be scheduled with time for discussion and panels. Informal discussion and collective work may be scheduled on the 14= th. Extended abstract (one or two pages) of submitted contribution have= to be send for acceptation by e-mail to dauce@cert.fr or by post to Manuel Samuelides,=20 DERI ONERA-CERT, BP 4025, 31055 Toulouse CEDEX, FRANCE. =20 Provisional list of invited lecturers: J.P.AUBIN, M.COTTRELL, J.DEMONGEOT, J.DAYHOFF,G.DREYFUS, M.HIRSCH, J.TAYLOR. (This list will be completed) The number of attendants to the workshop is limited to 40 in order to allow living exchange and real discussion. Copies of abstracts and slides will be provided to participants. The registration fees amount to FF 1,200 including 2 nights with= american breakfast(11th and 12 th) at a first class hotel in downtown Toulouse (Holyday Inn, Crown Plaza), two lunches on the site of the workshop, the workshop banquet, transportation to and from CERT,= coffee beaks, the general costs of the workshop facilities and equipment. Payment should be made either by check payable to " AGENT COMPTABLE DU CERT ONERA " in French francs only or by Bank transfer to "AGENT COMPTABLE DU CERT ONERA" Bank: Societe Generale Ramonville Saint Agne Account N=B0 30003 /02117/ 00037291008/93 Please state the workshop reference: DYNN'96 on all transactions. *********************** IMPORTANT DATES: **************** 15th of January: Dead-line for contributions and declarations of= interest. 31 th of January: Date for signification of accepted contribution and expedition of final programming of the workshop 15 th of February: Dead-Line for Inscriptions to the workshop. To avoid postage delay, e-mail will be accepted as a usual communication If you want to attend DYNN'96 please use your computer to reply at= once ----------------------------------------------------------------------------= ---- Name Organization Adress e mail ( ) wishes the information about the final program ( ) wishes to attend DYNN'96 ( ) will submit a contribution entitled: ----------------------------------------------------------------------------= - Please send your reply to the following e-mail dauce@cert.fr or to xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx x Professor Manuel SAMUELIDES x x DERI ONERA-CERT x x BP 4025 x x 31055 Toulouse CEDEX x x FRANCE x xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx Manuel SAMUELIDES ----------------------------------------------------------------- for research: Chercheur a l'ONERA-CERT samuelid@cert.fr for Teaching Professeur a l'ENSAE Manuel.Samuelides@supaero.fr Tel: (33) 62 17 81 06 Fax: (33) 62 17 83 30 From pkso@castle.ed.ac.uk Sat Dec 16 19:19:43 1995 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Sat, 16 Dec 95 19:19:39 -0600; AA15005 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Sat, 16 Dec 95 19:19:37 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa28340; 16 Dec 95 18:31:54 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa28338; 16 Dec 95 18:19:24 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa11648; 16 Dec 95 18:19:01 EST Received: from EDRC.CMU.EDU by B.GP.CS.CMU.EDU id aa14028; 16 Dec 95 10:15:17 EST Received: from haymarket.ed.ac.uk by EDRC.CMU.EDU id aa23318; 16 Dec 95 10:13:42 EST Received: from castle.ed.ac.uk (castle.ed.ac.uk [129.215.128.23]) by haymarket.ed.ac.uk (8.6.10/8.6.12) with SMTP id PAA23129 for ; Sat, 16 Dec 1995 15:13:37 GMT From: P Sollich Subject: Thesis on Query Learning available To: Connectionists@cs.cmu.edu Date: Sat, 16 Dec 95 15:06:41 GMT Message-Id: <9512161506.aa29855@uk.ac.ed.castle> FTP-host: archive.cis.ohio-state.edu FTP-filename: /pub/neuroprose/Thesis/sollich.thesis.tar.Z Dear fellow connectionists, the following Ph.D. thesis is now available for copying from the neuroprose archive: ASKING INTELLIGENT QUESTIONS --- THE STATISTICAL MECHANICS OF QUERY LEARNING Peter Sollich Department of Physics University of Edinburgh, U.K. Abstract: This thesis analyses the capabilities and limitations of query learning by using the tools of statistical mechanics to study learning in feed-forward neural networks. In supervised learning, one of the central questions is the issue of generalization: Given a set of training examples in the form of input-output pairs produced by an unknown {\em teacher} rule, how can one generate a {\em student} which {\em generalizes}, i.e., which correctly predicts the outputs corresponding to inputs not contained in the training set? The traditional paradigm has been to study learning from {\em random examples}, where training inputs are sampled randomly from some given distribution. However, random examples contain redundant information, and generalization performance can thus be improved by {\em query learning}, where training inputs are chosen such that each new training example will be maximally `useful' as measured by a given {\em objective function}. We examine two common kinds of queries, chosen to optimize the objective functions, generalization error and entropy (or information), respectively. Within an extended Bayesian framework, we use the techniques of statistical mechanics to analyse the average case generalization performance achieved by such queries in a range of learning scenarios, in which the functional forms of student and teacher are inspired by models of neural networks. In particular, we study how the efficacy of query learning depends on the form of teacher and student, on the training algorithm used to generate students, and on the objective function used to select queries. The learning scenarios considered are simple but sufficiently generic to allow general conclusions to be drawn. We first study perfectly learnable problems, where the student can reproduce the teacher exactly. From an analysis of two simple model systems, the high-low game and the linear perceptron, we conclude that query learning is much less effective for rules with continuous outputs -- provided they are `invertible' in the sense that they can essentially be learned from a finite number of training examples -- than for rules with discrete outputs. Queries chosen to minimize the entropy generally achieve generalization performance close to the theoretical optimum afforded by minimum generalization error queries, but can perform worse than random examples in scenarios where the training algorithm is under-regularized, i.e., has too much `confidence' in corrupted training data. For imperfectly learnable problems, we first consider linear students learning from nonlinear perceptron teachers and show that in this case the structure of the student space determines the efficacy of queries chosen to minimize the entropy in {\em student} space. Minimum {\em teacher} space queries, on the other hand, perform worse than random examples due to lack of feedback about the progress of the student. For students with discrete outputs, we find that in the absence of information about the teacher space, query learning can lead to self-confirming hypotheses far from the truth, misleading the student to such an extent that it will not approximate the teacher optimally even for an infinite number of training examples. We investigate how this problem depends on the nature of the noise process corrupting the training data, and demonstrate that it can be alleviated by combining query learning with Bayesian techniques of model selection. Finally, we assess which of our conclusions carry over to more realistic neural networks, by calculating finite size corrections to the thermodynamic limit results and by analysing query learning in a simple two-layer neural network. The results suggest that the statistical mechanics analysis is often relevant to real-world learning problems, and that the potentially significant improvements in generalization performance achieved by query learning can be made available, in a computationally cheap manner, for realistic multi-layer neural networks. Criticism, comments and suggestions are welcome. Merry Christmas everyone! Peter Sollich -------------------------------------------------------------------------- Peter Sollich Department of Physics University of Edinburgh e-mail: P.Sollich@ed.ac.uk Kings Buildings phone: +44 - (0)131 - 650 5236 Mayfield Road Edinburgh EH9 3JZ, U.K. -------------------------------------------------------------------------- RETRIEVAL INSTRUCTIONS: Get `sollich.thesis.tar.Z' from the `Thesis' subdirectory of the neuroprose archive. Uncompress, and unpack the resulting tar file (on UNIX: uncompress sollich.thesis.tar.Z; tar xf - < sollich.thesis.tar). This will yield the postscript files listed below. Contact me if there are any problems with retrieval and or printing. QUICK GUIDE for busy readers: For a first look, see sollich_title.ps (has abstract and table of contents). File sollich_chapter1.ps contains a general introduction to query learning and an overview of the literature. Finally, for a summary of the main results and open questions, see sollich_chapter9.ps. LIST OF FILES: ------------------------------------------------------------------------------ Filename No of Size in KB Contents pages (compressed/ uncompressed) ------------------------------------------------------------------------------ sollich_title.ps 8 37/ 75 Title, Declaration, Acknowledgements, Publications, Abstract, Table of contents ------------------------------------------------------------------------------ sollich_chapter1.ps 8 48/ 98 Introduction ------------------------------------------------------------------------------ sollich_chapter2.ps 10 48/ 101 A probabilistic framework for query selection ------------------------------------------------------------------------------ sollich_chapter3.ps 21 128/ 376 Perfectly learnable problems: Two simple examples ------------------------------------------------------------------------------ sollich_chapter4.ps 19 135/ 337 Imperfectly learnable problems: Linear students ------------------------------------------------------------------------------ sollich_chapter5.ps 40 228/ 565 Query learning assuming the inference model is correct ------------------------------------------------------------------------------ sollich_chapter6.ps 12 244/1050 Combining query learning and model selection ------------------------------------------------------------------------------ sollich_chapter7.ps 20 217/ 558 Towards realistic neural networks I: Finite size effects ------------------------------------------------------------------------------ sollich_chapter8.ps 24 136/ 299 Towards realistic neural networks II: Multi-layer networks ------------------------------------------------------------------------------ sollich_chapter9.ps 5 31/ 59 Summary and Outlook ------------------------------------------------------------------------------ sollich_bib.ps 8 37/ 68 Bibliography ------------------------------------------------------------------------------