Concept - Naive Bayes

(Stub created by chunk 07; earlier/later chunks should append the general definition and derivation.)

From chunk 07 (s.181-210)

Classification by scoring each class as prior $\times$ product of per-feature likelihoods; the class with the highest score wins. With numeric features the likelihoods come from Gaussian curves (Concept - Gaussian Naive Bayes). Components: Concept - Prior Probability, Concept - Likelihood; numerical safeguard: log transform against Concept - Underflow.

Source chunk: 03 Text Classification - Chunk 07 (s.181-210)

Multinomial spam example: “Dear Friend” (s.61-90)

Source: 03 Text Classification - Chunk 03 (s.61-90).

• Training data: 12 messages, 8 normal (N), 4 spam (S); word likelihoods over Dear/Friend/Lunch/Money (s.61-62), see Concept - Likelihood.
• Score per class = Concept - Prior Probability x likelihood of each word of the new message in that class:
  • $p(N)p(\text{Dear}\mid N)p(\text{Friend}\mid N)=0.67\times 0.47\times 0.29=0.09$ (s.77)
  • $p(S)p(\text{Dear}\mid S)p(\text{Friend}\mid S)=0.33\times 0.29\times 0.14=0.01$ (s.90)
• The scores are only proportional to $p(N\mid \text{Dear Friend})$ (s.79), see Concept - Posterior Probability. The decision step (larger score wins) follows in the next chunk.

flowchart LR
    P["Prior p(class)"] --> X(("x"))
    L1["p(Dear | class)"] --> X
    L2["p(Friend | class)"] --> X
    X --> SC["Class score"]

Smoothing, why “naive”, and text variants (s.121-150)

Source: 03 Text Classification - Chunk 05 (s.121-150)

• Adding $\alpha$ pseudo-counts to every word avoids zero probabilities (Concept - Laplace Smoothing): $p(\text{Lunch}\mid \text{Spam})=1/(7+4)=0.09$ (s.126-128); priors stay 0.67 / 0.33 (s.129-130). “Lunch Money Money Money Money”: normal 0.00001 vs spam 0.00122 -> spam (s.132-135).
• Naive = treats all word orders the same, ignores grammar and phrases; “Dear Friend” and “Friend Dear” both score 0.08 (s.137-143). It treats text as a bag of words (Concept - Bag of Words).
• Still performs surprisingly well (s.144): high bias, low variance (Concept - Bias and Variance, s.145).
• Text variants: Concept - Multinomial Naive Bayes (counts / TF-IDF, frequency matters) and Concept - Bernoulli Naive Bayes (binary presence/absence) (s.146-150).

Scoring and decision with logs (s.211-240)

Class score = prior x product of feature likelihoods; compute it as $\log p(c)+{\sum }_j\log L(x_j\mid c)$ to avoid Concept - Underflow (s.211-214, s.231-233). Example: log score Loves = -124, Does Not Love = -48; the highest log score wins, so the person is classified as Does Not Love Troll 2 (s.237-238). Worked example: 03 Text Classification - Chunk 08 (s.211-240).

Worked example continued: “Dear Friend” and “Lunch Money Money Money Money” (from 03 Text Classification - Chunk 04 (s.91-120))

• Training estimates (s.91-120): $p(N)=0.67$, $p(S)=0.33$; $p(\text{Dear}\mid N)=0.47$, $p(\text{Friend}\mid N)=0.29$, $p(\text{Lunch}\mid N)=0.18$, $p(\text{Money}\mid N)=0.06$; $p(\text{Dear}\mid S)=0.29$, $p(\text{Friend}\mid S)=0.14$, $p(\text{Lunch}\mid S)=0.00$, $p(\text{Money}\mid S)=0.57$.
• Score = prior x product of word likelihoods, only proportional to the posterior $p(c\mid \text{message})$ (s.92). “Dear Friend”: N $=0.09$ > S $=0.01$ -> normal (s.91-96).
• Repeated words are multiplied once per occurrence: N score for “Lunch Money Money Money Money” $=p(N)p(\text{Lunch}\mid N)p(\text{Money}\mid N{)}^4=0.000002$ (s.99-106).
• Failure case: the spam score is 0 because $p(\text{Lunch}\mid S)=0$ (word unseen in spam training data), so the message is always labelled normal (s.107-118). See Concept - Zero Probability Problem; fixed by Concept - Laplace Smoothing (add 1 count to every word, s.120).

From chunk 02 (s.31-60)

Text version of Naive Bayes (Concept - Multinomial Naive Bayes): per-class word probabilities are learned from word-count histograms (Concept - Word Likelihood; worked example with Dear/Friend/Lunch/Money, normal vs spam, s.36-60). Problems and fixes: zero counts (Concept - Zero Probability Problem, Concept - Additive Smoothing) and unseen test words (Concept - Out of Vocabulary (OOV), <UNK> token) (s.31).

Source chunk: 03 Text Classification - Chunk 02 (s.31-60)

Worked comparison and GNB intro (s.151-180)

Spam/ham example classified with Concept - Multinomial Naive Bayes (0.00133 vs 0.000296) and Concept - Bernoulli Naive Bayes (0.00555 vs 0.000275), normalized with Concept - Posterior Normalization; then Concept - Gaussian Naive Bayes for continuous features. Details: 03 Text Classification - Chunk 06 (s.151-180).

Generative view and limitation (s.293-295, chunk 10)

• Naive Bayes is a generative model: it models the joint $P(X,Y)$ (how the data was generated) and derives $P(Y|X)$; logistic regression is its discriminative counterpart (s.293-294). See Concept - Generative vs Discriminative Models.
• As a text generator (s.295): for positions 1..T sample category $h_i$ from $p(h)$ (or fixed), then sample the word from $p(\mathbf{d}|h_i)$. It ignores word dependencies (e.g. P(“read the paper”) > P(“read the movie”)); a Hidden Markov Model partially solves this.
• Source: 03 Text Classification - Chunk 10 (s.271-300)

From chunk 01 (s.1-30)

Idea (s.21-23): Concept - Bayes Rule + Concept - Conditional Independence of attributes given the class. $p(\mathbf{d}|h_i)$ is hard to estimate for high-dimensional $\mathbf{d}$ (Concept - Curse of Dimensionality, s.20), so assume independence: $h_{NB}=\arg {\max }_{h_i\in \mathbb{H}}p(h_i){\prod }_{j=1}^{n}p(d_j|h_i)$ The assumption is often violated in practice but usually works well; successful for text documents and diagnosis (s.21).

Text application (s.25-30): classify a newsgroup article into its group; attributes = words. Priors from document counts (e.g. 300 likes / 700 dislikes of 1000 gives 0.3 / 0.7, s.27). Word probabilities by MLE counts in a per-class mega-document: $p(w|h_j)=count(w,h_j)/{\sum }_{d}count(d,h_j)$ (s.28). Unseen words zero the product (s.29), fixed by Concept - Additive Smoothing (s.30).

Source chunk: 03 Text Classification - Chunk 01 (s.1-30)

Related

Concept - Bayes Rule, Concept - Conditional Independence, Concept - Multinomial Naive Bayes, Concept - Bernoulli Naive Bayes, Concept - Gaussian Naive Bayes, Concept - Additive Smoothing, Concept - Underflow, Concept - Logistic Regression, Concept - Generative vs Discriminative Models. Up: 03 Text Classification - Index