---
title: "Classification \\newline
        \\normalsize chapter 4 of
        \\textit{An Introduction to Statistical Learning} (ISL)"
short-title: "Classification: ISL book chapter"
author: "Henrique Laureano \\newline \\url{http://leg.ufpr.br/~henrique}"
short-author: "leg.ufpr.br/~henrique"
#email: "laureano\\@ufpr.br"
#date: "August 12, 2019"
#short-date:
#department: "Laboratory of Statistics and Geoinformation (LEG)"
#institute: "UFPR/DEST/LEG"
#short-institute: "LEG"
section-titles: true
safe-columns: true # enables special latex macros for columns
output:
  legtheme::beamer_leg
---

### What we read (long description)

\begincols
 \column{.4\linewidth}
  \begin{figure}
   \centering
   \includegraphics[width=.95\textwidth]{book.jpg}
  \end{figure}
 \column{.6\linewidth}
  \begin{figure}
   \centering
   \includegraphics[width=\textwidth]{chap4.png}
  \end{figure}
\endcols

###

\textcolor{beamer@UIUCorange}{Now in a shorter way}

###

\textcolor{beamer@UIUCblue}{What we read (short description)}

\begin{adjustwidth}{2.5em}{0pt}
 At chapter 4 are discussed three of the most widely-used classifiers.
 \begin{itemize}
  \item Logistic Regression
  \item Linear Discriminant Analysis (LDA)
  \item Quadratic Discriminant Analysis (QDA)
 \end{itemize}
\end{adjustwidth}

\textcolor{beamer@UIUCblue}{What we didn't read}

\begin{adjustwidth}{2.5em}{0pt}
More computer-intensive methods are discussed in later chapters, such as
\begin{itemize}
\item Generalized Additive Models (GAM)
\item Trees
\item Random Forests
\item Boosting
\item Support Vector Machines (SVM)
\end{itemize}
\end{adjustwidth}

# Why Not Linear Regression?

###

We could consider encoding the response, \(Y\), as a quantitative
variable, \textcolor{beamer@UIUCblue}{e.g.},

\begin{block}{Predict the medical condition of a patient on the basis of
her symptoms.}
\[
Y = \begin{cases}
  1 & \text{if}~\textcolor{beamer@UIUCblue}{\texttt{stroke}};\\
  2 & \text{if}~\textcolor{beamer@UIUCblue}{\texttt{drug overdose}};\\
  3 & \text{if}~\textcolor{beamer@UIUCblue}{\texttt{epileptic seizure}}.\\
\end{cases}
\]
\end{block}

\pause
\textcolor{beamer@UIUCorange}{Unfortunately, this coding implies an
ordering on the outcomes.}

Each possible coding would produce a
\textcolor{beamer@UIUCblue}{fundamentally different linear model} that
would ultimately lead to \textcolor{beamer@UIUCblue}{different sets of
predictions}.

### This leads us to other questions,

+ What if the response variable values did take on a
  \textcolor{beamer@UIUCblue}{natural ordering}, such as
  \textcolor{beamer@UIUCblue}{\texttt{mild}},
  \textcolor{beamer@UIUCblue}{\texttt{moderate}}, and
  \textcolor{beamer@UIUCblue}{\texttt{severe}}?

+ For a \textcolor{beamer@UIUCblue}{\texttt{binary}} (two level)
  qualitative response, the situation is
  \textcolor{beamer@UIUCblue}{better}.

   - \textcolor{beamer@UIUCblue}{However}, if we use linear regression,
     some of our estimates might be \textcolor{beamer@UIUCblue}{outside}
     the \textcolor{beamer@UIUCblue}{[0, 1] interval}.

   - However, the \textcolor{beamer@UIUCblue}{dummy variable approach}
     cannot be easily extended to accommodate qualitative responses with
     more than two levels.

\pause
\textcolor{beamer@UIUCorange}{For these reasons, it is preferable to use
a classification method that is truly suited for qualitative response
values, such as the ones presented next.}

\begin{block}{Curiously,}
 it turns out that the classifications that we get if we use
 \textcolor{beamer@UIUCblue}{linear regression} to predict a binary
 response will be \textcolor{beamer@UIUCblue}{the same} as for the
 linear discriminant analysis (\textcolor{beamer@UIUCblue}{LDA})
 procedure we discuss later.
\end{block}

# A typical dataset

### A classic 'book example dataset relationship'

\begin{figure}
 \centering
 \includegraphics[width=.8\textwidth]{iBagens/dataset_chap4.png}
\end{figure}

... a very pronounced relationship between
\textcolor{beamer@UIUCorange}{\texttt{balance}} and
\textcolor{beamer@UIUCorange}{\texttt{default}}.

# Logistic Regression

### To start, a comparison with Linear Regression

\begin{figure}
 \centering
 \includegraphics[width=\textwidth]{iBagens/linr-vs-logr.png}
\end{figure}

###

\textcolor{beamer@UIUCorange}{\textit{Logistic regression in two slides}}

## The model framework

### Some math, but with just one predictor

\begin{block}{The model and its relations}
\[
p(X) = \underset{\begin{gathered}
                  \text{\textit{logistic}}\\[-\jot]
                  \text{\textit{function}}\\[-\jot]
                  (\textit{S-shaped})
                 \end{gathered}}{
        \underbrace{\frac{e^{\beta_{0}+\beta_{1}X}}{
         1+e^{\beta_{0}+\beta_{1}X}}}} \Rightarrow
       \underset{\textit{odds}~\in~(0, \infty)}{
        \underbrace{\frac{p(X)}{1-p(X)}}} = e^{\beta_{0}+\beta_{1}X}
       \Rightarrow \underset{\begin{gathered}
                              \text{\textit{log-odds}}\\[-\jot]
                              \text{or}\\[-\jot]
                              \text{\textit{logit}}
                             \end{gathered}}{
                    \underbrace{\log \frac{p(X)}{1-p(X)}}} =
                   \beta_{0}+\beta_{1}X
\]
\end{block}

For example,
\[
p(X) = 0.2~\Rightarrow~\frac{0.2}{1-0.2} = \frac{1}{4}
\quad \textit{ and } \quad
p(X) = 0.9~\Rightarrow~\frac{0.9}{1-0.9} = 9.
\]

## Estimating the Regression Coefficients

### Maximum likelihood

The estimates \(\hat{\beta}_{0}\) and  \(\hat{\beta}_{1}\) are chosen to
\textcolor{beamer@UIUCblue}{maximize} a math equation called a

\begin{block}{\textit{likelihood function}}
 \[
 l(\beta_{0}, \beta_{1}) =
 \prod_{i:y_{i}=1} p(x_{i}) \prod_{i':y_{i'}=0} (1-p(x_{i'})).
 \]
\end{block}

The coefficients \(\hat{\beta}_{0}\) and \(\hat{\beta}_{1}\) are
unknown, and must be estimated. The general method of
\textcolor{beamer@UIUCblue}{maximum likelihood} is preferred, since it
has better statistical properties.

Maximum likelihood is a very general approach that is used to fit many
of the non-linear models examined throughout the book. In the linear
regression setting, the least squares approach is in fact a special case
of maximum likelihood.

# Linear Discriminant Analysis (LDA)

## To start... why do we need something different?

###

\textcolor{beamer@UIUCorange}{Different ideas, sometimes the same results}

###

\textcolor{beamer@UIUCblue}{Different ideas,}

\begin{figure}
 \centering
 \includegraphics[width=\textwidth]{iBagens/logr-vs-lda.jpeg}
\end{figure}

\begin{adjustwidth}{2.5em}{0pt}
 With \textcolor{beamer@UIUCorange}{LDA} we model the distribution of
 the predictors \(X\) separately in each of the response classes (i.e.
 given \(Y\)), and then use Bayes’ theorem to flip these around into
 estimates for \(\mathbb{P}[Y = \textcolor{red}{k} | X =
 \textcolor{red}{x}]\).
\end{adjustwidth}

\pause
\textcolor{beamer@UIUCblue}{Sometimes the same results}

\begin{adjustwidth}{2.5em}{0pt}
 When these distributions are \textcolor{beamer@UIUCorange}{assumed} to
 be \textcolor{beamer@UIUCorange}{normal}, it turns out that the model
 is very similar in form to \textcolor{beamer@UIUCorange}{logistic
 regression}.
\end{adjustwidth}

###

\textcolor{beamer@UIUCorange}{But, ok... why not continue with logistic
regression?}

### But, ok... why not continue with logistic regression?

Simple, \textcolor{beamer@UIUCorange}{LDA} is popular when we have more
than two response classes.

\noindent{\color{beamer@UIUCorange}\rule{\linewidth}{0.25mm}}

Now, a reason more serious: \textcolor{beamer@UIUCblue}{stability}

+ When the classes are well-separated, the parameter estimates for the
  \textcolor{beamer@UIUCorange}{logistic regression} model are
  surprisingly unstable. \textcolor{beamer@UIUCorange}{LDA} does not
  suffer from this problem.

+ If \(n\) is small and the distribution of the predictors \(X\) is
  approximately \textcolor{beamer@UIUCorange}{normal} in each of the
  classes, the \textcolor{beamer@UIUCorange}{linear discriminant} model
  is again more stable than the \textcolor{beamer@UIUCorange}{logistic
  regression} model.

## LDA in a nutshell

### Model framework

\begin{figure}
 \centering
 \includegraphics[width=\textwidth]{iBagens/lda-def.jpeg}
\end{figure}

+ \(\pi_{\textcolor{red}{k}}\) is the overall or
  \textcolor{beamer@UIUCblue}{prior} prob. that a chosen obs. comes from
  \(\textcolor{red}{k}\).

+ In general, estimating \(\pi_{\textcolor{red}{k}}\) is easy if we have
  a sample of \(\textcolor{beamer@UIUCblue}{Y}\)s: we simply compute the
  fraction of observations that belong to the \(\textcolor{red}{k}\)th
  class. However, estimating
  \(f_{\textcolor{red}{k}}(\textcolor{red}{x})\) tends to be more
  challenging, unless we assume some simple forms for these densities.

\textcolor{beamer@UIUCorange}{Remember from Chap. 2} that the
\textcolor{beamer@UIUCblue}{Bayes classifier} has the lowest possible
error rate out of all classifiers.

## Living in a simple and \textit{normal} world

### Dealing with just one predictor

\textcolor{beamer@UIUCorange}{Assumptions}:
\(f_{\textcolor{red}{k}}(\textcolor{red}{x})\) is
\textcolor{beamer@UIUCblue}{normal} with equal variance for the
\(\textcolor{red}{k}\)th classes.

\begin{figure}
\centering
\includegraphics[width=\textwidth]{iBagens/lda1-steps.jpeg}
\end{figure}

Putting a \textcolor{beamer@UIUCblue}{hat} (simple average and a
weighted average of the sample variances for each class) in everything,
the \textcolor{beamer@UIUCorange}{LDA}
\textcolor{beamer@UIUCblue}{approx.} this
\textcolor{beamer@UIUCorange}{Bayes classifier}.

###

Ok, nice! But... \textcolor{beamer@UIUCblue}{why} the name
\textcolor{beamer@UIUCorange}{linear discriminant analysis}?

\begin{adjustwidth}{2.5em}{0pt}
 The word \textcolor{beamer@UIUCorange}{linear} stems from the fact that
 the \textcolor{beamer@UIUCorange}{discriminant functions}
 \(\hat{\delta}_{\textcolor{red}{k}}(x)\) are linear functions of \(x\).

 That is, the \textcolor{beamer@UIUCorange}{LDA} decision rule depends on
 \(x\) only through a \textcolor{beamer@UIUCorange}{linear combination}
 of its elements.
\end{adjustwidth}
\noindent{\color{beamer@UIUCorange}\rule{\linewidth}{0.25mm}}
\pause

\begin{block}

\textcolor{beamer@UIUCorange}{LDA} is trying to
\textcolor{beamer@UIUCblue}{approximate} the
\textcolor{beamer@UIUCorange}{Bayes classifier}, which has the
\textcolor{beamer@UIUCblue}{lowest} total
\textcolor{beamer@UIUCblue}{error rate} out of all classifiers
(\textcolor{beamer@UIUCblue}{if} the Gaussian model is correct).

\end{block}

## Now, with more than one predictor

### Getting bigger

\[
\text{More than one predictor}~\Rightarrow~
\begin{gathered}
  \text{Multivariate normal distribution,}\\[-\jot]
  \text{with a class-specific mean vector}\\[-\jot]
  \text{and a common covariance matrix}
\end{gathered}
\]

\noindent{\color{beamer@UIUCorange}\rule{\linewidth}{0.25mm}}
\pause
\[
f(x) = \frac{1}{(2\pi)^{p/2} |\bm{\Sigma}|^{1/2}}
        \exp\Big\{-\frac{1}{2}(x-\mu_{\textcolor{red}{k}})^{\top}
                              \bm{\Sigma}^{-1}
                              (x-\mu_{\textcolor{red}{k}})
            \Big\}
\]

\[ \text{\LARGE{\(\textcolor{beamer@UIUCblue}{\Rightarrow}\)}} \]

\[
\hat{\delta}_{\textcolor{red}{k}}(x) =
x^{\top} \hat{\bm{\Sigma}}^{-1} \hat{\mu}_{\textcolor{red}{k}} -
\frac{1}{2} \hat{\mu}_{\textcolor{red}{k}}^{\top} \hat{\bm{\Sigma}}^{-1}
            \hat{\mu}_{\textcolor{red}{k}} +
\log \hat{\pi}_{\textcolor{red}{k}}
\]

### An example

\begin{figure}
 \centering
 \includegraphics[width=.85\textwidth]{iBagens/lda-ex.png}
\end{figure}

## Some important details

### Ok, and about what else do we need to talk? (1/2)

\begin{figure}
 \centering
 \includegraphics[width=.95\textwidth]{iBagens/threshold-error_rate.png}
\end{figure}

### Ok, and about what else do we need to talk? (2/2)

\begin{figure}
 \centering
 \includegraphics[width=.75\textwidth]{iBagens/roc_curve.png}
\end{figure}

# Quadratic Discriminant Analysis (QDA)

###

\textcolor{beamer@UIUCblue}{Unlike} \textcolor{beamer@UIUCorange}{LDA},
\textcolor{beamer@UIUCorange}{QDA} assumes that each class has its
\textcolor{beamer@UIUCblue}{own} covariance matrix.

Under this assumption, the \textcolor{beamer@UIUCblue}{approximation} of
the Bayes classifier becomes
\[
\textcolor{beamer@UIUCorange}{\text{QLA}}: \quad
\hat{\delta}_{\textcolor{red}{k}}(x) =
- \frac{1}{2} (x-\hat{\mu}_{\textcolor{red}{k}})^{\top}
              \hat{\bm{\Sigma}}_{\textcolor{red}{k}}^{-1}
              (x-\hat{\mu}_{\textcolor{red}{k}})
- \frac{1}{2} \log |\hat{\bm{\Sigma}}_{\textcolor{red}{k}}|
+ \log \hat{\pi}_{\textcolor{red}{k}}.
\]
\(x\) appears as a \textcolor{beamer@UIUCorange}{quadratic} function,
this is where \textcolor{beamer@UIUCorange}{QDA} gets its name.
\pause
\begin{figure}
 \centering
 \includegraphics[width=.7\textwidth]{iBagens/qda-ex.png}
\end{figure}

### Ok, but... in practice, what's the difference?

\textcolor{beamer@UIUCblue}{Why} does it matter whether or not we assume
that the \(\textcolor{red}{K}\) classes share a common covariance
matrix?

The \textcolor{beamer@UIUCblue}{answer} lies in the
\textcolor{beamer@UIUCorange}{bias-variance trade-off.}

\begin{figure} \centering
\includegraphics[width=.85\textwidth]{iBagens/bias-variance_trade-off.jpeg}
\end{figure}

### Concluding...

\textcolor{beamer@UIUCorange}{LDA} tends to be a
\textcolor{beamer@UIUCblue}{better} bet than
\textcolor{beamer@UIUCorange}{QDA} if there are relatively few
observations and so \textcolor{beamer@UIUCblue}{reducing variance is
crucial}.

In contrast, \textcolor{beamer@UIUCorange}{QDA} is
\textcolor{beamer@UIUCblue}{recommended if the data set is very large},
so that the variance of the classifier is not a major concern, or if the
assumption of a common covariance matrix for the \(\textcolor{red}{K}\)
classes is clearly untenable.

# Main remarks

###

+ The \textcolor{beamer@UIUCorange}{logistic regression} and
  \textcolor{beamer@UIUCorange}{LDA} methods are
  \textcolor{beamer@UIUCblue}{closely connected}, since both produce
  \textcolor{beamer@UIUCblue}{linear decision boundaries}.

To make a nicer comparison, we may mencion the
\textcolor{beamer@UIUCorange}{KNN}.

+ \textcolor{beamer@UIUCorange}{KNN} is a completely
  \textcolor{beamer@UIUCblue}{non-parametric} approach: no assumptions
  are made about the shape of the decision boundary. Nevertheless,
  \textcolor{beamer@UIUCorange}{KNN} does not tell us which predictors
  are important.
\noindent{\color{beamer@UIUCorange}\rule{\linewidth}{0.25mm}}

+ When the true
\textcolor{beamer@UIUCblue}{decision boundaries} are
  \textcolor{beamer@UIUCblue}{linear}, the
  \textcolor{beamer@UIUCorange}{LDA} and
  \textcolor{beamer@UIUCorange}{logistic regression} approaches will
  tend to perform well. When the boundaries are
  \textcolor{beamer@UIUCblue}{moderately non-linear},
  \textcolor{beamer@UIUCorange}{QDA} may give better results. Finally,
  for much more \textcolor{beamer@UIUCblue}{complicated decision
  boundaries}, a non-parametric approach such as
  \textcolor{beamer@UIUCorange}{KNN} can be superior. But the level of
  smoothness for a non-parametric approach must be chosen carefully.

### and...

\begin{figure} \centering \includegraphics[width=.5\textwidth]{end.jpg}
\end{figure}
\hfill \small \href{mailto:laureano@ufpr.br}{laureano@ufpr.br}
