Construction of binary operators having two complicated children

[oisinkim1]

Dear Miles,

Thanks very much for your package and excellent documentation.

I had a question relating to the way trees are constructed in PYSR.

I am working on a project which involves creating first order logical formulas which are true on a mathematical dataset. Roughly speaking, we want statements which involve arithmetic atomic formulas (statements such as feature + 1 = feature') strung together with logicals, i.e. implies(and (A,B), C), where A, B and C are such atomic formulas. To implement this, we have turned off PYSR's constants and just treat the integers as extra features. We have implemented the logicals as custom operators and they are largely working correctly.

However, the problem we are having is as follows. We can easily create complex atomic formula of the form: 1+feature+feature'=feature''+2, etc using the GA. Similarly, we can create syntactically incorrect statements of the form implies('1', 1+feature=feature'), which we penalise by a soft constraint in the loss function. We can also create complex, logical statements that don't have any arithmetic operators. For example, implies(equals(feature', feature''), equals(feature''', feature'''')). However, we never find any statements of the form implies(A,B), where A and B are both correctly formed equals atomic formulas with at least one arithmetic operator, such as 1+feature=feature'.

We have heavily encouraged these in the loss function and even set their loss to zero to see if they are ever created in the population; they seem to either be vanishingly rare or virtually impossible to create.

We have come to the conclusion that this has to do with the way trees are made within PYSR itself. In essence, I am guessing that trees are constructed by building out one of the children A repeatedly, then attaching a binary implies(1, -) to A. What this means is that an implies is stacked onto A with the other child being a degree 0 node (constant/feature). After this, it is too rare for mutation to correctly occur inside the left child of implies to create a tree of the desired form. We were also hoping that boosting crossover probability could help for two trees implies(1,A) and implies (B,1). However, this seems to have little to no impact.

As a result, we were wondering if you would have any recommendations for going under the hood of the PYSR algorithm itself, to support the creation of two sufficiently complex arithmetic children A, B which are then joined by a binary. Otherwise, any suggestions for the creation of such trees would be greatly appreciated.

Thanks for taking the time to read this.

[MilesCranmer]

In principle there is nothing necessarily forming a hard block against this from forming, because of the fact that crossovers exist. A crossover could in theory just take a tree with implies(A,1) and another tree B, and make an implies(A,B) tree.

But I suppose the issue here is that it’s exceedingly rare to get this, because your constraints are quite rigid. And it’s hard to get there via direct mutation because all of the intermediate states are blocked from forming.

Is there any way you can relax certain constraints? i.e., rather than returning Inf if constraints are violated, could you return a large penalty that gets larger as the constraints are violated to a greater degree? Sometimes what I will do is count the number of violations, and return that added to the regular loss. It gives the genetic algorithm some “direction” to search on.

This is actually why the dimensional analysis constraint is implemented as a soft penalty rather than hard constraint.

---

To summarise, I suppose my advice is to think about intermediate states along the road to the final form - how would you measure performance of these in a way that proximity to the final form ~ proximity in loss?

[oisinkim1]

Thanks very much for your response, it is very helpful.

However, if I am understanding you correctly, I think that we have already tried using such a soft penalty approach in our loss function, relaxing the dimensional constraints in quite a number of ways. For example, we allowed the syntactically incorrect case implies(1, 1+feature=feature’), only penalising it softly. Unfortunately, we never saw these grow out at all beyond this point; they seemed to get stuck at this intermediate stage,

Thus, we were wondering if there was any relatively easy “under the hood” changes to the tree construction algorithm for us to implement that seemed plausible to you. In essence, directly allowing the construction of binaries joining together two complex children at some point in the process, if this makes sense at all. This was only because relaxing all the hard “inf” constraints seemed to have little to no effect, perhaps because the right kinds of mutations and crossovers are still exceedingly rare.

Thanks again for taking the time with this already.

[MilesCranmer]

Are you able to share the full code or a minimal reproduction of it, to help clarify the issue? It’s hard to understand otherwise.

I guess you can also take a look at template expression specs as it lets you are subexpressions. Maybe somewhat useful.

[oisinkim1]

Yes, thanks a lot.

Here, for example, is how we have handled our custom logical implies in the loss function, as well as a summary of the latter:

for node in tree:
  ...
  ...
  if is_implies_node
        left_child = node.l
        right_child = node.r
        for child in (node.l, node.r)
          if (child.degree == 0)
            implies_logical_error_count += 1
          elseif !((child.degree == 2 && child.op == equals_index) ||
              (child.degree == 2 && child.op == conjunction_index) || (child.degree == 2 && child.op == implies_index) || (child.degree == 1 && child.op == logical_neg_index))
            implies_logical_error_count += 1
          end
        end
        if (left_child.degree == 2 && left_child.op == equals_index)
            # Count all arithmetic operators in the entire equals subtree
            child_equals_arith += count_arithmetic_in_subtree(left_child, plus_index, times_index, minus_index)
            if child_equals_arith > 0
              flag = 1
            end
        end
        if (right_child.degree == 2 && right_child.op == equals_index)
            # Count all arithmetic operators in the entire equals subtree
            prev_child_equals_arith = child_equals_arith
            child_equals_arith += count_arithmetic_in_subtree(right_child, plus_index, times_index, minus_index)
            if child_equals_arith > prev_child_equals_arith && flag == 1
              println("NICE! Found the right kind of tree structure for implies.")
              return L(0.0)
            end
        end        
        implies_used_count += 1
      end
      ...
      ...
      exponent_sum = .... + (loss.dataErrorPenalty  (1.0 - weighted_acc)) - complexity_decay_val + implies_logical_error_count * loss.impliesLogicalCompErrorPenalty - child_equals_arith * loss.childComplexity + ... (Similar terms for the other operators)
      signumLoss = exp(exponent_sum)
end

The counts for logical operators, shown only for implies, are combined into the exponent_sum loss function. The idea is to softly penalise incorrect uses via the terms like implies_logical_error_count * loss.impliesLogicalCompErrorPenalty. Then we boost the kind of terms we want via the terms like child_equals_arith * loss.childComplexity, which counts the number of arithmetic operators nested inside equals whenever it is a child of implies. The terms we ultimately want would look like:

implies(equals(A+B,C+D), equals(E+F,G+H))

where A,B,C,D are features which may also have more arithmetic nested inside. Conjunction is implemented in an identical way.

Typical runs look like:

Complexity Loss Score Equation
1 2.005e-01 0.000e+00 y = nullity_D2
3 4.814e-04 3.016e+00 y = equals(nullity_D2, nullity_D2)
4 2.626e-04 6.060e-01 y = logical_neg(equals(rank_D2, width_D1))
5 8.788e-08 8.002e+00 y = equals(width_D1, width_D1 * _1)
6 5.945e-08 3.910e-01 y = logical_neg(equals(nullity_D2, height_D1 + nullity_D1))
7 2.261e-32 5.623e+01 y = implies(equals(height_D2 - height_D1, height_D2), nullity_D2)

In the final expression, only one of the children has the sort of arithmetic complexity we are looking for, and as a result it is syntactically wrong and softly penalised. As you can see, logical_neg, a unary operator, is able to have a child with arithmetic complexity, but the binary implies only has one child in which a "+" appears. Even after many runs with a range of parameter choices and significant boost for these terms in the loss, we have never found them. The print line: println("NICE! Found the right kind of tree structure for implies.") was our attempt at debugging to see if the right kind of expression ever appeared. For example, around 150 runs with the choices: "populations": 50, "niterations": 100, "ncycles_per_iteration": 1000, never produced any of the terms we want.

One other sort of typical run produces results like:

6 7.444e-08 3.910e-01 y = logical_neg(equals(nullity_D2, height_D1 - height_D1))
7 2.715e-11 7.916e+00 y = equals(rank_D1 - _0, rank_D1 * _1)
11 6.180e-13 9.457e-01 y = conjunction(equals(_0, _0), implies(equals(rank_D1, _0), equals(_0, _0)))

where the implies children have no arithmetic complexity at all, although they are now syntactically correct.

Many thanks again for taking the time to read this, I hope that it clarifies our previous questions.

[MilesCranmer]

Thanks, i see. Since you want a specific functional form, have you tried using template expression spec for this? https://ai.damtp.cam.ac.uk/pysr/examples/#template-expressions

[oisinkim1]

We looked into it a bit before, but found that learning a fixed template may be a bit too rigid for our project. However, we will look into it again at your suggestion - thanks very much for this.