cs-m146-ps2

(c) What is the entropy of the label Y ? Solution: H ( X ) = 1 8 log(8) + 7 8 log 8 7 = 0 . 543 bits , since Y ∼ Bernoulli( 7 8 ) (d) Is there a split that reduces the entropy of Y by a non-zero amount? If so, what is it, and what is the resulting conditional entropy of Y given this split? (Again, as in lecture, you should restrict your attention to splits that consider a single attribute. Please use logarithm in base 2 to report Entropy.) Solution: Yes, by splitting along any of X 1 , X 2 , or X 3 . Using conditional entropy for X i , H ( Y | X i ) = 1 2 [0] + 1 2 1 4 log(4) + 3 4 log ( 4 3 ) = 0 . 406 bits. 2 Entropy and Information [5 pts] The entropy of a Bernoulli (Boolean 0/1) random variable X with P ( X = 1) = q is given by B ( q ) = − q log q − (1 − q ) log(1 − q ) . Suppose that a set S of examples contains p positive examples and n negative examples. The entropy of S is defined as H ( S ) = B p p + n . In this problem, you should assume that the base of all logarithms is 2. That is, log( z ) := log 2 ( z ) in this problem (as in the lectures concerning entropy). (a) Show that 0 ≤ H ( S ) ≤ 1 and that H ( S ) = 1 when p = n . Solution: Let p p + n = q . We take the first derivative of B with respect to q (use chain rule) and apply the first derivative test: dB dq = − log q − q ( q ln 2 ) − − log (1 − q ) + (1 − q ) 1 (1 − q )(ln 2)( − 1) = − log q + log (1 − q ) = 0 This gives us q = 1 − q , providing q = 0 . 5 as a critical point. Now, B ′ (0 . 3) > 0 and B ′ (0 . 7) < 0, so g = 0 . 5 is a maximum. The value is B (0 . 5) = 1. We then check the endpoints: the variable q is restricted to the range [0 , 1], and we have B (0) = 0, and B (1) = 0. The only critical point in the interval [0 , 1] is 0 . 5, and it is a maximum, so thus, 0 ≤ B ( q ) ≤ 1, which gives 0 ≤ H ( S ) ≤ 1, as desired. Then, when p = n , p p + n = p 2 p = 0 . 5, and according to the above, H ( S = 0 . 5) = 1, as desired. (b) Based on an attribute, we split our examples into k disjoint subsets S k , with p k positive and n k negative examples in each. If the ratio p k p k + n k is the same for all k , show that the information gain of this attribute is 0. Solution: Gain is defined as H [ S ] - H [ S | split ]. Taking advantage of this since p = ∑ k p k and n = ∑ k n k , if p k / ( p k + n k ) is the same for all k , it must be that p k / ( p k + n k ) = p/ ( p + n ) = q for all k . Then the entropy of S is B ( p/ ( p + n )) and the weighted average entropy of its children S k is: ∑ k p k + n k p + n B ( p k / ( p k + n k )) = p + n p + n B ( p/ ( p + n )) = B ( p/ ( p + n )). Substituting this expression and the expression for H [ S ] into the gain equation gives: Gain = B ( p/ ( p + n )) − B ( p/ ( p + n )) = 0. Thus, we have shown that this particular split results in no information gain. 3

4 Programming exercise : Applying decision trees and k-nearest neighbors [50 pts] Introduction 1 This data was extracted from the 1994 Census bureau database by Ronny Kohavi and Barry Becker. For computational reasons, we have already extracted a relatively clean subset of the data for this HW. The prediction task is to determine whether a person makes over $ 50K a year. In this problem, we ask you to complete the analysis of what sorts of people were likely to earn more than $ 50K a year. In particular, we ask you to apply the tools of machine learning to predict which individuals are more likely to have high income. Starter Files code and data • Code: CS146-Winter2023-PS1.ipynb • Data: nutil.py and adult subsample.csv documentation • Decision Tree Classifier: http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html • K-Nearest Neighbor Classifier: http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html • Cross-Validation: https://scikit-learn.org/stable/modules/generated/sklearn.model_selection.StratifiedShuffleSplit. html • Metrics: http://scikit-learn.org/stable/modules/generated/sklearn.metrics.accuracy_score.html , https://scikit-learn.org/stable/modules/generated/sklearn.metrics.f1_score.html?highlight=f1%20score# sklearn.metrics.f1_score • Data Preprocessing: https://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.StandardScaler.html?highlight= standardscaler#sklearn.preprocessing.StandardScaler Note that any portions of the code that you must modify have been indicated with TODO . Do not change any code outside of these blocks. To work on this HW: you need to download two files (i) nutil.py (ii) adult subsample.csv from here . Then copy/upload them to you own Google drive. 1 This assignment is adapted from the UCI Machine learning repository, available at https://archive.ics.uci. edu/ml/datasets/adult . 6

The following analysis is conducted keeping in the mind the data markers from the linked resource: • Workclass: Most people are self-employed. Government workers are most likely to make > 50k. • Education: The more educated a person is, the more likely they are to make > 50k. • Marital Status: Divorced people are the most likely to make > 50k. • Occupation: Sales and exec-managerial are most likely to make > 50k. • Relationship: Husbands are more likely to make > 50k. • Race: Most people in this dataset are white, but Asians have a high fraction of people making > 50k. • Native Country: Most people in this study are from the USA. Most of these people make < 50k. • Age: People in the 40-50 age group are most likely to make > 50k. • Fnlwgt: The fraction of people making > 50k is relatively constant. There are more people who make < 50k. • Education Nums: Most people have 8-10 years of education. People with ¿14 years of education have higher chances of making > 50k. • Capital Gain: Most people have a low capital gain. People with high capital gain tend to make > 50k. • Capital Loss: Most people have a low capital loss. People with high capital loss are evenly spread above the below the 50k mark. • Hours per week: Most people work around 40 hours weekly. People who work more tend to earn > 50k. • Sex: There are more women in this study. Women have a higher chance of making > 50k. 4.2 Evaluation [45 pts] Now, let’s use scikit-learn to train a DecisionTreeClassifier and KNeighborsClassifier on the data. Using the predictive capabilities of the scikit-learn package is very simple. In fact, it can be carried out in three simple steps: initializing the model, fitting it to the training data, and predicting new values. 2 (b) Before trying out any classifier, it is often useful to establish a baseline . We have implemented one simple baseline classifier, MajorityVoteClassifier , that always predicts the majority class from the training set. Read through the MajorityVoteClassifier and its usage and make sure you understand how it works. Your goal is to implement and evaluate another baseline classifier, RandomClassifier , that predicts a target class according to the distribution of classes in the training data set. For 2 Note that almost all of the model techniques in scikit-learn share a few common named functions, once they are initialized. You can always find out more about them in the documentation for each model. These are some-model-name.fit(...) , some-model-name.predict(...) , and some-model-name.score(...) . 9

(h) Another useful tool for evaluating classifiers is learning curves , which show how classifier performance (e.g. error) relates to experience (e.g. amount of training data). For this experi- ment, first generate a random 90/10 split of the training data using train_test_split from scikit-learn with random_state set to 0. Then, do the following experiments considering the 90% fraction as training and 10% for testing. Run experiments for the decision tree and k-nearest neighbors classifier with the best depth limit and k value you found above. This time, vary the amount of training data by starting with splits of 0 . 10 (10% of the data from 90% fraction) and working up to full size 1 . 00 (100% of the data from 90% fraction) in increments of 0 . 10. Then plot the decision tree and k-nearest neighbors training and test error against the amount of training data. Include this plot in your writeup, and provide a 1-2 sentence description of your observations. Solution: The Decision Tree error increases with the amount of training data. The training error is always less than the testing error. (i) Pre-process the data by standardizing it. See the sklearn.preprocessing.StandardScaler pack- age for details. After performing the standardization such as normalization please run all previous steps part (b) to part (h) and report what difference you see in performance. Solution: 12