2
$\begingroup$

In Rapid Miner, I created a predictive model (SVM) with Kernel type = polynomial, c= 10, and obtained 80.77% accuracy using cross validation. When compared to hold out set my accuracy on the test set was: 71.54472%. That is 9.23% difference. My questions are 1) Is my SVM model overfit? 2) I created other models like k-NN, decision trees, Naive bayes etc but they all gave accuracy of less than 70%. Will the difference against the hold out set be less than 9.23% ?

$\endgroup$
4
  • $\begingroup$ How did you choose the polynomial and the regularisation parameter? $\endgroup$ Nov 12, 2012 at 17:17
  • $\begingroup$ @DikranMarsupial I tried all of the kernels with c=10 and polynomial kernel is the only one which gave accuracy more than 70%. $\endgroup$
    – Siga
    Nov 12, 2012 at 19:29
  • $\begingroup$ do you mean cross-validation accuracy or test accuracy? $\endgroup$ Nov 13, 2012 at 8:26
  • $\begingroup$ It is cross validation accuracy. $\endgroup$
    – Siga
    Nov 13, 2012 at 13:37

4 Answers 4

3
$\begingroup$

This question cannot be answered without knowing the test sample size of the holdout set and the number of samples in the cross validation, because they heavily influence the random uncertainty of both hold out estimate and cross validation estimate.

Also, did you perform the cross validation independently of the modeling (i.e. any data-driven optimization (data pre-processing, choice of c, choice of kernel)?


Edit: using the detail information provided in the comment.

Terminology I use:

  • Overfitting is caused by (some reason).
  • Optimistic bias of cross validation results is a symptom of overfitting.
Considering the sample sizes:

In order to judge whether the cross validation results are accidentally better (random error) than the hold out set or whether this is systematic (optimistic bias; symptom of overfitting) we need to consider random uncertainty due to finite test sample size.

p.cv <- 0.8077
p.ho <- 0.7154472

n.cv <- 4545
n.ho <- 1968

Now, calculate 95% confidence intervals for the observed proportions:

require("binom")
binom.wilson(round(p.cv * n.cv), n.cv) # pick your method of choice

##   method    x    n   mean lower  upper
## 1 wilson 3671 4545 0.8077 0.796 0.8189

binom.wilson(round(p.ho * n.ho), n.ho)

##   method    x    n   mean  lower  upper
## 1 wilson 1408 1968 0.7154 0.6951 0.7349

They are well apart, so the cross validation is optimistically biased. By the way: this should also tell you how to sensibly round the reported numbers.

We could have directly tested for equal proportions:

prop.test(round(c(p.cv * n.cv, p.ho * n.ho)), c(n.cv, n.ho), alternative = "greater")

## 
##  2-sample test for equality of proportions with continuity
##  correction
## 
## data:  round(c(p.cv * n.cv, p.ho * n.ho)) out of c(n.cv, n.ho) 
## X-squared = 67.54, df = 1, p-value < 2.2e-16

[...snip...]

There's a second source of random testing uncertainty for the cross validation. You can check that e.g. by doing repeated/iterated $k$-fold cross validation and checking the variance between different predictions for the same sample.

Why is the cross validation optimistically biased?

Cross validation by itself is not optimistically biased. It may have a slight pessimistic bias. The optimistic bias comes from confusing what exactly is measured and what should be estimated. If you want to estimate the performance for unknown samples, then you need to make sure that you test with unknown samples. If you want to measure goodness-of-fit, then use known samples.
Esbensen and Geladi (2010): Principles of Proper Validation: use and abuse of re-sampling for validation gives a thorough discussion of such considerations (and goes a step further: if you want to estimate performance for future unknown samples, you need to acquire unknown samples a certain time after the training samples were acquired, etc.).

In my experience, these are the 3 most common ways of test-sample information leaking into model training:

  • Data-driven optimization means that the test data enters the model in form of hyper-parameters (Dikran's terminology). That can be cross validation, but it cannot be the cross validation you use for choosing the best model. Optimization is a multiple testing situation, and selecting the apparently best of $m$ models wil "skim" the random testing uncertainty. I.e. the more models you compare, the higher the risk for overfitting. This kind of overfitting can happen even if the model has apparently restricted degrees of freedom. See Eriks and Dikrans answers and Dikran's paper.

  • All data-driven steps in the model building e.g. feature generation or data pre-treatment that uses multiple cases (i.e. cannot sensibly be done one row alone), like

    • centering on the column averages,
    • variance scaling,
    • MSC without fixed reference,
    • using PCA scores as input for the "actual" classifier
    • etc. - you get the idea need to be done separately for each cross validation split. These steps determine hyper-parameters as well.
      The same would of course apply to data-driven post-processing of the classifier output.
      You have this for sure: "Only polynomial kernel give accuracy of more than 70% with c=10. So I chose that model."
  • Rows of your data matrix are not independent. This happens with "clustered" or "hierarchical" data structures. You may say you have multiple rows per case, e.g.

    • repeated measurements of the same case
    • several samples taken from each patient
    • multiple locations measured on the same specimen

The common point is that the test data is not unknown to the model: with data driven optimization, you adapt the model to that particular test set. If determine PCA projection from the whole data set, then the (later) test data did influence this projection. If you have multiple rows of data of a case , make sure your cross validation splits the highest level cases (e.g. patients).

Edit: as you comment above that you are very new to the whole field, feel free to ask for more literature. Also dig around here at cross validated. There are lots of useful questions and answers about (cross) validation topics.

$\endgroup$
2
  • $\begingroup$ the training set contains 4545 examples. the test set contains 1968 examples. The holdout set is with my lecturer and I have no idea how big it is. I used K-NN, Logistic Regression, Naive Bayes and SVM. For SVM, I used c=10 on kernels like multiquadratic, dot, radial and polynomial. Only polynomial kernel give accuracy of more than 70% with c=10. So I chose that model $\endgroup$
    – Siga
    Nov 13, 2012 at 13:45
  • $\begingroup$ Thank you very much for taking the time to answer my questions, There are terms that I am not familiar with and need to read more like PCA projection and MSC without fixed reference. Also, I think binom.wilson is an R function? I will have to find similar one in RapidMiner. Also, When you mentioned 2 sample test for equality of proportions, do you mean 1 sample from the training and another 1 sample from the test set? I will read the link that you gave. Thank you very much for that too :D $\endgroup$
    – Siga
    Nov 13, 2012 at 21:50
2
$\begingroup$

The simple is answer is yes, the fact that your accuracy goes down when you compare to a new set means that your model is overfitted. However, almost all models will display this behavior, so it doesn't mean that you don't have a good model. 71% accuracy is still very good for many purposes, but you need to ask yourself if it is "good enough" for your purpose.

I can't tell you if the differences with other models between cross-validation sets or test sets will be less than 9%. You will have to perform the predictions with those models yourself, and compare them.

I doubt that these other models that you have tried will be better than the one you have just described. If the accuracy is less than 70% on a cross-validation set, it's possible though very unlikely that they will be more accurate on a test set.

$\endgroup$
4
  • 1
    $\begingroup$ This is not quite correct, if cross-validation performance is performed correctly, it is almost unbiased, so it should give the same performance estimate as a test set in expectation, whether the model is over-fit or not. However, in this case CV has been used to make model choices, so it is no longer an (almost) unbiased estimator. $\endgroup$ Nov 13, 2012 at 13:53
  • $\begingroup$ Yes I am quite a beginner and I followed the tutorials in youtube. They showed that in order to obtain accuracy, I need to use cross validation. I also used ROC chart and compare the models. k-NN, Naive bayes and decision tree graph, didn't look normal. While SVM and logistic regression give the normal curve graph.I then chose SVM because it plots higher than logistic regression $\endgroup$
    – Siga
    Nov 13, 2012 at 17:43
  • $\begingroup$ @siga, it is a problem that is quite common in machine learning, which is one of the reasons I wrote the paper I mentioned in my answer. I was very surprised when I saw the experimental results just how big a difference this can make. It is easy to get round though, use nested cross-validation (see the paper for details). $\endgroup$ Nov 13, 2012 at 18:15
  • $\begingroup$ Thank you very much for the help @DikranMarsupial . I sure will refer to the paper that you wrote. :D $\endgroup$
    – Siga
    Nov 13, 2012 at 21:33
1
$\begingroup$

As the models have been chosen by optimising the cross-validation error, I suspect this is part of the reason for the cross-validation accuracy being a lot higher than the test error. Essentially the model has been tuned by optimising the cross-validation error, which means it then provides an optimistically biased estimate of performance. The bias introduced by this king of thing can be surprising large, and can easily result in drawing incorrect conclusions, see

G. C. Cawley and N. L. C. Talbot, Over-fitting in model selection and subsequent selection bias in performance evaluation, Journal of Machine Learning Research, 2010. Research, vol. 11, pp. 2079-2107, July 2010. (www)

Consider a problem were the aim is to predict the outcome of 10 flips of an unbiased coin. The "model predictions" are formed by generating 10 flips of other unbiased coins (so that the skill of the predictions is exactly zero). However if you choose the best of these models on the 10 flips you observed, you are likely to get one that appears to have some skill and the more models you have to choose from, the greater the apparent skill. However, the best model will still have skill of zero if the coin is flipped another ten times.

Likewise, if you choose your model by optimising the CV accuracy, the choice is partly due to genuine gains in generalisation, but also partly due to random chance (you have over-fitted the cross-validation estimate). As a result, the CV accuracy is higher than the true generalisation performance of the model (estimated by the test set).

@cbeleites also makes an excellent point (+1) that if the test and training sets are small, then the performance estimates (both CV and test set) will have a high variance, so it wouldn't be too surprising for one to be higher or lower than the other.

$\endgroup$
1
  • $\begingroup$ Thank you for the reply. Yes I chose my model based on the CV accuracy and partly from the ROC chart. But I was not too sure of the ROC chart because 2 of the models that I designed gave weird pattern on the ROC chart. Thank you for the link too. It sure helps me in writing my report :) $\endgroup$
    – Siga
    Nov 13, 2012 at 21:31
1
$\begingroup$

There is more than one possible cause here. Model overfitting is one for sure. I don't know how you fitted the model, with an SVM you tune the parameters by CV as well. If the tuning CV and performance estimation CV is the same (you should have two, with the tuning CV layered within the estimation CV) then yes, your model is probably overfitted.

OTH this can simply be chance. It depends on the size of both your training and hold whether this is a plausible explanation. Even if your cv-estimated accuracy was absolutely correct, the test accuracy will still be binomially distributed around it, so you can check. But there is also uncertainty involved with the cv-estimated accuracy, so you also need to check the range of your confidence interval for that.

$\endgroup$
1
  • $\begingroup$ Thank you for the comment. As a beginner, I randomly select the c value for SVM. May I ask do you mean tuning CV as in training CV? and the estimation CV, do you mean the predicted cross validation (accuracy) on the selected model? My lecturers did not inform me the size of the hold set , they only gave me my accuracy on the test set when compared to hold out set. $\endgroup$
    – Siga
    Nov 13, 2012 at 18:22

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.