03 Text Classification - Cheat Sheet

Up: 03 Text Classification - Index | 03 Text Classification - Mind Map

Core definitions

• Bayes rule (s.13): $p(h|D)=\frac{p(D|h)p(h)}{p(D)}$: posterior = likelihood x prior / evidence. Concept - Bayes Rule
• MLE $\arg {\max }_{h}P(D|h)$ vs MAP $\arg {\max }_{h}P(D|h)P(h)$; equal for a uniform prior (s.18-19). Concept - Maximum Likelihood Estimation, Concept - Maximum A Posteriori
• Naive Bayes (s.23): $h_{NB}=\arg {\max }_{h}p(h){\prod }_{j}p(d_j|h)$, assuming attributes are independent given the class. Often violated, still works well. Concept - Naive Bayes, Concept - Conditional Independence
• Parameter estimate (s.28): $p(w|h)=\frac{count(w,h)}{{\sum }_{d}count(d,h)}$ from a per-class mega-document.
• Zero probability / OOV: an unseen word zeroes the whole product. Fix: additive smoothing $\frac{count+\alpha }{total+\alpha V}$ ($\alpha =1$ is Laplace; add a pseudo-count to every word). Concept - Zero Probability Problem, Concept - Additive Smoothing, Concept - Laplace Smoothing, Concept - Out of Vocabulary (OOV)
• Underflow: multiplying many small numbers; use the sum of logs instead. Concept - Underflow
• Why “naive” yet good: ignores word order (bag of words); high bias, low variance.
• Logistic regression: sigmoid $\sigma (z)=\frac{1}{1+e^{-z}}$ on a linear score; trained with cross-entropy loss by gradient descent; linear decision boundary. Concept - Logistic Regression, Concept - Sigmoid Function, Concept - Cross-Entropy Loss, Concept - Gradient Descent, Concept - Decision Boundary
• Generative (NB: models $p(x|y)p(y)$) vs discriminative (LR: models $p(y|x)$). Concept - Generative vs Discriminative Models

Key comparison

Method	Input features	Model of	Notes
Concept - Multinomial Naive Bayes	word counts / TF-IDF	$p(w	class)$ per word occurrence
Concept - Bernoulli Naive Bayes	binary presence/absence	presence prob. per word	Also penalizes absent words
Concept - Gaussian Naive Bayes	continuous values	one Gaussian per feature per class	Use log scores
Concept - Logistic Regression	any vector (e.g. BoW)	$p(y	x)$ directly
Concept - Decision Tree	attributes	recursive splits	Easy to read, prone to overfit

Evaluation formulas

• Accuracy $=\frac{TP+TN}{\text{all}}$ (misleading on imbalanced data); Precision $=\frac{TP}{TP+FP}$; Recall $=\frac{TP}{TP+FN}$; $F_1=\frac{2PR}{P+R}$. Concept - Confusion Matrix, Concept - Precision and Recall, Concept - F1 Score
• ROC plots TPR vs FPR over thresholds; AUC = area under it. Concept - ROC Curve and AUC
• Multiclass: Concept - One-vs-All Classification or Concept - Softmax Classifier.

Decision trees

• ID3 greedily picks the attribute with the highest information gain $=H(S)-\sum \frac{|S_v|}{|S|}H(S_v)$, with entropy $H=-\sum p_i{\log }_2{p}_i$. Concept - ID3, Concept - Entropy, Concept - Information Gain
• IG favours many-valued attributes; gain ratio corrects this. Gini $=1-\sum p_i^2$ is the alternative criterion. Concept - Gain Ratio, Concept - Gini Impurity
• Continuous attributes: threshold splits. Concept - Splitting Continuous Attributes
• Overfitting is limited by pruning (pre: stopping criteria; post: validation set). Concept - Decision Tree Pruning, Concept - Overfitting

Ensembles

• Concept - Bagging: bootstrap samples + majority vote (Concept - Bootstrapping, Concept - Majority Voting); Concept - Random Forest = bagged trees with random feature choice. Reduces variance; helps unstable learners.
• Concept - Boosting: sequentially focus on errors of weak learners. Concept - Stacking: a meta-learner combines base models.
• Concept - Bias-Variance Tradeoff, Concept - No Free Lunch Theorem.

Worked numbers to remember

• Likes/dislikes: 300 of 1000 like, so $p(like)=0.3$, $p(dislike)=0.7$ (s.27).
• Spam example: $p(N)=0.67$, $p(S)=0.33$; “Dear Friend” scores 0.09 (normal) vs 0.01 (spam), so normal; “Lunch Money Money Money Money” gives spam 0 until smoothing (s.65-135).
• Gaussian NB Troll 2: log scores about -124 (loves) vs -48 (does not love), so “Does not love” (s.211-238).

Likely exam questions (across the deck)

1. Explain Naive Bayes, the independence assumption and why it is “naive”. (s.21-23, 136-145)
2. Describe the zero-probability problem and how smoothing fixes it. (s.29-30, 119-135)
3. MLE vs MAP. (s.19)
4. Multinomial vs Bernoulli vs Gaussian NB: when to use each. (s.146-181)
5. Why use logs in NB? (s.204-214)
6. Why is linear regression a poor classifier; what does the sigmoid fix? (s.253-263)
7. Naive Bayes vs logistic regression (generative vs discriminative). (s.292-295)
8. Define precision, recall, F1; why accuracy fails on imbalanced data. (s.272-283)
9. ID3: compute entropy / information gain / Gini on a small table. (s.311-327)
10. Overfitting, pruning, and how bagging/boosting/stacking differ. (s.331-360)
11. Inter-annotator agreement and getting labels. (s.374-381)

See also Past Exam - Question Bank & Style Guide for the exam style.