Considering, assessing, and ensuring fairness is key when relying on machine learning (ML) for sensitive decision making.Yet, despite growing attention, multiple fairness definitions are currently adopted and consensual guidelines across learning paradigms are still lacking.Therefore, this review first describes sources of bias and focuses on outcome fairness, comparing popular criterion such as independence, separation, and sufficiency.Fairness interventions are then examined at pre-, in-, and post-processing stages and across supervised, semi-supervised, unsupervised, and self-supervised settings.

Neighbor embedding has been a quantum leap in nonlinear dimensionality reduction, revolutionizing the way data can be visualized.Neighbor embedding typically adapts to the local density in the highdimensional data space with adaptive bandwidths in entropic affinities, while it resolves scale indeterminacies by having unit bandwidths in the low-dimensional embedding space.In this paper, multi-scale stochastic neighbor embedding (Ms.SNE) is improved by allowing it to adapt lowdimensional bandwidths in a data-driven way instead of having fixed ones.In practice, Ms.SNE goes through a multi-scale optimization process; coordinates and bandwidths are optimized separately, in an alternate fashion, to avoid interferences: (i) bandwidths are optimized from previous coordinates and (ii) coordinates are optimized given the new bandwidths.Experimentally, twice adaptive bandwidths improve Ms.SNE's capability to preserve neighborhoods on all scales, i.e., local and global data structure; this claim is supported with quantitative results on several benchmarks. Neighbor embedding for data visualizationDimensionality reduction (DR) [1] yields nonlinear embeddings [2] that allow for visualization and exploratory analysis of data in many domains, such as computational biology [3], to cite just one example.Modern DR involves mostly methods of neighbor embedding (NE) [4], like Student t-distributed stochastic NE (t-SNE) [5] or uniform manifold approximation and projection (UMAP) [6].These methods are very robust to the curse of dimensionalty [7] and produce local embeddings; sparsity of small-size neighborhoods is also the key to accelerate these methods [8,6,9,10].However, sparsity might also cause the loss of the global structure of data [11,6,12,10,2,13,14].This depends on how the final embedding does reminisce [12] about its initialization with PCA [15] or Laplacian eigenmaps [16], either due to early stopping [5] or explicit regularization [13].Another workaround consists in having neighborhoods on two [9, 10] or more scales [11], even though acceleration can become more difficult.A less investigated feature of NE is a form of uniformization of data density in the low-dimensional (LD) embedding.It results from the use of entropic affinities

Local methods of dimensionality reduction like neighborhood embedding (NE) and t-SNE in particular outperform older global approaches such as stress-based multi-dimensional scaling (MDS).Stochastic neighborhoods are less sensitive than distances to statistical variations between spaces with strongly different dimensionalities, making a match across them very difficult.Here, we take inspiration from those stochastic neighborhoods in order to devise a pseudo-distance that is less prone to concentration than the Euclidean distance.For two points in the high-dimensional data space, it is defined as the symmetrized Kullback-Leibler divergence across the (stochastic) neighborhoods of the two points (SKLAN).Plugging the SKLAN in a method of stress-based MDS, we compare quantitatively t-SNE, MDS with all Euclidean distances, and MDS with SKLAN & Euclidean distances on several data sets.The results show that SKLAN allows MDS to perform competitively with t-SNE.

As a local method of dimensionality reduction, t-SNE requires careful initialization in order to preserve the data global structure to the best extent.In regular t-SNE, the low-dimensional embedding is initialized either randomly or with PCA; next, gradient descent refines the embedding coordinates in two phases.In the first one, called early exaggeration, attractive forces between points are artificially strengthened to delay any detrimental effect of repulsive forces while points are still poorly organized.In this paper, a novel initialization of t-SNE is proposed.It works by hierarchizing the data points into a space-partitioning binary tree and successive runs of t-SNE with 4, 8, 16, ..., N points.Between two runs, the prototypical point in each tree branch is split into its two children prototypes, with some little random noise, and the embedding is rescaled to account for the increased population.Experimental results show the effectiveness of the method.The proposed method is compatible with any method of neighbor embedding (t-SNE, UMAP, etc.) provided early exaggeration can be disabled and initial coordinates can be fed into.

To minimise its loss function, the popular method of nonlinear dimensionality reduction t-SNE requires O(N 2 ) computations.As its applications often involve large datasets, fast approximations have been developed, such as Barnes-Hut t-SNE and FIt-SNE.Most fast approximations to t-SNE require the embedding dimensionality to be small, typically 2 or 3, limiting the use of t-SNE to data visualisation.Additionally, the effective computation time of the current accelerated t-SNE algorithms stays too high for a comfortable interactive visual exploration of data.This paper proposes an accelerated approximation to t-SNE with iterations of complexity O(N K), which does not rely on the use of a model to capture information about the low-dimensional space, relieving the computational burden of high dimensionality of the embedding space.For this purpose, the proposed method approximates neighbour sets and keeps track of smoothed estimations of long-range interactions in O(N K) time.The method is qualitatively tested on a handful of datasets and shows comparable results to existing fast neighbour embedding methods in the context of data visualisation.Code is available at https://github.com/PierreLambert3/c_fast_hSNE.git.

Since their release, transformers, and in particular fine-tuned transformers are widely used for text-related classification tasks.However, only a few studies try to understand how fine-tuning actually works and existing alternatives, such as feature-based transformers, are often overlooked.In this work, we study a French transformer model, Camem-BERT, to compare the fine-tuned and feature-based approaches in terms of their performances, interpretability and embedding space.We observe that while fine-tuning has a limited impact on performances in our case study, it significantly affects the intepretability (by better isolating words that are intuitively connected to the classification task) and embedding space (by summarizing the majority of the relevant information into a fewer dimensions) of the results.We conclude by highlighting open questions regarding the generalization potential of fine-tuned embeddings.

Reconstruction-based anomaly detection typically relies on the reconstruction of a defect-free output from an input image.Such reconstruction can be obtained by training an autoencoder to reconstruct clean images from inputs corrupted with a synthetic defect.Previous works have shown that adopting an autoencoder with skip connections improves reconstruction sharpness.However, it remains unclear how skip connections aect the latent representations learned during training.Here, we compare internal representations of autoencoders with and without skip connections.Experiments over the MVTec AD dataset reveal that skip connections enable the autoencoder latent representations to intrinsically discriminate between clean and defective images.

Most recent deep neural network architectures for tabular data operate at the feature level and process multiple latent representations simultaneously.While the dimension of these representations is set through hyper-parameter tuning, their number is typically fixed and equal to the number of features in the original data.In this paper, we explore the impact of varying the number of latent representations on model performance.Our results suggest that increasing the number of representations beyond the number of features can help capture more complex interactions, whereas reducing their number can improve performance in cases where there are many uninformative features.

Student t-distributed stochastic neighbor embedding (t-SNE) finds low-dimensional data representations allowing visual exploration of data sets.t-SNE minimises a cost function with a custom two-phase gradient descent.The first phase is called early exaggeration and involves a hyper-parameter whose value can be tricky and time-consuming to set.This paper proposes another way to optimise the cost function without early exaggeration.Empirical evaluation shows that the proposed method of optimization converges faster and yields competitive results in terms of neighborhood preservation.

Abstract Random Projection is one of the most popular and successful dimensionality reduction algorithms for large volumes of data. However, given its stochastic nature, different initializations of the projection matrix can lead to very different levels of performance. This paper presents a guided random search algorithm to mitigate this problem. The proposed method uses a small number of training data samples to iteratively adjust a projection matrix, improving its performance on similarly distributed data. Experimental results show that projection matrices generated with the proposed method result in a better preservation of distances between data samples. Conveniently, this is achieved while preserving the database-friendliness of the projection matrix, as it remains sparse and comprised exclusively of integers after being tuned with our algorithm. Moreover, running the proposed algorithm on a consumer-grade CPU requires only a few seconds.

Dimension reduction (DR) computes faithful low-dimensional (LD) representations of high-dimensional (HD) data. Outstanding performances are achieved by recent neighbor embedding (NE) algorithms such as t -SNE, which mitigate the curse of dimensionality. The single-scale or multiscale nature of NE schemes drives the HD neighborhood preservation in the LD space (LDS). While single-scale methods focus on single-sized neighborhoods through the concept of perplexity, multiscale ones preserve neighborhoods in a broader range of sizes and account for the global HD organization to define the LDS. For both single-scale and multiscale methods, however, their time complexity in the number of samples is unaffordable for big data sets. Single-scale methods can be accelerated by relying on the inherent sparsity of the HD similarities they involve. On the other hand, the dense structure of the multiscale HD similarities prevents developing fast multiscale schemes in a similar way. This article addresses this difficulty by designing randomized accelerations of the multiscale methods. To account for all levels of interactions, the HD data are first subsampled at different scales, enabling to identify small and relevant neighbor sets for each data point thanks to vantage-point trees. Afterward, these sets are employed with a Barnes-Hut algorithm to cheaply evaluate the considered cost function and its gradient, enabling large-scale use of multiscale NE schemes. Extensive experiments demonstrate that the proposed accelerations are, statistically significantly, both faster than the original multiscale methods by orders of magnitude, and better preserving the HD neighborhoods than state-of-the-art single-scale schemes, leading to high-quality LD embeddings. Public codes are freely available at https://github.com/cdebodt.

Multidimensional scaling is a statistical process that aims to embed high-dimensional data into a lower-dimensional, more manageable space.Common MDS algorithms tend to have some limitations when facing large data sets due to their high time and spatial complexities.This paper attempts to tackle the problem by using a stochastic approach to MDS which uses gradient descent to optimise a loss function defined on randomly designated quartets of points.This method mitigates the quadratic memory usage by computing distances on the fly, and has iterations in O(N ) time complexity, with N samples.Experiments show that the proposed method provides competitive results in reasonable time.Public codes are available at https://github.com/PierreLambert3/SQuaD-MDS.git. Multidimensional scaling and its limitationsDimensionality reduction (DR) is the process of mapping high-dimensional (HD) observations into a lower-dimensional (LD) space such that the LD embedding is a faithful representation of the HD data.The main DR uses are in machine learning, to curb the curse of dimensionality, and in visualisation.Mapped data can reveal structures that would lay hidden from the human perception if left in HD.Typically, some information is lost by the DR and, therefore, each DR method has a take on what kind of information should be preserved and what can be lost.Used frequently in visualisation, t-SNE [1] aims at retaining the neighbourhood of each point according to a distance metric and a perplexity, which reflects the size of the neighbourhood to preserve.While t-SNE excels at retaining local structures, sufficiently remote points tend to be considered equally distant by the algorithm and, therefore, the larger-scale structures can be distorted.Such distortions can lead to erroneous conclusions by the human user, who might overestimate the dissimilarity between two clusters that are distant in the LD embedding.For this reason, using multiple DR paradigms in conjunction is a good practice in visualisation: another embedding that preserves distances instead of neighbourhoods would have prevented this erroneous conclusion.This paper considers metric multidimensional scaling (MDS): a DR technique that produces a LD embedding such that the pairwise distances in LD reflect those in HD.MDS minimises a cost function which, in its simplest form, is the sum of the squared differences between distances in HD and the Euclidean distances in LD.A common strategy to optimize this cost function is based on 417

Fast multi-scale neighbor embedding (f-ms-NE) is an algorithm that maps high-dimensional data to a low-dimensional space by preserving the multi-scale data neighborhoods.To lower its time complexity, f-ms-NE uses random subsamplings to estimate the data properties at multiple scales.To improve this estimation and study the f-ms-NE sensitivity to randomness, this paper generalizes the f-ms-NE cost function by averaging several subsamplings.Experiments reveal that this can slightly improve the quality of the embeddings while maintaining reasonable computation times.Codes are available at https://github.com/cdebodt/Fast_Multi-scale_NE.

Dimensionality reduction (DR) aims at faithfully and meaningfully representing high-dimensional (HD) data into a low-dimensional (LD) space. Recently developed neighbor embedding DR methods lead to outstanding performances, thanks to their ability to foil the curse of dimensionality. Unfortunately, they cannot be directly employed on incomplete data sets, which become ubiquitous in machine learning. Discarding samples with missing features prevents their LD coordinates computation and deteriorates the complete samples treatment. Common missing data imputation schemes are not appropriate in the nonlinear DR context either. Indeed, even if they model the data distribution in the feature space, they can, at best, enable the application of a DR scheme on the expected data set. In practice, one would, instead, like to obtain the LD embedding with the closest cost function value on average with respect to the complete data case. As the state-of-the-art DR techniques are nonlinear, the latter embedding results from minimizing the expected cost function on the incomplete database, not from considering the expected data set. This paper addresses these limitations by developing a general methodology for nonlinear DR with missing data, being directly applicable with any DR scheme optimizing some criterion. In order to model the feature dependences, an HD extension of Gaussian mixture models is first fitted on the incomplete data set. It is afterward employed under the multiple imputation paradigms to obtain a single relevant LD embedding, thus minimizing the cost function expectation. Extensive experiments demonstrate the superiority of the suggested framework over alternative approaches.