Partitioned logistic regression for spam filtering

ABSTRACT

Naive Bayes and logistic regression perform well in different regimes. While the former is a very simple generative model which is efficient to train and performs well empirically in many applications,the latter is a discriminative model which often achieves better accuracy and can be shown to outperform naive Bayes asymptotically. In this paper, we propose a novel hybrid model, partitioned logistic regression, which has several advantages over both naive Bayes and logistic regression. This model separates the original feature space into several disjoint feature groups. Individual models on these groups of features are learned using logistic regression and their predictions are combined using the naive Bayes principle to produce a robust final estimation. We show that our model is better both theoretically and empirically. In addition, when applying it in a practical application, email spam filtering, it improves the normalized AUC score at 10% false-positive rate by 28.8% and 23.6% compared to naive Bayes and logistic regression, when using the exact same training examples.

REFERENCES

• 1: Ion Androutsopoulos , John Koutsias , Konstantinos V. Chandrinos , Constantine D. Spyropoulos, An experimental comparison of naive Bayesian and keyword-based anti-spam filtering with personal e-mail messages, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.160-167, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345569]
• 2: Paul N. Bennett, Using asymmetric distributions to improve text classifier probability estimates, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860457]
• 3: Paul N. Bennett , Jaime Carbonell , John Lafferty, Building reliable metaclassifiers for text learning, Carnegie Mellon University, Pittsburgh, PA, 2006
• 4: S. Bickel and T. Scheffer. Dirichlet-enhanced spam filtering based on biased samples. In Advances in Neural Information Processing Systems 19 (NIPS--2006), pages 161--168, 2007.
• 5: G. Cormack. TREC 2006 spam track overview. In Proceedings of TREC-2006, 2006.
• 6: G. Cormack and T. Lynam. TREC 2005 spam track overview. In Proceedings of TREC-2005, 2005.
• 7: Thomas G. Dietterich, Approximate statistical tests for comparing supervised classification learning algorithms, Neural Computation, v.10 n.7, p.1895-1923, Oct. 1998 [doi>10.1162/089976698300017197]
• 8: Thomas G. Dietterich, Ensemble Methods in Machine Learning, Proceedings of the First International Workshop on Multiple Classifier Systems, p.1-15, June 21-23, 2000
• 9: 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]
• 10: H. Drucker, D. Wu, and V. Vapnik. Support vector machines for Spam categorization. IEEE Transactions on Neural Networks, 10(5):1048--1054, 1999.
• 11: D. Fallows. Spam: How it is hurting email and degrading life on the Internet. Pew Internet and American Life Project, October 2003.
• 12: 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]
• 13: J. Goodman and W. Yih. Online discriminative spam filter training. In CEAS-2006, 2006.
• 14: J. He and B. Thiesson. Asymmetric gradient boosting with application to spam filtering. In CEAS-2007, 2007.
• 15: Shlomo Hershkop , Salvatore J. Stolfo, Combining email models for false positive reduction, 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.1081885]
• 16: G. Hinton. Products of experts. In Proc. of the 9thInternational Conference on Artificial Neural Networks (ICANN99), pages 1--6, 1999.
• 17: Joseph M. Kahn, A generative Bayesian model for aggregating experts' probabilities, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.301-308, July 07-11, 2004, Banff, Canada
• 18: Josef Kittler , Mohamad Hatef , Robert P. W. Duin , Jiri Matas, On Combining Classifiers, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.3, p.226-239, March 1998 [doi>10.1109/34.667881]
• 19: Aleksander Kolcz , Wen-tau Yih, Raising the baseline for high-precision text classifiers, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281237]
• 20: B. Leiba, J. Ossher, V. T. Rajan, R. Segal, and M. N. Wegman. SMTP path analysis. In CEAS-2005, 2005.
• 21: Daniel Lowd , Christopher Meek, Adversarial learning, 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.1081950]
• 22: D. Lowd and C. Meek. Good word attacks on statistical spam filters. In CEAS--2005, 2005.
• 23: V. Metsis, V. Androutsopoulos, and G. Paliouras. Spam filtering with naive Bayes -- which naive Bayes? In CEAS-2006, 2006.
• 24: A. Ng and M. Jordan. On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes. In Proceedings of NIPS 14, 2002.
• 25: K. Nigam, J. Lafferty, and A. McCallum. Using maximum entropy for text classification. In IJCAI-99 Workshop on Machine Learning for Information Filtering, 1999.
• 26: R. Raina, Y. Shen, A. Ng, and A. McCallum. Classification with hybrid generative/discriminative models. In Proceedings of NIPS 16, 2004.
• 27: J. Rennie, L. Shih, J. Teevan, and D. Karger. Tackling the poor assumptions of naive Bayes text classifiers. In ICML-2003, 2003.
• 28: M. Sahami, S. Dumais, D. Heckerman, and E. Horvitz. A Bayesian approach to filtering junk e-mail. In AAAI-98 Workshop on Learning for Text Categorization, 1998.
• 29: G. Sakkis, I. Androutsopoulos, G. Paliouras, V. Karkaletsis,C. D. Spyropoulos, and P. Stamatopoulos. Stacking classifiers for anti-spam filtering of e-mail. In EMNLP-2001,pages 44--50, 2001.
• 30: D. Sculley , Gabriel M. Wachman, Relaxed online SVMs for spam filtering, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277813]
• 31: R. Segal. Combining global and personal anti--spam filtering.In CEAS--2007, 2007.
• 32: Andrew Smith , Trevor Cohn , Miles Osborne, Logarithmic opinion pools for conditional random fields, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.18-25, June 25-30, 2005, Ann Arbor, Michigan [doi>10.3115/1219840.1219843]
• 33: A. Smith and M. Osborne. Using gazetteers in discriminative information extraction. In Proceedings of the Tenth Conference on Computational Natural Language Learning(CoNLL-X), pages 133--140, 2006.
• 34: Charles Sutton , Michael Sindelar , Andrew McCallum, Reducing weight undertraining in structured discriminative learning, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, p.89-95, June 04-09, 2006, New York, New York [doi>10.3115/1220835.1220847]
• 35: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 36: W. Yih, J. Goodman, and G. Hulten. Learning at low false positive rates. In CEAS--2006, 2006.
• 37: W. Yih, R. McCann, and A. Kolcz. Improving spam filtering by detecting gray mail. In CEAS--2007, 2007.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications
          Subjects: Electronic mail

General Terms:
Algorithms, Theory

Keywords:
email spam filtering, logistic regression, naive bayes