Chapter 4: Information-based Learning

Question 1

How do you build perceptive machine learning models?

Answer 1

Use the most informative features

Question 2

In this context what is an informative feature?

Answer 2

Descriptive feature whose values split the instances in the dataset into the most homogenous sets with respect to the target feature value

Question 3

How do you calculate the average number of questions you have to ask per game?

Answer 3

Add the number of paths to get to each person and divide by the number of people

Question 4

What do we consider the effects of difference answers in terms of?

Answer 4

• How the domain is split up after the answer is received
• The likelihood of each of the answers

Question 5

What does a decision tree consist of?

Answer 5

• Root node (starting node)
• Interior nodes
• Leaf nodes (terminating nodes)

Question 6

What are some important information about non-leaf nodes and leaf nodes?

Answer 6

• Each non-leaf node specifies a test to be carried out on one of the query’s descriptive features
• Each leaf node contains a class label, it specifies a predicted classification for the query

Question 7

What is the process of using a decision tree to make a prediction for a query instance?

Answer 7

• Start by testing the value of the descriptive feature at the root node of the tree
• The result of the test determines which of the root node’s children the process should descend to
• The two steps of testing the descriptive feature and descending a level are repeated until the process comes to a leaf node at which a prediction can be made

Question 8

What is the preference for decision trees?

Answer 8

Shallower trees

Question 9

How do we make shallow trees?

Answer 9

• Testing the informative features early on in the tree
• We do that with ENTROPY which is a computational metric of the purity of a set

Question 10

What is Shannon’s entropy model?

Answer 10

• It defines a computational measure of the impurity of the elements of a set

Question 11

How is entropy related to the probability of an outcome?

Answer 11

High probability –> Low entropy
Low probability –> High entropy

Question 12

How do we map probability to entropy value?

Answer 12

log functions of the probability multiplied by -1

Question 13

What is Shannon’s entropy model?

Answer 13

• A weighted sum of the logs of the probabilities of each of the possible outcomes when we make a random selection from a set
• It is the cornerstone of modern information theory and is an excellent measure of the impurity (heterogeneity) of a set

Question 14

What are the weights used in the sum?

Answer 14

The weights used in the sum are the probabilities of the outcomes themselves so that outcomes with high probabilities contribute to the overall entropy of a set than outcomes with low probabilities

Question 15

Why is there a minus sign at the beginning of the equation?

Answer 15

It is added to convert negative numbers returned by the log function to positive ones

Question 16

What is the base of our calculation?

Answer 16

We always use base 2 so that entropy is calculated in bits

Question 17

What is the relationship between a measure of heterogeneity of a set and predictive analytics?

Answer 17

If we can construct a sequence of tests that splits the training data into pure sets with respect to the target feature values then we can label queries by applying the same sequence of tests to a query and labeling it with the target feature value of instances in the set it ends up in

Question 18

What is our intuition for information gain?

Answer 18

Our intuition is that the ideal discriminatory feature will partition the data into pure subsets where all the instances in each subset have the same classification

Question 19

What is the information gain of a descriptive feature?

Answer 19

It is a measure of the reduction in the overall entropy of a prediction task by testing on that feature

Question 20

What is the first step of the three step process to computing information gain?

Answer 20

• Compute the entropy of the original dataset with respect to the target feature.
• This gives a measure of how much information is required to organize the data into pure sets

Question 21

What is the second step of the three step process to computing information gain?

Answer 21

• For each descriptive feature, create the sets that result by partitioning the instances in the dataset using their feature values and then sum the entropy scores of each set
• This gives a measure of the information that remain required to organize the instances into pure sets after we have split them using the descriptive feature

Question 22

What is the third step of the three step process to computing information gain?

Answer 22

-Subtract the remaining entropy value (step 2) from the original entropy value (step 1) to give the information gain

Question 23

What does ID3 stand for?

Answer 23

Iterative Dichotomizer 3

Question 24

What does ID3 do?

Answer 24

It attempts to create the shallowest tree that is consistent with the data that is given

Question 25

How does ID3 work?

Answer 25

It builds a tree in a recursive depth-first manner, beginning at the root node and working down to the leaf nodes.

Question 26

What is step 1 of the ID3 algorithm

Answer 26

Start by choosing the best descriptive feature to test using information gain (basically best question to ask first)

Question 27

What is step 2 of the ID3 algorithm

Answer 27

Add the root node to the tree and label it with the selected test feature

Question 28

What is step 3 of the ID3 algorithm

Answer 28

• Partition the training dataset using the test (the chosen attribute value)
• One partition is created for each possible test result which contains the training instances that returned that result

Question 29

What is step 4 of the ID3 algorithm

Answer 29

A branch is grown from the node for each partition

Question 30

What is step 5 of the ID3 algorithm

Answer 30

Repeat the process for each branch using the relevant partition of the training set in place of the full training set and with the selected test feature excluded form further testing

Question 31

What is step 6 of the ID3 algorithm

Answer 31

This process is repeated until all the instances in
a partition have the same target level, at which point a leaf node is created and labeled
with that level.

Question 32

What assumption is ID3 algorithm based on?

Answer 32

A correct decision tree for a domain will classify instances from that domain in the same proportion as the target level occurs in the domain

Question 33

What is the first thing to remember when designing base cases?

Answer 33

• First, the dataset of training instances considered at each of the interior
  nodes in the tree is not the complete dataset, rather it is the subset of instances considered
  at its parent node that had the relevant feature value for the branch from the parent to the
  current node.

Question 34

What is the second thing to remember when designing base cases?

Answer 34

Once a feature has been tested, it is not considered for selection
again along that path in the tree. A feature will only be tested once on any path in the tree,
but it may occur several times in the tree on different paths.

Question 35

What is the first ID3 stopping condition?

Answer 35

• All instances in the dataset have the same classification (target value)
• Return a leaf node with that classification as its label

Question 36

What is the first ID3 stopping condition?

Answer 36

• The set of features left to test is empty
• Return a leaf node tree with the majority class of the dataset as its classification/label

Question 37

What is the third ID3 stopping condition?

Answer 37

• The dataset is empty
• Return a leaf node tree with the majority class of the dataset at the parent node that made the recursive call

Question 38

What is the first step to recursively create interior nodes?

Answer 38

• Decide which descriptive feature should be tested at this node (use information gain)
• This is based on purity and homogeneity of the resulting partition

Question 39

What is the second step to recursively create interior nodes?

Answer 39

After choosing the most informative feature, the algorithm adds a new node the the tree
- It then splits the dataset considered at this node according the levels the new node can take

Question 40

What is the third step to recursively create interior nodes?

Answer 40

Remove the feature of the new node form the set of features to be considered for testing later on

Question 41

What is the fourth step to recursively create interior nodes?

Answer 41

The algorithm grows a branch in the tree for each of the values in the domain of the new node

Question 42

How do you address the issue of preferencing features with many levels?

Answer 42

• Information gain ratio
• Computed by dividing the information gain of a feature by the amount of information used to determine the value of the feature

Question 43

What is another commonly used measure of impurity?

Answer 43

Gini Index

Question 44

What is Gini Index?

Answer 44

It is calculating how often you would misclassify an instance in the dataset if you classifies it based on the distribution of classifications in the dataset

Question 45

How do you calculate information gain using the Gini index?

Answer 45

Replace the entropy measure with the Gini index

Question 46

How do you determine which impurity threshold to use between Gini or entropy?

Answer 46

Try out different impurity metrics and compare the results to see which suits a dataset best

Question 47

What is CART?

Answer 47

• Classification And Regression Tree
• another version of ID3 algorithm which uses Gini Index as replacement for Information Gain

Question 48

What is the easiest way to handle continuous valued descriptive features?

Answer 48

Turn them into Boolean features by defining a threshold and using it to partition the instances based on their value of the continuous descriptive feature

Question 49

How do we set the threshold?

Answer 49

• The instances in the dataset are sorted according to the continuous feature values
• The adjacent instances in the ordering that have different classifications are selected as possible threshold points
• The optimal threshold is found by computing the information gain for each classification boundary and selecting the boundary with the highest information gain as the threshold

Question 50

What happens once the threshold has been set?

Answer 50

• The dynamically created new Boolean feature can compete with the other categorical features for selection as the splitting feature at that node
• The process is repeated at each node as the tree grows