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

UNIT 1: Machine Learning Foundations

I. Foundations of Machine Learning

Learning Paradigms

Hypothesis Spaces

• Finite Hypothesis Spaces: Limited set of possible models (e.g., all linear functions with fixed features).

  • Implication: Lower risk of overfitting; generalization easier but may underfit if too restrictive.

• Infinite Hypothesis Spaces: Unbounded models (e.g., all possible polynomials).

  • Implication: High model complexity; risk of overfitting; requires regularization for good generalization.

[!TIP] Exam often asks to compare both—focus on complexity vs generalization trade-off.

II. Supervised Learning

A. Regression

Cost Function & Convergence

• Sum of Squared Errors (SSE):

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

• Minimized via Gradient Descent: Iteratively update $\beta$ to reduce SSE until convergence.

[!TIP] For logistic regression, use cross-entropy loss, not SSE.

B. Classification

Support Vector Machines (SVM)

• Linear Classification: Find hyperplane $$\displaystyle w^T x + b = 0 $$ separating classes.

• Margin Optimization: Maximize distance between hyperplane and nearest points (support vectors).

  • Margin: $$\displaystyle \frac{2}{\|w\|} $$; maximize margin ⇔ minimize $$\displaystyle \frac{1}{2}\|w\|^2 $$ subject to $$\displaystyle y_i(w^T x_i + b) \geq 1 $$.

• Support Vectors: Training points lying on margin boundaries; define the optimal hyperplane.

Decision Trees (ID3 Algorithm)

• Entropy (impurity measure):

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

• Information Gain:

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

• Steps:

  1. Start with all training data at root.

  2. Select attribute with highest IG.

  3. Split on attribute values; recurse on subsets.

  4. Stop when all instances belong to same class or no attributes left.

[!TIP] ID3 handles only categorical features; for continuous, discretize first.

Bayesian Classifiers

• Naïve Bayes:

  • Assumption: Features conditionally independent given class $$\displaystyle P(x_1,...,x_n|C) = \prod_i P(x_i|C) $$.

  • Posterior:

$$P(C|x) \propto P(C) \prod_i P(x_i|C)$$

• Simplification: Avoids joint probability over all features; computes per-feature likelihoods.

• Noise Effect: Independence violation (noise) degrades performance but often still robust.

• Bayesian Learning:

  • Framework: Update prior belief $P(h)$ with data $D$ to posterior $P(h|D) \propto P(D|h)P(h)$.

  • Example: Predict disease given symptoms using Bayes' theorem with prior prevalence.

III. Neural Networks

Multilayer Perceptron (MLP)

• Feedforward network with input, hidden, output layers.

• Trained via backpropagation: compute gradient of loss w.r.t. weights, update via gradient descent.

Activation Functions

• Role: Introduce nonlinearity; enable learning complex patterns (without them, MLP collapses to linear model).

• Common Functions:

  • Sigmoid: $$\displaystyle \sigma(x) = \frac{1}{1+e^{-x}} $$; output (0,1); vanishing gradient issue.

  • Tanh: $\tanh(x)$; output (-1,1); zero-centered.

  • ReLU: $\max(0,x)$; avoids vanishing gradient; sparse activation.

[!TIP] ReLU most used in hidden layers; sigmoid/tanh in output for probability/range constraints.

IV. Ensemble Learning

Bagging (Bootstrap Aggregating)

• Process:

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

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

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

• Variance Reduction: Decorrelates errors by averaging diverse models; reduces overfitting.

Stacking

• Meta-Learners: Second-level model trained on base learners' predictions.

• Process:

  1. Split training data into folds.

  2. Train base models on training folds; predict on hold-out fold.

  3. Use base predictions as features for meta-learner (e.g., linear regression).

  4. Final prediction: meta-learner combines base outputs.

Model Combination Schemes

V. Dimensionality Reduction

Principal Component Analysis (PCA)

• Concept: Find orthogonal axes (principal components) maximizing variance; project data onto top $k$ components.

• Steps:

  1. Standardize data.

  2. Compute covariance matrix.

  3. Eigen-decomposition; sort eigenvectors by eigenvalue.

  4. Select top $k$ eigenvectors; project data.

• Example: Reduce 2D data to 1D by projecting onto direction of highest variance.

Locally Linear Embedding (LLE)

• Concept: Preserve local neighborhood structure; each point reconstructed from neighbors in lower-dim space.

• Comparison with PCA:

  • PCA: Global linear structure; LLE: Local nonlinear manifold.

  • LLE handles nonlinear data better (e.g., Swiss roll).

• Advantages: Captures nonlinear manifolds; no need for distance metrics in original space.

[!TIP] Use LLE when data lies on a nonlinear manifold; PCA for linear relationships.

VI. Unsupervised Learning: Clustering

A. Partitional Clustering

k-means Algorithm

• Steps:

  1. Initialize $k$ centroids (randomly or k-means++).

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

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

  4. Repeat 2–3 until centroids stabilize (or max iterations).

• Example Execution:

  • Data: A1(2,10), A2(2,5), B1(5,8), B2(7,5), C1(1,2), C2(4,9); $$\displaystyle k=3 $$; initial centers: A1, B1, C1.

  • After first round: Recompute means → new centers (e.g., cluster1: mean of A1,A2,C2? depends on assignments).

B. Hierarchical Clustering

• AGNES (Agglomerative Nesting):

  • Bottom-up: Start each point as cluster; merge closest pairs (using single/complete/average linkage).

• DIANA (Divisive Analysis):

  • Top-down: Start with all points; recursively split clusters.

• Advantages/Limitations:

  • Adv: No need to specify $k$; dendrogram gives full hierarchy.

  • Lim: Computationally expensive ($$\displaystyle O(n^3) $$); once merged/split, cannot undo.

C. Probabilistic Clustering

Gaussian Mixture Models (GMM)

• Modeling: Clusters as Gaussian distributions; each point has soft assignment (probability).

  • Density: $$\displaystyle p(x) = \sum_{k=1}^{K} \pi_k \mathcal{N}(x|\mu_k, \Sigma_k) $$.

• EM Algorithm (Brief):

  1. E-step: Compute responsibilities $$\displaystyle \gamma(z_k) = P(z_k|x) $$.

  2. M-step: Update $$\displaystyle \pi_k, \mu_k, \Sigma_k $$ using responsibilities.

• Suitability for Overlapping Clusters: Soft assignments allow points to belong partially to multiple Gaussians; captures uncertainty.

VII. Frequent Pattern Mining

Market Basket Analysis

• Find items frequently bought together (e.g., {bread, milk}).

k-Frequent Itemset Mining (Apriori Algorithm)

• Minimum Support Threshold: Minimum fraction of transactions containing itemset.

• Steps:

  1. Find frequent 1-itemsets (support ≥ min_supp).

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

  3. Prune candidates with infrequent subsets (Apriori property: all subsets of frequent itemset must be frequent).

  4. Repeat until no new frequent itemsets.

• Example: Transactions: {A,B}, {A,C}, {B,C}, {A,B,C}; min_supp=2 → frequent 2-itemsets: {A,B}, {A,C}, {B,C}.

VIII. Probabilistic Graphical Models

Bayesian Belief Networks (BBN)

• Construction:

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

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

  3. CPTs: For each node, conditional probabilities given parents.

• Joint Probability:

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

• Example (Malaria & Headache):

  • 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 $$ |

IX. Specialized Architectures

Self-Organizing Maps (SOM)

• Concept: Unsupervised neural network for dimensionality reduction & visualization; preserves topological structure.

• Working Principle:

  1. Initialize grid of neurons with weight vectors (same dim as input).

  2. For each input:

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

     • Update BMU and neighbors: $$\displaystyle w_{new} = w_{old} + \alpha(t) \cdot h_{bmu,i}(t) \cdot (x - w_{old}) $$.

     • $\alpha$: learning rate; $h$: neighborhood function (decreases with distance/time).

  3. Repeat; neighborhood shrinks over time.

• Diagram: 2D grid of neurons; input space mapped onto grid; nearby inputs activate nearby neurons.

• Example Application: Visualizing high-dimensional data (e.g., gene expression patterns); color quantization.

Final Note: Always connect theory to examples from past papers (e.g., solve regression/SVM numerically, compute entropy for ID3, apply Apriori). Practice derivations (PCA eigenvectors, EM for GMM) and diagrammatic explanations (SOM, BBN).