Home / Past papers / MLT End Term / this paper

2023 Dec24: IIT M FN EXAM FDD1 - 24 Dec 2023

MLT End Term18 questions100 marks8 MSQ · 6 SA · 4 MCQforenoon

Elapsed 00:00

Q1MSQ5 marksselect all that apply

Comprehension passage - the questions below it refer to this

Based on the above data, answer the given subquestions. question figure

Q2MCQ5 marks

Suppose the team applies linear PCA on the dataset and reconstructs the data points with zero error using k principal components (directions). For which value of k the reconstruction error would become zero?

Q3MSQ6 marksselect all that apply

Q4SA5 marks

(Enter your answer correctly to two decimal places) question figure

Your numeric answer:

Q5SA6 marks

Your numeric answer:

Q6MSQ6 marksselect all that apply

Q7MCQ6 marks

[2, 6, 9, 12]
[2, 4, 7, 10]
[3, 5, 8, 11]
[1, 3, 6, 8]

Q8SA6 marks

Your numeric answer:

Q9MCQ5 marks

0
1
Insufficient information to make a prediction.

Q10MCQ5 marks

Yes, it will converge.
No, it will never converge.
Insufficient data

Q11SA6 marks

Your numeric answer:

Comprehension passage - the questions below it refer to this

Based on the above data, answer the given subquestions. question figure

Q12MSQ6 marksselect all that apply

What is the equation of the decision boundary? Select all options that are correct.

Q13SA5 marks

Your numeric answer:

Q14MSQ6 marksselect all that apply

Q15MSQ6 marksselect all that apply

Which of the following statements are correct?

Overfitting models have high bias and low variance.
Underfitting models have low bias and high variance.
Generally, weak learners in the random forest tend to overfit.
If the performance of each estimator in the bagging algorithm is almostidentical, the benefit of using bagging to combine them may be minimal or insignificant.
In random forests, multiple decision trees (estimators) are trainedsimultaneously, allowing for parallel processing and faster model training.

Q16MSQ5 marksselect all that apply

Model 4 tends to overfit.
Model 4 tends to underfit.
Model 1 tends to underfit.
Model 1 tends to overfit.

Q17MSQ5 marksselect all that apply

Q18SA6 marks

Your numeric answer:

Answer key

Q1 (MSQ, 5 marks): A, D
Q2 (MCQ, 5 marks): C
Q3 (MSQ, 6 marks): A, B
Q4 (SA, 5 marks): 43.10 to 43.20
Q5 (SA, 6 marks): 0.32 to 0.38
Q6 (MSQ, 6 marks): A, D, E
Q7 (MCQ, 6 marks): D
Q8 (SA, 6 marks): 12
Q9 (MCQ, 5 marks): C
Q10 (MCQ, 5 marks): B
Q11 (SA, 6 marks): 1
Q12 (MSQ, 6 marks): A, C
Q13 (SA, 5 marks): 5.32 to 5.44
Q14 (MSQ, 6 marks): A, D
Q15 (MSQ, 6 marks): C, D, E
Q16 (MSQ, 5 marks): B, D
Q17 (MSQ, 5 marks): A, C, D
Q18 (SA, 6 marks): 4081

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 core topics, concepts, principles, and equations essential for the exam, followed by Mermaid knowledge graphs to visualize relationships.

Core Topics & Key Concepts

1. Dimensionality Reduction

Principal Component Analysis (PCA)

Linear PCA:
- Projects data onto orthogonal axes (principal components) that maximize variance.
- Reconstruction Error: Zero if k = rank(data). For the given dataset (Q3), k = 3 achieves zero error.
- Covariance Matrix: Eigenvectors = principal directions; eigenvalues = variance along directions.
- Equation:

C = \frac{1}{n} X^T X \quad \text{(Covariance matrix)}

X_{\text{projected}} = U_k^T X \quad \text{(Projection onto top-$k$ PCs)}

where $U_k$ = matrix of top- $k$ eigenvectors.

Kernel PCA:
- Non-linear extension using kernel trick (e.g., RBF, polynomial).
- Key Points (Q4):
  - Principal directions differ from linear PCA unless the kernel is linear.
  - Computationally more expensive than linear PCA (due to kernel matrix $K$ ).
  - Eigenvectors of $K$ are not the same as eigenvectors of covariance matrix $C$ .

Key Equations:

K_{ij} = \phi(x_i)^T \phi(x_j) \quad \text{(Kernel matrix)}

\text{Centered } K = K - 1_n K - K 1_n + 1_n K 1_n \quad \text{(Centering in feature space)}

2. Clustering

Lloyd’s Algorithm (K-Means)

Steps:
1. Initialize centroids (e.g., $c_1 = 5, c_2 = 15, c_3 = 25$ in Q5).
2. Assign points to nearest centroid.
3. Recompute centroids as mean of assigned points.
4. Repeat until convergence.
Convergence: Guaranteed (finite iterations), but may reach local optima.
Final Centers Sum (Q5): After convergence, sum of centroids ≈ 43.15 (exact depends on ties).

Gaussian Mixture Models (GMM) & EM Algorithm

E-Step (Q6):
- Compute responsibilities ( $\lambda_k^i$ ) for each data point $x_i$ and cluster $k$ :

\lambda_k^i = \frac{\pi_k f(x_i | \mu_k, \sigma_k^2)}{\sum_{j=1}^K \pi_j f(x_i | \mu_j, \sigma_j^2)}

For $i=1, k=2$ , $\lambda_2^1 \approx 0.35$ (given densities and priors).
- M-Step: Update $\pi_k, \mu_k, \sigma_k^2$ using responsibilities.

3. Linear Regression & Regularization

Ordinary Least Squares (OLS)

Objective (Q7):

L(w) = \sum_{i=1}^n (w^T x_i - y_i)^2

Perfect Fit: If $L(w^*) = 0$ , the model interpolates all training points (implies $X$ is full-rank or $y$ is in the column space of $X$ ).

Ridge Regression (L2 Regularization)

Objective:

L(w) = \|Xw - y\|^2 + \lambda \|w\|^2

Solution (Q8):

w_\lambda = (X^T X + \lambda I)^{-1} X^T y

Effect of $\lambda$ :
- Higher $\lambda$ → smaller weights (shrinks coefficients toward zero).
- Example: If $w_{\lambda=4} = [2,5,7,9]$ , increasing $\lambda$ to 8 likely reduces weights (e.g., option D: $[1,3,6,8]$ ).

4. Classification Algorithms

Decision Trees

Splitting Rule (Q9):
- For binary classification, find threshold $p$ in $x < p$ that perfectly separates classes.
- Possible Integer Values for $p$ :
  - Sort unique values of $X$ , count midpoints between consecutive values where class labels change.
  - For the given dataset, 12 possible integer thresholds.

Naive Bayes

Prediction Rule (Q10):

\hat{y} = \arg\max_y P(y) \prod_{j=1}^d P(x_j | y)

Insufficient Information: If priors $P(y=0)$ and $P(y=1)$ are unknown, cannot compute $P(y|x)$ .

Perceptron Algorithm

Convergence (Q11):
- Converges only if data is linearly separable.
- Given dataset is not separable (e.g., point $(-1,0)$ and $(0,1)$ have same label but lie on opposite sides of possible hyperplanes).

Logistic Regression

Probability Output (Q12):

P(y=1|x) = \sigma(w^T x) = \frac{1}{1 + e^{-w^T x}}

Decision Rule: Predict $\hat{y} = 1$ if $P(y=1|x) > 0.6$ .
- For $x = [1, 0]$ and $w = [1/2, 2/3]$ :

w^T x = 0.5 \implies P(y=1|x) = \sigma(0.5) \approx 0.62 > 0.6 \implies \hat{y} = 1

Support Vector Machines (SVM)

Hard-Margin SVM (Q13, Q14):
- Decision Boundary: $w^T x + b = 0$ .
- Supporting Hyperplanes: $w^T x + b = \pm 1$ .
- Width of Margin:

\text{Width} = \frac{2}{\|w\|}

For Q14, width ≈ 5.38 (given options).
- Equations of Boundaries (Q13):
Scaled versions of $w^T x + b = 0$ (e.g., $\frac{5}{2}x_1 + 3x_2 = 0$ ).

Soft-Margin SVM (Q15):
- Optimization:

\min_{w,b} \frac{1}{2} \|w\|^2 + C \sum_i \xi_i \quad \text{s.t.} \quad y_i(w^T x_i + b) \geq 1 - \xi_i, \xi_i \geq 0

Key Points:
- $C = 0$ : Ignores margin violations (objective = 0 if data is separable).
- Constraints: $2n$ total (one for each $\xi_i \geq 0$ and one for the margin condition per point).

5. Model Evaluation & Ensemble Methods

Bias-Variance Tradeoff (Q16, Q17)

Overfitting:
- High variance, low bias (e.g., Model 1: training error = 0.2, test error = 1.8).
Underfitting:
- High bias, low variance (e.g., Model 4: training error = 5.9, test error = 6.3).
Bagging (Random Forest):
- Reduces variance by averaging multiple high-variance models (e.g., decision trees).
- Parallel Training: Trees are independent (can train simultaneously).

Loss Functions for Classification (Q18)

Suitable for Gradient Descent:
- Square Loss (OLS): $L(w) = \sum_i (w^T x_i - y_i)^2$ (though not ideal for classification).
- Hinge Loss (SVM): $L(w) = \sum_i \max(0, 1 - y_i w^T x_i)$ .
- Modified Hinge: $L(w) = \sum_i \max(0, y_i w^T x_i)$ (margin maximization).
- Not Suitable: Sign function (non-differentiable).

2023 Dec24: IIT M FN EXAM FDD1 - 24 Dec 2023

Answer key

Concepts this paper tests

Core Topics & Key Concepts

1. Dimensionality Reduction

Principal Component Analysis (PCA)

Key Equations:

2. Clustering

Lloyd’s Algorithm (K-Means)

Gaussian Mixture Models (GMM) & EM Algorithm

3. Linear Regression & Regularization

Ordinary Least Squares (OLS)

Ridge Regression (L2 Regularization)

4. Classification Algorithms

Decision Trees

Naive Bayes

Perceptron Algorithm

Logistic Regression

Support Vector Machines (SVM)

5. Model Evaluation & Ensemble Methods

Bias-Variance Tradeoff (Q16, Q17)

Loss Functions for Classification (Q18)

Graph 2: Clustering & GMM

Graph 3: Linear Models & Regularization

Graph 4: Classification Algorithms

Graph 5: Model Evaluation & Ensembles