"Semi supervised learning" - is this overfitting?

Question

I was reading the report of the winning solution of a Kaggle competition (Malware Classification). The report can be found in this forum post. The problem was a classification problem (nine classes, the metric was the logarithmic loss) with 10000 elements in the train set, 10000 elements in the test set.

During the competition, the models were evaluated against 30% of the test set. Another important element is that the models were performing very well (close to 100% accuracy)

The authors used the following technique:

Another important technique we come up is Semisupervised Learning. We first generate pseudo labels of test set by choosing the max probability of our best model. Then we predict the test set again in a cross validation fashion with both train data and test data. For example, the test data set is split to 4 part A, B, C and D. We use the entire training data, and test data A, B, C with their pseudo labels, together as the new training set and we predict test set D.

The same method is used to predict A, B and C. This approach, invented by Xiaozhou, works surprisingly well and it reduces local cross validation loss, public LB loss and private LB loss. The best Semisupervised learning model can achieve 0.0023 in private LB log loss, which is the best score over all of our solutions.

I really don't see how it can improve the results. Is it because 30% of the test set was "leaked" and it was a way to use this information?

Or is there any theoretical reason explaining why it works ?

Answer 1

It doesn't appear to be overfitting. Intuitively, overfitting implies training to the quirks (noise) of the training set and therefore doing worse on a held-out test set which does not share these quirks. If I understand what happened, they did not do unexpectedly-poorly on held-out test data and so that empirically rules out overfitting. (They have another issue, which I'll mention at the end, but it's not overfitting.)

So you are correct that it takes advantage of the available (30%?) test data. The question is: how?

If the available test data has labels associated with it, you could simply lump it into your training data and enlarge your training data, which in general would yield better results in an obvious way. No real accomplishment there.

Note that the labels wouldn't have to be explicitly listed if you have access to an accuracy score. You could simply climb the accuracy gradient by repeatedly submitting scores, which is what people have done in the past with poorly-designed competitions.

Given that the available test data does not have labels associated with it -- directly or indirectly -- there are at least two other possibilities:

First, this could be an indirect boosting method where you're focusing on cases where your predictions with only the training data disagree with your predictions with the pseudo-labeled test data included.

Second, it could be straightforward semi-supervised learning. Intuitively: you could be using the density of unlabeled data to help shape the classification boundaries of a supervised method. See the illustration (https://en.wikipedia.org/wiki/Semi-supervised_learning#/media/File:Example_of_unlabeled_data_in_semisupervised_learning.png) in the Wikipedia definition of semi-supervised learning to clarify.

BUT this doesn't mean that there isn't a trick here. And that trick comes from the definition of training and test data. In principle, training data represents data that you could have in hand when you are ready to deploy your model. And test data represents future data that will come into your system once it's operational.

In that case, training on test data is a leak from the future, where you are taking advantage of data you would not have seen yet. This is a major issue in the real world, where some variables may not exist until after the fact (say after an investigation is done) or may be updated at a later date.

So they are meta-gaming here: what they did is legitimate within the rules of the competition, because they were given access to some of the test data. But it's not legitimate in the real world, where the true test is how well it does in the future, on new data.

Answer 2

It is not gross over fitting (depending on definition). Target information of test set is preserved. Semi-supervised allow to generate an extra synthetic data set to train the model on. In the described approach, original training data is mixed unweighted with synthetic in ratio 4:3. Thus, if the quality of the synthetic data is poor, the approach would turn out disastrous. I guess for any problem where predictions are uncertain, the synthetic data set would be of poor accuracy. If the the underlying structure is very complex and system has low noise, it may help to generate synthetic data, I guess. I think semi-supervised learning is quite big within deep learning (not my expertise), where the feature representation is to be learned also.

I have tried to reproduce increased accuracy with semi.supervised training on several data sets with both rf and xgboost without any positive result. [Feel free to edit my code.] I notice the actual improvement of accuracy using semi-supervised is quite modest in the kaggle report, maybe random?

rm(list=ls())
#define a data structure
fy2 = function(nobs=2000,nclass=9) sample(1:nclass-1,nobs,replace=T)
fX2 = function(y,noise=.05,twist=8,min.width=.7) {
  x1 = runif(length(y)) * twist
  helixStart = seq(0,2*pi,le=length(unique(y))+1)[-1]
  x2 = sin(helixStart[y+1]+x1)*(abs(x1)+min.width) + rnorm(length(y))*noise
  x3 = cos(helixStart[y+1]+x1)*(abs(x1)+min.width) + rnorm(length(y))*noise
  cbind(x1,x2,x3)
}

#define a wrapper to predict n-1 folds of test set and retrain and predict last fold  
smartTrainPred = function(model,trainX,trainy,testX,nfold=4,...) {
  obj = model(trainX,trainy,...)
  folds = split(sample(1:dim(trainX)[1]),1:nfold)
  predDF = do.call(rbind,lapply(folds, function(fold) {
    bigX      = rbind(trainX ,testX[-fold,])
    bigy      = c(trainy,predict(obj,testX[-fold,]))
    if(is.factor(trainy)) bigy=factor(bigy-1)
    bigModel  = model(bigX,bigy,...)
    predFold  = predict(bigModel,testX[fold,])
    data.frame(sampleID=fold, pred=predFold)
  }))
  smartPreds = predDF[sort(predDF$sampleID,ind=T)$ix,2]
}

library(xgboost)
library(randomForest)

#complex but perfect separatable
trainy = fy2(); trainX = fX2(trainy)
testy  = fy2();  testX = fX2(testy )
pairs(trainX,col=trainy+1)

#try with randomForest
rf = randomForest(trainX,factor(trainy))
normPred = predict(rf,testX)
cat("\n supervised rf", mean(testy!=normPred))
smartPred = smartTrainPred(randomForest,trainX,factor(trainy),testX,nfold=4)
cat("\n semi-supervised rf",mean(testy!=smartPred))

#try with xgboost
xgb = xgboost(trainX,trainy,
              nrounds=35,verbose=F,objective="multi:softmax",num_class=9)
normPred = predict(xgb,testX)
cat("\n supervised xgboost",mean(testy!=normPred))

smartPred = smartTrainPred(xgboost,trainX,trainy,testX,nfold=4,
                           nrounds=35,verbose=F,objective="multi:softmax",num_class=9)
cat("\n semi-supervised xgboost",mean(testy!=smartPred))



printing prediction error:
 supervised rf 0.007
 semi-supervised rf 0.0085
 supervised xgboost 0.046
 semi-supervised xgboost 0.049

Answer 3

No, it is not overfitting.

I think your worry here is that the model is byhearting the data instead of modeling it. That depends on the complexity of the model (which remained the same) and size of the data. It happens when the model is too complex and/or when the training data is too small, neither of which is the case here. The fact that the test error (cross-validation error) is minimized after the semi-supervised learning should imply that it is not over-fitted.

On why such an approach is even working
The approach used here is not out-of-world, I have seen many people doing this in many machine-learning competitions (Sorry, I tried, but cannot recollect where I have seen this).
When you predict a portion of test data and include that in the training, the model will be exposed to new features. In this case, the test data is as big as the training data, no wonder they are gaining so much by semi-supervised learning.

Hope this explains
Thanks

Answer 4

By this definition: "Overfitting occurs when a statistical model describes random error or noise instead of the underlying relationship."(wikipedia), the solution is not overfitting.

But in this situation:
- Test data is a stream of items and not a fixed set of items.
OR
- Prediction process should not contain learning phase (for example because of performance issues)

The mentioned solution is overfitting. Because the accuracy of modeling is more than real situations.