CS269: Machine Learning TheoryFinal Project GuidelinesFall 20101 Project OverviewAll students enrolled in CS269 are required to complete a class project. This project is intended to provideyou with a chance to explore recent research on a particular subtopic of machine learning theory in moredepth on your own. The project is fairly open-ended. You may choose to explore any topic that excites you,as long as your project touches on the theoretical foundations of learning.Projects may be completed in groups of up to three students. While students are free to work aloneif they wish, collaboration is strongly encouraged. Some of the papers you read will involve ideas andtechniques that are new to you, and it can be extremely useful to discuss them with your partners. Plus, theresearch process is more fun when you get to share your ideas and discoveries with friends.2 Project TypesThere are three primary styles of projects that I would recommend for most students: a literature synthesisproject, an implementation-based research project, and a theoretical research project. These are describedbelow. However, you are welcome to pursue projects that don’t fit neatly into one of these categories. If youhave such a project in mind, make an appointment to meet with me and we can discuss whether or not itsounds appropriate for the class.Please keep in mind when selecting your project that this is a class on learning theory. Your project mustinvolve a theoretical component. Simply implementing a machine learning algorithm (whether or not it isnovel) and measuring its accuracy on data is not a valid project for this class. However, this can certainlybe a valid component of a bigger project.• Literature Synthesis: If you are interested in learning more about current research on learning theory,but not ready to jump into a research project just yet, you may choose to prepare a literature synthesis(i.e., survey paper) for your final project. This synthesis may be on any subtopic of learning theory,such as learning bounds for domain adaptation, privacy-preserving machine learning, or machinelearning for finance. These and other suggestions are listed on the course website, along with somelinks to relevant papers to get you started. Your survey should not just summarize existing work.You should strive to provide insight about this work, such as connections between different papers,assumptions that you found unrealistic or unmotivated, or interesting open problems that could bestudied. Your grade will be based on both the clarity of your explanations and the insights that youprovide. It should be clear that you have given the topic some real thought, and are not simply restatingresults that appear in the papers you survey.• Implementation-Based Research Project: If you have an idea for an exciting domain in whichmachine learning techniques could be applied, you may wish to do an implementation-based researchproject. For a typical implementation-based project, you should plan to implement a selection of the1algorithms covered in class (e.g., the Perceptron, Weighted Majority, Adaboost, or SVMs) or minorvariations of these algorithms, and compare their performance on a real-world data set of your choice.(Be sure to separate your data into training and test sets to get an accurate measure of generalizationerror. You might want to take a look at some examples of experimental results sections from machinelearning conference papers to get a feel for other conventions.)In addition to empirical results, your report should include a detailed technical discussion of thereasons why one algorithm may have outperformed others, making reference to theoretical resultsdiscussed in class or in the literature. For example, you may choose to compare the performance ofeach algorithm to the performance that would be predicted by the theory. If the theoretical predictionsare inaccurate, discuss why this might be the case. For example, were there assumptions that we hadto make for the analysis that were violated by your data set?If you like, you could additionally try implementing algorithms that we did not discuss in class, oralgorithms of your own. Just remember that your paper must have a theoretical component.• Theoretical Research Project: Finally, you have the option of attempting to generate new theoreticalresults of your own. There are (at least) two good options here. First, you could choose a known openproblem related to models that we have examined in class or other models that have been studied inthe learning theory community and write about your attempts to solve this problem. It’s ok if youdon’t end up solving the problem, as long as you make a reasonable attempt, clearly explain what youtried, and explain why what you tried didn’t work.Alternately, you could design your own model of learning, for example by extending one of themodels that we discussed in class. If you choose this option, you should provide a clear motivationfor your new model and explain your design choices. (What natural learning problem does the modelrepresent? What assumptions are you making and why? What phenomena does your model capturethat existing models do not?) You should also attempt to provide some preliminary results for yourmodel, such as classes that are learnable or algorithms that yield provably low error. Again, it is ok ifyou make a reasonable effort but are unable to prove the results that you hoped for. In this case youshould explain why the techniques you tried failed, and what this says about the model.If you choose to do a theoretical research project, you must do enough of a literature search to bereasonably certain that your ideas are novel. I will expect to see a brief section in your report coveringrelated work.Be warned that theoretical research projects can be really hard! You are certainly not expected toprove ground-breaking theorems in a couple of weeks. Always start by trying to prove somethingsimple, and go on from there. Make an appointment to meet with me if you get stuck.3 Important Dates and MilestonesThere are four deliverables associated with the class project. Each of these is described below. All submis-sions are one per group.• Project Proposals: Proposals should be submitted by email ([email protected]) before the startof class (2pm) on Wednesday, October 27. Submit your proposal in plain text, right in the body of theemail. Be sure to copy all group members on the email so that I