Dimensionality Reduction using Elastic Measures

With the recent surge in big data analytics for hyper-dimensional data there is a renewed interest in dimensionality reduction techniques for machine learning applications. In order for these methods to improve performance gains and understanding of the underlying data, a proper metric needs to be identified. This step is often overlooked and metrics are typically chosen without consideration of the underlying geometry of the data. In this paper, we present a method for incorporating elastic metrics into the t-distributed Stochastic Neighbor Embedding (t-SNE) and Uniform Manifold Approximation and Projection (UMAP). We apply our method to functional data, which is uniquely characterized by rotations, parameterization, and scale. If these properties are ignored, they can lead to incorrect analysis and poor classification performance. Through our method we demonstrate improved performance on shape identification tasks for three benchmark data sets (MPEG-7, Car data set, and Plane data set of Thankoor), where we achieve 0.77, 0.95, and 1.00 F1 score, respectively.


Introduction
With the ever increasing number of observations and expanding number of variables in modern datasets, the use of dimensionality reduction as a first step for training machine learning models has gained a renewed interest. Methods such as the t-distributed Stochastic Neighbor Embedding (t-SNE) (van der Maaten and Hinton, 2008) and the Uniform Mani-fold Approximation and Projection (UMAP) (McInnes et al., 2020), have enabled improved classification performance over methods such as principal component analysis (PCA) and factor analysis. This is due to their ability to accurately embed complicated data structures into small dimensional spaces by computing the distances between observations in higher dimensional space. The choice of distance function is typically left to the user, where the default metric is the Euclidean distance, which is deficient in higher dimensional space. It has been shown that the UMAP is sensitive to the choice of distance metric and can effect the results significantly (McInnes et al., 2020).
When computing the distances between observations, a metric which is symmetric, isometric, and obeys the triangle inequality is preferred. These properties lead to pairwise distance computations that are independent of input order and can be degenerate for some data types (Srivastava et al., 2011b;Tucker et al., 2013). For example, the Euclidean distance is not a proper distance on functional data in R 1 under phase variation (Tucker et al., 2013), the space of open and closed curves (Srivastava and Klassen, 2016), and any trajectory on a Riemmanian manifold (Su et al., 2014).
In this paper, we demonstrate that selecting a distance metric that is consistent with the data topology drastically improves the performance of both t-SNE and UMAP on functional data. We apply this method to a clustering of curves tasks in R n , where we choose our distance metric such that it measures the shape of these curves by accounting for rotation, scale, and parameterization. We utilize the elastic shape framework (Srivastava and Klassen, 2016), which yields two metrics that properly measure distance in both shape and amplitude, and provides a distance from one shape to another in sampling variability.
When applied to the space of open curves, a Riemmanian manifold, we are able to obtain an initialization point for dimensionality reduction that is consistent with the properties of the data. We also apply this framework to any trajectory on a Riemmanian manifold using the square-root velocity transformation. This paper is organized as follows. In Section 2 we provide an overview of the Elastic Shape Analysis (ESA) framework, in Section 3 we review both t-SNE and UMAP, in Section 4 we provide results on two data sets, one being a set of shapes from the MPEG7, shapes of cars extracted from video, and fighter jet shapes, and finally, we provide a discussion and concluding remarks in Section 5.

Elastic Shape Analysis
Elastic Shape Analysis (ESA) is a collection of techniques for registering and analyzing functional data, using the process of phase-amplitude separation. From the separated components, statistical analysis can be performed on the individuals phase and amplitude components (Kurtek et al., 2011;Srivastava et al., 2011a;Tucker et al., 2013). In this section we provide a review of ESA and refer the reader to (Kurtek et al., 2011;Srivastava et al., 2011a;Srivastava and Klassen, 2016;Tucker et al., 2013) for a complete overview.
Phase and amplitude represent two orthogonal components of a function's shape, which are properties of a function that remain invariant to shape-preserving transformations (rotation, translation, scaling, and phase) (Dryden and Mardia, 2016;Srivastava and Klassen, 2016). The phase component represents the horizontal variability within trajectories or reparameterization, where as the amplitude component represents the vertical variability independent of phase. In order to analyze these components the need to be separated through alignment, Srivastava et al. (2011a) demonstrated that the Fisher-Rao metric is a proper distance and provides this separation.
To compute the alignment using the Fisher-Rao metric, the Square Root Velocity Function (SRVF) (Srivastava et al., 2011a) is used for registration of functions in R n . For real-valued curves, the SRVF performs a bijective mapping of the real-valued curve f to its normalized gradient f / |f |. The registration of two real-valued curves is performed by elastically deforming the domain of one function such that the L 2 distance between the SRVFs of the two curves is minimized. The amount of elastic deformation required is measured by the phase distance (Section 2.2), while the residual distance between the SRVF, post registration (rotation, and scaling), defines the amplitude distance between them (Section 2.1). Together they are known as elastic distances. By registering SRVFs instead of trajectories directly, the phase and amplitude distances become proper metrics and are invariant to shape-preserving transformations.

Amplitude distance for R n valued functions
Let F R n = {f : [0, 1] → R n , f differentiable} be the class of differentiable trajectories on [0, 1] mapping to R n with n ≥ 2 1 . In higher dimensional Euclidean space (n ≥ 2), the scale, rotation, and phase of a trajectory need to be accounted for in order to isolate its shape. Scale variability is removed by standardizing each trajectory to have unit length, i.e., each trajectory is divided by the L 2 norm of its gradient: Rotation variability is accounted for using the space of rotation matrices, the Special Orthogonal Group SO(n) and is defined as the group of orthogonal matrices with a determinant of one. For trajectories in R 2 , SO(2) defines the rotations around a point and in R 3 SO(3) defines rotations around a line. The action of SO(n) on a trajectory f is denoted as O(f ) and is defined pointwise as where Of (t) represents a standard matrix multiplication of the n × n matrix O and the n × 1 vector f (t). See Vladimir (1994) for more details on the Orthogonal groups and their properties. The optimal rotation matrix in SO(n) is found alongside the optimal reparameterization when computing the amplitude distance.
Phase variability in R n is represented using the space Γ = {γ : I → I|{γ, γ −1 } ∈ C 1 (I),γ > 0} of all positive slope diffeomorphisms of the unit interval. Together with the operation of composition, Γ is a group and is defined with respect to the domain I = [0, 1] . The reparameterization of a curve f by a warping function γ ∈ Γ is denoted as the operation f • γ.
We desire a distance that is invariant to simultaneous reparameterizations, which allows us to use the SRVF as the following transformation on trajectories f ∈ F n R : The SRVF is defined as the following transformation on trajectories f ∈ F n R : where |f (t)| is the absolute value of f at t. This transformation maps trajectories onto the L 2 ball of radius one and is a bijective mapping, up to an additive constant (Srivastava and Klassen, 2016).
Since the space of SRVFs is the L 2 ball then the norm on the SRVFs is the arc length distance between points on the sphere: where q f = SRV F (f ) and q g = SRV F (g) for two trajectories f, g ∈ F R n and q f (t), q g (t) denotes the inner product of the vectors q f (t), q g (t). To convert this into an amplitude distance we need to place f and g in phase and rotation with each other. This optimization is summarized as the following amplitude distance on R n valued trajectories (Srivastava et al., 2011a): where q f and q O(g•γ) denote the SRVF's of f and O(g • γ) respectively.

Phase Space
We will define the phase space using diffeomorphic mapping. The phase space of the unit interval [0, 1] as defined above is This diffeomorphic constraint gives rise to the notion of elasticity because the elements of Γ, i.e., phase functions, can only smoothly stretch and contract portions of the unit interval so that it maps back to itself. Phase is generally thought of as the representation of a trajectory because any trajectory with domain [0, 1] can be warped by a phase function to appear differently. The amplitude will be taken to be those features of a trajectory that remain unchanged under any possible warping.

Phase distance
To define phase distance we use the optimal γ that defines the amplitude distance. The phase space Γ is a nonlinear manifold with no known geometry so we use the SRVF to map Γ to a known geometry (Tucker et al., 2013). Phase functions are positive for all t ∈ [0, 1] and ||q γ || = 1 0 γ (t) 2 dt = 1, so the SRVF maps Γ onto the positive orthant of a unit Hilbert Sphere. Thus the phase distance is defined as where ψ = √γ and ·, · is the inner product between the two vectors (Srivastava and Klassen, 2016). The metric d p (γ 1 , γ 2 ) is essentially measuring the amount of elastic deformation needed to compare the shapes of f 1 and f 2 , when γ 1 = id is the identity warping.

Dimension Reduction
In dimensionality reduction, we are interested in finding a low dimensional embedding space, Y , for the high dimensional space, X, such that Y is as similar to X as possible and that the representation of the reduced space facilitates better data analysis (e.g., classification with good class separation). For the dimensionatliy reduction to work we want to define the similarities between two objects x i and x j in X and their mapping to Y . Recently, two methods have become highly utilized in the literature for performing dimensionality reduction; t-SNE and UMAP. In the following sections we will give a brief overview of the two methods.

t-SNE: t-distributed Stochastic Neighbor Embedding
A t-distributed Stochastic Neighbor Embedding (t-SNE) (van der Maaten and Hinton, 2008) embedding defines probabilities proportional to the similarity of the objects x i and x j , and are defined as is the Euclidean distance between the two objects (as defined in (van der Maaten and Hinton, 2008)). The similarity between the two objects is the conditional probability that x i is similar to x j in proportion to the probability density under a Gaussian distribution centered at x i .
The total probability or similarity is defined as where t-SNE aims to learn a d-dimensional mapping, Y , that reflects the similarities p ij .
The similarities between y i and y j are defined as: for which the student t-distribution measures these similarities in the mapping space.
The locations of the points (y i ) in the lower dimensional space is determined by minimizing the Kullback-Leibler divergence of the distribution P from the distribution Q, i.e., This minimization is performed using gradient descent and is the mapping between X and Y .

UMAP: Uniform Manifold Approximation and Projection
Uniform Manifold Approximation and Projection (UMAP) approximates a manifold by constructing a fuzzy simplicial set representation, which is performed on high dimensional data (X) and on a low dimensional representation (Y ∈ R d ). The selected representation is the one that optimizes the cross entropy between the high and low dimensional spaces.
UMAP is similar to the approach of t-SNE, which constructs a probability distribution over pairs of high-dimensional objects. In t-SNE similar objects have a high probability of being picked, whereas dissimilar points have an extremely small probability of being picked.
t-SNE defines a similar probability distribution over the points in the low-dimensional map, and minimizes the Kullback-Leibler divergence between the two distributions.
In UMAP, the high dimensional similarities, v j|i , are local fuzzy simplicial set memberships based on smooth nearest-neighbor (NN) distances v j|i from x i ∈ X to one of its k is the Euclidean distance on the learned manifold. The parameter ρ i is the distance to nearest neighbor and σ i is a normalizing constant. The symmetrization are used to produce an undirected graph structure representing the 1-dimensional frame of the fuzzy simplicial set, is carried out by fuzzy set union using the probabilistic t-conorm The graph defined by the v ij is then embedded into a low dimensional space Y , where the dimension is prescribed as a parameter. The low dimensional similarities between the projections y i and y j , of x i and x j , into Y via the initial embedding are given by where a and b are user defined and a gradient descent procedure is used to find them. The defaults for UMAP are a ≈ 1.929 and b ≈ 0.7915 (McInnes et al., 2020).
The cost function that is optimized to find the embedding is which penalizes discrepancies in the relative distributions of similarities in X and Y .

Elastic Modifications
To perform dimensionality reduction, it is critical that the distance, d(x i , x j ), is appropriate for the underlying data. In this work, we perform dimensionality reduction on curves that lie in R n . We then can utilize the distance defined in Equation 3  We give a brief review of the geometry of the space of PDFs but refer the reader to Kurtek and Bharath (2015) for a more in-depth review. We focus here on univariate densities on [0, 1], but the theory can easily be extend for all finite dimensional densities.
Let P = {p : [0, 1] → R ≥0 | 1 0 p(x) dx = 1} as the space of all PDFs and we define the tangent space T p (P) = {d p : [0, 1] → R| 1 0 d p (x)p(x) dx = 0}. The inner-product on this space, known as the Fisher-Rao Riemmanian metric (Kass and Vos, 1997;Rao, 1945) is given by: Cencov (1982) showed that this metric is invariant to re-parameterizations. However, the metric is difficult to compute, requiring numerical methods and large computations. Bhattacharya (1943) proposed a convenient square-root transformation with simplifies the computation of the metric and is the transformed space where the Hellinger distance is an extrinsic metric. Define the transformation φ(p) = √ p as the square-root density of PDF p, which is similar to SRVF described previously. The corresponding space of SRDs is which the positive orthant of the Hilbert Sphere. Since the geometry is known in this transformed space we can define the geodesic distance between two PDFs p 1 , p 2 ∈ P under the Fisher-Rao metric using the SRDS √ p 1 , √ p 2 ∈ Ψ is the great circle defined as Therefore, we can replace the Kullback-Leibler divergence in t-SNE with a proper metric on the space of PDFs using Equation 5 similar to divergences done in Bunte et al. (2012); Im et al. (2018). The use of an intrinsic metric is more natural than an extrinsic method as it is the exact distance between two PDFs and is invariant to re-parametrizations of the PDFs We will denote this modification to t-SNE as elastic t-SNE or et-SNE and will compare t-SNE, UMAP, and elastic t-SNE using the elastic metrics on the space of curves in R n .

Results
In this section we provide results on two data set. The first data set will be analyzing a set of shapes where we have 65 shape classes from the MPEG-7 Core Experiment CE-Shape-1 Test Set (Jeannin and Bober, 1999). This data set is used for benchmarking shape matching algorithms and includes binary images grouped into categories by their content, not their appearance or shape. The second is the fighter plane shapes and the car shapes from Thakoor et al. (2007) and includes part of the MPEG-7 data set.

MPEG7
In this section, we classify real world curve data taken from the MPEG-7 database (Jeannin and Bober, 1999). The full database has 1300 shape samples, 20 shapes for each class, and 65 shape classes. An example of some of the shapes from the MPEG-7 bases is presented in Figure 1. Note the differences in rotations and scales of each of the shapes which complicates the analysis. Using the shape distance in Definition 3 we can compute the pairwise distance matrix between all shapes in the data set. Figure 2a provides the distance matrix using the elastic distance and for comparison we computed the distance metric using the Euclidean distance and is provided in Figure 2b. There is a definite difference in structure and visually there is a noticeable large amount of clustering in the elastic distance where the Euclidean distance is only showing roughly three large groups.  We computed both t-SNE, e-tSNE, and UMAP projecting the data onto two components using the elastic distance and the Euclidean distance for comparison. Figure 3 provides the t-SNE results with panel (a) using the elastic distance and panel (b) using the Euclidean distance. There is a distinct clustering of each of the classes and separability of the classes versus the Euclidean distance. Figure 4 provides the elastic t-SNE results with panel (a) using the elastic distance and panel (b) using the Euclidean distance. Comparing to standard t-SNE using the Kullback-Leibler divergence we see a slightly better separation of classes and as mentioned in above we see neighborhood sizes are more preserved. To add a more complete picture to the embedding we trained a Random Forest classifier (Breiman, 2001) using 5-fold cross-validation. Since, t-SNE was not originally defined for out-of-sample data we will focus on UMAP. In the following section, for the full data analysis we will utilize parametric t-SNE (Maaten, 2009;Poličar et al., 2021) which allows for outof-sample data. Figure 6 provides the average F1 score across folds with the standard deviation shaded, using the elastic metric and the Euclidean metric. Overall, for each class the F1 score is larger for each class and maintains on average over 0.8 while on average of the Euclidean is 0.6. Figure 7 provides the confidence matrix for the elastic metric in panel (a) and the Euclidean metric in panel (b). As was noted from the F1 score, the elastic distance for most of the classes does extremely well with few classes being misspecified.   The Euclidean distance does have trouble with a few of the classes with more than a few miss classifications.

Shape Database
In this section, we look at the overall classification performance utilizing UMAP and parametric t-SNE as a dimensionality reduction tool and then performing classification using a Random Forest classifier. Again we will compare the results against using the standard Euclidean metric in both dimension reduction techniques. For this study we will utilize the fighter jet shapes, car shapes, and the full MPEG7 database described and analyzed in the previous section.
The fighter airplane shape database includes Mirage,Eurofighter,Harrier, shapes. Since the F-14 has two possible shapes, one when its wings are closed and another when its wings are opened, the total number of shape classes is seven, where there are 30 shapes for each class for a total of 210 examples. The database was created from digital pictures of die-cast replica of the airplanes and were segmented to extract the contour.
The car shapes were generated using the method described in Thakoor and Gao (2005) where contours of vehicles were extracted from video clips. There are four classes in the group: sedan, pickup, minivan, and SUV and each have 30 samples for each class. The data set shows larger within-class variation, as shapes of vehicles of different makes and models vary and some contours are distorted due to the shadow also being extracted. This data set contains more real world variability in applying shape classification metrics. Figure 8 presents the F1 score for each class for the plane data set in panel a) and the car data set in panel b). A Random Forest classifier was trained from the UMAP embedding using the designated distance. The shaded region shows the variability across the 5-fold cross-validation. In both data sets the elastic metric vastly outperforms the the Euclidean metric for all of the classes and shows less variability across the folds. The increase in performance is directly related to utilizing a proper distance and a metric that is invariant to scale, rotation, and re-parameterization of the shape. Being invariant to these actions is critical in any shape analysis/recognition task.     Lastly, to examine performance across multiple classifiers we compared the performance of the Random Forest (RF) against the Gradient Boosted Trees (GBT) (Friedman, 2001) and K-nearest neighbors classifiers (KNN) (Cover and Hart, 1967). The purpose of this comparison is to demonstrate that the method is independent of the classifier and to show the power is in choosing the proper metric for the geometry of the data under consideration. Table 2 presents the class averaged F1 score and MCC for the three classifiers for the MPEG-7 data set. For all three classifiers under both UMAP and t-SNE we see an improvement in classification performance when using the elastic metric over the Euclidean.
Across the classifiers, UMAP has the most consistent performance, while t-SNE obtains the highest under KNN, the performance under the other classifiers is quite reduced. The increase in performance between the two metrics is attributed to picking a metric that is a proper distance for the data being classified.

Discussion
We have proposed a new flexible elastic metric for functional data utilizing state-ofthe art dimensionality reduction methods. We have demonstrated its advantages over the current methods using current shape analysis benchmarking data set. Unlike the current cross-sectional metrics the elastic method accurately estimates the mean of the underlying data generating mechanism and handles rotation and parametrization as a nuisance accordingly. It is imperative to choose a metric that is respective of the underlying variability of the data and is respective of the geometry. Doing so will give advantages in multiple machine learning tasks. We have presented the metric for open and closed shapes in R n , but equivalent metrics exists for functions in R 1 (Tucker et al., 2013), surfaces (Kurtek et al., 2017), and images (Xie and Srivastava, 2016