ECCV 2012 Tutorial T7

Additive Kernels and Explicit Embeddings for Large Scale Computer Vision Problems

Sunday October 7, 9:15 to 13:00, Room B 2F Affari

ECCV 2012 tutorial page link

Jianxin Wu (Nanyang Technological University, Singapore)
Andrea Vedaldi (Univ. of Oxford, UK)
Subhransu Maji (TTI Chicago, USA)
Florent Perronnin (Xerox Research Center Europe)


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 research-oriented 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.


Part 1: Additive kernels, learning algorithms, and software (90 min)
by: Jianxin Wu
  1. Background
    • Classifier in computer vision
    • Linear vs. non-linear SVM
  2. Introduction & Goals
    • Definition and typical usage of additive kernels
    • When & why they should be used
  3. The common computational bottleneck
    • Identify what is hindering the use of additive kernels in various tasks: SVM training and testing, kernel k-means clustering, kernel version of the Gaussian Process
    • how the additive property changes the problem
  4. 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
  5. Linear Regression based learning and Nystrom approximation
    • The non-symmetric 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 LR-SVM framework for general non-linear kernels
    • Nystrom low-rank approximation as special case of LR-SVM
  6. Lookup table based algorithms
    • Lookup table for PmSVM and their quality assurance
    • ICD: a lookup table based method for HIK
    • Additive kernels in the C4 object detection framework
    • Lookup table for kernel k-means clustering
  7. 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
  1. Introduction
    • What is a kernel feature map and why it is useful
    • Dense and sparse approximate feature maps
  2. Dense low-dimensional feature maps
    • Nyström's approximation: PCA in kernel space
    • homogeneous kernel map -- the analytical approach
    • addKPCA -- the empirical approach
    • non-additive kernes -- random Fourier features
  3. Sparse high-dimensional 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
  1. 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
  2. Learning additive classifiers directly
    • Motivation
    • An optimization framework (regularized empirical loss)
    • Search for efficient representations of the function and regularization
  3. Spline embeddings
    • Representation and regularization
    • Linearization and visualizing the implicit kernel
    • Efficiently solving the optimization
    • Computational tradeoffs
  4. Fourier embeddings
    • Representation
    • Regularization -- penalty on derivatives
    • Practical basis - orthogonal basis with orthogonal derivatives
  5. Experiments, Conclusions, Software, References
Part 4: Explicit embeddings (III): higher-order representations (30 min)
by Florent Perronnin
  1. Introduction
    • An explicit embedding view of the BoV
    • Higher order statistics
  2. A first example: the VLAD
    • Presentation of the VLAD descriptor
    • In which sense is it optimal?
  3. The Fisher Vector
    • The Fisher kernel, the Fisher Information matrix and the Fisher Vector
    • Application to images
    • Relationship to the BoV
  4. Other higher-order representations
    • Back to the VLAD
    • The Super Vector
  5. Large-scale results
    • ILSVRC 2010
    • ILSVRC 2011
    • ImageNet10K