examples/02_model_collaborative_filtering/als_deep_dive.ipynb

{
    "cells": [
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "<i>Copyright (c) Recommenders contributors.</i>\n",
                "\n",
                "<i>Licensed under the MIT License.</i>"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "# Spark Collaborative Filtering (ALS) Deep Dive"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "Spark MLlib provides a collaborative filtering algorithm that can be used for training a matrix factorization model, which predicts explicit or implicit ratings of users on items for recommendations.\n",
                "\n",
                "This notebook presents a deep dive into the Spark collaborative filtering algorithm."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## 1 Matrix factorization algorithm\n",
                "\n",
                "### 1.1 Matrix factorization for collaborative filtering problem\n",
                "\n",
                "Matrix factorization is a common technique used in recommendation tasks. Basically, a matrix factorization algorithm tries to find latent factors that represent intrinsic user and item attributes in a lower dimension. That is,\n",
                "\n",
                "$$\\hat r_{u,i} = q_{i}^{T}p_{u}$$\n",
                "\n",
                "where $\\hat r_{u,i}$ is the predicted ratings for user $u$ and item $i$, and $q_{i}^{T}$ and $p_{u}$ are latent factors for item and user, respectively. The challenge to the matrix factorization problem is to find $q_{i}^{T}$ and $p_{u}$. This is achieved by methods such as matrix decomposition. A learning approach is therefore developed to converge the decomposition results close to the observed ratings as much as possible. Furthermore, to avoid overfitting issue, the learning process is regularized. For example, a basic form of such matrix factorization algorithm is represented as below.\n",
                "\n",
                "$$\\min\\sum(r_{u,i} - q_{i}^{T}p_{u})^2 + \\lambda(||q_{i}||^2 + ||p_{u}||^2)$$\n",
                "\n",
                "where $\\lambda$ is a the regularization parameter. \n",
                "\n",
                "In case explict ratings are not available, implicit ratings which are usually derived from users' historical interactions with the items (e.g., clicks, views, purchases, etc.). To account for such implicit ratings, the original matrix factorization algorithm can be formulated as \n",
                "\n",
                "$$\\min\\sum c_{u,i}(p_{u,i} - q_{i}^{T}p_{u})^2 + \\lambda(||q_{i}||^2 + ||p_{u}||^2)$$\n",
                "\n",
                "where $c_{u,i}=1+\\alpha r_{u,i}$ and $p_{u,i}=1$ if $r_{u,i}>0$ and $p_{u,i}=0$ if $r_{u,i}=0$. $r_{u,i}$ is a numerical representation of users' preferences (e.g., number of clicks, etc.). \n",
                "\n",
                "### 1.2 Alternating Least Square (ALS)\n",
                "\n",
                "Owing to the term of $q_{i}^{T}p_{u}$ the loss function is non-convex. Gradient descent method can be applied but this will incur expensive computations. An Alternating Least Square (ALS) algorithm was therefore developed to overcome this issue. \n",
                "\n",
                "The basic idea of ALS is to learn one of $q$ and $p$ at a time for optimization while keeping the other as constant. This makes the objective at each iteration convex and solvable. The alternating between $q$ and $p$ stops when there is convergence to the optimal. It is worth noting that this iterative computation can be parallelised and/or distributed, which makes the algorithm desirable for use cases where the dataset is large and thus the user-item rating matrix is super sparse (as is typical in recommendation scenarios). A comprehensive discussion of ALS and its distributed computation can be found [here](http://stanford.edu/~rezab/classes/cme323/S15/notes/lec14.pdf)."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## 2 Spark Mllib implementation\n",
                "\n",
                "The matrix factorization algorithm is available as `ALS` module in [Spark `ml`](https://spark.apache.org/docs/latest/ml-collaborative-filtering.html) for DataFrame or [Spark `mllib`](https://spark.apache.org/docs/latest/mllib-collaborative-filtering.html) for RDD. \n",
                "\n",
                "* The uniqueness of ALS implementation is that it distributes the matrix factorization model training by using \"Alternating Least Square\" method. \n",
                "* In the training method, there are parameters that can be selected to control the model performance.\n",
                "* Both explicit and implicit ratings are supported by Spark ALS model."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## 3 Spark ALS based MovieLens recommender\n",
                "\n",
                "In the following code, the MovieLens-100K dataset is used to illustrate the ALS algorithm in Spark."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "**Note**: This notebook requires a PySpark environment to run properly. Please follow the steps in [SETUP.md](https://github.com/Microsoft/Recommenders/blob/master/SETUP.md#dependencies-setup) to install the PySpark environment."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 1,
            "metadata": {},
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "System version: 3.8.0 (default, Nov  6 2019, 21:49:08) \n",
                        "[GCC 7.3.0]\n",
                        "Pandas version: 1.3.5\n",
                        "PySpark version: 3.2.0\n"
                    ]
                }
            ],
            "source": [
                "import warnings\n",
                "warnings.simplefilter(action='ignore', category=FutureWarning)\n",
                "\n",
                "import sys\n",
                "from matplotlib import pyplot as plt\n",
                "import numpy as np\n",
                "import pandas as pd\n",
                "import seaborn as sns\n",
                "\n",
                "import pyspark\n",
                "from pyspark.sql import SparkSession\n",
                "from pyspark.ml.recommendation import ALS\n",
                "import pyspark.sql.functions as F\n",
                "from pyspark.sql.functions import col\n",
                "from pyspark.ml.tuning import CrossValidator\n",
                "from pyspark.sql.types import StructType, StructField\n",
                "from pyspark.sql.types import FloatType, IntegerType, LongType\n",
                "\n",
                "from recommenders.datasets import movielens\n",
                "from recommenders.utils.spark_utils import start_or_get_spark\n",
                "from recommenders.evaluation.spark_evaluation import SparkRankingEvaluation, SparkRatingEvaluation\n",
                "from recommenders.tuning.parameter_sweep import generate_param_grid\n",
                "from recommenders.datasets.spark_splitters import spark_random_split\n",
                "\n",
                "print(f\"System version: {sys.version}\")\n",
                "print(f\"Pandas version: {pd.__version__}\")\n",
                "print(f\"PySpark version: {pyspark.__version__}\")"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "Data column names"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 2,
            "metadata": {
                "tags": [
                    "parameters"
                ]
            },
            "outputs": [],
            "source": [
                "MOVIELENS_DATA_SIZE = \"100k\"\n",
                "\n",
                "COL_USER = \"UserId\"\n",
                "COL_ITEM = \"MovieId\"\n",
                "COL_RATING = \"Rating\"\n",
                "COL_PREDICTION = \"prediction\"\n",
                "COL_TIMESTAMP = \"Timestamp\""
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 3,
            "metadata": {},
            "outputs": [],
            "source": [
                "schema = StructType(\n",
                "    (\n",
                "        StructField(COL_USER, IntegerType()),\n",
                "        StructField(COL_ITEM, IntegerType()),\n",
                "        StructField(COL_RATING, FloatType()),\n",
                "        StructField(COL_TIMESTAMP, LongType()),\n",
                "    )\n",
                ")"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "Model hyper parameters - these parameters are selected with reference to the benchmarking results [here](http://mymedialite.net/examples/datasets.html)."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 4,
            "metadata": {},
            "outputs": [],
            "source": [
                "RANK = 10\n",
                "MAX_ITER = 15\n",
                "REG_PARAM = 0.05"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "Number of recommended items"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 5,
            "metadata": {},
            "outputs": [],
            "source": [
                "K = 10"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "Initialize a Spark session."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 6,
            "metadata": {},
            "outputs": [],
            "source": [
                "spark = start_or_get_spark(\"ALS Deep Dive\", memory=\"16g\")\n",
                "spark.conf.set(\"spark.sql.analyzer.failAmbiguousSelfJoin\", \"false\")"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### 3.1 Load and prepare data"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "Data is read from csv into a Spark DataFrame."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 7,
            "metadata": {},
            "outputs": [
                {
                    "name": "stderr",
                    "output_type": "stream",
                    "text": [
                        "100%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 4.81k/4.81k [00:08<00:00, 593KB/s]\n",
                        "                                                                                \r"
                    ]
                }
            ],
            "source": [
                "dfs = movielens.load_spark_df(spark=spark, size=MOVIELENS_DATA_SIZE, schema=schema)"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 8,
            "metadata": {
                "scrolled": true
            },
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "+------+-------+------+---------+\n",
                        "|UserId|MovieId|Rating|Timestamp|\n",
                        "+------+-------+------+---------+\n",
                        "|   196|    242|   3.0|881250949|\n",
                        "|   186|    302|   3.0|891717742|\n",
                        "|    22|    377|   1.0|878887116|\n",
                        "|   244|     51|   2.0|880606923|\n",
                        "|   166|    346|   1.0|886397596|\n",
                        "+------+-------+------+---------+\n",
                        "only showing top 5 rows\n",
                        "\n"
                    ]
                }
            ],
            "source": [
                "dfs.show(5)"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "Data is then randomly split by 80-20 ratio for training and testing."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 9,
            "metadata": {},
            "outputs": [],
            "source": [
                "dfs_train, dfs_test = spark_random_split(dfs, ratio=0.75, seed=42)"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### 3.2 Train a movielens model "
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "It is worth noting that Spark ALS model allows dropping cold users to favor a robust evaluation with the testing data. In case there are cold users, Spark ALS implementation allows users to drop cold users in order to make sure evaluations on the prediction results are sound."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 10,
            "metadata": {},
            "outputs": [],
            "source": [
                "als = ALS(\n",
                "    maxIter=MAX_ITER, \n",
                "    rank=RANK,\n",
                "    regParam=REG_PARAM, \n",
                "    userCol=COL_USER, \n",
                "    itemCol=COL_ITEM, \n",
                "    ratingCol=COL_RATING, \n",
                "    coldStartStrategy=\"drop\"\n",
                ")\n",
                "\n",
                "model = als.fit(dfs_train)"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### 3.3 Prediction with the model\n",
                "\n",
                "The trained model can be used to predict ratings with a given test data."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 11,
            "metadata": {},
            "outputs": [],
            "source": [
                "dfs_pred = model.transform(dfs_test).drop(COL_RATING)"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "With the prediction results, the model performance can be evaluated."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 12,
            "metadata": {},
            "outputs": [
                {
                    "name": "stderr",
                    "output_type": "stream",
                    "text": [
                        "                                                                                \r"
                    ]
                },
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "RMSE score = 0.9636472784840003\n",
                        "MAE score = 0.7508415106649321\n",
                        "R2 score = 0.2661953136123826\n",
                        "Explained variance score = 0.271522993322584\n"
                    ]
                }
            ],
            "source": [
                "evaluations = SparkRatingEvaluation(\n",
                "    dfs_test, \n",
                "    dfs_pred,\n",
                "    col_user=COL_USER,\n",
                "    col_item=COL_ITEM,\n",
                "    col_rating=COL_RATING,\n",
                "    col_prediction=COL_PREDICTION\n",
                ")\n",
                "\n",
                "print(\n",
                "    \"RMSE score = {}\".format(evaluations.rmse()),\n",
                "    \"MAE score = {}\".format(evaluations.mae()),\n",
                "    \"R2 score = {}\".format(evaluations.rsquared()),\n",
                "    \"Explained variance score = {}\".format(evaluations.exp_var()),\n",
                "    sep=\"\\n\"\n",
                ")"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "Oftentimes ranking metrics are also of interest to data scientists. Note usually ranking metrics apply to the scenario of recommending a list of items. In our case, the recommended items should be different from those that have been rated by the users. "
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 13,
            "metadata": {},
            "outputs": [
                {
                    "name": "stderr",
                    "output_type": "stream",
                    "text": [
                        "[Stage 477:>                                                        (0 + 1) / 1]\r"
                    ]
                },
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "+------+-------+----------+\n",
                        "|UserId|MovieId|prediction|\n",
                        "+------+-------+----------+\n",
                        "|     1|      3| 2.6714876|\n",
                        "|     1|      7|  4.319914|\n",
                        "|     1|      9|  4.151373|\n",
                        "|     1|     20|  3.829036|\n",
                        "|     1|     33| 3.5674067|\n",
                        "|     1|     36| 1.1223706|\n",
                        "|     1|     43| 2.3707652|\n",
                        "|     1|     46|  3.959927|\n",
                        "|     1|     48| 4.6534643|\n",
                        "|     1|     50| 5.2104144|\n",
                        "|     1|     52| 4.1401386|\n",
                        "|     1|     63| 2.2337403|\n",
                        "|     1|     65| 3.5661814|\n",
                        "|     1|     84| 2.0204403|\n",
                        "|     1|    113|  4.335376|\n",
                        "|     1|    117| 3.3492455|\n",
                        "|     1|    118|  2.856406|\n",
                        "|     1|    119|  4.807717|\n",
                        "|     1|    161| 2.8039317|\n",
                        "|     1|    190|  3.963532|\n",
                        "+------+-------+----------+\n",
                        "only showing top 20 rows\n",
                        "\n"
                    ]
                },
                {
                    "name": "stderr",
                    "output_type": "stream",
                    "text": [
                        "\r\n",
                        "[Stage 481:>                                                        (0 + 1) / 1]\r\n",
                        "\r\n",
                        "                                                                                \r"
                    ]
                }
            ],
            "source": [
                "# Get the cross join of all user-item pairs and score them.\n",
                "users = dfs_train.select(COL_USER).distinct()\n",
                "items = dfs_train.select(COL_ITEM).distinct()\n",
                "user_item = users.crossJoin(items)\n",
                "dfs_pred = model.transform(user_item)\n",
                "\n",
                "# Remove seen items.\n",
                "dfs_pred_exclude_train = dfs_pred.alias(\"pred\").join(\n",
                "    dfs_train.alias(\"train\"),\n",
                "    (dfs_pred[COL_USER] == dfs_train[COL_USER]) & (dfs_pred[COL_ITEM] == dfs_train[COL_ITEM]),\n",
                "    how='outer'\n",
                ")\n",
                "\n",
                "dfs_pred_final = dfs_pred_exclude_train.filter(dfs_pred_exclude_train[\"train.Rating\"].isNull()) \\\n",
                "    .select('pred.' + COL_USER, 'pred.' + COL_ITEM, 'pred.' + \"prediction\")\n",
                "\n",
                "dfs_pred_final.show()"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 14,
            "metadata": {},
            "outputs": [
                {
                    "name": "stderr",
                    "output_type": "stream",
                    "text": [
                        "[Stage 560:>                                                        (0 + 2) / 2]\r"
                    ]
                },
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "Precision@k = 0.04379639448568401\n",
                        "Recall@k = 0.014286194686756822\n",
                        "NDCG@k = 0.03730295615527768\n",
                        "Mean average precision = 0.0034619726118607337\n"
                    ]
                },
                {
                    "name": "stderr",
                    "output_type": "stream",
                    "text": [
                        "\r\n",
                        "                                                                                \r"
                    ]
                }
            ],
            "source": [
                "evaluations = SparkRankingEvaluation(\n",
                "    dfs_test, \n",
                "    dfs_pred_final,\n",
                "    col_user=COL_USER,\n",
                "    col_item=COL_ITEM,\n",
                "    col_rating=COL_RATING,\n",
                "    col_prediction=COL_PREDICTION,\n",
                "    k=K\n",
                ")\n",
                "\n",
                "print(\n",
                "    \"Precision@k = {}\".format(evaluations.precision_at_k()),\n",
                "    \"Recall@k = {}\".format(evaluations.recall_at_k()),\n",
                "    \"NDCG@k = {}\".format(evaluations.ndcg_at_k()),\n",
                "    \"Mean average precision = {}\".format(evaluations.map_at_k()),\n",
                "    sep=\"\\n\"\n",
                ")"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### 3.4 Fine tune the model\n",
                "\n",
                "Prediction performance of a Spark ALS model is often affected by the parameters\n",
                "\n",
                "|Parameter|Description|Default value|Notes|\n",
                "|-------------|-----------------|------------------|-----------------|\n",
                "|`rank`|Number of latent factors|10|The larger the more intrinsic factors considered in the factorization modeling.|\n",
                "|`regParam`|Regularization parameter|1.0|The value needs to be selected empirically to avoid overfitting.|\n",
                "|`maxIters`|Maximum number of iterations|10|The more iterations the better the model converges to the optimal point.|\n",
                "\n",
                "It is always a good practice to start model building with default parameter values and then sweep the parameter in a range to find the optimal combination of parameters. The following parameter set is used for training ALS models for comparison study purposes."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 15,
            "metadata": {},
            "outputs": [],
            "source": [
                "param_dict = {\n",
                "    \"rank\": [10, 15, 20],\n",
                "    \"regParam\": [0.001, 0.1, 1.0]\n",
                "}"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "Generate a dictionary for each parameter combination which can then be fed into model training."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 16,
            "metadata": {},
            "outputs": [],
            "source": [
                "param_grid = generate_param_grid(param_dict)"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "Train models with parameters specified in the parameter grid. Evaluate the model with, for example, the RMSE metric, and then record the metrics for visualization."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 17,
            "metadata": {},
            "outputs": [
                {
                    "name": "stderr",
                    "output_type": "stream",
                    "text": [
                        "                                                                                \r"
                    ]
                }
            ],
            "source": [
                "rmse_score = []\n",
                "\n",
                "for g in param_grid:\n",
                "    als = ALS(        \n",
                "        userCol=COL_USER, \n",
                "        itemCol=COL_ITEM, \n",
                "        ratingCol=COL_RATING, \n",
                "        coldStartStrategy=\"drop\",\n",
                "        **g\n",
                "    )\n",
                "    \n",
                "    model = als.fit(dfs_train)\n",
                "    \n",
                "    dfs_pred = model.transform(dfs_test).drop(COL_RATING)\n",
                "    \n",
                "    evaluations = SparkRatingEvaluation(\n",
                "        dfs_test, \n",
                "        dfs_pred,\n",
                "        col_user=COL_USER,\n",
                "        col_item=COL_ITEM,\n",
                "        col_rating=COL_RATING,\n",
                "        col_prediction=COL_PREDICTION\n",
                "    )\n",
                "\n",
                "    rmse_score.append(evaluations.rmse())\n",
                "\n",
                "rmse_score = [float('%.4f' % x) for x in rmse_score]\n",
                "rmse_score_array = np.reshape(rmse_score, (len(param_dict[\"rank\"]), len(param_dict[\"regParam\"]))) "
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 18,
            "metadata": {},
            "outputs": [],
            "source": [
                "rmse_df = pd.DataFrame(data=rmse_score_array, index=pd.Index(param_dict[\"rank\"], name=\"rank\"), \n",
                "                       columns=pd.Index(param_dict[\"regParam\"], name=\"reg. parameter\"))"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 19,
            "metadata": {},
            "outputs": [
                {
                    "data": {
                        "text/plain": [
                            "<AxesSubplot:xlabel='reg. parameter', ylabel='rank'>"
                        ]
                    },
                    "execution_count": 19,
                    "metadata": {},
                    "output_type": "execute_result"
                },
                {
                    "data": {
                        "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEGCAYAAABmXi5tAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAi60lEQVR4nO3de5xN9f7H8ddn7z0XlyEz5C45dTouHZVLcgqdnFAJEemUSHeFyiWnoptEN+midBLRjVKEilOc5JfGpTiik2unGUNyZ4yZ2fv7+2Nvk8GMqezZmfV+Ph770V7f9V1rfb5W+z1rvntZzDmHiIiUfL5YFyAiIsVDgS8i4hEKfBERj1Dgi4h4hAJfRMQjArEuoCA7u1+o24dOYBXf/S7WJcivtGtg81iXIL9BmeFTraB1usIXEfEIBb6IiEco8EVEPEKBLyLiEQp8ERGPUOCLiHiEAl9ExCMU+CIiHqHAFxHxCAW+iIhHKPBFRDxCgS8i4hEKfBERj1Dgi4h4hAJfRMQjFPgiIh6hwBcR8QgFvoiIRyjwRUQ8QoEvIuIRCnwREY9Q4IuIeIQCX0TEIxT4IiIeocAXEfEIBb6IiEco8EVEPEKBLyLiEQp8ERGPUOCLiHiEAl9ExCMCsS6gJCh18yDizm6G272TPYOuP2J9oNFfKNW1F4QcLhRk/2vPEfzvSvyn/IFS19+JlS4DoSBZ771OzqJ5edsldu1NXLOWEApxYO4Msj+eVpzDKtHaXNyKp556CL/Px/hX32TU48/nW1+rVnX+Oe4pKlZKZsf2nfTo2Zf09AwaNqzP88+OIKlcWYLBICMee5apU2fkbffwQ4Pp3PkygsEgL730Gs89P57u3TsxcMBtmBl79+yjzx1DWLFiVXEPuUSKv+JWAmc0wu3bxf4xdx+x3l+3MfGtr8I5B6Eg2bMmEPr+WwCsfEUSOt2ClU8BIGvio7idW/HVaUB8u2sxf4Bg+nqy3xsLoVCxjitaFPjHQfa/PyL74/cofduQo67PXbmUPUsXAuCrVYcyfYexZ8B1uAMHyBw7gtDmdKxCCknDXyJ3RSoucx/xLdviSzmZPXdfB85h5U4qxhGVbD6fjzHPDKftJd1JS8tg0Rez+WDmHFavXpPXZ9TIoUx6/R0mTZrKha3+wvBHhtCzV18yM/fT8/p+rF27gapVK5O66EPmzJnPrl27ua5HV2rUqEb9Bi1wzlGpUjhINm74gb9e1IWdO3fRts2FvPjCSJqf3z5Wwy9RcpfNJ3fRRyR0uf2o64PrVrJ/9QAArHItErvfxf7R/QFI6HI72fOnEVq3AuITwYXAjITOfcga/xBuWwZxF3UjcHYrcpd+Wkwjii5N6RwHwW9X4PbuLrjDgay8t5aQCDgAQpvTCG1OB8Dt2IbbvTMv2ONbX07WtIngwn3d7p3RKN2TmjY5m3XrNrJhw//IyclhypTpXN6+Tb4+deuezrx54R/S8+Yv5PL2FwOwZs161q7dAEBGxhZ+3LotL9hvubkHjwx/Onw1CWzdug2ALxYtYefOXQAs+nIZ1atXjf4gPSK0cTUuc2/BHbIP+ezFJ+Z9nqxSDfD5w2F/sF9ONpRKgmAublsGAMG1y/HXPzdq9Re3qAS+mZU3s8fM7Fsz225m28xsdaTtpGgc8/curvH5JD0xkTKDRpD50qgj1vv/8CcIBAht2QSAr3I14s67kLLDX6TM4MfwVale3CWXWNWqV+GHtE15y2npGVSrViVfnxUrVtGpYzsAOnZsR7lySSQnV8jXp0njs4iPj2Pduo0A1KlTm65XXs6iL2Yzc8YkTjvt1COOfX2vq/jo43lHtEv0+Os1pVT/0ST2GMKBaWMB8FWsisvaR8LVA0jsM4q4tteC+SBzN/j8+KrXASDQ4Dx85SvGsvzjKlpX+FOAHUAr51yycy4FuDDSNiVKx/xdy1nyOXsGXMe+J+8n8cr88/x2UjKlbxtC5osjf74CiYuHnGz23nsL2Z/OovTNg2JRtmcNGvwwLVo0Y3Hqx7S4oBlpaRkEg8G89VWqnMyECWO44Ya78q7oExLiyco6QLPzLuGf49/gn+OezLfPVi2b06tXd4b849FiHYvXBVelsn90f7JeH0V8627hRp8ff+26ZH/4Gllj78FX4WQC57QC4MDbo4m/pCeJt47AHdiPcyVj/h6iF/i1nXMjnXObDzY45zY750YCpxS0kZndZGZLzGzJhLWbCup2Qgt+uwLfyVWxpHLhhlKlKTNoBFlvv0Jw7eq8fqFtW8lJXQBAzuIF+GvViUW5JdKm9M3UrFEtb7lG9aps2rQ5X5+MjC1c2fVGmjRtw/1DRwKwa1d42i4pqSwzpr/G/UNH8mXqsrxt0tIzeO/92QC8//6HnHlm3bx1Z55Zl5defJwrOl/P9u07ojY2KVho42osuTKUTsLt3kYoYyNux48QChFcvRhftfBvZKEfviPr5aFkjR1CaOMq3E8lJ4uiFfjfm9kgM6t8sMHMKpvZYOCHgjZyzo1zzjV2zjXueVq1grqdcHyVfx6Lv/bpWFwcbs9u8Acoc9fD5CyYQ07qZ/m2yVnyOYH6ZwMQqNuQYEZasdZcki1e8jWnnXYqtWvXJC4ujq5dO/DBzDn5+qSkVMDMALhn8B1MmPgWAHFxcbw79RUmT36HadNm5dtmxoyPaNWyOQAtW5zHd2vWA1CzZjWmvv0yPXv1Y02kTYqHJf88VeerdioE4iBzD6G0dZBYGkqHL7x8dRoQ+jHyGSsTuRjzB4hr0ZGc1LnFXXbUROsunW7APcC/zezkSNsWYAZwZZSOGTOl77iPQN2zsKTylHtuClnvTICAH4Dsf31AXNMWxLdoA7m5uOwD7BvzEABx57Ui8Kc/4ytbjvgWbQHIfPExgt+v48CMNyh9+30ktOuCy9pP5rgnYjW8EicYDNKv/33MnvUGfp+PCRPfZtWq73hg2ACWLF3OzJlzadmyOcMfHoLDsWDBIu7oey8AV17ZngsuOJfklAr06NEVgN433Mny5d8wctTzTJr4HP363ci+vZncfMtAAO67905SUirw7LPhqZzc3FyanXdJbAZfwiR07YevTn2sdBKlBr1IzidTwB/+7OWmziVQ/1wCZ7fEhYKQk82Bt54Ob+hCZH84iVK9hwJGcNN6cpd8AkDcBR0InHEOmI+c1I8JrV8Zo9Edf3Zw/rHYDmjWyzn36rH67ex+YfEWJsdVxXe/i3UJ8ivtGtg81iXIb1Bm+FQraF0sbst8MAbHFBHxvKhM6ZjZioJWAZULWCciIlEUrTn8ykAbwrdhHsqA/4vSMUVEpBDRCvyZQFnn3NeHrzCz+VE6poiIFCIqge+c613IuqujcUwRESmcnqUjIuIRCnwREY9Q4IuIeIQCX0TEIxT4IiIeocAXEfEIBb6IiEco8EVEPEKBLyLiEQp8ERGPUOCLiHiEAl9ExCMU+CIiHqHAFxHxCAW+iIhHKPBFRDxCgS8i4hEKfBERj1Dgi4h4hAJfRMQjFPgiIh6hwBcR8QgFvoiIRyjwRUQ8QoEvIuIRCnwREY9Q4IuIeEQg1gUUJHHw3bEuQX4De/fmWJcgIofRFb6IiEco8EVEPEKBLyLiEQp8ERGPUOCLiHiEAl9ExCMU+CIiHqHAFxHxCAW+iIhHKPBFRDxCgS8i4hEKfBERj1Dgi4h4hAJfRMQjFPgiIh6hwBcR8QgFvoiIRyjwRUQ8QoEvIuIRCnwREY9Q4IuIeIQCX0TEIxT4IiIeocAXEfEIBb6IiEco8EVEPKJIgW9mCUdpSz7+5YiISLQU9Qp/mpnFHVwws6rA3OiUJCIi0VDUwH8fmGJmfjOrDXwMDIlWUSIicvwFitLJOfeymcUTDv7awM3Ouf+LYl0iInKcFRr4ZnbXoYtALeBroJmZNXPOPRXF2kRE5Dg61hV+0mHL0wpo97ShY9/is2WrSS5XlmlPDiyw38q1/6PH/c8yst81/K1ZQwCefn0mC5atBuCmzq1p2/xsAO5/4U2WrFpPUulEAB667Sr+VLt6lEfiHRdf3IqnnnoIv8/H+Fff5PHHn8+3vlat6rw87ikqVUpm+/adXNezL+npGTRsWJ/nnh1BUrmyhIJBRjz2LFOnzgCgVau/MGrk/cTFx/HVsv9w4013EwwG8/bZuFFDFiyYwd+vuY1p02YV63hLqvgrbiVwRiPcvl3sH3P3Eev9dRsT3/oqnHMQCpI9awKh778FwMpXJKHTLVj5FACyJj6K27kVX50GxLe7FvMHCKavJ/u9sRAKFeu4oqXQwHfOPVhchZzIOrRsQvc253Pv828W2CcYCjH6jVmc9+c/5rV9tmwV325IY8qou8jOyeWGB8dy/ll1KRsJ+buuuSzvB4McPz6fjzHPDKfdJd1JS8tg0RezmTlzDqtXr8nrM3LkUCa//g6TJk2lVau/MPyRIfTs1ZfMzP30ur4fa9duoGrVyny56EPmzJnP7t17GP/KaNq07caaNesZNmwAPa69klcnvJV3zEcfvZe5c/8dq2GXSLnL5pO76CMSutx+1PXBdSvZv3oAAFa5Fond72L/6P4AJHS5nez50witWwHxieBCYEZC5z5kjX8Ity2DuIu6ETi7FblLPy2mEUVXUW/L/KOZjTOzOWb26cFXIf3bHvK+vJm9YmYrzOwNM6t8PAr/PWlU7w+UK1u60D5vfvg5rc89k+TyZfPa1qdt4Zy6fyDg91M6MYHTT6nKwuXfRrtcz2va5GzWrdvIhg3/Iycnh7enTKd9+zb5+tStezrz5i0EYP78hbRvfzEAa9asZ+3aDQBkZGxh69ZtVKqUQkpKBbKzs1mzZj0A//rXZ3TqdEne/m7vcz3vvTeLrVu3FccQPSO0cTUuc2/BHbKz8t5afCI4F35fqQb4/OGwP9gvJxtKJUEwF7ctA4Dg2uX4658btfqLW1Hv0pkKfAXcBww85FWQRw95/ySQAbQHFgMv/fIyT2xbtu/i08X/oevfmudr/+Mp1fi/r79l/4Fsduzey+Jv1rL5p515659960O6DHyCxydOJzsnt5irLrmqVa9CWtqmvOX09AyqV6uSr8+KFavo1LEdAB07tqNcuSSSkyvk69Ok8VnExcexbt1GfvppO4FAgEbn/BmAzldcSs2a1cLHq1aFDh3a8uJLr0VzWFIAf72mlOo/msQeQzgwbSwAvopVcVn7SLh6AIl9RhHX9lowH2TuBp8fX/U6AAQanIevfMVYln9cFekuHSDXOTf2Vx6jsXPurMj7p83suoI6mtlNwE0Az93Xh96d2xbU9YTy+IT36X/1Zfh8+X++Nm94Bt+s+4Hr7n+WCuXK0PD0U/BH+vTtfikVT0oiJzfIQ+OmMn76p9zS5eJYlO9Jgwc/zDPPPEKPHl1ZsGARaWkZ+ebjq1Q5mVcnjKH39f3D88PANdfcxhNPPEBCQjxz//UZwWB43vfJJx/kH/94NK+fFK/gqlT2r0rFV7su8a27kfXqw+Dz469dl/3PDcTt+omEbncSOCc8dXPg7dHEX9ITAnEE1yzHuZIxfw9FD/wPzOw24D3gwMFG59z2AvqfHLnDx4ByZmbu5//bC/ytwjk3DhgHkPX1zBLz6fhmfRqDx0wCYMfufSz46lv8fh9/bXImN17RmhuvaA3APWMmc0q1SgBUqlAOgPi4AB1aNWHizPkxqb0k2pS+mRo1quUtV69elfRNm/P1ycjYQteuNwJQpkxpOnW6lF27dgOQlFSWGdNfY+jQkXyZuixvm0VfLuXCv14BQOvWLTj99PBVYqNz/szkyS8AULFiMm3b/pXc3FxmzPg4eoOUI4Q2rsaSK0PpJNzubYQyNuJ2/AhAcPVifDVPh6UQ+uE7sl4eCoD/tD/jq1g1lmUfV0UN/INX5YdO4zigTgH9X+bnO3kmAhWBrWZWhfBtnZ7y4XP35r2//4U3aXFOPf7a5EyCoRB79u3npKQyfPf9Jr77PoNH+oS/1N26YzeVKpTDOce8xSs5rWaVgnYvv9DiJV9z2mmnUrt2TdLTN9Otaweu7dEnX5+UlAps374T5xyDB9/BhInhL1/j4uJ4Z+orTJ78zhF32lSqlMLWrduIj49n4IA+jHhsDAB/POO8vD6v/PNpZs3+l8K+mFhyFdz28A9zX7VTIRAHmXsI7d8HiaWhdDnI3I2vTgNC6evCG5UpB/t2gz9AXIuOZM+fVsgRTixF/YtXp/6SnRZ0d49zbrOZzfsl+zoRDH5mEktWrWPnnn387daHuPXKNuRGfv0/fN7+ULm5QXoNC98OWKZUAo/ecTUBvx+AIc++zo7de3EOzqhdjftv7BL9gXhEMBikX//7mDXrDfw+HxMmvs2qVd8xbNgAli5dzsyZc2nZsjmPPDwEh+PzBYu4o2/4h/aVV7bnggvOJSWlAj16dAWg9w13snz5N9x9161ccmlrfD4f4156jfnzF8ZymJ6Q0LUfvjr1sdJJlBr0IjmfTIHIZyg3dS6B+ucSOLslLhSEnGwOvPV0eEMXIvvDSZTqPRQwgpvWk7vkEwDiLuhA4IxzwHzkpH5MaP3KGI3u+LOiziuaWQOgHpB4sM0594u/hTKz/znnah2rX0ma0vGipKY3x7oE+ZV2Diz4IkV+/8oMn2oFrSvSFb6ZDQNaEQ782UA74HPgqIFvZisK2hVQ4m7LFBE5ERR1Dr8L0BD4yjnXK3Iv/eRC+lcG2gA7Dms3QM/gERGJgaIGfpZzLmRmuWZWDvgRqFlI/5lAWefc14evMLP5v7hKERH5zY4Z+GZmwAozO4nw3TdLgb3AFwVt45zrXci6q395mSIi8lsdM/Cdc87MmjrndgIvmtlHQDnnXEHz9CIi8jtU1EcrLDOzJgDOuY0KexGRE09R5/DPBf5uZt8D+wh/+eqcc3+OWmUiInJcFTXw2xy7i4iI/J4V9W/afh/tQkREJLqKOocvIiInOAW+iIhHKPBFRDxCgS8i4hEKfBERj1Dgi4h4hAJfRMQjFPgiIh6hwBcR8QgFvoiIRyjwRUQ8QoEvIuIRCnwREY9Q4IuIeIQCX0TEIxT4IiIeocAXEfEIBb6IiEco8EVEPEKBLyLiEQp8ERGPUOCLiHhEINYFFMRfo16sS5DfwMW6ABE5gq7wRUQ8QoEvIuIRCnwREY9Q4IuIeIQCX0TEIxT4IiIeocAXEfEIBb6IiEco8EVEPEKBLyLiEQp8ERGPUOCLiHiEAl9ExCMU+CIiHqHAFxHxCAW+iIhHKPBFRDxCgS8i4hEKfBERj1Dgi4h4hAJfRMQjFPgiIh6hwBcR8QgFvoiIRyjwRUQ8QoEvIuIRCnwREY9Q4IuIeIQCX0TEIxT4IiIeocAXEfGIQKwLKAnue/QpPluYSnKFk3h/8otHrE9dtoK+9zxI9apVAGjdsjm3Xv/3vPXBYJBuvftycqWKvPD4gwAMfmAk33y7hkAgQIN6f2TYoL7EBXS6jpc2F7fiqacewu/zMf7VNxn1+PP51teqVZ1/jnuKipWS2bF9Jz169iU9PYOGDevz/LMjSCpXlmAwyIjHnmXq1BkAzP90GmWTygJwcqUUFi/5ms5detOyxXlMe3c8Gzb+AMD778/mkeGji3W8JVX8FbcSOKMRbt8u9o+5+4j1/rqNiW99Fc45CAXJnjWB0PffAmDlK5LQ6RasfAoAWRMfxe3ciq9OA+LbXYv5AwTT15P93lgIhYp1XNGiBDkOOl7yN67ufDn/ePiJAvuc07BBXpgfbvLU6dSpXYu9+zLz2i69+EIeGzYIgEEPjOTdDz7iqk6XHd/CPcrn8zHmmeG0vaQ7aWkZLPpiNh/MnMPq1Wvy+owaOZRJr7/DpElTubDVXxj+yBB69upLZuZ+el7fj7VrN1C1amVSF33InDnz2bVrN63+ekXe9lPeHseMD+bkLX/+eSodOl1XrOP0gtxl88ld9BEJXW4/6vrgupXsXz0AAKtci8Tud7F/dH8AErrcTvb8aYTWrYD4RHAhMCOhcx+yxj+E25ZB3EXdCJzditylnxbTiKIrKlM6ZlbezB4zs2/NbLuZbTOz1ZG2k6JxzFhqfNaZlC+X9Ku23fzjVj77v1Q6t2+Tr71F86aYGWbGmXXPYMuPPx2PUgVo2uRs1q3byIYN/yMnJ4cpU6Zz+WF//nXrns68eQsBmDd/IZe3vxiANWvWs3btBgAyMrbw49ZtVKqUkm/bpKSyXNjqL0yf/lExjMbbQhtX4zL3FtwhOyvvrcUngnPh95VqgM8fDvuD/XKyoVQSBHNx2zIACK5djr/+uVGrv7hFaw5/CrADaOWcS3bOpQAXRtqmROmYv2vLV67miutu45a772ft+u/z2kc+8xJ33dYbs6OfipzcXD74+BPOP7dxcZVa4lWrXoUf0jblLaelZ1CtWpV8fVasWEWnju0A6NixHeXKJZGcXCFfnyaNzyI+Po516zbma+/QoS2fzlvInj0/B1GzZo1YumQuM2dMol69Px7nEUlh/PWaUqr/aBJ7DOHAtLEA+CpWxWXtI+HqAST2GUVc22vBfJC5G3x+fNXrABBocB6+8hVjWf5xFa3Ar+2cG+mc23ywwTm32Tk3EjglSsf83ap3xh+Y++5Epk18gas7t6fvkIcAmL/wS5IrnET9P51e4LaPPPE8jRo2oNFZDYqrXAEGDX6YFi2asTj1Y1pc0Iy0tAyCwWDe+ipVTmbChDHccMNd4fnhQ1zVtQNvvf1+3vKyr/5DndOa0qjx33j+hVd5d+r44hqGAMFVqewf3Z+s10cR37pbuNHnx1+7LtkfvkbW2HvwVTiZwDmtADjw9mjiL+lJ4q0jcAf241zJmL+H6AX+92Y2yMwqH2wws8pmNhj4oaCNzOwmM1tiZkv++dqbUSqt+JUtU4bSpUsB4ama3NxcduzcxVcrVjH/80Vc3Pk6Bg57jNSlyxn84Ki87V4Y/zo7du5iUN+bYlV6ibQpfTM1a1TLW65RvSqbNm3O1ycjYwtXdr2RJk3bcP/QkQDs2rUbCE/ZzJj+GvcPHcmXqcvybZeSUoEmTc5m9uxP8tr27NnLvsj3Mx9+9ClxcQFSUvL/tiDRF9q4GkuuDKWTcLu3EcrYiNvxI4RCBFcvxlft1HC/H74j6+WhZI0dQmjjKtxPm46x5xNHtL607QbcA/w7EvoO2ALMALoWtJFzbhwwDiDnp/WuoH4nmp+2bScluQJmxn9W/ZeQc5xUvhx33tqLO2/tBYTv5Jnw5ruMjHxR+86Mj1j45VJeGTMCn093zx5Pi5d8zWmnnUrt2jVJT99M164duLZHn3x9UlIqsH37Tpxz3DP4DiZMfAuAuLg43p36CpMnv8O0abOO2HfnKy5j1ux/ceDAgby2ypUrsWXLViA8DeTz+di2bUcURygHWXIV3PbwD3NftVMhEAeZewjt3weJpaF0Ocjcja9OA0Lp68IblSkH+3aDP0Bci45kz58WwxEcX1EJfOfcDjN7FZgLLHLO5U1mmllboER9mzVw2GMs/moFO3fu5qKO13Bb72vJzc0FoFunS5kz73Pefm8W/oCfxPh4Hn/wHsys0H0+/MSzVK18Mn+/6S7gyFs55dcLBoP0638fs2e9gd/nY8LEt1m16jseGDaAJUuXM3PmXFq2bM7wh4fgcCxYsIg7+t4LwJVXtueCC84lOaUCPXqEr11633Any5d/A0C3rpcfcYtn5ysu5eabe5CbGyRrfxZ/v+a24h1wCZbQtR++OvWx0kmUGvQiOZ9MAb8fgNzUuQTqn0vg7Ja4UBBysjnw1tPhDV2I7A8nUar3UMAIblpP7pLwb2VxF3QgcMY5YD5yUj8mtH5ljEZ3/Nnh84/HZadmfYE+wGrgLKCfc256ZN0y59w5x9pHSbrC96JS1S6IdQnyK+0a2DzWJchvUGb41AKvJqM1pXMj0Mg5t9fMagPvmFlt59wzQOGXtiIiEhXRCnzfwWkc59xGM2tFOPRPQYEvIhIT0fo2cIuZnXVwIRL+lwEVgTOjdEwRESlEtAK/B5DvPjfnXK5zrgfQIkrHFBGRQkTrLp20QtYtjMYxRUSkcLrBW0TEIxT4IiIeocAXEfEIBb6IiEco8EVEPEKBLyLiEQp8ERGPUOCLiHiEAl9ExCMU+CIiHqHAFxHxCAW+iIhHKPBFRDxCgS8i4hEKfBERj1Dgi4h4hAJfRMQjFPgiIh6hwBcR8QgFvoiIRyjwRUQ8QoEvIuIRCnwREY9Q4IuIeIQCX0TEIxT4IiIeocAXEfEIc87FugZPMrObnHPjYl2H/Do6fycuL587XeHHzk2xLkB+E52/E5dnz50CX0TEIxT4IiIeocCPHU/OIZYgOn8nLs+eO31pKyLiEbrCFxHxCAW+iIhHKPCPAzNra2b/NbO1ZnbPUdYnmNnbkfVfmlntQ9YNibT/18zaHNI+3sx+NLOVxTQMOUwRzmsLM1tmZrlm1iUWNcrRHevzY2FjIud2hZmdU9w1xoIC/zcyMz/wPNAOqAd0N7N6h3XrDexwzp0GPA2MjGxbD7gKqA+0BV6I7A9gQqRNYqCI5/V/QE/gjeKtTopgAoV/ftoBp0deNwFji6GmmFPg/3ZNgbXOufXOuWzgLaDDYX06ABMj798BLjIzi7S/5Zw74JzbAKyN7A/n3GfA9uIYgBzVMc+rc26jc24FEIpFgVKwInx+OgCvubBFwElmVrV4qosdBf5vVx344ZDltEjbUfs453KBXUBKEbeV2NC5Kdk8eX4V+CIiHqHA/+3SgZqHLNeItB21j5kFgPLAtiJuK7Ghc1OyefL8KvB/u8XA6WZ2qpnFE/4SdsZhfWYA10XedwE+deG/8TYDuCpyF8+phL9ASi2muqVwRTmvcuKaAfSI3K3TDNjlnMuIdVHRFoh1ASc651yumd0OfAz4gfHOuW/M7CFgiXNuBvAKMMnM1hL+IumqyLbfmNkUYBWQC/RxzgUBzOxNoBVQ0czSgGHOuVeKeXieVZTzamZNgPeACkB7M3vQOVc/hmVLxNE+P0AcgHPuRWA2cAnhGyUygV6xqbR46dEKIiIeoSkdERGPUOCLiHiEAl9ExCMU+CIiHqHAFxHxCAW+yO+Qmf0j1jVIyaPbMuWEEXngnDnnfhcPKzMz/8G/NxGFfe91zpX9vdQjJYOu8OV3zcxqR55J/xqwEqhpZgPNbHHkOeYPHtL3/kjfz83sTTMbcIx99zSz6WY238zWmNmwQ9a9b2ZLzewbM7vpkPa9ZvakmS0HzjOzoZFaVprZuMgPJSL7fNrMlpjZajNrYmbTIsd55JD9XWNmqWb2tZm9ZGZ+M3sMKBVpe72gfker57j8oUvJ5ZzTS6/f7QuoTfjxw80iyxcT/keojfAFy0ygBdAE+BpIBJKANcCAY+y7J5BB+MmlpQj/QGkcWZcc+e/B9pTIsgO6HrKP5EPeTwLaR97PB0ZG3vcDNgFVgQTCT2ZMAeoCHwBxkX4vAD0i7/cest/C+uWrRy+9Cnvp0QpyIvjehZ9ZDuHAvxj4KrJclvAziJKA6c65LCDLzD4o4r7nOue2AZjZNOB8YAnQ18w6RfrUjBxjGxAE3j1k+wvNbBBQGkgGviEczvDzs3f+A3zjIs9qMbP1kX2eDzQCFkd+MSgF/HiUGi8qpN/h9YgUSIEvJ4J9h7w3YIRz7qVDO5hZ/1+578O/xHJm1gpoDZznnMs0s/mEf3MAyHI/P+8okfDVdmPn3A9m9sAh/QAORP4bOuT9weVAZCwTnXNDjlFjYf3y6hE5Fs3hy4nmY+B6MysLYGbVzexkYCHhB5glRtZdVsT9/c3Mks2sFNAxsp/yhP9Jykwz+xPQrIBtD4b7T5Fj/tJ/1/YToEukfiJ1nBJZl2NmcUXoJ1JkusKXE4pzbo6Z1QW+iExv7AWucc4tNrMZwApgC+FplF0AZnZLZNsXj7LLVMJTIjWAyc65JWb2H+AWM1sN/BdYdJTtcM7tNLOXCc/xbyb8SOVfMpZVZnYfMMfMfEAO0Af4nvD3FCvMbJlz7u+F9BMpMt2WKSWGmZV1zu01s9LAZ8BNzrllhfTvSXg65vbiqlEklnSFLyXJODOrR3iqZWJhYS/iRbrCFxHxCH1pKyLiEQp8ERGPUOCLiHiEAl9ExCMU+CIiHvH/Lufbq4FeUs0AAAAASUVORK5CYII=",
                        "text/plain": [
                            "<Figure size 432x288 with 1 Axes>"
                        ]
                    },
                    "metadata": {
                        "needs_background": "light"
                    },
                    "output_type": "display_data"
                }
            ],
            "source": [
                "fig, ax = plt.subplots()\n",
                "sns.heatmap(rmse_df, cbar=False, annot=True, fmt=\".4g\")"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "The calculated RMSE scores can be visualized to comparatively study how model performance is affected by different parameters."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "It can be seen from this visualization that RMSE first decreases and then increases as rank increases, due to overfitting. When the rank equals 20 and the regularization parameter equals 0.1, the model achieves the lowest RMSE score."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### 3.5 Top K recommendation"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "#### 3.5.1 Top k for all users (items)"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 20,
            "metadata": {},
            "outputs": [],
            "source": [
                "dfs_rec = model.recommendForAllUsers(10)"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 21,
            "metadata": {},
            "outputs": [
                {
                    "name": "stderr",
                    "output_type": "stream",
                    "text": [
                        "[Stage 2198:>                                                       (0 + 1) / 1]\r"
                    ]
                },
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "+------+--------------------+\n",
                        "|UserId|     recommendations|\n",
                        "+------+--------------------+\n",
                        "|     1|[{1536, 3.8911996...|\n",
                        "|     3|[{1536, 3.106386}...|\n",
                        "|     5|[{1536, 3.1345377...|\n",
                        "|     6|[{1536, 3.735431}...|\n",
                        "|     9|[{1536, 4.2483497...|\n",
                        "|    12|[{1536, 4.44719},...|\n",
                        "|    13|[{1536, 3.3997424...|\n",
                        "|    15|[{1536, 3.1361642...|\n",
                        "|    16|[{1536, 4.565808}...|\n",
                        "|    17|[{1536, 3.0498183...|\n",
                        "+------+--------------------+\n",
                        "only showing top 10 rows\n",
                        "\n"
                    ]
                },
                {
                    "name": "stderr",
                    "output_type": "stream",
                    "text": [
                        "\r\n",
                        "                                                                                \r"
                    ]
                }
            ],
            "source": [
                "dfs_rec.show(10)"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "#### 3.5.2 Top k for a selected set of users (items)"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 22,
            "metadata": {},
            "outputs": [],
            "source": [
                "users = dfs_train.select(als.getUserCol()).distinct().limit(3)\n",
                "\n",
                "dfs_rec_subset = model.recommendForUserSubset(users, 10)"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 23,
            "metadata": {},
            "outputs": [
                {
                    "name": "stderr",
                    "output_type": "stream",
                    "text": [
                        "[Stage 2228:=================================================>   (93 + 2) / 100]\r"
                    ]
                },
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": [
                        "+------+--------------------+\n",
                        "|UserId|     recommendations|\n",
                        "+------+--------------------+\n",
                        "|   471|[{1536, 3.3287532...|\n",
                        "|   463|[{1536, 3.1125846...|\n",
                        "|   148|[{1536, 3.907574}...|\n",
                        "+------+--------------------+\n",
                        "\n"
                    ]
                },
                {
                    "name": "stderr",
                    "output_type": "stream",
                    "text": [
                        "\r\n",
                        "                                                                                \r"
                    ]
                }
            ],
            "source": [
                "dfs_rec_subset.show(10)"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "#### 3.5.3 Run-time considerations for top-k recommendations\n",
                "\n",
                "It is worth noting that usually computing the top-k recommendations for all users is the bottleneck of the whole pipeline (model training and scoring) of an ALS based recommendation system. This is because\n",
                "* Getting the top k from all user-item pairs requires a cross join which is usually very computationally expensive. \n",
                "* Inner products of user-item pairs are calculated individually instead of leveraging matrix block multiplication features which are available in certain contemporary computing acceleration libraries (e.g., BLAS).\n",
                "\n",
                "More details about possible optimizations of the top k recommendations in Spark can be found [here](https://engineeringblog.yelp.com/2018/05/scaling-collaborative-filtering-with-pyspark.html)."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 24,
            "metadata": {},
            "outputs": [],
            "source": [
                "# cleanup spark instance\n",
                "spark.stop()"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## References"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "1. Yehuda Koren, Robert Bell, and Chris Volinsky, \"Matrix Factorization Techniques for Recommender Systems\n",
                "\", ACM Computer, Vol. 42, Issue 8, pp 30-37, Aug., 2009.\n",
                "2. Yifan Hu, Yehuda Koren, and Chris Volinsky, \"Collaborative Filtering for Implicit Feedback Datasets\n",
                "\", Proc. IEEE ICDM, 2008, Dec, Pisa, Italy.\n",
                "3. Apache Spark. url: https://spark.apache.org/docs/latest/ml-collaborative-filtering.html\n",
                "4. Seaborn. url: https://seaborn.pydata.org/\n",
                "5. Scaling collaborative filtering with PySpark. url: https://engineeringblog.yelp.com/2018/05/scaling-collaborative-filtering-with-pyspark.html\n",
                "6. Matrix Completion via Alternating Least Square (ALS). url: http://stanford.edu/~rezab/classes/cme323/S15/notes/lec14.pdf"
            ]
        }
    ],
    "metadata": {
        "celltoolbar": "Tags",
        "interpreter": {
            "hash": "7ec2189bea0434770dca7423a25e631e1cca9c4e2b4ff137a82f4dff32ac9607"
        },
        "kernelspec": {
            "display_name": "Python 3 (ipykernel)",
            "language": "python",
            "name": "python3"
        },
        "language_info": {
            "codemirror_mode": {
                "name": "ipython",
                "version": 3
            },
            "file_extension": ".py",
            "mimetype": "text/x-python",
            "name": "python",
            "nbconvert_exporter": "python",
            "pygments_lexer": "ipython3",
            "version": "3.8.0"
        }
    },
    "nbformat": 4,
    "nbformat_minor": 2
}