Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!sdd.hp.com!ucsd!ucbvax!hplabs!hpcc01!hpwrce!kingsley
From: kingsley@hpwrce.HP.COM (Kingsley Morse)
Newsgroups: comp.ai.neural-nets
Subject: Really smart systems
Message-ID: <3430007@hpwrce.HP.COM>
Date: 14 Aug 90 21:05:25 GMT
Organization: Ye Olde Salt Mines
Lines: 33

If we aspire to making truly intelligent machines, our algorithms must scale
up well to large training sets. In other words, the computational complexity
of our algorithms must accomodate many training patterns and many dimensions.
You may have heard of the "curse of dimensionality". If the computational
complexity of our algorithms grows slowly, then we can train with more patterns
and dimensions to get a smarter system. On the other hand, if the computation
required grows explosively as the number of training patterns or dimensions are
increased, then even astoundingly fast hardware won't help.

So, our challange is to find algorithms which scale up well to large problems,
so we can make really smart systems. Listen........... I'll post some
computational complexity figures for some common algorithms. If you add to
(correct?) these, please do. The terminology that I propose is that 
linear computational complexity is better than polynomial which is
better than exponential. Furthermore, the algorithms' scalability must be
measured with respect to learning, recall, patterns, and dimensions.


Algorithm          Learning                   Recall
             patterns  dimensions      patterns     dimensions
------------------------------------------------------------
Backprop    polynomial     ?           independent  linear

Nearest
   neighbor linear      linear         linear       linear

Cart        nlogn       exponential    independent      ?


This leads me to believe that nearest neighbor algorithms work better
for learning a lot because they can be trained faster.

Any contributions to this list are welcome.