# Generalization Bounds for Coregularized Multiple Kernel Learning

Authors: Xinxing Wu; Guosheng Hu
Journal: Computational Intelligence and Neuroscience
 (2018)

---

## Abstract

Multiple kernel learning (MKL) as an approach to automated kernel selection plays an important role in machine learning. Some learning theories have been built to analyze the generalization of multiple kernel learning. However, less work has been studied on multiple kernel learning in the framework of semisupervised learning. In this paper, we analyze the generalization of multiple kernel learning in the framework of semisupervised multiview learning. We apply Rademacher chaos complexity to control the performance of the candidate class of coregularized multiple kernels and obtain the generalization error bound of coregularized multiple kernel learning. Furthermore, we show that the existing results about multiple kennel learning and coregularized kernel learning can be regarded as the special cases of our main results in this paper.


---

## Body

## 1. Introduction

Kernel-based learning is related to achieve nonlinear machine learning tasks from linear ones. In the real applications, selecting a good or suitable kernel for the kernel-based learning is an important and difficult task. To this end, an approach named multiple kernel learning has been developed, and it allows to automatically choose the best kernel from a predefined kernel class. The earliest work of multiple kernel learning can be traced back to the research in [1], where the authors proposed to automatically pick up a linear combination of candidate kernels for the support vector machines based on a semidefinite programming approach. Theoretical generalization analysis of multiple kernel learning has been widely studied by many researchers [1–7]. In particular, Ying and Campbell in [2] proposed a novel generalization bound (Rademacher chaos complexity) for the study of multiple kernel learning. However, the discussions in [2] were for single view and supervised learning. In this paper, we will employ Rademacher chaos complexity proposed in [2] to study the generalization error of coregularized multiple kernel learning in the semisupervised multiview learning framework.Semisupervised multiview learning as an area of machine learning is trained with both labeled samples and unlabeled samples, and the unlabeled samples are helpful to reduce the amount of the labeled samples. Semisupervised multiview learning supposes that the train samples can be represented by multiple views. The coregularized least squares algorithm—a semisupervised version of regularized least squares with two views—is a typical multiview learning model that uses the unlabeled samples to estimate the view incompatibility of models [8, 9]. Rosenberg in [10] extended the coregularized least squares algorithm to the case of kernel cotraining. And Brefeld et al. and Rosenberg in [11, 12, 13] discussed the generalization bound of kernel-based learning with multiple (or two) views in the semisupervised learning framework. However, the discussions in [11, 12, 13] supposed that the kernel used to construct the reproducing kernel Hilbert space is predefined. Therefore, their results cannot be used to the analysis of multiple kernel learning.In this paper, we will discuss the generalization error of coregularized multiple kernel learning in the semisupervised multiview learning framework. And we show that the results in [2] and [11] can be regarded as the special cases of our main results. The rest of the paper is organized as follows. In Section 2, we introduce some basic notations and definitions for later discussion. In Section 3, we discuss the related research and put forward the question that will be studied in this paper. In Section 4, we present our main results. In Section 5, we give the main proofs for our main results proposed in Section 4. In Section 6, we give a comparative discussion of our results to the existing work and show that the results about multiple kennel learning in [2] and coregularized kernel learning in [11] can be regarded as the special cases of our main results. The last Section 7 concludes this paper.


## 2. Notations and Definitions

In this section, we introduce notations and definitions for later discussions:(i)
LetN be the set of natural numbers and R be the set of real numbers. Let Nn=1,2,…,n,n∈N.(ii)
LetΩ,A,P be a probability space; that is, Ω alone is called the sample space, A is a σ-algebra on Ω, and P is a probability measure on Ω,A. And Ω has the structure Ω=X×Y⊂R, where X and Y are the input space and output space, respectively. Denote PX as the marginal distribution on X. For ignoring the discussion of measure theory, we simply denote Ω,A,P as Ω,P.(iii)
Letℱ be the set of all measurable functions f:X⟶Y. Assume that ℋ is a subset of ℱ. That is, ℋ⊂ℱ, the set ℋ is called the hypothesis class.(iv)
LetS=zi=xi,yi,i∈Nn be a finite set of the labeled training samples, and assume these samples are independent and identically distributed (i.i.d.) according to P. Denote the bold letter as a vector; for example, z presents a vector z1,z2,…,zn.(v)
For the sign⋅, if D is a set, we use D to represent the number of elements of a set and if D is a function, we use D to represent the absolute value of the function D.(vi)
IfA is a matrix, we use AT to represent the transpose of the matrix A.(vii)
LetL be the loss function, L:Y×Y⟶0,+∞, and the loss of f on a sample point z=x,y is defined by Lf,z or Lfx,y.In learning theory, one of the purposes is to pick up a functionf in hypothesis space ℋ that minimizes the following generalization error:(1)EPLfX,Y≜∫ΩLf,zdP.Generally speaking, the distributionP in the above Equation (1) is unknown. Rather than minimizing EPLfX,Y, we usually minimize the empirical or training error below:(2)Enf,S≜1m∑i∈NmLf,zi,where the sign S represents the finite labeled samples and zi=xi,yi∈S,i∈Nm.In this paper, the main quantity we are interested in is the following uniform estimation of the difference between the generalization error and empirical error:(3)supfEPLfX,Y−Enf,S.For the discussion in the later sections, we introduce the following four definitions and one lemma (Definition 5 is proposed by us).Definition 1 (Empirical Rademacher Complexity) [2]. Let ℋ be a class of functions f:Ω⟶R. The samples xi,i∈Nn, are independently drawn from the probability space Ω,P. The empirical Rademacher complexity can be defined as(4)ℛnℋ≜Eσsupf∈ℋ1n∑i∈Nnσifxi,where the random variables σi,i∈Nn, are Rademacher variables, and σ presents a vector σ1,σ2,…,σn.Definition 2 (Empirical Rademacher Chaos Complexity) [2]. Let ℋ be a class of functions f:Ω×Ω⟶R. The samples xi,i∈Nn, are independently drawn from the probability space Ω,P. The empirical Rademacher chaos complexity can be defined as(5)Unℋ≜Eσsupf∈ℋ1n∑i,j∈Nn,i<jσiσjfxi,xj,where the random variables σi,i∈Nn, are Rademacher variables, and σ presents a vector σ1,σ2,…,σn.Definition 3 (Reproducing Kernel Hilbert Space, RKHS) [14]. The function(6)K:X×X⟶R,is a reproducing kernel of the Hilbert space ℋK if and only if.(i)
For anyx∈X,K⋅,x∈ℋK(ii)
For anyf∈ℋK, for any x∈X, f,KxℋK=fxA Hilbert space of functions which possesses a reproducing kernel is called a reproducing kernel Hilbert space.Remark 1.
The second condition in the above Definition 3 is called “the reproducing property”: the value of the functionf at the point x is reproduced by the inner product of f with Kx. From the above two conditions, for any, x,y∈X×X, it is clear that(7)Kx,y=Kx,⋅,Ky,⋅ℋK.
In real applications, the solution to many reproducing kernel Hilbert space optimization questions is contained in a special subspace of the reproducing kernel Hilbert space, often known as the “span of the data”. The span of the data for an reproducing kernel Hilbert spaceℋK is the linear subspace (Appendix A.3 on page 75 of [13]):(8)spanKxi,⋅:xi∈X,i∈Nm.
For simplicity, we denote the above linear subspace byℒmK.
LetK⊂K:X×X⟶R be a class of kernels. In this paper, we assume that κ≜supK∈K,x∈XKx,x is finite.Definition 4 (Subnormalized Functional with Degenerate Dimension n). If a loss function ℓ:∏i∈NnℋKi×Y⟶0,+∞ satisfies(9)ℓ0,…,0︸n,y≤1,for  anyy∈Y,then we call ℓ a subnormalized functional with degenerate dimension n on ∏i∈NnℋKi×Y.Lemma 1.
[13] Let ℋ be a reproducing kernel Hilbert space with kernel K:X×X⟶R, and consider any point x∈X. If ℒK is a closed subspace containing Kx, then the projection of f onto ℒK has the same value at x as f does. That is,(10)fx=ProjℒKfx.For multiple kernel learning, the main task is to automatically choose a kernel K from a predefined classK of kernels, and find a function from the reproducing kernel Hilbert space ℋK that is most suitable to model the given samples.In this paper, our purpose is to minimize(11)Qf1,f2≜1m∑i∈Nmℓf1xi,f2xi,yi+γ1f1ℋK12+γ2f2ℋK22+λ∑i=m+1m+uf1xi−f2xi2,over the class ∪K1∈KℋK1×∪K2∈K′ℋK2. Here, let K and K′ be the classes of kernels. ℋK1 and ℋK2 denote the reproducing kernel Hilbert spaces. m represents the amount of the labeled points xi,yi∈X×Y,i∈Nm, and u represents the amount of the unlabeled points xm+i∈X,i∈Nu. The signs γ1,γ2, and λ mean the regularization parameters. The functions f1 and f2, respectively, represent two viewers, and the function ℓf1⋅,f2⋅,⋅ is the labeled loss function, which measures the performance of f1 and f2 on the labeled points zi,i∈Nm.


## 3. Related Work

In [11], Rosenberg and Bartlett used Rademacher complexity to bound the coregularized kernel class in the semisupervised two-view learning framework, and two viewers are two predefined reproducing kernel Hilbert spaces (ℋ1 and ℋ2, respectively). Take labeled points zi=xi,yi∈X×Y,i∈Nm, and unlabeled points xm+i∈X,i∈Nu. The coregularized least squares algorithm discussed in [11] can be described as follows:(12)fz1,fz2≜argminf1∈ℋ1f2∈ℋ21m∑i∈Nmℓf1xi,f2xi,yi+γ1f1ℋ12+γ2f2ℋ22+λ∑i=m+1m+uf1xi−f2xi2,where m represents the amount of the labeled points xi,yi∈X×Y,i∈Nm, and u represents the amount of the unlabeled points xm+i∈X,i∈Nu. The signs γ1,γ2, and λ mean the regularization parameters. The functions f1 and f2, respectively, represent two viewers, and the function ℓf1⋅,f2⋅,⋅ is the labeled loss function, which measures the performance of f1 and f2 on the labeled points zi,i∈Nm.In [11], the final output is denoted as fz1+fz2/2.In [2], Ying and Campbell applied the Rademacher chaos complexity to study the generalization of multiple kernel learning in the supervised learning framework. The multiple kernel learning model they considered is as follows:(13)fz≜argminK∈Kminf∈ℋK1m∑i∈Nmℓfxi,yi+γfℋK2,where m represents the amount of the labeled points xi,yi∈X×Y,i∈Nm. The function ℓfxi,yi is the loss function. The sign λ means the regularization parameters. And ℋK denotes the reproducing kernel Hilbert spaces. In Equation (13), ℋK is not predefined and depends on the kernel choose from the class K of kernel.In this paper, we are interested in the topic of coregularized multiple kernel learning; that is, the two reproducing kernel Hilbert spaces are not defined in advance. Our discussions are in the framework of semisupervised multiview learning. We give this learning question as the following two-layer minimization formation:(14)fz1,fz2≜argminK1∈KK2∈K′minf1∈ℋK1f2∈ℋK21m∑i∈Nmℓf1xi,f2xi,yi+γ1f1ℋK12+γ2f2ℋK22+λ∑i=m+1m+uf1xi−f2xi2,where let K and K′ be the classes of kernels. ℋK1 and ℋK2 denote the reproducing kernel Hilbert spaces. m represents the amount of the labeled points xi,yi∈X×Y,i∈Nm, and u represents the amount of the unlabeled points xm+i∈X,i∈Nu. The signs γ1,γ2, and λ mean the regularization parameters. The functions f1 and f2, respectively, represent two viewers, and the function ℓf1⋅,f2⋅,⋅ is the labeled loss function, which measures the performance of f1 and f2 on the labeled points zi,i∈Nm.Remark 2.
We will explain the following:(1)
Equation (14) given in this paper is different from Equation (12):(a)
The solution from Equation (14) is to minimize on the class ∪K1∈KℋK1×∪K2∈K′ℋK2, while the solution from Equation (12) is to minimize on the class ℋK1×ℋK2.(b)
The solution from Equation (14) is through two minimization steps: first, it finds the most suitable reproducing kernel for the given samples. Second, it obtains the best function/model from the found reproducing kernel Hilbert spaces in the first step. While in Equation (12), it only needs to get the best function/model from the reproducing kernel Hilbert spaces which are predefined.(2)
Equation (14) given in this paper is different from Equation (13):(a)
The solution from Equation (14) is to minimize on the product space ∪K1∈KℋK1×∪K2∈K′ℋK2, while the solution from Equation (12) is to minimize on the space ∪K1∈KℋK1.(b)
The minimization item in Equation (13) is much simpler because the analysis on Equation (13) is limited to supervised learning and single view and does not deal with unlabeled samples.
From the above discussion, we can see that the generalization analysis about Equation (14) will make more meaningful and bring greater challenge.
In the next section, we will present the main results of this paper.


## 4. Generalization Bounds

In this section, we assume that the loss functionℓ in Equation (11) is the subnormalized functional with degenerate dimension 2 on ℋK1×ℋK2×Y,K1∈K,K2∈K′. In Equation (11), let f1=0 and f1=0, we have(15)minK1∈KK2∈K′minf1∈ℋK1f2∈ℋK2Qf1,f2≤Q0,0=1m∑i∈Nmℓ0,0,yi≤1,Note thatQf1,f2≥0, and then for any samples xi,yi,i∈Nm and xm+i,i∈Nu, the class of candidate reproducing kernel Hilbert spaces is defined as follows:(16)fz1,fz2∈ℋK,K′≜f1,f2:γ1f1ℋK12+γ2f2ℋK22+λ∑i=m+1m+uf1xi−f2xi2≤1,K1∈K,K2∈K′.That is, the solutionfz1,fz2 minimizing Qf1,f2 belongs to the class ℋK×ℋK′. For simplicity, we use ℋK,K′ to denote ℋK×ℋK′ in the next sections.As the assumption in [11], the final predictor for the coregularized multiple kernel learning is selected from the following class:(17)ℋ^K,K′≜f+g2:f,g∈ℋK,K′.Remark 3.
In Equations (16) and (17), we can see that ℋK,K′ and ℋ^K,K′ mainly depend on the prescribed set of candidate kernels and the unlabeled data.
For anyf∈ℋ^K,K′, we define the expected loss as Equation (2), and we can use the loss function L to compute the labeled empirical loss in Equation (11). For the given samples xi,yi∈X×Y,i∈Nm, the loss can be also computed as Equation (3).
IfL satisfies the Lipschitz continuous condition on ℋ^K,K′, we introduce the constant defined by(18)Lsup=supLf⋅,·:for  anyf≤κ+κ′minγ1,γ2,and the local Lipschitz constant denoted as(19)Lsuploc=supLf⋅,·−Lf′⋅,·f−f′:for  anyf,f′≤κ+κ′minγ1,γ2.
In the end of this section, we give the main theorems in this paper.Theorem 1.
Let the function L be a subnormalized functional with degenerate dimension 1 onℋ^K,K′×Y and satisfy the Lipschitz continuous condition on ℋ^K,K′. Let the labeled samples zi=xi,yi∈X×Y,i∈Nm, be independent random variables drawn from the probability space X×Y,P, and the unlabeled samples xm+i∈X,i∈Nu, be independent random variables drawn from the probability space X,PX. Then, for any δ∈0,1, with probability at least 1−δ, for any f∈ℋ^K,K′, the following inequality holds(20)EPLfX,Y−Enf,S≤Lsuplocm2γ1UmK+2γ2UmK′+κ2γ1+κ′2γ2+−1m⋅EσinfK1∈KK2∈K′σT⋅1γ1KMU1−1γ2KMU2⋅O⋅ΔUUλ,K1,K2⋅OT2⋅σ1/2+3Lsup⋅ln2/δ2m,where σ presents a vector σ1,σ2,…,σn and σi,i∈Nm, are Rademacher variables, 1/γ1⋅KUU1+1/γ2⋅KUU2=O⋅DUUK1,K2⋅OT with diagonal elements DiiK1,K2≥0,i∈Nu, and orthogonal matrix O, and(21)DUUK1,K2=d11K1,K2d22K1,K2⋱duuK1,K2,(22)ΔUUλ,K1,K2=1λ−1+d11K1,K21λ−1+d22K1,K2⋱1λ−1+duuK1,K2.Corollary 1.
Under the assumption of Theorem 1, we have the following inequality:(23)EPLfX,Y−1m∑i∈NmLfxi,yi≤Lsuplocm2γ1UmK+2γ2UmK′+κ2γ1+κ′2γ2+−1m⋅EσinfK1∈KK2∈K′σT⋅1γ1KMU1−1γ2KMU2⋅O⋅ΔUUλ,κ,κ′⋅OT2⋅σ1/2+3Lsup⋅ln2/δ2m.Corollary 2.
Under the assumption of Theorem 1 and assumeK=K′ and γ1=γ2, the following inequality holds(24)EPLfX,Y−1m∑i∈NmLfxi,yi≤Lsuplocm4γ1UmK+2κ2γ1+3Lsup⋅ln2/δ2m.Remark 4.
We will proof Theorem 1 and Corollaries 1 and 2 in Section5. And in Section 6, we will reveal that Theorem 1 and Corollary 1 are the extensions of the results in [2] and [11], respectively.


## 5. Proofs

In this section, we will prove Theorem 1 and Corollaries 1 and 2 in Section4. As the preparation for the next proof, we give two following lemmas (Lemmas 2 and 3) in advance.Lemma 2.
Let the function L be a subnormalized functional with degenerate dimension 1 onℋ^K,K′×Y, and satisfy the Lipschitz continuous condition on ℋ^K,K′. Let the labeled samples zi,i∈Nm, be independently drawn from the X×Y,P and the unlabeled samples xm+i∈X,i∈Nu, be independently from the probability space X,PX. Then, for any δ∈0,1, with probability at least 1−δ, we have the following inequality:(25)supf∈ℋ^K,K′EPLfX,Y−Enf,S≤2Eσsupf∈ℋ^K,K′1m∑i∈Nmσi⋅Lfxi,yi+3Lsup⋅ln2/δ2m,where σ presents a vector σ1,σ2,…,σn and σi,i∈Nm, are Rademacher variables.Proof.
For simplicity, let(26)ΔNm≜supf∈ℋ^K,K′EPLfX,Y−1m∑i∈NmLfxi,yi.
Replacing theith sample xi,yi in the labeled samples with xi′,yi′, we have(27)ΔNm−supf∈ℋ^K,K′EPLfX,Y−1m∑i∈Nm/jLfxi,yi+Lfxj′,yj′=supf∈ℋ^K,K′1mLfxj,yj−Lfxj′,yj′.
By McDiarmid’s inequality (Theorem D.3 on page 372 of [15]), with probability at least 1−δ/2, we have(28)supf∈ℋ^K,K′EPLfX,Y−1m∑i∈NmLfxi,yi≤EPsupf∈ℋ^K,K′EPLfX,Y−1m∑i∈NmLfxi,yi+Lsup⋅ln2/δ2m.
By the symmetrization argument (page 36 of [15]), we bound the expectation of the first term on the right-hand side of the above inequality (28) as follows:(29)EPsupf∈ℋ^K,K′EPLfX,Y−1m∑i∈NmLfxi,yi≤2EPEσsupf∈ℋ^K,K′1m∑i∈Nmσi⋅Lfxi,yi.
Again, applying McDiarmid’s inequality to the right-hand side of the above inequality (29), with probability at least 1−δ/2, we have(30)EPEσsupf∈ℋ^K,K′1m∑i∈Nmσi⋅Lfxi,yi≤Eσsupf∈ℋ^K,K′1m∑i∈Nmσi⋅Lfxi,yi+Lsup⋅ln2/δ2m.
Combining inequalities (28), (29), and (30) yield with probability at least 1−δ:(31)supf∈ℋ^K,K′EPLfX,Y−1m∑i∈NmLfxi,yi≤2Eσsupf∈ℋ^K,K′1m∑i∈Nmσi⋅Lfxi,yi+3Lsup⋅ln2/δ2m.Lemma 3.
Under the assumption of Lemma 2, for anyδ∈0,1, with probability at least 1−δ, we have the following inequality:(32)Eσsupf∈ℋ^K,K′1m∑i∈Nmσi⋅Lfxi,yi≤Lsuploc⋅Eσsupf∈ℋ^K,K′1m∑i∈Nmσi⋅fxi,where, σ presents a vector σ1,σ2,…,σn and σi,i∈Nm, are Rademacher variables.Proof.
As defined in Equation (19), Lsuploc is the local Lipschitz constant of L. And by the contraction property of Rademacher complexity (Lemma 26.9 on page 331 of [16] and Theorem 7 of [17]), the result is as follows.Lemma 4.
If Equation (11) has a solution, then, for a fixed K1∈K and a fixed K2∈K′, it has a solution fz1,fz2 as follows:(33)fz1=∑i∈Nm+uαiK1xi,⋅∈∪K1∈Kℒm+uK1,(34)fz2=∑i∈Nm+uβiK2xi,⋅∈∪K2∈K′ℒm+uK2,for some α=α1,α2,…,αm+uT∈Rm+u and β=β1,β2,…,βm+uT∈Rm+u. That is, the solution belongs to ∪K1∈Kℒm+uK1×∪K2∈K′ℒm+uK2.Proof.
The result follows in a similar way to Proposition 2.3.1 in [11].Lemma 5.
Let the labeled sampleszi=xi,yi∈X×Y,i∈Nm, be independent random variables drawn from the probability space X×Y,P and the unlabeled samples xm+i∈X,i∈Nu, be independent random variables drawn from the probability space X,PX. The following inequality holds(35)Eσsupf∈ℋ^K,K′1m∑i∈Nmσi⋅fxi≤12m2γ1UmK+2γ2UmK′+κ2γ1+κ′2γ2+−1m⋅EσinfK1∈KK2∈K′σT⋅1γ1KMU1−1γ2KMU2⋅O⋅ΔUUλ,K1,K2⋅OT2⋅σ1/2,where σ presents a vector σ1,σ2,…,σn and σi,i∈Nm, are Rademacher variables, 1/γ1⋅KUU1+1/γ2⋅KUU2=O⋅DUUK1,K2⋅OT with diagonal elements DiiK1,K2≥0,i∈Nu, and orthogonal matrix O, and(36)DUUK1,K2=d11K1,K2d22K1,K2⋱duuK1,K2,(37)ΔUUλ,K1,K2=1λ−1+d11K1,K21λ−1+d22K1,K2⋱1λ−1+duuK1,K2,Proof.
As defined in Equation (17), we can rewrite the left-hand side of inequality (35) as(38)Eσsupf∈ℋ^K,K′1m∑i∈Nmσi⋅fxi=Eσsupf,g∈ℋK,K′12m∑i∈Nmσi⋅fxi+gxi,where the sign ℋK,K′ is defined in Equation (16).
From the assumptions, we have(39)ℒm+uK1≜spanK1xi:xi∈X,i∈Nm+u⊆ℋK1,K1∈K,(40)ℒm+uK2≜spanK2xi:xi∈X,i∈Nm+u⊆ℋK2,K2∈K′.
By the reproducing property and Lemma 1, for anyK1∈K and K2∈K′, for any i∈Nm+u, we have(41)fxi=Projℒm+uK1fxi,(42)fxi=Projℒm+uK2fxi.
Combining Equations (39), (40), (41), and (42) yields that(43)Eσsupf,g∈ℋK,K′12m∑i∈Nmσi⋅fxi+gxi=EσsupK1∈KK2∈K′12m∑i∈Nmσi⋅fxi+gxi:f,g∈ℒm+uK1×ℒm+uK2∩ℋK1,K2,where(44)ℋK1,K2≜f,g:γ1fℋK12+γ2gℋK22+λ∑i=m+1m+ufxi−gxi2≤1.
By Lemma 4, for anyK1∈K and K2∈K′, we have (this is similar to Section 5.2.1 converting to Euclidean space in [11])(45)fx1,fx2,…,fxmT=KMU1KMM1⋅α,gx1,gx2,…,gxmT=KMU2KMM2⋅β,fℋK12=αT⋅K1⋅α,gℋK22=βT⋅K2⋅β,∑i=m+1m+ufxi−gxi2=αTβT⋅KUU1KMU1−KUU2−KMU2⋅KUU1KUM1−KUU2−KUM2⋅αβ,where(46)Ki=KUUiKUMiKMUiKMMim+u×m+u,i=1,2,KUUi=Kixm+1,xm+1…Kixm+1,xm+uKixm+2,xm+1…Kixm+2,xm+u⋮⋱⋮Kixm+u,xm+1…Kixm+u,xm+uu×u,i=1,2,KUMi=Kixm+1,x1…Kixm+1,xmKixm+2,x1…Kixm+2,xm⋮⋱⋮Kixm+u,x1…Kixm+u,xmu×m,i=1,2,KMUi=Kix1,xm+1…Kix1,xm+uKix2,xm+1…Kix2,xm+u⋮⋱⋮Kixm,xm+1…Kixm,xm+um×u,i=1,2,KMMi=Kix1,x1…Kix1,xmKix2,x1…Kix2,xm⋮⋱⋮Kixm,x1…Kixm,xmm×m,i=1,2.
Hence, we have(47)Eσsupf,g∈ℋK,K′12m∑i∈Nmσi⋅fxi+gxi=EσsupK1∈KK2∈K′12m∑i∈Nmσi⋅fxi+gxi:f,g∈ℒm+uK1×ℒm+uK2∩ℋK1,K2=EσsupK1∈KK2∈K′supα∈Rm+uβ∈Rm+uσT⋅KMU1KMM1⋅α+σT⋅KMU1KMM1⋅β2m:αTβT⋅Λ⋅αβ≤1,where(48)Λ=γ1K100γ2K2+λ⋅KUU1KMU1−KUU2−KMU2⋅KUU1KUM1−KUU2−KUM2.
Note that the matrixΛ is not full rank, and by using the similar steps in [11], we can rewrite Equation (47) as(49)Eσsupf,g∈ℋK,K′12m∑i∈Nmσi⋅fxi+gxi=12mEσsupK1∈KK2∈K′ΛK1,K2^−1/2⋅KK1,K2^T⋅σ,where(50)ΛK1,K2^=KMU1KMM1KMU2KMM2⋅V00W,KK1,K2^=γ1EK100γ2EK2+λ⋅R⋅RT,R=VT00WT⋅KUU1KMU1−KUU2−KMU2,VTK1V=EK1,WTK2W=EK2,
In the above equations, the matricesEK1 and EK2 are, respectively, diagonal matrices containing nonzero eigenvalues. And we write the projections of α and β onto the column spaces of K1 and K2 as V⋅a and W⋅b.
Next, we try to relate Equation (47) to Rademacher Chaos complexity. Note that(51)KK1,K2^⋅ΛK1,K2^−1⋅KK1,K2^T=1γ1KMM1+1γ2KMM2−λ1γ1KMU1−1γ2KMU2⋅I+λ1γ1KUU1+1γ2KUU2−1⋅1γ1KUM1−1γ2KUM2=1γ1KMM1+1γ2KMM2−1γ1KMU1−1γ2KMU2⋅O⋅ΔUUλ,K1,K2⋅OT2,
The first equation can be easily obtained by the discussion of Section 5.2.4 in [11]. The second equation from(52)λI+λ1γ1KUU1+1γ2KUU2−1=O⋅λ−1⋅I+DUUK1,K2−1⋅OT=O⋅λ−1+d11K1,K2λ−1+d22K1,K2⋱λ−1+dUUK1,K2−1⋅OT=O⋅1λ−1+d11K1,K21λ−1+d22K1,K2⋱1λ−1+duuK1,K2⋅OT2
Then, we have(53)EσsupK1∈KK2∈K′ΛK1,K2^−1/2⋅KK1,K2^T⋅σ=EσsupK1∈KK2∈K′σT⋅KK1,K2^⋅ΛK1,K2^−1⋅KK1,K2^T⋅σ=EσsupK1∈KK2∈K′σT⋅1γ1KMM1⋅σ+σT⋅1γ2KMM2⋅σ−σT⋅1γ1KMU1−1γ2KMU2⋅O⋅ΔUUλ,K1,K2⋅OT2⋅σ1/2=EσsupK1∈KK2∈K′1γ1∑i,j∈Nmσi⋅σi⋅K1xi,xj+1γ2∑i,j∈Nmσi⋅σi⋅K2xi,xj−σT⋅1γ1KMU1−1γ2KMU2⋅O⋅ΔUUλ,K1,K2⋅OT2⋅σ1/2≤EσsupK1∈KK2∈K′2γ1∑i,j∈Nm,i<jσi⋅σj⋅K1xi,xj+2γ2∑i,j∈Nm,i<jσi⋅σj⋅K2xi,xj+1γ1∑i∈NmK1xi,xi+1γ2∑i∈NmK2xi,xi−σT⋅1γ1KMU1−1γ2KMU2⋅O⋅ΔUUλ,K1,K2⋅OT2⋅σ1/2≤2mγ1UmK+2mγ2UmK′+κ2mγ1+κ′2mγ2−EσinfK1∈KK2∈K′σT⋅1γ1KMU1−1γ2KMU2⋅O⋅ΔUUλ,K1,K2⋅OT2⋅σ1/2.
The second equation uses Equation (51), the forth inequality is obtained by using Jensen’s inequality twice, and the last inequality uses the definition of Rademacher chaos complexity and the finite of kernels.Proof (Proof of Theorem 1).
For anyf∈ℋ^K,K′, it is easy to show that(54)EPLfX,Y−∑i∈NmLfxi,yi≤supf∈ℋ^K,K′EPLfX,Y−∑i∈NmLfxi,yi,
Combining Lemmas 2, 3, 4, and 5, the result is as follows.Proof (Proof of Corollary 1).
By Gershgorin Circle Theorem (Theorem 7.2.1 on page 381 of [18]), the DUUK1,K2 in Equation (21) can be estimated as follows:(55)diiK1,K2≤u⋅κ2γ1+κ′2γ2,i∈Nu,
Then, we can write Equation (22) as(56)ΔUUλ,K1,K2≥ΔUUλ,κ,κ′≜1λ−1+u⋅κ2/γ1+κ′2/γ21λ−1+u⋅κ2/γ1+κ′2/γ2⋱1λ−1+u⋅κ2/γ1+κ′2/γ2,
So, the result is as follows.Proof (Proof of Corollary 2).
By the assumption in Corollary 2, we have(57)2γ1UmK+2γ2UmK′+κ2γ1+κ′2γ2=4γ1UmK+2κ2γ1=4γ2UmK′+2κ′2γ2,(58)1m⋅EσinfK1∈KK2∈K′σT⋅1γ1KMU1−1γ2KMU2⋅O⋅ΔUUλ,κ,κ′⋅OT2⋅σ=0.
By substituting Equations (57) and (58) into Equation (24), the Corollary 2 follows.


## 6. Discussion

In the above two sections, we give our main results and proof these results. In this section, we will give a comparative discussion of our results to the existing work (in [2] and [11]).First, we can see that the term(59)1m⋅EσinfK1∈KK2∈K′σT⋅1γ1KMU1−1γ2KMU2⋅O⋅ΔUUλ,K1,K2⋅OT2⋅σin Theorem 1 reflects the compatibility of two viewers on the unlabeled samples.(1)
For multiple kernel learning in supervised learning.If we letu=0 and γ1=γ2=λ, then we have(60)2γ1UmK+2γ2UmK′+κ2γ1+κ′2γ2=4λUmK+2κ2λ,(61)1m⋅EσinfK1∈KK2∈K′σT⋅1γ1KMU1−1γ2KMU2⋅O⋅ΔUUλ,κ,κ′⋅OT2⋅σ=0.By Corollary (1) and Equations (60) and (61), we can get that(62)EPLfX,Y−1m∑i∈NmLfxi,yi≤Lsuplocm4λUmK+2κ2λ1/2+3Lsup⋅ln2/δ2m.Then, the main result in [2] recovers from Corollary (1). Therefore, the main result in [2] becomes the special case of Corollary (1).Remark 5.
For the discussion in Section3, if we set u=0 and γ1=γ2=λ and by combining Equation (17), then we have that Equation (14) reduces to Equation (13). Furthermore, let K=K′=1 and K=K′, and we have(63)UmK=UmK=≤2m∑i∈ℕmKxi,xi.
Substituting inequality (63) into inequality (62), we can obtain the generalization bound for the single kernel learning in the framework of supervised learning as follows:(64)EPLfX,Y−1m∑i∈NmLfxi,yi≤Lsuplocm8mλ∑i∈NmKxi,xi+2κ2λ1/2+3Lsup⋅ln2/δ2m.(2)
For coregularized kernel learning in semisupervised learning.
If we letK1∈K, K=1, K2∈K′, and K′=1, by equation we have(65)Eσsupf,g∈ℋK,K′12m∑i∈Nmσi⋅fxi+gxi=12mEσsupK1∈KK2∈K′ΛK1,K2^−1/2⋅KK1,K2^T⋅σ=12mEσΛK1,K2^−1/2⋅KK1,K2^T⋅σ.
And note that Equation (65) is the same as the supremum evaluation in Section 5.2.2 in [11]. So, the main result in [11] recovers from Theorem 1. Then, we have that the main result in [11] can be regarded as the special case of Theorem 1.Remark 6.
For the discussion in Section3, if we set K1∈K, K=1, K2∈K′, and K′=1, then we have that Equation (14) reduces to Equation (12).
In Figure1, we show the relations between the main results in this paper and the results in [2] and [11].Figure 1
Semisupervised learning as supervised learning whenu=0. And if K has a single kernel, we think that it is the special case of multiple kernel learning. The scope of the discussion in [2] is the intersection of the green and blue ellipses, the scope of the discussion in [11] is the yellow ellipse, and the cope of the discussion in this paper is the blue ellipse.


## 7. Conclusion

In this paper, based on semisupervised two-viewers learning, we study the generalization bound of coregularized multiple kernel learning. The main research tool is Rademacher chaos complexity which we use to control the performance of the candidate class of coregularized multiple kernels. In this paper, we mainly blend the work in [2] and [11] to discuss the generalization error of coregularized multiple kernel learning in the semisupervised multiview learning framework. First, we discuss the differences between the learning question proposed by us and the learning questions in [2] and [11]. Then, we analyze the generalization bound of coregularized multiple kernel learning in the semisupervised multiview learning framework. And we show that the existing results in [2] and [11] can be regarded as the special cases of our main results.



---

*Source: 1853517-2018-11-01.xml*