IIT M FOUNDATION AN EXAM QDF3 31 Aug - 31 Aug 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 structured summary of the core topics, concepts, principles, and equations essential for the Diploma Level: Machine Learning Foundations (Computer-Based Exam) based on the provided question paper. The exam covers probability, linear algebra, optimization, convexity, and statistics, with a focus on foundational mathematics for machine learning.

1. Core Topics & Key Concepts

A. Probability & Random Variables

1. Probability Inequalities

   • Markov’s Inequality: For a non-negative random variable $X$ and $a > 0$:

• Used for bounding tail probabilities (e.g., $\mathbb{P}(X \geq 2pn) \leq \frac{1}{2}$ for $X \sim \text{Binomial}(n, p)$).

  • Chebyshev’s Inequality:

  For any random variable $X$ with mean $\mu$, variance $\sigma^2$, and $k > 0$:

• Bounds deviation from the mean (e.g., $\mathbb{P}(X \geq 2pn) \leq \frac{1-p}{np}$).

1. Binomial Distribution

   • $X \sim \text{Binomial}(n, p)$:

     • Mean: $\mathbb{E}[X] = np$
     • Variance: $\text{Var}(X) = np(1-p)$

1. Normal Distribution & Linear Combinations

   • If $X \sim \text{Normal}(\mu_X, \sigma_X^2)$ and $Y \sim \text{Normal}(\mu_Y, \sigma_Y^2)$ are independent, then:

• Standardization: $Z = \frac{X - \mu}{\sigma} \sim \text{Normal}(0, 1)$.

1. Conditional Probability

   • Definition:

• Example: Permutations with constraints (e.g., seating arrangements).

1. Joint Probability Density Functions (PDFs)

   • For continuous random variables $X$ and $Y$, the joint PDF $f(x, y)$ satisfies:

• Marginal PDF: $f_Y(y) = \int_{-\infty}^{\infty} f(x, y) \, dx$
• Variance: $\text{Var}(Y) = \mathbb{E}[Y^2] - (\mathbb{E}[Y])^2$

B. Linear Algebra

1. Vector Spaces & Span

   • Span of a vector $v_1$: $S = \text{span}(v_1) = \{ \alpha v_1 \mid \alpha \in \mathbb{R} \}$
   • Projection of $v_2$ onto $S$:

• Orthogonality: $v_1 \cdot v_2 = 0$

1. Eigenvalues & Eigenvectors

   • For a matrix $A$, eigenvalues $\lambda$ satisfy $\det(A - \lambda I) = 0$.

   • Properties:

     • Trace $= \sum \lambda_i$
     • Determinant $= \prod \lambda_i$
   • Diagonalizable Matrices: $A = PDP^{-1}$, where $D$ is diagonal.
   • Hermitian Matrices: $A = A^H$ (equal to its conjugate transpose).
   • Unitary Matrices: $A^H A = I$.

1. Matrix Operations

   • Example: For $A$ with eigenvalues $\lambda_i$, the eigenvalues of $2A^2 - 3I$ are $2\lambda_i^2 - 3$.

C. Optimization & Convexity

1. Convex Functions

   • Definition: A function $f$ is convex if for all $x, y$ and $\theta \in [0, 1]$:

• Examples:

  • $f_1(x, y) = x^4 + x^2 - 2xy + y^2$ (convex, as its Hessian is positive semidefinite).
  • $f_3(x) = (x^2 - 3x + 2)(x^2 - 7x + 12)$ is convex on $(2, 3)$.
• Non-Convex Example: $f_2(x, y) = x^\alpha y^\beta$ with $\alpha + \beta \leq 1$ is not convex in general.

1. Convex Sets

   • Definition: A set $S$ is convex if for all $x, y \in S$ and $\theta \in [0, 1]$:

• Example: The set $S = \{ (x, y) \mid -x - 3y \leq -9, -2x - y \leq -6, x, y \geq 0 \}$ is convex.

1. Optimization Problems

   • Primal Problem: Minimize a convex objective subject to convex constraints. Example:

• Lagrangian Function:

• Stationary Conditions (KKT Conditions):

D. Calculus & Quadratic Forms

1. Hessian Matrix

   • For a function $f(x, y)$, the Hessian $H$ is:

• Convexity Test: $f$ is convex if $H$ is positive semidefinite.

1. Quadratic Optimization

   • Example: Minimizing $C = 5x^2 + 2xy + 3y^2 + 500$ subject to $x + y = 39$.
   • Solution: Use substitution and calculus to find critical points.

2. Key Equations Summary

Graph 2: Linear Algebra

Graph 3: Optimization & Convexity

Graph 4: Relationships Between Topics

4. Exam Preparation Tips

1. Probability Inequalities:

   • Practice applying Markov’s and Chebyshev’s inequalities to binomial and normal distributions.
   • Remember: Markov’s gives a looser bound, while Chebyshev’s is tighter but requires variance.

1. Linear Algebra:

   • Master projections, orthogonality, and span.
   • For matrices, focus on eigenvalues, diagonalization, and special types (Hermitian, unitary).

1. Optimization:

   • Recognize convex functions (e.g., quadratic forms, $x^4$).
   • For constrained optimization, write the Lagrangian and KKT conditions.

1. Calculus:

   • Compute Hessians to test convexity.
   • Solve quadratic optimization problems using substitution.

1. Statistics:

   • Compute marginal and conditional probabilities for discrete/continuous cases.
   • Calculate variance from joint PDFs.

1. Common Pitfalls:

   • Misapplying Chebyshev’s inequality (e.g., forgetting to center the variable).
   • Confusing convex/concave functions (e.g., $f_2(x, y) = x^\alpha y^\beta$ is not convex for $\alpha + \beta \leq 1$).
   • Incorrectly setting up the Lagrangian (e.g., forgetting non-negativity constraints on multipliers).