Memory in GP

Back to main GP Brainstorming page.


Astro Teller's slides for the symposium session on memory in GP

Session Format and Outline
==========================================================

Memory and Memory issues in GP: Format
--------------------------------------

Go through each of the five related topics for a minute
to give some form (not necessarily boundaries) to the discussion.

Go back through the five topics more slowly for discussion on
the each of the related topics.  However, discussion which cuts across
some or all of the topics instead of running along one of them is
encouraged!

Memory and Memory issues in GP: Topics Outline
----------------------------------------------

Techniques and Tools for analyzing GP programs

Memory structures and Memory based problems

GP task domains that need Memory

Loops and Recursion

Where does GP+Memory fit in the ML Picture?

Open Propositions



Memory in GP: Techniques and Tools for Analyzing [how] GP Programs [work]
================================================================

The ``Fly-through'' model of memory investigation

The "Bllllllllllll" technique 
(Showing a running visualization of both the program's actions and
 its changing memory)

Historical Information

Identification of related subtrees and subsections of memory

Memory Benchmark problems like Tartarus

Fingerprinting (e.g., I/O Boundedness)

Automatic code annotation wrt memory usage

Show which memory locations are being used as pointers.

Show which mem locations are not being read at all.  Show which mem
locations are used as pointers to these dead locations, etc.



Memory in GP: Memory Structures and Memory-based Problems
======================================================================

A) How can we build more complex data-structures from simpler ones in GP?
   (e.g., W. Langdon's work on stacks and queues using indexed memory)

B) Once we evolve them, how can we use them in future runs or even related
   domains?

Should we do those two previous steps in serial or parallel?
   In other words, when is doing step A first important?

Whether steps A and B are done together or in order, is indexed memory
   the right level at which to start?

What are attributes of the class of problems where memory (in particular
   sizable amount of memory) is necessary for success?


It may be possible for complex modular memory structures to emerge on the
fly if subtrees (Afra Zomorodian's idea) or ADFS (Alex Chaffee's idea) are
given *local* (static?) memory.




Memory in GP: Example Difficult Learning Problems that need GP + Memory
=======================================================================

Need the memory for computation VS. Need the memory for recall

Classification with many more than 2 classes



Memory in GP: Loops and Recursion
=======================================================================

Loops and Recursion need memory, but it can be in the environment (i.e
not accessible by the program).  Do we really need explicitly manipulable
memory structures?


Memory in GP: Where does GP fit in the Machine Learning Picture?
========================================================================

K-NN <-- X --> GP + Memory <-- Y --> ANNs. 

Is/Can/Should X < Y ?


Memory in GP: Open Propositions
========================================================================

The size of your indexed memory array does not dramatically effect
   your results.

If memory can be a mental model then a shared memory can be a language.

Retrieving the GP ``answer'' from memory instead of from the RPB can
   be a big win. (Upcoming Andre-Teller paper on this...)

Adding memory (READ + WRITE) to a problem does (in the worst case) no
   more harm than adding any two useless non-terminals.


Memory in GP: MEMORY FLY-THROUGH
==========================================================================

Visualization not available in ASCII form.




Sometimes indexed memory may be overkill, since the state-information of a DFA may be sufficient. {Eric Siegel}

(not (equalp array-of-integers mental-model))
GP makes it particularly easy to introduce useful bias in the form of high-level programming elements. For AI problems in particular (e.g., agents in virtual worlds) we should facilitate the production of "mental models" through the inclusion of high-level reasoning and knowledge representation tools in function and terminal sets. {Lee Spector}

the use of memory in applications such as symbolic regression and my time series merits serious investigation, and I will take a look at that. I can see arguments for memory being 'communal' (shared across all individuals, and persistent from one generation to the next) and 'individual' (with some means of inheritance). I wonder if it could come to replace ephemeral constants in some situations? {Howard Oakley}


Astro suggested benefits in taking GPs answer from a specified memory cell rather than using the function's return value. He and Dave Andre are working on a convincing demonstration of this for GP-96.

Discussion of debugging aids/tools for GP. Astro suggested need for tool to visualise how GP is using memory. Others suggested they would rather keep GP as black box and not investigate its guts.

Gregort Seront suggested there as a need for better explanations of why GP worked. Many in the audience felt that GP crossover would never be formally explained. Others felt this was mystic. Need for wider range of abilities on GP (eg mathematicians)? but Howard suggested good to have audience entirely of GP practitioners.

Lee Spector suggested GP needs much higher level memory structures than indexed memory. I suggested he should start with a read-only knowledge database and show GP can use such a thing before trying to evolve a knowledge database and the code to use it.

{William Langdon}