Exercise 3.20 - Class conditional densities for binary data

For question (a), we have:

The number of parameter in this case is:

For question (b) and (c), the overfitting is generally assumed to decline when $N$ grows. The dependence within the variables generally hinder generalization when $N$ is small, but it could correctly capture the dependence, be it exist.

For question (d), fitting each parameter for the naive Bayes model requires averaging all components in the samples belong to one class, which is of complexity order $𝒪(N)$. The total complexity is thus of order $𝒪(C\cdot D\cdot N)$. For the full Bayes classifier, the complexity is of order $𝒪(C\cdot 2^D\cdot N)$.

For question (e), the cost of inference in the naive Bayes model is $𝒪(C\cdot D)$ for each sample. While that for full Bayes model is $𝒪(C\cdot 2^D)$.

For question (f), we have:

where we assumed a uniform prior on all classes since it is not the bottleneck of complexity. The complexity for the naive model is then:

while that for the full model is: