15
$\begingroup$

Let's say I have a logistic regression classifier. In normal batch learning, I'd have a regularizer term to prevent overfitting and keep my weights small. I'd also normalize and scale my features.

In an online learning setting, I'm getting a continuous stream of data. I do a gradient descent update with each example and then discard it. Am I supposed to use feature scaling and regularization term in online learning? If yes, how can I do that? For example, I don't have a set of training data to scale against. I also don't have validation set to tune my regularization parameter. If no, why not?

In my online learning, I get a stream of examples continuously. For each new example, I do a prediction. Then in the next time step, I get the actual target and do the gradient descent update.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
9
$\begingroup$

The open-source project vowpal wabbit includes an implementation of online SGD which is enhanced by on the fly (online) computation of 3 additional factors affecting the weight updates. These factors can be enabled/disabled by their respective command line options (by default all three are turned on, the --sgd option, turns them all off, i.e: falls-back on "classic" SGD).

The 3 SGD enhancing options are:

  • --normalized updates adjusted for scale of each feature
  • --adaptive uses adaptive gradient (AdaGrad) (Duchi, Hazan, Singer)
  • --invariant importance aware updates (Karampatziakis, Langford)

Together, they ensure that the online learning process does a 3-way automatic compensation/adjustment for:

  • per-feature scaling (large vs small values)
  • per-feature learning rate decay based on feature importance
  • per feature adaptive learning rate adjustment for feature prevalence/rarity in examples

The upshot is that there's no need to pre-normalize or scale different features to make the learner less biased and more effective.

In addition, vowpal wabbit also implements online regularization via truncated gradient descent with the regularization options:

  • --l1 (L1-norm)
  • --l2 (L2-norm)

My experience with these enhancements on multiple data-sets, was that they significantly improved model accuracy and smoother convergence when each of them was introduced into the code.

Here are some academic papers for more detail related to these enhancements:

Improve this answer
$\endgroup$
3
  • $\begingroup$ Arielf - If you turn off the three enhancements (via --sgd) is the sgd that is being done shown on slide 11 of github.com/JohnLangford/vowpal_wabbit/wiki/v6.1_tutorial.pdf so that then power_t and initial_t become relevant? $\endgroup$
    – B_Miner
    Commented Feb 16, 2015 at 4:28
  • 1
    $\begingroup$ B_miner: as far as I understand --power_t and --initial_t are global (not per feature) independent options. --sgd only reverts to the "classic" SGD. IOW: --sgd only cancels --invariant, --normalized, and --adaptive (which imply separate, per-feature learning-rates) $\endgroup$
    – arielf
    Commented Feb 16, 2015 at 6:34
  • $\begingroup$ Do you know if there is a way to do these updates in a parallel asynchronous fashion (as is done in asynchronous SGD)? It seems VW with multiple workers averages each worker's model at the end of each pass. Any papers/software pointers on how to do this? $\endgroup$
    – JC1
    Commented Feb 15, 2018 at 4:53
2
$\begingroup$

This paper describes a technique for online regularization which they apply to various algorithms, including logistic regression: http://ai.stanford.edu/~chuongdo/papers/proximal.pdf

Improve this answer
$\endgroup$
1
$\begingroup$

yes you certainly need regularisation... it also helps the gradient descent ( and initialise learning rate to 1/C)

see eg SGD-QN paper http://leon.bottou.org/papers bottou's papers

you haven't really explained what you mean by online learning: eg for each point do you get target value? I don't know how you would incorporate... searching for C ... I guess you would have multiple classifiers with different regularisation terms and track the prediction error ( before you update weights)

Improve this answer
$\endgroup$
7
  • $\begingroup$ By online learning, I get one example and do a prediction. At the next time step, I get the actual target for my example and do a gradient descent update. $\endgroup$
    – siamii
    Commented Jul 13, 2013 at 13:16
  • $\begingroup$ well then it should be as I suggested - you run a bunch of classifiers with different regularisation parameter and keep track of the prediction errors of each classifier. $\endgroup$
    – seanv507
    Commented Jul 13, 2013 at 14:18
  • $\begingroup$ I'm not sure what you mean by initialize learning rate to 1/C. What is C? Are you talking about support vector machines? I'm talking about logistic regression where the regularizer has coefficient lambda. I don't know what that has to do with the learning rate. $\endgroup$
    – siamii
    Commented Jul 13, 2013 at 15:09
  • $\begingroup$ yes the l2 regularisation parameter, C, lambda, or whatever. its something that is mentioned in an aside in bottou's sgdqn paper, and I presume explained better somewhere else. basically your learning rate should be the 1/curvature (inverse of Hessian) of your error surface.. now if your error surface is $\endgroup$
    – seanv507
    Commented Jul 13, 2013 at 15:30
  • 1
    $\begingroup$ Do I also need to do feature scaling? How to do that in an online setting? $\endgroup$
    – siamii
    Commented Jul 13, 2013 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.