SGD_Matrix_Factorisation.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "SGD Matrix_Factorisation.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "authorship_tag": "ABX9TyOh+fDcDnNq3IEP9isNPmxk"
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GgIxC69NaT3N",
        "colab_type": "text"
      },
      "source": [
        "Importing required paskages"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XLXrLQ_jaCIc",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from __future__ import print_function\n",
        "\n",
        "import numpy as np\n",
        "import pandas as pd\n",
        "from mpl_toolkits.mplot3d import Axes3D\n",
        "from IPython import display\n",
        "from matplotlib import pyplot as plt\n",
        "import sklearn\n",
        "import sklearn.manifold\n",
        "import tensorflow as tf\n"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9qwAwdRWN58v",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 531
        },
        "outputId": "8f754df2-d8d7-4333-a6cd-dee2f22cc6be"
      },
      "source": [
        " !curl -O http://files.grouplens.org/datasets/movielens/ml-100k.zip\n",
        " !unzip ml-100k.zip"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current\n",
            "                                 Dload  Upload   Total   Spent    Left  Speed\n",
            "100 4808k  100 4808k    0     0  3747k      0  0:00:01  0:00:01 --:--:-- 3745k\n",
            "Archive:  ml-100k.zip\n",
            "   creating: ml-100k/\n",
            "  inflating: ml-100k/allbut.pl       \n",
            "  inflating: ml-100k/mku.sh          \n",
            "  inflating: ml-100k/README          \n",
            "  inflating: ml-100k/u.data          \n",
            "  inflating: ml-100k/u.genre         \n",
            "  inflating: ml-100k/u.info          \n",
            "  inflating: ml-100k/u.item          \n",
            "  inflating: ml-100k/u.occupation    \n",
            "  inflating: ml-100k/u.user          \n",
            "  inflating: ml-100k/u1.base         \n",
            "  inflating: ml-100k/u1.test         \n",
            "  inflating: ml-100k/u2.base         \n",
            "  inflating: ml-100k/u2.test         \n",
            "  inflating: ml-100k/u3.base         \n",
            "  inflating: ml-100k/u3.test         \n",
            "  inflating: ml-100k/u4.base         \n",
            "  inflating: ml-100k/u4.test         \n",
            "  inflating: ml-100k/u5.base         \n",
            "  inflating: ml-100k/u5.test         \n",
            "  inflating: ml-100k/ua.base         \n",
            "  inflating: ml-100k/ua.test         \n",
            "  inflating: ml-100k/ub.base         \n",
            "  inflating: ml-100k/ub.test         \n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LZCKxw6Ea6_K",
        "colab_type": "text"
      },
      "source": [
        "Download the dataset"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UHJx2wqEJI3E",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 238
        },
        "outputId": "76b5ef1c-a3ad-4f1e-d47f-216cbb47d044"
      },
      "source": [
        "#ratings\n",
        "names = ['user_id', 'movie_id', 'rating', 'timestamp']\n",
        "movielens_ratings = pd.read_csv('ml-100k/u.data', sep='\\t', names=names)\n",
        "movielens_ratings.head(6)\n"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>user_id</th>\n",
              "      <th>movie_id</th>\n",
              "      <th>rating</th>\n",
              "      <th>timestamp</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>196</td>\n",
              "      <td>242</td>\n",
              "      <td>3</td>\n",
              "      <td>881250949</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>186</td>\n",
              "      <td>302</td>\n",
              "      <td>3</td>\n",
              "      <td>891717742</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>22</td>\n",
              "      <td>377</td>\n",
              "      <td>1</td>\n",
              "      <td>878887116</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>244</td>\n",
              "      <td>51</td>\n",
              "      <td>2</td>\n",
              "      <td>880606923</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>166</td>\n",
              "      <td>346</td>\n",
              "      <td>1</td>\n",
              "      <td>886397596</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>5</th>\n",
              "      <td>298</td>\n",
              "      <td>474</td>\n",
              "      <td>4</td>\n",
              "      <td>884182806</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "   user_id  movie_id  rating  timestamp\n",
              "0      196       242       3  881250949\n",
              "1      186       302       3  891717742\n",
              "2       22       377       1  878887116\n",
              "3      244        51       2  880606923\n",
              "4      166       346       1  886397596\n",
              "5      298       474       4  884182806"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eqbgaAoYbIe-",
        "colab_type": "text"
      },
      "source": [
        "Movies ratings"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Cu52Q6_zITdc",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 238
        },
        "outputId": "72b5e876-4618-4d30-ff81-1207772ba3ba"
      },
      "source": [
        "\n",
        "movielens_ratings.head(6)"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>user_id</th>\n",
              "      <th>movie_id</th>\n",
              "      <th>rating</th>\n",
              "      <th>timestamp</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>196</td>\n",
              "      <td>242</td>\n",
              "      <td>3</td>\n",
              "      <td>881250949</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>186</td>\n",
              "      <td>302</td>\n",
              "      <td>3</td>\n",
              "      <td>891717742</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>22</td>\n",
              "      <td>377</td>\n",
              "      <td>1</td>\n",
              "      <td>878887116</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>244</td>\n",
              "      <td>51</td>\n",
              "      <td>2</td>\n",
              "      <td>880606923</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>166</td>\n",
              "      <td>346</td>\n",
              "      <td>1</td>\n",
              "      <td>886397596</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>5</th>\n",
              "      <td>298</td>\n",
              "      <td>474</td>\n",
              "      <td>4</td>\n",
              "      <td>884182806</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "   user_id  movie_id  rating  timestamp\n",
              "0      196       242       3  881250949\n",
              "1      186       302       3  891717742\n",
              "2       22       377       1  878887116\n",
              "3      244        51       2  880606923\n",
              "4      166       346       1  886397596\n",
              "5      298       474       4  884182806"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rX6n4_JEb2MJ",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 72
        },
        "outputId": "f8d65058-7c81-4657-b47c-0b0beefafa28"
      },
      "source": [
        "n_users = movielens_ratings.user_id.unique().shape[0]\n",
        "n_items = movielens_ratings.movie_id.unique().shape[0]\n",
        "print('Pour la base de données 100k')\n",
        "print (str(n_users) + ' utilisateurs')\n",
        "print (str(n_items) + ' films')\n"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Pour la base de données 100k\n",
            "943 utilisateurs\n",
            "1682 films\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Gi-e3HbuLurQ",
        "colab_type": "text"
      },
      "source": [
        "#Rappel Factorisation matricielle"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "07JF9PXRcypZ",
        "colab_type": "text"
      },
      "source": [
        "Un système de recommandation peut se décomposer en deux principales tâches: une prédiction des notes qu'un utilisateur est susceptible de donner à un item (film, livres, article etc) et la suggestion des éléments qui pourraient l'intéresser. Dans les approches de type filtrage collaboratif, ces évaluations sont regroupées dans des matrices de type utilisateur/produit où chaque ligne représente un utilisateur et chaque colonne un item (produit). On les appelle matrices d'évaluations. Elles sont non seulement de grandes tailles (des milliers voire des millions d'utilisateurs/produits) mais elles ont aussi la particularité d'être sparse (creuses). En effet, seul un nombre assez faible d'items se retrouvent notées ce qui fait qu'une garande partie des entrées de la matrice sont inconnues. Pour remédier à ce problème et réduire la dimensionalité des matrices d'évaluations, on les décompose en produits de matrices. On parle de factorisation matricielle.\n",
        "\n",
        "Supposons que nous disposons d'une matrice $R$ de $\\mathcal M_{m,n}(R)$ dont les entrées $r_{ui}$ sont les évaluations des films sur Netflix et où chaque ligne représente un utilisateur et chaque colonne un film. L'objectif de la factorisation matricielle est de trouver deux matrices de facteurs latents dont le produit est égale à la matrice $R$. On apprend donc un modéle latent d'utilisateurs $X$ $\\in$  $\\mathcal M_{m,d}(R)$ et d'items $Y$ $\\in$ $\\mathcal M_{d,n}(R)$ afin que le produit $\\hat{r}_{ui}$ = $x_u^T$ $\\cdot$ $y_i$ estime l'entrée $r_{ui}$ de la matrice $R$. Le nombre de variables latentes est égale à $d$. Ces facteurs latents sont en général les attributs des items. Dans le cas des films, il est évident que les utilisateurs préferent certains genres, acteurs ou encore réalisateurs. Ces catégories représentent les facteurs latents. Deux utilisateurs fans d'un même réalisateur ou qui apprécient un genre en particulier aiment vraisemblement des films similaires. Pour un utilisateur, un attribut peut être par exemple un nombre indiquant à quel point il aime les films de comédie et pour un film, un nombre indiquant son caractère humoristique (par exemple 1 s'il s'agit d'une comédie et 0 sinon). Par conséquent, les entrées de $X$ traduiront la force de préférence des utilisateurs pour les attributs choisis (genre du film dans notre exemple). Ces informations nous permettront de prédire les notes manquantes dans la matrice et donc recommander les films non évalués."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uHFe36dHdayq",
        "colab_type": "text"
      },
      "source": [
        "Pour déterminer les variables latentes $X$ et $Y$, on minimise la fonction objective suivante:\n",
        "\\begin{equation}\n",
        "    \\mathcal{L} = \\sum_{(u,i)\\in \\Gamma }(r_{ui}-x^T_u \\cdot y_i)^2\n",
        "\\end{equation}\n",
        "Le terme $\\hat{r}_{ui}$ = $x^T_u \\cdot y_i$ représente la prédiction de l'évaluation de l'item $i$ par l'utilisateur $u$. $\\Gamma$ est l'ensemble des ($u$,$i$) telle que $r_{ui}$ est connue. \\\\\n",
        "Afin d'éviter le surapprentissage, on ajoute à la fonction objective précédente des termes de régularisation. L'égalité précédente se réécrit de la manière suivante:\n",
        "\n",
        "\\begin{equation}\n",
        "     \\mathcal{L} = \\sum_{(u,i)\\in \\Gamma }(r_{ui}-x^T_u \\cdot y_i)^2 + \\lambda (||{x_{u}}||^2 + ||{y_{i}}||^2)\n",
        "\\end{equation}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "93b4Q28kdxTx",
        "colab_type": "text"
      },
      "source": [
        "#Descente de gradient stochastique"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZRaF17tOestk",
        "colab_type": "text"
      },
      "source": [
        "La minimisation de la fonction objective $(2)$ par la descente de gradient stochastique a été popularisée par Simon Funk. Comme dans l'algorithme précédent, on commence tout d'abord par initialiser les matrices de facteurs latents $X$ et $Y$. On définit un ensemble d'entraînement sur lequel on passe en revue toutes les évaluations de la matrice de départ. A chaque itération, on évalue l'erreur de prédiction $e_{ui}$ définie comme suit:\n",
        "\\begin{equation}\n",
        "    e_{ui} = r_{ui} - \\hat{r}_{ui}\n",
        "\\end{equation}\n",
        "\n",
        "On met jour les variables latentes $x_u$ et $y_i$ dans la direction opposée au gradient avec un pas $\\gamma$.\n",
        "\n",
        "$x_u$ $\\longleftarrow$ $x_{u}$ + $\\gamma$ $(e_{ui}y_{i}- \\lambda x_{u})$\n",
        "\n",
        "$y_i$ $\\longleftarrow$ $y_{i}$ + $\\gamma$ $(e_{ui}x_{u}- \\lambda y_{i})$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "x2YACDqCM5_0",
        "colab_type": "text"
      },
      "source": [
        "**Les biais dans la recommandation**\n",
        "\n",
        "Certains films ont tendance à recevoir plus de bonnes notes que d'autres en raison de leur popularité. On constate aussi que certains utilisateurs sont plus généreux que d'autres dans la notation des films. Prenons l'exemple de deux utilisateurs A et B. Admettons que la moyenne des notes de A soit égale à 1.5 et celle de B à 4.7. Une note de 3 attribuée à un nouveau film par l'utilisateur A n'a pas la même signification qu'un 3 de l'utilisateur B. A a sûrement apprécié le nouveau film contrairement à B. C'est la raison pour laquelle on introduit des biais qu'on associe aux utilisateurs et aux films. La prise en compte de ces biais augmente considérablement la pertinence des items recommandés. Les vainqueurs du challenge netflix de 2007 ont d'ailleurs pris en compte ces biais dans leur algorithme. \n",
        "\n",
        "Le biais $b_{ui}$ associé à la note $r_{ui}$ est défini par:\n",
        "\n",
        "$$\n",
        "b_{ui}=\\mu + b_u + b_i\n",
        "$$\n",
        "\n",
        "\n",
        "*   $\\mu$ est la moyenne des évaluations\n",
        "*   $b_u$ biais associé aux utilisateurs\n",
        "*   $b_i$ biais associé aux films\n",
        "\n",
        "Dès lors, la prédiction de la note de l'item $i$ par l'utilisateur $u$ se réecrit:\n",
        "$$\n",
        "\\hat{r}_{ui}=x_u^Ty_i + b_u + b_i + \\mu \n",
        "$$\n",
        "\n",
        "La fonction objective à minimiser est donc:\n",
        "\\begin{equation}\n",
        "     \\mathcal{L} = \\sum_{(u,i)\\in \\Gamma }(r_{ui}-x^T_u \\cdot y_i-b_u-b_i-\\mu)^2 + \\lambda (||{x_{u}}||^2 + ||{y_{i}}||^2 + b_u^2 + b_i^2)\n",
        "\\end{equation}\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Vw0OtNP6h2zo",
        "colab_type": "text"
      },
      "source": [
        "###Création de la matrice et des ensembles d'entrainement et d'évaluation"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "w8v_2topcxJR",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 201
        },
        "outputId": "8a74d7ca-a921-4295-dd71-2c598bff8460"
      },
      "source": [
        "\n",
        "X = movielens_ratings[['user_id', 'movie_id']].values\n",
        "y = movielens_ratings['rating'].values\n",
        "\n",
        "#X_1m = mv_1m[['user_id', 'movie_id']].values\n",
        "#y_1m = mv_1m['rating'].values\n",
        "print ('X')\n",
        "print (X)\n",
        "print ('y')\n",
        "print (y)"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "X\n",
            "[[ 196  242]\n",
            " [ 186  302]\n",
            " [  22  377]\n",
            " ...\n",
            " [ 276 1090]\n",
            " [  13  225]\n",
            " [  12  203]]\n",
            "y\n",
            "[3 3 1 ... 1 2 3]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7uhUSxYZcATO",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 164
        },
        "outputId": "fe175107-1a8f-4ef4-9cd4-8dedf629674d"
      },
      "source": [
        "from scipy import sparse\n",
        "\n",
        "def Convert_to_array(X, y, shape):  \n",
        "    row  = X[:,0]\n",
        "    col  = X[:,1]\n",
        "    data = y\n",
        "    matrix_sparse = sparse.csr_matrix((data,(row,col)), shape=(shape[0]+1,shape[1]+1))  \n",
        "    ratings_matrix = matrix_sparse.todense()   \n",
        "    ratings_matrix = ratings_matrix[1:,1:]                 \n",
        "    ratings_matrix = np.asarray(ratings_matrix)             \n",
        "    return ratings_matrix\n",
        "  \n",
        "\n",
        "ratings_matrix_shape = (n_users, n_items)\n",
        "\n",
        "ratings_matrix = Convert_to_array(X, y, ratings_matrix_shape)\n",
        "print (ratings_matrix)\n",
        "print (ratings_matrix.shape)"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[5 3 4 ... 0 0 0]\n",
            " [4 0 0 ... 0 0 0]\n",
            " [0 0 0 ... 0 0 0]\n",
            " ...\n",
            " [5 0 0 ... 0 0 0]\n",
            " [0 0 0 ... 0 0 0]\n",
            " [0 5 0 ... 0 0 0]]\n",
            "(943, 1682)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zoHnreZbkDq3",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 366
        },
        "outputId": "9e32b71f-87f3-4fd2-a175-2c354540ceb4"
      },
      "source": [
        "from sklearn.model_selection import train_test_split\n",
        "\n",
        "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.33)\n",
        "\n",
        "train_matrix = Convert_to_array(X_train, y_train, ratings_matrix_shape)\n",
        "test_matrix = Convert_to_array(X_test, y_test, ratings_matrix_shape)\n",
        "\n",
        "print ('train_matrix')\n",
        "print (train_matrix)\n",
        "print (train_matrix.shape)\n",
        "print('')\n",
        "print ('test_matrix')\n",
        "print (test_matrix)\n",
        "print (test_matrix.shape)"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "train_matrix\n",
            "[[0 3 4 ... 0 0 0]\n",
            " [4 0 0 ... 0 0 0]\n",
            " [0 0 0 ... 0 0 0]\n",
            " ...\n",
            " [5 0 0 ... 0 0 0]\n",
            " [0 0 0 ... 0 0 0]\n",
            " [0 0 0 ... 0 0 0]]\n",
            "(943, 1682)\n",
            "\n",
            "test_matrix\n",
            "[[5 0 0 ... 0 0 0]\n",
            " [0 0 0 ... 0 0 0]\n",
            " [0 0 0 ... 0 0 0]\n",
            " ...\n",
            " [0 0 0 ... 0 0 0]\n",
            " [0 0 0 ... 0 0 0]\n",
            " [0 5 0 ... 0 0 0]]\n",
            "(943, 1682)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LFrewi0Jlm7r",
        "colab_type": "text"
      },
      "source": [
        "Fonction retournant le MSE"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DSUCxHhmkqBI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#Determining the mean square error\n",
        "from sklearn.metrics import mean_squared_error\n",
        "\n",
        "def mse_calculer(prediction_data, real_data):\n",
        "  prediction_data = prediction_data[real_data.nonzero()].flatten()\n",
        "  real_data = real_data[real_data.nonzero()].flatten()\n",
        "  return mean_squared_error(prediction_data,real_data)"
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LWdnx2FtmHvk",
        "colab_type": "text"
      },
      "source": [
        "#SGD dans la factorisation matricielle"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dMhinBDXL3vW",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class birdi():\n",
        "    def __init__(self, ratings, n_iters, n_factors, gamma, lmbda):\n",
        "        self.ratings = ratings\n",
        "        self.n_iters = n_iters\n",
        "        self.n_factors = n_factors  \n",
        "        self.gamma = gamma\n",
        "        self.lmbda = lmbda\n",
        "        #self.m, self.n = ratings.nonzero()\n",
        "        #lbmda est le terme de régularisation, ici lambda\n",
        "        #n_factors est le nombre de facteurs latents choisi\n",
        "        #n_iters est le nombre d'itérations effectué\n",
        "\n",
        "\n",
        "        \n",
        "    def fit(self, train, test):\n",
        "        self.n_user, self.n_item = train.shape\n",
        "        \n",
        "        #Initialiser X et Y\n",
        "        self.X_u = np.random.random((self.n_user, self.n_factors))\n",
        "        self.Y_i = np.random.random((self.n_item, self.n_factors))\n",
        "\n",
        "        #Initialiser les biais\n",
        "        self.b = np.mean(self.ratings[np.where(self.ratings != 0)])\n",
        "        self.b_u = np.zeros(n_users)\n",
        "        self.b_i = np.zeros(n_items) \n",
        "\n",
        "        # listes contenant l'erreur quadratique de chaque itération\n",
        "        self.test_mse_result  = []\n",
        "        self.train_mse_result = []  \n",
        "        users, items = train.nonzero()\n",
        "\n",
        "        for w in range(self.n_iters):\n",
        "\n",
        "          #Descente de gradient stochastique\n",
        "              for u, i in zip(users, items):\n",
        "                e_pred = train[u,i] - self.rating_prediction(u,i)  #e_pred = erreur de prédiction\n",
        "\n",
        "                #Mis à joutr des biais\n",
        "\n",
        "                self.b_u[u] += self.gamma * (e_pred - self.lmbda * self.b_u[u])\n",
        "                self.b_i[i] += self.gamma * (e_pred - self.lmbda * self.b_i[i])\n",
        "            \n",
        "                #Mis à jour des facteurs latents\n",
        "\n",
        "                self.X_u[u, :] += self.gamma * (e_pred * self.Y_i[i, :] - self.lmbda * self.X_u[u, :])\n",
        "                self.Y_i[i, :] += self.gamma * (e_pred * self.X_u[u, :] - self.lmbda * self.Y_i[i, :])\n",
        "           \n",
        "              predictions = self.all_rating_prediction()\n",
        "              train_mse = mse_calculer(predictions, train)\n",
        "              test_mse = mse_calculer(predictions, test)\n",
        "              self.test_mse_result.append(test_mse)\n",
        "              self.train_mse_result.append(train_mse)\n",
        "              return self\n",
        "\n",
        "\n",
        "    def rating_prediction(self, u, i):\n",
        "      prediction = self.b + self.b_u[u] + self.b_i[i] + self.X_u[u, :].dot(self.Y_i[i, :].T)\n",
        "      return prediction\n",
        "\n",
        "    def all_rating_prediction(self):\n",
        "      all_rating = np.zeros((self.X_u.shape[0], self.Y_i.shape[0]))\n",
        "      for i in range(self.X_u.shape[0]):\n",
        "        for j in range(self.Y_i.shape[0]):\n",
        "          all_rating[i,j] = self.rating_prediction(i,j)\n",
        "\n",
        "      return all_rating    \n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VwRTnH9NlBkI",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "47af3947-5e87-4373-d06c-0b1289c72451"
      },
      "source": [
        "dioula = birdi(ratings_matrix, 200, 5, 0.001, 0.1)\n",
        "dioula.fit(train_matrix, test_matrix)"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<__main__.birdi at 0x7f4c550c35f8>"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 13
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4LWajw_xvXAz",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%matplotlib inline\n",
        "import matplotlib.pyplot as plt\n",
        "\n",
        "def plot_mse(iteration, birdi):\n",
        "    plt.plot(iteration, birdi.train_mse_result, \\\n",
        "             label='Training_MSE', linewidth=3)\n",
        "    plt.plot(iteration, birdi.test_mse_result, \\\n",
        "             label='Testing_MSE', linewidth=3)\n",
        "\n",
        "\n",
        "    plt.xticks(fontsize=20);\n",
        "    plt.yticks(fontsize=20);\n",
        "    plt.xlabel('Nombre d\\'itérations', fontsize=20);\n",
        "    plt.ylabel('MSE', fontsize=20);\n",
        "    plt.legend(loc='best', fontsize=20);"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cI5qr_NrxtJT",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 304
        },
        "outputId": "224d2324-096d-4e54-ead5-6cab56f5ed44"
      },
      "source": [
        "plot_mse(range(birdi.n_iters), birdi)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAaEAAAEfCAYAAADoaHnHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAgAElEQVR4nOydeXiTVdr/P0ma7nvpRvcCBdlBVimyFESQTZBFHRiX0XHmRUdn+YnKjMKLMCLKi4qKiiKiIIsgKFCpLLYsbZEdSlug0FLoTpc0XZImvz/SpA1Nl5S2Scv5XBcXyTnnOc83aZLvc+7nPudItFqtFoFAIBAILIDU0gIEAoFAcO8iTEggEAgEFkOYkEAgEAgshjAhgUAgEFgMYUICgUAgsBjChAQCgUBgMYQJCQQCgcBi2FhaAMC+fftITEwkKSmJS5cuUVpaypQpU1i5cmWT+7h9+zYxMTEcOnSIlJQUsrOzkcvlREREMGPGDGbOnIlUKjxXIBAIrAmrMKFPPvmES5cu4ejoiJ+fH1evXjW7j3379vHWW2/h7e3N0KFD6dy5M3l5eezfv59FixYRGxvL6tWrkUgkrfAKBAKBQNAcJNawYsLx48fx8/MjJCSEhIQE5s+fb/ZI6NixY5SVlTF69GijEU9ubi6zZs3i1q1bfPDBB0yYMKE1XoJAIBAImoFVxKeGDRtGaGjoXY1Shg8fztixY+uE3Ly9vZk7dy4ACQkJd6VTIBAIBC2LVYTjWhsbG93LlMlkzTr+9u1SNJqmDxi9vJzJz1c061ytjbVqE7rMQ+gyH2vV1tF0SaUSPDycmty+w5uQWq3mxx9/BGDkyJHN6kOj0ZplQvpjrBVr1SZ0mYfQZT7Wqu1e1tXhTei9994jJSWFUaNGNduEvLyczT7G29ulWedqC6xVm9BlHkKX+VirtntZV4c2oQ0bNvDll18SHh7OihUrmt1Pfr7CrCsCb28XcnNLmn2+1sRatQld5iF0mY+1autouqRSiVkX7laRmNAabNy4kbfffpuuXbuyYcMG3N3dLS1JIBAIBHfQIUdC69evZ/ny5URERLB+/Xq8vLwsLUkgEAgEJuhwJvTZZ5/x3nvvcd999/Hll1/i6elpaUkCgUAgqId2F45TqVRcuXKF9PT0OnVr1qzhvffeo1evXqxfv95iBpRToGTdzxf5JaGuRoFAIBDUYBUjoZiYGGJiYgDdCgcAp0+fZuHChQB4eHjw6quvApCdnc2kSZMICAjgwIEDhj527NjBBx98gEwmY9CgQXzzzTd1zhMQEMCMGTNa++Xww6HLHDmXBUDXQHfCO7u2+jkFAoGgPWIVJpSUlMSOHTuMyjIyMsjIyAB05qE3ofq4ceMGAFVVVXz99dcm2wwZMqRNTKi8Um14fD27RJiQlaNWqygtLaaiogyNpsqoLidHikajsZCy+hG6zMdatVm7LqlUhp2dA05OrtjYyFv8PFaxdpy1Y26K9q+nb7J13zkqseHhISHMHtu1FdWZR0dLB71b1GoVBQXZODq6YG/vhEwmM1o+ysZGilptfT8QQpf5WKs2a9alUlVRVVVFeXkpSmUJnp6+jRqRuSnaVjES6miEqa/ytscWcqtcOXh7vqXlCBqgtLQYR0cXnJ3dLC1FILA6JBIJNjY2hu9HaWkxbm4tm23c7hIT2gOeBeewlVQRYHMb19uXLC1H0AAVFWXY2zd9nSuB4F7F3t6JioqyFu9XmFAr4OjuYXhsV56LiHhaLxpNVbMXthUI7iVkMlmde6YtgTChVsDZL8jw2ENbSGm5uoHWAksjNjoUCBqntb4nwoRaAVuvAMNjH1kxObdbfggrEAgEHQFhQq2AvLYJSYvIva20oBqBQCCwXoQJtQIyZw/UElsAHKUqCvPzLKxIILBOIiMHsWDB83fdz4IFzxMZOagFFAnaGpGi3QpIJBIqHDpho7wJQGX+TaC3ZUUJBCYw94f79dffZNKkKa2kpmOzbt1avvrqcwAmTJjEv/+9xGS7U6d+58UX/wyAn58/27btNqqvqKhg+/YtHDwYQ3r6NSoqKnBzc8PLy5vevfswZsw4Bgy439B+z57dLFu2uEFtps7TVggTaiW0Lr5QbUIUZ1lWjEBQD08//Vydsq1bN6FQKJg163GcnY0nHXbrFtGi5//2223Y2dnfdT+LFi2hoqK8BRS1PjKZjEOHfuXll/+Fi0vdTeN2796JTCajqqpuJppSqWTBgudJSbmEl5cXo0aNxcurE2VlSi5fTmXXrh0oFAojE9LTtWsEI0eOMqnJlI62QphQKyH39IfsUwDYlolwnMA6efbZP9cp27v3JxQKBbNnP46/f+dWPX9ISGiL9OPn59ci/bQFDzwwktjYQ/zyy15mzpxtVFdcXMyhQwcYMeJBfvvtYJ1jt2z5jpSUSwwZMox33lmFXC6vc/z162kmz9utW4TJv7elEfeEWglnn0DDYxd1Aeoq61uWQyAwB/19F5VKxVdffc7jj89gzJjhvP32WwAoFAo2bvyal156gUcfncTo0cOYPHkcr776CufPnzXZp6l7QuvWrSUychAnT57g4MEYnntuPlFRI5g4cSxvvvkaubk59WqrzcmTJ4iMHMS6dWtJTU3m739/iYcfHk1U1AgWLHiec+fOmNSUl5fHsmWLmTx5PGPHjuCpp55g796fjPq7G4YOHY6Pjy8//bSzTl109B4qKyuYMmW6yWP17+P06Y/VMSAAV1dX+vTpd1f62hphQq2E3KvmCtJHVkx+UfsIFQgEjfHGG/+PHTu20adPP2bNepzwcN3aiNeupfHpp2uQSKQMHz6COXOeZNCgoZw8eYL/+Z/nOH78qFnn2bFjG//7v//Bz68zM2bMJjy8C7/+up+XX/4rlZWVTe4nOTmJF154hsrKCiZPns4DD4zk7NnT/O1vfyU9/ZpR29u3C3jhhafZs2c3oaFhzJ79OBER3Xnvvf+ydetms/TXh0wm45FHppKamsKlSxeN6nbv3oG/fwCDBw81eaybm275nIyM6y2ixRoQ4bhWQupWEx7oJC3hRoECX09HCyoSCFqG7OxbbNjwPe7u7kbloaFh/PRTdJ11+HJysnnuuT/y4YfvM2zYA00+T3z8MT7/fANdutQsAPzWW28QExNNbOxhoqLGN6mfo0fjeP31N5k6dZphodCdO7ezcuVytmzZzD//udDQ9tNPPyIr6xZPPDGfv/71JUP5rFmP8/zzf2yy9sZ45JGpfP31Onbt2kHv3rqkpfPnz3H16hWee+4v9R43duxDREfv5YsvPuXWrVs88EAkERE96NSpU6PnTE1NqXcU16tXH7P+Ni2JVZjQvn37SExMJCkpiUuXLlFaWsqUKVNYuXKlRfppCSRye5RSZxw1CmQSLUU5N6GrT5vrEDSfffHp7DqSRnllyy9V0lLY2cqYNiKMh4cGt9k5//SnF+oYEICzs7PJFaF9fHwZMyaKbdu+Jysrq8n3bx57bI6RAQFMnfooMTHRJCVdaLIJ9enTr05G3+TJ01i1agVJSRcMZSqVipiYaJydnXnqqWeN2nfrFsHDDz/C7t11Q2jNwc/Pn8GDhxET8wuvvPJP5HI7du/eYRgl1ceIESP529/+ybp1n7Jz5zZ27twGgJeXFwMHDmbatBn07z/Q5LGXL6dw+XKKybpZsx6/t03ok08+4dKlSzg6OuLn58fVq1ct2k9LUeHQCcdSBaBP0+5vUT0C84hOTLdqAwKoqKwiOjG9TU3ovvvqn25w5sxpNm/+jgsXznH7dgEqlcqoPi8vp8km1KNHzzplPj6+AJSUFDdZr6l+bGxs8PT0MuonPf06FRUV9OjRE0fHuova9u3bv8VMCGDq1OnExx9l//5oRo0ay4ED+xk+fASdOnmjVte/1NesWXOZMmU6iYnHOXfuLKmpyZw/f5b9+/exf/8+nnrqT/zpTy/UOW7ixMm88cZbLaa/pbAKE3rttdfw8/MjJCSEhIQE5s9v3vYHLdVPS6F18YXSa7rHRdkW1SIwnwmDg9vFSGjC4LYzINBddZvi8OGD/Pvfr2Jra8vgwUPp3DkQBwcHJBIJp079zunTJ826l3NnejhgWGzWnE3gTPWj76t2PwqF7oLRw8PTZPv6ypvLiBEP4unpxa5dO6isrKSsrIwpUx5t0rH29vaMHDmakSNHA7pR3K5dO/jgg/dYv/4LRo0aQ7du3VtUb2thFSY0bNgwq+qnpZB7dobqKUK2ZbmWFSMwm4eHBjN5RKjVbjhmKV31LWT5xRefIJfL+eKLbwgNDTOqW7HibU6fPtkW8pqNk5Nu9HP7doHJ+vrKm4uNjQ2TJk1h48b15OTk4OPj2+yQmFwuZ+bM2Vy8eI7o6L38/ntiuzEhkR3Xijj71qRpO6sLxJYOgg5NZuYNQkPD6hiQRqPh7FnT6dDWREhIKHZ2dly5kopSWVqn/uzZ0y1+zilTpiORSMjJyeaRR6be9bYiDg46I21PPzXChFoRp1pzhTpJiigpUzXQWiBo3/j5+ZORkUFeXs2oX6vV8uWXn3HtmmXvzzYFuVxOVNRDKBQK1q9fZ1SXmprCvn0/t/g5AwIC+b//+4hly1by2GNzGm2/c+c2zp8/Z7Lu+vVrHDoUA0D//gNaVGdrYhXhOGvHnP3S9Xh7u6D1ciQVKTZocJOWoaosxzukZbfGbQ7e3pZboqMhLKErJ0eKjU3D12KN1VuK1tYlkxm/N/owXH3nffzxJ3nnnWU8/fSTjBkThY2NDWfPniYtLY3IyAeJi/utTp/6fmuXSaUSk+fXl5k6xpQ2fVuptKatKe21y/7nf17i5MlEvvtuA0lJF+jbty95eXn8+ut+HnggksOHD2JjI2vWe69/XbX1gG7yqonWJvUlJBxn5cr/4u/fmb59++Hr60dlZSUZGenExx9DrVYze/bj9OnTp855L19O4auvPqtX33PP1U1muPN1SqXSFv+eChNqAvn5CjSapo9vvb1dyM0tAUAh88C9Kh+A9OQUPN1dW0VjU6mtzZqwlC6NRtPgvRVL3ntpiLbQVVVl/N7ow8n1nXfKlBnI5bZs3vwde/bsxs7Ojr59B/Daa29y6NCvxMX9VqdPfb+1y/TfNVNtq6pXHrnzGFPa9G01Gl3b+t6z2mVubh588smXrF27huPHj3DhwnmCg0P4xz8WYm9vz+HDB3FwcGzWe69/XXo9ekzpqv289uMXXniRPn36c+JEAufPn+Pw4YNUVVXh4eHJAw+M5JFHpjJixEiT72dqagqpqaZTtAGeftp45QpTujQaTaPfU6lUYtaFu0RrZTcq4uPjmT9//l3P72mpfuDuTCj122X4ler+8BcDZzB0Uv1zANoCYULGZGVdx88vpN76e9mEmoO16oK717Z27Rq++eYr3nvvw3pGL5bR1VqY0tXY9wXMNyHrjDN0ILQuvjVPisRq2gKBtVP7npaeK1cus23b97i6utU7GVTQPEQ4rpUxStNWijRtgcDaefbZeQQGBhEW1gUHBwdu3Ejn6NE4tFot//rX69jZ2VlaYoei3ZmQSqUiPT0duVxOcHDbTtJrDs4+gVC9RqGTumXnGQgEgpZn2rQZxMYeIiYmmrIyJc7OzgwdOpy5c//AwIE1K3Xv2bObW7duNtpft27defDB0a2ouH1jFSYUExNDTIwutTA3VzdaOH36NAsX6hYW9PDw4NVXXwUgOzubSZMmERAQwIEDB5rdT1vhHhCMfv1sT4qoVKmxlVvF2y4QCEzwzDPP88wzjW85vmfP7iZNwJ04cbIwoQawil/DpKQkduzYYVSWkZFBRkYGAAEBAU0yj5bqpyWRO7lRoLXDUVKBnUTN7ewsfAMDGz9QIBBYNR99VH+6s6DpWF12nDVyN9lxAKlfLMRPo7sxlDXwz3Qb1HKZNeYisuOMEdlxLYu16gLr1daedInsuHZKuX3NXh/luY3HkAUCgeBeQZhQG6CplaatLRZp2gKBQKBHmFAbIPeo2erbVpljQSUCgUBgXQgTagOc/WoSEZxUty2oRCAQCKwLYUJtgEfnIPR5Da7aYjSqpm/sJRAIBB0ZYUJtgLOTA7e1umwRqQQUOZkWViQQCATWgTChNkAikVAsq9kauPhWhgXVCAQCgfUgTKiNKKudpp0vRkICgUAAwoTaDK1zrTRtsZq2QNBk1q1bS2TkIE6ePGFpKYJWwCqW7bkXsPH0h+pFtG1KxWraAusgMnJQ441q8frrbzJp0pQW1bBnz26WLVvcKn23FSdPnuCll3Q7k/r7d2bLlh8Nu73WRqlUMn36RJTKUgC2bt1FUJDxMl4HDsTw008/kpJyiZKSYpycnPH09CQiogeDBw9l4sTJhra3bt1k1qzG9yjbunUX/v6dG21nCYQJtRFOPgGQrHvsrBKraQusg6effq5O2datm1AoFMya9TjOzsbLr3TrFtFW0gzMnDmHceMm4Ovr1+bnNheZTMatWzdJTIxnyJBhdep//fUXlMpSZDIZVVVVderfeedtdu/egZ2dHcOHR9K5c2e0Wrh+/RpHjvzGqVO/G5mQHmdnZ2bNerxeXc7OLbsld0siTKiN8PL1o0Jrg51EjT3laMpLkNpb7wdDcG/w7LN/rlO2d+9PKBQKZs9+3Cqunt3d3XF3d7e0jCYxaNBQTp06wa5dO0ya0K5dO/Dy6oSvrx8XL543qjtz5jS7d+/Ax8eXTz/9Eh8fX6N6tVrNqVOmQ5LOzi4m/5btAWFCbYSnmwMpVa4E2ehGQar8TOwCelhYlUBgHhcunGfTpg2cPXuG4uIiPD29GDbsAZ555nk6dfI2apuZeYONG7/m5MlEcnNzsbOzw9vbmz59+vH883/Fzc2dBQueN2yHsGzZYpYtW2w4Xh9CWrduLV999TkffPCp0X4+kZGD6N9/IEuXrmDt2jUcPfobxcXFBAQE8fjjf+CRR+qGqSorK/nmm6/Yt28PeXk5dOrkzfjxD/PUU39i7NgH6N9/4F2tju3m5saDD47h0KFfuX37Nh4eHoa6y5dTSUq6wLx5T5vcAuL8+TMAjBo1to4BAdjY2DB4cF1ja+9Y3IT27dtHYmIiSUlJXLp0idLSUqZMmcLKlSvN7isrK4vVq1cTGxtLYWEhPj4+REVFsWDBAtzc3FpBfdOxkUkplroDOhMqSU8WJiRoV/z004+8++4y5HI5I0Y8iK+vLxkZGfz0048cORLL2rXrCQzUjZzy8vJ47rk/UlqqYPjwEYwaNZbKykpu3cokOnoPM2fOxs3NnUmTpuDi4kJs7GFGjhxF16414b6mhJAUCgV/+cszyOVyRo+OorJSxcGDMSxfvgSpVGoUutJqtSxa9P84ejSOwMBgZsyYTVWVmr17fyIt7WqLvU9Tpz5KTEw0e/f+xBNPzDOU7969A4lEwuTJ00yakP436saN9BbT0h6wuAl98sknXLp0CUdHR/z8/Lh6tXkfhvT0dObOnUt+fj5RUVGEh4dz9uxZNmzYQGxsLJs2bTK6KrEEeQ6hUKF7fbLkX9EOnojExtaimgSCppCefp2VK5fj5+fPRx99hre3j6HuxIkE/v73BaxevZJ3330fgEOHYiguLuKll/7B7NnG9yrKysqQSnU37fWJCDoTGm12YsLlyylMnjyNf/3rdWQyGQCzZz/OU089zrfffm1kQvv2/czRo3H06zeA//u/j5HL5QA8++wL/PnPT5n3hjTAgAH3ExgYxE8/7TSYUEVFOdHRe7n//sEEBJjeT2zo0Adwdnbm2LEjvPrqK0RFTeC++3oSGBhkMsmhNgpFCevWrTVZ5+XlxfTpj93di2pFLG5Cr732Gn5+foSEhJCQkMD8+fOb1c/ixYvJz89n0aJFzJtXc/WxfPly1q9fz6pVq1iyZElLyW4Wt30GUnT9GG7SMmwqi1FdOoxt7/EW1SSon8qzeyn5/UdQlTfe2FLI7bG7fxq2fSe26ml27tyGWq3mb3/7p5EBAQwaNIQRIx7k6NFYSktLsbNzMNTZ2dnV6cvBwaFOWXOxt7fnxRdfMRgQQFhYOH369OP06ZMolUocHR0B+PnnnwB47rm/GAwIwMXFhaee+hNLlvy7RTTpRzuffvoRp0+fpH//gRw8+CsKRQlTpjxa73He3j4sW7aSd95ZypEjsRw5EguAo6MTvXv3ZcKEiYwbN8HotepRKBR89dXnJvvt2jVCmFBDDBt29zHO9PR04uLiCAgI4MknnzSqe/HFF9myZQu7du1i4cKFhg+kJejd1ZdfL/VmhlMiABWnf0beY5QYDVkplWejrduAAFTlVJ6NbnUTOn/+HACnT/9OUtKFOvWFhQVUVVWRkXGdrl17EBk5irVrP+b9998hIeEYQ4YMp0+ffoSFhTd6VW8OgYHBODnV3UBNf0+lpKTY8J1PSUlGKpXSu3ffOu379u3fYppAN8L74otP2b17B/37D2TXrh24u7s3us33wIGD2LTpB86dO8OpU7+TmprMuXNnSUg4RkLCMfbu/YkVK/4PW1vj3ww/P3+2bdvdoq+hrbC4CbUE8fHxAERGRiKVGs+/dXZ2ZuDAgcTFxXHmzBmGD7fcrqZ9u3ix2bY3UZrzuEnLQFmIKvk3bHuNs5gmQf3Y9p1ARTsYCdn2ndDqpykuLgLgu+++abCdUlkG6H4UP//8a7788jPi449y+PBBQGcOjz8+j1mz5raIrjtTyPXoRwsaTc3OoKWlClxdXbGxqfuz5+HhWafsbvD09GLEiJEcOnSARx+dxdmzp5k79w9GI7D6kEql9Os3gH79BgC6e1mJifG8/fabnDiRwM6d25g9+4kW1WtJOoQJ6e8jhYaGmqwPCQkhLi6OtLQ0i5qQTCpleN8gDpzoxaNOulTLytN7dKMhWeMfTkHbYtt3Io4DH2k3Wy+3JvrRRnT0IZMjDz21dYWGhrFkyXLUajWXL6dy4kQ827dvYfXqlTg42DN58vQ20a7HycmJ4uJi1Gp1HSO6fbvl5+5NnTqDw4cP8p//vFb9vHmvVyKRMGTIMJ577i/8979L+f33RGFC1oZCoQB0sV1T6MtLSkqa1b85+6Xr8fY2reXRsRG8cPQyUQ7ncZWWoy0twD4zAdf7H26WtuZQnzZLYwldOTlSbGwaXr2qsXpL0dq6ZLKa96ZPnz4kJydx/vwZRowYaZYuGxtbevfuRe/evejfvz8vvPAnYmMPM336DADkcv09Dq3J16RPYqitR49EIjF5jD7kV/uYiIjunDiRSFLSOQYMuN+ovT49ur7+GkMmk1YfX/P6hw8fjp+fP1lZtxgwYCDh4eEm9UHT/pa1R3369vrjm9qHudzZp1QqbfHvaYcwodYmP1+BRr8hUBPw9nYhN7d+w7uvix+/3ujNo4660VB+7HbKA4a0yWioMW2WwlK6NBpNgyOKth5xNJW20FVVVfPePProbHbu/IFVq97D3z+Q4OAQo7YqlYqLF89z//33o1ZruHQpicDAoDrhstzcPADs7OwNfTs7uwJw69Ytk69J/92rrUePVqs1eYxWW/eYiRMnc+JEIp9++rFRdpxCoeDLLz9vsL/GqKrSVB+P0fFvv/0u2dlZhIaGGpXX1ge6Y44fP0pFRTkjRjxYZ6SmVCrZvPk7APr1G2DoS3+8vo+WxNRnTKPRNPo9lUolZl24dwgT0n/Q6xvp6MvrGym1NaMHdGbN5QjG2Z/HpXo0pEqOxbbnWEtLEwhMEhISymuv/Yfly5cwb95shg59gKCgYKqq1GRnZ3HmzGnc3d3ZsmUHANHRe/jxxx/o27cfAQGBuLi4kpl5gyNHYrG1tTVK2+7Vqy/29vZs2fIdRUWFeHp6AfDYY3PrvefTHCZNmswvv0QTH3+UefPmEBn5IGq1msOHD9CjR0/S06/Xuad8t3Tv3oPu3Zs2HzA9/RoffPA+Li6u9OvXn8DAYGQyGbm5ORw9GodCUULPnr2ZOXN2nWMbStEGXaKENax+YYoOYUL6Ye61a9dM1l+/fh2AsLCwtpLUIL3DvHB1debX8l5Md/wdgMrTPyPv/iASWYf4kwg6IBMmTKJr1wg2b97IyZMnSEw8jr29A506dWL06LFERT1kaDtu3ARUqkrOnTtLcvIlKioq8Pb2Zty4h5g790nCw7sa2rq6urJ06Qq++upz9u79ibKyMsP5WtKEJBIJy5a9yzfffEV09B62b/8eL69OPPzwI8yYMYvY2EM4OTm12PnM5aGHJuHo6ERiYjxXrqRy+vQpysqUuLi40K1bBGPGjGPKlOkmkxsaStEG3dwlazUhiVY/LrQC4uPjmT9/vtkrJqSnpzN+/HgCAgKIiYkxuppRKBSMHDkSrVbL0aNHm5Wi3dLhOIDdR6/x82/J/Md9By5SXfaV3cinsL1vtNn6zEGE44zJyrqOn19IvfX3cjiuOVirLmhYW2LicV55ZQF/+MNTvPDCAqvRZUlM6Wrs+wLmh+Os845rPahUKq5cuUJ6uvGyFsHBwURGRpKZmcm3335rVPfhhx+iVCqZOnWqRecI3cnIvv5USW05UN7TUFZ5ajfaKrUFVQkEHZu8vLrbqBQVFfLJJx8BNDqPR9DyWDz2ExMTQ0xMDAC5uboPyOnTp1m4cCEAHh4evPrqqwBkZ2czadIkAgICOHDggFE/b775JnPnzmXp0qUcO3aMLl26cObMGeLj4wkNDeWVV15pw1fVOO7OdvTv1om45O5E2V/AWVqBVpGPKiWu1UdDAsG9yocfvs/ly6n07t0Xd3cPcnNzOH78KMXFRUybNoOePXtbWuI9h8VNKCkpiR07dhiVZWRkkJGRAUBAQIDBhBoiODiY7du388EHHxAbG8tvv/2Gt7c38+fPt4oFTE0xun8AvyfncqC8F1MddQsaVp7+CXn3SCRSi/9pBIIOx4MPjqWgoIAjR2JRKEqwtbUjLCycyZOnMXnyNEO7kydPcOrU74325+Li0qHm7FgCq7onZK20xj0hAI1Wy2trj1FUWMKb7j/gLK0AwO7Bp7HtMarZeltCW1sj7gmZh9BlPuZo028f0RgtsVyOtb5nbXVPSFxuWxCpRMLo/gFsPXSFg+U9meJ4CoCK49+DWoW852gxIhIILMCzz/653W4S195oV4kJHZERffyRSSXElvdAoalecSbwzrwAACAASURBVLhSScXRjSi3/Qd1+lnLChQIBIJWRJiQhXF1suX+7t5UIOcLxRiUspp7V5rCm5Ttex/lnpVUFWRaUKVAIBC0DsKErIDR/QMASFP7sKx4KrKBM0Fub6ivunEe5fZFlMd+jaas2FIyBQKBoMURJmQFdA92x89TN4eppELCCfn9OM15B3mPUboVEQG0WlRJBynd/CqVZ/airVJZUHHHQuTmCASN01rfE2FCVoBEImFU/5olNfYnZqCUOGL/4NM4zliCLKBXTWNVGRXx31O69Q1UaSfED+hdIpXKqKqqsrQMgcDqqaqqQiqtu6vr3SJMyEoY0ccfm+pl2TPzSlmyPpHrWSXIvIJwmPRPHCa8jMTNz9BeW5xD+f6PKPvpv1TlXbOQ6vaPnZ0D5eWllpYhEFg95eXGW7e3FMKErARnBzmzxnQxPM8rKmfZxt+JO3tLt8dJSH+cZi3F7oEnwa5mkcWqW8kof1hM2aEv0JTetoT0do2TkytKZQkKRRFqtVqMLAWCWui2tlCjUBShVJbg5OTa4ucQk1WbQGtNVjXFqZRcvvj5ImUVNSGi0f078/i4COTVG0xpyxVUnPwR1YUDoK0VSrKxw7b/JGz7PozExq7FtbUmltSlVqsoLS2moqIMjcY4NCeVSo22iLYWhC7zsVZt1q5LKpVhZ+eAk5MrNjZN2Z7cvMmqwoSaQFuaEEB2gZKPdpwjM7cmTBTm78Jfp/fBy60ma05TeIvy499TlX7a6HiJkyd2Qx7DpuswJBLjwa4wIfMQuszDWnWB9WrraLo69Cra9wq+no4smjeIoT19DWVpt0pYvD6RC9cKDGVSd38cH34Zh0n/QuoZaCjXlhZQfvAzlD8upSr7cptqFwgEAnMQJmSl2NnKeH5KTx4f1w2ZVJemrShT8f73p/n52DU0tQawNoG9cJyxBLuRTyFxqInZanKuovxxKWUxH6MpyWvrlyAQCASNIkzIipFIJIwfFMT/e2IAbs62gG4P++2Hr7Lmh3Moy2v2HpJIpdjeNxqnOe9g2/8RqLVDq/pqAqVbFlKRsI3KnOto1RVt/loEAoHAFFZzTygrK4vVq1cTGxtLYWEhPj4+REVFmb0NQ3R0NBs3buTixYuoVCqCgoKYOnUqTz/9NLa2ts3S1tb3hExRpKjgkx8vkJJRaCjz8XBgwaN9CPSpG3/VFOdSkbAV9dUEk/1JHN2RuvogcfVBqv/n5qsrs2v7LY47Wly8tRG6zMdatXU0Xe0yMSE9PZ25c+eSn59PVFQU4eHhnD17lvj4eMLCwti0aRMeHh6N9vP++++zdu1aHB0dmTBhAm5ubpw4cYLz588zfPhwPv/8c5P7szeGNZgQgLpKw7ZDV/glMcNQZiuX8tTEHgzr6Wf6mKxUKo59hyY3reknsnOqMabqfxK9QTm4IdGv4tCCdLQvYmsjdJmPtWrraLra5VYOixcvJj8/n0WLFjFv3jxD+fLly1m/fj2rVq1iyZIlDfZx4cIF1q5di6urKz/88ANBQUGALs/9rbfeYvPmzWzcuJGnn366VV9La2IjkzI3qhvhnV35as8lKlRVVKo0fLbrIlczi5k9tqthwqvhGL9uyKb/G/Xl46guH0eiyEFdmGuc2n0nFaVoctNMG5eNbbUx+SJx9TY8lrr6IHH2QiIVEV6BQNB0LD4SSk9PZ/z48QQEBBATE4O01o+YQqFg5MiRaLVajh49iqOjY739rF69mo8//phnnnmmzk6sRUVFDBkyhKCgIMNW4uZgLSOh2mTmlbLmh3NkFSgNZV0D3fjLtN54uJieI6TXlpNdiFaRj6Y4x/BPW5yDpkj3mKrK5omSypC4dKo2Je8ac3L1QerSCYlN/eHQjnY12NoIXeZjrdo6mq52NxKKj48HIDIy0siAAJydnRk4cCBxcXGcOXOG4cOH19tPXp4u+0s/AqqNm5sbbm5uhm3DTbVpbwR0cuLffxzElz8n8XtKLgCXbxSxeH0if5nWi+7B9YcvJVKZ4V7QnWi1WrTKwhpjKs5BU5SNpiQXTVE2VCpN9FiNpgptUTZVRdnUHWdJkDh5VN938kZSbVBSgw4Xs98DgUDQ/rG4CV29ehWA0NBQk/UhISHExcWRlpbWoAnp7xnduHGjTl1xcTFFRUUApKWldQgTAnCws+Gvj/ZmX0I62w5dQauF4tJK3t10mlljuvDQ4CCz799IJNVm4eQB/t3r1GvLFUYjKE1xNtpinUFpy4oa6FmLtrSAqtICqm4m1alVyGzAxg6JjZ1uxCTXPTb8b2N7x3M7JHJTZTX/649DJm+V+1gCgeDusbgJKRQKAFxcTF8J68tLShoeFo4aNYq1a9eydetWnnjiCQIDdZM3tVotq1atMrQrLjZ/Px5zhpZ6vL3b7sp+/uTe9O/hy4pvTlCkqESj1fL9gcvcyFfy0uz+ONobJ2PcnTYXwN9kjaayDNXtbNS3s1HdvlX9uPr/4jzQNrA0SZUaqtRoK0pp8fiwRIpEbodUbofE1h6p3BaJ3F73XG6PxNYOqdz+jja6OkWOHY76toZyu5rjbe3qrErRVrTlZ8wcrFUXWK+2e1mXxU2opbj//vt57LHH2LZtG1OnTjXKjktOTiY8PJyrV6/WCfk1BWu8J3Qn/m72/Hv+ID7eeZ6rN3VGe+TMTa7eKGTBjD74ezm1jTapF3h5gVdPQPcBswG0VWq0JXmG0ZPRvajiXNCoG+z2rtBq0FaWUVVZBq2xYLZMbjwik1eP5mqPzIxGabaGsjvb1hnRyUx/RTvafYS2wFq1dTRd7e6ekLOzTmx9Ix19eX0jpdosXbqUvn37smXLFvbu3YtEIqFfv3588803fPLJJ1y9ehVPT8+WE29leLra8+oTA9l8IJWDJ3Xbgd/KV7Lk6xM8O+k+BvWoew+orZDIbJC4+yF1r5tKrtVq6eRpT96tfLTqCrSqCqj9v7oCVBXVdZU1ZepKk210/1caHreqwQFUqXSbDFYoWmEUJ4M7wo4SGztuOTpQqdJUb3ooAYlENyKr9Rz9c0OZtLqdvqxWvb49Nc/r9mfcD7X60fdZ5OJAZWml8TH68zaiy3DeRnQ1tz+VTSmaEmXd/u58/xp4nYb3T9BiWNyEwsPDAbh27ZrJ+uvXrwMQFhbWaF8SiYQ5c+YwZ86cOnUpKSlIpVJ69epl4siOg9xGyryHutOlsysb9iVTqdZQUVnFxzvP8/CQYF54rJ+lJdZBIpEgtbFFYu+MBPNDn42h1VQZm1q1Sd1ZZsrcbGUayhWK+g1P3cxMwiaLr4LKMrSVZbqn1cVlrXvWZmPNa3G06CC4WSZu2uTKbWRUabQt0J+kJjTcBEOVNHAuJFKKA0PR+t/fYFZrS9AkE9q5cyc9evSgR48ehrLKykoqKysNI5naJCQkkJCQwIIFCxrte+jQoQDExcVVLxtunKJ98uRJHBwc6Nev+T+e8fHx3Lx5kzFjxjRpRNUReKC3P4HezqzZcY7cwnIA9iWkE3fuFl0D3IgIcqd7sDvBvs7IOvjcHolUBraOSGzrT/Gvj8ZCElqtBtSqO4zpTsOrNrZao7Q729Y8NjbHBu+jCSyHVgtU0dDQt6mjYlVL6GkF8s6B7ZDHsOs/uVXP0yQTWrhwIQsWLDAyoc8++4w1a9aQlFQ30ykhIYE1a9Y0yYSCg4OJjIwkLi6Ob7/91miy6ocffohSqWTOnDlGc4SuXLkCQJcuXYz6UigUdUwxMzOTRYsWIZfLefnll5vycjsMwb4u/OepwXy++yJnr+QDukVQT1/O4/RlXUq7va2MboE6Q4oIcifUz6XOhFdB/UgkUl2YTG4HLbzppFar1YUS9aFIdQWodGbm5mxDUaGy+sdQA1qtrr1WW21c+sfVz7VaQ5lW/9xQVut5s/qreexgb0OZssJk39pafdNA37X7u/NcRv01oN2ov+pjZVKoUlc1oT8afF/uJerbl6wlsXg4DuDNN99k7ty5LF26lGPHjtGlSxfOnDlDfHw8oaGhvPLKK0btJ02aBEBycrJR+euvv87Nmzfp2bMn7u7u3LhxgwMHDqBWq1mxYoWRid4rONnLeemxvkTHpxOdmEFxqXH4qLyyinNX8zl3VWdStnIpXQPc6B7kTvdgD8L8XQ2b6QnaFolEAjK5LvHhjjClo7cLpVZ4M7uTld5kh5ZLANA2YHi1DVXbgIHWNjkPD0cK8hUN9qdtxJAbvXAwcRGhbUSXe1AopW7d7vr9agyrMKHg4GC2b9/OBx98QGxsLL/99hve3t7Mnz/frAVMx4wZw/fff090dDSlpaV4eXkxYcIEnn/++TqjpnsJqUTCxGEhPDw0mEokHDuTSUp6IckZhdwuMY7iV6o0XLx2m4vXbgNp2MikdOnsSvdgd7oHuRMe4IadXGaZFyIQWAFGiR0NtWtif7adXJBprc+4nbxdULbBBYVVmBCAv78/y5cvb1LbO0dAeh599FEeffTRlpTVoZBIJAR6uzC6fwCj+weg1WrJLSonOf22wZTyisqNjlFXaUjO0NUByKQSwvxrTKlroBv2tlbzMRIIBO0M8etxDyORSPBxd8DH3YGRfTsDkF9UTkpGIckZt0lOLyT7tnEeVpVGy+XMIi5nFvHzsetIJRJC/FwM95QiAt3qTI4VCASC+hAmJDDCy82e4W5+DO+tm89zu6SClIzCamMq5GaecaKrRqsl7VYxabeK2RefjgQI8nWme5CHwZicHYQpCQQC0zTZhEpKSrh586bhuX75m1u3bnHnQtzNWRpHYJ14uNgxtKcvQ3v6AlCsrDSE7pLTC8nMNZ6gqQXSsxWkZyvYf0K371GAt5Mh0SEiyB03p9addyAQCNoPTTahDRs2sGHDhjrlY8eObVFBAuvG1dGWQT18DKsvKMpUpN7QGVJyRiHp2SV1slgzc0vJzC3lQPUqDn6ejoZ7St2DPRrcekIgEHRsmmRCnTt3bm0dgnaKs4OcAd28GdDNG4CyCjWpN4pIztAlO1zLKqmeDV5DVoGSrAIlh0/rRtY+7g7cF+aFj5sdQT7OBPk44+YsjEkguBdokgkdOHCgtXUIOggOdjb07eJF3y5eAFRUVnE5s4jkjEJS0m9z9VYx6ipjU8opLCPnlPEWHK6O8mpDcjEYk5+Xo5hIKxB0MERigqBVsbOV0SvMk15huoVjK1VVXL1ZrDOljEKuZBZRqa67NE2xUsWFa7e5cO22ocxGJqFzJ6c65iQSHwSC9oswIUGbYiuX0SPEgx4huk0I1VUarmWVcFupIulKHhk5Cm7kllKhqrs3q7pKa0h6gCxDuYdLTRhP/8/XwxGpVKx2LBBYO00yofLycnJzc/Hw8DC5Ntvy5cs5fvw4Wq2WwYMH8+qrrzZp1WuBwEamWybI29uFwd06Abq079zbZWTkKEjPUXAjR0FGTgn5xabXaL5dUsHtkgrD+nigW34ooJNzHXNysBPXXQKBNdGkb+TGjRt577332LRpE/379zeUKxQK5s2bZ5SmfejQIc6fP8/u3bsNW24LBOYglUjw9XTE19PRaA+k0nIVN6qNKaP6X2ZuKeqquuG8SpXGMH+pNp3c7GuZkgtBvs54u9mLPWIEAgvRJBM6ceIE/v7+RgYEsGnTJm7evMmAAQNYsWIFTk5OfPzxx2zcuJFvvvmGl156qVVEC+5NnOzldA/2oHtwzcVNlUZDVkEZGTklBmPKyFFQpDC9z09eUTl5ReWcSs0zlNnbygisNVoK9nEhwNtJrJEnELQBTTKhK1euMHDgwDrl+/fvRyKRsGzZMoKCggBYtGgRhw8f5vDhw8KEBK2OTColoJMTAZ2cGNazprxYWakzpOwaY7qVX1onXRx0K4lfvlHE5RtFhjKJBHw9HOka5I5PrdGTh4udGDUJBC1Ik0yooKCAgIAAozKVSsXFixcJCwurc/9n2LBh7Nu3zywhWVlZrF69mtjYWAoLC/Hx8SEqKsqsVbRBN2pbt24dycnJ5Obm4uXlRbdu3Zg3bx4PPvigWZoE7RdXR1t6hXrSK7RmO3eVWsOt/FKjEVNGjgJFWd1txbTamvlMtXGyt6mTnde5k5PY7kIgaCZNMqHKykrKy41XV758+TJqtZq+ffvWae/p6UlZWdM3IE5PT2fu3Lnk5+cTFRVFeHg4Z8+eZcOGDcTGxrJp06Ym3V/67rvvWLx4MY6OjowbNw4/Pz+ysrLYv38/v/32Gy+//DJ/+ctfmqxL0LGQ20gJ9nUh2Ldmd12tVkuhorJOOC+rQGly/7LScjWX0gu5lF5oKJNJJfh5Od6RBOEilicSCJpAk0zI29ub1NRUo7KTJ08ikUjo3bt3nfalpaW4u7s3WcTixYvJz89n0aJFRjurLl++nPXr17Nq1SqWLFnSYB8qlYr3338fOzs7tm/fTnh4uKHuypUrTJ8+nU8//ZRnn30WW1vx4yDQIZFI8HCxw8PFjr5dOhnKK1RV3Mwr5bZSXZ06XkJGroKyirqp41UarWFpouMXsg3lrk62dbLz/DzFhFuBoDZNMqEBAwawd+9e4uPjGTp0KOXl5WzduhWABx54oE771NRUfHx86pSbIj09nbi4OAICAnjyySeN6l588UW2bNnCrl27WLhwodEW33dSVFRESUkJ3bt3NzIg0G0DHhoaSkpKCqWlpcKEBI1iJ5cR5u/KEG8XBnbRhfS0Wi35ReV1wnk5haZH/cWllVxIK+BCWoGhzEYmpXMnRzHhViCopkkm9NRTT7F3716effZZunXrRk5ODgUFBQwZMqTOD75CoeDkyZPMmjWrSQLi4+MBiIyMRCo1vkJ0dnZm4MCBxMXFcebMGYYPH15vP15eXnh6enLt2jWuXbtGaGiooS4tLY3r169z3333ibRxQbORSCR0cnegk7sDAyK8DeVlFWoyc0uNQnr1T7jVmJxw6+lqR5C3M0G+Nebk4+4gJtwKOjxNMqE+ffqwfPlylixZQlJSkqHsnXfeqdN2x44dqFQqRowY0SQBV69eBTAyjdqEhIQQFxdHWlpagyYkkUj4z3/+w7/+9S9mzJjB+PHj8fHxITs7m/3799O1a1dWrVrVJE0CgTk42NnQNdCNroE1CTTmTrgtKK6goLiCM3dMuA30Ng7nBXqLCbeCjkWTP83Tpk1jwoQJpKSk4OHhYUjJvpMxY8YwePDgOiOk+lAoFAC4uLiYrNeXl5Q0vtf5xIkT8fHx4R//+Ac7d+40lHfq1ImZM2fWq7kxvLycG290B97epl+PNWCt2jqaLl8fV3p39zUqK1FWcu1mMWk3i0i7WUzarSLSs0pQmVg/r1Kl4erNYq7eNJ5w6+flSESQB4+O6UrXwKbfe20rrPXvCNar7V7WZdYllb29vclsuNoEBgbelaC74ccff+Tf//4348eP569//SsBAQFkZmby8ccfs2TJEhISEli9erXZ/ebnK9CYmF9SH97eLuTmNm6alsBatd1Luvzc7PBz82H4fbr7plUaDVn5yjr3mopKTU+4zcpXkpWvJPZ0JqMHBjDjwXCcrGRLdWv9O4L1autouqRSiVkX7hYf1+vXoqtvpKMvr2+kpCctLY033niDiIgI3n33XcP9pS5duvDuu++SlpbGvn37DMkVAoG1IJNKCfB2JsDbmWG9asqLSytrmVJJ9YRbpWHCrRY4eDKTxKQcHhvdhci+/kjFRFpBO6NJJlQ7tGUO06dPb7SNPmx37do1k/XXr18HaHRB1CNHjqBSqRgyZEidBAepVMrgwYO5cOECFy5cECYkaBe4OtkabYMBugm3GTkK9sSnczI5B9Dtbrt+7yV+O3OTPzwUQaifq6UkCwRm0yQTWrhwoVlLlWi1WiQSSZNMSG8IcXFxaDQaIwPRZ9o5ODjQr1+/BvuprNSFLgoKCkzW68vlcusIWwgEzUFuIyW8sytvPTeM6CNpbP41xZDscPVmMf+7/gSjBuhCdCLtW9AeaHI4TiaTMXbs2CYnHDSV4OBgIiMjiYuL49tvvzWarPrhhx+iVCqZM2eO0RyhK1euALpQm55BgwYBEB0dzTPPPEOPHj0MdUlJSURHRyORSBg2bFiL6hcILIFEIuH+7t70Dvfk52PX2Rd/HXWVFi1w6FQmJy6JEJ2gfSDRak0tTmLMvHnzSExMRCKRMGDAAGbPns3EiROxs7NrERF3LtvTpUsXzpw5Q3x8PKGhoWzevNlofk/37t0BSE5ONurntdde44cffkAulzN+/Hg6d+5MZmYmMTExqFQq/vjHP/L666+brU8kJrQ+Qpd53Kkru0DJdzGpnLuab9QuzN+VPzwUQZh/24TorPX9AuvV1tF0mZuY0CQTAt29mS1btrBz504KCgpwdnZm6tSpzJo1y2jU0Vxu3brFBx98YFjA1Nvbm3HjxplcwLQ+E9JqtezYsYMdO3Zw6dIlSktLcXZ25r777mP27Nk88sgjzdImTKj1EbrMw5QurVbL6dQ8votJJb+4Zq1HCTCqf2dmjOrS6iE6a32/wHq1dTRdrWZCetRqNb/++itbtmzh2LFjaLVaevXqxZw5c3jkkUcaXFqnvSJMqPURusyjIV0Vqir2HLvO3vh0ow3/nB3kzBwVzsh+nVstRGet7xdYr7aOpqvVTag2mZmZbN26lR07dpCTk4OjoyNffPEFAwYMaG6XVokwodZH6DKPpujKvq1kU0yq0bbnAGH+Lvzhoe6tEqKz1vcLrFdbR9Nlrgnd1XK+AQEBvPzyyyxZsgRfX1+USmW92WkCgaBt8fVw5G+P9eXFmX3o5GZvKE+7VcLSr0/w9b5LJvdSEgjakmZPVs3Ozmb79u1s376dmzdvYmdnx9SpU+nVq1fjBwsEgjZBIpEwoJs3vUI92XP8OnuO60J0WuDw6ZucuJTDzFFdeLBfZ7FYqsAimGVCGo2GgwcPsnXrVuLi4lCr1URERPDGG28wbdq0Rlc1EAgElsFWLmP6yHAe6O3Hd7VCdKXlajZEJ1dPdO1OeGcx0VXQtjTJhDIyMti2bRs//PADubm5ODg4MH36dGbPnt3oWnICgcB68PFw5OVZ/aqz6FLIK9Jl0V3LKuHtDScY2a8zM0eF4+Io9twStA1NMqGHHnoIgN69e/PSSy912Cw4geBeoX+3TvQM9WBvfDo/H7tuCNH9duYmvyfnMGNUF0aJEJ2gDWiSCWm1WmxsbMjNzWXNmjWsWbOm0WMkEgkHDx68a4ECgaB1sJXLmBYZxvDefmyOSeX05TxAF6L7xhCii6BLZ7dGehIImk+T7wmp1WqysrIabygQCNoVPu4OvPRYX05fzmNTTAq5hboQ3fWsEt7e8DsP9vNn5qguIkQnaBWaZEKXLl1qbR0CgcDC9O/aiV6hHuw9ns7Px68bNtr77cwtfk/OZcaD4YzqHyBCdIIW5a7mCQkEgo6F3EbG1Mgwlv5pKP27djKUl5ar+eaXFP736xNcySyyoEJBR0OYkEAgqIN3dYjub4/1xdu9ZqLr9ewS3v7md77ck0Sx0vTOrwKBOVh8Z1WBQGC99OtqnEWnD9HFnb3FyeRcZowKZ7QI0QnuAjESEggEDSK3kTF1hC5EN6BbTYhOWaFm4y8pLPk6kcsiRCdoJlYzEsrKymL16tWGrRx8fHyIiooyuZWDKeLj45k/f36j7Q4dOoS/v39LSBYI7im83R14cWZfzl7J47v9qeQUlgGQnq1g2Te/E9nHnz/PbHgHZIHgTqzChO7c1C48PJyzZ8+yYcMGYmNj2bRpk9GmdqYICAhgwYIFJutSUlL45ZdfiIiIEAYkENwlfbt04r4QD/ZVh+gq9SG6c7c4dTmP6ZFhjBkgQnSCpmEVJrR48WLy8/NZtGiR0fbey5cvZ/369axatYolS5Y02EdgYCAvvviiybq///3vAMyaNavlRAsE9zByGxlTRoQxvJcfm35N5VRq9UTXMhXf7k8htnotuq6BYqKroGEsfk8oPT2duLg4AgICePLJJ43qXnzxRRwdHdm1axdKpbJZ/RcUFLB//37s7e2ZPn16S0gWCATVdKoO0b0yux8+Hg6G8vQcBcs2/s66ny9SXCqy6AT1Y3ETio+PByAyMhKp1FiOs7MzAwcOpKysjDNnzjSr/507d1JZWcnDDz+Mq6tYIVggaA36hHvxv88O5Q8Te2BrU/M9PnIui9c+O07MiQyqNJoGehDcq1jchK5evQpAaGioyfqQkBAA0tLSmtX/li1bAJgzZ06zjhcIBE1DbiNlzrjuLH1uKPdHeBvKyyrUfBeTypL1J0i9UWhBhQJrxOL3hBQKBUC9exHpy0tKzN9mNiEhgbS0NCIiIhg4cGCzNZqzVa0eb2/r3VvJWrUJXeZhrbru6+rDW119OHkph7U7znIzrxSAjBwFyzeeZOygIJ6a3BMPF/tGemp5rPU9u5d1WdyEWpPvv/8egNmzZ99VP/n5CjQabZPbW+ue8WC92oQu82gPuoK8HHjzqcH8kpjO7iPXDFl0B05kcOzcTaaPDGfswABk0rYJyLSH98yaaK4uqVRi1oW7xcNxzs46sfWNdPTl5u7aWlhYyC+//IK9vT3Tpk27O5ECgaBZyG2kPDI8lLefG8b93WuH6KrYFJPK4q9OkJIhQnT3MhY3ofDwcACuXbtmsv769esAhIWFmdWvPiFh4sSJIiFBILAwXm72/M+jffj7nH74etZsiHkjV8F/vz3J57svUqSosKBCgaWwuAkNHToUgLi4ODR3ZM8oFApOnjyJg4MD/fqZNxNbn5Bwt6E4gUDQcvQO82LJM0OYOSocW3nNz8+xC1m8/vlx9ieKLLp7DYubUHBwMJGRkWRmZvLtt98a1X344YcolUqmTp1qtJ34lStXuHLlSr19njhxgitXrtx1QoJAIGh5DCG6Pw1j0J0hul9TWfxVogjR3UNYRWLCm2++ydy5c1m6dCnHjh2jS5cunDlzhvj4eEJDQ3nllVeM2k+aNAmA5ORkk/21VEKCkEbYmwAAIABJREFUQCBoPbzc7Pnro324kFbAt/tTyCrQTUi/kVvKf789yfBevswa0xV3ZzsLKxW0JhYfCYFuNLR9+3ZmzJjB2bNn+eqrr8jIyGD+/Pls2bKl0XXjalNUVER0dLRISBAI2gm9wjxZ8uwQHhvd5Y4QXTavf3acX0SIrkMj0Wq1Tc89vkcRKdqtj9BlHh1VV0FxOZsPXObEpRyj8gBvJ/4wPoLuwU2/IG1pba1FR9PV7lK0BQKBQI+nqz1/nd6bf8ztj79XzX3gzNxS3vnuFJ/tvkChyKLrUAgTEggEVkevUE8WPzOEWaO7YCeXGcqP60N0Cemoq0SIriMgTEggEFglNjIpE4eF8PZzQxncw8dQXl5ZxeYDl1n8VSLJ6bctqFDQEggTEggEVo2nqz1/md6bf94ZosurDtHtusDtEhGia68IExIIBO2CnvoQ3Zg7QnQXs3n98+PsixchuvaIMCGBQNBusJFJmTg0hGXPD2PIfTUhuorKKrYcvMxbXyVy6boI0bUnhAkJBIJ2h4eLHS9M682/Hh9gFKK7mVfKik2n+PTH8yJE104QJiQQCNot94V4sPiZIcwe0xU725oQXUJSjgjRtROECQkEgnaNjUzKw0ODWfbcMIb29DWU1w7RJYkQndUiTEggEHQIPFzs+PPUXvy/xwfQuZOTofxmXinvbjrFim9OiBCdFSJMSCAQdCh6hHjw1tODmTPWOEQXezqT1z87zt746yJEZ0UIExIIBB0OG5mUCUN0IbphtUN0qiq2HrzCm18mcPFagQUVCvQIExIIBB0WDxc7np/ai1efGECwn4uh/Fa+kpWbT/PJzvMUFJdbUKHAKvYTAsjKymL16tXExsZSWFiIj48PUVFRLFiwADc3N7P6unDhAl9++SWJiYkUFBTg6upKeHg4jz32GNOnT2+lVyAQCKyV7sEerP77aL7fl8TOuDTKK6sASLyUw9kr+UwdEcr4wUHYyMR1eVtjFSaUnp7O3Llzyc/PJyoqivDwcM6ePcuGDRuIjY1l06ZNTd5TaOPGjbz99tu4uroyevRofH19KSwsJDU1lcOHDwsTEgjuUWxkUh4aEsyQnr5sOXiZ4xeygeoQ3aErxJ27xRPjI+gV6mlhpfcWVmFCixcvJj8/n0WLFjFv3jxD+fLly1m/fj2rVq1iyZIljfYTFxfH0qVLGTFiBKtXr8bZ2XhPC5VK1eLaBQJB+8Ld2Y7np/RiVL/ObNyfQmZuKaAL0b23+TSDevgwd2xXPF3tLaz03sDiY8/09HTi4uIICAjgySefNKp78cUXcXR0ZNeuXSiVykb7WrFiBfb29qxcubKOAQHI5fIW0y0QCNo33YM9ePOpwcyN6oZ9rSy6E5d0E133HBdZdG2BxU0oPj4egMjISKRSYznOzs4MHDiQsrIyzpw502A/KSkpJCcnM2LECNzd3Tl+/Djr1q3jyy+/5NixY2jE9sACgeAObGRSHhocxLLnhzG8V00WXaVKw7ZDV/jPugQupIksutbE4uG4q1evAhAaGmqyPiQkhLi4ONLS0hg+fHi9/Zw7dw4ALy8v5s2bR2JiolF9REQEH330ESEhIS0jXCAQdBjcne14bkovRvUPYOMvydyoDtFlFSh57/vT3N/dm7lju+HlJkJ0LY3FTUihUADg4uJisl5fXlLS8F7n+fn5AGzbtg1fX18+++wz7r//fvLy8lizZg27du3i+eefZ/fu3dja2pql0Zz90vV4e5t+PdaAtWoTusxD6DKfxrR5e7swrF8APx9J49voSyjL1QD8npzL+bQC5oyLYPqoLshtZA3209K6LEVb6LK4CbUUWq0WgKqqKt5//30GDBgA6EJ6K1as4OrVq5w/f55ffvmFyZMnm9V3fr4CjUbb5Pbe3i7k5jZsmpbCWrUJXeYhdJmPOdqG3+dDzyA3th66wtHzWYBuLboNe5KIPn6dJ8d3o3eYV5vrakuaq0sqlZh14W7xe0L6BIL6Rjr68vpGSnr09d7e3gYD0iORSIiKigLg7Nmzd6VXIBDcG7g52/GnyT1Z+ORAAr1rflSzC5S8//0Z1vxwjvwiMdH1brG4CYWHhwNw7do1k/XXr18HICwsrMF+9PX1mZV+wmt5ufjQCASCphMR5M6bTw/iiXHdcLCrCcP9npLLG58f56ej11D9//buPKCm/P8f+LO06KJCG0XZzkUplRKiaRlLtpms02LJd8aM3Rgfu5nhgzGGGWWGjAmphE/CWJqxDV1LGlFENEkqmhTtu87vj3736rqn5W7d8Hr8xftsr/s+p/O6533e9/2upo5PslJ5Eho4cCCA2t/4vNmDrbi4GPHx8dDR0YGNjU2D++nfvz94PB6ysrI4u3M/fPgQAGBmZqagyAkh74tW6urwGNAFGz8bhCFWJqLyyuoaHL38CGt/i8WdR3kqjPDtpfIk1LVrVzg7OyMrKwthYWFiywIDA1FaWopx48aBx3s9e2JqaipSU1PF1tXR0cGECRNQUVGBn376SfSOCAAePHiAqKgoaGhoYOTIkcr9QISQd5ZeGy3MGtMXK3zt0MWoThPdyzL8eDgBO47eQW5BmQojfPuosXXv1iry5rA9PXr0QEJCAmJjY2FhYYGIiAixYXv4fD6A2uRSV3FxMXx9fXH//n3Y2NjAzs4Oubm5OHv2LMrLy7Fy5UpMnz5d6vioY4LyUVzSobikp+jYXtXU4K9bT3H08iOUVVSLyrU01DF6sAVGOnaFpkbj3/Nbap01V8eEFpGEAODZs2cICAgQDWBqaGgIDw8PzgFM60tCAFBSUoLdu3cjOjoaWVlZaN26NaytreHv7w9nZ2eZYqMkpHwUl3QoLukpK7aCkkr8769/cOVOtli5UXsdeHswsO7RcC+6llpn710SaskoCSkfxSUdikt6yo7tn8wChP75AE9yisXKbXsZ4BP3XjDQ11FJXLJ6b7poE0LIu6CnmR7WznCAz4cMdLRf/wTzVkouVu2Jxe9X0lBV/UqFEbZMlIQIIURB1NXV4G5vhk2fOcG5XydReVV1DaJi0rBmzw0kpuaqMMKWh5IQIYQomG4bLfiP7oOVfvboavy6aSonvww/HUlEYGQicvOpFx1ASYgQQpSmp6ke1k53gO9wBjyOJroTV9JQWfV+N9FREiKEECVSV1eDm50ZNs52wlBr8Sa6YzFpmLflIhL+eX+b6CgJEUJIM9DlaWGmZx+s8rOHufHr4cWe5ZVg+/8SEfC/RDx/D5voKAkRQkgz6mGqhzXTB8BvOIM2rV830d3+Jxer98TiuOD9aqKjJEQIIc1MXV0NrnZm2PiZE4YPfD3RZlV1DY4L0rDmt1jcfk+a6CgJEUKIirTjaWH+5P5YNc0e5iavm+ie55cj4H+J2H4kATnveBMdJSFCCFGxHp31sGbaAEwbwRdroktIzcPqX2NxLObRO9tER0mIEEJaAHV1NXxga4qNnzlhmE1nqP3/8upXNThx5TFW74nF7ZR3r4mOkhAhhLQg7XhamDGqN1ZNGwCLOk10uQXlCIhMxE9HEpDzUnLOtLcVJSFCCGmBunfWxeppAzBtpHgTXWJqHlbvuYGoy49Q8Q400Wk0vkrzyM7Oxvbt20VTORgZGcHd3Z1zKof6+Pn54caNG/UuT0xMhLa2tqJCJoQQpVJXV8MH/U0xgG+EyEupuHz7KVjUNtH9fvUxriVl4xP3XujfywBqamqN7q8lahFJ6M1J7bp3747ExESEhIQgJiYGBw8eFJvUrjHz5s3jLG/VqhVnOSGEtGRtdTQxfWRvDLPpjNA/HyDtWe0UC7kF5Qg8egfWPTriE49eMG7Pa2RPLU+LSELffvst8vLysHr1avj5+YnKN23ahH379uHHH3/EunXrmry/+fPnKyNMQghRqW6ddLFq2gDEJDxF5KVHKC6rAlDbRHfv8QuMHGiO0YPMoa359nzhVvk7oSdPnkAgEMDU1BQ+Pj5iy+bPnw8ej4cTJ06gtPTdeRFHCCGyUldTg0v/2l50H9ia1ulFx+Lk1cdY/Wss4h8+x9syX6nKk1BsbCwAwNnZGerq4uG0bdsWdnZ2KCsrQ0JCQpP3efr0aezevRt79+7FpUuXUFlZqdCYCSFE1drqaGLaCD5WTx+Abp10ReV5heXYcfQOfjqSiH/fgl50Km+Oe/ToEQDAwsKCc7m5uTkEAgHS0tIwaNCgJu1z8eLFYv/v2LEj1q5di5EjR8oVKyGEtDS1TXT2ECQ+w//+ShU10d15lIc1e15g5MCuGD3IosU20ak8CRUX187H3q5dO87lwvKiosbnOnd3d4e/vz/69u0LfX19ZGVl4dixYwgODsbixYvB4/EwbNgwqWOUZr50IUND7s/TErTU2Cgu6VBc0mupsSkirgkeuhg+uBsOnLmP6GuPwbLCJrp0xN7PwafjreBk1UmqXnTNUV8qT0KKNGPGDLH/d+/eHV9++SWMjIywfv16bNu2TaYklJdXjJqaprevGhq2w/PnjSdNVWipsVFc0qG4pNdSY1N0XJOGdYcDY4DQPx/i0dNCAMDzl2XYuC8OVt06wOdDBsYdGu9FJ2tc6upqUn1xV/k7obZta4Ot70lHWF7fk1JTTJo0CRoaGrh//77oyYsQQt5VFia6WOlnjxmjeqOtjqao/G7aC6z5LRaRl1JRUdkyfuiq8iTUvXt3AMDjx485l6enpwMAunXrJvMxtLW10aZNGwBAWdm7PSItIYQAtb3ohtl0xsbPnOBqJ96L7tS1dKzacx03H+SovBedypPQwIEDAQACgQA1NTViy4qLixEfHw8dHR3Y2NjIfIxHjx6hoKAAbdq0kepHr4QQ8rZrq6MJv+F8rJ3hgB6dX/eie1FYgZ+j7mLb4QRkv1BdLzqVJ6GuXbvC2dkZWVlZCAsLE1sWGBiI0tJSjBs3Djze6zbM1NRUpKamiq2bkZGB/Px8if2/ePECK1euBACMHj0aGhrv1GswQghpEnOTdljhZ4+ZnuJNdElpL7Bmj+qa6NRYVT+LQXLYnh49eiAhIQGxsbGwsLBARESE2BMMn88HADx48EBUdvToUXz99dewt7dHly5doKenh2fPnuHSpUsoKiqClZUV9u7dC11dXYnjN4Y6JigfxSUdikt6LTU2VcRVUl6FqMuPcPFWFupmgA662pjq1gv2fEMYGek2S8eEFvFY0LVrV0RGRiIgIAAxMTG4fPkyDA0NMW3atCYPYGppaYnRo0cjKSlJ1AGhTZs2YBgGo0aNwpQpU6ClpdUMn4YQQlq2Nq014Tucj6HWnRF69gFSs2p70b0orMAvx+7C0qI95k2xhXYzjInaIp6EWjp6ElI+iks6FJf0Wmpsqo6rhmVx9U42jvz1D4pKq0TlGq3U8B9vO/Q0bdosBkJvXRdtQgghqqOupgZn607Y9JkT3O3MIPwta/UrFjcf5Cj9+C2iOY4QQohq8Vprwmc4g6E2nXBckIbyqhoMte6s9ONSEiKEECLS1bgd5k+wbrZmQmqOI4QQojKUhAghhKgMJSFCCCEqQ0mIEEKIylASIoQQojKUhAghhKgMddFuAnV16ceukGWb5tJSY6O4pENxSa+lxvYuxSXtNjRsDyGEEJWh5jhCCCEqQ0mIEEKIylASIoQQojKUhAghhKgMJSFCCCEqQ0mIEEKIylASIoQQojKUhAghhKgMJSFCCCEqQ0mIEEKIytDYcQqSnZ2N7du3IyYmBvn5+TAyMoK7uzvmzZsHPT09pR335cuXOHfuHP766y88fPgQ//77LzQ1NcEwDLy8vDBhwgSoq7/+rpGZmQl3d/d69+fp6Ykff/xRIbG5ubkhKyuLc5mBgQGuXLkiUR4fH4+dO3ciISEB5eXlMDc3x4QJE+Dn54dWrVopJK6jR49ixYoVDa6jrq6O+/fvA1B8nUVHRyMuLg73799HcnIySkpKMHbsWPzwww/1biNLvVy8eBHBwcG4d+8eampq0LNnT3h7e+Pjjz9WSGyPHz/Gn3/+CYFAgPT0dOTl5UFXVxc2NjaYPn06nJycJLZprO6/+eYbfPLJJ3LFJc/5ioqKQlhYGFJTU6Guro6+ffvC398frq6unOtLE9fy5csRFRVVb1wA4OTkhP3794v+L0t9SXtPEGqua+xNlIQU4MmTJ5g6dSry8vLg7u6O7t27IzExESEhIYiJicHBgwfRvn17pRw7Ojoa33zzDQwNDTFw4EB07twZubm5OHv2LFavXo2YmBhs374damrigwr27t0bHh4eEvvr1auXQuNr164dpk+fLlHO4/Ekys6dO4cFCxZAW1sbo0aNgp6eHi5evIhNmzYhPj4eAQEBCompT58+mDdvHueyv//+G9evX8ewYcMklimqznbu3Ink5GTweDyYmJjg0aNHDa4vS72EhoZi/fr10NfXx7hx46CpqYk//vgDy5cvx8OHD7Fs2TK5Y9u+fTtOnz6Nnj17wsXFBXp6ekhLS8OFCxdw4cIFrFq1CtOmTePc1t3dHX369JEot7KykjsuIWnP1+bNmxEcHAwTExNMmjQJVVVVOH36ND7//HOsWbMGvr6+csXl4eEBU1NTzmXHjx9HRkYG53UHSFdfstwTmvMak8ASufn7+7MMw7AhISFi5Rs3bmQZhmHXrFmjtGNfvXqVPX/+PPvq1Sux8pycHNbFxYVlGIaNjo4WlWdkZLAMw7DLli1TWkxCrq6urKura5PWLSoqYp2cnFhLS0s2MTFRVF5eXs5OmTKFZRiGPXnypLJCFZk8eTLLMAx77tw5UZmi6+zatWtsWloaW1NTw16/fp1lGIZdsmQJ57qy1EtGRgZrZWXFOjo6shkZGaLy/Px81sPDg2UYho2Pj5c7tsjISDYpKUmiPDY2lrW0tGQtLS3Zf//9V2IbhmHYyMhI7sqphzRxyXK+bt68yTIMw3p4eLD5+fli+3J0dGStrKzE6lKWuOpTUFDAWltbs5aWlmxeXp7YMlnqS9p7QnNfY2+id0JyevLkCQQCAUxNTeHj4yO2bP78+eDxeDhx4gRKS0uVcvxBgwbBzc1N4vHa0NAQU6dOBQDcuHFDKcdWpOjoaLx48QKjR49Gv379ROXa2tpYuHAhAODgwYNKjeHBgwe4ffs2jI2N8cEHHyjtOE5OTrCwsJB4OuUiS71ERkaisrISPj4+MDMzE5Xr6elh9uzZAICIiAi5Y/Py8kLfvn0lyh0dHeHo6IiqqircunWr0f00hTRxyUJYH59//rlY87mZmRm8vb1RWVmJo0ePKiWu48ePo7y8HMOHD0eHDh1k3o+QtPeE5r7G3kTNcXKKjY0FADg7O0uc9LZt28LOzg4CgQAJCQkYNGhQs8amoVF7ernac3NychAREYH8/Hzo6+ujf//+6N27t8JjqKysxPHjx/Hs2TPo6OiAz+fDwcFBIqbr168DAIYOHSqxDwcHB+jo6ODWrVuorKyElpaWwuMEgMOHDwMAJk6cqNI6q0uWemloG2Fzj3AdZWno2gOA+/fvY9++faisrISRkRGcnJxgYmKi0BikOV+N1dkvv/yC69evY8GCBQqNEXh93U2ePLnedRRVX1znRdXXGCUhOQnbgC0sLDiXm5ubQyAQIC0trVmTUHV1NY4fPw6A+0K5cuWKRMcAR0dHbN68GZ07d1ZYHM+fP8d//vMfsTIzMzNs2rQJjo6OorK0tDQA3PWooaEBMzMzpKSkICMjAz169FBYfELl5eU4ceIEWrVqhUmTJnGu01x1Vpcs9dLQNkZGRuDxeMjOzkZZWRl0dHQUHnNWVhauXbsGHR0dODg4cK4TEhIi9v9WrVph4sSJWLVqFbS1tRUSR1PPV2lpKf7991/weDwYGRlJ7Mfc3BxAbUcMRbt16xYePnwICwsLzo4cQoqor/ruCaq+xigJyam4uBhA7Qt4LsLyoqKiZosJALZu3YqHDx/CxcVF7ILT0dHBnDlz4OHhgS5dugCobYYKDAxEbGwsZsyYgWPHjnF2HJCWl5cX7O3t0atXL7Rp0wYZGRkIDQ3F4cOH8emnn+LQoUOib6aN1WPbtm0BAIWFhXLHxeXMmTMoLCzEBx98gE6dOokta846e5Ms9dKUbUpLS1FUVKTwJFRZWYmvvvoKlZWVWLp0qUTPUDMzM6xZswZDhgyBiYkJioqKcPPmTWzbtg2HDh1CSUkJtm7dKlcM0p4v4d9mY3/Dyrj2GnsKUmR91XdPUPU1Ru+E3kEhISEIDg5G9+7d8f3334st69ixIxYuXAhLS0vo6upCV1cXDg4OCA4Oho2NDdLT03HkyBGFxDFv3jwMGjQIBgYG0NHRAcMwWLduHWbOnIny8nIEBgYq5DiKcOjQIQDAlClTJJY1Z529zV69eoWlS5ciPj4enp6emDVrlsQ6jo6O8PX1Rbdu3aCjowMjIyOMGjUKISEh0NPTw8mTJ5GcnCxXHG/L+SoqKsKZM2egqalZb5dmRdVXQ/cEVaMkJCfht4T6nnQa+5alaKGhodiwYQN69uyJkJAQ6OvrN2k7DQ0NUTPU33//rcwQRS9H6x6nsXoUfvPS1dVVeDwpKSm4desWTExM4OLi0uTtmqPOZKmXpm6jyGtSmICio6MxatQobNmyRaqX9Z06dRK9S4iLi1NYXHXVd74aa60Qliv62jtx4gTKyspk6pAgTX01dk9Q9TVGSUhO3bt3B1B/e3F6ejoAoFu3bkqPZd++fVi/fj0YhkFISAgMDQ2l2l74WyZl9eQTEv7B1T2OsH646rG6uhqZmZnQ0NAQNa8okvApqL4OCQ1Rdp3JUi8NbZOTk4PS0lKYmJgorCmuqqoKX375JU6dOoUxY8Zg69atohfg0hBeF2VlZQqJiwvX+eLxeDA2NkZpaSlycnIkthH+Ddf33ldWwqY4rqfvpmhKfTXlnqDqa4ySkJwGDhwIABAIBKipqRFbVlxcjPj4eOjo6MDGxkapcezevRubNm1Cnz59sH//fnTs2FHqfSQkJACAUm70dd2+fVviOMKXsjExMRLrx8XFoaysDLa2tgrvGVdRUSHqkDBx4kSpt1d2nclSLw1tc/nyZbF15FVZWYmFCxciOjoaH330EbZs2SLzyBaJiYkAINblV9HqO1/NWWfCOJKTk2FhYSG6h0irsfpq6j1B1dcYJSE5de3aFc7OzsjKykJYWJjYssDAQJSWlmLcuHFKeWkt9PPPP2Pr1q2wtLTEvn37Gny0T0pKkkiWAHDt2jXs27cPADBu3Di5Y0pNTeV8OsjMzMT69esljjNy5Ei0b98ep06dwp07d0TlFRUV2L59OwBwDucirzNnzqCgoADDhg2T6JAg1Fx1xkWWevHy8oKWlhbCwsKQmZkpKi8oKEBQUBCA102i8qisrMS8efNw/vx5TJw4EZs2beIcDqauup9BqKamBkFBQbh16xbat29f76gBTSXL+RLWx65du1BQUCAqz8zMRHh4OLS0tODl5SVXXHU19A6yLlnrS5p7gqqvMTWWZdkmrUnq9eawPT169EBCQgJiY2NhYWGBiIgIpQ3bExUVheXLl6NVq1bw9fXlbIM1NTUV/QH5+fnh8ePHsLW1Ff3O4MGDB6I+/QsXLsScOXPkjiswMBDBwcFwcHBA586dRb3j/vrrL1RUVMDFxQU7duwQ+3ZVd+gQT09P6Onp4cKFC0hLS8OIESM4hx+Sl7e3N27evImdO3fCzc2Ncx1F19m5c+dw7tw5ALVd2AUCAbp06YIBAwYAqG0yqjvkiSz1cuDAAfz3v/+Fvr4+PD09RUOqZGdnw9/fv94hVaSJbcWKFTh69Cjat28Pb29vznPj6Ogo9k2fz+eDYRjw+XwYGxujqKhI1E1ZR0cHO3bsgLOzs1xxyXq+vvvuO+zduxcmJiYYMWKEaNie/Pz8eoftkfZcArUtJEOHDkV1dTUuXbrUYIKQpb6kvScIP0dzXWNvoiSkIM+ePUNAQIBoAFNDQ0N4eHgofQDTwMBA7Nixo8F1HB0dceDAAQDAkSNHcO7cOaSkpODly5eoqqqCgYEB+vfvD19fX9Efj7xu3LiBiIgI3Lt3D7m5uSgrK0O7du3Qp08fjB8/HuPHj+e8ad28eRO7du3C7du3UVFRoZQBTIVSU1Ph6ekJExMTXLhwod79K7rOGjtnpqamuHDhgliZLPVy4cIFBAcHIykpCSzLokePHvD19W1wcElpYvPz82t0NI558+Zh/vz5ov9v3rwZd+7cwePHj1FQUAB1dXV06tQJgwcPxsyZM+tt1pQmLnnO19GjR0UDmKqpqcHS0hKzZs2qdwBTWc5leHg4vv32W4wePRrbtm2rd1tAtvqS9p4g1FzX2JsoCRFCCFEZeidECCFEZSgJEUIIURlKQoQQQlSGkhAhhBCVoSRECCFEZSgJEUIIURlKQoQQTiUlJRg9ejRcXFzw9OlTVYdD3lGUhMh7IzY2Fnw+v0VNIdFUy5cvB5/PFxsipT5+fn7g8/lyH3PFihXIzc1FcHCw0ibtk8bRo0fB5/M5p9kmby9KQkRqfD4ffD4frq6uqKio4FzHzc0NfD4f1dXVzRzd+yMzM7PJSVXaBBwUFISYmBjs3r1bKTPZcnmbvyQQ2dHMqkRmT58+xf79+/HZZ5+pOhRSx+bNm+WaDqG0tBTV1dX49ddflT76uzQ+/PBD2NjYcE7BTd5elISITPT09KCmpobdu3dj4sSJUk/KRZRH3qYzHo+HuXPnKigaxWnXrl2zTQ5Jmg81xxGZtG7dGl988QWKiorw888/S7Xt6dOn4ePjA3t7e1hbW2Ps2LEICgpCZWWlxLpubm5wc3NDSUkJNm7cCBcXF1hbW2P8+PGi0Yurq6uxc+dODB8+HP369YOHhwdCQ0MbjOHWrVuYMWMG7O3tYWtri1mzZnEOmx8YGAg+n4/Y2Fj8/vvvmDRpEmxtbcVG3C4rK0NQUBDGjx+P/v37w9bWFlOmTMHJkyelqhcAuHr1Kry9vdENHPFLAAALmUlEQVS/f384Ojpizpw5SE1NlWofb74TWr58OaZNmwYA2LFjh6g5Vfi56jp58iT8/PwwYMAA9OvXD6NGjcIvv/zCeW74fD78/Pzw/PlzrFq1CkOHDkWfPn1E72zS0tLwww8/wMvLC05OTrCysoKrqyvWrFmD7OxssX01JcaG3gndvXsX8+fPx6BBg0TH+eabbzgnqav7fi0iIgJjx45Fv379MHjwYKxZs4ZzttDk5GR8+eWXcHNzg5WVFZycnPDxxx9jw4YNqKqqavB8kIbRkxCRmY+PD8LCwnDo0CH4+fk1aebJbdu2ISgoCO3bt8eYMWPA4/EQExODbdu2QSAQ4LfffpOYuK6qqgr+/v7Iz8+Hu7s7qqqqcPLkScyfPx/BwcEIDw9HQkIChg0bBi0tLURHR2P9+vXo0KEDPD09JWJISEhAUFAQBg8eDB8fH6Snp+Ps2bOIi4tDcHAw5yjLe/fuxZUrV+Dq6oqBAweKblSFhYWYPn067t27B0tLS0yYMAE1NTUQCARYsmQJUlJSsHjx4ibVZ3R0NBYvXgxNTU14enrC0NAQN2/exNSpU+XqaODh4QGgdoh/R0dHODo6ipaZmpqK/i2cmsHExATDhw+Hrq4ubt++je3bt+PatWvYu3evxIyp+fn5mDJlCng8HoYPHw41NTXR5Glnz55FREQEBg4cCDs7O2hqaiIlJQVHjhzBxYsXERkZCWNjY6li5HLx4kXRSN0jRoxA586dkZSUhIMHD+L8+fMIDw/nHG16y5YtEAgEcHV1xZAhQxAbG4vDhw8jPT0dISEhovWSk5MxefJkqKmpwc3NDWZmZiguLsaTJ09w8OBBLFq0CJqamo2fCMKNJURKDMOwQ4cOZVmWZc+cOcMyDMPOnTtXbB1XV1eWYRi2qqpKVBYfH88yDMO6uLiwOTk5ovKqqip29uzZLMMw7M6dOzn3M3v2bLaiokJUHhcXxzIMwzo4OLBeXl5sQUGBaNmTJ09YS0tLdvz48WL7un79OsswDMswDHvgwAGxZWfPnmUZhmE//PBD9tWrV6LygIAAlmEY1sbGhk1KSpKoi2XLlrEMw7C7d+8WKy8vL2f9/f1ZPp/P3rt3j7si6yguLmYdHR3Zvn37somJiWLLNmzYIIo7IyOj0X35+vqyDMNwfvaAgADObSIjI0XnsaysTGyZsA727dsnVi6MaenSpWLnWSg7O1vsnAnFxMSwvXv3ZteuXStTjJGRkaIyYb317t2bjYuLE1s/KCiIZRiGnTlzpli58Jy5uLiwWVlZovKqqirW29ubZRiGTUhIEJVv2rSJZRiGPXv2rERM+fn5YtcLkR41xxG5jBw5Era2tjh79iz+/vvvBteNjIwEAHzxxRdic91raGhg2bJlUFdXx5EjRzi3XblypdgT0oABA2BmZoaCggJ89dVX0NXVFS3r0qULbG1tkZKSglevXknsy9zcHN7e3mJlHh4ecHR0RHp6OufnmDx5Mvr27StW9vLlS5w4cQJWVlb49NNPxZZpa2tj6dKlYFkWv//+e31VInL+/Hnk5+djzJgx6Nevn9iy+fPnK/1dSEhICDQ0NLBx40a0bt1abNmcOXOgr6/P+Tk0NTWxbNkyiSckADA2Nuacjt3Z2Rk9e/aEQCCQO25hvXl6eko8wfr7+8PU1BRXrlzh/J3T3Llzxd6faWhoiCZ6E06dXdeb9QLUvhttbDZZ0jBqjiNyW7ZsGaZOnYrvv/8ehw8frne9e/fuAeCee75bt24wMTFBZmYmioqKxG66urq66Nq1q8Q2RkZGyMzMhJWVlcQyY2NjVFdXIzc3V9TkI2Rvb89543B0dMSNGzdw7949seYgALC2tpZY/86dO3j16hXU1NQ4uxULu6c/evRIYtmbhHXj4OAgsUw4GWBjE8jJqqysDMnJyWjfvj3279/PuY6WlhbnuylTU1NR89ubWJbFiRMnEBUVheTkZBQWFop9KVBEE1ZD15SGhgYcHByQlZWFe/fuSXTY4LpuhFO8153i29PTEyEhIZg7dy5GjBiBwYMHw87OjvOaJNKjJETkZmtrixEjRuCPP/7A6dOnOd/DABC9R6n7FFSXoaEhnj59isLCQrEkVN9TgPDbN9dy4TKul8YGBgac+xOWFxcXN2mb/Px8ALXJiKtTg1BJSUm9y4SEddNYbMpQWFgIlmXx4sWLRmfkfFN95xIANm3ahP3798PQ0BDOzs4wNjYWPU1ERUUhKytLrriBpl1Tdderi+u6Ec4gWlNTIyqztrZGWFgYdu3ahT/++APHjx8HUPvFad68eRgzZox8H+I9R0mIKMSSJUtw4cIFbN26VfSS+U3CP/rc3FzOb5HPnz8XW09ZcnNzGyxv27atxDKuqciFcc6YMQMrVqyQK6a6ddNQbMog/Lx9+/ZFVFSUVNty1QsA5OXl4cCBA2AYBgcPHpSoU1l6DnIR1pvw2nmToq4pW1tbUQ/Ou3fvIiYmBqGhoViyZAk6dOiAwYMHy7X/9xk1ZhKFMDc3xyeffILMzMx6u0f36dMHACS6BQNAeno6srOzYWZmJvZ+Rxni4+PFvukKCZu73nz3Ux9ra2uoq6s3+i6sKYTHjIuLk1hWVFSE+/fvy7V/4Td8rndkbdq0Qa9evZCSkiJ6upNXRkYGampqMGTIEIkElJ2dzTn8UEMx1kd4TXE1VVZXV4vOTVPPaWO0tLRgZ2eHhQsXYtWqVQBq30sR2VESIgozd+5c6OrqYteuXZxNUBMmTAAA7Ny5Ey9evBCVv3r1Cps3b0ZNTQ0mTpyo9DgfP36M8PBwsbJz587hxo0bMDc35+yizaVjx44YO3Ys7t69i59//pnz5vnkyRNkZGQ0ui93d3fo6enh5MmTEk17gYGBnM1J0tDX1wcAPHv2jHP5jBkzUFVVhZUrV6KwsFBieUFBAZKSkpp8PGG36ps3b4rVS0lJCVavXs05nFNjMXLx8PCAvr4+Tp06hdu3b4st279/PzIzMzF48GC5fsAbHx+P8vJyifK8vDwA3B0WSNNRcxxRGH19fcyePRtbtmzhXG5nZ4f/+7//w549ezBmzBiMGDECOjo6iImJwcOHD2Fvb49Zs2YpPc6hQ4fiu+++w+XLl9G7d2/R74S0tbWxceNGqXo7rV27Funp6QgICMCJEydgZ2cHAwMD5OTkIDU1FXfu3MG2bds4f6dSV5s2bbBu3TosXrwYPj4+Yr8TSklJgYODA+dTUlN169YNxsbGOHXqFDQ0NNC5c2eoqalh/PjxMDU1xcSJE5GUlITw8HB8+OGHcHZ2RqdOnVBQUIDMzEzExcXBy8sL69ata9LxDA0NMXr0aJw6dQofffQRhgwZgqKiIly9ehVaWlro06ePxNNdYzHWV28bNmzAokWL4Ovri5EjR4p+JyQQCGBoaNjkmOuzZ88eXL9+XdQjk8fj4Z9//sHly5ehp6eHKVOmyLX/9x0lIaJQ06ZNQ3h4eL0vnZcuXYq+ffsiNDQUx44dQ3V1Nbp27YpFixbB39+fs0uvotnY2GDu3LnYvn07QkNDwbIsnJycsGjRIs5ecA1p27YtDhw4gMOHD+PkyZP4888/UVFRAQMDA5ibm2PFihVNfl8wcuRItGvXDjt27MCZM2egpaWFAQMGICIiAr/++qtcSahVq1bYsWMHtm7diujoaJSUlIBlWdjb24tu8F9//TWGDRuGiIgIXL16FUVFRdDT00OnTp0wa9YsjBs3TqpjbtiwAV26dMHp06cRFhaGDh06wM3NDQsWLMCCBQtkipGLh4cHwsPDERQUBIFAgOLiYhgYGGDq1KmYM2eORO9IaXl7e0NPTw8JCQmiJztjY2N4e3tj5syZjf6YljRMjWVZVtVBEEIIeT/ROyFCCCEqQ0mIEEKIylASIoQQojKUhAghhKgMJSFCCCEqQ0mIEEKIylASIoQQojKUhAghhKgMJSFCCCEqQ0mIEEKIyvw/2uPbqZKRsNgAAAAASUVORK5CYII=\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "611vwaslx1Z2",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 293
        },
        "outputId": "afb0503c-c346-46a7-af78-8ba34bd03687"
      },
      "source": [
        "print('La matrice d\\'évaluation après complétion')\n",
        "print('')\n",
        "birdi.all_rating_prediction()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "La matrice d'évaluation après complétion\n",
            "\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[3.19701837, 3.45006603, 3.10955555, ..., 3.28054947, 3.34017579,\n",
              "        3.34599149],\n",
              "       [4.21078539, 3.57749846, 3.17084016, ..., 3.68590512, 3.69492168,\n",
              "        3.65016211],\n",
              "       [3.34471953, 2.91499348, 2.65790332, ..., 3.11992054, 3.11319444,\n",
              "        3.06183409],\n",
              "       ...,\n",
              "       [4.52376836, 3.72628327, 3.32523694, ..., 3.79895614, 3.79215072,\n",
              "        3.77021019],\n",
              "       [4.31012248, 3.78118243, 3.42344439, ..., 3.92126548, 3.92540358,\n",
              "        3.87776333],\n",
              "       [3.67246363, 3.18796169, 2.98273505, ..., 3.28348045, 3.29884059,\n",
              "        3.26865994]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 18
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qCm1ScDHXS3N",
        "colab_type": "text"
      },
      "source": [
        "Comme nous nous y attendions, avec l'algorithme de descente de gradient stochastique, les paramètres de notre modèle s'affinent au fil du temps. Nous avons choisi au hasard au début ces paramètres. L'une des premières observations que nous avons faites est l'influence du nombre de facteurs latents sur notre modèle. Avec des facteurs latents de tailles différentes, on a constaté que l'erreur de prédiction variait considérablement."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "A5OsSgNGXKQ1",
        "colab_type": "text"
      },
      "source": [
        "Nous avons trouvé un score RMSE égal à $\\textbf{0.88}$. À titre indicatif, celui de Netflix lors du challenge de 2007 était de l'ordre de $0.95$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cxYKmOMk9TIj",
        "colab_type": "text"
      },
      "source": [
        "#Completion matricielle par optimisation convexe"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yeSGHCZyiMzR",
        "colab_type": "text"
      },
      "source": [
        "Nous allons utiliser la bibliothèque **fancyimpute** pour la complétion matricielle. La bibliothèque contient des algorithmes de completion matricielle par optimisation convexe. Cette partie est différente de la factorisation matricielle. Voir **Matrix Completion Via Convex Optimization** de **E Candès** ou le pdf Recommender_filtrage_collaboratif dans le dossier Recommender_System"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0ucWEmrKAfA-",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import random\n",
        "import math\n",
        "import itertools\n",
        "\n",
        "import numpy as np\n",
        "from cvxpy import *"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BvO0NAtsAtKB",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 992
        },
        "outputId": "42903008-1517-4951-ae68-2a42276dc021"
      },
      "source": [
        "pip install fancyimpute"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Requirement already satisfied: fancyimpute in /usr/local/lib/python3.6/dist-packages (0.4.3)\n",
            "Requirement already satisfied: tensorflow in /usr/local/lib/python3.6/dist-packages (from fancyimpute) (2.2.0)\n",
            "Requirement already satisfied: keras>=2.0.0 in /usr/local/lib/python3.6/dist-packages (from fancyimpute) (2.3.1)\n",
            "Requirement already satisfied: six in /usr/local/lib/python3.6/dist-packages (from fancyimpute) (1.12.0)\n",
            "Requirement already satisfied: scipy in /usr/local/lib/python3.6/dist-packages (from fancyimpute) (1.4.1)\n",
            "Requirement already satisfied: scikit-learn>=0.19.1 in /usr/local/lib/python3.6/dist-packages (from fancyimpute) (0.22.2.post1)\n",
            "Requirement already satisfied: knnimpute in /usr/local/lib/python3.6/dist-packages (from fancyimpute) (0.1.0)\n",
            "Requirement already satisfied: cvxpy>=1.0.6 in /usr/local/lib/python3.6/dist-packages (from fancyimpute) (1.0.31)\n",
            "Requirement already satisfied: np-utils in /usr/local/lib/python3.6/dist-packages (from fancyimpute) (0.5.12.1)\n",
            "Requirement already satisfied: numpy>=1.10 in /usr/local/lib/python3.6/dist-packages (from fancyimpute) (1.18.4)\n",
            "Requirement already satisfied: tensorflow-estimator<2.3.0,>=2.2.0 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (2.2.0)\n",
            "Requirement already satisfied: tensorboard<2.3.0,>=2.2.0 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (2.2.1)\n",
            "Requirement already satisfied: keras-preprocessing>=1.1.0 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (1.1.2)\n",
            "Requirement already satisfied: opt-einsum>=2.3.2 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (3.2.1)\n",
            "Requirement already satisfied: gast==0.3.3 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (0.3.3)\n",
            "Requirement already satisfied: wrapt>=1.11.1 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (1.12.1)\n",
            "Requirement already satisfied: absl-py>=0.7.0 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (0.9.0)\n",
            "Requirement already satisfied: google-pasta>=0.1.8 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (0.2.0)\n",
            "Requirement already satisfied: astunparse==1.6.3 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (1.6.3)\n",
            "Requirement already satisfied: h5py<2.11.0,>=2.10.0 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (2.10.0)\n",
            "Requirement already satisfied: wheel>=0.26; python_version >= \"3\" in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (0.34.2)\n",
            "Requirement already satisfied: grpcio>=1.8.6 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (1.29.0)\n",
            "Requirement already satisfied: termcolor>=1.1.0 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (1.1.0)\n",
            "Requirement already satisfied: protobuf>=3.8.0 in /usr/local/lib/python3.6/dist-packages (from tensorflow->fancyimpute) (3.10.0)\n",
            "Requirement already satisfied: pyyaml in /usr/local/lib/python3.6/dist-packages (from keras>=2.0.0->fancyimpute) (3.13)\n",
            "Requirement already satisfied: keras-applications>=1.0.6 in /usr/local/lib/python3.6/dist-packages (from keras>=2.0.0->fancyimpute) (1.0.8)\n",
            "Requirement already satisfied: joblib>=0.11 in /usr/local/lib/python3.6/dist-packages (from scikit-learn>=0.19.1->fancyimpute) (0.15.1)\n",
            "Requirement already satisfied: osqp>=0.4.1 in /usr/local/lib/python3.6/dist-packages (from cvxpy>=1.0.6->fancyimpute) (0.6.1)\n",
            "Requirement already satisfied: multiprocess in /usr/local/lib/python3.6/dist-packages (from cvxpy>=1.0.6->fancyimpute) (0.70.9)\n",
            "Requirement already satisfied: scs>=1.1.3 in /usr/local/lib/python3.6/dist-packages (from cvxpy>=1.0.6->fancyimpute) (2.1.2)\n",
            "Requirement already satisfied: ecos>=2 in /usr/local/lib/python3.6/dist-packages (from cvxpy>=1.0.6->fancyimpute) (2.0.7.post1)\n",
            "Requirement already satisfied: future>=0.16 in /usr/local/lib/python3.6/dist-packages (from np-utils->fancyimpute) (0.16.0)\n",
            "Requirement already satisfied: tensorboard-plugin-wit>=1.6.0 in /usr/local/lib/python3.6/dist-packages (from tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (1.6.0.post3)\n",
            "Requirement already satisfied: google-auth-oauthlib<0.5,>=0.4.1 in /usr/local/lib/python3.6/dist-packages (from tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (0.4.1)\n",
            "Requirement already satisfied: werkzeug>=0.11.15 in /usr/local/lib/python3.6/dist-packages (from tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (1.0.1)\n",
            "Requirement already satisfied: setuptools>=41.0.0 in /usr/local/lib/python3.6/dist-packages (from tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (46.4.0)\n",
            "Requirement already satisfied: google-auth<2,>=1.6.3 in /usr/local/lib/python3.6/dist-packages (from tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (1.7.2)\n",
            "Requirement already satisfied: requests<3,>=2.21.0 in /usr/local/lib/python3.6/dist-packages (from tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (2.23.0)\n",
            "Requirement already satisfied: markdown>=2.6.8 in /usr/local/lib/python3.6/dist-packages (from tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (3.2.2)\n",
            "Requirement already satisfied: dill>=0.3.1 in /usr/local/lib/python3.6/dist-packages (from multiprocess->cvxpy>=1.0.6->fancyimpute) (0.3.1.1)\n",
            "Requirement already satisfied: requests-oauthlib>=0.7.0 in /usr/local/lib/python3.6/dist-packages (from google-auth-oauthlib<0.5,>=0.4.1->tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (1.3.0)\n",
            "Requirement already satisfied: pyasn1-modules>=0.2.1 in /usr/local/lib/python3.6/dist-packages (from google-auth<2,>=1.6.3->tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (0.2.8)\n",
            "Requirement already satisfied: rsa<4.1,>=3.1.4 in /usr/local/lib/python3.6/dist-packages (from google-auth<2,>=1.6.3->tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (4.0)\n",
            "Requirement already satisfied: cachetools<3.2,>=2.0.0 in /usr/local/lib/python3.6/dist-packages (from google-auth<2,>=1.6.3->tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (3.1.1)\n",
            "Requirement already satisfied: chardet<4,>=3.0.2 in /usr/local/lib/python3.6/dist-packages (from requests<3,>=2.21.0->tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (3.0.4)\n",
            "Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.6/dist-packages (from requests<3,>=2.21.0->tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (2020.4.5.1)\n",
            "Requirement already satisfied: idna<3,>=2.5 in /usr/local/lib/python3.6/dist-packages (from requests<3,>=2.21.0->tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (2.9)\n",
            "Requirement already satisfied: urllib3!=1.25.0,!=1.25.1,<1.26,>=1.21.1 in /usr/local/lib/python3.6/dist-packages (from requests<3,>=2.21.0->tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (1.24.3)\n",
            "Requirement already satisfied: importlib-metadata; python_version < \"3.8\" in /usr/local/lib/python3.6/dist-packages (from markdown>=2.6.8->tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (1.6.0)\n",
            "Requirement already satisfied: oauthlib>=3.0.0 in /usr/local/lib/python3.6/dist-packages (from requests-oauthlib>=0.7.0->google-auth-oauthlib<0.5,>=0.4.1->tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (3.1.0)\n",
            "Requirement already satisfied: pyasn1<0.5.0,>=0.4.6 in /usr/local/lib/python3.6/dist-packages (from pyasn1-modules>=0.2.1->google-auth<2,>=1.6.3->tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (0.4.8)\n",
            "Requirement already satisfied: zipp>=0.5 in /usr/local/lib/python3.6/dist-packages (from importlib-metadata; python_version < \"3.8\"->markdown>=2.6.8->tensorboard<2.3.0,>=2.2.0->tensorflow->fancyimpute) (3.1.0)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Pg1Gb0iRbXYc",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 146
        },
        "outputId": "f0cd0313-6403-485d-fe84-93ae8b0f735f"
      },
      "source": [
        "haha = ratings_matrix.astype('float')\n",
        "haha[haha == 0] = 'nan' # or use np.nan\n",
        "haha"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 5.,  3.,  4., ..., nan, nan, nan],\n",
              "       [ 4., nan, nan, ..., nan, nan, nan],\n",
              "       [nan, nan, nan, ..., nan, nan, nan],\n",
              "       ...,\n",
              "       [ 5., nan, nan, ..., nan, nan, nan],\n",
              "       [nan, nan, nan, ..., nan, nan, nan],\n",
              "       [nan,  5., nan, ..., nan, nan, nan]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "r2x2qiw9diaU",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 92
        },
        "outputId": "64c6faea-4cac-4e78-de88-8981863c731e"
      },
      "source": [
        "from fancyimpute import KNN, NuclearNormMinimization, SoftImpute, BiScaler"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "/usr/local/lib/python3.6/dist-packages/sklearn/externals/six.py:31: FutureWarning: The module is deprecated in version 0.21 and will be removed in version 0.23 since we've dropped support for Python 2.7. Please rely on the official version of six (https://pypi.org/project/six/).\n",
            "  \"(https://pypi.org/project/six/).\", FutureWarning)\n",
            "Using TensorFlow backend.\n"
          ],
          "name": "stderr"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bCxeH2eJeLUf",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "10576319-d6f0-4154-b43e-fe5b994066bf"
      },
      "source": [
        "X_incomplete_normalized = BiScaler().fit_transform(haha)\n",
        "X_filled_softimpute = SoftImpute().fit_transform(X_incomplete_normalized)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[BiScaler] Initial log residual value = 10.300311\n",
            "[BiScaler] Iter 1: log residual = 2.109617, log improvement ratio=8.190694\n",
            "[BiScaler] Iter 2: log residual = 2.730659, log improvement ratio=-0.621043\n",
            "[SoftImpute] Max Singular Value of X_init = 47.368426\n",
            "[SoftImpute] Iter 1: observed MAE=0.055487 rank=848\n",
            "[SoftImpute] Iter 2: observed MAE=0.055061 rank=776\n",
            "[SoftImpute] Iter 3: observed MAE=0.054581 rank=726\n",
            "[SoftImpute] Iter 4: observed MAE=0.054117 rank=685\n",
            "[SoftImpute] Iter 5: observed MAE=0.053695 rank=655\n",
            "[SoftImpute] Iter 6: observed MAE=0.053299 rank=628\n",
            "[SoftImpute] Iter 7: observed MAE=0.052937 rank=604\n",
            "[SoftImpute] Iter 8: observed MAE=0.052605 rank=586\n",
            "[SoftImpute] Iter 9: observed MAE=0.052305 rank=568\n",
            "[SoftImpute] Iter 10: observed MAE=0.052021 rank=553\n",
            "[SoftImpute] Iter 11: observed MAE=0.051746 rank=538\n",
            "[SoftImpute] Iter 12: observed MAE=0.051504 rank=527\n",
            "[SoftImpute] Iter 13: observed MAE=0.051291 rank=515\n",
            "[SoftImpute] Iter 14: observed MAE=0.051087 rank=504\n",
            "[SoftImpute] Iter 15: observed MAE=0.050892 rank=495\n",
            "[SoftImpute] Iter 16: observed MAE=0.050700 rank=485\n",
            "[SoftImpute] Iter 17: observed MAE=0.050526 rank=477\n",
            "[SoftImpute] Iter 18: observed MAE=0.050358 rank=470\n",
            "[SoftImpute] Iter 19: observed MAE=0.050211 rank=462\n",
            "[SoftImpute] Iter 20: observed MAE=0.050055 rank=455\n",
            "[SoftImpute] Iter 21: observed MAE=0.049925 rank=448\n",
            "[SoftImpute] Iter 22: observed MAE=0.049796 rank=444\n",
            "[SoftImpute] Iter 23: observed MAE=0.049696 rank=439\n",
            "[SoftImpute] Iter 24: observed MAE=0.049576 rank=432\n",
            "[SoftImpute] Iter 25: observed MAE=0.049466 rank=427\n",
            "[SoftImpute] Iter 26: observed MAE=0.049354 rank=422\n",
            "[SoftImpute] Iter 27: observed MAE=0.049244 rank=416\n",
            "[SoftImpute] Iter 28: observed MAE=0.049151 rank=413\n",
            "[SoftImpute] Iter 29: observed MAE=0.049063 rank=408\n",
            "[SoftImpute] Iter 30: observed MAE=0.048965 rank=403\n",
            "[SoftImpute] Iter 31: observed MAE=0.048876 rank=400\n",
            "[SoftImpute] Iter 32: observed MAE=0.048801 rank=396\n",
            "[SoftImpute] Iter 33: observed MAE=0.048716 rank=391\n",
            "[SoftImpute] Iter 34: observed MAE=0.048640 rank=388\n",
            "[SoftImpute] Iter 35: observed MAE=0.048567 rank=385\n",
            "[SoftImpute] Iter 36: observed MAE=0.048501 rank=382\n",
            "[SoftImpute] Iter 37: observed MAE=0.048431 rank=377\n",
            "[SoftImpute] Iter 38: observed MAE=0.048365 rank=376\n",
            "[SoftImpute] Iter 39: observed MAE=0.048317 rank=374\n",
            "[SoftImpute] Iter 40: observed MAE=0.048249 rank=370\n",
            "[SoftImpute] Iter 41: observed MAE=0.048198 rank=367\n",
            "[SoftImpute] Iter 42: observed MAE=0.048137 rank=365\n",
            "[SoftImpute] Iter 43: observed MAE=0.048076 rank=361\n",
            "[SoftImpute] Iter 44: observed MAE=0.048024 rank=359\n",
            "[SoftImpute] Iter 45: observed MAE=0.047977 rank=357\n",
            "[SoftImpute] Iter 46: observed MAE=0.047930 rank=355\n",
            "[SoftImpute] Iter 47: observed MAE=0.047881 rank=352\n",
            "[SoftImpute] Iter 48: observed MAE=0.047841 rank=351\n",
            "[SoftImpute] Iter 49: observed MAE=0.047805 rank=349\n",
            "[SoftImpute] Iter 50: observed MAE=0.047768 rank=347\n",
            "[SoftImpute] Iter 51: observed MAE=0.047727 rank=344\n",
            "[SoftImpute] Iter 52: observed MAE=0.047687 rank=343\n",
            "[SoftImpute] Iter 53: observed MAE=0.047658 rank=341\n",
            "[SoftImpute] Iter 54: observed MAE=0.047624 rank=340\n",
            "[SoftImpute] Iter 55: observed MAE=0.047586 rank=338\n",
            "[SoftImpute] Iter 56: observed MAE=0.047553 rank=336\n",
            "[SoftImpute] Iter 57: observed MAE=0.047520 rank=334\n",
            "[SoftImpute] Iter 58: observed MAE=0.047478 rank=332\n",
            "[SoftImpute] Iter 59: observed MAE=0.047450 rank=331\n",
            "[SoftImpute] Iter 60: observed MAE=0.047414 rank=329\n",
            "[SoftImpute] Iter 61: observed MAE=0.047389 rank=328\n",
            "[SoftImpute] Iter 62: observed MAE=0.047358 rank=326\n",
            "[SoftImpute] Iter 63: observed MAE=0.047326 rank=325\n",
            "[SoftImpute] Iter 64: observed MAE=0.047301 rank=324\n",
            "[SoftImpute] Iter 65: observed MAE=0.047278 rank=322\n",
            "[SoftImpute] Iter 66: observed MAE=0.047251 rank=321\n",
            "[SoftImpute] Iter 67: observed MAE=0.047229 rank=319\n",
            "[SoftImpute] Iter 68: observed MAE=0.047201 rank=318\n",
            "[SoftImpute] Iter 69: observed MAE=0.047173 rank=316\n",
            "[SoftImpute] Iter 70: observed MAE=0.047147 rank=315\n",
            "[SoftImpute] Iter 71: observed MAE=0.047127 rank=315\n",
            "[SoftImpute] Iter 72: observed MAE=0.047114 rank=314\n",
            "[SoftImpute] Iter 73: observed MAE=0.047099 rank=313\n",
            "[SoftImpute] Iter 74: observed MAE=0.047074 rank=311\n",
            "[SoftImpute] Iter 75: observed MAE=0.047053 rank=311\n",
            "[SoftImpute] Iter 76: observed MAE=0.047034 rank=309\n",
            "[SoftImpute] Iter 77: observed MAE=0.047015 rank=308\n",
            "[SoftImpute] Iter 78: observed MAE=0.046994 rank=306\n",
            "[SoftImpute] Iter 79: observed MAE=0.046969 rank=306\n",
            "[SoftImpute] Iter 80: observed MAE=0.046949 rank=304\n",
            "[SoftImpute] Iter 81: observed MAE=0.046928 rank=303\n",
            "[SoftImpute] Iter 82: observed MAE=0.046911 rank=303\n",
            "[SoftImpute] Iter 83: observed MAE=0.046894 rank=302\n",
            "[SoftImpute] Iter 84: observed MAE=0.046877 rank=301\n",
            "[SoftImpute] Iter 85: observed MAE=0.046859 rank=300\n",
            "[SoftImpute] Iter 86: observed MAE=0.046842 rank=299\n",
            "[SoftImpute] Iter 87: observed MAE=0.046831 rank=298\n",
            "[SoftImpute] Iter 88: observed MAE=0.046814 rank=297\n",
            "[SoftImpute] Iter 89: observed MAE=0.046797 rank=296\n",
            "[SoftImpute] Iter 90: observed MAE=0.046783 rank=295\n",
            "[SoftImpute] Iter 91: observed MAE=0.046768 rank=295\n",
            "[SoftImpute] Iter 92: observed MAE=0.046756 rank=294\n",
            "[SoftImpute] Iter 93: observed MAE=0.046745 rank=294\n",
            "[SoftImpute] Iter 94: observed MAE=0.046734 rank=292\n",
            "[SoftImpute] Iter 95: observed MAE=0.046717 rank=291\n",
            "[SoftImpute] Iter 96: observed MAE=0.046702 rank=291\n",
            "[SoftImpute] Iter 97: observed MAE=0.046687 rank=289\n",
            "[SoftImpute] Iter 98: observed MAE=0.046671 rank=289\n",
            "[SoftImpute] Iter 99: observed MAE=0.046662 rank=289\n",
            "[SoftImpute] Iter 100: observed MAE=0.046656 rank=289\n",
            "[SoftImpute] Stopped after iteration 100 for lambda=0.947369\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9orkOhjNahwe",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 146
        },
        "outputId": "8e925ae9-79bd-4756-dd43-92416d01a312"
      },
      "source": [
        "missing_mask = np.random.rand(*haha.shape) < 0.1\n",
        "missing_mask"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[False, False, False, ..., False, False, False],\n",
              "       [False, False, False, ..., False, False, False],\n",
              "       [False, False, False, ..., False, False, False],\n",
              "       ...,\n",
              "       [False, False, False, ..., False, False, False],\n",
              "       [False, False,  True, ..., False, False,  True],\n",
              "       [False, False, False, ...,  True, False, False]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0CJVw-sab_fC",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "94806200-0bc3-495b-964c-674e7a70ec0d"
      },
      "source": [
        "softImpute_mse = ((X_filled_softimpute[missing_mask] - ratings_matrix[missing_mask]) ** 2).mean()\n",
        "print(\"Matrix Completion MSE: %f\" % softImpute_mse)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Matrix Completion MSE: 0.853624\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}