...

PPT - University of British Columbia

by user

on
Category:

design

3

views

Report

Comments

Transcript

PPT - University of British Columbia
Fast Krylov Methods for N-Body Learning
Maryam Mahdaviani, Nando de Freitas, Yang Wang and Dustin Lang, University of British Columbia
Experimental results
Step 2: Fast N-Body Methods
O(N2 x Number of
Iterations)
O(NlogN x Number of Iterations)
}
Fast Gauss Transform (FGT)
Improved FGT (IFGT)
Spectral clustering
to predict the labels of 128-dimensional SIFT features for object class detection and
localization. Thousands of features per image => BIG covariance matrix
Fast Multipole Methods (Greengard et al):
We present a family of low storage, fast algorithms for:
Gaussian Processes with Large Dimensional Features: Using GPs
Work in low
dimensions
but O(N)
Dual Trees (Gray & Moore)
Dimensionality reduction
Gaussian processes
Kernel methods
xi
The inverse problem (e.g. in GPs) and the eigenvalue problem (e.g. in
spectral clustering) have a computational cost of O(N3) and storage
requirement O(N2) in the number of data points N.
Step 1: Krylov subspace iteration
O(N3
)
O(N2 x Number of Iterations)
Arnoldi
GMRES for solving Ax = b
xi
Xj’s
vi
( lower )
vi
( upper)
N
(x i , x j )  a(d
( upper)
(xi , x j )  a(d
( lower )
(xi , x j )) q j
j 1
N
(xi , x j )) q j
Xj’s
Spectral Clustering and Image Segmentation: A generalized
eigenvalue problem.
j 1
1 (upper)
( lower )
~
vi (x i , x j )  (vi
(x i , x j )  vi
(x i , x j ))
2
1 (upper)
( lower )
ei (x i , x j )  (vi
(x i , x j )  vi
(x i , x j ))
2
And the storage is now O(N) instead of O(N2)
Does it still work with step 2?
But how do the errors accumulate over successive iterations?
Original
In the paper we prove that:
1) The deviation in residuals is upper bounded
Other similar Krylov Methods: Lanczos,
Conjugate Gradients, MINRES
Expensive Step:
N
v  Aq
vi   q a(xi ,x j )
j 1
(t )
j
(t )
Requiring solving two kernel estimates
IFGT
Dual Tree
Nystrom
Stochastic neighbor embedding: Projecting to low dimensions (Roweis
and Hinton)
2) The orthogonality of the Krylov subspace can be preserved
The upper-bounds in terms of the measured residuals
will enable us to design adaptive algorithms
i  1,2,..., M .
True
Manifold
Sampled Embedding Embedding of
data
of SNE
SNE+IFGT
Embedding on S-curve and Swiss-roll datasets
Fly UP