Master Study Guide: Artificial Neural Networks and Machine Learning Foundations

Module 1: Foundations of Supervised Learning

1.1 Formal Setup and Terminology

Supervised learning aims to learn a function that maps an input vector to an output target value. An object is represented by a feature vector of length $d$:

$$x = (x^{(1)}, \dots, x^{(d)})^T$$

A dataset with $l$ objects and target values $y \in \mathbb{R}$ is represented by the data matrix $Z$:

$$Z = \begin{pmatrix} X \\ y^T \end{pmatrix}$$

where $X$ is a $d \times l$ matrix containing the feature vectors $x_i$ as columns, and $y$ is the target vector.

1.2 Generalization Error and Risk

The generalization error (or risk) measures how well a model $g(x; w)$ performs on unseen future data, defined as the expected loss:

$$R(g(\cdot; w)) = \mathbb{E}_z[L(y, g(x; w))] = \int_X \int_\mathbb{R} L(y, g(x; w)) p(x, y) dy dx$$

Because the true joint distribution $p(x, y)$ is unknown, we use Empirical Risk Minimization (ERM), minimizing the empirical risk over the training set:

$$R_{emp}(g(\cdot; w), Z) = \frac{1}{l} \sum_{i=1}^l L(y_i, g(x_i; w))$$

1.3 Bias-Variance Tradeoff

For the expected prediction error (EPE) at a point $x_0$ using quadratic loss, the error decomposes into three components:

$$EPE(x_0) = \mathbb{E}_{y|x_0, Z_l}[(y - g(x_0; w(Z_l)))^2]$$

$$EPE(x_0) = \text{noise} + \text{bias}^2 + \text{variance}$$

1. Noise: $Var(y|x_0)$ (Irreducible error)
2. Bias $^2$: $( \mathbb{E}_{y|x_0}[y|x_0] - \mathbb{E}_{Z_l}[g(x_0; w(Z_l))] )^2$
3. Variance: $\mathbb{E}_{Z_l}[ (g(x_0; w(Z_l)) - \mathbb{E}_{Z_l}[g(x_0; w(Z_l))])^2 ]$

An overly simple model yields high bias (underfitting), while a highly complex model yields high variance (overfitting).

Module 2: Probabilistic Framework and Linear Models

2.1 The Probabilistic Framework

Bayes' Theorem dictates the relationship between the joint, marginal, and conditional probabilities:

$$p(y|x) = \frac{p(x|y)p(y)}{p(x)}$$

For a Gaussian classifier, we assume $p(x|y)$ is normally distributed. The density of a $d$ -variate Gaussian $\mathcal{N}(\mu, \Sigma)$ is:

$$p(x) = \frac{1}{(2\pi)^{d/2}\sqrt{\det\Sigma}} \exp\left[ -\frac{1}{2} (x-\mu)^T\Sigma^{-1}(x-\mu) \right]$$

2.2 Linear and Polynomial Regression

Linear regression aims to find a function $g(x) = W^T x$ that minimizes the squared error. For a polynomial of degree $m$, the feature vector is expanded to $x = (1, x, x^2, \dots, x^m)^T$. Using the Vandermonde matrix $\tilde{X}$, the global minimum parameter vector $W$ is found explicitly via:

$$W = (\tilde{X}^T \tilde{X})^{-1} \tilde{X}^T y$$

Minimizing the squared error is mathematically equivalent to minimizing the negative log-likelihood under the assumption of Gaussian noise: $p(y_i|x_i) = \mathcal{N}(g(x_i), \sigma^2)$.

2.3 Logistic Regression and Softmax

For binary classification, logistic regression utilizes the sigmoid activation function:

$$g(x; W) = \sigma(W^T x) = \frac{1}{1 + e^{-W^T x}}$$

We minimize the cross-entropy loss (negative log-likelihood):

$$\min_W \left[ -\sum_i [y_i \ln g(x_i; W) + (1-y_i) \ln(1-g(x_i; W))] \right]$$

For multi-class settings ($M$ classes), this generalizes to the Softmax function:

$$p(y = j|x) = \frac{e^{W_j^T x}}{\sum_{k=1}^K e^{W_k^T x}}$$

Module 3: Support Vector Machines (SVM)

3.1 Linear SVMs (Hard Margin)

The objective is to find a separating hyperplane that maximizes the margin $2/\|w\|$.
Primal Problem:

$$\min \frac{1}{2} \|w\|^2$$

$$\text{subject to } y_i(w \cdot x_i - b) - 1 \ge 0 \quad \text{for } i = 1, \dots, l$$

Using the Lagrange function:

$$L(w, b; \alpha_1, \dots, \alpha_l) = \frac{1}{2}\|w\|^2 - \sum_{i=1}^l \alpha_i(y_i(w \cdot x_i - b) - 1)$$

the optimal weights become $w = \sum_{i=1}^l \alpha_i y_i x_i$.

Dual Problem:

$$\max_\alpha -\frac{1}{2} \alpha^T Q \alpha + 1^T \alpha$$

$$\text{subject to } \alpha^T y = 0 \text{ and } \alpha \ge 0$$

where $Q_{ij} = y_i y_j (x_i \cdot x_j)$.

3.2 C-SVMs (Soft Margin)

To handle non-linear separability caused by noise or outliers, slack variables $\xi_i \ge 0$ are introduced. The new primal problem minimizes $\frac{1}{2}\|w\|^2 + C \sum_i \xi_i$.
The dual problem remains largely identical but introduces an upper bound $C$ on the Lagrange multipliers:

$$0 \le \alpha_i \le C$$

3.3 Nonlinear SVMs (The Kernel Trick)

Data is transformed into a higher-dimensional Hilbert space $\mathcal{H}$ via a non-linear map $\Phi(x)$. Instead of computing dot products in $\mathcal{H}$, we use a positive semi-definite kernel function $k(x, x') = \Phi(x) \cdot \Phi(x')$.
Popular Kernels include:

• Polynomial: $k(x, x') = (x \cdot x' + \beta)^\alpha$
• Gaussian / RBF: $k(x, x') = \exp\left( -\frac{1}{2\sigma^2} \|x - x'\|^2 \right)$

The Dual Problem with a kernel becomes:

$$\max_\alpha \sum_{i=1}^l \alpha_i - \frac{1}{2} \sum_{i=1}^l \sum_{j=1}^l \alpha_i \alpha_j y_i y_j k(x_i, x_j)$$

Module 4: Tree-Based Models and Boosting

4.1 Decision Trees

Trees partition the feature space by splitting nodes. For categorical target values, the Gini Impurity is used to evaluate split quality:

$$I_G(Z) = 1 - \sum_{k=1}^M p_k(Z)^2$$

The Gini Purity Gain for a split $s$ into subsets $K_s$ is:

$$g_G(Z, s) = I_G(Z) - \sum_{t=1}^{K_s} \frac{|Z_{s,t}|}{|Z|} I_G(Z_{s,t})$$

4.2 Gradient Boosting

Boosting sequentially applies weak classifiers. In forward stagewise additive modeling, the model $g_N(x)$ is constructed as an expansion:

$$g_N(x) = \sum_{n=1}^N \beta_n b(x; \gamma_n)$$

At each step $n$, we solve:

$$(\beta_n, \gamma_n) = \arg\min_{\beta, \gamma} \sum_{i=1}^l L(y_i, g_{n-1}(x_i) + \beta b(x_i; \gamma))$$

Module 5: Artificial Neural Networks

5.1 Fully Connected Feed-Forward Neural Networks (MLP)

Neural networks use hidden layers to learn non-linear representations. The Universal Approximation Theorem proves that a network with a single hidden layer and a sigmoidal activation function $\phi$ can approximate any continuous function $f$:

$$F(x) = \sum_{i=1}^N \alpha_i \phi(w_i^T x + b_i)$$

where $|F(x) - f(x)| < \epsilon$.

In matrix-vector notation, the forward pass for layer $l$ computing activations $a^{[l]}$ and pre-activations $s^{[l]}$ is:

$$s^{[l]} = W^{[l]} a^{[l-1]} + b^{[l]}$$

$$a^{[l]} = \sigma^{[l]}(s^{[l]})$$

5.2 Convolutional Neural Networks (CNNs)

CNNs utilize local receptive fields, weight sharing, and striding. The discrete 2D convolution over channels $C$ and a spatial kernel $R \times R$ is computed as:

$$s_{a,b} = \sum_{c=0}^{C-1} \sum_{i=0}^{R-1} \sum_{j=0}^{R-1} w_{i,j,c} x_{a+i, b+j, c} = (W * x)_{a,b}$$

5.3 Recurrent Neural Networks (RNNs) and LSTMs

RNNs process sequences by combining the current input $x_t$ with the previous hidden state $h_{t-1}$:

$$h_t = f(W^T x_t + R^T h_{t-1} + b)$$

A major issue is the Vanishing Gradient Problem, which arises during Backpropagation Through Time (BPTT) due to the multiplication of Jacobian matrices:

$$\frac{\partial s(t)}{\partial s(t-l)} = \prod_{\tau=0}^{l-1} R \text{diag}[f'(s(t-\tau-1))]$$

Long Short-Term Memory (LSTM) architectures solve this via a gating mechanism around a cell state $c^t$. The core formulas are:

• Cell input: $z^t = g(W_z x^t + R_z y^{t-1} + b_z)$
• Input gate: $i^t = \sigma(W_i x^t + R_i y^{t-1} + b_i)$
• Forget gate: $f^t = \sigma(W_f x^t + R_f y^{t-1} + b_f)$
• Cell state update: $c^t = i^t \odot z^t + f^t \odot c^{t-1}$
• Output gate: $o^t = \sigma(W_o x^t + R_o y^{t-1} + b_o)$
• Hidden/Cell output: $y^t = o^t \odot h(c^t)$