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
A student apears in exam of math, physics, and chemistry. Write a program to find the total marks aa student has aqueired find the average.

(a) Write a recursive procedure (digits n) that computes the number of digits in the integer n using a linear recursive process. For example, (digits 42) should return 2 and (digit

Luminous Jewels - The Polishing Game Byteland county is very famous for luminous jewels. Luminous jewels are used in making beautiful necklaces. A necklace consists of various lum

# Dear I want help to programmer that write C++ code for my small project as soon as posible If we can help me?..

Objective of this Program: (a) To learn more about modularization of a program into independent modules, (b) To use arrays in a program, (c) To get some experience with us

We have used logic symbols in the past, but not really though about the actual real devices. Semiconductor companies have taken the logic symbols are manufactured them into logic f

Smugglers are becoming very smart day by day. Now they have developed a new technique of sending their messages from one smuggler to another. In their new technology, they are send

A PROGRAM TO CALCULATE AREA OF TRIANGLE

Need to Fix a code written in c++,SDL2.00 for high CPU and memory leak There is a 2D simple game written with SDL2.00 using c++. The game isn't complete and the code is a little

what is virtual datatype