Classi cation of possible errors in formal contexts is given and the possibilities of exploring them are discussed. An approach for nding errors of some classes in formal contexts is introduced. This approach may be used in attempt to nd errors in an object that is to be added to the context. The idea is based on nding 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 nd solution in polynomial time and deal with inconsistent combination of attributes. Examples are provided.
The work is motivated by the idea of building multi-user system based on Formal Concept Analysis methods. It would be di erent 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 nding tools are absolutely necessary. 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 nd errors in new objects based on the information already in the context. This is actually the rst step to building error nding tools.
Consider mappings ' : 2G ! 2M and : 2M ! 2G: '(A) := fm 2 M j gIm for all g 2 Ag; (B) := fg 2 G j gIm for all m 2 Bg: For any A1; A2 G, B1; B2 M one has Mappings ' and de ne 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 2 G the set g0 = fm 2 M jgImg is called an intent of g and is denoted int(g). Similarly, for attribute m 2 M the set m0 is called an extent of m and is denoted ext(m). Let M = fm j m 2 M g and I = f(g; m) j g 2 G; m 2 M; (g; m) 2= Ig. Triple K := (G; M ; I) is called a complementary (formal) context.
Let B M; g 2 G; B := fb j b 2 Bg. 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 de ned 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 B0, 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 ! X ;
X ! Y X [ Z ! Y ;
X ! Y; Y [ Z ! W
X [ Z ! W A support of an implication is the set of object, whose intents respect this implication.
An implication basis of context K is de ned 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 de ned 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 pseudointent Q such that Q P , one has Q00 P . Canonical implication basis looks then as follows: fP ! (P 00 n P ) j P - pseudo-intentg. 3
Every object in the context is described by the set of attributes, that are related 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 object M is not respected by an 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 (de nitions of reducible objects and lattices of contexts are not given in this paper for the sake of compactness, for de nitions 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 de nition. 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 rst class are caught using this approach. 4
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 de nitely 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. fError 1ge =fhas equal legs, at least 3 di erent angles, all legs equalg fError 1ge00 =fall angles equal, all legs equal, at least 3 di erent angles, at least 3 di erent legs, has equal angles, has equal legs, has right angleg
t t la reen reen seg legan legan lau equ id id l l l q s 3 3 a a t e le equ equ irgh seg gan ltsea ltsea sah sah sah llla lla ta ta
Error4 s e lagn lseg t t la reen reen s seg legan legan lau equ id id l l l q s 3 3 a a t e le equ equ irgh seg gan ltsea ltsea sah sah sah llla lla ta ta
Fig. 2. Context of errors Ke
Canonical basis of the context on Fig. 1 looks as follows: 1. at least 3 di erent angles ! at least 3 di erent 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 di erent legs ! at least 3 di erent angles 5. has equal angles, has equal legs, at least 3 di erent legs, all legs equal ! has right angle,at least 3 di erent angles, all angles equal 6. has equal angles, has equal legs, at least 3 di erent legs, all angles equal, has right angle, at least 3 di erent angles ! all legs equal 7. has right angle, has equal legs, all legs equal, has equal angles ! all angles equal
Consider Error2. fError 2ge =fhas equal legs, has right angle, all legs equal, all angles equalg 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
Although this approach gives the needed result, there are some problems remaining. The problem of producing canonical basis with known algorithms is intractable. Recent theoretical results suggest that existing approaches for computing the stem base may not lead to algorithms with better worst-case complexity [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 minimal yet su cient 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 context 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 9g 2 G : H g0. In this case H00 = M and the implication H ! H00 n 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 consistent. 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 su cient to reveal an error of the rst class. A better idea would be to investigate the subset of object's intent. Even if H00 = M , we are still able to reveal an error of the rst class, because we examine all possible dependencies on the subset of object's intent that were satis ed 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 nd errors of the rst 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 satis ed 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[ := fG; M [ M ; I [ Ig, then we are also able to nd errors of the second class in the very same manner, that we discussed before for the rst class. Thus we are able to nd all the errors of rst 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 = fobject0\H | object2Gg 2. Candidates = fcandidate2Candidates |
6 9c2Candidates: candidate cg 3. Result = ; 4. for candidate in Candidates: 5. if candidate0[0[ != candidate:
6. Result.add(candidate ! candidate0[0[ n(candidate[H)) 7. return Result H is the intent of an object to be added to the context K. In the rst line we compute 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 di ers from the intersection, i.e. there are attributes in conclusion of future 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 Hncandidate are not contained in the intent of at least one object, from which this candidate was generated in the rst line.
It is possible to provide further optimisation. In the rst line we can stop generating Candidates after all the maximal subsets satisfying condition were found. 6
FCA package for Python written by Nikita Romashkin was used for implementation [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 di erent angles ! at least 3 di erent legs all legs equal ! has equal angles, has equal legs inspect\_with\_negation has equal legs, at least 3 di erent angles ! at least 3 di erent legs, all legs equal has equal legs, all legs equal ! has equal angles, at least 3 di erent angles Both implications in the result of v without overlined attributes in conclusions 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 always 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 attributes. 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 nding 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 di erent legs, at least 3 di erent 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 di erent angles, at least 3 di erent 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. inspect\_dg has equal angles, has equal legs, at least 3 di erent legs, all legs equal ! has right angle, at least 3 di erent angles, all angles equal inspect\_with\_negation has equal angles, has equal legs, all legs equal ! at least 3 di erent legs has equal angles, has equal legs, at least 3 di erent 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
An algorithm for nding errors in new objects of the context was proposed. As opposed to nding not respected implications in an implication basis proposed algorithm nishes in polynomial time. Moreover, in case of inconsistent combination 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.