This column is also available in pdf: filename kernelCoreSetMEB.pdf

1 Smallest enclosing ball and coresets

Let = {p₁,…,p_n} be a finite point set. In ℝ^d, the Smallest Enclosing Ball (SEB) SEB() with radius r(SEB()) is fully determined by s points of lying on the boundary sphere [15, 9], with 2 ≤ s ≤ d + 1 (assuming general position with no d + 2 cospherical points). Computing efficiently the SEB in finite dimensional space has been thoroughly investigated in computational geometry [5].

A (1 + ϵ)-approximation of the SEB is a ball covering with radius (1 + ϵ)r(SEB()). A simple iterative approximation algorithm [1] (BC algorithm) proceeds iteratively as follows: Set c⁽⁰⁾ = p₁ and update the current center as

⊂

⊂

2 Smallest enclosing ball in feature space

In machine learning, one is interested in defining the data domain [13]. For example, this is useful for anomaly detection that can be performed by checking whether a new point belongs to the domain (inlier) or not (outlier). The Support Vector Data Description [13, 14] (SVDD) defines the domain of data by computing an enclosing ball in the feature space induced by a given kernel k(⋅,⋅) (e.g., polynomial or Gaussian kernels). The Support Vector Clustering [3] (SVC) further builds on the enclosing feature ball to retrieve clustering in the data space.

Let k(⋅,⋅) be a kernel [12] so that k(x,y) = ⟨Φ(x),Φ(y)⟩ (kernel trick) for a feature map Φ(x) : ℝ^d → ℝ^D, where ⟨⋅,⋅⟩ denotes the inner product in the Hilbert feature space F. Denote by = {ϕ₁,…,ϕ_n} the corresponding feature vectors in F, with ϕ_i = Φ(p_i). SVDD (and SVC) needs to compute SEB().

We can kernelize the BC algorithm [1] by maintaining an implicit representation of the feature center φ = ∑ _i=1ⁿα_iϕ_i where α ∈ Δ_n is a normalized unit positive weight vector (with Δ_n denoting the (n- 1)-dimensional probability simplex). The distance between the feature center φ = ∑ _iα_iϕ(p_i) = ∑ _iα_iϕ_i and a feature point ϕ(p) is calculated as follows:

Therefore at iteration i, the farthest distance of the current center φ_i to a point of in the feature space can be computed using the implicit feature center representation: max_j∈[d]∥φ_i - ϕ(p_j)∥. Denote by f_i the index of the farthest point in F. Then we update the implicit representation of the feature center by updating the weight vector α as follows:

Observe that at iteration i, at most i + 1 coordinates of α are non-zero (sparse implicit representation), so that the maximum distance of the center to the point set can be computed via Eq. 2 in O(ni²). Thus it follows that the kernelized BC algorithm costs overall O()-time. The proof of the approximation quality of the BC algorithm relies on the Pythagoras’s theorem [6, 7] that holds in finite-dimensional Hilbert spaces. Although we used an implicit feature map Φ (e.g., Gaussian kernel feature map), we can approximate feature maps by finite-dimensional feature maps using the randomized Fourier feature maps  [11].

This note is closely related to the work [4] where the authors compute a feature SEB for each class of data (points having the same label), and perform classification using the Voronoi diagrams defined on the feature (approximated) circumcenters.

Notice that the choice of the kernel for SVDD/SVC is important since the feature SEB has at most D + 1 support vectors (without outliers) in general position, where D is the dimension of the feature space. Thus for a polynomial kernel, the number of support vectors is bounded (and so is the number of clusters retrieved using SVC). Another byproduct of the kernelized BC algorithm is that it proves that the feature circumcenter is contained in the convex hull of the feature vectors (since α encodes a convex combination of the feature vectors).

3 Some kernel examples

The feature map of the polynomial kernel k_P(x,y) = ^a (with c ≥ 0) is finite-dimensional (F = ℝ^D with D = ). For a = 2, we get the explicit feature map:

The feature map Φ_G(x) of the Gaussian kernel k_G(x,y) = exp(-γ∥x - y∥²) (Radial Basis Function, RBF) is infinite-dimensional (D = ∞):

References