Pattern Theory — Basic Neuroscience and Geometry of Neuroscience

This lecture introduces Grenander’s pattern theory. The main references are Grenander’s Elements of Pattern Theory, Grenander and Miller’s Pattern Theory: From Representation to Inference, and Mumford and Desolneux’s Pattern Theory: The Stochastic Analysis of Real-World Signals (full references at the end).

Motivation

The broad motivation is a question: is it possible to use something like the theory of formal languages for vision?

The principle is to determine what the building blocks of images are, and to find the rules by which they are coupled together. Things to account for include

texture;
(types of) randomness;
symmetries;
clustering of elements;
shapes (and variations of shapes);
discretization and approximation;
pattern interference;
etc.

Generators, bonds and configurations

Generator space and symmetries

Definition G15.1 (Generators, similarities and bonds).

The generator space is a space of “building blocks”, or patterns, . It comes with a decomposition into various parts, or sectors, of the generator space.
The similarity group is a group of transformations (bijections preserving the decomposition into the ).
Arity: each has a certain “valence” (arity) , like a node in a graph, which is the number of other elements it can connect to (“bond”). The bond structure of is , .
The bond value space: each bond carries a label .

Both and are preserved by all .

The figure shows a configuration of seven generators . Each line is a bond between two generators, and the small circle on it is the bond couple, where the bond values of the two ends are matched.

Configurations

Configurations are built by gluing generators together according to their bond structure.

Definition G15.2 (Configurations and regularity).

The configuration architecture of a configuration is a graph, the connector graph.
A bond is internal if it is connected to another bond, and external if it is left open.
A truth-valued function on the bond values decides which bonds match: or .
A configuration is locally regular if for all elements and any internal bond between them Over all internal bonds, for all pairs of generators, this says
A configuration is regular if it is locally regular and its connector graph is in some assigned class (lattice, tree, linear, etc.).
The regularity is the data .

Definition G15.3 (Configuration space). The configuration space is the set of all possible regular configurations with given regularity (with the connector graph varying in ). It comes with

a coupling connector ;
the action of the similarities: each maps to itself.

Definition G15.4 (Homomorphisms). Let and be two regularities with the same similarities and the same connection type . A homomorphism is a map with (-equivariant) and .

Images, patterns and templates

Put an equivalence relation on the configuration space , subject to three requirements:

the equivalence relation must be compatible with the -action;
equivalent configurations must have the same external structure (external bonds);
the equivalence preserves coupling connectors.

Definition G15.5 (Images, patterns, templates).

The images are the equivalence classes, .
A pattern is any -invariant subset of .
A pattern family is a partition of into pieces that are unions of -orbits.
A template is a choice of a representative in each -orbit of a pattern.

Dressing everything with probabilities

Grenander had earlier argued the viewpoint that any (algebraic) structure in mathematics can be dressed with probabilities: Ulf Grenander, Probabilities on Algebraic Structures, Dover, 2008 (originally 1963).
In the theory of formal languages and generative grammars it is common to consider probabilistic grammars: Rens Bod, Jennifer Hay, Stefanie Jannedy, Probabilistic Linguistics, MIT Press, 2003.
So consider some kind of statistical physics model for probabilistic patterns and images.

Assigning probabilities

Definition G15.6 (Acceptor function and probability of a configuration). An acceptor function is a function , for instance with an interaction energy. The probability of a configuration is with normalization by the partition function

Another, similar version also puts a probability on the set of generators :

One thing probabilities do is replace rigid regularity by a more general relaxed regularity, by replacing the truth-valued bond value function discussed before by the acceptor function: one uses Rigid regularity is recovered as the limit (the frozen, zero-temperature limit) of the probabilistic model with .

Probabilities of images and conditioning

A subset of images gets the measure

Observe that the probability of a subconfiguration of , conditioned on the rest of , does not depend on the bonds of that are not connected to . Write , and let be the outer boundary of (the generators of bonded to ). Then where the products run over the bonds inside (or ) and the bonds joining it to , and the sum runs over the subconfigurations that can be coupled to in place of . All other terms cancel.

Deformations

Definition G15.7 (Deformations).

are the abstract images (not directly observable).
Deformation mappings are maps to the deformed images.
The deformation mechanism is automorphic if .
More realistically, the are effects like noise, etc., and destroy part of the structure of : heteromorphic deformations.

Deformations can act on , or on , or directly on .

Definition G15.8 (Image restoration problem). Find a mapping such that the target set is “as close as possible” to the abstract images , in an appropriate notion of proximity (metric, topological, measure theoretic).

Definition G15.9 (Pattern recognition problem). Algorithmically find the pattern class (a subset of made of a union of -orbits) to which a given collection of images belongs, when the observed images belong to some deformed set .

The rest of the lecture takes a closer look at the mathematics involved:

probabilistic directed acyclic graphs;
hidden Markov models;
Markov random fields;
canonical representations of pattern theory;
shape analysis.

Probabilistic directed acyclic graphs

For a directed edge of a graph , write for its source and for its target.

Definition G15.10 (Probabilistic directed acyclic graph). Let be a directed acyclic graph.

Each vertex carries a random variable .
All these random variables have the same (finite) state space .
A configuration is a point in , with .
The model is given by the conditional probabilities of a site , conditional on its parents the parent vertices of in the directed structure.

Definition G15.11 (Realization by a directed graph). A random variable has a realization by a directed graph if at each node “parents split sites from descendants”: where is the set of descendants of : the vertices reached from by an oriented path (its children are the with , ).

Proposition G15.12 (Factorization). Random variables with a realization by a PDAG satisfy where .

Proof. By recursively “peeling off leaf nodes”. A leaf has no descendants, so the splitting property says that is independent of all the other variables given its parents, and . Remove the leaves and repeat on the smaller graph. ∎

In the figure, the graph has edges , , , , , . Its leaves are ; removing them leaves , with leaves ; removing those leaves , the edge , with leaf ; and finally .

Example G15.13 (Finite state Markov chains). The simplest case of a PDAG is when the graph is the one-dimensional lattice, : This is equivalent to the splitting property

Example G15.14 (Branching processes on trees).

The probability law for the next generation depends only on the immediately previous one (Markov).
The number of branchings at a site is independent of the number of sites in the same generation.
Nodes are conditionally independent of their non-descendants given their parents.

The tree in the figure is generated by the rules (terminals, non-terminals, production rules, ...), with the nodes of types . Beside generation , counts its non-terminal nodes: of type and of type .

Information on a PDAG

From , the entropy splits as

Hidden Markov models

Definition G15.15 (Hidden Markov model).

There are observed states , each taking possible values.
There are hidden states , each taking possible values.
They satisfy the conditional independence

In the special case where all the transitions are given by the same stochastic matrix and all the transitions by the same stochastic matrix , the HMM is described by the image of a polynomial map bi-homogeneous in the coordinates and , of degree in the (and degree in the ), plus added positivity and normalization conditions (stochastic matrices and probability distributions).

Example G15.16. Take and , so .

The eight terms correspond to the eight hidden sequences : the term for is .

Definition G15.17 (Invariants). The invariants of the HMM are the polynomial functions on that vanish on the image of .

The invariants generate an ideal . For small it can be computed with Gröbner bases; larger cases are computationally hard.

Questions.

Viterbi sequence: find the most likely hidden data given the observed data.
Find all parameter values for a model that result in the same observed distribution.
Find what parameter-independent relations hold between the observed probabilities .

Recent algebro-geometric methods (tropical geometry, etc.) have been developed to approach these problems about HMMs; see Pachter–Sturmfels, Tropical geometry of statistical models, and Drton–Sturmfels–Sullivant, Lectures on Algebraic Statistics.

Formal languages and generative grammars within pattern theory

The case of formal languages and generative grammars can be recovered within pattern theory.

Probabilistic context-free grammars

Definition G15.18 (Probabilistic context-free grammar). A probabilistic context-free grammar is , where

and are disjoint finite sets: the non-terminal and terminal symbols;
is the start symbol;
is a finite rewriting system on , the production rules with and ;
assigns probabilities to the production rules, with the ways to expand the same non-terminal add up to probability one.

Probabilities of parse trees

Let be the family of parse trees for a context-free grammar . If is probabilistic, one can assign probabilities to all the possible parse trees for a given string in the language : The last equality holds because the tree includes the terminals (the labels of its leaves), so .

These probabilities account for the syntactic ambiguities of parse trees in context-free languages.

Subtree independence assumption

Definition G15.19 (Span). A vertex in an oriented rooted planar tree spans a subset of the set of leaves of if is the set of leaves reached by an oriented path in starting at .

Denote by a non-terminal labeling a vertex of a parse tree that spans the substring of the string parsed by . The subtree independence assumption is

;
.

Example G15.20. Take the parse tree with root and children and , where spans and spans :

Then

Sentence probabilities in PCFGs

Theorem G15.21 (Chomsky normal form). Context-free grammars can always be put in Chomsky normal form, where all the production rules are of the form where are non-terminals and is a terminal.

So a parse tree for a CFG in Chomsky normal form has two kinds of nodes: an internal node marked with a non-terminal and one output to a leaf with a terminal , or a node with non-terminal and two outputs with non-terminals and .

Assume the CFG is in Chomsky normal form. Write , and for the non-terminal at a vertex spanning .

Definition G15.22 (Inside and outside probabilities). The inside probabilities are the probability of the string of terminals “inside” (the outputs of) the oriented tree with vertex (root) . The outside probabilities are the probability of everything that is outside the tree with root .

In the figure, the inside probability concerns the inner triangle, the subtree with root over ; the outside probability concerns the rest of the tree with root , over and .

Proposition G15.23 (Recursive formula for inside probabilities).

Proof. Split the tree at the first branching, , as in the figure, and use the chain rule, then the subtree independence assumption: ∎

Training probabilistic context-free grammars

Consider first the simpler case of a Markov chain, with a transition from state to state labeled by . Given a large training corpus, count the number of times the given transition occurs: this is the counting function . Then model the probabilities on the frequencies obtained from these counting functions: A similar procedure exists for hidden Markov models.

In the case of probabilistic context-free grammars, use the training corpus to estimate the probabilities of the production rules, At the internal (hidden) nodes, the counting function is related to probabilities by

Markov random fields

Markov random fields are one of the main probabilistic tools for the configuration spaces of pattern theory. They live on arbitrary non-directed graphs (a special case being lattices).

Definition G15.24 (Markov random field). To each vertex of a graph assign a finite set of random variables , all with the same (finite) state space . Let the neighborhood of be The random variables form a Markov random field if

Example: the Ising model

is the collection of pixels of an image (a real-valued function of two variables).
is a binary image, a black/white approximation of by areas.

Definition G15.25 (Ising model of an image). The energy functional is where the second sum is over nearest neighbors. The probability density is

The probability decomposes into a Gaussian and a discrete part, where is the number of pixels.

In the physical Ising model, is the external magnetic field and are the spin variables.
For image segmentation problems, consider as fixed, and the conditional probability

The temperature controls the behavior:

in the high temperature regime , the probability approaches the uniform probability distribution on the finite set of all possible ;
in the low temperature regime , the probability approaches the delta distribution concentrated on the minimizer of (for fixed ).

Monte Carlo and Metropolis–Hastings type algorithms converge to the minimizer of .

The slides show an example of the segmentation of an image obtained with the Ising model, lowering the temperature from to . The image is a grayscale photograph of a cow standing in front of a tree trunk. A row of six binary images shows the segmentation as the temperature decreases: at first it is mostly salt-and-pepper noise, and by it is a clean black silhouette of the cow and the tree on white.

Potts models

Potts models are a more general example of Markov random fields. The Ising model is used to approximate a -valued image by a -valued . More generally, when a palette of different colors is available, use the energy with the indicator function of the set . The same algorithmic procedure gives the minimizer.

The example on the slides is a satellite image (CNES, the French space agency) of farmland, a patchwork of fields in shades of gray, next to its segmentation using a Potts model (Xavier Descombes), in which each field becomes a region of one flat color from a small palette.

Canonical representations of pattern theory

A canonical representation is a construction of the generator set for a given type of probability model on a graph .

Example G15.26 (Probabilistic directed acyclic graphs). Let be a probabilistic directed acyclic graph. We want Use , and take generators given by with arity , in-bond value and out-bond values . Then when (rigid regularity), or more generally with some acceptor .

Shape analysis

The historical origin of shape analysis is D’Arcy Thompson’s On Growth and Form (1917). The slide reproduces some of his drawings. A fish (Polyprion) is drawn on a square grid, and three related species (Pseudopriacanthus altus, Scorpaena, Antigonia capros) are drawn on deformed versions of the same grid. In another pair, a porcupinefish drawn on a rectangular grid (A) becomes a sunfish (B) when the grid is bent into a fan of curved coordinate lines. Each species is obtained from another by a smooth deformation of the plane.

Shape space

Definition G15.27 (Templates and shapes).

is a template.
The shapes are , with a diffeomorphism of the ambient space.
is the space of diffeomorphisms and the shape space, with the transformations .

The map is many-to-one, so the projection from to requires an optimization over the diffeomorphism group: given a target shape , look for an optimal diffeomorphism with Optimality is measured by a Riemannian metric on , measuring the distance between and the identity.

To achieve an optimal one uses a minimization process, with an error function .

The optimal is computed via the solutions of an ODE: , where with a time-dependent vector field on the ambient space. The time variable gives a continuous deformation from the template to the target. This is an optimal control problem with the control: with and the norm of a Hilbert space of smooth vector fields.

The slides show an example from Trouvé–Younes (Mise en correspondance d’objets déformables): two images to be matched, a blurred white square and a blurred white disk on black, and the deformation obtained between them, drawn as a square grid bent by the diffeomorphism, with the grid lines pulled in toward the center.

More details on shape spaces

These follow Bauer–Bruveris–Michor, Overview of the geometries of shape spaces and diffeomorphism groups.

Definition G15.28 (Spaces of shapes).

A shape is a submanifold of an ambient diffeomorphic to a fixed manifold .
is the space of immersed submanifolds, and the space of embedded submanifolds.
is the space of parameterized immersions, with the action of by changes of parameterization, and an orbifold with singular points.

A Riemannian metric on that is -invariant induces a metric on (and similarly for , with the parameterized embeddings modulo ).

Metrics of this kind come from the ambient space.

Consider the left action of on the parameterized embeddings .
is a Lie group, with Lie algebra , the compactly supported vector fields.
Construct a right invariant metric on .
Then the left action of on induces a metric on such that is a Riemannian submersion.
This measures the cost of deforming a shape in terms of the minimal cost of deforming the ambient space, through the quadratic form for an infinitesimal deformation of , with the infimum over the that agree with on .
This induces a metric on through the metric on induces a metric on invariant under reparameterizations of by , so it descends to a metric on .

Remark. All these spaces are infinite dimensional, so there are many analytic subtleties in dealing with their Riemannian geometry.

Metrics on

To specify a metric it suffices to specify the paths of minimal distance, the geodesics. A geodesic in is a path of diffeomorphisms satisfying a differential equation; its logarithmic derivative is a path of vector fields.

Proposition G15.29 (Geodesic equation). If the metric is specified by the quadratic form for a differential operator , then the geodesic equation is for the momentum , with .

This gives a relation between metrics on and the equations of fluid dynamics (Arnold–Khesin).

Example G15.30 (Geodesic equations on ).

With (just the metric) the geodesic equation is a model of turbulence in fluid dynamics (Burgers).
With the geodesic equation is the Camassa–Holm equation (shallow water waves).
With the geodesic equation is the periodic Hunter–Saxton equation (propagation of waves in nematic liquid crystals).

Definition G15.31 (Sobolev metrics). The Sobolev metric on is with the Fourier transform. For an integer , so .

Theorem G15.32 (Completeness). Let be a compact Riemannian manifold and the Sobolev metric induced on . For , with is geodesically complete.

The last slide shows an example of a geodesic between shapes for the Sobolev metric (Martins Bruveris): a stack of closed outlines of an elongated, fish-like shape, each a step along the geodesic, deforming gradually from the first outline to the last.

References

Ulf Grenander, Elements of Pattern Theory, Johns Hopkins University Press, 1996.
Ulf Grenander, Michael I. Miller, Pattern Theory: From Representation to Inference, Oxford University Press, 2007.
David Mumford, Agnès Desolneux, Pattern Theory: The Stochastic Analysis of Real-World Signals, CRC Press, 2010.
Ulf Grenander, Probabilities on Algebraic Structures, Dover, 2008 (originally 1963).
Rens Bod, Jennifer Hay, Stefanie Jannedy, Probabilistic Linguistics, MIT Press, 2003.
Lior Pachter, Bernd Sturmfels, Tropical geometry of statistical models, Proc. Natl. Acad. Sci. USA 101 (2004), no. 46, 16132–16137.
Mathias Drton, Bernd Sturmfels, Seth Sullivant, Lectures on Algebraic Statistics, Birkhäuser, 2009.
Alain Trouvé, Laurent Younes, Mise en correspondance d’objets déformables, Traitement du Signal 20 (2003), no. 3, 295–302.
Martin Bauer, Martins Bruveris, Peter W. Michor, Overview of the geometries of shape spaces and diffeomorphism groups, J. Math. Imaging Vision 50 (2014), no. 1-2, 60–97.
D’Arcy Wentworth Thompson, On Growth and Form, Cambridge University Press, 1917.

G15 Pattern Theory