mahout-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dmitriy Lyubimov <dlie...@gmail.com>
Subject Re: Which exact algorithm is used in the Mahout SGD?
Date Wed, 01 Jun 2011 05:00:35 GMT
i must say i don't understand most of the math.

as for sharding, if i understood it correctly, i remember having
exactly same idea for 'strata' selection as they show their a year
ago. But i think the problem is that you have to run as many MR jobs
as the number of strata selected. I.e. if you parallelize it 5 ways (5
maps) then you have to run it at least 5 times. or maybe one can
recombine subepochs in reducers and have another run with reducers (so
it's 3 times, not 5). Which seems to put fundamental limitations on
hadoopified scalability of this (they partly show increased time after
some rather low # of mappers  which seems to confirm my old concern
about this).

it probably makes sense with a lot of data. It probably makes even
more sense without MR sort phase.

Another thing i did not quite get, how they cope with regularization?
it looks like they don't want to use it. How's overfitting handled
then?

but it's compelling enough for my work so i could try it. Again, i
probably did not get some aspects of the algorithm though.

Factorization is essentially a quantitative (continuous) target
regression, not a classification, so our abstract classifier
interfaces probably would not fit here

On Tue, May 31, 2011 at 9:45 PM, Ted Dunning <ted.dunning@gmail.com> wrote:
> After a quick skumming of the paper, it looks vaguely like if you reduced
> this to learning logistic regression that you have something roughly the
> same as feature sharding.
>
> (which is still a good idea)
>
> With matrices, of course, you have two ways to shard, not just one.
>
> On Tue, May 31, 2011 at 7:19 PM, Dmitriy Lyubimov <dlieu.7@gmail.com> wrote:
>
>> Interesting.
>> i'd probably be interested to try it out.
>>
>>
>>
>> On Thu, Apr 28, 2011 at 11:31 PM, Stanley Xu <wenhao.xu@gmail.com> wrote:
>> > Thanks Ted and Lance. And sorry for the jargon.
>> >
>> > For the delay Ted mentioned, we have already considered that, still
>> thanks a
>> > lot for all the detail ideas, they were pretty helpful.
>> > For the parallelized SGD, just found a new paper about using DSGD in
>> matrix
>> > factorization, it's different from logistic regression, but might helpful
>> as
>> > well. Put the title here "Large-Scale Matrix Factorization with
>> Distributed
>> > Stochastic Gradient Descent" if anyone is interested.
>> >
>> > Best wishes,
>> > Stanley Xu
>> > On Fri, Apr 29, 2011 at 2:08 PM, Ted Dunning <ted.dunning@gmail.com>
>> wrote:
>> >
>> >> Yes.
>> >>
>> >> Apologies for jargon and TLA<
>> >> http://en.wikipedia.org/wiki/Three-letter_acronym>
>> >> 's
>> >>
>> >> On Thu, Apr 28, 2011 at 7:04 PM, Lance Norskog <goksron@gmail.com>
>> wrote:
>> >>
>> >> > CTR == Clickthrough Rate
>> >> >
>> >> > On Thu, Apr 28, 2011 at 12:06 PM, Ted Dunning <ted.dunning@gmail.com>
>> >> > wrote:
>> >> > > On Tue, Apr 26, 2011 at 8:00 PM, Stanley Xu <wenhao.xu@gmail.com>
>> >> wrote:
>> >> > >
>> >> > >> ... I understood as the algorithm, the time in training only
relies
>> on
>> >> > the
>> >> > >> non-zero records, but per our test, there would be some overhead
we
>> >> > could
>> >> > >> not ignore for thoso non-zero records, though the cost is
>> sub-linear
>> >> or
>> >> > >> logit to the length of the hashed vector.
>> >> > >>
>> >> > >
>> >> > > This is pretty close if we say "non-zero values".  A record usually
>> >> > refers
>> >> > > to an entire training
>> >> > > example.
>> >> > >
>> >> > > The extra work refers mostly to deferred regularization that
>> eventually
>> >> > has
>> >> > > to be
>> >> > > applied.  My guess is that it is even less than log in the feature
>> >> vector
>> >> > > size.
>> >> > >
>> >> > >
>> >> > >> And in CTR prediction, I am not pretty sure it will converge
very
>> >> > quickly.
>> >> > >>
>> >> > >
>> >> > > I was saying this purely based on the number of features.
>> >> > >
>> >> > >
>> >> > >> Because we will very possibly see some records has the almost
same
>> >> > feature
>> >> > >> but different result in display ads.
>> >> > >
>> >> > >
>> >> > > The algorithm can still converge to an estimate of the probability
>> >> here.
>> >> > >
>> >> > >
>> >> > >> But we will see the result in the
>> >> > >> future.
>> >> > >
>> >> > >
>> >> > > You have to be *very* careful about this to avoid prejudicing
the
>> model
>> >> > > against
>> >> > > recent impressions.  If you have a fast feedback to the ad targeting
>> >> > system,
>> >> > > you
>> >> > > can have severely instability.
>> >> > >
>> >> > > The key thing that you have to do to avoid these biases is to
define
>> a
>> >> > > maximum
>> >> > > delay before click for the purposes of modeling.  You need to
ignore
>> >> all
>> >> > > impressions
>> >> > > younger than this delay (because they may still get a click) and
you
>> >> need
>> >> > to
>> >> > > ignore
>> >> > > all clicks after this delay (to avoid bias in favor of old
>> >> impressions).
>> >> > >  For on-line ads
>> >> > > you can probably use a maximum delay of a few minutes because
most
>> >> clicks
>> >> > > will
>> >> > > happen by then.
>> >> > >
>> >> > > To find a good value for maximum delay, you should plot the CTR
for
>> a
>> >> > bunch
>> >> > > of
>> >> > > ads versus delay.  This will increase rapidly shortly after zero
>> delay,
>> >> > but
>> >> > > then will
>> >> > > level off.  The ordering of ads by CTR is what you care about
so you
>> >> can
>> >> > > follow the
>> >> > > curves back and find the shortest delay where the ordering is
>> clearly
>> >> > > preserved.  Use
>> >> > > that as your maximum delay.  Typically this is roughly where
your
>> CTR
>> >> is
>> >> > at
>> >> > > about
>> >> > > 80-90% of the final value.
>> >> > >
>> >> > >
>> >> > >
>> >> > >
>> >> > >> (We were still working on creating a framework to digg all
the
>> >> > >> features we need from the log, I would like to share our experience
>> by
>> >> > >> using
>> >> > >> Mahout SGD once we got our CTR prediction model release.)
>> >> > >>
>> >> > >> And for parallelize SGD, what do you mean for help with sparse
>> inputs
>> >> > that
>> >> > >> exhibit long-tail frequency distribution? Would you like to
share
>> some
>> >> > of
>> >> > >> your ideas, Ted?
>> >> > >>
>> >> > >> Currently, what I could think about is split the data to multiple
>> >> mapper
>> >> > >> randomly and let every mapper to learn from the local data
and get
>> an
>> >> > >> average on the whole model, or let multiple model to vote
for every
>> >> > >> feature's weight. A little like the idea of AdaBoost or
>> RandomForest.
>> >> > But I
>> >> > >> am not a scientist or mathematician, so no idea if it is correct
or
>> >> not.
>> >> > >>
>> >> > >>
>> >> > >> Thanks so much.
>> >> > >> Stanley Xu
>> >> > >>
>> >> > >>
>> >> > >>
>> >> > >> On Tue, Apr 26, 2011 at 11:16 PM, Ted Dunning <
>> ted.dunning@gmail.com>
>> >> > >> wrote:
>> >> > >>
>> >> > >> > On Mon, Apr 25, 2011 at 11:46 PM, Stanley Xu <
>> wenhao.xu@gmail.com>
>> >> > >> wrote:
>> >> > >> >
>> >> > >> > > 1 hour is acceptable, but I guess you misunderstand
the data
>> scale
>> >> I
>> >> > >> mean
>> >> > >> > > here. The 900M records didn't mean 900M Bytes, but
900M lines
>> of
>> >> > >> training
>> >> > >> > > set(900M training example.). If every training data
has 1000
>> >> > dimension,
>> >> > >> > it
>> >> > >> > > means 900 million X 1000 X 16 B = 14TB. If we reduce
the logs
>> >> > collected
>> >> > >> > to
>> >> > >> > > 14 days, it would be still 2-3TB data.
>> >> > >> > >
>> >> > >> >
>> >> > >> > Oops.  Forgot that last multiplier.
>> >> > >> >
>> >> > >> >
>> >> > >> > > Per our simple test, for 1000 dimension, 10M lines
of record,
>> it
>> >> > will
>> >> > >> > take
>> >> > >> > > about 1-2 hours to do the training, so 90M lines
of data will
>> cost
>> >> > at
>> >> > >> > least
>> >> > >> > > 90 hours, is that correct?
>> >> > >> > >
>> >> > >> >
>> >> > >> > 10M x 1000 x 8 = 80 GB.
>> >> > >> >
>> >> > >> > 1-2 hours = (approx) 5000 seconds.  So this is
>> >> > >> >
>> >> > >> > 80 GB / 5000 s = 80/5 MB /s = 16MB / s
>> >> > >> >
>> >> > >> > Yes.  This is reasonable speed.  I think you can get
a small
>> factor
>> >> > >> faster
>> >> > >> > than this with SGD.  I have seen 100 million records
with more
>> >> > non-zero
>> >> > >> > values than you describe with a training time of 3 hours.
 I
>> would
>> >> not
>> >> > >> > expect even as much as a factor of 10 speedup here.
>> >> > >> >
>> >> > >> >
>> >> > >> > >
>> >> > >> > > And from the PPT you provided
>> >> > >> > > http://www.slideshare.net/tdunning/sdforum-11042010
>> >> > >> > > You said it would take less than an hour for 20M
data records
>> for
>> >> > >> > > numeric/category mixed dimensions. I am wondering,
how many
>> >> > dimensions
>> >> > >> > per
>> >> > >> > > record?
>> >> > >> > >
>> >> > >> >
>> >> > >> > These are sparse records records with about a thousand
non-zero
>> >> > elements
>> >> > >> > per
>> >> > >> > record.
>> >> > >> >
>> >> > >> >
>> >> > >> > But let's step back to your data for a moment.  Where
do these
>> >> > thousand
>> >> > >> > dimensions come from?  Do you really have a thousand
hand-built
>> >> > features?
>> >> > >> >  Do you not have any sparse, text-like features?
>> >> > >> >
>> >> > >> > If you really only have a thousand dimensional problem,
then I
>> think
>> >> > your
>> >> > >> > model might exhibit early convergence.
>> >> > >> >
>> >> > >> > If not, it is quite possible to parallelize SGD, but
this is only
>> >> > likely
>> >> > >> to
>> >> > >> > help with sparse inputs that exhibit long-tail frequency
>> >> distribution.
>> >> > >> >
>> >> > >>
>> >> > >
>> >> >
>> >> >
>> >> >
>> >> > --
>> >> > Lance Norskog
>> >> > goksron@gmail.com
>> >> >
>> >>
>> >
>>
>

Mime
View raw message