Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

September 2, 2013

Formal Concept Analysis

Posted by Simon Willerton

Last time I posted about the nucleus of enriched functors. This time I will post about something a bit (!) less abstract — formal concept analysis — something which has applications in data-mining, software engineering and, possibly, catching terrorists. Next time I’ll post about how these two things come together and can give rise to fuzzy concept analysis.

Formal concept analysis is about extracting the relationships and hierarchies available from the common attributes shared by objects. Let’s try to break up this abstract definition with a concrete example.

In the most basic form of formal concept analysis, the input consists of a set of objects GG (from the German ‘Gegenstände’), a set of attributes MM (from the German ‘Merkmale’) and a relation II (from the German ‘Inzidenzrelation’) between the objects and the attributes expressing which objects have which attributes. This triple (G,M,I)(G,M,I) is called the formal context and is often expressed as a table. I don’t feel witty enough today to think up a pertinent Café-based example, so instead I will steal a standard example from the formal concept analysis literature. Here is the table.

A concept lattice

[For non-native English speakers, bream is a kind of fish.]

The output of the analysis is the concept lattice (G,M,I)\mathcal{B}(G,M,I) (from the German ‘Begriffsverband’). This is a lattice, which means it is a poset in which each pair of elements have a greatest lower bound and a least upper bound. The concept lattice expresses relationships between the objects and the attributes. Here is the concept lattice for the above example.

A concept lattice

I will explain how you go from the formal context to the concept lattice in the main body below. The relation with my last post is contained in the following slogan.

The concept lattice is the nucleus N(I)N(I) of the relation II.

This comes about by thinking about everything here as being done in the realm of categories enriched over truth values. I’ll explain that next time, but many of you will be able to see that in what you read here.

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 GG and a set of attributes MM, in our example these are G ={fish leech,bream,frog,,corn} M ={needs water to live,lives in water,,breast feeds} \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 AGA\subseteq G we can form a set of attributes I *(A)MI^{\ast }(A)\subseteq M which is the set of attributes shared by all objects in AA: I *(A){bMaIbfor allaA} I^{\ast }(A)\coloneqq \{ b\in M\mid a I b\, \text {for all}\, a\in A\} So for instance I *({dog,bream})={needs water to live,can move,has limbs}. 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 *:𝒫(G)𝒫(M)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 *I^{\ast } is order reversing: AAI *(A)I *(A). 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 *:𝒫(G)𝒫(M) op. I^{\ast }\colon \mathcal{P}(G)\to \mathcal{P}(M)^{\mathrm{op}}.

Similarly we have an order preserving function going the other way I *:𝒫(M) op𝒫(G) I_{\ast }\colon \mathcal{P}(M)^{\mathrm{op}}\to \mathcal{P}(G) which is the objects-with-those-attributes function. So for instance I *({needs water to live,can move,has limbs})={dog,bream,frog}. 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 *I^{\ast } and I *I_{\ast } form what is known as a Galois connection. This means that for all subsets of objects A𝒫(G)A\in \mathcal{P}(G) and sets of attributes B𝒫(M)B\subseteq \mathcal{P}(M) we have I *(A)BAI *(B). 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 AA have all the attributes in BB.

A Galois connection gives rise to two closure operations. The closure operations here are I *I *:𝒫(G)𝒫(G)I_{\ast }I^{\ast }\colon \mathcal{P}(G)\to \mathcal{P}(G) and I *I *:𝒫(M)𝒫(M)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 *I *({dog,bream})={dog,bream,frog}. 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 *I *({has limbs})={needs water to live,can move,has limbs}. 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. AGA\subseteq G such that I *I *(A)=AI_{\ast }I^{\ast }(A)=A. So {dog,bream}\{ \text {dog},\text {bream}\} is not closed, but {dog,bream,frog} \{ \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 {has limbs}\{ \text {has limbs}\} is not closed but {needs water to live,can move,has limbs}\{ \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)𝒫(G)×𝒫(M)(A,B)\in \mathcal{P}(G)\times \mathcal{P}(M) consists of a set of objects AA and a set of attributes BB such that I *(A)=BI^{\ast }(A)=B and A=I *(B)A=I_{\ast }(B). It is immediate that both AA and BB are closed. In our example we would have the concept ({dog,bream,frog},{needs water to live,can move,has limbs}), (\{ \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)(A,B) the set of objects AA is called the extent of the concept and the set of attributes BB is called the intent of the concept.

You can imagine rather bigger examples than our baby example here, such as GG being the set of all species of animal on the planet and MM 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 (G,M,I)\mathcal{B}(G,M,I) is in bijective correspondence with the set 𝒫 cl(G)\mathcal{P}_{\mathrm{cl}}(G) of closed sets of objects. In one direction you just take the extent of the concept, (A,B)A(A,B)\mapsto A, and in the other direction you take the closed set with its shared attributes, A(A,I *(A))A\mapsto (A,I^{\ast }(A)). Similarly we have a bijection with the set 𝒫 cl(M)\mathcal{P}_{\mathrm{cl}}(M) of closed sets of attributes. So as sets we have bijections 𝒫 cl(G)(G,M,I)𝒫 cl(M). \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 (G,M,I)\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 ({bream,frog},{needs water to live,lives in water,can move,has limbs}). (\{ \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)(G,M,I)(A,B),(A',B')\in \mathcal{B}(G,M,I) write (A,B)(A,B)(A,B)\le (A',B') if AAA\subseteq A', or equivalently if BBB\supseteq B'. This gives the set of concepts (G,M,I)\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 (G,M,I)\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)(A,B) and (A,B)(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)(A,B) and (A,B)(A',B'), so the extent must contain AAA\cup A', and the closure I *I *(AA)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 *I *(AA),I *(AA)). \sup ((A,B),(A',B'))=(I_{\ast }I^{\ast }(A\cup A'), I^{\ast }(A\cup A')). However, I *(AA)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 AA and those shared by the objects in AA'. In other words sup((A,B),(A,B))=(I *I *(AA),BB). \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))=(AA,I *I *(BB)). \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 II 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.

Posted at September 2, 2013 12:40 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2652

28 Comments & 1 Trackback

Re: Formal Concept Analysis

Glad to see that a host here get interested in the area that I have been working on during most of my postgraduate period.

Yeah, FCA has a natural closed relationship with profunctors between quantale-enriched categories (or more generally, quantaloid-enriched categories — for FCA on fuzzy sets).

The main theory of FCA can be translated into purely categorical languages. Indeed, the Galois connection of FCA generalizes the Isbell adjunction in category theory. It is also interesting that the Galois connection in another theory in computer science, rough set theory (RST), generalizes Kan extensions in category theory. We refer to them as Isbell adjunctions and Kan adjunctions in a recent paper.

Posted by: Lili Shen on September 2, 2013 2:52 PM | Permalink | Reply to this

Re: Formal Concept Analysis

Welcome to the Café Lili! Your paper gets a mention in my Isbell completion paper which has just appeared in TAC. (I didn’t realise it had appeared until I just googled it now!) I haven’t updated the arxiv version yet.

Is Zhang your supervisor? I mentioned the paper with Gutiérrez García et al in my last post.

Posted by: Simon Willerton on September 2, 2013 3:18 PM | Permalink | Reply to this

Re: Formal Concept Analysis

Yes, Zhang is my supervisor. I am so happy that my little job gets noticed. :-) At first we just tried to “categorify” the process of generating concept lattices from formal contexts, but made it into a pure categorical story at last.

Posted by: Lili Shen on September 2, 2013 4:14 PM | Permalink | Reply to this

Re: Formal Concept Analysis

I’m sorry to lower the tone, but let’s get this out of the way. A bream has limbs?

Posted by: Tom Leinster on September 2, 2013 5:20 PM | Permalink | Reply to this

Re: Formal Concept Analysis

Good question. It appears that fins count as limbs. Here’s the main definition of limb from the OED.

limb, n. 2.a. A part or member of an animal body distinct from the head or the trunk, e.g. a leg, arm, wing.

Posted by: Simon Willerton on September 2, 2013 5:32 PM | Permalink | Reply to this

Re: Formal Concept Analysis

I see. So no one thinks a bream looks like this.

Posted by: Tom Leinster on September 2, 2013 7:57 PM | Permalink | Reply to this

Re: Formal Concept Analysis

Nice! I’ve probably had a bit too much wine, but I wonder if anyone has ever gotten, or will ever get, the concept of ‘concept’ to emerge naturally from formal concept analysis.

Posted by: John Baez on September 3, 2013 3:31 PM | Permalink | Reply to this

Re: Formal Concept Analysis

There was a Dagstuhl seminar (no 06341: Computational Structures for Modelling Space, Time and Causality) where some of this was discussed for its relationship with locales, quantales, and domain theory. There were some excellent talks and discussions but unfortunately the published abstracts are thin on the ground. Guo-Qiang Zhang was there as was John Pfaltz, and both talked about FCA and its relationship with topics such as Chu spaces, domains, closure systems, etc.

Posted by: Tim Porter on September 4, 2013 7:37 AM | Permalink | Reply to this

Re: Formal Concept Analysis

Is this collection of abstracts the one you mean?

06341 Abstracts Collection – Computational Structures for Modelling Space, Time and Causality

I know essentially nothing about Chu spaces or domain theory, so can’t really see the connections between the Pfaltz and Zhang abstracts and FCA.

Posted by: Simon Willerton on September 4, 2013 9:25 AM | Permalink | Reply to this

Re: Formal Concept Analysis

At its simplest a Chu space is just a relation, but Vaughan Pratt in his development of them allowed for the array of values to take on values in a general structured object. This could be the classical {0,1} as in a relation between two sets or it could be [0,1], or lots of other possibilities.

Look at Pfaltz’s list of publications especially here

Posted by: Tim Porter on September 4, 2013 8:42 PM | Permalink | Reply to this

Re: Formal Concept Analysis

So it sounds like Chu spaces are like the fuzzy relations I’ll talk about next time (I hope!).

Pfaltz’s stuff looks interesting. He’s done some work on social networks I see. Here’s an exercise for the interested reader. Start with a graph, possibly directed, possibly with loops. (This is supposed to be representing a social network.) Think of this as relation between the nodes/participants. What do concepts represent in this case?

Posted by: Simon Willerton on September 5, 2013 10:09 AM | Permalink | Reply to this

Re: Formal Concept Analysis

The link with domains is in a paper by Hintzler and Wendt, here. That raises interesting questions about doing `fuzzy’ or K-valued FCA. Does it have links with some variant form of Domain theory?

Note that there is an inherent logic for knowledge transmission in Chu spaces. See van Benthem, J.: Information transfer across Chu spaces. Logic Journal of the IGPL 8 (2000)

Posted by: Tim Porter on September 5, 2013 9:28 PM | Permalink | Reply to this

Re: Formal Concept Analysis

Simon wrote:

Think of this as relation between the nodes/participants. What do concepts represent in this case?

Hmm, something like ways people can like other people? The extent of the concept is the people doing the liking, and the intent is the people being liked? Or vice versa?

I’m not sure of this…

I just wanted to add that what you’re talking about in this blog article is incredibly important. When I made my joke about using formal concept analysis in math to discover the concept of ‘concept’, there was supposed to be a serious point to it: have people applied formal concept analysis to mathematics?

I can vaguely imagine trying to take ideas from formal concept analysis and extend them to situations where what we have to start with is a lot more structured than a pair of sets and a relation between them.

I can also vaguely imagine links to Lawvere’s functorial semantics, since the ‘intent’ / ‘extent’ duality is a bit like the ‘semantics’ / ‘syntax’ duality.

I also want to add that I’ve never heard anyone say ‘bream’ in America, and I don’t really know what a bream is (apparently a fish with limbs). I see: there aren’t bream in America.

Posted by: John Baez on September 6, 2013 7:55 AM | Permalink | Reply to this

Bream

Actually, when I hear the word bream I think of sea bream. That seems to describe a family rather than a species though. According to wikipedia, in North America the word ‘porgy’ is used. Have you heard of those? It’s not something I remember coming across when I’ve been in the US.

I’ve found names of types of fish to be particularly difficult to translate when I’ve travelled. Sometimes there’ll be regional names for things (spigola in southern Italy, branzino in northern Italy), sometimes more specific or more general words are used, sometimes the species are slightly different in different places and sometimes the same words are used for different species (for instance if I ask for seabass in California I get something in a different family to what I would get in Britain).

Posted by: Simon Willerton on September 6, 2013 10:44 AM | Permalink | Reply to this

Re: Bream

Sea bream, eh? I’ve never heard of those either… nor ‘porgy’. But I guess there are lots of fish I don’t know about.

Posted by: John Baez on September 8, 2013 1:12 PM | Permalink | Reply to this

Re: Bream

I don’t consider myself a “foodie”, but I think I’ve heard of both. Maybe your wife Lisa has heard of them?

Posted by: Todd Trimble on September 9, 2013 12:57 AM | Permalink | Reply to this

Social networks

For concreteness, let’s make the relation symmetric, like being friends on facebook, and let’s suppose that it’s reflexive, so everyone’s friends with themselves.

If we take a set of people, say me and Tom Leinster, then the closure of that set will be the common mutual friends of all the mutual friends of me and Tom. As Tom and I have common friends from various bits of life I suspect the closure would just be me and Tom. I don’t think that would be an interesting concept. (I suppose you would think of “being friends with Simon and Tom” as being the intent and the set of mutual friends as the extent.)

However, if we took me, Tom and David Corfield, I would guess that everyone who knows the three of us also knows Eugenia Cheng. So the closure of me, David and Tom would include Eugenia. The corresponding extent would be all the people who knew the four of us and so is likely to be people who are category-minded in some fashion.

You can imagine google circles or terrorists cells being identified in this way.

Posted by: Simon Willerton on September 6, 2013 1:33 PM | Permalink | Reply to this

Re: Formal Concept Analysis

John said

I just wanted to add that what you’re talking about in this blog article is incredibly important. When I made my joke about using formal concept analysis in math to discover the concept of ‘concept’, there was supposed to be a serious point to it: have people applied formal concept analysis to mathematics?

Well, of course it depends what you mean. For instance, although I don’t know whether they’ve studied the concept of ‘concept’ I do know that they’ve studied the lattice of lattices. See, for example, page 84 of the following beamer presentation.

Bernhard Ganter, Finger Exercises in Formal Concept Analysis, Dresden ICCL Summer School, June/July 2006.

There are many attributes a lattice can have, such as being join-distributive or semimodular, and you can apply formal concept analysis to sets of lattices.

Another mathematical example, given in those notes from page 66 onwards, is about the possible relative positions of two unit squares.

So that would be one way of applying formal concept analysis to mathematics.

Another aspect of formal concept analysis concerns logical systems in the following sense. Given some data on the attributes of some objects, you want to be able to make deductions, or indeed, to decide exactly what deductions can be, erm, deduced from the data. Let me give another standard example. I’ve taken this from the paper I found via Tim Porter’s comments above.

J.L. Pfaltz, Establishing Logical Rules from Empirical Data, Intern. Journal on Artificial Intelligence Tools , Vol. 17, no. 5 (2008) 985-1001

There is a mushroom data set drawn from “The Audubon Society Field Guide to North American Mushrooms” which lists for 8124 species of mushroom 85 physical attributes such as ‘red cap’, ‘blue cap’, ‘does not bruise’, ‘pungent odour’, ‘foul odour’ together with the important attributes of being poisonous or edible. One can form the context lattice and from that calculate deductions such as

  • foul odour implies (poisonous and free gill attachment)
  • (red cap and doesn’t bruise) implies poisonous

I believe there are algorithms for calculating generating sets of deductions. So you should be able to come up with a minimal list of things to check to make sure the mushrooms you have picked are not poisonous.

Posted by: Simon Willerton on September 6, 2013 7:03 PM | Permalink | Reply to this

Re: Formal Concept Analysis

Posted by: David Roberts on September 10, 2013 6:47 AM | Permalink | Reply to this

Re: Syntax and semantics

John said

I can also vaguely imagine links to Lawvere’s functorial semantics, since the ‘intent’ / ‘extent’ duality is a bit like the ‘semantics’ / ‘syntax’ duality.

The semantics/syntax adjunction of Lawvere does fit into this picture. I have only an intuitive feel for what semantics and syntax actually mean, but the adjunction is explained in the following article.

Peter Smith, The Galois Connection between Syntax and Semantics.

The gist of it is as follows. Suppose that LL is some formal language. Let GG be the set of LL-structures and let MM be the set of LL-sentences. Let II be the relation expressing the truth of a sentence with respect to a structure: so for a structure sGs\in G and a sentence ϕM\phi \in M write sIϕs I \phi if the sentence ϕ\phi is true with respect to the structure ss. I believe the relation would normally be written sϕs \vDash \phi .

If SS is a set of LL-structures then I *(S)MI^{\ast }(S)\subseteq M is the set of all sentences which are true with respect to all of the structures. And if α\alpha is a set of sentences then I *(α)GI_{\ast }(\alpha )\subseteq G is the set of all structures in which all the sentences in α\alpha are true.

The concepts here would be theories. A concept (S,α)(S,\alpha ) consists of α\alpha a set of sentences which is closed under logical consequence and SS the set of models of the theory. So SS would be the semantics and α\alpha would be the syntax, is that right?

I realise that I’m being vague here (I’m not entirely sure what an ‘LL-structure’ really is), so would appreciate if someone could tell me what LL I would need to take to, say, get the theory of groups popping out. I also realise I’m probably being cavalier with the word ‘set’.

Posted by: Simon Willerton on September 10, 2013 10:05 AM | Permalink | Reply to this

Re: Syntax and semantics

Fortunately you never have to leave the Café for further information on evidently category theoretic topics, such as syntax-semantics duality. Do you remember Todd’s two posts (I and II)?

Then we reported on Awodey and Forssell’s first-order logical duality. The thesis gives the propositional case first, before moving up to first-order logic.

Posted by: David Corfield on September 10, 2013 11:52 AM | Permalink | Reply to this

Re: Syntax and semantics

David said:

Do you remember Todd’s two posts (I and II)?

I do now! Thanks. There’s interesting stuff in those posts, but there’s no mention of the relation between sentences and structures which underpins my perspective. Thinking about the material in Todd’s first post did lead me on to realizing the relationship with classical dualities which I’ve now described in my Classical Dualities and Formal Concept Analysis post.

Posted by: Simon Willerton on September 18, 2013 9:21 AM | Permalink | Reply to this

Re: Formal Concept Analysis

I just wanted to add that what you’re talking about in this blog article is incredibly important. When I made my joke about using formal concept analysis in math to discover the concept of “concept”, there was supposed to be a serious point to it: have people applied formal concept analysis to mathematics?

Incredibly important indeed. I once came across this inspiring paper:

Paul Halmos, “Does Mathematics Have Elements?”, Bulletin of the Australian Mathematical Society, Vol. 25, 1982, pp. 161-175.

The paper also appeared as:

“Does Mathematics Have Elements?”, Mathematical Intelligencer, Vol. 3, 4, 1981, pp. 147–153.

where it was introduced by an unflattering comparison between mathematics and alchemy:

John Ewing, “Mathematics and Alchemy”, ibid., pp. 146.

I can access the Ewing link, but I think it’s because I’m in an Oxford library. A quick check on my server machine showed that it can’t: Springer paywall strikes again. So to summarise, Ewing says that mathematicians preen themselves as being superior to experimental scientists. A theorem taught in Newton’s time is true today, but the chemistry taught in Newton’s time is mere alchemy. Pah!

But in reality, continues Ewing, mathematicians are dreadful scientists. Alchemists just threw together whatever chemicals they could find, then saw what came out. Most of the time, it was completely uninteresting. And modern mathematics? No sense of empirical classification or experimental control. In the alchemists’ world of pour and mix, stir and sniff, the mathematicians would feel right at home.

So what mathematics needs is a periodic table. What are the basic constituents of mathematics? How can one plan a “mathematical synthesis”, as an organic chemist would plan a specific drug, paint, or other complex molecule? Perhaps this is a meaningless question. But it is worth asking, and perhaps, Ewing implies, Halmos is offering a first answer.

Maybe Halmos’s suggestions could be the starting point for a formal concept analysis of mathematics.

By the way, I first came across the Halmos and Ewing pieces at about the same time as an incredibly exciting computer program. This was an automated creator of mathematical conjectures and concepts, and hence seemed both to need the answers to Ewing’s questions, and to offer them.

I’m talking about Douglas Lenat’s AM program. The program started with a “vocabulary” of simple data structures representing sets and set operations. Lenat equipped it with a lot of heuristics (rules of thumb) about what makes mathematical concepts interesting. For example, if an operation is interesting, its inverse is probably interesting. If a binary operation is interesting, then the result of making both arguments identical is probably very interesting. A concept which has been discovered in more than one way is probably very interesting. And so on.

Having defined all these, Lenat let his program run. And to quote one of his abstracts, itself quoted in:

Ken Haase, “Invention and Exploration in Discovery”, Ph.D Thesis, MIT, 1990.

Given an initial vocabulary of set theoretic concepts and operators, the AM program – through the application of simple AI techniques – proceeds to define and develop concepts including `numbers’, `multiplication’, `factoring’, and `prime numbers’. Based on the empirical properties of these concepts, AM makes conjectures such as unique factorization (there is one prime factorization for every number) and Goldbach’s conjecture (every even number can be expressed as the sum of two primes).

An FCA of mathematics would be a boon to automated reasoning.

Posted by: Jocelyn Ireson-Paine on November 18, 2014 6:26 PM | Permalink | Reply to this

Re: Formal Concept Analysis

There is a not dissimilar proposal by Valentini to use formal topology (the predicative theory of sites on a poset) for organizing concepts.

I have once pursued this line of thought a bit and tried to use Sambin’s Basic Picture, a predicative presentation of the category of SupLattices using relations, for this.

In small experiments it looks like the closure operator of the Basic Picture produces more “concepts” than formal concept analysis, and hence may perhaps be less useful “in practice”.

Posted by: Bas Spitters on September 9, 2013 1:17 PM | Permalink | Reply to this

Re: Formal Concept Analysis

Dear Author and members of discussion:

I drifted into this while looking up for references on definition of “precision of concept” when no measurements & values of measurement are involved.

I use math with fear and admiration but NOT with sufficient understanding!

Please do not mind non-mathematical description below.

I am describing the following to know from you if there is a mathematical definition relating to the following (similar or different)

AA: I formulated a proposal that precision of a concept is the fineness with which a concept is described. Then I found that one can keep adding finer details arbitrarily to the same concept without adding any “distinction” to the concept.

BB: Then it occurred to me that the precision of a concept is its “distinction” from similar concepts which I realized is a “sub-class” of a “class” in Object Oriented Analysis and Design.

CC: Then I thought that precision of concept depends on the depth of a sub-class in a class. On further thinking it occurred to me that every sub-class in a class is equally precise to convey whatever that sub-class stands for.

DD: I see a lot of what you discuss is about “attributes”. How about “methods” or “operations” of OOAD? I see that ability to act is also treated as an attribute. Does it help to distinguish “ability to act” as a method or an operation in OOAD?

EE: Coming back, “precision” of a concept is NOT fineness or coarseness but its distinction from all other sub-classes.

FF: Would it be correct to say that precision of a concept is 1/n where n is the number of all sub-classes including the root class or base class of a class?

Hope this is NOT too much of off-topic discussion.

You may respond to me directly without drifting away from your main topic in this discussion.

Thanks and regards

putchavn@yahoo.com 30 DEC 13

Posted by: Putcha V. Narasimham on December 30, 2013 2:52 PM | Permalink | Reply to this
Read the post Galois Correspondences and Enriched Adjunctions
Weblog: The n-Category Café
Excerpt: Translate from category theory to order theory
Tracked: February 5, 2014 11:13 PM

Re: Formal Concept Analysis

believe there’s a ⊆ flipped in the line stating the Galois connection property. very helpful post though, thanks.

Posted by: Matt Earnshaw on August 17, 2016 12:48 AM | Permalink | Reply to this

Re: Formal Concept Analysis

Hi Matt, do you mean the following line?

I *(A)BAI *(B) I^{\ast }(A)\supseteq B \, \Longleftrightarrow \, A\subseteq I_{\ast }(B)

I think it’s correct (but I could be wrong!) Do you want to explain why you think it’s incorrect?

Posted by: Simon Willerton on August 17, 2016 7:45 PM | Permalink | Reply to this

Re: Formal Concept Analysis

You are quite right. I was caught out by the contravariance of I∗: although the adjoint relation gives (AI (B))(I *(A)B)(A \to I_{∗}(B)) \leftrightsquigarrow (I^{*}(A) \to B), the latter is of course in 𝒫(M) op\mathcal{P}(M)^{\text{op}} and we are instead considering 𝒫(M)\mathcal{P}(M) in stating the Galois connection. Makes sense. Apologies for the confusion.

Posted by: Matt Earnshaw on August 17, 2016 9:59 PM | Permalink | Reply to this

Post a New Comment