Fall 2008.
|
Location: |
Wednesdays 5:30pm-8:00pm ECCR 151 |
|
Instructor: |
Professor Greg Grudic |
|
Office: |
ECCR 1B21 |
|
Office Hours: |
Tuesdays 1:00 to 2:00 And By Appointment |
|
Phone: |
303-492-4419 |
|
Email: |
grudic@cs.colorado.edu |
Term Project: (Due December 17, 2008 – Please email the project directly to me.) The project write-up should include concise descriptions of 1) what you did, 2) why you did it, 3) your experimental or theoretical results, 4) a conclusion, and 5) future work (if applicable). All software written for the project should be submitted, along with all detailed experimental results if appropriate. The default project should either use either WEKA (http://www.cs.waikato.ac.nz/ml/weka/ ) or other publically available software to analyze the following datasets: Data_Default_Project.zip – there are five data sets, four classifications and one regression. You should use at least 3 different algorithms to estimates future error rates on each data set, for each algorithm type.
Quizzes:
· Quiz 1 (CSCI5622_Quiz_1.pdf):
Please answer questions using a pencil or pen. This is a take home quiz due On Wednesday, October 8, 2008,
at the beginning of class.
· Quiz 2 (CSCI5622_Quiz_2.pdf):
Please answer questions using a pencil or pen. This is a take home quiz due On Wednesday, November 12, 2008,
at the beginning of class.
Homework: Please submit homework to Shumin Wu
[wushumin@gmail.com]. In the subject of the homework use: “CSCI5622_HW#”, where
# is the homework number (1, 2, 3, etc).
· Homework
1 (Due Wednesday October 1, 2008): Document the Matlab code in Linear_RSS_and_Ridge.zip and Demo_Kernels.zip. In documenting the code,
concentrate your efforts in relating the equations implemented in the code to
those presented in the class notes.
· Homework
2 (Due Wednesday October 22, 2008): Implement Kernel Ridge Regression using the code in Homework 1 as
Building Blocks (see pages 9 to 11 of Intro_Regression.pdf
for hints). The functions you need to implement must work when you run the matlab function Test_Ridge.m in
the file HW2_Code_Data.zip. The matlab functions you need to implement are called Learn_Kernel_Regression_Model.m and Evaluate_Kernel_Regression_Model.m
(see Test_Ridge.m for the input and outputs of these
functions). Note that, running Test_Ridge.m with no
changes should give you figures 1 to 3 as in HW2_Code_Data.zip.
However, you need to test you code with all three kernel types and a variety a
kernel parameter values before handing it in. Make sure your code runs with higher dimensional data (i.e. d > 1). You need not use more than about 10 or so
training examples for this high dimensional data. Please email a zipped
directory containing all the code you use, and the high dimensional data you
tested on (testing with d = 2, 3, and 10 is fine). In your email, please
explain how you generated the higher dimensional data.
· Homework
3 (Due Wednesday November 12, 2008): You are free to talk with anyone about this homework, but the code
you hand in must be your own.
Please hand in your answers and matlab code in the
directory containing the template code (i.e. HW3_code.zip).
This homework consists of two parts.
1. Part 1. Implement the batch and online Perceptron
algorithms described in slide 14 of Perceptron.pdf.
The template code is in HW3_code.zip. Implement your
online version in the matlab file Learn_Perceptron.m,
and the batch version in matlab file Learn_Perceptron_Batch.m. These files should be executable
from the matlab file HW_3_main.m. Use the flag
variable “Cost_Function_Type = 1”, in HW_3_main.m, to
indicate the standard Perceptron algorithm (i.e update rule). Debug your algorithm with separable data,
chosen by setting “Data_Sepearable = 1” in
HW_3_main.m.
2. Part 2. Modify the Perceptron
update rule to give 1) appropriate convergence for non-separable data, and 2)
convergence to a unique hyperplane when the data is
linearly separable (independent of initial randomly selected model parameters).
This new algorithm should be used when the flag “Cost_Function_Type
= 2” is set in HW_3_main.m. You can use the linear and non-linear data in
HW_3_main.m as a guide in creating your
own data for debugging your new modified Perceptron
like update rule. Briefly justify your new update rule, and the data you used
to debug it. Define what you mean by “appropriate convergence for non-separable
data” and “convergence to a unique hyperplane”.
Include the your debug data in homework submission.
· Homework
4 (Due Wednesday December 10, 2008): You are free to talk with anyone about this homework, but the code
you hand in must be your own.
This homework consists of two parts.
1.
Part 1.
Estimate the future error of a model constructed on the data HW4_Data.zip using a support vector machine with a
radial basis function kernel. Use the LIBSVM package (http://www.csie.ntu.edu.tw/~cjlin/libsvm/
) with the Matlab Interface (http://www.csie.ntu.edu.tw/~cjlin/cgi-bin/matlab.cgi?+http://www.csie.ntu.edu.tw/~cjlin/libsvm/matlab+zip
). To estimate your error, do 50 random experiments, each time splitting the
data randomly into 10% for testing and 90% for training. The training data
should be used in a 5 fold cross validation experiment to pick the “best”
radial basis function kernel parameter gamma,
and the “best” value for C (use the
C-SVM implementation; i.e. set “–s 0”). Make sure to normalize your data and to
find an appropriate search range for C
and gamma. Once you find your
optimal C and gamma, use the entire 90% of the data to build a single SVM model
with these parameters, and use it to obtain an error rate on the 10% test data.
Report your final estimated error on future data by averaging the error rates
over the 50 experiments.
2.
Part2. Repeat this experimental scenario by mapping the data into radial basis
function kernel space (i.e. the same kernel as for the SVM experiments), and
using the Modified Perceptron Algorithm you developed
in part 2 of Homework 3. Once more use the 90% training set to perform 5 fold
cross validation to pick the “best” radial basis function kernel parameter gamma, as well as the parameters
associated with your Modified Perceptron Algorithm. Once these learning
parameters are known, use the entire 90% training set to build a single model
for testing on the 10% test set.
Please Submit the following: Report the average error on future data of this
Modified Perceptron Algorithm by averaging all your
errors over the 50 random experiments. In a single zip file, email the Shumin
Wu [wushumin@gmail.com] in 1) all code (which must be in matlab)
used to run these experiments, 2) instructions on how to run the code, 3) the
final error rates on for the SVM algorithm and the Modified Perceptron
Algorithm.
Weekly Class Schedule:
1. August 27, 2008: Introduction.
2. September 3, 2008: K Nearest Neighbor Algorithm (NearestNeighbor.pdf). Introduction to regression (Regression_1.pdf, Intro_Regression.pdf). Introduction to Kernels (Mercer_Kernels.pdf). Please read and be prepared to discuss the following Classification_1.pdf for next class.
3. September 10, 2008: Introduction to classification (please read the following before class Classification_1.pdf). Introduction to Matlab (please go over the Matlab introduction before class). Perceptron Algorithms (Perceptron.pdf). Code samples: Linear_RSS_and_Ridge.zip and Demo_Kernels.zip.
4. September 17, 2008: Cross Validation, Model Selection, and Accuracy Estimation (Model_Selection_1.pdf).
5. September 24, 2008: Support Vector Machine (SVM) Classification (SMV_classification.pdf).
6. October 1, 2008: Support Vector Machine (SVM) Regression (SMV_regression.pdf). Decision Trees (Trees.pdf).
7. October 8, 2008: Ensemble Learning (Approaches_To_Supervised_Learning.pdf).
8. October 15 2008: Neural Networks (NeuralNetwork.pdf).
9. October 22 2008: Neural Networks (NeuralNetwork.pdf).
10. October 29 2008: Bayesian Learning. K-Means Clustering. (Bayesian_1.pdf)
11. November 5, 2008: Sparse Linear Systems (code). Linear Discriminant Analysis (LDA), Fisher's Linear Discriminant, Quadratic Discriminant Analysis (QDA). Mixture of Gaussians.
12. November 12, 2008: Reinforcement Learning and Review.
13. November 19, 2008: Midterm Exam.
14. November 26, 2008: No Class.
15. December 3, 2008: Dimensionality Reduction.
16. December 10, 2008: Reinforcement Learning (pdf
). Semi-Supervised Learning (paper) (code).
If you qualify for accommodations because of a disability, please submit to me a letter from Disability Services in a timely manner so that your needs may be addressed. Disability Services determines accommodations based on documented disabilities. Contact: 303-492-8671, Willard 322, and http://www.Colorado.EDU/disabilityservices.
Campus policy regarding religious observances requires that faculty make every effort to reasonably and fairly deal with all students who, because of religious obligations, have conflicts with scheduled exams, assignments or required attendance. See full details at http://www.colorado.edu/policies/fac_relig.html.
Students and faculty each have responsibility for maintaining an appropriate learning environment. Those who fail to adhere to such behavioral standards may be subject to discipline. Professional courtesy and sensitivity are especially important with respect to individuals and topics dealing with differences of race, culture, religion, politics, sexual orientation, gender, gender variance, and nationalities. Class rosters are provided to the instructor with the student's legal name. I will gladly honor your request to address you by an alternate name or gender pronoun. Please advise me of this preference early in the semester so that I may make appropriate changes to my records. See polices at http://www.colorado.edu/policies/classbehavior.html and at http://www.colorado.edu/studentaffairs/judicialaffairs/code.html#student_code
The University of Colorado at Boulder policy on Discrimination and Harassment, the University of Colorado policy on Sexual Harassment and the University of Colorado policy on Amorous Relationships apply to all students, staff and faculty. Any student, staff or faculty member who believes s/he has been the subject of discrimination or harassment based upon race, color, national origin, sex, age, disability, religion, sexual orientation, or veteran status should contact the Office of Discrimination and Harassment (ODH) at 303-492-2127 or the Office of Judicial Affairs at 303-492-5550. Information about the ODH, the above referenced policies and the campus resources available to assist individuals regarding discrimination or harassment can be obtained at http://www.colorado.edu/odh
All students of the University of Colorado at Boulder are responsible for knowing and adhering to the academic integrity policy of this institution. Violations of this policy may include: cheating, plagiarism, aid of academic dishonesty, fabrication, lying, bribery, and threatening behavior. All incidents of academic misconduct shall be reported to the Honor Code Council (honor@colorado.edu; 303-725-2273). Students who are found to be in violation of the academic integrity policy will be subject to both academic sanctions from the faculty member and non-academic sanctions (including but not limited to university probation, suspension, or expulsion). Other information on the Honor Code can be found at http://www.colorado.edu/policies/honor.html and at http://www.colorado.edu/academics/honorcode/