6 ms·

So I have a question somewhat related to this that I never knew where/who to ask (well actually I asked a few mathematicians at a university I work with whose a

by roel_v 8y ago

So I have a question somewhat related to this that I never knew where/who to ask (well actually I asked a few mathematicians at a university I work with whose answers I couldn't understand - their answers were almost as impenetrable as the Wikipedia page, and some engineering scientists who I thought would be more into 'applied math' but they didn't know. So I'm hoping some data science people reading this would better understand where I'm coming from, and be able to explain at my primitive math skills level). So, some time ago I contracted out writing some code for fitting a logistic regression onto a given set of observations. There were some specific requirements, but I think I should have been able to piece something myself together using mainstream LA libraries; some of them even hint at 'you could fit a logistic regression using these functions' but no complete examples. But I didn't understand well enough so I contracted it out. The woman who ended up writing the code used a 'Hessian' matrix to do so (she actually wrote two functions doing the same thing, one used this Hessian approach - I think the idea was that it would be faster but there wasn't a lot of time and it never got tweaked enough to make a difference). So my question - is there a layman's explanation for what a Hessian matrix is, and how it applies to fitting a logistic model? Also (with an eye to the future of my project), does it have applications for non-linear regressions? Alternatively, are there any books where this is covered? I have most standard stats/applied stats/operations research books, as well as a few like the no bullshit guide to linear algebra, but none cover this specific issue - or even how to fit a logistic regression at all, on a practical level (so not just 'conceptually you do xyz, implementation is left as an exercise for the reader').

matheist 8y ago
Random guess: a logistic regression is fit by maximizing a particular log likelihood. [+] You can find the maximum by (1) gradient ascent, or (2) the analogue of Newton's method in multiple dimensions [++], which involves computing the Hessian matrix. So there's your Hessian. [+] https://en.wikipedia.org/wiki/Logistic_regression#Model_fitting https://en.wikipedia.org/wiki/Logistic_regression#Model_fitt... [++] https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization#Higher_dimensions https://en.wikipedia.org/wiki/Newton%27s_method_in_optimizat...
- nerdponx 8y ago
  Good guess!
imh 8y ago
Look up maximum likelihood estimation [0] and look up newton's method[1]. Take the log likelihood of your data and find the parameters which maximize it. If that doesn't make sense, read up on numerical optimization. [0] https://en.wikipedia.org/wiki/Maximum_likelihood_estimation https://en.wikipedia.org/wiki/Maximum_likelihood_estimation [1] https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization#Higher_dimensions https://en.wikipedia.org/wiki/Newton%27s_method_in_optimizat...
Rainymood 8y ago
>So my question - is there a layman's explanation for what a Hessian matrix is (I'm approaching this from a graduate level stats angle). Just like the score vector is the derivative of the ML wrt its parameters, the Hessian matrix is just the derivative of the score vector. It's just the second derivative wrt the parameters of the ML. It's the derivative of the derivative of the ML function.
enriquto 8y ago
The Hessian matrix is covered in just about any standard calculus book. The Hessian is a generalization of the second derivative of elementary calculus. Recall that the second derivative of a function f(x) allows to distinguish concave (f''>0) and convex (f''<0) parts of the function. If you are at a local extremum (f'=0) it allows to distinguish maxima and minima. The Hessian does the same thing, but for functions of several variables. It says in which spatial directions your function is convex or concave. At a local maximum, it is concave in all directions, and at a local minimum it is convex in all directions. At a saddle point, there will be directions where it is concave and directions where it is convex. The eigen decomposition of the hessian allows to find these directions. It is useful for function approximation because the 2nd degree coefficients of a polynomial that better fits your data are precisely the entries of the Hessian matrix (due to Taylor theorem).
mehrdadn 8y ago
Are you familiar with what the 2nd derivative of a function is? The Hessian is just that, when you have a function with multiple inputs. What's the second derivative of f(x,y) = x/y? Well there are four of them depending on the order in which you differentiate: f_xx = 0, f_xy = -1/y^2, f_yx = -1/y^2, f_yy = 2x/y^3. You just put these in a nice matrix and call it the Hessian matrix. So for functions of N input variables, there are N^2 second-derivatives, so the Hessian is the matrix of all those second derivatives. I'm not sure how you saw it used for fitting a logistic model, but in general knowing the concavity of a function is useful for minimizing or maximizing it (e.g. by repeatedly approximating it as a 2nd-order polynomial and minimizing that), so maybe that's what you saw.
- thomasahle 8y ago
  > I'm not sure how you saw [the Hessian] used for fitting a logistic model Probably some 2nd derivative version of gradient descent or Newton's method. https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization#Higher_dimensions https://en.wikipedia.org/wiki/Newton%27s_method_in_optimizat...
  - mehrdadn 8y ago
    Yeah that's what I was referring to when I said "approximating it as a 2nd-order polynomial and minimizing that".
TJSomething 8y ago
Those Wikipedia pages are kind of awful for pedagogy, but they have the right equations, so I won't cover those. Say we have a curve that corresponds to how good of a fit your model is. We want to try to find the maximum on that curve. However, calculating every point of the curve is too expensive, so we want to minimize the number of points we have to check. So, we start with a guess as to the highest point on the curve and take the first and second derivatives of the curve at that point. This gives us enough to fit a parabola that approximates the curve in the neighborhood of our initial guess point. Then, it's pretty easy to solve for the highest point on the parabola. That's our new guess. Repeat that a few times until the guesses stop shifting much. If the curve is nicely shaped (i.e. smooth everywhere, only has one maximum), the guesses will converge on the highest point. This is a often faster than a similar method, gradient ascent, which relies upon only taking the first derivative. This would yield a line in the vicinity of our guess, and then we just move our guess a little bit, such that it goes up the line. This is pretty slow, since it can't just go straight to a guess of the top, and if you go too fast, then it'll blow right past the maximum. The Hessian matrix is the higher dimensional equivalent to the second derivative there and the gradient is the equivalent for the first derivative. For example, if we have a two dimensional surface in 3D, then those matrices will be 2x2 and capture the curvature of the 3D paraboloid in the vicinity of the guess. As you go up in dimensionality, they're called quadric hypersurfaces. When you're fitting a logistic regression, your hypersurface is the logarithm of the likelihood that the data you have fits the logistic curve with parameters at that point. The logarithm makes the hypersurface better behaved and makes the calculus easier. You just need the gradient and the Hessian, evaluate those at your initial guess, fit a quadric hypersurface to the guess there, pop up to the top of that hypersurface, repeat a few times, and you've got your model.
- cimmanom 8y ago
  Thank you for a super clear explanation that was easy to grok even with no more math background than (extremely rusty) high school calculus.
  - hotwire 8y ago
    yep, these are the kinds of posts on HN that I really appreciate, not the contrarian "well akshually" kind that usually appear.
anilakar 8y ago
Engineering maths is usually "put your numbers in a matrix and calculate the eigenvalues and eigenvectors" regardless of the field :-)
- MarkMMullin 8y ago
  Please make the lowest variance dimension go away to see if you can understand the problem then, and if not, rinse and repeat ?
archgoon 8y ago
So, when you perform a regression of any sort, what you're doing is saying "Hey, I want to find parameters X,Y,Z, etc, that make this curve best fit the data that I have". One interpretation of 'best fit' is 'minimize the mean squared error'. So regression is just a minimization problem. You're trying to find the values that minimize f(X,Y,Z...) And, well, that means that you just want to find values for X,Y,Z such that ∇f(X,Y,Z) = 0 Why? Because the derivative tracks the rate of change. If the function isn't changing much locally, you've hit either a minimum or maximum (assuming the function is smooth). Let's see how this plays out when you have a function that you're trying to minimize that only has 1 parameter. This is then just a regular old function of one variable, and we can easily visualize it. | | | x^2 + 2x \ |/ ------------ \_/| And take it's dervative | / | / | / 2x + 2 |/ | /| / | ------------ And then you'd say, oh hey I know the roots of 2x + 2 ! It's just x = -1. So x^2 + 2x would have a minimum at -1. But when dealing with many functions you may not know the functional form, or there may not be a way to solve for the roots symbolically (or you don't know the tricks to do so), you might want to try a strictly numerical approach. You say "Look, I know how to compute the original function, can't I just use that directly?" Well, one option would be to find two points on your function, one where it's positive, the other where it's negative, and then keep bisecting the interval down until you zoom in on the point where it crossed the x axis (with additional logic to handle multiple crossings). Of course, if you're function is discontinuous, or is discontinuous due to a floating point error, you're going to be hosed. This is the bisection method. However, it's not as fast as is desirable. Since each decimal point is an increase by a factor of 10 precision, and you typically want several decimal points at least, simply increasing your precision by a mere factor of 2 each time may not be good enough. This is especially true if you're doing this by hand. :) So a faster method is to start at a point, and then draw a line tangent to that point, and see where that line intersects the x-axis. Evaluate that point, and normally it'll be closer to a zero than before. repeat. This, in many cases, will converge much faster than performing bisection. This is known as the Newton-Raphson Method. Now, in order to draw a tangent line, you have to know how the function is changing at that point, so the line and the function's slopes will match, and well, that means you take the derivative. Since, however, the function which we're trying to find the root of is itself a derivative, this is now a second derivative. So it turns out Newton-Raphson generalizes upwards in dimension. So when you start off with your error function that you're trying to minimize, you take it's derivative, but now you have to track how it changes in N dimensions, so the derivative object is now a vector. Now, we're trying to minimize this vector valued function (the gradient), and set it to zero. So we take it's derivative, which, since it's vector valued, will now be a matrix, since each component can vary in N directions. So we now have a NxN matrix that tracks how everything is changing. This second order derivative is called the Hessian. And we can use it the same way (implementation left to the reader ;) ) as we did in one dimension.
GistNoesis 8y ago
In a general manner when you have a complex function you want to minimize to obtain your parameters. One way to proceed is to assume some initial parameters and refine them. To refine them, you locally approximate your function, get the minimum of the approximation, take a step toward this minimum and loop until convergence. At first order you can approximate locally your function as a plane (the plane that go through the point and has the same first derivative), and to minimize that you take a small step (because your approximation is only valid locally) in the direction where the plane is inclined. Alternatively you can make a better approximation of your function using higher order derivatives. So instead of approximating your function with a plane, you approximate it with a quadratic form (the multidimensional extension of the parabola). This quadratic form matches the first derivatives and also the Hessian (second derivatives in multi-dimension) of your function at your current parameters. Once you have the approximation, there are closed formula for the minimum of the quadratic form so you can directly jump closer to the result (but how it will perform will depend how close your function resemble your approximation). When to pick first order approximation or second order approximation is problem dependent, but a quick rule of thumb is second order is faster when close to the solution but consume memory quadratically with respect to the number of dimension so is only applicable when the dimension is low, or when you have problem specific simplifications like your problem being a sum of squares. In practice interesting problem are too big and first order method is all you can do. But you can also improve things a little by approximating the diagonal of the Hessian, or some low-rank approximation of the Hessian. (This is another tractable kind of approximation of your function). You can also make some probabilistic approximation of your function (only considering a few examples instead of the whole training set) and from that you can derive all "on-line" methods, but this is a story for another day.
pX0r 8y ago
A logistic regression model is typically used for a classification task. 'Fitting a logistic model' entails finding optimal coefficients / 'weights' of input features such that classification error is minimised. For a binary classification task, one could simply calculate mean squared error between predicted values and actual labels (as in linear regression) and then proceed to find the optimal weights iteratively using gradient descent. But the sigmoid shape of the logistic function makes gradient descent a poor choice of an optimization technique (w.r.t. lack of guarantee of finding a global optimum). A surer way to find globally optimal weights is using the Newton's method of calculating weight updates. This is a numerical optimization technique that requires one to calculate the 1st and 2nd order derivatives of the error function. The matrix that 'calculates' the 1st order derivative is called a Jacobian and the one that calculates the 2nd order derivative is called a Hessian...

by roel_v 8y ago

matheist 8y ago

Random guess: a logistic regression is fit by maximizing a particular log likelihood. [+] You can find the maximum by (1) gradient ascent, or (2) the analogue of Newton's method in multiple dimensions [++], which involves computing the Hessian matrix. So there's your Hessian. [+] https://en.wikipedia.org/wiki/Logistic_regression#Model_fitting https://en.wikipedia.org/wiki/Logistic_regression#Model_fitt... [++] https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization#Higher_dimensions https://en.wikipedia.org/wiki/Newton%27s_method_in_optimizat...

nerdponx 8y ago
Good guess!

imh 8y ago

Look up maximum likelihood estimation [0] and look up newton's method[1]. Take the log likelihood of your data and find the parameters which maximize it. If that doesn't make sense, read up on numerical optimization. [0] https://en.wikipedia.org/wiki/Maximum_likelihood_estimation https://en.wikipedia.org/wiki/Maximum_likelihood_estimation [1] https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization#Higher_dimensions https://en.wikipedia.org/wiki/Newton%27s_method_in_optimizat...

Rainymood 8y ago

>So my question - is there a layman's explanation for what a Hessian matrix is (I'm approaching this from a graduate level stats angle). Just like the score vector is the derivative of the ML wrt its parameters, the Hessian matrix is just the derivative of the score vector. It's just the second derivative wrt the parameters of the ML. It's the derivative of the derivative of the ML function.

enriquto 8y ago

The Hessian matrix is covered in just about any standard calculus book. The Hessian is a generalization of the second derivative of elementary calculus. Recall that the second derivative of a function f(x) allows to distinguish concave (f''>0) and convex (f''<0) parts of the function. If you are at a local extremum (f'=0) it allows to distinguish maxima and minima. The Hessian does the same thing, but for functions of several variables. It says in which spatial directions your function is convex or concave. At a local maximum, it is concave in all directions, and at a local minimum it is convex in all directions. At a saddle point, there will be directions where it is concave and directions where it is convex. The eigen decomposition of the hessian allows to find these directions. It is useful for function approximation because the 2nd degree coefficients of a polynomial that better fits your data are precisely the entries of the Hessian matrix (due to Taylor theorem).

mehrdadn 8y ago

Are you familiar with what the 2nd derivative of a function is? The Hessian is just that, when you have a function with multiple inputs. What's the second derivative of f(x,y) = x/y? Well there are four of them depending on the order in which you differentiate: f_xx = 0, f_xy = -1/y^2, f_yx = -1/y^2, f_yy = 2x/y^3. You just put these in a nice matrix and call it the Hessian matrix. So for functions of N input variables, there are N^2 second-derivatives, so the Hessian is the matrix of all those second derivatives. I'm not sure how you saw it used for fitting a logistic model, but in general knowing the concavity of a function is useful for minimizing or maximizing it (e.g. by repeatedly approximating it as a 2nd-order polynomial and minimizing that), so maybe that's what you saw.

thomasahle 8y ago
> I'm not sure how you saw [the Hessian] used for fitting a logistic model Probably some 2nd derivative version of gradient descent or Newton's method. https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization#Higher_dimensions https://en.wikipedia.org/wiki/Newton%27s_method_in_optimizat...
- mehrdadn 8y ago
  Yeah that's what I was referring to when I said "approximating it as a 2nd-order polynomial and minimizing that".

TJSomething 8y ago

Those Wikipedia pages are kind of awful for pedagogy, but they have the right equations, so I won't cover those. Say we have a curve that corresponds to how good of a fit your model is. We want to try to find the maximum on that curve. However, calculating every point of the curve is too expensive, so we want to minimize the number of points we have to check. So, we start with a guess as to the highest point on the curve and take the first and second derivatives of the curve at that point. This gives us enough to fit a parabola that approximates the curve in the neighborhood of our initial guess point. Then, it's pretty easy to solve for the highest point on the parabola. That's our new guess. Repeat that a few times until the guesses stop shifting much. If the curve is nicely shaped (i.e. smooth everywhere, only has one maximum), the guesses will converge on the highest point. This is a often faster than a similar method, gradient ascent, which relies upon only taking the first derivative. This would yield a line in the vicinity of our guess, and then we just move our guess a little bit, such that it goes up the line. This is pretty slow, since it can't just go straight to a guess of the top, and if you go too fast, then it'll blow right past the maximum. The Hessian matrix is the higher dimensional equivalent to the second derivative there and the gradient is the equivalent for the first derivative. For example, if we have a two dimensional surface in 3D, then those matrices will be 2x2 and capture the curvature of the 3D paraboloid in the vicinity of the guess. As you go up in dimensionality, they're called quadric hypersurfaces. When you're fitting a logistic regression, your hypersurface is the logarithm of the likelihood that the data you have fits the logistic curve with parameters at that point. The logarithm makes the hypersurface better behaved and makes the calculus easier. You just need the gradient and the Hessian, evaluate those at your initial guess, fit a quadric hypersurface to the guess there, pop up to the top of that hypersurface, repeat a few times, and you've got your model.

cimmanom 8y ago
Thank you for a super clear explanation that was easy to grok even with no more math background than (extremely rusty) high school calculus.
- hotwire 8y ago
  yep, these are the kinds of posts on HN that I really appreciate, not the contrarian "well akshually" kind that usually appear.

anilakar 8y ago

Engineering maths is usually "put your numbers in a matrix and calculate the eigenvalues and eigenvectors" regardless of the field :-)

MarkMMullin 8y ago
Please make the lowest variance dimension go away to see if you can understand the problem then, and if not, rinse and repeat ?

archgoon 8y ago

So, when you perform a regression of any sort, what you're doing is saying "Hey, I want to find parameters X,Y,Z, etc, that make this curve best fit the data that I have". One interpretation of 'best fit' is 'minimize the mean squared error'. So regression is just a minimization problem. You're trying to find the values that minimize f(X,Y,Z...) And, well, that means that you just want to find values for X,Y,Z such that ∇f(X,Y,Z) = 0 Why? Because the derivative tracks the rate of change. If the function isn't changing much locally, you've hit either a minimum or maximum (assuming the function is smooth). Let's see how this plays out when you have a function that you're trying to minimize that only has 1 parameter. This is then just a regular old function of one variable, and we can easily visualize it. | | | x^2 + 2x \ |/ ------------ \_/| And take it's dervative | / | / | / 2x + 2 |/ | /| / | ------------ And then you'd say, oh hey I know the roots of 2x + 2 ! It's just x = -1. So x^2 + 2x would have a minimum at -1. But when dealing with many functions you may not know the functional form, or there may not be a way to solve for the roots symbolically (or you don't know the tricks to do so), you might want to try a strictly numerical approach. You say "Look, I know how to compute the original function, can't I just use that directly?" Well, one option would be to find two points on your function, one where it's positive, the other where it's negative, and then keep bisecting the interval down until you zoom in on the point where it crossed the x axis (with additional logic to handle multiple crossings). Of course, if you're function is discontinuous, or is discontinuous due to a floating point error, you're going to be hosed. This is the bisection method. However, it's not as fast as is desirable. Since each decimal point is an increase by a factor of 10 precision, and you typically want several decimal points at least, simply increasing your precision by a mere factor of 2 each time may not be good enough. This is especially true if you're doing this by hand. :) So a faster method is to start at a point, and then draw a line tangent to that point, and see where that line intersects the x-axis. Evaluate that point, and normally it'll be closer to a zero than before. repeat. This, in many cases, will converge much faster than performing bisection. This is known as the Newton-Raphson Method. Now, in order to draw a tangent line, you have to know how the function is changing at that point, so the line and the function's slopes will match, and well, that means you take the derivative. Since, however, the function which we're trying to find the root of is itself a derivative, this is now a second derivative. So it turns out Newton-Raphson generalizes upwards in dimension. So when you start off with your error function that you're trying to minimize, you take it's derivative, but now you have to track how it changes in N dimensions, so the derivative object is now a vector. Now, we're trying to minimize this vector valued function (the gradient), and set it to zero. So we take it's derivative, which, since it's vector valued, will now be a matrix, since each component can vary in N directions. So we now have a NxN matrix that tracks how everything is changing. This second order derivative is called the Hessian. And we can use it the same way (implementation left to the reader ;) ) as we did in one dimension.

GistNoesis 8y ago

In a general manner when you have a complex function you want to minimize to obtain your parameters. One way to proceed is to assume some initial parameters and refine them. To refine them, you locally approximate your function, get the minimum of the approximation, take a step toward this minimum and loop until convergence. At first order you can approximate locally your function as a plane (the plane that go through the point and has the same first derivative), and to minimize that you take a small step (because your approximation is only valid locally) in the direction where the plane is inclined. Alternatively you can make a better approximation of your function using higher order derivatives. So instead of approximating your function with a plane, you approximate it with a quadratic form (the multidimensional extension of the parabola). This quadratic form matches the first derivatives and also the Hessian (second derivatives in multi-dimension) of your function at your current parameters. Once you have the approximation, there are closed formula for the minimum of the quadratic form so you can directly jump closer to the result (but how it will perform will depend how close your function resemble your approximation). When to pick first order approximation or second order approximation is problem dependent, but a quick rule of thumb is second order is faster when close to the solution but consume memory quadratically with respect to the number of dimension so is only applicable when the dimension is low, or when you have problem specific simplifications like your problem being a sum of squares. In practice interesting problem are too big and first order method is all you can do. But you can also improve things a little by approximating the diagonal of the Hessian, or some low-rank approximation of the Hessian. (This is another tractable kind of approximation of your function). You can also make some probabilistic approximation of your function (only considering a few examples instead of the whole training set) and from that you can derive all "on-line" methods, but this is a story for another day.

pX0r 8y ago

A logistic regression model is typically used for a classification task. 'Fitting a logistic model' entails finding optimal coefficients / 'weights' of input features such that classification error is minimised. For a binary classification task, one could simply calculate mean squared error between predicted values and actual labels (as in linear regression) and then proceed to find the optimal weights iteratively using gradient descent. But the sigmoid shape of the logistic function makes gradient descent a poor choice of an optimization technique (w.r.t. lack of guarantee of finding a global optimum). A surer way to find globally optimal weights is using the Newton's method of calculating weight updates. This is a numerical optimization technique that requires one to calculate the 1st and 2nd order derivatives of the error function. The matrix that 'calculates' the 1st order derivative is called a Jacobian and the one that calculates the 2nd order derivative is called a Hessian...