Removing Training Order Dependency on SGD Classification

[Tom Marthaler <ma...@gmail.com>]

Hi, looking at the org.apache.mahout.classifier.sgd.TrainNewsGroups
examples class, it seems that the online nature of the SGD logistic
regression will always be dependent on the order in which the classifier is
trained.

There is a call to randomize the order in which the newsgroup files are
read in on line 112 of TrainNewsGroups (the Collections.shuffle(files);
call). This means that the output of the TrainNewsGroups main method will
be non-deterministic.

I am specifically looking at the weights put into the
org.mahout.classifier.sgd.ModelDissector core class.

Is there a way to make the feature weights deterministic, no matter the
order of the input training vectors?

Re: Removing Training Order Dependency on SGD Classification

[Ted Dunning <te...@gmail.com>]

On Mon, May 13, 2013 at 9:24 PM, Tom Marthaler <ma...@gmail.com> wrote:

> Is there a way to make the feature weights deterministic, no matter the
> order of the input training vectors?
>

Well, not if you use *STOCHASTIC* gradient descent.

That is part of the point, actually.

But seriously, this is likely to be true of any online logistic regression
algorithms.

You can build deterministic on-line algorithms for linear regression but
even there large sparse systems make gradient descent more palatable.

If you make multiple passes through the input, then you could switch to
BFGS or use update averaging to accelerate convergence after SGD has gotten
you near the solution, but getting near the solution depends a bit on
randomized ordering of examples.

Hope this helps.

Re: Removing Training Order Dependency on SGD Classification

[Ted Dunning <te...@gmail.com>]

On Tue, May 14, 2013 at 12:06 AM, Dan Filimon
<da...@gmail.com>wrote:

> Nice! Thanks for the links Ted!
>

yeah... I can google!


> >
> > SGD converges with 1/n [1].  Second order techniques converge
> quadratically
> > in the number of iterations but each iteration can be quite expensive in
> > terms of the number of points.
> >
>
> Right, but iteration in SGD is processing just 1 point whereas in BGD it's
> processing n points

And also, I might be confused here, but I thought BGD is not a second order
> technique. It still only computes the gradient which is the first
> derivative (or rather, the version I learned in school does this :) ?
>

BGD = Batch Gradient Descent is, indeed, not quadratic.

But there are second order methods.  And quasi-second order methods that
are forms of conjugate gradients.


> > Mini-batch algorithms can combine these by doing batch updates on small
> > batches.  They can be viewed as mini-batch or mega-SGD depending on your
> > point of view.
> >
> > SGD can also use a higher order conjugate gradient technique like BFGS.
> >  Vowpal wabbit uses this to good effect [2].  Update averaging can have
> > similar effect [3].
> >
>
> About update averaging, is it basically averaging k updates (by looking at
> k points I mean) into 1 per iteration?
>

Yeah.

The reason it works (I haven't gone through the details in detail) is that
this averaging is like a poor man's conjugate gradient.


>
> >
> > [1] http://cilvr.cs.nyu.edu/diglib/lsml/bottou-sgd-tricks-2012.pdf
> >
> > [2]
> http://www.slideshare.net/jakehofman/technical-tricks-of-vowpal-wabbit
> >
> > [3] http://arxiv.org/pdf/1303.6149v1.pdf
> >
>

Re: Removing Training Order Dependency on SGD Classification

[Dan Filimon <da...@gmail.com>]

Nice! Thanks for the links Ted!

On Tue, May 14, 2013 at 9:20 AM, Ted Dunning <te...@gmail.com> wrote:

> On Mon, May 13, 2013 at 10:48 PM, Dan Filimon
> <da...@gmail.com>wrote:
>
> > SGD and batch gradient descent have the same expected errors however.
>
>
> But not the same rate of convergence.
>
> SGD converges with 1/n [1].  Second order techniques converge quadratically
> in the number of iterations but each iteration can be quite expensive in
> terms of the number of points.
>

Right, but iteration in SGD is processing just 1 point whereas in BGD it's
processing n points.
And also, I might be confused here, but I thought BGD is not a second order
technique. It still only computes the gradient which is the first
derivative (or rather, the version I learned in school does this :) ?


> Mini-batch algorithms can combine these by doing batch updates on small
> batches.  They can be viewed as mini-batch or mega-SGD depending on your
> point of view.
>
> SGD can also use a higher order conjugate gradient technique like BFGS.
>  Vowpal wabbit uses this to good effect [2].  Update averaging can have
> similar effect [3].
>

About update averaging, is it basically averaging k updates (by looking at
k points I mean) into 1 per iteration?

>
> [1] http://cilvr.cs.nyu.edu/diglib/lsml/bottou-sgd-tricks-2012.pdf
>
> [2] http://www.slideshare.net/jakehofman/technical-tricks-of-vowpal-wabbit
>
> [3] http://arxiv.org/pdf/1303.6149v1.pdf
>

Re: Removing Training Order Dependency on SGD Classification

[Ted Dunning <te...@gmail.com>]

On Mon, May 13, 2013 at 10:48 PM, Dan Filimon
<da...@gmail.com>wrote:

> SGD and batch gradient descent have the same expected errors however.


But not the same rate of convergence.

SGD converges with 1/n [1].  Second order techniques converge quadratically
in the number of iterations but each iteration can be quite expensive in
terms of the number of points.

Mini-batch algorithms can combine these by doing batch updates on small
batches.  They can be viewed as mini-batch or mega-SGD depending on your
point of view.

SGD can also use a higher order conjugate gradient technique like BFGS.
 Vowpal wabbit uses this to good effect [2].  Update averaging can have
similar effect [3].

[1] http://cilvr.cs.nyu.edu/diglib/lsml/bottou-sgd-tricks-2012.pdf

[2] http://www.slideshare.net/jakehofman/technical-tricks-of-vowpal-wabbit

[3] http://arxiv.org/pdf/1303.6149v1.pdf

Re: Removing Training Order Dependency on SGD Classification

[Tom Marthaler <ma...@gmail.com>]

Dan / Ted, thanks for the responses.

I think that my confusion with the SGD implementation was from the
combination of randomization of the seeds and the batch versus online
nature of the classification training. I had previously never used an
online classifier before.

It turns out that the library that I was comparing the results against
(scikit-learn, which is a wrapper around LIBLINEAR) was doing batch L2
Regression processing, which I believe does not use a gradient descent
calculation. So apples and oranges to some extent.

I'll take a look at the RandomUtils.useTestSeed() to see if I can replicate
some of my test data using this online training.

Thanks again for the response.



On Mon, May 13, 2013 at 10:48 PM, Dan Filimon
<da...@gmail.com>wrote:

> Hi,
>
> On Tue, May 14, 2013 at 7:24 AM, Tom Marthaler <ma...@gmail.com>
> wrote:
>
> > Hi, looking at the org.apache.mahout.classifier.sgd.TrainNewsGroups
> > examples class, it seems that the online nature of the SGD logistic
> > regression will always be dependent on the order in which the classifier
> is
> > trained.
> >
>
> Yes, gradient descent is dependent on the starting point and SGD, given
> that it stochastically choses a single point to compute the gradient with
> respect to, is also is dependent on the order of the points.
> SGD and batch gradient descent have the same expected errors however.
>
>
> > There is a call to randomize the order in which the newsgroup files are
> > read in on line 112 of TrainNewsGroups (the Collections.shuffle(files);
> > call). This means that the output of the TrainNewsGroups main method will
> > be non-deterministic.
> >
>
> Yes and I can tell you from experience (sadly... :) that not shuffling the
> points will break everything.
>
> I am specifically looking at the weights put into the
> > org.mahout.classifier.sgd.ModelDissector core class.
> >
> > Is there a way to make the feature weights deterministic, no matter the
> > order of the input training vectors?
> >
>
> For it to work in general, the stochasticity is what makes it have the same
> expected errors as normal GD. It's just by nature a random algorithm.
> For testing however, you can always set a fixed seed for the random number
> generator. This will always give you the same "random" points. There's a
> method in RandomUtils.useTestSeed() that does just that.
>

Re: Removing Training Order Dependency on SGD Classification

[Dan Filimon <da...@gmail.com>]

Hi,

On Tue, May 14, 2013 at 7:24 AM, Tom Marthaler <ma...@gmail.com> wrote:

> Hi, looking at the org.apache.mahout.classifier.sgd.TrainNewsGroups
> examples class, it seems that the online nature of the SGD logistic
> regression will always be dependent on the order in which the classifier is
> trained.
>

Yes, gradient descent is dependent on the starting point and SGD, given
that it stochastically choses a single point to compute the gradient with
respect to, is also is dependent on the order of the points.
SGD and batch gradient descent have the same expected errors however.


> There is a call to randomize the order in which the newsgroup files are
> read in on line 112 of TrainNewsGroups (the Collections.shuffle(files);
> call). This means that the output of the TrainNewsGroups main method will
> be non-deterministic.
>

Yes and I can tell you from experience (sadly... :) that not shuffling the
points will break everything.

I am specifically looking at the weights put into the
> org.mahout.classifier.sgd.ModelDissector core class.
>
> Is there a way to make the feature weights deterministic, no matter the
> order of the input training vectors?
>

For it to work in general, the stochasticity is what makes it have the same
expected errors as normal GD. It's just by nature a random algorithm.
For testing however, you can always set a fixed seed for the random number
generator. This will always give you the same "random" points. There's a
method in RandomUtils.useTestSeed() that does just that.