代写600.464/664 Artificial Intelligence Spring 2019 Final Exam代写留学生Matlab语言程序

Final Exam

600.464/664 Artificial Intelligence

Spring 2019

Basic Search                                                                                                 10 points

1.  (5 points) Number the nodes (1, 2, ...)  in the order they are explored in depth-first search. Process children left to right.

2.  (5 points) Number the nodes (1, 2, ...)  in the order they are explored in iterative deepening search. Enter multiple numbers, if a node is visited more than once.

Process children left to right.

Informed Search                                                                                          10 points

Consider the search space below, where S is the start node and G satisfies the goal test. Arcs are labeled with the cost of traversing them and the heuristic cost to the goal is reported inside nodes (so lower scores are better).

3.  (10 points) For A* search, indicate which goal state is reached at what cost and list, in order, all the states popped of of the OPEN list. You use a search graph to show your work. Do not expand paths that revisit states at higher cost.

Note: When all else is equal, nodes should be removed from OPEN in alphabetical order.

Path to goal (cost):

States popped of of OPEN:

First Order Logic                                                                                         20 points

4.  (6 points) Convert the following sentences into first-order predicate calculus logic:

If a student gets a good grade in an exam in a class, they are happy.

If a student takes a exam for a class, studied for the exam in the class, and is smart, they get a good grade.

If a student takes a class, they take the exam.

Jane takes the class Artificial Intelligence.

Jane studied for the exam in Artificial Intelligence.

Jane is smart.

5.  (6 points) Convert all rules to Conjunctive Normal Form (CNF). You do not need to restate rules that are already in CNF.

6.  (8 points) Carry out a resolution proof of the statement Jane is happy. Hint:  start with : Happy(Jane).

Probabilistic Reasoning                                                                               15 points

If students know the material, they answer a yes/no question correctly p(cjk) = 99% of the time. If students do not know the material, they get it right p(cj:k) = 50% of the time.

When a students answer a question correctly, you want to know the probability p(kjc) that they know the material.

7.  (5 points) Give an explanation why this is not su册cient information to compute the probability p(kjc)?

8.  (5 points) Assume that half of the students know the material.  Compute the probability p(kjc).

9.  (5 points) Instead, assume that on average 80% of the students answer the question correctly.  Compute the probability p(kjc).

Machine Learning                                                                                        10 points

Consider the following plot of data points (circles and squares).

10.  (5 points) Build a linear classifier  (x; y) → shape. You do not have to get the optimal parameter values for the model but they should be reasonable.

11.  (5 points) Draw a decision tree for this data.  Will it classify all examples correctly?

Reinforcement Learning                                                                              20 points

Consider the non-deterministic reinforcement environment drawn below.  States are represented by circles, and actions by squares.  The Probability of a transitions is indicated on the arc from actions to states. Immediate rewards are indicated above and below states. Once the agent reaches the end state the current episode ends.

12.  (15 points) The current policy is to always take action X.

(a)  What paths could be taken?

(b)  What is each path’s probability?

(c)  What is each path’s reward?

(d)  What is the utility of each state?

13.  (5 points) Assuming that under the current policy state b has higher utility than state a.

(a)  How will a greedy agent that has access to the transition probabilities change the policy? (b)  Is the updated policy guaranteed to be the best policy?

Natural Language Processing                                                                       15 points

14.  (5 points) Co-reference resolution.

(a)  Consider the following sentences.

The boy kicks the ball. He scores a goal.

To which noun (boy, ball or goal) does the pronoun he refer to?

How can a computer identify the right noun?

(b)  Consider the following sentences.

Jane went to the store to eat a pizza. It was very tasty.

To which noun (Jane, store or pizza) does the pronoun it refer to?

How can a computer identify the right noun?

15.  (10 points) N-Gram Language models.  You  are given the following text (tokenized, lowercased) as training data (with <s> as beginning-of-sentence marker and </s> as end-of-sentence marker).

<s> the sun is shining .  </s> <s> the girl is going to the park with the boy .  </s> <s> the boy gives the girl a flower .  </s> <s> she is happy .  </s> <s> the boy is happy , too .  </s>

You use this data to train a bigram language model with maximum likelihood estimation. What score will it assign to the following sentence?

<s> the girl is happy .  </s>