In this paper we discuss how biresiduations provide a unifying paradigm for fuzzy formal concept analysis and mathematical morphology. In particular we provide constructions of morphological operators such as dilation and erosion within the framework of convolution algebras of action networks (also known as small covariant categories) over join complete semirings. This uni es and generalizes previous contributions in mathematical morphology, such as the work of Isabelle Bloch. Further we show how decomposition, factorization, and hedges naturally align themselves in the framework of fuzzy formal concept analysis.
In our paper we outline the fundamental role of biresiduation in combination with biadditivity for a common view on fuzzy FCA and mathematical morphology. While the concept of biresiduation is an important paradigm of algebraic logic, the concept of biadditivity is rooted in linear algebra (over complete monoids and complete semirings). The close relationship between both approaches is re ected in the bijective correspondence of the residuated complete lattices and the join complete semirings on a xed set. Our considerations yield a major application for a better understanding of mathematical morphology: We achieve this by constructing and investigating convolution algebras of action networks over join complete semirings. Finally, as a tool for information reduction, we also discuss the role of hedges on residuated complete lattices and their relationship with substructures of join complete semirings, and more generally within the category of biadditive setups.
Important literature for (fuzzy) FCA is given by [
Over the last two decades, major contributions to mathematical morphology go
back to Isabelle Bloch [
2
One of the key concepts for accessing FCA and its generalizations is that of a biresiduated map. We start by recalling the de nition of a residuated map. De nition 1 (residuated map, adjunction). Let P1 := (P1; ) and P2 := (P2; ) be ordered sets. Then a map f : P1 ! P2 is residuated from P1 to P2 if there exists a map f + : P2 ! P1 such that Here, the map f + is uniquely determined by f and is called the residual of f . The pair (f; f +) is called an adjunction w.r.t. (P1; P2). In case P1 = P2, we will say that (f; f +) forms an adjunction on P1.
Remark 1. A map between complete lattices is residuated if and only if it is completely join preserving, that is, f (sup X) = sup(f X) holds for all X P1 in the above setting.
De nition 2 (biresiduation). Let P1 := (P1; ), P2 := (P2; ), and P := (P; ) be ordered sets. Then a map such that p1 (p p2) () (p1 p2) p () p2 holds for all p1 2 P1, p2 2 P2, and p 2 P .
In case P1 = P2 = P, we say that forms a biresiduation w.r.t. P. If in addition (P; ; ") is a monoid then (P; ; ") will be referred to as residuated ordered set. If in particular P forms a complete lattice, (P; ; ") is a residuated complete lattice. Remark 2. A biresiduation is characterized as a map which is residuated in both arguments. In particular a biresiduation is isotone in each argument. will be called a biresiduation w.r.t. P := (P1; P2; P) if there exist maps : P1
P2 ! P ! : P1 : P
P ! P2 P2 ! P1 Example 1. Any two sets G and M give rise to a biresiduation as follows: The map : 2G 2M ! 2G M ; (A; B) 7! A
B is a biresiduation w.r.t. (2G; 2M ; 2G M ), where 2G denotes the power set lattice of G. This follows immediately since power set lattices are complete with the supremum operation as set union. In particular for I G M we consider the context (G; M; I): For all A G and all B M we have where
(A
B) () A (B !
) (B !
) = [fH (
A) = [fN
G j H M j A
B N g = B0: g = A0: We have recaptured the derivation operators of classical formal concept analysis as residuals of a speci c biresiduation, the cartesian product.
Now, it is worth noting the connection between cartesian product and dyadic product as used in linear algebra. We recall the de nition of a dyadic product. Given two n-dimensional vectors u; v over a semiring S we can de ne the dyadic product as u
v := u vT where the second multiplication is simply matrix multiplication. If S is the wellknown boolean 2-element semiring, the dyadic product resembles exactly the cartesian product. So, in a sense, the dyadic product generalizes the cartesian product. From our point of view, this is key to understanding fuzzy concept analysis in terms of biresiduations.
Example 2 (t-Norm). A binary operation on the real unit interval [0; 1], which is isotone in both arguments, is called t-Norm if for all a; b; c 2 [0; 1] the following hold:
arbitrary index set) the following holds: 2 [0; 1]I (where I is an From the terminology introduced above, a map : [0; 1] [0; 1] ! [0; 1] is a left continuous t-norm if and only if ([0; 1]; ; ; 1) forms a residuated complete lattice. Among the various left continuous t-norms we point out the Godel t-notm and the Lukasiewicz t-norm These t-norms will be used in our visualizations for mathematical morphology in gure 1 and 2.
In the next section, we will highlight that residuals of a biresiduation play a crucial role in FCA and its abstractions. 3 Let P1 := (P1; ); P2 := (P2; ) and P = (P; ) be ordered sets and uation w.r.t. (P1; P2; P). We de ne a biresidto be its set of formal rectangles. If f := P1
P2
K := ( ; ) is called an abstract context w.r.t. (P1; P2; P). Given such an abstract context we can de ne the set of formal rectangles w.r.t. K as f
K := f(u; w) 2 f j u w g: On a formal rectangle, we can apply our biresiduation operation to yield an (actual) rectangle. We de ne to be the set of (actual) rectangles w.r.t. K and
K := fu
w j (u; w) 2 f Kg
K mf := max f
K to be the set of maximal rectangles regarding the product order on P1 de ne the set of abstract concepts as P2. We BK := f(u; w) 2 P1 In case (P1; P2; P) is a triple of complete lattices, BK forms a complete lattice, called the abstract concept lattice of K.
As usual in FCA, let us abbreviate u ! as u0, the derivation of u w.r.t. K := ( ; ), and similarly, w as w0. We show that even in our rather abstract setting we can talk about maximal rectangles being the abstract concepts. Proposition 1. Let K := ( ; ) be an abstract context w.r.t. (P1; P2; P) and de ne : P1 ! P; x 7! (x00; x0) and : P2 ! P; x 7! (x0; x00). Then
K 1. BK = im( ) = im( ) 2. mf
= BK We call (p1; p2) 2 f (p1; p2) 2 mf
a decomposition of K if p1
K we call (p1; p2) a conceptual decomposition of K.
p2 =
K Corollary 1. Let K = ( ; ) be an abstract context w.r.t. (P1; P2; P). If (p1; p2) is a decomposition of K there exists a conceptual decomposition (q1; q2) of K with p1 q1 and p2 q2. . If additionally Proof. For instance, set (q1; q2) := (p1). 4
We complement the approach sketched above (where ordered sets are used as
basic structures) by using complete monoids [
i2I Remark 3. For every complete lattice L := (L; ) let A(L) := (L; +; 0; ) be the join complete monoid, where x + y := supLfx; yg for all x; y 2 L and 0 := supL; and := supLf (i) j i 2 Ig for every index set I and all 2 LI . If on the other hand, A := (A; +; 0; P) is a join complete monoid then L(A) := (A; ) is a complete lattice, provided x y :, x + y = y for all x; y 2 A. This observation establishes for every set A a bijective correspondence between all complete lattices on A and all join complete monoids on A.
L := (L1; L2; L) is a triple of complete lattices then A(L) := (A(L1); A(L2); A(L)).
De nition 5 (biadditive map). Let A := (A1; A2; A) be a triple of complete monoids. Then a biadditive map w.r.t. A is de ned as a map : A1 A2 ! A such that = (i;j)2I J i j holds for all 2 AI1 and
2 A2J for arbitrary index sets I; J .
De nition 6 (biadditive setup, morphism). Let A := (A1; A2; A) be a triple of complete monoids and let be a biadditive map on A. Then we call the pair (A; ) a biadditive setup. In case A1 = A2 = A, we say that is a biadditive operation on A, and (A; ) forms a biadditive setup.
Given two biadditive setups (A; ) and (U; ) we call := ('1; '2; ') a morphism from (U; ) to (A; ) if '1; '2; ' are morphisms from U1; U2, and U to
'1(u1) '2(u2) = '(u1 u2): Biadditive setups and their morphisms obviously form a category. In particular, (U; ) is a substructure of (A; ) if U1; U2, and U are complete submonoids of A1; A2, and A, respectively, and U1 U2 U . Clearly, The image of a morphism induces a substructure.
De nition 7 (complete semiring). A tuple R := (R; +; ; 0; 1; P) is a complete semiring if the following properties are satis ed: (1) Radd := (R; +; 0; X) is a complete monoid, (2) Rmult := (R; ; 1) is a monoid with 1 6= 0, (3) the following distributive laws hold for all a 2 R, 2 RI : a (X (X i2I i) i) = a =
X(a i2I X( i
Remark 5. If R := (R; +; ; 0; 1; P) is a given join complete semiring then L(R) := (L(Radd); ; 1) forms a complete residuated lattice. If on the other hand L := (L; ; ") with L = (L; ) is a given residuated complete lattice then R(L) := (L; +; ; 0; "; P) with (L; +; 0; P) := A(L) is a join complete semiring. This establishes a bijection between all join complete semirings on a set R and all complete residuated lattices on R. In particular for every join complete semiring R := (R; +; ; 0; 1; P) there exist maps ! and from R R to R such that for all r; s; t 2 R the following holds: r (t s) () (r s) t () s (r ! t) A more extensive discussion of the interplay between biresiduation and biadditivity will be presented in section 6.
Proposition 2. Let (A; ) be a biadditive setup where A := (A1; A2; A). For sets G and M de ne : A1G A2M ! AG M where (u w)(g; m) := u(g) w(m): Then forms a biadditive map w.r.t. (A1G; A2M ; AG M ) which is also known as the dyadic product.
Proposition 3. Let (A; ) be a biadditive setup where A := (A1; A2; A). For sets G, H, and M de ne : AG H 1
AH M 2 ! AG M where ( )(g; m) := h2H (g; h) (h; m): Then forms a biadditive map w.r.t. (A1G H ; A2H M ; AG M ) { which, as a matter of fact, is the matrix product.
If (A; ) is a biadditive setup where A := (A1; A2; A) and 2 A then a familiy (uh; wh)h2H 2 (A1 A2)H will be called a sum-decomposition of ( ; ) if = h2H uh wh:
Proposition 4. Let (A; ) be a biadditive setup where A := (A1; A2; A). Then for sets G, H, M and 2 AG M the following holds
Remark 6. An important situation where this proposition can be applied occurs when R = (R; +; ; 0; 1; ) is a complete semiring, since then (Radd; ) is a biadditive setup as already mentioned in remark 4.
In mathematical morphology the concept of dilation is fundamental, and crucially involves convolution in a general setting which will be layed out in the following. 5
The ingredients of our modelling approach for the construction of convolution algebras are action networks and complete semirings. For this we still need to introduce networks and action networks.
De nition 9 (network). A triple G := (V; E; %) will be called a network (directed multigraph) if V and E are sets and % : E ! V V is a map. In this context we interpret V as the set of nodes, E as the set of edges, and % as the structure map of G.
Additional Remark: The structure map % of G induces two maps : E ! V; e 7! : E ! V; e 7! e e and e e e satisfying %e = ( e; e) for all e 2 E; here we consider e as source node and e as target node of e.
A pair of edges (c; d) will be called sequential if the target node of c is equal to the source node of d. The set of all sequential pairs of edges will be denoted by Eh2i. Similarly Eh3i will denote the set of all triples of edges (c; d; e) such that (c; d) and (d; e) are sequential pairs.
Next we consider networks with additional structure. In this situation, edges will be interpreted as actions which allow concatenation of sequential pairs of actions.
De nition 10 (action network). A triple G := (G; ; id) will be called an action network (small covariant category ) if G := (V; E; %) is a network and : Eh2i ! E; (c; d) 7! c d and id : V ! E are maps satisfying: %(c d) = ( c; d) for all (c; d) 2 Eh2i (c d) e = c (d e) for all (c; d; e) 2 Eh3i %(idp) = (p; p) for all p 2 V id( c) c = c = c id( c) for all c 2 E: We interprete E as set of actions and as concatenation map, which maps every sequential pair of actions (c; d) to its concatenation c d. Furthermore, idp denotes the passive action at node p.
Example 3. Any monoid M := (M; ; ") can be interpreted as action network with f"g as the singleton node set, M as the set of edges, and as concatenation map as well as id : f"g ! M , " 7! ". b Example 4. Any preordered set P := (P; R) can be interpreted as action network which has (P; R; ) as underlying network, where : R ! V V; (p; q) 7! (p; q), and : Rh2i ! R; ((p; t); (t; q)) 7! (p; q) as concatenation map and furthermore id : P ! R; p 7! (p; p) as passivity map.
Construction 1 (convolution algebra). Let R := (R; +; ; 0; 1; P) be a complete semiring and let G := (G; ; id) be an action network with underlying network G := (V; E; %); then the convolution algebra of G over R is given by
R[G] := (RE ; +; ; O; I; X); where for every index set I for all i 2 I and ui; u; w 2 RE as well as e 2 E the following hold: a " a+b with SplitG(e) := f(c; d) 2 Eh2ijc d = eg and (u + w)e := ue + we (X ui)e :=
X(uie) i2I (u w)e := i2I
X (c;d)2SplitG(e)
uc wd O : E ! R; e 7! 0
(1 for e 2 idV I : E ! R; e 7! 0 otherwise
convolution of u with w. w will be called the Remark 8. In case M := (M; ; ") is a monoid then R[M] is de ned as R[G] where G is the action network associated with M and R[M]. 6
The following fact will help us to combine biresiduation and biadditivity, which will be relevant for fuzzy FCA and also for mathematical morphology: Proposition 5. Let L := (L1; L2; L) be a triple of complete lattices and let : L1 L2 ! L be a map. Then is biresiduated w.r.t. L if and only if is biadditive w.r.t. A(L).
Theorem 1. Let L := (L1; L2; L) be a triple of complete lattices and let a biresiduation w.r.t. L. Then for sets G, R, and M the following holds: be Also, for all g 2 G and u
( ( w) () (u w) () w (u ! ): w)(g) = infL1 f (g; m)
w(m) j m 2 M g (u ! )(m) = infL2 fu(g) ! (g; m) j g 2 Gg
for all m 2 M .
is a biresiduation w.r.t. (L1G H ; L2H M ; LG M ).
Hence, for all 2 L1G H and 2 L2H M and 2 LG M we have () () ! :
for all (g; h) 2 G
H and for all (h; m) 2 H and : G
H ! L1; (g; h) 7! uh(g) : H
M ! L2; (h; m) 7! wh(m) is a conceptual decomposition of K. If ( ; ) is a conceptual decomposition of K then, by de nition, = and = ! .
Proof. Part 1 follows from Propositions 5 and 2. Part 2 follows from Propositions
5 and 3. Part 3 follows from Proposition 5 and 4 together with Corollary.
The above theorem extends Theorem 6 from [
Remark 9. Referring to remark 6, the last theorem is connected with fuzzy formal concept analysis in the following way: Let R := (R; +; ; 0; 1; ) be a join complete semiring. Then for sets G; M and 2 RG M , the triple (G; M; ) will be regarded as fuzzy context over R having the same concept lattice as the abstract context ( ; ) w.r.t. (LG; LM ; LG M ) for L := L(Radd). Also the decomposition discussed in the third part of the above theorem applies to this situation.
If we restrict ourselves to the situation of M being a singleton, Theorem 1.1 yields for all r 2 R and u; v 2 RG u r v () r (u ! v); that is, u ! v can be interpreted as the degree of u being a subset of v. Theorem 2. For every complete semiring R := (R; +; ; 0; 1; P) and every action network G := (G; ; id) with G := (V; E; %) the convolution algebra R[G] is a complete semiring.
In case R is join complete then so is R[G]; consequently (L(RE; +; O; P); ; I) forms a residuated complete lattice, and for all u; w 2 RE and all d 2 E it follows
(u ! w)d = inffuc ! w(c d) j c 2 E : (c; d) 2 Eh2ig: Proof. Straightforward calculation yields that R[G] is a complete semiring, which is join complete if R is join complete.
In the latter, it remains to show that for all u; v; w 2 RE the following holds: 8d 2 E : vd
(u ! w)d ,v (u ! w) ,(u v) w ,8e 2 E :
X (c;d)2Split(e) uc vd
we ,8e 2 E; 8(c; d) 2 Split(e) : uc vd we ,8(c; d) 2 Eh2i : uc ,8(c; d) 2 Eh2i : vd vd
w(c d) uc ! w(c d) ,8d 2 E : vd
inffuc ! w(c d) j c 2 E : (c; d) 2 Eh2ig
(u ! w)d = inffuc ! w(c d) j c 2 E : (c; d) 2 Eh2ig for all d 2 E: Construction 2 (dilation and erosion). Let R := (R; +; ; 0; 1; P) be a join complete semiring and G := (G; ; id) be an action network with G := (V; E; %). Then an element 2 RE will be considered as structuring element of G over R, and the map : RE ! RE ; 7! ( ) is called the dilation via the structuring element and the map " : RE ! RE ; 7! ( ! ) is the erosion via the structuring element . In this setting, 2 RE often plays the role of an image, the dilation of which via the structuring element is given by
): (" ) = ( ! ): Remark 10. Here, the pair ( ; " ) is an adjunction on L(RE ; +; O; P). A signi cant application of mathematical morphology is photo editing. Here we visualize dilation and erosion by using convolution algebras induced via the t-norms introduced previously.
original
Structuring element dilation
erosion Remark 11 (fuzzy FCA). Referring to construction 2, let R := (R; +; ; 0; 1; P) be a given join complete semiring and G := (G; ; id) be an action network with G := (V; E; %). In this situation, an element 2 RE will be considered as input image and an element 2 RE will be regarded as structuring element. Then := ( ! ) is the erosion of via . From the viewpoint of fuzzy FCA, is the derivation of in the abstract context K := ( ; ) w.r.t. (LE ; LE ; LE ) for L := L(Radd). 7
Isabelle Bloch has been one of the key scientists in developing mathematical
morphology and its fuzzi cations during the past 20 years (for example we mention
[
Let S := (S; +; O) be a commutative group and : [0; 1] [0; 1] ! [0; 1] a left continuous t-norm. Then Isabelle Bloch de nes the dilation via a structuring element : S ! [0; 1] as : [0; 1]S ! [0; 1]S ;
7! " : [0; 1]S ! [0; 1]S ; 7! " where where (" )x := inff (y x) ! y j y 2 Sg for all x 2 S: Here is the dilation of the image via the structuring element , and " is the erosion of the image via the structuring element . Indeed, Bloch proves that the pair ( ; " ) forms an adjunction on ([0; 1]; ).
Remark 12. By theorem 2 it follows immediately that ( ; " ), as introduced by Bloch, forms an adjunction on ([0; 1]; ): Indeed, theorem 2 implies for the complete semiring R := ([0; 1]; _; ; 0; 1; sup) that the pair ( ; " ) forms an adjunction on R[S], that is, on L(R[S]).
In our nal section we will discuss hedges and their role for information reduction. ( )x := supf (x y) y j y 2 Sg for all x 2 S:
Hedges were introduced as parameters controlling the size of a fuzzy concept
lattice [
Theorem 3. Let L = (L; ; ") be a residuated complete lattice. Then its hedges are in one-to-one correspondence with the substructures of the join-complete semiring R(L).
Proof. Since hedges are kernel operators they are in one-to-one correspondence with their kernel systems (a hedge is mapped to its image set L ). Let be a hedge on L. We will show that its image set L forms a substructure (join-complete sub-semiring) of R(L). We know already that L is closed under joins, that 1 = 1 2 L , and that 0 = 0 2 L . To show that L is closed under we will verify that a b = (a b) holds for all a; b 2 L ; it su ces to prove a b (a b) : Since a = a and b = b we conclude the argument.
Let K be a substructure of a given join-complete semiring R(L). Since K is closed under arbitrary joins it forms a kernel system in L inducing its kernel operator . Thus, K = L and 1 2 L . It remains to be shown that implications are weakly preserved by : () =) a a (a ! b) (a ! b) (a ! b) (a ! b) b b
get a (a ! b) b , which implies (a ! b) (a
! b ). (a ! b) is a kernel and we Remark 13 (construction of hedges via substructures). Let G := (G; ; id) be an action network with G := (V; E; %). We say that a subset D of E forms a substructure of G if idV D and c d 2 D holds for all (c; d) 2 Dh2i. If R := (R; +; ; 0; 1; P) is a complete semiring and D forms a substructure of G, then the set
U := fu 2 SE j ue = 0 for all e 2 E n Dg forms a substructure of the complete semiring R[G]. In case R is a join complete semiring, the hedge associated with U is given by
: RE ! RE ; u 7! uD where uDe := ue for all e 2 D and uDe := 0 for all e 2 E n D.
One application of the above for mathematical morphology is when the action network is given by Zadd and the substructure is D := 2Z2, where the join com2 plete semiring R is induced by a t-norm.
Proposition 6. Let : P1 P2 ! P be a biresiduation and let ( 1; 2 ; ) be a triple of kernel operators. The following are equivalent 1. 8p1 2 P1; 8p 2 P : (p1 ! p) 2 2. 8p1 2 P1; 8p2 2 P2 : p11 p22 3. P1 1 P2 2 P p11 ! p (p1 p2) A star system is a triple of kernel operators where one of the above conditions holds.
Proof. \ 1 ) 2": \ 2 ) 1":
() \ 2 ) 3": By 2, p11 p22 equality and therefore p11 \ 3 ) 2": Since p11 p22 (p1 p2) .
() =) =) =)
p1 p11 p2 p2 p22 p22 p22 p1
p2 (p1 ! (p1 (p1 ! (p1 (p11 ! (p1 (p1 p2) p2)) p2)) 2 p2) ) Proposition 7. Let L := (L1; L2; L), P := (P1; P2; P) be triples of complete lattices and let L : L1 L2 ! L and P : P1 P2 ! P be biresiduations. Then for every morphism := ('1; '2; ') from (A(L); L) to (A(P); P) the triple ('1 '1+; '2 '2+; ' '+) forms a star system w.r.t. (P; P).
('1 '1+)P1
P ('2 '2+)P2 = '('1+P1
L '2+P2) 'L = (' '+)P: As a consequence of our considerations we receive the following extension of
Theorem 4. Let be a biresiduation on a triple of complete lattices L := (L1; L2; L). Then the star systems w.r.t. (L; ) are in one-to-one correspondence with the substructures of (A(L); ). 9
Some background information: Our paper is indeed based on our 2012 paper "A Macroscopic Approach to FCA and its Various Fuzzi cations" but goes far beyond it. Who carefully reads our present paper will realize that notions have been re ned and adjusted to our situation. Roughly said, biresiduation generalizes residuated posets while biadditivity generalizes complete semirings. What we mainly need is a specialization where these two concepts meet, that is, residuated complete lattices (algebraic logic point of view) which correspond to join complete semirings (linear algebra point of view). The importance of the latter point is for constructions.
Looking into Isabelle Bloch's constructions for mathematical morphology, we found out that there is a general framework in linear algebra over complete semirings which is outlined in section 5, named "Construction of Convolution Algebras". These turn out to be again complete semirings. So the bijective correspondence between residuated complete lattices and join complete semirings can be lifted from a "coordinate level" to a "space level". That is what Bloch essentially does in a special situation (without putting this into a general framework) and we derive from the general construction of convolution algebras over join complete semirings (and a subsequent paradigm shift into residuated complete lattices).