<gh_stars>10-100
\input{../../style/preamble}
\newcommand{\titlefigure}{figure/cart_stopprun_2.pdf}
\newcommand{\learninggoals}{
\item Understand which problems arise when growing the tree until the end
\item Know different stopping criteria
\item Understand the idea of pruning}

\title{Introduction to Machine Learning}
% \author{<NAME>, <NAME>, <NAME>, <NAME>}
\institute{\href{https://compstat-lmu.github.io/lecture_i2ml/}{compstat-lmu.github.io/lecture\_i2ml}}
\date{}

\begin{document}
\lecturechapter{CART: Stopping Criteria \& Pruning}
\lecture{Introduction to Machine Learning}
\sloppy

\begin{frame}{Overfitting Trees}

The \textbf{recursive partitioning} procedure used to grow a CART would run until every leaf only contains a single observation. 
\begin{itemize}
\item Problem 1: This would take a very long time, as the amount of splits we have to try \emph{grows exponentially} with the number of leaves in the trees.
\item Problem 2: At some point before that we should stop splitting nodes into ever smaller child nodes: very complex trees with lots of branches and leaves will \emph{overfit the training data.}
\item Problem 3: However, it is very hard to tell where we should stop while we're growing the tree: Before we have actually tried all possible additional splits further down a branch, we can't know whether any one of them will be able to reduce the risk by a lot (\emph{horizon effect}).
\end{itemize}
\end{frame}

\begin{vbframe}{Stopping Criteria}
Problems 1 and 2 can be \enquote{solved} by defining different \textbf{stopping criteria}:
  \begin{itemize}
    \item Stop once the tree has reached a certain number of leaves.
    \item Don't try to split a node further if it contains too few observations.
    \item Don't perform a split that results in child nodes with too few observations.
    \item Don't perform a split unless it achieves a certain minimal improvement of the empirical risk in the child nodes, compared to the empirical risk in the parent node.
    \item Obviously: Stop once all observations in a node have the same target value (\textbf{pure node}) or identical values for all features. 
  \end{itemize}
\end{vbframe}

\begin{vbframe}{Pruning}

We try to solve problem 3 by \textbf{pruning}:

\begin{itemize}
\item A method to select the optimal size of a tree
\item Finding a combination of suitable strict stopping criteria (\enquote{pre-pruning}) is a hard problem: there are many different stopping criteria and it's hard to find the best combination (see chapter on \textbf{tuning})
\item Better: Grow a large tree, then remove branches so that the resulting smaller tree has optimal cross-validation risk
\item Feasible without cross-validation: Grow a large tree, then remove branches so that the resulting smaller tree has a good balance between training set performance (risk) and complexity (i.e., number of terminal nodes). The trade-off between complexity and accuracy is governed by a \textbf{complexity parameter}.
\end{itemize}

\framebreak



\framebreak

\begin{knitrout}\scriptsize
\definecolor{shadecolor}{rgb}{0.969, 0.969, 0.969}\color{fgcolor}

{\centering \includegraphics[width=0.95\textwidth]{figure/cart_stopprun_1} 

}




{\centering \includegraphics[width=0.95\textwidth]{figure/cart_stopprun_2} 

}




{\centering \includegraphics[width=0.95\textwidth]{figure/cart_stopprun_3} 

}




{\centering \includegraphics[width=0.95\textwidth]{figure/cart_stopprun_4} 

}



\end{knitrout}
\end{vbframe}



\endlecture
\end{document}
