Calculating entropy of Naive Bayes random variables

Suppose a Naive Bayes graphical model with binary random variables is given by $$P(y,x_1,x_2,...,x_n)=P(y)P(x_1|y)...P(x_n|y)$$

Attempting to calculate $I(x_1,...,x_n;y)$ raises the question: how can the entropy $H(P(x_1,x_2,...,x_n))$ be calculated efficiently? There must be a better way than computing an exponential number of entries.

-
I don't think there's an easy way. You will need to sum over all possible patterns. –  Memming Aug 16 '13 at 14:50
@Memming - I find it strange that the effort needed is the same as when we know nothing about the marginal. Given the Naive Bayes assumption there are much less degrees of freedom to the marginal distribution. –  Leo Aug 16 '13 at 21:38