Machine Learning Techniques 16 Jul 26 - 19 Jul 2026

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 summary of the core topics, concepts, principles, and equations essential for the exam, based on the provided questions.

Summary of Core Topics and Concepts

The questions cover fundamental aspects of Data Science, Machine Learning, Linear Algebra, and Optimization, crucial for understanding and implementing various algorithms.

1. Linear Algebra for Data Science

• Covariance Matrix: A square matrix giving the variance between each pair of random variables. It is symmetric and positive semi-definite.
• Eigenvalue Decomposition: Decomposing a matrix into a set of eigenvalues and eigenvectors. Eigenvalues represent magnitudes (e.g., variance in PCA), and eigenvectors represent directions.
• Matrix Rank: The number of linearly independent rows or columns in a matrix. For a covariance matrix, its rank indicates the effective dimensionality of the data.
• Vector Norms: Measures the "length" or "magnitude" of a vector. The Euclidean (L2) norm, denoted as $\|v\|$, is commonly used for distance calculations.

2. Principal Component Analysis (PCA)

• Dimensionality Reduction: A technique to reduce the number of features (dimensions) in a dataset while retaining most of the variance.
• Variance Maximization: PCA finds orthogonal directions (principal components) along which the data varies most.
• Eigenvalues in PCA: The eigenvalues of the covariance matrix represent the amount of variance captured by their corresponding principal components. Larger eigenvalues correspond to more important components.
• Eigenvectors in PCA: The eigenvectors of the covariance matrix are the principal components, representing the new orthogonal axes.
• Mean-centered Data: For PCA, it's common practice to center the data by subtracting the mean of each feature, making the mean of the dataset zero.

3. Optimization

• Minimizing Sum of Squared Errors: A common objective in many machine learning algorithms (e.g., linear regression, K-Means). Finding the minimum involves calculus.
• Gradient Descent (Concept): An iterative optimization algorithm for finding the local minimum of a function by moving in the direction of the steepest descent (negative of the gradient).
• Vector Calculus for Optimization: Using derivatives (gradients) with respect to vector variables to find critical points of multivariate functions.

4. K-Means Clustering

• Iterative Algorithm: An unsupervised learning algorithm that partitions $n$ data points into $K$ clusters.
• Objective Function (WCSS - Within-Cluster Sum of Squares): The sum of squared distances between each data point and its assigned cluster centroid. The goal of K-Means is to minimize this function.
• E-Step (Assignment): Each data point is assigned to the cluster whose centroid is closest (based on Euclidean distance).
• M-Step (Centroid Update): Each cluster's centroid is updated to be the mean of all data points currently assigned to that cluster.
• Convergence Properties: K-Means is guaranteed to converge to a local optimum of its objective function. The WCSS will never increase in an iteration.
• Revisiting Configurations: Due to the descent property (WCSS never increasing), K-Means cannot revisit a previous configuration (cluster assignments and centroids) once it has moved to a new one, as that would imply a non-decreasing WCSS after a change.
• Sensitivity to Initialization: The final clustering result can vary significantly depending on the initial choice of centroids.
• Choice of K: The number of clusters $K$ is a hyperparameter. A smaller $K$ generally leads to a higher WCSS.

5. Kernel Methods

• Kernel Functions: Functions that compute the inner product of data points in a high-dimensional feature space without explicitly transforming the data (kernel trick).
• Positive Semi-Definite (PSD) Kernels: A function $K(x,y)$ is a valid kernel if and only if its Gram matrix (a matrix of pairwise kernel evaluations) is positive semi-definite for any set of data points.
• Properties of Kernels (Closure Properties): Valid kernels retain their validity under certain operations (e.g., addition, multiplication, scaling by non-negative constants, normalization).

• Common Valid Kernels:

  • Linear Kernel: Measures linear similarity between data points.
  • Gaussian (RBF - Radial Basis Function) Kernel: Measures non-linear similarity, often used for its ability to map data to infinite-dimensional spaces.

6. Gaussian Mixture Models (GMM)

• Expectation-Maximization (EM) Algorithm: An iterative algorithm for finding maximum likelihood or maximum a posteriori estimates of parameters in statistical models, where the model depends on unobserved latent variables (like cluster assignments in GMM).
• GMM Components: A GMM represents the probability distribution of observations as a mixture of several Gaussian distributions.
• E-Step (Expectation Step): Computes the posterior probability (responsibility) that each data point belongs to each component, given the current parameter estimates.
• M-Step (Maximization Step): Updates the parameters (mixing weights, means, covariances) of each Gaussian component to maximize the likelihood, given the responsibilities computed in the E-step.
• Mixing Weights ($\pi_k$): The prior probability of a data point belonging to component $k$.
• Conditional Probability Density ($f(x|z=k)$): The probability density of observing data point $x$ given that it came from component $k$.
• Marginal Probability Density ($p(x)$): The overall probability density of observing data point $x$, marginalized over all components.
• Posterior Responsibility ($\gamma_k$): The posterior probability that data point $x$ belongs to component $k$, given $x$ and the current model parameters. This is the output of the E-step.

Essential Equations and Principles (in LaTeX)

1. Covariance Matrix (for mean-centered data $\bar{x} = \mathbf{0}$):

   $$S = \frac{1}{n} \sum_{i=1}^n x^{(i)} (x^{(i)})^T$$

2. Eigenvalue Decomposition: For a square matrix $S$, an eigenvector $v$ and eigenvalue $\lambda$ satisfy:

   $$S v = \lambda v$$

3. Variance Explained by a Principal Component: For a mean-centered dataset and a unit eigenvector $u$ (principal component), the variance of the projections of data points onto $u$ is its corresponding eigenvalue $\lambda$:

   $$\frac{1}{n} \sum_{i=1}^n (u^T x^{(i)})^2 = \lambda$$

   The sum of all eigenvalues equals the total variance (trace of the covariance matrix):

   $$\text{Trace}(S) = \sum_{j=1}^d \lambda_j = \sum_{j=1}^d \text{Var}(x_j)$$

   The number of non-zero eigenvalues equals the rank of the covariance matrix.

4. Minimization of Sum of Squared Errors: To minimize $J(v) = \sum_{i=1}^n \|C x_i - D v\|^2$ with respect to $v$, set the gradient to zero:

   $$\nabla_v J(v) = \sum_{i=1}^n -2D^T (C x_i - D v) = \mathbf{0}$$

   For the specific problem $v^* = \arg \min_{v \in \mathbb{R}^d} \sum_{i=1}^n \|3x_i - 2v\|^2$:

   $$v^* = \frac{3}{2n} \sum_{i=1}^n x_i$$

5. K-Means Algorithm:

   • Objective Function (WCSS):

     $$J(C, \mu) = \sum_{k=1}^K \sum_{x_i \in C_k} \|x_i - \mu_k\|^2$$

   • Assignment Step (E-step):

     $$Z_i = \arg \min_k \|x_i - \mu_k\|^2$$

   • Update Step (M-step):

     $$\mu_k^{\text{new}} = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i$$

6. Kernel Functions:

   • Linear Kernel: $K_1(x,y) = x^T y$
   • Gaussian (RBF) Kernel: $K_2(x,y) = \exp\left(-\frac{\|x-y\|^2}{2\sigma^2}\right)$

   • Properties of Valid Kernels ($K_a, K_b$):

     • Sum: $K_a(x,y) + K_b(x,y)$ is a valid kernel.
     • Product: $K_a(x,y) \cdot K_b(x,y)$ is a valid kernel.
     • Scaling ($c \ge 0$): $c K_a(x,y)$ is a valid kernel.
     • Normalization (if $K(x,x) > 0$): $\frac{K(x,y)}{\sqrt{K(x,x)K(y,y)}}$ is a valid kernel.

7. Gaussian Mixture Models (GMM) - E-Step:

   • Posterior Responsibility ($\gamma_k$):

     $$\gamma_k = \frac{\pi_k f(x | z=k)}{p(x)}$$

   • Marginal Probability Density ($p(x)$):

     $$p(x) = \sum_{j=1}^K \pi_j f(x | z=j)$$

   • Properties of Responsibilities:

     $$\sum_{j=1}^K \gamma_j = 1$$
     $$\sum_{j \neq k} \gamma_j = 1 - \gamma_k$$
     $$\frac{\pi_k f(x | z=k)}{\sum_{j \neq k} \pi_j f(x | z=j)} = \frac{\gamma_k}{1 - \gamma_k}$$