Machine Learning - Homework #1

1. Decision tree learning (25 pts.)

The following table gives a data set for deciding whether to play or cancel a ball game, depending on the weather conditions.

(a) (8 pts.) At the root node for a decision tree in this domain, what are the information gains associated with the Outlook and Humidity attributes? (Use a threshold of 75 for humidity (i.e., assume a binary split: humidity <= 75 / humidity > 75). Be sure to show your computations.

(b) (8 pts.) Again at the root node, what are the gain ratios associated with the Outlook and Humidity attributes (using the same threshold as in (a))? Be sure to show your computations.

(c) (9 pts.) Suppose you build a decision tree that splits on the Outlook attribute at the root node. How many children nodes are there are at the first level of the decision tree? Which branches require a further split in order to create leaf nodes with instances belonging to a single class? For each of these branches, which attribute can you split on to complete the decision tree building process at the next level (i.e., so that at level 2, there are only leaf nodes)? Draw the resulting decision tree, showing the decisions (class predictions) at the leaves.

2. Decision Trees and Linear Discriminants (15 pts.)

Describe how to modify a classic decision tree algorithms to obtain oblique splits (i.e, splits that are not parallel to an axis).

3. K-Nearest Neighbor (10 pts.)

Consider the following labeled data set:

2, 4, +
4, 2, +
4, 4, -
4, 6, +
6, 2, -
6, 4, +

(a) (6 pts) Plot the data twice and draw the decision surface that separates the two classes (+ and -) for both k=1 and k=3.

(b) (2 pts) How would you classify a point at (8,1) for both k=1 and k=3?

(c) (2 pts) How would you classify a point at (8,8) for both k=1 and k=3?

4. Linear Regression and kNN (25 pts.)

[Exercise 2.7 from Hastie, et al.] 
Suppose we have a sample of N pairs (x_i, y_i) drawn i.i.d. from the distribution characterized as follows:
    x_i ∈ X, the set of instances
    y_i = f(x_i) + ε_i,  where f() is the regression function
    ε_i ~ G(0, σ²), a Gaussian with mean 0 and variance σ²
We can construct an estimator for f() that is linear in the yⁱ,
    f (x₀) = ∑_i=1..N  l_i(x₀; X) y_i ,
where the weights l_i(x₀; X) do not depend on the y_i, but do depend on the entire training set X.

Show that both linear regression and k-nearest neighbor regression are members of this class of estimators.  Explicitly describe the weights l_i(x₀; X) for each of these algorithms.

5. Machine Learning in WEKA (25 points)

In this problem, you will gain familiarity with the WEKA (Waikato Environment for Knowledge Analysis) machine learning toolkit. It is widely used in the machine learning community, and provides both a graphical interface and Java API to a wide variety of standard machine learning algorithms. Using WEKA will help reinforce the material we covered in class.

You must download and install WEKA from the following location: http://www.cs.waikato.ac.nz/ml/weka/. The "Getting Started" section of that page has links for information on system requirements, how to download the software, and documentation. WEKA is written in Java and should run on any platform with Java 1.4 or higher.

In addition to the reading that I handed out in class, here is a site that contains documentation on WEKA:

• http://www.cs.waikato.ac.nz/ml/weka/index_documentation.html

When you run WEKA, you should choose the use the "WEKA Explorer" when answering these questions. One problem that I sometimes run into is that WEKA needs more memory than java gives it by default. You can use java's "-Xmx" option to have java allocate more memory to the virtual machine. For example "java -Xmx200M ..." would have java allocate a maximum of 200 MB to the virtual machine.

Download the hw1-mushroom.arff data file and load it into WEKA in the preprocess tab. The mushroom task involves identifying poisonous or edible mushrooms from their features. In the classify tab, try out the following classifiers, using 10-fold cross-validation to get accurate estimates of the performance of each algorithm.:

• Logistic Regression (classifiers.functions.Logistic).
• J48 (classifiers.trees.J48), which is WEKA's decision tree implementation.
• IBk (classifiers.lazy.IBk), which is WEKA's k-Nearest Neighbor implementation. Vary the KNN parameter to set the number of neighbors to both 1 and 4.

(a) (5 pts) Create a table reporting the classification accuracy of each algorithm on the mushroom data.

(b) (5 pts) On this particular problem, WEKA reported the following performance information for two of the algorithms: (note that your numbers in part (a) may vary)

Even though the algorithms both have the same reported accuracy, their True/False positive rates are different. For this particular problem, identifying poisonous mushrooms, is one algorithm better? If so, which one? Justify your answer by explaining why one is better or why they're both equally good.

(c) (5 pts) Run the J48 algorithm with and without reduced error pruning on the hw1-zoo.arff data. Explore varying the numFolds variable for reduced error pruning between 2 and 10 folds. You do not need to run every number; just pick a number of samples intelligently.

Plot the performance accuracy as a function of the number of folds in a properly-formatted graph (axes labeled, clear title, etc.). (You generate the plot by computer.) In a few sentences, describe the effect of reduced error pruning on the induced decision tree. Why does reduced error pruning improve the classification accuracy of the decision tree? (Hint: what machine learning phenominon is occurring?) How does the numFolds variable affect the pruning and why?

(d) (10 pts) For this problem, you will create a classifier for some unknown data. The training data is contained in hw1-unknown2-train.arff. You should attempt to construct the best model you can for this training data. You can use cross-validated accuracy to determine your chosen model or any other evaluation criteria you want. You can use any WEKA classifier you want, even those other than the ones we've used in this homework, with any settings. Some classifiers perform dramatically different depending on the settings.

Report the best 10-fold cross-validated accuracy you can on this training data. What algorithm did you use to create the model? Justify any parameter settings you changed. Include a paragraph describing the algorithm you used for creating the model. If you settled on one that we didn't cover in class, you will have to do a bit of outside reading to understand it and be able to describe it. Tell why you think the algorithm you chose did the best.

(Extra credit) The real test of machine learning algorithms is taking a learned model and applying it to never-before-seen data to test its effectiveness.

The file hw1-unknown2-test-unlabeled.arff contains a number of unlabeled data drawn from the same distribution as the unknown training data you saw in (d) above. Once you've developed your learned model, you can apply it to the new test data. Make sure that the training data set is loaded into WEKA and your classifier options are all set as before. (If you do this immediately after (d), you should only have to do the next instruction.) Change the test option from cross-validation to "Supplied test set" and set it to use the hw1-unknown2-test-unlabeled.arff file for testing. Also, change the "More options..." to "Output predictions" for the data. When you "Start" the evaluation, WEKA will train your model on the training data and output predictions for the unlabeled data.

The classifier output should now have predicted labels for every test instance. Ignore that WEKA tells us that every predition is an error -- it does this because the test data does not have any class labels. The table will look something like the following (the predicted labels are contained in the third column):

=== Predictions on test set ===
inst#, actual, predicted, error, probability distribution
1        ?       1:f       +       *0.926  0.074
2        ?       2:t       +        0.045 *0.955
3        ?       2:t       +        0.045 *0.955
...     ...      ...      ...        ...    ...

Copy only the predicted t/f values from the third column into a text file, without headers, one per row and in order (trimming whitespace above and below it) into a text file.  For example, the table above would look like simply:

f
t
t
...

Name the file  <LASTNAME><FIRSTNAME>HW1EC.out (where <LASTNAME> and <FIRSTNAME> are your names, of course. For example, my file would be called EatonEricHW1EC.out), and submit it as an attachment to me via e-mail.  The subject line for your e-mail should be exactly "CS 380:  HW1 Extra Credit".

I'll evaluate the performance of your classifier on the test data by computing the accuracy of your predictions with the true labels for the test data. Anyone who submits their predictions will receive 5 extra credit points.  The three people with the highest test accuracies will get 5 additional extra credit points!