COMP4015 Artificial Intelligence and Machine Learning Semester 1, Year 2019-2020
Additional Assignment
Due Date and Time: December 20, 2019 (4:59pm Hong Kong Time)
Questions (Total Scores: 100):
1. Given a search tree with branching factor b, supposing the solution is at the depth level d (d > 0), the overhead of repeatedly expanded states in Iterative Deepening Search method is obvious. Please propose a method to save this cost, and analyze how much this saving can be achieved. (15 marks)
2. (a)
(b)
Let us consider a scenario: Given a problem, there does not exist an appropriate evaluation function. Instead, there is a way to tell which node is better as given a pair of nodes. Is this enough for A* search? If no, explain it. Otherwise, what properties of A* search do we give up if we only use this method? (10 marks)
We show that an admissible heuristic leads to monotonically nondecreasing f values in A* search along any path. Does monotonicity in f imply admissibility of the associated h? Please explain it.
3. Consider the following story:
Anyone gaining his job promotion and making profit from his stock investment is happy. But anyone who works hard or is lucky can gain job promotion. Joe did not work hard but he is lucky. Anyone who is lucky makes profit from his stock investment.
(a) Represent the above English story using first-order logic. (10 marks) (b) Answer the question “Is Joe happy?” by resolution refutation proof. (10 marks)
4. (a) Peter and Mary, in different places, individually use their telescopes to count the number of stars N in a region of the sky. The counting results are M1 and M2, respectively, each of which would have a small probability of counting error by up to one star. Also, each telescope may be likely out of focus (i.e. events F1 and F2). It turns out that Peter and Mary will undercount by three or more stars. Suggest an efficient way to represent the joint probability of these five variables, i.e. P(M1, M2, N, F1, F2), and justify your answer. (10 marks)
(b) You are an AI consultant for a credit card company, and your task is to construct a belief net that will allow the company to determine whether or not to grant a person a card. Which variables will you consider? Construct your network by incrementally adding the variables you mentioned in causal order. (10 marks)
(5 marks)
1
5. Given an unfair coin, we repeatedly flip this coin 100 times. In 80 of the 100 trials, the output value is head, denoted as 1; in the other 20, it is tail, i.e. 0. What will a back-propagation network predict for this coin, assuming that it has been trained and reaches a global optimum? Justify your answer.
(8 marks)
6. Consider two learned hypothesis, h1 and h2, for some Boolean concept. When h1 is tested on a set of 100 examples, it classifies 85 correctly, while h2 classifies 90 correctly. Can we simply draw a conclusion that h2 is generally better than h1? If yes, please justify your answer. Otherwise, please give a more
reasonable way to draw a conclusion.
7. Suppose there are 14 samples from the credit history of loan applications:
(8 marks)
Risk
high high moderate high
low
low
high moderate low
low
high moderate low
high
No. Credit History Debt Collateral
1 bad high none
2 unknown high none
3 unknown low none
4 unknown low none
5 unknown low none
6 unknown low adequate
7 bad low none
8 bad low adequate
9 good low none
10 good high adequate
11 good high none
12 good high none
13 good high none
14 bad high none
Income
$0 to $15k $15k to $35k $15k to $35k $0 to $15k over $35k over $35k
$0 to $15k over $35k over $35k over $35k
$0 to $15k $15k to $35k over $35k
$15k to 35k
propose a bit-string encoding of hypotheses when a genetic algorithm is used. Please discuss the potential limitation of your proposed encoding scheme, if any. (6 marks)
8. One claims that reinforcement learning is an appropriate abstract model for human learning. Do you
agree or not? Please discuss it.
(8 marks)
< END >
2
Reviews
There are no reviews yet.