CS771 Machine Learning Portfolio

A comprehensive collection of advanced machine learning implementations developed for the CS771: Introduction to Machine Learning course at IIT Kanpur. This repository demonstrates rigor in mathematical derivation, algorithm optimization, and application to hardware security.

📂 Repository Structure

CS771-ML-Coursework/
│
├── 01-SVM-Optimization/               # Debugging SDCM & Weak Duality Analysis
│   ├── documentation/
│   │   └── CS771_Minor_Assignment_1.pdf
│   └── code/
│
├── 02-GMM-Generative-Classification/  # EM Algorithm & Missing Data Inference
│   ├── documentation/
│   │   └── CS771_Minor_Assignment_2.pdf
│   └── code/
│
└── 03-Kernel-Methods-PUF-Security/    # Custom Kernels & XOR Arbiter PUF Attacks
    ├── documentation/
    │   └── CS771_Major_Assignment_1.pdf
    └── code/
        └── submit.py                  # Python implementation for Kernel derivation & PUF decoding

---

🚀 Projects Overview

1. Hardware Security: Attacking XOR Arbiter PUFs & Custom Kernels

Location: 03-Kernel-Methods-PUF-Security/

Context: Hardware security relies on Physical Unclonable Functions (PUFs). Modeling these requires advanced regression techniques, while attacking them requires solving inverse problems on high-dimensional tensors.

• Semi-Parametric Regression:

  • Addressed a video production resource problem where staff requirements $y$ depend linearly on duration $x$ but non-linearly on metadata $z$.
  • Derivation: Mathematically derived a custom kernel $\hat{K}$ to map the semi-parametric problem $y = w(z)x + b$ into a purely non-parametric Kernel Ridge Regression form.
  • The Kernel: $\hat{K}((x_1, z_1), (x_2, z_2)) = x_1 x_2 (z_1^T z_2 + c)^d + 1$.
  • Optimization: Conducted grid search to identify optimal hyperparameters ($d=2, c=0.09$) balancing computational cost $O(n_1 n_2)$ and $R^2$ score.

• PUF Model Inversion (Cryptography):

  • Challenge: Given a 1089-dimensional linear model $w$ of a 32-bit XOR Arbiter PUF (where $w = u \otimes v$), recover the underlying 256 physical delay parameters.
  • Method: Implemented a my_decode algorithm using linear algebra to reverse the Kronecker product, solving $W = uv^T$ via matrix rank-1 decomposition to extract delay vectors $u$ and $v$.
  • Delay Recovery: Inverted the linear model equations involving characteristic difference parameters $\alpha_i$ and $\beta_i$ to recover the specific non-negative delays ($p_i, q_i, r_i, s_i$).

2. Generative Classification: Gaussian Mixture Models (GMM)

Location: 02-GMM-Generative-Classification/

Context: Moving beyond simple discriminative boundaries to model the underlying distribution of the MNIST dataset.

• Expectation-Maximization (EM):
  • Implemented the EM algorithm from scratch to train generative multi-classification models where each class-conditional distribution $\mathbb{P}[x|y=c]$ is a mixture of $K$ Gaussians.
  • E-Step: Computed component weights (responsibilities) $w_{ik}^{(c,t)}$ using Bayes' rule.
  • M-Step: Maximized the $Q$-function to update component selection priors $\pi_k^c$, means $\mu_k^c$, and covariance matrices $\Sigma_k^c$.
• Inference on Censored Data:
  • Developed a specialized inference engine to classify images with missing (censored) pixels.
  • Implemented marginalization over latent components to reconstruct missing features $\hat{x}_m$ based on observed features $x_o$ by maximizing $\mathbb{P}[v | x_o^t, \hat{y}^t, \theta]$.
  • Result: Achieved robust accuracy even with significant data corruption.

3. Optimization Engines: Debugging C-SVM

Location: 01-SVM-Optimization/

Context: Deep dive into the internal mechanics of the Stochastic Dual Coordinate Ascent Method (SDCM).

• Algorithm Repair:
  • Identified and fixed critical errors in a broken SDCM implementation, including incorrect Lagrangian updates (failing to account for existing $\alpha$ values) and projection logic errors (incorrectly clipping $\alpha \in [0, C]$).
  • Corrected the bias update $b_{SDCM}$ and weight vector $w_{SDCM}$ updates to strictly follow the coordinate ascent rule.
• Theoretical Verification:
  • Conducted primal-dual gap analysis to verify the Weak Duality Theorem.
  • Demonstrated that the dual objective function approaches the primal from below, strictly adhering to $f_{dual}(\alpha) \leq f_{primal}(w)$ throughout convergence.
  • Analyzed convergence behavior across different hyperparameters ($C$) and coordinate generation strategies (cyclic vs. random).

---

🛠️ Technical Stack

• Languages: Python 3.x
• Libraries: NumPy (Vectorization/Linear Algebra), Scikit-Learn (Kernel Ridge base), Matplotlib (Convergence visualization).
• Concepts: Kronecker Products, Lagrangian Duality, Convex Optimization, Expectation-Maximization, Kernel Methods.

📄 References

• Assignments and problem statements authored by the course instructor at IIT Kanpur (CS771).
• Specific derivations and proofs available in the PDF documentation within each project folder.

---

This portfolio represents coursework completed for CS771.