Machine Learning Algorithms and Theory Questions

Core supervised and unsupervised machine learning algorithms and the theoretical principles that guide their selection and use. Covers linear regression, logistic regression, decision trees, random forests, gradient boosting, support vector machines, k means clustering, hierarchical clustering, principal component analysis, and anomaly detection. Topics include model selection, bias variance trade off, regularization, overfitting and underfitting, ensemble methods and why they reduce variance, computational complexity and scaling considerations, interpretability versus predictive power, common hyperparameters and tuning strategies, and practical guidance on when each algorithm is appropriate given data size, feature types, noise, and explainability requirements.

HardTechnical

26 practiced

Analyze sample complexity for learning a linear classifier. Discuss how margin size, presence of label noise, and model capacity (VC dimension) affect the number of labeled examples required to reach a target generalization error. Provide intuitive derivations and practical guidance for data collection strategies.

Sample Answer

**Approach overview**I summarize sample-complexity results for linear classifiers, then show how margin, label noise, and VC dimension change required labeled examples. I end with practical data-collection guidance.

**Key results (intuitions + formulas)**- VC-dimension for d-dimensional homogeneous linear classifier is d. Using VC bounds, to get generalization error ≤ ε with probability 1−δ:

text

n = O( (d + log(1/δ)) / ε )

Intuition: more parameters (d) → more examples linear in d.

- Margin (large-margin / separable case): with margin γ and data bounded in radius R, the Perceptron/SVM margin bound gives

text

n = O( (R^2 / γ^2) * log(1/δ) )

Intuition: larger margin reduces effective complexity — sample complexity depends on 1/γ^2, not d.

- Label noise (agnostic / classification noise): in the agnostic PAC setting, error compares to best achievable err*; sample complexity scales as

text

n = O( (VC + log(1/δ)) / ε^2 )

Intuition: noise forces 1/ε^2 dependence; achieving small excess error needs more samples.

**Combined view and trade-offs**- Clean, separable data with large margin → sample complexity depends on 1/γ^2, often much smaller than d.- High-capacity model (large d) with small margin and noisy labels → worst: n scales like d / ε^2.- Regularization (norm constraints) effectively reduces capacity toward margin-like bounds.

**Practical guidance for data collection**- If you can engineer features to increase margin (feature scaling, feature selection, PCA), do so — reduces samples needed.- If label noise is suspected, invest in label cleaning or repeated labeling (consensus) to reduce noise; budget trade-off: one high-quality label often better than multiple noisy ones.- Use active learning in margin-friendly regimes: uncertainty sampling often reduces labels to ~log(1/ε) factors when separable.- Monitor learning curves (error vs n) early to detect regime (1/ε vs 1/ε^2) and reallocate labeling budget (more labels vs better features).

**Takeaway**Aim to reduce effective capacity (through features/regularization) and label noise; both yield far bigger sample-efficiency gains than merely collecting more labels.

HardTechnical

24 practiced

A stakeholder asks to include PII-derived features (e.g., exact address, date-of-birth) to improve model accuracy. You lead the applied science team: describe how you'd assess privacy, legal and ethical risks, propose alternative approaches that preserve utility (coarsening, hashing, synthetic data, differential privacy), and explain how you'd communicate the decision and implement guardrails.

Sample Answer

**Situation & goal** A stakeholder requests exact PII (address, DOB) to boost model accuracy. My responsibility is to balance model utility with legal, privacy, and ethical risk, then recommend a safe path and operational guardrails.

**Assessing privacy / legal / ethical risk** - Rapid intake: identify data lineage, purpose, retention, processing location, and applicable laws (GDPR, CCPA, sector rules). - Perform a Data Protection Impact Assessment (DPIA): map threats (re-identification, profiling, secondary use), attack surface, and potential harms. - Quantify risk: sensitivity score, likelihood of re-identification, and business impact. - Consult legal/compliance and ethics council before any PII use.

**Alternative approaches preserving utility** - Coarsening / minimal granularity: use ZIP3 or city instead of full address; age-bands instead of DOB. Often retains most signal with lower risk. - Feature hashing / encoding: deterministic hashes for grouping while avoiding reversible identifiers; combine with salt and access controls. - Derived features: distance-to-nearest-store or time-since-birth rather than raw DOB. - Synthetic data: train on realistic but non-identifying synthetic records for model pretraining or testing. - Differential privacy: add calibrated noise during training (DP-SGD) or to released aggregates to provide provable privacy guarantees. - K-anonymity / l-diversity checks if releasing datasets.

I would prototype 2–3 alternatives (coarsened features, hashed+derived features, DP-trained model) and evaluate accuracy delta via A/B testing and lift analysis. Emphasize cost/benefit: small accuracy gains rarely justify high legal risk.

**Decision & stakeholder communication** - Present DPIA findings, accuracy trade-offs, mitigation options, and recommended path. - Use visual comparisons: accuracy vs risk curves, and concrete examples of harms. - Offer a rollout plan: prototype with protected experiment, periodic reviews, and escalation route if further PII is essential.

**Implementation & guardrails** - Block direct PII in model training pipelines; require explicit exception with senior approvals. - Technical controls: encryption-at-rest/in-transit, secure enclaves for any approved PII work, salted hashing, access RBAC, and short-lived credentials. - Operational controls: feature flag for PII-derived features, audit logging, regular re-review, automated checks for leakage (membership inference tests, adversarial re-ID). - Model governance: model cards documenting data, intended use, known risks, and revocation plan; monitoring for drift and fairness impact across subgroups.

**Outcome expectation & follow-up** - Deliver safe prototype showing comparable utility with reduced risk. If stakeholder still requests exact PII, require documented justification, updated DPIA, legal sign-off, and strongest possible controls (secure enclave + minimal retention + DP if feasible).

MediumTechnical

23 practiced

Outline a practical hyperparameter tuning plan for XGBoost on a tabular dataset (~1M rows). Which hyperparameters do you tune first, which search strategies (grid, random, Bayesian) do you use under compute constraints, how do you use early stopping, and what validation procedure avoids overfitting?

MediumTechnical

26 practiced

Derive the closed-form solution for ordinary least squares linear regression using normal equations (theta = (X^T X)^{-1} X^T y). Explain computational complexity, memory, numerical stability issues, and describe when you would avoid the normal equations in favor of gradient-based optimization or regularized methods like ridge regression in production.

Sample Answer

**Closed-form derivation (brief)**

Start from minimizing mean squared error: minimize ||y - X θ||_2^2. Setting gradient to zero gives normal equations.

text

X^T X θ = X^T y
θ = (X^T X)^{-1} X^T y

Intuition: X^T X projects covariance of features; solving yields coefficients that make residuals orthogonal to feature columns.

**Computational cost & memory**

- Forming X^T X costs O(n p^2) (n = rows, p = features).- Inverting or solving costs O(p^3) (matrix factorization).- Total roughly O(n p^2 + p^3).- Memory: storing X is O(n p); X^T X is O(p^2). For large n or p this becomes prohibitive.

**Numerical stability**

- Direct inversion of X^T X can be unstable if X^T X is ill-conditioned (high condition number) or singular (multicollinearity).- Prefer numerically stable solvers: QR decomposition or SVD, or call a linear solver (e.g., solve(A,b)) rather than explicit inverse.- SVD gives stable pseudo-inverse for rank-deficient X.

**When to avoid normal equations**

- p large (p ≳ few thousands) because p^2 and p^3 costs and memory blow up.- n ≫ p but streaming/online requirements: use stochastic gradient descent (SGD) or mini-batch optimizers.- Multicollinearity or near-singularity: use regularization (Ridge).

**Regularization (ridge) and production choices**

Ridge adds λI to stabilize inversion:

text

θ_ridge = (X^T X + λ I)^{-1} X^T y

- Improves conditioning (adds λ to eigenvalues), reduces variance.- For very large-scale problems use iterative solvers (conjugate gradient, L-BFGS) or SGD with early stopping.- In production choose based on scale, need for online updates, and numerical properties: use QR/SVD or regularized iterative solvers rather than explicit normal-equation inversion.

HardTechnical

29 practiced

Explain why common tree-based feature importance measures (like Gini importance) are biased toward features with many categories or continuous features. Describe unbiased alternatives (permutation importance, conditional permutation, SHAP), their trade-offs, computational costs, and how you would choose an approach in production.

Sample Answer

**Why Gini/Tree-based importances are biased**

Tree impurity measures (Gini, entropy, split-count) favor features that allow more potential splits — high-cardinality categorical features or continuous variables — because they can produce larger impurity reductions by chance. Trees evaluate many candidate thresholds; with more distinct values the probability of finding a spurious split that reduces impurity increases, inflating importance even when the feature has little true signal.

**Unbiased alternatives and trade-offs**

- Permutation importance - What: Shuffle a feature and measure drop in model performance. - Pros: Model-agnostic, interpretable global importance, removes split-count bias. - Cons: Correlated features cause misleading drops (importance shared across correlated predictors); can be unstable for small validation sets. - Cost: O(m · Npred) evaluations (m features) — potentially expensive.

- Conditional permutation importance - What: Permute feature while conditioning on correlated features (block or model-based conditional sampling). - Pros: Accounts for correlation, yields more causal-like importances. - Cons: Requires modeling feature conditional distribution (complex with high-dim or mixed types); computationally heavier. - Cost: Extra fit/sampling cost per feature plus repeated predictions.

- SHAP (TreeSHAP or KernelSHAP) - What: Shapley-value–based attribution producing local and global importances. - Pros: Theoretically grounded, handles feature interactions, local explanations, TreeSHAP is fast for tree ensembles. - Cons: KernelSHAP is slow; Shapley assumes feature independence unless conditional variants used; explanations can be misinterpreted as causal. - Cost: TreeSHAP O(T·L) per prediction (trees T, leaves L); KernelSHAP exponential sampling cost approximated by Monte Carlo.

**How I'd choose in production**- Start with permutation importance on a held-out set for quick, unbiased global ranking.- If strong feature correlation exists or interpretability must reflect conditional effects, use conditional permutation (with well-validated conditional samplers) or TreeSHAP with conditional sampling.- For large-scale real-time explanations on tree ensembles, use TreeSHAP (precompute where possible) and present global permutation as complementary.- Monitor stability (bootstrapped importances), cost, and business needs (global vs local, causal vs associative) before finalizing.

Unlock Full Question Bank

Get access to hundreds of Machine Learning Algorithms and Theory interview questions and detailed answers.

Join thousands of developers preparing for their dream job.