Simon Fraser University

 

Spring Semester 2002

 

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” 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.

8.     Donald Nute’s V-world is a software package for building artificial agents in a “virtual” world. It’s easy to use and cute to look at. How about enhancing the V-world with agents that learn to adapt to their environment, for example learning to navigate mazes or find food? Reinforcement learning is the obvious approach here.

 

Open Mathematical/Theoretical Questions

 

  1. There are open questions about mistake-bounded function learning and PAC learning. For example, if there is a mistake-bounded PAC learner for a learning problem, is there then a mistake-bounded function learner? And vice versa? Are function learners that minimize the number of mistakes automatically PAC learners?
  2. What is mistake-bounded learning like with positive examples only (e.g., language learning)? How does PAC learning with positive examples only relate to mistake-bounded function learning (similar questions as above). Note: this project would require some more extra reading on learning from positive examples only.
  3. How can we design our learning techniques so that they minimize mistakes? For example, what kind of decision tree learner minimizes mistakes? Neural nets, or Bayesian causal graphs? The theoretical analysis could be combined with an implementation.
  4. An important concept learning problem in genomics is to distinguish “active” gene sites from “noise”. Perform a learning-theoretic analysis to estimate the difficulty of this problem. Are there plausible assumptions that make the problem easier, and what algorithms can exploit these assumptions?
  5. Compare the Find-S algorithm from the text (rule out as many negative examples as possible) with Winston’s arch learner and/or Mill’s methods (see above). Are Winston/Mill implementations of Find-S?

 

 

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.