Raising the baseline for high-precision text classifiers

ABSTRACT

Many important application areas of text classifiers demand high precision andit is common to compare prospective solutions to the performance of Naive Bayes. This baseline is usually easy to improve upon, but in this work we demonstrate that appropriate document representation can make out performing this classifier much more challenging. Most importantly, we provide a link between Naive Bayes and the logarithmic opinion pooling of the mixture-of-experts framework, which dictates a particular type of document length normalization. Motivated by document-specific feature selection we propose monotonic constraints on document term weighting, which is shown as an effective method of fine-tuning document representation. The discussion is supported by experiments using three large email corpora corresponding to the problem of spam detection, where high precision is of particular importance.

REFERENCES

• 1: P. Bennett. Assessing the calibration of naive Bayes' posterior estimates. Technical Report CMU-CS-00-155, School of Computer Science, Carnegie Mellon University, 2000.
• 2: L. Chen, J. Huang, and Z. Gong. An anti-noise text categorization method based on support vector machines. In Proceedings of AWIC 2005, pages 272--278, 20025.
• 3: G. Cormack. The TREC 2006 spam filter evaluation track. Virus Bulletin, (1), 2007.
• 4: G. Cormack and A. Bratko. Batch and online spam filter comparison. In Proceedings of the 3rd Conference on Email and Anti-Spam (CEAS-2006), 2006.
• 5: G. Cormack and T. Lynam. TREC 2005 spam track overview. In Proceedings of TREC 2005 - the Fourteenth Text REtrieval Conference, 2005.
• 6: Franca Debole , Fabrizio Sebastiani, Supervised term weighting for automated text categorization, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952688]
• 7: Pedro Domingos , Michael Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, v.29 n.2-3, p.103-130, Nov./Dec. 1997 [doi>10.1023/A:1007413511361]
• 8: H. Drucker, D. Wu, and V. Vapnik. Support Vector Machines for Spam Categorization. IEEE Transactions on Neural Networks, 10(5):1048--1054, 1999.
• 9: Edda Leopold , Jörg Kindermann, Text Categorization with Support Vector Machines. How to Represent Texts in Input Space?, Machine Learning, v.46 n.1-3, p.423-444, 2002 [doi>10.1023/A:1012491419635]
• 10: C. Elkan. The foundations of cost-sensitive learning. In IJCAI, pages 973--978, 2001.
• 11: Nir Friedman , Dan Geiger , Moises Goldszmidt, Bayesian Network Classifiers, Machine Learning, v.29 n.2-3, p.131-163, Nov./Dec. 1997 [doi>10.1023/A:1007465528199]
• 12: Thomas Gärtner , Peter A. Flach, WBCsvm: Weighted Bayesian Classification based on Support Vector Machines, Proceedings of the Eighteenth International Conference on Machine Learning, p.154-161, June 28-July 01, 2001
• 13: C. Genest and J. Zidek. Combining probability distributions: A critique and an annotated bibliography. Statistical Science, 1986.
• 14: Joshua Goodman, Sequential conditional Generalized Iterative Scaling, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073086]
• 15: P. Graham. A plan for spam http://www.paulgraham.com/spam.html, 2002.
• 16: G. Hinton. Products of experts. In Proceedings of the Ninth International Conference on Artificial Neural Networks (ICANN99), pages 1--6, 1999.
• 17: Se June Hong , Jonathan Hosking , Ramesh Natarajan, Ensemble Modeling Through Multiplicative Adjustment of Class Probability, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.621, December 09-12, 2002
• 18: A. Juan and H. Ney. Reversing and smoothing the multinomial naive Bayes text classifier. In Proceedings of the 2nd Int. Workshop on Pattern Recognition in Information Systems (PRIS 2002), pages 200--212, 2002.
• 19: Sang-Bum Kim , Kyoung-Soo Han , Hae-Chang Rim , Sung Hyon Myaeng, Some Effective Techniques for Naive Bayes Text Classification, IEEE Transactions on Knowledge and Data Engineering, v.18 n.11, p.1457-1466, November 2006 [doi>10.1109/TKDE.2006.180]
• 20: Aleksander Kolcz, Local sparsity control for naive Bayes with extreme misclassification costs, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081888]
• 21: A. Kołcz and J. Alspector. SVM-based filtering of e-mail spam with content-specific misclassification costs. In Proceedings of the Workshop on Text Mining (TextDM'2001), 2001.
• 22: M. Lee and E. Corlett. Sequential sampling models of human text classification. Cognitive Science, 27(2):159--1193, 2003.
• 23: David D. Lewis, Naive (Bayes) at Forty: The Independence Assumption in Information Retrieval, Proceedings of the 10th European Conference on Machine Learning, p.4-15, April 21-23, 1998
• 24: A. K. McCallum and K. Nigam. A comparison of event models for Naive Bayes text classification. In AAAI-98 Workshop on Learning for Text Categorization, 1998.
• 25: V. Metsis, I. Androutsopoulos, and G. Paliouras. Spam filtering with Naive Bayes - which Naive Bayes? In Proceedings of the 3rd Conference on Email and Anti-Spam (CEAS-2006), 2006.
• 26: Dunja Mladenić , Janez Brank , Marko Grobelnik , Natasa Milic-Frayling, Feature selection using linear classifier weights: interaction with classification models, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009034]
• 27: Dunja Mladenic , Marko Grobelnik, Feature Selection for Unbalanced Class Distribution and Naive Bayes, Proceedings of the Sixteenth International Conference on Machine Learning, p.258-267, June 27-30, 1999
• 28: R. Raina, Y. Shen, A. Ng, and A. McCallum. Classification with hybrid generative/discriminative models. In Proceedings of NIPS 16, 2004.
• 29: J. Rennie, L. Shih, J. Teevan, and D. Karger. Tackling the poor assumptions of Naive Bayes text classifiers. In Proceedings of the Twentieth International Conference on Machine Learning, 2003.
• 30: Gary Robinson, A statistical approach to the spam problem, Linux Journal, v.2003 n.107, p.3, March 2003
• 31: M. Sauban and B. Pfahringer. Text categorisation using document profiling. In Proceedings of PKDD 2003, pages 411--422, 2003.
• 32: K. Schneider. Techniques for improving the performance of naive Bayes for text classification. In Proceedings of CICLing 2005, pages 682--693, 2005.
• 33: P. Soucy and G. Mineau. Beyond TFIDF weighting for text categorization in the vector space model. In Proceedings of the Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005), pages 1130--1135, 2005.
• 34: Haoran Wu , Tong Heng Phang , Bing Liu , Xiaoli Li, A refinement approach to handling model misfit in text categorization, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775078]
• 35: W. Yih, J. Goodman, and G. Hulten. Learning at low false positive rates. In Proceedings of the 3rd Conference on Email and Anti-Spam (CEAS-2006), 2006.
• 36: Zijian Zheng , Geoffrey I. Webb , Kai Ming Ting, Lazy Bayesian Rules: A Lazy Semi-Naive Bayesian Learning Technique Competitive to Boosting Decision Trees, Proceedings of the Sixteenth International Conference on Machine Learning, p.493-502, June 27-30, 1999

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Text analysis

General Terms:
Algorithms, Performance

Keywords:
email spam detection, high precision text classification, low false positive rates, naive bayes