Decision Trees

Question 1

What is the ID3 algorithm?

Answer 1

Split (node, {example}):

1. A
2. For each value of A create child node
3. Split training {example}’s to child nodes
4. For each subset Split (child_node, {subset}) until subset is pure

Question 2

What is the definition of Entropy?

Answer 2

H(S) = -p₍₊₎ log₂ p₍₊₎ - p_(-) log₂ p_(-)

Where p₍₊₎ and p₍₊₎ are % positive/negative examples in S

Question 3

How can we interpret entropy?

Answer 3

How many bits needed to tell if X is positive or negative

Question 4

How do we compute the expected drop in entropy (gain)?

Answer 4

Question 5

What does gain tell us?

Answer 5

Average entropy after the split, biased to larger subsets

Question 6

What is infomation gain?

Answer 6

Difference between the entopy before the split and after the split

Question 7

What does infomation gain tell you?

Answer 7

How much more certain you are after a split

Question 8

What happens if you run ID3 to completion?

Answer 8

All subsets will be pure

Question 9

How to Decision trees overfit?

Answer 9

Running ID3 to completion, end up with lots of singleton subsets, not alot of confidence in estimates (only 1 traning example).

Question 10

How can we avoid overfitting (decision trees)?

Answer 10

• Create full DT
• For each node
  
  • Remove
  • Measure performance on validation set
• Remove node that results in greatest improvement
• Repeat until accuracy drops

Question 11

How is split entropy defined?

Answer 11

Question 12

What do we use split entropy for

Answer 12

Normalize infomation gain by how fine grained the split is

Question 13

Definition of gain ratio?

Answer 13

Question 14

What does GainRation penalize?

Answer 14

Attributes with many values

Question 15

What is the problem with infomation gain?

Answer 15

Biased towards attributes with many values (they create lots of small pure subsets)

Question 16

Whats unique about DT?

Answer 16

Not a black box, you can interpet rules of the tree

Question 17

How can we expland DT to multi class?

Answer 17

• Predict most freq class
• Generalize entropy: H(S) = -Σ_c p_(c) log₂ p_(c) where p_(c) is % of class c in S

Question 18

How can we expand DT to regression?

Answer 18

• Predict average of examples in subset (or use linear regression)
• Minimize variance in subsets

Question 19

Whats are the pros of DT?

Answer 19

• Interpretable
• Easly handles irrelevant attributes (gain = 0)
• can handle missing data
• very compact
• very fast testing time: O(depth)

Question 20

What are the cons of DT?

Answer 20

• Only axis-aligned splits of data
• Greedy (may not find best tree
  
  • Exponentially many possible trees

Question 21

How do you create a random decision forest?

Answer 21

• Grow K different decision trees
  
  • Pick a random subset S_r of training examples
  • Grow a full ID3 tree T_r
    
    • Pick from a subset d << D random attributes
    • Compute gain based on S_r
  • Repeat for r = 1…k

Question 22

How do you classify an example with random forrests?

Answer 22

• Classify each X using trees T₁ to T_k
• Use majority vote

Question 23

What does entropy measure?

Answer 23

How pure/inpure a subset is