Copy Link
Add to Bookmark
Report
AIList Digest Volume 5 Issue 214
AIList Digest Wednesday, 16 Sep 1987 Volume 5 : Issue 214
Today's Topics:
Neural Networks - Bindings & Generalization,
Theory - P = NP?,
Philosophy - Is Computer Science Science?,
Programming - inSecurity
----------------------------------------------------------------------
Date: Fri, 11 Sep 87 22:20:38 EDT
From: Peter Sandon <sandon%dartmouth.edu@RELAY.CS.NET>
Subject: Re: Neural Networks & Unaligned fields
I did not read the Byte article either. However, assuming that
the network under discussion had no way to represent the similarity
relationship among different nodes that represent translated
versions of the same feature, it is not surprising that it would
have a difficult time generalizing from a given pattern to
an 'unaligned' version of that pattern.
Rumelhart pointed out to Banks that what is needed are many sets
of units having similar weight patterns, that is, weights that
are sensitive to translated versions of a given pattern. In addition,
the relationship between these similar units must be represented.
Rumelhart suggests adding units as needed but does not mention how
to relate these additional units to the trained unit. Fukushima did
something similar in his Neocognitron, by broadcasting a learned
weight set to an entire layer of units which were then all connected
to an OR unit. This OR unit then represented the fact that all the
units represented the same feature, modulo translation. Of course,
broadcasting weights requires more global control than many would
like, and the OR is not quite the relation we want for patterns of
any complexity.
In 1981, Hinton suggested a means of separately representing shape and
translation in a network, such that 'unaligned' patterns could be
recognized. In my thesis, I implemented a modified version of that
network scheme, in order to demonstrate that a network can generalize
object recognition across translation. The network that I implemented
is five layers deep, which proved too much for standard backpropagation
(the generalized delta rule) and for my extensions to the GDR.
However, generalization across translation can be demonstrated in
a subnetwork of this network. I am working on further improvements
to backpropagation that will allow the entire network to be trained.
It is important to recognize that there are many useless
generalizations that might be made, and a few useful ones. The
Hamming distance between two 'T's that are offset from one another
is much greater than that between a 'T' and a 'C' that is offset such
that it overlaps much of the 'T'. What is the 'correct' generalization
to be made when trying to classify these patterns? In order to get
the desired generalization, the network must be biased toward
developing representations in which the Hamming distances (of the
intermediate representations) between within-class patterns is
small compared to that between other patterns. Generalization based
on similarity will then be appropriate. Without such biases, 'good'
generalization would be quite surprising.
--Pete Sandon
------------------------------
Date: 15 Sep 87 21:31:50 GMT
From: jr@io.att.com (j.ratsaby)
Subject: need email addresses
Would you have email addresses of some graduate fellows or
professors that deal with neural-nets in the university of
Toronto and Cambridge (England)?
I would really appreciate it since I'm engaged in research
on stochastic neural-nets,
I recieved some answers from a few of you but unfortunately
there was a fatal shutdown here and I lost the email addresses.
thanks in advance,
joel
------------------------------
Date: 12 Sep 87 06:30:36 GMT
From: ihnp4!alberta!mnetor!genat!maccs!leb@ucbvax.Berkeley.EDU
(Anthony Hurst )
Subject: P may indeed = NP !!
I normally do not keep track of mathematics papers, but I happened
to notice an interesting news item that jumped right out at me. It
was reported in a recent issue of the University of Guelph's "Alumnus"
magazine. (Guelph is in Ontario, Canada).
Included here are three excerpts from the authoress Mary Dickieson.
She writes:
"One of the most perplexing problems in computer science may have
been solved by Professor Ted Swart, who has a joint appointment in
the departments of Mathematics & Statistics and Computing & Infor-
mation Science. He has written a paper offering proof that P = NP.
...
"Dr. Swart cautions that the jury is still out on whether his approach
will be proved or disproved by his peers, but already his pronouncement
has caused a stir in the computer world."
...
"Dr. Swart's problem establishes that the Hamilton circuit problem can
be solved in polynomial time by converting a mathematical programming
formulation of the problem into a linear programming formulation and
using existing polynomial time algorithms as established by Kachiyan
and Karmarkar."
What I should like to know is, has Swart's paper "caused a stir in
the computer world" and if not, why not?
--
seismo!mnetor!{genat,lsuc}!maccs!leb Anthony Hurst
McMaster Dept. of Comp. Sci. & Systems (416)-525-9140 x4030
Will there be cigarettes in heaven?
------------------------------
Date: 14 Sep 87 12:25:56 GMT
From: necntc!linus!faron!bs@eddie.mit.edu (Robert D. Silverman)
Subject: Re: P may indeed = NP !!
In article <761@maccs.UUCP] leb@maccs.UUCP (Anthony (Tony) Hurst) writes:
]
]"One of the most perplexing problems in computer science may have
]been solved by Professor Ted Swart, who has a joint appointment in
]the departments of Mathematics & Statistics and Computing & Infor-
]mation Science. He has written a paper offering proof that P = NP.
]...
No one, repeat no one who does serious research in computational complexity
really belives P=NP. I have seen several such 'proofs'. All are basically
the same: Some imaginative person formulates a problem in NP as a linear
program. Unfortunately, most of these people fail to realize that their
'formulation' requires a number of variables that is exponential in the
size of the problem. Poof goes the proof.
I had already heard of Prof. Swart's purported proof and heard that it
suffers from the same defect.
Bob Silverman
------------------------------
Date: 15 Sep 87 00:23:49 GMT
From: jaw@ames-aurora.arpa (James A. Woods)
Subject: Re: P = NP (review article in The Economist, Sept. 4, 1987)
# "The average mathematician should not forget that
intuition is the final authority." -- J. Barkley Rosser
"There's only one two." -- local TV station slogan
An informative synopsis of P=NP? here is surprising for those
accustomed to the usual style of general-purpose business periodicals.
One would expect something like this to appear in the more outre
New Scientist (hooray for British science writing!), where it might be
by-lined by John Maddox. But the enormity of the question, coupled
with its tight connection to operations research, makes it all
the more important that a general audience is exposed to the art.
The treatment comes complete with mention of revealing Cook/Karp/Levin
history, the role of random oracles, circuit complexity, and the solution
of the old Chomsky grammar chestnut by Neil Immerman. As they say in
the Southern states, "check it out" (of your local public library).
Also entertaining is Steven Johnson's plea for a halt to bogus P=NP
proofs, a cease fire perhaps encouraged by a monetary pot to contain a
$1000 bond for each submission posted before publication, which would then
be forfeited after a bug is found, and thence to the eventual prize
winner, Goedel notwithstanding. It's too bad that a team of "grunt
mathematicians" (*) must still filter the fluff.
Thoughts of anyone other than a Blum or a Karmarkar or a Matyasevich
or an Adelman coming through with a solution may be disturbing to some
workers in the field. Indeed, history has shown repeated lack of faith
with similar assaults [the Bieberbach Conjecture (De Branges), the Poincare
Conjecture (still unresolved), and Fermat's Last Theorem, where episodic
premature announcements in AMS Notices leave no one with even the hope that
a counterexample would fit on a T-shirt.]
As for P=NP, again, refer to the discussion in The Economist for
the week ending 4 September 1987.
-- James A. Woods (ames!jaw)
(*) Term first seen in the seminal paper by DeMillo, Lipton, and Perlis,
CACM, May 1979 -- "Social Processes and Proofs of Theorems and Programs",
well worth your attention for wry commentary and mathematics anecdotes.
------------------------------
Date: 15 Sep 87 06:51:20 GMT
From: maiden@sdcsvax.ucsd.edu (VLSI Layout Project)
Subject: Re: P = NP (review article in The Economist, Sept. 4, 1987)
In article <1035@aurora.UUCP> jaw@aurora.UUCP (James A. Woods) writes:
>Indeed, history has shown repeated lack of faith
>with similar assaults [the Bieberbach Conjecture (De Branges), the Poincare
>Conjecture (still unresolved), and Fermat's Last Theorem, where episodic
^^^^^^^^^^^^^^^^
Only unresolved in three dimensions. Resolved for all
others.
------------------------------
Date: 15 Sep 87 12:11:07 GMT
From: bloom-beacon!gatech!hubcap!steve@think.com ("Steve" Stevenson)
Subject: Re: P = NP subclasses
I once heard a commment that most instances of "NP-complete" problems
encountered in practice do not exhibit the pathological behavior of
the exponential growth function.
Take your favorite characterization of the NP-complete problem.
Questions:
What is the largest subclass of instances (decidable or not) which does
not exhibit the exponetial? What is the largest Turing-decidable
subclass?
--
Steve (really "D. E.") Stevenson steve@hubcap.clemson.edu
Department of Computer Science, (803)656-5880.mabell
Clemson University, Clemson, SC 29634-1906
------------------------------
Date: 10 Sep 87 09:27:00 GMT
From: johnson@p.cs.uiuc.edu
Subject: Re: Is Computer Science Science?
There is a general rule that disciplines with names like XXX Science are
not a science. In spite of that, there are some general laws that arise
out of CS. My favorite are all from computability and complexity theory,
though I do not do that kind of research and don't plan to.
Undecideability -- just because a question has an answer doesn't mean
that there is a method to answer it. E.g. all programs will either
terminate or not terminate, but the halting problem is undecideable.
NP complete problems -- just because a proposed answer is very easy to
check for correctness does not mean that the question is easy to solve.
NP complete problems are those whose answer can be checked in polynomial
time but where any method for finding the solution must essentially
check all possible solutions, taking exponential time. In a similar
manner, a proof can be easily checked for correctness, but it is
undecideable (in any interesting theory) whether there exists a proof
or not for a particular theorem.
------------------------------
Date: 14 Sep 87 12:06:24 GMT
From: uunet!mnetor!yetti!geac!daveb@seismo.css.gov (Brown)
Subject: inSecurity (was Re: Is Computer Science Science?)
In article <8300004@osiris.cso.uiuc.edu> goldfain@osiris.cso.uiuc.edu writes:
>IN SPITE OF RESEARCH, THE FOLLOWING ARE TENETS OF THE CURRENT WORKPLACE:
>"There is no such thing as real computer security."
>"There is always one more bug."
These two tenets are related to each other in an interesting way:
provably secure operating systems exist (so-called "A1" systems), but
the proof merely demonstrates that
a) An externally specified standard is met, and
b) Certain insecure features have a diminishingly small bandwidth.
(a) is related to the buggyness theorem by one level of indirection: there
is no proof in the system that the extra-systemic security policy does not
contain bugs.
--dave (and I can point one out, oh orange-bookers) c-b
--
David Collier-Brown. {mnetor|yetti|utgpu}!geac!daveb
Geac Computers International Inc., | Computer Science loses its
350 Steelcase Road,Markham, Ontario, | memory (if not its mind)
CANADA, L3R 1B3 (416) 475-0525 x3279 | every 6 months.
------------------------------
Date: 14 Sep 87 16:06:37 GMT
From: kodak!elmgate!ram@cs.rochester.edu (Randy Martens)
Subject: Re: Is Computer Science Science?
I am of the firm opinion that there is NO such thing as
computer science. To quote (and I have forgotten the attribution)
"Computer Science bears the same relationship to Real Science, that
plumbing bears to Hydrodynamics."
There is, however, Computer Engineering. (and Software Engineering,
and Systems Engineering etc.). Science is the discovery of the new.
Engineering takes what the scientists have found, and finds ways
to do useful things with it. The two are like Yin and Yang, closely
interrelated, but not the same, and each dependant on the other.
I am a computer engineer.
Randy Martens
"Reality - What a Concept !" - R.Williams
------------------------------
End of AIList Digest
********************
