The naive Bayes classifier decides which class an object belongs to (an e-mail, a document, a day's weather) by combining the evidence of each of its attributes through Bayes' theorem, with a deliberate simplification: it assumes that, given the class, the attributes are independent of one another. Witten and colleagues admit it outright: this is unrealistic, and yet it works surprisingly well (Witten et al., 2017, p. 96).
How it works
The rule is P(class | x₁…xₙ) ∝ P(class) · P(x₁ | class) · … · P(xₙ | class). The denominator, P(x₁…xₙ), is the same for every class and disappears on normalization; P(class) is the prior probability (Witten et al., 2017, p. 98). Each factor is estimated by counting. In Witten and colleagues' weather example, a sunny, cool, humid, windy day yields a likelihood of 2/9 × 3/9 × 3/9 × 3/9 × 9/14 ≈ 0.0053 for "play" and 0.0206 for "don't play"; normalized, 20.5% against 79.5% (Witten et al., 2017, pp. 96–98).
Two fixes are indispensable. If a value never occurred with a class, its probability is zero and "vetoes" all the others; the Laplace estimator adds 1 to every count (Witten et al., 2017, p. 99). And since a long document multiplies hundreds of small numbers, logarithms are added instead, to avoid underflow (Witten et al., 2017, p. 104). For text, the document is represented as a bag of words: tokenize, build a vocabulary and count, with no order and no meaning (Alammar & Grootendorst, 2024, pp. 6–7). The multinomial version uses the frequencies: P(E | H) = N! × ∏ Pᵢ^nᵢ / nᵢ! (Witten et al., 2017, pp. 103–104).
History
Probabilistic modeling is one of the oldest forms of machine learning; Bayesian calculation was done by hand long before computers (Chollet, 2021, sec. 1.2.1). The work usually cited as its first use for text is by Maron (1961), at RAND: 405 abstracts of computer literature, 32 categories and 90 "clue words" chosen for being neither very frequent nor very rare (1961, pp. 407–409). Maron described the inference as an "inverse transition from evidence to hypothesis" (1961, p. 409) and declared independence "clearly" false, but convenient for computation (1961, p. 410). It picked the right category for 84.6% of the documents from which it had estimated its probabilities, but for only 51.8% of new documents with at least two clue words (1961, pp. 411–413): a textbook generalization gap. To avoid zeros, he inserted a small value into the empty cells, an idea of Paul Baran's (1961, p. 413). Four decades later, spam filters adopted Bayesian classifiers, and spammers answered with deliberate misspellings and white text on a white background (Witten et al., 2017, pp. 524–525).
Why it works, and when it doesn't
To classify, exact probabilities are unnecessary: it is enough for the correct class to get the highest one (Witten et al., 2017, p. 105). That is why it shrugs off irrelevant attributes, unlike k-nearest neighbors, but suffers from redundant ones: adding ten copies of temperature makes it decide on temperature alone (Witten et al., 2017, pp. 105, 289). It trains in linear time and can be updated one example at a time, like the Perceptron (Witten et al., 2017, pp. 507, 510).
A taxonomic detail: it models how each class generates its attributes, P(x | class), which makes it a generative model; the "discriminative" badge refers to its use as a classifier. It shares counting and smoothing with the n-gram model, but throws away the word order that the latter keeps.