Pattern Theory - Algebraic Foundations

Algebraic Foundations

We begin with an example to motivate the algebraic definitions that follow.

Example 1 Grammar

If we want to represent language patterns, the most immediate candidate for primitives might be words. However, such phrases as “in order to” immediately indicate the inappropriateness of words as atoms. In searching for other primitives, we might try the rules of grammar. We can represent grammars as Finite State Automata or Context-Free Grammars. Below is a sample Finite State grammar automaton.

The following phrases are generated from a few simple rules of the automaton and programming code in pattern theory:

the boy who owned the small cottage went to the deep forest

the prince walked to the lake

the girl walked to the lake and the princess went to the lake

the pretty prince walked to the dark forest

To create such sentences, rewriting rules in Finite State Automata act as "generators" to create the sentences as follows: if a machine starts in state 1, it goes to state 2 and writes the word “the”. From state 2, it writes one of 4 words: prince, boy, princess, girl. Such a simplistic automaton occasionally generates more awkward sentences

the evil evil prince walked to the lake

the prince walked to the dark forest and the prince walked to a forest and the princess who lived in some big small big cottage who owned the small big small house went to a forest

From the finite state diagram we can infer the following generators (right) that creates the signal. A generator is a 4-tuple: current state, next state, word written, probability of written word when there are multiple choices.

Imagine that a "configuration" of generators are strung together linearly so its output forms a sentence, so each generator "bonds" to the generators before and after it. Denote these bonds as 1a,1b,2a,2b,…12a,12b. Each numerical label corresponds to the automaton's state and each letter "a" and "b" corresponds to the inbound and outbound bonds. Then the following bond table (left) is equivalent to the automaton diagram. For the sake of simplicity, only half of the bond table is shown -- the table is actually symmetric.

As one can tell from this example, and typical of signals we study, identifying the primitives and bond tables requires some thought. The example highlights another important fact not readily apparent in other signals problems: that a configuration is not the signal we observe; rather, we observe its image as a sentence. Herein lies a significant justification for distinguishing an observable from a non-observable construct. Additionally, it gives us an algebraic structure to associate our Hidden Markov Models with. In sensory examples such as the vision example below, the hidden configurations and observed images are much more similar, and such a distinction may not seem justified. Fortunately, we have the Grammar example to remind us of this distinction.

Motivated by the example, we have the following definitions:

1. A generator, drawn as

is the primitive of Pattern Theory that generates the observed signal. Structurally, it is a value with interfaces, called bonds, which connects the 's to form a signal generator. 2 neighboring generators are connected when their bond values are the same. Similarity self-maps s: G -> G express the invariances of the world we are looking at, such as rigid body transformations, or scaling.

2. Bonds glue generators into a configuration, c, which creates the signal against a backdrop Σ, with global features described locally by a bond coupling table called . The boolean function is the principal component of the regularity 4-tuple , which is defined as

seems to capture the notion of allowable generator neighbors. That is, Regularity is the law of the stimulus domain defining, via a bond table, what neighbors are acceptable for a generator. It is the laws of the stimulus domain. Later, we will relax regularity from a boolean function to a probability value, it would capture what stimulus neighbors are probable.

Σ is the physical arrangement of the generators. In vision, it could be a 2-dimensional lattice. In language, it is a linear arrangement.

3. An image (C mod R) captures the notion of an observed Configuration, as opposed to one which exists independently from any perceptual apparatus. Images are configurations distinguished only by their external bonds, inheriting the configuration’s composition and similarities transformations. Formally, images are equivalence classes partitioned by an Identification Rule "~" with 3 properties:

1. ext(c) = ext(c') whenever c~c'
2. sc~sc' whenever c~c'
3. sigma(c1,c2) ~ sigma(c1',c2') whenever c1~c1', c2~c2' are all regular.

A configuration corresponding to a physical stimulus may have many images, corresponding to many observer perception's identification rule.

4. A pattern is the repeatable components of an image, defined as the S-invariant subset of an image. Similarities are reference transformations we use to define patterns, e.g. rigid body transformations. At first glance, this definition seems suited for only texture patterns where the minimal sub-image is repeated over and over again. If we were to view an image of an object such as a dog, its is not repeated, yet seem like it seems familiar and should be a pattern. (Help needed here).

5. A deformation is a transformation of the original image that accounts for the noise in the environment and error in the perceptual apparatus. Grenander identifies 4 types of deformations: noise and blur, multi-scale superposition, domain warping, and interruptions.

Example 2 Directed boundary

With the benefit of being given generators and complete bond tables, a difficult part of pattern analysis is done. In tackling a new class of signals and features, the task of devising the generators and bond table is much more difficult

Again, just as in grammars, identifying the generators and bond tables require some thought. Just as subtle is the fact that a configuration is not the signal we observe. Rather, we observe its image as silhouette projections of the identification rule.