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


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.


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). Lettmp1411-246_thumbbe a finite ordered set (poset), let X be a finite set of labels, and lettmp1411-247_thumbbe an annotation function. Then we calltmp1411-248_thumban annotated ordered set and refer to (X,F) as an annotation of P. In case P is a (complete) lattice we calltmp1411-249_thumban annotated (complete) lattice denotedtmp1411-250_thumb. for convenience, we regard F as a map from X to P and say thattmp1411-251_thumbis 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 tmp1411-252_thumbcan be interpreted as a relationtmp1411-253_thumbwhere xTRy if and only iftmp1411-254_thumb. 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 tmp1411-264_thumband nodetmp1411-265_thumbwe denote bytmp1411-266_thumbthe principal filter of q and dually bytmp1411-267_thumbthe principal ideal. Also, for later use, fortmp1411-268_thumb lettmp1411-269_thumband duallytmp1411-270_thumbGiven an annotated ordered settmp1411-271_thumbwe can construct a formal contexttmp1411-272_thumb (X, P, I) where we define the relationtmp1411-273_thumb

This means that I equalstmp1411-274_thumb. Note that in the case of an elementary annotated ordered set the definition of I can be written astmp1411-275_thumb since F is regarded as mapping to P (instead of 2P).

The concept lattice oftmp1411-276_thumbwill be denoted bytmp1411-277_thumb, wheretmp1411-278_thumb tmp1411-279_thumbis the set of formal concepts of the formal contexttmp1411-280_thumbis called the concept lattice representation of the annotated ordered settmp1411-281_thumb

In casetmp1411-282_thumbforms an annotated complete lattice andtmp1411-283_thumbis a formal concept intmp1411-284_thumb, we observe thattmp1411-285_thumbis the set of alltmp1411-286_thumbsuch thattmp1411-287_thumb is an upper bound of F(x). Also, for convenience, for a nodetmp1411-288_thumbdenote tmp1411-289_thumb

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, lettmp1411-290_thumbbe a meet-semilattice, and lettmp1411-291_thumbThentmp1411-292_thumbis called pattern structure tmp1411-293_thumbgenerates a complete subsemilatticetmp1411-294_thumbThe 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 thattmp1411-295_thumbis complete and therefore, there exists a (unique) operation U to maketmp1411-296_thumbinto a complete lattice. This operation (on D) is given bytmp1411-297_thumb tmp1411-298_thumbFurthermore, a subset M of D is called U-dense fortmp1411-299_thumbif any elementtmp1411-300_thumbcan be recaptured as join of elementstmp1411-301_thumbthat istmp1411-302_thumb

Now (G, M, I) is a representation context fortmp1411-303_thumbif M is U-dense for (Dg, n) andtmp1411-304_thumbis defined astmp1411-305_thumb

Basic Connections

On the one hand, given an elementary annotated ordered settmp1411-348_thumb we get a pattern structuretmp1411-349_thumballows for (finite) meets and F (X) generates a complete subsemilattice oftmp1411-350_thumbOn the other hand, given a pattern structuretmp1411-351_thumbwe always get an elementary annotated ordered settmp1411-352_thumbwhen considering the meet-semilattice as ordered set via the usual definitiontmp1411-353_thumbTherefore, 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 structuretmp1411-354_thumbas elementary annotated ordered set and let us build its associated context via the annotated ordered sets method. We gettmp1411-355_thumbwheretmp1411-356_thumbis given bytmp1411-357_thumb. It is obvious that D istmp1411-358_thumbIf we had dualized the ordertmp1411-359_thumbupfront 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 thattmp1411-360_thumband 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. Lettmp1411-361_thumbbe a pattern structure, lettmp1411-362_thumbbe a representation context, lettmp1411-363_thumbbe a mapping, and lettmp1411-364_thumbbe a mapping. Thentmp1411-365_thumbforms a dual adjunction (or Galois connection) between the ordered set of patterns D and the concept latticetmp1411-366_thumb. In particular, y is injective and is surjective.

Proof. We show that y is injective (the surjectivity of ^ follows from the injectivity oftmp1411-367_thumb). Assume we have two concepts (A, B) and (C, D) which are mapped to the same element, that is,tmp1411-368_thumbWe will show thattmp1411-369_thumbfrom which it follows thattmp1411-370_thumbWe have thattmp1411-371_thumbif and only if tmp1411-372_thumbif and only iftmp1411-373_thumbfor alltmp1411-374_thumbif and only iftmp1411-375_thumb

The pairtmp1411-376_thumbforms a Galois connection sincetmp1411-377_thumb


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 lettmp1411-410_thumbbe 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 annotationtmp1411-411_thumbeverytmp1411-412_thumbis a principal ideal intmp1411-413_thumband an object intent of a formal concept oftmp1411-414_thumbSince, 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 systemtmp1411-415_thumbin the ideal lattice oftmp1411-416_thumbgenerated by the principal idealstmp1411-417_thumbwe can define a corresponding elementary annotation tmp1411-418_thumbwheretmp1411-419_thumb


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 structurestmp1411-420_thumbthe following two conditions are equivalent.

(1) There exists a projectiontmp1411-421_thumbwithtmp1411-422_thumb

(2) There exist representation contexts (G, M, I) oftmp1411-423_thumband


In the proof of the theorem it is claimed thattmp1411-427_thumb 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 lettmp1411-446_thumb

tmp1411-447_thumb(visualized by the dotted compartment in Figure 1) for i = 1, 2. Note that the carrier settmp1411-448_thumbof the complete sub-semilattice generated bytmp1411-449_thumbis given bytmp1411-450_thumbfor i =1, 2. It is immediate thattmp1411-451_thumb dense regardingtmp1411-452_thumband thattmp1411-453_thumb, but obviously there exists no projectiontmp1411-454_thumbwithtmp1411-455_thumb (2) implies (1) does not hold in Theorem 2

Fig. 1. (2) implies (1) does not hold in Theorem 2

Operator from the proof is not a kernel operator

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 lettmp1411-468_thumb andtmp1411-469_thumb(visualized by the dotted compartment in Figure 2). Note that the carrier settmp1411-470_thumbof the complete sub-semilattice generated by tmp1411-471_thumbis given bytmp1411-472_thumbIt is immediate that M is U-dense regardingtmp1411-473_thumbbut

tmp1411-474_thumbis not contractive sincetmp1411-475_thumb, thustmp1411-476_thumbis  not a kernel operator.

To repair Theorem 2 we additionally require thattmp1411-477_thumbis 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 structurestmp1411-478_thumbthe following two conditions are equivalent.

(1) There exists a projectiontmp1411-479_thumbwithtmp1411-480_thumb

(2) We havetmp1411-481_thumband there exist representation contexts (G,M,I) of Pi and


Proof.tmp1411-483_thumb: Since there exists a projectiontmp1411-484_thumbwithtmp1411-485_thumbwe have for

tmp1411-486_thumbthattmp1411-487_thumbwhich impliestmp1411-488_thumbsincetmp1411-489_thumbis contractive. We construct the two representation contexts. Let M := D and let

tmp1411-490_thumb. Obviously, we havetmp1411-491_thumb. Sincetmp1411-492_thumbwe gettmp1411-493_thumb

It remains to show that arbitrary meets of elements fromtmp1411-494_thumbcan be recovered from N.

Next post:

Previous post: