IIT M IMPROVEMENT AN EXAM QID4 26 Oct - 26 Oct 2025

Concepts this paper tests

Auto-generated summary from the source site. Handy as a checklist; the lessons above explain each idea from scratch.

Here's a comprehensive summary of the core topics, concepts, principles, and equations essential for the "Machine Learning Techniques" exam, derived from the provided questions.

Machine Learning Techniques Exam: Core Topics Summary

This exam focuses heavily on Unsupervised Learning techniques, particularly Clustering and Dimensionality Reduction, alongside foundational Mathematical Concepts from linear algebra, probability, and statistics.

1. Unsupervised Learning: Clustering

1.1 K-Means Clustering (Lloyd's Algorithm)

• Concept: An iterative partitioning algorithm that aims to partition $N$ data points into $K$ clusters, where each data point belongs to the cluster with the nearest mean (centroid).

• Principles:

  • Algorithm Steps:

    1. Initialization: Choose $K$ initial cluster centroids.
    2. Assignment Step (E-step-like): Assign each data point to the cluster whose centroid is closest, typically using squared Euclidean distance.
    3. Update Step (M-step-like): Recalculate the centroids as the mean of all data points assigned to that cluster.
    4. Convergence: Repeat steps 2 and 3 until cluster assignments no longer change or centroids do not move significantly.

  • Properties:

    • Convergence: Always converges in a finite number of iterations to a local optimum of the objective function.
    • Sensitivity to Initialization: The final clustering result can vary significantly based on the initial placement of centroids.
    • Sensitivity to Outliers: Highly sensitive to outliers due to its reliance on means and squared Euclidean distance, which heavily penalizes large distances.
    • Optimality: Does not guarantee finding the global optimal clustering.

• Equations:

  • Squared Euclidean Distance: For points $x = (x_1, \dots, x_D)$ and $y = (y_1, \dots, y_D)$:

    $$||x - y||^2 = \sum_{j=1}^D (x_j - y_j)^2$$

  • K-Means Objective Function (Sum of Squared Errors - SSE):

    $$J = \sum_{k=1}^K \sum_{x \in C_k} ||x - \mu_k||^2$$

    where $C_k$ is the set of points in cluster $k$, and $\mu_k$ is the centroid of cluster $k$.

  • Centroid Update:

    $$\mu_k = \frac{1}{|C_k|} \sum_{x \in C_k} x$$

1.2 K-Means++ Initialization

• Concept: A smart initialization technique for K-Means that selects initial centroids to be far apart, improving the chance of finding a better local optimum.

• Principles:

  • Randomly choose the first center from the data points.
  • For each subsequent center, choose a data point $x$ with probability proportional to its squared distance $D(x)^2$ from the closest existing center.
  • This probabilistic selection biases towards choosing points that are far from already chosen centroids.

• Equations:

  • Probability of selecting next center $x$:

    $$P(x) = \frac{D(x)^2}{\sum_{x' \in \text{data}} D(x')^2}$$

    where $D(x) = \min_{j=1, \dots, l-1} (||x - \mu_j^0||)$ and $\mu_j^0$ are the already chosen initial cluster centers.

1.3 Gaussian Mixture Models (GMM) and Expectation-Maximization (EM) Algorithm

• Concept: A probabilistic model that assumes data points are generated from a mixture of several Gaussian distributions with unknown parameters (means, covariances, and mixing weights). The EM algorithm is used to estimate these parameters.

• Principles:

  • GMM Likelihood: For a dataset $X = \{x_1, \dots, x_N\}$ and $K$ Gaussian components, the likelihood function for parameters $\theta = \{\pi_k, \mu_k, \Sigma_k\}_{k=1}^K$ is:

    $$L(\theta; X) = \prod_{i=1}^N \sum_{k=1}^K \pi_k N(x_i|\mu_k, \Sigma_k)$$

    where $\pi_k$ are the mixing coefficients (prior probabilities of components), and $N(x_i|\mu_k, \Sigma_k)$ is the probability density function (PDF) of the $k$-th Gaussian component.

  • EM Algorithm: An iterative optimization algorithm for finding maximum likelihood estimates of parameters in probabilistic models, especially when the model depends on unobserved latent variables.

    • E-step (Expectation): Calculate the "responsibilities" (posterior probabilities) that each data point belongs to each component, given the current parameter estimates.
    • M-step (Maximization): Update the parameters (means, covariances, mixing weights) to maximize the expected log-likelihood found in the E-step.

• Equations:

  • 1D Gaussian PDF:

    $$N(x|\mu, \sigma^2) = \frac{1}{\sigma\sqrt{2\pi}} \exp\left(-\frac{1}{2}\left(\frac{x-\mu}{\sigma}\right)^2\right)$$

  • Responsibility $\lambda_i^k$ (posterior probability for data point $x_i$ belonging to component $k$):

    $$\lambda_i^k = P(Z=k|x_i, \theta) = \frac{\pi_k N(x_i|\mu_k, \Sigma_k)}{\sum_{j=1}^K \pi_j N(x_i|\mu_j, \Sigma_j)}$$

    (This is the formula for $\gamma(z_{ik})$ as seen in textbooks).

2. Unsupervised Learning: Dimensionality Reduction

2.1 Principal Component Analysis (PCA)

• Concept: A linear dimensionality reduction technique that transforms data to a new coordinate system such that the greatest variance by any projection of the data lies on the first coordinate (first principal component), the second greatest variance on the second coordinate, and so on.

• Principles:

  • Covariance Matrix: PCA is based on the eigenvalue decomposition of the data's covariance matrix.
  • Principal Components: The principal components are the eigenvectors of the covariance matrix, ordered by their corresponding eigenvalues in descending order.
  • Variance Explained: Each eigenvalue represents the amount of variance captured along its corresponding principal component.
  • Intrinsic Dimensionality: If a dataset inherently lies in a $k$-dimensional linear subspace, then its covariance matrix will have $k$ non-zero eigenvalues, and $k$ principal components are sufficient to reconstruct the data with zero error.
  • Reconstruction Error: When reducing dimensionality, the reconstruction error relates to the variance not captured by the selected principal components. Zero residue implies all variance is captured.

• Equations:

  • Mean Vector: For a dataset $X \in \mathbb{R}^{N \times D}$ where $N$ is the number of samples and $D$ is the number of features, the mean of feature $j$ is:

    $$\bar{x}_j = \frac{1}{N} \sum_{i=1}^N X_{ij}$$
  • Mean-Centered Data Matrix: $X_{centered} = X - \text{mean}(X)$ (each row has mean subtracted).

  • Sample Covariance Matrix: For mean-centered data $X_{centered}$:

    $$\Sigma = \frac{1}{N-1} X_{centered}^T X_{centered}$$

    (Often $1/N$ is used in ML contexts for population covariance, or when treating $X$ as a population.) For a 2D dataset with points $(x_i, y_i)$:

    $$\Sigma = \frac{1}{N-1} \begin{pmatrix} \sum (x_i - \bar{x})^2 & \sum (x_i - \bar{x})(y_i - \bar{y}) \\ \sum (y_i - \bar{y})(x_i - \bar{x}) & \sum (y_i - \bar{y})^2 \end{pmatrix}$$
  • Eigenvalue Decomposition: $\Sigma v = \lambda v$, where $\lambda$ is an eigenvalue and $v$ is an eigenvector.

  • Proportion of Variance Explained (PVE) by $j$-th principal component:

    $$PVE_j = \frac{\lambda_j}{\sum_{i=1}^D \lambda_i}$$

    where $\lambda_j$ is the eigenvalue for the $j$-th principal component and $\sum_{i=1}^D \lambda_i$ is the total variance.

3. Kernel Functions

• Concept: Functions that compute the inner product between two vectors in a high-dimensional feature space, without explicitly transforming the data into that space (the "kernel trick"). Used in algorithms like SVMs and Kernel PCA to handle non-linear relationships.

• Principles:

  • A function $K(x, y)$ is a valid kernel if it corresponds to an inner product in some high-dimensional feature space, i.e., $K(x, y) = \phi(x)^T \phi(y)$ for some mapping $\phi$.
  • Mercer's Theorem: Provides formal conditions for a function to be a valid kernel (the kernel matrix must be positive semi-definite).

• Common Valid Kernels:

  • Radial Basis Function (RBF) / Gaussian Kernel:

    $$K(x, y) = \exp\left(-\frac{||x - y||^2}{2\sigma^2}\right) \quad \text{or} \quad K(x, y) = \exp(-\gamma ||x - y||^2)$$

    where $\sigma > 0$ (or $\gamma > 0$) is a bandwidth parameter.

  • Polynomial Kernel:

    $$K(x, y) = (x \cdot y + c)^d$$

    where $c \ge 0$ is a constant and $d \in \mathbb{N}$ is the degree of the polynomial.

  • Linear Kernel:

    $$K(x, y) = x \cdot y$$

• Non-Valid Kernels (Example):

  • $K(x, y) = ||x - y||$ (absolute distance) is generally not a valid kernel as it does not typically correspond to an inner product.

4. Bayesian Inference (Beta-Binomial Model)

• Concept: A framework for updating beliefs about parameters of a distribution using observed data. The Beta-Binomial model is a common example of a conjugate prior relationship.

• Principles:

  • Bayes' Theorem: Relates the posterior probability of a parameter ($\theta$) given data ($D$) to the likelihood of the data given the parameter and the prior probability of the parameter.

    $$P(\theta|D) = \frac{P(D|\theta) P(\theta)}{P(D)}$$
  • Conjugate Prior: When the posterior distribution is in the same family as the prior distribution. For a Binomial likelihood, the Beta distribution is a conjugate prior.
  • Beta Distribution: A continuous probability distribution defined on the interval $[0, 1]$, often used to model probabilities or proportions.
  • Binomial Distribution: A discrete probability distribution of the number of successes in a sequence of $n$ independent yes/no experiments.

• Equations:

  • Beta Prior Distribution: $\theta \sim \text{Beta}(a, b)$
  • Binomial Likelihood: Given $k$ successes in $n$ trials: $P(k|n, \theta) \sim \text{Binomial}(n, \theta)$

  • Beta Posterior Distribution: Given a $\text{Beta}(a, b)$ prior and observing $k$ successes in $n$ trials, the posterior is:

    $$\theta|k, n \sim \text{Beta}(a+k, b+n-k)$$

  • Expected Value of a Beta Distribution: For $\text{Beta}(\alpha, \beta)$:

    $$E[\theta] = \frac{\alpha}{\alpha + \beta}$$

  • Posterior Mean: The expected value of the posterior distribution, used as an estimate for $\theta$:

    $$E[\theta|D] = \frac{a+k}{a+k+b+n-k} = \frac{a+k}{a+b+n}$$