Logistic Regression and Text Classification

Assigning a label or category to a text or document. Examples: sentiment analysis (positive/negative orientation toward something), spam detection, language identification, and authorship attribution.

Each word of the vocabulary is a class: predicting the next word means classifying the context-so-far into one of \(|V|\) classes.

A neural network can be seen as stacked logistic regression classifiers; it introduces the sigmoid, softmax, logit and gradient descent that underlie LLMs; and it is a key analytic tool in the social and natural sciences.

Take an input observation \(x\), extract useful features, and assign it one of a fixed set of discrete classes \(Y = \{y_1, \ldots, y_M\}\).

Rules are fragile as data change, and hard to write when features interact (e.g. negation: “don’t love”). LLMs may hallucinate and may not be able to explain why they chose a class.

Learning a classifier from a labeled training set \(\{(x^{(1)}, y^{(1)}), \ldots, (x^{(m)}, y^{(m)})\}\), where each input comes with its correct output (the supervision signal), so that it maps new inputs to their correct classes.

The probability of the observation being in each class. This distribution is useful for downstream decisions; avoiding early discrete decisions helps when combining systems.

(1) A feature representation of the input; (2) a classification function computing \(P(y \mid x)\) (sigmoid or softmax); (3) an objective function to optimize, usually a loss such as cross-entropy; (4) an optimization algorithm, e.g. stochastic gradient descent.

Training: learn the weights \(w\) and bias \(b\) with SGD and the cross-entropy loss. Test: compute \(P(y \mid x)\) for each class and return the most probable label.

How important feature \(x_i\) is to the decision: positive weights give evidence for the positive class, negative weights for the negative class (e.g. awesome high positive, abysmal very negative).

A real number added to the weighted sum of the features.

\(z = \sum_i w_i x_i + b = w \cdot x + b\): the weighted sum of the evidence for the class. It ranges from \(-\infty\) to \(\infty\).

\(\sigma(z) = \frac{1}{1 + e^{-z}} = \frac{1}{1 + \exp(-z)}\). It maps any real number into (0, 1).

It maps reals to (0, 1); it is nearly linear around 0 but flattens at the ends, squashing outliers toward 0 or 1; and it is differentiable, which is handy for learning.

\(P(y=1) = \sigma(w \cdot x + b)\) and \(P(y=0) = 1 - \sigma(w \cdot x + b) = \sigma(-(w \cdot x + b))\), using \(1 - \sigma(x) = \sigma(-x)\).

The logit function is the inverse of the sigmoid: the log odds, \(\text{logit}(p) = \ln \frac{p}{1-p}\). Calling \(z = w \cdot x + b\) the logit reminds us that the sigmoid interprets it as a log odds.

The classifier’s output \(\sigma(w \cdot x + b)\): the estimated probability that the observation is in the positive class.

0.5: output class 1 if \(P(y=1 \mid x) > 0.5\), otherwise 0.

Count of positive-lexicon words, count of negative-lexicon words, whether “no” occurs, count of 1st/2nd person pronouns, whether “!” occurs, and the log of the document length.

\(z = 7.5 - 10 - 1.2 + 1.5 + 0 + 2.93 + 0.1 \approx 0.83\), so \(P(+ \mid x) = \sigma(0.83) \approx 0.70\) and \(P(- \mid x) \approx 0.30\): positive.

Negative-lexicon words count against the positive class, and each is about twice as important as a positive word.

Whether the current word is lowercase (likely EOS), whether it is in an abbreviation dictionary (likely not EOS), and combinations like “word is St. and previous word is capitalized” (likely a street name, not EOS).

Feature interactions are complex features combining primitive ones. Feature templates are abstract specifications that generate features automatically (e.g. one feature for every word bigram before a period), usually hashed to integer ids; the resulting feature space is sparse.

Designing features takes extensive human effort, so systems use representation learning: learning features automatically from the input.

Standardize: \(x_i' = \frac{x_i - \mu_i}{\sigma_i}\) (zero mean, unit standard deviation over the dataset). Normalize: \(x_i' = \frac{x_i - \min(x_i)}{\max(x_i) - \min(x_i)}\).

Features with very different ranges are hard to compare, and comparable ranges speed up gradient descent, especially in large neural networks. Count features that follow a Zipfian distribution are often log-transformed.

Stack the examples as rows of a matrix \(X\) of shape \([m \times f]\): \(\hat{y} = \sigma(Xw + b)\), with \(w\) of shape \([f \times 1]\), \(b\) the bias repeated \(m\) times, and \(\sigma\) applied element-wise. One matrix multiply replaces a for-loop.

A loss (cost) function measuring the distance between the system output \(\hat{y}\) and the gold label \(y\) (cross-entropy loss), and an optimization algorithm that iteratively updates the weights to minimize it (gradient descent).

Choosing the parameters \(w, b\) that maximize the log probability of the true labels \(y\) in the training data given the observations \(x\). The resulting loss is the negative log likelihood, i.e. cross-entropy loss.

\(p(y \mid x) = \hat{y}^{\,y}(1 - \hat{y})^{1-y}\): a Bernoulli distribution that reduces to \(\hat{y}\) when \(y = 1\) and to \(1 - \hat{y}\) when \(y = 0\).

\(L_{CE}(\hat{y}, y) = -\log p(y \mid x) = -[\,y \log \hat{y} + (1-y)\log(1-\hat{y})\,]\), with \(\hat{y} = \sigma(w \cdot x + b)\).

Positive: \(-\log 0.70 \approx 0.36\). Negative: \(-\log 0.30 \approx 1.2\). The loss is smaller when the model is right.

It goes from 0 (probability 1, no loss) to infinity (probability 0). And since the class probabilities sum to 1, raising the correct one necessarily lowers the incorrect one.

The formula is the cross-entropy between the true distribution \(y\) and the estimated distribution \(\hat{y}\).

Find the parameters \(\hat{\theta} = \arg\min_\theta \frac{1}{m}\sum_i L_{CE}(f(x^{(i)}; \theta), y^{(i)})\), with \(\theta = \{w, b\}\).

Find the direction in parameter space in which the loss rises most steeply (the gradient) and move in the opposite direction, like walking downhill along the steepest slope into a canyon.

Logistic regression’s loss is convex: it has at most one minimum and no local minima. Multi-layer network losses are non-convex, so gradient descent may get stuck in local minima.

A vector pointing in the direction of greatest increase; its components are the partial derivatives with respect to each variable. For one variable it is just the slope.

\(w^{t+1} = w^t - \eta \frac{d}{dw} L(f(x; w), y)\), where \(\eta\) is the learning rate.

It is the vector of partial derivatives \(\nabla L = [\partial L/\partial w_1, \ldots, \partial L/\partial w_n, \partial L/\partial b]\), and the update is \(\theta^{t+1} = \theta^t - \eta \nabla L(f(x; \theta), y)\).

\(\frac{\partial L_{CE}}{\partial w_j} = (\hat{y} - y)\,x_j = [\sigma(w \cdot x + b) - y]\,x_j\): the prediction error times the input value. For the bias: \(\hat{y} - y\).

An online algorithm that computes the gradient after each (randomly chosen) training example and nudges \(\theta\) in the opposite direction, rather than waiting for the whole dataset.

To 0 for logistic regression (small random values for neural networks). Stop at convergence (gradient norm below \(\epsilon\)) or when progress halts, e.g. loss goes up on a held-out set.

Too high: steps overshoot the minimum. Too low: training takes too long. Commonly it starts higher and is slowly decreased over iterations (\(\eta_k\)).

Parameters (weights, biases) are learned from the training set; hyperparameters (learning rate, regularization strength…) are chosen by the designer and affect how the algorithm works.

\(\hat{y} = \sigma(0) = 0.5\), so the gradient is \((0.5 - 1)[3, 2, 1] = [-1.5, -1.0, -0.5]\). New parameters: \(\theta - 0.1 \cdot \text{gradient} = [0.15, 0.1, 0.05]\).

Batch: gradient over the whole training set (excellent direction, slow). Stochastic: one random example at a time (fast but choppy). Mini-batch: groups of e.g. 512 or 1024 examples, which can be processed in parallel as one vectorized computation.

The average loss over the \(m\) examples, \(\text{Cost} = \frac{1}{m}\sum_i L_{CE}(\hat{y}^{(i)}, y^{(i)})\), with gradient \(\frac{1}{m}\sum_i (\hat{y}^{(i)} - y^{(i)}) x_j^{(i)}\), or in matrix form \(\frac{1}{m}(\hat{y} - y)^\top X\).

With more than two classes: 3-way sentiment, part-of-speech tags, named-entity types, or the \(|V|\)-way next-word prediction of LLMs. Also called softmax regression (older name: maxent classifier).

Each observation belongs to exactly one of the \(K\) classes.

A vector with one element equal to 1 (the correct class) and all others 0; used to represent the gold label \(y\) in multiclass classification.

For \(z = [z_1, \ldots, z_K]\): \(\text{softmax}(z_i) = \frac{\exp(z_i)}{\sum_{j=1}^{K}\exp(z_j)}\). It maps \(K\) arbitrary values to a probability distribution (each in [0, 1], summing to 1).

It squashes values toward 0 or 1: if one input is larger than the others, its probability is pushed toward 1 and the smaller inputs are suppressed. Its inputs are also called logits.

With a separate weight vector \(w_k\) and bias \(b_k\) for each class, packed into a matrix \(W\) of shape \([K \times f]\) and vector \(b\): \(\hat{y} = \text{softmax}(Wx + b)\).

The dot product acts as a similarity function, so logistic regression learns a template vector per class and assigns inputs to the class whose template they are most similar to.

Each class has its own weight for each feature, so a feature can be evidence for or against each class separately, e.g. “!” might have positive weights for + and − but a negative weight for neutral.

That a feature (with its single weight) depends on both the input and the output class, e.g. \(f_5(x, +)\), \(f_5(x, -)\), \(f_5(x, 0)\). It is used later for CRFs.

\(L_{CE}(\hat{y}, y) = -\sum_{k=1}^{K} y_k \log \hat{y}_k = -\log \hat{y}_c\): since \(y\) is one-hot, only the correct class \(c\) contributes. Hence also called the negative log likelihood loss.

\(\frac{\partial L_{CE}}{\partial w_{k,i}} = -(y_k - \hat{y}_k)\,x_i\): the difference between the true value for class \(k\) (0 or 1) and its predicted probability, times the input.

The human-defined correct labels that a system’s outputs are compared against.

A table comparing system output with gold labels, whose cells count true positives, false positives, false negatives and true negatives (for binary tasks).

	gold +	gold −
system +	true positive	false positive
system −	false negative	true negative

A classifier that labels a million tweets as “not about pie” when only 100 are about pie gets 99.99% accuracy while finding nothing. Accuracy rewards ignoring rare classes.

Precision = tp / (tp + fp): the fraction of items the system labeled positive that really are positive. Recall = tp / (tp + fn): the fraction of truly positive items the system found.

0 (0 true positives out of 100), exposing it as useless despite its accuracy.

\(F_\beta = \frac{(\beta^2 + 1)PR}{\beta^2 P + R}\); \(\beta > 1\) favors recall, \(\beta < 1\) precision. With \(\beta = 1\): \(F_1 = \frac{2PR}{P + R}\).

The harmonic mean is closer to the smaller of the two values than the arithmetic mean, so it weighs the weaker one more heavily: a conservative combination.

For class \(c\): precision = correct \(c\) / all items the system labeled \(c\) (its row); recall = correct \(c\) / all items whose gold label is \(c\) (its column).

Macroaveraging computes the metric per class and averages over classes. Microaveraging pools all decisions into one confusion matrix and computes the metric from it.

When performance on all classes matters equally: the microaverage is dominated by the most frequent class, while the macroaverage reflects small classes.

In the pooled matrix every false positive for one class is a false negative for another, so the total fp equals the total fn.

With fixed training/dev/test splits, the test or dev set may be too small to be representative. Cross-validation lets all the data be used for both training and testing.

Partition the data into \(k\) disjoint folds. For each fold, train on the other \(k-1\) folds and measure the error on that fold; average the \(k\) error rates. With \(k = 10\), 10 models are each trained on 90% of the data.

If all data is used for testing, the whole corpus must stay blind: you couldn’t look at any of it to design features without peeking at test data. A fixed test set lets you inspect the training data.

The performance difference on test set \(x\): \(\delta(x) = M(A, x) - M(B, x)\) for a metric \(M\) such as F1 or accuracy.

A might be better just by accident on this particular test set; we want to know whether the advantage would hold on other test sets.

\(H_0: \delta(x) \le 0\) (A is not better than B) and \(H_1: \delta(x) > 0\). We try to reject \(H_0\).

The probability, assuming the null hypothesis is true, of seeing a \(\delta\) as large as the one observed or larger: \(P(\delta(X) \ge \delta(x) \mid H_0)\).

When the p-value is below a chosen threshold (commonly .05 or .01), so we reject the null hypothesis.

Parametric tests assume distributions (e.g. normality) of the test statistic that usually don’t hold for NLP metrics. Non-parametric tests build a distribution by sampling many versions of the experiment.

Approximate randomization and the bootstrap test.

A comparison of two sets of aligned observations, e.g. systems A and B evaluated on the same test items, so each item’s result for A is paired with its result for B.

Repeatedly drawing samples with replacement from an observed set to create many virtual test sets. It assumes only that the sample is representative of the population; it works with any metric (accuracy, F1, BLEU…).

Create \(b\) virtual test sets of size \(n\) by sampling items of \(x\) with replacement, and compute \(\delta(x^{(i)})\) for each. Since these samples are biased toward A by \(\delta(x)\), count how often \(\delta(x^{(i)}) \ge 2\delta(x)\): \(p \approx \frac{1}{b}\sum_i \mathbb{1}(\delta(x^{(i)}) \ge 2\delta(x))\).

The bootstrap samples are drawn from \(x\), which is already biased by \(\delta(x)\) in favor of A, so their expected \(\delta\) is \(\delta(x)\), not 0. We ask how often they exceed that expectation by \(\delta(x)\) or more.

Harms caused by systems that demean a social group, e.g. by perpetuating stereotypes. Most of 200 sentiment systems assigned more negative sentiment to sentences that differed only by having a common African American first name instead of a European American one.

They falsely flag non-toxic sentences that mention identities (women, blind people, gay people) or use features of varieties like AAVE, which can silence discourse by or about these groups.

Training data (systems replicate and amplify its biases), labels (biased annotators), resources (lexicons, pretrained embeddings), and even model architecture or training objective.

Documentation released with each model version: training algorithms and parameters, training and evaluation data (sources, motivation, preprocessing), intended use and users, and performance across demographic or other groups and situations.

We can know why it reached its decision. With human-designed features, inspect each feature’s weight magnitude or test its significance (likelihood ratio test, Wald test).

To test whether a feature (e.g. negation words) is associated with an outcome (negative sentiment, hospital readmission, sales) above and beyond other variables. Potential confounds (genre, year, review length, patient age…) must be included as controls.

Weights fit the training data too perfectly, e.g. huge weights for features that happen to occur in only one class, modeling noise that accidentally correlates with the class, so the model generalizes poorly.

It adds a penalty term \(R(\theta)\) for large weights: \(\hat{\theta} = \arg\max_\theta \sum_i \log P(y^{(i)} \mid x^{(i)}) - \alpha R(\theta)\). A solution using smaller weights is preferred over one that fits slightly better with large weights; \(\alpha\) sets the strength.

Normally not: it acts as a threshold that handles uncentered data and class priors.

L2 (ridge): \(R(\theta) = \|\theta\|_2^2 = \sum_j \theta_j^2\), the squared Euclidean norm. L1 (lasso): \(R(\theta) = \|\theta\|_1 = \sum_j |\theta_j|\), the Manhattan distance.

L2 prefers many small weights and is easier to optimize (derivative \(2\theta\)). L1 prefers sparse solutions with many weights exactly zero (fewer features) but its derivative is discontinuous at 0.

L1 corresponds to a Laplace prior on the weights; L2 to a Gaussian prior with mean 0, i.e. a preference for weights near 0.

\(\frac{d\sigma(z)}{dz} = \sigma(z)(1 - \sigma(z))\)

For \(f(x) = u(v(x))\): \(\frac{df}{dx} = \frac{du}{dv} \cdot \frac{dv}{dx}\).

Differentiate \(-[y \log \sigma + (1-y)\log(1-\sigma)]\) using \(\frac{d}{dx}\ln x = \frac{1}{x}\) and the chain rule, getting \(-\big[\frac{y}{\sigma} - \frac{1-y}{1-\sigma}\big]\frac{\partial \sigma}{\partial w_j}\). Then substitute \(\frac{\partial \sigma}{\partial w_j} = \sigma(1-\sigma)x_j\); the \(\sigma(1-\sigma)\) terms cancel, leaving \(-(y - \sigma)x_j\).

In statistics (by the 1960s, especially medicine); in linguistics from the late 1970s for studying linguistic variation. NLP adopted it in the 1990s from information retrieval and speech, and at IBM under the name maximum entropy (maxent) modeling.

Removing features unlikely to generalize, by ranking them by how informative they are about the class: information gain (bits of information a word’s presence gives about the class), χ², pointwise mutual information, GINI index.