Solution Path Algorithms: An Efficient Model Selection Approach

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Solution Path Algorithms: An Efficient Model Selection Approach"

By

Mr. Gang Wang


Abstract

One of the fundamental problems in statistical machine learning is the
generic regularization optimization. The objective function of the
optimization problem under this regularization framework is comprised of
two parts, i.e., the loss and the regularizer. Besides the parameters we
aim to optimize, there are some other hyperparameters in the formulation,
e.g., the regularization parameter and the kernel hyperparameter, whose
values have to be specified in advance by the user. The optimal
hyperparameter value is data dependent, and prior knowledge is often
required to set its value properly. The traditional approach to this model
selection problem is to apply methods like cross validation to determine
the best choice among a number of prespecified hyperparameter values.
Extensive exploration, such as performing line search for one
hyperparameter or grid search for two hyperparameters, is usually used.
However, this requires training the model multiple times with different
hyperparameter values and hence is computationally prohibitive especially
when the number of candidate values is very large.

Solution path algorithms provide a new approach to the model selection
problem. Such algorithms attempt to calculate every solution for each
possible hyperparameter value without having to re-train the model
multiple times. Since it can rapidly generate the full path of solutions,
the optimal value can be found with a low extra computational cost through
estimating the generalization errors under different hyperparameter
values. For a large family of statistical learning models, the path of
solutions extends in a piecewise linear manner. Hence, it is efficient to
explore the entire solution path by monitoring the breakpoints only.
However, in some problems, the solution paths are nonlinear with respect
to a hyperparameter and it is challenging to have an efficient approach to
trace the nonlinear solution path.

In this thesis, we investigate this new class of algorithms. We provide a
general method investigating how to analyze the solution space of learning
models and how to derive their path-following algorithms. Based on this
method, we develop solution path algorithms for many learning models.
These algorithms have shown many advantages over previous problem-solving
approaches. Experimental results demonstrate that solution path algorithms
provide an efficient and effective approach to model selection.


Date:			Thursday, 20 December 2007

Time:			4:00p.m.-6:00p.m.

Venue:			Room 3501
			Lifts 25-26

Chairman:		Prof. Hong XUE (BICH)

Committee Members:	Prof. Frederick H. LOCHOVSKY (Supervisor)
			Prof. Dit-Yan YEUNG (Supervisor)
			Prof. James KWOK
			Prof. Nevin L. ZHANG
			Prof. Michael K. Y. WONG (PHYS)
			Prof. Trevor John HASTIE (Statistics, Stanford Univ.)


**** ALL are Welcome ****