Mailing-List: contact user-help@mahout.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@mahout.apache.org
Received-SPF: pass (athena.apache.org: domain of ssc.open@googlemail.com
 designates 209.85.215.42 as permitted sender)
Message-ID: <4E1F05C1.8040203@apache.org>
Date: Thu, 14 Jul 2011 17:05:37 +0200
From: Sebastian Schelter <ssc@apache.org>
Reply-To: ssc@apache.org
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US;
 rv:1.9.2.17) Gecko/20110424 Lightning/1.0b2 Thunderbird/3.1.10
MIME-Version: 1.0
To: user@mahout.apache.org
Subject: Re: Understanding mahout's recommendation system parameters
References: 
 <CANon9ZPtX7Fv9zBUdjRc=JNeTJ0kRZiQxotzCjvMh5p6VrErGw@mail.gmail.com>
In-Reply-To: 
 <CANon9ZPtX7Fv9zBUdjRc=JNeTJ0kRZiQxotzCjvMh5p6VrErGw@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Hi Jack,

trying to answer your questions as detailed as possible:

Regarding point 2) --maxSimilaritiesPerItem

RecommenderJob uses Itembased Collaborative Filtering to compute the 
recommendations and is a parallelized implementation of the algorithm 
presented in [1]. The main idea is to use a "neighbourhood" of similar 
items that have already been rated by a user to estimate his/her 
preference towards an unknown item. These similar items are found by 
comparing the ratings of frequently co-rated items according to some 
similarity measure. The parameter --maxSimilaritiesPerItem lets you 
specify the number of similar items per item to consider when estimating 
preferences towards an unknown item. Usually a small number of items 
should be sufficient, have a look into [1] for some numbers and experiments.

Regarding point 1) --maxCooccurrencesPerItem

In order to compute the item-item-similarities a naive approach would 
have to consider all possible pairs of items which has quadratic 
complexity and obviously won't scale.

RowSimilarityJob which is at the heart of both RecommenderJob and 
ItemSimilarityJob ensures that only pairs of items that have at least 
been co-rated once are taken into consideration which helps a lot in 
recommendation usecases as most users have only rated a very small 
number of items.

However if you look at the distribution of the number of ratings per 
user or per item, it will usually follow a heavily tailed distribution, 
which means that there is a small number of items ("topsellers") with an 
exorbitant number of ratings as well as a small number of users 
("powerusers") that show the same behavior.

These powerusers and topsellers might slow down the similarity 
computation orders of magnitude (as all pairs of items that have been 
co-rated have to be considered which is still quadratic growth) without 
providing a lot of additional insight. I think Ted wrote a mail to this 
list some time ago where he confirmed this observation from his experience.

So we need some way to sample down these ratings which is done in 
MaybePruneRowsMapper with a very simple heuristic using 
--maxCooccurrencesPerItem that only looks at the portion of data 
available for that single mapper instance and might throw away ratings 
for very frequently rated items.

I think this is a point where a lot of optimization is possible, Mahout 
should provide support for customizable sampling strategies here, like 
looking only at the x latest ratings of a user for example.


--sebastian

[1] Sarwar et. al. "Itembased Collaborative Filtering Algorithms" 
http://portal.acm.org/citation.cfm?id=372071


On 14.07.2011 16:11, Kris Jack wrote:
> Hello,
>
> I'm trying to get a better understanding of the following 2 RecommenderJob
> parameters:
> 1) --maxCooccurrencesPerItem (integer): Maximum number of cooccurrences
> considered per item (100)
> 2) --maxSimilaritiesPerItem (integer): Maximum number of similarities
> considered per item (100)
>
> Could you please help me to understand these in terms of a recommender job
> where we are trying to recommend items to users?
>
>  From what I see, maxCooccurrencesPerItem first gets used in job 4/12 in the
> pipeline, the MaybePruneRowsMapper job.  Does maxCooccurrencesPerItem limit
> the number of cooccurrences that are kept for that item?  Is this limit
> within a single user's set of items or globally for all users?  For example,
> if a user has 100 items then each item can be seen to cooccur with the 99
> other items.  Taking all user libraries, however, assume that it cooccurs
> with 1,000,000 other items.  Does maxCooccurrencesPerItem limit the number
> of cooccurrences on a user item set basis or is this applied to the set of
> items with which the item cooccurs with regard to all user libraries?  Also,
> how is the selection made (most frequent or first found)?
>
> maxSimilaritiesPerItem first gets used in job 7/12 in the pipeline,
> EntriesToVectorsReducer.  Does this cap the number of rows that are compared
> with one another?  Are the rows cooccurrence vectors of items for a given
> user by this point in the process?
>
> Thanks,
> Kris
>