Make sure you check the syllabus for the due date. Please use the notations adopted in class, even if the problem is stated in the book using a different notation.
UCI datasets: AGR, BAL, BAND, CAR, CMC, CRX, MONK, NUR, TIC, VOTE. (These are archives which I downloaded a while ago. For more details and more datasets visit http://archive.ics.uci.edu/ml/)
The relevant files in each folder are only two:
- .config : # of datapoints, number of discrete attributes, # of continuous
(numeric) attributes. For the discrete ones, the possible values are provided,
in order, one line for each attribute. The next line in the config file is the
number of classes and their labels.
- .data: following the .config convention the datapoints are listed, last column are the class labels.
(You should write a reader that given the .config file, reads the data from the .data file.)
Implement the Adaboost algorithm with decision stumps as weak learners, as described in class. Run it on the MCI data and report the results. The datasets CAR, CRX, VOTE are required, the others are Extra Credit.
Run the algorithm for each dataset using c% of the datapoints chosen randomly for training, for several c values: 5, 10, 15, 20, 30, 50, 80. Test on the datapoints not used for training. For statistical significance, you can repeat the experiment with different randomly selected data or you can use cross-validation.
Run your code from PB1 to perform active learning. Specifically:
- start with a training set of about 5% of the data (selected randomly)
- iterate M episodes: train the Adaboost for T rounds; from the datapoints not in the training set, select the one that is closest to the separation surface (smallest discriminant) and add it to the training set. Repeat until the size of the training set reaches 50% of the data.
How is the performance improving with the training set increase? Compare the performance of the Adaboost algorithm on the c% randomly selected training set with c% actively-built training set for several values of c : 5, 10, 15, 20, 30, 50. Perhaps you can obtain results like these
What is the VC dimension for the class of hyphothesis of
a) unions of two rectangles
b) circles
c) triangles
d) multidimensional "sphere" given by f(x) = sign [(x-c)(x-c) -b] in the Euclidian space with m dimensions. Justify your answers !
