The CombinatorialChains.jl Julia library, when complete, will allow for Markov Chain Monte Carlo (MCMC) similation over arbitrary C-Sets. Recall that a C-Set is a copresheaf, which is a functor from some category C to Set.
This is useful because states of a system are isomorphic to C-Sets (or copresheaves) over some choice of schema (which lives in the category C), and while states are usually thought of as instances over some graph-like strucutre, we can in practice generalise this to other types of structures, allowing for abrbitary MCMC simulation.
The MCMC state update is carried out via the double pushout algorithm. Moreover, the schema are built via slice category contructions. As such, concepts of category theory are central to the construction, and indeed the package will rely heavily on other AlgebraicJulia packages once complete (Catlab.jl and CombinatorialSpaces.jl).
Although this machinery is rather heavy for simulating an Ising model, this example serves to demonstrate how a well studied example is implemented within the proposed framework.
The Ising chain example has the following schema:
C-Sets from this schema are our Ising states. The code proceeds as folllows:
- A random state of up/down spins is generated on an n by n lattice.
- A rewrite rule is randomly selected from all possible rewrite rules. These rules are stored as spans L<-I->R, where L is the structure we search for in the graph G, and R is what we replace it with. I is the subgraph with homomorphisms (which we call l and r, respectively) into L and R.
- If a match for the rewrite rule is found in the Ising graph state, the double pushout (DPO) is performed to form the new state (C-set) H. If not, a new rewrite rule is selected until a match is found.
- Next, the rewrite rule is either accepted or rejected depending on the temperature of the system. The method of accepting/rejecting in the Ising model is given by the Metropolis-Hastings algorithm.
- This is repeated m times (we set m to 1000).
Moreover, we have implemented a function which is able to plot the Ising state C-Set as a via graphviz.
Below are the results for temperatures T=1 and T=10. As expected, at low temperatures spins tend to align with one another, thus reducing interaction energy, while at high temperatures the available thermal energy prevents this from happening.
A generalisation of this only requires
- A different choice of schema (generated by user via slice categories)
- A choice of rewrite rules written as spans L<-I->R
- An accept/reject probability, which will depend on the particular model