Year: 2021

Abstract:
The recent success of deep learning has encouraged many researchers to explore the deep/concatenated variants of classical kernel methods. Some of which includes MLMKL, DGP and DKL. These methods have proven to be quite helpful in various real-world settings. But so far, we have only been utilizing kernels from Hilbert spaces, which has their own limitations. In this paper, we address these shortcomings by introducing a new concatenated kernel learning approach that uses the kernels from the reproducing kernel Banach spaces(RKBSs) instead. We present a general framework of construction for these Deep RKBS models and then provide a representer theorem for regularized learning problems. We also describe the relationship with its deep RKHS variant as well as standard deep Gaussian processes. In the end, we construct and implement a two-layer deep RKBS model and demonstrate it on a range of machine learning tasks.

heading: 1 INTRODUCTION
text: In recent years, promising new variants of kernel learning methods, namely deep ker-nel learning and multi-layer-MKL (MLMKL) algorithms have been developed. These concatenated kernel learning approach includes, see e.g. Cho & Saul (2009); Damianou & Lawrence (2013); Zhuang et al. (2011). Although they have proven to be very successful in regression and classification tasks. we are still only utilizing kernel from Hilbert Space. There has be a recent interest in studying a space which is similar to RKHS but contains alot more functions i.e, reproducing kernel Banach space (RKBS). In this paper, we will define a general framework of concatenated RKBSs as well as provide a concatenated representer theorem which can be used to develop a generalized variant of all the concatenated kernel learning(Bohn et al. (2019)) methods described earlier. We will now give a brief overview of our paper.
In Section 2, we briefly review the interpolation problem in RKBS and discuss how we can recast this to RKHS. In Section 3, we introduce the optimal concatenated approximation problem for arbitrary loss function and regularizers. We first present a general framework to construct a deep/concatenated RKBS and then propose a representer theorem for this problem in multi-layer case. we then examine the concrete example of a two-layer RKBS kernel. Furthermore, we discuss the relation of our method to classical concatenated kernel learning in RKHSs which describe the connect with multiple array of methods such as DeepGP, DKL, MLMKL etc. In section 4 we look at a simple experiment and compare our Deep RKBS kernels with Deep RKHS ones. we also briefly talk about our library we have built to easily perform experimentation with Deep RKBS Kernels. Finally, we conclude with some related works and a summary of our paper.

heading: 2 REPRODUCING KERNEL BANACH SPACES
text: In this section, we briefly define RKBS and its reproducing kernel then we will present the representer theorem for minimal norm interpolation problem. for more comprehensive overview we refer the readers to Lin et al. (2019b).
A reproducing kernel Banach space B on a prescribed nonempty set X is a Banach space of certain functions on X such that every point evaluation functional δx, x ∈ X on B is continuous, that is, there exists a positive constant Cx such that
|δx(f)| = |f(x)| ≤ Cx‖f‖B for all f ∈ B.
this definition is the natural generalization of the classical definition of RKHS. Now before moving forward, we will present another definition as well as general framework of construction for RKBS which we will be using throughout this paper.
(Construction of RKBS using feature maps) Let W(1),W(2) be two Banach spaces, and 〈·, ·〉W(1)×W(2) be a continuous bilinear form onW(1) ×W(2). Suppose there exist two nonempty sets Ω(1) and Ω(2), and mappings Φ(1) : Ω(1) → W(1), Φ(2) : Ω(2) → W(2) such that with respect to the bilinear form span Φ(1)(Ω(1)) is dense inW(1), span Φ(2)(Ω(2)) is dense inW(2).We construct
B(1) := { fv(x) := 〈Φ(1)(x), v〉W(1)×W(2) : v ∈ W(2), x ∈ Ω(1) } (2.1)
and B(2) := { gu(y) := 〈u,Φ(2)(y)〉W(1)×W(2) : u ∈ W(1), y ∈ Ω(2) } (2.2)
with norm ‖fv‖B(1) := ‖v‖W(2) and ‖gu‖B(2) := ‖u‖W(1) respectively.
Theorem 2.1 Let B(1) and B(2) be constructed as above. Then with the bilinear form on B(1)×B(2)
〈fv, gu〉B(1)×B(2) := 〈u, v〉W(1)×W(2) for all fv ∈ B(1) and all gu ∈ B(2), (2.3)
B(1) is an RKBS on Ω(1) with the adjoint RKBS B(2) on Ω(2). Moreover,
K(x, y) := 〈Φ(1)(x),Φ(2)(y)〉W(1)×W(2) , x ∈ Ω(1), y ∈ Ω(2), (2.4)
is a reproducing kernel for B(1). Using the reproducing property we can rewrite f ∈ B(1) as:
f(x) = 〈f,K(x, ·)〉B1×B2 for all x ∈ Ω(1) and all f ∈ B1, (2.5)
where, K(x, ·) ∈ B(2).

heading: 2.1 INTERPOLATION PROBLEM IN RKBS
text: The minimal norm interpolation problem looks for the minimizer
finf := arg inf f∈Sx,t
‖f‖B(1) where Sx,t = { f ∈ B(1) : f(xj) = tj , j ∈ Nm } (2.6)
vinf := arg inf v∈Vx,t
‖v‖W(2) (2.7)
with Vx,t := { v ∈ W(2) : 〈Φ(1)(xj), v〉W(1)×W(2) = tj , j ∈ Nm } . (2.8)
Theorem 2.2 (Representer Theorem) Assume the same assumptions as in Theorem 2.1. In addition, suppose that W(2) is reflexive, strictly convex and Gâteaux differentiable, and the set {Φ(1)(xj) : j ∈ Nm} is linearly independent inW(1). Then the minimal norm interpolation problem (2.7) has a unique solution vinf ∈ W(2) and it satisfies
G(vinf) ∈ ( (Φ(1)(x))` )⊥ . (2.9)
If Ω(1) = Ω(2), W(2)∗ = W(1) and W(2) is reduced to a Hilbert Space then we can recover the classical representer theorem(Schölkopf et al. (2002)) for minimal norm interpolation in RKHS.

heading: 3 A REPRESENTER THEOREM FOR CONCATENATED KERNEL LEARNING IN BANACH SPACE
text: In this section, we will be deriving a concatenated RKBS representer theorem for an arbitrary numberL ∈ N of concatenations of vector-valued RKBS spaces. For more comprehensive treatment of vector-valued RKBS we refer the readers to Chen et al. (2019), Zhang & Zhang (2013) and Lin et al. (2019a) respectively.
LetB1, ..., BL be reproducing kernel Banach Spaces with finite dimensional domain Ω (1) l and ranges Rl ⊆ Rdl with dl ∈ N for l = 1, ..., L such that Rl ⊆ Ω(1)l−1 for l = 2, ..., L,Ω (1) L = Ω and R1 ⊆ C. We consider learning a function from a prescribed set of finite sampling data
z := {(xi, ti) : i ∈ N} ⊆ Ω× C Let furthermore L : R2 → [0,∞] be an arbitrary continuous and convex loss function and let Θ1, ...,ΘL : [0,∞) be continuous, convex and strictly monotonically increasing functions. For each arbitrary function fl ∈ Bl : ∀l = 1, ...L, we set
J(f1, ..., fL) := N∑ i=1 L(ti, f1 ◦ ... ◦ fL(xi)) + L∑ l=1 Θl(‖fl‖Bl) (3.10)
and our objective is:
inff1◦...◦fL∈B1×...×BL J(f1 ◦ ... ◦ fL) (3.11)
Since, ∀l = 1, ..., L
fl(x (l)) := fvl(x (l)) = 〈Ω(1)l (x (l)), vl〉W (1)l ×W (2)l , x (l) ∈ Ω(1)l , vl ∈ ¯span{Φ (2) l (y (l)) : y(l) ∈ Ω(2)l }
Thus 3.11 reduces to
v1, ...vLinf := arg infv1,...,vL∈W (2)1 ,...,W (2) L L ( ti, 〈Φ(1)1 , v1〉W (1)1 ×W (2)1 ◦ ... ◦ 〈Φ (1) L (xi), vL〉W (1)L ×W (2)L ) +
L∑ l=1 Θl(‖vl‖W (2)l )
(3.12)
Even if L is a convex loss function (3.11) is still a highly non-linear optimization problem. we therefore assume that, there are w ∈ N optimal composite functions which minimizes J . We Let F ∗l = f l∗ 1 , ..., f l∗ w be a set of all the optimal functions in Bl for all l = 1, ..., L .
Theorem 3.1 In addition to above assumption, suppose that W (2)l is reflexive, strictly convex and Gâteaux differentiable for all l = 1, ...L, and the set Φ(1)l (xj) : xj ∈ Dl,∀j ∈ N is linearly independent in W (1)l . Provided that F ∗ l is non-empty for all l = 1, ..., L then, there exist a set of w minimizers where each vlinf ∈W (2) l : ∀l = 1, ...L satisfies
G(vlinf) ∈ (Vlx,0)⊥
where,
Vlx,0 := {vl ∈W (2) l : 〈Φ (1) l (x (l) j ), vl〉W (1)l ×W (2)l = 0 : x (l) j ∈ Ω (1) l , j ∈ N}
Proof: Suppose there exist a minimizer f∗l ∈ F ∗l ∈ Bl then we create a data set Dl: Dl := (xj , f ∗ l (xj)) : j ∈ Nm
By theorem 2.2 there exists a unique solution vinf ∈ W2 for the min norm interpolation problem with the samples Dl and it satisfy that G(vlinf) ∈ (Vlx,0)⊥ It follows that flv inf = 〈Φ(1)l (·), vlinf〉W (1)l ×W (2)l interpolates the sample data Dl and for all vl ∈W (2) l :
||vlinf ||W (2)l ≤ ||vl||W (2)l
Thus, fv inf(x) = fv∗(x).
We can extend this result for all l = 1, ..., L such that:
G(v̂linf) ∈ (Vlx,0)⊥
as long as F ∗l ∈ Bl is non-empty. The proof is complete.

heading: 3.1 EXAMPLE
text: In this section, we will define a concrete example of a 2 layer RKBS using our framework of construction. Suppose, our inner vector-valued RKBS B2 is endowed by l1 norm and our outer vectorvalued RKBSB1 is endowed by Lp norm where, 1 < p < ∞. using the representer theorem (see, Lin et al. (2019a) and Chen et al. (2019) ) we can rewrite a vector-valued f2(·) ∈ B2 as:
f2(·) = N∑ i=1 d2∑ k2=1 ci,k2K2 (xi, ·) ek2
for certain coefficients ci,k2 ∈ R. Furthermore, we have that f1 ∈ Sx1 = span {K1 (f2 (xi) , ·) | i = 1, . . . , N} and thus
f1(·) = N∑ j=1 αjK1 ( N∑ i=1 d2∑ k2=1 ci,k2K2 (xi,xj) ek2 , · )
The concatenated function is then given by h(·) := f1◦f2(·) = ∑N
j=1 αjK (xj , ·) with the following deep RKBS kernel
K(x,y) = K1 ( N∑ i=1 d2∑ k2=1 ci,k2K2 (xi,x) ek2 , N∑ i=1 d2∑ k2=1 ci,k2K2 (xi,y) ek2 ) (3.13)
Therefore, instead of considering the infinite-dimensional optimization problem of finding f1 ∈ B1 and f2 ∈ B2 that minimize
J (f1, f2) = N∑ i=1 L (yi, f1 (f2 (xi))) + Θ1 ( ‖f1‖2B1 ) + Θ2 ( ‖f2‖2B2 ) we can restrict ourselves to finding the N + N · d2 coefficients αj , ci,k2 for i, j = 1, . . . , N and k2 = 1, . . . , d2

heading: 3.2 RELATION TO DEEP KERNEL LEARNING
text: As briefly mentioned in 2.2, we can recover the classical representer theorem for interpolation problem ( the detailed proof is given in the appendix ). If we assume B1, ...BL to be H1, ...,HL where Hl ∀l = 1, ...L as a set of RKHS of vector-valued function then we can find a set of minimizers f1, ..., fL fl ∈ Hl of 3.10 which satisfies that for all l = 1, ...L:
fl ∈ spanKl(fl+1 ◦ ... ◦ fL(xi), ·)ekl : i = 1, ...Nandkl = 1, ..., dl (3.14)
where Kl denotes the reproducing kernel ofHl and ekl ∈ Rdl is the kl-th unit vector. which is exactly the representer theorem for concatenated kernel learning in hilbert space as described in Bohn et al. (2019), if we define a probability measure on each Hl above then we can recover the Deep gaussian processes. which means that the methods such as Cho & Saul (2009), Damianou & Lawrence (2013), Zhuang et al. (2011), Wilson et al. (2016) are the special cases of our framework. It will be interesting to see the RKBS equivalent of these methods using our framework in future.

heading: 4 EXPERIMENT
text: Although, we are leaving more thorough experimentation on deep RKBS kernels for future works. Here, for the sake of completeness we simply perform some preliminary experiments on two synthetic data which is generated as follows:
We choose Ω = [0, 1]2
h1 : Ω→ R h1(x, y) := (0.1 + |x− y|)−1 h2 : Ω→ R h2(x, y) := {
1 if x · y > 320 0 else
We define our deep RKBS kernel similar to 3.13 where we use the following kernels:
K2(x, y) := 1− |x− y|
which is the reproducing kernel for C([0,1]) and for K1:
K1(x, y) := min{x, y} − t ∗ xy : 0 < t < 1
which is the generalization of Brownian bridge kernel. now, for deep RKHS we take the polynomial kernel of degree 2 as inner kernel and Matern kernel as its outer kernel.
We compare deep RKHS and deep RKBS in regularized regression setting which is regularized by l2. the results are presented in table below where the performance is calculated by averaging the MSE loss of 50 trials.
avg. MSE
Deep RKHS 0.00304 Deep RKBS 0.00112
The difference isn’t significant, deep RKBS does slightly outperform deep RKHS in this setting. Since, Deep RKHS is a subset of Deep RKBS we can see the practical significance of this method. Although a more thorough empirical study is required.
For this experiment we have also implemented a small library which contains implementation of multiple RKBS kernels, the library also allows to easily Create deep Kernels by simply specifying the kernel and its ranges.

heading: 5 RELATED WORKS
text: While concatenated kernel learning methods such as deepGP have been a well-established line of research, deep RKBS is still in this infency. although there are some very promising recent works in this direction such as Bartolucci et al. (2021), but to the best of authors knowledge, concatenated RKBS kernel learning is not been presented in the literature so far.

heading: 6 CONCLUSION
text: We proposed a general framework to construct deep RKBS Kernels, which give rise to a new direction in concatenated kernel learning literature. we started by presenting the general RKBS and its reproducing kernel. we then define a new class of concatenated kernel learning in RKBS spaces and presented a representer theorem along with some examples of deep RKBS, we then derived the connection between the classical concatenated kernel learning methods which includes DKL, MLMKL, DeepGP among other, we finished our paper by describing our new Library to do experiments with Deep RKBS as well as showed some preliminary results of comparing deep RKHS and deep RKBS.

heading: ACKNOWLEDGMENTS
text: We would like to thank ICLR committe for organising ICLR CoSubmitting Summer 2022 this year.

heading: A APPENDIX
text: You may include other additional sections here.

Review summaries:
The paper presents a means of constructing deep (concatenated) reproducing kernel Banach space kernels.  The main contribution appears to be a representor theory for concatenated Banach space kernels.  Some experimental results are provided to accompany this result.