Climbing trees 1: what are decision trees?

Summary

This is the first in a se­ries of posts about de­ci­sion trees in the con­text of ma­chine learn­ing. The goal here is to pro­vide a foun­da­tional un­der­stand­ing of de­ci­sion trees and to im­ple­ment them. Climb­ing trees se­ries De­ci­sion trees are not amaz­ing al­go­rithms by them­selves. They have lim­i­ta­tions that can re­sult in sub­op­ti­mal and even weird pre­dic­tions. And yet, they have be­come ex­tremely pop­u­lar. Some would even say they are the de facto go-to al­go­rithm for many ma­chine learn­ing do­mains. This is due to bag­ging and boost­ing, tech­niques that turned sub­par de­ci­sion trees into state-​of-​the-​art al­go­rithms. We’ll ex­plore them in the fu­ture. First, we’ll build an in­tu­ition for what are de­ci­sion trees and de­fine them math­e­mat­i­cally. Then, we’ll ex­plore how de­ci­sion trees are built. This will allow us to grasp their main char­ac­ter­is­tics, ad­van­tages and dis­ad­van­tages. I will try to in­tro­duce com­plex­ity grad­u­ally, but I will as­sume you have some knowl­edge on math­e­mat­i­cal no­ta­tion, sta­tis­tics and basic ma­chine learn­ing con­cepts. If things be­come too com­pli­cated, try to read the pro­vided ref­er­ences. I’ve drawn upon var­i­ous sources in­stru­men­tal to my un­der­stand­ing of de­ci­sion trees, in­clud­ing books, doc­u­men­ta­tion, ar­ti­cles, blog posts and lec­tures. Even if you un­der­stand every­thing, check the ref­er­ences: there is great con­tent there. What is a de­ci­sion tree? Imag­ine you’re try­ing to de­cide whether to take an um­brella when leav­ing home. You might ask ques­tions like: “Are there clouds?”. If yes, you might then ask “What’s the hu­mid­ity level?”. Each ques­tion helps you nar­row down the de­ci­sion. This is how a de­ci­sion tree works. Let’s sim­u­late this weather ex­am­ple: A de­ci­sion tree can be thought of as mak­ing con­sec­u­tive de­ci­sions by ask­ing a se­ries of ques­tions about our data. Each in­ter­nal tree node uses a cer­tain fea­ture (in ...