::= "-"+ "|" "-"+
::= ( )+
::= (" " )* " | "
::= "t" | "f"
::= "0" | "0"? "." +
::= "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
::=
"A"|"B"|"C"|"D"|"E"|"F"|"G"|"H"|"I"|"J"|"K"|"L"|"M"|"N"
| "O"|"P"|"Q"|"R"|"S"|"T"|"U"|"V"|"W"|"X"|"Y"|"Z"
::= "\n"
Implementing the Variable Enumeration Algorithm
The variables should be visited in this order:
1. Parents should be visited before their children.
2. To choose between two nodes whose parents have all been visited, choose alphabetically.
At the end of your implementation of the ENUMERATE-ALL function, you should print the following:
- the variables passed in to ENUMERATE-ALL;
- the assignment passed in to ENUMERATE-ALL;
- the return value for ENUMERATE-ALL.
Below is the output you should get when running the program on the "alarm" example using variable enumeration and the query "P(B|J=t,M=t)".
M | A=t B=f E=t J=t M=t = 0.70000000
J M | A=t B=f E=t J=t M=t = 0.63000000
M | A=f B=f E=t J=t M=t = 0.01000000
J M | A=f B=f E=t J=t M=t = 0.00050000
A J M | B=f E=t J=t M=t = 0.18305500
M | A=t B=f E=f J=t M=t = 0.70000000
J M | A=t B=f E=f J=t M=t = 0.63000000
M | A=f B=f E=f J=t M=t = 0.01000000
J M | A=f B=f E=f J=t M=t = 0.00050000
A J M | B=f E=f J=t M=t = 0.00112950
E A J M | B=f J=t M=t = 0.00149335
B E A J M | B=f J=t M=t = 0.00149186
M | A=t B=t E=t J=t M=t = 0.70000000
J M | A=t B=t E=t J=t M=t = 0.63000000
M | A=f B=t E=t J=t M=t = 0.01000000
J M | A=f B=t E=t J=t M=t = 0.00050000
A J M | B=t E=t J=t M=t = 0.59852500
M | A=t B=t E=f J=t M=t = 0.70000000
J M | A=t B=t E=f J=t M=t = 0.63000000
M | A=f B=t E=f J=t M=t = 0.01000000
J M | A=f B=t E=f J=t M=t = 0.00050000
A J M | B=t E=f J=t M=t = 0.59223000
E A J M | B=t J=t M=t = 0.59224259
B E A J M | B=t J=t M=t = 0.00059224
RESULT:
P(B = f | J = t, M = t) = 0.7158281646356071
P(B = t | J = t, M = t) = 0.2841718353643929
Implementing the Variable Elimination Algorithm
Variables are visited according to a greedy heuristic: eliminate whichever variable minimizes the size of the next factor to be constructed. Ties are broken alphabetically. Importantly, a variable cannot be eliminated if all the factors that depend on that variable have not been created yet.
Print out when a variable is being eliminated. At the end of the main loop for ELIMINATION-ASK, print the factors that are active. These can be printed one line per element with the corresponding assignment and element value.
Below is the output you should get when running the program on the "alarm" example using variable elimination and the query "P (B|J=t,M=t)".
----- Variable: J -----
Factors:
B=f E=f: 0.0011295
B=t E=f: 0.5922299999999999
B=f E=t: 0.183055
B=t E=t: 0.598525
B=f E=f: 0.0011295
B=t E=f: 0.5922299999999999
B=f E=t: 0.183055
B=t E=t: 0.598525
A=f: 0.05
A=t: 0.9
----- Variable: M -----
Factors:
A=f: 0.05
A=t: 0.9
A=f: 0.01
A=t: 0.7
----- Variable: A -----
Factors:
----- Variable: B -----
Factors:
B=f: 0.999
B=t: 0.0010
----- Variable: E -----
Factors:
B=f: 0.999
B=t: 0.0010
B=f: 0.0014933510000000002
B=t: 0.5922425899999999
RESULT:
P(B = f | J = t, M = t) = 0.7158281646356071
P(B = t | J = t, M = t) = 0.2841718353643929
Posted Date: 3/5/2013 6:31:41 AM | Location : United States