03 Text Classification - Chunk 10 (s.271-300)

Overview

This part of the lecture finishes Concept - Logistic Regression (multiple weights, BoW input vectors; s.271) and then moves to evaluation of classifiers: the Concept - Confusion Matrix, accuracy, Concept - Precision and Recall, the precision/recall trade-off, the Concept - F1 Score and why accuracy fails on imbalanced data, and the Concept - ROC Curve and AUC (s.272-283). It then extends binary classification to multiclass problems with Concept - One-vs-All Classification and the Concept - Softmax Classifier trained with cross entropy (s.284-291). The last part contrasts Concept - Generative vs Discriminative Models (Naive Bayes vs logistic regression), notes that Naive Bayes ignores word dependencies (s.292-295), and starts the next topic, the Concept - Decision Tree with its terminology (s.296-300; s.300 is the divider “Function Approximation”).

Detailed notes

1. Logistic regression with multiple weights (s.271)

• Simplification so far: one feature x, hence only one weight $w$ and one bias $b$ (s.271).
• In practice each data sample is an n-dimensional vector; the logistic regression model has n weights and one bias b (s.271).
• For text mining, the input vectors are BoW vectors (see Concept - Bag of Words) (s.271).
• Worked output on the slide (colour-coded: weights orange, input values blue, bias dark red): $\text{output}=\sigma (-1.2\cdot 10+1.4\cdot 5+2.2\cdot 3+0.6\cdot 5+0.2)$ i.e. weights $-1.2,1.4,2.2,0.6$, input vector $(10,5,3,5)$ and bias $0.2$ (s.271). (Inner sum = $-12+7+6.6+3+0.2=4.8$ - added arithmetic, see note below.)

Added context

The value 4.8 is my arithmetic on the slide’s numbers; the slide only writes the expression.

2. Evaluation: the problem (s.272-273)

• s.272: section divider “Evaluation”.
• s.273: “How do we evaluate the model performance? i.e., how to quantify the matching degree between the ground truth y and the predicted labels $\hat{y}$.“

3. Confusion matrix and accuracy (s.274)

Confusion matrix for a binary problem (rows = true label, columns = prediction):

	Predicted Positive	Predicted Negative
Positive Label	TP (True Positive)	FN (False Negative)
Negative Label	FP (False Positive)	TN (True Negative)

• Accuracy: “How accurate is the prediction?” $\text{Accuracy}=\frac{\text{Correct Prediction}}{\text{Total \#-of-Samples}}=\frac{TP+TN}{TP+FP+TN+FN}$ (s.274)

4. Precision and recall (s.275)

• Same matrix with highlights: the Predicted Positive column (TP, FP; red oval) is the basis of precision; the Positive Label row (TP, FN; green oval) is the basis of recall (s.275).
• Precision $=\frac{TP}{TP+FP}$ - “how accurate the positive prediction is?” (s.275)
• Recall $=\frac{TP}{TP+FN}$ - “how many positive cases are detected?” (s.275)

5. Worked example: H6751 Auto-grade (s.276)

Confusion matrix (s.276):

	Predicted Positive	Predicted Negative
Positive Label	27	4
Negative Label	1	18

• Accuracy $=(27+18)/(27+1+18+4)=0.9$
• Precision $=27/(27+1)=0.964$
• Recall $=27/(27+4)=0.871$
• Closing question on the slide: “Can we do better?” (no answer given).

6. Precision vs recall (s.277-279)

• s.277 poses two cases with the prompt “Examples?” (answers not on the slide):
  • Case 1: accuracy is high, but recall is low.
  • Case 2: accuracy is high, but precision is low.
• s.278 (plot, GPA vs “K6312 Result”): logistic-regression example. x-axis GPA 1.0-4.8; y-axis result 0-1. Blue crosses at y=0 for GPA 1.0-2.8 and at y=1 for GPA 3.0-4.8; red curve = fitted sigmoid. Three horizontal decision thresholds are drawn:
  • dark-red line at about 0.8: High Precision, Low Recall;
  • green line at 0.5 (default);
  • orange line at about 0.2: Low Precision, High Recall.
  • Takeaway: moving the threshold on the predicted probability trades precision against recall.
• s.279: “Under non-trivial situation, precision and recall cannot be optimized at the same time”; which one to optimize depends on use cases. Right: precision-recall curve (precision falls from 1.0 at recall 0 to about 0.4 at recall 1; source towardsdatascience.com “beyond accuracy: precision and recall”).

Added context

Typical answers to s.277: Case 1 - rare-positive data (e.g. fraud) where predicting everything negative gives high accuracy but recall 0. Case 2 - predicting many positives wrongly while the negatives dominate. The slide itself does not answer; the fraud example appears on s.280.

7. F1 score vs accuracy (s.280)

• Accuracy does not perform well for imbalanced data sets. Example: 100 transactions, 90 non-fraud and 10 fraud; high accuracy can be achieved by classifying every transaction as non-fraud (s.280).
• Precision and recall can give more insights; the F1 score conveys the balance between precision and recall (s.280): $F1=\frac{2\times \text{precision}\times \text{recall}}{\text{precision}+\text{recall}}$

8. ROC and AUC (s.281-283)

• s.281: The ROC (Receiver Operation Characteristic) curve illustrates the diagnostic ability of a binary classifier as its discrimination threshold varies; it plots the true positive rate (TPR) against the false positive rate (FPR) at various thresholds.
• s.282:
  • FPR = probability of false alarm: $\frac{FP}{FP+TN}$.
  • TPR = probability of detection: $\frac{TP}{TP+FN}$.
  • Best possible prediction = point in the upper-left corner (0,1), called perfect classification.
  • A random guess gives a point along the diagonal.
• s.283: Area Under Curve (AUC) is the area under the ROC curve. The ROC curve plots TPR(T) versus FPR(T) parametrically with threshold T as the varying parameter. In the figure AUC(A) > AUC(B), so classifier A is better than classifier B. AUC equals the probability that the classifier ranks a randomly chosen positive example higher than a randomly chosen negative example. AUC is one of the most widely used metrics for binary classification.

9. Multiclass classification (s.284-287)

• s.284: divider “Multiclass Classification”.
• s.285 examples: Weather (Cloudy, Rain, Snow, …); Fruit (Apple, Orange, Peach, …); Email tagging (Work, Ad, Friends, …).
• s.286 figure: left “Binary classification” - red circles vs green squares separated by one line; right “Multiclass classification” - three groups (red circles, blue triangles, green squares), no single line separates them.
• One-vs-All (One-vs-Rest) (s.287): train a logistic regression classifier $p_i(y=1\mid x)$ for each class $i$ to predict the probability of $y=i$; predict $i^{\ast }=\arg {\max }_i{p}_i(y=1\mid x)$ Figure: three binary problems, each separating one class (coloured) from the rest (grey): red vs rest, blue vs rest, green vs rest.

10. Softmax classifier (s.288-291)

• s.288 (4-class): find 4 vectors $w_1..w_4$ such that $P(C_1|x):P(C_2|x):P(C_3|x):P(C_4|x)=e^{w_1^{T}x}:e^{w_2^{T}x}:e^{w_3^{T}x}:e^{w_4^{T}x}$; probabilities sum to 1: $P(C_1|x)=\frac{e^{w_1^{T}x}}{e^{w_1^{T}x}+e^{w_2^{T}x}+e^{w_3^{T}x}+e^{w_4^{T}x}}$ This is the softmax function (labelled in orange).
• s.289 (k-class): extend from the binary case; model $p(y=i|\mathbf{x})$, $i=\mathrm{1..}k$, with softmax: $P(y=i|\mathbf{x})=\frac{e^{w_i^{T}x}}{{\sum }_j{e}^{w_j^{T}x}}$ Figure: bar chart of raw scores -> after softmax the largest bar dominates and the others shrink (softmax sharpens and normalizes).
• s.290 (objective): optimize cross entropy: $L(\mathbf{w})=-{\sum }_{i=1}^N{\sum }_{k=1}^K{t}_{ik}\log p(y=k|\mathbf{x})$ where $t_{ik}=1$ if $y_i=k$, otherwise 0 (one-hot target). Figure (github.com/GoogleCloudPlatform/tensorflow-without-a-phd): cross entropy $-\sum Y_i^{\prime }\cdot \log (Y_i)$ with “actual probabilities, one-hot encoded” (a 1 at position 6 of digits 0-9) vs “computed probabilities” (0.1, 0.2, 0.1, 0.3, 0.2, 0.1, 0.9, 0.2, 0.1, 0.1; the 0.9 circled, “this is a 6”).
• s.291 (architecture): inputs $x_1..x_n$ plus bias feed $K$ linear units $z_j=w_j^{T}x$ (matrix form $\mathbf{z}=W\mathbf{x}$, rows $w_1^T..w_K^T$); softmax $e^{z_j}/{\sum }_k{e}^{z_k}$ gives class probabilities, shown as bars coloured green, blue, purple, …, red. Link on slide: stats.stackexchange.com “derivative of softmax with respect to weights”.

11. Generative vs discriminative (s.292-295)

• s.292: divider “Generative vs Discriminative”.
• s.293 For classification:
  • Generative: given features X and label Y, find the joint probability P(X,Y); “how was the data generated?”; from P(X,Y) get P(Y|X), then categorize; less direct, more probabilistic.
  • Discriminative: find the conditional probability P(Y|X); distribution-free approaches; simply categorizes the data; more direct, less probabilistic.
• s.294 Questions: “Generative and Discriminative?” with sub-items Naive Bayes and Logistic Regression (the slide asks which is which; answer expected: Naive Bayes = generative, Logistic Regression = discriminative, consistent with s.293 and s.295).
• s.295 Naive Bayes model for text generation: for word indices 1..T: randomly sample the category $h_i$ from $p(h)$ (or $h_i$ is fixed), then sample the word from the distribution $p(\mathbf{d}|h_i)$. However, it does not consider words’ intrinsic dependency: e.g. Probability(read the paper) > Probability(read the movie); the word at index T should depend on previous words (T-1, T-2, T-3, …). Hidden Markov Model partially solves this issue.

12. Decision tree intro (s.296-300)

• s.296: divider “Decision Tree”.
• s.297 What is a decision tree: a decision support tool that uses a tree-like model/graph of decisions and their possible consequences. Example “Should I do exercise today?”: root “Exercise Yesterday?” - Yes -> Don’t Go; No -> “Eat McSpicy Today?” - Yes -> Go; No -> Don’t Go.
• s.298: two properties: (1) top-down approach, (2) divide and conquer. Figure “Should I accept a new job offer?”: root node “salary at least $50,000” (no -> decline offer); yes -> decision node “commute more than 1 hour” (yes -> decline offer); no -> decision node “offers free coffee” (yes -> accept offer; no -> decline offer). Labels mark root node, decision nodes, leaf nodes (source: medium.com/greyatom).
• s.299 Terminology:
  • Root node: represents the entire population or sample, which is further divided into multiple subsets.
  • Splitting: dividing a node into two or more sub-nodes.
  • Decision node: a sub-node that can be split into further sub-nodes.
  • Leaf/Terminal node: nodes that do not split.
  • Branch/Sub-tree: a sub-section of the entire tree.
  • Pruning: remove nodes (opposite of splitting).
  • Parent and child node: a node divided into sub-nodes is the parent of those sub-nodes, which are its children. Figure note: “A is parent node of B and C”.
• s.300: section divider “Function Approximation” (content in next chunk).

Figures & diagrams

• s.271 Colour-coded logistic regression expression with 4 weights, 4 inputs and bias 0.2.
• s.274 Confusion matrix (TP/FN/FP/TN) with the accuracy formula.
• s.275 Confusion matrix with highlighted column (precision) and row (recall).
• s.276 Filled-in confusion matrix 27/4/1/18 for the auto-grade example.
• s.278 GPA vs K6312 result scatter with sigmoid curve and three thresholds (0.8, 0.5, 0.2).
• s.279 / s.280 Precision-recall curve, decreasing from (0,1) to (1, about 0.4).
• s.281-282 ROC space: points A, B, C, C’ with perfect classification at (0,1), random-guess diagonal, “better” above / “worse” below the diagonal. A, C’ are above the diagonal (better), B on it (random), C below (worse).
• s.283 Two ROC curves: A (blue, bowed towards upper left) above B (red), diagonal black = random.
• s.286 Binary (one separating line) vs multiclass (three clusters) scatter plots.
• s.287 One-vs-all: three binary separations.
• s.289 Softmax bar chart before / after (largest value amplified).
• s.290 One-hot target vs computed probabilities for digit “6”.
• s.291 Softmax network: bias + inputs -> $z_1..z_K$ -> softmax -> class probability bars.
• s.297-298 Decision tree examples (exercise, job offer).
• s.299 Tree anatomy: root, decision nodes, terminal nodes, branch/sub-tree, splitting arrow.

flowchart TD
    CM[Confusion Matrix<br/>TP FN FP TN] --> ACC["Accuracy = (TP+TN)/all"]
    CM --> P["Precision = TP/(TP+FP)"]
    CM --> R["Recall = TP/(TP+FN)"]
    P --> F1["F1 = 2PR/(P+R)"]
    R --> F1
    CM --> TPR["TPR = TP/(TP+FN)"]
    CM --> FPR["FPR = FP/(FP+TN)"]
    TPR --> ROC[ROC curve]
    FPR --> ROC
    ROC --> AUC[AUC = area under ROC]

flowchart LR
    X[Input x] --> Z["z_j = w_j^T x  (j=1..K)"]
    Z --> S["softmax: e^z_i / sum_k e^z_k"]
    S --> PR[Class probabilities sum to 1]
    PR --> L["Cross entropy loss vs one-hot target"]

flowchart TD
    R["Root: salary >= $50,000?"] -->|no| D1[decline offer]
    R -->|yes| N1["Decision: commute > 1 hour?"]
    N1 -->|yes| D2[decline offer]
    N1 -->|no| N2["Decision: free coffee?"]
    N2 -->|yes| A[accept offer]
    N2 -->|no| D3[decline offer]

Comparison (s.293, s.294):

	Generative	Discriminative
Learns	joint $P(X,Y)$ (how data was generated)	conditional $P(Y\mid X)$
Classification	derive $P(Y\mid X)$, then categorize	directly categorize
Style	less direct, more probabilistic	more direct, less probabilistic, distribution-free
Example (s.294)	Concept - Naive Bayes	Concept - Logistic Regression

Key terms

• Concept - Logistic Regression
• Concept - Bag of Words
• Concept - Confusion Matrix
• Concept - Precision and Recall
• Concept - F1 Score
• Concept - ROC Curve and AUC
• Concept - One-vs-All Classification
• Concept - Softmax Classifier
• Concept - Generative vs Discriminative Models
• Concept - Naive Bayes
• Concept - Decision Tree

Formulas

• Accuracy $=\frac{TP+TN}{TP+FP+TN+FN}$ (s.274)
• Precision $=\frac{TP}{TP+FP}$; Recall $=\frac{TP}{TP+FN}$ (s.275)
• $F1=\frac{2\cdot \text{precision}\cdot \text{recall}}{\text{precision}+\text{recall}}$ (s.280)
• $FPR=\frac{FP}{FP+TN}$; $TPR=\frac{TP}{TP+FN}$ (s.282)
• One-vs-all: $i^{\ast }=\arg {\max }_i{p}_i(y=1|x)$ (s.287)
• Softmax: $P(y=i|\mathbf{x})=\frac{e^{w_i^{T}x}}{{\sum }_j{e}^{w_j^{T}x}}$ (s.289)
• Cross entropy: $L(\mathbf{w})=-{\sum }_{i=1}^N{\sum }_{k=1}^K{t}_{ik}\log p(y=k|\mathbf{x})$, $t_{ik}=1$ iff $y_i=k$ (s.290)

Likely exam questions

Style: short “discuss / explain / determine the correctness” answers (see Past Exam - Question Bank & Style Guide, a Machine Learning past exam; no Text & Web Mining past exam is recorded, so only the style is borrowed).

1. What is a confusion matrix? Define TP, FP, TN, FN. (s.274) 2x2 table of true label vs predicted label; TP = positive predicted positive, FN = positive predicted negative, FP = negative predicted positive, TN = negative predicted negative.
2. Give the formulas for accuracy, precision and recall. (s.274-275) $(TP+TN)/(TP+FP+TN+FN)$; $TP/(TP+FP)$; $TP/(TP+FN)$.
3. Given TP=27, FN=4, FP=1, TN=18, compute accuracy, precision, recall. (s.276) 0.9, 0.964, 0.871.
4. Discuss the trade-off between precision and recall. (s.278-279) Raising the probability threshold gives high precision but low recall; lowering it gives low precision but high recall; they cannot generally both be optimized, the choice depends on the use case.
5. Why is accuracy a poor metric for imbalanced data? (s.280) 90 non-fraud / 10 fraud: classifying everything as non-fraud gives 90% accuracy but detects no fraud; use precision, recall, F1.
6. What is the F1 score? (s.280) Balance of precision and recall, $2PR/(P+R)$.
7. Explain the ROC curve and the axes. (s.281-282) TPR vs FPR at varying thresholds; ideal point (0,1); random guess = diagonal.
8. What is AUC and how do you interpret it? (s.283) Area under ROC; probability a random positive is ranked above a random negative; larger AUC = better classifier.
9. How can logistic regression be used for multiclass problems? (s.287) One-vs-all: train one LR per class, predict $\arg {\max }_i{p}_i$.
10. Write the softmax function and the loss used to train it. (s.289-290) $e^{w_i^{T}x}/{\sum }_j{e}^{w_j^{T}x}$; cross entropy with one-hot targets.
11. Compare generative and discriminative approaches; classify Naive Bayes and logistic regression. (s.293-294) See comparison table: NB generative (joint P(X,Y)), LR discriminative (P(Y|X)).
12. State a limitation of the Naive Bayes generative model. (s.295) Ignores word dependencies (order/context); HMM partially solves this.
13. Define the decision-tree terms root, splitting, decision node, leaf, pruning, parent/child. (s.299) See s.299 definitions above.

Common confusions

• Precision vs recall denominators: precision divides by predicted positives (TP+FP, column), recall by actual positives (TP+FN, row) (s.275).
• Recall vs TPR: recall and TPR have the same formula $TP/(TP+FN)$ (s.275, s.282).
• High threshold = high precision, low recall (dark-red line, s.278); low threshold = low precision, high recall (orange line).
• Accuracy can be high while recall is low on imbalanced data (s.277, s.280).
• ROC “better” direction: points towards the upper-left corner are better; points below the diagonal are worse than random (s.281-282).
• Softmax vs one-vs-all: one-vs-all trains K independent binary LR models; softmax trains K weight vectors jointly so probabilities sum to 1 (s.287-289).
• Generative vs discriminative: generative models P(X,Y); discriminative models P(Y|X) directly (s.293).
• Pruning is the opposite of splitting (s.299).

Slide coverage

Slide	Content	Covered in
271	Multiple weights: n weights + 1 bias, BoW input, example expression	Detailed notes 1
272	Divider: Evaluation	Detailed notes 2
273	How to evaluate model performance (y vs y-hat)	Detailed notes 2
274	Confusion matrix, accuracy	Detailed notes 3
275	Precision and recall	Detailed notes 4
276	H6751 auto-grade example (27/4/1/18)	Detailed notes 5
277	Precision vs recall: cases with high accuracy (questions)	Detailed notes 6
278	GPA/K6312 plot with thresholds	Detailed notes 6; Figures
279	Precision-recall trade-off curve	Detailed notes 6; Figures
280	F1 score vs accuracy, imbalanced data	Detailed notes 7
281	ROC definition and ROC space	Detailed notes 8; Figures
282	FPR, TPR, perfect classification, random guess	Detailed notes 8
283	AUC	Detailed notes 8; Figures
284	Divider: Multiclass classification	Detailed notes 9
285	Multiclass examples (weather, fruit, email)	Detailed notes 9
286	Binary vs multiclass figure	Detailed notes 9; Figures
287	One-vs-all	Detailed notes 9
288	Softmax (4-class)	Detailed notes 10
289	Softmax (k-class) and bar chart	Detailed notes 10
290	Cross entropy objective	Detailed notes 10; Formulas
291	Softmax network diagram	Detailed notes 10; Figures
292	Divider: Generative vs Discriminative	Detailed notes 11
293	Generative vs discriminative approaches	Detailed notes 11
294	Questions: NB / LR generative or discriminative	Detailed notes 11
295	Naive Bayes for text generation; HMM	Detailed notes 11
296	Divider: Decision tree	Detailed notes 12
297	What is a decision tree (exercise example)	Detailed notes 12
298	Top-down, divide and conquer; job-offer tree	Detailed notes 12; Figures
299	Decision tree terminology	Detailed notes 12
300	Divider: Function approximation	Detailed notes 12

Previous: 03 Text Classification - Chunk 09 (s.241-270) | Next: 03 Text Classification - Chunk 11 (s.301-330) | Up: 03 Text Classification - Index