Topology for data science

TOPOLOGY FOR DATA
SCIENCE: MORSETHEORY
AND APPLICATION
Colleen M. Farrelly

Level Sets in Everyday Life
• Front maps partition weather patterns by areas
of the same pressure (isobars).
• Elevation maps partition land areas by height
above/below sea level.

Level Sets of Functions
• Continuous functions have defined
local and global peaks, valleys, and
passes.
• Define height “slices” to partition
function.
• Akin to a cheese grater scraping off
layers of a cheese block.
• In the example, the blue lines slice a
sine wave into pieces of similar height.
• Function on discrete date (points) can
be partitioned into level sets, too.

Level Sets to Critical Points
• Continuous functions:
• Can be decomposed with level sets.
• Contain local optima (critical points).
• Maxima (peaks)
• Minima (valleys)
• Saddle points (inflections/height change)
• Continuous functions can live in
higher-dimensional spaces with more
complicated critical points.

Degenerate and Non-DegenerateOptima
• Morse functions have stable and isolated local
optima (non-degenerate critical points).
• Related to 1st and 2nd derivatives of function.
• Don’t change with small shifts to the function.
• Technically, related to Hessian being
defined/undefined at the critical point.
• Reflects neighborhood behavior around the
critical point.
1. Non-degenerate critical points have defined
behavior in the critical point’s neighborhood.
2. Degenerate points have undefined behavior
near the critical point.
f’=0
f’=0
f’’(x)<0
f’’(x)>0
f’’(x)=0

Morse Function Definition
1. None of the function’s critical points
are degenerate.
2. None of the critical points share the
same value.
• These properties allow a map between a
function’s critical point values to a space
of level sets (left).
• All critical values map to values in the level
set collection.
• Function can be plotted nicely to
summarize its peaks, valleys, and in-
between spaces.
1
0
-1
Level Set
Critical
Point
Map

Discrete Extensions to DataAnalysis
• Morse functions can be extended to
discrete spaces.
• Data lives in a discrete point cloud.
• Topological spaces, called simplicial
complexes, can be built from these.
• Several algorithms exist to connect
points to each other via shared
neighborhoods.
• Vietoris-Rips complexes are built from
connecting points with d distance from
each other.
• Any metric distance can be used.
• Process turns data into a topological space
upon which a Morse function can be
defined.
2-d neighborhoods are
defined by Euclidean
distance.
Points within a given
circle are mutually
connected, forming a
simplex.
Example
simplicial
complex

Morse-Smale Clustering
• Partition space between minima and
maxima of function by flow.
• Example:
• The truncated sine wave shown has 2
minima and 2 maxima shown (dots).
• Pieces between local minima and maxima
define regions of the function.
1. Yellow
2. Blue
3. Red
• Higher-dimensional spaces can be
simplified by this partitioning.
• Can be used to cluster data.
• Subgroups can then be compared across
characteristics using statistical tests (t-
test, Chi square…).
Cluster 1
Cluster 2
Cluster 3

Intuitive 2-Dimensional Example
• Imagine a soccer player kicking a ball on the ground of a hilly field.
• The high and low points determine where the ball will come to rest.
• These paths of the ball define which parts of the field share common hills and
valleys.
• These paths are actually gradient paths defined by height on the field’s topological
space.
• The spaces they define are the Morse-Smale complex of the field, partitioning it
into different regions (clusters).
Algorithms that compute
Morse-Smale complexes
typically follow this intuition.

Morse-Smale Regression
• Type of piece-wise regression.
• Fit regression model to partitions
found by Morse-Smale
decompositions of a space given a
Morse function.
• Regression models include:
• Linear and generalized linear models
• Machine learning models
• Random forest
• Elastic net
• Boosted regression
• Neural/deep networks
• Can examine group-wise differences
in regression models.
Example: 2 groups,
3 predictors

Reeb Graphs
• Track evolution of level sets
through critical points of a
Morse function.
• Partition space according to a
function (left by height).
• Plot critical points entering
model.
• Track until they are subsumed
into another partition.
• Useful in image analytics and
shape comparison.

Persistent Homology
• Filtration of simplicial complexes built from
data
• Iterative changing of lens with which to examine
data (neighborhood size…)
• Topological features (critical points) appear and
disappear as the lens changes.
• Creates a nested sequence of features with
underlying algebraic properties, called a homology
sequence:
Hom1⊂Hom2⊂Hom3⊂Hom4
• Persistence gives length of feature existence in
homology sequence.
• Many plots (left) exist to summarize this
information, and special statistical tools can
compare datasets/topological spaces.
• Filtration defines an MRI-type examination of
data’s topological characteristics and evolution
of critical points.
0 2 4 6 8 10
0246810
Birth
Death
0 2 4 6 8 10
time

MapperAlgorithm
• Generalizes Reeb graphs to track
connected components through
covers/nerves of a space with a defined
Morse function.
• Basic steps:
• Define distance metric on data
• Define filtration function (Morse function)
• Linear, density-based, curvature-based…
• Slice multidimensional dataset with that
function
• Examine function behavior across slice (level
set)
• Cluster by connected components of cover
• Plot clusters by overlap of points across
covers
Response
gradations
Outliers

Multiscale Mapper Methods
• Mapper clusters change with
parameter scale change
(unstable solutions).
• Filtrations at multiple
resolution settings to create
stability (see above example).
• Creates hierarchy of Reeb
graphs (mapper clusters) from
each slice.
• Analyze across slices to gain
deeper insight underlying data
structures.
1st Scale 2nd Scale
Scale
change
Psychometric
test example:
verbal vs.
math ability

Conclusion
• Morse functions underlie several methods used in modern data analysis.
• Understanding the theory and application can facilitate use on new data
problems, as well as development of new tools based on these methods.
• Combined with statistics and machine learning, these methods can create power
analytics pipelines yielding more insight than individual

Good References
• Carlsson,G. (2009).Topology and data. Bulletin of the American MathematicalSociety,
46(2), 255-308.
• Gerber, S., Rübel, O., Bremer, P.T., Pascucci,V., &Whitaker, R.T. (2013). Morse–smale
regression. Journal of Computational and Graphical Statistics, 22(1), 193-214.
• Edelsbrunner, H., & Harer, J. (2008). Persistent homology-a survey. Contemporary
mathematics, 453, 257-282.
• Forman, R. (2002).A user’s guide to discrete Morse theory. Sém. Lothar. Combin, 48, 35pp.
• Carr, H., Garth, C., &Weinkauf,T. (Eds.). (2017). Topological Methods in Data Analysis and
Visualization IV:Theory, Algorithms, and Applications. Springer.
• Di Fabio, B., & Landi,C. (2016).The edit distance for Reeb graphs of surfaces. Discrete &
Computational Geometry, 55(2), 423-461.

Topology for data science

Recommended

More Related Content

What's hot (20)

Similar to Topology for data science (20)

More from Colleen Farrelly (20)

Recently uploaded (20)

Topology for data science