Automatic Differentiation with Julia
blog.rogerluo.me
blog.rogerluo.me
The Julia world has done a lot of experimentation with AD and is converging on some really cool things, so if you're interested in this field it's definitely worth a look.
[1]: https://github.com/FluxML/Flux.jl/blob/master/src/tracker/Tr...
"You could have written Flux. All of it, from LSTMs to GPU kernels, is straightforward Julia code. When in doubt, it’s well worth looking at the source. If you need something different, you can easily roll your own." http://fluxml.ai/Flux.jl/stable/
edit: and the automatic differentiation works on them too!
It uses a special sort of invented numbers which square to zero even though they are not themselves zero.
Here is one of the many tutorials on automatic differentiation: https://pizzaseminar.speicherleck.de/automatic-differentiati...
Fundamentally, automatic differentiation is the methodical application of the chain rule. Forward mode results from the application of the rules for directional derivatives. Reverse mode results from the total derivative. The reason that we have a reverse pass in reverse mode can be seen from this perspective. The directional derivative is `(f o g)'(x)dx = f'(g(x)) g'(x)`. Note, we compute `g(x)` before `f(g(x))` and the derivative `g'(x)` before `f'(g(x))`. Therefore, we can compute the derivatives as we compute the answer. If we want the gradient, which results from the total derivative, we have `grad (f o g)(x)` = `g'(x)* grad f(g(x))`. Although we still compute `g(x)` before `f(g(x))` during our computation, the gradient requires the computation of `grad f(g(x))` before the application of the adjoint operator `g'(x)*`. We do the evaluations on the first pass, and cache extra values, and then compute the gradient on a reverse pass because we need the adjoint of the total derivatives in the reverse order.
Or, at least that's my bias in how to derive things.
Besides efficiency concerns (which I don't have a clue about), a disadvantage of the point of view using dual numbers is that, to my knowledge, it can only be used to derive the forward mode of automatic differentiation. Still I take pleasure in appreciating the slightly mystic aura of the dual numbers. :-)
But yes, dual numbers only do forward mode. However, slightly related is tracker types, like ReverseDiff.jl or Flux.jl's Tracker, where you essentially push a type forward through the code similarly to a dual number, and use this to build the computational graph which you then run backwards with the chain rule.
As magical as the chain rule of differentiation.
1. There is a fundamental difference between normed spaces and inner product spaces and this affects what algorithms we can derive. Specifically, the forward mode corresponds to a version of the chain rule that only requires a normed space and not an inner product space. If we assume that we have an inner product, then we can apply the Reisz representation theorem. This is important because it means that there's a concrete element in the space that corresponds to the derivative. This is precisely the gradient. Further, we have a concrete way of finding this element. Because we have a (complete) inner product space, we have a Hilbert adjoint. The gradient, and ultimately reverse mode, can be calculated by combining the chain rule with the Hilbert adjoint to obtain the gradient. Specifically,
(f o g)'(x) dx = f'(g(x))g'(x) dx = (f'(g(x))g'(x) dx) 1 = <f'(g(x))g'(x)dx,1> = <g'(x)dx,f'(g(x))* 1> = <dx,g'(x)*f'(g(x))*1> = <dx,g'(x)* grad f(g(x))>
2. Eventually, we feed the the gradients `grad f(g(x))` into the adjoint of `g'(x)`. However, we it turns out that we can delay further delaying sending the values of the adjoint of `g'(x)` into its parent by accumulating all of the gradient information being fed to it first. Essentially, this means that we can follow a computational graph and accumulate all of the intermediate derivative information before moving on. This means that we can traverse the graph a single time in reverse mode, which is efficient. How we traverse this graph corresponds to a topological sort of the graph. This can be generated at compile time using what's called a tape. This may or may not be more efficient modulo a bunch of reasons, which aren't all that important right now.
Anyway, this is more to say that automatic differentiation is not an obvious result from basic calculus. At least not to me. For me, it required knowledge of real and functional analysis, graph theory, and knowledge of programming languages. It's not impossible to learn, but it's not trivial in my opinion.
Is this really used in practice?
It seems to me that most of the AD frameworks used for deep learning implement the backward function that returns the jacobian for every initial function, and then chain those backward functions
From this it should be clear why machine learning uses reverse-mode.
On the other hand, forward-mode is better for e.g. calculating the tangent of a high-dimensional curve (i.e. R -> R^n).
Though I have never seen AD frameworks used in the production contexts for neural networks/backpropagation. As you say, the code for this seems to be mostly handrolled. Please take this negative statement with a grain of salt, I don't actually work in machine learning.
https://www.infoworld.com/article/3284380/data-science/what-...
Close to C speed in a dynamic language? Seems pretty great on paper. Is this generally the case?
function test1(n)
x = 0
for i = 1:n
if i == 10
x = x + 0.1
else
x = x + 1
end
end
return x
end
The following code is type stable:
function test2(n)
x = 0.0
for i = 1:n
if i == 10
x = x + 0.1
else
x = x + 1.0
end
end
return x
end
julia> @btime test1(10^5)
147.427 μs (0 allocations: 0 bytes)
99999.1
julia> @btime test2(10^5)
88.472 μs (0 allocations: 0 bytes)
99999.1
The performance is awesome, the REPL is super great as well. There's libraries that I'm itching to try out as soon as I've got a relevant project (Flux ML being the top of that list).
There's been a lot of situations in using it where I've just gone "this is everything I needed/wanted": the performance, the language features and API design, etc.
Plus there's a lot of very interesting things going on with the language and ecosystem, I definitely recommend trying it out.
function foo(x)
#do something
endthe catch is, the first time you run a function there is often a noticeable compile time. but it’s cached after that.
other problems with Julia include a somewhat immature/unfinished set of libraries, in part because the language was constantly changing underneath people.
but now that 1.0 has been released, the language will be stable for a long time and you can expect that to improve quickly.
good language! it gets a lot of hype on HN but that’s because it is actually very nice.
That isn't true. Closures, higher order functions and fused broadcast array expressions are all very fast except in some corner cases.
Anyway, this isn't really Julia specific, and I haven't tried with Julia recently so I may be wrong :)