Decision Trees and Random Forest

Question 1

Motivation for Decision Trees

Answer 1

• goal of classifier: give accurate prediction; its sufficient to know that a test point is in an area where all neighbors are of a particular class, exact identities are irrelevant
• Decision Trees:
  
  • build tree structure that recursively divides space into regions with similar labels
  • very fast inference
  • no metric needed
• bad ML algorithms but bias variance problems can be adressed by
  
  • variance: bagging
  • bias: boosting

Question 2

Decision Trees

Answer 2

• which node on top?
  
  • gini impurity, total gini impurity (weighted average of gini impurities)
  • choose lowest as root
• do the same for the next leaves
  
  • only include node if gini impurity gets better
• numeric
  
  • sort lowest to highest
  • calc average between adjacent rows
  • calc gini impurities of different averages
  • take lowest

Question 3

Random Forest

Answer 3

• Bootstraped data set (randomly select samples till size of original ds)
• build decision tree from that (only select a subset of dims randomly)
• repeat
• classify an example: run through all trees, choose which label is assigned the most often
• Test RF
  
  • 1/3 of data does not appear in dataset becaust of bootstraping
  • out of bag data set
  • run to test RF - ‘out of bag error’

Question 4

Bagging

Answer 4

Bootstrap aggregating

Question 5

Random Forest Algorithm

Answer 5

Question 6

Random Forest

Differences to Individual Tree

Answer 6

Question 7

Boosting

Answer 7

• draw sample of observations from data (with replacement)
• oberservations are not sampled randomly, higher weight observations are more likely choosen
• wheight each training example by how incorrectly it was classified