GATE DA & AI Engineering Machine Learning Syllabus

What assumption gives the Naive Bayes classifier its name?

It naively assumes all features are conditionally independent given the class label.

State the classification rule used by Naive Bayes.

$$\hat{y} = \arg\max_{c}\; P(c)\prod_{j=1}^{p}P(x_j\mid c)$$ choosing the class maximizing the posterior via Bayes' theorem.

Write Bayes' theorem as used in Naive Bayes.

$$P(c\mid \vec{x}) = \frac{P(\vec{x}\mid c)\,P(c)}{P(\vec{x})}$$

What is Laplace (additive) smoothing in Naive Bayes and why is it used?

It adds a constant $\alpha$ (often 1) to counts: $P(x_j\mid c)=\frac{N_{jc}+\alpha}{N_c + \alpha V}$, preventing zero probabilities for feature values unseen in training.

What is the goal of Linear Discriminant Analysis (LDA)?

To find a linear projection that maximizes between-class separation while minimizing within-class scatter, used for classification and dimensionality reduction.

What distributional assumptions does LDA make?

Each class is Gaussian-distributed and all classes share a common covariance matrix $\Sigma$, which yields linear decision boundaries.

What objective (Fisher's criterion) does LDA maximize for two classes?

$$J(\vec{w}) = \frac{\vec{w}^{T}S_B\vec{w}}{\vec{w}^{T}S_W\vec{w}}$$ the ratio of between-class scatter $S_B$ to within-class scatter $S_W$.

How does LDA differ from QDA (Quadratic Discriminant Analysis)?

LDA assumes a shared covariance matrix giving linear boundaries; QDA allows each class its own covariance, producing quadratic (curved) boundaries.

What does a Support Vector Machine (SVM) optimize for in classification?

It finds the hyperplane that maximizes the margin (distance) between the two classes' nearest points.

What are support vectors in an SVM?

The training points lying closest to the decision boundary (on or within the margin); they alone determine the position of the optimal hyperplane.

State the margin width maximized by a hard-margin SVM.

The margin is $\frac{2}{\lVert \vec{w}\rVert}$, so the SVM minimizes $\frac{1}{2}\lVert\vec{w}\rVert^{2}$ subject to $y_i(\vec{w}^{T}\vec{x}_i+b)\geq 1$.

What is the kernel trick in SVMs?

It replaces inner products $\vec{x}_i^{T}\vec{x}_j$ with a kernel $K(\vec{x}_i,\vec{x}_j)$, implicitly mapping data to a higher-dimensional space to enable nonlinear separation without explicit transformation.

Give the formula for the RBF (Gaussian) kernel.

$$K(\vec{x},\vec{x}') = \exp\!\left(-\gamma\lVert\vec{x}-\vec{x}'\rVert^{2}\right)$$

What is the role of the slack/penalty parameter $C$ in a soft-margin SVM?

$C$ controls the trade-off between maximizing the margin and minimizing classification errors; large $C$ penalizes misclassification heavily (low bias, high variance), small $C$ allows a wider, softer margin.

How does a decision tree make predictions?

It recursively splits the feature space along feature thresholds, routing an input from the root to a leaf, whose stored class (or value) is the prediction.

Define Gini impurity for a node.

$$Gini = 1 - \sum_{k=1}^{K}p_k^{2}$$ where $p_k$ is the proportion of class $k$ in the node; $0$ means pure.

Define entropy and information gain used in decision tree splitting.

Entropy: $H = -\sum_{k=1}^{K}p_k\log_2 p_k$. Information gain = entropy of parent minus weighted average entropy of children; the split maximizing gain is chosen.

How are decision trees prone to overfitting and how is it controlled?

Deep, fully grown trees overfit by memorizing noise; controlled via pruning, max depth, minimum samples per leaf, or minimum impurity decrease.

Define the bias-variance trade-off.

It is the tension between bias (error from overly simple assumptions, causing underfitting) and variance (error from sensitivity to training data, causing overfitting); reducing one tends to increase the other.

Write the bias-variance decomposition of expected squared error.

$$\mathbb{E}[(y-\hat{f}(\vec{x}))^{2}] = \text{Bias}^{2}[\hat{f}(\vec{x})] + \text{Var}[\hat{f}(\vec{x})] + \sigma^{2}$$ where $\sigma^{2}$ is irreducible noise.

In the bias-variance trade-off, what characterizes underfitting versus overfitting?

Underfitting: high bias, low variance, poor on both train and test. Overfitting: low bias, high variance, good on train but poor on test.

What is the purpose of cross-validation?

To estimate a model's generalization performance and tune hyperparameters by repeatedly training and validating on different data partitions, using data more efficiently than a single split.

Describe k-fold cross-validation.

Data is split into $k$ equal folds; the model trains on $k-1$ folds and validates on the remaining one, rotating so each fold is validation once; the $k$ scores are averaged.

What is Leave-One-Out Cross-Validation (LOOCV)?

A special case of $k$-fold where $k = n$: each single observation is held out as the validation set once. It is nearly unbiased but computationally expensive and high-variance.

What is stratified k-fold cross-validation and when is it used?

A variant that preserves the class proportions in each fold; used for classification, especially with imbalanced classes, to keep folds representative.

What is a Multi-Layer Perceptron (MLP)?

A feed-forward neural network with one or more hidden layers of nonlinearly-activated neurons fully connected between layers, capable of learning nonlinear mappings.

Why are nonlinear activation functions essential in an MLP?

Without them, stacked linear layers collapse into a single linear transformation; nonlinearities (e.g. ReLU, sigmoid, tanh) let the network approximate complex nonlinear functions (universal approximation).

What does 'feed-forward' mean in a feed-forward neural network?

Information flows in one direction, from input through hidden layers to output, with no cycles or feedback connections (a directed acyclic graph).

What algorithm trains MLPs and what does it compute?

Backpropagation with gradient descent; it applies the chain rule to compute the gradient of the loss with respect to every weight, which is used to update the weights.

What is the goal of clustering algorithms?

Unsupervised grouping of data points so that points in the same cluster are more similar to each other than to points in other clusters, without using labels.

Describe the K-Means algorithm's iterative steps.

1) Initialize $k$ centroids; 2) assign each point to its nearest centroid; 3) recompute each centroid as the mean of assigned points; repeat steps 2-3 until assignments stabilize.

What objective does K-Means minimize?

The within-cluster sum of squares (inertia): $$J = \sum_{i=1}^{k}\sum_{\vec{x}\in C_i}\lVert\vec{x}-\vec{\mu}_i\rVert^{2}$$

How does K-Medoids differ from K-Means?

K-Medoids uses actual data points (medoids) as cluster centers and minimizes sum of pairwise dissimilarities, making it more robust to outliers and usable with arbitrary distance metrics; K-Means uses mean centroids and Euclidean distance.

What is the 'elbow method' for choosing $k$ in K-Means?

Plot within-cluster sum of squares versus $k$; the 'elbow' point, where adding more clusters yields diminishing reduction in WCSS, indicates a good $k$.

What are the two main approaches to hierarchical clustering?

Agglomerative (bottom-up): start with each point as its own cluster and merge. Divisive (top-down): start with one cluster containing all points and split.

What is a dendrogram in hierarchical clustering?

A tree diagram showing the sequence of merges/splits and the distances at which they occur; cutting it at a chosen height yields a given number of clusters.

Name three linkage criteria used in agglomerative hierarchical clustering.

Single linkage (minimum pairwise distance), complete linkage (maximum pairwise distance), and average linkage (mean pairwise distance); Ward's method (minimizes variance increase) is also common.

What is a key advantage of hierarchical clustering over K-Means?

It does not require pre-specifying the number of clusters and produces a full hierarchy (dendrogram), though it is computationally more expensive (typically $O(n^{2}\log n)$ or $O(n^{3})$).

Compare generative versus discriminative classifiers with examples.

Generative models the joint $P(\vec{x},y)$ / class-conditional densities (e.g. Naive Bayes, LDA); discriminative models the boundary or $P(y\mid\vec{x})$ directly (e.g. logistic regression, SVM).

Why does feature scaling matter for KNN, SVM, and K-Means but not for decision trees?

KNN, SVM, and K-Means rely on distance/inner-product magnitudes, so unscaled features dominate; decision trees split on thresholds per feature and are invariant to monotonic feature scaling.

What is one major limitation of K-Means clustering?

It requires choosing $k$ in advance, assumes spherical equally-sized clusters, is sensitive to initialization and outliers, and may converge to a local optimum (mitigated by k-means++ initialization).