CSE4301 / 5290FINAL EXAM[14 question, 3 pages, 30 points, Time: 75 min]
WRITE YOURNAME and ID4:
YOU MAY WORK FOR COMPUTATIONS ON BALNK PAGES HERE BUT, THE RESULTS MUST BE ON THIS TABLE, AND ALL ROUGH WORKS MUST BE NUMBERED FOR ME IN CASE I WANT TO VERIFY.
Questions / Write your answers hereQ1. The canonical Decision tree learning algorithm for choosing “next” attribute is by looking at ______of the attribute with respect to all available attributes at that stage, and this quantity is computed based on ______calculation. Fill in these two blanks. / ANS a. Information gain
ANS b. Entropy
[2]
Q2.With five binary attributes making a target decision (e.g. going to a restaurant or not) how many decision trees may be generated (without eliminating any attribute from the tree)? / Ans: 2^2^5
All subsets of truth table
[2]
Q3. A machine learning algorithm is so much biased toward the training set that it often fails in test sets. What is this problem called?
How is it avoided in the decision tree-learning? You need not explain. / ANS a. Overfitting.
ANS b. Decision tree pruning, (and early stopping)
[2]
Q4. What type of learning problem is the following one?
Given a training set learn to predict the classification of a unknown data. / ANS. Supervised learning / Classifier
[1]
Q5. What type of learning problem is the following one?
Given a set of data cluster them into different groups. / Ans. Unsupervised learning / Clustering
[1]
Q6. Your goal is to navigate a robot out of a maze.
The coordinate system is defined so that the center of the maze is at (0, 0), and the maze itself is a square from (−1,−1) to (1, 1). The robot can turn to North, South, East, or West. Initial state: robot at coordinate (0, 0), facing North. Goal test: either |x| 1 or |y| 1 where (x, y) is the current location in real number. Successor function: move forwards any distance d; change direction of robot it is facing.
Cost function: total distance moved.
How large is the state space? / Ans. Infinite. The coordinate system is continuous.
[3.2a, c]
[2]
Q7. In above question, assume now that the maze consists of 3x3 (9) rooms and the robot navigates from room to room (i.e., x and y are integers between -1 and 1).
a. How many doors are possible in the maze to go from one room to another?
b. If there are 4 doors (the robot now moves straight if it sees through doors, i.e. state changes only when robot turns its face), then how large is the search space? / Ans a. 12inner walls.
Ans b. 8,
four turnings to face a door.
[2]
Q8.Search: If f(s), g(s) and h(s) are admissible heuristics, then will the followingsbealso guaranteed to be admissible heuristics? Answer with True/False.
a. f(s) + g(s) + h(s)
b. max(f(s), g(s), h(s)) / ANS a. F
ANS b. T
[Quiz 1]
[2]
Q9. Suppose anAC iteration makes a node empty. Instead of stopping if it is allowed to run to the end (until nothing changes any more) what will happen? / [2]
ANS. All nodes will eventually become empty. AC will never run infinitely on a finite input!
Q10. Consider a vocabulary with the following symbols and express the English statement in First Order logic:
O(p, c): Predicate. Person p has occupation t.
C(p1, p2): Predicate. Person p1 is a customer of person p2.
Constants denoting occupations: Doctor (D), Surgeon (S), Lawyer (L).
a. There exists a lawyer all of whose customers are doctors. (Do not skolemize from Q10-11) / ANS. [2]
a. ∃p O(p,L) ∧∀q C(q, p) ⇒O(q,D).
[8.10 f, g]
Q10 b. Every surgeon has a lawyer.
[Clients are customers] / ANS. [2]
b. ∀p O(p, S) ⇒∃q O(q,L) ∧C(p, q).
Q11. Using a constant Wumpus, and a location variables, create a first order logical statement that says
the Wumpus is not at two different locations.
Predicate: In(x, y) means agent x is at location y / ANS. [2]
∃s1 In(Wumpus, s1) ∧∀s2 (s1 =/= s2) ⇒ ￢In(Wumpus, s2) .
Q12.
toothache / toothache / ~toothache / ~toothache
catch / ~catch / catch / ~catch
cavity / .108 / .012 / .072 / .008
~cavity / .016 / .064 / .144 / .576
Calculate the followings:
(Note upper case for vector)
a. P(Cavity) / ANS a. [2]
This asks for the vector of probability values for the random variable Cavity. It has two
values. First add up for Cavity=true: 0.108 + 0.012 +0.072 +0.008 = 0.2. Then we have
P(Cavity=t/f) = 0.2, 0.8.
[13.8]
Q12 b. P(Toothache | Cavity=true) / ANS b. [2]
P(Toothache|Cavity=t) = (.108 + .012)/0.2, (0.072 + 0.008)/0.2=<0.6, 0.4
Q13. A bag of 3 biased coins a, b, and c (for head: 80%, 60%, 20% respectively). A coin is drawn randomly from the bag and flipped 3 times: X1, X2, X3.
Calculate the probability
P(2heads, 1tail| coin= a) / ANS. [2]
From the Bayesian network we can see that X1, X2, and X3 are conditionally independent
given C, so for example
P(X1 = tails,X2 = heads,X3 = heads|C = a)
= P(X1 = tails|C = a)P(X2 = heads|C = a)P(X3 = heads|C = a)
= 0.8 ×0.2 ×0.2 = 0.032, C is coin
Note that since the CPTs for each coin are the same, we would get the same probability
above for any ordering of 2 heads and 1 tails. Since there are three such orderings, we
have
P(2heads, 1tails|coin= a) = 3 ×0.032 = 0.096.
[14.1b]
Q14. Write your group number and the two algorithms you studied (Grad),
or,mention the two projects you did (Undergrad). / ANS.
[2]