The n-Category Café

Formal concept analysis

I don’t know anything about the philosophical roots of the subject but the mathematics of formal concept analysis was fomented in a seminal paper of Rudolf Wille in the 80s.

Wille, Rudolf, “Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts” Ordered Sets. Springer, 1982. 445-470.

The theory was based on Garrett Birkoff’s work on lattice theory of the 30s and developed with Wille’s colleague’s Peter Burmeister and Bernard Ganter in Darmstadt.

I got to meet Bernard Ganter briefly recently by a strange coincidence. Nora Ganter was visiting Sheffield last month from Melbourne. I was talking to her about categorical traces and categorical representations. Over coffee it came out that her father was a mathematician and I realised that it was the Bernard Ganter whose name I had first come across the week before when chasing up some references for my Isbell completion paper. However, not only was he her father, but he was also in Sheffield in the role as baby-sitting grandfather to Nora’s daughter. We managed to have a quick chat before I disappeared off on holiday.

Objects and attributes

Anyway, getting back to the mathematical story, we start with a set of objects $G$ and a set of attributes $M$, in our example these are $$\begin{aligned} G&=\{ \text {fish leech}, \text {bream}, \text {frog}, \dots , \text {corn}\} \\ M&=\{ \text {needs water to live},\text {lives in water},\dots ,\text {breast feeds}\} \end{aligned}$$ Given a set of objects $A\subseteq G$ we can form a set of attributes $I^{\ast }(A)\subseteq M$ which is the set of attributes shared by all objects in $A$: $$I^{\ast }(A)\coloneqq \{ b\in M\mid a I b\, \text {for all}\, a\in A\}$$ So for instance $$I^{\ast }(\{ \text {dog},\text {bream}\} )= \{ \text {needs water to live},\text {can move},\text {has limbs}\} .$$

This gives us a function – the shared attributes function – between power sets $I^{\ast }\colon \mathcal{P}(G)\to \mathcal{P}(M)$. Power sets come with a natural partial order on them, namely that of being a subset. With respect to this, the shared attributes function $I^{\ast }$ is order reversing: $$A\subseteq A'\, \implies \, I^{\ast }(A)\supseteq I^{\ast }(A').$$ In words, if you increase the set of objects then you will decrease the set of attributes that they share.

This means we can think of the shared attributes function as an order-preserving function $$I^{\ast }\colon \mathcal{P}(G)\to \mathcal{P}(M)^{\mathrm{op}}.$$

Similarly we have an order preserving function going the other way $$I_{\ast }\colon \mathcal{P}(M)^{\mathrm{op}}\to \mathcal{P}(G)$$ which is the objects-with-those-attributes function. So for instance $$I_{\ast }(\{ \text {needs water to live},\text {can move},\text {has limbs}\} )= \{ \text {dog},\text {bream},\text {frog}\} .$$

Galois connections and closure operations

The functions $I^{\ast }$ and $I_{\ast }$ form what is known as a Galois connection. This means that for all subsets of objects $A\in \mathcal{P}(G)$ and sets of attributes $B\subseteq \mathcal{P}(M)$ we have $$I^{\ast }(A)\supseteq B \, \Longleftrightarrow \, A\subseteq I_{\ast }(B).$$ This is clear, because both expressions are just saying that all the objects in $A$ have all the attributes in $B$.

A Galois connection gives rise to two closure operations. The closure operations here are $I_{\ast }I^{\ast }\colon \mathcal{P}(G)\to \mathcal{P}(G)$ and $I^{\ast }I_{\ast }\colon \mathcal{P}(M) \to \mathcal{P}(M)$. The closure operation on sets of objects is to take all objects which share all the attributes that the objects in the original set share. So $$I_{\ast }I^{\ast }(\{ \text {dog},\text {bream}\} )= \{ \text {dog},\text {bream},\text {frog}\} .$$

Similarly, the closure operation for attributes takes a set of attributes and adds in all other attributes which are shared by the objects with the original attributes. So for example $$I^{\ast }I_{\ast }(\{ \text {has limbs}\} )= \{ \text {needs water to live},\text {can move},\text {has limbs}\} .$$ It should be reasonably clear that these deserve the name closure operations as they are idempotent, so doing the operation twice doesn’t add anything new.

A closed set of objects is one which is equal to its closure, i.e. $A\subseteq G$ such that $I_{\ast }I^{\ast }(A)=A$. So $\{ \text {dog},\text {bream}\}$ is not closed, but $\{ \text {dog},\text {bream},\text {frog}\}$ is. A closed set of objects is a maximal set of objects which share some attributes. There is the analogous notion for attributes, so $\{ \text {has limbs}\}$ is not closed but $\{ \text {needs water to live},\text {can move},\text {has limbs}\}$ is.

The concept of a concept

We now reach the fundamental notion of a concept. A concept $(A,B)\in \mathcal{P}(G)\times \mathcal{P}(M)$ consists of a set of objects $A$ and a set of attributes $B$ such that $I^{\ast }(A)=B$ and $A=I_{\ast }(B)$. It is immediate that both $A$ and $B$ are closed. In our example we would have the concept $$(\{ \text {dog},\text {bream},\text {frog}\} ,\{ \text {needs water to live},\text {can move},\text {has limbs}\} ),$$ we might call this concept ‘limbed animals’. For a concept $(A,B)$ the set of objects $A$ is called the extent of the concept and the set of attributes $B$ is called the intent of the concept.

You can imagine rather bigger examples than our baby example here, such as $G$ being the set of all species of animal on the planet and $M$ being some suitable set of attributes. I would expect (subject to picking a good set of attributes) that there would be a concept of ‘bird’, with the extent of the concept of bird being the set of all bird species and the intent including attributes such as ‘lays eggs’, ‘has feathers’ and ‘has wings’, but not including ‘can fly’ as we know of bird species such as penguins which can’t fly.

It’s not hard to see that the set of concepts $\mathcal{B}(G,M,I)$ is in bijective correspondence with the set $\mathcal{P}_{\mathrm{cl}}(G)$ of closed sets of objects. In one direction you just take the extent of the concept, $(A,B)\mapsto A$, and in the other direction you take the closed set with its shared attributes, $A\mapsto (A,I^{\ast }(A))$. Similarly we have a bijection with the set $\mathcal{P}_{\mathrm{cl}}(M)$ of closed sets of attributes. So as sets we have bijections $$\mathcal{P}_{\mathrm{cl}}(G)\cong \mathcal{B}(G,M,I) \cong \mathcal{P}_{\mathrm{cl}}(M).$$

The ordering on concepts

The set of all concepts $\mathcal{B}(G,M,I)$ has a natural partial order on it given by the notion of a subconcept. For instance, ‘limbed, water-dwelling animal’ is a subconcept of ‘limbed animal’, and it consists of the following $$(\{ \text {bream},\text {frog}\} ,\{ \text {needs water to live},\text {lives in water},\text {can move},\text {has limbs}\} ).$$ Clearly, a subconcept has a reduced extent (set of objects) and an increased intent (set of attributes). Formally, for concepts $(A,B),(A',B')\in \mathcal{B}(G,M,I)$ write $(A,B)\le (A',B')$ if $A\subseteq A'$, or equivalently if $B\supseteq B'$. This gives the set of concepts $\mathcal{B}(G,M,I)$ the structure of a poset.

You can look back to the top to see a picture of the poset structure on our example.

In fact, the set of concepts $\mathcal{B}(G,M,I)$ is a lattice meaning that each pair of concepts has a greatest lower bound and a least upper bound. Given two concepts $(A,B)$ and $(A',B')$ we want to find the least upper bound (or supremum). We know that any upper bound must be a superconcept of both $(A,B)$ and $(A',B')$, so the extent must contain $A\cup A'$, and the closure $I^{\ast }I_{\ast }(A\cup A')$ is the smallest closed set containing the union so must be the extent of the least upper bound thus $$\sup ((A,B),(A',B'))=(I_{\ast }I^{\ast }(A\cup A'), I^{\ast }(A\cup A')).$$ However, $I^{\ast }(A\cup A')$ is the set of attributes shared by everything in the union, and this is the intersection of the set of attributes shared by the objects in $A$ and those shared by the objects in $A'$. In other words $$\sup ((A,B),(A',B'))=(I_{\ast }I^{\ast }(A\cup A'), B\cap B').$$

Similarly, the greatest lower bound, or infimum, is given by taking the closure of the union of the intents. $$\inf ((A,B),(A',B'))=(A\cap A', I^{\ast }I_{\ast }(B\cup B')).$$

What has this to do with the nucleus of a profunctor?

Several of you will have realised that the relation $I$ can be viewed as a profunctor enriched in truth values, that the Galois connection is an adjunction between presheaf-type enriched categories and the concept lattice is the centre of the adjunction, i.e. the nucleus of the profunctor. I’ll explain this in more detail next time and go on to say how this point of view can be used to generalize to fuzzy concept analysis.