{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "Programming Assignment 2\n", "=======\n", "\n", "\n", "### Instructions / Notes:\n", "\n", "**_Read these carefully_**\n", "\n", "* **IMPORTANT**: In your terminal run `pip install --user --upgrade ipython-sql`. This will install the necessary sql packages for Jupyter notebook.\n", "* Run the cell below to load the database `assignment2.db` (make sure the actual database file, `assignment2.db`, is in the same directory as this IPython notebook is running in)\n", "* Some of the problems involve _changing_ this database (e.g. deleting rows)- you can always re-download `assignment2.db` or make a copy if you want to start fresh!\n", "* You **may** create new IPython notebook cells to use for e.g. testing, debugging, exploring, etc.- this is encouraged in fact!- **just make sure that your final answer for each question is _in its own cell_ and _clearly indicated_**\n", "* When you see `In [*]:` to the left of the cell you are executing, this means that the code / query is _running_.\n", " * **If the cell is hanging- i.e. running for too long: To restart the SQL connection, you must restart the entire python kernel**\n", " * To restart kernel using the menu bar: \"Kernel >> Restart >> Clear all outputs & restart\"), then re-execute the sql connection cell at top\n", " * You will also need to restart the connection if you want to load a different version of the database file\n", "* Remember:\n", " * `%sql [SQL]` is for _single line_ SQL queries\n", " * `%%sql [SQL]` is for _multi line_ SQL queries\n", "* **See Piazza for submission instructions**\n", "* _Have fun!_" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "u'Connected: @assignment2.db'" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Connect to the database.\n", "%load_ext sql\n", "%sql sqlite:///assignment2.db" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Problem 1: Matrix Manipulations\n", "------------------------\n", "\n", "Two random 3x3 ($N=3$) matrices have been provided in tables `A` and `B`, having the following schema:\n", "> * `i INT`: Row index\n", "> * `j INT`: Column index\n", "> * `val INT`: Cell value\n", "\n", "**Note: all of your answers below _must_ work for any _square_ matrix sizes, i.e. any value of $N$**.\n", "\n", "Note how the matrices are represented- why do we choose this format? Run the following queries to see the matrices in a nice format:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
A
7 , 5 , 8
10 , 7 , 7
2 , 0 , 5
" ], "text/plain": [ "[(u'7 , 5 , 8',), (u'10 , 7 , 7',), (u'2 , 0 , 5',)]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%sql SELECT group_concat(val, \" , \") AS \"A\" FROM A GROUP BY i;" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
B
9 , 6 , 10
7 , 6 , 9
1 , 1 , 7
" ], "text/plain": [ "[(u'9 , 6 , 10',), (u'7 , 6 , 9',), (u'1 , 1 , 7',)]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%sql SELECT group_concat(val, \" , \") AS \"B\" FROM B GROUP BY i;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (a): Elementwise multiplication [5 points]\n", "\n", "We want the _elementwise multiply_ of matrices A and B. That is,\n", "$(A\\cdot B)_{ij} = A_{ij}B_{ij}$ for all $i,j$.\n", "\n", "Write a _single SQL query_ that performs this operation (in the same format as $A$- output tuples should be of format `(i,j,val)` where `i` is row, `j` is column, and the output is ordered by row then column index)\n", "\n", "Write your query here:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ijval
0063
0130
0280
1070
1142
1263
202
210
2235
" ], "text/plain": [ "[(0, 0, 63),\n", " (0, 1, 30),\n", " (0, 2, 80),\n", " (1, 0, 70),\n", " (1, 1, 42),\n", " (1, 2, 63),\n", " (2, 0, 2),\n", " (2, 1, 0),\n", " (2, 2, 35)]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"\"\"\n", "Expected output below- don't re-evaluate this cell!\n", "\n", "NOTE: A valid answer must work for ALL inputs of the given type,\n", "not just this example. I.e. do not hardcode around this answer / etc!\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (b): Permutations [5 points]\n", "\n", "A _permutation_ is a mapping from a set of integers to itself, i.e. $\\pi:[n] \\rightarrow [n]$, where $[n]$ denotes the set $\\{0,\\ldots, n-1\\}$.\n", "\n", "We write\n", "$$\n", " \\pi([a_1, a_2, \\ldots, a_n]) \n", " = [a_{\\pi(1)},a_{\\pi(2)}, \\ldots a_{\\pi(n)} ]\n", "$$\n", "\n", "The provided table $c$ contains a permutation on $[3]$." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
indpi
01
12
20
" ], "text/plain": [ "[(0, 1), (1, 2), (2, 0)]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%sql SELECT * FROM c;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Write a _single SQL query_ that permutes the rows of matrix $A$ according to the permutation stored in $c$.\n", "\n", "$$\n", "(i,j,A_{ij}) \\rightarrow (i,j,A_{\\pi(i)j})\n", "$$\n", "\n", "For the example provided, this means a single-step cyclic upward shift, however your code needs to work for any input $A,c$ of the right dimensions.\n", "\n", "Write your query here:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ijval
0010
017
027
102
110
125
207
215
228
" ], "text/plain": [ "[(0, 0, 10),\n", " (0, 1, 7),\n", " (0, 2, 7),\n", " (1, 0, 2),\n", " (1, 1, 0),\n", " (1, 2, 5),\n", " (2, 0, 7),\n", " (2, 1, 5),\n", " (2, 2, 8)]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"\"\"\n", "Expected output below- don't re-evaluate this cell!\n", "\n", "NOTE: A valid answer must work for ALL inputs of the given type,\n", "not just this example. I.e. do not hardcode around this answer / etc!\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (c): Composability of permutations [8 points]\n", "\n", "A known property of permutations, is that they are closed under composition. This implies that applying two permutations in succession is equivalent to applying a different, single permutation.\n", "$$\n", " \\pi_2(\\pi_1([a_1, a_2, \\ldots, a_n]))\n", " = [a_{\\pi(1)},a_{\\pi(2)}, \\ldots a_{\\pi(n)} ]\n", "$$\n", "where $\\pi(i) = \\pi_2(\\pi_1(i))$.\n", "\n", "Write a _single SQL query_ that applies the permuation in table $c$ twice on the rows of matrix $A$.\n", "\n", "$$\n", "(i,j,A_{ij}) \\rightarrow (i,j,A_{\\pi(\\pi(i))j})\n", "$$\n", "\n", "For the example provided, this means a two-step cyclic upward shift, however your code needs to work for any input $A,c$ of the right dimensions.\n", "\n", "Write your query here:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ijval
002
010
025
107
115
128
2010
217
227
" ], "text/plain": [ "[(0, 0, 2),\n", " (0, 1, 0),\n", " (0, 2, 5),\n", " (1, 0, 7),\n", " (1, 1, 5),\n", " (1, 2, 8),\n", " (2, 0, 10),\n", " (2, 1, 7),\n", " (2, 2, 7)]" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"\"\"\n", "Expected output below- don't re-evaluate this cell!\n", "\n", "NOTE: A valid answer must work for ALL inputs of the given type,\n", "not just this example. I.e. do not hardcode around this answer / etc!\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (d): Local maximum [12 points]\n", "\n", "Consider the _local maximum_ matrix function, \n", "$MAX:\\mathbb{R}^{n,n} \\rightarrow \\mathbb{R}^{n,n}$:\n", "\n", "$$\n", " MAX(A)_{ij} = \\max \\{ A_{ij} \\textrm{ and cells up, down, left, right }\\}\n", "$$\n", "\n", "that is, if\n", "\n", "$$A=\\begin{bmatrix}a & b & c\\\\ d & e & f\\\\ g & h & i\\end{bmatrix}$$\n", "\n", "then\n", "\n", "$$\n", " MAX(A)_{00} = \\max \\{ a,b,d \\},\n", "$$\n", "\n", "$$\n", " MAX(A)_{01} = \\max \\{ a,d,g,e \\},\n", "$$\n", "\n", "and\n", "\n", "$$\n", " MAX(A)_{11} = \\max \\{ d,b,e,h,f \\}.\n", "$$\n", "\n", "Write a _single SQL query_ that computes the local maximum of matrix $A$.\n", "\n", "Write your query here:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ijval
0010
018
028
1010
1110
128
2010
217
227
" ], "text/plain": [ "[(0, 0, 10),\n", " (0, 1, 8),\n", " (0, 2, 8),\n", " (1, 0, 10),\n", " (1, 1, 10),\n", " (1, 2, 8),\n", " (2, 0, 10),\n", " (2, 1, 7),\n", " (2, 2, 7)]" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"\"\"\n", "Expected output below- don't re-evaluate this cell!\n", "\n", "NOTE: A valid answer must work for ALL inputs of the given type,\n", "not just this example. I.e. do not hardcode around this answer / etc!\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Problem 2: U.S. Sustainable Energy Sources\n", "----------------------------------------------\n", "\n", "We've prepared and loaded a [public dataset](https://catalog.data.gov/dataset/energy-generation-by-state-and-technology-2009-69f4f) from the US DOE (Department of Energy) of sustainable energy production in MWh (megawatt hours, i.e., 1000 [kilowatt hours](https://en.wikipedia.org/wiki/Kilowatt_hour)). This data is from 2009, the latest year available. The data includes each state, the region of the United States it is in, and its production in MWh of sustainable energy by source (solar, wind, hydroelectric, and nuclear). The table `energy` has the following schema:\n", "```\n", "TABLE energy (\n", " state varchar(30),\n", " region varchar(30),\n", " solar float,\n", " wind float,\n", " hydro float,\n", " nuclear float)\n", "```" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
stateregionsolarwindhydronuclear
AlabamaSoutheast0.00.011753493.3739716204.0
AlaskaAlaska0.03062.4421204550.3920.0
ArizonaWest13759.4459555.06348462.99230661851.0
" ], "text/plain": [ "[(u'Alabama', u'Southeast', 0.0, 0.0, 11753493.37, 39716204.0),\n", " (u'Alaska', u'Alaska', 0.0, 3062.442, 1204550.392, 0.0),\n", " (u'Arizona', u'West', 13759.445, 9555.0, 6348462.992, 30661851.0)]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%sql SELECT * FROM energy LIMIT 3;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (a): Regional Champions [10 points]\n", "\n", "Using a _single SQL query_, find all of the regions in the United States with a state in it that is the leading producer of one of the four types of energy (solar, wind, hydro, and nuclear), and return the counts of how many state winners they had in descending order. **Do not include any regions with no state winners.**\n", "\n", "Further requirements:\n", "* Use `GROUP BY`\n", "* Write the shortest possible SQL query to accomplish this\n", "* Return relation `(region, num_state_winners)`\n", "\n", "Write your query here:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
regionnum_state_winners
West2
Midwest1
Southeast1
" ], "text/plain": [ "[(u'West', 2), (u'Midwest', 1), (u'Southeast', 1)]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"\"\"\n", "Expected output below- don't re-evaluate this cell!\n", "\n", "NOTE: A valid answer must work for ALL inputs of the given type,\n", "not just this example. I.e. do not hardcode around this answer / etc!\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (b): Pareto Frontiers [10 points]\n", "\n", "Solar power and wind power [tend to be complementary](https://en.wikipedia.org/wiki/Wind_power#Variability), since it tends to be less windy when there are few clouds and the sun can best reach solar panels.\n", "\n", "Our goal in this part is to identify states that strike the best balance between solar and wind energy production. Here we define a state as \"best\" if it exists on the [Pareto frontier](https://en.wikipedia.org/wiki/Pareto_efficiency#Formal_representation) of solar and wind energy production. In other words, a state is Pareto optimal if no other state produces **both more solar and more wind energy**, and the Pareto frontier is the set of states that are Pareto optimal.\n", "\n", "Write a query that returns the entire Pareto frontier. Results should be triples of the form `(state, solar, wind)`, where `state` is the name of the state in the frotier, and `solar` and `wind` are its solar and wind energy production in MWh. Order the results in descending order by sum total of solar and wind energy production in MWh." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Write your query here:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
statesolarwind
Texas0.019367238.86
California611763.3875764637.309
" ], "text/plain": [ "[(u'Texas', 0.0, 19367238.86), (u'California', 611763.387, 5764637.309)]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"\"\"\n", "Expected output below- don't re-evaluate this cell!\n", "\n", "NOTE: A valid answer must work for ALL inputs of the given type,\n", "not just this example. I.e. do not hardcode around this answer / etc!\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Problem 3: Classification\n", "--------------------------------------------------\n", "\n", "SQL is a very [expressive language](http://wiki.postgresql.org/wiki/Mandelbrot_set) (some SQL extensions are known to be [Turing complete](http://stackoverflow.com/questions/900055/is-sql-or-even-tsql-turing-complete/7580013#7580013)). Here, we go through the steps of using it for a simple machine learning task: _binary classification_.\n", "\n", "We will use a subset of the [Iris](https://archive.ics.uci.edu/ml/datasets/Iris) dataset. The reduced dataset included here as table IRIS, is comprised of $100$ samples with features SepalLength, SepalWidth, PetalLength, PetalWidth and labels 0 (identifying the species Iris-setosa) and 1 (the species Iris-versicolor). Samples of the third class (Iris-virginica) present in the original dataset have been dropped for this exercise." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
iSepalLengthSepalWidthPetalLengthPetalWidthLabel
05.13.51.40.20
14.93.01.40.20
24.73.21.30.20
34.63.11.50.20
45.03.61.40.20
" ], "text/plain": [ "[(0, 5.1, 3.5, 1.4, 0.2, 0),\n", " (1, 4.9, 3.0, 1.4, 0.2, 0),\n", " (2, 4.7, 3.2, 1.3, 0.2, 0),\n", " (3, 4.6, 3.1, 1.5, 0.2, 0),\n", " (4, 5.0, 3.6, 1.4, 0.2, 0)]" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%sql SELECT * FROM IRIS LIMIT 5;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Model**\n", "\n", "We will use a simple _linear model_ to predict the label (species) given the four features included in the dataset.\n", "An unlabeled sample $x_i \\in \\mathbb{R}^4$ is a vector the four given feature values. For example, the first sample in our dataset is $x_0=[5.1, 3.5, 1.4, 0.2]^\\top$.\n", "This model, known as the [Perceptron](https://en.wikipedia.org/wiki/Perceptron), is also represented as a four-dimensional vector $w \\in \\mathbb{R}^4$. Given sample $x_i$ and model $w$ the perceptron makes the following prediction $\\hat{y}_i$ for the true label, $y_i$ of sample $x_i$:\n", "$$\n", " \\hat{y}_i={\\begin{cases}1&{\\text{if }} x_i^\\top w >0\\\\0&{\\text{otherwise}}\\end{cases}}\n", "$$\n", "\n", "A pre-trained model, $w$, is included in table MODEL." ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
jval
00.35260621
1-0.90142873
20.59729474
31.30194557
" ], "text/plain": [ "[(0, 0.35260621), (1, -0.90142873), (2, 0.59729474), (3, 1.30194557)]" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%sql SELECT * FROM MODEL;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (a): Matrix-vector multiplication [15 points]\n", "\n", "If we consider the _feature matrix_, $X$, whose $i$-th row is $x_i^\\top$, the prediction rule for all samples becomes:\n", "$$\n", " \\hat{y}= \\mathrm{step}(X w)\n", "$$\n", "where $Xw$ is a matrix-vector multiplication and\n", "$$\n", " \\mathrm{step}(z)_i={\\begin{cases}1&{\\text{if }} z_i >0\\\\0&{\\text{otherwise}}\\end{cases}}.\n", "$$\n", "The final product, $\\hat{y} \\in \\{0,1\\}^n$ is a vector with the predictions for all samples.\n", "\n", "The product of a matrix $X$ (having dimensions $n\\times m$) and a vector $w$ (having dimensions $m\\times 1$) is the vector $c$ (of dimension $n\\times 1$) having cell at row $i$ and column $j$ equal to:\n", "\n", "$$c_{i} = \\sum_{j=1}^m X_{ij}w_{j}$$\n", "\n", "In other words, to do matrix-vector multiplication, get each cell of the resulting vector $c$, $c_{i}$, by taking the _dot product_ of the $i$th row of $X$ and the $w$.\n", "\n", "We start by preprocessing IRIS to create the $X$ feature matrix, using the following schema:\n", "\n", "> * `i INT`: Row index\n", "> * `j INT`: Column index\n", "> * `val INT`: Cell value\n", "\n", "In order to streamline the work in this section we will make use of views. A view is a virtual table based on the output set of a SQL query. A view can be used just like a normal table; the only difference under the hood is that the DBMS re-evaluates the query used to generate it each time a view is queried by a user (thus the data is always up-to date!)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n", "Done.\n" ] }, { "data": { "text/plain": [ "[]" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%sql\n", "DROP VIEW IF EXISTS X;\n", "CREATE VIEW X AS\n", "SELECT i, 0 as j, SepalLength as val\n", "FROM IRIS\n", "UNION\n", "SELECT i, 1 as j, SepalWidth as val\n", "FROM IRIS\n", "UNION\n", "SELECT i, 2 as j, PetalLength as val\n", "FROM IRIS\n", "UNION\n", "SELECT i, 3 as j, PetalWidth as val\n", "FROM IRIS;" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ijval
005.1
013.5
021.4
030.2
104.9
" ], "text/plain": [ "[(0, 0, 5.1), (0, 1, 3.5), (0, 2, 1.4), (0, 3, 0.2), (1, 0, 4.9)]" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%sql SELECT * FROM X LIMIT 5;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Write a single SQL statement that implements the matrix-vector multiply $Xw$ between the provided view $X$ and model $w$ from table MODEL. Return the first 5 tuples as your answer.\n", "\n", "Write your query here:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ival
0-0.260107134
10.120085989
2-0.190450473
3-0.016109273
4-0.385510628
" ], "text/plain": [ "[(0, -0.26010713400000024),\n", " (1, 0.12008598900000017),\n", " (2, -0.19045047300000034),\n", " (3, -0.016109273000000146),\n", " (4, -0.38551062799999997)]" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"\"\"\n", "Expected output below- don't re-evaluate this cell!\n", "\n", "NOTE: A valid answer must work for ALL inputs of the given type,\n", "not just this example. I.e. do not hardcode around this answer / etc!\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (b): Predict labels [15 points]\n", "\n", "Now we can predict the labels using the following rule:\n", "$$\n", " \\hat{y}= \\mathrm{step}(X w)\n", "$$\n", "\n", "Create a view named 'PREDICTION' that will produce tuples of sample IDs and label predictions, i.e. $(i,\\hat{y}_i)$.\n", "\n", "**Not sure you got the previous question right?**\n", "The provided view 'ANSWER_P3a' with schema $(i,(Xw)_i)$ has the right answer. You can use it in your solution here for full credit in this question. **Warning**: Using this view in Part (a) is against the rules.\n", "\n", "Write your query in the following cell:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "To help you test, below is the expected output of a query for the first five records in the view:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "%sql SELECT * FROM PREDICTION LIMIT 5;" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ival
00
11
20
30
40
" ], "text/plain": [ "[(0, 0), (1, 1), (2, 0), (3, 0), (4, 0)]" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"\"\"\n", "Expected output below- don't re-evaluate this cell!\n", "\n", "NOTE: A valid answer must work for ALL inputs of the given type,\n", "not just this example. I.e. do not hardcode around this answer / etc!\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (c): Evaluate accuracy [20 points]\n", "\n", "Given the predicted labels $\\hat{y}_i$ and true labels $y_i$ we evaluate the predictive power of our model using _accuracy_: the fraction of labels our model got right.\n", "$$\n", " \\mathrm{accuracy} \n", " = \\frac{1}{n}\\sum_{i=1}^n \\mathbb{I}[y_i = \\hat{y}_i]\n", "$$\n", "\n", "Using the 'PREDICTION' view from the previous part should make for a simpler solution.\n", "\n", "**Not sure you got the previous question right?**\n", "The provided view 'ANSWER_P3b' with schema $(i,\\hat{y}_i)$ has the right answer. You can use it in your solution here for full credit in this question. **Warning**: Using this view in Part (b) is against the rules.\n", "\n", "Write your query here:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", "
accuracy
0.87
" ], "text/plain": [ "[(0.87,)]" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"\"\"\n", "Expected output below- don't re-evaluate this cell!\n", "\n", "NOTE: A valid answer must work for ALL inputs of the given type,\n", "not just this example. I.e. do not hardcode around this answer / etc!\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Our pre-trained classifer achieved a classification accuracy of 87%. If you don't think this is good enough, you are correct. This is not an optimally trained model. Try the bonus question to see how this classification performance can be improved!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Bonus Problem 1: Classification, Pt. II\n", "\n", "A simple procedure from training the model $w$ given labeled data, is as follows.\n", "$$\n", " w' = w + 0.0001 \\sum_{i=1}^n (y_i-\\hat{y_i})x_i\n", "$$\n", "This kind of optimization algorithm is typically applied iteratively, but here we will just run a single step. \n", "\n", "Run a SQL statement that computes the new model value, $w'$, based on the original model $w$ in MODEL and the samples $x_i$ in IRIS. \n", "\n", "**Using answers from previous parts.**\n", "As before, you should feel free to use the provided views 'ANSWER_P3a' and 'ANSWER_P3b' described in parts (b) and (c) in your solution for full credit in this question. **Warning**: Using these views in Parts (a) and (b) respectively is against the rules.\n", "\n", "Write your answer here:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
jval
00.34618621
1-0.90557873
20.59523474
31.30153557
" ], "text/plain": [ "[(0, 0.34618621), (1, -0.90557873), (2, 0.5952347400000001), (3, 1.30153557)]" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"\"\"\n", "Expected output below- don't re-evaluate this cell!\n", "\n", "NOTE: A valid answer must work for ALL inputs of the given type,\n", "not just this example. I.e. do not hardcode around this answer / etc!\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We have a new model now. If you perform the evaluation process for this new model, you should find that accuracy has increased to 90%. Not bad for a single step of the algorithm! Further iterations will improve this performance more." ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.13" } }, "nbformat": 4, "nbformat_minor": 1 }