Date: Sat 19 Mar 1988 22:18-PST From: AIList Moderator Kenneth Laws Reply-To: AIList@KL.SRI.COM Us-Mail: SRI Int., 333 Ravenswood Ave., Menlo Park, CA 94025 Phone: (415) 859-6467 Subject: AIList V6 #53 - VLSI Testability, Agriculture, Genetic Algorithms To: AIList@KL.SRI.COM Status: RO AIList Digest Sunday, 20 Mar 1988 Volume 6 : Issue 53 Today's Topics: Philosophy - Implications of the Chinese Room, Application - References on VLSI Testibility Checking & Agricultural Uses of AI, Logic - Funny Logics and AI, Course - Graduate Study in AI (Washington University), Genetic Algorithms - Definition and Schools of Research ---------------------------------------------------------------------- Date: 14 Mar 88 11:03 PST From: hayes.pa@Xerox.COM Subject: Re: AIList V6 #51 ..implications of the Chinese Room Adrian G C Redgers writes: >a) I thought Searle's point was that humans might not "understand" >Chinese (or English) and are simply manipulating symbols which >model the world. The 'Chinese room' is then a brain. ... Or was >Searle pointing out that the room is unsatisfactory for those very >reasons? Why not try reading Searle? He couldnt be clearer or more entertaining ( or wronger, but thats another story ). He isnt claiming that brains arent machines, or that humans dont understand Chinese. His point is that a programmed computer cant understand anything, even if it behaves impeccably, passing the Turing test all over the place. Reason: well, the program cant because its just a pile of symbols, and the unprogrammed hardware ( =the man in the room ) certainly doesnt know anything, being just dumb electronics, and that/s all there is in a programmed computer, QED. A brain, now, is different, because of course brains understand things: and the conclusion obviously is that whatever sort of machine the brain is, it isnt a programmed computer. So `strong AI' is wrong, Turing test and all. Weak AI, on the other hand, just claims that it is simulating intelligence on electronics, which is fine ( says Searle ) - probably a scientific mistake, he guesses, but not a philosophical mistake, and immune from the Chinese room argument. Pat Hayes ------------------------------ Date: Tue 15 Mar 88 13:05:24-CST From: Charles Petrie Subject: Reply to Gabriel - VLSI Testibility Checking The MCC CAD program has a knowledge-based testibility checker - contact Thomas@MCC.com The NCR Design Advisor includes testibility checking - contact AI.Steele@MCC.com also see Robin Steele's article in the proceedings of the 24th Design Automation Conference (ACM/IEEE) Both are commercial applications. NCR charges a minimum of $4,000 for users to come in and run their designs through the Design Advisor and interact with it. ------------------------------ Date: 16 Mar 88 14:07:06 est From: Mark Shirley Subject: applications of AI techniques to Testability in VLSI design? Does anyone out there have any references or information on applications of AI techniques to Testability in VLSI design? Thanks in advance, Gabriel. AI and Design for Testability: @InProceedings(shirley87, Key="shirley87", Author="Shirley, M., P. Wu, R. Davis, G. Robinson", Title="A Synergistic Combination of Test Generation and Design for Testability", Organization="The Computer Society of the IEEE", BookTitle="International Testing Conference 1987 Proceedings", Year="1987", Pages="701-711") In the last couple of years, the testing conference has had AI sessions \bibitem{abadir85} Magdy~S. Abadir and Melvin~A. Breuer. \newblock A Knowledge-Based System for Designing Testable VLSI Chips. \newblock {\it IEEE Design \& Test of Computers}, 56--68, August 1985. AI and Test Generation: @InProceedings(Shirley86, key="Shirley86", Author="Shirley, M.", Title="Generating Tests by Exploiting Designed Behavior", Organization=AAAI, BookTitle="Proceedings of the Fifth National Conference on Artificial Intelligence (AAAI-86)", Year=1986, Month=August, Pages="884-890") @InProceedings(Singh86, key="Singh86", Author="Singh, N.", Title="Saturn: An Automatic Test Generation System for Digital Circuits", Organization=AAAI, BookTitle="Proceedings of the Fifth National Conference on Artificial Intelligence (AAAI-86)", Year=1986, Month=August, Pages="778-783") Related DFT and Test Generation work: \bibitem{horstmann} Paul~W. Horstmann. \newblock Design for Testability using Logic Programming. \newblock In {\it Proceedings of 1983 International Test Conference}, pages~706--713, 1983. @PhDThesis(Lai81, Key="Lai", Author="Lai, Kwok-Woon", FullAuthor="Larry Kwok-Woon Lai", Title="Functional Testing of Digital Systems", School=CMU, Number="CMU-CS-148", Month="December", Year="1981") \bibitem{williams73} M.~J.~Y. Williams et al. \newblock Enhancing testability of large-scale integrated circuits via test points and additional logic. \newblock {\it IEEE trans on Computers}, C-22(1):46--60, January 1973. ------------------------------ Date: 18 Mar 88 08:34:47 GMT From: munnari!metro.ucc.su.oz.au!daemon@uunet.UU.NET Subject: Re: Agricultural Uses of AI Siratac is an expert system for the advice of pest management for cotton farmers. it is being developed by the CSIRO Division of Information Technology and Division of Plant Industry in Australia. Several references are available in conference proceedings both computer/ai and cotton related. However, a talk is being presented to the AAAI Workshop Series in the US this year specifically to do with Siratac. If you want any copies contact me at the following adresses ARPA: jansen%ditsyda.oz@seismo.css.gov CSNET: jansen@ditsyda.oz UUCP: {enea,hplabs,mcvax,prlb2,seismo,ubcvision,ukc}!munnari!ditsyda.oz!jansen AUSPAC: jansen@au.csiro.ditsyda ------------------------------ Date: Tue, 15 Mar 88 13:39:55 GMT From: Flash Sheridan Reply-to: flash <@NSS.Cs.Ucl.AC.UK,@cs.qmc.ac.uk:flash@ee.qmc.AC.UK> Subject: Re: Funny Logics and AI: references You might also look at _Non-Standard Logics for Automated Reasoning_, Academic Press, 1988, ed. E.H.Mamdani et al. It's a bunch of polemics and discussions and expositions of lots of different approaches, of varying quality. ------------------------------ Date: 18 Mar 88 21:22:39 GMT From: wucs1!wucs2!posdamer@uunet.uu.net (Jeff Posdamer) Subject: Graduate study in AI offering (Washington University) GRADUATE CERTIFICATE IN ARTIFICIAL INTELLIGENCE Intensive Program Summer Session - May 30-August, 1988 This Graduate Certificate in Artificial Intelligence offers a strong foundation in the theory, techniques and methods of AI. Graduates will have a grounding in knowledge engineering, AI pro- gramming methods and languages, knowledge acquisition and representation, and application development tools and methods. Ideal for engineers, scientists and MIS professionals, this pro- gram will give the students an intensive preparation in the fun- damentals of artificial intelligence and expert systems with em- phasis on the practices required to design and construct applica- tions. The program has over 100 graduates and is currently in its fourth offering. Graduates will earn credit applicable to a graduate degree and will be awarded a graduate certificate upon satisfactory completion. the program emphasises laboratory work. A significant part of the program is the students' projects. Each student should enter the program with a proposed AI project. The individual student performs knowledge acquisition, luation, en- coding and analysis. The staff will select projects to be imple- mented as prototypes by teams of three or four students. Final project reports are presented in seminar and written form. For further information contact: Center for Intelligent Computing Systems Campus Box 1141 Washington University Saint Louis, MO 63130 (314)-889-6766 tonya@syr.wustl.edu -- Jeff Posdamer, Washington University, St. Louis, MO, (314) 889-6147 posdamer@syr.wustl.edu ------------------------------ Date: Wed, 16 Mar 88 18:16:17 PST From: rik%cs@ucsd.edu (Rik Belew) Subject: A four-bit definition of Genetic Algorithms My two-bit definition of "genetic algorithms has, like all over-simplifications, drawn criticisms for being --- you guessed it --- over-simplified! So here's a second pass: First and foremost, I want to "make one thing perfectly clear": When I defined GA(1) in terms of "... John Holland and his students" I most certainly did not intend that only those that had journeyed to Ann Arbor and been annointed by the man himself were fully certified to open GA franchises! Defining a scientific approach in terms of the personalities involved is not adequate, for GA or any other work. I was attempting to distinguish a particular approach from the broader set of techniques that I called GA(2). In my experience, John is the "root" of all such work and much of it has been done by "direct" students of his at Michigan and "indirect" students of these students. I also know, however, that others --- notably Dave Ackley and Larry Rendell --- have worked on these methods without direct contact with this lineage. But I very much consider them "students of Holland," in that they are aware of and have benefited from John's work. (Again, I mean that as a compliment, not because I have been charged with GA Clique membership validation.) I see absolutely no benefit and potentially great harm in drawing lines between closely related bodies of research. So let's move on to more meaningful attempts to define the GA. My two-bit definition focused on the cross-over operator: GA(1) depended on it, and GA(2) generally relyed on the weaker (less intelligent) mutation operator. This lead Dave Ackley to feel that: ... membership in GA(1) is restricted to a small and somewhat quirky "DNA-ish" subset of all possible combination rules [ackley@flash.bellcore.com, 3 Mar 88] I take Dave to mean that the algorithm presented by Holland (let's say the R class of algorithms described in his ANAS Chapter 6, to be specific) sacrifices some performance in order to remain more biologically plausible. But I'm with Dave on this one: Personally, I'm also more intereted in the algorithms than their relation to real biological mechanisms. (Let the record show, however, that there are GA practioners who do try to take biological plausibility more seriously, e.g., Grosso and Westerdale.) So the next possibility is to refer to properties of the GA we find desirable. For Dave, I think the key property of the GA is its "implicit parallelism": the ability to search a huge space implicitly by explicitly manipulating a very small set of structures. Jon Richardson comes closer to the definition I had in mind with his emphasis on Holland's "building blocks" notion: The proper distinction I think is whether or not the recombination operator in question supports the building block hypothesis. "Mutation-like operators" do not do this. Any kind of weird recombination which can be shown to propagate and construct building blocks, I would call a Genetic Algorithm. If the operator does nothing with building blocks, I would consider it apocryphal. It may be valuable but apocryphal nonetheless and shouldn't be called a GA. [richards@UTKCS2.CS.UTK.EDU, 4 Mar 88] While I would echo the value of both these desiderata, I don't find them technically tight enough to be useful. So I suggest that we follow Holland's suggestion (in his talk at ICGA85) and reserve the term "GA" for those algorithms for which we can prove the "schemata theorem" (ANAS, Theorem 6.2.3). I believe this theorem is still the best understanding we have of how the GA gives rise to the properties of implicit parallelism, building blocks, and why. Of course, there are problems with this definition as well. In particular, it is so tightly wed to the string representation and cross-over operator that it is very difficult to imagine any algorithm very different from the (traditional) GA that would satisfy the theorem. But that's exactly where I think the work needs to be done. Finally, I want to say why I (as Dave Ackley says) "took the trouble to exclude" Ackely's SIGH system from my definition of GA(1). My answer is simply that I view SIGH as a hybrid. It has borrowed techniques from a number of areas, the GA, connectionism, simulated annealing to name three. There is absolutely nothing wrong with doing this, and as Dave's thesis showed and Larry Eshelman's note confirmed [Larry.Eshelman- @F.GP.CS.CMU.EDU, 11 Mar 1988] there are at least some problems in which SIGH does much better that the traditional GA. My only problem with SIGH is that I can't do the apportionment of credit problem: when it works, I don't know exactly which technique is responsible, and when it doesn't work I don't know who to blame. I too think about connectionist algorithms and simulated annealing along with Holland's GA and bucket brigade, and see all of them as members of a class of algorithms I want to understand better. But I find it necessary to isolate the properties of each before trying to combine them. In short, I think Dave and I agree to a great extent (on the problem, and on what portions of the solution might be), and disagree only in our respective approaches to putting it all together. ------------------------------ End of AIList Digest ********************