On Scaling of Fuzzy FCA to Pattern Structures Aleksey Buzmakov1 and Amedeo Napoli2 1 National Research University Higher School of Economics, Perm, Russia 2 LORIA (CNRS – Inria – University of Lorraine), Vandœuvre-lès-Nancy, France avbuzmakov@hse.ru, amedeo.napoli@loria.fr Abstract. FCA is a mathematical formalism having many applications in data mining and knowledge discovery. Originally it deals with binary data tables. However, there is a number of extensions that enrich stan- dard FCA. In this paper we consider two important extensions: fuzzy FCA and pattern structures, and discuss the relation between them. In particular we introduce a scaling procedure that enables representing a fuzzy context as a pattern structure. Studying the relation between dif- ferent extensions of FCA is of high importance, since it allows migrating methods from one extension to another. Moreover, it allows for more simple implementation of different extensions within a software. Keywords: fuzzy FCA, pattern structures, scaling 1 Introduction In this paper we deal with Formal Concept Analysis (FCA) and its extensions. FCA is a mathematical formalism having many applications in data mining and knowledge discovery. It starts from a binary table, a so-called formal context (G, M, I), where G is the set of objects, M is the set of attributes, and I ⊆ G×M is a relation between G and M , and proceeds to a lattice of formal concepts [1]. Fuzzy FCA is an extension of standard FCA that allows for fuzzy sets of objects and attributes in order to express uncertainty. Pattern structures is another extension of FCA that allows processing com- plex data, e.g., graph or sequence datasets. It is a quite general framework and the question if fuzzy FCA can be represented within Pattern Structures and vice versa is still open. In this paper we make a step in this direction and study the connections between pattern structures and fuzzy FCA. We show how a fuzzy context can be scaled to a “Minimum Pattern Struc- ture” (MnPS), a special kind of pattern structures, that is close to interval pattern structures when considering numerical data. A scaling is needed, since pattern structures deal with crisp sets of objects and, thus, fuzzy extents cannot be expressed within the formalism of pattern structures. For such a kind of scal- ing we add new objects to the fuzzy context that express objects with uncertain membership in fuzzy sets, allowing expressing fuzzy sets of objects in the for- malism of pattern structures. The resulting context is processed by MnPS. This kind of scaling is applicable to fuzzy FCA based on residuated lattices, a special kind of lattices expressing uncertain membership degrees in fuzzy sets. Table 1: A toy dataset of transactions for a supermaket and the related similarity matrix. (a) A dataset with 5 transactions. (b) Similarity matrix. i1 i2 i3 i4 i5 i6 i7 t1 t2 t3 t4 t5 t1 x x x x x t1 1.000 0.714 0.857 0.429 0.429 t2 x x x x x t2 0.714 1.000 0.571 0.429 0.429 t3 x x x x t3 0.857 0.571 1.000 0.286 0.714 t4 x x x t4 0.429 0.429 0.286 1.000 0.000 t5 x x x x t5 0.429 0.429 0.714 0.000 1.000 The rest of the paper is organized as follows. Section 2 describes a running example. Later, in Section 3 we introduce main definitions of fuzzy FCA and pattern structures. The main contribution of this paper is located in Section 4, where we introduce and discuss the scaling procedure of fuzzy FCA to pattern structures. Finally, at the end of the paper we discuss some related works. 2 Running Example Let us consider a toy dataset of transactions within a supermarket. It is shown in Table 1a. Every row corresponds to a basket bought by a customer and every attribute corresponds to an item that can be bought in the supermarket. A cross in a cell (i, j) means that in the basket i there is the item j. For making the example concrete, let us consider a clustering task. When dealing with clustering one typically needs a similarity or a distance measure. Such distance and similarity measures for the purpose of this example could be |t0 +t0 | the fraction of different items shared by two baskets Dist(t1 , t2 ) = 1|M |2 and Sim(t1 , t2 ) = 1 − Dist(t1 , t2 ), where operation ’+’ between sets is an exclusive OR (a so-called XOR or the symmetric difference, i.e., A+B = (A\B)∪(B \A)). The similarity measure for any pair of transactions is shown in Table 1b. For example, similarity between t1 and t2 is equal 0.714. These baskets are different in two items i4 and i5 . Thus Dist(t1 , t2 ) = 72 = 0.286, where 7 is the number of items in the supermarket, and Sim(t1 , t2 ) = 1 − Dist(t1 , t2 ) = 0.714. 3 Definitions Formal Concept Analysis (FCA) is a formalism for dealing with data mining and knowledge discovery tasks. It starts from a binary context (G, M, I), where G is the set of objects, M is the set of attributes and I ⊆ G × M is a relation between G and M . However, in real tasks such a binary encoding is too limited and several extensions of FCA were introduced. One of them is fuzzy FCA [2] that changes crisp sets into fuzzy sets. By doing so one is able to encode uncertainty. Another extension is pattern structures [3] dealing with crisp sets of objects but replacing binary sets of attributes with arbitrary descriptions allowing processing of many kinds of datasets, e.g., graph or sequential datasets. Below we discuss these two generalizations and their relation. 3.1 Fuzzy FCA Fuzzy FCA works with fuzzy logic instead of crisp-logic, used in standard FCA. There are several generalizations of FCA to the fuzzy case [2]. Here the approach of Belohlavek is considered [4]. In fuzzy logic formulas can be valid up to a certain degree. It means that the formula can be completely valid, completely invalid, or between these two states. This fuzziness in fuzzy FCA is represented by a so-called residuated lattice, where the top of the lattice > corresponds to “com- pletely valid” state of the logic and the bottom ⊥ corresponds to “completely invalid” state. Definition 1. A Residuated Lattice is an algebra L = hL, ∨, ∧, ⊗, , 0, 1i, where hL, ∨, ∧, 0, 1i is a complete lattice; hL, ⊗, 1i is a commutative monoid, i.e. ⊗ is commutative, associative, and ∀a(a ⊗ 1 = 1 ⊗ a = a); and ⊗ form an adjiont pair, i.e., a ⊗ b ≤ c ⇔ a ≤ b c. For the following, L refers to the set of elements of some residuated lattice and L for the residuated lattice itself. Such a lattice naturally appears when we want to introduce some degree of uncertainty. In the running example we introduced a similarity measure for any two objects. The values of the similarity can be considered as elements of the residuated lattice [0, 1], a linear order of real numbers. The lattice operators x ∧ y and x ∨ y are given by min(x, y) and max(x, y) correspondingly. The operations ⊗ and are “fuzzy conjunction” and “fuzzy implication”. An important residuated lattice based on a linearly ordered set is Göodel residuated lattice, which is used in examples of this paper. In Göodel residuated lattices the fuzzzy implication is defied as following:  >a≤b a b= (1) b a>b In the crisp logic the implication > → ⊥ is not valid, i.e., > → ⊥ = ⊥, while other three possible implications are valid, i.e., > → > = >, ⊥ → > = >, and ⊥ → ⊥ = >. The formula (1) generalizes this behavior. If the premise is less certain than the conclusion, then the implication is valid (>), otherwise the validity of the implication is equal to the certainty of the conclusion. In Definition 1 it is required that the fuzzy implication is adjoint (related) with an ⊗-operation. For Göodel residuated lattices the fuzzy implication is adjoint with a ⊗ b = min(a, b). Indeed, b c ≥ c according to (1). If a ⊗ b ≤ c, i.e., min(a, b) ≤ c and min(a, b) = a, then a ≤ c ≤ b c. If min(a, b) = b, then b ≤ c and a ≤ 1 = b c. Accordingly one can check that a ≤ b c ⇒ a ⊗ b ≤ c. ⊗-operation is called fuzzy conjunction since it is a generalization of the crisp conjunction that is valid only if both arguments are valid, i.e., > ⊗ > = >. A fuzzy dataset is encoded by means of a fuzzy context as defined below. Definition 2. A Fuzzy Relation between two sets X and Y is a function I : X × Y → L, for some residuated lattice L. Definition 3. A Fuzzy Context is a triple (X, Y, I) where X is a set of objects, Y is a set of attributes, I is a fuzzy relation, I : X × Y → L. Let us consider Table 1b as an example. It describes a fuzzy context where the set of attributes and the set of objects are the same. The cells of this table are similarity measures between objects. In this case the residuated lattice is formed as a linear order on similarity values. Let us now define what is a fuzzy set, the next building block of fuzzy FCA. Definition 4. Given a crisp set X, a fuzzy set A is a function A : X → L, mapping each element of the crisp set to an S element of the residuated lattice. A fuzzy set is denoted as {li ∈L /xi ∈X }, where xi = X, and for simplicity elements A(x ∈ X) = ⊥ are omitted. For example, {1 /t2 ,0.571 /t3 } is a fuzzy set. Object t2 belongs to this set entirely while object t3 belongs only partially. The other items do not belong to this set, i.e., A(g) = ⊥. Given our similarity measure we know that 1 ≡ > and 0 ≡ ⊥. In the fuzzy case of FCA one also defines Galois connections between a fuzzy set of objects A : X → L and a fuzzy set of attributes B : Y → L. Definition 5 (Derivation Operators). Given a fuzzy context (X, Y, I), a fuzzy set of objects A : X → L, a fuzzy set of attributes B : Y → L, the fuzzy membership for object x ∈ X and for attribute y ∈ Y in the corresponding sets A↑ and B ↓ are as follows: ^ A↑ (y) = (A(x) I(x, y)) ∀x∈X ^ ↓ B (x) = (B(y) I(x, y)) ∀y∈Y Let us illustrate the derivation operators. First let us introduce the fuzzy set of interest A = {1.0 /t1 ,1.0 /t2 } (all other objects do not belong to this set, i.e., they have “0” membership in that set). Then we would like to find A↑ . To compute A↑ we should compute A(x) I(x, y) for every object x ∈ X and for every attribute y ∈ Y (in the example we have a particular case where X ≡ Y ). According to our set of interest A(x) is either 1 or 0. For the function I(x, y), the first argument varies from row to row and the second argument varies from column to column. The result of these operations is shown in Table 2. For example, the result of computing A(t1 ) I(t1 , t2 ) is given in the first row second column cell. The last row of that table shows the resulting fuzzy set of Table 2: Example of computations for {1.0 /t1 ,1.0 /t2 }↑ . y t1 t2 t3 t4 t5 (A(t1 ) = 1) I(t1 , y) 1.000 0.714 0.857 0.429 0.429 (A(t2 ) = 1) I(t2 , y) 0.714 1.000 0.571 0.429 0.429 (A(t3 ) = 0) I(t3 , y) 1 1 1 1 1 (A(t4 ) = 0 I(t4 , y) 1 1 1 1 1 (A(t5 ) = 0) I(t5 , y) 1 1 1 1 1 {1.0 /t1 ,1.0 /t2 }↑ 0.714 0.714 0.571 0.429 0.429 Table 3: Example of computations for {1.0 /t1 ,1.0 /t2 }↑↓ . /t2 } ↑↓ t1 ) t2 ) t3 ) t4 ) t5 ) I (x, I (x, I (x, I (x, I (x, /t1 , 1.0 0.714 0.714 0.571 0.429 0.429 { 1.0 t1 1 1 1 1 1 1 t2 1 1 1 1 1 1 t3 1 0.571 1 0.286 1 0.286 t4 0.429 0.429 0.286 1 0 0 t5 0.429 0.429 1 0 1 0 the attributes (more precisely their membership degree). The value of the last row can be computed by applying ∧ operator of the residuated lattice to the whole column, and in the case of our example ∧ corresponds to the minimum. As the result of A↑ we obtained B = A↑ = {0.714 /t1 ,0.714 /t2 ,0.571 /t3 ,0.429 /t4 ,0.429 /t5 }. Let us now apply the derivation operator to the set A↑ . To find B ↓ = A↑↓ we need to compute B(x) I(x, y). The result of these operations is shown in Table 3 and should be read in the same way as Table 2. The last column corresponds to the result of B ↓ . Then we have: {1.0 /t1 ,1.0 /t2 }↑↓ = {1.0 /t1 ,1.0 /t2 ,0.286 /t3 } It can be checked that A↑↓↑ = B and A↑↓↑↓ = B ↓ = A↑↓ . These properties of the derivation operators defines fuzzy concepts [2]. Definition 6. A fuzzy concept is a pair (A, B), where A is a fuzzy set of objects, A : X → L and B is a fuzzy set of attributes B : Y → L, such that A↑ = B and A = B↓. In particular in the previous example we have found the concept: {1.0 /t1 ,1.0 /t2 ,0.286 /t3 }, {0.714 /t1 ,0.714 /t2 ,0.571 /t3 ,0.429 /t4 ,0.429 /t5 } .  (2) This concept can be interpreted in the following way. Every object from the extent is similar (with a certain degree of confidence) to an object from the intent by at least the corresponding membership degree, e.g., object t1 is similar to object t2 with confidence 1 (taken from the left membership degree of t1 ) by at least 0.714 (taken form the right membership degree of t2 ), while object t3 is similar with t2 by at least 0.714 with confidence only 0.286. In particular if on the extent side we consider objects with membership degree of 1 (>), e.g., t1 and t2 then we would find the similarity of all these objects to the rest of the objects, thus, providing a good description for a cluster around these objects. The set of fuzzy concepts is ordered such that (A, B) ≤ (X, Y ) iff A ⊆ X (or dually B ⊇ Y ) forming a complete lattice, called fuzzy concept lattice. 3.2 Pattern Structures A concept lattice L(G, M, I) is constructed from a (binary) formal context (G, M, I) [1]. For non-binary data, such as sequences or graphs, lattices can be constructed in the same way using pattern structures [3]. Definition 7. A pattern structure P is a triple (G, (D, u), δ), where G, D are sets, called the set of objects and the set of descriptions, and δ : G → D maps an object to a description. Respectively, (D, u) is a meet-semilattice on D w.r.t. u, called similarity operation such that δ(G) := {δ(g) | g ∈ G} generates a complete subsemilattice (Dδ , u) of (D, u). For illustration, let us represent standard FCA in terms of pattern structures. The set of objects G is preserved, the semilattice of descriptions is (℘(M ), ∩), where ℘(M ) denotes the powerset of the set of attributes M , a description is a subset of attributes and ∩ is the set-theoretic intersection. If x = {a, b, c} and y = {a, c, d} then x u y = x ∩ y = {a, c}, and δ : G → ℘(M ) is given by δ(g) = {m ∈ M | (g, m) ∈ I}. Derivation operator for a pattern structure (G, (D, u), δ), relating sets of objects and descriptions, is defined as follows: l A := δ(g), for A ⊆ G g∈A  d := {g ∈ G | d v δ(g)}, for d ∈ D Given a subset of objects A, A returns the description which is common to all objects in A. Given a description d, d is the set of all objects whose description subsumes d. The natural partial order (or subsumption order between descriptions) v on D is defined w.r.t. the similarity operation u: c v d ⇔ cud = c (in this case we say that c is subsumed by d). In the case of standard FCA the natural partial order corresponds to the set-theoretical inclusion order, i.e., for two sets of attributes x and y, x v y ⇔ x ⊆ y. Definition 8. A pattern concept of a pattern structure (G, (D, u), δ) is a pair (A, d), where A ⊆ G and d ∈ D such that A = d and d = A; A is called the pattern extent and d is called the pattern intent. As in standard FCA, a pattern concept corresponds to the maximal set of objects A whose description subsumes the description d, where d is the maximal common description of objects in A. The set of all pattern concepts is partially ordered w.r.t. inclusion of extents or, dually, w.r.t. subsumption of pattern in- tents within a concept lattice, these two anti-isomorphic orders form a lattice, called pattern lattice. Let us return to the example in Table 1b. Let us consider a special case of pattern structures, a so-called Minimum Pattern Structure (MnPS), that is close to interval pattern structures [5]. MnPS is based on the minimum of two numbers as the similarity operation rather than on the convex hull of two intervals. We will show that MnPS is well adapted for formalizing fuzzy FCA within the framework of pattern structures. In Table 1b we have the set G as both, a set of objects and a set of attributes. Let us first consider only one attribute. Then the set of descriptions D is just the interval [0, 1] of real numbers and the similarity operation between two de- scriptions (numbers) is the minimum. When there are several attributes, the set of descriptions is just an element of R|N | , where R is the set of real numbers and N is the set of numerical attributes. In particular, in our example the set of objects is G. The set D of descriptions is R5 , since we have 5 numerical attributes. The mapping function δ is given in Table 1b, e.g., δ(t2 ) = h0.714, 1, 0.571, 0.429, 0.429i. The similarity operation is the component-wise minimum, e.g., the similarity between descriptions of t2 and t3 is given by {t2 } u {t3 } = = h0.714, 1, 0.571, 0.429, 0.429i u h0.857, 0.571, 1, 0.286, 0.714i = = hmin(0.714, 0.857), min(1, 0.571), min(0.571, 1), min(0.429, 0.286), min(0.429, 0.714)i = h0.714, 0.571, 0.571, 0.286, 0.429i 4 From Fuzzy FCA to Pattern Structures with Scaling Let us now discuss a possible connection between fuzzy FCA and pattern struc- tures. A certain connection was already proposed in [6]. In particular, every crisply closed subset of objects is an extent of an interval pattern structure. Here, crisply closed subset of objects means that the fuzzy closure of this set contains no additional objects g with a membership degree coinciding with the top of the residuated lattice, i.e., A(g) = >. Here, we discuss a loss-less scaling from a fuzzy formal context (X, Y, I) to a pattern structure, that allows a more efficient processing than the loss-less scaling to crisp formal context and highlights another connection between fuzzy FCA and pattern structures. Since pattern structures can deal with any kind of descriptions, they should take into account fuzziness on the intent side. However, for the extent side it Table 4: Scaling of the fuzzy context from table Table 1b to a number-minimum pattern structure. t1 t2 t3 t4 t5 t1 t2 t3 t4 t5 ht1 , 1.000i 1.000 0.714 0.857 0.429 0.429 ··· ht1 , 0.857i 1.000 0.714 1.000 0.429 0.429 ht3 , 0.429i 1.000 1.000 1.000 0.286 1.000 ht1 , 0.714i 1.000 1.000 1.000 0.429 0.429 ··· ··· ht4 , 1.000i 0.429 0.429 0.286 1.000 0.000 ht2 , 1.000i 0.714 1.000 0.571 0.429 0.429 ··· ··· ht4 , 0.286i 1.000 1.000 1.000 1.000 0.000 ht2 , 0.571i 1.000 1.000 1.000 0.429 0.429 ··· ··· ht5 , 1.000i 0.429 0.429 0.714 0.000 1.000 ht3 , 1.000i 0.857 0.571 1.000 0.286 0.714 ··· ··· ht5 , 0.286i 1.000 1.000 1.000 1.000 0.000 is not so straightforward, since pattern structures deal only with crisp sets of objects. Accordingly, we should somehow “scale” object sets, in order to express fuzzy sets of objects. 4.1 On expressing Fuzziness on the Extent Side of Pattern Structures A natural way is to scale the object set X from a fuzzy context (X, Y, I) by sub- stituting it with the direct product of the crisp set of objects and the residuated lattice (the degrees of confidence), X × L. For every scaled object from this new set, we should compute a description. Let us consider the scaled description for the pair hx, li, where x ∈ X is an object and l ∈ L is the membership degree of this object. The description of this element should correspond to the description of the fuzzy set {l /x }, since hx, li is “a model of” this fuzzy set. The derivation operator {l /x }↑ (y ∈ Y ) = {l /x }(x) I(x, y) = l I(x, y) gives the description of the element hx, li and allows computing the fuzzy relation I˜ between X × L and Y . Let us return to our example. Let T be the set of transaction IDs. The scaled fuzzy context is partially shown in Table 4. It consist of |T | · |L| = 5 · 7 = 35 objects, 5 attributes and the fuzzy relation between them. Every subset of objects corresponds to a fuzzy set of objects by joining corresponding fuzzy representation for every object. This is made precise in the next subsection. 4.2 Relation between fuzzy and pattern extents and intents Let (X, Y, I) be a fuzzy context with a residuated lattice L and (G, D, δ) be a pattern structure, where G is the scaled set of objects G = X × L. Let us formally define the correspondence between fuzzy sets of objects and scaled sets of objects. Definition 9 (Object sets equivalence). A fuzzy object set A : X → L is equivalent to a scaled object set N ⊆ G, denoted as A ∼ N , when (∀hx, li ∈ G)(A(x) ≥ l ⇔ hx, li ∈ N ) Then object sets are equivalent when all scaled objects with membership degree smaller than or equal to A(x) (w.r.t. the residuated lattice) are present in the scaled object set. For example, the fuzzy set {0.286 /t1 ,0.429 /t4 } is equivalent to the scaled set {ht1 , 0.286i, ht4 , 0.429i, ht4 , 0.286i}3 , where hg, li ∈ X × L is an element of the direct product of the set of objects and the residuated lattice. Given a scaled fuzzy context (X × L, Y, I) ˜ we can process it as a minimum pattern structure (X × L, D, δ), where D = L|Y | is a tuple of elements from the residuated lattice L and the semilattice operation is given by the component- wise infimum of L. In particular, we have discussed that for the numerical case, the similarity operation is the component-wise minimum. Indeed, fuzziness on the extent side is expressed by means of scaled object sets, and fuzziness on the intent side is directly processed by the pattern structure. Let us discuss the correspondence between fuzzy intents and patterns. Definition 10. A fuzzy attribute set B : Y → L is equivalent to a pattern d ∈ D, written as B ∼ d, iff (∀y ∈ Y )(B(y) = d(y)), where d(y) is the value of the tuple d corresponding to the attribute y. A fuzzy attribute set B is equivalent to a pattern d iff for any attribute y ∈ Y , the membership degree B(y) in the fuzzy set is equal to the value in the pattern tuple in the position corresponding to the attribute y, e.g., the pattern h0.5, 0.7i corresponds to the fuzzy set {0.5 /y1 ,0.7 /y2 }. It should be noticed that the definition of equality between fuzzy sets of attributes and patterns is a bijection, while there are scaled sets of objects that have no equivalent fuzzy set of objects. Indeed, there is no equivalent fuzzy set to the scaled set {ht1 , 0.286i, ht4 , 0.429i}, since according to Definition 9 all hx, li such that A(x) ≥ l should be in this set. And since we have ht4 , 0.429i in this set, we should also have ht4 , 0.286i in the set. We can notice here that in our particular example the residuated lattice has only the element 0.286 that is smaller than 0.429. By contrast, if we take the real interval [0, 1], then all points smaller than 0.429 should be added to the scaled set. Let us define equivalence classes of scaled sets of objects in order to have a bijection between the equivalence classes and the fuzzy sets of objects. Definition 11. A scaled object set N ⊆ G is complete iff a scaled object hx ∈ X, l ∈ Li belongs to N , then (∀l∗ ∈ L, l∗ ≤ l)hx, l∗ i ∈ N . It can be checked that for any scaled object set N ⊆ G there is only one minimal complete superset of N . Let us denote this complete set by φ(N ). For example, the set N = {ht1 , 0.286i, ht4 , 0.429i} is not complete, since the scaled object ht4 , 0.286i is not in N . By contrast, Nc = φ(N ) = {ht1 , 0.286i, ht4 , 0.429i, ht4 , 0.286i} is complete. Moreover, it can be seen that this set is equivalent to {0.286 /t1 ,0.429 /t4 } according to Definition 9. Furthermore, it can be checked, that any complete scaled set of objects is equivalent to a fuzzy set and accordingly the function φ(·) defines the required equivalence classes. 3 We notice that ht4 , 0.429i and ht4 , 0.286i are two different scaled objects. 4.3 Isomorphism of fuzzy and pattern lattices In this subsection we show that our scaling procedure is correct. And the result- ing pattern lattice and the fuzzy lattice are isomorphic. Moreover, the extents and intents of these lattices are connected by means of Definitions 9 and 10. The first lemma (a standard property of residuated lattices) shows that fuzzy implications are related if their premises are comparable. Lemma 1 If there are l1 , l2 , l ∈ L such that l1 ≤ l2 then l1 l ≥ l2 l Proof. Let l2 l = r then according to Def. 1: (∀f ∈ L, f ≤ r)(f ⊗ l2 ≤ l) ⇔ (∀f ≤ r)(l2 ⊗ f ≤ l) ⇔ (∀f ≤ r)(f l ≥ l2 ≥ l1 ) ⇔ (∀f ≤ r)(l1 l ≥ f ) ⇒ l1 l ≥ r. Let us now show that starting from two (fuzzy and scaled) equivalent sets of objects the resulting descriptions are also equivalent. Lemma 2 Given a fuzzy set of objects A : X → L and a scaled set of objects N ⊆ G, such that A ∼ φ(N ), we have A↑ ∼ N  .  Proof. Consider d the value of the pattern tuple N corresponding to an attribute  y: N (y) = ∀g∈N δ(g) (y). The semilattice operation of the minimum pattern structure corresponds to the infimum in the residuated lattice: ^ ^ N  (y) = ˜ I(hx, li, y) = l I(x, y) = ∀hx,li∈N ∀hx,li∈N  ^   ^  = A(x) I(x, y) ∧ l I(x, y) = ∀x∈X ∀hx,li∈N :l