Summary of “Evaluation Collaborative Filtering Recommender Systems”

The following is a short summary of:
J. Herlocker, J. Konstan, L. Terveen, and J. Riedl. Evaluating collaborative filtering recommender systems. ACM Transactions on Information Systems (TOIS), 22(1):5--53, 2004.

Commonly observed user tasks from recommender systems are as follow:
-. Annotation in context : Uses a recommender in an existing context. E.g., Overlay prediction information on top of existing links
-. Find good items : Video recommender, Item recommender, etc
-. Find All Good Items : purpose is to lower false negative rate
-. Recommend sequence : can be interesting
-. Find credible recommender : making the system more credible

Ratings can be explicit (users rate directly) or implicit (inferred from users behavior or preferences)

Commonly used evaluation metrics are:
1. Predictive accuracy
-. MAE (Mean Absolute Error) = (\sum (p_i – r_i))/N
-. MSE (Mean Square Error) = (\sum (p_i – r_i)^2)/N
-. RMSE (Root Mean Square Error) = \sqrt (MSE)
2. Classification accuracy
-. Precision : the ratio of relevant items selected to number of items selected
-. Recall : the ratio of relevant items selected to total number of relevant items available (Note: Precision and recall are inversely related.)
-. MAP(Mean Average Precision, aka F1) = 2PR/(P+R)

Netflix Prize for the best collaborative filtering algorithm

Collaborative filtering, also known as social tagging, is much more popular these days in the Internet but it’s not so clear yet how much and what kind of information we can extract from the system. Regarding this problem, I think Netflix prize would be a great challenge to make those questions clear out.

@. What to predict?

Simple. From the training set, provided by Netflix, which contains over 100M movie 1-to-5 scale ratings, we need to predict unknown movie ratings for the given qualifying set. More specifically, each data in the training set is quadruple of <user, movie, date of grade, grade> and the qualifying set is given <user, movie, date of grade, unknown grade>. We need to fill out the unknown grades by prediction and submit them for evaluation.

Besides two data sets, the training and qualifying set, Netflix provides the probe set which is a problem set with answers. With this, we can roughly estimate the accuracy without consulting with the scoring oracle.

@. How to predict?

Hard. However, we can learn from the front-runners, posted at the Leaderboard. The first annual progress winner is BellKor and they wrote about their algorithm.

@. Number-wise story

#. of data in the training set = 100,480,507
#. of users in the training set = 480,189
#. of movies in the training set = 17,770
#. of data to predict in the qualifying set = 2,817,131
#. of data in the probe set = 1,408,395

@. Research problems

As a student, trying to apply machine learning algorithms to various applications, it is interesting to study:

1. What kind of machine learning algorithms can be applied to analyze the Netflix collaborative filtering data? Furthermore, Can we find more general algorithms can be used for the data in the net?
2. How such computations can be expedited by using parallel, multi-core platform? Interestingly, is it possible to use other computing powers, such as cloud computing?
3. Can we improve accuracy by adding other information easily accessible from the Internet? What kind of infrastructure of the Internet can help this? Web2.0 or else?

@. Reading list

J. Herlocker, J. Konstan, L. Terveen, and J. Riedl. Evaluating collaborative filtering recommender systems. ACM Transactions on Information Systems (TOIS), 22(1):5--53, 2004.

R. Bell, Y. Koren, and C. Volinsky. Modeling relationships at multiple scales to improve accuracy of large recommender systems. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 95--104, 2007

R. Bell and Y. Koren. Improved Neighborhood-based Collaborative Filtering. KDD-Cup and Workshop.

R. M. Bell and Y. Koren, Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weights, Proc. IEEE International Conference on Data Mining (ICDM'07), 2007

Possible useful papers can be found from the Internet. I will keep this list up-to-date, as I read through.

PMPP workshop at NCSA

I attended PMPP (Programming Massively Parallel Processors Agenda) workshop at NCSA last week (July 10th, 2008). It was great opportunity to see what we can do with parallel processors and modern powerful GPUs. Recently Multi-core or many-core has been drawing great attentions in various research communities and people are still struggling to find a way to maximize its capabilities in the coming 80-core era. In other side, Peoples have been also trying to utilize GPUs as a parallel computing unit. Modern GPUs are equipped  with tens of, or hundreds of cores, which can be used for computing intensive jobs. The workshop was about all of these: Multicores and GPUs.

Here are some highlights:

• Parallel GPU: Mostly two venders, nVidia and ATI, are actively developing this market by continually supplying powerful hardware and SDKs. nVidia provides CUDA and ATI does Stream SDK for programming kits.
• nVidia's parallel GPU with CUDA: Lightweight threads running on nVidia GPU (8 to 240 cores). Designed with parallel execution in mind, while general CPU is not. GPU can be considered as massively parallel manycore machine.
• Autotuning for multicore : Multicore tuning parameter spaces are so huge to investigate one by one. We can overcome this by systematic approaches. Details can be seen from the papers by Samuel Williams and Kaushik Datta. In their paper, many multicore tuning techniques are introduced.
• Cell broadband engine (Cell BE): Interesting demonstration was shown by Hema Reddy from IBM. Look at this article and clip. I saw the more interesting clip in the workshop but I can't find the exact one in the Internet.
• Multicore/GPU researchers : look at Pedro Trancoso, John Stone, and