Algorithm::AM::lattice - How to store and manipulate large lattices in C
version 3.12
The Analogical Modeling (AM) algorithm requires constructing and traversing large completely distributive lattices, also known as Boolean algebras. This document tells how we do it in Parallel.xs.
A lot of what appears below could be used generally to store lattices; that which applies specifically to AM::Parallel is so marked.
AM::Parallel
If n is a positive integer, then the set of positive integers that can be expressed in n or fewer bits, along with the operations & (bitwise AND) and | (bitwise OR), is an example of a Boolean algebra. It is also an example of a lattice which is completely distributive. Although all the lattices used in AM are in fact Boolean algebras, it is customary to refer to them merely as lattices.
Any lattice can have a partial order imposed upon it; this is done by defining a <= b whenever a & b = b (or equivalently, a | b = a). This partial order is symmetric, transitive, and antireflexive (if a <= b and b <= a, then a = b). It's called a partial order because it is often the case that neither a <= b nor b <= a.
A common way to draw lattices on paper is by putting elements that are greater than other elements higher up on the paper, using line segments to indicate the partial order. Here's an example:
000 /|\ / | \ / | \ / | \ 001 010 100 | \ / \ / | | \/ \/ | | /\ /\ | | / \ / \ | 011 101 110 \ | / \ | / \ | / \|/ 111
If you can get from one element to another by only going down along the line segments, then the first element is greater than the second.
The elements of the lattice created by AM are sets. The partial order is defined as follows: A <= B if B is a subset of A. If you draw the lattice, the smaller sets are at the top. This lattice is known as the supracontextual lattice; its elements are called supracontexts.
The value of n, and thus the size of the lattice, is determined by the length of the feature vector of the test item (see AM.pod for more explanation). There is a set corresponding to each n-bit positive integer; furthermore, if set A corresponds to integer a and set B corresponds to integer b, then A is a superset of (or "below") B if a & b = b.
Many of the elements of the supracontextual lattice are equal as sets; i.e., they have precisely the same members. Thus, for those of you who know a lot of math, it is important not to confuse the supracontextual lattice with the Boolean algebra generated by the power set of a set. The supracontextual lattice is a Boolean algebra of sets; where these sets come from is explained in AM.pod.
To store the supracontextual lattice, it is enough to create an array lattice[] of length 2^n, where lattice[a] contains a pointer to a structure containing information about the elements of the set corresponding to a.
lattice[]
lattice[
]
Of course, the size of lattice[] grows exponentially with n; to overcome that, see the section on lattices as products of smaller lattices.
The supracontextual lattice is built up by adding elements to these sets one at a time. When a new element is added to a set, it is a simple thing to memcpy (actually, we use Perl's safe equivalent, Copy) the original set to a new location, append the new element, and change the pointer. We only have to do this once; Parallel.xs keeps track of the creation of new sets, so sometimes all that is necessary is the changing of a pointer.
memcpy
Copy
During the course of the AM algorithm, it is necessary to visit all the supracontexts that lie "below" a given supracontext. For example, given that a supracontext is labeled
1001011
AM requires an iterator that produces
1001111 1011011 1011111 1101011 1101111 1111011 1111111
though the order in which these seven are produced is immaterial.
Parallel.xs does this by using a Gray code. This is a method by which only one bit flips (either from 0 to 1 or from 1 to 0) at each step. Deciding which bit to flip is done as follows:
List the "gaps"; for
the gaps are
0100000 = gaps[0] 0010000 = gaps[1] 0000100 = gaps[2]
Each gap has exactly one 1 bit which lines up with a 0 in the original number.
If there are g gaps, list the g-bit integers in reverse order: in this case, 111, 110, ..., 001, 000.
Take each of these numbers in succession. Determine where the rightmost 1 is; its position determines which bit to flip:
1001011 1101011 = 1001011 ^ 0100000 (rightmost 1 of 111 is bit 0, use gap[0]) 1111011 = 1101011 ^ 0010000 (rightmost 1 of 110 is bit 1, use gap[1]) 1011011 = 1111011 ^ 0100000 (rightmost 1 of 101 is bit 0, use gap[0]) 1011111 = 1011011 ^ 0000100 (rightmost 1 of 100 is bit 2, use gap[2]) 1111111 = 1011111 ^ 0100000 (rightmost 1 of 011 is bit 0, use gap[0]) 1101111 = 1111111 ^ 0010000 (rightmost 1 of 010 is bit 1, use gap[1]) 1001111 = 1101111 ^ 0100000 (rightmost 1 of 001 is bit 0, use gap[0])
(As I write this, I see that finding the bit to flip is the same problem of deciding which disk to move in the Towers of Hanoi problem.)
Consider the following lattice: the first number is the binary label, and the other numbers represent the elements of the set with that label:
label elements 0000 0001 3 0010 0100 6 1000 0011 3 0101 3 6 0110 6 1001 1 3 1010 4 1100 5 6 0111 2 3 6 1011 1 3 4 7 1101 1 3 5 6 1110 4 5 6 1111 1 2 3 4 5 6 7
(Verify that this is a lattice.)
This lattice can be stored as two smaller lattices:
label elements 00 3 01 2 3 6 10 1 3 4 7 11 1 2 3 4 5 6 7 label elements 00 5 6 01 1 3 5 6 10 4 5 6 11 1 2 3 4 5 6 7
The set labeled by 1001 in the large lattice is precisely the intersection of the sets labeled by 10 and 01 respectively in the smaller lattices: {1, 3} is the intersection of {1, 3, 4, 7} and {1, 3, 5, 6}.
AM::Parallel breaks the supracontextual lattice up into 4 smaller lattices, resulting in a great savings of memory at the expense of finding a lot of intersections. But since the elements of the sets are listed as increasing sequences of positive integers, finding the intersection is actually quite straightforward.
To initialize, set i to point to the largest element of the first set and j to point to the largest element of the second set.
Move i to the left as long as it points to an integer larger than that pointed to by j.
If i points to an integer less than the integer pointed to by j, swap i and j so they point into the opposite sets; go to step 1.
If i and j point to equal values, put this equal value into the intersection and move both i and j once to the left.
If i can't be moved, the algorithm ends.
Theron Stanford <shixilun@yahoo.com>, Nathan Glenn <garfieldnate@gmail.com>
This software is copyright (c) 2021 by Royal Skousen.
This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.
To install Algorithm::AM, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Algorithm::AM
CPAN shell
perl -MCPAN -e shell install Algorithm::AM
For more information on module installation, please visit the detailed CPAN module installation guide.