GATE 2024 DA Q.20: solution and answer

Official answer: BSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

1. Naïve Bayes assumes the attributes are conditionally independent given the class, so the model is $P(Y){\prod }_{i=1}^{K}P(X_i\mid Y)$. Only these factors need to be estimated.

2. Class prior: $Y$ takes 2 values and $P(Y=0)+P(Y=1)=1$, so $P(Y)$ has $2-1=1$ free parameter.

3. Each attribute $X_i$ is binary, so for each class value $y$ the distribution $P(X_i\mid Y=y)$ is a Bernoulli distribution with one free parameter, $P(X_i=1\mid Y=y)$. The value $P(X_i=0\mid Y=y)$ follows from it.

4. Conditional parameters: $K$ attributes $\times$ 2 classes $=2K$.

5. Total number of parameters: $2K+1$, which is option (B).

6. Without the independence assumption, the joint distribution of $K$ binary attributes would need $2^K-1$ free parameters per class, so $2(2^K-1)+1$ in all. The naïve assumption therefore cuts the growth from exponential to linear in $K$.