Decision Trees

Question 1

What is a decision tree?

Answer 1

It is a process of sorting things via a set of parameters and their order

Question 2

What is the idea of Entropy of information?

Answer 2

The information of a message is inversely proportional to the probability of a message

Question 3

What are the 2 equations fo the entropy of information?

Answer 3

Information:

I(x) = -log₂P(x)

H = E[I] = ∑_i - p_ilog₂p_i

Question 4

What is the equation for total entropy?

Answer 4

This is the sum of all the entropies for each class

Question 5

How can the entropy of information be applied to compression algorithms?

Answer 5

When we have 2 classes (binary), the probability of 1 and 0 can be related by the following equation: p₀ + p₁ = 1

Question 6

How do you decide what parameters to use and in what order?

Answer 6

We want the process in which the change in entropy from a parameter is greatest

Question 7

What is the equation for informatin gain?

Answer 7

G(S,F) = H(S) - ∑_{f∈values(F)} |S_f| / |S| × H(S_f)

Question 8

What is the ID3 philosophy?

Answer 8

Chose the method that has the greatest entropy gain

Question 9

What is the ID3 algorithm?

Answer 9

IF: all examples have the same label => return a leaf with that label

ELSE IF: there are no features left to test => return leaf with the most common label

ELSE: Chose the feature F that maximises the informaation gain of S to be the next node. Add a branch of the node for each possible value f in F.

For each branch:

> Calculate Sf by removing F from the set of features

> Recursively call the algorithm with Sf to compute the gain relative to the current set of examples

Question 10

What are the characteristics of the ID3 Algorithm?

Answer 10

> Greedy with respect to G. It always goes for the path with the greatest entropy gain. This can lead to a local minima

> Deals with noisy data by assigning the label to the most common class

> Always uses features so it is prone to overfitting

• Uses pruning
• Uses continueous varaibles - Can deal with missing attributes

Question 11

What is the CART algorithm?

Answer 11

This is the same as the ID3 but instead of using entropy we use the gini impurity

Question 12

What is the equation fo gini impurity?

Answer 12

G(s) = ∑_i^C (p_i(1 - p_i))

Question 13

What is the equation for the gini split?

Answer 13

G(S,F) = G(S) - ∑_{f∈values(F)} |S_f| / |S| × G(S_f)

Question 14

What is the issue with ID3 and Gini?

Answer 14

Both algorithms are greedy so can find a local minima. It is important to produce different decision trees.

Question 15

What is a random forrest?

Answer 15

This is creating 1000s of trees with different subsets. this is called a forrest.

Each tree uses a random fraction of the features and a random fraction of training data points

Question 16

What are the sources of randomness?

Answer 16

> Random subset of features

> Random subset of training points

Question 17

What is the idea of combining trees?

Answer 17

Each tree votes for a class. The random forest classes the majoriity of the trees. This is called an ensable which is when you combine many weak classifiers into 1 strong one.

Question 18

How does ID3 chose what feature to split with?

Answer 18

The features that produces the greatest information gain

Question 19

What type of data can decision trees classify that normal MLPs cannot?

Answer 19

Non Numerical data