Text Classification Fundamentals

A text classification task is specified by a document space $\mathcal{X}$, a finite label set $\mathcal{Y} = \{y_1, \dots, y_k\}$, and a target function $f: \mathcal{X} \to \mathcal{Y}$ that we want to approximate. In the supervised setting, we are given a labeled dataset $D = \{(x_i, y_i)\}_{i=1}^N$ of documents paired with their true labels, and the goal is to learn a hypothesis $\hat{f}$ that generalizes well to unseen documents, not merely one that memorizes $D$. Before any learning algorithm can act, a document must become a feature vector: a fixed-length numerical representation $\phi(x) \in \mathbb{R}^d$. The simplest such representation, bag-of-words, counts vocabulary term occurrences; TF-IDF reweights those counts to downweight terms common across the whole corpus and upweight terms distinctive to a document. Other common features include n-grams (capturing local word order), document length, presence of specific punctuation or capitalization patterns (useful for spam or sentiment), and, in modern systems, dense embeddings from a pretrained encoder. Feature engineering — deciding what $\phi$ captures — is often as consequential as the choice of classifier itself, because a classifier can only exploit information that survives the encoding step. Given a training set of feature vectors and labels, a classifier is any function that maps $\phi(x)$ to a predicted label $\hat{y}$, usually by scoring each candidate label and picking the highest-scoring one. The classifier's parameters are fit by an optimization procedure that minimizes some loss on the training data — for example, maximizing the likelihood of the observed labels under a probabilistic model. Binary classification distinguishes two classes (spam vs. not-spam); multiclass classification distinguishes among $k > 2$ mutually exclusive classes (topic tagging into "sports," "politics," "tech," ...); multilabel classification allows a document to receive several labels simultaneously (a news article can be both "politics" and "economy"). The evaluation methodology described here applies to all three settings, with small adjustments for multilabel scoring.

The end-to-end pipeline has four stages: representation, splitting, training, and evaluation. Each stage has specific responsibilities and specific failure modes if done carelessly.

1. Representation. Every document is passed through a fixed feature function $\phi$, producing a vector of the same dimensionality $d$ for every document, regardless of the document's original length. This is what allows classifiers — which expect fixed-size numerical input — to operate uniformly over documents of varying length. The vocabulary used to build $\phi$ (which words map to which coordinates) must be fixed using only the training set; using test-set vocabulary is a subtle form of information leakage.

2. Splitting. The labeled dataset is partitioned into disjoint subsets:

• Training set — used to fit the classifier's parameters.
• Validation (development) set — used to tune hyperparameters and make modeling decisions (which features to use, how much regularization, when to stop training).
• Test set — touched exactly once, at the very end, to report a final unbiased performance estimate.

A common split is 80/10/10 or 70/15/15, though the right ratio depends on dataset size; with very large datasets, even a 98/1/1 split can leave thousands of validation/test examples. When labeled data is scarce, k-fold cross-validation replaces a single validation split: the training pool is divided into $k$ folds, and the model is trained $k$ times, each time validating on a different fold, with results averaged. This uses data more efficiently at the cost of $k\times$ the training time.

3. Training. The classifier's parameters are optimized on the training set only. For probabilistic classifiers this typically means maximizing the log-likelihood of the training labels (see Naive Bayes for Text for a worked instance); for margin-based classifiers, minimizing a hinge-loss objective; for neural classifiers, minimizing cross-entropy via gradient descent.

4. Evaluation. The trained classifier is applied to held-out data, and its predictions are compared against true labels using metrics discussed below. Validation-set performance guides model selection; test-set performance is the number that gets reported as the final result. ``` function TRAIN_AND_EVALUATE(labeled_data, feature_fn, classifier_class):

# Step 1: split data BEFORE any feature extraction that uses corpus statistics train, dev, test = SPLIT(labeled_data, ratios=(0.8, 0.1, 0.1), stratified=True)

# Step 2: fit feature extractor (e.g. vocabulary, IDF weights) on TRAIN ONLY feature_fn.fit(train.documents) best_model = None best_dev_score = -infinity for hyperparams in HYPERPARAMETER_GRID: model = classifier_class(hyperparams) X_train = [feature_fn.transform(doc) for doc in train.documents] model.fit(X_train, train.labels) X_dev = [feature_fn.transform(doc) for doc in dev.documents] predictions = model.predict(X_dev) score = MACRO_F1(predictions, dev.labels) if score > best_dev_score: best_dev_score = score best_model = model best_hyperparams = hyperparams

# Step 3: final, one-time evaluation on TEST X_test = [feature_fn.transform(doc) for doc in test.documents] test_predictions = best_model.predict(X_test) report = CLASSIFICATION_REPORT(test_predictions, test.labels) return best_model, best_hyperparams, report

function CLASSIFICATION_REPORT(predictions, gold_labels): classes = UNIQUE(gold_labels) confusion = ZERO_MATRIX(len(classes), len(classes)) for pred, gold in zip(predictions, gold_labels): confusion[INDEX(gold), INDEX(pred)] += 1 metrics = {} for c in classes: tp = confusion[INDEX(c), INDEX(c)] fp = SUM(confusion[:, INDEX(c)]) - tp # predicted c, actually not c fn = SUM(confusion[INDEX(c), :]) - tp # actually c, predicted not c precision = tp / (tp + fp) if (tp + fp) > 0 else 0 recall = tp / (tp + fn) if (tp + fn) > 0 else 0 f1 = 2 precision recall / (precision + recall) if (precision + recall) > 0 else 0 metrics[c] = (precision, recall, f1) accuracy = TRACE(confusion) / SUM(confusion) macro_f1 = MEAN([metrics[c][2] for c in classes]) return {"per_class": metrics, "accuracy": accuracy, "macro_f1": macro_f1, "confusion": confusion} ``` The `SPLIT` function should be stratified — preserving the proportion of each class in every split — so that a rare class is not accidentally absent from the validation or test set. Note the critical ordering: `feature_fn.fit` runs only on `train`, never on `dev` or `test`, so vocabulary and IDF statistics never see held-out documents.

Feature extraction. For a bag-of-words or TF-IDF representation over a vocabulary of size $|V|$, transforming a document with $L$ tokens takes $O(L)$ time (a single pass to count terms), producing a sparse vector with at most $L$ nonzero entries. Over a corpus of $N$ documents with total length $T = \sum_i L_i$, feature extraction for the whole dataset costs $O(T)$ time and $O(T)$ space if stored sparsely (dense storage would cost $O(N \cdot |V|)$, typically far larger since most documents use only a small fraction of the vocabulary).

Splitting. A stratified split over $N$ examples with $k$ classes costs $O(N)$ time: bucket examples by label ($O(N)$), then partition each bucket proportionally ($O(N)$ total across buckets). Correctness of stratification follows from a simple invariant — after splitting, for every class $c$ the fraction of class-$c$ examples in each split matches the fraction in the full dataset, up to rounding. This invariant matters because it prevents a split from asymmetrically starving a class from training or test data, which would otherwise bias the estimated per-class metrics.

Why held-out evaluation is honest. The core statistical argument is this: if the test set is drawn independently from the same distribution as future, unseen data, and the classifier's parameters were fit without ever observing the test labels, then the test accuracy is an unbiased estimate of the true generalization accuracy, with error decreasing as $O(1/\sqrt{n_{\text{test}}})$ by standard concentration bounds (e.g., a Hoeffding-style argument on the sample mean of a 0/1 correctness indicator). The moment any test example influences training — even indirectly, through vocabulary choice or hyperparameter tuning on test performance — this independence is broken, and the reported number becomes optimistically biased. This is why the pipeline enforces a strict separation: dev data may be touched many times during model development, but test data is touched exactly once.

Cross-validation's tradeoff. $k$-fold cross-validation reduces the variance of the performance estimate by averaging over $k$ different train/validation partitions, at the cost of training the model $k$ times — an explicit time-for-statistical-reliability tradeoff. As $k \to N$ (leave-one-out), the estimate becomes nearly unbiased for the "train on $N-1$ examples" regime but has high variance across folds and is often the most expensive option, since it requires up to $N$ full training runs.

Metric definitions and why accuracy misleads. Given per-class counts of true positives ($TP$), false positives ($FP$), and false negatives ($FN$):

Accuracy is $\frac{\sum_c TP_c}{N}$. Consider a spam corpus with 990 legitimate emails and 10 spam emails. A classifier that predicts "not spam" for every message achieves $99\%$ accuracy while having zero recall on the class that actually matters. Precision and recall, computed per class, expose this failure immediately: recall for the spam class is $0/10 = 0$. $F_1$ is the harmonic mean of precision and recall specifically because the harmonic mean punishes a large gap between the two — a classifier with precision $1.0$ and recall $0.01$ gets $F_1 \approx 0.02$, not the misleadingly high arithmetic mean of $0.505$. For multiclass problems, macro-averaging (unweighted mean of per-class $F_1$) treats every class equally regardless of frequency, while micro-averaging (pooling $TP$/$FP$/$FN$ across classes before computing one aggregate $F_1$) weights each example equally, so common classes dominate. The choice between them should match the actual cost structure of the application.

Consider a tiny 3-class news-topic classifier with classes `sports`, `politics`, `tech`, evaluated on a test set of 10 documents. Suppose the trained classifier produces these predictions:

Confusion matrix (rows = true, columns = predicted):

Per-class metrics: For `sports`: $TP = 2$, $FP =$ column-sum minus $TP = (2+0+1) - 2 = 1$, $FN =$ row-sum minus $TP = (2+1+0) - 2 = 1$.

For `politics`: $TP = 2$, $FP = (1+2+0) - 2 = 1$, $FN = (0+2+1) - 2 = 1$.

For `tech`: $TP = 3$, $FP = (0+1+3) - 3 = 1$, $FN = (1+0+3) - 3 = 1$.

Aggregate metrics:

Here accuracy (0.70) and macro-$F_1$ (0.695) happen to be close because classes are fairly balanced (3, 3, 4 examples) and errors are spread evenly — but this closeness is a coincidence of a balanced toy example, not a general property, as the spam example above demonstrated. If class `politics` had been only 1 example out of 100 and the classifier had ignored it entirely, accuracy could stay near $0.99$ while macro-$F_1$ would collapse toward $0.67$ once that one class's zero recall is averaged in — this is precisely the imbalance sensitivity that macro-averaging is designed to surface.

Text categorization as a statistical learning problem crystallized in the information-retrieval community, where the practical need to route, filter, and index documents at scale made hand-written rules unworkable. The formal treatment of held-out evaluation and error metrics draws directly on statistical hypothesis testing and signal-detection theory developed decades earlier, then re-purposed for text.

Every production text classifier — spam filters in email systems, content moderation pipelines flagging toxic or policy-violating posts, sentiment dashboards summarizing product reviews, language identifiers routing text to the correct downstream model, intent classifiers behind virtual assistants, and topic tags in news aggregation — relies on this same skeleton: features, a train/validation/test split, and metrics chosen to match the cost of different error types. Search engines use classification to detect query intent; e-commerce platforms use it to route customer support tickets; social platforms use it to prioritize moderation queues by predicted severity. Even as classifiers evolve from bag-of-words plus logistic regression to deep transformer encoders, the evaluation discipline described here — honest splits, stratification, precision/recall/F1 rather than raw accuracy alone — remains unchanged, because it addresses a statistical problem, not an architectural one. Understanding it is the prerequisite for evaluating any classifier correctly, including the probabilistic model introduced next, Naive Bayes for Text.

Ask the tutor: How would this evaluation pipeline change for a multilabel classification problem, where a document can carry several correct labels at once?