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

UNIT 1: Foundations of Machine Learning

1.1 Introduction to Machine Learning

Learning Paradigms

Machine learning methods are categorized by the nature of the learning signal available.

Hypothesis Spaces

The hypothesis space $\mathcal{H}$ is the set of all possible models (functions) a learning algorithm can consider.

• Finite Hypothesis Space: $$\displaystyle |\mathcal{H}| < \infty $$.

  Implication: With enough data, uniform convergence guarantees exist. Risk of underfitting if $\mathcal{H}$ is too small (lacks expressive power).

• Infinite Hypothesis Space: $$\displaystyle |\mathcal{H}| = \infty $$ (e.g., all linear functions, all neural nets with real weights).

  Implication: Requires regularization (e.g., weight decay, early stopping) to prevent overfitting and ensure good generalization. Capacity is controlled by parameters like VC-dimension or Rademacher complexity.

[!TIP] Exam Focus: Be prepared to link hypothesis space size to the bias-variance trade-off. A small (high-bias) space may underfit; a large (high-variance) space may overfit without proper regularization.

1.2 Supervised Learning

1.2.1 Regression

Predicts a continuous numerical output.

Cost Function & Convergence

For linear regression, the Sum of Squared Errors (SSE) is minimized:

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

Closed-form solution: $$\displaystyle \mathbf{w} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y} $$ (if invertible).

For logistic regression, log loss (cross-entropy) is minimized via gradient descent. Convergence is assessed when the change in cost $J(\mathbf{w})$ or parameters $\mathbf{w}$ falls below a threshold $\epsilon$.

[!TIP] Common Pitfall: Do not confuse logistic regression (classification) with linear regression (regression). Logistic outputs probabilities via sigmoid; linear outputs raw values.

1.2.2 Classification

Support Vector Machines (SVM) - Linear Classification

• Goal: Find the maximum margin hyperplane that separates classes with the largest possible gap.

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

• Support Vectors: The critical training points that lie exactly on the margin boundaries. They solely define the optimal hyperplane.

• Optimization: For linearly separable data, solve:

$$ \min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 \quad \text{s.t.} \quad y_i(\mathbf{w}^T\mathbf{x}_i + b) \geq 1 $$

The solution depends only on support vectors: $$\displaystyle \mathbf{w} = \sum_{i \in SV} \alpha_i y_i \mathbf{x}_i $$.

Decision Trees - ID3 Algorithm

• Core Idea: Recursively split data using the attribute that yields the highest information gain.

• Entropy (measure of impurity): $$\displaystyle H(S) = -\sum_{c} p_c \log_2 p_c $$, where $$\displaystyle p_c $$ is the proportion of class $c$ in set $S$.

• Information Gain: $$\displaystyle IG(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v) $$, where $$\displaystyle S_v $$ is the subset for attribute value $v$.

• Process: Start with full dataset. For each attribute, compute $IG$. Choose attribute with max $IG$ as root. Recur on splits until all instances in a node belong to one class or no attributes remain.

Neural Networks - Multilayer Perceptron (MLP)

• Structure: Input layer → one or more hidden layers → Output layer. Fully connected.

• Activation Functions (enable learning nonlinear patterns):

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

  • ReLU: $$\displaystyle f(z) = \max(0, z) $$. Computationally efficient, mitigates vanishing gradient, but can "die".

  • Tanh: $\tanh(z)$. Outputs (-1,1), zero-centered.

• Learning: Forward pass computes predictions. Backpropagation computes gradient of loss w.r.t. weights. Gradient descent updates weights: $$\displaystyle w \leftarrow w - \eta \frac{\partial \mathcal{L}}{\partial w} $$.

Naive Bayes Classifier

• Assumptions:

  1. Conditional Independence: Features $$\displaystyle x_1, ..., x_n $$ are conditionally independent given class $y$.

  2. Equal importance of features (often unrealistic but works well in practice).

• Bayes' Theorem: $$\displaystyle P(y|x_1,...,x_n) = \frac{P(y) \prod_{i} P(x_i|y)}{P(x_1,...,x_n)} $$.

• Simplification: Denominator $P(\mathbf{x})$ is constant for all classes. So, predict:

$$ \hat{y} = \arg\max_y P(y) \prod_{i=1}^n P(x_i|y) $$

This avoids estimating the full joint distribution $P(\mathbf{x}, y)$, which would require exponential data.

[!TIP] Key Insight: Naive Bayes is generative (models $P(\mathbf{x}|y)$). Despite its strong independence assumption, it's robust to irrelevant features and works well with small datasets.

1.3 Unsupervised Learning

1.3.1 Clustering

k-means Algorithm

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

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

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

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

Objective: Minimize within-cluster sum of squares (WCSS):

$$ J = \sum_{i=1}^k \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - \boldsymbol{\mu}_i\|^2 $$

Hierarchical Clustering

• AGNES (Agglomerative Nesting): Bottom-up. Start with each point as a cluster. Iteratively merge the two closest clusters until one cluster remains. Linkage criteria: Single (min distance), Complete (max distance), Average.

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

• Comparison:

  | | AGNES | DIANA | | :--- | :--- | :--- | | Approach | Agglomerative | Divisive | | Complexity | $$\displaystyle O(n^3) $$ (naive), $$\displaystyle O(n^2 \log n) $$ with heap | $$\displaystyle O(2^n) $$ (exponential) | | Flexibility | Less flexible once merged | More flexible at top levels | | Use Case | Common, intuitive | Rarely used due to cost |

Gaussian Mixture Models (GMM)

• Probabilistic Model: Assumes data generated from a mixture of $k$ Gaussian distributions.

• Parameters: For each cluster $k$: mean $$\displaystyle \boldsymbol{\mu}_k $$, covariance $$\displaystyle \boldsymbol{\Sigma}_k $$, mixing coefficient $$\displaystyle \pi_k $$ (prior $$\displaystyle P(z=k) $$).

• Likelihood: $$\displaystyle P(\mathbf{x}) = \sum_{k=1}^K \pi_k \mathcal{N}(\mathbf{x}|\boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k) $$.

• Learning: Expectation-Maximization (EM) algorithm.

  • E-step: Compute responsibility $$\displaystyle \gamma(z_k) = P(z=k|\mathbf{x}) $$.

  • M-step: Update $$\displaystyle \pi_k, \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k $$ using $$\displaystyle \gamma(z_k) $$.

• Suitability for Overlapping Clusters: Provides soft assignments (probabilistic membership) and models cluster shape via covariance (e.g., elliptical), unlike k-means (spherical, hard).

Distance Metric - Euclidean Distance

For points $$\displaystyle \mathbf{x} = (x_1,...,x_n) $$, $$\displaystyle \mathbf{y} = (y_1,...,y_n) $$:

$$ d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^n (x_i - y_i)^2} $$

[!TIP] Numerical Tip: For k-means, always compute distance before squaring to avoid errors. $$\displaystyle \|\mathbf{x}-\boldsymbol{\mu}\|^2 = \sum (x_i - \mu_i)^2 $$.

1.3.2 Dimensionality Reduction

Principal Component Analysis (PCA)

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

• Steps:

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

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

  3. Compute eigenvectors/eigenvalues of $\mathbf{C}$.

  4. Sort eigenvectors by decreasing eigenvalues. Top d eigenvectors form projection matrix $\mathbf{W}$.

  5. Transform: $$\displaystyle \mathbf{Y} = \mathbf{X}\mathbf{W} $$.

• Interpretation: Captures global linear structure. Maximizes preserved variance.

Locally Linear Embedding (LLE)

• Goal: Preserve local geometric relationships (neighborhoods) while reducing dimensionality. Non-linear method.

• Steps:

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

  2. Compute reconstruction weights $$\displaystyle \mathbf{W}_{ij} $$ that minimize error of reconstructing $$\displaystyle \mathbf{x}_i $$ from its neighbors: $$\displaystyle \min_{\mathbf{W}_i} \|\mathbf{x}_i - \sum_j \mathbf{W}_{ij} \mathbf{x}_j\|^2 $$, subject to $$\displaystyle \sum_j \mathbf{W}_{ij}=1 $$.

  3. Compute low-dimensional embeddings $$\displaystyle \mathbf{y}_i $$ that preserve these weights: $$\displaystyle \min_{\mathbf{Y}} \sum_i \|\mathbf{y}_i - \sum_j \mathbf{W}_{ij} \mathbf{y}_j\|^2 $$.

• When to prefer LLE over PCA:

  • Data lies on a non-linear manifold (e.g., Swiss roll, face images with varying pose/expression).

  • Local neighborhood structure is more important than global variance.

  • PCA would require many components to capture manifold structure; LLE can unfold it with fewer dimensions.

[!TIP] Comparison: PCA is linear and global; LLE is non-linear and local. Use PCA for quick, linear compression; use LLE when you suspect underlying non-linear manifold.

1.4 Ensemble Learning

Bagging (Bootstrap Aggregating)

• Technique: Create B bootstrap samples (random sampling with replacement). Train B base learners (e.g., decision trees) independently. Combine predictions by voting (classification) or averaging (regression).

• Variance Reduction: By averaging many high-variance models (like deep trees), bagging reduces overall variance without increasing bias significantly. Works best with unstable learners.

• Example: Random Forest is a bagged ensemble of decision trees with random feature selection.

Stacking (Stacked Generalization)

• Technique: Train multiple base learners (level-0). Their predictions become features for a meta-learner (level-1), which is trained to make the final prediction.

• Role of Meta-learners: Learns how to best combine the diverse predictions of base models. Often a simple linear model (e.g., linear regression) or logistic regression is used to prevent overfitting.

• Process:

  1. Split training data into folds.

  2. Train base learners on training folds, predict on hold-out folds → generate meta-features.

  3. Train meta-learner on these meta-features and true labels.

Model Combination Schemes Comparison

[!TIP] Exam Tip: Bagging reduces variance (by averaging), boosting reduces bias (by focusing on errors). Stacking can, in theory, reduce both but is more complex.

1.5 Probabilistic Graphical Models

Bayesian Belief Networks (BBNs) / Bayesian Networks

• Definition: A directed acyclic graph (DAG) where nodes represent random variables and edges represent conditional dependencies.

• Construction:

  1. Nodes: Define the set of random variables $$\displaystyle X_1, ..., X_n $$.

  2. Edges: Draw directed edge $$\displaystyle X_i \rightarrow X_j $$ if $$\displaystyle X_j $$ depends directly on $$\displaystyle X_i $$ (parent-child relationship). No cycles.

  3. Conditional Probability Tables (CPTs): For each node, specify $$\displaystyle P(X_j | \text{Parents}(X_j)) $$. For root nodes (no parents), specify prior $$\displaystyle P(X_j) $$.

• Joint Probability Table: The full joint distribution factorizes according to the graph structure:

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

This factorization exploits conditional independence to avoid exponential table size.

[!TIP] Example: For a simple network $$\displaystyle A \rightarrow B \rightarrow C $$, joint is $P(A)P(B|A)P(C|B)$. Much smaller than full $$\displaystyle 2^3 $$ table if discrete binary.

1.6 Frequent Pattern Mining

Concept & Importance

• Frequent Pattern: An itemset (set of items), subsequence, or substructure that appears in a dataset with frequency at least a user-specified minimum support threshold ($$\displaystyle min\_sup $$).

• Importance: Forms the basis for association rule mining (e.g., "If bread, then milk"). Key application: Market Basket Analysis—discovering items frequently bought together to inform store layout, promotions, cross-selling.

k-Frequent Itemset Mining (Apriori Algorithm)

• Principle (Apriori Property): All subsets of a frequent itemset must also be frequent. (If $\{A,B\}$ is infrequent, $\{A,B,C\}$ cannot be frequent).

• Steps:

  1. Initialize: $$\displaystyle L_1 $$ = frequent 1-itemsets (scan DB, count support).

  2. Iterate for $$\displaystyle k=2,3,... $$ until no new frequent itemsets:

     • Candidate Generation: $$\displaystyle C_k $$ = set of candidate k-itemsets formed by joining $$\displaystyle L_{k-1} $$ with itself (ensuring first $k-2$ items are same).

     • Prune: Remove any candidate in $$\displaystyle C_k $$ having an infrequent $(k-1)$-subset (using Apriori property).

     • Counting: Scan DB, count support of candidates in $$\displaystyle C_k $$.

     • Output: $$\displaystyle L_k $$ = candidates in $$\displaystyle C_k $$ with support $$\displaystyle \geq min\_sup $$.

  3. Result: $$\displaystyle \bigcup_k L_k $$ = all frequent itemsets.

• FP-Growth (Alternative): Uses a compact FP-tree structure to mine patterns without candidate generation, often faster than Apriori.

[!TIP] Numerical Tip: For given transactions, list all 1-itemsets, apply $$\displaystyle min\_sup $$, then generate 2-itemset candidates only from frequent 1-itemsets, prune using Apriori, count, etc.

1.7 Performance Evaluation and Metrics

Effect of Noise on Classifier Performance

• Noise (mislabeled data, irrelevant features) generally degrades performance.

• Impact: Increases bias if model is simple (underfits noisy patterns) or variance if model is complex (overfits noise). Leads to lower accuracy, precision, recall.

• Example: In a binary classification with 5% label noise, even an optimal classifier's error rate will be at least 5% (Bayes error rate increases).

False Positives, False Negatives & Bayes Theorem

• Confusion Matrix:

  | | Predicted + | Predicted - | | :--- | :--- | :--- | | Actual + | TP (True Positive) | FN (False Negative) | | Actual - | FP (False Positive) | TN (True Negative) |

• Key Metrics:

  • Precision = $TP / (TP + FP)$ (of predicted positives, how many correct?)

  • Recall = $TP / (TP + FN)$ (of actual positives, how many found?)

  • F1-Score = $$\displaystyle 2 \cdot \frac{\text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}} $$.

• Bayes Theorem Application: Computes posterior probability given evidence.

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

Where:

*   $P(D)$ = prior probability (e.g., prevalence)

*   $P(T|D)$ = sensitivity (1 - false negative rate)

*   $P(T|\neg D)$ = false positive rate

*   $$\displaystyle P(T) = P(T|D)P(D) + P(T|\neg D)P(\neg D) $$

Cost Function Convergence in Regression

• Objective: Minimize cost function $J(\mathbf{w})$ (e.g., MSE, SSE).

• Convergence: Achieved when $$\displaystyle \|\nabla J(\mathbf{w})\| < \epsilon $$ or $$\displaystyle |J^{(t)} - J^{(t-1)}| < \epsilon $$.

• Relation to SSE: For linear regression with MSE, $$\displaystyle J(\mathbf{w}) = \frac{1}{n} SSE $$. Convergence of $J$ implies SSE is minimized (for convex problems, global optimum).

1.8 Special Topics

Self-Organizing Maps (SOM)

• Concept: An unsupervised neural network that produces a low-dimensional (typically 2D), discretized representation of input space, preserving topological relationships. Also called Kohonen maps.

• Process:

  1. Initialization: Grid of neurons (e.g., 10x10) with random weight vectors $$\displaystyle \mathbf{w}_i $$ of same dimension as input.

  2. Competition: For input $\mathbf{x}$, find neuron $c$ with weight most similar to $\mathbf{x}$ (using Euclidean distance). $c$ is the Best Matching Unit (BMU).

  3. Cooperation: BMU's neighborhood (on grid) is determined. Neighborhood size decreases over time.

  4. Adaptation: Update weights of BMU and its neighbors: $$\displaystyle \mathbf{w}_i(t+1) = \mathbf{w}_i(t) + \alpha(t) h_{ci}(t) (\mathbf{x} - \mathbf{w}_i(t)) $$, where $$\displaystyle h_{ci} $$ is neighborhood kernel (e.g., Gaussian), $\alpha$ is learning rate.

  5. Repeat for many inputs, decreasing $\alpha$ and neighborhood radius.

• Diagram & Example:

  DiagramCANVAS: A 2D grid of neurons (nodes) arranged in a rectangular lattice. Each neuron has a weight vector in high-D input space. An input vector (star) is shown. The BMU (highlighted node) and its neighboring nodes (shaded region) are indicated. Arrows show weight updates towards the input for BMU and neighbors.

  Example: Document clustering. Each document is a high-D vector (word frequencies). SOM maps similar documents to adjacent grid cells, revealing topics.

[!TIP] Key Difference from k-means: SOM provides a topology-preserving map; k-means just gives cluster centers. SOM's grid structure visualizes relationships between clusters.