IIT M FOUNDATION AN2 EXAM QPF2 16 JULY 2023 - 16 Jul 2023

Concepts this paper tests

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

The examination covers fundamental concepts in Machine Learning, Linear Algebra, Multivariable Calculus, and Optimization. A strong understanding of these mathematical and algorithmic foundations is crucial.

Summary of Core Topics, Concepts, Principles, and Equations

1. Machine Learning Fundamentals

• Loss Functions: Quantify the error between predicted and actual values.

  • Mean Squared Error (MSE): Primarily used for regression problems, penalizes larger errors more heavily.

    $$MSE = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{y}_i)^2$$

  • Max Absolute Error ($L_\infty$ Loss): Determines the largest absolute difference between any single prediction and its true value.

    $$L = \max_i |y_i - \hat{y}_i|$$
• Classification vs. Regression: Distinguish between problems predicting discrete categories (classification) and continuous values (regression). MSE is not suitable for classification.

• Autoencoders and Dimensionality Reduction:

  • Encoder: Maps input data to a lower-dimensional representation.
  • Decoder: Maps the lower-dimensional representation back to the original data space.

  • Reconstruction Error: Measures how well the decoder can reconstruct the original input from the encoded representation. Often uses squared Euclidean norm.

    $$R(f, g) = \frac{1}{n} \sum_{i=1}^n \|x_i - g(f(x_i))\|^2$$

    where $f$ is the encoder, $g$ is the decoder, and $\| \cdot \|$ is the Euclidean norm.

• Gaussian Mixture Models (GMM): A probabilistic model used for representing sub-populations within an overall population, often for modeling multimodal data.

• Indicator Function: A function that returns 1 if a given condition is true, and 0 otherwise.

  $$I(condition) = \begin{cases} 1 & \text{if condition is true} \\ 0 & \text{if condition is false} \end{cases}$$

2. Linear Algebra

• Vector Spaces and Subspaces:

  • Row Space, Column Space, Null Space (Kernel): Understand their definitions and properties.
  • Orthogonality: The row space of a matrix is orthogonal to its null space. The column space of a matrix is orthogonal to the null space of its transpose.

  • Rank-Nullity Theorem: For a matrix $A \in \mathbb{R}^{m \times n}$, the dimension of its column space (rank) plus the dimension of its null space (nullity) equals the number of columns $n$.

    $$\text{rank}(A) + \text{nullity}(A) = n$$
  • Rank: The dimension of the column space (or row space) of a matrix. The column rank is always equal to the row rank.

• Eigenvalues and Eigenvectors:

  • Definition: For a matrix $A$, a non-zero vector $v$ is an eigenvector if $Av = \lambda v$ for some scalar $\lambda$, called the eigenvalue.
  • Symmetric Matrices: Have real eigenvalues and an orthogonal basis of eigenvectors. They are always diagonalizable.
  • Diagonalization: A square matrix $A$ is diagonalizable if and only if there exists a basis of eigenvectors for the entire space $\mathbb{R}^d$. This means the algebraic multiplicity of each eigenvalue equals its geometric multiplicity.

• Matrix Operations and Properties:

  • Matrix multiplication, transpose.
  • Determinant: A scalar value that can be computed from the elements of a square matrix.

  • Projection Matrices: Project vectors onto a subspace.

    • Projection matrix onto the line spanned by vector $a$:

      $$P_a = \frac{a a^T}{a^T a}$$

    • Projection matrix onto the orthogonal complement of the span of $a$:

      $$P_{a^\perp} = I - P_a$$

• Systems of Linear Equations ($Ax=b$):

  • Consistency: A system is consistent if a solution $x$ exists (i.e., $b$ lies in the column space of $A$). This can be checked by comparing the rank of $A$ with the rank of the augmented matrix $[A|b]$.

  • Least Squares Approximation: If $Ax=b$ is inconsistent, the least squares method finds $\hat{x}$ that minimizes $\|Ax-b\|^2$. The solution $\hat{x}$ is found by solving the normal equations:

    $$A^T A \hat{x} = A^T b$$
  • Projection Vector: The vector $p = A\hat{x}$ is the projection of $b$ onto the column space of $A$.

• Euclidean Norm (Vector Length):

  $$\|v\| = \sqrt{\sum_{i=1}^d v_i^2}$$

3. Multivariable Calculus

• Partial Derivatives: Derivatives of a multivariable function with respect to one variable, holding others constant.

• Gradient Vector ($\nabla f$): A vector containing all the partial derivatives of a multivariable function. Points in the direction of the greatest rate of increase of the function.

  $$\nabla f = \begin{bmatrix} \frac{\partial f}{\partial x_1} \\ \vdots \\ \frac{\partial f}{\partial x_d} \end{bmatrix}$$

• Directional Derivative ($D_u f$): The rate of change of a function in a specific direction defined by a unit vector $u$.

  $$D_u f = \nabla f \cdot u$$

• Linear Approximation (First-Order Taylor Series): Approximating a function near a point $(x_0, y_0)$ with a linear function.

  $$L(x, y) = f(x_0, y_0) + \frac{\partial f}{\partial x}(x_0, y_0)(x - x_0) + \frac{\partial f}{\partial y}(x_0, y_0)(y - y_0)$$

• Continuity of Functions: For a function to be continuous at a point $c$, the limit of the function as $x$ approaches $c$ from both sides must exist and be equal to the function's value at $c$.

  $$\lim_{x \to c^-} f(x) = \lim_{x \to c^+} f(x) = f(c)$$

4. Optimization

• Gradient Descent: An iterative optimization algorithm used to find the local minimum of a function. It moves in the direction opposite to the gradient.

  $$X_{n+1} = X_n - h \nabla f(X_n)$$

  where $h$ is the learning rate (step size).

• Convergence: Understanding how the choice of step size and function properties (e.g., convexity) affect the convergence of optimization algorithms. Convex functions guarantee convergence to a global minimum under appropriate conditions.