Recent News
UNM receives $1.5 million to support computational workforce development
May 8, 2023
Tapia elected to Computing Research Association Board of Directors
March 3, 2023
UNM computer science students take part in HPC competition
March 3, 2023
Computer science professor, student part of AI panel on March 8
February 24, 2023
News Archives
Fast Algorithms for Support Vector Machines
April 5, 2005
- Date: Tuesday, April 5, 2005
- Time: 11:00 a.m.
- Place: Woodward 149
Dr. Don Hush dhush@lanl.gov
Los Alamos National Labs
This talk provides a brief introduction to support vector machines (SVMs) for machine learning and then describes some recent advances in the development of fast algorithms for solving the quadratic programming (QP) problem associated with the support vector machine (SVM) training process. Since the primal QP problem can be prohibitively large a smaller dual QP problem is solved and its solution mapped to a primal solution. Decomposition algorithms are arguably the most common type of algorithm used to solve the dual in practice. We describe a new class of decomposition algorithms (introduced by Simon) that produce an approximate solution to the dual in O(n2 ln(1/e)) time, where n is the number of data samples and e is the accuracy of the approximation. This is a substantial improvement over the previous best result of O(n5 ln(n)/e) for an algorithm we developed in 2003. We also describe a new O(n ln(n)) algorithm for mapping an approximate dual solution to an approximate primal solution. Finally we compare these new algorithms with algorithms currently used in practice.