simulations/frecency.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Federated Learning"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:06.334432Z",
     "start_time": "2018-07-06T00:13:06.302931Z"
    }
   },
   "outputs": [],
   "source": [
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:06.838000Z",
     "start_time": "2018-07-06T00:13:06.337725Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:06.856150Z",
     "start_time": "2018-07-06T00:13:06.840322Z"
    }
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "sys.path.insert(0, '..')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:07.019447Z",
     "start_time": "2018-07-06T00:13:06.858432Z"
    }
   },
   "outputs": [],
   "source": [
    "from data.frecency import sample, frecency_points\n",
    "from data.frecency import sample_suggestions_normal as sample_suggestions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Regression\n",
    "\n",
    "This section is mostly to check that's it possible to fit a linear model perfectly to the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:07.449049Z",
     "start_time": "2018-07-06T00:13:07.021372Z"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.linear_model import LinearRegression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To fit a model, we sample a lot of these scores and also add noise on top to make the problem more similar to the real application."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:08.724726Z",
     "start_time": "2018-07-06T00:13:08.400635Z"
    }
   },
   "outputs": [],
   "source": [
    "n = int(1e6)\n",
    "noise = np.random.normal(0, 2, size=(n))\n",
    "X, y = sample(n)\n",
    "y += noise"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:10.123284Z",
     "start_time": "2018-07-06T00:13:09.291773Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "LinearRegression(copy_X=True, fit_intercept=False, n_jobs=1, normalize=False)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "model = LinearRegression(fit_intercept=False)\n",
    "model.fit(X, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The resulting coefficients are extremely close to the actual frecency weights. How close they are depends on how much noise we add to the data matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:10.722421Z",
     "start_time": "2018-07-06T00:13:10.698627Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(120.00622752979648, 120.0),\n",
       " (36.003933467053777, 36.0),\n",
       " (98.003077164944798, 98.0),\n",
       " (13.999646106828301, 14.0),\n",
       " (19.995704850139081, 20.0),\n",
       " (100.00855775215507, 100.0),\n",
       " (140.00088625840999, 140.0),\n",
       " (69.984876974811627, 70.0),\n",
       " (199.99552266230589, 200.0),\n",
       " (42.00215482401132, 42.0),\n",
       " (60.001217134718196, 60.0),\n",
       " (140.02112537814267, 140.0),\n",
       " (12.003903910178556, 12.0),\n",
       " (60.013477224633149, 60.0),\n",
       " (83.99664336736997, 84.0)]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zip(model.coef_, frecency_points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:11.239433Z",
     "start_time": "2018-07-06T00:13:11.216532Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.00622753,  0.00393347,  0.00307716, -0.00035389, -0.00429515,\n",
       "        0.00855775,  0.00088626, -0.01512303, -0.00447734,  0.00215482,\n",
       "        0.00121713,  0.02112538,  0.00390391,  0.01347722, -0.00335663])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "model.coef_ - frecency_points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ranking and SVM loss\n",
    "\n",
    "Now, we make the problem slightly more difficult: Instead of just learning the frecency function from data, we try to learn it from user interactions. The training data now consists of a variable number of history suggestions and their respective features. The label corresponds to the suggestion that the user clicked on. We still assume that the user clicks on the item with the highest frecency score."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Preprocessing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gradient descent generally works better when the data is centered around the origin:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:13.055710Z",
     "start_time": "2018-07-06T00:13:13.036010Z"
    }
   },
   "outputs": [],
   "source": [
    "from utils import normalize"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:20.508354Z",
     "start_time": "2018-07-06T00:13:13.429733Z"
    }
   },
   "outputs": [],
   "source": [
    "X = normalize(X)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Optimizers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:20.572382Z",
     "start_time": "2018-07-06T00:13:20.510420Z"
    }
   },
   "outputs": [],
   "source": [
    "from optimizers import GradientDescent, AdaptiveGradientDescent, DecayedGradientDescent, RProp, Adam"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hinge Loss (SVM loss)\n",
    "\n",
    "To supervise training, we keep logging the loss:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:20.680592Z",
     "start_time": "2018-07-06T00:13:20.574513Z"
    }
   },
   "outputs": [],
   "source": [
    "def svm_loss(preds, ys, delta=0):\n",
    "    correct = ys.argmax()\n",
    "    score_correct = preds[correct]\n",
    "    \n",
    "    loss = 0\n",
    "    \n",
    "    for i, pred in enumerate(preds):\n",
    "        loss += max(0, pred + delta - score_correct)            \n",
    "            \n",
    "    return loss"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Helpers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "During training, we want to supervise the learning process and save the best models."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:20.790356Z",
     "start_time": "2018-07-06T00:13:20.683111Z"
    }
   },
   "outputs": [],
   "source": [
    "from utils import ModelCheckpoint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "accuracy needs to be measured carefully here: In our simulation, we assume that the current frecency is the perfect ranking function. But because items sometimes get the same frecency scores, there can be more than one correct answer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:20.902274Z",
     "start_time": "2018-07-06T00:13:20.792321Z"
    }
   },
   "outputs": [],
   "source": [
    "def rank_accuracy(y, preds):\n",
    "    correct = 0.\n",
    "    \n",
    "    for yi, pi in zip(y, preds):\n",
    "        if yi[pi.argmax()] == yi.max():\n",
    "            correct += 1\n",
    "            \n",
    "    return correct / len(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `SVMRanking` class is the main mechanism for fitting models."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:13:21.036099Z",
     "start_time": "2018-07-06T00:13:20.904264Z"
    }
   },
   "outputs": [],
   "source": [
    "class SVMRanking:\n",
    "    def __init__(self, delta):\n",
    "        self.delta = delta\n",
    "        \n",
    "    def fit(self, data_generator, optimizer, num_iterations=10, callbacks=[]):\n",
    "        X, y = data_generator(1)\n",
    "        num_features = X[0].shape[1]\n",
    "        self.W = frecency_points + (np.random.random(size=(num_features)) - 0.5) * 100\n",
    "        \n",
    "        for j in range(num_iterations):\n",
    "            X, y = data_generator(4000)\n",
    "            \n",
    "            preds = self.predict(X)\n",
    "            gradient = np.zeros(num_features)\n",
    "\n",
    "            for xi, pi, yi in zip(X, preds, y):\n",
    "                correct = yi.argmax()\n",
    "                score_correct = pi[correct]\n",
    "\n",
    "                for i, predicted_score in enumerate(pi):\n",
    "                    gradient -= xi[i] * max(0, predicted_score + self.delta - score_correct)\n",
    "            \n",
    "            gradient /= len(X)\n",
    "            \n",
    "            loss = np.mean([svm_loss(pi, yi) for pi, yi in zip(self.predict(X), y)])\n",
    "            accuracy = rank_accuracy(y, model.predict(X))\n",
    "            \n",
    "            print(\"[%d/%d] training: %.5f loss, %.3f accuracy\" % (j + 1, num_iterations, loss, accuracy))\n",
    "            \n",
    "            for callback in callbacks:\n",
    "                callback(self)\n",
    "            \n",
    "            self.W += optimizer(gradient)\n",
    "            \n",
    "    def predict(self, X):\n",
    "        preds = []\n",
    "        \n",
    "        for x in X:\n",
    "            scores = x.dot(self.W)\n",
    "            preds.append(scores)\n",
    "        \n",
    "        return preds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Training"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:14:26.871877Z",
     "start_time": "2018-07-06T00:13:21.038362Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1/48] training: 11.71683 loss, 0.738 accuracy\n",
      "[ModelCheckpoint] New best model with 0.73150 validation accuracy\n",
      "[2/48] training: 122.41008 loss, 0.731 accuracy\n",
      "validation: 0.721 accuracy\n",
      "[3/48] training: 55.80964 loss, 0.906 accuracy\n",
      "[ModelCheckpoint] New best model with 0.91160 validation accuracy\n",
      "[4/48] training: 6.76885 loss, 0.954 accuracy\n",
      "[ModelCheckpoint] New best model with 0.95830 validation accuracy\n",
      "[5/48] training: 2.21581 loss, 0.958 accuracy\n",
      "[ModelCheckpoint] New best model with 0.96020 validation accuracy\n",
      "[6/48] training: 1.10265 loss, 0.965 accuracy\n",
      "[ModelCheckpoint] New best model with 0.96490 validation accuracy\n",
      "[7/48] training: 0.85294 loss, 0.981 accuracy\n",
      "[ModelCheckpoint] New best model with 0.98130 validation accuracy\n",
      "[8/48] training: 0.57912 loss, 0.980 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[9/48] training: 0.32446 loss, 0.982 accuracy\n",
      "validation: 0.981 accuracy\n",
      "[10/48] training: 0.32911 loss, 0.980 accuracy\n",
      "[ModelCheckpoint] New best model with 0.98140 validation accuracy\n",
      "[11/48] training: 0.19747 loss, 0.982 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[12/48] training: 0.20725 loss, 0.976 accuracy\n",
      "validation: 0.981 accuracy\n",
      "[13/48] training: 0.13382 loss, 0.979 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[14/48] training: 0.12088 loss, 0.981 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[15/48] training: 0.14444 loss, 0.980 accuracy\n",
      "validation: 0.981 accuracy\n",
      "[16/48] training: 0.07397 loss, 0.981 accuracy\n",
      "validation: 0.979 accuracy\n",
      "[17/48] training: 0.11807 loss, 0.980 accuracy\n",
      "[ModelCheckpoint] New best model with 0.98220 validation accuracy\n",
      "[18/48] training: 0.10564 loss, 0.977 accuracy\n",
      "validation: 0.981 accuracy\n",
      "[19/48] training: 0.05892 loss, 0.980 accuracy\n",
      "validation: 0.981 accuracy\n",
      "[20/48] training: 0.05180 loss, 0.981 accuracy\n",
      "[ModelCheckpoint] New best model with 0.98290 validation accuracy\n",
      "[21/48] training: 0.04937 loss, 0.980 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[22/48] training: 0.06325 loss, 0.977 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[23/48] training: 0.02504 loss, 0.982 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[24/48] training: 0.04105 loss, 0.981 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[25/48] training: 0.03999 loss, 0.978 accuracy\n",
      "validation: 0.978 accuracy\n",
      "[26/48] training: 0.04406 loss, 0.980 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[27/48] training: 0.03507 loss, 0.981 accuracy\n",
      "validation: 0.983 accuracy\n",
      "[28/48] training: 0.03034 loss, 0.978 accuracy\n",
      "validation: 0.981 accuracy\n",
      "[29/48] training: 0.02061 loss, 0.978 accuracy\n",
      "validation: 0.979 accuracy\n",
      "[30/48] training: 0.02439 loss, 0.979 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[31/48] training: 0.01800 loss, 0.977 accuracy\n",
      "validation: 0.979 accuracy\n",
      "[32/48] training: 0.01398 loss, 0.981 accuracy\n",
      "validation: 0.981 accuracy\n",
      "[33/48] training: 0.01017 loss, 0.981 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[34/48] training: 0.01032 loss, 0.985 accuracy\n",
      "validation: 0.981 accuracy\n",
      "[35/48] training: 0.00939 loss, 0.980 accuracy\n",
      "validation: 0.979 accuracy\n",
      "[36/48] training: 0.01502 loss, 0.977 accuracy\n",
      "validation: 0.979 accuracy\n",
      "[37/48] training: 0.00746 loss, 0.979 accuracy\n",
      "validation: 0.979 accuracy\n",
      "[38/48] training: 0.00704 loss, 0.979 accuracy\n",
      "validation: 0.979 accuracy\n",
      "[39/48] training: 0.00586 loss, 0.982 accuracy\n",
      "validation: 0.979 accuracy\n",
      "[40/48] training: 0.00901 loss, 0.981 accuracy\n",
      "validation: 0.979 accuracy\n",
      "[41/48] training: 0.00558 loss, 0.981 accuracy\n",
      "validation: 0.979 accuracy\n",
      "[42/48] training: 0.00382 loss, 0.980 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[43/48] training: 0.00282 loss, 0.980 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[44/48] training: 0.00435 loss, 0.979 accuracy\n",
      "validation: 0.979 accuracy\n",
      "[45/48] training: 0.00344 loss, 0.981 accuracy\n",
      "validation: 0.982 accuracy\n",
      "[46/48] training: 0.00313 loss, 0.976 accuracy\n",
      "validation: 0.980 accuracy\n",
      "[47/48] training: 0.00344 loss, 0.982 accuracy\n",
      "validation: 0.978 accuracy\n",
      "[48/48] training: 0.00299 loss, 0.983 accuracy\n",
      "validation: 0.982 accuracy\n"
     ]
    }
   ],
   "source": [
    "np.random.seed(0)\n",
    "model = SVMRanking(delta=0.)\n",
    "model.fit(data_generator=sample_suggestions,\n",
    "          optimizer=GradientDescent(30.),\n",
    "          num_iterations=48,\n",
    "          callbacks=[ModelCheckpoint(rank_accuracy, sample_suggestions)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:17:03.147327Z",
     "start_time": "2018-07-06T00:15:57.407354Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1/48] training: 11.71683 loss, 0.738 accuracy\n",
      "[ModelCheckpoint] New best model with 0.73150 validation accuracy\n",
      "[2/48] training: 13.43970 loss, 0.728 accuracy\n",
      "validation: 0.721 accuracy\n",
      "[3/48] training: 11.48569 loss, 0.748 accuracy\n",
      "[ModelCheckpoint] New best model with 0.73510 validation accuracy\n",
      "[4/48] training: 11.15089 loss, 0.749 accuracy\n",
      "validation: 0.734 accuracy\n",
      "[5/48] training: 11.64325 loss, 0.739 accuracy\n",
      "[ModelCheckpoint] New best model with 0.74280 validation accuracy\n",
      "[6/48] training: 10.64545 loss, 0.849 accuracy\n",
      "[ModelCheckpoint] New best model with 0.84070 validation accuracy\n",
      "[7/48] training: 10.95008 loss, 0.839 accuracy\n",
      "validation: 0.837 accuracy\n",
      "[8/48] training: 11.11485 loss, 0.834 accuracy\n",
      "validation: 0.838 accuracy\n",
      "[9/48] training: 9.85802 loss, 0.845 accuracy\n",
      "validation: 0.829 accuracy\n",
      "[10/48] training: 10.26959 loss, 0.839 accuracy\n",
      "validation: 0.839 accuracy\n",
      "[11/48] training: 10.19416 loss, 0.834 accuracy\n",
      "validation: 0.840 accuracy\n",
      "[12/48] training: 8.56436 loss, 0.838 accuracy\n",
      "validation: 0.838 accuracy\n",
      "[13/48] training: 8.43679 loss, 0.836 accuracy\n",
      "validation: 0.837 accuracy\n",
      "[14/48] training: 7.54865 loss, 0.838 accuracy\n",
      "validation: 0.838 accuracy\n",
      "[15/48] training: 6.76996 loss, 0.846 accuracy\n",
      "[ModelCheckpoint] New best model with 0.84470 validation accuracy\n",
      "[16/48] training: 6.35255 loss, 0.836 accuracy\n",
      "validation: 0.841 accuracy\n",
      "[17/48] training: 5.25627 loss, 0.845 accuracy\n",
      "validation: 0.841 accuracy\n",
      "[18/48] training: 4.95672 loss, 0.836 accuracy\n",
      "validation: 0.842 accuracy\n",
      "[19/48] training: 3.83310 loss, 0.847 accuracy\n",
      "[ModelCheckpoint] New best model with 0.85160 validation accuracy\n",
      "[20/48] training: 3.37146 loss, 0.852 accuracy\n",
      "[ModelCheckpoint] New best model with 0.86440 validation accuracy\n",
      "[21/48] training: 3.19823 loss, 0.859 accuracy\n",
      "[ModelCheckpoint] New best model with 0.86970 validation accuracy\n",
      "[22/48] training: 2.33854 loss, 0.868 accuracy\n",
      "validation: 0.859 accuracy\n",
      "[23/48] training: 2.25716 loss, 0.868 accuracy\n",
      "validation: 0.864 accuracy\n",
      "[24/48] training: 1.64944 loss, 0.868 accuracy\n",
      "validation: 0.863 accuracy\n",
      "[25/48] training: 1.81462 loss, 0.868 accuracy\n",
      "validation: 0.868 accuracy\n",
      "[26/48] training: 1.41966 loss, 0.950 accuracy\n",
      "[ModelCheckpoint] New best model with 0.94650 validation accuracy\n",
      "[27/48] training: 1.26415 loss, 0.948 accuracy\n",
      "validation: 0.946 accuracy\n",
      "[28/48] training: 0.97492 loss, 0.945 accuracy\n",
      "[ModelCheckpoint] New best model with 0.94890 validation accuracy\n",
      "[29/48] training: 0.69980 loss, 0.961 accuracy\n",
      "[ModelCheckpoint] New best model with 0.95650 validation accuracy\n",
      "[30/48] training: 0.63502 loss, 0.949 accuracy\n",
      "validation: 0.948 accuracy\n",
      "[31/48] training: 0.45750 loss, 0.954 accuracy\n",
      "validation: 0.951 accuracy\n",
      "[32/48] training: 0.38181 loss, 0.948 accuracy\n",
      "validation: 0.953 accuracy\n",
      "[33/48] training: 0.30913 loss, 0.942 accuracy\n",
      "validation: 0.946 accuracy\n",
      "[34/48] training: 0.19486 loss, 0.970 accuracy\n",
      "[ModelCheckpoint] New best model with 0.96670 validation accuracy\n",
      "[35/48] training: 0.12802 loss, 0.889 accuracy\n",
      "validation: 0.894 accuracy\n",
      "[36/48] training: 0.12336 loss, 0.969 accuracy\n",
      "[ModelCheckpoint] New best model with 0.97210 validation accuracy\n",
      "[37/48] training: 0.04596 loss, 0.970 accuracy\n",
      "validation: 0.972 accuracy\n",
      "[38/48] training: 0.04869 loss, 0.973 accuracy\n",
      "validation: 0.972 accuracy\n",
      "[39/48] training: 0.04960 loss, 0.970 accuracy\n",
      "validation: 0.972 accuracy\n",
      "[40/48] training: 0.03582 loss, 0.964 accuracy\n",
      "validation: 0.968 accuracy\n",
      "[41/48] training: 0.03337 loss, 0.973 accuracy\n",
      "[ModelCheckpoint] New best model with 0.97330 validation accuracy\n",
      "[42/48] training: 0.01440 loss, 0.971 accuracy\n",
      "validation: 0.973 accuracy\n",
      "[43/48] training: 0.01551 loss, 0.973 accuracy\n",
      "validation: 0.970 accuracy\n",
      "[44/48] training: 0.01612 loss, 0.971 accuracy\n",
      "validation: 0.972 accuracy\n",
      "[45/48] training: 0.00739 loss, 0.972 accuracy\n",
      "validation: 0.973 accuracy\n",
      "[46/48] training: 0.00419 loss, 0.975 accuracy\n",
      "validation: 0.972 accuracy\n",
      "[47/48] training: 0.00507 loss, 0.971 accuracy\n",
      "validation: 0.971 accuracy\n",
      "[48/48] training: 0.00589 loss, 0.974 accuracy\n",
      "validation: 0.971 accuracy\n"
     ]
    }
   ],
   "source": [
    "np.random.seed(0)\n",
    "opt = AdaptiveGradientDescent(0.1, len(frecency_points))\n",
    "model = SVMRanking(delta=0.)\n",
    "model.fit(data_generator=sample_suggestions,\n",
    "          optimizer=opt,\n",
    "          num_iterations=48,\n",
    "          callbacks=[ModelCheckpoint(rank_accuracy,  sample_suggestions)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After fitting, we can compare the learned weights with the true frecency scores. Note that the values themselves are very different now but that the ordering is nearly the same as in the real algorithm. This shows that we are ranking very similarly to the real algorithm but that the optimization process did not fully reach the global optimum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:17:03.195582Z",
     "start_time": "2018-07-06T00:17:03.149428Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(12.0, 14.328107294741949),\n",
       " (14.0, 10.147936225293185),\n",
       " (20.0, 34.335460264505343),\n",
       " (36.0, 34.335334892244539),\n",
       " (42.0, 34.338056202528762),\n",
       " (60.0, 34.335892421808076),\n",
       " (60.0, 34.350521497586705),\n",
       " (70.0, 34.335328740904643),\n",
       " (84.0, 61.827233423435842),\n",
       " (98.0, 61.827444877537495),\n",
       " (100.0, 61.827442586893319),\n",
       " (120.0, 116.45108591309054),\n",
       " (140.0, 116.45141094451398),\n",
       " (140.0, 116.45498071467374),\n",
       " (200.0, 244.46689170495839)]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ais = np.argsort(frecency_points)\n",
    "zip(frecency_points[ais], model.W[ais])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Still, the model is correct most of the time:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:17:04.078878Z",
     "start_time": "2018-07-06T00:17:03.197775Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.97"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X, y = sample_suggestions(10000)\n",
    "rank_accuracy(y, model.predict(X))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Side note: Evaluation during training in production\n",
    "\n",
    "If we only use 400 data points for validating the current model, then this is not enough to properly assess the model quality.\n",
    "The accuracies jump too much.\n",
    "However, this evaluation could still be used to test that the model is not completely off."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:17:38.255248Z",
     "start_time": "2018-07-06T00:17:04.080871Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([   3.,    2.,   25.,   35.,  188.,  222.,  219.,  232.,   60.,   13.]),\n",
       " array([ 0.935,  0.941,  0.947,  0.953,  0.959,  0.965,  0.971,  0.977,\n",
       "         0.983,  0.989,  0.995]),\n",
       " <a list of 10 Patch objects>)"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAhQAAAFkCAYAAAB4sKK5AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAAPYQAAD2EBqD+naQAAG1VJREFUeJzt3X+U3XV95/HnG5EgeBJOTUnK2iwoEsMepTvDAtkKZRcV\nhS5YaStTUyzUZVmR1WnPWXXXHxTOrgdbCYuVs+yppVJ0eljUgiyQuoiU3/QkuIIOQWhwlB+RkZik\nxCGBvPeP73dObi4zSWY+9zvfmeT5OOceMp/vZ+59fz98597X/Xx/RWYiSZJUYr+2C5AkSXOfgUKS\nJBUzUEiSpGIGCkmSVMxAIUmSihkoJElSMQOFJEkqZqCQJEnFDBSSJKmYgUKSJBWbUqCIiE9ExIMR\nsSki1kfENyLiqK4+10TE9q7HLV195kXEFyNiNCI2R8QNEXFoL1ZIkiTNvKnOUJwIfAE4Hng78Grg\n7yLiNV39bgUWAYvrx0DX8iuA04GzgJOAw4CvTbEWSZI0S0TJzcEiYiHwU+CkzLy7brsGWJCZ753k\nd+YDzwFnZ+Y36ralwDBwQmY+OO2CJElSK0qPoTgESOD5rvaT610ij0bEVRHxSx3L+oH9gdvHGzJz\nLTACLC+sR5IktWD/6f5iRATVrou7M/MHHYtupdp9sQ54I/BZ4JaIWJ7VdMhiYGtmbup6yvX1sole\n63XAqcCTwNh0a5YkaR90IHA4sCozf9bUi0w7UABXAUcDv97ZmJnXd/z4/Yh4GHgCOBm4Y5qvdSrw\nlWn+riRJgvcDX23qyacVKCLiz4HTgBMz85ld9c3MdRExChxJFSieBQ6IiPldsxSL6mUTeRLguuuu\nY9myZdMpea8yODjIypUr2y6jdY5DxXHYwbGoOA47OBYwPDzMihUroP4sbcqUA0UdJs4EfiMzR/ag\n/+uB1wHjwWM18BJwCtB5UOYS4L5JnmYMYNmyZfT19U215L3OggULHAcch3GOww6ORcVx2MGx2Emj\nhwxMKVBExFVUp4CeAbwQEYvqRRszcywiDgY+Q3UMxbNUsxKXAY8BqwAyc1NEfAm4PCI2AJuBK4F7\nPMNDkqS5aaozFBdQndXxna72c4FrgZeBtwLnUJ0B8jRVkPh0Zm7r6D9Y970BmAfcBlw4xVokSdIs\nMaVAkZm7PM00M8eAd+3B87wIXFQ/JEnSHOe9POaggYHuC4/umxyHiuOwg2NRcRx2cCxmTtGVMmdK\nRPQBq1evXu3BNZIkTcGaNWvo7+8H6M/MNU29jjMUkiSpmIFCkiQVM1BIkqRiBgpJklTMQCFJkooZ\nKCRJUjEDhSRJKmagkCRJxQwUkiSpmIFCkiQVM1BIkqRiBgpJklTMQCFJkooZKCRJUrH92y5AkvZ1\nIyMjjI6Otl3GpBYuXMiSJUvaLkOznIFCklo0MjLC0qXLGBvb0nYpkzrwwINYu3bYUKFdMlBIUotG\nR0frMHEdsKztciYwzNjYCkZHRw0U2iUDhSTNCsuAvraLkKbNgzIlSVIxA4UkSSpmoJAkScUMFJIk\nqZiBQpIkFTNQSJKkYgYKSZJUzEAhSZKKeWErST3h/SikfZuBQlIx70chyUAhqZj3o5BkoJDUQ96P\nQtpXGSgk7TOGh4fbLuEVZmNN0nQYKCTtA54B9mPFihVtFyLttQwUkvYBPwe2MzuP8bgF+FTbRUjF\nDBSS9iGz8RgPd3lo7+CFrSRJUjEDhSRJKmagkCRJxQwUkiSpmIFCkiQVM1BIkqRiBgpJklTMQCFJ\nkooZKCRJUjEDhSRJKmagkCRJxQwUkiSpmIFCkiQVM1BIkqRiBgpJklRsSoEiIj4REQ9GxKaIWB8R\n34iIoybod0lEPB0RWyLiWxFxZNfyeRHxxYgYjYjNEXFDRBxaujKSJKkdU52hOBH4AnA88Hbg1cDf\nRcRrxjtExMeADwPnA8cBLwCrIuKAjue5AjgdOAs4CTgM+No010GSJLVs/6l0zszTOn+OiD8Afgr0\nA3fXzR8BLs3Mm+s+5wDrgfcA10fEfOA84OzMvLPucy4wHBHHZeaD018dSZLUhtJjKA4BEngeICKO\nABYDt493yMxNwAPA8rrpWKog09lnLTDS0UeSJM0h0w4UERFUuy7uzswf1M2LqQLG+q7u6+tlAIuA\nrXXQmKyPJEmaQ6a0y6PLVcDRwK/3qJbdGhwcZMGCBTu1DQwMMDAwMFMlSJI0aw0NDTE0NLRT28aN\nG2fktacVKCLiz4HTgBMz85mORc8CQTUL0TlLsQh4qKPPARExv2uWYlG9bFIrV66kr69vOiVLkrTX\nm+hL9po1a+jv72/8tae8y6MOE2cC/yYzRzqXZeY6qlBwSkf/+VRnhdxbN60GXurqsxRYAtw31Xok\nSVL7pjRDERFXAQPAGcALEbGoXrQxM8fqf18BfDIiHgeeBC4FfgLcCNVBmhHxJeDyiNgAbAauBO7x\nDA9Jkuamqe7yuIDqoMvvdLWfC1wLkJmfi4iDgKupzgK5C3h3Zm7t6D8IvAzcAMwDbgMunGrxkiRp\ndpjqdSj2aBdJZl4MXLyL5S8CF9UPSZI0x3kvD0mSVMxAIUmSihkoJElSMQOFJEkqZqCQJEnFDBSS\nJKmYgUKSJBUzUEiSpGIldxuVNINGRkYYHR1tu4wJDQ8Pt12CpJYZKKQ5YGRkhKVLlzE2tqXtUiRp\nQgYKaQ4YHR2tw8R1wLK2y5nALcCn2i5CUosMFNKcsgzoa7uICbjLQ9rXeVCmJEkqZqCQJEnFDBSS\nJKmYgUKSJBUzUEiSpGIGCkmSVMxAIUmSihkoJElSMQOFJEkqZqCQJEnFDBSSJKmYgUKSJBUzUEiS\npGIGCkmSVMxAIUmSihkoJElSMQOFJEkqZqCQJEnFDBSSJKmYgUKSJBUzUEiSpGIGCkmSVMxAIUmS\nihkoJElSMQOFJEkqZqCQJEnFDBSSJKmYgUKSJBUzUEiSpGIGCkmSVMxAIUmSihkoJElSMQOFJEkq\nZqCQJEnFDBSSJKmYgUKSJBUzUEiSpGIGCkmSVMxAIUmSik05UETEiRFxU0Q8FRHbI+KMruXX1O2d\nj1u6+syLiC9GxGhEbI6IGyLi0NKVkSRJ7ZjODMXBwHeBDwE5SZ9bgUXA4vox0LX8CuB04CzgJOAw\n4GvTqEWSJM0C+0/1FzLzNuA2gIiISbq9mJnPTbQgIuYD5wFnZ+adddu5wHBEHJeZD061JkmS1K6m\njqE4OSLWR8SjEXFVRPxSx7J+qiBz+3hDZq4FRoDlDdUjSZIaNOUZij1wK9Xui3XAG4HPArdExPLM\nTKpdIFszc1PX762vl0mSpDmm54EiM6/v+PH7EfEw8ARwMnBHyXMPDg6yYMGCndoGBgYYGOg+REOS\npH3P0NAQQ0NDO7Vt3LhxRl67iRmKnWTmuogYBY6kChTPAgdExPyuWYpF9bJJrVy5kr6+vuaKlSRp\nDpvoS/aaNWvo7+9v/LUbvw5FRLweeB3wTN20GngJOKWjz1JgCXBf0/VIkqTem/IMRUQcTDXbMH6G\nxxsi4hjg+frxGapjKJ6t+10GPAasAsjMTRHxJeDyiNgAbAauBO7xDA9Jkuam6ezyOJZq10XWj8/X\n7V+mujbFW4FzgEOAp6mCxKczc1vHcwwCLwM3APOoTkO9cBq1SJKkWWA616G4k13vKnnXHjzHi8BF\n9UOSJM1x3stDkiQVM1BIkqRiBgpJklTMQCFJkooZKCRJUjEDhSRJKmagkCRJxQwUkiSpmIFCkiQV\nM1BIkqRiBgpJklTMQCFJkooZKCRJUjEDhSRJKmagkCRJxQwUkiSpmIFCkiQVM1BIkqRiBgpJklTM\nQCFJkooZKCRJUjEDhSRJKmagkCRJxQwUkiSpmIFCkiQVM1BIkqRiBgpJklTMQCFJkooZKCRJUjED\nhSRJKmagkCRJxQwUkiSpmIFCkiQVM1BIkqRiBgpJklTMQCFJkooZKCRJUjEDhSRJKmagkCRJxQwU\nkiSpmIFCkiQVM1BIkqRiBgpJklTMQCFJkooZKCRJUjEDhSRJKmagkCRJxQwUkiSpmIFCkiQVM1BI\nkqRiBgpJklRsyoEiIk6MiJsi4qmI2B4RZ0zQ55KIeDoitkTEtyLiyK7l8yLiixExGhGbI+KGiDi0\nZEUkSVJ7pjNDcTDwXeBDQHYvjIiPAR8GzgeOA14AVkXEAR3drgBOB84CTgIOA742jVokSdIssP9U\nfyEzbwNuA4iImKDLR4BLM/Pmus85wHrgPcD1ETEfOA84OzPvrPucCwxHxHGZ+eC01kSSJLWmp8dQ\nRMQRwGLg9vG2zNwEPAAsr5uOpQoynX3WAiMdfSRJ0hzS64MyF1PtBlnf1b6+XgawCNhaB43J+kiS\npDlkyrs82jQ4OMiCBQt2ahsYGGBgYKCliiRJmj2GhoYYGhraqW3jxo0z8tq9DhTPAkE1C9E5S7EI\neKijzwERMb9rlmJRvWxSK1eupK+vr4flSpK095joS/aaNWvo7+9v/LV7ussjM9dRhYJTxtvqgzCP\nB+6tm1YDL3X1WQosAe7rZT2SJGlmTHmGIiIOBo6kmokAeENEHAM8n5k/pjol9JMR8TjwJHAp8BPg\nRqgO0oyILwGXR8QGYDNwJXCPZ3hIkjQ3TWeXx7HAHVQHXybw+br9y8B5mfm5iDgIuBo4BLgLeHdm\nbu14jkHgZeAGYB7VaagXTmsNJElS66ZzHYo72c2uksy8GLh4F8tfBC6qH5IkaY7zXh6SJKmYgUKS\nJBUzUEiSpGIGCkmSVMxAIUmSihkoJElSMQOFJEkqZqCQJEnFDBSSJKmYgUKSJBUzUEiSpGIGCkmS\nVMxAIUmSihkoJElSMQOFJEkqZqCQJEnFDBSSJKmYgUKSJBUzUEiSpGIGCkmSVMxAIUmSihkoJElS\nMQOFJEkqZqCQJEnFDBSSJKmYgUKSJBUzUEiSpGIGCkmSVMxAIUmSihkoJElSMQOFJEkqZqCQJEnF\nDBSSJKmYgUKSJBUzUEiSpGIGCkmSVMxAIUmSihkoJElSMQOFJEkqZqCQJEnFDBSSJKmYgUKSJBUz\nUEiSpGL7t12AJGn2Gx4ebruESS1cuJAlS5a0XcY+z0AhSdqFZ4D9WLFiRduFTOrAAw9i7dphQ0XL\nDBSSpF34ObAduA5Y1nItExlmbGwFo6OjBoqWGSgkSXtgGdDXdhGaxTwoU5IkFTNQSJKkYgYKSZJU\nzEAhSZKK9TxQRMRnImJ71+MHXX0uiYinI2JLRHwrIo7sdR2SJGnmNDVD8QiwCFhcP942viAiPgZ8\nGDgfOA54AVgVEQc0VIskSWpYU6eNvpSZz02y7CPApZl5M0BEnAOsB94DXN9QPZIkqUFNzVC8KSKe\niognIuK6iPhVgIg4gmrG4vbxjpm5CXgAWN5QLZIkqWFNBIr7gT8ATgUuAI4A/j4iDqYKE0k1I9Fp\nfb1MkiTNQT3f5ZGZqzp+fCQiHgR+BPwu8GjJcw8ODrJgwYKd2gYGBhgYGCh5WkmS9gpDQ0MMDQ3t\n1LZx48YZee3GL72dmRsj4jHgSOA7QFAdsNk5S7EIeGh3z7Vy5Ur6+rz0qyRJE5noS/aaNWvo7+9v\n/LUbvw5FRLyWKkw8nZnrgGeBUzqWzweOB+5tuhZJktSMns9QRMSfAt+k2s3xz4A/AbYBf1N3uQL4\nZEQ8DjwJXAr8BLix17VIkqSZ0cQuj9cDXwVeBzwH3A2ckJk/A8jMz0XEQcDVwCHAXcC7M3NrA7VI\nkqQZ0MRBmbs9QjIzLwYu7vVrS5KkdngvD0mSVMxAIUmSihkoJElSMQOFJEkqZqCQJEnFDBSSJKmY\ngUKSJBUzUEiSpGIGCkmSVMxAIUmSihkoJElSMQOFJEkq1sTdRqU5aWRkhNHR0bbLmNDw8HDbJUjS\nLhkoJKowsXTpMsbGtrRdiiTNSQYKCRgdHa3DxHXAsrbLmcAtwKfaLkKSJmWgkHayDOhru4gJuMtD\n0uzmQZmSJKmYgUKSJBUzUEiSpGIGCkmSVMxAIUmSihkoJElSMQOFJEkqZqCQJEnFvLCVZoz3ypCk\nvZeBQjPCe2VI0t7NQKEZ4b0yJGnvZqDQDPNeGZK0N/KgTEmSVMxAIUmSihkoJElSMQOFJEkqZqCQ\nJEnFDBSSJKmYgUKSJBUzUEiSpGIGCkmSVMxAIUmSihkoJElSMe/lIUma84aHZ+/9eBYuXMiSJUva\nLqNxBgpJ0hz2DLAfK1asaLuQSR144EGsXTu814cKA4UkaQ77ObAduI7qbsazzTBjYysYHR01UEiS\nNPstA/raLmKf5kGZkiSpmIFCkiQVM1BIkqRiBgpJklTMQCFJkooZKCRJUjEDhSRJKmagmIOGhoba\nLmGWcBwqjsMOjkXFcdjBsZgprQaKiLgwItZFxC8i4v6I+Fdt1jNXGCjGOQ4Vx2EHx6LiOOzgWMyU\n1q6UGRHvAz4PnA88CAwCqyLiqMwcbauuyaxbt44TTngbGzb8rO1SeOmlbRxwwIGvaH/nO0/j5pu/\n3kJFkqR9XZuX3h4Ers7MawEi4gLgdOA84HMt1jWhRx55hJ/+9GngvwPzW67mf7Jt2wVdbd/m9ttX\nsWbNmlYq2p3ZfCdASVK5VgJFRLwa6Kf6dAYgMzMi/i+wvI2a9tx5wKKWa1gFXNjVtp6xsRvp7+9v\noyBJ0j6urRmKhcCrgPVd7euBpRP0PxDa/Zb7xBNP1P/6a9qfofgR8L+62u4DXgb+EPiVGa9o9x4G\nbgRuAXr1//EnwFd69Fz31P/tZX29tKv6ejkO0zVbxm+ysZgt9U2kidr829ih7b+PdUC7n18dr/3K\nfeU9FJnZ5PNP/KIRvwI8BSzPzAc62i8DTsrM5V39f4/23zElSZrL3p+ZX23qyduaoRil+jrdve9g\nEfDsBP1XAe8HngTGGq1MkqS9y4HA4VSfpY1pZYYCICLuBx7IzI/UPwcwAlyZmX/aSlGSJGla2jzL\n43LgryJiNTtOGz0I+KsWa5IkSdPQWqDIzOsjYiFwCdWuju8Cp2bmc23VJEmSpqe1XR6SJGnv4b08\nJElSMQOFJEkq1lqgmOqNwer+P4iILRExHBG/37X8tyLiHyJiQ0T8U0Q8FBErml2Lcr0eh66+Z0fE\n9oiY9Tf4aGB7+EC97i/X/90eEVuaXYveaGKbiIgFEfHFiHg6IsYi4tGIeFdza1GugW3ijo5tofPx\nzWbXpFxD28RH6+1gS0SMRMTlETGvubUo18A2sX9EfDoiHq+f86GIOLXZtSgTESdGxE0R8VS9/Z6x\nB79zckSsrv/2H4uID0zQ53fqMfpFRPy/iHj3lIvLzBl/AO+jup7EOcCbgauB54GFk/T/j8DPgd+m\nOpf2fcAm4PSOPicBZ1JdafMI4D8B24B3tLGObY1DR9/DgR8D3wG+3va6trA9fADYAPwycGj9+OW2\n17WlsXg18A/AN4ETgCXAicBb2l7fGR6HQzq2hUOBo+v3iN9ve31bGIvfA35RL1sCvJ3qkpJ/1vb6\nzvA4XFa/T55a97kA2AIc0/b67mIc3kV1MsOZVNdzOmM3/Q8H/onqHllLqe7bsNNnI/Cv67Y/qvtc\nArwIHD2l2loakPuB/9Hxc9Qb83+epP89wGVdbX8G/P1uXmc18CdtbwAzPQ5UM093A+cC1zD7A0XP\nx4EqUDzf9rrNkrG4APgh8Kq216/NcZjgdz5af+C8pu31bWGb+ALwramMV9uPhsbhKeCCrj43ANe2\nvb57OCbb2X2guAz4XlfbEHBLx89/A9zU1ec+4Kqp1DPjuzxix43Bbh9vy6r6Xd0YbB6vvELmGHBc\nRLxqktc5BTgKuLO05iY0PA6fAdZn5jW9q7gZDY/DayPiyXo6928j4ugelt5zDY7Fv6N+c4iIZyPi\n4Yj4RETMymOoZuo9gupOf0OZ+YuyipvT4FjcC/SP7zKIiDcApwH/p3fV906D4zCP6pt4p18Abyut\neRY5gWqcOq1i53Fbvgd9dquNN5Rd3Rhs8SS/swr4YET0AUTEsVR3wXp1/XzU7fMjYnNEbKWa3r0o\nM7/d4/p7pZFxiIi3Uc1MfLCBmpvQ1PawluoD4wyqy7bvB9wbEYf1tPreamos3gD8DtUYvJtqOvOP\ngf/ay+J7qLH3iHERcRzwL4C/6FHNTWlkLDJziOqLx931++UPgTsy87Ker0FvNLVNrAL+KCKOjMo7\ngPcyO++wOF2LmXjc5nccMzNZn8nGdkKz8hvKBC4FbgXui4htwDfYcUXN7R39NgPHAMdSvVmujIiT\nZrDOpu1yHCLitcC1wL/PzA3tlDgjdrs9ZOb9mXldZn4vM++iepN4DvgPLdTbpD3529iP6s3h/Mx8\nKDP/N/DfqHaF7C329D1i3B8CD2fm6pkpb0btdiwi4mTgv1BtA/+S6u/jNyPikzNdbIP2ZJv4CFWY\nepRqpuJK4C+ZeJvRbrQRKKZ6YzAycywzP0h1ae5/TnUQ0Y+AzdlxZc2s/GP9IbKSal/YJxpYh15o\nYhzeWLd/MyK21X9E5wBnRsTWiDiimVUp0tj20PU7LwEPAUf2qO4mNDUWzwCP1VPE44aBxRHR5uX3\nJ9PoNhERB1EdoDfbZyegubG4BPjrzLwmM7+fmTdSBYyPN7AOvdDIOGTmaGa+d7xPZi4DXgD+sZG1\naMezTDxumzLzxd30mXBsJzPjgSIzt1EdLHnKeFtERP3zvbv53Zcz8+n6jfFsqt0au7If1T6yWaeh\ncXgUeAvwa1QzNccANwHfrv/94x6vRrGZ2h7q4wXeQvXhOis1OBb38MogtRR4pg5as8oMbBO/CxwA\nfKVnRTekwbE4COj+fz8+exE9KL2nmt4mMnNrZj5TH6txFvC3vay/ZffRMW61d9btu+rzjq4+uzeV\nIzh79aD6g97Czqf//Iz6tD7gs8CXO/q/iWo/+JHAcVRHpD4HLOno83GqU5+OqJ/zj6mmsM5tYx3b\nGocJXmMunOXRxPbwqfoP4giqKd0hqm8eb257fVsYi9dTnc1wZd3/dKpvHh9ve31nchw6+t4FfLXt\ndWx5m/hMvU28j+q0wndQTf3P2nFpaByOA36rfp84kerAxMeB+W2v7y7G4WCqL4i/RhUCP1r//KuT\njMPhVIcDXEb1ReJDwFbg7R19llN9Xo6fNnox1QGss/+00XoFPgQ8SXVE7X3AsR3LrgG+3fHzm4E1\nVOfSbgC+Dryp6/kupToQ7wWq6bG7gd9u+3/+TI/DBM8/6wNFQ9vD5cC6+vmepvpW8ta217OtbQI4\nnuqb3BaqD46PUd/LZ7Y+GhqHo6imzv9t2+vX5lhQzd5+Cnisfs98kipwztoP0obG4STg+/XfxU/r\n51jc9nruZgx+gypIvNz1+MuJxqFjPVfX4/ZDJrj2CtXMzKN1n+9R3axzSrV5czBJklRsrpzlIUmS\nZjEDhSRJKmagkCRJxQwUkiSpmIFCkiQVM1BIkqRiBgpJklTMQCFJkooZKCRJUjEDhSRJKmagkCRJ\nxf4/dZdAOWCCv0gAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f7ad7eb3210>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "X, y = sample_suggestions(1000 * 400)\n",
    "accuracies = []\n",
    "\n",
    "for i in range(0, len(X) - 400, 400):\n",
    "    Xi, yi = X[i:i+400], y[i:i+400]\n",
    "    acc = rank_accuracy(yi, model.predict(Xi))\n",
    "    accuracies.append(acc)\n",
    "    \n",
    "plt.hist(sorted(accuracies))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Frequency\n",
    "\n",
    "We still need to take into account that users visit links more than once.\n",
    "How often a user visits a link is sampled from an exponential distribution in this simulation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:17:38.509711Z",
     "start_time": "2018-07-06T00:17:38.257225Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([ 535.,  215.,   97.,   75.,   33.,   20.,   10.,    4.,    3.,    8.]),\n",
       " array([  0. ,   4.3,   8.6,  12.9,  17.2,  21.5,  25.8,  30.1,  34.4,\n",
       "         38.7,  43. ]),\n",
       " <a list of 10 Patch objects>)"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAg4AAAFkCAYAAABIPLOYAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAAPYQAAD2EBqD+naQAAHCpJREFUeJzt3X+w3XV95/HnCzFJwQZckARWY+lS03Ts6HJpMKtiK04t\nYhWXjstdM6ywLkMFhs3sjtRZOmbJ1HVx+FFaXJlZtlapt8OGuqhVEKGlCEjWXIrrek2LghGRLFEM\nmWAIPz77x/cbPTne3Ps599c55/J8zJwh5/P93HPen/lc7n3dz/fzPd+UUpAkSapxSL8LkCRJw8Pg\nIEmSqhkcJElSNYODJEmqZnCQJEnVDA6SJKmawUGSJFUzOEiSpGoGB0mSVM3gIEmSqvUcHJIcl+RT\nSXYmeSrJA0lO7OpzWZJH2+O3JTmh6/jSJNe2r7E7yeYkx8x2MJIkaX71FBySHAncDTwNvBVYA/wH\n4ImOPpcAFwLnAWuBPcCtSZZ0vNTVwOnAmcApwHHATTMehSRJWhDp5SZXST4CrCulvGmKPo8CHy2l\nXNU+Xw7sAP5NKeXG9vnjwFmllM+0fVYDE8DrSilbZjwaSZI0r3o9VfG7wNeS3JhkR5LxJO/bfzDJ\n8cBK4Pb9baWUJ4H7gHVt00nAoV19tgHbO/pIkqQBdGiP/X8Z+H3gCuCPaE5FXJPk6VLKp2hCQ6FZ\nYei0oz0GsALY1waKg/U5QJKjaE6NPAzs7bFmSZJeyJYBvwTcWkr54WxfrNfgcAiwpZTyh+3zB5K8\nGjgf+NRsi5nCW4G/mMfXlyRpsXsP8OnZvkivweEHNHsROk0A/7L992NAaFYVOlcdVgD3d/RZkmR5\n16rDivbYZB4GuOGGG1izZk2PJQ+mDRs2cNVVV/W7jDmzmMazmMYCjmeQLaaxgOMZVBMTE6xfvx7a\n36Wz1WtwuBtY3dW2GvguQCnloSSPAacCX4efbo48Gbi27b8VeLbt07k5chVw70Hedy/AmjVrOPHE\nEw/SZbgcccQRi2YssLjGs5jGAo5nkC2msYDjGQJzcqq/1+BwFXB3kg8CN9IEgvcB/66jz9XApUke\npEk3m4BHgJuh2SyZ5HrgyiRPALuBa4C7vaJCkqTB1lNwKKV8Lcm7gI8Afwg8BFxcSvnLjj6XJzkM\nuA44ErgLOK2Usq/jpTYAzwGbgaXALcAFsxmIJEmaf72uOFBK+QLwhWn6bAQ2TnH8aeCi9iFJkoaE\n96rok9HR0X6XMKcW03gW01jA8QyyxTQWcDwvFD19cmS/tPfC2Lp169bFtlFFkqR5NT4+zsjICMBI\nKWV8tq/nioMkSapmcJAkSdUMDpIkqZrBQZIkVTM4SJKkagYHSZJUzeAgSZKqGRwkSVI1g4MkSapm\ncJAkSdUMDpIkqZrBQZIkVTM4SJKkagYHSZJUzeAgSZKqGRwkSVI1g4MkSapmcJAkSdUMDpIkqZrB\nQZIkVTM4SJKkagYHSZJUzeAgSZKqGRwkSVI1g4MkSap2aL8L6MUHPvABXvrSl/a7jCpHHXUUV1xx\nBYcffni/S5Ekac4MVXC4/fY9JC/qdxkV9lHKZk477TTe+c539rsYSZLmzFAFB7iWUk7sdxEVHgeO\n6XcRkiTNOfc4SJKkagYHSZJUzeAgSZKqGRwkSVI1g4MkSapmcJAkSdUMDpIkqZrBQZIkVTM4SJKk\nagYHSZJUzeAgSZKq9RQcknwoyfNdj2929bksyaNJnkpyW5ITuo4vTXJtkp1JdifZnMQbO0iSNARm\nsuLwDWAFsLJ9vGH/gSSXABcC5wFrgT3ArUmWdHz91cDpwJnAKcBxwE0zKV6SJC2smdwd89lSyuMH\nOXYxsKmU8nmAJGcDO4AzgBuTLAfOBc4qpdzZ9jkHmEiytpSyZQb1SJKkBTKTFYdfSfL9JN9OckOS\nVwAkOZ5mBeL2/R1LKU8C9wHr2qaTaMJKZ59twPaOPpIkaUD1Ghy+CrwXeCtwPnA88HdJDqcJDYVm\nhaHTjvYYNKc49rWB4mB9JEnSgOrpVEUp5daOp99IsgX4LvBu4FtzWdjkNgBHdLWNtg9Jkl7YxsbG\nGBsbO6Bt165dc/oeM9nj8FOllF1J/gE4AfhbIDSrCp2rDiuA+9t/PwYsSbK8a9VhRXtsGlcBJ86m\nZEmSFq3R0VFGRw/8Y3p8fJyRkZE5e49ZfY5DkpfQhIZHSykP0fzyP7Xj+HLgZOCetmkr8GxXn9XA\nKuDe2dQiSZLmX08rDkk+CnyO5vTEPwX+M/AM8Jdtl6uBS5M8CDwMbAIeAW6GZrNkkuuBK5M8AewG\nrgHu9ooKSZIGX6+nKl4OfBo4Cngc+ArwulLKDwFKKZcnOQy4DjgSuAs4rZSyr+M1NgDPAZuBpcAt\nwAWzGYQkSVoYvW6OnHYXYillI7BxiuNPAxe1D0mSNES8V4UkSapmcJAkSdUMDpIkqZrBQZIkVTM4\nSJKkagYHSZJUzeAgSZKqGRwkSVI1g4MkSapmcJAkSdUMDpIkqZrBQZIkVTM4SJKkagYHSZJUzeAg\nSZKqGRwkSVI1g4MkSapmcJAkSdUMDpIkqZrBQZIkVTM4SJKkagYHSZJUzeAgSZKqGRwkSVI1g4Mk\nSapmcJAkSdUMDpIkqZrBQZIkVTM4SJKkagYHSZJUzeAgSZKqGRwkSVI1g4MkSapmcJAkSdUMDpIk\nqZrBQZIkVTM4SJKkagYHSZJUzeAgSZKqGRwkSVK1WQWHJH+Q5PkkV3a1X5bk0SRPJbktyQldx5cm\nuTbJziS7k2xOcsxsapEkSfNvxsEhyW8A5wEPdLVfAlzYHlsL7AFuTbKko9vVwOnAmcApwHHATTOt\nRZIkLYwZBYckLwFuAN4H/Ljr8MXAplLK50sp3wDOpgkGZ7Rfuxw4F9hQSrmzlHI/cA7w+iRrZzYM\nSZK0EGa64nAt8LlSyh2djUmOB1YCt+9vK6U8CdwHrGubTgIO7eqzDdje0UeSJA2gQ3v9giRnAa+l\nCQDdVgIF2NHVvqM9BrAC2NcGioP1kSRJA6in4JDk5TT7E95SSnlmfkqSJEmDqtcVhxHgZcB4krRt\nLwJOSXIh8KtAaFYVOlcdVgD3t/9+DFiSZHnXqsOK9tgUNgBHdLWNtg9Jkl7YxsbGGBsbO6Bt165d\nc/oevQaHLwO/3tX2CWAC+Egp5TtJHgNOBb4OP90MeTLNvgiArcCzbZ/PtH1WA6uAe6d++6uAE3ss\nWZKkF4bR0VFGRw/8Y3p8fJyRkZE5e4+egkMpZQ/wzc62JHuAH5ZSJtqmq4FLkzwIPAxsAh4Bbm5f\n48kk1wNXJnkC2A1cA9xdStkyi7FIkqR51vPmyEmUA56UcnmSw4DrgCOBu4DTSin7OrptAJ4DNgNL\ngVuAC+agFkmSNI9mHRxKKW+epG0jsHGKr3kauKh9SJKkIeG9KiRJUjWDgyRJqmZwkCRJ1QwOkiSp\nmsFBkiRVMzhIkqRqBgdJklTN4CBJkqoZHCRJUjWDgyRJqmZwkCRJ1QwOkiSpmsFBkiRVMzhIkqRq\nBgdJklTN4CBJkqoZHCRJUjWDgyRJqmZwkCRJ1QwOkiSpmsFBkiRVMzhIkqRqBgdJklTN4CBJkqoZ\nHCRJUjWDgyRJqmZwkCRJ1QwOkiSpmsFBkiRVMzhIkqRqBgdJklTN4CBJkqoZHCRJUjWDgyRJqmZw\nkCRJ1QwOkiSpmsFBkiRVMzhIkqRqBgdJklTN4CBJkqoZHCRJUrWegkOS85M8kGRX+7gnye909bks\nyaNJnkpyW5ITuo4vTXJtkp1JdifZnOSYuRiMJEmaX72uOHwPuAQ4ERgB7gBuTrIGIMklwIXAecBa\nYA9wa5IlHa9xNXA6cCZwCnAccNMsxiBJkhbIob10LqX8dVfTpUl+H3gdMAFcDGwqpXweIMnZwA7g\nDODGJMuBc4GzSil3tn3OASaSrC2lbJnVaCRJ0rya8R6HJIckOQs4DLgnyfHASuD2/X1KKU8C9wHr\n2qaTaMJKZ59twPaOPpIkaUD1tOIAkOTVwL3AMmA38K5SyrYk64BCs8LQaQdNoABYAexrA8XB+kiS\npAHVc3AAvgW8BjgC+D3gk0lOmdOqDmpD+7adRtuHJEkvbGNjY4yNjR3QtmvXrjl9j56DQynlWeA7\n7dP7k6yl2dtwORCaVYXOVYcVwP3tvx8DliRZ3rXqsKI9No2raPZlSpKkbqOjo4yOHvjH9Pj4OCMj\nI3P2HnPxOQ6HAEtLKQ/R/PI/df+BdjPkycA9bdNW4NmuPquBVTSnPyRJ0gDracUhyYeBL9JsZvxF\n4D3Am4DfbrtcTXOlxYPAw8Am4BHgZmg2Sya5HrgyyRM0eySuAe72igpJkgZfr6cqjgH+HDgW2AV8\nHfjtUsodAKWUy5McBlwHHAncBZxWStnX8RobgOeAzcBS4BbggtkMQpIkLYxeP8fhfRV9NgIbpzj+\nNHBR+5AkSUPEe1VIkqRqBgdJklTN4CBJkqoZHCRJUjWDgyRJqmZwkCRJ1QwOkiSpmsFBkiRVMzhI\nkqRqBgdJklTN4CBJkqoZHCRJUjWDgyRJqmZwkCRJ1QwOkiSpmsFBkiRVMzhIkqRqBgdJklTN4CBJ\nkqoZHCRJUjWDgyRJqmZwkCRJ1QwOkiSpmsFBkiRVMzhIkqRqBgdJklTN4CBJkqoZHCRJUjWDgyRJ\nqmZwkCRJ1QwOkiSpmsFBkiRVMzhIkqRqBgdJklTN4CBJkqoZHCRJUjWDgyRJqnZovwtYzB5//HHG\nx8f7XUa1o48+mlWrVvW7DEnSADM4zKP3v/8innlmb7/LqLZs2WFs2zZheJAkHZTBYR41oeEGYE2/\nS6kwwd6969m5c6fBQZJ0UAaHebcGOLHfRUiSNCd62hyZ5INJtiR5MsmOJJ9J8qpJ+l2W5NEkTyW5\nLckJXceXJrk2yc4ku5NsTnLMbAcjSZLmV69XVbwR+BPgZOAtwIuBLyX5hf0dklwCXAicB6wF9gC3\nJlnS8TpXA6cDZwKnAMcBN81wDJIkaYH0dKqilPK2zudJ3gv8P2AE+ErbfDGwqZTy+bbP2cAO4Azg\nxiTLgXOBs0opd7Z9zgEmkqwtpWyZ+XAkSdJ8mu3nOBwJFOBHAEmOB1YCt+/vUEp5ErgPWNc2nUQT\nWDr7bAO2d/SRJEkDaMbBIUloTjl8pZTyzbZ5JU2Q2NHVfUd7DGAFsK8NFAfrI0mSBtBsrqr4GPBr\nwOvnqJYKG4AjutpG24ckSS9sY2NjjI2NHdC2a9euOX2PGQWHJH8KvA14YynlBx2HHgNCs6rQueqw\nAri/o8+SJMu7Vh1WtMemcBVe2ihJ0uRGR0cZHT3wj+nx8XFGRkbm7D16PlXRhoZ3Ar9VStneeayU\n8hDNL/9TO/ovp7kK4562aSvwbFef1cAq4N5e65EkSQunpxWHJB+jOS/wDmBPkhXtoV2llP2frXw1\ncGmSB4GHgU3AI8DN0GyWTHI9cGWSJ4DdwDXA3V5RIUnSYOv1VMX5NJsf/7ar/RzgkwCllMuTHAZc\nR3PVxV3AaaWUfR39NwDPAZuBpcAtwAW9Fi9JkhZWr5/jUHVqo5SyEdg4xfGngYvahyRJGhKz/RwH\nSZL0AmJwkCRJ1QwOkiSpmsFBkiRVMzhIkqRqBgdJklTN4CBJkqoZHCRJUjWDgyRJqmZwkCRJ1QwO\nkiSpmsFBkiRVMzhIkqRqBgdJklTN4CBJkqoZHCRJUjWDgyRJqmZwkCRJ1QwOkiSpmsFBkiRVMzhI\nkqRqBgdJklTN4CBJkqoZHCRJUjWDgyRJqmZwkCRJ1QwOkiSpmsFBkiRVMzhIkqRqBgdJklTN4CBJ\nkqoZHCRJUjWDgyRJqmZwkCRJ1QwOkiSpmsFBkiRVMzhIkqRqBgdJklTN4CBJkqoZHCRJUrWeg0OS\nNyb5bJLvJ3k+yTsm6XNZkkeTPJXktiQndB1fmuTaJDuT7E6yOckxsxmIJEmafzNZcTgc+Hvg/UDp\nPpjkEuBC4DxgLbAHuDXJko5uVwOnA2cCpwDHATfNoBZJkrSADu31C0optwC3ACTJJF0uBjaVUj7f\n9jkb2AGcAdyYZDlwLnBWKeXOts85wESStaWULTMaiSRJmndzuschyfHASuD2/W2llCeB+4B1bdNJ\nNIGls882YHtHH0mSNIDmenPkSprTFzu62ne0xwBWAPvaQHGwPpIkaQB5VYUkSarW8x6HaTwGhGZV\noXPVYQVwf0efJUmWd606rGiPTWEDcERX22j70FyYmJjodwnVjj76aFatWtXvMiRpYIyNjTE2NnZA\n265du+b0PVLKz10YUf/FyfPAGaWUz3a0PQp8tJRyVft8OU2IOLuU8j/b54/TbI78TNtnNTABvG6y\nzZFJTgS2wlbgxBnXu3AeB/ZfXTosNf818A7g+X4XUm3ZssPYtm3C8CBJUxgfH2dkZARgpJQyPtvX\n63nFIcnhwAk0KwsAv5zkNcCPSinfo7nU8tIkDwIPA5uAR4CbodksmeR64MokTwC7gWuAu72iop9+\nTBMabgDW9LmWGhPs3buenTt3GhwkaQHN5FTFScDf0GyCLMAVbfufA+eWUi5PchhwHXAkcBdwWill\nX8drbACeAzYDS2ku77xgRiPQHFvDcKyQSJL6YSaf43An02yqLKVsBDZOcfxp4KL2IUmShoRXVUiS\npGoGB0mSVM3gIEmSqhkcJElSNYODJEmqZnCQJEnVDA6SJKnaXN+rQlpQw3RvDfD+GpKGn8FBQ+oH\nwCGsX7++34X0xPtrSBp2BgcNqWG7twZ4fw1Ji4HBQUPOe2tI0kJyc6QkSapmcJAkSdUMDpIkqZrB\nQZIkVTM4SJKkagYHSZJUzeAgSZKqGRwkSVI1g4MkSapmcJAkSdUMDpIkqZrBQZIkVTM4SJKkagYH\nSZJUzeAgSZKqGRwkSVI1g4MkSap2aL8LkF5oJiYm+l1CtaOPPppVq1b1uwxJA8TgIC2YHwCHsH79\n+n4XUm3ZssPYtm3C8CDppwwO0oL5MfA8cAOwps+11Jhg79717Ny50+Ag6acMDtKCWwOc2O8iJGlG\n3BwpSZKqGRwkSVI1g4MkSarmHgdJUxqmy0fBS0il+WZwkHQQw3f5KHgJqTTfDA6SDmLYLh8FLyGV\n5p/BQdI0vHxU0s+4OVKSJFVzxaFvxoDRfhcxhxbTeBbTWOCFOJ5h2dB5yy23sH79+kVzWmVsbIzR\n0cXzvbbYxjNX+hocklwA/EdgJfAAcFEp5X/3s6aF88L7YT48FtNY4IU1nuHb0Llp0x8tms2cg/qL\ndvv27ezcubPnr/v4xz/O6tWr56Gi6Q3y1UF9Cw5J/hVwBXAesAXYANya5FWllN5nWJKGbkPn+9i7\n9343c86j7du3s3r1GvbufWpGXz8yMjLHFdUZ5KuD+rnisAG4rpTySYAk5wOnA+cCl/exLklDb1g2\ndP4iMDynVvYb5L+Gu+3cubMNDTMJkxuAq+a+qGkN9tVBfQkOSV4MjAAf3t9WSilJvgys60dNkrTw\n9jJsp1YAli5dxk03bebYY489oH3Xrl2Mj4/3qarJ/SyUzSRMHjGDr1n8+rXicDTwImBHV/sOYLIT\nSsua//wV8LX5rGuO7O749xeAyf6aeAT4i4Upp8rd7X8PVu90Fno8s613KvM1lvmseSozHU+/6p3O\nVOMZ1JoPZgfNqZV/Cxw7Td9B8Y88/fSNvP3tb5/0aL+W9qc3k++Jfv2cfgiYu5WojtdZNhevl1LK\nXLxOb2+aHAt8H1hXSrmvo/2/AqeUUtZ19f/XDNZvWUmShs17Simfnu2L9GvFYSfwHLCiq30F8Ngk\n/W8F3gM8TLO2J0mS6iwDfonmd+ms9WXFASDJV4H7SikXt88DbAeuKaV8tC9FSZKkKfXzqoorgU8k\n2crPLsc8DPhEH2uSJElT6FtwKKXcmORo4DKaUxR/D7y1lPJ4v2qSJElT69upCkmSNHy8yZUkSapm\ncJAkSdWGIjgkuSDJQ0l+kuSrSX6j3zX1KsmHkjzf9fhmv+uqleSNST6b5Ptt7e+YpM9lSR5N8lSS\n25Kc0I9aa0w3niR/Nsl8faFf9U4lyQeTbEnyZJIdST6T5FWT9BuK+akZz7DMT5LzkzyQZFf7uCfJ\n73T1GYp5genHMyzzMpkkf9DWe2VX+9DMT6fJxjNX8zPwwaHjZlgfAv45zV00b203Vg6bb9BsBF3Z\nPt7Q33J6cjjNBtb3Az+3MSbJJcCFNDctWwvsoZmnJQtZZA+mHE/rixw4X4N327/GG4E/AU4G3gK8\nGPhSkl/Y32HI5mfa8bSGYX6+B1xC87nFI8AdwM1J1sDQzQtMM57WMMzLAdo/Rs+j+f3S2T5s8wMc\nfDyt2c9PKWWgH8BXgT/ueB6azwH9QL9r63EcHwLG+13HHI3leeAdXW2PAhs6ni8HfgK8u9/1znA8\nfwb8Vb9rm+F4jm7H9IZFMj+TjWeY5+eHwDnDPi8HGc/QzQvwEmAb8Gbgb4ArO44N3fxMM545mZ+B\nXnHouBnW7fvbSjP6Yb0Z1q+0S+PfTnJDklf0u6C5kOR4muTaOU9PAvcxnPO032+2S+XfSvKxJP+k\n3wVVOpJmFeVHsCjm54DxdBiq+UlySJKzaD6v5p5hn5fu8XQcGqp5Aa4FPldKuaOzcYjnZ9LxdJj1\n/PTzA6Bq9HozrEH2VeC9NEnwWGAj8HdJXl1K2dPHuubCSpof7JPN08qFL2dOfBG4ieZuM/8M+C/A\nF5Ksa8PrQEoS4GrgK6WU/XtohnZ+DjIeGKL5SfJq4F6aj/3dDbyrlLItyTqGcF4ONp728NDMC0Ab\nfF4LnDTJ4aH7/2aa8cAczc+gB4dFo5TS+Rnh30iyBfgu8G6a5SMNkFLKjR1P/2+S/wN8G/hNmuW/\nQfUx4NeA1/e7kDky6XiGbH6+BbyG5h7Nvwd8Mskp/S1pViYdTynlW8M0L0leThNK31JKeabf9cxW\nzXjman4G+lQFvd8Ma2iUUnYB/wAMxQ7daTxGs/dk0c3TfqWUh2i+Hwd2vpL8KfA24DdLKT/oODSU\n8zPFeH7OIM9PKeXZUsp3Sin3l1L+E82GtYsZ0nmZYjyT9R3YeaE5Df4yYDzJM0meAd4EXJxkH83K\nwjDNz5TjaVfvDjDT+Rno4NCmpq3Aqfvb2sGfyoHn1IZOkpfQTNaUPxCHQfvN9xgHztNyml3xQz1P\n+7Vp/igGdL7aX7LvBH6rlLK989gwzs9U4zlI/4Geny6HAEuHcV4O4hBg6WQHBnxevgz8Os3S/mva\nx9eAG4DXlFK+w3DNz3TjmexquJnNT793gFbsEH038BRwNvCrwHU0u3hf1u/aehzHR4FTgFcC/wK4\njSbRHtXv2irrP7z9RnwtzQ73f98+f0V7/APtvPxu+837v4B/BJb0u/Zex9Meu5zmB8QraX5wfA2Y\nAF7c79onGcvHgCdoLmNc0fFY1tFnaOZnuvEM0/wAH27H8Urg1TTnlJ8F3jxs8zLdeIZpXqYYX/dV\nCEM1P1ONZy7np+8Dqxz8+4GHaS6DuRc4qd81zWAMYzSXkf6E5vbhnwaO73ddPdT/pvYX7HNdj//R\n0WcjzeVLT9Hc9/2Eftc9k/HQbPq6heavjb3Ad4D/xoCG1YOM4zng7K5+QzE/041nmOYH+O9tfT9p\n6/0SbWgYtnmZbjzDNC9TjO+OzuAwbPMz1Xjmcn68yZUkSao20HscJEnSYDE4SJKkagYHSZJUzeAg\nSZKqGRwkSVI1g4MkSapmcJAkSdUMDpIkqZrBQZIkVTM4SJKkagYHSZJU7f8DDyTbMe0VDtoAAAAA\nSUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f7ad95f8250>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "frequencies = np.int32(np.random.exponential(7, size=(1000)))\n",
    "plt.hist(frequencies)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:17:38.536531Z",
     "start_time": "2018-07-06T00:17:38.512230Z"
    }
   },
   "outputs": [],
   "source": [
    "def sample_url_features(num_samples):\n",
    "    frequencies = np.int32(np.random.exponential(7, size=num_samples)) + 1\n",
    "    frequencies = np.int32(np.ones(num_samples))\n",
    "    X = []\n",
    "    \n",
    "    for frequency in frequencies:\n",
    "        num_sampled = min(10, frequency)\n",
    "        features = sample_weighted(num_sampled, weights).sum(axis=0)\n",
    "        X.append(frequency / num_sampled * features)\n",
    "        \n",
    "    return np.array(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:18:45.118445Z",
     "start_time": "2018-07-06T00:17:38.538528Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1/48] training: 6.18883 loss, 0.848 accuracy\n",
      "[ModelCheckpoint] New best model with 0.84790 validation accuracy\n",
      "[2/48] training: 1.06586 loss, 0.945 accuracy\n",
      "[ModelCheckpoint] New best model with 0.94890 validation accuracy\n",
      "[3/48] training: 0.34774 loss, 0.946 accuracy\n",
      "validation: 0.942 accuracy\n",
      "[4/48] training: 0.23382 loss, 0.944 accuracy\n",
      "[ModelCheckpoint] New best model with 0.95250 validation accuracy\n",
      "[5/48] training: 0.11506 loss, 0.964 accuracy\n",
      "[ModelCheckpoint] New best model with 0.96180 validation accuracy\n",
      "[6/48] training: 0.13775 loss, 0.963 accuracy\n",
      "validation: 0.958 accuracy\n",
      "[7/48] training: 0.09727 loss, 0.956 accuracy\n",
      "[ModelCheckpoint] New best model with 0.96200 validation accuracy\n",
      "[8/48] training: 0.14268 loss, 0.964 accuracy\n",
      "validation: 0.960 accuracy\n",
      "[9/48] training: 0.08408 loss, 0.967 accuracy\n",
      "[ModelCheckpoint] New best model with 0.96470 validation accuracy\n",
      "[10/48] training: 0.11251 loss, 0.961 accuracy\n",
      "validation: 0.965 accuracy\n",
      "[11/48] training: 0.08002 loss, 0.965 accuracy\n",
      "validation: 0.962 accuracy\n",
      "[12/48] training: 0.07924 loss, 0.960 accuracy\n",
      "validation: 0.959 accuracy\n",
      "[13/48] training: 0.03795 loss, 0.965 accuracy\n",
      "validation: 0.963 accuracy\n",
      "[14/48] training: 0.05874 loss, 0.962 accuracy\n",
      "validation: 0.962 accuracy\n",
      "[15/48] training: 0.03857 loss, 0.968 accuracy\n",
      "validation: 0.959 accuracy\n",
      "[16/48] training: 0.04413 loss, 0.964 accuracy\n",
      "validation: 0.963 accuracy\n",
      "[17/48] training: 0.04385 loss, 0.960 accuracy\n",
      "validation: 0.964 accuracy\n",
      "[18/48] training: 0.06421 loss, 0.954 accuracy\n",
      "validation: 0.963 accuracy\n",
      "[19/48] training: 0.02293 loss, 0.956 accuracy\n",
      "validation: 0.962 accuracy\n",
      "[20/48] training: 0.03481 loss, 0.975 accuracy\n",
      "[ModelCheckpoint] New best model with 0.97780 validation accuracy\n",
      "[21/48] training: 0.04948 loss, 0.977 accuracy\n",
      "validation: 0.973 accuracy\n",
      "[22/48] training: 0.02398 loss, 0.981 accuracy\n",
      "validation: 0.977 accuracy\n",
      "[23/48] training: 0.02134 loss, 0.971 accuracy\n",
      "validation: 0.972 accuracy\n",
      "[24/48] training: 0.02303 loss, 0.974 accuracy\n",
      "validation: 0.977 accuracy\n",
      "[25/48] training: 0.01597 loss, 0.976 accuracy\n",
      "validation: 0.974 accuracy\n",
      "[26/48] training: 0.03493 loss, 0.974 accuracy\n",
      "validation: 0.974 accuracy\n",
      "[27/48] training: 0.02015 loss, 0.973 accuracy\n",
      "validation: 0.976 accuracy\n",
      "[28/48] training: 0.00946 loss, 0.972 accuracy\n",
      "validation: 0.974 accuracy\n",
      "[29/48] training: 0.01747 loss, 0.978 accuracy\n",
      "[ModelCheckpoint] New best model with 0.97860 validation accuracy\n",
      "[30/48] training: 0.01490 loss, 0.985 accuracy\n",
      "[ModelCheckpoint] New best model with 0.98120 validation accuracy\n",
      "[31/48] training: 0.01863 loss, 0.981 accuracy\n",
      "[ModelCheckpoint] New best model with 0.98180 validation accuracy\n",
      "[32/48] training: 0.01493 loss, 0.987 accuracy\n",
      "[ModelCheckpoint] New best model with 0.99080 validation accuracy\n",
      "[33/48] training: 0.01119 loss, 0.987 accuracy\n",
      "validation: 0.989 accuracy\n",
      "[34/48] training: 0.00920 loss, 0.988 accuracy\n",
      "validation: 0.989 accuracy\n",
      "[35/48] training: 0.00459 loss, 0.988 accuracy\n",
      "validation: 0.989 accuracy\n",
      "[36/48] training: 0.01033 loss, 0.992 accuracy\n",
      "validation: 0.990 accuracy\n",
      "[37/48] training: 0.01775 loss, 0.989 accuracy\n",
      "validation: 0.991 accuracy\n",
      "[38/48] training: 0.01152 loss, 0.989 accuracy\n",
      "validation: 0.991 accuracy\n",
      "[39/48] training: 0.01566 loss, 0.988 accuracy\n",
      "validation: 0.990 accuracy\n",
      "[40/48] training: 0.01165 loss, 0.990 accuracy\n",
      "validation: 0.990 accuracy\n",
      "[41/48] training: 0.00757 loss, 0.993 accuracy\n",
      "validation: 0.990 accuracy\n",
      "[42/48] training: 0.01432 loss, 0.989 accuracy\n",
      "validation: 0.990 accuracy\n",
      "[43/48] training: 0.01217 loss, 0.990 accuracy\n",
      "[ModelCheckpoint] New best model with 0.99100 validation accuracy\n",
      "[44/48] training: 0.01379 loss, 0.987 accuracy\n",
      "validation: 0.991 accuracy\n",
      "[45/48] training: 0.00440 loss, 0.992 accuracy\n",
      "validation: 0.989 accuracy\n",
      "[46/48] training: 0.00816 loss, 0.992 accuracy\n",
      "validation: 0.991 accuracy\n",
      "[47/48] training: 0.00210 loss, 0.992 accuracy\n",
      "validation: 0.990 accuracy\n",
      "[48/48] training: 0.01071 loss, 0.991 accuracy\n",
      "validation: 0.989 accuracy\n"
     ]
    }
   ],
   "source": [
    "model = SVMRanking(delta=0.)\n",
    "model.fit(data_generator=sample_suggestions,\n",
    "          optimizer=GradientDescent(30.),\n",
    "          num_iterations=48,\n",
    "          callbacks=[ModelCheckpoint(rank_accuracy, sample_suggestions, 10000)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Federated Learning\n",
    "\n",
    "To implement a federated version of the model above, we have to create a `Client` class that completely encapsulates training data. Only the `Client` can compute gradients based on its own data. While the `Server` is the main class for controlling the training process, it can only request gradients from clients."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:18:45.158904Z",
     "start_time": "2018-07-06T00:18:45.120708Z"
    }
   },
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:40:18.905134Z",
     "start_time": "2018-07-06T00:40:18.862878Z"
    }
   },
   "outputs": [],
   "source": [
    "class Server:\n",
    "    def __init__(self, clients):\n",
    "        self.clients = clients\n",
    "        \n",
    "        num_features = len(frecency_points)\n",
    "        self.W = np.int32(frecency_points + (np.random.random(size=(num_features)) - 0.5) * 100)\n",
    "    \n",
    "    def fit(self, optimizer, num_iterations, num_clients_per_iteration, constraints=[], callbacks=[]):\n",
    "        for j in range(num_iterations):\n",
    "            clients = random.sample(self.clients, num_clients_per_iteration)\n",
    "            updates, losses = zip(*[client.request_update(self) for client in clients])\n",
    "            \n",
    "            gradient = np.mean(updates, axis=0)\n",
    "            loss = np.mean(losses, axis=0)\n",
    "            \n",
    "            print(\"[%d/%d] training loss across clients %.5f\" % (j + 1, num_iterations, loss))\n",
    "            \n",
    "            for callback in callbacks:\n",
    "                callback(self)\n",
    "            \n",
    "            self.W += np.int32(optimizer(gradient))\n",
    "            \n",
    "            for constraint in constraints:\n",
    "                self.W = constraint(self.W)\n",
    "            \n",
    "    def predict(self, X):\n",
    "        preds = []\n",
    "        \n",
    "        for x in X:\n",
    "            scores = x.dot(self.W)\n",
    "            preds.append(scores)\n",
    "        \n",
    "        return preds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:18:45.381044Z",
     "start_time": "2018-07-06T00:18:45.278291Z"
    }
   },
   "outputs": [],
   "source": [
    "class AnalyticalClient:\n",
    "    def __init__(self, data_generator, delta=0):\n",
    "        self.data_generator = data_generator\n",
    "        self.delta = 0\n",
    "    \n",
    "    def request_update(self, model):\n",
    "        X, y = self.data_generator()\n",
    "        preds = model.predict(X)\n",
    "        \n",
    "        num_features = X[0].shape[1]\n",
    "        gradient = np.zeros(num_features)\n",
    "        loss = 0\n",
    "\n",
    "        for xi, pi, yi in zip(X, preds, y):\n",
    "            correct = yi.argmax()\n",
    "            score_correct = pi[correct]\n",
    "\n",
    "            for i, predicted_score in enumerate(pi):\n",
    "                gradient -= xi[i] * max(0, predicted_score + self.delta - score_correct)\n",
    "            \n",
    "            loss += svm_loss(pi, yi)\n",
    "                \n",
    "        gradient /= len(X)\n",
    "        loss /= len(X)\n",
    "        \n",
    "        return gradient, loss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:39:55.750972Z",
     "start_time": "2018-07-06T00:39:55.712035Z"
    }
   },
   "outputs": [],
   "source": [
    "class FrecencyConstraints:\n",
    "    def __call__(self, gradient):\n",
    "        return gradient - min(0, gradient.min())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How many data points a user has in each round is sampled from the following exponential distribution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:18:45.929414Z",
     "start_time": "2018-07-06T00:18:45.605254Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([ 722.,    0.,  197.,    0.,   61.,    0.,   13.,    0.,    6.,    1.]),\n",
       " array([ 1. ,  1.5,  2. ,  2.5,  3. ,  3.5,  4. ,  4.5,  5. ,  5.5,  6. ]),\n",
       " <a list of 10 Patch objects>)"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAgkAAAFkCAYAAACq4KjhAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAAPYQAAD2EBqD+naQAAHSZJREFUeJzt3X+MXeV95/H3h4JNndYglWKHplaIaF1Xqag81IBoyGrJ\nJiWoKVmqlmmybGApSwqIersqiUpVF2u7WaKCl9SpkBY1ISQTsWYjGkqhFFpKDMUbhkLTOK5oTCeE\n2M0k7GCZGvPju3/c4/R6+mC412Pfsf1+SUfMfc73nvmeK+T7mec8955UFZIkSbMdNeoGJEnS/GRI\nkCRJTYYESZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQJElNA4WEJEclWZvk\n60leSPJUkmsbddclebaruS/JKbP2L0yyPsl0kh1JNiQ5cX9PRpIkzZ1BZxI+Avxn4NeAnwB+E/jN\nJFfuKUhyDXAlcBmwCtgJ3JtkQd9x1gHnARcAZwMnAXcMeQ6SJOkAyCA3eEryRWBbVf1q39gG4IWq\nuqh7/Czw8aq6sXu8GNgO/Mequr17/G3gwqr6QlezHNgMnFFVm+bm1CRJ0v4YdCbhYeCcJD8GkORU\n4Czg7u7xycBS4P49T6iq54FHgTO7odOAo2fVbAGm+mokSdKIHT1g/ceAxcDXkrxCL2T8VlV9vtu/\nFCh6Mwf9tnf7AJYAu7vw8Fo1e0nyQ8B7gKeBXQP2LEnSkexY4K3AvVX1nUGeOGhI+GXgV4ALga8C\nPw38zyTPVtVnBjzWIN4DfPYAHl+SpMPdB4DPDfKEQUPC9cB/r6r/3T3+uyRvBT4KfAbYBoTebEH/\nbMIS4PHu523AgiSLZ80mLOn2tTwNcNttt7FixYoBW9awVq9ezY033jjqNo4ovuYHn6/5wedrfnBt\n3ryZD37wg9C9lw5i0JCwCHhl1tirdGsbqmprkm3AOcCT8L2Fi6cD67v6x4CXu5r+hYvLgEde4/fu\nAlixYgUrV64csGUN67jjjvP1Psh8zQ8+X/ODz9d8ZAa+XD9oSPgicG2SZ4C/A1YCq4H/1Vezrqt5\nil5qWQs8A9wJvYWMSW4BbkjyHLADuAnY6CcbJEmaPwYNCVfSe9NfD5wIPAv8YTcGQFVdn2QRcDNw\nPPAQcG5V7e47zmp6MxIbgIXAPcAVQ56DJEk6AAYKCVW1E/gv3bavujXAmn3sfxG4qtskSdI85L0b\n9JrGx8dH3cIRx9f84PM1P/h8zQ8dA33j4qgkWQk89thjj7nYRZKkAUxOTjI2NgYwVlWTgzzXmQRJ\nktRkSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYESZLU\nZEiQJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1HT0\nqBsYxEsvvcTu3btH3cZAknDMMceMug1JkgZ2SIWEM844Y9QtDOzYYxexceNDrFy5ctStSJI0kEMq\nJMB1wFtH3cQAXmHXrot58sknDQmSpEPOIRYSzgMOpTfbl4GLR92EJElDceGiJElqGigkJNma5NXG\n9om+muuSPJvkhST3JTll1jEWJlmfZDrJjiQbkpw4VyckSZLmxqAzCacBS/u2fwcUcDtAkmuAK4HL\ngFXATuDeJAv6jrGO3nWDC4CzgZOAO4Y/BUmSdCAMtCahqr7T/zjJzwP/UFUPdUNXA2ur6q5u/0XA\nduB84PYki4FLgAur6sGu5mJgc5JVVbVpv85GkiTNmaHXJCQ5BvgAcEv3+GR6swv376mpqueBR4Ez\nu6HT6AWT/potwFRfjSRJmgf2Z+Hi+4HjgE93j5fSu/SwfVbd9m4fwBJgdxceXqtGkiTNA/vzEchL\ngD+tqm1z1czrW00vl/Qb7zZJko5sExMTTExM7DU2MzMz9PGGCglJlgHvorfWYI9tQOjNFvTPJiwB\nHu+rWZBk8azZhCXdvtdxI4fW9yRIknTwjI+PMz6+9x/Ok5OTjI2NDXW8YS83XEIvCNy9Z6CqttJ7\noz9nz1i3UPF04OFu6DF63zDUX7McWAY8MmQvkiTpABh4JiFJgA8Bn6qqV2ftXgdcm+Qp4GlgLfAM\ncCf0FjImuQW4IclzwA7gJmCjn2yQJGl+GeZyw7uAHwX+aPaOqro+ySLgZuB44CHg3Krqv3XjauAV\nYAOwELgHuGKIPiRJ0gE0cEioqvuA79vH/jXAmn3sfxG4qtskSdI85b0bJElSkyFBkiQ1GRIkSVKT\nIUGSJDUZEiRJUpMhQZIkNRkSJElSkyFBkiQ1GRIkSVKTIUGSJDUZEiRJUpMhQZIkNRkSJElSkyFB\nkiQ1GRIkSVKTIUGSJDUZEiRJUpMhQZIkNRkSJElSkyFBkiQ1GRIkSVKTIUGSJDUZEiRJUpMhQZIk\nNRkSJElSkyFBkiQ1GRIkSVKTIUGSJDUNHBKSnJTkM0mmk7yQ5IkkK2fVXJfk2W7/fUlOmbV/YZL1\n3TF2JNmQ5MT9PRlJkjR3BgoJSY4HNgIvAu8BVgC/ATzXV3MNcCVwGbAK2Ancm2RB36HWAecBFwBn\nAycBdwx9FpIkac4dPWD9R4Cpqrq0b+wfZ9VcDaytqrsAklwEbAfOB25Pshi4BLiwqh7sai4GNidZ\nVVWbhjgPSZI0xwa93PDzwJeT3J5ke5LJJN8LDElOBpYC9+8Zq6rngUeBM7uh0+iFk/6aLcBUX40k\nSRqxQUPC24APA1uAdwN/CNyU5D90+5cCRW/moN/2bh/AEmB3Fx5eq0aSJI3YoJcbjgI2VdVvd4+f\nSPJ24HLgM3PaWdNq4LhZY+PdJknSkW1iYoKJiYm9xmZmZoY+3qAh4VvA5lljm4F/3/28DQi92YL+\n2YQlwON9NQuSLJ41m7Ck27cPNwIr910iSdIRanx8nPHxvf9wnpycZGxsbKjjDXq5YSOwfNbYcrrF\ni1W1ld4b/Tl7dnYLFU8HHu6GHgNenlWzHFgGPDJgP5Ik6QAZdCbhRmBjko8Ct9N7878U+NW+mnXA\ntUmeAp4G1gLPAHdCbyFjkluAG5I8B+wAbgI2+skGSZLmj4FCQlV9Ocn7gY8Bvw1sBa6uqs/31Vyf\nZBFwM3A88BBwblXt7jvUauAVYAOwELgHuGJ/TkSSJM2tQWcSqKq7gbtfp2YNsGYf+18Eruo2SZI0\nD3nvBkmS1GRIkCRJTYYESZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQJElN\nhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYE\nSZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYESZLUNFBISPI7SV6dtX11Vs11SZ5N8kKS\n+5KcMmv/wiTrk0wn2ZFkQ5IT5+JkJEnS3BlmJuErwBJgabf97J4dSa4BrgQuA1YBO4F7kyzoe/46\n4DzgAuBs4CTgjmGalyRJB87RQzzn5ar69mvsuxpYW1V3ASS5CNgOnA/cnmQxcAlwYVU92NVcDGxO\nsqqqNg3RjyRJOgCGmUn4sSTfTPIPSW5L8qMASU6mN7Nw/57CqnoeeBQ4sxs6jV4w6a/ZAkz11UiS\npHlg0JDw18CHgPcAlwMnA3+V5E30AkLRmznot73bB73LFLu78PBaNZIkaR4Y6HJDVd3b9/ArSTYB\n/wj8EvC1uWxMkiSN1jBrEr6nqmaS/D1wCvCXQOjNFvTPJiwBHu9+3gYsSLJ41mzCkm7f61gNHDdr\nbLzbJEk6sk1MTDAxMbHX2MzMzNDH26+QkOQH6AWET1fV1iTbgHOAJ7v9i4HTgfXdUx4DXu5qvtDV\nLAeWAY+8/m+8EVi5Py1LknTYGh8fZ3x87z+cJycnGRsbG+p4A4WEJB8HvkjvEsOPAL8LvAR8vitZ\nB1yb5CngaWAt8AxwJ/QWMia5BbghyXPADuAmYKOfbJAkaX4ZdCbhLcDngB8Cvg18CTijqr4DUFXX\nJ1kE3AwcDzwEnFtVu/uOsRp4BdgALATuAa7Yn5OQJElzb9CFi6978b+q1gBr9rH/ReCqbpMkSfOU\n926QJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1GRI\nkCRJTYYESZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQJElNhgRJktRkSJAk\nSU2GBEmS1GRIkCRJTYYESZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1LRfISHJR5K8muSGWePXJXk2\nyQtJ7ktyyqz9C5OsTzKdZEeSDUlO3J9eJEnS3Bo6JCT5GeAy4IlZ49cAV3b7VgE7gXuTLOgrWwec\nB1wAnA2cBNwxbC+SJGnuDRUSkvwAcBtwKfD/Zu2+GlhbVXdV1VeAi+iFgPO75y4GLgFWV9WDVfU4\ncDFwVpJVw52GJEmaa8POJKwHvlhVD/QPJjkZWArcv2esqp4HHgXO7IZOA46eVbMFmOqrkSRJI3b0\noE9IciHw0/Te7GdbChSwfdb49m4fwBJgdxceXqtGkiSN2EAhIclb6K0neFdVvXRgWtqX1cBxs8bG\nu02SpCPbxMQEExMTe43NzMwMfbxBZxLGgB8GJpOkG/s+4OwkVwI/AYTebEH/bMIS4PHu523AgiSL\nZ80mLOn27cONwMoBW5Yk6cgwPj7O+PjefzhPTk4yNjY21PEGXZPw58BP0bvccGq3fZneIsZTq+rr\n9N7oz9nzhG6h4unAw93QY8DLs2qWA8uAR4Y6C0mSNOcGmkmoqp3AV/vHkuwEvlNVm7uhdcC1SZ4C\nngbWAs8Ad3bHeD7JLcANSZ4DdgA3ARuratN+nIskSZpDAy9cbKi9HlRdn2QRcDNwPPAQcG5V7e4r\nWw28AmwAFgL3AFfMQS+SJGmO7HdIqKp/2xhbA6zZx3NeBK7qNkmSNA957wZJktRkSJAkSU2GBEmS\n1GRIkCRJTYYESZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQJElNhgRJktRk\nSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQ\nJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTQOFhCSXJ3kiyUy3PZzk52bVXJfk2SQvJLkvySmz9i9M\nsj7JdJIdSTYkOXEuTkaSJM2dQWcSvgFcA6wExoAHgDuTrABIcg1wJXAZsArYCdybZEHfMdYB5wEX\nAGcDJwF37Mc5SJKkA+DoQYqr6k9mDV2b5MPAGcBm4GpgbVXdBZDkImA7cD5we5LFwCXAhVX1YFdz\nMbA5yaqq2rRfZyNJkubM0GsSkhyV5EJgEfBwkpOBpcD9e2qq6nngUeDMbug0esGkv2YLMNVXI0mS\n5oGBZhIAkrwdeAQ4FtgBvL+qtiQ5Eyh6Mwf9ttMLDwBLgN1deHitGkmSNA8MHBKArwGnAscBvwjc\nmuTsOe3qNa3ufm2/8W6TJOnINjExwcTExF5jMzMzQx9v4JBQVS8DX+8ePp5kFb21CNcDoTdb0D+b\nsAR4vPt5G7AgyeJZswlLun2v40Z6ayYlSdJs4+PjjI/v/Yfz5OQkY2NjQx1vLr4n4ShgYVVtpfdG\nf86eHd1CxdOBh7uhx4CXZ9UsB5bRu4QhSZLmiYFmEpL8HvCn9BYa/iDwAeCdwLu7knX0PvHwFPA0\nsBZ4BrgTegsZk9wC3JDkOXprGm4CNvrJBkmS5pdBLzecCHwaeDMwAzwJvLuqHgCoquuTLAJuBo4H\nHgLOrardfcdYDbwCbAAWAvcAV+zPSUiSpLk36PckXPoGatYAa/ax/0Xgqm6TJEnzlPdukCRJTYYE\nSZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQJElNhgRJktRkSJAkSU2GBEmS\n1GRIkCRJTYYESZLUZEiQJElNhgRJktRkSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQJElNhgRJktRk\nSJAkSU2GBEmS1GRIkCRJTYYESZLUZEiQJElNhgRJktQ0UEhI8tEkm5I8n2R7ki8k+fFG3XVJnk3y\nQpL7kpwya//CJOuTTCfZkWRDkhP392QkSdLcGXQm4R3AJ4DTgXcBxwB/luT79xQkuQa4ErgMWAXs\nBO5NsqDvOOuA84ALgLOBk4A7hjwHSZJ0ABw9SHFVvbf/cZIPAf8EjAFf6oavBtZW1V1dzUXAduB8\n4PYki4FLgAur6sGu5mJgc5JVVbVp+NORJElzZX/XJBwPFPBdgCQnA0uB+/cUVNXzwKPAmd3QafTC\nSX/NFmCqr0aSJI3Y0CEhSehdNvhSVX21G15KLzRsn1W+vdsHsATY3YWH16qRJEkjNtDlhlk+Cfwk\ncNYc9fIGrAaOmzU23m2aa1NTU0xPT4+6jaGccMIJLFu2bNRtSNJBNTExwcTExF5jMzMzQx9vqJCQ\n5A+A9wLvqKpv9e3aBoTebEH/bMIS4PG+mgVJFs+aTVjS7duHG4GVw7SsAU1NTbF8+Qp27Xph1K0M\n5dhjF7Fly2aDgqQjyvj4OOPje//hPDk5ydjY2FDHGzgkdAHhF4B3VtVU/76q2ppkG3AO8GRXv5je\npyHWd2WPAS93NV/oapYDy4BHhjoLzbnp6ekuINwGrBh1OwPazK5dH2R6etqQIEn7YaCQkOST9Ob2\n3wfsTLKk2zVTVbu6n9cB1yZ5CngaWAs8A9wJvYWMSW4BbkjyHLADuAnY6Ccb5qMVOHsjSUemQWcS\nLqe3MPEvZ41fDNwKUFXXJ1kE3Ezv0w8PAedW1e6++tXAK8AGYCFwD3DFoM1LkqQDZ9DvSXhDn4ao\nqjXAmn3sfxG4qtskSdI85L0bJElSkyFBkiQ1GRIkSVKTIUGSJDUZEiRJUpMhQZIkNRkSJElSkyFB\nkiQ1GRIkSVKTIUGSJDUZEiRJUpMhQZIkNRkSJElSkyFBkiQ1GRIkSVKTIUGSJDUZEiRJUpMhQZIk\nNRkSJElSkyFBkiQ1GRIkSVKTIUGSJDUZEiRJUpMhQZIkNRkSJElSkyFBkiQ1GRIkSVLTwCEhyTuS\n/HGSbyZ5Ncn7GjXXJXk2yQtJ7ktyyqz9C5OsTzKdZEeSDUlO3J8TkSRJc2uYmYQ3AX8D/BpQs3cm\nuQa4ErgMWAXsBO5NsqCvbB1wHnABcDZwEnDHEL1IkqQD5OhBn1BV9wD3ACRJo+RqYG1V3dXVXARs\nB84Hbk+yGLgEuLCqHuxqLgY2J1lVVZuGOhNJkjSn5nRNQpKTgaXA/XvGqup54FHgzG7oNHrhpL9m\nCzDVVyNJkkZsrhcuLqV3CWL7rPHt3T6AJcDuLjy8Vo0kSRoxP90gSZKaBl6T8Dq2AaE3W9A/m7AE\neLyvZkGSxbNmE5Z0+/ZhNXDcrLHxbpMk6cg2MTHBxMTEXmMzMzNDH29OQ0JVbU2yDTgHeBKgW6h4\nOrC+K3sMeLmr+UJXsxxYBjyy799wI7ByLluWJOmwMT4+zvj43n84T05OMjY2NtTxBg4JSd4EnEJv\nxgDgbUlOBb5bVd+g9/HGa5M8BTwNrAWeAe6E3kLGJLcANyR5DtgB3ARs9JMNkiTNH8PMJJwG/AW9\nBYoF/H43/mngkqq6Pski4GbgeOAh4Nyq2t13jNXAK8AGYCG9j1ReMdQZSJKkA2KY70l4kNdZ8FhV\na4A1+9j/InBVt0mSpHnITzdIkqQmQ4IkSWoyJEiSpCZDgiRJajIkSJKkJkOCJElqMiRIkqQmQ4Ik\nSWoyJEiSpKa5vgukpP0wNTXF9PT0qNsYygknnMCyZctG3YakOWRIkOaJqakpli9fwa5dL4y6laEc\ne+witmzZbFCQDiOGBGmemJ6e7gLCbcCKUbczoM3s2vVBpqenDQnSYcSQIM07K4CVo25Ckly4KEmS\n2gwJkiSpyZAgSZKaDAmSJKnJkCBJkpoMCZIkqcmQIEmSmgwJkiSpyZAgSZKaDAmSJKnJkCBJkpoM\nCZIkqcmQIEmSmgwJkiSpyVtFSzqifeITn+Css84adRtDOeGEE1i2bNmo2xjYxMQE4+Pjo25Db8BI\nQ0KSK4D/CiwFngCuqqr/O8qeJB05pqam+PVfX82rr74y6laGcuyxi9iyZfMhFxQMCYeOkYWEJL8M\n/D5wGbAJWA3cm+THq2p6VH1JOnJMT093AeE2YMWo2xnQZnbt+iDT09OHXEjQoWOUMwmrgZur6laA\nJJcD5wGXANePsC9JR5wVwMpRN3HE+Od//mcmJydH3cZQDtVLPMMaSUhIcgwwBvzenrGqqiR/Dpw5\nip4kSQfe1NQUDzzwF4yNjY26laEcqpd4hjWqmYQTgO8Dts8a3w4sb9Qf2/vP/wG+fCD7mmOvAvC3\nf/u3fPaznx1xL4PZunVr99PdwOZRtjKEXu933303mzcfOr37mh98vuYH39atW7tLPP8JePOo2xnQ\nt9i16xZuvfVWTj755FE384b9y//ne95L37hU1dx280Z+afJm4JvAmVX1aN/4/wDOrqozZ9X/CnBo\nvctKkjS/fKCqPjfIE0Y1kzANvAIsmTW+BNjWqL8X+ADwNLDrgHYmSdLh5VjgrfTeSwcykpkEgCR/\nDTxaVVd3jwNMATdV1cdH0pQkSfqeUX664QbgU0ke418+ArkI+NQIe5IkSZ2RhYSquj3JCcB19C4z\n/A3wnqr69qh6kiRJ/2JklxskSdL85g2eJElSkyFBkiQ1zeuQkOQdSf44yTeTvJrkfaPu6XCX5KNJ\nNiV5Psn2JF9I8uOj7utwluTyJE8kmem2h5P83Kj7OlIk+Uj378sNo+7lcJbkd7rXuX/76qj7Otwl\nOSnJZ5JMJ3mh+7fmDX8H+bwOCcCb6C1o/DXAxRMHxzuATwCnA+8CjgH+LMn3j7Srw9s3gGvo3Txg\nDHgAuDPJoXbHoUNOkp+hd5O5J0bdyxHiK/QWqi/ttp8dbTuHtyTHAxuBF4H30LtJyW8Az73RY4z0\nVtGvp6ruAe6B732Pgg6wqnpv/+MkHwL+id6b15dG0dPhrqr+ZNbQtUk+DJzBofddwYeMJD9A7/aP\nlwK/PeJ2jhQv+wm2g+ojwFRVXdo39o+DHGC+zyRo9I6nN4vz3VE3ciRIclSSC+l9Z8gjo+7nMLce\n+GJVPTDqRo4gP9ZdPv6HJLcl+dFRN3SY+3ngy0lu7y4fTya59HWf1WdezyRotLrZm3XAl6rKa4cH\nUJK30wsFxwI7gPdX1ddG29XhqwtiPw2cNupejiB/DXwI2ELvzk5rgL9K8vaq2jnCvg5nbwM+DPw+\n8N+AVcBNSV6sqs+8kQMYErQvnwR+Ejhr1I0cAb4GnAocB/wicGuSsw0Kcy/JW+iF33dV1Uuj7udI\nUVX99w34SpJN9Ka+fwn4o9F0ddg7CthUVXsupz3R/UFyOfCGQoKXG9SU5A+A9wL/pqq+Nep+DndV\n9XJVfb2qHq+q36K3kO7qUfd1mBoDfhiYTPJSkpeAdwJXJ9nt+qeDo6pmgL8HThl1L4exb/Gv1zVt\nBpa90QM4k6B/pQsIvwC8s6qmRt3PEeooYOGomzhM/TnwU7PGPkXvH8+PlV9De1B0C0dPAW4ddS+H\nsY3A8lljyxlg8eK8DglJ3kTvf6I9yf5tSU4FvltV3xhdZ4evJJ8ExoH3ATuT7Lmd90xVeZvuAyDJ\n7wF/Su8uqD9I77bo7wTePcq+Dlfd9e+91tgk2Ql8p6r8NMkBkuTjwBfpvUH9CPC7wEvAxCj7Oszd\nCGxM8lHgdnofbb8U+NU3eoB5HRLoLSr6C3qr64ve4guATwOXjKqpw9zl9F7rv5w1fjEm/gPlRHr/\nT78ZmAGeBN7tqvuDytmDA+8twOeAHwK+Te8j1WdU1XdG2tVhrKq+nOT9wMfofcx3K3B1VX3+jR7D\nGzxJkqQmFy5KkqQmQ4IkSWoyJEiSpCZDgiRJajIkSJKkJkOCJElqMiRIkqQmQ4IkSWoyJEiSpCZD\ngiRJajIkSJKkpv8PkbQ0oE8IAnEAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f7ad7a27490>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "num_datapoints = np.int32(np.random.exponential(.8, size=(1000))) + 1\n",
    "plt.hist(num_datapoints)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have 5000 clients:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:18:45.955213Z",
     "start_time": "2018-07-06T00:18:45.931708Z"
    }
   },
   "outputs": [],
   "source": [
    "clients = [AnalyticalClient(lambda: sample_suggestions(np.int32(np.random.exponential(.8)) + 1)) for _ in range(5000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:21:03.190202Z",
     "start_time": "2018-07-06T00:20:38.939491Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1/48] training loss across clients 12.52600\n",
      "[ModelCheckpoint] New best model with 0.75180 validation accuracy\n",
      "[2/48] training loss across clients 69.63567\n",
      "validation: 0.579 accuracy\n",
      "[3/48] training loss across clients 126.53121\n",
      "[ModelCheckpoint] New best model with 0.82800 validation accuracy\n",
      "[4/48] training loss across clients 8.36708\n",
      "[ModelCheckpoint] New best model with 0.95320 validation accuracy\n",
      "[5/48] training loss across clients 3.77042\n",
      "[ModelCheckpoint] New best model with 0.95440 validation accuracy\n",
      "[6/48] training loss across clients 2.39812\n",
      "[ModelCheckpoint] New best model with 0.96300 validation accuracy\n",
      "[7/48] training loss across clients 1.98479\n",
      "[ModelCheckpoint] New best model with 0.97820 validation accuracy\n",
      "[8/48] training loss across clients 1.14083\n",
      "validation: 0.973 accuracy\n",
      "[9/48] training loss across clients 0.92900\n",
      "validation: 0.975 accuracy\n",
      "[10/48] training loss across clients 1.00767\n",
      "[ModelCheckpoint] New best model with 0.97900 validation accuracy\n",
      "[11/48] training loss across clients 1.72417\n",
      "[ModelCheckpoint] New best model with 0.98060 validation accuracy\n",
      "[12/48] training loss across clients 0.77604\n",
      "validation: 0.976 accuracy\n",
      "[13/48] training loss across clients 1.85472\n",
      "validation: 0.977 accuracy\n",
      "[14/48] training loss across clients 0.48146\n",
      "validation: 0.976 accuracy\n",
      "[15/48] training loss across clients 0.65021\n",
      "validation: 0.979 accuracy\n",
      "[16/48] training loss across clients 0.38479\n",
      "validation: 0.979 accuracy\n",
      "[17/48] training loss across clients 0.92471\n",
      "validation: 0.976 accuracy\n",
      "[18/48] training loss across clients 0.54500\n",
      "validation: 0.977 accuracy\n",
      "[19/48] training loss across clients 0.64333\n",
      "validation: 0.976 accuracy\n",
      "[20/48] training loss across clients 0.21917\n",
      "validation: 0.974 accuracy\n",
      "[21/48] training loss across clients 1.24250\n",
      "validation: 0.979 accuracy\n",
      "[22/48] training loss across clients 0.17479\n",
      "validation: 0.975 accuracy\n",
      "[23/48] training loss across clients 0.37125\n",
      "validation: 0.980 accuracy\n",
      "[24/48] training loss across clients 0.17708\n",
      "validation: 0.977 accuracy\n",
      "[25/48] training loss across clients 0.19312\n",
      "validation: 0.974 accuracy\n",
      "[26/48] training loss across clients 0.21071\n",
      "validation: 0.975 accuracy\n",
      "[27/48] training loss across clients 0.15375\n",
      "validation: 0.979 accuracy\n",
      "[28/48] training loss across clients 0.25217\n",
      "validation: 0.978 accuracy\n",
      "[29/48] training loss across clients 0.11625\n",
      "validation: 0.978 accuracy\n",
      "[30/48] training loss across clients 0.14438\n",
      "[ModelCheckpoint] New best model with 0.98140 validation accuracy\n",
      "[31/48] training loss across clients 0.19250\n",
      "validation: 0.977 accuracy\n",
      "[32/48] training loss across clients 0.11167\n",
      "validation: 0.975 accuracy\n",
      "[33/48] training loss across clients 0.11208\n",
      "validation: 0.977 accuracy\n",
      "[34/48] training loss across clients 0.11167\n",
      "validation: 0.981 accuracy\n",
      "[35/48] training loss across clients 0.02958\n",
      "validation: 0.978 accuracy\n",
      "[36/48] training loss across clients 0.07437\n",
      "validation: 0.977 accuracy\n",
      "[37/48] training loss across clients 0.12875\n",
      "validation: 0.981 accuracy\n",
      "[38/48] training loss across clients 0.11971\n",
      "validation: 0.976 accuracy\n",
      "[39/48] training loss across clients 0.06208\n",
      "validation: 0.978 accuracy\n",
      "[40/48] training loss across clients 0.05292\n",
      "validation: 0.978 accuracy\n",
      "[41/48] training loss across clients 0.04750\n",
      "validation: 0.980 accuracy\n",
      "[42/48] training loss across clients 0.05975\n",
      "validation: 0.977 accuracy\n",
      "[43/48] training loss across clients 0.07625\n",
      "validation: 0.981 accuracy\n",
      "[44/48] training loss across clients 0.05604\n",
      "validation: 0.980 accuracy\n",
      "[45/48] training loss across clients 0.04167\n",
      "validation: 0.976 accuracy\n",
      "[46/48] training loss across clients 0.04900\n",
      "validation: 0.980 accuracy\n",
      "[47/48] training loss across clients 0.10875\n",
      "validation: 0.975 accuracy\n",
      "[48/48] training loss across clients 0.04458\n",
      "validation: 0.978 accuracy\n"
     ]
    }
   ],
   "source": [
    "np.random.seed(10)\n",
    "server = Server(clients)\n",
    "server.fit(optimizer=GradientDescent(30.),\n",
    "          num_iterations=48,\n",
    "           num_clients_per_iteration=400,\n",
    "           constraints=[FrecencyConstraints()],\n",
    "          callbacks=[ModelCheckpoint(rank_accuracy, sample_suggestions, 5000)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "=> The model quality improved from 70% to >97% validation accuracy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:21:03.240159Z",
     "start_time": "2018-07-06T00:21:03.192921Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(12.0, 0),\n",
       " (14.0, 1031),\n",
       " (20.0, 1029),\n",
       " (36.0, 1027),\n",
       " (42.0, 1222),\n",
       " (60.0, 1220),\n",
       " (60.0, 1224),\n",
       " (70.0, 1376),\n",
       " (84.0, 1375),\n",
       " (98.0, 1605),\n",
       " (100.0, 1667),\n",
       " (120.0, 1730),\n",
       " (140.0, 1790),\n",
       " (140.0, 1790),\n",
       " (200.0, 1897)]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zip(frecency_points[ais], server.W[ais])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### With RProp\n",
    "\n",
    "[RProp](https://florian.github.io/rprop/) is a gradient descent variation that ignores the magnitude of the gradient.\n",
    "The general motivation for this is that the mangitude can be misleading since it does not have to contain useful information for the step size.\n",
    "\n",
    "The motivation for using RProp in our case is a little bit different: Since we do not collect any training data at all, we have no idea how large the gradient mangitudes are going to be. This is problematic because it makes it very hard to properly configure the learning rate beforehand.\n",
    "To deal with this, we can use RProp to only take into account the signs of gradients.\n",
    "\n",
    "This also makes updates much easier to interpret: They change each frecency weight between 1 and 3, depending on how strong the feedback signal for that weight has been in the past."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:19:34.066635Z",
     "start_time": "2018-07-06T00:19:10.092005Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1/48] training loss across clients 12.52600\n",
      "[ModelCheckpoint] New best model with 0.75180 validation accuracy\n",
      "[2/48] training loss across clients 11.57683\n",
      "[ModelCheckpoint] New best model with 0.75420 validation accuracy\n",
      "[3/48] training loss across clients 10.13446\n",
      "[ModelCheckpoint] New best model with 0.76120 validation accuracy\n",
      "[4/48] training loss across clients 9.87555\n",
      "[ModelCheckpoint] New best model with 0.81120 validation accuracy\n",
      "[5/48] training loss across clients 6.85687\n",
      "validation: 0.806 accuracy\n",
      "[6/48] training loss across clients 7.84021\n",
      "validation: 0.800 accuracy\n",
      "[7/48] training loss across clients 6.18229\n",
      "validation: 0.797 accuracy\n",
      "[8/48] training loss across clients 5.60081\n",
      "[ModelCheckpoint] New best model with 0.86840 validation accuracy\n",
      "[9/48] training loss across clients 4.31879\n",
      "validation: 0.866 accuracy\n",
      "[10/48] training loss across clients 3.27196\n",
      "validation: 0.867 accuracy\n",
      "[11/48] training loss across clients 4.12021\n",
      "validation: 0.868 accuracy\n",
      "[12/48] training loss across clients 1.78142\n",
      "validation: 0.867 accuracy\n",
      "[13/48] training loss across clients 2.35683\n",
      "[ModelCheckpoint] New best model with 0.87420 validation accuracy\n",
      "[14/48] training loss across clients 1.59417\n",
      "[ModelCheckpoint] New best model with 0.91000 validation accuracy\n",
      "[15/48] training loss across clients 1.13029\n",
      "validation: 0.905 accuracy\n",
      "[16/48] training loss across clients 0.90542\n",
      "[ModelCheckpoint] New best model with 0.93580 validation accuracy\n",
      "[17/48] training loss across clients 0.77200\n",
      "[ModelCheckpoint] New best model with 0.93900 validation accuracy\n",
      "[18/48] training loss across clients 0.62500\n",
      "[ModelCheckpoint] New best model with 0.94560 validation accuracy\n",
      "[19/48] training loss across clients 0.55208\n",
      "[ModelCheckpoint] New best model with 0.95260 validation accuracy\n",
      "[20/48] training loss across clients 0.22333\n",
      "[ModelCheckpoint] New best model with 0.95680 validation accuracy\n",
      "[21/48] training loss across clients 0.24579\n",
      "validation: 0.955 accuracy\n",
      "[22/48] training loss across clients 0.22500\n",
      "validation: 0.951 accuracy\n",
      "[23/48] training loss across clients 0.33917\n",
      "validation: 0.952 accuracy\n",
      "[24/48] training loss across clients 0.21667\n",
      "[ModelCheckpoint] New best model with 0.95780 validation accuracy\n",
      "[25/48] training loss across clients 0.10833\n",
      "validation: 0.957 accuracy\n",
      "[26/48] training loss across clients 0.06333\n",
      "[ModelCheckpoint] New best model with 0.96220 validation accuracy\n",
      "[27/48] training loss across clients 0.20771\n",
      "validation: 0.863 accuracy\n",
      "[28/48] training loss across clients 0.03800\n",
      "[ModelCheckpoint] New best model with 1.00000 validation accuracy\n",
      "[29/48] training loss across clients 0.22592\n",
      "validation: 0.927 accuracy\n",
      "[30/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[31/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[32/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[33/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[34/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[35/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[36/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[37/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[38/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[39/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[40/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[41/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[42/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[43/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[44/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[45/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[46/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[47/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[48/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n"
     ]
    }
   ],
   "source": [
    "np.random.seed(10)\n",
    "opt = opt = RProp(2., len(frecency_points), min_value=1, max_value=3, alpha=2., beta=0.6)\n",
    "server = Server(clients)\n",
    "server.fit(optimizer=opt,\n",
    "          num_iterations=48,\n",
    "           num_clients_per_iteration=400,\n",
    "           constraints=[FrecencyConstraints()],\n",
    "          callbacks=[ModelCheckpoint(rank_accuracy, sample_suggestions, 5000)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:19:53.747166Z",
     "start_time": "2018-07-06T00:19:53.706820Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 3.,  2.,  3.,  3.,  3.,  2.,  2.,  3.,  2.,  2.,  3.,  3.,  2.,\n",
       "        2.,  3.])"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt.learning_rates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:19:54.541101Z",
     "start_time": "2018-07-06T00:19:54.517385Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(12.0, 0),\n",
       " (14.0, 22),\n",
       " (20.0, 24),\n",
       " (36.0, 26),\n",
       " (42.0, 37),\n",
       " (60.0, 98),\n",
       " (60.0, 98),\n",
       " (70.0, 104),\n",
       " (84.0, 105),\n",
       " (98.0, 107),\n",
       " (100.0, 109),\n",
       " (120.0, 140),\n",
       " (140.0, 142),\n",
       " (140.0, 142),\n",
       " (200.0, 203)]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zip(frecency_points[ais], server.W[ais])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Even in the simulation this works a bit better. It's the only optimizer that reaches a perfect score. In a real life application, it is also much more practical, as explained above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### With numerical gradient computation\n",
    "\n",
    "So far all simulations were based on the fact that we knew how to analytically derive the gradient.\n",
    "This is not the case for the actual addon, which uses a simple [finite difference method](https://en.wikipedia.org/wiki/Finite_difference_method) of computing the gradient.\n",
    "To make sure the simulations still work, the following reconstructs the important part of the client-side code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:40:25.916393Z",
     "start_time": "2018-07-06T00:40:25.894816Z"
    }
   },
   "outputs": [],
   "source": [
    "def full_loss(model, loss_fn, X, y):\n",
    "    preds = model.predict(X)\n",
    "    return sum([loss_fn(pi, yi) for pi, yi in zip(preds, y)]) / len(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:40:26.344533Z",
     "start_time": "2018-07-06T00:40:26.311489Z"
    }
   },
   "outputs": [],
   "source": [
    "class NumericalClient:\n",
    "    def __init__(self, data_generator, delta=0):\n",
    "        self.data_generator = data_generator\n",
    "        self.delta = 0\n",
    "    \n",
    "    def request_update(self, model, eps=1):\n",
    "        X, y = self.data_generator()\n",
    "        loss = full_loss(model, svm_loss, X, y)\n",
    "        \n",
    "        num_features = X[0].shape[1]\n",
    "        gradient = []\n",
    "        \n",
    "        for i in range(num_features):\n",
    "            model.W[i] -= eps\n",
    "            loss1 = full_loss(model, svm_loss, X, y)\n",
    "            \n",
    "            model.W[i] += 2 * eps\n",
    "            loss2 = full_loss(model, svm_loss, X, y)\n",
    "            \n",
    "            finite_difference = (loss1 - loss2) / (2 * eps)\n",
    "            gradient.append(finite_difference)\n",
    "            \n",
    "            model.W[i] -= eps\n",
    "        \n",
    "        return gradient, loss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:40:26.743318Z",
     "start_time": "2018-07-06T00:40:26.677818Z"
    }
   },
   "outputs": [],
   "source": [
    "clients = [NumericalClient(lambda: sample_suggestions(np.int32(np.random.exponential(.8)) + 1)) for _ in range(5000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:41:09.911718Z",
     "start_time": "2018-07-06T00:40:27.554833Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1/48] training loss across clients 12.52600\n",
      "[ModelCheckpoint] New best model with 0.75180 validation accuracy\n",
      "[2/48] training loss across clients 10.58042\n",
      "[ModelCheckpoint] New best model with 0.75660 validation accuracy\n",
      "[3/48] training loss across clients 8.25508\n",
      "[ModelCheckpoint] New best model with 0.81060 validation accuracy\n",
      "[4/48] training loss across clients 7.12117\n",
      "[ModelCheckpoint] New best model with 0.82620 validation accuracy\n",
      "[5/48] training loss across clients 4.03208\n",
      "[ModelCheckpoint] New best model with 0.88960 validation accuracy\n",
      "[6/48] training loss across clients 4.00917\n",
      "validation: 0.889 accuracy\n",
      "[7/48] training loss across clients 2.68683\n",
      "validation: 0.882 accuracy\n",
      "[8/48] training loss across clients 1.18067\n",
      "[ModelCheckpoint] New best model with 0.96580 validation accuracy\n",
      "[9/48] training loss across clients 0.88250\n",
      "[ModelCheckpoint] New best model with 0.98420 validation accuracy\n",
      "[10/48] training loss across clients 0.51500\n",
      "[ModelCheckpoint] New best model with 0.99840 validation accuracy\n",
      "[11/48] training loss across clients 0.56775\n",
      "[ModelCheckpoint] New best model with 0.99880 validation accuracy\n",
      "[12/48] training loss across clients 0.20125\n",
      "[ModelCheckpoint] New best model with 0.99900 validation accuracy\n",
      "[13/48] training loss across clients 0.18000\n",
      "validation: 0.999 accuracy\n",
      "[14/48] training loss across clients 0.00250\n",
      "[ModelCheckpoint] New best model with 0.99980 validation accuracy\n",
      "[15/48] training loss across clients 0.10050\n",
      "validation: 0.999 accuracy\n",
      "[16/48] training loss across clients 0.07000\n",
      "validation: 1.000 accuracy\n",
      "[17/48] training loss across clients 0.08992\n",
      "[ModelCheckpoint] New best model with 1.00000 validation accuracy\n",
      "[18/48] training loss across clients 0.00583\n",
      "validation: 1.000 accuracy\n",
      "[19/48] training loss across clients 0.04833\n",
      "validation: 1.000 accuracy\n",
      "[20/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[21/48] training loss across clients 0.03350\n",
      "validation: 1.000 accuracy\n",
      "[22/48] training loss across clients 0.00750\n",
      "validation: 1.000 accuracy\n",
      "[23/48] training loss across clients 0.06917\n",
      "validation: 1.000 accuracy\n",
      "[24/48] training loss across clients 0.00125\n",
      "validation: 1.000 accuracy\n",
      "[25/48] training loss across clients 0.04396\n",
      "validation: 1.000 accuracy\n",
      "[26/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[27/48] training loss across clients 0.14417\n",
      "validation: 1.000 accuracy\n",
      "[28/48] training loss across clients 0.07417\n",
      "validation: 1.000 accuracy\n",
      "[29/48] training loss across clients 0.04975\n",
      "validation: 1.000 accuracy\n",
      "[30/48] training loss across clients 0.00250\n",
      "validation: 1.000 accuracy\n",
      "[31/48] training loss across clients 0.03542\n",
      "validation: 1.000 accuracy\n",
      "[32/48] training loss across clients 0.00000\n",
      "validation: 1.000 accuracy\n",
      "[33/48] training loss across clients 0.09988\n",
      "validation: 1.000 accuracy\n",
      "[34/48] training loss across clients 0.00125\n",
      "validation: 1.000 accuracy\n",
      "[35/48] training loss across clients 0.13833\n",
      "validation: 1.000 accuracy\n",
      "[36/48] training loss across clients 0.04250\n",
      "validation: 1.000 accuracy\n",
      "[37/48] training loss across clients 0.05583\n",
      "validation: 1.000 accuracy\n",
      "[38/48] training loss across clients 0.00750\n",
      "validation: 1.000 accuracy\n",
      "[39/48] training loss across clients 0.08583\n",
      "validation: 1.000 accuracy\n",
      "[40/48] training loss across clients 0.04708\n",
      "validation: 1.000 accuracy\n",
      "[41/48] training loss across clients 0.04333\n",
      "validation: 1.000 accuracy\n",
      "[42/48] training loss across clients 0.00500\n",
      "validation: 1.000 accuracy\n",
      "[43/48] training loss across clients 0.10917\n",
      "validation: 1.000 accuracy\n",
      "[44/48] training loss across clients 0.08542\n",
      "validation: 1.000 accuracy\n",
      "[45/48] training loss across clients 0.03250\n",
      "validation: 1.000 accuracy\n",
      "[46/48] training loss across clients 0.00750\n",
      "validation: 1.000 accuracy\n",
      "[47/48] training loss across clients 0.12083\n",
      "validation: 1.000 accuracy\n",
      "[48/48] training loss across clients 0.05917\n",
      "validation: 1.000 accuracy\n"
     ]
    }
   ],
   "source": [
    "np.random.seed(10)\n",
    "opt = opt = RProp(2., len(frecency_points), min_value=1, max_value=3, alpha=2., beta=0.6)\n",
    "server = Server(clients)\n",
    "server.fit(optimizer=opt,\n",
    "          num_iterations=48,\n",
    "           num_clients_per_iteration=400,\n",
    "           constraints=[FrecencyConstraints()],\n",
    "          callbacks=[ModelCheckpoint(rank_accuracy, sample_suggestions, 5000)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:41:09.953946Z",
     "start_time": "2018-07-06T00:41:09.913793Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 3.,  3.,  3.,  3.,  1.,  3.,  2.,  3.,  3.,  3.,  1.,  2.,  2.,\n",
       "        1.,  3.])"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "opt.learning_rates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-07-06T00:41:10.063705Z",
     "start_time": "2018-07-06T00:41:09.955859Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(12.0, 0),\n",
       " (14.0, 43),\n",
       " (20.0, 45),\n",
       " (36.0, 52),\n",
       " (42.0, 57),\n",
       " (60.0, 104),\n",
       " (60.0, 105),\n",
       " (70.0, 119),\n",
       " (84.0, 129),\n",
       " (98.0, 134),\n",
       " (100.0, 135),\n",
       " (120.0, 164),\n",
       " (140.0, 183),\n",
       " (140.0, 185),\n",
       " (200.0, 214)]"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zip(frecency_points[ais], server.W[ais])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The model still converges nicely with this method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Notes \n",
    "\n",
    "Simplifications made:\n",
    "\n",
    "- All users sample from the same distribution\n",
    "- `ModelCheckpoint` cannot be based on validation data in the actual implementation\n",
    "- Users should run more than one SGD iteration locally\n",
    "\n",
    "## To make fitting easier\n",
    "\n",
    "- Fair initialization\n",
    "- Normalize data (0-center)\n",
    "- Remove features with a value of 0\n",
    "\n",
    "## Still missing\n",
    "\n",
    "- Implement frequency part (switch from one-hot encoding to up to sum of 10 and add multiplicative factor)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "toc_cell": false,
   "toc_position": {
    "height": "1162px",
    "left": "0px",
    "right": "1494px",
    "top": "160px",
    "width": "212px"
   },
   "toc_section_display": "block",
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}