Lecture 10: Decision trees and random forests 3

Q: What is learning essential for in AI?

Unknown environments where the designer lacks omniscience.

Q: What are the two main uses of learning in systems?

1. Adapting to unknown environments.
   2. Exposing the agent to reality rather than trying to hand-code every rule.

Q: What does learning modify in an agent?

The decision-making mechanisms to improve performance.

Q: What are the three types of feedback in learning?

• Supervised learning: correct answers given.
• Unsupervised learning: no correct answers given.
• Reinforcement learning: occasional rewards.

Q: What is inductive learning?

Learning a function f from examples (x, f(x)) by finding a hypothesis h such that h ≈ f.

Q: What is Ockham’s razor in learning?

Prefer the simplest hypothesis consistent with the data.

Q: In decision tree learning, what is the goal?

Find a small tree that is consistent with the training examples.

Q: What is an attribute-based representation?

Describing examples using values for different attributes (Boolean, discrete, continuous).

Q: How expressive are decision trees?

They can represent any function of the input attributes.

Q: Why don’t we want giant decision trees that perfectly memorize training data?

They may not generalize to new examples; simpler trees are preferred.

Q: How many distinct decision trees are there with n Boolean attributes?

2^(2ⁿ)
(e.g., with 6 attributes, over 18 quintillion trees!)

Q: How many purely conjunctive hypotheses exist with n attributes?

3^n.

Q: What happens as the hypothesis space gets bigger?

• It’s more likely to contain the target function.
• But it’s also easier to overfit.

Q: What is the main idea when choosing an attribute for a decision tree split?

Pick the attribute that splits the data into subsets that are mostly “pure” (mostly positive or negative).

Q: What formula is used to compute the uncertainty (entropy) of a dataset?

I(P(v₁), ..., P(vₙ)) = -∑ P(vᵢ) log₂ P(vᵢ)

Q: What is Information Gain (IG)?

The reduction in entropy from splitting on an attribute; higher IG is better.

Q: How do you choose the best attribute to split on?

Choose the attribute with the highest information gain.

Q: In the restaurant example, which attribute had the highest Information Gain?

Patrons.

Q: What does a learning curve show?

Prediction accuracy as a function of training set size.

Q: What are two ways to measure if h ≈ f (if your model is good)?

• Try h on a new test set.
• Use computational/statistical learning theory.