Quantum Computing (IT-802 (D)) - Unit 4 Short Notes

UNIT 4: Machine Learning

1. Foundations of Machine Learning

Learning Paradigms

Hypothesis Spaces

• Finite Hypothesis Space: Limited set of possible models (e.g., decision trees with depth ≤ 5).

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

• Infinite Hypothesis Space: Unbounded models (e.g., all possible linear functions).

  • Implication: High capacity to fit complex patterns; requires regularization to prevent overfitting.

• Generalization: Model's performance on unseen data. Controlled by model complexity vs. training data size.

[!TIP]

Exam Focus: Compare finite/infinite spaces in terms of bias-variance tradeoff. Finite spaces → high bias, low variance. Infinite spaces → low bias, high variance (without regularization).

2. Supervised Learning: Classification

2.1 Decision Trees – ID3 Algorithm

Core Idea: Recursively split data using attribute with highest Information Gain.

Key Formulas:

• Entropy (measure of impurity):

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

where \(p_i\) = proportion of class \(i\) in set \(S\), \(c\) = number of classes.

• Information Gain:

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

\(S_v\) = subset where attribute \(A\) has value \(v\).

ID3 Steps:

1. Start with all training data at root.

2. For each attribute, compute information gain.

3. Select attribute with highest gain as splitting node.

4. Recur on each branch with remaining attributes until:

   • All instances belong to same class, OR

   • No attributes left (assign majority class).

[!EXAMPLE]

Numerical Problem: Given a dataset with attributes Outlook (Sunny, Overcast, Rain) and Temperature (Hot, Mild, Cool), compute entropy and gain to decide first split.

2.2 Support Vector Machines (SVM) – Linear Classification

Goal: Find maximum margin hyperplane separating classes.

• Margin: Distance between hyperplane and nearest data points of any class.

• Support Vectors: Data points lying on margin boundaries; uniquely define the hyperplane.

• Optimization Problem (linearly separable case):

$$ \min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 \quad \text{subject to} \quad y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 $$

Solution via Lagrange multipliers; only support vectors have non-zero multipliers.

Margin Width:

$$ \text{Margin} = \frac{2}{\|\mathbf{w}\|} $$

[!EXAMPLE]

Problem-Solving: Given 2D points with labels, find \(\mathbf{w}, b\) by solving constraints for support vectors.

Tip: Identify points closest to decision boundary; they are support vectors.

2.3 Neural Networks – Multilayer Perceptron (MLP)

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

• Activation Functions:

  | Function | Formula | Role | |----------|---------|------| | Sigmoid | \(\sigma(x) = \frac{1}{1+e^{-x}}\) | Maps to (0,1); smooth gradient. | | Tanh | \(\tanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}\) | Maps to (-1,1); zero-centered. | | ReLU | \(\text{ReLU}(x) = \max(0, x)\) | Sparse activation; mitigates vanishing gradient. |

Why Nonlinear?

Linear combinations of linear functions remain linear. Activation functions introduce nonlinearity, enabling MLPs to approximate complex decision boundaries (Universal Approximation Theorem).

[!TIP]

ReLU is default for hidden layers due to computational efficiency and sparsity. Sigmoid/Tanh used in output layers for probability outputs (binary classification).

2.4 Probabilistic Classifiers

2.4.1 Naive Bayes Classifier

Assumption: Conditional Independence – features \(X_i\) are independent given class \(C\):

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

Bayes' Theorem:

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

• Prior \(P(C)\): Probability of class before seeing data.

• Posterior \(P(C|X)\): Updated probability after observing features \(X\).

Effect of Noise:

Noise violates independence assumption, leading to overconfident probabilities (poor calibration). Robust to feature noise if independence holds approximately.

[!EXAMPLE]

Text Classification: Words as features; class = spam/ham. Compute \(P(\text{spam}|\text{word}_1, \text{word}_2)\) via product of \(P(\text{word}_i|\text{spam})\).

2.4.2 Bayesian Belief Networks (BBN)

Construction:

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

2. Edges: Direct dependencies (causal/associative).

3. Conditional Probability Tables (CPTs): Specify \(P(\text{Node}|\text{Parents})\).

Joint Probability Distribution:

For network with variables \(X_1, \dots, X_n\):

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

Inference: Compute posterior given evidence (e.g., \(P(M|H=1)\)) using CPTs and chain rule.

[!EXAMPLE]

Network: \(M \rightarrow H\). Given \(P(M)=0.03\), \(P(H|M)=0.6\), \(P(H|\neg M)=0.2\).

Joint table: \(P(M,H) = P(M)P(H|M)\); \(P(\neg M, H) = P(\neg M)P(H|\neg M)\), etc.

3. Supervised Learning: Regression

3.1 Linear Regression

Simple vs Multiple:

• Simple: \(y = \beta_0 + \beta_1 x\)

• Multiple: \(y = \beta_0 + \beta_1 x_1 + \dots + \beta_p x_p\)

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

$$ \text{SSE} = \sum_{i=1}^n (y_i - \hat{y}_i)^2, \quad \text{MSE} = \frac{\text{SSE}}{n} $$

Convergence: SSE decreases with each iteration of Gradient Descent until reaching minimum (optimal \(\beta\)s). Closed-form solution: \(\boldsymbol{\beta} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}\).

Assumptions:

1. Linearity.

2. Independence of errors.

3. Homoscedasticity (constant variance).

4. Normality of errors (for inference).

[!EXAMPLE]

Problem: Given data (Time, Sales), compute \(\beta_0, \beta_1\) via formulas:

\(\beta_1 = \frac{\sum (x_i - \bar{x})(y_i - \bar{y})}{\sum (x_i - \bar{x})^2}\), \(\beta_0 = \bar{y} - \beta_1 \bar{x}\).

Predict sales at \(x=40\) months.

3.2 Logistic Regression

Purpose: Binary classification (outputs probability). Model:

$$ P(Y=1|X) = \frac{1}{1 + e^{-(\beta_0 + \beta_1 x)}} $$

Odds: \(\frac{P(Y=1|X)}{1-P(Y=1|X)} = e^{\beta_0 + \beta_1 x}\)

Comparison with Linear Regression:

Advantages:

• Outputs interpretable probabilities.

• No assumption of linear relationship between features and probability (via logit transformation).

4. Unsupervised Learning

4.1 Clustering

4.1.1 K-means Clustering

Algorithm:

1. Initialization: Randomly select \(k\) centroids.

2. Assignment: Assign each point to nearest centroid (Euclidean distance).

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

4. Convergence: Repeat 2–3 until centroids stabilize.

Distance Metric: Euclidean: \(d(\mathbf{x},\mathbf{y}) = \sqrt{\sum_{i=1}^d (x_i - y_i)^2}\).

[!EXAMPLE]

Problem: Given 8 points and \(k=3\), initial centers A1, B1, C1.

i) After first round: Assign points, compute new centroids.

ii) Final clusters: Iterate until no change.

Limitations: Sensitive to initialization, assumes spherical clusters, requires \(k\) specified.

4.1.2 Hierarchical Clustering

AGNES (Agglomerative):

• Bottom-up: Start with each point as cluster; merge closest clusters.

• Linkage Criteria:

  • Single: min distance between points in clusters.

  • Complete: max distance.

  • Average: average pairwise distance.

DIANA (Divisive):

• Top-down: Start with all points in one cluster; split recursively.

Comparison:

4.1.3 Gaussian Mixture Models (GMM)

Model: Data generated from mixture of \(k\) Gaussians:

$$ p(\mathbf{x}) = \sum_{i=1}^k \pi_i \mathcal{N}(\mathbf{x}|\boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i) $$

\(\pi_i\) = mixing coefficient, \(\mathcal{N}\) = Gaussian distribution.

EM Algorithm:

1. E-step: Compute responsibility \(\gamma(z_i)\) = probability point \(i\) belongs to cluster \(k\).

2. M-step: Update \(\pi_k, \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k\) using \(\gamma(z_i)\).

Soft Assignments: Unlike k-means (hard), GMM gives probabilities → handles overlapping clusters.

Comparison with K-means:

• K-means: Assumes equal spherical covariance, hard assignments.

• GMM: Flexible covariance, soft assignments; more robust to irregular shapes.

4.1.4 Self-Organizing Maps (SOM)

Architecture:

• Input layer → Competitive (Kohonen) layer (2D grid).

• Each neuron has weight vector \(\mathbf{w}_i\) of same dimension as input.

Training:

1. Competition: Find neuron with weight closest to input \(\mathbf{x}\) (winner-takes-all).

2. Cooperation: Winner and its neighbors on grid adapt.

3. Adaptation: Update weights:

   \(\mathbf{w}_i(t+1) = \mathbf{w}_i(t) + \alpha(t) h_{ci}(t) (\mathbf{x} - \mathbf{w}_i(t))\)

   \(h_{ci}\) = neighborhood function (decreases with distance from winner).

Application: Visualization of high-dimensional data (e.g., color clustering, document mapping).

4.2 Dimensionality Reduction

4.2.1 Principal Component Analysis (PCA)

Objective: Find orthogonal axes (principal components) maximizing variance.

Steps:

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

2. Compute covariance matrix \(\mathbf{C} = \frac{1}{n-1}\mathbf{X}^T\mathbf{X}\).

3. Eigen decomposition: \(\mathbf{C}\mathbf{v} = \lambda \mathbf{v}\).

   • Eigenvectors \(\mathbf{v}_1, \mathbf{v}_2, \dots\) = principal components.

   • Eigenvalues \(\lambda_i\) = variance explained by PC\(_i\).

4. Project data: \(\mathbf{X}_{\text{reduced}} = \mathbf{X}\mathbf{V}_k\) (top \(k\) eigenvectors).

Explained Variance Ratio: \(\frac{\lambda_i}{\sum \lambda_j}\).

[!EXAMPLE]

Reduce 3D data to 2D: Compute top 2 eigenvectors; project points onto plane spanned by them.

4.2.2 Locally Linear Embedding (LLE)

Idea: Preserve local geometry – each point reconstructed from its neighbors.

Steps:

1. For each point \(\mathbf{x}_i\), find \(k\) nearest neighbors.

2. Compute reconstruction weights \(\mathbf{W}_{ij}\) minimizing:

   \(\min_{\mathbf{W}} \sum_i \|\mathbf{x}_i - \sum_j \mathbf{W}_{ij} \mathbf{x}_j\|^2\), subject to \(\sum_j \mathbf{W}_{ij}=1\).

3. Compute low-dimensional embedding \(\mathbf{y}_i\) that preserves weights:

   \(\min_{\mathbf{Y}} \sum_i \|\mathbf{y}_i - \sum_j \mathbf{W}_{ij} \mathbf{y}_j\|^2\).

Comparison with PCA:

5. Ensemble Learning

5.1 Bagging (Bootstrap Aggregating)

Process:

1. Bootstrapping: Sample \(n\) instances with replacement from training set (create \(B\) bootstrap samples).

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

3. Aggregate: For classification → majority vote; regression → average.

Variance Reduction:

Bagging reduces variance by averaging multiple high-variance models (e.g., trees). De-correlates errors via bootstrap sampling.

Example: Random Forest – bagging + feature subset selection at each split.

5.2 Stacking

• Level-0 models: Diverse base learners (e.g., SVM, tree, k-NN).

• Level-1 model (meta-learner): Trained on predictions of level-0 models (as features) to produce final prediction.

• Contribution: Meta-learner learns how to best combine base models, often improving accuracy beyond any single model.

[!EXAMPLE]

Level-0: SVM, Decision Tree, k-NN.

Level-1: Logistic regression trained on [SVM_pred, Tree_pred, kNN_pred] for each training instance.

5.3 Model Combination Schemes

6. Frequent Pattern Mining

Market Basket Analysis: Find items frequently bought together (e.g., {bread, milk}).

Key Metrics:

• Support: \(P(A \cup B)\) – frequency of itemset.

• Confidence: \(P(B|A) = \frac{\text{Support}(A \cup B)}{\text{Support}(A)}\) – predictive strength.

• Lift: \(\frac{\text{Confidence}(A \rightarrow B)}{\text{Support}(B)}\) – >1 indicates positive correlation.

Apriori Algorithm:

1. Candidate Generation: Join frequent \((k-1)\)-itemsets to create candidate \(k\)-itemsets.

2. Pruning: Remove candidates with any subset infrequent (Apriori property: all subsets of frequent itemset must be frequent).

3. Repeat until no new frequent itemsets.

[!EXAMPLE]

Problem: Transactions:

T1: {A,B,C}, T2: {A,B}, T3: {A,C}, T4: {B,C}, T5: {A,B,C}.

min_supp = 2 (appear in ≥2 transactions).

Frequent 1-itemsets: A(4), B(4), C(4).

Frequent 2-itemsets: {A,B}(3), {A,C}(3), {B,C}(3).

Frequent 3-itemset: {A,B,C}(2).

7. Advanced Probabilistic and Optimization Topics

7.1 Bayesian Learning

Bayes' Theorem:

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

• \(H\) = hypothesis, \(D\) = data.

• Posterior \(P(H|D)\) updated from prior \(P(H)\) via likelihood \(P(D|H)\).

Example – Covid Drug Test:

• \(P(\text{pos}|\neg D)=0.01\) (false positive rate).

• \(P(\text{neg}|D)=0.05\) → \(P(\text{pos}|D)=0.95\).

• \(P(D)=0.02\).

• Find \(P(D|\text{pos})\):

$$ P(D|\text{pos}) = \frac{P(\text{pos}|D)P(D)}{P(\text{pos})} = \frac{0.95 \times 0.02}{0.95 \times 0.02 + 0.01 \times 0.98} \approx 0.66 $$

7.2 Noise in Data

• Effect: Increases false positives/negatives, degrades accuracy.

• Robust Models: Probabilistic models (Naive Bayes) can incorporate noise via conditional probabilities; tree-based models handle noise via pruning.

7.3 Cost Function and Optimization

Linear Regression: Minimize SSE → equivalent to maximizing likelihood under normal errors. Convergence: Gradient descent updates \(\beta_j := \beta_j - \alpha \frac{\partial \text{SSE}}{\partial \beta_j}\) until \(\|\nabla \text{SSE}\| < \epsilon\).

8. Comparative Analyses (Cross-Cutting Themes)

[!TIP]

Exam Strategy: For comparison questions, structure answer as:

1. Define each.

2. List 3–4 key differences (mathematical, assumptions, use cases).

3. Conclude with when to prefer which.