home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3248 < prev    next >
Encoding:
Text File  |  1992-08-19  |  7.9 KB  |  170 lines

  1. Newsgroups: comp.ai.neural-nets
  2. Path: sparky!uunet!usc!sol.ctr.columbia.edu!destroyer!ubc-cs!unixg.ubc.ca!kakwa.ucs.ualberta.ca!alberta!arms
  3. From: arms@cs.UAlberta.CA (Bill Armstrong)
  4. Subject: Re: Reducing Training time vs Generalisation
  5. Message-ID: <arms.714289771@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: <Bt9GIx.9In.1@cs.cmu.edu>
  10. Date: Thu, 20 Aug 1992 05:49:31 GMT
  11. Lines: 157
  12.  
  13. sef@sef-pmax.slisp.cs.cmu.edu writes:
  14.  
  15. >    >If you shape the training set a bit more carefully
  16. >    
  17. >    >                *      *
  18. >    >  .............*        *.................
  19. >    
  20. >    >and use a two-hidden unit net, you can FORCE the solution with a big
  21. >    >excursion.  Only the "ankle" part of the sigmoid will fit these tossing
  22. >    >points.  However, a net with more hidden units could again create a
  23. >    >plateau, however, and this would be the more likely solution.
  24. >    
  25. >    Same question: is this plateau a local minimum only?
  26.  
  27. >Well, one ugly solution uses four hidden units and gets up to the plateau
  28. >in two steps, and down in two more.  Again, zero error, so the solution is
  29. >one of the global minima.
  30.  
  31. The plateau solution might not be a global minimum if we just specify
  32. the values along the ....... part to fit the sigmoids perfectly only
  33. if there is a peak.
  34.  
  35. >    The more hidden units and layers you have, the less transparent the
  36. >    behavior of the whole net becomes.  Some examples of "wild" behavior
  37. >    will only appear with relatively small weights, but lots of layers:
  38. >    linear regions of sigmoids all lining up to produce a big excursion.
  39. >    
  40. >Sure, but they will have no incentive to do this unless the data, in some
  41. >sense, forces them to.  You could always throw a narrow Gaussian unit into
  42. >the net, slide it over between any two training points, and give it an
  43. >output weight of 10^99.  But it would be wrong.
  44.  
  45. A good reason not to use such units, eh!
  46.  
  47. >    >1. Sacrifice perfect fit.  Weight decay does this in a natural way, finding
  48. >    >a compromise between exact fit on the training set and the desire for small
  49. >    >weights (or low derivatives on the output surface).  The weight-decay
  50. >    >parameter controls the relative weight given to fit and smallness of
  51. >    >weights.
  52. >    
  53. >    I agree this will work if you can get fine enough control that reaches
  54. >    to every point of the input space to prevent excursions, and the
  55. >    fitting of the function to the spec is good enough.  Though I don't
  56. >    deny it could be done, is this easy, or even possible to do in practice?
  57. >    
  58. >You don't need fine control.  If you just crank some weight decay into the
  59. >error measure, it will keep the net from making wild excursion without
  60. >being forced to by the data.  For example, in the example about the big
  61. >gaussian spike, it would drive the output weight to zero if the Gaussian is
  62. >not helping to fit the data.
  63.  
  64. I seem to recall going over this before, and I believe what is
  65. required to upset the scheme is to have a lot of training points which
  66. force training to fit a solution having a peak.  I.e. if six points
  67. aren't enough, take as many as are required to overwhelm the weight
  68. decay.  I suppose you can make the weight decay greater as the number
  69. of training points increases to make it so the weight decay can't be
  70. overwhelmed.  But I think you would lose some genuine peaks which
  71. weren't represented by their fair share of points in the training set.
  72. Isn't this true: unless your training samples are well distributed,
  73. you tend to wipe out features of less well sampled parts of the space?
  74. You might say this is what you want.  A little control might be desirable.
  75.  
  76. >    >2. Sacrifice smoothness.  If sharp corners are OK, it is a trivial matter
  77. >    >to add an extra piece of machinery that simply enforces the non-excursion
  78. >    >criterion, clipping the neural net's output when it wanders outside the
  79. >    >region bounded by the training set outputs.
  80. >    
  81. >    If you do want some excursions and you don't want others, this won't
  82. >    work.  It is not a simple matter to find the problem regions and bound
  83. >    them specially.  I believe it is NP complete to find them.  The
  84. >    plausibility of this can be argued as follows: ALNs are a special case
  85. >    of MLPs; you can't tell if an ALN is constant 0 or has some 1 output
  86. >    somewhere (worst case, CNF- satisfiability); this is a special case of
  87. >    a spike that may not be wanted.
  88. >    
  89. >Huh???  It's trivial to put a widget on each output line that clips the
  90. >output to lie between all those seen during training.
  91.  
  92. Sure.
  93.  
  94.   It's a bit harder,
  95. >but still not NP complete, to find the convex hull of outputs and clip to
  96. >that.
  97.  
  98.  
  99. Fine.  Unfortunately in both cases above, there can still be excursions in 
  100. the convex hull that you don't want and can't prevent this way.
  101.  
  102.   Now, if you want some excursions and not others, you'd better tell
  103. >the net or the net designer about this -- it's a bit unreasonable to expect
  104. >a backrpop net to read your mind.
  105.  
  106. OK -- this is close to what I meant by "fine control".
  107.  
  108.  
  109. >    
  110. >    The usual MLPs are very "globally" oriented, so they may be good at
  111. >    capturing the global information inherent in training data.  The
  112. >    downside is that you can't evaluate the output just taking local
  113. >    information into account...
  114. >    (Does anyone hear soft funeral music?)
  115. >    
  116. >Well, since you keep pounding on this, I will point out that in most
  117. >backprop-style nets after training, almost all of the hidden units are
  118. >saturated almost all of the time.  So you can replace them with sharp
  119. >thresholds and use the same kind of lazy evaluation at runtime that you
  120. >propose for ALNs: work backwards through the tree and don't evaluate any
  121. >input sub-trees that can't alter the current unit's state.
  122.  
  123. You have a lot more experience than I do with sigmoid type nets, so
  124. what you have just said is extremely significant, in that you are
  125. coming closer all the time to a logical net.  If you are able to
  126. replace sigmoids with sharp thresholds, and not change the output of
  127. the net significantly, then you are really using threshold *logic*
  128. nets.  Now let's see what it takes to get lazy evaluation: first of
  129. all, I think you would have to insist that the sign of all weights on
  130. an element be positive, and all signals in the net too.  Otherwise in
  131. forming a weighted sum of inputs, you can not be sure you are on one
  132. side of the sharp threshold or not until you have evaluated all inputs
  133. (not lazy!).  I think the signals would have to be bounded too.
  134. I think this would be OK.  ALNs are still faster, because they don't
  135. do arithmetic, but ALNs don't have as powerful nodes.
  136.  
  137. One argument for going whole hog into ALNs is that you don't have to
  138. train using sigmoids, then risk damaging the result of learning by
  139. going to sharp thresholds.  If there were a training procedure for
  140. networks of the above kind of node with a sharp threshold, that would
  141. be very promising.  I thought backprop required differentiability to
  142. work though.
  143.  
  144.  
  145. >Myself, I prefer to think in terms of parallel hardware, so lazy evaluation
  146. >isn't an issue. 
  147.  
  148. Not true!  If you have a fixed amount of hardware, then to do large
  149. problems, you will have to iterate it.  Lazy evaluation allows one to
  150. suppress iterations because you don't need certain inputs, so laziness
  151. is still very useful.  The speedup factor compared to complete evaluation
  152. grows with the size of the problem.
  153.  
  154.  Yes, sigmoid unit hardware is a bit more expensive to
  155. >implement than simple gates, but I don't need nearly as many of them.
  156.  
  157. Hardly seems worth while to keep sigmoids if almost all of your units
  158. are almost always saturated though.  ALNs may have to train with lots
  159. of nodes, but after training, we collapse entire subtrees of adaptive
  160. nodes into just a single transistor for execution.
  161.  
  162. Thanks.
  163.  
  164. Bill
  165. --
  166. ***************************************************
  167. Prof. William W. Armstrong, Computing Science Dept.
  168. University of Alberta; Edmonton, Alberta, Canada T6G 2H1
  169. arms@cs.ualberta.ca Tel(403)492 2374 FAX 492 1071
  170.