<p>As told in the previous comments, $min\{2^{|O|}, 2^{|A|}\}$ is a correct upper bound. </p>

<p>When the parameter $R$ is also available, we can improve the upper bound to $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}}\}$</p>

CC BY-SA 3.0
2017-02-22T15:42:48.383Z
2017-02-22T15:42:48.383Z
Luz
<p>A context is a tuple $(O, A, R)$ where $O$ is the set of objects, $A$ the set of attributes and $R \subseteq O\times A$ is a relation. For $o \in O$ and $a \in A$ we read $oRa$ as the object $o$ possesses the attribute $a$.</p>

<p>For $P \subseteq O$ and $B \subseteq A$ we define $P'=\{a \in A |  \forall o \in P \, oIa \}$ and $B'=\{o \in O |  \forall a \in B \, oIa \}$.</p>

<p>$P'$ is the set of attributes shared by all object of $P$ and $B'$ is the set of objects having all the attributes of $B$.</p>

<p>A concept of the context $(O, A, R)$ is a couple $(P, B)$ where $P \subseteq O$ and $B \subseteq A$ such that $P'=B$ and $P=B'$.</p>

<p>The concepts may be organised according to a partial order in a structure called a concept lattice (or "galois" lattice). For more info check the wikipedia page on <a href="https://en.wikipedia.org/wiki/Formal_concept_analysis" rel="nofollow noreferrer">Formal Concept Analysis</a>.</p>

<p>The number of concepts in a concept lattice is bounded by :</p>

<ul>
<li>$2^{1+\sqrt{|R|}}$ as told in <a href="https://www.hse.ru/data/2013/03/05/1292994568/2001%20On%20Computing%20the%20Size%20of%20a%20Lattice%20and%20Related%20Decision%20Problems.pdf" rel="nofollow noreferrer">this paper</a> (which mentions a result from <a href="http://puma.uni-kassel.de/bibtex/f8a2333a3b04c2d27588b746530cedcb" rel="nofollow noreferrer">this paper</a> in german). Note that their upper bound is tighter - the one I give here is less precise.</li>
<li>$2^{|O|+|A|}$ according to <a href="http://cla.inf.upol.cz/papers/cla2011/paper16.pdf" rel="nofollow noreferrer">this paper</a> (which is presented as a trivial easy upper bound).</li>
</ul>

<p>I dont understand why these upper bounds are that large.
Intuitively I would say that the number of concepts is bounded by $min(2^{|O|}, 2^{|A|})$. I get this intuition from the observation that since for any pair of concepts $(P_0, B_0)$ and $(P_1, B_1)$ we have $P_0=P_1$ iff $B_0=B_1$, then there can not be more concepts than the number of object sets neither than the number of attribute sets appearing in the lattice.</p>

<p>Could someone explain me if I did a mistake ?</p>

<p>Many thanks, Luz </p>

CC BY-SA 3.0
2017-02-22T14:40:59.270Z
I don’t see what is the problem. Yes, $\min\{2^{|O|},2^{|A|}\}$ is an upper bound. The bound in the second paper is, as you say, “presented as a trivial easy upper bound”, which means there is nothing remarkable on the fact that it is not a good bound, nor is it worth wasting more than a minute to think about. The bound mentioned in the first paper (but coming from a completely different paper [13]) is strictly speaking incomparable with your bound, but usually it is stronger in typical cases where $|O|\sim|A|$.
Emil Jeřábek
CC BY-SA 3.0
2017-02-22T15:04:35.347Z
Thank you for answering :) I'm sorry if my question was trivial. But the fact is that I did not find this easy upper bound $min\{2^{|O|}, 2^{|A|}\}$ anywhere... Those two bounds are the only one I could find. And this made me hesitate. Especially $2^{1+\sqrt{|R|}}$ for which if $|O|$ is much greater than $|A|^2$ then their upper bound leads to something close to $2^{1+\sqrt{|O|}}$, whereas the best upper bound is simply $2^{|A|}$. Maybe those papers should have written that a simple immediate upper bound is $min\{2^{|O|}, 2^{|A|}\}$ for newbies like me :)
Luz
CC BY-SA 3.0
2017-02-22T15:08:55.980Z
Do you think that by integrating the $2^{1+\sqrt{|R|}}$ upper bound we can say that one "good" upper bound is $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}} \}$ ?
Luz
CC BY-SA 3.0
2017-02-22T15:34:04.947Z
Yes, why not, if you have access to all the three parameters.
Emil Jeřábek
<machine-learning><upper-bounds><lattice><relational-structures><data-mining>
Upper bound on the size of a Concept Lattice (Galois Lattice)?
Luz
# Upper bound on the size of a Concept Lattice (Galois Lattice)?

(Asked by: username_0 on 2017-02-22)

A context is a tuple $(O, A, R)$ where $O$ is the set of objects, $A$ the set of attributes and $R \subseteq O\times A$ is a relation. For $o \in O$ and $a \in A$ we read $oRa$ as the object $o$ possesses the attribute $a$.

For $P \subseteq O$ and $B \subseteq A$ we define $P'=\{a \in A | \forall o \in P \, oIa \}$ and $B'=\{o \in O | \forall a \in B \, oIa \}$.

$P'$ is the set of attributes shared by all object of $P$ and $B'$ is the set of objects having all the attributes of $B$.

A concept of the context $(O, A, R)$ is a couple $(P, B)$ where $P \subseteq O$ and $B \subseteq A$ such that $P'=B$ and $P=B'$.

The concepts may be organised according to a partial order in a structure called a concept lattice (or "galois" lattice). For more info check the wikipedia page on [Formal Concept Analysis](https://en.wikipedia.org/wiki/Formal_concept_analysis).

The number of concepts in a concept lattice is bounded by :

* $2^{1+\sqrt{|R|}}$ as told in [this paper](https://www.hse.ru/data/2013/03/05/1292994568/2001%20On%20Computing%20the%20Size%20of%20a%20Lattice%20and%20Related%20Decision%20Problems.pdf) (which mentions a result from [this paper](http://puma.uni-kassel.de/bibtex/f8a2333a3b04c2d27588b746530cedcb) in german). Note that their upper bound is tighter - the one I give here is less precise.
* $2^{|O|+|A|}$ according to [this paper](http://cla.inf.upol.cz/papers/cla2011/paper16.pdf) (which is presented as a trivial easy upper bound).

I dont understand why these upper bounds are that large.
Intuitively I would say that the number of concepts is bounded by $min(2^{|O|}, 2^{|A|})$. I get this intuition from the observation that since for any pair of concepts $(P\_0, B\_0)$ and $(P\_1, B\_1)$ we have $P\_0=P\_1$ iff $B\_0=B\_1$, then there can not be more concepts than the number of object sets neither than the number of attribute sets appearing in the lattice.

Could someone explain me if I did a mistake ?

Many thanks, username_0

**Tags:** machine-learning, upper-bounds, lattice, relational-structures, data-mining

> **Comments:**
> **username_1**: I don’t see what is the problem. Yes, $\min\{2^{|O|},2^{|A|}\}$ is an upper bound. The bound in the second paper is, as you say, “presented as a trivial easy upper bound”, which means there is nothing remarkable on the fact that it is not a good bound, nor is it worth wasting more than a minute to think about. The bound mentioned in the first paper (but coming from a completely different paper [13]) is strictly speaking incomparable with your bound, but usually it is stronger in typical cases where $|O|\sim|A|$.  
> **username_0**: Thank you for answering :) I'm sorry if my question was trivial. But the fact is that I did not find this easy upper bound $min\{2^{|O|}, 2^{|A|}\}$ anywhere... Those two bounds are the only one I could find. And this made me hesitate. Especially $2^{1+\sqrt{|R|}}$ for which if $|O|$ is much greater than $|A|^2$ then their upper bound leads to something close to $2^{1+\sqrt{|O|}}$, whereas the best upper bound is simply $2^{|A|}$. Maybe those papers should have written that a simple immediate upper bound is $min\{2^{|O|}, 2^{|A|}\}$ for newbies like me :)  
> **username_0**: Do you think that by integrating the $2^{1+\sqrt{|R|}}$ upper bound we can say that one "good" upper bound is $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}} \}$ ?  
> **username_1**: Yes, why not, if you have access to all the three parameters.  

---

## 1 answers

### Answer by username_0 on 2017-02-22. Score: 1 | Accepted answer

As told in the previous comments, $min\{2^{|O|}, 2^{|A|}\}$ is a correct upper bound.

When the parameter $R$ is also available, we can improve the upper bound to $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}}\}$


---

