generative-modelsmachine learning
In an interview, the interviewer said that discriminative models tend to overfit more than generative models because they solve a more complex problem and hence consume more resources (or parameters) doing so. For definitions on discriminative and generative models, you can sse this post Generative vs. discriminative
I thought more parameters would lead to overfitting but here the logic is reversed. Any ideas?
The fundamental difference between discriminative models and generative models is:
To answer your direct questions:
SVMs (Support Vector Machines) and DTs (Decision Trees) are discriminative because they learn explicit boundaries between classes. SVM is a maximal margin classifier, meaning that it learns a decision boundary that maximizes the distance between samples of the two classes, given a kernel. The distance between a sample and the learned decision boundary can be used to make the SVM a "soft" classifier. DTs learn the decision boundary by recursively partitioning the space in a manner that maximizes the information gain (or another criterion).
It is possible to make a generative form of logistic regression in this manner. Note that you are not using the full generative model to make classification decisions, though.
There are a number of advantages generative models may offer, depending on the application. Say you are dealing with non-stationary distributions, where the online test data may be generated by different underlying distributions than the training data. It is typically more straightforward to detect distribution changes and update a generative model accordingly than do this for a decision boundary in an SVM, especially if the online updates need to be unsupervised. Discriminative models also do not generally function for outlier detection, though generative models generally do. What's best for a specific application should, of course, be evaluated based on the application.
(This quote is convoluted, but this is what I think it's trying to say) Generative models are typically specified as probabilistic graphical models, which offer rich representations of the independence relations in the dataset. Discriminative models do not offer such clear representations of relations between features and classes in the dataset. Instead of using resources to fully model each class, they focus on richly modeling the boundary between classes. Given the same amount of capacity (say, bits in a computer program executing the model), a discriminative model thus may yield more complex representations of this boundary than a generative model.
Is overfitting so bad that you should not pick a model that does overfit, even though its test error is smaller? No. But you should have a justification for choosing it.
This behavior is not restricted to XGBoost. It is a common thread among all machine learning techniques; finding the right tradeoff between underfitting and overfitting. The formal definition is the Bias-variance tradeoff (Wikipedia).
The bias-variance tradeoff
The following is a simplification of the Bias-variance tradeoff, to help justify the choice of your model.
We say that a model has a high bias if it is not able to fully use the information in the data. It is too reliant on general information, such as the most frequent case, the mean of the response, or few powerful features. Bias can come from wrong assumptions, for exemple assuming that the variables are Normally distributed or that the model is linear.
We say that a model has high variance if it is using too much information from the the data. It relies on information that is revelant only in the training set that has been presented to it, which does not generalize well enough. Typically, the model will change a lot if you change the training set, hence the "high variance" name.
Those definition are very similar to the definitions of underfitting and overfitting. However, those definition are often too simplified to be opposites, as in
Those simplifications are of course helpful, as they help choosing the right complexity of the model. But they overlook an important point, the fact that (almost) every model has both a bias and a variance component. The underfitting/overfitting description tell you that you have too much bias/too much variance, but you (almost) always have both.
If you want more information about the bias-variance tradeoff, they are a lot of helpful visualisation and good ressource available through google. Every machine learning textbook will have a section on the bias-variance tradeoff, here are a few
Also, a nice blog post that helped me grasp is Scott Fortmann-Roe's Understanding the Bias-Variance Tradeoff.
Application to your problem
So you have two models,
$$ \begin{array}{lrrl} & \text{Train MAE} & \text{Test MAE} &\\ \text{MARS} & \sim4.0 & \sim4.0 & \text{Low variance, higher bias},\\ \text{XGBoost} & \sim0.3 & \sim2.4 & \text{Higher variance, lower bias},\\ \end{array} $$
and you need to pick one. To do so, you need to define what is a better model. The parameters that should be included in your decisions are the complexity and the performance of the model.
The goal here is not to find a model that "does not overfit". It is to find the model that has the best bias-variance tradeoff. In this case, I would argue that the reduction in bias accomplished by the XGBoost model is good enough to justify the increase in variance.
What can you do
However, you can probably do better by tuning the hyperparameters.
Increasing the number of rounds and reducing the learning rate is a possibility. Something that is "weird" about gradient boosting is that running it well past the point where the training error has hit zero seems to still improve the test error (as discussed here: Is Deeper Better Only When Shallow Is Good?). You can try to train your model a little bit longer on your dataset once you have set the other parameters,
The depth of the trees you grow is a very good place to start. You have to note that for every one unit of depth, you double the number of leafs to be constructed. If you were to grow trees of size two instead of size 16, it would take $1/2^{14}$ of the time! You should try growing more smaller trees. The reason why is that the depth of the tree should represent the degree of feature interaction. This may be jargon, but if your features have a degree of interaction of 3 (Roughly: A combination of 4 features is not more powerful than a combination of 3 of those feature + the fourth), then growing trees of size larger than 3 is detrimental. Two trees of depth three will have more generalization power than one tree of depth four. This is a rather complicated concept and I will not go into it right now, but you can check this collection of papers for a start. Also, note that deep trees lead to high variance!
Using subsampling, known as bagging, is great to reduce variance. If your individual trees have a high variance, bagging will average the trees and the average has less variance than individual trees. If, after tuning the depth of your trees, you still encounter high variance, try to increase subsampling (that is, reduce the fraction of data used). Subsampling of the feature space also achieves this goal.
Best Answer
This is a fun question as it provides good context for why the often used heuristic that more parameters $\implies$ more risk of overfitting is just that, a heuristic. To ground the discussion let's consider what is in some sense the simplest problem, binary classification. As a specific example we will take the canonical generative-discriminative pair, naive Bayes and logistic regression respectively. It is important we look at corresponding pairs in this way. Otherwise anything we have to say is going to be useless. We could certainly come up with extraordinarily flexible generative models (imagine replacing the factored conditional $p(x|y)$ in naive Bayes with something like delta functions) which will essentially always overfit.
First we should define what we mean by overfitting. One useful definition of overfitting involves deriving tight probabilistic bounds on generalization error based on training set error and the type of classifiers we're using. In this case a relevant parameter is the VC dimension of the hypothesis class $H$ (the set of classifiers being used). Put simply the VC dimension of a hypothesis class is given by the largest set of examples such that for any possible labeling of that set, there exists an $h \in H$ which can label them in exactly that way. So given $m$ examples in a binary classification setting there are $2^m$ ways to label them. If there exists some set of $m$ example, and for each of the $2^m$ possible ways of labeling there is some $h \in H$ that labels them correctly, we can conclude $\text{VCdim}(H) \ge m$. Furthermore we say the set of $m$ points is shattered by $H$.
In turns out that naive Bayes and logistic regression both have the same VC dimension since they both classify examples in $n$ dimensions using an $n$ dimensional hyperplane. The VC dimension of an $n$ dimensional hyperplane is $n+1$. You can show this by upper-bounding the VC dimension using Randon's Theorem and then giving an example of a set of $n+1$ points which is shattered. Furthermore in this case our intuition from low dimensional examples generalizes to higher dimensions and we can make pretty pictures.
In this sense, both are equally likely to overfit because we'll generally get similar bounds on generalization. This also explain why 1 nearest neighbor is the king of overfitting, it has infinite VC dimension because it shatters every set of examples. This isn't the end of the story though.
Another useful way to formally define overfitting is based on obtaining generalization bounds in terms of the best predictor in the hypothesis class, i.e., the hypothesis we would all agree is best if we had an infinite number of examples. Here, things look different for the naive Bayes/logistic regression comparison. The first thing to note is that because of the way naive Bayes is parameterized (they need to specify valid conditionals, sum to 1, etc), we are not guaranteed to converge on the optimal linear classifier, even given an infinite number of examples. On the other hand, logistic regression will. So we can conclude that in fact the set of all naive Bayes classifiers is a proper subset of all logistic regression classifiers. This provides some evidence that indeed, naive Bayes classifiers may be less prone to overfit in this sense simply because they are less powerful/more constrained. Indeed this is the case. In short if we are performing classification in $n$ dimensional space, naive Bayes requires on the order of $O(\log n)$ samples to converge whp to the best naive Bayes classifier. Logistic regression requires on the order of $O(n)$. For a reference for this result see On Discriminative vs. Generative classifiers by Ng and Jordan.