Learning a tree that classifies the training data perfectly may not lead to the tree with the best generalization performance.

- There may be noise in the training data

- May be based on insufficient data

A hypothesis h is said to overfit the training data if there is another hypothesis, h', such that h has smaller error than h' on the training data but h has larger error on the test data than h'.

Lack of data points makes it difficult to predict correctly the class labels of that region.

Overfitting results in decision trees that are more complex than necessary.

Training error no longer provides a good estimate of how well the tree will perform on previously unseen records.

How can we avoid overfitting a decision tree?

- Prepruning : Stop growing when data split not statistically significant

- Postpruning : Grow full tree then remove nodes

Methods for evaluating subtrees to prune:

- Minimum description length (MDL):

Minimum: size(tree) + size(misclassifications(tree))

- Cross-validation

Evaluate splits before installing them :

- Don't install splits that don't look worthwhile

- When no worthwhile splits to install, done

Typical stopping condition for a node:

- Stop if all instances belong to the same class

- Stop if all the attribute values are the same

More restrictive conditions:

- Stop if number of instance is less than some user-specified threshold

- Stop if class distribution of instance are independent of the available features (e.g., using 𝓍2 test)

- Stop if expanding the current node does not improve impurity measures (e.g., Gini or information gain).

A post-pruning, cross validation approach

- Partition training data into "grow" set and "validation" set.

- Build a complete tree for the "grow" data

- Until accuracy on validation set decreases, do:

For each non-leaf node in the tree

Temporarily prune the tree below; replace it by majority vote

Test the accuracy of the hypothesis on the validation set

Permanently prune the node with the greatest increase in accuracy on the validation test.

Problem: Uses less data to construct the tree

Sometimes done at the rules level

Learning is an ill-posed problem; data is not sufficient to find a unique solution

The need for inductive bias, assumptions about H

Generalization: How well a model performs on new data

Overfitting: H more complex than C or ƒ

Undderfitting: H less complex than C or ƒ

There is a trade-off between three factors:

- Complexity of H, c (H),

- Training set size, N,

- Generalization error, E on new data

As N increases-, E decreases

As c (H) increases-, first E decreases and then E-increases

As c (H)- increases, the training error decreases for some time and then stays constant (frequently at 0)

Overfitting happens when a model is capturing idiosyncrasies of the data rather than generalities.

- Often caused by too many parameters relative to the amount of training data.

- E.g. an order-N polynomial can intersect any N+1 data points

Use more data

Use a tuning set

Regularization

Be a Bayesian

In a linear regression model overfitting is characterized by large weights.

Introduce a penalty term in the loss function.

- There may be noise in the training data

- May be based on insufficient data

A hypothesis h is said to overfit the training data if there is another hypothesis, h', such that h has smaller error than h' on the training data but h has larger error on the test data than h'.

**Underfitting and Overfitting (Example)****Underfitting :**When model is too simple, both training and test errors are large.**Overfitting due to Insufficient Examples**Lack of data points makes it difficult to predict correctly the class labels of that region.

Overfitting results in decision trees that are more complex than necessary.

Training error no longer provides a good estimate of how well the tree will perform on previously unseen records.

**Avoid Overfitting**How can we avoid overfitting a decision tree?

- Prepruning : Stop growing when data split not statistically significant

- Postpruning : Grow full tree then remove nodes

Methods for evaluating subtrees to prune:

- Minimum description length (MDL):

Minimum: size(tree) + size(misclassifications(tree))

- Cross-validation

**Pre-Pruning (Early stopping)**Evaluate splits before installing them :

- Don't install splits that don't look worthwhile

- When no worthwhile splits to install, done

Typical stopping condition for a node:

- Stop if all instances belong to the same class

- Stop if all the attribute values are the same

More restrictive conditions:

- Stop if number of instance is less than some user-specified threshold

- Stop if class distribution of instance are independent of the available features (e.g., using 𝓍2 test)

- Stop if expanding the current node does not improve impurity measures (e.g., Gini or information gain).

**Reduced-error Pruning**A post-pruning, cross validation approach

- Partition training data into "grow" set and "validation" set.

- Build a complete tree for the "grow" data

- Until accuracy on validation set decreases, do:

For each non-leaf node in the tree

Temporarily prune the tree below; replace it by majority vote

Test the accuracy of the hypothesis on the validation set

Permanently prune the node with the greatest increase in accuracy on the validation test.

Problem: Uses less data to construct the tree

Sometimes done at the rules level

**Model Selection & Generalization**Learning is an ill-posed problem; data is not sufficient to find a unique solution

The need for inductive bias, assumptions about H

Generalization: How well a model performs on new data

Overfitting: H more complex than C or ƒ

Undderfitting: H less complex than C or ƒ

**Triple Trade-Off**There is a trade-off between three factors:

- Complexity of H, c (H),

- Training set size, N,

- Generalization error, E on new data

As N increases-, E decreases

As c (H) increases-, first E decreases and then E-increases

As c (H)- increases, the training error decreases for some time and then stays constant (frequently at 0)

Overfitting happens when a model is capturing idiosyncrasies of the data rather than generalities.

- Often caused by too many parameters relative to the amount of training data.

- E.g. an order-N polynomial can intersect any N+1 data points

**Dealing with Overfitting**Use more data

Use a tuning set

Regularization

Be a Bayesian

**Regularization**In a linear regression model overfitting is characterized by large weights.

**Penalize large weights in Linear Regression**Introduce a penalty term in the loss function.

## No comments:

## Post a Comment