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

UNIT 2: MACHINE LEARNING

1.0 Foundations of Machine Learning

1.1 Learning Paradigms

1.2 Hypothesis Spaces

• Finite Hypothesis Space (H): Limited number of candidate models (e.g., all linear functions with integer coefficients).

  • Implication on Complexity: Lower risk of overfitting; easier to guarantee generalization via uniform convergence.

  • Implication on Generalization: Generalization error bound depends on |H| (size of H).

• Infinite Hypothesis Space (H): Unbounded models (e.g., all linear functions over real numbers, all neural networks of a given architecture).

  • Implication on Complexity: Higher capacity; can fit complex patterns but prone to overfitting.

  • Implication on Generalization: Generalization depends on capacity measures (e.g., VC dimension, Rademacher complexity) rather than |H|.

[!TIP] Exam Focus: Be prepared to contrast finite vs. infinite spaces. Key term: VC Dimension (for infinite spaces).

1.3 Core Concepts

• Features (x): Input variables.

• Labels (y): Output/target variable.

• Training Set: Data used to learn model parameters.

• Test Set: Unseen data used to evaluate generalization.

• Overfitting: Model learns noise in training data; high training accuracy, low test accuracy. High variance.

• Underfitting: Model fails to capture underlying pattern; low training & test accuracy. High bias.

2.0 Supervised Learning: Regression

2.1 Linear Regression

• Model Form: y = w₁x₁ + w₂x₂ + ... + wₙxₙ + b (or y = wᵀx + b).

• Cost Function (MSE):

$$J(w) = \frac{1}{m} \sum_{i=1}^{m} (y^{(i)} - (w^T x^{(i)} + b))^2$$

• Goal: Find w, b that minimize MSE (or SSE = m * MSE).

• Convergence: Achieved when gradient of J(w) approaches zero.

2.2 Parameter Estimation (Ordinary Least Squares - OLS)

For simple linear regression (y = wx + b):

$$w = \frac{\sum_{i=1}^{m} (x^{(i)} - \bar{x})(y^{(i)} - \bar{y})}{\sum_{i=1}^{m} (x^{(i)} - \bar{x})^2}, \quad b = \bar{y} - w\bar{x}$$

For multiple regression (with feature matrix X including bias column, target y):

$$\boxed{w = (X^T X)^{-1} X^T y}$$

[!CAUTION] Assumes XᵀX is invertible (no perfect multicollinearity).

2.3 Logistic Regression

• Purpose: Binary classification.

• Model Form: First computes z = wᵀx + b, then applies sigmoid:

$$\sigma(z) = \frac{1}{1 + e^{-z}}$$

Output `h(x) = σ(z)` is interpreted as **P(y=1|x)**.

• Decision Boundary: h(x) ≥ 0.5 → class 1 (i.e., wᵀx + b ≥ 0).

• Cost Function (Log Loss):

$$J(w) = -\frac{1}{m} \sum_{i=1}^{m} [y^{(i)}\log(h(x^{(i)})) + (1-y^{(i)})\log(1-h(x^{(i)}))]$$

• Comparison with Linear Regression:

  | Aspect | Linear Regression | Logistic Regression | | :--- | :--- | :--- | | Output | Continuous value | Probability [0,1] | | Use-case | Predict quantity (sales, price) | Predict class (spam/not spam) | | Cost | MSE (quadratic) | Log Loss (convex for classification) |

3.0 Supervised Learning: Classification

3.1 Support Vector Machines (SVM) - Linear

• Goal: Find the maximum margin hyperplane that separates classes.

• Margin: Distance between hyperplane and nearest data points from each class.

• Support Vectors: The critical training points that lie on the margin boundaries; they support the hyperplane.

• Optimization Problem (Primal):

  Minimize ½ ||w||² subject to y⁽ⁱ⁾(wᵀx⁽ⁱ⁾ + b) ≥ 1 for all i.

• Solution: Via dual problem using Lagrange multipliers. Only support vectors have non-zero α coefficients.

• Maximum Margin:

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

[!TIP] Numerical Problem: Given points, find w, b by solving the dual or using the fact that support vectors satisfy y⁽ⁱ⁾(wᵀx⁽ⁱ⁾ + b) = 1.

3.2 Decision Trees - ID3 Algorithm

• Core Idea: Recursively split data using the feature that provides the highest Information Gain (IG).

• Entropy (H): Measure of impurity/uncertainty.

$$H(S) = -\sum_{c \in C} p_c \log_2 p_c$$

where `p_c` is proportion of class `c` in set `S`.

• Information Gain:

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

`S_v` is subset of `S` where feature `A` has value `v`.

• Process:

  1. Start with whole dataset at root.

  2. For each feature, compute IG.

  3. Select feature with max IG as splitting node.

  4. Recur on resulting subsets.

• Pruning (Conceptual): Remove branches that have low predictive power to prevent overfitting (e.g., reduced-error pruning).

3.3 Probabilistic Classifiers

Bayesian Learning

• Bayes' Theorem:

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

- **Posterior** `P(H|D)`: Belief in hypothesis `H` after seeing data `D`.

- **Prior** `P(H)`: Initial belief in `H`.

- **Likelihood** `P(D|H)`: Probability of data given `H`.

- **Evidence** `P(D)`: Normalizing constant.

• Goal: Find hypothesis h that maximizes posterior P(h|D) (MAP - Maximum A Posteriori).

Naïve Bayes Classifier

• Core Assumption: Conditional Independence of features given the class.

$$P(x_1, x_2, ..., x_n | y) = \prod_{i=1}^{n} P(x_i | y)$$

• Simplification: Posterior becomes:

$$P(y|x) \propto P(y) \prod_{i=1}^{n} P(x_i | y)$$

• Prediction: Predict class y that maximizes the above product.

• Why it works: Reduces joint probability estimation from exponential to linear in number of features.

Bayesian Belief Networks (BBN)

• Structure: Directed Acyclic Graph (DAG).

  • Nodes: Random variables.

  • Edges: Direct conditional dependencies (parent → child).

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

• Joint Probability Distribution: Factorizes according to graph structure.

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

[!EXAMPLE] For a network M → H (Malaria causes Headache):

• CPTs: P(M), P(H|M), P(H|¬M).

• Joint: P(M, H) = P(H|M) P(M) and P(¬M, H) = P(H|¬M) P(¬M).

4.0 Neural Networks & Deep Learning Fundamentals

4.1 Multilayer Perceptron (MLP) Architecture

• Layers: Input layer → one or more hidden layers → Output layer.

• Units (Neurons): Each unit in layer l computes:

$$z^{(l)} = W^{(l)} a^{(l-1)} + b^{(l)}, \quad a^{(l)} = g(z^{(l)})$$

where `g` is activation function, `a⁽⁰⁾` is input `x`.

• Fully Connected: Every neuron in layer l-1 connects to every neuron in layer l.

4.2 Role of Activation Functions

• Purpose: Introduce non-linearity. Without them, MLP would collapse to a single linear transformation.

• Common Functions:

  | Function | Formula | Properties | Use | | :--- | :--- | :--- | :--- | | Sigmoid | $$\displaystyle \sigma(z) = \frac{1}{1+e^{-z}} $$ | Output (0,1), saturates, vanishing gradient | Output layer for binary classification | | Tanh | $$\displaystyle \tanh(z) = \frac{e^z - e^{-z}}{e^z + e^{-z}} $$ | Output (-1,1), zero-centered | Hidden layers (often better than sigmoid) | | ReLU | $$\displaystyle \text{ReLU}(z) = \max(0, z) $$ | Non-saturating for z>0, sparse activation | Hidden layers (most common) | | Leaky ReLU | $\max(\alpha z, z)$, $\alpha \approx 0.01$ | Fixes "dying ReLU" problem | Hidden layers |

5.0 Ensemble Learning Methods

5.1 Bagging (Bootstrap Aggregating)

• Process:

  1. Create B bootstrap samples (random sampling with replacement from training set).

  2. Train B base learners (e.g., decision trees) independently on each sample.

  3. Aggregate predictions:

     • Classification: Majority vote.

     • Regression: Average.

• Mechanism: Reduces variance by averaging many high-variance models (like deep trees).

• Example: Random Forest (bagging + feature randomness).

5.2 Stacking

• Process:

  1. Split training data into k folds.

  2. Train base learners (e.g., SVM, tree, NB) on k-1 folds, predict on held-out fold → creates level-0 predictions.

  3. Use these level-0 predictions as new features to train a meta-learner (level-1 model).

• Role of Meta-Learner: Learns how to best combine the diverse predictions of base models.

• Contribution: Often achieves higher performance than single models or voting by learning optimal combination weights.

5.3 Model Combination Schemes

[!TIP] Exam: Be ready to compare bagging vs. stacking. Bagging reduces variance via averaging similar models trained on bootstraps. Stacking reduces both bias & variance by training a different model to combine diverse base learners.

6.0 Unsupervised Learning: Clustering

6.1 k-Means Algorithm

• Objective: Partition m points into k clusters minimizing within-cluster sum of squares (WCSS).

• Steps:

  1. Initialization: Randomly choose k data points as initial centroids μ₁, ..., μₖ.

  2. Assignment: For each point x⁽ⁱ⁾, assign to nearest centroid:

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

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

$$\mu_j = \frac{1}{|C_j|} \sum_{i \in C_j} x^{(i)}$$

4. Repeat 2-3 until centroids stabilize (convergence).

• Distance Metric: Euclidean distance ||x - y||.

• Convergence: Guaranteed to decrease J each iteration, but may converge to local optimum.

6.2 Hierarchical Clustering

AGNES (Agglomerative Nesting)

• Process: Bottom-up. Start with each point as its own cluster. Iteratively merge the two closest clusters until one cluster remains.

• Linkage Criteria: Defines "closest clusters":

  • Single (min distance), Complete (max distance), Average, Ward (min increase in WCSS).

• Advantages: No need to specify k upfront; produces dendrogram.

• Limitations: Once merged, cannot undo; computationally expensive O(m² log m); sensitive to noise/outliers.

DIANA (Divisive Analysis)

• Process: Top-down. Start with all points in one cluster. Iteratively split the most heterogeneous cluster until each point is isolated (or k clusters).

• Advantages: Can produce more balanced clusters.

• Limitations: More complex; also O(m² log m); sensitive to initial split.

Comparison:

6.3 Probabilistic Clustering: Gaussian Mixture Models (GMM)

• Model: Assumes data generated from k Gaussian distributions:

$$p(x) = \sum_{j=1}^{k} \phi_j \mathcal{N}(x | \mu_j, \Sigma_j)$$

where `φⱼ` is mixing coefficient (prior probability of cluster `j`).

• Parameters: {φⱼ, μⱼ, Σⱼ} for j=1..k.

• Expectation-Maximization (EM) Intuition:

  1. E-step: Compute responsibilities γ(z⁽ⁱ⁾ⱼ) = P(z⁽ⁱ⁾=j | x⁽ⁱ⁾) (posterior probability that point i belongs to cluster j).

  2. M-step: Update parameters using responsibilities (soft counts):

     • φⱼ = (1/m) Σᵢ γ(zⁱⱼ)

     • μⱼ = (Σᵢ γ(zⁱⱼ) xⁱ) / (Σᵢ γ(zⁱⱼ))

     • Σⱼ = (Σᵢ γ(zⁱⱼ) (xⁱ - μⱼ)(xⁱ - μⱼ)ᵀ) / (Σᵢ γ(zⁱⱼ))

• Suitability for Overlapping Clusters: GMMs assign soft assignments (probabilities), naturally handling points that lie between clusters. k-Means makes hard assignments.

7.0 Dimensionality Reduction & Manifold Learning

7.1 Principal Component Analysis (PCA)

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

• Steps:

  1. Standardize data (zero mean, unit variance).

  2. Compute covariance matrix: Σ = (1/m) XᵀX (if X is mean-centered).

  3. Compute eigenvectors and eigenvalues of Σ.

  4. Sort eigenvectors by decreasing eigenvalues. Top k eigenvectors = principal components.

  5. Project data: Z = X Wₖ, where Wₖ is n×k matrix of top eigenvectors.

• Key: Eigenvectors point in directions of maximum variance; eigenvalues = variance along that direction.

7.2 Locally Linear Embedding (LLE)

• Assumption: Data lies on a non-linear manifold; each point is a linear combination of its nearest neighbors.

• Steps:

  1. For each point xⁱ, find k nearest neighbors.

  2. Compute reconstruction weights Wᵢⱼ that minimize error in reconstructing xⁱ from its neighbors:

$$\min_{W_i} ||x^{(i)} - \sum_j W_{ij} x^{(j)}||^2, \quad \text{s.t. } \sum_j W_{ij} = 1$$

3. Compute low-dimensional embeddings `yⁱ` that preserve these local relationships:

$$\min_{Y} \sum_i ||y^{(i)} - \sum_j W_{ij} y^{(j)}||^2$$

• Output: Y (m×d) where d is desired reduced dimension.

7.3 Comparison: PCA vs. LLE

8.0 Frequent Pattern Mining

8.1 Concept & Importance

• Frequent Itemset: Set of items that appear together in transactions above a minimum support threshold.

• Support: P(itemset) = (transactions containing itemset) / (total transactions).

• Importance: Foundation for association rule mining (e.g., {bread} → {butter}). Used in market basket analysis, recommendation systems, cross-selling.

8.2 k-Frequent Itemset Mining (Apriori-like)

• Apriori Principle: If an itemset is frequent, all its subsets must be frequent. (Anti-monotone property).

• Algorithm Steps:

  1. k=1: Count support of all single items. Prune those below min_supp.

  2. Candidate Generation (k→k+1): Join frequent k-itemsets with themselves to create candidate (k+1)-itemsets (ensuring all k-subsets are frequent).

  3. Pruning: Eliminate candidates whose any k-subset is not frequent (using Apriori principle).

  4. Support Counting: Scan database, count support of remaining candidates.

  5. Prune candidates below min_supp. Repeat from step 2 until no new frequent itemsets.

• Output: All frequent itemsets up to size k (or until no more).

[!EXAMPLE] For min_supp=2 and transactions:

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

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

• Candidate 2-itemsets: {A,B}, {A,C}, {B,C}. All have support ≥2 → all frequent.

• Candidate 3-itemset: {A,B,C}. Support=2 → frequent.

9.0 Model Evaluation & Probabilistic Reasoning

9.1 Performance Metrics (Classification)

From Confusion Matrix:

• Precision: TP / (TP + FP) → Of predicted positives, how many are correct?

• Recall (Sensitivity): TP / (TP + FN) → Of actual positives, how many did we find?

• F1-Score: Harmonic mean: 2 * (Precision * Recall) / (Precision + Recall).

• Specificity: TN / (TN + FP).

Bayesian Inference in Evaluation (Drug Test Example)

Problem: Covid'19 drug test: 1% false positive (P(T+|¬D)=0.01), 5% false negative (P(T-|D)=0.05), 2% use drugs (P(D)=0.02). Find P(D|T+).

Solution:

1. Find P(T+|D) = 1 - P(T-|D) = 0.95.

2. P(T+) = P(T+|D)P(D) + P(T+|¬D)P(¬D) = (0.95*0.02) + (0.01*0.98) = 0.019 + 0.0098 = 0.0288.

3. By Bayes:

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

Conclusion: Despite high accuracy, only ~66% of positive tests are actual drug users due to low base rate (P(D)=0.02).

9.2 Constructing Joint Probability Table from Bayesian Network

Given network M → H with:

• P(M) = 0.03

• P(H|M) = 0.6

• P(H|¬M) = 0.2

Joint Probability Table:

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

[!TIP] Exam Pattern: You will likely get a question to compute a posterior probability (like the drug test) or build a joint table from a simple BBN. Always write out full joint distribution first.