My goal is to formulate the learning and generalization phases of any Boosting algorithm as a matrix-vector operation.

Through Google, I found a good pdf (*) describing several boosting algorithms but the author Marco Cusumano-Towner only hints and doesn't explain how to recast the boosting algorithms (GradientBoost, Adaboost, QuadBoost) using matrix operations.

My question is:

Can I formulate a boosting algorithm as a regression, a game or a linear programming and arrive at closed-form solution which uses only matrix operations?

(*) Boosting with log-loss

  • $\begingroup$ This seems pretty broad, and I don't know of any reason to expect there to be a simple universal solution. Boosting is a generic method that can be applied to many different kinds of weak learners. I suspect everything will depend on the specifics of the weak learners you use with boosting, and I don't know of any reason to expect that the solution will necessarily be matrix-vector operations or to expect the same answer for all weak learners. $\endgroup$ – D.W. Feb 26 '19 at 0:46
  • 1
    $\begingroup$ Also, AdaBoost as normally described doesn't involve computation of any gradients (see, e.g., en.wikipedia.org/wiki/…), so I'm not sure I understand what you mean by "to avoid iterative computing of gradients", and I'm not sure why expressing it in matrix-vector operations would be any better than the standard way it is expressed. $\endgroup$ – D.W. Feb 26 '19 at 0:48
  • $\begingroup$ Since you mention gradients, are you familiar with gradient boosting and xgboost? Xgboost deals with the special case where the weak learner is a decision tree algorithm, and might be related to what you're hoping for. Apologies if I'm telling you things you already know and are familiar with. $\endgroup$ – D.W. Feb 26 '19 at 0:50
  • $\begingroup$ nice comments D.W.. I simplified and edited my question, thanks $\endgroup$ – R. S. Feb 26 '19 at 1:10

Basically: no. Boosting is a "meta-method". If you have a weak learner (an algorithm for learning), it is a way of taking advantage of that weak learner algorithm iteratively to do better at learning some concept than the weak learner would do on its own.

Many/most weak learners don't have a closed-form solution for the model they build; instead, their learning algorithm may fundamentally rely upon iterative methods, optimization algorithms, or other techniques. As a result, boosting with such a weak learner won't have a closed-form solution, either.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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