Additive Kernels and Explicit Embeddings for Large Scale Computer Vision ProblemsSunday October 7, 9:15 to 13:00, Room B 2F AffariOrganizers Jianxin Wu (Nanyang Technological University, Singapore)
Abstract It is generally accepted in our community that: in many vision tasks, more training images will usually lead to better performance. Furthermore, recent advances have shown that additive kernel and explicit embeddings are the best performers in most visual classification tasks–a fact that has been repeatedly verified by various papers and researchoriented public contests (e.g., the ImageNet Large Scale Visual Recognition Challenge.) In this tutorial, we will introduce the theories, applications, algorithms, software, and practical issues of using additive kernels and explicit embeddings in various computer vision domains, especially when the problem scale is very large.
OutlinePart 1: Additive kernels, learning algorithms, and software (90 min)
by: Jianxin Wu  Background
 Classifier in computer vision
 Linear vs. nonlinear SVM
 Introduction & Goals
 Definition and typical usage of additive kernels
 When & why they should be used
 The common computational bottleneck
 Identify what is hindering the use of additive kernels in various tasks: SVM training and testing, kernel kmeans clustering, kernel version of the Gaussian Process
 how the additive property changes the problem
 The PmSVM algorithm
 The power mean family of additive kernels
 The dual coordinate descent framework
 The PmSVM algorithm based on linear regression
 A few important considerations in PmSVM
 Linear Regression based learning and Nystrom approximation
 The nonsymmetric kernel approximation from PmSVM
 Nystrom embedding for additive kernels are symmetric special cases
 PmSVM for all additive kernels
 Approximation quality of various approximations
 Choice of training examples
 the LRSVM framework for general nonlinear kernels
 Nystrom lowrank approximation as special case of LRSVM
 Lookup table based algorithms
 Lookup table for PmSVM and their quality assurance
 ICD: a lookup table based method for HIK
 Additive kernels in the C^{4} object detection framework
 Lookup table for kernel kmeans clustering
 Software and a few practical issues
 A list of software from myself
 A few important practical issue in using additive kernels
Part 2: Explicit embeddings (I): kernel feature maps (30 min) by Andrea Vedaldi
 Introduction
 What is a kernel feature map and why it is useful
 Dense and sparse approximate feature maps
 Dense lowdimensional feature maps
 Nyström's approximation: PCA in kernel space
 homogeneous kernel map  the analytical approach
 addKPCA  the empirical approach
 nonadditive kernes  random Fourier features
 Sparse highdimensional feature maps
 Sparse coding in kernel space
 Intersection Kernel Map revisited
 Product Quantisation as a sparse feature map
Part 3: Explicit embeddings (II): generalized additive models (30 min) by Subhransu Maji
 Summary of the tutorial so far
 Additive kernels are widely used
 Additive kernel SVMs can be efficiently evaluated
 Additive kernel SVMs can be efficiently trained
 Learning additive classifiers directly
 Motivation
 An optimization framework (regularized empirical loss)
 Search for efficient representations of the function and regularization
 Spline embeddings
 Representation and regularization
 Linearization and visualizing the implicit kernel
 Efficiently solving the optimization
 Computational tradeoffs
 Fourier embeddings
 Representation
 Regularization  penalty on derivatives
 Practical basis  orthogonal basis with orthogonal derivatives
 Experiments, Conclusions, Software, References
Part 4: Explicit embeddings (III): higherorder representations (30 min) by Florent Perronnin
 Introduction
 An explicit embedding view of the BoV
 Higher order statistics
 A first example: the VLAD
 Presentation of the VLAD descriptor
 In which sense is it optimal?
 The Fisher Vector
 The Fisher kernel, the Fisher Information matrix and the Fisher Vector
 Application to images
 Relationship to the BoV
 Other higherorder representations
 Back to the VLAD
 The Super Vector
 Largescale results
 ILSVRC 2010
 ILSVRC 2011
 ImageNet10K

