IIT M IMPROVEMENT AN EXAM QIP3 13 July - 13 Jul 2025

Concepts this paper tests

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

Summary of Core Topics, Concepts, Principles, and Equations

1. K-means and K-means++ Algorithm

• Core Concepts:

  • K-means is a clustering algorithm that partitions data into K clusters.
  • K-means++ improves the initialization process of K-means by spreading out the initial centroids.

• Key Equations:

  • Objective function: $F(z_1, \dots, z_n) = \sum_{i=1}^{n} ||x_i - \mu_{z_i}||^2$
  • Convergence: The algorithm converges when the objective value stabilizes.

2. Kernel Functions and Kernel PCA

• Core Concepts:

  • Kernel functions map data into higher-dimensional spaces.
  • Kernel PCA is a non-linear extension of PCA using kernel functions.

• Key Equations:

  • Kernel function: $k(x, y) = \phi(x)^T \phi(y)$
  • Centered kernel matrix: $k_{ij}^c = k_{ij} - \theta_i \mathbb{1}_j^T - \mathbb{1}_i \theta_j^T + P \mathbb{1}_i \mathbb{1}_j^T$
  • Polynomial kernel: $k(x_i, x_j) = (1 + x_i^T x_j)^2$

3. Expectation-Maximization (EM) Algorithm

• Core Concepts:

  • EM algorithm is used for finding maximum likelihood estimates in models with latent variables.
  • E-step: Estimate the latent variables.
  • M-step: Maximize the likelihood over the model parameters.

• Key Principles:

  • EM algorithm converges to a local optimum.
  • Poor initialization can affect the convergence and the quality of clusters.

4. Gradient Descent and Stochastic Gradient Descent

• Core Concepts:

  • Gradient descent is an optimization algorithm used to minimize some function by iteratively moving in the direction of steepest descent.
  • Stochastic gradient descent (SGD) is a variant of gradient descent that uses a subset of the data to compute the gradient.

• Key Principles:

  • Gradient descent converges to a global minimum for convex functions.
  • SGD can be faster but may require more iterations to converge.

5. Principal Component Analysis (PCA)

• Core Concepts:

  • PCA is a dimensionality reduction technique that transforms data into a set of orthogonal axes.
  • The principal components are the directions of maximum variance.

• Key Equations:

  • Principal component: $w_k = \sum_{i=1}^{n} \alpha_i x_i$
  • Covariance matrix: $C = \frac{1}{n-1} \sum_{i=1}^{n} (x_i - \bar{x})(x_i - \bar{x})^T$
  • Variance along the first principal component: $\lambda_1$

6. Maximum Likelihood Estimation (MLE)

• Core Concepts:

  • MLE is a method of estimating the parameters of a statistical model.
  • For a Pareto distribution, the MLE of the shape parameter $\theta$ can be derived from the likelihood function.

• Key Equations:

  • Pareto distribution: $f(x \mid \theta) = \theta x^{-\theta-1}$
  • Likelihood function: $L(\theta) = \prod_{i=1}^{n} \theta x_i^{-\theta-1}$

7. Linear Regression

• Core Concepts:

  • Linear regression models the relationship between a dependent variable and one or more independent variables.
  • The model is fitted using the least squares method.

• Key Equations:

  • Linear regression model: $y = wx$
  • Mean squared error: $MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2$