We provide an approach to generalized metrics that covers various concepts of distance. In particular, we consider functorial maps which are weakly positive. Here, we focus on the supermodular case which generalizes dimension functions. We give a lattice-theoretically based construction for supermodular functorial maps, which generalize those arising from Dempster-Shafer-Theory. Within this framework, generalized metrics relevant for FCA and closure operators are discussed.
Introduction
Generalized metrics recently have become of increased interest for modelling a
concept of directed distances with values in a qualitative measurement space. In
particular, they allow to distinguish between deletion and error within the
context of transferred information. We propose a general modeling including lattices
and ordered monoids. Here, our goal is to construct generalized metrics relevant
for FCA and closure operators [
Our modeling of generalized metrics can be very helpful to improve and better understand the mapping of ratings, i. e. compare the rating methodologies of di erent rating agencies with di erent result scales.
We start with a lattice L = (L; L). Then, we consider the ordered monoid M = (M; [; ;; ) with M = 2L. Furthermore, we set and de ne the maps and # x := ft 2 L j t L xg : L
! M : x 7!# x D :
L ! M : (x; y) 7!# y # x: (1) We can easily see that D (x; y) is equal to the set ft 2 L j t L y and t L xg, where x; y 2 L and x L y.
Observation Obviously, D ful ls the following properties: { D (x; x) = ; holds for all x 2 L, since D (x; x) =# x # x = ;. { D (x; y) [ D (y; z) = D (x; z) holds for all x; y; z 2 L with x since Now we want to put the previous considerations in a slightly more general setting. As above, the starting point is a lattice L = (L; L). For a given subset A of L we consider the ordered monoid M = (M; [; ;; ) with M = 2A. Then, for all x 2 L we de ne
Ax := fa 2 A j a L xg:
: L
! M : x 7! Ax; D :
L ! M : (x; y) 7! Ay
Ax: (2) Claim 1 D is functorial w. r. t. (L; M).
Proof. { Firstly, D (x; x) = ; obviously holds for all x 2 L.
{ Secondly, we have to show that D (x; y) [ D (y; z) = D (x; z) holds for all x; y; z 2 L with x L y L z:
L y
L x and a L y and a
L y, that is a 2 D (x; y).
L z, that is a 2 D (y; z).
Hence, a 2 D (x; y) [ D (y; z).
On the other hand, assume a 2 D (x; y) [ D (y; z). Hence, a L x and a L y, or a L y and a L z. Then, a L x (since x L y) and a L z (since y L z) which yields a 2 D (x; z). 2
for an extension of D
as a function with domain L. Next, we want to look onto L L. We achieve this by the following map: d : L
L ! M : (x; y) 7! D (x ^ y; y) (3) Claim 2 The map d is a generalized quasi metric (GQM) w. r. t. (L; M), that is, the subsequent conditions are satis ed: (A0) (A1) (A2) for all x; y 2 L : for all x 2 L : for all x; y; z 2 L : ;
d (x; y), d (x; x) = ;, d (x; z) d (x; y) [ d (y; z).
We remind the reader that A is called join-dense in L if for all x; y 2 L with x L y there exists a 2 A such that a L y and a L x.
Claim 3 Let A be join-dense in L. Then d is a generalized metric (GM) w. r. t. (L; M), that is, d is a GQM which additionally satis es: (A3)
For all x; y 2 L : d (x; y) = ; = d (y; x) =) x = y.
A more general de nition for the underlying concepts will be given in de nition 3.
(A0) Obviously, for all x; y 2 L, the condition ; satis ed. d (x; y) is (A1) (A2)
Clear, since for all x 2 L : d (x; x) = ;.
x; y; z 2 L. This is equivalent to d (x; y) [ d (y; z) holds for all D (x ^ z; z)
D (x ^ y; y) [ D (y ^ z; z): To do so, let a 2 D (x ^ z; z). Hence, a which implies L x ^ z and a
Let x; y 2 L. We suppose d (x; y) = ;. This is equivalent to ()
Ay A(x ^ y) = ;
Ay = A(x ^ y): Taking advantage of the precondition d (x; y) = ; = d (y; x), we follow that
Ay = A(x ^ y) = A(y ^ x) = Ax:
Hence, y = x, as A is join-dense.
All in all, d is a GM w. r. t. (L; M).
Claim 4 The map D is supermodular w. r. t. (L; M) [
D (x ^ y; y)
D (x; x _ y) Proof. Let a 2 D (x ^ y; y). Since D (x ^ y; y) equals Ay that
a 2 Ay and a 2= A(x ^ y):
y and a x^y. Hence, a
Ax = D (x; x _ y). 2
3
We want to put our recent examinations from the special case into a more general
setting. For that, we start with some necessary de nitions [
If in addition, (A3) holds, d is a generalized metric (GM) w. r. t. (P; M): for all (p; q) 2 P
P : d(p; q) = " = d(q; p) =) p = q { for all p 2 P :
(p; p) = ", { for all p; t; q 2 P with p
P t
P q : (p; t) (t; q) = (p; q).
is called weakly positive, if " (p; q) for all (p; q) 2
is called supermodular w. r. t. (P; M), if (p ^ q; q) all (p; q) 2 P. (p; p _ q) holds for Furthermore, is called submodular w. r. t. (P; M), if (p^q; q) holds for all (p; q) 2 P. (p; p_q) De nition 3 Let P be a set, and M = (M; ; "; ) be an ordered monoid. A function d : P P ! M is called generalized quasi-metric (GQM) w. r. t. (P; M), if for all (p; q) 2 for all p 2 P : for all p; t; q 2 P :
P : "
d(p; q) d(p; p) = " d(p; t) d(t; q) d(p; q) (A0) (A1) (A2) (A3) For a given : P ! M , does there exist a generalized quasi-metric d : P P ! M w. r. t. (P; M) which extends such that dj P = ? Theorem 1 Let P = (P; P) be a lattice. If a map : positive, supermodular and functorial w. r. t. (P; M), then P ! M is weakly d : P
P ! M; (p; q) 7! For (A2), we have to show that d(p; q) P d(p; t) d(t; q) holds for all p; t; q 2 P .
We will prove this inequality immediately in Claim 3 below. However, rst of all, we need to show two properties in preparation for that.
Claim 1 (Interval Property)
is functorial, we obtain t P x P y P z =) (x; y) (t; z): As is weakly positive, we get (t; z) = (t; x) (x; y) (y; z): (x; y) = " (x; y) " (t; z): Claim 2 (Meet Property) x P y =) (x ^ z; y ^ z) (x; y):
(x ^ z; y ^ z) = (x ^ (y ^ z); y ^ z) We continue denoting y ^ z by y0 and derive (x ^ (y ^ z); y ^ z) = (x ^ y0; y0) (x; x _ y0); due to supermodularity of . We know that x _ y0 P y, since x P y and y0 P y. Hence, with Claim 1, we get (x ^ z; y ^ z) (x; y): 3 Claim 3 z y x t z p ^ t t p ^ q q t ^ q p ^ t ^ q
The latter theorem can be applied to various concepts of distance between objects of a given lattice. In the following, we will study some interesting applications in di erent context, starting with formal concept analysis. 4
Application to FCA Let K = (G; M; I) be a nite formal context. Then the set of formal concepts of
BK := f(X; Y ) 2 2G 2M j X0 = Y and ; Y 0 = Xg and the formal concept lattice of K is de ned as BK := (BK;
BK) with c1
BK c2 i A1
A2 holds for all c1 = (A1; B1); c2 = (A2; B2) 2 BK. dext : BK
BK ! N such that (c1; c2) 7! #(A2
A1) is a GM w. r. t. (BK; M) with M := (N; +; 0; ). The reason for this is based in Theorem 1, as we will outline below.
For all c1 = (A1; B1); c2 = (A2; B2) 2 BK it follows
(A1 \ A2) and # is the counting measure.
Dext :
BK ! N such that(c1; c2) 7! #A2 #A1: Claim 4 Dext is functorial w. r. t. (BK; M), weakly positive and supermodular. Proof. The properties of being weakly positive and functorial are clear due to the de nition of Dext via the counting measure. Let us have a closer look at the supermodularity:
! Dext(c1 ^ c2; c2) Dext(c1; c1 _ c2):
Dext(c1 ^ c2; c2) = Dext
A1 \ A2; (A1 \ A2)0 ; A2; B2 = #A2 = dext(c1; c2): #(A1 \ A2) Dext(c1; c1 _ c2) = Dext A1; A2 ; (B1 \ B2)0; B1 \ B2 |=(A1{[zA2)00 } = # (A1 [ A2)00
#(A1 [ A2) = #A2 = dext(c1; c2): #(A1 \ A2)
#A1 #A1
Dext(c1 ^ c2; c2)
Dext(c1; c1 _ c2) Obviously, by theorem 1 together with claim 4 it immediately follows that dext is a GM w. r. t. (BK; M).
dint : BK
BK ! N such that (c1; c2) 7! #(B1
B2) is a GM w. r. t. (BK; M). 2
Application to Dempster-Shafer-Theory is a GM w. r. t. the power set of U into the naturally ordered additive monoid of non-negative real numbers.
Remark. With the plausibility map introduced above, a submodular pendant to the supermodular map in (6) can be constructed via e(X; Y ) := Plm Y
Plm X where X
Y
U: e is indeed submodular, as the following inequation holds:
Plm(X [ Y ) + Plm(X \ Y ) Let P = (P; P) be a poset, M = (M; ; ") be a monoid, and : P be a map such that the following properties are satis ed: M ! P 1 2 3
For all p 2 P and all x; y 2 M : For all p 2 P :
p " = p For all p; y 2 P; x 2 M : p P q =)
p x P q x p (x y) = (p x) x Then we call the triple (P; M; ) a poset right monoid action.
P
! M de ned by r(p; q) := fx 2 M j q P p xg for all p; q 2 P: Claim 6 For all p; q; r 2 P the following reverse triangle inequality holds: r(q; r). That is, there exits x 2 r(p; y) and
3 r P q y
P (p x) y 1 = p (x y) = p z:
Let t 2 r(p; q) y 2 r(q; r) such that t = to property, i. e. we obtain
(x y) t:
x y 2 r(p; q) (8) 2 and the triangle inequality of d is shown.
De nition 4 Let M = (M; ; ") be a monoid and let L = (L; ; ; ) be an ordered monoid. Then, a map : M ! L is a monoid norm w. r. t. (M; L) if (") = and (x y) x y holds for all x; y 2 M .
Theorem 2 Let (P; M; ) be a poset right monoid action with P = (P; P) and M = (M; ; "). Further, let L = (L; ; ; ) be a residual complete lattice and : M ! L be a monoid norm w. r. t. (M; L).
is a GQM w. r. t. (P; L).
Application to join geometries Let P = (P; ) be a complete lattice. Then an element x 2 P is called compact in P if for every subset T of P with x sup T there exists a nite subset U of
De nition 5 A join geometry is de ned as a pair (P; E) consisting of a complete lattice P and a join-dense subset E consisting of compact elements in P. For the following, let (P; E) be a join geometry such that for all p; q 2 P there exists a compact element r 2 P such that q p _ r.
Then the triple (P; M; ) is a poset right monoid action for M = (M; [; ;) with
E M := 2fin and : P
M ! P;
(x; D) 7! x _ sup D:
is a monoid norm w. r. t. (M; L) for : M ! N [ f1g;
D 7! #D
L := N [ f1g; +; 0; (which forms a residual complete lattice). Obviously, by theorem 2 it follows that d : P
P ! N [ f1g; (p; q) 7! inf
This result has an important specialisation for closure operators on power sets of nite sets. 8
Application to Closure Operators
Further, let M := N; +; 0; be a closure operator on P := P;
. Then the map is a GQM w. r. t. (P; M), which we want to call the closure distance.
P is a GM w. r. t. ( P; M).
In context of information pooling, for a group of received elements, we can construct the corresponding closure and with the closure distance d from above, the distance to a given closure can be evaluated. This works for arbitrary closure operators, which also includes closure systems of a matroid, for instance. with P := 2U .