You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by Sisir Koppaka <si...@gmail.com> on 2010/03/22 17:36:54 UTC
Reg. Netflix Prize Apache Mahout GSoC Application
Dear Robin & the Apache Mahout team,
I'm Sisir Koppaka, a third-year student from IIT Kharagpur, India. I've
contributed to open source projects like FFmpeg earlier(Repository diff
links are here<http://git.ffmpeg.org/?p=ffmpeg;a=commitdiff;h=16a043535b91595bf34d7e044ef398067e7443e0>and
here<http://git.ffmpeg.org/?p=ffmpeg;a=commitdiff;h=9dde37a150ce2e5c53e2295d09efe289cebea9cd>
), and I am very interested to work on a project for Apache Mahout this
year(the Netflix algorithms project, to be precise - mentored by Robin).
Kindly let me explain my background so that I can make myself relevant in
this context.
I've done research work in meta-heuristics, including proposing the
equivalents of local search and mutation for quantum-inspired algorithms, in
my paper titled "*Superior Exploration-Exploitation Balance With
Quantum-Inspired Hadamard Walks*", that was accepted as a late-breaking
paper at GECCO 2010. We(myself and a friend - it was an independent work),
hope to send an expanded version of the communication to a journal in the
near future. For this project, our language of implementation was in
Mathematica, as we needed the combination of functional paradigms and
available mathematically sound resources(like biased random number
generation, simple linear programming functions etc.) as well as rapid
prototyping ability.
I have earlier interned in GE Research in their Computing and Decision
Sciences Lab<http://ge.geglobalresearch.com/technologies/computing-decision-sciences/>last
year, where I worked on machine learning techniques for large-scale
databases - specifically on the Netflix Prize itself. Over a 2 month
internship we rose from 1800 to 409th position on the Leaderboard, and had
implemented at least one variant of each of the major algorithms. The
contest ended at the same time as the conclusion of our internship, and the
winning result was the combination of multiple variants of our implemented
algorithms.
Interestingly, we did try to use Hadoop and the Map-Reduce model for the
purpose based on a talk from a person from Yahoo! who visited us during that
time. However, not having access to a cluster proved to be an impedance for
fast iterative development. We had one machine of 16 cores, so we developed
a toolkit in C++ that could multiprocess upto 16 threads(data input
parallelization, rather than modifying the algorithms to suit the Map-Reduce
model), and implemented all our algorithms using the same toolkit.
Specifically, SVD, kNN Movie-Movie, kNN User-User, NSVD(Bellkor and other
variants like the Paterek SVD, and the temporal SVD++ too) were the major
algorithms that we implemented. Some algorithms had readily available open
source code for the Netflix Prize, like NSVD1, so we used them as well. We
also worked on certain regression schemes that could improve prediction
accuracy like kernel-ridge regression, and it's optimization.
Towards the end, we also attempted to verify the results of the infamous
paper that showed that IMDB-Netflix correlation could destroy privacy, and
identify users. We would import IMDB datasets, and put them into a database
and then correlate the IMDB entries to Netflix(we matched double the number
of movies that the paper mentioned), and then verify the results. We also
identified genre-wise trends and recorded them as such. Unfortuantely, the
paper resulted in a libel case, wherein Netflix surrendered it's rights to
hold future Prizes of this kind in return for withdrawal of charges. The
case effectively closed the possibility of Netflix or any other company
releasing similar datasets to the public pending further advances in privacy
enforcement techniques, leaving the Netflix database as the largest of it's
kind.
Naturally, it is very interesting if there is an opportunity to implement
the same for Hadoop, since Netflix is the largest database of it's kind and
this would be of multiple uses - as a kickstart, tutorial, and as a
performance testing(using an included segment of the total database) tool
for grids. In addition, the Netflix and IMDB framework base code could be
incredibly useful as a prototyping tool for algorithm designers who want to
design better machine learning algorithms/ensembles for large-scale
databases. The lack of a decent scalable solution for the Netflix Prize so
that people can learn from it/add to it, is also a major disappointment that
this proposal hopes to correct.
Specifically, the challenge I am personally looking forward to is to
implement some of these algorithms using the Map-Reduce model, which is what
I missed out last time. I am looking forward to:
1. Account for the 12 global effects. The global effects were 12 corrections
made in the dataset to account for time, multiple votes on a single day
etc., and these alone give a major boost to the accuracy of the predictions.
2. Implement at least 1 kNN based approach. Most of them differ in their
parameters, or in their choice of distance definitions(Pearson, Cosine,
Euclidean etc.)
3. Implement at least 1 SVD based temporal approach. While Mahout already
possesses SVD implementations - slight variations of which could replicate
multiple SVD approaches for the Netflix Prize, the temporal SVD++ has in my
past experience been a very promising candidate that contributes a lot of
perpendicular insight into the predictions.
4. RBM implementation. RBM's were found to offer distinct insights into the
predictions, and Mahout doesn't currently possess one implementation yet(as
Ankur C. Goel mentioned on this list a few days ago), so this is a
no-brainer for a must-do implementation for the Netflix Prize GSoC project.
5. Implementing at least 1 regression scheme relevant to the Netflix Prize
as part of the boiler plate code that would be required for this project to
facilitate further additions of algorithm variants. I'd like to do
kernel-ridge regression, since it has, again, provided decent results on the
Netflix dataset compared to other options. I need to discuss this part with
my mentor/the Apache Mahout team because while multiple regression schemes
are required for this project, I am not sure if it is necessary to implement
this as a Map-Reduce based scheme, *at least within the scope of the GSoC
project.* This is because it is not very compute-intensive, at least not as
much as the central algorithms for the Netflix Prize, and wouldn't be a
critical limiting factor to successful completion of an 8% improvement
project goal.
The idea is that 1,2,5 would not take more than two weeks, with 3 taking
another two weeks and the rest of the time would be spent on 4. A
demonstrated 8% improvement over Cinematch on the Netflix dataset would be
the project goal.
There are plenty of references about the Grand Prize solution - Yehuda
Koren's final summary<http://www.netflixprize.com/assets/GrandPrize2009_BPC_BellKor.pdf>is
a great starting point. However, when I last worked on the problem
this
wasn't available, so I referred to papers by Arik Paterek and some of
Bellkor's earlier papers.
Looking forward to a discussion about the proposal,
Thanks a lot,
Best regards,
Sisir Koppaka
--
SK
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Sisir Koppaka <si...@gmail.com>.
As far as I'm aware, RBM's for Netflix were pioneered by Ruslan
Salakhtudinov <http://www.cs.toronto.edu/%7Ersalakhu/> and Geoffrey Hinton
of UToronto. I'm planning to base my code on their algorithms. If there's
another source that you prefer I keep as a reference in addition to the
above, then please do let me know.
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Sisir Koppaka <si...@gmail.com>.
Hi Jake and Ted,
Thanks a lot for your feedback. I'll refocus my proposal on implementing RBM
for the Netflix dataset(there is some parallelization opportunity, I'm
working on figuring out the details). This would add in a new RBM algorithm,
as well as provide the hooks required for rapid iteration of an ensemble
approach for Netflix using already implemented algorithms. As Ted mentioned,
I'll also account for documentation and other associated works in the
timeline in the final proposal.
I'll do some more ground work at the algorithm and code level, and update on
the list with any queries that I have.
Please do give any other feedback that you think is relevant.
Best regards,
Sisir Koppaka
On Tue, Mar 23, 2010 at 2:39 AM, Jake Mannix <ja...@gmail.com> wrote:
> Hi Sisir,
>
> I'm the one who added the most recent SVD stuff to Mahout,
> and while I'd love to see improvements in that, and incorporation
> into netflix-style recommenders, I would even more like to see
> a stacked-RBM implementation if you think you can do that. We
> don't currently have anything like that in Mahout, and even if
> it is completely serial (no Hadoop-hooks), it would be very
> excellent as an addition to the project.
>
> That's my opinion on the matter. :)
>
> -jake
>
--
SK
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Sisir Koppaka <si...@gmail.com>.
I have put up the processed Netflix dataset
here<https://mahout-rbm-netflix.s3.amazonaws.com/netflix-dataset-wodates.csv>.
This file does not contain dates, and is 1.5GB in
size.<https://mahout-rbm-netflix.s3.amazonaws.com/netflix-dataset-wodates.csv?torrent>
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Sisir Koppaka <si...@gmail.com>.
On Sun, Apr 4, 2010 at 4:10 PM, Sean Owen <sr...@gmail.com> wrote:
> I think you want to write this to accept "generic" data, and not
> necessarily assume the Netflix input format. I suggest you accept CSV
> data, in the form "userID,itemID,value", since that is what all the
> recommenders do.
>
> Sure, I'll write it for "userID, movieID, rating". Netflix also provides
dates but we can ignore it for the time being.
> You may need a quick utility program to convert Netflix data format to
> this. this wouldn't be part of the project, or else, we can put it in
> utils later.
>
> I have done this already. I have a 1.2GB CSV file containing all the 100
million records in the Netflix dataset as "userID, movieID, rating, date".
--
SK
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Sean Owen <sr...@gmail.com>.
I think you want to write this to accept "generic" data, and not
necessarily assume the Netflix input format. I suggest you accept CSV
data, in the form "userID,itemID,value", since that is what all the
recommenders do.
You may need a quick utility program to convert Netflix data format to
this. this wouldn't be part of the project, or else, we can put it in
utils later.
I don't think data storage is an issue here -- the files will live on
HDFS/S3, that's it. No code is needed. I don't think this has anything
to do with the classifier data stores unless I misunderstand the
project.
On Sun, Apr 4, 2010 at 11:17 AM, Sisir Koppaka <si...@gmail.com> wrote:
> Thanks, this is what I wanted to know. So, now, there would be a separate
> example that reads-in the Netflix dataset in a distributed way, that would
> be utilize the RBM implementation. Would that be right?
>
> The datastore I was referring to in the proposal was based on
> mahout.classifier.bayes.datastore. I understand the HBase, Cassandra and
> other adapters are being refactored out in a separate ticket, so I'll just
> stick with HDFS and S3.
>
> If there's anything else that I would need to add in the proposal, do let me
> know.
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Sisir Koppaka <si...@gmail.com>.
that would *be* utilize - sorry!
I'll start off by implementing the distributed Netfflix read-in, if that's
OK by you.
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Sisir Koppaka <si...@gmail.com>.
Thanks, this is what I wanted to know. So, now, there would be a separate
example that reads-in the Netflix dataset in a distributed way, that would
be utilize the RBM implementation. Would that be right?
The datastore I was referring to in the proposal was based on
mahout.classifier.bayes.datastore. I understand the HBase, Cassandra and
other adapters are being refactored out in a separate ticket, so I'll just
stick with HDFS and S3.
If there's anything else that I would need to add in the proposal, do let me
know.
On Sun, Apr 4, 2010 at 3:09 PM, Sean Owen <sr...@gmail.com> wrote:
> Reusing code is fine, in principle. The code you mention, however,
> will not help you much. It is non-distributed and has nothing to do
> with Hadoop. You might reuse a bit of code to parse the input files,
> that's about it.
>
> Which data store are you referring to... if I understand right, you
> are implementing an algorithm on Hadoop. You would definitely not
> implement anything to load into memory, and I think you want to work
> with HDFS and Amazon S3, not Hbase.
>
> On Sun, Apr 4, 2010 at 9:29 AM, Sisir Koppaka <si...@gmail.com>
> wrote:
> > Firstly, I am expecting to reuse the code at
> > *org.apache.mahout.cf.taste.example.netflix
> > *and have mentioned so in my proposal. Please let me know if this is OK,
> or
> > if you foresee any problems doing this. Secondly, I will implement a
> > HBase-based datastore as well as a InMemory-based one, but is the
> > InMemory-based one a pre-requisite for the HBase-based one to be used?
> > (Eventually everything has to go to memory, so is this being done
> elsewhere
> > or does the InMemory datastore do it?)
>
--
SK
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Sean Owen <sr...@gmail.com>.
Reusing code is fine, in principle. The code you mention, however,
will not help you much. It is non-distributed and has nothing to do
with Hadoop. You might reuse a bit of code to parse the input files,
that's about it.
Which data store are you referring to... if I understand right, you
are implementing an algorithm on Hadoop. You would definitely not
implement anything to load into memory, and I think you want to work
with HDFS and Amazon S3, not Hbase.
On Sun, Apr 4, 2010 at 9:29 AM, Sisir Koppaka <si...@gmail.com> wrote:
> Firstly, I am expecting to reuse the code at
> *org.apache.mahout.cf.taste.example.netflix
> *and have mentioned so in my proposal. Please let me know if this is OK, or
> if you foresee any problems doing this. Secondly, I will implement a
> HBase-based datastore as well as a InMemory-based one, but is the
> InMemory-based one a pre-requisite for the HBase-based one to be used?
> (Eventually everything has to go to memory, so is this being done elsewhere
> or does the InMemory datastore do it?)
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Sisir Koppaka <si...@gmail.com>.
Thanks Robin, Ted, Jake and Sean for your feedback. I've refined my
proposal, added in a milestone timeline, with design details, and have
submitted it at the GSoC site. The title of the proposal is *Restricted
Boltzmann Machines on the Netflix Dataset. Please do give me your feedback
on the proposal located
here<https://docs.google.com/fileview?id=0B-jUrudTSg7-ZTg3YTU5YTktZDBhZC00NWFiLTk4MTQtNzVlODZhOWEzYTU0&hl=en>
.*
I have a couple of queries that'd help me further refine my proposal.
Firstly, I am expecting to reuse the code at
*org.apache.mahout.cf.taste.example.netflix
*and have mentioned so in my proposal. Please let me know if this is OK, or
if you foresee any problems doing this. Secondly, I will implement a
HBase-based datastore as well as a InMemory-based one, but is the
InMemory-based one a pre-requisite for the HBase-based one to be used?
(Eventually everything has to go to memory, so is this being done elsewhere
or does the InMemory datastore do it?)
Thanking you,
Best regards,
Sisir Koppaka
Re: Reg. Netflix Prize Apache Mahout GSoC Application (SVD option)
Posted by Necati Batur <ne...@gmail.com>.
*IDEA:Create adapters for MYSQL and NOSQL(hbase, cassandra) to access data
for all the algorithms to use *
*Summary*
* *First of all,I am very excited to join an organization like
GSOC and most importantly work for a big open source Project apache.I am
looking for a good collaboration and new challenges on software
development.Especially information management issues sound great to me.I am
confident to work with all new technologies.I took the data structures I ,
II courses at university so I am ok with data structures.Most importantly I
am interested in databases.From my software engineering courses experience I
know how to work on a project by iterative development and timelining* *
*About Me*
I am a senior student at computer engineering at
iztech<http://english.iyte.edu.tr/main_eng.jsp?pageName=main.htm>in
turkey. My areas of inetrests are information management, OOP(Object
Oriented Programming) and currently bioinformatics. I have been working with
a Asistan Professor(Jens Allmer <http://jens.allmer.de/>) in molecular
biology genetics department for one year.Firstly, we worked on a protein
database 2DB <http://www.2db.de.ms/> and we presented the project in
HIBIT09<http://hibit09.ii.metu.edu.tr/>organization. The Project
was “Database management system independence by amending 2DB with a
database access layer”. Currently, I am working on another project (Kerb) as
my senior project which is a general sqeuential task management system
intend to reduce the errors and increase time saving in biological
experiments. We will present this project in
HIBIT2010<http://hibit2010.ii.metu.edu.tr/>too.
*My Offer for Project *
* *The data adapters fort he higher level languages will require
the good capability of using data structures and some information about
finite mathematics that I am confident on that issues.Then,the code given in
svn repository seems to need some improvements and also documetation.
Briefly,I would do the following operations fort his project
1. Understand the underlying maths for adapters
2. Determine the data structures that would be used for adapters
3. Implement the neccassary methods to handle creation of these
structures
4. Some test cases that we probably would need to check whether our code
cover all the issues required by a data retrieve operations
5. New iterations on the code to robust the algorithms
6. Documentation of overall project to join our particular Project to
overall scope
Re: Reg. Netflix Prize Apache Mahout GSoC Application (SVD option)
Posted by Richard Simon Just <in...@richardsimonjust.co.uk>.
Awesome guys,
Thanks for the quick responses! The details and clarifications are both
helpful and incredibly reassuring. I've never done a proposal before,
but no matter what happens I'm really looking forward to the end of my
exams so I can gear into Mahout properly.
Many thanks
Richard
Sean Owen wrote:
> Your audience is the project committers.
>
> I wouldn't spend much time rehashing the SVD theory. You should name
> your approach and I suppose write enough to make it clear you
> understand the algorithm enough to implement it. In this case you can
> assume we all understand the SVD well enough already.
>
> I think the proposal should rather focus on how you'd structure the
> implementation in the project, what the major classes are, and that
> you've thought reasonably about how long it'll take to build, test,
> and document.
>
> And to reiterate what Jake said, yeah there is already a fairly clear
> structure for Hadoop jobs in the recommender area -- you'd want to
> subclass AbstractJob and run series of Mappers/Reducers. You're going
> to emulate that for sure. You can probably reuse many of the Writable
> representations, in that package and in math or common, to represent
> the intermediate outputs.
>
> What's really key to your proposal is sketching the series of
> map-reduces that you'd drop into this structure to get the job done.
>
>
> On Mon, Apr 5, 2010 at 9:38 PM, Richard Simon Just
> <in...@richardsimonjust.co.uk> wrote:
>
>> I was wondering when it comes to the proposal what sort of background
>> detail should I be going into? Should I be talking about the use of SVD
>> within a recommender situation for example? Or given that the Mentors
>> already know this should I be discussing purely what sort of SVD-based
>> recommender implementation I'm planning? I guess a question beside the
>> question is am I aiming the proposal to people who are familiar with
>> Mahout and Machine Learning or to other people as well?
>>
>
>
Re: Reg. Netflix Prize Apache Mahout GSoC Application (SVD option)
Posted by Sean Owen <sr...@gmail.com>.
Your audience is the project committers.
I wouldn't spend much time rehashing the SVD theory. You should name
your approach and I suppose write enough to make it clear you
understand the algorithm enough to implement it. In this case you can
assume we all understand the SVD well enough already.
I think the proposal should rather focus on how you'd structure the
implementation in the project, what the major classes are, and that
you've thought reasonably about how long it'll take to build, test,
and document.
And to reiterate what Jake said, yeah there is already a fairly clear
structure for Hadoop jobs in the recommender area -- you'd want to
subclass AbstractJob and run series of Mappers/Reducers. You're going
to emulate that for sure. You can probably reuse many of the Writable
representations, in that package and in math or common, to represent
the intermediate outputs.
What's really key to your proposal is sketching the series of
map-reduces that you'd drop into this structure to get the job done.
On Mon, Apr 5, 2010 at 9:38 PM, Richard Simon Just
<in...@richardsimonjust.co.uk> wrote:
> I was wondering when it comes to the proposal what sort of background
> detail should I be going into? Should I be talking about the use of SVD
> within a recommender situation for example? Or given that the Mentors
> already know this should I be discussing purely what sort of SVD-based
> recommender implementation I'm planning? I guess a question beside the
> question is am I aiming the proposal to people who are familiar with
> Mahout and Machine Learning or to other people as well?
Re: Reg. Netflix Prize Apache Mahout GSoC Application (SVD option)
Posted by Jake Mannix <ja...@gmail.com>.
Hi Richard,
A few notes about what would be required to get a nice distributed SVD
recommender in Mahout: if you look at the current distributed recommenders
(in org.apache.mahout.cf.taste.hadoop package and children), you can see
how it works: using HDFS-backed data, a batch of recommendations is
computed for all users at once, with the output being another HDFS file,
which can then be used in a recommender.
A distributed SVD recommender would work roughly the same way -
there should be a class with a main() method which fires off a Hadoop
job to transform the data into sparse vector form, doing any weighting
or modification to the matrix (such as normalization), then use the
current DistributedLanczosSolver class to compute the SVD, and
use the resultant singular vectors and values to re-fill in the original
matrix, finding items to recommend (see the current in-memory
SVD-recommender to get a feel for how that part is done).
I hope this helps you understand a little of the scope of this part
of the project.
-jake
On Mon, Apr 5, 2010 at 1:38 PM, Richard Simon Just <
info@richardsimonjust.co.uk> wrote:
> Thanks for the super speedy response!
>
> Going on from what you said I've been reading up on the different SVD
> based variants used throughout the Netflix competition and working on my
> proposal. I'm focussing on what you suggested with aiming purely on the
> SVD-based recommender with the possibility of also optimizing the SVD code.
>
> I was wondering when it comes to the proposal what sort of background
> detail should I be going into? Should I be talking about the use of SVD
> within a recommender situation for example? Or given that the Mentors
> already know this should I be discussing purely what sort of SVD-based
> recommender implementation I'm planning? I guess a question beside the
> question is am I aiming the proposal to people who are familiar with
> Mahout and Machine Learning or to other people as well?
>
> Many thanks
> Richard
>
> Sean Owen wrote:
> > It'd be a matter of making a brand-new distributed recommender. It
> > need not have anything to do with SVDRecommender, which is a fine but
> > separate non-parallel implementation.
> >
> > Tacking on distributed slope-one is fairly easy, I think. Both
> > together, with testing, documentation, etc. are certainly big enough
> > for a GSoC project, probably a bit too large.
> >
> > I'd be pleased to see someone do a quite thorough job with an
> > SVD-based recommender, and perhaps along the way analyzing and
> > optimizing the SVD impl itself, and documenting and testing well and
> > so on. That's a nice project IMHO.
> >
> > On Thu, Apr 1, 2010 at 6:41 PM, Richard Simon Just
> > <in...@richardsimonjust.co.uk> wrote:
> >
> >> Just looking for some clarification. As a GSoC project would the SVD
> >> option mentioned below be a case of integrating the distributed SVD of
> >> MAHOUT-180 with the existing SVDRecommender?
> >>
> >> If so is there still a full GSoC project there? or would I need to
> >> combine it with say making the slope-one recommender fully distributed
> too?
> >>
> >> Many Thanks
> >> Richard
> >>
> >>
> >
> >
>
Re: Reg. Netflix Prize Apache Mahout GSoC Application (SVD option)
Posted by Richard Simon Just <in...@richardsimonjust.co.uk>.
Thanks for the super speedy response!
Going on from what you said I've been reading up on the different SVD
based variants used throughout the Netflix competition and working on my
proposal. I'm focussing on what you suggested with aiming purely on the
SVD-based recommender with the possibility of also optimizing the SVD code.
I was wondering when it comes to the proposal what sort of background
detail should I be going into? Should I be talking about the use of SVD
within a recommender situation for example? Or given that the Mentors
already know this should I be discussing purely what sort of SVD-based
recommender implementation I'm planning? I guess a question beside the
question is am I aiming the proposal to people who are familiar with
Mahout and Machine Learning or to other people as well?
Many thanks
Richard
Sean Owen wrote:
> It'd be a matter of making a brand-new distributed recommender. It
> need not have anything to do with SVDRecommender, which is a fine but
> separate non-parallel implementation.
>
> Tacking on distributed slope-one is fairly easy, I think. Both
> together, with testing, documentation, etc. are certainly big enough
> for a GSoC project, probably a bit too large.
>
> I'd be pleased to see someone do a quite thorough job with an
> SVD-based recommender, and perhaps along the way analyzing and
> optimizing the SVD impl itself, and documenting and testing well and
> so on. That's a nice project IMHO.
>
> On Thu, Apr 1, 2010 at 6:41 PM, Richard Simon Just
> <in...@richardsimonjust.co.uk> wrote:
>
>> Just looking for some clarification. As a GSoC project would the SVD
>> option mentioned below be a case of integrating the distributed SVD of
>> MAHOUT-180 with the existing SVDRecommender?
>>
>> If so is there still a full GSoC project there? or would I need to
>> combine it with say making the slope-one recommender fully distributed too?
>>
>> Many Thanks
>> Richard
>>
>>
>
>
Re: Reg. Netflix Prize Apache Mahout GSoC Application (SVD option)
Posted by Sean Owen <sr...@gmail.com>.
It'd be a matter of making a brand-new distributed recommender. It
need not have anything to do with SVDRecommender, which is a fine but
separate non-parallel implementation.
Tacking on distributed slope-one is fairly easy, I think. Both
together, with testing, documentation, etc. are certainly big enough
for a GSoC project, probably a bit too large.
I'd be pleased to see someone do a quite thorough job with an
SVD-based recommender, and perhaps along the way analyzing and
optimizing the SVD impl itself, and documenting and testing well and
so on. That's a nice project IMHO.
On Thu, Apr 1, 2010 at 6:41 PM, Richard Simon Just
<in...@richardsimonjust.co.uk> wrote:
> Just looking for some clarification. As a GSoC project would the SVD
> option mentioned below be a case of integrating the distributed SVD of
> MAHOUT-180 with the existing SVDRecommender?
>
> If so is there still a full GSoC project there? or would I need to
> combine it with say making the slope-one recommender fully distributed too?
>
> Many Thanks
> Richard
>
Re: Reg. Netflix Prize Apache Mahout GSoC Application (SVD option)
Posted by Richard Simon Just <in...@richardsimonjust.co.uk>.
Just looking for some clarification. As a GSoC project would the SVD
option mentioned below be a case of integrating the distributed SVD of
MAHOUT-180 with the existing SVDRecommender?
If so is there still a full GSoC project there? or would I need to
combine it with say making the slope-one recommender fully distributed too?
Many Thanks
Richard
Jake Mannix wrote:
> And to provide some options, I can say that I would certainly help, Sisir,
> with getting the distributed SVD into the recommender framework. While
> there is not much fundamental "computer science" left to that, there is
> a fair amount of high-performance *engineering* left to do in that
> direction.
>
> -jake
>
> On Mon, Mar 22, 2010 at 4:09 PM, Sean Owen <sr...@gmail.com> wrote:
>
>
>> I also second the recommendation to pick one of these ideas and focus
>> on it first, as it will be a lot more work to get it working,
>> documented, and tested!
>>
>> I personally like the idea of getting a distributed SVD-based
>> recommender into the project. The SVD works quite well and all we have
>> now is a non-parallel implementation.
>>
>> However I support Jake's suggestion more that RBM would be most useful
>> at the moment.
>>
>> Pick your area, dig in, and we can help you refine your ideas and begin.
>>
>> Sean
>>
>>
>
>
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Jake Mannix <ja...@gmail.com>.
And to provide some options, I can say that I would certainly help, Sisir,
with getting the distributed SVD into the recommender framework. While
there is not much fundamental "computer science" left to that, there is
a fair amount of high-performance *engineering* left to do in that
direction.
-jake
On Mon, Mar 22, 2010 at 4:09 PM, Sean Owen <sr...@gmail.com> wrote:
> I also second the recommendation to pick one of these ideas and focus
> on it first, as it will be a lot more work to get it working,
> documented, and tested!
>
> I personally like the idea of getting a distributed SVD-based
> recommender into the project. The SVD works quite well and all we have
> now is a non-parallel implementation.
>
> However I support Jake's suggestion more that RBM would be most useful
> at the moment.
>
> Pick your area, dig in, and we can help you refine your ideas and begin.
>
> Sean
>
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Sean Owen <sr...@gmail.com>.
I also second the recommendation to pick one of these ideas and focus
on it first, as it will be a lot more work to get it working,
documented, and tested!
I personally like the idea of getting a distributed SVD-based
recommender into the project. The SVD works quite well and all we have
now is a non-parallel implementation.
However I support Jake's suggestion more that RBM would be most useful
at the moment.
Pick your area, dig in, and we can help you refine your ideas and begin.
Sean
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Jake Mannix <ja...@gmail.com>.
Hi Sisir,
I'm the one who added the most recent SVD stuff to Mahout,
and while I'd love to see improvements in that, and incorporation
into netflix-style recommenders, I would even more like to see
a stacked-RBM implementation if you think you can do that. We
don't currently have anything like that in Mahout, and even if
it is completely serial (no Hadoop-hooks), it would be very
excellent as an addition to the project.
That's my opinion on the matter. :)
-jake
On Mon, Mar 22, 2010 at 1:53 PM, Sisir Koppaka <si...@gmail.com>wrote:
> Hi,
> Thanks a lot for taking time out to reply. I understand that it's important
> to get the proposal right - that's why I wanted to bounce off all
> possibilites as far as Netflix is concerned - the methods that I've worked
> with before, on this list, and see what would be of priority interest to
> the
> team. If global effects, and temporal SVD would be of interest then I'd
> incorporate that into my final proposal accordingly. On the other hand,
> I've
> read that RBM is something the team is interested in, so I could also
> implement a very good performing(approximately 0.91 RMSE) RBM for Netflix,
> as the GSoC project. I'd like to know which of the Netflix algorithms the
> Mahout team would like to see implemented first.
>
> Depending on the feedback, I'll prepare the final proposal. I'll definitely
> work with the code now and post any queries that I get on the list.
>
> Thanks a lot,
> Best regards,
> Sisir Koppaka
>
> On Tue, Mar 23, 2010 at 1:22 AM, Robin Anil <ro...@gmail.com> wrote:
>
> > Hi Sisir,
> > I am currently on vacation. So wont be able to review your
> > proposal fully. But from the looks of it what I would suggest you is to
> > target a somewhat lower and practical proposal. Trust me converting these
> > algorithms to map/reduce is not as easy as it sounds and most of the time
> > you would spend in debugging your code. Your work history is quite
> > impressive but whats more important here is getting your proposal right.
> > Sean has written most of the recommender code of Mahout and would be best
> > to
> > give you feedback as he has tried quite a number of approaches to
> > recommenders on map/reduce and knows very well, some of the constraints
> of
> > the framework. Feel free to explore the current Mahout recommenders code
> > and
> > ask on the list if you find anything confusing. But remember you are
> trying
> > to reproduce some of the cutting edge work in Recommendations over 2
> years
> > in a span of 10 weeks :) so stop and ponder over the feasibility. If you
> > still are good to go then prolly, you need to demonstrate something in
> > terms
> > of code during the proposal period(which is optional).
> >
> > Don't take this in the wrong way, its not meant to demotivate you. If we
> > can
> > get this into mahout, I am sure noone here would be objecting to it. So
> > your
> > good next step would be read, explore, think, discuss.
> >
> > Regards
> > Robin
> >
> >
> > On Mon, Mar 22, 2010 at 4:36 PM, Sisir Koppaka <sisir.koppaka@gmail.com
> > >wrote:
> >
> > > Dear Robin & the Apache Mahout team,
> > > I'm Sisir Koppaka, a third-year student from IIT Kharagpur, India. I've
> > > contributed to open source projects like FFmpeg earlier(Repository diff
> > > links are here<
> > >
> >
> http://git.ffmpeg.org/?p=ffmpeg;a=commitdiff;h=16a043535b91595bf34d7e044ef398067e7443e0
> > > >and
> > > here<
> > >
> >
> http://git.ffmpeg.org/?p=ffmpeg;a=commitdiff;h=9dde37a150ce2e5c53e2295d09efe289cebea9cd
> > > >
> > > ), and I am very interested to work on a project for Apache Mahout this
> > > year(the Netflix algorithms project, to be precise - mentored by
> Robin).
> > > Kindly let me explain my background so that I can make myself relevant
> in
> > > this context.
> > >
> > > I've done research work in meta-heuristics, including proposing the
> > > equivalents of local search and mutation for quantum-inspired
> algorithms,
> > > in
> > > my paper titled "*Superior Exploration-Exploitation Balance With
> > > Quantum-Inspired Hadamard Walks*", that was accepted as a late-breaking
> > > paper at GECCO 2010. We(myself and a friend - it was an independent
> > work),
> > > hope to send an expanded version of the communication to a journal in
> the
> > > near future. For this project, our language of implementation was in
> > > Mathematica, as we needed the combination of functional paradigms and
> > > available mathematically sound resources(like biased random number
> > > generation, simple linear programming functions etc.) as well as rapid
> > > prototyping ability.
> > >
> > > I have earlier interned in GE Research in their Computing and Decision
> > > Sciences Lab<
> > >
> http://ge.geglobalresearch.com/technologies/computing-decision-sciences/
> > > >last
> > > year, where I worked on machine learning techniques for large-scale
> > > databases - specifically on the Netflix Prize itself. Over a 2 month
> > > internship we rose from 1800 to 409th position on the Leaderboard, and
> > had
> > > implemented at least one variant of each of the major algorithms. The
> > > contest ended at the same time as the conclusion of our internship, and
> > the
> > > winning result was the combination of multiple variants of our
> > implemented
> > > algorithms.
> > >
> > > Interestingly, we did try to use Hadoop and the Map-Reduce model for
> the
> > > purpose based on a talk from a person from Yahoo! who visited us during
> > > that
> > > time. However, not having access to a cluster proved to be an impedance
> > for
> > > fast iterative development. We had one machine of 16 cores, so we
> > developed
> > > a toolkit in C++ that could multiprocess upto 16 threads(data input
> > > parallelization, rather than modifying the algorithms to suit the
> > > Map-Reduce
> > > model), and implemented all our algorithms using the same toolkit.
> > > Specifically, SVD, kNN Movie-Movie, kNN User-User, NSVD(Bellkor and
> other
> > > variants like the Paterek SVD, and the temporal SVD++ too) were the
> major
> > > algorithms that we implemented. Some algorithms had readily available
> > open
> > > source code for the Netflix Prize, like NSVD1, so we used them as well.
> > We
> > > also worked on certain regression schemes that could improve prediction
> > > accuracy like kernel-ridge regression, and it's optimization.
> > >
> > > Towards the end, we also attempted to verify the results of the
> infamous
> > > paper that showed that IMDB-Netflix correlation could destroy privacy,
> > and
> > > identify users. We would import IMDB datasets, and put them into a
> > database
> > > and then correlate the IMDB entries to Netflix(we matched double the
> > number
> > > of movies that the paper mentioned), and then verify the results. We
> also
> > > identified genre-wise trends and recorded them as such. Unfortuantely,
> > the
> > > paper resulted in a libel case, wherein Netflix surrendered it's rights
> > to
> > > hold future Prizes of this kind in return for withdrawal of charges.
> The
> > > case effectively closed the possibility of Netflix or any other company
> > > releasing similar datasets to the public pending further advances in
> > > privacy
> > > enforcement techniques, leaving the Netflix database as the largest of
> > it's
> > > kind.
> > >
> > > Naturally, it is very interesting if there is an opportunity to
> implement
> > > the same for Hadoop, since Netflix is the largest database of it's kind
> > and
> > > this would be of multiple uses - as a kickstart, tutorial, and as a
> > > performance testing(using an included segment of the total database)
> tool
> > > for grids. In addition, the Netflix and IMDB framework base code could
> be
> > > incredibly useful as a prototyping tool for algorithm designers who
> want
> > to
> > > design better machine learning algorithms/ensembles for large-scale
> > > databases. The lack of a decent scalable solution for the Netflix Prize
> > so
> > > that people can learn from it/add to it, is also a major disappointment
> > > that
> > > this proposal hopes to correct.
> > >
> > > Specifically, the challenge I am personally looking forward to is to
> > > implement some of these algorithms using the Map-Reduce model, which is
> > > what
> > > I missed out last time. I am looking forward to:
> > > 1. Account for the 12 global effects. The global effects were 12
> > > corrections
> > > made in the dataset to account for time, multiple votes on a single day
> > > etc., and these alone give a major boost to the accuracy of the
> > > predictions.
> > > 2. Implement at least 1 kNN based approach. Most of them differ in
> their
> > > parameters, or in their choice of distance definitions(Pearson, Cosine,
> > > Euclidean etc.)
> > > 3. Implement at least 1 SVD based temporal approach. While Mahout
> already
> > > possesses SVD implementations - slight variations of which could
> > replicate
> > > multiple SVD approaches for the Netflix Prize, the temporal SVD++ has
> in
> > my
> > > past experience been a very promising candidate that contributes a lot
> of
> > > perpendicular insight into the predictions.
> > > 4. RBM implementation. RBM's were found to offer distinct insights into
> > the
> > > predictions, and Mahout doesn't currently possess one implementation
> > yet(as
> > > Ankur C. Goel mentioned on this list a few days ago), so this is a
> > > no-brainer for a must-do implementation for the Netflix Prize GSoC
> > project.
> > > 5. Implementing at least 1 regression scheme relevant to the Netflix
> > Prize
> > > as part of the boiler plate code that would be required for this
> project
> > to
> > > facilitate further additions of algorithm variants. I'd like to do
> > > kernel-ridge regression, since it has, again, provided decent results
> on
> > > the
> > > Netflix dataset compared to other options. I need to discuss this part
> > with
> > > my mentor/the Apache Mahout team because while multiple regression
> > schemes
> > > are required for this project, I am not sure if it is necessary to
> > > implement
> > > this as a Map-Reduce based scheme, *at least within the scope of the
> GSoC
> > > project.* This is because it is not very compute-intensive, at least
> not
> > as
> > > much as the central algorithms for the Netflix Prize, and wouldn't be a
> > > critical limiting factor to successful completion of an 8% improvement
> > > project goal.
> > >
> > > The idea is that 1,2,5 would not take more than two weeks, with 3
> taking
> > > another two weeks and the rest of the time would be spent on 4. A
> > > demonstrated 8% improvement over Cinematch on the Netflix dataset would
> > be
> > > the project goal.
> > >
> > > There are plenty of references about the Grand Prize solution - Yehuda
> > > Koren's final summary<
> > > http://www.netflixprize.com/assets/GrandPrize2009_BPC_BellKor.pdf>is
> > > a great starting point. However, when I last worked on the problem
> > > this
> > > wasn't available, so I referred to papers by Arik Paterek and some of
> > > Bellkor's earlier papers.
> > >
> > > Looking forward to a discussion about the proposal,
> > > Thanks a lot,
> > > Best regards,
> > > Sisir Koppaka
> > >
> > > --
> > > SK
> > >
> >
>
>
>
> --
> SK
>
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Sisir Koppaka <si...@gmail.com>.
Hi,
Thanks a lot for taking time out to reply. I understand that it's important
to get the proposal right - that's why I wanted to bounce off all
possibilites as far as Netflix is concerned - the methods that I've worked
with before, on this list, and see what would be of priority interest to the
team. If global effects, and temporal SVD would be of interest then I'd
incorporate that into my final proposal accordingly. On the other hand, I've
read that RBM is something the team is interested in, so I could also
implement a very good performing(approximately 0.91 RMSE) RBM for Netflix,
as the GSoC project. I'd like to know which of the Netflix algorithms the
Mahout team would like to see implemented first.
Depending on the feedback, I'll prepare the final proposal. I'll definitely
work with the code now and post any queries that I get on the list.
Thanks a lot,
Best regards,
Sisir Koppaka
On Tue, Mar 23, 2010 at 1:22 AM, Robin Anil <ro...@gmail.com> wrote:
> Hi Sisir,
> I am currently on vacation. So wont be able to review your
> proposal fully. But from the looks of it what I would suggest you is to
> target a somewhat lower and practical proposal. Trust me converting these
> algorithms to map/reduce is not as easy as it sounds and most of the time
> you would spend in debugging your code. Your work history is quite
> impressive but whats more important here is getting your proposal right.
> Sean has written most of the recommender code of Mahout and would be best
> to
> give you feedback as he has tried quite a number of approaches to
> recommenders on map/reduce and knows very well, some of the constraints of
> the framework. Feel free to explore the current Mahout recommenders code
> and
> ask on the list if you find anything confusing. But remember you are trying
> to reproduce some of the cutting edge work in Recommendations over 2 years
> in a span of 10 weeks :) so stop and ponder over the feasibility. If you
> still are good to go then prolly, you need to demonstrate something in
> terms
> of code during the proposal period(which is optional).
>
> Don't take this in the wrong way, its not meant to demotivate you. If we
> can
> get this into mahout, I am sure noone here would be objecting to it. So
> your
> good next step would be read, explore, think, discuss.
>
> Regards
> Robin
>
>
> On Mon, Mar 22, 2010 at 4:36 PM, Sisir Koppaka <sisir.koppaka@gmail.com
> >wrote:
>
> > Dear Robin & the Apache Mahout team,
> > I'm Sisir Koppaka, a third-year student from IIT Kharagpur, India. I've
> > contributed to open source projects like FFmpeg earlier(Repository diff
> > links are here<
> >
> http://git.ffmpeg.org/?p=ffmpeg;a=commitdiff;h=16a043535b91595bf34d7e044ef398067e7443e0
> > >and
> > here<
> >
> http://git.ffmpeg.org/?p=ffmpeg;a=commitdiff;h=9dde37a150ce2e5c53e2295d09efe289cebea9cd
> > >
> > ), and I am very interested to work on a project for Apache Mahout this
> > year(the Netflix algorithms project, to be precise - mentored by Robin).
> > Kindly let me explain my background so that I can make myself relevant in
> > this context.
> >
> > I've done research work in meta-heuristics, including proposing the
> > equivalents of local search and mutation for quantum-inspired algorithms,
> > in
> > my paper titled "*Superior Exploration-Exploitation Balance With
> > Quantum-Inspired Hadamard Walks*", that was accepted as a late-breaking
> > paper at GECCO 2010. We(myself and a friend - it was an independent
> work),
> > hope to send an expanded version of the communication to a journal in the
> > near future. For this project, our language of implementation was in
> > Mathematica, as we needed the combination of functional paradigms and
> > available mathematically sound resources(like biased random number
> > generation, simple linear programming functions etc.) as well as rapid
> > prototyping ability.
> >
> > I have earlier interned in GE Research in their Computing and Decision
> > Sciences Lab<
> > http://ge.geglobalresearch.com/technologies/computing-decision-sciences/
> > >last
> > year, where I worked on machine learning techniques for large-scale
> > databases - specifically on the Netflix Prize itself. Over a 2 month
> > internship we rose from 1800 to 409th position on the Leaderboard, and
> had
> > implemented at least one variant of each of the major algorithms. The
> > contest ended at the same time as the conclusion of our internship, and
> the
> > winning result was the combination of multiple variants of our
> implemented
> > algorithms.
> >
> > Interestingly, we did try to use Hadoop and the Map-Reduce model for the
> > purpose based on a talk from a person from Yahoo! who visited us during
> > that
> > time. However, not having access to a cluster proved to be an impedance
> for
> > fast iterative development. We had one machine of 16 cores, so we
> developed
> > a toolkit in C++ that could multiprocess upto 16 threads(data input
> > parallelization, rather than modifying the algorithms to suit the
> > Map-Reduce
> > model), and implemented all our algorithms using the same toolkit.
> > Specifically, SVD, kNN Movie-Movie, kNN User-User, NSVD(Bellkor and other
> > variants like the Paterek SVD, and the temporal SVD++ too) were the major
> > algorithms that we implemented. Some algorithms had readily available
> open
> > source code for the Netflix Prize, like NSVD1, so we used them as well.
> We
> > also worked on certain regression schemes that could improve prediction
> > accuracy like kernel-ridge regression, and it's optimization.
> >
> > Towards the end, we also attempted to verify the results of the infamous
> > paper that showed that IMDB-Netflix correlation could destroy privacy,
> and
> > identify users. We would import IMDB datasets, and put them into a
> database
> > and then correlate the IMDB entries to Netflix(we matched double the
> number
> > of movies that the paper mentioned), and then verify the results. We also
> > identified genre-wise trends and recorded them as such. Unfortuantely,
> the
> > paper resulted in a libel case, wherein Netflix surrendered it's rights
> to
> > hold future Prizes of this kind in return for withdrawal of charges. The
> > case effectively closed the possibility of Netflix or any other company
> > releasing similar datasets to the public pending further advances in
> > privacy
> > enforcement techniques, leaving the Netflix database as the largest of
> it's
> > kind.
> >
> > Naturally, it is very interesting if there is an opportunity to implement
> > the same for Hadoop, since Netflix is the largest database of it's kind
> and
> > this would be of multiple uses - as a kickstart, tutorial, and as a
> > performance testing(using an included segment of the total database) tool
> > for grids. In addition, the Netflix and IMDB framework base code could be
> > incredibly useful as a prototyping tool for algorithm designers who want
> to
> > design better machine learning algorithms/ensembles for large-scale
> > databases. The lack of a decent scalable solution for the Netflix Prize
> so
> > that people can learn from it/add to it, is also a major disappointment
> > that
> > this proposal hopes to correct.
> >
> > Specifically, the challenge I am personally looking forward to is to
> > implement some of these algorithms using the Map-Reduce model, which is
> > what
> > I missed out last time. I am looking forward to:
> > 1. Account for the 12 global effects. The global effects were 12
> > corrections
> > made in the dataset to account for time, multiple votes on a single day
> > etc., and these alone give a major boost to the accuracy of the
> > predictions.
> > 2. Implement at least 1 kNN based approach. Most of them differ in their
> > parameters, or in their choice of distance definitions(Pearson, Cosine,
> > Euclidean etc.)
> > 3. Implement at least 1 SVD based temporal approach. While Mahout already
> > possesses SVD implementations - slight variations of which could
> replicate
> > multiple SVD approaches for the Netflix Prize, the temporal SVD++ has in
> my
> > past experience been a very promising candidate that contributes a lot of
> > perpendicular insight into the predictions.
> > 4. RBM implementation. RBM's were found to offer distinct insights into
> the
> > predictions, and Mahout doesn't currently possess one implementation
> yet(as
> > Ankur C. Goel mentioned on this list a few days ago), so this is a
> > no-brainer for a must-do implementation for the Netflix Prize GSoC
> project.
> > 5. Implementing at least 1 regression scheme relevant to the Netflix
> Prize
> > as part of the boiler plate code that would be required for this project
> to
> > facilitate further additions of algorithm variants. I'd like to do
> > kernel-ridge regression, since it has, again, provided decent results on
> > the
> > Netflix dataset compared to other options. I need to discuss this part
> with
> > my mentor/the Apache Mahout team because while multiple regression
> schemes
> > are required for this project, I am not sure if it is necessary to
> > implement
> > this as a Map-Reduce based scheme, *at least within the scope of the GSoC
> > project.* This is because it is not very compute-intensive, at least not
> as
> > much as the central algorithms for the Netflix Prize, and wouldn't be a
> > critical limiting factor to successful completion of an 8% improvement
> > project goal.
> >
> > The idea is that 1,2,5 would not take more than two weeks, with 3 taking
> > another two weeks and the rest of the time would be spent on 4. A
> > demonstrated 8% improvement over Cinematch on the Netflix dataset would
> be
> > the project goal.
> >
> > There are plenty of references about the Grand Prize solution - Yehuda
> > Koren's final summary<
> > http://www.netflixprize.com/assets/GrandPrize2009_BPC_BellKor.pdf>is
> > a great starting point. However, when I last worked on the problem
> > this
> > wasn't available, so I referred to papers by Arik Paterek and some of
> > Bellkor's earlier papers.
> >
> > Looking forward to a discussion about the proposal,
> > Thanks a lot,
> > Best regards,
> > Sisir Koppaka
> >
> > --
> > SK
> >
>
--
SK
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Ted Dunning <te...@gmail.com>.
It is also typically the case that about 2/3 of the project consists of
moving the code from "working" to "usable". That involves writing up
examples, wiki pages and ironing out strangeness in how the program is
invoked or how the output might be consumed.
On Mon, Mar 22, 2010 at 12:52 PM, Robin Anil <ro...@gmail.com> wrote:
> But from the looks of it what I would suggest you is to
> target a somewhat lower and practical proposal. Trust me converting these
> algorithms to map/reduce is not as easy as it sounds and most of the time
> you would spend in debugging your code.
>
Re: Reg. Netflix Prize Apache Mahout GSoC Application
Posted by Robin Anil <ro...@gmail.com>.
Hi Sisir,
I am currently on vacation. So wont be able to review your
proposal fully. But from the looks of it what I would suggest you is to
target a somewhat lower and practical proposal. Trust me converting these
algorithms to map/reduce is not as easy as it sounds and most of the time
you would spend in debugging your code. Your work history is quite
impressive but whats more important here is getting your proposal right.
Sean has written most of the recommender code of Mahout and would be best to
give you feedback as he has tried quite a number of approaches to
recommenders on map/reduce and knows very well, some of the constraints of
the framework. Feel free to explore the current Mahout recommenders code and
ask on the list if you find anything confusing. But remember you are trying
to reproduce some of the cutting edge work in Recommendations over 2 years
in a span of 10 weeks :) so stop and ponder over the feasibility. If you
still are good to go then prolly, you need to demonstrate something in terms
of code during the proposal period(which is optional).
Don't take this in the wrong way, its not meant to demotivate you. If we can
get this into mahout, I am sure noone here would be objecting to it. So your
good next step would be read, explore, think, discuss.
Regards
Robin
On Mon, Mar 22, 2010 at 4:36 PM, Sisir Koppaka <si...@gmail.com>wrote:
> Dear Robin & the Apache Mahout team,
> I'm Sisir Koppaka, a third-year student from IIT Kharagpur, India. I've
> contributed to open source projects like FFmpeg earlier(Repository diff
> links are here<
> http://git.ffmpeg.org/?p=ffmpeg;a=commitdiff;h=16a043535b91595bf34d7e044ef398067e7443e0
> >and
> here<
> http://git.ffmpeg.org/?p=ffmpeg;a=commitdiff;h=9dde37a150ce2e5c53e2295d09efe289cebea9cd
> >
> ), and I am very interested to work on a project for Apache Mahout this
> year(the Netflix algorithms project, to be precise - mentored by Robin).
> Kindly let me explain my background so that I can make myself relevant in
> this context.
>
> I've done research work in meta-heuristics, including proposing the
> equivalents of local search and mutation for quantum-inspired algorithms,
> in
> my paper titled "*Superior Exploration-Exploitation Balance With
> Quantum-Inspired Hadamard Walks*", that was accepted as a late-breaking
> paper at GECCO 2010. We(myself and a friend - it was an independent work),
> hope to send an expanded version of the communication to a journal in the
> near future. For this project, our language of implementation was in
> Mathematica, as we needed the combination of functional paradigms and
> available mathematically sound resources(like biased random number
> generation, simple linear programming functions etc.) as well as rapid
> prototyping ability.
>
> I have earlier interned in GE Research in their Computing and Decision
> Sciences Lab<
> http://ge.geglobalresearch.com/technologies/computing-decision-sciences/
> >last
> year, where I worked on machine learning techniques for large-scale
> databases - specifically on the Netflix Prize itself. Over a 2 month
> internship we rose from 1800 to 409th position on the Leaderboard, and had
> implemented at least one variant of each of the major algorithms. The
> contest ended at the same time as the conclusion of our internship, and the
> winning result was the combination of multiple variants of our implemented
> algorithms.
>
> Interestingly, we did try to use Hadoop and the Map-Reduce model for the
> purpose based on a talk from a person from Yahoo! who visited us during
> that
> time. However, not having access to a cluster proved to be an impedance for
> fast iterative development. We had one machine of 16 cores, so we developed
> a toolkit in C++ that could multiprocess upto 16 threads(data input
> parallelization, rather than modifying the algorithms to suit the
> Map-Reduce
> model), and implemented all our algorithms using the same toolkit.
> Specifically, SVD, kNN Movie-Movie, kNN User-User, NSVD(Bellkor and other
> variants like the Paterek SVD, and the temporal SVD++ too) were the major
> algorithms that we implemented. Some algorithms had readily available open
> source code for the Netflix Prize, like NSVD1, so we used them as well. We
> also worked on certain regression schemes that could improve prediction
> accuracy like kernel-ridge regression, and it's optimization.
>
> Towards the end, we also attempted to verify the results of the infamous
> paper that showed that IMDB-Netflix correlation could destroy privacy, and
> identify users. We would import IMDB datasets, and put them into a database
> and then correlate the IMDB entries to Netflix(we matched double the number
> of movies that the paper mentioned), and then verify the results. We also
> identified genre-wise trends and recorded them as such. Unfortuantely, the
> paper resulted in a libel case, wherein Netflix surrendered it's rights to
> hold future Prizes of this kind in return for withdrawal of charges. The
> case effectively closed the possibility of Netflix or any other company
> releasing similar datasets to the public pending further advances in
> privacy
> enforcement techniques, leaving the Netflix database as the largest of it's
> kind.
>
> Naturally, it is very interesting if there is an opportunity to implement
> the same for Hadoop, since Netflix is the largest database of it's kind and
> this would be of multiple uses - as a kickstart, tutorial, and as a
> performance testing(using an included segment of the total database) tool
> for grids. In addition, the Netflix and IMDB framework base code could be
> incredibly useful as a prototyping tool for algorithm designers who want to
> design better machine learning algorithms/ensembles for large-scale
> databases. The lack of a decent scalable solution for the Netflix Prize so
> that people can learn from it/add to it, is also a major disappointment
> that
> this proposal hopes to correct.
>
> Specifically, the challenge I am personally looking forward to is to
> implement some of these algorithms using the Map-Reduce model, which is
> what
> I missed out last time. I am looking forward to:
> 1. Account for the 12 global effects. The global effects were 12
> corrections
> made in the dataset to account for time, multiple votes on a single day
> etc., and these alone give a major boost to the accuracy of the
> predictions.
> 2. Implement at least 1 kNN based approach. Most of them differ in their
> parameters, or in their choice of distance definitions(Pearson, Cosine,
> Euclidean etc.)
> 3. Implement at least 1 SVD based temporal approach. While Mahout already
> possesses SVD implementations - slight variations of which could replicate
> multiple SVD approaches for the Netflix Prize, the temporal SVD++ has in my
> past experience been a very promising candidate that contributes a lot of
> perpendicular insight into the predictions.
> 4. RBM implementation. RBM's were found to offer distinct insights into the
> predictions, and Mahout doesn't currently possess one implementation yet(as
> Ankur C. Goel mentioned on this list a few days ago), so this is a
> no-brainer for a must-do implementation for the Netflix Prize GSoC project.
> 5. Implementing at least 1 regression scheme relevant to the Netflix Prize
> as part of the boiler plate code that would be required for this project to
> facilitate further additions of algorithm variants. I'd like to do
> kernel-ridge regression, since it has, again, provided decent results on
> the
> Netflix dataset compared to other options. I need to discuss this part with
> my mentor/the Apache Mahout team because while multiple regression schemes
> are required for this project, I am not sure if it is necessary to
> implement
> this as a Map-Reduce based scheme, *at least within the scope of the GSoC
> project.* This is because it is not very compute-intensive, at least not as
> much as the central algorithms for the Netflix Prize, and wouldn't be a
> critical limiting factor to successful completion of an 8% improvement
> project goal.
>
> The idea is that 1,2,5 would not take more than two weeks, with 3 taking
> another two weeks and the rest of the time would be spent on 4. A
> demonstrated 8% improvement over Cinematch on the Netflix dataset would be
> the project goal.
>
> There are plenty of references about the Grand Prize solution - Yehuda
> Koren's final summary<
> http://www.netflixprize.com/assets/GrandPrize2009_BPC_BellKor.pdf>is
> a great starting point. However, when I last worked on the problem
> this
> wasn't available, so I referred to papers by Arik Paterek and some of
> Bellkor's earlier papers.
>
> Looking forward to a discussion about the proposal,
> Thanks a lot,
> Best regards,
> Sisir Koppaka
>
> --
> SK
>