UNIT 4: MACHINE LEARNING FOUNDATIONS & APPLICATIONS (Robotics Context)

1. FOUNDATIONS OF MACHINE LEARNING

Learning Paradigms

• Supervised Learning: Model learns a mapping from inputs to outputs using labeled training data (X, y). Goal: Predict y for new X. Examples: Regression, Classification.

• Unsupervised Learning: Model finds hidden patterns or intrinsic structures in unlabeled data X. Examples: Clustering, Dimensionality Reduction.

• Reinforcement Learning: Agent learns to make decisions by performing actions in an environment to maximize cumulative reward. No labeled dataset; learns via trial-and-error with feedback (reward/punishment).

Hypothesis Spaces: Finite vs. Infinite

• Finite Hypothesis Space: A set of possible models with a limited, countable number of parameters/functions (e.g., all decision trees with depth ≤ 5).

  • Implication for Complexity: Complexity is bounded by the size of the space. Easier to control overfitting.

  • Implication for Generalization: With enough data, can find the best hypothesis in the space. Risk of underfitting if the true pattern isn't in the space.

• Infinite Hypothesis Space: A continuous or uncountably large set of models (e.g., all possible linear functions y = w₁x₁ + w₂x₂ + b with real-valued weights).

  • Implication for Complexity: Can represent extremely complex functions. High risk of overfitting to noise in training data.

  • Implication for Generalization: Requires explicit regularization (e.g., L1/L2 penalties) or constraints to prefer simpler models and ensure good performance on unseen data.

[!TIP] Exam Focus: Be prepared to state that infinite spaces offer high flexibility but need regularization to generalize, while finite spaces are inherently regularized but may lack expressive power.

2. SUPERVISED LEARNING: REGRESSION

Linear & Multiple Linear Regression

• Objective: Find the best-fit straight line (or hyperplane) that minimizes the difference between predicted and actual continuous values.

• Model: ŷ = β₀ + β₁x₁ + β₂x₂ + ... + βₙxₙ

• Cost Function: Sum of Squared Errors (SSE) or Mean Squared Error (MSE).

$$SSE = \sum_{i=1}^{m} (y_i - \hat{y}_i)^2$$

$$MSE = \frac{1}{m} SSE$$

• Convergence Objective: Minimize SSE/MSE using optimization (e.g., Gradient Descent or Ordinary Least Squares analytical solution: β = (XᵀX)⁻¹Xᵀy).

Logistic Regression

• Purpose: Used for binary classification (predicting probability of class 0 or 1).

• Model: Applies the logistic (sigmoid) function to a linear combination of inputs to squash output to [0,1].

$$\hat{p} = \sigma(z) = \frac{1}{1 + e^{-z}}, \quad \text{where } z = \beta_0 + \beta_1 x_1 + ...$$

• Comparison with Linear Regression:

  • Output: Logistic gives probability (0 to 1); Linear gives any real number.

  • Use Case: Logistic for classification (spam/not-spam); Linear for predicting continuous values (price, temperature).

  • Cost Function: Logistic uses Log Loss (Cross-Entropy), not SSE, because SSE is non-convex for classification.

[!TIP] Problem-Solving: For linear regression problems, set up the normal equations or use gradient descent update rule: β_j := β_j - α * ∂(SSE)/∂β_j.

3. SUPERVISED LEARNING: CLASSIFICATION

Support Vector Machines (SVM)

• Goal: Find the optimal separating hyperplane that maximizes the margin between two classes.

• Margin: The distance between the hyperplane and the nearest data points from each class.

• Support Vectors: The training points that lie exactly on the margin boundaries. They support (define) the margin and hyperplane. Only these points influence the final model.

• Optimization: Solve a constrained quadratic programming problem to maximize margin subject to correct classification constraints.

Decision Trees: ID3 Algorithm

• Core Idea: Recursively split the dataset into purer subsets using the feature that provides the highest Information Gain.

• Splitting Criteria:

  1. Entropy: Measures impurity/uncertainty of a set S.

$$Entropy(S) = -\sum_{i=1}^{c} p_i \log_2 p_i$$

    (`p_i` = proportion of class `i` in `S`, `c` = number of classes).

2.  **Information Gain (IG):** Reduction in entropy after splitting on attribute `A`.

$$IG(S, A) = Entropy(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} Entropy(S_v)$$

• Algorithm Steps:

  1. Start with all training examples at root.

  2. If all examples belong to one class, make a leaf with that class.

  3. Else, for each attribute, compute IG.

  4. Select attribute with highest IG as the splitting node.

  5. Recur on each branch with remaining examples/attributes.

Neural Networks & Activation Functions

• Multilayer Perceptron (MLP): Feedforward network with an input layer, one or more hidden layers, and an output layer.

• Role of Activation Functions:

  • Without them: An MLP would collapse to a single linear transformation (sum of weighted inputs), unable to learn complex nonlinear patterns.

  • With them (e.g., ReLU, Sigmoid, Tanh): Introduce nonlinearity at each neuron. This allows the network to approximate arbitrarily complex continuous functions (Universal Approximation Theorem).

  • Common Functions:

    • ReLU: f(z)=max(0,z) – Computationally efficient, mitigates vanishing gradient.

    • Sigmoid: f(z)=1/(1+e^{-z}) – Outputs probability, suffers from vanishing gradient.

    • Tanh: f(z)=(e^z - e^{-z})/(e^z + e^{-z}) – Zero-centered output.

[!TIP] Key Point: "Stacking linear layers with nonlinear activations is what gives deep networks their power."

4. UNSUPERVISED LEARNING: CLUSTERING

k-means Clustering

• Objective: Partition n points into k clusters to minimize within-cluster sum of squares (WCSS).

• Algorithm:

  1. Initialize: Randomly choose k data points as initial centroids.

  2. Assignment: Assign each point to the nearest centroid using Euclidean distance.

$$d(p, c) = \sqrt{\sum_{i=1}^{n} (p_i - c_i)^2}$$

3.  **Update:** Recalculate centroids as the mean of all points assigned to each cluster.

4.  **Repeat** steps 2 & 3 until centroids stabilize (or max iterations).

• Output: Final cluster assignments and centroids.

Hierarchical Clustering

• AGNES (Agglomerative Nesting): Bottom-up. Starts with each point as its own cluster. Iteratively merges the two closest clusters until one cluster remains or a stopping criterion is met.

• DIANA (Divisive Analysis): Top-down. Starts with all points in one cluster. Iteratively splits the most heterogeneous cluster until each point is its own cluster or a stopping criterion is met.

• Comparison:

  | Feature | AGNES (Agglomerative) | DIANA (Divisive) | | :--- | :--- | :--- | | Approach | Bottom-up (merging) | Top-down (splitting) | | Complexity | Generally O(n²) or higher | Generally more complex (O(2ⁿ)) | | Mistakes | Irreversible merges can be suboptimal | Early bad splits propagate | | Use Case | Common, intuitive, good for small datasets | Less common, computationally heavy |

Gaussian Mixture Models (GMM)

• Concept: Assumes data points are generated from a mixture of several Gaussian (Normal) distributions. Each cluster corresponds to one Gaussian.

• Modeling: Estimates parameters (μ mean, Σ covariance, π mixing coefficient) for each Gaussian using Expectation-Maximization (EM) algorithm.

• Suitability for Overlapping Clusters: Unlike k-means (which uses hard boundaries and spherical clusters), GMM provides soft assignments (probabilistic membership) and can model elliptical, overlapping clusters via covariance matrices.

[!TIP] Remember: k-means is a special case of GMM with equal, spherical covariances and hard assignments.

5. DIMENSIONALITY REDUCTION

Principal Component Analysis (PCA)

• Objective: Transform data into a new coordinate system such that the first principal component (PC) captures the greatest variance, the second PC (orthogonal to first) captures the next greatest, and so on.

• Steps:

  1. Standardize the data.

  2. Compute the covariance matrix.

  3. Compute eigenvectors and eigenvalues of the covariance matrix.

  4. Sort eigenvectors by decreasing eigenvalues; choose top k eigenvectors as principal components.

  5. Project original data onto the new k-dimensional subspace.

• Key: Maximizes variance retained in lower dimensions. Linear technique.

Locally Linear Embedding (LLE)

• Concept: A manifold learning technique. Assumes data lies on a low-dimensional manifold embedded in high-dimensional space.

• How it works:

  1. For each point, find its k nearest neighbors.

  2. Compute weights that best linearly reconstruct each point from its neighbors (preserves local geometry).

  3. Find low-dimensional embedding where these reconstruction weights remain valid (minimizes reconstruction error in low-D).

• Comparison with PCA:

  • PCA: Global linear method. Preserves global variance (largest eigenvalues).

  • LLE: Local nonlinear method. Preserves local neighborhood relationships. Better for nonlinear manifolds (e.g., Swiss roll, curved surfaces).

[!TIP] When to prefer LLE? When the high-dimensional data lies on a nonlinear manifold and preserving local structure is more important than preserving global variance.

6. ENSEMBLE METHODS

Bagging (Bootstrap Aggregating)

• Technique:

  1. Create B bootstrap samples (random sampling with replacement) from training data.

  2. Train B base learners (e.g., decision trees) independently on each sample.

  3. For classification: majority vote; for regression: average the predictions.

• Role in Variance Reduction: By averaging many high-variance models (like deep trees), bagging reduces overall variance without increasing bias significantly. Particularly effective for unstable learners.

Stacking

• Technique:

  1. Split training data into folds.

  2. Train multiple base learners (level-0 models) on training folds.

  3. Use these base learners to generate predictions on hold-out folds, creating a new meta-feature dataset.

  4. Train a meta-learner (level-1 model) on this new dataset to learn how to best combine the base learners' predictions.

• Role of Meta-learners: The meta-learner (often a simple linear model or logistic regression) is trained to weight the outputs of the diverse base models optimally, learning their strengths and weaknesses. This often leads to better performance than any single base model or simple voting/averaging.

Model Combination Schemes

7. PROBABILISTIC MODELS & BAYESIAN METHODS

Bayesian Belief Networks (BBNs)

• Construction Process:

  1. Define Nodes: Each node represents a random variable.

  2. Define Directed Edges: Draw arrow from parent (cause) to child (effect). Encodes conditional independence assumptions.

  3. Define Conditional Probability Tables (CPTs): For each node, specify P(Child | Parents). If no parents, specify prior P(Node).

• Joint Probability: The full joint distribution over all variables X₁, ..., Xₙ is the product of all local conditional probabilities.

$$P(X_1, ..., X_n) = \prod_{i=1}^{n} P(X_i | Parents(X_i))$$

Naïve Bayes Classifier

• Core Assumption: Conditional Independence. Given the class label C, all feature variables X₁, X₂, ..., Xₙ are conditionally independent.

$$P(X_1, X_2, ..., X_n | C) = \prod_{i=1}^{n} P(X_i | C)$$

• Simplification: This assumption reduces the number of parameters needed drastically. Instead of estimating P(X₁, X₂|C) for all combinations, we only need P(X_i|C) for each feature individually.

• Posterior vs. Prior:

  • Prior Probability P(C): Probability of class C before seeing any feature data (based on training frequency).

  • Posterior Probability P(C|X): Probability of class C given the observed feature vector X. This is what we predict.

$$P(C|X) \propto P(C) \prod_{i=1}^{n} P(X_i|C)$$

• Impact of Noise: The conditional independence assumption is often violated in real data (noise). This can lead to overly confident (miscalibrated) probability estimates, but the classifier can still be surprisingly accurate for ranking/classification (the "zero-one" loss).

[!TIP] Bayesian Inference Example (Covid Test):

Use Bayes' Theorem: P(D|+) = [P(+|D) * P(D)] / P(+).

1. P(D)=0.02 (prior), P(+|D)=0.95 (sensitivity), P(+|¬D)=0.01 (false positive rate).

2. P(+) = P(+|D)P(D) + P(+|¬D)P(¬D) = (0.95*0.02) + (0.01*0.98).

3. Compute P(D|+).

8. FREQUENT PATTERN MINING

Concept & Objective

• Objective: Discover interesting patterns (frequent itemsets, associations, correlations) from large transaction databases.

• Market Basket Analysis: Classic application. Finds sets of items (itemset) that frequently appear together in transactions.

• Key Metrics:

  • Support: Fraction of transactions containing the itemset.

$$supp(X) = \frac{|\{t_i : X \subseteq t_i\}|}{N}$$

*   **Confidence:** Conditional probability of item `Y` given item `X`.

$$conf(X \Rightarrow Y) = \frac{supp(X \cup Y)}{supp(X)}$$

k-Frequent Itemset Mining (Apriori-like)

• Core Principle (Apriori): All subsets of a frequent itemset must also be frequent. (Anti-monotone property).

• Algorithm Steps:

  1. Set k=1. Scan DB to find all frequent 1-itemsets (support ≥ min_supp).

  2. Iterate: To find frequent k-itemsets:

     • Generate candidate k-itemsets by joining frequent (k-1)-itemsets.

     • Prune: Remove candidates having any subset that is infrequent.

     • Scan DB to count support of remaining candidates.

     • Keep those with support ≥ min_supp.

  3. Increment k and repeat until no new frequent itemsets found.

• Problem-Solving: For a given min_supp and transaction table, systematically generate candidate sets, prune using the Apriori property, and count supports from the provided transactions.

9. CORE CONCEPTS & PROBLEM-SOLVING

Distance Metric: Euclidean Distance

• For two points p = (p₁, p₂, ..., pₙ) and q = (q₁, q₂, ..., qₙ):

$$d(p, q) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}$$

• Use: Primary metric for k-means assignment step and many instance-based learning methods.

Cost Function & Convergence (Regression)

• Cost Function (e.g., SSE/MSE): Quantifies the total error of the model on the training set.

• Convergence Objective: The training process (e.g., Gradient Descent) aims to minimize this cost function.

• Relationship: As iterations proceed, parameter updates should decrease SSE. Convergence is reached when further updates produce negligible change in SSE (i.e., a (local) minimum is found).

Generalization & Hypothesis Space

• Underfitting (High Bias): Model is too simple (e.g., linear model for nonlinear data). High training error & high test error. Occurs with overly restrictive hypothesis space.

• Overfitting (High Variance): Model is too complex and memorizes noise. Very low training error but high test error. Occurs with overly large/flexible hypothesis space.

• Balancing Act: Choose hypothesis space complexity appropriate for the amount and noisiness of data. Use techniques like cross-validation, regularization, and ensemble methods to improve generalization.