[MUSIC] It may happen that, after we computed the concept set of a formal context, a new object appears and it's necessary to integrate it into what we've done so far. It would be a waste of time to start the computation from scratch. It would be nice to be able to somehow change our concept lattice in those places that are relevant to this object. Incremental algorithms do precisely this. So let's say that C is... this beautiful C, calligraphic C, is the concept set of some formal context, K = (G, M, I). And we've computed it. And then a new object arrives. Let's call it g. And we need to add it. So we need to add a new object g. It's new, it's not an our object set, capital G. So we add it with intent g' to our context K. And this updated context, let's call it K_g. Now we want to compute the concept set of this new context. So this is our task, compute the concept set C_g of the context K_g. So how can we do this? Let's look at the concepts of C_g. So let some concept (C,D) be a concept of this updated context. So it belongs to calligraphic C_g. Let's consider a few cases. Well, first of all, the extent of this concept C, either it includes g or it doesn't. So the first case is when g is in C. Then if g is in C, there are again two cases. Let's remove g from C. What we get is a pair (C \ {g}, D). And it may happen that this is a formal concept of the old context; so, it belongs to calligraphic C. Or, and this is the second case, g is in C, but (C \ {g}, D) is not in calligraphic C. It's not a concept of the old context. Why isn't it a concept of the old context? This may happen if objects from C, except for g, not only share attributes from D, but they share something else. So there's another attribute not shared by g, but shared by all other objects from C. In this case, there is a concept C \ {g}, with the extent C \ {g} and the intent (C \ {g})'. And this is a concept of the old context. Why so? Well, for it to be a concept, (C \ {g})'' must be equal to C \ {g}, and this is indeed so. There are no others objects in formal context K that have all attributes from (C \ {g})', because there are no objects in this context that have all attributes from D. So all objects that have all attributes from D are among these objects, are among those in C. And D is a subset of (C \ {g})'. Therefore, this is precisely the set of all objects that have all attributes from this set. And therefore, this is a formal concept of the old context. Let's call it the generator of the concept (C, D). So every concept (C, D) of the second type has a unique generator in the old context. Okay. And the third case is when g is not in C. Well, in this case, (C, D) is simply a concept of the old context. It belongs to calligraphic C. So we classified all concepts of the new context into one of three types. Now let's check how this helps us compute them. So the general incremental strategy looks like this. We have the concept set C, calligraphic C, of the old context. We have a new object g with intent g'. And we want to compute calligraphic C_g. So we initialize it with the empty set. And then we go through all concepts of C of the old concept set. For (A, B) in calligraphic C we do this: First we check if B is a subset of g'. Well, if B is a subset of g', then we're in Case 1. (A, B) is in fact this concept, (C \ {g}, D), and then, if we add g to A, we'll get a formal concept of a new context. So this is Case 1, and we add the concept (A union {g}, B) to our new concept set. Note that, in doing so, we handle all new concepts of the first type, because, for each of them, there is a concept (C \ {g}, D), which is among the old concepts, and here we go through all old concepts. So every concept of the first type will be generated here, will be added to the set of C_g here. Else, so what if B is not a subset of g'? Then we cannot add g to the extent of this concept, because it doesn't have all attributes from B. But then it means that (A, B) is itself a concept of the new context, because all objects from A still have all attributes from B; there are no other objects in K that have all attributes from B (because (A, B) is an old concept; and the new object g, it also doesn't have B. So this is a concept of a new context, and we add it. And this is actually Case 3. And again, we add all concepts of type 3 in this line, but there's more that we have to do here. We compute the intersection of B and g'. And then we add the concept (D', D) to Cg. This is Case 2. Why is it a formal concept? For it to be a formal concept, D must be equal to D''. So let's check this. Let's look at objects from D'. What do they have in common? What attributes do they share? Well, objects from D' include all objects from A. So they share at most all attributes from B. So D must be a subset of B. But D' also includes g. So D can include only those attributes from B... D'' must include only those attributes from B that are in g'. So, D'' equals the intersection of B and g'. Or, in other words, D'' equals D. So, this is indeed a formal concept. And we add it to C_g, and this is the second case. Why do we handle all concepts of the second type here? Well, because every concept of the second type has a unique generator. And sooner or later, this generator will be (A, B). We will consider it in our algorithm. A problem that we have here is that (D', D) can be generated several times. So we need some mechanism to avoid duplicates. And this can be done in different ways. So first of all, one can use a smart data structure to implement the set C_g, so that, when we add a set, when we add a concept to C_g, if this concept is already there, we don't produce a duplicate. The set doesn't change. Here options include a trie. This has been done by Nourine and Raynaud. And this gives the theoretically most efficient algorithm known so far. Or one can use a hashtable. This was done by Robert Godin and his colleagues. Or essentially any other reasonable data structure for implementing sets. A quite different approach is to add (D', D) to C_g only when (A,B) is the generator of (D', D). Well not a generator, the generator. Because every concept has a unique generator. So we add D prime D, only if (A, B) is its unique generator. And this, in formal concept analysis, this approach is known as the algorithm of Norris. And it's pretty efficient in practice. We're going to see how it works in the next video. [SOUND]