Applied Math & Computer Science Lab
Data Analysis, Optimization & Mathematical Modeling, Artificial Intelligence, Neural Net For Everyday Life Applications
AI/Data Mining Links Online Free Courses Online Bookstore AMCSL Forum Submit Link New Additions Archive
Practical Data Mining Courses      Get Certificate of Completion Now for Free   
Search the Web:    



Optimization Techniques for Finding the Trend

Inroduction

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/aiaj
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 :
L/az=-2Sum((Yk-Sum(aiXki)Xki)
2L/azaj=2Sum(Xkj*Xkz)

The Numerical Example

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  
H=46
610
 
H-1=2.5-1.5
-1.51

Now we do iteration :  
a0new   =   5  -  2.5-1.5 * 44
a1new 5-1.5170

a0=0
a1=1
so y=f(x)=0+1*x=x


References



1. Online Inverse Matrix Calculation
2. Inverse Matrix Calculaltion - includes source code to calculate inverse matrix