EECS 492 sample final exam from Fall 2024
Final Exam
EECS 492 -- Introduction to Artificial Intelligence
Problem 1: MDP [17 points]
In this map, the agent starts in square “Start”. Its goal is to choose a sequence of actions that allow it to arrive at the +1 Terminal state. There is one square an agent can’t enter (labeled “Wall” and shaded gray). There are named states: x, y, and z, and unnamed states (blank). There are two terminal states, +1 and -1.
The agent can go up, down, left or right. In each case, the probability of moving in the intended direction (e.g., tries to go left and does go left) is 0.5. The probability of moving either 90o or -90o (e.g., tries to go left, goes up or down) is 0.25. If the agent hits a wall, either the border of the map or border of the square marked “Wall”, it stays in its current square. Assume Y = 1.
The utility of all states is initialized to 0. The reward associated with transitioning into a state is defined as follows:
a . If the destination state is a terminal state, the reward is +1 or -1 (see map).
b. If the destination state is a non-terminal state, then the reward is as specified (“non- terminal reward”) in each problem below.
1. [2 pts] If the non-terminal reward is 2, which of the following is the optimal policy?
o Left, left, left, right, right, right, right
o Up, up, up, right, right, right, right
o Left, left, left, left, … (forever)
o Right, right, right
2. [2 pts] If the non-terminal reward is -2, which of the following is the optimal policy?
o Left, left, left, right, right, right, right
o Up, up, up, right, right, right, right
o Left, left, left, left, … (forever)
o Right, right, right
3. [3 pts] Assume a non-terminal reward of 0. You are trying to calculate the utility of square z and have decided to use the Bellman update equation. How many update steps are needed for the utility of z to first become non-zero?
o1
o2
o3
o4
4. [4 pts] Assume a non-terminal reward of -0.25. You perform. one iteration of the Bellman update equation. What is U1 (x)? Note: diagram repeated for convenience.
5. [6 pts] Now let’s imagine that the agent is uncertain regarding its starting position. Recall that the walls are along the edge of the map and on the border of the square marked “Wall”. Your agent can perceive the number of walls in its current square. The agent’s perception of number of walls is correct ¾ of the time and incorrect ¼ of the time. Its belief state is as follows: where o represents all states besides x, y, z. Your agent moves up and perceives two walls. What is the new belief state for state y, bI(y)? Leave your answer in terms of α , the normalization constant over all states.
Problem 2: Probability and Bayes [11 points]
1. [4 pts] Suppose that biologists are studying the presence of rabies in bats. They know that 10% of all bats have rabies. However, the biologists have an imperfect rabies test: 90% of the bats who do have rabies test positive for rabies, while 20% of the bats who do not have rabies will also test positive (meaning that they are incorrectly diagnosed with rabies).
Define two Boolean random variables, T and H. Let t represent the event of a positive rabies test, and ¬t a negative test. Let h represent the event of a bat having rabies, and ¬h a bat not having rabies.
If a trapped bat tests positively for rabies, what is the probability that it actually has rabies? Leave your answer as a fraction.
2. [2 pts] Suppose we have three random variables: A, B, and C. Write out the definition of conditional probability: P(A|B).
Answer all questions with respect to the following network topology to the right. Leave all probabilities in terms of fractions
3. [1 pt] Given the network to the right, you can compute any joint probability over the five variables.
o True
o False
4. [2 pts] Write out the joint probability in terms of
conditional probabilities as suggested by the network structure in the figure.
o P(A, B, C, D, E) = P(EIC , D)P(CIB)P(DIB)P(BIA)
o P(A, B, C, D, E) = P(EIC , D)P(CIB)P(DIB)P(BIA)P(A)
o P(E) = P(EIC, D)P(CIB)P(DIB)P(BIA)P(A)
o P(A, B, C, D, E) = P(EIA, B, C, D)P(CIA, B)P(DIA, B)P(BIA)P(A)
o P(E) = P(EIA, B, C, D)P(CIA, B)P(DIA, B)P(BIA)P(A)
5. [2 pts] Calculate P(a, ~b, ~c, d, e)
Problem 3: Reinforcement Learning [6 points]
Suppose that an agent will use a Reinforcement Learning (RL) approach to learn more about the world. Consider the map to the right of this page. There are two terminal squares (C and F). The agent can move in the following ways: up (e.g., B → E), right (e.g., B → C), left (e.g., B → A), down (e.g., E → B).
If the agent hits a wall, it stays in its current square (e.g., if the agent is in A and goes left, the agent stays in state A). Otherwise, all actions are executed perfectly, as intended by the agent. When an agent reaches the terminal state, there is only one action available (exit) at which point the agent is no longer in this world.
Suppose the agent executes two separate episodes: Episode 1: A, B, E, F and Episode 2: A, B, C.
As it enters a given square, it receives the following rewards: Square F: r = +1, Square C: r = -1, all other squares: r = -0.1.
1. [2 pts] Use direct utility estimation (DUE) to calculate the utilities after episode 1 (write answers in the table below – answers not written in that table will not be considered)
2. [2 pts] Use DUE to calculate the utilities after episode 2 (write answers in the table)
3. [2 pts] What is the final utility estimate for DUE (write answers in the table)
Enter your answers in this table, use NA (not applicable) for any unknown values
|
|
A
|
B
|
D
|
E
|
|
Episode 1
|
|
|
|
|
|
Episode 2
|
|
|
|
|
|
Final
|
|
|
|
|
Problem 4: Neural Networks [10 points]
1. [1 pt] You have decided to build a neural network classifier to predict how tall a given plant will grow, given information about the amount of light that it receives on a given day. Which loss function is most appropriate for this task?
o Binary cross entropy (BCE)
o Root mean square error (RMSE)
2. [1 pt] Given an arbitrarily large neural network, any continuous function can be learned.
o True
o False
3. [2 pts] You should decide when you should stop training your network by assessing performance on the:
o Training data
o Validation data
o Testing data
4. Consider the neural network architecture, above. The weights are shown on each branch. There are labels, Q4a and Q4b, they refer to the two questions that follow. Assume that the threshold function uses a threshold of 0 (when the function’s input is greater than or equal to 0, it outputs a 1). You are given x = [x0 , 2, 1, -5]. Hint: assign the correct value to x0, as discussed in lecture.
a . [3 pts] What is the value after the threshold is applied (Q4a in the figure above)?
o0
o1
o None of the above
b. [3 pts] What is ^y (Q4b in the figure above)?
Problem 5: Decision Trees [9 points]
1. Let’s say that you are trying to build a decision tree classifier to classify “Happy”. You have data of the following form.
|
Data
|
Sunny
|
Weekend
|
Productive
|
Happy
|
|
x1
|
1
|
1
|
1
|
False
|
|
x2
|
1
|
0
|
1
|
True
|
|
x3
|
0
|
1
|
1
|
True
|
|
x4
|
0
|
1
|
0
|
True
|
|
x5
|
0
|
1
|
1
|
True
|
|
x6
|
0
|
0
|
0
|
False
|
[1 pt] What is B(1/2) →
[6 pts] Calculate the information gain over the attribute Productive.
[2 pts] Assume that we split on the attribute Sunny. What is the entropy of the Happy attribute in the branch where Sunny = 0?
o0 o8/10
o6/10 o9/10
o7/10 o1
Problem 6: Concept Questions [19 points]
1. [1 pt] If A is among B’s k-Nearest Neighbors, then B must be among A’s k-Nearest Neighbors.
o True
o False
2. [1 pt] BFS has a lower space complexity than DFS.
o True
o False
3. [1 pt] Multiple nodes in a search tree can represent the same state.
o True
o False
4. [1 pt] Consider the SAME function. It takes two binary inputs, and outputs a 1 if both inputs are the same, or 0 otherwise. True or False: A perceptron network (without hidden layers) can learn the SAME function.
o True
o False
5. [1 pt] It is good practice to train a classifier until the training loss gets as low as possible.
o True
o False
6. [1 pt] Neural networks are maximum margin classifiers.
o True
o False
7. [1 pt] There are local minima to avoid when minimizing loss in linear regression.
o True
o False
8. [1 pt] A* is an example of local search.
o True
o False
9. [1 pt] Fully observable environments are always known.
o True
o False
10. [1 pt] You have created a new agent and you would like it to operate effectively in the
world. You have decided to accomplish this goal using reinforcement learning, specifically one using a model-based approach. True or False: At the end you will always have an estimate of the transition probabilities and the reward function.
o True
o False
11. [1 pt] Select the approach in which you are given a fixed policy, τ
o Passive RL
o Active RL
o Neither
o Both
Two companies, Company One and Company Two, are attempting to rationally maximize their own profit. Each company can either take Action A or Action B. The two companies must decide this simultaneously. The payoff matrix for each company’s profit is shown below, where Company One is the row player and Company Two is the column player.
|
|
Two: A
|
Two: B
|
|
One: A
|
One=$0, Two=$0
|
One=$0, Two=-$10k
|
|
One: B
|
One=-$10k, Two=$0
|
One=-$2k, Two=-$2k
|
12. [2 pts] What is the dominant strategy for Company One?
o Action A
o Action B
o No dominant strategy
For the following two questions (13 and 14), consider the following knowledge bank (KB):
1. cat(x) → Feline(x)
2. Bird(x) → ¬cat(x)
3. ¬cat(Tweety) Λ ¬cat(Robin)
4. cat(x) Λ Bird(y) → EatsBird(x, y)
5. Bird(Tweety)
6. Bird(Robin)
13. [1 pts] The KB is written in propositional logic (true/false)
o True
o False
14. [4 pts] Which of the following is entailed by the knowledge base (select all)?
o ¬cat(Tweety)
o cat(sylvester)
o ¬cat(x) V Feline(x)
o cat(x) Λ ¬Feline(x)
o cat(Robin) → Feline(Robin)
15. [1 pt] In minimax and alpha-beta pruning, which player always goes first?
o Max
o Min
o It depends