home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3158 < prev    next >
Encoding:
Text File  |  1992-08-12  |  2.5 KB  |  55 lines
  1. Newsgroups: comp.ai.neural-nets
  2. Path: sparky!uunet!gumby!destroyer!ubc-cs!alberta!arms
  3. From: arms@cs.UAlberta.CA (Bill Armstrong)
  4. Subject: Re: Characterizing learnable functions
  5. Message-ID: <arms.713640420@spedden>
  6. Sender: news@cs.UAlberta.CA (News Administrator)
  7. Nntp-Posting-Host: spedden.cs.ualberta.ca
  8. Organization: University of Alberta, Edmonton, Canada
  9. References: <1992Aug10.223138.25927@cco.caltech.edu>     <1992Aug11.111206.25386@cs.tu-berlin.de> <arms.713550511@spedden>     <1992Aug12.112845.1060@cs.tu-berlin.de> <TMB.92Aug12171333@arolla.idiap.ch>
  10. Date: Wed, 12 Aug 1992 17:27:00 GMT
  11. Lines: 42
  12.  
  13. tmb@arolla.idiap.ch (Thomas M. Breuel) writes:
  14.  
  15. >In article <1992Aug12.112845.1060@cs.tu-berlin.de> async@opal.cs.tu-berlin.de (Stefan M. Rueger) writes:
  16.  
  17. >   >Maybe consumers of NNs should ask for and insist on Lipschitz conditions:
  18. >   >   |output(a) - output(b)| <=  const * | a - b |
  19. >   >
  20. >   >for all a, b in the domain of the function. 
  21.  
  22. >   These Lipschitz-functions **are** continuous and thus covered  by the
  23. >   results of Cybernko, described in my original article.
  24.  
  25. >Unfortunately, imposing a Lipschitz condition is not enough. While a
  26. >neural network might be able to approximate any Lipschitz function,
  27. >the number of training examples (the "sample complexity") you need for
  28. >actually finding a "good approximation" is provably too large in many
  29. >cases.
  30.  
  31. Excellent point.  If the training or test data is very sparse, you
  32. would have to have an infinitesimally small Lipschitz constant to
  33. specify what you want on the whole space or to determine that the
  34. result of training is within spec.
  35.  
  36. On the other hand, if you look at the structure of a net and you try
  37. to compute a Lipschitz bound at a given point, you would probably have
  38. to use absolute values of weights, and make pessimistic estimates of
  39. the derivatives of the sigmoids, so you would end up with a uselessly
  40. large bound.
  41.  
  42. I wouldn't give up on the idea of Lipschitz bounds yet, but it looks
  43. bleak.  The only alternative I can see is to assume piecewise
  44. monotonicity of the desired function in the specification, and to
  45. force piecewise monotonicity of the result of training.
  46.  
  47. AN IMPORTANT QUESTION: Can anyone think of any other straightforward
  48. ways to get bounds on values *between* test points?  The application
  49. of NNs in safety-critical areas is at stake.
  50. --
  51. ***************************************************
  52. Prof. William W. Armstrong, Computing Science Dept.
  53. University of Alberta; Edmonton, Alberta, Canada T6G 2H1
  54. arms@cs.ualberta.ca Tel(403)492 2374 FAX 492 1071
  55.