2
$\begingroup$

I am trying to train and implement a Neural Network. I was reading a few articles, learning about their principles and the math that goes behind them. However, while I was trying to understand the math, specifically the optimization part (for selecting weights), I ran into a problem: I couldn’t understand the Broyden–Fletcher–Goldfarb–Shanno algorithm. I understand that it (basically) uses newton's method, expect that it finds the zeroes of the derivative of the original function (to find the local minima of the original function).

However I was having trouble following the notation and math that is written on Wikipedia about it: enter image description here

First of, I do understand that Bk is a Hessian matrix that holds the partial second derivatives and f(x) is the original function that we are finding the local minima of. Moving on to step 1, I do not understand why the search direction needs to be solved. (Is it because we need to figure out whether the zero of the derivative is a local maximum or minimum of f(x) aka perform the first derivative test). In step 2, I do not understand why line search needs to be performed. In step 3, I do not understand what the product of ak and pk means. In step four, (correct me if I am wrong), yk equals the change in y or f(x). Finally, I know step 5 is trying to approximate Bk+1, which is what newton's method does, but I do not understand why its trying to estimate another Hessian matrix, shouldn't it be estimating a point? Or is it estimating a matrix because the algorithm is supposed to work with a multidimensional space, but then how does the partial second derivative matrix lead to finding the local minima of the original function? Also, what does the right side of the equation mean with all the vector/matrix multiplication and division. (I know this is a quasi-netown method but do not really understand it).

I tried to search the internet for my answers, but I couldn't really find anything. I am only in high school and don't have anyone who can explain me this math. So I really appreciate your help. Thank you so much in advance.

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! BFGS is indeed challenging to understand. The good news is you don't need to understand it: today most neural networks are trained with some kind of online/stochastic gradient descent, not with BFGS. Of course your question is still valid. I would suggest looking for another explanation of BFGS other than Wikipedia; there are many blog posts and others that explain what's going on better (Wikipedia's explanation just isn't very good). Make sure you understand first how/why gradient descent works and how Newton's method works for 1D functions $f:\mathbb{R}\to \mathbb{R}$. $\endgroup$ – D.W. Jul 19 '16 at 7:04
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jul 19 '16 at 9:52
  • $\begingroup$ @D.W. Thank you for your response. I will definitely look into Stochastic gradient descent. But I wanted to understand the underlying principles (and then the math) behind these algorithms. Thank you! $\endgroup$ – user5139637 Jul 19 '16 at 14:54
1
$\begingroup$

The purpose of the "search direction" is that we want to move closer to a minimum of $f(x)$. The gradient tells us the direction of steepest descent (as in gradient descent).

The reason we do the line search is to figure out how far to travel in that direction. The gradient tells us the direction; but it doesn't tell us how far to go in that direction.

The product $\alpha_k \mathbf{p}_k$ is an ordinary product of a scalar and a vector; i.e., component-wise product. You probably need to study a bit of linear algebra and multivariate calculus to get familiar with this sort of thing -- that's a vitally important foundation.

Step 5 is the heart of BFGS. A full Newton method would calculate the Hessian (matrix of second partiala derivatives) at each point; i.e., it would re-calculate the Hessian in step 5. BFGS doesn't re-calculate it from scratch, as re-calculating it is expensive. Instead, it tries to make an estimate/guess of how the Hessian has changed. That's what step 5 is doing. This estimate is less accurate than simply recomputing the full Hessian matrix, but it's faster.

You're not going to be able to understand what's going on in BFGS from Wikipedia. Wikipedia's description is not very good, and there is no explanation of where the method came from. Look for a better, more detailed explanation that explains where these steps came from, the intuition of what's going on, and how these particular formulas were derived. Wikipedia is a great resource, but it's not a very good source for learning BFGS.

$\endgroup$
  • 1
    $\begingroup$ That was very helpful. It definitely cleared up some confusion. I will definitely look at the math. I found a good article exaplinjg the math and gradient descent: cs229.stanford.edu/notes/cs229-notes1.pdf $\endgroup$ – user5139637 Jul 19 '16 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.