Zayed Alsayed

Guillaume Bresson

Fawzi Nashashibi

Anne Verroust-Blondet

PML-SLAM: a solution for localization in large-scale urban environments

Localization is considered a key factor for autonomous cars. In this paper, we present a complete Simultaneous Localization And Mapping (SLAM) solution. This algorithm is based on probabilistic maximum likelihood framework using grid maps (the map is simply presented as a grid of occupancy probabilities). The solution mainly solve three renowned localization problems (1. localization in unknown environment, 2. localization in a pre-mapped environment and 3. recovering the localization of the vehicle). Memory issues caused by the open size of outdoor environment are solved using an optimized management strategy that we propose. This strategy allows us to navigate smoothly while saving and loading probabilities-grid submaps into/from a hard-disc in a transparent way. We present the results of our solution using our own experimental dataset as well as the KITTI dataset.

I. INTRODUCTION

One of the key aspects induced by a self-driving car is the ability to localize itself in its environment. This perception task, essential to every navigation system, is crucial for autonomous driving as it is the basis on which trajectory planning and command laws will rely. This topic has therefore received a great amount of attention from the scientific community. However, it is a difficult goal to achieve as such a solution must be able to operate in large environments, provide accurate results in real time and be able to find the vehicle's location in a previously explored environment when necessary.

Simultaneous Localization And Mapping (SLAM) techniques play a central role in making cars truly autonomous. The idea behind SLAM is, for a vehicle, to be able to incrementally build a map of its surroundings while estimating its pose (position and orientation) inside this map. An interesting, but often neglected aspect is that, once a map has been built, it can then be enriched or/and used for re-localization purposes if a vehicle re-enters a previously mapped area.

In order to work in a fully autonomous car (embedding other detection and safety algorithms), the requirements of each algorithm should be optimized. This includes localization system, as well as the architecture surrounding it, they must be designed with this constraint in mind and should not limit the size of the environment in which the vehicle is moving.

We propose here a complete SLAM solution, called PML-SLAM for Probabilistic Maximum Likelihood -SLAM, based on horizontal laser sensors. PML-SLAM is well-suited to real-life applications, it's designed to perform in low re-source requirements, both in terms of computational time and memory consumption management. PML-SLAM has the particularity to be designed around a solid map management strategy in order to allow navigation to be smooth while save/load/update/enrich map of any size environment. Based on this map management strategy three of the most popular problems related to localization are solved. 1. localization in unknown environment, where our solution offers the possibility to build a consistent map. 2. localization in known environment, using a pre-built map which offers the possibility to define vehicle's trajectory. 3. the kidnapped robot problem, in this case the vehicle can retrieve precisely its location and orientation after kidnapping without any priori knowledge about its new position. In these three cases the environment map can be updated in real-time even when the vehicle route from a previously explored environment or after kidnapping.

The paper is organized as follows: Section II presents the state of the art regarding SLAM algorithms. Then, Section III introduces the PML-SLAM algorithm with it's different modules that have been developed. The architecture as well as the underlying mathematical framework are presented. Finally, Section IV deals with the experiments and the results obtained.

II. STATE OF THE ART

Early work on the SLAM problem led to the foundation of a probabilistic framework [START_REF] Durrant-Whyte | Simultaneous Localization and Mapping: Part I[END_REF][2] [START_REF] Thrun | A Real-Time Algorithm for Mobile Robot Mapping With Applications to Multi-Robot and 3D Mapping[END_REF]. Even though the SLAM problem can now be considered as being theoretically solved [START_REF] Durrant-Whyte | Simultaneous Localization and Mapping: Part I[END_REF], many issues have emerged in practical implementations.

The map representation has a great impact on which environments could be tackled and the performance of the algorithm. Three main map representations can be found in the literature: landmark-based maps, grid maps and rawmeasurement maps. The first one relies on the environment's specific characteristics to extract significant landmarks (points, edges, etc.) [START_REF] Davison | MonoSLAM: Real-time Single Camera SLAM[END_REF]. One strong constraint is to be able to have a sufficiently high number of landmarks in the scene to compute a proper localization. Grid maps divide the environment into cells. Each cell is associated to an occupancy probability [START_REF] Grisetti | Improved techniques for grid mapping with rao-blackwellized particle filters[END_REF]. Consequently, these algorithms depend on the geometric structure of the environment. Last, approaches based on rawmeasurement maps directly integrate raw sensor data in order to have the most accurate map possible. The direct consequence is that these maps can be difficult to store and can require a high computational cost for processing [START_REF] Vu | Vehicle Perception: Localization, Mapping with Detection, Classification and Tracking of Moving Objects[END_REF].

The sensors used (information type), the environment's characteristics (information extraction) as well as the estimation process (information processing) should guide the choice of a map representation. Regarding estimation processes, the initial solutions to address the SLAM problem were based on Extented Kalman Filters [START_REF] Durrant-Whyte | Simultaneous Localization and Mapping: Part I[END_REF] and Particle Filters [3][7]. Optimization methods, such as Bundle Adjustment [START_REF] Mouragnon | Real Time Localization and 3D Reconstruction[END_REF], are now computationally viable and provide interesting results. These approaches are better suited to a landmark-based representation. Conversely, other solutions based on Likelihood Maximization [START_REF] Xie | A real-time robust global localization for autonomous mobile robots in large environments[END_REF][6] are suited to grid maps. Some implementations also consider a raw-measurement map in addition. Landmark maps are usually built with vision and laser sensors whereas grid maps rely mostly on lasers.

The computational performance of SLAM algorithms is also a major criterion when real-life applications are targeted. This aspect has been considered in many recent SLAM algorithms such as [START_REF] Hamzaoui | A fast scan matching for grid-based laser SLAM using streaming SIMD extensions[END_REF] and [START_REF]tinySLAM: A SLAM algorithm in less than 200 lines C-language program[END_REF] [START_REF] Levinson | Map-Based Precision Vehicle Localization in Urban Environments[END_REF]. Still in the objective of making vehicles autonomous, being able to solve the kidnapped robot problem (localize the vehicle in a map given a set of observations) is important [START_REF] Se | Global Localization using distinctive visual features[END_REF]. Indeed, the vehicle should be able to use a reference map when the environment has already been mapped, as it increases the relative localization accuracy and allows the map to be enriched [START_REF] Mouragnon | Real Time Localization and 3D Reconstruction[END_REF].

In this paper, we propose a solution to deal with large-scale environments using a standard computer. Our solution is based on laser sensors data only which require less processing for data extraction than cameras. This choice led us to a grid-based representation due to its lightness. Around these choices, we built an estimation process based on likelihood maximization.

III. PML-SLAM

A. Probabilistic SLAM

The general formulation of the SLAM problem is the estimation of the joint probability posterior of the robot pose and the environment map simultaneously over all previous sensor observations and command inputs:

P (x t , M t |z 0:t , u 0:t , x 0 ) (1)
where x t is the position and orientation of the robot (x, y, α) at time t, M t is the environment map at time t, z 0:t = {z 0 , z 1 , ..., z t } is the set of all sensor observations up to time t, u 0:t = {u 0 , u 1 , ..., u t } is the set of robot motion measurements up to time t and x 0 is the initial position and orientation of the vehicle.

SLAM algorithms mainly consist of a two-step recursive process:

• time update (prediction): which is a prediction of the robot state and the joint map, based on previous observations as well as command inputs.

P (x t , M t |z 0:t-1 , u 0:t , x 0 ) = P (x t |x t-1 , u t ) ×P (x t-1 , M t-1 |z 0:t-1 , u 0:t-1 , x 0 )dx t-1 (2)
• measurement update (correction): which is a correction of the state (vehicle and map) based on the current observation.

P (x t , M t |z 0:t , u 0:t , x 0 ) = P (z t |x t , M t ) × P (x t , M t |z 0:t-1 , u 0:t , x 0 ) P (z t |z 0:t-1 , u 0:t ) (3)
B. General Overview PML-SLAM for Probabilistic Maximum Likelihood -SLAM, is a complete SLAM framework for autonomous cars based on information provided by laser sensors. PML-SLAM offers two different operating modes (localization with or without an a prior map of the environment). It is based on a complete framework to manage large-scale maps (there is no limitation on the environment size and the map can be gradually expanded and/or updated in real-time).

The general flowchart of the PML-SLAM approach is given in Figure 1. It shows the architecture of the implementation which is basically built around three main blocks (dark green boxes). Different module illustrated on this flowchart will be detailed in the rest of this section.

C. Overview on Data Representation

The map is expressed through a grid of probability cells with a parameterizable resolution, which makes it possible to control the discretization level of the environment. We also take advantage of this discretization to maintain maps at different resolutions to perform localization recovery faster (cf.

III-H). The cell size, in the highest resolution, is set according to the laser sensor characteristics to obtain the best localization accuracy possible. An example of such a map is shown in Figure 2. The map, at resolution level r and at time t, is denoted as M t,L=r . It is the fusion of all submaps

{M 1 , M 2 , • • • M t } L=r , where the submap M t
L=r is the environment seen at time t. The different resolution level are used to solve kidnapped robot problems (more details in Section III-H).

M t

L=r is the collection of cells {m 1 , m 2 , • • • m N } with N being the maximum number of cells in the submap. Each cell corresponds to an occupancy probability [0, 1] where a cell occupancy probability close to 0 means that it is likely to be free. Conversely, a probability close to 1 means that a cell is likely to be occupied.

Figure 2(b) shows the probability grid map of the real environment presented in Figure 2(a). The dark cells are those with a high occupancy probability and the light cells represent the ones that are likely to be free. The green points represent the current observation data.

D. Motion Model

The Motion Model computes the pose prediction based on a vehicle model. It takes into account the vehicle's previous pose x t-1 and the vehicle's speed v t-1 (linear and angular) to provide a list of position and orientation candidates

X t = {x 1,t , x 2,t , • • • x n,t }
where the vehicle can be located.

Here, we are using a Constant Velocity model to describe the behavior of the vehicle's motion. Indeed, as the time interval δt between two consecutive laser scans is small (≈ 60 milliseconds), we assume that the variation in the vehicle's speed δv t is also small. Our prediction model is expressed as:

∆x t = ∆x t-1 + δt × δv t (4)
x t|t-1 = x t-1|t-1 + ∆x t (5)

E. Initial velocity finder

The role of the Initial velocity finder module is to deal with scenarios which begin when the vehicle is already moving. With the Constant Velocity model presented previously, these cases can lead to wrong estimates at the beginning of such a trajectory.

The module computes a rough estimation of the movement by minimizing the distance (translation and rotation) between the two first laser scans z 0 = {z 0 0 ,

z 1 0 • • • z n-1 0 } and z 1 = {z 0 1 , z 1 1 • • • z n-1 1
} where z i j is the i th 2D point in the j th laser scan composed of n points. This first estimate is estimated as follows (dist is the function computing the Euclidean distance between two points):

∆x 1 = 1 n n-1 i=0 dist(z i 0 , z i 1 ) (6)
v 1 = ∆x 1 /δt (0,1) (7)
The values computed (∆x 1 , v 1 ) can then be transmitted to the Motion Module presented above.

The search space is limited by the maximum distance the vehicle can travel during time between the first two observations (z 0 , z 1 ). Figure 3 shows the distribution of candidates all around to cover the possible area. Each square represents one candidate on a low resolution map to accelerate the search process.

F. Maximum Likelihood Matching

The Maximum Likelihood Matching module corresponds to the correction process in SLAM algorithms (see Equation 3)). It takes into account the new measurement of the environment z t in order to refine the state estimation x t|t-1 proposed in the output of the Motion Model.

This module performs a maximization of similarity between the current laser scan z t and the map M t-1 from the previous time using the list of candidate poses X t provided by the motion model:

x t|t = arg max {P (z t |x t|t-1 , M t-1 ) ×P (x t|t-1 |x t-1|t-1 , u t )} (8)
P (z t |x t|t-1 , M t-1 ) ∝ N cell i=1 P (m i t-1 ) (9)
where m i t-1 is occupied. In other words, this step consists in finding the best position and orientation x t|t of the vehicle by fitting the observation z t on the map M t-1 .

After performing the correction step, we update the system joint state (x t , M t ) by merging the new observation in the map:

M t = M t-1 ∪ M t ( 10
)
This module is completed by a feedback process to adapt the matching parameters depending on the matching score. The threshold for cell selection (which is based on their probability) is adjusted to maximize the number of matched cells in the next SLAM update. If the matching score is too low, the feedback triggers a reset of the system in order to re-localize the vehicle.

G. Map Manager

This map manager is the key feature of our work. The map is represented by a high resolution occupancy grid and we aim at performing SLAM in large-scale environments. This is not compatible as maps grow in size and we have limited memory resources. The Map Manager module provides a robust management of our limited resources. The goal is to be able to have high resolution maps for accurate matching without putting any limitation on the environment size.

Tiles of the exchange buffer (loaded from hard-disk) Tiles of the current local map (later saved on hard-disk)

Common tiles between buffers (conserved on memory)

Fig. 4. Map buffers to deal with large-scale environments

Our technique consists in managing the map between the limited Random Access Memory (RAM) and the hard-diskdrive (HDD) where space is not an issue. First, the map is divided into small areas which we call tiles. Then, we only keep in the memory a current local part of the global map which is still big enough to navigate seamlessly from one local map to another. The other tiles are saved on the harddisk. Tiles are then loaded and unloaded depending on the pose of the vehicle so as always being able to match current observations. An illustration of this map management strategy is given in Figure 4. The grey square is the current local map buffer, containing a grid of 16 tiles, which is actually loaded in the RAM. The other squares (blue, green and red) are candidate configurations to which the local buffer may next move, depending on the vehicle's direction. The arrows of same color shows the next configuration to be adopted.

Furthermore, the key ingredient behind exchanging buffers seamlessly between RAM and HDD in real-time is by compressing probability grid submaps. The buffer (grid of probability) is seen as an image buffer. This allows us to use a image compression techniques. Here we are using a compression technique in PNG which accelerates files saving and loading operations as well as reducing the space required on the harddrive.

H. Pyramidal Map Matching

The Pyramidal Map Matching module is able to solve the kidnapped robot and relocalization in pre-mapped environments (with what is called a reference map) problems. The idea is to perform an extensive search of the current observation over the reference map to find the robot's pose with relation to this map. As this process can be unreliable and time consuming, the reference map is expressed at different resolution levels. At low resolutions, finding a correspondence is fast but not accurate. By going through the different levels, we are able to refine the pose quickly, by testing only a few pose candidates.

This module uses a similar strategy than proposed by Xie et al. [START_REF] Xie | A real-time robust global localization for autonomous mobile robots in large environments[END_REF]. The main difference comes from the map representation. Instead of a raw-measurement map, we take advantage of our Map Manager module to directly use a grid representation. It has the advantage to allow a faster and constant loading time compared to [START_REF] Xie | A real-time robust global localization for autonomous mobile robots in large environments[END_REF] where the time will vary according to the map size.

As the search can be long without prior knowledge (GPS position for instance), the vehicle continues to perform SLAM while the Pyramid Map Matching module works as a background task. Once the pose on the reference map is found, the current state is brought back into the frame of the reference map.

IV. EXPERIMENTS

The first experiments were carried out using the KITTI odometry database [START_REF] Geiger | Vision meets Robotics: The KITTI Dataset[END_REF] which provides datasets (with Velodyne, cameras and a ground truth) in various environments for performance evaluation. In order to adapt the data to our implementation inputs, we cut the original Velodyne data to simulate an ordinary single-layer LiDAR scanner configuration (360°field of view with a 0.25°resolution).

In order to test the relocalization performance of PML-SLAM, we also built our own datasets thanks to a vehicle equipped with 5 laser scanners covering a 360°field of view with a 0.25°resolution. Only one layer was used to obtain the results presented in this article. An IMU was fused with a RTK-GPS to provide a ground truth.

All the experiments took place in urban and peri-urban environments in real conditions (moving obstacles were present). All tests were performed on a computer equipped with a Core-i7 running at 2.9 GHz. For all the results presented below, PML-SLAM took on average 2 ms to process a scan layer.

A. SLAM in unknown environments

In this experiment, we used the sequence "05" from the KITTI odometry dataset, collected in a residential environment. We performed SLAM without any prior knowledge on the environment.

At the beginning of the trajectory, a map of 16 tiles (resolution 10 pixels/meter) were initialized. During the whole trajectory, a total of 32 tiles were created and saved on the hard disk, covering a 720, 000 m 2 surface. The map produced takes up 981 KB on the hard disk. The computed trajectory is shown in Figure 5. The errors in displacement and heading at each iteration are illustrated in the Figure 6. As we can see, the errors in displacement are bounded by ± 5 cm, while the errors in heading are limited to ± 0.3°.

Path estimated by SLAM is close to the ground truth. The deviation throughout the trajectory in distance and in heading are shown in Figure 7. We can see that after 2, 204 meters the deviation in distance is about 6 meters with 0.1°of deviation in heading.

B. Recovering from kidnapping

In this experiment we used a dataset which we collected in a city using our platforms. The aim of this test is to illustrate The vehicle starts to build a map (black path), then the vehicle is kidnapped and put in another location (diamond on the trajectory). As a consequence, the vehicle starts a new local SLAM process (red path) whose computed trajectory takes a similar shape to the previous route. During this time, the position is provided in a local reference. The matching process then finds the vehicle new position on the pre-built map (recover from kidnapping). The recovery moment is represented by the dashed green lines. The vehicle's positions provided from now on are given on the global map. The map is further enriched during the common path (in dark green).

Once the vehicle enters areas not previously mapped (light green), the vehicle continues to map and localize itself.

The map built at the beginning of the experiment served as a recovering-from-kidnapping map, and covered 360, 000 m 2 . The localization precision after recovering was ± 5 cm.

The operation of recovering took about 27 seconds in this example. However, this time depends on the random selection of matching candidates and is thus variable. Nevertheless, while searching for its position, the vehicle is still localizing itself with the SLAM process. The final map built takes up 508 KB on the hard disk and it should cover 517, 500 m 2 of surface.

C. Memory consumption

The limitation in resources is an important issue treated in this paper. Figure 9 shows a comparison in terms of memory consumption regarding the maximal size of the area covered by the SLAM system with and without the Map Manager module presented in this article (see Section III-G). We can see on the graphic that memory required by a SLAM system without Map Management increases quadratically in function of the environment size. In contrast the memory required by a SLAM with a Map Manager is constant regardless the environment size. In realistic scenarios of autonomous driving we can't predefine the map size, a vehicle need to have it's freedom to navigate.

V. CONCLUSION

We have presented a complete SLAM algorithm, called PML-SLAM. The proposed solution is based on the probabilistic maximum likelihood framework coupled with a grid representation. Its integration inside a complete architecture allows to use any previously built map if available. A map matching algorithm, based on a pyramidal search with multiresolution map, is able to re-localize the vehicle inside a map given an observation, thus solving the kidnapped robot case. Our approach has been designed with real-life applications in mind and is consequently light both in terms of memory requirements and processing time. The map is smartly managed to be loaded and unloaded on the hard drive when needed thus allowing to work in large-scale environments.

We have validated PML-SLAM with several experiments over different scenarios: SLAM localization, relocalization and navigation inside an existing map. The results show that our approach is viable for real-time urban localization without restrictions on the size of the environment.

In future work, we plan to fuse several localization algorithms within a supervision layer in order to increase robustness and localization accuracy.

Fig. 1 .

 1 Fig. 1. General flowchart of the PML-SLAM algorithm

  Fig. 2. Map from Plaisir-France

Fig. 3 .

 3 Fig. 3. Search area around the vehicle to compute its movement.

Fig. 5 .

 5 Fig. 5. Vehicle paths from the Kitti odometry dataset, the path estimated by PML-SLAM and the ground truth path.

Fig. 6 .

 6 Fig. 6. Errors in heading and displacement by iteration during the test.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Deviation from real path in distance and heading along journey.

Fig. 9 .

 9 Fig. 9. Memory consumption regarding the area covered by SLAM


Cao-Tri Do

Ahlame Douzal-Chouakria

Sylvain Marié

Michèle Rombaut

MULTIPLE METRIC LEARNING FOR LARGE MARGIN kNN CLASSIFICATION OF TIME SERIES

Keywords: Multiple metric learning, Time series, kNN, Classification

Time series are complex data objects, they may present noise, varying delays or involve several temporal granularities. To classify time series, promising solutions refer to the combination of multiple basic metrics to compare time series according to several characteristics. This work proposes a new framework to learn a combination of multiple metrics for a robust kNN classifier. By introducing the concept of pairwise space, the combination function is learned in this new space through a "large margin" optimization process. We apply it to compare time series on both their values and behaviors. The efficiency of the learned metric is compared to the major alternative metrics on large public datasets.

INTRODUCTION

Nowadays, time series are present in various fields, particularly in emerging applications such as sensor networks, smart buildings, social media networks or Internet of Things [START_REF] Yin | Clustering distributed time series in sensor networks[END_REF][START_REF] Najmeddine | Mesures de similarité pour l'aide à l'analyse des données énergétiques de bâtiments[END_REF][START_REF] Nguyen | Predicting collective sentiment dynamics from time-series social media[END_REF][START_REF] Díaz | Big data on the internet of things: An example for the E-health[END_REF]. Due to their temporal nature, time series constitute complex data to analyze by standard machine learning approaches [START_REF] Fu | A review on time series data mining[END_REF].

To classify such challenging data, one may require advanced metrics bringing closer time series of identical classes while separating those of different classes. For this purpose, some propositions refer to embedding time series into new descriptive spaces such as spectral or tensor representations [START_REF] Caiado | A periodogrambased metric for time series classification[END_REF][START_REF] Papadimitriou | Streaming pattern discovery in multiple time-series[END_REF] or by using new dissimilarity metrics and temporal kernels [START_REF] Douzal-Chouakria | A random-periods model for the comparison of a metrics efficiency to classify cell-cycle expressed genes[END_REF][START_REF] Cuturi | A Kernel for Time Series Based on Global Alignments[END_REF][START_REF] Douzal-Chouakria | Adaptive dissimilarity index for measuring time series proximity[END_REF][START_REF] Frambourg | Learning Multiple Temporal Matching for Time Series Classification[END_REF]. As opposed to static data, temporal data may be compared not only on their values but also on their dynamics [START_REF] Benesty | Pearson correlation coefficient[END_REF][START_REF] Douzal-Chouakria | Classification trees for time series[END_REF]. The most frequently used value-based metrics are the Euclidean distance [START_REF] Ding | Querying and Mining of Time Series Data : Experimental Comparison of Representations and Distance Measures[END_REF] and the Dynamic Time Warping dtw to cope with delays [START_REF] Cuturi | A Kernel for Time Series Based on Global Alignments[END_REF][START_REF] Ding | Querying and Mining of Time Series Data : Experimental Comparison of Representations and Distance Measures[END_REF][START_REF] Sakoe | Dynamic Programming Algorithm Optimization for Spoken Word Recognition[END_REF].

Recent approaches show the benefit of combining multiple temporal metrics to classify challenging time series [START_REF] Benesty | Pearson correlation coefficient[END_REF][START_REF] Douzal-Chouakria | Classification trees for time series[END_REF]. Such metrics are generally built as a combination of several behavior-and values-based metrics through a combination function set a priori, regardless of the analysis task [START_REF] Douzal-Chouakria | Classification trees for time series[END_REF]. In the same spirit than the metric learning approach introduced in Weinberger & Saul [START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF], we propose a new approach to learn a combined metric for a robust kNN classifier. The main idea is first to embed pairs of time series in a space whose dimensions are basic temporal metrics, and then to learn the metric combination function through a "large margin" optimization process in this space. The rest of the paper is organized as follows. Section 2 recalls briefly the major metrics for time series. In Section 3, we present the proposed multiple metric learning approach. Finally, Section 4 presents the experiments conducted and discusses the results obtained.

TIME SERIES METRICS

Let x i = (x i1 , ..., x iT ) and x j = (x j1 , ..., x jT ) be two time series of time length T . Generally, time series are asynchronous (i.e. varying delays), they need to be aligned before any comparison or analysis process. An alignment

π ij of length |π ij | = M ij (with T ≤ M ij ≤ 2T -1)
between two time series x i and x j is defined as the sequence of M ij index pairs (π i , π j ) of aligned elements in x i and x j :

π ij = ((π i (1), π j (1)), ..., (π i (t), π j (t)), ..., (π i (M ij ), π j (M ij )))
where the applications π i and π j defined from {1, ..., M ij } to {1, ..., T } obey the following boundary and monotocity conditions:

1 = π i (1) ≤ π i (2) ≤ ... ≤ π i (M ij ) = T 1 = π j (1) ≤ π j (2) ≤ ... ≤ π j (M ij ) = T and ∀t ∈ {1, ..., M ij }, π i (t + 1) ≤ π i (t) + 1 and π j (t + 1) ≤ π j (t) + 1 (π i (t + 1) -π i (t)) + (π j (t + 1) -π j (t)) ≥ 1
Let A be the set of all possible alignments. To find an optimal alignment, the Dynamic Time Warping algorithm and its variants have been proposed [START_REF] Fu | A review on time series data mining[END_REF][START_REF] Sakoe | Dynamic Programming Algorithm Optimization for Spoken Word Recognition[END_REF]. Given a cost function C (e.g. a dissimilarity measure), it computes the optimal alignment π * ij such that:

π * ij = arg min πij ∈A   Mij t=1 C(x iπi(t) , x jπj (t) )   (1)
In the following, we consider the Euclidean distance as the cost function C. We suppose that the best alignment π * ij is found for each pair and note for simplification purpose (x i , x j ) = ((x i1 , ..., x it , ..., x iMij ), (x j1 , ..., x jt , ..., x jMij )) the time series after being aligned according to π * ij . Time series metrics fall at least within two main categories. The first one concerns value-based metrics (d V ), where time series are compared according to their values regardless of their behaviors. Among these metrics are the Euclidean distance (D E ), the Minkowski distance and the Mahalanobis distance [START_REF] Fu | A review on time series data mining[END_REF].

The second category of metrics aims to compare time series based on their behavior regardless of the range of their values. By similar behavior, it is generally meant that for all periods [t, t ], the two time series increase or decrease simultaneously with the same growth rate in absolute value. On the contrary, they are said of opposite behavior if for all [t, t ], if one time series increases, the other one decreases (and vice-versa) with the same growth rate. Finally, time series are considered of different behaviors if they are not similar, nor opposite. Many applications refer to the Pearson correlation [START_REF] Benesty | Pearson correlation coefficient[END_REF][START_REF] Abraham | An Integrated Framework for Simultaneous Classification and Regression of Time-Series Data[END_REF] for behavior comparison. A generalization of the Pearson correlation has been introduced by Douzal & al. in [START_REF] Douzal-Chouakria | Classification trees for time series[END_REF]:

Cort r (x i , x j ) = t,t (xit-x it )(xjt-x jt ) t,t (xit-x it ) 2 t,t (xjt-x jt ) 2 (2) where |t -t | ≤ r, r ∈ [1, ..., M ij -1]
being a parameter that can be learned or fixed a priori. For r = M ij -1, Eq. 2 leads to the Pearson correlation. As Cort r is a similarity measure, it is transformed into a dissimilarity measure:

d Br (x i , x j ) = 1 2 (1 -Cort r (x i , x j )
). Some applications show the benefit of involving both behavior and value (d V ) components through a combination function. A sigmoid combination function is proposed in [START_REF] Douzal-Chouakria | A random-periods model for the comparison of a metrics efficiency to classify cell-cycle expressed genes[END_REF][START_REF] Douzal-Chouakria | Classification trees for time series[END_REF]:

D Sig (x i , x j ) = 2d V (x i ,x j ) 1+exp(αCort r (x i ,x j )) (3)
More generally, value (d V ) and behavior (d Br ) dissimilarity metrics may be combined through a linear or geometric function: α defines the value/behavior trade-off and can be learned through a grid search procedure. Note that these combination functions suffer from some limitations: they are fixed a priori, defined regardless of the analysis task, and are limited to two basic metrics. Our aim in this paper is to propose a new framework to learn a combined temporal metric D that combines several basic metrics for a robust kNN. In the next section, we first recall the metric learning framework proposed by Weinberger & Sault [START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF]. Then, we detail how this work is extended to multiple metric learning and applied to temporal data.

D Lin (x i , x j ) = αd Br (x i , x j ) + (1 -α)d V (x i , x j ) (4) D Geom (x i , x j ) = (d Br (x i , x j )) α (d V (x i , x j )) 1-α (5)

MULTIPLE METRIC LEARNING FOR A LARGE MARGIN kNN

Metric learning for a robust kNN classifier

Let X = {x i , y i } N i=1 be a set of N static vector samples, x i ∈ R p , p being the number of descriptive features and y i the class labels. Weinberger & Sault proposed in [START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF] an approach to learn a dissimilarity metric D for a large margin kNN. It is based on two intuitions: first, each training sample x i should have the same label y i as its k nearest neighbors ; second, training samples with different labels should be widely separated. For this, they introduced the concept of target and imposters for each training sample x i . Target neighbors of x i , noted j i, are the k closest x j of the same class (y j = y i ), while imposters of x i , denoted, l i, are the x l of different class (y l = y i ) that invade the perimeter defined by the farthest targets of x i . The target neighborhood is defined with respect to an initial metric ; the learned metric D pulls the targets and pushes the imposters as shown in Figure 1.

In the following, we extend this framework to learn a combined metric for a large margin kNN.

Metric combination and pairwise space

Let d 1 , ..., d h ..., d p be p given dissimilarity metrics that allow to compare samples. The computation of a metric always takes into account a pair of samples. We introduce a new space representation referred as the pairwise space. In this new space, illustrated in Figure 2, a vector x ij represents a pair of samples (x i , x j ) described by the p basics metrics d h :

x ij = [d 1 (x i , x j ), ..., d p (x i , x j )] T . If x ij = 0 then x j is identical to x i according to all metrics d h .
A combination function D of the metrics d h can be seen as a function in this space. We propose in the following to use a linear combination of d h : D w (x i , x j ) = h w h .d h (x i , x j ). Its pairwise notation is:

D w (x ij ) = w T .x ij (6)

Multiple metric learning in the pairwise space for a large margin kNN

The Weinberger & Sault framework can be used within the pairwise space to learn the combined metric D w . The main steps of the proposed approach, detailed hereafter, can be summarized as follows:

1. Embed each pair (x i , x j ) into the pairwise space R p as explained in Section 3.2.

2. Scale the data within the pairwise space.

3. Define for each x i its targets.

4. Scale the neighborhood of each x i .

5. Learn the combined metric D w .

Data scaling. This operation is performed to scale the data within the pairwise space and ensure comparable ranges for the p basic metrics d h . In our experiment, we use dissimilarity measures with values in [0; +∞[. Therefore, we propose to Z-normalize their log distributions.

Target set. For each x i , we define its target neighbors as the k nearest neighbors x j (j i) of the same class according to an initial metric. In this paper, we choose a L2-norm of the pairwise space as an initial metric ( h d 2 h ). Other metrics could be chosen. We emphasize that target neighbors are fixed a priori (at the first step) and do not change during the learning process.

Neighborhood scaling. In real datasets, local neighborhoods can have very different scales. To make the target neighborhood spreads comparable, we propose for each x i to scale its neighborhood vectors x ij such that the L2-norm of the farthest target is 1.

Learning the combined metric D w . Let {x ij , y ij } N i,j=1 be the training set with y ij = -1 if y j = y i and +1 otherwise. Learning D w for a large margin kNN classifier can be formalized as the following optimization problem:

min w,ξ i,j i D w (x ij ) pull + C i,j i,l 1 + y il 2 .ξ ijl push s.t. ∀j i, y l = y i , D w (x il ) -D w (x ij ) ≥ 1 -ξ ijl ξ ijl ≥ 0 w h > 0∀h = 1...p (7)
Note that the "pull" term

j i D w (x ij ) = j i w T .x ij = N.k.w T .
x ij is a L1-Mahalanobis norm weighted by the average target sample. Therefore, it behaves like a L1norm in the optimization problem. The problem is very similar to a C-SVM classification problem. When C is infinite, we have a "strict" problem: the solver will try to find a direction in the pairwise space for which there is both no imposters invading the target spaces of each x i , and a maximum margin 1 ||w||2 .

kNN classification of a new sample x test . Let x test,i (i = 1, ..., N ) be the induced vectors in the pairwise space. These vectors are normalized according to the parameters retained at the Data Scaling step. x test is classified with the kNN using the learned metric D w .

EXPERIMENTATION

In this section, we compare kNN classifier performances for several temporal metrics on reference time series datasets [START_REF] Keogh | The UCR Time Series Classification/Clustering Homepage[END_REF][START_REF] Bache | UCI Machine Learning Repository[END_REF][START_REF]LIG-AMA Machine Learning Datasets Repository[END_REF] described in Table 1. To compare our results with the reference results in [START_REF] Ding | Querying and Mining of Time Series Data : Experimental Comparison of Representations and Distance Measures[END_REF][START_REF] Keogh | The UCR Time Series Classification/Clustering Homepage[END_REF], the experiments are conducted with the same protocols as in

V (x i , x j ) = D E (x i , x j ) and d Br = 1 2 (1 -Cort r (x i , x j ))
. Then, we consider linear (D Lin , Eq. 4), geometric (D Geom , Eq. 5) and sigmoid (D Sig , Eq. 3) combination functions. For D Lin and D Geom , the dissimilarity metrics are Z-normalized on their log distributions as explained in Section 3.3. Finally, we learn the combined metric D w according to the procedure described in 3.3. First, two basic metrics are considered in D 2 (d V and d Br ). Second, eight basic metrics are used for D 8 : d 1 = d V , d 2 , ..., d 8 = d Br based on Cort r for r = 1, 0.05T, 0.1T, 0.2T, 0.25T, T, r * . Finally, in D All , we consider d V and d Br based on all orders of Cort r . GNU Linear Programming Kit (GLPK Reference Manual [START_REF] Makhorin | GLPK, GNU Linear Programming Kit[END_REF]) is used to solve the optimization problem in Eq. 7 to find D 2 , D 8 , D All .

Most of these metrics have parameters. We learn the optimal parameter values by minimizing a leave-one out cross-validation criterion. As the training dataset sizes are small, we propose a hierarchical error criterion:

1. Minimize the kNN error rate 2. Minimize dintra dinter if several parameter values obtain the minimum kNN error.

where d intra and d inter stands respectively to the mean of all intraclass and interclass distances according to the metric at hand. Table 2 gives the range of the grid search considered for the parameters.

Two experiments are conducted: first, the raw series are used (Table 3) ; then, time series are aligned according to the optimal alignment found by the dtw algorithm 1 with an Euclidean distance as the cost function (Table 4). For all reported results, the best one is indexed with a star and the ones significantly similar from the best one (Z-test at 10% risk) are in bold [START_REF] Dietterich | Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms[END_REF].

From Table 3, we can see that value d V or behavior d Br metrics alone performs better one from the other depending on the dataset. One basic metric does not always reach the best performance. There is a need to combine both of them into one metric. D 2 always reaches the best performance of d V and d Br or is equivalent to the best one on all datasets. The new approach allows to extend combination functions to many metrics without having to cope with additional parameters in grid search (D 8 , D All ). Adding metrics allows to outperform the two basics metrics (SonyAIBO). However, using a large number of metrics does not always improve the results (Po-werCons, ECG200, SonyAIBOII). This might be caused by the fact that the many d Br are highly correlated: this probably hides the information of d V when the target sets are computed with the initial metric (L2-norm in the pairwise space). Note that for MoteStrain, most combined metrics (a priori and learned) attain poorer performances than the best one of d V and d Br . This may be due to the drastic difference between the training and test sets (Table 1).

From Table 4, we observe that aligning time series through dtw allows to reach better performances than without dtw on some databases (SonyAIBO, GunPoint, UMD), even with basic metrics. In this experiment, D 2 allows to reach the best performances of d V and d Br or is equivalent to the best one on all datasets. This confirms the observations made for Table 3. We note that for D All , the best performances are attained for 7 datasets.

CONCLUSION

In this paper, we proposed a new method to learn a combination of multiple metrics for a robust kNN. It is based on a large margin optimization process in the pairwise space. We tested it on time series data to combine value-and behavior-based metrics, with good results.

For future work, we are looking for some improvements. First, the choice of the initial metric is crucial. It has been set here as the L2-norm of the pairwise space but a different metric could provide better target sets. Otherwise, using an iterative procedure (reusing D w to generate new target sets and learn D w again) could be another solution. Experiments have also shown that including many redundant metrics could affect the learning process. Second, we note that the L1-norm on the "pull" term leads to sparcity. Changing it into a L2-norm could allow for non-sparse solutions and also extend the approach to non-linear metric combination functions thanks to the Kernel trick. The Kernel function will have to be chosen carefully to ensure that D w is monotonous in the pairwise space. Third, the learned metric could be used in other classification algorithms (decision tree, support vector machine, etc.) in its metric form or in a Kernel form. Finally, we could extend this framework to multivariate, regression or clustering problems.

Fig. 1 :

 1 Fig. 1: Pushed and pulled samples in the k = 3 target neighborhood of xi before (left) and after (right) learning. The pushed (vs. pulled) samples are indicated by a white (vs. black) arrows (Weinberger & Sault [16]).

Fig. 2 :

 2 Fig. 2: Example of embedding of time series xi from the temporal space (left) into the pairwise space (right). In this example, a pair of time series (x1, x2) is projected into the pairwise space as a vector x12 described by p = 3 basic metrics: x12 = [d1(x1, x2), d2(x1, x2), d3(x1, x2)] T .

Table 1 :

 1 Dataset description giving the number of classes (Nb. Class), the number of time series for the training (Nb. Train) and the testing (Nb. Test) sets, and the length of each time series (TS length). , 10 -3 , ...,10 8 ]

	Dataset	Nb. Class Nb. Train Nb. Test TS length
	SonyAIBO	2	20	601	70
	MoteStrain	2	20	1252	84
	GunPoint	2	50	150	150
	PowerCons	2	73	292	144
	ECG5Days	2	23	861	136
	ECG200	2	100	100	96
	SonyAIBOII	2	27	953	65
	Coffee	2	28	28	286
	BME	3	48	102	128
	UMD	3	48	92	144
	Method		Parameter Parameter range
	dB r		r	[1, 2, 3, , ..., T ]
	DLin, DGeom	α	[0, 0.1, 0.2, ..., 1]
	DSig		α	[0, 1, 2, ..., 6]
	D2, D8, DAll	C	[10 -4

Table 2 :

 2 Parameter ranges

Keogh &. Al: k is set to 1 ; train and test set are given a priori.

First, we solely consider basic metrics d

Table 3 :

 3 Experimental results (error rate) of 1NN classifier for different metrics without dtw.

	Metrics

Table 4 :

 4 Experimental results (error rate) of 1NN classifier for different metrics with dtw.