Generate and Test
Preview
Optional reading: Winston Chapter 3, pp. 47-50
Guards and Prisoners
KABI is a collection of three components: knowledge representations, problem-solving techniques, and architectures.
Generate and Test method has a generator to generate all the possible next steps (a dumb generator) and a tester to remove illegal solutions.
In the exercise below, list all the possible next steps a generator could come up.
Now, remember, the tester only removes illegal states, so which one/ones will be removed?
Dumb Generators, Dumb Testers
Dumb Generators, Dumb Testers can solve the problem but it is computationally expensive because it would not eliminate states that appeared before.
Smart Testers
Smart Testers eliminate previously visited states and collate the path of problem-solving.
Smart Generators
Smart Generators will not generate states that appeared previously.
When design an AI system, whether to make the generator smarter or tester smarter or balance the two is a practical question to ask.
Discussion: Smart Generators and Testers
Then, for the dead-end paths, who should take the responsibility to terminate them, the generator or the tester? David said tester. Is he right?
examples of the intelligence question
The transformation from C to the options are not discrete, so the space of the possibilities can become very large very quickly. So smarter generator and smart testers are critical.
Here is when the knowledge representation become helpful.
- knowledge representation is a high-level abstraction of the problem and ignores a lot of low-level details.
- but knowledge representation alone could not solve the problem. it must coples with a problem-solving method
Generate & Test for Raven’s Problems II
- The way humans solve the problem: learn a transformation rule for A -> B; apply the transformation to C, and get a possible solution, then compare the solution with the options provided. If there is no match, repeat by generating a new set of transformation rules, etc… until a match is found.
I The way knowledge representation + generate & test solve the problem: select an option to calculate semantic networks from C to the option, then compare the semantic networks with the semantic networks of A -> B. Do it repeatedly for all the options and then evaluate all the semantic networks and then select the one with the most possibility or weights.
Wrap Up
The Cognitive Connection
Human beings uses generate and test all the time because we do not have the whole knowledge of the world and our computation ability is limited.
2017-01-21 first draft