[SOUND] [MUSIC] This is a formal context where objects and attributes are all the divisors of 100. And we put a cross if an object is a divisor of an attribute. So, for instance, four is a divisor of 20. You can divide 20 by 4, and you get 5. So, you have a cross here. But four is not a divisor of 10. So, we don't have a cross here. Four doesn't divide 10. And this is the concept lattice of this formal context. It's very irregular, because the data is kind of very regular. And so this is the structure of the data in the form of a concept lattice. Now let's try to reduce this formal context to keep all those objects and attributes that are necessary to obtain this structure. First we need to identify objects that are irreducible. Actually there's an easy way to do this if you look at the concept lattice. In a concept lattice, we have some nodes labeled by objects. Well, in this concept lattice, all Nodes are labeled by objects. And it turns out that an object is irreducible if and only if there is exactly one edge that connects it from below to the rest of the lattice. So four is irreducible, but, let's say, 10 is not irreducible. 10 is the supremum of two and five, and, indeed, if we look into the formal context,so what’s, what is, {10}'? Well, {10}' is the set of all attributes that 10 has. And these include 10, 20, 50, and 100— so exactly all the numbers that 10 divides, for which ten is a divisor. And now let's look at two and five. {2, 5}' is the set of all attributes shared by 2 and 5. So what are these attributes? Let's compute the intersection of this row and this row, the one that corresponds to 2 and the one that corresponds to 5. What do they have in common? So this is an attribute that 2 has, but 5 doesn't. The same here. Here, this attribute 5 has, but 2 doesn't have. So we have this attribute shared by both, and this is 10. This attribute is also shared by both— 20. Well, what else? This one, 50, and finally this one, 100, and you see it's exactly the same as {10}'. So it's the same set. So 10 is reducible, because its intent can be obtained as the intersection of intents of 2 and 5. And you can see this in the lattice. We have two downward arcs coming out of 10 to 2 and to 5, so it's reducible. Okay, so let's use this principle to mark objects that are irreducible. Now 1 has no arcs at all, has no downward arcs at all, so it's reducible. 2 is irreducible, 4 is irreducible. 5, where is 5? 5 is irreducible. 10 is reducible. 20 is also reducible, because it's the intersection of 4 and 10. And what else? 25 is irreducible. And 50 is reducible, and 100 is reducible, because we have two arcs here. Actually... So the irreducible objects are 2, 4, 5, and 25. And if you think a little bit, it turns out that reducible objects in this case are products of other different numbers from the context. Well, with the only exception of one. So one is not a product of any other numbers in this context, but all other reducible elements are. So 10 is the product of 2 and 5. 20 is the product of 5 and 4, and so on. So again you can see this in the lattice. So 20 is the product of 4 and 5, these two elements, so it's the supremum of these two elements. Now, let's look at reducible attributes. Well, an attribute is irreducible, if, when you look at it's attribute concept, that is, the concept labeled by this attribute, you can see only one arc that goes upwards. In particular, here 20 is irreducible, because it has only one uppward arc. So, it's not the infimum or any other concepts. This concept is not the infimum of any other concepts. And the extent of 20 cannot be represented as the intersection of any other attribute extents in the context. Okay, so let's check all of them. 1 is not irreducible, so 1 is reducible, because we have two arcs. It’s the intersection of 2 and 5. And 2 is also reducible. 4 is irreducible. So, we need 4. 5 is reducible. 10 is reducible. 20 is irreducible. 25 is here, and it's irreducible. 50 is irreducible. And 100 is reducible. All right, so it turns out that, in this case, reducible attributes are precisely the greatest common divisors of other numbers. Well, with the exception of 100, so 100 is reducible, but it doesn't satisfy this property. Indeed, so let's take some reducible element, 10 for instance. So 10 is the greatest common divisor of 20 and 50, and, for instance, 5 is the greatest common divisor of 10 and 25. So, in this case, in this lattice, the greatest common divisor is the operation that corresponds to the infimum operation. And so, if an element can be represented as the greatest common divisor of other numbers, then it's reducible, then it can be represented as the infimum of other nodes in this lattice. Okay, so now we have identified irreducible objects and irreducible attributes. Let's build our formal context. So the objects are 2, 4, 5, and 25, and the attributes are 4, 20, 25, and 50. And so 2 is a divisor of 4, a divisor of 20, not of 25. It's a divisor of 50. 4 divides 4, divides 20, divides nothing else. 5 divides 20, 25, and 50. And 25 divides 25 and 50. And that's the standard context of this lattice. And it's also a reduced version of this formal context. Well, the concept lattice of this formal context is exactly the same as this one, as the concept lattice of the original context, but now we have fewer labels, because we removed some objects and some attributes. And so now it looks like this. All reducible objects have disappeared, and all reducible attributes have also disappeared. We no longer have 20 as an object, because it's reducible. But we still have it as an attribute, because, as an attribute, 20 is irreducible. As for 10, it has disappeared completely, because it's reducible both as an object and as an attribute. What's important here is that we have obtained a context which is much smaller than the original context, but we still have the same concept lattice. And in fact, yes, we have lost some of the information, we have lost all the information about the number 10, for instance. But if we want to keep it, there is a way to add some extra information to the reduced context, so that we can restore the information about 10. What's important is that all other computations can be done with this smaller context, and so this can, in certain cases, lead to faster computations. Actually, computation is what we're going to discuss next. So next we're going to see, finally, how one can build a concept lattice out of a formal context. [SOUND] [MUSIC]