Rule extraction from linear support vector machines

ABSTRACT

We describe an algorithm for converting linear support vector machines and any other arbitrary hyperplane-based linear classifiers into a set of non-overlapping rules that, unlike the original classifier, can be easily interpreted by humans. Each iteration of the rule extraction algorithm is formulated as a constrained optimization problem that is computationally inexpensive to solve. We discuss various properties of the algorithm and provide proof of convergence for two different optimization criteria We demonstrate the performance and the speed of the algorithm on linear classifiers learned from real-world datasets, including a medical dataset on detection of lung cancer from medical images. The ability to convert SVM's and other "black-box" classifiers into a set of human-understandable rules, is critical not only for physician acceptance, but also to reducing the regulatory barrier for medical-decision support systems based on such classifiers.

REFERENCES

• 1: D. P. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont, MA, 1995.
• 2: Dimitri P. Bertsekas. Projected Newton methods for optimization problems with simple constraints. SIAM Journal on Control and Optimization, 20:221--246, 1982.
• 3: F. Beyer, L. Zierott, J. Stoeckel, W. Heindel, and D. Wormanns. Computer-assisted detection (cad) of pulmonary nodules at mdct: Can cad be used as concurrent reader? In Proceeding of the 11th European Congress of Radiology, Viena, Austria, March 2005. To appear.
• 4: Bruce G. Buchanan , Edward H. Shortliffe, Rule Based Expert Systems: The Mycin Experiments of the Stanford Heuristic Programming Project (The Addison-Wesley series in artificial intelligence), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 5: Paul S. Bradley , O. L. Mangasarian, Feature Selection via Concave Minimization and Support Vector Machines, Proceedings of the Fifteenth International Conference on Machine Learning, p.82-90, July 24-27, 1998
• 6: Vladimir S. Cherkassky , Filip Mulier, Learning from Data: Concepts, Theory, and Methods, John Wiley & Sons, Inc., New York, NY, 1998
• 7: Glenn Fung , Olvi L. Mangasarian, Proximal support vector machine classifiers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.77-86, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502527]
• 8: G. Fung, O. L. Mangasarian, and J. Shavlik. Knowledge-based support vector machine classifiers. Technical Report 01-09, Data Mining Institute, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, November 2001. ftp://ftp.cs.wisc.edu/pub/dmi/tech-reports/01-09.ps, NIPS 2002 Proceedings, to appear.
• 9: Glenn Fung, The disputed federalist papers: SVM feature selection via concave minimization, Proceedings of the 2003 conference on Diversity in computing, p.42-46, October 15-18, 2003, Atlanta, Georgia, USA [doi>10.1145/948542.948551]
• 10: Franz J. Kurfess, Neural Networks and Structured Knowledge: Rule Extraction andApplications, Applied Intelligence, v.12 n.1-2, p.7-13, January-April 2000 [doi>10.1023/A:1008344602888]
• 11: O. L. Mangasarian. Generalized support vector machines. In A. Smola, P. Bartlett, B. Schölkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, pages 135--146, Cambridge, MA, 2000. MIT Press. ftp://ftp.cs.wisc.edu/math-prog/tech-reports/98-14.ps.
• 12: O. L. Mangasarian, W. N. Street, and W. H. Wolberg. Breast cancer diagnosis and prognosis via linear programming. Operations Research, 43(4):570--577, July-August 1995.
• 13: S. Mika, G. Rätsch, J. Weston, B. Schölkopf, and K.-R. Müller. Fisher discriminant analysis with kernels. In Y.-H. Hu, J. Larsen, E. Wilson, and S. Douglas, editors, Neural Networks for Signal Processing IX, pages 41--48. IEEE, 1999.
• 14: P. M. Murphy and D. W. Aha. UCI machine learning repository, 1992. www.ics.uci.edu/ mlearn/MLRepository.html.
• 15: Haydemar Nunez, Cecilio Angulo, and Andreu Catal. Rule extraction from support vector machines. In ESANN'2002 proceedings - European Symposium on Artificial Neural Networks, pages 107-112. d-side, 2002.
• 16: K. Preston. Computer processing of biomedical images. Computer, 9:54--68, 1976.
• 17: A. Tickle R. Andrews, J. Diederich. A survey and critique of techniques for extracting rules from trained artificial neural networks. Knowledge-Based Systems, 8:373--389, 1995.
• 18: L. B. Lusted R. S. Ledley. Reasoning foundations of medical diagnosis. Science, 130:9--21, 1959.
• 19: J. Roehrig. The promise of cad in digital mammography. European Journal of Radiology, 31:35--39, 1999.
• 20: Geoffrey G. Towell , Jude W. Shavlik, Extracting Refined Rules from Knowledge-Based Neural Networks, Machine Learning, v.13 n.1, p.71-101, Oct. 1993 [doi>10.1023/A:1022683529158]
• 21: J. A. K. Suykens , J. Vandewalle, Least Squares Support Vector Machine Classifiers, Neural Processing Letters, v.9 n.3, p.293-300, June 1999 [doi>10.1023/A:1018628609742]
• 22: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.m Miscellaneous

General Terms:
Algorithms

Keywords:
linear classifiers, mathematical programming, medical decision-support, rule extraction