Yuan Shi

Aurélien Bellet
email: bellet@usc.edu.

Fei Sha
email: feisha@usc.edu.

Sha Fei

Sparse Compositional Metric Learning

Keywords:

come   L'archive ouverte pluridisciplinaire

Introduction

The need for measuring distance or similarity between data instances is ubiquitous in machine learning and many application domains. However, each problem has its own underlying semantic space for defining distances that standard metrics (e.g., the Euclidean distance) often fail to capture. This has led to a growing interest in metric learning for the past few years, as summarized in two recent surveys [START_REF] Bellet | A Survey on Metric Learning for Feature Vectors and Structured Data[END_REF][START_REF] Kulis | Metric Learning: A Survey[END_REF]. Among these methods, learning a globally linear Mahalanobis distance is by far the most studied setting. Representative methods include [START_REF] Xing | Distance Metric Learning with Application to Clustering with Side-Information[END_REF][START_REF] Goldberger | Neighbourhood Components Analysis[END_REF][START_REF] Davis | Information-theoretic metric learning[END_REF][START_REF] Jain | Online Metric Learning and Fast Similarity Search[END_REF][START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF][START_REF] Shen | Positive Semidefinite Metric Learning Using Boostinglike Algorithms[END_REF][START_REF] Ying | Distance Metric Learning with Eigenvalue Optimization[END_REF]. This is equivalent to learning a linear projection of the data to a feature space where constraints on the training set (such as "x i should be closer to x j than to x k ") are better satisfied.

Although the performance of these learned metrics is typically superior to that of standard metrics in practice, a single linear metric is often unable to accurately capture the complexity of the task, for instance when the data are multimodal or the decision boundary is complex. To overcome this limitation, recent work has focused on learning multiple locally linear metrics at several locations of the feature space [START_REF] Frome | Learning Globally-Consistent Local Distance Functions for Shape-Based Image Retrieval and Classification[END_REF][START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF][START_REF] Zhan | Learning instance specific distances using metric propagation[END_REF][START_REF] Hong | Learning a mixture of sparse distance metrics for classification and dimensionality reduction[END_REF][START_REF] Wang | Parametric Local Metric Learning for Nearest Neighbor Classification[END_REF], to the extreme of learning one metric per training instance [START_REF] Noh | Generative Local Metric Learning for Nearest Neighbor Classification[END_REF]. This line of research is motivated by the fact that locally, simple linear metrics perform well [START_REF] Ramanan | Local Distance Functions: A Taxonomy, New Algorithms, and an Evaluation[END_REF][START_REF] Hauberg | A Geometric take on Metric Learning[END_REF]. The main challenge is to integrate these metrics into a meaningful global one while keeping the number of learning parameters to a reasonable level in order to avoid heavy computational burden and severe overfitting. So far, existing methods are not able to compute valid (smooth) global metrics from the local metrics they learn and do not provide a principled way of generalizing to new regions of the space at test time. Furthermore, Figure 1: Illustration of the general framework and its applications. We extract locally discriminative basis elements from the training data and cast metric learning as learning sparse combinations of these elements. We formulate global metric learning as learning a single sparse weight vector w. For multi-task metric learning, we learn a vector w t for each task where all tasks share the same basis subset. For local metric learning we learn a function T (x) that maps any instance x to its associated sparse weight vector w x . Shades of grey encode weight magnitudes. they scale poorly with the dimensionality D of the data: typically, learning a Mahalanobis distance requires O(D 2 ) parameters and the optimization involves projections onto the positive semidefinite cone that scale in O(D 3 ). This is expensive even for a single metric when D is moderately large.

In this paper, we study metric learning from a new perspective to efficiently address these key challenges. We propose to learn metrics as sparse compositions of locally discriminative metrics. These "basis metrics" are low-rank and extracted efficiently from the training data at different local regions, for instance using Fisher discriminant analysis. Learning higher-rank linear metrics is then formulated as learning the combining weights, using sparsity-inducing regularizers to select only the most useful basis elements. This provides a unified framework for metric learning, as illustrated in Figure 1, that we call SCML (for Sparse Compositional Metric Learning). In SCML, the number of parameters to learn is much smaller than existing approaches and projections onto the positive semidefinite cone are not needed. This gives an efficient and flexible way to learn a single global metric when D is large.

The proposed framework also applies to multi-task metric learning, where one wants to learn a global metric for several related tasks while exploiting commonalities between them [START_REF] Caruana | Multitask Learning[END_REF][START_REF] Parameswaran | Large Margin Multi-Task Metric Learning[END_REF]. This is done in a natural way by means of a group sparsity regularizer that makes the task-specific metrics share the same basis subset. Our last and arguably most interesting contribution is a new formulation for local metric learning, where we learn a transformation T (x) that takes as input any instance x and outputs a sparse weight vector defining its metric. This can be seen as learning a smoothly varying metric tensor over the feature space [START_REF] Ramanan | Local Distance Functions: A Taxonomy, New Algorithms, and an Evaluation[END_REF][START_REF] Hauberg | A Geometric take on Metric Learning[END_REF]. To the best of our knowledge, it is the first discriminative metric learning approach capable of computing, in a principled way, an instance-specific metric for any point in the feature space. All formulations can be solved using scalable optimization procedures based on stochastic subgradient descent with proximal operators [START_REF] Duchi | Efficient Online and Batch Learning Using Forward Backward Splitting[END_REF][START_REF] Xiao | Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization[END_REF].

We present both theoretical and experimental evidence supporting the proposed approach. We derive a generalization bound which provides a theoretical justification to seeking sparse combinations and suggests that the basis set B can be large without incurring overfitting. Empirically, we evaluate our algorithms against state-of-the-art global, local and multi-task metric learning methods on several datasets. The results strongly support the proposed framework.

The rest of this paper is organized as follows. Section 2 describes our general framework and illustrates how it can be used to derive efficient formulations for global, local and multi-task metric learning. Section 3 provides a theoretical analysis supporting our approach. Section 4 reviews related work. Section 5 presents an experimental evaluation of the proposed methods. We conclude in Section 6.

Proposed Approach

In this section, we present the main idea of sparse compositional metric learning (SCML) and show how it can be used to unify several existing metric learning paradigms and lead to efficient new formulations.

Main Idea

We assume the data lie in R D and focus on learning (squared) Mahalanobis distances d M (x, x ) = (xx ) T M (x -x ) parameterized by a positive semidefinite (PSD) D × D matrix M . Note that M can be represented as a nonnegative weighted sum of K rank-1 PSD matrices:1

M = K i=1 w i b i b T i , with w ≥ 0, (1)
where the b i 's are D-dimensional column vectors.

In this paper, we use the form (1) to cast metric learning as learning a sparse combination of basis elements taken from a basis set B = {b i } K i=1 . The key to our framework is the fact that such a B is made readily available to the algorithm and consists of rank-one metrics that are locally discriminative. Such basis elements can be easily generated from the training data at several local regions -in the experiments, we simply use Fisher discriminant analysis (see the corresponding section for details). They can then be combined to form a single global metric, multiple global metrics (in the multi-task setting) or a metric tensor (implicitly defining an infinite number of local metrics) that varies smoothly across the feature space, as we will show in later sections.

We use the notation d w (x, x ) to highlight our parameterization of the Mahalanobis distance by w. Learning M in this form makes it PSD by design (as a nonnegative sum of PSD matrices) and involves K parameters (instead of D 2 in most metric learning methods), enabling it to more easily deal with highdimensional problems. We also want the combination to be sparse, i.e., some w i 's are zero and thus M only depends on a small subset of B. This provides some form of regularization (as shown later in Theorem 1) as well as a way to tie metrics together when learning multiple metrics. In the rest of this section, we apply the proposed framework to several metric learning paradigms (see Figure 1). We start with the simple case of global metric learning (Section 2.1.1) before considering more challenging settings: multi-task (Section 2.1.2) and local metric learning (Section 2.1.3). Finally, Section 2.2 discusses how these formulations can be solved in a scalable way using stochastic subgradient descent with proximal operators.

Global Metric Learning

In global metric learning, one seeks to learn a single metric d w (x, x ) from a set of distance constraints on the training data. Here, we use a set of triplet constraints C where each (x i , x j , x k ) ∈ C indicates that the distance between x i and x j should be smaller than the distance between x i and x k . C may be constructed from label information, as in LMNN [START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF], or in an unsupervised manner based for instance on implicit users' feedback (such as clicks on search engine results). Our formulation for global metric learning, SCML-Global, is simply to combine the local basis elements into a higher-rank global metric that satisfies well the constraints in C:

min w 1 |C| (x i ,x j ,x k )∈C L w (x i , x j , x k ) + β w 1 , (2)
where

L w (x i , x j , x k ) = [1 + d w (x i , x j ) -d w (x i , x k )] + with [•] + = max(0,
•), and β ≥ 0 is a regularization parameter. The first term in (2) is the classic margin-based hinge loss function. The second term w 1 = K i=1 w i is the 1 norm regularization which encourages sparse solutions, allowing the selection of relevant basis elements. SCML-Global is convex by the linearity of both terms and is bounded below, thus it has a global minimum.

Multi-Task Metric Learning

Multi-task learning [START_REF] Caruana | Multitask Learning[END_REF] is a paradigm for learning several tasks simultaneously, exploiting their commonalities. When tasks are related, this can perform better than separately learning each task. Recently, multi-task learning methods have successfully built on the assumption that the tasks should share a common low-dimensional representation [START_REF] Argyriou | Convex multi-task feature learning[END_REF][START_REF] Yang | Heterogeneous multitask learning with joint sparsity constraints[END_REF][START_REF] Gong | Robust multi-task feature learning[END_REF]. In general, it is unclear how to achieve this in metric learning. In contrast, learning metrics as sparse combinations allows a direct translation of this idea to multi-task metric learning.

Formally, we are given T different but somehow related tasks with associated constraint sets C 1 , . . . , C T and we aim at learning a metric d wt (x, x ) for each task t while sharing information across tasks. In the following, the basis set B is the union of the basis sets B 1 , . . . , B T extracted from each task t. Our formulation for multi-task metric learning, mt-SCML, is as follows:

min W T t=1 1 |C t | (x i ,x j ,x k )∈Ct L wt (x i , x j , x k ) + β W 2,1 ,
where W is a T × K nonnegative matrix whose t-th row is the weight vector w t defining the metric for task t, L wt (x i , x j , x k ) = [1 + d wt (x i , x j ) -d wt (x i , x k )] + and W 2,1 is the 2 / 1 mixed norm used in the group lasso problem [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF]. It corresponds to the 1 norm applied to the 2 norm of the columns of W and is known to induce group sparsity at the column level. In other words, this regularization makes most basis elements either have zero weight or nonzero weight for all tasks.

Overall, while each metric remains task-specific (d wt is only required to satisfy well the constraints in C t ), it is composed of shared features (i.e., it potentially benefits from basis elements generated from other tasks) that are regularized to be relevant across tasks (as favored by the group sparsity). As a result, all learned metrics can be expressed as combinations of the same basis subset of B, though with different weights for each task. Since the 2 / 1 norm is convex, mt-SCML is again convex.

Local Metric Learning

Local metric learning addresses the limitations of global methods in capturing complex data patterns [START_REF] Frome | Learning Globally-Consistent Local Distance Functions for Shape-Based Image Retrieval and Classification[END_REF][START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF][START_REF] Zhan | Learning instance specific distances using metric propagation[END_REF][START_REF] Noh | Generative Local Metric Learning for Nearest Neighbor Classification[END_REF][START_REF] Hong | Learning a mixture of sparse distance metrics for classification and dimensionality reduction[END_REF][START_REF] Wang | Parametric Local Metric Learning for Nearest Neighbor Classification[END_REF]. For heterogeneous data, allowing the metric to vary across the feature space can capture the semantic distance much better. On the other hand, local metric learning is costly and often suffers from severe overfitting since the number of parameters to learn can be very large. In the following, we show how our framework can be used to derive an efficient local metric learning method.

We aim at learning a metric tensor T (x), which is a smooth function that (informally) maps any instance x to its metric matrix [START_REF] Ramanan | Local Distance Functions: A Taxonomy, New Algorithms, and an Evaluation[END_REF][START_REF] Hauberg | A Geometric take on Metric Learning[END_REF]. The distance between two points should then be defined as the geodesic distance on a Riemannian manifold. However, this requires solving an intractable problem, so we use the widely-adopted simplification that distances from point x are computed based on its own metric alone [START_REF] Zhan | Learning instance specific distances using metric propagation[END_REF][START_REF] Noh | Generative Local Metric Learning for Nearest Neighbor Classification[END_REF][START_REF] Wang | Parametric Local Metric Learning for Nearest Neighbor Classification[END_REF]:

d T (x, x ) = (x -x ) T T (x)(x -x ) = (x -x ) T K i=1 w x,i b i b T i (x -x ),
where w x is the weight vector for instance x.

We could learn a weight vector for each training point. This would result in a formulation similar to mt-SCML, where each training instance is considered as a task. However, in the context of local metric learning, this is not an appealing solution. Indeed, for a training sample of size S we would need to learn SK parameters, which is computationally difficult and leads to heavy overfitting for large-scale problems. Furthermore, this gives no principled way of computing the weight vector of a test instance.

We instead propose a more effective solution by constraining the weight vector for an instance x to parametrically depend on some embedding of x:

T A,c (x) = K i=1 (a T i z x + c i ) 2 b i b T i , (3)
where

z x ∈ D is an embedding of x, 2 A = [a 1 . . . a K ] T is a D × K real-valued matrix and c ∈ R K .
The square makes the weights nonnegative ∀x ∈ R D , ensuring that they define a valid (pseudo) metric.

Intuitively, (3) combines the locally discriminative metrics with weights that depend on the position of the instance in the feature space.

There are several advantages to this formulation. First, by learning A and c we implicitly learn a different metric not only for the training data but for any point in the feature space. Second, if the embedding is smooth, T A,c (x) is a smooth function of x, therefore similar instances are assigned similar weights. This can be seen as some kind of manifold regularization. Third, the number of parameters to learn is now K(D + 1), thus independent of both the size of the training sample and the dimensionality of x. Our formulation for local metric learning, SCML-Local, is as follows:

min à 1 |C| (x i ,x j ,x k )∈C L T A,c (x i , x j , x k ) + β à 2,1 ,
where à is a (D + 1) × K matrix denoting the concatenation of A and c, and

L T A,c (x i , x j , x k ) = 1 + d T A,c (x i , x j ) -d T A,c (x i , x k ) + .
The 2 / 1 norm on à introduces sparsity at the column level, regularizing the local metrics to use the same basis subset. Interestingly, if A is the zero matrix, we recover SCML-Global. SCML-Local is nonconvex and is thus subject to local minima.

Optimization

Our formulations use (nonsmooth) sparsity-inducing regularizers and typically involve a large number of triplet constraints. We can solve them efficiently using stochastic composite optimization [START_REF] Duchi | Efficient Online and Batch Learning Using Forward Backward Splitting[END_REF][START_REF] Xiao | Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization[END_REF], which alternates between a stochastic subgradient step on the hinge loss term and a proximal operator (for 1 or 2,1 norm) that explicitly induces sparsity. We solve SCML-Global and mt-SCML using Regularized Dual Averaging [START_REF] Xiao | Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization[END_REF], which offers fast convergence and levels of sparsity in the solution comparable to batch algorithms. For SCML-Local, due to local minima, we ensure improvement over the optimal solution w * of SCML-Global by using a forward-backward algorithm [START_REF] Duchi | Efficient Online and Batch Learning Using Forward Backward Splitting[END_REF] which is initialized with A = 0 and c i = w * i . Recall that unlike most existing metric learning algorithms, we do not need to perform projections onto the PSD cone, which scale in O(D3 ) for a D × D matrix. Our algorithms thereby have a significant computational advantage for high-dimensional problems.

Theoretical Analysis

In this section, we provide a theoretical analysis of our approach in the form of a generalization bound based on algorithmic robustness analysis [START_REF] Xu | Robustness and Generalization[END_REF] and its adaptation to metric learning [START_REF] Bellet | Robustness and Generalization for Metric Learning[END_REF]. For simplicity, we focus on SCML-Global, our global metric learning formulation in (2).

Consider the supervised learning setting, where we are given a labeled training sample S = {z i = (x i , y i )} n i=1 drawn i.i.d. from some unknown distribution P over Z = X × Y. We call a triplet (z, z , z ) admissible if y = y = y . Let C be the set of admissible triplets built from S and L(w, z, z , z ) = [1 + d w (x, x ) -d w (x, x )] + denote the loss function used in (2), with the convention that L returns 0 for non-admissible triplets.

Let us define the empirical loss of w on S as

R S emp (w) = 1 |C| (z,z ,z )∈C L(w, z, z , z ),
and its expected loss over distribution P as

R(w) = E z,z ,z ∼P L(w, z, z , z ).
The following theorem bounds the deviation between the empirical loss of the learned metric and its expected loss.

Theorem 1. Let w * be the optimal solution to SCML-Global with K basis elements, β > 0 and C constructed from S = {(x i , y i )} n i=1 as above. Let K * ≤ K be the number of nonzero entries in w * . Let us assume the norm of any instance bounded by some constant R and L uniformly upper-bounded by some constant U . Then for any δ > 0, with probability at least 1 -δ we have:

R(w * ) -R S emp (w * ) ≤ 16γRK * β + 3U N ln 2 + ln 1 δ 0.5n ,
where N is the size of an γ-cover of Z.

This bound has a standard O(1/ √ n) asymptotic convergence rate. 3 Its main originality is that it provides a theoretical justification to enforcing sparsity in our formulation. Indeed, notice that K * (and not K) appears in the bound as a penalization term, which suggests that one may use a large basis set K without overfitting as long as K * remains small. This will be confirmed by our experiments (Section 5.3). A similar bound can be derived for mt-SCML, but not for SCML-Local because of its nonconvexity. The details and proofs can be found in Appendix A.

Related Work

In this section, we review relevant work in global, multi-task and local metric learning. The interested reader should refer to the recent surveys of [START_REF] Kulis | Metric Learning: A Survey[END_REF] and [START_REF] Bellet | A Survey on Metric Learning for Feature Vectors and Structured Data[END_REF] for more details.

Global methods Most global metric learning methods learn the matrix M directly: see [START_REF] Xing | Distance Metric Learning with Application to Clustering with Side-Information[END_REF][START_REF] Goldberger | Neighbourhood Components Analysis[END_REF][START_REF] Davis | Information-theoretic metric learning[END_REF][START_REF] Jain | Online Metric Learning and Fast Similarity Search[END_REF][START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF] for representative papers. This is computationally expensive and subject to overfitting for moderate to high-dimensional problems. An exception is BoostML [START_REF] Shen | Positive Semidefinite Metric Learning Using Boostinglike Algorithms[END_REF] which uses rank-one matrices as weak learners to learn a global Mahalanobis distance via a boosting procedure. However, it is not clear how BoostML can be generalized to multi-task or local metric learning.

Multi-task methods Multi-task metric learning was proposed in [START_REF] Parameswaran | Large Margin Multi-Task Metric Learning[END_REF] as an extension to the popular LMNN [START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF]. The authors define the metric for task t as

d t (x, x ) = (x -x ) T (M 0 + M t )(x -x )
, where M t is task-specific and M 0 is shared by all tasks. Note that it is straightforward to incorporate their approach in our framework by defining a shared weight vector w 0 and task-specific weights w t . However, this assumption of a metric that is common to all tasks can be too restrictive in cases where task relatedness is complex, as illustrated by our experiments.

Local methods MM-LMNN [START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF]) is an extension of LMNN which learns only a small number of metrics (typically one per class) in an effort to alleviate overfitting. However, no additional regularization is used and a full-rank metric is learned for each class, which becomes intractable when the number of classes is large. msNCA [START_REF] Hong | Learning a mixture of sparse distance metrics for classification and dimensionality reduction[END_REF] learns a function that splits the space into a small number of regions and then learns a metric per region using NCA [START_REF] Goldberger | Neighbourhood Components Analysis[END_REF]. Again, the metrics are full-rank so msNCA does not scale well with the number of metrics. Like SCML-Local, PLML [START_REF] Wang | Parametric Local Metric Learning for Nearest Neighbor Classification[END_REF] is based on a combination of metrics but there are major differences with our work: (i) weights only depend on a manifold assumption: they are not sparse and use no discriminative information, (ii) the basis metrics are full-rank, thus expensive to learn, and (iii) a weight vector is learned explicitly for each training instance, which can result in a large number of parameters and prevents generalization to new instances (in practice, for a test point, they use the weight vector of its nearest neighbor in the training set). As observed by [START_REF] Ramanan | Local Distance Functions: A Taxonomy, New Algorithms, and an Evaluation[END_REF], the above methods make the implicit assumption that the metric tensor is locally constant (at the class, region or neighborhood level), while SCML-Local learns a smooth function that maps any instance to its specific metric. ISD [START_REF] Zhan | Learning instance specific distances using metric propagation[END_REF] is an attempt to learn the metrics for unlabeled points by propagation, but is limited to the transductive setting. Unlike the above discriminative approaches, GLML [START_REF] Noh | Generative Local Metric Learning for Nearest Neighbor Classification[END_REF] learns a metric for each point independently in a generative way by minimizing the 1-NN expected error under some assumption for the class distributions.

Experiments

In this section, we compare our methods to state-of-the-art algorithms on global, multi-task and local metric learning. 4 We use a 3-nearest neighbor classifier in all experiments. To generate a set of locally discriminative rank-one metrics, we first divide data into regions via clustering. For each region center, we select J nearest neighbors from each class (for J = {10, 20, 50} to account for different scales), and apply Fisher discriminant analysis followed by eigenvalue decomposition to obtain the basis elements.5 Section 5.1 presents results for global metric learning, Section 5.2 for multi-task and Section 5.3 for local metric learning.

Global Metric Learning

We use 6 datasets from UCI6 and BBC7 (see Table 1). The dimensionality of USPS and BBC is reduced to 100 and 200 using PCA to speed up computation. We normalize the data as in [START_REF] Wang | Parametric Local Metric Learning for Nearest Neighbor Classification[END_REF] and split into train/validation/test (60%/20%/20%), except for Letters and USPS where we use 3,000/1,000/1,000.

Results are averaged over 20 random splits.

Proof of Concept

Setup Global metric learning is a convenient setting to study the effect of combining basis elements. To this end, we consider a formulation with the same loss function as SCML-Global but that directly learns the metric matrix, using Frobenius norm regularization to reduce overfitting. We refer to it as Global-Frob. Both algorithms use the same training triplets, generated by identifying 3 target neighbors (nearest neighbors with same label) and 10 imposters (nearest neighbors with different label) for each instance. We tune the regularization parameter on the validation data. For SCML-Global, we use a basis set of 400 elements for Vehicle, Vowel, Segment and BBC, and 1,000 elements for Letters and USPS. Table 4: Average number of basis elements in the solution.

Results

Table 2 shows misclassification rates with standard errors, where Euc is the Euclidean distance.

The results show that SCML-Global performs similarly as Global-Frob on low-dimensional datasets but has a clear advantage when dimensionality is high (USPS and BBC). This demonstrates that learning a sparse combination of basis elements is an effective way to reduce overfitting and improve generalization. SCML-Global is also faster to train than Global-Frob on these datasets (about 2x faster on USPS and 3x on BBC) because it does not require any PSD projection.

Comparison to Other Global Algorithms

Setup We now compare SCML-Global to two state-of-the-art global metric learning algorithms: Large Margin Nearest Neighbor (LMNN, [START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF] and BoostML [START_REF] Shen | Positive Semidefinite Metric Learning Using Boostinglike Algorithms[END_REF]. The datasets, preprocessing and setting for SCML-Global are the same as in Section 5.1.1. LMNN uses 3 target neighbors and all imposters, while these are set to 3 and 10 respectively for BoostML (as in SCML-Global).

Results Table 3 shows the average misclassification rates, along with standard error and the average rank of each method across all datasets. SCML-Global clearly outperforms LMNN and BoostML, ranking first on 5 out of 6 datasets and achieving the overall highest rank. Furthermore, its training time is smaller than competing methods, especially for high-dimensional data. For instance, on the BBC dataset, SCML-Global trained in about 90 seconds, which is about 20x faster than LMNN and 35x faster than BoostML. Note also that SCML-Global is consistently more accurate than linear SVM, as shown in Appendix B.

Number of selected basis elements

Like SCML-Global, recall that BoostML is based on combining rank-one elements (see Section 4). The main difference with SCML-Global is that our method is given a set of locally discriminative metrics and picks the relevant ones by learning sparse weights, while BoostML generates a new basis element at each iteration and adds it to the current combination. elements than BoostML (on two datasets, it uses more but this yields to significantly better performance).

The results on USPS and BBC also suggest that the number of basis elements selected by SCML-Global seems to scale well with dimensionality. These nice properties come from its knowledge of the entire basis set and the sparsity-inducing regularizer. On the contrary, the number of elements (and therefore iterations) needed by BoostML to converge seems to scale poorly with dimensionality.

Multi-task Metric Learning

Dataset Sentiment Analysis [START_REF] Blitzer | Biographies, Bollywood, Boom-boxes and Blenders: Domain Adaptation for Sentiment Classification[END_REF] is a popular dataset for multi-task learning that consists of Amazon reviews on four product types: kitchen appliances, DVDs, books and electronics. Each product type is treated as a task and has 1,000 positive and 1,000 negative reviews. To reduce computational cost, we represent each review by a 200-dimensional feature vector by selecting top 200 words of the largest mutual information with the labels. We randomly split the dataset into training (800 samples), validation (400 samples) and testing (400 samples) sets.

Setup We compare the following metrics: st-Euc (Euclidean distance), st-LMNN and st-SCML (singletask LMNN and single-task SCML-Global, trained independently on each task), u-Euc (Euclidean trained on the union of the training data from all tasks), u-LMNN (LMNN on union), u-SCML (SCML-Global on union), multi-task LMNN [START_REF] Parameswaran | Large Margin Multi-Task Metric Learning[END_REF] and finally our own multi-task method mt-SCML. We tune the regularization parameters in mt-LMNN, st-SCML, u-SCML and mt-SCML on validation sets. As in the previous experiment, the number of target neighbors and imposters for our methods are set to 3 and 10 respectively. We use a basis set of 400 elements for each task for st-SCML, the union of these (1,600) for mt-SCML, and 400 for u-SCML.

Results

Table 5 shows the results averaged over 20 random splits. First, notice that u-LMNN and u-SCML obtain significantly higher error rates than st-LMNN and st-SCML respectively, which suggests that the dataset may violate mt-LMNN's assumption that all tasks share a similar metric. Indeed, mt-LMNN does not outperform st-LMNN significantly. On the other hand, mt-SCML performs better than its singletask counterpart and than all other compared methods by a significant margin, demonstrating its ability to leverage some commonalities between tasks that mt-LMNN is unable to capture. It is worth noting that the solution found by mt-SCML is based on only 273 basis elements on average (out of a total of 1,600), while st-SCML makes use of significantly more elements (347 elements per task on average). Basis elements selected by mt-SCML are evenly distributed across all tasks, which indicates that it is able to exploit meaningful information across tasks to get both more accurate and more compact metrics. Finally, note that our algorithms are about an order of magnitude faster.

Local Metric Learning

Setup We use the same datasets and preprocessing as for global metric learning. We compare SCML-Local to MM-LMNN [START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF], GLML [START_REF] Noh | Generative Local Metric Learning for Nearest Neighbor Classification[END_REF] and PLML [START_REF] Wang | Parametric Local Metric Learning for Nearest Neighbor Classification[END_REF]. The parameters of all methods are tuned on validation sets or set by authors' recommendation. MM-LMNN use 3 target neighbors and all imposters, while these are set to 3 and 10 in PLML and SCML-Local.

The number of anchor points in PLML is set to 20 as done by the authors. For SCML-Local, we use the same basis set as SCML-Global, and embedding dimension D is set to 40 for Vehicle, Vowel, Segment and BBC, and 100 for Letters and USPS.

Results Table 6 gives the error rates along with the average rank of each method across all datasets. Note that SCML-Local significantly improves upon SCML-Global on all but one dataset and achieves the best average rank. PLML does not perform well on small datasets (Vehicle and Vowel), presumably because there are not enough points to get a good estimation of the data manifold. GLML is fast but has rather poor performance on most datasets because its Gaussian assumption is restrictive and it learns the local metrics independently. Among discriminative methods, SCML-Local offers the best training time, especially for high-dimensional data (e.g. on BBC, it trained in about 8 minutes, which is about 5x faster than MM-LMNN and 15x faster than PLML). Note that on this dataset, both MM-LMNN and PLML perform worse than SCML-Global due to severe overfitting, while SCML-Local avoids it by learning significantly fewer parameters. Finally, SCML-Local achieves accuracy results that are very competitive with those of a kernel SVM, as shown in Appendix B.

Visualization of the learned metrics To provide a better understanding of why SCML-Local works well, we apply it to digits 1, 2, and 3 of USPS projected in 2D using t-SNE (van der [START_REF] Van Der Maaten | Visualizing Data using t-SNE[END_REF], We see that the local metrics vary smoothly and are thereby robust to outliers. Unlike MM-LMNN, points within a class are allowed to have different metrics: in particular, this is useful for points that are near the decision boundary. While smooth, the variation in the weights is thus driven by discriminative information, unlike PLML where they are only based on the smoothness assumption. Finally, Figure 2(c) shows that the metrics consistently generalize to test data.

Effect of the basis set size Figure 3 shows the number of selected basis elements and test error rate for SCML-Global and SCML-Local as a function of the size of basis set on Segment (results were consistent on other datasets). The left pane shows that the number of selected elements increases sublinearly and eventually converges, while the right pane shows that test error may be further reduced by using a larger basis set without significant overfitting, as suggested by our generalization bound (Theorem 1). Figure 3 also shows that SCML-Local generally selects more basis elements than SCML-Global, but notice that it can outperform SCML-Global even when the basis set is very small.

Conclusion

We proposed to learn metrics as sparse combinations of rank-one basis elements. This framework unifies several paradigms in metric learning, including global, local and multi-task learning. Of particular interest is our local metric learning algorithm which can compute instance-specific metrics for both training and test points in a principled way. The soundness of our approach is supported theoretically by a generalization bound, and we showed in experimental studies that the proposed methods improve upon state-of-the-art algorithms in terms of accuracy and scalability.

Let L(h, z, z , z ) be the loss suffered by some hypothesis h on triplet (z, z , z ), with the convention that L returns 0 for non-admissible triplets. We assume L to be uniformly upper-bounded by a constant U . The empirical loss R C S emp (h) of h on C S is defined as

R C S emp (h) = 1 |C S | (z,z ,z )∈C S L(h, z, z , z ),
and its expected loss R(h) over distribution P as

R(h) = E z,z ,z ∼P L(h, z, z , z ).
Our goal is to bound the deviation between R(A C S ) and R C S emp (A C S ), where A C S is the hypothesis learned by algorithm A on C S .

A.2 Algorithmic Robustness

To derive our generalization bounds, we use the recent framework of algorithmic robustness [START_REF] Xu | Robustness and Generalization[END_REF], in particular its adaptation to pairwise and tripletwise loss functions used in metric learning [START_REF] Bellet | Robustness and Generalization for Metric Learning[END_REF]. For the reader's convenience, we briefly review these main results below.

Algorithmic robustness is the ability of an algorithm to perform "similarly" on a training example and on a test example that are "close". The proximity of points is based on a partitioning of the space Z: two examples are close to each other if they lie in the same region. The partition is based on the notion of covering number [START_REF] Kolmogorov | -entropy and -capacity of sets in functional spaces[END_REF].

Definition 1 (Covering number). For a metric space (S, ρ) and V ⊂ S, we say that

V ⊂ V is a γ-cover of V if ∀t ∈ V, ∃ t ∈ V such that ρ(t, t) ≤ γ. The γ-covering number of V is N (γ, V, ρ) = min | V| : V is a γ-cover of V .
In particular, when X is compact, N (γ, X , ρ) is finite, leading to a finite cover. Then, Z can be partitioned into |Y|N (γ, X , ρ) subsets such that if two examples z = (x, y) and z = (x , y ) belong to the same subset, then y = y and ρ(x, x ) ≤ γ. The definition of robustness for tripletwise loss functions (adapted from [START_REF] Xu | Robustness and Generalization[END_REF]) is as follows.

Definition 2 (Robustness for metric learning [START_REF] Bellet | Robustness and Generalization for Metric Learning[END_REF]).

An algorithm A is (N, (•)) robust for N ∈ N and (•) : (Z × Z) n → R if Z can be partitioned into N disjoints sets, denoted by {Q i } N i=1 , such that the following holds for all S ∈ Z n : ∀(z 1 , z 2 , z 3 ) ∈ C S , ∀z, z , z ∈ Z, ∀i, j ∈ [N ] : if z 1 , z ∈ Q i , z 2 , z ∈ Q j , z 3 , z ∈ Q k then |L(A C S , z 1 , z 2 , z 3 ) -L(A C S , z, z , z )| ≤ (C S ),
where A C S is the hypothesis learned by A on C S .

N and (•) quantify the robustness of the algorithm and depend on the training sample. Again adapting the result from [START_REF] Xu | Robustness and Generalization[END_REF], [START_REF] Bellet | Robustness and Generalization for Metric Learning[END_REF] showed that a metric learning algorithm that satisfies Definition 2 has the following generalization guarantees.

In the non-admissible case, by definition their respective loss is 0 and so is the deviation between the losses. In the admissible case we have:

[1 + dw * (x1, x2) -dw * (x1, x3)] + -1 + dw * (x 1 , x 2 ) -dw * (x 1 , x 3 ) + ≤ |(x1 -x2) T M * (x1 -x2) -(x1 -x3) T M * (x1 -x3) + (x 1 -x 3 ) T M * (x 1 -x 3 ) -(x 1 -x 2 ) T M * (x 1 -x 2 )| = |(x1 -x2) T M * (x1 -x2) -(x1 -x2) T M * (x 1 -x 2 ) + (x1 -x2) T M * (x 1 -x 2 ) -(x 1 -x 2 ) T M * (x 1 -x 2 ) + (x 1 -x 3 ) T M * (x 1 -x 3 ) -(x 1 -x 3 ) T M * (x1 -x3) + (x 1 -x 3 ) T M * (x1 -x3) -(x1 -x3) T M * (x1 -x3)| = |(x1 -x2) T M * (x1 -x2 -(x 1 -x 2 )) + (x1 -x2 -(x 1 -x 2 )) T M * (x 1 -x 2 ) + (x 1 -x 3 ) T M * (x 1 -x 3 -(x1 -x3)) + (x 1 -x 3 -(x1 -x3)) T M * (x1 -x3)| ≤ |(x1 -x2) T M * (x1 -x 1 )| + |(x1 -x2) T M * (x 2 -x2)| + |(x1 -x 1 ) T M * (x 1 -x 2 )| + |(x 2 -x2) T M * (x 1 -x 2 )| + |(x 1 -x 3 ) T M * (x 1 -x1)| + |(x 1 -x 3 ) T M * (x3 -x 3 )| + |(x 1 -x1) T M * (x1 -x3)| + |(x3 -x 3 ) T M * (x1 -x3)| ≤ x1 -x2 ∞ M * 1 x1 -x 1 1 + x1 -x2 ∞ M * 1 x 2 -x2 1 + x1 -x 1 1 M * 1 x 1 -x 2 ∞ + x 2 -x2 1 M * 1 x 1 -x 2 ∞ + x 1 -x 3 ∞ M * 1 x 1 -x1 1 + x 1 -x 3 ∞ M * 1 x3 -x 3 1 + x 1 -x1 1 M * 1 x1 -x3 ∞ + x3 -x 3 1 M * 1 x1 -x3 ∞ ≤ 16γRK * β ,
by using the property that the hinge loss is 1-Lipschitz, Holder's inequality and bounds on the involved quantities. Thus SCML-Global is (|Y |N (γ, X, • 1 ), 16γRK * β )-robust and the generalization bound follows.

A.3.2 Bound for mt-SCML

In the multi-task setting, we are given a training sample S t = {z i = (x t i , y t i )} nt i=1 . Let C St be the set of all admissible triplets built from instances in S t .

Let W * be the optimal solution to mt-SCML. Using the same arguments as for SCML-Global, by optimality of W * we have W * 2,1 ≤ 1/β. Let M * t = K i=1 W * ti b i b T i be the learned metric for task t and W * t be the weight vector for task t, corresponding to the t-th row of W * . Then using the fact that W * t 2,1 ≤ W * 2,1 and b 2,1 = b 2 , we have:

M * t 2,1 = K i=1 W * ti b i b T i 2,1 = i:W * ti =0 W * ti b i b T i 2,1 ≤ W * t 2,1 i:W * ti =0 b i 2,1 b i 2,1 ≤ K * t /β,
where K * t ≤ K is the number of nonzero entries in W * t . From this we can derive a generalization bound for each task using arguments similar to the global case, using a partition specific to each task defined with respect to • 2 . Without loss of generality, we focus on task t and only explicitly write the last derivations as the beginning is the same as above: where we used the same arguments as above and the inequality M * F ≤ M * 2,1 . Thus mt-SCML is

[1 + d w * (x 1 , x 2 ) -d w * (x 1 , x 3 )] + -[1 + d w * (x 1 , x 2 ) -d w * (x 1 , x 3 )] + ≤ |(x 1 -x 2 ) T M * (x 1 -x 1 )| + |(x 1 -x 2 ) T M * (x 2 -x 2 )| + |(x 1 -x 1 ) T M * (x 1 -x 2 )| + |(x 2 -x 2 ) T M * (x 1 -x 2 )| + |(x 1 -x 3 ) T M * (x 1 -x 1 )| + |(x 1 -x 3 ) T M * (x 3 -x 3 )| + |(x 1 -x 1 ) T M * (x 1 -x 3 )| + |(x 3 -x 3 ) T M * (x 1 -x 3 )| ≤ x 1 -x 2 2 M * F x 1 -x 1 2 + x 1 -x 2 2 M * F x 2 -x 2 2 + x 1 -x 1 2 M * F x 1 -x 2 2 + x 2 -x 2 2 M * F x 1 -x 2 2 + x 1 -x 3 2 M * F x 1 -x 1 2 + x 1 -x 3 2 M * F x 3 -x 3 2 + x 1 -x 2 2 M * F x 1 -x 3 2 + x 3 -x 3 2 M * F x 1 -x 3 2 ≤ 16γRK *
(|Y |N (γ, X, • 2 ), 16γRK * t β
)-robust and the bound for task t follows. Note that the number of training examples in the bound is only that from task t, i.e., n = n t .

A.3.3 Comments on SCML-Local

It would be interesting to be able to derive a similar bound for SCML-Local. Unfortunately, as it is nonconvex, we cannot assume optimality of the solution. If a similar formulation can be made convex, the same proof technique should apply: even though each instance has its own metric, it essentially depends on the instance itself (whose norm is bounded) and on the learned parameters shared across metrics (which could be bounded using optimality of the solution). Deriving such a convex formulation and the corresponding generalization bound is left as future work.

Figure 2 :

 2 Figure 2: Illustrative experiment on digits 1, 2 and 3 of USPS in 2D. Refer to the main text for details.

Figure 3 :

 3 Figure 3: Effect of the number of bases on Segment dataset.

Table 1 :

 1 Datasets for global and local metric learning.

	Vehicle Vowel Segment Letters USPS BBC
	# samples 846	990	2,310 20,000 9,298 2,225
	# classes	4	11	7	26	10	5
	# features	18	10	19	16	256 9,636
	Dataset		Euc	Global-Frob SCML-Global
	Vehicle 29.7±0.6 21.5±0.8	21.3±0.6
	Vowel 11.1±0.4 10.3±0.4	10.9±0.5
	Segment 5.2±0.2	4.1±0.2		4.1±0.2
	Letters 14.0±0.2	9.0±0.2		9.0±0.2
	USPS 10.3±0.2	5.1±0.2		4.1±0.1
	BBC	8.8±0.3	5.5±0.3		3.9±0.2

Table 2 :

 2 Global metric learning results (best in bold).

Table 3 :

 3 Comparison of SCML-Global against LMNN and BoostML (best in bold).

	Dataset	Euc	LMNN BoostML SCML-Global
	Vehicle 29.7±0.6 23.5±0.7 19.9±0.6	21.3±0.6
	Vowel 11.1±0.4 10.8±0.4 11.4±0.4	10.9±0.5
	Segment 5.2±0.2 4.6±0.2 3.8±0.2	4.1±0.2
	Letters 14.0±0.2 11.6±0.3 10.8±0.2	9.0±0.2
	USPS	10.3±0.2 4.1±0.1 7.1±0.2	4.1±0.1
	BBC	8.8±0.3 4.0±0.2 9.3±0.3	3.9±0.2
	Avg. rank	3.3	2.0	2.3	1.2
		Dataset BoostML SCML-Global
		Vehicle	334	164
		Vowel	19	47
		Segment	442	49
		Letters	20	133
		USPS	2,375	300
		BBC	3,000	59

Table 5 :

 5 Multi-task metric learning results.

	Task	st-Euc	st-LMNN st-SCML	u-Euc	u-LMNN u-SCML	mt-LMNN mt-SCML
	Books	33.5±0.5 29.7±0.4 27.0±0.5 33.7±0.5 29.6±0.4 28.0±0.4	29.1±0.4	25.8±0.4
	DVD	33.9±0.5 29.4±0.5 26.8±0.4 33.9±0.5 29.4±0.5 27.9±0.5	29.5±0.5	26.5±0.5
	Electronics	26.2±0.4 23.3±0.4 21.1±0.5 29.1±0.5 25.1±0.4 22.9±0.4	22.5±0.4	20.2±0.5
	Kitchen	26.2±0.6 21.2±0.5 19.0±0.4 27.7±0.5 23.5±0.3 21.9±0.5	22.1±0.5	19.0±0.4
	Avg. accuracy 30.0±0.2 25.9±0.2 23.5±0.2 31.1±0.3 26.9±0.2 25.2±0.2	25.8±0.2	22.9±0.2
	Avg. runtime	N/A	57 min	3 min	N/A	44 min	2 min	41 min	5 min

Table 4 reports the number of basis elements used in SCML-Global and BoostML solutions. Overall, SCML-Global uses fewer

Table 6 :

 6 Local metric learning results (best in bold).

	Dataset MM-LMNN GLML	PLML SCML-Local
	Vehicle	23.1±0.6 23.4±0.6 22.8±0.7	18.0±0.6
	Vowel	6.8±0.3	4.1±0.4 8.3±0.4	6.1±0.4
	Segment	3.6±0.2	3.9±0.2 3.9±0.2	3.6±0.2
	Letters	9.4±0.3	10.3±0.3 8.3±0.2	8.3±0.2
	USPS	4.2±0.7	7.8±0.2 4.1±0.1	3.6±0.1
	BBC	4.9±0.4	5.7±0.3 4.3±0.2	4.1±0.2
	Avg. rank	2.0	2.7	2.0	1.2

Table 7 :

 7 Comparison of SCML against linear and kernel SVM (best in bold).

	β	t	,

Such an expression exists for any PSD matrix M since the eigenvalue decomposition of M is of the form (1).

In our experiments, we use kernel PCA[START_REF] Schölkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF] as it provides a simple way to limit the dimension and thus the number of parameters to learn. We use RBF kernel with bandwidth set to the median Euclidean distance in the data.

In robustness bounds, the cover radius γ can be made arbitrarily close to zero at the expense of increasing N . Since N appears in the second term, the right hand side of the bound indeed goes to zero when n → ∞. This is in accordance with other similar learning bounds, for example, the original robustness-based bounds in[START_REF] Xu | Robustness and Generalization[END_REF].

For all compared methods we use MATLAB code from the authors' website. The MATLAB code for our methods is available at http://www-bcf.usc.edu/ ˜bellet/.

We also experimented with a basis set based on local GLML metrics. Preliminary results were comparable to those obtained with the procedure above.

http://archive.ics.uci.edu/ml/

http://mlg.ucd.ie/datasets/bbc.html

When the training triplets consist of only a subset of all admissible triplets (which is often the case in practice), a relaxed version of the robustness property can be used to derive similar results[START_REF] Bellet | Robustness and Generalization for Metric Learning[END_REF]. For simplicity, we focus here on the case when all admissible triplets are used.

Acknowledgements This research is partially supported by the IARPA via DoD/ARL contract # W911NF-12-C-0012 and DARPA via contract # D11AP00278. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of IARPA, DoD/ARL, DARPA, or the U.S. Government.

Appendix A Detailed Analysis

In this section, we give the details of the derivation of the generalization bounds for the global and multi-task learning formulations given in Section 3.

A.1 Preliminaries

We start by introducing some notation. We are given a training sample S = {z i = (x i , y i )} n i=1 drawn i.i.d. from a distribution P over the labeled space Z = X × Y. We assume that x ≤ R (for some convenient norm), ∀x ∈ X . We call a triplet (z, z , z ) admissible if y = y = y . Let C S be the set of all admissible triplets built from instances in S. 8

Theorem 2. If a learning algorithm A is (N, (•))-robust and the training sample consists of the triplets C S obtained from a sample S generated by n i.i.d. draws from P , then for any δ > 0, with probability at least 1 -δ we have:

As shown in [START_REF] Bellet | Robustness and Generalization for Metric Learning[END_REF], establishing the robustness of an algorithm is easier using the following theorem, which basically says that if a metric learning algorithm has approximately the same loss for triplets that are close to each other, then it is robust.

and

We now have all the tools we need to prove the results of interest.

A.3 Generalization Bounds for SCML A.3.1 Bound for SCML-Global

We first focus on SCML-Global where the loss function is defined as follows:

We obtain a generalization bound by showing that SCML-Global satisfies Definition 2 using Theorem 3. To establish the result, we need a bound on the 2 norm of the basis elements. Since they are obtained by eigenvalue decomposition, their norm is equal to (and thus bounded by) 1.

Let w * be the optimal solution to SCML-Global. By optimality of w * we have:

i be the learned metric. Then using Holder's inequality and the bound on w * and the b's:

where K * ≤ K is the number of nonzero entries in w * .

Using Definition 1, we can partition Z into |Y|N (γ, X , ρ) subsets such that if two examples z = (x, y) and z = (x , y ) belong to the same subset, then y = y and ρ

(z 1 , z 2 , z 3 ) are either both admissible or both non-admissible triplets.

Appendix B Experimental Comparison with Support Vector Machines

In this section, we compare SCML-Global and SCML-Local to Support Vector Machines (SVM) using a linear and a RBF kernel. We used the software LIBSVM [START_REF] Chang | LIBSVM : a library for support vector machines[END_REF] and tuned the parameter C as well as the bandwidth for the RBF kernel on the validation set. Table 7 shows misclassification rates averaged over 20 random splits, along with standard error and the average rank of each method across all datasets. First, we can see that SCML-Global consistently performs better than linear SVM. Second, SCML-Local is competitive with kernel SVM. These results show that a simple k-nearest neighbor strategy with a good metric can be competitive (and even outperform) SVM classifiers.


PhD Agata Krasny-Pacini

Francillette Leila

MD Toure Hanna

MD Brugel Dominique

MD Laurent-Vannier Anne

MD Meyer Philippe

PhD Evans Jonathan

PhD Chevignard Mathilde

Keywords:

2 prospective longitudinal study: a brief report.

PM than matched controls in the two low-motivation PM tasks: (1) the ecological long-delay task consisting of sending a letter on a rainy day (p=0.047, odds ratio = 2.6); (2) the non-ecological short-delay task consisting of taking off post-its while identifying facial emotions (p=0.004, r=0.34). Differences in PM on the high motivation were not significant. PM is impaired several years post severe TBI Prospective memory (PM) is the ability to remember to perform intended activities [START_REF] Kliegel | The effects of age and cue-action reminders on event-based prospective memory performance in preschoolers[END_REF] . Children with PM impairment can fail to deliver important messages to parents, forget appointments, or fail to bring necessary items for planned activities. Successful PM requires (a) that you remember what has to be done (this includes remembering the action to be performed and the proper target event) and (b) that you remember to perform the action at the appropriate time or in response to the appropriate target event [START_REF] Einstein | Normal aging and prospective memory[END_REF] .

PM tasks require retrospective memory to remember the task, but depend on executive functions (EF) [START_REF] Fish | The assessment and rehabilitation of prospective memory problems in people with neurological disorders: A review[END_REF] for successful goal maintenance, retrieval and execution at the right moment. At least three attributes are accepted as characterizing a PM task [START_REF] Ellis | Prospective memory in 2000: Past, present, and future directions[END_REF] : (1) a delay between formation of the intention and the opportunity to carry it out; (2) absence of an explicit reminder to carry out the task at an appropriate moment; (3) the need to interrupt one's ongoing activity in order to carry out the intention.

One of the most influential models of PM is the Multiprocess Framework of McDaniel and Einstein [START_REF] Mcdaniel | Strategic and automatic processes in prospective memory retrieval: A multiprocess framework[END_REF] . This framework suggests that there are several ways by which prospective remembering may be achieved and several factors that influence PM performance. Thus, PM may be accomplished by the strategic allocation of monitoring resources (i.e. actively monitoring for PM target cues), or by more automatic memory processes whereby a PM cue automatically triggers memory for the intended action. Probability of remembering is affected by factors such as the importance of the task, PM cue distinctiveness, level of association between cue and intended action, whether the PM cue is focal (i.e. will be encountered and attended to as part of an ongoing task) or non-focal (i.e. is present but not attended to as part of the ongoing task), how demanding the ongoing task is, and the extent of pre-task planning. Most of the studies that have identified these influences on PM performance have, however, involved adults and it is less clear whether the same factors may be relevant to the PM of children.

Although PM problems are reported as a major concern by the parents of children with traumatic brain injury (TBI) [START_REF] Ward | Interview study of the effects of paediatric traumatic brain injury on memory[END_REF] , there are surprisingly few studies that have evaluated PM in children with TBI (as opposed to adults with TBI [START_REF] Fish | The assessment and rehabilitation of prospective memory problems in people with neurological disorders: A review[END_REF][START_REF] Shum | Prospective memory and traumatic brain injury: A review[END_REF][START_REF] Shum | Prospective memory in patients with closed head injury: A review[END_REF] ). Ward et al. [START_REF] Ward | Prospective Memory and Pediatric Traumatic Brain Injury: Effects of Cognitive Demand[END_REF] found that children with TBI had poorer PM than their uninjured peers, and that this may be attributable to worse executive functioning, especially if the PM task is cognitively demanding. Recently, a real cooking task (Children's Cooking Task [START_REF] Chevignard | Development and Evaluation of an Ecological Task to Assess Executive Functioning Post Childhood TBI: The Children's Cooking Task[END_REF][START_REF] Chevignard | Assessment of executive functioning in children after TBI with a naturalistic open-ended task: A pilot study[END_REF] ) has been used to explore PM in children with acquired brain injury [START_REF] Krasny-Pacini | Ecological prospective memory assessment in children with acquired brain injury using the Children's Cooking Task[END_REF] : it showed a striking impairment in PM, with older (14-20 years) children with brain injuries performing close to young (8-10 years) healthy controls. McCauley et al. [START_REF] Mccauley | Incentive effects on event-based prospective memory performance in children and adolescents with traumatic brain injury[END_REF][START_REF] Mccauley | Monetary incentive effects on event-based prospective memory three months after traumatic brain injury in children[END_REF][START_REF] Mccauley | Event-based prospective memory performance during subacute recovery following moderate to severe traumatic brain injury in children: Effects of monetary incentives[END_REF] used a monetary incentive to increase children's performance on an event-based PM task consisting of asking the examiner for points (exchangeable for dollars or for pennies) before each new neuropsychological test. Children with severe TBI were impaired on PM. Motivation (dollars versus pennies) influenced PM performance of controls and of children with chronic severe TBI [START_REF] Mccauley | Incentive effects on event-based prospective memory performance in children and adolescents with traumatic brain injury[END_REF] , while it had no effect on children with subacute severe TBI [START_REF] Mccauley | Monetary incentive effects on event-based prospective memory three months after traumatic brain injury in children[END_REF][START_REF] Mccauley | Event-based prospective memory performance during subacute recovery following moderate to severe traumatic brain injury in children: Effects of monetary incentives[END_REF] . However even the chronic severe TBI group performance remained significantly below the low-motivation condition performance of controls.

Limitations of these studies were that they used either a biased sample of children with TBI (recruited from patients referred for rehabilitation) or, for the one prospective study [START_REF] Mccauley | Event-based prospective memory performance during subacute recovery following moderate to severe traumatic brain injury in children: Effects of monetary incentives[END_REF] , children examined early after their TBI. Therefore, the frequency and degree of PM impairment after severe TBI in the long term is unknown. This is particularly needed information because PM can impair functional memory and daily life even more than episodic memory [START_REF] Ward | Interview study of the effects of paediatric traumatic brain injury on memory[END_REF] , but most patients in clinical practice (and even in research or legal expertise) are assessed only on the latter.

The aim of this study was to investigate long term PM outcome following childhood severe TBI, using short novel ecological PM tasks in a prospective longitudinal cohort. Our hypothesis were that (1) individuals with a TBI would perform more poorly on all PM tasks; (2) in high motivation task, individuals with TBI would differ less from controls than on low motivation tasks; (3) PM performance would be better in older individuals.

Methods

Participants: Participants were a cohort of children with severe accidental TBI [defined as Glasgow Coma Scale (GCS) score of 8 or lower at admission and/or an Injury severity score [START_REF] Baker | The injury severity score: a method for describing patients with multiple injuries and evaluating emergency care[END_REF] > 16], aged 0-15 years at the time of inclusion and recruited between 2005 and 2008 at the pediatric neurosurgical intensive care unit of Paris 5 University "Necker Enfants Malades" Hospital. The main aim of the follow up of this cohort was to assess cognitive functioning, participation and quality of life several years post-severe TBI (manuscripts in preparation). Exclusion criteria at the time of cohort recruitment were: children with no vital signs upon admission, children with non-accidental head injury, previous history of diagnosed neurological, psychiatric or learning disorders. Patients were assessed at seven years post inclusion for PM. By the seven year testing, the sample therefore contained both children (<18 years) and young adults (≥18 years). A population-based group of healthy controls was recruited at the seven year follow up point.

Controls were matched individually in terms of age (±3 months of age), gender and parental education (± 2 years of education) with each individual from the TBI group. For controls, the exclusion criteria were the same as for the TBI sample plus the absence of any TBI history. Socio-demographic data collected included language spoken at home, type of schooling and TBI characteristics for the TBI group. This study is part of a larger study, which was approved by the CPP IDF VI ethic committee. PM tasks: Three ecological tasks of PM were developed for the study. The tasks were embedded in an assessment of outcome and quality of life following TBI that is not reported here. Because PM performance is influenced by motivation [START_REF] Mccauley | Incentive effects on event-based prospective memory performance in children and adolescents with traumatic brain injury[END_REF] , by the ecological features of the task (meaningful task versus exercise type task, home versus laboratory context) [START_REF] Ceci | Don't forget to take the cupcakes out of the oven": prospective memory, strategic time-monitoring, and context[END_REF] and by delay [START_REF] Rendell | Effect of delay on children's delay-execute prospective memory performance[END_REF] between formation of an intention (PM instructions in this case) and the opportunity to carry out the intention, the tasks were designed to vary on these three factors.

Low-motivation, ecological context, ecological task, long delay: the letter task: participants received an envelope with the address of the hospital and were asked to send to the examiner a short note the next time it rained in the place they live. The letter had to contain four pieces of information: name of the participant, date, place and a mention of rain. The participant was also told than even if s/he forgot to send the letter the first time it rained, s/he could still do it later on, the most important thing being to send the letter at some point. Instructions were given twice to the participant during the testing and the examiner checked if the individual had understood and encoded the instructions by asking him/her to repeat them. The task was not explained to parents, but they were warned the participant had a task to do when s/he was at home. They were told that this was the reason why s/he had an envelope for the hospital. They were asked not to help the participant. Data from the letter task was treated as categorical (success or failure) in relation to two components: (1) sending the letter with all adequate information (which comprised a retrospective memory component -the letter content -as with most PM tasks of daily life) and ( 2) sending the letter irrespective of content (which assessed the prospective component of PM, as the child only had to remember the intention to send a letter).

High-motivation, ecological task, non-ecological context, medium delay task: the amusement park prize-draw competition: at the beginning of the testing, individuals were told they could enter a prizedraw competition to thank them for participating in the study. The examiner showed them a colored entry sheet that mentioned the draw. They were told that they could enter their name for the draw after the end of testing. The prize was two entries for an amusement park of their choice. At the end of the testing (6-7 hours after the instructions for the participants with TBI and 2.5-3 hours after the instructions for the controls who had less tests to complete), the examiner said "ok, we have finished all the tests, well done". If the participant did not ask spontaneously to enter the draw, the examiner made discreetly visible the colored competition entry-sheet so that it came into the participant visual space but without giving it to him/her. If the participant did not react to this visual cue, the examiner used a verbal nonspecific cue: "did you want do to something else before leaving?". If this was not enough, the participant was reminded explicitly s/he could enter his/her name for the draw competition. Data from the draw competition PM task was treated as ordinal: 3 points were awarded for individuals succeeding without cues (individuals asking spontaneously to enter the competition at the end of testing); 2 points for individuals needing the visual cue only; 1 point for individuals needing the verbal cue and zero points for individuals needing an explicit reminder to enter their name for the draw. On the competition entry-sheet the participant was instructed to add his/her name and telephone number. In addition, there was an instruction to read and to tell the examiner which amusement park s/he would like to go to if s/he won, and to fold the completed sheet in two for the draw box. These tasks did not constitute PM tasks as they could be carried out immediately, but tested the child's ability to follow through a series of task instructions.

Low-motivation, exercise-type, non-ecological context, short delay (retrieve-execute): post-it/faces task: in the last task, the delay was short. For this task, we used two existing tests as the on-going task: the NEPSY-2 affect recognition subtest (< 18 years) and the Bordeaux Faces Test [START_REF] Etchepare | Évaluer la cognition sociale chez l'adulte : validation préliminaire du Protocole d'évaluation de la cognition sociale de Bordeaux (PECS-B)[END_REF] (≥ 18 years). In the adult version and most items of the child version, the individual had to name an emotion by looking at a face. Colored post-its were placed on some pages of these tests. The individuals were told to remove all the post-its apart from the pink ones throughout the task, but only after they had stated the emotion, not before. There were 9 post-its to remove (and 4 pink post-its to leave), placed in pre-determined positions on nine of the 39 (children version) or 40 (adult version) pages of the test. The instruction to take off only post-its of certain colors was meant to increase task difficulty and prevent the individuals from automatizing post-it removal without effortful processing. Face recognition was used as the ongoing task, because we considered this close to everyday life: usually face recognition happens conjunctively with complex reasoning ("what have I said? Is he angry or sad?"), prospective memory or multitasking (thinking of the bus arriving in 5 minutes while searching for keys and trying to figure out if our companion is cross following the previous conversation).

Participants: Eighty-one children were included at the acute stage of TBI between January 2005 and December 2008. Causes of accidental TBI were motor vehicle accidents and falls. Sixteen children died during acute care, leaving 65 children entering the follow-up. Most children (83%) received multidisciplinary rehabilitation after acute care, similar to that described by Chevignard et al [START_REF] Chevignard | A comprehensive model of care for rehabilitation of children with acquired brain injuries[END_REF] . By seven years post-injury, 26 were lost to follow-up, leaving 39 patients, aged 7-22 at PM assessment. Three of them could not be tested for PM (one was too fatigued, one had a severe depression, one agreed to participate initially and then refused to finish the testing).

Statistical analysis: All analyses were performed with IBM SPSS 21. Individuals with severe TBI participating in the study were compared to individuals lost to follow-up, by Mann-Whitney tests on GCS score, coma length, age at injury, and one-year post injury intellectual quotients and executive functioning [START_REF] Krasny-Pacini | Executive function after severe childhood traumatic brain injury -Age-at-injury vulnerability periods: The TGE prospective longitudinal study[END_REF] . Further, Chi squared test was used to compare participants for language spoken at home, gender and parental education (defined as high if above high school or low if high school and below). The same tests were used to compare the participating severe TBI group to the control group on age at testing, parental education, gender and language spoken at home. Controls and individuals with TBI were compared for categorical PM data using Chi squared test. Effect size was calculated by odds ratios. The draw competition PM data was ordinal and therefore analyzed also using Mann-Whitney test. The Post-it task yielded a score of number of post-its taken out which was analyzed between groups using Mann-Whitney tests because score distribution was not normal, and effect size was calculated using r = 𝑧 √𝑁 and interpreted according to Cohen's guidelines [START_REF] Cohen | Statistical Power Analysis for the Behavioral Sciences[END_REF] . Additionally, among each group (TBI and controls), adults' performance was compared to childrens' performance using Mann-Whitney test or Fisher's exact test.

Results and Discussion

Individuals remaining at 7 years follow-up did not differ significantly from those lost to follow-up on GCS score, coma length, parental education, language used at home, age at injury, nor on their one year postinjury intellectual quotients and executive functioning (all ps>0.05). Detailed description and results of IQ and EF used at one year follow-up can be found elsewhere [START_REF] Krasny-Pacini | Executive function after severe childhood traumatic brain injury -Age-at-injury vulnerability periods: The TGE prospective longitudinal study[END_REF] . Most individuals (26) were still children at the time of the study but 13 had become young adults. Thirty-seven controls were recruited (two controls could not be recruited within the time frame of the study). There was no significant difference between the TBI and the control groups on gender, age at testing, parental education, and language spoken at home (see Age at testing effects: Children performed poorer than young adults on the Post-it Task, irrespective of injury status (in the TBI group: Mann-Whitney U=210, z=2.61, p=0.009, r=0.38; in the typically developing controls: Mann-Whitney U=237, z=2.69, p=0.007, r=0.44). On the prospective component of the letter task (sending a letter irrespective of content), there was a trend for adults to perform better than children in both groups (Fisher's exact test = 0.068 in the TBI group and 0.084 in the typically developing controls group). There was no difference between younger and older participants for the prize-draw competition and the overall letter task.

Regarding the study hypothesis, individuals with severe TBI showed significantly poorer PM than matched controls in the two low-motivation PM tasks. Differences in PM on the high motivation task were not significant. Developmental effects varied across tasks: children performed poorer than young adults on the Post-it Task, irrespective of injury status; there was no difference between younger and older participants for the other tasks. This is to our knowledge the largest cohort of patients having sustained severe childhood TBI. Most cohorts usually include heterogeneous samples of children with a range of TBI severity, where severe TBI are usually relatively few. It is also to our knowledge the first cohort study that assessed PM at long-term post injury. The prospective longitudinal nature of this study was expected to capture more positive outcomes compared to retrospective studies based on the inclusion of patients in rehabilitation departments; nonetheless PM impairment appeared significant. This should raise awareness about frequent PM deficits, that are not explored by usual memory tests used in children and adults, and that should be given more attention, given the consequences of PM deficits on everyday life.

Our result are consistent with previous publications on both developmental [START_REF] Somerville | Young Children's Deliberate Reminding[END_REF] and clinical samples [START_REF] Mccauley | Incentive effects on event-based prospective memory performance in children and adolescents with traumatic brain injury[END_REF] that showed that deficits in PM performance may be reduced under high motivation conditions. The lack of age effects in the high motivation condition may have been due to an unequal degree of motivation, as the experimenter noted qualitatively that younger children seemed more enthusiastic about the prize-draw, while some young adults and adolescents appeared less interested (one did not even want to enter the draw). An unequal motivation effect was probably also present for the letter task, which was designed to be a low motivation condition: children aged 7-10 seemed very proud to have a letter to write and post and many parents reported the enthusiasm of their child for the task. Also, we cannot exclude that parents helped their children with the letter task, because young children are not expected to send a letter on their own and it may have seemed natural for their parents to help them despite the examiner's explanations. There were some indications, albeit not statistically significant, that younger children had more difficulties than older children on the letter posting task. This may simply have been because younger children are less familiar with posting letters than older children and adults. Unusual PM cues that have fewer general associations than more familiar cues are considered to be more likely to prompt PM task performance 2 but less is known about the effect of familiarity of the intended action, particularly in children, something which needs to be explored further.

Whether PM improves with age is still a matter of debate. Small children as young as two can succeed in PM if motivation is high (remind their Mum to buy them sweets) [START_REF] Somerville | Young Children's Deliberate Reminding[END_REF] [START_REF] Kvavilashvili | The development of prospective memory in children: Methodological issues, empirical findings, and future directions[END_REF] . This is in line with our findings, as the prize-draw competition showed no difference between age groups.

Limitations: The way the tasks were designed did not allow to systematically evaluate the three variables of delay, motivation and context, because comparable conditions were not constructed for each of the two conditions of the three variables. The differences observed between the high and low motivation tasks may be due to unequal task difficulty and not the motivation factor per se. Therefore, it is difficult to draw firm conclusions, on how motivation and the other factors influenced PM. Most tasks generated categorical or ordinal data that did not allow assessment of PM impairment severity. The advantage of using these three different 1-item PM tasks that tried in different ways to be close to real life (ecological context of the letter task, ecological real-life activity of entering an amusement park draw, use of joint facial recognition and PM task similar to real life conditions) was counterbalanced by the question of reliability and validity of those tasks. However, this study was not aiming at precisely characterizing and quantify PM impairment but rather provide pilot data on PM without relying on usual paper-and-pencil tests that underestimate PM deficits [START_REF] Krasny-Pacini | Ecological prospective memory assessment in children with acquired brain injury using the Children's Cooking Task[END_REF] or don't even screen for PM impairment. It would have been interesting to assess PM using questionnaires of PM in daily life completed by parents, which was not possible in this study, as families already had several questionnaires and interviews to complete for other parts of the study. The burden of assessment would have been too high. Also, because all individuals were assessed 7 years post injury, those injured youngest had also the youngest age at testing; therefore, age at injury effects could not be explored (would have been confounded with developmental effects). Finally, it would be interesting to explore if poorer EF contributed to poorer PM performance as the role of EF in PM in children is a matter of debate [START_REF] Kvavilashvili | The development of prospective memory in children: Methodological issues, empirical findings, and future directions[END_REF] and to explore if poorer retrospective memory or attentional resources could account for the differences in PM observed in our tasks.

The post-it task could be argued to reflect rather a dual task (dependent more on working memory ability than prospective memory), as the target (non-pink post-its) were relatively frequent (9 targets out of 40 pages), while other experimental laboratory PM tasks tend to use less frequent targets (e.g.: 2 out of 13 [START_REF] Mahy | Executive functioning and prospective memory in young children[END_REF] , 1 out of 20 [START_REF] Kvavilashvili | Prospective memory in children: the effects of age and task interruption[END_REF] ) but not always (e.g.: 3 out of 10 1 ). Probably, the higher the number of target stimuli, the more the task relies on working memory, because the frequent target acts as a constant reminder of the intention and is therefore kept in the attentional focus of working memory [START_REF] Oberauer | Access to information in working memory: Exploring the focus of attention[END_REF] . On the other hand, if the target is infrequent, as the on-going task proceeds, the intention drops progressively to lower attentional levels. Further, dual task performance is more about switching between two activities while PM more about delaying an intention until a favorable moment to execute it is encountered. Our post-it task may have better assessed PM if the target stimuli were less frequent. Further, because children had to switch between facial recognition, post-it removal and pink post-it inhibition of removal, the task evaluated probably both working memory and PM. The post-it task was complex, with the element of removing

table 1

 1 *Controls could not be matched for type of schooling as the exclusion criteria excluded controls with neurological and learning disorders and therefore children needing special schooling were excluded.

	).

* Each control was matched individually to one patient in terms of age, gender and parental education.

However, due to recruitment difficulties of individuals from parental very low education background, the last 4 controls had to be matched more loosely on parental education. *

Table 1 : Demographic variables of the TBI and the control groups and injury variables of the TBI group.

 1

		Individuals with	Controls	Test statistic
		severe TBI
		Letter Task
	% individuals who	20%	49%	χ 2 (1) = 6.68,
	succeeded to send			p=0.01*
	the letter with all			odds ratio = 3.7
	information
	required
	% individuals who	44%	68%	χ 2 (1) = 3.96,
	succeeded to send			p=0.047*
	a letter,			odds ratio =2.6
	irrespective of
	adequate content
		Prize Draw Competition
	% individuals who	28%	27%	U=660, z=-0.07,
	spontaneously			p= 0.94
	entered their
	name for the draw			χ 2 (3) = 2.30,
	% individuals who	19%	14%	p=0.51
	needed visual
	cues to enter their
	name for the draw
	% individuals who	31%	46%
	needed verbal
	cues to enter their
	name for the draw
	% individuals who	22%	13%
	needed an explicit
	reminder to enter
	their name for the
	draw
		Post-it Task
	% individuals who	36%	13%	U=420.5, z=-2.87,
	totally forgot to			p= 0.004*, r=0.34
	take out the post-
	its			χ 2 (2) = 8.43,
	% individuals who	28%	60%	p=0.015*
	remembered to
	take off all
	required (non-
	pink) post-its
	% individuals who	36%	27%
	partially
	remembered to
	take off required
	(non-pink) post-its

PM tasks: Results are summarized in Table

2

.

TABLE 2 : Results of Prospective Memory tasks in the TBI group and the control group U=789

 2 , z=2.28, p= 0.023, r=0.27) and who spoke exclusively French at home (Mann-Whitney U=377, z=-2.34, p= 0.019, r=0.28) followed more instructions.

This research was co-funded by the French Ministry of Health's general direction of health and direction of research, studies, assessment and statistics, by the national fund for health insurance of salaried workers, the national fund for health insurance of independent workers, by the national fund for solidarity and autonomy and by the national institute for prevention and education for health, in the call for research projects launched by the IReSP in 2011.

We wish to thank Sabine Lancien, Maria de Agostini, Sylvie Escolano, for their participation in the data collection and analyses in the initial inclusion and follow-up of this cohort. We also thank Laurence Watier for her participation in the design and analyses of the results of the 7-year follow-up part of the study.

Letter task -Overall, 56 % of participants sent a letter. Individuals with TBI failed significantly more on both the prospective and the retrospective component of the task. One letter from a control contained weather and date information but no name and therefore it was not included in the analysis. If an individual had sustained a TBI he was 2.6 times more likely to forget to send the letter and 3.7 times less likely to send a letter with all required information. Amusement park prize-draw task -Although unequal delay between instructions and opportunity to carry out the intention may have disadvantaged the individuals with TBI on this task, there was no significant difference between individuals with TBI (Mean Rank = 36.8) and controls (Mean Rank =37. 16) in the prize-draw competition (U=660, z=-0.07, p= 0.94).

Capacity to follow the 5 instructions to enter the draw: When entering the amusement park draw competition, individuals with TBI managed to follow less instructions (fill in name, read instructions, fill in table with phone number, state the amusement park they would like to go to, fold the participation sheet for the draw) than controls (mean in TBI group = 3.7, mean in controls = 4.2; Mann-Whitney U=452.5, z= -2.20, p= 0.028, r=0.26).

Post-it Task-Individuals with TBI remembered to take out significantly less post-its (Mean = 5.06, SD = 4.07) than their matched controls [Mean = 7.35, SD = 3.07, (U=420.5, z=-2.87 , p= 0.004, r=0.34)]. Apart from one control who took out all four pink post its, individuals respected the rule of leaving the pink post its equally well in the TBI and the control group (p = 0.16). Performance on the on-going tasks (emotion recognition) was not significantly different between controls and individuals with TBI (p=0.11 for children and p = 0.12 for adults).

Demographic and injury effects: None of the PM tasks was influenced by parental education, initial GCS or coma length. In the whole sample, individuals whose parents had higher education (Mann-Whitney post-its on some pages, but not removing the pink ones. To some extent the task may have been considered 'non-focal' [START_REF] Einstein | Multiple Processes in Prospective Memory Retrieval: Factors Determining Monitoring Versus Spontaneous Retrieval[END_REF] in that the ongoing task (face emotion recognition) did not require conscious attention to the post-its, though they were present during the course of the task. For non-focal tasks it is suggested that a greater degree of strategic monitoring is required, as memory associations with the intended action are not triggered automatically [START_REF] Mcdaniel | Strategic and automatic processes in prospective memory retrieval: A multiprocess framework[END_REF] . Given that executive skills develop with age, this may explain why the young adults were better than the children in both the TBI and control groups. Similarly given the common impact of TBI on EF, this may explain why the TBI group were poorer than the control group.

Implications: There is now more evidence that PM is a common sequelae of childhood severe TBI [START_REF] Ward | Interview study of the effects of paediatric traumatic brain injury on memory[END_REF][START_REF] Krasny-Pacini | Ecological prospective memory assessment in children with acquired brain injury using the Children's Cooking Task[END_REF][START_REF] Mccauley | Incentive effects on event-based prospective memory performance in children and adolescents with traumatic brain injury[END_REF] , that can persist over time. When assessing sequelae post TBI, the evaluation should include an assessment of PM in addition to classical episodic memory assessment, especially in legal expertise in order not to underestimate memory impairment in daily life. When PM is found impaired, interventions should aim at using high motivation tasks/incentives for most essential PM tasks of daily life as motivation may be an enhancer of PM performance [START_REF] Mccauley | Incentive effects on event-based prospective memory performance in children and adolescents with traumatic brain injury[END_REF] . However other methods should also be considered (e.g. pager, alarms), given the frequent overall PM impairment.

Conclusions: Across the large age span of 7-22, individuals with severe TBI systematically recruited for a longitudinal prospective follow-up showed significantly poorer PM seven years' post-injury than matched controls in two PM tasks. The ecological task consisting of sending a letter on a rainy day, showed significant differences both in its PM component (sending the letter irrespective of adequate content), and the overall task (sending the letter containing all adequate information). Individuals with TBI had more difficulty performing a simple PM task while identifying facial emotions. Performance on a high motivation PM task did not differ from controls. High motivation conditions may enhance PM. More ecological tests of PM should be designed and administered to assess PM after childhood severe TBI.