Bayes Rule

$P(C|A)=\frac{P(A|C)\cdot P(C)}{P(A)}$

• $P(A,C)=P(C)\cdot P(A|C)$
• $P(C,A)=P(A)\cdot P(C|A)$
• $P(A)\cdot P(C|A)=P(C,A)=P(A,C)=P(C)\cdot P(A|C)$
• $P(A)\cdot P(C|A)=P(C)\cdot P(A|C)$

In words, it becomes:
$P(\text{cause}|\text{evidence})=P(\text{evidence}|\text{cause})\cdot P(\text{cause})÷P(\text{evidence})$

• $P(\text{cause}|\text{evidence})$ is the Posterior
• $P(\text{evidence}|\text{cause})$ is the Likelihood
• $P(\text{cause})$ is the Prior
• $P(\text{evidence})$ is the Normalization

Evidence is what we know -- the given feature.
Cause is the class we are trying to classify the item into.

This is useful because $P(\text{evidence}|\text{cause})$ tends to be stable, but $P(\text{cause}|\text{evidence})$ is less stable, because it depends on the set of possible causes and how common they are right now.

In a "We see a teal bike. What is the chance that it's a veoride?" example, Veoride likes teal and regular bike owners don't. So probability of teal given Veoride is stable, while probability of Veoride given Teal depends on what types of bikes we are looking at.

MAP Estimate

Maximum a Posterior (MAP) Estimate chooses the type with the highest posterior probability:

• Suppose type $X$ comes from a set of types $T$
• MAP picks the type $X$ such that $P(X|\text{evidence})$ is highest: $argma{x}_{X\in T}P(X|\text{evidence})$
• where $argmax$ returns the index (value of $X$) that gives the larges value

Ignoring normalization factor
Bayesian estimation often works with the equation
$P(\text{cause}|\text{evidence})\propto P(\text{evidence}|\text{cause})\cdot P(\text{cause})$

The normalization is often ignored because we are only trying to determine the relative probabilities. $P(\text{evidence})$ is often the same in one comparison. That is to say, for all entries in the dataset, the denominator does not change, it remain static. so we only care about the posterior $\propto$ (proportional to)

MLE Estimate

The Maximum a Posterior (MAP) Estimate reflects the relative frequencies of the two underlying causes/types by including the prior $P(\text{cause})$. If we know that all causes/types are equally likely, then we can set $P(\text{cause})$ to the same value. We have:

Maximum Likelihood Estimate
$P(\text{cause}|\text{evidence})\propto P(\text{evidence}|\text{cause})$

• Maximizes the likelihood $P(\text{evidence}|\text{cause})$
• Pros: can be a sensible choice if we have poor information about the prior probabilities
• Cons: inaccurate if the prior probabilities of different causes are very different.

Naive Bayes

Naive Bayes deal with multiple types of evidences ($A,B$) about the same cause/class $C$. It is based on applying Intro Probability and #Bayes Rule with strong independence assumption between features.

• MAP Estimate: $P(C|A,B)\propto P(A,B|C)\cdot P(C)$
• Assume that $A$ and $B$ are conditionally independent given $C$: $P(A,B|C)=P(A|C)\cdot P(B|C)$
• So the Naive Bayes Equation is: $P(C|A,B)\propto P(A|C)\cdot P(B|C)\cdot P(C)$

In larger dimensions, where $C$ causes $E_1,...E_n$ effects:
$P(C|E_1...E_n)\propto P(E_1|C)\cdot P(E_2|C)...\cdot P(E_n|C)\cdot P(C)=P(C)\cdot {\mathrm{\Pi }}_{k=1}^{n}P(E_k|C)$

E.g. Classify UK v UK English given an input document $W_1,W_2...W_n$

• $P(\text{UK}|W_1...W_n)\propto P(\text{UK})\cdot {\mathrm{\Pi }}_{k=1}^{n}P(W_k|\text{UK})$

• $P(\text{US}|W_1...W_n)\propto P(\text{US})\cdot {\mathrm{\Pi }}_{k=1}^{n}P(W_k|\text{US})$

We need the following pre-knowledge from training data:

• The likelihood $P(W|\text{UK})$ and $P(W|\text{US})$ for each word type $W$

• The priors $P(\text{UK})$ and $P(\text{US})$

So $O(n)$ probabilities to estimate, where $n$ is the number of word types, whereas the full joint distribution is $O(2^n)$.

In the following sections, we look at how to find the likelihood of each word appearing in document of a certain types $P(W|C)$, as well as its underlying problems and solutions.

Simple Estimating Probabilities from Data

Given Document $W_1...W_n$, two classes $C_1$ and $C_2$:

• $P(C_1)\cdot {\mathrm{\Pi }}_{k=1}^{n}P(W_k|C_1)$
• $P(C_2)\cdot {\mathrm{\Pi }}_{k=1}^{n}P(W_k|C_2)$

First try:
$\text{count}(W)$= number of times $W$ occurs in the documents of class $C$
$n$ = number of total words in the documents of class $C$
The naive estimate is $P(W|C)=\frac{\text{count}(W)}{n}$

Text Classification

Text Data Model
CS440 Artificial Intelligence/Classification

Underflow and Log Transformation

Problem: Underflow

Using the simple estimation, uncommon words can cause the estimate process to produce numbers too small for standard floating point storage.

Log Transformation

Log Transformation gives better precisions on small values, loses precision on large values.

• $P(C_1)\cdot {\mathrm{\Pi }}_{k=1}^{n}P(W_k|C_1)$
• becomes
• $log(P(C))+\sum _{k=1}^{n}log(P(W_k|C))$

That is, our naive Bayes algorithm will be maximizing

$log(P(C|W_1...W_k))\propto log(P(C))+\sum _{k=1}^{n}log(P(W_k|C))$

E.g. "The" and "my" are very common. We don't care about what their probability differences are. But we do care about the appearance probability of less commonly used words.

Overfitting and Smoothing

Problem: Overfitting

Words that didn't appear in the training data get estimated zero probability. Words that were uncommon in the training data get inaccurate estimates. Zeroes destroy the Naive Bayes algorithm.

Laplace Smoothing

Smoothing assigns non-zero probabilities to unseen words. Note that it's tricky because all probabilities of words must add up to one.

• $\text{UNK}$ = all unseen words (seen as a single word type)
• $V$ = number of word types seen in training data
• $n$ = number of words in our Class $C$ training data
• $P(\text{UNK}|C)=\frac{\alpha }{n+\alpha (V+1)}$
• $P(W|C)=\frac{\text{count}(W)+\alpha }{n+\alpha (V+1)}$

If we only use $\text{UNK}$ and $\alpha$, we will have a larger than 1 probability. So $V$ forces it back to normal.

Performance of Laplace smoothing

• overestimates probability of unseen words
• underestimates probability of common words

Deleted Estimation

Used to directly measure estimation errors. The steps are as follows:

1. Divide our training data into two halves 1 and 2.
2. Pick a specific count $r$ in the first half.
3. Suppose that $W_1...W_n$ are words that occur $r$ times in the first half. We can estimate the corrected count for this group of words as the average of their counts in the second half.
   • Specifically, suppose $C(W_k)$ is the count of $W_k$ in the second half of the dataset
   • The corrected count value $Corr(r)=\frac{\sum _{k=1}^{n}C(W_k)}{n}$
4. Further, make the estimate symmetrical:
   • Assume both half contains roughly the same number of words, compute:
   • $Corr(r)$ as above
   • $Cor{r}^{\prime }(r)$ reversing the role of the two halfs
   • $\frac{Corr(r)+Cor{r}^{\prime }(r)}{2}$ estimate of the true count for a word with observed count $r$