Description

[created by Fernando Valladares Monteiro and Keith Jenkins]
You are given a dataset 𝐷!”## with 10 features and 10$ samples. We want to use a simple perceptron to test how the generalization bound, ε varies in practice as a
function of the number of samples 𝑁%&, the tolerance level δ, and the VC dimension 𝑑’(. Whenever you vary one of these parameters, the others should be kept constant.
Hint: Remember that the VC dimension of the perceptron equals the number of features plus one, i.e., 𝑑’( = 𝑑 + 1.

a) To study the dependence on the tolerance level use 𝑁%& = 1000, 𝑑’( = 4, δ = 0.01, 0.02, … 0.5 and follows the steps:
i) Use the parameters above to compute theoretical generalization bound values as a function of δ.
ii) Extract a dataset 𝐷)”* with 𝑁)”* = 10+ samples and the first 𝑑 (note that 𝑑 ≠ 𝑑’() features from 𝐷!”##. You will use this dataset to estimate 𝐸)”*.
iii) Extract a dataset 𝐷%& with 𝑁%& samples and the first 𝑑 features from 𝐷!”##, train a perceptron on 𝐷%&, and compute 𝐸%& and 𝐸)”*
iv) Repeat steps (iii) 1000 times, remembering to save all your results in arrays.
v) For each in the values above, determine the maximum value of |𝐸)”* − 𝐸%&| such that, over the 1000 runs, a proportion δ of the samples are above that value. Hint: for δ = 0.5, this value is the median. This provides an estimate of the generalization bound as a function of the tolerance level.
vi) Plot the results from (i) and from (v) side by side.
Would you say the theoretical bound is tight, moderate, or loose in this experiment? (Let’s define tight as within a factor of 2; moderate as a factor of 2-10; and loose as a factor of more than 10.) Would you say the relationship between the bound and the tolerance level is the same in theory and in the experiment, i.e., do the plots have similar shapes? If not, conjecture why if you can.

b) To study the dependence on VC dimension, you will vary the perceptron’s complexity by selecting only the first 𝑑 features. Use: 𝑁%& = 1000, 𝑑’( = [2 … 11], δ = 0.1 and follow the steps:
i) Use the parameters above to compute theoretical generalization bound values as a function of 𝑑’(
ii) Extract a dataset 𝐷)(-.”*) with 𝑁)”* = 10+ samples and all the 10 features from 𝐷!”##. You will use this dataset to estimate 𝐸)”*.
2
iii) Extract a dataset 𝐷%&(-.) with 𝑁%& = 1000 and all the features from the 𝐷!”##.
iv) For each 𝑑’( = [2 … 11]: create datasets 𝐷)(0″*) and 𝐷%&(0) by extracting the first 𝑑 (note that 𝑑 ≠ 𝑑’() features of 𝐷)(-.”*) and 𝐷%&(-.) respectively, train a perceptron on 𝐷%&(0), and compute 𝐸%& and 𝐸)”*.
v) Repeat steps (iii)-(iv) 100 times, remembering to save all your results in arrays.
vi) Determine the maximum value of |𝐸)”* − 𝐸%&| such that, over the 100 runs, a
proportion δ of the samples are above that value. This provides an estimate of the generalization bound as a function of the VC dimension.
vii) Plot the results from (i) and from (vi) side by side
Would you say the theoretical bound is tight, moderate, or loose in this experiment? (Let’s define tight as within a factor of 2; moderate as a factor of 210; and loose as a factor of more than 10.) Would you say the relationship between the bound and the VC dimension is the same in theory and in the experiment, i.e., do the plots have similar shapes? If not, conjecture why if you can. (Hint: the model that the data was generated from is very simple.)

c) To study the dependence on the number of samples use: 𝑁*12%& =
[10,30,100,300,1000,3000,10000], 𝑁*34* = 𝑁*12%&/5, 𝑑’( = 4, δ = 0.1 and follow the steps:
i) Use the parameters above to compute theoretical generalization bound values as a function of 𝑁*12%&.
ii) Use the parameters above to compute theoretical generalization bound values as a function of 𝑁*34*. Remember that the generalization bound for train and test sets have different formulas.
iii) Extract a dataset 𝐷)”* with 𝑁)”* = 10+ samples and the first 𝑑 (note that 𝑑 ≠ 𝑑’() features from𝐷!”##. You will use this dataset to estimate 𝐸)”* iv) For each 𝑁*12%&: extract a dataset 𝐷*12%& with 𝑁*12%& samples and 𝑑 features from 𝐷!”##, extract a dataset 𝐷*34* with 𝑁*12%&/5 samples and 𝑑 features from 𝐷!”##, train a perceptron on 𝐷*12%&, and compute 𝐸*12%&, 𝐸*34* and 𝐸)”*.
v) Repeat step (iv) 100 times, remembering to save all your results in arrays.
vi) Determine the maximum value of |𝐸)”* − 𝐸*12%&| such that, over the 100 runs, a proportion δ of the samples are above that value. This provides an estimate of the generalization bound as a function of the number of training samples.
vii) Repeat item (vi) for |𝐸)”* − 𝐸*34*|. viii) Plot the results from (i) and from (vi) side by side.
ix) Plot the results from (ii) and from (vii) side by side.
3