🚀 go-pugleaf

Neil Rickert wrote:
> 
> In <344397B0.66CD@bigfoot.com> "the_walrus@bigfoot.com" <the_walrus@bigfoot.com> writes:
> 
> >Erik Vick wrote:
> 
> >> I am interested in knowing why a neural net must be biologically
> >> plausible?  (Yes I'm a NN newbie)  I thought there were two accepted
> >> methodologies of Neural Nets : 1) the biologic modeling approach and 2)
> >> more of a functional modeling approach.
> 
> >> Is it your position that to gain common sense / learn, the construct
> >> must be a biologically plausible neural net?
> 
> >Learning in ANNs has recently been proven to be NP-Complete (the book is
> >by Judd, and I can't remember the name ... someone helpful might know
> >it), so they ain't viable as they stand.
> 
> I presume you are talking about the 1990 book "Neural Network Design
> and the Complexity of Learning." I haven't yet read the book.  From
> what I see by skimming, I'm not persuaded one needs to take the
> NP-completeness seriously.  Judd appears to define a formal problem,
> which he admits is an approximation of what connectionists take
> neural networks to be doing.  Very little would seem to follow from
> "an approximation of the problem is NP-complete".

Indeed, NP-completeness is another issue that plays a role in a
potential logicist trap.  Someone said that mathematicians will tell us
that NP-complete can't be "gotten around", but allegiance to such a
claim would have prevented people from developing the workable solutions
that *have* been developed for the Traveling Salesman and other
NP-complete and thus supposedly intractable problems.  NP-completeness
is a property that applies to a class of problems as *formally*
described, but none of the problems in the real world are an
exact match to such a formal description.  An algorithm that might
provide a nonoptimal salesman's route 1/n times, where 1/n is, say,
considerably less than the failure rate of the most robust
fault-tolerant computing system in existence, is, from in terms of the
*formal* description, not a solution to the Traveling Salesman problem
at all, any more than a random number generator is.  If we were to take
such an algorithm as a *formal* solution to the problem then we would
have an inconsistency (horrors!) and could prove *anything* (oh my!).
Nonetheless, such a *solution* is completely adequate for any real world
salesman, who does not in fact have to face the precise
absolutely-no-error-allowed problem given by the formal description.

We find the same logicist fallacy with Penrose (not that that is his
only error), who employs Godel in talk about what computers can do,
when no real world computer (or human) has to deal with the
absolutely-no-errors-allowed consistency that is demanded of Godel's
systems and is essential to Godel's Theorem.  And we find it in all this
talk about induction vs. deduction, where induction, not being
*logically valid*, can lead to error (horrors!), and thus we could
prove *anything* by it (oh my!).  But this fear of being able to
prove anything is a bogeyman, since what is relevant to us as real
world creatures is not what *can* happen, a matter for some Platonic
ideal, but is *likely* to happen, how the events distribute themselves,
how many paths through the search thicket lead to the evil erroneous
result.  Of course we could prove anything, and in fact we do all the
time.  All of our best thinkers hold to false and inconsistent beliefs
and manage to prove things that are false.  But it is quite obvious that
that is not the end of the story, that we learn to reduce the likelihood
of reaching wrong results, that we shift the probabilities.  That's
what matters, not getting caught like a deer in the headlights
of *possibility*.

So, for a bottom line, the trick to solving NP-complete problems is to
solve a slightly different class of problem, something like "find the
optimal path for a salesman in a finite but common set of cases and
a nonoptimal path or no path at all in an infinite but uncommon set of
cases".  It turns out that such classes can be found that are not
NP-complete, and in fact that yield low-order polynomial solutions.

Another example is "zero-knowledge proofs".  There is no way for A
to *formally prove* that B knows the answer to some question Q without A
knowing the answer to Q, but there are ways that A can have an assurance
to any degree of likelihood that B knows the answer to Q without A
knowing the answer to Q.  This involves A asking B yes/no questions
that B has only a .5 probability of answering correctly if
B doesn't know the answer to Q, whereas B should always be able to give
the correct answer if she knows the answer to Q.  Each independent
question answered correctly doubles A's assurance that B has the
requisite knowledge.  At any point A might terminate the questioning
when satisfied that B is knowledgeable.  Of course, A could be *wrong*,
no matter how many questions are asked.  The inference about B's
knowledge is *inductive*, not *deductive*.  But the *possibility*
of being wrong isn't what matters in this world, it is the
*probability* that one is wrong.  And so we shouldn't be concerned
merely with what is *valid*, but rather the *degree of justification*
we have for our conclusions.  Validity is merely the asymptotic
limit of degree of justification.

--
<J Q B>
========= WAS CANCELLED BY =======:

Rogue cancel from Michael Enlow, X-Cancelled-by etc. are forged.

Control: cancel <344803DC.7481@sandpiper.com>
Newsgroups: comp.ai
Path: ...!news.rediris.es!news-ge.switch.ch!feed1.news.luth.se!luth.se!feed1.news.erols.com!news-xfer.netaxs.com!news.misty.com!news.uwa.edu.au!munnari.OZ.AU!comp.vuw.ac.nz!canterbury.ac.nz!southpower.co.nz!nobody
From: rra@eyrie.org,sw@eyrie.org,rgm@eyrie.org
Subject: cmsg cancel <344803DC.7481@sandpiper.com>
Approved: rra@eyrie.org,sw@eyrie.org,rgm@eyrie.org
Message-ID: <cancel.344803DC.7481@sandpiper.com>
X-No-Archive: Yes
Sender: Jim Balter <jqb@sandpiper.com>
X-Cancelled-By: rra@eyrie.org,sw@eyrie.org,rgm@eyrie.org
Organization: Southpower Ltd
Date: Sun, 19 Oct 1997 02:22:55 GMT
Lines: 2


The article was canceled on 10/18/97 at 10:13:06 PM with the Usenet Cancel Engine (UCE).