ICML-98 Submission #78

Collaborative Filtering using Weighted Majority Prediction Algorithms 

Atsuyoshi Nakamura and Naoki Abe 
NEC C&C Media Research Laboratories 
4-1-1 Miyazaki, Miyamae-ku, Kawasaki 216-8555 JAPAN

Abstract

We apply various generalizations of weighted majority
prediction algorithms for on-line prediction of binary relations to
the problem of predicting personal preferences over information
contents, which is a key issue in collaborative filtering.  Note that
the collaborative filtering problem can be casted as learning a binary
relation between the users (as the rows) and the contents (as the
columns).  The original prediction algorithm of Goldman and Warmuth
[GW95] makes its prediction by majority voting by the rows with
observed data in the same column, weighted by the believed similarity
between the rows.  In the present paper, we propose a generalization
`G-Learn-Relation' of their algorithm to the multi-valued setting, and
empirically demonstrate that it performs better than existing
filtering methods based on correlation coefficients, both on simulated
and real data.  The performance comparison was done in terms of the
total number of prediction mistakes and the measures of precision and
recall.  Additionally, we propose a version of G-Learn-Relation that
makes use of indirect evidence available as believed similarity
between other rows, and another version in which both row similarity
and column similarity are used for prediction.  In both cases,
significant improvement was observed in experiments involving
simulated data.  Finally, we give a theoretical performance guarantee
for G-Learn-Relation in terms of an upper bound on the worst case
number of mistakes, which together with a lower bound on the number of
mistakes made by a correlation-based method establishes that it
performs better in theory as well as in practice.

Keywords:
Information Filtering, Collaborative Filtering, Binary Relation,
Weighted Majority

Email: {atsu,abe}@ccm.cl.nec.co.jp

Tel: +81-44-856-2143