Principal Geodesic Analysis in Python

Principal Component Analysis (PCA) is essential for dimensionality and noise reduction, feature extraction, and anomaly detection. However, its effectiveness is limited by the strong assumption of linearity.?

Principal Geodesic Analysis (PGA) addresses this limitation by extending PCA to handle non-linear data that lies on a lower-dimensional manifold.

Introduction
Principal components
       Principal Component Analysis
       Differential geometry
       Tangent PCA
Implementation
       Setup
       Euclidean PCA
       Tangent PCA on hypersphere
References
Appendix        

What you will learn:?How to implement principal geodesic analysis as extension of principal components analysis on a manifolds tangent space.

The complete article, featuring design principles, detailed implementation, in-depth analysis, and exercises, is available in Hands-on Principal Geodesic Analysis

Notes:?

• Environments:?Python ?3.10.10, Geomstats 2.7.0, Scikit-learn 1.4.2
• The implementation relies on Geomstats, an open-source, object-oriented library following Scikit-Learn’s API conventions to gain hands-on experience with Geometric Learning. It is described in article Introduction to Geomstats for Geometric Learning

• This article assumes that the reader is somewhat familiar with differential and tensor calculus [ref?1]. Please refer to our previous articles related to geometric learning [ref?2,?3,?4].
• Source code is available at??Github.com/patnicolas/Data_Exploration/manifolds
• To enhance the readability of the algorithm implementations, we have omitted non-essential code elements like error checking, comments, exceptions, validation of class and method arguments, scoping qualifiers, and import statements.

Introduction

This article is the ninth installments of our ongoing series focused on geometric learning. As with previous articles, we utilize the Geomstats Python library [ref.?5] to implement concepts associated with geometric learning.

As a reminder, the primary goal of learning?Riemannian geometry?is to understand and analyze the properties of curved spaces that cannot be described adequately using Euclidean geometry alone.?

This article revisits the widely used unsupervised learning technique, Principal Component Analysis (PCA), and its counterpart in non-Euclidean space, Principal Geodesic Analysis (PGA).

The content of this article is as follows:

1- Brief recap of PCA

2- Overview of key components of differential geometry

3- Introduction to PCA on tangent space using the logarithmic map

4- Implementation in Python using the Geomstats library.

Principal components

Principal component analysis

Principal Component Analysis (PCA) is a technique for reducing the dimensionality of a large dataset, simplifying it into a smaller set of components while preserving important patterns and trends. The goal is to?reduce the number of variables of a data set, while preserving as much information as possible.

For a n-dimensional data, PCA tries to put maximum possible information in the first component?c0, then maximum remaining information in the second?c1?and so on, until having something like shown in the scree plot below.

Finally, we select the p << n top first components such as:

The principal components are actually the eigenvectors of the Covariance?matrix.

The first thing to understand about eigenvectors and eigenvalues is that they always appear in pairs, with each eigenvector corresponding to an eigenvalue. Additionally, the number of these pairs matches the number of dimensions in the data.

For instance, in a 3-dimension space, the eigenvalues are extracted from the following 3x3 symmetric Covariance matrix:

as?cov(a, b) = cov(b, a).

The eigenvectors of the Covariance matrix (principal components) are?the?directions of the axes where there is the most variance?(most information).

Assuming n normalized data points xi, the first principal component (with most significant eigenvalue) is defined as:

where?'.'?is the?dot product.

Differential geometry

Extending principal components to differentiable manifolds requires basic knowledge of differential and Riemann geometry introduced in previous articles [ref ?2,?3,?4].

Smooth manifold

A smooth (or differentiable) manifold is a topological manifold equipped with a globally defined differential structure. Locally, any topological manifold can be endowed with a differential structure by applying the homeomorphisms from its atlas and the standard differential structure of a vector space.

Tangent space

At every point?P?on a differentiable manifold, one can associate a tangent space, which is a real vector space that intuitively encompasses all the possible directions in which one can move tangentially through?P. The elements within this tangent space at?P?are referred to as the tangent vectors,?tgt_vector?at?P.?

This concept generalizes the idea of a vector originating from a specific point in Euclidean space. For a connected manifold, the dimension of the tangent space at any point is identical to the dimension of the manifold itself.

Geodesics

Geodesics are curves on a surface that only turn as necessary to remain on the surface, without deviating sideways. They generalize the concept of a "straight line" from a plane to a surface, representing the shortest path between two points on that surface.

Mathematically, a curve c(t) on a surface S is a geodesic if at each point c(t), the acceleration?is zero or parallel to the normal vector:

Logarithmic map

Given two points P and Q on a manifold, the vector on the tangent space v from P to Q is defined as:?

Tangent PCA

On a manifold, tangent spaces (or plane) are local euclidean space for which PCA can be computed. The purpose of Principal Geodesic Analysis is to project the principal components on the geodesic using the logarithmic map (inverse exponential map).

Given a mean?m?of?n?data points?x[i]?on a manifold with a set of geodesics at?m,?geod, the first principal component on geodesics is defined as:

The mean point on the data point x[I] on the manifold can be defined as either a barycenter or a?Frechet Mean?[ref?6]. Our implementation in the next section relies on the Frechet mean.

Implementation

For the sake of simplicity, we illustrate the concept of applying PCA on manifold geodesics using a simple manifold, Hypersphere we introduced in a previous article,?Differentiable Manifolds for Geometric Learning: Hypersphere

Further applications and evaluations are available in Hands-on Principal Geodesic Analysis.

Setup

Let's encapsulate the evaluation of principal geodesics analysis in a class, HyperspherePCA. We leverage the class?HyperphereSpace?[ref?7] its implementation of random generation of data points on the sphere.

Euclidean PCA

First let's implement the traditional PCA algorithm for 3 dimension (features) data set using scikit-learn library with two methods:

• euclidean_pca_components?to extract the 3 eigenvectors along the 3 eigenvalues
• euclidean_pca_transform?to project the evaluation data onto 3 directions defined by?the eigenvectors.

We compute the principal components on 256 random 3D data points on the hypersphere.

Output

Principal components:
     [[ 0.63124842 -0.7752775  -0.02168467]
       [ 0.68247094  0.54196625  0.49041411]
       [ 0.36845467  0.32437229 -0.8712197 ]]

Eigen values: [9.84728751 9.0183337  8.65835924]        

Important note: The 3 eigenvalues are similar because the input data is random.

Tangent PCA on hypersphere?

The private method?__tangent_pca?computes principal components on the tangent plane using the logarithmic map. As detailed in the previous section, this implementation employs the Frechet mean as the base point on the manifold, which is the argument of the Geomstats method?fit.

The method?tangent_pca_components?extracts the principal components computed using the logarithmic map. Finally the method?tangent_pca_transform?projects input data along the 3 principal components, similarly to the Euclidean euclidean_pca_transform.

We evaluate the principal geodesic components on hypersphere using the same 256 points randomly generated on the hypersphere and compared with the components on the Euclidean space.

Output:

Euclidean PCA components:
       [[ 0.63124842 -0.7752775  -0.02168467]
         [ 0.68247094  0.54196625  0.49041411]
         [ 0.36845467  0.32437229 -0.8712197 ]]

Tangent Space PCA components:
        [[ 0.8202982  -0.45814582  0.34236423]
         [ 0.45806882  0.16783651 -0.87292832]
         [-0.34246724 -0.87288792 -0.34753831]]        

Thank you for reading this article! I hope you found this overview insightful. For a detailed exploration of the topic, check out Hands-on Principal Geodesic Analysis.

References

[1]?Tensor Calculus - Eigenchris

[2]?Foundation of Geometric Learning

[3]?Differentiable Manifolds for Geometric Learning

[4]?Riemann Metric & Connection for Geometric Learning

[5]?Introduction to Geometric Learning in Python with Geomstats

[6]?Intrinsic Representation in Geometric Learning: Euclidean and Fréchet means

[7]?Differentiable Manifolds for Geometric Learning: Hypersphere

[8] Hands-on Principal Geodesic Analysis

Patrick Nicolas has over 25 years of experience in software and data engineering, architecture design and end-to-end deployment and support with extensive knowledge in machine learning.? He has been director of data engineering at Aideo Technologies since 2017 and he is the?author of "Scala for Machine Learning", Packt Publishing ISBN 978-1-78712-238-3 and Hands-on Geometric Deep Learning newsletter.

#Geomstats #Python #RiemannianManifold #Manifold #RiemannMetric #BetaDistribution #FisherRao #GeometricLearning #PrincipalGeodesicAnalysis