CSE 519: Data Science

Steven Skiena

Stony Brook University

Lecture 21: Decision Trees and Boosting

The Machine Learning Zoo

The variety of clever machine learning algorithms makes it easy to lose sight of why?

Evaluation dimensions include:

• Power and expressibility
• Interpretability
• Ease of Use
• Training speed
• Prediction speed

Subjective Rankings

I asked knowledgeable people to compare these ML methods by these dimensions:

Take Home Lessons

• Linear/logistic regression is pretty good, except in expressibility.
• No single method dominates all the others.
• The comparative advantages of most methods are relatively murky.

The no free lunch theorem states that no single method works best in all cases.

XOR and Linear Classifiers

Linear classifiers cannot be used to fit simple non-linear functions like eXclusive OR.

More powerful methods are needed, including:

• Decision trees
• Nearest neighbor methods
• Support vector machines

XOR and Decision Trees

Decision Tree Classifiers

Each row/instance travels a unique root-to-leaf path to classification.

The tree partitions the training examples into groups of relatively uniform composition, where the decision becomes easy.

Reducing each training example to its own leaf node implies over training.

​

Class Logic-Based Explanations? (Projects)

• Miss Universe?
• Movie gross?
• Baby weight?
• Art auction price?
• Snow on Christmas?
• Super Bowl / College Champion?
• Ghoul Pool?
• Future Gold / Oil Price?

​

Advantages of Decision Trees

• Non-linearity
• Support for categorical variables (hair=red)
• Interpretability -- people can read the tree
• Robustness -- we can construct ensembles of different trees and vote (CART)
• Applicability to regression within leaf subset

Biggest disadvantage is lack of elegance/Math.

Constructing Decision Trees

Trees are constructed in a top-down manner.

Seek a split along one feature/dimension to purify the information over m classes.

• Pure splits create nodes of one single class
• Balanced splits partition the items into equal-sized groups.

Thus tradeoffs between speed and robustness.

Information-Theoretic Entropy

Entropy measures the amount of class confusion:

​

• Complete disorder means f_i= 1/m, so H(S)=log(m).
• Perfect order means f_1=1 and f_2=0, so H(S)=0.

Split Criteria

The value of a potential split S is how much it reduces the entropy of the system:

• Information gain

​

• Gini impurity

Look Ahead and Decision Trees

Finding the best XOR tree requires look ahead, as it cannot be found by greedy:

Optimal Decision Trees

Finding the minimum height decision tree is NP-complete.

The greedy heuristic approximates the minimum height decision tree to a log(n)-factor.

Stopping Criteria

Building a tree until each leaf is pure (f=1) likely ends with singleton elements, and is overfit.

• Better is to stop when the information gain is small, instead of zero.
• An alternate strategy is to build the full tree, then prune way low value nodes.

Decision tree construction is hacking, not science.

​

Comparison with KNN

Decision trees win when:

• Many dimensions, but only a few matter
• Discrete attributes and missing data (new branch)
• Fast at test time, and interpretable

KNN wins when:

• Can handle features that interact (like pixels)
• Typically performs better in practice

Ensembles of Decision Trees

We can construct hundreds of decision trees by randomly selecting the feature to split on.

• Voting among multiple classifiers increases robustness and let us score our trust level.
• Bagging picks randomly selected subsets of items to train each tree on.

But should all trees get equal votes?

1 Tree vs. 100

Smoother boundary with

Bagged trees.

Voting Classifiers

The natural way to use multiple classifiers gives each a vote, and takes the majority label.

Such aggregation is typically done for random sets of decision trees, or even single features.

But should each classifier get the same vote?

Epicurus’ Principle: ``Keep all theories that are consistent with the data’’. But not equal votes..

​

Weighing Better Classifiers More

​

​

​

​

​

Might weigh by accuracy or linear regression.

But better means getting the hard cases right...

Boosting

Boost weak (but >0.5 accuracy) classifiers in a strong classifier.

To set the weights of the classifier, we will adjust the weights of the training examples.

Easy training examples will be properly classified by most classifiers: we reward classifiers more for getting the hard cases right.

Adaboost in Action

We seek non-linear classifiers using thresholded features as classifiers (e.g x>1)

Initially all points are of equal weight.

Boosting Misclassified Points

The weight of the misclassified points is boosted to make them more important in the next round.

​

​

Normalize total weights to sum to 1.

The weight of the new classifier depends upon how accurate it is:

AdaBoost Algorithm

Final Classifier

This weighted ensemble correctly classifies all points.

Boosting: Pro and Con

Boosting provides a way to take advantage of weak classifiers (small correlation features) in an effective way.

Boosting tries to fit every example, thus it will overfit noisy data. “Hard cases make bad law.”

Gradient boosted decision trees are the most common method in Kaggle competitions.