Source-linked AI summary
Principal Graphs and Manifolds
A. N. Gorban, A. Y. Zinovyev
TL;DR
Approximating branched data with one-dimensional principal curves is inadequate, motivating principal graphs and manifolds as lower-complexity objects embedded in multidimensional data. The paper presents a mean-squared-distance framework and related construction algorithms, reporting that nonlinear two-dimensional manifolds can match the performance of three- and four-dimensional linear principal manifolds.
Problem
One-dimensional principal curves inadequately represent branched data distributions, motivating principal graphs with branching points.
Method
The chapter uses mean squared distance approximation with expectation/maximisation algorithms, elastic penalties, and graph grammars to construct principal graphs and manifolds.
Results
Nonlinear two-dimensional principal manifolds systematically outperform corresponding criteria while achieving the performance of three- and four-dimensional linear principal manifolds.
Takeaways & Limitations
Principal graphs and manifolds provide a unified lower-dimensional approximation framework that generalizes mean points, principal components, and k-means principal points.
Takeaways & Limitations
The constructed object's interpretation depends on the probabilistic interpretation of the dataset and the chosen heuristic approach to coarse-grained self-consistency.
Abstract
from arXiv · showhide
In many physical, statistical, biological and other investigations it is desirable to approximate a system of points by objects of lower dimension and/or complexity. For this purpose, Karl Pearson invented principal component analysis in 1901 and found 'lines and planes of closest fit to system of points'. The famous k-means algorithm solves the approximation problem too, but by finite sets instead of lines and planes. This chapter gives a brief practical introduction into the methods of construction of general principal objects, i.e. objects embedded in the 'middle' of the multidimensional data set. As a basis, the unifying framework of mean squared distance approximation of finite datasets is selected. Principal graphs and manifolds are constructed as generalisations of principal components and k-means principal points. For this purpose, the family of expectation/maximisation algorithms with nearest generalisations is presented. Construction of principal graphs with controlled complexity is based on the graph grammar approach.
PROBABILISTIC INTERPRETATION OF STATISTICS AND NOTION OF SELF-CONSISTENCY
The probabilistic view treats a dataset as an i.i.d. sample from an underlying multidimensional distribution, enabling principal manifolds to be defined through self-consistency. For finite datasets, conditional means require coarse-grained neighborhood-based approximations whose size controls approximator complexity.
- A dataset X is treated as one i.i.d. sample from a multidimensional probability distribution F(x), which assigns probabilities to observations.
- Self-consistency requires each vector y in Y to equal the conditional mean of x given that x projects orthogonally onto y.The concept was introduced by Efron and later developed by Flury as a fundamental statistical notion.
- Finite datasets often cannot provide conditional means because each y may receive zero or one projected point, motivating neighborhood-based self-consistency.The effective neighborhood size is a fundamental parameter controlling the complexity of the resulting approximator Y.
Generic Expectation-Maximisation algorithm for estimating principal objects
The generic expectation-maximisation algorithm alternates projection and optimization steps to estimate a principal object, optionally adapting its properties until convergence. A principal-line implementation exemplifies this bi-iteration scheme.
- Core algorithm: The algorithm initializes a principal-object configuration, projects every data point orthogonally onto it, and maximizes the configuration given those projections.These initialization, expectation, and maximization steps form the core iteration.
- Core algorithm: An optional adaptation step changes the principal object’s properties, typically by adding or removing points, before repeating the iteration until convergence criteria are satisfied.Adaptation is applied within the repeated projection–optimization cycle when needed.
- Principal-line example: The principal line provides an implementation of this bi-iteration scheme, with broader generalizations attributed to subsequent work.The cited example connects the generic procedure to a concrete principal-object construction.
Iterative algorithm for calculating the first principal component
The first principal component is computed by an iterative EM procedure that initializes from the mean and a random direction, repeatedly updates and renormalizes the direction, and stops when its change is sufficiently small. Subsequent components are obtained by deflation, while convergence is reliable only when leading covariance eigenvalues are well separated.
- Iterative algorithm for calculating the first principal component: The EM iteration initializes a0 as the mean, selects a random a1, updates the direction, renormalizes it, and repeats until its angular change is sufficiently small.The stopping condition is based on the direction of a1 changing by no more than a small angle.
- Iterative algorithm for calculating the first principal component: After finding a1, the method deflates the data by subtracting the mean and its projection onto a1, then repeats the procedure to calculate further components.The deflated dataset is denoted X(1).
- Iterative algorithm for calculating the first principal component: The basic EM procedure has good convergence properties only when the first covariance-matrix eigenvalues are sufficiently well separated.When the leading eigenvalues are not well separated, more sophisticated approaches are needed.
SOM APPROACH FOR PRINCIPAL MANIFOLD APPROXIMATION AND ITS GENERALISATIONS
The section presents SOMs and their generalisations for principal-manifold approximation, then contrasts self-consistent and globally optimal principal curves with elastic-map constructions. It emphasizes SOM’s structural and approximation goals, the need for coarse-grained self-consistency, and optimization through elastic energies.
- SOM approach: SOMs map a finite metric space into R^m while balancing preservation of its structure against approximation of the dataset, using grid-like domains for principal manifolds.The algorithm connects centroids so neighboring positions change together, and its neighborhood radius decreases across epochs.
- SOM approach: SOM lacks an objective function minimized by training, motivating optimization-based alternatives such as GTM, which fits a Gaussian mixture by EM likelihood maximization.GTM aligns mixture centers along an embedded two-dimensional grid.
- Principal manifolds by Hastie and Stuelze: For finite datasets, the Hastie–Stuelze method replaces exact self-consistency with local smoothing: projection, neighborhood-weighted regression, and iteration until the curve stabilizes.The method uses a coarse-grained neighborhood span and weighted least-squares local averages.
- Principal manifolds by Hastie and Stuelze: Kégl’s principal curves of fixed length are globally optimal approximators, but because practical global optimization was unsuccessful, his Polygonal line algorithm provides an efficient heuristic.The Polygonal line algorithm follows a standard EM splitting scheme and controls global curve smoothness with a parameter.
- Elastic maps and graphs: Elastic maps approximate manifolds by optimizing mean squared distance together with membrane or plate elastic energy, while elastic graphs formalize topology through selected families of k-stars.An elastic principal manifold is an elastic map obtained from an elastic net embedded in R^m.
Algorithm for estimating the elastic principal manifold
The method estimates elastic principal manifolds by progressively softening an elastic net initialized on a principal-component manifold. It extends principal curves to branched principal graphs and uses pluriharmonic embeddings as ideal objects penalizing nonlinear deviations.
- Algorithm for estimating the elastic principal manifold: The algorithm initializes elastic-net nodes on the manifold spanned by the leading principal components, then repeatedly optimizes the graph while decreasing softening parameters across predefined epochs.Each epoch updates the elastic moduli before graph optimization; the procedure repeats through all specified epochs.
- Algorithm for estimating the elastic principal manifold: Stretching and bending moduli control edge-length and rib-bending penalties, and may be uniform or adapted across different graph regions.At the final softening stage, stretching coefficients can be set to zero with little effect on the manifold configuration.
- PLURIHARMONIC GRAPHS AS IDEAL APPROXIMATORS: Principal graphs generalize principal curves by adding branching points, enabling principal objects to represent branched data distributions.The branching-point penalty measures deviation from ideal configurations such as ends, lines, corners, T-shapes, Y-shapes, and X-shapes.
- PLURIHARMONIC GRAPHS AS IDEAL APPROXIMATORS: For a k-star, the nonlinearity penalty is zero exactly when the central node equals the mean of its neighbors, making ideal primitive embeddings harmonic on the graph.Such embeddings are called pluriharmonic when the mean-value condition holds for the relevant stars.
GRAPH GRAMMARS AND THREE TYPES OF COMPLEXITY FOR PRINCIPAL GRAPHS
Principal graphs are data approximators with controllable geometric, structural, and construction complexity. Graph grammars construct them through constrained candidate transformations, selecting embeddings that minimize elastic energy until no permissible transformation remains or the construction limit is reached.
- GRAPH GRAMMARS AND THREE TYPES OF COMPLEXITY FOR PRINCIPAL GRAPHS: Principal-graph complexity has geometric, structural, and construction components: deviation from an ideal graph, counts of structural elements, and grammar steps required for construction.Geometric complexity is measured by elastic energy; structural complexity depends on vertices, edges, and k-stars, while construction complexity counts elementary transformations.
- GRAPH GRAMMARS AND THREE TYPES OF COMPLEXITY FOR PRINCIPAL GRAPHS: Graph grammars encode elementary transformations as production rules A → B that replace one elastic-graph substructure with another.A rule removes a copy of A and its incident edges before inserting B.
- GRAPH GRAMMARS AND THREE TYPES OF COMPLEXITY FOR PRINCIPAL GRAPHS: Construction iterates candidate selection and substitution until permissible transformations are exhausted or a predefined construction-complexity limit is exceeded.The graph is initialized with two vertices connected by an edge, then repeatedly replaced by the selected optimal candidate.
- GRAPH GRAMMARS AND THREE TYPES OF COMPLEXITY FOR PRINCIPAL GRAPHS: The algorithm applies every grammar operation, filters candidates exceeding the structural-complexity ceiling, and optimizes each permissible embedding.At each iteration, the candidate with the minimal elastic functional is selected as Gopt.