CPSC 415 - Artificial Intelligence - Fall 2023

Program #6 — Probabilistic agents

Possible experience: up to +50XP (or even +65XP)

Due: Fri., Dec. 15th, midnight

Overview

In this assignment, you'll be writing a program that can compute exact and/or approximate probabilistic inference on an arbitrary Bayesian Belief Net.

Requirements

Create a single Python file called yourUmwId_bbn.py with the following command-line usage:

Usage: jsmith8_bbn.py bbnFile exact|approx query

The first required command-line argument will be the name of a BBN file describing the network (see below for formatting). The second required command-line argument will be either the word "exact" or the word "approx". The third required command-line argument should be a probabilistic query in the correct syntax (see below). Your program should print a helpful error message and exit if either (a) the bbnFile is not a valid file, or (b) the file exists but is not in the correct format, or (c) some word other than "exact" or "approx" is given for the second argument, or (d) the query is not in the right syntax or contains undefined variables. It should also exit with a helpful error message if the user omits any of the required arguments.

Note: for consistency with my grader, please do require and accept the exact or approx argument in the correct position, even if you only did exact mode or only did approximate mode.

The output of the program should be a single, un-rounded floating-point number (between 0 and 1) on a single line, giving the exact or approximate probability of the requested event.

Here are some examples of using the program correctly:

$ ./jsmith8_bbn.py snowy.bbn exact "snowy"
0.1
$ ./jsmith8_bbn.py snowy.bbn exact "~late"
0.89
$ ./jsmith8_bbn.py snowy.bbn exact "hotchoc|late"
0.490909090909090909
$ ./jsmith8_bbn.py snowy.bbn exact "~hotchoc|late^~snowy"
0.6

(Note that the query argument will probably need to be put in quotes when you run it, so that your shell doesn't interpret characters like "|" or "^" in an unfortunate way.)

When running in exact mode the answer must be exactly right to all available decimal places. When running in approximate mode the answer must only be in the ballpark of the correct answer (say, ±.01), but must complete and print its answer in one minute or less on Stephen's laptop.

File format

A valid .bbn file contains (possibly) multiple lines for each random variable, giving the conditional probabilities of all its values for each value of its parent(s). Here's the first example from class:

And here's the Terminator example from the class activity:

Note the following:

• Random variables have capital letters, while values are in lower-case. You may take advantage of this fact if you wish, but are not required to check it.
• All values in the file are guaranteed to be globally unique across all r.v.'s. In other words, if a variable T has a value foster, you are guaranteed that no other variable in the file will also have one named foster. You may take advantage of this but need not verify it.
• If a r.v. has no parents in the BBN, it is represented on a single line with its prior probabilities for each possible value.
• If a r.v. has one or more parents, it is represented on multiple lines as conditionals with each combination of parental values.
• Variables are of two types: binary and non-binary. Binary variables will have two values: the lower-case version of the r.v.'s name, and the same thing preceded by a "not" symbol ("~" in the file.) Non-binary variables will have differently-named values, with only letters.
• The network represented by the file is guaranteed to be a DAG; i.e., there is guaranteed to be at least one node with no parents, and the graph will have no cycles. As above, you do not need to check this.
• The probabilities for a row of the table are guaranteed to sum to 1, and you do not need to check for this.
• All conditional probabilities for a node are guaranteed to be present, and none others will be. For example, if there is a "WIN|practice:" line, there will also be a "WIN|~practice:" line as required, and there won't be multiple such lines, nor irrelevant lines like "WIN|liberalarts^mayonnaise."
• Finally, the order of the lines in the file is not guaranteed to be in any special order. The example above does begin with the only variable that has no parents, and proceeds one variable after another, in an order that you might actually calculate probabilities. But this is not guaranteed, and your program should work equally well (and give the same answers) with this file:

Query syntax

Queries can either be unconditional, like:

hotchoc^~snowy

or conditional, like:

~late^snowy|~hotchoc

The only logical operators you are required to support are "not" ("~"), "and" ("^"), and "given" ("|"). You do not need to support parentheses. (Note that "~" always has the highest precedence and "|" the lowest.)

Grading

Note that I will run your program not just on the Snowy and Terminator examples, but also on those of my own concoction. Points will be awarded as follows:

• If you get your program working in exact mode only, you can receive up to +50XP. (To get credit, your answers must be exactly right, but you don't have to handle larger BBN files.)
• If you get your program working in approximate mode only, your answers need only be close to correct, but they must handle large files with no trouble in less than a minute.) You can receive up to +50XP for a working approximate mode.
• If you get your program working in both exact mode and approximate mode, you can receive up to +60XP.

Turning it in

You will turn this assignment in by attaching your properly-named Python file (your UMW ID, followed by the string _bbn.py) to an email with subject line "CPSC 415 Program #6 turnin". In the body of the email, please specify whether your program works in (a) exact mode only, (b) approximate mode only, or (c) both modes. Please do not leave me to guess.

For up to an additional +5XP, also attach a complete and properly-formatted .bbn file characterizing a Bayes Net of your own invention. It should contain a minimum of five r.v.'s, at most two of which can have no parents and at least one of which must have two or more parents. Not all of the r.v.'s can be binary: at least one must have more than two possible values. The BBN should be about something real (i.e., like the Terminator example, not like a purely random example.) The body of your email should contain a brief description of the domain, what each r.v. and value means, and a couple of useful sample queries together with their answers and interpretations. Especially witty and clever BBNs may be awarded additional XP and/or shared with the class, at my discretion.

Getting help

Come to office hours, or send me email with subject line "CPSC 415 Program #6 help!!"