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
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
