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

UNIT 3: MACHINE LEARNING FUNDAMENTALS AND TECHNIQUES

1.0 Foundations of Machine Learning

1.1 Learning Paradigms

• Supervised Learning: Model learns from labeled data (input-output pairs).

  Examples: Classification (spam detection), Regression (price prediction).

• Unsupervised Learning: Model finds patterns in unlabeled data.

  Examples: Clustering (customer segmentation), Dimensionality reduction (PCA).

• Reinforcement Learning: Agent learns by interacting with an environment, receiving rewards/penalties.

  Examples: Game playing (AlphaGo), Robotics.

1.2 Hypothesis Spaces

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

  Implications: Lower risk of overfitting, but may underfit if too restrictive.

• Infinite Hypothesis Space: Continuum of models (e.g., linear regression with real-valued weights).

  Implications: High capacity to fit complex patterns, but requires regularization to avoid overfitting.

• Generalization: Ability to perform well on unseen data. Overfitting occurs when model complexity exceeds data information.

[!TIP] Exam Focus: Contrast finite/infinite spaces with respect to model complexity and generalization. Use VC dimension as a measure of capacity for infinite spaces.

1.3 Noise in Data and Its Effect on Classifier Performance

• Noise: Errors in feature values (feature noise) or labels (class noise).

• Effects:

  • Increases bias if model is too simple (underfitting).

  • Increases variance if model is too complex (overfitting).

  • Reduces overall accuracy and reliability.

• Mitigation: Use robust algorithms (e.g., Naive Bayes handles noise better), regularization, data cleaning.

2.0 Supervised Learning: Regression

2.1 Linear Regression

• Simple Linear Regression: One independent variable.

  Model: $$\displaystyle y = \beta_0 + \beta_1 x + \epsilon $$

• Multiple Linear Regression: Multiple independent variables.

  Model: $$\displaystyle y = \beta_0 + \beta_1 x_1 + \dots + \beta_n x_n + \epsilon $$

• Cost Function (SSE):

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

Minimized via gradient descent or normal equation.

• Convergence: Cost function decreases iteratively until gradient ≈ 0 or max iterations.

• Coefficient Calculation (simple linear):

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

• Model Fitting: Estimate $\beta$ coefficients from training data.

• Prediction: $$\displaystyle \hat{y} = \beta_0 + \beta_1 x $$ (or multiple features).

\boxed{\text{SSE} = \sum (y_i - \hat{y}_i)^2}

[!TIP] Numerical Problem: Given data points (x,y), compute $$\displaystyle \beta_0 $$, $$\displaystyle \beta_1 $$, SSE, and predict for new x. Use means and sums.

2.2 Logistic Regression

• Comparison with Linear Regression:

  • Output: Probability (0 to 1) via sigmoid function, not continuous value.

  • Used for classification (binary), linear regression for regression.

  • Loss function: Cross-entropy, not SSE.

• Applications: Spam classification, disease diagnosis.

• Advantages: Outputs probabilities, handles nonlinear decision boundaries via feature transformation, computationally efficient.

3.0 Supervised Learning: Classification

3.1 Support Vector Machines (SVM)

• Linear Classification: Find hyperplane $$\displaystyle \mathbf{w} \cdot \mathbf{x} + b = 0 $$ separating classes.

• Margin: Distance between hyperplane and nearest data points.

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

• Maximum Margin Hyperplane: Optimize $$\displaystyle \min \frac{1}{2} \|\mathbf{w}\|^2 $$ subject to $$\displaystyle y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 $$.

• Support Vectors: Data points lying on margin boundaries ($$\displaystyle y_i(\mathbf{w} \cdot \mathbf{x}_i + b) = 1 $$). They define the hyperplane.

• Problem-Solving for Linear Separable Data:

  1. Identify support vectors (closest points from each class).

  2. Solve constrained optimization (e.g., using Lagrange multipliers).

  3. Compute $\mathbf{w}$ and $b$ from support vectors.

[!TIP] Exam Problem: Given 2D points, plot, identify support vectors, derive $\mathbf{w}$ and $b$ by solving margin equations.

3.2 Decision Trees

• ID3 Algorithm:

  1. Start with all training instances at root.

  2. For each attribute, compute entropy and information gain.

  3. Select attribute with highest gain as splitting node.

  4. Recur on subsets until all instances belong to same class or no attributes left.

• Entropy (measure of impurity):

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

where $$\displaystyle p_i $$ = proportion of class $i$ in set $S$.

• Information Gain:

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

• Tree Construction: Greedy top-down splitting; handle continuous attributes by thresholding.

3.3 Probabilistic Classifiers

3.3.1 Naive Bayes Classifier

• Assumptions: Feature independence given class $C$: $$\displaystyle P(\mathbf{x} \mid C) = \prod_i P(x_i \mid C) $$.

• Posterior Probability:

$$P(C \mid \mathbf{x}) = \frac{P(C) \prod_i P(x_i \mid C)}{P(\mathbf{x})}$$

• Prior Probability: $P(C)$ (from training data frequency).

• Simplification: Denominator $P(\mathbf{x})$ constant for all classes; compare numerators only.

• Application: Text classification (spam filter), medical diagnosis.

[!TIP] For continuous features, assume Gaussian distribution: $$\displaystyle P(x_i \mid C) = \frac{1}{\sqrt{2\pi\sigma_C^2}} e^{-(x_i - \mu_C)^2/(2\sigma_C^2)} $$.

3.3.2 Bayesian Learning

• Probabilistic Approach: Treat hypotheses as random variables; update beliefs via Bayes' theorem.

$$P(h \mid D) = \frac{P(D \mid h) P(h)}{P(D)}$$

• Example Applications: Spam filtering, disease testing.

3.3.3 Bayesian Belief Networks (BBN)

• Construction:

  • Nodes: Random variables.

  • Edges: Direct dependencies (no cycles).

  • Conditional Probability Tables (CPT): $P(\text{child} \mid \text{parents})$ for each node.

• Joint Probability Table Derivation:

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

• Example: Malaria ($M$) and Headache ($H$) network:

  $$\displaystyle P(M,H) = P(M) \cdot P(H \mid M) $$ given $$\displaystyle P(M)=0.03 $$, $$\displaystyle P(H \mid M)=0.6 $$, $$\displaystyle P(H \mid \neg M)=0.2 $$.

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

4.0 Neural Networks

4.1 Multilayer Perceptron (MLP)

• Structure:

  • Input Layer: Receives features (size = number of features).

  • Hidden Layer(s): One or more; apply nonlinear transformations.

  • Output Layer: Produces prediction (size = number of classes/regression output).

• Fully connected between layers.

4.2 Activation Functions

• Role: Introduce nonlinearity, enabling learning of complex patterns. Without them, MLP reduces to linear model.

• Common Functions:

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

  • ReLU: $$\displaystyle \text{ReLU}(z) = \max(0,z) $$. Computationally efficient, avoids vanishing gradient for positive $z$.

  • Tanh: $$\displaystyle \tanh(z) = \frac{e^z - e^{-z}}{e^z + e^{-z}} $$, output (-1,1).

[!TIP] ReLU preferred in hidden layers for deep networks due to sparsity and faster convergence.

5.0 Unsupervised Learning: Clustering

5.1 Partitional Clustering: K-means

• Steps:

  1. Initialize $k$ cluster centers (randomly or by heuristics).

  2. Assignment: Assign each point to nearest center using Euclidean distance:

     $$\displaystyle d(\mathbf{x}, \mathbf{c}) = \sqrt{\sum_{i=1}^{n} (x_i - c_i)^2} $$.

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

  4. Repeat until centers stabilize (convergence).

• Problem-Solving: Given initial centers, show assignments and updated centers per iteration.

• Numerical Example:

  Points: A1(2,10), A2(2,5), B1(5,8), B2(7,5), C1(1,2), C2(4,9).

  Initial centers: A1, B1, C1.

  First round: Assign all points to nearest center, recompute means.

  Final clusters: After convergence.

5.2 Hierarchical Clustering

• AGNES (Agglomerative Nesting):

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

  • Linkage criteria: single (min distance), complete (max distance), average.

• DIANA (Divisive Analysis):

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

• Comparison:

5.3 Probabilistic Clustering: Gaussian Mixture Models (GMM)

• Concept: Model clusters as Gaussian distributions with unknown parameters (mean, covariance, mixture weights).

• Suitability for Overlapping Clusters: Soft assignments (probabilistic membership) allow points to belong to multiple clusters with certain probabilities.

• Estimation: Use Expectation-Maximization (EM) algorithm:

  1. E-step: Compute responsibility of each cluster for each point.

  2. M-step: Update parameters (means, covariances, weights) using responsibilities.

6.0 Dimensionality Reduction and Visualization

6.1 Principal Component Analysis (PCA)

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

• Steps:

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

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

  3. Compute eigenvectors of $\mathbf{C}$; sort by descending eigenvalues.

  4. Project data onto top $k$ eigenvectors.

• Relation to Dimensionality Reduction: Reduce $n$ dimensions to $$\displaystyle k < n $$ while preserving maximum variance.

• Example Application: Face recognition (eigenfaces), noise reduction.

6.2 Locally Linear Embedding (LLE)

• Concept: Preserve local neighborhoods; each point reconstructed as linear combination of neighbors.

• Comparison with PCA:

  • PCA: Global linear method; maximizes global variance.

  • LLE: Local nonlinear method; preserves local geometry, suitable for manifolds.

• When to Prefer LLE over PCA: Data lies on a nonlinear manifold (e.g., Swiss roll, images with pose variations).

6.3 Self-Organizing Maps (SOM)

• Explanation: Unsupervised neural network for dimensionality reduction and visualization.

  • Structure: 2D grid of neurons (nodes), each with weight vector same dimension as input.

  • Training:

    1. Initialize weights (random or from data).

    2. For each input $\mathbf{x}$:

       • Find Best Matching Unit (BMU): neuron with weight closest to $\mathbf{x}$.

       • Update BMU and its neighbors: $$\displaystyle \mathbf{w}_t \leftarrow \mathbf{w}_{t-1} + \alpha(t) \cdot h_{bmu,i}(t) \cdot (\mathbf{x} - \mathbf{w}_{t-1}) $$.

    3. Reduce learning rate $\alpha$ and neighborhood radius $h$ over time.

• Diagram:

  DiagramCANVAS: Input layer (n-dimensional) fully connected to 2D grid of neurons. During training, BMU and its neighbors adjust weights toward input vector, with neighborhood function (e.g., Gaussian) decaying with distance from BMU.

• Use Cases: Data visualization (e.g., gene expression data), feature mapping, anomaly detection.

7.0 Ensemble Learning

7.1 Bagging (Bootstrap Aggregating)

• Technique:

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

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

  3. Combine predictions: majority vote (classification) or average (regression).

• Variance Reduction Mechanism: Averaging reduces variance by factor $$\displaystyle \frac{1}{B} $$ if models are independent. Decorrelation via bootstrap sampling.

• Example: Random Forest (bagged decision trees with feature randomness).

7.2 Stacking

• Role of Meta-Learners:

  • Base learners: Trained on original data; outputs predictions.

  • Meta-learner: Trained on predictions of base learners (as features) to learn optimal combination.

• Contribution to Performance: Leverages strengths of diverse base models; meta-learner learns to weight predictions, often improving accuracy beyond any single model.

7.3 Model Combination Schemes

[!TIP] Stacking typically outperforms voting/averaging but requires careful cross-validation to avoid overfitting.

8.0 Association Rule Mining

8.1 Frequent Pattern Mining

• Importance in Market Basket Analysis: Discover items frequently bought together (e.g., "bread and butter").

• Key Metrics:

  • Support: Proportion of transactions containing itemset $X$:

    $$\displaystyle \text{supp}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|} $$.

  • Confidence: Conditional probability of $Y$ given $X$:

    $$\displaystyle \text{conf}(X \Rightarrow Y) = \frac{\text{supp}(X \cup Y)}{\text{supp}(X)} $$.

  • Lift: $$\displaystyle \text{lift}(X \Rightarrow Y) = \frac{\text{conf}(X \Rightarrow Y)}{\text{supp}(Y)} $$.

8.2 Apriori Algorithm (K-Frequent Itemset Mining)

• Principle: Downward closure—all subsets of a frequent itemset are frequent.

• Process:

  1. Find frequent 1-itemsets by scanning DB, pruning those below min_support.

  2. For $$\displaystyle k = 2, 3, \dots $$:

     • Generate candidate $k$-itemsets from frequent $(k-1)$-itemsets (join step).

     • Prune candidates with infrequent subsets.

     • Scan DB, count support of remaining candidates.

     • Keep those with support ≥ min_support.

  3. Stop when no new frequent itemsets.

• Problem-Solving: Given transaction DB and min_support, list all frequent itemsets.

\boxed{\text{If } X \text{ is frequent, then all subsets of } X \text{ are frequent.}}

9.0 Advanced Topics and Applications

9.1 Bayes' Theorem in Real-World Problems

• Example: Covid Drug Test

  Given:

  • $$\displaystyle P(D) = 0.02 $$ (2% take drugs)

  • $$\displaystyle P(T^+ \mid \neg D) = 0.01 $$ (false positive rate)

  • $$\displaystyle P(T^- \mid D) = 0.05 $$ (false negative rate)

  Find $$\displaystyle P(D \mid T^+) $$.

• Solution:

  • $$\displaystyle P(T^+ \mid D) = 1 - 0.05 = 0.95 $$

  • $$\displaystyle P(T^+) = P(T^+ \mid D)P(D) + P(T^+ \mid \neg D)P(\neg D) = 0.95 \times 0.02 + 0.01 \times 0.98 = 0.019 + 0.0098 = 0.0288 $$

  • $$\displaystyle P(D \mid T^+) = \frac{P(T^+ \mid D)P(D)}{P(T^+)} = \frac{0.019}{0.0288} \approx 0.6604 $$

[!TIP] Common Pitfall: Forgetting to compute total probability $$\displaystyle P(T^+) $$ correctly.

9.2 Evaluation Considerations

• Effect of Noise on Classifier Performance:

  • Noise increases bias (if model too simple) or variance (if model too complex).

  • Example: Label noise in training data leads to overfitting if model has high capacity.

• Model Complexity vs Generalization Trade-off:

  • High complexity (e.g., deep trees, high-degree polynomials): Low bias, high variance → overfitting.

  • Low complexity (e.g., linear models, shallow trees): High bias, low variance → underfitting.

  • Balance: Use cross-validation, regularization (L1/L2), pruning.

Key Formulas Summary

• Linear Regression Coefficients: $$\displaystyle \beta_1 = \frac{\sum (x_i - \bar{x})(y_i - \bar{y})}{\sum (x_i - \bar{x})^2} $$, $$\displaystyle \beta_0 = \bar{y} - \beta_1 \bar{x} $$

• SVM Optimization: $$\displaystyle \min \frac{1}{2} \|\mathbf{w}\|^2 $$ s.t. $$\displaystyle y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 $$

• Entropy: $$\displaystyle H(S) = -\sum p_i \log_2 p_i $$

• Naive Bayes: $$\displaystyle P(C \mid \mathbf{x}) \propto P(C) \prod_i P(x_i \mid C) $$

• PCA: Covariance matrix eigenvectors.

• GMM: EM algorithm for parameters.

• Bayes' Theorem: $$\displaystyle P(A \mid B) = \frac{P(B \mid A) P(A)}{P(B)} $$

Exam Strategy:

• For derivation questions (e.g., SVM, ID3), show step-by-step calculations.

• For numerical problems (regression, k-means, Apriori), present clear tables and iterations.

• Always state assumptions (e.g., Naive Bayes independence, linear separability in SVM).