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

UNIT 3: MACHINE LEARNING FOR ROBOTICS

I. FOUNDATIONS OF MACHINE LEARNING

Learning Paradigms

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

• Unsupervised Learning: Find hidden patterns in unlabeled data (e.g., clustering, dimensionality reduction).

• Reinforcement Learning: Agent learns by interacting with an environment, receiving rewards/penalties.

• Semi-supervised Learning: Uses a small amount of labeled data with a large amount of unlabeled data.

Hypothesis Spaces

• Finite Hypothesis Space: Limited set of possible models (e.g., decision trees with depth ≤ d). Lower risk of overfitting, but may underfit if too restrictive.

• Infinite Hypothesis Space: Unbounded set of models (e.g., all linear functions). High risk of overfitting; requires regularization (e.g., weight decay) to ensure good generalization.

[!TIP] Exam Focus: Link hypothesis space size to VC dimension—larger spaces need more data to generalize.

II. SUPERVISED LEARNING: REGRESSION TECHNIQUES

Linear Regression

• Model: $$\displaystyle y = \theta_0 + \theta_1 x + \epsilon $$, where $\epsilon$ is error.

• Assumptions: Linearity, independence, homoscedasticity, normal errors.

• Cost Function (MSE):

$$J(\theta) = \frac{1}{2m} \sum_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)})^2$$

Minimized via gradient descent.

• Sum of Squared Errors (SSE): $$\displaystyle SSE = \sum (y_i - \hat{y}_i)^2 $$. $$\displaystyle J(\theta) = \frac{SSE}{2m} $$.

• Convergence Objective: Find $\theta$ that minimizes $J(\theta)$. Convergence implies $J(\theta)$ stabilizes near global minimum (for convex MSE).

Example (May 2023): Given Time (x) and Sales (y), compute $$\displaystyle \theta_1 = \frac{\sum(x-\bar{x})(y-\bar{y})}{\sum(x-\bar{x})^2} $$, $$\displaystyle \theta_0 = \bar{y} - \theta_1\bar{x} $$. Predict for $$\displaystyle x=40 $$.

Multiple Linear Regression

• Extends to $n$ features: $$\displaystyle y = \theta_0 + \theta_1 x_1 + ... + \theta_n x_n $$. Solved via normal equation: $$\displaystyle \theta = (X^TX)^{-1}X^Ty $$.

Logistic Regression

• Model: $$\displaystyle P(y=1|x) = \frac{1}{1+e^{-(\theta^Tx)}} $$ (sigmoid function).

• Comparison: Used for binary classification (outputs probability), not continuous values. Cost function: log loss (cross-entropy).

• Advantages: Outputs probabilities, robust to noise, interpretable coefficients.

III. SUPERVISED LEARNING: CLASSIFICATION ALGORITHMS

Support Vector Machines (SVM)

• Linear Classification: Find hyperplane $$\displaystyle w^Tx + b = 0 $$ that maximizes margin (distance to nearest points of each class).

• Support Vectors: Training points closest to hyperplane; define margin.

• Margin Optimization: Solve $$\displaystyle \min_{w,b} \frac{1}{2}||w||^2 $$ s.t. $$\displaystyle y^{(i)}(w^Tx^{(i)}+b) \geq 1 $$. Use Lagrange multipliers.

Example (May 2023): For points $\{(2,1),(2,-1),(5,1)\}$ (class +1) and $\{(1,0),(0,1),(-1,0),(0,-1)\}$ (class -1), find $w,b$ such that margin is max. Support vectors are points on margin boundaries.

Decision Trees (ID3 Algorithm)

• Steps:

  1. Start with all training data at root.

  2. For each attribute, compute Entropy $$\displaystyle H(S) = -\sum p_i \log_2 p_i $$ and Information Gain $$\displaystyle IG(S,A) = H(S) - \sum \frac{|S_v|}{|S|} H(S_v) $$.

  3. Select attribute with highest IG as node.

  4. Recur on subsets until all instances in a branch belong to same class or no attributes left.

• Example: Classify products based on price (Low/High) and sales (Yes/No).

Neural Networks (MLP)

• Architecture: Input layer → Hidden layer(s) (with activation) → Output layer.

• Activation Functions:

  • Sigmoid: $$\displaystyle \sigma(z) = \frac{1}{1+e^{-z}} $$ (outputs 0–1, suffers vanishing gradient).

  • ReLU: $$\displaystyle f(z) = \max(0,z) $$ (avoids vanishing gradient, sparse activation).

  • Enable learning nonlinear patterns by composing linear transforms with nonlinear activations.

Naive Bayes Classifier

• Assumption: Conditional Independence—features independent given class: $$\displaystyle P(x_1,...,x_n|y) = \prod P(x_i|y) $$.

• Posterior: $$\displaystyle P(y|x) \propto P(y) \prod P(x_i|y) $$. Prior: $P(y)$ (class probability from training).

• Simplification: Avoids estimating joint distribution $$\displaystyle P(x_1,...,x_n|y) $$ (exponential in n); instead uses product of marginals.

• Noise Effect: Violation of independence assumption degrades performance, but often robust due to probability estimates.

IV. UNSUPERVISED LEARNING: CLUSTERING

k-means Clustering

• Algorithm:

  1. Initialize: Choose $k$ centroids (randomly or given).

  2. Assign: For each point, assign to nearest centroid (Euclidean distance).

  3. Update: Recompute centroids as mean of assigned points.

  4. Repeat until convergence (centroids unchanged).

• Distance: Euclidean $$\displaystyle d(p,q) = \sqrt{\sum (p_i - q_i)^2} $$.

Example (May 2023): Cluster 8 points with initial centers A1(2,10), B1(5,8), C1(1,2). After first round, compute new centroids. Final clusters after convergence.

Hierarchical Clustering

• AGNES (Agglomerative): Bottom-up. Start with each point as cluster; merge closest pairs (using single/complete/average linkage). Advantage: No need to specify $k$; gives dendrogram. Limitation: Irreversible merges, computationally heavy $$\displaystyle O(n^3) $$.

• DIANA (Divisive): Top-down. Start with all points in one cluster; split recursively. Advantage: Can handle large clusters better. Limitation: Complex splitting criterion.

Gaussian Mixture Models (GMM)

• Probabilistic Model: Data generated from mixture of $k$ Gaussians: $$\displaystyle p(x) = \sum_{k=1}^K \pi_k \mathcal{N}(x|\mu_k,\Sigma_k) $$.

• Parameters: Weights $$\displaystyle \pi_k $$, means $$\displaystyle \mu_k $$, covariances $$\displaystyle \Sigma_k $$. Learned via Expectation-Maximization (EM).

• Suitability for Overlapping Clusters: Soft assignments (probabilistic membership) allow points to belong to multiple clusters with varying probabilities.

V. UNSUPERVISED LEARNING: DIMENSIONALITY REDUCTION

Principal Component Analysis (PCA)

• Objective: Find orthogonal axes (principal components) that maximize variance in data.

• Steps:

  1. Standardize data.

  2. Compute covariance matrix $$\displaystyle C = \frac{1}{m} X^TX $$.

  3. Compute eigenvectors/eigenvalues of $C$.

  4. Sort eigenvectors by decreasing eigenvalues; top $k$ form projection matrix.

• Example: Reduce 2D data to 1D by projecting onto eigenvector with largest eigenvalue.

Locally Linear Embedding (LLE)

• Nonlinear Technique: Preserves local geometry by modeling each point as linear combination of neighbors.

• Steps:

  1. Find $k$ nearest neighbors for each point.

  2. Compute reconstruction weights $$\displaystyle W_{ij} $$ that minimize $$\displaystyle \sum_i ||x_i - \sum_j W_{ij}x_j||^2 $$.

  3. Compute low-dimensional embeddings $Y$ that preserve weights: minimize $$\displaystyle \sum_i ||y_i - \sum_j W_{ij}y_j||^2 $$.

• Comparison with PCA:

  | PCA | LLE | |---|---| | Linear, global structure | Nonlinear, local manifold | | Eigen-decomposition of covariance | Eigen-decomposition of cost matrix | | Prefer LLE when: Data lies on curved manifold (e.g., Swiss roll). |

VI. PROBABILISTIC METHODS

Bayesian Belief Networks (BBN)

• Construction:

  • Nodes: Random variables (e.g., Malaria M, Headache H).

  • Edges: Direct dependencies (e.g., M → H).

  • Conditional Probability Tables (CPTs): $P(H|M)$, $P(H|\neg M)$.

• Joint Probability: $$\displaystyle P(M,H) = P(M) \cdot P(H|M) $$ for all instantiations.

Example (May 2023): Given $$\displaystyle P(M)=0.03 $$, $$\displaystyle P(H|M)=0.6 $$, $$\displaystyle P(H|\neg M)=0.2 $$. Joint table:

| M | H | P(M,H) |

|---|---|---|

| T | T | $$\displaystyle 0.03 \times 0.6 = 0.018 $$ |

| T | F | $$\displaystyle 0.03 \times 0.4 = 0.012 $$ |

| F | T | $$\displaystyle 0.97 \times 0.2 = 0.194 $$ |

| F | F | $$\displaystyle 0.97 \times 0.8 = 0.776 $$ |

Bayesian Learning

• Framework: Update prior beliefs with evidence using Bayes' theorem: $$\displaystyle P(h|D) = \frac{P(D|h)P(h)}{P(D)} $$.

• Example: Predict disease given symptoms; update probability as new symptoms observed.

VII. ENSEMBLE LEARNING

Bagging (Bootstrap Aggregation)

• Process:

  1. Create $B$ bootstrap samples (random sampling with replacement).

  2. Train base learner (e.g., decision tree) on each sample.

  3. Combine predictions: voting (classification) or averaging (regression).

• Variance Reduction: Averaging multiple high-variance models (like trees) reduces overall variance by factor $$\displaystyle \approx \frac{1}{B} $$.

Stacking

• Role of Meta-Learners:

  1. Base learners trained on original data.

  2. Their predictions become features for meta-learner (e.g., linear regression).

  3. Meta-learner learns how to best combine base predictions.

• Contribution: Captures complex combination patterns; often outperforms simple voting/averaging.

Model Combination Schemes Comparison

VIII. SPECIALIZED TOPICS

Frequent Pattern Mining (Apriori)

• Concept: Find itemsets (e.g., {milk, bread}) appearing frequently in transactions.

• Process:

  1. Set min support $s$.

  2. Generate candidate $k$-itemsets from frequent $(k-1)$-itemsets.

  3. Prune candidates with support $$\displaystyle < s $$.

  4. Repeat until no new frequent itemsets.

• Importance: Market basket analysis (e.g., "customers who buy X also buy Y").

Example (May 2023): Given transactions, find frequent itemsets with $$\displaystyle k=3 $$, min_supp=2. Use Apriori: generate 1-itemsets, prune, then 2-itemsets, then 3-itemsets.

Self-Organizing Maps (SOM)

• Architecture: 2D grid of neurons, each with weight vector of same dimension as input.

• Training:

  1. Initialize weights randomly.

  2. For each input $x$:

     • Find Best Matching Unit (BMU): neuron with weight closest to $x$.

     • Update BMU and neighbors: $$\displaystyle w_i(t+1) = w_i(t) + \alpha(t) \cdot h_{BMU,i}(t) \cdot (x - w_i(t)) $$, where $h$ is neighborhood function.

  3. Reduce $\alpha$ and neighborhood radius over time.

• Diagram:

  DiagramCANVAS: 2D grid with neurons, input vector mapped to BMU, neighborhood update arrows

• Application: Visualization of high-dimensional data (e.g., gene expression, document clustering).

Cost Function Convergence

• Objective: Find parameters $\theta$ that minimize cost $J(\theta)$ (e.g., MSE for regression).

• Relation to SSE: $$\displaystyle J(\theta) = \frac{SSE}{2m} $$. Convergence of gradient descent on $J(\theta)$ implies SSE is minimized.

• Can we use for linear regression? Yes—MSE is convex, guaranteeing global minimum; gradient descent converges if learning rate appropriate.

IX. PRACTICAL IMPLEMENTATION AND CASE STUDIES

Regression Problem-Solving (Linear)

1. Compute means $\bar{x}, \bar{y}$.

2. Compute $$\displaystyle \theta_1 = \frac{\sum (x_i-\bar{x})(y_i-\bar{y})}{\sum (x_i-\bar{x})^2} $$.

3. Compute $$\displaystyle \theta_0 = \bar{y} - \theta_1\bar{x} $$.

4. Compute $$\displaystyle R^2 = 1 - \frac{SSE}{SST} $$ (SST = total sum of squares).

5. Predict $$\displaystyle \hat{y} = \theta_0 + \theta_1 x_{\text{new}} $$.

Classification Problem-Solving (SVM/Decision Tree)

• SVM: For linearly separable data, find $w,b$ such that $$\displaystyle y^{(i)}(w^Tx^{(i)}+b) \geq 1 $$. Support vectors satisfy equality. Solve via Lagrange dual.

• Decision Tree: Compute entropy for target, then IG for each feature. Split on highest IG. Recur.

Clustering Problem-Solving (k-means)

1. Compute Euclidean distance $$\displaystyle d = \sqrt{\sum (x_i - c_i)^2} $$ for each point to each centroid.

2. Assign to nearest centroid.

3. Update centroids: $$\displaystyle c_j = \frac{1}{|\text{cluster}_j|} \sum_{x \in \text{cluster}_j} x $$.

4. Repeat until no change.

Bayesian Probability Applications (Covid Test)

• Given: $$\displaystyle P(\text{Pos}|\neg D)=0.01 $$, $$\displaystyle P(\text{Neg}|D)=0.05 $$, $$\displaystyle P(D)=0.02 $$.

• Find $$\displaystyle P(D|\text{Pos}) = \frac{P(\text{Pos}|D)P(D)}{P(\text{Pos})} $$.

• $$\displaystyle P(\text{Pos}|D) = 1 - 0.05 = 0.95 $$.

• $$\displaystyle P(\text{Pos}) = P(\text{Pos}|D)P(D) + P(\text{Pos}|\neg D)P(\neg D) = 0.95\times0.02 + 0.01\times0.98 = 0.019 + 0.0098 = 0.0288 $$.

• $$\displaystyle P(D|\text{Pos}) = \frac{0.95\times0.02}{0.0288} \approx 0.66 $$.

Algorithm Selection Guidance

• Linear separable data? → SVM (linear kernel).

• Need probabilities? → Logistic Regression, Naive Bayes.

• Nonlinear boundaries? → SVM (RBF kernel), Neural Networks.

• Interpretable model? → Decision Tree.

• High-dimensional data? → PCA before classification.

• Overlapping clusters? → GMM.

• Small data, high variance? → Bagging.

X. COMPARATIVE ANALYSIS AND ADVANCED CONCEPTS

Comparison of Regression Types

Comparison of Dimensionality Reduction

Comparison of Clustering Methods

Ensemble Method Comparison

[!TIP] Exam Strategy: For 7m questions, structure answer: Definition → Key Steps/Formulas → Example → Advantages/Limitations. Always include numerical example if asked (e.g., regression, clustering).