main.tex

\documentclass{article}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{bbm}

\begin{document}

\tableofcontents

\pagebreak

\section{Introduction to Machine Learning}

\begin{itemize}
    \item Machine learning algorithms are statistical algorithms that can learn from data and generalize to unseen data, thus performing tasks without explicit instructions.
    \item In supervised methods we know the outcome Y for each input X; often, the task is to predict Y based on X.
    \item In unsupervised methods we have only the inputs X. Typical tasks are about finding structure in data.
    \begin{itemize}
        \item For example, it can be used to find "clusters".
    \end{itemize}
    \item X is often known as:
    \begin{itemize}
        \item Input
        \item Feature
        \item Predictor
        \item Covariate
        \item Independent variable
    \end{itemize}
    \item Y is often known as:
    \begin{itemize}
        \item Output
        \item Outcome
        \item Response
        \item Target variable
        \item Dependent variable
    \end{itemize}
    \item Supervised problems are often referred to as either:
    \begin{itemize}
        \item \textbf{Regression}: The outcome Y is quantitative (typically $\mathbb{R}$)s
        \item \textbf{Classification}: The outcome Y is categorical
    \end{itemize}
\end{itemize}

\pagebreak

\section{Linear Regression}

\subsection{Simple Linear Regression}
Simple linear regression models the relationship between a single predictor \(X\) and a response \(Y\) using a linear function:
\[
Y = \beta_0 + \beta_1 X + \epsilon,
\]
where:
\begin{itemize}
    \item \(\beta_0\) is the intercept,
    \item \(\beta_1\) is the slope of the line,
    \item \(\epsilon\) is the error term, which is assumed to be normally distributed with mean 0.
\end{itemize}
The coefficients \(\beta_0\) and \(\beta_1\) are estimated using the least squares criterion, which minimizes the residual sum of squares (RSS):
\[
RSS = \sum_{i=1}^{n} (y_i - \hat{y}_i)^2 = \sum_{i=1}^{n} (y_i - (\beta_0 + \beta_1 x_i))^2.
\]

\textbf{Interpretation:} 
\begin{itemize}
    \item \(\beta_1\) represents the average change in the response \(Y\) associated with a one-unit change in the predictor \(X\).
    \item For example, in predicting sales based on TV advertising spend, \(\beta_1\) would indicate how much sales increase, on average, for each additional unit of advertising expenditure on TV.
\end{itemize}

\subsection{Multiple Linear Regression}
Multiple linear regression extends the simple linear regression model to include multiple predictors:
\[
Y = \beta_0 + \beta_1 X_1 + \beta_2 X_2 + \ldots + \beta_p X_p + \epsilon.
\]
Here:
\begin{itemize}
    \item Each \(\beta_j\) represents the change in \(Y\) associated with a one-unit change in \(X_j\), holding all other predictors constant.
    \item The model can be written in matrix notation as:
    \[
    Y = X\beta + \epsilon,
    \]
    where \(Y\) is an \(n \times 1\) vector of responses, \(X\) is an \(n \times (p+1)\) matrix of predictors (including a column of ones for the intercept), \(\beta\) is a \((p+1) \times 1\) vector of coefficients, and \(\epsilon\) is an \(n \times 1\) vector of errors.
\end{itemize}

\textbf{Example: Advertising Data.} Consider a multiple regression model for predicting sales using TV, radio, and newspaper advertising budgets:
\[
\text{sales} = \beta_0 + \beta_1 \cdot \text{TV} + \beta_2 \cdot \text{radio} + \beta_3 \cdot \text{newspaper} + \epsilon.
\]
The estimated coefficients \(\beta_1, \beta_2,\) and \(\beta_3\) help to understand the individual contribution of each type of advertising while accounting for the other types.

\subsection{3.3 Other Considerations in the Regression Model}
\textbf{Qualitative Predictors:} 
Qualitative or categorical predictors can be incorporated into regression models by creating dummy variables. For example, if the predictor is a categorical variable 'region' with three levels (East, West, North), we can introduce two dummy variables:
\[
\text{region}_1 = 
\begin{cases} 
1 & \text{if East} \\
0 & \text{otherwise}
\end{cases}, \quad 
\text{region}_2 = 
\begin{cases} 
1 & \text{if West} \\
0 & \text{otherwise}
\end{cases}.
\]
Incorporating these into the regression model allows us to estimate different intercepts for each region.

\textbf{Interaction Terms:}
Interaction terms allow modeling situations where the effect of one predictor depends on another. For example, if we believe that the effect of TV advertising on sales depends on the level of radio advertising, we can include an interaction term:
\[
\text{sales} = \beta_0 + \beta_1 \cdot \text{TV} + \beta_2 \cdot \text{radio} + \beta_3 \cdot (\text{TV} \times \text{radio}) + \epsilon.
\]

\textbf{Extensions and Potential Problems:}
\begin{itemize}
    \item \textbf{Polynomial Regression:} Adds polynomial terms to the regression model to capture non-linear relationships.
    \item \textbf{Potential Issues:} Multicollinearity (high correlation among predictors), non-linearity of relationships, and outliers can affect model estimates.
\end{itemize}


\section{Bias and Variance}

Assuming $Y=f(X_0)+\varepsilon$, where:
\begin{itemize}
    \item $\mathbb{E}(\varepsilon)=0$
    \item $\varepsilon$ is independent of $X_0$
\end{itemize}
When fitting $\hat{f}$ with a dataset of $N$ observations ($X$,$Y$)
\begin{itemize}
    \item $N$ observations = \textit{training data}
    \item Algorithm for fitting $\hat{f}$ = \textit{learner}
    \item Applying learner to the training data = \textit{training}
\end{itemize}
Given training data and a chosen model framework, we want to minimize \textit{expected test MSE}: 
\begin{align*}
    \mathbb{E}[(Y_0-\hat{f}(X_0))^2]
\end{align*}
The expected test MSE at $x_0$ is:
\begin{align*}
    \mathbb{E}(Y_0-\hat{f}(x_0))=\mathbb{E}(\hat{f}(x_0)-\mathbb{E}(\hat{f}(x_0)))^2+(\mathbb{E}(\hat{f}(x_0))-f(x_0))^2+\text{Var}(\varepsilon)
\end{align*}
Where:
\begin{itemize}
    \item $\mathbb{E}(\hat{f}(x_0)-\mathbb{E}(\hat{f}(x_0)))^2$ is the Variance of $\hat{f}(x_0)$, the amount by which $\hat{f}$ would change if it were estimated with a different training data set
    \item $\mathbb{E}(\hat{f}(x_0))-f(x_0)$ is the Bias of $\hat{f}(X_0)$, the expected deviation of the model prediction from the true value - a.k.a., the inability to capture the true relationship
\end{itemize}
In the MSE, all 3 terms are non-negative, so any large term = large MSE; however, variance and bias are both \textit{reducible errors}.

\subsection{Validation sets}

If we wish to use MSE for model building - selecting features and tuning hyperparameters - we create a validation set, separate from training/testing set, for estimating the MSE.

\subsubsection{Leave-one-out crossvalidation (LOOCV)}

Create $n$ different partitions (where $n$ is amount of data points), with just one validation data point in each.
For each partition, $i$, the test MSE is $(y_i-\hat{y_i})^2$.
The LOOCV estimate for the test MSE is:
\begin{align*}
    \text{MSE} = \frac{1}{n}\sum_{i=n}^{n}(y_i-\hat{y_i})^2
\end{align*}
Downside: This is computationally expensive, requiring $n$ fits.

\subsubsection{$k$-fold crossvalidation}

Create $k$ different partitions ("folds"), in each $1/k$ of the data is for validation. Randomly shuffle data beforehand if it's ordered.

For each fold, compute $\text{MSE}_i$. Then, average:
\begin{align*}
    \frac{1}{k}\sum_{i=1}^{k}\text{MSE}_k
\end{align*}
Downside: Non-deterministic.

\section{Regression with many features}

Problem:
\begin{itemize}
    \item When features $p \approx n$, not enough data to estimate the regression curve well.
    \item When $p > n$, MLE doesn't exist.
\end{itemize}

Solutions:
\begin{itemize}
    \item Model selection
    \item Shrinkage (regularisation)
\end{itemize}

\subsection{Model selection}

As mentioned in 2.6.2, several methods:
\begin{itemize}
    \item \textbf{Best subset:} Self-explanitory, expensive
    \begin{itemize}
        \item Genetic algorithm can be used as heuristic
    \end{itemize}
    \item \textbf{Forward selection:} Start by including no/few variables
    \item \textbf{Backward selection:} Start by including all/many variables
    \item \textbf{Alternating:} Alternate between forward and backward selection
\end{itemize}

For comparing models, AIC, BIC, or test error can be used.

\subsubsection{AIC and BIC}

\begin{align*}
    \text{AIC}=-2\log\hat{L}+2p
\end{align*}
\begin{align*}
    \text{BIC}=-2\log\hat{L}+p \log n
\end{align*}
Where $p$ is the number of parameters, $n$ is the number of features, and d $\hat{L}$ is the maximised likelihood function. Smaller = better.

\subsubsection{Stepwise selection}

\textbf{Backwards:}
\begin{enumerate}
    \item Make initial model, with all/many features
    \item Iterative remove the least relevant feature (largest drop in AIC)
    \item Stop if removing a feature does not drop AIC significantly
\end{enumerate}

\textbf{Forwards:}
\begin{enumerate}
    \item Make initial model, with only intercept/few features
    \item Iterative add the most relevant feature (largest drop in AIC)
    \item Stop if adding a feature does not drop AIC significantly
\end{enumerate}

\subsubsection{Notes on automatic model selection}

\begin{itemize}
    \item One may wish to keep certain variables, even if they are not significant, if they are relevant in some other way, such as to the research question.
    \item One may wish to remove certain variables, even if they are significant, if they complicate interpretations.
\end{itemize}

\subsection{Shrinkage}

Shrinkage helps estimate coefficients $\beta$ in a constrained way, keeping them small. Doing so reduces coefficient variance and can improve the fit.

\subsubsection{Ridge regression}

Ridge regression minimizes the residual sum of squares, but adds a penalty term proportional to the squared magnitude of the coefficients:

\begin{align*}
    \hat{\beta}_\text{ridge} = \underset{\beta}{\mathrm{argmin}} \left\{ \sum_{i=1}^{n} (y_i - \beta_0 - \sum_{j=1}^{p} \beta_j x_{ij})^2 + \lambda \sum_{j=1}^{p} \beta_j^2 \right\}
\end{align*}

Where:
\begin{itemize}
    \item $\lambda \geq 0$ is a tuning parameter that controls the strength of the penalty.
    \item A larger $\lambda$ leads to more shrinkage and smaller coefficients.
    \item Ridge regression shrinks coefficients towards zero but never sets them exactly to zero.
    \item $\text{argmin}$ (short for "argument of the minimum") finds the value of $\beta$ that minimizes the function inside the curly braces. In this case, it finds the coefficients that minimize the sum of squared errors plus the penalty term.
\end{itemize}

\subsubsection{Lasso}

Lasso (Least Absolute Shrinkage and Selection Operator) regression also minimizes the residual sum of squares, but it adds a penalty term proportional to the absolute value of the coefficients:

\begin{align*}
    \hat{\beta}^\text{lasso} = \underset{\beta}{\mathrm{argmin}} \left\{ \sum_{i=1}^{n} (y_i - \beta_0 - \sum_{j=1}^{p} \beta_j x_{ij})^2 + \lambda \sum_{j=1}^{p} |\beta_j| \right\}
\end{align*}

Where:
\begin{itemize}
    \item $\lambda \geq 0$ is a tuning parameter that controls the strength of the penalty.
    \item Lasso encourages sparsity, meaning that some coefficients are set exactly to zero for sufficiently large $\lambda$.
    \item Lasso can be used for both regularization and feature selection.
\end{itemize}

\subsubsection{Lasso vs Ridge}

\textbf{TLDR}: Ridge scales everything down, while Lasso also gets rid of small enough coefficients.

\begin{itemize}
    \item \textbf{Ridge:}
    \begin{itemize}
        \item Ridge regression applies an $L_2$ penalty, which shrinks the coefficients continuously towards zero.
        \item It does not perform feature selection as it keeps all coefficients, though they may be very small.
    \end{itemize}
    
    \item \textbf{Lasso:}
    \begin{itemize}
        \item Lasso applies an $L_1$ penalty, which shrinks some coefficients to zero exactly.
        \item It performs both regularization and feature selection by setting some coefficients to zero.
    \end{itemize}
    
    \item \textbf{Choosing between them:}
    \begin{itemize}
        \item Lasso is preferred when you suspect many features are irrelevant and need automatic feature selection.
        \item Ridge is preferred when all features are potentially relevant but need regularization to prevent overfitting.
        \item Elastic net is a compromise between Ridge and Lasso, applying a combination of $L_1$ and $L_2$ penalties.
    \end{itemize}
\end{itemize}

\section{Classification with Logistic Regression}

\begin{itemize}
    \item Logistic regression seeks to:
    \begin{itemize}
        \item Model the probability of an event occurring depending on the values of the independent variables, which can be categorical or numerical
        \item Estimate the probability that and vent occurs for a randomly selected observation versus the probability that the event does not occur
        \item Predict the effect of a series of variables on a binary response (dependent) variable
        \item Classify observations by estimating the probability that an observation is in a particular category
    \end{itemize}
    \item Binary data does not have a normal distribution, which is needed for linear regression
    \item For logistic regression, we use the $\chi^2$-squared test instead of $F$-test
\end{itemize}

\subsection{Odds}

\begin{itemize}
    \item $\text{odds}=\frac{P(\text{occurring})}{P(\text{not occurring})}=\frac{p}{1-p}$
    \item $p=\frac{e^{\log(\text{odds})}}{1+e^{\log(\text{odds})}}$
    \item $\text{odds ratio}=\frac{\text{odds}_1}{\text{odds}_0}$ for two events with probabilities $p_0$ and $p_1$
    \item In logistic regression for an independent variable, the odds ratio represents how the odds change with a 1 unit increase in the variable, holding all other variables constant
    \item The odds ratio holds constant for the entire range of the variable
\end{itemize}

\subsection{Logit}

\begin{itemize}
    \item The dependent variable in logistic regression follows the Bernoulli distribution having an unknown probability $p$
    \item In logistic regression we are estimating an unknown $p$ for any given linear combination of independent variables. This estimate is $\hat{p}$
    \item We need to link our independent variables to the Bernoulli distribution; that link is called the logit
    \item Logit - the natural log of the odds ratio - maps linear combinations of variables onto the Bernoulli probability distribution with a domain from 0 to 1
    \item $\text{logit}(p)=\ln(\text{odds})=\ln(\frac{p}{1-p})=\ln(p)-\ln(1-p)$
    \item $\text{logit}$ is undefined at $p=0$ and $p=1$
    \item The logit function runs from 0 to 1 along the x-axis, not the y-axis. This we use inverse logit
    \item $\text{logit}^{-1}(\alpha)=\mu_{y|x}=\frac{1}{1+e^{-\alpha}}=\frac{e^{\alpha}}{1+e^{\alpha}}$
    \item The logit is equivalent to a linear function of the independent variables. The antilog of the logit function allows us to find the estimated regression equation
    \item $\text{logit}(p)=\ln(\frac{p}{1-p})=\beta_0+\beta_1x_1$ $\Rightarrow$ $\frac{p}{1-p}=e^{b_0+b_1 x_1}$ $\Rightarrow \dots \Rightarrow$ $\hat{p}=\frac{e^{b_0+b_1 x_1}}{1 + e^{b_0+b_1 x_1}}$, the estimated regression equation
\end{itemize}

\subsection{Estimating the Probability}

\begin{itemize}
    \item Logistic regression uses Maximum Likelihood Estimation (MLE) to estimate the parameters $\beta_0$ and $\beta_1$
    \item MLE seeks to maximize the likelihood function, which measures the probability of observing the given sample data
\end{itemize}

\subsubsection{Likelihood and Log-Likelihood}

\begin{itemize}
    \item The likelihood function $L(\beta_0, \beta_1 \mid y, x)$ is the joint probability of observing the given sample data as a function of the parameters $\beta_0$ and $\beta_1$
    \item For a binary outcome $y_i \in \{0,1\}$ with probability $p_i$ for $y_i=1$ and $(1-p_i)$ for $y_i=0$, the likelihood function for $n$ observations is:
    \[
    L(\beta_0, \beta_1) = \prod_{i=1}^{n} p_i^{y_i} (1-p_i)^{1-y_i}
    \]
    \item The log-likelihood function is the natural logarithm of the likelihood function:
    \[
    \ell(\beta_0, \beta_1) = \ln(L(\beta_0, \beta_1)) = \sum_{i=1}^{n} \left[ y_i \ln(p_i) + (1-y_i) \ln(1-p_i) \right]
    \]
    \item The log-likelihood function is easier to maximize because it converts the product of probabilities into a sum, which is mathematically simpler to handle
\end{itemize}

\subsubsection{Maximum Likelihood Estimation (MLE)}

\begin{itemize}
    \item MLE involves finding the parameter values $\beta_0$ and $\beta_1$ that maximize the log-likelihood function
    \item This is often done using iterative numerical optimization techniques, such as the Newton-Raphson method or gradient descent. There is no direct method like with gaussian (normal) models
    \item The estimated parameters $\hat{\beta}_0$ and $\hat{\beta}_1$ maximize the likelihood of observing the sample data, providing the best fit for the logistic regression model
\end{itemize}

\subsection{Multiple Logistic Regression}

\begin{itemize}
    \item Logistic regression can be extended to handle multiple predictors to model the probability of a binary outcome.
    \item The logistic regression model for multiple predictors takes the form:
    \[
    \log \left(\frac{p(X)}{1-p(X)}\right) = \beta_0 + \beta_1 X_1 + \cdots + \beta_p X_p
    \]
    \item This can be rewritten to give the estimated probability:
    \[
    p(X) = \frac{e^{\beta_0 + \beta_1 X_1 + \cdots + \beta_p X_p}}{1 + e^{\beta_0 + \beta_1 X_1 + \cdots + \beta_p X_p}}
    \]
    \item Each coefficient $\beta_i$ represents the change in the log-odds of the response per unit increase in the corresponding predictor $X_i$, holding all other predictors constant.
\end{itemize}

\subsection{Coefficients and Interpretation of Results}

\begin{itemize}
    \item The coefficients in a logistic regression model indicate the effect of each predictor on the log-odds of the outcome, holding other variables constant.
    \item A positive coefficient increases the odds of the event, while a negative coefficient decreases the odds.
    \item However, when predictors are correlated (confounding), their individual effects may appear different when considered alone versus together, potentially leading to misleading interpretations.
    \item Proper interpretation requires understanding both the individual and combined effects of predictors on the response.
\end{itemize}

\subsubsection{Making Predictions}

\begin{itemize}
    \item Using the logistic regression equation, we can predict the probability of an event occurring for a given set of predictor values.
    \item For example, for a given set of predictor values $X = (X_1, \ldots, X_p)$, the predicted probability of the event is:
    \[
    \hat{p}(X) = \frac{e^{\beta_0 + \beta_1 X_1 + \cdots + \beta_p X_p}}{1 + e^{\beta_0 + \beta_1 X_1 + \cdots + \beta_p X_p}}
    \]
\end{itemize}

\subsection{Multinomial Logistic Regression}

\begin{itemize}
    \item Multinomial logistic regression extends binary logistic regression to classify a response variable with more than two classes.
    \item For $K$ classes, we select one as the baseline (e.g., class $K$), and model the probabilities for the other classes as:
    \[
    \operatorname{Pr}(Y=k \mid X=x)=\frac{e^{\beta_{k0}+\beta_{k1} x_1 + \cdots + \beta_{kp} x_p}}{1 + \sum_{l=1}^{K-1} e^{\beta_{l0} + \beta_{l1} x_1 + \cdots + \beta_{lp} x_p}}
    \]
    for $k = 1, \ldots, K-1$, with the baseline class:
    \[
    \operatorname{Pr}(Y=K \mid X=x)=\frac{1}{1 + \sum_{l=1}^{K-1} e^{\beta_{l0} + \beta_{l1} x_1 + \cdots + \beta_{lp} x_p}}
    \]
    \item The log odds for class $k$ versus the baseline $K$ is:
    \[
    \log \left(\frac{\operatorname{Pr}(Y=k \mid X=x)}{\operatorname{Pr}(Y=K \mid X=x)}\right) = \beta_{k0} + \beta_{k1} x_1 + \cdots + \beta_{kp} x_p
    \]
    \item Coefficients are interpreted in terms of log odds ratios relative to the baseline class. A one-unit increase in $X_j$ leads to a $\beta_{kj}$ increase in the log odds of class $k$ versus the baseline.
\end{itemize}

\subsubsection{Softmax Coding}

\begin{itemize}
    \item In softmax coding, no baseline class is chosen, and probabilities for all $K$ classes are modeled symmetrically:
    \[
    \operatorname{Pr}(Y=k \mid X=x)=\frac{e^{\beta_{k0}+\beta_{k1} x_1 + \cdots + \beta_{kp} x_p}}{\sum_{l=1}^{K} e^{\beta_{l0} + \beta_{l1} x_1 + \cdots + \beta_{lp} x_p}}
    \]
    \item The log odds ratio between two classes $k$ and $k^{\prime}$ is:
    \[
    \log \left(\frac{\operatorname{Pr}(Y=k \mid X=x)}{\operatorname{Pr}(Y=k^{\prime} \mid X=x)}\right) = (\beta_{k0} - \beta_{k^{\prime}0}) + \sum_{j=1}^{p} (\beta_{kj} - \beta_{k^{\prime}j}) x_j
    \]
\end{itemize}

\section{Bayes Classifiers, K-nearest neighbours}

\begin{itemize}
  \item For classifying data points, we can use Bayes' Theorem:
  \[
  p(\mathcal{C}_k \mid X) = \frac{p(X \mid \mathcal{C}_k) p(\mathcal{C}_k)}{p(X)}
  \]
  \item We can assign a data point to the class with the highest posterior probability:
  \[
  d(x) = \arg\max_k \, p(\mathcal{C}_k \mid X)
  \]
  \item Decision regions $\mathcal{R}_k$ are separated by boundaries based on $p(\mathcal{C}_k \mid X)$.
\end{itemize}

\subsection{Loss and Loss Matrix}

\begin{itemize}
  \item The loss matrix $L_{kj}$ captures the cost of predicting class $j$ when the true class is $k$. Each element of the matrix represents how costly a mistake is. For example, a large $L_{kj}$ indicates that predicting $j$ when the true class is $k$ is a serious error.
  \item In the matrix, rows represent the true class, and columns represent the predicted class:
  \[
  L_{kj} \quad \text{(Rows: True Class, Columns: Predicted Class)}
  \]
  \item The goal is to minimize the expected loss:
  \[
  \mathbb{E}[L] = \sum_{k} \sum_{j} \int_{\mathcal{R}_j} L_{kj} p(X) p(\mathcal{C}_k \mid X) \, dX
  \]
  This formula sums over all classes $k$ and predictions $j$, calculating the total cost of assigning a point $X$ to class $j$ while the true class is $k$. The integral over region $\mathcal{R}_j$ considers all feature space where class $j$ is predicted.
  \item To minimize loss, we assign $X$ to the class $j$ that minimizes:
  \[
  \sum_{k} L_{kj} p(\mathcal{C}_k \mid X)
  \]
  Here, for each possible predicted class $j$, we sum the cost $L_{kj}$ weighted by the posterior probability $p(\mathcal{C}_k \mid X)$, selecting the class $j$ that minimizes this sum. This ensures the decision balances the cost of errors with the likelihood of each class.
\end{itemize}

\subsection{Bayes Classifier}

\begin{itemize}
  \item The Bayes classifier is a specific case of minimizing expected loss, using a 0-1 loss function, defined as:
  \[
  L(j, k) = \begin{cases} 1, & j \neq k \\ 0, & j = k \end{cases}
  \]
  This is a loss function, where all errors are equal, unlike in the loss matrix with varying costs.
  
  \item The Bayes classifier assigns a new data point $X$ to the class with the highest posterior probability:
  \[
  d(x) = \arg\max_y \, p(Y = y \mid X)
  \]
\end{itemize}

\subsection{KNN for Classification}

\begin{itemize}
  \item Find the $K$ nearest neighbors to $X_0$ and estimate class probabilities based on neighbors' classes:
  \[
  p(Y = j \mid X_0) = \frac{1}{K} \sum_{i \in \mathcal{N}_0} I(y_i = j)
  \]
  \item Assign to the class with the highest posterior probability.
\end{itemize}

\subsubsection{Choosing $K$}

\begin{itemize}
  \item Low $K$: highly flexible boundaries.
  \item High $K$: less flexible, possibly too rigid.
  \item Choose $K$ via cross-validation to optimize performance.
\end{itemize}

\section{Linear Discriminant Analysis (LDA) and Quadratic Discriminant Analysis (QDA)}

\textbf{Oversimplified TLDR:}
\begin{itemize}
    \item Both assume all classes have a Gaussian distribution
    \item \textbf{LDA:}
    \begin{itemize}
        \item Assumes equal variation (same covariance) between classes
        \item Has straight (linear) decision boundaries
        \item Works well with less data due to fewer parameters to estimate
    \end{itemize}
    \item \textbf{QDA:}
    \begin{itemize}
        \item Assumes different variation (different covariance) between classes
        \item Has curved (quadratic) decision boundaries
        \item More flexible but requires more data to avoid overfitting
    \end{itemize}
\end{itemize}

\subsection{LDA}

\begin{itemize}
  \item LDA is a generative classification model that assumes the feature vectors $\mathbf{x} \in \mathbb{R}^p$ are generated from class-specific Gaussian distributions.
  \item Key assumptions of LDA:
  \begin{itemize}
    \item The class conditional densities $p(\mathbf{x} \mid \mathcal{C}_k)$ are multivariate Gaussian distributions.
    \item All classes share a common covariance matrix $\boldsymbol{\Sigma}$.
  \end{itemize}
  \item The class conditional density function is:
  \[
  p(\mathbf{x} \mid \mathcal{C}_k) = \frac{1}{(2\pi)^{p/2} |\boldsymbol{\Sigma}|^{1/2}} \exp\left( -\frac{1}{2} (\mathbf{x} - \boldsymbol{\mu}_k)^\top \boldsymbol{\Sigma}^{-1} (\mathbf{x} - \boldsymbol{\mu}_k) \right)
  \]
  where:
  \begin{itemize}
    \item $\boldsymbol{\mu}_k$ is the mean vector of class $\mathcal{C}_k$.
    \item $|\boldsymbol{\Sigma}|$ denotes the determinant of the covariance matrix.
    \item $p$ is the number of features.
  \end{itemize}
  \item Using Bayes' theorem, the posterior probability is:
  \[
  P(\mathcal{C}_k \mid \mathbf{x}) = \frac{\pi_k \, p(\mathbf{x} \mid \mathcal{C}_k)}{p(\mathbf{x})}
  \]
  where $\pi_k = P(\mathcal{C}_k)$ is the prior probability of class $\mathcal{C}_k$.
  \item The discriminant function for LDA is linear in $\mathbf{x}$:
  \[
  \delta_k(\mathbf{x}) = \mathbf{x}^\top \boldsymbol{\Sigma}^{-1} \boldsymbol{\mu}_k - \frac{1}{2} \boldsymbol{\mu}_k^\top \boldsymbol{\Sigma}^{-1} \boldsymbol{\mu}_k + \ln \pi_k
  \]
  \item Classification rule:
  \[
  \text{Assign } \mathbf{x} \text{ to class } \mathcal{C}_k \text{ if } \delta_k(\mathbf{x}) = \max_{j} \delta_j(\mathbf{x})
  \]
  \item Decision boundaries are linear hyperplanes separating the classes.
\end{itemize}

\subsubsection{Estimation of Parameters}

\begin{itemize}
  \item \textbf{Class Means}:
  \[
  \hat{\boldsymbol{\mu}}_k = \frac{1}{n_k} \sum_{i \in \mathcal{C}_k} \mathbf{x}_i
  \]
  where $n_k$ is the number of observations in class $\mathcal{C}_k$.
  \item \textbf{Common Covariance Matrix}:
  \[
  \hat{\boldsymbol{\Sigma}} = \frac{1}{n - K} \sum_{k=1}^K \sum_{i \in \mathcal{C}_k} (\mathbf{x}_i - \hat{\boldsymbol{\mu}}_k)(\mathbf{x}_i - \hat{\boldsymbol{\mu}}_k)^\top
  \]
  where $n$ is the total number of observations and $K$ is the number of classes.
  \item \textbf{Class Priors}:
  \[
  \hat{\pi}_k = \frac{n_k}{n}
  \]
  These can also be set based on prior knowledge.
\end{itemize}

\subsection{Quadratic Discriminant Analysis (QDA)}

\begin{itemize}
  \item QDA relaxes the assumption of a common covariance matrix, allowing each class to have its own covariance matrix $\boldsymbol{\Sigma}_k$.
  \item The class conditional density function is:
  \[
  p(\mathbf{x} \mid \mathcal{C}_k) = \frac{1}{(2\pi)^{p/2} |\boldsymbol{\Sigma}_k|^{1/2}} \exp\left( -\frac{1}{2} (\mathbf{x} - \boldsymbol{\mu}_k)^\top \boldsymbol{\Sigma}_k^{-1} (\mathbf{x} - \boldsymbol{\mu}_k) \right)
  \]
  \item The discriminant function for QDA is quadratic in $\mathbf{x}$:
  \[
  \delta_k(\mathbf{x}) = -\frac{1}{2} \ln |\boldsymbol{\Sigma}_k| - \frac{1}{2} (\mathbf{x} - \boldsymbol{\mu}_k)^\top \boldsymbol{\Sigma}_k^{-1} (\mathbf{x} - \boldsymbol{\mu}_k) + \ln \pi_k
  \]
  \item Classification rule:
  \[
  \text{Assign } \mathbf{x} \text{ to class } \mathcal{C}_k \text{ if } \delta_k(\mathbf{x}) = \max_{j} \delta_j(\mathbf{x})
  \]
  \item Decision boundaries are quadratic surfaces in the feature space.
\end{itemize}

\subsubsection{Estimation of Parameters}

\begin{itemize}
  \item \textbf{Class Means}:
  \[
  \hat{\boldsymbol{\mu}}_k = \frac{1}{n_k} \sum_{i \in \mathcal{C}_k} \mathbf{x}_i
  \]
  \item \textbf{Class Covariance Matrices}:
  \[
  \hat{\boldsymbol{\Sigma}}_k = \frac{1}{n_k - 1} \sum_{i \in \mathcal{C}_k} (\mathbf{x}_i - \hat{\boldsymbol{\mu}}_k)(\mathbf{x}_i - \hat{\boldsymbol{\mu}}_k)^\top
  \]
  \item \textbf{Class Priors}:
  \[
  \hat{\pi}_k = \frac{n_k}{n}
  \]
\end{itemize}

\subsection{Comparison between LDA and QDA}

\begin{itemize}
  \item \textbf{Assumptions}:
  \begin{itemize}
    \item LDA assumes equal covariance matrices across classes.
    \item QDA allows for different covariance matrices for each class.
  \end{itemize}
  \item \textbf{Decision Boundaries}:
  \begin{itemize}
    \item LDA produces linear decision boundaries.
    \item QDA produces quadratic decision boundaries.
  \end{itemize}
  \item \textbf{Complexity}:
  \begin{itemize}
    \item LDA estimates fewer parameters, which can be advantageous with limited data.
    \item QDA requires estimation of separate covariance matrices, increasing the number of parameters.
  \end{itemize}
  \item \textbf{Bias-Variance Tradeoff}:
  \begin{itemize}
    \item LDA may have higher bias if the assumption of equal covariances is violated.
    \item QDA may have higher variance due to more parameters, potentially leading to overfitting.
  \end{itemize}
  \item \textbf{When to Use}:
  \begin{itemize}
    \item LDA is preferred when class covariances are similar and the sample size is small.
    \item QDA is suitable when class covariances differ significantly and there is sufficient data.
  \end{itemize}
\end{itemize}

\subsection{Bias-Variance Tradeoff}

\begin{itemize}
  \item \textbf{LDA}:
  \begin{itemize}
    \item Lower variance due to fewer parameters.
    \item Potentially higher bias if covariance matrices are not equal.
  \end{itemize}
  \item \textbf{QDA}:
  \begin{itemize}
    \item Lower bias as it models each class more flexibly.
    \item Higher variance due to more parameters to estimate.
  \end{itemize}
  \item The choice depends on the dataset size and whether the equal covariance assumption holds.
\end{itemize}

\subsection{Decision Rule Interpretation}

\begin{itemize}
  \item The discriminant functions $\delta_k(\mathbf{x})$ can be seen as scoring functions.
  \item The classification rule selects the class with the highest score.
  \item The decision boundaries are determined by where the discriminant functions are equal.
\end{itemize}

\subsection{Practical Considerations}

\begin{itemize}
  \item \textbf{Regularization}:
  \begin{itemize}
    \item In cases of small sample sizes, covariance estimates may be unstable.
    \item Regularization techniques can be applied to covariance matrices to improve estimates.
  \end{itemize}
  \item \textbf{Computational Efficiency}:
  \begin{itemize}
    \item LDA is computationally less intensive due to a single covariance matrix.
    \item QDA requires inversion of multiple covariance matrices.
  \end{itemize}
  \item \textbf{Assumption Checking}:
  \begin{itemize}
    \item It's important to check the assumption of normality.
    \item Techniques like plotting or statistical tests can be used to assess distributional assumptions.
  \end{itemize}
\end{itemize}

\section{Multivariate Gaussian Distribution, LDA, and QDA with Multiple Features}

\textbf{Oversimplified TLDR:}
\begin{itemize}
    \item Multivariate Gaussian distributions extend the normal distribution to multiple dimensions.
    \item \textbf{LDA with Multiple Features:}
    \begin{itemize}
        \item Assumes class conditional densities are multivariate Gaussian with a common covariance matrix.
        \item Decision boundaries are linear hyperplanes.
    \end{itemize}
    \item \textbf{QDA with Multiple Features:}
    \begin{itemize}
        \item Assumes class conditional densities are multivariate Gaussian with class-specific covariance matrices.
        \item Decision boundaries are quadratic surfaces.
    \end{itemize}
\end{itemize}

\subsection{Multivariate Data}

\begin{itemize}
    \item \textbf{Random Vectors:} If $X_1, X_2, \ldots, X_p$ are real-valued random variables, we can define a $p$-dimensional random vector $\mathbf{X}$ as:
    \[
    \mathbf{X} = \begin{bmatrix} X_1 \\ \vdots \\ X_p \end{bmatrix}
    \]
    \item \textbf{Expectation (Mean):} The expectation of $\mathbf{X}$ is:
    \[
    \mathbb{E}[\mathbf{X}] = \begin{bmatrix} \mathbb{E}[X_1] \\ \vdots \\ \mathbb{E}[X_p] \end{bmatrix}
    \]
    \item \textbf{Sample Mean:} Given $n$ observations $\{\mathbf{X}_1, \mathbf{X}_2, \ldots, \mathbf{X}_n\}$, the sample mean is:
    \[
    \hat{\boldsymbol{\mu}} = \frac{1}{n} \sum_{i=1}^n \mathbf{X}_i
    \]
    \item \textbf{Variance and Covariance Matrix:} The variance of $\mathbf{X}$ is the covariance matrix $\boldsymbol{\Sigma}$, defined as:
    \[
    \operatorname{Var}[\mathbf{X}] = \mathbb{E}\left[(\mathbf{X} - \mathbb{E}[\mathbf{X}]) (\mathbf{X} - \mathbb{E}[\mathbf{X}])^\top\right]
    \]
    where $\boldsymbol{\Sigma}$ is a $p \times p$ matrix with entries:
    \[
    \Sigma_{ij} = \operatorname{Cov}[X_i, X_j]
    \]
\end{itemize}

\subsection{The Multivariate Normal Distribution}

\begin{itemize}
    \item The $p$-dimensional \textbf{Multivariate Normal Distribution} with mean vector $\boldsymbol{\mu}$ and covariance matrix $\boldsymbol{\Sigma}$ has the probability density function:
    \[
    p(\mathbf{x}; \boldsymbol{\mu}, \boldsymbol{\Sigma}) = \frac{1}{(2\pi)^{p/2} |\boldsymbol{\Sigma}|^{1/2}} \exp\left\{ -\frac{1}{2} (\mathbf{x} - \boldsymbol{\mu})^\top \boldsymbol{\Sigma}^{-1} (\mathbf{x} - \boldsymbol{\mu}) \right\}
    \]
    \item The exponent involves the \textbf{Mahalanobis distance}:
    \[
    (\mathbf{x} - \boldsymbol{\mu})^\top \boldsymbol{\Sigma}^{-1} (\mathbf{x} - \boldsymbol{\mu}) = \|\mathbf{x} - \boldsymbol{\mu}\|_{\boldsymbol{\Sigma}}^2
    \]
    \item \textbf{Special Case:} When $\boldsymbol{\Sigma} = \mathbf{I}$ (identity matrix), the variables are independent standard normal, and the Mahalanobis distance reduces to the Euclidean distance:
    \[
    \|\mathbf{x} - \boldsymbol{\mu}\|_{\mathbf{I}}^2 = \sum_{i=1}^p (x_i - \mu_i)^2
    \]
    \item \textbf{Properties:}
    \begin{itemize}
        \item Any linear transformation or translation of a multivariate normal variable is also multivariate normal.
        \item Marginal distributions of subsets of variables are multivariate normal.
    \end{itemize}
\end{itemize}

\subsection{Linear Discriminant Analysis (LDA) with Multiple Features}

\begin{itemize}
    \item \textbf{Assumptions:}
    \begin{itemize}
        \item Each class conditional density $p(\mathbf{x} \mid \mathcal{C}_k)$ is a multivariate normal distribution with mean $\boldsymbol{\mu}_k$ and common covariance matrix $\boldsymbol{\Sigma}$:
        \[
        p(\mathbf{x} \mid \mathcal{C}_k) = \frac{1}{(2\pi)^{p/2} |\boldsymbol{\Sigma}|^{1/2}} \exp\left\{ -\frac{1}{2} (\mathbf{x} - \boldsymbol{\mu}_k)^\top \boldsymbol{\Sigma}^{-1} (\mathbf{x} - \boldsymbol{\mu}_k) \right\}
        \]
    \end{itemize}
    \item \textbf{Discriminant Function:}
    \begin{itemize}
        \item The discriminant function for class $\mathcal{C}_k$ is derived from the log of the joint probability:
        \[
        g_k(\mathbf{x}) = \ln \pi_k - \frac{1}{2} (\mathbf{x} - \boldsymbol{\mu}_k)^\top \boldsymbol{\Sigma}^{-1} (\mathbf{x} - \boldsymbol{\mu}_k)
        \]
        \item Simplifies to:
        \[
        g_k(\mathbf{x}) = \mathbf{x}^\top \boldsymbol{\Sigma}^{-1} \boldsymbol{\mu}_k - \frac{1}{2} \boldsymbol{\mu}_k^\top \boldsymbol{\Sigma}^{-1} \boldsymbol{\mu}_k + \ln \pi_k
        \]
    \end{itemize}
    \item \textbf{Classification Rule:}
    \begin{itemize}
        \item Assign $\mathbf{x}$ to the class with the highest discriminant score:
        \[
        \text{Classify } \mathbf{x} \text{ to class } \mathcal{C}_k \text{ if } g_k(\mathbf{x}) = \max_j g_j(\mathbf{x})
        \]
    \end{itemize}
    \item \textbf{Decision Boundaries:}
    \begin{itemize}
        \item The boundaries between classes are linear hyperplanes where $g_j(\mathbf{x}) = g_k(\mathbf{x})$.
    \end{itemize}
\end{itemize}

\subsection{Quadratic Discriminant Analysis (QDA) with Multiple Features}

\begin{itemize}
    \item \textbf{Assumptions:}
    \begin{itemize}
        \item Each class conditional density $p(\mathbf{x} \mid \mathcal{C}_k)$ is a multivariate normal distribution with mean $\boldsymbol{\mu}_k$ and covariance matrix $\boldsymbol{\Sigma}_k$:
        \[
        p(\mathbf{x} \mid \mathcal{C}_k) = \frac{1}{(2\pi)^{p/2} |\boldsymbol{\Sigma}_k|^{1/2}} \exp\left\{ -\frac{1}{2} (\mathbf{x} - \boldsymbol{\mu}_k)^\top \boldsymbol{\Sigma}_k^{-1} (\mathbf{x} - \boldsymbol{\mu}_k) \right\}
        \]
    \end{itemize}
    \item \textbf{Discriminant Function:}
    \begin{itemize}
        \item The discriminant function for class $\mathcal{C}_k$ is:
        \[
        g_k(\mathbf{x}) = \ln \pi_k - \frac{1}{2} \ln |\boldsymbol{\Sigma}_k| - \frac{1}{2} (\mathbf{x} - \boldsymbol{\mu}_k)^\top \boldsymbol{\Sigma}_k^{-1} (\mathbf{x} - \boldsymbol{\mu}_k)
        \]
    \end{itemize}
    \item \textbf{Classification Rule:}
    \begin{itemize}
        \item Assign $\mathbf{x}$ to the class with the highest $g_k(\mathbf{x})$.
    \end{itemize}
    \item \textbf{Decision Boundaries:}
    \begin{itemize}
        \item The boundaries between classes are quadratic surfaces defined by $g_j(\mathbf{x}) = g_k(\mathbf{x})$.
    \end{itemize}
\end{itemize}

\subsection{Constructing Decision Boundaries}

\begin{itemize}
    \item \textbf{LDA Decision Boundary:}
    \begin{itemize}
        \item Between classes $\mathcal{C}_j$ and $\mathcal{C}_k$, the decision boundary is where:
        \[
        g_j(\mathbf{x}) = g_k(\mathbf{x})
        \]
        \item Simplifies to a linear equation in $\mathbf{x}$.
    \end{itemize}
    \item \textbf{Effect of Class Priors:}
    \begin{itemize}
        \item Increasing the prior probability $\pi_k$ shifts the decision boundary away from $\boldsymbol{\mu}_k$.
        \item The term $\ln \pi_k$ influences the discriminant function.
    \end{itemize}
    \item \textbf{QDA Decision Boundary:}
    \begin{itemize}
        \item Boundaries are more complex due to class-specific covariance matrices.
        \item The equation $g_j(\mathbf{x}) = g_k(\mathbf{x})$ results in quadratic terms.
    \end{itemize}
\end{itemize}

\subsection{Issues with LDA and QDA}

\begin{itemize}
    \item \textbf{Number of Parameters:}
    \begin{itemize}
        \item Covariance matrix $\boldsymbol{\Sigma}$ has $\frac{p(p+1)}{2}$ parameters.
        \item LDA estimates one covariance matrix; QDA estimates one per class.
    \end{itemize}
    \item \textbf{Bias-Variance Trade-Off:}
    \begin{itemize}
        \item LDA has lower variance but higher bias if the assumption of equal covariances is incorrect.
        \item QDA has lower bias but higher variance due to more parameters.
    \end{itemize}
    \item \textbf{Naive Bayes Classifier:}
    \begin{itemize}
        \item Assumes independence among features, leading to diagonal covariance matrices.
        \item Simplifies computation but may not capture feature correlations.
    \end{itemize}
\end{itemize}

\subsection{Case Studies}

\subsubsection{Case 1: Equal Covariance Matrices (No Correlations)}

\begin{itemize}
    \item Covariance matrices are equal and features are uncorrelated.
    \item LDA performs well due to matching assumptions.
    \item Logistic regression and Naive Bayes provide similar performance.
\end{itemize}

\subsubsection{Case 2: Unequal Covariance Matrices (No Correlations)}

\begin{itemize}
    \item Covariance matrices differ but features remain uncorrelated.
    \item QDA outperforms LDA as it models class-specific covariances.
    \item Logistic regression may require additional features (e.g., interaction terms) to capture the non-linearity.
\end{itemize}

\subsubsection{Case 3: Unequal Covariance Matrices (With Correlations)}

\begin{itemize}
    \item Covariance matrices differ and features are correlated.
    \item QDA and logistic regression with interaction terms perform best.
    \item Naive Bayes performs poorly due to the independence assumption.
\end{itemize}

\subsection{Test Error Comparison}

\begin{center}
\begin{tabular}{lccccc}
\hline
 & LDA & QDA & Naive Bayes & Logistic Regression & Logistic Regression (Quadratic) \\
\hline
Case 1 & 1.20\% & 1.30\% & 1.33\% & 1.40\% & 1.33\% \\
Case 2 & 8.00\% & 7.27\% & 7.43\% & 7.60\% & 7.57\% \\
Case 3 & 2.27\% & 0.63\% & 2.20\% & 0.87\% & 0.60\% \\
\hline
\end{tabular}
\end{center}

\subsection{LDA vs Logistic Regression}

\begin{itemize}
    \item \textbf{Relationship:}
    \begin{itemize}
        \item Both produce linear decision boundaries under certain conditions.
        \item LDA assumes normality and equal covariances; logistic regression does not.
    \end{itemize}
    \item \textbf{Log-Posterior Odds:}
    \begin{itemize}
        \item In logistic regression, the log-odds are modeled directly:
        \[
        \log\left( \frac{P(\mathcal{C}_k \mid \mathbf{x})}{P(\mathcal{C}_K \mid \mathbf{x})} \right) = \boldsymbol{\beta}_k^\top \mathbf{x} + \beta_{0k}
        \]
        \item LDA implies a linear model for log-odds when the normality assumptions hold.
    \end{itemize}
    \item \textbf{Advantages of LDA:}
    \begin{itemize}
        \item More efficient if the normality and equal covariance assumptions are valid.
        \item Naturally incorporates class priors.
    \end{itemize}
    \item \textbf{Advantages of Logistic Regression:}
    \begin{itemize}
        \item Flexible in including various types of predictors and transformations.
        \item Does not rely on distributional assumptions.
    \end{itemize}
\end{itemize}

\subsection{Practical Considerations}

\begin{itemize}
    \item \textbf{Regularization:}
    \begin{itemize}
        \item In high dimensions, covariance estimates may be unstable.
        \item Regularization techniques can improve estimates (e.g., shrinkage methods).
    \end{itemize}
    \item \textbf{Computational Efficiency:}
    \begin{itemize}
        \item LDA is computationally less intensive than QDA.
        \item QDA requires inversion of multiple covariance matrices.
    \end{itemize}
    \item \textbf{Assumption Checking:}
    \begin{itemize}
        \item Check normality of features using plots or tests.
        \item Verify the homogeneity of covariances for LDA.
    \end{itemize}
    \item \textbf{Feature Engineering:}
    \begin{itemize}
        \item Including interaction terms or polynomial features can improve logistic regression.
        \item Dimensionality reduction techniques (e.g., PCA) may be beneficial.
    \end{itemize}
\end{itemize}

\section{Performance Metrics in Classification}

\textbf{Oversimplified TLDR:}
\begin{itemize}
    \item Classification performance is assessed using various metrics beyond simple accuracy.
    \item \textbf{Confusion Matrix:} Summarizes the correct and incorrect predictions for each class.
    \item \textbf{Precision:} Measures the proportion of positive identifications that are correct.
    \item \textbf{Recall:} Measures the proportion of actual positives correctly identified.
    \item \textbf{F1-Score:} Harmonic mean of precision and recall; balances both metrics.
    \item \textbf{ROC Curve:} Plots true positive rate against false positive rate at various thresholds.
    \item \textbf{Adjusting Decision Threshold:} Changes the balance between precision and recall.
\end{itemize}

\subsection{Confusion Matrix}

\begin{itemize}
    \item A confusion matrix is a table that describes the performance of a classification model.
    \item For binary classification, it is a $2 \times 2$ matrix:
    \[
    \begin{tabular}{|c|c|c|}
    \hline
    & \textbf{Predicted Positive} & \textbf{Predicted Negative} \\
    \hline
    \textbf{Actual Positive} & \text{True Positive (TP)} & \text{False Negative (FN)} \\
    \hline
    \textbf{Actual Negative} & \text{False Positive (FP)} & \text{True Negative (TN)} \\
    \hline
    \end{tabular}
    \]
    \item Definitions:
    \begin{itemize}
        \item \textbf{True Positive (TP):} Correctly predicted positive instances.
        \item \textbf{False Positive (FP):} Incorrectly predicted positive instances.
        \item \textbf{False Negative (FN):} Incorrectly predicted negative instances.
        \item \textbf{True Negative (TN):} Correctly predicted negative instances.
    \end{itemize}
    \item The confusion matrix can be extended to multi-class classification problems.
\end{itemize}

\subsubsection{Stock Price Prediction Example}

\begin{itemize}
    \item Task: Predict stock price movement (\textit{Increase}, \textit{Decrease}, \textit{Unchanged}).
    \item Sample confusion matrix:
    \[
    \begin{tabular}{|c|c|c|c|c|}
    \hline
    & \multicolumn{3}{c|}{\textbf{Predicted Class}} & \textbf{Total} \\
    \hline
    \textbf{Actual Class} & \text{Increase} & \text{Decrease} & \text{Unchanged} & \\
    \hline
    \text{Increase} & 9 & 3 & 28 & 40 \\
    \hline
    \text{Decrease} & 1 & 5 & 34 & 40 \\
    \hline
    \text{Unchanged} & 4 & 3 & 33 & 40 \\
    \hline
    \textbf{Total} & 14 & 11 & 95 & 120 \\
    \hline
    \end{tabular}
    \]
    \item \textbf{Accuracy}:
    \[
    \text{Accuracy} = \frac{9 + 5 + 33}{120} = \frac{47}{120} \approx 0.392
    \]
    \item \textbf{Misclassification Rate}:
    \[
    \text{Misclassification Rate} = 1 - \text{Accuracy} \approx 0.608
    \]
\end{itemize}

\subsection{Accuracy and Misclassification Rate}

\begin{itemize}
    \item \textbf{Accuracy} measures the proportion of correctly classified instances:
    \[
    \text{Accuracy} = \frac{TP + TN}{TP + FP + FN + TN}
    \]
    \item \textbf{Misclassification Rate} is the proportion of incorrectly classified instances:
    \[
    \text{Misclassification Rate} = \frac{FP + FN}{TP + FP + FN + TN}
    \]
    \item High accuracy can be misleading in imbalanced datasets.
\end{itemize}

\subsection{Precision and Recall}

\begin{itemize}
    \item \textbf{Precision} (Positive Predictive Value):
    \[
    \text{Precision} = \frac{TP}{TP + FP}
    \]
    \item \textbf{Recall} (Sensitivity or True Positive Rate):
    \[
    \text{Recall} = \frac{TP}{TP + FN}
    \]
    \item These metrics help understand the model's ability to correctly predict positive instances.
\end{itemize}

\subsubsection{Calculating Precision and Recall for "Increase" Class}

\begin{itemize}
    \item For the \textit{Increase} class:
    \begin{itemize}
        \item \textbf{True Positives (TP)}: 9
        \item \textbf{False Positives (FP)}: Predictions of \textit{Increase} when actual is not \textit{Increase}:
        \[
        \text{FP} = \text{Predicted Increase Total} - \text{TP} = 14 - 9 = 5
        \]
        \item \textbf{False Negatives (FN)}: Actual \textit{Increase} instances predicted as other classes:
        \[
        \text{FN} = \text{Actual Increase Total} - \text{TP} = 40 - 9 = 31
        \]
    \end{itemize}
    \item \textbf{Precision for Increase}:
    \[
    \text{Precision}_{\text{Increase}} = \frac{9}{9 + 5} = \frac{9}{14} \approx 0.643
    \]
    \item \textbf{Recall for Increase}:
    \[
    \text{Recall}_{\text{Increase}} = \frac{9}{9 + 31} = \frac{9}{40} = 0.225
    \]
    \item \textbf{Interpretation}:
    \begin{itemize}
        \item Precision of 0.643 means that 64.3\% of predicted \textit{Increase} instances are correct.
        \item Recall of 0.225 indicates that 22.5\% of actual \textit{Increase} instances are correctly identified.
    \end{itemize}
\end{itemize}

\subsubsection{When to Use Precision vs. Recall}

\begin{itemize}
    \item \textbf{High Precision} is important when false positives are costly.
    \begin{itemize}
        \item Example: Diagnosing a rare disease where treatment is expensive or has side effects.
    \end{itemize}
    \item \textbf{High Recall} is crucial when missing positive cases is costly.
    \begin{itemize}
        \item Example: Screening for cancer where early detection is critical.
    \end{itemize}
\end{itemize}

\subsection{F1-Score}

\begin{itemize}
    \item The F1-score combines precision and recall:
    \[
    F1 = 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}}
    \]
    \item For the \textit{Increase} class:
    \[
    F1_{\text{Increase}} = 2 \times \frac{0.643 \times 0.225}{0.643 + 0.225} \approx 0.333
    \]
    \item The F1-score is low when either precision or recall is low.
\end{itemize}

\subsection{Receiver Operating Characteristic (ROC) Curve}

\begin{itemize}
    \item The ROC curve plots the \textbf{True Positive Rate (TPR)} against the \textbf{False Positive Rate (FPR)} at various thresholds.
    \item \textbf{True Positive Rate (TPR)}:
    \[
    \text{TPR} = \text{Recall} = \frac{TP}{TP + FN}
    \]
    \item \textbf{False Positive Rate (FPR)}:
    \[
    \text{FPR} = \frac{FP}{FP + TN}
    \]
    \item The area under the ROC curve (AUC) indicates the classifier's ability to distinguish between classes.
    \item A higher AUC represents better performance.
\end{itemize}

\subsubsection{Interpreting the ROC Curve}

\begin{itemize}
    \item The ROC curve helps in selecting an optimal threshold by visualizing the trade-off between TPR and FPR.
    \item It is particularly useful in imbalanced datasets.
\end{itemize}

\subsection{Adjusting the Decision Threshold}

\begin{itemize}
    \item Classification models often output probabilities or scores.
    \item The decision threshold determines the point above which instances are classified as positive.
    \item Adjusting the threshold affects precision and recall:
    \begin{itemize}
        \item Increasing the threshold generally increases precision but decreases recall.
        \item Decreasing the threshold generally increases recall but decreases precision.
    \end{itemize}
    \item \textbf{Example}:
    \begin{itemize}
        \item If the cost of false negatives is high, set a lower threshold to increase recall.
        \item If the cost of false positives is high, set a higher threshold to increase precision.
    \end{itemize}
\end{itemize}

\subsubsection{Impact on Confusion Matrix}

\begin{itemize}
    \item As the threshold changes, the numbers in the confusion matrix change accordingly.
    \item This can be visualized by plotting precision and recall against different thresholds.
\end{itemize}

\subsection{Practical Considerations}

\begin{itemize}
    \item \textbf{Choice of Metric}:
    \begin{itemize}
        \item Select metrics that align with the specific goals and context of the task.
        \item Be cautious of relying solely on accuracy.
    \end{itemize}
    \item \textbf{Model Evaluation}:
    \begin{itemize}
        \item Use cross-validation to assess model performance.
        \item Compare models using relevant metrics.
    \end{itemize}
    \item \textbf{Model Interpretability}:
    \begin{itemize}
        \item Consider the trade-off between model complexity and interpretability.
        \item Simpler models may be preferred if they offer similar performance.
    \end{itemize}
\end{itemize}

\subsection{Comparing to Random Classifiers}

\begin{itemize}
    \item A model should perform better than random guessing.
    \item To assess this, compare the model's performance to that of a classifier trained on shuffled labels.
    \item If the model significantly outperforms the random baseline, it suggests that it has learned meaningful patterns.
\end{itemize}

\subsection{Final Thoughts}

\begin{itemize}
    \item Avoid focusing solely on improving numerical metrics without considering practical implications.
    \item Ensure the model is sensible, interpretable, and aligns with domain knowledge.
    \item Consider the costs associated with different types of errors when selecting thresholds and metrics.
\end{itemize}

\section{Principal Component Analysis (PCA) and Dimensionality Reduction}

\textbf{Oversimplified TLDR:}
\begin{itemize}
    \item \textbf{PCA} is an unsupervised technique used to reduce the dimensionality of high-dimensional datasets while preserving as much variance as possible.
    \item It identifies new orthogonal axes (principal components) that capture the maximum variance in the data.
    \item The first principal component accounts for the largest possible variance, the second for the next largest, and so on.
    \item PCA helps in data visualization, noise reduction, and feature extraction by transforming data to a lower-dimensional space.
\end{itemize}

\subsection{Introduction to PCA}

\begin{itemize}
    \item High-dimensional datasets often pose challenges in terms of computation, visualization, and overfitting.
    \item PCA is an unsupervised linear transformation technique that projects data onto a lower-dimensional subspace.
    \item The goal is to find the directions (principal components) that maximize the variance in the data.
    \item PCA is widely used for:
    \begin{itemize}
        \item Data visualization in two or three dimensions.
        \item Reducing the number of features for computational efficiency.
        \item Identifying patterns and correlations in data.
    \end{itemize}
\end{itemize}

\subsection{Mathematical Foundation of PCA}

\begin{itemize}
    \item Given a dataset with $n$ observations and $p$ features, represented as $\mathbf{X} \in \mathbb{R}^{n \times p}$.
    \item The data is centered by subtracting the mean of each feature:
    \[
    \tilde{\mathbf{X}} = \mathbf{X} - \overline{\mathbf{X}}
    \]
    where $\overline{\mathbf{X}}$ is the mean vector of the features.
    \item The covariance matrix $\mathbf{S}$ of the centered data is:
    \[
    \mathbf{S} = \frac{1}{n-1} \tilde{\mathbf{X}}^\top \tilde{\mathbf{X}}
    \]
    \item PCA involves solving the eigenvalue decomposition of the covariance matrix:
    \[
    \mathbf{S} \mathbf{a}_k = \lambda_k \mathbf{a}_k
    \]
    where:
    \begin{itemize}
        \item $\lambda_k$ is the $k$-th eigenvalue.
        \item $\mathbf{a}_k$ is the corresponding eigenvector (principal component).
    \end{itemize}
    \item The eigenvalues represent the amount of variance captured by each principal component.
\end{itemize}

\subsection{Derivation of Principal Components}

\begin{itemize}
    \item \textbf{Goal}: Find a unit vector $\mathbf{a}_1$ such that the projection of the data onto $\mathbf{a}_1$ maximizes the variance:
    \[
    \max_{\mathbf{a}_1} \operatorname{Var}(\mathbf{a}_1^\top \tilde{\mathbf{X}})
    \]
    subject to $\|\mathbf{a}_1\| = 1$.
    \item The variance of the projected data is:
    \[
    \operatorname{Var}(\mathbf{a}_1^\top \tilde{\mathbf{X}}) = \mathbf{a}_1^\top \mathbf{S} \mathbf{a}_1
    \]
    \item Using the method of Lagrange multipliers, we set up the objective function:
    \[
    L(\mathbf{a}_1, \lambda) = \mathbf{a}_1^\top \mathbf{S} \mathbf{a}_1 - \lambda (\mathbf{a}_1^\top \mathbf{a}_1 - 1)
    \]
    \item Taking the derivative with respect to $\mathbf{a}_1$ and setting it to zero:
    \[
    \frac{\partial L}{\partial \mathbf{a}_1} = 2\mathbf{S} \mathbf{a}_1 - 2\lambda \mathbf{a}_1 = 0
    \]
    \item This leads to the eigenvalue equation:
    \[
    \mathbf{S} \mathbf{a}_1 = \lambda \mathbf{a}_1
    \]
    \item The eigenvector $\mathbf{a}_1$ corresponding to the largest eigenvalue $\lambda_1$ is the first principal component.
\end{itemize}

\subsection{Subsequent Principal Components}

\begin{itemize}
    \item After finding the first principal component, subsequent components are found by maximizing the variance in directions orthogonal to the previous components.
    \item For the $k$-th principal component $\mathbf{a}_k$, the optimization problem is:
    \[
    \max_{\mathbf{a}_k} \mathbf{a}_k^\top \mathbf{S} \mathbf{a}_k
    \]
    subject to:
    \begin{align*}
    \|\mathbf{a}_k\| &= 1 \\
    \mathbf{a}_k^\top \mathbf{a}_j &= 0 \quad \text{for } j = 1, \dots, k-1
    \end{align*}
    \item This ensures that all principal components are orthogonal (uncorrelated).
\end{itemize}

\subsection{Principal Component Scores}

\begin{itemize}
    \item The principal component scores for observation $i$ are calculated as:
    \[
    z_{ik} = \mathbf{a}_k^\top (\mathbf{x}_i - \overline{\mathbf{x}})
    \]
    where $\mathbf{x}_i$ is the $i$-th observation.
    \item The scores represent the coordinates of the data in the new principal component space.
\end{itemize}

\subsection{Reconstruction of Data}

\begin{itemize}
    \item The original data can be reconstructed from the principal components:
    \[
    \mathbf{x}_i = \overline{\mathbf{x}} + \sum_{k=1}^p z_{ik} \mathbf{a}_k
    \]
    \item By using only the first $m < p$ principal components, we obtain an approximation:
    \[
    \tilde{\mathbf{x}}_i = \overline{\mathbf{x}} + \sum_{k=1}^m z_{ik} \mathbf{a}_k
    \]
    \item The approximation minimizes the reconstruction error in the least-squares sense.
\end{itemize}

\subsection{Explained Variance and Choosing the Number of Components}

\begin{itemize}
    \item The total variance in the data is the sum of the variances of all principal components:
    \[
    \text{Total Variance} = \sum_{k=1}^p \lambda_k
    \]
    \item The proportion of variance explained by the $k$-th principal component is:
    \[
    \text{Proportion Variance Explained} = \frac{\lambda_k}{\sum_{j=1}^p \lambda_j}
    \]
    \item A Scree plot can be used to visualize the explained variance and determine an appropriate number of components.
    \item Common criteria for choosing $m$:
    \begin{itemize}
        \item Cumulative explained variance reaches a threshold (e.g., 90\%).
        \item The point of diminishing returns in the Scree plot (elbow method).
    \end{itemize}
\end{itemize}

\subsection{Data Visualization using PCA}

\begin{itemize}
    \item PCA can reduce high-dimensional data to two or three dimensions for visualization.
    \item Scatter plots of the first two or three principal components can reveal patterns, clusters, or outliers.
    \item Biplots combine scores and loadings to display both observations and variables in the principal component space.
    \item In a biplot:
    \begin{itemize}
        \item Points represent observations projected onto the principal components.
        \item Vectors represent variables, showing their contributions (loadings) to the components.
        \item The angle between vectors indicates the correlation between variables.
    \end{itemize}
\end{itemize}

\subsection{Centering and Scaling}

\begin{itemize}
    \item Centering the data (subtracting the mean) is essential for PCA to ensure that the first principal component describes the direction of maximum variance.
    \item Scaling (standardizing) the data is important when variables are measured in different units or have different variances.
    \item Without scaling, variables with larger variances may dominate the principal components.
    \item Standardization transforms each feature to have zero mean and unit variance:
    \[
    \tilde{x}_{ij} = \frac{x_{ij} - \overline{x}_j}{s_j}
    \]
    where $s_j$ is the standard deviation of feature $j$.
\end{itemize}

\subsection{PCA Approximations and Reconstruction Error}

\begin{itemize}
    \item The reconstruction error when approximating data using the first $m$ principal components is:
    \[
    E = \sum_{k=m+1}^p \lambda_k
    \]
    \item This error represents the variance not captured by the selected components.
    \item Minimizing the reconstruction error is equivalent to capturing the maximum variance with fewer components.
\end{itemize}

\subsection{PCA and the Singular Value Decomposition (SVD)}

\begin{itemize}
    \item PCA can also be computed using the Singular Value Decomposition of the data matrix.
    \item For the centered data matrix $\tilde{\mathbf{X}}$:
    \[
    \tilde{\mathbf{X}} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^\top
    \]
    where:
    \begin{itemize}
        \item $\mathbf{U} \in \mathbb{R}^{n \times p}$ contains the left singular vectors.
        \item $\mathbf{\Sigma} \in \mathbb{R}^{p \times p}$ is a diagonal matrix with singular values.
        \item $\mathbf{V} \in \mathbb{R}^{p \times p}$ contains the right singular vectors.
    \end{itemize}
    \item The principal components are related to the right singular vectors:
    \[
    \mathbf{a}_k = \mathbf{v}_k
    \]
    \item The singular values are related to the square roots of the eigenvalues:
    \[
    \sigma_k = \sqrt{\lambda_k}
    \]
\end{itemize}

\subsection{Practical Considerations}

\begin{itemize}
    \item \textbf{Interpretation of Principal Components}:
    \begin{itemize}
        \item The loadings indicate the contribution of each original variable to the principal components.
        \item Understanding the loadings helps in interpreting the meaning of each principal component.
    \end{itemize}
    \item \textbf{Assumptions and Limitations}:
    \begin{itemize}
        \item PCA assumes linear relationships between variables.
        \item It is sensitive to outliers, which can distort the variance structure.
        \item PCA captures variance, not necessarily the features important for classification or prediction.
    \end{itemize}
    \item \textbf{Centering and Scaling Decisions}:
    \begin{itemize}
        \item Deciding whether to scale variables depends on the context and the importance of preserving the original units.
        \item If all variables are on the same scale and variance, scaling may not be necessary.
    \end{itemize}
    \item \textbf{Missing Data}:
    \begin{itemize}
        \item PCA requires a complete dataset; missing values must be handled appropriately.
        \item Techniques include imputation or using algorithms that can handle missing data.
    \end{itemize}
    \item \textbf{Software Implementation}:
    \begin{itemize}
        \item PCA is available in many statistical software packages and libraries.
        \item Ensure that the implementation matches the intended use (e.g., centered vs. uncentered PCA).
    \end{itemize}
\end{itemize}

\subsection{PCA for Sphering (Whitening) Data}

\begin{itemize}
    \item Sphering transforms data to have zero mean and identity covariance matrix.
    \item Steps to sphere data using PCA:
    \begin{enumerate}
        \item Center the data: $\tilde{\mathbf{X}} = \mathbf{X} - \overline{\mathbf{X}}$.
        \item Compute the eigenvalue decomposition: $\mathbf{S} = \mathbf{A} \mathbf{\Lambda} \mathbf{A}^\top$.
        \item Transform the data: $\mathbf{Z} = \mathbf{\Lambda}^{-1/2} \mathbf{A}^\top \tilde{\mathbf{X}}^\top$.
    \end{enumerate}
    \item The transformed data $\mathbf{Z}$ has uncorrelated features with unit variance.
\end{itemize}

\subsection{Applications of PCA}

\begin{itemize}
    \item \textbf{Noise Reduction}:
    \begin{itemize}
        \item By retaining components with significant variance, PCA can filter out noise.
    \end{itemize}
    \item \textbf{Feature Extraction}:
    \begin{itemize}
        \item PCA can create new features (principal components) that may be more effective for modeling.
    \end{itemize}
    \item \textbf{Data Compression}:
    \begin{itemize}
        \item Reducing dimensionality reduces storage space and computational cost.
    \end{itemize}
    \item \textbf{Anomaly Detection}:
    \begin{itemize}
        \item Observations that deviate significantly in the principal component space may be outliers.
    \end{itemize}
\end{itemize}

\subsection{Limitations of PCA}

\begin{itemize}
    \item \textbf{Linearity}:
    \begin{itemize}
        \item PCA captures linear relationships; nonlinear structures may not be well-represented.
    \end{itemize}
    \item \textbf{Interpretability}:
    \begin{itemize}
        \item Principal components are linear combinations of original features, which may be hard to interpret.
    \end{itemize}
    \item \textbf{Scaling Sensitivity}:
    \begin{itemize}
        \item PCA is sensitive to the scaling of variables; inappropriate scaling can mislead the analysis.
    \end{itemize}
    \item \textbf{Outliers}:
    \begin{itemize}
        \item Outliers can disproportionately affect the principal components.
    \end{itemize}
\end{itemize}

\subsection{Alternatives and Extensions to PCA}

\begin{itemize}
    \item \textbf{Kernel PCA}:
    \begin{itemize}
        \item Extends PCA to capture nonlinear structures using kernel functions.
    \end{itemize}
    \item \textbf{Independent Component Analysis (ICA)}:
    \begin{itemize}
        \item Decomposes data into statistically independent components, useful for source separation.
    \end{itemize}
    \item \textbf{Factor Analysis}:
    \begin{itemize}
        \item Assumes an underlying latent variable model explaining the observed variables.
    \end{itemize}
    \item \textbf{t-Distributed Stochastic Neighbor Embedding (t-SNE)}:
    \begin{itemize}
        \item Nonlinear dimensionality reduction technique for visualization of high-dimensional data.
    \end{itemize}
\end{itemize}

\subsection{Summary}

\begin{itemize}
    \item PCA is a powerful tool for dimensionality reduction, capturing the most significant variance in data.
    \item By transforming to a new set of uncorrelated variables, PCA simplifies the structure of data.
    \item Appropriate application of PCA requires careful consideration of data scaling, centering, and the interpretation of results.
    \item While PCA has limitations, it remains a fundamental technique in data analysis and machine learning.
\end{itemize}

\section{Clustering}

\textbf{Oversimplified TLDR:}
\begin{itemize}
    \item Clustering aims to discover inherent groupings in unlabeled data.
    \item \textbf{K-means Clustering:}
    \begin{itemize}
        \item Partitions data into $K$ non-overlapping clusters.
        \item Minimizes within-cluster variance by iteratively updating cluster assignments and centroids.
        \item Sensitive to the initial choice of centroids and the value of $K$.
    \end{itemize}
    \item \textbf{Hierarchical Clustering:}
    \begin{itemize}
        \item Builds a tree-like structure (dendrogram) representing data groupings at different levels.
        \item Does not require pre-specifying the number of clusters.
        \item Can be agglomerative (bottom-up) or divisive (top-down).
    \end{itemize}
    \item \textbf{Evaluation:}
    \begin{itemize}
        \item Silhouette score assesses the quality of clustering by measuring how similar an object is to its own cluster compared to other clusters.
        \item High silhouette scores indicate well-separated clusters.
    \end{itemize}
\end{itemize}

\subsection{Cluster Analysis}

\begin{itemize}
    \item Cluster analysis involves grouping data points such that points within a cluster are similar and points in different clusters are dissimilar.
    \item It is an unsupervised learning technique since it deals with unlabeled data.
    \item Choosing the appropriate number of clusters $K$ is a critical part of the analysis.
    \item Visualization can sometimes be more effective than clustering algorithms for identifying groupings.
\end{itemize}

\subsection{K-means Clustering}

\begin{itemize}
    \item K-means clustering partitions the data into $K$ clusters $C_1, C_2, \dots, C_K$ by minimizing the total within-cluster variance.
    \item The objective function to minimize is:
    \[
    \underset{C_1, \dots, C_K}{\text{minimize}} \sum_{k=1}^{K} W(C_k)
    \]
    where $W(C_k)$ measures the within-cluster variation.
    \item A common choice for $W(C_k)$ is the sum of squared distances between data points and the cluster centroid:
    \[
    W(C_k) = \sum_{\boldsymbol{x}_i \in C_k} \left\| \boldsymbol{x}_i - \boldsymbol{r}_k \right\|^2
    \]
    where $\boldsymbol{r}_k$ is the centroid of cluster $C_k$.
    \item The centroid $\boldsymbol{r}_k$ is calculated as the mean of all points in the cluster:
    \[
    \boldsymbol{r}_k = \frac{1}{|C_k|} \sum_{\boldsymbol{x}_i \in C_k} \boldsymbol{x}_i
    \]
\end{itemize}

\subsubsection{The K-means Algorithm}

\begin{enumerate}
    \item \textbf{Initialization:} Choose $K$ initial cluster centroids, possibly by selecting $K$ random data points.
    \item \textbf{Assignment Step:} Assign each data point to the nearest centroid:
    \[
    \text{Assign } \boldsymbol{x}_i \text{ to cluster } C_k \text{ where } k = \underset{j}{\arg\min} \left\| \boldsymbol{x}_i - \boldsymbol{r}_j \right\|^2
    \]
    \item \textbf{Update Step:} Recalculate the centroids based on the current cluster assignments:
    \[
    \boldsymbol{r}_k = \frac{1}{|C_k|} \sum_{\boldsymbol{x}_i \in C_k} \boldsymbol{x}_i
    \]
    \item \textbf{Convergence Check:} Repeat steps 2 and 3 until the centroids no longer change significantly or a maximum number of iterations is reached.
\end{enumerate}

\subsubsection{Convergence and Initialization}

\begin{itemize}
    \item The K-means algorithm is guaranteed to converge in a finite number of iterations since there are a finite number of possible cluster assignments.
    \item It may converge to a local minimum rather than the global minimum of the objective function.
    \item Multiple runs with different initial centroids can help find a better clustering solution.
\end{itemize}

\subsubsection{Factors Affecting K-means Clustering}

\begin{itemize}
    \item \textbf{Choice of $K$:} The number of clusters must be specified in advance, and different values can lead to different clusterings.
    \item \textbf{Scale of Variables:} Features with larger scales can dominate the distance calculations; standardization is often necessary.
    \item \textbf{Outliers:} Outliers can significantly affect the cluster centroids; consider removing or treating outliers.
    \item \textbf{Dimensionality:} High-dimensional data can make distance measures less meaningful; dimensionality reduction techniques like PCA may help.
\end{itemize}

\subsubsection{Evaluating Clustering Results}

\textbf{Silhouette Score:}

\begin{itemize}
    \item For each data point $\boldsymbol{x}_i$, calculate:
    \begin{itemize}
        \item \textbf{Mean Intra-cluster Distance:}
        \[
        a(\boldsymbol{x}_i) = \frac{1}{|C_k| - 1} \sum_{\boldsymbol{x}_j \in C_k, \boldsymbol{x}_j \neq \boldsymbol{x}_i} d(\boldsymbol{x}_i, \boldsymbol{x}_j)
        \]
        where $C_k$ is the cluster containing $\boldsymbol{x}_i$ and $d(\cdot, \cdot)$ is the distance measure.
        \item \textbf{Mean Nearest-cluster Distance:}
        \[
        b(\boldsymbol{x}_i) = \min_{C_l \neq C_k} \left( \frac{1}{|C_l|} \sum_{\boldsymbol{x}_j \in C_l} d(\boldsymbol{x}_i, \boldsymbol{x}_j) \right)
        \]
    \end{itemize}
    \item The silhouette score for $\boldsymbol{x}_i$ is:
    \[
    s(\boldsymbol{x}_i) = \frac{b(\boldsymbol{x}_i) - a(\boldsymbol{x}_i)}{\max \left\{ a(\boldsymbol{x}_i), b(\boldsymbol{x}_i) \right\}}
    \]
    \item The silhouette score ranges from $-1$ to $1$:
    \begin{itemize}
        \item $s(\boldsymbol{x}_i) \approx 1$: Data point is well matched to its own cluster and poorly matched to neighboring clusters.
        \item $s(\boldsymbol{x}_i) \approx 0$: Data point lies between clusters.
        \item $s(\boldsymbol{x}_i) \approx -1$: Data point may have been assigned to the wrong cluster.
    \end{itemize}
    \item The average silhouette score over all data points provides an overall measure of clustering quality.
\end{itemize}

\subsection{Hierarchical Clustering}

\begin{itemize}
    \item Hierarchical clustering builds a hierarchy of clusters without requiring a pre-specified number of clusters.
    \item The result is typically visualized using a \textbf{dendrogram}, which illustrates the arrangement of the clusters produced by either agglomerative or divisive methods.
\end{itemize}

\subsubsection{Agglomerative vs. Divisive Strategies}

\begin{itemize}
    \item \textbf{Agglomerative (Bottom-Up) Clustering:}
    \begin{itemize}
        \item Starts with each data point as a singleton cluster.
        \item Iteratively merges the two closest clusters until all points are in a single cluster.
    \end{itemize}
    \item \textbf{Divisive (Top-Down) Clustering:}
    \begin{itemize}
        \item Starts with all data points in one cluster.
        \item Iteratively splits clusters into smaller clusters based on dissimilarity.
    \end{itemize}
\end{itemize}

\subsubsection{Measuring Dissimilarity Between Clusters}

\begin{itemize}
    \item The choice of linkage criterion determines how the distance between clusters is calculated.
    \item \textbf{Single Linkage:}
    \[
    D(C_i, C_j) = \min \left\{ d(\boldsymbol{x}, \boldsymbol{y}) \mid \boldsymbol{x} \in C_i, \boldsymbol{y} \in C_j \right\}
    \]
    \item \textbf{Complete Linkage:}
    \[
    D(C_i, C_j) = \max \left\{ d(\boldsymbol{x}, \boldsymbol{y}) \mid \boldsymbol{x} \in C_i, \boldsymbol{y} \in C_j \right\}
    \]
    \item \textbf{Average Linkage:}
    \[
    D(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_{\boldsymbol{x} \in C_i} \sum_{\boldsymbol{y} \in C_j} d(\boldsymbol{x}, \boldsymbol{y})
    \]
    \item Common distance measures $d(\boldsymbol{x}, \boldsymbol{y})$ include Euclidean distance, Manhattan distance, etc.
\end{itemize}

\subsubsection{Dendrograms}

\begin{itemize}
    \item A dendrogram is a tree-like diagram that records the sequences of merges or splits.
    \item The vertical axis represents the distance or dissimilarity at which clusters are merged or split.
    \item By "cutting" the dendrogram at a particular height, we obtain a clustering corresponding to that level of dissimilarity.
\end{itemize}

\subsubsection{Interpreting Dendrograms}

\begin{itemize}
    \item Clusters joined at lower heights are more similar than those joined at higher heights.
    \item The dendrogram helps in deciding the number of clusters by visualizing where large increases in dissimilarity occur.
    \item It is important to note that proximity in the dendrogram does not always correspond to proximity in the original feature space.
\end{itemize}

\subsection{Soft vs. Hard Clustering}

\begin{itemize}
    \item \textbf{Hard Clustering:} Each data point is assigned to exactly one cluster (e.g., K-means, hierarchical clustering).
    \item \textbf{Soft Clustering:} Assigns a probability or degree of membership of each data point to clusters (e.g., Gaussian Mixture Models).
    \item Soft clustering provides more nuanced information about data point affiliations.
\end{itemize}

\subsection{Clustering as Data Reduction}

\begin{itemize}
    \item Clustering can be used to reduce the complexity of data by representing clusters with prototype points (e.g., centroids).
    \item This approach can simplify tasks like nearest-neighbor classification by reducing the number of comparisons.
    \item For example, instead of using all training data in K-nearest neighbors, one can use cluster centroids as representative points.
\end{itemize}

\subsection{Practical Considerations}

\begin{itemize}
    \item \textbf{Preprocessing:}
    \begin{itemize}
        \item Feature scaling is crucial, especially for distance-based clustering methods.
        \item Dimensionality reduction techniques (like PCA) can help mitigate the curse of dimensionality.
    \end{itemize}
    \item \textbf{Algorithm Selection:}
    \begin{itemize}
        \item The choice between K-means and hierarchical clustering depends on the data size and the desired clustering granularity.
        \item Hierarchical clustering is more computationally intensive but provides a full hierarchy of clusters.
    \end{itemize}
    \item \textbf{Validation:}
    \begin{itemize}
        \item Internal validation measures (e.g., silhouette score) help assess clustering quality without ground truth labels.
        \item External validation requires labeled data to compare clustering results against known classes.
    \end{itemize}
\end{itemize}

\section{Decision Trees}

\textbf{Oversimplified TLDR:}

\begin{itemize}
    \item Decision Trees are supervised learning algorithms used for both classification and regression tasks.
    \item They split the data into subsets based on the value of input features, creating a tree-like model of decisions.
    \item \textbf{Key Characteristics:}
    \begin{itemize}
        \item Easy to interpret and visualize; can be visualized as a flowchart.
        \item Handle both numerical and categorical data.
        \item Non-parametric model that can capture complex, non-linear relationships.
    \end{itemize}
    \item \textbf{Limitations:}
    \begin{itemize}
        \item Prone to overfitting if not properly pruned.
        \item Can create biased trees if some classes dominate.
        \item Sensitive to small changes in the data (unstable).
    \end{itemize}
\end{itemize}

\subsection{Introduction}

\begin{itemize}
    \item A Decision Tree is a flowchart-like structure where internal nodes represent tests on features, branches represent the outcome of the test, and leaf nodes represent the final output (class label or continuous value).
    \item The model makes decisions by recursively partitioning the feature space into regions where the predicted value is homogeneous.
    \item The process continues until a stopping criterion is met (e.g., maximum depth, minimum number of samples in a node).
\end{itemize}

\subsection{How Decision Trees Work}

\subsubsection{Classification Example}

\begin{itemize}
    \item Consider a dataset with two features, $X_1$ and $X_2$, and two classes.
    \item The goal is to classify new data points by partitioning the feature space using simple decision rules based on feature thresholds.
    \item For instance:
    \begin{enumerate}
        \item If $X_2 > 10$, classify as Class A.
        \item Else, if $X_1 > 5$, classify as Class B.
        \item Else, classify as Class A.
    \end{enumerate}
    \item This forms a tree structure where each node represents a decision based on a feature, and each leaf node represents a class label.
    \item The feature space is partitioned into regions corresponding to these rules.
\end{itemize}

\subsubsection{Regression Example}

\begin{itemize}
    \item In regression trees, the goal is to predict a continuous target variable.
    \item Example: Predicting a baseball player's salary based on years of experience ($X_1$) and number of hits last year ($X_2$).
    \item The tree partitions the feature space and assigns the average target value (salary) of the training samples in each region as the prediction.
    \item For instance:
    \begin{enumerate}
        \item If $X_1 > 4.5$, predict the average salary of players with more than 4.5 years of experience.
        \item Else, predict the average salary of players with 4.5 or fewer years of experience.
    \end{enumerate}
    \item This results in a piecewise constant prediction function.
\end{itemize}

\subsection{Decision Tree Terminology}

\begin{itemize}
    \item \textbf{Root Node:} The topmost node of the tree, representing the entire dataset.
    \item \textbf{Internal Nodes:} Nodes that represent tests on features and have child nodes.
    \item \textbf{Leaf Nodes (Terminal Nodes):} Nodes that represent the final output; they do not have any children.
    \item \textbf{Branches (Edges):} Connections between nodes, representing the outcome of a test.
    \item \textbf{Splitting:} The process of dividing a node into two or more sub-nodes.
    \item \textbf{Parent and Child Nodes:} A node that is divided into sub-nodes is a parent, and the resulting nodes are children.
    \item \textbf{Subtree:} A portion of the tree consisting of a node and its descendants.
\end{itemize}

\subsection{Training a Decision Tree}

\begin{itemize}
    \item Building a decision tree involves selecting the best splits at each node based on a certain criterion.
    \item The goal is to create pure nodes where the target variable is as homogeneous as possible.
    \item Since finding the optimal tree is computationally infeasible (NP-complete problem), we use a greedy algorithm to build the tree recursively.
\end{itemize}

\subsubsection{The Training Algorithm}

\begin{enumerate}
    \item \textbf{For each node:}
    \begin{enumerate}
        \item Evaluate all possible splits for each feature.
        \item Use a criterion (e.g., reduction in impurity) to select the best split.
        \item Split the node into child nodes based on the best split.
    \end{enumerate}
    \item \textbf{Recursively repeat} the process for each child node until a stopping condition is met (e.g., maximum depth, minimum number of samples).
\end{enumerate}

\subsubsection{Evaluating the Quality of a Split}

\paragraph{For Regression Trees}

\begin{itemize}
    \item The quality of a split is evaluated using the \textbf{Residual Sum of Squares (RSS)}.
    \item For a split $s$ that partitions the data at node $t$ into regions $R_1^{(s)}$ and $R_2^{(s)}$, the RSS is computed as:
    \[
    \mathrm{RSS} = \sum_{i: x_i \in R_1^{(s)}} (y_i - \bar{y}_{R_1^{(s)}})^2 + \sum_{i: x_i \in R_2^{(s)}} (y_i - \bar{y}_{R_2^{(s)}})^2
    \]
    where $\bar{y}_{R_1^{(s)}}$ and $\bar{y}_{R_2^{(s)}}$ are the mean target values in regions $R_1^{(s)}$ and $R_2^{(s)}$, respectively.
    \item The split that results in the lowest RSS is selected.
\end{itemize}

\paragraph{For Classification Trees}

\begin{itemize}
    \item The quality of a split is evaluated using an \textbf{impurity measure} (e.g., Gini impurity, entropy).
    \item For a node $t$ with $N_t$ samples, and a split $s$ that creates child nodes $t_L$ and $t_R$:
    \begin{itemize}
        \item Compute the impurity of each child node: $\Phi(t_L)$ and $\Phi(t_R)$.
        \item Compute the weighted average impurity:
        \[
        \Phi_{\text{split}} = \frac{N_{t_L}}{N_t} \Phi(t_L) + \frac{N_{t_R}}{N_t} \Phi(t_R)
        \]
    \item The split that minimizes $\Phi_{\text{split}}$ is selected.
    \end{itemize}
    \item Alternatively, compute the \textbf{information gain}:
    \[
    \text{Information Gain} = \Phi(t) - \Phi_{\text{split}}
    \]
    \item The split that maximizes the information gain is selected.
\end{itemize}

\subsection{Impurity Measures}

\begin{itemize}
    \item An impurity measure quantifies the homogeneity of the target variable within a node.
    \item Common impurity measures for classification trees include:
    \begin{enumerate}
        \item \textbf{Gini Impurity:}
        \[
        G(t) = 1 - \sum_{k=1}^K p_k^2
        \]
        where $p_k$ is the proportion of samples of class $k$ in node $t$, and $K$ is the number of classes.
        \item \textbf{Entropy (Information Gain):}
        \[
        H(t) = -\sum_{k=1}^K p_k \log_2 p_k
        \]
        \item \textbf{Classification Error:}
        \[
        E(t) = 1 - \max_k p_k
        \]
    \end{enumerate}
    \item These measures are maximized when the classes are equally mixed and minimized when the node is pure.
\end{itemize}

\subsubsection{Gini Impurity}

\begin{itemize}
    \item Gini impurity measures the probability of misclassifying a randomly chosen sample from the node if it were labeled according to the distribution of labels in the node.
    \item For binary classification (two classes), the Gini impurity simplifies to:
    \[
    G(t) = 2 p (1 - p)
    \]
    where $p$ is the proportion of one of the classes.
    \item Gini impurity ranges between 0 (pure node) and 0.5 (maximum impurity for binary classification).
\end{itemize}

\subsubsection{Entropy}

\begin{itemize}
    \item Entropy measures the expected amount of information needed to classify a randomly drawn sample.
    \item It reaches its maximum when the classes are equally likely (most uncertain) and minimum when the node is pure.
    \item For binary classification, entropy ranges between 0 and 1.
\end{itemize}

\subsubsection{Classification Error}

\begin{itemize}
    \item Classification error measures the fraction of samples that do not belong to the majority class in the node.
    \item It is less sensitive to changes in the node probabilities compared to Gini impurity and entropy.
    \item Due to its less sensitivity, it is less suitable for tree building but can be used for pruning.
\end{itemize}

\subsection{Advantages and Disadvantages}

\subsubsection{Advantages}

\begin{itemize}
    \item \textbf{Interpretability:} Decision trees are easy to interpret and explain, making them suitable for situations where transparency is important.
    \item \textbf{Versatility:} Can handle both numerical and categorical data.
    \item \textbf{Non-parametric:} Do not assume any underlying distribution, can capture non-linear relationships.
    \item \textbf{Efficiency:} Require relatively little data preparation, and the prediction time is fast, proportional to the depth of the tree.
\end{itemize}

\subsubsection{Disadvantages}

\begin{itemize}
    \item \textbf{Overfitting:} Decision trees can create overly complex trees that do not generalize well to unseen data.
    \item \textbf{Instability:} Small changes in the data can lead to different splits and completely different trees.
    \item \textbf{Bias:} Trees can be biased towards features with more levels (categorical features with many categories).
\end{itemize}

\subsection{Practical Considerations}

\begin{itemize}
    \item \textbf{Stopping Criteria:} To prevent overfitting, consider setting parameters like maximum depth, minimum number of samples per leaf, or minimum impurity decrease.
    \item \textbf{Pruning:} Post-pruning can simplify the tree by removing branches that have little power in predicting the target variable.
    \item \textbf{Feature Selection:} Decision trees perform implicit feature selection; however, they may favor features with more levels. Consider preprocessing steps to mitigate bias.
    \item \textbf{Ensemble Methods:} Combining multiple trees (e.g., Random Forests, Gradient Boosting) can improve predictive performance and reduce overfitting.
\end{itemize}

\subsection{Decision Tree Structures}

\subsubsection{Binary vs. Multi-way Splits}

\begin{itemize}
    \item \textbf{Binary Trees:} Each internal node splits the data into two subsets based on a feature threshold. Most common and preferred due to their simplicity.
    \item \textbf{Multi-way Splits:} Nodes can split data into more than two subsets, which can be useful for categorical features with multiple levels but may lead to more complex trees.
\end{itemize}

\subsubsection{Feature Types}

\begin{itemize}
    \item Decision trees can handle both \textbf{continuous} (numerical) and \textbf{categorical} features.
    \item For continuous features, splits are based on thresholds (e.g., $X_j \leq s$).
    \item For categorical features, splits can be based on equality or membership in a subset of categories.
\end{itemize}

\subsection{Building a Decision Tree}

\begin{enumerate}
    \item \textbf{Select the Best Split:}
    \begin{itemize}
        \item For each feature, evaluate all possible splits.
        \item For continuous features, consider all possible thresholds.
        \item For categorical features, consider all possible subsets.
        \item Use the impurity measure to select the split that best separates the data.
    \end{itemize}
    \item \textbf{Split the Node:}
    \begin{itemize}
        \item Partition the data into child nodes based on the selected split.
    \end{itemize}
    \item \textbf{Repeat Recursively:}
    \begin{itemize}
        \item Apply the same process to each child node.
        \item Continue until a stopping criterion is met.
    \end{itemize}
    \item \textbf{Assign Predictions:}
    \begin{itemize}
        \item For classification, assign the majority class in the leaf node.
        \item For regression, assign the mean target value in the leaf node.
    \end{itemize}
\end{enumerate}

\subsection{Interpretability and Efficiency}

\subsubsection{Interpretability}

\begin{itemize}
    \item Decision trees are highly interpretable due to their structure resembling human decision-making processes.
    \item The set of decision rules can be easily extracted and understood.
    \item This transparency makes them suitable for applications requiring explainability.
\end{itemize}

\subsubsection{Efficiency}

\begin{itemize}
    \item \textbf{Memory Efficiency:} Only the tree structure needs to be stored, not the entire dataset.
    \item \textbf{Prediction Time:} Making a prediction involves traversing the tree from root to leaf, which has a time complexity of $O(\log_2 L)$ for a balanced tree with $L$ leaves.
\end{itemize}

\section{Decision Trees (continued) and Ensemble Methods}

\textbf{Oversimplified TLDR:}

\begin{itemize}
    \item \textbf{Decision Trees:}
    \begin{itemize}
        \item Hierarchical models that split data based on feature values.
        \item Prone to overfitting; can capture noise in the data.
        \item Sensitive to small variations in data (high variance).
        \item Not robust to rotations; scaling and shifting are acceptable.
        \item Feature importance is derived from the top splits in the tree.
    \end{itemize}
    \item \textbf{Ensemble Methods:}
    \begin{itemize}
        \item Combine multiple models to improve overall performance.
        \item Reduce variance (e.g., Bagging, Random Forests).
        \item Reduce bias (e.g., Boosting).
        \item Benefit from the wisdom of crowds under certain conditions.
    \end{itemize}
\end{itemize}

\subsection{Decision Trees}

\begin{itemize}
    \item Decision Trees split data recursively based on feature values to predict the target variable.
    \item The structure consists of nodes (decision points) and leaves (predictions).
\end{itemize}

\subsubsection{Feature Importance}

\begin{itemize}
    \item Features used at the top levels of the tree are considered more globally important.
    \item Some features may not be used at all, effectively performing feature selection.
\end{itemize}

\subsubsection{Sensitivity to Data Transformations}

\begin{itemize}
    \item \textbf{Rotation:} Trees are sensitive to rotations of the feature space.
    \item \textbf{Scaling:} Trees are invariant to scaling of features.
    \item \textbf{Shifting:} Trees are invariant to shifting (adding constants to features).
\end{itemize}

\subsubsection{Instability and Variance}

\begin{itemize}
    \item Decision Trees can be unstable; small variations in data can lead to different trees.
    \item High variance makes trees sensitive to noise and prone to overfitting.
\end{itemize}

\subsubsection{Handling Missing Features - Surrogate Splits}

\begin{itemize}
    \item Missing values are common in real-world datasets.
    \item \textbf{Surrogate splits} are used when the best splitting feature is missing for some data points.
    \item A surrogate feature is selected that closely mimics the original split.
    \item This helps to handle missing values during both training and prediction.
\end{itemize}

\subsection{Building a Decision Tree}

\begin{itemize}
    \item Start with the entire dataset at the root node.
    \item Recursively split the data:
    \begin{itemize}
        \item Try all possible splits on all features.
        \item Use a criterion (e.g., Gini impurity, entropy) to evaluate splits.
        \item Choose the split that best reduces impurity.
    \end{itemize}
    \item Continue splitting until a stopping condition is met.
\end{itemize}

\subsubsection{Stopping Conditions}

\begin{itemize}
    \item \textbf{Purity:} Stop when nodes are pure (all samples belong to one class).
    \item \textbf{Impurity Reduction:} Stop when no split reduces impurity.
    \item \textbf{Minimum Samples:} Stop when the number of samples in a node is below a threshold.
    \item \textbf{Maximum Depth:} Limit the depth of the tree.
    \item \textbf{Maximum Nodes:} Limit the total number of nodes in the tree.
\end{itemize}

\subsection{Bias and Variance in Decision Trees}

\begin{itemize}
    \item Decision Trees can achieve low bias but often have high variance.
    \item Overfitting occurs when the tree captures noise instead of underlying patterns.
\end{itemize}

\subsubsection{Reducing Overfitting}

\begin{itemize}
    \item \textbf{Early Stopping:}
    \begin{itemize}
        \item Limit tree growth using stopping conditions.
        \item Prevents the tree from becoming too complex.
    \end{itemize}
    \item \textbf{Pruning (Post-Pruning):}
    \begin{itemize}
        \item Grow a full tree and then remove branches that do not provide significant benefit.
        \item Compare subtrees based on a cost-complexity metric.
        \item Prune subtrees if the simplified tree performs as well.
    \end{itemize}
\end{itemize}

\subsection{Advantages and Disadvantages of Decision Trees}

\textbf{Advantages:}

\begin{itemize}
    \item \textbf{Interpretability:} Easy to understand and explain.
    \item \textbf{Versatility:} Can handle both numerical and categorical data.
    \item \textbf{Feature Selection:} Performs implicit feature selection.
    \item \textbf{Invariance:} Not affected by scaling or shifting of data.
\end{itemize}

\textbf{Disadvantages:}

\begin{itemize}
    \item \textbf{Overfitting:} Prone to overfitting without proper tuning.
    \item \textbf{Unstable:} Sensitive to small changes in data (high variance).
    \item \textbf{Lack of Smoothness:} Predictions are not smooth; decision boundaries are axis-aligned.
    \item \textbf{Rotation Sensitivity:} Sensitive to rotations in the feature space.
\end{itemize}

\subsection{Bias-Variance Tradeoff}

\begin{itemize}
    \item Decision Trees have low bias but high variance.
    \item Controlling tree complexity can help balance the tradeoff.
    \item Ensemble methods can reduce variance and improve generalization.
\end{itemize}

\section{Ensemble Methods}

\subsection{Wisdom of Crowds}

\begin{itemize}
    \item Aggregating predictions from multiple models can improve accuracy.
    \item Underlying principle: Errors from individual models may cancel out.
    \item Effective when models are diverse and errors are uncorrelated.
\end{itemize}

\subsection{Law of Large Numbers}

\begin{itemize}
    \item The average of a large number of independent random variables tends toward the expected value.
    \item In ensembles, averaging predictions reduces variance.
    \item Mathematically:
    \[
    \frac{1}{m} \sum_{i=1}^{m} X_{i} \rightarrow \mathbb{E}[X] \quad \text{as} \quad m \rightarrow \infty
    \]
    where \( X_{i} \) are independent and identically distributed random variables.
\end{itemize}

\subsection{Voting Methods}

\subsubsection{Hard Voting (Majority Rule)}

\begin{itemize}
    \item Each base learner makes a class prediction.
    \item The final prediction is the class that receives the majority of votes.
    \item Suitable when base learners output class labels.
\end{itemize}

\subsubsection{Soft Voting}

\begin{itemize}
    \item Base learners provide class probabilities.
    \item Probabilities are averaged across models.
    \item The final prediction is the class with the highest average probability.
    \item Often performs better than hard voting.
\end{itemize}

\subsection{Reducing Variance with Ensembles}

\begin{itemize}
    \item Combining multiple models can reduce the variance of predictions.
    \item The base learners should be diverse and make uncorrelated errors.
    \item Independence among base learners is ideal but difficult to achieve.
\end{itemize}

\subsection{Introducing Diversity in Ensembles}

\subsubsection{Diversity in Predictors}

\begin{itemize}
    \item Use different types of models (heterogeneous ensemble).
    \item Different algorithms may capture different patterns in the data.
    \item Example: Combining decision trees, support vector machines, and neural networks.
\end{itemize}

\subsubsection{Diversity in Training Data}

\begin{itemize}
    \item Use the same model type but train on different subsets of data.
    \item Techniques like bootstrapping create varied training sets.
    \item Helps in creating independent base learners.
\end{itemize}

\subsection{Bootstrapping}

\begin{itemize}
    \item Sampling with replacement from the original dataset to create multiple bootstrap samples.
    \item Each sample is used to train a separate base learner.
    \item Leads to diversity in the training data.
\end{itemize}

\subsection{Popular Ensemble Methods}

\begin{itemize}
    \item \textbf{Bagging (Bootstrap Aggregating):}
    \begin{itemize}
        \item Train multiple models on bootstrap samples.
        \item Average predictions to reduce variance.
        \item Particularly effective with high-variance models like decision trees.
    \end{itemize}
    \item \textbf{Random Forests:}
    \begin{itemize}
        \item An extension of bagging applied to decision trees.
        \item Introduces randomness by selecting a random subset of features at each split.
        \item Further reduces correlation between base learners.
    \end{itemize}
    \item \textbf{Boosting:}
    \begin{itemize}
        \item Sequentially trains models, each focusing on correcting errors of the previous one.
        \item Aims to reduce both bias and variance.
        \item Examples include AdaBoost and Gradient Boosting.
    \end{itemize}
    \item \textbf{Stacking:}
    \begin{itemize}
        \item Combines predictions from multiple models using a meta-learner.
        \item The meta-learner learns how to best combine base learners' predictions.
    \end{itemize}
\end{itemize}

\subsection{Conditions for Effective Ensembles}

\begin{itemize}
    \item Base learners should have low bias.
    \item Errors among base learners should be uncorrelated.
    \item Diversity can be introduced through different models or data variations.
\end{itemize}

\subsection{Limitations of Ensembles}

\begin{itemize}
    \item Increased computational complexity.
    \item May reduce interpretability compared to single models.
    \item Requires careful tuning to balance bias and variance.
\end{itemize}

\section{Conclusion}

\begin{itemize}
    \item Decision Trees are simple and interpretable but prone to overfitting.
    \item Ensemble methods improve performance by combining multiple models.
    \item Techniques like bagging and boosting leverage different strategies to reduce variance and bias.
    \item The effectiveness of ensembles depends on the diversity and independence of base learners.
\end{itemize}

\section{Ensemble Methods (continued): Bagging, Random Forests, and Boosting}

\textbf{Oversimplified TLDR:}
\begin{itemize}
    \item \textbf{Ensemble Methods} combine multiple models to improve performance and robustness.
    \item \textbf{Bagging (Bootstrap Aggregation):}
    \begin{itemize}
        \item Reduces variance by training multiple models on different bootstrapped subsets of data.
        \item Aggregates predictions via averaging (regression) or majority voting (classification).
        \item Particularly effective for high-variance, low-bias models like decision trees.
    \end{itemize}
    \item \textbf{Random Forests:}
    \begin{itemize}
        \item An extension of bagging using decision trees.
        \item Introduces additional randomness by selecting random subsets of features at each split.
        \item Further reduces variance and combats overfitting.
    \end{itemize}
    \item \textbf{Boosting:}
    \begin{itemize}
        \item Reduces bias by sequentially training models that focus on correcting previous errors.
        \item Models are weighted based on their performance.
        \item Aggregates predictions using weighted voting or summation.
    \end{itemize}
\end{itemize}

\subsection{Introduction to Ensemble Methods}

\begin{itemize}
    \item \textbf{Ensemble Methods} aim to improve the performance of machine learning models by combining multiple learners.
    \item The key idea is that a group of weak learners can come together to form a strong learner.
    \item Ensemble methods can be categorized based on whether they primarily reduce variance or bias.
\end{itemize}

\subsection{Reducing Variance with Ensemble Methods}

\begin{itemize}
    \item Variance refers to the model's sensitivity to fluctuations in the training data.
    \item High-variance models, like decision trees, can benefit from ensemble methods that reduce variance.
    \item \textbf{Key Strategy:} Combine multiple independent models to average out errors.
\end{itemize}

\subsubsection{Need for Diversity}

\begin{itemize}
    \item For an ensemble to effectively reduce variance, the base learners should be diverse and make uncorrelated errors.
    \item Diversity can be introduced by:
    \begin{itemize}
        \item \textbf{Using Different Predictors:} Training different types of classifiers on the same data.
        \item \textbf{Varying Training Data:} Training the same classifier type on different subsets of the data.
    \end{itemize}
\end{itemize}

\subsection{Bagging (Bootstrap Aggregation)}

\begin{itemize}
    \item \textbf{Bagging} stands for \textbf{Bootstrap Aggregating}.
    \item It reduces variance by creating multiple versions of a predictor and using them to get an aggregated predictor.
\end{itemize}

\subsubsection{Training Procedure}

\begin{enumerate}
    \item Generate $m$ bootstrapped datasets $\{\mathcal{D}_1, \mathcal{D}_2, \dots, \mathcal{D}_m\}$ from the original training data $\mathcal{D}$.
    \begin{itemize}
        \item Each bootstrapped dataset is created by sampling $n$ instances from $\mathcal{D}$ with replacement.
    \end{itemize}
    \item Train a separate base learner $h_i$ on each bootstrapped dataset $\mathcal{D}_i$.
\end{enumerate}

\subsubsection{Prediction Procedure}

\begin{itemize}
    \item For regression:
    \[
    \hat{f}_{\text{bag}}(\mathbf{x}) = \frac{1}{m} \sum_{i=1}^{m} h_i(\mathbf{x})
    \]
    \item For classification:
    \[
    \hat{y}_{\text{bag}} = \text{MajorityVote}\left\{ h_1(\mathbf{x}), h_2(\mathbf{x}), \dots, h_m(\mathbf{x}) \right\}
    \]
\end{itemize}

\subsubsection{Out-of-Bag (OOB) Error Estimation}

\begin{itemize}
    \item Approximately $37\%$ of the original data are not included in each bootstrapped dataset (since $(1 - \frac{1}{n})^n \approx \frac{1}{e} \approx 0.37$).
    \item These \textbf{Out-of-Bag} samples can be used to estimate the prediction error without the need for a separate validation set.
    \item \textbf{Procedure:}
    \begin{enumerate}
        \item For each instance, aggregate the predictions from the models where that instance was not included in the training data.
        \item Compute the OOB error as the average error across all instances.
    \end{enumerate}
\end{itemize}

\subsubsection{Advantages of Bagging}

\begin{itemize}
    \item Reduces variance without increasing bias significantly.
    \item Easy to implement and parallelize.
    \item Provides an unbiased estimation of the generalization error via OOB error.
    \item Improves stability and reduces overfitting for high-variance models.
\end{itemize}

\subsection{Random Forests}

\begin{itemize}
    \item \textbf{Random Forests} are an extension of bagging, specifically applied to decision trees.
    \item They introduce additional randomness in the model-building process.
\end{itemize}

\subsubsection{Training Procedure}

\begin{enumerate}
    \item Generate $m$ bootstrapped datasets from the original data.
    \item For each node in a decision tree:
    \begin{itemize}
        \item Randomly select $k$ features from the total $p$ features.
        \item Determine the best split among the selected $k$ features.
    \end{itemize}
    \item Train a full decision tree on each bootstrapped dataset using the modified splitting criterion.
\end{enumerate}

\subsubsection{Hyperparameters}

\begin{itemize}
    \item Number of trees $m$.
    \item Number of features to consider at each split $k$.
    \begin{itemize}
        \item For classification: $k = \sqrt{p}$.
        \item For regression: $k = \frac{p}{3}$.
    \end{itemize}
\end{itemize}

\subsubsection{Advantages of Random Forests}

\begin{itemize}
    \item Further reduces variance compared to bagging.
    \item Handles high-dimensional data well.
    \item Provides estimates of feature importance.
    \item Less prone to overfitting due to feature randomness.
\end{itemize}

\subsection{Boosting}

\begin{itemize}
    \item \textbf{Boosting} aims to reduce bias by combining weak learners sequentially.
    \item Each new model focuses on the errors of the previous models.
    \item Particularly useful when the base learner is simple and exhibits high bias.
\end{itemize}

\subsubsection{AdaBoost (Adaptive Boosting)}

\begin{itemize}
    \item Commonly used for classification problems.
    \item Adjusts the weights of training instances based on classification errors.
\end{itemize}

\paragraph{Training Procedure}

\begin{enumerate}
    \item Initialize weights $w_i^{(1)} = \frac{1}{n}$ for $i = 1, 2, \dots, n$.
    \item For $c = 1$ to $M$ (number of iterations):
    \begin{enumerate}
        \item Train a weak learner $h_c(\mathbf{x})$ using weights $w_i^{(c)}$.
        \item Compute the weighted error:
        \[
        \epsilon_c = \frac{\sum_{i=1}^n w_i^{(c)} \mathbb{I}\left( h_c(\mathbf{x}_i) \neq y_i \right)}{\sum_{i=1}^n w_i^{(c)}}
        \]
        \item Compute the model's weight (amount of say):
        \[
        \alpha_c = \frac{1}{2} \ln\left( \frac{1 - \epsilon_c}{\epsilon_c} \right)
        \]
        \item Update the instance weights:
        \[
        w_i^{(c+1)} = w_i^{(c)} \times \begin{cases}
            e^{-\alpha_c}, & \text{if } h_c(\mathbf{x}_i) = y_i \\
            e^{\alpha_c}, & \text{if } h_c(\mathbf{x}_i) \neq y_i \\
        \end{cases}
        \]
        \item Normalize the weights so that $\sum_{i=1}^n w_i^{(c+1)} = 1$.
    \end{enumerate}
\end{enumerate}

\paragraph{Prediction Procedure}

\begin{itemize}
    \item The final prediction is a weighted majority vote:
    \[
    H(\mathbf{x}) = \text{sign}\left( \sum_{c=1}^M \alpha_c h_c(\mathbf{x}) \right)
    \]
\end{itemize}

\subsubsection{Incorporating Weights into Training}

\begin{itemize}
    \item Weights can be incorporated by:
    \begin{itemize}
        \item Sampling training instances according to their weights.
        \item Modifying the loss function to account for instance weights.
        \item Adjusting the impurity measures in decision trees using weighted counts.
    \end{itemize}
\end{itemize}

\subsubsection{Gradient Boosting}

\begin{itemize}
    \item A generalization of boosting for both regression and classification.
    \item Models are trained to predict the residuals (errors) of the previous models.
\end{itemize}

\paragraph{Training Procedure}

\begin{enumerate}
    \item Initialize the model with a constant value:
    \[
    F_0(\mathbf{x}) = \arg\min_{\gamma} \sum_{i=1}^n L(y_i, \gamma)
    \]
    \item For $m = 1$ to $M$ (number of iterations):
    \begin{enumerate}
        \item Compute the pseudo-residuals:
        \[
        r_i^{(m)} = -\left[ \frac{\partial L(y_i, F(\mathbf{x}_i))}{\partial F(\mathbf{x}_i)} \right]_{F(\mathbf{x}) = F_{m-1}(\mathbf{x})}
        \]
        \item Fit a base learner $h_m(\mathbf{x})$ to the pseudo-residuals.
        \item Update the model:
        \[
        F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \nu h_m(\mathbf{x})
        \]
        \item $\nu$ is the learning rate (typically between $0.01$ and $0.1$).
    \end{enumerate}
\end{enumerate}

\paragraph{Advantages of Gradient Boosting}

\begin{itemize}
    \item Can optimize arbitrary differentiable loss functions.
    \item Effective for both regression and classification.
    \item Provides state-of-the-art results on many problems.
\end{itemize}

\subsection{Bagging vs. Boosting}

\begin{itemize}
    \item \textbf{Bagging:}
    \begin{itemize}
        \item Reduces variance.
        \item Models are trained independently (can be parallelized).
        \item Effective for high-variance, low-bias models.
    \end{itemize}
    \item \textbf{Boosting:}
    \begin{itemize}
        \item Reduces bias.
        \item Models are trained sequentially (cannot be fully parallelized).
        \item Effective for low-variance, high-bias models.
        \item Can be prone to overfitting, especially with noisy data.
    \end{itemize}
\end{itemize}

\subsection{Stacking}

\begin{itemize}
    \item \textbf{Stacking} involves training a meta-learner to combine the predictions of several base learners.
    \item Base learners are trained on the original dataset.
    \item The meta-learner is trained on the outputs of the base learners.
\end{itemize}

\subsubsection{Procedure}

\begin{enumerate}
    \item Split the training data into two sets.
    \item Train base learners on the first set.
    \item Generate predictions for the second set using the trained base learners.
    \item Train a meta-learner on the predictions from the base learners.
\end{enumerate}

\subsubsection{Advantages of Stacking}

\begin{itemize}
    \item Can model complex relationships between base learners.
    \item Often achieves better performance than individual models.
\end{itemize}

\subsection{Practical Considerations}

\begin{itemize}
    \item \textbf{Choice of Ensemble Method:}
    \begin{itemize}
        \item Depends on the problem, data size, and computational resources.
        \item Bagging is suitable when variance is high.
        \item Boosting is suitable when bias is high.
    \end{itemize}
    \item \textbf{Computational Efficiency:}
    \begin{itemize}
        \item Bagging and Random Forests can be parallelized.
        \item Boosting requires sequential training.
    \end{itemize}
    \item \textbf{Overfitting:}
    \begin{itemize}
        \item Boosting can overfit on noisy datasets.
        \item Regularization techniques and early stopping can mitigate overfitting.
    \end{itemize}
\end{itemize}

\section{Support Vector Machines (SVM)}

\textbf{Oversimplified TLDR:}
\begin{itemize}
    \item SVM aims to find the optimal hyperplane that separates classes by maximizing the margin between them.
    \item \textbf{Hard-Margin SVM:}
    \begin{itemize}
        \item Assumes data is perfectly linearly separable.
        \item Maximizes the minimum distance (margin) to the closest data points from each class.
        \item Sensitive to outliers and cannot handle misclassifications.
    \end{itemize}
    \item \textbf{Soft-Margin SVM:}
    \begin{itemize}
        \item Allows some misclassifications to achieve better generalization.
        \item Introduces slack variables and a regularization parameter $C$ to control the trade-off between maximizing margin and minimizing classification error.
        \item More robust to noisy data and outliers.
    \end{itemize}
    \item \textbf{Kernel Trick:}
    \begin{itemize}
        \item Projects data into higher-dimensional space to handle non-linear separations.
        \item Uses kernel functions to compute inner products in transformed space without explicit mapping.
        \item Common kernels: Linear, Polynomial, Radial Basis Function (RBF), Sigmoid.
    \end{itemize}
\end{itemize}

\subsection{Introduction}

\begin{itemize}
    \item Support Vector Machines (SVM) are supervised learning models used for classification and regression tasks.
    \item SVM aims to find a hyperplane that best separates classes in the feature space.
    \item The optimal hyperplane is the one that maximizes the margin between the classes.
    \item Key concepts:
    \begin{itemize}
        \item \textbf{Margin:} The distance between the hyperplane and the nearest data points from each class.
        \item \textbf{Support Vectors:} The data points that lie closest to the hyperplane and influence its position.
    \end{itemize}
\end{itemize}

\subsection{Hard-Margin SVM}

\subsubsection{Assumptions and Definitions}

\begin{itemize}
    \item Applicable when data is linearly separable.
    \item Goal: Find a hyperplane that separates the classes with maximum margin.
    \item Linear classifier is defined as:
    \[
    f(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b
    \]
    where:
    \begin{itemize}
        \item $\mathbf{w}$ is the weight vector (normal to the hyperplane).
        \item $b$ is the bias term.
    \end{itemize}
    \item Decision rule:
    \[
    \text{Predict class } \begin{cases}
    +1 & \text{if } f(\mathbf{x}) \geq 0 \\
    -1 & \text{if } f(\mathbf{x}) < 0
    \end{cases}
    \]
\end{itemize}

\subsubsection{Optimization Problem}

\begin{itemize}
    \item The margin is defined as $\dfrac{2}{\|\mathbf{w}\|}$.
    \item To maximize the margin, we minimize $\|\mathbf{w}\|$ subject to correct classification.
    \item Constraints for all training samples $(\mathbf{x}_i, y_i)$:
    \[
    y_i (\mathbf{w}^\top \mathbf{x}_i + b) \geq 1
    \]
    \item The optimization problem becomes:
    \[
    \begin{aligned}
    & \underset{\mathbf{w}, b}{\text{minimize}} && \frac{1}{2} \|\mathbf{w}\|^2 \\
    & \text{subject to} && y_i (\mathbf{w}^\top \mathbf{x}_i + b) \geq 1, \quad \forall i
    \end{aligned}
    \]
\end{itemize}

\subsubsection{Support Vectors}

\begin{itemize}
    \item Support vectors are the data points that lie on the margin boundaries (i.e., satisfy $y_i (\mathbf{w}^\top \mathbf{x}_i + b) = 1$).
    \item These points directly influence the position and orientation of the hyperplane.
    \item Data points further away from the hyperplane do not affect the solution.
\end{itemize}

\subsection{Soft-Margin SVM}

\subsubsection{Motivation}

\begin{itemize}
    \item Real-world data is often not perfectly linearly separable.
    \item Hard-margin SVM cannot handle misclassifications or noisy data.
    \item Soft-margin SVM introduces slack variables to allow some misclassifications.
\end{itemize}

\subsubsection{Mathematical Formulation}

\begin{itemize}
    \item Introduce slack variables $\xi_i \geq 0$ to allow violations of the margin constraints.
    \item Modified constraints:
    \[
    y_i (\mathbf{w}^\top \mathbf{x}_i + b) \geq 1 - \xi_i
    \]
    \item The optimization problem becomes:
    \[
    \begin{aligned}
    & \underset{\mathbf{w}, b, \boldsymbol{\xi}}{\text{minimize}} && \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i \\
    & \text{subject to} && y_i (\mathbf{w}^\top \mathbf{x}_i + b) \geq 1 - \xi_i, \quad \forall i \\
    &&& \xi_i \geq 0, \quad \forall i
    \end{aligned}
    \]
    where:
    \begin{itemize}
        \item $C > 0$ is the regularization parameter controlling the trade-off between margin maximization and classification error.
    \end{itemize}
\end{itemize}

\subsubsection{Regularization Parameter $C$}

\begin{itemize}
    \item A large $C$ assigns a higher penalty to misclassifications, leading to a smaller margin.
    \item A small $C$ allows more misclassifications, leading to a larger margin.
    \item $C$ controls the bias-variance trade-off:
    \begin{itemize}
        \item High $C$: Low bias, high variance.
        \item Low $C$: High bias, low variance.
    \end{itemize}
\end{itemize}

\subsection{Non-linear SVM and the Kernel Trick}

\subsubsection{Feature Transformation}

\begin{itemize}
    \item Linear SVMs cannot handle non-linearly separable data in the original feature space.
    \item Idea: Map data to a higher-dimensional feature space where it becomes linearly separable.
    \item Mapping function $\phi: \mathbb{R}^n \rightarrow \mathbb{R}^N$, where $N > n$.
\end{itemize}

\subsubsection{Kernel Trick}

\begin{itemize}
    \item Computing $\phi(\mathbf{x})$ explicitly can be computationally expensive or infeasible.
    \item The kernel trick allows computation of inner products in the high-dimensional space without explicit mapping.
    \item Kernel function $K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j)$.
    \item The optimization problem depends only on inner products of the form $\mathbf{x}_i^\top \mathbf{x}_j$, which can be replaced with $K(\mathbf{x}_i, \mathbf{x}_j)$.
\end{itemize}

\subsubsection{Common Kernel Functions}

\begin{itemize}
    \item \textbf{Linear Kernel:}
    \[
    K(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i^\top \mathbf{x}_j
    \]
    \item \textbf{Polynomial Kernel:}
    \[
    K(\mathbf{x}_i, \mathbf{x}_j) = (\gamma \mathbf{x}_i^\top \mathbf{x}_j + r)^d
    \]
    where $\gamma$, $r$, and $d$ are kernel parameters.
    \item \textbf{Radial Basis Function (RBF) Kernel:}
    \[
    K(\mathbf{x}_i, \mathbf{x}_j) = \exp\left( -\gamma \| \mathbf{x}_i - \mathbf{x}_j \|^2 \right)
    \]
    where $\gamma > 0$ is a kernel parameter.
    \item \textbf{Sigmoid Kernel:}
    \[
    K(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\gamma \mathbf{x}_i^\top \mathbf{x}_j + r)
    \]
\end{itemize}

\subsection{Dual Formulation}

\begin{itemize}
    \item The SVM optimization problem can be expressed in its dual form, which depends only on the inner products of data points.
    \item Dual problem for soft-margin SVM:
    \[
    \begin{aligned}
    & \underset{\boldsymbol{\alpha}}{\text{maximize}} && \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j K(\mathbf{x}_i, \mathbf{x}_j) \\
    & \text{subject to} && 0 \leq \alpha_i \leq C, \quad \forall i \\
    &&& \sum_{i=1}^n \alpha_i y_i = 0
    \end{aligned}
    \]
    \item The decision function becomes:
    \[
    f(\mathbf{x}) = \sum_{i=1}^n \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b
    \]
    \item Only support vectors (data points with $\alpha_i > 0$) contribute to the decision function.
\end{itemize}

\subsection{SVM in Practice}

\subsubsection{Pros}

\begin{itemize}
    \item Effective in high-dimensional spaces.
    \item Works well when the number of features exceeds the number of samples.
    \item Uses a subset of training points (support vectors), making it memory efficient.
    \item Flexible with different kernel functions for various data types.
\end{itemize}

\subsubsection{Cons}

\begin{itemize}
    \item Can be computationally intensive for large datasets.
    \item Choosing the right kernel and hyperparameters can be challenging.
    \item SVMs do not provide direct probability estimates (though methods exist to approximate them).
\end{itemize}

\subsubsection{Practical Considerations}

\begin{itemize}
    \item \textbf{Hyperparameter Tuning:}
    \begin{itemize}
        \item Regularization parameter $C$ and kernel parameters (e.g., $\gamma$ in RBF kernel) need to be tuned using methods like cross-validation.
    \end{itemize}
    \item \textbf{Feature Scaling:}
    \begin{itemize}
        \item Feature scaling is important as SVMs are sensitive to the scale of the inputs.
    \end{itemize}
    \item \textbf{Class Imbalance:}
    \begin{itemize}
        \item SVMs may perform poorly when classes are imbalanced; techniques like class weighting can be used.
    \end{itemize}
\end{itemize}

\subsection{Conclusion}

\begin{itemize}
    \item SVMs are powerful tools for classification and regression tasks.
    \item The use of kernel functions allows SVMs to model complex, non-linear relationships.
    \item Proper tuning and consideration of practical aspects are essential for achieving good performance.
\end{itemize}

\section{Support Vector Machines (SVMs) continued}

\textbf{Oversimplified TLDR:}
\begin{itemize}
    \item SVM is a powerful supervised learning algorithm for classification and regression tasks.
    \item \textbf{Hard-margin SVM:}
    \begin{itemize}
        \item Used when data is linearly separable.
        \item Finds the hyperplane that maximizes the margin between classes.
        \item Relies on support vectors (data points closest to the decision boundary).
    \end{itemize}
    \item \textbf{Soft-margin SVM:}
    \begin{itemize}
        \item Handles non-linearly separable data.
        \item Introduces slack variables to allow some misclassifications.
        \item Balances maximizing margin and minimizing classification errors.
    \end{itemize}
    \item \textbf{Kernel Trick:}
    \begin{itemize}
        \item Allows SVM to perform in high-dimensional feature spaces.
        \item Enables non-linear decision boundaries using kernel functions.
        \item Computationally efficient without explicitly mapping data to higher dimensions.
    \end{itemize}
    \item \textbf{Dual Formulation:}
    \begin{itemize}
        \item Reformulates the optimization problem using Lagrange multipliers.
        \item The solution depends only on inner products between data points.
        \item Facilitates the use of the kernel trick.
    \end{itemize}
\end{itemize}

\subsection{Hard-margin Support Vector Machine}

\begin{itemize}
    \item Applicable when data is linearly separable.
    \item Objective: Find the hyperplane that maximizes the margin between two classes.
    \item The decision boundary is defined as:
    \[
    y(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b = 0
    \]
    where:
    \begin{itemize}
        \item $\mathbf{w}$ is the weight vector orthogonal to the hyperplane.
        \item $b$ is the bias term.
    \end{itemize}
    \item The margin is the distance between the hyperplane and the nearest data points (support vectors).
\end{itemize}

\subsubsection{Optimization Problem}

\begin{itemize}
    \item Goal: Maximize the margin while ensuring all data points are correctly classified.
    \item The constraints for correctly classified data points are:
    \[
    \begin{cases}
    \mathbf{w}^\top \mathbf{x}_i + b \geq 1 & \text{if } y_i = +1 \\
    \mathbf{w}^\top \mathbf{x}_i + b \leq -1 & \text{if } y_i = -1
    \end{cases}
    \]
    \item Combining the constraints:
    \[
    y_i (\mathbf{w}^\top \mathbf{x}_i + b) \geq 1, \quad \forall i
    \]
    \item The optimization problem becomes:
    \[
    \begin{aligned}
    & \min_{\mathbf{w}, b} \quad \frac{1}{2} \|\mathbf{w}\|^2 \\
    & \text{subject to} \quad y_i (\mathbf{w}^\top \mathbf{x}_i + b) \geq 1, \quad \forall i
    \end{aligned}
    \]
    \item The factor $\frac{1}{2}$ is included for mathematical convenience.
\end{itemize}

\subsubsection{Lagrangian and Dual Formulation}

\begin{itemize}
    \item Introduce Lagrange multipliers $\alpha_i \geq 0$ for each constraint.
    \item The Lagrangian is:
    \[
    L(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_{i=1}^n \alpha_i [y_i (\mathbf{w}^\top \mathbf{x}_i + b) - 1]
    \]
    \item To find the saddle point, we set the derivatives with respect to $\mathbf{w}$ and $b$ to zero:
    \[
    \begin{aligned}
    \frac{\partial L}{\partial \mathbf{w}} &= \mathbf{w} - \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i = 0 \\
    \frac{\partial L}{\partial b} &= -\sum_{i=1}^n \alpha_i y_i = 0
    \end{aligned}
    \]
    \item This leads to:
    \[
    \mathbf{w} = \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i
    \]
    \item Substitute $\mathbf{w}$ back into the Lagrangian to obtain the dual form:
    \[
    \begin{aligned}
    & \max_{\boldsymbol{\alpha}} \quad \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j (\mathbf{x}_i^\top \mathbf{x}_j) \\
    & \text{subject to} \quad \alpha_i \geq 0, \quad \sum_{i=1}^n \alpha_i y_i = 0
    \end{aligned}
    \]
    \item The dual problem depends only on the inner products of the data points.
\end{itemize}

\subsubsection{Decision Function}

\begin{itemize}
    \item The decision function for classifying a new data point $\mathbf{x}$ is:
    \[
    y(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b = \left( \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i^\top \mathbf{x} \right) + b
    \]
    \item Only data points with $\alpha_i > 0$ (support vectors) contribute to the decision function.
    \item The bias term $b$ can be computed using any support vector $\mathbf{x}_s$:
    \[
    b = y_s - \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i^\top \mathbf{x}_s
    \]
\end{itemize}

\subsection{Soft-margin Support Vector Machine}

\begin{itemize}
    \item Used when data is not linearly separable.
    \item Introduces slack variables $\xi_i \geq 0$ to allow some misclassifications.
    \item Balances maximizing the margin and minimizing the classification error.
\end{itemize}

\subsubsection{Optimization Problem with Slack Variables}

\begin{itemize}
    \item The constraints become:
    \[
    y_i (\mathbf{w}^\top \mathbf{x}_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0, \quad \forall i
    \]
    \item The optimization problem is:
    \[
    \begin{aligned}
    & \min_{\mathbf{w}, b, \boldsymbol{\xi}} \quad \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i \\
    & \text{subject to} \quad y_i (\mathbf{w}^\top \mathbf{x}_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0, \quad \forall i
    \end{aligned}
    \]
    \item The hyperparameter $C > 0$ controls the trade-off between maximizing the margin and minimizing the classification error.
\end{itemize}

\subsubsection{Dual Formulation}

\begin{itemize}
    \item Introduce Lagrange multipliers $\alpha_i \geq 0$ and $\mu_i \geq 0$.
    \item The dual problem becomes:
    \[
    \begin{aligned}
    & \max_{\boldsymbol{\alpha}} \quad \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j (\mathbf{x}_i^\top \mathbf{x}_j) \\
    & \text{subject to} \quad 0 \leq \alpha_i \leq C, \quad \sum_{i=1}^n \alpha_i y_i = 0
    \end{aligned}
    \]
    \item The upper bound $\alpha_i \leq C$ ensures that the influence of misclassified points is limited.
\end{itemize}

\subsubsection{Decision Function}

\begin{itemize}
    \item Similar to the hard-margin case:
    \[
    y(\mathbf{x}) = \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i^\top \mathbf{x} + b
    \]
    \item Support vectors are data points with $0 < \alpha_i < C$.
    \item The bias term $b$ can be computed using support vectors that lie exactly on the margin:
    \[
    b = y_s - \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i^\top \mathbf{x}_s
    \]
    where $\alpha_s \in (0, C)$.
\end{itemize}

\subsection{Kernel Trick}

\begin{itemize}
    \item Enables SVM to perform non-linear classification.
    \item Implicitly maps data into a higher-dimensional feature space where it is linearly separable.
    \item Kernel function $K(\mathbf{x}_i, \mathbf{x}_j)$ computes the inner product in the feature space without explicit mapping.
    \item Common kernel functions:
    \begin{itemize}
        \item \textbf{Linear Kernel:} $K(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i^\top \mathbf{x}_j$
        \item \textbf{Polynomial Kernel:} $K(\mathbf{x}_i, \mathbf{x}_j) = (\gamma \mathbf{x}_i^\top \mathbf{x}_j + r)^d$
        \item \textbf{Radial Basis Function (RBF) Kernel:} $K(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2)$
        \item \textbf{Sigmoid Kernel:} $K(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\gamma \mathbf{x}_i^\top \mathbf{x}_j + r)$
    \end{itemize}
    \item The decision function using kernels:
    \[
    y(\mathbf{x}) = \sum_{i=1}^n \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b
    \]
\end{itemize}

\subsection{Dual Representation and Advantages}

\begin{itemize}
    \item The dual formulation depends only on the inner products (or kernels) between data points.
    \item Advantages:
    \begin{itemize}
        \item Enables the use of the kernel trick.
        \item Reduces computational complexity for high-dimensional data.
        \item The number of variables in the dual problem is equal to the number of training samples.
    \end{itemize}
\end{itemize}

\subsection{Multi-class Classification with SVM}

\begin{itemize}
    \item SVMs are inherently binary classifiers.
    \item Methods to extend SVM for multi-class classification:
    \begin{itemize}
        \item \textbf{One-vs-One:}
        \begin{itemize}
            \item Train an SVM for every pair of classes.
            \item Number of classifiers: $\binom{K}{2} = \frac{K(K-1)}{2}$
            \item Final prediction by majority voting or max-wins strategy.
        \end{itemize}
        \item \textbf{One-vs-All:}
        \begin{itemize}
            \item Train an SVM to separate each class from all other classes.
            \item Number of classifiers: $K$
            \item Final prediction by selecting the class with the highest decision function value.
        \end{itemize}
    \end{itemize}
\end{itemize}

\subsection{Practical Considerations}

\begin{itemize}
    \item \textbf{Choice of Kernel:}
    \begin{itemize}
        \item Depends on the data and problem at hand.
        \item RBF kernel is a popular choice due to its flexibility.
        \item Cross-validation can help in selecting the appropriate kernel and its parameters.
    \end{itemize}
    \item \textbf{Regularization Parameter $C$:}
    \begin{itemize}
        \item Controls the trade-off between maximizing margin and minimizing classification error.
        \item A large $C$ aims for a smaller margin with fewer misclassifications.
        \item A small $C$ allows a larger margin with more misclassifications.
    \end{itemize}
    \item \textbf{Computational Complexity:}
    \begin{itemize}
        \item Training complexity is between $O(n^2)$ and $O(n^3)$, where $n$ is the number of training samples.
        \item SVMs are not well-suited for very large datasets.
        \item Techniques like decomposition methods and approximate SVM can be used for large-scale problems.
    \end{itemize}
    \item \textbf{Scaling and Preprocessing:}
    \begin{itemize}
        \item Feature scaling can improve the performance of SVMs.
        \item Outliers can significantly affect the SVM, especially with small $C$.
    \end{itemize}
\end{itemize}

\subsection{Summary}

\begin{itemize}
    \item SVMs are powerful classifiers that aim to find the optimal separating hyperplane.
    \item The use of kernels allows SVMs to perform non-linear classification.
    \item The dual formulation leverages the kernel trick and depends only on inner products.
    \item Soft-margin SVMs handle non-separable data by introducing slack variables.
    \item SVMs can be extended to multi-class problems using strategies like one-vs-one and one-vs-all.
\end{itemize}

\section{Gradient Descent (GD)}

\textbf{Oversimplified TLDR:}
\begin{itemize}
    \item Gradient Descent is an iterative optimization algorithm to find the minimum of a function.
    \item It moves in the direction opposite to the gradient (steepest descent).
    \item Widely used to train machine learning models by minimizing cost functions.
    \item Key components:
    \begin{itemize}
        \item \textbf{Learning Rate ($\alpha$)}: Controls the size of the steps taken towards the minimum.
        \item \textbf{Gradient}: The vector of partial derivatives indicating the direction of steepest ascent.
        \item \textbf{Update Rule}: Parameters are updated by moving in the opposite direction of the gradient.
    \end{itemize}
    \item Variants include:
    \begin{itemize}
        \item \textbf{Batch Gradient Descent}
        \item \textbf{Stochastic Gradient Descent (SGD)}
        \item \textbf{Mini-batch Gradient Descent}
    \end{itemize}
\end{itemize}

\subsection{Introduction to Optimization}

\begin{itemize}
    \item Optimization involves finding the best solution from all feasible solutions.
    \item In machine learning, this typically means minimizing a cost function with respect to model parameters.
    \item Two main types of optimization methods:
    \begin{itemize}
        \item \textbf{Analytical Methods}:
        \begin{itemize}
            \item Find closed-form solutions.
            \item Provide exact solutions but may be computationally expensive or infeasible for large datasets or complex models.
        \end{itemize}
        \item \textbf{Numerical Methods}:
        \begin{itemize}
            \item Provide approximate solutions within an acceptable tolerance.
            \item Generally faster and applicable when analytical solutions are not feasible.
        \end{itemize}
    \end{itemize}
\end{itemize}

\subsection{Gradient Descent Algorithm}

\begin{itemize}
    \item Gradient Descent is a first-order iterative optimization algorithm for finding the minimum of a function.
    \item It uses the gradient (first derivative) of the function to find the direction of steepest ascent.
    \item To find the minimum, we move in the opposite direction of the gradient (steepest descent).
    \item \textbf{Gradient Vector}:
    \[
    \nabla f(\boldsymbol{\theta}) = \left[ \frac{\partial f}{\partial \theta_1}, \frac{\partial f}{\partial \theta_2}, \dots, \frac{\partial f}{\partial \theta_m} \right]^\top
    \]
    \item \textbf{Update Rule}:
    \[
    \boldsymbol{\theta}^{(t+1)} = \boldsymbol{\theta}^{(t)} - \alpha \nabla f(\boldsymbol{\theta}^{(t)})
    \]
    where:
    \begin{itemize}
        \item $\boldsymbol{\theta}^{(t)}$ are the parameters at iteration $t$.
        \item $\alpha$ is the learning rate (step size).
        \item $\nabla f(\boldsymbol{\theta}^{(t)})$ is the gradient evaluated at $\boldsymbol{\theta}^{(t)}$.
    \end{itemize}
\end{itemize}

\subsubsection{Learning Rate ($\alpha$)}

\begin{itemize}
    \item The learning rate controls how big of a step we take in the direction opposite to the gradient.
    \item If $\alpha$ is too small:
    \begin{itemize}
        \item Convergence will be slow.
    \end{itemize}
    \item If $\alpha$ is too large:
    \begin{itemize}
        \item May overshoot the minimum.
        \item Can cause divergence or oscillations.
    \end{itemize}
    \item Choosing an appropriate learning rate is crucial for the performance of Gradient Descent.
\end{itemize}

\subsection{Gradient Descent in One Dimension}

\begin{itemize}
    \item Consider minimizing a simple quadratic function:
    \[
    f(\theta) = (\theta - 5)^2
    \]
    \item The derivative (gradient) is:
    \[
    \frac{\partial f}{\partial \theta} = 2(\theta - 5)
    \]
    \item The update rule becomes:
    \[
    \theta^{(t+1)} = \theta^{(t)} - \alpha \cdot 2(\theta^{(t)} - 5)
    \]
    \item Example with $\alpha = 0.1$ and initial $\theta^{(0)} = 1$:
    \begin{align*}
        \theta^{(1)} &= \theta^{(0)} - 0.1 \cdot 2(\theta^{(0)} - 5) = 1 - 0.1 \cdot 2(-4) = 1 + 0.8 = 1.8 \\
        \theta^{(2)} &= \theta^{(1)} - 0.1 \cdot 2(\theta^{(1)} - 5) = 1.8 - 0.1 \cdot 2(-3.2) = 1.8 + 0.64 = 2.44 \\
        \theta^{(3)} &= \theta^{(2)} - 0.1 \cdot 2(\theta^{(2)} - 5) = 2.44 - 0.1 \cdot 2(-2.56) = 2.44 + 0.512 = 2.952 \\
        \vdots \\
    \end{align*}
    \item The iterations continue until convergence is achieved.
\end{itemize}

\subsection{Stopping Criteria}

\begin{itemize}
    \item Gradient Descent iterates until convergence, but how do we determine when to stop?
    \item Common stopping criteria:
    \begin{itemize}
        \item The magnitude of the gradient falls below a threshold:
        \[
        \| \nabla f(\boldsymbol{\theta}^{(t)}) \| < \epsilon
        \]
        \item The change in the cost function is below a threshold:
        \[
        | f(\boldsymbol{\theta}^{(t+1)}) - f(\boldsymbol{\theta}^{(t)}) | < \epsilon
        \]
        \item A maximum number of iterations is reached.
    \end{itemize}
    \item Note: The gradient may not reach exactly zero, especially for non-convex functions.
\end{itemize}

\subsection{Sensitivity to Learning Rate}

\begin{itemize}
    \item The choice of learning rate $\alpha$ can significantly affect the convergence of Gradient Descent.
    \item If $\alpha$ is too small, the algorithm will take tiny steps and require many iterations.
    \item If $\alpha$ is too large, the algorithm may overshoot and diverge.
    \item Strategies for choosing $\alpha$:
    \begin{itemize}
        \item Use a constant small value.
        \item Implement a learning rate schedule (e.g., decrease $\alpha$ over time).
        \item Use adaptive learning rates (e.g., methods like AdaGrad, RMSProp).
    \end{itemize}
\end{itemize}

\subsection{Gradient Descent in Multiple Dimensions}

\begin{itemize}
    \item For functions of multiple variables, the gradient is a vector of partial derivatives.
    \[
    \nabla f(\boldsymbol{\theta}) = \left[ \frac{\partial f}{\partial \theta_1}, \frac{\partial f}{\partial \theta_2}, \dots, \frac{\partial f}{\partial \theta_p} \right]^\top
    \]
    \item The update rule generalizes to:
    \[
    \boldsymbol{\theta}^{(t+1)} = \boldsymbol{\theta}^{(t)} - \alpha \nabla f(\boldsymbol{\theta}^{(t)})
    \]
    \item Gradient Descent works well for convex functions, where any local minimum is a global minimum.
    \item For non-convex functions, Gradient Descent may converge to a local minimum.
\end{itemize}

\subsection{Applying Gradient Descent to Machine Learning Models}

\begin{itemize}
    \item In machine learning, Gradient Descent is used to minimize the cost (loss) function with respect to model parameters.
    \item \textbf{Example: Linear Regression}
    \begin{itemize}
        \item Model: $\hat{y} = \beta_0 + \beta_1 x$
        \item Cost function (Mean Squared Error):
        \[
        J(\beta) = \frac{1}{n} \sum_{i=1}^{n} (\hat{y}_i - y_i)^2
        \]
        \item The optimization objective:
        \[
        \min_{\beta} J(\beta)
        \]
        \item The cost function is differentiable and convex, ensuring convergence to the global minimum.
        \item Gradient of the cost function:
        \[
        \frac{\partial J}{\partial \beta_0} = \frac{2}{n} \sum_{i=1}^{n} (\hat{y}_i - y_i)
        \]
        \[
        \frac{\partial J}{\partial \beta_1} = \frac{2}{n} \sum_{i=1}^{n} x_i (\hat{y}_i - y_i)
        \]
        \item Update rules:
        \[
        \beta_0^{(t+1)} = \beta_0^{(t)} - \alpha \frac{2}{n} \sum_{i=1}^{n} (\hat{y}_i^{(t)} - y_i)
        \]
        \[
        \beta_1^{(t+1)} = \beta_1^{(t)} - \alpha \frac{2}{n} \sum_{i=1}^{n} x_i (\hat{y}_i^{(t)} - y_i)
        \]
    \end{itemize}
\end{itemize}

\subsubsection{Simultaneous Parameter Updates}

\begin{itemize}
    \item Update all parameters simultaneously to ensure consistency:
    \[
    \begin{aligned}
    \beta_{\text{new }0} &= \beta_0 - \alpha \frac{\partial J}{\partial \beta_0} \\
    \beta_{\text{new }1} &= \beta_1 - \alpha \frac{\partial J}{\partial \beta_1} \\
    \beta_0 &= \beta_{\text{new }0} \\
    \beta_1 &= \beta_{\text{new }1}
    \end{aligned}
    \]
\end{itemize}

\subsubsection{Loss and Cost Functions}

\begin{itemize}
    \item \textbf{Loss Function} $L(\hat{y}_i, y_i)$: Measures the error for a single data point.
    \item \textbf{Cost Function} $J(\beta)$: The average of the loss over the entire dataset.
    \[
    J(\beta) = \frac{1}{n} \sum_{i=1}^{n} L(\hat{y}_i, y_i)
    \]
    \item The gradient of the cost function is the average of the gradients of the loss function over all data points:
    \[
    \nabla J(\beta) = \frac{1}{n} \sum_{i=1}^{n} \nabla L(\hat{y}_i, y_i)
    \]
    \item Therefore, the Gradient Descent update step is:
    \[
    \beta^{(t+1)} = \beta^{(t)} - \alpha \nabla J(\beta^{(t)}) = \beta^{(t)} - \alpha \frac{1}{n} \sum_{i=1}^{n} \nabla L(\hat{y}_i^{(t)}, y_i)
    \]
\end{itemize}

\subsection{Variants of Gradient Descent}

\begin{itemize}
    \item \textbf{Batch Gradient Descent}
    \begin{itemize}
        \item Uses the entire training dataset to compute the gradient at each step.
        \item Update rule:
        \[
        \beta^{(t+1)} = \beta^{(t)} - \alpha \frac{1}{n} \sum_{i=1}^{n} \nabla L(\hat{y}_i^{(t)}, y_i)
        \]
        \item Pros:
        \begin{itemize}
            \item Stable convergence for convex functions.
        \end{itemize}
        \item Cons:
        \begin{itemize}
            \item Computationally expensive for large datasets.
            \item May cause memory issues.
        \end{itemize}
    \end{itemize}
    \item \textbf{Stochastic Gradient Descent (SGD)}
    \begin{itemize}
        \item Updates parameters using one data point at a time.
        \item Update rule:
        \[
        \beta^{(t+1)} = \beta^{(t)} - \alpha \nabla L(\hat{y}_i^{(t)}, y_i)
        \]
        \item Pros:
        \begin{itemize}
            \item Faster iterations.
            \item Can escape local minima due to noise.
        \end{itemize}
        \item Cons:
        \begin{itemize}
            \item May fluctuate and not converge to the exact minimum.
        \end{itemize}
        \item Often repeated over epochs, where one epoch equals $n$ iterations (the size of the dataset).
    \end{itemize}
    \item \textbf{Mini-batch Gradient Descent}
    \begin{itemize}
        \item Compromise between Batch GD and SGD.
        \item Uses a small batch of data points (mini-batch) to compute the gradient.
        \item Update rule:
        \[
        \beta^{(t+1)} = \beta^{(t)} - \alpha \frac{1}{|S|} \sum_{i \in S} \nabla L(\hat{y}_i^{(t)}, y_i)
        \]
        where $S$ is the mini-batch.
        \item Pros:
        \begin{itemize}
            \item Faster than Batch GD.
            \item More stable convergence than SGD.
        \end{itemize}
    \end{itemize}
\end{itemize}

\subsection{Practical Considerations}

\begin{itemize}
    \item \textbf{Convergence}
    \begin{itemize}
        \item Gradient Descent converges to a global minimum for convex functions.
        \item For non-convex functions, it may converge to a local minimum.
    \end{itemize}
    \item \textbf{Non-Convex Functions}
    \begin{itemize}
        \item Optimization landscape may have multiple local minima and saddle points.
        \item Variants like SGD and Mini-batch GD can help in escaping local minima due to their stochastic nature.
    \end{itemize}
    \item \textbf{Choosing Learning Rate}
    \begin{itemize}
        \item Experiment with different values.
        \item Use techniques like learning rate decay or adaptive learning rates.
    \end{itemize}
    \item \textbf{Feature Scaling}
    \begin{itemize}
        \item Scaling features can improve convergence speed.
        \item Methods include normalization and standardization.
    \end{itemize}
    \item \textbf{Initialization}
    \begin{itemize}
        \item Randomly initialize parameters.
        \item Proper initialization can affect convergence and avoid getting stuck in poor local minima.
    \end{itemize}
    \item \textbf{Regularization}
    \begin{itemize}
        \item Techniques like L1 or L2 regularization can prevent overfitting.
        \item Added to the cost function to penalize large weights.
    \end{itemize}
\end{itemize}

\subsection{Extensions and Advanced Topics}

\begin{itemize}
    \item \textbf{Momentum}
    \begin{itemize}
        \item Accelerates Gradient Descent by adding a fraction of the update vector of the past time step to the current update.
        \item Update rule with momentum:
        \[
        \begin{aligned}
        v^{(t)} &= \gamma v^{(t-1)} + \alpha \nabla J(\beta^{(t)}) \\
        \beta^{(t+1)} &= \beta^{(t)} - v^{(t)}
        \end{aligned}
        \]
        where $\gamma$ is the momentum term (typically between 0 and 1).
    \end{itemize}
    \item \textbf{Adaptive Learning Rates}
    \begin{itemize}
        \item Methods like AdaGrad, RMSProp, and Adam adjust the learning rate during training based on past gradients.
        \item \textbf{Adam} (Adaptive Moment Estimation) combines momentum and adaptive learning rates.
    \end{itemize}
    \item \textbf{Second-Order Methods}
    \begin{itemize}
        \item Utilize second derivatives (Hessian matrix) for optimization.
        \item Examples include Newton's Method and Quasi-Newton methods (e.g., BFGS).
        \item Converge faster but are computationally expensive due to the calculation of the Hessian.
    \end{itemize}
\end{itemize}

\subsection{Summary}

\begin{itemize}
    \item Gradient Descent is a fundamental algorithm in optimization and machine learning.
    \item Understanding its mechanics and variations is crucial for training effective models.
    \item Practical implementation requires careful consideration of learning rates, convergence criteria, and data characteristics.
\end{itemize}

\section{A Simple Artificial Neural Network (ANN) with a Hidden Layer}

\textbf{Oversimplified TLDR:}
\begin{itemize}
    \item Artificial Neural Networks (ANNs) are computational models inspired by biological neural networks.
    \item A typical ANN consists of layers of neurons: an input layer, one or more hidden layers, and an output layer.
    \item Each neuron computes a weighted sum of its inputs, adds a bias, and passes the result through an activation function.
    \item The hidden layer(s) enable the network to learn non-linear decision boundaries, allowing more complex tasks to be performed.
    \item Training involves adjusting weights (and biases) via Gradient Descent (or its variants) using a process called back-propagation.
\end{itemize}

\subsection{Introduction to Artificial Neural Networks}

\begin{itemize}
    \item \textbf{Biological Inspiration:} Neurons in the human brain receive signals via dendrites, process them in the cell body (soma), and transmit an output via the axon. ANNs mimic this structure in a simplified computational form.
    \item \textbf{Historical Context:}
    \begin{itemize}
        \item Early neural network models (like the perceptron) appeared in the 1940s and 1950s.
        \item Interest waned in the 1970s, but was revived in the 2000s and 2010s (often called ``deep learning'') due to increased computational power and large datasets.
    \end{itemize}
    \item \textbf{Real-World Examples:}
    \begin{itemize}
        \item Image classification (e.g., recognizing handwritten digits, detecting objects in photographs).
        \item Natural language processing (e.g., spam detection, sentiment analysis).
        \item Regression tasks (e.g., predicting house prices, forecasting stock prices).
    \end{itemize}
\end{itemize}

\subsection{Structure of a Simple ANN}

\begin{itemize}
    \item A simple ANN typically has:
    \begin{itemize}
        \item One \textbf{input layer}, which directly outputs the input values (no activation function).
        \item One or more \textbf{hidden layers}, each consisting of several neurons with non-linear activation functions (e.g., sigmoid, tanh, ReLU).
        \item An \textbf{output layer}, whose activation function is chosen based on the task (e.g., linear for regression, sigmoid for binary classification, softmax for multi-class classification).
    \end{itemize}
    \item \textbf{Forward Pass:} For a given input vector $\mathbf{x}$, signals travel through the layers until an output $\mathbf{a}^{(o)}$ is computed.
    \item \textbf{Parameters:} All the weights and biases in the network are the trainable parameters.
\end{itemize}

\subsection{Universal Approximation Theorem (Informal)}

\begin{itemize}
    \item Under mild assumptions, a neural network with at least one hidden layer and a sufficient (finite) number of neurons can approximate any continuous function to a desired accuracy.
    \item Non-linear activation functions (e.g., sigmoid, ReLU) are crucial; if the activation were purely linear, the network would only represent linear transformations regardless of the depth.
\end{itemize}

\subsection{Forward Pass Equations}

\subsubsection{One Hidden Layer Network}

Suppose we have an input layer of size $d$, a hidden layer of size $m$, and an output layer of size $k$.

\textbf{Hidden layer computation:}

\[
\mathbf{z}^{(h)} = \mathbf{x} W^{(h)} + \mathbf{b}^{(h)}
\quad,\quad
\mathbf{a}^{(h)} = f(\mathbf{z}^{(h)})
\]

where:
\begin{itemize}
    \item $\mathbf{x}$ is the input row vector of dimension $1 \times d$.
    \item $W^{(h)}$ is a $d \times m$ weight matrix for the hidden layer.
    \item $\mathbf{b}^{(h)}$ is a $1 \times m$ bias row vector.
    \item $f(\cdot)$ is an element-wise non-linear activation function (e.g., $\sigma, \tanh, \mathrm{ReLU}$).
    \item $\mathbf{a}^{(h)}$ is the output of the hidden layer (dimension $1 \times m$).
\end{itemize}

\textbf{Output layer computation:}

\[
\mathbf{z}^{(o)} = \mathbf{a}^{(h)} W^{(o)} + \mathbf{b}^{(o)}
\quad,\quad
\mathbf{a}^{(o)} = g(\mathbf{z}^{(o)})
\]

where:
\begin{itemize}
    \item $W^{(o)}$ is an $m \times k$ weight matrix for the output layer.
    \item $\mathbf{b}^{(o)}$ is a $1 \times k$ bias row vector.
    \item $g(\cdot)$ is the output-layer activation function (linear, sigmoid, softmax, etc.).
    \item $\mathbf{a}^{(o)}$ is the final output (dimension $1 \times k$).
\end{itemize}

\subsubsection{Loss Function}

\begin{itemize}
    \item For \textbf{regression tasks}, a common choice is the Mean Squared Error (MSE):
    \[
    L\bigl(\mathbf{a}^{(o)}, y\bigr) = \frac{1}{2}\bigl(y - \mathbf{a}^{(o)}\bigr)^2
    \]
    \item For \textbf{binary classification}, a common choice is the Binary Cross-Entropy (Log Loss):
    \[
    L\bigl(\mathbf{a}^{(o)}, y\bigr)
    = -\Bigl[y \cdot \log\bigl(\mathbf{a}^{(o)}\bigr) + (1-y)\cdot \log\bigl(1 - \mathbf{a}^{(o)}\bigr)\Bigr]
    \]
    \item For \textbf{multi-class classification}, the Softmax cross-entropy loss is often used:
    \[
    L\bigl(\mathbf{a}^{(o)}, y\bigr)
    = -\sum_{i=1}^{k} y_i \cdot \log\bigl(a_i^{(o)}\bigr)
    \quad \text{where } \mathbf{a}^{(o)} \text{ is computed via Softmax.}
    \]
\end{itemize}

\subsection{Training the ANN}

\begin{itemize}
    \item \textbf{Goal:} Find the set of weights and biases that minimize the chosen loss function over the training dataset.
    \item \textbf{Process:}
    \begin{enumerate}
        \item \textbf{Initialization:} Randomly initialize all weights and biases.
        \item \textbf{Forward Pass:} For each training sample $(\mathbf{x}, y)$, compute the output $\mathbf{a}^{(o)}$ and loss $L(\mathbf{a}^{(o)}, y)$.
        \item \textbf{Backward Pass (Back-Propagation):} 
        \begin{itemize}
            \item Compute partial derivatives of the loss w.r.t. the parameters by applying the chain rule from the output layer back toward the input layer.
        \end{itemize}
        \item \textbf{Gradient Descent Update:}
        \[
        W_{(t+1)} = W_{(t)} - \alpha \, \nabla_W L, 
        \quad
        b_{(t+1)} = b_{(t)} - \alpha \, \nabla_b L
        \]
        where $\alpha$ is the learning rate.
    \end{enumerate}
\end{itemize}

\subsection{Example: Binary Classification with One Hidden Layer}

\begin{itemize}
    \item \textbf{Network Architecture:}
    \begin{itemize}
        \item Input layer: $\mathbf{x}$ of dimension $d$
        \item Hidden layer with $m$ neurons and sigmoid activation $\sigma(z) = \frac{1}{1+e^{-z}}$
        \item Output layer with 1 neuron (also using a sigmoid activation) to produce an output in $(0,1)$
    \end{itemize}
    \item \textbf{Loss Function (Cross-Entropy):}
    \[
    L\bigl(a^{(o)}, y\bigr)
    = -\Bigl[y\log\bigl(a^{(o)}\bigr) + (1-y)\log\bigl(1 - a^{(o)}\bigr)\Bigr]
    \]
    \item \textbf{Forward Pass Equations:}

    \[
    \begin{aligned}
    \mathbf{z}^{(h)} &= \mathbf{x}W^{(h)} + \mathbf{b}^{(h)}, 
    & \mathbf{a}^{(h)} &= \sigma\bigl(\mathbf{z}^{(h)}\bigr),
    \\
    \mathbf{z}^{(o)} &= \mathbf{a}^{(h)}W^{(o)} + \mathbf{b}^{(o)}, 
    & a^{(o)} &= \sigma\bigl(\mathbf{z}^{(o)}\bigr).
    \end{aligned}
    \]

    \item \textbf{Backward Pass (Conceptual):}
    \begin{itemize}
        \item Compute $\frac{\partial L}{\partial a^{(o)}}$, $\frac{\partial L}{\partial \mathbf{z}^{(o)}}$, and then $\frac{\partial L}{\partial W^{(o)}}$, $\frac{\partial L}{\partial \mathbf{b}^{(o)}}$.
        \item Propagate the error back to the hidden layer: $\frac{\partial L}{\partial \mathbf{a}^{(h)}}$, $\frac{\partial L}{\partial \mathbf{z}^{(h)}}$, and then $\frac{\partial L}{\partial W^{(h)}}$, $\frac{\partial L}{\partial \mathbf{b}^{(h)}}$.
        \item Update the parameters: 
        \[
        W^{(o)} \leftarrow W^{(o)} - \alpha \frac{\partial L}{\partial W^{(o)}},
        \quad
        b^{(o)} \leftarrow b^{(o)} - \alpha \frac{\partial L}{\partial b^{(o)}} \quad \text{(similarly for } W^{(h)}\text{, }b^{(h)}\text{).}
        \]
    \end{itemize}
\end{itemize}

\subsection{Intuitive Explanation}

\begin{itemize}
    \item \textbf{Hidden Layer Function:} The hidden layer allows the network to transform inputs into intermediate representations. Non-linear activations help capture more complex patterns than a single linear transformation would.
    \item \textbf{Error Signal:} The difference between the predicted output and the true label guides how to update each weight. If the prediction is too high or too low, the gradient indicates how to adjust each parameter.
    \item \textbf{Learning Rate:} Controls the size of these updates. Too large can cause divergence; too small can slow learning.
    \item \textbf{Why Sigmoid for Binary Classification?} The sigmoid outputs a value between 0 and 1, naturally interpreting it as a probability for the positive class. 
\end{itemize}

\subsection{Real-World Use Case}

\begin{itemize}
    \item \textbf{Spam Detection:} 
    \begin{itemize}
        \item Input layer: Email features (e.g., word counts, presence of suspicious links).
        \item Hidden layer: Captures non-linear relationships in the text features.
        \item Output layer: Sigmoid activation to predict the probability of ``spam'' (1) vs. ``not spam'' (0).
        \item Loss Function: Binary Cross-Entropy.
        \item Training: Adjust weights via back-propagation on a large dataset of labeled emails.
    \end{itemize}
\end{itemize}

\subsection{Summary}

\begin{itemize}
    \item An ANN with a hidden layer can learn non-linear relationships.
    \item Choosing appropriate activation functions and a suitable loss function is crucial for performance.
    \item Training is done by Gradient Descent and back-propagation:
    \begin{itemize}
        \item Forward pass computes the output for each training sample.
        \item Backward pass uses chain rule to compute gradients w.r.t. the weights and biases.
        \item Parameters are updated to reduce the loss.
    \end{itemize}
    \item Despite their simplicity, single-hidden-layer ANNs can approximate a wide range of functions (Universal Approximation Theorem).
    \item Additional hidden layers (deep networks) can further improve representational power.
\end{itemize}

\section{ANN with Softmax Output Layer and Regularization}

\textbf{Oversimplified TLDR:}
\begin{itemize}
    \item When dealing with multiple classes, the \textbf{softmax} activation function is often used in the output layer.
    \item Regularization methods (e.g., L2 weight decay, dropout, early stopping, data augmentation) help prevent overfitting and improve generalization.
    \item Advanced optimization variants (momentum, Nesterov accelerated gradient, RMSProp, Adam) can speed up and stabilize training.
    \item Frameworks like \textbf{Keras/TensorFlow} offer high-level APIs for rapid development and experimentation.
\end{itemize}

\subsection{Softmax Output for Multi-Class Classification}

\begin{itemize}
    \item \textbf{Softmax Definition:} Converts logits (real-valued outputs) into a probability distribution. For a given output vector $\mathbf{z}^{(o)} = [z_1^{(o)}, z_2^{(o)},\ldots, z_C^{(o)}]$, the softmax function produces:
    \[
    a_{c}^{(o)} 
    = \frac{e^{z_{c}^{(o)}}}{\sum_{k=1}^{C} e^{z_{k}^{(o)}}}
    \quad,\quad c = 1,\ldots, C,
    \]
    where $C$ is the number of classes.
    \item \textbf{Cross-Entropy Loss (Multi-Class)}:
    \[
    L\bigl(\mathbf{a}^{(o)}, \mathbf{y}\bigr)
    = -\sum_{c=1}^{C} y_c \,\log\bigl(a_{c}^{(o)}\bigr),
    \]
    where $\mathbf{y}$ is a one-hot encoded label vector.
\end{itemize}

\subsubsection{Partial Derivatives}

\begin{itemize}
    \item For each class $c$, 
    \[
    \frac{\partial L}{\partial z_{c}^{(o)}}
    = a_{c}^{(o)} - y_{c}.
    \]
    \item Parameter updates for output layer weights $w_{j,c}^{(o)}$ and biases $b_{c}^{(o)}$ follow:
    \[
    \frac{\partial L}{\partial w_{j,c}^{(o)}} 
    = \bigl(a_{c}^{(o)} - y_c\bigr)\, a_{j}^{(h)}
    \quad,\quad
    \frac{\partial L}{\partial b_{c}^{(o)}}
    = a_{c}^{(o)} - y_c.
    \]
    \item Errors are then back-propagated to the hidden layer:
    \[
    \frac{\partial L}{\partial a_{j}^{(h)}}
    = \sum_{c=1}^{C} \Bigl(\frac{\partial L}{\partial z_{c}^{(o)}} \cdot \frac{\partial z_{c}^{(o)}}{\partial a_{j}^{(h)}}\Bigr)
    \quad,\quad
    \frac{\partial L}{\partial z_{j}^{(h)}}
    = \frac{\partial L}{\partial a_{j}^{(h)}} \cdot \frac{\partial a_{j}^{(h)}}{\partial z_{j}^{(h)}}.
    \]
    \item Hidden weights and biases update similarly, using
    \[
    \frac{\partial L}{\partial w_{i,j}^{(h)}} 
    = \frac{\partial L}{\partial z_{j}^{(h)}} \cdot x_i
    \quad,\quad
    \frac{\partial L}{\partial b_{j}^{(h)}} 
    = \frac{\partial L}{\partial z_{j}^{(h)}}.
    \]
\end{itemize}

\subsection{Regularization Methods in ANNs}

\subsubsection{Weight Decay (L2 Regularization)}

\begin{itemize}
    \item \textbf{Idea:} Penalize large weights to reduce model complexity.
    \item \textbf{Loss Function with L2 Penalty:}
    \[
    Q(\mathbf{W}) + \frac{\lambda}{2}\,\|\mathbf{W}\|_{2}^{2},
    \]
    where $Q(\mathbf{W})$ is the original loss (e.g., cross-entropy), $\mathbf{W}$ the collection of weights, and $\lambda$ the regularization coefficient.
    \item \textbf{Gradient Descent Update:} 
    \[
    \mathbf{W}_{t+1} = \mathbf{W}_t \;-\;\alpha \nabla_{\mathbf{W}} Q(\mathbf{W}_t)\;-\;\lambda\,\mathbf{W}_t.
    \]
\end{itemize}

\subsubsection{Dropout}

\begin{itemize}
    \item \textbf{Idea:} Randomly ``drop'' (disable) neurons during training with a certain probability (keep-prob).
    \item \textbf{Effect:} Forces the network to learn redundant representations, reducing overfitting. 
    \item \textbf{Implementation Detail:} 
    \begin{itemize}
        \item During training, each neuron's output is multiplied by a random mask of 0's (drop) and 1's (keep).
        \item In \textbf{inverted dropout}, outputs are scaled up by $\frac{1}{(\text{keep-prob})}$, so no scaling is needed at inference.
    \end{itemize}
    \item \textbf{At Inference:} All neurons are used without random drops.
\end{itemize}

\subsubsection{Early Stopping}

\begin{itemize}
    \item Monitor validation loss (or accuracy) over epochs.
    \item Stop training when the validation loss stops improving (or starts to worsen) to avoid overfitting.
\end{itemize}

\subsubsection{Data Augmentation}

\begin{itemize}
    \item \textbf{Idea:} Increase effective training set size by applying random transformations (e.g., rotations, flips, noise) to the existing data.
    \item Commonly used in image processing, but also applicable in other domains (e.g., text augmentation, audio augmentation).
    \item Helps the model learn robust features and generalize better.
\end{itemize}

\subsection{Variants of Gradient Descent}

\begin{itemize}
    \item \textbf{Momentum:} 
    \[
    \begin{aligned}
    v_{t+1} &= \beta \, v_{t} \;+\;\alpha\, \nabla L(\mathbf{W}_t),\\
    \mathbf{W}_{t+1} &= \mathbf{W}_t \;-\; v_{t+1},
    \end{aligned}
    \]
    where $v_t$ accumulates a history of gradients to accelerate movement in consistent directions.
    \item \textbf{Nesterov Accelerated Gradient (NAG):} 
    \[
    \begin{aligned}
    v_{t+1} &= \beta \, v_{t} \;+\;\alpha\, \nabla L(\mathbf{W}_t + \beta\,v_t),\\
    \mathbf{W}_{t+1} &= \mathbf{W}_t \;-\; v_{t+1},
    \end{aligned}
    \]
    which looks ahead before updating momentum.
    \item \textbf{Other Optimizers (Brief Mention):} Adagrad, Adadelta, RMSProp, Adam. These adjust learning rates automatically per parameter.
\end{itemize}

\subsection{Practical Example with Keras/TensorFlow}

\begin{itemize}
    \item \textbf{Model Definition:}
    \begin{verbatim}
    classifier = tf.keras.Sequential(name='my_model')
    classifier.add(tf.keras.Input(shape=(784,)))
    classifier.add(tf.keras.layers.Dense(10, activation='relu'))
    classifier.add(tf.keras.layers.Dense(1, activation='sigmoid'))
    \end{verbatim}
    \item \textbf{Compilation:}
    \begin{verbatim}
    classifier.compile(loss='binary_crossentropy',
                       optimizer=tf.keras.optimizers.SGD(learning_rate=0.01),
                       metrics=['accuracy'])
    \end{verbatim}
    \item \textbf{Fitting:}
    \begin{verbatim}
    history = classifier.fit(x_train, y_train,
                             epochs=150,
                             batch_size=x_train.shape[0],
                             verbose=0)
    \end{verbatim}
    \item \textbf{Regularization in Code Example:} 
    \begin{itemize}
        \item \texttt{tf.keras.layers.Dropout(rate)} introduces dropout with a specified drop probability.
        \item L2 weight decay can be added via \texttt{kernel\_regularizer} in \texttt{Dense} layers.
        \item Early stopping can be integrated via \texttt{tf.keras.callbacks.EarlyStopping}.
    \end{itemize}
\end{itemize}

\subsection{Intuitive and Real-World Perspective}

\begin{itemize}
    \item \textbf{Why Softmax?} 
    \begin{itemize}
        \item In multi-class tasks (e.g., classifying digits 0--9), we want a probability distribution over possible classes.
        \item The largest probability in the softmax output is chosen as the predicted class.
    \end{itemize}
    \item \textbf{Regularization in Practice:}
    \begin{itemize}
        \item \textbf{Dropout:} Encourages each neuron to not rely on specific other neurons, yielding more robust features (akin to an ensemble of sub-networks).
        \item \textbf{Early Stopping:} Prevents training for so long that the model memorizes the training set noise.
        \item \textbf{Data Augmentation:} Particularly impactful in image recognition tasks (e.g., \textit{ImageNet}, \textit{MNIST}) to artificially enlarge the dataset.
    \end{itemize}
    \item \textbf{Real-World Example: Image Classification}
    \begin{itemize}
        \item \textbf{Task:} Identifying objects in photos among many categories (dogs, cats, cars, etc.).
        \item \textbf{Softmax Output:} Probability of each category is returned; the top score is the predicted label.
        \item \textbf{Regularization:} 
            \begin{itemize}
                \item \textit{Dropout} to ensure the network generalizes across diverse features.
                \item \textit{Data Augmentation} (flip, rotate, zoom images) to simulate more training data.
                \item \textit{Weight Decay} to avoid overly large parameter values that overfit the training set.
            \end{itemize}
    \end{itemize}
\end{itemize}

\subsection{Summary}

\begin{itemize}
    \item The \textbf{softmax output layer} is key for multi-class classification, returning a probability distribution over classes.
    \item \textbf{Regularization} (weight decay, dropout, early stopping, data augmentation) helps control overfitting, which is especially crucial for deep ANNs.
    \item More \textbf{advanced optimizers} provide faster convergence and better performance in practice.
    \item Building ANN models in frameworks like TensorFlow/Keras allows us to quickly test, tune, and deploy models for real-world use cases.
\end{itemize}

\section{Deep Network Challenges and Convolutional Neural Networks}

\textbf{Oversimplified TLDR:}
\begin{itemize}
    \item \textbf{Weight Initialization:} If weights in the same layer are all identical, we lose diversity of neuron behavior (symmetry problem). Proper initialization heuristics (e.g., Xavier, He) reduce vanishing/exploding gradients.
    \item \textbf{Vanishing/Exploding Gradients:} In very deep networks, gradients can become extremely small (vanish) or extremely large (explode), hindering stable training.
    \item \textbf{Activation Functions:} Sigmoid and tanh can cause vanishing gradients. ReLU is more robust but can ``die'' for negative inputs. Leaky ReLU mitigates this.
    \item \textbf{CNNs:} Convolutional Neural Networks preserve spatial information in images via filters/kernels, pooling layers, and typically fewer parameters than fully connected models.
\end{itemize}

\subsection{Weight Initialization and Symmetry Problem}
\begin{itemize}
    \item \textbf{Symmetry Problem:} Initializing all weights in a layer to the same value causes identical updates for each neuron, preventing diverse feature extraction.
    \item \textbf{Bias Initialization:} Usually acceptable to initialize all biases to zero. Biases shift activation functions without breaking symmetry in the same way.
    \item \textbf{Guidelines for Weight Initialization:}
    \begin{itemize}
        \item \textbf{Xavier (Glorot) Initialization:} 
        \[
        w_{i,j} \sim \mathcal{N}\!\bigl(0,\,\sigma^2\bigr), 
        \quad 
        \sigma^2 = \frac{1}{n_{\text{avg}}}, 
        \quad
        n_{\text{avg}} = \tfrac{1}{2}\bigl(n_{\text{in}} + n_{\text{out}}\bigr).
        \]
        \item \textbf{He Initialization:} 
        \[
        \sigma^2 = \frac{2}{n_{\text{avg}}},
        \]
        often recommended for ReLU-type activations.
    \end{itemize}
\end{itemize}

\subsection{Vanishing and Exploding Gradients in Deep Networks}

\subsubsection{Vanishing Gradients}
\begin{itemize}
    \item \textbf{Definition:} The magnitude of gradients becomes extremely small in deeper layers, causing negligible weight updates.
    \item \textbf{Why It Happens:}
    \begin{itemize}
        \item \textbf{Sigmoid/Tanh Saturation:} For large positive/negative inputs, the derivative is near zero.
        \item Deep products of small derivatives compound (chain rule), leading to near-zero gradients in early layers.
    \end{itemize}
    \item \textbf{Consequence:} The earliest layers (closest to input) barely train, limiting representation learning.
\end{itemize}

\subsubsection{Exploding Gradients}
\begin{itemize}
    \item \textbf{Definition:} Gradient values grow exponentially through back-propagation, potentially causing numerical instability (NaN or infinite values).
    \item \textbf{Why It Happens:}
    \begin{itemize}
        \item Large weight magnitudes and repeated multiplications can amplify gradients.
        \item Deep products of derivatives greater than 1 explode exponentially.
    \end{itemize}
    \item \textbf{Consequence:} Training becomes unstable, and weight updates can overshoot the loss minimum.
\end{itemize}

\subsection{Activation Functions in Hidden Layers}
\begin{itemize}
    \item \textbf{Sigmoid:} 
    \[
    f(x) = \frac{1}{1 + e^{-x}}.
    \]
    \begin{itemize}
        \item Saturates at 0 or 1, leading to small gradients (vanishing problem).
        \item Computationally more expensive (involves exponentials).
    \end{itemize}
    \item \textbf{Tanh:}
    \[
    f(x) = \tanh(x) = \frac{e^{x} - e^{-x}}{e^{x} + e^{-x}}.
    \]
    \begin{itemize}
        \item Ranges from -1 to 1, can still saturate and cause vanishing.
        \item Derivatives are steeper than sigmoid, but the issue persists for large $|x|$.
    \end{itemize}
    \item \textbf{ReLU:}
    \[
    f(x) = \max(0,\,x).
    \]
    \begin{itemize}
        \item Faster computation: if $x > 0$, derivative is 1; if $x < 0$, derivative is 0.
        \item \textbf{Dying ReLU Problem:} Once a neuron's weights cause negative inputs, its gradient becomes 0 forever.
    \end{itemize}
    \item \textbf{Leaky ReLU:}
    \[
    f(x) = 
    \begin{cases}
       x & \text{if } x \ge 0,\\
       \alpha x & \text{if } x < 0,
    \end{cases}
    \]
    where $0 < \alpha \ll 1$. This alleviates the dying ReLU issue by maintaining a small slope for negative inputs.
\end{itemize}

\subsection{Convolutional Neural Networks (CNNs)}

\subsubsection{Motivation and Overview}
\begin{itemize}
    \item \textbf{Spatial Structure in Images:} Flattening a 2D image into a 1D vector loses crucial local information. Fully connected layers are often large and prone to overfitting.
    \item \textbf{Convolutions:} Enable local feature extraction with fewer parameters by applying small filters (kernels) that learn localized patterns (edges, corners, textures).
    \item \textbf{Multi-Channel Inputs/Outputs:} Images can have multiple channels (RGB), and convolutional layers often learn multiple filters (output channels) to detect diverse features.
\end{itemize}

\subsubsection{Convolution Operation}
\begin{itemize}
    \item \textbf{Definition (2D Case):} For a filter of size $k \times k$ slid over an image:
    \[
    \text{ConvOutput}[i,j] 
    = \sum_{p=0}^{k-1} \sum_{q=0}^{k-1} \bigl(\text{Image}[i+p,\, j+q]\bigr)\,\bigl(\text{Filter}[p,\,q]\bigr).
    \]
    \item \textbf{Padding:} 
    \begin{itemize}
        \item \textit{Valid Padding}: No extra border; output is smaller than input.
        \item \textit{Same Padding}: Add zeros around the image so the output dimension remains unchanged.
    \end{itemize}
    \item \textbf{Stride:} The step size for shifting the filter. A larger stride downsamples the feature map more aggressively.
\end{itemize}

\subsubsection{Pooling}
\begin{itemize}
    \item \textbf{Purpose:} Downsample the feature map to reduce dimensionality and control overfitting.
    \item \textbf{Max-Pooling:} Takes the maximum value in each local region (often more effective in practice than average-pooling).
    \item \textbf{Example:} $2\times 2$ max-pooling picks the largest value in each $2\times 2$ block.
\end{itemize}

\subsubsection{CNN Architecture}
\begin{itemize}
    \item \textbf{Feature Extraction:} Stacks of convolution + activation + pooling capture patterns at multiple scales, from simple edges to complex shapes.
    \item \textbf{Classification Stage:} Flatten the final feature maps into a vector and pass through fully connected layers, commonly ending with a softmax (for multi-class tasks).
\end{itemize}

\subsection{Intuitive Explanation and Real-World Examples}
\begin{itemize}
    \item \textbf{Weight Initialization:} Good initialization ensures that signals (and gradients) neither vanish nor explode across layers, especially in deep networks.
    \item \textbf{Vanishing/Exploding Gradients:} 
    \begin{itemize}
        \item \textit{Vanishing} leads to slow or no learning in early layers. 
        \item \textit{Exploding} leads to instability or NaN values.
    \end{itemize}
    \item \textbf{Convolutional Networks in Practice:}
    \begin{itemize}
        \item Commonly used in \textit{image classification}, \textit{object detection}, \textit{medical image analysis}, and more.
        \item Each convolutional filter learns specialized features (e.g., edges, textures). Pooling reduces spatial resolution while retaining the most important information.
    \end{itemize}
\end{itemize}

\subsection{Summary}
\begin{itemize}
    \item \textbf{Weight Initialization:} Diversify neuron starting points and maintain stable gradient flow with heuristics like Xavier or He.
    \item \textbf{Deep Network Pitfalls:} Vanishing and exploding gradients are major challenges, especially when using saturating activations like sigmoid.
    \item \textbf{Recommended Activations:} ReLU or variants (e.g., leaky ReLU) are preferred in many modern architectures to mitigate vanishing gradient issues.
    \item \textbf{Convolutional Neural Networks:} Harness local patterns, reduce parameters, and preserve spatial structure. Pooling layers further downsample intermediate feature maps for efficient and robust image understanding.
    \item \textbf{Practical Importance:} Weight initialization, activation choice, and CNN design are cornerstones for building successful deep learning models in computer vision and beyond.
\end{itemize}

\end{document}