Implementation of nested cross-validation

Question

I'm trying to figure out if my understanding of nested cross-validation is correct, therefore I wrote this toy example to see if I'm right:

import operator
import numpy as np
from sklearn import cross_validation
from sklearn import ensemble
from sklearn.datasets import load_boston

# set random state
state = 1

# load boston dataset
boston = load_boston()

X = boston.data
y = boston.target

outer_scores = []

# outer cross-validation
outer = cross_validation.KFold(len(y), n_folds=3, shuffle=True, random_state=state)
for fold, (train_index_outer, test_index_outer) in enumerate(outer):
    X_train_outer, X_test_outer = X[train_index_outer], X[test_index_outer]
    y_train_outer, y_test_outer = y[train_index_outer], y[test_index_outer]

    inner_mean_scores = []

    # define explored parameter space.
    # procedure below should be equal to GridSearchCV
    tuned_parameter = [1000, 1100, 1200]
    for param in tuned_parameter:

        inner_scores = []

        # inner cross-validation
        inner = cross_validation.KFold(len(X_train_outer), n_folds=3, shuffle=True, random_state=state)
        for train_index_inner, test_index_inner in inner:
            # split the training data of outer CV
            X_train_inner, X_test_inner = X_train_outer[train_index_inner], X_train_outer[test_index_inner]
            y_train_inner, y_test_inner = y_train_outer[train_index_inner], y_train_outer[test_index_inner]

            # fit extremely randomized trees regressor to training data of inner CV
            clf = ensemble.ExtraTreesRegressor(param, n_jobs=-1, random_state=1)
            clf.fit(X_train_inner, y_train_inner)
            inner_scores.append(clf.score(X_test_inner, y_test_inner))

        # calculate mean score for inner folds
        inner_mean_scores.append(np.mean(inner_scores))

    # get maximum score index
    index, value = max(enumerate(inner_mean_scores), key=operator.itemgetter(1))

    print 'Best parameter of %i fold: %i' % (fold + 1, tuned_parameter[index])

    # fit the selected model to the training set of outer CV
    # for prediction error estimation
    clf2 = ensemble.ExtraTreesRegressor(tuned_parameter[index], n_jobs=-1, random_state=1)
    clf2.fit(X_train_outer, y_train_outer)
    outer_scores.append(clf2.score(X_test_outer, y_test_outer))

# show the prediction error estimate produced by nested CV
print 'Unbiased prediction error: %.4f' % (np.mean(outer_scores))

# finally, fit the selected model to the whole dataset
clf3 = ensemble.ExtraTreesRegressor(tuned_parameter[index], n_jobs=-1, random_state=1)
clf3.fit(X, y)

Any thoughts appreciated.

Answer 1

UPS, the code is wrong, but in a very subtle way!

a) the splitting of the train set into a inner training set and test set is OK.

b) the problem is the last two lines, which reflect the subtle misunderstanding about the purpose of a nested cross-validation. The purpose of a nested CV is not to select the parameters, but to have an unbiased evaluation of what is the expected accuracy of your algorithm, in this case ensemble.ExtraTreesRegressor in this data with the best hyperparameter whatever they might be.

And this is what your code correctly computes up to the line:

    print 'Unbiased prediction error: %.4f' % (np.mean(outer_scores))

It used the nested-CV to compute an unbiased prediction of the classifier. But notice that each pass of the outer loop may generate a different best hyperparameter, as you knew when you wrote the line:

   print 'Best parameter of %i fold: %i' % (fold + 1, tuned_parameter[index])

So now you need a standard CV loop to select the final best hyperparameter, using folds:

tuned_parameter = [1000, 1100, 1200]
for param in tuned_parameter:

    scores = []

    # normal cross-validation
    kfolds = cross_validation.KFold(len(y), n_folds=3, shuffle=True, random_state=state)
    for train_index, test_index in kfolds:
        # split the training data
        X_train, X_test = X[train_index], X[test_index]
        y_train, y_test = y[train_index], y[test_index]

        # fit extremely randomized trees regressor to training data
        clf2_5 = ensemble.ExtraTreesRegressor(param, n_jobs=-1, random_state=1)
        clf2_5.fit(X_train, y_train)
        scores.append(clf2_5.score(X_test, y_test))

    # calculate mean score for folds
    mean_scores.append(np.mean(scores))

# get maximum score index
index, value = max(enumerate(mean_scores), key=operator.itemgetter(1))

print 'Best parameter : %i' % (tuned_parameter[index])

which is your code but with references to inner removed.

Now the best parameter is tuned_parameter[index], and now you can learn the final classifier clf3 as in your code.

Answer 2

I have released a package that can help implementing nested cross validation in Python (for the moment, it only works for binary classifiers). If you want to check it out, it's here:

https://github.com/JaimeArboleda/nestedcvtraining

It's my first Python package, so any comments, suggestions or critics will be more than welcome!!

I post it as an answer because nested cross validation is performed inside the main function and you don't have to take care of how to implement it. It comes with many options thay may be enough for a lot of common settings I think.

Answer 3

To summarize Jacques' answer,

Nested CV is required for a model's unbiased error estimation. We can compare the score of different models in this manner. Using this information, we can then perform a separate K-fold CV loop for parameter tuning of the selected models.