Machine Learning Algorithms
Supervised learning trains a model on labeled examples to predict outputs for unseen inputs. GATE DA tests both the mathematical foundations and the algori...
Supervised Learning: Regression and Classification Algorithms
Supervised learning trains a model on labeled examples to predict outputs for unseen inputs. GATE DA tests both the mathematical foundations and the algorithmic mechanics of major supervised learning methods. Conceptual clarity about what each algorithm optimizes is more important than implementation details.
Linear regression minimizes the sum of squared residuals between predictions and true values. The closed-form solution is w = (X^T X)^(-1) X^T y, where X is the design matrix with a column of ones prepended for the bias term. Ridge regression adds a penalty lambda * ||w||^2 to the loss, shrinking coefficients toward zero. Lasso adds lambda * ||w||_1, which produces sparse solutions by forcing some coefficients exactly to zero. The trade-off between bias and variance is controlled by the regularization hyperparameter lambda.
Logistic regression models the probability of a binary class using the sigmoid function sigma(z) = 1 / (1 + e^(-z)), where z = w^T x. The model is trained by maximizing the log-likelihood, which is equivalent to minimizing the binary cross-entropy loss. Unlike linear regression, no closed-form solution exists, so gradient descent or Newton's method is used. Decision boundary is the hyperplane where w^T x = 0.
Decision trees partition the feature space by recursively splitting on features that maximize information gain (for classification) or minimize mean squared error (for regression). The information gain of a feature equals the entropy of the parent minus the weighted average entropy of the children. Gini impurity is an alternative split criterion. Decision trees overfit easily; pruning, maximum depth, and minimum samples per leaf are regularization techniques.
Random forests build an ensemble of decision trees, each trained on a bootstrap sample of the data with a random subset of features at each split. The final prediction is the majority vote (classification) or average (regression) of all trees. Bagging reduces variance. Feature randomness decorrelates the trees, reducing variance further without increasing bias. Random forests are robust to outliers and require little hyperparameter tuning.
Unsupervised Learning, SVMs, and Ensemble Methods
Unsupervised learning discovers structure in unlabeled data. K-means clustering partitions data into k clusters by iteratively assigning each point to the nearest centroid and recomputing centroids as cluster means. The algorithm minimizes within-cluster sum of squared distances (inertia). K-means is sensitive to initialization; k-means++ improves initialization by choosing initial centroids with probability proportional to their distance from already chosen centroids.
Hierarchical clustering builds a tree of clusters called a dendrogram. Agglomerative clustering starts with each point as its own cluster and merges the two closest clusters at each step. The distance between clusters is measured by linkage criteria: single linkage uses minimum pairwise distance, complete linkage uses maximum, and average linkage uses the mean. GATE questions often ask you to trace a small hierarchical clustering example manually.
Principal component analysis (PCA) reduces dimensionality by projecting data onto the directions of maximum variance. These directions are the eigenvectors of the covariance matrix, ordered by decreasing eigenvalue. The proportion of variance explained by the first k components is the sum of the top k eigenvalues divided by the total sum of all eigenvalues. PCA is a linear method and is sensitive to feature scaling; always standardize features before applying PCA.
Support vector machines find the maximum-margin hyperplane separating two classes. The margin is the distance between the hyperplane and the nearest points of each class, called support vectors. The primal optimization problem is to minimize (1/2)||w||^2 subject to y_i(w^T x_i + b) >= 1. The kernel trick replaces dot products with kernel functions, allowing SVMs to learn non-linear boundaries without explicitly computing high-dimensional features. Common kernels: linear, polynomial, RBF (radial basis function).
Gradient boosting builds an ensemble sequentially, with each new tree fitted to the residuals of the previous ensemble. XGBoost and LightGBM are popular implementations that add regularization and use histogram-based splitting for speed. The key hyperparameters are the number of trees, learning rate (shrinkage), maximum depth, and subsampling ratio. Gradient boosting typically outperforms random forests on structured tabular data.
Model Evaluation, Bias-Variance Trade-off, and Neural Networks Basics
Model evaluation measures how well a trained model generalizes to unseen data. The most fundamental evaluation principle is to never evaluate on training data; always use a held-out test set or cross-validation. K-fold cross-validation divides data into k equal folds, trains on k-1 folds, validates on the remaining fold, and averages results across all k runs. Stratified k-fold preserves class proportions in each fold.
Classification metrics: accuracy = (TP + TN) / (TP + TN + FP + FN); precision = TP / (TP + FP); recall = TP / (TP + FN); F1 score = 2 * precision * recall / (precision + recall). The ROC curve plots true positive rate versus false positive rate at varying thresholds. The AUC (area under the ROC curve) summarizes classifier performance across all thresholds. For imbalanced classes, F1 score and AUC are more informative than accuracy.
The bias-variance trade-off is the fundamental tension in machine learning. Bias measures how far off a model's average prediction is from the true value; it results from model assumptions being too simple. Variance measures how much predictions vary across different training sets; it results from the model being too sensitive to training data. Total expected prediction error = bias^2 + variance + irreducible noise. Simple models (linear regression) have high bias and low variance. Complex models (deep decision trees) have low bias and high variance.
A feedforward neural network consists of an input layer, one or more hidden layers, and an output layer. Each neuron computes a weighted sum of its inputs plus a bias and applies a nonlinear activation function. Common activations: sigmoid compresses output to (0,1); tanh compresses to (-1,1); ReLU(x) = max(0,x) is the most widely used hidden-layer activation because it avoids the vanishing gradient problem. Softmax converts a vector of raw scores to a probability distribution over classes.
Backpropagation computes the gradient of the loss with respect to each weight using the chain rule, layer by layer from output to input. Stochastic gradient descent updates weights using the gradient computed on a single training example or a mini-batch. GATE DA questions on neural networks typically ask about activation function properties, backpropagation steps on small networks, or the role of regularization techniques like dropout and weight decay.