Note: For several of these problems, the answer below is one of several correct possibilities.
Consider the following problem: Given a graph G and a number K, find a vertex cover for G of size at most K.
A. Describe a systematic (tree-like) search space for solving the vertex cover problem
A state is a set of vertices of size at most K.
An operator on state S is to add to S a vertex in V that is alphabetically later than any of the vertices in S, and that covers at least one edge not covered by S.
The start state is the empty set of vertices.
The goal state is a set of vertices that covers all the edges in G.
B. What is the branching factor in your state space? What is the depth of the space? Give your answer in terms of G and K in general, not for the particular example in (B)
Answer: The branching factor is |V|, the number of vertices in G. The depth is K.
C. Give an example where a goal state is much shallower than the maximum depth of the space, or give an argument that no such example exists.
Answer: A "star"-graph where the edge all connnect a center vertex to the other vertices in t graph.
There are two types of propositional atoms.
A. Give one example of each of these categories that would be generated in compiling the example from problem 1.
Answer: W. A_in_S => A_1 V A_2 V A_3. X. B_2 => A_1. Y. ~(A_1 ^ B_1). Z. A_in_S V B_in_S.
B. Argue that the category (Y) is necessary by describing a variable assignment that satisfies all the constraints in categories (W), (X), and (Z) but is not a solution to the problem.
Answer The solution where all the atoms except A_2 and A_3 are assigned the value TRUE.
1. P => (Q <=> R).
2. Q <=> ~(R^W)
3. Q => (P^W).
A. Convert this set to CNF. (You need not show the intermediate steps.)
1A. ~P V ~Q V R.
1B. ~P V Q V ~R.
2A. ~Q V ~R V ~W.
2B. Q V R
2C. Q V W.
3A. ~Q V P
3B. ~Q V W.
B. Show how the Davis-Putnam assignment finds a satisfying assumption. (Assume that, when a branch point is reached, the algorithm chooses the first atom alphabetically and tries TRUE before FALSE.)
Let S0 be the above set of clauses. Try P=TRUE. Delete ~P from 1A and 1B. Delete 3A. S1: 1A. ~Q V R.
1B. Q V ~R.
2A. ~Q V ~R V ~W.
2B. Q V R 2C. Q V W. 3B. ~Q V W. Try Q=TRUE. Delete ~Q from 1A, 2A, 3B. Delete 1B, 2B, 2C. 1A. R.
2A. ~R V ~W.
3B. W. 1A is a singleton clause. Set R=TRUE. Delete ~R from 2A. Delete 1A. 2A. ~W.
3B. W. 2A is a singleton clause. Set W=FALSE. Delete W from 3B. Delete 2A. 3B is now the null clause. Fail. Return to S1, Try Q=FALSE. Delete Q from 1B,2B,2C. Delete 1A, 2A, 3B. 1B. ~R.
2B. R 2C. W. Set R=FALSE. Delete R from 2B. Delete 1B. 2B is now the null clause. Fail. Return to S0. Set P=FALSE. Delete P from 3A, delete 1A, 1B. 2A. ~Q V ~R V ~W.
2B. Q V R 2C. Q V W. 3A. ~Q. 3B. ~Q V W. 3A is a singleton clause. Set Q=FALSE. Delete Q from 2B, 2C, delete 2A, 3C, 3B. 2B. R 2C. W 2B and 2C are singleton clauses. Set R=TRUE, W=TRUE. Succeed. Answer: P=FALSE, Q=FALSE, R=TRUE, W=TRUE.
s(X) --- X is satisfied with life.
d(X) --- X is a doctor.
h(X) --- X is a heart surgeon.
c(X,Y) --- X is a child of Y.
f --- Fred.
A. Express the following statements in L.
W. A person is satisfied with life if all his/her children are doctors.
forall(A) [forall(B) c(B,A) => d(B)] => s(A).
X. All of Fred's children are heart surgeons.
forall(X) c(X,f) => h(X).
Y. Heart surgeons are doctors.
forall(X) h(X) => d(X).
Z. Fred is satisfied with life.
B. Give a resolution proof of Z from W,X,Y. You need not show the intermediate stages of conversion to CNF. Your proof must be a resolution proof; no credit will be given for any other kind of proof. Your proof must show all the resolutions involved in the proof.
Converting W, X, Y, and the negation of Z to CNF gives five clauses:
W1. c(sk0(A),A) V s(A).
W2. ~d(sk0(A)) V s(A).
X. ~c(X,f) V h(X).
Y. ~h(X) V d(X).
Z. ~s(f). Resolving Z with W1 gives A. c(sk0(f),f).
Resolving A with X gives B. h(sk0(f)). Resolving B with Y gives C. d(sk0(f)). Resolving Y with W2 gives D. s(f). Resolving D with Z gives the empty clause.
C. Is this a Horn theory? Explain your answer.
Answer: No. W1 has two positive literals and is thus not a Horn clause.
This takes many different forms. In this problem, we will consider how different characterizations of the classification attribute affect the prediction. Suppose, for instance, that you are trying to guess in what month and year a given event occured, based on other information. One way is to view this as two classification attributes, "Month" and "Year" and apply classification techniques to these separately. Another way is to view it as a single attribute "Month-Year" and apply a classification technique to that single attribute.
Suppose that the predictive attributes are A and B, and that the ML technique being used is 1R. Construct a data set in which applying the 1R technique to "Month" and "Year" separately gives rules that predicts "Month=January" and "Year=2000" for the instance A=T,B=T, but applying the 1R technique to "Month-Year" gives the prediction "Month-Year=February-2002" for the same instance.