Scribe: Omri

Present: Lee, Micah, Omri, Emma, Tom, Kwaku

Administrativia

• There will be no meeting next week, but Lee will have open office hours after 3pm. Next meeting will be the week after, November 2 from 1-3pm.
• At the meeting on November 2, we will be meeting with Ranjan Srivastava (from UConn–whom Lee met on the train leaving GECCO).
• Also at the meeting on November 2, we will do a more thorough discussion of Learning Programs : A Hierarchical Bayesian Approach, which had been scheduled for today, but we didn’t have enough time for.
• Despite not meeting next week, Lee would like everybody to submit very realistic publication ideas and plans by next Friday.
• For next year’s GECCO, Lee doesn’t yet know what sort of funding for travel will be possible.

News

• There is a collaboration possible with William LaCava at UMass on a MatLab based project.
• Lee met with Adam Kalai, from Microsoft Cambridge (he works with Sumit Gulwani), who had interesting things to say about program creation by example. Reading some of his papers may uncover good problems for us to try and tackle using automatic software creation.
• Parent reversion is not a part of Clojush. @Lee: parent reversion should change such that an unimproved child will always survive if it is smaller.
• Lee, Omri, and Kwaku may collaborate to propose a workshop for GP using stack-based languages.
• Jon Klein seems have resurfaced, and has written a version of Push for Ruby. He wants assertion tests that are themselves Push instructions, which would leave true on the boolean stack if the assertion succeeds, false otherwise.

Discussion

• We discussed how to manage the size explosion of GSXover, leaving with the ideas that we could try increasing the iterations of auto-simplification; decreasing the rate of GSXover; increasing parent reversion; and/or implementing the new deletion operator.
• We briefly discussed Learning Programs : A Hierarchical Bayesian Approach
• Flea Market may only need explanation/examples/documentation for now. There may be pathologies that will surface, but hopefully they would be trivial to fix.
• We briefly discussed scoping for Push, but ultimately decided to have the real discussion take place through email.

Scribe : Emma

Present: Lee, Micah, Zeke, Tom, Emma, Kwaku

Administrativia

Lee – pushing things incrementally forward; potential meeting with Sumit Gulwani’s colleague in Boston; meeting one of Kourash Dani’s new students; corresponding with David Clark (tree GP – makes more sense than Push), will try using lexicase selection on it, geometric semantic crossovers things to add to Clojush (random on failure to combat reproduction default when crossover fails due to child size, i.e. fail to random instead of mom)

Tom’s suggestion for handling bloat: use simplification operator BEFORE fitness evaluation.

David Clark is interested in a new crossover operator that swaps the chunks of code that are crossed over.

Status Stuff

Status updates were framed primarily by issues of bloat and a desire to find better operators that either adapt to the state of the system or adapt to the particular parameters of the problem. In unrelated updates, Zeke is doing a Public Health hackathon and wanted to know if anyone had suggestions for uses of GP in this context.

Tom: Geometric Semantic Crossover gets really big really fast

Micah: Discuss places where humans are systematically outperformed by algorithms. Perhaps these are places that would be a good place to attempt to produce better algorithms for with GP.

Lee – implementing Family Feud

Tom – implementing deletion operators; having problems with random code generation (should perhaps be problem-specific) -> this is particularly problematic for language control structures

Lee (in response to some of Tom’s concern) – We should seriously consider implementing a notion of scope -> using tag space machines to capture scope (where the tag space is a stack of frames) -> maybe something halfway between push and tsm?

Consider the fact that not having scope makes it considerably more difficult to evolve larger programs.

Problems with variation operators – as a group, we’re really leaning towards

Zeke – interested in adaptive operators to handle plateaus

Issues with simplification – it’s really a mutation-delete operator.

Paper for next time

Learning Programs : a Hierarchical Bayesian Approach

• Scribe: Tom
• Members Present: Lee, Tom, Emma, Micah, Zeke, Omri (digitally)
  

  Pre-Meeting Agenda

  • UConn contact contacted
  • Lein 2?
  • web gp / push / javascript gp applications
  • bioavailability … bug?
  • lexicase + semantic xover on mux, valiant
  • database for visualization work (?)
  • uniform subtree mutation etc.
  • size-based tournaments future paper?

  Meeting Notes

  Administrivia

  • Put things you want to talk about it next week’s meeting notes.
  • Lein1 vs. Lein2 – it appears that Lein2’s deps is not compatible with Clooj, so use lein1 if you need to pull deps for Clooj.
  • It would be great if someone can figure out how to run Clojure code, hit an exception, and be able to examine the state and the variables. It would be preferable if this did not include using emacs, but it’s fine if it does.

  Lexicase + Geometric Semantic Genetic Operators

  • Good success on MUX-6, though Tom notes that this problem seems ideal for this method
  • Les Valiant boolean problem
    • Lee is trying a 50 out of 100 version currently
    • Programs get big, even with simplification
  • Lee should implement general operators

  Size-based Tournaments

  • We can use the GECCO 2012 poster results as a beginning / reason for using 2/2
  • Test on 1 or 2 hard problems in ECJ
  • Maybe do some Clojush runs, but only for our benefit and not for the paper

  Database for Visualization

  Zeke, Tom, Emma, and Josiah will be working on this in various capacities.

  Web GP / Javascript

  Possible uses include a Push demo that could be an interactive interpreter or a demo of PushGP.

  Cell Phone Load Management

  This is a potential full app for an Android phone. Maybe worth pursuing?

  Uniform subtree mutation and crossver

  • Micah will try using Lee’s tree GP.
  • If we want to publish results, it should be relatively easy to implement in ECJ.

Reading: File:Nchembio.689.pdf Efficient discovery of anti-inflammatory small-molecule combinations using evolutionary computing – Zeke to lead

Administrativa

• Merging updates with master: Since I (Tom) am pushing a lot of Clojush updates recently, I’d be happy to do the actual merging etc. as well. This would probably involve Lee giving an ok to the merge before it happens.

Things Tom wants to Discuss

• Bloat theory and uniform operators
• Real-time graphing and statistics of cluster runs.

Notes:

article:

   this paper was about innate immunity rather than that which you develop in response to pathogens
   There are certain white bloodcells that just respond to patterns of bad.
   Ther white blood cells they looked at respond to certain things and signal other cells to act with IL1beta
   The drug company wanted to use drugs synergistically to control IL1beta, because using a lot will kill you
   they had 33 drugs and wanted to combine them in order to attempt to produce a specific amount of IL1betta in response to LPS
   note that the drugs can kill the macrophages, so they were trying to get low macrophage death for low IL1betta production
   they used a simple binary GA with the fitness in the real world
       the trick to it is the way you treat multiple objectives for fitness in parents. There's a lot of talk about hypervolume in attempting to improve this. Most are pareto based. This one wasn't.

LEE!!! ~ Contact UCon guy. Invite him to come discuss projects with us.

UMASS may have automated labs that could do the wet side of some cool gp stuff.

we should have a blackboard of ideas —>> we could build a space —>> we could have a google doc, Oh, ya great. Coool, now we have one.

Experiment idea: Lexicase selection is a way of making parents that are talented as specific aspects of problems. Similarly if any parent that is capable of solving a novel combination of answers it should be valued. Perhaps scaled lexical selection should be pursued. The two together (lexical and gsgp) could be mashed up so they might hit on answers and then blend success.

quasi-gsgp where instead of (if ___ A B), you do (if ______ (chunk A) (chunk B)) even better if you can do it intelligently. The goal of this is to use gsgp ideas to increase modularity, rather than acting towards hitting the geometric mean.

You can have a GP program which is a bunch of numbers and they follow lists choosing options and diving down to deeper lists.

code could be executed on it’s own scope <— relating to chunk gsgp

why do people mutate so stuff adds and removes in the same spot in push, why even do both?

there are some papers which believe they have conclusively stated that bloat as defense against cross over and mutation have been disprove. Lee doesn’t believe them. There’s lot’s of stuff that causes bloat, it’s context dependent.

Thomass and Zeke: a web page that is displaying graphs and logfiles of the generations as they’re run

   currently only outputting population data
   should test to see how much it's slowing things down
   you could link children to parents to get genealogies

read File:Uniform mutation.pdf

Present: Lee, Tom, Zeke, Micah, Kwaku, Emma
Administrativia

– Must send updates early! (This is for everyone)

– Clojush macro issue: Tom’s solution seems to be working; it will be pushed with the oral bioavailability code

– Readings: whosoever suggested the reading, leads and will be expected to have a greater depth of understanding. Everyone else is expected to at least skim and have a high level view of the paper.

– The Valiant Challenge: Lee is still working on it, knows what to try next, but may have a conflict with Valiant over the definition of evolution

– Emphasis on escalating research to journal articles and making incremental progress on all projects.
File:Operator Equalisation, Bloat and Overfitting – A Study on Human Oral Bioavailability Prediction.pdf discussion

– New sample problem + new technique

– Possible future task: apply Silva work in Push, leveraging ease with which programs of varying size can be made using Push

– do an experiment/analysis of whether bloat really does protect against cross over (possible literature review?)
TSM

– mutation -> consider making uniform; four types: (1) deletes entry, (2) inserts entry, (3) mutate tag, (4) mutate value -> use the same probabilities as the initial random tag mutation

– toggle between eda and improving the machine

Tom wants to discuss:

• Hardness-biased lexicase selection
• Web-based graphs of cluster runs

IN MEETING NOTES CI Lab notes

Administrative

• none

Talking about clojush speed

• Lee codes for readability overall
• profiling can be tricky
• No one really wants to take this on, but someone should do this…

Talking about paper

• Lee summarizes
• We discuss
• we could use this in clojush .. might work well with lexicase selection
• POSSIBLE TASK: Implement semantic crossover in clojush with lexicase selection
• POSSIBLE TASK: differentiate a few code size limits and make more parameters
• POSSIBLE TASK: improve simplification by testing parts of code for constants.

Scribe: Tom

Paper to read for next week: Geometric Semantic GP. Feel free to skim the sections that get very mathy.

Fall Membership

• Members now include: Lee, Tom, Emma, Zeke, and Micah, with Kwaku and Omri being maybes. Someone should probably change the main lab page to reflect this.
• Lee should pester Kwaku and Omri about their membership.

Tag Space Machines

• So far, we aren’t seeing much evolutionary progress.
• Most initial programs are probably too small. We’ll focus for now on generating a viable generation 0, so that evolution has something to work with.

Uniform Mutation and Crossover

We got sidetracked by a large discussion about uniform mutation and crossover, both in TSMs and in PushGP. This may definitely be worth pursuing further in Push.

• Option 1: Set a mutation percentage, and then each point independently has that probability of being mutated.
• Option 2: For a program of size N, mutate (mutation percent * N) points within the program.
• Either of these options may also work with crossover, where the inserted code is taken from the “father” instead of created from scratch.
• These are also potentially doable in tree GP, which would be of higher interest to the community at large.

Kata Bowling

• Tom has been working on some graphing things.
  • Heatmaps of best individuals of a run over all test cases.
  • Piano roll plots of fitnesses and sizes within a run.
• What can we do to solve this problem?
  • Some sort of combination of historically assessed hardness and lexicase selection may be useful. This could add bias to have harder test cases near the beginning of the sorted list of test cases for lexicase selection.

Geometric Semantic GP

• Singles out good features of parents and combines them (somehow).
• Problem: This creates a lot of bloat.
• Solution? Maybe use Push with simplification.

Leslie Valiant

If we can solve the 500-500 boolean parity problem with GP, that would be very good!

• New members wanted! Lee already emailed his advisees, but this does not include all people from past GP classes, nor people that changed advisees while Lee was on sabbatical. He is going to do that.
• NO meeting next week.
• Following week, meeting on Friday 1-3pm at Hampshire (this will be the regular time henceforth.
• Zeke has been evolving R programs. Programs seem to be memorizing, not coming up with meaningful data. He would like to see how some “solutions” do on test data to see if they have any predictive power.
• We all want GP web apps, through Clojure and/or Clojurescript. Zeke and Lee have been working on this, random errors and bugs. Still being worked out–oh wait, we fixed it during meeting, now it works.
• Omri should really get the Flea Market all set and working (what a thought)!
• Lee looked at Emma’s TSM code, hasn’t yet tried out the examples.
• Emma included input instructions for TSM. Discussed possibility of non-uniform TSM generation, with high amount of pairs and tag instructions.
• Lee proposed a COSMOS experiment with non-parametric data: COSMOS versus no COSMOS. The idea would be to show that no COMSOS will show “significant” results after some “large” number of runs, BUT after a “larger” number of runs, it will no longer show significance. Ideally COSMOS would not be fooled by this ephemeral “significant result” (stardust?).
• Tom has been doing Bowling runs. Nothing groundbreaking, progress happening.
• Lee brought up a very interesting idea about evolving rules for cellular automata given image data.
• For next meetings’ status report, everybody should also include a reading suggestion.
• We all decided to be BFFs (friendship bracelets pending)!

Admin

Agenda

Admin (10min)

Discuss readings

General: Sumit Gulwani’s Spreadsheet Data Manipulation Using Examples (in email)

Suggested Background: Version Space Algebra and its Application to Programming by Demonstration 

Additional reading: Martin Rinard’s Example Driven Program Synthesis for End-User Programming

Possible followup with Gulwani: Feedback generation for intelligent tutoring systems?

The Tozier files

Pushing Zeke to Push and Clojure

“Fast” lexicase selection

Quotes re GECCO?

Finite algebra draft

Clojush updates needing merging? (recognize-literal)

Meeting Notes

• Lee will be meeting with Hampshire PR person about GECCO article. Get him quotes about GECCO if you want!
• We have merged the changes to master. NOTE: Make sure you follow the proceedure for updating code – don’t update on GitHub, since things get messed up that way.
• Finite Algebras paper draft will be emailed to those interested in reading and making suggestions.
• Tom will be using the cluster next week for some kata bowling runs.
• Zeke was encouraged to use Clojure and Push, but will likely stick to what he knows.
• Tom will delete fast-lexicase-selection and push to GitHub. The old version will still be on GitHub in old commits, so we can get it back later if we want.

The Tozier Files

• There are some valuable things in the Bill Tozier emails, but also some things that aren’t really what we want to do.
• Things that may be valuable to persue:
  • Try shorter test cases with kata bowling
  • Monitoring of runs during evolution. Piano Roll plots or other finer details may be worthwhile, but other graphical investigations that only require things that are currently printed in logs may be just as good.
  • Think about why we are failing, and what to try next.
  • Cheating: Interesting topic. It may be useful to cheat at the beginning to see what you are up against, and take away later once you understand the problem better. Plus, cheating can be seen in different lights depending on your goals.
  • Maybe remove some instructions to make the search space smaller (flush, yank, shove, …)
  • Try writing a solution by hand.

Discussion of Gulwani paper

• This makes us think it may be worthwhile to implement a stronger string / pattern matching library in Push.
• The problems solved here may be inspirations for future “programming problems” for GP to solve.
• Our motivations for program synthesis are similar to theirs.
• As for the intelligent tutoring system, Lee will contact Sumit Gulwani to investigate further collaboration.