Fast Computation of Proper Premises Uwe Ryssel1 , Felix Distel2 , and Daniel Borchmann3 1 Institute of Applied Computer Science, Technische Universität Dresden, Dresden, Germany, uwe.ryssel@tu-dresden.de 2 Institute of Theoretical Computer Science, Technische Universität Dresden, Dresden, Germany, felix@tcs.inf.tu-dresden.de 3 Institute of Algebra, Technische Universität Dresden, Dresden, Germany, borch@tcs.inf.tu-dresden.de Abstract. This work is motivated by an application related to refactor- ing of model variants. In this application an implicational base needs to be computed, and runtime is more crucial than minimal cardinality. Since the usual stem base algorithms have proven to be too costly in terms of runtime, we have developed a new algorithm for the fast computation of proper premises. It is based on a known link between proper premises and minimal hypergraph transversals. Two further improvements are made, which reduce the number of proper premises that are obtained multiple times and redundancies within the set of proper premises. We provide heuristic evidence that an approach based on proper premises will also be beneficial for other applications. 1 Introduction Today, graph-like structures are used in many model languages to specify al- gorithms or problems in a more readable way. Examples are data-flow-oriented simulation models, such as MATLAB/Simulink, state diagrams, and diagrams of electrical networks. Generally, such models consist of blocks or elements and connections among them. Using techniques described in Section 5.2, a formal context can be obtained from such models. By computing an implicational base of this context, dependencies among model artifacts can be uncovered. These can help to represent a large number of model variants in a structured way. For many years, computing the stem base has been the default method for extracting a small but complete set of implications from a formal context. There exist mainly two algorithms to achieve this [10,15], and both of them compute not only the implications from the stem base, but also concept intents. This is problematic as a context may have exponentially many concept intents. Recent theoretical results suggest that existing approaches for computing the stem base may not lead to algorithms with better worst-case complexity [6,1]. Bearing this in mind, we focus on proper premises. Just like pseudo-intents, that are used to obtain the stem base, proper premises yield a sound and com- plete set of implications. Because this set of implications does not have minimal cardinality, proper premises have been outside the focus of the FCA community for many years. However, there are substantial arguments to reconsider using them. Existing methods for computing proper premises avoid computing con- cept intents. Thus, in contexts with many concept intents they may have a clear advantage in runtime over the stem base algorithms. This is particularly true for our application where the number of concept intents is often close to the theoretical maximum. Here, attributes often occur together with their negated counterparts, and the concept lattice can contain several millions of elements. In Section 5.1 we provide arguments that we can expect the number of con- cept intents to be larger than the number of proper premises in most contexts, assuming a uniform random distribution. Often, in applications, runtime is the limiting factor, not the size of the basis. But even where minimal cardinality is a requirement, computing proper premises is worth considering, since there are methods to transform a base into the stem base in polynomial time [16]. In this paper we present an algorithm for the fast computation of proper premises. It is based on three ideas. The first idea is to use a simple connection between proper premises and minimal hypergraph transversals. The problem of enumerating minimal hypergraph transversals is well-researched. Exploiting the link to proper premises allows us to use existing algorithms that are known to behave well in practice. A first, naïve algorithm iterates over all attributes and uses a black-box hypergraph algorithm to compute proper premises of each attribute. A drawback when iterating over all attributes is that the same proper premise may be computed several times for different attributes. So we introduce a can- didate filter in the second step: For each attribute m, the attribute set is filtered and proper premises are searched only among the candidate attributes. We show that this filtering method significantly reduces the number of multiple-computed proper premises while maintaining completeness. In a third step we exploit the fact that there are obvious redundancies within the proper premises. These can be removed by searching for proper premises only among the meet-irreducible attributes. We argue that our algorithms are trivial to parallelize, leading to further speedups. Due to their incremental nature, parallelized versions of the stem base algorithms are not known to date. We conclude by providing experimental re- sults. These show highly significant improvements for the contexts obtained from the model refactoring application. For a sample context, where Next-Closure re- quired several hours to compute the stem base, runtime has dropped to fractions of a second. For contexts from other applications the improvements are not as impressive but still large. 2 Preliminaries We provide a short summary of the most common definitions in formal concept analysis. A formal context is a triple K = (G, M, I) where G is a set of objects, M a set of attributes, and I ⊆ G × M is a relation that expresses whether an object g ∈ G has an attribute m ∈ M . If A ⊆ G is a set of objects then A0 denotes the set of all attributes that are shared among all objects in A, i.e., A0 = { m ∈ M | ∀g ∈ G : gIm }. Likewise, for some set B ⊆ M we define B 0 = { g ∈ G | ∀m ∈ B : gIm }. Pairs of the form (A, B) where A0 = B and B 0 = A are called formal concepts. Formal concepts of the form ({ m }0 , { m }00 ) for some attribute m ∈ M are called attribute concept and are denoted by µm. We define the partial order ≤ on the set of all formal concepts of a context to be the subset order on the first component. The first component of a formal concept is called the concept extent while the second component is called the concept intent. Formal concept analysis provides methods to mine implicational knowledge from formal contexts. An implication is a pair (B1 , B2 ) where B1 , B2 ⊆ M , usually denoted by B1 → B2 . We say that the implication B1 → B2 holds in a context K if B10 ⊆ B20 . An implication B1 → B2 follows from a set of implications L if for every context K in which all implications from L hold, B1 → B2 also holds. We say that L is sound for K if all implications from L hold in K, and we say that L is complete for K if all implications that hold in K follow from L. There exists a sound and complete set of implications for each context which has minimal cardinality [12]. This is called the stem base. The exact definition of the stem base is outside the scope of this work. A sound and complete set of implications can also be obtained using proper premises. For a given set of attributes B ⊆ M , define B • to be the set of those attributes in M \ B that follow from B but not from a strict subset of B, i.e.,  [  B • = B 00 \ B ∪ S 00 . S(B B is called a proper premise if B • is not empty. It is called a proper premise for m ∈ M if m ∈ B • . It can be shown that L = { B → B • | B proper premise } is sound and complete [11]. Several alternative ways to define this sound and complete set of implications can be found in [2]. We write g $ m if g 0 is maximal with respect to the subset order among all object intents which do not contain m. 3 Proper Premises as Minimal Hypergraph Transversals We present a connection between proper premises and minimal hypergraph transversals, which forms the foundation for our enumeration algorithms. It has been exploited before in database theory to the purpose of mining functional dependencies from a database relation [14]. Implicitly, it has also been known for a long time within the FCA community. However, the term hypergraph has not been used in this context (cf. Prop. 23 from [11]). Let V be a finite set of vertices. Then a hypergraph on V is simply a pair (V, H) where H is a subset of the power set 2V . Intuitively, each set E ∈ H represents an edge of the hypergraph, which, in contrast to classical graph theory, may be incident to more or less than two vertices. A set S ⊆ V is called a hypergraph transversal of H if it intersects every edge E ∈ H, i.e., ∀E ∈ H : S ∩ E 6= ∅. S is called a minimal hypergraph transversal of H if it is minimal with respect to the subset order among all hypergraph transversals of H. The transversal hyper- graph of H is the set of all minimal hypergraph transversals of H. It is denoted by Tr (H). The problem of deciding for two hypergraphs G and H whether H is the transversal hypergraph of G is called TransHyp. The problem of enumerating all minimal hypergraph transversals of a hypergraph G is called TransEnum. Both problems are relevant to a large number of fields and therefore have been well-researched. TransHyp is known to be contained in coNP. Since it has been shown that TransHyp can be decided in quasipolynomial time [9], it is not believed to be coNP-complete. Furthermore, it has been shown that it can be decided using only limited non-determinism [8]. For the enumeration problem it is not known to date whether an output-polynomial algorithm exists. However, efficient algorithms have been developed for several classes of hypergraphs [8,4]. The following proposition can be found in [11] among others. Proposition 1. P ⊆ M is a premise of m ∈ M iff (M \ g 0 ) ∩ P 6= ∅ holds for all g ∈ G with g $ m. P is a proper premise for m iff P is minimal (with respect to ⊆) with this property. We immediately obtain the following corollary. Corollary 1. P is a premise of m iff P is a hypergraph transversal of (M, H) where H := {M \ g 0 | g ∈ G, g $ m}. The set of all proper premises of m is exactly the transversal hypergraph Tr ({M \ g 0 | g ∈ G, g $ m}). In particular this proves that enumerating the proper premises of a given attribute m is polynomially equivalent to TransEnum. This can be exploited in a naïve algorithm for computing all proper premises of a formal context (Al- gorithm 1). Being aware of the link to hypergraph transversals, we can benefit from existing efficient algorithms for TransEnum in order to enumerate proper premises similar to what has been proposed in [14]. Of course, it is also possible to use other enumeration problems to which TransEnum can be reduced. Ex- amples are the enumeration of prime implicants of Horn functions [2] and the enumeration of set covers. 4 Improvements to the Algorithm 4.1 Avoiding Duplicates using Candidate Sets We can further optimize Algorithm 1 by reducing the search space. In the naïve algorithm proper premises are typically computed multiple times since they can be proper premises of more than one attribute. Our goal is to avoid this wherever possible. The first idea is shown in Algorithm 2. There we introduce a candidate set C of particular attributes, depending on the current attribute m. We claim now that we only have to search for minimal hypergraph transversals P of { M \ g 0 | g $ m } with P ⊆ C. We provide some intuition for this idea. Algorithm 1 Naïve Algorithm for Enumerating All Proper Premises Input: K = (G, M, I) P=∅ for all m ∈ M do P = P ∪ Tr ({M \ g 0 | g ∈ G, g $ m}) end for return P Algorithm 2 A Better Algorithm for Enumerating All Proper Premises Input: K = (G, M, I) P = { { m } | m ∈ M, { m } is a proper premise of K } for all m ∈ M do C = { u ∈ M \ { m } | 6 ∃v ∈ M : µu ∧ µm ≤ µv < µm } P = P ∪ { P ⊆ C | P minimal hypergraph transversal of { M \ g 0 | g $ m } } end for return P Let us fix a formal context K = (G, M, I), choose m ∈ M and let P ⊆ M be a proper premise for m. Then we know that m ∈ P 00 , which is equivalent to ^ µp ≤ µm. p∈P If we now find another attribute n ∈ M \ { m } with ^ µp ≤ µn < µm p∈P it suffices to find the set P as a proper premise for n, because from µn < µm we can already infer m ∈ P 00 . Conversely, if we search for all proper premises for m, we only have to search for those who are not proper premises for attributes n with µn < µm. Now suppose that there exists an element u ∈ P and an attribute v ∈ M such that µm ∧ µu ≤ µv < µm. (1) Then we know ^ ^ ( µp) ∧ µm = µp ≤ µv < µm, p∈P p∈P i.e., P is already a proper premise for v. In this case, we do not have to search for P , since it will be found in another iteration. On the other hand, if P is a proper premise for m but not for any other attribute n ∈ M with µn < µm, the argument given above shows that an element u ∈ P and an attribute v ∈ M satisfying (1) cannot exist. Lemma 1. Algorithm 2 enumerates for a given formal context K = (G, M, I) all proper premises of K. Proof. Let P be a proper premise of K for the attribute m. P is a proper premise and therefore m ∈ P 00 holds, which is equivalent to µm ≥ (P 0 , P 00 ). Let c ∈ M be such that µm ≥ µc ≥ (P 0 , P 00 ) and µc is minimal with this property. We claim that either P = { c } or P is found in the iteration for c of Algorithm 2. Suppose c ∈ P . Then m ∈ { c }00 follows from µm ≥ µc. As a proper premise, P is minimal with the property m ∈ P 00 . It follows P = { c } and P is found by Algorithm 2 during the initialization. Now suppose c 6∈ P . Consider C := { u ∈ M \ { c } | 6 ∃v ∈ M : µu ∧ µc ≤ µv < µc }. We shall show P ⊆ C. To see this, consider some p ∈ P . Then p 6= c holds by assumption. Suppose that p 6∈ C, i.e., there is some v ∈ M such that µp ∧ µc ≤ µv < µc. Because of p ∈ P , µp ≥ (P 0 , P 00 ) and together with µc ≥ (P 0 , P 00 ) we have (P 0 , P 00 ) ≤ µp ∧ µc ≤ µv < µc in contradiction to the minimality of µc. This shows p ∈ C and all together P ⊆ C. To complete the proof it remains to show that P is a minimal hypergraph transversal of { M \ { g }0 | g $ c }, i.e., that P is also a proper premise for c, not only for m. Consider n ∈ P . Assume c ∈ (P \ { n })00 . Since {c} implies m, then P \ { n } would be a premise for m in contradiction to the minimality of P . Thus c 6∈ (P \ { n })00 holds for all n ∈ P and therefore P is a proper premise for c. 4.2 Irreducible Attributes We go one step further and also remove attributes m from our candidate set C whose attribute concept µm is the V meet of other attribute concepts µx1 , . . . , µxn , n where x1 , . . . , xn ∈ C, i.e., µm = i=1 µxi . This results in Algorithm 3 that no longer computes all proper premises, but a subset that still yields a complete implicational base. We show that we only have to search for proper premises P with P ⊆ N where N is the set of irreducible attributes of K. To ease the presentation, let us assume for the rest of this paper that the formal context K is attribute-clarified. Algorithm 3 Computing Enough Proper Premises Input: K = (G, M, I) P = { { m } | m ∈ M, { m } Vis a proper premise of K } N = M \ { x ∈ M | µx = n i=1 µxi for an n ∈ N and xi ∈ M for 1 ≤ i ≤ n } for all m ∈ M do C = { u ∈ N \ { m } | 6 ∃v ∈ M : µu ∧ µm ≤ µv < µm } P = P ∪ { P ⊆ C | P minimal hypergraph transversal of { M \ g 0 | g $ m } } end for return P Proposition 2. Let m be an attribute and let P be a proper premise for m. Let x ∈ P , n ∈ N, and for 1 ≤ i ≤ n let xi ∈ M be attributes satisfying – m∈ / {Vx1 , . . . , xn }, n – µx = i=1 µxi , 00 – xi ∈ / ∅ for all 1 ≤ i ≤ n and – µx < µxi for all 1 ≤ i ≤ n. Then { x } is a proper premise for all xi and there exists a nonempty set Y ⊆ { x1 , . . . , xn } such that (P \ { x }) ∪ Y is a proper premise for m. Proof. It is clear that { x } is a proper premise for all xi , since xi ∈ { x }00 and / ∅00 . Define xi ∈ QY := (P \ { x }) ∪ Y for Y ⊆ { x1 , . . . , xn }. We choose Y ⊆ { x1 , . . . , xn } such that Y is minimal with respect to m ∈ Q00Y . Such a set exists, since m ∈ ((P \ { x }) ∪ { x1 , . . . , xn })00 because of { x1 , . . . , xn } → { x }. Furthermore, Y 6= ∅, since m ∈ / (P \ { x })00 . We now claim that QY is a proper premise for m. Clearly m ∈ / QY , since m∈ / Y . For all y ∈ Y it holds that m ∈ / (QY \ { y })00 or otherwise minimality of Y would be violated. It therefore remains to show that m ∈ / (QY \ { y })00 for all y ∈ QY \ Y = P \ { x }. (QY \ { y })00 = ((P \ { x, y }) ∪ Y )00 ⊆ ((P \ { y }) ∪ Y )00 = (P \ { y })00 / (P \{ y })00 , we get m ∈ since { x } → Y and x ∈ P \{ y }. Since m ∈ / (QY \{ y })00 as required. In sum, QY is a proper premise for m. Lemma 2. Let N be the set of all meet-irreducible attributes of a context K. Define P = { X ⊆ M | |X| ≤ 1, X proper premise } ∪ { X ⊆ N | X proper premise } Then the set L = { P → P • | P ∈ P } is sound and complete for K. Proof. Let m be an attribute and let P be a proper premise for m. If P ∈ / P then it follows that P 6⊆ N . Thus we can find y1 ∈ P \N and elements x1 , . . . , xn ∈ M with n ≥ 1 such that – m∈ / { xV1 , . . . , xn }, n – µy1 = i=1 µxi , / ∅00 for all 1 ≤ i ≤ n and – xi ∈ – µx < µxi for all 1 ≤ i ≤ n. By Proposition 2 we can find a proper premise P1 such that P → { m } fol- lows from { y1 } → { x1 , . . . , xn } and P1 → { m }. Clearly { y1 } ∈ P, since all singleton proper premises are contained in P. If P1 ∈ / P then we can apply Proposition 2 again and obtain a new proper premise P2 , etc. To see that this process terminates consider the strict partial order ≺ defined as P ≺ Q iff ∀q ∈ Q : ∃p ∈ P : µp < µq. It is easy to see that with each application of Proposition 2 we obtain a new proper premise that is strictly larger than the previous with respect to ≺. Hence, the process must terminate. This yields a set P 0 = { { y1 }, . . . , { yk }, Pk } ⊆ P such that P → { m } follows from { Q → Q• | Q ∈ P 0 }. Thus L is a sound and complete set of implications. Together with Lemma 1 this yields correctness of Algorithm 3. Corollary 2. The set of proper premises computed by Algorithm 3 yields a sound and complete set of implications for the given formal context. 5 Evaluation 5.1 Computing Proper Premises Instead of Intents In both the stem base algorithms and our algorithms, runtime can be exponential in the size of the input. In the classical case the reason is that the number of intents can be exponential in the size of the stem base [13]. In the case of our algorithms there are two reasons: the computation of proper premises is TransEnum-complete, and there can be exponentially many proper premises. The first issue is less relevant in practice because algorithms for TransEnum, while still exponential in the worst case, behave well for most instances. To see that there can be exponentially many proper premises in the size of the stem base, let us look at the context Kn from Table 1 for some n ≥ 2, consisting of two contranominal scales of dimension n × n and one attribute a with empty extent. It can be verified that the proper premises of the attribute a are exactly the sets of the form {mi | i ∈ I} ∪ {m0i | i ∈ / I} for some I ⊆ {1, . . . , n}, while the only pseudo-intents are the singleton sets and {m1 , . . . , mn , m01 , . . . , m0n }. Hence there are 2n proper premises for a, while there are only 2n + 2 pseudo-intents. Table 1. Context Kn with Exponentially Many Proper Premises m1 . . . mn m01 . . . m0n a g1 .. . I6= I6= gn Next-Closure behaves poorly on contexts with many intents while our algo- rithms behave poorly on contexts with many proper premises. In order to provide evidence that our algorithm should behave better in practice we use formulae for the expectation of the number of intents and proper premises in a formal context that is chosen uniformly at random among all n × m-contexts for fixed natural numbers n and m.4 Derivations of these formulae can be found in [7]. The expected value for the number of intents in an n × m-context is m  X n   X m n −rq Eintent = 2 (1 − 2−r )m−q (1 − 2−q )n−r , q=0 q r=0 r while the expected value for the number of proper premises for a fixed attribute a in an n × m-context is n   m−1   q X n X m 2 X Y pi+1 −pi −1 Epp = 2−n q! 2−q 1 − 2−q (1 + i) . r=0 r q=0 q q i=0 (p1 ,...,pq )∈N 1≤p1 <···