Naive Bayes

It is 2002. Your inbox is drowning in offers for cheap medication and unclaimed fortunes. A filter built by researchers at MIT and Yahoo flips the switch — not by parsing sentences or understanding meaning, but by doing arithmetic so blunt it borders on insultingly simple: it multiplies probabilities.

That filter was Naive Bayes, and it still powers spam detection, medical triage, and sentiment analysis today. Its secret is an assumption so obviously false that statisticians wince when they hear it: every word in a message is independent of every other word.

"Win" and "money" appearing together is treated as no more suspicious than each word appearing alone. The model has no idea they travel in packs. Yet the math works out so well in practice that Naive Bayes beat virtually every rival technique when email spam exploded in the early internet era. The naivety — the independence assumption — is not a bug. It is a deliberate, practical trade-off that makes the numbers tractable.

To understand why, we need to meet Bayes' theorem: a two-century-old equation about updating beliefs with evidence.

Below is a tiny email dataset. The classifier has already learned word frequencies from the training examples. Type a new message and hit Classify — the demo shows you the per-word log-probability contributions and the final verdict.

<div class="nb-wrap">
  <div class="training-panel">
    <div class="panel-title">{{training_data}}</div>
    <div id="training-list" class="training-list"></div>
  </div>
  <div class="classify-panel">
    <div class="panel-title">{{classify_msg}}</div>
    <textarea id="msg-input" rows="2" placeholder='{{placeholder}}'></textarea>
    <div class="btn-row">
      <button id="classify-btn" type="button">{{classify_btn}}</button>
      <button id="reset-btn" type="button" class="ghost">{{clear_btn}}</button>
    </div>
    <div id="result-box" class="result-box hidden"></div>
    <div id="breakdown" class="breakdown hidden"></div>
  </div>
</div>

* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; font-size: 14px; color: #222; padding: 8px; }
.nb-wrap { display: flex; gap: 10px; flex-wrap: wrap; }
.training-panel, .classify-panel { flex: 1 1 200px; min-width: 180px; }
.panel-title { font-weight: 700; font-size: .8rem; text-transform: uppercase;
               letter-spacing: .05em; color: #556; margin-bottom: 6px; }
.training-list { display: flex; flex-direction: column; gap: 4px; }
.train-item { border-radius: 6px; padding: 5px 8px; font-size: .82rem; line-height: 1.4; }
.train-item.spam { background: #fde8e8; border-left: 3px solid #e63946; }
.train-item.ham  { background: #e8f5e9; border-left: 3px solid #2a9d55; }
.train-label { font-weight: 700; font-size: .75rem; text-transform: uppercase;
               letter-spacing: .04em; margin-right: 4px; }
.train-item.spam .train-label { color: #c92f3c; }
.train-item.ham  .train-label { color: #1a7a40; }
textarea { width: 100%; border: 1px solid #ccd; border-radius: 6px; padding: 6px 8px;
           font: 14px system-ui, sans-serif; resize: vertical; }
.btn-row { display: flex; gap: 6px; margin: 6px 0; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .38rem .8rem; border-radius: 6px;
         cursor: pointer; border: 1px solid #1d3557; background: #1d3557; color: #fff; }
button.ghost { background: #fff; color: #1d3557; }
.result-box { padding: 8px 10px; border-radius: 6px; font-weight: 700; font-size: .95rem; }
.result-box.spam { background: #fde8e8; color: #c92f3c; border: 1px solid #f5b5b8; }
.result-box.ham  { background: #e8f5e9; color: #1a7a40; border: 1px solid #a8d5b5; }
.breakdown { margin-top: 8px; }
.bk-title { font-size: .78rem; font-weight: 700; color: #556; text-transform: uppercase;
            letter-spacing: .04em; margin-bottom: 4px; }
.bk-row { display: flex; align-items: center; gap: 6px; margin: 3px 0; font-size: .8rem; }
.bk-word { min-width: 80px; font-family: ui-monospace, monospace; }
.bk-bar-wrap { flex: 1; background: #e8eef3; border-radius: 4px; height: 10px; overflow: hidden; }
.bk-bar { height: 100%; border-radius: 4px; transition: width .3s; }
.bk-bar.spam { background: #e63946; }
.bk-bar.ham  { background: #2a9d55; }
.bk-val { min-width: 54px; text-align: right; font-family: ui-monospace, monospace; font-size: .75rem; color: #556; }
.hidden { display: none; }

// Code not found

Notice how each word shifts the score up (toward spam) or down (toward ham). Words the model has never seen get a tiny floor probability so one unknown word cannot silence everything else — that trick is called Laplace smoothing. The whole classification runs in time proportional to the number of words: scaling from ten words to ten million words is just ten million multiplications.

So why does a lie work so well? The formal answer arrives from a 1997 paper by Pedro Domingos and Michael Pazzani: Naive Bayes is optimal under zero-one loss whenever the naive assumption is correct — but also in a much wider class of distributions where it is completely wrong.

The key insight is that the classifier only needs to rank classes, not measure their probabilities accurately. Even if P(spam | "win", "money") is wildly off because the two words are correlated, the ranking — spam score higher than ham score — can still be right most of the time.

Concretely:

• Training: count word frequencies per class, divide by class totals. $O(N \cdot V)$ time where N is the number of documents and V is the vocabulary size.
• Inference: sum log-probabilities of each word in the new document. O(|message|) time — blazingly fast.
• Accuracy: on many real text benchmarks Naive Bayes matches k-means and even simple neural networks while training in milliseconds.
• Failure modes: highly correlated features (like bigrams) can skew probability estimates, and the model cannot learn feature interactions. For structured data with strong correlations, methods like logistic regression or gradient boosting often win.

The status of Naive Bayes is solved — we understand exactly when it is optimal and when it is not. Unlike NP-hard problems such as P vs NP, there is no open question about tractability: classifying a document is always linear in the number of words.

"Count words, multiply probabilities, pick the highest class" is one of the most useful algorithms ever written:

• Spam filtering: SpamAssassin and the early Gmail filter used Naive Bayes. Training takes seconds; updates after a user marks a message as spam take milliseconds.
• Medical diagnosis: a symptom-checklist classifier that must run on a slow device in a rural clinic. Each symptom contributes its own probability — no matrix inversion, no GPU required.
• News categorization: Reuters and the 20 Newsgroups benchmark showed Naive Bayes matching far more complex models on topic classification.
• Sentiment analysis: product reviews, social-media monitoring and customer-feedback pipelines routinely start with a Naive Bayes baseline because it is fast, explainable, and surprisingly hard to beat without substantial extra data.
• Real-time malware detection: every file name, API call and network packet becomes a "word" — independence is still wrong, but the classifier still flags malicious software with high precision.

The classifier pairs naturally with Bayesian inference, which generalises the same updating logic to richer probabilistic models. It also shows up as a baseline in virtually every machine-learning benchmark, because a method this simple and fast provides a meaningful floor: if you cannot beat Naive Bayes, your fancy model has a problem.

Naive Bayes is a study in productive dishonesty. Its foundational assumption — that "win" tells you nothing extra about "money" — is empirically false in almost every message ever written. Yet ignoring that correlation makes the computation linear, the model interpretable, and the training instant. In the tradeoff between rigor and practicality, Naive Bayes chose practicality and turned out to be right more often than theories predicted.

The next time your spam folder silently catches a hundred scam emails before you even open your inbox, remember: underneath the hood is nothing more than Bayes' theorem, a handful of word counts, and a willingness to pretend that language has no grammar. It is one of the most successful lies in the history of computing — and it runs in time proportional to the length of the message.

For a deeper look at where the independence assumption breaks down and what replaces it, see Bayesian inference and PAC learning.