Graphs on the web are often used to present data. Sometimes we also are interesting in
finding equation that describes the data trend so we could use it for prediction. The processing time on the web is very important since nobody wants to wait web page loading. This discussion will show
one of the way to calculate quickly the equation coefficients using some optimization theory.
The problem
Having some data x,y we want to minimize the error between actual data x,y and our model y=f(x) that we need to find.
Mathematically the problem can be viewed as following:
For given set of N points x,y find function y=f(x) that is the closest to all points x,y.
This means that we need to minimize
L(t)=Sum(Yi - f(Xi))2 ==> min
where
f(X)=a0+a1X+a2X2+....
X,Y is actual or training data
t is the vector of coefficients (a0, a1, a2, ...)
Our goal is to find coefficients (a0, a1, a2, ...) .
The Newton-Raphson Method
We will apply the Newton-Raphson method which is using first and second derivative of L
There are many other algorithms but the Newton-Raphson method will be the quickest in terms of computing time because it requires only one iteration. The algorithm can be described by following equation:
tk+1 = tk - H-1g(tk)
The matrix H is the second derivative of L by t, so each element of H is ¶2L/¶ai¶aj
Since L is quadratic by t H as a second derivative of L by t is const and this algorithm requires only one iteration !
However it requires existing and calculation of inverse matrix
The elements of g and H can be found by :
Here is the numerical example:
Find y=f(x) for Y1(1,1) Y2(2,2)
In this example we assume that y is linear so we need to find a0, a1 for the following trend:
f(x)=a0+a1x
In nonlinear case with any number of coefficient the algorithm will be the same. Of course we would need more than 2 training data.
We can take any start point for a0, a1
In this example we take start point is (5,5)
We calculate first derivatives which go to g(t)
¶L/¶a0=-2(1-a0-a1)-2(2-a0-2a1) =44
¶L/¶a1=-2(1-a0-a1)-4(2-a0-2a1) =70
Now we calculate matrix H as second derivative of L by coefficients aai, i=0,1
and then calculate inverse of H
