In the NB classifier, we have instances with $n$ attributes ($x = (a_1,\dots, a_n)$) values in a finite set $V$ and we want to find the most probable classification (max a posteriori classification)

\begin{align} v_{\text{MAP}} &= \text{argmax}_{v_j \in V} ~P(v_j|a_1,\dots,a_n)\\ & = \text{argmax}_{v_j \in V} P(a_1,\dots,a_n|v_j) P(v_j) \end{align}

To estimate the first term in the last expression, and assuming each of the $a_i$'s can take on $k$ possible distinct values, we need to estimate $k^n \times |V|$ terms (is this correct?). This might be too difficult, or indeed impossible given the size of the training set, so the NB assumption is that:

\begin{align} v_{\text{NB}} &= \text{argmax}_{v_j \in V} ~P(v_j|a_1,\dots,a_n)\\ & \approx \text{argmax}_{v_j \in V} ~ P(v_j) \prod_{i=1}^n P(a_i|v_j) \end{align}

and now the number of terms to estimate is $n \times k \times |V|$.

I am just wondering if my reasoning about the number of terms to estimate is correct?


You are almost right. For each feature $a_i$, conditioned by value $v_j$, the distribution is to be estimated. However, from the fact that $\forall v\in V:\sum_{i=1}^k P(a_i|v)=1$, you can infer one of the parameters, e.g. $P(a_k|v)=1-\sum_{i=1}^{k-1} P(a_i|v)$. Thus, you may need $n\times (k-1)\times |V|$ parameters to be estimated. The difference may be obvious especially in case of numerous binary features.

In the case of the full model, the situation is similar and you may need $(k^n-1)\times |V|$ parameters.

So far on the estimation. For the actual classification, you have to quantify for each option $v\in V$ the posterior probability which is based on $n$ features. If you have constant-time access to the probabilities (which is possible when representing them by matrices), then the complexity is $\mathcal{O}(|V|\times n)$. If the access would be based on more complicated indexing (e.g alphabetically listed),then the complexity would be $\mathcal{O}(|V|\times n \times \log(k))$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.