Robotics (IT-802 (C)) - Unit 5 Short Notes

1. Foundations of Machine Learning

Learning Paradigms

• Supervised Learning: Model learns a mapping from inputs to outputs using labeled training data (e.g., classification, regression).

• Unsupervised Learning: Model finds patterns or structure in unlabeled data (e.g., clustering, dimensionality reduction).

• Reinforcement Learning: Agent learns to make decisions by performing actions in an environment to maximize a cumulative reward.

Hypothesis Spaces: Finite vs. Infinite

[!TIP] Exam Focus: Be prepared to explain why an infinite space requires regularization for good generalization, while a finite space's generalization is tied to its cardinality relative to the training data size.

2. Regression Analysis

Linear & Multiple Linear Regression

• Goal: Find the best-fit straight line (or hyperplane) to model the relationship between a dependent variable $y$ and one or more independent variables $x$.

• Simple Linear Regression Equation: $$\displaystyle y = \beta_0 + \beta_1 x + \epsilon $$

• Multiple Linear Regression Equation: $$\displaystyle y = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + ... + \beta_p x_p + \epsilon $$

• Fitting Method: Ordinary Least Squares (OLS). Minimizes the Sum of Squared Errors (SSE) or Residual Sum of Squares (RSS).

$$SSE = \sum_{i=1}^{n} (y_i - \hat{y}_i)^2 = \sum_{i=1}^{n} (y_i - (\beta_0 + \beta_1 x_i))^2$$

• Cost Function: $$\displaystyle J(\beta_0, \beta_1) = \frac{1}{2n} SSE $$. The factor $$\displaystyle \frac{1}{2n} $$ simplifies gradient descent derivation.

• Convergence: Gradient descent aims to find $\beta$ values where $\nabla J(\beta) \approx 0$, indicating a (local) minimum of the cost function, which corresponds to the best fit.

Logistic Regression

• Purpose: Used for binary classification (e.g., spam/not spam). Despite the name, it's a classifier.

• Model: Applies the logistic (sigmoid) function to a linear combination of inputs to estimate probability $$\displaystyle P(Y=1|X) $$.

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

• Key Difference from Linear Regression: Output is bounded between 0 and 1 (a probability), not a continuous value. Uses log-loss (cross-entropy) as the cost function, not SSE.

• Example Use: Predicting if a customer will buy a product (Yes/No) based on age and income.

[!TIP] Exam Problem: For linear regression, you may be asked to compute $$\displaystyle \beta_0, \beta_1 $$ using OLS formulas from a small dataset and then predict a new $y$ value. Always plot the fitted line.

3. Classification Methods

Support Vector Machines (SVM) - Linear

• Goal: Find the maximum margin hyperplane that best separates two classes of linearly separable data.

• Key Concepts:

  • Support Vectors: The training data points closest to the decision boundary (lying on the margin). They support (define) the margin.

  • Margin: The distance between the decision boundary and the nearest data points of any class. SVM maximizes this margin.

  • Decision Boundary (Hyperplane): $$\displaystyle w^T x + b = 0 $$.

  • Constraints: For correctly classified points, $$\displaystyle y_i(w^T x_i + b) \geq 1 $$.

• Optimization Problem (Primal):

$$\min_{w,b} \frac{1}{2} \|w\|^2 \quad \text{subject to } y_i(w^T x_i + b) \geq 1 \quad \forall i$$

Maximizing margin is equivalent to minimizing $$\displaystyle \frac{1}{\|w\|} $$, which is solved by minimizing $$\displaystyle \frac{1}{2}\|w\|^2 $$.

Decision Trees - ID3 Algorithm

• Process: Iteratively selects the attribute that maximizes Information Gain to split the data at each node.

• Entropy (Measure of Impurity):

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

where $$\displaystyle p_i $$ is the proportion of class $i$ in set $S$, and $c$ is the number of classes.

• Information Gain:

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

where $$\displaystyle S_v $$ is the subset of $S$ for which attribute $A$ has value $v$.

• Steps: Start with all training data at root → For each attribute, compute Gain → Choose attribute with highest Gain as split → Recur on resulting subsets until all data in a branch belongs to one class or no attributes left.

Naïve Bayes Classifier

• Core Assumption: Conditional Independence. Given the class label $C$, the features $$\displaystyle X_1, X_2, ..., X_n $$ are conditionally independent.

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

• Bayes' Theorem for Classification:

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

We predict the class $C$ that maximizes the **posterior probability** $P(C|X)$.

• Simplification: The independence assumption reduces the need to estimate the huge joint distribution $P(X|C)$ to just the individual conditional distributions $$\displaystyle P(X_i|C) $$.

• Prior vs. Posterior:

  • Prior Probability $P(C)$: Probability of class $C$ before seeing the evidence (features).

  • Posterior Probability $P(C|X)$: Updated probability of class $C$ after observing features $X$.

• Effect of Noise: The conditional independence assumption is often violated by noisy, correlated data, which can degrade performance despite the simplification.

Bayesian Learning (Example)

• Framework: Represents uncertainty about hypotheses using probability. Maintains a posterior distribution over all possible hypotheses $h \in H$ given data $D$:

$$P(h|D) = \frac{P(D|h) P(h)}{P(D)}$$

• Prediction: Makes predictions by averaging over all hypotheses, weighted by their posterior probability.

$$P(x|D) = \sum_{h \in H} P(x|h) P(h|D)$$

• Example: Predicting the next coin flip outcome. Hypotheses: $$\displaystyle h_1 $$: coin is fair ($$\displaystyle P(H)=0.5 $$), $$\displaystyle h_2 $$: coin is biased ($$\displaystyle P(H)=0.9 $$). Update beliefs (posterior) after observing a sequence of flips.

4. Clustering Techniques

Partitional Clustering: k-means

1. Initialization: Randomly select $k$ data points as initial cluster centroids $$\displaystyle \mu_1, \mu_2, ..., \mu_k $$.

2. Assignment: Assign each point $$\displaystyle x_i $$ to the nearest centroid (using Euclidean distance).

$$c^{(i)} := \arg\min_{j} \|x_i - \mu_j\|^2$$

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

$$\mu_j := \frac{1}{|C_j|} \sum_{i \in C_j} x_i$$

4. Repeat: Steps 2 & 3 until centroids no longer change significantly (convergence).

Hierarchical Clustering

Gaussian Mixture Models (GMM)

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

• Model: $$\displaystyle p(x) = \sum_{k=1}^{K} \pi_k \mathcal{N}(x|\mu_k, \Sigma_k) $$, where $$\displaystyle \pi_k $$ is the mixing coefficient (prior probability of cluster $k$).

• EM Algorithm:

  1. Expectation (E-step): Compute the "responsibility" $$\displaystyle \gamma(z_{ik}) $$ of cluster $k$ for point $$\displaystyle x_i $$, given current parameters.

  2. Maximization (M-step): Update parameters $$\displaystyle \pi_k, \mu_k, \Sigma_k $$ using the responsibilities as soft cluster assignments.

• Suitability for Overlapping Clusters: Provides soft clustering (probabilistic membership) via responsibilities $$\displaystyle \gamma(z_{ik}) $$, naturally handling clusters with overlapping densities.

5. Dimensionality Reduction

Principal Component Analysis (PCA)

• Goal: Find orthogonal axes (principal components) that capture the maximum variance in the data, reducing dimensions while preserving as much information as possible.

• Steps:

  1. Standardize the data (mean=0, variance=1).

  2. Compute the covariance matrix $$\displaystyle C = \frac{1}{n} X^T X $$.

  3. Compute eigenvectors and eigenvalues of $C$.

  4. Sort eigenvectors by decreasing eigenvalues. The top $k$ eigenvectors form the projection matrix $W$.

  5. Transform data: $$\displaystyle Y = X W $$.

• Key: Principal components are linear combinations of original features.

Locally Linear Embedding (LLE)

• Goal: Preserve local geometric properties (neighborhood relationships) of the data in a lower-dimensional space. Non-linear method.

• Mechanism:

  1. Local Step: For each point $$\displaystyle x_i $$, find its $k$ nearest neighbors. Compute weights $$\displaystyle w_{ij} $$ that best linearly reconstruct $$\displaystyle x_i $$ from its neighbors (solving a constrained least-squares problem).

  2. Global Step: Find low-dimensional embeddings $$\displaystyle y_i $$ that preserve these reconstruction weights as much as possible. Minimize the cost function:

$$\Phi(Y) = \sum_i \|y_i - \sum_j w_{ij} y_j\|^2$$

    This is solved by an eigenvector problem.

PCA vs. LLE

6. Ensemble Learning

Bagging (Bootstrap Aggregation)

• Technique: Create multiple bootstrap samples (random sampling with replacement) from the training set. Train a base learner (e.g., decision tree) on each sample. Final prediction is average (regression) or majority vote (classification) of all learners.

• Variance Reduction Mechanism: By averaging many high-variance models (like deep trees), the variance of the final ensemble prediction is reduced. The key is that the errors of individual models are uncorrelated.

$$\text{Var}(\bar{X}) = \frac{1}{m} \text{Var}(X) \quad \text{(if errors are independent)}$$

where $m$ is the number of models.

Stacking

• Technique: Combines multiple heterogeneous base learners (e.g., SVM, tree, NB) using a meta-learner (or blender).

• Process:

  1. Split training data into $k$ folds.

  2. Train each base learner on $k-1$ folds and predict on the held-out fold. This creates a new dataset of base learner predictions (level-0 data).

  3. Train the meta-learner on this new dataset, where the features are the base learners' predictions.

• Role of Meta-learner: Learns how to best combine the potentially complementary predictions of the diverse base models, often leading to superior performance.

Model Combination Schemes Comparison

7. Association Rule Mining

Frequent Pattern Mining

• Definition: Discovering itemsets (sets of items) that appear together in a transaction database with frequency (support) above a minimum threshold.

• Importance (Market Basket Analysis): Identifies products that are frequently bought together (e.g., {bread, milk}). Used for cross-selling, store layout, and recommendation systems.

k-Frequent Itemset Mining (Apriori Algorithm)

• Key Principle (Apriori Property): All subsets of a frequent itemset must also be frequent. If {A,B,C} is frequent, then {A,B}, {A,C}, {B,C} must be frequent.

• Steps:

  1. Initialize: Set $$\displaystyle k=1 $$. Find all frequent 1-itemsets by counting support and comparing to min_support.

  2. Iterate:

     • Candidate Generation: Use frequent $(k-1)$-itemsets to generate candidate $k$-itemsets (by joining and pruning using Apriori property).

     • Support Counting: Scan database to count support of each candidate.

     • Pruning: Keep candidates with support ≥ min_support. These are the frequent $k$-itemsets.

  3. Terminate: When no new frequent itemsets are found.

• Solving Problem: Given a transaction list and min_supp=2, systematically apply the steps above. Start with $$\displaystyle k=1 $$, find all items with count ≥2. Then generate candidates for $$\displaystyle k=2 $$ (e.g., from {A}, {B} → candidate {A,B}), count, prune, and so on.

8. Probabilistic Graphical Models

Bayesian Belief Networks (BBNs)

• Construction:

  1. Nodes: Represent random variables (e.g., Malaria, Headache).

  2. Edges (Directed): Represent direct conditional dependencies. An edge $$\displaystyle A \rightarrow B $$ means $A$ is a parent of $B$, and $B$'s probability depends on $A$.

  3. Conditional Probability Tables (CPTs): For each node, specify $P(\text{Node} | \text{Parents})$. If a node has no parents, it has a prior probability.

• Joint Probability Distribution & Factorization:

  The full joint distribution over all variables $$\displaystyle X_1, ..., X_n $$ factorizes according to the graph structure:

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

• Example Network (Malaria & Headache):

  • Nodes: M (Malaria), H (Headache).

  • Edge: M → H (Headache can be caused by Malaria).

  • CPTs:

    • $P(M)$: Prior (e.g., $$\displaystyle P(M)=0.03 $$).

    • $P(H|M)$ and $P(H|\neg M)$: Conditionals (e.g., $$\displaystyle P(H|M)=0.6 $$, $$\displaystyle P(H|\neg M)=0.2 $$).

  • Joint Probability Table (for M,H):

    | M | H | Joint Probability $P(M,H)$ | |:-:|:-:|:---:| | T | T | $$\displaystyle P(M) \times P(H|M) = 0.03 \times 0.6 = 0.018 $$ | | T | F | $$\displaystyle P(M) \times P(\neg H|M) = 0.03 \times 0.4 = 0.012 $$ | | F | T | $$\displaystyle P(\neg M) \times P(H|\neg M) = 0.97 \times 0.2 = 0.194 $$ | | F | F | $$\displaystyle P(\neg M) \times P(\neg H|\neg M) = 0.97 \times 0.8 = 0.776 $$ |

Naïve Bayes as a Simplified BBN

• Naïve Bayes is a BBN where the class node is the parent of all feature nodes, and features have no parents among themselves.

• This structure explicitly encodes the conditional independence assumption: $$\displaystyle P(\text{Features}|\text{Class}) = \prod P(\text{Feature}_i|\text{Class}) $$.

9. Neural Networks

Multilayer Perceptron (MLP)

• Structure: Input layer → One or more hidden layers → Output layer. Fully connected between layers.

• Role of Activation Functions:

  1. Introduce Non-linearity: Without them, an MLP would collapse to a single linear transformation, unable to learn complex patterns.

  2. Enable Gradient Flow: Differentiable functions (Sigmoid, Tanh, ReLU) allow error backpropagation.

• Common Functions:

  • Sigmoid: $$\displaystyle \sigma(z) = \frac{1}{1+e^{-z}} $$. Outputs (0,1). Suffers from vanishing gradients.

  • ReLU (Rectified Linear Unit): $$\displaystyle f(z) = \max(0, z) $$. Computationally efficient, mitigates vanishing gradient, but can have "dying ReLU" problem.

• Learning Nonlinear Patterns: The composition of multiple linear transformations ($Wx + b$) interleaved with non-linear activations allows the network to approximate any continuous function (Universal Approximation Theorem).

Self-Organizing Maps (SOM)

• Explanation: An unsupervised neural network for dimensionality reduction and visualization. It projects high-dimensional data onto a (usually 2D) grid of neurons while preserving topological relationships (neighboring data points in input space map to neighboring neurons on the grid).

• Mechanism (Competitive Learning):

  1. Initialization: Neurons' weight vectors (prototypes) are initialized (often randomly).

  2. Competition: For an input $x$, find the neuron whose weight vector is closest (Best Matching Unit, BMU).

  3. Cooperation: The BMU and its neighboring neurons on the grid form a "neighborhood".

  4. Adaptation: Update the weights of the BMU and its neighbors to move them closer to the input $x$:

$$w_t(t+1) = w_t(t) + \alpha(t) \cdot h_{bmu,t}(t) \cdot (x - w_t(t))$$

    where $\alpha(t)$ is the learning rate and $$\displaystyle h_{bmu,t}(t) $$ is the neighborhood kernel (decreases with distance/time).

• Diagram & Application:
  DiagramCANVAS: A 2D grid (e.g., 5x5) of neurons. Show a high-dimensional data point being mapped to a specific neuron (BMU), and arrows showing how neighboring neurons' weights also shift towards the data point. Label: "Input Space -> SOM Grid (Topology Preserving Map)". Example Application: Visualizing customer segments from high-dimensional demographic data.

10. Performance Evaluation & Applied Probability

Impact of Noise on Classifier Performance

• Noise (mislabeled data, irrelevant features, measurement errors) corrupts the true underlying pattern.

• Effect: Increases bias (if model is too simple to overcome noise) or variance (if model overfits to noise). Generally leads to lower accuracy and poor generalization to clean test data.

• Example: In a spam filter, if 10% of legitimate emails are mislabeled as spam (noise in training labels), the classifier may learn to associate certain "ham" words with the spam class, causing it to incorrectly classify future legitimate emails.

Convergence of Cost Function & SSE

• Objective: In linear regression (using OLS), minimizing the cost function $$\displaystyle J(\beta) = \frac{1}{2n} SSE $$ is equivalent to minimizing the Sum of Squared Errors (SSE).

• Relation: $J(\beta) \propto SSE$. Therefore, convergence of $J(\beta)$ to a minimum directly implies convergence of SSE to a minimum.

• Justification: The OLS solution $$\displaystyle \hat{\beta} = (X^T X)^{-1} X^T y $$ is the unique global minimum for SSE when $$\displaystyle X^T X $$ is invertible (no multicollinearity). Gradient descent will converge to this minimum if the learning rate is appropriate, indicating the best possible linear fit to the data.

Bayesian Inference Applications (Covid Drug Test Example)

• Problem: Test for a drug (D).

  • $$\displaystyle P(\text{Positive} | \neg D) = 0.01 $$ (False Positive Rate)

  • $$\displaystyle P(\text{Negative} | D) = 0.05 $$ (False Negative Rate) → $$\displaystyle P(\text{Positive} | D) = 0.95 $$

  • $$\displaystyle P(D) = 0.02 $$ (Prevalence)

• Find: $$\displaystyle P(D | \text{Positive}) = ? $$

• Solution via Bayes' Theorem:

$$P(D|+) = \frac{P(+|D) P(D)}{P(+)}$$

First, find $P(+)$ using Law of Total Probability:

$$P(+) = P(+|D)P(D) + P(+|\neg D)P(\neg D) = (0.95 \times 0.02) + (0.01 \times 0.98) = 0.019 + 0.0098 = 0.0288$$

Then,

$$P(D|+) = \frac{0.95 \times 0.02}{0.0288} = \frac{0.019}{0.0288} \approx 0.6597$$

\boxed{P(D|+) \approx 0.66}

• Key Insight: Even with a highly accurate test (95% sensitivity, 99% specificity), because the disease prevalence ($P(D)$) is low (2%), a positive test result means only a ~66% chance of actually having the disease. This highlights the critical role of prior probability.

General Bayes' Theorem Problem-Solving

1. Identify: Events $A$ (hypothesis) and $B$ (evidence).

2. Know/Find: $P(A)$ (prior), $P(B|A)$, $P(B|\neg A)$ or $P(B)$.

3. Apply:

$$P(A|B) = \frac{P(B|A) P(A)}{P(B|A)P(A) + P(B|\neg A)P(\neg A)}$$

4. Compute: Plug in values. Ensure all probabilities are consistent (e.g., $$\displaystyle P(\neg A) = 1 - P(A) $$).