Support for subclass type with STGP

[cmd-ntrf]

From JasonZu...@gmail.com on January 18, 2013 10:17:47

Below is the patch text generated by mercurial. I am hoping this was the correct avenue to submit a change.

# HG changeset patch
# User Jason Zutty <jasonzutty@gmail.com>
# Date 1358521911 18000
# Branch dev
# Node ID 72e303c713bc7dd83b1286a7109e5881b5041b97
# Parent  2bb81fcc9b7bf352e60d31814f7910152641f1d5
Added a method polymorph to class PrimitiveSetTyped.  Polymorph allows the terminals from one type to be used wherever terminals of another type are permitted.

diff -r 2bb81fcc9b7b -r 72e303c713bc deap/gp.py
--- a/deap/gp.py    Mon Jan 14 11:08:22 2013 -0500
+++ b/deap/gp.py    Fri Jan 18 10:11:51 2013 -0500
@@ -304,6 +304,12 @@
         """
         return self.terms_count / float(self.terms_count + self.prims_count)

+    def polymorph(self,supertype,subtype):
+   """Allows the use of all terminals of a subtype,
+   wherever the use of the supertype is permitted
+   """
+   self.terminals[supertype] = self.terminals[supertype] + self.terminals[subtype]
+
 class PrimitiveSet(PrimitiveSetTyped):
     """Class same as :class:`~deap.gp.PrimitiveSetTyped`, except there is no 
     definition of type.

Original issue: http://code.google.com/p/deap/issues/detail?id=12

[cmd-ntrf]

From f.derain...@gmail.com on January 18, 2013 07:22:37

Labels: -Type-Defect Type-Enhancement

[cmd-ntrf]

From felix.antoine.fortin on January 18, 2013 07:43:23

Hi Jason,

The function is actually incomplete as the polymorphism is only implemented for terminals. Primitives should also be considered such as :

def polymorph(self, supertype, subtype):
    self.primitives[supertype].extend(self.primitives[subtype])
    self.terminals[supertype].extend(self.terminals[subtype])

I like the fact that it is quite simple and I think it covers most cases.

However, I am not sure I like the idea of forcing the user to order the calls to PrimitiveSet function. What I mean, is that if a primitive returning a subtype is added after the polymorph function is called, it will not be included in the supertype set. This can of behaviour is difficult for the user to debug and there is no way we can actually force the user to order its function call, we can only provide a warning in the documentation. My experience tells me that warnings are too often looked over and might indicate a problem with the design.

One more example of the ordering problem, if there is more than two levels to the type hierarchy, the user would have to start call to polymorph from the leaves i.e. : Form <- Rectangle <- Square

pset.polymorph('rectangle', 'square')
pset.polymorph('form', 'rectangle')

Otherwise, the primitive returning Square won't be added to the set of primitives returning Form.

Finally, if we are to integrate such mechanism in DEAP, we will also need a clear and non-trivial example where such mechanism is useful. We do our best to provide users example of different possible use cases with DEAP and it will be interesting to add another GP example using polymorphism.

Status: Started
Labels: -Priority-Medium Priority-Low Component-Logic

[cmd-ntrf]

From felix.antoine.fortin on January 18, 2013 08:02:34

I would probably opt more or a solution where the user can define via a dictionary a type hierarchy and provide that dictionary to the init function of the PrimitiveSet during its creation. This has the advantage of defining once and for all the type hierarchy and avoid any king of trouble regarding call orders.

This however implies a major overhaul of the way primitives and terminals are currently selected in DEAP GP. I know how it could be done properly, the only thing I am currently lacking is the proper motivation to integrate it in DEAP as I am still missing a clear example of when such feature is actually essential.

So if you could provide us a nice example that could be integrated in DEAP examples where type hierarchy is concretely used to solve a genetic programming problem, I will be glad to undertake that major overhaul.

Regards,

[cmd-ntrf]

From JasonZu...@gmail.com on January 18, 2013 08:02:37

Thank you for catching the primitives issue. For some reason I had talked myself out of it yesterday when I was thinking about this, but I realize now I was making a logic flaw (I was thinking in terms of inputs, not return types).

I realize that this fix is not ideal, and can result in some human error, in terms of placing it before some methods are added, or putting levels in the wrong order, but it is a very simple solution that won't require modifying huge amounts of (and possibly breaking) existing code. It also is nice in that it will save users adding loads of terminals and primitives.

In summary this fix:
Reduces search space to produce higher percentage of valid programs
Eases the burden of creating a large amount of primitives and terminals to handle types that can be used together.

A can provide you an example of how I am using this:
I was using terminals of my user defined type numpy, they were numpy arrays. I also had a primitive that called numpy.sqrt. This would cause a lot of problems in my produced programs if the numpy array contained negative values. My solution was to create a type numpypos. Primitives like numpy.abs could now return numpypos. Terminals like arrays from numpy.ones or numpy.zeros could also be numpypos. The catch is I wanted all these numpypos objects to be used wherever numpy was also accepted. I can achieve this by calling
pset.polymorph('numpy','numpypos')
at the end of my pset additions.

[cmd-ntrf]

From felix.antoine.fortin on January 21, 2013 09:12:57

Although I agree that type hierarchy can be used to reduce the search space, I need to point out that this is not always the case. In the example you described, the search is reduced because the primitive argument type is changed from a global, top of hierarchy type 'numpy', to a more specific type 'numpypos'. However, the opposite case actually expand the search space.

Regarding your example, I am not sure that type hierarchy is required to solve your problem. Here is resume of what I understand, correct me if I am wrong :

• There is only two terminals returning a 'numpypos', 0 and 1, which square root is directly 0 and 1. The operation could be therefore be simplified to 0 or 1.
• The only primitive numpy.sqrt can have as a child is numpy.abs. So systematically, before calculating the square root, we take the absolute value of the argument except if it is a terminal.

I think it would be preferable and simpler to define a safe square root function on the same principle as the safe division proposed by Koza: if the input argument of the square root is negative, return 0.

[cmd-ntrf]

From JasonZu...@gmail.com on January 22, 2013 07:23:32

I am working on a more general GP primitive and terminal set, what I have commented above was merely one example.

For the numpypos type I can also generate several random numbers for negative and several for positive to serve as terminals.

I can make a float supertype and then have int subtypes. The int may be able to be used for methods where indices may be required.

Finally let's go with something more specific. Let's say one of my primitives is an fft (fast fourier transform), and another is an ifft (inverse fast fourier transform). The first returns a complex numpy array and the other takes in a complex numpy array. There are functions that work with complex numbers, and there are those that don't. Being able to work with the ffts in a way that produces valid trees will be beneficial to search space of my code.

I have added the methods to my code, and am using them at the moment to produce a much higher percentage of valid trees. I completely understand if you don't want to add the functionality to the project until it is completely fleshed out, but I am getting a lot benefit out of it, and I thought it would be good to share it with the community.

[cmd-ntrf]

From felix.antoine.fortin on January 23, 2013 12:17:27

I think we have cornered the proper solution to the problem of subclass type with STGP. I have included a patch of the proposed changes.

Instead of passing types as string to functions of PrimitiveSetType, we propose to directly use Python type and class. Each time a user add a primitive, we check first check if the type is already represented in the set. If it is not, we add every primitives that is a subclass of that type to its list of primitive. Then, the primitive is always added to each type's list of which it is a subclass.

The patch also include modification to the spambase example to demonstrate how it works on the user side.

The user do not specify the type hierarchy via the PrimitveSetTyped, but directly by using the Python subclass mechanism. The default type in gp, type, is change to object.

This patch should be importable with from the tip of the dev branch via hg import.

Summary: Support for subclass type with STGP (was: Added a patch to allow terminals of a subtype to be used where a supertype is permitted)

Attachment: polymorph.patch

[cmd-ntrf]

From felix.antoine.fortin on January 23, 2013 13:55:17

Owner: felix.antoine.fortin

[cmd-ntrf]

From felix.antoine.fortin on February 04, 2013 13:39:12

The patch has been imported in the development branch for release 1.0.

Status: Fixed