5
$\begingroup$

I would like some help in understanding how does Complement Naive Bayes work. I have googled the paper Complement Naive Bayes

I understand that naive bayes works by computing the probability of a document belonging to a class based on its features. However, in complement naive bayes it takes the complement of features in other classes? I am unsure of this part as to how it works.

$\endgroup$

1 Answer 1

10
$\begingroup$

Let's make this simple, and do a very contrived two class case:

Let's say we have three documents with the following words:

Doc 1: "Food" occurs twice, "Meat" occurs once, "Brain" occurs once

Class of Doc 1: "Health"

Doc 2: "Food" occurs once, "Meat" occurs once, "Kitchen" occurs 9 times, "Job" occurs 5 times.

Class of Doc 2: "Butcher"

Doc 3: "Food" occurs 2 times, "Meat" occurs 1 times, "Job" occurs once.

Class of Doc 3: "Health"

Total word count in class 'Health' - $(2 + 1 + 1) + (2 + 1 + 1) = 8$

Total word count in class 'Butcher' - $(1 + 1 + 9 + 5) = 16$

So we have two possible y classes: $(y = Health)$ and $(y = Butcher)$, with prior probabilities thus:

$p(y = Health) = {2 \over 3}$ (2 out of 3 docs are about health)

$p(y = Butcher) = {1 \over 3}$

Now, for Complement Normal Naive Bayes, instead of calculating the likelihood of a word occuring in a class, we calculate the likelihood that it occurs in other classes. So, we would proceed to calculate the word-class dependencies thus:

Complement Probability of word 'Food' with class 'Health': $$p(w = Food | \hat y = Health) = {1 \over 16}$$ See? 'Food' occurs 1 time in total for all classes NOT health, and the number of words in class NOT health is 16

Complement Probability of word 'Food' with class 'Butcher': $$p(w = Food | \hat y = Butcher) = {2+1+5 \over 8} = 1 $$

For others, $$p(w = Kitchen | \hat y = Health) = {9 \over 16}$$ $$p(w = Kitchen | \hat y = Butcher) = {0 \over 8} = 0$$ $$p(w = Meat | \hat y = Health) = {1 \over 16}$$ $$p(w = Meat | \hat y = Butcher) = {2 \over 8}$$

...and so forth

Then, say we had a new document containing the following:

New doc: "Food" - 1, "Job" - 1, "Meat" - 1

For normal Naive Bayes, (neglecting the constant evidence denominator), we would do our calculation and find the one with the maximum argument, viz:

$$argmax \ p(y) \bullet \prod p(w | y)^{f_i}$$

where $f_i$ is the frequency count of word $i$ in document $d$

But for Complement Naive Bayes, we would do:

$$argmin \ p(y) \bullet \prod {1 \over p(w | \hat y)^{f_i}}$$

...and now seek the one with the minimum argument.

We would predict the class of this new doc by doing the following:

$$ p(y=Health|w_1 = Food, w_2 =Job, w_3 =Meat) = $$ which gives us $$ p(y=Health) \bullet {1 \over p(w = Food | \hat y=Health)^{f_{Food}} \bullet p(w = Job | \hat y=Health)^{f_{Butcher}} \bullet p(w=Meat|\hat y=Health)^{f_{Meat}}} $$

Let's work it out - this will give us:

$$ {2 \over 3} \bullet {1 \over { {1 \over 16}^{1} \bullet {5 \over 16}^{1} \bullet {1 \over 16}^{1} } } \approx 6.302 $$

and for the second:

$$ p(y=Butcher) \bullet {1 \over p(w = Food | \hat y=Butcher)^{f_{Food}} \bullet p(w = Job | \hat y=Butcher)^{f_{Butcher}} \bullet p(w=Meat|\hat y=Butcher)^{f_{Meat}}} $$

giving us:

$$ {1 \over 3} \bullet {1 \over { {1 \over 8}^{1} \bullet {1 \over 8}^{1} \bullet {2 \over 8}^{1} } } \approx 85.333 $$

...and likewise for the other classes. So, the one with the lower probability (minimum value) is said to be the class it belongs to - in this case, our new doc will be classified as belonging to Health. We DON'T use the one with the maximum probability because for the Complement Naive Bayes Algorithm, we take it - a higher value - to mean that it is highly likely that a document with these words does NOT belong to that class.

Obviously, this example is, again, highly contrived, and we should even talk about Laplacian smoothing. But hope this helps you have a working idea on which you can build!

$\endgroup$
3
  • 1
    $\begingroup$ awesome simply awesome answer. i wish everyone were answering like this $\endgroup$ May 1, 2016 at 22:04
  • $\begingroup$ Say Knife occures a lot in documents with class Butcher, and rarely in documents with class health and both classes have approx. same number of total words. Hence, complement probability P(knife/y=Butcher) = "a low value" complement probability P(knife/y=Health) = "a high value" New document with "knife" will have P(health/d) = low value, while P(Butcher/d) a high value. Taking argmin will classify the document as Health, which wont be correct, I guess $\endgroup$ Feb 28, 2018 at 4:34
  • $\begingroup$ An attempted editor argues that the numerator of p(food|butcher) should be 2+2. $\endgroup$ Dec 25, 2018 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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