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
d) a "static destructor" is a static member function of the class which accepts one argument - a pointer to the object of that class to be cracked. It is probably utilized along wi

What are pre-processor directives? - Pre-processor directives are placed at the beginning of a C program. They begin with # symbol. - This is the place, where library files

convert lower case to uper case

B a s i c D a t a t y p e : T h e r e a r e t h r e e t y p e o f d a t a t y p e i n C+ + 1.       P r

Program: Write a program that predicts users' age (0-128 years old) with at most 7 questions. The game starts with asking the user whether he/she is younger or older than G (an

Incomplete types refer to pointers in which there is no availability of the execution of the referenced location or it points to some location whose value is not available for modi


Project Description: I play this game called mobstar (mobstar) and I would like the program to grade my account for me. It would require doing a crime, GTA, jail busting, lead a

write a C program for padovan string for a natural number   program 1 : package test.padovanstring; public class PadovanString {     public int stringOccurrences(int n,

Develop a Student class that has the following header file: #ifndef STUDENT_H #define STUDENT_H #include #include #include using namespace std; class Stu