Computational units induced by convolutional kernels together with biologically inspired perceptrons belong to the most widespread types of units used in neurocomputing. Radial convolutional kernels with varying widths form RBF (radial-basis-function) networks and these kernels with fixed widths are used in the SVM (support vector machine) algorithm. We investigate suitability of various convolutional kernel units for function approximation. We show that properties of Fourier transforms of convolutional kernels determine whether sets of input-output functions of networks with kernel units are large enough to be universal approximators. We compare these properties with conditions guaranteeing positive semidefinitness of convolutional kernels.
Computational units induced by radial and convolutional
kernels together with perceptrons belong to the most
widespread types of units used in neurocomputing. In
contrast to biologically inspired perceptrons [
Other important kernel units are units induced by
convolutional kernels in the form of translations of functions of
one vector variable. Isotropic RBF units can be viewed as
non symmetric kernel units obtained from convolutional
radial kernels by adding a width parameter. Variability
of widths is a strong property. It allows to apply
arguments based on classical results on approximation of
functions by sequences of their convolutions with scaled bump
functions to prove universal approximation capabilities of
many types of RBF networks [
On the other hand, symmetric positive semidefinite
kernels (which include some classes of RBFs with fixed
widths parameters) benefit from geometrical properties of
reproducing kernel Hilbert spaces (RKHS) generated by
these kernels. These properties allow an extension of
the maximal margin classification from finite dimensional
spaces also to sets of data which are not linearly separable
by embedding them into infinite dimensional spaces [
ate stabilizers in the form of norms on RKHSs suitable for
modeling generalization in terms of regularization [
Arguments proving the universal approximation
property of RBF networks using sequences of scaled kernels
might suggest that variability of widths is necessary for the
universal approximation. However, for the special case of
the Gaussian kernel, the universal approximation property
holds even when the width is fixed and merely centers are
varying [
On the other hand, it is easy to find some examples of positive semidefinite kernels such that sets of inputoutput functions of shallow networks with units generated by these kernels are too small to be universal approximators. For example, networks with product kernel units of the form K(x, y) = k(x)k(y) generate as input-output functions only scalar multiples ck(x) of the function k.
In this paper, we investigate capabilities of networks with one hidden layer of convolutional kernel units to approximate multivariable functions. We show that a crucial property influencing whether sets of input-output functions of convolutional kernel networks are large enough to be universal approximators is behavior of the Fourier transform of the one variable function generating the convolutional kernel. We give a necessary and sufficient condition for universal approximation of kernel networks in terms of the Fourier transforms of kernels. We compare this condition with properties of kernels guaranteeing their positive definitness. We illustrate our results by examples of some common kernels such as Gaussian, Laplace, parabolic, rectangle, and triangle.
The paper is organized as follows. In section 2, notations and basic concepts on one-hidden-layer networks and kernel units are introduced. In section 3, a necessary and sufficient condition on a convolutional kernel that guarantees that networks with units induced by the kernel have the universal approximation property. In section 4 this condition is compared with a condition guaranteeing that a kernel is positive semidefinite and some examples where as 3 units induced by the kernel K are contained in Hilbert spaces defined by these kernels. These spaces are called reproducing kernel Hilbert spaces (RKHS) and denoted
span GK (X ) = span{Kx | x ∈ X },
Kx(.) = K(x, .), together with limits of their Cauchy sequences in the norm k.kK . The norm k.kK is induced by the inner product h., .iK , which is defined on of kernels satisfying both or one of these conditions are given. Section 5 is a brief discussion. 2
Radial-basis-function networks as well as kernel models
belong to the class of one-hidden-layer networks with one
linear output unit. Such networks compute input-output
functions from sets of the form
span G =
( n )
∑ wigi | wi ∈ R, gi ∈ G, n ∈ N+ ,
i=1
where the set G is called a dictionary [
GK (X ,Y ) = {K(., y) : X → R | y ∈ Y } where K : X × Y → R is a function of two variables, an input vector x ∈ X ⊆ Rd and a parameter y ∈ Y ⊆ Rs. Such functions of two variables are called kernels. This term, derived from the German term “kern”, has been used since 1904 in theory of integral operators [18, p.291].
which are obtained by translations of one-variable functions k : Rd → Rd as
K(x, y) = k(x − y).
Radial convolutional kernels are convolutional kernels obtained as translations of radial functions, i.e., functions of the form
k(x) = k1(kxk), where k1 : R+ → R.
f ∗ g(x) = [20, p.170].
Recall, that a kernel K : X × X → R is called positive semidefinite if for any positive integer m, any x1, . . . , xm ∈ X and any a1, . . . , am ∈ R, m m ∑ ∑ aia jK(xi, x j) ≥ 0.
i=1 j=1 Similarly, a function of one variable k : Rd → R is called positive semidefinite if for any positive integer m, any x1, . . . , xm ∈ X and any a1, . . . , am ∈ R, m m ∑ ∑ aia jk(xi − x j) ≥ 0.
i=1 j=1
span GK (X ) of input-output functions of networks with GK (X ) = {Kx | x ∈ X } hKx, KyiK = K(x, y).
So span GK (X ) ⊂ HK (X ).
Universal approximation capability of convolutional kernel networks
sets of input-output functions of convolutional kernel networks are large enough to be universal approximators.
The universal approximation property is formally defined as density in a normed linear space. A class of onehidden-layer networks with units from a dictionary G is said to have the universal approximation property in a normed linear space (X , k.kX ) if it is dense in this space, i.e., clX span G = X , where span G denotes the linear span of G and clX denotes the closure with respect to the topology induced by the norm k.kX . More precisely, for every f ∈ X and every ε > 0 there exist a positive integer n, g1, . . . , gn ∈ G, and w1, . . . , wn ∈ R such that n k f − ∑ wigikX < ε.
i=1
Function spaces where the universal approximation property has been of interest are spaces (C(X ), k.ksup) of continuous functions on subsets X of Rd (typically compact) with the supremum norm k f ksup = sup | f (x)| x∈X and spaces (L p(Rd ), k.kL p ) of functions on Rd with finite RRd | f (y)|pdy and the norm k f kL p =
Z Rd | f (y)|pdy 1/p .
Recall that the d-dimensional Fourier transform is an isometry on L 2(Rd ) defined on L 2(Rd ) ∩ L 1(Rd ) as fˆ(s) = 1
Z and extended to L 2(Rd ) [20, p.183].
real and the Fourier transform of a radial function is radial. If k ∈ cL1(Rd ), then kˆ is uniformly continuous and with increasing frequencies converges to zero, i.e., lim kˆ(s) = 0.
ksk→∞
The following theorem gives a necessary and sufficient condition on a convolutional kernel that guarantees that the class of input-output functions computable by networks with units induced by the kernel can approximate arbitrarily well all functions in L 2(Rd ). The condition is formulated in terms of the size of the set of frequencies for which the Fourier transform is equal to zero. By λ is denoted the
Theorem 1. Let d be a positive integer, k ∈ L 1(Rd ) ∩ L 2(Rd ) be even, K : Rd Rd → R be defined as K(x, y) = k(x − y), and X ⊆ Rd ×be Lebesgue measurable. Then span GK (X ) is dense in (L 2(X ), k.kL 2 ) if and only if λ ({s ∈ Rd | kˆ(s) = 0}) = 0.
contradiction, assume that λ (S) 6= 0. Take any function f ∈ L 2(Rd ) ∩ L 1(Rd ) with a positive Fourier transform (for example, f can be the Gaussian). Let ε > 0 be such that ε <
Z Rd fˆ(s)2ds.
Assume that there exists n, wi ∈ R, and yi ∈ Rd such that n k f − ∑ wik(. − yi)kL2 < ε.
j=1 Then by the Plancherel Theorem [20, p.188],
n n k fˆ − ∑ wik(\.− yi)k2L2 = k fˆ − ∑ w¯ikˆk2L2 ,
j=1 j=1 where w¯i = wieiyi . Hence
n k fˆ − ∑ w¯ikˆk2L2 =
j=1 which is a contradiction.
To prove the sufficiency, we first assume that X = Rd .
clL 2 span GK (Rd ) = clL 2 span {K(., y) | y ∈ Rd } 6= L 2(Rd ).
ists a bounded linear functional l on L 2(Rd ) such that for all f ∈ clL 2 span GK (Rd ), l( f ) = 0 and for some f0 ∈ As As the set
Z
Rd L 2(Rd ) \ clL 2 span GK (Rd ), l( f0) = 1. By the Riesz Representation Theorem [5, p.206], l can be expressed as an inner product with some h ∈ L 2(Rd ).
As k is even, for all y ∈ Rd ,
Z
Rd hh, K(., y)i =
h(x)k(x − y)dx = Z Rd
h(x)k1(y − x)dx = h ∗ k1(x) = 0.
By the Young Inequality for convolutions h ∗ k ∈ L 2(Rd ) and so by the Plancherel Theorem [20, p.188], kh [∗k1kL 2 = 0. h [∗k1 =
1 (2π)d/2
hˆ kˆ Z Rd
(hˆ(s) kˆ(s))2ds = 0.
S = {s ∈ Rd | kˆ(s) = 0} [20, p.183], we have khˆ kˆkL 2 = 0 and so has Lebesgue measure zero we have
Z
Rd\S hˆ(s)2kˆ(s)2ds = hˆ(s)2kˆ(s)2ds = 0.
As for all s ∈ Rd \ S, kˆ(s)2 > 0, we have khˆk2L 2 ds = 0. So khkL 2 = 0 and hence by the Cauchy-Schwartz Inequality we get
Z 1 = l( f0) =
Rd f0(y) h(y)dy ≤ k f0kL 2 khkL 2 = 0, which is a contradiction.
Extending a function f from L 2(X ) to f¯ from L 2(Rd ) by setting its values equal to zero outside of X and restricting approximations of f¯ by functions from span GK (Rd ) to
set X of Rd .
convolutional kernel networks are large enough to approximate arbitrarily well all L 2-functions if and only if the
Theorem 1 implies that when kˆ(s) is equal to zero for all s such that ksk ≥ r for some r > 0 (the Fourier transform is band-limited), then the set span GK (Rd ) is too small to have the universal approximation capability. In the next section we show, that some of such kernels are positive semidefinite. So they can be used for classification by the
✷
Positive semidefinitness and universal approximation property
K(x, y) = k(x − y) = 1
Z it is easy to verify that when kˆ is positive or non negative than K defined as K(x, y = k(x − y) is positive definite, semidefinite, resp.
n
Indeed, to verify that ∑ j,l=1 a jal K(x j, xl ) ≥ 0 we express K in terms of the inverse Fourier transform. Thus we get ∑n a jal K(x j, xl ) = ∑n a jal (2π1)d/2 ZRd kˆ(s)ei(x j−xl)·sds = j,l=1 j,l=1 1 Proposition 2. Let k ∈ L 1(Rd ) ∩ L 2(Rd ) be an even function such that kˆ(s) ≥ 0 for all s ∈ Rd . Then K(x, y) = k(x − y) is positive semidefinite.
bounded continuous kernels follows from the Bochner
Theorem 3 (Bochner). A bounded continuous function k : Rd → C is positive semidefinite iff k is the Fourier transform of a nonnegative finite Borel measure μ, i.e., k(x) = 1
Z
sure μ has a distribution function then the condition in
Comparison of the characterization of kernels for which by Theorem 1 one-hidden-layer kernel networks are universal approximators with the condition on positive semidefinitness from Proposition 2 shows that there are positive semidefinite kernels which do not generate networks possessing the universal approximation capability and there also are kernels which are not positive definite but induce networks with the universal approximation property. The first ones are suitable for SVM but not for regression, while the second ones can be used for regression but are not suitable for SVM. In the sequel, we give some examples of such kernels.
Gaussian kernel ga : Rd → R defined for a width a > 0 as
ga = e−a2k.k2 . gba = (√2a)−d e−1/a2k.k2 .
The rectangle kernel is defined as rect(x) = 1 for x ∈ (−1/2, 1/2), otherwise rect(x) = 0.
sin(π s) rdect(s) = sinc(s) = . π s
zeros form a discrete set of the Lebesgue measure zero.
induces class of networks with the universal approximation property. On the other hand, the Fourier transform of sinc is the rectangle kernel and thus it is positive semidefinite, but does not induce networks with the universal approximation property.
l(x) = e−a|x|. lˆ(s) =
2a a2 + (2πs)2 .
The triangle kernel is defined as tri(x) = 2x − 1/2 for x ∈ (−1/2, 0), tri(x) = −2(x + 1/2) for x ∈ (0, 1/2), otherwise tri(x) = 0.
tbri(s) = sinc(s)2 = sin(π s) 2 π s .
The parabolic (Epinechnikov) kernel is defined epi(x) = 34 (1 − x2) for x ∈ (−1, 1), otherwise epi(x) = 0.
ecpi(s) = s33 (sin(s) − 21 s cos(s)) for s 6= 0, ecpi(s) = 1 for s = 0.
5
We investigated effect of properties of the Fourier transform of a kernel function on suitability of the convolutional kernel for function approximation (universal approximation property) and for maximal margin classification algorithm (positive semidefinitness). We showed that these properties depend on the way how the Fourier transform converges with increasing frequencies to infinity. For the universal approximation property, the Fourier transform can be negative but cannot be zero on any set of frequencies of non-zero Lebesgue measure. On the other hand, functions with non-negative Fourier transforms are positive semidefinite even if they are compactly supported.
of the multivariable Gaussian kernel and by some onedimensional examples. Multivariable Gaussian is a product of one variable functions and thus its multivariable
one-variable Gaussians. Fourier transforms of other radial multivariable kernels are more complicated, their expressions include Bessel functions and the Hankel transform.
the grant GACˇ R 15-181085 and institutional support of the