CS1013 (Grand Challenges of Artificial Intelligence) 12 August, 2009
1. Answer all ten parts of this question. Note that brief answers are expected for these questions.
(a) Name any two of the ten people who were present at the 1956 Dartmouth conference on Artificial Intelligence. (2)
(b) Give an example of a sentence which could be interpreted in more than one way by a natural language understanding system, but where the correct meaning is obvious to a human by using commonsense knowledge. Explain the two possible meanings which the computer could choose. (2)
(c) Give two example Artificial Intelligence applications of search techniques. (2)
(d) Briefly describe one of the advantages of genetic algorithms, when compared with artificial neural networks. (2)
(e) Give an example of a computer vision application which is relatively easy for current systems, and another example of an application which is too hard for current systems. (2)
(f) How is a “Universal Turing Machine” different to a “Turing Machine”? (3)
(g) Briefly explain the type of method used in “shallow” machine translation. (3)
(h) Sketch a diagram of an artificial neural network which has two inputs and one output, and which could recognise the exclusive-or function. You do not need to provide the weights on the connections. (3)
(i) What is the difference between a “cognitive robot” and a “behaviour based robot”? (3)
(j) What is meant by “exploitation” and “exploration” in reinforcement learning, and why must there be a trade-off between them? (3)
(25)
2. (a) Consider the following four board games: draughts, backgammon, chess, go; for each game state if it is difficult or easy for a computer to beat a human; for each game explain why it is relatively easy or difficult for a computer versus a human. Your answer should also mention relevant Artificial Intelligence (AI) techniques where appropriate. (10)
(b) Briefly describe what is meant by a board evaluation function for chess. Given a certain position in the middle of a game of chess, an AI program should be able to suggest the best move to make; briefly explain how an AI program could use an evaluation function to completely search the game tree up to a depth limit, and then to find the best move. (5)
(c) Describe how a machine learning approach could be used to train a computer to play one of the above games. Describe the performance measure to be used, and how the training experience could be gathered. Also describe a possible machine learning technique to be used. (5)
(d) Some Artificial Intelligence (AI) researchers claim that board games are a waste of time for AI research, and are a distraction from the real problems of AI. Explain what is meant by this. Do you agree or disagree with this point of view? Support your answer with arguments. (5)
(25)
PLEASE TURN OVER
3. (a) Consider the “travelling salesman problem”, that is, the problem of finding an ordered list of cities that results in the shortest trip for a salesman to travel. A genetic algorithm is to be used to solve this problem. Describe the meaning of the term “chromosome” in genetic algorithms, and describe how chromosomes might be encoded for the travelling salesman problem. (4)
(b) Explain what is meant by “fitness function” in genetic algorithms. Give an example of an appropriate fitness function in the case of the travelling salesman problem. (3)
(c) Explain what is meant by “crossover” in genetic algorithms. Sketch a diagram showing chromosomes to explain how it works. (3)
(d) Explain what is meant by “mutation” in genetic algorithms. Sketch a diagram showing chromosomes to explain how it works. (3)
(e) A genetic algorithm repeatedly loops through a procedure in order to find improved solutions to a problem. Describe what needs to be given at the start of the procedure, and describe the main steps involved in this procedure. (5)
(f) Apart from the travelling salesman problem, describe two other problems (or applications) where genetic algorithms can be used. (3)
(g) Describe the advantages of genetic algorithms, and the general features of problems which genetic algorithms are particularly good at solving. (4)
(25)
4. (a) What is Cognitive Science? How does it differ from the behaviourist viewpoint which had dominated Psychology in the early twentieth century? (6)
(b) Noam Chomsky is credited with having sparked the “cognitive revolution” in Psychology. Explain Chomsky’s argument of the “poverty of the stimulus”. (5)
(c) Apart from Chomsky’s argument of the “poverty of the stimulus”, what evidence is there to suggest that humans might have an innate knowledge of rules for language which describe a “universal grammar”? Are there any counterarguments which could give an alternative explanation for any of the evidence? (5)
(d) “AI is an Engineering discipline built on an unfinished Science.” - Matt Ginsberg.
What is the difference between Science and Engineering? Explain both with examples. Explain what Matt Ginsberg meant by this quotation. How does AI differ from other Engineering disciplines, such as Civil Engineering or Mechanical Engineering? Give some examples of AI work which could be classified as engineering, and some examples which could be classified as science. (9)
(25)
END OF PAPER
XXX