lightgcn_pyg.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "accelerator": "GPU",
    "colab": {
      "name": "lightgcn_pyg.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/HikaruHotta/945c6f5e48b544a3333cade93d5d061d/lightgcn_pyg.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lxoenua1-u5r"
      },
      "source": [
        "# Install required packages.\n",
        "%%capture\n",
        "!pip install torch-scatter -f https://data.pyg.org/whl/torch-1.10.0+cu111.html\n",
        "!pip install torch-sparse -f https://data.pyg.org/whl/torch-1.10.0+cu111.html\n",
        "!pip install torch-geometric\n",
        "!pip install -q git+https://github.com/snap-stanford/deepsnap.git\n",
        "!pip install -U -q PyDrive"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rWkNAZvtNQ6R"
      },
      "source": [
        "# Implementing a Recommender System using LightGCN\n",
        "\n",
        "In this colab, we explain how to set up a graph recommender system using the [LighGCN](https://arxiv.org/abs/2002.02126) model. Specifically, we apply LightGCN to a movie recommendation task using [PyTorch](https://pytorch.org/) and [PyTorch Geometric](https://pytorch-geometric.readthedocs.io/en/latest/).\n",
        "\n",
        "We use the [MovieLens](https://grouplens.org/datasets/movielens/) (*small*) dataset which has 100,000 ratings applied to 9,000 movies by 600 users. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5OBSacx6Q03m"
      },
      "source": [
        "# import required modules\n",
        "import random\n",
        "from tqdm import tqdm\n",
        "import pandas as pd\n",
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "from sklearn.model_selection import train_test_split\n",
        "\n",
        "import torch\n",
        "from torch import nn, optim, Tensor\n",
        "\n",
        "from torch_sparse import SparseTensor, matmul\n",
        "\n",
        "from torch_geometric.utils import structured_negative_sampling\n",
        "from torch_geometric.data import download_url, extract_zip\n",
        "from torch_geometric.nn.conv.gcn_conv import gcn_norm\n",
        "from torch_geometric.nn.conv import MessagePassing\n",
        "from torch_geometric.typing import Adj"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8mZ6-zPxPklE"
      },
      "source": [
        "# Loading the Dataset\n",
        "\n",
        "We load the dataset and set ratings >=4 on a 0.5 ~ 5 scale as an edge between users and movies.\n",
        "\n",
        "We split the edges of the graph using a 80/10/10 train/validation/test split."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "6cRC_IazQ4Oj",
        "outputId": "569f4157-5808-4765-845d-76b0e5048fac"
      },
      "source": [
        "# download the dataset\n",
        "url = 'https://files.grouplens.org/datasets/movielens/ml-latest-small.zip'\n",
        "extract_zip(download_url(url, '.'), '.')\n",
        "\n",
        "movie_path = './ml-latest-small/movies.csv'\n",
        "rating_path = './ml-latest-small/ratings.csv'"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "Downloading https://files.grouplens.org/datasets/movielens/ml-latest-small.zip\n",
            "Extracting ./ml-latest-small.zip\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "o2P3zYR8Q8EX"
      },
      "source": [
        "# load user and movie nodes\n",
        "def load_node_csv(path, index_col):\n",
        "    \"\"\"Loads csv containing node information\n",
        "\n",
        "    Args:\n",
        "        path (str): path to csv file\n",
        "        index_col (str): column name of index column\n",
        "\n",
        "    Returns:\n",
        "        dict: mapping of csv row to node id\n",
        "    \"\"\"\n",
        "    df = pd.read_csv(path, index_col=index_col)\n",
        "    mapping = {index: i for i, index in enumerate(df.index.unique())}\n",
        "    return mapping\n",
        "\n",
        "\n",
        "user_mapping = load_node_csv(rating_path, index_col='userId')\n",
        "movie_mapping = load_node_csv(movie_path, index_col='movieId')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BkJzQlxSRDEq"
      },
      "source": [
        "# load edges between users and movies\n",
        "def load_edge_csv(path, src_index_col, src_mapping, dst_index_col, dst_mapping, link_index_col, rating_threshold=4):\n",
        "    \"\"\"Loads csv containing edges between users and items\n",
        "\n",
        "    Args:\n",
        "        path (str): path to csv file\n",
        "        src_index_col (str): column name of users\n",
        "        src_mapping (dict): mapping between row number and user id\n",
        "        dst_index_col (str): column name of items\n",
        "        dst_mapping (dict): mapping between row number and item id\n",
        "        link_index_col (str): column name of user item interaction\n",
        "        rating_threshold (int, optional): Threshold to determine positivity of edge. Defaults to 4.\n",
        "\n",
        "    Returns:\n",
        "        torch.Tensor: 2 by N matrix containing the node ids of N user-item edges\n",
        "    \"\"\"\n",
        "    df = pd.read_csv(path)\n",
        "    edge_index = None\n",
        "    src = [src_mapping[index] for index in df[src_index_col]]\n",
        "    dst = [dst_mapping[index] for index in df[dst_index_col]]\n",
        "    edge_attr = torch.from_numpy(df[link_index_col].values).view(-1, 1).to(torch.long) >= rating_threshold\n",
        "\n",
        "\n",
        "    edge_index = [[], []]\n",
        "    for i in range(edge_attr.shape[0]):\n",
        "        if edge_attr[i]:\n",
        "            edge_index[0].append(src[i])\n",
        "            edge_index[1].append(dst[i])\n",
        "\n",
        "    return torch.tensor(edge_index)\n",
        "\n",
        "\n",
        "edge_index = load_edge_csv(\n",
        "    rating_path,\n",
        "    src_index_col='userId',\n",
        "    src_mapping=user_mapping,\n",
        "    dst_index_col='movieId',\n",
        "    dst_mapping=movie_mapping,\n",
        "    link_index_col='rating',\n",
        "    rating_threshold=4,\n",
        ")"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wIueYZfaT6_H"
      },
      "source": [
        "# split the edges of the graph using a 80/10/10 train/validation/test split\n",
        "num_users, num_movies = len(user_mapping), len(movie_mapping)\n",
        "num_interactions = edge_index.shape[1]\n",
        "all_indices = [i for i in range(num_interactions)]\n",
        "\n",
        "train_indices, test_indices = train_test_split(\n",
        "    all_indices, test_size=0.2, random_state=1)\n",
        "val_indices, test_indices = train_test_split(\n",
        "    test_indices, test_size=0.5, random_state=1)\n",
        "\n",
        "train_edge_index = edge_index[:, train_indices]\n",
        "val_edge_index = edge_index[:, val_indices]\n",
        "test_edge_index = edge_index[:, test_indices]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "U5yKILBJUAN6"
      },
      "source": [
        "# convert edge indices into Sparse Tensors: https://pytorch-geometric.readthedocs.io/en/latest/notes/sparse_tensor.html\n",
        "train_sparse_edge_index = SparseTensor(row=train_edge_index[0], col=train_edge_index[1], sparse_sizes=(\n",
        "    num_users + num_movies, num_users + num_movies))\n",
        "val_sparse_edge_index = SparseTensor(row=val_edge_index[0], col=val_edge_index[1], sparse_sizes=(\n",
        "    num_users + num_movies, num_users + num_movies))\n",
        "test_sparse_edge_index = SparseTensor(row=test_edge_index[0], col=test_edge_index[1], sparse_sizes=(\n",
        "    num_users + num_movies, num_users + num_movies))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KqKI1VduKcwf"
      },
      "source": [
        "# function which random samples a mini-batch of positive and negative samples\n",
        "def sample_mini_batch(batch_size, edge_index):\n",
        "    \"\"\"Randomly samples indices of a minibatch given an adjacency matrix\n",
        "\n",
        "    Args:\n",
        "        batch_size (int): minibatch size\n",
        "        edge_index (torch.Tensor): 2 by N list of edges\n",
        "\n",
        "    Returns:\n",
        "        tuple: user indices, positive item indices, negative item indices\n",
        "    \"\"\"\n",
        "    edges = structured_negative_sampling(edge_index)\n",
        "    edges = torch.stack(edges, dim=0)\n",
        "    indices = random.choices(\n",
        "        [i for i in range(edges[0].shape[0])], k=batch_size)\n",
        "    batch = edges[:, indices]\n",
        "    user_indices, pos_item_indices, neg_item_indices = batch[0], batch[1], batch[2]\n",
        "    return user_indices, pos_item_indices, neg_item_indices"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JOB5kDmtUrUY"
      },
      "source": [
        "# Implementing LightGCN\n",
        "\n",
        "## Light Graph Convolution\n",
        "Between each layer, LightGCN uses the following propagation rule for user and item embeddings.\n",
        "\n",
        "\\begin{equation}\n",
        "e_u^{(k+1)} = \\sum_{i \\in N_u} \\frac{1}{\\sqrt{|N_u|}\\sqrt{|N_i|}} e_i^{(k)} \\quad e_i^{(k+1)} = \\sum_{u \\in N_i} \\frac{1}{\\sqrt{|N_i|}\\sqrt{|N_u|}} e_u^{(k)}\n",
        "\\end{equation}\n",
        "\n",
        "$N_u$: the set of all neighbors of user $u$ (items liked by $u$)\n",
        "\n",
        "$N_i$: the set of all neighbors of item $i$ (users who liked $i$)\n",
        "\n",
        "$e_u^{(k)}$ : k-th layer user embedding\n",
        "\n",
        "$e_i^{(k)}$ : k-th layer item embedding\n",
        "\n",
        "\n",
        "\n",
        "## Layer Combination and Model Prediction\n",
        "The only trainable parameters of LightGCN are the 0-th layer embeddings $e_u^{(0)}$ and $e_i^{(0)}$ for each user and item. We combine the embeddings obtained at each layer of propagation to form the final embeddings for all user and item, $e_u$ and $e_i$ via the follwing equation.\n",
        "\n",
        "\n",
        "\\begin{equation}\n",
        "e_u = \\sum_{k = 0}^K \\alpha_k e_u^{(k)} \\quad e_i = \\sum_{k = 0}^K \\alpha_k e_i^{(k)}\n",
        "\\end{equation}\n",
        "\n",
        "$\\alpha_k$ : hyperparameter which weights the contribution of the k-th layer embedding to the final embedding\n",
        "\n",
        "The model prediction is obtained by taking the inner product of the final user and item embeddings.\n",
        "\n",
        "\\begin{equation}\n",
        "\\hat{y}_{ui} = e_u^Te_i\n",
        "\\end{equation}\n",
        "\n",
        "## Matrix Form\n",
        "In our implementation, we utilize the matrix form of LightGCN. We perform multi-scale diffusion to obtain the final embedding, which sums embeddings diffused across multi-hop scales. \n",
        "\n",
        "\\begin{equation}\n",
        "E^{(K)} = \\alpha_0 E^{(0)} + \\alpha_1 \\tilde{A}^1 E^{(0)} + \\alpha_2 \\tilde{A}^2 E^{(0)} + \\cdot \\cdot \\cdot + \\alpha_K \\tilde{A}^K \\tilde{A} E^{(0)}\n",
        "\\end{equation}\n",
        "\n",
        "$E^{(0)} \\in \\mathcal{R}^{(M + N)} \\times T$ : stacked initial item and user embeddings where $M$, $N$, and $T$ denote the number of users, number of items, and the dimension of each embedding respectively\n",
        "\n",
        "$\\tilde{A} = D^{-\\frac{1}{2}}AD^{-\\frac{1}{2}}$ : symmetrically normalized adjacency matrix\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "o9GvYg9ehDOX"
      },
      "source": [
        "# defines LightGCN model\n",
        "class LightGCN(MessagePassing):\n",
        "    \"\"\"LightGCN Model as proposed in https://arxiv.org/abs/2002.02126\n",
        "    \"\"\"\n",
        "\n",
        "    def __init__(self, num_users, num_items, embedding_dim=64, K=3, add_self_loops=False):\n",
        "        \"\"\"Initializes LightGCN Model\n",
        "\n",
        "        Args:\n",
        "            num_users (int): Number of users\n",
        "            num_items (int): Number of items\n",
        "            embedding_dim (int, optional): Dimensionality of embeddings. Defaults to 8.\n",
        "            K (int, optional): Number of message passing layers. Defaults to 3.\n",
        "            add_self_loops (bool, optional): Whether to add self loops for message passing. Defaults to False.\n",
        "        \"\"\"\n",
        "        super().__init__()\n",
        "        self.num_users, self.num_items = num_users, num_items\n",
        "        self.embedding_dim, self.K = embedding_dim, K\n",
        "        self.add_self_loops = add_self_loops\n",
        "\n",
        "        self.users_emb = nn.Embedding(\n",
        "            num_embeddings=self.num_users, embedding_dim=self.embedding_dim) # e_u^0\n",
        "        self.items_emb = nn.Embedding(\n",
        "            num_embeddings=self.num_items, embedding_dim=self.embedding_dim) # e_i^0\n",
        "\n",
        "        nn.init.normal_(self.users_emb.weight, std=0.1)\n",
        "        nn.init.normal_(self.items_emb.weight, std=0.1)\n",
        "\n",
        "    def forward(self, edge_index: SparseTensor):\n",
        "        \"\"\"Forward propagation of LightGCN Model.\n",
        "\n",
        "        Args:\n",
        "            edge_index (SparseTensor): adjacency matrix\n",
        "\n",
        "        Returns:\n",
        "            tuple (Tensor): e_u_k, e_u_0, e_i_k, e_i_0\n",
        "        \"\"\"\n",
        "        # compute \\tilde{A}: symmetrically normalized adjacency matrix\n",
        "        edge_index_norm = gcn_norm(\n",
        "            edge_index, add_self_loops=self.add_self_loops)\n",
        "\n",
        "        emb_0 = torch.cat([self.users_emb.weight, self.items_emb.weight]) # E^0\n",
        "        embs = [emb_0]\n",
        "        emb_k = emb_0\n",
        "\n",
        "        # multi-scale diffusion\n",
        "        for i in range(self.K):\n",
        "            emb_k = self.propagate(edge_index_norm, x=emb_k)\n",
        "            embs.append(emb_k)\n",
        "\n",
        "        embs = torch.stack(embs, dim=1)\n",
        "        emb_final = torch.mean(embs, dim=1) # E^K\n",
        "\n",
        "        users_emb_final, items_emb_final = torch.split(\n",
        "            emb_final, [self.num_users, self.num_items]) # splits into e_u^K and e_i^K\n",
        "\n",
        "        # returns e_u^K, e_u^0, e_i^K, e_i^0\n",
        "        return users_emb_final, self.users_emb.weight, items_emb_final, self.items_emb.weight\n",
        "\n",
        "    def message(self, x_j: Tensor) -> Tensor:\n",
        "        return x_j\n",
        "\n",
        "    def message_and_aggregate(self, adj_t: SparseTensor, x: Tensor) -> Tensor:\n",
        "        # computes \\tilde{A} @ x\n",
        "        return matmul(adj_t, x)\n",
        "\n",
        "model = LightGCN(num_users, num_movies)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "My8eqloiBccE"
      },
      "source": [
        "# Loss Function\n",
        "\n",
        "\n",
        "\n",
        "We utilize a Bayesian Personalized Ranking (BPR) loss, a pairwise objective which encourages the predictions of positive samples to be higher than negative samples for each user.\n",
        "\n",
        "\\begin{equation}\n",
        "L_{BPR} = -\\sum_{u = 1}^M \\sum_{i \\in N_u} \\sum_{j \\notin N_u} \\ln{\\sigma(\\hat{y}_{ui} - \\hat{y}_{uj})} + \\lambda ||E^{(0)}||^2 \n",
        "\\end{equation}\n",
        "\n",
        "$\\hat{y}_{uj}$: predicted score of a positive sample\n",
        "\n",
        "$\\hat{y}_{uj}$: predicted score of a negative sample\n",
        "\n",
        "$\\lambda$: hyperparameter which controls the L2 regularization strength"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QmPs1xS-BYfe"
      },
      "source": [
        "def bpr_loss(users_emb_final, users_emb_0, pos_items_emb_final, pos_items_emb_0, neg_items_emb_final, neg_items_emb_0, lambda_val):\n",
        "    \"\"\"Bayesian Personalized Ranking Loss as described in https://arxiv.org/abs/1205.2618\n",
        "\n",
        "    Args:\n",
        "        users_emb_final (torch.Tensor): e_u_k\n",
        "        users_emb_0 (torch.Tensor): e_u_0\n",
        "        pos_items_emb_final (torch.Tensor): positive e_i_k\n",
        "        pos_items_emb_0 (torch.Tensor): positive e_i_0\n",
        "        neg_items_emb_final (torch.Tensor): negative e_i_k\n",
        "        neg_items_emb_0 (torch.Tensor): negative e_i_0\n",
        "        lambda_val (float): lambda value for regularization loss term\n",
        "\n",
        "    Returns:\n",
        "        torch.Tensor: scalar bpr loss value\n",
        "    \"\"\"\n",
        "    reg_loss = lambda_val * (users_emb_0.norm(2).pow(2) +\n",
        "                             pos_items_emb_0.norm(2).pow(2) +\n",
        "                             neg_items_emb_0.norm(2).pow(2)) # L2 loss\n",
        "\n",
        "    pos_scores = torch.mul(users_emb_final, pos_items_emb_final)\n",
        "    pos_scores = torch.sum(pos_scores, dim=-1) # predicted scores of positive samples\n",
        "    neg_scores = torch.mul(users_emb_final, neg_items_emb_final)\n",
        "    neg_scores = torch.sum(neg_scores, dim=-1) # predicted scores of negative samples\n",
        "\n",
        "    loss = -torch.mean(torch.nn.functional.softplus(pos_scores - neg_scores)) + reg_loss\n",
        "\n",
        "    return loss"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CS7HVr3qLQGx"
      },
      "source": [
        "# Evaluation Metrics\n",
        "\n",
        "We evalaluate our model using the following metrics\n",
        "\n",
        "\\begin{equation}\n",
        "\\text{Recall} = \\frac{TP}{TP + FP}\n",
        "\\end{equation}\n",
        "\n",
        "\\begin{equation}\n",
        "\\text{Precision} = \\frac{TP}{TP + FN}\n",
        "\\end{equation}\n",
        "\n",
        "**Dicounted Cumulative Gain (DCG)** at rank position p is defined as:\n",
        "\n",
        "\\begin{equation}\n",
        "\\text{DCG}_\\text{p} = \\sum_{i = 1}^p \\frac{2^{rel_i} - 1}{\\log_2{(i + 1)}}\n",
        "\\end{equation}\n",
        "\n",
        "p: a particular rank position\n",
        "\n",
        "$rel_i \\in \\{0, 1\\}$ : graded relevance of the result at position $i$\n",
        "\n",
        "**Idealised Dicounted Cumulative Gain (IDCG)**, namely the maximum possible DCG, at rank position $p$ is defined as:\n",
        "\n",
        "\\begin{equation}\n",
        "\\text{IDCG}_\\text{p} = \\sum_{i = 1}^{|REL_p|} \\frac{2^{rel_i} - 1}{\\log_2{(i + 1)}}\n",
        "\\end{equation}\n",
        "\n",
        "$|REL_p|$ : list of items ordered by their relevance up to position p\n",
        "\n",
        "**Normalized Dicounted Cumulative Gain (NDCG)** at rank position $p$ is defined as:\n",
        "\n",
        "\\begin{equation}\n",
        "\\text{nDCG}_\\text{p} = \\frac{\\text{DCG}_p}{\\text{nDCG}_p}\n",
        "\\end{equation}\n",
        "\n",
        "Specifically, we use the metrics recall@K, precision@K, and NDCG@K. @K indicates that these metrics are computed on the top K recommendations."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nHO2gdhRSwzJ"
      },
      "source": [
        "# helper function to get N_u\n",
        "def get_user_positive_items(edge_index):\n",
        "    \"\"\"Generates dictionary of positive items for each user\n",
        "\n",
        "    Args:\n",
        "        edge_index (torch.Tensor): 2 by N list of edges\n",
        "\n",
        "    Returns:\n",
        "        dict: dictionary of positive items for each user\n",
        "    \"\"\"\n",
        "    user_pos_items = {}\n",
        "    for i in range(edge_index.shape[1]):\n",
        "        user = edge_index[0][i].item()\n",
        "        item = edge_index[1][i].item()\n",
        "        if user not in user_pos_items:\n",
        "            user_pos_items[user] = []\n",
        "        user_pos_items[user].append(item)\n",
        "    return user_pos_items"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8We4BTtfS4NV"
      },
      "source": [
        "# computes recall@K and precision@K\n",
        "def RecallPrecision_ATk(groundTruth, r, k):\n",
        "    \"\"\"Computers recall @ k and precision @ k\n",
        "\n",
        "    Args:\n",
        "        groundTruth (list): list of lists containing highly rated items of each user\n",
        "        r (list): list of lists indicating whether each top k item recommended to each user\n",
        "            is a top k ground truth item or not\n",
        "        k (intg): determines the top k items to compute precision and recall on\n",
        "\n",
        "    Returns:\n",
        "        tuple: recall @ k, precision @ k\n",
        "    \"\"\"\n",
        "    num_correct_pred = torch.sum(r, dim=-1)  # number of correctly predicted items per user\n",
        "    # number of items liked by each user in the test set\n",
        "    user_num_liked = torch.Tensor([len(groundTruth[i])\n",
        "                                  for i in range(len(groundTruth))])\n",
        "    recall = torch.mean(num_correct_pred / user_num_liked)\n",
        "    precision = torch.mean(num_correct_pred) / k\n",
        "    return recall.item(), precision.item()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9v4A3Ek4TE02"
      },
      "source": [
        "# computes NDCG@K\n",
        "def NDCGatK_r(groundTruth, r, k):\n",
        "    \"\"\"Computes Normalized Discounted Cumulative Gain (NDCG) @ k\n",
        "\n",
        "    Args:\n",
        "        groundTruth (list): list of lists containing highly rated items of each user\n",
        "        r (list): list of lists indicating whether each top k item recommended to each user\n",
        "            is a top k ground truth item or not\n",
        "        k (int): determines the top k items to compute ndcg on\n",
        "\n",
        "    Returns:\n",
        "        float: ndcg @ k\n",
        "    \"\"\"\n",
        "    assert len(r) == len(groundTruth)\n",
        "\n",
        "    test_matrix = torch.zeros((len(r), k))\n",
        "\n",
        "    for i, items in enumerate(groundTruth):\n",
        "        length = min(len(items), k)\n",
        "        test_matrix[i, :length] = 1\n",
        "    max_r = test_matrix\n",
        "    idcg = torch.sum(max_r * 1. / torch.log2(torch.arange(2, k + 2)), axis=1)\n",
        "    dcg = r * (1. / torch.log2(torch.arange(2, k + 2)))\n",
        "    dcg = torch.sum(dcg, axis=1)\n",
        "    idcg[idcg == 0.] = 1.\n",
        "    ndcg = dcg / idcg\n",
        "    ndcg[torch.isnan(ndcg)] = 0.\n",
        "    return torch.mean(ndcg).item()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "x6_741LlTMwI"
      },
      "source": [
        "# wrapper function to get evaluation metrics\n",
        "def get_metrics(model, edge_index, exclude_edge_indices, k):\n",
        "    \"\"\"Computes the evaluation metrics: recall, precision, and ndcg @ k\n",
        "\n",
        "    Args:\n",
        "        model (LighGCN): lightgcn model\n",
        "        edge_index (torch.Tensor): 2 by N list of edges for split to evaluate\n",
        "        exclude_edge_indices ([type]): 2 by N list of edges for split to discount from evaluation\n",
        "        k (int): determines the top k items to compute metrics on\n",
        "\n",
        "    Returns:\n",
        "        tuple: recall @ k, precision @ k, ndcg @ k\n",
        "    \"\"\"\n",
        "    user_embedding = model.users_emb.weight\n",
        "    item_embedding = model.items_emb.weight\n",
        "\n",
        "    # get ratings between every user and item - shape is num users x num movies\n",
        "    rating = torch.matmul(user_embedding, item_embedding.T)\n",
        "\n",
        "    for exclude_edge_index in exclude_edge_indices:\n",
        "        # gets all the positive items for each user from the edge index\n",
        "        user_pos_items = get_user_positive_items(exclude_edge_index)\n",
        "        # get coordinates of all edges to exclude\n",
        "        exclude_users = []\n",
        "        exclude_items = []\n",
        "        for user, items in user_pos_items.items():\n",
        "            exclude_users.extend([user] * len(items))\n",
        "            exclude_items.extend(items)\n",
        "\n",
        "        # set ratings of excluded edges to large negative value\n",
        "        rating[exclude_users, exclude_items] = -(1 << 10)\n",
        "\n",
        "    # get the top k recommended items for each user\n",
        "    _, top_K_items = torch.topk(rating, k=k)\n",
        "\n",
        "    # get all unique users in evaluated split\n",
        "    users = edge_index[0].unique()\n",
        "\n",
        "    test_user_pos_items = get_user_positive_items(edge_index)\n",
        "\n",
        "    # convert test user pos items dictionary into a list\n",
        "    test_user_pos_items_list = [\n",
        "        test_user_pos_items[user.item()] for user in users]\n",
        "\n",
        "    # determine the correctness of topk predictions\n",
        "    r = []\n",
        "    for user in users:\n",
        "        ground_truth_items = test_user_pos_items[user.item()]\n",
        "        label = list(map(lambda x: x in ground_truth_items, top_K_items[user]))\n",
        "        r.append(label)\n",
        "    r = torch.Tensor(np.array(r).astype('float'))\n",
        "\n",
        "    recall, precision = RecallPrecision_ATk(test_user_pos_items_list, r, k)\n",
        "    ndcg = NDCGatK_r(test_user_pos_items_list, r, k)\n",
        "\n",
        "    return recall, precision, ndcg"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yr_qESXASsVw"
      },
      "source": [
        "# wrapper function to evaluate model\n",
        "def evaluation(model, edge_index, sparse_edge_index, exclude_edge_indices, k, lambda_val):\n",
        "    \"\"\"Evaluates model loss and metrics including recall, precision, ndcg @ k\n",
        "\n",
        "    Args:\n",
        "        model (LighGCN): lightgcn model\n",
        "        edge_index (torch.Tensor): 2 by N list of edges for split to evaluate\n",
        "        sparse_edge_index (sparseTensor): sparse adjacency matrix for split to evaluate\n",
        "        exclude_edge_indices ([type]): 2 by N list of edges for split to discount from evaluation\n",
        "        k (int): determines the top k items to compute metrics on\n",
        "        lambda_val (float): determines lambda for bpr loss\n",
        "\n",
        "    Returns:\n",
        "        tuple: bpr loss, recall @ k, precision @ k, ndcg @ k\n",
        "    \"\"\"\n",
        "    # get embeddings\n",
        "    users_emb_final, users_emb_0, items_emb_final, items_emb_0 = model.forward(\n",
        "        sparse_edge_index)\n",
        "    edges = structured_negative_sampling(\n",
        "        edge_index, contains_neg_self_loops=False)\n",
        "    user_indices, pos_item_indices, neg_item_indices = edges[0], edges[1], edges[2]\n",
        "    users_emb_final, users_emb_0 = users_emb_final[user_indices], users_emb_0[user_indices]\n",
        "    pos_items_emb_final, pos_items_emb_0 = items_emb_final[\n",
        "        pos_item_indices], items_emb_0[pos_item_indices]\n",
        "    neg_items_emb_final, neg_items_emb_0 = items_emb_final[\n",
        "        neg_item_indices], items_emb_0[neg_item_indices]\n",
        "\n",
        "    loss = bpr_loss(users_emb_final, users_emb_0, pos_items_emb_final, pos_items_emb_0,\n",
        "                    neg_items_emb_final, neg_items_emb_0, lambda_val).item()\n",
        "\n",
        "    recall, precision, ndcg = get_metrics(\n",
        "        model, edge_index, exclude_edge_indices, k)\n",
        "\n",
        "    return loss, recall, precision, ndcg"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NYw1cUgPTjws"
      },
      "source": [
        "# Training\n",
        "\n",
        "Your test set performance should be in line with the following (*K=20*):\n",
        "\n",
        "*Recall@K: 0.13, Precision@K: 0.045, NDCG@K: 0.10*"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MQL2W-NQTeFd"
      },
      "source": [
        "# define contants\n",
        "ITERATIONS = 10000\n",
        "BATCH_SIZE = 1024\n",
        "LR = 1e-3\n",
        "ITERS_PER_EVAL = 200\n",
        "ITERS_PER_LR_DECAY = 200\n",
        "K = 20\n",
        "LAMBDA = 1e-6"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "49JDkBtKTfE-",
        "outputId": "1df57d45-a5a6-4d0e-9785-14c1e80ae71a"
      },
      "source": [
        "# setup\n",
        "device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')\n",
        "print(f\"Using device {device}.\")\n",
        "\n",
        "\n",
        "model = model.to(device)\n",
        "model.train()\n",
        "\n",
        "optimizer = optim.Adam(model.parameters(), lr=LR)\n",
        "scheduler = optim.lr_scheduler.ExponentialLR(optimizer, gamma=0.95)\n",
        "\n",
        "edge_index = edge_index.to(device)\n",
        "train_edge_index = train_edge_index.to(device)\n",
        "train_sparse_edge_index = train_sparse_edge_index.to(device)\n",
        "\n",
        "val_edge_index = val_edge_index.to(device)\n",
        "val_sparse_edge_index = val_sparse_edge_index.to(device)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Using device cuda.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "wYjrDp1w-hiP",
        "outputId": "3f95ff0e-c5d4-4ef3-c0b1-3c07c1552e7f"
      },
      "source": [
        "# training loop\n",
        "\n",
        "train_losses = []\n",
        "val_losses = []\n",
        "\n",
        "for iter in range(ITERATIONS):\n",
        "    # forward propagation\n",
        "    users_emb_final, users_emb_0, items_emb_final, items_emb_0 = model.forward(\n",
        "        train_sparse_edge_index)\n",
        "\n",
        "    # mini batching\n",
        "    user_indices, pos_item_indices, neg_item_indices = sample_mini_batch(\n",
        "        BATCH_SIZE, train_edge_index)\n",
        "    user_indices, pos_item_indices, neg_item_indices = user_indices.to(\n",
        "        device), pos_item_indices.to(device), neg_item_indices.to(device)\n",
        "    users_emb_final, users_emb_0 = users_emb_final[user_indices], users_emb_0[user_indices]\n",
        "    pos_items_emb_final, pos_items_emb_0 = items_emb_final[\n",
        "        pos_item_indices], items_emb_0[pos_item_indices]\n",
        "    neg_items_emb_final, neg_items_emb_0 = items_emb_final[\n",
        "        neg_item_indices], items_emb_0[neg_item_indices]\n",
        "\n",
        "    # loss computation\n",
        "    train_loss = bpr_loss(users_emb_final, users_emb_0, pos_items_emb_final,\n",
        "                          pos_items_emb_0, neg_items_emb_final, neg_items_emb_0, LAMBDA)\n",
        "\n",
        "    optimizer.zero_grad()\n",
        "    train_loss.backward()\n",
        "    optimizer.step()\n",
        "\n",
        "    if iter % ITERS_PER_EVAL == 0:\n",
        "        model.eval()\n",
        "        val_loss, recall, precision, ndcg = evaluation(\n",
        "            model, val_edge_index, val_sparse_edge_index, [train_edge_index], K, LAMBDA)\n",
        "        print(f\"[Iteration {iter}/{ITERATIONS}] train_loss: {round(train_loss.item(), 5)}, val_loss: {round(val_loss, 5)}, val_recall@{K}: {round(recall, 5)}, val_precision@{K}: {round(precision, 5)}, val_ndcg@{K}: {round(ndcg, 5)}\")\n",
        "        train_losses.append(train_loss.item())\n",
        "        val_losses.append(val_loss)\n",
        "        model.train()\n",
        "\n",
        "    if iter % ITERS_PER_LR_DECAY == 0 and iter != 0:\n",
        "        scheduler.step()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[Iteration 0/10000] train_loss: -0.69112, val_loss: -0.68374, val_recall@20: 0.00161, val_precision@20: 0.0009, val_ndcg@20: 0.00125\n",
            "[Iteration 200/10000] train_loss: -0.70072, val_loss: -0.6902, val_recall@20: 0.05163, val_precision@20: 0.01618, val_ndcg@20: 0.03836\n",
            "[Iteration 400/10000] train_loss: -0.89317, val_loss: -0.82984, val_recall@20: 0.14365, val_precision@20: 0.04005, val_ndcg@20: 0.10178\n",
            "[Iteration 600/10000] train_loss: -1.79995, val_loss: -1.54339, val_recall@20: 0.14435, val_precision@20: 0.04259, val_ndcg@20: 0.10322\n",
            "[Iteration 800/10000] train_loss: -3.49128, val_loss: -2.8681, val_recall@20: 0.14737, val_precision@20: 0.04476, val_ndcg@20: 0.10516\n",
            "[Iteration 1000/10000] train_loss: -5.57447, val_loss: -4.47435, val_recall@20: 0.14575, val_precision@20: 0.04485, val_ndcg@20: 0.10477\n",
            "[Iteration 1200/10000] train_loss: -7.60937, val_loss: -6.33453, val_recall@20: 0.14457, val_precision@20: 0.04512, val_ndcg@20: 0.10412\n",
            "[Iteration 1400/10000] train_loss: -9.72321, val_loss: -8.18129, val_recall@20: 0.14758, val_precision@20: 0.04548, val_ndcg@20: 0.10508\n",
            "[Iteration 1600/10000] train_loss: -12.35682, val_loss: -10.17684, val_recall@20: 0.14414, val_precision@20: 0.04476, val_ndcg@20: 0.10299\n",
            "[Iteration 1800/10000] train_loss: -14.44013, val_loss: -12.2623, val_recall@20: 0.14556, val_precision@20: 0.04503, val_ndcg@20: 0.1034\n",
            "[Iteration 2000/10000] train_loss: -17.09245, val_loss: -14.23878, val_recall@20: 0.14424, val_precision@20: 0.04485, val_ndcg@20: 0.10373\n",
            "[Iteration 2200/10000] train_loss: -19.21111, val_loss: -15.98005, val_recall@20: 0.14526, val_precision@20: 0.0453, val_ndcg@20: 0.10443\n",
            "[Iteration 2400/10000] train_loss: -22.51374, val_loss: -18.14113, val_recall@20: 0.14457, val_precision@20: 0.04494, val_ndcg@20: 0.10415\n",
            "[Iteration 2600/10000] train_loss: -24.43242, val_loss: -20.06738, val_recall@20: 0.14579, val_precision@20: 0.04512, val_ndcg@20: 0.10457\n",
            "[Iteration 2800/10000] train_loss: -26.27654, val_loss: -21.99173, val_recall@20: 0.14578, val_precision@20: 0.04521, val_ndcg@20: 0.10468\n",
            "[Iteration 3000/10000] train_loss: -30.05969, val_loss: -23.61742, val_recall@20: 0.14754, val_precision@20: 0.04539, val_ndcg@20: 0.10548\n",
            "[Iteration 3200/10000] train_loss: -30.67489, val_loss: -25.52533, val_recall@20: 0.14602, val_precision@20: 0.0453, val_ndcg@20: 0.1051\n",
            "[Iteration 3400/10000] train_loss: -34.77532, val_loss: -27.26008, val_recall@20: 0.14733, val_precision@20: 0.04521, val_ndcg@20: 0.10517\n",
            "[Iteration 3600/10000] train_loss: -35.58294, val_loss: -28.98993, val_recall@20: 0.1479, val_precision@20: 0.0453, val_ndcg@20: 0.1054\n",
            "[Iteration 3800/10000] train_loss: -37.35663, val_loss: -30.62263, val_recall@20: 0.14661, val_precision@20: 0.04539, val_ndcg@20: 0.10509\n",
            "[Iteration 4000/10000] train_loss: -39.28416, val_loss: -32.10266, val_recall@20: 0.14753, val_precision@20: 0.04539, val_ndcg@20: 0.10542\n",
            "[Iteration 4200/10000] train_loss: -41.50747, val_loss: -33.64888, val_recall@20: 0.14636, val_precision@20: 0.04539, val_ndcg@20: 0.10503\n",
            "[Iteration 4400/10000] train_loss: -42.93468, val_loss: -34.81876, val_recall@20: 0.1469, val_precision@20: 0.04548, val_ndcg@20: 0.10519\n",
            "[Iteration 4600/10000] train_loss: -45.86227, val_loss: -36.24535, val_recall@20: 0.15224, val_precision@20: 0.04593, val_ndcg@20: 0.10648\n",
            "[Iteration 4800/10000] train_loss: -45.33321, val_loss: -37.53897, val_recall@20: 0.14983, val_precision@20: 0.04575, val_ndcg@20: 0.10567\n",
            "[Iteration 5000/10000] train_loss: -47.07096, val_loss: -38.74474, val_recall@20: 0.14741, val_precision@20: 0.04575, val_ndcg@20: 0.1057\n",
            "[Iteration 5200/10000] train_loss: -50.03451, val_loss: -40.00531, val_recall@20: 0.14717, val_precision@20: 0.04566, val_ndcg@20: 0.10548\n",
            "[Iteration 5400/10000] train_loss: -50.09203, val_loss: -41.62997, val_recall@20: 0.14629, val_precision@20: 0.04557, val_ndcg@20: 0.10514\n",
            "[Iteration 5600/10000] train_loss: -53.07259, val_loss: -42.51913, val_recall@20: 0.14707, val_precision@20: 0.04566, val_ndcg@20: 0.10529\n",
            "[Iteration 5800/10000] train_loss: -52.63025, val_loss: -43.57563, val_recall@20: 0.14765, val_precision@20: 0.04593, val_ndcg@20: 0.10562\n",
            "[Iteration 6000/10000] train_loss: -52.31987, val_loss: -44.17801, val_recall@20: 0.14936, val_precision@20: 0.0462, val_ndcg@20: 0.10616\n",
            "[Iteration 6200/10000] train_loss: -54.28507, val_loss: -45.68126, val_recall@20: 0.14887, val_precision@20: 0.04584, val_ndcg@20: 0.10602\n",
            "[Iteration 6400/10000] train_loss: -58.80605, val_loss: -46.39964, val_recall@20: 0.14909, val_precision@20: 0.04602, val_ndcg@20: 0.10593\n",
            "[Iteration 6600/10000] train_loss: -58.40558, val_loss: -47.90079, val_recall@20: 0.14895, val_precision@20: 0.04593, val_ndcg@20: 0.10596\n",
            "[Iteration 6800/10000] train_loss: -58.89854, val_loss: -48.89202, val_recall@20: 0.14922, val_precision@20: 0.04611, val_ndcg@20: 0.1059\n",
            "[Iteration 7000/10000] train_loss: -61.2205, val_loss: -49.39697, val_recall@20: 0.14898, val_precision@20: 0.04593, val_ndcg@20: 0.10575\n",
            "[Iteration 7200/10000] train_loss: -62.91126, val_loss: -49.24725, val_recall@20: 0.14915, val_precision@20: 0.04602, val_ndcg@20: 0.10576\n",
            "[Iteration 7400/10000] train_loss: -62.67969, val_loss: -50.60665, val_recall@20: 0.14916, val_precision@20: 0.04602, val_ndcg@20: 0.10584\n",
            "[Iteration 7600/10000] train_loss: -61.43322, val_loss: -51.59992, val_recall@20: 0.1491, val_precision@20: 0.04602, val_ndcg@20: 0.10584\n",
            "[Iteration 7800/10000] train_loss: -62.50441, val_loss: -52.01427, val_recall@20: 0.1491, val_precision@20: 0.04602, val_ndcg@20: 0.10597\n",
            "[Iteration 8000/10000] train_loss: -62.64954, val_loss: -53.00801, val_recall@20: 0.14916, val_precision@20: 0.04602, val_ndcg@20: 0.10584\n",
            "[Iteration 8200/10000] train_loss: -63.46519, val_loss: -52.97116, val_recall@20: 0.14938, val_precision@20: 0.0462, val_ndcg@20: 0.10595\n",
            "[Iteration 8400/10000] train_loss: -62.74277, val_loss: -53.66493, val_recall@20: 0.1491, val_precision@20: 0.04602, val_ndcg@20: 0.10593\n",
            "[Iteration 8600/10000] train_loss: -68.88041, val_loss: -54.37319, val_recall@20: 0.14916, val_precision@20: 0.04602, val_ndcg@20: 0.10605\n",
            "[Iteration 8800/10000] train_loss: -69.47198, val_loss: -54.55242, val_recall@20: 0.14913, val_precision@20: 0.04602, val_ndcg@20: 0.10583\n",
            "[Iteration 9000/10000] train_loss: -70.36764, val_loss: -54.75371, val_recall@20: 0.14933, val_precision@20: 0.04611, val_ndcg@20: 0.10598\n",
            "[Iteration 9200/10000] train_loss: -68.07756, val_loss: -56.0104, val_recall@20: 0.14913, val_precision@20: 0.04602, val_ndcg@20: 0.10586\n",
            "[Iteration 9400/10000] train_loss: -70.01717, val_loss: -56.17115, val_recall@20: 0.14913, val_precision@20: 0.04602, val_ndcg@20: 0.10598\n",
            "[Iteration 9600/10000] train_loss: -71.47074, val_loss: -56.40413, val_recall@20: 0.14913, val_precision@20: 0.04602, val_ndcg@20: 0.10586\n",
            "[Iteration 9800/10000] train_loss: -69.44392, val_loss: -57.50562, val_recall@20: 0.14933, val_precision@20: 0.04611, val_ndcg@20: 0.10598\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 294
        },
        "id": "nLcdvV5iXBSv",
        "outputId": "9f5ea09b-34ef-4611-fb3d-ba0b6349d26f"
      },
      "source": [
        "iters = [iter * ITERS_PER_EVAL for iter in range(len(train_losses))]\n",
        "plt.plot(iters, train_losses, label='train')\n",
        "plt.plot(iters, val_losses, label='validation')\n",
        "plt.xlabel('iteration')\n",
        "plt.ylabel('loss')\n",
        "plt.title('training and validation loss curves')\n",
        "plt.legend()\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAY0AAAEWCAYAAACaBstRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nOzdd3hUVfrA8e+bQnogBQgkQCiR3kIXUVCUIlJUioqKUuyo6+qirmVd19XVn+sqTYpYARERsGBBQXoJvUNoEmoIJASSQMr5/XEvOEAIE5jJpLyf57kPM7e+d+4wb+4595wjxhiUUkopZ3h5OgCllFIlhyYNpZRSTtOkoZRSymmaNJRSSjlNk4ZSSimnadJQSinlNE0a6hwRGSsiL7l6XU8SkfkiMsQN+90jIp3t1y+IyARn1r2C43QQkW1XGmcB+40VESMiPq7etyrd9AtTSojIHmCIMWbule7DGPOwO9Yt7Ywxb7hqXyJigDhjTKK974VAXVftX6mrpXcaZYT+RalKOrHob5aH6QUoBUTkM6A68K2InBSR5xyKHwaLyB/Ab/a6X4nIIRFJE5EFItLQYT8fi8jr9uuOIpIkIs+IyBEROSgiD1zhuhEi8q2InBCRlSLyuogsKuB8LhfjKBH5XkTSRWS5iNR2WH6ziGy1tx0JyCWOUVVEMkUk3GFecxE5KiK+IlJbRH4TkRR73hciUuES+3pVRD53eH+viOy1t33xgnVbi8hSEUm1P6eRIlLOXrbAXm2dfR37n/1sHbavbxe5pYrIJhHp6exnUxD785gtIsdEJFFEhl4Qc4J9/Q6LyLv2fH8R+dw+z1T72la+xP6ricgMEUm21x95ic/uvGIz+1z/JSKLgQzgWRFJuGDfT4vIbPu1n4i8IyJ/2LGOFZEAe1mkiHxnx3pMRBaKJqFC0w+sFDDG3Av8AdxmjAk2xvzHYfENQH2gi/1+DhAHVAJWA18UsOsooDwQDQwGRolI2BWsOwo4Za9zvz0V5HIxDgD+AYQBicC/wPpRAGYAfwcigZ1A+/wOYIw5ACwF7nCYfTcw3RiTjZVs/g1Uxfr8qgGvXiZuRKQBMAa41942AohxWCUXeNqOrx1wE/CoHdP19jpN7ev45QX79gW+BX7G+myeAL4QEcfiq3w/GydMBZLsmO8E3hCRG+1l/wP+Z4wJBWoD0+z592Nd82r2eT4MZObzmXgD3wF7gVis78hUJ+MC67McBoQAY4G6IhLnsPxuYLL9+k3gGqAZUMc+1sv2smfsc6wIVAZeALQfpcIyxuhUCiZgD9DZ4X0s1n+IWgVsU8Fep7z9/mPgdft1R6wfAB+H9Y8AbQuzLuANZAN1HZa9Dixy8rzyi3GCw/LuwFb79X3AModlgvUjMeQS+x4C/Oaw7j7g+kus2xtYk9/njZVMPrdfvwxMdVgvCDjjeG0u2O9TwDcO7w1Qx+F9RyDJft0BOAR4OSyfArx6uc8mn+Oe/X74YP3o5wIhDsv/DXxsv16AlYgiL9jHg8ASoMllrmE7INnx++Gw7Nxnd2Fc9vv5wGsXbPM58LL9Og5IBwLta3gKqH3BsXfbr18DZjl+vjoVftI7jdJv39kXIuItIm+KyE4ROYH1wwfWX735STHG5Di8zwCCC7luRawfpn0Oyxxfn8fJGA9dIqaqjvs21i/FJY8FfA20E5EqwPVAHrDQjqOyiEwVkf12HJ9z6c/J0YUxnAJSHM7vGruI5JC93zec3O+5fRtj8hzm7cX6a/qsS302l9vvMWNM+iX2Oxjrr/etdhFUD3v+Z8BPwFQROSAi/7Hvhi5UDdh7wfejMC68hpOBu+zXdwMzjTEZWN+1QGCVXQSVCvxozwd4G+vu62cR2SUiI64wnjJNk0bpcanbbMf5dwO9gM5YxQqx9vx8y/1dJBnI4fwimmoFrH81MR503LeISEHHMsYcxyrq6W8fd6qdaMD6MTdAY2MVywy8whgCsYpuzhoDbMV6QioUq4jE2c//AFDtgnL46sB+J7cvaL/hIhKS336NMTuMMXdhFYm9BUwXkSBjTLYx5h/GmAbAtUAPrLu9C+0Dqkv+D2OcwvqhPysqn3Uu/G7/AlQUkWZYyeNs0dRRrDvehsaYCvZU3hgTbJ9HujHmGWNMLaAn8BcRuSn/j0RdiiaN0uMwUOsy64QAp7H+8g3E+mF0K2NMLlY9w6siEigi9cj/h8UVMX4PNBSR2+0fqOHk/yPkaLIdz538+eNzNo6TQJqIRAPPOhnDdKCHiFxnV3C/xvn/z0KAE8BJ+7N45ILtC7qOy7HuHp4Tq7K+I3AbhasfuIgxZh9WMdO/7crtJlh3F58DiMhAEalo3+Gk2pvliUgnEWls11mcwCqGzMvnECuwkumbIhJkH+NsXdNa4HoRqS4i5YHnnYg3G/gK684hHCuJYMc3HviviFSyY48WkS726x4iUsf+YyINq0guv3hVATRplB7/Bv5u35b/9RLrfIpV7LAf2AwsK6LYHse6aziEVaQxBSsx5OeKYzTGHAX6YlWGpmCVdy++zGaz7fUOGWPWOcz/BxCP9ePyPVbicyaGTcBjWAnoIHAcq17lrL9i3dWkY/3AfXnBLl4FPrGvY78L9n0GK0l0w/qrejRwnzFmqzOxXcZdWHd1B4BvgFfMn21+ugKbROQkVqX4AGNMJlZCno6VMLYAv2Nd3/PYfzjchlUx/QfW59HfXvYL1mewHliFVWHujMlYd6NfXVDs9TesIqhldvHfXP5s5xJnvz+J9RDEaGPMPCePp2zy5924UkVDRN4Coowxl3uKSilVzOidhnI7EaknIk3E0hqr6OMbT8ellCo8bSWsikIIVpFUVawy+//DevRRKVXCaPGUUkopp2nxlFJKKaeViuKpyMhIExsb6+kwlFKqRFm1atVRY0zFy6/5p1KRNGJjY0lISLj8ikoppc4Rkb2F3UaLp5RSSjlNk4ZSSimnadJQSinltGJbpyEiXbG6LPDG6u75TQ+HpJQqItnZ2SQlJZGVleXpUEoFf39/YmJi8PXNrxPiwimWScPuAG0UcDNWPzUrRWS2MWazZyNTShWFpKQkQkJCiI2NxepfUF0pYwwpKSkkJSVRs2bNq95fcS2eag0kGmN22Z20TcXqLlspVQZkZWURERGhCcMFRISIiAiX3bUV16QRzfkDryRx/kAziMgwscYtTkhOTi7S4JRS7qcJw3Vc+VkWy+IpZxhjxgHjAFq2bHlFfaHs3ZLAoSVTrBFwRM5N1nsvfAJCKBcUTkBoGMHlIwkJiyAgOBzKx4CXt8vORSmlSorimjT2c/6IazFc/ehkFzm6ez2t/piIlxQu55zwqsCJGjdTpW1fvGt3BB8/V4emlPKg1NRUJk+ezKOPPlqo7bp3787kyZOpUKGCmyLzvGLZYaE96tp24CasZLESuNse4OYiLVu2NFfSIjwvz5BnDAYwBozJw/o4DLm5uaSlHSfteDInU1M4lXaMrPRjnElPxi9pMdfmriJEMjntHUReXBcCmvSGOjdDucDLHFUpdTlbtmyhfv36Hjv+nj176NGjBxs3bjxvfk5ODj4+xfVv7YLl95mKyCpjTMvC7KdYnr0xJkdEHscatN4b+OhSCeNqeHkJXucNz+xYxeNLUEAVqkZVuWi7nNw8ftu4j/ULZ1Ht0K/cvOVnArbOINs/Et+u/4QmA8CruFYXKaUuZ8SIEezcuZNmzZrh6+uLv78/YWFhbN26le3bt9O7d2/27dtHVlYWTz75JMOGDQP+7NLo5MmTdOvWjeuuu44lS5YQHR3NrFmzCAgI8PCZXb1ieadRWFd6p+EKe46eYuryXexJ+ImHcqfQ3CsRE9MGufUdqNLEIzEpVdI5/lX8j283sfnACZfuv0HVUF65reEllzveacyfP59bb72VjRs3nntk9dixY4SHh5OZmUmrVq34/fffiYiIOC9p1KlTh4SEBJo1a0a/fv3o2bMnAwcOdOl5FIar7jT0z+GrFBsZxIhbG/N/I57i43rjeDZ7GOkHtmHG3QDfPwMZxzwdolLqKrVu3fq8Ng7vv/8+TZs2pW3btuzbt48dO3ZctE3NmjVp1qwZAC1atGDPnj1FFa5bFcviqZIoyM+H9+6K54vlkdz4bWue859B34SPkE3fQOdXofm91tNZSqlCKeiOoKgEBQWdez1//nzmzp3L0qVLCQwMpGPHjvm2gfDz+/MBGW9vbzIzM4skVnfTOw0XEhEGtq3Bx4/ewgd+Q7ntzBsc8q0Os5+AqXfDqRRPh6iUckJISAjp6en5LktLSyMsLIzAwEC2bt3KsmXLijg6z9Kk4QaNosvz3RMdqFq3Fe0OP8NXkY9gdvwCY9vD7gWeDk8pdRkRERG0b9+eRo0a8eyzz563rGvXruTk5FC/fn1GjBhB27ZtPRSlZ2hFuBsZY5iwcDdvzNlC3+hj/DvvPbyP7YTrnoZOL4D31XceplRp5OlHbksjrQgvAUSEodfX4n8DmjPjQAT9eYusJvfAonfhoy5wbJenQ1RKqULRpFEEejatyrj7WrDhSDY99vTj+K3jISURxl4PW3/wdHhKKeU0TRpF5MZ6lfn0wdYcSsvitt8i2df/F4isY1WQL/4flIJiQqVU6adJowi1qRXBlKFtOXU6h9sn72Nbty+hQS/45WWY9RjknPZ0iEopVSBNGkWscUx5pj3UDi+Bfh+tY1Xrd+GGEbD2C/i0N5w66ukQlVLqkjRpeEBc5RCmP3wtYYG+DJy4knlVB8MdE2H/Khh/IxzZ4ukQlVIqX5o0PKRaeCBfPXwttSoGMfSTBGbmtIMHfoCcLJhwM2z/2dMhKqWcFBwcDMCBAwe48847812nY8eOXK5pwHvvvUdGRsa59927dyc1NdV1gbqAJg0Pqhjix9RhbWkZG8ZTX67loz0RMPQ3CK8JU/rDkpFaQa5UCVK1alWmT59+xdtfmDR++OGHYjc2hyYNDwvx9+XjB1rTpWFlXvtuM28vO4l5YA7U6wE/vwizHtcKcqWK2IgRIxg1atS596+++iqvv/46N910E/Hx8TRu3JhZs2ZdtN2ePXto1KgRAJmZmQwYMID69evTp0+f8/qeeuSRR2jZsiUNGzbklVdeAaxOEA8cOECnTp3o1KkTYHW1fvSoVc/57rvv0qhRIxo1asR777137nj169dn6NChNGzYkFtuucXtfVxph4XFgL+vN6PvacHfZ25g1LydpJw8w+t3TMJnwVuw4D9wbCf0+wyCK3o6VKWK3pwRcGiDa/cZ1Ri6vXnJxf379+epp57iscceA2DatGn89NNPDB8+nNDQUI4ePUrbtm3p2bPnJcffHjNmDIGBgWzZsoX169cTHx9/btm//vUvwsPDyc3N5aabbmL9+vUMHz6cd999l3nz5hEZGXnevlatWsWkSZNYvnw5xhjatGnDDTfcQFhYGDt27GDKlCmMHz+efv368fXXX7u1C3a90ygmvL2EN/o05vFOdZi6ch/Dv1zHmeufhzs/ggNrrArywy4fh0oplY/mzZtz5MgRDhw4wLp16wgLCyMqKooXXniBJk2a0LlzZ/bv38/hw4cvuY8FCxac+/Fu0qQJTZr8Ob7OtGnTiI+Pp3nz5mzatInNmzcXGM+iRYvo06cPQUFBBAcHc/vtt7Nw4UKg6Ltg1zuNYkRE+GuXulQI9OX177eQeSaBMQN74/9ATasR4MRb4I4JULebp0NVqugUcEfgTn379mX69OkcOnSI/v3788UXX5CcnMyqVavw9fUlNjY23y7RL2f37t288847rFy5krCwMAYNGnRF+zmrqLtg1zuNYmhIh1q80acx87cnM2jSCk5GNrEqyCPsFuSrPvZ0iEqVev3792fq1KlMnz6dvn37kpaWRqVKlfD19WXevHns3bu3wO2vv/56Jk+eDMDGjRtZv349ACdOnCAoKIjy5ctz+PBh5syZc26bS3XJ3qFDB2bOnElGRganTp3im2++oUOHDi48W+dp0iim7m5Tnff6N2PlnuMMnLCcNJ+KMOh7qH0TfPskzH9Tn6xSyo0aNmxIeno60dHRVKlShXvuuYeEhAQaN27Mp59+Sr169Qrc/pFHHuHkyZPUr1+fl19+mRYtWgDQtGlTmjdvTr169bj77rtp3779uW2GDRtG165dz1WEnxUfH8+gQYNo3bo1bdq0YciQITRv3tz1J+0Ej3SNLiJ9gVeB+kBrY0yCw7LngcFALjDcGPPT5fZXXLtGd4WfNh3iiclrqF0pmM8GtyYywAtmD4d1k6HFIOj+f+CtpYyqdNGu0V2vpHeNvhG4HThvRCIRaQAMABoCXYHRIuJd9OEVH10aRjFxUEt2Hz1Jvw+XcvBkDvQeDR2esYqppt0H2aVjGEmlVPHnkaRhjNlijNmWz6JewFRjzGljzG4gEWhdtNEVPx3iKvLZ4DYknzjNvRNXcOJ0Dtz0MnR7G7b9AJ/2goxjng5TKVUGFLc6jWhgn8P7JHveRURkmIgkiEhCcnJykQTnSa1iwxl3X0v2HD3FY1+sJic3D9oMg74fW4/kftQVThzwdJhKuUxpGFW0uHDlZ+m2pCEic0VkYz5TL1fs3xgzzhjT0hjTsmLFstHorV3tCP7VpxELdxzlte/s57ob9oaBM+DEfh0NUJUa/v7+pKSkaOJwAWMMKSkp+Pv7u2R/bqtBNcZ0voLN9gPVHN7H2POUrX+r6uxKPsWHC3ZRKzKIQe1rQs0OcP+38Pkd1h3HvTOhcgNPh6rUFYuJiSEpKYmyUIpQFPz9/YmJiXHJvorbYzezgcki8i5QFYgDVng2pOLnua712HX0FK99t5kakUF0qlsJouPhgTnwWW+Y1M26+4hp4elQlboivr6+1KxZ09NhqHx4pE5DRPqISBLQDvheRH4CMMZsAqYBm4EfgceMMbmeiLE48/YS/jegGfWrhPLE5DVsO2Q3BqpUDx78EQIqwKc9YfeCgneklFKF5JF2Gq5WmttpFORgWia9Ri7G19uLWY+3JzLY7k4g/ZA1CuCxXVZFeb3uHo1TKVU8laR2GsoFqpQPYML9LUk5dZrBH68kNeOMtSAkyhrQKaoRfDkQVn/m2UCVUqWGJo0SrklMBUbdHc+Wg+kMGLeMI+l2x2eB4XDfLKjVEWY/DvPf0m5HlFJXTZNGKXBT/cp8NKgVfxzLoO/Ypew7Zo/85RcCd38JTe+C+W9YfVbl5ng2WKVUiaZJo5S4Li6Sz4e04fipM/Qdu5TEI3bluLcv9B4DHf4Kqz+xesk9c8qzwSqlSixNGqVIfPUwvnyoHTl5hr5jl7IhKc1aIAI3vQS3vguJv8DHPeCkPv+ulCo8TRqlTP0qoUx/uB2B5Xy4a/wylu9K+XNhq8HQ/3M4shkm3gzJ2z0XqFKqRNKkUQrFRgYx/ZF2VA714/5JK1i3L/XPhfVutVqPn06H8Z1g8yzPBaqUKnE0aZRSVcoH8OVD7YgM9mPopwkcTHPoPr1aa3jod6hY1+pa/eeXtIJcKeUUTRqlWGSwHxPvb0XGmVyGfJJAxhmHxFA+xup2pOWDsOR9q/sRredQSl2GJo1Srm5UCB/c1ZwtB0/wly/XkZfn0FbDxw96/Bd6jYaklTDuBkgqey3rlVLO06RRBnSqV4kXb23Aj5sO8c7P+Yx91fweGPwzeHlbveSun1b0QSqlSgRNGmXEg+1juat1NUbP38mM1UkXr1ClKQz7Haq3hRnDYPWnRR+kUqrY06RRRogIr/VqRLtaEYz4egMJe/IZHjYwHO75CurcBLOfgBXjiz5QpVSxpkmjDPH19mLMwHiqVvDnoc9WsSv5ZD4rBcCAyVC3O/zwV1g6qugDVUoVW5o0ypgKgeWYOKgVAP0+XMbWQycuXsnHD/p+AvV7wk8vwMJ3izhKpVRxpUmjDKpdMZgvH2qLtxcMGLeM9UmpF6/kUw7unASN+8Kv/4D5b2ovuUopTRplVZ1KIXz10LUE+/lw9/jlrMyvjsPbB/p8CM3ugfn/hl9egry8og9WKVVsaNIow6pHBPLVw+2oFOrHvROXs3BHPo37vLyh50hoNQSWfABfPwjZWUUfrFKqWNCkUcZVKR/AtIfaERsRxOCPE/h506GLV/Lygu7vwM2vwaZv4NNecCrl4vWUUqWeR5KGiLwtIltFZL2IfCMiFRyWPS8iiSKyTUS6eCK+siYy2I+pw9pSv2ooj3yxml+3HL54JRFo/6Q15viBNTCxM6TsLPJYlVKe5ak7jV+ARsaYJsB24HkAEWkADAAaAl2B0SLi7aEYy5QKgeX4Ykgb6kWF8Oz09Rw9eTr/FRv2sXrJzUyFCZ1h79KiDVQp5VEeSRrGmJ+NMWd7z1sGxNivewFTjTGnjTG7gUSgtSdiLIuC/Xz4b/9mnMzK4aWZGzGXelqqehsYMhcCwuDTnrBhetEGqpTymOJQp/EgMMd+HQ3sc1iWZM+7iIgME5EEEUlITtbeWV3lmsohPH3zNczZeIhv1x+89IoRta3EEd0Cvh5steXQR3KVKvXcljREZK6IbMxn6uWwzotADvBFYfdvjBlnjGlpjGlZsWJFV4Ze5g3tUJNm1Srw8qyNHEkv4EmpwHC4dyY0usNqy/HtcMjNLrpAlVJFzm1JwxjT2RjTKJ9pFoCIDAJ6APeYP8tB9gPVHHYTY89TRcjH24v/69eUzDO5vDBjw6WLqQB8/eH2CdDhGauTw8n9ICufVuZKqVLBU09PdQWeA3oaYzIcFs0GBoiIn4jUBOKAFZ6IsayrXTGYZ7vUZe6WI3yz5jJ528sLbnoZen4Au363uldPy6cnXaVUieepOo2RQAjwi4isFZGxAMaYTcA0YDPwI/CYMSbXQzGWeQ+0r0mr2DBemb2JQ2lONOiLvw8GToe0fdaTVQfXuT9IpVSR8tTTU3WMMdWMMc3s6WGHZf8yxtQ2xtQ1xswpaD/Kvby9hLfvbEpOrmHEjPUFF1OdVftGePBHEG/4qBusneL+QJVSRaY4PD2lirHYyCBGdKvH/G3JfL78D+c2qtwQhv4KVZvBzIetQZ1Op7s3UKVUkdCkoS7r3rY16BAXyUszN/Lh7zudu+MIibIaAXZ8HjZ8BR9eb7UkV0qVaJo01GV5eQnj72vJrY2r8O85W3lx5kZycp3o7dbLGzqOgPu/g5zTMOFma1Anbc+hVImlSUM5xd/Xmw/uas4jHWszefkfDP4kgfQsJ9tkxLaHhxdB3C3WoE6T+0FGPl2xK6WKPU0aymleXsLfutbj37c3ZlHiUfqOXcqB1EznNg4MhwFfWL3l7ppvPV2lHR4qVeJo0lCFdlfr6nz8QCv2H8+kz+jFbNyf5tyGItB6qN3h4XGYcBPsXeLeYJVSLqVJQ12RDnEVmf7ItXiL0HfsUn7cmM84HJdSva3Vb1VghDU2x/pp7gtUKeVSmjTUFasbFcLMx9pTNyqEhz9fxcjfdjj3ZBVYHR4O/gViWsOMoToGuVIlhCYNdVUqhfozdVhbejeryjs/b2f41LVkZTvZiD8wHO79BpreZY1B/s1D1lNWSqliy8fTAaiSz9/Xm//2b8Y1USG8/dM29qacYvx9Lakc6n/5jX3KQe8xEF4b5r0Ox3ZBv08htKr7A1dKFZreaSiXEBEe7ViHDwe2IPHISXqOXMT6pFRnN4YbnrWGkj282WoIuHuhW+NVSl0ZTRrKpW5pGMXXj1yLj5cX/T5cys7kk85v3LAPDJtnjwjYCxa/r/UcShUzmjSUy9WvEsqMR6/F18uL177d7HzlOEDFujD0N6jfA355Cabdp/1WKVWMaNJQblE51J8nO8fx+/Zkft1ypHAb+4VA30/gltdh6/cwrhMc2eqeQJVShaJJQ7nN/dfGUqdSMK99t9n5J6rOEoFrn4D7Z0NWKoy/ETbOcE+gSimnadJQbuPr7cWrtzXkj2MZTFy0+8p2EnsdPLQQohrB9Afgx+d1HHKlPEiThnKr6+Ii6dowipG/JXIwzcl+qi4UWsXqKbfNw7BsNHxyG6QXogW6UsplNGkot3vx1vrkGcMbP1xFvYRPOej2Ftwx0RpGdmwH2LPYdUEqpZyiSUO5XbXwQB6+oTbfrjvA8l0pV7ezxndaT1f5h1p3HEs+0MdylSpCHkkaIvJPEVkvImtF5GcRqWrPFxF5X0QS7eXxnohPud7DN9QmukIAr8ze5NwATgWpVB+GzoN6t8LPf4cpA+DUVSYjpZRTPHWn8bYxpokxphnwHfCyPb8bEGdPw4AxHopPuVhAOW/+fmt9th5KZ8oKJ8caL4h/qNXdSPd3YOdvMLa9tiJXqgh4JGkYY044vA0CzpYv9AI+NZZlQAURqVLkASq36NooimtrR/DOz9tZnHiU0zmFfAz3QmfH5xjyK5QLtoqr5r0BuTmuCVgpdRGP1WmIyL9EZB9wD3/eaUQD+xxWS7Ln5bf9MBFJEJGE5ORk9warXEJE+EfPhuTlGe6ZsJzmr/3Cgx+v5OPFu9mVfLJwLccdVWkCw+ZDs7vh97es5JGW5MrQlVI2ueL/qJfbschcICqfRS8aY2Y5rPc84G+MeUVEvgPeNMYsspf9CvzNGJNQ0LFatmxpEhIKXEUVI+lZ2SzbdYwF25NZsCOZvSkZAMSEBfDPXo3oVK/Sle98/TT47mnw9rWKrhrdYd2RKKUuIiKrjDEtC7WNu5KG0wGIVAd+MMY0EpEPgfnGmCn2sm1AR2PMwYL2oUmjZNubcooFO44yafFuTp3OYf5fOxFQzvvKd5iyE2YMg/0JUK8H3PouhFR2XcBKlRJXkjQ89fRUnMPbXsDZB/hnA/fZT1G1BdIulzBUyVcjIoh729bgzdubcPjEaT5afIWtx8+KqA2Df4abX4Mdv8DoNrD+K300VykX8FSdxpsislFE1gO3AE/a838AdgGJwHjgUQ/Fpzygdc1wOtevxNj5Ozl26szV7czLG9o/CQ8vgog6MGMIfDkQ0g+7JlilyihPPT11hzGmkf3Y7W3GmP32fGOMecwYU9sY0/hydRmq9Plb13qcOpPDyN8SXbPDitfAgz/Bzf+07jpGtYYN012zb6XKIG0RroqVuMoh9G1Rjc+W7WHfsQzX7NTLG9oP//Ou4+vBMH0wZB53zf6VKkM0aahi5+mbr5XQ9G0AACAASURBVMHbS3jn522u3fHZu45OL8LmmTD6Wtg5z7XHUKqU06Ship2o8v482L4ms9YeYOP+NNfu3NsHbngOBv8C5YLgs94wZwRkX2EPvEqVMZo0VLH0cMfahAX68taPbhqxLzoeHloArR+C5WPgwxtg3wr3HEupUkSThiqWQv19efzGOBbuOMrCHW5q8V8uELr/B+79xhqHfOLNMOVuOLzZPcdTqhRwKmmIyJMiEmq3n5goIqtF5BZ3B6fKtoFtqxMTFsCbc7aSl+fGNha1b4THV8KNf4c9C2HMtVbjwGNX2V5EqVLI2TuNB+1OBm8BwoB7gTfdFpVSgJ+PN3+9pS6bDpzgq1X7Lr/BVR0sGK5/Fp5cZz1ptXkWjGwJ3/1FRwlUyoGzSeNs5z3dgc+MMZsc5inlNj2bVqVJTHn+9vUGur63gHELdnL4RJb7DhgYbrUkH74W4u+H1Z/ABy1h5QTIu8pxQJQqBZzqe0pEJmH1NlsTaAp4Y/UR1cK94TlH+54q3dIys5m1dj8zVu9n7b5UvATa14mkT/NoujSMIsjPx30HT9kJ3/8Fds2Ham2h5wfWo7tKlQJu67BQRLyAZsAuY0yqiIQDMcaY9VcWqmtp0ig7diWfZOaa/Xyzdj/7jmUSHlSOkXc159o6ke47qDGwdjL89AJkZ8D1z1ldlPiUc98xlSoC7kwa7YG1xphTIjIQiAf+Z4zZe2WhupYmjbLHGMPKPcd58ZsN7Ew+yQvd6zP4upqIO7tBP3kE5vwNNs2ASg2su46YQv1/U6pYcWcvt2OADBFpCjwD7AQ+LWR8SrmMiNC6ZjjfPNaeLg2jeP37LTw5dS2ZZ65yNMCCBFeCvpNgwBTITIUJnWHWY1YyUaqMcDZp5BjrlqQXMNIYMwoIcV9YSjkn2M+H0ffE82yXuny7/gC3j1niuj6rLqVed3hsObR7DNZNhQ9awJIPIOcqe+ZVqgRwNmmk2yPs3Qt8b9dx+LovLKWcJyI81qkOkwa1Yv/xDG4buYgF2908BLB/KHT5Fzy6DKq1gZ//DmPawfaf3XtcpTzM2aTRHziN1V7jEBADvO22qJS6Ah3rVuLbJ66jcog/gyat4JMle9x/0Mg4GDgd7rYHeZrcF77oC0fc1P2JUh7m9HCvIlIZaGW/XWGMKTYFuVoRrhydOp3Dk1PXMnfLYQZfV5MXutfH26sImhXlnIHlY+H3/0D2KWg+EDo+D6FV3X9spa6A2yrCRaQfsALoC/QDlovInYUPUSn3C/Lz4cN7WzDo2lgmLtrNo1+scm8F+Vk+5azW5E+uszpCXDsF3o+Huf+ALBf31quUhzj7yO064OazdxciUhGYa4xp6ub4nKJ3GupSPlq0m39+v5kmMRWYcF9LKob4Fd3Bj++B316HDV9BQJjVTUmrIeBThDEoVQB3PnLrdUFxVEohtlXKYx68riZjB7Zg26ET3D5mMYlHThbdwcNi4Y4JVhfsVZpZjQNHtYbNs636D6VKIGd/+H8UkZ9EZJCIDAK+B3642oOLyDMiYkQk0n4vIvK+iCSKyHoRib/aYyjVpWEUU4e1I/NMLrePXkzCnmNFG0CVpnDfTBj4NfgEwLR74eMecGBt0cahlAs4lTSMMc8C44Am9jTOGPO3qzmwiFTD6jX3D4fZ3YA4exqG1ahQqavWrFoFvnm0PRHBftz/0YqiTxwAdTpb45Tf+i4kb4FxHWHmY9qLripRnC5iMsZ8bYz5iz1944Jj/xd4DnC8T+8FfGosy4AKIlLFBcdSimrhgUwd1pZKof6eSxzePtBqMAxfA9c+ARumWZXlS0ZqL7qqRCgwaYhIuoicyGdKF5ETV3pQEekF7DfGrLtgUTTgOHBCkj0vv30ME5EEEUlITnZzQy5ValQO9fd84gDwLw+3/NNqWV7rBvj5RfjiTu2SRBV7BSYNY0yIMSY0nynEGBNa0LYiMldENuYz9QJeAF6+msCNMeOMMS2NMS0rVqx4NbtSZUyxSRwA4bVgwGTo8V/YuxjGtIedv3kuHqUuw21PQBljOhtjGl04AbuwxuVYJyJ7sFqXrxaRKGA/UM1hNzH2PKVcqlglDhFo+SAMnQeBEfBZH/jlZcjN9lxMSl1CkT82a4zZYIypZIyJNcbEYhVBxdvdk8wG7rOfomoLpBljDhZ1jKpsuDBxLE486uGAGsDQ36DFA7D4f/BRFzi2y7MxKXWB4tbW4gesO5FEYDzwqGfDUaXd2cQRVd6feyYs5/kZGziR5cG/8MsFwm3vQd9P4GgijGwFXw6ExF+1olwVC073PVWcaYtwdbUyzuTw31+2M3HRbiKD/fhn70Z0aRjl2aDSkmD5h7D2C8hIgQo1oMX90GwghFT2bGyqVHDbyH3FnSYN5Srrk1L529cb2HLwBN0aRfGPng2pFOrv2aByTsPW7yBhEuxZCF4+ULc7tH8KYlp4NjZVomnSUMoFsnPzGL9wF+/N3YGfjxev925Er2b5Pvld9I4mwuqPYfVnkJUKNa+HDs9AzRusCnWlCkGThlIutCv5JM9OX8/afalMHdaWVrHhng7pT6fTYdXHVqPAk4egaryVPOp2B6/iVlWpiitNGkq5WHpWNrd9sIjM7Fy+H96ByOBi1kNtdhasmwKL37N61Y2sCw17Q61OENMSvHWATXVpmjSUcoPNB07QZ/RiWsWG88mDrYtmQKfCys2BzTOtivP9CWDyoFwI1OxgJZDanSCijhZhqfNo0lDKTb5c+Qd/+3oDT3WO46nO13g6nIJlHofdC2DnPKt1eepea37cLXDb+xCq3bkpy5UkDR93BaNUadKvZTWW7z7G/37dQYsaYXSIK8Zd1wSEQYNe1gRWA8FN38Dvb8PottD9bWjcV+861BXRGjOlnCAivN67EXGVgnlq6loOpWV5OiTnhdeyKskfXgSR18CMoVaDwZPa0acqPE0aSjkpsJwPo++JJzM7lyemrCY712qhbYzhj5QMpq9K4m/T13PXuGUs8XSXJPmJrAMP/gg3vwY7fobRbWDTTE9HpUoYrdNQqpBmrd3Pk1PX0r1xFCJCwp5jHD5xGoDyAb4E+HpzJD2L57rW46HrayHFsRjoyFaY+TAcWGO19Wh4O9TrAcHFuNhNuZxWhCtVRF6auZHPlu2lSnl/WsWG06pmOK1jw4mrFExGdi7PTV/HDxsO0bVhFG/3bUKIfzF89DU3B5aOtNp7HN8N4gXV20H9nlC/B5SP8XSEys00aShVRPLyDEdPnaZSSP5djBhjmLhoN/+es5Ua4YF8eG8L4iqHFHGUTjIGDm+CLbNhy7dwZLM1P7aDNc5HZJxn41Nuo0lDqWJm2a4UHp+8mowzufznzib0aFLV0yFd3tFEq83Hkg8gJwtuegXaPKwtzUuhK0ka+i1Qyo3a1orguyc6UC8qhMcnr+GTJXs8HdLlRdaB6/9qD0XbEX56Hj6+Vcf2UIAmDaXcLqq8P1OHteOmepV4/fvNrN2X6umQnBMSBXdNhd5jrOKrMe1hxXgd16OM06ShVBEo5+PF//VrSqUQfx6fvJq0jBIylKsINLsbHl0K1dvCD3+FT3vC3qVWXYgqczRpKFVEKgSW44O7m3MoLYtnp6+jRNUnlo+GgTOgx3tweCNM6grjb4QN03Us8zJGk4ZSRSi+ehgjutXj582HmbR4j6fDKRwRaPkAPL0Zbn0XTp+ArwfD/5rB4vchs4QUu6mrok9PKVXEjDEM/XQVv28/wlcPX0uzahU8HdKVycuDHT/B0lHWiIK+QRDbHqq1saboeCgX5OkoVQFKzCO3IvIqMBQ42/nNC8aYH+xlzwODgVxguDHmp8vtT5OGKmlSM85w6/uLAPhheAfKBxbDxn+FcWAtrJpk1XUc3WbNE2+IagzVWlvJIzPVGm3w3L/HrfE/uvxL24J4SElLGieNMe9cML8BMAVoDVQF5gLXGGNyC9qfJg1VEq354zh9xy6lU71KjLu3RfHsbuRKZByDpATYt9ya9q+C3DPgXwECKli98PpXAP9Q2DEXcjKh/ZNWp4q+AZ6OvkwpDV2j9wKmGmNOA7tFJBErgSz1bFhKuV5zu37j9e+3cM+E5YQHlaOcjxflvL0o5+OFr7cXLWuE0a1xCRv/IjAcrrnFmsAqxhLJvyv2k0fg55dgwduwfprVbfs1XYo2XlUonqwIf1xE1ovIRyISZs+LBvY5rJNkz7uIiAwTkQQRSUhO1i6eVck0+LqaPNi+JsdOnWHzgROs2H2M37YeYfa6A3yxfC+PfLGaeduOeDrMq+PldemxO4Irwe0fwv3fgY8/TO4HU++B1H35r688zm3FUyIyF4jKZ9GLwDLgKGCAfwJVjDEPishIYJkx5nN7HxOBOcaY6QUdS4unVGmUlZ1L71GLOZJ+mh+GdyCqfP79XJUaOWdg2SiY/5Y1XG2TftDucahUz9ORlVrFqhsRY0xnY0yjfKZZxpjDxphcY0weMB6rCApgP1DNYTcx9jylyhx/X29G3RNPVnYuw6esISe3lLfE9ikH1z0Nj6+A5vfAhq+sMT8+v8MatrYUPOlZGnikeEpEHAtp+wAb7dezgQEi4iciNYE4YEVRx6dUcVG7YjD/6tOIFXuO8d7cHZ4Op2hUqG71rvv0Zuj0dzi4Hj7rY3VjsuoTSNmpXZl4kKcqwv8jIs2wiqf2AA8BGGM2icg0YDOQAzx2uSenlCrt+jSPYenOFEbNT6RNrfDiPT65KwVFwA3PQvvhVsvzpaPg2+HWsnLBULmh9Uhv5UYQ1QSqNgMvb8/GXAZo4z6lSoDMM7n0GrWIlJNnmPNkByqFOle/kZ2bR9LxTA6kZtIkpnzxHAzKWcbAofXWncehDVZ3Joc2WC3TAcJqQttHrb6y/II9G2sJUWLaabiaJg1VFuw4nE7PkYtpWq08Xwxpi7fXn08kncjKZuP+NDYfOMGelFPsTclgT8opDqRmkZtn/R+vVTGITx5oTbXwQE+dgusZA6l7Yd8KWDEOklZabUBaPgCth0FoCRi/xIM0aShVyn2VsI9np6/n3rY1iA4LYMP+NDbtT2NPSsa5dSoE+lIjIoga4YHERgRSIyIIH2/h5Vmb8PX2YtKgVjSOKe/Bs3CjfSusIWy3fGsNX9voTqtFel4u5OU4TLnWeOhxXSC0hLWDcSFNGkqVAX+ZtpYZq62HCqMrBNA4ujyNY8rTKLo8jaqGEhHsl+92iUfSuf+jlRzPOMOoe+LpVLdSUYZdtI7thuUfwprP4MzJgteNbgn1boV6PaDiNUUTXzGhSUOpMuBMTh5r96USVymYsKByhdr28IksHpi0km2H03mjTyP6t6rupiiLiTMZVp2Hl8/FU8oO2PodbP0eDqyx1o+oYyWQ+j2hanypH+JWk4ZS6rJOns7hkc9XsXDHUZ68KY6nOseVnn6vrlRaEmybYyWRPYusIqyQKtbdR/0eUKM9eJfghwguQZOGUsop2bl5jPh6A1+vTuLhG2ozopu2uj4n8zhs/8mqF0n81epQMSAM4m6BsFgIjLCmoEj7daT1ugQmldLQYaFSqgj4envxTt8mGAwTF+1iYNvqxISVoqeqrkZAGDQdYE1nTlmJY+t3sHMenErGal6W33bhVl9aQRXtfytBrY5WB4yl6E5O7zSUKsP2p2bS8e159G9Vjdd7N/Z0OMVfXq51J3LqKGSkQMZR6/Wpo3DyMJw6AieTrX/TD0P2KYjtAF3egCpNPB39RfROQylVKNEVArizRTWmrUzi8U5xpb9TxKvl5W0VRQVFXn7d3BxrYKr5/4YPr7f607rxJQjJrx/XkqN0PxqglLqsRzvWJs8Yxv6+09OhlC7ePtB6KDyxGq59HNZ9Ce/Hw+//sZ7qKqG0eEopxXPT1zFr7QEWPtfJ6S5KVCEd2wW/vAJbZltD4QaEWQNWBYRZ9SFn34dUsRochlS17kpCqoCve66JFk8ppa7IY53q8PXq/YxbsIu/92jg6XBKp/Ba0P8zaxz1xF+sYXEzj1vTiSSrL61TR62ntS4UVAma3QXXDneuaMyNNGkopagREUSvZlX5fPleHu5Ym8hLtCpXLlCjnTXlxxjISoP0g3DigP3vQaujxiUfwIrx0PJBa0z1YM+06NekoZQCrLuNmWv2M37hLp7vVt/T4ZRNIhBQwZoqXXANju6ABe/AstGwcuKfySOkcpGGqBXhSinAGvDptqZV+WzpXo6dOuPpcNSFIuOs8dQfT4CGfWD5WPhfE2uckSKkSUMpdc7jneqQmZ3LxEW7PB2KupSI2tBnDDyRAI3vhPLVLr+NC2nSUEqdE1c5hO6NqvDJkr2kZpx/t5Gdm8f2w+n8vj2ZI+lZHopQnRNeC3qNggY9i/SwWqehlDrP4zfW4fsNB3njhy3EVQphy6ETbD2YTuKRk5zJ/XNs7ugKAcTXCCO+egXiq4dRv0oo5Xz079DSTpOGUuo89auE0rVhFNMSkgCoHOpHvahQOlwTSYMqoVQM8WPzgROs+SOVhD3H+HbdAQACfL154/ZG9Gke48nwlZt5LGmIyBPAY0Au8L0x5jl7/vPAYHv+cGPMT56KUamy6q07m/BA+1jiKocQns+YHdfW/rOtwMG0TFbvTeWTJXt4Zto6/Hy86d647I6GV9p5JGmISCegF9DUGHNaRCrZ8xsAA4CGQFVgrohcY4zJ9UScSpVV5QN8aVMrwql1q5QP4NYmAXSsW5H7PlrB8Clr8Pf14sZ6RfsoqCoaniqAfAR40xhzGsAYc8Se3wuYaow5bYzZDSQCrT0Uo1KqEIL8fJj0QCvqVwnl4c9XszjxqKdDUm7gqaRxDdBBRJaLyO8i0sqeHw3sc1gvyZ53EREZJiIJIpKQnJzs5nCVUs4I9ffl0wdbUzMiiCGfJJCw55inQ1Iu5rakISJzRWRjPlMvrGKxcKAt8CwwTQo53qQxZpwxpqUxpmXFihXdcAZKqSsRFlSOz4a0pkp5fx6YtJL1SameDkm5kNuShjGmszGmUT7TLKw7iBnGsgLIAyKB/YBjS5UYe55SqgSpFOLP50PaEBrgy30frWDj/jRPh6RcxFPFUzOBTgAicg1QDjgKzAYGiIifiNQE4oAVHopRKXUVqlYIYMrQtvj7eHPn2CV8lbDv8htdwpmcPCYs3MUdY5YwYeEuMs7kuDBSVRgeGU9DRMoBHwHNgDPAX40xv9nLXgQeBHKAp4wxcy63Px1PQ6ni60h6Fk9OWcvSXSn0axnDP3o2IqCct1PbGmP4ceMh3vxxK3tTMqgREcjelAzCAn0ZfF1N7m0XS/kAXzefQel1JeNp6CBMSim3y80zvDd3Ox/8lki9qBBG3xNPrYrBBW6zbl8qr3+/mZV7jnNN5WBe6F6fjnUrsWrvcUbNS+S3rUcI8fPh/mtjefC6mvm2J1EF06ShlCrW5m87wtNfruVMTh5v3dmEHk2qApCTm8fRk2c4fCKLQyeymLPhIDPXHiAyuBx/ubku/VrG4ON9fmn6xv1pjJ6fyJyNh/Dz8SI2IohQf19CA3wpH+BLaIAP5QN8aRpTgQ5xkRdtn5+s7FzSMrOpXEZGL9SkoZQq9g6kZvL45NWs/iOVelEhHM84Q3L6afIcforK+Xgx5LqaPNKxNiH+BRc/JR5J5/Nlf3AgNZMTWdmkZeZwIjObE5nZpJ+26j4ig8vRs2k0t8dH07BqKI4Pa548ncO8rUf4ceMh5m07Qm6eKTPD3mrSUEqVCNm5eXzw6w7WJqVROcSPqPL+VA61pqhQf6pHBLqkruJ0Ti6/b0tmxur9/Lr1MNm5hrqVQ7g9PpqIYD9+3HiIBTuSOZOTR2RwOa6Pq8iMNfv5+631GdKhlgvOtHjTpKGUUpeQmnGGb9cfZMbqJNb8YbUdqVLeny4No+jWKIqWseF4ewm9Ri4iO9fww5MdPByx+11J0tBebpVSZUKFwHLc27YG97atwe6jpziZlUPDqqF4eZ3frrh382j+8e1mth1Kp25UiIeiLb6083ulVJlTMzKIxjHlL0oYALc1rYq3lzBjTZIHIiv+NGkopZSDyGA/brimIrPWHCAvr+QX37uaJg2llLpAn+bRHDqRxbJdKZ4OpdjRpKGUUhe4uUFlgv18mLFGu767kCYNpZS6gL+vN90aRTFnw0Eyz+gYcI40aSilVD76xEdz6kwuP28+5OlQihVNGkoplY+2NSOoWt6fmVpEdR5NGkoplQ8vL6FX82gW7DhKcvppT4dTbGjSUEqpS7i9eTS5eYZv1x3wdCjFhiYNpZS6hLjKITSsGso3WkR1jiYNpZQqQJ/m0WzYn0bikXSX7C814wyJR066ZF+eoElDKaUK0LNZVbwEl9xtHD6RRa9Ri+n63gKmXcXwt56kSUMppQpQKcSfDnEVmXmV3Yokp5/m7vHLOJp+mubVK/Dc9PW8+8t2SlpP45o0lFLqMm6Pj2Z/aia3vLeAV2dvYu7mw6RnZTu9/bFTZxg4YTkHUrOY9EBrJg9tS98WMbz/6w6e+WodZ3Ly3Bi9a3mka3QR+RKoa7+tAKQaY5rZy54HBgO5wHBjzE+eiFEppc66rUlVUjOy+XXrEaau/IOPl+zB20toVq0C7etEcluTKsRVzr8b9bSMbAZOWM6elFNMGtSK1jXDAfjPnU2oFh7Iu79s51BaFmMGtijUwFPGGEbP38lN9StRLyrUJefpDI8PwiQi/wekGWNeE5EGwBSgNVAVmAtcY4wpsB2/DsKklCoqp3NyWb03lcWJR1mUeJT1SankGWgVG8bdbarTrVEV/H29ATiRlc29E5az5WA64+9vyQ3XVLxofzNWJ/G3r9dTMzKISQ+0JrpCwGVjyM0zvDRrI5OX/8FDN9Ti+W71r+hcStzIfWIN1PsHcKMxZod9l4Ex5t/28p+AV40xSwvajyYNpZSnpJw8zderk5i8/A/2pGRQIdCXO+Jj6NM8mldmb2LdvlTGDmxB5waVL7mPJYlHeejzVfj7evPm7Y25qf6l183KzuXpL9cyZ+MhHu1Ym2e71D1vzPPCKIlJ43rg3bNBi8hIYJkx5nP7/URgjjFmej7bDgOGAVSvXr3F3r17iy5wpZS6QF6eYemuFCYv/4OfNh0iJ8/g7SWMvKs53RpXuez22w+n88TkNWw7nE7vZlV5+baGhAeVO2+d9Kxshn6awLJdx3ipRwMGX1fzqmIuVsO9ishcICqfRS8aY2bZr+/CKo4qNGPMOGAcWHcaVxSkUkq5iJeX0L5OJO3rRJKcfpqZa/ZTu1IQN9a79F2Do2sqh/DtE9cxen4iI39LZOGOo/yjV0NubVwFESE5/TSDJq1g26F03uvfjN7No918RvlzW9IwxnQuaLmI+AC3Ay0cZu8Hqjm8j7HnKaVUiVExxI+h19cq9HblfLx4qvM1dG0UxXPT1/P45DV82/AAw66vxV+mrePIidNMuL8lHetWckPUzvHkI7edga3GGMeBeGcDA0TET0RqAnHACo9Ep5RSHlIvKpQZj1zL893qMX9bMneMWUpaZjaTh7bxaMIADz1yaxvABUVTxphNIjIN2AzkAI9d7skppZQqjXy8vXjohtrc3KAyHy/Zw33talCnUv6P9RYljz9y6wr69JRSShXelVSEa4twpZRSTtOkoZRSymmaNJRSSjlNk4ZSSimnadJQSinlNE0aSimlnKZJQymllNM0aSillHJaqWjcJyLJwJV2cxsJHHVhOCVJWT13Pe+yRc/70moYYy4e5KMApSJpXA0RSShsi8jSoqyeu5532aLn7VpaPKWUUsppmjSUUko5TZOGPZBTGVVWz13Pu2zR83ahMl+noZRSynl6p6GUUsppmjSUUko5rUwnDRHpKiLbRCRRREZ4Op6rJSLVRGSeiGwWkU0i8qQ9P1xEfhGRHfa/YfZ8EZH37fNfLyLxDvu6315/h4jc76lzKgwR8RaRNSLynf2+pogst8/vSxEpZ8/3s98n2stjHfbxvD1/m4h08cyZOE9EKojIdBHZKiJbRKRdWbjeIvK0/R3fKCJTRMS/NF5vEflIRI6IyEaHeS67viLSQkQ22Nu8LyJy2aCMMWVyAryBnUAtoBywDmjg6biu8pyqAPH26xBgO9AA+A8wwp4/AnjLft0dmAMI0BZYbs8PB3bZ/4bZr8M8fX5OnP9fgMnAd/b7acAA+/VY4BH79aPAWPv1AOBL+3UD+3vgB9S0vx/enj6vy5zzJ8AQ+3U5oEJpv95ANLAbCHC4zoNK4/UGrgfigY0O81x2fYEV9rpib9vtsjF5+kPx4MVoB/zk8P554HlPx+Xic5wF3AxsA6rY86oA2+zXHwJ3Oay/zV5+F/Chw/zz1iuOExAD/ArcCHxn/yc4CvhceL2Bn4B29msfez258DvguF5xnIDy9o+nXDC/VF9vO2nss38Efezr3aW0Xm8g9oKk4ZLray/b6jD/vPUuNZXl4qmzX7yzkux5pYJ9C94cWA5UNsYctBcdAirbry/1GZTEz+Y94Dkgz34fAaQaY3Ls947ncO787OVp9vol7bxrAsnAJLtYboKIBFHKr7cxZj/wDvAHcBDr+q2i9F/vs1x1faPt1xfOL1BZThqllogEA18DTxljTjguM9afFKXqOWsR6QEcMcas8nQsRcwHq+hijDGmOXAKq7jinFJ6vcOAXlhJsyoQBHT1aFAe4onrW5aTxn6gmsP7GHteiSYivlgJ4wtjzAx79mERqWIvrwIcsedf6jMoaZ9Ne6CniOwBpmIVUf0PqCAiPvY6judw7vzs5eWBFEreeScBScaY5fb76VhJpLRf787AbmNMsjEmG5iB9R0o7df7LFdd3/326wvnF6gsJ42VQJz9xEU5rAqy2R6O6arYTz5MBLYYY951WDQb+P/27ifEyiqM4/j3R4IpQqS1czEKlpDgHxRmoTCQzEJaRAiGgqGBKairCHVW7gS3unEVhLgQUVxp9McyRbJkHCWLRloUYgSFZULIEglDtQAAAypJREFU+Lg4z2VeL1c9IzfuOPP7wMvc+/67c94zc5973nPuc1ojJt6j9HW01m/OURf9wJ1s9p4FBiW9nJ/qBnPdpBQReyNifkT0Uerxi4jYBHwJrM/d2svduh7rc//I9e/maJsFwCJKR+GkFBG3gV8lvZ6r3gR+YIrXN+W2VL+k2fk33yr3lK7vhq7Ub277W1J/XsfNjXM9Xq87eXrcwbSOMsLoJjDU69+nC+VZTWmqjgDDuayj3L/9HPgZ+AyYm/sLOJzlvwasbJxrKzCay5Zel20C12CA8dFTCylvAqPAcWBmrn8xn4/m9oWN44fyevxExUiSXi/AMuC7rPNTlNExU76+gf3Aj8B14BPKCKgpV9/AMUq/zX1Ky/L9btYvsDKv4U3gEG2DKjotTiNiZmbVpvPtKTMzmyAHDTMzq+agYWZm1Rw0zMysmoOGmZlVc9Awa5B0MX/2SdrY5XPv6/RaZs8TD7k160DSAPBhRLw1gWNmxHjuo07b70bEnG78fma94paGWYOku/nwALBG0nDO3fCCpIOSLudcBR/k/gOSzks6TflWMpJOSfo+53vYlusOALPyfEebr5Xf4D2oMjfENUkbGuc+p/H5Mo5WzXdg9j+a8fRdzKalPTRaGvnmfyciVkmaCVyQ9GnuuwJYEhG/5POtEfGnpFnAZUknImKPpJ0RsazDa71D+Wb3UuCVPObr3LYceAO4BVyg5Fj6pvvFNavjloZZnUFKXp9hSrr5eZRcRQDfNgIGwG5JV4FLlERxi3iy1cCxiBiLiN+Br4BVjXP/FhEPKGlh+rpSGrNn5JaGWR0BuyLikUR+2ffxb9vztZTJfO5JOkfJffSs/ms8HsP/s9ZjbmmYdfYPZcrclrPAjkw9j6TXcsKjdi8Bf2XAWEyZSrPlfuv4NueBDdlv8iplis/nIduqTUP+1GLW2QgwlreZPqbMz9EHXMnO6D+AtzscdwbYLukGJXPqpca2I8CIpCtRUre3nKRMT3qVkqX4o4i4nUHHbFLxkFszM6vm21NmZlbNQcPMzKo5aJiZWTUHDTMzq+agYWZm1Rw0zMysmoOGmZlVewgVnUssvughKAAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "G6UjCTMQ_N5e",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "cbb47e93-575c-4e0d-d3a5-bdc45274f427"
      },
      "source": [
        "# evaluate on test set\n",
        "model.eval()\n",
        "test_edge_index = test_edge_index.to(device)\n",
        "test_sparse_edge_index = test_sparse_edge_index.to(device)\n",
        "\n",
        "test_loss, test_recall, test_precision, test_ndcg = evaluation(\n",
        "            model, test_edge_index, test_sparse_edge_index, [train_edge_index, val_edge_index], K, LAMBDA)\n",
        "\n",
        "print(f\"[test_loss: {round(test_loss, 5)}, test_recall@{K}: {round(test_recall, 5)}, test_precision@{K}: {round(test_precision, 5)}, test_ndcg@{K}: {round(test_ndcg, 5)}\")"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[test_loss: -51.86417, test_recall@20: 0.12678, test_precision@20: 0.04674, test_ndcg@20: 0.10205\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "At4zWPfaVW6q"
      },
      "source": [
        "# Make New Recommendatios for a Given User"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SzuMPxFVZlQn"
      },
      "source": [
        "# def get_movie_title_mapping():\n",
        "model.eval()\n",
        "df = pd.read_csv(movie_path)\n",
        "movieid_title = pd.Series(df.title.values,index=df.movieId).to_dict()\n",
        "movieid_genres = pd.Series(df.genres.values,index=df.movieId).to_dict()\n",
        "\n",
        "user_pos_items = get_user_positive_items(edge_index)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DSFgwnaecWBw",
        "outputId": "691161a1-da35-4d15-cbd4-e02d2be2d1ed"
      },
      "source": [
        "USER_ID = 1\n",
        "NUM_RECS = 10\n",
        "\n",
        "user = user_mapping[USER_ID]\n",
        "e_u = model.users_emb.weight[user]\n",
        "scores = model.items_emb.weight @ e_u\n",
        "\n",
        "values, indices = torch.topk(scores, k=len(user_pos_items[user]) + NUM_RECS)\n",
        "\n",
        "movies = [index.cpu().item() for index in indices if index in user_pos_items[user]][:NUM_RECS]\n",
        "movie_ids = [list(movie_mapping.keys())[list(movie_mapping.values()).index(movie)] for movie in movies]\n",
        "titles = [movieid_title[id] for id in movie_ids]\n",
        "genres = [movieid_genres[id] for id in movie_ids]\n",
        "\n",
        "print(f\"Here are some movies that user {USER_ID} rated highly\")\n",
        "for i in range(NUM_RECS):\n",
        "    print(f\"title: {titles[i]}, genres: {genres[i]} \")\n",
        "\n",
        "print()\n",
        "\n",
        "movies = [index.cpu().item() for index in indices if index not in user_pos_items[user]][:NUM_RECS]\n",
        "movie_ids = [list(movie_mapping.keys())[list(movie_mapping.values()).index(movie)] for movie in movies]\n",
        "titles = [movieid_title[id] for id in movie_ids]\n",
        "genres = [movieid_genres[id] for id in movie_ids]\n",
        "\n",
        "print(f\"Here are some suggested movies for user {USER_ID}\")\n",
        "for i in range(NUM_RECS):\n",
        "    print(f\"title: {titles[i]}, genres: {genres[i]} \")"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Here are some movies that user 1 rated highly\n",
            "title: Forrest Gump (1994), genres: Comedy|Drama|Romance|War \n",
            "title: Matrix, The (1999), genres: Action|Sci-Fi|Thriller \n",
            "title: Silence of the Lambs, The (1991), genres: Crime|Horror|Thriller \n",
            "title: Star Wars: Episode IV - A New Hope (1977), genres: Action|Adventure|Sci-Fi \n",
            "title: Fight Club (1999), genres: Action|Crime|Drama|Thriller \n",
            "title: Schindler's List (1993), genres: Drama|War \n",
            "title: Star Wars: Episode V - The Empire Strikes Back (1980), genres: Action|Adventure|Sci-Fi \n",
            "title: Braveheart (1995), genres: Action|Drama|War \n",
            "title: American Beauty (1999), genres: Drama|Romance \n",
            "title: Usual Suspects, The (1995), genres: Crime|Mystery|Thriller \n",
            "\n",
            "Here are some suggested movies for user 1\n",
            "title: Shawshank Redemption, The (1994), genres: Crime|Drama \n",
            "title: Pulp Fiction (1994), genres: Comedy|Crime|Drama|Thriller \n",
            "title: Godfather, The (1972), genres: Crime|Drama \n",
            "title: Terminator 2: Judgment Day (1991), genres: Action|Sci-Fi \n",
            "title: Lord of the Rings: The Return of the King, The (2003), genres: Action|Adventure|Drama|Fantasy \n",
            "title: Lord of the Rings: The Fellowship of the Ring, The (2001), genres: Adventure|Fantasy \n",
            "title: Lord of the Rings: The Two Towers, The (2002), genres: Adventure|Fantasy \n",
            "title: Apollo 13 (1995), genres: Adventure|Drama|IMAX \n",
            "title: Aladdin (1992), genres: Adventure|Animation|Children|Comedy|Musical \n",
            "title: Sixth Sense, The (1999), genres: Drama|Horror|Mystery \n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hLkRpNldrSQe"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}