CS264A: Automated Reasoning
Homework 4
Due Date: Sunday, December 10
1. (25pt) Consider a linear classifier f(X,Y,Z) = −6·X +5·Y −4·Z +3, where X,Y,Z are binary features (each takes values in {0,1}). The classifier labels an instance positively iff f(X,Y,Z) ≥ 0. For example, since f(1,1,1) = −2 < 0, the instance X = 1,Y = 1,Z = 1 is labeled negatively.
(a) (7pts) What is the classification function given X = 1, Y = 1? In general, what is the form of the classification function after we know the values of features X, Y ?
(b) (15pts) Draw a reduced OBDD representing the decision function of the classifier, using variable order X, Y, Z.
(c) (3pts) If an instance has X = 0 and Y = 1, will the value of feature Z affect the instance classification?
2. (22pt) Consider the Bayesian network in Figure 1 and suppose we want to compute the most probable explanation (MPE) for this network.
(a) (12pt) Show the weighted CNF which can be used to compute MPE using weighted MaxSAT.
(b) (3pt) Modify this weighted CNF so it can be used to compute MPE under evidence B = b0.
(c) (7pt) What is the MPE instantiation under B = b0, what is the corresponding in- stantiation of indicator variables, and what is the weight and penalty of this indicator instantiation?
3. (14pt) Consider the following DNF:
∆ = w ̄x ̄y ̄z ̄ + w ̄x ̄y ̄z + w ̄x ̄yz ̄ + wx ̄y ̄z ̄ + wx ̄yz ̄ + wx ̄yz + wxyz ̄ + wxyz.
(a) (9pt) Compute the prime implicants of ∆ using the consensus method. That is, close the DNF under consensus and remove subsumed terms.
A B θB|A A C θC|A
AθA a0b0 a00.8a0b1 a10.2a1b0
0.3 a0 c0 0.1 0.7 a0 c1 0.9 0.7 a1 c0 0.9 0.3 a1 c1 0.1
Figure 1: Bayesian network.
程序代写 CS代考 加微信: cstutorcs
(b) (5pt) Suppose ∆ is a classifier. What are the sufficient reasons for the instance wxyz? 4. (20pt) Consider the following classifier and suppose that R is a protected feature.
∆=[E∧[(F ∧(G∨W))∨(¬F ∧R)]]∨[G∧R∧W]. (a) (5pt) What is the decision (yes, no) on instance E, ¬F, G, W, R?
(b) (10pt) Which of the following are sufficient reasons (PI-explanations) for this decision? (E,G,R), (E,W), (E,G,R,¬F), (E,G,W).
(c) (5pt) Is this decision biased? Why?
5. (10pt) Consider the following class formula ∆ = (x12 + y1) · (x1 + y1 + z1) + (x3 · y2 · z2) and the instance I = {x1, y1, z1}. Suppose X has states {x1, x2, x3}, Y has states {y1, y2, y3}, and Z has states {z1, z2}.
(a) (5pt) Compute the complete reason ∀I · ∆. (b) (5pt) Compute the general reason ∀I · ∆.
6. (9pt) True or False (no need to explain)?
(a) (3pt) We can compute marginals on an arithmetic circuit in linear time if it satisfies the decomposability property.
(b) (3pt) We can compute MPE on an arithmetic circuit in linear time if it satisfies the decomposability and smoothness properties.
(c) (3pt) A PSDD is an arithmetic circuit that satisfies the properties of decomposability and determinism.
程序代写 CS代考 加QQ: 749389476