Ayoub Tahiri
email: a.tahiri@cacg.fr

Pascale Chiron
email: pascale.chiron@enit.fr

David Ladevèze

Bernard Archimède

David Ladeveze
email: d.ladeveze@cacg.fr

Bernard Archimede
email: bernard.archimede@enit.fr

Une heuristique pour résoudre le problème de flot de coût minimal dans un réseau de transport à fonctions de coût quadratiques, convexes et non-séparables

Keywords: Réseaux de transport, fonctions de coût quadratiques, convexes et non séparables, optimisation globale

Une heuristique pour résoudre le problème de flot de coût minimal dans un réseau de transport à fonctions de coût quadratiques, convexes et non-séparables

Introduction

Contrairement aux fonctions de coût linéaires, les fonctions de coût convexes, évoluant avec le flux, permettent de mieux le distribuer sur un réseau (ex : distribution d'électricité, distribution de la ressource en eau, gestion du portefeuille d'une entreprise…). D'autre part, les contraintes de proportionnalité entre les flux, fréquemment rencontrées (ex : les charges d'activités, modélisation des pertes dans un réseau…), sont modélisables par des fonctions de coût non séparables. Dans ce papier, nous proposons une heuristique pour résoudre le problème de flot de coût minimal dans un réseau de transport à fonctions de coût quadratiques, convexes et non-séparables.

Formulation mathématique du problème

Soit G = (V, E) un réseau de transport, avec 𝑉 l'ensemble des sommets et 𝐸 l'ensemble des arcs. Soit 𝑅⊂𝑉, l'ensemble des sommets de « répartition ». Un sommet de répartition est un sommet qui repartit le flux entrant en 𝑚 flux sortants en fonction des coefficients de répartition {𝛽 1 , 𝛽 2 … , 𝛽 𝑚 }. Cette modélisation peut être simplifiée par une succession de répartition en 2 flux. Les flux ne se déplacent pas instantanément sur un réseau, mais nécessitent un temps de transfert pour parcourir chaque arc ; de plus, ils évoluent dans le temps. On parle alors de flux dynamiques. Pour prendre en compte le temps de transfert, nous utilisons un réseau étendu temporisé. Ainsi, le problème de flot de coût minimal est formulé par les équations 1-5 :

𝑀𝑖𝑛 ∑ 𝐶 𝑒 (∅ 𝑒 ) 𝑒∈𝐸 (1) ∑ ∅ 𝑒 𝑎𝑟𝑐𝑠 𝑠𝑜𝑟𝑡𝑎𝑛𝑡𝑠 𝑑𝑒 𝑙𝑎 = 𝑙𝑎 𝑟𝑒𝑠𝑠𝑜𝑢𝑟𝑐𝑒 𝑑𝑖𝑠𝑝𝑜𝑛𝑖𝑏𝑙𝑒 (2) ∀𝑒 ∈ 𝐸 0 ≤ ∅ 𝑒 ≤ 𝑈 𝑒 (3) ∀𝑛 ∈ 𝑉\{𝑆, 𝑃} ∑ ∅ 𝑒 𝑎𝑟𝑐𝑠 𝑒𝑛𝑡𝑟𝑎𝑛𝑡𝑠 = ∑ ∅ 𝑒 𝑎𝑟𝑐𝑠 𝑠𝑜𝑟𝑡𝑎𝑛𝑡𝑠 (4) ∀𝑛 ∈ 𝑅 ∅ 𝑓𝑙𝑢𝑥 𝑝𝑟𝑖𝑛𝑐𝑖𝑝𝑎𝑙 𝑠𝑜𝑟𝑡𝑎𝑛𝑡 = 𝛽 ∅ 𝑓𝑙𝑢𝑥 𝑒𝑛𝑡𝑟𝑎𝑛𝑡 𝑠𝑢𝑟 𝑛 (5) Et ∅ 𝑓𝑙𝑢𝑥 𝑠𝑒𝑐𝑜𝑛𝑑𝑎𝑖𝑟𝑒 𝑠𝑜𝑟𝑡𝑎𝑛𝑡 = (1 -𝛽) ∅ 𝑓𝑙𝑢𝑥 𝑒𝑛𝑡𝑟𝑎𝑛𝑡 𝑠𝑢𝑟 𝑛

Algorithme d'optimisation

L'algorithme proposé pour trouver la distribution optimale s'appuie sur le théorème de Busacker et Saaty [START_REF] Saaty | Finite Graphs and Networks: an introduction with applications[END_REF] qui stipule qu'une distribution du flux, est optimale si et seulement si le graphe résiduel [START_REF] Evans | Optimization algorithms for networks and graphs[END_REF] ne contient aucun circuit à coût négatif. Un sous graphe est indépendant si toute modification d'un flux sur un de ses arcs n'impacte pas le reste du graphe. Si un circuit passe par un ou plusieurs sommets de répartition alors, il est possible qu'il ne constitue plus un sous-graphe indépendant. En effet, en faisant circuler un flux ∅ sur un circuit contenant un sommet de répartition, une quantité proportionnelle à ce flux peut quitter le circuit. Pour concevoir un sous-système indépendant, les arcs et les sommets qui acheminent cette perte jusqu'au sommet (U) sont intégrés au circuit. Le sous graphe ainsi obtenu est nommé dans la suite multi-circuit. L'algorithme commence par une distribution initiale réalisable, ensuite les deux étapes suivantes sont répétées jusqu'à ce qu'aucun multi-circuit de coût négatif ne soit détecté.  Détecter un multi-circuit à coût négatif en utilisant l'algorithme de Bellman-Ford [START_REF] Fulkerson | Flow networks and combinatorial operations research[END_REF].  Éliminer le multi-circuit en déplaçant une quantité de flux dans le circuit de sorte que le coût du circuit s'annule ou qu'un des arcs soit saturé. L'élimination d'un multi-circuit à coût négatif améliore la fonction objectif tout en gardant la faisabilité de la distribution.

Conclusions et perspectives

Dans cet article nous avons proposé une méthode de recherche du flot à coût minimal sur un réseau étendu temporisé en prenant en compte des fonctions de coût, quadratiques, convexes et non-séparables. Cette méthode a été appliquée, pour protéger contre les inondations, avec succès au système hydraulique composé de 3 barrages de la Haute vilaine. La prise en compte de coefficients de répartition variables est une des perspectives à développer à court terme.

Figure 1 :

 1 Figure 1: Exemple d'un sommet de répartition Pour chaque noeud 𝑛 de 𝑉, la loi de Kirchhoff est vérifiée hormis pour le sommet source (𝑆) et le sommet utilisation (𝑃). A tout arc 𝑒 est associé une capacité 𝑈 𝑒 et une fonction de coût quadratique et convexe : 𝐶 𝑒 (∅ 𝑒 ) = 𝑎 𝑒 ∅ 𝑒 2 + 𝑏 𝑒 ∅ 𝑒 ; 𝑎 𝑒 ≥ 0 avec ∅ 𝑒 le flux présent sur l'arc 𝑒.

Ayoub Tahiri, Pascale Chiron, David Ladevèze, Bernard Archimède. Une heuristique pour résoudre le problème de flot de coût minimal dans un réseau de transport à fonctions de coût quadratiques, convexes et non-séparables. ROADEF 2018, 19ème conférence de la Société Française de Recherche Opérationnelle et Aide à la Décision, Feb 2018, Lorient, France. pp.0. hal-03635481


Ahmad Karfoul

Sahbi Chaibi

Amar Kachenoura

Anca Nica

Abdennaceur Kachouri

Régine Le

Bouquin Jeannès

Fatma Krikid
email: fatma.krikid@etudiant.univ-rennes1.fr

Classification of High Frequency Oscillations in intracranial EEG signals based on coupled time-frequency and image-related features

Keywords: Epilepsy, High Frequency Oscillations, Time frequency representation, Image gradient, Sparsity, Multi-classification, SVM

I. INTRODUCTION

Around 65 million people worldwide are affected by epilepsy which can be characterized by recurrent seizures [1]. However, more than 30% of patients are drug resistant and a surgical resection of the Epileptogenic Zone (EZ) stands for the best therapeutic solution to reduce the occurrence of such seizures [START_REF] Jacobs | High frequency oscillations (HFOs) in clinical epilepsy[END_REF]. The success of resection surgery mainly depends on the localization of the EZ. The epilepsy can be diagnosed through different neuroimaging modalities (functional and structural) [START_REF] Shoeibi | Applications of epileptic seizures detection in neuroimaging modalities using deep learning techniques: methods, challenges, and future works[END_REF]. In this context, recent studies have proposed various algorithms [START_REF] Shoeibi | A comprehensive comparison of handcrafted features and convolutional autoencoders for epileptic seizures detection in EEG signals[END_REF], [START_REF] Shoeibi | Detection of epileptic seizures on EEG signals using ANFIS classifier, autoencoders and fuzzy entropies[END_REF] to diagnose epileptic seizures. More recently, High Frequency Oscillations (HFOs) have gained particular attention as promising biomarkers of the EZ [START_REF] Jacobs | High frequency oscillations (HFOs) in clinical epilepsy[END_REF], [START_REF] Zijlmans | High-frequency oscillations as a new biomarker in epilepsy[END_REF]. HFOs, occurring in epileptic human intracranial ElectroEncephaloGraphic (iEEG) signals, are non-stationary oscillations with consecutive oscillations in the frequency band that can be distinguished from the baseline [START_REF] Zijlmans | High-frequency oscillations as a new biomarker in epilepsy[END_REF]. Frequently, researchers divide the HFOs into two bands, namely Ripples (Rs, [80-250 Hz]) and Fast Ripples (FRs, [250-500 Hz]) [START_REF] Jacobs | High frequency oscillations (HFOs) in clinical epilepsy[END_REF], [START_REF] Zijlmans | High-frequency oscillations as a new biomarker in epilepsy[END_REF]. Actually, in some studies, authors have proven that HFOs bands also include Gamma ( , ) [START_REF] Uhlhaas | A new look at gamma? highlight-(>60 Hz) γ-band activity in Accepted manuscript / Final version cortical networks: Function, mechanisms and impairment[END_REF], [START_REF] Park | Ictal high-gamma oscillation (60-99Hz) in intracranial electroencephalography and postoperative seizure outcome in neocortical epilepsy[END_REF] and High-Gamma (  H , [80-120 Hz]) [START_REF] Uhlhaas | A new look at gamma? highlight-(>60 Hz) γ-band activity in Accepted manuscript / Final version cortical networks: Function, mechanisms and impairment[END_REF], [START_REF] Park | Ictal high-gamma oscillation (60-99Hz) in intracranial electroencephalography and postoperative seizure outcome in neocortical epilepsy[END_REF] bands. Thus, HFOs can be divided into four bands:  ([30-80 Hz]),  H ([80-120 Hz]), Rs ) and FRs ). HFOs detection is traditionally performed by experts through a visual inspection from long hours of iEEG recordings [START_REF] Jacobs | High frequency oscillations (HFOs) in clinical epilepsy[END_REF]. However, such marking remains timeconsuming and subjective [START_REF] Zijlmans | High-frequency oscillations as a new biomarker in epilepsy[END_REF]. To cope with this issue, several approaches [START_REF] Jrad | Automatic detection and classification of high frequency oscillations in depth-EEG signals[END_REF], [START_REF] Birot | Automatic detection of fast ripples[END_REF], [START_REF] Staba | Quantitative analysis of high-frequency oscillations (80-500 Hz) recorded in human epileptic hippocampus and entorhinal cortex[END_REF], [START_REF] Gardner | Human and automated detection of high-frequency oscillations in clinical intracranial EEG recordings[END_REF], [START_REF] Crépon | Mapping interictal oscillations greater than 200 Hz recorded with intracranial macroelectrodes in human epilepsy[END_REF], [START_REF] Krikid | A comparative study between three epileptic high frequency oscillations detection strategies[END_REF], [START_REF] Roehri | Are highfrequency oscillations better biomarkers of the epileptogenic zone than spikes?[END_REF] have been proposed in the literature aiming at providing automatic identification of these particular cerebral activities, and especially their discrimination from other transient events like Interictal Epileptic Spikes (IESs). Commonly, the HFOs detection procedures are split into detection and classification [START_REF] Jrad | Automatic detection and classification of high frequency oscillations in depth-EEG signals[END_REF], [START_REF] Birot | Automatic detection of fast ripples[END_REF], [START_REF] Staba | Quantitative analysis of high-frequency oscillations (80-500 Hz) recorded in human epileptic hippocampus and entorhinal cortex[END_REF], [START_REF] Gardner | Human and automated detection of high-frequency oscillations in clinical intracranial EEG recordings[END_REF], [START_REF] Crépon | Mapping interictal oscillations greater than 200 Hz recorded with intracranial macroelectrodes in human epilepsy[END_REF], [START_REF] Roehri | Are highfrequency oscillations better biomarkers of the epileptogenic zone than spikes?[END_REF] to cite a few, but, in the present study only the classification stage is considered. Therefore, existing approaches on detection and estimation of HFOs are out of the scope of this paper. A recent study [START_REF] Roehri | Are highfrequency oscillations better biomarkers of the epileptogenic zone than spikes?[END_REF] showed that HFOs and IESs are complementary biomarkers of the EZ. Hence, identifying relevant features for those biomarkers is a real need. The present study focuses on the prominent features for a multi-classification task with the aim of discriminating among the different HFOs and IESs. Until now, various algorithms have been developed for the classification of HFOs events. The principle of these algorithms involves machine learning approaches to extract relevant features and use them for HFOs classification. In this context, supervised and unsupervised machine learning algorithms (see Table 1) have been widely used. Firpi et al. [START_REF] Firpi | Highfrequency oscillations detected in epileptic networks using swarmed neural-network features[END_REF] proposed an algorithm based on particle swarm optimization and neural networks to generate relevant features that separate HFOs and a baseline activity. An unsupervised cluster has been provided by Blanco et al. [17] to discriminate between HFOs and artifacts based on a k -medoids approach and some features in the time and frequency domains. To distinguish between true and false HFOs, Dümpelmann et al. [START_REF] Dümpelmann | Automatic 80 -250 Hz "ripple" high frequency oscillation detection in invasive subdural grid and strip recordings in epilepsy by a radial basis function neural network[END_REF] employed time features and radial basis function neural networks. Moreover, for a binary classification between physiological and pathological HFOs, Matsumoto et al. [START_REF] Matsumoto | Pathological and physiological high-frequency oscillations in focal human epilepsy[END_REF] employed a cascade of time and frequency features as an input to a Support Vector Machine (SVM) classifier. Chaibi et al. [START_REF] Chaibi | Detection of high frequency oscillations (HFOs) in the 80-500 Hz range in epilepsy recordings using decision tree analysis[END_REF] associated several features with decision trees classifier to distinguish HFOs and background activity. To increase the discrimination among HFOs events and noise, Liu et al. [START_REF] Liu | Exploring the time-frequency content of high frequency oscillations for automated identification of seizure onset zone in epilepsy[END_REF] provided a Gaussian Mixture Model (GMM) based clustering. Approximate entropy [START_REF] López-Cuevas | An algorithm for online detection of high frequency oscillations related to epilepsy[END_REF] and fuzzy entropy [START_REF] Ting | Automatic detection of high frequency oscillations based on Fuzzy entropy and Fuzzy neural network[END_REF] were also used to separate HFOs from normal activity. In the context of multiclassification of the HFOs events, Jrad et al. [START_REF] Jrad | Automatic detection and classification of high frequency oscillations in depth-EEG signals[END_REF] considered energy ratio between bands and time duration as features. Recently, wavelet entropy and Teager energy were used in [START_REF] Yuxiao | A method for detecting highfrequency oscillations using semisupervised k-means and mean shift clustering[END_REF] for HFOs clustering using kmeans and mean shift algorithms. More recently, other studies focused on the discrimination between different HFOs bands using root mean square energy [START_REF] Lachner-Piza | Automatic detection of highfrequency-oscillations and their subgroups co-occurring with interictalepileptic-spikes[END_REF], line length energy [START_REF] Lachner-Piza | Automatic detection of highfrequency-oscillations and their subgroups co-occurring with interictalepileptic-spikes[END_REF], [26], short time energy [26] and Teager energy [START_REF] Lachner-Piza | Automatic detection of highfrequency-oscillations and their subgroups co-occurring with interictalepileptic-spikes[END_REF] as features. for a complete review of conventional time, frequency and energy-based features, the reader can refer to [START_REF] Park | High frequency oscillations in epilepsy: Detection methods and considerations in clinical application[END_REF].

As listed in Table 1, it is clear that the most frequent features in the literature come either from the time domain or from the frequency domain. However, a main drawback of those domains is the difficulty in providing any information about frequency variations over time. Hence, since HFOs are non-stationary, it is essential to describe their spectral change in time. Thus, the time frequency (TF) representation presents the advantage of merging both time and frequency information. Moreover, the TF representation has shown to be efficient in a number of neuroscience applications, for instance Alzheimer's disease identification [START_REF] Fiscon | Combining EEG signal processing with supervised methods for Alzheimer's patients classification[END_REF], sleep stage classification [START_REF] Ghasemzadeh | Sleep stages classification from eeg signal based on Stockwell transform[END_REF], [START_REF] Tsinalis | Automatic sleep stage scoring Using Time-Frequency Analysis and Stacked Sparse Autoencoders[END_REF], or epileptic seizure classification [START_REF] Krishnan | Automated EEG seizure detection based on Stransform[END_REF], [START_REF] Shoeibi | Epileptic seizures detection using deep learning techniques: a review[END_REF]. Recently, several studies have addressed the relevance of the TF representation in the context of HFOs classification [START_REF] Jrad | Automatic detection and classification of high frequency oscillations in depth-EEG signals[END_REF], [START_REF] Liu | Exploring the time-frequency content of high frequency oscillations for automated identification of seizure onset zone in epilepsy[END_REF]. More particularly, Migliorelli et al. [START_REF] Migliorelli | SGM: a novel timefrequency algorithm based on unsupervised learning improves highfrequency oscillation detection in epilepsy[END_REF] proposed a set of relevant TF-based features for a binary classification of HFOs (i.e., HFOs vs no HFOs). However, no study has addressed the shape of HFOs events in the TF plane as a way to characterize them. Such shape related features can further be relevant for a complete description of HFOs events. Therefore, the novelty of the present contribution resides in combining TF and image related features derived from TF representations of HFOs as an adequate mean towards a complete characterization of HFOs and hence a more robust HFOs multiclassification task. To achieve high classification performances, extracting relevant TF features requires powerful TF representation tool. Most TF representations are based on short time Fourier transform (STFT), wavelet analysis such as the continuous wavelet transform (CWT) or Wigner Ville distribution (WVD). The major drawback of these TF representations is the cross-term which may cause noise in TF signal analysis. Hence, the Stockwell transform (S-transform) [START_REF] Stockwell | Localization of the complex spectrum:the S transform[END_REF] has been developed to overcome the limits of the conventional representations. Thanks to its TF resolution, the S-transform provides a better visualization. This advantage makes this representation an appropriate tool in our study.

In this paper, we propose a new approach to discriminate between five classes, namely  ,  H , Rs, FRs and IESs. More precisely, we proposed to firstly extract diverse features from a TF based S-transform representation [START_REF] Stockwell | Localization of the complex spectrum:the S transform[END_REF] with the aim of tracking the energy distribution of the different five classes. Likewise, relevant image-based features derived from image processing tools such as image binarization and image gradient, commonly used in computer vision, are also used in this study to characterize the events of interest. Finally, the constructed feature vector, including both TF and image-related features, is provided as an input to a multiclass SVM classifier.

The remainder of the paper is organized as follows: Section II is dedicated to methodology. Numerical experiments are presented in Section III, discussion is given in Section IV and finally the conclusion in Section V.

II. METHODOLOGY

The present work proposes a new approach for the classification of  ,  H , Rs, FRs (i.e., HFOs) and IESs activities. It relies mainly on employing relevant features extracted, for each event of interest, from the corresponding TF representation and its associated TF grayscale image. These characteristics are then used to learn the classifier. A flow chart describing the main steps of the proposed approach is given in Fig. 1. More details regarding each step are presented in the subsequent subsections.

II.1. Notations

In the sequel, matrices are denoted by italic boldface capital letters, e.g., A , vectors are denoted by italic boldface lowercase letters, e.g., a , and scalars are denoted by italic lowercase letters, e.g., a . In addition, the ( )

, i j
th entry of a matrix A is denoted by ( ) , A i j . Besides, . will denote either the absolute value function of real numbers or the magnitude in case of complex argument. In addition, and  stand for the transposition and the convolution operators, respectively.

II.2. Data preprocessing

As the labeled segments of interest (SOIs) in our dataset are not of equal duration, the data preprocessing step consists in reframing each SOI into a 200 ms length one. This time period (i.e., 200 ms ) corresponds to the average of all periods of labeled events in our dataset. Then, each 200 ms -length SOI was first centered around 0 ms such that each event lasted from -100 ms to + 100 ms. Besides, in order to assess the relevance of the chosen time period of each SOI (i.e., 200 ms ), the performance of the proposed approach was also evaluated using different time periods (60 ms and 600 ms). The time period of 60 ms corresponds to the one of the shortest labelled SOI in our data set while the time period of 600 ms is the one of the largest labelled SOI. Numerical simulations have shown a highest performance of the proposed approach when a time period of 200 ms was Accepted manuscript / Final version used. An extensive description of this comparative study is provided as supplementary materials. Finally, in order to avoid the edge effect in each segment during the S-transform step, the obtained SOI was multiplied with a Hanning window of 200 ms length.

II.3. Time-Frequency representation

Once the SOIs have all the same duration, a TF representation of each SOI is then performed using the S-transform [START_REF] Stockwell | Localization of the complex spectrum:the S transform[END_REF]. Let

  =- , 0,1,2
  -0, , 1 mM
, where M stands for the number of frequency bins, is defined as follows:

        - - = = -  1 2 0 m N ik M n S k,m x n k n,m e (1)
where    , nm is a specific mother wavelet function given by:

    - = 22

II.4. Feature extraction

In this step which is the core of the proposed approach, features are extracted not only from conventional raw TF representation [START_REF] Boashash | Principles of time-frequency feature extraction for change detection in non-stationary signals: applications to newborn EEG abnormality Accepted manuscript / Final version detection[END_REF] of each SOI but also from its associated TF grayscale image. Such transformed representation permits to employ specific features in the field of image analysis and processing as described below. For the sake of convenience, we note from now on

II.4.2. Time-frequency image feature

In addition to the above TF features, other image-related ones are also employed. To this end, two transformations of the initial TF plane are performed: (i) binarization and (ii) binarization followed by an image gradient computation [START_REF] Abudhamid Mohamed | Gradient Based Image Edge Detection[END_REF]. Image related features are then extracted from these two representations.

II.4.2.1. Binary image features

The TF representation of each SOI is transformed into a 8-bit grayscale image. Then, the obtained grayscale image is binarized using Otsu's method [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF]. This method is widely used in image processing for image segmentation or binarization. For each obtained binary image, denoted here by  , geometric features are extracted. These features can be calculated using the image moment, The moment based geometric features considered in our study are:

• The area: the number of pixels constituting the SOI in the image 0,0 Area = M

• The perimeter: the number of image pixels constituting the SOI boundary

( ) ( ) ( ) = + + + 2 2 3,0 1,2 0,3 2,1 Perimeter M M M M
• The compactness: a measure reflecting the SOI shape in the considered plane 2

Perimeter

Compactness = Area

• The centroid: the pixel at the center of the SOI shape with TF coordinates given by

   

1,0 0,1 0,0 0,0 ; MM MM .

II.4.2.2. Image gradient features

For each considered SOI, the gradient of its binarized TF representation is computed by convolving its associated binary image  with the gradient operator

  = -1 0 1 h
. This convolution is performed through the time and frequency directions separately: =  t Gh [START_REF] Gardner | Human and automated detection of high-frequency oscillations in clinical intracranial EEG recordings[END_REF] =  f Gh [START_REF] Crépon | Mapping interictal oscillations greater than 200 Hz recorded with intracranial macroelectrodes in human epilepsy[END_REF] where t G and f G are respectively the image gradients following the time and frequency axes. Then, the magnitude of the obtained gradient image [START_REF] Abudhamid Mohamed | Gradient Based Image Edge Detection[END_REF],  , is computed as follows:

 = + 22 tf GG (14)
Once the gradient image is computed, its 1 Lnorm can be considered as a feature quantifying the sparsity of the resulting contour. This A summary list of the TF extracted features is given in Table 2.

II.5. Multi-class SVM classification

Once the aforementioned features are computed, they are used to learn the classifier. In this study, the SVM algorithm is used for the multi-classification of the different events in our dataset. The choice of this algorithm comes from its efficiency which has been reported earlier in several EEG based multi-classification studies [START_REF] Jrad | Automatic detection and classification of high frequency oscillations in depth-EEG signals[END_REF], [START_REF] Lachner-Piza | Automatic detection of highfrequency-oscillations and their subgroups co-occurring with interictalepileptic-spikes[END_REF], [26]. In this work, the radial basis function (RBF) widely used in the context of multiclassification problems is employed as a kernel for the SVM algorithm [START_REF] Fu | Classification of seizure based on the time-frequency image of EEG signals using HHT and SVM[END_REF]. The RBF

Accepted manuscript / Final version

Type Name Formula Specificity

Raw TF feature the margins between classes. To minimize the risk of model overfitting, the abovementioned parameters are wisely defined using the grid search method [START_REF] Chao | The Construction of Support Vector Machine Classifier Using the Firefly algorithm[END_REF].

TF flux       ---- = = = + + -  1 1 0 0 , , , N l M
Besides, the widely used One-Against-All (OAA) technique [START_REF] Chao | The Construction of Support Vector Machine Classifier Using the Firefly algorithm[END_REF] is employed to adapt the SVM algorithm, initially proposed for binary classification, to multi-classification tasks.

Accepted manuscript / Final version

III. NUMERICAL EXPERIMENTS

III.1. iEEG dataset

Both simulated and real iEEG signals are used in this study. More details regarding the description of these signals can be found in [START_REF] Jrad | Automatic detection and classification of high frequency oscillations in depth-EEG signals[END_REF].

Briefly, the real iEEG signals were recorded in the Neurology Department of the University Hospital of Rennes, France from five patients who suffered from refractory epilepsy. All patients gave informed consent for participation in research studies. A 256-Brain Quick (Micromed, Italy) recording system with a sampling rate of 2048 Hz was used for data acquisition. The visual marking of HFOs events was done by two reviewers independently in LTSI, University of Rennes 1. A total number of 5174 marked events were employed in the present study. In fact, five classes  ,  H , Rs, FRs and IESs are taken into consideration in the annotation procedure and labeled as  (1015),  H (1032), Rs (1053), FRs (1071), and IESs (1003).

To assess the performance of the proposed classification system, a study on simulated signals was also conducted. These signals were generated by adding simulated cerebral background activity to the real annotated events described above. The background activity was simulated by means of a computational model of neural population where sigmoid weights were used to control the background activity level. A signal to noise ratio (SNR) was defined to control the ratio between the event of interest and the background activity. This permits to evaluate the robustness of the proposed approach to several SNR values (-10, -5, 0, 5, 10 and 15 dB).

III.2. Performance measures

Several performance criteria are used in this study to evaluate the classification performance of the proposed approach. These criteria are the sensitivity (SEN), the specificity (SPE), the accuracy (ACC) and F1score defined respectively as follows:

( ) Moreover, the SEN and SPE metrics are used to design a receiver operating characteristic (ROC) curve, from which the area under the ROC curve (AUC) is computed as a measure to assess the relevance of the SVM classifier.

All experiments and simulations in the present study were performed using MATLAB (Mathworks Inc., Natick, MA) for iEEG database processing and Python software for classification through the scikit-learn library (https://scikit-learn.org). Different simulations were run on an Intel(R) Xeon (R), 2.7 GHz (2 processors) with 32 Go memory.

III.3. Feature extraction and analysis

As mentioned previously (Section II.5), for each SOI, both TF and image-based features are used to learn the classifier. Fig. 2 shows for each SOI in our dataset (first row) (i) the TF plane (second row), (ii) the TF plane in a grayscale image form (third row), (iii) the binarized version of the TF grayscale image (fourth row) and (iv) the gradient representation of the TF grayscale image (fifth row). Each representation has its own specificity to characterize the considered SOI. For example, while the TF representation provides information regarding the energy distribution over the time and frequency domains, which can be revealed by adequate TF features such as , the image gradient based TF representation helps in shedding light upon the event contour which can be quantified using the 1 L -norm. Features described previously are extracted for each SOI in our dataset. Then, in order to analyze the relevance of the selected features, a feature analysis based on violin plot representation [START_REF] Waskom | Seaborn: Statistical Data Visualization Seaborn[END_REF] is adopted as depicted in Fig. 3. Such representation combines statistical information that can be given by a simple boxplot representation with the distribution of the considered feature over the entire dataset. Furthermore, for the sake of comparability between all violin representations, a min-max normalization approach is applied to all computed features. Fig. 3 shows generally that, for each event (i.e.,  ,  H , Rs, FRs and IESs), the selected features are discriminant since their corresponding violin plots are different in terms of both statistical information (median and quartiles) and feature distribution. Besides, even for those features with quasisimilar feature distributions (i.e., case of features ku and cv ), their corresponding expected to provide a good classification of the segments of interest.

Accepted manuscript / Final version

III.4. Events classification

Once the features are computed, the next step consists in evaluating the performance of the proposed approach in classifying the five events  ,  H , Rs, FRs and IESs. This classification step is performed using the SVM classifier since the proposed approach has shown higher performance using such classifier compared to the other well-known knearest neighbor (KNN), naive Bayes (NB) and random forest (RF) ones. For a detailed description of this comparative study, the reader can refer to the provided supplementary materials. The performance evaluation study is conducted first using only simulated data and then using only real data. Here, each dataset (simulated and real data) is split into a training set (70%) and a test set (30%). Then, the training set is used to learn the optimal SVM-RBF hyperparameters 𝐶 and 𝛽 using the grid search method with a 5fold cross validation scheme. Indeed, the retained couple (𝐶, 𝛽), among a set of (𝐶, 𝛽) candidates ((𝐶, 𝛽) ∈ {1,10,100,1000,100000} × {10 -5 , 10 -4 , 0.01, 0.1, 1}) defined over the search grid, is the one for which the smallest model prediction error is obtained. Once the optimal hyperparameters are found, the test set is then used to evaluate the model performance in terms of sensitivity, specificity, accuracy, AUC and F1-score. The above steps are repeated over 100 trials where, at each trial, the training and test sets are randomly reshuffled. Regarding the couple (𝐶, 𝛽) of hyperparameters, the optimal value was (10 ,1) for the simulated data and (1,0.1) for the real ones.

III.4.1. Case of simulated events

The behavior of the proposed classification approach is first evaluated on a simulated dataset generated as described in subsection III.1 for several SNRs (-10, -5, 0, 5, 10 and 15 dB) and then compared to conventional methods where only time, frequency [START_REF] Matsumoto | Pathological and physiological high-frequency oscillations in focal human epilepsy[END_REF], [START_REF] Chaibi | Detection of high frequency oscillations (HFOs) in the 80-500 Hz range in epilepsy recordings using decision tree analysis[END_REF] or energy-based [26] features are used.

Obtained classification results in terms of SEN, SPE, ACC, AUC and F1-score criteria are given in Table 3 for the different SNR values. The mean and the standard deviation (STD) of the different computed performance metrics were provided for each class of the HFOs events. In addition, an averaged performance score for each metric was used as suggested in [START_REF] Alhudhaif | A novel multi-class imbalanced EEG signals classification based on the adaptive synthetic sampling (ADASYN) approach[END_REF] and [START_REF] Memar | A Novel Multi-Class EEG-Based Sleep Stage Classification System[END_REF]. The goal of this latter score is to get an overview on the performance of the proposed method. According to Table 3, a good classification performance can be observed for the proposed approach for all classes and for all SNR values. More particularly, at first glance, we note that SEN, SPE, ACC, AUC and F1score criteria show, for all event types and SNR values, averaged values around 0.970, 0.990, 0.990, 0.990 and 0.970, respectively.

From a SNR point of view, the proposed classification strategy shows slightly lower performance for lower SNR values (i.e., -5 and -10 dB) compared to the case of relatively high SNR values (10 and 15 dB). For instance, for SNR of 15 dB, values of 0.990 (0.001), 0.996 (0.003), 0.995 (0.004), 0.993 (0.002) and 0.990 (0.001), are obtained respectively, for SEN, SPE, ACC AUC and F1-score criteria. However, for SNR value of -10 dB, these criteria have values of 0.978 (0.003), 0.988 (0.004), 0.983 (0.005), 0.994 (0.002) and 0.980 (0.002), respectively. This is probably due the fact that, for low SNR, events of interest are drowned in the background activity or at least their amplitude is very comparable to the one of the background activity. Regarding the comparison of the proposed approach with the abovementioned conventional methods [START_REF] Matsumoto | Pathological and physiological high-frequency oscillations in focal human epilepsy[END_REF], [START_REF] Chaibi | Detection of high frequency oscillations (HFOs) in the 80-500 Hz range in epilepsy recordings using decision tree analysis[END_REF], [26], Fig. 4 shows the performance of the proposed approach in terms of SEN, SPE, ACC, AUC and F1-score for different SNR values i.e.,-10, -5, 0, 5, 10 and 15 dB. According to this figure, a higher classification performance of the proposed approach compared to the conventional methods can be noticed, especially for low SNR values. For instance, while the approach in [START_REF] Lachner-Piza | Automatic detection of highfrequency-oscillations and their subgroups co-occurring with interictalepileptic-spikes[END_REF] shows, for SNR equal to -10 dB, values of 0.854, 0.752, 0.711, 0.800 and 0.800 for SEN, SPE, ACC, AUC and F1-score, respectively, the proposed approach provides values of 0.978, 0.998, 0.983, 0.994 and 0.980 for the same criteria. Similarly, the proposed approach provides also higher classification scores compared to [START_REF] Matsumoto | Pathological and physiological high-frequency oscillations in focal human epilepsy[END_REF] and [START_REF] Chaibi | Detection of high frequency oscillations (HFOs) in the 80-500 Hz range in epilepsy recordings using decision tree analysis[END_REF].

III.4.2. Case of real data

The proposed approach has been also evaluated on real data in terms of SEN, SPE, ACC, AUC and F1-score. Hence, the mean and the STD of the different performance metrics are provided in Table 4 for each class of the HFOs events. According to this table, the proposed approach shows an averaged classification performance of 0.765 (0.025), 0.941 (0.006), 0.906 (0.006), 0.929 (0.005) and 0.768 (0.016), respectively. The relatively low value of the SEN criterion (0.765) compared to the one of the SPE (0.941) and ACC (0.906) is probably due to a lack of class separability in the trained classifier. However, despite the relatively low value of the SEN criterion, a high AUC value (0.929) is obtained. Furthermore, from event point of view, Table 4 shows that the best classification results are obtained for  and FRs events with SEN value of 0.846 (0.025) and 0.825 (0.025), respectively.

Regarding the comparison of the proposed approach with conventional approaches [START_REF] Matsumoto | Pathological and physiological high-frequency oscillations in focal human epilepsy[END_REF], [START_REF] Chaibi | Detection of high frequency oscillations (HFOs) in the 80-500 Hz range in epilepsy recordings using decision tree analysis[END_REF], [26], results in terms of SEN, SPE, ACC, AUC and F1-score are depicted in Fig. 5. According to this figure, we note again a higher classification performance for the proposed approach. For instance, while averaged values of 0.765, 0.941, 0.906, 0.929 and 0.768 of SEN, SPE, ACC AUC and F1score criteria are respectively obtained for the proposed approach, lower values respectively equal to 0.529, 0.811, 0.852, 0.807, and 0.697 are obtained using the method proposed in [26]. Similarly, methods proposed in [START_REF] Matsumoto | Pathological and physiological high-frequency oscillations in focal human epilepsy[END_REF] and [START_REF] Chaibi | Detection of high frequency oscillations (HFOs) in the 80-500 Hz range in epilepsy recordings using decision tree analysis[END_REF] show lower multiclassification performance compared to the proposed approach. In fact, the lowest behavior is noticed for the method developed in [START_REF] Matsumoto | Pathological and physiological high-frequency oscillations in focal human epilepsy[END_REF] as depicted in Fig. 5.

IV. DISCUSSION

In this study a new approach for the classification of HFOs (  ,  H , Rs, FRs) and IESs activities was proposed. This approach relies mainly on employing relevant TF and image-based features to characterize the events of interest. These features allow for a complete characterization of these events in both time and frequency domains, simultaneously.

On the methodological level, thanks to its efficiency [START_REF] Migliorelli | SGM: a novel timefrequency algorithm based on unsupervised learning improves highfrequency oscillation detection in epilepsy[END_REF], [START_REF] Burnos | Human intracranial high frequency oscillations (HFOs) detected by automatic timefrequency analysis[END_REF], the S-transform was used to compute the TF representation of each SOI. This transform provides an efficient TF representation to reveal different TF and related image-based features. To the best of our knowledge, no study has yet addressed HFOs and IESs classification by employing simultaneously TF and image-based features. Such combination of TF and image-based features as proposed in this paper led to a very competitive classification performance in terms of SEN, SPE, ACC, AUC and F1-score, as shown in the previous section. More particularly, the proposed approach provides generally good performance results using simulated data as shown in Table 3, for all considered SNR values. However, a slight decrease in performance has been noticed in the case of low SNRs (i.e., -10 dB and -5 dB). Regarding the performance of the proposed approach on real iEEG recordings, a good behavior was still observed compared to the conventional approaches [START_REF] Matsumoto | Pathological and physiological high-frequency oscillations in focal human epilepsy[END_REF], [START_REF] Chaibi | Detection of high frequency oscillations (HFOs) in the 80-500 Hz range in epilepsy recordings using decision tree analysis[END_REF] and [26] which is based only on time, frequency and energy features. Indeed, the proposed method achieved a good specificity across all HFOs classes with a good averaged value of 0.929 for the AUC criterion.

In fact, the good behavior of the proposed approach brings out the relevance of the employed TF and image-based features. This fact holds true for both simulated and real data.

The major finding in our work concerns the fact that TF features combined with imagebased ones are a promising tool for multiclassification of HFOs and IESs. However, there are some limitations in the present study, which should be highlighted for future research. On the one hand, the proposed approach could suffer from the curse of dimensionality problem. This is mainly due to the dimensionality of the input feature vector which is proportional to the number of TF and image-based features. Such an issue can be dealt with by resorting to deep learning that allows for an automatic extraction of the most Accepted manuscript / Final version relevant TF and image-based features. In fact, deep learning has proved its relevance in image and signal processing areas. Even for HFOs classification, some studies such as [START_REF] Zuo | Automated detection of high-frequency oscillations in epilepsy based on a convolutional neural network[END_REF], [START_REF] Zhao | Integrated automatic detection, classification and imaging of high frequency oscillations with stereoelectroencephalography[END_REF], to cite a few, have employed the CNN as a powerful deep learning tool. However, resorting to deep learning requires the data set to be large enough for a reliable network training step. Such condition is not fulfilled in the current study and stands, on the second hand, for an another limitation to be pointed out here. Therefore, future work would concern the collect of more clinical data for a more complete assessment.

V. Conclusion

The present paper investigated a new approach for HFOs classification method based on TF representation of events of interest. Several SOIs are projected in the TF domain using S-transform and from which several TF and image-based features were extracted. The efficiency of the proposed approach in terms of SEN, SPE, ACC, AUC and F1-score has been assessed through numerical experiments using simulated and real iEEG recordings. Obtained results support our claim that combining TF and image-based features are a promising tool to characterize events of interest in time and frequency domains, simultaneously and consequently to provide a powerful multiclassification of HFOs and IESs.

Fig. 1 .

 1 Fig. 1. Flowchart of the proposed HFOs classification method.

••

  . II.4.1. Raw Time-frequency features • Time-frequency flux () flux TF: a measure of the variation of the signal energy in the TF plane. It is defined by: r are the direction of the signal energy through the time and frequency axes, respectively. Three possible directions are considered in this study: (i) along the time axis (i.e., = l 1 , Energy concentration() EC : a measure to quantify the concentration of the signal energy in the TF plane: Statistical features: statistical features such as the mean  (), standard deviation  () , skewness () sk , kurtosis () ku and the coefficient of variation () cv , are also considered. Conventionally, those features are employed separately either in the time or in the frequency domain. Recently, they have been extended to the TF domain and defined as follows[START_REF] Boashash | Principles of time-frequency feature extraction for change detection in non-stationary signals: applications to newborn EEG abnormality Accepted manuscript / Final version detection[END_REF]:

   and  are two training samples and  denotes the width of the RBF function. Another important parameter to be taken into account for the SVM algorithm is the regularization parameter C , which is used to balance the relative importance of minimizing the training error and maximizing

Fig. 2 .

 2 Fig. 2. Representation of HFOs and IESs patterns in time domain (first row) (i) TF plane (second row), (ii) TF based grayscale image (third row), (iii) binarized TF based grayscale image (fourth row) and (iv) TF based grayscale image gradient (fifth row).

Fig. 3 .

 3 Fig. 3. Violin plots of the considered features of the five classes: (a):  , (b):  H , (c): Rs, (d): FRs

Fig. 4 .

 4 Fig. 4. Classification performance of the proposed approach compared to conventional ones using simulated data for different SNR values: (a): -10 dB, (b): -5 dB, (c): 0 dB, (d): 5 dB, (e): 10 dB and (f): 15 dB.

Table 1 .

 1 An overview on HFOs classification methods.

	Study	Features	Classification techniques	Context
	Firpi et al.	Particle swarm	Supervised/neural	Separation between HFOs and
	2007 [16]	optimization	networks	baseline activity

Table 2 .

 2 List of extracted TF and image-related features.

Table 3 .

 3 Classification performance of the proposed approach using simulated data, the mean (STD) of SEN, SPE, ACC, AUC and F1-score are reported.

	SNR (dB)	SOI class 	SEN 0.999 (0.003)	SPE 0.999 (0.002)	ACC 0.999 (0.001)	AUC 0.997 (0.004) 0.998 (0.005) F1-score
		 H	0.987 (0.002)	0.996 (0.005)	0.995 (0.006)	0.990 (0.004) 0.987 (0.001)
	+15	Rs FRs	0.981 (0.002) 0.985 (0.002)	0.994 (0.006) 0.995 (0.006)	0.991 (0.007) 0.993 (0.007)	0.990(0.001) 0.991 (0.003) 0.985 (0.001) 0.982 (0.001)
		IESs	1.000 (0.000)	1.000 (0.000)	1.000 (0.000)	1 (0.000)	1.000 (0.000)
		Average	0.990 (0.001)	0.996 (0.003)	0.995 (0.004)	0.993 (0.002) 0.990 (0.001)
			1.000 (0.000)	0.999 (0.000)	0.999 (0.000)	0.999 (0.000) 0.999 (0.001)
		 H	0.987 (0.002)	0.997 (0.004)	0.995 (0.000)	0.990 (0.004) 0.989 (0.001)
	+10	Rs FRs	0.987 (0.001) 0.986 (0.002)	0.994 (0.000) 0.997 (0.006)	0.992 (0.000) 0.994 (0.006)	0.992 (0.001) 0.983 (0.001) 0.992 (0.006) 0.988 (0.001)
		IESs	0.999 (0.003)	0.999 (0.001)	0.999 (0.001)	0.989 (0.001) 0.999 (0.003)
		Average	0.991 (0.001)	0.997 (0.002)	0.995 (0.001)	0.992 (0.002) 0.991 (0.001)
			0.999 (0.001)	0.998 (0.000)	0.998 (0.000)	0.999 (0.004) 0.996 (0.001)
		 H	0.973 (0.005)	0.995 (0.001)	0.986 (0.001)	0.991 (0.001) 0.977 (0.004)
		Rs	0.976 (0.005)	0.989 (0.001)	0.993 (0.006)	0.993 (0.007) 0.971 (0.003)
	+5	FRs	0.980 (0.004)	0.994 (0.001)	0.988 (0.001)	0.995 (0.001) 0.975 (0.003)
		IESs	0.998 (0.001)	0.999 (0.000)	0.999 (0.000)	0.999 (0.000) 0.998 (0.001)
		Average	0.985 (0.003)	0.995 (0.000)	0.992 (0.001)	0.995 (0.002) 0.983 (0.002)
			0.998 (0.001)	0.999 (0.000)	0.998 (0.000)	0.990 (0.007) 0.996 (0.001)
		 H	0.976 (0.005)	0.995 (0.001)	0.991 (0.001)	0.978 (0.001) 0.979 (0.003)
	0	Rs FRs	0.973 (0.004) 0.976 (0.004)	0.991 (0.001) 0.992 (0.001)	0.987 (0.007) 0.988 (0.001)	0.998 (0.006) 0.972 (0.003) 0.990 (0.002) 0.976 (0.003)
		IESs	0.999 (0.001)	0.999 (0.000)	0.999 (0.000)	0.999 (0.001) 0.998 (0.003)
		Average	0.984 (0.003)	0.995 (0.000)	0.992 (0.001)	0.992 (0.003) 0.984 (0.002)
			0.998 (0.001)	0.998 (0.000)	0.998 (0.000)	1.000 (0.007) 0.996 (0.001)
		 H	0.967 (0.006)	0.993 (0.001)	0.994 (0.007)	0.994 (0.007) 0.980 (0.001)
		Rs	0.988 (0.001)	0.971 (0.004)	0.964 (0.006)	0.999 (0.006) 0.966 (0.004)
	-5	FRs	0.974 (0.005)	0.990 (0.001)	0.986 (0.001)	0.995 (0.002) 0.972 (0.003)
		IESs	0.991 (0.001)	0.999 (0.000)	0.999 (0.000)	0.998 (0.001) 0.998 (0.001)
		Average	0.

983 (0.002) 0.990 (0.001) 0.988 (0.002) 0.997 (0.004) 0.982 (0.002)

			0.999 (0.005)	0.999 (0.001)	0.991 (0.001)	0.997 (0.004) 0.990 (0.004)
		 H	0.954 (0.002)	0.996 (0.005)	0.993 (0.006)	0.989 (0.001) 0.982 (0.001)
		Rs	0.980 (0.002)	0.961 (0.008)	0.961 (0.009)	0.992 (0.007) 0.967 (0.002)
	-10	FRs	0.973 (0.002)	0.993 (0.007)	0.977 (0.008)	0.993 (0.001) 0.969 (0.001)
		IESs	0.988 (0.008)	0.991 (0.000)	0.994 (0.001)	0.999 (0.000) 0.992 (0.004)
		Average	0.978 (0.003)	0.988 (0.004)	0.983 (0.005)	0.994 (0.002) 0.980 (0.002)
			Accepted manuscript / Final version

Table 4 .

 4 Classification performance of the proposed approach using real data, the mean (STD) of SEN, SPE, ACC, AUC and F1-score are reported.

	SOI class	SEN	SPE	ACC	AUC	F1-score
		0.846 (0.025)	0.963 (0.005)	0.940 (0.006)	0.970 (0.001)	0.848 (0.016)
	 H	0.717 (0.025)	0.882 (0.010)	0.849 (0.008)	0.866 (0.006)	0.655 (0.017)
	Rs	0.694 (0.024)	0.939 (0.007)	0.889 (0.007)	0.877 (0.012)	0.719 (0.018)
	FRs	0.825 (0.025)	0.965 (0.005)	0.936 (0.006)	0.953 (0.004)	0.843 (0.015)
	IESs	0.747 (0.026)	0.956 (0.005)	0.916 (0.006)	0.982 (0.006)	0.775 (0.017)

Average 0.765 (0.025) 0.941 (0.006) 0.906 (0.006) 0.929 (0.005) 0.768 (0.016) Accepted

manuscript / Final version Fig 5. Classification performance of the proposed approach compared to conventional ones using real data.

Accepted manuscript / Final version

ACKNOWLEDGMENTS

The research reported in this paper was developed as a part of the PHC (Partenariat Hubert Curien) Project CREDIADIC n°41711PK, CMCU Code 19G1411.

DECLARATION OF COMPETING

INTEREST

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.


Sébastien Ferré
email: ferre@irisa.fr

Agile Browsing of a Document Collection with Dynamic Taxonomies

Dynamic taxonomies and faceted search are increasingly used to organize and browse document collections. The main function of dynamic taxonomies is to start with the full collection, and zoom-in to a small enough subset of items for direct inspection. In this paper, we present other navigation modes than zoom-in for less directed and more exploratory browsing of a document collection. The presented navigation modes are zoom-out, shift, pivot, and querying by examples. These modes correspond to query transformations, and make use of boolean operators. Therefore, the current focus is always clearly specified by a query.

Introduction

Collections of numerical items are omnipresent: e.g., emails, photos, scientific publications, program source files, job announcements, e-commerce. The browsing of such collections is a key issue for users, and requires three main qualities: precision, ease of use, and confidence. Precision means that a subset of items can be retrieved under non-ambiguous criteria; ease of use means that users are guided in the expression of those criteria; and confidence means that enough feedback is returned to users so that they are confident about the results of their search.

The combination of those qualities requires the combination of querying and navigation [START_REF] Chiaramella | Browsing and querying: two complementary approaches for multimedia information retrieval[END_REF][START_REF] Godin | Experimental comparison of navigation in a Galois lattice with conventional information retrieval methods[END_REF]. Dynamic Taxonomies (DT) [START_REF] Sacco | Dynamic taxonomies: A model for large information bases[END_REF] are a general browsing mechanism that fullfils this combination. At any time, the focus is set on a subset of items, which can be characterized by a boolean combination of concepts (precision). The focus can be moved to smaller subsets of items by selecting concepts in a dynamic taxonomy, which is a taxonomy relevant to the current focus. In this way, users are guided in the refining process that leads to the desired items (ease of use), and feedback is given at any stage about all alternative choices (confidence). The same results are achieved by Logical Information Systems (LIS) [START_REF] Ferré | An introduction to logical information systems[END_REF], which use logics instead of taxonomies.

The goal is to show how dynamic taxonomies can be used to support more agile browsing of an item collection than the common zoom-in navigation mode. The motivation is that the user goal is not always to reach one item, but sometimes to reach and compare various sets of items, or simply to explore the item collection in order to discover interesting (ir)regularities [START_REF] Ferré | An introduction to logical information systems[END_REF]. We show that complex boolean queries can be composed without typing anything, but by simply selecting concepts in dynamic taxonomies. We also show that other navigation modes than zoom-in can be defined: zoom-out, shift, pivot, and querying by examples.

Section 2 recalls the basics of DTs, including how they provide local views on a collection. Section 3 details the different navigation modes, and illustrates them using a collection of photos. Section 4 discusses a few extensions and perspectives that are relevant to the agile browsing of a collection, and concludes this paper.

Dynamic Taxonomies as Local Views

A taxonomy is a concept hierarchy, where concepts are ordered from the more general topics to the more specific ones. Taxonomies can be designed for locations (from continents to towns), for dates (from years to days), or for groups of persons (from larger groups to individuals). Generally, the taxonomies used in DTs are multi-dimensional, and so include several such taxonomies. Items can then be classified under several concepts and at different levels of abstraction. When an item belongs to a concept, it also belongs to all ancestor concepts in the taxonomy. A key notion is the extension of a concept, which is defined as the set of all items that belong to it. A taxonomy extended with the extension of concepts is called an infobase.

The navigation space induced by an infobase is a very large graph, whose nodes are navigation places, and edges are navigation links. A navigation place is any non-empty set of items that is the extension of some query. A query is a boolean combination of concepts, and the extension of a query is computed by set operations (union, intersection, complement), starting from concept extensions, according to boolean operations (resp., or, and, not). Hence, the richer the taxonomy is, the larger the navigation space is. Of course, the navigation space can have a size exponential in the number of items, but it is never computed entirely.

The principle of DTs is to show only a local view, focusing on one navigation place at a time. A local view is made of 3 parts: (1) the query, (2) the extension of this query, and (3) the dynamic taxonomy over this extension. The dynamic taxonomy plays the role of an index or summary for the current extension, and is defined as the pruning of the taxonomy to retain only concepts having common items with the current extension. Furthermore, the dynamic taxonomy is the support of the various navigation links that lead to related navigation places. The most common navigation link is the zoom-in that leads to smaller extensions. Other kinds of navigation links are introduced in Section 3, and consti-tute the contribution of this paper. Every navigation link is defined by a query modification, and the current query therefore summarizes the navigation path since the beginning of the session. Even when the user does not need to edit the query, we think it is important to show it because it plays the role of a breadcrumb in the navigation process: after many navigation steps, the user may feel lost, but the query always tells her exactly where she is in the navigation space, and which choices she has already made.

Figure 1 is a screenshot of CAMELIS, our generic implementation of DTs, which we use to showcase the navigation modes in various applications. The structure of the local view is reflected by the graphical interface of CAMELIS. At any point in the interaction, the current query and its extent are displayed respectively as a text field at the top and as an item list at the right (here, photo thumbnails). The query is editable, and the extent can be scrolled page by page. At the left is displayed the dynamic taxonomy, where numbers, colors and scales are used to represent indicators about concepts, in the spirit of elastic lists [START_REF] Stefaner | Elastic lists for facet browsers[END_REF]. The numbers are the (local) count of concepts in the current extension, and the font scale represents the logarithmic ratio between this count and the size of the current extension. The grey-level at the left of each concept count represents the logarithmic ratio between the local count and the global count of the concept: light-grey means that most items of this concept are in the current extension, and dark-grey means that few of them are. The background color of some concept counts show when several concepts have the same items in the current extension. For instance, in Figure 1, we see that the 13 photos taken in March 2004 are the same as the 13 photos taken in "Feather Dale Park", which means I visited this park in March 2004. Finally, if a concept is shared by all items in the current extent, it is red-colored if it occurs in the query, and orange-colored otherwise. This makes it possible to distinguish between logical and extensional consequences of the query. For instance in Figure 1, all selected photos are from Australia because the query says so (red), but all selected photos are from New South Wales because this is the only part of Australia I have visited (orange). Moreover, the distinction between red, orange, and black colors plays a crucial role in the navigation modes, namely between zoom-in and zoom-out.

Navigation Modes

We start with the common zoom-in mode, but extend it to handle disjunction and negation in queries. We then proceed with other modes: zoom-out, shift, pivot, and querying by examples. All modes are illustrated by examples on Lisa's photo collection spanning several years. This collection contains 5,820 photos, which are described by date, location, event, type, visible persons and objects, and exif descriptors (e.g., time, flash, orientation). Exif descriptors are automatically extracted from photos, while other descriptors are given manually.

Zoom-in

Suppose Lisa wants to find some photos from a trip in Australia at the conference ICFCA'04. She first expands the concept Location, and finds she has photos from Europe (4859), Africa (162), and Australia (148). After selecting the concept Australia 1 :

• the query becomes Australia,

• the concept Australia becomes red because it is now part of the query, and it is automatically expanded to show sub-locations of Australia,

• the concepts Europe and Africa are no longer visible, because they are no longer relevant, i.e., count = 0, and 1 There are French words in the screenshot as it is a personal photo collection, but english translations are used in the text for consistency.

• the extension displays 10 photos (out of 148).

The sub-location 'New South Wales' becomes orange, which means this is the only region of Australia where Lisa has been. More precisely, she finds that she has been mainly in Sydney (105), and in the Blue Mountains (18). Now she expands the concept Type and sees there are different types of photos: buildings (29), animals (34), and plants [START_REF] Millen | Dogear: Social bookmarking in the enterprise[END_REF]. She becomes interested in Australian organisms, so she selects both Animal and Plant, which leads her to the refined query Australia and (Animal or Plant), whose extension contains 40 photos. One of these photos is a portrait, which Lisa does not want, so she selects the negation of Portrait with the help of a contextual menu. This leads her to the new query Australia and (Animal or Plant) and not Portrait (39 photos). By expanding more concepts, she discovers that these photos were taken in February and March 2004 in New South Wales, and that 5 photos of 3 different species of marsupials are present: kangaroo, koala, and wallaby.

These 3 navigation steps lead to local views with increasingly more precise queries, and hence increasingly smaller extensions. This is called the zoom-in navigation mode, and it combines the current query and a refinement with a conjunction. A refinement can be a single concept, a disjunction of concepts, or the negation of such a refinement. When a refinement uses only concepts that are relevant and not colored, the new local view is always strictly smaller but not empty. This is an advantage compared to purely querying systems, where it is common to get empty results.

Figure 1 shows the interface obtained after the previous navigation operations. At this stage, Lisa can either browse the 39 photos in CAMELIS, or launch a diaporama in an external application.

Zoom-out

During navigation, the user may want to remove or generalize concepts in the query so as to reach larger extensions: this is the zoom-out navigation mode. For instance, Lisa realises she desires more photos of animals and plants. The back button can be used to retract the previous refinement. Hence if she wants to remove the first refinement Australia, she needs to move 3 steps backwards, and then re-select the last 2 refinements. She could also edit the query by hand, but users usually prefer to navigate rather than to edit queries [START_REF] Godin | Experimental comparison of navigation in a Galois lattice with conventional information retrieval methods[END_REF].

Orange and red concepts are shared by all extension items and, therefore, cannot be used for zoom-in. This makes them available for zoom-out. When a red concept is selected, it is removed from the query. For instance, if Lisa selects Australia, the new query is (Animal or Plant) and not Portrait (282 photos from many locations). When an orange concept is selected, it replaces more specific concepts in the query. For instance, if she selects Pacific, the new query is (Animal or Plant) and not Portrait and Pacific. In the latter case, the concept Pacific becomes red because it is in the new query, and the concept Australia becomes black, or orange in the case this generalization adds no additional photo.

Compared to the existing approach, i.e., a list of removeable concepts, our approach has 3 advantages: (1) it is integrated into the dynamic taxonomy, (2) it allows the replacement of a concept by a more general one, and (3) it applies to refinements with disjunction and negation.

Shift

Zoom-in and zoom-out can be combined in 2 forms of shift navigation modes. Suppose the current query is now Australia and not Portrait and Plant (6 photos). At this point, Lisa sees that 1 photo has also the type Landscape, which interests her. She selects this concept (zoom-in) and, since the result has only 1 photo, she generalizes it by removing the concept Plant from the query (zoom-out). Therefore, she has executed a shift from Australian plants (6 photos) to Australian landscapes (80 photos), replacing in the query the concept Plant by the concept Landscape. From there, she performs a new shift from the concept Landscape to the concept Building, resulting in 28 photos of Australian buildings. These navigation steps are suggested and supported by photos sharing two concepts, i.e., by extensional relations [START_REF] Sacco | Dynamic taxonomies: A model for large information bases[END_REF]. This illustrates the relevance of assigning several types to photos, which is common in this photo infobase. The same would apply to persons visible on photos, as a photo can contain several people.

However, the same does not apply to locations, as a photo cannot be taken in 2 incomparable locations (e.g., in Australia and in Europe). Nonetheless, it is still possible to shift between locations, through the taxonomy of locations. Suppose Lisa wants to find building photos from other locations. She first generalizes Australia by Location in the query (zoom-out), and then browses suggested locations before selecting Spain (zoom-in). Thus, she has performed a shift from Australian buildings to Spanish buildings, and find 48 photos (which appear to be mainly churches taken in the north-west of Spain in 2003).

The former form of shift is a zoom-in/zoom-out combination, and can be qualified as extensional because it relies on extensional relations in the infobase. The latter form of shift is a zoom-out/zoom-in combination, and can be qualified as conceptual because it relies on conceptual relations in the taxonomy.

Pivot

The user may not remember a concept she wants to use to refine the query, but she can find it through another query. For instance, suppose Lisa wants to retrieve the photos of the building of some town. She does not remember which town it is, but she remembers that the ICFCA conference took place there in 2004. Therefore, she can first reach the query event contains "ICFCA" and date = 2004 by zoom-in navigation. The resulting extension shows photos of ICFCA'04, and the dynamic taxonomy shows relevant information about these photos, such as precise dates, locations, and so on. By browsing the dynamic taxonomy, she discovers that Sydney, in Australia, is the location of ICFCA'04. Then, she can make the query become Sydney, and refine it to the desired query Sydney and Building by zoom-in. The concept Sydney plays the role of a pivot between the 2 queries.

Pivot navigation relies on the ability of DTs to answer queries not only by a set of items (the extension), but also by a set of concepts (the dynamic taxonomy). In previous navigation modes, these concepts where added or removed from the query, whereas here they are used as new queries. Therefore, pivot navigation is a way to restart a search from the results of a first search. This kind of navigation has already been applied in collaborative websites [START_REF] Millen | Dogear: Social bookmarking in the enterprise[END_REF][START_REF] Zhou | Conversation pivots and double pivots[END_REF].

There is an interesting analogy with natural language. Indeed, the query above can be rephrased as "photos of buildings in the town, where the ICFCA conference took place in 2004". The idea of pivot is reflected by the fact that Sydney occurs in the main sentence as "town", and in the relative sentence as the relative pronoun "where". The relative pronoun indicates which facet to browse for a pivot: e.g., "where" indicates a location, "when" indicates a date, and "who" indicates a person. Iterated pivot navigation then corresponds to nested relative sentences, such as "photos of buildings in the town, where the ICFCA conference took place in the year, when I also visited Hinterzarten". The first pivot is the year 2004, and the second pivot is the town Sydney.

Querying by Examples

A query can be determined by the selection of a subset of items, thus supporting querying by examples. The idea is to construct the query as the conjunction of all most specific concepts which are shared by the selected items. For instance, suppose Lisa starts with the query Australia and not Portrait. While browsing photos in the result, she sees interesting photos of buildings (e.g., 2 photos of the Opera, and 1 photo of the Harbour Bridge), and she would like to find more. By selecting them she moves to a new query that is the conjunction of the concepts shared by those 3 photos. As usual with this form of navigation, the resulting query is very specific and she receives no additional photos. The concepts that make up the query are red-colored in the dynamic taxonomy, and she finds some of them very specific, e.g., a precise date (22 Feb 2004), a precise location (Sydney). At this step, she can use zoom-out to generalize the query. By removing in the query the concepts related to date and event, the query becomes Sydney and Building, and she finds 29 photos. From there, she can further zoom-out, zoom-in to find photos of modern buildings, or shift to find buildings in different countries. Interactive query relaxation [START_REF] Heer | Generalized selection via interactive query relaxation[END_REF] is similar to this process, except that only one facet is retained in the generalized query. For instance, starting with the same photos, Lisa could reach the query Sydney or Building, but not Sydney and Building.

A special case of querying by examples is when selecting only one photo. Since there is only one item in the extension, there is enough concepts to uniquely characterize each photo, and the query contains all the object descriptor concepts, which are more easily read as red concepts in the dynamic taxonomy. Therefore, this is an easy way to access the full description of an item.

Discussion and Conclusion

There are many ways to extend and improve the use of dynamic taxonomies for browsing and managing a collection of items. Some extensions are already implemented or being experimented in CAMELIS. First, the graphical interface of CAMELIS not only supports querying and navigation, but also the update of the infobase through the import of items (e.g., a pack of photos), or the addition/removal of items in concept extensions (manual annotations). Second, a preselection mechanism helps users to foresee the consequences of choosing some concepts to zoom-in, without changing the current local view, similarly to RB++ [START_REF] Zhang | Coupling browse and search in highly interactive user interfaces: A study of the relation Browser++[END_REF]. This is realized by modifying the appearance of the dynamic taxonomy and extension (e.g., background lightness), and enables a quick browsing and comparison of different selections. For instance, in the photo collection, Lisa can quickly see when she visited various locations by preselecting each location in turn, and looking at highlighted dates.

The intuitive display of statistical indicators [START_REF] Stefaner | Elastic lists for facet browsers[END_REF][START_REF] Zhang | Coupling browse and search in highly interactive user interfaces: A study of the relation Browser++[END_REF], and the definition and navigation of relations between items [START_REF] Bedel | Handling spatial relations in logical concept analysis to explore geographical data[END_REF] may improve the agility of navigation. Statistical indicators extend DTs in the direction of data mining. Relations extend DTs towards structured data, and widens the application scope to, e.g., geographical information systems, genealogy, and software development.

In conclusion, dynamic taxonomies support the agile browsing of a collection of documents, given a multidimensional classification of them. Documents can be se-lected according to complex boolean combination of concepts, i.e., queries. Those queries need not be edited by hand, but can be incrementally constructed by succesive navigation steps, starting with the most general query. Only relevant navigation steps are suggested to users through dynamic taxonomies. Different navigation modes enable the user to change the query in various directions: zoom-in makes the query more specific, zoom-out makes it more general, shift replaces a query concept by a related concept, pivot replaces the whole query by a related concept. Finally, querying by example allows the definition of a query from a set of items.

Figure 1 .

 1 Figure 1. The graphical interface of CAMELIS.


Michel Mitov

Pierre Slxou

Study of a Cholesteric Liquid Crystal Polymer in Solution in

come   L'archive ouverte pluridisciplinaire


Dr Illia A Lenko

Alexander Mamontov

Carole Alayrac
email: carole.witulski-alayrac@ensicaen.fr

Rémi Legay

Dr Bernhard Witulski
email: bernhard.witulski@ensicaen.fr

Dr C Mamontov

Dr R Alayrac

Prof Legay

Media-Driven Pd-Catalyzed Reaction Cascades with 1,3-Diynamides Leading Selectively to Either Indoles or Quinolines

Keywords: ynamides, indoles, quinolines, cumulenes, homogeneous catalysis [1]

Divergent Pd-catalyzed reaction cascades with various 1,3-diynamides yielding either 2-amino-3-alkynylindoles or 2-amino-4-alkenylquinolines were established. Omitting or adding TBAF (tetrabutylammonium fluoride) to the reaction of N,N-(2iodophenyl)(4-toluenesulfonyl)-1,3-diynamides with secondary or primary amines in the presence of KOH in THF and catalytic amounts of Pd(PPh3)4 completely changed the outcome of the reaction. In the absence of TBAF, 2-amino-3-alkynylindoles were the sole products, while the presence of TBAF switched the product formation to 2amino-4-alkenylquinolines. Deuterium labeling proceeded selectively at the C3 and C11 positions of the 2-amino-4-alkenylquinoline products and this suggests the unprecedented formation of [4]cumulenimines from 1,3-diynamides as reactive key intermediates.

Ynamides are inspiring building blocks for the construction of heterocycles relevant to pharmaceutical, agrochemical, and materials chemistry. [1] Their key reactivity is stirred by an electronically tunable nitrogen atom necessitating an adjacent electron-rich and polarized carbon-carbon triple bond being best described by the mesomeric forms A and A' in Figure 1. The electron-withdrawing group (EWG) attached to the ynamide nitrogen is guaranteeing sufficient stability and tunable reactivity. [1,2] Further activation of ynamides often relies on their reaction with Brønsted [3] or transition metal -acids [4] to form keteniminium ions [1a,5] providing superb reactivity within addition and/or annulation processes. Such approaches were particularly realized in the emerging gold catalysis of ynamides [6] leading to indoles [START_REF] Tian | For indole syntheses based on Au-catalysis with ynamides[END_REF][START_REF] Zhang | For indole syntheses based on ynamides[END_REF] and quinolines [START_REF] Zhao | For quinoline synthesis based on Au-catalysis[END_REF][START_REF] Oh | For quinoline syntheses based on ynamides[END_REF] with different substitution pattern. Protocols aiming at generating reactive neutral ketenimines [11] from ynamides have been less explored. [12] They encompass the N→C 1,3-tosyl group transfer of an N-(4toluenesulfonyl)ynamide carboxylic ester (Figure 1a) [13] and the N→C allyl shift via aza-Claisen rearrangement (Figure 1b). [8e,14] Decarboxylative allyl rearrangements were also reported to involve ketenimine intermediates that were designed to undergo a second Pd-guided [3,3] sigmatropic rearrangement (Figure 1c). [15] Last but not least, the saponification of ynamides under strong basic conditions provided ketenimines that were trapped in subsequent transformations [16] such as the addition of indoles, [16a] or the Imino-Staudinger reaction (Figure 1d). [16d] Figure 1. Resonance structures A/A' of ynamides; and ynamides as precursors of in situ generated ketenimine intermediates (a-d).

Some time ago, we reported the synthesis of 2aminoindoles from N-alkynyl-2-haloanilides by a Pd-catalyzed heteroannulation reaction. [8m] This diversity oriented approach encompassed the activation of ynamides through in situ formed -chelated palladium intermediates facilitating the addition of various primary and secondary amines to give 2-aminoindoles after reductive elimination.

As a part of our current efforts in the synthesis and application of 1,3-diynamides, [17] the extension of this 2aminoindole approach was investigated aiming to unravel the ethynylogous reactivity of 1,3-diynamides and gaining access to versatile functionalized 2-amino-3-alkynylindoles 2 (Scheme 1). However, by exploring this annulation sequence we realized that by increasing the basicity of the reaction medium an unprecedented reactivity mode of 1,3-diynamides was observed: Instead of the expected indoles 2 now 2-amino-4alkenylquinolines 3 were producedmost likely via [4]cumulenimine intermediates [18,[START_REF] Ghorai | For in situ azacumulene generation via reactions of terminal 1,3-diynes and azides[END_REF] . Scheme 1. Pd-catalyzed transformation of 1,3-diynamides 1 to 2-amino-3alkynylindoles 2 and its unprecedented reaction to 2-amino-4alkenylquinolines 3 via [4]cumulenimines.

In view of the significance of indoles [START_REF]The Chemistry of Indoles[END_REF] and quinolines [21] as privileged molecular platforms for drug discovery, divergent syntheses to these heterocyclic motifs allowing a great extent of structural diversity are important. Here, we report that the outcome of the reaction between 1,3-diynamide 1 and nucleophilic amines can be steered from the formation of 2-amino-3-alkynylindoles 2 to the selective construct of functionalized 2-amino-4alkenyl-quinolines 3 by just adding TBAF to the reaction medium while keeping all other reagents and conditions identical.

As a first experiment, the reaction of 1,3-diynamide 1a with 4-methylpiperidine, pre-catalyst Pd(PPh3)4 (10 mol%) and K2CO3 in THF was run at 70 °C for 12 h (Table 1, entry 1). The expected indole 2a was readily produced and isolated in 74% yield. With KOH as the base (solid KOH in THF) the reaction was faster and full conversion was reached after 2 h at 70 °C (76% yield; Table 1, entry 2). Switching the solvent to ethanol, in order to improve the solubility of KOH in the reaction medium, led to the full conversion of 1a after 1 h (reaction monitored by TLC). However, now a new compound -different from indole 2a -was formed selectively and isolated in 65% yield. It was identified as the 2-amino-4-alkenylquinoline 3a (Table 1, entry 3; for 2D NMR analysis, see supporting information). Moreover, now the indole 2a was not found.

Optimization favouring the formation of quinoline 3a was taken on: Small amounts of EtOH in THF sufficiently increased the solubility of KOH and promoted the formation of 3a (71% yield) during 1h at 70 °C (Table 1, entry 4). When THF was replaced by toluene the reaction was slowed down and the yield dropped to 55% (Table 1,entry 5). The effect of TBAF as additive aiming to improve the solubility of hydroxide anions in THF through counter ion exchange (Bu4NOH instead of KOH) was investigated. Gratifyingly, the reaction of 1a run in the presence of TBAF (10 equiv) in THF furnished 3a in 80% yield after 1 h at 70 °C (Table 1, entry 6). Clearly, the presence of TBAF boosted the formation of the 2-aminoquinoline 3a -and even 2.5 equivalents of TBAF with respect to substrate 3a were sufficient to promote the quinoline formation (Table 1,entry 7). It is noteworthy to mention, that the synthesis of 3a proceeded even at room temperature in the presence of TBAF, albeit with a lower yield of 49% (Table 1, entry 8).

As observed with 4-methylpiperidine as the nucleophile, the presence or absence of the additive TBAF prompted a switch in the reaction of 1a with primary and secondary amines. Without TBAF the 2-amino-3-alkynylindoles 2a-m were the exclusively formed products (Scheme 2). Morpholine, 1benzylpiperazine, acyclic dialkyl amines or N-methylanilines led to the corresponding indoles 2b-i in yields up to 98%. Conversion of 1a into the corresponding indoles 2a-h required 2-3 h heating (70 °C) with 10 mol% of Pd(PPh3)4 as the catalyst source and solid KOH as the base in THF. Notably, the unprotected alcohol function of 1c was tolerated and the indoles 2k and 2l were obtained in 83% and 99% yield with respectively morpholine and 2,2-dimethoxy-N-methylethanamine. Finally, the latter gave the 2-amino-3-alkynylindole 2m (93% yield) in the reaction with 1b (R 1 = (CH2)3OBn).

Table 1. Optimization of the synthesis of 2-amino-3-alkynylindole 2a and 2-amino-4alkenylquinoline 3a a Entry [a] Solvent Additive (equiv) Amine (equiv) t [°C] Time [h] 2a Yield [%] [b] 3a Yield [%] [b] 3a (E) / (Z) [c] 1 [d] [a] Reaction conditions: 1a (0.1 mmol), 4-methylpiperidine (2 equiv), Pd(PPh3)4 (10 mol%), KOH (2.5 equiv), Solvent (1mL). [b] Yield of isolated product after chromatography. [c] Isomer ratio determined from the 1 H NMR spectrum by integration of the olefinic proton signals assigned to the (E) and (Z) isomers. [d] reaction run without KOH. The scope of the 2-amino-4-alkenylquinoline-(3)-synthesis promoted by adding TBAF to the reaction medium was surveyed: Defined reaction conditions (10 mol% of Pd(PPh3)4, 2.5 equiv KOH, reaction temperature 70 °C) were applied to all transformations of 1,3-diynamide 1a (0.1 mmol in 1 mL of a commercially available 1M TBAF/THF solution) with various amines. Both, cyclic and acyclic secondary amines led to the corresponding 2-amino-4-alkenylquinolines 3a-i in 49 to 80% yield (Scheme 3). In all cases the major isomer had (E) configuration. The reaction proceeded also with the weaker nucleophilic N-methyl-para-methoxyaniline to afford the quinoline 3j in 34% yield. Furthermore, it was successful with primary amines to give the functionalized 2-amino-4-alkenylquinolines 3k-m (53-60% yield). The scope was further extended through variations in the 1,3-diynamide substrate -by substituents on the 1,3-diyne or the phenyl moieties. For example, the O-benzyl, O-3,5difluorobenzyl, or O-THP substituted 1,3-diynamide substrates 1b, 1d, and 1e effectively underwent this reaction to give the quinolines 3n-p with 2-diethylamine, 2-pyrrolidine, and 2-(4fluorobenzyl)methylamine, in 47, 55 and 44% yield respectively. The methyl group bearing 1,3-diynamide 1f and N-Bocpiperazine gave 2-amino-4-vinylquinoline 3q in 73% yield. Substitution of the phenyl ring of 1,3-diynamides by an electronwithdrawing or electron-donating group did not affect the efficiency of the synthesis as exemplified by the obtained 2amino-4-alkenylquinolines 3r-u (48-66% yield). The 1,3-diynamide 1c with its non-protected hydroxy moiety, however, yielded only trace amounts of 3v with decomposition of the starting 1,3-diynamide.

Scheme 3. Synthesis of quinolines 3a-u. The E/Z-ratio was determined via 1 H NMR spectroscopy by integration of the corresponding olefinic proton signals.

Deuterium labelling experiments were helpful to provide mechanistic insights into the conversion of 1,3-diynamides into 2-amino-4-alkenylquinolines. These experiments were performed with t-BuOK in CH3OD/THF to promote efficient H/D exchange with the amine NH proton and to exclude other proton sources that are obvious when using KOH as the base. Deuterium incorporation experiments with the 1,3-diynamides 1a, 1h, and 1i provided the deuterated quinolines 4a-c in yields of 64%, 57%, and 62% respectively (Scheme 4).

Scheme 4. Deuterium labelling experiment with in situ prepared N-deuterated pyrrolidine. Yields are given for the mixture of 3,11-bis-and the two monodeuterated products with a ratio of approx. 8:2 respectively.

The deuterium was selectively incorporated into the C3 and C11 positions of the quinoline product and this was evidenced by a very significant intensity decrease/disappearance of the corresponding 1 H-NMR signals at  = 6.58 (s, H-3) and 6.91 (broad d, H-11) for product 4b in comparison to the nondeuterated product 3t (for further details on the deuterium labelling experiments, see supporting information).

By considering the above deuterium labelling experiments, the mechanism outlined in Scheme 5 is proposed. Saponification of the 1,3-diynamide A with TBAF/KOH in THF gives the [4]cumulenimine B that after oxidative addition of the Pd(0)-catalyst to the chelated Pd-species C facilitates amine addition to give the allene derived intermediate D. Intramolecular Heck-type reaction furnishes the annulated-allyl-palladium species E. [START_REF] Guo | For carbopalladation of N-allenamides[END_REF]23] The latter undergoes -hydrogen elimination to produce the 2-amino-4-alkenylquinoline product. However, when the oxidative addition of the palladium catalyst to the iodophenyl moiety of the 1,3-diynamide (A→F) is faster than its detosylation (A→B) the -chelated palladium species F is formed activating the ynamide carbon-carbon triple bond and facilitating amine addition along the 2-amino-3-alkynylindole formation. In conclusion, we have developed divergent Pd-catalyzed reaction cascades for the selective synthesis of either 2-amino-3-alkynylindoles or 2-amino-4-alkenylquinolines from 1,3diynamides and primary or secondary amines. Starting from identical or similar substrates the outcome of the reaction giving either indole or quinoline motifs can be switched respectively by the absence or presence of TBAF. The in situ generation of [4]cumulenimine intermediates is proposed as a key step of the 2-amino-4-alkenylquinoline synthesis. This was supported by selective deuterium incorporation into the C3 and C11 positions of the quinoline products. Thus, a new reaction modethe in situ transformation of 1,3-diynamides into [4]cumulenimineswas revealed and this will open new exciting opportunities for the development of the chemistry of ynamides and [n]cumulenimines.

Scheme 2 .

 2 Scheme 2. Synthesis of indoles 2a-m. a K2CO3 (2.5 equiv), 12 h at 70 °C. b Cs2CO3 (2.5 equiv) and 10 equiv cyclopropylamine, 4 h at 80 °C.

Scheme 5 .

 5 Scheme 5. Proposed mechanism for the synthesis of 2-amino-4-alkenylquinolines involving the [4]cumulenimine B and the TBAF-free pathway to 2-amino-3alkynylindoles. H atoms (bold) indicate the positions identified by deuterium incorporation experiments.

Acknowledgements

This work was supported by the CNRS, Normandie Université, the Conseil Régional de Normandie, and the Fonds Européen de Développement Régional (FEDER).

Entry for the Table of Contents

Which coast to take? Divergent Pd-catalyzed reaction cascades with 1,3-diynamides and primary or secondary amines result by adding or omitting TBAF. In the absence of TBAF 2-amino-3-alkynylindoles are formedwhereas the addition of TBAF leads selectively to 2-amino-4-alkenylquinolines. The latter pathway involves the unprecedented formation of [4]cumulenimines from 1,3diynamides.