MC3-Homework-1

Draft

The description for this assignment has not been created yet. Once it is finalized, this notice will be removed.

Overview

You will also write some code to generate your own datasets. That part of the project will test your understanding of the strengths and weaknesses of various learners.

Reference Material

Note: As of Sept 14, 2016, we are still adding to these materials.

The following materials are provided to give you information on what we want you to build:

• How to use a decision tree if you have one (Balch Youtube video)
• How to build a decision tree & Random Trees (Balch Youtube video) (not yet available)
• paper on Random Trees by Adele Cutler
• Balch slides on decision trees (not yet available)
• You may be interested to take a look at Andew Moore's slides on instance based learning.
• A definition of correlation which we'll use to assess the quality of the learning.
• Bootstrap Aggregating
• AdaBoost
• numpy corrcoef
• numpy argsort
• RMS error

You can use code like the below to instantiate several learners with the parameters listed in kwargs:

learners = []
kwargs = {"k":10}
for i in range(0,bags):
    learners.append(learner(**kwargs))

Template and Data

Note: As of Sept 14, 2016, the repo has not been updated to include the wine data. We will notify you when that is complete. In the mean time you can use the provided data sets.

Instructions:

• Update your copy of the class' github repo. We will send separate instructions by email on how to do that.

You will find these files in the mc3_p1 directory

• Data/: Contains data for you to test your learning code on.
• LinRegLearner.py: An implementation of the LinRegLearner class. You can use it as a template for implementing your learner classes.
• __init__.py: Tells Python that you can import classes while in this directory.
• testlearner.py: Helper code to test a learner class.

In the Data/ directory there are three files:

• 3_groups.csv
• ripple_.csv
• simple.csv
• red_wine.csv
• white_wine.csv

We will mainly be working with the wine-based data. The other files are there as alternative sets for you to test your code on. Each data file contains N+1 columns: X1, X2, ... XN, and Y. When we test your code we will randomly select 60% of the data to train on and use the other 40% for testing. However, as of this writing, the testlearner.py code uses the first 60% of the data for training, and the remaining 40% for testing. That may be helpful because it will enable you to compare results with your friends on piazza.

Part 1: Implement RTLearner (30%)

You should implement a Random Tree learner class in the file RTLearner.py. You should consult the paper by Adele Cutler as a reference. Note that for this part of the project, your code should only build a single tree (not a forest). We'll get to forests later in the project. The primary differences between Cutler's Random Tree and the methodology originally proposed by JR Quinlan are:

1. The feature i to split on at each level is determined randomly. It is not determined using information gain or correlation, etc.
2. The split value for each node is determined by: Randomly selecting two samples of data and taking the mean of their Xi values.

Your code should support exactly the API defined below. DO NOT import any modules besides those listed in the prohibited/allowed section below. You should implement the following functions/methods:

import RTLearner as rt
learner = rt.RTLearner(leaf_size = 1, verbose = False) # constructor
learner.addEvidence(Xtrain, Ytrain) # training step
Y = learner.query(Xtest) # query

Where "leaf_size" is the maximum number of samples to be aggregated at a leaf. Xtrain and Xtest should be ndarrays (numpy objects) where each row represents an X1, X2, X3... XN set of feature values. The columns are the features and the rows are the individual example instances. Y and Ytrain are single dimension ndarrays that indicate the value we are attempting to predict with X.

If "verbose" is True, your code can print out information for debugging. If verbose = False your code should not generate ANY output. When we test your code, verbose will be False.

This code should not generate statistics or charts. You may modify testlearner.py to generate statistics and charts.

Part 2: Implement BagLearner (20%)

Implement Bootstrap Aggregating as a Python class named BagLearner. Your BagLearner class should be implemented in the file BagLearner.py. It should support EXACTLY the API defined below. You should implement the following functions/methods:

import BagLearner as bl
learner = bl.BagLearner(learner = rt.RTLearner, kwargs = {"leaf_size":1}, bags = 20, boost = False, verbose = False)
learner.addEvidence(Xtrain, Ytrain)
Y = learner.query(Xtest)

Where learner is the learning class to use with bagging. kwargs are keyword arguments to be passed on to the learner's constructor and they vary according to the learner (see hints below). "bags" is the number of learners you should train using Bootstrap Aggregation. If boost is true, then you should implement boosting.

If verbose is True, your code can generate output. Otherwise it should be silent.

Notes: See hints section below for example code you might use to instantiate your learners. Boosting is an optional topic and not required. There's a citation below in the Resources section that outlines a method of implementing bagging. If the training set contains n data items, each bag should contain n items as well. Note that because you should sample with replacement, some of the data items will be repeated.

This code should not generate statistics or charts. If you want create charts and statistics, modify testlearner.py for that purpose.

Part 3: Generate your own datasets (20%)

• Create your own dataset generating code (call it best4linreg.py) that creates data that performs significantly better with LinRegLearner than KNNLearner. Explain your data generating algorithm, and explain why LinRegLearner performs better. Your data should include at least 2 dimensions in X, and at least 1000 points. (Don't use bagging for this section).
• Create your own dataset generating code (call it best4KNN.py) that creates data that performs significantly better with KNNLearner than LinRegLearner. Explain your data generating algorithm, and explain why KNNLearner performs better. Your data should include at least 2 dimensions in X, and at least 1000 points. (Don't use bagging for this section).

Part 4: Experiments and report (30%)

Create a report that addresses the following issues/questions. Use 11pt font and single spaced lines. We expect that a complete report addressing all the criteria would be at least 4 pages. It should be no longer than 10 pages including charts, tables and text. To encourage conciseness we will deduct 2% for each page over 10 pages. The report should be submitted as report.pdf in PDF format. Do not submit word docs or latex files. Include data as tables or charts to support each your answers. I expect that this report will be 4 to 10 pages.

• Include charts or tables of data to support your results. However your submitted code should not generate statistics or charts. Modify testlearner.py to generate statistics and charts.
• Consider the dataset ripple with KNN. For which values of K does overfitting occur? (Don't use bagging).
• Now use bagging in conjunction with KNN with the ripple dataset. Choose some K keep it fixed. How does performance vary as you increase the number of bags? Does overfitting occur with respect to the number of bags?
• Can bagging reduce or eliminate overfitting with respect to K for the ripple dataset? Fix the number of bags and vary K.

What to turn in

Be sure to follow these instructions diligently!

Via T-Square, submit as attachment (no zip files; refer to schedule for deadline):

• Your code as KNNLearner.py, BagLearner.py, best4linreg.py, best4KNN.py
• Your report as report.pdf

Unlimited resubmissions are allowed up to the deadline for the project.

Extra Credit (3%)

Implement boosting as part of BagLearner. How does boosting affect performance for ripple and 3_groups data?

Does overfitting occur for either of these datasets as the number of bags with boosting increases?

Create your own dataset for which overfitting occurs as the number of bags with boosting increases.

Describe and assess your boosting code in a separate report.pdf. Your report should focus only on boosting. It should be submitted separately to the "extra credit" assignment on t-square.

Rubric

• KNNLearner, auto grade 10 test cases (including ripple.csv and 3_groups.csv), 3 points each: 30 points
• BagLearner, auto grade 10 test cases (including ripple.csv and 3_groups.csv), 2 points each: 20 points
• best4linreg.py
  • Code submitted: -5 if absent
  • Description complete -- Sufficient that someone else could implement it: -5 if not
  • Description compelling -- The reasoning that linreg should do better is understandable and makes sense. Graph of the data helps but is not required if the description is otherwise compelling: -5 if not
  • Train and test data drawn from same distribution: -5 if not
  • Performance demonstrates that linreg does better: -10 if not
• best4KNN.py
  • Code submitted: -5 if absent
  • Description complete -- Sufficient that someone else could implement it: -5 if not
  • Description compelling -- The reasoning that KNN should do better is understandable and makes sense. Graph of the data helps but is not required if the description is otherwise compelling: -5 if not
  • Train and test data drawn from same distribution: -5 if not
  • Performance demonstrates that KNN does better: -10 if not
• Overfitting
  • Student conveys a correct understanding of overfitting in the report?: -5 points if not.
  • Is the region of overfitting correctly identified? -5 points if not.
  • Is the conclusion supported with data (table or chart): -5 points if not.
• Bagging
  • Correct conclusion regarding overfitting as bags increase, supported with tables or charts: -10 points if not.
  • Correct conclusion regarding overfitting as K increases, supported with tables or charts: -10 points if not.

Test Cases

Here are the test cases we used while grading. These are updated each semester, and released after grading.

• MC3-Project-1-Test-Cases-spr2016

Required, Allowed & Prohibited

Required:

• Your project must be coded in Python 2.7.x.
• Your code must run on one of the university-provided computers (e.g. buffet02.cc.gatech.edu), or on one of the provided virtual images.
• Your code must run in less than 5 seconds on one of the university-provided computers.
• The code you submit should NOT include any data reading routines. The provided testlearner.py code reads data for you.
• The code you submit should NOT generate any output: No prints, no charts, etc.

Allowed:

• You can develop your code on your personal machine, but it must also run successfully on one of the university provided machines or virtual images.
• Your code may use standard Python libraries.
• You may use the NumPy, SciPy, matplotlib and Pandas libraries. Be sure you are using the correct versions.
• You may reuse sections of code (up to 5 lines) that you collected from other students or the internet.
• Code provided by the instructor, or allowed by the instructor to be shared.
• Cheese.

Prohibited:

• Any other method of reading data besides testlearner.py
• Any libraries not listed in the "allowed" section above.
• Any code you did not write yourself (except for the 5 line rule in the "allowed" section).
• Any Classes (other than Random) that create their own instance variables for later use (e.g., learners like kdtree).
• Code that includes any data reading routines. The provided testlearner.py code reads data for you.
• Code that generates any output when verbose = False: No prints, no charts, etc.

Legacy

MC3-Homework-1-legacy