3 ms·

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 cl

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 tends to as well. This leads to all very long documents being classified as positive, regardless of their text. You can observe this by training your model and then classifying /usr/dict/words. This is the most common mistake I've seen in production use of linear models on document text. Invariably, they'll misfire on any unusually long document.

intune 9y ago
Is there some way to normalize the document length?
- moultano 9y ago
  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.
  - _dps 9y ago
    I'll add to this that you can add a very crude (separate) model for the document length and number of distinct words, and use that to flag outlier documents that might bump into the known weaknesses with respect to document length.
  - geezerjay 9y ago
    > 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.
- Houshalter 9y ago
  You can use term frequency instead of binary features. This is invariant to the size of the document. This is called multinomial naive Bayes: https://en.m.wikipedia.org/wiki/Naive_Bayes_classifier#Multinomial_naive_Bayes https://en.m.wikipedia.org/wiki/Naive_Bayes_classifier#Multi...
  - moultano 9y ago
    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, and E[wᵀx] > 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.
    - Houshalter 9y ago
      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 problem you mention. A longer email does mean the word "viagra" is more likely to occur in a normal email just by random chance. But the model takes that into account by recording the frequency of "viagra" in normal emails and seeing if it's consistent with that.
      - moultano 9y ago
        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.
- geezerjay 9y ago
  > 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 https://en.wikipedia.org/wiki/Tf%E2%80%93idf
mooman219 9y ago
I agree, there are issues with NB such as the ones you brought up. I don't think document length is the real offender here though. This really boils down to noise and how well you filter and devalue it. Stacking more filters like stemming, stopwords, and high frequency features definitely helps in this case to the point where longer documents can actually improve accuracy. Additionally, tuning your ngram lengths or using variable lengths, choosing between word or character ngrams, and limiting your distribution size all will help depending on what you're trying to categorize.
logicallee 9y ago
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.

intune 9y ago

Is there some way to normalize the document length?

moultano 9y ago
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.
- _dps 9y ago
  I'll add to this that you can add a very crude (separate) model for the document length and number of distinct words, and use that to flag outlier documents that might bump into the known weaknesses with respect to document length.
- geezerjay 9y ago
  > 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.
Houshalter 9y ago
You can use term frequency instead of binary features. This is invariant to the size of the document. This is called multinomial naive Bayes: https://en.m.wikipedia.org/wiki/Naive_Bayes_classifier#Multinomial_naive_Bayes https://en.m.wikipedia.org/wiki/Naive_Bayes_classifier#Multi...
- moultano 9y ago
  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, and E[wᵀx] > 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.
  - Houshalter 9y ago
    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 problem you mention. A longer email does mean the word "viagra" is more likely to occur in a normal email just by random chance. But the model takes that into account by recording the frequency of "viagra" in normal emails and seeing if it's consistent with that.
    - moultano 9y ago
      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.
geezerjay 9y ago
> 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 https://en.wikipedia.org/wiki/Tf%E2%80%93idf

mooman219 9y ago

I agree, there are issues with NB such as the ones you brought up. I don't think document length is the real offender here though. This really boils down to noise and how well you filter and devalue it. Stacking more filters like stemming, stopwords, and high frequency features definitely helps in this case to the point where longer documents can actually improve accuracy. Additionally, tuning your ngram lengths or using variable lengths, choosing between word or character ngrams, and limiting your distribution size all will help depending on what you're trying to categorize.

logicallee 9y ago

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.