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

Assignment Help:

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

 


Related Discussions:- Program that implements inference given a bayesian network

Flowcharting., flowcharting of 3 quizes display the average

flowcharting of 3 quizes display the average

How can define an array, Q: How can Define an Array? An Array is define...

Q: How can Define an Array? An Array is defined in much the alike manner as ordinary variables except that every array name must be accompanied by a size specification (that is

Guidelines or "rules of thumb" for overloading operators?, What are some gu...

What are some guidelines / "rules of thumb" for overloading operators? A: Here are a few guidelines / rules of thumb .Use common sense. If your overloaded operator makes life si

About, How can I learn all programming languages.?

How can I learn all programming languages.?

Computer Science 101, This is what I need help with. "Create a program cre...

This is what I need help with. "Create a program creates an interface allowing the user to select from some other programs I have made one being a money converter and the other ca

Arrays within a class, A r r a y s w i t h i n a c l a s s:...

A r r a y s w i t h i n a c l a s s: I t i s j u s t d ecl a r i n g o r c on s t ru c ti n g a d e r i v e d t

Describe, A: Use operator overloading to present a friend right-shift opera...

A: Use operator overloading to present a friend right-shift operator, operator>>. It is similar to the output operator, except the parameter doesn't contain a const: "Fred&" instea

Strings, write a c program to find input string using strlen(), strcpy(), s...

write a c program to find input string using strlen(), strcpy(), strcat(),strncat(), strcmp().

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd