CS221 Final Project Guidelines
The final project gives you an opportunity to apply the techniques that you've
learned in this class to a new setting that you're interested in.
Specifically, you will build a system to solve a well-defined task.
Which task you choose is completely open-ended, but the methods you use should
be drawn from the ones from the course.
You should work in groups of two (individual projects are okay too).
The project can overlap with your research or other classes,
but what you produce in the end must conform to the CS221 guidelines.
The project consists of the following pieces:
- Task definition: What does your system do (what is its input and output)?
What real-world problem does this system try to solve?
Be precise about the scope of the project and ensure that it is not too
narrow or broad. For example, building a system to answer any natural
language question is too broad, whereas answering short factoid questions
about movies is more reasonable. You are encouraged to come to office hours
to get help finding the appropriate definition. This is probably the most
important part of the project, but is also the part that you will not get
practice doing from homeworks.
Finally, how will you measure success of your system? Usually, this involves
collecting a dataset of example scenarios, either from existing sources or
creating one from scratch.
Approach: What are the challenges of building the system?
How should you model the task (e.g., using search, machine learning, logic, etc.)?
There are going to be many ways to do this, but you should pick one or two
and explain how the methods address the challenges as well as any pros and cons.
What algorithms are appropriate for handling the models that you came up with
and what are the tradeoffs between accuracy and efficiency?
Are there any implementation choices specific to your problem?
- Literature review: Have there been other attempts to build such a
system? Compare and contrast your approach with existing work, citing the
- Error analysis:
Design a few experiments to show the properties (both pros and cons) of your system.
For example, if your system is supposed to deal with graphs with lots of cycles,
then show this. Each experiment should ask a concise question, such as: Do we need
to model the interactions between the ghosts in Pac-Man? or
How well does the system scale up to large datasets?
Analyze the data and show either graphs or tables to illustrate your point.
What's the take-away message? Were there any surprises?
Throughout the quarter, there will be several milestones so that you can get
adequate feedback on the project.
- Ideas (1-2 pages, due Tue Oct 1):
Brainstorm two ideas of systems that you could build. Be specific about the
input/output behavior of the system and the scope of the project.
What is your evaluation metric for success?
Collect some preliminary data, and give concrete examples of inputs and
outputs. What are the challenges? Which topics (e.g., search,
MDPs, etc.) might be able to address those challenges (at a high-level, since
we haven't covered any techniques in detail at this point)?
Search the Internet for similar projects and mention the related work.
You should have thought through the problems at this point, even if you don't
know how to solve them.
- Proposal (1-2 pages, due Tue Oct 22): Choose one idea and refine
your task definition and literature review based on feedback.
Gather any necessary data and implement a simple baseline system. Describe
the data and the preliminary results of your baseline system.
You should basically have all the infrastructure (e.g., building a simulator,
cleaning data) completed to do something interesting by now.
- Progress report (3-5 pages, due Tue Nov 5):
Propose a model and an algorithm for tackling your task. You should describe
the model and algorithm in detail and use a concrete example to demonstrate
how the model and algorithm work.
Don't describe methods in general; describe precisely how they apply to your method
(what are variables, factors, states, etc.)?
You should also also have made a decent amount of progress towards
implementing the algorithm — were there any unexpected challenges?
- Poster session (Dec 4, in class):
By the poster session, you should have finished implementation, run
some preliminary experiments, and done some basic analysis.
In the poster, you should describe the motivation, problem definition,
challenges, approaches, and results and analysis.
Use lots of diagrams and a few bullet points rather than long sentences and equations.
The goal of the poster is to convey the important high-level ideas and give intuition
rather than be a formal specification of everything you did.
You will be evaluated on both the contents of the poster as well as your
presentation. During the poster session, the course staff will come around.
You should be able to give a 30-second elevator pitch providing the
highlights of your work, but also be prepared to take questions about any of
the specific details.
- Final report (5-10 pages, due Fri Dec 13):
Incorporate any feedback from the poster session. You should additional
experiments to answer the remaining error analysis questions.
You should submit a PDF with your writeup, as well as supplementary material
(code and data and a README file documenting what everything is, and what
commands you ran). You can use standard libraries, as long as you are clear
about which parts you implemented.
- Task definition: is the task precisely defined and does the formulation make sense?
- Approach: was a baseline method and an advanced method described clearly, well justified, and tested?
- Data and experiments: was the data explained clearly, and were systematic
experiments done, and concrete results reported?
- Analysis: did you interpret the results and try to explain why things
worked (or didn't work) the way they did? Do you show concrete examples?
- Extra credit: does the project and present interesting and novel ideas
(i.e., would this be publishable at a good conference)?
This is a suggestion of how to approach the final project with an example.
- Pick a topic that you're passionate about (e.g., food, language, energy,
politics, sports, card games, robotics).
As a running example, say we're interested in how people read the news to get their information.
- Brainstorm to find some tasks on that topic: ask wouldn't it be nice to
have a system that does X or wouldn't it be nice to understand X? A good
task should not be too easy (sorting a list of numbers) and not too hard
(building a system that can automatically solve CS221 homeworks).
Please come to office hours for feedback on finding the right balance.
Let's focus on recommending news to people.
- Define the task you're trying to solve clearly and convince yourself (and a few friends) that it's important/interesting.
Also state your evaluation metric – how will you know if you have succeeded or not?
Concentrate on a small set of popular news sites: nytimes.com, slashdot.org, sfgate.com, onion.com, etc.
For each user and each day, assume we have acquired a set of articles that the user is interested in reading (training data).
Our task is to predict for a new day, given the full set of articles, the best subset to show the user;
evaluation metric would be prediction accuracy.
- Gather and clean the necessary data (this might involve scraping websites, filtering outliers, etc.).
This step can often take an annoyingly large amount of time if you're not careful, so do not try to get bogged down here.
Simplify the task or focus on a subset of the data if necessary.
You might find yourself adjusting the task you're trying to solve based on new empirical insights you get by looking at the data.
Notice that even if you're not doing machine learning, it's necessary to have data for evaluation purposes.
Write some scripts that download the RSS feeds from the news sites, run
some basic NLP processing (e.g., tokenization), say, using NLTK.
- Implement a baseline algorithm. For a classification task, this would be
always predicting the most common label. If your baseline is too high, then
your task is probably too easy.
One baseline is to always produce the first document from each news site.
- Implement at least two complementary algorithms. What are the different
tradeoffs of each? Can they be combined into a new algorithm that draws from
the advantages of both (this is usually a good way of deriving new
algorithms)? Remember to try as much as possible to separate model (what you
want to compute) from algorithms (how you do it).
You might train a classifier to predict, for each news article, whether to include it or not.
You might try to include these predictions as factors in a weighted CSP and
try to find a set of articles that balance diversity and relevance.
- Perhaps the most important part of the project is the final step, which
is to analyze the results. It's more important that you do a thorough
analysis and interpret your results rather than implement a huge number of
complicated heuristics in trying to eke out the maximum performance.
The analysis should begin with basic facts, e.g., how much time/memory did
the algorithm take, how does the accuracy vary with the amount of training
data? What are the instances that your system does the worst on? Give concrete examples
and try to understand why? Is there a bottleneck? Is it due to lack of training data?
- Predict the price of airline ticket prices given day time, location, etc.
- Predict the amount of electricity consumed over the course of a day.
- Based on sensor readings from your smartphone, predict whether the phone should be switched off.
- Auto-complete of code when you're programming.
- Search for source code using natural language.
- Answer questions for a restricted domain (e.g., movies, sports).
- Solve Sudoku puzzles or crossword puzzles.
- Find the optimal way to get from one place on Stanford campus to another place, taking into account
uncertain travel times due to traffic.
- Break substitution codes based on knowledge of English.