Sunday, March 31, 2013

Prolegomena to an XML schema for pattern theory



A link to a working draft specification is here:




The pattern theory created by Ulf Grenander is based on mathematical definitions for a set of entities that are used to model and perceive the world: generator, bond, configuration, image, pattern, similarity transformation, deformation, among others.

Here is an example of what a configuration might look like (from Elements of Pattern Theory):

In the XML schema for PTML (Pattern-Theoretic Markup Language), this would be coded as follows:

<config>
<gen id="g1">
   <bond name="W" gref="#" bcxn="E"></bond>
   <bond name="E" gref="#g2" bcxn="W"></bond>
   <bond name="S" gref="#g3" bcxn="N"></bond>
</gen>
<gen id="g2">
   <bond name="W" gref="#g1" bcxn="E"></bond>
   <bond name="N" gref="#" bcxn="S"></bond>
   <bond name="S" gref="#g4" bcxn="N"></bond>
</gen>
<gen id="g3">
   <bond name="N" gref="#g1" bcxn="S"></bond>
   <bond name="E" gref="#g4" bcxn="W"></bond>
</gen>
<gen id="g4">
   <bond name="N" gref="#g2" bcxn="S"></bond>
   <bond name="W" gref="#g3" bcxn="E"></bond>
   <bond name="E" gref="#g5" bcxn="W"></bond>
   <bond name="S" gref="#g6" bcxn="N"></bond>
</gen>
<gen id="g5">
   <bond name="W" gref="#g4" bcxn="E"></bond>
   <bond name="E" gref="#" bcxn="W"></bond>
</gen>
<gen id="g6">
   <bond name="N" gref="#g4" bcxn="S"></bond>
</gen>
</config>


This includes elements config (configuration), gen (generator), bond (bond), a gen attribute id, bond attributes name, gref (generator being linked to), and bcxn (bond connection). (The bond names — or indices — N, S, E, W were chosen to suggest geographical directions.) A gref such as "#g4" is an internal link to a generator within the same configuration. bcxn specifies the bond (by name) within the generator being linked to. A gref="#" indicates an unconnected (external) bond. This is something of an "empty" configuration in that it currently holds no application-dependent content within the bond or gen elements.

Because the config element can have arbitrarily-connected internal links as shown in this example, any graph topology can be modeled, not just tree structures.

Further developments for PTML include:

0. Add syntax for bond domains (bset="set", where set is the name of a set of bond values), bond values (bval="val", where val is an element of bset), bond relations (brel="rel", where rel is the name of a two-argument function taking two bond values and returning TRUE or FALSE), and bond probability distributions (bprob="prob", where prob is the name of a one-argument function that takes the list of bond names from the generator and returns a list of random bond values. (prob is a multivariate probability distribution.)

Example:
<gen bset="MAPDIRECTION" brel="EQUALS" bprob="COINFLIP"
       id="g2">
   <bond name="W" gref="#g1" bcxn="E" bval="HEADS"></bond>
   <bond name="N" gref="#" bcxn="S" bval="TAILS"></bond>
   <bond name="S" gref="#g4" bcxn="N" bval="HEADS"></bond>
</gen>

Note: The probablities introduced by bprob induce a probability model over configrations known as a random field.

0.1. Add an attribute for the gen element, gtype="typeid" and a new element <gtype id="typeid" bset="set" brel="rel" bprob="prob" bsim="sim"> where sim is the name of a similarity group. The gtypes could be collected into another file defs.ptml and referenced by a link element:
<ptml>
<head>
    <link rel="definitions" href="defs.ptml">
</head>
<body>
   <config>
     ...
       <gen gtype="typeid" ...>
     ...
   ...
</body>
</ptml>
(See SVG <defs>, for example.)

1. Add a bdir=["in"|"out"] attribute to bond for where the underlying configuration graph is directed.

2. bcxn could list a set of prioritized options: bcxn="name1,name2,..."

3. Content to include <script>s.

4. Content to include analogs of SVG <filters>s, transforms, ...

5. XML transformation language to capture the other pattern theoretic definitions such as similarity, image, and deformation.
(Example: a PTML → SVG transform)

...

With PTML, one can publish pattern-theoretic objects or store them in XML databases.