{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img style=\"float: left; width: 260px;\" src=\"images/testcloud.png\">\n",
    "***\n",
    "# <font color=\"grey\">    Lecture 6 - Machine Learning</font>\n",
    "***\n",
    "$\\newcommand{\\vct}[1]{\\mathbf{#1}}$\n",
    "$\\newcommand{\\mtx}[1]{\\mathbf{#1}}$\n",
    "$\\newcommand{\\e}{\\varepsilon}$\n",
    "$\\newcommand{\\norm}[1]{\\|#1\\|}$\n",
    "$\\newcommand{\\minimize}{\\text{minimize}\\quad}$\n",
    "$\\newcommand{\\maximize}{\\text{maximize}\\quad}$\n",
    "$\\newcommand{\\subjto}{\\quad\\text{subject to}\\quad}$\n",
    "$\\newcommand{\\R}{\\mathbb{R}}$\n",
    "$\\newcommand{\\trans}{T}$\n",
    "$\\newcommand{\\ip}[2]{\\langle {#1}, {#2} \\rangle}$\n",
    "$\\newcommand{\\zerovct}{\\vct{0}}$\n",
    "$\\newcommand{\\diff}[1]{\\mathrm{d}{#1}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this lecture we will embark on one of the most important modern applications of convex optimization: **machine learning**. The goal of machine learning is to develop methods to automatically *learn* a function\n",
    "\n",
    "\\begin{equation*}\n",
    " h\\colon \\mathcal{X}\\to \\mathcal{Y},\n",
    "\\end{equation*}\n",
    "\n",
    "where $\\mathcal{X}$ is a space of *inputs* or *features*, and $\\mathcal{Y}$ consists of *outputs* or *responses*. The input space $\\mathcal{X}$ is usually an $\\R^n$, though the inputs could represent anything such as images, texts, emails, genome sequences, or networks, financial time series, or demographic data. The output could be either **quantitative** values, such as a temperature or the amount of some substance in the body, or **qualitative** or **categorical**, such as {YES, NO} or $\\{0,1,2,3,4,5,6,7,8,9\\}$ (for recognising spam or handwritten digits, respectively). The first type of problem is usually called **regression**, while the latter is called **classification**. Machine learning techniques underlie much of modern technology, from car electronics to online product recommendation systems and search engines."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## <font color=\"grey\">Supervised Learning</font>\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example** (Handwriting recognition)\n",
    "Given a dataset of pixel matrices, each representing a grey-scale image, with associated \\textbf{labels} telling us for each image the number it represents, the task is to use this to train a computer program to recognise new numbers. Such classification tasks are often carried out using **deep neural networks**. \n",
    "\n",
    "![Letter recognition](images/letters.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example** (Linear regression)\n",
    "Recall from Lecture 1 the problem of finding a function of the form\n",
    "\n",
    "\\begin{equation*}\n",
    "  Y = \\beta_0+\\beta_1X_1+\\cdots +\\beta_pX_p.\n",
    "\\end{equation*}\n",
    "\n",
    "Given a set of input-output pairs $(\\vct{x}_i,y_i)$, arranged in a matrix $\\mtx{X}$ and a vector $\\vct{y}$, we saw that we could *guess* the correct $\\vct{\\beta} = (\\beta_0,\\beta_1,\\dots, \\beta_p)^{\\trans}$ by solving the *least-squares* optimization problem\n",
    "\n",
    "\\begin{equation*}\n",
    "  \\mathop{\\minimize}_{\\vct{\\beta}} \\norm{\\mtx{X}\\vct{\\beta}-\\vct{y}}_2^2.\n",
    "\\end{equation*}\n",
    "\n",
    "By now, we know how to solve this problem using gradient descent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example** In text classification, the task is to decide to which of a given set of categories a given text belongs. The training data consists of a *bag of words*: this is a large sparse matrix, whose\n",
    "columns represent words and the rows represent articles, with the $(i,j)$-th entry containing the number of times word $j$ is contained in text $i$. \n",
    "\n",
    "\n",
    "|           | Rooney | Boris |\n",
    "|---------- |--------|-------|\n",
    "| Article 1 |      5 |     0 |\n",
    "| Article 2 |      1 |     7 |\n",
    "\n",
    "For example, in the above set we would classify the first article as \"Sports\" and the second one as \"Politics\". One such training dataset is the [Reuters Corpus Volume I (RCV1)](http://www.daviddlewis.com/resources/testcollections/rcv1/), an archive of over 800,000 categorised newswire stories.\n",
    "\n",
    "A typical binary classifier for such a problem would be a **linear classifier** of the form\n",
    "\n",
    "\\begin{equation*}\n",
    "  h(\\vct{x}) = \\vct{w}^{\\trans}\\vct{x}-\\tau,\n",
    "\\end{equation*} \n",
    "\n",
    "with $\\vct{w}\\in \\R^n$ and $\\tau\\in \\R$. Given a text, represented as a row of the dataset $\\vct{x}$, it is classified into one of two classes $\\{+1,-1\\}$, depending on whether $h(\\vct{x})>0$ or $h(\\vct{x})<0$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose we have the training data $\\{\\vct{x}_i,y_i\\}_{1\\leq i\\leq m}$ and we found a candidate function $h\\colon \\mathcal{X}\\to \\mathcal{Y}$. How do we assess if this is a good fit? One usually assigns to the problem a **loss function** $\\ell\\colon \\mathcal{Y}\\times \\mathcal{Y}\\to \\R_+$ that measures the mismatch of a prediction. One would then aim to find a function $h$ among a set of candidates that minimizes the loss when applying the function to the training data:\n",
    "\n",
    "\\begin{equation*}\n",
    "  \\mathop{\\minimize}_{h} \\ \\frac{1}{m} \\sum_{i=1}^m \\ell(h(\\vct{x}_i,y_i).\n",
    "\\end{equation*}\n",
    "\n",
    "The form of the loss function depends on the problem at hand, but two typical candidates are the **square error** for regression problems,\n",
    "\n",
    "\\begin{equation*}\n",
    "  \\ell(h(\\vct{x}),y) = (h(\\vct{x})-y)^2,\n",
    "\\end{equation*}\n",
    "\n",
    "and the indicator loss function\n",
    "\n",
    "\\begin{equation*}\n",
    "  \\mathbf{1}\\{h(\\vct{x})\\neq y\\},\n",
    "\\end{equation*}\n",
    "\n",
    "where $\\mathbf{1}\\{A\\}$ is the indication function, which takes the value $1$ if $A$ is true, and $0$ else. As this function is not continuous, in practice one often encounters the *log loss* function,\n",
    "\n",
    "\\begin{equation*}\n",
    "  \\ell(h(\\vct{x}),y) = \\log\\left(1+e^{-h(\\vct{x})y} \\right).\n",
    "\\end{equation*}\n",
    "\n",
    "Note that if $h(\\vct{x})$ and $\\vct{y}$ have the same sign (corresponding to a match), then the value of this function will be close to zero. \n",
    "\n",
    "Suppose we have a binary classification task at hand, with $\\mathcal{Y}=\\{-1,1\\}$. We could *learn* the following function from our data:\n",
    "\n",
    "\\begin{equation*}\n",
    "  h(\\vct{x}) = \\begin{cases}\n",
    "    y_i & \\text{ if } \\vct{x}=\\vct{x}_i,\\\\\n",
    "    1 & \\text{ otherwise.}\n",
    "  \\end{cases}\n",
    "\\end{equation*}\n",
    "\n",
    "The **empirical misclassification risk** in for this problem is then $0$,\n",
    "\n",
    "\\begin{equation*}\n",
    "  R(h) = \\frac{1}{m} \\sum_{i=1}^m \\mathbf{1}\\{h(\\vct{x}_i\\neq y_i\\} = 0.\n",
    "\\end{equation*}\n",
    "\n",
    "Nevertheless, this is not a good classifier: it will not perform very well outside of the training set. This is an example of **overfitting**: when the function is adapted too closely to the seen data. To remedy this, one often (randomly) splits the available data into a **training set** and a **test set**. The training set is used to find the function $h$, while the test set is for testing how good it is (in practise, one often adds a validation set, used to tune some parameters of the problem)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example** In the linear regression problem with the quadratic loss function, we end up with the minimization problem\n",
    "\n",
    "\\begin{equation*}\n",
    "  \\mathop{\\minimize}_{\\vct{\\beta}} \\frac{1}{n} \\sum_{i=1}^n (\\vct{x}_i^{\\trans}\\vct{\\beta}-y_i)^2 =\\frac{1}{n}\\norm{\\mtx{X}\\vct{\\beta}-\\vct{y}}_2^2.\n",
    "\\end{equation*}\n",
    "\n",
    "This is precisely the problem encountered in Lecture 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example** In the example of classifying a text into two classes using a linear classifier, we can look at the problem\n",
    "\n",
    "\\begin{equation*}\n",
    " \\mathop{\\minimize}_{\\vct{w}, \\tau} \\frac{1}{n}\\sum_{i=1}^m \\mathbf{1}\\{\\vct{w}^{\\trans}\\vct{x}_i-\\tau \\neq y_i\\}.\n",
    "\\end{equation*}\n",
    "\n",
    "Since this function is not smooth or even continuous, we can work with the log-loss function described above,\n",
    "\n",
    "\\begin{equation*}\n",
    "\\mathop{\\minimize}_{\\vct{w}, \\tau} \\frac{1}{n} \\sum_{i=1}^m \\ell(\\vct{w}^{\\trans}\\vct{x}_i-\\tau, y_i).\n",
    "\\end{equation*}\n",
    "\n",
    "This function can, in principle, be minimized using gradient descent or Newton's method. \n",
    "\n",
    "In the following example, we use this classifier to separate an artificial data set of 20 points. 10 points are generated as normal (Gaussian) distributed vectors in $\\R^2$, with mean $(2,2)^{\\trans}$ and variance $0.25$, while the other 10 points are generated with mean $(0,0)^{\\trans}$ and the same variance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import numpy.random as rnd\n",
    "import numpy.linalg as la\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAEACAYAAABVtcpZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAFpBJREFUeJzt3X+MXeV95/H3d8Imahwtm6Stkxkax5qQjdJsRZOVcZSV\nfFHlxs4fkJWqbSKs1Ky0iyJwqmbTDeoymhnNP2XFHxugFcsqrUMhCqusmhASVGYFdxFZ2UWACwWc\nksnEJTPgdkPcNiaqKPPdP+4dexjfO56Zc2bOufe8X9LI98fDOV+ea8/nnvM8zzmRmUiSmmmk6gIk\nSdUxBCSpwQwBSWowQ0CSGswQkKQGMwQkqcEKh0BEvCUijkfEUxHxTERM9ml3W0S8EBEnIuKKovuV\nJBV3SdENZOY/RsRVmflqRLwJ+G5EPJiZf77cJiIOAuOZeXlEXAncCewtum9JUjGlnA7KzFe7D99C\nJ1hWr0C7Bri72/Y4cGlE7Cxj35KkzSslBCJiJCKeAl4GZjPz8VVNxoAXVzxf6L4mSapQWUcCS5n5\nq8BlwJUR8cEytitJ2lqFxwRWysy/j4hHgAPAcyveWgB+acXzy7qvXSAivJiRJG1QZsZm/rsyZgf9\nfERc2n38c8B+4OSqZvcDn+m22QucyczT/baZmbX+mZycrLwG67RO67TO5Z8iyjgSeDfwlYgYoRMq\n92XmdyLi+s7v87yr+/wTEfF94CxwXQn7lSQVVMYU0WeAD/d4/b+ven5j0X1JksrliuFNaLVaVZew\nLtZZLussl3XWQxQ9n1S2iMi61SRJdRYRZFUDw5KkwWUISFKDGQKS1GCGgCQ1mCEgSQ1mCEhSgxkC\nktRghoAkNVipVxGVVJ75+VNMTBxlYWGJsbERZmYOs3v3rqrLEsP12bhiWKqh+flT7N9/O3Nz08AO\n4Czj45PMzh4Z2F82w6KOn40rhqUhMzFxdMUvGYAdzM1NMzFxtMKqBMP32RgCUg0tLCxx/pfMsh0s\nLi5VUY5WGLbPxhCQamhsbITOrTdWOsvoqP9kqzZsn81gVi0NuZmZw4yPT3L+l03nvPPMzOHKalLH\nsH02DgxLNbU8A2VxcYnR0cGcgTJMs2hWqttnU2Rg2BCQtCXqOItmWDk7SFLtDNssmmFVOAQi4rKI\neDgino2IZyLicz3a7IuIMxHxZPfn5qL7lVRvwzaLZliVsWL4n4DPZ+aJiHgb8EREPJSZJ1e1ezQz\nry5hf5IGwPlZNCuDYHBn0Qyrwp9GZr6cmSe6j38KPA+M9Wi6qfNVkgbTsM2iGValDgxHxHuBNvCh\nbiAsv74P+F/Aj4AF4Hcz87k+23BgWBoSdZtFM6xqMTuoeyqoDcxk5jd7vLeUma9GxEHgS5n5/j7b\nMQQkaQOKhEApVxGNiEuArwN/sjoA4NxpouXHD0bEH0bEOzLzlV7bm5qaOve41WrRarXKKFPSABrW\ntQZFtNtt2u12Kdsq5UggIu4G/l9mfr7P+zsz83T38R7gf2bme/u09UhAEuBag/Wq9HRQRHwMeBR4\nBsjuz+8Bu4DMzLsi4gbgs8BrwM+A38nM4322ZwhIAuDQoWnuvfcLrJ5hdO21t3LPPZNVlVU7lZ4O\nyszvAm+6SJs/AP6g6L4kNYtrDbaeE3Yl1dawXbGzjuxJSbXlWoOt5wXkJNWaaw0urhbrBMpiCEjS\nxngVUUnSphgCktRghoAkNZghIEkNZghIUoMZApLUYIaAJDWYISBJDWYISFKDGQKS1GCGgCQ1mCEg\nSQ1mCEhSgxkCktRghoAkNVjhEIiIyyLi4Yh4NiKeiYjP9Wl3W0S8EBEnIuKKovuVJBVX+EbzwD8B\nn8/MExHxNuCJiHgoM08uN4iIg8B4Zl4eEVcCdwJ7S9i3JKmAwkcCmflyZp7oPv4p8DwwtqrZNcDd\n3TbHgUsjYmfRfUuSiil1TCAi3gtcARxf9dYY8OKK5wtcGBSSpG1WxukgALqngr4O/Hb3iGDTpqam\nzj1utVq0Wq1CtUnSMGm327Tb7VK2VcqN5iPiEuAB4MHM/FKP9+8EHsnM+7rPTwL7MvN0j7beaF4a\nIPPzp5iYOMrCwhJjYyPMzBxm9+5dVZfVKEVuNF/WkcAfAc/1CoCu+4EbgPsiYi9wplcASBos8/On\n2L//dubmpoEdwFmOHZtkdvaIQTAgCh8JRMTHgEeBZ4Ds/vwesAvIzLyr2+4O4ABwFrguM5/ssz2P\nBKQBcejQNPfe+wU6AbDsLNdeeyv33DNZVVmNU+mRQGZ+F3jTOtrdWHRfkuplYWGJNwYAwA4WF5eq\nKEeb4IphSZs2NjZC5+B+pbOMjvqrZVD4SUnatJmZw4yPT3I+CM4yPj7JzMzhymrSxpQyO6hMjglI\ng2V5dtDi4hKjo84OqkKRMQFDQJIGXJEQ8HSQJDWYISBJDWYISFKDGQKS1GCGgCQ1mCEgSQ1mCEhS\ngxkCktRghoAkNZghIEkNZghIUoMZApLUYIaAJDWYISBJDWYISFKDlRICEfHliDgdEU/3eX9fRJyJ\niCe7PzeXsV9JzTA/f4pDh6a56qpJDh2aZn7+VNUlDY3CN5rv+mPgduDuNdo8mplXl7Q/SQ0xP3+K\n/ftvZ25ums5N7c9y7Ngks7NHvINZCUo5EsjMx4CfXKTZpu56I+mNmvateGLi6IoAANjB3Nw0ExNH\nK6xqeJR1JLAeH42IE8AC8LuZ+dw27lsaCk38VrywsMT5AFi2g8XFpSrKGTrbFQJPAO/JzFcj4iDw\nDeD9/RpPTU2de9xqtWi1WltdnzQQ+n8rvpV77pmssrQtMzY2ApzljUFwltHR5s5rabfbtNvtUrZV\n2o3mI2IX8K3M/JV1tJ0HPpKZr/R4zxvNS31cddUk7fZ0z9cffvjC14dBr6Of8fHhPvrZqCI3mi/z\nSCDoc94/InZm5unu4z10wueCAJC0tiZ+K969exezs0eYmLiVxcUlRkdHmJkxAMpSypFARHwVaAHv\nBE4Dk8CbgczMuyLiBuCzwGvAz4DfyczjfbblkYDUh9+K1UuRI4HSTgeVxRCQ1jY/f4qJiaMrvhUf\nNgAazhCQpAary5iAJDXa8lHawsISY2ODcZTmkYAklaDK8ZoiRwLDO6VAkrbRoK5sNgQkqQSDurLZ\nEJCkEpxfw7FS/ddw1Ls6SRoQMzOHGR+f5HwQdMYEZmYOV1bTejgwLEklqWoNh+sEJKnBnB0kSdoU\nF4tJGniDuEirLjwdJGmgeVE9TwdJarBBXaRVF4aApIE2qIu06sIQkDTQBnWRVl3YS5IG2qAu0qoL\nB4YlDbym32jHxWKS1GDODpIkbUopIRARX46I0xHx9BptbouIFyLiRERcUcZ+JUnFlHUk8MfAx/u9\nGREHgfHMvBy4HrizpP1KkgooJQQy8zHgJ2s0uQa4u9v2OHBpROwsY9+SpM3brjGBMeDFFc8Xuq9J\nkipUywvITU1NnXvcarVotVqV1SJJddNut2m326Vsq7QpohGxC/hWZv5Kj/fuBB7JzPu6z08C+zLz\ndI+2ThGVpA2oyxTR6P70cj/wGYCI2Auc6RUAkqTtVcrpoIj4KtAC3hkRfw1MAm8GMjPvyszvRMQn\nIuL7dNZ2X1fGfiVJxbhiWLVzan6eoxMTLC0sMDI2xuGZGXbt3l11WVJtedkIDY1T8/Pcvn8/03Nz\n3duDwOT4OEdmZw0CqY+6jAlIhR2dmDgXANC5Svz03BxHJyaqLEslmp8/xaFD01x11SSHDk0zP3+q\n6pIarZZTRNVcSwsLPW4PAkuLi1WUo5L1uhXksWPNuhVk3XgkoFoZGRvrcXsQGBkdraIclcxbQdaP\nIaBaOTwzw+T4+Irbg3TGBA7PzFRZlkrirSDrx9NBqpVdu3dzZHaWWycmWFpcZGR0lCPODhoa528F\nuTIIvBVklZwdJGnb9BoTGB93TKAop4hKGhhNvxXkVjAEJKnBXCcgSdoUQ0CSGswQkKQGMwQkqcEM\nAUlqMENAkhrMEJCkBjMEJKnBDAFJajBDQJIarJQQiIgDEXEyIv4qIr7Y4/19EXEmIp7s/txcxn4l\nScUUvpR0RIwAdwC/BiwCj0fENzPz5Kqmj2bm1UX3J0kqTxlHAnuAFzLzVGa+BnwNuKZHu01d3EiS\ntHXKCIEx4MUVz3/UfW21j0bEiYj4dkR8sIT9SpIK2q47iz0BvCczX42Ig8A3gPf3azw1NXXucavV\notVqbXV9kjQw2u027Xa7lG0Vvp9AROwFpjLzQPf5TUBm5i1r/DfzwEcy85Ue73k/AUnagKrvJ/A4\n8L6I2BURbwY+Bdy/qsCdKx7voRM+FwSAJGl7FT4dlJmvR8SNwEN0QuXLmfl8RFzfeTvvAn4jIj4L\nvAb8DPjNovuVJBXn7SUlacBVfTpIkjSgDAFJajBDQJIazBCQpAYzBCSpwbZrxbBUO6fm5zk6McHS\nwgIjY2Mcnplh1+7dVZclbSuniKqRTs3Pc/v+/UzPzbEDOAtMjo9zZHbWINDAcYqotEFHJybOBQDA\nDmB6bo6jExNVliVtO0NAjbS0sHAuAJbtAJYWF6soR6qMIaBGGhkb4+yq184CI6OjVZQjVcYQUCMd\nnplhcnz8XBAsjwkcnpmpsixp2zkwrMY6NztocZGR0VFnB2lgFRkYNgRUOqdeStvLEFBtOPVS2n5O\nEVVtOPVSGiyGgErl1EtpsBgCKpVTL6XBYgioVE69lAaLA8MqnVMvpe1V+eygiDgA/DfO32j+lh5t\nbgMO0vlyeDgzT/TZliEgSRtQ6eygiBgB7gA+Dvwy8OmI+MCqNgeB8cy8HLgeuLPofiVJxZUxJrAH\neCEzT2Xma8DXgGtWtbkGuBsgM48Dl0bEzhL2LUkqoIybyowBL654/iM6wbBWm4Xua6dL2L+2gKt+\npWao5Z3Fpqamzj1utVq0Wq3Kamminqt+jx1z1a9UE+12m3a7Xcq2Cg8MR8ReYCozD3Sf3wTkysHh\niLgTeCQz7+s+Pwnsy8wLjgQcGK7e9KFDfOHee9+w6OsscOu11zJ5zz1VlSWpjyIDw2UcCTwOvC8i\ndgEvAZ8CPr2qzf3ADcB93dA40ysAtP16nfZx1a/UHIVDIDNfj4gbgYc4P0X0+Yi4vvN23pWZ34mI\nT0TE9+l8qbyu6H5VXL/TPq9/6EOchQuOBFz1Kw0fF4s1WL/TPlNXX00++6xXApUGRNWngzSg+p32\nees//AP/fnaWW1es+j3i7CBpKBkCDbZ8sbdep3127d7tILDUAF5ArsG82JskxwQazou9SYOv8gvI\nlckQkKSN8faSkqRNMQQkqcEMAUlqMENAkhrMEJCkBjMEJKnBDAFJajAvG6GB4J3OpK3hYjHVXs9L\nXntVU+kcF4tpqB2dmDgXANC54N303BxHJyaqLEsaCoaAas87nUlbxxBQ7S1f8nol73QmlcMQUO15\nyWtp6xQaGI6ItwP3AbuAHwL/LjP/rke7HwJ/BywBr2XmnjW26cCwLuAlr6X+KruUdETcAvw4M/9r\nRHwReHtm3tSj3Q+Aj2TmT9axTUNAkjagyhA4CezLzNMR8S6gnZkf6NFuHvjXmfnjdWxzQyHg/HFJ\nTVdlCLySme/o93zF6z8AzgCvA3dl5v9YY5vrDgHnj2sj/MKgYbWlIRARs8DOlS8BCdwMHF0VAj/O\nzHf22Ma7M/OliPgFYBa4MTMf67O/dYfA9KFDfOHeey+4Ufqt117rTdL1Bn5h0DArEgIXvWxEZu5f\nY8enI2LnitNBf9NnGy91//zbiPhTYA/QMwQApqamzj1utVq0Wq2e7Zw/rvXqt+Ds1okJvzBo4LTb\nbdrtdinbKnrtoPuBw8AtwG8B31zdICLeCoxk5k8jYgfw68D0WhtdGQJrWZ4/vvpIwPnjWs0vDBom\nq78cT0+v+St1TUXXCdwC7I+I7wG/Bvw+dE7/RMQD3TY7gcci4ingGPCtzHyo4H4B549r/VxwJvU2\n8BeQG4b54w5Ybj3HBDTMKpsdtBWatk5gq345GSwXGoYvDFIvhsAA24oZTn7rlZrFS0kPsK0YsPTS\ny5LWyxCo2FYMWDoTRtJ6GQIV24oZTs6EkbRejgnUQNkDlo4JSM3iwLAu4EwYqTkMAUlqMGcHSZI2\nxRCQpAYzBCSpwQwBSWowQ0CSGswQkKQGMwQkqcEMAUlqMENAkhrMEJCkBjMEJKnBCoVARPxGRPxl\nRLweER9eo92BiDgZEX8VEV8ssk9JUnmKHgk8A/xb4P/0axARI8AdwMeBXwY+HREfKLjfSrXb7apL\nWBfrLJd1lss666FQCGTm9zLzBWCtq9ftAV7IzFOZ+RrwNeCaIvut2qD8pbDOcllnuayzHrZjTGAM\neHHF8x91X5MkVeySizWIiFlg58qXgAT+S2Z+a6sKkyRtvVJuKhMRjwD/KTOf7PHeXmAqMw90n98E\nZGbe0mdb3lFGkjZoszeVueiRwAb0K+Bx4H0RsQt4CfgU8Ol+G9ns/4gkaeOKThH9ZES8COwFHoiI\nB7uvvzsiHgDIzNeBG4GHgGeBr2Xm88XKliSVoXb3GJYkbZ9KVwwPymKziHh7RDwUEd+LiD+LiEv7\ntPthRPxFRDwVEX++jfVdtH8i4raIeCEiTkTEFdtV26oa1qwzIvZFxJmIeLL7c3MFNX45Ik5HxNNr\ntKlDX65ZZ0368rKIeDgino2IZyLic33aVdqf66mzJv35log43v398kxETPZpt7H+zMzKfoB/CVwO\nPAx8uE+bEeD7wC7gnwEngA9sc523AP+5+/iLwO/3afcD4O3bXNtF+wc4CHy7+/hK4FgFn/V66twH\n3L/dta2q4d8AVwBP93m/8r5cZ5116Mt3AVd0H78N+F5N/26up87K+7Nbx1u7f74JOAbsKdqflR4J\n5OAsNrsG+Er38VeAT/ZpF2z/0dV6+uca4G6AzDwOXBoRO9le6/0cK50YkJmPAT9Zo0kd+nI9dUL1\nfflyZp7oPv4p8DwXrhGqvD/XWSdU3J8Amflq9+Fb6EzsWX0+f8P9OQgXkKvDYrNfzMzT0PkLA/xi\nn3YJzEbE4xHxH7aptvX0z+o2Cz3abLX1fo4f7R7GfjsiPrg9pW1IHfpyvWrTlxHxXjpHLsdXvVWr\n/lyjTqhBf0bESEQ8BbwMzGbm46uabLg/y5wi2tOgLDZbo85e5/76jaZ/LDNfiohfoBMGz3e/sWl9\nngDek5mvRsRB4BvA+yuuaVDVpi8j4m3A14Hf7n7TrqWL1FmL/szMJeBXI+KfA9+IiA9m5nNFtrnl\nIZCZ+wtuYgF4z4rnl3VfK9VadXYH4HZm5umIeBfwN3228VL3z7+NiD+lcwpkq0NgPf2zAPzSRdps\ntYvWufIfXmY+GBF/GBHvyMxXtqnG9ahDX15UXfoyIi6h84v1TzLzmz2a1KI/L1ZnXfpzRQ1/H51F\nugeAlSGw4f6s0+mgiy42i4g301lsdv/2lQXd/R3uPv4t4IK/JBHx1u43CSJiB/DrwF9uQ23r6Z/7\ngc90a9sLnFk+vbWNLlrnynOXEbGHzhTmKv6RBf3/PtahL5f1rbNGfflHwHOZ+aU+79elP9essw79\nGRE/vzwzMSJ+DtgPnFzVbOP9WfFI9yfpnL/6GZ3VxA92X3838MCKdgfojNi/ANxUQZ3vAP53t4aH\ngH+xuk5gN50ZL0/RucT2ttXZq3+A64H/uKLNHXRm5/wFfWZiVV0ncAOd4HwK+L/AlRXU+FVgEfhH\n4K+B62ral2vWWZO+/Bjw+op/F092/w7Uqj/XU2dN+vNfdWs7ATxN55R64X/rLhaTpAar0+kgSdI2\nMwQkqcEMAUlqMENAkhrMEJCkBjMEJKnBDAFJajBDQJIa7P8DZEUzA9PsP8wAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x76d2358>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "X = np.zeros((2,20))\n",
    "for i in range(10):\n",
    "    X[:,i] = np.array([2,2]) + 0.5*rnd.randn(2)\n",
    "for i in range(10):\n",
    "    X[:,10+i] = np.array([0,0]) + 0.5*rnd.randn(2)\n",
    "    \n",
    "% matplotlib inline\n",
    "plt.plot(X[0,0:10], X[1,0:10], 'o')\n",
    "plt.plot(X[0,10:], X[1,10:], 'o', color='red')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We next minimize the {\\em log-loss function},\n",
    "\n",
    "\\begin{equation*}\n",
    "  F(\\vct{w}) = \\sum_{i=1}^{20} \\log(1+e^{-y_i (\\vct{w}^{\\trans}\\vct{x}_i-\\tau)}),\n",
    "\\end{equation*}\n",
    "\n",
    "where the $\\vct{x}_i\\in \\R^2$ are the points, and the $y_i\\in \\{-1,1\\}$ classify these as either red or blue. As minimization algorithm we choose gradient descent with backtracking, though any other reasonable algorithm would do.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def graddesc_bt(f, df, x0, tol, maxiter=100, rho=0.5, c=0.1):\n",
    "    \"\"\"\n",
    "    Gradient descent with backtracking\n",
    "    \"\"\"\n",
    "    x = np.vstack((x0+2*tol*np.ones(x0.shape),x0)).transpose()\n",
    "    i = 1\n",
    "    while ( la.norm(x[:,i]-x[:,i-1]) > tol ) and ( i < maxiter ):\n",
    "        p = -df(x[:,i])\n",
    "        # Start backtracking\n",
    "        alpha = 1\n",
    "        xnew = x[:,i] + alpha*p\n",
    "        while (f(xnew) >= f(x[:,i]) + alpha*c*np.dot(p, df(x[:,i]))):\n",
    "            alpha = alpha*rho\n",
    "            xnew = x[:,i] + alpha*p\n",
    "        x = np.concatenate((x,xnew.reshape((len(x0),1))), axis=1)\n",
    "        i += 1\n",
    "    return x[:,1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "y = np.concatenate((-np.ones(10),np.ones(10)))\n",
    "X = np.concatenate((X, np.ones((1,20))), axis=0)\n",
    "\n",
    "def f(w):\n",
    "    return np.sum(np.log(1+np.exp(-y*(np.dot(w,X)))))\n",
    "\n",
    "def df(w):\n",
    "    return np.array([-np.sum(y*X[0,:]*np.exp(-y*np.dot(w,X))/\n",
    "     \t\t\t\t (1+np.exp(-y*np.dot(w,X)))), \n",
    "                     -np.sum(y*X[1,:]*np.exp(-y*np.dot(w,X))/\n",
    "                     (1+np.exp(-y*np.dot(w,X)))),\n",
    "                     -np.sum(y*X[2,:]*np.exp(-y*np.dot(w,X))/\n",
    "                     (1+np.exp(-y*np.dot(w,X))))])\n",
    "\n",
    "W = graddesc_bt(f, df, np.array([1.,1.,1.]), 1.e-8)         "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The algorithm gives as output a vector $\\vct{w}=(w_1,w_2,w_3)\\in \\R^3$, so that the line separating the two sets of points is given by\n",
    "\n",
    "\\begin{equation*}\n",
    " w_1 x_1 + w_2 x_2 + w_3 = 0.\n",
    "\\end{equation*}\n",
    "\n",
    "Rearranging this as a function $\\ell(x_1) = x_2 = -(w_1x_1+w_3)/w_2$ and plotting the line into the pointcloud, we get the following graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAEACAYAAABI5zaHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XlclVX+B/DPYRf33cA1UsHUzEozLa8mudE2a7/BJisH\nVAxstHIZBMRMHc0FUGCqwUlrps1KXEkly30jTSUVlApcc0lQZDu/P8BHL4Fs997z3Od+3q8XL7lf\nHu79eoTPfTznWYSUEkREZCxOqhsgIiLLY7gTERkQw52IyIAY7kREBsRwJyIyIIY7EZEBWSzchRBO\nQoj9QogvLfWcRERUO5bccw8DcMSCz0dERLVkkXAXQrQFMALAO5Z4PiIiqhtL7bkvBPAaAJ7uSkSk\nA3UOdyHESABnpZRpAETZBxERKSTqem0ZIcRsAKMAFAGoB6AhgM+klH8ttx336omIakFKWeOd5jrv\nuUspp0kp20sp7wbwHIDN5YP9tm11/xEREaG8B/bJHtkn+7z5UVs8zp2IyIBcLPlkUsqvAXxtyeck\nIqKa4557OSaTSXUL1cI+LcceegTYp6XZS5+1VecF1Wq/kBDSVq9FRGQUQghIFQuqRESkPwx3IiID\nYrgTERkQw52IyIAY7kREBsRwJyIyIIY7EZEBMdyJiAyI4U5EZEAMdyIiA2K4ExEZEMOdiMiAGO5E\nRAbEcCciMiCGOxGRATHciYgMiOFORGRADHciIgNiuBMRGRDDnYjIgBjuZaSUSNyXiPyifNWtEBHV\nGcO9TFJaEoKTg9FjWQ9sytykuh0iojoRUkrbvJAQ0lavVVO/XPsFXWK74OL1i1rt+Z7PY8ETC9Cy\nfkuFnRGRoxNCQEopavp93HMH0LReU8wePBuN3RtrtfcPvg/fOF+8d+A96PVNiYioMtxzv82Z3DN4\ndcOr+O/3/zWrP9bhMSQEJMC3ha+izojIUdV2z53hXoH1J9Zj/JrxOHn5pFZzdXLF1AFTMfXRqfBw\n8VDYHRE5EmXhLoRwB7AVgBsAFwCfSCmjKtjObsIdAK4VXsPMr2diwY4FKCop0updmndB/Mh4DOo0\nSGF3ROQolO65CyE8pZTXhBDOALYBCJVS7i63jV2F+02Hzh5CUHIQdv6806z+wn0vYP4T89HCs4Wi\nzojIEShdUJVSXiv71B2le+/2l+KV6NG6B7a9tA3LRi4zW3Bd/t1y+Mb6IiktiQuuRKQ7ltpzdwKw\nD4APgDgp5dQKtrHLPffbnb56GhM3TMRHhz8yq5s6mhA/Mh5dW3RV1BkRGZUuFlSFEI0AfA5ggpTy\nSLmv2X2437T2+FqMXzMeWVeytJqbsxumDZiGKQOmwN3FXWF3RGQkugj3skbCAeRJKd8uV5cRERHa\nY5PJBJPJZNHXtqW8gjxEpkZi4c6FKJbFWr1r866ID4iHqaNJXXNEZLdSU1ORmpqqPY6KilJ2tEwL\nAIVSyitCiHoANgCYI6VcW247w+y53y7tTBqCk4OxO9ts/Rije43GfP/5aO7ZXFFnRGQEKg+F7AFg\nOUoXZ50A/E9K+WYF2xky3AGguKQY8XvjMXXTVFwtuKrVW3i2wIInFuD5ns9DiBr/2xAR6WdaptIX\nMnC435T9azbC1ofh06OfmtUHdxqM+JHx6Ny8s6LOiMheMdx1ZPUPqzFh3QT8eOVHrebu7I7pj07H\n6/1f54IrEVUbw11ncgtyEbElAot2LUKJLNHqfi38kBCQgEc7PKqwOyKyFwx3ndp/ej+Ck4OxN2ev\nWf3l+1/GPP95aFavmaLOiMgeMNx1rLikGHF74jB983TkFuRq9ZaeLbFw6EL8pcdfuOBKRBViuNuB\nn3/9GaHrQrEqfZVZ3f9ufywduRT3NLtHUWdkaydPZiE8PAnZ2SXw9nZCdPRodOrUQXVbpEMMdzvy\nRfoXmLBuAn7+9Wet5uHigfDHwjH5kclwc3ZT2B1Z28mTWfD3j0FGRhSA+gDy4OMTgZSUVxjwOqC3\nN16Gu525euMqZmyZgSW7l5gtuHZr2Q2JAYno376/wu7ImkaNisLKlZNRGuw35SEwcD5WrIio7NvI\nBvT4xsvb7NmZhu4NsXDYQuwesxu97+qt1Y+cP4IB/x6A4NXBuHT9ksIOyVqys0tgHuwAUB85OSUV\nbU42FB6edFuwA0B9ZGREITw8SWFXtcNwV+wBrwewa8wuLBy6EPVdb/3CJ+5PhG+cLz489CEvKWww\n3t5OAPLKVfPg5cVfR9WM9MbLnyYdcHFywcSHJ+JoyFE81fUprX4u7xz+8tlfMHzlcGReylTYIVlS\ndPRo+PhE4FbAl/7XPzp6tLKeaurkySyMGhWFQYMiMGpUFE6ezKr6m+yAkd54OeeuM1JKfJ7+OV5Z\n9wqyr2ZrdQ8XD0QMjMCkfpPg6uyqsEOyhJuLdjk5JfDyUr9oVxN6nJe2FD3+3bigajC/3vgV4ZvD\nEbM7BvK2G1t1b9UdiQGJ6Neun8LuyJEZfUFYb2+8DHeD2pO9B8HJwThw5oBWExAIfiAYbw15C008\nmijsjhzRoEERSE2NqrC+efNv61Q3PFrGoB7yfgi7/7YbC55YAE9XTwCAhET8vnj4xfnho8MfccGV\nbMpI89JGxj13O5J1OQsha0Ow5vgas/rwe4YjbkQcOjXtpKgzciSWmpfW28lCesVpGQchpcRnRz9D\n6PpQ5FzN0er1XOoh0hSJVx9+lQuuZHV1nZfW48KlXjHcHcyV/CuYvnk6lu5Zarbg2rN1TyQGJKJv\n274KuyO6M6MvyloS59wdTGOPxogdEYsdL+9Az9Y9tfrBswfR791+CFkTgiv5VxR2SFQ5I50spFcM\ndzvXt21f7P3bXswbMg/1XOoBKF1wXbp3Kfzi/PDJkU+44Eq6w0VZ6+O0jIGcunwK49eMx7oT68zq\nIzuPRNyIOHRowrlM0gfOuVcf59wJQOmC68dHPkbY+jCcyT2j1T1dPTHTNBNhD4fBxclFYYdEpfR2\nspBeMdzJzOX8y5i2aRri98abLbj2atMLCQEJ6OPdR2F3RFRdDHeq0I6fdiA4ORiHzh3SagICIQ+F\n4M3H30Qj90YKuyOiqjDcqVKFxYV4e8fbiPo6CteLrmt1r4ZeiBkeg2d9n+U9XIl0iuFOVcq8lInx\na8ZjQ8YGs/qTXZ5E7IhYtG/cXlFnRFQZhjtVi5QSHx3+CGHrw3A276xWr+9aHzMHzURo31AuuBLp\nCMOdauTS9UuYumkqEvYlmNXvb3M/Ep9MxINeDyrqjIhux3CnWtn24zYEJwfj8PnDWs1JOOGVPq8g\nelA0Gro3VNgdETHcqdYKiguwYPsCzNw6E/lF+Vq9baO2iB0ei6d9n1bYHZFjUxbuQoi2AP4DoDWA\nEgD/klIuqWA7hrvOZVzMwLg145CSmWJWf8b3GcQMj0HbRm0VdUbkuFSGexsAbaSUaUKIBgD2AXha\nSplebjuGux2QUuKDQx/g1Q2v4vy181q9gVsDzBo0CxP6TICzk7PCDokci26mZYQQnwOIkVJuKldn\nuNuRi9cv4o2UN/DOgXfM6g96PYiEgAT0vqu3os6IHIsuwl0I0RFAKoDuUsrccl9juNuhb7K+QXBy\nMI5eOKrVnIQTwvqGYeagmWjg1kBhd2RtvFuSesrDvWxKJhVAtJTyiwq+LiMibl2E32QywWQyWeS1\nyboKigswb9s8zNo6CzeKb2j1do3aIXZELJ7q+pTC7shaeOVGNVJTU5Gamqo9joqKUhfuQggXAMkA\n1kkpF1eyDffc7dzxX45j3Jpx2HTSbMYNv/P7HZYMWwLvRt6KOiNr4N2S9EH1nZjeA3CksmAnY+jc\nvDNSnk/B+8++jxaeLbT6Z0c/g1+cH2J2xaC4pFhhh2RJvFuSfatzuAsh+gMIBDBYCHFACLFfCDGs\n7q2RHgkhMKrnKKSHpOOlXi9p9asFVxG6PhT93u2HtDNpCjskS+HdkuwbT2KiOtmatRXBycFIv3Dr\nyFdn4YyJD09EpCmSC652jHPu+qB8QbXKF2K4G9aNohuYu20u3vzmTRQUF2j19o3bY+mIpRjZZaTC\n7qgueLck9RjupNwPF37AuDXjsOXUFrP6H7r9AYuHLYZXQy9FnRHZL4Y76YKUEv/57j+YtHESfrn+\ni1Zv5N4Ibz3+FoIfCOYZrkQ1wHAnXblw7QJeS3kNSWlJZvW+3n2R+GQierbuqaYxIjvDcCdd2nJy\nC8auGYtjvxzTas7CGZP6TcKMgTNQ3638oXZEdDuGO+lWflE+5nw7B299+5bZgmvHJh2xdMRSDO88\nXGF3RPrGcCfdS7+QjrHJY/F11tdm9T/d+ycsGroIdzW8S1FnRPrFcCe7IKVEUloSJqdMxsXrF7V6\nY/fGmDNkDoIeCIKT4EkyRDcx3MmunM87j0kbJ+H9g++b1fu17YeEgAT0aN1DUWdE+sJwJ7u0KXMT\nxq4ZixMXT2g1FycXTO43GeEDw+Hp6qmwOyL1GO5kt/KL8vHm1jcxd9tcFJYUavW7m96NpSOWYug9\nQxV2R9bGa8bfGcOd7N6R80cQnByMb3/81qz+f93/DwuHLkTrBq0VdWY7jhZ0vH5N1RjuZAglsgTv\nHXgPr6e8jkv5l7R6E48mmDdkHl7u/bJhF1wdMeh4zfiqqb6eO5FFOAknjOk9BukT0hHYI1CrX86/\njKDkIDz278dw+NxhhR1aT3h40m3BDgD1kZERhfDwJIVdWRevGW89DHfSpVb1W2HF71Zg46iN8Gnq\no9W3/bQNvRJ6Yfqm6bheeF1hh5bniEHHa8ZbD0eQdM3fxx+Hxh3CtAHT4OLkAgAoKinC7G9no8ey\nHkjJSFHcoeU4YtBFR4+Gj08Ebv29S6eioqNHK+vJKDjnTnbj+3PfIzg5GNt/2m5WD+wRiLeHvo1W\n9Vsp6swyHHHOHbCPa8arXOjmgio5hBJZgnf3v4vXv3odl/Mva/WmHk3xT/9/4sX7X7TrBVd7CDpH\no/pNl+FODuVs7lm8uuFVfPj9h2b1R9s/iviAeHRr2U1RZ2Q0qo/o4dEy5FBaN2iND37/AdYHrken\nJp20+jc/foNe8b0Qvjkc+UX5Cjsko7DXhW6GO9m1ofcMxffjv8eU/lO0BdfCkkLM+mYWei7ric0n\nNyvukOydvS50c1qGDOPQ2UMITg7Gjp93mNX/et9fMd9/PlrWb6moM7JnnHOv6oUY7mQDJbIEifsS\nMeWrKbhy44pWb16vOeY/MR8v3PcChKjx7wk5OJUL3Qx3otucvnoaEzdMxEeHPzKrD+wwEPEB8fBt\n4auoM6oJR7vWTkUY7kQVWHt8LULWhuDU5VNazc3ZDVMHTMWUAVPg4eKhrjm6I9XTIXrBcCeqRF5B\nHmZ+PRMLdixAsSzW6l2ad0FCQAJMHU3qmqNKqT4EUS94KCRRJeq71cdc/7nYF7QPfbz7aPVjvxzD\noOWD8OIXL+LCtQsKO6SK2OshiHrBcCeHcV+b+7D9pe2IHR6Lhm4NtXpSWhJ8Y32xPG05+L9L/bDX\nQxD1wiLTMkKIdwEEADgrpexZyTacliHdyLmag9B1ofj06Kdm9UEdByE+IB5dmndR1BndxDn3Ukrn\n3IUQAwDkAvgPw53sSfKxZISsDcGPV37Uam7Obpj+6HS80f8NuLu4K+yOeK0dHSyoCiE6AFjNcCd7\nk1eQh8jUSCzcudBswdW3hS8SAhLwWIfHFHZHjo7hTlRHaWfSELQ6CHty9pjVX77/Zczzn4dm9Zop\n6owcmV2Ee0TErcOXTCYTTCaTRV6byFKKS4qxbO8yTNs0DVcLrmr1lp4t8fbQtxHYI5BnuJJVpaam\nIjU1VXscFRWl/3DnnjvZi+xfsxG2Puw3C66Pd3ocy0YuQ+fmnRV1Ro5GD3vuHVEa7j0q+TrDnZB1\n8iSSwsNRkp0NJ29vjI6ORodOnar+RkVW/7AaIWtD8NOvP2k1d2d3hD8Wjtf6vwY3ZzeF3ZEjUH20\nzAcATACaAzgLIEJK+e9y2zDcHVzWyZOI8fdHVEZG2YFtQISPD15JSdF1wOcW5GLGlhlYvGsxSuSt\nE2j8Wvgh8clEDGg/QGF3+sJrwVie8j33Kl+I4e7wokaNwuSVK8udTA7MDwxExIoVqtqqtv2n9yNo\ndRD2nd5nVh9z/xjM9Z/r8AuuPC7dOnj5AdK9kuzsCk4mB0pyclS0U2O97+qNXWN2YdHQRWjg1kCr\nv3PgHfjF+eGDQx849Bmu4eFJtwU7ANRHRkYUwsOTFHbluBjuZDNO3t4VnEwOOHl5qWinVpydnBH2\ncBiOjD+Cp7s+rdXP5Z1D4GeBGLZyGDIuZijsUB1eC0ZfGO5kM6OjoxHh46MF/M0599HR0SrbqpV2\njdvh8+c+x6o/r4J3Q2+tvjFjI7ov6445385BYXGhwg5tj9eC0RfOuZNNaUfL5OTAyctL90fLVMfV\nG1cRviUcMbtjzBZcu7fqjoSABDzS7hGF3dkO59ytgwuqRIrtzdmLoNVBOHDmgFk9qHcQ5gyZg6b1\nmirqzHZ4LRjLY7gT6UBRSRGW7FqCGVtmIK/w1hRF6/qtsWjYIvz53j/zDFeqEYY7kY5kXc7ChHUT\nkHws2aw+1Gcolo1chk5N7XsqimyH4U6kM1JKfHb0M4SuD0XO1VuHe9ZzqYeIgRH4e7+/w9XZVWGH\nZA8Y7kQ6dSX/Cv6x+R+I2xMHiVu/Az1a9UBCQAL6teunsDvSO4Y7kc7t+nkXgpOD8d3Z77SagMDY\nB8di9uOz0cSjicLuSK8Y7kR2oLC4EIt3LUZEagSuFV7T6m0atMHiYYvxx25/5IIrmWG4E9mRU5dP\nIWRtCNYeX2tWH9F5BOJGxKFjk45qGiPdYbgT2RkpJT458glC14fiTO4Zre7p6okoUxTC+oZxwZUY\n7kT26kr+FUzdNBXxe+PNFlzva30fEp9MRB/vPgq7I9UY7kR2bufPOxG0OgiHzh3SagICIQ+F4M3H\n30Qj90YKuyNVGO5EBlBYXIi3d7yNqK+jcL3oulb3auiFJcOW4Hd+v+OCq4NhuBMZSOalTISsDcH6\nE+vN6k92eRKxI2LRvnF7RZ2RrTHciQxGSomPDn+EsPVhOJt3VqvXd62PmYNmIrRvKFycXBR2SLbA\ncCcyqMv5lzHlqylI2JdgVr+/zf1IfDIRD3o9qKgzsgWGO1EZ7Zrx2dlw8vY2xDXjAWD7T9sRtDoI\nh88f1mpOwgkTHpqA6MHRXHA1KIY7EUqDPcbfH1EZGWW3iyi929MrKSmGCPiC4gJtwTW/KF+rezf0\nRszwGDzr96zC7sgaGO5EAKJGjcLklSvN7uSZB2B+YCAiVqxQ1ZbFZVzMwPi147ExY6NZ/emuTyNm\neAzaNW6nqDOytNqGO29uSIZSkp1dwS2agZKcnIo2t1s+zXywPnA9Pvz9h2hVv5VW/+KHL+AX54dF\nOxehuKRYYYekGsOdDMXJ27uCWzQDTl5eKtqxKiEEnuv+HNJD0hHUO0ir5xXm4dUNr6LvO32xL2ef\nwg5JJU7LUI3ofbHS6HPud7Ltx20ISg7CkfNHtJqTcEJon1BED45GA7cGCruj2uKcO1mdvQSn9gaU\nkwMnLy/dvQFZU0FxAeZvn4+ZX8/EjeIbWr1do3aIHRGLp7o+pbA7qg2GO1mdoyxWGsGJiycwbs04\nfJX5lVn9Wd9nsWT4ErRt1FZRZ1RTXFAlq3OUxUojuKfZPdg4aiNWPLsCLT1bavVV6avgF+eHJbuW\ncMHV4CwS7kKIYUKIdCHEMSHEG5Z4TtIfR1qsNAIhBAJ7BiJ9Qjpevv9lrZ5bkIuw9WHo924/HDh9\nQGGHZE11npYRQjgBOAbgcQA5APYAeE5KmV5uO07L2Dl7mXOnin2T9Q2Ck4Nx9MJRreYsnDHx4YmI\nNEVywVWnlM25CyEeBhAhpRxe9ngKACmlnFtuO4a7ATjyYqUR3Ci6gX9u/ydmbZ1ltuDavnF7xI2I\nQ0CXAIXdUUVUhvvvAQyVUgaVPR4FoI+UMrTcdgx3HdD7oYxkG8d/OY6xa8Zi88nNZvU/dPsDFg9b\nDK+GnGrTi9qGu02vFxoZGal9bjKZYDKZbPnyDq/CaZWdOzmt4oA6N++Mr57/Cu8ffB+TNk7ChWsX\nAACfHPkEG05swFuPv4WxD46Fs5Oz4k4dT2pqKlJTU+v8PJaalomUUg4re8xpGZ0ov5d+OTcXs774\ngocykpkL1y7gtZTXkJSWZFbv490HiQGJuK/NfWoaIwBqp2WcAfyA0gXV0wB2A/g/KeXRctsx3G2o\nor30Vzw8EJGfjw7lto0YNAhRmzdX8CzkSFJPpSI4ORjHfjmm1ZyFM/7e7++IGBiB+m7lD4QlW1B2\nnLuUshjABAAbARwG8N/ywU62lxQergU7UHo8ekx+Pt4ptx0PZaSbTB1NODj2ICIHRsLN2Q0AUCyL\n8c/t/8S9S+/F2uNrFXdINWGR49yllOullF2llJ2llHMs8ZxUN5WdcJTp4aEdq37zUMbR0dG2bY50\ny93FHRGmCBwcexCmjiatnnUlCyM/GIk/ffwnnL56Wl2DVG28/IBBVXapgMinnkKDhg15KCNVSUqJ\n5d8tx6SNk3Dx+kWt3ti9MeYMmYOgB4LgJHiSu7Xx2jJkhicckaWczzuP11Jew/LvlpvVH277MBID\nEtGjdQ9FnTkGhjv9Bk84IkvafHIzxiaPxfGLx7Wai5MLJvWbhBkDZ8DT1VNhd8bFcCciq8svysfs\nb2ZjzrdzUFhSqNU7NemEpSOXYtg9wxR2Z0wMdyKymaPnjyI4ORjf/PiNWf257s9h4dCFaNOgjaLO\njIfhTkQ2VSJLkJSWhMkbJ+NS/iWt3sSjCeYOmYsxvcdwwdUCGO5kl3itG/t3Lu8cJm2chBUHzc9y\nfqTdI0gISED3Vt0VdWYMDHeyOzyix1hSMlIwbs04ZFzK0GouTi547ZHXEP5YOOq51lPYnf1iuJPd\n4W37jOd64XXM2joL87bPQ1FJkVa/u+ndiB8ZD38ff4Xd2SfeZo/sDm/bZzz1XOvhzcffRFpwGvq3\n66/VMy9l4okVTyDws0CczT2rsEPHwXAnZXjbPuO6t9W92PriViQGJKKJRxOt/sGhD+AX54d39r+D\nElmisEPj0+20DBfajI9z7o7hbO5ZTNo4CSsPrTSrD2g/AAkBCejWspuizuyDoebc+UvvOCx1Fi13\nBvRvY8ZGjFszDpmXMrWaq5Mr3uj/BqY/Nh0eLh4Ku9MvQ4U7F9qoJrgzYD+uFV5D9NfRmL9jvtmC\n6z3N7sGykcsw5O4hCrvTJ0MtqHKhjWqiomvXR2VkICk8XGVbVAFPV0+8NeQt7A/aj35t+2n1ExdP\nwP99fzy/6nmcyzunsEPj0GW4G2WhLevkSUSNGlV6p6NRo5B18qTqlgyJOwP2p0frHvj2pW8RPzIe\njd0ba/UVB1fAL84P7x14Dzx0um50Ge6jo6MR4eNj1zeVuDlVMHnlSkSlpmLyypWI8fevc8DzDeO3\njLIz4GichBOCHwxG+oR0PNf9Oa1+8fpFvPzlyzAtNyH9QrrCDu2clNImH6UvVX2nMjNlZGCgnDFo\nkIwMDJSnMjNr9P2qRQYGylxAyts+cgEZGRhY6+c8lZkpJ/n4aM+bC8hJPj52NzaWxnExhrXH1spO\nizpJREL7cIt2kxFbIuT1wuuq21OmLDtrnLm6XFA1gohBgxCVmlpxvZY3o+ZCc+V47XpjuFZ4DVGp\nUViwYwGKZbFW79K8C+JHxmNQp0EKu1OjtguqLtZohm5NFZQP4rpMFXBuuXIdOnVy+Dc4I/B09cRc\n/7kI7BmIoNVB2JW9CwBw7JdjGPyfwXjhvhcw/4n5aOHZQnGn+qfLOXcjsMa6AeeWyVH0bN0T217a\nhqUjlqKReyOtvvy75fCN9UVSWhIXXKvAaRkrsvRUAY/nJkeUczUHE9dPxMdHPjarmzqaED8yHl1b\ndFXUmW0Y6iQmqhznlslRrTm2BiFrQ5B1JUuruTm7Yfqj0/FG/zfg7uKusDvrYbgTkeHlFeQhMjUS\nC3cuNFtw7dq8KxICEjCw40CF3VkHw52IHEbamTQErQ7Cnpw9ZvWXer2Eef7z0NyzuaLOLI/hTkQO\npbikGMv2LsO0TdNwteCqVm/h2QJvP/E2RvUcBSFqnIm6w3AnIoeU/Ws2wtaH4dOjn5rVB3cajPiR\n8ejcvLOiziyD4U5EDm31D6sRsjYEP/36k1Zzd3bH9Een4/X+r9vtgquScBdC/AFAJAA/AA9JKfff\nYVuGOxFZVW5BLmZsmYHFuxab3enJr4UfEgIS8GiHRxV2Vzuqwr0rgBIACQAmM9yJSA/2n96P4ORg\n7M3Za1Yfc/8YzPWfi2b1minqrOaUXM9dSvmDlPI4APtftSAiw+h9V2/sfHknFg9bjAZuDbT6Owfe\ngW+sL1YeXGn4M1x5+QEiMiRnJ2eE9g3F0ZCjeMb3Ga1+/tp5jFo1CkNXDEXGxQyFHVpXleEuhEgR\nQhy87eNQ2Z9P2qJBIqK6aNuoLVb9eRVW/XkV2jZqq9VTMlPQfVl3zP5mNgqKCxR2aB0WOVpGCLEF\nwKSq5twjIiK0xyaTCSaTqc6vTURUXVdvXEX4lnDE7I4xW3Dt1rIbEgMS0b99f4XdlUpNTUXqbZcL\nj4qKUncoZFm4T5ZS7rvDNlxQJSJd2JezD0HJQdh/2nx/NKh3EOYMmYOm9Zoq6uy3VB0t8wyAGAAt\nAFwGkCalHF7Jtgx3ItKNopIixO6OxT82/wN5hbcupt2qfissGroIz3V/ThdnuPIkJiKiWvjpyk+Y\nsG4CvvzhS7P6UJ+hWDpyKe5uereizkox3ImIaklKic/TP8cr615B9tVsre7h4oGIgRGY1G8SXJ1d\nlfTGcCciqqNfb/yK8M2lC64St/Kqe6vuSAxIRL92/WzeE8OdiMhC9mTvQVByENLOpJnVgx8Ixpwh\nc9DEo4nNemG4ExFZUFFJEZbsWoLwLeG4VnhNq7dp0AaLhy3GH7v90SYLrgx3IiIryLqchQnrJiD5\nWLJZfUTnEYgbEYeOTTpa9fUZ7kREViKlxKdHP0XoulCczj2t1eu51EOUKQoTH55otQVXhjsRkZVd\nyb+CaZvnvCvcAAAHXUlEQVSmYdneZWYLrj1b90RiQCL6tu1r8ddkuBMR2cjOn3ciODkYB88e1GoC\nAuMeHIfZj89GY4/GFnsthjsRkQ0VFhdi0c5FiEiNwPWi61r9rgZ3YcnwJfi93+8tsuDKcCciUuDU\n5VMYv2Y81p1YZ1Yf2Xkk4kbEoUOTDnV6foY7EZEiUkp8fORjhK0Pw5ncM1rd09UTM00zEfZwGFyc\nXGr13Ax3IiLFLudfxrRN0xC/N95swbVXm15IDEjEQ94P1fg5Ge5ERDqx46cdCEoOwvfnvtdqAgIT\n+kzArMGz0Mi9UbWfi+FORKQjhcWFWLBjAWZ+PdNswdWroRdihsfgWd9nq7XgynAnItKhzEuZGL9m\nPDZkbDCrP9X1KcQOj0W7xu3u+P0MdyIinZJS4n+H/4eJ6yfibN5ZrV7ftT5mDZ6FCX0mVLrgynAn\nItK5S9cvYcpXU5C4P9Gs3vuu3kgISMCDXg/+5nsY7kREdmLbj9sQlByEI+ePaDUn4YRX+ryC6EHR\naOjeUKsz3ImI7EhBcQHmb5+P6K3RyC/K1+ptG7VF7PBYPO37NACGOxGRXTpx8QTGrRmHrzK/Mqs/\n4/sMYobHoF3jdgx3IiJ7JKXEh99/iInrJ+L8tfNavYFbA+ROy61VuDtZtEMiIqoxIQT+0uMvSJ+Q\njjH3j9HquQW5tX5OhjsRkU40q9cM/3rqX9g6eiv8WvjV6bk4LUNEpEMFxQWYt20ewgeGc86diMho\nanu0DKdliIgMiOFORGRADHciIgOqU7gLIeYJIY4KIdKEEJ8KIap/kWIiIrKauu65bwRwr5SyF4Dj\nAKbWvSW1UlNTVbdQLezTcuyhR4B9Wpq99FlbdQp3KeVXUsqSsoc7AbSte0tq2cs/OPu0HHvoEWCf\nlmYvfdaWJefcXwKwrsqtiIjI6qq8HbcQIgVA69tLACSA6VLK1WXbTAdQKKX8wCpdEhFRjdT5JCYh\nxGgAfwMwWEp54w7b8QwmIqJaqM1JTFXuud+JEGIYgNcAPHanYAdq1xwREdVOnfbchRDHAbgB+KWs\ntFNKOd4SjRERUe3Z7NoyRERkO1Y7Q1UI8QchxPdCiGIhRO87bDdMCJEuhDgmhHjDWv3c4fWbCiE2\nCiF+EEJsEEI0rmS7U0KI74QQB4QQu23UW5VjI4RYIoQ4XnYiWS9b9FVBD3fsUwgxUAhxWQixv+zj\nHwp6fFcIcVYIcfAO2+hhLO/Ypx7GsqyPtkKIzUKIw0KIQ0KI0Eq2Uzqm1elT9ZgKIdyFELvKsuWQ\nECKiku1qNpZSSqt8AOgKoDOAzQB6V7KNE4ATADoAcAWQBsDXWj1V0sNcAK+Xff4GgDmVbJcJoKkN\n+6pybAAMB7Cm7PO+KJ0Ws9nY1aDPgQC+tHVv5XoYAKAXgIOVfF35WFazT+VjWdZHGwC9yj5vAOAH\nnf58VqdP5WMKwLPsT2eUnjPUp65jabU9dynlD1LK4yg9dLIyfQAcl1JmSSkLAfwXwNPW6qkSTwNY\nXvb5cgDPVLKdgG2vxVOdsXkawH8AQEq5C0BjIURr2FZ1/w2VLqhLKb8FcOkOm+hhLKvTJ6B4LAFA\nSnlGSplW9nkugKMAvMttpnxMq9knoP7n81rZp+4oPdCl/Hx5jcdS9YXDvAH8dNvjn1HxwFtTKynl\nWaD0BwFAq0q2kwBShBB7hBB/s0Ff1Rmb8ttkV7CNtVX337Bf2X8n1wghutmmtRrRw1hWl67GUgjR\nEaX/29hV7ku6GtM79AkoHlMhhJMQ4gCAMwBSpJR7ym1S47Gs66GQVZ7gpAd36LOiubXKVpj7SylP\nCyFaojTkj5btZVHV9gFoL6W8JoQYDuBzAF0U92SvdDWWQogGAD4BEFa2Z6xLVfSpfExl6WVc7i+7\n+OLnQohuUsojdXnOOoW7lNK/Lt+P0nef9rc9bltWs6g79Vm2eNVaSnlWCNEGwLlKnuN02Z/nhRCr\nUDodYc1wr87YZANoV8U21lZln7f/Mkkp1wkhlgohmkkpL9qox+rQw1hWSU9jKYRwQWlgvi+l/KKC\nTXQxplX1qacxlVL+KoTYAmAYgNvDvcZjaatpmcrms/YAuEcI0UEI4QbgOQBf2qinm74EMLrs8xcA\n/OYfXwjhWfbODyFEfQBPAPjeyn1VZ2y+BPDXsr4eBnD55hSTDVXZ5+1zg0KIPig9BFdFsAtU/rOo\nh7G8qdI+dTSWAPAegCNSysWVfF0vY3rHPlWPqRCixc2j9IQQ9QD4A0gvt1nNx9KKq7/PoHSO6DqA\n0wDWldXvApB823bDULqCfRzAFAWr1M0AfFXWw0YATcr3CaATSo8COQDgkK36rGhsAAQDCLptm1iU\nHq3yHSo5Kkl1nwBCUPpmeADAdgB9FfT4AYAcADcA/AjgRZ2O5R371MNYlvXRH0Dxbb8X+8t+DnQ1\nptXpU/WYAuhR1lcagIMondau8+86T2IiIjIg1UfLEBGRFTDciYgMiOFORGRADHciIgNiuBMRGRDD\nnYjIgBjuREQGxHAnIjKg/wfCK+gS804BowAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x790da20>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def l(x):\n",
    "    return (-W[0,-1]*x-W[2,-1])/W[1,-1]\n",
    "    \n",
    "xx = np.linspace(-0.5,3,100)\n",
    "yy = l(xx)\n",
    "plt.plot(X[0,0:10], X[1,0:10], 'o')\n",
    "plt.plot(X[0,10:], X[1,10:], 'o', color='red')\n",
    "plt.plot(xx,yy,linewidth=3)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course, we would like to know how our classifier does with a {\\em test set} generated according to the same distribution. The result is seen the following plot."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXMAAAEACAYAAABBDJb9AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl4VNX9x/H3yYZhFwSRHQJo0SpaRUHRgI1A2CsImAQT\nrPWpitpqW6vyCzTdtLRatdZqVSTsyCY7CTCGqKjVIlTBBSMoKFXLDtnP74+EARFIYiZzZu58Xs+T\nh5nDnTufeYDvXM52jbUWEREJb1GuA4iISO2pmIuIeICKuYiIB6iYi4h4gIq5iIgHqJiLiHhAwIq5\nMSbKGPO2MealQJ1TRESqJ5BX5ncB7wXwfCIiUk0BKebGmLZAMvDPQJxPRERqJlBX5o8AvwC0nFRE\nxIFaF3NjzCBgt7V2I2Aqf0REJIhMbfdmMcb8HkgFSoF4oBGwwFo77oTjdNUuIvIdWGurvEiu9ZW5\ntfZ+a217a21nYAyw9sRCftyxnv3JzMx0nkGfT59Nn897P9WleeYiIh4QE8iTWWtfBl4O5DlFRKRq\nujIPkMTERNcR6pSXP5+XPxvo80WKWg+AVvuNjLHBei8REa8wxmCDMQAqIiLuqZiLiHiAirmIiAeo\nmIuIeICKuYiIB6iYi4h4gIq5iIgHqJiLiHiAirmIiAeomIuIeICKuYiIB6iYi4h4gIq5iIgHqJiL\niHiAirmIiAeomIuIeICKuYiIB6iYi4h4gIq5iIgHqJiLiHiAinmYsdbytzf+xqHiQ66jiEgIUTEP\nMw+sfYA7VtxBUnYSe47scR1HREKEsdYG542MscF6L6967dPX6P1cb//zi86+iFWpqzi74dkOU4lI\nXTLGYK01VR2nK/Mw0qtdLx4b8Jj/+Tu736HP833YsW+Hw1QiEgp0ZR6GXtj4AuNfGk+5LQegXeN2\n5KTlcO5Z5zpOJiKBVt0rcxXzMLVgywLGzh9LcVkxAC3qt2B12mp6tOrhOJmIBFLQirkxph6QB8QB\nMcCL1trJJzlOxTzAcrblMHzOcA6XHAagSb0mLE9ZTu92vat4pYiEi6BemRtj6ltrDxtjooFXgDut\ntW+ccIyKeR149dNXSZ6RzL6ifQDUj63PotGLSEpIcpxMRAIhqAOg1trDlQ/rUXF1rqodJL3b9caX\n7qNlg5YAHC45zOBZg1m4ZaHjZCISTAEp5saYKGPMv4EvgBxr7ZuBOK9UT49WPVifsZ52jdsBUFxW\nzKh5o5j2zjTHyUQkWAJ1ZV5urb0YaAtcbozpHojzSvV1a96N/PH5dG3WFYAyW8ZNi27iiTeecJxM\nRIIhJpAns9buN8asAwYA7534+5MmTfI/TkxMJDExMZBvH/HaN2nP+oz19J/en3d2vwPAhBUT2Fu4\nlwf6PIAxVXa7iYhjPp8Pn89X49cFYjbLWUCJtXafMSYeWAX80Vq7/ITjNAAaJHsL9zJo5iBe/fRV\nf9u9ve7l4aSHVdBFwkwwB0DPAdYZYzYCrwOrTizkElxNz2jK6tTVJHU+NqNlymtTuHXprZSVlzlM\nJiJ1RYuGPKyotIix88eycOuxmS2jzx/NtBHTiIuOc5hMRKpLK0AFgNLyUm5+6eZvzGxJ7prMi6Ne\nJD423mEyEakObbQlAMRExfD8sOe547I7/G3LP1zOgBkD2F+032EyEQkkFfMIEGWieGzgYzzY50F/\nW972PK6ddi1fHf7KYTIRCRR1s0SYP7/6Z+7Nudf/vHuL7qxOXU2bxm0cphKRU1GfuZzSM289w61L\nb8VW7rrQqWkncsfl0vnMzo6TiciJVMzltGb/ZzZpC9MoLS8F4JyG55CTlsP5Lc93nExEjqdiLlVa\n9sEyRs4bSWFpIQDN4puxMmUll7W5zHEyETlKxVyq5eVPXmbIrCEcKD4AQMO4hiwZu4TEjolug4kI\noKmJUk3XdLyGtTetpXl8cwAOFh9k4IyBLP1gqeNkIlITKubCpa0vJS8jj3MangNAYWkhI+aMYNbm\nWY6TiUh1qZgLUDFFMX98vn9GS2l5KSkLUvjHv/7hOJmIVIf6zOUbdh3YRVJ2Eu99eWwH44d++BC/\nvPKXDlPJyRQUbGfixKns3FlOmzZRZGWl06lTB9exJMA0ACrf2deHv2bAjAH8a9e//G2/vurX/K7f\n77SFbogoKNhOUtLjbNs2GWgAHCIhIZOcnAkq6B6jAVD5zprXb86acWu4psM1/rY/5P+BCSsmUG7L\nHSaToyZOnHpcIQdowLZtk5k4carDVOKSirmcVON6jVmRsoJBXQf52/725t+4adFN/oVG4s7OneUc\nK+RHNWDXLrdftgUF20lNnUzfvpmkpk6moGC70zyRJKC3jRNviY+NZ+HohYxbNI7Z/5kNwPRN0zlQ\ndIDZI2dzRswZjhNGrjZtooBDfLOgH6J1a3fXZyfr+tmwQV0/waIrczmt2OhYpo+Yzk8u+Ym/bfH7\nixk8czAHiw86TBbZsrLSSUjIpKKgw9E+86ysdGeZ1PXjloq5VCk6KpqnBj/FL3r/wt+2pmANSdlJ\n/O/I/xwmi1ydOnUgJ2cCKSlT6Ns3k5SUKc6vgEO16ydSqJtFqsUYw0M/fIimZzTlgbUPALDhsw0k\nTk1kddpqWjVs5Thh5OnUqQPTp2e6juEXil0/kURTE6XG/vbG37hjxbE7F3Vp1oXctFw6NFW/aCTT\ndMm6oXnmUqey38kmY3EGZbYMgLaN25KTlsN5Z53nOJm4dHQh065d5bRurYVMgaBiLnVu0dZFjH5x\nNMVlxQC0qN+C1Wmr6dGqh+NkIt6hYi5BkftxLsNnD+dQScWsiib1mrDsxmVc2f5Kx8lEvEHFXILm\ntU9fI3lmMnsL9wIQH1MxP71/l/6Ok4mEPy3nl6Dp1a4Xvpt8tGzQEoAjpUcYMmsI89+b7ziZSOTQ\nlbkEzIdff8gPs3/Ijn07AIgyUTw79FnSe6S7DeZx2j3R29TNIk7s2LeDpOwkPvj6A3/bo/0f5a4r\n7nKYyruOTQe8GZgLlNCw4SaWLfsVV1+tcQsvUDEXZ/576L/0n96fjV9s9LdNTpzMxKsnagvdAEtN\nncyMGTcAzwLH5nc3bDiBTZsydYXuAeozF2daNmjJupvW0btdb39bpi+Te1bfg77QA6tiCf1cjhVy\ngAYcPPi49kSJMLUu5saYtsaYtcaYd40xm40xdwYimIS3pmc0ZXXqapI6J/nbHtnwCLcsuYWy8jKH\nycLf8dvMfvLJf4CvONmeKNu2HTrJq8Wrat3NYoxpBbSy1m40xjQE3gKGWWu3nnCculkiUFFpETcu\nuJEFWxb420Z1H8X0H00nLjrOYbLwdLIl88b8BGsfBL533JGHaNhwLJs2Pa6uljAXtG4Wa+0X1tqN\nlY8PAluANrU9r3hDvZh6zBk55xszWua9N49hs4dxuOSwu2Bh6mTbzFr7NBX/IT62HS5kcvDgQ+pq\niSAB7TM3xnQEegCvB/K8Et5iomJ4duiz3NnzWA/cyo9WMmD6APYV7nOYLPycapvZhg1bAFOAzMpf\nJwDf0/azESRgW+BWdrG8CNxVeYX+LZMmTfI/TkxMJDExMVBvLyEuykTx6IBHaXpGU36T9xsA1u9Y\nT79p/ViZspIWDVo4ThgeTrXNbPPmRRw4cO+32rX9bPjx+Xz4fL4avy4gUxONMTHAUmCFtfavpzhG\nfeYCwF9e+wv3rL7H//y8s84jJy2Hto3bOkwVHk61zexzz41g/PiF2n7Wg4I6z9wYMw34ylr789Mc\no2Iufv98+5/8ZMlPsFT8nejYtCM5aTl0adbFcbLQd6ptZrX97Ld5YXVs0Iq5MeZKIA/YDNjKn/ut\ntStPOE7FXL5h7rtzSV2QSkl5CQCtGrZidepqvn/29x0nEy/wys0ytAJUwsKKD1fwo7k/orC0EIAz\nzziTlakr6dmmp+NkEu4qVsd+exwhJWVKSN1urypaASphYWDXgaxKXUWjuEYA7Cncw7XTrmVdwTrH\nyULX8YuGUlMnU1Cw3XWkkBRpN5hWMRfnru5wNetuWkfz+OYAHCw+yMAZA1ny/hLHyULP0a6DGTPu\nxeeruPJMSnpcBf0kjs38OZ53Z/h481NJ2PlB6x+Ql5FH60atASgqK2LEnBHM3DzTcbLQcrJFQ9u2\nTdbioJPIykonISGT4xdTJSRkkpWV7ixTXVIxl5DRvUV38jPy6XxmZwDKbBmpC1L5+5t/d5wsdERa\n10FtdOrUgZycCaSkTKFv30xSUqaE3eBnTQRs0ZBIIHQ6sxP5GfkkZSfx7pfvYrHctvw29hXt476r\n7nMdz7lTLRryatdBbXXq1CGsBjtrQ7NZJCR9ffhrBs4YyJu73vS33Xflffz+2t9H9J7owZxu54U5\n2l6gqYkS9g4UHWDo7KH4PvH523566U95IvkJokzkXokGY3GQV+Zoe4GKuXjCkZIjjH5xNEs+ODaz\nJeX7KTw/7Hlio2MdJvM2r8zR9gLNMxdPiI+NZ/4N8xl7wVh/24zNMxg5b6R/oZEEngZaw4+KuYS8\n2OhYskdkc+sPbvW3vfT+SwyaOYgDRQccJvOuSJuj7QXqZpGwYa3lvtz7ePjVh/1tl7e5nOUpy2kW\n38xhMrfqYqBSfeahQ33m4ll/WP8H7l97v//591t+n9Vpq2nVsJXDVG7UZdHVLoyhQcVcPO3JN5/k\n9uW3+593adaF3LRcOjSNrGKjgUrv0wCoeNptl91G9ohsok00AB/97yOufO5Ktn61tYpXeosGKuUo\nFXMJW6kXpjL/hvnUi64HwM4DO+nzfB/e/vxtx8mCRwOVcpS6WSTsrfl4DcNmD+NQSUVRa1yvMctu\nXMZV7a9ynKzuaaDS+9RnLhHl9c9eZ+CMgewp3ANAfEw8C0cvpH+X/o6T1T0NVHqbirlEnE27N3Fd\n9nXsPrQbgNioWGZeP5OR3Uc6Tiby3WkAVCLOhWdfSP74fDo0qbgqLSkvYfSLo3nu3885TiZS91TM\nxVO6NOtC/vh8zm1+LgDltpybX7qZRzc86jiZSN1SMRfPadu4LXkZefRo1cPf9rNVP2OSbxLq6hOv\nUp+5eNbewr0MnjmYVz59xd929+V385f+f4noPdElvGgAVAQ4VHyI6+dez6ptq/xt43uM5+khTxMd\nFe0wmUj1qJiLVCoqLSJlQQrzt8z3t43qPorpP5pOXHScw2QiVdNsFpFK9WLqMXvkbDJ6ZPjb5r03\nj6GzhnK45LDDZCKBo2IuESEmKoZ/Dv0nd11+l79t1bZV9J/en32F+xwmEwkMFXOJGFEmikf6P8L/\nXf1//rb8Hfn0m9aPLw996TCZSO2pz1wi0qMbHuVnq37mf37eWeeRk5ZD28ZtHaYS+bag9pkbY541\nxuw2xmwKxPlE6trdV9zNs0OfJcpU/BPY+tVWrnruKj7630eOk4l8N4HqZnke8P6ORuIp4y8ez+zr\nZxMbFQvA9n3bueq5q9i8e7PjZCI1F5Bibq3NB/YE4lwiwTTq/FEsHrOY+Jh4AHYf2s01U6/h9c9e\nd5xMpGY0ACoRb2DXgaxKXUWjuEYA7Cncw7XTrmVtwVrHyUSqLyaYbzZp0iT/48TERBITE4P59iKn\n1KdDH3zpPvpP789Xh7/iUMkhkmckM2fkHIadN8x1PIkgPp8Pn89X49cFbDaLMaYDsMRae+Epfl+z\nWSTkbflyC0nZSew8sBOAaBPN1OFTSb0w1XEyiVQuVoCayh+RsPW9Ft8jf3w+CWcmAFBmyxi3cBx/\nf/PvjpOJnF6gpibOBF4FuhljdhhjMqp6TaTZXlDA5NRUMvv2ZXJqKtsLClxHklPo2LQj6zPWc0HL\nCwCwWG5bfht/zP+j42Qip6ZFQ0GwvaCAx5OSmLxtW+UtdyEzIYEJOTl06NTJdTw5hf8d+R8DZwzk\njZ1v+Nt+deWv+MO1f9AWuhI02mgrhEydONFfyKHiHuqTt21j6sSJLmNJFZrFNyM3LZe+Hfv62x56\n5SFuW3Yb5bbcYTKRb1MxD4LynTv9hfyoBkD5rl0u4kgNNKrXiOUpyxnSbYi/7am3niJtYRolZSUO\nk4l8k4p5EES1acOhE9oOAVGtW7uIIzV0RswZzL9hPinfT/G3zdw8k+vnXk9haaHDZCLHqJgHQXpW\nFpkJCf6CfrTPPD0ry2UsqYHY6FimjZjGTy/9qb9tyQdLSJ6RzIGiAw6TiVTQAGiQbC8oYOrEiZTv\n2kVU69akZ2Vp8DMMWWu5f839/PGVYzNberbpyfIbl9O8fnOHycSrdNs4kTr0UP5D3LfmPv/zC1pe\nwOrU1ZzT6ByHqcSLVMxF6thT/3qK25bdhqXi73XCmQnkjsulY9OOboOJp6iYiwTBzM0zGbdwHGW2\nDIA2jdqQk5bD91p8z3Ey8QoVc5EgWfL+EkbNG0VRWREAZ9U/i1Wpq7jknEscJxMvUDEXCaJ1BesY\nOnsoB4sPAtC4XmOWjl1Knw59HCeTcKcVoCJB1LdTX3LTcjnzjDMB2F+0n+umX8eKD1c4TiaRQsVc\nJEAub3s5eRl5tGrYCoDC0kKGzR7GvHfnOU4mkUDFXCSALmh5Aesz1tOhSQcASspLGDN/DM++/azj\nZOJ1KuYiAdalWRfyx+dz3lnnAVBuy/nxkh/zl9f+4jiZeJmKuUgdaNu4LXnped+Y0XLP6nvIXJeJ\nJgJIXdBslhDkX/q/cydRbdpUufS/psdL8Owr3MeQWUNYv2O9v+3OnnfyyIBHiDK6lpKqaWpimKrp\njSx044vQd7jkMNfPvZ6VH630t6X3SOeZIc8QExXUe6pLGNLUxDBV0xtZ6MYXoa9+bH0Wj1nMyO4j\n/W1TN05lzItjKCotcphMvETFPMTU9EYWuvFFeIiLjmP29bMZ32O8v23+lvkMnT2UQ8Un7nYvUnMq\n5iGmpjeyCKcbX0T6Ta2jo6J5Zugz3H353f621dtW0396f/YW7nWYTDzBWhuUn4q3kqp88vHH9p6E\nBHsQrAV7EOw9CQn2k48/DsjxroRLzmAoLy+3k32TLZPw//R4qofdfXC362gSgiprZ5U1VgOgIaim\nN7IIhxtfTE5N5d4ZM77RJXQImJKSQub06a5iOfXXDX/l7lXHrtLPbX4uOWk5tGvSzmEqCTWazSIh\nJbNvXyb7fCdvX7s2+IFCxNSNU7n5pZspt+UAtG/Snty0XLo27+o4mYQKzWaRkBJOffvBlN4jnbkj\n5xIbFQvAjn076PN8Hzbt3uQ4mYQbXZlLUGg+/Omt+mgVI+aM4EjpEQCantGU5Tcup1e7Xo6TiWvq\nZpGQEw59+y69suMVkmcms79oPwANYhuwaMwiftj5h46TiUsq5iJh6N+f/5v+0/vz5eEvgYr56XNG\nzmH4ecMdJxNX1GcuEoYuPudi1mesp23jtgAUlxUzcu5Ipm+KzBk/Un0BKebGmAHGmK3GmA+MMb8K\nxDlFItW5Z51LfkY+XZp1AaDMlpG2MI0n33zScTIJZbXuZjHGRAEfANcCu4A3gTHW2q0nHKduFpEa\n+OLgF1yXfR2b/7vZ3/b7fr/nvqvuw5gq/9ctHhHMbpaewIfW2u3W2hJgNjAsAOcVj4v05f1VadWw\nFb50H1e0vcLfdv/a+7kv9z7tiS7fEoj9N9sAnx73/DMqCnzI0b7foeOkUxU3bNBUxRM0i29GTloO\nw2cPZ03BGgAefvVh9hbu5clBTxIdFe04oYSKoG6mPGnSJP/jxMREEhMTg/beKh6h5VRb906ZODFi\nl/efSsO4hiy9cSljXhzD4vcXA/D0209zoPgALwx/gdjoWMcJJZB8Ph++k6yWrkog+syvACZZawdU\nPr+Pio1hHjrhOKd95tobJLRoeX/NlZaXMn7xeLI3ZfvbBncbzNyRc4mPjXeYTOpSMPvM3wS6GGM6\nGGPigDHASwE4b0Bp3+/QouX9NRcTFcPU4VO57dLb/G1LP1hK8sxkDhQdcJhMQkGti7m1tgy4A1gN\nvAvMttZuqe15A03FI7SkZ2WRmZDg/zM5urw/PSvLZayQF2WieCL5CX591a/9bb5PfPSb1o+vD3/t\nMJm4FjErQLU3SOjR8v7aefiVh/lV7rFlHd1bdCcnLYfWjXSB4iVazn8SKh7iNf/41z/46bKfYqn4\nt9X5zM7kpuXS6Uz9vfYKFfMIoimXkW3W5lmMWzSO0vJSAFo3ak1OWg7dW3R3nEwCQcU8QkRC95G+\nrKq29IOljJw7kqKyIgCaxzdnZepKLm19qeNkUlsq5hHC61MuI+HLKlB8n/gYMmsIB4sPAtAorhFL\nxi7hmo7XOE4mtaFdEyOE16dcnmpx0dSJE13GCkmJHRNZM24NzeKbAXCg+AADZgxg2QfLHCeTYFAx\nD3Nen3Lp9S+rQOvZpicvp79Mq4atACgsLWT4nOHM+c8cx8mkrqmYhzmvz9f2+pdVXbig5QXkZ+TT\nsWlHoGLl6Nj5Y3nmrWfcBpM6pT5zD/DKlMuTDXQC6jP/jnbu30lSdhJbvjq2hm9K0hTu6X2Pw1RS\nUxoAlbByuoFOwBNfVi58dfgrBkwfwFufv+Vve7DPg/ym72+0J3qYUDGXsOL1WTku7S/az5BZQ8jb\nnudvm9BzAo8OeJQoo57WUKfZLBJWNNBZdxrXa8zKlJUkd032tz3+xuNkLM7wLzSS8KdiLiFBA511\nKz42noWjF3LD+Tf426a9M40b5t1AUWmRw2QSKCrmEhK8PisnFMRFxzHzRzP58cU/9rct3LqQIbOG\ncKj4xK9SCTfqM5eQ4ZVZOaHOWssvcn7Bn1/7s7+tV9teLE9ZTtMzmjpMJiejAVAROSVrLb9b/zsm\nrju2kvaisy9iVeoqzm54tsNkciIVcxGp0mOvP8ZdK+/yP+/WvBs5aTm0b9LeYSo5noq5iFTLCxtf\nYPxL4ym35QC0a9yO3HG5dGvezXEyARVzEamBBVsWMObFMZSUlwDQskFLVqWuokerHo6TiYq5iNTI\nqo9WMWLOCI6UHgGgSb0mLE9ZTu92vR0ni2wq5iJSY69++irJM5LZV7QPgPqx9Vk0ehFJCUmOk0Uu\nrQAVkRrr3a43vnQfLeq3AOBwyWEGzxrMwi0LHSeTqqiYi8g39GjVg/UZ62nXuB0AxWXFjJo3imnv\nTHOcTE5HxVxEvuXcs84lf3w+XZt1BaDMlnHTopt4/PXHHSeTU1ExF5GTat+kPXkZeVx49oX+tjtX\n3slv836Lxr9CjwZAReS09hzZQ/LMZDZ8tsHfdk+ve/hT0p+0J3oQaDaLiATMweKDDJ89nDUFa/xt\nt1xyC38f9Heio6IdJvM+FXMRCajC0kLGzh/Loq2L/G2jzx/NtBHTiIuOc5jM21TMRSTgSstLGb94\nPNmbsv1tyV2TeXHUi8THxjtM5l1BmWdujBlpjPmPMabMGHNJbc4lIqEvJiqGqcOncvtlt/vbln+4\nnAEzBrC/aL/DZFLb2SybgRHAywHIIiJhIMpE8fjAx3mgzwP+trztefR7oR9fHf7KYbLIVqtibq19\n31r7IaAhbZEIYozht/1+y5+S/uRve+vzt7hm6jXs3L/TYbLIpXnmIvKd3dv7Xp4e/DSm8nruvS/f\no8/zffh4z8eOk0WeKou5MSbHGLPpuJ/Nlb8OCUZAEQltt/zgFmZeP5OYqBgACvYWcNVzV/Huf991\nnCyyxFR1gLU2YNulTZo0yf84MTGRxMTEQJ1aRBwac8EYGsU1YuS8kRSWFvL5wc+5eurVrExZyWVt\nLnMdL6z4fD58Pl+NXxeQqYnGmHXAvdbat05zjKYminjcy5+8zJBZQzhQfACAhnENWTJ2CYkdE90G\nC2PBmpo43BjzKXAFsNQYs6I25xOR8HZNx2tYe9NamsU3AypWjg6cMZClHyx1nMz7tGhIRALu3f++\nS1J2Ep8f/ByomJ+ePSKbMReMcZws/OjmFCLizPktzyd/fD6dmnYCKlaO3jj/Rp5+62nHybxLxVxE\n6kTnMzuTPz6f7i26A2Cx3Lr0Vv70yp+qeKV8FyrmIlJnWjdqTV56Hpe2vtTf9svcX/Lg2ge1J3qA\nqc9cROrc/qL9DJk1hLztef622y+7nccGPkaU0TXl6WjXRBEJKUdKjjBy3kiWf7jc35Z2YRrPDXvO\nv+BIvk0DoCISUuJj41k4eiGjzx/tb8velM2oeaMoKi1ymMwbVMxFJGjiouOY8aMZ3HLJLf62RVsX\nMXjWYA4WH3SYLPypmItIUEVHRfOPwf/g3l73+ttyP84lKTuJPUf2OEwW3lTMRSTojDE8nPQwv+37\nW3/bhs82kPhCIrsP7naYLHxpAFREnHrijSeYsGKC/3nXZl3JScuhQ9MODlOFDs1mEZGwMe2daWQs\nzqDclgPQrnE7ctJyOPescx0nc0/FXETCysItCxkzfwzFZcUAtKjfgtVpq+nRqofjZG6pmHvQ9oIC\npk6cSPnOnUS1aUN6VhYdOnVyHUskYHI/zmXY7GEcLjkMQJN6TVh24zKubH+l42TuqJh7zPaCAh5P\nSmLytm00AA4BmQkJTMjJUUEXT3nt09dInpnM3sK9ANSPrc/C0Qu5LuE6x8nc0KIhj5k6caK/kAM0\nACZv28bUiRNdxhIJuF7teuG7yUfLBi0BOFxymMEzB7NgywLHyUKbinmYKN+501/Ij2oAlO/a5SKO\nSJ26qNVFrM9YT7vG7QAoKS9h1LxRTN041W2wEKZiHiai2rTh0Alth4Co1q1dxBGpc92adyN/fD7d\nmncDoNyWk7E4g8def8xxstCkYh4m0rOyyExI8Bf0o33m6VlZLmOJ1Kn2TdqTl57HRWdf5G+7a+Vd\nZL2cpS10T6AB0DDin82yaxdRrVtrNotEjL2Fexk0cxCvfvqqv+3nV/ycKddNwZgqxwbDmmaziIin\nHCo+xIg5I8j5OMff9uOLf8xTg58iOiraYbK6pWIuIp5TVFrEjQtu/MbMlhvOv4HsEdnERcc5TFZ3\nVMxFxJNKy0u5+aWbmfbONH/boK6DeGnsS568a5HmmYuIJ8VExfD8sOeZ0PPY5lwDuwz0ZCGvCd2r\nSUTCTpSJ4q8D/krTM5pSL7oet/e83XUk59TNIiISwtTNIiISQVTMRUQ8QMVcRMQDalXMjTEPG2O2\nGGM2GmOE+bBdAAADdklEQVTmG2MaByqYiIhUX22vzFcD51trewAfAr+ufaTw5PP5XEeoU17+fF7+\nbKDPFylqVcyttbnWVt60DzYAbWsfKTx5/S+Ulz+flz8b6PNFikD2mY8HVgTwfCIiUk1VLhoyxuQA\nZx/fBFjgAWvtkspjHgBKrLUz6ySliIicVq0XDRlj0oFbgH7W2qLTHKcVQyIi30F1Fg3Vajm/MWYA\n8Avg6tMV8uqGERGR76ZWV+bGmA+BOODryqYN1trbAhFMRESqL2h7s4iISN0J6gpQLy8yMsaMNMb8\nxxhTZoy5xHWeQDHGDDDGbDXGfGCM+ZXrPIFkjHnWGLPbGLPJdZa6YIxpa4xZa4x51xiz2Rhzp+tM\ngWKMqWeMed0Y8+/Kz5bpOlNdMMZEGWPeNsa8VNWxwV7O7+VFRpuBEcDLroMEijEmCngC6A+cD4w1\nxpznNlVAPU/FZ/OqUuDn1trzgV7A7V7586sco+trrb0Y6AEMNMb0dByrLtwFvFedA4NazL28yMha\n+7619kMqpm56RU/gQ2vtdmttCTAbGOY4U8BYa/OBPa5z1BVr7RfW2o2Vjw8CW4A2blMFjrX2cOXD\nelRM5vBUn7Expi2QDPyzOse73GhLi4xCXxvg0+Oef4aHikEkMcZ0pOIK9nW3SQKnsgvi38AXQI61\n9k3XmQLsESpmC1brSyrgdxry8iKj6nw2kVBjjGkIvAjcVXmF7gmV/8u/uHLsbZExpru1tlpdEqHO\nGDMI2G2t3WiMSaQa/+MPeDG31iad7vcrFxklA/0C/d51rarP5kE7gfbHPW9b2SZhwhgTQ0Uhz7bW\nLnadpy5Ya/cbY9YBA6hm/3IYuBIYaoxJBuKBRsaYadbacad6QbBnsxxdZDS0qkVGYc4r/eZvAl2M\nMR2MMXHAGKDKUfUwY/DOn9fJPAe8Z639q+sggWSMOcsY06TycTyQBGx1mypwrLX3W2vbW2s7U/Hv\nbu3pCjkEv8/8caAhkFM53ebJIL9/nTHGDDfGfApcASw1xoT9eIC1tgy4g4pZSO8Cs621W9ymChxj\nzEzgVaCbMWaHMSbDdaZAMsZcCaQA/Sqn8L1deUHlBecA64wxG6kYB1hlrV3uOJNTWjQkIuIBum2c\niIgHqJiLiHiAirmIiAeomIuIeICKuYiIB6iYi4h4gIq5iIgHqJiLiHjA/wPikkGvNKLjjAAAAABJ\nRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x812b390>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Generate test data\n",
    "T = np.zeros((2,20))\n",
    "for i in range(10):\n",
    "    T[:,i] = np.array([2,2]) + 0.5*rnd.randn(2)\n",
    "for i in range(10):\n",
    "    T[:,10+i] = np.array([0,0]) + 0.5*rnd.randn(2)\n",
    "    \n",
    "plt.plot(T[0,0:10], T[1,0:10], 'o')\n",
    "plt.plot(T[0,10:], T[1,10:], 'o', color='red')\n",
    "plt.plot(xx,yy,linewidth=3)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The given example is unproblematic, since the two sets of points are generated in a way that makes it unlikely that they can't be separated using a linear classifier. With real data, the situation may not be as favourable.\n",
    "\n",
    "It is also interesting to see how fast the objective function (the {\\em empirical risk}) approaches the minimum. While the value of the objective function decreases very quickly at the beginning, the decrease slows down dramatically and the algorithm does not reach the desired accuracy within the limit we set for the number of iterations. Now, however, that for the classification task we are interested, we don't need the best possible precision! In fact, the noise in the data makes too much precision meaningless, and we can safely use the result obtained after 100 iterations. Other algorithms and approaches may perform better for this problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYYAAAEPCAYAAABGP2P1AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGi5JREFUeJzt3Xu0XGWd5vHvc3IhAZJ0UJMgEeTSXKTlpqA9Ok21ICDY\nwHLGLGjaAcXRvgyhW8chYS2bqN2N0OM46OAabYHJcmC6URcQWlwJMRS0Osodwi0gDBeFHHAgmSQk\n5HJ+88fexal9UlWncnL2W1Wnns9atWrvXfvyq02o57zvvikiMDMzqxnodAFmZtZdHAxmZlbgYDAz\nswIHg5mZFTgYzMyswMFgZmYFpQeDpFmSvi/pcUmPSnqfpNmSVkhaI2m5pFll12FmZu1J0WK4Crgt\nIo4AjgaeABYBKyPiMGAVsDhBHWZm1gaVeYGbpJnAAxFx8IjpTwAnRsSgpHlANSIOL60QMzNrW9kt\nhgOB30q6TtL9kr4jaU9gbkQMAkTEWmBOyXWYmVmbyg6GycBxwNURcRywiawbaWQzxfflMDPrEpNL\nXv+vgRci4t58/IdkwTAoaW5dV9LLjRaW5MAwMxuDiNBYly21xZB3F70g6dB80knAo8Ay4IJ82vnA\nLS3W4VcEl112Wcdr6JaX94X3hfdF69fuKrvFALAQuF7SFOAZ4JPAJOBGSZ8CngMWJKjDzMzaUHow\nRMRDwPENPjq57G2bmdmu85XPPaJSqXS6hK7hfTHM+2KY98X4KfU6ht0lKbq5PjOzbiSJ6NaDz2Zm\n1nscDGZmVuBgMDOzAgeDmZkVOBjMzKzAwWBmZgUOBjMzK3AwmJlZgYPBzMwKHAxmZlbgYDAzswIH\ng5mZFTgYzMyswMFgZmYFDgYzMytwMJiZWYGDwczMChwMZmZW4GAwM7OCrg+G227rdAVmZv2l64Nh\nzZpOV2Bm1l+6PhjeeKPTFZiZ9ZeuD4YtWzpdgZlZf3EwmJlZQdcHg7uSzMzS6vpgcIvBzCytyWVv\nQNKzwHpgCNgWESdImg38E3AA8CywICLWN1reLQYzs7RStBiGgEpEHBsRJ+TTFgErI+IwYBWwuNnC\nbjGYmaWVIhjUYDtnAUvz4aXA2c0WdjCYmaWVIhgCuF3SPZI+nU+bGxGDABGxFpjTbGF3JZmZpVX6\nMQbgAxHxkqS3ASskrSELi3ojx9/kFoOZWVqlB0NEvJS/vyLpZuAEYFDS3IgYlDQPeLnZ8k8+uYQl\nS7LhSqVCpVIpu2Qzs55SrVapVqvjtj5FNP1jffdXLu0JDETERkl7ASuALwEnAa9GxBWSLgFmR8Si\nBsvHe94T3HtvaSWamU04kogIjXX5slsMc4GbJEW+resjYoWke4EbJX0KeA5Y0GwF7koyM0ur1BbD\n7pIUhxwSPPVUpysxM+sdu9ti8JXPZmZW4GAwM7OCrg8GX8dgZpZW1weDWwxmZml1fTBs2wZDQ52u\nwsysf3R9MIC7k8zMUuqJYHB3kplZOj0RDG4xmJml0xPB4BaDmVk6DgYzMyvoiWBwV5KZWTo9EQxu\nMZiZpdMTweAWg5lZOj0RDG4xmJml42AwM7OCnggGdyWZmaXTE8HgFoOZWToOBjMzK+iJYHBXkplZ\nOj0RDG4xmJml0xPB4BaDmVk6PREMbjGYmaXjYDAzs4KeCAZ3JZmZpdMTweAWg5lZOj0RDG4xmJml\n0xPB4BaDmVk6DgYzMyvoiWBwV5KZWTpJgkHSgKT7JS3Lx2dLWiFpjaTlkma1Wt4tBjOzdFK1GC4G\nHqsbXwSsjIjDgFXA4lYLOxjMzNIpPRgkzQdOB75bN/ksYGk+vBQ4u9U63JVkZpZOihbD14EvAFE3\nbW5EDAJExFpgTqsVuMVgZpbO5DJXLukMYDAiHpRUaTFrNP9oCWvXwpIlUKlUqFRarcbMrP9Uq1Wq\n1eq4rU8RLX6Td3fl0t8BfwJsB6YDM4CbgPcClYgYlDQPuCMijmiwfECw777w4oullWlmNqFIIiI0\n1uVL7UqKiEsjYv+IOAg4B1gVEZ8AbgUuyGc7H7il1XrclWRmlk6nrmP4KvBhSWuAk/Lxpnzw2cws\nnVK7knZXrStpYAB27Oh0NWZmvaH0riRJBzaYdvxYNzgWQ0OwfXvKLZqZ9a92upJ+KGm/2oikE4Fr\nyyupMR9nMDNLo51g+Cxws6R5kk4HvkF2wVpSDgYzszRGvY4hIu6RtBBYAWwBTo6IV0qvbAQfgDYz\nS6NpMEi6leKFZ3sC64Fr8gMbZ5ZdXD23GMzM0mjVYvjPyapog4PBzCyNpsEQEXcCSNoL2BwRQ5IO\nBQ4Hfpyovje5K8nMLI12Dj7fBUzLz0xaAXwC+B9lFtWIWwxmZmm0EwyKiNeBjwHfioiPA79Xblk7\nc4vBzCyNtoJB0u8D5wE/2oXlxpVbDGZmabTzA/+XZE9YuykiHpV0EHBHuWXtzMFgZpZGO9cx3Anc\nWTf+DLCwzKIacVeSmVkara5j+K8R8ZcNrmcA8HUMZmYTVKsWw/fy9664nsEtBjOzNFpdx3CfpEnA\nZyLivIQ1NeQWg5lZGi0PPkfEDuAASVMT1dOUg8HMLI1RDz4DzwA/k7QM2FSbGBH/pbSqGnBXkplZ\nGu0Ew9P5awCYUW45zbnFYGaWRjunq34pRSGjcTCYmaWR/ArmsXJXkplZGj0TDG4xmJml0TPB4BaD\nmVkara58/iYNrniuiYikt8Vwi8HMLI1WB5/vTVZFGxwMZmZptLryeWnKQkbjriQzszRGPV1V0tuA\nS4B3AdNq0yPiQyXWtRO3GMzM0mjn4PP1wOPAgcCXgGeBe0qsqSG3GMzM0mgnGN4SEdcA2yLizoj4\nFJC0tQBuMZiZpdJOMGzL31+SdIakY4F92lm5pD0k/VLSA5JWS7osnz5b0gpJayQtlzRrtHU5GMzM\n0mgnGP4m/+H+PPAfge8Cf9XOyiPiDeAPI+JY4BjgI5JOABYBKyPiMGAV2aNDW3JXkplZGopoeqnC\n+G5I2hO4C/gzsocAnRgRg5LmAdWIOLzBMlG7lGLOHBgcTFKqmVlPk0REaKzLj9pikLRU0u/Ujc+W\ndO0uFDgg6QFgLXB7RNwDzI2IQYCIWAvMGW097koyM0ujndtuHxUR62ojEfFafpyhLRExBBwraSZw\nk6Qj2fmK6hbNliUAbNoE1WqFSqXS7qbNzPpCtVqlWq2O2/pG7UqS9BBQiYjX8vF9gDsj4t27vDHp\ni8DrwKfzdda6ku6IiCMazB/1mTE0BBpz48jMrD+U3pUEfA3435K+IulvgJ8DV7ZZ3FtrZxxJmg58\nmOyaiGXABfls5wO3NFvH1LqHim7d2s5Wzcxsd7R18FnSuxi+dmFVRDzW1sqldwNLyQJoAPiniPjb\nvNVxI/AO4DlgQX13Vd3yMWNGsGFDNr5uHcwa9cRWM7P+trsthqbBIGlmRPy//Ed8JxHx6lg32i5J\n8ba3Ba+8ko2vXQtz55a9VTOz3ra7wdDq4PMNwEeB+ygeHFY+ftBYN7orpk0bHva1DGZm5Wt1d9WP\nShLZ9QbPJ6ypYI89hod9yqqZWflaHnyOrJ/pR4lqacgtBjOztNo5K+l+SceXXkkT9cHgFoOZWfna\nucDtfcB5kp4DNpEfY4iIo0qtLOeuJDOztNoJhlNLr6IFdyWZmaXVNBhqp6sCGxLWsxN3JZmZpbUr\np6vWnxOb7HRVdyWZmaXV8nTV/P3AdOXszF1JZmZptXOMAUkfAz5I1lL4l4i4udSq6rjFYGaWVjvP\nY/gW8KfAauAR4E8lXV12YTVuMZiZpdVOi+FDwBH5xW5IWgo8WmpVdXzw2cwsrXYucPsVsH/d+Dvy\naUm4K8nMLK12WgwzgMcl3Z2PHw/cK2kZQEScWVZx4K4kM7PU2gmGvy69ihbclWRmltaowRARd0J2\nwVv9/CmexwDFriS3GMzMyjdqMEj6DPBlYAswRAefx+AWg5lZ+drpSvoC8HsR8duyi2nEB5/NzNJq\n56ykp4HXyy6kGR98NjNLq50Ww2Lg55J+Cbz50xwRC0urqo67kszM0monGL4NrCK78nmo3HJ25q4k\nM7O02gmGKRHxudIracJdSWZmabVzjOHHkj4jaV9J+9RepVeWc1eSmVla7bQYzs3fF9dN68jpqps3\np9iimVl/a+cCt44+j2HvvYeHN23qXB1mZv2iaVeSpP9UN/zxEZ/9XZlF1asPho0bU23VzKx/tTrG\ncE7d8OIRn51WQi0NORjMzNJqFQxqMtxovDR77TU8vHEjZE+FMDOzsrQKhmgy3Gi8IUnzJa2S9Kik\n1ZIW5tNnS1ohaY2k5ZJmNVvHpEkwfXq+0fABaDOzsima/AkuaQewiax1MJ3h22IImBYRU0ZduTQP\nmBcRD0raG7gPOAv4JPB/I+JKSZcAsyNiUYPlIyKYMwdeeSWbNjgIc+bs4rc0M+sjkoiIMffsNG0x\nRMSkiJgZETMiYnI+XBsfNRTydayNiAfz4Y3A48B8snBYms+2FDi71Xp8nMHMLJ12LnAbF5LeCRwD\n/AKYGxGDkIUH0LIN4GAwM0unnQvcdlvejfQD4OKI2Cip7WMWS5Ys4bXXamMVNm6slFOkmVmPqlar\nVKvVcVtf02MM47YBaTLwz8CPI+KqfNrjQCUiBvPjEHdExBENlo2I4JRT4Pbbs2nLl8Mpp5RasplZ\nTyvtGMM4uhZ4rBYKuWXABfnw+cAtrVbgriQzs3RK7UqS9AHgPGC1pAfIuowuBa4AbpT0KeA5YEGr\n9TgYzMzSKTUYIuJnwKQmH5/c7nocDGZm6SQ7K2l3OBjMzNJxMJiZWYGDwczMChwMZmZW4GAwM7MC\nB4OZmRU4GMzMrMDBYGZmBQ4GMzMrcDCYmVmBg8HMzAocDGZmVtATwTB1KkzJHya6bRts3drZeszM\nJrKeCAZwq8HMLJWeDIYNGzpXh5nZRNeTweAWg5lZeRwMZmZW4GAwM7MCB4OZmRU4GMzMrMDBYGZm\nBQ4GMzMrcDCYmVmBg8HMzAocDGZmVuBgMDOzAgeDmZkVOBjMzKyg1GCQdI2kQUkP102bLWmFpDWS\nlkua1c66HAxmZmmU3WK4Djh1xLRFwMqIOAxYBSxuZ0UOBjOzNEoNhoj4KfDaiMlnAUvz4aXA2e2s\ny8FgZpZGJ44xzImIQYCIWAvMaWchB4OZWRrdcPA52pnJwWBmlsbkDmxzUNLciBiUNA94udXMS5Ys\nASACoAJU2LIFtm+HyZ2o3sysy1SrVarV6ritTxFt/cE+9g1I7wRujYh35+NXAK9GxBWSLgFmR8Si\nJstGfX0zZw4/73ndOpjV1vlMZmb9RRIRobEuX/bpqjcAPwcOlfS8pE8CXwU+LGkNcFI+3hZ3J5mZ\nla/UzpiI+OMmH508lvU5GMzMytcNB5/b5mAwMyufg8HMzAocDGZmVuBgMDOzAgeDmZkVOBjMzKzA\nwWBmZgUOBjMzK3AwmJlZgYPBzMwKHAxmZlbgYDAzswIHg5mZFTgYzMyswMFgZmYFDgYzMytwMJiZ\nWUHpz3zeHSOf+bxjB0yeXPsMtm+HgZ6KNjOz8nX1M5/H26RJMH16NhwBmzd3th4zs4mop4IB3J1k\nZla2nguGmTOHh3/6087VYWY2UfVcMJx22vDwwoWwfn3najEzm4h6Lhi+/GWYOzcbfvFFuOSSztZj\nZjbR9Fww7LMPfPObw+Pf/jbcdVfn6jEzm2h66nTVmgg4+2xYtiwbP/RQeOghmDYtcYFmZl2or05X\nrZHg6qthxoxs/Mkn4dJLO1uTmdlE0ZPBADB/Plx55fD4178OK1Z0rh4zs4miJ7uSaiLgox+F227L\nxufNg9Wr4a1vTVSgmVkX6tmuJEmnSXpC0pOSxnRukQTXXgtz5mTja9fChRdmgWFmZmPTkRaDpAHg\nSeAk4EXgHuCciHhixHwtWww1t90GZ5wxPH7wwdnZSzNnZsch9t4b9tpr+LXnntlr2rTsFhvTp2fD\ne+wx/D51avaqH54yZfh9ypS092mqVqtUKpV0G+xi3hfDvC+GeV8M290Ww+TxLGYXnAA8FRHPAUj6\nR+As4ImWSzVx+ulw0UXDp7E+/XT2KtvAQHZTvylTiu+116RJxffa8GivgYHi8MAAPPJIlWOPrbw5\nvisvqfF4q/faq9n4yOmNXiPnqe2z0ZaD1tOvv77Kli2VUeerH24072jzjZw2lvl3d776zxotc9NN\nVfbfv9Jyfc2+R6v5Rvus3fWN57aajdesWFHlve+tjNv6xlpfO8vsyrY6oVPBsB/wQt34r8nCYsyu\nvDI7ZTXlNQ1DQ7B1a/ZKYfXqNNvpBTfc0OkKusc3vtHpCrrH5Zd3uoK06gNk3rzsot/x0KlgGHfT\npkG1mh1nWLcuu1XG+vWwaVN2s70NG+D117PX5s3Z9C1bsuHNm+GNN7LXli3Z+9atw9O2bRsOgG3b\nhsfNzDqpvqd9PI8KdOoYw/uBJRFxWj6+CIiIuGLEfD6MbGY2BrtzjKFTwTAJWEN28Pkl4G7g3Ih4\nPHkxZmZW0JGupIjYIek/ACvITpm9xqFgZtYduvoCNzMzS68rb4kxHhe/9SpJ8yWtkvSopNWSFubT\nZ0taIWmNpOWSZnW61lQkDUi6X9KyfLwv94WkWZK+L+nx/N/H+/p4X/yVpEckPSzpeklT+2VfSLpG\n0qCkh+umNf3ukhZLeir/d3NKO9voumDIL377b8CpwJHAuZIO72xVSW0HPhcRRwK/D/xF/v0XASsj\n4jBgFbC4gzWmdjHwWN14v+6Lq4DbIuII4Giy6376bl9IejtwEXBcRBxF1iV+Lv2zL64j+32s1/C7\nS3oXsAA4AvgI8C1p9Kskui4YqLv4LSK2AbWL3/pCRKyNiAfz4Y3A48B8sn2wNJ9tKXB2ZypMS9J8\n4HTgu3WT+25fSJoJ/OuIuA4gIrZHxHr6cF/kJgF7SZoMTAd+Q5/si4j4KfDaiMnNvvuZwD/m/16e\nBZ6ijWvGujEYGl38tl+HaukoSe8EjgF+AcyNiEHIwgOY07nKkvo68AWg/mBYP+6LA4HfSrou71b7\njqQ96cN9EREvAl8DnicLhPURsZI+3Bd15jT57iN/T39DG7+n3RgMBkjaG/gBcHHechh5lsCEP2tA\n0hnAYN6CatX8nfD7gqy75Djg6og4DthE1n3Qj/8ufofsL+QDgLeTtRzOow/3RQu79d27MRh+A+xf\nNz4/n9Y38ubxD4DvRcQt+eRBSXPzz+cBL3eqvoQ+AJwp6RngfwEfkvQ9YG0f7otfAy9ExL35+A/J\ngqIf/12cDDwTEa9GxA7gJuBf0Z/7oqbZd/8N8I66+dr6Pe3GYLgHOETSAZKmAucAyzpcU2rXAo9F\nxFV105YBF+TD5wO3jFxooomISyNi/4g4iOzfwaqI+ARwK/23LwaBFyQdmk86CXiUPvx3QdaF9H5J\n0/IDqSeRnZzQT/tCFFvRzb77MuCc/KytA4FDyC4obr3ybryOQdJpZGdg1C5++2qHS0pG0geAu4DV\nZM3BAC4l+495I1n6PwcsiIh1naozNUknAp+PiDMl7UMf7gtJR5MdhJ8CPAN8kuwgbD/ui8vI/ljY\nBjwAfBqYQR/sC0k3ABXgLcAgcBlwM/B9Gnx3SYuBC8n21cURMeqzLrsyGMzMrHO6sSvJzMw6yMFg\nZmYFDgYzMytwMJiZWYGDwczMChwMZmZW4GCwpCQNSfr7uvHPS/rrcVr3dZI+Nh7rGmU7/1bSY5J+\nMmL6vpJuzIePlvSRcdzmLEl/1mhbZuPNwWCpvQF8LL9IrWvkj5tt14XApyPipPqJEfFSRCzIR48h\nuyvseNUwG/jzJtsyG1cOBkttO/Ad4HMjPxj5F7+kDfn7iZKqkm6W9CtJl0v6Y0m/lPRQfql/zYcl\n3aPsQU9n5MsPSLoyn/9BSf++br13SbqF7PYSI+s5N38QzMOSLs+nfRH4IHCNpCtGzH+AsocrTQa+\nDCzI74T6cUl75g9Y+YWk+yT9Ub7M+ZJuyVsfKyXtJWmlpHvz7/ZH+eovBw7K13dFbVv5OvaQdG1e\n532SKnXr/qGkHyt7gMsVdfvjunz+hyRdvGv/CW2i68gzn62vBXA1sHrkD2uTeWuOAg4H1pHdDuIf\nIuJ9yp5wdxHDQXNARBwv6RDgDkkHk907Zl0+/1TgZ5JqtwU4FjgyIp6v37CkfYGv5p+vA26XdGZE\nfEXSh8gepvRAo5ojYnvePfaeiKg9ge9vgZ9ExIXKnq51t6SVdTW8OyLWK3tQ1dkRsVHSW8huuX4r\n2Z1Uj8zvrIqkA+r2z18AQxFxlKTDgBWSfjf/7Giy1ss2YI2kbwBzgf3yh9zUnvVg9ia3GCy5/Dbi\nS8mezNaueyLi5YjYCjwN1H7YVwPvrJvvxnwbv8rnOxw4Bfh3kh4AfgnsA9R+OO8eGQq544E78jt4\nDgHXA39Q9/moT8Ea4RRgUV5DFZjK8F2Eb88fugPZ/5OXS3oIWAm8XdJozxX4IPA/ASJiDfAsULvZ\n3k8iYmNEvEF2o7kDyIL1QElXSToV2LCL38UmOLcYrFOuAu4ne0xhzXbyP1byu2ZOrfvsjbrhobrx\nIYr/jutbGcrHBVwUEbfXF5DfmG9Tixp39cd/NP8mIp4aUcP7R9RwHvBW4NiIGJL0f4Bpu7id+rrr\n99sOYHJErMtvyHcq8FmyRz9euIvbsAnMLQZLTQAR8RrZX/f1P0jPAu/Nh88iu4vorvq4MgeTPfVs\nDbAc+PO87x9Jv6vs6Wet3A38gaR98oPC55L9pd+uDUB9F81yYGFtRNIxTZabBbych8Ifkv2FX1vf\njCbL/AtZoKDsttzvIPveDeVdVJMi4ibgi2RdWWZvcjBYavV/0X+N7NbBtWn/AJyYd7eM/Eu62TpG\nep7sR/1HwGfzrqfvknWj3J8fsP3vZLerbl5k9njERWRh8ABZV9Y/t7H9mjuAd9UOPgNfAabkB3wf\nITs43cj1wPF5V9KfkD3zm4h4lezYyMMNjs18C5gk6WGyBxqdnz8vfaevlb/vB1Tz/fy9/Huavcm3\n3TYzswK3GMzMrMDBYGZmBQ4GMzMrcDCYmVmBg8HMzAocDGZmVuBgMDOzAgeDmZkV/H+otpW+QsPa\nQgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x787f400>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "risk = np.zeros(W.shape[1])\n",
    "for i in range(W.shape[1]):\n",
    "    risk[i] = f(W[:,i])\n",
    "    \n",
    "plt.plot(range(W.shape[1]), risk, linewidth=3)\n",
    "plt.xlabel('Number of iterations')\n",
    "plt.ylabel('Empirical risk')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have seen how a machine learning problem can be turned into an optimization problem. Unfortunately, when the amount of data is large, computing gradients and Hessians of the resulting functions can be very expensive. Suppose the function $h$ depends on parameters $\\vct{w}$ which we want to optimize over, $h=h(\\vct{x}; \\vct{w})$, and denote the composition of the loss function $\\ell$ with $h$ on the data $\\vct{x}_i$ by\n",
    "\n",
    "\\begin{equation*}\n",
    "  f_i(\\vct{w}) := \\ell(h(\\vct{x}_i; \\vct{w}),y_i).\n",
    "\\end{equation*}\n",
    "\n",
    "We can then write our optimization problem as\n",
    "\n",
    "\\begin{equation*}\n",
    "  \\mathop{\\minimize}_{\\vct{w}} F(\\vct{w}), \\quad F(\\vct{w}) = \\frac{1}{m} \\sum_{i=1}^m f_i(\\vct{w}).\n",
    "\\end{equation*}\n",
    "\n",
    "The gradient is then\n",
    "\n",
    "\\begin{equation*}\n",
    "  \\nabla F(\\vct{w}) = \\frac{1}{m} \\sum_{i=1}^n \\nabla f_i(\\vct{w}).\n",
    "\\end{equation*}\n",
    "\n",
    "For large datasets (for example, $m>10^6$ is not uncommon), computing all the gradients in each step is highly ineffective.\n",
    "\n",
    "An old algorithm that has recently been revived in light of big data is **Stochastic Gradient Descent** (**SGD**). The idea is to compute, at each step, only the gradient of *one* (or sometimes a few) of the summands of the loss function:\n",
    "\n",
    "\\begin{equation*}\n",
    "  \\vct{w}_{k+1} = \\vct{w}_k-\\alpha_k \\nabla f_{i_k}(\\vct{w}_k),\n",
    "\\end{equation*}\n",
    "\n",
    "where the index $i_k$ is *chosen at random* from $\\{1,\\dots,m\\}$ at each step. \n",
    "\n",
    "Each step of this algorithm is clearly faster than gradient descent, but does it even work? It turns out that this algorithm converges quickly and that it is surprisingly effective on large datasets.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [py27]",
   "language": "python",
   "name": "Python [py27]"
  },
  "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}