Implement a Map/Reduce enabled Machine Learning Algorithm

[surya ganesh <su...@gmail.com>]

Hi,

I would like to implement Logistic Regression classification algorithm using
Hadoop. Here is the proposal of the same -

*Title: *Implementing Logistic Regression Classifier for Mahout

*Abstract: *

Mahout intends to create a suite of scalable, parallelizable machine
learning libraries using Hadoop. Hadoop is a Java framework that supports
data intensive distributed applications. It was inspired by Google's
MapReduce and Google File System papers.

The aim of this project is to implement Logistic Regression classifier using
Hadoop for the Mahout project. Logistic Regression predicts the probability
of occurrence of an event by fitting data to a logistic curve. It makes use
of several predictor variables that may be either numerical or categorical.

*Description:*

The task of implementing Logistic Regression classifier using Hadoop
includes two phases, one is learning and the other is prediction. The
implementation details of both the phases are described below –

*Learning: *

This is an offline phase which estimates the parameter vector that best fits
the training data.  So, first the training data is divided into multiple
chunks and they are distributed to nodes around the cluster using Hadoop
Distributed File System (HDFS). Each node then performs a map task that uses
BFGS a Quasi-Newton optimization method to produce gradient and hessian
matrix. The reducer then sums up the values for gradient and hessian to
perform the update for parameter vector.

*Prediction:*

This is an online phase which estimates the probability of occurrence of an
event. The testing data is divided into multiple chunks and they are
distributed to nodes around the cluster using HDFS.  Each node then performs
a map task that predicts the probability of occurrence of every event in the
chunk. The number of reduce tasks are set to zero as no reduction of
map-outputs is desired. So, the outputs of the map-tasks go directly
to the file
system.

Any Suggestions ??
Thank you,
Surya Ganesh.

Re: Implement a Map/Reduce enabled Machine Learning Algorithm

[Ted Dunning <te...@gmail.com>]

On Tue, Mar 31, 2009 at 1:37 AM, surya ganesh <su...@gmail.com>wrote:

>
> Any Suggestions ??
> Thank you,
> Surya Ganesh.
>


Yes.  First, this is a fine thing to do.

First, though, I think it is true that you can really just sum up the
partial estimates of the Hessian and gradient, but I don't think that it is
clear that this actually is the only costly step.  Is it?

Secondly, in your approach it is easy to introduce a simple regularization,
but I think that you should consider cases where something more aggressive
is needed.  Using a Laplacian (double exponential) prior gives one such
regularizer that has the desirable feature of encouraging sparseness,
aggressive variable selection is another approach.  For very large problems,
some sort of regularization is absolutely required because as the data size
grows, it is common for the number of possibile features to grow as well as
the number of possible interactions that can be considered.

Thirdly, you should plan some sort of evaluation of your results in terms of
run-time and accuracy.  There are many standard data sets that you can use
for this, although most are relatively small.

Here are some references:

Sparse logistic regression:
http://www.lx.it.pt/~mtf/Krishnapuram_Carin_Figueiredo_Hartemink_2005.pdf

Variable selection: *http://ideas.repec.org/p/wop/pennin/01-05.html*

Better chi^2 testing: *
http://tdunning.blogspot.com/2008/03/surprise-and-coincidence.html*

-- 
Ted Dunning, CTO
DeepDyve