Second Order Optimization - The Math of Intelligence #2

Key Takeaways

[Music] hello world it's SJ and let's talk about [Music] optimization there are thousands of languages spoken across the world each one unique its ability to represent Concepts and convey ideas but there is one language that is shared by All Humans regardless of where you come from mathematics no matter your culture or your age you possess the ability to understand this language of numbers that connects us all across continents and time like all languages fluency requires practice but unlike any other language the more fluent you become in math the more Unstoppable you'll be in anything you want to do in life math is happening all around us to a degree that most people don't realize we can think of everything as a set of variables as metrics and there exists relations between all of these variables in math we call these relations functions it's our way of representing a set of patterns a mapping a relationship between many variables variables no matter what machine learning model we use no matter what data set we use the goal of machine learning is to optimize for an objective and by doing so we are approximating a function the process of optimization helps us iteratively discover the functions hidden in the depths of data last week we talked about a popular optimization technique called gradient descent this can be broken down in into a fstep process first we Define some machine learning model with a set of initial weight values these act as the coefficients of the function that the model represents the mapping between input data and output predictions these values are naive we have no idea what they should actually be but we're trying to discover the optimal ones we'll Define an error function and when we plot the graph of the relationship between all the possible error values and all the possible weight values for our function we'll see that there exists a valley a Minima we'll use our error to help us compute the partial derivative with respect to each weight value we have and this gives us our gradient the gradient represents the change in the error when the weights are changed by a very small value Val from their original value we use the gradient to update the values of our weights in a direction such that the error is minimized iteratively coming closer and closer to the Minima of the function we step our solution in the negative direction of the gradient repeatedly when we reach it we have learned the optimal weight values for our model where our gradient is equal to zero our model will then be able to make predictions for input data it's never seen before most optimization problems can be solved using gradient descent and its variance they all fall into a category called first order optimization methods we call them first order because they only require us to compute the first derivative but there's another class of techniques that aren't as widely used called second order optimization methods that require us to compute the second derivative the first derivative tells us if the function is increasing or decreasing at a certain point and the second derivative tells us if the first derivative is increasing or decreasing which hints at its curvature first order methods provide us with a line that is tangential to a point on an air surface and second order methods provide us with a quadratic surface that kisses the curvature of the error surface H get a room you two the advantage then of second order methods is that they don't ignore the curvature of the eror surface and in terms of stepwise performance they are better let's look at a popular second order optimization technique called Newton's method named after the dude who invented calculus whose name [Music] was there are actually two versions of Newton's method the first version is for find the roots of a polinomial all those points where it intersects with the xais so if you threw a ball and recorded its trajectory finding the root of the equation would tell you exactly what time it hits the ground the second version is for optimization and it's what we use in machine learning but let's code the root finding version first to develop some basic intuition hey you must be Eloise ofl p and you must be S the data scientist yeah hi good to meet you good to meet you too any Revelations on how to predict our neuron network not yet this is going to be quite a challenge we've got to perform anomaly detection on a 500 tab data set I was thinking we just use Newton's method to perform logistic regression first to see if we can predict particles nun method yeah it's a form of second order optimization I already built a prototype it's been training for the past few hours I'm impressed machine learner you should be let's say we have a function F ofx and some initial guessed solution Newton's method says that we first find the slope of the tangent line at our guess point then find the point at which the tangent line intersects the xaxis we'll use that point to find its projection in the original function then we iterate again from our first step this time replacing our first point with this one we keep iterating and eventually we'll stop when our current value X is less than or equal to a threshold so that's the root finding version of Newton's method where we're trying to find where the function equals zero but in the optimization version we're trying to find where the derivative of the function equals z it's minimum at a high level given a random starting location we construct a quadratic approximation to the objective function that matches the first and second derivative values at the that point and then we minimize that quadratic function instead of the original function the minimizer of the quadratic function is used as the starting point in the next step and we repeat this process iteratively okay so let's go over two cases of Newton's method for optimization to learn more a 1D case and a 2d case in the first case we've got a 1dimensional function we can obtain a quadratic approximation at a given point of the function using what's called a tailor series expansion neglecting terms of order three or higher a tailor series is a representation of a function as an infinite sum of terms that are calculated from the values of the function's derivatives at a single point it was invented by an English mathematician named Brooke Taylor Swift just kidding so we take the second order tailor series for our initial point x and minimize it by finding the first derivative and second derivative and equating them to zero in order to find the minimum x value we iterate this process in the second case let's say we've got a function of multiple Dimensions we can find the minimum of it using the same approach except for two changes we replace the first derivatives with a gradient and the second derivatives with a hessen a hessen is a matrix of the second order partial derivatives of a scalar and it describes the local curvature of a multivariable function check this out derivatives help us compute gradients which we can represent using a Jacobian matrix for first order optimization and we can use the hesen for second order optimization these are four of the five derivative operators used in all of calculus they're the ways that we organize and represent change numerically so when should you use a second order method first order methods are usually less computationally expensive to compute and less time expensive converging pretty fast on large data sets second order methods are faster when the second derivative is known and easy to compute but the second derivative is often intractable to compute requiring lots of computation for certain problems gradient descent can get stuck along paths of slow convergence around saddle points whereas second order methods won't trying out different optimization techniques for your specific problem is the best way to see what works best here are the key points to remember from this video first order optimization techniques use the first derivative of a function to minimize it second order optimization techniques use a second derivative the Jacobian is a matrix of first partial derivatives and the hessen is a matrix of second partial derivatives and Newton's method is a popular second order optimization technique that can sometimes outperform gradient descent last week's coding challenge winner is Alberto gares Alberto used gradient descent to find the line of best fit his Jupiter notebook is insanely detailed you could learn gradient descent just from reading it alone very well thought out that was dope Alberto wizard of the week and the runner up is Ivan gusev who implemented gradient descent from scratch for polinomial of any order this week's challenge is to implement Newton's method for optimizations from scratch details are in the read me post your GitHub Link in the comments and winners will be announced next week please subscribe for more programming videos and for now I've got to invent the six derivative so thanks for watching