home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3156 < prev    next >
Encoding:
Internet Message Format  |  1992-08-12  |  1.8 KB
  1. Path: sparky!uunet!olivea!hal.com!decwrl!sdd.hp.com!usc!snorkelwacker.mit.edu!ai-lab!life.ai.mit.edu!tmb
  2. From: tmb@arolla.idiap.ch (Thomas M. Breuel)
  3. Newsgroups: comp.ai.neural-nets
  4. Subject: Re: Characterizing learnable functions
  5. Message-ID: <TMB.92Aug12171333@arolla.idiap.ch>
  6. Date: 12 Aug 92 21:13:33 GMT
  7. References: <1992Aug10.223138.25927@cco.caltech.edu>
  8.     <1992Aug11.111206.25386@cs.tu-berlin.de> <arms.713550511@spedden>
  9.     <1992Aug12.112845.1060@cs.tu-berlin.de>
  10. Sender: news@ai.mit.edu
  11. Reply-To: tmb@idiap.ch
  12. Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
  13.     Perceptive)
  14. Lines: 25
  15. In-reply-to: async@opal.cs.tu-berlin.de's message of 12 Aug 92 11:28:45 GMT
  16.  
  17. In article <1992Aug12.112845.1060@cs.tu-berlin.de> async@opal.cs.tu-berlin.de (Stefan M. Rueger) writes:
  18.  
  19.    >Maybe consumers of NNs should ask for and insist on Lipschitz conditions:
  20.    >   |output(a) - output(b)| <=  const * | a - b |
  21.    >
  22.    >for all a, b in the domain of the function. 
  23.  
  24.    These Lipschitz-functions **are** continuous and thus covered  by the
  25.    results of Cybernko, described in my original article.
  26.  
  27. Unfortunately, imposing a Lipschitz condition is not enough. While a
  28. neural network might be able to approximate any Lipschitz function,
  29. the number of training examples (the "sample complexity") you need for
  30. actually finding a "good approximation" is provably too large in many
  31. cases.
  32.  
  33. Proving that a learning method is capable of representing a result is
  34. only a first step, and not even a decisive one. For example, you may
  35. be able to do most natural language parsing with small, finite state
  36. automata, even though they are theoretically not sufficiently to parse
  37. natural language. Conversely, even if your learning method can
  38. represent some result, you still need to consider questions of sample
  39. complexity and algorithmic efficiency.
  40.  
  41.                     Thomas.
  42.