GATE DA cheat sheet

Supervised learning minimizes empirical risk: given n samples (x_i, y_i), fit f to minimize (1/n)·Σ L(y_i, f(x_i)) + λ·R(f); λ controls the bias–variance trade-off, with larger λ increasing bias and reducing variance.

Bias–variance decomposition for squared loss: E[(y − f̂(x))²] = σ²_noise + Bias(f̂(x))² + Var(f̂(x)); total error cannot drop below the irreducible noise term.

Precision = TP/(TP+FP), Recall = TP/(TP+FN), F1 = 2·P·R/(P+R); accuracy = (TP+TN)/(TP+TN+FP+FN) and is misleading under class imbalance - use F1, balanced accuracy, or AUC-PR instead.

Confusion-matrix identities: TP+FN = actual positives, TN+FP = actual negatives; ROC plots TPR vs FPR, and AUC equals the probability a random positive is scored above a random negative.

k-fold cross-validation trains k models on (k−1)/k of the data; leave-one-out is the k = n case; stratified folds preserve class proportions and reduce variance of the estimate for skewed labels.

Regularized linear models: Ridge (L2) adds λ‖w‖² and shrinks coefficients smoothly; Lasso (L1) adds λ‖w‖₁ and drives coefficients exactly to zero, performing feature selection; Elastic Net mixes both penalties.

Gradient descent update: θ ← θ − η·∇L(θ); learning rate η too large diverges, too small converges slowly; stochastic and mini-batch variants trade gradient variance for speed on large datasets.

Decision trees split on impurity reduction: Gini = 1 − Σ p_i² and entropy = −Σ p_i·log₂ p_i; information gain = parent impurity − weighted child impurity, and deeper trees lower training error but raise variance.

k-Nearest Neighbors predicts by majority vote or mean of the k closest points; small k gives low bias and high variance, large k the reverse; distance scaling matters because Euclidean distance is scale-sensitive.

Naive Bayes applies Bayes' rule with a conditional-independence assumption: P(y|x) ∝ P(y)·Π P(x_i|y); Laplace smoothing adds α to counts to avoid zero probabilities.

SVM maximizes the margin 2/‖w‖ subject to y_i(wᵀx_i + b) ≥ 1; the soft-margin parameter C trades margin width against training violations, and the kernel trick replaces dot products with K(x, x').

Model evaluation rules of thumb: use holdout or cross-validation for model selection, never tune on the test set; report variance across folds, and prefer nested CV when both tuning and estimating generalization error.

Regression metrics: MSE penalizes large errors quadratically, MAE is robust to outliers, R² = 1 − SS_res/SS_tot is scale-free but can be negative for models worse than the mean.

Clustering: k-means minimizes within-cluster sum of squares and requires k in advance; DBSCAN finds arbitrary shapes and labels noise but is sensitive to ε and minPts; hierarchical clustering yields a dendrogram cut at a chosen height.

Dimensionality reduction: PCA projects onto eigenvectors of the covariance matrix, retaining components with the largest eigenvalues; explained-variance ratio = λ_i/Σλ_j; t-SNE preserves local neighborhoods for visualization only.

Ensembles: bagging averages high-variance learners to cut variance; boosting fits weak learners sequentially to residual-like gradients to cut bias; random forests add feature subsampling to decorrelate trees.

Bayes' theorem: P(A|B) = P(B|A)·P(A)/P(B); posterior ∝ likelihood × prior, and the denominator is the normalizing constant Σ or ∫ of the numerator over the hypothesis space.

Expectation and variance: E[aX + b] = aE[X] + b; Var(aX + b) = a²Var(X); Var(X) = E[X²] − (E[X])²; for independent variables Var(X + Y) = Var(X) + Var(Y).

Common distributions: Binomial(n, p) has mean np and variance np(1−p); Poisson(λ) has mean and variance λ; Normal(μ, σ²) has ~68/95/99.7% of mass within 1/2/3 standard deviations.

Central Limit Theorem: the sample mean of n i.i.d. variables with finite variance approaches Normal(μ, σ²/n); standard error of the mean = σ/√n, so quadrupling n halves the standard error.

Hypothesis testing: a p-value is P(data at least this extreme | H₀ true), not P(H₀ true); reject H₀ when p < α; a Type I error rejects a true H₀ (rate α), a Type II error fails to reject a false H₀ (power = 1 − β).

Confidence interval for a mean with known σ: x̄ ± z_{α/2}·σ/√n; a 95% interval uses z ≈ 1.96; wider intervals follow from larger σ or smaller n, and the interval does not give the probability the parameter lies inside.

Linear algebra essentials: rank = number of nonzero singular values = dimension of the column space; a square matrix is invertible iff determinant ≠ 0 iff all eigenvalues are nonzero.

Matrix facts: (AB)ᵀ = BᵀAᵀ; (AB)⁻¹ = B⁻¹A⁻¹; trace equals the sum of eigenvalues; determinant equals their product; a symmetric matrix is positive definite iff all eigenvalues are positive.

Conditional probability: P(A∩B) = P(A|B)·P(B); A and B are independent iff P(A∩B) = P(A)·P(B), which for nonzero probabilities is equivalent to P(A|B) = P(A).

Python complexity: list append and dict lookup are amortized O(1); list insert at position 0 is O(n); sorting with Timsort is O(n log n) worst case and O(n) on already-sorted input.

Mutable default arguments are evaluated once at function definition; use None as the default and create the list or dict inside the function to avoid shared state across calls.

Pandas semantics: loc selects by label, iloc by integer position; groupby(...).agg applies per-group reductions; merge with how in {inner, left, right, outer} controls which keys survive, and NaN propagates through arithmetic.

SQL evaluation order is FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY → LIMIT; WHERE filters rows before aggregation, HAVING filters groups after aggregation, and NULL comparisons need IS NULL rather than = NULL.

Data cleaning rules: drop or impute missing values (mean/median for numeric, mode for categorical); detect outliers with the IQR rule (below Q1 − 1.5·IQR or above Q3 + 1.5·IQR); standardize features before distance-based methods.

Neural network basics: a dense layer computes z = Wx + b then a = φ(z); ReLU φ(z) = max(0, z) avoids saturation for positive inputs; softmax converts logits to probabilities summing to 1, trained with cross-entropy loss.

Backpropagation applies the chain rule to compute gradients layer by layer; parameters update as W ← W − η·∂L/∂W; vanishing gradients in deep sigmoid or tanh networks are mitigated by ReLU, batch normalization, and residual connections.

Overfitting controls: more data, L1/L2 regularization, dropout, early stopping on validation loss, and reduced model capacity; underfitting shows high training and validation error and calls for more capacity or longer training.