Simon Fraser University


Spring Semester 2004


Oliver Schulte


Course Projects for CMPT 882, Machine Learning


Below I list a number of suggestions for course project. You are free to propose your own, but you should clear it with me. Once you have some idea of what you want your project to be, you should come see (preferably during office hours) so I can give you more guidance. My general expectation is that the project should take you 20-25 hours.


Programming Projects


1.     Learning conjunctive causes. In some learning problems, we may assume that there is a set of conditions that (deterministically) causes an effect, but we don’t know which set it exactly is. For example, Maria may get sick after eating a certain combination of foods, but she doesn’t know which – is it the Chinese with the Salad, or the orange juice with the bread? A powerful algorithm for learning the cause was developed in the 19th century by John Stuart Mill, known as “Mill’s methods”. Mill’s methods were reinvented in the 20th century by Patrick Winston in his “arch learner” program. The project is to implement Mill’s methods and run them on a reasonably large data set to test the result.

2.     Jasmina Arifovic from our economics department has a “Turing tournament” for algorithms that learn from repeated interactions, and that learn to distinguish computer players from human players. $10,000 U.S. prize money for the winner. Basically, the tournament goes like this: We fix a certain kind of game (in the sense of game theory). We have people and computers playing together – the computers are called emulators and they try to look as much as possible as people. We have other computers – the “sniffers” that observe the tournament and try to tell which participants are emulators and which are people. The winner is the best emulator or the best sniffer. More details are in this postscript file. The project is to write an emulator or a sniffer.

3.     Some machine learning tools could be enhanced with more features. This would be a service to the community as well. For example, the ANL learner could be enhanced with so-called “boosting” or “bagging” techniques which are widely used for learners in general. The project would be to add an improvement to some existing but not completely mature technology.

4.     The Tetrad program from Carnegie Mellon is an implementation of causal inference procedures using Bayes Nets, close to Pearle’s theory. How does Tetrad do as a concept learner, say compared with decision trees?

5.     An important concept learning problem in genomics is to distinguish “active” gene sites from “noise”. How do the concept learners we’ve looked at do in this problem? How does Tetrad do?

6.     Reinforcement learning methods are based on various probability estimates. A promising idea is that this probabilistic knowledge could be represented by a Bayes net. Then reinforcement learning could be based on inference methods for Bayes net learning. The project is to take a typical reinforcement learning problem (e.g., “grid world”), represent its features (states) in a Bayes net, see how the Bayes net can learn the relevant probabilities, and translate those probabilities into actions. (The last part may be optional if the other parts are difficult enough.)

7.     Try to build a reinforcement learner for some problem of interest to you. How about a reinforcement learner for “mine sweeper”, along the lines of the TD backgammon program? Along the lines of problem 4, you could try using a Bayes Net for this purpose.



Further Research


  1. There are a number of suggestions for using Bayes Nets to represent knowledge in a planning problem. Boutilier et al. have a recent survey article about this topic. The project would be to read the article, summarize the main points, and a) discuss the main points, and/or b) look up further readings (e.g., on state abstraction or planning). If you have ideas for a new approach coming out of this reading, you can consider implementing them or developing them theoretically.
  2. Similar projects can be done for other topics in this course, e.g. neural nets or decision trees. I’m particularly interested in Bayes nets and reinforcement learning. For example, you could look at Pearle’s theory of interventions in a Bayes Net, read some more literature on it and see how this might relate to reinforcement learning.


Problems and Exercises


You could work out a number of exercises (let’s say around 30) to get some in-depth familiarity with the theory/mathematics of learning theory in general or a particular aspect of our course.