CS522 -- Spring 2006

Assignment 1

Due: 11:00 am, Tuesday 24 January 2006

The aim of the assignments in this course get beyond what you were taught in class. Feel free to post any questions to the course newsgroup: ubc.courses.cpsc.522

Question 1

Suppose we want to diagnose school student's addition of multi-digit binary numbers. Suppose we are only considering subtracting a two-digit number from a three digit number.

That is, problems of the form:

X2 X1 X0
- Y1 Y0
Z2 Z1 Z0
Here Xi, Yi and Zi are all binary digits.

In this question you will represent this problem as a belief network, and test it with a belief network implementation.

  1. Describe how to do multi-digit binary subtraction. [This procedure that you are assuming students are carrying out will affect the network produced.] What errors would you expect students to make?
  2. What variables are needed to model subtraction of this form and the errors students could make? Give a DAG that specifies the dependence of these variables.
  3. What are reasonable conditional probabilities for this domain?
  4. Implement this, for example using the belief network tool at:
    http://www.cs.ubc.ca/labs/lci/CIspace/.
    Test the implementation (don't forget to save your graph).
  5. Explain how to extend your graph to allow for two different subtraction problems to help us better test the student. [Hint: What nodes should be shared and what should be replicated?]
  6. What would happen if there were two distinct methods that students used to solve such subtraction problems and we are not certain which method a student will use? Explain how your network could handle this. It is up to you whether you implement this, but it's probably instructive to do so.

Question 2

In this question we will explore ideas to extend the idea of belief networks. Be brief.
  1. What happens if we allow for a different base (say base 10 instead of base 2)? What is the size of the resulting tables? Suggest what could be done to make this more manageable.
  2. What if we were to allow for an arbitrary number of digits for each subtraction and an arbitrary number of different subtraction problems to test the student? Suggest what facilities you would like to be able to handle this.
  3. Suppose we wanted to model teaching the student something. How could we model this? [Hint: think about teaching as a node that specifies what is taught and have separate variables representing before and after teaching.]

Question 3

For each question in this assignment, say how long you spent on it. Was this reasonable? What did you learn?
David Poole