intermediate classification-sentiment 40 min read

Linear Text Classifiers: Generative vs. Discriminative

Naive Bayes and logistic regression draw the same kind of boundary through word-count space and disagree only about where to put it. They share a hypothesis class and match different moments; Zipf's long tail breaks the generative shortcut; on separable text the logistic MLE runs off to infinity while its direction settles on the maximum-margin line; and no unigram model of financial tone can see that "costs rose" is bad news

Part of the Classification & Sentiment track · View full curriculum →

Prerequisites: Zipf's and Heaps' Laws: The Statistics of Vocabulary

Overview & Motivation

Train two classifiers on $1{,}500$ synthetic financial filings labeled negative, neutral, or positive in tone, using nothing but each document’s word counts, and test them on $1{,}500$ more. Naive Bayes gets $0.601$ of the test documents right. Logistic regression, given exactly the same counts, gets $0.739$ . Both draw linear boundaries through the same space of count vectors; on this page we work out why they draw them in different places, and when that difference favors which one. Then we look at the one thing neither can see. The word “rose” gets a weight of $0.060$ from logistic regression, no more than noise among these weights, because “sales rose” is good news and “costs rose” is bad. A reader who parses every sentence could reach $0.890$ .

The Zipf topic showed that a vocabulary is mostly rare words. That fact runs through everything below. We develop it in order:

One hypothesis class. Naive Bayes is a softmax of a linear function of the counts, so it and logistic regression choose from the same family of boundaries.
Two estimating equations. They differ in which moments of the training data they reproduce.
How fast the generative side learns. Ng and Jordan’s bound, made explicit, and why it is honest but loose.
The Zipf tail. A multinomial vocabulary cannot meet that bound’s hypothesis, and the cost is polynomial in the vocabulary.
Burstiness and the crossover. When naive Bayes is the true model there is no crossover; when words come in bursts, there is.
Separation. With more words than documents the logistic MLE does not exist, and its direction does.
Naive Bayes features as a prior.

Then the finance corpus, where part of tone turns out to be an exclusive-or.

Two ways to draw one line

Take only two words, “strong” and “weak,” and plot each document as a point: how many times it says “strong” on one axis, how many times it says “weak” on the other. Most documents of every tone land exactly on the origin: $55\%$ of negative, $79\%$ of neutral, and $60\%$ of positive training documents say neither word, and so do $956$ of the $1{,}500$ test documents. The rest carry the signal, positive documents leaning along the first axis and negative ones along the second, and a classifier is a line through that plane.

Naive Bayes draws the line by modeling each class’s words. It estimates how often positive documents use “strong” and how often negative ones do, takes the log of the ratio as the word’s weight, and puts the line where the two classes’ models assign equal probability. Every word gets a vote proportional to its log ratio, whatever the other words are doing. Logistic regression draws the line directly. It moves the line until its predicted probabilities fit the labels as well as possible, and a word whose evidence the other words already carry gets less weight.

With $3{,}246$ words the plane becomes a $3{,}246$ -dimensional space, and the line a hyperplane, but the picture is the same. Both methods draw a hyperplane. The rest of this page is about where each one puts it.

One hypothesis class

We write $x \in \mathbb{N}^V$ for a document’s count vector over a vocabulary of $V$ features, $L(x) = \sum_j x_j$ for its length, and $y \in \{1, \dots, K\}$ for its class.

Definition 1 (Bag of words).

A document’s count vector $x$ has $x_j$ equal to the number of occurrences of feature $j$ , a word or, with bigrams, an adjacent pair of words. Its binarization is $\hat x_j = \mathbf{1}\{x_j \gt 0\}$ .

Multinomial naive Bayes models a document of class $k$ as $L$ independent draws from a distribution $\theta_k$ over the vocabulary, so $P(x \mid y = k) \propto \prod_j \theta_{kj}^{x_j}$ . Bernoulli naive Bayes models each feature’s presence as an independent coin with probability $\theta_{kj}$ . Both are generative: they model $x$ given $y$ and invert with Bayes’s rule.

Proposition 1 (Naive Bayes is softmax-linear).

(a) Multinomial naive Bayes has $\log P(y = k \mid x) = \log \operatorname{softmax}_k(Wx + b)$ with $W_{kj} = \log \theta_{kj}$ and $b_k = \log \pi_k$ . Bernoulli naive Bayes has the same form in $\hat x$ , with $W_{kj} = \operatorname{logit} \theta_{kj}$ and $b_k = \log \pi_k + \sum_j \log(1 - \theta_{kj})$ .

(b) For every $(W, b)$ and every length $L$ , some multinomial naive Bayes model has posterior $\operatorname{softmax}(Wx + b)$ on all documents of length $L$ . Across lengths,

\operatorname{softmax}(Wx + b) = \operatorname{softmax}\big(\tilde W x + b + L(x)\,\bar\lambda\big), \qquad \bar\lambda_k = \log \textstyle\sum_j e^{W_{kj}}, \quad \tilde W_k = W_k - \bar\lambda_k \mathbf{1},

with each row of $e^{\tilde W}$ a probability distribution. The softmax-linear family is naive Bayes’s posteriors with one more feature, the length.

Proof.

(a) By Bayes’s rule, $\log P(y = k \mid x) = \log \pi_k + \log P(x \mid y = k) - \log P(x)$ . For the multinomial, $\log P(x \mid k) = \log\big(L! / \prod_j x_j!\big) + \sum_j x_j \log \theta_{kj}$ , and the coefficient is the same for every class, so it cancels in the normalization. For the Bernoulli model, $\log P(\hat x \mid k) = \sum_j \big[\hat x_j \log \theta_{kj} + (1 - \hat x_j)\log(1 - \theta_{kj})\big] = \sum_j \hat x_j \operatorname{logit}\theta_{kj} + \sum_j \log(1 - \theta_{kj})$ .

(b) Set $\theta_k = \operatorname{softmax}(W_k)$ , so $W_k = \log \theta_k + \bar\lambda_k \mathbf{1}$ and $W_k \cdot x = \sum_j x_j \log \theta_{kj} + L(x)\,\bar\lambda_k$ . When every document has length $L$ , choose $\log \pi_k = b_k + L \bar\lambda_k$ up to a constant, and the naive Bayes posterior is $\operatorname{softmax}(Wx + b)$ . When lengths vary, $L(x)\,\bar\lambda_k$ depends on the document, so it is a feature rather than a bias.

∎

The extra feature matters. With a one-word vocabulary every document is just a length, every naive Bayes posterior is its prior, and a softmax of $w_k L + b_k$ can still use the length. The difference of the two classes’ Bernoulli weights in (a), $\operatorname{logit}\theta_{1j} - \operatorname{logit}\theta_{0j}$ , is the Robertson–Spärck Jones relevance weight, with relevance as the class (formalRAG BM25 topic, Theorem 1). The harness checks (a) against the literal Bayes rule to $10^{-9}$ and against scikit-learn to $10^{-8}$ .

Definition 2 (Generative–discriminative pair).

A generative classifier fits a model of $p(x, y)$ and predicts $\arg\max_y p(y \mid x)$ . Its discriminative partner fits $p(y \mid x)$ directly, in the parametric family that the generative model induces. Multinomial naive Bayes and softmax logistic regression on counts are such a pair.

The pairing is Ng and Jordan’s (2002), building on Rubinstein and Hastie (1997). The formalML naive-Bayes topic develops the three variants and their smoothing; here we take the pair as given and ask what distinguishes its members.

Two estimating equations

Logistic regression fits $W$ and $b$ by minimizing the average cross-entropy of $p_i = \operatorname{softmax}(Wx_i + b)$ , with a ridge penalty on the weights:

F(W, b) = \frac{1}{n}\sum_{i=1}^n \Big[\log \sum_k e^{z_{ik}} - z_{i, y_i}\Big] + \frac{\lambda}{2}\lVert W \rVert^2, \qquad z_i = Wx_i + b.

We write $y_{ik}$ for the one-hot label, $n_k$ for the number of training documents in class $k$ , and $\tilde x_i = (x_i, 1)$ .

Theorem 1 (Two estimating equations).

(a) $F$ is convex, with Hessian

\frac{1}{n}\sum_i \big(\operatorname{diag} p_i - p_i p_i^\top\big) \otimes \tilde x_i \tilde x_i^\top \;+\; \lambda\, I_K \otimes \operatorname{diag}(1, \dots, 1, 0).

At $\lambda = 0$ its null space contains every $\mathbf{1}_K \otimes v$ , a subspace of dimension $V + 1$ . At $\lambda \gt 0$ , when the $p_i$ are interior, the null space is the single direction that shifts every intercept together.

(b) At any minimizer,

\sum_i (y_{ik} - p_{ik})\, x_{ij} = n\lambda W_{kj} \quad \text{for all } k, j, \qquad \sum_i p_{ik} = n_k \quad \text{for all } k.

(c) Multinomial naive Bayes instead sets $\hat\theta_{kj} = \sum_{i:\,y_i = k} x_{ij} \big/ \sum_{i:\,y_i = k} L_i$ , which matches each class’s word totals and in general satisfies neither equation in (b).

Proof.

(a) The function $z \mapsto \log\sum_k e^{z_k}$ is convex with Hessian $\operatorname{diag} p - p p^\top$ , and $z_i = (I_K \otimes \tilde x_i^\top)\,\theta$ is linear in $\theta = (W, b)$ , so the chain rule gives the Kronecker form and each term is positive semidefinite. Since $(\operatorname{diag} p - p p^\top)\mathbf{1} = 0$ , every $\mathbf{1} \otimes v$ is in each term’s null space. With $\lambda \gt 0$ , a direction $(U, c)$ has quadratic form at least $\lambda \lVert U \rVert^2$ , which vanishes only if $U = 0$ ; then the form is $\frac1n \sum_i c^\top(\operatorname{diag} p_i - p_i p_i^\top)c$ , which vanishes only for $c \propto \mathbf{1}$ when the $p_i$ are interior.

(b) The gradient is $\partial F / \partial W_{kj} = \frac1n \sum_i (p_{ik} - y_{ik})x_{ij} + \lambda W_{kj}$ and $\partial F / \partial b_k = \frac1n \sum_i (p_{ik} - y_{ik})$ . Set both to zero.

(c) Naive Bayes maximizes the joint likelihood $\sum_i \big[\log \pi_{y_i} + \sum_j x_{ij}\log \theta_{y_i j}\big]$ subject to $\sum_j \theta_{kj} = 1$ , and stationarity of the Lagrangian gives the ratio.

∎

The first equation in (b) says that at $\lambda = 0$ the fitted model predicts, for every class and every word, exactly as many occurrences of the word in documents of the class as the training data contains. The second says the predicted class totals equal the observed ones, for every $\lambda$ : logistic regression is calibrated in the large on its training data. Naive Bayes matches a different set of moments. On the finance unigrams at $\alpha = 3$ its fitted posteriors miss the neutral and positive class totals by $22.3$ and $21.9$ documents out of $1{,}500$ , and its co-counts by up to $268$ . Much of that is the smoothing: at $\alpha = 0.001$ the largest misses are $6.4$ and $74.8$ . Logistic regression’s class totals hold to $8 \times 10^{-10}$ . Its co-counts miss by up to $8.81$ , and that gap is the penalty term $n\lambda W$ of (b) exactly; what vanishes, to $4.5 \times 10^{-8}$ , is the residual of the penalized equation.

Theorem 1 is the multiclass version of the binary logistic results in the formalStatistics GLM topic (its Theorems 1 and 2). The harness checks the gradient and Hessian against finite differences, the null-space dimensions on random instances (one with more features than documents, since (a) at $\lambda \gt 0$ needs no spanning), and agreement with scikit-learn, whose solver stops at an objective no lower than ours.

How fast the generative side learns

Ng and Jordan compare how much data each member of a pair needs to come within $\varepsilon_0$ of its own asymptotic error. Their generative side is about binary features whose rates are bounded away from $0$ and $1$ . We state it with explicit constants.

Lemma 1 (Uniform concentration of the parameters).

Take $V$ binary features and suppose each of the two classes has at least $m_0 = \lceil \ln(4V/\delta)/(2\varepsilon^2) \rceil$ training documents.

(a) Conditional on the labels, with probability at least $1 - \delta$ every estimated rate satisfies $\lvert \hat p(x_j = 1 \mid b) - p(x_j = 1 \mid b) \rvert \le \varepsilon$ .

(b) With $m \ge \ln(4/\delta)/(2\varepsilon^2)$ documents, $\lvert \hat\pi - \pi \rvert \le \varepsilon$ with probability at least $1 - \delta$ ; if $\rho_0 \le \pi \le 1 - \rho_0$ , then $m \ge m_0 / (\rho_0 - \varepsilon)$ documents give each class at least $m_0$ on that event.

(c) Add- $l$ smoothing moves each rate by at most $l / m_b$ .

Proof.

(a) Each $\hat p_{jb}$ is a mean of $m_b$ independent Bernoulli variables, so Hoeffding’s inequality gives $P(\lvert \hat p_{jb} - p_{jb} \rvert \gt \varepsilon) \le 2e^{-2\varepsilon^2 m_b}$ . A union bound over the $2V$ pairs $(j, b)$ gives at most $4V e^{-2\varepsilon^2 m_0} \le \delta$ .

(b) Hoeffding’s inequality for the labels; on its event, $m_b \ge (\pi_b - \varepsilon)m \ge (\rho_0 - \varepsilon) m$ .

(c) $\big\lvert (c + l)/(m_b + 2l) - c/m_b \big\rvert \le l / m_b$ for $0 \le c \le m_b$ .

∎

The union bound is where $\log V$ comes from: $V$ parameters cost only $\log V$ in the sample size. Ng and Jordan state this as their Lemma 3, with $m = O\big(\varepsilon^{-2}\log(V/\delta)\big)$ .

Let $l(x) = \sum_j \log\big[p(x_j \mid 1)/p(x_j \mid 0)\big] + \log\big[\pi/(1 - \pi)\big]$ be the population discriminant, $h_\infty$ its sign rule, and $\hat l$ , $\hat h$ the plug-in versions from estimated parameters. For a margin width $\tau$ , let

G(\tau) = P\big[\big(l(x) \in [0, \tau V] \wedge y = 1\big) \vee \big(l(x) \in [-\tau V, 0] \wedge y = 0\big)\big],

the probability that $h_\infty$ is right but by a margin of at most $\tau V$ .

Theorem 2 (The generative error bound).

Suppose every true rate $p(x_j = 1 \mid b)$ , and $\pi$ , lie in $[\rho_0, 1 - \rho_0]$ , and every estimate is within $\varepsilon \le \rho_0/2$ of the truth. Then

(a) $\lvert \hat l(x) - l(x) \rvert \le \tau V$ for every $x$ , with $\tau V = 4(V + 1)\varepsilon / \rho_0$ ;

(b) $\operatorname{err}(\hat h) \le \operatorname{err}(h_\infty) + G(\tau)$ .

Proof.

(a) Every true probability, for $x_j = 1$ and for $x_j = 0$ , is at least $\rho_0$ , and every estimate is within $\varepsilon \le \rho_0/2$ , so both are at least $\rho_0/2$ . By the mean value theorem, $\lvert \log \hat a - \log a \rvert \le \lvert \hat a - a \rvert / \min(\hat a, a) \le 2\varepsilon/\rho_0$ . The discriminant has $2V$ feature log terms and $2$ prior log terms, so $\lvert \hat l - l \rvert \le (2V + 2)(2\varepsilon/\rho_0)$ .

(b) If $\hat h$ errs on a document that $h_\infty$ gets right, the two discriminants have opposite signs, so $\lvert l(x) \rvert \le \lvert \hat l(x) - l(x) \rvert \le \tau V$ , and $h_\infty$ was right: that is the event that $G$ measures.

∎

With Lemma 1, $\varepsilon = O\big(\sqrt{\log(V/\delta)/m}\big)$ , so $\tau = O\big(\sqrt{\log V / m}\big)$ , which is Ng and Jordan’s Theorem 4. If $G(\tau) \le \varepsilon_0/2 + F(\tau)$ for some $F$ with $F(\tau) \to 0$ , then $m = O(\log V)$ documents bring naive Bayes within $\varepsilon_0$ of its asymptotic error (their Corollary 6). The discriminative side we cite. Half-spaces in $\mathbb{R}^V$ have VC dimension $V + 1$ (formalML VC-dimension topic, Theorem 6), which gives their Proposition 2: the discriminative classifier comes within $O\big(\sqrt{(V/m)\log(m/V)}\big)$ of its asymptotic error, and needs $m = \Omega(V)$ documents in the worst case. Their Proposition 1 adds that the discriminative classifier’s asymptotic error is never worse. Both concern the classifier that minimizes training 0-1 error over half-spaces; logistic regression’s MLE is a convex stand-in for it.

How loose is it? The harness builds a world where Bernoulli naive Bayes is exactly true: $V = 200$ features, rates clipped to $[0.1, 0.9]$ , $\varepsilon = 0.05$ , $\delta = 0.2$ . Lemma 1 asks for $m_0 = 1{,}659$ documents per class. In $40$ draws of that size no parameter was ever off by more than $\varepsilon$ , and the largest deviation’s $0.8$ quantile was $0.040$ . Theorem 2’s margin is $\tau V = 402$ nats. The largest gap between $\hat l$ and $l$ on any test document in any draw was $2.15$ nats, and the median $\lvert l \rvert$ is $1.63$ . With a margin of $402$ , $G(\tau)$ is every correctly classified document, and the bound says nothing. A margin of one nat would take $2.7 \times 10^8$ documents per class. Most of the slack is in the size of each term, not in their signs. The proof charges every log term $2\varepsilon/\rho_0 = 1$ nat, while the real terms have median $0.013$ and maximum $0.17$ . With those sizes and every sign aligned, the worst test document reaches $8.0$ nats, a factor of $50$ below $402$ , and the worst document anyone could build reaches $12.3$ ; letting the signs cancel takes off a further factor of $4.4$ . The sample size it predicts grows the right way in $V$ , but the constants make it vacuous at any realistic size.

Multinomial counts and the Zipf tail

Theorem 2 needs every rate to be at least $\rho_0$ : Lemma 1 has no such hypothesis, but Theorem 2’s log terms blow up near zero. A multinomial vocabulary cannot have that: its rates sum to $1$ , so some word has $\theta_j \le 1/V$ , and under Zipf’s law most words are far rarer.

Theorem 3 (Relative accuracy costs the rarest word).

Let a class’s $N$ training tokens be independent draws from $\theta \in \Delta^V$ , and let $\hat\theta = C/N$ be the empirical rates. Fix $\varepsilon \in (0, 1/2]$ .

(a) If $N \ge 3\ln(2V/\delta)/(\varepsilon^2 \theta_{\min})$ , then with probability at least $1 - \delta$ every $\lvert \hat\theta_j / \theta_j - 1 \rvert \le \varepsilon$ . Then every $\lvert \log\hat\theta_j - \log\theta_j \rvert \le 2\varepsilon$ . If each of two classes has that many tokens, then with probability at least $1 - 2\delta$ a document’s discriminant moves by at most $4\varepsilon L$ .

(b) If $N \le 1/(2\theta_{\min})$ , the rarest word is unseen with probability at least $1/2$ , and its relative error is $1$ . So relative accuracy for every word needs more than $1/(2\theta_{\min}) \ge V/2$ tokens.

(c) Under Zipf( $s$ ), $\theta_{\min} = V^{-s}/H_{V,s}$ , so (a) asks for a number of tokens that grows like $V^s H_{V,s} \log V$ : polynomially in $V$ , not logarithmically.

Proof.

(a) The multiplicative Chernoff bound gives $P\big(\lvert C_j - N\theta_j \rvert \ge \varepsilon N\theta_j\big) \le 2e^{-\varepsilon^2 N\theta_j/3}$ , and a union bound over $V$ words with $\theta_j \ge \theta_{\min}$ gives at most $2V e^{-\varepsilon^2 N \theta_{\min}/3} \le \delta$ . For $\varepsilon \le 1/2$ , $-\log(1 - \varepsilon) \le \varepsilon/(1 - \varepsilon) \le 2\varepsilon$ and $\log(1 + \varepsilon) \le \varepsilon$ . A union bound over the two classes’ events gives $1 - 2\delta$ , and on both the discriminant $\sum_j x_j(\log\hat\theta_{1j} - \log\hat\theta_{0j})$ moves by at most $\sum_j x_j \cdot 4\varepsilon = 4\varepsilon L$ .

(b) $P(C_{\min} = 0) = (1 - \theta_{\min})^N \ge 1 - N\theta_{\min} \ge 1/2$ .

(c) Zipf( $s$ ) gives word $j$ probability $j^{-s}/H_{V,s}$ , the law of the Zipf topic, and the last word has the smallest.

∎

In the long-tailed world of the next section ( $V = 3{,}071$ words, rates in proportion to the corpus’s), $\theta_{\min}$ is $4.8 \times 10^{-6}$ , and part (a) at $\varepsilon = 1/2$ , $\delta = 0.1$ asks for $27.7$ million tokens per class. A uniform vocabulary of the same size would need $0.41$ million, and a pure Zipf(1.1) vocabulary $5.5$ million. Training on $4{,}096$ documents supplies $0.44$ million tokens per class and leaves about $67$ words never seen.

The bound is sufficient, not necessary, because rare words are rare in test documents too. The share of test tokens whose word occurred fewer than five times in training falls from $0.104$ at $64$ training documents to $0.028$ at $512$ and $0.0018$ at $4{,}096$ . What the long tail does change is the smoothing. When the smoothing strength $\alpha$ is chosen on validation data, its median choice in the $3{,}071$ -word world rises unevenly, from under $1$ through $n = 64$ to $20$ at $n = 4{,}096$ , on a grid that stops at $30$ , while in a $101$ -word world it stays between $0.1$ and $0.65$ . More data does not mean more words seen once. Pooled across classes, words seen exactly once peak near $650$ at $n = 256$ and are down to about $30$ at $n = 4{,}096$ ; within one class they peak near $600$ at $n = 1{,}024$ and fall to $160$ , while $\alpha$ is still rising. What changes is what shrinkage costs. At $n = 256$ , raising $\alpha$ from $1$ to $10$ gains $0.063$ of validation accuracy by shrinking the noise words, and loses $0.052$ by flattening the informative words and $0.103$ because $\alpha V$ pseudo-tokens turn a small difference between the classes’ token totals into a bias that grows with a document’s length. At $n = 4{,}096$ those costs are $0.006$ and $0.002$ , and the gain is still $0.024$ .

Burstiness and the crossover

Ng and Jordan’s two results predict two regimes. Naive Bayes approaches its asymptote faster, so it should lead early. Logistic regression has the better asymptote, so it should lead late if the two asymptotes differ. When naive Bayes is the true model they do not differ, and the prediction is no crossover at all.

Real words also come in bursts: a filing that mentions “impairment” once tends to mention it again. (The synthetic corpus does not do this: “impairment” occurs $30$ times in $29$ of its $1{,}500$ training documents. So we build bursts into simulated worlds.) Model it in the simplest way: draw an underlying count vector $u$ from naive Bayes, and observe $x = r \odot u$ , where each word’s occurrences repeat $r_j \ge 1$ times.

Proposition 2 (Bursts keep logistic regression right and can move naive Bayes's asymptote).

Let $u \sim \operatorname{Multinomial}(L, \theta_y)$ with $L$ independent of $y$ , and observe $x = r \odot u$ for fixed $r_j \ge 1$ .

(a) $P(y \mid x) = \operatorname{softmax}_y\big(\sum_j (x_j/r_j)\log\theta_{yj} + \log\pi_y\big)$ , which is linear in $x$ . Softmax logistic regression contains the true conditional, and its population error is the Bayes error.

(b) Multinomial naive Bayes fit to infinitely many such documents converges to $\tilde\theta_k = r \odot \theta_k / Z_k$ with $Z_k = \sum_j r_j\theta_{kj}$ . Its weight per observed count is $\log(\theta_{1j}/\theta_{0j}) + \log(Z_0/Z_1)$ : per underlying occurrence, $r_j$ times the Bayes weight, plus a term in the length. Its asymptotic error is generally above the Bayes error.

(c) If $r_j = c$ for every word with $\theta_{1j} \ne \theta_{0j}$ , then $Z_0 = Z_1$ , and naive Bayes’s limiting weights are $c$ times the Bayes weights per observed count. With $\pi = 1/2$ its limiting rule is the Bayes rule, whatever $r$ does on the other words.

Proof.

(a) $u = x / r$ is a function of $x$ , so $P(y \mid x) = P(y \mid u)$ , which Proposition 1(a) writes as a softmax of $\sum_j u_j \log\theta_{yj} + \log\pi_y$ .

(b) By the law of large numbers, $\hat\theta_{kj} \to \mathbb{E}[x_j \mid k] / \mathbb{E}[L(x) \mid k] = r_j \theta_{kj}\mathbb{E}[L] / (\mathbb{E}[L]\, Z_k)$ .

(c) Let $S$ be the set of words with unequal rates. Since $\sum_{j \in S} \theta_{kj} = 1 - \sum_{j \notin S} \theta_{kj}$ is the same for both classes, so is $Z_k = c\sum_{j \in S} \theta_{kj} + \sum_{j \notin S} r_j\theta_{kj}$ . The weight in (b) is then $\log(\theta_{1j}/\theta_{0j})$ , which is $0$ off $S$ and $c$ times the weight $(1/r_j)\log(\theta_{1j}/\theta_{0j})$ of (a) on $S$ . With $\pi = 1/2$ neither discriminant has a prior term, so one is $c$ times the other and they have the same sign.

∎

The harness builds four worlds from the corpus. In each, $71$ informative words (the sentiment lexicon, the direction words, and “not”) have class-dependent rates taken from the corpus and hold $6.2\%$ of every document. The rest of each document is spread over uninformative words in proportion to their corpus frequencies: $30$ of them ( $V = 101$ ) or $3{,}000$ ( $V = 3{,}071$ ). In the bursty worlds a fixed half of the words repeat four times, including $34$ of the $71$ informative ones. All four worlds have one Bayes accuracy, $0.854$ on a million documents: the bursts are a deterministic relabeling, and words whose rates do not depend on the class cannot change it. Naive Bayes’s asymptote in the bursty worlds is $0.816$ at $V = 101$ and $0.815$ at $V = 3{,}071$ . Each method’s hyperparameter, the smoothing $\alpha$ for naive Bayes and the penalty $\lambda$ for logistic regression, is chosen for every fit on a fresh validation draw, and each curve averages four nested training draws.

Naive Bayes true, $V = 101$ : naive Bayes leads at every training size and reaches $0.852$ at $4{,}096$ documents, against $0.848$ . No crossover.
Naive Bayes true, $V = 3{,}071$ : again no crossover; at $4{,}096$ documents naive Bayes has $0.831$ and logistic regression $0.811$ .
Bursty, $V = 101$ : naive Bayes leads until $512$ documents, and logistic regression leads from there on, finishing at $0.849$ , past naive Bayes’s asymptote; naive Bayes finishes at $0.817$ .
Bursty, $V = 3{,}071$ : the crossover moves out to $2{,}048$ documents, and at $4{,}096$ logistic regression has $0.790$ and naive Bayes $0.772$ .

Do the two regimes appear exactly where the asymptotic errors differ? No. Proposition 2(c) says overcounting alone costs nothing. Repeat every word four times, or all $71$ informative words and nothing else, and naive Bayes’s asymptote stays at the Bayes accuracy, because every weight that matters scales by one factor. That needs balanced classes: at $\pi = 0.3$ the score scales and the prior does not, and uniform bursts cost $0.010$ . What costs the asymptote is unevenness among informative words. Let every other informative word burst and nothing else, so that some signal words get four votes and others one, and the asymptote falls to $0.809$ .

The crossover does not need that. Let only the noise words burst. Their log ratios are zero, so by (c) naive Bayes’s asymptote is exactly the Bayes accuracy, and there is no gap. Logistic regression overtakes it anyway, winning all four draws from $n = 256$ at $V = 101$ and from $n = 1{,}024$ at $V = 3{,}071$ , sooner than the $1{,}024$ and $4{,}096$ of the half-informative worlds, where the gap exists. A noise word’s fitted weight is small and wrong, and a burst gives it four votes at test time. Naive Bayes’s weight is a log ratio of rates and cannot see the four: at $n = 256$ the noise words’ part of its score grows fourfold, from a standard deviation of $0.73$ to $2.92$ . Logistic regression refits. By Proposition 3(a) with $r = 4$ , repeating a word four times divides its weight by about four ( $3.73$ , $3.96$ , $3.99$ at $\lambda = 0.1$ , $0.01$ , $0.001$ , and exactly $4$ at $\lambda = 0$ ), so that part of its score barely moves, from $1.21$ to $1.27$ . At $V = 101$ the two meet again by $n = 32{,}768$ , as equal asymptotes predict; at $V = 3{,}071$ logistic regression still wins all four draws there.

So a gap between asymptotes is one way to get Ng and Jordan’s two regimes, not the only one. The other is a difference in how each method pays for noise it has not yet averaged out. Choose the world and the vocabulary in the laboratory.

A · Crossover — naive Bayes leads early; where words come in bursts, logistic regression overtakes it

training documents n512

naive Bayeslogistic regressionBayes accuracy

naive Bayes at n = 512

0.832

logistic regression at n = 512

0.795

Bayes accuracy

0.854

naive Bayes asymptote

0.854

crossover n

none

When naive Bayes is the true model, its asymptote is the Bayes accuracy and it leads at every n shown. When half the words come in bursts of four, logistic regression stays well specified. Naive Bayes loses asymptote because the bursts hit some informative words and not others (Proposition 2), and its noise words get four votes each until it has averaged them out. A gap in asymptotes is not required: on the page, bursts on noise words alone produce a crossover with no gap at all.

Separation

The finance corpus has $1{,}500$ training documents and $3{,}246$ unigram features, $17{,}706$ with bigrams. With more features than documents, a hyperplane can usually separate the training classes perfectly, on either feature set: the unigram count matrix has rank $1{,}500$ . That changes what logistic regression’s fit means. We use the homogeneous model here (no intercept), write $z_i = s_i x_i$ for a document times its label $s_i \in \{\pm 1\}$ , and let

\ell(w) = \frac{1}{n}\sum_i \log\big(1 + e^{-z_i \cdot w}\big), \qquad F_\lambda(w) = \ell(w) + \frac{\lambda}{2}\lVert w \rVert^2 .

Theorem 4 (Separation, the missing MLE, and the max-margin limit).

(a) If some $\bar w$ has $z_i \cdot \bar w \gt 0$ for every $i$ , then $\inf \ell = 0$ and no $w$ attains it; $\nabla\ell(w)\cdot\bar w \lt 0$ at every $w$ , so $\ell$ has no stationary point. For $\lambda \gt 0$ , $F_\lambda$ has a unique minimizer $\hat w_\lambda$ .

(b) If the $x_i$ are linearly independent, which needs $n \le V$ , every labeling is separable.

(c) Let $\hat w = \arg\min \lVert w \rVert^2$ subject to $z_i \cdot w \ge 1$ for all $i$ , the hard-margin SVM, which is unique, and let $u^* = \hat w / \lVert \hat w \rVert$ and $\gamma^* = 1/\lVert \hat w \rVert$ . As $\lambda \to 0$ , $\lVert \hat w_\lambda \rVert \to \infty$ , $\min_i z_i \cdot \hat w_\lambda / \lVert \hat w_\lambda \rVert \to \gamma^*$ , and $\hat w_\lambda / \lVert \hat w_\lambda \rVert \to u^*$ .

Proof.

(a) Along $t\bar w$ every margin grows, so $\ell(t\bar w) \to 0$ as $t \to \infty$ , while $\ell \gt 0$ everywhere. The directional derivative $\nabla\ell(w)\cdot\bar w = -\frac1n\sum_i \sigma(-z_i\cdot w)\, z_i\cdot\bar w$ is negative. $F_\lambda$ is strictly convex and grows without bound, so it has exactly one minimizer.

(b) The map $w \mapsto Xw$ from $\mathbb{R}^V$ onto $\mathbb{R}^n$ is surjective, so $Xw = s$ has a solution for any sign vector $s$ , and then $z_i \cdot w = s_i^2 = 1$ .

(c) Write $\hat w_\lambda = \rho_\lambda u_\lambda$ with $\lVert u_\lambda \rVert = 1$ , and $\gamma_\lambda = \min_i z_i \cdot u_\lambda$ .

The norm grows without bound. Fix $R$ . On the ball $\lVert w \rVert \le R$ , $F_\lambda \ge c_R = \min_{\lVert w \rVert \le R} \ell(w) \gt 0$ . Since $\log(1 + e^{-m}) \le e^{-m}$ , $F_\lambda(R' u^*) \le e^{-R'\gamma^*} + \lambda R'^2/2$ , which is below $c_R$ for $R'$ large and then $\lambda$ small. So eventually $\hat w_\lambda$ lies outside the ball.

Compare at equal norm. $F_\lambda(\hat w_\lambda) \le F_\lambda(\rho_\lambda u^*)$ and the penalties are equal, so $\ell(\rho_\lambda u_\lambda) \le \ell(\rho_\lambda u^*) \le e^{-\rho_\lambda \gamma^*}$ .

The margin is eventually positive. If $\gamma_\lambda \lt 0$ , one term of $\ell(\rho_\lambda u_\lambda)$ is at least $\log 2$ , so $\ell \ge \log 2 / n$ , which exceeds $e^{-\rho_\lambda\gamma^*}$ once $\rho_\lambda$ is large.

The margin approaches the maximum. For $m \ge 0$ , $\log(1 + e^{-m}) \ge e^{-m}/2$ , so $\frac{1}{2n}e^{-\rho_\lambda\gamma_\lambda} \le e^{-\rho_\lambda\gamma^*}$ , which gives $\gamma_\lambda \ge \gamma^* - \ln(2n)/\rho_\lambda \to \gamma^*$ .

The direction converges. Every limit point $\bar u$ of $u_\lambda$ on the unit sphere has $\min_i z_i \cdot \bar u \ge \gamma^*$ , so it is a max-margin direction, and by uniqueness $\bar u = u^*$ . A bounded sequence whose every convergent subsequence has the same limit converges to it.

∎

Part (c) is Rosset, Zhu, and Hastie’s (2004) Theorem 2.1 for the logistic loss with the squared $L_2$ penalty; their JMLR paper proves the same limit along the constrained path $\lVert w \rVert \le c$ . Albert and Anderson (1984) classify when the MLE exists; part (a) is the complete-separation case. Cover’s (1965) function-counting theorem gives (b) its exact form: $n$ points in general position in $\mathbb{R}^d$ admit all $2^n$ homogeneous labelings exactly when $n \le d$ .

The harness takes the $200$ polar tone documents of a $300$ -document corpus, with $2{,}738$ words. Their count vectors have full rank, so every labeling is separable, and a linear program confirms it for the true labels and three random ones. The SVM normalized margin is $\gamma^* = 0.692$ . As $\lambda$ falls from $10^{-1}$ to $10^{-7}$ the norm $\lVert \hat w_\lambda \rVert$ runs from $1.541$ to $18.005$ , the cosine to the SVM direction rises from $0.930$ to $0.998$ , and the normalized margin from $0.032$ to $0.645$ . The last decade of $\lambda$ adds $3.047$ to the norm, near $\ln 10 / \gamma^* = 3.326$ , as $\lVert \hat w_\lambda \rVert \approx \ln(1/\lambda)/\gamma^*$ would predict.

Unregularized gradient descent does the same thing with time in place of $\lambda$ . Soudry and colleagues (2018, Theorems 3 and 5) prove that on separable data, from any start and with a small enough step, $w(t)$ grows like $\hat w \log t$ and its direction converges to the max-margin direction, at rate $O(\log\log t / \log t)$ . From $w = 0$ on the tone documents, the cosine to the SVM direction is $0.591$ after $10$ steps, $0.906$ after $1{,}000$ , and $0.987$ after $100{,}000$ , while the loss falls to $0.0025$ . The laboratory plots both paths. A logistic regression on separable text that reports its weights is reporting how long it ran; only the direction is a fact about the data, and the margin bound of the formalML generalization topic (Theorem 6) is why that direction is a good one.

Naive Bayes features as a prior

Wang and Manning (2012) reuse naive Bayes inside a discriminative model. Their log-count ratio for a binary task is

r = \log\frac{p / \lVert p \rVert_1}{q / \lVert q \rVert_1}, \qquad p = \alpha + \sum_{i:\,y_i = 1} f_i, \quad q = \alpha + \sum_{i:\,y_i = 0} f_i,

naive Bayes’s weight vector for features $f$ , and their NBSVM fits a linear model to $r \odot f$ .

Proposition 3 (Naive Bayes weights as a prior).

(a) Let every $r_j \ne 0$ . Logistic regression on the features $r \odot x$ with penalty $\frac{\lambda}{2}\lVert v \rVert^2$ has the same decision function as logistic regression on $x$ with penalty $\frac{\lambda}{2}\sum_j w_j^2 / r_j^2$ , through $w = r \odot v$ .

(b) For raw counts with class totals $N_1$ , $N_0$ , and word totals $c_j = c_{0j} + c_{1j}$ ,

\lvert r_j \rvert \le \ln\frac{c_j + \alpha}{\alpha} + \Big\lvert \ln\frac{N_1 + \alpha V}{N_0 + \alpha V} \Big\rvert .

Proof.

(a) The substitution $w = r \odot v$ is a bijection that leaves every score $x \cdot w = (r \odot x)\cdot v$ unchanged and sends $\lVert v \rVert^2$ to $\sum_j w_j^2/r_j^2$ .

(b) $r_j = \ln\frac{c_{1j} + \alpha}{c_{0j} + \alpha} + \ln\frac{N_0 + \alpha V}{N_1 + \alpha V}$ , and since $0 \le c_{kj} \le c_j$ , the first ratio lies between $\alpha / (c_j + \alpha)$ and $(c_j + \alpha)/\alpha$ .

∎

Part (a) is a Gaussian prior with a different variance for each word, set by naive Bayes: $F$ averages its loss, so against the summed log likelihood the penalty is a prior of variance $r_j^2/(n\lambda)$ (formalStatistics regularization topic). A word that naive Bayes finds uninformative gets a tight prior around zero, and a word it finds strongly polar is free to move. Part (b) is the funnel in the laboratory. On the $1{,}000$ polar training documents ( $6{,}307$ words), the most extreme log ratio of any word seen once is $2.408$ at $\alpha = 0.1$ , $0.703$ at $\alpha = 1$ , and $0.102$ at $\alpha = 10$ , each exactly the bound. Smoothing caps what a rare word can say, and under Zipf most words are rare. Add- $\alpha$ smoothing is a posterior mean under a symmetric Dirichlet prior (formalStatistics multivariate topic, Theorem 6). The formalRAG query-likelihood topic smooths toward a background distribution instead.

The aspect exclusive-or

The finance corpus writes its tone into $5$ to $8$ aspect sentences per document. Each sentence names an aspect (revenue, margins, demand, liquidity, costs, taxes, liabilities) and says what happened to it. For revenue, up is good news; for costs, up is bad.

Proposition 4 (Valence times direction is not linear in unigrams).

On the four one-clause documents “revenue rose” (positive), “revenue fell” (negative), “costs rose” (negative), and “costs fell” (positive), no $(w, b)$ separates the labels using unigram counts. Bigram indicators separate them.

Proof.

Suppose $(w, b)$ separates them. The positive documents give $w_{\text{revenue}} + w_{\text{rose}} + b \gt 0$ and $w_{\text{costs}} + w_{\text{fell}} + b \gt 0$ , whose sum is $S = w_{\text{revenue}} + w_{\text{costs}} + w_{\text{rose}} + w_{\text{fell}} + 2b \gt 0$ . The negative documents give $w_{\text{revenue}} + w_{\text{fell}} + b \lt 0$ and $w_{\text{costs}} + w_{\text{rose}} + b \lt 0$ , whose sum is the same $S \lt 0$ . With bigram indicators, weight $+1$ on “revenue rose” and “costs fell” and $-1$ on the other two separates them.

∎

This is the exclusive-or that a single hyperplane cannot draw, and the corpus shows its signature. In the unigram fit, logistic regression gives “rose” a weight of $0.060$ and “fell” $0.024$ (positive minus negative). That is noise, not zero: the weights have standard deviation $0.092$ and median magnitude $0.031$ , which puts “rose” in about the top quarter, but no direction word gets past it and their signs follow no pattern, because the words cancel across aspects. The bigram fit puts the sign on the pairs:

bigram	weight
costs rose	$-0.355$
costs fell	$0.526$
taxes rose	$-0.351$
sales rose	$0.265$
revenue rose	$0.001$
not strong	$-0.199$
not weak	$0.336$

“Revenue rose” is the row that fails, and instructively: $45$ of its $71$ training occurrences sit inside “cost of revenue rose,” an exclusive-or one word wider than a bigram. Negation is the same kind of interaction: “not” flips the adjective after it, and “not weak” is positive.

§ Finance case study: tone in synthetic filings

The ceiling. Each document has $k$ aspect sentences, $k$ uniform on $5$ to $8$ , whose polarities are independent draws from a mixture that depends on the tone. Nothing else in a document depends on its tone, so the counts of positive, neutral, and negative sentences are sufficient, and the Bayes accuracy is an exact sum over them: $0.890$ . That is the accuracy of a reader who recovers every sentence’s polarity, which the corpus’s templates make possible.

The classifiers. Train on $1{,}500$ documents, choose each hyperparameter on $600$ more, test on $1{,}500$ , all three tones. The NB-weighted model is the one of Proposition 3(a), one-versus-rest: for each tone, logistic regression on binarized features scaled by that tone’s log-count ratio against the others (Wang and Manning’s NBSVM uses a squared hinge loss and an interpolation we leave out).

method	features	accuracy	confidence	ECE
naive Bayes	unigrams	$0.601$	$0.899$	$0.301$
naive Bayes	bigrams	$0.694$	$0.962$	$0.270$
logistic regression	unigrams	$0.739$	$0.780$	$0.046$
logistic regression	bigrams	$0.771$	$0.869$	$0.099$
NB-weighted	unigrams	$0.719$	$0.728$	$0.029$
NB-weighted	bigrams	$0.776$	$0.796$	$0.027$

Confidence is the mean top probability and ECE the 15-bin expected calibration error of the calibration topic. Logistic regression beats naive Bayes by $0.138$ on unigrams and $0.077$ on bigrams.

Those rows use grids that stop at what they select: $\alpha$ up to $3$ and $\lambda$ of $0.01$ or $0.001$ . $\alpha = 3$ is the top of its grid and wins on all six of the splits we ran; $\lambda = 0.01$ is the top of its grid and wins on unigrams, where a wider grid keeps it. On wider grids the tuning set picks $\alpha = 100$ here, which gives naive Bayes $0.615$ on unigrams (confidence $0.817$ , ECE $0.203$ ) and moves its six-split mean from $0.607$ to $0.617$ . Logistic regression on bigrams moves to $\lambda = 0.003$ , with ECE $0.073$ and the same accuracy, and the NB-weighted model goes to $0.709$ on unigrams and $0.777$ on bigrams. The ranking of the three methods does not change, so the table and the laboratory keep the short grids; “wide grid” below means the longer ones.

What bigrams add. Bigrams help every method, though mostly not by Proposition 4’s route. Over six splits the $84$ bigrams that pair an aspect word with a direction word give logistic regression $0.012$ of the $0.039$ that all bigrams give, and adding the $16$ “not” bigrams brings it to $0.021$ . The generator says why: only $6.1\%$ of aspect sentences carry their polarity on a direction word alone, while $40.5\%$ have an evaluative word that agrees with it.

How much of the ceiling is a wall? Nothing above comes within $0.11$ of $0.890$ . Contrast sentences are not most of the reason. Here is one from the test corpus: “Taxes declined 7 percent in quotalines, but lease liabilities rose 14 percent in equityflow, a trend executives characterized as weaker.” Its polarity is its first clause’s, and no bag of n-grams can make the second clause stop counting. But a reader who gets everything else right and cannot tell which clause counts has an exact Bayes accuracy of $0.873$ , only $0.017$ below the ceiling. Verbs cost more: a cost that “exceeded expectations” is bad news in a good-news word ( $3.6\%$ of aspect sentences), and a reader who also sees such a verb only as a word falls to $0.861$ . One who further cannot read a bare direction word and takes “not strong” at face value ( $3.1\%$ ) falls to $0.816$ . And most of the distance was data. Train past $1{,}500$ documents by concatenating independent corpora, tune on $3{,}000$ , and test on $9{,}000$ , in one run:

$n$	all unigrams	best $200$ unigrams by chi-squared	bigrams	naive Bayes, unigrams
$1{,}500$	$0.735$	$0.781$	$0.770$	$0.596$
$15{,}000$	$0.787$	$0.798$	$0.826$	$0.704$
$50{,}000$	$0.792$	$0.798$	$0.847$	$0.741$

Unigrams level off near $0.80$ : they cannot see the exclusive-or, the negation, or the verb. At $1{,}500$ documents the best $200$ of them still beat all the bigrams. Bigrams keep climbing, to within $0.043$ of the ceiling and $0.026$ of the contrast-blind reader. These corpora share no content words, so take the direction rather than the digits.

No crossover here. Train on the first $n$ documents, on the full vocabulary, with the hyperparameter each method chose on all $1{,}500$ :

$n$	naive Bayes	logistic regression
$30$	$0.324$	$0.460$
$100$	$0.437$	$0.515$
$300$	$0.517$	$0.620$
$1{,}000$	$0.602$	$0.723$
$1{,}500$	$0.601$	$0.739$

That table borrows from the full fit. Retune at each $n$ , on the vocabulary of those $n$ documents and the wide grids, over six splits:

$n$	$8$	$16$	$30$	$60$	$100$	$300$
naive Bayes	$0.380$	$0.366$	$0.419$	$0.449$	$0.461$	$0.524$
logistic regression	$0.373$	$0.383$	$0.461$	$0.500$	$0.540$	$0.620$

Logistic regression wins all six splits from $n = 60$ up. Below that it is close to a coin flip: at $n = 8$ , where only four splits have all three tones, it wins two.

Why does the early lead the theory allows not show? Most of each document is company names, products, and Pitman–Yor content words that carry no tone, thousands of them. Naive Bayes gives each one a log ratio fit to noise and adds them all up. Logistic regression shrinks them, though not all the way: on the $50$ best words by chi-squared it scores $0.777$ against $0.734$ on all $3{,}246$ , and the gap to naive Bayes falls from $0.117$ to $0.022$ . The loss is estimation among clustered words more than a distant asymptote. Keep each document’s token counts and redraw its content words independently, and over four splits naive Bayes goes from $0.621$ to $0.689$ while logistic regression stays near $0.73$ ; the gap falls from $0.116$ to $0.041$ . Redraw every word, and the order reverses, $0.840$ against $0.820$ . Naive Bayes is also still climbing at $50{,}000$ documents, as the table above shows. Take the noise words away and the early lead appears: on $106$ tone, aspect, and neutral words naive Bayes wins every split through $n = 300$ , $0.735$ against $0.709$ there.

Calibration. Naive Bayes is overconfident by $0.30$ on unigrams: words co-occur, and it counts their evidence as if independent, the failure Niculescu-Mizil and Caruana (2005) document. The template words are only about half of what co-occurs. Redraw word groups independently as above, at $\alpha = 3$ over six splits, and ECE is $0.297$ on real text, $0.191$ with the content words redrawn, $0.191$ with the template words redrawn, and $0.058$ with both: company and sector words travel together too. The vocabulary agrees. On the generator’s $99$ tone and aspect words naive Bayes has ECE $0.027$ , on those plus seven neutral-phrase words $0.069$ , and on all words $0.250$ .

Logistic regression’s calibration is set by its penalty, not by Theorem 1 and not by its features. The class-total equation holds at every $\lambda$ , including $\lambda = 0.001$ , where the six-split unigram ECE is $0.147$ . The bigram training set is separable, but so is the unigram one, and unigram training accuracy is $1.000$ at $\lambda = 0.001$ . Over six splits, at equal $\lambda$ bigrams are the better calibrated from $\lambda = 0.01$ down:

$\lambda$	unigram ECE	unigram accuracy	bigram ECE	bigram accuracy
$0.03$	$0.033$	$0.739$	$0.035$	$0.772$
$0.01$	$0.048$	$0.733$	$0.034$	$0.773$
$0.003$	$0.106$	$0.723$	$0.072$	$0.773$
$0.001$	$0.147$	$0.718$	$0.098$	$0.772$

The table’s bigram overconfidence, $0.869$ against $0.771$ , is the $\lambda$ this split’s accuracy grid picked. Bigram accuracy is flat across that range, and the grid chose $0.001$ on two of six splits, this one among them, and $0.01$ on the other four. Choose $\lambda$ by dev log loss instead and ECE is $0.033$ on both feature sets, with accuracy $0.739$ and $0.772$ . On separable text the penalty sets the confidence, so a penalty meant to give good probabilities has to be chosen by a score that reads them.

Label noise. Flip a share of the training labels to another tone at random, keep the test labels clean:

noise	naive Bayes	logistic regression	NB-weighted
$0$	$0.601$	$0.739$	$0.719$
$0.15$	$0.526$	$0.660$	$0.689$
$0.30$	$0.510$	$0.584$	$0.598$

That table is one stream of flips, which happened to draw $16.9\%$ and $31.1\%$ . Over six streams, with the standard deviation across them:

noise	naive Bayes	logistic regression	logistic regression, wide grid	NB-weighted, wide grid
$0.15$	$0.569$ $(0.026)$	$0.674$ $(0.016)$	$0.690$ $(0.012)$	$0.688$ $(0.010)$
$0.30$	$0.533$ $(0.017)$	$0.594$ $(0.016)$	$0.637$ $(0.008)$	$0.626$ $(0.019)$

Logistic regression stays ahead of naive Bayes at every level. Its table grid stops at $\lambda = 0.01$ , though, and noisier labels want more penalty: the tuned $\lambda$ is $0.03$ to $0.3$ . On the wide grid logistic regression and the NB-weighted model tie within their spread. Every hyperparameter here is chosen on clean dev labels, which real noisy data would not offer. The real EDGAR excerpts carry no tone labels, so they appear in none of these numbers.

Where this sits

Naive Bayes for text goes back decades, and its independence assumption has been examined from many sides: Lewis (1998) surveys its history in retrieval, Domingos and Pazzani (1997) explain why it can classify well with badly wrong probabilities, McCallum and Nigam (1998) compare the multinomial and Bernoulli event models, and Rennie and colleagues (2003) repair several of its biases, including burstiness, with complement classes and log term frequencies. Joachims (1998) showed that text is the high-dimensional, nearly separable setting where margin methods do well, the geometry of Theorem 4. The formalML naive-Bayes topic covers Gaussian naive Bayes, Ng and Jordan for that case, and the Platt and isotonic repairs of its probabilities.

The next topic replaces learned weights with a fixed dictionary, Loughran and McDonald’s (2011), and asks what a lexicon gets wrong about financial words. The same log-linear model, lifted from documents to label sequences, is the linear-chain conditional random field of the sequence-labeling topic. Whether a $0.03$ accuracy gap between two of these classifiers is real is a question for the significance-testing topic. And a fine-tuned encoder replaces the bag of words with a representation that can see “costs rose” as a phrase.

Honest caveats

⚠ Rigor flag

Proved and cited. Propositions 1–4, Lemma 1, and Theorems 1–4 are proved here. Ng and Jordan’s discriminative results (their Propositions 1 and 2) and Soudry and colleagues’ theorems on gradient descent are cited.
A vacuous bound, honestly stated. Theorem 2 holds as stated, and with explicit constants its margin is $402$ nats where observed gaps are near $2$ . It describes how the sample size scales, not what it is.
The discriminative side concerns 0-1 error. Ng and Jordan analyze the classifier that minimizes training 0-1 error over half-spaces. Logistic regression’s MLE minimizes log loss, and on separable data it does not exist.
Crossovers are not universal. Xue and Titterington (2008) find Ng and Jordan’s two regimes unreliable on real data. Our crossovers appear only in worlds built for them, and the finance corpus shows none on its full vocabulary.
Simulated worlds tune on fresh data. Every hyperparameter in the learning curves is chosen on an independent validation draw from the world, which real data does not provide.
Sufficient, not necessary. Theorem 3’s token count is a worst case over words; rare words are rare in test documents, too.
A synthetic corpus. The finance tone and its $0.890$ ceiling come from a generator with planted structure. The NB-weighted model is a logistic one-versus-rest variant of NBSVM, and its probabilities are normalized scores.
One split, short grids. The main finance table is one split on grids that stop at the values they select. Six-split figures are labeled, and the wider grids change the numbers, not the ranking.
One run past $1{,}500$ documents. The training-size table is a single run on concatenated corpora that share no content words. Take the direction rather than the digits.

Implementation

The companion notebook (notebookPath) imports linear_text_classifiers.py, which owns every number on this page. That module imports the Zipf topic’s module for Zipf’s law and the shared finance corpus through it. It implements multinomial and Bernoulli naive Bayes in Proposition 1’s closed form, softmax and binary logistic regression by trust-region Newton–CG with exact Hessian-vector products, the hard-margin SVM through its dual, the simulated worlds with common random numbers, and the finance classifiers. A harness of $45$ assertion-based tests runs in about four minutes on a laptop CPU, and --slow adds two checks that fit on up to $50{,}000$ documents, about ten minutes more. The tests cover:

Proposition 1 against the literal Bayes rule and scikit-learn’s naive Bayes, and the length counterexample.
Theorem 1’s gradient, Hessian, and null spaces against finite differences, its estimating equations at the fitted optimum, and scikit-learn’s logistic regression.
Lemma 1 and Theorem 2 in a Bernoulli world that meets their hypotheses, including how loose the bound is; Theorem 3 in the long-tailed world, with a Monte Carlo check of its Chernoff step.
Proposition 2’s identity and its balanced case, the one Bayes accuracy, who bursts, and the learning curves’ regimes in all four worlds; words seen once and what $\alpha$ pays for.
Theorem 4’s rank, separability by linear programming, the missing stationary point, and the monotone path and gradient-descent directions.
Proposition 3’s equivalence and bound, Proposition 4 by linear programming and on the corpus, and the finance tables, ceiling, prefixes, and label noise.
The case study’s explanations: six splits, wide grids, vocabulary cuts, redrawn words, exact readers, the bigram decomposition, and every phrase the page quotes from the corpus.

The laboratory reads its data from a JSON file that one of those tests requires to equal the module’s viz_payload() exactly, so the figure cannot drift from the code.

References & Further Reading

paper On Discriminative vs. Generative Classifiers: A Comparison of Logistic Regression and Naive Bayes — Andrew Y. Ng and Michael I. Jordan (2002) Advances in Neural Information Processing Systems 14, 841–48 (NIPS 2001, MIT Press 2002). Generative–discriminative pairs; Proposition 1 (asymptotic errors), Proposition 2 (the discriminative side, m = Ω(n)), Lemma 3 and Theorem 4 (the generative side), Corollary 6 (m = O(log n)), on which Lemma 1 and Theorem 2 are modeled
paper Comment on 'On Discriminative vs. Generative Classifiers: A Comparison of Logistic Regression and Naive Bayes' — Jing-Hao Xue and D. Michael Titterington (2008) Neural Processing Letters 28 (3): 169–87. Simulations and real data on which the two regimes of Ng and Jordan are not reliable, and no general criterion for choosing between the two kinds of classifier
paper A Comparison of Event Models for Naive Bayes Text Classification — Andrew McCallum and Kamal Nigam (1998) Learning for Text Categorization: Papers from the 1998 AAAI Workshop, 41–48. The multinomial and Bernoulli event models of Proposition 1
paper Margin Maximizing Loss Functions — Saharon Rosset, Ji Zhu, and Trevor Hastie (2004) Advances in Neural Information Processing Systems 16, 1237–44. Theorem 2.1: as the penalty vanishes, the normalized penalized solution of a margin-maximizing loss converges to the max-margin separator, Theorem 4(c) here at p = 2
paper Boosting as a Regularized Path to a Maximum Margin Classifier — Saharon Rosset, Ji Zhu, and Trevor Hastie (2004) Journal of Machine Learning Research 5: 941–73. Section 5, Theorem 3: the same limit along the constrained path
paper The Implicit Bias of Gradient Descent on Separable Data — Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro (2018) Journal of Machine Learning Research 19 (70): 1–57. Theorem 3: gradient descent on separable logistic loss grows like the max-margin vector times log t; Theorem 5: its direction converges at rate O(log log t / log t)
paper On the Existence of Maximum Likelihood Estimates in Logistic Regression Models — A. Albert and J. A. Anderson (1984) Biometrika 71 (1): 1–10. Complete separation, quasi-complete separation, and overlap, the trichotomy behind Theorem 4(a)
paper Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition — Thomas M. Cover (1965) IEEE Transactions on Electronic Computers EC-14 (3): 326–34. Theorem 1, the function-counting theorem: how many labelings of points in general position a hyperplane can realize
paper Baselines and Bigrams: Simple, Good Sentiment and Topic Classification — Sida Wang and Christopher D. Manning (2012) Proceedings of the 50th Annual Meeting of the ACL (Volume 2: Short Papers), 90–94. The log-count ratio (their Eq. 2) and NBSVM (Eq. 4), whose feature weighting Proposition 3 analyzes
paper Tackling the Poor Assumptions of Naive Bayes Text Classifiers — Jason D. M. Rennie, Lawrence Shih, Jaime Teevan, and David R. Karger (2003) Proceedings of the Twentieth International Conference on Machine Learning, 616–23. Complement naive Bayes, weight normalization, and log term-frequency transforms against burstiness
paper Predicting Good Probabilities with Supervised Learning — Alexandru Niculescu-Mizil and Rich Caruana (2005) Proceedings of the 22nd International Conference on Machine Learning, 625–32. Naive Bayes pushes its probabilities toward 0 and 1
paper On the Optimality of the Simple Bayesian Classifier under Zero-One Loss — Pedro Domingos and Michael Pazzani (1997) Machine Learning 29 (2–3): 103–30. Why naive Bayes can classify well while its probabilities are badly wrong
paper Naive (Bayes) at Forty: The Independence Assumption in Information Retrieval — David D. Lewis (1998) Machine Learning: ECML-98, 4–15. Lecture Notes in Computer Science 1398
paper Discriminative vs Informative Learning — Y. Dan Rubinstein and Trevor Hastie (1997) Proceedings of the Third International Conference on Knowledge Discovery and Data Mining, 49–53. The two ways of fitting one classifier, before Ng and Jordan
paper The Efficiency of Logistic Regression Compared to Normal Discriminant Analysis — Bradley Efron (1975) Journal of the American Statistical Association 70 (352): 892–98. When the Gaussian model is right, logistic regression loses a third to a half of the discriminant's asymptotic efficiency
paper Probability Inequalities for Sums of Bounded Random Variables — Wassily Hoeffding (1963) Journal of the American Statistical Association 58 (301): 13–30. The inequality behind Lemma 1
paper Text Categorization with Support Vector Machines: Learning with Many Relevant Features — Thorsten Joachims (1998) Machine Learning: ECML-98, 137–42. Text is high-dimensional, sparse, and nearly separable, the setting of Theorem 4
paper When Is a Liability Not a Liability? Textual Analysis, Dictionaries, and 10-Ks — Tim Loughran and Bill McDonald (2011) Journal of Finance 66 (1): 35–65. Financial tone and the words a general-purpose sentiment model misreads; the next topic