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

UNIT 5: MACHINE LEARNING - EXAM-FOCUSED SHORT NOTES

A. FOUNDATIONS & LEARNING PARADIGMS

Learning Paradigms

• Supervised Learning: Model learns a mapping from input features X to a known target/output Y using labeled data. Example: Spam classification (email text → "spam"/"not spam").

• Unsupervised Learning: Model finds hidden patterns or intrinsic structures in unlabeled data X. Example: Customer segmentation (grouping based on purchasing behavior).

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

Hypothesis Spaces

• Finite Hypothesis Space: A set of possible models with a limited number of distinct functions (e.g., all decision trees with depth ≤ 5). Implication: Guarantees exist for generalization error based on size of hypothesis space and training data (Occam's Razor).

• Infinite Hypothesis Space: An unbounded set of possible models (e.g., all possible linear functions, all possible neural networks of any size). Implication: Risk of overfitting is higher; regularization and careful optimization are critical to find a "simple" yet effective function within the infinite space.

[!TIP] Exam Focus: Be prepared to contrast the generalization guarantees (finite) vs. flexibility/overfitting risk (infinite).

Core Probabilistic Concepts & Bayes' Theorem

• Prior Probability P(H): Initial belief in hypothesis H before seeing data.

• Likelihood P(D|H): Probability of observing data D given hypothesis H is true.

• Posterior Probability P(H|D): Updated belief in H after observing D.

• Bayes' Theorem:

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

• Noise in Data: Random error or irreducible variance in the target variable Y. It sets a lower bound on the achievable error (Bayes error rate). A classifier's performance cannot realistically surpass this limit.

[!TIP] Common Pitfall: Confusing P(D|H) (Likelihood) with P(H|D) (Posterior). The former is about data given a model; the latter is about the model given the data.

Numerical Example (Bayes' Theorem - from MAY 2023):

Covid drug test: 1% false positive, 5% false negative, 2% prevalence.

Find P(Drug|Positive).

Let D+ = takes drug, D- = doesn't. T+ = test positive.

P(D+) = 0.02, P(T+|D-) = 0.01 (False Pos), P(T-|D+) = 0.05 (False Neg) → P(T+|D+) = 0.95.

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

$$= \frac{0.95 \times 0.02}{0.95 \times 0.02 + 0.01 \times 0.98} = \frac{0.019}{0.019 + 0.0098} \approx \boxed{0.66}$$

B. SUPERVISED LEARNING: CLASSIFICATION & REGRESSION

Regression Models

• Simple Linear Regression: y = β₀ + β₁x + ε. Fits a line to one predictor.

• Multiple Linear Regression: y = β₀ + β₁x₁ + ... + βₚxₚ + ε. Fits a hyperplane to multiple predictors.

• Logistic Regression: Used for binary classification. Models probability P(Y=1|X) using the logistic (sigmoid) function:

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

• Cost Function (SSE): For linear regression, Sum of Squared Errors:

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

. Goal: Minimize SSE to find best-fit parameters β.

• Convergence of Cost Function: In iterative optimization (e.g., Gradient Descent), the SSE should monotonically decrease and eventually stabilize (converge) to a (local) minimum, indicating the model parameters have been optimized.

[!TIP] Exam Focus: You WILL get a numerical problem to fit a simple linear regression line by calculating β₁ (slope) and β₀ (intercept) from a data table, then make a prediction. (See MAY 2023 Q3).

Support Vector Machines (SVM) - Linear Classification

• Hyperplane: Decision boundary: w·x + b = 0.

• Margin: Distance between the hyperplane and the nearest data points from each class. Goal: Maximize the margin.

• Support Vectors: The critical training points that lie exactly on the margin boundaries (w·x + b = ±1). They uniquely define the optimal hyperplane.

• Optimization Problem: Maximize margin = 2/||w|| subject to y_i (w·x_i + b) ≥ 1 for all i.

[!TIP] Common Pitfall: The margin is defined by the support vectors, not all points. Only these points influence the final model.

Numerical Example (SVM - from MAY 2023):

Data: Class1: {(2,1), (2,-1), (5,1), (-5,1)}; Class2: {(1,0), (0,1), (-1,0), (0,-1)}.

Find max-margin hyperplane and support vectors.

Step 1: Plot points. Visually, a clear separating line exists (e.g., x₁ = 0 or x₂ = 0).

Step 2: For x₂ = 0 (horizontal line), points (2,1), (2,-1) etc. are not correctly separated. For x₁ = 0 (vertical line), Class1 points have x₁ > 0 (except (-5,1)), Class2 points are centered at origin. A line like x₁ = 1.5 might work.

Step 3: The support vectors will be the points closest to the decision boundary from each class. For a vertical line x₁ = c, the closest Class1 point is likely (2,1) or (2,-1) at distance |2-c|. The closest Class2 point is (1,0) at distance |1-c|. To maximize margin, set c midway: c = (2+1)/2 = 1.5. Margin = 0.5.

Support Vectors: (2,1), (2,-1) from Class1; (1,0) from Class2.

Optimal Hyperplane: \boxed{x_1 = 1.5}

Decision Trees - ID3 Algorithm

1. Start with all training examples at the root node.

2. For each attribute A, calculate Entropy of the current set S:

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

where p_i is proportion of class i.

3. Calculate Information Gain for attribute A:

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

4. Select attribute with highest Gain as the decision node.

5. Branch on each value of that attribute, creating subsets S_v.

6. Recursively repeat steps 2-5 on each branch until:

   • All examples in a branch belong to the same class (leaf node).

   • No more attributes to split on (leaf node with majority class).

   • No examples left (leaf node with default class).

Naïve Bayes Classifier

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

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

• Simplification: This reduces the number of probability estimates needed from exponential (2ⁿ for binary features) to linear (2n). The posterior becomes:

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

Classify by choosing class `C` with highest `P(C) ∏ P(X_i|C)`.

Bayesian Belief Networks (BBNs)

• Structure: Directed Acyclic Graph (DAG). Nodes = random variables. Edges = direct conditional dependencies.

• Conditional Probability Tables (CPTs): For each node, a table specifying P(Node | Parents).

• Joint Probability: For variables X₁,...,Xₙ with topological ordering, the joint distribution is the product of conditional probabilities:

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

Numerical Example (BBN - from MAY 2023):

Network: M (Malaria) → H (Headache). Given: P(M)=0.03, P(H|M)=0.6, P(H|¬M)=0.2.

Joint Probability Table (JPT):

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

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

| T | T | 0.03 * 0.6 = 0.018 |

| T | F | 0.03 * (1-0.6) = 0.012 |

| F | T | (1-0.03) * 0.2 = 0.194 |

| F | F | 0.97 * 0.8 = 0.776 |

Check: Sum = 0.018+0.012+0.194+0.776 = 1.0.

C. NEURAL NETWORKS & DEEP LEARNING FUNDAMENTALS

Multilayer Perceptron (MLP) & Activation Functions

• Role: Activation functions introduce non-linearity into the network. Without them, an MLP would collapse into a single linear transformation, unable to learn complex, non-linear patterns.

• Common Functions:

  • Sigmoid: σ(x) = 1/(1+e⁻ˣ). Outputs (0,1). Suffers from vanishing gradient.

  • Tanh: tanh(x). Outputs (-1,1). Zero-centered, but still vanishing gradient.

  • ReLU: max(0, x). Computationally efficient, mitigates vanishing gradient (for positive inputs), but can cause "dying ReLU" problem.

• How they enable non-linear learning: By applying a non-linear transformation at each neuron, the network can compose these transformations to approximate arbitrarily complex non-linear functions (Universal Approximation Theorem).

Self-Organizing Maps (SOM)

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

• Process:

  1. Initialize grid neurons with random weight vectors (same dimension as input).

  2. For each input sample:

     • Find Best Matching Unit (BMU): neuron whose weight vector is closest (e.g., Euclidean distance).

     • Update BMU and its neighbors on the grid: move their weights slightly towards the input sample. Learning rate and neighborhood size decrease over time.

• Purpose: Visualize clusters in high-D data, see data distribution, pre-processing for classification.

• Example: Mapping documents (represented as word frequency vectors) onto a 2D map where similar documents cluster together.

[!TIP] Diagram:

DiagramSEARCH: self-organizing map topology preservation

or

DiagramCANVAS: A 2D grid of neurons, with an input vector in high-D space shown connecting to its BMU, and arrows showing weight updates for the BMU and its immediate neighbors.

D. ENSEMBLE LEARNING METHODS

Core Motivation: Combine multiple "weak" learners to create a single, more accurate and robust "strong" learner. Aims to reduce variance (bagging) or bias (boosting), and improve overall predictive performance.

Bagging (Bootstrap Aggregating)

1. Bootstrapping: Create B bootstrap samples (random samples with replacement) from the original training set.

2. Train: Train B base models (e.g., decision trees) independently, each on one bootstrap sample.

3. Aggregate: For classification, use majority vote; for regression, use average of predictions.

• How it reduces variance: By averaging many high-variance models (like deep trees), the random errors (noise) in each model tend to cancel out, leading to a more stable overall prediction. The correlation between base models is key.

Stacking (Stacked Generalization)

1. Base Learners: Train multiple diverse base models (e.g., SVM, k-NN, Decision Tree) on the full training set.

2. Meta-features: Use the predictions of these base models as new input features for a meta-learner (or meta-classifier).

3. Train Meta-learner: Train the meta-learner (often a simple linear model) on this new dataset. The meta-learner learns how to best combine the base models' outputs.

• Role of Meta-learner: It is trained to optimize the final combination strategy, often learning non-linear combinations and weights, which can outperform simple voting or averaging.

Model Combination Schemes Comparison

E. UNSUPERVISED LEARNING: CLUSTERING

Partitional Clustering: k-Means Algorithm

1. Initialize: Choose k initial cluster centroids (randomly or by heuristic).

2. Assign: For each point, assign it to the cluster whose centroid is closest (using Euclidean distance).

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

4. Repeat steps 2 & 3 until cluster assignments no longer change (or centroids stabilize).

Numerical Example (k-Means - from MAY 2023):

Points: A1(2,10), A2(2,5), A3(8,4), B1(5,8), B2(7,5), B3(6,4), C1(1,2), C2(4,9). k=3. Initial centers: A1, B1, C1.

i) After first round:

• Cluster 1 (center A1(2,10)): Assign points closest to (2,10). A2(2,5) dist=5; C2(4,9) dist=√((2)²+(1)²)=√5≈2.24. New center: Mean of {A1, C2} = ((2+4)/2, (10+9)/2) = (3, 9.5).

• Cluster 2 (center B1(5,8)): Assign points. B2(7,5) dist=√(4+9)=√13≈3.6; B3(6,4) dist=√(1+16)=√17≈4.1; A3(8,4) dist=√(9+16)=5. New center: Mean of {B1, B2, B3, A3} = ((5+7+6+8)/4, (8+5+4+4)/4) = (6.5, 5.25).

• Cluster 3 (center C1(1,2)): Assign points. A2(2,5) now closer to Cluster1? Dist to C1=√(1+9)=√10≈3.16; to Cluster1 center (3,9.5)=√(1+20.25)=√21.25≈4.6 → stays in C1? Wait, A2 was initially in Cluster1? Correction: Initial assignment based on initial centers A1, B1, C1.

*   A2(2,5): dist to A1(2,10)=5, to B1(5,8)=√(9+9)=√18≈4.24, to C1(1,2)=√(1+9)=√10≈3.16 → **to C1**.

*   C2(4,9): dist to A1=√(4+1)=√5≈2.24 → **to A1**.

*   So Cluster1: {A1, C2}; Cluster2: {B1, B2, B3, A3}; Cluster3: {C1, A2}.

**New centers:**

*   C1: Mean of {A1(2,10), C2(4,9)} = **(3, 9.5)**

*   C2: Mean of {B1(5,8), B2(7,5), B3(6,4), A3(8,4)} = **(6.5, 5.25)**

*   C3: Mean of {C1(1,2), A2(2,5)} = **(1.5, 3.5)**

ii) Final Clusters: Continue iterations until convergence. (Final answer would be the stable cluster assignments after subsequent assignments/updates).

Hierarchical Clustering

• AGNES (Agglomerative Nesting): Bottom-up. Start with each point as its own cluster. Repeatedly merge the two closest clusters until one cluster remains. Requires a linkage criterion (single, complete, average) to define inter-cluster distance.

• DIANA (Divisive Analysis): Top-down. Start with all points in one cluster. Repeatedly split the most heterogeneous cluster until each point is isolated. More computationally expensive.

• Comparison:

  • AGNES: Simple, intuitive. Produces a dendrogram. Final k clusters obtained by cutting the dendrogram. Can't undo merges.

  • DIANA: Can produce more balanced clusters. More complex to implement. Also produces a dendrogram.

  • Advantage of both: No need to specify k upfront; the dendrogram shows cluster hierarchy.

  • Limitation: Once a merge/split is made, it cannot be reversed, which can lead to suboptimal partitions.

Gaussian Mixture Models (GMMs)

• Models data as a mixture of several Gaussian distributions. Each cluster k has a Gaussian with mean μ_k and covariance Σ_k.

• Soft Clustering: Assigns a probability P(cluster=k | x) that a point x belongs to cluster k, rather than a hard assignment.

• Suitability for Overlapping Clusters: Because it uses probabilistic membership, GMMs naturally handle clusters that overlap in feature space. Points in overlapping regions get fractional membership probabilities from multiple Gaussians.

• Fitting: Typically done via Expectation-Maximization (EM) algorithm.

F. DIMENSIONALITY REDUCTION & FEATURE EXTRACTION

Principal Component Analysis (PCA)

• Objective: Find a new set of orthogonal axes (principal components) that capture the maximum variance in the data. The first PC has highest variance, second PC (orthogonal to first) has next highest, etc.

• Process:

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

  2. Compute covariance matrix.

  3. Compute eigenvectors and eigenvalues of the covariance matrix.

  4. Sort eigenvectors by decreasing eigenvalues. Top k eigenvectors form the projection matrix.

  5. Project original data onto these k eigenvectors (principal components).

• Result: Reduced-dimensional representation (k features) that preserves as much variance (information) as possible. Linear method.

Locally Linear Embedding (LLE)

• Core Concept: A non-linear manifold learning technique. It assumes data lies on a smooth, non-linear manifold. It preserves local linear relationships between a point and its nearest neighbors.

• Process:

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

  2. Compute reconstruction weights w_ij that best linearly reconstruct x_i from its neighbors (minimize squared error with constraint ∑ w_ij = 1).

  3. Compute low-dimensional embeddings y_i that best preserve these local reconstruction weights (minimize error in y_i vs. ∑ w_ij y_j).

• Comparison with PCA:

  • PCA: Global, linear. Maximizes global variance. Fails on curved manifolds (e.g., Swiss roll).

  • LLE: Local, non-linear. Preserves local geometry. Can unroll non-linear manifolds.

• When to prefer LLE: When you suspect the high-dimensional data lies on a non-linear manifold (e.g., images of a rotating object, text documents on a semantic topic manifold). PCA would distort these local relationships.

[!TIP] Exam Focus: Be ready to state "PCA is linear, LLE is non-linear" and explain that LLE preserves local neighborhoods while PCA preserves global variance.

G. FREQUENT PATTERN MINING

Association Rule Mining & Frequent Itemsets

• Goal: Discover interesting relationships (rules) between items in large transaction databases (Market Basket Analysis).

• Key Terms:

  • Itemset: A set of items (e.g., {bread, milk}).

  • Support supp(X): Fraction of transactions containing itemset X.

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

*   **Confidence `conf(X→Y)`:** Conditional probability of `Y` given `X`. 

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

• k-Frequent Itemset Mining (Apriori Principle):

  1. Frequent 1-itemsets: Scan DB, count items, keep those with supp ≥ min_supp.

  2. Generate candidate k-itemsets: Join frequent (k-1)-itemsets with themselves (if they share first k-2 items).

  3. Prune candidates: Remove any candidate whose any subset is not frequent (Apriori property: All subsets of a frequent itemset must be frequent).

  4. Count support: Scan DB again to count support of remaining candidates.

  5. Repeat steps 2-4 until no new frequent itemsets.

  6. Generate rules: From frequent itemsets L, for each l ∈ L, for each non-empty subset a ⊂ l, form rule a → (l - a) if conf ≥ min_conf.

Numerical Example (Apriori - from MAY 2023):

Assume min_supp = 2 (absolute count). Transactions provided in paper image (must be reconstructed from context).

Generic Solution Steps:

1. C1 (Candidates 1-itemset): List all items with counts.

2. L1 (Frequent 1-itemsets): Keep items with count ≥ 2.

3. C2 (Candidate 2-itemsets): Join L1 with L1 (e.g., if L1={A,B,C}, C2={AB, AC, BC}).

4. Prune C2: Check if all 1-subsets of each candidate are in L1. (They will be by construction from join).

5. Count C2: Scan DB, get support counts for each candidate in C2.

6. L2: Keep candidates with count ≥ 2.

7. C3: Join L2 with L2 (e.g., from L2={AB, AC, BC}, join AB & AC → ABC if they share A).

8. Prune C3: For ABC, check subsets AB, AC, BC. If any not in L2, prune ABC.

9. Count C3 & L3: Scan DB, keep those with count ≥ 2.

10. Stop when no new frequent itemsets (L4 empty).

11. Generate Rules: From final frequent itemsets (e.g., L2 or L3), calculate confidences.

Final Answer: List of all frequent itemsets with support ≥ 2 (e.g., {A}:3, {B}:4, {A,B}:2, etc.).

[!TIP] Exam Focus: The Apriori property ("All subsets of a frequent itemset must be frequent") is the key pruning rule. You WILL be asked to solve a small transaction database with min_supp=2 or similar.