4 ms·
If only there was a faster known way to get the inverse of a matrix... Gradient descent seems like an ugly hack compared to that (having taken an ML class) It
by pmarreck 10y ago
If only there was a faster known way to get the inverse of a matrix... Gradient descent seems like an ugly hack compared to that (having taken an ML class)
It reminds me of taking the derivative by manually measuring the slope between 2 points on the curve, instead of, you know, directly getting the derivative
- jofer 10y agoGradient descent is for non-linear problems where you can't directly invert or somehow linearize the problem.
- pmarreck 10y agoOften you can directly invert, but with current methods it would just be prohibitively expensive computationally. What I'm trying to say is that occam's razor seems to suggest that there is a better way to do matrix inversions which we simply haven't discovered yet.
- dragonwriter 10y ago> What I'm trying to say is that occam's razor seems to suggest that there is a better way to do matrix inversions which we simply haven't discovered yet. Occam's razor doesn't suggest that. Such a method is an additional assumed entity that adds nothing to our ability to explain what is observed, and is thus the kind of thing Occam's razor calls one to reject, rather than suggests. Now, belief in the existence of such a method might be a means of satisfying an aesthetic preference for a computationally convenient universe, but that's something very different than Occam's razor.
- pmarreck 10y agoFair enough, you got at what I was getting at in your last paragraph
- xaedes 10y agoTaking the inverse of a matrix only solves problems which can be described in a specific way. There are situations where you want to optimize an arbitrary function. Also taking the inverse of a matrix isn't always easy. For example for very large matrices. The are also problems where the optimal solution changes over time (e.g. trajectory following control). This gives a good guess for the solution at each timestep(t>0) and improving that with gradient descent can be more performant than completely solving for a matrix inverse each time.
- pmarreck 10y ago> Also taking the inverse of a matrix isn't always easy. For example for very large matrices. Yeah, I know. I am saying that I think there is probably an undiscovered solution to doing faster inverse matrices, based on occam's razor (which I'm taking to mean that "complex and ugly" suggests there is probably undiscovered "simpler and more elegant"... which I've seen over and over again in other areas... gradient descent being the "complex and ugly" here) > This gives a good guess for the solution at each timestep(t>0) and improving that with gradient descent can be more performant than completely solving for a matrix inverse each time. That's a good point, but perhaps the hypothetical matrix inversion I'm assuming exists also allows you to do computationally efficient differential inversions based on small changes to the matrix. I admit this was just a "gut feeling," but when I first learned about gradient descent vs. matrix inversion I had a very strong gut feeling that there was a better way out there. My career is programming (where I have followed this "gut feeling" many times, usually to success) and I did papers on matrices and determinants in high school, this may be informing my "gut". Not sure if any mathy people are reading this, but I think there's gold to be had here, if you look hard enough
- RBerenguel 10y agoGolub/van Loan (Matrix Computations) is a thick book talking only on methods to work with matrices, old... And not "much" has changed in the basics. If there is gold to be had there, is damn deep, and won't be an easy algorithm at all
- maxerize 10y ago
- plg 10y agohttp://www.johndcook.com/blog/2010/01/19/dont-invert-that-matrix/ http://www.johndcook.com/blog/2010/01/19/dont-invert-that-ma...
- Sherlock 10y agoThis is the clearest signal to tell apart people who have studied applied math and people that haven't.
- thatsadude 10y agoCheck out Nesterov's Accelerate gradient. Its convergence rate is O(1/t^2).
- pmarreck 10y agohttps://blogs.princeton.edu/imabandit/2013/04/01/acceleratedgradientdescent/ https://blogs.princeton.edu/imabandit/2013/04/01/accelerated... for anyone else curious