Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Automatic Differentiation with Julia

blog.rogerluo.me

Post reply on HN
Print view View original

71–80 of 83 posts

Re: Automatic Differentiation with Julia

#71

Post by iguy »

geezerjay wrote: post #70
shele wrote: post #32

Earlier quoted context omitted.

Counting is slightly easier: if you have one object, it has slot number 1, and if you have one more object (meaning you have two objects) that second object has slot number 2. PS: I am joking here of course, but seriously, try counting things with your fingers starting with a fist, then one finger, then two.

Indexing isn't counting. It represents shifts from the reference position, which is the natural reference when dealing with contiguous objects. Everyone knows that the first floor of a building is right above the ground floor.

And even for buildings, we have two conventions in use. Plus a debate about whether the ground floor is really a floor, or whether the word "floor" naturally implies something elevated above the ground...

Re: Automatic Differentiation with Julia

#72

Post by pzone »

geezerjay wrote: post #70
shele wrote: post #32

Earlier quoted context omitted.

Counting is slightly easier: if you have one object, it has slot number 1, and if you have one more object (meaning you have two objects) that second object has slot number 2. PS: I am joking here of course, but seriously, try counting things with your fingers starting with a fist, then one finger, then two.

Indexing isn't counting. It represents shifts from the reference position, which is the natural reference when dealing with contiguous objects. Everyone knows that the first floor of a building is right above the ground floor.

"Indexing isn't counting" is not a fact; it is a language implementation choice inherited from C. It may be a useful choice for systems programming but it is not necessarily the best choice for every language.

Re: Automatic Differentiation with Julia

#73

Post by abecedarius »

aaaaaaaaaab wrote: post #62
abecedarius wrote: post #58

Earlier quoted context omitted.

It’s interesting though that the way calculus is classically taught does not make this obvious.

Hmmm, I don’t know. If you’re allowed skim over edge cases, the statement of the chain rule is pretty obvious: the composition of two linear functions is another linear function, with the coefficients multiplied.

I mean that knowing the chain rule does not, historically, imply seeing that automatic differentiation is possible and efficient.

Re: Automatic Differentiation with Julia

#74

Post by cbkeller »

one-more-minute wrote: post #4

You may like to take a look at Flux's implementation [1]; roughly the same idea but "professionalised" with performance work, tighter integration with the type system, nested AD and so on. It's a little less simple for that, of course, but is still under 500loc of fairly straightforward Julia code, and is generally a bit faster than PyTorch. The Julia world has done a lot of experimentation with AD and is converging…

Flux is awesome. One of the biggest advantages IMO is that kernels you can easily write yourself should be by default just as fast as what's built-in -- since it's all written in Julia and Julia itself is fast, without having to rely on C/C++/FORTRAN under the hood. As the Flux devs say:

"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!

Re: Automatic Differentiation with Julia

#75

Post by 3JPLW »

0-_-0 wrote: post #47
psychometry wrote: post #46

Earlier quoted context omitted.

That's so absurd I hope it's satire. Humans instinctively reason about iteration in terms of the natural numbers, not the semantic purity of the underlying abstract algebra.

It's not absurd at all. In situations where you need to do modulo arithmetic on array indices 1-based indexing forces you to shift the offset by 1.

Or, you know, just use the `mod1` function in those cases: https://docs.julialang.org/en/v1/base/math/index.html#Base.m... . Even more fun is that you can use the special `end` index to implement a stupid-simple circular index: `A[mod1(i, end)]` will always be in-bounds for integer `i`.

It's not a common case, though. Using inclusive ranges and 1-based indexing makes Julia's slicing syntax use first-class ranges that can behave like arrays themselves. You can do math on them. You can do all sorts of amazing things that make your life easier: https://julialang.org/blog/2016/02/iteration

Sometimes you want to count fenceposts, and sometimes you want the distance (e.g., offset) from the first post. Keep this imagery in mind and it's easy to do either in any language.

Re: Automatic Differentiation with Julia

#76

Post by ska »

ncfausti wrote: post #2

For those curious about Julia, I just found this: 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?

Julia is hardly the first (cf some common lisp environments, 20+ years ago). To really get near (say within 2x) of c you need some sort of type annotation or inference of course, and (more importantly) you have to structure your code such that this works, but it's quite do-able. Your code does tend to end up a bit c-like in those performance critical sections, but that's hardly surprising.

Re: Automatic Differentiation with Julia

#77

Post by taeric »

hpcjoe wrote: post #53
0-_-0 wrote: post #39

Earlier quoted context omitted.

My argument was that in situations where the difference between 0 and 1 based indexing makes a difference it's ususally 0-based indexing that leads to simpler code.

I guess I find it ironic then, that one of the most common programming errors, is of the "off-by-one" variety[1]. It is in part due to differences in convention and notation in various fields[2]. This isn't common in 1-based indexing languages. Very common in 0-based indexing languages[3]. If the 0-based indexing was objectively superior, wouldn't there be fewer instances of such bugs? [1] https://en.wikipedia.org/wi…

This implies that off by one is more common in zero based counting. Evidence? Your link didn't seem tob support that changing convention of indexing mattered. Rather, no longer indexing at all is what helped. (E.g., iterators.)

This fits my understanding. I've seen people do off by one just in the wild when counting how many posts/nails/etc are needed.

Re: Automatic Differentiation with Julia

#78

Post by gugagore »

ChrisRackauckas wrote: post #59
IngoBlechschmid wrote: post #44

Earlier quoted context omitted.

Thank you for the very insightful background. 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. :-)

Dual numbers don't have efficiency concerns in a language like Julia where the dispatching occurs at compile time, so basically you get the same compiled code as you'd want from source-to-source transformations. The issue though is that all functions have to be generic. Dual numbers is a very easy form to allow the user to add their own overloads though and take advantage of how the AD works: this is much harder with…

presumably, source-to-source "AD" could do some symbolic reasoning (whether any systems do, and whether it still counts as AD, I don't actually know). Specifically, I have in mind a source-to-source system that could look at `sqrt(x^2)` and produce a valid sub-gradient at x=0. With AD (whether forward-mode or reverse), you get NaN=Inf*0, because the gradient of x^2 is 0 and the gradient of `sqrt` is Inf.

Re: Automatic Differentiation with Julia

#79

Post by kxyvr »

abecedarius wrote: post #73
aaaaaaaaaab wrote: post #62

Earlier quoted context omitted.

Hmmm, I don’t know. If you’re allowed skim over edge cases, the statement of the chain rule is pretty obvious: the composition of two linear functions is another linear function, with the coefficients multiplied.

I mean that knowing the chain rule does not, historically, imply seeing that automatic differentiation is possible and efficient.

It's not and I also find it a bit frustrating when the default answer is just chain rule. For me, the key insights into how AD is derived are the following:

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 =  =  =  =
Here, * represents the Hilbert adjoint. Anyway, we get away with this because the derivatives are really linear operators, which we get from the total derivative.

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.

Re: Automatic Differentiation with Julia

#80

Post by byt143 »

ska wrote: post #76
ncfausti wrote: post #2

For those curious about Julia, I just found this: 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?

Julia is hardly the first (cf some common lisp environments, 20+ years ago). To really get near (say within 2x) of c you need some sort of type annotation or inference of course, and (more importantly) you have to structure your code such that this works, but it's quite do-able. Your code does tend to end up a bit c-like in those performance critical sections, but that's hardly surprising.

>Your code does tend to end up a bit c-like in those performance critical sections, but that's hardly surprising.

That isn't true. Closures, higher order functions and fused broadcast array expressions are all very fast except in some corner cases.

Post reply on HN