Copy Link
Add to Bookmark
Report
AIList Digest Volume 4 Issue 153
AIList Digest Wednesday, 18 Jun 1986 Volume 4 : Issue 153
Today's Topics:
Literature - AI and Organic Chemistry,
AI Tools - Common Lisp on Silicon Graphics,
Expert Systems - Conditional Independence References,
Algorithms - Traveling Salesman Problem,
Review - Spang Robinson Report Volume 2 No 6,
Philosophy - Creativity and Analogy
----------------------------------------------------------------------
Date: Mon 16 Jun 86 13:24:13-PDT
From: Matt Heffron <BEC.HEFFRON@USC-ECL.ARPA>
Subject: Re: AI & Organic Chemistry
A brand-new book from the American Chemical Society is:
Artificial Intelligence Applications in Chemistry,
Edited by: Thomas H. Pierce and Bruce A. Hohne
ACS Symposium Series #306, published by ACS. 1986
28 chapters in 5 sections: Expert Systems, Computer Algebra, Handling Molecular
Structures, Organic Synthesis, and Analytic Chemistry.
Each chapter is a paper given at an ACS Symposium last September.
-Matt Heffron
BEC.HEFFRON@USC-ECL.ARPA
------------------------------
Date: Sun, 15 Jun 86 13:26:31 PDT
From: Harry Weeks <franz!harry@kim.Berkeley.EDU>
Subject: Common Lisp implementations.
This note is in reply to a recent inquiry on this list for Common Lisp
implementations on Silicon Graphics systems.
Franz Inc. now supports our Extended Common Lisp, as well as Franz Lisp,
on Silicon Graphics workstations. Both products incorporate an inter-
face to the Iris graphic libraries. Extended Common Lisp is a complete
and robust implementation of the Common Lisp language as specified in
Guy Steele's book `Common Lisp: The Language.' We have added extensions
that include a Symbolics-compatible Flavors system, a foreign-function
interface, and extensive debugging tools. Franz Inc. also supports
Extended Common Lisp on workstations available from ATT, ISI, Masscomp,
Sun, and Tektronix. Inquiries are welcome and may be directed to our
offices at 1141 Harbor Bay Parkway, Alameda, California 94501, (415)
769-5656, ...!ucbvax!franz!info.
Harry Weeks
Franz Incorporated
------------------------------
Date: 12 Jun 86 19:38:00 GMT
From: pur-ee!uiucdcs!uicsl!bharat@ucbvax.berkeley.edu
Subject: Re: Conditional independence in possibility theory
I do not have the references you asked for. However if you are interested
these are some other references I found useful relating to conditional
independance and probabilities in EXPERT SYSTEMS.
1. Quinlan J.R.
Inferno : a cautious approach to uncertain inference.
The Computer journal, 26: 3, 255-269, 1983.
2. Allan P. White
Predictor : An alternative approach to uncertain inference in
Expert Systems.
Proc - IJCAI 1985, Vol.1, 328-330, 1985.
If you need them, please contact me at
bharat@a.cs.uiuc.arpa, or write a note to net.ai
Good luck
R.Bharat Rao
------------------------------
Date: Sat, 14 Jun 86 15:22:01 pdt
From: John B. Nagle <jbn@su-glacier.arpa>
Subject: Known solution to traveling salesman problem
There is a well-known and fast method for finding near-optimum
solutions to the traveling salesman problem. It was discovered at
Bell Labs in the 1960s, and it is as follows:
1. Connect up all N points in some arbitrary order,
resulting in a path with N-1 edges and two endpoints.
2. Pick two edges at random. Cut the path at these points.
This produces three paths, each with two endpoints.
3. There are six possible ways to connect the paths into
a single path. Try all six, and compute the total
distance for each arrangement. Keep the arrangement
with the shortest total length.
4. Iterate steps 2 and 3 until no improvement is observed
for a reasonable number of iterations, at least N
but less than N*N.
I strongly suspect that the neural nets people have just rediscovered
this classic algorithm, especially since the Business Week article
mentions that the neural net approach produces near-optimal, not
optimal, paths. Comparisons with the brute-force solution are
misleading.
John Nagle
[While the Hopfield-net solution may well be based on similar
mathematics, the flavor is quite different. It is more of a
parallel "relaxation" process or fuzzy linking, with each node
trying to link to neighbors in proportion to their nearness.
Hopfield describes this as an analog process that cuts through
the space of possibilities instead of moving around the outside
as the iterative solutions do. The net quickly approaches a
stable configuration of intersecting cliques (if that's not a
contradiction) separated by longer paths, then the cliques fight
it out to determine the final route. (The establishment of one
clique disrupts others, so a slow gradient search for the optimum
is necessary.) The lack of guaranteed optimality is primarily due
to the initial rapid convergence -- it is possible to construct
problems for which the true optimum is quite far from any broad
"potential well" that would attract the system. Some algorithms
use randomized "stochastic anealing" to get around this, others
start the process many times from very different initial conditions,
others just ignore the problem.
For an interesting study of one such problem, see the Spring 1985 issue
of Abacus. It presents a lengthy analysis of Lee Sallows' custom-built
hardware for solving pangram puzzles by full search, then a short article
by John Letaw showing how the same puzzles can (usually!) be solved by
approximation/optimization on a microcomputer running BASIC. -- KIL]
------------------------------
Date: WED, 20 apr 86 17:02:23 CDT
From: E1AR0002%SMUVM1.BITNET@WISCVM.WISC.EDU
Subject: Spang Robinson Report, Volume 2 No 6
Summary of Spang Robinson Report, Volume 2 NO. 6
June 1986
Emphasis on AI and Parallel Processing:
There are 28 companies marketing parallel hardware with 900 machines installed
for total revenues from 1985- mid 1986 of 160 million dollars.
Alliant Computer Systems is working with Stanford and Lucid, Inc. in a
DARPA funded project to develop a public domain LISP for parallel applications
called QLISP.
Control Data is working with the University of Georgia to develop a parallel
Prolog and after that a parallel Lisp.
Flexible Computer claims that 30 to 40 percent of its customers are interested
in AI.
Concurrent Lisp from Golden Common Lisp has been benchmarked on the Gabriel
Triangle Benchmark at 86 percent of the speed of a Xerox 1108 Dandelion
using one node of the IPSC hypercube. On a sixteen node hypercube, it
runs at 9.1 times the speed. INTEL says that 25% of 1000 queries were
oriented to AI.
LISP Machine announced that it intends to have its Object LISP running
on the INTEL hypercube by the end of May.
Sequent Computer says that 10 to 15 percent of its customers based
their decision buying decision on the availability of LISP, 50% were
interested in AI.
__________________________________________________________________________
Japan Watch:
Arthur D. Little's Japan affiliate reported the results of a survey
of twenty Japanese companies. The US has over a five year lead in Japan
in AI but the gap will narrow with time. They predict the catchup will
be completed by 1992. There is a twelve to one differential in the US favor
in funds invested in AI up to 1985.
The Japanese AI market in 1985 was 80 million while the American
market was $412 million.
Kansai Electric Power has been developing a diagnostic expert system for use
with nuclear reactors with the prototype finished by March 1986. Kyushi
Electric Power Company is field testing an expert system system for diagnosis
and repair of electric power systems. Tokyo Electric Power Co., Inc.,
Hitachi Ltd and Mitsubishi Electric Corporation are working on expert systems
for supply and demand for power and for planning system operations.
Nippon Telephone and Telegraph will officially announce KBMS, an expert
systems tool. NTT is negotiating with other companies for collaboration
in the development of AI software.
__________________________________________________________________________
AI at IBM:
Dr. Herbert Schorr, Group Director for Products and Technology at IBM,
stated that IBM does not plan to release a dedicated LISP machine or AI
workstation. It considers its RT machine to be the IBM AI workstation.
He claims that benchmarking at Carnegie Mellon has done benchmarking of
this machine which shows it fares favorably with other AI languages
and hardware.
Most of IBM's efforts in developing expert systems are for internal
applications and it does not see the need to compete with those already
providing such products. There are 70 expert systems under development
at IBM with 24 more to be added.
------------------------------
Date: Fri, 13 Jun 86 13:44:40 bst
From: Gordon C Joly <gcj%qmc-ori.uucp@Cs.Ucl.AC.UK>
Subject: Re: Creativity and Analogy -- More Questions than Answers.
Uttam Mukhopadhyay asks, in AIList Vol 4 #148 :-
>Is there more to creativity than making interesting analogies? I am
>inclined to believe that making interesting analogies is at the heart
>of all intelligent activity that is described as creative.
Hmmm... A friend described another friend as a potentially good novelist,
because ``she always has a radically different view in the situation;
she always has a new angle''. But is there analogy tucked away in her
reasoning? And would we be able to elicit that knowledge from the
`expert'?
Finally, *is* creativity always intelligent, and in what sense of the
word -- AI, machine intelligence or human intelligence? As for analogy,
we always need hooks to hang ideas on, don't we?
Gordon Joly
INET: gcj%maths.qmc.ac.uk%cs.qmc.ac.uk@cs.ucl.ac.uk
EARN: gcj%MATHS.QMC.AC.UK%CS.QMC.AC.UK@AC.UK
UUCP: ...!seismo!ukc!qmc-ori!gcj
------------------------------
Date: Fri, 13 Jun 86 14:32:36 bst
From: Gordon C Joly <gcj%qmc-ori.uucp@Cs.Ucl.AC.UK>
Subject: Re: Creativity and Analogy -- Coda.
``To the extent that a professor of music at a conservatoire
can assist his students in becoming familiar with the patterns
of harmony and rhythm, and with how they combine, it must be
possible to assist students in becoming sensitive to patterns
of reasoning and how they combine. The analogy is not far-
fetched at all. -- Dijkstra.''
>From -- `Knowledge-Based Systems in Artificial Intelligence'
by Randall Davis and Douglas B. Lenat, McGraw-Hill, 1982, page 163.
Gordon Joly
INET: gcj%maths.qmc.ac.uk%cs.qmc.ac.uk@cs.ucl.ac.uk
EARN: gcj%MATHS.QMC.AC.UK%CS.QMC.AC.UK@AC.UK
UUCP: ...!seismo!ukc!qmc-ori!gcj
------------------------------
Date: Mon, 16 Jun 86 10:41:48 edt
From: Jay Weber <jay@rochester.arpa>
Reply-to: jay@rochester.UUCP (Jay Weber)
Subject: Re: Creativity and Analogy
> At a recent talk in Ann Arbor, Roger Schank observed/implied that
>a distinct characteristic of many creative people is the ability to
>analogize. My understanding of analogizing is to define transformations
>between two domains so that entities and relationships in one domain
>can be mapped into corresponding entities and relationships in the
>other domain. It appears that the greater the disparity in the "physics"
>of the two domains, the higher is the creative effort demanded.
> Not all transformations produce interesting results. Good analogies
>must be interesting from the perspective of the particular creative
>activity.
True. Every pair of "things" is analogous in *some* sense, i.e. there
exists a mapping between them. The utility of an analogy is how it
leads one to use those things more successfully.
> Is this model of creativity--making interesting analogies--valid
>across the spectrum of creative actvities, from the hard sciences
>(Physics, Chemistry, etc.) to the fine arts (painting, music)?
>Is there more to creativity than making interesting analogies? I am
>inclined to believe that making interesting analogies is at the heart
>of all intelligent activity that is described as creative.
I believe that one could give a reasonable definition of analogy that
encompasses all intelligent activity, or at least inductive learning
(which is a biggie as far as intelligence goes). I question, however,
how useful it is in AI to relate a slippery word like "analogy" to an
even slipperier word like "creativity". A formal approach with those
two terms will satisfy very few people, and an informal approach will
only give us an inflated opinion of the value of our own research,
which is largely why people make such comparisons.
Jay Weber
Department of Computer Science
University of Rochester
jay@rochester.arpa
------------------------------
Date: Mon, 16 Jun 86 16:56:06 EDT
From: "Col. G. L. Sicherman" <colonel%buffalo.csnet@CSNET-RELAY.ARPA>
Subject: Re: Creativity and Analogy
This is a brief reply to U. Mukhopadhyay's article.
> [...]
> Is this model of creativity--making interesting analogies--valid
> across the spectrum of creative actvities, from the hard sciences
> (Physics, Chemistry, etc.) to the fine arts (painting, music)?
> Is there more to creativity than making interesting analogies? I am
> inclined to believe that making interesting analogies is at the heart
> of all intelligent activity that is described as creative.
"Creativity" is often idealized as the missing ingredient in computer
consciousness, but what exactly does it mean? In most of the examples
drawn from science, it means advantageously overriding the usual
categories and compartments, since categorizing and compartmentalizing
knowledge are characteristically scientific habits. Of course, making
analogies is one way to achieve this.
In art, creativity is much more straightforward! One creates a work
of art where there was none before. The essence of this kind of
creativity is to be able to perceive what _is not._ This follows
in an essential way from the ability to perceive what one is taking
for granted, in order to stop taking it for granted.
A good reference is F. Perls et al., _Gestalt Therapy._
------------------------------
Date: Tue 17 Jun 86 12:33:35-PDT
From: Ken Laws <Laws@SRI-AI.ARPA>
Subject: Artistic Creativity
From Col. Sicherman:
"In art, creativity is much more straightforward! One creates a
work of art where there was none before."
While there is truth to this, I disagree with the implication that
art, or certainly that >>all<< art, is pure creation. Most examples
that I have seen are transformations. The artist sees a scene,
technique, or concept that intrigues him, and searches for a way
to capture the same thing in a new medium. This is analogy in a
pure form, not the opposite of analogy.
-- Ken Laws
------------------------------
End of AIList Digest
********************
