We build a prediction model using one or machine learning algorithms for future use. The historic data used to train the model, for those you know the outcome already. So what you want to know at the end of the day, is how your prediction models perform on future data. Your test set or validation set are these 'future data'.
In general, the larger your training set is in terms of cases/observations the less likely overfitting is to occur - the situation you want to investigate using a separate test or validation set. On the other hand, the more flexible a prediction model is the higher the risk over overfitting.
For training classifiers some theoretical results are available. Confidence intervals for the error rate has been derived for linear and quadratic discriminant analysis. See chapter 10 in the book Discriminant Analysis and Statistical Pattern Recognition by G.J. McLachlan (Wiley), 2004. These confidence intervals provide bounds for the performance on future test data. For more complex learning algorithms, such theoretical results do not yet exist (to my knowledge, that is).
For nonparametric classifiers, you can only assess future performance using validation data.
Specifically, you perform imputation of missing values. As stated, different missing value mechanisms can be the case:
- MCAR (Missing Completely At Random)
- MAR (Missing At Random)
- NMAR (Not Missing At Random)
MCAR means that the probability that a data point is missing (i.e. a '?' in your data matrix), the observed data you do have - they give no clue what so ever about the most likely value (range) of the missing data point. Strict independence between the missing data mechanism and the observed data variables is present.
MAR means that the (unknown) value of the missing data point itself does not influence in any way the probability that the data point has gone missing. However, one or more observed data values do statistically determine whether that particular data value is missing. Strict independence between the actual value of the missing data point and the probability that it is missing, that is the case with MAR.
NMAR means MAR, plus that the value of the absent value itself statistically influences the probability that it has gone missing.
Imputation of missing values can be successful using existing schemes (such as the EM-algorithm), when the missing data mechanism is MCAR or MAR. Nonetheless, many scientific studies have shown that missing value imputation by the EM-algorithm tends to yield imputed values closer to the (conditional) means of the distribution of the missing data than is the case in the true underlying distribution. Multiple imputation is one approach to overcome this problem - a real challenge when your data are not normally distributed.
Final conclusion and my advice is as follows. You model the missing data mechanism, perform imputation and build a predictive model afterwards. Hence, even more parameters are being fitted in your scheme than when just building a prediction model in 'one go'. More parameters combined with a complex scheme that models possible higher order relations between variables (namely the missing data mechanism) - these factors make validation by independent test sets even more necessary.