Local-to-Global Methods for Topological Data
Analysis
Brad Nelson
Institute for Computational and Mathematical Engineering
Stanford University
AI-at-SLAC Seminar
October 1, 2018

Acknowledgments

The first half of this talk is intended to be an introduction to TDA, andis not original work (aside from defects). Several review papers now exist
that cover the material from various perspectives including (but notlimited to) [1, 2, 3].
Some of the examples in the first section are based on work with Rahul
Sarkar (Stanford ICME)The second half of this talk is work with/supervised by my advisor,
Gunnar Carlsson (Stanford Mathematics/Ayasdi)

2

Outline

Introduction to Topological Data Analysis
Persistent Homology
Topological Modeling
A Klein Bottle For Image Patches
Multi-Scale/Fiberwise ModelingFiber Bundles
Higher-Dimensional Images

3Outline

Introduction to Topological Data Analysis
Persistent Homology
Topological Modeling
A Klein Bottle For Image Patches
Multi-Scale/Fiberwise ModelingFiber Bundles
Higher-Dimensional Images

Introduction to Topological Data Analysis

4

“Data has shape, and shape has meaning”
Gunnar Carlsson

Introduction to Topological Data Analysis

5What do you see?

Using Topological Data Analysis is one way to get a computer to agreewith you.
Introduction to Topological Data Analysis

6What is Topology?

The study of deformation invariants of spaces.
In topological data analysis, we often think
Open Set ↔ Similarity Neighborhood
A similarity can be as strong as a metric, or as weak as an equivalence
relation.

Introduction to Topological Data Analysis

7

A Bird’s Eye View of Algebraic Topology

I

Study topological spaces using algebraic objects (groups, rings,
modules, vector spaces)– Example: Fundamental Group– Example: Homology

I

Primarily interested in topological invariants

I

Interested in functors– Deforming or continuously modifying a space doesn’t change result– Maps between spaces become maps between algebraic objects

Algebra = Computable

Introduction to Topological Data Analysis

8Simplicial Complexes

Question: How to encode a topological space on a computer?

(One) Answer: A simplicial complex

Introduction to Topological Data Analysis

9Simplicial Complexes - I
Key: Blue denotes Contractible, Red denotes a hole
2
3

0

1

Simplicial complexes are one way to generalize graphs.
Let X be a simplicial complex. Then X has data:
I a vertex set {v0 , . . . , vn }I a collection of simplices on the vertex set– a k-simplex σ spans k + 1 vertices and is denoted σ = (vi0 , . . . , vik )Example: An undirected graph G(V, E) (with no self edges) is a
simplicial complex. V is the vertex set, and E is a set of 1-simplices
Introduction to Topological Data Analysis

10Simplicial Complexes - II
2

0

3

1

Let Xk denote the set of k-simplices in X.
X0 = {(0), (1), (2), (3)}X1 = {(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)}
X2 = {(0, 1, 2)}
A face of a simplex σ is a simplex in the boundary ∂σ that is one
dimension smaller (remove a single vertex from σ).
Introduction to Topological Data Analysis

11Homology

Now we want a way to say something about the topology of the space.
2

3
'

0

1

One way to do this is to use homology.

Introduction to Topological Data Analysis

12Homology - I
A chain complex is a sequence of vector spaces with boundary operators
∂k+1

∂

k
→ Ck+1 −−−→ Ck −→Ck−1 → . . .

where ∂k ◦ ∂k+1 = 0.
One way to get a chain complex is to start with a simplicial complex X
and a field F . Recall
Xk = {k-simplices in X}
And letCk = Free vector space over Xk(Free refers to a vector space with basis given by the elements of Xk ).
The boundary operator ∂k will send a k-simplex to a F -linear
combination of its faces.
Example: The incidence matrix of a graph G is ∂1
Introduction to Topological Data Analysis

13Homology - II
Specifically, let (v0 , . . . vk ) be a k-simplex, then α(v0 , . . . , vk ) ∈ Ck ,where α ∈ F . Then∂k α(v0 , . . . , vk ) = αkX(−1)i (v0 , . . . , v̂i , . . . , vk )i=0

where v̂i indicates we have the face where vi is not present.
If k = 0, then ∂0 (v0 ) = 0.
∂()=( )−( )One can verify that ∂k ∂k+1 = 0. How?
To go from a k-simplex to a (k − 2)-simplex, we remove two vertices. We
can do this in two orders, each of which produces the opposite sign.
Introduction to Topological Data Analysis

14

Homology - III
The property ∂k ∂k+1 = 0 meansker(∂k ) ⊆ img(∂k+1 )In Ck , we call ker(∂k ) ”cycles”, and img(∂k+1 ) ”boundaries”. Note thatthese are both vector sub-spaces of Ck .

The perimeter of the triangle is always a cycle.
However, only on the left it is also a boundary.
The picture suggests that cycles that aren’t boundaries are topologicallymeaningful.
Introduction to Topological Data Analysis

15

Homology - IV
Mathematically, we have a way of describing cycles that aren’tboundaries using a quotient vector space. Define
Hk (X) = ker(∂k )/ img(∂k+1 )the dimension of Hk is also known as the kth betti number βk (X).

(
Hk (X) =

F
0

k=0
k=1

(
F
Hk (X) =
F

k=0
k=1

dim(H0 (X)) is number of connected components of X
dim(H1 (X)) is number of ”loops” in X
I dim(Hk (X)) is number of k-dimensional ”voids” in X
I

I

Introduction to Topological Data Analysis

16Persistent Homology - I

Often in applications, we don’t like to choose parameters.
If there’s a single parameter we vary, this gives rise to a filtered space
Xt = · · · ⊆ Xt− ⊆ Xt ⊆ Xt+ ⊆ . . .
The parameter can be anything - height, curvature, distance - anyreal-valued function on data.
Persistent Homology P H(Xt ) tracks the birth and death of homology
throughout this filtration, as the space changes.
This is one way topologists can tell coffee mugs from doughnuts.

Introduction to Topological Data Analysis

17Persistent Homology - II
A filtration Xt produces a Persistence Barcode.
t=0
t=1
t=2
t=3
⊆

⊆

⊆

H0 (Xt )H1 (Xt )H0 (Xt ) F 3

F2

F

F

H1 (Xt ) 0

0

F

0

Top: Filtration. Middle: Barcode. Bottom: Homology vector spaces.
Introduction to Topological Data Analysis

18Persistent Homology - III
The information in a barcode is a set of birth-death pairs.
H0 (Xt )H1 (Xt )Pairs = (0, 1), (0, 2), (0, ∞), (2, 3)
We can also encode this information in a Persistence Diagram.

death

∞

birth
Introduction to Topological Data Analysis

19Vietoris-Rips Filtrations - I

One easy filtration to define is the Vietoris-Rips Filtration.
1. Start with a finite dimensional vector space on n points.
This is the vertex set.
2. At time r, we put an edge between v, w ∈ V if d(v, w) ≤ r
3. At time r, we have a k-simplex (v0 , . . . vk ), if the vertices form a(k + 1)-clique.

Introduction to Topological Data Analysis

20Vietoris-Rips Filtrations - II

Left: Point Cloud
Right: Persistence Diagram for Vietoris-Rips Filtration

Introduction to Topological Data Analysis

21

Image-Based Filtrations - I

One way to define a filtration on a (gray-scale) image is the following:
Let f (p) denote the (gray-scale) intensity at a pixel p.
1. Make the vertex set the set of pixels in the image
2. A pixel p is in the filtration at time t if f (p) ≤ t
3. Each pixel in the filtration connects to neighbors that are also in thefiltration.
This is an example of a sub-levelset filtration.

Introduction to Topological Data Analysis

22

Image-Based Filtrations - II⇒⇒

Persistence diagrams from Sipi texture rotation dataset.
Joint work with Rahul Sarkar.
Introduction to Topological Data Analysis

23

Featurization - I

Persistence diagrams/barcodes are not immediately useful for machinelearning. We face the following challenges when comparing two diagrams:
I

The number of birth-death pairs may differ between diagrams

I

There’s not a natural vector-space structure (can’t throw into neuralnet, SVM, regression, etc.)

There have been a variety of solutions proposed:
I

Polynomial featurization [4]I

Persistence Images [5]Persistence Landscapes [6]I ...
IIntroduction to Topological Data Analysis

24

Featurization - II
Polynomial featurization[4]. For each homology dimension:
1. Transform pairs (bi , di ) 7→ (mi , `i ), wheremi = (bi + di )/2`i = di − bi
2. Evaluate a polynomial function of these pairs
pα ({(mi , `i )}) =

X

1 X
mki 1 `ki 2
αk1 ,k2ni
k1 ,k2where n is the number of pairs (note these are like moments ofpersistence diagrams).
Do this for a few polynomials, and you now have several real numbersthat are a function of a barcode.
I Same number of features, no matter how many birth-death pairs
I Naturally lives in Rk (k is number of polynomials).
Introduction to Topological Data Analysis

25

Featurization - III
Two polynomial features on Sipi texture recognition data.

Horizontal - 1st mixed moment in H0 .
Vertical - 1st mixed moment in H1 .
Joint work with Rahul Sarkar.
Introduction to Topological Data Analysis

26

More Applications

Ingredients: Data + Filtration (+ Featurization + ML)
I Materials Discovery - Hiraoka [5]– Use of filtrations similar to the one presented for images
I

Drug Discovery - G. Wei [7]– Molecules are treated as topological spaces– Filtrations similar to Rips construction

I

Shape Classification [8]– Shapes treated as topological spaces– Filtrations based on coordinate axis, curvature, etc.

(This is not a complete list, even for applications described.)

Introduction to Topological Data Analysis

27

Outline

Introduction to Topological Data Analysis
Persistent Homology
Topological Modeling
A Klein Bottle For Image Patches
Multi-Scale/Fiberwise ModelingFiber Bundles
Higher-Dimensional Images

Topological Modeling28

What is Topological Modeling?

We’re looking for a topological space that lies near sampled data.
Structures of interest:
I

Parameterization of the space (strong result)I

Clusters, flares

I

Maps to other spaces

Examples:I Models of Image Patches (this talk)I

Dynamical systems [9]Topological Modeling29

What is an Image Patch?

Image from van Hateren Natural Images Database [12]II

A d × d pixel block of a natural image
This talk: black & white images– Pixel values measure light intensity

I

We’re interested in “high contrast” image patches

Topological Modeling30

Why Study Image Patches?

Natural images are complex. Patches are (relatively) simple.
A sparse, rough and incomplete picture:
I Image Compression, Harmonic Analysis– Ridgelets, Curvelets, etc. [10]I

Image denoising/interpolation [11]I

Vision - understand the visual cortex [12, 13]Topological Modeling31

Image Patches in TDA

Circles and Klein Bottles
I Carlsson & de Silva (2004) use as an example in witness complex
construction. [14]– 3 circle model for a dense region of 3 × 3 patches
I

Carlsson et al. (2008) formulate Klein bottle model. [15]– Showed that a dense region of 3 × 3 patches lies near a Klein bottle

I

Adams & Carlsson (2009) - range images primary circle [16]Applications:
I

Compression scheme by Maleki, Shahram, Carlsson (2008):
BiWedgelets / Kleinlets [17]I

Perea & Carlsson (2014) - rotation-invariant pattern recognition
using Klein bottle [18]Topological Modeling32

What’s New?

Contributions in this talk:Fiber bundle construction for the image patch Klein bottle
I generalization of this construction to higher dimensional data
I

Topological Modeling33

Whence the Klein Bottle?

???

Klein Bottle artist: Ron Estrin
Topological Modeling34

Our Viewpoint

I

Image patches are functions (intensity) on a d × d grid

I

Image patches are a discretization of a continuous phenomenonf (x)Topological Modelingf (xi )

35

Obtaining Patches

1. Randomly select 5000 patches fromimage
2. Take log intensities of patches
3. mean-center patches
4. take top 20% by contrast norm
5. normalize by contrast norm
Procedure from Lee, Pedersen, Mumford (2003) [13] applied to van
Hateren dataset [12]Topological Modeling36EdgesOur model for “high-contrast” image patches is based on the observationthat patches that look like edges are common.

Example image patches from the van Hateren data set [12]Topological Modeling37

Sources of Variation
Two sources of variation in edges:
I

Orientation of edges (primary circle)

I

Type of edge (secondary circles)

Example image patches from the van Hateren data set [12]Topological Modeling38

Odd Functions

Odd functions capture the behavior of transitions from one intensity toanother

Topological Modeling39

Even Functions

Even functions capture the behavior of lines

Topological Modeling40

Combined Functions

Edges can also be a combination of even and odd functions+=

Generally, a sampled patch will have both an even and odd component.

Topological Modeling41

Density & Topology

Even though we’ve already restricted ourselves to “high contrast” image
patches, samples will eventually fill in the space.
We’re interested in modeling “high-density” subspaces.
I

Compute density estimator at each sample (using knn)

I

Filter data to contain top p% by density

I

compute persistent homologyIrelax the density threshold and repeat

Topological Modeling42

Circle of Odd Functions
The first topological feature to be computed in the 3 × 3 image patch
data set was a circle of odd functions [14]. This is the “most dense”
portion of the data.

(This is the “Primary Circle” [14])Topological Modeling43

Mixing Even and Odd
Other features that appear as the density threshold is relaxed are circles
through even and odd functions at a fixed orientation.

(These are “Secondary Circles” [14])Topological Modeling44

Circle of Even Functions
In larger patch sizes (4 × 4 and larger), you can also find patches thatlive on a circle of even functions.

Note that one rotation in this circle is half a rotation in angle.
Topological Modeling45

Identification
The Klein bottle can be obtained by making an identification on thesquare.

0

φ

π
0
θ
2π

Topological Modeling46

Klein Bottle Identification

Green: primary circle, Blue: secondary circles
Topological Modeling47

Outline

Introduction to Topological Data Analysis
Persistent Homology
Topological Modeling
A Klein Bottle For Image Patches
Multi-Scale/Fiberwise ModelingFiber Bundles
Higher-Dimensional Images

Multi-Scale/Fiberwise Modeling48

How to Generalize?

Finding the Klein bottle in image patches took some time.
I

How can this be turned into a general process?

I

What were the important ingredients?

Multi-Scale/Fiberwise Modeling49How to Generalize?

Finding the Klein bottle in image patches took some time.
I

How can this be turned into a general process?

I

What were the important ingredients?

Some (possible) answers:
I Find easy (simple) structure first (circle of edges).
– Build on this to add complexity
I

One important ingredient was an orientation map

We’re going to focus on leveraging maps to learn about spaces

Multi-Scale/Fiberwise Modeling49

Maps and Fibers
A map is a continuous function. Let p : X → B be a map.
A fiber of the map is the inverse image of a point b ∈ B, p−1 (b) ⊆ X.

X
p
B

p

p−1
b

Example: X = S 1 , B = S 1 , p : θ 7→ 2θ
p−1 (θ) = { θ2 , θ2 + π}

Multi-Scale/Fiberwise Modeling50

Fiber Bundles
A fiber bundle is a map p : X → B, where inverse images look locallylike a product of an open set in B with a space F .1

X
p

p

p−1

B
Example: X = S 1 , B = S 1 , p : θ 7→ 2θ
p−1 (θ) = { θ2 , θ2 + π}, F is a two-point space
F is called the fiber, B is called the base space, and X is called the total
space.
1 This isn’t the full definition of a fiber bundle
Multi-Scale/Fiberwise Modeling51

Fiber Bundles - II

Examples:I B = S 1 , F = [−1, 1]– Cylinder (trivial)– Möbius Band (twisted)I

B = S1, F = S1
– Torus (trivial)– Klein bottle (twisted)

Multi-Scale/Fiberwise Modeling52

Image Patches Revisited - I
A circle of edges at various orientations was the first discovery.

The second discoveries were circles of edges at a fixed orientation.
Idea: an orientation map can reveal a fiber bundle structure.
Multi-Scale/Fiberwise Modeling53

Orientation Estimation - Harris Matrix [19]hI12 (x) =

k k−1
X
X
1
(xi,j − xi+1,j )2k(k − 1) j=1 i=1I22 (p) =

k k−1
X
X
1
(xi,j − xi,j+1 )2k(k − 1) i=1 j=1

k−1
X k−1
X
1
(xi,j − xi,j+1 )(xi,j − xi+1,j )2(k − 1) i=1 j=1
 2

I
I12
vφ (x) = MaxEigVec 1
2
I12 I2I12 (x) =Multi-Scale/Fiberwise ModelingI

Sign ambiguity ineigenvector naturally
identifies antipodal points
on circle: vφ ∼ −vφ

I(S 1 / ∼) ' RP 1 ' S 1

I

map is similar to: φ 7→ 2φ

54

Image Patches Revisited - II
Point cloud is a fiber of the Harris Map (7 × 7 patches). Inverse image ofan open set covering about 10% of RP 1

Multi-Scale/Fiberwise Modeling55

Image Patches Revisited - III

Vertical - Fibers. Horizontal - Section of Base SpaceMulti-Scale/Fiberwise Modeling56

3D Image Patches
A similar, but more complex, set of data comes from 3-dimensional
images.
I

pixels ⇒ voxels

I

patches ⇒ d × d × d blocks of voxels

One source of 3D-images: MRI [20]Multi-Scale/Fiberwise Modeling57

3D Orientations

We used an open-source MRI dataset (OASIS)[20] to use for sampling
I

Initial investigations revealed a sphere of odd edges.

I

We then decided to investigate fibers of the orientation map.

I

Note that in 3 dimensions, the space of orientations is(S 2 / ∼) = RP 2

I

Harris map generalizes to higher dimensions– in d dimensions - eigenvector of d × d matrix– finite differences in each dimension

Multi-Scale/Fiberwise Modeling58

3D Orientation Fibers
Point cloud is a fiber of the Harris Map (7 × 7 × 7 cubes).
Inverse image of an open set in RP 2 .

Multi-Scale/Fiberwise Modeling59

Stitching Everything Together

We’ve seen some evidence that fibers of the orientation map again look
like circles.
What is the topological model for this?
I

A fiber bundle with fiber S 1 and base space RP 2

I

As in the Klein bottle, there are twists

I

The Klein bottle is a subspace (diameters)

Ongoing work: We’re investigating ways to use structure to speed up
computations.

Multi-Scale/Fiberwise Modeling60

Conclusion

Overview of Persistent Homology, some applications
I Topological modeling of dataI

– Klein bottle in image patches
I

Using maps and fibers to investigate spaces– Proposed model for 3D image patches

What’s Next?
I
I(ongoing) Computational framework that exploits structure of maps
Applications that use structure of 3D patch space– Can we compress 3D images?
– Can we understand 3D CNNs?

I

Interested in finding other examples of fiber bundles in data

Multi-Scale/Fiberwise Modeling61

References I

G. Carlsson. Topology and Data. Bulletin of the AMS. 46(2). 2009.
R. Ghrist. Homological Algebra and Data. Preprint:
https://www.math.upenn.edu/ ghrist/preprints/HAD.pdf 2017.
N. Otter et. al. A roadmap for the computation of persistent homology. EPJ
Data Science 6(1). 2017.
A. Adcock, E. Carlsson, G. Carlsson. The ring of algebraic functions on
persistence bar codes. Homology, Homotopy and Applications. 18(1) 2016.
I. Obayashi and Y. Hiraoka. Persistence Diagrams with Linear Machine Learning
Models. arXiv:1706.10082 2017.
P. Bubenik. Statistical Topological Data Analysis using Persistence Landscapes.
JMLR 16 pp. 77-102. 2015.
Z. Cang and G. Wei. TopologyNet: Topology based deep convolutional andmulti-task neural networks for biomolecular property predictions. PLOS
Computational Biology. 13(7). 2017.

Multi-Scale/Fiberwise Modeling62

References II

F. Chazal et. al. Gromov-Hausdorff Stable Signatures for Shapes using
Persistence. Computer Graphics Forum 28. pp. 13931403. 2009.
J. Perea and J. Harer. Sliding Windows and Persistence: An Application ofTopological Methods to Signal Analysis. FOCM 15(3). pp. 799-838. 2015.
D.L. Donoho, A.G. Flesia, Can recent innovations in harmonic analysis explain
key findings in natural image statistics?. Network: computation in neuralsystems, 12(3), pp.371-393. 2001.
S. Osher, Z. Shi, and W. Zhu. Low Dimensional Manifold Model for Image
Processing. Technical Report UCLA CAM Report 16-04, 2016.
J.H. van Hateren and A. van der Schaaf. Independent component filters ofnatural images compared with simple cells in primary visual cortex. Proc. R. Soc.
Lond., B265:359366, 1998.
A.B. Lee, K.S. Pedersen, and D.B. Mumford. The nonlinear statistics ofhigh-contrast patches in natural images. International Journal of Computer
Vision, 54:83103, 2003.

Multi-Scale/Fiberwise Modeling63

References III
V. de Silva, G. Carlsson. Topological estimation using witness complexes.
Eurographics Symposium on Point-Based Graphics. 2004.
G. Carlsson, T. Ishkhanov, V. de Silva, and A. Zomorodian. On the local
behavior of spaces of natural images. International Journal of Computer Vision,76(1):112, 2008.
H. Adams, G. Carlsson. On the nonlinear statistics of range image patches. SIAM
J. Imaging Sciences, 2(1):110117, 2009.
A. Maleki, M. Shahram, G. Carlsson A Near Optimal Coder For Image Geometry
With Adaptive Partitioning. 15th IEEE International Conference on Image
Processing, 2008.
J. Perea, G. Carlsson. A klein-bottle-based dictionary for texture representation.
International Journal of Computer Vision, 107(1):7597, 2014.
C. Harris, M. Stephens. A combined corner and edge detector. 1988.
Marcus, D. S. et al. (2010). Open Access Series of Imaging Studies (OASIS):
Longitudinal MRI Data in Nondemented and Demented Older Adults. Journal of
cognitive neuroscience 22.12: 26772684.
Multi-Scale/Fiberwise Modeling64

Texture Recognition

J. Perea, G. Carlsson “A Klein-Bottle-Based Dictionary for Texture
Representation” (2014)
Multi-Scale/Fiberwise Modeling65

Compression

A. Maleki, M. Shahram, G. Carlsson “A Near Optimal Coder For Image
Geometry With Adaptive Partitioning” (2008)
Multi-Scale/Fiberwise Modeling66