Binary Naive Bayes in Exponential Family Form

Yaroslav Bulatov

April 29, 2006

Consider Naive Bayes classifier over binary domain. We want to predict Y ∈ {0,1} given X_{1,...,n} ∈ {0,1}^{n}.

We have

P(Y = y|X_{1,...,n} = x_{1,...,n}) = P(Y = y)∏_{i=1}^{n} P(X_{i} = x_{i})  (1)

For compactness introduce the following notation:

p_{0} = P(Y = 1)
p_{i0} = P(X_{i} = 1|Y = 0)
p_{i1} = P(X_{i} = 1|Y = 1)

Then we can write our probabilities as follows

P(X_{i} = x_{i}|Y = y) = p_{i0}^{(1−y)x_{i}}(1 − p_{i0})^{(1−y)(1−x_{i})} p_{i1}^{yx_{i}(1−p_{i1})}(1 − p_{i1})^{y(1−x_{i})}  (2)

Similary

P(Y = y) = p_{0}^{y}(1 − p_{0})^{1−y}  (3)

Substituting into original formula we get

P(Y = y,X_{1,...,n}) = p_{0}^{y}(1−p_{0})^{1−y} ∏_{i=1}^{n} p_{i0}^{(1−y)x_{i}}(1−p_{i0})^{(1−y)(1−x_{i})} p_{i1}^{yx_{i}}(1−p_{i1})^{y(1−x_{i})}

(4)

It’s easier to work with logs, so logP(Y = y,X_{1,...,n} = x_{1,...,n}) = = ylogp_{0}+ (1 − y)log(1 − p_{0})+ +∑ _{i=1}^{n} (1 − y)x_{i}logp_{i0}+ (1 − y)(1 − x_{i})log(1 − p_{i0})+ +∑ _{i=1}^{n} yx_{i}logp_{i1}+ y(1 − x_{i})log(1 − p_{i1}) Expand and group like terms to get

logP(Y = y,X_{1,...,n} = x_{1,...,n}) = log(1 − p_{0}) + ∑_{i=1}^{n} log(1 − p_{i}0)  (5)

+ y[log \frac{p_{0}}{1 − p_{0}} + ∑_{i=1}^{n} log \frac{1 − p_{i1}}{1 − p_{i0}} ]  (6)

+ ∑_{i=1}^{n} x_{i}log \frac{p_{i0}}{1 − p_{i0}}  (7)
+ ∑_{i=1}^{n} x_{i}ylog \frac{1 − p_{i0}}{p_{i0}} \frac{p_{i1}}{1 − p_{i1}}  (8)

Changing parameters we write

P(Y = y,X_{1,...,n} = x_{1,...,n}) = exp(θ_{0}y + ∑_{i=1}^{n} ϕ_{i}x_{i}+ ∑_{i=1}^{n} θ_{i}x_{i}y − A(p))  (9)

Where

θ_{0} = log \frac{p_{0}}{1 − p_{0}} + ∑_{i=1}^{n} log \frac{1 − p_{i1}}{1 − p_{i0}}  (10)
ϕ_{i} = log \frac{p_{i0}}{1 − p_{i0}} ,  (11)
θ_{i} = log \frac{1 − p_{i0}}{p_{i0}} \frac{p_{i1}}{1 − p_{i1}}  (12)
A(p) = −log(1 − p_{0}) − ∑_{i=1}^{n} log(1 − p_{i0})  (13)

This isn’t quite the exponential family form because the normalizer, A(p), needs to be in terms of our new parameters. First we solve for p_{i}’s to get

p_{0} = \frac{e^{θ_{0}} ∏ _{i=1}^{n} \frac{1+e^{ϕ_{i}+θ_{i}}}{1+e^{ϕ_{i}}}}{1 + e^{θ_{0}} ∏ _{i=1}^{n} \frac{1_{e}^{ϕ_{i}+θ_{i}}}{1+e^{ϕ_{i}}}}  (14)

p_{i0} = \frac{e^{ϕ_{i}}}{1 + e^{ϕ_{i}}}  (15)
p_{i1} = \frac{e^{ϕ_{i}+θ_{i}}}{1 + e^{ϕ_{i}+θ_{i}}}  (16)

Substituting into A(p) and simplifying get

A = log( ∏_{i=1}^{n} (1 + e^{ϕ_{i}}) + e^{θ_{0}} ∏ (1 + e^{ϕ_{i}+θ_{i}} ))  (17)

Finally our equation becomes

P(Y = y,X_{1,...,n} = x_{1,...,n}) = \frac{exp(θ_{0}y + ∑ _{i=1}^{n} ϕ_{i}x_{i}+ ∑ _{i=1}^{n} θ_{i}x_{i}y)}{∏ _{i=1}^{n} (1 + e^{ϕ_{i}}) + e^{θ_{0}} ∏ (1 + e^{ϕ_{i}+θ_{i}} )}  (18)

It can be useful to rewrite this as a product of conditional and marginal distributions:

P(Y,X_{1,...,n}) = \underbrace{\frac{exp(θ_{0}+ ∑ _{i=1}^{n} θ_{i}x_{i})^{y}}{1 + exp(θ_{0}+ ∑ _{i=1}^{n} θ_{i}x_{i})}}_{conditional}·\underbrace{\frac{exp(∑ _{i=1}^{n} ϕ_{i}x_{i}) + exp(∑ _{i=1}^{n} (ϕ_{i}+ θ_{i})x_{i}+ θ_{0})}{∏ _{i=1}^{n} (1 + e^{ϕ_{i}}) + e^{θ_{0}} ∏ (1 + e^{ϕ_{i}+θ_{i}} )}}_{marginal}

(19)

You can see that the conditional part is equivalent to logistic regression. Another thing to note is that since conditional part involves only θ’s, for every logistic regression model, there’s a corresponding Naive Bayes model (just set ϕ’s to be anything).