EECS 391/491: EXTRA PROBLEMS FAQ
Here are some notes on the arrowed problems we did not get to during lecture:

CMU 15-381 Spring 05 Final

Problem 1

(a) min{1, 2} = 1
(b) (1/2)(1) + (1/2)(3) = 2
(c) (3/4)(2) + (1/4)(2) = 7/4
(d) min{2, 7/4} = 2

Problem 3

  1. (a) H(1+,3-) = -(1/4) log2(1/4) - (3/4) log2(3/4) =  0.8113
(b) H(4+,0-) = 0
(c) H(1+,1-) = 1 [This is the highest entropy can be]
(d) H(1-,2+) = .9183

Problem 4

(a) 
The equations come directly from the Naive Bayes net structure;
probabilities come from the empirical conditional probability tables
(which come from just counting using the data in the table):

P(W=G|H=0)P(S=P|H=0)P(H=0) = (3/5)(1/5)(5/8) = 3/40
P(W=G|H=1)P(S=P|H=1)P(H=1) = (1/3)(3/3)(3/8) = 1/8 = 5/40
(e) 
The equations come directly from MAP over the two
hypotheses (H=0 vs. H=1) using Bayes' Rule.  The
probabilities are determined emprically from the
table (by simple counting):

P(W=G, S=P, N=O |H=0)P(H=0) = (0/5)(5/8) = 0
P(W=G, S=P, N=O |H=1)P(H=1) = (1/3)(3/8) = 1/8

Problem 7

  1. Recall the nodes are independent of non-descendents given their parents

  2. P(C) = P(C|E)P(E) + P(C|not E)P(not E)
     = (0.3)(0.5) + (0.8)(0.5)
     = 0.15 + 0.40
     = 0.55
  3. Sum over values of variable C: 
    P(B|A) = P(B|A,C)P(C) + P(B|A, not C)P(not C)
       = (0.6)(0.55) + (0.1)(0.45)
       = 0.33 + 0.045
       = 0.375

Problem 8

  1. There are two choices of action at each of the three states.
  2. For sub-part 1: 
    Uπ0(S1) = 10 + γ 10 + γ2 10 + γ3 10 + ...
       = 10 (1 + γ + γ2 + γ3 + ... )
       = 10 ( Σi=0 to +inf γi )
       = 10 1/(1-γ)
       = 10 1/(1-0.9)
       = 10 1/(0.1)
       = 100
  3. The updated policy is to choose the action in each state that maximizes the payoffs as computed in part (a).
  4. Note that the problem says 
    U1(S1) = R(1) = 10
U1(S2) = R(2) = -10
U1(S3) = R(3) = 20

Now, doing just sub-part 1, we obtain

U2(S1) = R(S1) + γ maxi=1,2 { U(s'(S1, ai) }
       = 10 + (0.9) maxi=1,2 { U1(S1>), U(S2>) } 
       = 10 + (0.9) maxi=1,2 { U1(S1>), U1(S2>) } 
       = 10 + (0.9) maxi=1,2 { 10, -10 } 
       = 10 + (0.9) { 10 } 
       = 10 + 9 
       = 19

Problem 9

The answers given are pretty clear: linear function without threshold gives a line through the origin; if a threshold is used, an arbitrary line results from a single Linear Threshold Unit. Hence, the importance of whether the data is "linearly separable" or not.

Problem 10

In part (b), the transition probabilities are determined empirically from the recorded trials (in a fashion similar to that you used to estimate the Markov chain for your friend's heads or tails picks way back on PS#1). 

There are seven transitions in the trials: AAAB, AAB, AB, AB

AA appears 3 times --> 3/7
AB appears 4 times --> 4/7
Author: Michael S. Branicky. Created: 2005-04-30. Modified: 2008-04-27.