5 ms·

I'm not an AI expert, but I'm decent with computers. Could anyone explain what is this about?

cool_username 9y ago
Assuming you want to understand a bit more about saddle points: http://graemebell.net/pubs/taros05-bl-embedded-preprint.pdf http://graemebell.net/pubs/taros05-bl-embedded-preprint.pdf Section 3 has some low dimensional examples with simulated robots and donkeys. Take a look at Figure 3 with the donkey. Burridan's Ass is a classic philosophical example where a saddle point prevents success. Basically, place a donkey between two piles of food in front of it that are equally attractive. The donkey moves in whatever direction will take it towards food. So at first, it can move forward (reducing its distance to both piles of food) up to a point, but then it gets stuck because both piles are equally attractive. It can't move forward or back either because that moves it away from both piles of food. There is nothing to 'push' the donkey to the left or the right. ('push'/hunger being analogous to 'following the gradient' for neural net training or robot navigation here) If you add a bit of a random wobble, it's enough to free the donkey from its indecision and make one of the piles slightly closer. But things are more complex than that especially as you move into higher-dimensions of space beyond 2D and 3D [as you see when training neural nets, for example]. And a random wobble is not enough to guarantee success. It may have consequences for physical devices (your robot shakes around and falls over), it may have consequences for realism and immersion in games/simulations (the AI monster stops and does a mad shake for a minute to creep its way around a rock to get you, rather than moving smoothly/normally around the rock)
- wyldfire 9y ago
  > There is nothing to 'push' the donkey to the left or the right. It's funny -- I can imagine a real human (perhaps a particularly anxious one) stall in indecision wondering which similar-looking pile held more value or which was closer. Fear of wasted time would likely force them to make a decision. And once they committed to a pile they would likely continue until/unless they discovered new information. What if the agent had a list of waypoints and only re-evaluated the list every N ticks or when the horizon reveals something new? I know very little about AI so I have no idea if this is out of scope or could possibly apply.
sumitgt 9y ago
I'm not an AI expert either, but let me give this a try. I assume you are vaguely familiar with gradient descent. In gradient descent, we are basically trying to find the sweet spot where the value of a function is minimized. We do this by calculating the derivative of the function at a certain point and then use it to take small steps in the direction where we believe the function will have a lower value. Gradient descent usually suffers from a problem where the algorithm gets stuck in local minimas if the function is not convex in shape. However, when people use gradient descent to optimize functions with a very large number of parameters (as is the case in Deep Learning), another problem surfaces called saddle points. Imagine a 3 dimensional plot of the function at different values of its parameters (in reality the plot will be multi-dimensional). Now on this plot, there will be many regions where the derivative of the components defining the surface become zero. This messes with our plan to use derivatives to find the direction in which to move. So we need to come up with strategies to escape saddle points during the gradient descent process.
- unityByFreedom 9y ago
  Here's a section from the fast.ai course where Jeremy discusses learning rates and saddle points (about 2-3 minutes in) https://youtu.be/V2h3IOBDvrA?t=26m5s https://youtu.be/V2h3IOBDvrA?t=26m5s
- whatidonteven 9y ago
  How can a non-linear function even be convex in shape? I assume you mean the whole volume below or above the function and not just the function's surface itself? Also, what about the case where the function isn't continuous or where it's not defined everywhere (the surface has holes)?
  - blt 9y ago
    one definition of a convex function is that its epigraph { (x, y) : f(x) <= y } is a convex set. Another is that the line segment between two points on the graph lies above the graph, i.e. (1 - t) f(x) + t f(y) >= f((1 - t) x + t y) for all 0 <= t <= 1 known as Jensen's inequality. Convex function must be defined on a convex domain (no holes) and continuous at everywhere except the boundary of the domain.
chestervonwinch 9y ago
You're in the middle of a saddle shape (see the figure [1]). This is bad because you could be lower (the goal is to be at the lowest point). Moreover, getting out is apparently slow / difficult. The authors explain "how to escape" the saddle point in an efficient way. [1]: http://bair.berkeley.edu/blog/assets/saddle_eff/strictsaddle.png http://bair.berkeley.edu/blog/assets/saddle_eff/strictsaddle...

Assuming you want to understand a bit more about saddle points: http://graemebell.net/pubs/taros05-bl-embedded-preprint.pdf http://graemebell.net/pubs/taros05-bl-embedded-preprint.pdf Section 3 has some low dimensional examples with simulated robots and donkeys. Take a look at Figure 3 with the donkey. Burridan's Ass is a classic philosophical example where a saddle point prevents success. Basically, place a donkey between two piles of food in front of it that are equally attractive. The donkey moves in whatever direction will take it towards food. So at first, it can move forward (reducing its distance to both piles of food) up to a point, but then it gets stuck because both piles are equally attractive. It can't move forward or back either because that moves it away from both piles of food. There is nothing to 'push' the donkey to the left or the right. ('push'/hunger being analogous to 'following the gradient' for neural net training or robot navigation here) If you add a bit of a random wobble, it's enough to free the donkey from its indecision and make one of the piles slightly closer. But things are more complex than that especially as you move into higher-dimensions of space beyond 2D and 3D [as you see when training neural nets, for example]. And a random wobble is not enough to guarantee success. It may have consequences for physical devices (your robot shakes around and falls over), it may have consequences for realism and immersion in games/simulations (the AI monster stops and does a mad shake for a minute to creep its way around a rock to get you, rather than moving smoothly/normally around the rock)

wyldfire 9y ago
> There is nothing to 'push' the donkey to the left or the right. It's funny -- I can imagine a real human (perhaps a particularly anxious one) stall in indecision wondering which similar-looking pile held more value or which was closer. Fear of wasted time would likely force them to make a decision. And once they committed to a pile they would likely continue until/unless they discovered new information. What if the agent had a list of waypoints and only re-evaluated the list every N ticks or when the horizon reveals something new? I know very little about AI so I have no idea if this is out of scope or could possibly apply.

sumitgt 9y ago

I'm not an AI expert either, but let me give this a try. I assume you are vaguely familiar with gradient descent. In gradient descent, we are basically trying to find the sweet spot where the value of a function is minimized. We do this by calculating the derivative of the function at a certain point and then use it to take small steps in the direction where we believe the function will have a lower value. Gradient descent usually suffers from a problem where the algorithm gets stuck in local minimas if the function is not convex in shape. However, when people use gradient descent to optimize functions with a very large number of parameters (as is the case in Deep Learning), another problem surfaces called saddle points. Imagine a 3 dimensional plot of the function at different values of its parameters (in reality the plot will be multi-dimensional). Now on this plot, there will be many regions where the derivative of the components defining the surface become zero. This messes with our plan to use derivatives to find the direction in which to move. So we need to come up with strategies to escape saddle points during the gradient descent process.

unityByFreedom 9y ago
Here's a section from the fast.ai course where Jeremy discusses learning rates and saddle points (about 2-3 minutes in) https://youtu.be/V2h3IOBDvrA?t=26m5s https://youtu.be/V2h3IOBDvrA?t=26m5s
whatidonteven 9y ago
How can a non-linear function even be convex in shape? I assume you mean the whole volume below or above the function and not just the function's surface itself? Also, what about the case where the function isn't continuous or where it's not defined everywhere (the surface has holes)?
- blt 9y ago
  one definition of a convex function is that its epigraph { (x, y) : f(x) <= y } is a convex set. Another is that the line segment between two points on the graph lies above the graph, i.e. (1 - t) f(x) + t f(y) >= f((1 - t) x + t y) for all 0 <= t <= 1 known as Jensen's inequality. Convex function must be defined on a convex domain (no holes) and continuous at everywhere except the boundary of the domain.

chestervonwinch 9y ago

You're in the middle of a saddle shape (see the figure [1]). This is bad because you could be lower (the goal is to be at the lowest point). Moreover, getting out is apparently slow / difficult. The authors explain "how to escape" the saddle point in an efficient way. [1]: http://bair.berkeley.edu/blog/assets/saddle_eff/strictsaddle.png http://bair.berkeley.edu/blog/assets/saddle_eff/strictsaddle...