IIT M QUIZ 1 FOUNDATION DAD DIPLOMA QPD1 16 Oct 2022 - 16 Oct 2022

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. Kernel Methods and Kernel PCA

• Kernel Functions: Functions that compute the inner product of two vectors in a high-dimensional space without explicitly transforming the vectors.

  • Example: Polynomial kernel $k(x, y) = (x^T y)^2 + 1$

• Transformation Mapping ($\phi$): Maps data to a higher-dimensional space.

  • Example: $\phi([x_1, x_2]^T) = [x_1^2, \sqrt{2} x_1, x_2, x_2^2, 1]^T$
• Valid Kerners: A kernel must satisfy Mercer's condition to be valid.

2. Principal Component Analysis (PCA)

• Principal Components: Directions in which the data varies the most.

  • Example: First principal component $\begin{bmatrix} \frac{\sqrt{3}}{3} \\ -\frac{2}{3} \end{bmatrix}^T$

• Variance and Compression Ratio:

  • Variance along principal components: $\theta = \frac{\text{variance along the first principal component}}{\text{sum of variances along all principal components}}$
  • Compression ratio: $\frac{\text{size of original dataset}}{\text{size of reconstructed dataset}}$

3. Clustering Algorithms

• K-Means and Lloyd’s Algorithm:

  • Initialization: Choose initial cluster centers.
  • Assignment: Assign each data point to the nearest cluster center.
  • Update: Recompute the cluster centers as the mean of the assigned points.

• K-Means++: Probabilistic method for choosing initial cluster centers to improve convergence.

  • Probability of choosing a point: Proportional to the squared distance from the closest already chosen center.

4. Gaussian Mixture Models (GMM) and EM Algorithm

• EM Algorithm: Iterative method for finding maximum likelihood estimates of parameters in probabilistic models.

  • E-step: Compute the posterior probabilities ($\lambda_k^i$) of each data point belonging to each mixture component.
  • M-step: Update the parameters ($\pi_k$, $\mu_k$, $\Sigma_k$) of the mixture components.

• GMM Parameters:

  • $\pi_k$: Mixing coefficients.
  • $\lambda_k^i$: Posterior probabilities.

5. Probability and Statistics

• Bernoulli Distribution: Models binary outcomes.

  • Example: $P(x = 1) = p$

• Beta Distribution: Conjugate prior for the parameter $p$ of a Bernoulli distribution.

  • Example: Prior $\text{Beta}(18, 8)$, Posterior $\text{Beta}(30, 40)$

• Log-Likelihood: Logarithm of the likelihood function.

  • Example: $\log L(\theta) = 5 \log \theta + (\theta - 1) \sum_{i=1}^{5} \log x_i$

6. Data Centering and Variance

• Centered Dataset: Dataset where the mean of each feature is zero.
• Variance along Principal Components: Measure of the spread of data along each principal component.