class_07_dimensionality_reduction_optimization.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "downtown-trading",
   "metadata": {},
   "source": [
    "# Dimensionality reduction and optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "verified-accommodation",
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "from IPython.display import Markdown, display, HTML\n",
    "from collections import defaultdict\n",
    "\n",
    "np.set_printoptions(edgeitems=10, linewidth=500)\n",
    "\n",
    "# Fix the dying kernel problem (only a problem in some installations - you can remove it, if it works without it)\n",
    "import os\n",
    "os.environ['KMP_DUPLICATE_LIB_OK'] = 'True'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "educated-tourist",
   "metadata": {},
   "source": [
    "## Load data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "rough-editing",
   "metadata": {},
   "outputs": [],
   "source": [
    "seed = 6779\n",
    "rng = np.random.RandomState(seed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "looking-feeling",
   "metadata": {},
   "outputs": [],
   "source": [
    "ml_ratings_df = pd.read_csv(os.path.join(\"data\", \"movielens_small\", \"ratings.csv\")).rename(columns={'userId': 'user_id', 'movieId': 'item_id'})\n",
    "ml_movies_df = pd.read_csv(os.path.join(\"data\", \"movielens_small\", \"movies.csv\")).rename(columns={'movieId': 'item_id'})\n",
    "ml_df = pd.merge(ml_ratings_df, ml_movies_df, on='item_id')\n",
    "\n",
    "# Filter the data to reduce the number of movies\n",
    "left_ids = [1, 318, 1193, 1208, 1214, 1721, 2959, 3578, 4306, 109487]\n",
    "\n",
    "ml_ratings_df = ml_ratings_df.loc[ml_ratings_df['item_id'].isin(left_ids)]\n",
    "ml_movies_df = ml_movies_df.loc[ml_movies_df['item_id'].isin(left_ids)]\n",
    "ml_df = ml_df.loc[ml_df['item_id'].isin(left_ids)]\n",
    "\n",
    "display(ml_movies_df)\n",
    "\n",
    "print(\"Number of interactions left: {}\".format(len(ml_ratings_df)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "plastic-brooklyn",
   "metadata": {},
   "source": [
    "## Shift item ids and user ids so that they are consecutive"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "valuable-modem",
   "metadata": {},
   "outputs": [],
   "source": [
    "interactions_df = ml_ratings_df.copy()\n",
    "\n",
    "unique_item_ids = interactions_df['item_id'].unique()\n",
    "item_id_mapping = dict(zip(unique_item_ids, list(range(len(unique_item_ids)))))\n",
    "item_id_reverse_mapping = dict(zip(list(range(len(unique_item_ids))), unique_item_ids))\n",
    "unique_user_ids = interactions_df['user_id'].unique()\n",
    "user_id_mapping = dict(zip(unique_user_ids, list(range(len(unique_user_ids)))))\n",
    "user_id_reverse_mapping = dict(zip(list(range(len(unique_user_ids))), unique_user_ids))\n",
    "\n",
    "interactions_df.replace({'item_id': item_id_mapping, 'user_id': user_id_mapping}, inplace=True)\n",
    "\n",
    "display(interactions_df.head(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basic-meeting",
   "metadata": {},
   "source": [
    "## Get the number of items and users"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "close-massachusetts",
   "metadata": {},
   "outputs": [],
   "source": [
    "n_items = np.max(interactions_df['item_id']) + 1\n",
    "n_users = np.max(interactions_df['user_id']) + 1\n",
    "\n",
    "print(\"n_items={}\\nn_users={}\".format(n_items, n_users))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acknowledged-threshold",
   "metadata": {},
   "source": [
    "## Get the user-item interaction matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "extraordinary-mexico",
   "metadata": {},
   "outputs": [],
   "source": [
    "# mapping to int is necessary because of how iterrows works\n",
    "r = np.zeros(shape=(n_users, n_items))\n",
    "for idx, interaction in interactions_df.iterrows():\n",
    "    r[int(interaction['user_id'])][int(interaction['item_id'])] = 1\n",
    "    \n",
    "print(r)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lovely-password",
   "metadata": {},
   "source": [
    "# Dimensionality reduction"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alien-performance",
   "metadata": {},
   "source": [
    "## PCA (Principal Component Analysis)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "friendly-necklace",
   "metadata": {},
   "source": [
    "**Task 1.** Apply PCA (Principal Component Analysis) to the rows (user representations) of the interaction matrix into two dimensions. Use sklearn.decomposition.PCA. Set the transformed rows to the pca_reduced_r variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "rubber-detector",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "speaking-aberdeen",
   "metadata": {},
   "source": [
    "### Plot the reduced data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "emotional-colors",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_unique_datapoints_2d(data, tolerance=0.000001):\n",
    "    \n",
    "    max_value = np.max(np.abs(data))\n",
    "    \n",
    "    # Round the data so that points closer than tolerance are mapped into the same coordinates\n",
    "    \n",
    "    rounded_data = np.round(data, int(np.log10(1 / tolerance)))\n",
    "    \n",
    "    # Choose the first representative from each group mapped into the same coordinates\n",
    "    \n",
    "    unique_representations, indices = np.unique(rounded_data, return_index=True, axis=0)\n",
    "    \n",
    "    # Plot\n",
    "\n",
    "    fig = plt.figure(tight_layout=True)\n",
    "    fig.set_size_inches(16, 9)\n",
    "    ax1 = fig.add_subplot(1, 1, 1)\n",
    "\n",
    "    sns.scatterplot(x=data[indices, 0], y=data[indices, 1], ax=ax1)\n",
    "\n",
    "    for i in indices:\n",
    "        plt.text(x=data[i, 0] + max_value / 150, y=data[i, 1] + max_value / 150, s=i, \n",
    "                 fontdict=dict(color='red', size=8))\n",
    "\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "neural-moses",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_unique_datapoints_2d(pca_reduced_r, tolerance=0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "unusual-birmingham",
   "metadata": {},
   "source": [
    "### Print representations for chosen pairs of users close on the graph\n",
    "\n",
    "Notice that their initial represenation in the interaction matrix was also similar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "virtual-affiliate",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_representations(chosen_user_id_groups, representations, reduced_representations):\n",
    "    for user_id_group in chosen_user_id_groups:\n",
    "        for user_id in user_id_group:\n",
    "            print(\"User {} full representation and reduced representation\".format(user_id))\n",
    "            print(representations[user_id])\n",
    "            print(reduced_representations[user_id])\n",
    "            print()\n",
    "        print(\"==============================\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "duplicate-approval",
   "metadata": {},
   "outputs": [],
   "source": [
    "chosen_user_ids = [(0, 16), (133, 52), (75, 159), (279, 346), (15, 61)]\n",
    "print_representations(chosen_user_ids, r, pca_reduced_r)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "exempt-barcelona",
   "metadata": {},
   "source": [
    "### Topology of distant datapoints"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "disturbed-extraction",
   "metadata": {},
   "source": [
    "**Task 2.** Write a method which returns a pair of indices of datapoints with the highest discrepancy between the distance in the reduced space and the original distance measured as:\n",
    "\n",
    "<center>\n",
    "$$\n",
    "    \\frac{d(x_{reduced}, y_{reduced})}{\\text{max}(d(x, y), 0.001)}\n",
    "$$\n",
    "</center>\n",
    "\n",
    "where $d$ is the Euclidean distance. The interface for the method:\n",
    "\n",
    "    find_poorest_reduction(orig_data, reduced_data)\n",
    "\n",
    "Find the pair of user ids with the highest discrepancy for the PCA reduction and set those ids to pca_user_id_1 and pca_user_id_2.\n",
    "\n",
    "You can a loop over all pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "biblical-penalty",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write your code here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "annoying-wildlife",
   "metadata": {},
   "outputs": [],
   "source": [
    "pca_user_id_1, pca_user_id_2 = find_poorest_reduction(r, pca_reduced_r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fancy-constant",
   "metadata": {},
   "outputs": [],
   "source": [
    "chosen_user_ids = [(pca_user_id_1, pca_user_id_2)]\n",
    "print_representations(chosen_user_ids, r, pca_reduced_r)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "arranged-white",
   "metadata": {},
   "source": [
    "Interpretation: if the original vectors for the chosen pair are far away from each other, then this means that the reduction properly kept distances between points which were far away in the original space. Otherwise, it means that the reduction lost an important piece of topological information from the original space."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "republican-egyptian",
   "metadata": {},
   "source": [
    "## tSNE"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "collected-texas",
   "metadata": {},
   "source": [
    "**Task 3.** Apply tSNE to the rows (user representations) of the interaction matrix into two dimensions. Use sklearn.manifold.TSNE (with init='pca'). Set the transformed rows to the tsne_reduced_r variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "signal-orchestra",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "mexican-interaction",
   "metadata": {},
   "source": [
    "### Plot the reduced data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "alternate-romantic",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_unique_datapoints_2d(tsne_reduced_r, tolerance=0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "frozen-creek",
   "metadata": {},
   "source": [
    "### Print tSNE representations for chosen pairs of users close on the PCA graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "restricted-satellite",
   "metadata": {},
   "outputs": [],
   "source": [
    "chosen_user_ids = [(0, 16), (133, 52), (75, 159), (279, 346), (15, 61)]\n",
    "print_representations(chosen_user_ids, r, tsne_reduced_r)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "empty-defense",
   "metadata": {},
   "source": [
    "### Print tSNE representations for chosen pairs of users close on the tSNE graph\n",
    "\n",
    "Notice that those clusters of points represent points with exactly the same interaction vector. In PCA they were mapped into the same point, but tSNE separates all points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cheap-conjunction",
   "metadata": {},
   "outputs": [],
   "source": [
    "chosen_user_ids = [(81, 39, 120, 101), (11, 49, 288, 378), (14, 329), (150, 127, 148)]\n",
    "print_representations(chosen_user_ids, r, tsne_reduced_r)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "traditional-flood",
   "metadata": {},
   "source": [
    "### Topology of distant datapoints"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "expressed-zealand",
   "metadata": {},
   "source": [
    "**Task 4.** Find the pair of user ids with the highest discrepancy for the tSNE reduction and set those ids to tsne_user_id_1 and tsne_user_id_2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fundamental-arnold",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write your code here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "electrical-aircraft",
   "metadata": {},
   "outputs": [],
   "source": [
    "chosen_user_ids = [(tsne_user_id_1, tsne_user_id_2)]\n",
    "print_representations(chosen_user_ids, r, tsne_reduced_r)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "practical-characteristic",
   "metadata": {},
   "source": [
    "# Matrix factorization"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "elect-season",
   "metadata": {},
   "source": [
    "## SVD (Singular Value Decomposition)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "geographic-emphasis",
   "metadata": {},
   "source": [
    "**Task 5.** Implement a method for performing SVD for an arbitrary matrix and returning the two submatrices corresponding to the $k$ biggest eigenvalues - the matrix consisting of the $k$ first columns of $P$ multiplied by the matrix consisting of the first $k$ rows and columns of $\\Sigma$ (that's the first matrix in decomposition), the matrix consisting of the first $k$ columns of $Q$ (compare the lecture). For $k$ equal to None return the full decomposition. Return a tuple with both resulting matrices. \n",
    "\n",
    "Use numpy.linalg.svd to perform SVD. Note that this method does not return a diagonal matrix as the second matrix, but only a vector of singular values. To perform the matrix multiplication as suggested in the lecture you have to transform it into a diagonal matrix (for instance with np.diag). Note also that the $Q$ matrix returned by this method is already transposed (you have to revert the transposition). To make the calculations easier you can use this method with full_matrices=False. It will cut the matrices to the sizes $m \\text{x} k$, $k \\text{x} k$, $k \\text{x} n$, where $m$ is the number of rows in the original matrix, $k$ is the number of non-zero eigenvalues, $n$ is the number of columns in the original matrix.\n",
    "\n",
    "The interface of the method should have the following form:\n",
    "\n",
    "    perform_svd(r, k=None)\n",
    "\n",
    "To test the method decompose the matrix defined in the cell below for the following values of $k$: None, 6, 5, 4, 3, 2, 1, and then reconstruct the original matrix by multiplying the matrices from the decomposition. For every $k$ calculate and print the element-wise difference between the original matrix and the matrix retrieved from the decomposition and calculate and print the Euclidean distance between the matrices (take the the square of every element in the difference matrix, sum them up and take the square root - that's the same formula as for RMSE). You can also print the decomposition for every $k$ to see how it looks like.\n",
    "\n",
    "Compare the decomposition given in the lecture with the one given by your method for $k = 2$ and compare the reconstructed matrices distance to the original. Which decomposition is better (i.e. gives a closer approximation)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "analyzed-walter",
   "metadata": {},
   "outputs": [],
   "source": [
    "r_aggarwal = [\n",
    "    [1, 1, 1, 0, 0, 0],\n",
    "    [1, 1, 1, 0, 0, 0],\n",
    "    [1, 1, 1, 0, 0, 0],\n",
    "    [1, 1, 1, 1, 1, 1],\n",
    "    [-1, -1, -1, 1, 1, 1],\n",
    "    [-1, -1, 1, 1, 1, 1],\n",
    "    [-1, -1, -1, 1, 1, 1],\n",
    "]\n",
    "\n",
    "# Write your code here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "boxed-fleet",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "# Test the method\n",
    "\n",
    "# Write your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "varied-edition",
   "metadata": {},
   "source": [
    "## Application of the SVD decomposition to obtain 2D representation of users for the movielens dataset subset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "improved-horizontal",
   "metadata": {},
   "outputs": [],
   "source": [
    "svd_reduced_r, _ = perform_svd(r, k=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "knowing-alloy",
   "metadata": {},
   "source": [
    "### Plot the reduced data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "downtown-interim",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_unique_datapoints_2d(svd_reduced_r, tolerance=0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "twelve-synthesis",
   "metadata": {},
   "source": [
    "### Print representations for chosen pairs of users close on the graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "smart-distinction",
   "metadata": {},
   "outputs": [],
   "source": [
    "chosen_user_ids = [(15, 61, 213), (65, 26, 4), (413, 304), (86, 320, 505), (43, 52, 133)]\n",
    "print_representations(chosen_user_ids, r, svd_reduced_r)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eligible-mauritius",
   "metadata": {},
   "source": [
    "### Topology of distant datapoints"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "amateur-minute",
   "metadata": {},
   "outputs": [],
   "source": [
    "svd_user_id_1, svd_user_id_2 = find_poorest_reduction(r, svd_reduced_r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "elegant-spring",
   "metadata": {},
   "outputs": [],
   "source": [
    "chosen_user_ids = [(svd_user_id_1, svd_user_id_2)]\n",
    "print_representations(chosen_user_ids, r, svd_reduced_r)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "familiar-hacker",
   "metadata": {},
   "source": [
    "# Optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "indirect-tiger",
   "metadata": {},
   "source": [
    "**Task 6.** Write a method perform_sgd for performing n_steps of stochastic gradient descent (SGD) for a given alpha for a linear fit to a 2D dataset. The method should return a tuple of fitted theta_0 and theta_1. Write all the updating formulas yourself.\n",
    "\n",
    "The interface of the method should be as follows:\n",
    "    \n",
    "    perform_sgd(data, theta_0_init, theta_1_init, n_steps, alpha)\n",
    "    \n",
    "Test several initial pairs of theta_0 and theta_1, and several values of n_steps and alpha. Does the method always converge to the same solution?\n",
    "\n",
    "You can also compare your solution to the optimal one found by sklearn.linear_model.LinearRegression.\n",
    "    \n",
    "Plot the data (as scatterplot) and the fit (as lineplot) on a single seaborn chart."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "super-timer",
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.array([\n",
    "    [0.2, 0.52],\n",
    "    [0.5, 1.36],\n",
    "    [0.9, 1.00],\n",
    "    [1.3, 1.69],\n",
    "    [1.5, 2.58],\n",
    "    [2.8, 2.34]\n",
    "])\n",
    "\n",
    "# Write your code here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "realistic-conjunction",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}