Repeated Random Subsampling¶
Definition¶
First learn the function \(f_{\cal D}\) which is trained on the entire dataset \(\cal D\).
Then we partition \(\cal D\) into \(k\) subsets: \((\cal D_{train}, \cal D_{test})^{1} \dots (\cal D_{train}, \cal D_{test})^{k}\), where:
Which just means that our subset comprises of a test and train, which are disjoint from each other but combined equals the total dataset.
We learn the corresponding \(f\) from each \(k\) subsets: \((f^{(1)}, err^{(1)}) \dots (f^{(k)}, err^{(k)})\), where \(f^{(j)}\) is the j'th learned function and \(err^{(j)}\) is the corresponding error obtained from its corresponding test set.
We then take the average error such that:
And that is our generalized error approximation for our originally learned \(f_{\cal D}\).
Bias and Variance of the Estimator¶
The estimator has two sources of stochasticity:
- Randomness of the data (our dataset \(\cal D\) was sampled form some true distribution \(p\))
- Distribution in the partitioning (because we choose what \(k\) subsets to partition)
The error is biased because \(err^{(j)}\) is likely a pessimistically biased estimation of the true error. This is because we obtain \(err^{(j)}\) from the same dataset where the true error lies. However, since each \(err^{(j)}\) is obtained from a sample of the dataset, each \(f^{(j)}\) will likely have higher error than \(f_{\cal D}\). (since more data means lower error)
The bias depends on the size of the training data in the partition, and the size of the whole dataset. The larger the size of the training data, the closer \(f^{(j)}\) is to \(f_{\cal D}\) and so there is little bias.If most of the data is used in the test set, then the bias is bigger. The larger the whole data set is, the more the bias shrinks.
The variance of the estimator is:
The variance decreases when \(k\) is larger, and when \(\text{Var}[err^{(j)}]\) is smaller, which occurs when the dataset is larger.
Example¶
