## 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(C=true | A=adult) = 0.2 P(C=false | A=adult) = 0.8
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?