Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A practical explanation of a Naive Bayes classifier

monkeylearn.com

Post reply on HN
Print view View original

31–40 of 42 posts

Re: A practical explanation of a Naive Bayes classifier

#31

Post by Houshalter »

b_ttercup wrote: post #25

Is Naive Bayes really ever the most practical choice? Yes it is a simple, fast algorithm, but it's usually a non trivial step below other simple models in my experience and doesn't seem to show any major advantages. The results shown here seem good but bag of words models usually do better than you might think on supervised NLP. So what's the motivation?

The scikit-learn flowchart recommends it for text data with less than 100k samples when linear SVC doesn't work: http://scikit-learn.org/stable/tutorial/machine_learning_map...

AFAIK it's by far the fastest machine learning method and one of the only ones that can be learned "online". I.e. it can just update the model each time it gets a datapoint, and then throw it away without saving it for future training. These are nice properties if you are doing something at a very large scale or in an environment with very limited resources.

And if your data happens to actually meet the naive bayes assumptions (that all the features are conditionally independent) then it's literally mathematically optimal and you can't do any better than it. It seems to work fairly well even when that isn't the case though.

Re: A practical explanation of a Naive Bayes classifier

#32

Post by abhgh »

imh wrote: post #27
abhgh wrote: post #23

Earlier quoted context omitted.

I may be missing something, but how do you take a log on the RHS of p(c_1|w)? The denominator has a sum i.e. "1+ something", which the log doesn't distribute over.

Heh, nope you're right I was writing to quickly. I meant to say to take a log of of the probability term in p(c_1|w). So you take p(c_1|w) = 1/(1+stuff) and turn it into p(c_1|w) = 1/(1+exp(log(stuff))). stuff is a product, so log(stuff) is a sum. Good catch.

Oh, I see it now. Thanks for clarifying!

In that case, you needn't have kept the denominator around at all. Since P(w) is not based on a class i.e. its not class conditioned, the classifier could have directly calculated P(C_1|w)/P(C_0|w). The P(w) term cancels out, and you end up with the product of ratios of feature probabilities conditioned on the classes.

Note though that, for K-classes, K>2, the number of parameters you need to store would blow up. You would need have these N ratios: P(w_j|C_x)/P(w_j|C_y) for all possible classes x,y. Here N is the number of features. So, in all N*C(K,2) values. On the contrary, multiclass softmax regression (the discriminative analogue for NB) would need NK parameters.

Re: A practical explanation of a Naive Bayes classifier

#33

Post by moultano »

Houshalter wrote: post #29
moultano wrote: post #21

Earlier quoted context omitted.

This is not invariant to the size of the document (though agreed, generally better). It doesn't solve the problem of having mostly positive features and a negative prior. Stated more formally, your model is b + wᵀx. Generally, b is 0. As the document grows, wᵀx tends to dominate b. You'll have bias with length as long as E[wᵀx]≠0 and there aren't any constraints on w that would force this.

If your data obeys the naive Bayes assumptions then this model is mathematically optimal. That each word is independently drawn from some distribution conditional on it's class. E.g. if there was an exactly 1% chance any given word in a spam email would be "viagra". Now obviously real world data doesn't obey these assumptions perfectly. But I don't see how violating the independent features assumption would cause the…

For a simple example, imagine a dataset where the naive assumption is true if you split it into 100 classes, but false if you split it into one vs everything else. All of the conditional probabilities for the "everything else" class will be underestimated, biasing the weights towards the one.

This problem happens because the class you are interested in is more compact than its inverse.

It's also exacerbated by feature selection, as the negative features have smaller weights and thus lower information gain than the positive features.

Re: A practical explanation of a Naive Bayes classifier

#35

Post by nl »

j2kun wrote: post #8
schuetze wrote: post #2

Considering the relative ease of implementation, classification accuracy with smaller datasets, and computational efficiency of Naive Bayes classifiers, I am surprised that they are not mentioned as often as other machine learning competitors, such as random forest. Are there major drawbacks to Naive Bayes classifiers? Is it just that they aren't as accurate on large datasets?

Boosted decision trees account for >50% of all Kaggle winners. That is the real surprise, since people rarely talk about boosted decision trees.

There is no greater discussion topic on Kaggle Slack than a comparison of XGB vs LightGBM vs CatGBM.

Re: A practical explanation of a Naive Bayes classifier

#36

Post by phunge »

Houshalter wrote: post #31
b_ttercup wrote: post #25

Is Naive Bayes really ever the most practical choice? Yes it is a simple, fast algorithm, but it's usually a non trivial step below other simple models in my experience and doesn't seem to show any major advantages. The results shown here seem good but bag of words models usually do better than you might think on supervised NLP. So what's the motivation?

The scikit-learn flowchart recommends it for text data with less than 100k samples when linear SVC doesn't work: http://scikit-learn.org/stable/tutorial/machine_learning_map... AFAIK it's by far the fastest machine learning method and one of the only ones that can be learned "online". I.e. it can just update the model each time it gets a datapoint, and then throw it away without saving it for future training. These a…

Logistic regression can easily be made online too, keep in mind! sklearn has an implementation of online gradient descent, and vowpal wabbit is also excellent at those problems.

Naive bayes can be parallelized in ways that SGD can't, that's a whole other conversation.

Re: A practical explanation of a Naive Bayes classifier

#37

Post by logicallee »

moultano wrote: post #9

A practical issue for Naive Bayes that also infects linear models is bias w.r.t. document length. Typically when you are detecting a rare, relatively compact class such as sports articles (or spam) you will tend to have a strongly negative prior, many positive features, and few negative ones. As a consequence, as the length of your text increases, not only does the variance of your prediction increase, but the mean t…

I have an unusually poor understanding of this subject, so I know I am likely to be wrong and am seeking your correction. I just don't get it.

Naively, I was shocked that you suggest classifying usr/dict/words as a test after training - to me, this seems like classifying some specific exhaustive sample catalogue of microbes in the Center for Disease Control's building for -- anything related to microbes that was trained on the real world. I expect that of course it would pass the test (be a false positive for) a hospital, as a leprosy ward, as a middle school, as a sewage processing plant, as a factory, as a kitchen, as an African steppe, as the ISS space station, as a suburb, as anything. If it's exhaustive, it'll have whatever is in those places! And if it's a catalogue, you've reduced the frequency information that could differentiate these.

Like, how could I expect an exhaustive list of unique words with their count reduced to 1 to have any ability to be classified in any way based on a training set based on words and frequencies? It just seems like a shocking suggestion because it artificially reduces to a count of 1 the exact feature you are using, and then to make sure you can't even use the presence or absence of anything, it includes 1 of everything.

I was thinking, it is like learning to classify a Romance language (French, Italian, Spanish etc) based on the frequency of the letters A-Z based on documents in those languages, and then "testing" that classification on the text "abcdefghijklmnopqrstuvwxyz". If we trained on frequency, why would we expect useful output after reducing frequency to 1? Actually since a dictionary is exhaustive, it is like including the German ß, not in other languages, the French ç, not in other languages - and then being surprised that it passes the test for German (based on letters frequency) and for French. You've completely removed the information you trained on, then added examples for anything that can be used.

This seems really unrelated to document length.

A further example I thought of is suppose you were training something to classify professions, from a database of classified CV's/resumes, to decide if someone is a programmer, cook, athlete, etc. If I fed it a list of every keyword from my entire database, one per line, then the answer to 'is this an embedded systems programmer' is yes, is this front-end developer the answer is 'yes' and if your database is big enough, is this a Historian specialized is medieval metallurgy the answer is 'yes.' Why would any of these be considered false positives since I've just put them as skills!

So I realize I am trying to be intuitive and likely am very naive, but I am totally confused why you suggest usr/dict/words.

You seem to say it is about length, but my a-z text example is just 26 characters (plus special ones) whereas the training data could be thousands of pages in each language.

I simply don't follow at all, which is frustrating because I have such a poor understanding to begin with.

I will appreciate any correction!

Sorry this ended up a bit long. I tried to include 2 or 3 practical examples so you can better judge my understanding and maybe correct it. Thank you.

Re: A practical explanation of a Naive Bayes classifier

#38

Post by geezerjay »

moultano wrote: post #14
intune wrote: post #12

Earlier quoted context omitted.

Is there some way to normalize the document length?

Lots of reasonable hacks. 1. Use only the beginning of the document, as that's probably the most important part anyways, and it's fast. 2. Divide the sum of your feature scores by sqrt(n) to give it constant variance, and hopefully keep it comparable with your prior. 3. Split the doc into reasonably sized chunks, and average their scores rather than adding them.

> 1. Use only the beginning of the document, as that's probably the most important part anyways, and it's fast.

That seems to be a solution devised for news articles, as the standard news writing style involves providing answers to the Five Ws up front on the article.

Re: A practical explanation of a Naive Bayes classifier

#39

Post by geezerjay »

intune wrote: post #12
moultano wrote: post #9

A practical issue for Naive Bayes that also infects linear models is bias w.r.t. document length. Typically when you are detecting a rare, relatively compact class such as sports articles (or spam) you will tend to have a strongly negative prior, many positive features, and few negative ones. As a consequence, as the length of your text increases, not only does the variance of your prediction increase, but the mean t…

Is there some way to normalize the document length?

> Is there some way to normalize the document length?

A basic technique is to normalize each term within a document following the term frequency-inverse document frequency statistic.

https://en.wikipedia.org/wiki/Tf%E2%80%93idf

Re: A practical explanation of a Naive Bayes classifier

#40

Post by Houshalter »

phunge wrote: post #36
Houshalter wrote: post #31

Earlier quoted context omitted.

The scikit-learn flowchart recommends it for text data with less than 100k samples when linear SVC doesn't work: http://scikit-learn.org/stable/tutorial/machine_learning_map... AFAIK it's by far the fastest machine learning method and one of the only ones that can be learned "online". I.e. it can just update the model each time it gets a datapoint, and then throw it away without saving it for future training. These a…

Logistic regression can easily be made online too, keep in mind! sklearn has an implementation of online gradient descent, and vowpal wabbit is also excellent at those problems. Naive bayes can be parallelized in ways that SGD can't, that's a whole other conversation.

Gradient descent can be made online. But it's very slow and suffers from catastrophic forgetting. Typical gradient descent needs to iterate over the dataset many times, while naive Bayes only needs one pass.
Post reply on HN