Chapter 9- Decision Trees

Question 1

is the process of automatically creating a tree from data is recursive, true or false?

Answer 1

true

Question 2

give the ID3 algorithm

Answer 2

base case:
if depth==0 or all labels have the same label
return most common label in the subsample

recursive case:
for each feature:
    split the data
    calculate the cost for this stump
pick feature with minimum cost

add left branch = build tree(left subsample, depth-1)
add right branch = build tree(right subsample, depth-1)

Question 3

what do we risk as we split on fewer and fewer examples?

Answer 3

we could risk making new nested rules for few examples, which may just be outliers, just noise in the data

Question 4

what two restrictions can we place on a decision tree to prevent overfitting?

Answer 4

maximum depth

minimum subsample size

Question 5

what is a strong indicator that a decision tree is overfitted?

Answer 5

it is very deep

Question 6

what is a decision tree splitting criterion?

Answer 6

split based on the number of errors, i.e. count the number of misclassified samples after split

Question 7

what is another word for information gain

Answer 7

mutual information

Question 8

how do we determine which features would give us the most information?

Answer 8

measure the information gain as a score for each feature

Question 9

what does entropy measure?

Answer 9

entropy is a mathematical expression that quantifies the randomness- the amount of randomness

Question 10

the entropy for variable X, H(X)=?

Answer 10

• sum for each x: p(x)logp(x)

log base 2

Question 11

what is the equation for information gain, I(T;W) = ?

Answer 11

H(T) - H(T|W)
or
H(W) - H(W|T)

Question 12

given that information gain is H(T) - H(T|W), and W can have two values, strong or weak. What is I(T;W) = H(T) - H(T|W)

Answer 12

calculate H(T), the entropy of T

calculate H(T|W=strong), the entropy of T where W is strong
calculate H(T|W=weak), the entropy of T where W is week

weighted average of H(T|W=strong) and H(T|W=weak),

Question 13

we get the maximum possible information gain when….

Answer 13

H(T|W)=0

Question 14

the maximum possible value of the entropy of T, H(T) = ?

Answer 14

log(|T|)

Question 15

what is pruning?

Answer 15

truncating a decision tree to prevent overfitting

Question 16

what is prepruning?

Answer 16

stop the decision tree from growing too large

Question 17

how can we create pre-pruning rules that were based on some knowledge about the training data set?

Answer 17

calculate the usefulness of each decision tree split at the point of computing the split- information gain

Question 18

what are the benefits of pre-pruning (2)?

Answer 18

reduce the likelihood of overfitting

reduce the overall training time

Question 19

what is the risk of prepruning?

Answer 19

it is possible for a decision to have low information gain but for child branches to have high information gain

Question 20

what is post-pruning?

Answer 20

deliberately allow the tree to overfit to the training data by allowing ID3 to run until all the training data are perfectly classified.

Then examine the performance on validation data

systematically remove branches to improve the validation accuracy until it matches the training accuracy.

Question 21

Two plausible leaf nodes (or base cases) for the id3 decision tree algorithm are:

Answer 21

When all labels are equal, or the minimum number of examples has been reached

Question 22

In the ID3 algorithm, we choose to split based on

Answer 22

mutual information (Information gain)

Question 23

what is pop in a decision tree leaf

Answer 23

the number of training points that arrived at that node

Question 24

what is err of a leaf

Answer 24

the fraction of the examples arriving at that node that are incorrectly classified

Question 25

how do we know the number of rules in a tree

Answer 25

count the number of possible paths.

Question 26

Describe the distribution of a random variable where we will get the lowest entropy

Answer 26

The lowest entropy is calculated for a random variable that has a single event with a probability of 1.0, a certainty.

Question 27

Describe the distribution of a random variable where we will get the highest entropy

Answer 27

The largest entropy for a random variable will be if all events are equally likely.