Comprehensive University Study Notes: Machine Learning and Deep Learning Fundamental Deep Learning

Page 1: Statistics Reminders for Machine Learning

A random variable (RV) is defined as a mathematical function that assigns a numerical value to every possible outcome of a random experiment. A random experiment is characterized as an event whose outcome cannot be predicted with total certainty. Random variables are categorized based on the nature of the values they assume:

• Discrete Random Variables: These take values from a countable set $X = \{x_1, x_2, \dots, x_n\}$. The set of outcomes is finite or countably infinite (e.g., the set of positive integers $\mathbb{N}$), but never uncountably infinite like the set of real numbers $\mathbb{R}$.

  • Verbatim Example: The roll of a six-sided die, where the random variable assumes one of the discrete values in the set $\{1, 2, 3, 4, 5, 6\}$.

• Continuous Random Variables: These take values within a continuous set $X$, containing an infinite number of elements that usually form a continuum or an interval of real numbers. Unlike discrete variables, these values are not isolated points.

Probability Distributions

To quantify the likelihood of these values, we utilize mathematical functions known as probability distributions:

• Probability Mass Function (PMF): Used for discrete variables, denoted as $P(X = x)$. It assigns a probability between 0 and 1 to each specific value $x$, ensuring the sum of all probabilities over the set equals 1.

• Probability Density Function (PDF): Used for continuous variables, denoted as $p(x)$, where $p(x) \geq 0$. Probabilities are calculated by integrating the density over a specific interval. The total area under the PDF curve across the domain must equal 1.

Expected Value and Variance

The Expected Value (or expectation) of a function $f(x)$ relative to a distribution represents the long-term average value observed after many samples.

• For Discrete RVs: $E[f(x)] = \sum_{x} P(x)f(x)$

• For Continuous RVs: $E[f(x)] = \int p(x)f(x)$.

Variance measures the dispersion of values around the expected value: $Var(f(x)) = E[(f(x) - E[f(x)])^2]$

Page 2: Variability and Statistical Principles

When variance is small, values of $f(x)$ cluster near the expected value. The Standard Deviation is the square root of the variance and provides variability in the same units as the variable.

Covariance measures the degree of linear relationship between two variables while reflecting their scale: $Cov(f(x), g(x)) = E[(f(x) - E[f(x)])(g(y) - E[g(y)])]$

The Law of Large Numbers (LLN)

The LLN states that as the number of trials or observations ($n$) increases, the sample average converges toward the theoretical expected value of the distribution. If an experiment is repeated many times, the observed average becomes increasingly precise. $\lim_{n \rightarrow \infty} \frac{1}{n} \sum_{i=1}^{n} f(x_i) \approx E[f(x)]$ where $x_i$ are independent samples of the random variable $X$.

• Verbatim Case Study: Rolling a fair six-sided die. Rolling it many times and averaging the outcomes will cause the mean to gradually approach $3.5$, which is the theoretical expectation.

• Machine Learning Connection: The LLN is foundational to ML, as the expected value of a function is frequently approximated by computing the average over a finite sample of observed data.

Page 3: Introduction to Machine Learning (ML)

Early AI systems were based on codified knowledge, relying on manually designed rules. These struggled in complex, uncertain environments because explicitly encoding every possible situation is extremely difficult. Machine Learning solves this by allowing systems to automatically extract patterns from raw data.

Tom M. Mitchell’s Definition (1997):
"A computer program is said to learn from experience E with respect to some task T and performance measure P if its performance at task T, as measured by P, improves with experience E."

Advanced Forms and Paradigms

• Deep Learning (DL): A subset of ML where machines learn to map inputs to outputs and automatically discover the most useful internal data representations for the task directly from raw data, reducing the need for manual feature design.

• Generative Models: Recent developments that go beyond outcome prediction to generate new data resembling training examples (e.g., text, images, or multimodal content using visual-language models).

ML Tasks and Features

Tasks are defined by how they process samples (sets of measurable characteristics called features). An example is represented by a feature vector $\mathbf{x} \in \mathbb{R}^n$.

• Image Recognition: Features are pixel intensity values.

• Housing Prediction: Features are size, location, and room count.

Common Tasks:

1. Classification: Assigning inputs to one of $k$ predefined categories. Function: $f: \mathbb{R}^n \rightarrow \{1, \dots, k\}$. Output is a label $y = f(x)$.

2. Regression: Predicting a continuous numerical value. Function: $f: \mathbb{R}^n \rightarrow \mathbb{R}$.

Page 4: Types of Learning Paradigms

In traditional programming, behavior is deterministic. In Machine Learning, the process is reversed; provided with data and outcomes, the system learns the mapping function. Major categories include:

• Supervised Learning: Training is performed on a labeled dataset $\{(x_1, f(x_1)), (x_2, f(x_2)), \dots, (x_n, f(x_n))\}$. The goal is to minimize prediction error against true labels. Algorithms: Naïve Bayes, Logistic Regression, Neural Networks.

• Unsupervised Learning: No labels are provided. The goal is to discover internal structures in observations $\{X_1, X_2, \dots, X_n\}$.

  • Clustering: Grouping similar data points.

  • Recommendations: Grouping users by preferences.

  • Precision Medicine: Personalizing therapies by grouping patients via clinical, genetic, and lifestyle data.

• Reinforcement Learning (RL): An agent interacts with an environment, receiving feedback (performance function $P$). The agent learns action $f(x)$ based on the environment state $x$, creating state sequences $(X_1, X_2, \dots, X_n)$.

  • Examples: Autonomous driving; Google DeepMind’s AlphaGo.

• Semi-supervised Learning: Uses a small amount of labeled data and a large amount of unlabeled data. The labels guide the learning process while the structure of the unlabeled data is leveraged for accuracy.

Page 5: Training Strategies and Logistics

The Training Set consists of data samples used for statistical optimization. The strategies for providing this data vary:

• Batch Learning: The algorithm receives all data in advance, performs a training phase, and then moves to a working phase without further learning. It assumes the underlying distribution of training and deployment data is identical.

• Distribution Shift (Caveat): If data distribution changes, performance degrades.

  • Example: A software trained to estimate age using only images of $22\text{--}30$ year-old Caucasian individuals will fail when applied to younger/older individuals or different ethnicities.

Page 6: Incremental and Lifelong Learning

• Incremental Learning: The training and working phases alternate. Data collected during the working phase is periodically used for new training sessions.

• Lifelong (Natural) Learning: Training and working phases occur simultaneously. The system solves new problems and uses immediate feedback to improve performance in real-time.

Page 7: Data Types and Representation

1. Numeric Data: Continuous or quantized (discrete) measurable characteristics (e.g., age, height, weight).

2. Categorical Data: Qualitative properties from a finite set (e.g., blood type). These require One-Hot Encoding to be processed by neural networks.

   • One-Hot Encoding Example: Blood type A is $[1, 0, 0, 0]$, B is $[0, 1, 0, 0]$, AB is $[0, 0, 1, 0]$, and O is $[0, 0, 0, 1]$. It avoids meaningful arithmetic operations on labels where no ordinal relationship exists (e.g., averaging blood types).

3. Structured Data: Sequences (audio), hierarchical trees (HTML), or general graphs (chemical compounds).

The Importance of Representation: Designers must process raw data to highlight signal over noise. While reducing resolution helps reduce noise, doing so excessively can remove subtle but valuable details, degrading performance (Signal-to-Noise Ratio dependency).

Page 8: The Learning Pipeline and Open vs. Closed Worlds

Three Stages of ML Learning:

1. Collection: Gathering relevant information.

2. Feature Extraction: Transforming data manually (domain expertise) or automatically.

3. Learning: Building the predictive model.

Closed-World vs. Open-World Systems:

• Closed-World: Assumes all inputs belong to known categories.

  • Example: A Euro banknote counter that only classifies denote values (€5, €10, etc.) based on length. It might mistakenly classify a blank paper of the same length as a €10 note.

• Open-World: Must distinguish between known categories and reject unknown or invalid inputs (e.g., using size, color patterns, and texture to verify it is actually a banknote).

Page 9: The Overfitting Problem and Hypothesis Spaces

We restrict the search for an unknown function $f$ to a parametrized family of functions known as the Hypothesis Space. Each hypothesis is defined by a parameter vector $\theta$.

• Example: Second-degree polynomials $f(x) = a_0 + a_1x + a_2x^2$ where $\theta = (a_0, a_1, a_2)$.

Optimization: $\theta^* = \arg\min_{\theta} L(\theta, Train)$ where $L$ is the loss function.

• Hyperparameters: Constants set manually before learning (e.g., the degree $M$ of a polynomial).

Gaussian Noise Example: If the true function is $f(x) = \sin(2\pi x) + e$ (where $e$ is Gaussian noise), the algorithm tries to approximate this using a model $f(x) = \sum_{j=0}^{M} a_jx^j$.

Page 10: Model Complexity and Empirical vs. Expected Error

Mean Squared Error (MSE): $Loss(a_0, \dots, a_M) = \frac{1}{N} \sum_{i=1}^{N} (t_i - f(x_i))^2$

• Overfitting (Variance Error): For an $N=10$ dataset, a 9th-degree polynomial has zero training error but diverges from the target function on unseen points by fitting the noise/space instead of the function.

• Underfitting: Occurs when the model is too simple to capture the relationship.

• Expected Error: Minimizing distance across the whole input space weighted by probability: $E_x[(f_{true}(x) - f(x))^2]$.

• Observations: If we had $N=100$ training points, a 9th-degree polynomial might not overfit. Complexity is relative to training set size.

Page 11: Bias, Variance, and the No Free Lunch Theorem

Total Error Components:

1. Bias: Error from overly simple models.

2. Variance: Error from overly complex models failing to generalize.

3. Noise: Irreducible intrinsic randomness.

No Free Lunch (NFL) Theorem: States there is no universal algorithm. If algorithm $A_1$ beats $A_2$ on problem $F_1$, there exists $F_2$ where $A_2$ is superior. $E_F[E_x[error_{A1}(F)] - E_x[error_{A2}(F)]] = 0$

Remote Sensing Example: Task: Classify satellite pixels into Residential, Sea, Cultivated, Forest, or Scrub using wavelength bands.

• Choosing features 3 and 4 makes the classes more separable than features 4 and 5.

Page 12-13: Generalization and Testing

Generalization is the ability to perform on unseen data. Training error is deceptive due to overfitting. A Test Set must be used for a reliable estimate: $E_x[Performance(f, x)] \approx \frac{1}{M} \sum_{j=1}^{M} Performance(f, x_j) \text{ where } x_j \in Test\,Set$

Requirements for Valid Testing:

• Large test set.

• Independent samples (of each other and the training set).

• Same probability distribution as real-world data.

Warning: Inspected errors on the test set to adjust the algorithm compromises independence. Testing must occur only after training is complete.

Page 14-15: Model Capacity and Quantitative Example

Capacity Trade-off:

• Underfitting regime: Both errors high (low capacity).

• Overfitting regime: Large gap between training and test error (high capacity).

Verbatim Math Example: Target: $f_{true}(x) = A$ if x < 5, else $B$. Input $x \sim U(0, 10)$, thus $p(x) = 0.1$. Hypothesis: $f_\theta(x) = A$ if x < \theta, else $B$. Expected Performance for $\theta$: $ExPerf(\theta, x) = \int_0^{10} p(x)Perf(\theta, x)dx = 0.1\min(\theta, 5) + 0.1(10 - \max(\theta, 5))$ Observations from training on 6 samples ($3A, 3B$) showed multiple optimal $\theta \in [4.85, 6.05]$. Testing can under- or over-estimate true performance depending on finite sample size.

Page 16-17: Validation and Cross-Validation

Validation Set: An independent third set used exclusively to tune hyperparameters (like polynomial degree) to avoid "leaking" test set info into the model.

K-Fold Cross-Validation:

1. Divide data into $K$ equal parts.

2. Train $K$ times, each time using one part as test and $K-1$ as training.

3. Average results.

   • High Variance in Folds: Indicates the dataset is unrepresentative or too small (e.g., $\pm 0.15$ variation).

• Leave-One-Out: $K = N$. Extremely expensive, used for very small datasets ($N \approx 100$).

Page 18: Data Augmentation

Augmentation increases dataset size artificially using valid transformations (rotation, scaling, blurring).

• Offline Augmentation: Transforming input $x$ into set $T' = \{x, \tau_1(x), \dots, \tau_k(x)\}$ and saving it.

• Online Augmentation: Transforming a sample randomly during each training iteration. Common in Neural Networks.

• Warning: Flipping a '6' upside down in digit recognition creates a '9', which is an invalid transformation.

Page 19: Regularization (Tikhonov/L2)

Regularization modifies the learning objective to penalize model complexity: $\theta^* = \arg\min_{\theta} L(\theta, Train) + \lambda R(\theta)$ where $\lambda$ controls regularization strength.

• L2 Regularization (Tikhonov): $R(\theta) = \sum_i a_i^2$. This forces the algorithm to prefer smaller coefficients in polynomials, smoothing the curve.

Page 20-22: Evaluation Metrics (Precision/Recall)

Accuracy and Confusion Matrix:

• Accuracy: $\frac{\text{samples correctly classified}}{\text{total samples}}$.

• Error: $1 - Accuracy$.

The Confusion Matrix (Binary):

• True Positive (TP), False Negative (FN), False Positive (FP), True Negative (TN).

• Precision: $\frac{TP}{TP+FP}$ (Correctness of positive predictions).

• Recall: $\frac{TP}{TP+FN}$ (Sensitivity to actual positives).

• F1-Score (Harmonic Mean): $2 \cdot \frac{Precision \times Recall}{Precision + Recall}$. This penalizes cases where one metric is very low.

Verbatim Example (Rare Disease): Disease prevalence $10^{-4}$. Test is 100% accurate for sick and 99% for healthy. If someone tests positive, Precision is only 1% because the population of healthy people is massive ($100$ FPs vs $1$ TP).

Page 23: ROC Curve and AUC

ROC (Receiver Operating Characteristic) Curve: Plots the True Positive Rate (Recall) vs. False Positive Rate ($FPR = \frac{FP}{FP+TN}$) as the operating threshold $\tau$ varies.

• AUC (Area Under Curve): A single-number measure of performance. Ideal $AUC = 1$.

Page 24-25: Neural Networks Foundations

Artificial Neural Networks (ANNs) are inspired by the human brain ($\approx 86 \times 10^9$ neurons).

McCulloch & Pitts Neuron (1943):

• Binary inputs $x_i$.

• Weights $w_i$ and Bias $w_0$.

• Net Input: $net = \sum_{i=1}^d i_n w_i + w_0$.

• Activation: Step function (all-or-nothing).

• Limitation: Can only solve linearly separable problems. Decision boundary is a hyperplane: $\sum_{i=1}^d w_i i_n + w_0 = 0$.

Page 26-27: Rosenblatt’s Perceptron and the XOR Problem

Rosenblatt’s Perceptron (1958): Introduced on-line learning weights updates: $w_i \leftarrow w_i + \eta(t_j - y_j)x_{ji}$ where $\eta$ is the learning rate.

Minsky & Papert (1969): Showed a single Perceptron cannot solve the XOR problem. This led to a decline in NN research until multi-layer networks emerged.

Page 28-29: Multi-Layer Perceptron (MLP)

Architecture: Feed-forward structure with Hidden Layers. Neurons use non-linear, differentiable activation functions.

• Layer Computation: $y^{[k]} = f^{[k]}(w^{[k]}y^{[k-1]})$.

• Universal Approximation Theorem (Cybenko, 1989): An MLP with one hidden layer and a continuous, non-polynomial activation function can approximate any continuous function on a compact domain with arbitrary precision $\epsilon$.

Page 30-33: Backpropagation and Gradient Descent

Gradient Descent: Updates weights in the direction of the negative gradient: $\mathbf{w}' = \mathbf{w} - \eta \cdot \nabla L(\mathbf{w})$

Backpropagation Phases:

1. Forward Pass: Calculate outputs and loss.

2. Backward Pass: Use the Chain Rule to compute gradients of the loss with respect to each weight, moving from the output layer back to the input.

Chain Rule for Hidden Layer Gradient: $\frac{\partial L}{\partial w_{jk}^h} = \frac{\partial L}{\partial z_j} \cdot f'_h(w_j^h \cdot x) \cdot x_k$ where $\frac{\partial L}{\partial z_j} = \sum_i \frac{\partial L}{\partial y_i} \cdot f'_O(w_i^O \cdot z) \cdot w_{ij}^O$.

Page 34-36: Stochastic Gradient Descent (SGD)

SGD: Approximates the true gradient (from the whole dataset) using a average over a Minibatch of $m$ samples.

• Epoch: One full pass through the training set.

• Minibatch size ($m$): Typically $32\text{--}1024$. Smaller $m$ varies more but saves memory; larger $m$ is stable.

• Weight Initialization: Must be random to break symmetry. If weights were identical, neurons would learn identical features.

Page 38-39: Momentum and Adaptive Rates

Momentum: Dampens oscillations and accelerates convergence by adding weight to past gradients. $\Delta w \leftarrow \mu \cdot \Delta w - \eta \frac{\partial L}{\partial w}$ $\mathbf{w} \leftarrow \mathbf{w} + \Delta w$

Optimizers: Adaptive methods (Adam, RMSprop) use different learning rates for each parameter based on historical updates.

Page 40-44: Regularization and Loss Functions

• L1 (Lasso): $L_{reg} = \sum |w_i|$. Promotes sparsity (feature selection).

• L2 (Ridge): $L_{reg} = \sqrt{\sum w_i^2}$. Penalizes large weights.

• Activation Functions:

  • Sigmoid: $\sigma(net) = \frac{1}{1 + e^{-net}}$. Range $[0, 1]$. Derivative: $\sigma(net)(1 - \sigma(net))$.

  • Tanh: Range $[-1, 1]$.

  • ReLU: $\max(0, net)$. Solves vanishing gradient.

MLP as Regressor:

• MSE: Optimal prediction is the Conditional Mean. Sensitive to outliers.

• MAE: Optimal prediction is the Conditional Median. Robust to outliers.

MLP as Binary Classifier:

• Binary Cross-Entropy (BCE): $L = -[t\ln(y) + (1-t)\ln(1-y)]$.

• Why not MSE? In saturated regions ($y \approx 1$ when $t=0$), MSE gradients vanish ($\approx 0$). BCE gradients remain large ($\approx 1$), ensuring learning continues.

Page 47-48: Multi-class Classification

Softmax Function: $y_k = \frac{e^{net_k}}{\sum_j e^{net_j}}$ Constrains outputs to sum to 1, creating a probability distribution.

Categorical Cross-Entropy (CCE): $L = -\sum_j t_j\ln(y_j)$. With Softmax, the gradient $\frac{\partial L}{\partial net_k} = y_k - t_k$ ensures the network pushes up the correct class score and pushes down all others concurrently.

Page 49-53: Competitive Networks and LVQ

Learning Vector Quantization (LVQ): Neurons compete; the "winner" with the smallest distance (Euclidean or Manhattan) is selected.

• Unsupervised LVQ: Winning weight moves toward input: $w_v \leftarrow w_v + \alpha(x - w_v)$. This partitions space into Voronoi cells.

• Supervised LVQ:

  • If Winner Class == Input Class: Move weight toward input.

  • If Winner Class != Input Class: Move weight away: $w_v \leftarrow w_v - \gamma(x - w_v)$.

Page 54-56: Manifold Learning and SOM

Manifold: A space that is locally Euclidean but globally complex (e.g., Earth's surface). Self-Organizing Map (SOM): Unsupervised grid of neurons. Updates the winner AND neighbors using a Neighborhood function $\theta(u, v, t)$, allowing the network to topology-preserve high-dimensional data in 2D or 3D.

Page 57-62: The Reject Option

Used when errors are costly ($C_e$) vs. manual processing ($C_r$). Rejection is beneficial if C_r < C_e.

Chow’s Algorithm: Reject if posterior probability y_v < \frac{C_e - C_r}{C_e - 1}.

Vento et al. Reliability Measures:

1. Confidence ($\psi_a$): Magnitude of max output ($y_v$).

2. Ambiguity ($\psi_b$): Difference between first and second highest outputs ($y_v - max_{i \neq v} y_i$).

Page 63-70: Deep Learning and CNNs

Historical Waves: Cybernetics, Connectionism, Deep Learning. Vanishing Gradient: Repeated multiplication of Sigmoid derivatives ($\approx 0.25$ max) causes gradients to reach zero in early layers. ReLU solves this ($f' = 1$ for net > 0).

CNN Innovations:

1. Local Connections: Receptive fields only look at small patches.

2. Weight Sharing: Same filter applies to all positions (Translation invariance).

3. Heterogeneous Layers: Alternating Convolution (feature discovery) and Pooling (subsampling).

AlexNet (2012): 5 Conv layers, 3 FC layers. used Dropout. Reduced ImageNet error from $25\%$ to $15.3\%$.

Page 71-77: Convolution Detail

Discrete Convolution: $s(t) = \sum x(t-a)w(a)$. CNN Operations:

• Strides: Step size of the filter.

• Padding: Adding zeros to preserve edge dimensions.

  • $W_{output} = \lfloor \frac{W_{in} - W_{kernel} + 2P}{stride} \rfloor + 1$.

• Pooling: Max vs Average. Reduces parameter space but loses fine details.

• Dropout: Randomly setting neurons to 0 with probability $1-p$ during training to prevent co-adaptation.

Page 81-85: Optimization Strategies

• Skip Connections (ResNet): $\frac{\partial L}{\partial x} = \frac{\partial L}{\partial y}(1 + \frac{\partial g}{\partial x})$. Allows direct gradient flow, bypassing unstable intermediate layers.

• Batch Normalization: Normalizes layer inputs to mean 0, variance 1. Reduces Internal Covariate Shift, decoupling layer updates.

• Auxiliary Heads: Extra outputs at intermediate layers providing direct gradients (e.g., GoogLeNet).

Page 86-98: Reinforcement Learning (RL)

Q-Learning: Learns expected value of action $a$ in state $s$. Bellman Equation: $Q(s, a) \approx r + \gamma \max_{a'} Q(s', a')$

Exploration vs. Exploitation:

• $\epsilon$-greedy policy: Choose best action with prob $1-\epsilon$, random action with prob $\epsilon$.

Actor-Critic (DDPG for continuous actions):

• Critic: Evaluates action value ($Q$).

• Actor: Predicts the best action (Policy $\pi$).

• Replay Buffer: Stores transitions to break correlation between consecutive samples.

• Target Networks: Uses frozen weights to construct the learning target, preventing the network from chasing a "moving target."