{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TP Reco n°2 : factorisation de matrices (ALS, SGD)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Le filtrage collaboratif classique n'est pas, dans certaines formes, du _machine learning_, dans la mesure où l'on ne spécifie pas explicitement une fonction que l'on cherche à maximiser ou minimiser. Dans cette partie, nous allons aborder la factorisation de matrices avec laquelle on apprend effectivement les paramètres d'un modèle en vue de minimiser directement une fonction. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Préliminaires"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On va réutiliser les données de la séance précédente (Movielens). On disposera donc d'une matrice utilisateurs-films, avec des notes d'utilisateurs sur les films.\n",
"La factorisation de matrice suppose que :\n",
"- chaque utilisateur peut être décrit par $k$ attributs (par exemple : à quel point il/elle apprécie les films historiques\n",
"- chaque film peut être décrit par un ensemble de $k$ caractéristiques. Pour correspondre à l'exemple ci-dessus, une caractéristique pourrait indiquer à quel point un film est proche de la catégorie \"film historiques\"\n",
"- si on multiplie les caractéristiques des utilisateurs par celles des films (et fait les sommes adéquates), on aura une approximation raisonnable de l'évaluation d'un utilisateur pour un film"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ce qui est intéressant, c'est que l'on ne sait pas quelles sont ces caractéristiques, ni même combien d'entre elles sont pertinentes. On choisit un nombre $k$, et l'on apprend les valeurs des caractéristiques pour les utilisateurs et les films, en minimisant une fonction de perte."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Si notre utilisateur est représenté par un vecteur de dimension $k$ $\\textbf{x}_{u}$ et un item par un vecteur de dimension $k$ $\\textbf{y}_{i}$, la note prédite pour l'item par l'utilisateur est : \n",
"\n",
"$$\\hat r_{ui} = \\textbf{x}_{u}^{\\intercal} \\cdot{} \\textbf{y}_{i} = \\sum\\limits_{k} x_{uk}y_{ki}$$\n",
"\n",
"où $\\hat r_{ui}$ représente la prédiction de la vraie note $r_{ui}$. $\\textbf{y}_{i}$ est un vecteur colonne, $\\textbf{x}_{u}^{\\intercal}$ un vecteur ligne. On les appelle en général \"vecteurs latents\". Les *k* attributs sont les facteurs latents."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On cherche à minimiser le carré de la différence entre les notes de notre jeu de données et nos prédictions. La fonction à la forme suivante :\n",
"\n",
"$$L = \\sum\\limits_{u,i \\in S}(r_{ui} - \\textbf{x}_{u}^{\\intercal} \\cdot{} \\textbf{y}_{i})^{2} + \\lambda_{x} \\sum\\limits_{u} \\left\\Vert \\textbf{x}_{u} \\right\\Vert^{2} + \\lambda_{y} \\sum\\limits_{u} \\left\\Vert \\textbf{y}_{i} \\right\\Vert^{2}$$\n",
"\n",
"On ajoute deux termes de régularisation L2 pour limiter le sur-apprentissage (overfitting) des utilisateurs et des items. On va s'intéresser à deux manières de minimiser, à l'aide de l'ALS (Alternate Least Squares) et d'une SGD (Stochastic gradient descent)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## ALS\n",
"\n",
"Pour réaliser l'ALS, on fixe les valeurs d'un ensemble de vecteurs latents. Nous allons par exemple garder constants les vecteurs d'items. On cherche qaund la dérivée vaut 0, et on résout pour les vecteurs non constants (utilisateurs). Vient maintenant l'alternance : on va maintenant fixer ces nouveaux vecteurs utilisateurs, pour lesquels on a résolu l'équation, prendre la dérivée de la loss par rapport aux vecteurs anciennement constants. On fera cette alternance successivement jusqu'à convergence.\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Derivation\n",
"\n",
"Plus précisément : \n",
"\n",
"$$\\frac{\\partial L}{\\partial \\textbf{x}_{u}} = - 2 \\sum\\limits_{i}(r_{ui} - \\textbf{x}_{u}^{\\intercal} \\cdot{} \\textbf{y}_{i}) \\textbf{y}_{i}^{\\intercal} + 2 \\lambda_{x} \\textbf{x}_{u}^{\\intercal}$$\n",
"\n",
"$$0 = -(\\textbf{r}_{u} - \\textbf{x}_{u}^{\\intercal} Y^{\\intercal})Y + \\lambda_{x} \\textbf{x}_{u}^{\\intercal}$$\n",
"\n",
"$$\\textbf{x}_{u}^{\\intercal}(Y^{\\intercal}Y + \\lambda_{x}I) = \\textbf{r}_{u}Y$$\n",
"\n",
"$$\\textbf{x}_{u}^{\\intercal} = \\textbf{r}_{u}Y(Y^{\\intercal}Y + \\lambda_{x}I)^{-1}$$\n",
"\n",
"$Y$ (de dimensioins $m \\times k$) représente tous les vecteurs-lignes pour les éléments mis l'un sous l'autre. Et le vecteur ligne $\\textbf{r}_{u}$ représente la ligne de l'utilisateur $u$ de la matrice de ratings (dimensions $1 \\times m$). Enfin, $I$ est la matrice identité, de dimension $\\times k$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La dérivation avec les vecteurs d'items est similaire : \n",
"$$\\frac{\\partial L}{\\partial \\textbf{y}_{i}} = - 2 \\sum\\limits_{i}(r_{iu} - \\textbf{y}_{i}^{\\intercal} \\cdot{} \\textbf{x}_{u}) \\textbf{x}_{u}^{\\intercal} + 2 \\lambda_{y} \\textbf{y}_{i}^{\\intercal}$$\n",
"\n",
"$$0 = -(\\textbf{r}_{i} - \\textbf{y}_{i}^{\\intercal} X^{\\intercal})X + \\lambda_{y} \\textbf{y}_{i}^{\\intercal}$$\n",
"\n",
"$$ \\textbf{y}_{i}^{\\intercal} ( X^{\\intercal}X + \\lambda_{y}I) = \\textbf{r}_{i} X$$\n",
"\n",
"$$ \\textbf{y}_{i}^{\\intercal} = \\textbf{r}_{i} X ( X^{\\intercal}X + \\lambda_{y}I) ^{-1}$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Implémentation\n",
"\n",
"On reprend les données précédentes, recrée la matrice de notes, découpe en train/test. On se donne une fonction pour calculer la RMSE, qu'on optimisera."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"import pandas as pd\n",
"np.random.seed(0)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"cd ml-100k/"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# chargement de données\n",
"names = ['user_id', 'item_id', 'rating', 'timestamp']\n",
"df = pd.read_csv('u.data', sep='\\t', names=names)\n",
"n_users = df.user_id.unique().shape[0]\n",
"n_items = df.item_id.unique().shape[0]\n",
"\n",
"# Matrice de notes\n",
"ratings = np.zeros((n_users, n_items))\n",
"for row in df.itertuples():\n",
" ratings[row[1]-1, row[2]-1] = row[3]\n",
"\n",
"# On découpe en train/tests, en prenant 10 notes\n",
"# de chaque utilisateur pour les placer en test\n",
"def train_test_split(ratings):\n",
" test = np.zeros(ratings.shape)\n",
" train = ratings.copy()\n",
" for user in range(ratings.shape[0]):\n",
" test_ratings = np.random.choice(ratings[user, :].nonzero()[0], \n",
" size=10, \n",
" replace=False)\n",
" train[user, test_ratings] = 0.\n",
" test[user, test_ratings] = ratings[user, test_ratings]\n",
" \n",
" # Test and training are truly disjoint\n",
" assert(np.all((train * test) == 0)) \n",
" return train, test\n",
"\n",
"train, test = train_test_split(ratings)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from sklearn.metrics import mean_squared_error\n",
"\n",
"def get_mse(pred, actual):\n",
" # Ignore nonzero terms.\n",
" pred = pred[actual.nonzero()].flatten()\n",
" actual = actual[actual.nonzero()].flatten()\n",
" return mean_squared_error(pred, actual)"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true,
"jupyter": {
"outputs_hidden": true
}
},
"source": [
"On se dote maintenant d'une classe pour réaliser l'ALS."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from numpy.linalg import solve\n",
"\n",
"class ExplicitMF():\n",
" def __init__(self, \n",
" ratings, \n",
" n_factors=40, \n",
" item_reg=0.0, \n",
" user_reg=0.0,\n",
" verbose=False):\n",
" \"\"\"\n",
" Train a matrix factorization model to predict empty \n",
" entries in a matrix. The terminology assumes a \n",
" ratings matrix which is ~ user x item\n",
" \n",
" Params\n",
" ======\n",
" ratings : (ndarray)\n",
" User x Item matrix with corresponding ratings\n",
" \n",
" n_factors : (int)\n",
" Number of latent factors to use in matrix \n",
" factorization model\n",
" \n",
" item_reg : (float)\n",
" Regularization term for item latent factors\n",
" \n",
" user_reg : (float)\n",
" Regularization term for user latent factors\n",
" \n",
" verbose : (bool)\n",
" Whether or not to printout training progress\n",
" \"\"\"\n",
" \n",
" self.ratings = ratings\n",
" self.n_users, self.n_items = ratings.shape\n",
" self.n_factors = n_factors\n",
" self.item_reg = item_reg\n",
" self.user_reg = user_reg\n",
" self._v = verbose\n",
"\n",
" def als_step(self,\n",
" latent_vectors,\n",
" fixed_vecs,\n",
" ratings,\n",
" _lambda,\n",
" type='user'):\n",
" \"\"\"\n",
" One of the two ALS steps. Solve for the latent vectors\n",
" specified by type.\n",
" \"\"\"\n",
" if type == 'user':\n",
" # Precompute\n",
" YTY = fixed_vecs.T.dot(fixed_vecs)\n",
" lambdaI = np.eye(YTY.shape[0]) * _lambda\n",
"\n",
" for u in range(latent_vectors.shape[0]):\n",
" latent_vectors[u, :] = solve((YTY + lambdaI), \n",
" ratings[u, :].dot(fixed_vecs))\n",
" elif type == 'item':\n",
" # Precompute\n",
" XTX = fixed_vecs.T.dot(fixed_vecs)\n",
" lambdaI = np.eye(XTX.shape[0]) * _lambda\n",
" \n",
" for i in range(latent_vectors.shape[0]):\n",
" latent_vectors[i, :] = solve((XTX + lambdaI), \n",
" ratings[:, i].T.dot(fixed_vecs))\n",
" return latent_vectors\n",
"\n",
" def train(self, n_iter=10):\n",
" \"\"\" Train model for n_iter iterations from scratch.\"\"\"\n",
" # initialize latent vectors\n",
" self.user_vecs = np.random.random((self.n_users, self.n_factors))\n",
" self.item_vecs = np.random.random((self.n_items, self.n_factors))\n",
" \n",
" self.partial_train(n_iter)\n",
" \n",
" def partial_train(self, n_iter):\n",
" \"\"\" \n",
" Train model for n_iter iterations. Can be \n",
" called multiple times for further training.\n",
" \"\"\"\n",
" ctr = 1\n",
" while ctr <= n_iter:\n",
" if ctr % 10 == 0 and self._v:\n",
" print('\\tcurrent iteration: {}'.format(ctr))\n",
" self.user_vecs = self.als_step(self.user_vecs, \n",
" self.item_vecs, \n",
" self.ratings, \n",
" self.user_reg, \n",
" type='user')\n",
" self.item_vecs = self.als_step(self.item_vecs, \n",
" self.user_vecs, \n",
" self.ratings, \n",
" self.item_reg, \n",
" type='item')\n",
" ctr += 1\n",
" \n",
" def predict_all(self):\n",
" \"\"\" Predict ratings for every user and item. \"\"\"\n",
" predictions = np.zeros((self.user_vecs.shape[0], \n",
" self.item_vecs.shape[0]))\n",
" for u in range(self.user_vecs.shape[0]):\n",
" for i in range(self.item_vecs.shape[0]):\n",
" predictions[u, i] = self.predict(u, i)\n",
" \n",
" return predictions\n",
" def predict(self, u, i):\n",
" \"\"\" Single user and item prediction. \"\"\"\n",
" return self.user_vecs[u, :].dot(self.item_vecs[i, :].T)\n",
" \n",
" def calculate_learning_curve(self, iter_array, test):\n",
" \"\"\"\n",
" Keep track of MSE as a function of training iterations.\n",
" \n",
" Params\n",
" ======\n",
" iter_array : (list)\n",
" List of numbers of iterations to train for each step of \n",
" the learning curve. e.g. [1, 5, 10, 20]\n",
" test : (2D ndarray)\n",
" Testing dataset (assumed to be user x item).\n",
" \n",
" The function creates two new class attributes:\n",
" \n",
" train_mse : (list)\n",
" Training data MSE values for each value of iter_array\n",
" test_mse : (list)\n",
" Test data MSE values for each value of iter_array\n",
" \"\"\"\n",
" iter_array.sort()\n",
" self.train_mse =[]\n",
" self.test_mse = []\n",
" iter_diff = 0\n",
" for (i, n_iter) in enumerate(iter_array):\n",
" if self._v:\n",
" print('Iteration: {}'.format(n_iter))\n",
" if i == 0:\n",
" self.train(n_iter - iter_diff)\n",
" else:\n",
" self.partial_train(n_iter - iter_diff)\n",
"\n",
" predictions = self.predict_all()\n",
"\n",
" self.train_mse += [get_mse(predictions, self.ratings)]\n",
" self.test_mse += [get_mse(predictions, test)]\n",
" if self._v:\n",
" print('Train MSE: ' + str(self.train_mse[-1]))\n",
" print('Test MSE: ' + str(self.test_mse[-1]))\n",
" iter_diff = n_iter"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On commence par un premier entraînement avec $k=40$, sans régularisation. On va ensuite tracer la courbe de la MSE en fonction des itérations."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"MF_ALS = ExplicitMF(train, n_factors=40, \\\n",
" user_reg=0.0, item_reg=0.0)\n",
"print('attention, cellule longue à exécuter. Décommenter avec précaution.')\n",
"#iter_array = [1, 2, 5, 10, 25, 50, 100]\n",
"#%timeit MF_ALS.calculate_learning_curve(iter_array, test)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%matplotlib inline\n",
"import matplotlib.pyplot as plt\n",
"import seaborn as sns\n",
"sns.set()\n",
"\n",
"def plot_learning_curve(iter_array, model):\n",
" plt.plot(iter_array, model.train_mse, \\\n",
" label='Training', linewidth=5)\n",
" plt.plot(iter_array, model.test_mse, \\\n",
" label='Test', linewidth=5)\n",
"\n",
"\n",
" plt.xticks(fontsize=16);\n",
" plt.yticks(fontsize=16);\n",
" plt.xlabel('iterations', fontsize=30);\n",
" plt.ylabel('MSE', fontsize=30);\n",
" plt.legend(loc='best', fontsize=20);"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"plot_learning_curve(iter_array, MF_ALS)"
]
},
{
"cell_type": "markdown",
"metadata": {
"editable": true,
"slideshow": {
"slide_type": ""
},
"tags": []
},
"source": [
"**Question :** Que concluez-vous ?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La MSE 50% plus élevée en test qu'en training indique que le sur-apprentissage (*overfitting*) est assez conséquent. Le fait que la MSE de test atteigne son minimum après 5 itérations et réaugmente ensuite est aussi un signe de ce sur-apprentissage."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Ajustements\n",
"\n",
"Proposons un peu de régularisation, pour améliorer."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"MF_ALS = ExplicitMF(train, n_factors=40, \\\n",
" user_reg=1., item_reg=1.)\n",
"\n",
"iter_array = [1, 2, 5, 10, 25, 50, 100]\n",
"MF_ALS.calculate_learning_curve(iter_array, test)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"plot_learning_curve(iter_array, MF_ALS)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question:** Que s'est-il passé ?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La régularisation a réduit l'écart entre nos MSE, mais n'a pas changé significativement notre MSE de test."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Effectuons une petite grid-search pour trouver de bons paramètres pour la régularisation et le nombre de facteurs latents. Pour simplifier, les paramètres de régularisation seront les mêmes (utilisateurs et items)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"latent_factors = [5, 10, 20, 40, 80]\n",
"regularizations = [0.01, 0.1, 1., 10., 100.]\n",
"regularizations.sort()\n",
"iter_array = [1, 2, 5, 10, 25, 50, 100]\n",
"\n",
"best_params = {}\n",
"best_params['n_factors'] = latent_factors[0]\n",
"best_params['reg'] = regularizations[0]\n",
"best_params['n_iter'] = 0\n",
"best_params['train_mse'] = np.inf\n",
"best_params['test_mse'] = np.inf\n",
"best_params['model'] = None\n",
"\n",
"for fact in latent_factors:\n",
" print('Factors: {}'.format(fact))\n",
" for reg in regularizations:\n",
" print('Regularization: {}'.format(reg))\n",
" MF_ALS = ExplicitMF(train, n_factors=fact, \\\n",
" user_reg=reg, item_reg=reg)\n",
" MF_ALS.calculate_learning_curve(iter_array, test)\n",
" min_idx = np.argmin(MF_ALS.test_mse)\n",
" if MF_ALS.test_mse[min_idx] < best_params['test_mse']:\n",
" best_params['n_factors'] = fact\n",
" best_params['reg'] = reg\n",
" best_params['n_iter'] = iter_array[min_idx]\n",
" best_params['train_mse'] = MF_ALS.train_mse[min_idx]\n",
" best_params['test_mse'] = MF_ALS.test_mse[min_idx]\n",
" best_params['model'] = MF_ALS\n",
" print('New optimal hyperparameters')\n",
" print(pd.Series(best_params))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"best_als_model = best_params['model']\n",
"plot_learning_curve(iter_array, best_als_model)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question :** Quels sont les meilleurs paramètres ?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"k=20, regularisation à 0.01."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## La SGD (Stochastic Gradient Descent)\n",
"\n",
"Avec la SGD, on utilise à nouveau les dérivées partielles de la fonction de loss, mais on les calcule par rapport à chaque variable. La partie \"stochastique\" de l'algorithme repose sur une mise à jour des poids un échantillon à la fois. Pour chaque échantillon, on prend la dérivée par rapport à chaque variable, résout en zéro pour les poids donnés et on met à jour.\n",
"\n",
"On va utiliser la même fonction que précédemment, mais ajouter quelques détails au modèle : au lieu de considérer que l'évaluation de chaque utilisateur pour un item est simplement le produit de leurs vecteurs latents, on va \n",
"ajouter un terme de biais, pour prendre en compte le fait que certains utilisateurs notent *toujours haut*, et que certains films ont des notes *toujours basses*. On va ajouter un petit terme de biais global ($\\mu$). Notre note prédite se calcule ainsi :\n",
"\n",
"$$ \\hat r_{ui} = \\mu + b_{u} + b_{i} + \\textbf{x}_{u}^{\\intercal} \\cdot{} \\textbf{y}_{i} $$\n",
"\n",
"où $b_{u}$ ($b_{i}$) est le bias utilisateur (item)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notre fonction de _loss_ devient :\n",
"$$L = \\sum\\limits_{u,i}(r_{ui} - (\\mu + b_{u} + b_{i} + \\textbf{x}_{u}^{\\intercal} \\cdot{} \\textbf{y}_{i}))^{2} + \n",
"\\lambda_{xb} \\sum\\limits_{u} \\left\\Vert b_{u} \\right\\Vert^{2} + \\lambda_{yb} \\sum\\limits_{i} \\left\\Vert b_{i} \\right\\Vert^{2} + \\lambda_{xf} \\sum\\limits_{u} \\left\\Vert \\textbf{x}_{u} \\right\\Vert^{2} + \\lambda_{yf} \\sum\\limits_{u} \\left\\Vert \\textbf{y}_{i} \\right\\Vert^{2}$$\n",
"\n",
"On a ajouté les termes de régularisation."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On veut mettre à jour chaque caractéristique (les facteurs latents utilisateurs et item, les biais) à chaque échantillon. La mise à jour du biais utilisateur est donnée par :\n",
"$$ b_{u} \\leftarrow b_{u} - \\eta \\frac{\\partial L}{\\partial b_{u}} $$\n",
"où $\\eta$ est le pas d'apprentissage, qui pondère comment chaque mise à jour va modifier les poids de chaque caractéristique. \n",
"\n",
"La dérivée partielle vaut :\n",
"$$ \\frac{\\partial L}{\\partial b_{u}} = 2(r_{ui} - (\\mu + b_{u} + b_{i} + \\textbf{x}_{u}^{\\intercal} \\cdot{} \\textbf{y}_{i}))(-1) + 2\\lambda_{xb} b_{u} $$\n",
"$$ \\frac{\\partial L}{\\partial b_{u}} = 2(e_{ui})(-1) + 2\\lambda_{xb} b_{u} $$\n",
"$$ \\frac{\\partial L}{\\partial b_{u}} = - e_{ui} + \\lambda_{xb} b_{u} $$\n",
"\n",
"où $e_{ui}$ représente l'erreur de prédiction. \n",
"\n",
"Les mises à jour complètes sont donc :\n",
"\n",
"$$ b_{u} \\leftarrow b_{u} + \\eta \\, (e_{ui} - \\lambda_{xb} b_{u}) $$\n",
"$$ b_{i} \\leftarrow b_{i} + \\eta \\, (e_{ui} - \\lambda_{yb} b_{i}) $$\n",
"$$ \\textbf{x}_{u} \\leftarrow \\textbf{x}_{u} + \\eta \\, (e_{ui}\\textbf{y}_{i} - \\lambda_{xf} \\textbf{x}_{u}) $$\n",
"$$ \\textbf{y}_{i} \\leftarrow \\textbf{y}_{i} + \\eta \\, (e_{ui}\\textbf{x}_{u} - \\lambda_{yf} \\textbf{y}_{i}) $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Implémentation\n",
"\n",
"Reprenons la classe ci-dessus, en ajoutant la possibilité de faire la mise à jour SGD."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class ExplicitMF():\n",
" def __init__(self, \n",
" ratings,\n",
" n_factors=40,\n",
" learning='sgd',\n",
" item_fact_reg=0.0, \n",
" user_fact_reg=0.0,\n",
" item_bias_reg=0.0,\n",
" user_bias_reg=0.0,\n",
" verbose=False):\n",
" \"\"\"\n",
" Train a matrix factorization model to predict empty \n",
" entries in a matrix. The terminology assumes a \n",
" ratings matrix which is ~ user x item\n",
" \n",
" Params\n",
" ======\n",
" ratings : (ndarray)\n",
" User x Item matrix with corresponding ratings\n",
" \n",
" n_factors : (int)\n",
" Number of latent factors to use in matrix \n",
" factorization model\n",
" learning : (str)\n",
" Method of optimization. Options include \n",
" 'sgd' or 'als'.\n",
" \n",
" item_fact_reg : (float)\n",
" Regularization term for item latent factors\n",
" \n",
" user_fact_reg : (float)\n",
" Regularization term for user latent factors\n",
" \n",
" item_bias_reg : (float)\n",
" Regularization term for item biases\n",
" \n",
" user_bias_reg : (float)\n",
" Regularization term for user biases\n",
" \n",
" verbose : (bool)\n",
" Whether or not to printout training progress\n",
" \"\"\"\n",
" \n",
" self.ratings = ratings\n",
" self.n_users, self.n_items = ratings.shape\n",
" self.n_factors = n_factors\n",
" self.item_fact_reg = item_fact_reg\n",
" self.user_fact_reg = user_fact_reg\n",
" self.item_bias_reg = item_bias_reg\n",
" self.user_bias_reg = user_bias_reg\n",
" self.learning = learning\n",
" if self.learning == 'sgd':\n",
" self.sample_row, self.sample_col = self.ratings.nonzero()\n",
" self.n_samples = len(self.sample_row)\n",
" self._v = verbose\n",
"\n",
" def als_step(self,\n",
" latent_vectors,\n",
" fixed_vecs,\n",
" ratings,\n",
" _lambda,\n",
" type='user'):\n",
" \"\"\"\n",
" One of the two ALS steps. Solve for the latent vectors\n",
" specified by type.\n",
" \"\"\"\n",
" if type == 'user':\n",
" # Precompute\n",
" YTY = fixed_vecs.T.dot(fixed_vecs)\n",
" lambdaI = np.eye(YTY.shape[0]) * _lambda\n",
"\n",
" for u in range(latent_vectors.shape[0]):\n",
" latent_vectors[u, :] = solve((YTY + lambdaI), \n",
" ratings[u, :].dot(fixed_vecs))\n",
" elif type == 'item':\n",
" # Precompute\n",
" XTX = fixed_vecs.T.dot(fixed_vecs)\n",
" lambdaI = np.eye(XTX.shape[0]) * _lambda\n",
" \n",
" for i in range(latent_vectors.shape[0]):\n",
" latent_vectors[i, :] = solve((XTX + lambdaI), \n",
" ratings[:, i].T.dot(fixed_vecs))\n",
" return latent_vectors\n",
"\n",
" def train(self, n_iter=10, learning_rate=0.1):\n",
" \"\"\" Train model for n_iter iterations from scratch.\"\"\"\n",
" # initialize latent vectors \n",
" self.user_vecs = np.random.normal(scale=1./self.n_factors,\\\n",
" size=(self.n_users, self.n_factors))\n",
" self.item_vecs = np.random.normal(scale=1./self.n_factors,\n",
" size=(self.n_items, self.n_factors))\n",
" \n",
" if self.learning == 'als':\n",
" self.partial_train(n_iter)\n",
" elif self.learning == 'sgd':\n",
" self.learning_rate = learning_rate\n",
" self.user_bias = np.zeros(self.n_users)\n",
" self.item_bias = np.zeros(self.n_items)\n",
" self.global_bias = np.mean(self.ratings[np.where(self.ratings != 0)])\n",
" self.partial_train(n_iter)\n",
" \n",
" \n",
" def partial_train(self, n_iter):\n",
" \"\"\" \n",
" Train model for n_iter iterations. Can be \n",
" called multiple times for further training.\n",
" \"\"\"\n",
" ctr = 1\n",
" while ctr <= n_iter:\n",
" if ctr % 10 == 0 and self._v:\n",
" print('\\tcurrent iteration: {}'.format(ctr))\n",
" if self.learning == 'als':\n",
" self.user_vecs = self.als_step(self.user_vecs, \n",
" self.item_vecs, \n",
" self.ratings, \n",
" self.user_fact_reg, \n",
" type='user')\n",
" self.item_vecs = self.als_step(self.item_vecs, \n",
" self.user_vecs, \n",
" self.ratings, \n",
" self.item_fact_reg, \n",
" type='item')\n",
" elif self.learning == 'sgd':\n",
" self.training_indices = np.arange(self.n_samples)\n",
" np.random.shuffle(self.training_indices)\n",
" self.sgd()\n",
" ctr += 1\n",
"\n",
" def sgd(self):\n",
" for idx in self.training_indices:\n",
" u = self.sample_row[idx]\n",
" i = self.sample_col[idx]\n",
" prediction = self.predict(u, i)\n",
" e = (self.ratings[u,i] - prediction) # error\n",
" \n",
" # Update biases\n",
" self.user_bias[u] += self.learning_rate * \\\n",
" (e - self.user_bias_reg * self.user_bias[u])\n",
" self.item_bias[i] += self.learning_rate * \\\n",
" (e - self.item_bias_reg * self.item_bias[i])\n",
" \n",
" #Update latent factors\n",
" self.user_vecs[u, :] += self.learning_rate * \\\n",
" (e * self.item_vecs[i, :] - \\\n",
" self.user_fact_reg * self.user_vecs[u,:])\n",
" self.item_vecs[i, :] += self.learning_rate * \\\n",
" (e * self.user_vecs[u, :] - \\\n",
" self.item_fact_reg * self.item_vecs[i,:])\n",
" def predict(self, u, i):\n",
" \"\"\" Single user and item prediction.\"\"\"\n",
" if self.learning == 'als':\n",
" return self.user_vecs[u, :].dot(self.item_vecs[i, :].T)\n",
" elif self.learning == 'sgd':\n",
" prediction = self.global_bias + self.user_bias[u] + self.item_bias[i]\n",
" prediction += self.user_vecs[u, :].dot(self.item_vecs[i, :].T)\n",
" return prediction\n",
" \n",
" def predict_all(self):\n",
" \"\"\" Predict ratings for every user and item.\"\"\"\n",
" predictions = np.zeros((self.user_vecs.shape[0], \n",
" self.item_vecs.shape[0]))\n",
" for u in range(self.user_vecs.shape[0]):\n",
" for i in range(self.item_vecs.shape[0]):\n",
" predictions[u, i] = self.predict(u, i)\n",
" \n",
" return predictions\n",
" \n",
" def calculate_learning_curve(self, iter_array, test, learning_rate=0.1):\n",
" \"\"\"\n",
" Keep track of MSE as a function of training iterations.\n",
" \n",
" Params\n",
" ======\n",
" iter_array : (list)\n",
" List of numbers of iterations to train for each step of \n",
" the learning curve. e.g. [1, 5, 10, 20]\n",
" test : (2D ndarray)\n",
" Testing dataset (assumed to be user x item).\n",
" \n",
" The function creates two new class attributes:\n",
" \n",
" train_mse : (list)\n",
" Training data MSE values for each value of iter_array\n",
" test_mse : (list)\n",
" Test data MSE values for each value of iter_array\n",
" \"\"\"\n",
" iter_array.sort()\n",
" self.train_mse =[]\n",
" self.test_mse = []\n",
" iter_diff = 0\n",
" for (i, n_iter) in enumerate(iter_array):\n",
" if self._v:\n",
" print('Iteration: {}'.format(n_iter))\n",
" if i == 0:\n",
" self.train(n_iter - iter_diff, learning_rate)\n",
" else:\n",
" self.partial_train(n_iter - iter_diff)\n",
"\n",
" predictions = self.predict_all()\n",
"\n",
" self.train_mse += [get_mse(predictions, self.ratings)]\n",
" self.test_mse += [get_mse(predictions, test)]\n",
" if self._v:\n",
" print('Train mse: ' + str(self.train_mse[-1]))\n",
" print('Test mse: ' + str(self.test_mse[-1]))\n",
" iter_diff = n_iter"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Comme avec l'ALS plus tôt, commençons avec 40 facteurs latents, sans régularisation et un pas de 0.001."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"MF_SGD = ExplicitMF(train, 40, learning='sgd', verbose=True)\n",
"iter_array = [1, 2, 5, 10, 25, 50, 100, 200]\n",
"MF_SGD.calculate_learning_curve(iter_array, test, learning_rate=0.001)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"plot_learning_curve(iter_array, MF_SGD)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question :** Que concluez-vous de ces résultats ?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Les résultats sont bien meilleurs, la prise en compte des biais a amélioré les performances."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Ajustements\n",
"\n",
"Optimisons un peu, avec une grid-search pour le pas d'apprentissage."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"iter_array = [1, 2, 5, 10, 25, 50, 100, 200]\n",
"learning_rates = [1e-5, 1e-4, 1e-3, 1e-2]\n",
"\n",
"best_params = {}\n",
"best_params['learning_rate'] = None\n",
"best_params['n_iter'] = 0\n",
"best_params['train_mse'] = np.inf\n",
"best_params['test_mse'] = np.inf\n",
"best_params['model'] = None\n",
"\n",
"\n",
"for rate in learning_rates:\n",
" print('Rate: {}'.format(rate))\n",
" MF_SGD = ExplicitMF(train, n_factors=40, learning='sgd')\n",
" MF_SGD.calculate_learning_curve(iter_array, test, learning_rate=rate)\n",
" min_idx = np.argmin(MF_SGD.test_mse)\n",
" if MF_SGD.test_mse[min_idx] < best_params['test_mse']:\n",
" best_params['n_iter'] = iter_array[min_idx]\n",
" best_params['learning_rate'] = rate\n",
" best_params['train_mse'] = MF_SGD.train_mse[min_idx]\n",
" best_params['test_mse'] = MF_SGD.test_mse[min_idx]\n",
" best_params['model'] = MF_SGD\n",
" print('New optimal hyperparameters')\n",
" print(pd.Series(best_params))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question :** Qu'obtenez-vous ?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"0.001 était le meilleur pas d'apprentissage."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut chercher à optimiser les autres hyperparamètres (termes de régularisation et facteurs latents). Cela pourrait être parallélisé, ça prend un peu de temps."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#va être trop long\n",
"\n",
"iter_array = [1, 2, 5, 10, 25, 50, 100, 200]\n",
"latent_factors = [5, 10, 20, 40, 80]\n",
"regularizations = [0.001, 0.01, 0.1, 1.]\n",
"regularizations.sort()\n",
"\n",
"best_params = {}\n",
"best_params['n_factors'] = latent_factors[0]\n",
"best_params['reg'] = regularizations[0]\n",
"best_params['n_iter'] = 0\n",
"best_params['train_mse'] = np.inf\n",
"best_params['test_mse'] = np.inf\n",
"best_params['model'] = None\n",
"\n",
"for fact in latent_factors:\n",
" print 'Factors: {}'.format(fact)\n",
" for reg in regularizations:\n",
" print 'Regularization: {}'.format(reg)\n",
" MF_SGD = ExplicitMF(train, n_factors=fact, learning='sgd',\\\n",
" user_fact_reg=reg, item_fact_reg=reg, \\\n",
" user_bias_reg=reg, item_bias_reg=reg)\n",
" MF_SGD.calculate_learning_curve(iter_array, test, learning_rate=0.001)\n",
" min_idx = np.argmin(MF_SGD.test_mse)\n",
" if MF_SGD.test_mse[min_idx] < best_params['test_mse']:\n",
" best_params['n_factors'] = fact\n",
" best_params['reg'] = reg\n",
" best_params['n_iter'] = iter_array[min_idx]\n",
" best_params['train_mse'] = MF_SGD.train_mse[min_idx]\n",
" best_params['test_mse'] = MF_SGD.test_mse[min_idx]\n",
" best_params['model'] = MF_SGD\n",
" print 'New optimal hyperparameters'\n",
" print pd.Series(best_params)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"plot_learning_curve(iter_array, best_params['model'])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print 'Best regularization: {}'.format(best_params['reg'])\n",
"print 'Best latent factors: {}'.format(best_params['n_factors'])\n",
"print 'Best iterations: {}'.format(best_params['n_iter'])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question :** Qu'obtenez-vous ? Que pourrait-on faire ?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La valeur pour le nombre de facteurs latents et pour le nombre d'itérations sont au maximum de la *grid search* : on pourrait proposer une *grid search* étendue, pour trouver d'autres valeurs ou confirmer celles-ci."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Les recommandations proposées\n",
"\n",
"On va, comme précédemment, essayer de regarder \"à l'œil\", la qualité des recommandations proposées, en listant 5 recommandations pour un film donné."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On commence par entraîner nos modèles avec l'ALS et la SGD, avec nos meilleurs paramètres."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"best_als_model = ExplicitMF(ratings, n_factors=20, learning='als', \\\n",
" item_fact_reg=0.01, user_fact_reg=0.01)\n",
"best_als_model.train(50)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"best_sgd_model = ExplicitMF(ratings, n_factors=80, learning='sgd', \\\n",
" item_fact_reg=0.01, user_fact_reg=0.01, \\\n",
" user_bias_reg=0.01, item_bias_reg=0.01)\n",
"best_sgd_model.train(200, learning_rate=0.001)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On calcule une similarité cosinus \"film à film\" sur les deux matrices des modèles :"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def cosine_similarity(model):\n",
" sim = model.item_vecs.dot(model.item_vecs.T)\n",
" norms = np.array([np.sqrt(np.diagonal(sim))])\n",
" return sim / norms / norms.T\n",
"\n",
"als_sim = cosine_similarity(best_als_model)\n",
"sgd_sim = cosine_similarity(best_sgd_model)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On va maintenant chercher, pour un film donné, 5 recommandations avec chaque modèle."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"idx_to_movie = {}\n",
"with open('u.item', 'r', encoding=\"utf8\", errors='ignore') as f:\n",
" for line in f.readlines():\n",
" info = line.split('|')\n",
" idx_to_movie[int(info[0])-1] = info[1]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def top_k_movies(similarity, mapper, movie_idx, k=6):\n",
" return [mapper[x] for x in np.argsort(similarity[movie_idx,:])[:-k-1:-1]]\n",
"\n",
"def print_top_k_movies(movies):\n",
" for k,movie in enumerate(movies[1:]): # on sort le film d'entrée lui-même\n",
" print(\"%s : %s\"%(k+1,movie)) #on affiche avec décalage d'indice"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from IPython.display import HTML\n",
"from IPython.display import display\n",
"\n",
"def compare_recs(als_similarity, sgd_similarity, mapper,\\\n",
" movie_idx, k=5):\n",
" # Display input\n",
" display(HTML(''+'Entrée : '+idx_to_movie[movie_idx]+''))\n",
" # Display ALS Recs\n",
" display(HTML(''+'Recommandations avec ALS :'+''))\n",
" print_top_k_movies(top_k_movies(als_similarity, idx_to_movie, movie_idx))\n",
" # Display SGD Recs\n",
" display(HTML(''+'Recommandations avec SGD :'+''))\n",
" #display_top_k_movies(sgd_similarity, idx_to_movie, movie_idx )\n",
" print_top_k_movies(top_k_movies(sgd_similarity, idx_to_movie, movie_idx))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"idx = 0 # Toy Story\n",
"compare_recs(als_sim, sgd_sim, idx_to_movie, idx)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"idx = 1 # GoldenEye\n",
"compare_recs(als_sim, sgd_sim, idx_to_movie, idx)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"idx = 20 # Muppet Treasure Island\n",
"compare_recs(als_sim, sgd_sim, idx_to_movie, idx)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"idx = 500 # Dumbo\n",
"compare_recs(als_sim, sgd_sim, idx_to_movie, idx)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question :** Que concluez-vous ?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"L'ALS a une MSE bien plus haute que la SGD, pourtant les recos SGD semblent inférieures à celles de l'ALS. Idées d'explication : sur-apprentissage de la SGD, susceptibilité à la popularité. Ou encore : les films moins similaires \"à l'œil\" peuvent en fait être de meilleurs recos (cf A/B tests chez Netflix). Dernier point : on pourrait compléter ces modèles dans modèles hybrides."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"editable": true,
"slideshow": {
"slide_type": ""
},
"tags": []
},
"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.11.7"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": true,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 4
}