Transcript Document

Multiple Parameter Selection of
Support Vector Machine
Hung-Yi Lo
Spoken Language Group
Chinese Information Processing Lab.
Institute of Information Science
Academia Sinica, Taipei, Taiwan
http://sovideo.iis.sinica.edu.tw/SLG/index.htm
Outline
2
 Phonetic Boundary Refinement Using Support Vector Machine
(ICASSP’07, ICSLP’07)
 Automatic Model Selection for Support Vector Machine
(Distance Metric Learning for Support Vector Machine)
2007/07/11
3
Automatic Model Selection for
Support Vector Machine
(Distance Metric Learning for
Support Vector Machine)
2007/07/11
Automatic Model Selection for SVM
 The problem of choosing a good parameter or model setting for a
better generalization ability is the so called model selection.
 We have two parameter in support vector machine:
 regularization variable C
 Gaussian kernel width parameter γ
 Support vector machine formulation:
min
(w, b,  )  R
s. t.
n 1 m
1
   ww
2
D( Aw  eb)    e
 0
 Gaussian kernel:
K ( x, y)  e i1

2007/07/11
n
( xi  yi ) 2
(QP)
4
Automatic Model Selection for SVM
 C.-M. Huang, Y.-J. Lee, Dennis K. J. Lin and S.-Y. Huang. "Model Selection
for Support Vector Machines via Uniform Design", A special issue on
Machine Learning and Robust Data Mining of Computational Statistics
and Data Analysis. (To appear)
2007/07/11
5
Automatic Model Selection for SVM
 Strength:
 Automate the training progress of SVM, nearly no humaneffort needed.
 The object of the model selection procedure is directly related
to testing performance. In my experimental experience, testing
correctness always better than the results of human-tuning.
 Nested uniform-designed-based method is much faster than
exhaustive grid search.
 Weakness:
 No closed-form solution, need doing experimental search.
 Time consuming.
2007/07/11
6
Distance Metric Learning
 L. Yang "Distance Metric Learning: A Comprehensive
Survey", Ph.D. survey
 Many works have done to learn a quadratic (Mahalanobis)
distance measures:
dij  ( xi  x j )Q( xi  x j )
where xi is the input vector for the ith training case and Q is a
symmetric, positive semi-definite matrix.
 Distance metric learning is equivalent to feature transformation:
d ij  ( xi  x j )AA( xi  x j )
 (Axi  Ax j )(Axi  Ax j )
 ( yi  y j )( yi  y j )
2007/07/11
7
Global Distance Metric Learning
by Convex Programming
Supervised
Distance Metric Learning
Local
Unsupervised
Distance Metric Learning
Distance Metric Learning
based on SVM
Kernel Methods for
Distance Metrics Learning
2007/07/11
Local Adaptive Distance
Metric Learning
Relevant Component Analysis
Neighborhood Components Analysis
Linear embedding
PCA, MDS
Nonlinear embedding
LLE, ISOMAP, Laplacian Eigenmaps
Large Margin Nearest Neighbor
Based Distance Metric Learning
Cast Kernel Margin
Maximization into a SDP problem
Kernel Alignment with SDP
Learning with Idealized Kernel
8
Distance Metric Learning
 Strength:
 Usually have closed-form solution.
 Weakness:
 The object of the distance metric learning is based some data
distribution criterion, but not the evaluation performance.
2007/07/11
9
10
Automatic Multiple Parameter Selection for SVM
 Gaussian kernel:
K ( x, y)  e i1
n

( xi  yi ) 2
 Traditionally, each dimension of the feature vector will be
normalized into zero-mean and one standard deviation. So each
dimension have the same contribute to the kernel.
 However, some features should be more important.
K ( x, y)  e i1

n
 i ( xi  yi ) 2
which is equivalent to diagonal distance metric learning:
K ( x, y)  e
2007/07/11
 ( x  y )Q ( x  y )
11
Automatic Multiple Parameter Selection for SVM
 I would like to do this task by experimental search, and
incorporate data distribution criterion as some heuristic.
 Much more time consuming, might only applicable on small data.
 Feature selection is another similar task and can be solved by
experimental search, while the diagonal of the matrix is zero or
one.
 Applicable on large data.
 But, already have many publication.
K ( x, y)  e
2007/07/11
 ( x  y )Q ( x  y )
12
Thank you!
2007/07/11