Naive Bayes classifier big O complexity

Question

I am trying to learn about The Naive Bayes Classifier as defined by the following:

where $\textbf{x} \in \{1, ... , K\}^{D}$

$K$ is the number of different values a feature can have

$D$ is the number of features in an input vector $\textbf{x}$

I actually have two questions:

First, could someone please explain this formula? It is still very fuzzy. For instance, the book says: "The model is called “naive” since we do not expect the features to be independent, or even conditional on the class label". Why is that the case? I understand what the class label is in this case (y=c) but I don't see why the book would make such an assertion.

And second, the book also says that the model has $O(C \times D)$ parameters. I know what Big O notation is, but what does it mean in this case?

Thanks in advance

Answer 1

Naive Bayes classifier is a Bayesian network classifier in which its structure restricted to be naive. It means that there is only one parent for all attributes. In Bayesian networks literature, this structure is called diverging connection. In diverging connections, when the parent is instantiated, the children are independent given knowing the different values of the parent. Since in naive Bayes classifier, we are going to calculate the posterior probability of class variable given attributes, we have to inverse it to the probability of attributes given class variable. In this case, the class is instantiated and attributes become conditionally independent given class variable.

At maximum state, naive Bayes classifier has O(CD) parameters. So, naive Bayes falls under the category of O(CD).