Hachem Kadri
email: hachem.kadri@lif.univ-mrs.fr

Stéphane Ayache
email: stephane.ayache@lif.univ-mrs.fr

Cécile Capponi
email: cecile.capponi@lif.univ-mrs.fr

Sokol

François-Xavier Dupé
email: francois-xavier.dupe@lif.univ-mrs.fr

Emilie Morvant
email: emilie.morvant@lif.univ-mrs.fr

Soon Cheng

Tu Bao Ong

Ho

S Koço

F.-X Dupé

The Multi-Task Learning View of Multimodal Data

Keywords: multimodal learning, multiple views, multi-task kernels, vector-valued RKHS, cross-covariance operator. 1. Sources, or views, or modalities

We study the problem of learning from multiple views using kernel methods in a supervised setting. We approach this problem from a multi-task learning point of view and illustrate how to capture the interesting multimodal structure of the data using multi-task kernels. Our analysis shows that the multi-task perspective offers the flexibility to design more efficient multiple-source learning algorithms, and hence the ability to exploit multiple descriptions of the data. In particular, we formulate the multimodal learning framework using vector-valued reproducing kernel Hilbert spaces, and we derive specific multi-task kernels that can operate over multiple modalities. Finally, we analyze the vector-valued regularized least squares algorithm in this context, and demonstrate its potential in a series of experiments with a real-world multimodal data set.

Introduction

Learning from multiple sources 1 , a.k.a multi-view learning, deals with the integration of different representations of the data, that can be either redundant, complementary, independent, or contradictory, in order to solve a learning problem [START_REF] Cesa-Bianchi | Guest editorial: Learning from multiple sources[END_REF]. Taking into account multimodal inputs can bring various information useful for improving the quality of the learned classifier. This could be very helpful in applications such as bioinformatics, computer vision, multimedia indexing and web search, where several descriptions on the same objects are available.

A number of studies have appeared in the last decade on multi-view learning, which can be broadly classified into three categories:

• supervised setting: multi-view learning is achieved through early fusion of descriptors then learning, or by learning on each view followed by a late fusion [START_REF] Muslea | Active learning with multiple views[END_REF][START_REF] Kludas | Information fusion in multimedia information retrieval[END_REF];

• semi-supervised setting: starting from co-training [START_REF] Blum | Combining labeled and unlabeled data with co-training[END_REF], learning approaches that fall in this category aim at exploiting the agreements between views, usually through regularization approaches on the non-labeled examples [START_REF] Balcan | Co-training and expansion: Towards bridging theory and practice[END_REF][START_REF] Christoudias | Multi-view learning in the presence of view disagreement[END_REF][START_REF] Sindhwani | An RKHS for multi-view learning and manifold coregularization[END_REF][START_REF] Wang | On multi-view active learning and the combination with semisupervised learning[END_REF];

• unsupervised setting: the idea here is to apply the co-regularization framework to unsupervised learning problems, such as clustering and dimensionality reduction (Kumar and Daumé III, 2011;Kumar et al., 2011).

In this paper, we focus on the supervised learning part. We tackle the multi-view learning problem with a multi-task learning point of view and illustrate how to capture the interesting multimodal structure of the data using multi-task kernels. Indeed, learning from multiple views is closely related to multi-task learning, and some work has pointed out this connection [START_REF] Szedmak | Learning via linear operators: Maximum margin regression[END_REF][START_REF] Cavallanti | Linear algorithms for online multitask classification[END_REF][START_REF] Christoudias | Multi-view learning in the presence of view disagreement[END_REF]. However, most research in the area of multi-view (or/and multimodal) learning seems to have evolved as a "parallel learning strategy" to the larger area of multi-task learning. While the two learning mechanisms are similar, the viewpoints and ways of thinking about these tasks tend to be quite different. A major goal of this paper is to make some directly ideas from multi-task learning applicable in multi-view setting.

Learning from multiple views can be viewed as a special case of multi-task learning, where all tasks share the same label [START_REF] Cavallanti | Linear algorithms for online multitask classification[END_REF]. To further strengthen the link between multi-task and multi-view learning in this paper, we take advantage of the flexibility endowed by the vector-valued reproducing kernel Hilbert space (RKHS) framework [START_REF] Micchelli | On learning vector-valued functions[END_REF] and the ability of multi-task kernels (Micchelli and Pontil) to operate over multiple modalities (Section 3). Then, we describe and analyze the vectorvalued regularized least squares algorithm for learning when multiple views of the data are provided for training (Section 4). Finally, we demonstrate the merits of our approach on a real-world multimodal data set (Section 5).

To the best of our knowledge, the most directly related work to this paper is that of [START_REF] Luo | Vector-valued multi-view semi-supervised learning for multi-label image classification[END_REF] and [START_REF] Minh | A unifying framework for vector-valued manifold regularization and multi-view learning[END_REF]. In these two papers, the authors have studied the problem of multi-view learning using vector-valued RKHS in semi-supervised setting. However, in [START_REF] Luo | Vector-valued multi-view semi-supervised learning for multi-label image classification[END_REF] the vector-valued approach has been adopted to deal with multi-label classification and not the multi-view setup. A multiple kernel learning (MKL) approach has been used due to the presence of multiple views of input data, but this fails to capture between-view information. In [START_REF] Minh | A unifying framework for vector-valued manifold regularization and multi-view learning[END_REF] the connection between multi-view learning and vector-valued manifold regularization has been explored, providing a unifying framework linking these two learning approaches. In this setting, a crucial issue, which has not been discussed in [START_REF] Minh | A unifying framework for vector-valued manifold regularization and multi-view learning[END_REF], is the choice of the multi-task kernel as a way to exhibit the interesting multimodal structure of the data. We address this by introducing multi-task kernels based on cross-covariance operators on RKHS that allow modeling variables of multiple types and modalities. The remainder of the paper is mainly concerned with vector-valued RKHS and multi-task kernels, and their connections to supervised learning from multiple sources/views.

Multi-Task Learning with Kernels: A Brief Review

In this section, we briefly review the formal setup for multi-task learning using regularization in a reproducing kernel Hilbert space (RKHS) H with a multi-task kernel K(•, •). It extends the single-task kernel learning framework [START_REF] Schölkopf | Learning with kernels: Support vector machines, regularization, optimization, and beyond[END_REF] to multi-task setting. We refer the reader to [START_REF] Evgeniou | Learning multiple tasks with kernel methods[END_REF] and references therein for more details.

In the standard multi-task learning setup we have p tasks. For the l-th task, l ∈ N p (we use the notation N p for the set {1, . . . , p}), n examples {(x il , y il ) : i ∈ N n } ⊂ X l × Y l sampled i.i.d. from an unknown probability distribution P l on X l × Y l are available. The total data available is then {(x il , y il ) : i ∈ N n , l ∈ N p }, and the goal is to learn all p functions f l : X l → Y l simultaneously from the available data. It is common in multi-task learning to assume that the tasks share the same input space, that is X l = X for all l. In this case, multitask learning can be formulated as a vector-valued function learning problem [START_REF] Micchelli | On learning vector-valued functions[END_REF], where the goal is to learn a function f from X to Y; the input space X is typically a subset of R d , the d dimensional Euclidean space, and the output space Y is a subset of R p containing the outputs of the p tasks. To this end, a common approach is to learn f as the minimizer in a vector-valued RKHS H of the functional

1 n i∈Nn V (y i , f (x i )) + λ f 2 H , (1)
where y i = (y il ) l∈Np ∈ R p , λ > 0 is a regularization parameter, and f H is the norm of f in H. V is a convex loss function such as the square error y if (x i )2 Y . A vector-valued RKHS is uniquely defined by a positive definite multi-task kernel K(•, •); that is a matrix-valued function of two variables satisfying the following two properties.

Definition 1. (Positive definite multi-task kernel). A function

K : X × X → L(Y)
, where L(Y) is the the space of bounded linear operators from Y into itself 2 , is positive definite if the following holds (a) K(x, z) * = K(z, x), for any (x, z) ∈ X 2 , where * denotes the adjoint, (b) i,j∈Nq y i , K(x i , x j )y j Y ≥ 0, for any q ∈ N, {x i : i ∈ N q } ⊆ X , and

{y i : i ∈ N q } ⊆ Y.
Corresponding to any such kernel K(•, •) there is a map Φ from X × Y to a feature space F, such that:

y, K(x, z)v Y = Φ(x, y), Φ(z, v) F ,
for any (x, z) ∈ X 2 and (y, v) ∈ Y 2 . Hence, the kernel can be used, as with the basic scalarvalued kernel, to compute an inner product in the feature space. This is referred to as the multi-task "kernel trick". Note that the usual kernel trick can be recovered when p = 1.

One particularly attractive instantiation of such a feature space is the vector-valued RKHS H associated with the multi-task kernel K(•, •). Consider the set of functions {K(•, x)y : x ∈ X , y ∈ Y}, where x and y index the set of functions and the dot represents the argument to a given function. The span of such functions defines a linear space that is unique and can always be completed into a Hilbert space [START_REF] Schwartz | Sous-espaces hilbertiens d'espaces vectoriels topologiques et noyaux associés (noyaux reproduisants)[END_REF][START_REF] Micchelli | On learning vector-valued functions[END_REF]. The crucial property of these Hilbert spaces is the "reproducing property" of the kernel y, f (x) Y = K(•, x)y, f H , for any x ∈ X , y ∈ Y, and f ∈ H. Note in particular that if we define Φ(x, y) = K(•, x)y as a map into the vector-valued RKHS, then we have

Φ(x, y), Φ(z, v) F = K(•, x)y, K(•, z)v F = y, K(x, z)v Y ,
and thus Φ(x, y) = K(•, x)y is indeed an instantiation of the feature space perspective of the multi-task kernel. For completeness, we recall the definition of vector-valued RKHS.

Definition 2. (vector-valued RKHS). A vector-valued reproducing kernel Hilbert space is a Hilbert space H of functions f : X → Y that possesses a (matrix-valued) multi-task reproducing kernel, i.e., a function K : X × X → L(Y) for which the following holds

(a) K(x, •)y ∈ H for all x ∈ X , y ∈ Y, (b) f, K(•, x)y H = f (x), y Y for all x ∈ X , y ∈ Y, and f ∈ H.
It is important to note that there is a bijection between positive semidefinite multi-task kernels and vector-valued RKHS. Moreover, the multi-task kernel associated with a vectorvalued RKHS is unique. This guarantees the unicity of the solution to the problem (1) which is given by the representer theorem [START_REF] Micchelli | On learning vector-valued functions[END_REF].

Representer theorem. (vector-valued case). Any solution to the problem: find f ∈ H to minimize (1) has a representation of the form

f (•) = i∈Nn K(•, x i )c i , (2)
where c i ∈ Y.

The result in Equation ( 2) is noteworthy as it makes the optimization problem (1) amenable for computations. In particular, the unique minimizer of functional (1) can be found by replacing f by the right hand side of Equation (2) in Equation ( 1) and then optimizing with respect to the parameters {c i : i ∈ N n }.

We now show how multi-task learning using regularized kernel methods, as described above, is useful for "supervised" learning when multiple views of the data are available.

Multi-View Learning from a Multi-Task Perspective

In this section, we start by formalizing the link between kernel-based multi-task learning and multi-view learning. We then discuss multi-task kernels built from cross-covariance operators as a viable way of modeling within-and between-view information.

Framework

Consider the general setting of supervised learning with multiple views, where we aim to identify a target function given a set of labeled data drawn from m different sources. The training data is composed by multiple and various sets of features. One way to tackle this problem is to define a kernel for each view and to consider a regularized risk minimization problem in a reproducing kernel Hilbert space (RKHS) H arg min

f (•)∈H 1 n n i=1 V (y i , f (x i )) + λ f 2 , ( 3
)
where f = (f 1 , . . . , f m ) ∈ H 1 × . . . × H m , V (y, •) is a convex loss function, and λ ≥ 0 is a regularization parameter. Given n training data {(x i , y i ) : i ∈ N n } ⊂ (X × Y
) n (we use the notation N n for the set {1, . . . , n}) where each example

x i = (x (1) i , . . . , x (m)
i ) is seen in m views, H 1 , . . . , H m are the scalar-valued RKHSs associated respectively to the reproducing kernels k 1 , . . . , k m defined for each view.

Much previous work in the machine learning literature has focused on learning f in a scalar-valued RKHS [START_REF] Brefeld | Efficient co-regularised least squares regression[END_REF][START_REF] Farquhar | Two view learning: SVM-2K, theory and practice[END_REF][START_REF] Sindhwani | An RKHS for multi-view learning and manifold coregularization[END_REF]. This means that the decision function f (x) is obtained by computing the m functions f s , s ∈ N m , independently for each view. It is true that these previous work succeed in taking into account dependencies between views ; however, this is achieved only through regularization and mainly in the presence of unlabeled data. In the supervised setting, using a scalar-valued RKHS and learning independently the function (f s ) s∈Nm may fail to fully take into account the structure of multimodal data, since it is difficult to optimize the agreement between views under some assumptions (redundancy of views and conditional independence) or to promote some other properties among views, especially when the number of views m is large. Vector-valued RKHS and their associated multi-task kernels offer more natural and more powerful specialized procedures for addressing this issue.

In this work we adopt a multi-task kernel approach to take into account within-and between-view information. Multi-task kernels have been introduced in the machine learning community by Micchelli and Pontil in order to learn simultaneously multiple tasks [START_REF] Evgeniou | Learning multiple tasks with kernel methods[END_REF] and have recently been used successfully in functional regression [START_REF] Kadri | Functional regularized least squares classification with operator-valued kernels[END_REF] and structured output prediction [START_REF] Brouard | Semi-supervised penalized output kernel regression for link prediction[END_REF]Kadri et al., 2013b), but to our knowledge have never been applied to the problem of multi-view learning until recently [START_REF] Minh | A unifying framework for vector-valued manifold regularization and multi-view learning[END_REF]. We recall that the idea here is to consider the problem of learning from multiple views as a special case of multi-task learning where all tasks share the same label, and to learn the function f in a vector-valued RKHS. To this end, output values (labels) y i are considered to be vectors in R m , where m is the number of views, instead of real variables as usual. The simplest representation would therefore consist of m repetitions of the real-valued labels, even if it might be possible to design more sophisticated representations to encode specific prior knowledge about the task into the model. By doing this, one can make use of multi-task kernels, which in this case are matrix-valued functions from X × X → R m×m (since Y = R m ), to exhibit the interesting multimodal structure of the data represented by different features. In the following we show how to construct such kernels, but before this we recall that the solution to the multi-view learning problem (3) in a vector-valued RKHS is given by the representer theorem, and has the following form

f (•) = i∈N K(•, x i )c i , (4)
where c i ∈ R m . The learning algorithm will then be based on computing and manipulating the kernel matrix associated with the matrix-valued function K(•, •). In this setting, the kernel matrix is a block matrix of size nm × nm, where each block of size n × n at the s-th row and the t-th column, (s, t) ∈ (N m ) 2 , is devoted to take into account information between views s and t. This is described in more details in the next subsection.

Multi-task kernels for multimodal data

In the multi-view learning setting and in order to encode within-and between-view information, we strongly prefer to view the multi-task kernel as a scalar-valued function rather than viewing it as a matrix-valued function. The multi-task kernel K(•, •), which takes two examples x and x ′ and outputs a matrix of dimension m×m, with m the number of views, can be reformulated using a scalar-valued function (kernel) k on two pairs of input/view (Wahba, 1992;[START_REF] Evgeniou | Learning multiple tasks with kernel methods[END_REF] as follows

k(x, t, x ′ , s) = K(x, x ′ ) ts , where (x, x ′ ) ∈ (X ) 2 , (s, t) ∈ (N m ) 2 , and K(x, x ′ ) ∈ R m×m .
In this way, it is possible to construct the block kernel matrix K = K(x i , x j ) (i,j)∈(Nn) 2 ∈ R nm×nm from blocks of size n × n over input features of each view (or source) instead of blocks of size m × m over outputs. Since the tasks share the same labels, this is more convenient in order to extract the inherent structure that is informative on the multimodal data.

Multi-task kernel based on cross-covariance operator. In order to take into account within-and between-view information, we consider multi-task kernels built from cross-covariance operators on RKHS. Covariance operators on RKHS have recently received considerable attention. For example, these operators that provide the simplest measure of dependency have been successfully applied to the problem of dimensionality reduction [START_REF] Fukumizu | Dimensionality reduction for supervised learning with reproducing kernel Hilbert spaces[END_REF] and played an important role in dealing with a number of statistical test problems [START_REF] Gretton | Measuring statistical dependence with hilbert-schmidt norms[END_REF]. More recently, covariance-based operator-valued kernels have been introduced in the context of structured output learning to capture the dependencies between the outputs as well as between the input and output variables (Kadri et al., 2013b). Here we expand the applicability of these kernels to multiview learning setting. We propose to construct a multi-task kernel that can operate over multiple modalities as the following

k(x i , t, x j , s) = k t (x (t) i , •), C XtXs k s (x (s) j , •) , (5)
where C XtXs : H s → H t is the cross-covariance operator between the RKHSs H s and H t . To compute the kernel k, we have to estimate the cross-covariance operator with given data. The empirical cross-covariance operator Ĉ(n) XtXs is given by

Ĉ(n) XtXs = 1 n n i=1 k t (x (t) i , •) ⊗ k s (x (s) i , •),
where ⊗ is the tensor product defined by (f ⊗ g)h = g, h f , for all f ∈ X t and g, h ∈ X s . Thus, by restricting the cross-covariance operator C XtXs to the n-dimensional subspaces spanned by {k t (x

(t) i , •)} n i=1 and {k s (x (s) i , •)} n i=1
, we can estimate the operator by Ĉ(n) XtXs = k t k s , where k t and k s are the kernel matrices associated with the scalar-valued kernels k t and k s , respectively [START_REF] Fukumizu | Dimensionality reduction for supervised learning with reproducing kernel Hilbert spaces[END_REF]. The multi-task kernel thus built permits us to encode the interactions between views s and t, and the resulting block kernel matrix

K = k(x i , t, x j , s) (s,t)∈(Nm) 2
(i,j)∈(Nn) 2 allows to incorporate all the available information regarding the m views into the model. Special cases. The kernel matrix built from the above multi-task kernel is a full block matrix in that it consists of all the cross-covariance blocks from the views. One can alternatively consider only within-view information and would not necessarily need betweenview dependencies. In this case, the kernel matrix is block diagonal and the associated multi-task kernel is

k(x i , t, x j , s) = δ ts k t (x (t) i , •), C XtXs k s (x (s) j , •)
, where δ ts is the Kronecker delta function: δ ts = {1 if t = s, 0 otherwise}. One particularly attractive instantiation of such a kernel is when the cross-covariance operator is replaced by the identity operator

k(x i , t, x j , s) = δ ts k t (x (t) i , •), k s (x (s) j , •) . (6)
The kernel matrix is then block diagonal and each block corresponds to the "scalar-valued" kernel matrix over one view (or source). In other works, applying the vector-valued RKHS framework using the multi-task kernel of Equation ( 6) is equivalent to using a basic "uniformly weighted" multiple kernel learning (MKL) approach [START_REF] Bach | Multiple kernel learning, conic duality, and the SMO algorithm[END_REF].

Algorithm and Computational Aspects

We now discuss the multi-task kernel based algorithm used in this work to tackle the problem of learning from multiple views. In particular, based on the framework described above, we will concentrate on the vector-valued regularized least squares (RLS) algorithm, and we show how computational efficiency results well know in the scalar-valued case [START_REF] Rifkin | Notes on regularized least-squares[END_REF] can be restated in the vector-valued setting.

Vector-valued RLS

Vector-valued RLS algorithm is based on the squared loss

V (y, ŷ) = y -ŷ 2 R m . (7)
Substituting Equation ( 7) in the problem (3), the minimization problem associated with the multi-task formulation of supervised multi-view learning can be written as arg min

f (•)∈H 1 n n i=1 y i -f (x i ) 2 + λ f 2 H . (8)
Using the representer theorem, the problem (8) becomes arg min

c∈R nm 1 n y -Kc 2 + λ Kc, c , (9)
where c = (c i ) i∈Nn ∈ R nm×1 (c i ∈ R m ), y = (y i ) i∈Nn ∈ R nm×1
, and K is the block kernel matrix such that K = k(x i , t, x j , s) i,j,s,t ∈ R nm×nm , for all (i, j) ∈ (N n ) 2 and (s, t) ∈ (N m ) 2 . Setting the derivative with respect to c to zero, we see that c must satisfy

(K + λI)c = y, (10)
where I denotes an appropriately-sized identity matrix. The prediction of a new test point x is given by

f (x) = i∈Nn K(x, x i )c i = K x (K + λI) -1 y,
where K x is the m × nm matrix with m × m block entries K(x, x i ) i∈Nn . These results are very similar to those in the usual scalar-valued case. A major difference is the use of a block kernel matrix instead of a Gram matrix.

Leave-one-out procedure

In this subsection, we show how the classical result regarding computing in a closed form the leave-one-out solution in the case of regularized least squares [START_REF] Wahba | Spline models for observational data[END_REF][START_REF] Rifkin | Notes on regularized least-squares[END_REF] can be extended to the vector-valued setting. While the extension can be carried out in a direct way, it has, to the best of our knowledge, never been worked out before, and provides an adequate mechanism for finding a "good" value of the regularization parameter λ involved in the vector-valued RLS optimization problem (see Equation ( 8)).

We shall use the notation of [START_REF] Rifkin | Notes on regularized least-squares[END_REF] . Let f S i be the solution of the vector-valued RLS function trained on S i , where S i is the data set with the i-th point removed from the training set S = {(x j , y j ) :

j ∈ N n } ⊂ (X × Y) n (Y = R m ,
where m is the number of views). We define LOOV = f S i (x i ) i∈Nn and LOOE = y i -f S i (x i ) i∈Nn to be the vectors of leave-one-out values and errors over the training set. Let y i = (y i j ) j∈Nn , where y i j ∈ R m , be the nm-dimensional vector defined by:

y i j = y j j = i f S i (x i ) j = i.
If we solve the vector-valued RLS problem (8) when replacing the outputs y = (y j ) j∈Nn by y i , the optimal solution will be f S i . This can be seen by observing that, for any f ∈ H,

1 n n j=1 y i j -f (x i ) 2 + λ f 2 H ≥ 1 n j =i y i j -f (x i ) 2 + λ f 2 H ≥ 1 n j =i y i j -f S i (x i ) 2 + λ f S i 2 H = 1 n n j=1 y i j -f S i (x i ) 2 + λ f S i 2 H .
The above inequality says that we can write the vector of expansion coefficients c i of the predictor f S i given by the representer theorem as c i = G -1 y i , where G = (K + λI) with K = K(x i , x j ) (i,j)∈(Nn) 2 the nm × nm block kernel matrix associated with the multi-task kernel K(•, •) evaluated at the training points, and therefore

f S i (x i ) = K x i G -1 y i ,
where K x i is the m × nm matrix with m × m block entries K(x i , x j ) j∈Nn . This allows us to express f S i (x i ) in terms of f S (x i )

f S i (x i ) -f S (x i ) = K x i G -1 y i -K x i G -1 y = j∈Nn [KG -1 ] i,j (y i j -y j ) = [KG -1 ] i,i (f S i (x i ) -y j ), which leads to f S i (x i ) = [I -(KG -1 ) i,i ] -1 [f S (x i ) -(KG -1 ) i,i y i ].
Then,

f S i (x i ) = [I -(KG -1 ) i,i ] -1 [K x i G -1 y -(KG -1 ) i,i y i ]. ( 11
)
From Equation ( 11), it is straightforward to see that

LOOV = [diag b (I -KG -1 )] -1 [KG -1 y -diag b (KG -1 )y],
where diag b denotes the block diagonal operator3 . We thus obtain

LOOE = y -LOOV = y + [diag b (I -KG -1 )] -1 [diag b (KG -1 )y -KG -1 y] = [diag b (I -KG -1 )] -1 [diag b (I -KG -1 )y + diag b (KG -1 )y -KG -1 y] = [diag b (I -KG -1 )] -1 [y -KG -1 y]. (12)
This expression can be simplified in a way that leads to better computational properties. Let D and Q be the square matrices such that K = QDQ ⊤ . D and Q are generated by matrix diagonalization. We can note that

KG -1 = QDQ ⊤ Q(D + λI) -1 Q ⊤ = QD(D + λI) -1 Q ⊤ = Q(D + λI -λI)(D + λI) -1 Q ⊤ = I -λG -1 . (13)
Substituting Equation (13) in Equation ( 12), we obtain

LOOE = [diag b (I -(I -λG -1 ))] -1 [y -(I -λG -1 )y] = [diag b (G -1 )] -1 G -1 y = [diag b (G -1 )] -1 c. (14)
It is interesting to note that the leave-one-out solution in the scalar-valued case can be recovered from Equation ( 14) when the number of views m is equal to 1.

Efficient computation

As we have seen in the previous subsection, the leave-one-out error associated with a vectorvalued RLS algorithm can be computed in a closed form that provides a convenient way to choose a "good" value for the regularization parameter λ. However, this needs the computation of the solution of the vector-valued RLS algorithm for each value of λ. Selecting the value of λ using leave-one-out procedure can be then computationally demanding, since we have to perform a matrix inversion which costs O(n 3 m 3 ) for every λ. To address this issue, we show, as with the scalar-valued case, how the vector of coefficients c (Equation ( 10)), solution of the vector-valued RLS problem, can be efficiently calculated for different values of λ.

Let the eigendecomposition of K be K = QDQ ⊤ , where D is diagonal with D i,i ≥ 0 and QQ ⊤ = I. Then, the solution of the vector-valued RLS c can be expressed as

c = (K + λI) -1 y = (QDQ ⊤ + λI) -1 y = Q(D + λI)Q ⊤ -1 y = Q(D + λI) -1 Q ⊤ y. (15)
The computational complexity of computing the eigendecomposition of K and calculating Q ⊤ y is O(n 3 m 3 ) and O(n 2 m 2 ), respectively. Once these two terms have been computed, they will be stored in the memory. Hence, since the inversion and the multiplication of the diagonal matrix D + λI with Q ⊤ y can be performed in O(nm) time and the multiplication of the resulting matrix from left by Q costs O(n 2 m 2 ), the solution c can be calculated from Equation ( 15) for different values of the regularization parameter λ with the complexity of O(n 2 m 2 ). Moreover, we can compute [diag b (G -1 )] -1 (see Equation ( 14)) in O(n 2 m 3 ) time instead of O(n 3 m 3 ). This can be seen from the following equation

(G -1 ) (i,j)∈(Nn) 2 = Q(D + λI) -1 Q ⊤ (i,j)∈(Nn) 2 = l∈Nn Q i,l (D l,l + λI) -1 Q j,l , (16)
where M (i,j)∈(Nn) 2 denotes the (i, j)-th m×m block of the block matrix M of size nm×nm.

(G -1 ) (i,j)∈(Nn) 2 can be calculated from Equation ( 16) in O(nm 3 ) time. The computation of [diag b (G -1 )] -1 can then be performed in O(n 2 m 3 ), since the inverse of a block diagonal matrix is also a block diagonal matrix and can be found by inverting individually the blocks. Therefore, as the computational cost of the vector-valued RLS algorithm is O(n 3 m3), we can compute the solution coefficients c and the leave-one-out error LOOE over a fine grid of λ without additional cost if we perform an eigendecomposition of the block kernel matrix K. This complexity can be reduced via the Kronecker tensor product [START_REF] Minh | A unifying framework for vector-valued manifold regularization and multi-view learning[END_REF] ; however this is restricted to the particular case of separable multi-task kernels (or block diagonal kernel matrix). Here we are interested in the general case of any multi-task kernel, and consider a sparse approximation of vector-valued RLS in which only a part of the training instances has a non-zero coefficient in Equation ( 2) [START_REF] Rifkin | Regularized least squares classification[END_REF][START_REF] Pahikkala | Efficient cross-validation for kernelized leastsquares regression with sparse basis expansions[END_REF]. Let W ⊆ N n be a subset of N n and w = |W |. By M w ∈ R wm×nm we denote the block submatrix of M ∈ R nm×nm that contains only the block rows indexed by W . M ww ∈ R wm×wm denotes a block submatrix of M having block rows and columns indexed by W . Following [START_REF] Rifkin | Regularized least squares classification[END_REF], we consider instead of Equation ( 2) a solution allowing only the training points indexed by W to have non-zero coefficients. More formally, we consider

f (•) = i∈W K(•, x i )c i ,
where the set W is selected in advance. In this case, the vector of expansion coefficients c = (c i ) i∈W , where c i ∈ R m , is a wm-dimensional vector, and the minimization problem (9) associated with the vector-valued RLS algorithm becomes arg min

c∈R wm 1 n y -K ⊤ w c 2 + λ K ww c, c . (17)
By setting the derivative of problem ( 17) with respect to c to zero, we obtain

(K w K ⊤ w + λK ww )c = K w y. (18)
Equation ( 18) shows that when we only allow a subset of size w points to have non-zero coefficients in the expansion, we can solve a wm by wm system of equations rather than an nm by nm system. Moreover, as in the scalar-valued case [START_REF] Pahikkala | Efficient cross-validation for kernelized leastsquares regression with sparse basis expansions[END_REF], we can see that the matrices K ww and K w K ⊤ w = (KK) ww are principal sub matrices of the positive definite block kernel matrices K and KK, respectively. Then the matrix T = (K w K ⊤ w + λK ww ) is also positive definite and invertible. The solution of the vectorvalued RLS optimization is then given by

c = T -1 K w y. (19)
Hence, the matrix inversion involved in the vector-valued RLS algorithm can be performed by this procedure in O(w 3 m 3 ) time (Equation ( 19)) instead of O(n 3 m 3 ) (Equation ( 10)).

Experiments

In order to get a first experimental feedback of the usefulness of the cross-covariance operator within the vector-valued RLS algorithm, we performed experiments on the dataset Animals With Attributes (AwA) [START_REF] Lampert | Learning to detect unseen object classes by between-class attribute transfer[END_REF], which features six views describing images from 50 concepts (i.e. labels) in a multiclass supervised setting. Each view is described through hundreds of float-typed attributes. We compare our algorithm with: (1) a "uniformly weighted" MKL with a least squares loss, which can be seen as a late fusion algorithm and can be derived from our framework, and (2) an early fusion SVM algorithm.

Dataset Animals with Attributes (AwA)

We chose the dataset AwA because it comes with 6 views over 30, 475 images to be classified within 50 concepts in a multi-class setting (only one class labels each example). As pointed out below, these views depict various focus on the numerical representation of images; they may be either correlated, complementary, redundant, or even conflicting.

• cq: (global) color histogram (1 × 1 + 2 × 2 + 4 × 4 spatial pyramid, 128 bins each, each histogram L1-normalized).

• lss: local self similarity (2, 000 entry codebook, raw bag-of-visual-word counts).

• phog: histogram of oriented gradients (1 × 1 + 2 × 2 + 4 × 4 spatial pyramid, 12 bins each, each histogram L1-normalized or all zero).

• rgsift: rgSIFT descriptors (2, 000 entry codebook, bag-of-visual-word counts, L1normalized).

• sift: SIFT descriptors (2, 000 entry codebook, raw bag-of-visual-word counts).

• surf: SURF descriptors (2, 000 entry codebook, raw bag-of-visual-word counts)

Protocol

Since AwA is a multi-class learning problem, we processed a one-vs-all learning and testing protocol. For each concept, a classifier is trained from the n examples of the concept and 2n randomly selected examples among other concepts (n varies from 46 to 584, depending on the concept ; see Table 1). Each experiment is performed once with a random training set of size 3n (n is the number of examples of the current concept) and a random testing set of twice that size. In each experiment, the hyper-parameter λ is set using the LOOE method. All reported methods use a kernel: the χ 2 kernel is used everywhere, as usually done on histogram-based descriptors. The accuracy of each algorithm is reported for the algorithms: MKL (uniformly weighted), MVK (our Multi-View learning method with cross-covariance multi-task Kernel), and an SVM processed on the Early fusion of views using SVM (E-SVM).

Results

Table 1 summarizes the performance results of the MKL, MVK, and E-SVM, on the dataset AwA4 . It shows that our approach with multi-task cross-covariance kernel (MVK) performs better than the other approaches on many concepts, and in average. It is worthwhile noticing that when MVK is worse than MKL on a given concept, the difference may not be significative. Still, MVK performs better on the most difficult concepts if considering all the views (mole which has only 46 examples for learning, Polar-bear where only colorbased views are informative, etc.). Besides, Having a large look on all concepts (cf. row ALL -mean accuracy ), MVK performs better in accuracy than the other methods. These first experimental results acknowledge the relevance of our approach: information betweenviews is actually taken into account for a better accuracy. The overall performances of our approach are quite promising, and validate its pertinence.

Conclusion

The main point of this paper was to introduce and evaluate a method for learning from multiple views using a multi-task learning perspective. We have shown the ability of multi-task kernels in conjunction with cross-covariance operators on RKHS to capture the interesting multimodal structure of the data. Our first experimental results on a real-world dataset show that, in contrast to standard supervised multi-view learning methods, the vectorvalued RLS algorithm with cross-covariance multi-task kernels allows to easily incorporate both within and between-view information. Future work will aim to extend the presented multi-view/multi-task ideas towards ranking problems.

  4.4. Speeding-up training : sparse vector-valued RLSObviously, the computational complexity of the vector-valued RLS algorithm is O(n 3 m 3 ), and the training can be too costly with large numbers of training examples and/or views.

Table 1 :

 1 Accuracy of unweighted MKL, our approach MVK based on cross-covariance multitask kernel, and an early fusion with SVM (E-SVM), on the dataset AwA.

	class	n	MKL	MVK	E-SVM	class	n	MKL	MVK E-SVM
	antelope	273 98.21	95.34	90.89	hamster	421	62.03	93.62	83.57
	grizzly+bear	440	74.77	94.55	86.76	squirrel	454	61.07	95.07	84.51
	killer+whale	271	75.45	92.92	90.12	rhinoceros	350	97.71	97.12	87.80
	beaver	93	97.62	91.48	83.17	rabbit	284	98.13	95.14	83.48
	dalmatian	295 98.07	95.24	88.12	bat	201	50.03	91.51	82.46
	persian+cat	357 97.59	92.91	86.91	giraffe	550	96.39	95.44	88.51
	horse	411	84.60	92.38	87.66	wolf	273	98.21	93.33	86.34
	german+shepherd 529	84.11	95.24	86.83	chihuahua	347	97.73	92.80	86.10
	blue+whale	131 95.11	92.02	89.54	rat	152	98.84	93.37	85.73
	siamese+cat	243 98.41	91.88	86.16	weasel	140	99.07	80.17	84.59
	skunk	142	93.93	96.56	88.35	otter	363	97.62	94.46	83.99
	mole	46	63.01	94.97	75.23	buffalo	280	98.16	94.14	88.02
	tiger	273 98.21	95.36	87.58	zebra	385c	81.37	98.32	92.71
	hippopotamus	362 97.60	93.04	87.08	giant+panda	471	59.25	96.44	89.73
	leopard	304 98.00	94.78	89.11	deer	537	56.42	90.64	83.76
	moose	361	83.51	92.41	85.14	bobcat	321	97.90	93.69	84.49
	spider+monkey	176	91.28	95.61	92.09	pig	166	98.90	98.25	89.30
	humpback+whale 358 96.55	94.53	90.46	lion	242	98.41	92.20	87.79
	elephant	374	72.99	94.36	87.94	mouse	104	99.10	82.28	81.05
	gorilla	402 97.36	95.15	89.40	polar+bear	408	64.01	92.53	87.28
	ox	84	47.77	92.87	93.33	collie	584	49.67	94.06	96.16
	fox	213 98.60	94.15	89.27	walrus	169	97.14	94.14	90.35
	sheep	316 97.93	96.46	87.70	raccoon	317	97.92	94.89	87.57
	seal	255 97.01	89.68	82.89	cow	329	97.84	91.11	86.07
	chimpanzee	351	76.51	89.06	87.27	dolphin	341	67.18	92.80	89.16
	ALL		86.686 93.409	87.190

If p, the number of tasks, is finite, Y ⊆ R p is finite-dimensional and L(Y) = R p×p is the vector space of symmetric matrices of size p × p. In this case, the multi-task kernel K(•, •) is also called matrix-valued kernel[START_REF] Reisert | Learning equivariant functions with matrix valued kernels[END_REF].

Given a block matrix M of size nm × nm, diag b (M ) is the block diagonal matrix satisfying diag b (M )i,i = Mi,i, where Mi,i is the block at the ith row and the ith column of size m × m and i ∈ Nn.

For more experimental results with the same data set, see(Kadri et al., 2013a).

Acknowledgments

We would like to thank Liva Ralaivola for helpful discussions. This research was funded by the Ministry of Higher Education and Research and the CNRS PEPS program in Biology-Mathematics-Informatics.