You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@mahout.apache.org by Bill Mccormick <bi...@gmail.com> on 2012/06/11 20:42:45 UTC

Scalability of ParallelALSFactorizationJob with implicit feedback

Hi all,

We're interested in using Mahout for a recommendation system for a largish
online storefront.

The initial recommendations are based on download/purchase history, so we
were trying out the ParallelALSFactorizationJob which seems to give good
results.

The initial test run was limited to 100,000 users and the job ran with no
problems.

The next test set was structured differently with around 4M download
records and around 1.5 M users (rather than a fixed number of users, it was
the set of downloads over a fixed period of time).   The Hadoop tasks hung
in garbage collection on this job.

I started looking at memory usage, and I noticed that the existing
implementation attempts to compute the product of the user factor matrix
transpose with itself in memory.  (It also looks like it does this on every
mapper, instead of once per iteration.)

Our full data set has on the order of 100M users.    So this isn't going to
work as is.  (i.e. the user factor matrix will take 100M users x 20 factors
x 8 bytes per entry = 16 Gbytes)

I'm just pondering implementing a new version that does the large matrix
computations in a less memory intensive fashion.   Before I go too far, I
was hoping this list could provide some input:

- is my analysis correct?
- is someone already working on this?
- if we go ahead with this, is the Mahout project interested in accepting
the new implementation once it's done?

thank you very much.

-- 
Bill McCormick

Re: Scalability of ParallelALSFactorizationJob with implicit feedback

Posted by Sean Owen <sr...@gmail.com>.
PS on this point, I've had great success locally by keeping the
user-feature or item-feature matrix out of memory, and on disk in the
form of a Hadoop MapFile, and then putting a large cache on top.
Caching works quite well since the number of items (users) that appear
frequently is small. You pay extra overhead for all the lookups in the
MapFile, but that can be helped somewhat by tuning its indexing
factor. In the end I have found you save a surprising amount of time
vs loading the whole thing just because of the frequency distribution
-- many users/items, even most, need never be touched by a reducer.

On Mon, Jun 11, 2012 at 8:19 PM, Sean Owen <sr...@gmail.com> wrote:
> If you like ALS on Hadoop, I don't mind again plugging the Myrrix
> Computation Layer (http://myrrix.com/documentation-computation-layer/), a
> sort of spin off of this kind of work I've been doing in Mahout (though not
> this class) that I've done a lot to optimize. I think it's about as swift as
> this will be on Hadoop -- and ALS does fit Hadoop quite well. Email off-list
> if you want to try it out.
>
>
>> > I started looking at memory usage, and I noticed that the existing
>> > implementation attempts to compute the product of the user factor matrix
>> > transpose with itself in memory.  (It also looks like it does this on
>> > every
>> > mapper, instead of once per iteration.)
>> >
>> > Our full data set has on the order of 100M users.    So this isn't going
>> > to
>> > work as is.  (i.e. the user factor matrix will take 100M users x 20
>> > factors
>> > x 8 bytes per entry = 16 Gbytes)
>> >
>> > I'm just pondering implementing a new version that does the large matrix
>> > computations in a less memory intensive fashion.   Before I go too far,
>> > I
>> > was hoping this list could provide some input:
>

Re: Scalability of ParallelALSFactorizationJob with implicit feedback

Posted by Sean Owen <sr...@gmail.com>.
ParallelALSFactorizationJob? No, not based on co-occurrence. This is just a
matrix-factorization approach using alternating least squares as opposed to
say SGD to solve for the factors.

On Mon, Jun 11, 2012 at 8:28 PM, Ted Dunning <te...@gmail.com> wrote:

> Decomposition techniques do help with this, but it sounds like the OP was
> using one of the cooccurrence based techniques.
>
>

Re: Scalability of ParallelALSFactorizationJob with implicit feedback

Posted by Ted Dunning <te...@gmail.com>.
Decomposition techniques do help with this, but it sounds like the OP was
using one of the cooccurrence based techniques.

On Mon, Jun 11, 2012 at 12:19 PM, Sean Owen <sr...@gmail.com> wrote:

> Not so with ALS. The matrix in question is (# users) x (# features), so the
> number of rated items by any user won't matter.
>
> I didn't write this job, but implemented a similar pipeline. I struggled
> with this kind of tradeoff: loading the user feature matrix in memory is a
> scalability bottleneck (straings worker memory) but makes things go much,
> much faster.
>
> Computing U' * U is cake in memory. (Computing U * U' is not possible here!
> but I don't think the job ever tries that? Shouldn't...)
>
> U is the biggest thing you need in memory at any given time. And it is
> going to need about 0.5KB per user at most. 10M users = 5GB RAM. Meh, that
> seems roughly "OK".
>
>
> If you like ALS on Hadoop, I don't mind again plugging the Myrrix
> Computation Layer (http://myrrix.com/documentation-computation-layer/), a
> sort of spin off of this kind of work I've been doing in Mahout (though not
> this class) that I've done a lot to optimize. I think it's about as swift
> as this will be on Hadoop -- and ALS does fit Hadoop quite well. Email
> off-list if you want to try it out.
>
>
> On Mon, Jun 11, 2012 at 8:08 PM, Ted Dunning <te...@gmail.com>
> wrote:
>
> > This sounds like you have a pathological user (or several) in your data
> > set.
> >
> > The cost of these jobs scales as the square of the activity of the most
> > active user.  This means that you typically need to eliminate this user
> (if
> > they are robots or QA) or down-sample them (if they are just crazy people
> > who download thousands and tens of thousands of things).  This generally
> > causes no perceptible impact on performance.
> >
> > The system should easily scale to the size you need with a bit of care in
> > the data.
> >
> > On Mon, Jun 11, 2012 at 11:42 AM, Bill Mccormick <billmcc64@gmail.com
> > >wrote:
> >
> > > Hi all,
> > >
> > > We're interested in using Mahout for a recommendation system for a
> > largish
> > > online storefront.
> > >
> > > The initial recommendations are based on download/purchase history, so
> we
> > > were trying out the ParallelALSFactorizationJob which seems to give
> good
> > > results.
> > >
> > > The initial test run was limited to 100,000 users and the job ran with
> no
> > > problems.
> > >
> > > The next test set was structured differently with around 4M download
> > > records and around 1.5 M users (rather than a fixed number of users, it
> > was
> > > the set of downloads over a fixed period of time).   The Hadoop tasks
> > hung
> > > in garbage collection on this job.
> > >
> > > I started looking at memory usage, and I noticed that the existing
> > > implementation attempts to compute the product of the user factor
> matrix
> > > transpose with itself in memory.  (It also looks like it does this on
> > every
> > > mapper, instead of once per iteration.)
> > >
> > > Our full data set has on the order of 100M users.    So this isn't
> going
> > to
> > > work as is.  (i.e. the user factor matrix will take 100M users x 20
> > factors
> > > x 8 bytes per entry = 16 Gbytes)
> > >
> > > I'm just pondering implementing a new version that does the large
> matrix
> > > computations in a less memory intensive fashion.   Before I go too
> far, I
> > > was hoping this list could provide some input:
> > >
> > > - is my analysis correct?
> > > - is someone already working on this?
> > > - if we go ahead with this, is the Mahout project interested in
> accepting
> > > the new implementation once it's done?
> > >
> > > thank you very much.
> > >
> > > --
> > > Bill McCormick
> > >
> >
>

Re: Scalability of ParallelALSFactorizationJob with implicit feedback

Posted by Sean Owen <sr...@gmail.com>.
Not so with ALS. The matrix in question is (# users) x (# features), so the
number of rated items by any user won't matter.

I didn't write this job, but implemented a similar pipeline. I struggled
with this kind of tradeoff: loading the user feature matrix in memory is a
scalability bottleneck (straings worker memory) but makes things go much,
much faster.

Computing U' * U is cake in memory. (Computing U * U' is not possible here!
but I don't think the job ever tries that? Shouldn't...)

U is the biggest thing you need in memory at any given time. And it is
going to need about 0.5KB per user at most. 10M users = 5GB RAM. Meh, that
seems roughly "OK".


If you like ALS on Hadoop, I don't mind again plugging the Myrrix
Computation Layer (http://myrrix.com/documentation-computation-layer/), a
sort of spin off of this kind of work I've been doing in Mahout (though not
this class) that I've done a lot to optimize. I think it's about as swift
as this will be on Hadoop -- and ALS does fit Hadoop quite well. Email
off-list if you want to try it out.


On Mon, Jun 11, 2012 at 8:08 PM, Ted Dunning <te...@gmail.com> wrote:

> This sounds like you have a pathological user (or several) in your data
> set.
>
> The cost of these jobs scales as the square of the activity of the most
> active user.  This means that you typically need to eliminate this user (if
> they are robots or QA) or down-sample them (if they are just crazy people
> who download thousands and tens of thousands of things).  This generally
> causes no perceptible impact on performance.
>
> The system should easily scale to the size you need with a bit of care in
> the data.
>
> On Mon, Jun 11, 2012 at 11:42 AM, Bill Mccormick <billmcc64@gmail.com
> >wrote:
>
> > Hi all,
> >
> > We're interested in using Mahout for a recommendation system for a
> largish
> > online storefront.
> >
> > The initial recommendations are based on download/purchase history, so we
> > were trying out the ParallelALSFactorizationJob which seems to give good
> > results.
> >
> > The initial test run was limited to 100,000 users and the job ran with no
> > problems.
> >
> > The next test set was structured differently with around 4M download
> > records and around 1.5 M users (rather than a fixed number of users, it
> was
> > the set of downloads over a fixed period of time).   The Hadoop tasks
> hung
> > in garbage collection on this job.
> >
> > I started looking at memory usage, and I noticed that the existing
> > implementation attempts to compute the product of the user factor matrix
> > transpose with itself in memory.  (It also looks like it does this on
> every
> > mapper, instead of once per iteration.)
> >
> > Our full data set has on the order of 100M users.    So this isn't going
> to
> > work as is.  (i.e. the user factor matrix will take 100M users x 20
> factors
> > x 8 bytes per entry = 16 Gbytes)
> >
> > I'm just pondering implementing a new version that does the large matrix
> > computations in a less memory intensive fashion.   Before I go too far, I
> > was hoping this list could provide some input:
> >
> > - is my analysis correct?
> > - is someone already working on this?
> > - if we go ahead with this, is the Mahout project interested in accepting
> > the new implementation once it's done?
> >
> > thank you very much.
> >
> > --
> > Bill McCormick
> >
>

Re: Scalability of ParallelALSFactorizationJob with implicit feedback

Posted by Ted Dunning <te...@gmail.com>.
This sounds like you have a pathological user (or several) in your data set.

The cost of these jobs scales as the square of the activity of the most
active user.  This means that you typically need to eliminate this user (if
they are robots or QA) or down-sample them (if they are just crazy people
who download thousands and tens of thousands of things).  This generally
causes no perceptible impact on performance.

The system should easily scale to the size you need with a bit of care in
the data.

On Mon, Jun 11, 2012 at 11:42 AM, Bill Mccormick <bi...@gmail.com>wrote:

> Hi all,
>
> We're interested in using Mahout for a recommendation system for a largish
> online storefront.
>
> The initial recommendations are based on download/purchase history, so we
> were trying out the ParallelALSFactorizationJob which seems to give good
> results.
>
> The initial test run was limited to 100,000 users and the job ran with no
> problems.
>
> The next test set was structured differently with around 4M download
> records and around 1.5 M users (rather than a fixed number of users, it was
> the set of downloads over a fixed period of time).   The Hadoop tasks hung
> in garbage collection on this job.
>
> I started looking at memory usage, and I noticed that the existing
> implementation attempts to compute the product of the user factor matrix
> transpose with itself in memory.  (It also looks like it does this on every
> mapper, instead of once per iteration.)
>
> Our full data set has on the order of 100M users.    So this isn't going to
> work as is.  (i.e. the user factor matrix will take 100M users x 20 factors
> x 8 bytes per entry = 16 Gbytes)
>
> I'm just pondering implementing a new version that does the large matrix
> computations in a less memory intensive fashion.   Before I go too far, I
> was hoping this list could provide some input:
>
> - is my analysis correct?
> - is someone already working on this?
> - if we go ahead with this, is the Mahout project interested in accepting
> the new implementation once it's done?
>
> thank you very much.
>
> --
> Bill McCormick
>