Function Decomposition

The problem:

Given a set of base functions, a composite function is built and the number of functions used is returned and a set of constraints that the generated function fulfills is returned. Find a function with equal or lesser complexity that also fulfills the constraints.

Base functions can take any number of arguments and returns one value. All values are of the same type.

Example

Base Functions ADD(a, b), MUL(a, b), GT(a, b)

where GT returns 1 if a>b and 0 otherwise.

But what if base functions include binary operations (which are non-linear).

Proof Of Impossibility

If this were generally possible, it would be possible to reverse engineer a crypto hash.

Possible Constraints

Base Inversion

Require that for each base function an inverse function is also supplied. The inverse is not (necessarily) part of the set.

 F(a,b) = c → F'1(a,c) = b and F'2(c,b) = a

However, GT doesn't have an inverse.

It may work to only require an inverse over a set, which can be filled for GT.

Possible Sub-problems

Solve for Constants

From the original problem, let's say I return the function tree with no values filled in. Each argument is either going to be a constant or a top level argument. How to solve the values?

Something like back propagation may work here. proportionally change each value based on how much it's contributing to the error. This may require some sort of derivative. And it won't work if the out put of a function is chaotic.

It may also help to have linear approximations of non-linear functions. For instance GT could be approximated by a sigmoid function which is progressively tuned steeper and steeper.

Possible Solutions

Genetic

Lots of promise, but how do you measure fitness? You could do RMSE at first, but then change the weight of each constraint based on how often it's met.

I did a bit on this a long time ago, but you need genetic markers. Merging organisms from different evolutionary lines is very tricky.

Topological

I know very little about this. For a base set of functions look for different topologies that can be created. This builds up a library. Then the solution can be decomposed into the topologies.

For instance, addition with an argument always shifts the graph, but the topology is smooth. Multiplication adds a slant and GT adds a cliff.

Discrete Function

Any discrete set of points can assumed to be continuous. Start by generating a continuous function, then looking for the steepest slope and break it into dis-continuous segments there.

Discrete Table

Create a table and start by combining cells.

Possibly look at Karnaugh maps.