Automatic inverse of a function?

Hey,

I do have a function that makes a heavy computation in Julia, from \mathbb R^n to \mathbb R^m. It uses loops, multiplications, additions, divisions, substractions, powers and exp/log.

I am looking to inverse the function. I can carry out the inverse when the number of parameters and outputs is small, but when it gets larger i cannot by hand, and the combinatorics are hard.

Is there somewhere a software that could carry out the inversion for me ? I am not very informed about what kind of methods exists, which makes searching for implementation harder.But since Julia has awsome automatic differentation things, my guess is that someone came with this problem before me :slight_smile:

Unfortunately, this is basically impossible. The problem is that most functions (eg f(a,b)=a+b) are not invertible.

4 Likes

I hear you, yes. subpieces of the algorithm might not be invertibles. But what if the global algorithm is, indeed, invertible ? I mean, f(a,b) = (a+b, exp(a+2b)) is invertible, and you could get more creative.

Maybe you can use:

3 Likes

It seems like this is not what i want: it restores the input of a function (which is amazing), but does not compute the inverse operation to be applicable to other arguments.

How do you know that the complete algorithm is invertible, though, if you can’t see that “by hand”? You would need some algorithmic way to determine that.

There is very nice work by @zennatavares on parametric inversion.

You can also try IntervalConstraintProgramming.jl, which you can think of as giving a set-valued inverse of a function evaluated over a given set, which is all that you can hope for in general.

1 Like

If you’re looking to solve for a particular input then @dpsanders interval constraint programming is a good way to go. If that doesn’t work you could try relaxing the problem.

If you’re trying to actually invert the function there are a few options.

Sounds like your example is “partially” invertible. See this paper https://dl.acm.org/doi/10.1145/3409000

I’m not sure they have a tool though.

Finally I’m looking for benchmarks to try parametric inversion on so if you can send me an example I can take a look.

2 Likes

For a very simple proof that automatic inversion is generally impossible (even for invertible functions), consider that RSA encryption is invertible. If you can invert this automatically you will get several million dollars and a job at any tech company you want.

9 Likes

I agree in general, but isn’t the idea that it is possible to modify the function of interest such that it is invertible by returning extra information about internal states?

E.g. instead of doing \mathbb{R}\times\mathbb{R}\overset{f}{\rightarrow}\mathbb{R} you do \mathbb{R}\times\mathbb{R}\overset{g}{\rightarrow}\mathbb{R}\times\mathbb{R}

f(a,b) = a+b

vs

g(a,b) = (a+b, b)

For the RSA example, I would think that you could invert it IF you had access to intermediate states. Which obviously you don’t have. But you could write it so it was available.

1 Like

I don’t understand the original question, but what you usually do to invert a differentiable function f is to find a zero of g(x) = f(x) - y, eg with Newton method.

2 Likes

You are totaly right. My OP was silly.

This sort of thing can be doable, by writing a system based around a collection of invertible primitives.

As a simple example:

f(a, b) = (a + b, b)
f_inv(a, b) = (a - b, b)

g(a, b) = (a * b, b)
g_inv(a, b) = (a / b, b)

function myfunction(a, b)
    for j = 1:100
        a, b = f(a, b)
        if j in (7, 19)
            a, b = b, a
        end
        if j in (5, 32)
            a, b = g(a, b)
        end
    end
    return a, b
end

function myfunction_inv(a, b)
    for j = 100:-1:1
        if j in (5, 32)
            a, b = g_inv(a, b)
        end
        if j in (7, 19)
            a, b = b, a
        end
        a, b = f_inv(a, b)
    end
    return a, b
end

With a little clever engineering you can make it so that you don’t have to write myfunction_inv by hand (and have it autogenerated based on the invertible primitives you provide). Doing so would be very similar to writing an autodifferentiation system (just that you’re using invertible primitives rather than differentiable primitives) so the same sorts of methods apply: e.g. source-to-source transformations like Zygote; or by dynamically building up a computation graph like in PyTorch.

2 Likes

Or, has been done. Using the package I linked above:

julia> @i f(a, b) = a += b

julia> f(3, 5)
(8, 5)

julia> (~f)(8, 5)  # inverse
(3, 5)

julia> @i g(a, b) = a *= b

julia> g(7, 9)
ERROR: MethodError: no method matching (::MulEq{typeof(identity)})(::Int64, ::Int64)
Closest candidates are:
  (::MulEq{typeof(identity)})(::ULogarithmic, ::Real) at /Users/me/.julia/packages/NiLang/5Z72s/src/ulog.jl:13

Note that your g isn’t invertible, because b might be zero, so it won’t allow it.

1 Like

It is not quite the same thing, as your example show: You have to compute f(3,5) before being able to compute ~f(f(3,5)). You cannot compute directly ~f(x,y) for any x,y

Sure, I agree this isn’t what everyone means by inverse, at all times. It won’t crack RSA for you, but it is a working implementation of precisely the kind of reverse computation I was quoting.

If you don’t find a symbolic solution either by hand or by using a software (sympy, maple, mathematica, …),
you can always consider the numerical approach:
given Y= f(X) where f is your julia function and your Y₀,
search the solutions of f(X)-Y₀ = 0 with a numerical algorithm every time you want the “inverse”.
This problem could also be formulated as a nonlinear minimization of (f(X)-Y₀)², see NLopt.jl and JuMP.jl for the software.

1 Like

Very nice! Or even better, since you can translate the inverse problem to an optimization problem, machine learning techniques are ready for the work. lol.