Naive Bayes Net

Definition:

• Features: $W_i$ is the word at position $i$
• Predict label conditioned on feature variables
• Assume features are conditionally independent given label

Model:

• $P(Y,W_1,...,W_n)=P(Y){\prod }_{i}P(W_i|Y)$

Prediction:

• $\hat{Y}=\arg {\max }_{y}P(y,W_1,...,W_n)$

Parameters:

• for each word there is probablity given the class
• ex: Spam Email Filter: $P(\text{Free}|spam)>P(\text{hello}|spam)$
  • MLE for Naive Bayes Spam Classifier:
  • Find a single parameter for each word $P(F_i|Y=\text{ham})$ as $\theta$
  • $\mathcal{L}(\theta )={\prod }_{j=1}^{N_h}P\left(F_i=f_i^{(j)}\mid Y=\text{ ham }\right)={\prod }_{j=1}^{N_h}{\theta }^{f_i^{(j)}}(1-\theta {)}^{1-f_i^{(j)}}$
    • $P\left(F_i=f_i^{(j)}\mid Y=ham\right)=\{\begin{array}{ll}\theta & \text{ if }{f}_i^{(j)}=1\\ (1-\theta )& \text{ if }{f}_i^{(j)}=0\end{array}$
  • $\mathrm{P}\left({\mathrm{F}}_{\mathrm{i}}\mid \mathrm{Y}=\text{ ham }\right):\theta =\frac{1}{N_h}\sum _{j=1}^{N_h}{f}_i^{(j)}$
  • Aware of Fitting: Problems with relative-frequency parameters
    • Unlikely to see occurrences of every words in training data.
    • Likely to see occurrences of a word for only 1 class in training data.

Parameter estimation:

• $P_{\theta }(x)$ means the probability of event x occurring, given the parameter  θ.

with maximum likelihood:

• Estimating the distribution of a random variable
• Empirically: use training data (learning!)
• E.g.: red and blue
  • For a simple example of guessing if a bean is red/blue, the parameter is the probability of it being red/blue
  • for each outcome x, look at the empirical rate of that value: $P(r)=\frac{\text{count(r)}}{\text{nb of samples}}$
  • $P_{\theta }(x=r)=\theta ,P_{\theta }(x=b)=1-\theta$
  • Maximum Likelihood Estimation $L(x,\theta )={\prod }_i{P}_{\theta }(x_i)=\theta .\theta .(1-\theta )$
    • a function that assigns a value to different possible parameter values based on how well they explain the observed data.
    • Higher values of $L(x,\theta )$ indicate that the parameter value θ is more likely to have resulted in the observed data $x$
• General cases of n outcomes:
  • $P(H)=q,P(T)=1-q$
  • Flips are independent and identially distributed $D=\{x_i|i=1,...,n\},P(D|\theta )={\prod }_{i}P(x_i|\theta )$
  • $\mathcal{D}$ is sequence of data $D$, $P(\mathcal{D}|\theta )={\theta }^{{\alpha }_H}(1-\theta {)}^{{\alpha }_T}$
  • Hypothesis space: binomial distributions
  • Learning: finding q which is optimal
  • MLE solve: choose $q$ that maximize $\hat{\theta }=\arg {\max }_{\theta }P(\mathcal{D}|\theta )=\arg {\max }_{\theta }\ln P(\mathcal{D}|\theta )$
  • ex: 2 heads and 1 tail $\to \arg {\max }_{\theta }\ln ({\theta }^2(1-\theta ))$
  • for $n$ observations: $\frac{d}{d\theta }\ln P(\mathcal{D}|\theta )=\frac{d}{d\theta }\ln {\theta }^{{\alpha }_H}(1-\theta {)}^{{\alpha }_T}=0\to {\hat{\theta }}_{MLE}=\frac{{\alpha }_H}{{\alpha }_H+{\alpha }_T}$

Smoothing:

Laplace Smoothing:

• Laplace’s estimate:
  • Pretend you saw every outcome once more than you actually did
  • $P_{LAP}(x)=\frac{c(x)+1}{{\sum }_x[c(x)+1}=\frac{c(x)+1}{N+|X|}$ with Dirichlet priors
• Laplace’s extended estimate:
  • Pretend you saw every outcome k times more than you actually did
  • $P_{LAP,k}(x)=\frac{c(x)+k}{N+k|X|}$ where $k$ is the strenth of the prior
• Laplace for conditionals:
  • Smooth each condition independently: $P_{LAP,k}(x\mid y)=\frac{c(x,y)+k}{c(y)+k|X|}$

Naive Bayes classifier:

• $\hat{y}=\arg \underset{y}{\max }P(Y=y|X=x)=\arg \underset{y}{\max }\frac{P(X=x|Y=y)P(Y=y)}{P(X=x)}=\arg \underset{y}{\max }P(Y=y)\prod _{i=1}^{d}P(X_i=x_i|Y=y)$