Preview
We now focus on problem-solving methods.
Generate-and-test is a problem-solving method.
The generate-and-test method in a way, is very simple: given a problem, generate potential solutions to it, and then test the solutions for the efficiency for addressing the problem.
We will use this method in conjunction with semantic networks, or the prisoners and guards problem that we discussed last time.
Guards and Prisoners
Knowledge-based AI is a collection of three things.
Knowledge representations, problem-solving techniques and architectures.
We have already look at one knowledge representation, semantic networks.
We have not so far looked at problem-solving methods or architectures.
Today, I’d like to start by talking about the problem-solving method.
Let us illustrate the problem-solving method of generate-and-test with the same examples that we have discussed earlier. When we were discussing this example in the case of semantic networks, we simply came up with various states and pruned some of them without saying about how an AI agent would know what states to prune. So imagine that we have a generator that takes the initial state and from that initial or current state, generates all the possible successive states. For now, imagine it’s not a very smart generator, it’s a dumb generator.
So it generates all the possible states. So the generator test method not only has a generator but also has a tester. The tester looks at all the possible states the generator has generated and removes some of them. For now, let’s also assume that the tester is is dumb as well. And so the tester is removes only those states that are are clearly illegal based on the specific of the problem.
Namely, that one cannot have more prisoners than guards on either back.
So the first and the third states are removed by the tester.
Exercise generate-and-test I - Quiz
Let us continue with this exercise one step further. So now we have three successor states to the initial state. Given these three successor states, what states might the dumb generator generate next?
Exercise generate-and-test I
So from the top state we have three possible next states.
We can move both of them, we can move just the prisoner, or we can move just the guard. From this one we can either move one prisoner or two prisoners, and from this one all we can really do is move the prisoner back over to the left. Remember that David is not generating these successive states.
David is saying that the DOM generator will generate the successive states.
Exercise generate-and-test II - Quiz
So now that we have all of these states that the generator has generated, given that we have a dump tester what states will the dump tester dismiss?
Exercise generate-and-test II - Answer
So the only one of these six states that disobeys our one rule against having more prisoners than guards on either shore, is this state over here. So, that’s the only state that’s going to get thrown out. These five states are all legal according to our dumb testers understanding of the problem. So after we dismiss that state, though.
We’ll notice that we only have two unique states, we have everyone on the left coast and one prisoner on the right coast. So like we did earlier, we can collapse these two down into only these two states. It won’t matter how we got there, once we’re there.
Dumb Generators, Dumb Testers
Now we can continue to apply this method of generate-and-test iteratively. So we can apply it on this state and that state and see what successor states we get.
If we do so, then we get a very large number of successor states. This is a problem of call many total explosion. While one was tasked with a small number of states, but the number of successor states keeps on increasing very rapidly.
Now, the reason it is occurring here and it did not occur when we are talk, dealing with semantic networks is because here we have states like this one which have three guards and three prisoners on the same side of the bank, exactly the same state that was the initial state to begin with. This is because we have a dumb generator and a dumb tester. So this state never got pruned away, although this particular state is identical to the initial state that we started from. This method of generating test, even with a dumb generator and a dumb tester, if applied iteratively could finally lead to the goal state.
In which case, we will have a path from the initial state all the way to the goal state, but this will be computationally very inefficient.
This is because we have a dumb generator and a dumb tester. So the question now becomes, can we make a smarter generator and a smarter tester? Before we make a smarter generator and a smarter tester, we should note that generate-and-test is a very powerful problem-solving method.
Smart Testers
A smart tester should detect and discard states that are : - identical to previously visited states - have no successer states and are not solutions. It detect and merge identical generated current states
Note also that this particular state has no successor states, all successor states of this have been ruled out. Therefore this particular part clearly is not a good path to get to the gold state. If we notice also, that these two states are identical, then we can merge them. If we do so, then we get exactly the same kind of configuration of states that we had when we were dealing with the semantic network in the previous lesson. There is something to note here. We had this semantic network in the last lesson, but the knowledge representation of semantics network, while very useful, by itself and of itself doesn’t solve any problems.
You need a problem-solving method that uses knowledge afforded by the knowledge representation to actually do the problem-solving. Generating test is one of those problem-solving methods. In general, when we do problem-solving or reasoning, then there is a coupling between a knowledge representation and a problem-solving method, like semantic networks and generating test.
What we did so far had a dumb generator, but we made the testers smarter. The testers started looking for what states had been repeated. Alternatively, we can shift the balance of responsibility between them and make the generator smarter. Let’s see how that might happen.
Smart Generators
Instead of the generator generating all the successive states and then a tester finding out that this state, this state and this state are identical to the initial state. One could make the generator itself smarter and say that a generator will not even generate these three states, but it will know that it should not generate states that are already up here.
This means that we can either provide the generator with some additional abilities or the tester with some additional abilities or both. If the generator was smarter, then it would not even generate these three states because they are nonproductive. I would exclude maybe the tester, the determinant of this state is illegal and therefore dismisses it.
We could even go one step further and make the generator even smarter, so the generator will not generate this particular state. And thus, the balance within the generator and the tester can shift depending on where we try to put knowledge. For this problem, for this relatively simple and small problem, the balance will responsibility between the generator and test might look like a tree relationship. But imagine a problem in if there are a million such states. Then whether we have generated very smart or the tests are very smart or both can become a important issue.
Despite that, genetic testing factors are a very popular method used in some schools of AI.
Genetic algorithms, for instance, can be viewed as genetic
Given a number of states, they try to find out all the potential successive states that are possible, given some simple rules of recombination. And then of a fitness function that acts as a tester.
Genetic algorithms, therefore, are an effective method for a very large number of problems.
They’re also a very inefficient method because neither the generator nor the testing generator algorithms are especially smart.
Discussion Smart Generators and Testers - Quiz
What does everyone else think? Is David right about this?
Discussion Smart Generators and Testers - Answer
That sounds like a good answer, to me. So once again, we are back to the issue of where do we draw the balance of responsibility between the generator and the tester?
The important thing to note from here however is that generation test when in doubt with the right kind of knowledge can be a powerful method.
Generate Test for Ravens Problems
Let us return to our problem from the intelligence test to see how generate-and-test might apply as a problem-solving method. Again, here is a problem that we encountered earlier. Notice that this is a more complicated problem than the guards and prisoners problem. Here is why.
In case of the guards and prisoner problem, each transformation from one state to another, was a discrete transformation. One could take a certain number of guards to the other side. One could take a certain number of prisoners to the other side, or one could take a certain of number of guards and prisoners to the other side.
In this case, if I look at the approximation between A and B, and I notice that the diamond inside the circle is now outside the circle and is larger. Now suppose I were to try the same transformation from C to D. So I can look at the circle inside the triangle, put it outside, and also make it larger. I notice that when I put it outside, I can put it outside right next to the triangle, a little bit farther, a little bit farther, a little bit farther away. I can make it the same size, or a little larger, or a lot larger. Increase its size by 50% or 51% or 52%.
So this space of possibilities here is very large. So for problems of this kind, the need for a smarter generator and a smarter tester is critical, because this space of possibilities can become very large, very quickly.
Semantic Networks for generate-and-test
This is where the knowledge representation helps a lot. The semantic network knowledge representation provides a level of abstraction at which the problem gets represented and analyzed. So, although this particular diamond y could have been displaced here or a little bit further, it could have been of this size, maybe a little smaller, a little bit larger. The semantic network really doesn’t care about it.
With the level of extraction which a semantic network is dealing, y gets expanded, and that is all that matters. An important point to note here is that any knowledge representation picks a level of extraction at which it represents the world. There’s a lot of power in it because that knowledge representation ignores things that are at a low level of detail. And therefore the problem-solving method doesn’t have to worry about those things. So it is not the knowledge representation alone that solves the problem, or the problem-solving method that solves the problem. It is the knowledge representation and the problem-solving method coupled together that solve the problem, that provide the reasoning.
Generate Test for Ravens Problems II
So let’s assume that we’re using semantic network as a representation for this particular class of problem.
Given that, how would you apply generate and matter to this problem, David?
So it sounds like would I would do is I would use the transformation between A and B, transfer that transformation to C and use it to generate my answer for D. I then take my answer for D and compare it against 1, 2, 3, 4, 5 and 6 and see which one most closely matched what I generated.
If I wanted to make my tester and generator even smarter, I might say that in order to be the correct answer, it has to meet the generated answer with a certain level of confidence. And if it doesn’t meet that level of confidence, it should go back and see if there’s a different transformation we could have transferred.
That would take care of the problem earlier where either the middle shape disappeared or the outer shape disappeared.
That’s a good answer, David.
It is another way of solving this problem using test and semantic networks.
One could take one, put it under D. Generate the transformation from C to D and then test it against the transformation from A to B.
One could do the same thing with 2, put 2 here into D, directly transformation tested against the transformation A to B.
One could do this for all six choices and then find out, which one of these transformations is closest with the transformation from A to B.
Thus, in this problem, one can use test methods in two very different ways, all of the knowledge representation ribbon is the same.
So knowledge representation captures some knowledge about the world at a level of abstraction.
It is coupled with problem solving methods, but more than one problem-solving method, more than one variation of a problem solving method might be applicable using technology representation.
Assignment Generate Test
So how would you use generate-and-test to actually solve Raven’s Progressive Matrices?
We’ve talked about this a little bit already, but take it a little
bit further and talk about how you would actually implement the problem-solving approach you’ve seen today.
We talked about a couple different ways of going about it.
We talked about generating multiple answers and testing them against the answer options.
Or generating one answer and testing it more intelligently against the different options available to you.
So talk about which one you would do and how you would actually implement it.
In doing so, make sure to think of three-by-three problems as well.
With more transformations and more figures going on, it can be a lot more difficult to figure out what to generate, and the problem space can explode very quickly.
Also make sure to think about how you’re actually going to infer the mapping between different figures in the problem.
How do you know which shape in one frame maps up to a different shape in another frame?
And then talk about how you would use that information to generate what you think the answer is.
Wrap Up
- generate-and-test
- strong generators and
- strong testers
- generating tests an unconstrained domains
The Cognitive Connection
Let us examine the relationship between the method of generate and test, and human cognition. Humans use generate-and-test as the problem-solving method all the time.
This is because we do not have complete or correct knowledge of the world. We do not have infinite computational resources. And we also do not always have recourse to a method of reasoning that is guaranteed to be correct. When you do not have these things, then you use your own test method. You come up with particular solutions to a problem, you test the solutions out. Beyond human cognition, I’m sure you’ve come across the notion of genetic algorithms. Genetic algorithms are inspired by the processes of biological evolution. Through operations like crossover and mutation, one can generate solutions that can then be tested against some fitness function. Genetic algorithm are a good example of the genetical test method. First, genetic solutions, then test them out. So this method of generating test is connected not only with human cognition, but dependently, also with biological evolution. It’s all over the place.
Reuse
Citation
@online{bochman2016,
author = {Bochman, Oren},
title = {Lesson 04 {Generate} \& {Test}},
date = {2016-01-26},
url = {https://orenbochman.github.io/notes/cognitivie-ai-cs7637/04-generate-and-test/04-generate-and-test.html},
langid = {en}
}