Grading_by_matrix_completion.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING: Method definition ==(Base.Nullable{S}, Base.Nullable{T}) in module Base at nullable.jl:238 overwritten in module NullableArrays at /Users/madeleine/.julia/v0.6/NullableArrays/src/operators.jl:128.\n"
     ]
    }
   ],
   "source": [
    "using DataFrames, Plots, LowRankModels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Grading by Matrix-Completion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are $m$ ORIE 4741 project groups with $n$ students, and each student is responsible for grading several projects. \n",
    "\n",
    "Each project has an underlying quality; some are good, some less good. Some students are fair graders, and report the project quality as their grade. Some are easy graders, and report a higher grade. Some are harsh graders, and report a lower grade.\n",
    "\n",
    "We'll collect the grades into a grade matrix $A \\in \\mathbb{R}^{m \\times n}$: $A_{ij}$ will represent the grade that student $j$ would assign to project $i$.\n",
    "\n",
    "Of course, we cannot assign each student to grade every project. Instead, we make peer review assignments $\\Omega = \\{(i_1, j_1), \\ldots, \\}$. Here, $(i,j) \\in \\Omega$ if student $j$ is assigned to grade project $i$. Let us suppose each project is graded by $p$ peers.\n",
    "\n",
    "Unfortunately, this means that some projects are assigned harder graders than other projects. Our goal is to find a fair way to compute a project's final grade. We consider two methods:\n",
    "\n",
    "1.  *Averaging.* The grade $g_i$ for project $i$ is the average of the grades given by peer reviewers:\n",
    "\n",
    "    $$g^\\text{avg}_i = \\frac 1 p \\sum_{j: (i,j) \\in \\Omega} A_{ij}$$\n",
    "\n",
    "2.  *Matrix completion.* We fit a low rank model to the grade matrix and use it to compute an estimate $\\hat A$ of the grade matrix. \n",
    "    To be more concrete, let's suppose that we find $\\hat A$ by fitting a rank-1 model. We will use Huber loss, for robustness against outlier grades, and nonnegative regularization, since both student grading toughness and project quality are nonnegative.\n",
    "    $$\\text{minimize} \\quad \\sum_{(i,j) \\in \\Omega} \\text{huber}(A_{ij} - x_i y_j) + \\mathbb{1}(x \\geq 0) + \\mathbb{1}(y \\geq 0), $$\n",
    "    where $x \\in \\mathbb{R}^m$ and $y \\in \\mathbb{R}^n$. \n",
    "    \n",
    "    We will then compute our estimate $\\hat A$ as \n",
    "    $$ \\hat A = x y^T. $$\n",
    "    In other words, $\\hat A$ is the rank-1 matrix that matches the observations best in the sense of Huber error.\n",
    "    \n",
    "    We compute the grade $g_i$ for project $i$ as the average of these estimated grades:\n",
    "\n",
    "    $$g^\\text{mc}_i = \\frac 1 n \\sum_{j=1}^n \\hat A_{ij}$$\n",
    "\n",
    "In this problem, we will consider which of these two grading schemes, averaging or matrix completion, is better."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## a) Analytical problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider $m=2$ project groups and $n=4$ peer graders. Suppose group 1 did well on their project and deserves a grade of 6; whereas group 2 deserves a grade of 3. Graders 1 and 2 are easy graders, and graders 3 and 4 are harsh. \n",
    "\n",
    "Each project is graded by three graders. The grades given are\n",
    "    $$X= \\begin{bmatrix}\n",
    "    \\times \\quad 8 \\quad 4 \\quad 4\\\\ \n",
    "    4 \\quad 4 \\quad 2 \\quad \\times\\\\\n",
    "    \\end{bmatrix}.$$\n",
    "Here, an $\\times$ in the $(i,j)$th entry means the $j$th student was not responsible for grading the $i$th project. \n",
    "    \n",
    "Use both methods, averaging and matrix completion, to compute grades for the two groups. Here, you should be able to compute the results of both methods by hand (on paper). Explain how you computed $\\hat A$.\n",
    "\n",
    "Compare your results. Which grading method would you say is more fair?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## b) A more realistic example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's generate a more realistic example of a grade matrix and observation matrix. We use the following code to construct a rank-1 grade matrix with 40 rows and 120 columns, with true project quality scores ranging from 3 to 8 and student easyness index (ratio of the given score to the true score) ranging from 0.5 to 1.5. Each group is graded by 6 graders. \n",
    "\n",
    "Describe in words the structure of the true grades matrix generated by the code below. What rank does it have?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "srand(0)\n",
    "nprojects = 40\n",
    "nstudents = 120\n",
    "project_quality = rand(3:8, 40)\n",
    "student_easyness = vcat([i*ones(24) for i in .5:.25:1.5]...) # students are arranged in increasing order by easyness\n",
    "\n",
    "# grade matrix\n",
    "grades = project_quality*student_easyness'\n",
    "\n",
    "# generate observations\n",
    "obs_mat = zeros(size(grades)) # matrix of observations (1 for observed, 0 otherwise)\n",
    "Ω = Tuple{Int64,Int64}[]      # list of observations Ω\n",
    "for iproj = 1:nprojects\n",
    "    obs_mat[iproj, mod.(3*(iproj-1) + (0:5), 120) + 1] = 1\n",
    "    for j in mod.(3*(iproj-1) + (0:5), 120) + 1\n",
    "        push!(Ω, (iproj, j))\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## c) Fit a low rank model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the LowRankModels package, fit a rank-1 model for this grade matrix using a huber loss function and a nonnegative regularizer. Use your model to compute an estimated grade matrix $\\hat A$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "srand(0); # ensures GLRM model for everyone completing this hw will be initialized in the same way every time\n",
    "\n",
    "# fit model\n",
    "\n",
    "# predict Ahat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## d) Grade the projects"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compute final grades for all 40 projects using both Method 1 and 2. Compare the results. Which method would you say is more fair?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## e) (Extra credit) Distributions \n",
    "\n",
    "Try some other distributions for grades by changing the way we generated data, or changing how students are assigned to grade projects. Do the results change?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## f) (More extra credit) Low rank models\n",
    "\n",
    "Try some other matrix completion models, using different loss functions, regularizers, or ranks, initializing the models using different tricks, or changing the parameters of the optimization algorithm used by LowRankModels. Which work better and which work less well? Why do you think that is?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.6.0",
   "language": "julia",
   "name": "julia-0.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}