Keywords: Agnostic Feature Selection Dimensionality reduction, feature selection, unsupervised learning

Titre : S élection d'attributs agnostique Mots clés : R éduction de dimension, s élection d'attributs, apprentissage non supervis é Résumé : Les bases de donn ées dont la taille d épasse largement l' échelle humaine sont de plus en plus courantes. La surabondance de variables consid ér ées qui en r ésulte (amis sur un r éseau social, films regard és, nucl éotides codant l'ADN, transactions mon étaires...) a motiv é le d éveloppement des techniques de r éduction de dimensionalit é (DR). Une sous-cat égorie particuli ère de DR est form ée par les m éthodes de s élection d'attributs (SA), qui conservent directement les variables initiales les plus importantes. La mani ère de s électionner les meilleurs candidats est un sujet d'actualit é à la crois ée des chemins entre statistiques et apprentissage automatique. L'importance des attributs est g én éralement d éduite dans un contexte supervis é, o ù les variables sont class ées en fonction de leur utilit é pour pr édire une variable cible sp écifique. Cette th èse porte sur le contexte non supervis é de la SA, c'est-à-dire la situation épineuse o ù aucun objectif de pr édiction n'est disponible pour évaluer la pertinence des attributs. Au lieu de cela, les algorithmes de SA non supervis és construisent g én éralement un objectif de classification artificiel et notent les attributs en fonction de leur utilit é pour pr édire cette nouvelle cible, se rabattant ainsi sur le contexte supervis é. Dans ce travail, nous proposons un autre mod èle combinant SA non supervis ée et compression de donn ées. Notre algorithme AGNOS (Agnostic Feature Selection) ne repose pas sur la cr éation d'une cible artificielle, et vise à conserver un sous-ensemble d'attributs suffisant pour reconstruire l'int égralit é des donn ées d'origine, plut ôt qu'une variable cible en particulier. Par cons équent, AGNOS ne souffre pas du biais de s élection inh érent aux techniques bas ées sur le clustering. La seconde contribution de ce travail a est d' établir à la fois la fragilit é du processus supervis é standard d' évaluation de la SA non supervis ée ainsi que la stabilit é du nouvel algorithme propos é AGNOS.

Chapitre 1

Feature Selection in an unsupervised context

Data collection and processing have played an integral role in organized societies since antiquity, be it for recording taxes, managing cattle or organizing a military force. The advent of computers, however recent on the time scale of human History, has led to a paradigm shift ; data collection can now be performed automatically rather than manually. Additionally, dematerialized storage allows keeping record of unprecedented amounts of data.

Together, these two breakthroughs have led us to the Information era, in which data is gathered at an ever-growing rate. Consequently, a new challenge arose : the pace at which data is collected often vastly outscales the rate at which it can be processed. A notorious example of this issue is given by the CIA in the early 2000s, when the US federal agency accumulated large amounts of intelligence but lacked the manpower to analyze even a fraction of it. Accordingly, a new branch of research and industry dedicated to tackling this class of problems appeared in the last decade, and was named Big Data.

Rather than allocating evermore computational power to data processing, a cost-efficient way of handling large databases is provided by Dimensionality Reduction (DR). DR is informally defined as the process of compressing the information contained in the original high-dimensional dataset into a new data representation of lower dimension. Although DR predates computer science [START_REF] Pearson | On lines and planes of closest fit to systems of points in space[END_REF], it has become an increasingly prevalent tool in view of Big Data.

Context of the thesis

The presented work is concerned with automatic DR. The compressed data representation is discovered with Machine Learning (ML). The approach will rely on the basics of neural networks [START_REF] Haykin | Neural networks : a comprehensive foundation[END_REF].

A need for interpretability

As ML becomes more and more popular in varied application fields such as medical research, financial market prediction or weather forecast, it is increasingly important to the end user of ML to be able to make sense of the learning results. The motivation underlying this interpretability requirement is threefold.

The first desired property is fairness, corresponding to the absence of malicious or unwanted bias in the algorithm output (O'neil, 2016). Fairness has been a hotly debated topic in the past few years, for example in the US legal system ; the dangerousness of defendants and convicts is evaluated through risk assessment algorithms, and it was soon found that African-American citizens were on average assigned higher risk scores than for other origins. The question remained, however, to determine whether this discrepancy was the consequence of racist discrimination or the byproduct of other correlated factors such as firearm possession [START_REF] Skeem | Risk, race, and recidivism : predictive bias and disparate impact[END_REF]. Interpretability is therefore needed to assess the fairness of a learning agent.

The second desired property is transparency, which corresponds the understandability of a model. Transparency is especially useful in domains where Artificial Intelligence outperforms human experts, such as epilepsy prediction or the game of Go [START_REF] Deepmind | Alphago[END_REF]. In order for physicians to improve their own diagnoses or Go players their own skill, they need to understand why the ML algorithm makes certain decisions. In other words, interpretability is required for humans to learn from the machine.

The third desired property is accountability, such that there is clarity regarding who holds responsibility of the decisions made by the algorithm. The need for accountability was recently highlighted, with the first fatal accident involving a self-driving car happening in early 2018. Detailed analysis of the driving model is required in order to determine if the algorithm is faulty and if the car passenger is to blame. Moving forward, interpretability will thus become even more crucial, as ML algorithms become trusted with vital decisions.

Accordingly, the ML community as a whole is increasingly concerned with Fair, Transparent and Accountable (FTA) learning, for both research (Doshi-Velez and [START_REF] Doshi-Velez | Towards a rigorous science of interpretable machine learning[END_REF] and industry [START_REF] Fta | Fair, transparent and accountable learning[END_REF] purposes. The aim of the presented work is thus to achieve FTA DR.

In order to perform efficient information compression, DR techniques typically produce new variables, thereafter called features, that are obtained from the original features via an arbitrarily complex mapping. Following this unconstrained functional complexity, the resulting features are in the general case hardly interpretable by humans, regardless of their expertise.

Consequently, this thesis is concerned with a particular case of DR called Feature Selection (FS). Instead of producing new composite features, FS methods filter out the least promising original variables, retaining only the best candidates. The result of FS is therefore a subset containing interpretable features (assuming the original data was interpretable to begin with), such as e.g. {age, smoker} for a lung cancer prediction task on medical data. FS is therefore more appropriate than generic DR (often called Feature Construction (FC)) to achieve FTA learning.

The unsupervised context

Three particular different ML settings are relevant to this work : supervised, semi-supervised and unsupervised. In the supervised case, the end goal of learning is fully known. Consider for instance a visual recognition task where the learning agent is presented with pictures of street traffic and tasked with identifying pedestrians, given that the human expert knows all the correct answers.

In the semi-supervised setting, only a few correct answers are available. This is the case of the lung cancer prediction task example. Physicians can tell that patients with visible symptoms are ill, but are uncertain about healthy-looking cases.

In the unsupervised setting, no ground truth is available at all. Furthermore, the final goal of learning is itself unknown. Using the previous illustrating example, this means the learning agent does not know whether the medical data will ultimately be leveraged for lung cancer prediction, breast cancer prediction, or possibly something else entirely.

One may then wonder what the purpose of unsupervised learning is. If we do not even know what we want ourselves, how could ML be of any help ? An answer to this questioning is provided by the following argument, made by G. Hinton in 1996 :

"When we're learning to see, nobody's telling us what the right answers are -we just look. Every so often, your mother says "that's a dog", but that's very little information. You'd be lucky if you got a few bits of information -even one bit per second -that way. The brain's visual system has 10 14 neural connections. And you only live for 10 9 seconds. So it's no use learning one bit per second. You need more like 10 5 bits per second. And there's only one place you can get that much information : from the input itself".

In other words, life is at best a semi-supervised learning experience. Furthermore, supervised learning is very limited in terms of scalability due to the scarcity of ground truth information. Yet, cognitive mammals are able to learn quickly and efficiently using only their sensory inputs. This shows that unsupervised learning is actually a powerful tool, and is well-suited for real-world applications. The power and crucial importance of the unsupervised context has been further underlined by Y. [START_REF] Lecun | The next frontier in AI : Unsupervised learning[END_REF], essentially arguing that supervised learning is merely the tip of the iceberg, while unsupervised learning forms the submerged part.

Consequently, this thesis is mainly focused on unsupervised FS. This setting is however particularly challenging for the sake of interpretability, given the absence of a definitive goal shedding light on the results. For instance, the previous selection subset {age, smoker} is easily understandable for lung cancer prediction purposes, but less so without knowledge about the objective.

In order to comply with the FTA learning requirement, defining a clear unsupervised goal is therefore of paramount importance. Designing such a goal and demonstrating its soundness will in the following prove to be a cornerstone of the presented work.

Motivation

As previously mentioned, DR is a useful tool in a wide range of applications, such as banking, genomics research, online advertising, power grids or video game development. DR is essentially required for any Big Data endeavor ; as soon as one is concerned with large amounts of input information, FS should at least be considered as a pre-processing option.

Furthermore, as the computational power of CPUs and GPUs keeps increasing, private companies and governments alike pursue collection of more and more data, in the hopes that their data processing capabilities will eventually cease to be a bottleneck.

Moreover, the recent advent of cloud computing is an additional incentive for indiscriminate data harvesting, given the resulting boost of storage capacity. A telltale example of this trend is provided by Walmart (the world's biggest retail company), owner of the largest private cloud on the planet, which is able to process 2.5 petabytes of consumer data per hour. This means that the company is recording millions of tidbits of information (features) about each of their clients, not all features being equally interesting. There is thus little doubt that DR algorithms, and more specifically FS methods, play a large role in the data processing pipeline.

Consequently, even though our contributions were so far applied only to comparatively much smaller real-world datasets (spanning medical data, image data and text data), we expect unsupervised FS to be of potential use in a wide array of different domains moving forward.

Main contributions and organization of the work

The first contribution presented in this manuscript is algorithmic. The goal is to design a method bridging the gap between FC and FS, leveraging the constructed variables to guide the selection.

The second contribution is methodological in nature, and pertains to the evaluation procedure of unsupervised FS. We claim and empirically show that the typical performance assessment scheme is unreliable, and propose a more adequate stable efficiency criterion to rely on instead.

Performing unsupervised FS

The most common approach consists of i) performing spectral clustering (?) to equip the datapoints with pseudolabels ; ii) falling back on supervised techniques, select the features best able to predict the pseudo-labels. Still, the reliability and robustness of the clusters is not guaranteed. This manuscript investigates an alternate approach, called Agnostic Feature Selection (AGNOS), that does not rely on pseudo-labels.

Inspired by regularized regression [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF][START_REF] Simon | A sparse-group lasso[END_REF] and feature selection based on neural networks [START_REF] Verikas | Feature selection with neural networks[END_REF][START_REF] Roy | Feature selection using deep neural networks[END_REF][START_REF] Li | Deep feature selection : theory and application to identify enhancers and promoters[END_REF], the proposed AGNOS combines Auto-Encoders with structural regularization, and delegates the combinatorial optimization problem at the core of feature selection to a regularized data compression scheme.

Assessing unsupervised FS

The efficiency and relevance of unsupervised FS are usually estimated within a supervised learning setting. Accordingly, the ranking of different selection algorithms depends on the supervised goal.

In order to address this limitation, we introduce a novel performance indicator, called FIT, that corresponds to an unsupervised learning setting. Unsupervised FS algorithms are ranked w.r.t. the informativity of the respective selection subsets to retrieve the whole initial feature set.

Thesis outline

Chapter 2 introduces the general background of the DR problem setting and presents the concept of intrinsic data dimension.

Chapter 3 provides an overview of the DR field and focuses on the positioning of unsupervised FS approaches with respect to other FC techniques.

Chapter 4 introduces the proposed unsupervised FS method AGNOS, including its three declinations AGNOS-S, AGNOS-W and AGNOS-G, each corresponding to a particular structural regularization scheme.

Chapter 5 discusses the prominent supervised performance indicators for assessing unsupervised FS, and introduces the proposed FIT.

The experimental validation of the three versions of AGNOS is described and discussed in chapter 6. The empirical results of AGNOS are compared to baselines both w.r.t. the typical supervised indicators and the proposed unsupervised criterion. The sensitivity of the performance indicators w.r.t. the hyperparameters of the method is also assessed.

Chapter 7 concludes the thesis with a summary of our contributions and a discussion of further perspectives.

Chapitre 2

Dimensionality Reduction : formal background

This chapter first introduces the general setting of Dimensionality Reduction (DR), the main associated challenges and a tentative taxonomy of DR methods in section 2.1. An important hyperparameter of DR techniques is the dimensionality of the resulting low-dimensional data representation, which is tied to the intrinsic dimension (ID) of the dataset. Consequently, section 2.2 provides an overview of the ID estimation field. Lastly, section 2.3 concludes the chapter with a discussion of the presented concepts and methods.

Setting

The following definitions and notations will be used throughout the entirety of this work.

Notations Given strictly positive integers n and D, let X ∈ R n×D denote a dataset containing n samples (x 1 , . . . , x n ), each x i corresponding to a point in a D-dimensional space. ∀(i, j) ∈ [1, . . . , n] × [1, . . . , D], the coordinate of the i-th datapoint on the j-th dimension is denoted as f j (x i ). ∀j ∈ [1, . . . , D], the n-dimensional vector f j = (f j (x 1 ), . . . , f j (x n )) is called the j-th feature. F = {f 1 , . . . , f D } is called the original feature set.

Performing dimensionality reduction is in essence finding a new feature set containing fewer elements than the original s.t. "information" is preserved. In order to be theoretically well-grounded, all DR algorithms rely on the following underlying hypothesis, thereafter referred to as the manifold assumption :

The manifold assumption The D-dimensional datapoints x 1 , . . . , x n lie near a manifold M d * of dimension d * s.t.

d * << D.
Dimensionality reduction techniques can be categorized with respect to the kind of information they aim to preserve. For instance, Principal Component Analysis (PCA) attempts to capture the variance in the data, while Locally Linear Embedding (LLE) [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF] is concerned with preserving the pairwise distances between points (more in chapter 3). The cost function C measures the loss of information occurring due to the change of representation from F to Z * d . Along this setting, three main questions are addressed in order in the following sections :

-Should the search for Z * d span the entirety of H d , or should it be restricted to a particular subset of H d ?(section 2.1.1) -How should C be defined ?(section 2.1.2) -How should d be determined ?(section 2.2)

Constraining the search : Feature Construction and Feature Selection

The general case of DR where there are no restrictions put on H d is called Feature Construction (FC)1 . FC techniques are well-suited to perform efficient data compression. However, the results are hardly interpretable, given that the mapping between the original features (elements of F ) and the new ones (elements of Z * d ) is potentially non-linear and arbitrarily complex. In the light of the growing need for fair, transparent and accountable (FTA) learning (Doshi-Velez and [START_REF] Doshi-Velez | Towards a rigorous science of interpretable machine learning[END_REF] underlined in chapter 1, recent years saw a rise of popularity of the particular case of Feature Selection (FS). In this setting, the search for Z * d is restricted to the subsets of F containing d elements :

Z * d = arg min Z d ⊂F |Z d |=d C(F, Z d ) (2.2)
In other words, the new features are selected among the original ones. As such, the results of FS are typically easier to interpret than in the general case of FC2 . Furthermore, equation (2.2) defines a combinatorial problem ; the goal is to find the best candidate from the C d D subsets of F containing d elements (each original feature being either rejected or retained). Exhaustive exploration being too expensive computationally-wise, FS techniques rely on C to quickly orient the search towards a selection subset Z * d s.t. :

C(F, Z * d ) -C(F, Z * d ) ≤ , with ∈ R + *
The main challenge of FS is thus to preserve the desired "information" originally contained in F while simultaneously tailoring the cost function C so that the approximation Z * d is as accurate as possible, under the constraint of an affordable time complexity budget.

Defining the cost function : Supervised and unsupervised DR

In the event that the end goal of learning is known at the time of DR, this objective defines an additional target feature3 , which can be leveraged to design the cost function C. Consider a FS task on medical data for the purpose of predicting a certain disease among the patients. If one knows which patients are affected by the disease, then C should reflect the usefulness of the original features for discriminating between ill and healthy patients. This idea is the motivation of the early Fisher score [START_REF] Duda | Pattern classification[END_REF] approach. Considering for instance the age feature. Let age denote its mean across the whole dataset, and age h , σ h , age i , σ i its mean and variance on the respective subsets of the n h healthy and n i ill patients. Then the cost of the {age} selection subset singleton w.r.t. the Fisher score is given by :

C({age}) = n h σ h + n i σ i n h (age h -age) 2 + n i (age i -age) 2
The older (or younger) the ill patients relatively to the healthy ones, the more important the age variable. Exploiting the learning goal in this way to define C corresponds to the most extensively studied problem in the literature, called supervised DR.

An alternate setting, lower in popularity despite its crucial importance (LeCun, 2016) as highlighted in chapter 1, corresponds to the case where no learning goal is available. Such a context is referred to as unsupervised, in which C is harder to define (more in chapter 3).

Discussion

Following the discussions of sections 2.1.1 and 2.1.2, a tentative taxonomy of DR methods is proposed in Figure 2.1.

FIGURE 2.1: High-level Taxonomy of Dimensionality Reduction methods

This is in line with the typical point of view in the DR literature, where FS is treated as a concept separate from FC rather than a particular case. Here, this setting is adapted for the sake of a clear and streamlined presentation. However, an important aspect of our algorithmic contribution is to cross the gap between FC and FS (chapter 4).

The resulting four categories of DR algorithms, namely Supervised FC, Unsupervised FC, Supervised FS and Unsupervised FS will be discussed in chapter 3, along with some of the most prominent approaches for each category.

Following the manifold assumption, FC can be interpreted as the task of projecting the datapoints onto the latent manifold. Therefore, it naturally comes that hyperparameter d should be s.t. d ≈ d * . Consequently, the task of tuning d is closely tied to estimating the dimension of the underlying manifold4 . This can in turn be cast to a problem of intrinsic dimension estimation, which we will focus on in the following section.

Intrinsic dimension

The intrinsic dimension (ID) of a dataset is an informal concept commonly defined in Machine Learning5 as : Definition 1. The intrinsic dimension ID(X) of dataset X ∈ R n×D is the minimum number of features required to represent X with negligible loss of information w.r.t. the original D-dimensional representation.

After this definition, the intrinsic dimension should be an integer and bounded by D. It will be seen that continuous ID is also of interest. After the manifold assumption, ID should by construction match the dimension d * of the underlying manifold, s.t. ∀X ∈ R n×D , ID(X) = d * . Turning definition 1 into a formal definition proves to be challenging, as underlined by [START_REF] Pestov | Intrinsic dimension of a dataset : what properties does one expect ? International Joint Conference on Neural Networks[END_REF] :

"A search for the "right" concept of intrinsic dimension of a dataset is not yet over, and most probably one will have to settle for a spectrum of various dimensions, each serving a particular purpose, complementing each other".

To the best of our knowledge, there is no unifying framework for the concept of ID as of yet, even though promising new approaches have been proposed in the last decade [START_REF] Facco | Estimating the intrinsic dimension of datasets by a minimal neighborhood information[END_REF]. Additionally, authors often use their own taxonomy of ID estimators ; [START_REF] Facco | Estimating the intrinsic dimension of datasets by a minimal neighborhood information[END_REF] differentiate between fractal and neighborhood-based methods, and we will partially rely on their categorization. Note that e.g. [START_REF] Campadelli | Intrinsic dimension estimation : Relevant techniques and a benchmark framework[END_REF] refer to other distinctions such as projection and topological techniques, interpreted as global vs local estimates. In order to provide an overview of the ID estimation field, we will in the following rely on the tentative taxonomy from figure 2.2.

One may argue that the boundary between fractal and neighborhood-based methods is slim, as it will be shown in sections 2.2.2 and 2.2.3 that both share the core idea of "zooming in" on the samples and providing local ID estimates. This argument is the main reason for the varying taxonomies of ID estimators found in the literature.

Sparsity-based methods are concerned with estimating the impact on the pairwise distances between dataset samples of the curse of dimensionality, which we will now discuss.

The curse of dimensionality and sparsity-based ID estimation

The expression "curse of dimensionality" was coined by Richard E. Bellman to describe various phenomena arising in high-dimensional spaces that hinder typical data analysis. Among these adverse effects, the sparsity issue is the one most prominently considered in ML, and is informally described as : Definition 2. As the dimensionality of a dataset grows, samples become more and more spread apart. Eventually, all datapoints are equally far away from each other. The mathematical characterization of the root cause of this sparsity phenomenon is beyond the scope of this thesis. For the sake of completeness, we refer the interested reader to [START_REF] Pestov | On the geometry of similarity search : dimensionality curse and concentration of measure[END_REF] for a more formal explanation of the curse of dimensionality through the lens of the so-called concentration of measure.

Given the low variance in pairwise distance, every data sample has many equally remote "close" neighbors. Therefore, the sparsity property is typically harmful to ML algorithms relying on clustering, or more generally investigating local structure. Considering that this issue is mitigated or even absent in low-dimensional spaces, this provides an additional motivation to perform DR, besides those discussed in chapter 1 : escaping the curse of dimensionality.

The goal of a sparsity-based ID approximation is thus to quantify how much the dataset is plagued by the sparsity effect. Ch ávez et al. ( 2001) provided a simple estimator using the notations from definition 3 :

ID sparse (X) = µ D (X) 2 2σ D (X) 2 (2.3)
The stronger the sparsity effect in X, the larger ID sparse (X). Given that this ID estimation is both quite intuitive and computationally inexpensive, the ID sparse has become a popular tool in the ML community 6 . By contrast with the informal definition ID(X) ∈ N * , the above formula does not necessarily return an integer (and can return 0 in pathological cases), that is ID sparse (X) ∈ R + . Although a non-integer dimension may seem counterintuitive, this is in line with fractal dimensions, which we will now introduce and discuss.

Fractal-based ID estimation

Though seemingly unrelated, DR and fractal geometry [START_REF] Mandelbrot | The fractal geometry of nature[END_REF] bear some similarities, that we will now exhibit. As per the manifold assumption, DR relies on the hypothesis that there is a disconnect between the representation dimension D of dataset X and its "true" dimension ID(X).

On the other hand, fractals can be represented in 2D or 3D, such as the notorious real-life example of a snowflake (fig. 2.4), or the artificial Julia set (fig 2.5). Given that these two entities can be drawn on a sheet of paper, their representation dimension, thereafter called topological dimension, is D = 2.

This does not however provide us with any insight regarding whether these two objects are equally "complex" fractal patterns. Therefore, an additional concept to characterize complexity in a fractal, called fractal dimension [START_REF] Mandelbrot | The fractal geometry of nature[END_REF]) is needed, as informally defined in definition 4 : Definition 4. The fractal dimension of any geometrical object is the rate at which details in the pattern change with the scale of measure.

In other words, assume a magnifying glass is at one's disposal. The fractal dimension of the snowflake corresponds to the speed at which it becomes more detailed as one zooms in on a small region, w.r.t. the optical power of the lens.

A well-studied real-world illustration of this concept is provided by the problem of measuring the length of the coastline of Great Britain [START_REF] Mandelbrot | How long is the coast of britain ? statistical self-similarity and fractional dimension[END_REF], as shown in figure 2.6.

As the size of the segments used to approximate the coastline pattern decreases, the total measured length increases. The ratio between the two quantities is a tentative definition of the intrinsic dimension of Great Britain.

In light of definition 4, the link between fractal geometry and DR is made clearer ; the intrinsic dimension of a dataset can be thought of as the rate at which samples become simpler to depict as one closes in on the datapoints. The concept of fractal dimension can thus be transposed to the context of DR [START_REF] Camastra | Estimating the intrinsic dimension of data with a fractal-based method[END_REF][START_REF]Intrinsic dimension estimation using packing numbers[END_REF] in ML to approximate ID(X). Similarly as for the ID, numerous formal definitions of the fractal dimension were proposed over the years.

Box-counting dimension

The most well-known fractal dimension estimator is the box-counting dimension (also sometimes referred to as Minkowski dimension), which is illustrated in figure 2.7. The process consists in covering the dataset with square-like boxes of side length , then observing how the number N ( ) of boxes needed to achieve full coverage increases as decreases :

ID box (X) = lim →0 log(N ( )) log( 1 ) (2.4) Informally, this means that if X contains n samples, ID box (X) is the exponent of the power law such that N ( 1 n ) ∝ n ID box (X) .
Hausdorff dimension An alternative to the box-counting dimension is provided by the Hausdorff dimension, which relies on balls rather than square boxes, as illustrated in figure 2.8. Defining S(X) the (infinite) set of possible covers of X by balls centered on the datapoints, each ball being associated to its radius r i > 0, the Hausdorff content of X is defined as :

C d (X) = inf S(X) ri r d i (2.5)
The Hausdorff dimension of X is then given by :

ID Hausdorff (X) = inf d≥0 C d (X) = 0 (2.6)
The underlying idea is thus to cover the dataset with progressively smaller spheres, and observe how the total volume of the coverage decreases as the spheres shrink. Therefore, despite having a less intuitive definition, the Hausdorff dimension is conceptually close to the box-counting dimension. Interestingly enough, these two quantities are linked by the following inequality :

∀X ∈ R n×D , ID Hausdorff (X) ≤ ID box (X) (2.7)
Even though ID Hausdorff (X) = ID box (X) in most cases, the equality does not necessarily hold (e.g. considering Q the set of rational numbers, ID Hausdorff (Q) = 0 whereas ID box (Q) = 1).

Discussion

Both fractal dimensions presented above are hardly affordable in practice in terms of computational complexity. In order to address this issue, the correlation dimension [START_REF] Camastra | Estimating the intrinsic dimension of data with a fractal-based method[END_REF] and packing dimension (K égl, 2003) were designed by the ML community as computationally efficient variants of respectively the box-counting and Hausdorff dimensions.

An additional benefit of the fractal geometry framework is to shed light on the counter-intuitive notion of a noninteger intrinsic dimension, as was first showcased in section 2.2.1 ; the rate at which details appear in a fractal is not necessarily a multiple of the zoom multiplier. Going back to the Koch snowflake example, the total length of the pattern contour increases by a factor 4 every time the scale is enhanced by a factor 3. Therefore, the Koch snowflake is considered of fractal dimension log(4)/log(3) ≈ 1.27.

Global and local ID estimates

There is an important contrast in terms of methodology between sparsity-based and fractal-based methods. The technique from Ch ávez et al. ( 2001) is only concerned with the histogram of pairwise distances of X, thus considers the ID on the global scale and assumes it is invariant across the samples. By contrast, fractal-based methods investigate the complexity of each individual sample. The final ID(X) is therefore actually an aggregate of multiple estimations made on the local scale. This is tied to the underlying assumption that the ID dimension of a dataset is fluctuating across the different regions of the representation space. For example, it is likely that the ID of a cluster near the origin (meaning all feature values are simultaneously close to 0) differs from outliers. This idea FIGURE 2.9: An example of Geodesic Minimal Spanning Tree on a Swiss Roll. Image taken from [START_REF] Costa | Geodesic entropic graphs for dimension and entropy estimation in manifold learning[END_REF].

that one must examine the ID on a local basis forms the basis of neighborhood-based ID estimators, which we will now introduce.

Neighborhood-based ID estimation

Early neighborhood-based ID estimators [START_REF] Pettis | An intrinsic dimensionality estimator from near-neighbor information[END_REF][START_REF] Verveer | An evaluation of intrinsic dimensionality estimators[END_REF] directly relied on the Euclidean distance in the original representation space of the dataset to detect neighborhoods. However, following section 2.2.1, the sparsity effect caused by the curse of dimensionality prevents this strategy from being sound in high-dimensional spaces. In order to provide reliable results, one must therefore devise alternate ways of detecting neighborhoods.

To that end, [START_REF] Costa | Geodesic entropic graphs for dimension and entropy estimation in manifold learning[END_REF] rely on a popular unsupervised Feature Construction method called Isomap (more in chapter 3). The idea is to aggressively prune the pairwise sample similarity graph provided by Isomap, so that all datapoints remain connected using as few edges as possible. An illustration of this process is provided in figure 2.9, on the well-known Swiss Roll artificial dataset. Despite being originally generated and represented in a 3D space, this manifold can be "unfolded" and mapped to a 2D space. Most ID estimators will therefore return ID(SwissRoll) ≈ 2.

The pruned similarity graph is called a Geodesic Minimal Spanning Tree (GMST). It has been shown [START_REF] Costa | Geodesic entropic graphs for dimension and entropy estimation in manifold learning[END_REF]) that the depth of this tree can be used to approximate the intrinsic dimension of the manifold. The main shortcoming of the GMST approach is that the quality of its ID estimation depends on the accuracy of the similarity graph provided by Isomap. Unfortunately, Isomap has been experimentally demonstrated [START_REF] Balasubramanian | The isomap algorithm and topological stability[END_REF] to be topologically unstable, meaning a small error in neighborhood assessment (relying still on the Euclidean distance) can lead to a large error in the final graph.

Consequently, the GMST approach has decreased in popularity to the benefit of Maximum Likelihood Estimation (MLE) [START_REF] Levina | Maximum likelihood estimation of intrinsic dimension[END_REF]. This technique relies on the assumption that if one "zooms in" on a particular datapoint x, then the density f (x) of samples in this region is roughly constant in a ball S x (r) centered on x with a small radius r, s.t. f (x) ≈ C everywhere in S x (r). The idea is then to consider the samples as an homogenous Poisson process in S x (r). The number N (x, r) of datapoints inside S x (r) is then s.t. N (x, r) ∝ Cr d(x) . Here, d(x) denotes the dimension of sphere S x (r) and corresponds to the local ID at point x. Given a fixed sphere radius r 0 , the final ID approximation ID M LE is then simply obtained by averaging the local estimators :

∀X ∈ R n×D , ID M LE (X) = 1 n x∈X d(x) (2.8)
As said, the MLE ID estimator relies on the strong assumption of locally constant sample density. In practice, the more inhomogenous the underlying Poisson process, the less accurate ID M LE .

Building upon the MLE technique, [START_REF] Facco | Estimating the intrinsic dimension of datasets by a minimal neighborhood information[END_REF] proposed a neighborhood-based ID estimator that only relies on the two closest neighbors of each point, denoted ID 2N N . This essentially means that the homogenous Poisson process assumption needs only to hold in smaller spheres than before. ID 2N N is therefore better suited than ID M LE to deal with non-smooth manifolds.

Similarly as before, ID 2N N (X) is obtained by averaging local estimates d(x). However, rather than from counting the number of samples in S(x, r 0 ), d(x) is derived from the volume of the hyperspherical shell enclosed between the closest and second closest neighbors of x, as illustrated in figure 2.10. Before averaging the local results, the top 10% ranked datapoints w.r.t. the ratio r2 r1 are discarded. This essentially means that samples with only one close neighbor are ignored, given that these are likely to be outliers and would skew the final estimator ID 2N N .

An additional benefit of the 2 -N N method over traditional MLE estimation is the reduced computational cost ; [START_REF] Muja | Scalable nearest neighbor algorithms for high dimensional data[END_REF] have shown that dedicated algorithms were able to find the first two neighbors of n points in approximately O (nlog(n)) time.

Discussion

As discussed above, the boundary between fractal and neighborhood is slim, e.g. the pioneer MLE estimator from [START_REF] Levina | Maximum likelihood estimation of intrinsic dimension[END_REF] is referred to as a fractal-based technique in [START_REF] Facco | Estimating the intrinsic dimension of datasets by a minimal neighborhood information[END_REF].

Criteria for ID estimation

As shown, ID estimation is key to DR. In this context, the criteria for choosing an adequate ID estimator include :

-Affordable computational cost (both time and space-wise) -Resilience w.r.t. the sparsity effect of the curse of dimensionality -Accuracy of the results : ID should be close to the dimension d * of the latent manifold

The sparsity-based estimator from Ch ávez et al. ( 2001), the correlation dimension (?) and the packing dimension (K égl, 2003) all meet the first criterion. However, it has since been demonstrated [START_REF] Pestov | Intrinsic dimension of a dataset : what properties does one expect ? International Joint Conference on Neural Networks[END_REF] that the resulting ID is not necessarily close to d * ; all these techniques thus fail to meet the accuracy criterion. Additionally, correlation and packing dimensions are also sensitive to the sparsity effect [START_REF] Pestov | Intrinsic dimension of a dataset : what properties does one expect ? International Joint Conference on Neural Networks[END_REF].

By contrast, the 2 -N N method [START_REF] Facco | Estimating the intrinsic dimension of datasets by a minimal neighborhood information[END_REF] is both inexpensive computationally-wise and resilient to the sparsity effect. Furthermore and to the best of our knowledge, ID 2N N is empirically a close approximation of d * , in cases where ground truth knowledge about the dimension of the underlying manifold is known. Therefore, we will in the context of this thesis rely on the 2 -N N approach for the purpose of ID estimation. The discussion of this chapter should however not make us forget that many authors [START_REF] Guyon | Gene selection for cancer classification using support vector machines[END_REF][START_REF] Li | Deep feature selection : theory and application to identify enhancers and promoters[END_REF][START_REF] Ye | Variable selection via penalized neural network : a drop-out-one loss approach[END_REF] instead proceed manually or iteratively to tune d.

Alternate visual-based tuning of d d can be tuned relying e.g. on Principal Component Analysis (PCA) using a grid search process. The idea would be to perform a PCA of the original data for different number of principal components (corresponding to the constructed features), then visually examine the smoothness of the respective covariance matrices spectra. In the example provided in figure 2.11, the large gap between the leading eigenvalues and the tail of the spectrum for d = d 1 indicates that some of the constructed features are much less important than the others for capturing the variance in the data. Therefore, d should be lowered until the spectrum becomes smooth, as is the case for d = d 2 .

This "trial-and-error" technique come with the significant downside of being computationally expensive, given that the FC algorithm relied upon must be ran many times to obtain accurate results. This approach is therefore ill-advised in view of Big Data.

Online selection subset size calibration Another possibility exclusive to FS is to forego ID estimation and determine the number of features to select online, that is during the execution of the FS algorithm. This is a popular solution in supervised FS. In the Drop-Out-One approach (Ye and Sun, 2018) (more in chapter 3) for instance, features are greedily eliminated until the resulting change in predictive accuracy of the target features becomes lower than a threshold.

To the best of our knowledge, this type of technique has not yet been proposed for the unsupervised context, where a suitable stopping criterion is harder to define. This defines a direction for future research (chapter 7).

Chapitre 3

Dimensionality reduction : overview

Based on the formal background on Dimensionality Reduction (chap. 2), this chapter presents the state-of-the-art in Feature Extraction (FC) (section 3.1) and Feature Selection (FS) (section 3.2), in both supervised and unsupervised contexts (thereafter abbreviated as sup. and unsup.). A brief review of some of the most impactful and popular approaches is provided for each of the four problem settings. The chapter concludes with a discussion on the strengths and limitations of the aforementioned methods, coupled with the main lessons learned.

An important methological difference between FC and FS lies in the way sup. and unsup. learning are perceived. In the general FC context, unsup. historically came first, with early methods such as PCA [START_REF] Pearson | On lines and planes of closest fit to systems of points in space[END_REF], and remains the main focus of the literature. Sup. learning is then layered on top of unsup., and label information is taken advantage of as much as possible.

On the other hand, FS is most often studied in the sup. context. The absence of labels is seen as a handicap. Unsup. FS therefore aims to build pseudo-label information in order to fall back on sup. learning.

Accordingly, section 3.1 will introduce unsup. FC methods first, followed by sup. approaches. By contrast, section 3.2 begins with sup. FS and presents unsup. techniques afterwards.

Feature Construction

Following the general problem setting exposed in chapter 2 and using the same notations, DR aims to find a mapping φ * : F → H d s.t. φ * (F ) = Z * d minimizes cost function C. FC is not limited to "sparse filters" mappings selecting a subset of the initial features (as is FS). Instead, φ * can correspond to either a linear combination of the initial features or an arbitrarily complex non-linear function thereof.

Unsupervised FC

Linear mappings

Principal Component Analysis Perhaps the most well-known DR technique overall is the Principal Component Analysis (PCA) algorithm (fig 3.1), an early approach dating back to the 19th century and formalized by [START_REF] Pearson | On lines and planes of closest fit to systems of points in space[END_REF]. Assuming the original features have been preemptively centered and given the data covariance matrix X T X, the constructed features (referred to as principal components) are given by the columns of matrix Z s.t. Z = XW , where W contains the eigenvectors of X T X. In order to perform DR, only the d leading eigenvectors are considered, s.t. Z d = XW d is now a n × d matrix 1 The underlying idea is that provided d is well-tuned (see section 2.2), the leading eigenvectors are sufficient to capture most of the variance in the data. As said in chapter 2, DR methods can be categorized by the kind of "information" they respectively aim to preserve. Accordingly, the purpose of PCA is to accurately depict correlations between original features. FIGURE 3.1: A 2D example of PCA applied to the picture of a fish. From Wikipedia.

Singular Value Decomposition

The Singular Value Decomposition (SVD) of X ∈ R n×D is given by X = U ΣV , where U and V are orthogonal matrices of respective dimensions n × n and D × D, and Σ a n × D diagonal matrix. The diagonal entries of Σ (the singular values of X) are the square roots of the non-zero eigenvalues of X T X.

In order to perform DR (as well as greatly reduce the computational cost), only the d largest singular values and corresponding singular vectors are computed in the truncated SVD [START_REF] Golu | Singular value decomposition and least squares solutions[END_REF]

, s.t. X = U d Σ d V d . The constructed features then correspond to the rows of V d .
Interestingly enough, SVD is equivalent to PCA if the original features have been preemptively centered to zero mean. However, centering is ill-advised in some cases, e.g. image processing tasks where features correspond to positive pixel intensity values ; mean centering transforms null values into high amplitude negative values, artificially increasing the (usually low) importance of the corresponding features. SVD is therefore usually preferred over PCA in this setting.

Multi-Dimensional Scaling

Multi-Dimensional Scaling (MDS) [START_REF] Torgerson | Theory and methods of scaling[END_REF][START_REF] Borg | Modern multidimensional scaling : Theory and applications[END_REF] follows a different line of thought to PCA and SVD ; the goal is to preserve the likeness of samples (rather than the correlations between features). Accordingly, the input of the method is a similarity matrix containing the pairwise Euclidean distances between datapoints, which spectral decomposition produces the constructed features. The notion of similarity matrix is also central to unsup. FS, and the associated theory of spectral clustering (Von [START_REF] Luxburg | A tutorial on spectral clustering[END_REF] will be presented in more detail in section 3.2.3.

Discussion

Over the years, the three aforementioned techniques have been further refined into many computationally efficient variants such as the k-SVD [START_REF] Aharon | K-svd : An algorithm for designing overcomplete dictionaries for sparse representation[END_REF] or the generalized MDS [START_REF] Bronsteina | Generalized multidimensional scaling : a framework for isometry-invariant partial surface matching[END_REF]. However, a core limitation remains : the mapping φ * resulting of any of PCA, SVD or MDS is linear. As such, these methods are illadvised for performing DR on non-linear manifolds. An example of unwanted behavior is provided in figure 3.2 on an artificial Swiss Roll dataset (see section 2.2.3), which a standard PCA is unable to properly unfold.

Non-linear mappings

Isomap Isomap [START_REF] Tenenbaum | A global geometric framework for nonlinear dimensionality reduction[END_REF] is an extension of MDS designed to handle non-linear manifolds, taking note of the unreliability of the Euclidean distance (panel A of figure 3.3). The similarity matrix is first translated into graph As mentioned earlier (section 2.2.3), Isomap has quickly been shown to be topologically unstable [START_REF] Balasubramanian | The isomap algorithm and topological stability[END_REF], meaning that adding a small perturbating noise to the data is sufficient to greatly corrupt the associated similarity graph, and consequently the constructed features (figure 3.4).

Locally Linear Embedding Locally Linear Embedding (LLE) [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF][START_REF] Saul | Think globally, fit locally : unsupervised learning of low dimensional manifolds[END_REF] first defines the local structure of the n data points x i ∈ R D , through approximating each point as the barycenter of its k nearest neighbors. The goal is then to find points y 1 , . . . y n in R d , such that the y i satisfy the same local relationships as the x i s. Formally, let N (i) denote the set of indices of the k nearest neighbors of x i . The weights W i,j then minimize the Euclidean distance x i -j∈N (i) W i,j x j with the constraints j∈N (i) W i,j = 1, W i,j ≥ 0 and W i,j = 0 for j ∈ N (i). Note that W is invariant under rotation, translation or homothety on the dataset X : it captures the local structure of the samples. These local relationships are then leveraged to learn Y s.t. : From [START_REF] Balasubramanian | The isomap algorithm and topological stability[END_REF].

Y = arg min M ∈R n×d M -W M 2

Non-linear mappings learned with AutoEncoders

AutoEncoders are artificial neural networks designed to perform FC. An AutoEncoder is composed of two interacting parts : an encoder φ that learns the constructed features, followed by a decoder ψ aims to reconstruct the original variables from the constructed ones (figure 3.6). The goal is to minimize the discrepancy between the original data and the output of the decoder, i.e. find φ * , ψ * s.t. :

φ * , ψ * = arg min ψ,φ Loss(X, (ψ • φ)X) (3.1)
The most widely used loss function is the squared L 2 norm (often referred to as the mean squared error (MSE) loss), i.e. :

L = ||(ψ • φ)(X) -X|| 2 F = || X -X|| 2 F = n i=1 || x i -x i || 2 2 (3.2)
Alternatively, the MSE loss can be interpreted as a sum of individual errors over each feature :

L(F ) = D i=1 || f i -f i || 2 2
Equations (3.2) and (3.1.1.3) are clearly equivalent. However, given that our algorithmic contribution pertains to the field of unsupervised FS and relies on AutoEncoders (more in chapter 4), we will in the following prefer using the feature-based interpretation L(F ). Whether φ and ψ are linear mappings depends on the activation functions used in the neural network. As shown by [START_REF] Baldi | Neural networks and principal component analysis : Learning from examples without local minima[END_REF], an AutoEncoder with linear activation functions and a MSE loss essentially performs PCA. In practice, nonlinearities such as sigmoid, tanh or ReLU [START_REF] Xu | Empirical evaluation of rectified activations in convolutional network[END_REF] are thus relied upon instead.

If the output of the encoder is of the same dimensionality as the input, then the optimization problem is trivially solved by learning an identity mapping for both the encoder and the decoder2 . In order to enforce finding an interesting solution, the common strategy is thus to enforce φ : R D → R d and ψ : R d → R D , with d << D, thus creating an under-complete representation in the encoder. This under-complete representation can be viewed as data compression in the sense that ψ allows to recover the initial information.

An alternative to under-complete representations is to rely on an over-complete representation (d > D) under the constraint that φ is sparse. This idea of implicit compressibility rather than explicit is at the core of sparse coding [START_REF] Olshausen | Sparse coding with an overcomplete basis set : a strategy employed by v1 ?[END_REF]. Sparse encoding has been shown [START_REF] Poultney | Efficient learning of sparse representations with an energy-based model[END_REF][START_REF] Boureau | Sparse feature learning for deep belief networks[END_REF] to produce expressive constructed features s.t. each of these filters memorizes a different piece of information related to the input. The reconstructed data is provided by the additive (linear) combination of these filters (fig. 3.7). FIGURE 3.7: Example of encoder-learned filters on a handwritten digit taken from the popular MNIST database. From [START_REF] Boureau | Sparse feature learning for deep belief networks[END_REF].

Another strategy to prevent the AutoEncoder from learning uninteresting features is to use a loss function different than the one in equation (3.2). Such a strategy is implemented by Denoising AutoEncoders [START_REF] Vincent | Extracting and composing robust features with denoising autoencoders[END_REF], which first produce a noisy version X of X to use as input data, then task the network with reconstructing the original "clean" data from the corrupted version (fig. Following the manifold assumption (sec. 2.1), corrupted samples in X will generally lie farther than the uncorrupted datapoints from the underlying low-dimensional manifold. A denoising AutoEncoder is therefore learning to project these noisy samples back onto the manifold. To guarantee the success of this denoising process, the features constructed by the encoder must be resilient to perturbations in the input, and should thus be more expressive than the original ones. The resulting compressed representation accordingly depends on the type and magnitude of corrupting noise applied to transform X into X. The most common corruption is the so-called masking noise, setting a fraction of randomly chosen feature values to zero. This method can be linked to the DropOut strategy [START_REF] Hinton | Improving neural networks by preventing co-adaptation of feature detectors[END_REF][START_REF] Srivastava | Dropout : a simple way to prevent neural networks from overfitting[END_REF], setting a random fraction of neuronal weights to zero to avoid overfitting as well as co-adaptation of neurons.

In order to further increase the robustness of the learned compressed data representation w.r.t. input noise, Denoising AutoEncoders can be stacked together : after one AutoEncoder has been trained, the output of its decoder is corrupted, and is fed as input to the next AutoEncoder in the stack. Such an architecture is called a Stacked Denoising AutoEncoder [START_REF] Vincent | Stacked denoising autoencoders : Learning useful representations in a deep network with a local denoising criterion[END_REF], and leads to a series of intermediate compressed representations, each being resilient to the noise applied to the previous one. The resulting embedding Z * d is then provided by the deepest, lowest-dimension encoder.

Along the many more AutoEncoder variants that were unmentioned so far, the most notable approach corresponds to Variational AutoEncoders (VAE) (Kingma and Welling, 2013) (appendix .1). Although VAEs are actually quite remote from classical Auto-Encoders, they constitute a potential extension of our algorithmic contribution (chap. 7).

Discussion

The unsupervised FC methods introduced in section 3.1.1 can be organized in three categories : variance-preserving mappings (PCA, SVD), similarity-preserving mappings (MDS, Isomap, LLE), and reconstruction-preserving mappings (AutoEncoders). Similarity-preserving methods rely on the Euclidean distance or related constructs such as geodesic distances to assess the likeness of datapoints. As underlined in chapter 2, this might be unreliable for high-dimensional datasets due to the curse of dimensionality.

By contrast, AutoEncoders do not need to compute any kind of pairwise sample similarity, given that these are concerned only with rebuilding the original data representation from the constructed features. This key property is at the core of the proposed unsupervised FS approach (chapter 4).

Supervised FC

Interestingly enough, the most well-known supervised FC approaches all correspond to similarity-preserving mappings [REFS]. Furthermore, these techniques share the same core idea that samples of the same class should be close together w.r.t. the constructed features in Z * d , while samples of different classes should be mapped as far away from each other as possible.

Linear mapping via the Fisher discriminant

The Fisher Discriminant [START_REF] Fisher | The use of multiple measurements in taxonomic problems[END_REF], often referred to as Linear Discriminant Analysis (LDA) is an early supervised FC approach attempting to maximize the inter-class scatter while simultaneously minimizing the intra-class scatter. Formally, consider a binary classification task composed of n 1 samples from the first class and n 2 samples from the second one, and denote by X 1 and X 2 the subsets of samples corresponding to the respective classes.

∀i ∈ {1, 2}, let m i = 1 ni x∈Xi
x denote the vector of average feature values on the i-th class. The between-class and within-class scatter matrices

S B ∈ R D×D and S W ∈ R D×D are then defined s.t. S B = (m 1 -m 2 )(m 1 -m 2 ) T and S W = 2 i=1 x∈Xi (x -m i )(x -m i ) T .
LDA then aims to maximize the Fisher discriminant, that is find w * ∈ R D×1 s.t. :

J(w * ) = w * T S B w * w * T S W w * = arg max w∈R D×1 J(w) (3.4)
Intuitively, this corresponds to finding a direction maximizing the projected class means (the numerator) and minimizing the classes variance in that direction (the denominator). This direction corresponds to the vector normal to the discriminant hyperplane separating the classes (fig. 3.9). FIGURE 3.9: As a result of LDA, samples are projected on the vector normal to the discriminant hyperplane separating the first class (in green) from the second (in red). From Wikipedia.

The end result of LDA is thus a single constructed feature z * s.t. ∀i ∈ [1, . . . , n], z * (x i ) = w.x i . This constructed feature is clearly obtained from the original variables through a linear mapping. Therefore, LDA suffers from the same issue as linear unsup. FC techniques, as discussed in section 3.1.1.

In order to lift this limitation, non-linear refinements of the approach were later proposed. The most prominent such refinement is the Kernel LDA [START_REF] Mika | Fisher discriminant analysis with kernels[END_REF], which first projects the input samples to a new space through a nonlinear kernel function, then relies on the kernel trick [START_REF] Hofmann | Kernel Methods in Machine Learning[END_REF] to efficiently compute the Fisher discriminant in that space. Consequently, LDA still enjoys a high popularity for modern applications, both for the purpose of FC [START_REF] Ghassabeh | Fast incremental lda feature extraction[END_REF] and error correction [START_REF] Gorban | Correction of ai systems by linear discriminants : Probabilistic foundations[END_REF].

Non-linear mappings

Non-linear supervised FC techniques can be split in two categories : those that "enrich" the unsup. FC approach Isomap (see section 3.1.1) with label information, and those based on neural networks.

Enriched Isomap techniques

Using the same notations as for LLE in section 3.1.1, the similarity metric at the core of Isomap is in the unsup. context typically defined as :

∀(i, j) ∈ [1, . . . , n] 2 , S(x i , x j ) = exp (-||xi-xj|| 2 /β) if j ∈ N (i) or i ∈ N (j) 0 otherwise
This formalization clearly does not take advantage of the labels (y 1 , . . . , y n ). In order to do so, supervised approaches such as Locally Discriminant Projection (LDP) (Zhao et al., 2006a) and Orthogonal Discriminant Projection (ODP) [START_REF] Li | Supervised feature extraction based on orthogonal discriminant projection[END_REF] propose tweaking S s.t. : andy i = y j 0 otherwise (3.5) Equation (3.5) enforces that the similarity between neighboring samples from the same class is increased compared to regular Isomap, while the similarity between neighboring samples of different classes is decreased. Most notably, the similarity between non-neighboring samples remains zero, regardless of whether their labels are identical. This essentially means that each class can be split into multiple (potentially non-connected) components of the similarity graph, therefore allowing non-linear classification of patterns.

∀(i, j) ∈ [1, . . . , n] 2 , S(x i , x j ) =            exp (-||xi-xj|| 2 /β) 1 + exp (-||xi-xj|| 2 /β) if j ∈ N (i) or i ∈ N (j) and y i = y j exp (-||xi-xj|| 2 /β) 1 -exp (-||xi-xj|| 2 /β) if j ∈ N (i) or i ∈ N (j)

Neural network-based approaches Any deep neural network tasked with classification essentially performs sup.

FC in its hidden layers, in the same way that AutoEncoders tasked with reconstruction perform unsup. FC. However, this will in the general case lead to constructed features which do not necessarily preserve the information of the original features ; considering for instance a supervised classifier network involving one hidden layer Z * d , the network may learn to encode class information in a single latent variable, ignoring the (d -1) others, s. In order to avoid such pathological configurations, neural network-based sup. FC techniques explicitely encourage all constructed features to discriminate between classes via the objective function. [START_REF] Liu | Supervised deep feature extraction for hyperspectral image classification[END_REF] proposed to use a siamese [START_REF] Bromley | Signature verification using a siamese time delay neural network[END_REF] Convolutional Neural Network (CNN) [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] to learn the constructed features (fig. 3.10).

Defining, with a slight abuse of notation, δ(

x 1 , x 2 ) = ||Z * d (x 1 ) -Z * d (x 2 )
|| 2 as the Euclidean distance between the two input datapoints in the constructed feature space, δ(x 1 , x 2 ) is denoted δ + if y 1 = y 2 and δ -if y 1 = y 2 . Given µ a margin parameter, the final loss function of the Siamese CNN is then defined as :

L(x 1 , x 2 ) = max(0, δ + -δ -+ µ) (3.6)
The objective function from equation (3.6) essentially incentivizes minimizing the distance in Z * d between points of same label, while maximizing the distance between samples from different classes. This approach therefore corresponds to an non-linear adaptation, in neural network form, of the principle that similar points should be mapped close together while dissimilar points should be as remote as possible from one another in the embedding. This core idea is also prominent in FS, which we will now introduce and discuss.

Feature selection

As seen in chapter 2, FS is a particular of FC where the exploration for the optimal feature set Z * d (w.r.t. cost function C) is limited to a small region of the search space corresponding to the C d D subsets of the original feature set F containing d elements. Despite this restriction, FS is not a "simpler" version of the DR problem. On the contrary, the FS setting involves multiple new challenges and concepts absent from the general case of FC. The most prominent of these specificities are discussed in section 3.2.1. Section 3.2.2 thereafter provides an overview of the most impactful methods in the field of sup. FS. Unsup. FS is subsequently studied in section 3.2.3. The algorithmic contribution of this thesis (chapter 4) pertains to the latter setting.

Diversity of input data representations

Three implicit assumptions were made regarding the input data during the general background presentation of chapter 2 : Assumption 1. All original features are available from the beginning of the FS process.

Assumption 2. There are no structural relationships between original features3 . Assumption 3. All original features come from the same source.

Most FS algorithms from the literature (both sup. and unsup.) are designed to handle tasks where all three above assumptions hold, thus correspond to the so-called traditional FS context. However, the rise of Big Data has led to an increased prevalence of real-life applications where at least one of these assumptions no longer holds (Li and Liu, 2017). In the context of sentiment analysis using text data extracted from the Twitter social network, each feature correspond to one word of vocabulary. Given that new slang words are generated by the users every day, the size of the feature set is constantly growing, thus falsifying assumption 1. This setting corresponds to FS for streaming data.

In neuroimaging, features will typically correspond to voxels spatially arranged in a three-dimensional space so as to mirror the anatomy of the human brain (Jenatton et al., 2011) (fig. 3.11). This graph-like structure falsifies assumption 2 and is not exploited by traditional FS algorithms. This setting corresponds to FS with structured features. FIGURE 3.12: Taxonomy of FS from a data-driven perspective. From Li et al. (2018a) In bioinformatical cancer research, different types of genetic material (e.g. DNA and RNA) are simultaneously exploited for predicting tumors [START_REF] Zhao | Multi-source feature selection via geometry-dependent covariance analysis[END_REF]. Original features are therefore obtained from multiple sources different in nature4 . This setting corresponds to Multi-View FS.

We refer the interested reader to Li et al. (2018a) for a thorough review of FS methods in non-traditional settings, the taxonomy of which is presented in figure 3.12.

We will in the context of this thesis focus on traditional FS. It is however important to note that some traditional FS techniques can be seamlessly adapted to other settings. For instance, group LASSO [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF]) (more in section 3.2.2) is by construction well-suited for tree-like structured features (fig. 3.13), leading to its tree-guided group LASSO [START_REF] Liu | Moreau-yosida regularization for grouped tree structure learning[END_REF] variant.

Hierarchical group structures corresponding to figure 3.13 also provide a direction for future refinement of our algorithmic contribution (chapter 7).

Particularities of the Feature Selection setting

Independent, collective and semi-independent scoring

As said earlier, the aim of DR is in the general case to find

Z * d = arg min Z d ∈H d C(F, Z d ).
In the FS setting, the cost function C is responsible for estimated the quality of the selection subset. In other words, C is in this case a scoring Independent scoring [START_REF] Kohavi | Wrappers for feature subset selection[END_REF] proposed a first tentative definition of feature relevance in the sup.

context by interpreting the features f 1 , . . . , f D and the learning goal y as random variables drawn from an underlying joint distribution P (F, y). With a slight abuse of notation, the relevance of an original feature is defined as :

∀i ∈ [1, . . . , D], Relevance(f i ) = |P (f i , y) -P (f i )P (y)| (3.7)
It follows from equation (3.7) that a feature is irrelevant iff it is independent from the labels. The stronger the dependency between f i and y, the more relevant f i .

Given that state-of-the-art unsup. FS methods typically construct an artificial learning goal y (more in section 3.2.3), the above definition of relevance is applicable in both sup. and unsup. contexts.

In practice, given that the underlying joint distribution is unknown, relevance can hardly be computed empirically in this way. However, this definition is an integral part of prominent scoring criteria such as the Fisher score [START_REF] Duda | Pattern classification[END_REF] or the supervised version of the Laplacian score [START_REF] He | Laplacian score for feature selection[END_REF] (more in sections 3.2.2 and 3.2.3).

Most importantly, the relevance estimation of a particular original feature does not involve any of the other features. We will therefore in the following refer to FS approaches relying on such scoring functions as independent scoring methods. Figure 3.14 provides an illustration of the false negative problem on the well-known XOR example : X 1 and X 2 are both individually irrelevant and do not separate the classes at all. However, taken jointly, they allow for a perfect non-linear separation.

Limitations of independent scoring methods

Figure 3.15 illustrates the opposite issue of false positives ; X 1 and Y are dependent (left panel), but become independent conditionally to X 2 , meaning X 1 is not truly relevant. This phenomenon is known as Simpson's paradox 5. In the unsup. declination of the FS problem, a common alternative [START_REF] He | Laplacian score for feature selection[END_REF][START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF][START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF][START_REF] Li | Unsupervised feature selection using non-negative spectral analysis[END_REF] is to define two cost functions C1 and C2. C1 is tasked with scoring the features. C2 is responsible for assessing the quality Z * d after the selection process is complete. By contrast with the unsup. C1, C2 is often a sup. estimator (more in chapter 5) FIGURE 3.14: Independent scoring methods are unable to detect that although X 1 and X 2 are individually irrelevant, they perfectly separate the classes (stars and circles) if considered together.

From [START_REF] Guyon | An introduction to variable and feature selection[END_REF]. [START_REF] Simpson | The interpretation of interaction in contingency tables[END_REF], and is caused by feature redundancy : the information carried by X 1 is already accounted for in X 2 (X 2 however contains additional information absent from X 1 ). In light of these issues, the main benefit of independent scoring is its lower computational complexity relatively to both collective and semi-independent scoring, which we now introduce.

Semi-independent scoring ∀i ∈ [1, . . . , D], let F \i denote the subset of F containing every feature except f i .

Following [START_REF] Kohavi | Wrappers for feature subset selection[END_REF], the notion of feature relevance can be extended to tackle the aforementioned limitations :

Relevance(f i ) = S⊂F \i |P (f i , y|S) -P (f i |S)P (y|S)| (3.8)
Following equation (3.8), f i is considered irrelevant iff it is independent from the learning goal conditionally to any combination of other features, indicating that the information carried by f i (if any) is already accounted for elsewhere. This new definition solves the problem of false negatives 6 . By contrast with independent scoring, the process of estimating the relevance of an element of F involves all features. Nevertheless, each feature is still assigned its own individual score. Therefore, we will in the following refer to FS methods relying on this paradigm as semi-independent scoring techniques.

6. It is however not enough to avoid false positives. In order to avoid Simpson's paradox, [START_REF] Kohavi | Wrappers for feature subset selection[END_REF] further differentiate between weakly and strongly relevant features, with the idea of selecting only strongly relevant ones. However, the definitions of weak and strong relevance are unpractical, and bear mostly historical significance. FIGURE 3.15: On the left panel, X 1 appears relevant. However, it becomes irrelevant conditionally to X 2 (denoted by circles and stars on the right panel). From [START_REF] Guyon | An introduction to variable and feature selection[END_REF].

Collective scoring A third possible scoring approach consists in defining relevance on a subset level only, so that features are assessed as groups rather than individuals. This approach is intuitively well-suited for tree-like feature structures (fig. 3.13). However, the number of score estimates needed to fully explore the search space rises from D (one per original feature) to C d D (one per subset of F containing d elements). Exhaustive exploration is thus intractable.Gaudel and Sebag (2010) envision the search for Z * d as navigating through a decision tree, which is aggressively pruned to avoid considering unpromising candidate subsets. Such algorithms are in the following referred to as collective scoring approaches.

Forward, backward or simultaneous selection

Once scoring function C has been defined, three differing strategies are available to construct Z * d based on C.

Forward selection

The first selection strategy consists in an iterative process, of which pseudocode is provided in Algorithm 1 7 :

7. This algorithm is written from the perspective of semi-independent scoring. Nevertheless, its pseudocode can be slightly modified to adopt the point of view of collective scoring, without loss of generality.

Algorithm 1 Forward selection

Input : Feature set F = {f 1 , ..., f D } Parameter : Selection subset size d Output : Selection subset Z d Initialize Z d = ∅ and candidate set S = F Repeat for f ∈ S do Compute C(f ) end Determine best candidate f best w.r.t. C Z d ← (Z d ∪ f best ) S ← (S\f best ) until |Z d | = d Return Z d .
Following alg. 1, forward selection [START_REF] Guyon | An introduction to variable and feature selection[END_REF]) is a "bottom-up" approach, building the selection subset from the ground up.

Backward selection

The second selection strategy is also an iterative process, described in algorithm 2 :

Algorithm 2 Backward selection Input : Feature set F = {f 1 , ..., f D } Parameter : Selection subset size d Output : Selection subset Z d Initialize Z d = F Repeat for f ∈ Z d do Compute C(f ) end Determine worst candidate f worst w.r.t. C Z d ← (Z d \f worst ) until |Z d | = d Return Z d .
By alg. 2, backward selection [START_REF] Guyon | An introduction to variable and feature selection[END_REF] (also commonly referred to as Recursive Feature Elimination (RFE)) is a "top-down" method, pruning the selection subset down to the desired size d.

Simultaneous selection

This last strategy performs selection in a single pass rather than iteratively (alg. 3) :

Algorithm 3 Simultaneous selection Input : Feature set F = {f 1 , ..., f D } Parameter : Selection subset size d Output : Selection subset Z d Initialize Z d = ∅ for f ∈ F do Compute C(f ) end Determine the d best candidates (f 1 best , . . . , f d best ) w.r.t. C Z d ← {f 1 best , . . . , f d best } Return Z d .
Discussion If C defines an independent scoring process, then the order in which features are selected/discarded is clearly irrelevant. The above three strategies are therefore equivalent in that case. Independent scoring methods therefore opt for simultaneous selection, given its lower computational cost relatively to both forward and backward approaches.

On the other hand, if C pertains to either semi-independent or collective scoring, then each strategy likely leads to different results. An illustration of the respective weaknesses is provided in figure 3.16. In this sup. example, f 3 is the most individually relevant feature, given that it achieves the best class separation on its own (bottom-right panel). A forward selection method will therefore choose f 3 first. However, if tasked with selected a second candidate, then potential forward selections {f 3 , f 1 } and {f 3 , f 2 } are both worse predictors than {f 1 , f 2 }, corresponding to the result of backward selection.

In this example, going backwards is thus better than forward for d = 2, and worse for d = 1. This is a consequence of the greedy 8 nature of both approaches.

Informally, it appears that the lower the selection ratio d D , the better forward selection comparatively to RFE. In practice, both semi-independent and collective FS algorithms rely on either simultaneous [START_REF] He | Laplacian score for feature selection[END_REF][START_REF] Li | Unsupervised feature selection using non-negative spectral analysis[END_REF] or backward selection [START_REF] Guyon | Gene selection for cancer classification using support vector machines[END_REF][START_REF] Ye | Variable selection via penalized neural network : a drop-out-one loss approach[END_REF], while forward selection is seldom implemented in recent approaches.

Filters, wrappers and embedded methods

As said, the end goal of FS (and even DR in general) is to help a learning algorithm, e.g. a supervised classifier or an unsupervised regressor. An additional way of categorizing FS approaches (complimentary to the type and ordering of feature scoring) is therefore via the relationship between the FS technique and the learning algorithm. An illustration of the three resulting groups of methods is provided in fig. 3.17.a.

Filters [START_REF] Duda | Pattern classification[END_REF][START_REF] He | Laplacian score for feature selection[END_REF](panel a) of figure 3.17) act as a pre-processing step to the learning algorithm, the latter being uninvolved in the selection.

Wrappers [START_REF] Huang | A hybrid genetic algorithm for feature selection wrapper based on mutual information[END_REF](panel b)) also correspond to a pre-processing step. By contrast with filters, wrappers define an iterative selection pipeline. At each step, the learning algorithm is ran using the candidate selection subset as input. The eventual performance of learning is then leveraged to guide the search for the optimal selection subset Z * d during the next step.

8. Greedy is here used to reflect the fact that earlier selection/elimination decisions are never revisited in light of later decisions. Embedded methods [START_REF] Guyon | Gene selection for cancer classification using support vector machines[END_REF](panel c)) represent a paradigm shift. FS is performed online during the execution of the learning algorithm, rather than in pre-processing. The underlying idea is to leverage partial results of learning (such as the parameters of a neural network) to orient the search for Z * d . All three aforementioned techniques are clearly applicable in the sup. context, where the learning algorithm typically corresponds to a supervised classifier. The main motivation for choosing an adequate selection strategy is then the computational cost. Embedded methods require few runs of the learning algorithm (possibly with a warm start), while filters require none at all. By contrast, wrappers involve running the learning algorithm multiple times. This constitutes a significant downside of wrappers in many application domains. In sup. image classification for instance 9 , training a deep convolutional network hundred of times is typically unaffordable.

As a result, sup. FS most often correspond to either filters [START_REF] Duda | Pattern classification[END_REF] or embedded methods [START_REF] Guyon | Gene selection for cancer classification using support vector machines[END_REF]. Selection resulting of embedded FS likely yields higher learning performance than for filters, given that Z * d is tailor-made for the learning algorithm considered. On the flipside, filters lead to selection subsets of higher generalization power. This means that if the learning algorithm is modified (e.g. hidden layers are added to a deep neural network), filter-based FS is invariant, whereas the learning performance resulting of embedded FS is likely degraded.

This independence property of selection w.r.t. subsequent learning is thereafter called agnosticism. This notion is sought for and extended in both our algorithmic and methodological contributions (chapters 4 and 5).

In the unsup. context, the eventual learning algorithm (if any) is typically unknown at the time of FS. Consequently, both wrappers and embedded method are ill-suited to this setting. To the best of our knowledge, all of the most impactful traditional unsup. FS approaches [START_REF] He | Laplacian score for feature selection[END_REF][START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF][START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF][START_REF] Li | Unsupervised feature selection using non-negative spectral analysis[END_REF] are filters. A direction for future research would be to refine our algorithm AGNOS into an embedded unsup. method (chapter 7).

Supervised Feature Selection

This section introduces the most well-known sup. FS algorithms. For each approach, the scale of the scoring function (independent, semi-independent or collective), the order of assessment (simultaneous, forward selection or recursive elimination) and the link with the learning algorithm (filter, wrapper or embedded) are stated after the description of the method.

RelieF

The early RelieF [START_REF] Kira | The feature selection problem : Traditional methods and a new algorithm[END_REF][START_REF] Kononenko | Estimating attributes : analysis and extensions of relief[END_REF] searches for two specific neighbors of any given point x i : the closest (w.r.t. the Euclidean distance) observation with the same label (the nearest hit n h (i)) and the closest observation with a different label (the nearest miss n m (i)). The score of feature f j is then s.t. :

∀j ∈ [1, . . . , D], S(f i ) = 1 n n i=1 |f j (x i ) -f j (n m (i)) | 2 -|f j (x i ) -f j (n h (i)) | 2 (3.9)
In order to maximize this score, an informative feature should take similar values on neighboring points of the same class and as distinct values as possible on differently labeled neighboring points. Top ranked features should thus support stark separation of the classes and lead to a high prediction accuracy. Eq. (3.9) seems to define an independent scoring method. However, it is important to note that the nearest misses and hits have been determined by considering all original features. RelieF is accordingly a semi-independent approach. Keywords : Filter, semi-independent scoring, simultaneous selection 9. Selecting individual pixels in a high-resolution image is hardly effective for prediction. Therefore, Computer Vision applications of FS [START_REF] Chen | Handbook of pattern recognition and computer vision[END_REF] are concerned with identifying the best candidates among objects of greater scale, e.g. retaining the most informative convolutional filters.

Fisher score The Fisher score [START_REF] Duda | Pattern classification[END_REF] was introduced as an alternative to RelieF inspired by the Fisher discriminant (section 3.1.2). Considering a classification task with c classes, n i denotes the number of samples in the i-th class, µ j (i) and σ j (i) respectively the mean and variance of the j-th feature on the i-th class, and µ j the mean of the j-th feature on the whole dataset. The Fisher score of f j is then s.t. :

∀j ∈ [1, . . . , D], S(f j ) = c i=1 n i (µ j (i) -µ j ) 2 c i=1 n i σ j (i) 2
(3.10) Equation (3.10) implements the same core idea as RelieF, that the most informative features are those presenting a large contrast between different classes. However, contrarily to RelieF, the Fisher score is an independent scoring method and suffers from the issues presented in section 3.2.1.1. A generalized Fisher score has later been proposed in [START_REF] Gu | Generalized fisher score for feature selection[END_REF], turning to collective scoring instead. Keywords : Filter, independent scoring, simultaneous selection RFE-SVM Support Vector Machines (SVM) [START_REF] Cortes | Support-vector networks[END_REF] are a type of sup. classification algorithms. The goal of a linear SVM is to find the unique hyperplane (often referred to as decision boundary ) meeting two requirements in the separable case : i) all datapoints sharing a common label are on the same side of the border and ii) the distance between the border and the closest datapoint (thereafter called margin10 ) is maximal among all hyperplanes fulfilling condition i). This process is illustrated in figure 3.18, where H 1 is a poor separator. H 2 achieves perfect separation, but with only a small margin. H 3 is the optimal hyperplane maximizing inter-class margin.

The process of fitting the decision boundary corresponds to solving the following constrained optimization problem for w * and b * :

w * = arg min w∈R D ||w|| 2 ∀i ∈ [1, . . . , n], y i (w * .x i -b * ) ≥ 1 (3.11)
By definition, the learned weight vector w = (w 1 , . . . , w D ) involves one component per feature. Recursive Feature Elimination-Support Vector Machine (RFE-SVM) [START_REF] Guyon | Gene selection for cancer classification using support vector machines[END_REF] is an iterative embedded FS method leveraging this observation, of which pseudocode is provided in algorithm 4. Even though eliminating the features with the smallest associated weights (alg. 4) may seem counter-intuitive (given that the goal of the optimization problem in eq. (3.11) is to minimize ||w|| 2 ), it is well-grounded in theory ; the following explanation is also the core motivation of many neural network-based FS approaches [START_REF] Setiono | Neural-network feature selector[END_REF][START_REF] De | Feature analysis : neural network and fuzzy set theoretic approaches[END_REF][START_REF] Steppe | Improved feature screening in feedforward neural networks[END_REF][START_REF] Zurada | Pertubation method for deleting redundant inputs of perceptron networks[END_REF][START_REF] Ye | Variable selection via penalized neural network : a drop-out-one loss approach[END_REF], the most impactful of which will be introduced thereafter. Keywords : Embedded method, semi-independent scoring, backward selection/Recursive Feature Elimination Motivation of RFE-SVM and neural network-based FS In the sup. context, label information allow considering the performance of a classifier as a collective scoring criterion. In order to avoid the expensive combinatorial problem inherent to collective scoring, a semi-independent criterion can be derived from the collective one, by analyzing the sensitivity of the classifier performance w.r.t. the removal of each feature from the input.

Algorithm 4 RFE-SVM

Input : Feature set F = {f 1 , ..., f D } Parameter : Selection subset size d Output : Selection subset Z d Initialize candidate set Z d = F Repeat Train SVM from Z d , producing w = (w 1 , . . . , w D ) Find f worst s.t. w worst = arg min w j w 2 j Z d ← Z d \{f worst } until |Z d | = d Return Z d .
Formally, ∀j ∈ [1, . . . , D], ∀S ⊂ F , let D J (S, f j ) = J(S\{f j }) -J(S) denote the change in classifier performance J induced by the elimination of f j from S. Intuitively, removing irrelevant features should hardly degrade performance. Therefore, the lower D J (S, f j ), the less relevant f j . Note that positive values for D J (S, f j ) are possible, indicating an increase in performance due to removing harmful noise from the classifier input. Computing the exact value of D J (S, f j ) is computationally costly, as it requires training the classifier multiple times. A good approximation of it can however be obtained using the following trick : eliminating f j can be simulated by setting all weights associated to f j to 0. That is, in the case of RFE-SVM :

∀j ∈ [1, . . . , D], ∀S ⊂ F, D J (S, f j )) = J(S with w j ← 0) -J(S with w j untouched ) (3.12)
A second order Taylor expansion of J around w j gives :

D J (S, f j ) = ∂J ∂w j w j + 1 2 ∂ 2 J ∂ 2 w j w 2 j (3.13)
Given that J is examined after classifier training has converged, it lies in a local maximum, and the first order derivative can be neglected. Thus :

D J (S, f j ) = 1 2 ∂ 2 J ∂ 2 w j w 2 j (3.14)
In the context of a linear SVM,

J(S) = 1 2 w 2 , thus ∀j ∈ [1, . . . , D], ∂ 2 J ∂ 2 wj = const.
. This leads to :

D J (S, f j ) ∝ w 2 j (3.15)
Equation (3.15) motivates eliminating the features with the smallest weights in linear RFE-SVM. Similar demonstrations can be obtained for non-linear SVMs, as well as for neural networks.

Neural network-based FS Over the years, the idea of eliminating the features with the smallest associated weights or decrease in classifier performance sprouted many neural network-based sup. FS approaches [START_REF] Setiono | Neural-network feature selector[END_REF][START_REF] De | Feature analysis : neural network and fuzzy set theoretic approaches[END_REF][START_REF] Steppe | Improved feature screening in feedforward neural networks[END_REF][START_REF] Zurada | Pertubation method for deleting redundant inputs of perceptron networks[END_REF][START_REF] Ye | Variable selection via penalized neural network : a drop-out-one loss approach[END_REF]. These methods involve slight variations in implementation (e.g. adding a threshold value on the weights for the purpose of feature elimination). Most importantly, these algorithms differ on the type of weight regularization used.

Both the Signal Noise Ratio (SNR)11 [START_REF] Bauer | Feature screening using signal-to-noise ratios[END_REF] and Feature Quality Index (FQI) [START_REF] De | Feature analysis : neural network and fuzzy set theoretic approaches[END_REF] approaches do not implement any kind of weight regularization. Neural Network Feature Selector (NNFS) [START_REF] Setiono | Neural-network feature selector[END_REF]) adds a L 2 regularization term (also known as weight decay) to the loss function of the network. The Drop-Out-One [START_REF] Ye | Variable selection via penalized neural network : a drop-out-one loss approach[END_REF] refinement instead relies on a sparse group-LASSO [START_REF] Simon | A sparse-group lasso[END_REF] penalty on the weights to enforce sparsity in the selection. This regularized regression technique will be further discussed below.

The Deep Feature Selection (DFS) [START_REF] Li | Deep feature selection : theory and application to identify enhancers and promoters[END_REF] approach is particularly relevant to the algorithmic contribution of this thesis. DFS considers an alternate neural architecture, in which a sparse one-to-one linear layer is added between the input and the first hidden layer, as illustrated in figure 3.19. The loss function of the network is then augmented with a sparse group-LASSO penalty term on the weights of this additional layer. This architecture holds the practical benefit that the importance of input feature f j is now condensed in the single real-valued slack variable w j , rather than inferred from an R D×d weight matrix.

A limitation of sup. neural network-based FS is that the sensitivity of the classifier performance w.r.t. the input tends to decrease as the number of hidden layers in the network increases [START_REF] Pascanu | On the difficulty of training recurrent neural networks[END_REF]. This corresponds to the so-called vanishing gradient [START_REF] Hochreiter | The vanishing gradient problem during learning recurrent neural nets and problem solutions[END_REF] issue. [START_REF] Roy | Feature selection using deep neural networks[END_REF] report that the most important initial features are hardly identifiable empirically for networks of depth ≥ 3 using SNR, FQI or NNFS.

As will be seen, our algorithmic contribution (chapter 4)is the first attempt at extending regularized neural networkbased FS to the unsup. context. Keywords : Wrappers/Embedded methods, Semi-independent scoring, Backward selection/Recursive Feature Elimination Least Absolute Shrinkage and Selection Operator (LASSO) Ordinary Least Squares (OLS) [START_REF] Goldberger | Classical linear regression[END_REF] corresponds to the linear regression problem of finding β * ∈ R D s.t. :

β * = arg min β∈R D n i=1 ||y i -x i , β || 2 2 (3.16)
OLS is however prone to overfitting in the small n, large D regime (few datapoints, many features). In order to combat this issue, a tentative solution is to add an L 2 regularization penalty term to the optimization problem, parameter λ ≥ 0 governing the severity of the penalization :

β * = arg min β∈R D n i=1 ||y i -x i , β || 2 2 + λ||β|| 2
(3.17)

The vector β * = (β * 1 , . . . , β * D ) reflects the importance of the respective original features in the regression. However, by virtue of the L 2 geometry, β * optimized via eq. (3.16) is rotationally invariant, as illustrated in the leftmost panel of figure 3.20. This means that all features are likely associated to non-zero coefficients. An L 2 penalty term is thus hardly discriminative.

In order to enforce sparsity in the solution, [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] introduced the Least Absolute Shrinkage and Selection Operator (LASSO) technique, which adds a L 1 penalization term instead :

β * = arg min β∈R D n i=1 ||y i -x i , β || 2 2 + λ||β|| 1 (3.18)
This regularization enforces sparsity among the coefficients β * j , j ∈ [1, . . . , D]. This property stems from the nature of the L 1 geometry, in which the penalty function treats the coordinate directions differently from all other directions (center panel of figure 3.20). As a result of sparsity, the LASSO induces a supervised FS technique, discarding f j iff β * j < .

In order to obtain the best of both worlds of the L 1 and L 2 geometries, [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF] introduced the group-LASSO, in which the feature set is first partitioned in groups G 1 , . . . , G k . |G i | denoting the size of the i-th feature group, the L 2,1 penalized regression scheme reads : This hybrid geometry leads to sparsity at the group level (discarding as many groups of features as possible) while preserving the rotational invariance of the solution within each group (rightmost panel of figure 3.20) [START_REF] Bach | Consistency of the group lasso and multiple kernel learning[END_REF]. Many variants of the group LASSO have since been proposed to achieve specific sparsity and invariance properties [START_REF] Meier | The group lasso for logistic regression[END_REF][START_REF] Simon | A sparse-group lasso[END_REF][START_REF] Ivanoff | Adaptive lasso and group-lasso for functional poisson regression[END_REF]. Most notably, the sparse group LASSO, also referred to as elastic net, reads [START_REF] Simon | A sparse-group lasso[END_REF] :

β * = arg min β∈R D n i=1 ||y i -x i , β || 2 2 + λ k i=1 |G i | j∈Gi β 2 i (3.19)
β * = arg min β∈R D n i=1 ||y i -x i , β || 2 2 + (1 -α)λ k i=1 |G i | j∈Gi β 2 i + αλ||β|| 1 (3.20)
α ∈ [0, 1] governs the convex combination of the LASSO and group LASSO. The aim of the elastic net is to achieve sparsity of the solution both at the group level and within each group, and has become a useful regularization tool for training sup. Neural Networks on high-dimensional data [START_REF] Feng | Sparse-input neural networks for high-dimensional nonparametric regression and classication[END_REF]. Keywords : Filters, semi-independent scoring, simultaneous selection

Discussion

During this review of sup. FS methods, the central idea has remained constant : "datapoints of the same class should be neighbors, while datapoints of different classes should be strangers". Features are selected or rejected based on how well they reflect this desired structure. Interestingly enough, this same idea is also at the core of unsup. FS, as will be shown in the next section.

An additional observation of particular interest to this thesis is that neural network-based FS approaches such as Ye and Sun (2018) actually combine FC and FS, in the sup. context : features are selected w.r.t. their importance to build the constructed features in the hidden layers of the network.

Unsupervised FS

By contrast with the sup. context, all methods presented in the following are filters implementing a semi-independent feature scoring criterion, based on spectral clustering theory (Von [START_REF] Luxburg | A tutorial on spectral clustering[END_REF].

Spectral clustering

Let sim denote a similarity metric on the instance space, e.g. sim(x i , x j ) = exp{-x i -x j 2 2 } and M the n × n matrix with M i,j = sim(x i , x j ). Let ∆ be the diagonal degree matrix associated with M , i.e. ∆ ii = n k=1 M ik , and L = ∆ -1 2 (∆ -M )∆ -1 2 the normalized Laplacian matrix associated with M .

Spectral clustering relies on the diagonalization of L, with λ i (resp. ξ i ) the eigenvalues (resp. eigenvectors) of L, with λ i ≤ λ i+1 . Informally, the ξ i are used to define soft cluster indicators (i.e. the degree to which x k belongs to the i-the cluster being proportional to x k , ξ j ), with λ k measuring the inter-cluster similarity (the smaller the better).

The general unsupervised clustering scheme proceeds by clustering the samples and falling back on supervised feature selection by considering the clusters as if they were pseudo-labels ; more precisely, the features are assessed depending on how well they separate clusters.

Laplacian score The Laplacian score [START_REF] He | Laplacian score for feature selection[END_REF] can be viewed as an extension of the Fisher score (section 3.2.2), unifying sup. and unsup. contexts. The Laplacian score of feature f j is given by :

S(f j ) = 1 σ f j n i,k=1 (f j (x i ) -f j (x k ))M i,k (3.21)
S(f j ) can be rewritten using the Laplacian matrix, hence the name of the approach :

S(f j ) = f j T L f j f j T ∆ f j
with 1 the n-dimensional constant vector [1, ..., 1] T and f j = f j -

f T j ∆1
1 T ∆1 1. The higher S(f j ), the more important f j . The Laplacian score is also remotely related to the MaxVariance approach [START_REF] Kantardzic | Data Reduction[END_REF], selecting features with large variance for the sake of their higher representative power.

In the sup. context, a possible similarity metric is the following :

∀(i, k) ∈ [1, . . . , n] 2 , supsim(x i , x k ) = 1 if y i = y k 0 if y i = y k (3.22)
Using the similarity metric from equation (3.22), Laplacian and Fisher scores are equivalent :

∀j ∈ [1, . . . , D], Laplacian(f j ) = 1 1 + Fisher(f j ) (3.23)
In the unsupervised context using sim(x i , x j ) = exp{-x i -x j 2 2 }, the Laplacian score becomes a semi-independent scoring method, as are all unsup. methods introduced in the remainder of this section. SPEC SPEC 12 [START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF] propose three scores respectively noted φ 1 , φ 2 and φ 3 , still following the idea that relevant features should be slowly varying among samples close to each other. After [START_REF] Shi | Normalized cuts and image segmentation[END_REF]; [START_REF] Ng | On spectral clustering : Analysis and an algorithm[END_REF], considering eigenvectors ξ 0 , ..., ξ n-1 of the normalized Laplacian L (respectively associated with eigenvalues λ 0 < λ 1 < ... < λ n-1 ), smooth features are aligned with the first eigenvectors, hence the score φ 1 :

∀j ∈ [1, . . . , D], φ 1 (f j ) = f j T L f j where f j = ∆ 1 2 f j / ∆ 1 2 f j (3.24)
12. This name is not an acronym, rather a reference to the reliance on spectral clustering theory Eigenvectors ξ 0 , ..., ξ n-1 of L define soft cluster indicators, and eigenvalues λ 0 < λ 1 < ... < λ n-1 measure the separability of the clusters. The smaller φ 1 (f j ), the more efficient f j is to separate the clusters.

As the first eigenvector ξ 0 = ∆ 1 2 1 does not carry any information, with λ 0 = 0, one might rather consider the projection of the feature vector f j on the orthogonal space of ξ 0 :

φ 2 (f j ) = 1 1 -f j , ξ 0 f j T L f j (3.25)
Finally, in the case where the target number of clusters κ is known, only the top-κ eigenvectors are considered, and score φ 3 is defined as :

φ 3( f j ) = κ k=1 (2 -λ k ) f j , ξ k 2 (3.26)
Features are ranked in ascending order for φ 1 and φ 2 , and in descending order for φ 3 . The above scores measure the overall capacity of a feature to separate clusters, which might prove inefficient in multi-classes/multi clusters settings : a feature most efficient to separate a pair of clusters might have a mediocre general score.

MCFS Instead of assigning one global score per feature, Multi-Cluster Feature Selection (MCFS) [START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF] address the limitations of SPEC by computing one score per feature per cluster, essentially attempting to capture the local informativity of features. The respective capacities of the features to separate clusters are estimated through fitting the eigenvectors (reminding that ξ k is a soft indicator of the k-th cluster) up to a regularization term. Formally, this corresponds to defining κ independent optimization problems (one per cluster) s.t. :

∀k ∈ [1, . . . , κ], a * k = min a k ∈R D×1 ξ k -Xa k 2 2 + β k a k 1 (3.27) a * k = (a * k (f 1 ), . . . , a * k (f D ))
reflects the respective abilities of the original features to identify the k-th cluster. As seen in the earlier discussion on LASSO, the L 1 regularization term enforces the sparsity of a k (penalization strength being governed by parameter β k ), retaining only the features most relevant to this cluster. The final score of f j then simply corresponds to the maximum value of a k (f j ) over the κ clusters, s.t. :

S(f j ) = max k∈[1,...,κ] |a k (f j )| (3.28)
NDFS A general limitation common to Laplacian score, SPEC and MCFS is the reliance on an Euclidean distancebased similarity metric, which leads to unstable clustering in high-dimensional spaces due to the curse of dimensionality (section 2.2.1). Non-negative Discriminative Feature Selection (NDFS) [START_REF] Li | Unsupervised feature selection using non-negative spectral analysis[END_REF] alleviates this issue by defining a joint optimization problem. The κ learning goals (a * 1 , . . . , a * κ ) from MCFS are merged into a single feature importance matrix A ∈ R D×κ , subject to a group-LASSO regularization term. Moreover, considering that the original Laplacian eigenvectors ξ 0 , . . . , ξ n-1 are brittle, a second objective corresponds to a cluster indicator matrix Ξ ∈ R n×κ . The rows of Ξ are initialized with the Laplacian eigenvectors. α and β denoting two regularization weights, the goal is then to find

(Ξ * , A * ) s.t. : Ξ * , A * = arg min Ξ,A T r(Ξ T L Ξ) + α( Ξ -XA 2 F + β A 2 2,1 ) (3.29)
with the additional constraint that Ξ must be orthogonal and semi-positive definite (Ξ T Ξ = I κ , Ξ ≥ 0).

Following [START_REF] Yu | Multiclass spectral clustering[END_REF], the first term of equation (3.29) can be rewritten as13 :

T r(Ξ T LΞ) = 1 2 n i,j=1 sim(x i , x j ) Ξ(x i ) √ ∆ i - Ξ(x j ) ∆ j 2 2 (3.30)
Using the alternate formulation from eq. (3.30), it is apparent that minimizing the term T r(Ξ T LΞ) provides an incentive to cluster similar points together. The orthogonality and nonnegativity constraints on Ξ further push each sample to belong in exactly one cluster. Lastly, the group-LASSO penalty on the rows of A enforces sparse feature selection.

NDFS is acknowledged as a seminal work in unsup. FS : later approaches [START_REF] Li | Clustering-guided sparse structural learning for unsupervised feature selection[END_REF][START_REF] Shi | Robust spectral learning for unsupervised feature selection[END_REF][START_REF] Qian | Robust unsupervised feature selection[END_REF][START_REF] Nie | Unsupervised feature selection with structured graph optimization[END_REF] all stem from NDFS, and provide incremental performance improvements by adding (oftentimes computationally costly) third or even fourth optimization objectives. We will now introduce these methods for the sake of completeness.

CGSSL Clustering-Guided Sparse Structural Learning (CGSSL) [START_REF] Li | Clustering-guided sparse structural learning for unsupervised feature selection[END_REF] iterates on NDFS by making the additional assumption that the pseudo-labels associated to the samples are actually generated by an underlying ddimensional linear model, s.t. :

∀(i, j) ∈ [1, . . . , κ] × [1, . . . , n], y i (x j ) = v T i x j + p T i Q T x j (3.31)
where v i ∈ R D and p i ∈ R d are weight vectors and Q ∈ R D×d is an orthogonal matrix representing the linear transformation parameterizing the shared d-dimensional subspace. The feature importance matrix A from NDFS is then redefined to A = V + QP , and a regularization term on V is added to the optimization problem :

P * , Q * , Ξ * , A * = arg min P,Q,Ξ,A T r(Ξ T L Ξ) + α( Ξ -XA 2 F + β A 2 2,1 ) + γ A -QP 2 F (3.32)
still subject to Ξ orthogonal and semi-positive definite (Ξ T Ξ = I κ , Ξ ≥ 0), with α, β, γ regularization weights. The motivation for this sparse structural learning (Ando and Zhang, 2005a) refinement is that the selected features arguably capture the structure of the underlying d-dimensional manifold (as per the manifold assumption from chapter 2).

RSFS Robust Sparse Feature Selection (RSFS) [START_REF] Shi | Robust spectral learning for unsupervised feature selection[END_REF]) also aims at providing a more accurate cluster structure than NDFS, but does so in a different fashion than CGSSL, inspired by robust PCA [START_REF] Cand Ès | Robust principal component analysis ?[END_REF]. Instead of explicitly generating pseudo-labels, it is assumed that the learned cluster indicators may be arbitrarily corrupted, but that the corruption is sparse. This sparse noise is represented by a corruption matrix C ∈ R n×κ subject to a LASSO penalty. The optimization problem then becomes :

C * , Ξ * , A * = arg min C,Ξ,A T r(Ξ T L Ξ) + α( (Ξ -C) -XA 2 F + β A 2 2,1 ) + γ|C| 2 1 (3.33)
A parallel can be drawn between RSFS and denoising AutoEncoders (section 3.1.1) : a common idea is to increase the robustness of learning by exposition to small perturbating noise.

RUFS Robust Unsupervised Feature Selection (RUFS) [START_REF] Qian | Robust unsupervised feature selection[END_REF]) aims to improve the quality of the structure learned by NDFS by adding a cluster centroid matrix C ∈ R κ×D to the joint optimization problem :

C * , Ξ * , A * = arg min C,Ξ,A T r(Ξ T L Ξ) + α( Ξ -XA 2 2,1 + β A 2 2,1 ) + γ X -ΞC 2,1 (3.34)
The authors claim that by virtue of this addition, the inaccuracies caused in the spectral clustering process by irrelevant features should mainly affect C, thus spare the more important Ξ.

SOGFS Even if clusters are dynamically updated like in the aforementioned NDFS variants, the similarity graph can still be arbitrarily corrupted by irrelevant or redundant features. Structured Optimal Graph Feature Selection (SOGFS) [START_REF] Nie | Unsupervised feature selection with structured graph optimization[END_REF] aims to correct this flaw by also optimizing the similarity matrix M itself. The idea is to weigh the original features while computing pairwise similarities, according to the feature importance matrix A. The similarity metric is therefore progressively biased towards the best selection candidates.

Still following the neighbors should look alike idea, M * is defined as :

M * = arg min M T i 1=1,0≤mi,j ≤1 i,j ( x i -x j 2 2 m i,j + αm 2 i,j ) (3.35)
with α a regularization parameter to avoid the trivial solution. In order to consider only relevant features to learn the similarity matrix, this term becomes :

min M T i 1=1,0≤mi,j ≤1 i,j ( A T x i -A T x j 2 2 m i,j + αm 2 i,j ) (3.36)
The final optimization problem of SOGFS is then :

M * , Ξ * , A * = arg min M,Ξ,A γT r(Ξ T L Ξ) + β A 2 2,1 + i,j A T x i -A T x j 2 2 m i,j + αm 2 i,j
(3.37)

Discussion

While this review of state-of-the-art unsup. FS methods cannot be exhaustive14 , it supports the vision of unsup. FS as using spectral clustering to equip datapoints with pseudo-labels and fall back on sup. FS. This technique leads to two major issues :

-The already discussed reliance on a high-dimensional Euclidean distance to construct the similarity graph.

-The poor handling of redundant feature sets. Considering for instance that f 1 and f 2 are identical, then S(f 1 ) ≈ S(f 2 ) w.r.t. the Laplacian score, SPEC or MCFS. These twin features will consequently be either both rejected or selected, which is clearly sub-optimal no matter the cost function. Note that NDFS and its refinements address the redundancy issue.

As handling redundancy among initial features is of paramount importance, it is a cornerstone of our algorithmic contribution (chapter 4).

A third issue of state-of-the-art unsup. FS methods lie in their empirical validation pipeline rather than the selection itself. The efficiency of all aforementioned methods is assessed in a sup. environment, which goes against the agnosticism property of filters (more in chapter 5).

Data compression is traditionally performed through FC (chapters 2 and 3). Accordingly, AGNOS is a two-step process : A compressed representation Φ d ∈ R n×d of the dataset is first obtained via feature construction. The original features are then ranked w.r.t. their importance for learning the d latent features (φ 1 , . . . , φ d ) composing Φ d . A novelty of the approach thus is to bridge the gap between the two categories of DR techniques, using feature construction as a tool for feature selection. Interestingly enough, this essentially amounts to falling back on a supervised multi-labeled feature selection problem, where datapoints are assigned one continuous label per constructed feature φ i , i ∈ [1, . . . , d].

Working hypotheses (fig. 4.2)

The main perk of unsup. learning is its increased adaptability compared to sup. learning (chap. 1) : Unsup. learning is applicable to any dataset, whether it pertains to Bioinformatics, insurance risk assessment or electrical engineering.

In order to be as general as possible, AGNOS involves minimal hypotheses. It follows the so-called Occam's razor principle [START_REF] Blumer | Occam's razor[END_REF], formulated by [START_REF] Kearns | An introduction to computational learning theory[END_REF]; [START_REF] Crowder | Occam learning through pattern discovery : Computational mechanics in ai systems[END_REF] as Occam learning, specifically stipulating that the sought models involve as few contingencies as possible. The cornerstone of DR is the manifold assumption (chap. 2) :

The manifold assumption The D-dimensional datapoints x 1 , . . . , x n lie near a manifold M d * of dimension d * s.t.

d * << D.
In the following, the manifold assumption is the only assumption done in AGNOS.

Combining both motivations

Following section 4.1.1, AGNOS involves two interacting parts : a FC algorithm and a FS mechanism, and the question thus becomes to select the algorithms involved in each component. From the assumption perspective and given the hybrid nature of AGNOS, it follows :

Assumptions(AGNOS) = { Manifold assumption } = Assumptions(FC) ∪ Assumptions(FS)
where the first equality comes from sec. 4.1.2. Accordingly, both FC and FS components of AGNOS must not require any hypotheses beyond the manifold assumption. This requirement will rule out most DR methods (most often implicitly involving additional assumptions, e.g. PCA [START_REF] Pearson | On lines and planes of closest fit to systems of points in space[END_REF] relies on the assumption that the underlying manifold be linear, or SFUS [START_REF] Ma | Web image annotation via subspace-sparsity collaborated feature selection[END_REF], assuming that all original features are boolean).

Eventually, the AGNOS DR pipeline proceeds by elimination and discards methods relying on additional hypotheses, as will now be discussed.

Typical DR requirements

DR methods typically make assumptions on three different components of the problem : the datapoints (sec. 4.1.4.1), the underlying manifold (sec. 4.1.4.2), or the original features (sec. 4.1.4.3).

Assumptions regarding the datapoints

Sup. DR algorithms [START_REF] Ye | Variable selection via penalized neural network : a drop-out-one loss approach[END_REF][START_REF] Zhao | Local structure based supervised feature extraction[END_REF], assuming that each datapoint x i is equipped with a label y i , are inappropriate by construction as we focus unsup. DR.

State-of-the-art unsup. FS methods [START_REF] He | Laplacian score for feature selection[END_REF][START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF][START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF][START_REF] Li | Unsupervised feature selection using non-negative spectral analysis[END_REF][START_REF] Nie | Unsupervised feature selection with structured graph optimization[END_REF] (chap. 3) rely on the assumption that the pairwise likeness of datapoints can be accurately depicted using the Euclidean distance in the original high-dimensional data representation. This assumption is unlikely to hold in the view of the curse of dimensionality (chap. 2). Spectral clustering-based FS is thus also out of contention.

Assumptions regarding the nature of M * d

Linear FC techniques [START_REF] Pearson | On lines and planes of closest fit to systems of points in space[END_REF][START_REF] Golu | Singular value decomposition and least squares solutions[END_REF]) assume that the underlying manifold is linear, and are thus inappropriate in the AGNOS context1 .

Although approaches such as Isomap [START_REF] Tenenbaum | A global geometric framework for nonlinear dimensionality reduction[END_REF] and Locally Linear Embedding [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF] are able to unfold a non-linear Swiss Roll (chap. 3), their success hinges on two additional informal implicit assumptions : i) the underlying manifold M * d is smooth (informally, the parametric equations defining the manifold are infinitely differentiable) ; and ii) M * d does not contain "holes". The fact that both assumptions cannot be efficiently (either computationally or statistically) be overcome is argued as follows. Consider the case of a torus (fig. 4.3), smooth manifold of intrinsic dimension 2 (w.r.t. any of the ID estimators from chap. 2). It is clear that the torus clearly cannot be flattened from 3D to 2D while preserving local neighborhoods due to the hole in the middle. Indeed, an option would be to "cut" the manifold as a form of pre-processing to DR (van der [START_REF] Van Der Maaten | Dimensionality reduction : A comparative review[END_REF], so that it can thereafter be unfolded like a Swiss Roll (figure 4.4). However, such a pre-processing step involves n runs of the Dijkstra algorithm [START_REF] Jianya | An efficient implementation of shortest path algorithm based on dijkstra algorithm[END_REF], being thus computationally hardly affordable in most application domains. Furthermore, such a "cutting" process effectively induces a deformation of the manifold, and would thus alter the final selection subset. Considering these two significant downsides, similarity-preserving methods are ultimately discarded for performing FC in AGNOS.

Assumptions regarding the original features

As seen in chapter 3, independent scoring FS methods [START_REF] Duda | Pattern classification[END_REF] assume that the original feature set F does not contain any XOR-like concept (sec. 3.2.1). State-of-the-art unsup. methods such as the Laplacian score [START_REF] He | Laplacian score for feature selection[END_REF], SPEC [START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF] or MCFS [START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF] require that no elements of F are redundant in order to rank features fairly. Lastly, other approaches [START_REF] Ma | Web image annotation via subspace-sparsity collaborated feature selection[END_REF][START_REF] Chang | A convex formulation for semi-supervised multi-label feature selection[END_REF] assume that F contains only boolean features. Consequently, all aforementioned algorithms are not eligible to perform FS in AGNOS.

Discussion

Following the previous discussion, AGNOS should involve :

-A non-linear unsup. data compression scheme that does not rely on pairwise Euclidean distances between highdimensional datapoints.

-A semi-independent or collective feature scoring criterion able to handle redundancy.

In view of these specifications, the natural candidate for performing FC is the non-linear AutoEncoder (chap. 3). Taking inspiration from neural network-based FS (chap. 3), a semi-independent feature scoring criterion is derived from the parameters of the AutoEncoder at the end of training. The following section discusses the feature redundancy problem in the context of an AutoEncoder.

The redundancy issue

In a nutshell, the general AGNOS scheme uses an AutoEncoder to produce a compression representation Φ d ∈ R n×d of the dataset ; the initial variables are thereafter ranked w.r.t. their importance for learning (φ 1 , . . . , φ d ). In the large sample limit, tuning the size of the encoder layer so that d = ID(X) ensures that i) Φ d contains all the information needed to reconstruct the original feature set ; and ii) each of φ 1 , . . . , φ d is informative to some extent.

Note however that how the information is organized and scattered among the constructed features is unknown, which might adversely affect the approach in the presence of redundant original features ; we shall come to this point in section 4.4.

Consider a basic AutoEncoder equipped only with a MSE loss :

L(F ) = D i=1 || fi -f i || 2 2
The contributions of each feature to the total loss appear to be weighted equally. However, let us consider the case where the feature set contains κ duplicates of the first feature (for some κ ∈ [2, . . . , D -1], f 1 = f 2 = . . . = f κ . In an unsupervised feature selection setting, we would like the probability of selecting one copy of f 1 to increase with κ. On the other hand, the probability of selecting multiple copies should clearly always be zero no matter the value of κ. However :

L(F ) = κ i=1 || fi -f 1 || 2 2 + D i=κ+1 || fi -f i || 2 2
The contribution of f 1 to the total loss is considered κ times more important than for another feature. The larger κ, the more reconstructing f 1 is a priority for the AutoEncoder during training, the more influence f 1 and all its duplicates ultimately hold over Φ d . Given that AGNOS aims to score original features w.r.t. this influence, all copies of f 1 will obtain the same score and be discarded or selected together. This is a major issue, as it is very common for real world datasets to contain clusters of strongly correlated features. A sensible feature selection algorithm should select at most one representative per such cluster.

A key requirement for AGNOS to is to address the initial feature redundancy. To this end, three regularizations will be proposed (sec. 4.4) in the spirit of LASSO [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] and group-LASSO [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF] to enforce the sparsity of the latent (aka constructed) features. Each regularization scheme comes with its own optimization criterion. The three criteria however rely on the same principles, disccused in section 4.3.

Feature scoring

As said, AGNOS ranks original features w.r.t. an importance score derived from the parameters of the trained Au-toEncoder, reflecting their respective influence for learning Φ d . Three scoring criteria will be examined in section 4.4, each corresponding to a declination of AGNOS.

The first criterion is based on the weights of the encoder part of the network, and is used in AGNOS-W. The second considers the gradients of the constructed features w.r.t. the input features and is relied upon by AGNOS-G. Lastly, the scoring criterion of AGNOS-S is based on an altered neural architecture.

The influence of f i , i ∈ [1, . . . , D] over Φ d can be assessed independently for each of the constructed features φ 1 , . . . , φ d . Section 4.3.1 discusses how these d influence measurements should be aggregated to obtain the final score for f i . Section 4.3.2 assesses the semi-independence nature of the resulting scoring criteria.

As AGNOS essentially amounts to falling back on a sup. multi-labeled FS problem, where datapoints are assigned one continuous label per constructed feature φ i , i ∈ [1, . . . , d], one could wonder why a new scoring procedure is needed rather than simply adapting existing multi-labeled FS techniques [START_REF] Ma | Web image annotation via subspace-sparsity collaborated feature selection[END_REF][START_REF] Chang | A convex formulation for semi-supervised multi-label feature selection[END_REF]. This interrogation is addressed by section 4.3.3.

From local influence to global feature score

As a result of d = ID(X), in the large sample limit all constructed features are guaranteed to be relevant to the reconstruction of the initial features to some extent. ∀(i, j) ∈ [1, . . . , D] × [1, . . . , d], let I(f i , φ j ) denote the influence of f i over φ j (to be formalized below). A simple definition for the ranking criterion is to consider the average influence of f i over all constructed features :

Score(f i ) = 1 d d j=1 I(f i , φ j ) (4.1)
However, this formulation fails to take into account the local informativity of the features. The proposed approach takes inspiration from the unsupervised feature selection algorithm MCFS [START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF] (chap. 3), in which a feature is considered important iff it is helpful to identify at least one cluster. Assume that for a certain f i , ∃j ∈ [1, . . . , d] s.t. I(f i , φ j ) is large and ∀k ∈ [1, . . . , d] s.t. k = j, I(f i , φ k ) = 0. Then, according to equation (4.1), Score(f i ) is small, and f i is likely to be discarded. However, if a feature has a strong influence on at least one constructed feature, it means that preserving the information it contains is very important for data compression. Therefore, such a feature f i should be ranked highly and prioritized for selection.

Accordingly, a more suitable ranking criterion definition is to consider the maximum influence of f i over any constructed feature :

Score

(f i ) = max j∈[1,...,d] I(f i , φ j ) (4.2)
The criteria used in AGNOS-W and AGNOS-G both follow this reasoning.

Remark.

Taking the maximum value might however be inappropriate if some latent variables are significantly less important than others. If an initial feature f i holds a strong influence over only one φ j of lesser importance, then f i should be discarded. Nevertheless, f i will inaccurately be ranked highly w.r.t. eq. (4.2). Considering this possible imbalance in constructed feature importance, a solution is to alter the structure of the AutoEncoder, so that instead of aggregating d measurements I(f i , φ j ), the overall influence of

f i over Φ d is directly observed : Score(f i ) = I(f i , Φ d ) (4.3)
This change of scoring paradigm is the basis of AGNOS-S (sec. 4.4)

Is AGNOS an independent scoring method ?

As seen in chapter 2, unlike collective or semi-independent scoring methods, independent feature selection algorithms bear the important limitation of being unable to recognize features that are useless by themselves, but important together.

In AGNOS, although Score(f i ) is ultimately assessed in isolation from the other scores, it is derived from the influence measurements I(f i , φ j ) (or I(f i , Φ d ) in the case of AGNOS-S). Given that each constructed feature is obtained by a non-linear combination of every initial variable, I(f i , φ j ) actually indirectly involves the whole original feature set F . AGNOS is therefore a semi-independent scoring method, and meets the requirement of being applicable to datasets containing XOR-like concepts.

Supervised multi-labeled feature selection via shared subspace learning

Sup. multi-labeled FS has been tackled by several approaches [START_REF] Ma | Web image annotation via subspace-sparsity collaborated feature selection[END_REF][START_REF] Chang | A convex formulation for semi-supervised multi-label feature selection[END_REF] in the context of image annotation. In this setting, each image is labeled with multiple concepts it is related to such as "people", "party", "entertainement".

Sup. multi-labeled FS methods then make the assumption (Ando and Zhang, 2005b) that images are likely to share some labels with each other (e.g. ("people,"work") and ("people","party") pertain to the same topic "people"). The goal is then to learn a shared subspace for the original features to help predict the labels.

Formally, let Y = [y 1 , . . . , y d ] ∈ {0, 1} d×n denote the label matrix, V ∈ R D×d and P ∈ R D×d two weight matrices, and Q ∈ R D×D the shared subspace matrix. The goal is then to find V * , P * , Q * s.t. :

(V * , P * , Q * ) = arg min V,P,Q loss (V + QP ) T X T , Y + µΩ(V, P ) with Q T Q = I D (4.4)
where Ω(V, P ) is a regularization term weighted by µ. The original features selected are then those corresponding to non-zero rows of V * + Q * P * . Arguably, one could adapt this framework to our unsupervised context by replacing Y with Φ T d . However, such an adaptation raises several theoretical and practical objections.

Firstly, the process of shared subspace learning basically amounts to optimizing a function mapping the samples to the labels. However, a specificity of our approach is that we already have access to this exact function : it is given by the encoding part of the AutoEncoder. Therefore, rather than learning a new mapping from scratch, we aim to leverage the existing one, by observing the parameters of the AutoEncoder.

Secondly, φ i ∈ R n is not a binary feature, but a continuous one. Therefore, the underlying assumption for subspace learning that samples share some labels is much less likely to hold.

Finally, a requirement for feature selection to be applicable in practice is to be less computationally expensive than learning without dimensionality reduction. Training an AutoEncoder to learn φ d , then solving the optimization problem in equation (4.4) is hardly affordable in terms of time complexity.

The AGNOS algorithm

We address the issue of redundancy among the original features by adapting LASSO-inspired regularization techniques to the unsupervised context. The AutoEncoder loss function is enhanced with a penalty term enforcing that only few, non-redundant initial features are retained during learning. This section presents the three considered regularization schemes, each corresponding to a declination of AGNOS : weight-based regularization for AGNOS-W (section 4.4.1), gradient-based regularization for AGNOS-G (section 4.4.2), and slack variable-based regularization for AGNOS-S (section 4.4.3). The three versions of AGNOS are then discussed in section 4.4.3.

Preprocessing : normalizing the original features

Intuitively, the larger the contribution of f i to the AutoEncoder loss L(F ), the more influent f i , the more likely f i is ultimately selected.

Assume however that for some pair of initial features f i and f j , one has f j = C * f i for some constant C > 1. Clearly both features carry the same information and their respective influences on Φ d should be equal. However, like in the case of redundant features and for the same reason, the contribution of f j to the MSE-based L(F ) tends to be C times larger than for f i , and f j is prioritized over f i for selection.

This selection bias towards features with large first and second order moments is handled by pre-processing the dataset, each initial feature being normalized and centered.

AGNOS with weight regularization : AGNOS-W

The first declination of AGNOS is AGNOS-W, which is inspired by supervised feature selection with neural networks techniques relying on weight-based regularization [START_REF] Bauer | Feature screening using signal-to-noise ratios[END_REF][START_REF] Roy | Feature selection using deep neural networks[END_REF]. The AutoEncoder loss function is enhanced with a group-LASSO [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF] penalty term on the weights of the hidden layer. Formally, letting W ∈ R D×d denote the encoder weight matrix and W i, * its i-th row, the L 2,1 penalization reads :

L(W ) = D i=1 d k=1 W 2 i,k = D i=1 W i, * 2
and the learning criterion of AGNOS-W is accordingly defined as :

L W (F ) = D i=1 || fi -f i || 2 2 + λL(W ) (4.5)
with λ the penalization weight. This regularization leads to a sparse input neural network [START_REF] Feng | Sparse-input neural networks for high-dimensional nonparametric regression and classication[END_REF] (chap.

3), enforcing that only a few original features are influential for learning Φ d . In order to simultaneously reconstruct the whole feature set and rely on as few original features as possible, the AutoEncoder is coerced to discard redundant features by setting the corresponding rows of W to 0. This learning criterion thus is meant to tackle the issue of redundant feature sets.

After training, the influence of f i over φ j can be observed through coefficient |W i,j |, as in RFE-SVM [START_REF] Guyon | Gene selection for cancer classification using support vector machines[END_REF]. The larger this quantity, the more important f i . Naturally, considering the absolute value of W i,j is necessary to properly account for negative weights, which are as informative as positive ones.

As previously discussed, f i should be considered important iff it is influential on at least one constructed feature. Therefore, the final score of the i-th feature is defined as the maximum influence on any hidden neuron :

Score W (f i ) = W i, * ∞ (4.6)
This leads to the following algorithm :

(F ) = D i=1 fi -f i 2 2 + λ D i=1 W i,• 2
until convergence Rank features by decreasing scores with Score

W (f i ) = W i,• ∞ .

AGNOS with gradient regularization : AGNOS-G

The second proposed declination of AGNOS is AGNOS-G, inspired by studies on the benefits of gradient regularization [START_REF] Rifai | Contractive auto-encoders : Explicit invariance during feature extraction[END_REF][START_REF] Van Der Maaten | Dimensionality reduction : A comparative review[END_REF].

In the supervised context,Varga et al. ( 2017) have recently shown that L 2 regularization on the gradients of the output layer helps improve the predictive accuracy of discriminative neural networks. This improvement is explained by the fact that smaller output gradients leads to a decreased sensitivity of the learning goal w.r.t. the input, which helps combat overfitting.

In the unsupervised context, [START_REF] Rifai | Contractive auto-encoders : Explicit invariance during feature extraction[END_REF] introduced contractive AutoEncoders. This corresponds to enhancing a standard AutoEncoder with a L 2 penalty term on the gradients of the hidden layer w.r.t. the input dimensions. The compressed representation Φ d produced by contractive AutoEncoders has been empirically shown to be more robust w.r.t. input noise than for traditional AutoEncoders. By contrast with the supervised setting, the output layer of an Au-toEncoder is not the end goal of learning, rather a byproduct of feature construction. The actual learning goal is Φ d , which resides in the hidden layer. This reasoning motivates penalizing the hidden layer gradients rather than the output ones.

AGNOS-G also relies on regularizing the gradients of the hidden layer. Given that the end goal of AGNOS is feature selection, this regularization should aim to simultaneously cancel all gradients of the constructed features w.r.t. redundant original features. The L 2 regularization used for contractive AutoEncoders is inadequate for that purpose ; as seen in chapter 3, an L 2 penalty cannot enforce sparsity.

Therefore, AGNOS-G instead employs a group-LASSO [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF] regularization instead, regrouping hidden layer gradients by original feature :

L(Z d ) = D i=1 n k=1 d j=1 ∂z j ∂f i (x k ) 2 (4.7)
The total loss function of the AutoEncoder is then :

L G (F ) = D i=1 || fi -f i || 2 2 + λL(Z d ) (4.8)
Similarly as in AGNOS-W, the combination of the mean square error and the sparsity pressure incentivizes the AutoEncoder to nullify all hidden layer gradients related to superfluous initial features, therefore successfully tackling the redundancy issue.

After training, the influence of f i over φ j can be observed through the gradient of φ j w.r.t. f i , estimated at each datapoint :

I(f i , z j ) = n k=1 ∂φ j ∂f i (x k ) 2 (4.9)
With the same reasoning as for AGNOS-W, f i should be considered important iff it is influential for at least one constructed feature. Therefore, the final score is defined as :

Score G (f i ) = max 1≤j≤d n k=1 ∂φ j ∂f i (x k ) 2 (4.10)
The larger this quantity, the more important f i . This scoring criterion is similar to that of supervised feature saliency selection methods [START_REF] Steppe | Improved feature screening in feedforward neural networks[END_REF][START_REF] Zurada | Pertubation method for deleting redundant inputs of perceptron networks[END_REF], with the notable difference that we consider the hidden layer gradients rather than the output ones. This is consistent with the observation that our learning goal is not the output of the network, rather Φ d . Interestingly enough, this modification also holds two practical advantages over traditional feature saliency techniques. On one hand, examining the gradients halfway through the feedforward process helps reduce the probability of encountering a vanishing gradient problem [START_REF] Pascanu | On the difficulty of training recurrent neural networks[END_REF]. On the other hand, obtaining the pointwise gradients of the hidden layer w.r.t. the input dimensions requires n × d × D computations for each training iteration, as opposed to n × D 2 computations for the gradients of the output layer. Given that d << D, this is a significant reduction in time complexity.

Moreover, in the case of an encoder with a single hidden layer, this score can be computed in a simple fashion. For example, with a tanh activation function, one has :

Score G (f i ) = max 1≤j≤d n k=1 W 2 i,j 1 -φ j (x k ) 2 2 (4.

AGNOS with slack variables : AGNOS-S

A third version of AGNOS is considered, called AGNOS-S and inspired from [START_REF] Leray | Feature selection with neural networks[END_REF]; [START_REF] Li | Deep feature selection : theory and application to identify enhancers and promoters[END_REF]; [START_REF] Goudet | Learning functional causal models with generative neural networks[END_REF]. The neural architecture is augmented with a sparse one-to-one linear layer composed of slack variables, inserted between the input and the first hidden layer. Formally, to each feature f i is associated a (learned) coefficient a i initialized to 1, and the encoder is fed with the vector (a i f i ) (fig. 4.5). The learning criterion here is the reconstruction loss augmented with an L 1 penalization on the slack variables : Like in LASSO [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF], the L 1 penalization pushes the slack variables toward a sparse vector such that features unnecessary to reconstruct F are associated a null coefficient. This regularization thus efficiently tackles the issue of redundancy. In order to prevent the network from drawing slack variables toward 0 and compensating for the small slack variables by proportionally amplifying the encoder weights, the encoder weight vector W is normalized ( W 2 = 1). In order to obtain a standardized protocol, this normalization is also applied in the AGNOS-W and AGNOS-G variants.

L S (F ) = D i=1 || fi -f i || 2 2 + λ D i=1 |a i | (4.12)
Similarly as in [START_REF] Li | Deep feature selection : theory and application to identify enhancers and promoters[END_REF], the score of the i-th feature is eventually set to |a i | : this single real-valued coefficient reflects the contribution of f i to the latent representation, and its importance to reconstruct the whole feature set :

Score S (f i ) = |a i | (4.13)
The larger this quantity, the more important f i . This corresponds to directly measuring I(f i , Z d ) rather than I(f i , z j ) for each z j . Therefore, a major benefit of this altered neural architecture is to provide an accurate ranking criterion even if some constructed features are more important than others.

Discussion

About tied weights While designing the architecture of an AutoEncoder, it is common practice to rely on weight sharing [START_REF] Baldi | Autoencoders, unsupervised learning, and deep architectures[END_REF][START_REF] Bengio | Deep learning of representations for unsupervised and transfer learning[END_REF]. This practice, also referred to as tied weights, consists in setting the weights of the decoder part of the network to the transpose of the encoder weights (that is, in the case of a single hidden layer, W (decoder) = W T ). An immediate benefit lies in the reduced number of learned parameters, which both lowers the space complexity of training and helps prevent overfitting. Without weight sharing, the AutoEncoder might learn very small encoder weights (corresponding to a near linear regime in the activation functions) and compensate with large decoder weights. This essentially amounts to learning the identity function. An additional benefit of weight sharing is therefore its potential regularizing effect, which prevents learning this degenerate solution. However, weight sharing may be detrimental to learning when the end goal is not reconstruction but feature selection. Assume the AutoEncoder is able to reconstruct the whole feature set and that no initial feature is constant. By construction :

∀j ∈ [1, . . . , D], ∃i ∈ [1, . . . , d], |W (decoder) ij | > 0 With weight sharing, W (decoder) ij = W ji . Therefore : ∀j ∈ [1, . . . , D], ∃i ∈ [1, . . . , d], |W ji | > 0
In other words, there is at least one non-zero coefficient per row of W . This means that every initial feature is considered at least somewhat important w.r.t. the scoring function of AGNOS-W, hindering feature selection. This is precisely what the L 2,1 weight regularization employed in AGNOS-W aims to avoid, justifying leaving encoder and decoder weights untied.

Although the negative impact of weight sharing on AGNOS-G and AGNOS-S is less clear from a theoretical standpoint, preliminary experiments have shown that relying on tied weights led to decreased FS performance in both these versions of AGNOS.

Should the group LASSO penalty be sparse ? Recent supervised neural network-based FS methods [START_REF] Roy | Feature selection using deep neural networks[END_REF][START_REF] Li | Deep feature selection : theory and application to identify enhancers and promoters[END_REF][START_REF] Ye | Variable selection via penalized neural network : a drop-out-one loss approach[END_REF] (chap. 3) perform regularization via a sparse group LASSO penalty [START_REF] Simon | A sparse-group lasso[END_REF] on the weights of the first hidden layer.

By contrast, both AGNOS-W and AGNOS-G rely on a "vanilla" non-sparse group LASSO [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF] penalty instead. A first argument for this design choice is to avoid introducing the additional hyperparameter α, which would increase the complexity of the sensitivity study (more in chap. 6).

More importantly, the goal of the sparse group LASSO is to achieve sparsity both at the group level and inside each group, which is a desirable property in the supervised setting [START_REF] Feng | Sparse-input neural networks for high-dimensional nonparametric regression and classication[END_REF]. However, in the context of an AutoEncoder performing unsupervised learning, a sparse group LASSO penalty would induce a compressed representation s.t. each original feature contributes to as few constructed features as possible. This corresponds to learning a disentangled representation [START_REF] Bengio | Representation learning : A review and new perspectives[END_REF][START_REF] Kim | Disentangling by factorising[END_REF]. Learning a disentangled representation essentially corresponds to sacrificing some efficiency regarding data compression2 in exchange for better model interpretability3 . However, studying the impact of such a tradeoff is beyond the scope of this thesis.

Normalizing structural regularization strength λ The sparsity penalty terms implemented in AGNOS-S, AGNOS-W and AGNOS-G respectively involve D slack variables, D × d weights, and D × d × n gradients. The number of parameters involved in the structural regularization thus depends on the considered variant of the approach. Accordingly, for the sake of consistency and homogeneity, the respective penalty strengths

(λ S , λ W , λ G ) are normalized s.t. λ W = λ S d and λ G = λ S dn .
Impartiality Impartiality denotes the absence of unwanted bias towards selecting features of a certain nature, structure or apparent purpose. Consider for instance P I 1 s.t. :

P I 1 (S k ) = 1 if S k contains only categorical features 0 otherwise P I 1 incentivizes the selection of categorical features regardless of information carried, thus fails to meet the requirement of impartiality.

Expressivity The more information is taken into account by P I, the more expressive this performance indicator.

Consider e.g. the following P I 2 :

P I 2 (S k ) = max f ∈S k cov(f , f 1 )
The quality of S k is assessed using only a small piece of information (the covariance with a single particular feature) ; the expressiveness of P I 2 is hence clearly low.

Stability

The score of a particular unsup. FS algorithm w.r.t. P I is expected to fluctuate according to the selection subset size k and the set Θ of algorithm hyperparameters. However, the position of this method in the ranking of unsup.

FS approaches should hardly depend on k and Θ.

Consequently, P I is deemed stable iff the associated ordering of unsup. selection techniques is consistent across a wide range of values for k and Θ. In other words, what matters is the relative hierarchy of algorithms rather than the respective absolute scores.

Consider e.g. P I 3 s.t. :

P I 3 (S k ) = P I 1 (S k ) if k ≤ 10 P I 2 (S k ) if k > 10
The ordering of selection methods is likely shuffled when considering subsets of more than ten features. P I 3 is therefore unstable1 .

Interpretability In order to comply with FTA learning (chap. 1), a performance indicator should be easily understandable, even by a non-expert in ML. The behavior of information-theoretic measurements such as the Variation of Information (VI) [START_REF] Meil Ȃ | Comparing clusterings by the variation of information[END_REF] is unintuitive, as claimed by [START_REF] Gates | On comparing clusterings : an element-centric framework unifies overlaps and hierarchy[END_REF] (more in sec. 5.2). Such indicators thus arguably lack in interpretability.

Simplicity Assume FS algorithm A is ranked highly w.r.t. performance indicator P I. This could indicate that A is a better selection method than its competitors. However, it may also be that P I is partial towards the selection subset resulting of A. In the absence of ground truth, disentangling the experimental validation of unsup. FS methods from the empirical study of P I itself is therefore challenging. This issue is amplified in the presence of important hyperparameters for P I. Consider for instance P I 4 s.t. :

∀(α, β, γ) ∈ R 3 , P I 4 (S k , α, β, γ) = αP I 1 (S k ) + βP I 2 (S k ) + γP I 3 (S k )
The goal of measuring the quality of S k with P I 4 is mingled with the task of tuning α, β and γ. A simple performance indicator should therefore, unlike P I 4 , include as few hyperparameters as possible, so that it can be considered a fixed component of the validation process.

Cost-efficiency

In addition to all aforementioned qualities, an ideal performance indicator should also be as inexpensive as possible in terms of computational complexity (both time and space-wise). Most notably and in view of Big Data, the assessment procedure should scale well w.r.t. both the number of datapoints and the number of original features.

Discussion

As said, state-of-the-art unsup. FS methods [START_REF] He | Laplacian score for feature selection[END_REF][START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF][START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF][START_REF] Li | Unsupervised feature selection using non-negative spectral analysis[END_REF][START_REF] Nie | Unsupervised feature selection with structured graph optimization[END_REF] are typically empirically assessed with a sup. performance indicator. We claim that this procedure nets significant downsides for little benefits : Claim: Typical sup. performance indicators for unsup. FS all fail to meet the impartiality, expressivity and stability properties. This claim will be further discussed in section 5.2 and supported by empirical evidence in our experimental study (chap. 6). Our campaign of experiments will also show that, relatively to sup. performance indicators, the proposed unsup. FIT criterion is more impartial, expressive and stable. The main downside of this methodological contribution lies in its poor cost-efficiency (chap. 6). A direction for future research consists in improving the cost-efficiency of the FIT procedure (chap. 7).

Supervised performance indicators

State-of-the-art unsup. FS methods [START_REF] He | Laplacian score for feature selection[END_REF][START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF][START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF][START_REF] Li | Unsupervised feature selection using non-negative spectral analysis[END_REF] typically rely on one of two techniques to quantify the quality of the retained feature subset S k . The first technique is classifierbased (sec. 5.2.1), while the second one is clustering-based (sec. 5.2.2). Section 5.2.3 will thereafter investigate our claim that sup. performance indicators are ill-suited for assessing unsup. FS.

Classifier-based criterion

Given that we are here concerned with sup. assessment of unsup. FS, let f * denote the target feature and χ a classifier. Let the datapoints be split into a training set X train and a testing set X test . Let δ : N × N → {0, 1} denote the function s.t. :

∀(a, b) ∈ N 2 , δ(a, b) = 1 if a = b 0 otherwise.
The predictive power of the selection subset S k is measured using h. h is first trained on X train , considering only the features in S k . The test classification error rate of φ is thereafter defined as :

ER φ (S k , f * ) = 1 - x∈Xtest δ (h(x), f * (x)) = 1 |X test | x∈Xtest L f * (x), f (x) (5.1)
The lower ER φ (S k , f * ), the more accurate χ for predicting f * using only S k . Unsup. FS algorithms are then ranked in ascending order w.r.t. the respective resulting error rates.

The resulting ranking is actually a multivariate function involving f * , the classifier structure (e.g. Decision Tree [START_REF] Safavian | A survey of decision tree classifier methodology[END_REF], Random Forest (Díaz-Uriarte and Andres, 2006), Gaussian SVM [START_REF] Scholkopf | Learning with kernels : support vector machines, regularization, optimization, and beyond[END_REF]), the hyperparameters of h, and the random split between X train and X test . The dependency w.r.t. the train/test split is typically removed by relying on Leave-One-Out (LOO) cross-validation [START_REF] Kohavi | A study of cross-validation and bootstrap for accuracy estimation and model selection[END_REF] 2 .

The most common choice for g in the literature [START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF][START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF] is the p-Nearest-Neighbor (p-NN) classifier. The motivation underlying this choice is fourfold.

First of all, p-NN classification is non-linear, which is required due to working hypotheses (sec. 4.1.2). Furthermore, the unreliability of Euclidean distance-based similarities caused by the curse of dimensionality is alleviated in the kdimensional space defined by S k (provided that k << D).

Moreover, p-NN classification is usually more resilient w.r.t. overfitting than e.g. Decision-Tree based classification such as Random Forest. Lastly, a p-NN classifier does not involve any hyperparameters besides p, typically fixed to p = 1 (thus predicting the class of the sample closest to the considered datapoint). This classifier therefore adheres to the notion of simplicity introduced earlier.

With p = 1 and x i denoting the nearest neighbor of x i 3 , the error rate from equation (5.1) can then be rewritten as [START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF] :

ER(S k , f * ) = 1 - 1 n n i=1 δ f * (x i ), f * (x i ) (5.2)
The empirical assessment of the three declinations of AGNOS and baseline unsupervised FS algorithms w.r.t. this performance indicator will be provided in our experimental validation (chap. 6) with p = 5 neighbors, for the sake of stability.

Clustering-based metrics

In this procedure, samples are clustered with a standard K-means algorithm [START_REF] Hartigann | Algorithm as 136 : A k-means clustering algorithm[END_REF]) considering only the features in S k . Similarly as for the p-NN classifier, relying on a k-dimensional space instead of a D-dimensional one helps escape the curse of dimensionality and provide reliable clusters.

Notations As a result of K-means clustering, each sample is assigned to a unique cluster. This essentially amounts to equipping each datapoint x i with a pseudo-label (the corresponding cluster number). Let f * denote the resulting new feature vector, containing κ unique values (κ governing the number of clusters). Let c denote the number of classes in f * . ∀(i, j) ∈ [1, . . . , κ] × [1, . . . , c], let A i and B j respectively denote the set of samples belonging to the i-th cluster and the set of samples belonging to the j-th class.

. Given the above framework, two performance indicators are typically designed to assess the relevance of the clusters. Section 5.2.2.1 introduces a first criterion measuring the homogeneity of the clusters. Section 5.2.2.2 thereafter presents an alternate definition of relevance rooted in information theory.

In order to fully uncover the learning goal, it is clear that K-means clustering should be performed with κ ≥ c. However, tuning κ within the range [c, n] is both challenging and crucial to the success of clustering-based performance indicators, as will be discussed in section 5.2.2.3.

2. Arguably, the results still weakly depend on the order in which the n-folds are considered for training g. 3. Formally :

∀(i, j) ∈ [1, . . . , n] 2 s.t. j = i, f ∈S k f (xi) -f (x i ) 2 ≤ f ∈S k f (xi) -f (xj) 2

Cluster purity-based performance indicator

The goal is here to measure how well aligned f * is with f * , up to a reordering of the clusters. Formally, let Θ κ→c denote the family of functions θ :

[1, . . . , κ] → [1, . . . , c].
The accuracy score (ACC) [START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF][START_REF] Li | Unsupervised feature selection using non-negative spectral analysis[END_REF] of the selection subset S k is then defined as :

ACC(S k , f * ) = max θ∈Θκ→c 1 n κ i=1 c j=1 |A θ(i) ∩ B j | (5.3)
This can be rewritten from the perspective of the samples :

ACC(S k , f * ) = max θ∈Θκ→c 1 n n i=1 δ θ f * (x i ) , f * (x i ) (5.4)
It directly follows from eq. (5.4) that ∀S k ∈ F, 0 ≤ ACC(S k , f * ) ≤ 1, tightness of the upper bound being guaranteed by κ ≥ c. The higher ACC(S k , f * ), the better the clusters allow identifying the different target concepts, the better the selection.

The ranking of the three declinations of AGNOS and baseline unsupervised FS algorithms w.r.t. the ACC score will be discussed in our empirical study (chap. 6).

Information theoretic performance indicator

Following information theory [START_REF] Cover | Elements of information theory[END_REF], f * and f * can be interpreted as the respective realizations of two random variables. The core idea is then to measure the reduction of uncertainty (a.k.a. entropy) concerning the realization f * gained from knowing the realization f * .

The individual entropies of f * and f * are respectively denoted H( f * ) and H(f * ), defined as :

H( f * ) = - κ i=1 |A i | n log |A i | n H(f * ) = - c j=1 |B j | n log |B j | n (5.5)
Accordingly, the joint entropy H( f * , f * ) is given by :

H( f * , f * ) = - κ i=1 c j=1 |A i ∩ B j | n log |A i ∩ B j | n (5.6)
The mutual information (MI) [START_REF] Banerjee | Clustering on the unit hypersphere using von mises-fisher distributions[END_REF] performance indicator then measures how much knowledge about learning goal f * can be inferred from f * . M I( f * , f * ) corresponds to the sum of individual entropies minus the joint entropy, that is :

M I( f * , f * ) = H( f * ) + H(f * ) -H( f * , f * ) (5.7)
The higher the MI, the more informative the clustering for identifying the target, the better the selection.

By equations (5.5) and (5.6) :

0 ≤ H( f * ) ≤ log(κ) 0 ≤ H(f * ) ≤ log(c) H( f * )max H( f * ), H(f * ) ≤ H( f * , f * ) ≤ H( f * ) + H(f * )
Injecting these upper and lower bounds in eq. (5.7) yields :

0 ≤ M I( f * , f * ) ≤ min log(κ), log(c) (5.8)
Eq. (5.8) is source of an interpretability issue of the MI : the result M I( f * , f * ) = 1 can depict an arbitrarily good or bad selection subset, depending on the relative values of κ, c and n.

In order to obtain interpretable results, numerous possible normalizations of the MI have been proposed over the years, such as the minimum Normalized Mutual Information (N M I min ) [START_REF] Liu | Constructing tumor progression pathways and biomarker discovery with fuzzy kernel kmeans and dna methylation data[END_REF], joint NMI (N M I joint ) [START_REF] Yao | Information-theoretic measures for knowledge discovery and data mining[END_REF], square root NMI (N M I sqrt ) [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF] or Adjusted Mutual Information (AMI) [START_REF] Vinh | Information theoretic measures for clusterings comparison[END_REF]. Each normalization variant comes with specific pros and cons. For instance, the N M I min 4 is ill-suited for continuous learning goals s.t. c = n, given that any selection subset S k leads to a perfect score N M I min = 1. A thorough discussion of the respective benefits and limitations of each normalization procedure can be found in [START_REF] Vinh | Information theoretic measures for clusterings comparison : Variants, properties, normalization and correction for chance[END_REF].

For the sake of unsup. FS assessment, the most commonly used NMI variant [START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF][START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF]) is the mean NMI (N M I mean ) [START_REF] Kvalseth | Entropy and correlation : Some comments[END_REF], which we will in the rest of this work simply refer to as N M I :

N M I(S k , f * ) = 2 M I( f * , f * ) H( f * ) + H(f * )
(5.9)

The higher the NMI, the better the selection. A NMI score of 0 indicates no mutual information, while the maximum score of 1 indicates perfect correlation. The empirical ranking of the three declinations of AGNOS and baseline unsupervised FS algorithms w.r.t. the NMI score will be provided in chapter 6.

Tuning the number of clusters κ

The process of normalizing the mutual information does not remove the dependency of the performance indicator on κ. Most notably, the higher κ, the higher the NMI, as illustrated in figure 5.1.

The ACC score also faces the same issue, although admittedly to a lesser extent (more in chap. 6). In order to limit the bias in both performance indicators caused by large values of κ, we will in our experimental validation set κ to the minimal value allowing perfect scores, that is κ = c.

Other clustering-based sup. performance indicators such as e.g. the Variation of Information (Meil ȃ, 2003) also depend on κ, oftentimes in a non-monotonous fashion (fig. 5.2).

The number of clusters is therefore a crucial hyperparameter to all aforementioned clustering-based measurements, s.t. fine-tuning κ is necessary to fairly compare unsup. FS algorithms. Consequently, these performance indicators do not comply with the requirement of simplicity.

In order to fulfill this requirement and lower the importance of κ, [START_REF] Gates | On comparing clusterings : an element-centric framework unifies overlaps and hierarchy[END_REF] propose an element-centric (EC) clustering-based indicator. While this type of indicator has to the best of our knowledge not yet been utilized for the purpose of unsup. FS assessment, it is in any case ill-suited, as the validation procedure would still be supervised. Thus, the crux of the problem remains, as exposed in our earlier claim : sup. performance indicators, by design, lack impartiality, expressivity and stability. The following section will further discuss this claim. A byproduct of the limited expressiveness of sup. assessment is that ignoring D -k features means that the amount of information "wasted" depends on k. Arguably, this hinders the stability of the validation procedure, as will be empirically demonstrated in chapter 6.

Formally, NMImin

( f * , f * ) = M I( f * ,f * ) min H( f * ),H(f * ) .

Unsup. assessment of unsup. FS

The proposed FIT criterion

In accordance with the principle that any initial feature is potentially valuable, an unsup. performance indicator should evaluate the ability of S k to recover all original variables simultaneously, rather than a single specific f * .

As such, we propose an intuitive adaptation of the sup. classifier-based criterion from section 5.2.1 to the unsup. context ; given S k , D Nearest-Neighbor regressors χ 1 , . . . , χ D are trained from S k to respectively recover f 1 , . . . , f D . The motivation for relying on regressors rather than classifiers is that F may simultaneously contain categorical and continuous features.

The score of S k is then derived from the average reconstruction error of the regressors. A reconstruction error is an unbounded quantity, and thus faces the same interpretability issue as the MI (sec. 5.2). We therefore rely on the R 2 score instead, which we now introduce.

The coefficient of determination R 2 Given y a regression target, ȳ the mean of y across all samples and ŷ the target predicted by a regressor, the R 2 score is defined as :

R 2 (y, ŷ) = 1 - n i=1 (y i -ŷi ) 2 n i=1 (y i -ȳ) 2
(5.10)

The R 2 score measures the proportion of the variance in y that is accounted for by the regression model. R 2 (y, ŷ) is therefore an indicator of "goodness-of-fit". The maximal R 2 score of 1 indicates that the regressor predicts y perfectly. If regression fails and the model output is ȳ for all datapoints (meaning the input variables are disregarded), then If original features are normalized and centered, ȳ = 0 and n i=1

(y i -ȳ) 2 = n i=1 y 2 i = σ(y) = 1.
Therefore, eq. (5.10) can be rewritten as :

R 2 (y, ŷ) = 1 -M SE(y, ŷ) (5.11)

Consequently, the R 2 score can in the context of this work be interpreted as a normalization of the MSE. This leads to the following algorithm :

Algorithm 8 The unsup. FIT criterion Input : Dataset X, Selection subset S k Parameter :

Number of neighbors p Output : F IT (S k ) Let R 2 avg (S k ) = 0. for i = 1, . . . , n do Find the p nearest neighbors x 1 i , . . . , x p i of x i w.r.t. S k end for j = 1, . . . , D do Fit f j from S k using the p-NN regressor χ j R 2 avg (S k ) ← R 2 avg (S k ) + R 2 (f j , χ j (S k )) end Return F IT (S k ) = R 2 avg (S k ) D
The time complexity of computing MSE-based scores is negligible compared to that of searching for the p nearest neighbors of each datapoint. Furthermore, the structure of the pseudocode in alg. 8 underlines that the neighborhood search needs only be performed once, rather than D times. Consequently, the FIT score is only marginally less costefficient than the sup. classifier-based criterion.

Discussion

The ideal selection subset S * k w.r.t. FIT best supports the reconstruction of the whole dataset. This entails three important consequences.

First of all and by contrast with sup. performance indicators, the FIT assessment procedure is not swayed towards features most relevant for a specific purpose, hinting at impartiality. Naturally, one cannot claim the approach is devoid of bias, as the retained features in S k might be improper to the particular prediction of any considered feature (e.g. due to their distribution). This could be further alleviated by building a classifier based on S k for each feature. This approach however suffers from fundamental and computational issues, see below.

By construction, FIT actually exploits the information carried by every variable rather than only S k and f * , thus enjoys a higher expressivity relatively to sup. indicators.

5. The R 2 notation is therefore slightly misleading. In order to lift this ambiguity, alternate notations such as the Nash-Sutcliffe Efficiency (NSE) [START_REF] Mccuen | Evaluation of the nash-sutcliffe efficiency index[END_REF] are sometimes preferred instead.

Chapitre 6

Experimental validation

This chapter presents the experimental validation of AGNOS. The experimental setup is first introduced in section 6.1, along with a preliminary study regarding the intrinsic dimension of the benchmark datasets. Following chapter 5, the supervised performance of AGNOS-S, AGNOS-W and AGNOS-G is assessed and compared to baselines in section 6.2. Section 6.3 thereafter exhibits the unsupervised performance of AGNOS w.r.t. the novel proposed FIT criterion. A sensitivity study of the results is conducted in section 6.4, to assess the influence of the hyperparameters of the method. Section 6.5 concludes the chapter with a final discussion of the results. 2018) is an open-source feature selection repository developed at Arizona State University. It is built upon the widely used Python machine learning package scikit-learn. The skfeature databank currently contains 29 datasets commonly used in feature selection tasks and challenges. These datasets span multiple domains, including text data, face image data, genomics data, hand written text in image format, as well as artificial data specifically generated for feature selection purposes.

Experimental setup and preliminary study

Skfeature also provides ready-made Python implementations for 34 popular feature selection algorithms (28 supervised and 6 unsupervised), facilitating empirical comparison of new FS approaches w.r.t. some state-of-the-art methods.

Due to its open source nature and ease of use, skfeature has risen in popularity as an international benchmark for feature selection Li et al. (2017); [START_REF] Chen | Kernel feature selection via conditional covariance minimization[END_REF]. This justifies our usage of skfeature for the experimental validation of AGNOS.

Datasets

Experiments are carried on 8 datasets taken from the scikit-feature database, selected for their diversity in number of features, types (categorical and continuous) and domain (face image, sound processing and medical data). Complementary experiments on the other 21 datasets from the database have shown the representativity of the results obtained on the 8 chosen datasets. In all datasets but one (Isolet), the number of samples is small w.r.t. the number of features D. Dataset size, dimensionality, number of classes and data type are summarized in Table 6

Performance indicators

The three variants of AGNOS are compared to four unsup. baselines introduced in section 3.2.3 : the Laplacian score [START_REF] He | Laplacian score for feature selection[END_REF], SPEC [START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF], MCFS [START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF] and NDFS [START_REF] Li | Unsupervised feature selection using non-negative spectral analysis[END_REF]. The implementations of all baselines have been taken from the scikit-feature database, and all their hyperparameters have been set to their default values.

Four performance indicators have been considered, where the first three indicators correspond to the typical sup. assessment procedure (chap. 5 : the sup. accuracy of a p-NN classifier, the ACC score and the NMI score) and the fourth performance metric is the proposed unsup. FIT criterion.

Hyperparameters

In all experiments, AGNOS is ran using a single hidden layer Auto-Encoder with tanh activation functions for both encoder and decoder, Glorot parameter initialization [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF], and the Adam [START_REF] Ruder | An overview of gradient descent optimization algorithms[END_REF] gradient descent scheme, with initial learning rate of 10 -3 . The number p of neighbors used for all p-NN regressors involved in the FIT score (chap. 5) is set to p = 51 . Following section 5.2.2.3, the number of clusters to use for clustering-based performance indicators is set to κ = c for all experiments, where c is the number of classes in the sup. learning goal.

The results provided in sections 6.2 and 6.3 were recorded with the following default hyperparameter values for AGNOS : hidden layer size d = ID (estimated intrinsic dimension of the data), sparsity penalty strength λ = 1. The sensitivity of the results w.r.t. both d and λ will be assessed in section 6.4.

Intrinsic dimension and selection subset size

As seen (chap. 4), AGNOS includes two important preprocessing steps : i) feature normalization and ii) intrinsic dimension estimation. Therefore, we begin our experimental study by analyzing the ID estimation process. Section 6.1.2.1 presents the estimated ID for every benchmark dataset, as well as how these results are prone to change as a consequence of feature normalization. An analysis of the faithfulness of the ID estimator is thereafter conducted in section 6.1.2.2. The fact that the estimated ID is small compared to the original dimensionality for every dataset highlights the potential of feature selection for data compression. For 6 out of the 8 benchmark datasets, ID is mostly unaffected by the rescaling of each feature to zero mean and unit variance.

Intrinsic dimension estimation

However, for the remaining 2 datasets (Arcene and TOX171), the normalization process provokes a significant change in ID, which more than doubles in both cases. This suggests that the correlation between features can decrease as a result of normalization. This could limit the potential of data compression. However, feature normalization is mandatory to avoid bias in the selection (chap. 4), and is thus relied upon in AGNOS regardless of this drawback. We will therefore consider the ID of normalized data in our experimental validation.

Assessing the quality of the ID estimation

As said, the results from table 6.2 are merely an approximation, of unknown precision, of the "true" intrinsic dimension of the data. We therefore attempt to estimate the quality of the approximation ID.

In order to simulate randomness3 , we opt to perform 20 uniform train/test splits for each dataset. ID is thus estimated 20 times, considering for each run only the 80% of samples in the training set. The results are contained in table 6.3.

On half of the benchmark datasets (namely Isolet, ORL, pixraw10P and warpPIE10P), the average estimated ID over the 20 splits is close to the ID obtained with all samples (table 6.2, 10% variation or less), with a small variance (at most 5% of the expected value). This holds true for both the normalized and unnormalized versions of the data. The 2-NN method thus appears to be a trustworthy ID estimator for these datasets.

Although the mean estimated ID across splits is also consistent with table 6.2 for the remaining half of the benchmark datasets (namely Arcene, ProstateGE, TOX171 and Yale), we observe a high variance (between 7% and 20% of the expected value). This means that the results of a run are strongly dependent on which 20% of samples are omitted for ID estimation in that run. Therefore, this indicates that the ID estimator is sensitive w.r.t. outliers for these datasets, and that ID is a brittle estimation of the true intrinsic dimension in those cases.

The mean estimated ID is twice larger in the normalized version of the data for Arcene and TOX171, which is in line with table 6.2. However, a novel observation is that feature normalization also leads to a disproportionate increase in variance in both cases (from 2% to 7% in TOX171 ; from 4% to 19% in Arcene). This suggests that rescaling does not modify the apparent intrinsic dimensionality uniformly across the dataset, increasing the sensitivity of the ID estimator.

The main takeaway of this preliminary analysis is that the constraint d = ID should likely be relaxed in all three declinations of AGNOS, which section 6.4.2 will showcase the impact of.

Selection subset size

Following the manifold assumption and the discussion on intrinsic dimension (chap. 2), the intrinsic dimension ID of the data provides a lower bound for the selection subset size k by construction. In practice, it is unlikely that any selection subset of size k = ID is able to fully recover the original feature set F . Furthermore, we only have access to an approximation Î D of the "true" intrinsic dimension, of unknown precision.

In order to avoid selecting too few features and for the sake of cautiousness, we therefore want that k > ID. The wider the margin between ID and k, the more likely S k to be sufficient for recovering F . However, the larger k, the more similar the respective performances of the different considered unsupervised FS algorithms tend to be, as will be shown in section 6.4.

k should therefore ultimately be set to a value larger than the estimated intrinsic dimension of the datasets, but small enough that we can observe a stark contrast in performance among the baselines and the three declinations of AGNOS. As a consequence of preliminary experiments, we choose the default selection subset size to be k = 100. For the sake of completeness, we will however study the behavior of the baselines and AGNOS for varying subset sizes in section 6.4.

Supervised evaluation results

Section 6.2.1 first assesses the stability of the performance of AGNOS (according to the 3 considered supervised performance indicators) w.r.t. the random initialization of the AutoEncoder parameters. AGNOS-S, AGNOS-G and AGNOS-W are then compared to the baselines in section 6.2.2.

Sensitivity w.r.t. initialization of network parameters

All baseline unsupervised FS methods considered are deterministic algorithms. By contrast, AGNOS is stochastic, given that it relies on training a neural network. The inherent randomness comes from the initialization of the AutoEncoder parameters (using the Glorot initialization of weights and biases [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF]). A first step consists of examining the stability of AGNOS performance across runs, controlling the reliability of the results under an affordable time complexity budget. Tables 6.4 and 6.5 display the results respectively obtained with the standard classification and the ACC scores of AGNOS-S, AGNOS-W and AGNOS-G on the benchmark datasets. Each table contains the mean and variance, over 10 runs with different initial network parameters, of the score.

Dataset

The standard classification score (Table 6.4) is measured with a 5-NearestNeighbor classifier and k = 100 selected variables. The variance of the classification score is shown to be small (less than 1% of the mean) for every dataset and declination of AGNOS, establishing its low sensitivity w.r.t. the random initialization of the AutoEncoder.

Similar conclusions can be drawn from Table 6.5, which records the ACC scores using the same setup as above.

In both cases, and even more so in the ACC case, AGNOS-W and AGNOS-G variances are higher than for AGNOS-S. Specifically, the variance is negligible for AGNOS-S on all datasets but 2 (where it is 10 -3 ). In contrast, the variance is circa 4 10 -3 on all datasets but two for AGNOS-W and AGNOS-G.

Likewise, table 6.6 contains the mean and variance of the NMI scores. The variance of the NMI score is also less than 1% of the mean in most cases. There are however some outliers for which the variance is proportionally larger (e.g. ∼ 8% of the mean for AGNOS-W on ProstateGE). This seems to occur only in the event that the mean NMI score is itself small (less than 0.10).

Given the overall stability of the results, we will in the remainder of this chapter neglect the variance due to random network parameter initialization and consider only the expected value.

Comparison with the baselines

Tables 6.7, 6.8 and 6.9 respectively contain, for the three variants of AGNOS and the four baselines, the classification, ACC and NMI scores on every benchmark dataset. In particular, AGNOS-S appears to perform better on average than the group-LASSO based AGNOS-W and AGNOS-G, with the default hyperparameter values (k = 100, d = ID,

Dataset

AgnosS

Discussion

On one hand, we set the number of clusters κ used in sup. clustering to the minimal value c corresponding to the number of sup. classes in the dataset. On the other hand, the NMI score tends to be positively correlated with κ (sec. 5.2.2.3). Consequently, we expect the NMI to be positively correlated with c.

Table 6.10 contains the correlations between the ACC and NMI scores on one hand, and c on the other hand. Expectedly, the NMI score is strongly correlated to c. The correlation between the ACC score and c is much lower than for the NMI, for all algorithms 4 . The ACC score should accordingly be prioritized over the NMI score if no prior knowledge is available to tune κ.

4. Interestingly enough, this correlation is slightly positive for AGNOS-W and negative for the baselines and AGNOS-G. This suggests that the baselines and AGNOS-G are less adequate for multi-label classification than AGNOS-W and AGNOS-S.

Dataset

AgnosS

Unsupervised evaluation results

Section 6.3.1 first assesses the stability of the FIT score of AGNOS w.r.t. the randomness of the initial conditions ; section 6.3.2 provides a comparison of the three declinations of AGNOS with the baselines, which is further discussed in section 6.3.3.

Sensitivity w.r.t. initialization of network parameters

Similarly as for sup. assessment, the variance in the results due to the Glorot initialization is minimal (less than 1% of the mean value) for all datasets and declinations of AGNOS, though AGNOS-W and AGNOS-G appear to be slightly less stable than AGNOS-S. Overall, the FIT score is shown to be hardly sensitive w.r.t. initial conditions. We will therefore neglect this source of variance in the remainder of this chapter, recording only the mean value.

Comparison with the baselines

Table 6.12 contains the respective FIT scores of the considered FS algorithms over the benchmark datasets. The proposed AGNOS-S is shown to achieve a higher FIT score than the baselines on all datasets. These results empirically demonstrate that the selection subsets induced by AGNOS-S retain more information about the features on average than the baselines.

By constrast, AGNOS-W and AGNOS-G are both outperformed by at least one baseline on every benchmark dataset (with the exception of AGNOS-W on TOX171 and Yale). Our interpretation is that this is due to a key difference between the LASSO regularization and the slack variables. One one hand, the importance of initial feature f j is in AGNOS-W and AGNOS-G obtained by taking the maximum of a d-dimensional vector. This process therefore ignores the behavior of d -1 latent features. On the other hand, the importance of f j is directly given by the single positive real value |a j |, summarizing its influence over all d latent variables simultaneously, which tentatively explains why this allows the slack variable layer to better reflect the influence of the original variables.

Discussion

Stability of results is not stability of selection While the three variants of AGNOS obtain very stable results according to both sup. and unsup. performance indicators (w.r.t. the random initialization of the Auto-Encoder parameters), the selected features themselves are not. Quite the contrary, the overlap between selection subsets resulting of two different runs of AGNOS may be as low as 5% (95% of features selected in one run are rejected in the other), for all datasets.

Given that both sup. and unsup. performance indicators are stable across runs however, suggesting that different selected subsets carry the same information, the variability of the selected features is explained from the feature redundancy within a dataset : typically, in the case of several copies of a same feature, one of these copies should be selected indifferently by AGNOS. More generally, AGNOS indiscriminately picks one representative per cluster of correlated features.

Leaving no feature behind Figure 6.1 depicts the respective cumulative distribution functions of the R 2 scores achieved by a 5-NearestNeighbors regressor using the top 100 ranked features by the baseline methods and the three AGNOS variants, on Arcene. A first observation is that every FS algorithm leads to accurate fitting (R 2 score > 0.8) of some features and poor fitting (R 2 score < 0.2) on some other features. This shows that the quality of the model predictions is very sensitive w.r.t. the target variable, which is an additional supportive argument to our claim that sup. assessment of unsup. FS (dealing with a single target) is unreliable. Most importantly, FS algorithms differ in the number of poorly fitted features. R 2 scores < 0.2 are achieved for less than 20% of features using any declination of AGNOS and more than 35% of features using MCFS. This shows that on this example dataset, AGNOS retains information about more features than MCFS. FIGURE 6.1: Cumulative distribution functions of the R 2 scores of a 5-NearestNeighbors regressor using the top 100 ranked features on Arcene. If a point has coordinates (x, y), then the goodness-of-fit of the regressor is ≤ x for y initial features (the lower, the better).

Unreliabilty of sup. assessment Table 6.13 contains the respective frequencies of ranks attained by each selection method w.r.t. the R 2 scores of each feature on the warpPIE10P dataset. A first observation is that not only is AGNOS-S more often ranked first than the baselines, it is also least often ranked last. This property also holds true for AGNOS-W and AGNOS-G, although the contrast with the baselines is less pronounced. This is once again in line with the idea of reconstructing every initial variable. Most importantly, every FS algorithm is able to achieve any rank for some original features. Therefore, the ranking of unsup. FS w.r.t. sup. assessment is extremely brittle, depending on the target variable considered. This confirms our claim (chap. 5) that sup. assessment is partial, thus unreliable. It remains to show that the FIT score itself is stable w.r.t. hyperparameters d, k and λ (sec. 6.4). 1 2 3 4 5 6 7 AgnoS-S 0.37 0.09 0.12 0.09 0.17 0.07 0.08 AgnoS-W 0.16 0.11 0.09 0.23 0.07 0.21 0.13 AgnoS-G 0.12 0.17 0.11 0.18 0.05 0.24 0.13 LAP 0.12 0.17 0.20 0.17 0.04 0.17

Sensitivity study

We will study the sensitivity of the 3 aforementioned supervised performance indicators, as well as the proposed FIT score, w.r.t. three parameters :

-The size k of the selection subset (section 6.4.1).

-The size d of the hidden layer of the AutoEncoder (section 6.4.2).

-The strength λ of the sparsity penalty term in the AutoEncoder loss function (section 6.4.3).

In order to conduct this sensitivity study, we will record the performance indicators with 2 of the 3 parameters set to their respective default values and the remaining parameter varying across a wide range 5 . The default values are the same as in section 6.1, namely : {k = 100; d = ID, λ = 1}. A first observation is that this supervised score expectedly appears to increase with k overall. Additionally, AGNOS-S outperforms all other methods for k ≤ 100. Thereafter, it is locally overtaken by NDFS and globally matched by AGNOS-G. There is therefore a clear-cut best candidate on this dataset. However, the ranking of "middle of the pack" algorithms is unstable : AGNOS-W, NDFS and SPEC regularly overtake each other. This makes it difficult to precisely gauge the efficiency of the respective FS methods with this performance indicator.

Similar results are visible on fig. 6.3, depicting the results on ProstateGE. On this dataset, the clear-cut best candidate is AGNOS-W. For the other six methods, the performances are brittle and may be highly non monotonous w.r.t. k ; note for instance the sharp decreasef in classification accuracy of NDFS when k passes from 10 to 15. This nonmonotony is blamed on the addition of features irrelevant for predicting the target, hindering the classifier.

5. This technique will allow us to measure the sensitivity of the results in a small region of the R 3 hyperparameter space, centered around the coordinates corresponding to the default values. In order to obtain a more comprehensive overview of result sensitivity across the hyperparameter landscape, one should instead turn to a fine-grained grid search. In conclusion, the supervised performance indicator is too sensitive w.r.t. k to provide a consistent ranking of methods.6

Clustering-based criteria

Figures 6.4 and 6.5 depict the sensitivity w.r.t. k of the ACC score on TOX171 (resp. of the NMI score on warp-PIE10P). Both these performance criteria appear to be highly sensitive w.r.t. the selection subset size, and they do not support any consistent (dataset-dependent) ranking of the methods. Similarly chaotic performance curves were observed on all other benchmark datasets. This sensitivity could admittedly be decreased by fine-tuning the number For all considered FS algorithms, the FIT score appears to be a non-decreasing function of k, nonwithstanding a few exceptions (e.g. the decrease between 30 and 40 selected features for the Laplacian approach). Additionally, the ranking of selection methods is shown to be robust w.r.t. k 7 , with AGNOS-S attaining the top rank for any k > 20. Concordant results were observed on the other benchmark datasets.

FIT criterion

7. The rank of each method changes at most 3 times with k, and the top ranked algorithms are mostly invariant across the considered range [5, . . . , 200]. The smoothness of the performance curves was expected as the FIT indicator is an average over thousands of elements (the original features), whereas the supervised criteria are obtained from a single target, leading to the irregular curves shown previously.

Furthermore, the gap in performance between the top and bottom ranked algorithms expectedly decreases as k increases (it would eventually be 0 for k = D). However, an additional interesting result is that FS approaches do not all benefit equally from a larger selection subset size. Typically, SPEC generally obtains low results for small values of k. This is explained as SPEC is ill-suited to handle redundant features, with a tendency to select features correlated to each other. This is visible on Yale, and all the more so on the Arcene dataset, for which the results are provided in figure 6.7. Arcene is the only benchmark dataset for which negative FIT scores are recorded. The 5-NearestNeighbor regressor trained from SPEC is worse than a constant regressor for k ≤ 30. However, its performance then abruptly improves as k increases to 50.

Given that the performance of AGNOS-S is already close to the observed global maximum for k = 5, it appears than very few variables are required to accurately predict the whole feature set on this dataset. However, the top 30 ranked features w.r.t. SPEC are likely highly redundant (even duplicates), explaining the constant FIT score for k ∈ [5, . . . , 30]. Actually relevant features occupy the next 20 spots in the SPEC ranking, which is the reason for the sudden jump in fitting accuracy. The counterperformance of AGNOS-W is interpreted as the sparsity penalty being insufficiently strong to handle the known redundancy of the features. Ongoing experiments will clarify this phenomenon. By contrast, this issue of inefficient selection for small subset sizes has not been encountered by AGNOS-S. The brittleness of the resulting ranking confirms that these two performance criteria are ill-advised for comparing FS algorithms. The fact that the performance of AGNOS-W decreases for d > ID is congruent with the reasoning exposed in chapter 4 ; if the size of the hidden layer is larger than the intrinsic dimension, then the set of latent features likely contains redundancy. In turn, original features that are important to build only superfluous latent features may be wrongfully selected, negatively impacting the results.

Clustering-based criteria

FIT criterion

By construction, all latent features matter for d = ID, meaning the above issue is averted and only the most relevant initial features are selected. However, this assumption does not seem to hold in practice, as highlighted by the fact that the performance of AGNOS-G is shown to increase for d > ID. In order to address this shortcoming, a potential direction for further work is to take into account the varying importance of the latent features in the selection criterion (chap. 7).

The low sensitivity of performance w.r.t. d means that studying the intrinsic dimension of the dataset as preprocessing is of lesser importance for AGNOS-S than for AGNOS-G and AGNOS-W. This is consequently another argument in favor of this declination of AGNOS. We interpret this robustness property in the same manner as in section 6. The performance of AGNOS appear to be sensitive w.r.t. λ, with all three variants possibly being overtaken by some of the baselines. However, the suitable range for λ differs for each declination of AGNOS. For both AGNOS-S and AGNOS-W, the default value λ = 1 leads to a FIT score close to the recorded maximum. However, this default value appears to be too large for AGNOS-G, requiring λ = 10 -3 to reach its best performance instead. This is related to the phenomenon of fig. 6.7, which is under study.

Main drawback of AGNOS : the computational cost

Table 6.14 contains the empirical runtimes of the baselines and the three variants of AGNOS on each dataset. AGNOS-S is shown to be between 25% and 100% slower than NDFS, and several orders of magnitude slower than Laplacian score, SPEC and NDFS. Training an Auto-Encoder with a number of parameters of the order of D × d thus appears more expensive than spectral clustering-based optimization 8 . AGNOS-W and AGNOS-G are even slower, being on average 50% slower than AGNOS-S. This is explained by the fact that the respective loss functions of AGNOS-W and 8. Arguably, the use of GPU for neural computation is significally more advanced than for spectral clustering, although some announcements from Nvidia (nvi, 2017) suggest that appropriate libraries for spectral clustering with CUDA would be available soon. AGNOS-G involve D × d parameters (resp. weights and gradients) compared to the D slack variables computed in AGNOS-S. The computational effort thus constitutes the main limitation of the proposed algorithmic contribution. Consequently, a perspective for future research is to lower the complexity of the approach, either with early stopping or recursive feature elimination (chap. 7).

Partial Conclusion

This experimental study has shown that AGNOS is able to consistently select a subset sufficient to recover the whole original feature set, and outperform the considered baseline methods w.r.t. both sup. and unsup. performance criteria. A remaining question is which one of the three AGNOS declinations is best suited to the dataset at hand, particularly so among AGNOS-S and AGNOS-G. As said, the comparative lesser performance of AGNOS-W is under study.

The second contribution of the chapter is to show the merits of the proposed FIT criterion, in terms of stability w.r.t. the target feature by construction and also w.r.t. the hyper-parameters of FS such as the selection subset size. This robustness property, highlights the reliability of the FIT evaluation scheme for comparing unsupervised FS algorithms.

Finally, the unsup. part of this empirical study (sec. 6.3) has also underlined the partiality issue inherent to sup. validation of unsup. FS, as claimed in chapter 5, the ranking of unsup. FS algorithms w.r.t. any sup. scoring function arbitrarily depending on the considered learning goal.

Chapitre 7

Perspectives and conclusion

Two different aspects of unsupervised feature selection have been explored in this thesis. On one hand, a novel unsupervised FS algorithm has been proposed. On the other hand, we have devised a new performance evaluation framework for comparing unsupervised FS techniques.

This chapter first recalls the main results and lessons learned for the unsupervised feature selection problem (section 7.1), then discusses the research perspectives opened by this work in section 7.2.

Summary of contributions

Unsupervised Dimensionality Reduction

As shown (chap. 2), the curse of dimensionality [START_REF] Pestov | On the geometry of similarity search : dimensionality curse and concentration of measure[END_REF] effectively renders the Euclidean distance ineffective to assess similarity between high-dimensional datapoints. Moreover, the efficiency of state-of-the-art unsup. FS approaches (chap. 3) is noticeably hindered, admittedly to a varying extent, when faced with features carrying redundant information. Thirdly, features are typically retained in view of a single particular learning goal (chap. 5), even though all original variables are potential learning goals in the unsup. context [START_REF] Lecun | The next frontier in AI : Unsupervised learning[END_REF].

Taking note from the above three remarks, the proposed algorithmic contribution hinges on Auto-Encoding neural networks to simultaneously suppress the need for a high-dimensional similarity metric and perform agnostic feature selection. In doing so, Agnostic Feature Selection (AGNOS, chap. 4) essentially bridges the gap between unsupervised feature construction and selection. Three variants of this algorithmic contribution (named AGNOS-W, AGNOS-G and AGNOS-S) have been proposed, each enhancing the AutoEncoder with a different form of structural regularization enforcing sparse selection, thereby efficiently addressing the feature redundancy issue.

Assessment of unsupervised Feature Selection

As seen (chap. 5), we claim that typical sup. performance indicators for unsup. FS lack in reliability and stability. In order to provide a stable and reliable performance indicator, we propose the methodological contribution of this thesis, the unsup. FIT scoring criterion (chap. 5).

Empirical evidence

A systematic study has been conducted to back the claims of the thesis. On the one hand, it is shown that the proposed AGNOS algorithm outperforms state-of-the-art unsup. FS methods [START_REF] He | Laplacian score for feature selection[END_REF][START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF][START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF][START_REF] Li | Unsupervised feature selection using non-negative spectral analysis[END_REF] w.r.t. both typical sup. assessment metrics and the novel FIT score.

Chapitre 7. Perspectives and conclusion

The main two lessons learned from the empirical study concern both unsupervised FS and the validation methodology :

-On the algorithmic side, AGNOS favourably compares to the most impactful unsup. FS techniques on representative datasets illustrating different application domains (medical, text and face image data) and an artificial dataset known to hinder independent scoring methods.

-On the methodological side, we establish that sup. performance indicators generally used to assess unsup. FS provide brittle results. The exploitation of the intrinsic dimensionality of a dataset can also be considered a worthy ingredient for unsup. FS in the data compression perspective.

These findings were the subject of an accepted paper at the 2019 edition of the European Conference on Machine Learning (ECML) 1 .

Strengths and weaknesses

Pros The main benefits of our contribution are :

-Escaping the curse of dimensionality by avoiding usage of a high-dimensional pairwise similarity metric.

-Capturing much more information than spectral clustering-based methods : the objective is to recover D original features rather than a single pseudo-label variable. As a result, the selected subset is relevant w.r.t. any learning goal.

-Efficiently handling redundant feature sets, thanks to the sparsity-enforcing term in the Auto-Encoder loss.

Cons Nevertheless, AGNOS currently suffers from a sizeable drawback : its empirical time complexity is shown to be larger by at least a factor two, and often an order of magnitude, than state-of-the-art unsup. FS methods (chap. 6).

Lowering the computational cost of the approach is our first perspective for future research (sec. 7.2).

Towards more robust and computationally efficient agnostic feature selection

This work opens three perspectives for further research.

Computational cost

A short-term research perspective is to reduce the computational cost of AGNOS. A first option is to transform AG-NOS from a filter-based approach to an embedded online selection method, taking inspiration from [START_REF] Guyon | Gene selection for cancer classification using support vector machines[END_REF]. One possible way of iteratively eliminating the original features least contributing towards learning the constructed features in the latent AutoEncoder data representation during network training, is to set the associated slack variables to 0 in AGNOS-S. Given this modification, the dimensionality of the input continuously decreases, hereby greatly reducing computational cost both in terms of time and space complexity, and allowing AGNOS to better scale to large real-life datasets. Such an iterative process can support an automatic stopping criterion in the approach, s.t. the number of features to ultimately retain is determined on the fly, as is already implemented in supervised neural network-based approaches such as Drop-Out-One [START_REF] Ye | Variable selection via penalized neural network : a drop-out-one loss approach[END_REF].

A second option is to use an early stopping of the Auto-Encoder, e.g. when the feature ranks as computed from the slack variables and/or the weights or gradients have not changed for some consecutive epochs : indeed, a perfect reconstruction accuracy is a means rather than an end for the AE learning.

Probabilistic AGNOS

A longer-term perspective consists of replacing the deterministic AutoEncoder relied upon by AGNOS with a Variational AutoEncoder (Kingma and Welling, 2013) (appendix .1). Given this modified neural architecture, original features would be selected w.r.t. their usefulness for generating realistic new samples, rather than reconstructing the existing datapoints.

The goal of this extension is to provide a more robust feature selection approach in the case where the application domain contains very few samples comparatively to the number of features, e.g. in DNA-based bioinformatics research.

Better exploiting the latent features

As said, AGNOS relies on the implicit assumption that all constructed features are equally important for reconstructing the original data (chap. 4). This assumption is unlikely to hold in practice, as underlined by the lower empirical performance (chap. 6) of AGNOS-W and AGNOS-G (where feature importance is derived from one constructed feature) comparatively to AGNOS-S (where feature importance simultaneously involves all constructed features).

In the short term, the extension of AGNOS-G to consider the gradients from f i w.r.t. f i (∂ f i ) is a way to seamlessly handle the importance of the latent variables. In a medium term, the importance of the latent variables φ j w.r.t. f i can be used to weight the importance of the f i s.

Causal discovery

Lastly, a long-term perspective is to explore the link between the proposed unsupervised feature selection paradigm and the neighboring field of causal inference [START_REF] Pearl | Causal inference in statistics : An overview[END_REF]. Causal feature selection [START_REF] Guyon | Causal feature selection[END_REF][START_REF] Peters | Elements of causal inference : foundations and learning algorithms[END_REF] has insofar and to the best of our knowledge only been considered in the supervised context. However, the central motivation behind AGNOS of selecting features sufficient to recover the whole feature set is strongly reminiscent of finding a minimal functional causal model [START_REF] Goudet | Learning functional causal models with generative neural networks[END_REF] explaining all variables. Bridging the gap between causal discovery and unsupervised feature selection for the purpose of interpretability is therefore an especially interesting prospect in view of Fair, Transparent and Accountable learning (chap. 1).

.1 Appendix A : Variational Auto-Encoders

Variational AutoEncoders (VAE) [START_REF] Kingma | Auto-encoding variational bayes[END_REF] rapidly gained popularity over the past five years as a data augmentation method [START_REF] Pu | Variational autoencoder for deep learning of images, labels and captions[END_REF]. The mathematical basis of VAEs is actually quite remote from classical AutoEncoders. The name of the approach is therefore slightly ambiguous, as the resulting network merely resembles an AutoEncoder.

The core idea behind VAEs is to interpret the d constructed features as being the parameters of d probability distribution functions. The most common choice corresponds to a multivariate Gaussian distribution, so that each constructed feature in Z * d consists of a tuple (µ, σ) reflecting the mean and standard deviation of a scalar Gaussian. During training, latent variables are sampled from their respective distributions, and the decoder part of the neural network is tasked with recreating the original data X2 from the stochastic samples. The success of this reconstruction hinges on the crucial observation that a set of d Gaussian random variables can be mapped to an arbitrarily close approximation of any d-dimensional distribution (including that of X, provided the manifold assumption from chapter 2 holds), provided a sufficiently complex function [START_REF] Devroye | Sample-based non-uniform random variate generation[END_REF]). An illustration of this result is provided in figure 1. Provided with this setup, one could sample from the model without any input. However, obtaining a satisfactory reconstruction of X this way is unaffordable in terms of time complexity, as highlighted by figure 2 and the following discussion.

One would expect the model generating the digit in panel (b) to be deemed mediocre, given the apparent dissimilarity with the original MNIST datapoint of panel (a). On the other hand, the reconstruction of panel (c) (identical to (a) but shifted down and to the right by one pixel) is perceived to be better. Unfortunately, (b) is much closer to (a) than (c) is, w.r.t. the MSE loss. Therefore, one would need to obtain a model significantly better than (c) in order to discard results such as (b). This is consequently likely to require an unreasonable amount of samples. In order to accelerate the sampling procedure, an encoder φ mapping X to the constructed features (µ(X), σ(X)) is added to the pipeline, s.t. the distribution parameters are learned through backpropagation of the reconstruction error3 (fig. 3).

FIGURE 3: Illustration of the final VAE pipeline

The sole purpose of the encoder part is thus to ensure that training is affordable in terms of time complexity. After training is complete, φ is discarded and new samples can be generated using only the constructed features and ψ, therefore achieving data augmentation. This constitutes a significant methological difference with classical AutoEncoders :

  Formally, given target reduced dimensionality d ∈ N * s.t. d << D, let H d denote the set of all sets containing d features computed from F , and C : R D × R d → R a cost function. A dimensionality reduction problem can then be formulated as finding Z * d s.t. :

  FIGURE 2.2: Tentative taxonomy of intrinsic dimension estimation techniques

FIGURE 2 . 3 :

 23 FIGURE 2.3: Distribution of Euclidean distances between 10 4 randomly chosen pairs of points sampled from the unit hypercube I D , for different values of dimension D. Top-left panel corresponds to D = 3, top-right to D = 10, bottom-left to D = 100 and bottom-right to D = 1000. Image taken from Pestov (2007).

  FIGURE 2.4: A snowflake presents self-similarity properties characteristic of fractal patterns.Image taken from Wikipedia.

  FIGURE 2.6: The measured length of the coastline of Great Britain increases as the length of the measuring stick decreases. Image taken from Wikipedia.

  FIGURE 2.8: Illustration of the Hausdorff dimension concept applied to the Great Britain coastline example. Image taken from Wikipedia.

FIGURE 2 .

 2 FIGURE 2.10: Two-dimensional example of local ID estimation via the 2NN technique.

FIGURE 2 .

 2 FIGURE 2.11: Example of covariance matrices spectra resulting of PCA for different dimensions d 1 and d 2

FIGURE 3

 3 FIGURE 3.2: Far-away points are wrongly assessed as close together in the PCA projection by the Euclidean distance. From Roweis and Saul (2000).

FIGURE 3 . 3 :

 33 FIGURE 3.3: The geodesic distance accurately depicts pairwise similarities, and is used by Isomap to unfold the Swiss roll. From Tenenbaum et al. (2000).

F

  An illustration of the LLE DR process is provided in figure 3.5.

  FIGURE 3.4: Adding Gaussian noise of small amplitude leads to a badly unfolded Swiss Roll.From[START_REF] Balasubramanian | The isomap algorithm and topological stability[END_REF].

FIGURE 3 . 5 :

 35 FIGURE 3.5: Illustration of the three sequential steps involved in LLE.

FIGURE 3

 3 FIGURE 3.6: An AutoEncoder performs unsupervised FC by compressing the input into d latent variables.

  FIGURE 3.8: Illustration of the denoising AutoEncoder process on MNIST.

  FIGURE 3.10: The structure of a Siamese Convolutional Neural Network. From Liu et al. (2018).

FIGURE 3 .

 3 FIGURE 3.11: The spatial arrangement of the voxels is an important source of information neglected by traditional FS.

FIGURE 3 .

 3 FIGURE 3.13: Example of features forming groups in a tree-like structure. From Li et al. (2018a).

  Independent scoring methods are by construction plagued by two opposite issues : false negatives (features falsely considered irrelevant) and false positives (falsely relevant features).

FIGURE 3 .

 3 FIGURE 3.16: A binary classification task with three features. ∀(i, j) ∈ [1, 3] 2 , panel (i, j) depicts the separation of the two classes (resp. in black and white) achieved by selection subset {f i , f j }. The diagonal panels therefore resp. correspond to the singleton selection subsets {f 1 }, {f 2 }, {f 3 }. Taken from[START_REF] Guyon | An introduction to variable and feature selection[END_REF].

FIGURE 3 .

 3 FIGURE 3.17: Schematic of filters, wrappers and embedded methods.

FIGURE 3 .

 3 FIGURE 3.18: Illustration of a linear SVM on a binary classification task. Decision boundary H 3 maximizes the margin between the two classes (in black and white). Feature f 1 should be prioritized over f 2 for selection. From Wikipedia.

FIGURE 3 .

 3 FIGURE 3.19: The Deep Feature Selection architecture. From Li et al. (2016).

  FIGURE 3.20: Outline of different penalty functions : L 2 (left), LASSO (center), group-LASSO (right).

FIGURE 4

 4 FIGURE 4.2: AGNOS operates under minimal hypotheses

FIGURE 4

 4 FIGURE 4.3: A torus corresponds to a smooth manifold, but contains a hole. From Wikipedia.

FIGURE 4 . 4 :

 44 FIGURE 4.4: Like for the torus, Isomap fails to embed a 3D cylinder in a 2D space while preserving its similarity graph (upper panels). However, DR is succesful if the cylinder has been preemptively "cut" (lower panels). From van der Maaten et al.(2008)

  11) This leads to the proposed algorithm : Algorithm 6 AGNOS-G Input : Feature set F = {f 1 , ..., f D } Parameter : λ Output : Ranking of features in F Normalize each feature to zero mean and unit variance. Estimate intrinsic dimension ID of F . Initialize neural network with d = ID neurons in the hidden layer. decreasing scores with Score G (f i ) = max j∈[1,...,d] n k=1 | ∂φ j ∂f i (x k )|.

FIGURE 4 . 5 :

 45 FIGURE 4.5: Structure of the neural network used in AGNOS-S

  Feature set F = {f 1 , ..., f D } Parameter : λ Output : Ranking of features in F Normalize each feature to zero mean and unit variance. Estimate intrinsic dimension ID of F . Initialize neural network with (a 1 , ..., a D ) = 1 D and d = ID neurons in the hidden layer. Rank features by decreasing scores with Score S (f i ) = |a i |.

FIGURE 5 . 1 :

 51 FIGURE 5.1: Despite the left clustering clearly being more similar to the central configuration than the right clustering, the NMI score is higher for the latter. From Gates et al. (2018)

FIGURE 5 . 3 :

 53 FIGURE 5.3: Clustering of medical data (left) based on the same unsup. selection subset leads to a perfect performance w.r.t. a certain learning goal (middle) and poor performance w.r.t. another goal (right).

  (skfeature for short)[START_REF] Li | Feature selection : A data perspective[END_REF]; skf (

Figure 6

 6 Figure6.2 depicts the classification accuracy achieved by the 5-NearestNeighbor classifier trained only from the selection subset S k as a function of k, on the Yale dataset. A first observation is that this supervised score expectedly appears to increase with k overall. Additionally, AGNOS-S outperforms all other methods for k ≤ 100. Thereafter, it is locally overtaken by NDFS and globally matched by AGNOS-G. There is therefore a clear-cut best candidate on this dataset. However, the ranking of "middle of the pack" algorithms is unstable : AGNOS-W, NDFS and SPEC regularly overtake each other. This makes it difficult to precisely gauge the efficiency of the respective FS methods with this performance indicator.Similar results are visible on fig.6.3, depicting the results on ProstateGE. On this dataset, the clear-cut best candidate is AGNOS-W. For the other six methods, the performances are brittle and may be highly non monotonous w.r.t. k ; note for instance the sharp decreasef in classification accuracy of NDFS when k passes from 10 to 15. This nonmonotony is blamed on the addition of features irrelevant for predicting the target, hindering the classifier.

  FIGURE 6.2: Prediction score of 5-NearestNeighbor classifier w.r.t. selection subset size k, on Yale

  FIGURE 6.4: ACC score w.r.t. selection subset size k, on TOX171

Figure 6 .

 6 Figure 6.6 depicts the FIT score attained by the 3 declinations of AGNOS and the baselines as a function of the selection subset size k, on the Yale dataset.For all considered FS algorithms, the FIT score appears to be a non-decreasing function of k, nonwithstanding a few exceptions (e.g. the decrease between 30 and 40 selected features for the Laplacian approach). Additionally, the ranking of selection methods is shown to be robust w.r.t. k 7 , with AGNOS-S attaining the top rank for any k > 20. Concordant results were observed on the other benchmark datasets.

FIGURE 6

 6 FIGURE 6.6: FIT score w.r.t. selection subset size k, on Yale

FIGURE 6

 6 FIGURE 6.7: FIT score w.r.t. selection subset size k, on Arcene

  FIGURE 6.8: Prediction score of 5-NearestNeighbor classifier w.r.t. hidden layer size d, on Yale. The vertical black dotted line corresponds to the estimated intrinsic dimension. The colored horizontal dotted line correspond to the respective prediction scores of the baselines (independent of d)

FIGURE 6

 6 FIGURE 6.9: ACC score (left panel) and NMI score (right panel) w.r.t. hidden layer size d, on Yale. The vertical black dotted line corresponds to the estimated intrinsic dimension. The colored horizontal dotted line correspond to the respective FIT scores of the baselines (independent of d).

Figure 6 .

 6 Figure6.9 records the ACC and NMI scores as function of d, on Yale. The sensitivity of the results w.r.t. d is higher than for the classification criterion, with AGNOS-S generally being the best candidate and AGNOS-G a close second. However, all three declinations of AGNOS can perform worse than at least one baseline for some values of d. The brittleness of the resulting ranking confirms that these two performance criteria are ill-advised for comparing FS algorithms.

Figure 6 .

 6 Figure 6.10 depicts the FIT score attained by the 3 declinations of AGNOS as a function of the size d of the hidden layer of the AutoEncoder, on the Yale dataset. The respective performances of both AGNOS-W and AGNOS-G are s.t. the rank of both variants among the considered FS methods fluctuates with d. By contrast, the performance of AGNOS-S appears to be stable w.r.t. d, and remains higher than all baselines across the entire range d ∈ [5, . . . , 100]. Concordant results were observed on the other benchmark datasets.The fact that the performance of AGNOS-W decreases for d > ID is congruent with the reasoning exposed in chapter 4 ; if the size of the hidden layer is larger than the intrinsic dimension, then the set of latent features likely contains redundancy. In turn, original features that are important to build only superfluous latent features may be wrongfully selected, negatively impacting the results.By construction, all latent features matter for d = ID, meaning the above issue is averted and only the most relevant initial features are selected. However, this assumption does not seem to hold in practice, as highlighted by the fact that the performance of AGNOS-G is shown to increase for d > ID. In order to address this shortcoming, a potential direction for further work is to take into account the varying importance of the latent features in the selection criterion (chap. 7).The low sensitivity of performance w.r.t. d means that studying the intrinsic dimension of the dataset as preprocessing is of lesser importance for AGNOS-S than for AGNOS-G and AGNOS-W. This is consequently another argument

  FIGURE 6.10: FIT score w.r.t. hidden layer size d, on Yale. The vertical black dotted line corresponds to the estimated intrinsic dimension. The colored horizontal dotted line correspond to the respective FIT scores of the baselines (independent of d).

  Figure 6.11 depicts the FIT scores of the three AGNOS variants as function of λ (represented in log scale) on Isolet .The performance of AGNOS appear to be sensitive w.r.t. λ, with all three variants possibly being overtaken by some of the baselines. However, the suitable range for λ differs for each declination of AGNOS. For both AGNOS-S and AGNOS-W, the default value λ = 1 leads to a FIT score close to the recorded maximum. However, this default value appears to be too large for AGNOS-G, requiring λ = 10 -3 to reach its best performance instead. This is related to the phenomenon of fig.6.7, which is under study.

FIGURE 6 .

 6 FIGURE 6.11: FIT score w.r.t. penalization strength λ (represented in log scale), on Isolet. The vertical black dotted line corresponds to the default value of λ = 1. The colored horizontal dotted line correspond to the respective FIT scores of the baselines (independent of λ). Similar curves are obtained for the other benchmark datasets, as well as for sup. assessment.

FIGURE 1 :

 1 FIGURE 1: The 2D random variable z on the left panel can be mapped to a ring-shape distribution X through the function ψ(z) = z/10 + z/||z||

FIGURE 2 :

 2 FIGURE 2: The reconstructed digit of panel (c) is perceptually much closer to the original MNIST digit of panel (a) than the sample in panel (b). However, the MSE loss provides the reverse conclusion, that (b) is the far better approximation

  Ranking of features in FNormalize each feature to zero mean and unit variance.Estimate intrinsic dimension ID of F . Initialize neural network with d = ID neurons in the hidden layer.

	Algorithm 5 AGNOS-W
	Input	: Feature set F = {f 1 , ..., f D }
	Parameter	λ
	: Output : Repeat
	Backpropagate L W

TABLE 6

 6

	.1: Summary of benchmark datasets.

Table 6 .

 6 2 contains the estimated IDs for each dataset using the method from[START_REF] Facco | Estimating the intrinsic dimension of datasets by a minimal neighborhood information[END_REF] 2 .

	Dataset	Initial dimension ID of unnormalized data ID of normalized data
	Arcene	10000	18.01	39.89
	Isolet	617	8.29	8.53
	ORL	1024	5.60	5.50
	pixraw10P	10000	3.74	3.94
	ProstateGE	5966	22.27	22.32
	TOX171	5748	6.35	14.75
	warpPIE10P 2400	2.63	2.62
	Yale	1024	9.27	9.62
	TABLE 6.2: Intrinsic dimensions of each dataset, using all samples.

TABLE 6 .

 6 3: Mean and variance (in parenthesis) of intrinsic dimension across 20 runs for every dataset, using 80% of samples drawn at random for each run.

TABLE 6 .

 6 4: Mean and variance of standard classification score of 5-NearestNeighbor classifier on the benchmark datasets for the three declinations of AGNOS, over 10 runs with different Glorot initializations of network parameters. (-) indicates a variance lower than 10 -3 .

  Supervised classification scores of 5-NearestNeighbor classifier for the three declinations of AGNOS and the baselines on the benchmark datasets. Statistically significantly better (according to a t-test with a p-value of 0.05) results in boldface.

			AgnosW AgnosG Laplacian MCFS NDFS SPEC
	Arcene	0.81	0.77	0.75	0.67	0.52	0.69	0.70
	Isolet	0.83	0.84	0.65	0.68	0.65	0.82	0.74
	ORL	0.93	0.93	0.89	0.92	0.90	0.91	0.87
	pixraw10P	0.97	0.93	0.99	0.99	0.95	0.98	0.85
	ProstateGE	0.76	0.83	0.75	0.75	0.74	0.71	0.70
	TOX171	0.66	0.86	0.63	0.84	0.74	0.67	0.78
	warpPIE10P 0.99	0.98	0.98	0.99	0.96	0.98	0.98
	Yale	0.63	0.60	0.61	0.56	0.53	0.63	0.58
	TABLE 6.7: Dataset	AgnosS AgnosW AgnosG Laplacian MCFS NDFS SPEC
	Arcene	0.67	0.62	0.63	0.66	0.56	0.51	0.66
	Isolet	0.54	0.58	0.41	0.48	0.41	0.57	0.57
	ORL	0.57	0.55	0.53	0.55	0.56	0.54	0.47
	pixraw10P	0.81	0.64	0.78	0.80	0.75	0.78	0.48
	ProstateGE	0.61	0.59	0.57	0.58	0.59	0.57	0.59
	TOX171	0.40	0.29	0.36	0.45	0.48	0.46	0.47
	warpPIE10P 0.27	0.36	0.42	0.29	0.36	0.29	0.33
	Yale	0.51	0.38	0.53	0.44	0.40	0.44	0.40
	TABLE 6.8: Supervised ACC scores for the three declinations of AGNOS and the baselines on
	the benchmark datasets. Statistically significantly better (according to a t-test with a p-value of
				0.05) results in boldface.

TABLE 6 .

 6 11: Mean and variance of FIT score on the benchmark datasets for the three declinations of AGNOS, over 10 runs with different Glorot initializations of network parameters.(-) indicates a variance lower than 10 -4 .

		Arcene Isolet ORL	pixraw10P ProstateGE TOX171 warpPIE10P Yale
	AgnoS-S 0.610	0.763 0.800 0.855	0.662	0.581	0.910	0.703
	AgnoS-W 0.460	0.762 0.795 0.782	0.620	0.580	0.897	0.696
	AgnoS-G 0.560	0.701 0.780 0.832	0.606	0.528	0.901	0.671
	Laplacian 0.576	0.680 0.789 0.840	0.655	0.563	0.903	0.601
	MCFS	0.275	0.720 0.763 0.785	0.634	0.549	0.870	0.652
	NDFS	0.490	0.747 0.796 0.835	0.614	0.520	0.904	0.677
	SPEC	0.548	0.733 0.769 0.761	0.646	0.559	0.895	0.659

TABLE 6 .

 6

12: FIT score of 5-NearestNeighbors regressor using the top 100 ranked features. Statistically significantly (according to a t-test with a p-value of 0.05) better results in boldface.

TABLE 6 .

 6 13: Frequency of ranks of selection methods w.r.t. R 2 scores of each feature on warp-PIE10P with a 5-NearestNeighbors regressor using the top 100 ranked features. For instance, AGNOS-S obtains the lowest reconstruction error among the 7 candidate methods for 37% of the original features.

	0.13

TABLE 6 .

 6 14: Empirical runtimes on a single Nvidia Geforce GTX 1060 GPU, in seconds.

		arcene Isolet ORL pixraw10P ProstateGE TOX171 warpPie10P Yale
	AGNOS-S 265	25	29	242	145	143	31	14
	AGNOS-W 422	31	40	389	191	180	47	18
	AGNOS-G 428	32	42	394	195	184	48	18
	Laplacian	<1	<1	<1	<1	<1	<1	<1	<1
	SPEC	3	9	<1	2	1	2	1	<1
	MCFS	<1	2	<1	<1	<1	<1	<1	<1
	NDFS	130	16	17	193	80	76	18	7

Agnostic Feature Selection, G. Doquet and M. Sebag, ECML PKDD 2019

This problem is also frequently referred to as Feature Extraction (FE). However, we find this alternate name to be a potential source of ambiguity, due to the similarity in meaning with Feature Selection. We will therefore prefer using the term FC over FE in this work. Note that FC is also infrequently used in the litterature to describe the process of adding extra features to F , thus pertaining to the data augmentation setting, which is outside the scope of this thesis.

Consider for instance medical data which purpose is to predict lung cancer in patients. The selection subset {age, smoker} is likely more understandable to a physician than the artificial features {tanh(0.87age + 0.13gender), σ(0.95smoker + 0.05name)}.

There may also exist multiple learning goals simultaneously[START_REF] Zhang | Ml-knn : A lazy learning approach to multi-label learning[END_REF]. This variant is called multi-label learning[START_REF] Zhang | A review on multi-label learning algorithms[END_REF].

Chapitre 2. Dimensionality Reduction : formal background

The link between d and d * is less immediate in the case of FS : there is no guarantee that the latent manifold can be retrieved from exactly d * original features. Nevertheless, the manifold assumption provides a lower bound for the selection subset size, that is d * ≤ d. Estimating d * is thus still of interest for the purpose of FS.

The concept of intrinsic dimensionality is also relied upon in signal processing[START_REF] Trunk | Stastical estimation of the intrinsic dimensionality of a noisy signal collection[END_REF], where it refers to the minimum number of variables needed to generate a near-perfect approximation of the original signal.

It directly follows from equation (2.3) that the estimated ID of a dataset composed of a single sample is infinite. Although it has limited practical implications, this mathematical oddity has interestingly enough been shown[START_REF] Pestov | Intrinsic dimension of a dataset : what properties does one expect ? International Joint Conference on Neural Networks[END_REF] to be a required property of any theoretically well-grounded ID estimator.

Interestingly enough, the Eckart-Young theorem[START_REF] Eckart | The approximation of one matrix by another of lower rank[END_REF] guarantees that Z d is the best approximation (in the sense of the Frobenius norm) of X by a matrix of rank d or less.

More precisely, it suffices that ψ • φ = Id, which is achieved by learning any invertible φ : R D → R D and ψ = φ -1 . This is unlikely to produce a useful representation in the encoder. Furthermore, this can still occur even if non-linear activation functions are used (e.g. φ can stay in the linear regime of a sigmoid with small enough neuronal weights).

More specifically, even though these relationships may exist, we assume no prior information or expert knowledge regarding these structures

One could also consider the previous example of social network sentiment analysis, where features are extracted from different data formats such as text, image or video

Admittedly, this formulation slightly diverges from the formal definition of margin, which was here simplified for the sake of brevity without loss of generality in the following discussion.

This method consists in agumenting F artificial Gaussian noise features, and selecting only features which associated weights are significantly larger than for the noisy features, at the end of training.

Slightly abusing the notation, Ξ(x i ) designates the vector of cluster affilations of the i-th sample.

Additional references include for instance TRACK[START_REF] Wang | Unsupervised feature selection via unified trace ratio formulation and k-means clustering (track)[END_REF] and Similarity Preserving Feature Selection (SPFS)[START_REF] Zhao | On similarity preserving feature selection[END_REF].

Note that even in the linear case, PCA and SVD require a specific configuration of the covariance matrix, s.t. the angles between its eigenvectors be sufficiently large[START_REF] Martinez | Where are linear feature extraction methods applicable[END_REF].

This is a direct consequence of the network being prevented from spreadng the information contained by an important original feature into multiple components of the d-dimensional space.

Arguably, the fewer original features are involved for learning each constructed feature, the easier it is to measure their respective influence.

Arguably, P I3 is also non-smooth : the score of an algorithm abruptly changes across the boundary k = 10. Smoothness is also a desired property of performance indicators, although with a lower priority than stability.

Preliminary experiments have shown results to be more stable overall with p = 5 rather than p = 1.

As said (chap. 2), the ID is not necessarily an integer. However, the number of neurons in the hidden layer of the Auto-Encoder used in AGNOS must itself be an integer. Therefore, we opt to round up the estimated intrinsic dimension : ID ← ID .

The 2-NN ID estimator being a deterministic algorithm, we cannot simply perform multiple runs on the full dataset and examine the variance of the results.

Note that, even if the resulting ranking were stable w.r.t. k, the partiality problem exposed in chapter 5 would remain.

More precisely, the decoder is tasked with generating datapoints that look like those of X, which is why the approach is used to perform Data Augmentation. The decoder designation is therefore only used to draw the parallel between VAEs and traditional AEs ; a less ambiguous name for this network component would be generator.

Arguably, an alternate solution would be to design a similarity metric better suited to depict likeness of images than the MSE. However, not only are such metrics challenging to define in domains such as computer vision, but also hardly interpretable without label information indicating which images are similar, as is the case in unsupervised FC

the encoder is merely a convenient tool rather than the end goal of learning. Moreover, the constructed features do not necessarily contain any information related to X, which is why we consider VAEs to be remote from other FC methods.

Chapitre 4

Agnostic Feature Selection

This chapter presents our algorithmic contribution in the domain of unsup. FS, AGNOS, building upon the lessons learned from the state of the art (chapter 3). The proposed AGNOS presents an original learning criterion at the crossroad of FC and FS.

This novel combination of dimensionality reduction techniques is first discussed at a general level (sec. 4.1), introducing the main issues that need to be addressed (sec. 4.2). Section 4.3 thereafter discusses the feature scoring criteria. Lastly, three declinations of AGNOS, called AGNOS-W, AGNOS-G and AGNOS-S, are proposed in section 4.4.

AGNOS full picture

The proposed unsup. FS algorithm AGNOS combines two underlying motivations : data compression efficiency and generality, respectively defined and discussed in sections 4.1.1 and 4.1.2.

Efficient data compression (fig. 4.1)

State-of-the-art unsup. feature selection methods ( [START_REF] He | Laplacian score for feature selection[END_REF][START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF][START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF][START_REF] Li | Unsupervised feature selection using non-negative spectral analysis[END_REF][START_REF] Nie | Unsupervised feature selection with structured graph optimization[END_REF], chapter 3) perform selection with the ultimate goal of predicting a specific target f * not in the original feature set F , as in sup. learning (chap. 5). However, as underlined in chapter 1, unsup. learning constitutes the bulk of machine learning, and any element of the feature set can in principle define a learning goal [START_REF] Lecun | The next frontier in AI : Unsupervised learning[END_REF]. Following this idea, AGNOS aims to select a feature subset supporting the prediction of every initial feature and thus tackles the unsup. FS problem from the angle of data compression.

Performance indicators for assessing unsupervised Feature Selection

This chapter is concerned with the validation procedure of unsup. FS. The theoretical properties of an ideal performance indicator are first discussed in section 5.1. Section 5.2 thereafter introduces the three sup. criteria typically used in unsup. FS. Lastly, section 5.3 presents our methodological contribution, the unsup. FIT criterion.

How many features to select ?

The results of both sup. and unsup. assessment protocols depend on hyperparameter k governing the size of the selection subset S k . As discussed in chapter 2, k is in the unsup. FS context manually set by the user rather than automatically tuned like in sup. approaches [START_REF] Ye | Variable selection via penalized neural network : a drop-out-one loss approach[END_REF]. In the remainder of this chapter, k is considered a fixed parameter.

Empirical validation of state-of-the-art unsup. FS algorithms [START_REF] He | Laplacian score for feature selection[END_REF][START_REF] Zhao | Spectral feature selection for supervised and unsupervised learning[END_REF][START_REF] Cai | Unsupervised feature selection for multi-cluster data[END_REF][START_REF] Li | Unsupervised feature selection using non-negative spectral analysis[END_REF][START_REF] Nie | Unsupervised feature selection with structured graph optimization[END_REF] typically considers multiple values for k, in order to monitor the efficiency of selection as a function of the reduced dimensionality. Accordingly, we will follow this protocol in our own empirical study (chap. 6).

Motivation

In sup. FS, the relevance of a performance indicator P I is unambiguous : P I is a good criterion iff it rewards selecting the best features for predicting the learning goal.

By contrast, the quality of P I is harder to define in the unsup. context, given the absence of ground truth. An important question then arises : "What makes a good performance indicator for unsup. FS ?"

We argue that a suitable P I should strive for the following six qualities, defined thereafter :

- In order to support the selection of a feature subset sufficient to recover the entire dataset, one could adapt clustering-based criteria such as ACC or NMI to the unsup. context, and specifically use the retained features to predict each f i ranging among the other features. As said, this process however involves two related issues.

Both ACC and NMI rely on building clusters ; the number κ i of such clusters should depend on the considered feature f i , be it categorical or continuous. On the one hand, the S k based clustering procedure should be repeated many times, scaling poorly in the large D regime. On the other hand, this would require fine-tuning κ i for each f i (sec. 5.2.2.3), thus failing the requirement of simplicity.

Summary

In this chapter, we have first discussed what constitutes a suitable performance indicator for assessing unsup. FS. The state-of-the-art sup. criteria were thereafter introduced. These criteria were claimed to admit significant limitations, most notably regarding their reliability and stability. A novel unsup. performance criterion, called FIT, was accordingly proposed to tackle these limitations, by considering the reconstruction of all original features simultaneously. The next chapter will empirically compare the respective merits of existing performance indicators and FIT. λ = 1). The validity of this conclusion in other regions of the hyperparameter space will be investigate during the sensitivity study (sec. 6.4). Interestingly, on the two high-dimensional image datasets pixraw10P and warpPie10P, the Laplacian method matches respectively AGNOS-G and AGNOS-S w.r.t. the classification score.

On the remaining lower dimensionality image dataset Yale, NDFS matches the results of AGNOS-S. On Isolet, AGNOS-W and to a lesser extent AGNOS-S outperform all other algorithms, with NDFS ranking third. On ORL, AGNOS-S and AGNOS-W outperform others, though Laplacian and NDFS obtain close performances. On Arcene, AGNOS-S significantly outperforms all other methods, while AGNOS-W does so on ProstateGE and TOX171, medical datasets with comparatively high intrinsic dimension.

Overall, AGNOS is therefore shown to be competitive with the baselines in terms of supervised evaluation ; specifically, the best recorded performance is achieved by a declination of AGNOS on all datasets w.r.t. the classification score, 7 out of 8 datasets w.r.t. the ACC score, and 5 out of 8 w.r.t. the NMI score.

These first sup. results are encouraging. However, based on the claim that the sup. assessment is brittle, we shall delay the discussion regarding the respective performances of AGNOS-S, AGNOS-W and AGNOS-G to their unsup. assessment in sec. 6.3.