Cross-validation is a statistical method of evaluating and comparing hypothesis functions by dividing data into two segments. One segment is used to induce the hypothesis function and the other segment used to test the hypothesis function¹. Various cross-validation techniques exist, including hold-out cross-validation, $k$-fold cross-validation and leave-one-out cross-validation.

To acheive a robust the empirical loss associated with a given hypothesis function one can use estimate of $k$-fold cross-validation². The empirical loss³ is a measure of how well the hypothesis function $h$ approximates the true function $f$, calculated as,

where the loss function $L(y,h(\vec{x}))$ measures the extent with which the predicted class variable value $\hat{y}=h(\vec{x})$ differs from the actual class variable value $y$. Many different loss functions exist⁴, such as the mean-squared-error loss function,

or the cross-entropy loss function,

In this dissertation, the 0-1 loss function is used to calculate the empirical loss associated with a hypothesis function presented,

Using cross-validation provides valuable insight into the stability of the empirical loss associated with a given hypothesis function. Empirical loss may vary due to the choice of the testing set; the choice of the training set; the internal randomness of the induction algorithm; as well as the random classification error due to having mislabelled objects in the testing data⁵.

In model selection, $k$-fold cross-validation is employed to estimate the empirical loss associated with a given hypothesis function as summarized in Algorithm alg:modelselection. Several classifiers are trained, each with a different hyper-parameter configuration $\vec{\lambda}$. The best hyper-parameter configuration $\vec{\lambda}^*$ is selected in order to minimize the empirical loss $R_{emp}(h^{\vec{\lambda}})$. During cross-validation the dataset ${D}$ is split into $k$ subsets ${S_1},{S_2},...,{S_k}$ each with an approximately equal number of example instances. The set ${T_i} = {D} − {S_i}$ with $i=1..k$ is divided equally into a training subset $T_{i1}$ and validation subset $T_{i2}$. The subset $T_{i1}$ is used for training the classier, the subset $T_{i2}$ is used to calculate empirical loss of the induced classifier $h_i^{\vec{\lambda}}$, while subset $S_i$ is not used. The hypothesis $h^{\vec{\lambda}}$ is trained and validated $k$ times, each time producing an empirical loss estimate. The $k$ individual empirical loss estimates are averaged to calculate the reported empirical loss for classifier $h^{\vec{\lambda}}$.

After finding the best hyper-parameter configuration $\vec{\lambda}^*$ (the one with the lowest associated empirical loss), the empirical loss for hypothesis $h^{\vec{\lambda}}$ with $\vec{\lambda} = \vec{\lambda}^*$ is estimated using the set $T_i$ as training set, and the set $S_i$ as testing set as outlined in algorithm below. The hypothesis $h^{\vec{\lambda}}$ is trained and tested $k$ times, each time producing an empirical loss estimate. The $k$ individual empirical loss estimates are averaged to calculate the reported empirical loss for classifier $h^{\vec{\lambda}}$.

In this way, model selection is done independently from model evaluation, because $S_i$ is not used during model selection but to estimate the performance of the classifier only after a hyper-parameter configuration was selected. The phenomenon of peaking, where the same data set is used for both selecting and evaluating a hypothesis, is therefore avoided⁶.

Notes

• Originally published as part of Wilgenbus, E.F., 2013. The file fragment classification problem: a combined neural network and linearprogramming discriminant model approach. Masters thesis, North West University.

References

Related tags

data and decision science