We discuss how to randomly generate extents of a given formal context. Our basic method involves counting the generating sets of an extent, and we show how this can be done using the Mbius function. We then show how to generate closure systems on seven elements uniformly at random.
Let Random(0,1] denote an operator that generates a random number between
0 and 1 with equal probability. From such a (memoryless) random number
generator an operator Random_subset(S) can be derived that produces, upon
each invocation, a random subset of a given nite set S, such that all subsets are
equally likely (see, e.g., [
Building on this we derive in this article an operator that randomly selects a closed set from a given closure system 1 on a nite set.
Note that this is a trivial task for moderately sized systems of which you can label the closed sets by numbers 1; : : : ; n. For such you could simply randomly pick a number between 1 and n and select the closed set labeled by this number. Since the size of a closure system is at most exponential in the size of its carrier, this trivial algorithm clearly requires polynomial time. However, a potentially exponential list of closed sets must be pre-computed and stored.
For example we aim at generating closure systems at random2. But there
are many closure systems, even for small carrier sets. On seven elements the
number was recently computed by Colomb, Irlande, and Raynaud [
Our motivation comes from recent experimental computer investigations by D. Borchmann that yielded surprising results. Borchmann raised the question if these were artefacts caused by the non-uniform choice of the random input data.
Have a look at Figure 1. It shows ve diagrams, each with 27 rows and 13 columns, corresponding to the possible number of meet reducible and irreducible closed sets in a closure system on a ve element set (the trivial system with zero irreducibles is omitted). A system with r reducibles and i irreducibles corresponds 1 That is, from an intersection-closed familiy of sets. Such families are also called Moore families. 2 The family of all closure systems on a xed set is itself a closure system. to the cell in the r-th row from the bottom and the i-th column from the left. The rst diagram depicts which combinations of r and i are possible, while the other four display relative frequencies (the darker, the higher). The second diagram shows the true frequencies, counted over all 1 385 552 closure systems on ve elements. The other three show frequencies of randomly chosen closure systems (1 000 000 samples each). For the diagram in the middle, the systems were made by putting random crosses in a 5 13context. The fourth diagram was obtained by putting random crosses with random density in a formal context with a random number of columns. The fth diagram shows the distribution of a sample picked with uniform distribution.
We use the language of Formal Concept Analysis [
The closure operator for the extents will be denoted by
X 7! X00: If X = Y 00, then Y is called a generating set of the extent X (not necessarily a minimal one). The number of generating sets of an extent E shall be denoted by egen(E). We extend this denition to arbitrary subsets so that egen(Y ) := jfX
G j X00 = Y 00gj gives the number of generating sets of the extent generated by Y . Of course then, egen(Y ) = egen(Y 00). Therefore if E is an extent then obviously
X fY jY 00=Eg
1 egen(Y ) = 1: Computing the function egen() is a nontrivial task. We shall discuss this below.
Our method could theoretically be applied to many instances, such as generating random partitions, random subgroups, etc. However, its runtime performance is very bad. For most such situations algorithms are known that are much more ecient than what we suggest. Indeed, we do not believe that our method will be very useful in practice. Our contribution is meant as a challenge to come up with a more ecient approach.
We are grateful to the referees for several useful hints. We were unaware
of the paper by Boley, Grtner, and Grosskreutz [
Our innocent looking algorithm for generating a random extent of a given formal context (G; M; I) goes like this: Algorithm 1 Random_extent: Generating a random extent Input: A formal context (G; M; I).
Output: A random extent of (G; M; I) repeat
S := Random_subset(G) until Random(0,1] ege1n(S) return S00.
What the algorithm does essentially is to pick a random subset and output its closure with probability one over the number of generating sets 3. It is quite elementary to prove that it does what it is supposed to do: Proposition 1 The algorithm Random_extent generates extents of (G; M; I) with equal probability.
The proposition is an instance of the following lemma from elementary stochastics, for which we provide a proof. To obtain the proposition from the lemma, let 3 One of the referees pointed out that a much simpler algorithm with the same number of expected iterations is obtained by replacing the until statement by until S is closed. We see however no straightforward way to a recursive version of this algorithm.
A be the set of all subsets of G, let B be the set of all extents, and let f be the map that associates a subset to the extent it generates.
Lemma 1 Let f : A ! B be a surjective (i.e., onto) map between nite sets A and B and let Random(A) be an operator that picks elements from A with equal probability. Then Algorithm 2 outputs elements of B with equal probability. Algorithm 2 Random image: Random image of a mapping Input: An onto map f : A ! B and an operator Random(A) Output: A random element of B repeat a := Random(A) r := Random(0,1] b := f (a); until r jf 11(b)j return b.
Proof It is obvious that the algorithm produces elements of B. In order that a given element b is produced in one iteration of the loop, the element a must belong to f 1(b) and, independently, r jf 11(b)j . The probability that this happens is jf 1(b)j
A j j independently of b. The probability that some element is selected after one step thus is jBj . The probability that the element b is produced after k steps is jAj
1 jBj A j j k 1 k 1 1 A j j
:
jAj = #subsets
jBj #extents
The algorithm may therefore need quite some time. For example, would this
algorithm be applied to the standard context of closure systems to generate a random
closure system on a 6-element set, it requires, on average, 121 402 088 iterations
of the loop, since that context has 26 1 objects and 75 973 751 474 extents ([
Counting generating sets and hitting sets The algorithm in the previous section uses the number egen(A) of a given extent A, and that by itself is not easy. Of course, each such generating set must be a subset of A. On the other hand, a subset S A is a generating set of A i it is not contained in a lower neighbor of A. It is worthwhile to consider the formal context
(A; N ; 2); where N is the family of lower neighbor extents of A. For this context, the elements of N are precisely the maximal extents below A, and thus the generating sets of A are the same as before. Counting generating sets thereby has been reduced to counting generating sets of the unit element in a co-atomistic lattice.
Every subset of A is generating set of exactly one extent of (A; N ; 2). The total number of generating sets thus is 2jAj. Indeed, for every extent B we obtain where E runs over extents. By Mbius inversion we obtain
X egen(E) = 2jBj;
E B egen(A) = X
(E; A) 2jEj;
E A where is the Mbius function of the lattice B(A; N ; 2).
The evaluation of this formula poses no algorithmic diculties. Using the
standard Next_intent algorithm ([
X E<F A (F; A):
Note that this also counts the hitting sets of any nite hypergraph. A hitting set of a family H P(A) of subsets of A is a set T A that has nonempty intersection with each H 2 H (such sets are also called (weak) transversals).
Obviously, T is a hitting set i T is not a subset of a complement of some H 2 H, that is, i T is a generating set of the extent A in the formal context where
(A; Hc; 2);
Hc := fA n H j H 2 Hg: The algorithm given above therefore applies. However, using the Mbius function for counting generating sets is costly. Fortunately, it is unnecessary in many cases, as we shall explain in the next section. 4
The algorithm poses no conditions on how the random set and the random number are generated, and in which order. A huge number of iterations is necessary when we rst generate the extent and then perform a random experiment with very low success probability. A better strategy is to perform the random experiment in several steps and interrupt the loop at an early stage, if necessary. For given 0 p < 1 and p < 1 we may replace the experiment pick a random number r = Random(0,1] and test if r p by pick two random numbers r = Random(0,1] and s = Random(0,1] and test if s and r p , because they have the same success probability. This is the key to the following lemma.
Lemma 2 Let f : A ! B and g : B ! C be surjective mappings between nite sets and let Random(B) be an operator that picks elements from B with equal probability. Then Algorithm 3 outputs elements of C with equal probability. Proof Suppose that we start with a random choice a 2 A and apply Algorithm 3 to the mapping g f . We would draw a random number r := Random(0,1] and output c := g(f (a)) if
We then draw another random number r and output c if r p = jf 1(b)j :
jf 1(g 1(c))j According to Lemma 1 the rst part of this process generates the elements of B with equal probability. The rst part therefore may be replaced by a random choice of elements of B, as stated in the lemma.
Lemma 2 can be applied in several ways to the random extent problem. Typically, A is the set of all subsets of G and C is the set of all extents, while B is a selected family of generating sets. For example we may take some subset G0 G and let B consists of all sets of the form E [ R, where E is an extent of the formal context K0 := (G0; M; I \ (G0 M )) and R \ G0 = ;. This yields Algorithm 4.
Input: A formal context K and an operator Random_extent(K0) producing random extents of a subcontext K0 K Output: A random extent of K.
repeat
E := Random_extent(K0) A := E [ Random_subset(G n G0) r := Random(0,1]; until r egeegnen(E(A;K)0) return A00. 5
Our original motivation was generating closure systems (also called Moore families) at random. The number of generating sets of a closure system is easy to determine without using the Mbius function. Every closure system has a unique minimal generating set, consisting of all meet-irreducible elements. The total number of generating sets therefore is 2 to the power s, where s is the number of reducible closed sets.
The natural formal context for the closure systems on a set S is given by (P(S); Imp(S); j=); Imp(S) := fA ! b j A
S; b 2 S n Ag where is the set of all implications with singleton conclusion over S and X j= A ! b : ()
A 6
X or b 2 X: It is well known and easy to see that the extents of this formal context are precisely the closure systems on S. However, this context contains a reducible object, which is S. The standard context therefore is
The case we are interested in is S := f0; 1; : : : ; n 1g. The object set G of the context then consists of all proper subsets of S. We choose
(P(S) n fSg; Imp(S); j=): G0 := fX G1 := fX
S j n S j n 1 2= Xg 1 2 Xg: The extents of (G1; Imp(S); j=) are (when S is added) precisely those closure systems on S that contain n 1 in every closed set. These are in an obvious bijection to the closure systems on S n fn 1g.
The context (G0; Imp(S); j=) has precisely twice as many extents as there are closure systems on f0; : : : ; n 2g: Each closure system C on f0; : : : ; n 2g is an extent, but also C n fSg is.
Let S := f0; : : : ; n 1g. For applying Lemma 2 we let A be the set of all subsets of P(S) n fSg, C be the family of all closure systems on S, let G0 and G1 be as above and B consist of those set families F P(S) n fSg for which F \ G0 and F \ G1 are extents of the respective subcontexts. Every closure system C on S is in B, but not conversely. The closure system generated by a family F from B may contain additional sets, obtained as intersections of a set in G0 and a set in G1. However, such new sets can only be contained in G0, since a set containing the element n 1 cannot be obtained as an intersection involving one not containing n 1.
Algorithm 5 encodes the subsets of S := f0; : : : ; n 1g in the natural manner as the integers from 0 to 2n 1, using the bitwise and-operation for intersecting sets. A closure system on S is represented by an array F [0 . . 2n
The algorithm starts with two closure systems on f0; : : : ; n 2g and concatenates them. In addition, a random decision is made if the set f0; : : : ; n 2g is to be counted as a closed set. The result is not necessarily a closure system and needs to be made intersection closed. This is done in the second part of the algorithm (beginning with success:= true). Whenever a new reducible element is encountered, the generation process is abandoned with probability 0:5 and is started over. Only if this never happens, a closure system on f0; ::; n 1g is achieved for output.
Algorithm 5 Random_Moore(n): Random Moore family.
Input: An operator Random_Moore(n 1) generating random Moore families on f0; : : : ; n 2g.
Output: A random Moore family on f0; : : : ; n 1g.
repeat
F0 := Random_Moore(n 1) F [0 . . 2n 1 2] := F0[0 . . 2n 1 2] F [2n 1
We have implemented Algorithm 5 for n = 7 and present rst experimental results. Note that the number of random samples produced by this experiment is small compared to the number of closure systems: we have generated less than 0:000 000 000 000 4% of all closure systems on seven points. 5 10 15 20 25 30 35
The computation took one night on a 1.4 GHz PC. We did not even attempt to generate random closure systems on eight elements using Algorithm 5. We believe that a substantially better idea is needed for that case and beyond.