\documentclass[ignorenonframetext,]{beamer}
\setbeamertemplate{caption}[numbered]
\setbeamertemplate{caption label separator}{: }
\setbeamercolor{caption name}{fg=normal text.fg}
\beamertemplatenavigationsymbolsempty
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
  \else
    \usepackage{fontspec}
  \fi
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\newif\ifbibliography
\hypersetup{
            pdftitle={Module 5: RESAMPLING},
            pdfauthor={Mette Langaas, Department of Mathematical Sciences, NTNU},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\usepackage{framed}
\definecolor{shadecolor}{RGB}{248,248,248}
\newenvironment{Shaded}{\begin{snugshade}}{\end{snugshade}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.13,0.29,0.53}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.13,0.29,0.53}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.00,0.00,0.81}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.00,0.00,0.81}{#1}}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.00,0.00,0.81}{#1}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textit{#1}}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.13,0.29,0.53}{\textbf{#1}}}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.81,0.36,0.00}{\textbf{#1}}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textit{#1}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.77,0.63,0.00}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{0.94,0.16,0.16}{#1}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{0.64,0.00,0.00}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\usepackage{graphicx,grffile}
\makeatletter
\def\maxwidth{\ifdim\Gin@nat@width>\linewidth\linewidth\else\Gin@nat@width\fi}
\def\maxheight{\ifdim\Gin@nat@height>\textheight0.8\textheight\else\Gin@nat@height\fi}
\makeatother
% Scale images if necessary, so that they will not overflow the page
% margins by default, and it is still possible to overwrite the defaults
% using explicit options in \includegraphics[width, height, ...]{}
\setkeys{Gin}{width=\maxwidth,height=\maxheight,keepaspectratio}

% Prevent slide breaks in the middle of a paragraph:
\widowpenalties 1 10000
\raggedbottom

\AtBeginPart{
  \let\insertpartnumber\relax
  \let\partname\relax
  \frame{\partpage}
}
\AtBeginSection{
  \ifbibliography
  \else
    \let\insertsectionnumber\relax
    \let\sectionname\relax
    \frame{\sectionpage}
  \fi
}
\AtBeginSubsection{
  \let\insertsubsectionnumber\relax
  \let\subsectionname\relax
  \frame{\subsectionpage}
}

\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}

\title{Module 5: RESAMPLING}
\subtitle{TMA4268 Statistical Learning V2018}
\author{Mette Langaas, Department of Mathematical Sciences, NTNU}
\date{week 7 2018 (Version 11.02.2018)}

\begin{document}
\frame{\titlepage}

\begin{frame}

\begin{block}{Learning material for this module:}

\begin{itemize}
\tightlist
\item
  James et al (2013): An Introduction to Statistical Learning. Chapter
  5.\\
\item
  \href{https://www.math.ntnu.no/emner/TMA4268/2018v/notes/TMA4268ClassnotesM5.pdf}{Classnotes
  12.02.2018}
\end{itemize}

\end{block}

\begin{block}{Move to:}

\begin{itemize}
\tightlist
\item
  \protect\hyperlink{intro}{Introduction}
\item
  \protect\hyperlink{cv}{Cross-validation} and
  \protect\hyperlink{recexcv}{Recommended exercises on cross-validation}
\item
  \protect\hyperlink{boot}{Bootstrapping} and
  \protect\hyperlink{recexboot}{Recommended exercises on bootstrapping}
\item
  \protect\hyperlink{summing}{Summing up}
\item
  \protect\hyperlink{further}{Further reading}
\item
  \protect\hyperlink{Rpackages}{Packages to install before knitting this
  R Markdown file}
\end{itemize}

\end{block}

\end{frame}

\begin{frame}{ Introduction}

\begin{block}{What will you learn?}

\begin{itemize}
\tightlist
\item
  What is model assessment and model selection?
\item
  Ideal solution in a data rich situation.
\item
  Validation set - LOOCV and \(k\)-fold CV - what is the best?
\item
  Bootstrapping - how and why.
\item
  Summing up
\item
  The plan for the interactive lesson on Wednesday/Friday.
\end{itemize}

\end{block}

\end{frame}

\begin{frame}{Focus: Generalization performance of learning method}

\begin{itemize}
\tightlist
\item
  prediction capacity on independent test data
\item
  inference and understanding
\end{itemize}

This is important both for

\begin{block}{Model selection:}

estimate the \emph{performance} of different models (often different
order of complexity within one model class) to \emph{choose the best
model}.

\end{block}

\begin{block}{Model assessment:}

having chosen a final model, estimating its performance (prediction
error) on new data.

\end{block}

\end{frame}

\begin{frame}

\begin{block}{Example from ComplsoryEx 1- Problem 1}

We aim to do \emph{model selection} in KNN-regression, where true curve
is \(f(x)=-x+x^2+x^3\) with \(x \in [-3,3]\). \(n=61\) for the training
data.

\begin{figure}
\centering
\includegraphics{Prob1f1.png}
\caption{Regression problem: training data and true regression curve}
\end{figure}

\end{block}

\end{frame}

\begin{frame}

\begin{block}{KNN-regression}

\(n=61\) both for training and for test data (using same x-grid).
\includegraphics{Prob1f3.png}

\(K\) small: high complexity (left) and \(K\) large: low complexity
(right).

\end{block}

\end{frame}

\begin{frame}{The bias-variance trade-off}

\begin{figure}
\centering
\includegraphics{Prob1f4.png}
\caption{Regression problem: bias-variance traceoff}
\end{figure}

Left (high complexity): low squared-bias (red) and high variance
(green). Right (low complexity): high squared-bias (red) and low
variance (green).

\end{frame}

\begin{frame}

\begin{block}{Loss functions - reminder - we will use}

\begin{itemize}
\item
  Mean squared error (quadratic loss) for regression problems:
  \[Y_i=f({\bf x}_i)+\varepsilon_i \text{ for }i=1,\ldots,n \text{ and } \text{MSE}=\frac{1}{n}\sum_{i=1}^n (y_i-\hat{f}({\bf x}_i))^2\]
\item
  0/1 loss for classification problems:
  \[P(Y=j\mid {\bf x}_0) \text{ for }j=1,\ldots,K \text{ and } \frac{1}{n}\sum_{i=1}^n \text{I}(y_i \neq \hat{y}_i)\]
\end{itemize}

\end{block}

\begin{block}{The challenge}

our example was based on simulated data, so I had unlimited access to
data. Now, let us move to real data!

\end{block}

\end{frame}

\begin{frame}{Data rich situation}

If we had a large amount of data we could divide our data into three
parts:

\begin{itemize}
\tightlist
\item
  training set: to fit the model
\item
  validation set: to select the best model (aka model selection)
\item
  test set: to assess how well the model fits on new independent data
  (aka model assessment)
\end{itemize}

\textbf{Q} Why not enough with training and test?

\end{frame}

\begin{frame}

If this is the case - great - then you do not need Module 5. But, this
is very seldom the case - so we will study other solutions based on
efficient cample resue with \emph{resampling} data.

An alternative strategy for model selection (using methods penalizing
model complexity) is covered in Module 6.

First we look at \emph{crossvalidation}, then at \emph{bootstrapping}.

\end{frame}

\begin{frame}{Cross-validation (CV)}

\begin{itemize}
\tightlist
\item
  the validation set approach
\item
  leave one out cross validation (LOOCV)
\item
  5 and 10 fold crossvalidation (CV)
\item
  selection bias - all elements of a model selection strategy need to be
  within the CV-loop
\item
  recommended exercises
\end{itemize}

\end{frame}

\begin{frame}{The validation set approach}

Consider the case when you have a data set consisting of \(n\)
observations.

To fit a model and to test its predictive performance you randomly
divide the data set into two parts (\(n/2\) sample size each):

\begin{itemize}
\tightlist
\item
  a \emph{training set} (to fit the model) and
\item
  a \emph{validation set} (to make predictions of the response variable
  for the observations in the validation set)
\end{itemize}

First: focus on model selection

\end{frame}

\begin{frame}[fragile]

\begin{block}{Regression model selection example: validation set error}

Auto data set (library \texttt{ISLR}): predict \texttt{mpg} (miles pr
gallon) using polynomial function of \texttt{horsepower} (of engine),
\(n=392\).

\includegraphics{5Resample_files/figure-beamer/unnamed-chunk-1-1.pdf}

\end{block}

\end{frame}

\begin{frame}

\begin{block}{Regression example: validation set error for many random
divisions}

\includegraphics{5Resample_files/figure-beamer/unnamed-chunk-2-1.pdf}

\end{block}

\end{frame}

\begin{frame}

\begin{block}{Drawbacks with the validation set approach}

\begin{itemize}
\tightlist
\item
  high variability of validation set error (which we think of as
  estimate for test set error) - since this is dependent on which
  observation are included in the training and validation set
\item
  smaller sample size for model fit - since not all observations can be
  in the training set
\item
  the validation set error may tend to overestimate the test set error
  for a model that is fit on the full data set (because - the more data
  the lower error, and here our training set is half of our data set).
\end{itemize}

\end{block}

\end{frame}

\begin{frame}{Leave-one-out cross-validation (LOOCV)}

\begin{itemize}
\tightlist
\item
  If the data is very limited and the division of the data into two
  parts is unreasonable, leave-one-out cross-validation (LOOCV) can be
  used.
\item
  In LOOCV one observation at a time is left out and makes up the test
  set.
\item
  The remaining \(n-1\) observations make up the training set.
\item
  The procedure of model fitting is repeated \(n\) times, such that each
  of the \(n\) observations is left out once.
\item
  The total prediction error is the mean across these \(n\) models.
\end{itemize}

\[\text{MSE}_i=(y_i-\hat{y}_i)^2\]

\[CV_{n}=\frac{1}{n}\sum_{i=1}^n \text{MSE}_i\]

\end{frame}

\begin{frame}

\begin{block}{Regression example: LOOCV}

\includegraphics{5Resample_files/figure-beamer/unnamed-chunk-3-1.pdf}

\end{block}

\end{frame}

\begin{frame}[fragile]

\tiny

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{library}\NormalTok{(ISLR)}
\KeywordTok{library}\NormalTok{(boot)}
\KeywordTok{library}\NormalTok{(ggplot2)}
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{123}\NormalTok{)}
\NormalTok{n=}\KeywordTok{dim}\NormalTok{(Auto)[}\DecValTok{1}\NormalTok{]}
\NormalTok{testMSEvec=}\OtherTok{NULL}
\NormalTok{start=}\KeywordTok{Sys.time}\NormalTok{()}
\ControlFlowTok{for}\NormalTok{ (polydeg }\ControlFlowTok{in} \DecValTok{1}\OperatorTok{:}\DecValTok{10}\NormalTok{)}
\NormalTok{  \{}
\NormalTok{    glm.fit=}\KeywordTok{glm}\NormalTok{(mpg}\OperatorTok{~}\KeywordTok{poly}\NormalTok{(horsepower,polydeg),}\DataTypeTok{data=}\NormalTok{Auto)}
\NormalTok{    glm.cv1=}\KeywordTok{cv.glm}\NormalTok{(Auto, glm.fit,}\DataTypeTok{K=}\NormalTok{n)}
\NormalTok{    testMSEvec=}\KeywordTok{c}\NormalTok{(testMSEvec,glm.cv1}\OperatorTok{$}\NormalTok{delta[}\DecValTok{1}\NormalTok{])}
\NormalTok{\}}
\NormalTok{stopp=}\KeywordTok{Sys.time}\NormalTok{()}
\NormalTok{yrange=}\KeywordTok{c}\NormalTok{(}\DecValTok{15}\NormalTok{,}\DecValTok{28}\NormalTok{)}
\NormalTok{plotdf=}\KeywordTok{data.frame}\NormalTok{(}\StringTok{"testMSE"}\NormalTok{=testMSEvec,}\StringTok{"degree"}\NormalTok{=}\DecValTok{1}\OperatorTok{:}\DecValTok{10}\NormalTok{)}
\NormalTok{g0=}\KeywordTok{ggplot}\NormalTok{(plotdf,}\KeywordTok{aes}\NormalTok{(}\DataTypeTok{x=}\NormalTok{degree,}\DataTypeTok{y=}\NormalTok{testMSE))}\OperatorTok{+}\KeywordTok{geom_line}\NormalTok{()}\OperatorTok{+}\KeywordTok{geom_point}\NormalTok{()}\OperatorTok{+}\KeywordTok{scale_y_continuous}\NormalTok{(}\DataTypeTok{limits =}\NormalTok{ yrange)}\OperatorTok{+}\KeywordTok{scale_x_continuous}\NormalTok{(}\DataTypeTok{breaks=}\DecValTok{1}\OperatorTok{:}\DecValTok{10}\NormalTok{)}\OperatorTok{+}\KeywordTok{labs}\NormalTok{(}\DataTypeTok{y=}\StringTok{"LOOCV"}\NormalTok{)}
\NormalTok{g0}
\end{Highlighting}
\end{Shaded}

\normalsize

\end{frame}

\begin{frame}

\begin{block}{Issues with leave-one-out cross-validation}

\begin{itemize}
\tightlist
\item
  Good:

  \begin{itemize}
  \tightlist
  \item
    no randomness in training/validation splits!
  \item
    little bias since nearly the whole data set used for training
    (compared to half for validation set approach)
  \end{itemize}
\item
  Bad:

  \begin{itemize}
  \tightlist
  \item
    expensive to implement - need to fit \(n\) different models -
    however nice formula for linear model LOOCV - but not genereally so
  \item
    high variance since: two training sets only differ by one
    observation - which makes estimates from each fold are highly
    correlated and this can lead to that their average can have high
    variance.
  \end{itemize}
\end{itemize}

\[\text{Var}(\sum_{i=1}^na_iX_i+b)=\sum_{i=1}^n\sum_{j=1}^n a_ia_j\text{Cov}(X_i,X_j)\]
\[=\sum_{i=1}^na_i^2\text{Var}(X_i)+2\sum_{i=2}^n \sum_{j=1}^{i-1}
a_ia_j\text{Cov}(X_i,X_j).\]

\end{block}

\end{frame}

\begin{frame}

\begin{block}{LOOCV for multiple linear regression}

\[ CV_{n}=\frac{1}{n}\sum_{i=1}^n \left( \frac{y_i-\hat{y}_i}{1-h_{ii}} \right) ^2\]

where \(h_i\) is the \(i\)th diagonal element (leverage) of the hat
matrix \(({\bf X}^T{\bf X})^{-1}{\bf X}^T{\bf Y}\).

\end{block}

\end{frame}

\begin{frame}{\(k\)-fold cross-validation}

\end{frame}

\begin{frame}

\begin{block}{Formally}

\begin{itemize}
\tightlist
\item
  Indices of observations - divided into \(k\) folds:
  \(C_1, C_2, \ldots, C_k\).
\item
  \(n_k\) elements in each fold, if \(n\) is a multiple of \(k\) then
  \(n_k=n/k\).
\end{itemize}

\[\text{MSE}_k=\frac{1}{n_k}\sum_{i\in C_k}(y_i-\hat{y}_i)^2\] where
\(\hat{y}_i\) is the fit for observation \(i\) obtained from the data
with part \(k\) removed.

\[CV_{k}=\frac{1}{n} \sum_{i=j}^k n_k \text{MSE}_k\]

Observe: setting \(k=n\) gives LOOCV.

\end{block}

\end{frame}

\begin{frame}

\begin{block}{Regression example: \(5\) and \(10\)-fold
cross-validation}

\includegraphics{5Resample_files/figure-beamer/unnamed-chunk-5-1.pdf}

\end{block}

\end{frame}

\begin{frame}[fragile]

\tiny

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{library}\NormalTok{(ISLR)}
\KeywordTok{library}\NormalTok{(boot)}
\KeywordTok{library}\NormalTok{(ggplot2)}
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{123}\NormalTok{)}
\NormalTok{n=}\KeywordTok{dim}\NormalTok{(Auto)[}\DecValTok{1}\NormalTok{]}
\NormalTok{testMSEvec5=}\OtherTok{NULL}
\NormalTok{testMSEvec10=}\OtherTok{NULL}
\NormalTok{start=}\KeywordTok{Sys.time}\NormalTok{()}
\ControlFlowTok{for}\NormalTok{ (polydeg }\ControlFlowTok{in} \DecValTok{1}\OperatorTok{:}\DecValTok{10}\NormalTok{)}
\NormalTok{  \{}
\NormalTok{    glm.fit=}\KeywordTok{glm}\NormalTok{(mpg}\OperatorTok{~}\KeywordTok{poly}\NormalTok{(horsepower,polydeg),}\DataTypeTok{data=}\NormalTok{Auto)}
\NormalTok{    glm.cv5=}\KeywordTok{cv.glm}\NormalTok{(Auto, glm.fit,}\DataTypeTok{K=}\DecValTok{5}\NormalTok{)}
\NormalTok{    glm.cv10=}\KeywordTok{cv.glm}\NormalTok{(Auto, glm.fit,}\DataTypeTok{K=}\DecValTok{10}\NormalTok{)}
\NormalTok{    testMSEvec5=}\KeywordTok{c}\NormalTok{(testMSEvec5,glm.cv5}\OperatorTok{$}\NormalTok{delta[}\DecValTok{1}\NormalTok{])}
\NormalTok{    testMSEvec10=}\KeywordTok{c}\NormalTok{(testMSEvec10,glm.cv10}\OperatorTok{$}\NormalTok{delta[}\DecValTok{1}\NormalTok{])}
\NormalTok{\}}
\NormalTok{stopp=}\KeywordTok{Sys.time}\NormalTok{()}
\NormalTok{yrange=}\KeywordTok{c}\NormalTok{(}\DecValTok{15}\NormalTok{,}\DecValTok{28}\NormalTok{)}
\NormalTok{plotdf=}\KeywordTok{data.frame}\NormalTok{(}\StringTok{"testMSE5"}\NormalTok{=testMSEvec5,}\StringTok{"degree"}\NormalTok{=}\DecValTok{1}\OperatorTok{:}\DecValTok{10}\NormalTok{)}
\NormalTok{g0=}\KeywordTok{ggplot}\NormalTok{(plotdf,}\KeywordTok{aes}\NormalTok{(}\DataTypeTok{x=}\NormalTok{degree,}\DataTypeTok{y=}\NormalTok{testMSE5))}\OperatorTok{+}\KeywordTok{geom_line}\NormalTok{()}\OperatorTok{+}\KeywordTok{geom_point}\NormalTok{()}\OperatorTok{+}\KeywordTok{scale_y_continuous}\NormalTok{(}\DataTypeTok{limits =}\NormalTok{ yrange)}\OperatorTok{+}\KeywordTok{scale_x_continuous}\NormalTok{(}\DataTypeTok{breaks=}\DecValTok{1}\OperatorTok{:}\DecValTok{10}\NormalTok{)}\OperatorTok{+}\KeywordTok{labs}\NormalTok{(}\DataTypeTok{y=}\StringTok{"CV"}\NormalTok{)}\OperatorTok{+}\KeywordTok{ggtitle}\NormalTok{(}\StringTok{"5 and 10 fold CV"}\NormalTok{)}
\NormalTok{g0}\OperatorTok{+}\KeywordTok{geom_line}\NormalTok{(}\KeywordTok{aes}\NormalTok{(}\DataTypeTok{y=}\NormalTok{testMSEvec10),}\DataTypeTok{colour=}\StringTok{"red"}\NormalTok{)}\OperatorTok{+}\KeywordTok{geom_point}\NormalTok{(}\KeywordTok{aes}\NormalTok{(}\DataTypeTok{y=}\NormalTok{testMSEvec10),}\DataTypeTok{colour=}\StringTok{"red"}\NormalTok{)}\OperatorTok{+}\KeywordTok{ggtitle}\NormalTok{(}\StringTok{"5 fold (black), 10 fold (red)"}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\normalsize

\end{frame}

\begin{frame}

\includegraphics{5Resample_files/figure-beamer/unnamed-chunk-7-1.pdf}

\end{frame}

\begin{frame}

\begin{block}{Issues with \(k\)-fold cross-validation}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
  As for the validation set, the result may vary according to how the
  folds are made, but the variation is in general lower than for the
  validation set approach.
\item
  The training set is (k-1)/k of the original data set - this will
  estimated of prediction error that are biased upwards.
\item
  This bias is the smalles when \(k=n\) (LOOCV), but we know that LOOCV
  has high variance.
\item
  This is way often \(k=5\) or \(k=10\) is used as a compromise between
  2 and 3.
\end{enumerate}

\end{block}

\end{frame}

\begin{frame}{\(k\)-fold cross-validation in classification}

\begin{itemize}
\tightlist
\item
  what do we need to change from our regression set-up?
\end{itemize}

\end{frame}

\begin{frame}{The right and the wrong way to do cross-validation}

\href{https://lagunita.stanford.edu/c4x/HumanitiesScience/StatLearning/asset/cv_boot.pdf}{ISL
book slides, page 17}: model assessment.

\begin{itemize}
\tightlist
\item
  We have a two-class problem and would like to use a simple
  classification method, however,
\item
  we have many possible predictors \(p=5000\) and not so big sample size
  \(n=50\).
\end{itemize}

We use this strategy to produce a classifier:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
  We calculate the correlation between the class label and each of the
  \(p\) predictors, and choose the \(d=25\) predictors that have the
  highest (absolute value) correlation with the class label. (We need to
  have \(d<n\) to fit the logistic regression uniquely.)
\item
  Then we fit our classifier (here: logistic regression) using only the
  \(d=25\) predictors.
\end{enumerate}

How can we use cross-validation to produce an estimate of the
performance of this classifier?

\textbf{Q}: Can we apply cross-validation only to step 2? Why or why
not?

\end{frame}

\begin{frame}

Can we apply cross-validation only to step 2?

\textbf{A:} No, step 1 is part of the training procedure (the class
labels are used) and must be part of the CV to give an honest estimate
of the performance of the classifier.

\begin{itemize}
\tightlist
\item
  Wrong: Apply cross-validation in step 2.
\item
  Right: Apply cross-validation to steps 1 and 2.
\end{itemize}

We will see in the Recommended Exercises that doing the wrong thing can
give a misclassification error approximately 0 - even if the ``true''
rate is 50\%.

\end{frame}

\begin{frame}

\begin{block}{Selection bias in gene extraction on the basis of
microarray gene-expression data}

Article by \href{http://www.pnas.org/content/99/10/6562}{Christophe
Ambroise and Geoffrey J. McLachlan, PNAS 2002}: Direct quotation from
the abstract of the article follows.

\begin{itemize}
\tightlist
\item
  In the context of cancer diagnosis and treatment, we consider the
  problem of constructing an accurate prediction rule on the basis of a
  relatively small number of tumor tissue samples of known type
  containing the expression data on very many (possibly thousands)
  genes.
\item
  Recently, results have been presented in the literature suggesting
  that it is possible to construct a prediction rule from only a few
  genes such that it has a negligible prediction error rate.
\item
  However, in these results the test error or the leave-one-out
  cross-validated error is calculated without allowance for the
  selection bias.
\end{itemize}

\end{block}

\end{frame}

\begin{frame}

\begin{itemize}
\tightlist
\item
  There is no allowance because the rule is either tested on tissue
  samples that were used in the first instance to select the genes being
  used in the rule or because the cross-validation of the rule is not
  external to the selection process; that is, gene selection is not
  performed in training the rule at each stage of the crossvalidation
  process.
\item
  We describe how in practice the selection bias can be assessed and
  corrected for by either performing a crossvalidation or applying the
  bootstrap external to the selection process.
\item
  We recommend using 10-fold rather than leave-one-out cross-validation,
  and concerning the bootstrap, we suggest using the so-called .632
  bootstrap error estimate designed to handle overfitted prediction
  rules.
\item
  Using two published data sets, we demonstrate that when correction is
  made for the selection bias, the cross-validated error is no longer
  zero for a subset of only a few genes.
\end{itemize}

\end{frame}

\begin{frame}{ Recommended exercises on cross-validation}

\textbf{Problem 1}: Explain how \(k\)-fold cross-validation is
implemented + draw a figure, + specify algorithmically what is done, +
and in particular how the ``results'' from each fold are aggregated, +
relate to one example from regression (maybe is complexity wrt
polynomials of increasing degree in multiple linear regression or \(K\)
in KNN-regression?) + relate to one example from classification (maybe
is complexity wrt polynomials of increasing degree in logistic
regression or \(K\) in KNN-classification?)

Hint: the words ``loss function'', ``fold'', ``training'',
``validation'' are central.

\end{frame}

\begin{frame}

\textbf{Problem 2}: What are the advantages and disadvantages of
\(k\)-fold cross-validation relative to + the validation set approach +
leave one out cross-validation (LOOCV) + what are recommended values for
\(k\), and why?

Hint: the words ``bias'', ``variance'' and ``computational complexity''
should be included.

\end{frame}

\begin{frame}

\textbf{Problem 3:}. Selection bias and the ``wrong way to do CV''.

The task here is to devise an algorithm to ``prove'' that the wrong way
is wrong and that the right way is right.

\begin{enumerate}
\def\labelenumi{\alph{enumi}.}
\tightlist
\item
  What are the steps of such an algorithm? Write down a suggestion.
  Hint: how do you generate data for predictors and class labels, how do
  you do the classification task, where is the CV in the correct way and
  wrong way inserted into your algorithm? Can you make a schematic
  drawing of the right and the wrong way? Hint:
  \href{https://lagunita.stanford.edu/c4x/HumanitiesScience/StatLearning/asset/cv_boot.pdf}{ISL
  book slides, page 20+21} - but you can do better?
\end{enumerate}

\end{frame}

\begin{frame}[fragile]

\begin{enumerate}
\def\labelenumi{\alph{enumi}.}
\setcounter{enumi}{1}
\tightlist
\item
  One possible version of this is presented in the R-code below. Go
  through the code and explain what is done in each step, then run the
  code and observe if the results are in agreement with what you
  expected. Make changes to the R-code if you want to test out different
  strategies.
\end{enumerate}

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{library}\NormalTok{(boot)}
\CommentTok{# GENERATE DATA}
\CommentTok{# reproducible}
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{4268}\NormalTok{)}
\NormalTok{n=}\DecValTok{50} \CommentTok{#number of observations}
\NormalTok{p=}\DecValTok{5000} \CommentTok{#number of predictors}
\NormalTok{d=}\DecValTok{25} \CommentTok{#top correlated predictors chosen}
\NormalTok{kfold=}\DecValTok{10}
\CommentTok{#generating predictor data}
\NormalTok{xs=}\KeywordTok{matrix}\NormalTok{(}\KeywordTok{rnorm}\NormalTok{(n}\OperatorTok{*}\NormalTok{p,}\DecValTok{0}\NormalTok{,}\DecValTok{4}\NormalTok{),}\DataTypeTok{ncol=}\NormalTok{p,}\DataTypeTok{nrow=}\NormalTok{n) }\CommentTok{#simple way to to uncorrelated predictors}
\KeywordTok{dim}\NormalTok{(xs) }\CommentTok{# n times p}
\CommentTok{# generate class labels independent of predictors - so if all classifies as class 1 we expect 50% errors in general}
\NormalTok{ys=}\KeywordTok{c}\NormalTok{(}\KeywordTok{rep}\NormalTok{(}\DecValTok{0}\NormalTok{,n}\OperatorTok{/}\DecValTok{2}\NormalTok{),}\KeywordTok{rep}\NormalTok{(}\DecValTok{1}\NormalTok{,n}\OperatorTok{/}\DecValTok{2}\NormalTok{)) }\CommentTok{#now really 50% of each}
\KeywordTok{table}\NormalTok{(ys)}

\CommentTok{# WRONG CV - using cv.glm}
\CommentTok{# here select the most correlated predictors outside the CV}
\NormalTok{corrs=}\KeywordTok{apply}\NormalTok{(xs,}\DecValTok{2}\NormalTok{,cor,}\DataTypeTok{y=}\NormalTok{ys)}
\KeywordTok{hist}\NormalTok{(corrs)}
\NormalTok{selected=}\KeywordTok{order}\NormalTok{(corrs}\OperatorTok{^}\DecValTok{2}\NormalTok{,}\DataTypeTok{decreasing =} \OtherTok{TRUE}\NormalTok{)[}\DecValTok{1}\OperatorTok{:}\NormalTok{d] }\CommentTok{#top d correlated selected}
\NormalTok{data=}\KeywordTok{data.frame}\NormalTok{(ys,xs[,selected])}
\CommentTok{#apply(xs[,selected],2,cor,y=ys) yes, ave the most correlated}
\CommentTok{# then cv around the fitting of the classifier - use logistic regression and built in cv.glm function}
\NormalTok{logfit=}\KeywordTok{glm}\NormalTok{(ys}\OperatorTok{~}\NormalTok{.,}\DataTypeTok{family=}\StringTok{"binomial"}\NormalTok{,}\DataTypeTok{data=}\NormalTok{data)}
\NormalTok{cost <-}\StringTok{ }\ControlFlowTok{function}\NormalTok{(r, }\DataTypeTok{pi =} \DecValTok{0}\NormalTok{) }\KeywordTok{mean}\NormalTok{(}\KeywordTok{abs}\NormalTok{(r}\OperatorTok{-}\NormalTok{pi) }\OperatorTok{>}\StringTok{ }\FloatTok{0.5}\NormalTok{)}
\NormalTok{cvres=}\KeywordTok{cv.glm}\NormalTok{(}\DataTypeTok{data=}\NormalTok{data,}\DataTypeTok{cost=}\NormalTok{cost,}\DataTypeTok{glmfit=}\NormalTok{logfit,}\DataTypeTok{K=}\NormalTok{kfold)}
\NormalTok{cvres}\OperatorTok{$}\NormalTok{delta}
\CommentTok{# observe - near 0 misclassification rate}

\CommentTok{# WRONG without using cv.glm - should be similar (just added to see the similarity to the RIGHT version)}
\NormalTok{reorder=}\KeywordTok{sample}\NormalTok{(}\DecValTok{1}\OperatorTok{:}\NormalTok{n,}\DataTypeTok{replace=}\OtherTok{FALSE}\NormalTok{)}
\NormalTok{validclass=}\OtherTok{NULL}
\ControlFlowTok{for}\NormalTok{ (i }\ControlFlowTok{in} \DecValTok{1}\OperatorTok{:}\NormalTok{kfold)}
\NormalTok{\{}
\NormalTok{  neach=n}\OperatorTok{/}\NormalTok{kfold}
\NormalTok{  trainids=}\KeywordTok{setdiff}\NormalTok{(}\DecValTok{1}\OperatorTok{:}\NormalTok{n,(((i}\OperatorTok{-}\DecValTok{1}\NormalTok{)}\OperatorTok{*}\NormalTok{neach}\OperatorTok{+}\DecValTok{1}\NormalTok{)}\OperatorTok{:}\NormalTok{(i}\OperatorTok{*}\NormalTok{neach)))}
\NormalTok{  traindata=}\KeywordTok{data.frame}\NormalTok{(xs[reorder[trainids],],ys[reorder[trainids]])}
\NormalTok{  validdata=}\KeywordTok{data.frame}\NormalTok{(xs[reorder[}\OperatorTok{-}\NormalTok{trainids],],ys[reorder[}\OperatorTok{-}\NormalTok{trainids]])}
  \KeywordTok{colnames}\NormalTok{(traindata)=}\KeywordTok{colnames}\NormalTok{(validdata)=}\KeywordTok{c}\NormalTok{(}\KeywordTok{paste}\NormalTok{(}\StringTok{"X"}\NormalTok{,}\DecValTok{1}\OperatorTok{:}\NormalTok{p),}\StringTok{"y"}\NormalTok{)}
\NormalTok{  data=traindata[,}\KeywordTok{c}\NormalTok{(selected,p}\OperatorTok{+}\DecValTok{1}\NormalTok{)]}
\NormalTok{  trainlogfit=}\KeywordTok{glm}\NormalTok{(y}\OperatorTok{~}\NormalTok{.,}\DataTypeTok{family=}\StringTok{"binomial"}\NormalTok{,}\DataTypeTok{data=}\NormalTok{data)}
\NormalTok{  pred=}\KeywordTok{plogis}\NormalTok{(}\KeywordTok{predict.glm}\NormalTok{(trainlogfit,}\DataTypeTok{newdata=}\NormalTok{validdata[,selected]))}
  \KeywordTok{print}\NormalTok{(pred)}
\NormalTok{  validclass=}\KeywordTok{c}\NormalTok{(validclass,}\KeywordTok{ifelse}\NormalTok{(pred }\OperatorTok{>}\StringTok{ }\FloatTok{0.5}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{0}\NormalTok{))}
\NormalTok{\}}
\KeywordTok{table}\NormalTok{(ys[reorder],validclass)}
\DecValTok{1}\OperatorTok{-}\KeywordTok{sum}\NormalTok{(}\KeywordTok{diag}\NormalTok{(}\KeywordTok{table}\NormalTok{(ys[reorder],validclass)))}\OperatorTok{/}\NormalTok{n}

\CommentTok{# CORRECT CV}
\NormalTok{reorder=}\KeywordTok{sample}\NormalTok{(}\DecValTok{1}\OperatorTok{:}\NormalTok{n,}\DataTypeTok{replace=}\OtherTok{FALSE}\NormalTok{)}
\NormalTok{validclass=}\OtherTok{NULL}
\ControlFlowTok{for}\NormalTok{ (i }\ControlFlowTok{in} \DecValTok{1}\OperatorTok{:}\NormalTok{kfold)}
\NormalTok{\{}
\NormalTok{  neach=n}\OperatorTok{/}\NormalTok{kfold}
\NormalTok{  trainids=}\KeywordTok{setdiff}\NormalTok{(}\DecValTok{1}\OperatorTok{:}\NormalTok{n,(((i}\OperatorTok{-}\DecValTok{1}\NormalTok{)}\OperatorTok{*}\NormalTok{neach}\OperatorTok{+}\DecValTok{1}\NormalTok{)}\OperatorTok{:}\NormalTok{(i}\OperatorTok{*}\NormalTok{neach)))}
\NormalTok{  traindata=}\KeywordTok{data.frame}\NormalTok{(xs[reorder[trainids],],ys[reorder[trainids]])}
\NormalTok{  validdata=}\KeywordTok{data.frame}\NormalTok{(xs[reorder[}\OperatorTok{-}\NormalTok{trainids],],ys[reorder[}\OperatorTok{-}\NormalTok{trainids]])}
  \KeywordTok{colnames}\NormalTok{(traindata)=}\KeywordTok{colnames}\NormalTok{(validdata)=}\KeywordTok{c}\NormalTok{(}\KeywordTok{paste}\NormalTok{(}\StringTok{"X"}\NormalTok{,}\DecValTok{1}\OperatorTok{:}\NormalTok{p),}\StringTok{"y"}\NormalTok{)}
\NormalTok{  foldcorrs=}\StringTok{ }\KeywordTok{apply}\NormalTok{(traindata[,}\DecValTok{1}\OperatorTok{:}\NormalTok{p],}\DecValTok{2}\NormalTok{,cor,}\DataTypeTok{y=}\NormalTok{traindata[,p}\OperatorTok{+}\DecValTok{1}\NormalTok{]) }
\NormalTok{  selected=}\KeywordTok{order}\NormalTok{(foldcorrs}\OperatorTok{^}\DecValTok{2}\NormalTok{,}\DataTypeTok{decreasing =} \OtherTok{TRUE}\NormalTok{)[}\DecValTok{1}\OperatorTok{:}\NormalTok{d] }\CommentTok{#top d correlated selected}
\NormalTok{  data=traindata[,}\KeywordTok{c}\NormalTok{(selected,p}\OperatorTok{+}\DecValTok{1}\NormalTok{)]}
\NormalTok{  trainlogfit=}\KeywordTok{glm}\NormalTok{(y}\OperatorTok{~}\NormalTok{.,}\DataTypeTok{family=}\StringTok{"binomial"}\NormalTok{,}\DataTypeTok{data=}\NormalTok{data)}
\NormalTok{  pred=}\KeywordTok{plogis}\NormalTok{(}\KeywordTok{predict.glm}\NormalTok{(trainlogfit,}\DataTypeTok{newdata=}\NormalTok{validdata[,selected]))}
\NormalTok{  validclass=}\KeywordTok{c}\NormalTok{(validclass,}\KeywordTok{ifelse}\NormalTok{(pred }\OperatorTok{>}\StringTok{ }\FloatTok{0.5}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{0}\NormalTok{))}
\NormalTok{\}}
\KeywordTok{table}\NormalTok{(ys[reorder],validclass)}
\DecValTok{1}\OperatorTok{-}\KeywordTok{sum}\NormalTok{(}\KeywordTok{diag}\NormalTok{(}\KeywordTok{table}\NormalTok{(ys[reorder],validclass)))}\OperatorTok{/}\NormalTok{n}
\end{Highlighting}
\end{Shaded}

\end{frame}

\begin{frame}

\textbf{Problem 4}: Trying out different versions of cross-validation
with R. We will use a simulated data set (so that in the end the truth
can be reviled and you can see how well you have done). To see
differences we will look at a large data set and a small data set (in
the number of observations), and focus on regression and on
classification.

\end{frame}

\begin{frame}{The Bootstrap}

\begin{itemize}
\tightlist
\item
  flexible and powerful statistical tool that can be used to quantify
  \emph{uncertainty} associated with an estimator or statistical
  learning method
\item
  we will look at getting an estimate for the standard error of a sample
  median and of a regression coefficient
\item
  in Module 8 - bootstrapping is the core of the \emph{ensemble method}
  referred to at \emph{bagging}=bootstrap aggregation,
\item
  in TMA4300 Computation statistics - more on the bootstrap.
\end{itemize}

\end{frame}

\begin{frame}

The inventor: Bradley Efron in 1979 -
\href{https://www.youtube.com/watch?v=6l9V1sINzhE}{see interview}.

The name? \emph{To pull oneself up by one's bootstraps} from ``The
Surprising Adventures of Baron Munchausen'' by Rudolph Erich Raspe:

\emph{The Baron had fallen to the bottom of a deep lake. Just when it
looked like all was lost, he thought to pick himself up by his own
bootstraps.}

\textbf{Idea: Use the data itself to get more information about a
statistic (an estimator).}

\end{frame}

\begin{frame}

\begin{block}{Example: the standard deviation of the sample median?}

Assume that we observe a random sample \(X_1, X_2, \ldots, X_n\) from an
unknown probability distribution \(F\). We are interesting in saying
something about the population median, and to do that we calculate the
sample median \(\tilde{X}\). But, how accurate is \(\tilde{X}\) as an
estimator?

The bootstrap was introduced as a computer-based method to estimate the
standard deviation of an estimator, for example our estimator
\(\tilde{X}\).

But, before we look at the bootstrap method, first we assume that we
know \(F\) and can sample from \(F\), and use simulations to answer our
question.

\end{block}

\end{frame}

\begin{frame}[fragile]

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{123}\NormalTok{)}
\NormalTok{n=}\DecValTok{101}
\NormalTok{B=}\DecValTok{1000}
\NormalTok{estimator=}\KeywordTok{rep}\NormalTok{(}\OtherTok{NA}\NormalTok{,B)}
\ControlFlowTok{for}\NormalTok{ (b }\ControlFlowTok{in} \DecValTok{1}\OperatorTok{:}\NormalTok{B)}
\NormalTok{\{}
\NormalTok{  xs=}\KeywordTok{rnorm}\NormalTok{(n)}
\NormalTok{  estimator[b]=}\KeywordTok{median}\NormalTok{(xs)}
\NormalTok{\}}
\KeywordTok{sd}\NormalTok{(estimator)}
\CommentTok{# approximation for large samples }
\CommentTok{# (sd of median of standard normal)}
\FloatTok{1.253}\OperatorTok{*}\DecValTok{1}\OperatorTok{/}\KeywordTok{sqrt}\NormalTok{(n)}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
## [1] 0.1259035
## [1] 0.1246782
\end{verbatim}

\end{frame}

\begin{frame}[fragile]

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{ggplot}\NormalTok{(}\DataTypeTok{data=}\KeywordTok{data.frame}\NormalTok{(}\DataTypeTok{x=}\NormalTok{estimator),}\KeywordTok{aes}\NormalTok{(}\DataTypeTok{x=}\NormalTok{x))}\OperatorTok{+}
\StringTok{  }\KeywordTok{geom_density}\NormalTok{()}
\end{Highlighting}
\end{Shaded}

\includegraphics{5Resample_files/figure-beamer/unnamed-chunk-10-1.pdf}

\end{frame}

\begin{frame}

\begin{block}{Moving from simulation to bootstrapping}

The bootstrap method is using the observed data to estimate the
\emph{empirical distribution} \(\hat{F}\), that is each observed value
of \(x\) is given probability \(1/n\).

A \emph{bootstrap sample} \(X^*_1,X^*_2,\ldots, X^*_n\) is a random
sample drawn from \(\hat{F}\).

A simple way to obtain the bootstrap sample is to \emph{draw with
replacement from \(X_1, X_2, \ldots, X_n\)}.

This means that our bootstrap sample consists of \(n\) members of
\(X_1, X_2, \ldots, X_n\) - some appearing 0 times, some 1, some 2, etc.

\end{block}

\end{frame}

\begin{frame}[fragile]

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{123}\NormalTok{)}
\NormalTok{n=}\DecValTok{101}
\NormalTok{original=}\KeywordTok{rnorm}\NormalTok{(n)}
\KeywordTok{median}\NormalTok{(original)}
\NormalTok{boot1=}\KeywordTok{sample}\NormalTok{(}\DataTypeTok{x=}\NormalTok{original,}\DataTypeTok{size=}\NormalTok{n,}\DataTypeTok{replace=}\OtherTok{TRUE}\NormalTok{)}
\KeywordTok{table}\NormalTok{(}\KeywordTok{table}\NormalTok{(boot1))}
\NormalTok{n}\OperatorTok{-}\KeywordTok{sum}\NormalTok{(}\KeywordTok{table}\NormalTok{(}\KeywordTok{table}\NormalTok{(boot1)))}
\KeywordTok{median}\NormalTok{(boot1)}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
## [1] 0.05300423
## 
##  1  2  3  4  5 
## 42 16  6  1  1 
## [1] 35
## [1] -0.1388914
\end{verbatim}

\end{frame}

\begin{frame}

\begin{block}{The bootstrap algorithm for estimating standard errors}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  \(B\) bootstrap samples:
\item
  Evaluate statistic:
\item
  Estimate standard error by:
\end{enumerate}

\end{block}

\end{frame}

\begin{frame}[fragile]

\begin{block}{with for-loop in R}

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{123}\NormalTok{)}
\NormalTok{n=}\DecValTok{101}
\NormalTok{original=}\KeywordTok{rnorm}\NormalTok{(n)}
\KeywordTok{median}\NormalTok{(original)}
\NormalTok{B=}\DecValTok{1000}
\NormalTok{estimator=}\KeywordTok{rep}\NormalTok{(}\OtherTok{NA}\NormalTok{,B)}
\ControlFlowTok{for}\NormalTok{ (b }\ControlFlowTok{in} \DecValTok{1}\OperatorTok{:}\NormalTok{B)}
\NormalTok{  \{}
\NormalTok{  thisboot=}\KeywordTok{sample}\NormalTok{(}\DataTypeTok{x=}\NormalTok{original,}\DataTypeTok{size=}\NormalTok{n,}\DataTypeTok{replace=}\OtherTok{TRUE}\NormalTok{)}
\NormalTok{  estimator[b]=}\KeywordTok{median}\NormalTok{(thisboot)}
\NormalTok{\}}
\KeywordTok{sd}\NormalTok{(estimator)}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
## [1] 0.05300423
## [1] 0.1365856
\end{verbatim}

\end{block}

\end{frame}

\begin{frame}[fragile]

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{ggplot}\NormalTok{(}\DataTypeTok{data=}\KeywordTok{data.frame}\NormalTok{(}\DataTypeTok{x=}\NormalTok{estimator),}\KeywordTok{aes}\NormalTok{(}\DataTypeTok{x=}\NormalTok{x))}\OperatorTok{+}
\StringTok{  }\KeywordTok{geom_density}\NormalTok{()}
\end{Highlighting}
\end{Shaded}

\includegraphics{5Resample_files/figure-beamer/unnamed-chunk-13-1.pdf}

\end{frame}

\begin{frame}[fragile]

\begin{block}{using built in \texttt{boot} function from library
\texttt{boot}}

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{library}\NormalTok{(boot)}
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{123}\NormalTok{)}
\NormalTok{n=}\DecValTok{101}
\NormalTok{original=}\KeywordTok{rnorm}\NormalTok{(n)}
\KeywordTok{median}\NormalTok{(original)}
\KeywordTok{summary}\NormalTok{(original)}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
## [1] 0.05300423
##     Min.  1st Qu.   Median     Mean  3rd Qu.     Max. 
## -2.30917 -0.50232  0.05300  0.08248  0.68864  2.18733
\end{verbatim}

\end{block}

\end{frame}

\begin{frame}[fragile]

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{boot.median=}\ControlFlowTok{function}\NormalTok{(data,index) }\KeywordTok{return}\NormalTok{(}\KeywordTok{median}\NormalTok{(data[index]))}
\NormalTok{B=}\DecValTok{1000}
\KeywordTok{boot}\NormalTok{(original,boot.median,}\DataTypeTok{R=}\NormalTok{B)}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
## 
## ORDINARY NONPARAMETRIC BOOTSTRAP
## 
## 
## Call:
## boot(data = original, statistic = boot.median, R = B)
## 
## 
## Bootstrap Statistics :
##       original      bias    std. error
## t1* 0.05300423 -0.01413291    0.136591
\end{verbatim}

\end{frame}

\begin{frame}

\begin{block}{With or without replacement?}

In bootstrapping we sample \emph{with replacement} from our
observations.

What if we instead sample \emph{without replacement}?

\end{block}

\end{frame}

\begin{frame}

\begin{block}{Example: multiple linear regression}

We assume, for observation \(i\):
\[Y_i= \beta_0 + \beta_{1}  x_{i1} + \beta_2 x_{i2} + ... + \beta_p x_{ip} + \varepsilon_i,\]
where \(i=1,2,...,n\). The model can be written in matrix form:
\[{\bf Y}={\bf X} \boldsymbol{\beta}+{\boldsymbol{\varepsilon}}.\]

The least squares estimator:
\(\hat{\boldsymbol\beta}=({\bf X}^T{\bf X})^{-1} {\bf X}^T {\bf Y}\) has
\(\text{Cov}(\boldsymbol\beta)=\sigma^2({\bf X}^T{\bf X})^{-1}\).

We will in the recommended exercises look at how to use bootstrapping to
estimate the covariance of the estimator. Why is that ``needed'' if we
already know the mathematical formula for the standard deviation?

We will not do this here - but our bootstrap samples can also be used to
make confidence intervals for the regression coefficients or prediction
intervals for new observations. This means that we do not have to rely
on assuming that the error terms are normally distributed!

\end{block}

\end{frame}

\begin{frame}{Bagging}

Bagging is a special case of \emph{ensemble methods}.

In Module 8 we will look at bagging, which is built on bootstrapping the
the fact that it is possible to reduce the variance of a prediction by
taking the average of many model fits.

\begin{itemize}
\tightlist
\item
  Assume that we have \(B\) different predictors
  \(X_1, X_2, \ldots, X_B\). We have built them on \(B\) different
  bootstrap samples.
\item
  All are predictors for some parameter \(\mu\) and that all have some
  unknown variance \(\sigma^2\).
\item
  We then decide that we want to use all the predictors together -
  equally weighted - and make \(\bar{X}=\frac{1}{n} \sum_{i=1}^n X_i\),
  which we often use to predict \(\mu\).
\end{itemize}

\end{frame}

\begin{frame}

We can therefore obtain a new model (our average of the individual
models) that has a smaller variance than each of the individual model
because

\[\text{Var}(\bar{X})=\frac{\sigma^2}{n}\]

Since this averaged predictor has smaller variance than each of the
predictors we would assum that this is a more accurate prediction.
However, the interpretation of this bagged prediction might be harder
then for the separate predictors.

Models that have poor prediction ability (as we may see can happen with
regression and classification trees) might benefit greatly from bagging.
More in Module 8.

\end{frame}

\begin{frame}{ Recommended exercises on bootstrapping}

\textbf{Problem 1}: We will calculate the probability that a given
observation in our original sample is part of a bootstrap sample. This
is useful for us to know in Module 8.

Our sample size is \(n\).

\begin{enumerate}
\def\labelenumi{\alph{enumi}.}
\tightlist
\item
  We draw one observation from our sample. What is the probability of
  drawing observation \(x_i\)? And of not drawing observation \(x_i\)?
\item
  We make \(n\) independent drawing (with replacement). What is the
  probability of not drawing observation \(x_i\) in any of the \(n\)
  drawings? What is then the probability that \(x_i\) is in our
  bootstrap sample (that is, more than 0 times)?
\item
  When \(n\) is large \((1-\frac{1}{n})^n=\frac{1}{\exp(1)}\). Use this
  to give a numerical value for the probability that a specific
  observation \(x_i\) is in our bootstrap sample.
\item
  Write a short R code chunk to check your result. (Hint: An example on
  how to this is on page 198 in our ISLR book.)
\end{enumerate}

\end{frame}

\begin{frame}[fragile]

\textbf{Problem 2}: Explain with words and an algorithm how you would
proceed to use bootstrapping to estimate the standard deviation of one
of the regression parameters in multiple linear regression. Comment on
which assumptions you make for your regression model.

\textbf{Problem 3}: Implement your algorithm from 2 both using for-loop
and using the \texttt{boot} function. Hint: see page 195 of our ISLR
book. Use our SLID data set and provide standard errors for the
coefficient for age. Compare with the theoretical value
\(({\bf X}^T{\bf X})^{-1}\hat{\sigma}^2\) that you find in the output
from the regression model.

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{library}\NormalTok{(car)}
\KeywordTok{library}\NormalTok{(boot)}
\NormalTok{SLID =}\StringTok{ }\KeywordTok{na.omit}\NormalTok{(SLID)}
\NormalTok{n =}\StringTok{ }\KeywordTok{dim}\NormalTok{(SLID)[}\DecValTok{1}\NormalTok{]}
\NormalTok{SLID.lm =}\StringTok{ }\KeywordTok{glm}\NormalTok{(wages}\OperatorTok{~}\NormalTok{., }\DataTypeTok{data =}\NormalTok{ SLID)}
\KeywordTok{summary}\NormalTok{(SLID.lm)}\OperatorTok{$}\NormalTok{coeff[}\DecValTok{3}\NormalTok{,}\DecValTok{2}\NormalTok{]}
\end{Highlighting}
\end{Shaded}

\end{frame}

\begin{frame}{Summing up}

\end{frame}

\begin{frame}{Plan for interactive lecture (Wednesday 10.15-12.00 and
Friday 12.15-14.00)}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Enter - participate in interactive lecture IL (with lecturer) or
  supervision of CompEx1 (TAs). If supervision only - allocated table -
  or participate in IL and take breaks to ask for supervision of
  CompEx1.
\item
  If IL - answer: name+study programme+year+``I found CompEx1 ok or
  difficult'' Then groups are formed (by lecuturer) as homogeneous as
  possible (so, not random).
\item
  10.15/12.15: Presentation round in groups: name+study
  programme+year+previous background in statistics+level of expertise in
  R+favorite hobby!
\item
  10.20/12.20: Introduction to problems on cross-validation - work with
  problems 1-3 (4): \protect\hyperlink{recexcv}{Recommended exercises on
  cross-validation}
\item
  10.50/12.50: Summing up problems 1-2 (3) by lecturer.
\item
  11.00/13.00: Break - with fruits.
\end{enumerate}

\end{frame}

\begin{frame}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\setcounter{enumi}{6}
\tightlist
\item
  Maybe new groups, maybe not (we evaluate if some of the groups do not
  work well). If changes, need new presentation round.
\item
  11.15/13.15: Introduction to problems on bootstrapping - work with
  problems 1-3: \protect\hyperlink{recexboot}{Recommended exercises on
  bootstrapping}
\item
  11.40/13.40: Summing up problems 1-2 (3) by lecturer.
\item
  11.45/13.45: Team Kahoot! (in ghostmode on Friday - to beat the
  Wednesday people).
\item
  12.00/14.00: The end:-)
\end{enumerate}

\end{frame}

\begin{frame}{ Further reading }

\begin{itemize}
\tightlist
\item
  \href{https://www.youtube.com/playlist?list=PL5-da3qGB5IA6E6ZNXu7dp89_uv8yocmf}{Videoes
  on YouTube by the authors of ISL, Chapter 5}, and corresponding
  \href{https://lagunita.stanford.edu/c4x/HumanitiesScience/StatLearning/asset/cv_boot.pdf}{slides}
\end{itemize}

\end{frame}

\begin{frame}[fragile]{ R packages to install before knitting this R
Markdown file}

\footnotesize

\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{# packages to install before knitting this R Markdown file}
\CommentTok{# to knit the Rmd}
\KeywordTok{install.packages}\NormalTok{(}\StringTok{"knitr"}\NormalTok{)}
\KeywordTok{install.packages}\NormalTok{(}\StringTok{"rmarkdown"}\NormalTok{)}
\CommentTok{# cool layout for the Rmd}
\KeywordTok{install.packages}\NormalTok{(}\StringTok{"prettydoc"}\NormalTok{) }\CommentTok{# alternative to github}
\CommentTok{#plotting}
\KeywordTok{install.packages}\NormalTok{(}\StringTok{"ggplot2"}\NormalTok{) }\CommentTok{# cool plotting}
\KeywordTok{install.packages}\NormalTok{(}\StringTok{"ggpubr"}\NormalTok{) }\CommentTok{# for many ggplots}
\CommentTok{#datasets}
\KeywordTok{install.packages}\NormalTok{(}\StringTok{"ElemStatLearn"}\NormalTok{) }
\KeywordTok{install.packages}\NormalTok{(}\StringTok{"ISLR"}\NormalTok{)}
\CommentTok{# cross-validation and bootstrapping}
\KeywordTok{install.packages}\NormalTok{(}\StringTok{"boot"}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\end{frame}

\end{document}
