Date 
September 26, 2011 
Speaker 
Dr. Masayuki Karasuyama, Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology 
Title 
Optimal Solution Path Algorithm for Machine Learning:
Analytical Approach to Solving Support Vector Machines

Abstract 
Many machine learning algorithms are formulated as mathematical
optimization problems. These optimization problems are often
parametrized by one or more problem parameters such as regularization
parameter. The solution path algorithm (a. k. a. parametric
optimization) is an effective technique for solving a sequence of
parametrized optimization problems. For example, in the model selection
scenario, extensive exploration for the optimal regularization parameter
is needed to get good generalization performance. However, to solve
optimization problems for each regularization parameter is often
timeconsuming. In such a case, the solution path algorithm can
efficiently investigate the entire solutions for different
regularization parameters. This approach is faster than the extensive
grid search because it directly follows the changes of solutions
analytically without resolving optimization problem repeatedly.
In this talk, I will give brief introduction to the solution path
algorithms in machine learning and our recent study in this topic:
solution path algorithm for the instanceweighted support vector
machines. The instanceweighted learning is an instanceweighted variant
of empirical risk minimization and it plays an important role in various
machine learning tasks such as nonstationary data analysis,
heteroscedastic data modeling, covariate shift adaptation, learning to
rank and transductive learning. We develop a novel solution path
algorithm for the instanceweighted support vector machines which
efficiently updates the optimal solution when the instanceweights are
changed dynamically or adaptively. Since our approach is quite general,
it can be applied to various machine learning problems. I will
demonstrate usefulness of our approach through several examples of
applications for the above tasks.

