nn_universal_approximation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is my pytorch hello world. \n",
    "\n",
    "In addition to get familiar with the basic usage, I also want to demonstrate the universal approximation property of neural nets, which I believe is one of the core reason why deep learing is working so well.\n",
    "\n",
    "Consider the characteristic function for two interected circles on the 2-d plane (then the problem naturally becomes a classification problem), we will see that a nn with 2 hidden layer can aprroximate it pretty well. \n",
    "\n",
    "We remark here that actually only one layer is good enough since we know that even the one layer nn also has the universal approximation property."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy\n",
    "import torch\n",
    "import torch.nn as nn\n",
    "import torch.nn.functional as F\n",
    "import torch.optim as optim\n",
    "import matplotlib.pyplot as plt\n",
    "from torch.autograd import Variable\n",
    "from random import shuffle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The objective function below equals one within two intersected circles, first one centered at $(0,0)$ with a radius of $0.6$ and the second one entered at $(0.5,0.5)$ with a radius of $0.5$.\n",
    "\n",
    "Notice that the region is non-convex."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def target(x,y):\n",
    "    if (x-0.0)*(x-0.0) + (y-0.0)*(y-0.0) < 0.36 or (x-0.5)*(x-0.5) + (y-0.5)*(y-0.5) < 0.25:\n",
    "        return 1.0\n",
    "    else:\n",
    "        return 0.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define our neural net with 2 hidden layer. It takes a 2-d input and map to the first layer with 40 hidden units, then two the second hidden layer with 40 nodes and finally map to a scalar output.\n",
    "\n",
    "Also define the optimization method (Adam) and the loss function (cross entropy)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Net(nn.Module):\n",
    "\n",
    "    def __init__(self):\n",
    "        super(Net, self).__init__()     \n",
    "        self.fc1 = nn.Linear(2, 40) \n",
    "        self.fc2 = nn.Linear(40, 40)\n",
    "        self.fc3 = nn.Linear(40, 1)\n",
    "        self.out_act = nn.Sigmoid()\n",
    "\n",
    "    def forward(self, x):\n",
    "        x = F.relu(self.fc1(x))\n",
    "        x = F.relu(self.fc2(x))\n",
    "        x = self.fc3(x)\n",
    "        x = self.out_act(x)\n",
    "        return x\n",
    "\n",
    "net = Net()\n",
    "opt = optim.Adam(net.parameters(), lr=0.001, betas=(0.9, 0.999))\n",
    "lose_func = nn.BCELoss()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We sample data uniformly from a square $[-1.5,1.5]\\times [-1.5,1.5]$, label them and do a shuffle.\n",
    "\n",
    "One interesting here is that if you don't shuffle the input, the performance is prerry bad."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = []\n",
    "y = []\n",
    "for i in numpy.linspace(-1.5,1.5,num = 200):\n",
    "    for j in numpy.linspace(-1.5,1.5,num = 200):\n",
    "        x = x + [[i,j]]\n",
    "\n",
    "# try to comment out this and see what happens\n",
    "shuffle(x)\n",
    "\n",
    "for i in x:\n",
    "    y = y + [[target(i[0],i[1])]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A function used to visualize the data, x is a list of 2-d points and y is the list of label associated with x."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw(x,y, threshold = 1.0):\n",
    "    blue_x = []\n",
    "    blue_y = []\n",
    "    red_x = []\n",
    "    red_y = []\n",
    "    for i in range(len(x)):\n",
    "        if y[i][0] >= threshold:\n",
    "            blue_x = blue_x + [x[i][0]]\n",
    "            blue_y = blue_y + [x[i][1]]\n",
    "        else:\n",
    "            red_x = red_x + [x[i][0]]\n",
    "            red_y = red_y + [x[i][1]]\n",
    "      \n",
    "    [fig, ax] = plt.subplots()\n",
    "    plt.scatter(blue_x, blue_y, color='b')\n",
    "    plt.scatter(red_x, red_y, color='r')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the original input data, equals 1 inside the two circles and 0 otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD4CAYAAADvsV2wAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAV5ElEQVR4nO3dbYxc1X3H8e9v1xikBCXEuwTCgxdalIZUTZOOUBKkijYkBVThPEpsbZ4jxxBSS32FgpRKkZImfdM6BHCc1AmErSFFIjgNKYE8iL4oKeMIwlMojmMHyyhem4qEKMXY8++LuWOGZWZ3Zu+de2fm/D7SaO/MnL3n3Lm7vz37v3fuKCIwM7PxN1H1AMzMrBwOfDOzRDjwzcwS4cA3M0uEA9/MLBErqh7AYqampmJmZqbqYZiZjYwdO3YciIjpTs8NdeDPzMxQr9erHoaZ2ciQtKfbcy7pmJklwoFvZpYIB76ZWSIc+GZmiXDgm5klwoFvZpYIB76ZWSIKCXxJWyXtl/R4l+fPk/SCpEey22eK6LeruTmYmQEJJiebXxfeJiYWf7z9+V6We7n10n6pcfXaptut9Xos93Xpdez9vk79fu9y91+//Ze5L3tp32n/FfVzWNTj/b6uS21fv30OYr8O8vev07pnZpo5VrCi3nj1DeDLwG2LtPnPiPjrgvrrbm4OrroKDh1q3m80Orfr9jkArcfbn+9luRe9tF9qXL226ab1eiz3dVlMntep3+9d7v7rt/9e2vfbJs+2dtp/Rf0cFvV4tzbL3b5+++y3/17WP8jfv07r3rMHrryyubx27dLr7VEhM/yIeBB4voh15bZx4ythb2Y2ql5+uZlnBSqzhv8eSY9K+p6kt3drJGm9pLqk+vz8fP+9HDyYZ4xmZsOj4DwrK/B/CqyOiHcANwLf7tYwIrZERC0iatPTHa//Y2Zmy1BK4EfEbyLixWz5XuAYSVNl9G1mZk2lBL6kkyQpWz4n69e1FzOzEhVylo6kbcB5wJSkvcDfA8cARMRm4KPANZIOA78HLono93C7mZnlUUjgR8TsEs9/meZpm2ZmVhG/09bMLBEOfDOzRDjwzcwS4cA3M0uEA9/MLBEOfDOzRDjwzcwS4cA3M0uEA9/MLBEOfDOzRDjwzcwS4cA3M0uEA9/MLBEOfDOzRDjwzcwS4cA3M0uEA9/MLBEOfDOzRDjwzcwS4cA3M0uEA9/MLBEOfDOzRDjwzcwSUUjgS9oqab+kx7s8L0lfkrRT0s8kvauIfs3MrHdFzfC/AVywyPMXAmdlt/XALQX1a2ZmPSok8CPiQeD5RZqsAW6LpoeAN0o6uYi+zcysN2XV8E8Bnm27vzd77DUkrZdUl1Sfn58vZXBmZikoK/DV4bHo1DAitkRELSJq09PTAx6WmVk6ygr8vcBpbfdPBfaV1LeZmVFe4G8HLsvO1nk38EJEPFdS32ZJirZb41XL6vJ4tzavLNtoK+q0zG3AfwFvlbRX0tWSNkjakDW5F9gF7AS+ClxbRL9m9upgP4JoALtZzVpuZ4JggmAy+9pcbnR5vFub5vJabmeeVa/qz0aLIoZ3t9VqtajX6/19kzodLjAbH81Z9wSiwa9Yzaf5HNtYW/o4Zpnj89zA6ewhEBPZnwD/Bhasz4yWtCMiap2e8zttzUZAa0Y9zyrWcjsrOMIkwRnsriTsAbaxljPYzSTBii7/BdhwceCbDamFIT9BcCIHKgv4XmxjLSdygAmCm7iGRtUDsldx4JsNkVEM+W4+xc2s43Z2s/roAWGrlgPfbEg0gJu4ZqRDfqH2sk97uceq4cA3q1hrRr+O2/kUN1c9nIFplXtc56+OA9+sQq1Z/bjM6HvhOn91HPhmFUhlVr+UVp3fpZ5yOPDNSpbirH4xnUo9NhgOfLOSeFa/uFbw/5bXVT2UseXANyuBZ/W928BX+D+OqXoYY2lF1QMwG3dHmOBSbnPQ96j1Om1iI1Mc9KUaCuQZvtkABTjsl8HlncFw4JsNSNAs4zjsl28DX+ElVlY9jLHhko7ZALiMUwyXd4rlGb5ZwVzGKZbLO8Vx4JsV7Le83mE/AD57Jz+XdMwK9BIr2cDmqocxllp/ROdY59LOMnmGb1aQAK5kq2f3A7SNtRxgVdXDGFkOfLOCHGCVw74EG9nkyy8skwPfrABBM4hs8PxHdfkc+GYFCOQgKpHLOsvjwDfLKYCb2VD1MJKykU0+Y2cZfJaO2SKWqhUfYZLNrPfVL0vmM3aWxzN8S1rrY/Ya6OjyEUQD2M3qox8k3u12DIcd9hVxCa1/hQS+pAskPS1pp6TrOzx/haR5SY9kt48X0a9Zv6LtNs+qo4E+SeNoiK+gwSTBGex2qNhYyV3SkTQJ3AS8H9gLPCxpe0Q8uaDpnRFxXd7+zHrVKsc0mEA0+BWr+TSfc4hbsoqY4Z8D7IyIXRFxCLgDWFPAes361izPvLocs4IjnrGbUUzgnwI823Z/b/bYQh+R9DNJd0k6rdvKJK2XVJdUn5+fL2B4Nu4WhrzD3ayzIgK/00HyhSc3fAeYiYg/AR4Abu22sojYEhG1iKhNT08XMDwbV+11eIe82dKKCPy9QPuM/VRgX3uDiDgYES9ld78K/FkB/VqCFh5w9WfEmvWuiMB/GDhL0hmSVgKXANvbG0g6ue3uxcBTBfRriWl9EPgE4aA3W4bcZ+lExGFJ1wH3AZPA1oh4QtJngXpEbAf+VtLFwGHgeeCKvP1aGlozep9hYwvNMlf1EEaOIob3unO1Wi3q9Xp/3yS/724cBM3rpWxkk0PeXmOWOb7OVRzLoaqHMnh9ZrSkHRFR6/ScL61gQ6f14d9+B6t1s4mNaYR9wXxpBRsa7QdjHfa2mCkOVj2EkeQZvg0Fz+rNBs+Bb5U7wgSXcptr9dYTH6xdPpd0rFIBDnvr2SxzfJPLfEnkZfIM3yrTAG7mGoe99WSWObZyJZM0qh7KyHLgWyVcxrF+beYTHMfLVQ9jpLmkY6VzGcf6Ncscx/O7qocx8hz4VqrW2TgOe+tVs25/qev2BXBJx0rjMo71q/WO2sklP13YeuEZvpXCZRxbjs1s8DtqC+TAt1L8ltc77K1ns8yxnymO58WqhzJWXNKxgXuJlWxgc9XDsBFxI9dyLbd4NjoAfk1toAK4kq2e3duSWrP6TzrsB8YzfBuoA6xy2NuiZpljExuZ4qDPxBkwB74NTAAb2VT1MGyIuXxTLr/ONlCe3VsnLt9UwzN8G5gDrKp6CDaEPKuvjl9zG4iXWOlyjh3VmtE3kGf1FfIM3wrnM3OsxQdkh4v/0NpAOOzTNcscv2SGI4g51jHtsB8anuGbWW6zzPF5buB09iBwwA8pB74Vzgdrx197qabFIT/8CinpSLpA0tOSdkq6vsPzx0q6M3v+J5JmiujXho/PvR8/7SWaw0zSWFCq8Yx+dOQOfEmTwE3AhcDZwKyksxc0uxr434j4Q+CfgC/m7deGl+v346N1eeIZ9jABWdw74EdVETP8c4CdEbErIg4BdwBrFrRZA9yaLd8FvE+Sf2bMhtwmNvryxGOkiMA/BXi27f7e7LGObSLiMPACdC70SlovqS6pPj8/X8DwzGy52mv0NvqKCPxOM/WFH0/TS5vmgxFbIqIWEbXp6encgzMzs6YiAn8vcFrb/VOBfd3aSFoBvAF4voC+zcysR0UE/sPAWZLOkLQSuATYvqDNduDybPmjwA8jwh9SOaZmmat6CFYA78fxkzvws5r8dcB9wFPAtyLiCUmflXRx1uxfgFWSdgJ/B7zm1E0bD6J5oM9G3yY2+mycMaNhnmjXarWo1+v9fZNP/qlcABOdD9HYCGkgB/4w6DOjJe2IiFqn53wtHTOzRDjwbSBc/x1t3n/jyYFvhROwlSsdGiNqljm2cqXLOWPIgW8DcRwv++DtiNrERo7j5aqHYQPgwLeB8bs0R5P32/hy4NtAuawzWry/xpsD3wbG5+SPHp97P94c+DZQUxz0rHFEzDLncs6Yc+DbQPmMndHQuu69Z/fjzYFvA3ccL7OZT1Q9DFvEZjb4uvcJcOBbKY7nd57lD6lZ5jieF6sehpXAgW+lEPBNLnPoD5lZ5vgml7qUkwgHvpVmkga3s44bubbqoRhwI9dyO+uY9IXukuHAt1JNAJ/kFs/0KzbLHJ/kFgdAYry/rXTN8s6lDv2KNMs4l7mMkyAHvlVikmDO5Z3S3ci1zLGOSRpVD8Uq4MC3ygiXd8rUKuN4Zp8uB75VymfvlMNlHAMHvg2BSRou7wyQyzjW4sC3odAq7+xnyrP9gswyx36mXMaxoxz4NjQETHPQ5+oXoDWrn+agw96OcuDb0Gmdq+/Zfv88q7fFOPBtKLVm+3Os4wjil8w4/LuYZY5fMsMR5Fm9LSpX4Et6k6T7JT2TfT2hS7sjkh7Jbtvz9GlpEc0f0hn2uNTTQevyCDPsYQIc9LaovDP864EfRMRZwA+y+538PiL+NLtdnLNPS1Sr1NNASZd7WmWbBvLlEawveX9W1gC3Zsu3Ah/MuT6zRYlXl3tSCv5W0LeXbTyjt37kDfw3R8RzANnXE7u0O05SXdJDkhb9oyBpfda2Pj8/n3N4Ns7ag78xpnX+9tm86/OW15KBL+kBSY93uK3po5/TI6IG/A3wz5L+oFvDiNgSEbWIqE1PT/fRhaWqNdOdYc9YHOTtFvIOestrycCPiPMj4o873O4Bfi3pZIDs6/4u69iXfd0F/Bh4Z2FbYNam/SBva+Z/mMmh/SPQfobNYSYd8jZQeUs624HLs+XLgXsWNpB0gqRjs+Up4FzgyZz9mi2pFZiTNF7zR6CqA7/ts/dWuLfOsGnGvUPeBidv4H8BeL+kZ4D3Z/eRVJP0tazN24C6pEeBHwFfiAgHvlVCvPbAbwNxhImjIZznP4JOM/bm+tVx9u5wtzIpYng/3qxWq0W9Xu/vm+RfIStOLFjW0WWh7Nn2ZXCIW8H6zGhJO7Jjpq+xopABmY0pdV2Ojstmw8zv2TAzS4QD38wsEQ58M7NEOPDNzBLhwDczS4QD38wsEQ58M7NEOPDNzBLhwDczS4QD38wsEQ58M7NEOPDNzBLhwDczS4QD38wsEQ58M7NEOPDNzBLhwDczS4QD38wsEQ58M7NEOPDNzBLhwDczS4QD38wsEQ58M7NE5Ap8SR+T9ISkhqTaIu0ukPS0pJ2Srs/Tp5mZLU/eGf7jwIeBB7s1kDQJ3ARcCJwNzEo6O2e/ZmbWpxV5vjkingKQtFizc4CdEbEra3sHsAZ4Mk/fZmbWnzJq+KcAz7bd35s91pGk9ZLqkurz8/MDH5yZWSqWnOFLegA4qcNTN0TEPT300Wn6H90aR8QWYAtArVbr2s7MzPqzZOBHxPk5+9gLnNZ2/1RgX851mplZn8oo6TwMnCXpDEkrgUuA7SX0a2ZmbfKelvkhSXuB9wDflXRf9vhbJN0LEBGHgeuA+4CngG9FxBP5hm1mZv3Ke5bO3cDdHR7fB1zUdv9e4N48fZmZWT5+p62ZWSIc+GZmiXDgm5klwoFvZpYIB76ZWSIc+GZmiXDgm5klwoFvZpYIB76ZWSIc+GZmiXDgm5klwoFvZpYIB76ZWSIc+GZmiXDgm5klwoFvZpYIB76ZWSIc+GZmiXDgm5klwoFvZpYIB76ZWSIc+GZmiXDgm5klIlfgS/qYpCckNSTVFmm3W9Jjkh6RVM/Tp5mZLc+KnN//OPBh4Cs9tP2LiDiQsz8zM1umXIEfEU8BSCpmNGZmNjBl1fAD+L6kHZLWL9ZQ0npJdUn1+fn5koZnZjb+lpzhS3oAOKnDUzdExD099nNuROyTdCJwv6SfR8SDnRpGxBZgC0CtVose1/+KVavg4MG+v83MbOisWlXo6pYM/Ig4P28nEbEv+7pf0t3AOUDHwM9t0ya46io4dGggqzczK8UxxzTzrEADL+lIep2k41vLwAdoHuwdjLVrYetWWL26eX+ih01sPwbRat/+WLdjFHkeH/T6l+q32+uSZ1xFrSfP463t6mX7qnq8iDbt21fmGLspan/3s/+q2r48bZbKl9by6tXw9a8386xAuQ7aSvoQcCMwDXxX0iMR8VeS3gJ8LSIuAt4M3J0d2F0B/GtE/EfOcS9u7drCXygzs1GX9yydu4G7Ozy+D7goW94FvCNPP2Zmlp/faWtmlggHvplZIhz4ZmaJcOCbmSXCgW9mlggHvplZIhTR/9ULyiJpHtiTYxVTwLhcoXNctsXbMVy8HcMn77asjojpTk8MdeDnJakeEV2v0z9KxmVbvB3DxdsxfAa5LS7pmJklwoFvZpaIcQ/8LVUPoEDjsi3ejuHi7Rg+A9uWsa7hm5nZK8Z9hm9mZhkHvplZIsYq8CV9TNITkhqSup7WJGm3pMckPSKpXuYYe9XHtlwg6WlJOyVdX+YYeyHpTZLul/RM9vWELu2OZPvjEUnbyx5nN0u9vpKOlXRn9vxPJM2UP8ql9bAdV0iab9sHH69inEuRtFXSfkkdP0RJTV/KtvNnkt5V9hh70cN2nCfphbb98ZlCOo6IsbkBbwPeCvwYqC3SbjcwVfV4824LMAn8AjgTWAk8Cpxd9dgXjPEfgeuz5euBL3Zp92LVY13O6wtcC2zOli8B7qx63MvcjiuAL1c91h625c+BdwGPd3n+IuB7gIB3Az+peszL3I7zgH8vut+xmuFHxFMR8XTV4yhCj9tyDrAzInZFxCHgDmDN4EfXlzXArdnyrcAHKxxLv3p5fdu37y7gfVK/n583cKPwc9KTiHgQeH6RJmuA26LpIeCNkk4uZ3S962E7BmKsAr8PAXxf0g5J66seTA6nAM+23d+bPTZM3hwRzwFkX0/s0u44SXVJD0kalj8Kvby+R9tExGHgBWBVKaPrXa8/Jx/JyiB3STqtnKEVbhR+J3r1HkmPSvqepLcXscJcH3FYBUkPACd1eOqGiLinx9WcGxH7JJ0I3C/p59lf3FIVsC2dZpKln2e72Hb0sZrTs31yJvBDSY9FxC+KGeGy9fL6DsU+WEIvY/wOsC0iXpK0geZ/LX858JEVbxT2Ry9+SvOaOC9Kugj4NnBW3pWOXOBHxPkFrGNf9nW/pLtp/stbeuAXsC17gfaZ2KnAvpzr7Nti2yHp15JOjojnsn+t93dZR2uf7JL0Y+CdNOvOVerl9W212StpBfAGKvhXfQlLbkdEHGy7+1XgiyWMaxCG4ncir4j4TdvyvZJuljQVEbkuEJdcSUfS6yQd31oGPgB0PFI+Ah4GzpJ0hqSVNA8aDs0ZLpntwOXZ8uXAa/5zkXSCpGOz5SngXODJ0kbYXS+vb/v2fRT4YWRH3YbIktuxoM59MfBUieMr0nbgsuxsnXcDL7RKiqNE0kmtY0GSzqGZ1QcX/64eVH20uuAj3x+i+Rf+JeDXwH3Z428B7s2Wz6R5lsKjwBM0yyeVj30525Ldvwj4H5qz4aHbFpr17B8Az2Rf35Q9XgO+li2/F3gs2yePAVdXPe7FXl/gs8DF2fJxwL8BO4H/Bs6seszL3I5/yH4fHgV+BPxR1WPush3bgOeAl7Pfj6uBDcCG7HkBN2Xb+RiLnK035NtxXdv+eAh4bxH9+tIKZmaJSK6kY2aWKge+mVkiHPhmZolw4JuZJcKBb2aWCAe+mVkiHPhmZon4fzNRXnKghrlqAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "draw(x,y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we start to train the model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = torch.tensor(x)\n",
    "y = torch.tensor(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "def train_epoch(model, opt, criterion, batch_size=50):\n",
    "    losses = []\n",
    "    for beg_i in range(0, x.size(0), batch_size):\n",
    "        x_batch = x[beg_i:beg_i + batch_size, :]\n",
    "        y_batch = y[beg_i:beg_i + batch_size, :]\n",
    "        \n",
    "        opt.zero_grad()\n",
    "        y_hat = net(x_batch)\n",
    "        loss = criterion(y_hat, y_batch)\n",
    "        loss.backward()\n",
    "        opt.step()        \n",
    "        losses.append(loss.data.numpy())\n",
    "    return losses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "e_losses = []\n",
    "num_epochs = 100\n",
    "for e in range(num_epochs):\n",
    "    train_epoch(net, opt, lose_func)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the final result. I was pretty astonished when I saw the result for the first time. Before that, I didn't really believe in deep learning since it was really a black box to me. The result here changed my mind."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD4CAYAAADvsV2wAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAWPUlEQVR4nO3dbYxc1X3H8e/P6wckYhHiXQcCxAstakOkpg0rlASpok3SElThPBCJrc2DncgYA7XUV0iREilvmvRN6zhgx0lNeNgaUiSC05ASyIOoVJEyjiA8heKAEZZRvDYVgTSx8e6/L+aOGZuZ3Zm9d+6dmfP7SFdz586Ze86Zmf3NmXPvzCoiMDOz4beo6gaYmVk5HPhmZolw4JuZJcKBb2aWCAe+mVkiFlfdgLmMjo7G+Ph41c0wMxsYe/bsORQRY61u6+vAHx8fp1arVd0MM7OBIemldrd5SsfMLBEOfDOzRDjwzcwS4cA3M0uEA9/MLBEOfDOzRDjwzcwSUUjgS9op6aCkp9rcfomk1yQ9ni1fLKLetqamYHwcJBgZqV+evCxa1Hp789K4b/M+mu/XyT66rbNdmU7qXWifuq2/k7Z3+zh1e9/5thdVf5nPZSfl53tNdrIs9DEt8jXRTf+6rbMXz2sRr8lO+tRYHx+v51jBivri1beBrwN3zFHmPyPibwqqr72pKVi/Ho4erV+fnW1drpP/A9C4b/M+mu/X7f8S6KR8uzKd1LvQPnVbfzvt2tiL+863vaj6OynfbZk8fZ3vNdmJhT6mnW5vV2ah/eu2zm7r72T/RbwmO+lTY/2ll2Dduvr6mjWt77cAhYzwI+IR4NUi9pXb5s1vhb2Z2aB68816nhWozDn8D0t6QtIPJL2/XSFJGyTVJNWmp6e7r+Xw4TxtNDPrHwXnWVmB/3NgVUR8ANgKfLddwYjYERETETExNtby93/MzGwBSgn8iPhNRLyRrT8ALJE0WkbdZmZWV0rgSzpDkrL1i7J6PfdiZlaiQs7SkbQLuAQYlbQf+BKwBCAitgNXANdLOgb8DrgyotvD7WZmlkchgR8Rk/Pc/nXqp22amVlF/E1bM7NEOPDNzBLhwDczS4QD38wsEQ58M7NEOPDNzBLhwDczS4QD38wsEQ58M7NEOPDNzBLhwDczS4QD38wsEQ58M7NEOPDNzBLhwDczS4QD38wsEQ58M7NEOPDNzBLhwDczS4QD38wsEQ58M7NEOPDNzBLhwDczS0QhgS9pp6SDkp5qc7skfU3SXkm/kPTBIuo1M7POFTXC/zZw6Ry3fwI4P1s2ANsKqtfMzDpUSOBHxCPAq3MUWQ3cEXWPAu+UdGYRdZuZWWfKmsM/C3i56fr+bNvbSNogqSapNj09XUrjzMxSUFbgq8W2aFUwInZExERETIyNjfW4WWZm6Sgr8PcD5zRdPxs4UFLdZmZGeYG/G7g6O1vnQ8BrEfFKSXWbmRmwuIidSNoFXAKMStoPfAlYAhAR24EHgMuAvcD/AeuKqNfMzDpXSOBHxOQ8twdwQxF1mVl7ccK6ULblxPW3Dqo1r89mZQ6zgmUcYTlvHN9Xq4NwNnj8TVuzARPAbHYZwAyLmAX2sYo13MUigkUEI8y2WY+W64uZZYRgJYc4jdePb1/DXexjFbPATPa20fKMC+t7DnyzAdAI2WlWsIa7TgrqGUYIzmUfu1hTeN27WMO57GMke1NovAlMs+J4u/wGMBgc+GZ96uSQX5SNvnsR6t3axRpWcuiETwGNNwDrXw58sz7SzyE/l8YbwMkjf+svDnyzPhHALVw/MCHfSvPI/xauZ7bqBtkJHPhmFWse0d/ErVU3pzA3cStrmw74esRfPQe+WYUao/pBHdHPp/mAr+f5q+fAN6vAsI7q59KY7vFUT3UK+eKVmXXndU5lJYeqbkYlbuJW/ouL2cJmRjnsL3WVyCN8s5IdYSkb+UbVzaiUR/vVcOCblaQxjbOOnUM5X78QjQO7M46iUnhKx6wkKU/jzKXx5ncb61nG0YpbM9z8tmpWgt+zJPlpnLnsYg3r2OmzeHrMgW/WQ41pnPXc5mmceTTP6zv0e8OBb9Yjswz3Ofa9chO3+pz9HnHgm/XADGJtQufYF60x2n+dd1TdlKHiwDcrWABXcadH9QXYyHaOsLTqZgwNn6VjVqDGTyU47IvReBzv5GpGfMZ+bg58s4LMII/se6DxeE6x1t/KzclTOmYFmMXTOL3kx7UYDnyznAK41dM4PTfruMrNj6DZAqX4i5dV2sZ1Pk0zJ8/hm82jVci8zjvYyHaP6kvUeFO9gW2ey1+gQkb4ki6V9JykvZJubnH7tZKmJT2eLZ8vol6zIjX+D+ssrf+3bPNyGq877CvgT1L55B7hSxoBbgE+DuwHHpO0OyKeOanoPRFxY976zIrSPHI/xAo2s8UhbkOtiBH+RcDeiHghIo4CdwOrC9ivWWEaI/YZFjEL7GPVCSN3//yBpaCIwD8LeLnp+v5s28k+I+kXku6VdE4B9Zq1VJ+WUctpmcXMMEJwLvsc8APqECuqbsLAKiLwWx0/Ofk41/eA8Yj4E+Bh4Pa2O5M2SKpJqk1PTxfQPEvByeE+wqxH70NqM1t8ts4CFRH4+4HmEfvZwIHmAhFxOCKOZFe/CVzYbmcRsSMiJiJiYmxsrIDm2bBr/Cqlwz0Nfn4XrojAfww4X9K5kpYCVwK7mwtIOrPp6uXAswXUawlrnE2zj1X+VcrETDJVdRMGVu6zdCLimKQbgQeBEWBnRDwt6ctALSJ2A38n6XLgGPAqcG3eei1Ngc+oSd0WNvs8/AVSRP/Ohk1MTEStVuvuTvJLYdg0XqEOeoP6Afmk/sq7zGhJeyJiotVt/qat9bVZ6r9T4ykbs/z8WzrWlxpn3Hh+3pp5/j4fj/Ct73hUb61MMsVO1qU1nVMwj/Ctb3hUb3PZwmZO4c2qmzHQPMK3vtD414AOemtnlMNVN2HgeYRvlfJvypuVxyN8q9TrnMpKDlXdDOtzPlhbDI/wrTK/Zwkb+UbVzbA+N8kUd3KVD9YWwIFvpWtM46znNn+JyubUODNnxD+XVghP6VjpPI1jndrOdT4zp0Ae4VupjrDU0zjWkUmmWM5vq27GUHHgW2lmWMQ6dnoax+ZVn7e/2vP2BXPgWykCuIo7HPY2r61sYoq1jDBbdVOGjgPfSvE6pzrsbU6TTHGQUW5gm0f2PeKDttZzPv3S5jLJFFvYzCiHHfQ95sC3ngrw6ZfW1lY2sYltnmooiR9n66lDrHDY29s0T984hMrjEb71TACb2VJ1M6zPbGWT5+kr4jdX6ymP7g3eGtHPIod9hTzCN7Oe8QHZ/uIRvvXMIVZU3QSrwCRTvMg4M4gp1jLmsO8bHuFbTxxhqefvE+T5+f7mEb4VLsA/oZAYf2lqMDjwrScc9sOvMXUz66mbgVFI4Eu6VNJzkvZKurnF7csk3ZPd/jNJ40XUa2bVaPzezTgvIXDQD4jcgS9pBLgF+ARwATAp6YKTin0O+N+I+EPgn4Cv5q3X+pcP1g4nn1o5+IoY4V8E7I2IFyLiKHA3sPqkMquB27P1e4GPSvLrZQj5y1bDaZIpbufa49M2/uMdTEUE/lnAy03X92fbWpaJiGPAa9B6GChpg6SapNr09HQBzbOyef5++GxhM0s4VnUzLKciAr/Vm/3J/4CykzL1jRE7ImIiIibGxsZyN87M8tnKJkY5XHUzrABFBP5+4Jym62cDB9qVkbQYOA14tYC6rQ9tZVPVTbCC+Lz64VJE4D8GnC/pXElLgSuB3SeV2Q1ck61fAfw4Ivxv6IeQgOvZXnUzrCCb2O6wHyK5Az+bk78ReBB4FvhORDwt6cuSLs+K/QuwQtJe4O+Bt526acNjEcEkU1U3w3KaZAq1nnm1AaV+HmhPTExErVbr7k4++acvHGGpv2074A4yypjn7qvXZUZL2hMRE61u8zdtrSeWcZQtbK66GbZAk0z5QO0QcuBbzzgwBtMkU9zGes/dDyEHvpmdYAubWcbRqpthPeDAt57ywdvB409mw8uBbz0j8Dz+gPEb9HBz4FtPebQ4WLaw2XP3Q8yBbz3nUeNg8Jk5w8+Bbz0l4DbWO/T73CRT7GSdR/dDzoFvPbeMo2xnY9XNsDls5zpO4c2qm2E95sC3UiznDY/y+9QkUyznt1U3w0rgwLdSCLiTqx36fWaSKe7kak/lJMKBb6UZYZa7WOufT+4TjW/UjjBbdVOsJA58K9Ui4Aa2eaTfB7Zznb9RmxgHvpWuPr1zlUO/Qp63T5MD3yoxQnh6pyKet0+XA98q4+md8nnePm0OfKuUz94p13Y2et4+YQ58q9wIs+xknUO/hyaZ4iCjLOeNqptiFXLgW184hTfZznVVN2MobWUTU6xljMOet0+cA9/6xnJ+y0FGPdIvSGNUfwPbHPQGOPCtjwgY47DP3imAR/XWigPf+k7j7J1Z5BF/lzyqt7k48K0vibdG/FOsdfDPYZIpXmScGeRRvc0pV+BLepekhyQ9n12e3qbcjKTHs2V3njotPZ7qaW8rm7iLtYzzEovAQW9zyjvCvxn4UUScD/wou97K7yLiT7Pl8px1WqI81VPXmLaZRdzANn9Mt47lfa2sBm7P1m8HPplzf2ZzSnmqpxH0zdM2HtFbN/IG/rsj4hWA7HJlm3KnSKpJelSS3xSsEM3BP4t4kfGhC//m0bzn5y2veQNf0sOSnmqxrO6invdGxATwt8A/S/qDOerbkL051Kanp7uowlLVGOmO8xJTrGUG8SaLmRnQN4F2Ie+gt9wiYsEL8BxwZrZ+JvBcB/f5NnBFJ/u/8MILo2vgxcsJy2y2vMiqmOSuqptzwjLJXfEiq2IG4hiLjre18oZ56Z+l6wik1i5T807p7AauydavAe4/uYCk0yUty9ZHgYuBZ3LWa9axVp8Aqhr5N4/eGyP4xhk2I8x6JG89lTfwvwJ8XNLzwMez60iakPStrMz7gJqkJ4CfAF+JCAe+VULUX/SN8G8E7wyLjq8XdSC4+fz4Y9n+T56icbhbmZRNs/SliYmJqNVq3d1J/hOy/OL4pVB2LXgroE/c3nodHOhWgC4zWtKeqB8zfZvFhTTIbMjo+GXr8D5xe+t1s37j72yYmSXCgW9mlggHvplZIhz4ZmaJcOCbmSXCgW9mlggHvplZIhz4ZmaJcOCbmSXCgW9mlggHvplZIhz4ZmaJcOCbmSXCgW9mlggHvplZIhz4ZmaJcOCbmSXCgW9mlggHvplZIhz4ZmaJcOCbmSXCgW9mlggHvplZInIFvqTPSnpa0qykiTnKXSrpOUl7Jd2cp04zM1uYvCP8p4BPA4+0KyBpBLgF+ARwATAp6YKc9ZqZWZcW57lzRDwLIGmuYhcBeyPihazs3cBq4Jk8dZuZWXfKmMM/C3i56fr+bFtLkjZIqkmqTU9P97xxZmapmHeEL+lh4IwWN30hIu7voI5Ww/9oVzgidgA7ACYmJtqWMzOz7swb+BHxsZx17AfOabp+NnAg5z7NzKxLZUzpPAacL+lcSUuBK4HdJdRrZmZN8p6W+SlJ+4EPA9+X9GC2/T2SHgCIiGPAjcCDwLPAdyLi6XzNNjOzbuU9S+c+4L4W2w8AlzVdfwB4IE9dZmaWj79pa2aWCAe+mVkiHPhmZolw4JuZJcKBb2aWCAe+mVkiHPhmZolw4JuZJcKBb2aWCAe+mVkiHPhmZolw4JuZJcKBb2aWCAe+mVkiHPhmZolw4JuZJcKBb2aWCAe+mVkiHPhmZolw4JuZJcKBb2aWCAe+mVkiHPhmZonIFfiSPivpaUmzkibmKLdP0pOSHpdUy1OnmZktzOKc938K+DTwjQ7K/kVEHMpZn5mZLVCuwI+IZwEkFdMaMzPrmbLm8AP4oaQ9kjbMVVDSBkk1SbXp6emSmmdmNvzmHeFLehg4o8VNX4iI+zus5+KIOCBpJfCQpF9GxCOtCkbEDmAHwMTERHS4/7esWAGHD3d9NzOzvrNiRaG7mzfwI+JjeSuJiAPZ5UFJ9wEXAS0DP7ctW2D9ejh6tCe7NzMrxZIl9TwrUM+ndCSdKml5Yx34K+oHe3tjzRrYuRNWrapfX9RBF9sdg2jct90+2t2vk+3t1ova/3z1dtKnbuspaj95tvfyOStqexFlmvtXZhvbKer57ub5q6p/3ZZZSJ9WrYLbbqvnWYFyHbSV9ClgKzAGfF/S4xHx15LeA3wrIi4D3g3clx3YXQz8a0T8R852z23NmsIfKDOzQZf3LJ37gPtabD8AXJatvwB8IE89ZmaWn79pa2aWCAe+mVkiHPhmZolw4JuZJcKBb2aWCAe+mVkiFNH9rxeURdI08FKOXYwCw/ILncPSF/ejv7gf/SdvX1ZFxFirG/o68POSVIuItr/TP0iGpS/uR39xP/pPL/viKR0zs0Q48M3MEjHsgb+j6gYUaFj64n70F/ej//SsL0M9h29mZm8Z9hG+mZllHPhmZokYqsCX9FlJT0ualdT2tCZJ+yQ9KelxSbUy29ipLvpyqaTnJO2VdHOZbeyEpHdJekjS89nl6W3KzWTPx+OSdpfdznbme3wlLZN0T3b7zySNl9/K+XXQj2slTTc9B5+vop3zkbRT0kFJLf+Jkuq+lvXzF5I+WHYbO9FBPy6R9FrT8/HFQiqOiKFZgPcBfwT8FJiYo9w+YLTq9ubtCzAC/Ao4D1gKPAFcUHXbT2rjPwI3Z+s3A19tU+6Nqtu6kMcX2ARsz9avBO6put0L7Me1wNerbmsHfflz4IPAU21uvwz4ASDgQ8DPqm7zAvtxCfDvRdc7VCP8iHg2Ip6ruh1F6LAvFwF7I+KFiDgK3A2s7n3rurIauD1bvx34ZIVt6VYnj29z/+4FPip1+//zem4QXicdiYhHgFfnKLIauCPqHgXeKenMclrXuQ760RNDFfhdCOCHkvZI2lB1Y3I4C3i56fr+bFs/eXdEvAKQXa5sU+4USTVJj0rqlzeFTh7f42Ui4hjwGrCilNZ1rtPXyWeyaZB7JZ1TTtMKNwh/E536sKQnJP1A0vuL2GGuf3FYBUkPA2e0uOkLEXF/h7u5OCIOSFoJPCTpl9k7bqkK6EurkWTp59nO1Y8udvPe7Dk5D/ixpCcj4lfFtHDBOnl8++I5mEcnbfwesCsijkjaSP1Ty1/2vGXFG4TnoxM/p/6bOG9Iugz4LnB+3p0OXOBHxMcK2MeB7PKgpPuof+QtPfAL6Mt+oHkkdjZwIOc+uzZXPyT9WtKZEfFK9tH6YJt9NJ6TFyT9FPgz6vPOVerk8W2U2S9pMXAaFXxUn8e8/YiIw01Xvwl8tYR29UJf/E3kFRG/aVp/QNKtkkYjItcPxCU3pSPpVEnLG+vAXwEtj5QPgMeA8yWdK2kp9YOGfXOGS2Y3cE22fg3wtk8ukk6XtCxbHwUuBp4prYXtdfL4NvfvCuDHkR116yPz9uOkee7LgWdLbF+RdgNXZ2frfAh4rTGlOEgkndE4FiTpIupZfXjue3Wg6qPVBR/5/hT1d/gjwK+BB7Pt7wEeyNbPo36WwhPA09SnTypv+0L6kl2/DPgf6qPhvusL9fnsHwHPZ5fvyrZPAN/K1j8CPJk9J08Cn6u63XM9vsCXgcuz9VOAfwP2Av8NnFd1mxfYj3/I/h6eAH4C/HHVbW7Tj13AK8Cb2d/H54CNwMbsdgG3ZP18kjnO1uvzftzY9Hw8CnykiHr90wpmZolIbkrHzCxVDnwzs0Q48M3MEuHANzNLhAPfzCwRDnwzs0Q48M3MEvH/Gl5fvu2/DigAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "draw(x.tolist(), net(x).tolist(), threshold = 0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The decision boundary given by this nn should be linear, basically some polygon, which can be easily seen if we decrease the number of hidden units. So what we are doing here is basically try to approximate any region (don't need to be convex) using polygon and we know it is feasible from real analysis.\n",
    "\n",
    "Then some question to ask here are: \n",
    "    1. Given any polygon P, can we find a nn whose decision boundary is exactly P, if so, how to construct it.\n",
    "    2. Given a network structure, give an upper bound of the number of edges of its decision boundary."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}