Program that implements inference given a bayesian network, C/C++ Programming

In this problem, you will write a program that implements two algorithms for performing exact inference given a Bayesian network, namely, enumeration and variable elimination. Your program should accept exactly three command-line arguments:

BayesNet

The first argument is a file specifying a Bayesian network (see the section "Specifying a Bayesian Network" below for the file format for a Bayes net). The second argument is either elim or enum, which indicates whether enumeration or variable elimination should be used as the underlying inference mechanism. The third argument is a query. The query should be formu- lated as a probability, such as "P(C|A=f,E=t)". This query would return the two probabilities for C given that A is false, and E is true. Do not include spaces in the query, and you should put the query in quotes. Given these three inputs, one of the things your program should print to stdout the result of the inference. Specifically, the result should be output by printing the conditional probabilities of the query variable given the observed variables, such as:

P(C = f | A = f, E = t) = #

P(C = t | A = f, E = t) = #

for both values of the query variable and the values for the observed variables.

In addition to outputting the result of the inference, your program also needs to output other information it computes during the inference process so that we can track the correctness of your implementation. The sections "Implementing the Variable Enumeration Algorithm" and "Implementing the Variable Elimination Algorithm" provide details on what to print during inference.

To simplify your implementation, your program only needs to handle queries with one query variable. Nevertheless, your program should work even if no observed variables are given. In other words, your program should accept a query containing an unconditional probability of a variable.

Specifying a Bayesian Network

Let us try to understand the file format for a Bayes net via the "alarm" example we saw in class. Recall that in the "alarm" Bayes net, there are five nodes, B, E, A, J, and M, each of which is associated with a conditional probability table. The file for this Bayes net would look like this:

P(B) = .001

P(E) = .002

B E | A

----|-----

t t | .95

t f | .94

f t | .29

f f | .001

A | J

--|-----

t | 0.90

f | 0.05

A | M

--|-----

t | 0.7

f | 0.01

Specifically, each node is sectioned off from the others using double newlines, and there are two types of nodes: nodes without parents and nodes with parents. The nodes without parents are just represented as P(X) = #. The nodes with parents are represented as a table. The first line for the node is a table header which lists the parent nodes separated by spaces, followed by a pipe symbol and finally the name of that node. The next line can be skipped. There are then 2(#parents) lines representing table entries. A table entry is a list of p 't' or 'f' symbols (where p = #parents), separated by spaces, followed by a pipe symbol and finally a decimal number between 0 and 1. The entry can be interpreted as the probability of the node being true given the truth values for its parents. Truth value i corresponds to parent i from the table header.

If you understand BNF notation, below is the specification of a Bayes net in BNF (with extensions):

::= ( )*

::= |

::= "P(" ") = "

::=

::= (" " )* " | "

::= "-"+ "|" "-"+

::= ( )+

::= (" " )* " | "

::= "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







Related Discussions:- Program that implements inference given a bayesian network, Assignment Help, Ask Question on Program that implements inference given a bayesian network, Get Answer, Expert's Help, Program that implements inference given a bayesian network Discussions

Write discussion on Program that implements inference given a bayesian network
Your posts are moderated
Related Questions
how to find minimum number if shelves required

programing code on board coloring in clanguage

The Main program is slightly more complicated and you need to think about the I/O process. First of all, for most applications you do not call the low level routines GetChar and P

find area under the curve y=f(x) between x=a &y=b integrate y=f(x)


how to create program in c that will system restart

Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two points can b

Recursive Functions Recursion is a process by which a function includes itself with a condition for its safe exit. It is best suitable for a recursive problem. A typical exampl

what is local and global variable?give me some example to understand better

c | c-c-c-c-c | c-c-C-c-c | c find distance between difftent carbon atom by programing