# Some Remarks on the Relation between Annotated Ordered Sets and Pattern Structures (Pattern Recognition and Machine Learning)

## Abstract

We exhibit an intimate connection between the concept of an annotated, ordered set and that of a pattern structure. This enables an exchange of ideas and techniques between both domains.

## Introduction

Pattern structures were introduced in [KG01] to model information. The usefulness of annotated ordered sets for similar purposes was studied in [KSJ08]. Here, we compare and relate the two approaches. To keep the article rationably self-contained we recapitulate both concepts. We see how theorems can be moved between both domains and fix a theorem from [KG01].

In the first section we will introduce annotated ordered sets. In the second section we will outline pattern structures. In the third section we will argue that pattern structures can be understood as a certain sub-class of annotated ordered sets and review basic constructions and theorems. In the fourth section we will correct a theorem about pattern structures and their projections.

The reader is assumed to be knowledgeable about the basics of order theory and formal concept analysis as can be found in [DP90] and [GW99].

## Annotated Ordered Sets

Annotated ordered sets were introduced to model taxonomies, e.g. appearing in the realm of the Gene Ontology.

Definition 1 ((elementary) annotated ordered set). Let be a finite ordered set (poset), let X be a finite set of labels, and let be an annotation function. Then we call an annotated ordered set and refer to (X,F) as an annotation of P. In case P is a (complete) lattice we call an annotated (complete) lattice denoted . for convenience, we regard F as a map from X to P and say that is elementary.

It is interesting to note that an annotated ordered set (P, X, F) can be regarded as a formal context with ordered attributes (X, P,Fr ) since every mapping can be interpreted as a relation where xTRy if and only if . But the concept lattice of this formal context would not yield the intended concept lattice representation of the annotated ordered set, since it does not express the semantics of annotation in a taxonomy, that is, if we annotate an example to a class in a taxonomy we implicitly mean that it belongs to all the super-classes of the class it was annotated to. Additionally, modelling the annotated taxonomy as formal context would be rather counter-intuitive.

We describe how an appropriate formal context can be derived from an annotated ordered set to produce its concept lattice representation. For an ordered set and node we denote by the principal filter of q and dually by the principal ideal. Also, for later use, for let and dually Given an annotated ordered set we can construct a formal context (X, P, I) where we define the relation This means that I equals . Note that in the case of an elementary annotated ordered set the definition of I can be written as since F is regarded as mapping to P (instead of 2P).

The concept lattice of will be denoted by , where  is the set of formal concepts of the formal context is called the concept lattice representation of the annotated ordered set ## Pattern Structures

In [KG01] pattern structures are introduced to model information in the realm of pharmaceutical research. How pattern structures serve to analyze many-valued data contexts is described in [Ku09].

Definition 2 (pattern structure). Let G be a set, let be a meet-semilattice, and let Then is called pattern structure generates a complete subsemilattice The elements of G are called objects and the elements of D are called descriptions or patterns. The operation n models a similarity operation on the descriptions.

Pattern structures can be represented by the concept lattices of so called representation contexts. In the following we sketch the construction of representation contexts as given in [KG01]. First it is important to note that is complete and therefore, there exists a (unique) operation U to make into a complete lattice. This operation (on D) is given by  Furthermore, a subset M of D is called U-dense for if any element can be recaptured as join of elements that is Now (G, M, I) is a representation context for if M is U-dense for (Dg, n) and is defined as ## Basic Connections

On the one hand, given an elementary annotated ordered set we get a pattern structure allows for (finite) meets and F (X) generates a complete subsemilattice of On the other hand, given a pattern structure we always get an elementary annotated ordered set when considering the meet-semilattice as ordered set via the usual definition Therefore, we see that pattern structures are special cases of annotated ordered sets and we can immediately transfer all results on annotated ordered sets to pattern structures. When we consider the other direction we must be more careful. But let us first compare the constructions of formal contexts for representation in both cases.

For the time being, let us consider a pattern structure as elementary annotated ordered set and let us build its associated context via the annotated ordered sets method. We get where is given by . It is obvious that D is If we had dualized the order upfront the above construction would have yielded a representation context for P. Therefore, we can conclude that the method for representation context construction for pattern structures generalizes the method for concept lattice representation for annotated ordered sets in this case. It is important to note that Theorem 1 in [KG01] implies that the concept lattices of (different) representation contexts for a given pattern structure are isomorphic.

In [KG01], it follows directly from Theorem 1 that and the concept lattice of a representation context of the underlying pattern structure are anti-isomorphic. In the following, we exhibit a connection between the concept lattice of a representation context and D, the ordered set of all patterns. For elementary annotated complete lattices, Theorem 1 in [KSJ08] makes obvious that their concept lattice representations are tied to the underlying complete lattices via adjunctions. We need to generalize this result to pattern structures, since (D, C) is not necessarily a complete lattice.

Theorem 1. Let be a pattern structure, let be a representation context, let be a mapping, and let be a mapping. Then forms a dual adjunction (or Galois connection) between the ordered set of patterns D and the concept lattice . In particular, y is injective and is surjective.

Proof. We show that y is injective (the surjectivity of ^ follows from the injectivity of ). Assume we have two concepts (A, B) and (C, D) which are mapped to the same element, that is, We will show that from which it follows that We have that if and only if if and only if for all if and only if  From the above theorem it follows that the concept lattice of a representation context is embedded as a closure system into D.

In [KSJ08], it is investigated what can happen if we fix an ordered set and then vary the annotations. It turns out that the annotations are in one-to-one correspondence with the closure systems in the filter lattice of the ordered set. Clearly, this implies that in the case of pattern structures if a set of patterns or descriptions together with a similarity operation is given and we vary the annotation function 6 freely, we can only get a one-to-one correspondence between (elementary) annotations and a certain subset of the closure systems in the ideal lattice (the dual of the filter lattice of the ordered set). In the following we will single out this subset.

Theorem 2. Let G be a set of objects, and let be a semi-lattice.

The elementary annotations are, up to annotational equivalence, in one-to-one correspondence to the principally generated closure systems in the ideal lattice of D.

Proof. Given an elementary annotation every is a principal ideal in and an object intent of a formal concept of Since, in general, the intents of all concepts of a formal context are exactly the meets of the object intents the annotation induces a principally generated closure system in the ideal lattice of D.

Given a closure system in the ideal lattice of generated by the principal ideals we can define a corresponding elementary annotation where ## Projections

For pattern structures so called projections where introduced in [KG01] to model the process of simplification of the underlying subsumption order. Projections are defined as kernel operators1 on the ordered set of patterns or descriptions. The existence of projections can be characterized by the existence of certain representation contexts. We quote Theorem 2 from [KG01]:

For pattern structures the following two conditions are equivalent.

(2) There exist representation contexts (G, M, I) of and

In the proof of the theorem it is claimed that is a kernel operator on D if (G,N,I) is a representation context of (G, D,6). Examples 1 shows that condition (2) in Theorem 2 needs to be boosted 2 and Example 2 shows that the above operator used in the proof is not a kernel operator as claimed.

Example 1. Let D be given by the structure depicted in Figure 1 and let Fig. 1. (2) implies (1) does not hold in Theorem 2

Fig. 2. Operator from the proof is not a kernel operator

Example 2. Let D be given by the structure depicted in Figure 2 and let and (visualized by the dotted compartment in Figure 2). Note that the carrier set of the complete sub-semilattice generated by is given by It is immediate that M is U-dense regarding but

To repair Theorem 2 we additionally require that is point-wise contained in 61 in condition (2) and to repair the proof we make the above operator into a kernel operator.

Theorem 3. For pattern structures the following two conditions are equivalent.

(2) We have and there exist representation contexts (G,M,I) of Pi and

It remains to show that arbitrary meets of elements from can be recovered from N.