A Comprehensive Overview of Statistical Learning Methods for Machine Learning Interview Preparation

1. Knowledge Points

Processes and threads are described as CPU time slices of different granularity; discriminative models learn decision functions directly (e.g., k‑NN, perceptron, decision tree, logistic regression, SVM, boosting, CRF), while generative models learn joint distributions (e.g., Gaussian mixture, HMM, Naive Bayes, AODE, LDA).

Probability mass function (PMF), probability density function (PDF), and cumulative distribution function (CDF) are defined, followed by maximum likelihood estimation and least squares methods.

Gradient descent variants (BGD, SGD, MBGD) and Newton/Quasi‑Newton methods (including DFP and BFGS) are presented with their update formulas.

Bias‑variance decomposition, prior/posterior probabilities, and the principle of empirical versus structural risk minimization are explained.

2. Perceptron

The perceptron is a linear binary classifier with weight vector w and bias b , separating data by a hyperplane w·x + b = 0 . Its loss sums distances of mis‑classified points, and training uses stochastic gradient descent to adjust w and b .

The dual form expresses the solution as a linear combination of training examples, enabling kernel‑based extensions.

3. k‑Nearest Neighbors (k‑NN)

k‑NN classifies a query point by majority vote among its k nearest neighbors, typically using Euclidean distance. kd‑trees are introduced for efficient neighbor search, with recursive splitting and back‑tracking strategies illustrated.

4. Naive Bayes

Based on Bayes' theorem and the conditional independence assumption, the classifier computes posterior probabilities P(y|x) ∝ P(y)∏_i P(x_i|y) . Parameters are estimated via maximum likelihood or Laplace smoothing to avoid zero probabilities.

5. Decision Trees

Decision trees consist of internal feature nodes and leaf class nodes. Tree construction uses impurity measures such as entropy, information gain, gain ratio, and Gini index. Algorithms like ID3, C4.5, and CART are described, along with pruning strategies that minimize a loss function combining empirical entropy and tree complexity.

6. Logistic Regression and Maximum Entropy Models

Logistic regression models the log‑odds as a linear function of inputs, trained by maximizing the log‑likelihood (or minimizing cross‑entropy). Maximum entropy models share the same exponential form and are learned by maximizing likelihood under feature‑based constraints, often solved via iterative scaling or Newton‑type methods.

7. Support Vector Machines (SVM)

SVM finds the hyperplane with maximal margin, formulated as a convex quadratic program. Both hard‑margin (linearly separable) and soft‑margin (non‑separable) versions are presented, with dual derivations involving Lagrange multipliers and kernel functions (polynomial, Gaussian/RBF, string kernels). The SMO algorithm solves the dual efficiently by iteratively optimizing two variables.

8. Boosting and Gradient Boosting Trees

AdaBoost reweights mis‑classified samples and combines weak learners via weighted voting. Gradient Boosting Trees (GBDT) fit the negative gradient of a loss function at each iteration, using decision trees as base learners. XGBoost extends GDT with second‑order derivatives, regularization, column sampling, and optimized parallel computation.

9. Expectation‑Maximization (EM) Algorithm

EM iteratively performs an E‑step (computing expected sufficient statistics given current parameters) and an M‑step (maximizing the expected complete‑data log‑likelihood). The algorithm is applied to Gaussian Mixture Models, updating mixture weights, means, and covariances until log‑likelihood convergence.

10. Hidden Markov Models (HMM)

HMMs model sequences with hidden states and observable emissions, defined by initial state distribution π , transition matrix A , and emission matrix B . The forward‑backward algorithm computes observation likelihoods, the Baum‑Welch (EM) algorithm learns parameters unsupervised, and the Viterbi algorithm finds the most probable state sequence.

11. Summary of Statistical Learning

A visual summary (image) consolidates the relationships among the discussed models and algorithms.

12. Neural Networks

Neural units aggregate weighted inputs, apply an activation function, and output signals. Training uses back‑propagation (BP) with forward pass, error computation, and gradient‑based weight updates. Variants include deep neural networks (DNN), convolutional neural networks (CNN) for images, recurrent neural networks (RNN) for sequences, and long short‑term memory (LSTM) networks for long‑range dependencies.

13. K‑Means Clustering

K‑Means partitions data into K clusters by iteratively assigning points to nearest centroids and recomputing centroids. Improvements such as K‑Means++, Elkan’s triangle inequality acceleration, and Mini‑Batch K‑Means for large datasets are described.

14. Bagging and Random Forests

Bagging builds multiple models on bootstrap samples and aggregates predictions (majority vote or averaging). Random Forests specialize bagging with CART trees and random feature sub‑sampling, improving variance reduction.

15. Apriori Algorithm

Apriori discovers frequent itemsets using support and confidence thresholds, generating candidate k‑itemsets from frequent (k‑1)‑itemsets and pruning infrequent ones.

16. Dimensionality Reduction

Techniques include Principal Component Analysis (PCA) for variance‑maximizing orthogonal projections, Singular Value Decomposition (SVD) for matrix factorization, and Linear Discriminant Analysis (LDA) for class‑separability maximization.

17. References

Key references include a Zhihu discussion on back‑propagation and Pinard’s blog series on statistical learning.