# AI辅导 | 机器学习 | CS 540 HW8

There are ﬁve questions in this homework. Please answer the questions in a single pdf ﬁle. Please typeset your homework, do not submit handwritten+scan answers. The pdf ﬁle should be submitted on Canvas.

All assignments are due at the beginning of class on the due date. One (1) day late, deﬁned as a 24-hour period from the deadline (weekday or weekend), will result in 10% of the total points for the assignment deducted. So, for example, if a 60-point assignment is due on a Wednesday 9:30 a.m., and it is handed in between Wednesday 9:30 a.m. and Thursday 9:30 a.m., 6 points will be deducted. Two (2) days late, 25% off; three (3) days late, 50 off. No homework can be turned in more than three (3) days late. Written questions and program submission have the same deadline.

You are to complete this assignment individually. However, you are encouraged to discuss the general algorithms and ideas with classmates, TAs, and instructor in order to help you answer the questions. You are also welcome to give each other examples that are not on the assignment in order to demonstrate how to solve problems. But we require you to:

• not explicitly tell each other the answers

• not to copy answers or code fragments from anyone or anywhere

• not to get any code on the Web

In those cases where you work with one or more other people on the general discussion of the assignment and surrounding topics, we suggest that you speciﬁcally record on the assignment the names of the people you were in discussion with. CS 540

Spring 2019

Given the knowledge base

p =⇒ (q =⇒ r) use resolution to prove the query (p ∧ q) =⇒ (q =⇒ r).

Be sure to show what you convert to CNF (do not skip steps), and how you perform each resolution step.

(1) (7 points) Consider the following axioms:

• Every child loves Santa.

• Everyone who loves Santa loves any reindeer.

• Rudolph is a reindeer, and Rudolph has a red nose.

• Anything which has a red nose is weird or is a clown.

• No reindeer is a clown.

• Scrooge does not love anything which is weird.

• Scrooge is not a child.

Give the First Order Logic (FOL) sentences. You may deﬁne your FOL predicates and functions.

(2) (6 points) Consider the following axioms:

• Every Austinite who is not conservative loves some armadillo.

• Anyone who wears maroon-and-white shirts is an Aggie.

• Every Aggie loves every dog.

• Nobody who loves every dog loves any armadillo.

• Clem is an Austinite, and Clem wears maroon-and-white shirts.

• There is a conservative Austinite.

Give the First Order Logic (FOL) sentences. You may deﬁne your FOL predicates and functions.

Victor has been murdered and Alice, Barney, and Caddy are the only suspects. As the chief detective on the case, you bring them in for questioning. Each one tells the truth except for the culprit, who may be lying. Here is what they told you:

• Alice says that she is innocent. She says that Barney and Victor were friends, and Caddy and Victor were not friends.

• Barney says that he is innocent, plus that he and Victor were not friends.

• Caddy says that she is innocent, and that Barney and Victor were friends. As an astute detective you make the following assumptions about the world: CS 540

Spring 2019

• Friends don’t murder each other.

• There is no more than one murderer.

• If a person isn’t a murderer, they don’t lie. Now you want to ﬁnd the suspect.

(1) (1 point) Write a set of FOL sentences representing the information learned when interviewing the three suspects.

(2) (1 point) Write a set of FOL sentences representing the general knowledge assumptions you’ve made.

(3) (2 point) Convert all of your sentences in (1) and (2) to CNF.

(4) (1 point) State the goal to be solved as an FOL sentence.

(5) (1 point) Caddy later tells you that she was a friend of Victor. Write an FOL sentence that represents this new piece of information.

(6) (2 point) Is the knowledge base containing all of the sentences satisﬁable? If so, give an interpretation that makes it true. If not, prove unsatisﬁability using resolution.

(1) (5 points) Use forward chaining to solve the following problem:

A B C A∧B ⇒D B∧D ⇒F F ⇒G A∧E ⇒H A ∧ C ⇒ E Is H true? Draw a tree to illustrate the search for a proof.

(2) (5 points) Use backward chaining on the following KB to prove Q:

P ⇒Q E⇒B R⇒Q M ∧N ⇒Q A∧B ⇒P A⇒M C⇒M D⇒N D A Draw a tree to illustrate the search for a proof. Mark the nodes that are satisﬁed in this KB. What is the proof of Q? (Please show the steps) CS 540

Consider the following information about distances in miles between pairs of 10 U.S. cities:

The coordinates (latitude, longitude) of these cities are:

BOS (42.4, 71.1), NY (41.7, 74.0), DC (38.9, 77.0), MIA (25.8, 80.2), SLC (40.8, 111.9), SEA (47.6, 122.3), SF (37.8, 122.4), LA (34.1, 118.2), DEN (39.7, 105.0), ATL (33.7, 84.3).

Please directly use the Euclidean distance when solving (1) and (2).

(1) (10 points) Perform hierarchical clustering using single-linkage and the above data.

Spring 2019

(a) Show the resulting dendrogram.

(b) What clusters of cities are created if you want 3 clusters?

(2) (10 points) Show the results of one iteration of k-means clustering assuming k = 2 and the initial cluster centers are deﬁned as c1 = (50, 90) and c2 = (30, 100)

(a) Give the list of cities in the initial 2 clusters.

(b) Give the coordinates of the new cluster centers.

(c) Give the list of cities in the 2 clusters based on the new cluster centers computed in the (b).