[MUSIC] In the next few videos, we'll look into how we can compute implications using queries when we don't have direct access to the formal context. We'll learn two algorithms that use different sets of queries, but let's start with a motivating example, which you'll have to finish yourself as part of this weak problem set. We'll be looking at loopless directed graphs. A loopless directed graph is given by (V, E), where V is a set of vertices and E is a set of edges. And every edge... Every edge is an ordered pair of vertices. So the direction matters, that's why it's directed. And also we don't allow edges that connect a vertex to itself. So, (v, v) is not part of E for all vertices v. Now, loopless directed graphs will be objects of our formal context. And we'll be interested in the following properties, which will be our attributes. So, a graph is called strongly connected if there is a directed path from any vertex to any other vertex. For example, this is a strongly connected graph, because if we start from this vertex we can visit all other vertices. If we start from this vertex we can visit all other vertices also. And what else? Well, yeah, and this holds for all the vertices of this graph. A graph is weakly connected if we can do the same but only if we ignore the direction of edges. So let's look at this graph, the same as the previous one, but it doesn't have the middle vertex. Now this graph is only weakly connected. It's not strongly connected, because we can't go from this vertex anywhere at all. It is however weakly connected because if we allow ourselves to go in the opposite direction of an edge, then we can reach any vertex from this vertex and any vertex from every other vertex. So that's weakly connected. And it's also possible that a graph is not even weakly connected. In this case, it's called disconnected. And if a graph is disconnected, it means that it has two or three or more absolutely disconnected pieces. So, for instance, if we look at this graph... Now this graph has five vertices, but you can't get from this vertex to this vertex, even if you ignore the direction of edges. So you have, like, two separate pieces. Okay, so these are three properties, and we'll also need a few more. Okay, we'll say that a graph is rooted if there is one vertex from which you can reach all other vertices. Now this graph is, of course, rooted because you can reach every vertex from every other vertex. So any vertex in this graph can be chosen as a root. This graph is also rooted, because you can choose this vertex as a root, and, from this vertex, you can go to any other vertex. Well, this graph is not rooted, because it's disconnected, but each of the pieces is rooted. So here the root is this one and here the root is, well, here any vertex can be considered a root, because, if you remain in this triangle, you can go from every of the three vertices to every other of the three vertices. Okay, so the next property is acyclic. A graph is acyclic if it contains no cycles, that is, if it's not possible, once you left the vertex, it's not possible to come back to it. So, well, this graph is not acyclic, because you can go from this vertex to this vertex, from this vertex to this vertex, and then back to the initial vertex. So you have a cycle of three vertices. This graph is, however, acyclic, because once you left, for instance, this vertex, you can't get back to it if you go along the direction of each edge. So you can go here, then here, and then you're stuck. Or you can go here and here, and then you're stuck again. So this is acyclic, and this is not. This one is also not acyclic, because there's a cycle. And if we take this graph as a whole, it's also not acyclic. This part is acyclic, but, because you have a cycle in this part, the whole graph is not acyclic. Some graphs are also transitive. And this means that, whenever you have two vertices connected to each other, so the first vertex is connected to the second vertex and, let's say, this second vertex is also connected to some third vertex, then you must have an edge from the first vertex to the third vertex. So, whenever the first vertex is connected to the second and the second has an edge to the third, there must be an edge between the first and the third. These graphs are not transitive, because we have an edge from this vertex to this vertex, from this vertex to this vertex, but we don't have an edge that goes from here to here. And similarly here. And here we have an edge that goes from this vertex to this vertex, from this vertex to this vertex, but we don't have an edge that goes from here to here. Well, we have an edge that goes from the third vertex to the first, but that's not what we need for a graph to be transitive. And the seventh property that we'll consider is tournament. So a graph is called a tournament if, for every two vertices, there is exactly one edge connecting them. And this edge goes either one direction or the other direction. So, if you have two vertices, you must have either this edge or the opposite edge. So, for example, this is a tournament, as well as this one. But, if you add another vertex here and connect it, let's say, only to this vertex, it's not going to be a tournament, because now this vertex and this vertex are not connected by any edge. And also, if you add an edge that goes in the opposite direction of the existing edge, like here (so you have an edge that goes in both directions), this is also not a tournament. There should be only one direction between every two vertices. Okay, so these are our attributes, and our objects on loopless directed graphs. And we want to learn the implication theory of loopless directed graphs in terms of these properties. What kind of implications we may have here? Well, every such implication is a sort of a theorem. For example, we may consider this implication: acyclic and tournament implies transitive. Or, in more human terms, we can say that acyclic tournaments are transitive. And that sounds like a theorem. It's not completely obvious that it is true, but, well, it turns out it is true. So that's one potential theorem that we may want to discover. Another one is kind of more obvious. We can say that strongly connected graphs are rooted. And again, this is an implication. We say that strongly connected implies rooted and that's an obvious implication. For a graph to be rooted, you must have one vertex from which you can reach all other vertices, but, if a graph is strongly connected, then every vertex satisfies this condition. Okay, there may be some other theorems. And we want to be able to enumerate all of them and check those that are indeed valid. That's where learning with queries will help us. Here we work with a finite number of attributes, and so the context of loopless directed graphs described in terms of these attributes must have a finite implication basis and a finite concept lattice. But it has an infinite number of objects. We can't put all of them into a table and apply our usual algorithms for computing the canonical basis. Well, frankly we don't need to do this. Although there are infinitely many loopless directed graphs, there are only finitely many their descriptions in terms of the seven attributes we are interested in. There are 128 possible attribute combinations, and we could go through all of them, check which ones correspond to realistic descriptions of loopless directed graphs, add only these to our formal context, and then compute its canonical basis. But this is really boring and time consuming. We'll have to verify 128 propositions and this doesn't scale well at all. If we add three more attributes, we'll have to consider already over a thousand of their combinations. And this number grows exponentially. So we'll use learning with queries to reduce the number of propositions that we need to consider. We'll study two approaches. One gives us a polynomial-time algorithm to learn the implication set. The other one is less efficient in terms of complexity, but it is more suitable for practical applications we have in mind. [MUSIC].