## Artificial Intelligence: Problem Set 4

Assigned: Mar. 7
Due: Mar. 28

### Problem 1

Given that P(A) = a, P(B) = b P(X|A) = c, P(X|B) = d, where a+b > 1. Show that P(X|A,B) is at most min(ca,db)/(a+b-1). (E.g. if a=b=0.9 and c=d=0.1, then P(X|A,B) is at most 0.09/0.8 = 0.125.)

### Problem 2

We wish to build a program that recommends movie choices to users. We decide to use a Bayesian network that uses features of the movies and of the users. (Note: This is not how such programs are actually constructed. We will discuss more realistic models later in the semester.)

A small portion of this network might involve the following random variables:

S --- sex of user. Values: { male, female }
A --- age of user. Values: { child, adult }
F --- Does the user generally like science fiction (as determined by a questionaire)?
C --- Does the user generally like children's movies?
I --- Did the user enjoy Independence Day?
E --- Did the user enjoy E.T.?
L --- Did the user enjoy Stuart Little?

Random variables F,C,I,E,L, have values True and False. The Bayesian network for these variables is shown below.

```        A       S
|       |
|       |
|       |
V       V
C       F
/ \     / \
/   \   /   \
/     \ /     \
L       E       I
```
The following probability tables apply: (Needless to say, these numbers are all invented.)
```P(S=male) = 0.5                    P(S=female) = 0.5
P(A=child) = 0.3                   P(A=adult)  = 0.7
P(F=true | S=male) = 0.6           P(F=false | S=male) = 0.4
P(F=true | S=female) = 0.3         P(F=false | S=female) = 0.7
P(C=true | A=child) = 0.9          P(C=false | A=child) = 0.1
P(I=true | F=true) = 0.8           P(I=false | F=true) = 0.2
P(I=true | F=false) = 0.4          P(I=false | F=false) = 0.6
P(L=true | C=true) = 0.9           P(L=false | C=true) = 0.1
P(L=true | C=false) = 0.1          P(L=false | C=false) = 0.9
P(E=true | C=true,F=true) = 1.0    P(E=false | C=true, F=true) = 0.0
P(E=true | C=false,F=true) = 0.6   P(E=false | C=true, F=true) = 0.4
P(E=true | C=true,F=false) = 0.8   P(E=false | C=true, F=false) = 0.2
P(E=true | C=false,F=false) = 0.5  P(E=false | C=false, F=false) = 0.5
```
A. Which of the following are true:
• i. F and C are independent absolutely.
• ii. F and C are conditionally independent given E.
• iii. E and I are independent absolutely.
• iv. E and I are conditionally independent given F.
• v. A and L are independent absolutely
• vi. A and L are conditionally independent given C.
B. Evaluate the following:
• i. P(F = true).
• ii. P(L=true | A=child)
• iii. P(S=male | I=true)
• iii. P(I=true | E=true)
• iv. P(E=true | I=true,L=true)

### Problem 3

(Discussion) Suppose, which is probably true, that you could set up a web site to run this program and collect statistical data on users, and that users were generous about filling out questionaire with a few personal questions and extensive questions about movie preferences, both individual and category. How would you go about selecting the random variables and constructing the Bayesian network? How could you use the incoming data to improve the structure of the Bayesian network, either manually or automatically?