1 - Baseline Estimate.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e7b20cd6-9ae3-4d70-9d1b-fd32badddbc7",
   "metadata": {},
   "source": [
    "Baseline estimates\n",
    "----------\n",
    "----------"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad877d32-1b9b-4a87-a12a-5e6e165e8340",
   "metadata": {},
   "source": [
    "Collaborative Filtering data commonly displays significant biases. Some users consistently give higher ratings than others, and some items consistently receive higher ratings. To address these biases, it's standard practice to adjust the data by incorporating 'baseline estimates.'\n",
    "\n",
    "The overall average rating is represented by $\\mu$. A baseline estimate for an unknown rating ($r_{ui}$) is denoted by $b_{ui}$ and considers the biases of the specific user ($b_{u}$) and item ($b_{i}$):"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c1b74ad-c534-46ec-944d-ba302622e9dd",
   "metadata": {},
   "source": [
    "Equation 1 $$b_{ui} = \\mu + b_u + b_i$$\n",
    "----------"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f72a86ca-12f5-4582-a999-8c17a84bd42b",
   "metadata": {},
   "source": [
    "The parameters $b_{u}$ and $b_{i}$ represent how much a particular user ('u') or item ('i') deviates from the average rating.\n",
    "\n",
    "For instance, let's consider estimating the rating of the movie \"Titanic\" by a user named \"Joe.\"\n",
    "\n",
    "- $\\mu$: the average rating across all movies is 3.7 stars.\n",
    "- $b_{i}$: \"Titanic\" is generally rated 0.5 stars higher than the average.\n",
    "- $b_{u}$: \"Joe\" tends to rate movies 0.3 stars lower than the average.\n",
    "\n",
    "Therefore, the baseline estimate for \"Joe's\" rating of \"Titanic\" would be 3.9 stars: \n",
    "\n",
    "- $b_{ui}$ = 3.7 - 0.3 + 0.5 = 3.9"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa6592c5-e2bb-4470-bf3a-85b44a6b2e5d",
   "metadata": {},
   "source": [
    "In order to estimate $b_{u}$ and $b_{i}$ one can solve the least squares problem:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3356dbf2-ec73-4f2c-89dd-69f12fa46a20",
   "metadata": {},
   "source": [
    " Equation 2 $$\\min_{b} \\sum_{(u,i) \\in K} \\left(r_{ui} - \\mu - b_u - b_i\\right)^2 + \\lambda \\left(\\sum_u b_u^2 + \\sum_i b_i^2\\right)$$\n",
    "---------------\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ce2e409-e062-4684-8622-d4a17068501f",
   "metadata": {},
   "source": [
    "Equation 2 is posed as an optimization problem, which can be divided into two parts.\n",
    "\n",
    "The first term measures the squared error between the actual and predicted ratings:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b51e3ff-a2e4-4106-b31d-fb972d8c1be5",
   "metadata": {},
   "source": [
    "$$\\min_{b} \\sum_{(u,i) \\in K} \\left(r_{ui} - \\mu - b_u - b_i\\right)^2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a0968d6-cdcc-4d1f-803b-171b6b725e68",
   "metadata": {},
   "source": [
    "Here, we want to minimize the difference between the actual score ($r_{ui}$) and the estimate based on average effects ($-\\mu - b_u - b_i$)\n",
    "\n",
    "K is the set of pairs (u,i) where ratings are available."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "857decc8-5433-4d10-b938-e49066b0df98",
   "metadata": {},
   "source": [
    "This is the second term:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "444f88c6-28b9-4864-a33b-fa4907870672",
   "metadata": {},
   "source": [
    "$$\\lambda \\left(\\sum_u b_u^2 + \\sum_i b_i^2\\right)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9adba07f-2937-4e3b-8132-853fc6f76bf6",
   "metadata": {},
   "source": [
    "This term penalizes large values of $b_u$ and $b_i$, which could overfit the training data (overfitting)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9417d9d-b25e-409f-bf4b-0b70f78fd8c0",
   "metadata": {},
   "source": [
    "$\\lambda$ is a regularization parameter that controls the weight of this penalty. A larger $\\lambda$ means less flexibility, but less risk of overfitting."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b528f26e-7b71-45e6-9130-a6b696adf517",
   "metadata": {},
   "source": [
    "Let's see how the optimization process works\n",
    "--------------\n",
    "-------------\n",
    "\n",
    "To optimize the parameters $b_u$ and $b_i$, we take the partial derivatives of L with respect to each one.\n",
    "\n",
    "The L function is the loss function that we want to minimize using optimization techniques such as gradient descent. By differentiating L with respect to parameters $b_u$ and $b_i$, we obtain the formulas necessary to update these parameters in a way that best fits the data.\n",
    "\n",
    "### 1. The loss function\n",
    "$ L $ is defined as:\n",
    "$$\n",
    "L = \\sum_{(u, i) \\in K} \\left( r_{ui} - \\mu - b_u - b_i \\right)^2 + \\lambda \\left( \\sum_u b_u^2 + \\sum_i b_i^2 \\right).\n",
    "$$\n",
    "\n",
    "We have already explained the different parts of $L$\n",
    "\n",
    "### 2. Partial derivative of $ L $ with respect to $ b_u$\n",
    "To calculate the partial derivative of $L$ with respect to $b_u$, we take only the terms that depend on $b_u$:\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial b_u} = \\frac{\\partial}{\\partial b_u} \\sum_{(u, i) \\in K} \\left( r_{ui} - \\mu - b_u - b_i \\right)^2 + \\frac{\\partial}{\\partial b_u} \\lambda \\sum_u b_u^2.\n",
    "$$\n",
    "\n",
    "#### Quadratic error term:\n",
    "#### Step 1: Apply the chain rule\n",
    "The first term is a square, so we apply the chain rule. The derivative of a quadratic function $ f(x) = g(x)^2 $ is:\n",
    "$$\n",
    "\\frac{\\partial}{\\partial x} g(x)^2 = 2 \\cdot g(x) \\cdot \\frac{\\partial g(x)}{\\partial x}.\n",
    "$$\n",
    "\n",
    "In this case, we define:\n",
    "$$\n",
    "g(x) = r_{ui} - \\mu - b_u - b_i.\n",
    "$$\n",
    "\n",
    "Therefore, when deriving:\n",
    "$$\n",
    "\\frac{\\partial}{\\partial b_u} \\left( r_{ui} - \\mu - b_u - b_i \\right)^2 = 2 \\cdot \\left( r_{ui} - \\mu - b_u - b_i \\right) \\cdot \\frac{\\partial}{\\partial b_u} \\left( r_{ui} - \\mu - b_u - b_i \\right).\n",
    "$$\n",
    "\n",
    "#### Step 2: Differentiate $ g(x) $ with respect to $ b_u $\n",
    "The expression $g(x) = r_{ui} - \\mu - b_u - b_i $ is a sum of terms. We differentiate each term with respect to $b_u$:\n",
    "\n",
    "- $r_{ui}$: It is a constant, its derivative is $0$.\n",
    "- $ \\mu $: It is a constant, its derivative is $ 0 $.\n",
    "- $b_u$: Its derivative with respect to itself is $1$.\n",
    "- $b_i$: It is a constant with respect to $b_u$, its derivative is $0$.\n",
    "\n",
    "So:\n",
    "$$\n",
    "\\frac{\\partial}{\\partial b_u} \\left( r_{ui} - \\mu - b_u - b_i \\right) = -1.\n",
    "$$\n",
    "\n",
    "#### Step 3: Substitute into the chain rule\n",
    "By substituting the derivative into the chain rule, we obtain:\n",
    "$$\n",
    "\\frac{\\partial}{\\partial b_u} \\left( r_{ui} - \\mu - b_u - b_i \\right)^2 = 2 \\cdot \\left( r_{ui} - \\mu - b_u - b_i \\right) \\cdot (-1).\n",
    "$$\n",
    "\n",
    "The term $-1$ comes specifically from the derivative of $-b_u$ with respect to $b_u$.\n",
    "\n",
    "This results in:\n",
    "$$\n",
    "-2 \\sum_{(u, i) \\in K} \\left( r_{ui} - \\mu - b_u - b_i \\right).\n",
    "$$\n",
    "\n",
    "#### Regularization term:\n",
    "The second term penalizes large values ​​of $b_u$. Its derivative is:\n",
    "$$\n",
    "\\frac{\\partial}{\\partial b_u} \\lambda \\sum_u b_u^2 = 2 \\lambda b_u.\n",
    "$$\n",
    "\n",
    "#### Combined formula:\n",
    "By combining both terms, we obtain:\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial b_u} = -2 \\sum_{(u, i) \\in K} \\left( r_{ui} - \\mu - b_u - b_i \\right) + 2 \\lambda b_u.\n",
    "$$\n",
    "\n",
    "### 3. Simplified partial derivative with the error variable\n",
    "If we define the error as:\n",
    "$$\n",
    "\\text{error} = r_{ui} - \\mu - b_u - b_i,\n",
    "$$\n",
    "The derivative simplifies to:\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial b_u} = -2 \\cdot \\text{error} + 2 \\lambda b_u.\n",
    "$$\n",
    "\n",
    "### 4. Partial derivative with respect to $b_i$\n",
    "The reasoning for \\( b_i \\) is symmetric. The partial derivative is:\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial b_i} = -2 \\cdot \\text{error} + 2 \\lambda b_i.\n",
    "$$\n",
    "\n",
    "These derivatives guide the gradient descent to fit $b_u$ and $b_i$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cda6678-94de-465f-a804-b81f375ab227",
   "metadata": {},
   "source": [
    "Optimizing $b_u $ and $ b_i $ with Gradient Descent\n",
    "-------------\n",
    "-----------\n",
    "\n",
    "### Gradient Descent Steps\n",
    "Now that we have the derivatives, we can perform gradient descent to optimize $ b_u $ and $ b_i $.\n",
    "\n",
    "#### (a) Initialization:\n",
    "- Initialize $ b_u $ and $ b_i $ to small random values or zeros.\n",
    "\n",
    "#### (b) Update rules:\n",
    "Using the gradient descent update formula:\n",
    "$$\n",
    "b_u \\gets b_u - \\eta \\cdot \\frac{\\partial L}{\\partial b_u},\n",
    "$$\n",
    "$$\n",
    "b_i \\gets b_i - \\eta \\cdot \\frac{\\partial L}{\\partial b_i}.\n",
    "$$\n",
    "Here, $ \\eta $ is the learning rate.\n",
    "\n",
    "#### (c) Substitute the derivatives:\n",
    "Substitute the partial derivatives:\n",
    "$$\n",
    "b_u \\gets b_u + \\eta \\cdot \\left( 2 \\sum_{(u, i) \\in K} \\left( r_{ui} - \\mu - b_u - b_i \\right) - 2 \\lambda b_u \\right),\n",
    "$$\n",
    "$$\n",
    "b_i \\gets b_i + \\eta \\cdot \\left( 2 \\sum_{(u, i) \\in K} \\left( r_{ui} - \\mu - b_u - b_i \\right) - 2 \\lambda b_i \\right).\n",
    "$$\n",
    "\n",
    "#### (d) Iterate:\n",
    "- Repeat the updates for a fixed number of iterations or until convergence (when changes in $ b_u $ and $ b_i $ are below a threshold).\n",
    "\n",
    "---\n",
    "\n",
    "### 5. Error interpretation\n",
    "The term $ r_{ui} - \\mu - b_u - b_i $ is the prediction error for a specific user $ u $ and item $ i $. Gradient descent minimizes this error while penalizing large values of $ b_u $ and $ b_i $ through the regularization term.\n",
    "\n",
    "By iteratively applying these updates, the model adjusts $ b_u $ and $ b_i $ to better fit the data.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c296153b-e74b-4ebb-a224-d79ad358dccc",
   "metadata": {},
   "source": [
    "Practical Implementation\n",
    "----------\n",
    "---------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "42029ba1-7625-4a55-a692-1be86dbd4ffc",
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Collecting scikit-surpriseNote: you may need to restart the kernel to use updated packages.\n",
      "\n",
      "  Downloading scikit_surprise-1.1.4.tar.gz (154 kB)\n",
      "     -------------------------------------- 154.4/154.4 kB 2.3 MB/s eta 0:00:00\n",
      "  Installing build dependencies: started\n",
      "  Installing build dependencies: finished with status 'done'\n",
      "  Getting requirements to build wheel: started\n",
      "  Getting requirements to build wheel: finished with status 'done'\n",
      "  Preparing metadata (pyproject.toml): started\n",
      "  Preparing metadata (pyproject.toml): finished with status 'done'\n",
      "Collecting joblib>=1.2.0\n",
      "  Downloading joblib-1.4.2-py3-none-any.whl (301 kB)\n",
      "     -------------------------------------- 301.8/301.8 kB 9.4 MB/s eta 0:00:00\n",
      "Requirement already satisfied: scipy>=1.6.0 in c:\\users\\brods\\anaconda3\\lib\\site-packages (from scikit-surprise) (1.10.0)\n",
      "Requirement already satisfied: numpy>=1.19.5 in c:\\users\\brods\\anaconda3\\lib\\site-packages (from scikit-surprise) (1.23.5)\n",
      "Building wheels for collected packages: scikit-surprise\n",
      "  Building wheel for scikit-surprise (pyproject.toml): started\n",
      "  Building wheel for scikit-surprise (pyproject.toml): finished with status 'done'\n",
      "  Created wheel for scikit-surprise: filename=scikit_surprise-1.1.4-cp310-cp310-win_amd64.whl size=1296412 sha256=9e182d89f56eae762d11be4438b8aeb5d503a73501c680e7d264c743cd1a6db4\n",
      "  Stored in directory: c:\\users\\brods\\appdata\\local\\pip\\cache\\wheels\\8a\\ec\\b2\\58c47d2432188873013470d86ba25e2fc8d3d4e249ec625889\n",
      "Successfully built scikit-surprise\n",
      "Installing collected packages: joblib, scikit-surprise\n",
      "  Attempting uninstall: joblib\n",
      "    Found existing installation: joblib 1.1.1\n",
      "    Uninstalling joblib-1.1.1:\n",
      "      Successfully uninstalled joblib-1.1.1\n",
      "Successfully installed joblib-1.4.2 scikit-surprise-1.1.4\n"
     ]
    }
   ],
   "source": [
    "pip install scikit-surprise"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a908dc95-e34a-4183-bba4-7d1f5cf2dc02",
   "metadata": {},
   "source": [
    "This Python code implements a collaborative filtering model for movie recommendations using the MovieLens dataset.\n",
    "\n",
    "The MovieLens 100K Dataset is a stable benchmark. It contains 100,000 ratings from 1000 users on 1700 movies and was released in 1998.\n",
    "\n",
    "In this code, the model trains user and item biases through gradient descent and evaluates its performance based on RMSE (Root Mean Squared Error)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "eb3be333-d5d9-4dcb-9165-830ae73e128c",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 1/20, RMSE: 1.0909\n",
      "Epoch 2/20, RMSE: 1.0904\n",
      "Epoch 3/20, RMSE: 1.0903\n",
      "Epoch 4/20, RMSE: 1.0902\n",
      "Epoch 5/20, RMSE: 1.0901\n",
      "Epoch 6/20, RMSE: 1.0901\n",
      "Epoch 7/20, RMSE: 1.0901\n",
      "Epoch 8/20, RMSE: 1.0901\n",
      "Epoch 9/20, RMSE: 1.0901\n",
      "Epoch 10/20, RMSE: 1.0901\n",
      "Epoch 11/20, RMSE: 1.0900\n",
      "Epoch 12/20, RMSE: 1.0900\n",
      "Epoch 13/20, RMSE: 1.0900\n",
      "Epoch 14/20, RMSE: 1.0900\n",
      "Epoch 15/20, RMSE: 1.0900\n",
      "Epoch 16/20, RMSE: 1.0900\n",
      "Epoch 17/20, RMSE: 1.0900\n",
      "Epoch 18/20, RMSE: 1.0900\n",
      "Epoch 19/20, RMSE: 1.0900\n",
      "Epoch 20/20, RMSE: 1.0900\n",
      "Test RMSE: 1.1291\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from surprise import Dataset\n",
    "from surprise.model_selection import train_test_split\n",
    "\n",
    "# Load the MovieLens dataset provided by the Surprise library\n",
    "data = Dataset.load_builtin('ml-100k')\n",
    "trainset, testset = train_test_split(data, test_size=0.2) #the data is split into training and testing sets, using an 80/20 ratio\n",
    "\n",
    "# Initialize parameters\n",
    "mu = np.mean([r for (_, _, r) in trainset.all_ratings()])  # Global average rating\n",
    "lambda_reg = 10  # Regularization parameter to prevent overfitting\n",
    "learning_rate = 0.01  # Learning rate for gradient descent\n",
    "num_epochs = 20  # Number of epochs for training\n",
    "\n",
    "# Initialize user and item biases to zero\n",
    "users = trainset.all_users()\n",
    "items = trainset.all_items()\n",
    "b_u = np.zeros(trainset.n_users)  # User biases\n",
    "b_i = np.zeros(trainset.n_items)  # Item biases\n",
    "\n",
    "# Training using gradient descent\n",
    "for epoch in range(num_epochs):\n",
    "    for u, i, r_ui in trainset.all_ratings():\n",
    "        u, i = int(u), int(i)\n",
    "\n",
    "        # Compute the error between the actual rating and the predicted rating\n",
    "        pred = mu + b_u[u] + b_i[i]\n",
    "        error = r_ui - pred\n",
    "\n",
    "        # Update user and item biases using gradient descent\n",
    "        b_u[u] += 2 * learning_rate * (error - lambda_reg * b_u[u])\n",
    "        b_i[i] += 2 * learning_rate * (error - lambda_reg * b_i[i])\n",
    "\n",
    "    # Calculate RMSE on the training set\n",
    "    train_rmse = np.sqrt(np.mean([\n",
    "        (r_ui - (mu + b_u[int(u)] + b_i[int(i)]))**2\n",
    "        for u, i, r_ui in trainset.all_ratings()\n",
    "    ]))\n",
    "    print(f\"Epoch {epoch + 1}/{num_epochs}, RMSE: {train_rmse:.4f}\")\n",
    "\n",
    "# Prediction function for the test set\n",
    "def predict(user, item):\n",
    "    \"\"\"Predict the rating for a given user and item.\"\"\"\n",
    "    user_bias = b_u[user] if user < len(b_u) else 0\n",
    "    item_bias = b_i[item] if item < len(b_i) else 0\n",
    "    return mu + user_bias + item_bias\n",
    "\n",
    "# Compute RMSE on the test set\n",
    "test_rmse = np.sqrt(np.mean([\n",
    "    (r_ui - predict(int(u), int(i)))**2\n",
    "    for u, i, r_ui in testset\n",
    "]))\n",
    "print(f\"Test RMSE: {test_rmse:.4f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13847b4b-8006-420f-bf0c-b34d9ed91bdf",
   "metadata": {},
   "source": [
    "The results suggest that the model is not learning significantly after the first few iterations.\n",
    "\n",
    "**Some points to keep in mind**\n",
    "\n",
    "*1 - The RMSE on the training set*\n",
    "\n",
    "The RMSE converges quickly and remains constant from the beginning. This could be due to:\n",
    "- A high value of lambda regularization ($\\lambda$) that restricts changes in $b_u$ and $b_i$ too much\n",
    "- An insufficient step size ($\\eta$), leading to slow and small updates to the parameters.\n",
    "- A limited representation of the model, since you only adjust for biases without latent factors that can model more complex interactions between users and items (this is Koren's article main idea)\n",
    "\n",
    "*2 -  The difference between the train and test set in the RMSE*\n",
    "\n",
    "- The difference between the RMSE of training (∼1.0900) and test (∼1.1291) indicates possible overfitting to the training set.\n",
    "- Although this is not severe, a more robust model with tight regularization could improve generalization."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bdb705dc-cc82-4734-8ca2-4666c45c5f62",
   "metadata": {},
   "source": [
    "# Hyperparameter optimization\n",
    "\n",
    "In the first version of the code, we used only a combination of hyperparameters. In a real situation, choosing the most appropriate values for these elements requires careful research.\n",
    "\n",
    "In this version of the code we implement a new strategy:\n",
    "- A grid search is conducted over combinations of learning rates and regularization strengths\n",
    "- For each combination, the model is trained, and the RMSE is calculated on both the training and test sets.\n",
    "- The combination that minimizes test RMSE is recorded as the best configuration.\n",
    "- Finally, it reports the best hyperparameters and the corresponding RMSE test."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b847473f-ecd5-4219-8779-b60398398b67",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing combination: learning_rate=0.005, lambda_reg=1\n",
      "Epoch 1/20, Train RMSE: 1.0031\n",
      "Epoch 2/20, Train RMSE: 0.9892\n",
      "Epoch 3/20, Train RMSE: 0.9835\n",
      "Epoch 4/20, Train RMSE: 0.9802\n",
      "Epoch 5/20, Train RMSE: 0.9782\n",
      "Epoch 6/20, Train RMSE: 0.9768\n",
      "Epoch 7/20, Train RMSE: 0.9758\n",
      "Epoch 8/20, Train RMSE: 0.9751\n",
      "Epoch 9/20, Train RMSE: 0.9745\n",
      "Epoch 10/20, Train RMSE: 0.9740\n",
      "Epoch 11/20, Train RMSE: 0.9737\n",
      "Epoch 12/20, Train RMSE: 0.9733\n",
      "Epoch 13/20, Train RMSE: 0.9731\n",
      "Epoch 14/20, Train RMSE: 0.9729\n",
      "Epoch 15/20, Train RMSE: 0.9727\n",
      "Epoch 16/20, Train RMSE: 0.9725\n",
      "Epoch 17/20, Train RMSE: 0.9724\n",
      "Epoch 18/20, Train RMSE: 0.9722\n",
      "Epoch 19/20, Train RMSE: 0.9721\n",
      "Epoch 20/20, Train RMSE: 0.9720\n",
      "Train RMSE: 0.9720, Test RMSE: 1.1709\n",
      "Testing combination: learning_rate=0.005, lambda_reg=10\n",
      "Epoch 1/20, Train RMSE: 1.0927\n",
      "Epoch 2/20, Train RMSE: 1.0918\n",
      "Epoch 3/20, Train RMSE: 1.0915\n",
      "Epoch 4/20, Train RMSE: 1.0913\n",
      "Epoch 5/20, Train RMSE: 1.0912\n",
      "Epoch 6/20, Train RMSE: 1.0911\n",
      "Epoch 7/20, Train RMSE: 1.0911\n",
      "Epoch 8/20, Train RMSE: 1.0910\n",
      "Epoch 9/20, Train RMSE: 1.0910\n",
      "Epoch 10/20, Train RMSE: 1.0910\n",
      "Epoch 11/20, Train RMSE: 1.0909\n",
      "Epoch 12/20, Train RMSE: 1.0909\n",
      "Epoch 13/20, Train RMSE: 1.0909\n",
      "Epoch 14/20, Train RMSE: 1.0909\n",
      "Epoch 15/20, Train RMSE: 1.0909\n",
      "Epoch 16/20, Train RMSE: 1.0909\n",
      "Epoch 17/20, Train RMSE: 1.0909\n",
      "Epoch 18/20, Train RMSE: 1.0909\n",
      "Epoch 19/20, Train RMSE: 1.0909\n",
      "Epoch 20/20, Train RMSE: 1.0908\n",
      "Train RMSE: 1.0908, Test RMSE: 1.1274\n",
      "Testing combination: learning_rate=0.005, lambda_reg=20\n",
      "Epoch 1/20, Train RMSE: 1.1077\n",
      "Epoch 2/20, Train RMSE: 1.1074\n",
      "Epoch 3/20, Train RMSE: 1.1073\n",
      "Epoch 4/20, Train RMSE: 1.1072\n",
      "Epoch 5/20, Train RMSE: 1.1072\n",
      "Epoch 6/20, Train RMSE: 1.1072\n",
      "Epoch 7/20, Train RMSE: 1.1072\n",
      "Epoch 8/20, Train RMSE: 1.1072\n",
      "Epoch 9/20, Train RMSE: 1.1071\n",
      "Epoch 10/20, Train RMSE: 1.1071\n",
      "Epoch 11/20, Train RMSE: 1.1071\n",
      "Epoch 12/20, Train RMSE: 1.1071\n",
      "Epoch 13/20, Train RMSE: 1.1071\n",
      "Epoch 14/20, Train RMSE: 1.1071\n",
      "Epoch 15/20, Train RMSE: 1.1071\n",
      "Epoch 16/20, Train RMSE: 1.1071\n",
      "Epoch 17/20, Train RMSE: 1.1071\n",
      "Epoch 18/20, Train RMSE: 1.1071\n",
      "Epoch 19/20, Train RMSE: 1.1071\n",
      "Epoch 20/20, Train RMSE: 1.1071\n",
      "Train RMSE: 1.1071, Test RMSE: 1.1269\n",
      "Testing combination: learning_rate=0.01, lambda_reg=1\n",
      "Epoch 1/20, Train RMSE: 0.9916\n",
      "Epoch 2/20, Train RMSE: 0.9833\n",
      "Epoch 3/20, Train RMSE: 0.9800\n",
      "Epoch 4/20, Train RMSE: 0.9783\n",
      "Epoch 5/20, Train RMSE: 0.9773\n",
      "Epoch 6/20, Train RMSE: 0.9766\n",
      "Epoch 7/20, Train RMSE: 0.9761\n",
      "Epoch 8/20, Train RMSE: 0.9758\n",
      "Epoch 9/20, Train RMSE: 0.9755\n",
      "Epoch 10/20, Train RMSE: 0.9753\n",
      "Epoch 11/20, Train RMSE: 0.9751\n",
      "Epoch 12/20, Train RMSE: 0.9750\n",
      "Epoch 13/20, Train RMSE: 0.9748\n",
      "Epoch 14/20, Train RMSE: 0.9747\n",
      "Epoch 15/20, Train RMSE: 0.9746\n",
      "Epoch 16/20, Train RMSE: 0.9746\n",
      "Epoch 17/20, Train RMSE: 0.9745\n",
      "Epoch 18/20, Train RMSE: 0.9744\n",
      "Epoch 19/20, Train RMSE: 0.9744\n",
      "Epoch 20/20, Train RMSE: 0.9743\n",
      "Train RMSE: 0.9743, Test RMSE: 1.1739\n",
      "Testing combination: learning_rate=0.01, lambda_reg=10\n",
      "Epoch 1/20, Train RMSE: 1.0927\n",
      "Epoch 2/20, Train RMSE: 1.0923\n",
      "Epoch 3/20, Train RMSE: 1.0921\n",
      "Epoch 4/20, Train RMSE: 1.0921\n",
      "Epoch 5/20, Train RMSE: 1.0920\n",
      "Epoch 6/20, Train RMSE: 1.0920\n",
      "Epoch 7/20, Train RMSE: 1.0919\n",
      "Epoch 8/20, Train RMSE: 1.0919\n",
      "Epoch 9/20, Train RMSE: 1.0919\n",
      "Epoch 10/20, Train RMSE: 1.0919\n",
      "Epoch 11/20, Train RMSE: 1.0919\n",
      "Epoch 12/20, Train RMSE: 1.0919\n",
      "Epoch 13/20, Train RMSE: 1.0919\n",
      "Epoch 14/20, Train RMSE: 1.0919\n",
      "Epoch 15/20, Train RMSE: 1.0919\n",
      "Epoch 16/20, Train RMSE: 1.0919\n",
      "Epoch 17/20, Train RMSE: 1.0919\n",
      "Epoch 18/20, Train RMSE: 1.0919\n",
      "Epoch 19/20, Train RMSE: 1.0919\n",
      "Epoch 20/20, Train RMSE: 1.0919\n",
      "Train RMSE: 1.0919, Test RMSE: 1.1281\n",
      "Testing combination: learning_rate=0.01, lambda_reg=20\n",
      "Epoch 1/20, Train RMSE: 1.1077\n",
      "Epoch 2/20, Train RMSE: 1.1076\n",
      "Epoch 3/20, Train RMSE: 1.1076\n",
      "Epoch 4/20, Train RMSE: 1.1075\n",
      "Epoch 5/20, Train RMSE: 1.1075\n",
      "Epoch 6/20, Train RMSE: 1.1075\n",
      "Epoch 7/20, Train RMSE: 1.1075\n",
      "Epoch 8/20, Train RMSE: 1.1075\n",
      "Epoch 9/20, Train RMSE: 1.1075\n",
      "Epoch 10/20, Train RMSE: 1.1075\n",
      "Epoch 11/20, Train RMSE: 1.1075\n",
      "Epoch 12/20, Train RMSE: 1.1075\n",
      "Epoch 13/20, Train RMSE: 1.1075\n",
      "Epoch 14/20, Train RMSE: 1.1075\n",
      "Epoch 15/20, Train RMSE: 1.1075\n",
      "Epoch 16/20, Train RMSE: 1.1075\n",
      "Epoch 17/20, Train RMSE: 1.1075\n",
      "Epoch 18/20, Train RMSE: 1.1075\n",
      "Epoch 19/20, Train RMSE: 1.1075\n",
      "Epoch 20/20, Train RMSE: 1.1075\n",
      "Train RMSE: 1.1075, Test RMSE: 1.1273\n",
      "Testing combination: learning_rate=0.05, lambda_reg=1\n",
      "Epoch 1/20, Train RMSE: 1.0004\n",
      "Epoch 2/20, Train RMSE: 0.9987\n",
      "Epoch 3/20, Train RMSE: 0.9981\n",
      "Epoch 4/20, Train RMSE: 0.9978\n",
      "Epoch 5/20, Train RMSE: 0.9976\n",
      "Epoch 6/20, Train RMSE: 0.9975\n",
      "Epoch 7/20, Train RMSE: 0.9974\n",
      "Epoch 8/20, Train RMSE: 0.9974\n",
      "Epoch 9/20, Train RMSE: 0.9973\n",
      "Epoch 10/20, Train RMSE: 0.9973\n",
      "Epoch 11/20, Train RMSE: 0.9973\n",
      "Epoch 12/20, Train RMSE: 0.9973\n",
      "Epoch 13/20, Train RMSE: 0.9972\n",
      "Epoch 14/20, Train RMSE: 0.9972\n",
      "Epoch 15/20, Train RMSE: 0.9972\n",
      "Epoch 16/20, Train RMSE: 0.9972\n",
      "Epoch 17/20, Train RMSE: 0.9972\n",
      "Epoch 18/20, Train RMSE: 0.9972\n",
      "Epoch 19/20, Train RMSE: 0.9972\n",
      "Epoch 20/20, Train RMSE: 0.9972\n",
      "Train RMSE: 0.9972, Test RMSE: 1.1911\n",
      "Testing combination: learning_rate=0.05, lambda_reg=10\n",
      "Epoch 1/20, Train RMSE: 1.1007\n",
      "Epoch 2/20, Train RMSE: 1.1007\n",
      "Epoch 3/20, Train RMSE: 1.1007\n",
      "Epoch 4/20, Train RMSE: 1.1007\n",
      "Epoch 5/20, Train RMSE: 1.1007\n",
      "Epoch 6/20, Train RMSE: 1.1007\n",
      "Epoch 7/20, Train RMSE: 1.1007\n",
      "Epoch 8/20, Train RMSE: 1.1007\n",
      "Epoch 9/20, Train RMSE: 1.1007\n",
      "Epoch 10/20, Train RMSE: 1.1007\n",
      "Epoch 11/20, Train RMSE: 1.1007\n",
      "Epoch 12/20, Train RMSE: 1.1007\n",
      "Epoch 13/20, Train RMSE: 1.1007\n",
      "Epoch 14/20, Train RMSE: 1.1007\n",
      "Epoch 15/20, Train RMSE: 1.1007\n",
      "Epoch 16/20, Train RMSE: 1.1007\n",
      "Epoch 17/20, Train RMSE: 1.1007\n",
      "Epoch 18/20, Train RMSE: 1.1007\n",
      "Epoch 19/20, Train RMSE: 1.1007\n",
      "Epoch 20/20, Train RMSE: 1.1007\n",
      "Train RMSE: 1.1007, Test RMSE: 1.1326\n",
      "Testing combination: learning_rate=0.05, lambda_reg=20\n",
      "Epoch 1/20, Train RMSE: 13.7788\n",
      "Epoch 2/20, Train RMSE: 14.0201\n",
      "Epoch 3/20, Train RMSE: 14.0640\n",
      "Epoch 4/20, Train RMSE: 14.0865\n",
      "Epoch 5/20, Train RMSE: 14.0975\n",
      "Epoch 6/20, Train RMSE: 14.1072\n",
      "Epoch 7/20, Train RMSE: 14.1101\n",
      "Epoch 8/20, Train RMSE: 14.1125\n",
      "Epoch 9/20, Train RMSE: 14.1142\n",
      "Epoch 10/20, Train RMSE: 14.1144\n",
      "Epoch 11/20, Train RMSE: 14.1159\n",
      "Epoch 12/20, Train RMSE: 14.1158\n",
      "Epoch 13/20, Train RMSE: 14.1163\n",
      "Epoch 14/20, Train RMSE: 14.1169\n",
      "Epoch 15/20, Train RMSE: 14.1170\n",
      "Epoch 16/20, Train RMSE: 14.1176\n",
      "Epoch 17/20, Train RMSE: 14.1175\n",
      "Epoch 18/20, Train RMSE: 14.1179\n",
      "Epoch 19/20, Train RMSE: 14.1178\n",
      "Epoch 20/20, Train RMSE: 14.1182\n",
      "Train RMSE: 14.1182, Test RMSE: 14.1043\n",
      "\n",
      "Best hyperparameters: learning_rate=0.005, lambda_reg=20\n",
      "Test RMSE with best parameters: 1.1269\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from surprise import Dataset\n",
    "from surprise.model_selection import train_test_split\n",
    "from itertools import product\n",
    "\n",
    "# Load the MovieLens dataset\n",
    "data = Dataset.load_builtin('ml-100k')\n",
    "trainset, testset = train_test_split(data, test_size=0.2)\n",
    "\n",
    "# Training and evaluation function\n",
    "def train_and_evaluate(trainset, testset, learning_rate, lambda_reg, num_epochs=20):\n",
    "    # Global mean of all ratings\n",
    "    mu = np.mean([r for (_, _, r) in trainset.all_ratings()])\n",
    "\n",
    "    # Initialize biases for users and items\n",
    "    b_u = np.zeros(trainset.n_users)\n",
    "    b_i = np.zeros(trainset.n_items)\n",
    "\n",
    "    # Training loop with gradient descent\n",
    "    for epoch in range(num_epochs):\n",
    "        for u, i, r_ui in trainset.all_ratings():\n",
    "            u, i = int(u), int(i)\n",
    "\n",
    "            # Calculate prediction and error\n",
    "            pred = mu + b_u[u] + b_i[i]\n",
    "            error = r_ui - pred\n",
    "\n",
    "            # Update user and item biases with gradient descent\n",
    "            b_u[u] += 2 * learning_rate * (error - lambda_reg * b_u[u])\n",
    "            b_i[i] += 2 * learning_rate * (error - lambda_reg * b_i[i])\n",
    "\n",
    "            # Clip the values of b_u and b_i to avoid overflow\n",
    "            b_u[u] = np.clip(b_u[u], -10, 10)\n",
    "            b_i[i] = np.clip(b_i[i], -10, 10)\n",
    "\n",
    "        # Calculate train RMSE for each epoch\n",
    "        train_rmse = np.sqrt(np.mean([\n",
    "            (r_ui - (mu + b_u[int(u)] + b_i[int(i)]))**2\n",
    "            for u, i, r_ui in trainset.all_ratings()\n",
    "        ]))\n",
    "        print(f\"Epoch {epoch + 1}/{num_epochs}, Train RMSE: {train_rmse:.4f}\")\n",
    "\n",
    "    # Prediction function for test data\n",
    "    def predict(user, item):\n",
    "        user_bias = b_u[user] if user < len(b_u) else 0\n",
    "        item_bias = b_i[item] if item < len(b_i) else 0\n",
    "        return mu + user_bias + item_bias\n",
    "\n",
    "    # Calculate test RMSE\n",
    "    test_rmse = np.sqrt(np.mean([\n",
    "        (r_ui - predict(int(u), int(i)))**2\n",
    "        for u, i, r_ui in testset\n",
    "    ]))\n",
    "\n",
    "    return train_rmse, test_rmse\n",
    "\n",
    "# Grid search parameters\n",
    "learning_rates = [0.005, 0.01, 0.05]\n",
    "regularizations = [1, 10, 20]\n",
    "num_epochs = 20\n",
    "\n",
    "# Variables to store the best parameters\n",
    "best_params = None\n",
    "best_test_rmse = float('inf')\n",
    "\n",
    "# Test all combinations of hyperparameters\n",
    "for lr, reg in product(learning_rates, regularizations):\n",
    "    print(f\"Testing combination: learning_rate={lr}, lambda_reg={reg}\")\n",
    "    train_rmse, test_rmse = train_and_evaluate(trainset, testset, lr, reg, num_epochs)\n",
    "    print(f\"Train RMSE: {train_rmse:.4f}, Test RMSE: {test_rmse:.4f}\")\n",
    "\n",
    "    # Save the best parameters based on test RMSE\n",
    "    if test_rmse < best_test_rmse:\n",
    "        best_test_rmse = test_rmse\n",
    "        best_params = (lr, reg)\n",
    "\n",
    "print(f\"\\nBest hyperparameters: learning_rate={best_params[0]}, lambda_reg={best_params[1]}\")\n",
    "print(f\"Test RMSE with best parameters: {best_test_rmse:.4f}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4557bbb4-bf34-4884-a12e-86faee80892b",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}