Unit 1: Foundations of Machine Learning

1. Defining Machine Learning: Formalisms and Foundations

Machine Learning (ML) is an interdisciplinary branch of Computer Science and Artificial Intelligence that develops mathematical models and algorithms capable of extracting patterns from historical observations to make inferences on previously unseen data without explicit procedural programming.

CODECopy Code
+-----------------------------------------------------------------------------------+
|                        TRADITIONAL PROGRAMMING VS. MACHINE LEARNING               |
+-----------------------------------------------------------------------------------+
|  TRADITIONAL (PROCEDURAL) COMPUTATION:                                            |
|  [Input Data]  +  [Hand-Coded Rules / Algorithms]  ====>  [Computed Output]       |
+-----------------------------------------------------------------------------------+
|  MACHINE LEARNING (INDUCTIVE) PARADIGM:                                           |
|  [Input Data]  +  [Observed Outputs / Feedback]   ====>  [Learned Rules / Model] |
+-----------------------------------------------------------------------------------+

Classic and Formal Mathematical Definitions

• Arthur Samuel (1959): Coined the term Machine Learning as the "field of study that gives computers the ability to learn without being explicitly programmed."
• Tom M. Mitchell (1997) - The Operational Engineering Definition:

  "A computer program is said to learn from experience $\mathbf{E}$ with respect to some class of tasks $\mathbf{T}$ and performance measure $\mathbf{P}$, if its performance at tasks in $\mathbf{T}$, as measured by $\mathbf{P}$, improves with experience $\mathbf{E}$."

CODECopy Code
+-----------------------------------------------------------------------------------+
|                     THE MITCHELL (T, P, E) ENGINEERING TRIPLET                    |
+-----------------------------------------------------------------------------------+
| Problem Domain      | Task (T)               | Performance (P)   | Experience (E) |
+---------------------+------------------------+-------------------+----------------+
| Autonomous Driving  | Steering, braking, path| Miles driven with-| Sensor streams,|
|                     | planning on roads      | out intervention  | human steering |
+---------------------+------------------------+-------------------+----------------+
| Medical Imaging     | Classifying tumor scans| Diagnostic F1-    | Historical CT  |
|                     | as malignant or benign | score, Recall rate| scans & biop-  |
|                     |                        |                   | sies           |
+---------------------+------------------------+-------------------+----------------+
| Email Filtering     | Categorizing incoming  | Precision, Accu-  | User-flagged   |
|                     | messages (Spam vs Ham) | racy percentage   | spam & inbox   |
|                     |                        |                   | messages       |
+-----------------------------------------------------------------------------------+

Why Algorithmic Learning is Necessary

1. Rule Explosions: Tasks such as facial recognition, continuous speech decoding, or natural language understanding involve high-dimensional inputs with nonlinear combinatorial variations that defy manual if-else heuristic rule codification.
2. Dynamic Non-Stationary Environments: In fraud detection, network intrusion monitoring, and market trading, behavioral patterns evolve continuously. Static code degrades rapidly; ML algorithms continuously adapt by consuming new experience.
3. Hidden Phenomenological Knowledge: In bioinformatics (e.g., protein folding, genomic sequencing), human experts cannot articulate explicit mathematical mappings because the underlying biological laws remain partially unknown.

2. Paradigms of Machine Learning

Machine Learning methodologies are classified into distinct learning paradigms based on the nature, structure, and availability of feedback signals during training.

CODECopy Code
+-----------------------------------------------------------------------------------+
|                         MACHINE LEARNING PARADIGM TAXONOMY                        |
+-----------------------------------------------------------------------------------+
| Paradigm            | Training Data Structure   | Feedback Signal | Primary Goals |
+---------------------+---------------------------+-----------------+---------------+
| Supervised Learning | Pairs: $(x_i, y_i)$       | Ground-truth    | Approximation |
|                     | Feature vectors + Labels  | target values   | of function   |
|                     |                           |                 | $f: X \to Y$  |
+---------------------+---------------------------+-----------------+---------------+
| Unsupervised        | Unlabeled: $\{x_i\}$      | Zero explicit   | Structure     |
| Learning            | Feature vectors only      | labels; internal| discovery,    |
|                     |                           | density/distance| density estim.|
+---------------------+---------------------------+-----------------+---------------+
| Semi-Supervised     | Small labeled set $S_L$ + | Partial ground- | Leverage mass-|
| Learning            | large unlabeled set $S_U$ | truth feedback  | ive unlabeled |
|                     |                           |                 | data via geom.|
+---------------------+---------------------------+-----------------+---------------+
| Reinforcement       | State transitions:        | Scalar reward / | Optimal policy|
| Learning (RL)       | $(s_t, a_t, r_t, s_{t+1})$| penalty signals | $\pi(a|s)$ for|
|                     | Agent-environment loop    | (often delayed) | max cumulative|
|                     |                           |                 | return        |
+-----------------------------------------------------------------------------------+

Detailed Evaluation of Learning Paradigms

A. Supervised Learning

The model is provided with a training dataset of $m$ input-output exemplars:
$S = \{(x_1, y_1), (x_2, y_2), \dots, (x_m, y_m)\} \subset \mathcal{X} \times \mathcal{Y}$

• Regression Tasks: The output space $\mathcal{Y}$ is continuous (e.g., $\mathcal{Y} \subseteq \mathbb{R}$).
  • Examples: Forecasting electrical grid load, estimating life expectancy, predicting real estate asset valuations.
• Classification Tasks: The output space $\mathcal{Y}$ consists of a discrete set of nominal class identifiers.
  • Binary Classification: $\mathcal{Y} = \{0, 1\}$ or $\mathcal{Y} = \{-1, +1\}$ (e.g., Credit default prediction).
  • Multiclass Classification: $\mathcal{Y} = \{1, 2, \dots, K\}$ where each instance belongs to exactly one of $K$ mutually exclusive classes (e.g., Handwritten digit recognition: $K = 10$).
  • Multilabel Classification: $\mathcal{Y} \subseteq \{1, 2, \dots, K\}$ where an instance can simultaneously possess multiple labels (e.g., tagging an article with multiple topics: Tech, Finance, Politics).

B. Unsupervised Learning

The model receives observations without supervisory ground-truth annotations:
$S = \{x_1, x_2, \dots, x_m\} \subset \mathcal{X}$

• Clustering: Partitioning observations into homogeneous clusters such that intra-cluster pairwise similarity is maximized while inter-cluster similarity is minimized (e.g., K-Means, DBSCAN, Agglomerative Hierarchical Clustering).
• Dimensionality Reduction: Compressing high-dimensional feature spaces $\mathbb{R}^d$ into a lower-dimensional manifold $\mathbb{R}^k$ ($k \ll d$) while preserving variance, pairwise geometric distances, or topological relationships (e.g., Principal Component Analysis, t-SNE, UMAP).
• Density Estimation & Anomaly Detection: Estimating the underlying probability density function $p(x)$ to identify low-density outliers representing fraudulent credit transactions or equipment failures (e.g., Isolation Forests, Gaussian Mixture Models).
• Association Rule Mining: Discovering conditional co-occurrence dependencies within transactional itemsets (e.g., Market Basket Analysis using Apriori or FP-Growth).

C. Reinforcement Learning (RL)

Rather than passive data consumption, an autonomous Agent interacts with a dynamic Environment modeled as a Markov Decision Process (MDP):

• Core Loop: At time step $t$, the agent observes environment state $s_t \in \mathcal{S}$, executes action $a_t \in \mathcal{A}$ governed by its policy $\pi(a_t|s_t)$, receives scalar reward $r_t \in \mathbb{R}$, and transitions to next state $s_{t+1} \in \mathcal{S}$.
• Credit Assignment Dilemma: Feedback is frequently delayed. An agent executing 40 chess moves receives zero reward until a final checkmate; isolating which intermediate move caused victory or defeat represents the temporal credit assignment challenge.
• Exploration vs. Exploitation Trade-off: The agent must balance exploiting known high-reward actions against exploring unknown actions to discover potentially superior long-term strategies.

3. Core Practical Challenges in Machine Learning

Developing effective machine learning systems requires managing theoretical and practical data pitfalls:

CODECopy Code
+-----------------------------------------------------------------------------------+
|                        MACHINE LEARNING FAILURE MODES                             |
+-----------------------------------------------------------------------------------+
| Data-Side Failures                                Model-Side Failures             |
+-------------------------------------------------+---------------------------------+
| 1. Insufficient Sample Size                     | 1. Overfitting (High Variance)  |
| 2. Non-Representative Data (Sampling Bias)      | 2. Underfitting (High Bias)     |
| 3. Data Contamination (Noise & Outliers)        | 3. Curse of Dimensionality      |
| 4. Data Leakage & Feature Drift                 | 4. Inductive Bias Mismatch      |
+-----------------------------------------------------------------------------------+

Detailed Analysis of Failure Modes

1. Sampling Bias & Non-Representative Data: If the training sample distribution $\mathcal{D}_{\text{train}}$ diverges from the real-world inference distribution $\mathcal{D}_{\text{test}}$, the model exhibits sampling bias. (e.g., Training a facial recognition system exclusively on light-skinned subjects produces catastrophic error rates on dark-skinned subjects).
2. Data Contamination, Label Noise & Outliers: Mislabeled training examples, sensor glitches, or extreme outliers corrupt boundary optimization. Algorithms that aggressively minimize training error can distort their decision surfaces to accommodate corrupted data points.
3. The Curse of Dimensionality: Formulated by Richard Bellman. As the feature dimension $d$ increases, the volume of the feature space grows exponentially ($V \propto r^d$):
   • Data points become exponentially sparse, and the distance between any two random points converges to an identical constant.
   • Nearest-neighbor and distance-based metrics lose discriminatory power, demanding exponentially larger datasets to avoid severe overfitting.
4. Data Leakage: Occurs when training data accidentally incorporates features that encapsulate ground-truth target information that would never be available at actual inference time (e.g., including an internal hospital patient discharge ID when training a model to predict mortality upon emergency admission).

4. The Statistical Learning Framework

To formalize machine learning mathematically, statistical learning theory establishes a rigorous probabilistic framework.

CODECopy Code
+-----------------------------------------------------------------------------------+
|                     THE STATISTICAL LEARNING ARCHITECTURE                         |
+-----------------------------------------------------------------------------------+
|  Unknown Data Distribution D over Instance Space X                                |
|  Deterministic Target Labeling Function f: X -> Y (or Joint Distribution D(X,Y))  |
|                                       │                                           |
|                                       v [Sample m instances i.i.d.]               |
|  Training Set: S = {(x_1, y_1), (x_2, y_2), ..., (x_m, y_m)}                     |
|                                       │                                           |
|                                       v                                           |
|  Learning Algorithm A  <--- [Constrained by Hypothesis Space H]                   |
|                                       │                                           |
|                                       v                                           |
|  Candidate Hypothesis: h: X -> Y                                                  |
|                                       │                                           |
|                                       v                                           |
|  Evaluated on Generalization Risk: L_(D,f)(h) = E_x~D [ loss(h(x), f(x)) ]        |
+-----------------------------------------------------------------------------------+

Mathematical Definitions

1. Domain, Label & Training Sets

• Domain Set ($\mathcal{X}$): The input space of all possible feature vectors (e.g., $\mathcal{X} = \mathbb{R}^d$).
• Label Set ($\mathcal{Y}$): The output space of all possible target labels (e.g., $\mathcal{Y} = \{0, 1\}$ for binary classification).
• Training Set ($S$): A finite sequence of $m$ input-output pairs $S = ((x_1, y_1), \dots, (x_m, y_m))$ generated independently and identically distributed (i.i.d.) from an unknown probability distribution $\mathcal{D}$ over $\mathcal{X}$.

2. Loss Functions ($\ell$)

A loss function $\ell: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}^+$ quantifies the penalty incurred when the model predicts $\hat{y} = h(x)$ while the true target is $y$:

• Zero-One Loss ($\ell_{0-1}$) for Classification:
  $\ell_{0-1}(h(x), y) = \begin{cases} 0 & \text{if } h(x) = y \\ 1 & \text{if } h(x) \neq y \end{cases}$
• Squared Loss ($\ell_{\text{sq}}$) for Regression:
  $\ell_{\text{sq}}(h(x), y) = (h(x) - y)^2$
• Absolute Loss ($\ell_{\text{abs}}$) for Robust Regression:
  $\ell_{\text{abs}}(h(x), y) = |h(x) - y|$
• Cross-Entropy / Log Loss for Probabilistic Classification:
  $\ell_{\text{log}}(\hat{p}, y) = - [y \ln(\hat{p}) + (1 - y) \ln(1 - \hat{p})]$

3. Generalization Error (True Risk / Expected Loss)

The ultimate objective of machine learning is to identify a hypothesis $h$ that minimizes expected loss over the entire underlying population distribution $\mathcal{D}$:
$L_{(\mathcal{D}, f)}(h) \triangleq \mathbb{E}_{x \sim \mathcal{D}} [\ell(h(x), f(x))] = \mathbb{P}_{x \sim \mathcal{D}}[h(x) \neq f(x)]$

• The Fundamental Challenge: Because the true distribution $\mathcal{D}$ and the true labeling function $f$ are unknown to the learner, True Risk cannot be computed directly. The learner observes only the finite training sample $S$.

5. Empirical Risk Minimization (ERM) & Inductive Bias

Because True Risk is unobservable, learning algorithms deploy Empirical Risk Minimization (ERM) as a statistical proxy.

Definition of Empirical Risk

The Empirical Risk (Training Error) is the average loss computed over the finite training dataset $S$:
$L_S(h) \triangleq \frac{1}{m} \sum_{i=1}^m \ell(h(x_i), y_i)$

The Fallacy of Pure ERM (Overfitting Catastrophe)

If an algorithm attempts to minimize $L_S(h)$ over the unconstrained set of all possible mathematical functions ($\mathcal{H}_{\text{all}} = \mathcal{Y}^\mathcal{X}$):

• The algorithm can construct a "memorization hypothesis" $h_{\text{memo}}$:
  $h_{\text{memo}}(x) = \begin{cases} y_i & \text{if } x = x_i \in S \\ \text{arbitrary default} & \text{if } x \notin S \end{cases}$
• For this hypothesis:
  $L_S(h_{\text{memo}}) = 0 \quad (\text{Zero Empirical Training Error!})$
  $L_{(\mathcal{D}, f)}(h_{\text{memo}}) \approx 1 \quad (\text{Catastrophic Generalization Failure!})$
• Pure ERM over an unconstrained function space leads directly to Overfitting (memorizing sample noise rather than generalizable underlying signal).

Inductive Bias: The Antidote to Overfitting

To guarantee that an algorithm that performs well on training data will generalize to unseen data, we must constrain the learning algorithm prior to observing data. This restriction is known as Inductive Bias.

CODECopy Code
+-----------------------------------------------------------------------------------+
|                        CATEGORIES OF INDUCTIVE BIAS                               |
+-----------------------------------------------------------------------------------+
| Bias Form           | Operational Mechanism         | Concrete Algorithm Example  |
+---------------------+-------------------------------+-----------------------------+
| Restriction Bias    | Restricts the search space to | Linear Classifiers:         |
| (Language Bias)     | a predefined Hypothesis Class | Mandates linear hyperplanes |
|                     | $\mathcal{H}$ ($h \in \mathcal{H}$)       | $h(x) = \text{sign}(w^T x + b)$ |
+---------------------+-------------------------------+-----------------------------+
| Preference Bias     | Retains an expressive space   | Regularization & Decision   |
| (Search Bias)       | but prefers simpler hypotheses| Trees: Minimizes depth or   |
|                     | (Occam's Razor principle)     | penalizes $\|w\|_2^2$ norms |
+-----------------------------------------------------------------------------------+

The No-Free-Lunch Theorem

Formulated by David Wolpert:

"No single machine learning algorithm outperforms random guessing when averaged over all possible data-generating distributions."

• Implication: There is no universal "master algorithm." Every effective learning algorithm must incorporate an Inductive Bias matched to the underlying geometric structure of the specific problem domain.

6. PAC Learning: Probably Approximately Correct

Introduced by Turing Award laureate Leslie Valiant (1984), the Probably Approximately Correct (PAC) framework provides the foundational mathematical theory defining what is learnable.

CODECopy Code
+-----------------------------------------------------------------------------------+
|                          THE DUAL METRICS OF PAC LEARNING                         |
+-----------------------------------------------------------------------------------+
|  "APPROXIMATELY CORRECT"               "PROBABLY"                                 |
|  Accuracy Parameter: \epsilon          Confidence Parameter: \delta               |
|                                                                                   |
|  - Error bound:                        - Failure probability bound:               |
|    L_(D,f)(h) <= \epsilon              P[ L_(D,f)(h) > \epsilon ] <= \delta       |
|                                                                                   |
|  - Interpretation:                     - Interpretation:                          |
|    "Hypothesis error is at most        - "We are (1 - \delta) confident that      |
|    5% (if \epsilon = 0.05)"              the training sample is representative"   |
+-----------------------------------------------------------------------------------+

Why "Probably" and "Approximately"?

1. Why Approximately? Because the training sample $S$ covers only a tiny finite subset of the universe $\mathcal{X}$, demanding zero error ($\epsilon = 0$) would require seeing every conceivable data point, which is impossible in continuous spaces.
2. Why Probably? Because $S$ is drawn randomly according to distribution $\mathcal{D}$, there is always an infinitesimally small probability that the sample drawn is completely unrepresentative (e.g., drawing 100 non-smoking lung cancer patients by pure bad luck). We tolerate a failure probability $\delta$, demanding confidence $1 - \delta$.

Formal Mathematical PAC Definition

A hypothesis class $\mathcal{H}$ is PAC-learnable if there exists a learning algorithm $A$ and a polynomial function $m_{\mathcal{H}}(\epsilon, \delta)$ such that:

• For every distribution $\mathcal{D}$ over $\mathcal{X}$,
• For every target concept $f \in \mathcal{H}$ (Realizability Assumption),
• For every accuracy parameter $\epsilon \in (0, 1/2)$,
• For every confidence parameter $\delta \in (0, 1/2)$,
  When algorithm $A$ is given a sample $S$ of size:
  $m \ge m_{\mathcal{H}}(\epsilon, \delta)$
  the algorithm outputs a hypothesis $h_S \in \mathcal{H}$ satisfying:
  $\mathbb{P}_{S \sim \mathcal{D}^m} \Big[ L_{(\mathcal{D}, f)}(h_S) \le \epsilon \Big] \ge 1 - \delta$

Sample Complexity for Finite Hypothesis Classes

For any finite hypothesis class $\mathcal{H}$, under the Realizability assumption (where a hypothesis $h^* \in \mathcal{H}$ exists with $L_{(\mathcal{D}, f)}(h^*) = 0$):
$m_{\mathcal{H}}(\epsilon, \delta) \le \left\lceil \frac{1}{\epsilon} \left( \ln|\mathcal{H}| + \ln\left(\frac{1}{\delta}\right) \right) \right\rceil$

CODECopy Code
+-----------------------------------------------------------------------------------+
|                   SAMPLE COMPLEXITY SENSITIVITY RELATIONSHIPS                     |
+-----------------------------------------------------------------------------------+
| Parameter Varied    | Mathematical Dependency   | Operational Interpretation      |
+---------------------+---------------------------+---------------------------------+
| Accuracy ($\epsilon$)     | Inversely Linear ($1/\epsilon$) | Halving allowed error requires  |
|                     |                           | doubling training data sample   |
+---------------------+---------------------------+---------------------------------+
| Confidence ($\delta$)   | Logarithmic ($\ln(1/\delta)$)   | Increasing confidence from 90%  |
|                     |                           | to 99% requires minimal samples |
+---------------------+---------------------------+---------------------------------+
| Class Size ($|\mathcal{H}|$) | Logarithmic ($\ln|\mathcal{H}|$)   | Exponentially richer function   |
|                     |                           | spaces require linear data scale|
+-----------------------------------------------------------------------------------+

Agnostic PAC Learning (Relaxing Realizability)

In real-world data, the target concept rarely resides perfectly within $\mathcal{H}$, and data contains noise (probabilistic labeling $P(Y|X)$).

• Agnostic PAC Framework: Removes the realizability assumption. The learner cannot guarantee error $\le \epsilon$; instead, it guarantees that its error is within $\epsilon$ of the best possible hypothesis inside $\mathcal{H}$:
  $\mathbb{P}_{S \sim \mathcal{D}^m} \left[ L_{\mathcal{D}}(h_S) \le \min_{h' \in \mathcal{H}} L_{\mathcal{D}}(h') + \epsilon \right] \ge 1 - \delta$
• Agnostic Sample Complexity Bound:
  $m_{\mathcal{H}}^{\text{agnostic}}(\epsilon, \delta) \le \left\lceil \frac{2}{\epsilon^2} \left( \ln(2|\mathcal{H}|) + \ln\left(\frac{1}{\delta}\right) \right) \right\rceil$
  Notice the penalty: Sample complexity scales with $1/\epsilon^2$ rather than $1/\epsilon$.

7. The Bias-Variance Tradeoff

The prediction error of any supervised model decomposes mathematically into three distinct components:

$\text{Expected Test MSE} = \text{Bias}^2 + \text{Variance} + \text{Irreducible Error } (\sigma^2)$

CODECopy Code
+-----------------------------------------------------------------------------------+
|                        BIAS-VARIANCE DECOMPOSITION MATRIX                         |
+-----------------------------------------------------------------------------------+
| Metric               | High Bias (Underfitting)     | High Variance (Overfitting) |
+----------------------+------------------------------+-----------------------------+
| Model Complexity     | Too simple (e.g. Linear)     | Too complex (e.g. Deep Tree)|
| Assumptions Made     | Strong, rigid assumptions    | Weak, loose assumptions     |
| Training Set Error   | High (poor fit on training)  | Low (near-zero error)       |
| Test Set Error       | High (comparable to train)   | High (huge gap from train)  |
| Sensitivity to Data  | Low (consistent across splits| High (drastic model changes)|
| Remediation Strategy | Increase model capacity, add | Regularize ($\ell_1/\ell_2$), gather data, |
|                      | features, reduce penalty     | feature selection, ensemble |
+-----------------------------------------------------------------------------------+

CODECopy Code
Total Error
   ^
   |        \                      /  Total Error = Bias^2 + Variance + Noise
   |         \                    /
   |          \    Optimal       /
   |           \   Complexity   /
   |            \     |        /           Variance
   |  Bias^2     \    v       /           /
   |   \          \__________/           /
   |    \                               /
   |     \-----------------------------/
   |-----------------------------------------> Model Complexity

8. Comprehensive Foundations Reference Matrix

CODECopy Code
+------------------------------------------------------------------------------------------------------+
|                                   MACHINE LEARNING FOUNDATIONS MATRIX                                |
+------------------------------------------------------------------------------------------------------+
| Core Concept      | Mathematical Formulation                 | Practical Engineering Significance    |
+-------------------+------------------------------------------+---------------------------------------+
| Learning Triplet  | $T$ (Task), $P$ (Metric), $E$ (Experience)| Standard framework for problem framing|
+-------------------+------------------------------------------+---------------------------------------+
| True Risk         | $L_{(\mathcal{D},f)}(h) = \mathbb{E}[\ell(h(x), f(x))]$   | Unobservable true generalization error|
+-------------------+------------------------------------------+---------------------------------------+
| Empirical Risk    | $L_S(h) = \frac{1}{m} \sum \ell(h(x_i), y_i)$| Observable training set proxy error   |
+-------------------+------------------------------------------+---------------------------------------+
| Inductive Bias    | Restriction to Hypothesis Class $\mathcal{H}$     | Mandatory constraint to stop overfit  |
+-------------------+------------------------------------------+---------------------------------------+
| PAC Bounds        | $m \ge \frac{1}{\epsilon}(\ln|\mathcal{H}| + \ln(1/\delta))$| Formal data requirements for learning |
+-------------------+------------------------------------------+---------------------------------------+
| Error Split       | $\text{Error} = \text{Bias}^2 + \text{Var} + \sigma^2$   | Guides model complexity tuning        |
+------------------------------------------------------------------------------------------------------+