HDTenEightyP/NetNews huggingface dataset:
From: crawford@church.mitre.org (Randy Crawford)
Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
Organization: The MITRE Corporation, McLean, VA
Date: Thu, 13 Aug 1992 03:38:35 GMT

In article <1992Aug12.173546.3298@access.usask.ca> choy@skorpio.usask.ca (I am a terminator.) writes:
>In article <arms.713549466@spedden>, arms@cs.UAlberta.CA (Bill Armstrong) writes:
>|> The trouble is that all you need to define any function is a
>|> (complete) table of input-output pairs.  If you allow this table as
>|> (part of) the "instruction set", all of computability theory becomes
>|> uninteresting.  So yes, normally algorithms have to be finite.
>
> Why would computability theory become uninteresting?

Because any machine may be made arbitrarily powerful (that is, of less or equal
power to the original machine) by passing it more or less complex input (instr-
uctions).  In evaluating the machine as an interpreter of the instructions,
you are measuring the complexity of the input which the modified machine will
recognize, and not the complexity of the machine itself.  The arguments will
direct the interpreting machine to behave like a different machine.  Therefore 
stack machines may become finite-state machines, and turing machines may become
_any_ kind of machine.

This is not so different from the undecidability problem.  If you pass arguments
into a machine which direct the machine to act like a different machine, not
only can you not decide whether the original machine terminates for all input, 
but the new machine no longer behaves with the same level of complexity or
power that it did before the instructions were introduced.

That begs a question.  Are all universal turing machines of indeterminate 
power?  Or must they be considered turing machines because they _may_ be 
configured as turing machines, even though they also may not be so configured?
If they _are_ still turing machines, then once again, why does computibility 
theory become uninteresting once a turing machine is passed instructions?

(Do I detect a bit of circular reasoning here...)


Randy
crawford@mitre.org
-- 

| Randy Crawford        crawford@mitre.org        The MITRE Corporation
|                                                 7925 Colshire Dr., MS Z421
| N=1 -> P=NP           703 883-7940              McLean, VA  22102
From: robert@cs.strath.ac.uk (Robert B Lambert)
Newsgroups: comp.ai.neural-nets
Subject: Perceptrons
Date: 13 Aug 92 09:09:48 GMT
Organization: Comp. Sci. Dept., Strathclyde Univ., Glasgow, Scotland.

To the NN community in general.

I finally got around to reading "Perceptrons" (by Minsky and Papert - 3rd
edition) and was dismayed at how few of their principal objections have even
been addresses, never mind solved.

I was under the mistaken impression that BP overcame the limitations of the
single layer perceptron. Reading the book, I realized that BP is actually
more limiting and harder to use than its Nth order single layer cousin.

As far as I can see, the objections related to computational complexity such
as scale vs. training time (if it learns at all) have not even been tackled
by the NN community.

Is this right? If you know of work or are involved in research which 
demonstrates the applicability of NNs to "real-world" and not toy problems,
please e-mail me (references would be appreciated).

To what extent to the objections raised in perceptrons carry over to ANNs
other than BP? (In particular self-organizing NNs, recurrent NNs, ALNs). Again,
if you know of or are working on ANNs which you believe are practical to real
world problems (eg. scalable without an exponential rise in training time),
please e-mail me.

I will post a summary of responses as this is a very important issue in NN
research. I believe ANNs only have a future if all the principal objections 
raised in Perceptrons are addressed.

Thanks in advance,

Robert.

------------------------------------------------------------------------------
Robert B Lambert				E-Mail  robert@cs.strath.ac.uk
Dept. Computer Science,
University of Strathclyde,
Glasgow, Scotland.
From: c_tsai@csd.brispoly.ac.uk (C Tsai)
Newsgroups: comp.ai.neural-nets
Subject: Smell in Neural Network
Date: 18 Aug 92 11:57:59 GMT
Organization: Bristol Polytechnic, England

Hello everybody!!!!!

   Who knows 'smell' in Neural Network????  As I know that now only some people
research 'Speech' or 'Image Processing' in Neural Network.  Why nobody research
about 'Smell' in Neural Network!!!!

   I think that If we use neural network to let computer thinking what is good
smell or what is bad smell ( for example: A delicious food should be very good
smell ), so How we can let computer to know and think this smell problem????

   If we can go to out space,like moon or any stars, how we can let computer to
learn "this star can let human to live or not", this must depend on how much 
oxygon or gas is in this star????? 


  I think that Smell in Neural Network is a very interesting project which can
be research.  If someone knows about 'Smell in Neural Network' or where I can
find some articles about this, can you tell me??????? Thinks a lot!!!!!!



Chin-Yu Roman TSAI

My Email address: c_tsai@csd.brispoly.ac.uk
From: dsimon@atlas.nafb.trw.com
Newsgroups: comp.ai.neural-nets
Subject: Hey, Fred Sistler!
Date: 20 Aug 92 14:44:10 PST
Organization: TRW San Bernardino

Fred - I can't email you anything.  My mail messages to you are returned 
to me as undeliverable, although I received an email message from you.
However, I would be glad to mail you a hard-copy of my Neural-Based
Robot Path Planning paper if you give me your address.
----------
Dan Simon

Newsgroups: comp.ai.neural-nets
From: bdbryan@eng.clemson.edu (Ben Bryant)
Subject: Temporal networks
Reply-To: bdbryan@eng.clemson.edu
Organization: College of Engineering, Clemson Univ.
Date: Thu, 13 Aug 1992 12:59:46 GMT

I have recently been doing some work with speech recognition, and have used a
few network configurations in my search for "the perfect network architecture".
I wanted to find out from people in this group what some of the best networks
for sequence recognition are? -A few examples are: TDNN's (Dr. Waibel at CMU),
Spatio-Temporal Nets (-The author's names slip my mind currently), and a
version of Kohonen's SOFMs that use multiple frames per vector (this gives
some temporal invariance). -Are there others that you know about? -If you
would be so kind as to mail the name of the architecture and the inventor
to me - along with a reference or two on that architecture, I will be glad
to post a summary of responses in a few weeks. -Thanks much.

-Benjamin Bryant
<bdbryan@eng.clemson.edu>
From: peyote@umiacs.umd.edu (Gary W. Flake)
Newsgroups: comp.ai.neural-nets
Subject: Various theory references here.
Date: 14 Aug 92 01:05:17 GMT
Organization: UMIACS, University of Maryland, College Park, MD 20742


Some people have asked me for some theory text references.  Enough
have that I thought I'd post a list here.

For a general introduction to the various types of machines in
the computing hierarchy see Minsky, "Computation: Finite and Infinite
Machines."  Note that some material here is dated, but I am very fond
of Minsky's writing style.  Also, there are some interesting chapters
(one on neural networks) that have material you wont find in any other
single book.

More current general introductions can be found in Hopcroft and
Ullman, "Introduction to Automata Theory, Languages and Computation,"
and Lewis and Papadimitrou's, "Elements of the Theory of Computation."

For recursion theory (advance introduction) the classic (if somewhat
dense) in this field is Davis, "Computability and Unsolvability."  You
can find this in a Dover edition for probably less than ten bucks -- a
steal!

For NP-Completeness, the most important book is Garey and Johnson's
"Computers and Intractability."  This is a recipe book of known
NP-Complete problems, and it also provides clues to some unsolved
problems.

All of the above books touch on complexity.  I prefer the treatment
that algorithm texts give the subject.  In this category I like
Cormen, Leiserson and Rivest's "Introduction to Algorithms."  This
book is huge, filled with a great collection of algorithms, and
contains a very good introduction to amortized analysis.

Regards,
Gary
-- 
Spoken: Gary W. Flake  Domain: peyote@umiacs.umd.edu  UUCP: uunet!mimsy!peyote
Phone: +1-301-405-6757 USPS: UMIACS, U. of Maryland,  College Park, MD 20742
From: tedwards@src.umd.edu (Thomas Grant Edwards)
Newsgroups: comp.ai.neural-nets
Subject: Re: Smell in Neural Network
Date: 20 Aug 92 17:52:40 GMT
Organization: Systems Research Center, Maryversity of Uniland, College Park

In article <1992Aug18.115759.21078@csd.brispoly.ac.uk> c_tsai@csd.brispoly.ac.uk (C Tsai) writes:
>   Who knows 'smell' in Neural Network????  As I know that now only some people
>research 'Speech' or 'Image Processing' in Neural Network.  Why nobody research
>about 'Smell' in Neural Network!!!!

Studies of olfactory systems have already shed light on oscillatory 
systems in brain.  Here are some references:

Freeman, W.J. (1987)  Simulation of chaotic EEG patterns with a 
 dynamic model of the olfactory system.  _Biological Cybernetics_, v. 56,
 139-150.

Freeman, W.J. (1988)  Central pattern generating and recognizing in
 olfactory bulb:  A correlation learning rule.  _Neural Networks_, v. 1,
 277-278.

-Thomas Edwards
Newsgroups: comp.ai.neural-nets
From: al@jargon.gmd.de (Alexander Linden)
Subject: Re: Network Inversion
Organization: GMD, Sankt Augustin, Germany
Date: Sat, 22 Aug 1992 15:15:45 GMT

sef@sef-pmax.slisp.cs.cmu.edu writes:

>Most backprop-type networks are information-losing systems: many distinct
>inputs give rise to the same output.  You can't invert this kind of net
>into another feed-forward net (of the usual kind) because you just end up
>with a mushy average of the possible inputs for a given output.

>-- Scott

We should not talk about inversion in this case rather it is a kind
of search for (may be) spurious minima in input space.

They give no mushy averages but you can produce class boundaries.

Assume a net which is allready trained on classifying digits:

You can start with input I(0), lets say the bitmap of a three.
The output of the net tells you thats a "3". Now you start to 
change I(0) with dE/dI and E = (T-O)**2 and T says the output should
be a "9", for example. Now you see a sequence of I(1), I(2), ...
which are gradually becoming more like a "9" than a "3", if your
classifier is not sufficiently good, some distortions of a three 
are enough to give "9" at output. 
See Linden and Kindermann (1989) Int. Join Conf on NN, Washington D.C
for illustrative examples. 

Alexander

Alexander Linden             | TEL. (49 or 0) 2241/14-2435, FAX. -2618 or -2889
GMD - AI Research Division   | TELEX 889469 gmd d
P. O. BOX 1316               | email:  A.Linden@gmd.de
D-5205 Sankt Augustin 1, FRG
--
Alexander Linden             | TEL. (49 or 0) 2241/14-2435, FAX. -2618 or -2889
GMD - AI Research Division   | TELEX 889469 gmd d
P. O. BOX 1316               | email:  A.Linden@gmd.de
D-5205 Sankt Augustin 1, FRG
Xref: sparky comp.ai.neural-nets:3186 comp.ai:3087 comp.compression:3008 comp.theory:1759
From: dhd@exnet.co.uk (Damon)
Newsgroups: comp.ai.neural-nets,comp.ai,comp.compression,comp.theory
Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
Date: 13 Aug 92 18:56:49 GMT
Organization: ExNet Systems Ltd Public Access News, London, UK

In article <1992Aug12.150857.219@access.digex.com> dzik@access.digex.com (Joseph Dzikiewicz) writes:
>In article <1992Aug10.115352.1@acad3.alaska.edu> fxsdb@acad3.alaska.edu (Scott D. Berry) writes:
>>an
>>assembly language program, for example, may have an infinite number of states.
>
>Actually, unless you have an assembly language that allows addressing
>infinite memory, even an assembly language program has a finite
>number of states (a large number, admittedly, but still finite).
>
>This lack of infinite memory is why digital computers are of equal 
>computing power to a finite state machine and considerably less powerful
>than a Turing machine.  Admittedly, a computer with megabytes of memory
        ^^^^^^^^^^^^^^
		with an infinite tape (else the computer and the finite TM are equiv).

>is a finite state machine with a lot of states, but it's still not
>Turing-equivalent.

Damon
-- 
Damon Hart-Davis | Tel/Fax: +44 81 755 0077 |1.22|| ALL MAIL FREE.
Internet: dhd@exnet.co.uk | Also: Damon@ed.ac.uk || US hotrod motor groups.
--------------------------+----------------------++ >12 mail&news polls / day.
Public access UNIX (Suns), news and mail for #5 per month.  FIRST MONTH FREE.
Newsgroups: comp.ai.neural-nets,comp.ai,comp.compression,comp.theory
From: sethb@fid.morgan.com (Seth Breidbart)
Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
Organization: Morgan Stanley & Co., New York, NY
Date: Fri, 14 Aug 1992 17:04:29 GMT

In article <1992Aug12.173546.3298@access.usask.ca>
choy@skorpio.usask.ca (I am a terminator.) writes:
>In article <arms.713549466@spedden>, arms@cs.UAlberta.CA (Bill Armstrong) writes:
>|> mather@sees.bangor.ac.uk (Paul Mather) writes:

>|> The trouble is that all you need to define any function is a
>|> (complete) table of input-output pairs.  If you allow this table as
>|> (part of) the "instruction set", all of computability theory becomes
>|> uninteresting.  So yes, normally algorithms have to be finite.
>
>Why would computability theory become uninteresting?

A function is (can be viewed as) the set of input-output pairs.  If
you allow all such sets as part of the instruction set of a machine,
then all functions are computable.  If all functions are computable,
then the theory about which functions are not computable becomes
rather small.

Seth		sethb@fid.morgan.com
From: platt@synaptx.Synaptics.Com (John Platt)
Newsgroups: comp.ai.neural-nets
Subject: Interpolation and neural networks
Keywords: interpolation partition-of-unity
Date: 13 Aug 92 21:58:22 GMT
Reply-To: platt@synaptics.com (John Platt)
Organization: Synaptics Inc., San Jose, CA

In an article arms@cs.UAlberta.CA (Bill Armstrong) writes:
>AN IMPORTANT QUESTION: Can anyone think of any other straightforward
>ways to get bounds on values *between* test points?  The application
>of NNs in safety-critical areas is at stake.

  Yes.. It's quite straightforward and has already been suggested by
Moody & Darken and separately by Kurt Stockbro for neural networks.
It's a trick from approximation theory called "partition of unity" or
sometimes a "generalized Shepard's method".

  Normally, when you have a radial basis function network, the network
output is a linear superposition of radial basis functions:

       O_i = sum_j w_ij f_j(input) 

  Moody & Darken suggest averaging the outputs, not summing them:

             sum_j w_ij f_j(input)
       O_i = ---------------------
               sum_j f_j(input)

That way, the output is always in the convex hull of the w_ij for any
basis function f_j that is non-zero. If the f_j have local support, then
you can bound the output vector in a region quite easily.

  Notice that the meaning of the w_ij has changed using a partition of
unity. In the superposition case, the w_ij are small vectors that accumulate
towards the correct answer. In the averaging case, the w_ij are stored
memories of the O_i and the f_j control how strongly that memory is
recalled.

  Personally, I have found that averaging makes smoother functions than
superposition.

  References:

   Moody, J., Darken, C., "Fast Learning in Networks of Locally-Tuned
Processing Units," Neural Computation, vol 1, no. 2, pp. 281-294. 
(The relevant equation is on page 283), (1989).

   Stockbro, K., "Predicting Chaos with Weighted Maps", M. S. Thesis
Niels Bohr Institute, (1991)

  Other References back to Approximation Theory:

   Franke, R., "Scattered Data Interpolation: Test of Some Methods,"
Mathematics of Computation, vol. 38, no. 157, pp. 181-200, (1982).

   Shepard, D., "A Two-Dimensional Interpolation Function for Irregularly
Spaced Data," Proc. 23rd Nat. Conf. ACM, pp. 517-523, (1968).
From: henrik@mpci.llnl.gov (Henrik Klagges)
Newsgroups: comp.ai.neural-nets
Subject: Re: Reducing Training time vs Generalisation
Date: 20 Aug 92 20:02:52 GMT

arms@cs.UAlberta.CA (Bill Armstrong) writes:

>>Sure, but they will have no incentive to do this unless the data, in some
>>sense, forces them to.  You could always throw a narrow Gaussian unit into
>>the net, slide it over between any two training points, and give it an
>>output weight of 10^99.  But it would be wrong.

>A good reason not to use such units, eh!
Hm, Bill - this reasonability applies to your example problem as well, which
is pretty much constructed ad hoc. Just add a training point between your 
center - or remove the symmetry otherwise, and your extremum is gone (!).

>I seem to recall going over this before, and I believe what is
>required to upset the scheme is to have a lot of training points which
>force training to fit a solution having a peak.  I.e. if six points

If there are many points suggesting a peak, than the peak is right. Ever 
did a coupled pendulum experiment and plotted phase lag versus resonance ?
Perfect peaks. Few points, though, to generate/plot them !

Concerning lazy evaluation: It is difficult to program on parallel machines.
It is a kind of runtime loadunbalancing that constantly switches off tasks
(=subtree evaluations) of varying size essentially at random. No way to do
that in SIMD, and darn difficult to do it in MIMD at all, and especially not
with a high efficiency.


Cheers, Henrik
IBM Research Division physics group Munich
massively parallel group at Lawrence Livermore

Newsgroups: comp.ai.neural-nets,comp.ai,comp.compression,comp.theory
From: koops@asterix.gaul.csd.uwo.ca (Luke Koops)
Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
Reply-To: koops@asterix.gaul.csd.uwo.ca (Luke Koops)
Organization: University of Western Ontario
Date: Fri, 14 Aug 1992 21:20:05 GMT

In article <1992Aug10.115352.1@acad3.alaska.edu>, fxsdb@acad3.alaska.edu (Scott D. Berry) writes:
|> In article <1992Aug10.163725.26986@julian.uwo.ca>, koops@obelix.gaul.csd.uwo.ca (Luke Koops) writes:
|> > In article <arms.713457373@spedden>, arms@cs.UAlberta.CA (Bill Armstrong) writes:
|> >> koops@asterix.gaul.csd.uwo.ca (Luke Koops) writes:
|> > .
|> > .
|> >> >Why is the smallest turing machine considered the measure of
|> >> >complexity, and not the smallest boolean expression, or the smallest
|> >> >decision tree, or the smallest neural network description, or the
|> >> >shortest program in 6502 Assembly language?
|> > .
|> > .
|> >> I think the answer to your question [...] is that other models that you 
|> >> could use, like a random access machine, will *only* differ in their results 
|> >> by a constant factor.
|> >
|> > I suspect that, even though the models _only_ differ by a constant
|> > factor, in some cases that factor could be very  large
|> The reason you ignore even a very large constant factor is that complexity, on
|> the theoretical level, takes very large sets into consideration.  As the data
|> set gets infinitely large, the constants matter less (10000000000n is worse
|> that n^2, for large n).
|> 
|> The reason the other methods don't give an "unbiased estimate of the
|> complexity" is that a Turing machine is a finite-state machine, while an
|> assembly language program, for example, may have an infinite number of states.
|> A program that adds one to a number and jumps backwards will certainly be
|> small, but has "infinite complexity", and does not describe an algorithm, as it
|> doesn't terminate.
|>    -Scott (fxsdb@acad3.alaska.edu)

	I have learned a bit more about kolmogorov complexity since I brought
up the topic.  K-complexity usually applies to finite strings.  This is because inifinite
strings usually have inifinite complexity (i.e. are uncomputable and would require
an infinitely long Turing machine to generate them).  In the set of all infinite strings,
only a infinitesimally small subset of them have a finite complexity (i.e. periodic
strings, binary representation of pi).  Periodic strings can obviously be enumerated
by finite strings (the string that is being repeated).  Transcendental numbers which
can be generated by finite length turing machines are a different story, but, by
definition, they have a finite k-complexity.

	Also, I beleive that K-complexity is not unbiased, but is biased towards
Turing machine representations of concepts.  It just provides a really good estimate
of complexity.  This is merely my opinion, I would appreciate it if someone could
confirm it.
-- 
 Some newsreaders use proportional fonts!  

   ||||<>////\\
- <>
\------

which could make your signature looks like this ^^^^^     koops@csd.uwo.ca
From: henrik@mpci.llnl.gov (Henrik Klagges)
Newsgroups: comp.ai.neural-nets
Subject: Re: Reducing Training time vs Generalisation
Date: 20 Aug 92 19:52:27 GMT

sef@sef-pmax.slisp.cs.cmu.edu writes:
>For example, in the example about the big
>gaussian spike, it would drive the output weight to zero if the Gaussian is
>not helping to fit the data.

Key point. A few add-on 'reasonability criterions' like weight decay are
quite effective in avoiding pathological results.

>Well, since you keep pounding on this, I will point out that in most
>backprop-style nets after training, almost all of the hidden units are
>saturated almost all of the time.  So you can replace them with sharp

Same in our experiments. The decision trees being built do benefit a lot 
from the remaining nonlinearities, though (smoother decision surfaces-
really 8-).

>Myself, I prefer to think in terms of parallel hardware, so lazy evaluation
>isn't an issue.  Yes, sigmoid unit hardware is a bit more expensive to
>implement than simple gates, but I don't need nearly as many of them.

It is not terribly expensive - a 256 entry table is usually enough. Pipe
lined access to such a lookup table can be made at one lookup/cycle at a 
pipe stall of less than 5 (if not much better, hihi). Moreover, weight
accumulation/update are matrix operations, while lookup is only a vector
operation. It is no bottleneck at all.

Cheers, 
	Henrik


BM Research Division physics group Munich
massively parallel group at Lawrence Livermore
From: gary@concave.cs.wits.ac.za (Steven Ruskin c/o Gary Taylor)
Newsgroups: comp.ai.neural-nets
Subject: Hopfield Neural Networks
Date: 21 Aug 92 06:46:01 GMT
Article-I.D.: shannon.1992Aug21.064601.20900
Organization: Wits Univ. Computer Science Dept.


I am currently performing experimentation using a Hopfield neural network to colour graphs and solve constraint based problems. I would appreciate any information / references that anyone may have. I would also be grateful if someone could send me a coded implementation of a hopfield network (C preferably). 
 
I will post a summary of the info I receive.

Please send email to me at gary@concave.cs.wits.ac.za

Many thanks 
Steven Ruskin
From: jfbuss@math.uwaterloo.ca (Jonathan Buss)
Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
Organization: University of Waterloo
Date: Thu, 13 Aug 1992 15:15:58 GMT

In article <1992Aug12.150857.219@access.digex.com> dzik@access.digex.com (Joseph Dzikiewicz) writes:

>This lack of infinite memory is why digital computers are of equal 
>computing power to a finite state machine and considerably less powerful
>than a Turing machine.  Admittedly, a computer with megabytes of memory
>is a finite state machine with a lot of states, but it's still not
>Turing-equivalent.
>

This observation begs the question, why are digital computers modelled
as infinite-state machines?  Can one obtain more realistic results by
using finite-state machines as the model?

To particularize, do results like the following have finite-state
analogues?

   (1) Mergesort has time complexity O(n log n).

   (2) The Satisfiability problem is NP-complete.

These seem to be useful results, but their statement implicitly uses
an infinite-state model.


Jonathan Buss
Newsgroups: comp.ai.neural-nets