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