Classification Models

Source: Concepts adapted from Ace the Data Science Interview — Chapter 7 (“Machine Learning”) by Kevin Huo & Nick Singh. Rewritten in original wording for this course. Coding uses scikit-learn on Piston.

With evaluation tools from Classification fundamentals, this lesson covers the interview workhorses: logistic regression, Naive Bayes, SVMs, and decision trees — when they shine, where they fail, slider explorers (sigmoid, logistic 1-D, entropy, NB posteriors), and short coding drills after each.

Logistic regression

Map a linear score $X\beta$ through the sigmoid into a probability:

$$P(Y=1\mid X) = \sigma(X\beta) = \frac{1}{1+e^{-X\beta}}$$

Default threshold 0.5 → class 1 if $\sigma \ge 0.5$, else 0 (tune the threshold for FP/FN costs). Multi-class uses softmax (multinomial logistic).

Why interviews love it: fast, probabilistic, highly interpretable coefficients. Pitfalls: high bias / low variance — struggles with nonlinear boundaries; correlated features muddy $\beta$ (same remedies as linear regression: drop features, regularize).

Training typically minimizes log-loss (cross-entropy).

Quiz

Logistic regression

1 / 4

The sigmoid’s job is to…

Pick an answer to see if you are right.

Compute

Compute: sigmoid

1 / 5

Story problem — figure out which numbers are the formula inputs, then compute.

Sigmoid σ(z)=1/(1+e^(−z)). What is σ(-1)? Round to 2 decimals.

Enter a number (at most 2 decimal places).

Practice: logistic regression

Naive Bayes

Estimate $P(Y\mid X)$ via Bayes’ rule under strong assumptions:

1. Features are conditionally independent given $Y$
2. Features are treated with equal weight in that factorization

$$P(X_1,\ldots,X_d\mid Y) = \prod_{j=1}^{d} P(X_j\mid Y)$$ $$\hat y = \arg\max_y\, P(Y=y)\prod_j P(X_j\mid Y=y)$$

Why it works in practice: tiny data needs, very fast, strong text baseline (spam / sentiment) even when independence is false. Caveat: the independence assumption is almost never literally true — yet linear separation often still helps.

Independence cuts the interaction explosion: instead of needing order $2^d$ samples for all feature interactions, you estimate $d$ one-dimensional conditionals.

Quiz

Naive Bayes

1 / 4

The “naive” part is mainly…

Pick an answer to see if you are right.

Practice: Naive Bayes

Support vector machines (SVMs)

Find a maximum-margin hyperplane separating classes. Points on the margin boundary are support vectors.

When data are not linearly separable in the original space, a kernel $K(x,y)=\phi(x)^{\top}\phi(y)$ implicitly maps to a higher-dimensional feature space (the kernel trick) so a linear separator there can look nonlinear in input space. Common kernels: linear, RBF / Gaussian.

Prefer SVM when…	Prefer simpler linear models when…
Clear margin / nonlinear boundary, moderate $n$, high $d$	Need probabilities & interpretability, huge $n$
Kernel can help separation	Classes heavily overlap / compute budget is tight

SVMs are weaker when datasets are enormous (cost) or when you must explain a probability to a PM.

Quiz

SVMs

1 / 4

SVMs primarily maximize…

Pick an answer to see if you are right.

Practice: SVM

Decision trees (CART)

A tree recursively splits the feature space to reduce impurity. Each leaf holds a class prediction (or a regression mean — CART covers both).

Training is greedy: at each node, try splits and pick the one with largest information gain.

Entropy of a discrete label $Y$:

$$H(Y) = -\sum_k P(Y=k)\log P(Y=k)$$

(Binary: peaks at $p=0.5$, zero at $p\in\{0,1\}$.) Trees often use Gini impurity in practice — same “purer leaves are better” idea.

Information gain for a split on $X$:

$$\mathrm{IG}(Y,X) = H(Y) - H(Y\mid X)$$

Choose the feature/threshold maximizing IG; recurse on child nodes.

Interview bar: explain training, entropy / IG, and why single trees overfit (deep trees memorize) — leading to forests later.

Quiz

Decision trees

1 / 4

Information gain measures…

Pick an answer to see if you are right.

Compute

Compute: binary entropy

1 / 5

Story problem — figure out which numbers are the formula inputs, then compute.

Binary entropy H(p)=−p log₂ p − (1−p) log₂(1−p) (0 at p∈{0,1}). What is H(1)? Round to 2 decimals.

Enter a number (at most 2 decimal places).

Practice: entropy & trees

Model cheat sheet

Model	Strength	Watch out
Logistic regression	Probabilities, speed, interpretability	Linear boundary; collinearity
Naive Bayes	Tiny data, text, speed	Independence assumption
SVM (+ kernel)	Margins, nonlinear via kernels	Scale / interpretability
Decision tree	Nonlinear, readable rules	Overfit if deep; unstable splits

Quick synthesis

Topic	Sound bite
Logistic	$\sigma(X\beta)$ → probability; log-loss; softmax for $K>2$
Naive Bayes	Bayes + conditional independence; great text baseline
SVM	Max margin; kernels for nonlinear; support vectors
Trees	Greedy splits maximizing IG / impurity drop; CART

Ensembles (random forests, boosting) build on these trees — continue in Random Forests & Boosting.