CS 3600, Introduction to Intelligent Systems Project #5

CS 3600
Introduction to Intelligent Systems
Project #5
Supervised Learnings

Numbers

Due: December 9 at 11:59 PM
Please submit your code via WebWork (click here for directions). For questions about the assignment contact Ryan Riegel.

The assignment is worth 7% of your final grade.

Why?

This project is intended to familiarize you with standard approaches to classification problems. You will code three relatively simple, though powerful, classification algorithms and create a classification problem to test them out. The hope is that, as you work on this project, you will come to understand the powers and limitations of various algorithms.

This project is to be completed in LISP and will be graded using alisp on helsinki; please make sure that your code is functional using the (load "filename.lisp") command.

Part I: Classification Problem (10%)

A classification problem consists of four variables:

*training-examples* - an ordered list of training examples, where each example is an n-dimensional vector (i.e., use make-array or vector to create these; alternately, see how it's done in utils5.lisp).
*training-classes* - a corresponding ordered list of classification labels, where each label is t (in the class) or nil (not in the class).
*test-examples* - similar to *training-examples* in form, but used strictly for testing purposes.
*test-classes* - similar to *training-classes* in form, but used to evaluate the results of running the algorithm on *test-examples*.

Note: To make things really simple, let's assume that every element in your n-dimensional example vectors can only take on one of two values: 0 and 1 (e.g., all attributes are boolean). It is possible to represent a multi-valued attribute as a collection of boolean attributes as follows: Restaurant = {Thai, Burger, Italian, French} becomes Thai?, Burger?, Italian?, French?. Only one of these attributes should be set to 1 at a time, but you can enforce that by hand in your examples; your algorithms should not need to change in the slightest.

Be creative in coming up with your classification problem, but remember to indicate (in comments) the names of the attributes as well as the class you are trying to distinquish.

Part II: Classification Algorithms (75%)

You must implement:

knn - k-Nearest Neighbors
dt - Decision Trees
ds - Decision Stumps (used by AdaBoost)
ab - AdaBoost using Decision Stumps

Each of the above is described in detail in Russell/Norvig.

The signatures of your implementations should be as follows:

  (defun knn (examples classes k) ...)
  (defun dt (examples classes) ...)
  (defun ds (examples classes weights) ...)
  (defun ab (examples classes learning-function M) ...)

weights is a list of weight values for each example; learning-function is a function with the same signature of ds. Each implementation should return a function that, when used via funcall on an example (just one vector, not a list), returns a classification label (t or nil).

Part III: Analysis (15%)

In a separate, plain-text file, briefly describe the nature of the classification problem you created for Part I and explain why you feel the problem is important. Also include:

The error rates you obtained running each of the four algorithms on the problem.
Why you got the results you did for each of the algoirthms.
What changes you might make to each algorithm to improve its performance.

Feel free to submit supporting graphs and tables as well, but label them meaningfully and reference them appropriately in your text explanation.

Some handy analysis functions (and a sample classification problem) can be found in utils5.lisp. Also, the way classes were decided for the sample classification problem is given in utils5-gen.lisp.