  


Interior point methods for massive support vector machines
Michael Ferris (ferriscs.wisc.edu) Abstract: We investigate the use of interior point methods for solving quadratic programming problems with a small number of linear constraints where the quadratic term consists of a lowrank update to a positive semidefinite matrix. Several formulations of the support vector machine fit into this category. An interesting feature of these particular problems is the volume of data, which can lead to quadratic programs with between 10 and 100 million variables and a dense $Q$ matrix. We use OOQP, an objectoriented interior point code, to solve these problem because it allows us to easily tailor the required linear algebra to the application. Our linear algebra implementation uses a proximal point modification to the underlying algorithm, and exploits the ShermanMorrisonWoodbury formula and the Schur complement to facilitate efficient linear system solution. Since we target massive problems, the data is stored outofcore and we overlap computation and I/O to reduce overhead. Results are reported for several linear support vector machine formulations demonstrating the reliability and scalability of the method. Keywords: support vector machine, interiorpoint method, linear algebra Category 1: Applications  Science and Engineering (DataMining ) Citation: Data Mining Institute Technical Report 0005, Computer Sciences Department University of Wisconsin, Madison. Download: [Postscript] Entry Submitted: 08/22/2000 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  