Automatic Differentiation in Machine Learning: A Survey (2018) [pdf] • Hacker News Board

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#31

Post by adamnemecek » Fri, Mar 08, 2019, 1:09 AM UTC

throwawaymath wrote: post #26

adamnemecek wrote: post #21

Earlier quoted context omitted.

> I think characterizing duality in this way is kind of superfluous, It's an analysis done out of necessity. These dualities might not be a 100% in every case, but maybe I care about the ways in which they are similar. > because the only way all those meanings of duality are the same is in the most abstract sense of the word. So is a monad. Do you think that in the future, the level of abstraction in mathematics is g…

It will increase, which I guess is sort of my point. We already know there's a lot of abstraction. If these things are only alike semantically (two pairs of dual things can be completely unrelated), what does it gain you to point out they've everywhere? I don't mean to be obtuse, but it strikes me as saying that a city is full of concrete.

You can think of it as a really nice intermediate language.

It might be hard to build a computer system that lets you reason about both probability and say quantum mechanics.

However it might be easier to build a system that phrases a probabilistic problem in terms of duality and then solves it.

Like why should each of this have it's own foundation when there's one that captures a lot of them?

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#32

Post by adamnemecek » Fri, Mar 08, 2019, 1:19 AM UTC

throwawaymath wrote: post #27

adamnemecek wrote: post #24

Earlier quoted context omitted.

https://math.stackexchange.com/questions/2593296/why-is-prob... Automatic differentiation is something that you get for free if you use dual numbers. Lie theory describes the relationship between the discrete and continuous spaces. Probability has this deep connection to Lie groups. To give you some intuition (and I'm really rephrasing the stackexchange post above), the only way you can only measure randomness (or ge…

Wait, what? > Automatic differentiation is something that you get for free if you use dual numbers. Lie theory describes the relationship between the discrete and continuous spaces. Probability has this deep connection to Lie groups. This...doesn't follow. Probability has a connection to Lie groups because it's fundamentally analytic ("continuous"). But you haven't explained how you make the connection to the dual nu…

> Probability has a connection to Lie groups because it's fundamentally analytic ("continuous"). But you haven't explained how you make the connection to the dual numbers.

Are you familiar with Chu spaces?

> But just because you're working with continuous spaces doesn't mean you've engaged the duals. It generally means you're using the reals.

They are not just continous spaces, it's a pair of a discrete space and a continous space that are directly connected. You never work only with one of them at once. You manipulate things in smooth space to solve things in the discrete space and vice versa.

> This gets to the heart of what I'm saying - if I wanted to be flippant I could have said the real numbers, or continuity, or analysis, etc are at the heart of so many distinct subfields of mathematics. It doesn't mean quite a lot.

Analysis is too general and also much higher conceptually. Also, you need to be looking at constructive mathematics to really capture duality. Also analysis is unusuable for a lot of problems that duality is useful for.

For example the Rust borrow checker is based on linear logic, a logic that reifies the concept of duality. No one has ever used analysis to build a compiler.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#33

Post by adamnemecek » Fri, Mar 08, 2019, 1:20 AM UTC

throwawaymath wrote: post #28

adamnemecek wrote: post #22

Earlier quoted context omitted.

> For example, the way dual numbers are used to extend the reals for automatic differentiation doesn't have a deep connection to duality in vector spaces. They don't. Because certain operations are hard to reason about in linear spaces. Such as optimization. Don't get me wrong, I'm not shitting on vector spaces. All I'm saying is that some problems are hard to do in vector spaces, that are easy in the smooth spaces a…

Quite a bit of optimization is easy to reason about in linear algebra. Take linear and mixed integer programming, for example. And convex optimization subsumes linear optimization in general. There is a lot of nonlinear optimization, but I can assure you with extremely high confidence that the common thread you're seeing here isn't duality, but more abstractly linearity. Likewise cyclic things show up all the time in…

They show up separately but not in tandem.

The canonical example is robotic motion and the reason why Lie theory is used there. You have very discrete states (positions) that you want to interpolate between smoothly.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#34

Post by wenc » Fri, Mar 08, 2019, 1:23 AM UTC

adamnemecek wrote: post #30

throwawaymath wrote: post #29

Earlier quoted context omitted.

Unless I'm severely misunderstanding you, a discrete set (or function) cannot be a dual of a continuous set (or function). If nothing else, the former is countable and the latter is uncountable; there can be no isomorphism between the two.

Unless I'm severely misunderstanding you, a discrete set (or function) cannot be a dual of a continuous set (or function). If nothing else, the former is countable and the latter is uncountable; there can be no isomorphism between the two. There is. Discrete samples are samples of the continuous space. In order to capture the continous space, you only really need to capture a particular set of samples that you then i…

> Imagine a polynomial (in the smooth space). You can capture a particular set of points that uniquely determines the polynomial. In some circumstances you can use these samples to reconstruct the original polynomial by interpolating between any of the two points.

This is not duality though and you do lose information.

For instance let’s say one has a cubic polynomial and one samples 5 points from it and stores those points. If one didn’t know the original order was cubic, and if one tried to interpolate over the 5 points to fit a quintic, that would be an incorrect reconstruction.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#35

Post by throwawaymath » Fri, Mar 08, 2019, 1:26 AM UTC

adamnemecek wrote: post #30

throwawaymath wrote: post #29

Earlier quoted context omitted.

Unless I'm severely misunderstanding you, a discrete set (or function) cannot be a dual of a continuous set (or function). If nothing else, the former is countable and the latter is uncountable; there can be no isomorphism between the two.

Unless I'm severely misunderstanding you, a discrete set (or function) cannot be a dual of a continuous set (or function). If nothing else, the former is countable and the latter is uncountable; there can be no isomorphism between the two. There is. Discrete samples are samples of the continuous space. In order to capture the continous space, you only really need to capture a particular set of samples that you then i…

Okay, I think I understand what you're getting at. But if you've taken a set of points from a continuous set (like an interval on the reals) and you can put those in bijection with a discrete set, then by definition your subset of the continuous set isn't continuous. It must be discrete.

More succinctly, you actually can't draw an isomorphism between discrete and continuous spaces without losing information from the continuous space.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#36

Post by adamnemecek » Fri, Mar 08, 2019, 1:31 AM UTC

wenc wrote: post #25

adamnemecek wrote: post #17

Earlier quoted context omitted.

There are two types of spaces, discrete and continuous. These are in a dual relationship. Duality is the isomorphism between these two. For example, for humans, it's easier to reason about discrete spaces. However a lot of things simply cannot be done that way. Think of anything that is tangential (pun intended) to Lie theory. In the context of Lie theory, you have the discrete group and the continuous algebra (the g…

I’m not sure. I’m not entirely convinced that discrete and continuous spaces are dual spaces. They are connected, but they are not duals. Same with sampling vs continuous. One cannot interchange the order of the composing morphisms while preserving the properties of the original. The sampled object cannot reconstruct the continuous object in all situations due to effects like aliasing. In optimization, the concept of…

Look into Chu spaces.

> One cannot interchange the order of the composing morphisms while preserving the properties of the original.

Good observation one really can't but that was never a hard requirement, right? Ordering becomes actually more interesting because you can have interesting properties like anti-commutativity (https://en.wikipedia.org/wiki/Anticommutativity) which is a lot more useful than commutativity. Lie groups are anti-commutative groups btw.

> In optimization, the concept of duality is also a much stronger idea: the primal and the dual of a problem are opposing views of the same problem that correspond exactly (not approximately) in their dual properties.

My view is more general. The difference between these spaces lies in the idea of choice and in the idea of adversarial choice. You are correct, they are opposing view, like two players playing a game.

I control my moves. I do not have control over my opponents players moves, however I do have knowledge about my opponent's potential moves. Therefore I can do some sort of min-max optimization to figure out my optimal play given my situation and knowing my opponent's options.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#37

Post by adamnemecek » Fri, Mar 08, 2019, 1:34 AM UTC

wenc wrote: post #34

adamnemecek wrote: post #30

Earlier quoted context omitted.

Unless I'm severely misunderstanding you, a discrete set (or function) cannot be a dual of a continuous set (or function). If nothing else, the former is countable and the latter is uncountable; there can be no isomorphism between the two. There is. Discrete samples are samples of the continuous space. In order to capture the continous space, you only really need to capture a particular set of samples that you then i…

> Imagine a polynomial (in the smooth space). You can capture a particular set of points that uniquely determines the polynomial. In some circumstances you can use these samples to reconstruct the original polynomial by interpolating between any of the two points. This is not duality though and you do lose information. For instance let’s say one has a cubic polynomial and one samples 5 points from it and stores those…

You don't lose information if you pick your points correctly (you store only the extrema). In the cubic case, you need the two extrema (one minimum and one maximum and you need to know whether each extremum is a min or max) and then interpolate between them.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#38

Post by adamnemecek » Fri, Mar 08, 2019, 1:40 AM UTC

throwawaymath wrote: post #35

adamnemecek wrote: post #30

Earlier quoted context omitted.

Unless I'm severely misunderstanding you, a discrete set (or function) cannot be a dual of a continuous set (or function). If nothing else, the former is countable and the latter is uncountable; there can be no isomorphism between the two. There is. Discrete samples are samples of the continuous space. In order to capture the continous space, you only really need to capture a particular set of samples that you then i…

Okay, I think I understand what you're getting at. But if you've taken a set of points from a continuous set (like an interval on the reals) and you can put those in bijection with a discrete set, then by definition your subset of the continuous set isn't continuous. It must be discrete. More succinctly, you actually can't draw an isomorphism between discrete and continuous spaces without losing information from the…

Here's the thing, your description of the continuous set is already discretized. If we say an interval 4-6 we have captured the continuous space using only two numbers.

I know that this is a silly argument in some sense but this is something that you do naturally that you don't even think about it.

Do you see what I'm getting at? You capture extrema in the discrete space and the interpolate in the smooth space to recreate the smooth curve.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#39

Post by cs702 » Fri, Mar 08, 2019, 2:52 AM UTC

I'm trembling with excitement at the prospect that easy-to-use high-performance automatic differentiation looks likely to become a "must have" capability for more and more computer languages. It's going to become easier and easier to specify objective functions and have the computer optimize programs for a wider range of application.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#40

Post by wenc » Fri, Mar 08, 2019, 3:08 AM UTC

adamnemecek wrote: post #37

wenc wrote: post #34

Earlier quoted context omitted.

> Imagine a polynomial (in the smooth space). You can capture a particular set of points that uniquely determines the polynomial. In some circumstances you can use these samples to reconstruct the original polynomial by interpolating between any of the two points. This is not duality though and you do lose information. For instance let’s say one has a cubic polynomial and one samples 5 points from it and stores those…

You don't lose information if you pick your points correctly (you store only the extrema). In the cubic case, you need the two extrema (one minimum and one maximum and you need to know whether each extremum is a min or max) and then interpolate between them.

Unfortunately this is incorrect. Extrema do not always exist (consider y=x^3) and they do not uniquely define a polynomial (y=x^2 and y=x^4 both have minima at x=0).