home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / lisp / mcl / 1891 < prev    next >
Encoding:
Text File  |  1992-12-24  |  4.9 KB  |  100 lines
  1. Newsgroups: comp.lang.lisp.mcl
  2. Path: sparky!uunet!spool.mu.edu!agate!boulder!cambridge.apple.com!news.cambridge.apple.com!news.media.mit.edu!enterpoop.mit.edu!usc!news.service.uci.edu!ucivax!pazzani
  3. From: pazzani@pan.ics.uci.edu (Michael Pazzani)
  4. Subject: Re: speed freak buys farm?
  5. Message-ID: <725254225.24113@news.Colorado.EDU>
  6. Lines: 81
  7. Sender: news
  8. Nntp-Posting-Host: pan.ics.uci.edu
  9. Reply-To: pazzani@ics.uci.edu (Michael Pazzani)
  10. Organization: Univ. of Calif., Irvine, Info. & Computer Sci. Dept.
  11. References: <725148821.5417973@AppleLink.Apple.COM>
  12. Distribution: co
  13. Date: 25 Dec 92 02:36:07 GMT
  14. Approved: news
  15. X-Note1: mail msgid was <2B3A7397.27344@ics.uci.edu>
  16. X-Note2: message-id generated by recnews
  17. Lines: 81
  18.  
  19.  
  20. Howard-
  21. Others have asked the question "Are you sure you running the right
  22. algorithm?"  Although Koza has implemented his genetic programming
  23. approach efficiently, I'm not convinced that genetic programming
  24. is the best solution for your task.
  25.  
  26. I've read most of his papers, and looked at his book, (and seen the
  27. videotape), and I agree that it's a very interesting research
  28. paradigm, and has a lot of potential.  It overcomes a limitation of
  29. typical genetic algorithms in that it works on trees rather than
  30. bit-strings.  The great thing about genetic programming, is its
  31. generality. it can solve a wide variety of problems, from learning
  32. classification rules, curve fitting, robot control, game playing etc.
  33. But I don't think you really care about this generality.  You have a
  34. specific problem in mind:
  35. >The particular problem that I am battling with evaluates a 1000 deep stack
  36. >filter of window 7 across a test series of 600 data points
  37.  
  38. There's not enough information here to tell exactly what your task
  39. is, but there may be a special purpose algorithm (function optimization?),
  40. that can be used instead of the general purpose one.  For an area,
  41. I know more about (learning classification rules), there are algorithms
  42. (e.g., decision trees) that run thousands of times faster than genetic
  43. programming, and produce more accurate rules.  I would imagine there
  44. might be techniques (e.g., gradient descent, simulated annealing, etc.)
  45. that might also be applied to your problem.
  46.  
  47. In a previous message, you wrote:
  48. >Ultimately, you will end up with the 'fittest' (optimal) set of factors.
  49.  
  50. Actually, you'll learn one of a large family of functions that performs
  51. perfectly on the fitness (or training) data.  However, like all
  52. induction algorithms, there are no guarantees about how it will
  53. perform on unseen data drawn from the same population.  A potential
  54. problem with genetic programming is that the function learned is
  55. typically quite complex.  There are reasons to believe (the minimum
  56. description or Occam's razor), that simpler functions will be more
  57. accurate than complex ones on unseen data.  For example, look at the
  58. spiral example in Koza's book.  Although the learned function correctly
  59. distinguishes which of two spirals each point lies on, the resulting
  60. function (illustrated in gray in the figures) doesn't really look like
  61. two interleaved spirals.
  62.  
  63. Koza rarely discusses how functions created by genetic programming
  64. work on unseen data.  One excuse is that it would be difficult.  To do
  65. this well would require running genetic programming a number of times
  66. on different subsets of the data, and measuring the predictive
  67. accuracy on unseen data.  With repeated trials, you could find the
  68. average accuracy, and compare it to alternative approaches.  When each
  69. trial takes a week on Quadra, I can understand why this isn't done
  70. often.
  71.  
  72. By the way, it might be the case that a slight modification of genetic
  73. programming would generalize better on unseen data.  The fitness
  74. function typically used in this approach computes something (mean
  75. squared error, accuracy, etc) on the a sample of the data.  A fitness
  76. function that in addition penalized complex functions (e.g., by
  77. subtracting the number of cons cells in the s-exp of the program)
  78. might perform better.  I'll let you know in a few months.
  79.  
  80. Finally, if you are going to use genetic programming, you really
  81. aren't restricted to lisp.  It is very simple to write an interpreter
  82. in any language for the subset of lisp that genetic programming
  83. program operates on.  All you need is constants and function
  84. application. In fact, that's what the "fast-eval" function does.  For
  85. example, you could write a C program that mutates and breeds
  86. s-expressions, write the "terminal" functions in C, and write an
  87. interpreter to "eval" them.
  88.  
  89.  
  90. Mike
  91.  
  92. P.S.  The above messages isn't meant as a critcism of Koza.  He's
  93. clearly made a significant research contribution.  However, until more
  94. experience is gained with genetic programming, and it is compared to
  95. alternative approaches in AI, (and statistics), I wouldn't recommend
  96. purchasing any hardware to run it on a specific application.  In case
  97. anyone from NSF or DARPA is reading, I'd strongly recommend buying
  98. Koza a connection machine or a farm of Quadra so that he can continue
  99. research in this area.
  100.