Replacement for protected division

Some notes from Enhancement of Model Generalisation in Multiobjective Genetic Programming by Ji Ni:

Analytic quotient (AQ) operator systematically yields lower mean squared errors over a range of regression tasks, due principally to removing the discontinuities or singularities that can often result from using either protected or unprotected division. Further, the AQ operator is differentiable.

The function set is a very important component in a GP setup, and can be set as arithmetic operators, for instance, addition, subtraction, multiplication and protected division (PD), or Boolean operators, such as AND, OR, XOR or even complex functions e.g., filters for different problems.

The commonly-used basic arithmetic operators appear to date back to Koza. Koza’s basic concern about operator sets was closure – the desire for an operation on a real number to always map to another real number – although he recognised the difficulties with the normal division operator and therefore introduced protected division whereby
          | x/y    y<>0
PD(x,y) = |
          | 1      y=0
The protected division imposes a real number 1 to replace the mathematical singularity that is produced by normal division when the denominator equals 0.

The use of the protected division appears “common” although maybe not universal, and some authors appear to use an unprotected form of the division operation. According to IEEE754:1985 standard for floating-point arithmetic, using unprotected division (UPD) we have
     | INF   x<>0
x/0 =|
     | NaN  x=0
where INF symbolises infinity and NaN, not-a-number. More specifically, NaN stands for the indeterminate form of 0/0, although in other cases, e.g., NaN = sqrt(-2) stands for an imaginary (not real) number.

In the evolutionary process, we evaluate trees to obtain their fitness vectors comprising mean squared error and node count. While comparing fitness vectors by Pareto dominance, INF produces sensible results, while NaN always gives a logical FALSE that possibly disrupts the evolutionary process. We speculate that authors using unprotected division in GP have an (implicit) mechanism to discard GP trees with NaN fitness in selection for breeding or tournament comparison. Both PD and UPD operators are used in GP so we cover both protected and unprotected division in our experiments. Specifically, to avoid NaN disrupting the evolutionary process, we assign a large fitness to trees returning a NaN so that they will be discarded.

Having further investigated unprotected and protected division, we noticed the only effective difference is that they define the mathematical singularity differently – returning 1 in PD while returning INF in UPD – the discontinuity remains consistent. In the neighbourhood of the discontinuity, sensible but “large” real numbers are returned. Those “spikes” of very large values are highly undesirable, especially in regression problems since predictions can deviate markedly from the target function. This shortcoming of (un)protected protected division was previously identified by Keijzer who proposed using interval arithmetic to probe the regions around training points for discontinuities. Unfortunately, Keijzer’s work seems to have been largely ignored. Similarly, the option of simply omitting the problematic division operator has been explored, but the resulting function set is far less expressive.

Additionally, (U)PD embeds a discontinuity whenever y = 0 and therefore renders the function represented by the whole tree nonanalytic. This inability to differentiate the tree function restricts the range of operations which can be carried out on the tree. For example, the nonanalyticity due to (un)protected division prevents the use of curvature as a complexity measure. We thus propose an analytic quotient (AQ) operator to replace PD to stabilize the GP trees by fundamentally removing discontinuities.

AQ(x,y) has the general properties of division, especially when , but is everywhere differentiable.

morinim / vita

Replacement for protected division #6