Documentation - C API

homkermap.h File Reference

Homogeneous kernel map. More...

#include "generic.h"
#include <math.h>

Data Structures

struct  VlHomogeneousKernelMap
 Homogeneous kernel map. More...

Enumerations

enum  VlHomogeneousKernelType { VlHomogeneousKernelIntersection = 0, VlHomogeneousKernelChi2, VlHomogeneousKernelJS }
 

Type of kernel.

More...
enum  VlHomogeneousKernelMapWindowType { VlHomogeneousKernelMapWindowUniform = 0, VlHomogeneousKernelMapWindowRectangular = 1 }
 

Type of spectral windowing function.

More...

Functions

VlHomogeneousKernelMapvl_homogeneouskernelmap_new (VlHomogeneousKernelType kernelType, double gamma, vl_size order, double period, VlHomogeneousKernelMapWindowType windowType)
 Create a new homgeneous kernel map.
void vl_homogeneouskernelmap_delete (VlHomogeneousKernelMap *self)
 Delete a map object.
void vl_homogeneouskernelmap_evaluate_d (VlHomogeneousKernelMap const *self, double *destination, vl_size stride, double x)
 Evaluate map.
void vl_homogeneouskernelmap_evaluate_f (VlHomogeneousKernelMap const *self, float *destination, vl_size stride, double x)
 Evaluate map.

Detailed Description

Homogeneous kernel map

homkermap.h is an implementation of the homogeneous kernel maps introduced in [1,2]. Such maps are efficient linear representation of popular kernels such as the intersection, Chi2, and Jensen-Shannon.

References

  • [1] A. Vedaldi and A. Zisserman, Efficient Additive Kernels via Explicit Feature Maps, in Proc. CVPR, 2010.
  • [2] A. Vedaldi and A. Zisserman, Efficient Additive Kernels via Explicit Feature Maps, submitted to PAMI, 2011.

Overview

An homogeneous kernel map is a finite dimensional linear approximation of an homgeneous kernel. The homogeneous kernels includes the intersection Chi2, intersection, and Jensen-Shannon, among many others.

Formally, let $ x,y \in \mathbb{R}_+ $ be non-negative scalars and Let $ k(x,y) \in \mathbb{R} $ be an homogeneous kernel. Then the Chi2 and intersection kernels are given by

\[ k_{\mathrm{inters}}(x,y) = \min\{x, y\}, \quad k_{\chi^2}(x,y) = 2 \frac{(x - y)^2}{x+y}. \]

An homogeneous kernel map of order n is a vectorial function $ \Psi(x) \in \mathbb{R}^{2n+1} $ such that, for any choice of $ x, y \in \mathbb{R}_+ $, one has

\[ k(x,y) \approx \langle \Psi(x), \Psi(y) \rangle. \]

Additive kernels

A feature map $ \Psi(\mathbf{x}) $ for an additive combination of homogeneous kernels $ K(\mathbf{x},\mathbf{y}) = \sum_{i=1}^d k(x_i,y_i) $ can be obtained stacking the vectors $ [ \Psi(x_1), \dots, \Psi(x_n) $. vl_homogeneouskernelmap_evaluate_d is designed to do this stacking transparently. Note that the combined feature $ \Psi(\mathbf{x}) $ has dimension $ d(2n+1) $.

Extension to the negative reals

Any positive (semi-)definite kernel $ k(x,y) $ defined on the non-negative reals $ x,y \in \mathbb{R}_+ $ can be extended to the entiere real line by using the definition:

\[ k_\pm(x,y) = \operatorname{sign}(x) \operatorname{sign}(y) k(|x|,|y|). \]

The homogeneous kernel map implements this extension by defining $ \Psi_\pm(x) = \operatorname{sign}(x) \Psi(|x|) $. Note that other extensions are possible, such as

\[ k_\pm(x,y) = H(xy) \operatorname{sign}(y) k(|x|,|y|) \]

where $ H $ is the Heavyside function, but may require higher dimensional feature maps.

Homogeneity order

Any (1-)homogeneous kernel $ k_1(x,y) $ can be extended to a so called gamma-homgeneous kernel $ k_\gamma(x,y) $ by the definition

\[ k_\gamma(x,y) = (xy)^{\frac{\gamma}{2}} \frac{k_1(x,y)}{\sqrt{xy}} \]

Smaller value of $ \gamma $ enhance the kernel non-linearity and are sometimes beneficial in applications (see [1,2] for details).

Windowing and period

This section discusses aspects of the homogeneous kernel map which are more technical and may be skipped. The homogeneous kernel map approximation is based on periodicizing the kernel; given the kernel signature

\[ \Kappa(\lambda) = k(e^{\frac{\lambda}{2}}, e^{-\frac{\lambda}{2}}) \]

the homogeneous kerne map is a feature map for the windowed and periodicized kernel whose signature is given by

\[ \hat{\mathcal{K}}(\lambda) = \sum_{i=-\infty}^{+\infty} \mathcal{K}(\lambda + k \Lambda) W(\lambda + k \Lambda) \]

where $ W(\lambda) $ is a windowing function and $ \Lambda $ is the period. This implementation of the homogeneous kernel map supports the use of a uniform window ( $ W(\lambda) = 1 $) or of a rectangular window ( $ W(\lambda) = \operatorname{rect}(\lambda/\Lambda) $). Note that $ \lambda = \log(y/x) $ is equal to the logarithmic ratio of the arguments of the kernel. Empirically, the rectangular window seems to have a slight edge in applications.

Usage

The homogeneous kernel map is implemented as an object of type VlHomogeneousKernelMap. To use thois object, first create an instance by vl_homogeneouskernelmap_new, then use vl_homogeneouskernelmap_evaluate_d or vl_homogeneouskernelmap_evaluate_f (depdening on whether the data is double or float) to compute the feature map $ \Psi(x) $. When done, dispose of the object by calling vl_homogeneouskernelmap_delete.

The constructor vl_homogeneouskernelmap_new requires the kernel type kernel (see VlHomogeneousKernelType), the homogeneity order gamma (use one for the standard kernels), the approximation order order (usually order one is enough), the period period (use a negative value to use the default period), and a window type window (use VlHomogeneousKernelMapWindowRectangular if unsure). The approximation order trades off the quality and dimensionality of the approximation. The resulting feature map $ \Psi(x) $, computed by vl_homogeneouskernelmap_evaluate_d or vl_homogeneouskernelmap_evaluate_f , is 2*order+1 dimensional.

The code pre-computes the map $ \Psi(x) $ for efficient evaluation. The table spans values of $ x $ in the range $[2^{-20}, 2^{8}) $. In particular, values smaller than $ 2^{-20} $ are treated as zeroes (which result in a null feature).

Technical details

The code uses the expressions given in [1,2] to compute in closed form the maps $ \Psi(x) $ for the suppoerted kernel types. For efficiency reasons, it tabulates $ \Psi(x) $ when the homogeneous kernel map object is created.

The interal table stores $ \Psi(x) \in \mathbb{R}^{2n+1} $ for $ x \geq 0 $ by sampling this variable. In particular, x is decomposed as

   x = mantissa * (2**exponent),
   minExponent <= exponent <= maxExponent,
   1 <= matnissa < 2.
 

Each octave is further subdivided in numSubdivisions sublevels.

When the map $ \Psi(x) $ is evaluated, x is decomposed back into exponent and mantissa, and the result is computed by bilinear interpolation from the appropriate table entries.

Author:
Andrea Vedaldi

Enumeration Type Documentation

Enumerator:
VlHomogeneousKernelMapWindowUniform 

uniform window

VlHomogeneousKernelMapWindowRectangular 

rectangular window

Enumerator:
VlHomogeneousKernelIntersection 

intersection kernel

VlHomogeneousKernelChi2 

Chi2 kernel

VlHomogeneousKernelJS 

Jensen-Shannon kernel


Function Documentation

void vl_homogeneouskernelmap_delete ( VlHomogeneousKernelMap self )
Parameters:
selfmap object. The function deletes the specified map object.
vl_homogeneouskernelmap_evaluate_d ( VlHomogeneousKernelMap const *  self,
double *  destination,
vl_size  stride,
double  x 
)
Parameters:
selfmap object.
destinationoutput buffer.
stridestride of the output buffer.
xvalue to expand.

The function evaluates the feature map on x and stores the resulting 2*order+1 dimensional vector to destination[0], destination[stride], destination[2*stride], ....

vl_homogeneouskernelmap_evaluate_f ( VlHomogeneousKernelMap const *  self,
float *  destination,
vl_size  stride,
double  x 
)
Parameters:
selfmap object.
destinationoutput buffer.
stridestride of the output buffer.
xvalue to expand.

The function evaluates the feature map on x and stores the resulting 2*order+1 dimensional vector to destination[0], destination[stride], destination[2*stride], ....

VlHomogeneousKernelMap* vl_homogeneouskernelmap_new ( VlHomogeneousKernelType  kernelType,
double  gamma,
vl_size  order,
double  period,
VlHomogeneousKernelMapWindowType  windowType 
)
Parameters:
kernelTypetype of homogeneous kernel.
gammakernel homogeneity degree.
orderapproximation order.
periodkernel period.
windowTypetype of window used to truncate the kernel.
Returns:
the new homogeneous kernel map.

The function intializes a new homogeneous kernel map for the specified kernel type, homogeneity degree, approximation order, period, and truncation window. See Overview for details.

The homogeneity degree gamma must be positive (the standard kernels are obtained by setting gamma to 1). When unsure, set windowType to VlHomogeneousKernelMapWindowRectangular. The period should be non-negative; specifying a negative or null value causes the function to switch to a default value.

The function returns NULL if there is not enough free memory.