Finding Errors in New Object in Formal Contexts Artem Revenko12? , Sergei O. Kuznetsov2 , and Bernhard Ganter1 1 Technische Universität Dresden Zellescher Weg 12-14, 01069 Dresden, Germany 2 National Research University Higher School of Economics Pokrovskiy bd. 11, 109028 Moscow, Russia artem viktorovich.revenko@mailbox.tu-dresden.de, skuznetsov@hse.ru, bernhard.ganter@tu-dresden.de Abstract. Classification of possible errors in formal contexts is given and the possibilities of exploring them are discussed. An approach for finding errors of some classes in formal contexts is introduced. This ap- proach may be used in attempt to find errors in an object that is to be added to the context. The idea is based on finding those implications from an implication basis of the context, which are not respected by the object. It is noted that addressing such a problem directly may lead to an intractable solution. Alternative approach based on closing subsets of the intent of an object is considered in order to be able to find solution in polynomial time and deal with inconsistent combination of attributes. Examples are provided. Keywords: formal context, implication, error exploration 1 Introduction The work is motivated by the idea of building multi-user system based on Formal Concept Analysis methods. It would be different from QED project [QED] in the way that information should not be formalised as mathematical expressions and from Wikipedia in the way that information can somehow be inferenced by computer. In such a multi-user system error finding tools are absolutely nec- essary. In this work only errors in new objects (not yet added to the context) are considered. Throughout the text we assume that objects in the context are checked by an expert and correct. We attempt to find errors in new objects based on the information already in the context. This is actually the first step to building error finding tools. 2 Main Definitions Let G and M be given sets. Let I ⊆ G × M be a binary relation between G and M . Triple K := (G, M, I) is called a (formal) context. Set G is called a set of objects. Set M is called a set of attributes. ? We thank Sergei Obiedkov for discussion and useful remarks Consider mappings ϕ : 2G → 2M and ψ : 2M → 2G : ϕ(A) := {m ∈ M | gIm for all g ∈ A}, ψ(B) := {g ∈ G | gIm for all m ∈ B}. For any A1 , A2 ⊆ G, B1 , B2 ⊆ M one has 1. A1 ⊆ A2 ⇒ ϕ(A2 ) ⊆ ϕ(A1 ) 2. B1 ⊆ B2 ⇒ ψ(B2 ) ⊆ ψ(B1 ) 3. A1 ⊆ ψϕ(A1 ) and B1 ⊆ ϕψ(B1 ) Mappings ϕ and ψ define a Galois connection between (2G , ⊆) and (2M , ⊆), i.e. ϕ(A) ⊆ B ⇔ ψ(B) ⊆ A. Usually, instead of ϕ and ψ a single notation (·)0 is used. (·)0 is sometimes called a derivation operator. For object g ∈ G the set g 0 = {m ∈ M |gIm} is called an intent of g and is denoted int(g). Similarly, for attribute m ∈ M the set m0 is called an extent of m and is denoted ext(m). Let M = {m | m ∈ M } and I = {(g, m) | g ∈ G, m ∈ M, (g, m) ∈ / I}. Triple K := (G, M , I) is called a complementary (formal) context. Let B ⊆ M, g ∈ G, B := {b | b ∈ B}. B ⊆ int(g) means that in K = (G, M, I) object g is not related to all attributes from B. An implication of K := (G, M, I) is defined as a pair (A, B), written A → B, where A, B ⊆ M . A is called a premise, B is called a conclusion. Implication A → B is respected by a set of attributes N if A * N or B ⊆ N . Implication A → B holds (is valid) in K if A0 ⊆ (B ∪ A)0 or A0 ⊆ B 0 , i.e. every object, that has all the attributes from A, also has all the attributes from B. The implications of K satisfy Armstrong rules: X→Y X → Y, Y ∪ Z → W , , X→X X ∪Z →Y X ∪Z →W A support of an implication is the set of object, whose intents respect this im- plication. An implication basis of context K is defined as a set L of implications of K, from which any valid implication for K can be deduced by the Armstrong rules and none of the proper subsets of L has this property. A minimal implication basis is an implication basis minimal in the number of implications. A minimal implication basis was defined in [GD86] and is known as canonical implication basis. In paper [Gan84] the premises of implications from canonical base were characterized in terms of pseudo-intents. A subset of attributes P ⊆ M is called pseudo-intent, if P 6= P 00 and for every such pseudo- intent Q such that Q ⊂ P , one has Q00 ⊂ P . Canonical implication basis looks then as follows: {P → (P 00 \ P ) | P - pseudo-intent}. 3 Classification and Exploration of Errors Every object in the context is described by the set of attributes, that are re- lated to this object. In the ‘‘real world’’ there may exist dependencies between attributes. Consider possible cases in terms of implications: 1. Valid in ‘‘real world’’ dependency A → B, A, B ⊆ M is not respected by an object 2. Valid in ‘‘real world’’ dependency A → B, A, B ⊆ M is not respected by an object 3. Combination of two above cases, i.e. valid in ‘‘real world’’ dependency A → B ∧ C, A, B, C ⊆ M is not respected by an object 4. Valid in ‘‘real world’’ dependency A → b ∨ c, A ⊆ M, b, c ∈ M is not respected by an object 5. Valid in ‘‘real world’’ dependency A → F, where A ⊆ M, F is any logical formula not considered above, is not respected by an object (for example, F = a ∨ (b ∧ c)) Unfortunately, it turns out that not all possible errors might be found using implications of a context. Namely, case 4 corresponds to reducible object in a context, while it is known that reducible objects change neither the lattice nor the implication basis of a context (definitions of reducible objects and lattices of contexts are not given in this paper for the sake of compactness, for definitions and further information see [GW99]). Every implication A → B can be regarded as a conjunction of implications A → B1 and A → B2 , B1 ∪ B2 = B. Thereby, in Case 5 in F top level conjunctions can be dealt with easily. However, as in Case 4 we do not know how to reveal errors that have disjunctions in their conclusion. Let L be a set of all implications valid for a context K. From any implication basis any valid implication for the context should be deducible by definition. It means that if an object does not respect an implication from L, then it should not respect an implication from implication basis of the context. Then an expert is asked whether this implication is valid. If he accepts this implication, then the object is an error. All the errors of the first class are caught using this approach. 4 An Example The formal context on Fig. 1 shows the properties of convex quadrangles. The context is not full, i.e. not all possible convex quadrangles are considered, and some objects in the context are reducible (do not bring new information in an implication basis of the context). 7 attributes are considered. Attributes ‘has equal legs’ and ‘has equal angles’ require at least two angles/legs of a quadrangle to be equal. Some dependencies on attributes are obvious, for example, it is clear that if all angles are equal in a quadrangle then this quadrangle definitely has equal angles. 4 errors are presented on Fig 2. Errors are added to the context on Fig. 1 one at a time. One should treat an error as an object to be added to the context. The context without errors on Fig. 1 is denoted K , (·)0 is the corresponding derivation operator. The context of errors on Fig. 2 is denoted Ke , (·)e is the derivation operator for Ke . Example 1. {Error 1}e ={has equal legs, at least 3 different angles, all legs equal} {Error 1}e00 ={all angles equal, all legs equal, at least 3 different angles, at least 3 different legs, has equal angles, has equal legs, has right angle} at least 3 different angles at least 3 different legs has equal angles all angles equal has right angle has equal legs Convex quadrangles all legs equal Square × × × × × Rectangle × × × × Quadrangle × × Rhombus × × × Parallelogram × × Rectangular trapezium × × × × Quadrangle with 2 equal legs and right angle × × × × Isosceles trapezium × × × Rectangular trapezium with 2 equal legs × × × × × Quadrangle with 2 equal angles × × × Quadrangle with 2 equal legs × × × Quadrangle with 2 equal legs and 2 equal angles × × × × Fig. 1. Context of convex quadrangles K at least 3 different angles at least 3 different legs has equal angles all angles equal has right angle has equal legs Errors all legs equal Error1 × × × Error2 × × × × Error3 × × × × × × Error4 × × × × Fig. 2. Context of errors Ke Canonical basis of the context on Fig. 1 looks as follows: 1. at least 3 different angles → at least 3 different legs 2. all angles equal → has equal angles, has equal legs, has right angle 3. all legs equal → has equal angles, has equal legs 4. has right angle, at least 3 different legs → at least 3 different angles 5. has equal angles, has equal legs, at least 3 different legs, all legs equal → has right angle,at least 3 different angles, all angles equal 6. has equal angles, has equal legs, at least 3 different legs, all angles equal, has right angle, at least 3 different angles → all legs equal 7. has right angle, has equal legs, all legs equal, has equal angles → all angles equal Consider Error2. {Error 2}e ={has equal legs, has right angle, all legs equal, all angles equal} This object does not respect Implications 2 and 3. It is easy to see that both implications are valid in “real world”. Thereby, an expert recognizes object as an error. 5 Improvements Although this approach gives the needed result, there are some problems re- maining. The problem of producing canonical basis with known algorithms is intractable. Recent theoretical results suggest that existing approaches for com- puting the stem base may not lead to algorithms with better worst-case com- plexity [DS11], [BK10]. One can use other bases (for example, advances were achieved in computing proper premises [RDB11]), but known algorithms are still too costly and non minimal bases do not guarantee to ask an expert mini- mal yet sufficient number of questions. Since we are only interested in implication corresponding to an object, it is not necessary to compute a whole implication basis. Only the closure of object’s intent may be considered. From monotonicity of the closure operator of the con- text it follows that we do not lose any attributes that are erroneously not related to an object. Nevertheless, the following case is possible. Let a set H ⊆ M be the intent of an object such that 6 ∃g ∈ G : H ⊆ g 0 . In this case H 00 = M and the implication H → H 00 \ H has empty support. This is the case if an object is an error of the second class, because in its intent impossible in “real world” combination of attributes is contained. Although it is not the best solution, but we can ask an expert if the combination of attributes in object’s intent is con- sistent. In such a question we use information already input in the context, but an expert should consider all possible combinations of attributes to be excessive. Further on this question is not sufficient to reveal an error of the first class. A better idea would be to investigate the subset of object’s intent. Even if H 00 = M , we are still able to reveal an error of the first class, because we examine all possible dependencies on the subset of object’s intent that were satisfied by intents in the context. Searching through all the subsets of object’s intent leads to exponential time solution. Since we are only interested in such subsets that are contained in at least one intent in the context, we may consider only the intersections of object’s intent with intents in the context. This allows us to find errors of the first class in polynomial time. But we can do even better and replace the question about the consistency of set of attributes in object’s intent with an implication. This idea is better because in case of implication an expert is explicitly shown an attribute that breaks the dependencies satisfied in the context. For this purpose we should consider complementary context. If we investigate the closures of the subsets of initial object’s intent in the context K∪ := {G, M ∪ M , I ∪ I}, then we are also able to find errors of the second class in the very same manner, that we discussed before for the first class. Thus we are able to find all the errors of first three classes. 5.1 Pseudocode Below is presented the pseudocode of the method described above. inspect_with_negations(K:=(G, M, I), H⊆M) 1. Candidates = {object0 ∩H | object∈G} 2. Candidates = {candidate∈Candidates | 6 ∃c∈Candidates: candidate⊆c} 3. Result = ∅ 4. for candidate in Candidates: ∪ ∪ 5. if candidate0 0 != candidate: ∪ ∪ 6. Result.add(candidate → candidate0 0 \(candidate∪H)) 7. return Result H is the intent of an object to be added to the context K. In the first line we com- pute the set of all subsets that could produce desired implication. Since closure operator is monotone we may consider only maximal elements of Candidates. In the second line we discard all the non-maximal elements. In line 4 - 6 we check if closure differs from the intersection, i.e. there are attributes in conclusion of fu- ∪ ture implication. Here (·)0 denotes derivation operator of the context K∪ . There is no need to check if candidate00 is contained in H, because all the attributes from H\candidate are not contained in the intent of at least one object, from which this candidate was generated in the first line. It is possible to provide further optimisation. In the first line we can stop gener- ating Candidates after all the maximal subsets satisfying condition were found. 6 Results FCA package for Python written by Nikita Romashkin was used for implemen- tation [Rom]. The name inspect_dg is used to denote the function implementing the method described in Section 3. Inspecting Error1: inspect\_dg at least 3 different angles → at least 3 different legs all legs equal → has equal angles, has equal legs inspect\_with\_negation has equal legs, at least 3 different angles → at least 3 different legs, all legs equal has equal legs, all legs equal → has equal angles, at least 3 different angles Both implications in the result of v without overlined attributes in conclu- sions are deducible from the two implications in the result of inspect_dg. The two implications in the result of inspect_dg with the intent of Error1 added in the premise are deducible from the implications in the result of inspect_with_negation. Considering a particular object and corresponding implications we can always add object’s intent to the premise(s), because attributes from its intent are al- ways related to the object. Errors of the second class are not caught using canonical base. As described above such errors correspond to inconsistent in the context combination of at- tributes. Nevertheless, inspect_with_negation catches such errors. Inspecting Error2: inspect\_dg all angles equal → has equal angles, has equal legs, has right angle all legs equal → has equal angles, has equal legs inspect\_with\_negation has right angle, has equal legs, all legs equal, all angles equal → has equal angles In this example we are able to ask even less number of questions to the expert using inspect_with_negation as with inspect_dg. This is the result of finding implications generated by maximal subsets of object’s intent. Again, adding object’s intent to the premises of implications in the result of inspect_dg makes both groups mutually deducible. Inspecting Error3: inspect\_dg all angles equal → has equal angles, has equal legs, has right angle all legs equal → has equal angles, has equal legs inspect\_with\_negation has equal angles, has right angle, at least 3 different legs, at least 3 different angles → all angles equal, all legs equal has equal angles, has right angle, all legs equal, all angles equal → has equal legs, at least 3 different angles, at least 3 different legs The case of Error3 is more or less the same, as the case of Error1. The two groups of implications are mutually deducible under the same conditions as before. Inspecting Error4: inspect\_dg has equal angles, has equal legs, at least 3 different legs, all legs equal → has right angle, at least 3 different angles, all angles equal inspect\_with\_negation has equal angles, has equal legs, all legs equal → at least 3 different legs has equal angles, has equal legs, at least 3 different legs → all legs equal Error4 is a very special case when corresponding implication from canonical basis has empty support. In this case even if implication from the result of inspect_dg is rejected by an expert object may still be an error. This implication is in fact excessive, because the premise is not contained in any intent in the context and all attributes, that are not in premise, are in conclusion. Using inspect_with_negation we are able to ask an expert more sensible questions. Unfortunately, groups of implications are not deducible from each other in this example. 7 Conclusion An algorithm for finding errors in new objects of the context was proposed. As opposed to finding not respected implications in an implication basis proposed algorithm finishes in polynomial time. Moreover, in case of inconsistent combina- tion of attributes in object’s intent it is possible to state more sensible questions. In some cases the number of produced questions to an expert is less than the number of not respected implications in the canonical basis of the context. References [BK10] M. Babin and S. O. Kuznetsov. Recognizing pseudo-intent is conp-complete. Proc. 7th International Conference on Concept Lattices and Their Applica- tions, University of Sevilla, pages 294–301, 2010. [DS11] Felix Distel and Barış Sertkaya. On the complexity of enumerating pseudo- intents. Discrete Applied Mathematics, 159(6):450–466, 2011. [Gan84] B. Ganter. Two basic algorithms in concept analysis. Preprint-Nr. 831, 1984. [GD86] J.-L. Guigues and V. Duquenne. Familles minimales d’implications informa- tives résultant d’un tableau de données binaires. Math. Sci. Hum, 24(95):5–18, 1986. [GW99] B. Ganter and R. Wille. Formal Concept Analysis : Mathematical Founda- tions. Springer, 1999. [QED] The qed project. http://mizar.org/qed/. [RDB11] Uwe Ryssel, Felix Distel, and Daniel Borchmann. Fast computation of proper premises. In Amedeo Napoli and Vilem Vychodil, editors, International Con- ference on Concept Lattices and Their Applications, pages 101–113. INRIA Nancy – Grand Est and LORIA, 2011. [Rom] Nikita Romashkin. Python package for formal concept analysis. https://github.com/jupp/fca.