home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / ai / neuraln / 3434 < prev    next >
Encoding:
Internet Message Format  |  1992-09-09  |  4.1 KB
  1. Path: sparky!uunet!usc!rpi!usenet.coe.montana.edu!news.u.washington.edu!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!news
  2. From: sef@sef1.slisp.cs.cmu.edu
  3. Newsgroups: comp.ai.neural-nets
  4. Subject: Re: Summary of CUPS + new question
  5. Message-ID: <BuCFut.F6t.1@cs.cmu.edu>
  6. Date: 10 Sep 92 03:47:14 GMT
  7. Article-I.D.: cs.BuCFut.F6t.1
  8. Sender: news@cs.cmu.edu (Usenet News System)
  9. Organization: School of Computer Science, Carnegie Mellon
  10. Lines: 71
  11. Nntp-Posting-Host: sef1.slisp.cs.cmu.edu
  12.  
  13.  
  14.     From: jjb@sequent.com (Jeff Berkowitz)
  15.     
  16.     Some weeks back I posted a request for real examples of the performance
  17.     of back propogation simulators in "backprops/second."  Bill Armstrong
  18.     at the University of Alberta, Canada pointed out in a posting that the
  19.     accepted unit of measurement was CUPS...
  20.  
  21. Actually, it's a bit more complicated than this.  The cleanest form of the
  22. backprop algorithm (called "batch" or "per-epoch" updating) does
  23. forward/backprop cycles through the whole training set, accumulating dE/dw
  24. for each weight.  Then all the weights are updated at once.  This gives you
  25. the "true" error gradient, but can be slow if the training set is large and
  26. redundant.
  27.  
  28. An alternative form (unfortunately, the famous Rumelhart-Hinton-Williams
  29. paper tends to muddle these two forms together) is called "stochastic",
  30. "online", or "per-example" updating.  In this case you update the weights
  31. by a small amount as each training example goes by.  For very small step
  32. sizes, this amounts to the same thing; if your steps get too large, it can
  33. lead to trouble, since several atypical samples in a row can knock you far
  34. off course.
  35.  
  36. People generally speak of CUPS (connection UPDATES per second) only in
  37. connection with the second kind of algorithm.  If you're doing batch
  38. training, a more appropriate measure is CPS (connections per second), since
  39. the update step is outside the inner loop.  Things are further complicated
  40. by the fact that some people report CPS for the forward pass only, and
  41. others count the time required by both the forward and backward passes.
  42. And more complicates still is the question of what network you are talking
  43. about.  As the fan-in of units and the number of training examples
  44. increase, the CPS numbers go up, since the network is spending more time in
  45. its innermost loops.  So you sometimes see reports of "asymptotic CPS": the
  46. speed achieved in the limit of large fan-in and many training cases per
  47. epoch.
  48.  
  49. In batch training, counting both the forward and backward passes, the
  50. innermost loop is essentially a dot product in the forward direction and a
  51. dot product with added bookkeeping in the backward direction.  If
  52. everything is perfectly balanced, that's about 3-4 multiply/accumulate
  53. instructions (or 6-8 FLOPS) per connection-crossing.  So a DSP chip rated
  54. at 20 MFLOPS can hope to approach an asymptote of about 2.5 to 3.3 MCPS.
  55. (Some hardware backprop implementations may use integers rather than
  56. floating point, but that's another story.)  A lot of the accelerator boards
  57. beign sold as "neurocomputers" max out in the 1-3 MCPS range.  A hot
  58. workstation will do about as well.
  59.  
  60. One famous neural net implementation was done on the ten-processor Warp
  61. machine at CMU.  This machine was rated at 100 MFLOPS, and gave an
  62. asymptoptic backprop performance of about 17-20 MCPS, depending on how you
  63. count.  Some large SIMD machines should be capable of 1 GCPS or so, but
  64. there's a problem keeping these machines fed with sufficient data.
  65.  
  66. To answer your more recent question: If you're doing per-epoch update, the
  67. weights are not changed until after all the forwad-backward passes are
  68. completed.  If you are doing per-example updating, the back-propagation and
  69. weight updating can be interspersed.  It's probably more correct to update
  70. a weight AFTER the error has propagated backwards across it, but if your
  71. weight-update steps are large enough for this to matter, you're going to
  72. get in trouble anyway due to stochastic fluctuations in the data.
  73.  
  74. -- Scott
  75.  
  76. ===========================================================================
  77. Scott E. Fahlman
  78. School of Computer Science
  79. Carnegie Mellon University
  80. 5000 Forbes Avenue
  81. Pittsburgh, PA 15213
  82.  
  83. Internet: sef+@cs.cmu.edu
  84.