Probabilistic Connection between Cross-Validation and Vapnik Bounds - Agents and Artificial Intelligence - page 46

Ta b l e 1 . Details (folds, repetitions) of an exemplary experiment no. 1

no. of
expe-
riment repetition fold R emp ( ω I )

is
ω I = ω I ? R emp ( ω I )

1 1 1 0 . 397 false 0 . 444

1 1 2 0 . 418 true 0 . 369

1 1 3 0 . 400 false 0 . 468

C = 0 . 417

1 2 1 0 . 359 true 0 . 369

1 2 2 0 . 374 true 0 . 339

0 . 370 0 . 348

C = 0 . 352

1 2 3 true

. . . . . .

1 10 1 0 . 403 true 0 . 384

1 10 2 0 . 395 true 0 . 399

1 10 3 0 . 394 true 0 . 399

C = 0 . 394

We show the results in two tables 1 and 2. The first one gives an insight on details of
a single exemplary experiment: results of its particular folds and repetitions. The second
one shows collective results, where each row encapsulates 10 repetitions 12 .
To comment on the results we first remark that before each single experiment (1-12)
the whole data set was drawn once from p ( z ) and remained fixed throughout repetitions.
However, in the repetitions due to the non-stratified cross-validation we parted the data
set (via permutations) into different training and testing subsets. That is why in the table
R emp ( ω I ) and V are constant per experiment, whereas the cross-validation varies within
some observed range. In the table 2 we also present the interval [ V − ε L , V + ε U ] which

is implied by the theorems.
Please note that for all experiments the observed range for C was contained inside

[ V ε U ] — an empirical confirmation of theoretical results. Although the bounds

are true with probability at least 1

− ε L , V +

− α ( η , n ) , in this particular experiment they held with

frequency one.
In particular one can note in the table that the upper bounds V +

ε U are closer to

actual C outcomes, while lower bounds V + ε L are more loose — a fact we already

indicated in theoretical sections. Only in the case of experiment no. 9 the lower bound
we obtained was trivial. In the results one can also observe the qualitative fact that both

intervals tighten with 1 / √ I approximately. Keep in mind that this result stops working
for the 'leave-one-out' cross-validation (or a close one) and we experimented on n = 3
and n = 5.

12

It was difficult to allow ourselves for more repetitions, say 100, due to large amount of results
and the time-consumption of each experiment. Yet, the observed ratio 1 . 0of C falling inside
bounds shows that 10 repetitions was sufficient.