Alain Rakotomamonjy

Rémi Flamary

Gilles Gasso

Canu Stéphane

EA Litis

ℓ pℓ q penalty for Sparse Linear and Sparse Multiple Kernel Multi-Task Learning

Keywords: Multi-task learning, multiple kernel learning, sparsity, mixed-norm, Support Vector Machines

Recently, there has been a lot of interest around multi-task learning (MTL) problem with the constraints that tasks should share a common sparsity profile. Such a problem can be addressed through a regularization framework where the regularizer induces a joint-sparsity pattern between task decision functions. We follow this principled framework and focus on ℓpℓq (with 0 ≤ p ≤ 1 and 1 ≤ q ≤ 2) mixed-norms as sparsityinducing penalties. Our motivation for addressing such a larger class of penalty is to adapt the penalty to a problem at hand leading thus to better performances and better sparsity pattern. For solving the problem in the general multiple kernel case, we first derive a variational formulation of the ℓ1 -ℓq penalty which helps up in proposing an alternate optimization algorithm. Although very simple, the latter algorithm provably converges to the global minimum of the ℓ1 -ℓq penalized problem. For the linear case, we extend existing works considering accelerated proximal gradient to this penalty. Our contribution in this context is to provide an efficient scheme for computing the ℓ1 -ℓq proximal operator. Then, for the more general case when 0 < p < 1, we solve the resulting non-convex problem through a majorization-minimization approach. The resulting algorithm is an iterative scheme which, at each iteration, solves a weighted ℓ1 -ℓq sparse MTL problem. Empirical evidences from toy dataset and real-word datasets dealing with BCI single trial EEG classification and protein subcellular localization show the benefit of the proposed approaches and algorithms.

I. INTRODUCTION

Multi-Task Learning (MTL) is a statistical learning framework which seeks at learning several models in a joint manner. The idea behind this paradigm is that, when the tasks to be learned are similar enough or are related in some sense, it may be advantageous to take into account these relations between tasks. For instance, when the number of samples for learning are small, transferring some knowledge from one task to another while learning can be advantageous in term of generalization performances. Several works have provided empirical evidence on the benefit of such a framework [START_REF] Caruana | Multi-task learning[END_REF], [START_REF] Evgeniou | Regularized multi-task learning[END_REF], [START_REF] Kato | Multi-task learning via conic programming[END_REF], [START_REF] Ozawa | A multitask learning model for online pattern recognition[END_REF]. Application domains that have been shown to benefit from multi-task learning are medical diagnosis [START_REF] Bi | An improved multitask learning approach with applications in medical diagnosis[END_REF], drug therapy prediction [START_REF] Bickel | Multi-task learning for hiv therapy screening[END_REF], vaccine design [START_REF] Jacob | Clustered multi-task learning[END_REF] or conjoint analysis [START_REF] Argyriou | Multi-task feature learning[END_REF].

However, the notion of relatedness between tasks is vague and depends on the problem at hand. For instance, one can consider that models resulting from related tasks should be similar to a single model [START_REF] Evgeniou | Regularized multi-task learning[END_REF], [START_REF] Kato | Multi-task learning via conic programming[END_REF]. In other works, task's relatedness is represented through a probabilistic model [START_REF] Yu | Learning gaussian processes from multiple tasks[END_REF]. Prior knowledge on tasks are then translated into an appropriate regularization term or into a hierarchical Bayesian model that can be handled by a learning algorithm [START_REF] Dunson | The matrix stick-breaking process : flexible bayes meta analysis[END_REF], [START_REF] Xue | Multi-task learning for classification with dirichlet process priors[END_REF], [START_REF] Iii | Bayesian multitask learning with latent hierarchies[END_REF].

In this work, we consider that tasks to be learned share a common subset of features or kernel representation. This means that while learning the tasks, we jointly look for features or kernels that are useful for all tasks. In this context of joint feature selection with multiple related tasks, several works have already been carried out. For instance, Jebara et al. [START_REF] Jebara | Multi-task feature and kernel selection for svms[END_REF] has introduced a maximum entropy discrimination for solving such a problem. Some other works cast the problem into a probabilistic framework which uses automatic relevance determination and a hierarchical Bayesian model for selecting the relevant features [START_REF] Bi | An improved multitask learning approach with applications in medical diagnosis[END_REF], [START_REF] Xiong | Probabilistic joint feature selection for multi-task learning[END_REF]. Another trend considers a regularization principle and thus minimizes a regularized empirical risk with a regularization term that favors a common sparsity profile for all tasks. Such an approach has been investigated by Argyriou et al. [START_REF]Convex multi-task feature learning[END_REF] and Obozinski et al. [START_REF] Obozinski | Joint covariate selection and joint subspace selection for multiple classification problems[END_REF]. In these latter works, the authors propose a ℓ 1 -ℓ 2 regularization term which can be interpreted as a convex extension of the sparsityinducing ℓ 1 norm in single task learning.

As made clear in the sequel, our contribution in this paper lies in between multi-task and multiple kernel learning. Indeed, we provide a methodological framework for learning each task decision functions while these functions use an optimal, in some sense, linear combination of only few kernels. This point highlights the relation between our contribution and multiple kernel learning. Imposing that the few selected kernels are similar across the tasks is the point that defines task's relatedness. Following Obozinski et al. [START_REF] Obozinski | Joint covariate selection and joint subspace selection for multiple classification problems[END_REF] and Argyriou et al. [START_REF]Convex multi-task feature learning[END_REF], we induce this sparsity in joint kernel representation through a regularization principle where the regularization term is a mixed-norm penalty.

In practice and in theory as proved by the works of Lounici et al. [START_REF] Lounici | Taking advantage of sparsity in multi-task learning[END_REF], a fixed non-adaptive penalty like the ℓ 1 -ℓ 2 mixed norm, is beneficial with respects to other penalties only under certain situations. Hence, it seems natural that different penalties may suit better to different data structures. This motivates us to investigate the use of a larger class of mixednorm penalty that can be adapted to the data at hand. We focus here on the class of ℓ p -ℓ q mixed-norm penalty where 0 ≤ p ≤ 1 and 1 ≤ q ≤ 2. Our objective in using p < 1 is to make the kernel representation across tasks sparser than using p = 1; such an increased sparsity profile being valuable in a presence a large amount of noisy features or irrelevant kernels. Furthermore, the sparser representation induced by p < 1 is expected to enhance models interpretability and improve evaluation computational efficiency. Varying q between 1 and 2 allows the task decision functions to adapt themselves to the importance of the task relatedness. Indeed, it would be clear in the following that q = 1 makes the task learning independent while q > 1 ties them through the mixed-norm. Rationales on why we have not investigated cases where 2 < q < ∞ will also be discussed.

Our aim in this paper is to present a simple algorithm for handling the optimization problem resulting of the use of ℓ p -ℓ q mixed-norms regularizers in the multi-task framework and to provide empirical evidences that making the choice of p and q adaptive with respects to the data at hand works as good as or better than a fixed ℓ 1 -ℓ 2 penalty in various situations. Algorithmically, we first show that, for the general multiple kernel case, a variational formulation of the ℓ 1 -ℓ q mixednorm can be obtained. Such a novel formulation helps us in deriving a simple alternate algorithm for solving the sparse ℓ 1 -ℓ q multi-task problem which provably converges towards the solution of the problem. For the linear case, as such an algorithm may not be efficient, we extend existing works [START_REF] Chen | Accelerated gradient method for multi-task sparse learning problem[END_REF] on accelerated proximal gradient to handle the case of ℓ 1 -ℓ q norm. We essentially provide a novel way for computing the proximal operator of this mixed-norm. At a second stage, we address the case of the non-convex ℓ p -ℓ q (0 < p < 1) regularization term. The difficulty raised by this non-convex problem is tackled via a Majorization-Minimization (MM) approach [START_REF] Hunter | A tutorial on MM algorithms[END_REF]. This leads to an iterative scheme which solves at each iteration, a reweighted ℓ 1 -ℓ q multi-task learning problem.

In the next section, we present the general formulation of the sparse MTL problem as well as a brief review of closely spirit-related works. Algorithmic developments are presented in Section III. Then, some empirical results that illustrate the behavior of our algorithms are given in Section IV while some concluding remarks are drawn in Section V. For a sake of reproducibility, the Matlab code used for this paper is available at http://asi.insa-rouen.fr/enseignants/ ∼ arakotom/ code/SparseMTL.html

II. MULTI-TASK FEATURE/KERNEL SELECTION

FRAMEWORK

This section introduces our sparse MTL framework and discusses related works available in the literature.

A. Framework

Suppose we are given T classification tasks to be learned from T different datasets (x i,1 , y i,1 ) n1 i=1 , • • • , (x i,T , y i,T ) nT i=1 , where any x i,• ∈ X and y i,• ∈ {+1, -1} and n i denotes the ith dataset size. For a given task t, we are looking for a decision function of the form:

f t (x) = M k=1 f t,k (x) + b t ∀t ∈ {1, • • • , T } (1)
where a function f •,k belongs to a Reproducing Kernel Hilbert Space (RKHS) H k of kernel K k , b t is a bias term and M is the number of basis kernels provided. Depending on the input space X , H k can take different forms. For instance, if X = R d , H k can be a subset of R d built from a single or several dimensions. In some other situations, H k can be also an infinite dimension space defined implicitly by its kernel (e.g a Gaussian kernel). The objective of this work is to learn the decision function f t for each task under the constraints that all these functions share a common sparsity profile of their kernel representation. Hence, the pursued hope is to build a learning algorithm able to yield many vanishing functions f t,k for all t.

For achieving this goal, we cast our problem as the following optimization problem:

min f1,••• ,fT C • t,i L(f t (x i,t ), y i,t ) + Ω(f 1 , • • • , f T ) (2)
where L(f t (x), y) is a loss function, Ω a sparsity-inducing penalty term involving all functions f t and C a trade-off parameter that balances both antagonist objectives. Hereafter, we will focus on a Hinge loss function, denoted as H(f (x), y), although our algorithm can be straightforwardly applied to other losses.

B. Joint sparsity-inducing penalty

Since few years now, there has been a large interest around sparse models. While different approaches are possible for generating sparse methods [START_REF] Hu | Building sparse multi-kernel svm classifiers[END_REF], [START_REF] Lee | Constructing sparse kernel machines using attractors[END_REF], sparsity are usually induced by a penalty function [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] or a proper type of Bayesian modeling [START_REF] Tipping | Sparse Bayesian Learning and the Relevance Vector Machine[END_REF], [START_REF] Tzikas | Sparse bayesian modeling with adaptive kernel learning[END_REF].

For a single task empirical minimization problem, sparse models are usually induced by the use of a ℓ 1 -norm regularizer [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF]. For a Multi-Task Learning problem, this approach can be properly generalized by the use of appropriate norm. For instance, Obozinski et al. and Argyriou et al. [START_REF]Convex multi-task feature learning[END_REF], [START_REF] Obozinski | Joint covariate selection and joint subspace selection for multiple classification problems[END_REF] propose a regularizer of the form :

Ω(f 1 , • • • , f T ) = M k=1 T t=1 f t,k 2 H k 1/2
. This latter regularizer is a ℓ 1 block-norm that tends to produce sparse kernel solutions. For single task problem, such a regularizer has been used for sparse kernel selection in multiple kernel learning problem [START_REF] Bach | Multiple kernel learning, conic duality, and the SMO algorithm[END_REF]. For single task linear problem, this regularizer is equivalent to a ℓ 1 -norm penalty.

In order to be more data-adaptive, this regularizer can be generalized as :

Ω p,q (f 1 , • • • , f T ) = M k=1 T t=1 f t,k q H k p/q (3)
where typically 0 ≤ p ≤ 1 and q ≥ 1. For this regularizer, a ℓ q norm is applied to the vector of all task norms in H k and then a ℓ p norm or pseudo-norm is applied to the resulting vector. The ℓ q norm in the regularizer controls the weights of each task for the space H k and how this kernel representation will be shared across tasks. For instance, large value of q (such as q = ∞) means that as soon as f t,k H k is non-zero, another task t ′ can have a non-zero norm for f t ′ ,k without increasing significantly the regularizer Ω p,q . Note that for p = 1 and q = 1, the regularizer can be decoupled and thus the learning problem boils down to be T independent problems. The ℓ p pseudo-norm controls the sparsity of the kernel representation for all tasks. For p < 1, regularizer (3) is expected to produce sparser solutions than for p = 1, hence using such a mixednorm penalty is expected to be more efficient in presence of many irrelevant variables or kernels. Note that this kind of mixed-norm regularizer has already been proposed for single task learning for achieving composite absolute penalization [START_REF] Zhao | The composite absolute penalties family for grouped and hierarchical variable selection[END_REF] or for composite kernel learning [START_REF] Szafranski | Composite kernel learning[END_REF].

However, in the context of multi-task learning, only some particular cases of the mixed-norm Ω p,q have been considered. Obozinski et al. [START_REF] Obozinski | Joint covariate selection and joint subspace selection for multiple classification problems[END_REF] use p = 1 and q = 2 while Liu et al. [START_REF] Liu | Non parametric regression and classification with joint sparsity constraints[END_REF], [START_REF] Liu | Blockwise coordinate descent procedures for the multi-task lasso, with applications to neural semantic basis discovery[END_REF], Quattoni et al. [START_REF] Quattoni | Transfer learning for image classification with sparse prototype representations[END_REF], [START_REF] Quattoni | An efficient projection for ℓ 1,∞ regularization[END_REF] and Chen et al. [START_REF] Chen | Accelerated gradient method for multi-task sparse learning problem[END_REF] have considered the use of p = 1 and q = ∞. For all these works, the authors have focused on convex situations since Ω p,q is known to be convex whenever p, q ≥ 1 and non-convex for p < 1 and q ≥ 1. Recently, several works on learning single sparse models have stressed the need of non-convex penalties for achieving better sparsity profile. For instance, Knight et al. [START_REF] Knight | Asymptotics for lasso-type estimators[END_REF] suggested the use of the so-called Bridge penalty which simply consists in replacing the ℓ 1 norm with a ℓ p pseudonorm with 0 < p < 1. In our multi-task learning framework, this can be naturally generalized by using the regularizer given in Equation (3) with 0 < p < 1. For instance, two very recent works have focused on theoretical properties of the mixed-norm Ω p,1 and Ω 1,q for variable selection in multiple regression problems [START_REF] Huang | A group bridge approach for variable selection[END_REF], [START_REF] Liu | On the estimation and variable selection consistency of the sum of q-norm regularized regression[END_REF].

As we can see, there are a lot of algorithmic works that address the case where p = 1 and q ∈ {2, ∞}. These works usually aim at developing efficient algorithms in the linear decision function. The novelty of our contribution lies in considering a larger class (p ≤ 1 and 1 ≤ q ≤ 2) of mixed-norm penalties while keeping the kernel framework. By choosing p and q in these intervals, we aim a better adaptivity of the penalty to the datasets at hand. However, in this paper, we only focus on algorithms for solving the resulting optimization problems, while the task of efficiently selecting p and q has been left for future works. Furthermore, although we have focused on the use of Hinge loss function, the algorithms we propose in the sequel are generic enough to handle different type of loss functions in the optimization problem as well as heterogeneous loss functions.

As we have stated, we do not consider in this paper cases where 2 < q < ∞. There is a main reason for this. Indeed, we believe that as q becomes greater than 2, the ℓ 1 -ℓ q regularizer rapidly becomes numerically equivalent to a ℓ 1,∞ one. This point can be made clear from the relation

( i |a i | q ) 1/q = |a k | i | ai a k | q 1/q
where k is the index of the largest |a i |. Hence, since there already exists efficient method for ℓ 1,∞ sparse multi-task learning [START_REF] Quattoni | An efficient projection for ℓ 1,∞ regularization[END_REF], we have not addressed this case in this present work. However, we still plan in a forthcoming work, to provide a better analysis of the use of these ℓ 1 -ℓ q penalties so as to understand in which situations they may perform better than the ℓ 1 -ℓ ∞ penalty.

III. ALGORITHMS FOR JOINTLY SPARSE MULTI-TASK SVM

In this section, we propose some algorithms for solving the sparse multi-task SVM problem when using Ω p,q as a regularizer with values p ≤ 1 and 1 ≤ q ≤ 2. At first, we consider the convex case when p = 1 and then we introduce an algorithm which solves the problem for p < 1.

A. A smooth formulation of ℓ 1 -ℓ q regularized problem
The algorithm we propose is based on a variational formulation of the mixed-norm Ω 1,q (•). The following proposition extends the one of Michelli et al. [START_REF] Micchelli | Learning the kernel function via regularization[END_REF] to mixed-norm. Similar propositions have been derived for multiple and composite kernel learning [START_REF] Rakotomamonjy | SimpleMKL[END_REF], [START_REF] Szafranski | Composite kernel learning[END_REF]. Here and in what follows, u/v is defined as u/0 = ∞ if u = 0 and 0/0 = 0.

Proposition 1:

if s > 0 and {a t,k ∈ R : k ∈ [1, • • • , M ], t ∈ [1, • • • , T ]} such that at least one |a t,k | > 0,
then the following minimization problem over elements d t,k admits a unique minimum

min {d t,k }    k,t |a t,k | 2 d t,k : d t,k ≥ 0, k t d 1/s t,k s ≤ 1    =   k t |a t,k | q 1/q   2 (4)
where q = 2 s+1 . Furthermore, at optimality, we have:

d ⋆ t,k = |a t,k | 2s s+1 u |a u,k | 2 s+1 1-s 2 v u |a u,v | 2 s+1 s+1 2 (5)
Proof: (Sketch) The proof proceeds by writing down the Lagrangian of the minimization problem and deriving the optimality condition wrt to d t,k . Then, we get

d 1/s t,k = λ -1/(s+1) |a t,k | 2/(s+1) u d 1/s u,k 1-s 1+s
where λ is the Lagrangian multiplier associated to the mixednorm constraint. From these optimality conditions, we derive

u d 1/s u,k = λ -1 u |a u,k | 2/s+1 s+1 1/2s
. Then since at optimality, the mixed-norm inequality becomes an equality,

we have λ = k t |a t,k | 2/s+1 (s+1)/2 2
. Plugging all these equations into the optimality conditions of d t,k proves the above proposition.

Hence, by setting a t,k = f t,k H k , the above proposition gives a variational formulation of Ω 1,q (•) 2 . It is interesting to note how the mixed-norm on functions f t,k transfers to another mixed-norm on the weights d t,k . We can see that for q = 1, this latter mixed-norm decouples. When q → 2, which correspond to multiple kernel learning for a single task [START_REF] Bach | Multiple kernel learning, conic duality, and the SMO algorithm[END_REF], we have s → 0 and the mixed-norm on the weight becomes a mixed supnorm. This means that at optimality, all the weights {d .,k } associated to non-zero {a •,k } should have similar values. Indeed, suppose that for tasks t and t ′ , d t ′ ,k < d t,k and a t,k , a t ′ ,k are non-zero, then the objective value can be decreased by setting d t ′ ,k = d t,k . For this case, it would have been preferable to consider a single weight d k associated to each RKHS H k . Now let us consider the optimization problem related to our sparse multi-task learning problem for p = 1 and 1 ≤ q ≤ 2 :

min f1,••• ,fT C • t,i H(f t (x i,t ), y i,t ) + Ω 1,q (f 1 , • • • , f T ) 2 (6)
Since the penalty term is convex and the square function is strictly monotonically increasing function on R + , squaring the penalty term in the objective function as above, leads to an equivalent optimization problem without the squaring. Here the equivalence is understood as for any hyperparameter value C, there exists a hyperparameter C ′ related to the optimization problem without the squaring term (as in Equation 2) so that the solutions of both problems are equal (a more formal proof of this claim is detailed in the appendix). Then, owing to the variational formulation of Ω 1,q (f 1 , • • • , f T ) 2 , we can rewrite the optimization problem related to a sparse multi-task SVM as

min f1,••• ,fT ,d C t,i H(f t (x i,t ), y i,t ) + t,k f t,k 2 d t,k s.t k t d 1/s t,k s ≤ 1, d t,k ≥ 0 ∀k, t (7)
with s = 2-q q . We can note that the objective function of this optimization problem is smooth and convex and that the feasible domain is convex if s ≤ 1. After, re-arranging the sums, we have the following equivalent optimization problem:

min d J(d) = t J t (d) s.t k t d 1/s t,k s ≤ 1, d t,k ≥ 0 ∀k, t (8)
with

J t (d) = min ft C i H(f t (x i,t ), y i,t ) + k f t,k 2 d t,k = - min 0≤αt≤C,α T t y=0 1 2 α T t G t (d)α t -α T t 1 (9)
where

[G t (d)] i,j = y i,t y j,t k d t,k K k (x i,t , x j,t
) and {α t } are the vectors of Lagrangian multipliers related to the Hinge loss in problem J t (d). The second equality of equation 9 is due to Lagrangian duality and the strong duality of an SVM problem. We can note from these equations that for a fixed matrix d (matrix with entries d t,k ), each task can be trained independently. This latter formulation shows how our sparse multi-task SVM problem is related to Multiple Kernel Learning (MKL) problem. At first, we remark that Equations (8-9) boil down to be the MKL problem when only one single task is considered [START_REF] Rakotomamonjy | SimpleMKL[END_REF]. When several tasks are in play, the matrix d makes explicit that tasks are linked through their shared sparse kernel representation. Equations [START_REF] Candès | Enhancing sparsity by reweighted ℓ 1 minimization[END_REF][START_REF] Caruana | Multi-task learning[END_REF] suggest the use of similar algorithms than those proposed for solving MKL problem, for instance a reduced gradient algorithm as in SimpleMKL [START_REF] Rakotomamonjy | SimpleMKL[END_REF] or a Semi-Infinite programming approach as proposed by Sonnenburg et al. [START_REF] Sonnenburg | Large scale multiple kernel learning[END_REF]. Instead of adapting these methods to our problem, we present in the sequel a simple approach for solving problem [START_REF] Candès | Enhancing sparsity by reweighted ℓ 1 minimization[END_REF].

B. An alternate optimization algorithm for the ℓ 1 -ℓ q case

We introduce one of our contribution of this work which is a simple iterative algorithm based on block-coordinate descent for solving the ℓ 1 -ℓ q problem. We show that such a coordinate descent approach boils down to an alternate optimization scheme which provably converges to the minimizer of the problem.

At first let us define the objective function of our problem [START_REF] Boyd | Convex Optimization[END_REF] as

R(d, f ) = C t,i H(f t (x i,t ), y i,t ) + t,k f t,k 2 d t,k (10)
where f defines the set of all functions {f t,k } After appropriate initialization of the weight matrix d, our block-coordinate descent algorithm consists in alternatively minimizing : (i) problem [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] with respects to {f } while keeping the matrix d fixed. This step simply consists in solving T single-task SVM problems which, at step v, results in the following decision function for task t :

f (v) t (•) = i,k α (v) i,t y i,t d (v-1) t,k K k (x i,t , •) + b (v) t with α (v) t =      argmin αi,t 1 2 i,j α i,t α j,t G i,j,t -i α i,t s.t i α i,t y i,t = 0, 0 ≤ α i,t ≤ C ∀i where G i,j,t = y i,t y j,t k d (v-1) t,k K k (x i,t , x j,t ).
(ii) problem [START_REF] Boyd | Convex Optimization[END_REF] with respects to d with {f } being fixed.

Because of the relation between the {α

(v) t } and the {f (v) t,k (•) = i α (v) i,t y i,t d (v-1) t,k K k (x i,t , •)}, this problem is equivalent to solve (4) with, at step v a t,k = f (v) t,k H k = d (v-1) t,k i,j α (v) i,t α (v) j,t y i,t y j,t K k (x i,t , x j,t ) = d (v-1) t,k α (v)T t Kk,t α (v) t
where [ Kk,t ] i,j = y i,t y j,t K k (x i,t , x j,t ). According to proposition (1), we have a closed-form solution d

(v)
t,k of this problem given by equation ( 5) which now writes as :

d (v) t,k = f (v) t,k 2s s+1 H k u f (v) u,k 2 s+1 H k 1-s 2 u ′ u f (v) u,u ′ 2 s+1 H k s+1 2 (11)
Owing to the convexity and the smoothness of the objective function, such an algorithm should converge towards the minimizer of problem [START_REF] Candès | Enhancing sparsity by reweighted ℓ 1 minimization[END_REF]. In what follows, we give more details on the descent and convergence properties of this algorithm.

Proposition 2: Suppose that all the Gram matrices K k,t (the matrix of general term K k (x i,t , x j,t )) for all tasks are strictly positive definite, given d (v-1) with ∀t, k, d

(v-1) t,k = 0, at each iteration v > 1 of the alternate scheme, if d (v) = d (v-1) then the cost function strictly decreases R(d (v) , f (v) ) < min f R(d (v-1) , f ) < R(d (v-1) , f (v-1) ) (12)
and we have d

(v) t,k > 0.
Proof: The proof proceeds by considering that the right and the left inequalities respectively derive from the optimality of the α (v) in step (i) and the d (v) in step (ii) of the alternating scheme. The details are given in the appendix.

The above proposition makes clear that as iteration goes, the objective value decreases if the algorithm is properly initialized to a matrix with non-zero elements Furthermore, since the objective function is bounded from below, the iterates of the objective value converge. This proposition also suggests that our algorithm can get stuck into a fixed point. However as made clear in the following proposition, the sequence of {f (v) } and {d (v) } also converge and eventually such a fixed point would be the minimizer of our problem.

Proposition 3: For v ∈ N * , for 1 ≤ q ≤ 2, under the hypothesis that all Gram matrices K k,t are strictly positive definite and d (1) = 0, the sequence {d (v) , f (v) } converges to the minimizer of R(d, f ) subject to the constraints on d :

k t d 1/s t,k s ≤ 1, d t,k ≥ 0 ∀k, t
Proof: For a sake of clarity, the proof of this proposition has been postponed to the appendix. Globally, it follows the same lines of the convergence proof of the alternate optimization algorithm proposed by Argyriou et al. [START_REF]Convex multi-task feature learning[END_REF].

A key point for the convergence of the algorithm is that the weight matrix should be initialized to non-zero value. However, if so, as iteration goes, a given weight d (v) t,k does not strictly vanish. This can be interpreted as a weak point for an algorithm that should provide sparse solutions. However, along the iteration, d

(v)
t,k may rapidly converge towards zero and can rapidly reach a neglectable value. Details on how we have evaluated solution's sparseness are given in the experimental section.

The computational complexity of this algorithm is difficult to evaluate. However, we know that at each iteration, T SVM trainings and the weight matrix d computation are needed.

Each SVM training scales in O(n 3 t,sv ) while computing d is about O(T • M • n 2 t,sv
) with n t,sv being the number of support vectors related to task t. In practice, we take advantage of warm-start techniques when solving the quadratic programming associated to each SVM task, making the algorithm very efficient even compared to gradient descent techniques coupled with warm-starting [START_REF] Decoste | Alpha seeding for support vector machines[END_REF] similar to those used in SimpleMKL. Numerical experiments given in the sequel will support such a claim.

Many previous works on joint-sparse multi-task learning have been carried to in a linear framework thus leading to efficient algorithms. Here, by considering a kernelized framework, our algorithm still relies on a sequence of SVM trainings. This can be considered as very time-consuming. However, according to very recent works on multiple kernel learning [START_REF] Suzuki | Spicymkl[END_REF], [START_REF] Kloft | Efficient and accurate lp-norm multiple kernel learning[END_REF], using such a wrapper approach (which first solves an SVM then update the weights d) is still competitive compared to other algorithms. Hence, although we have not carried out extensive comparisons, we believe that our approach is relatively efficient (and at least is better than gradient descent techniques as proved in the experimental section). Note that in a linear framework i.e each H k is associated to one dimension of R d , the kernel matrix K k is a rank one matrix and our algorithm wastes many computational efforts in computing t d t,k K k (see step (i)). Hence, instead of computing these kernels, we can directly compute this sum through the inner product of the data. We have implemented this simple trick and named this version of our approach, in the experiments, as the linear alternate optimization. We will see that some interesting gain in computational effort can be obtained.

Although we have focused on SVM and the Hinge loss function, our approach can be applied to any convex loss function as long as the problem with fixed d can be easily solved. For instance, with a square-loss function, minimizing problem (10) boils down to be a weighted kernel rigde regression. Furthermore, our approach can handle situations where the loss functions for each task are heterogeneous. Indeed, in such cases, we would like to solve

min f1,••• ,fT ,d C t,i L t (f t (x i,t ), y i,t ) + t,k f t,k 2 d t,k s.t k t d 1/s t,k s ≤ 1, d t,k ≥ 0 ∀k, t (13)
where each loss function L t (•, •) depends on each task and can be either related to a regression or classification problem. This framework has been very recently investigated by Yang et al. and is motivated by applications in genetic association mapping [START_REF] Yang | Heterogeneous multitask learning with joint sparsity constraints[END_REF]. Our algorithm straightforwardly applies to these problems. Indeed, in our alternate optimization algorithm, the loss functions are taken into account only in the first step, where d is kept fixed. Thus each task learning decouples and the heterogeneity of loss functions does not pose difficulty.

C. A proximal method for the linear ℓ 1 -ℓ q case

Recently, several works have proposed efficient algorithms for penalized linear multi-task learning with ℓ 1 -ℓ 2 or ℓ 1ℓ ∞ norms [START_REF] Liu | Multi-task feature learning via efficient ℓ 2,1norm minimization[END_REF], [START_REF] Chen | Accelerated gradient method for multi-task sparse learning problem[END_REF]. These approaches are essentially based on accelerated proximal gradient (APG) method [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF]. We have extended these algorithms to the case of ℓ 1 -ℓ q norms. Since we have exactly followed the same steps of Chen et al. [START_REF] Chen | Accelerated gradient method for multi-task sparse learning problem[END_REF], we only detail how we have numerically computed the proximal operator of the ℓ 1 -ℓ q norm. Let us consider each linear classifier related to a task t as

f t (x) = w T t x+b t and the matrix W = [w 1 , • • • , w T ] ∈ R d×T .
At each iteration of the AGP algorithm, one has to use the socalled proximal operator which maps a matrix V ∈ R d×T to the unique minimizer of min

X∈R d×T 1 2 X -V 2 F + λ d k=1 X k,• q
This problem can be decomposed in d independent problems which consist of

min x∈R T 1 2 x -v 2 + λ x q (14)
for each dimension of the problem. For q = {1, 2, ∞}, this problem has a closed-form solution which makes the global APG algorithm very efficient. Unfortunately, for 1 < q < 2, one has to numerically solve this problem. However, considering a q ′ such that 1/q + 1/q ′ = 1, it can still be shown that if v q ′ ≤ λ then the solution is 0. In the other case, we have considered subgradient descent method and iterative reweighted least-square (IRLS) [START_REF] Saab | Stable sparse approximations via nonconvex optimization[END_REF]. Since we found out that the latter is more efficient due to the simple structure of the problem, our numerical implementation uses such an approach. It is simple to show by writing the optimality conditions of problem 14 that the IRLS algorithm consists at each iteration (z) in updating x according to the formula x (z) = [P (z) ] -1 v with

P (z) = diag 1 + λ x (z-1) q-1 q |x (z-1) | q-2
which is just a componentwise vector multiplication.

An important remark is that the accelerated proximal algorithm considered here present a fast convergence rate when the loss function is continuously differentiable with Lipschitz gradient (for instance logistic or square loss). In our case, the Hinge loss is non-smooth therefore, we cannot guarantee any convergence rate. However as Chen et al. [START_REF] Chen | Accelerated gradient method for multi-task sparse learning problem[END_REF] also noticed, considering the subgradient of the Hinge loss instead of the gradient leads to very good computational efficiency. As we will show in the experimental section, this AGP algorithm is indeed very fast for q = 2. For 1 < q < 2, although we do not have a closed-form solution of problem [START_REF] Dunson | The matrix stick-breaking process : flexible bayes meta analysis[END_REF], the numerical scheme we propose is still very efficient. Regarding sparsity, unlike the alternate optimization algorithm, the solution provided by this proximal approach is exactly sparse up to numerical precision.

D. The non-convex ℓ p -ℓ q case

Now that we are able to solve the sparse MTL problem using a ℓ 1 -ℓ q mixed-norms, we propose an algorithm which solves the non-convex case where ℓ p -ℓ q (with 0 < p < 1 and 1 ≤ q ≤ 2 ). For this novel situation, let us rewrite the regularization term as

Ω p,q = M k=1 g( f •,k q ) with f •,k q = t f t,k q H k 1/q (15)
for the linear case, f •,k q = ( t |W k,t | q ) 1/q , and where the upper level penalty function is g(u) = u p , u > 0 with p < 1. Clearly, this function is non-convex. To address this issue, we investigate the use of majorization-minimization (MM) algorithms [START_REF] Hunter | A tutorial on MM algorithms[END_REF] which form a general framework for optimizing non-convex objective functions. For our multitask problem, we propose a majorization that enables us to take advantage of the ℓ 1 -ℓ q MTL solver that we proposed above. Indeed, since g(u) is concave in its positive orthant, we consider the following linear majorization of g(•) at a given point u 0 :

∀u > 0, g(u) ≤ u p 0 + pu p-1 0 (u -u 0 )
Note that this linear majorization can also be obtained from the Fenchel inequality related to the Legendre-Fenchel transformation of the differentiable function g(u) [START_REF] Rockafellar | Convex Analysis[END_REF]. We could have proposed a tighter majorization of g(•) by using for instance a local quadratic approximation. However, the main advantage of a linear majorization is that it leads to a simple algorithm. Indeed, at iteration z, applying this linear majorization of g( f •,k q ), around a f (z)

•,k q yields to a majorizationminimization algorithm for ℓ p -ℓ q multi-task learning which consists at a given (z + 1)th iteration, in solving :

min f1,••• ,fT C t,i H(f t (x i,t ), y i,t ) + k p f •,k q f (z) •,k 1-p q
This latter equation shows that, in order to solve the nonconvex ℓ p -ℓ q problem using a MM approach, one needs to iteratively solve a weighted ℓ 1 -ℓ q multi-task problem :

min f1,••• ,fT C t,i H(f t (x i,t ), y i,t ) + M k=1 β k f •,k q (16)
where β k are some coefficients that depend on the current functions f t,k . They are defined at the z-th iteration as:

β k = p f (z) •,k 1-p , ∀ k = 1, • • • , M (17)
This definition of the β k implicitly requires the strict positivity of f •,k . To ensure this condition, a small term ǫ is added to f •,k in [START_REF] Evgeniou | Regularized multi-task learning[END_REF]. Hence, we use

β k = p ǫ+ f (z) •,k
1-p . This trick suggested as well by [START_REF] Candès | Enhancing sparsity by reweighted ℓ 1 minimization[END_REF] avoids numerical instabilities and overall prevents from having an infinite regularization term for f •,k . In some other context, this ǫ term can play a smoothing role if chosen adaptively [START_REF] Daubechies | Iteratively reweighted least squares minimization for sparse recovery[END_REF]. However, in this work, we have kept it fixed at ǫ = 0.001. Now, the equivalent optimization problem with smooth regularization term is :

min f1,••• ,fT ,d C t,i H(f t (x i,t ), y i,t ) + t,k β 2 k f t,k 2 d t,k s.t k t d 1/s t,k s ≤ 1, d t,k ≥ 0 ∀k, t (18)
where s = 2-q q . Note that the optimality conditions of this problem with respects to f t,k is simply given by the expression

f t,k (•) = d t,k β 2 k i α i,t y i,t K k (x i,t , •)
. Consequently, at each MM iteration, we have to solve a weighted sparse MTL problem, where the weights are applied to the basis kernels. Hence, problem (18) can be solved using the ℓ 1 -ℓ q algorithm just by replacing the kernel K k (x, x ′ ) with 1

β 2 k K k (x, x ′ ).
Details of the ℓ p -ℓ q problem solver are given in Algorithm 1. About its complexity, we can state that since the ℓ p -ℓ q Algorithm 1 ℓ p -ℓ q sparse MTL solver.

β k = 1 for k = 1, • • • , M Compute K k,t kernel matrices for all tasks repeat K β k,t ← K k,t β 2 k for all k Solve ℓ 1 -ℓ q MTL problem with kernels K β k,t
Update β k using Equation ( 17) until convergence of the β's algorithm is based on n iter iterations of the ℓ 1 -ℓ q algorithm (after appropriate rescaling of the kernels), its complexity can be approximated as n iter times the ℓ 1 -ℓ q algorithm complexity. However, here again, we can speed-up the convergence of ℓ p -ℓ q , algorithm by warm-starting the ℓ 1 -ℓ q with results from previous iteration. Empirical experiments have shown that n iter are typically lower than 10.

The local convergence of Algorithm 1 is guaranteed. Indeed, the MM programming approach proceeds by surrogating the concave part of the objective function with its affine majorization at each iteration. Therefore, the minimized function decreases until convergence to at least a local minimum [START_REF] Hunter | A tutorial on MM algorithms[END_REF].

IV. NUMERICAL EXPERIMENTS

In this section, we present some numerical experiments that demonstrate the utility of using a ℓ p -ℓ q penalty instead of a ℓ 1 -ℓ 2 one. They have been carried out on a toy dataset and on real datasets concerning BCI electro-encephalogram signals classification and protein subcellular localization.

Before delving into the experimental details, we provide some remarks on how we have evaluated the sparsity of our algorithm's output. Let us denote the vector s of components s k = t d t,k or s k = t |W k,t | depending on the used algorithm. We define the set S = {k ∈ 1, • • • , M : s k > γ} where γ is a threshold that allows us to neglect non-zero components due to numerical errors (diagonal loading of kernels to as to make them positive definite has been set to 1e -6 ). For the toy problem, we have set γ = 1e -5 which we believe is small enough so as to provide rather pessimistic estimation of the vector sparseness. We have also considered an heuristic for adaptively setting γ for our alternate optimization algorithm which provides dense although small outputs. In such a case, we have set γ = 0.01 • max k (s k ). The rationale behind this heuristic is that kernels or variables that have weights significantly smaller than the largest one do not influence the decision function. As a numerical criterion for sparsity evaluation, for the toy problem, since we know the true relevant variables S ⋆ , we have considered the Fmeasure between S and S ⋆ . For the other problems, we have evaluated the cardinality of S using the adaptive threshold. All performances reported are evaluated based on kernels and variables in the set S.

A. Toy dataset

Our aim throughout this first experiment is first to analyze the convergence of our alternate optimization algorithm and then to compare an ℓ 1 -ℓ 2 and an ℓ p -ℓ 2 (with p < 1) penalties in term of classification performance.

The toy problem is the same as the one used by Obozinski et al. [START_REF] Obozinski | Joint covariate selection and joint subspace selection for multiple classification problems[END_REF]. Each task is a binary classification problem in R d . Among these d variables, only r of them define a subspace of R d in which classes can be discriminated. For these r relevant variables, the two classes follow a Gaussian pdf with mean respectively µ and -µ and covariance matrices randomly drawn from a Wishart distribution. µ has been randomly drawn from {-1, +1} r . The other d-r non-relevant variables follow an i.i.d Gaussian probability distribution with zero mean and unit variance for both classes. In this experiment, we are interested in feature selection, thus, for any k, H k is the finite dimension subspace built from the kth component of R d . We have respectively sampled n, n v and n t number of examples for training, validation and testing. For some experiments, n is varying, but we have always set n v = n and n t = 5000. Before learning, the training set has been normalized to zero mean and unit variance and the validation and test sets have been rescaled accordingly.

1) Comparing convergence for ℓ 1 -ℓ 2 penalty: To evaluate the quality of the solution provided by our alternate optimization algorithm when considering a ℓ 1 -ℓ 2 penalty, we have compared it to the solution obtained by a reduced gradient algorithm similar to the one used for SimpleMKL [START_REF] Rakotomamonjy | SimpleMKL[END_REF]. Both algorithms are wrapper algorithms which in a inner loop solve several SVM problems with fixed kernel and in a outer loop optimize the weights d. The main difference between the two approaches is the way the matrix d is updated. Note that in our comparison, both methods take advantage of warm-start techniques for successive SVM retrainings. The stopping criterion we have used are the following. For our alternate optimization methods, we stop when max(|d (v+1)d (v) |) < 0.001 (where the max is considered componentwisely). For the reduced gradient approach, since we can check the KKT conditions without additional computational cost [START_REF] Rakotomamonjy | SimpleMKL[END_REF], we also imposed that before stopping, the KKT conditions should be satisfied up to a tolerance of 0.1 for each d t,k . Here, the comparison has been carried out for a hyperparameter C = 100 and for T = 4 tasks.

Figure 1 presents the results of this comparison. On the left, we have plotted an example of how the objective value decreases with respects to the CPU time. All the computations have been carried out on a single core of a Bi-Xeon machine with 24 Gb of memory. Source codes are in Matlab. We remark that for a given computational time, using the update equations of d given in Equation ( 5) yields to a faster convergence. Such a finding is corroborated by quantitative evaluation performances given in the right of Figure 1. We show in that table, that for very similar objective values and matrix d, our alternate optimization algorithm converges faster than the reduced gradient approach. The gained factor is about 15.

Table I compares the computational efficiency of several algorithms for solving a linear toy problem. We have compared the kernelized and linear versions of our alternate optimization algorithm as well as the proximal gradient algorithm which is stopped when the variation of its objective value is smaller than 0.001. Here, we have chosen algorithm hyperparameters so as to perfectly recover the sparsity pattern.

Firstly, we can see that in the linear case, the simple trick which consists in directly computing the sum k d t,k K k from the examples, yields in a substantial saving of computational efforts for our algorithm (regardless of q). When q = 2, the proximal algorithm is very efficient with a gain factor of about 10. For q = 4 3 , the method we proposed for numerically computing the proximal operator still yield to efficient algorithm with gain of about 6.

2) Comparing performance: In this experiment, we aim at showing that by using a ℓ p -ℓ 2 penalty which provides a more aggressive sparsity pattern, we are able to reduce test error compared to a ℓ 1 -ℓ 2 penalty. We also provide empirical evidence that for this toy problem, the variables that are recovered using the ℓ p -ℓ 2 penalty are more relevant than those recovered by the ℓ 1 -ℓ 2 one. As a baseline comparison, we have also considered sparse separated SVM (each single SVM is trained according to its task data) and a sparse pooled SVM (a single SVM is trained according to all task data). Since the problem is linear, we have used the accelerated gradient algorithm but we have also checked how the linear version of our alternate optimization approach behaves.

The two penalties have been compared through different experimental situations where we have varied some parameters of the toy problem e. Results are summarized in Figure 2. The figure shows that regardless the experimental situations considered, a ℓ p -ℓ 2 penalty leads to better performances than the ℓ 1 -ℓ 2 one and the ℓ 1 separated SVM (results of the pooled models have not been reported since they are always worse than 0.20). The statistical significance of this claim has been evaluated using a Wilcoxon signed rank test. The test shows that the difference in performance is significant at a level of 0.05 except in few situations (e.g first marker of the second and fourth plots from left to right). One can also see that the alternate optimization and the proximal algorithm lead to statistically equivalent performances when using ℓ p -ℓ 2 penalty except for few cases when the number of training example is small. We have checked that this is due to a model selection problem : the proximal algorithm seems to be more sensitive to the choice of λ. Figure 3 gives a rationale on why the ℓ p -ℓ 2 penalty performs better. We have evaluated the F-measure of S compared to the true relevant variables. The ℓ p -ℓ 2 penalty does a better job in recovering relevant variables (even when the ℓ 1 -ℓ q algorithm is our non-exactly sparse alternate optimization algorithm). The use of an adaptive threshold also lead to good estimation of relevant variables. Missing models in the plots have F-measures always lower than 0.3. This means for instance that an ℓ 1 -ℓ 2 penalty trained with an alternate optimization algorithm have too many weights so that t d t,k > 1e -5. As the number r of true relevant variable increases, the gap of performance between ℓ 1 -ℓ 2 and ℓ p -ℓ 2 penalties tends to reduce. This can be easily justified since in this case, the ℓ p -ℓ 2 penalty becomes too aggressive and tends to discard relevant variables. We can thus conclude that the use of an ℓ p -ℓ 2 penalty is more adapted to situations where the number of relevant variables is small compared to the problem dimensionality. This point is also illustrated in Figure 4. We can note there that the model selection procedure tends to choose larger value of p as the number of relevant variables increases. This clearly shows that if no prior knowledge on the sparsity level is available, adaptive data-driven penalty norms Test Error (%) r=4, d=100, n=100 5 [START_REF] Boyd | Convex Optimization[END_REF] 2

1 1 1 L 1 -L 2 Prox L p -L 2 Prox L p -L 2 Altern L 1 SepSVM
Fig. 2. Performance (test error ) comparisons between ℓ 1ℓ 2 ( red, dash-dotted), ℓpℓ 2 (blue, solid) multi-task models trained with proximal algorithms, ℓpℓ 2 trained with alternate optimization (black, dotted) and ℓ 1 separated models (green, dashed) for different experimental situations. For each experimental situation, we have kept fixed all except one of parameters : (from left to right) number of training examples n, problem dimension d, number of relevant variables r, number of tasks T . The number given next each marker represents the number of times (out of 20) the ℓ 1ℓ 2 penalty provides a better performance than the ℓpℓ 2 penalty both trained with proximal algorithms. Fig. 4. Illustration of how when using an ℓpℓ 2 penalty, the learned decision functions adapt themselves to the data at hand (d = 100, T = 4 and n = 100). The two plots show the number of times a given p has been selected by validation. On the left, the number of relevant variables r is equal to 4 while on the right plot, we have r = 20. We note that as the number of relevant variables increases, the model selection procedure tends to choose a larger p. are valuable.

B. BCI P300 single trial problem

We also illustrate the usefulness of sparse Multi-Task learning on a Brain-Computer Interface problem. Indeed, sparse MTL can be very relevant to BCI because of the need for channel/variable selection and because of the data variability with respects to different subjects. Our objective here is to show that sharing information between subjects through sparse multitask learning can lead to improvement in performance while reducing the number of variables involved in the recognition task. The dataset we consider is the BCI P300 Speller dataset used by Hoffmann et al. [START_REF] Hoffmann | An efficient p300-based brain-computer interface for disabled subjects[END_REF]. For this BCI paradigm, a subject is presented a six-symbol matrix where symbols are flashed in random order. A large P300 evoked potential can be recorded in the electro-encephalogram (EEG) signals recorded from the subject's scalp in response to the intensification of the desired symbol. Each trial corresponds to the EEG signals related to the response of a given flash. Hence, the classification task is to recognize whether this trial contains or not a P300 evoked potential. The datasets involve 9 subjects including disabled ones. All preprocessing steps we used are those described by Hoffmann et al. The steps include : referencing, band-pass filtering, downsampling, single trial extraction, windsorizing, scaling and feature vector construction. In our experiments, we have restricted ourselves to a 8 channel configuration (Fz, Cz, Pz, Oz, P7, P3, P4, P8) which leads after downsampling all subjects all-together using our multi-task approach (one task = one subject). Three types of penalty for the multi-task learning are considered : an ℓ 1 -ℓ 2 , an ℓ p -ℓ 2 and a ℓ 1 -ℓ q penalty. As a comparison, we have also learned a sparse and a classical SVM trained on a single subject, and a sparse and a classical SVM trained on all subject data. Sparse SVM has been obtained using a ℓ 1 multiple kernel learning approach where each feature is related to a kernel [START_REF] Rakotomamonjy | SimpleMKL[END_REF]. For selecting the hyperparameter of all algorithms, we have considered a validation approach. For all subjects, we have randomly split the available examples in 3 sets : n examples for training and validation and the rest for testing. For the experiment, we have set the training set size to n = 300 and n = 400. C and p have been selected from the same sets as the previous experiments while q ∈ { 4 3 , 5 3 , 20 11 }. Note that using a small part of the examples for training is motivated by the use of ensemble of SVM (that we do not consider here) [START_REF] Rakotomamonjy | BCI competition III: Dataset II -ensemble of SVMs for BCI P300 speller[END_REF] at a later stage of the EEG classification procedure. The performance is measured by AUC, due to the post-processing that is done throughout repetitions in the P300 : as the final decision regarding letters is taken after several trials, the correct row and column should receive high scores to correctly identify the letter.

Results averaged over 10 trials are presented in Table II. The baseline performance is the one provided by a classical SVM trained on a single subject (SepSVM). When comparing performance of a given approach to that baseline, a Wilcoxon sign-rank test has been evaluated and the p-value being reported. We remark that training with all examples lead to significantly worse performances compared to the baseline. However, when learning through a multi-task approach, we achieve a slight but significant increase of performance. Interestingly, the three multitask approaches yield a significant dimensionality reduction while slightly improving performances. When comparing performances of the three different multitask penalties, we see that AUC scores are equivalent but the ℓ p -ℓ 2 penalty need far fewer variables.

C. Protein subcellular localization

This last real-world experiment further highlights the utility of our approach in a kernel selection context. Indeed, we consider here two datasets for bacterial protein localization : the PSORT+ dataset contains four classes and 541 examples and the other, called PSORT-, has five classes with 1444 examples. For each datasets, 69 kernels have been computed and they are publicly available on http://www.fml.tuebingen. mpg.de/raetsch/suppl/protsubloc. This website also provides some information about the post-processing for performance evaluations. This classification problem is actually a multiclass problem that we address through pairwise binary classification. In order to reduce the number of kernels to compute, we are interested in joint kernel selection for all pairwise problems. Hence, we have considered a one-against-all framework where each one-against-all problem is a task. Note that we could have also considered that each task is related to a one-againstone pairwise problem, but in order to be compliant with the experimental setting of Zien and Ong and the way they evaluate performances, we have considered the one-against-all framework.

In our experiments, we have compared sparse MTL with ℓ 1 -ℓ 2 and sparse MTL with ℓ p -ℓ 2 and ℓ 1 -ℓ q . Due to the multiclass nature of the problem, comparisons with pooled and independent models are not possible. Data permutations as well as the 80% -20% splitting into training and testing sets are also provided by Zien and Ong [START_REF] Zien | Multiclass Multiple Kernel Learning[END_REF]. Hyperparameters C, p anq q have been selected through a validation method by randomly splitting the training set then training and validating on the resulting splits. C has been selected from 10 values logarithmically sampled from the interval [0.01, 100] while p and q are respectively chosen from {0.5, 0.75, 0.9} and { 4 3 , 5 3 , 20 11 } Averaged over 10 trials results are given in Figure 5. We have also given the performance achieved by the multiclass MKL algorithm of Zien and Ong [START_REF] Zien | Multiclass Multiple Kernel Learning[END_REF]. This MKL algorithm learns a linear combination of kernels that is jointly optimal for all winner-takes-all decision functions. Hence, their method is very similar to our sparse MTL learning with a ℓ 1 -ℓ 2 penalty. Results show that our algorithms and the different penalties yield to similar accuracy performances (according to a Wilcoxon sign-rank test) and they are competitive with the multiclass MKL of Zien and Ong. However, once again using an adaptive value of p or q compared to a pre-defined choice of p = 1 and q = 2 leads to significantly fewer selected kernels (up to a level of 0.05). We can also point out that the validation approach tends to select a value of p and q respectively of 0.9 and 4 3 . By using a value of p slightly smaller than 1, we thus achieve a substantial reduction of the number of selected kernels (compared to ℓ 1 -ℓ 2 ). Right plot of Figure 5 gives an example of the resulting weights d t,k for different penalties for the PSORT+ problem. We remark that some kernels (e.g the third, seventh and eighth) have been selected by the ℓ 1 -ℓ 2 and ℓ 1 -ℓ q penalties but have been discarded by the ℓ p -ℓ 2 one.

D. Computational efficiency on the real-world problems

In order to have an idea on the computational efficiency of our algorithms for ℓ 1 -ℓ q multi-task problems, we have reported in Table III, the time they need for converging. we also provide results for gradient descent approach (when q = 2) and proximal gradient descent for linear problems such as the BCI problem. Stopping criterion are the same as those used for the toy dataset problem. Note that while our alternate optimization and the gradient descent algorithms solve the same problem, the proximal algorithm solves an equivalent one. However, since it is hard to find the closedform relation between the hyperparameters producing the same solution, for a relatively fair comparison, we have chosen these hyperparameters so as to have a similar level of sparsity. The results we obtain are on the same lines of those obtained for the toy problem. Regardless of the situation, gradient descent is the less efficient approach. When compared to the kernel version of the alternate optimization algorithm, the loss in computational effort is from 2 to 4. When comparing linear methods, proximal descent is the most efficient method with a gain in computation of the order of 3 in the worst case.

V. CONCLUSION

In this paper, we investigated the use of mixed-norms for multi-task SVM with joint sparsity constraint. We went beyond convexity and proposed a large class of mixed-norm penalty based on ℓ p -ℓ q norm, (with p ≤ 1 and 1 ≤ q ≤ 2). For solving the resulting optimization problem, we first derive a general algorithm which addresses the convex case p = 1 and the use of multiple kernels. For the linear case, a more efficient proximal algorithm have been investigated. For the case p < 1, we fitted the optimization problem into the Majorization-Minimization framework, and proposed an iterative reweighted version of the ℓ 1 -ℓ q algorithm. Experimental results on toy data set brought evidence that ℓ p -ℓ q penalties lead to enhanced performance and better sparsity pattern compared to a ℓ 1 -ℓ 2 penalty especially in situations where a large number of variables are in play. Then, results on real-world datasets from various domains have shown the potential ( in terms of accuracy and variable selection) of our approach on applications where variable or kernel selections are of primary importance.

Now we plan to extend our efforts in the following directions. While this paper is essentially a proof of concept that adapting the penalty to the problem at hand is an interesting approach, up to now we have dealt with this adaptivity only through validation methods and grid search on p and q. Now, for addressing efficiently such an adaptivity, we will focus on algorithmic methods that would allow us to jointly select p and q. Notably, we project to investigate regularization path and continuation methods. Furthermore, we will also consider faster algorithms that can handle large-scale problems. Then, future works will also aim at theoretically analyzing the consistency of our ℓ p -ℓ q approach for variable selection.

VI. APPENDIX

A. Equivalence between problems ( 2) and [START_REF] Bickel | Multi-task learning for hiv therapy screening[END_REF] The equivalence between these two problems comes from two properties : i) the equivalence between constrained and regularized convex optimization problem and ii) the equivalence of optimization problems when objective functions or constraints are transformed through the composition of a monotonically increasing function.

Here we give the proof for a simple case without loss of generality. Let us consider the following optimization problems with F (•) and G(•) being two strictly convex functions of R d , (R) : min

x∈R d F (x) + λG(x) and (C) : min x∈R d ,G(x)≤τ F (x)
with λ and τ some parameters. These two problems are equivalent in the sense that for any λ, there exists a τ such that the minimizers of (R) and (C) are the same [START_REF] Weiss | Algorithmes rapides d'optimisation convexe. applications à la reconstruction d'images et à la détection de changements[END_REF]. Now, according to the same notion of equivalence, problem (C) is also equivalent to

(C 2 ) : min x∈R d ,G(x) 2 ≤τ 2 F (x)
owing to the monotonically increasing transformation of the constraints [START_REF] Boyd | Convex Optimization[END_REF]. Since (C 2 ) is equivalent to

(R 2 ) : min x∈R d F (x) + λ 2 G(x) 2
where λ 2 is another parameter. We thus have equivalence between (R) and (R 2 ). (left) Average F1 score and number of selected kernels using our algorithms with different penalties on protein subcellular localization problems. Scores of the multiclass MKL of Zien and Ong. [START_REF] Zien | Multiclass Multiple Kernel Learning[END_REF] have also been reported. (right) Example of kernel weights resulting from the different penalties for the PSORT+ problem. For a sake of clarity, we have restricted the plot to the 20 first kernels. We note that different penalties lead to different sets of selected variables and for some variables that have been selected by all three models, the weighting can largely differ. The number of kernels selected by Zien and Ong's method has not been explicitly reported and we have extrapolated them from one of their figure in [START_REF] Ong | An automated combination of kernels for predicting protein subcellular localization[END_REF].

Data

B. Descent property of the ℓ 1 -ℓ q algorithm

For the right strict inequality, positive definiteness of G t implies strict convexity and the solution's uniqueness of the minimization problem in f t related to all tasks. Besides, f

(v) t = f (v-1) t
would imply according to Equation (11) that d (v) = d (v-1) . Hence, since by hypothesis d (v) = d (v-1) , we have f

(v) t = f (v-1) t
. These points lead to the strict inequality :

min f R(d (v-1) , f ) < R(d (v-1) , f (v-1) )
Before showing the left strict inequality, the properties relating d (v) and d (v-1) are proved. We can first note that if d > 0, the left strict inequality of equation [START_REF] Daubechies | Iteratively reweighted least squares minimization for sparse recovery[END_REF] naturally comes from the strict convexity and the solution's uniqueness of problem (4).

C. Convergence of the ℓ 1 -ℓ q algorithm

Here we present the proof of convergence of our algorithm which follows the lines of the one of Argyriou et al. [START_REF]Convex multi-task feature learning[END_REF].

Let us define

S(f ) := R(d(f ), f ) = C t,i H(ft(x i,t ), y i,t ) +   t k f t,k q H k 1/q   2
The second equality in the definition of S(f ) naturally stems from Proposition 1 since d (1) = 0. For q so that 1 ≤ q ≤ 2, the mixed-norm regularizer term t k f t,k q H k 1/q is convex as a sum of convex functions. The composition with a strictly increasing and strictly convex function (the square term) on R + makes the overall regularizer strictly convex. Thus, even though the loss function H(•, •) is just convex, S(f ) is still strictly convex and admits an unique minimizer. Now let us introduce

g(f ) := min u {R(d(f ), u)} ( 19
)
we show in the sequel that the function g(f ) is continuous. This comes from the fact that the function :

G(d) := min u R(d, u)
is continuous and differentiable. Indeed, for a given d, the optimization problem defining G(d) is just T independent SVM problems; each task being related to each SVM problem with a kernel k d t,k K t,k . Results from multiple kernel learning have shown that each SVM objective value, for a task t, is a continuous and differentiable function [START_REF] Rakotomamonjy | SimpleMKL[END_REF] with respects to {d t,k }. From this point, we can conclude that G(d) is also continuous and differentiable. Thus g(f ) is continuous as a composition of continuous functions. Now let us show that the sequence {S(f (v) ) : v ∈ N} converges. We can observe that since S(f ) = R(d(f ), f ) and d(f ) minimizes R(•, f ), we have the following inequalities : S(f (v+1) ) ≤ g(f (v) ) ≤ S(f (v) ).

Hence, the sequence {S(f (v) ) : v ∈ N} is not increasing and since the loss function H is bounded from below, it is bounded. Thus as v goes to ∞, the sequence S(f (v) ) converges to a value S ⋆ . From the continuity and boundedness of S(f (v) ), we can also deduce that the mixed-norm regularizer and the sequence {f (v) } are bounded where boundedness of {f (v) } is understood according to some norm (e.g the norm induced by the inner product f , f = t,k f t,k , f t,k H k ). As a consequence, there exists a subsequence {f (vi) : i ∈ N} that converges towards f ⋆ . Now, we show that f ⋆ is a minimizer of R(•, •). Consider any convergent subsequence {f (vi) : i ∈ N} of {f (v) : v ∈ N}. Since S(f (vi+1) ) ≤ g(f (vi) ) ≤ S(f (vi) ), g(f (vi) ) converges towards S ⋆ . By the continuity of functions S(f ) and g(f ), we thus have g(f ⋆ ) = S(f ⋆ ). This implies that f ⋆ is a minimizer of R(d(f ⋆ ), •) because R(d(f ⋆ ), f ⋆ ) = S(f ⋆ ). Furthermore, d(f ⋆ ) is the minimizer of R(•, f ⋆ ) subject to constraints on d. Thus, since the objective function R(•, •) is smooth and strictly convex, the pair (d(f ⋆ ), f ⋆ ) is a stationary point of R(•, •) and thus its unique minimizer.

At this point, we have shown that any convergent subsequent of {f (v) : v ∈ N} converges to the minimizer of R(•, •). Then since S(f ) is continuous and {f (v) : v ∈ N} is bounded, it follows that the whole sequence converges towards the minimizer of R(•, •).

Fig. 1 .

 1 Fig.1. Comparing our block-coordinate descent algorithm in its kernel version with a gradient descent approach similar to the one used for multiple kernel learning in SimpleMKL. The left panel shows an example of how the objective value varies with respects to the CPU time. The right table summarizes the time needed for the gradient descent algorithm and for our method before convergence. Relative difference of objective value and the maximal difference between the weights returned by the two algorithms are also reported. All the criteria are averaged over 10 different training sets and with a fixed uniform and random non-zero initializations. The experimental set-up is d = 100, r = 4, T = 4 and n = 100 with C = 100.

  g the number of tasks, the number of training examples, the number of relevant variables. Model selection have been included into the comparison. Hence, hyperparameters have been tuned by means of a validation set and a validation error. For both ℓ 1 -ℓ 2 and ℓ p -ℓ 2 sparse MTL, hyperparameters λ (proximal algorithm) and C (alternate optimization) have been respectively selected among 10 different values logarithmically sampled from the interval [3, • • • , 60] and [0.01, • • • , 100]. For the ℓ p -ℓ 2 penalty, sparsity parameter p has also been selected among the value [0.2, 0.5, 0.75, 0.9]. For each experimental situations, trials have been replicated 20 times.

Fig. 3 .

 3 Fig. 3. Evaluation of the recovered sparsity pattern through the F-measure of retrieved variables. (left) F-measure wrt number of training examples. (right) F-measure wrt the number of relevant variables. Prox, Altern and Altern Ad respectively stand for models trained with proximal and alternate optimization and alternate optimization with adaptive thresholding for sparsity evaluation. When an algorithm exactly recovers the set of true relevant variables, F-measure should be equal to 1.

  Fig.5. (left) Average F1 score and number of selected kernels using our algorithms with different penalties on protein subcellular localization problems. Scores of the multiclass MKL of Zien and Ong.[START_REF] Zien | Multiclass Multiple Kernel Learning[END_REF] have also been reported. (right) Example of kernel weights resulting from the different penalties for the PSORT+ problem. For a sake of clarity, we have restricted the plot to the 20 first kernels. We note that different penalties lead to different sets of selected variables and for some variables that have been selected by all three models, the weighting can largely differ. The number of kernels selected by Zien and Ong's method has not been explicitly reported and we have extrapolated them from one of their figure in[START_REF] Ong | An automated combination of kernels for predicting protein subcellular localization[END_REF].

  = 0. But if d

> 0

 0 then strict positivity of d (v) t,k stems from the positive definiteness of matrices K k,t . Indeed, since we have f to Equation (11) yields to d (v) t,k > 0. Now, since d

TABLE I COMPARING

 I THE COMPUTATIONAL EFFICIENCY (IN SECONDS) OF DIFFERENT LINEAR APPROACHES FOR ℓ 1ℓq PENALTY. THE EXPERIMENTAL SET-UP IS d = 100, r = 4, T = 4 AND n = 100.

		ℓ 1,q penalty
	Methods	q = 2	q = 4 3
	Kernel Altern. Opt 1.02 ± 0.20	1.08 ± 0.20
	Linear Altern. Opt	0.59 ± 0.06	0.64 ± 0.08
	Proximal Descent	0.06 ± 0.01	0.10 ± 0.20

TABLE II AVERAGE

 II AUC PERFORMANCES OF 7 DIFFERENT ALGORITHMS ON THE BCI DATASET. THE NUMBER OF VARIABLES THAT HAVE BEEN KEPT IN THE DECISION FUNCTION IS ALSO GIVEN. SEPSVM AND SEP ℓ 1 SVM RESPECTIVELY DENOTE A SVM AND A SPARSE SVM CLASSIFIER TRAINED ON ISOLATED DATASETS FOR EACH SUBJECT. FULLSVM AND FULL ℓ 1 SVM ARE THE CLASSIFIERS TRAINED ON ALL EXAMPLES. TOP) n = 300. BOTTOM) n = 400. The number of single trials available for each subject is about 3300. Note that the datasets and the preprocessing algorithms are available on the EPFL BCI group website (http://bci.epfl.ch/p300). Instead of training a classifier separately on each subject as in Hoffmann et al., we have trained linear classifiers, using our alternate optimization algorithm, for

		MTL 1,2	MTL p,2	MTL 1,q	SepSVM	Sep ℓ 1 SVM	Full SVM	Full ℓ 1 SVM
	AUC	76.5 ± 0.6	76.1 ± 0.5	76.5 ± 0.6	75.6 ± 0.8	73.4 ± 1.3	67.1 ± 0.6	67.0 ± 0.6
	# Var	191 ± 26	134 ± 33	201 ± 23	256	118 ± 30	256	238 ± 7
	p-val	0.00019	0.00897	0.00014	-	0.00006	0.00006	0.00006
		MTL 1,2	MTL p,2	MTL 1,q	SepSVM	Sep ℓ 1 SVM	FullSVM	Full ℓ 1 SVM
	AUC	78.2 ± 0.6 77.8 ± 0.7	78.3 ± 0.6	77.4 ± 0.9	75.1 ± 1.3	67.9 ± 0.6	67.9 ± 0.6
	# Var	205 ± 18	150 ± 35	209 ± 16	256	149 ± 32	256	249 ± 2
	p-val	0.00009	0.007	0.00009	-	0.00009	0.00009	0.00009
	to a feature vector of size 256.

TABLE III EXAMPLES

 III OF AVERAGE TIME NEEDED FOR OUR ALTERNATE OPTIMIZATION ALGORITHM, THE GRADIENT DESCENT APPROACH AND PROXIMAL DESCENT FOR PRODUCING A SOLUTION OF A ℓ 1ℓq MTL PROBLEM. NOTE THAT FOR PSORT PROBLEMS, LINEAR ALGORITHMS ARE NOT CONSIDERED SINCE WE ARE DEALING WITH KERNELS ON STRUCTURED DATA. FOR THE BCI PROBLEM, n = 300.

		Altern. Opt
	Data	Linear	Kernel	Gradient	Proximal
	BCI, q = 2	18.8 ± 0.8	71.8 ± 4.2	309 ± 190	0.98 ± 0.17
	BCI, q = 4 3 PSORT +, q = 2	14.8 ± 0.7 -	46.8 ± 2.3 57.4 ± 6	-110 ± 35	4.1 ± 0.5 -
	PSORT +, q = 4 3 PSORT -, q = 2	--	62.2 ±4 350.5 ± 18	127 ± 41 1450 ± 400	--
	PSORT -, q = 4 3	-	364.5 ± 32	1480 ± 300	-

  MTL 1,2 MTL p,2 MTL 1,q MCMKL PSORT + 93.87 ± 2.82 93.62 ± 3.04 93.88 ± 2.73

					93.8
	# Kernels	15.4 ± 1.17	7.4 ± 1.42	15.9 ± 1.05	18
	PSORT -	95.92 ± 1.35 95.90 ± 1.12 96.02 ± 1.33	96.1
	# Kernels	12.9 ± 0.31	7.5 ± 0.85	12.8 ± 0.42	14


Severine Rivollier
email: rivollier@emse.fr

Johan Debayle
email: debayle@emse.fr

Jean-Charles Pinoli
email: pinoli@emse.fr

GENERAL ADAPTIVE NEIGHBORHOOD-BASED MINKOWSKI MAPS FOR GRAY-TONE IMAGE ANALYSIS

Keywords: General adaptive neighborhood, GLIP Mathematical morphology, Minkowski functionals, Minkowski maps, Multiscale image representation, Pattern analysis

In quantitative image analysis, Minkowski functionals are standard parameters for topological and geometrical measurements. Nevertheless, they are often limited to binary images and achieved in a global and monoscale way. The use of General Adaptive Neighborhoods (GANs) enables to overcome these limitations. The GANs are spatial neighborhoods defined around each point of the spatial support of a gray-tone image, according to three (GAN) axiomatic criteria: a criterion function (luminance, contrast, . . . ), an homogeneity tolerance with respect to this criterion, and an algebraic model for the image space. Thus, the GANs are simultaneously adaptive with the analyzing scales, the spatial structures and the image intensities. The aim of this paper is to introduce the GAN-based Minkowski functionals, which allow a gray-tone image analysis to be realized in a local, adaptive and multiscale way. The Minkowski functionals are computed on the GAN of each point of the image, enabling to define the so-called Minkowski maps which assign the geometrical or the topological functional to each point. The impact of the GAN characteristics, as well as the impact of multiscale morphological transformations, is analyzed in a qualitative way through these maps. The GAN-based Minkowski maps are illustrated on the test image 'Lena' and also applied in the biomedical and materials areas.

INTRODUCTION

This paper aims to introduce a novel approach for analyzing a gray-tone image in a local, adaptive and multiscale way. A segmentation process, generally used before quantitative image analysis, is not here required. The quantitative description is directly applied on the raw gray-tone images. Geometrical and topological measurements, through Minkowski functionals, are performed on spatial neighborhoods associated to each point of the image. These specific neighborhoods, named General Adaptive Neighborhoods (GANs) [START_REF] Debayle | General Adaptive Neighborhood Image Processing[END_REF], are simultaneously adaptive with the analyzing scales, the spatial structures and the image intensities. It enables to define the so-called GAN-based Minkowski maps which assign a measurement (based on the local Minkowski functionals) to each point of the image to be studied.

First, this paper recalls the notions of general adaptive neighborhood and of Minkowski functionals. Then, the next section introduces the GAN-based Minkowski maps. Thereafter, the impact of the GAN axiomatic criteria (analyzing criterion, homogeneity tolerance, algebraic model), as well as the impact of a multiscale morphological transformation is analyzed in a qualitative way through these maps. The GANbased Minkowski maps are illustrated on the test image 'Lena' and also in both the biomedical and materials areas.

GENERAL ADAPTIVE NEIGHBORHOODS

The GANIP (General Adaptive Neighborhood Image Processing) approach [START_REF] Debayle | General Adaptive Neighborhood Image Processing[END_REF] provides a general and operational framework for adaptive processing and analysis of gray-tone images. It is based on an image representation by means of spatial neighborhoods, named General Adaptive Neighborhoods (GANs). Indeed, GANs are simultaneously adaptive with:

• the spatial structures: the size and the shape of the neighborhoods are adapted to the local context of the image,

• the analyzing scales: the scales are given by the image itself, and not a priori fixed,

• the intensity values: the neighborhoods are defined according to the GLIP (Generalized Linear Image Processing) mathematical framework, enabling to consider the physical and/or psychophysical settings of the image class.

For each point x of the image f , a GAN belongs to the spatial support D ⊆ R 2 of f . The neighborhood of x, denoted V h m (x), is a connected set and homogeneous with respect to an analyzing criterion h (such as luminance, contrast, thickness, . . . ) using a tolerance m within a GLIP (Generalized Linear Image Processing) framework [START_REF] Oppenheim | Generalized Superposition[END_REF][START_REF] Pinoli | A General Comparative Study of the Multiplicative Homomorphic, Log-Ratio and Logarithmic Image Processing Approaches[END_REF], i.e. in a vector space with its vector addition + and its scalar multiplication × . The GAN of a point x is mathematically defined as follows:

V h m (x) := C h -1 ([h(x) -m ;h(x) + m ]) (x) (1)
where C X (x) denotes the path-connected component (with the usual Euclidean topology on D) of X ⊆ D holding x.

Figure 1 illustrates the GANs of two points computed with the luminance criterion in the CLIP (Classical Linear Image Processing) framework (the operations + and × correspond to the usual operations between images, + and × respectively) on a human retina image. The General adaptive neighborhoods are intrinsically defined by the local structures of the image. Thus, the GANs {V h m (.)} m allow a new multi-scale representation of gray-tone images to be defined. On the contrary, the shape and size of the classical neighborhoods {B r (.)} r (centered homothetic isotropic discs, of radius r), generally used as analyzing windows for image transforms, are a priori fixed (Fig. 2).

D x 1 B r (x 1 ) x 2 B r (x 2 ) x 3 V h m (x 3 ) x 4 V h m (x 4 ) r, m Fig. 2. Classical neighborhoods B r (x) vs. general adaptive neighborhoods V h m (x).

MINKOWSKI FUNCTIONALS AND DENSITIES

In quantitative image analysis, Minkowski functionals are standard parameters for topological and geometrical measurements [START_REF] Minkowski | Volumen und Oberfläche[END_REF]. A description of the shape of a two-dimensional pattern is provided, using the three 2D Minkowski functionals (up to a constant): area, perimeter, and Euler number, denoted A, P and χ, respectively. These functionals are defined on the class of the nonempty compact convex sets (convex bodies) of R 2 , and satisfy five properties (increasing, invariance under rigid motions, homogeneity, C-additivity, continuity vs. the Hausdorff metric). They have been extended (excluding the properties of increasing and continuity) to the convex ring [START_REF] Mecke | Statistical physics and spatial statistics[END_REF], i.e. the set of all finite unions of convex bodies of R 2 , which may be considered as a realistic Euclidean model for digital planar images.

In this paper, the densities of these functionals, i.e. the ratio of the Minkowski functionals by the area of the spatial support of the image, will be used. These densities are called the specific area, the specific perimeter, and the specific Euler number, and are denoted, A A , P A and χ A , respectively.

GAN-BASED MINKOWSKI MAPS

GANs measurements enable a gray-tone image analysis, in a local, adaptive and multiscale way to be defined. For each point x of the image f , various measurements, such as area, orientation, concavities number, . . . [START_REF] Coster | Précis d'analyse d'image[END_REF][START_REF] Rivollier | Analyse spectrale morphologique adaptative d'image[END_REF], of the GAN V h m (x), can be computed. In this paper, only the (densities of) Minkowski functionals are considered.

DEFINITION

A GAN-based Minkowski map is defined in assigning a value for each point x which represents the GAN Minkowski density of V h m (x). In a more explicit way, the GAN-based Minkowski map, denoted µ h m ( f ), of an image f , with respect to the Minkowski density µ (area: µ ≡ A A , perimeter: µ ≡ P A , Euler number: µ ≡ χ A ), is defined by:

µ h m ( f ) : D → R x → µ V h m (x) (2)
where V h m (x) is the GAN of the point x with respect to the analyzing criterion h using the homogeneity tolerance m in a GLIP framework.

The densities of the Minkowski functionals of the GAN V h m (x) can be estimated in an efficient way [START_REF] Osher | Statistical Analysis of Microstructures in Materials Science[END_REF]. The GANs depend on three axiomatic criteria (eq. 1): an analyzing criterion (luminance, contrast, . . . ), an homogeneity tolerance with respect to this criterion, and an algebraic model for the criterion mapping space. The following three sections of this paper will show, from a visual point of view, the impact of these characteristics on the Minkowski maps (eq. 2).

IMPACT OF THE HOMOGENEITY TOLERANCE

The GANs are homogeneous regions with respect to an analyzing criterion using a tolerance m within a GLIP framework (Fig. 2).

b) (χ A ) f 20 (c) (χ A ) f 30 (d) (χ A ) f 40 (e) (P A ) f 20 (f) (P A ) f 30 (g) (P A ) f 40 (h) (A A ) f 20 (i) (A A ) f 30 (j) (A A ) f 40
Gray-scale lower and upper bound values

IMPACT OF THE ANALYZING CRITERION

The GANs are homogeneous with respect to a criterion function h (such as luminance, contrast, thickness, . . . ). For instance, the luminance criterion is defined by h ≡ f where f is the original image. A contrast criterion can also be used. For instance, the image contrast, denoted c, can be defined as:

c :    D → R x → 1 #N(x) ∑ y∈N(x) | f (x) -f (y)| (3)
where N(x) is a neighborhood of the point x (for instance, points in the window 3 × 3 centered on x).

IMPACT OF THE GLIP MATHEMATICAL FRAMEWORK

The criterion function h is represented in a GLIP model, i.e. a vector space with its vector addition + and its scalar multiplication × . For instance, the operations + and × of the usual CLIP (Classical Linear Image Processing) framework correspond to the usual operations between images, + and × respectively. The vector addition and the scalar multiplication of the LIP (Logarithmic Image Processing) framework [START_REF] Pinoli | A General Comparative Study of the Multiplicative Homomorphic, Log-Ratio and Logarithmic Image Processing Approaches[END_REF], denoted + △ and × △ respectively, are defined as following:

f + △ g = f + g - f g M (4) α × △ f = M -M M -f M α (5)
where f and g are intensity gray-tone images, α ∈ R is a scalar, and M ∈ R denotes the upper bound of the range where intensity images are digitized and valued. The LIP framework has been proved to be consistent with the transmittance and the multiplicative reflectance/transmittance image formation model, and with several laws and characteristics of human brightness perception [START_REF] Pinoli | A General Comparative Study of the Multiplicative Homomorphic, Log-Ratio and Logarithmic Image Processing Approaches[END_REF].

IMPACT OF A MULTISCALE MORPHOLOGICAL TRANSFORMATION

Mathematical morphology [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF] is an important and nowadays a traditional theory in image processing, particularly used for geometrical image analysis. The elementary morphological operators of dilation and erosion (and thus the combined operators of closing and opening) act on image intensities within the use of an operational window named structuring element.

The GAN-based Minkowski maps can be computed on transformed images by morphological operators. For instance, figure 7

b) D 1 ( f ) (c) D 2 ( f ) (d) D 3 ( f ) (e) (A A ) D 1 ( f ) 40 (f) (A A ) D 2 ( f ) 40 (g) (A A ) D 3 ( f ) 40 (h) E 1 ( f ) (i) E 2 ( f ) (j) E 3 ( f ) (k) (A A ) E 1 ( f ) 40 (l) (A A ) E 2 ( f ) 40 (m) (A A ) E 3 ( f ) 40 (n) C 1 ( f ) (o) C 2 ( f ) (p) C 3 ( f ) (q) (A A ) C 1 ( f ) 40 (r) (A A ) C 2 ( f ) 40 (s) (A A ) C 3 ( f ) 40 (t) O 1 ( f ) (u) O 2 ( f ) (v) O 3 ( f ) (w) (A A ) O 1 ( f ) 40 (x) (A A ) O 2 ( f ) 40 (y) (A A ) O 3 ( f ) 40
Gray-scale lower and upper bound values (a,b-d,h-j,n-p,t-v) 0 255 (e-g) 6.10 -5 67316.10 -5 (k-m) 6.10 -5 63232.10 -5 (q-s) 6.10 -5 68439.10 -5 (w-y) 6.10 -5 45911.10 -5

CONCLUSION

In this paper, a novel approach for analyzing a gray-tone image in a local, adaptive and multiscale way is proposed. The so-called GANbased Minkowski maps assign a geometrical or topological measurement of a spatial neighborhood (GAN) associated to each point of the image to be studied.

The influence of the GAN axiomatic criteria (analyzing criterion, homogeneity tolerance, algebraic model), and the impact of a multiscale morphological transformation on the image to be studied, is analyzed in a qualitative way through these maps. Currently, the authors investigate a quantitative analysis through the histogram of these maps.

  Fig. 1. The GANs of the two points x and y of the original image (a) are connected and homogeneous (b) with respect to the luminance criterion using the tolerance value m = 20 within the CLIP framework.

Figure 3

 3 Figure 3 illustrates some GAN-based Minkowski maps of the image 'Lena' f . The GANs are homogeneous with respect to the luminance criterion (h ≡ f ) using the tolerance value m = 40 in the CLIP framework. Therefore, the value µ h m (x) of each point x of the Minkowski map corresponds to the density µ of the GAN V f 40 (x).

Fig. 3 .

 3 Fig. 3. GAN-based Minkowski maps (b-d) of the image 'Lena' (a) with respect to the luminance criterion h ≡ f using the homogeneity tolerance m = 40 in the CLIP mathematical framework. Gray-scale bound values gives the extrema of the Minkowski densities.

Figure 4

 4 Figure 4 illustrates the GAN-based Minkowski maps of a brain MR image f with respect to the luminance criterion f using various homogeneity tolerance values: m = 20, m = 30 and m = 40 in the CLIP framework. This figure illustrates the fact that the application m → (A A ) f m (.) increases, contrary to m → (P A ) f m (.) and m → (χ A ) f m (.). This property can be generalized to the others GLIP frameworks and criterions. This is due to the tortuosity of the adaptive neighborhood's boundary and the number of holes of this one.

Fig. 4 .

 4 Fig. 4. GAN-based Minkowski maps (b-j) of a brain image (a) with respect to the luminance criterion f using the homogeneity tolerance values m = 20 (b,e,h), m = 30 (c,f,i) and m = 40 (d,g,j) in the CLIP framework.

Figure 5

 5 Figure 5 illustrates the GAN-based Minkowski maps of a fibronectin image f with respect to the luminance criterion f and the contrast criterion c using the homogeneity tolerance m = 10 in the CLIP framework.

Fig. 5 .

 5 Fig. 5. GAN-based Minkowski maps (c-h) of a fibronectin image (a) with respect to the luminance criterion f (c,e,g) and the contrast criterion c (d,f,h) using the homogeneity tolerance m = 10 in the CLIP framework.

Figure 6

 6 Figure 6 illustrates the GAN-based Minkowski maps of a zinc sulfide image f acquired by scanning electron microscopy imaging with respect to the luminance criterion f using the homogeneity tolerance value 50 in both the CLIP and LIP mathematical frameworks, respectively.

  Fig. 6. GAN-based Minkowski maps (b-g) of a zinc

  first illustrates the morphological tranforms using a disk of radius r as structuring element (dilation D r , erosion E r , closing C r , opening O r ) of the image 'Lena' f . Thereafter, the GAN-based Minkowski maps (using the area functional) are computed with respect to the luminance criterion f using the homogeneity tolerance m = 40 in the CLIP framework. This figure illustrates the fact that the application r → (A A ) T r ( f ) m (.) is non-monotonous, contrary to r → T r ( f )(.).

Fig. 7 .

 7 Fig. 7. GAN-based Minkowski maps (e-g,k-m,q-s,wy) of the image 'Lena' (a) dilated (b-d), eroded (hj), closed (n-p), opened (t-v) with a disk of radius r,

ACKNOWLEDGMENTS

The authors wish to thank the University Hospital Center (ophtalmology and radiology) of Saint-Etienne in France, the UMR CNRS 5148, and the INSERM U890, who have kindly provided the original images.