2
$\begingroup$

Consider gradient boosting like gbm or xgboost.

I have a labelled dataset (X,y). If I don't care about over-fitting and I allow gbm or xgboost grow as much as needed, eventually can I reach the accuracy of 100% in predicting in training dataset?

$\endgroup$
  • 2
    $\begingroup$ can't be arbitrary? what if input is constant and output varies $\endgroup$ – seanv507 Oct 19 '18 at 6:33
  • $\begingroup$ very nice comment - never think about it. $\endgroup$ – mommomonthewind Oct 19 '18 at 6:42
  • $\begingroup$ yes, to expand on this, it largely depends on how "rich" the feature set is, compared to the size of the data set. If every instance is unique in feature space (or that instances which are equivalent in feature space, have the same label), then you can make xgboost behave like a decision tree, and "memorise" the labels. A reason XGBoost tends to be robust to over-fitting, is that you don't grow your trees very deeply. I'm less sure whether you can arbitrarily overfit if you grow enough shallow trees $\endgroup$ – gazza89 Oct 19 '18 at 9:34
2
$\begingroup$

A necessary condition for any method to achieve 100% accuracy on the training set is that there exists a one-to-one mapping from inputs to outputs for points in the training set. If this condition doesn't hold--that is, at least one input point occurs multiple times in the training set with different output values--then no method can achieve 100% accuracy.

Even if the above condition holds, gradient boosting can't achieve 100% accuracy on arbitrary datasets if the base models aren't sufficiently powerful. In particular, if linear base models are used, then the final ensemble model will also be linear. And, if the true relationship between inputs and outputs is nonlinear, then 100% accuracy isn't possible.

But, it's common to use decision trees as base models for gradient boosting, which are nonlinear. In this case (and assuming the above one-to-one condition is true), it is possible to achieve 100% accuracy on an arbitrary training set, provided we don't restrict model growth. For example, suppose we allow decision trees of unlimited depth. In this case, we can memorize the entire training set using a single decision tree, and achieve 100% accuracy in a single iteration. Of course, this runs a severe risk of overfitting, so a limit on tree depth is imposed. But, even if tree depth is limited, we can still memorize the training set (and achieve 100% accuracy) by using an unlimited number of trees (i.e. boosting iterations). So, to combat overfitting, a limit on the number of iterations is also needed. Other forms of regularization are typically imposed as well (e.g. shrinkage and subsampling of datapoints/features).

$\endgroup$

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.