KrisLibrary
1.0.0
|
Stochastic gradient descent estimation of least-squares solution to y = A x. More...
#include <OnlineOLS.h>
Public Member Functions | |
void | SetPrior (const Vector &coeffs, int strength=1) |
void | AddPoint (const Vector &data, Real outcome) |
Public Attributes | |
int | numObservations |
bool | store |
std::vector< Vector > | data |
std::vector< Real > | outcome |
std::vector< Real > | weightPolynomial |
Vector | coeffs |
Stochastic gradient descent estimation of least-squares solution to y = A x.
The A matrix is the "data" vector, y is the "outcome" vector. Each update step takes O(n) time, where n is the number of dimensions in x.
Single step error-minimizing least-squares solution gives min ||x-coeffs||^2 s.t. am^T x = bm => 2(x-coeffs) + lambda * am = 0, am^T x = bm x = coeffs + lambda*am am^T x = bm = am^T coeffs + lambda* am^T am lambda = (bm - am^T coeffs) / am^T am => x - coeffs = am * (bm - am^T coeffs) / am^T am Uses the stochastic gradient descent step coeffs(m) = coeffs(m-1) + w(m)*(x - coeffs). where w(m) is a weight term.
The weight is 1 / P(m) where m is the number of observations, and P(m) is a polynomial. If P(m) is constant, then the estimate "forgets" distant history. If P(m) is linear, then it converges to the true estimate.