Assignment 1: Reading a Paper

Due: Wednesday, October 2 at 4:00pm. Submit on Canvas.

Summary

Research gets transmitted in many forms — demos, code, talks, and more — but its formal report most often occurs through a written paper. The paper explains the problem, the approach, and an evaluation. When ready, the academic submits the paper for review by other academics; once it passes this peer review process, the paper appears at a venue such as conference or journal.

Since most research is disseminated in the form of papers, it's critical to be able to read research papers and make sense of them. Your first assignment will be to read a paper in the area of your project interest, and to synthesize its main argument into a detailed outline. In addition, you will be getting set up with any prerequisites for your section — e.g., getting a machine learning environment working for the AI section. Don't underestimate the time required for either of these!

Part 1: Read a paper and outline its argument and structure

Each section has listed five papers below; each paper is related to a potential project in that section. Pick a paper that is interesting to you, find yourself a quiet place, and work your way through it. Don't worry if you can't understand every detail; focus on understanding the paper's big ideas and how they are argued. It can take time to read a paper — don't feel discouraged if it takes you a long time.

Your outline should recompress the paper back into an outline format that explains the paper's argument. We suggest the following structure of one paragraph per bullet, with an example outline following the description:

  • Title: What paper did you read?
  • Problem: What problem is it solving? Why does this problem matter?
  • Assumption in prior work: What was the assumption that prior research made when solving this problem? Why was that assumption inadequate?
  • Insight: What is the novel idea that this paper introduces, breaking from that prior assumption?
  • Technical overview: How did the paper implement that insight? I.e., What did they build, or what did they prove, and how?
  • Proof: How did the paper evaluate or prove that its insight is correct, and is better than holding on to the old assumption?
  • Impact: What are the implications of this paper? How will it change how we think about the problem?

You may adapt this structure if needed for the paper you are outlining; check with your TA first if your proposed structure deviates by more than one bullet.

Example, for the paper Flash Organizations: Crowdsourcing Complex Work by Structuring Crowds As Organizations:

  • Title: Flash Organizations: Crowdsourcing Complex Work by Structuring Crowds As Organizations
  • Problem: Crowdsourcing has been used successfully for many goals that can be decomposed into small, modular microtasks, but it has struggled to achieve more complex goals such as design and engineering. For example, tasks such as image labeling work because it's modularizable, but design is interdependent and requires adapting as you go, so crowdsourcing has succeeded at image labeling but failed at design. If crowdsourcing is limited to modular tasks, then it will never be able to achieve goals of meaningful complexity, which will limit its impact on the world.
  • Assumption in prior work: Prior work all takes an algorithmic model of crowdsourcing: the programmer specifies who does what, and when, in a kind of big algorithmic recipe to follow. This assumption shows up in goals ranging from Wikipedia ("edit this page"), to interactive crowd-powered interfaces ("find errors" --> "fix errors" --> "verify fixes"), to open source software ("create a module with this fixed API").
  • Insight: This paper proposed that instead of coordinating crowds as we do algorithms, that we should be coordinating crowds as we do with organizations. They propose a series of computationally-enhanced versions of the structures that organizations use — roles, tasks, hierarchy, and so on — and introduce the idea of a flash organization, which is a rapidly assembled collective of online collaborators who use these computational organizational structures to coordinate.
  • Technical overview: The authors created a system called Foundry that implements these ideas. Foundry is a web interface that connects to the Upwork online labor marketplace to draw on-demand expertise. It uses a combination of first-come-first-served hiring queues and Slack integration to bring workers onboard and keep them updated. It introduces an adaptation model drawn from the metaphor of code branching and merging to enable the organization to adapt.
  • Proof: Three non-crowdsourcing experts used the system to convene and lead flash organizations to achieve proof-of-concept complex goals. These experts created (1) a tablet system for EMTs to report medical trauma cases enroute to the hospital, (2) a card game for storytelling, which was playtested and iterated upon, and (3) an enterprise-grade event planning system that had to meet branding and security standards.
  • Impact: Flash organizations offer a broad new view of crowdsourcing — one that's not rooted in Tayloristic algorithms, but instead in an organizational metaphor. This approach can achieve far more complex outcomes, enabling crowdsourcing to apply to a broad new class of problems. It has implications for the future of work (how do we protect labor rights?), for organizations (what will organizations look like in the future if flash organizations are widely deployed?), and for collaboration (will we all work remotely?).

Here are the paper options for each section. Look at your section's project list and pick the paper that corresponds to a project that intrigues you:

AI

AI project list here

Note: For papers 1, 3, 4, and 5, these two resources will be helpful:

HCI

HCI project list here

Systems

Systems project list here

Part 2: Complete starter task for your section

Each section (AI, HCI, and Systems) will have a starter task to get set up for the projects you'll be doing.

AI

Set up Google Colab and train a model on MNIST using PyTorch to at least 95% test accuracy. You may use any resource you want as long as you clearly cite it and understand what the code is doing. You may wholesale copying code, but you MUST cite any code you copy. Not citing used code constitutes an honor code violation.

  • Note 1: Google Colab uses your Google Drive space, so please use your Stanford drive if you want to avoid using storage space on your personal account (your Stanford drive has unlimited storage).
  • Note 2: Make sure to set an accelerator for improved speeds (Edit -> Notebook settings -> Hardware accelerator -> GPU). You may have to do this every time you open a notebook.
  • Note 3: Please contact Daniel ASAP if this task causes issues - using deep learning frameworks will be critical for all of the projects.

Instructions:

  1. Walk through the welcome Colab notebook (watch the video, run a few lines of Python): https://colab.research.google.com/notebooks/welcome.ipynb
  2. Set up a new notebook for this assignment.
  3. If you haven’t used PyTorch, walk through the 60 minute blitz. Make sure you’ve set the accelerator in your Colab notebook (note 2). The blitz is here: https://pytorch.org/tutorials/beginner/deep_learning_60min_blitz.html
    • Torch should already be installed in Colab
    • Use Python 3
    • Don’t just read the code, actually run it in Colab
  4. Read and understand the following code: https://github.com/pytorch/examples/tree/master/mnist
  5. Transfer the code from that repository to the Colab. You may copy code.

Get used to git by:

Deliverables

Combine the following into a single PDF and upload it to Canvas

  1. A short (one paragraph) writeup on using Colab, PyTorch, and what was difficult in the process.
  2. The notebook exported as a PDF.
  3. A link to the notebook (your instructor may request access to it).

HCI

Complete CITI training and upload your CITI certification. If you are not already certified to work with human subjects, follow the steps below:

  1. Go to the CITI webpage: https://www.citiprogram.org/index.cfm?pageID=14
  2. Click: “Log in through my institution” and select “Stanford University”
  3. Under "Learner Tools for Stanford University," click "Add a Course"
  4. Fill out the questions in the form: you are in Group 2 (Nonmedical Research) and do not currently need to complete a responsible conduct of research course (although you are encouraged to!)
  5. Complete each module in the course. You need to complete all modules with an average score of 96% to pass. This will take about 2-3 hours.

Familiarize yourself with git by:

Deliverables

Save your completion certificate and upload it to Canvas.

Systems

Getting familiar with Google cloud and git:

  1. Create a Google cloud instance
    • OS: Linux
    • Machine type: n1-standard-1
    • Region: us-west1
  2. If you have never used git before, skim the documentation below to get started: https://git-scm.com/book/en/v2/Getting-Started-About-Version-Control

Reproducing a benchmark

  1. Clone the following repository: https://github.com/stanford-futuredata/index-baselines
  2. Install the necessary packages on your GCP instance for C, C++ development e.g., apt-get update && apt-get install build-essential
  3. Follow the instructions until the “Hashing” section
  4. If everything runs correctly, you should see something like the following:
    Loaded 1900000 keys
    Benchmarking LinkedHashMap with 32-bit values
    Done inserting keys, filled = 1201166
    LinkedHashMap average time taken: 100.275789 ns, hits: 1900000
    Benchmarking CuckooHashMap with 32-bit values
    Done inserting keys, set size = 1900000
    CuckooHashMap average time taken: 91.580000 ns, hits: 1900000
    Benchmarking CuckooHashMap without values
    Done inserting keys, set size = 1900000
    CuckooHashMap average time taken: 47.892632 ns, hits: 1900000
  5. Repeat the above experiment a few times: are the runtimes reported above stable across the different runs?

Create a new local branch named ‘experiment’

  1. Modify gen_lognormal.cpp such that it generates datasets with 57M, 19M, and 1.9M unique 32-bit integers
  2. For each dataset size
    • Recompile the project
    • Run the hashing experiment 5 times and log the results
  3. Generate the following plot in Excel or your favorite plotting software:
    • X-axis: dataset size (1.9M, 19M, 57M)
    • Y-axis: average lookup time in ns
    • For each type of hashmap, plot its average lookup time as well as the standard error as error bars for each data size. There should be 3*3=9 points on this plot.
    • If the error bars are large, you might want to repeat the measurement a couple more times.
    • Please refer to the example below for what this plot should look like. Note that the data used to generate the following plot is made up, so don’t worry if your actual plot has different values/trends.

      • example plot

  4. Commit your local changes and push to the remote repository
  5. Don’t forget to shut down your GCP instance when you are done! Otherwise the credits are going to burn quickly.

Deliverables

Compile the following as a single PDF and submit to Canvas.

  • The plot described above
  • Answer the following questions in a few sentences:
    • Based on your experiments, what conclusions can you draw on the lookup performance of the three implementations of hash tables?
    • Based on your experiments, what effect, if any, does the dataset size have on the lookup performance of hash tables?

Part 3: Submit Project Interest Rankings

Finally, please submit project interest rankings for the projects in your section. These rankings will not be used to assign projects. Rather, they will give the course staff information to help faciliatate the creation of teams during your next section. Fill out the appropriate form below:

Submission

You are expecting to submit two PDFs for this assignment:

  • Submit a PDF with your paper outline on Canvas.
  • Submit a PDF for your section’s starter task on Canvas.
  • Submit your responses to the project ranking form linked above.

Grading

Your outline will be graded on the following rubric:

  • Accuracy: does the description correctly describe the paper? (5pt)
  • Completeness: does the description capture all the important ideas in the paper? (Not all the ideas; all the important ideas.) (5pt)
  • Clarity: does the description convey the ideas understandably to the reader? (5pt)

In addition, your starter task will be graded pass/fail, and worth a final 5pt.