Online Classification for Big Data


Highlighting my experience during coding of Stochastic Gradient Descent algorithm


Stochastic Gradient Descent is an online classification algorithm. This algorithm proves to be very efficient in classification of huge big data problems. Unlike Logistic algorithm, which is somewhat ancestor of this, it takes one row at a time from the input data which can also be called as tuple instead of a whole matrix. The data possess by the tuple undergoes computation and result gets added to previous computed record.
There is a huge possibility of the usage of this algorithm in Big data analytics. Most common use case has been seen in medical field wherein the system accepted input from the patient on basis of cholesterol level and other parameters, and with help of this algorithm gave a probability of that individual having heart disease. link  


Through this blog I intent to share my team’s experience in coding this feature, as well as documenting major findings during course of time.


It was pretty difficult for us to find any c# code for the same algorithm. Initially Accord.net proved to be of some help http://code.google.com/p/accord/ related to Logistic learning, but it didn’t have any help related to SGD which was our objective.


Nevertheless, we found some help from few articles and Java implementation of SGD in Apache Mahout. After much learning we had enough data to code in .net technology and came up with following findings.
1.       We coded for Online Stochastic gradient using lazy stochastic method, which was easier to implement.
2.       We calculated for Probability per epoch, log likelihood per epoch, error gradient and learning rate.


3.       Input File Format:

For verification of result we took input csv file as
A,B,C,D,E,F
a,1,2,4,6,4
b,1,4,3,6,4
c,1,7,2,6,4
d,1,2,5,6,4
e,0,9,8,6,4
f,1,1,6,6,4
f,0,1,6,6,4
f,1,1,6,6,4
f,1,1,6,6,4
f,1,1,6,6,4
f,0,1,6,6,4
f,1,1,6,6,4
f,1,1,6,6,4
f,1,1,6,6,4
f,1,1,6,6,4
f,1,1,6,6,4

Note here, the dependent column is B and C,D,E,F are the independent column. Let me portray a scenario for better understanding. Assuming the first row(epoch) is having a patient entry. You can read this row as
a,1,2,4,6,4
·         person name – a
·         Having heart disease – yes or 1
·         Cholesterol level above normal – 2
·         Blood pressure -4 etc.
As you can see the dependent column had binomial values 0 or 1.
If you take a note of the pattern I have deliberately made the 4th multiple row to be 0 so that I get a probability of 0.75 (3 cases out of 4 are having heart disease). I had approximately 630 data with such entry.


4.       Output File Format

The output that we achieved was in this format:
Result for per row,ProbabilityLikelihood,log likelihood, Error Gradient,Learning Rate
 
1,0.5,-0.693147180559945,0.5,15.8113883008419
1,1,0,0,15.0604916616593
1,1,0,0,14.4049036500379
1,1,0,0,13.825943979561
1,0,-100,-1,13.3096899721724
1,4.81619553731958E-190,-100,1,12.8455237353312
….
Resultant Headers for LR Classifier: Total Log Likelihood ,Deviance,Mean Error,Max Error
Result,-3987.86477761697,7975.72955523393,-0.000287308070520634,1
 
To us this huge output file was making no sense. As this was having a csv format we thought to depict graphical charts out of this.
 
Surprisingly, we got unique continuous patterns for the above outputs
 



Learning Rate



Log Likelihood






Probability


(Approximately coming to 0.75)

Error



Summary
Now after going through the charts the accuracy of the results were verified. Learning had an exponential decay, Log Likelihood was tending to zero, Probability was tending to 0.75 and error rates also were started to converge. Given a huge data of almost 1TB, may be the observation would have shown more clear patterns till saturation limit.

I would like to acknowledge Cesar Souza discussing with whom really helped us to deep dive in the problem statement.

Please feel free to post your view and suggestion to this.

Comments

  1. Hi Nabarun! This is very great. Will you be sharing your implementation someday, or is it a private work? Nevertheless, your work seems very interesting. I also have researched heart disease in the past, although
    with neural networks rather than logistic regression.

    Best regards,
    Cesar

    ReplyDelete
  2. Hi Cesar,
    Unfortunately this is not a private work. This was a customer oriented project and had some non disclosure agreement. However currently I am studying Random forest implementation, I will more than happy if I can contribute to Accord.net.
    I have no doubt your implementation with neural networks will be equally interesting as your other works. It is also great to see accord.net migrated to codeplex. Great going Cesar.
    Regards
    Nabarun

    ReplyDelete

Post a Comment

Popular posts from this blog

Firebase authentication with Ionic creator

Big Data - SWOT Analysis

LINKEDIN api call using NODE.JS OAUTH module