Definition of Overfitting

Question

Consider error of hypothesis h over training data errortrain(h) and error over entire distribution D of data errorD(h). Hypothesis h in H overfits training data if there exists an alternative hypothesis h´ in H such that:

• errortrain(h) < errortrain(h´)

• errorD(h) > errorD(h´)

I am struggling to find literature on that topic.

Is there a more formal (or more detailed) definition of overfitting?

Answer 1

I'll partially answer your question, and focus on providing some insight. Within the scope of this answer, overfitting is caused due to two reasons: 1. bias in training data 2. complexity of model (hypothesis)

There are several cross-validation schemes to help estimate the extent of overfitting in the learnt model. See sklearn cross-validation and analysis of cross-validation on Iris dataset

With the objective of visualization for an intuitive insight, I'll use synthetic data towards regression analysis. The train-test splits of data are in practice done randomly to reduce bias in sample. However, i'm intentionally going to sample training data as contiguous chucks from the entire data in order to artificially emphasize bias while keeping interpretation of results simple.

My data is a polynomial with Gaussian noise. The degree of the polynomial, the mean and standard-deviation of noise are randomly assigned. In the experiment, I consider a hypothesis/model as a polynomial of different degrees. In my training data sampling scheme I progressively split the entire data into smaller equal chunks, wherein 'least bias' samples all the data and 'most bias' samples 1/4 contiguous chunk of data (multiple disjoint subsets).

The code I used to generate the results:

"""
Analysis of over-fitting in regression based on both bias sampling and model complexity
"""

import numpy as np
import matplotlib.pyplot as plt
from sklearn import linear_model
from numpy.polynomial.polynomial import polyval
from sklearn.model_selection import cross_val_predict
from sklearn.preprocessing import PolynomialFeatures
from sklearn.pipeline import Pipeline
from sklearn.metrics import mean_squared_error
import itertools
from matplotlib import cm
import matplotlib as mpl

def generate_data(num_data=100, degree=3, mu=0.0, sigma=0.1):
    """
    Generates a set of data points on a polynomial with Gaussian noise
    :param num_data: The number of data points generated
    :param degree: The degree of the polynomial, model complexity
    :param mu: mean of noise
    :param sigma: standard deviation of noise
    :return: array of data points
    """
    degree = np.random.randint(2, 4)
    num_coeff = degree+1
    coeff = list(np.random.rand(num_coeff))
    x_pts = list(np.random.rand(num_data))
    x_pts = [10*(i-0.5) for i in x_pts]
    x_pts = list(np.sort(x_pts))
    mu = 1*np.random.rand()
    sigma = 2*np.random.rand()+1
    noise = np.random.normal(mu, sigma, num_data)
    y_pts = polyval(x_pts, coeff, tensor=False)
    y_pts += noise
    y_pts = list(y_pts)
    data = [x_pts, y_pts]
    return data


def get_fit(input_data):
    reg = linear_model.LinearRegression()
    train_x = [[i, input_data[0][i]] for i in range(len(input_data[0]))]
    train_y = input_data[1]
    reg.fit(train_x, train_y)
    print(reg.coef_)
    x_min = min(input_data[0])
    x_max = max(input_data[0])
    n_pts = len(input_data[0])
    x = [x_min+i*(x_max-x_min)/n_pts for i in range(n_pts)]
    y = polyval(x, reg.coef_, n_pts)
    fig = plt.figure(1)
    plt.plot(input_data[0], input_data[1], 'k.')
    plt.plot(x, y,'r-')
    lr = linear_model.LinearRegression()
    predicted = cross_val_predict(lr, train_x, train_y, cv=10)
    plt.plot(x, predicted, 'gx')
    plt.show()


def polyfit(input_data, ax, input_degree=2, num_split=4):
    data = [[x[0], x[1]] for x in zip(input_data[0], input_data[1])]
    model = Pipeline([('poly', PolynomialFeatures(degree=input_degree)), ('linear', linear_model.LinearRegression(fit_intercept=False))])
    x = input_data[0]
    y = input_data[1]
    xs, ys = zip(*sorted(zip(x, y)))
    xs = np.array(xs)
    ys = np.array(ys)
    handles = []
    h, = ax.plot(xs, ys, 'kx', label='data')
    handles.append(h)
    colors = ['r', 'g', 'b', 'y']
    ns = num_split
    nd = len(x)
    bs = int(np.floor(nd/ns))
    y_max = max(ys)
    y_min = min(ys)
    sum_mse_train = 0.0
    sum_mse_test = 0.0
    for i in range(ns):
        x_train = xs[i*bs:(i+1)*bs]
        y_train = ys[i*bs:(i+1)*bs]
        """ split train and test into disjoint sets"""
        x_test = list(itertools.chain(xs[0:i*bs], xs[(i+1)*bs:-1]))
        y_test = list(itertools.chain(ys[0:i*bs], ys[(i+1)*bs:-1]))
        """ test is the entire available data to avoid discontinuity since training sample isn't random"""
        x_test = xs
        y_test = ys

        model = model.fit(x_train[:, np.newaxis], y_train)
        coeff = model.named_steps['linear'].coef_

        pred_train = polyval(x_train, coeff, len(x_train))
        mse_train = mean_squared_error(y_train, pred_train)
        sum_mse_train += mse_train
        pred_test = polyval(x_test, coeff, len(x_test))
        mse_test = mean_squared_error(y_test, pred_test)
        sum_mse_test += mse_test
        label_str = '#%d, Train:%.2f, Test:%.1E' % (i+1, mse_train, mse_test)
        ax.plot(x_train, pred_train, colors[i]+'.', linewidth=3)
        h, = ax.plot(x_test, pred_test, colors[i], label=label_str, alpha=0.5)
        handles.append(h)
        ax.set_ylim([y_min, y_max])
        ax.legend(handles=handles)
    mean_mse_train = sum_mse_train/ns
    mean_mse_test = sum_mse_test/ns
    return mean_mse_train, mean_mse_test


if __name__ == '__main__':
    data = generate_data(100, 3)
    print(data)
    max_degree = 4
    max_split = 4
    train_err = np.zeros((max_split, max_degree), dtype=np.float32)
    test_err = np.zeros((max_split, max_degree), dtype=np.float32)
    fig, axes = plt.subplots(max_split, max_degree)

    for n_split in range(1, max_split+1):
        for n_degree in range(1, max_degree+1):
            err_train, err_test = polyfit(data, axes[n_split-1, n_degree-1], n_degree, n_split)
            train_err[n_split-1, n_degree-1] = err_train
            test_err[n_split-1, n_degree-1] = err_test

    print(train_err)
    print(test_err)

    fig2 = plt.figure(2, figsize=(16, 8))
    ax1 = fig2.add_subplot(121, projection='3d')
    ax2 = fig2.add_subplot(122, projection='3d')

    # fake data
    _x = np.arange(max_split)
    _y = np.arange(max_degree)
    x, y = np.meshgrid(_x, _y)
    z_train = []
    z_test = []
    for i in x:
        for j in y:
            z_train.append(train_err[i, j])
            z_test.append(np.log(test_err[i, j]))
    print(len(z_train), len(z_test))
    btrain = np.zeros_like(z_train)
    btest = np.zeros_like(z_test)
    width = depth = 1

    nrm = mpl.colors.Normalize(np.min(z_train), np.max(z_train))
    colors = cm.bwr(nrm(np.array(z_train)))
    alpha = np.linspace(0.2, 0.95, len(x), endpoint=True)
    ax1.set_xlabel('level of bias')
    ax1.set_ylabel('model complexity')
    ax1.set_zlabel('mean square error')
    ax1.set_title('Err on Training data')
    for i in range(len(x)):
        ax1.bar3d(x[i], y[i], btrain[i], width, depth, z_train[i], alpha=alpha[i], color=colors[i], linewidth=0)

    ax2.set_xlabel('level of bias')
    ax2.set_ylabel('model complexity')
    ax2.set_zlabel('log(mean square error)')
    ax2.set_title('Err on Test data')
    nrm = mpl.colors.Normalize(np.min(z_test), np.max(z_test))
    colors = cm.RdBu(nrm(np.array(z_test)))
    for i in range(len(x)):
        ax2.bar3d(x[i], y[i], btest[i], width, depth, z_test[i], alpha=alpha[i], color=colors[i], linewidth=0)
    plt.show()

The regression fits, along with associated train/test error, I get for various degrees of bias introduced by the sampling scheme and the degree of the polynomial (model complexity) is shown below:

The interesting inference from this experiment is that the mean square error of regression fit to the data depends on both training bias and model complexity. So, if you wished to compare between hypotheses for comparative overfitting, you'll have to consider both these factors jointly to derive a meaningful conclusion.

The next figure shows the mean-square-error between the learnt model/hypothesis and the data.

For the training data error analysis. We get a result that corroborates intuition. When the training data is the entire available data (low bias) and the model complexity is low (polynomial of order 1 or straight line) the training error is high. This is natural when fitting a straight line to a quadratic or cubic function with Gaussian noise. As we increase the bias, i.e. only consider a small section of the data, the training error goes down. We'd expect this since a higher-order polynomial can be better approximated by a lower-order polynomial for a small continuous part of x-axis (recall Calculus). Again, when the model complexity goes up, i.e. degree of the hypothesis approaches the degree of the polynomial used to generate the data, the error diminishes.

The important point to note here in the graph is that as the degree of the hypothesis polynomial goes beyond that of the actual data, the training error continues to diminish. This is classical visualization of overfitting!

Now, if you look at the mean square error for test set, we get a different picture. Note that I've shown log of the error since high-order polynomials trained on highly biased training data diverge from the rest of the data dramatically.

In the test data case, the error follows a different profile. I hope you can notice it, but there is a 'sweet spot' when the mean square error is minimum for an optimal value of degree of polynomial of hypothesis and the degree of bias in the data.

If there is no bias in our sampled data (which never happens for real world data), then higher complexity model tend to fit the testing data better. However, when there is even a slight bias in the data, simply increasing model complexity is evidently counter-productive. It's better to have complexity somewhere in the 'middle', i.e. prefer quadratic to both linear and cubic.

I realize this is not the definition of overfitting, nevertheless, I hope the answer helps towards a better intuition of overfitting and the part that both the nature of the data and the hypothesis play.