L'autre jour, j'ai implémenté un algorithme de recommandation appelé Bayesian Personalized Ranking (BPR). J'ai écrit le code en référence à la formule dans cet article, mais quand je l'ai exécuté, il était un peu trop lent à utiliser, j'ai donc amélioré la vitesse de traitement. J'ai travaillé dessus. Je vais résumer ce que j'ai essayé à l'époque sous forme de mémorandum.
BPR donne la décomposition matricielle de la matrice d'éléments utilisateur x. Décompose la matrice utilisateur x élément $ X $ en la matrice utilisateur x facteur $ U $ et la matrice élément x facteur $ V $.
X = U \cdot V^T
Voir [Original Paper] de BPR (http://arxiv.org/abs/1205.2618) pour savoir comment résoudre ce problème.
J'ai implémenté cette technique comme suit. $ X $ est défini dans scipy.sparse.lil_matrix. Les $ U $ et $ V $ décomposés sont numpy.array.
La procédure consiste à amorcer l'échantillon de l'échantillon utilisé pour la formation, puis à mettre à jour $ U et V $.
Pour ce code, je voudrais améliorer buildModel (), qui est la partie d'apprentissage du modèle.
MFbpr.py
class MFbpr(Recommender):
'''
Constructeur et autres traitements
'''
def buildModel(self):
loss_pre = sys.float_info.max
nonzeros = self.trainMatrix.nnz
hr_prev = 0.0
sys.stderr.write("Run for BPR. \n")
for itr in xrange(self.maxIter):
start = time.time()
# Each training epoch
for s in xrange(nonzeros):
# sample a user
u = np.random.randint(self.userCount)
itemList = self.trainMatrix.getrowview(u).rows[0]
if len(itemList) == 0:
continue
# sample a positive item
i = random.choice(itemList)
# One SGD step update
self.update_ui(u, i)
def update_ui(self, u, i):
# sample a negative item(uniformly random)
j = np.random.randint(self.itemCount)
while self.trainMatrix[u, j] != 0:
j = np.random.randint(self.itemCount)
# BPR update rules
y_pos = self.predict(u, i) # target value of positive instance
y_neg = self.predict(u, j) # target value of negative instance
mult = -self.partial_loss(y_pos - y_neg)
for f in xrange(self.factors):
grad_u = self.V[i, f] - self.V[j, f]
self.U[u, f] -= self.lr * (mult * grad_u + self.reg * self.U[u, f])
grad = self.U[u, f]
self.V[i, f] -= self.lr * (mult * grad + self.reg * self.V[i, f])
self.V[j, f] -= self.lr * (-mult * grad + self.reg * self.V[j, f])
exec_bpr.py
from MFbpr import MFbpr
def load_data(ratingFile, testRatio=0.1):
'''
Le processus de chargement des données
'''
return trainMatrix, testRatings
if __name__ == "__main__":
# data
trainMatrix, testRatings = load_data('yelp.rating')
# settings
topK = 100
factors = 64
maxIter = 10
maxIterOnline = 1
lr = 0.01
adaptive = False
init_mean = 0.0
init_stdev = 0.1
reg = 0.01
showProgress = False
showLoss = True
bpr = MFbpr(trainMatrix, testRatings, topK, factors, maxIter, lr, adaptive, reg, init_mean, init_stdev, showProgress, showLoss)
bpr.buildModel()
La totalité du code est disponible sur github.
Je vais l'essayer pour le moment.
--Nombre d'utilisateurs: 25677 --Nombre d'articles: 25815 --Nombre de notes (nombre d'échantillons avec notes): 627775
--Nombre de facteurs: 64
C'est ubuntu avec une mémoire 2G et 2 processeurs basés sur VirtualBox.
Le premier crochet correspond au temps nécessaire pour une ou plusieurs itérations et le dernier crochet correspond au temps nécessaire pour calculer la ou les pertes.
> python exex_bpr.py
Data yelp.rating
#Users 25677, #newUser: 588
#Items 25815
#Ratings 627775.0 (train), 73167(test), 10056(#newTestRatings)
Run for BPR.
Iter=0 [128.6936481] [-]loss: 624484.357765 [8.16665792465]
Iter=1 [137.202406883] [-]loss: 616970.769244 [7.11149096489]
Iter=2 [131.134891987] [-]loss: 609361.307524 [7.12593793869]
Iter=3 [134.665620804] [-]loss: 601240.628869 [8.45840716362]
Iter=4 [134.722868919] [-]loss: 592053.155587 [7.6300880909]
Même si je calcule environ 600 000 échantillons, j'estime que 130 secondes par itération sont trop longues.
Commençons par identifier les parties qui prennent beaucoup de temps.
Utilisez le profileur Python cProfile pour mesurer la vitesse de traitement.
python -m cProfile -s cumulative ***.py
Si vous exécutez, il affichera le traitement chronophage dans l'ordre décroissant.
> python -m cProfile -s cumulative exex_bpr.py
Data yelp.rating
#Users 25677, #newUser: 588
#Items 25815
#Ratings 627775.0 (train), 73167(test), 10056(#newTestRatings)
Run for BPR.
Iter=0 [244.87996006] [-]loss: 624394.802988 [53.4806399345]
Iter=1 [248.624686956] [-]loss: 616876.50976 [48.6073460579]
Iter=2 [253.822627068] [-]loss: 609269.820414 [52.5446169376]
Iter=3 [261.039247036] [-]loss: 601207.904104 [53.8221797943]
Iter=4 [260.285779953] [-]loss: 592212.148141 [54.9556028843]
369374621 function calls (368041918 primitive calls) in 1808.492 seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.171 0.171 1808.493 1808.493 exex_bpr.py:3(<module>)
1 34.307 34.307 1532.124 1532.124 MFbpr.py:40(buildModel)
3067088 535.383 0.000 830.046 0.000 MFbpr.py:92(update_ui)
6209078 48.829 0.000 433.564 0.000 lil.py:228(__getitem__)
3292937 26.140 0.000 376.631 0.000 lil.py:191(getrowview)
3292939 66.488 0.000 346.337 0.000 lil.py:85(__init__)
5 0.000 0.000 263.411 52.682 MFbpr.py:117(_showLoss)
5 22.098 4.420 263.410 52.682 MFbpr.py:128(loss)
1 9.443 9.443 242.550 242.550 exex_bpr.py:9(load_data)
À partir du bas de la ligne «Ordonné par: temps cumulé», les noms des fonctions et le temps nécessaire au traitement sont répertoriés. Si vous regardez ceci, vous pouvez voir que la fonction ʻupdate_ui est appelée 3 067 088 fois et prend un total de 535,383 secondes. (Eh bien, il est naturel que seul ʻupdate_ui soit appelé dans buildModel ...)
C'est la surcharge de cProfile que le temps d'exécution d'une itération est plus long qu'auparavant.
Vous pouvez utiliser line_profiler pour mesurer la fonction d'intérêt ligne par ligne. Vous pouvez l'installer avec pip.
> pip install line_profiler
Afin de profiler avec line_profiler, vous devez ajouter un décorateur @ profile à la fonction que vous regardez.
MFbpr.py
@profile
def update_ui(self, u, i):
# sample a negative item(uniformly random)
j = np.random.randint(self.itemCount)
while self.trainMatrix[u, j] != 0:
j = np.random.randint(self.itemCount)
# BPR update rules
y_pos = self.predict(u, i) # target value of positive instance
y_neg = self.predict(u, j) # target value of negative instance
mult = -self.partial_loss(y_pos - y_neg)
for f in xrange(self.factors):
grad_u = self.V[i, f] - self.V[j, f]
self.U[u, f] -= self.lr * (mult * grad_u + self.reg * self.U[u, f])
grad = self.U[u, f]
self.V[i, f] -= self.lr * (mult * grad + self.reg * self.V[i, f])
self.V[j, f] -= self.lr * (-mult * grad + self.reg * self.V[j, f])
Tout ce que vous avez à faire est de l'exécuter avec la commande kernprof.
> kernprof -l -v exex_bpr.py
Data yelp.rating
#Users 25677, #newUser: 588
#Items 25815
#Ratings 627775.0 (train), 73167(test), 10056(#newTestRatings)
Run for BPR.
Iter=0 [953.993126154] [-]loss: 624406.940531 [7.50253987312]
Iter=1 [962.82383585] [-]loss: 616855.373858 [7.96375918388]
Wrote profile results to exex_bpr.py.lprof
Timer unit: 1e-06 s
Total time: 1082.55 s
File: MFbpr.py
Function: update_ui at line 92
Line # Hits Time Per Hit % Time Line Contents
==============================================================
92 @profile
93 def update_ui(self, u, i):
94 # sample a negative item(uniformly random)
95 1226961 8241361 6.7 0.8 j = np.random.randint(self.itemCount)
96 1228124 39557350 32.2 3.7 while self.trainMatrix[u, j] != 0:
97 1163 6123 5.3 0.0 j = np.random.randint(self.itemCount)
98
99 # BPR update rules
100 1226961 9495381 7.7 0.9 y_pos = self.predict(u, i) # target value of positive instance
101 1226961 4331378 3.5 0.4 y_neg = self.predict(u, j) # target value of negative instance
102 1226961 10002355 8.2 0.9 mult = -self.partial_loss(y_pos - y_neg)
103
104 79752465 126523856 1.6 11.7 for f in xrange(self.factors):
105 78525504 161882071 2.1 15.0 grad_u = self.V[i, f] - self.V[j, f]
106 78525504 191293505 2.4 17.7 self.U[u, f] -= self.lr * (mult * grad_u + self.reg * self.U[u, f])
107
108 78525504 137871145 1.8 12.7 grad = self.U[u, f]
109 78525504 194033291 2.5 17.9 self.V[i, f] -= self.lr * (mult * grad + self.reg * self.V[i, f])
110 78525504 199315454 2.5 18.4 self.V[j, f] -= self.lr * (-mult * grad + self.reg * self.V[j, f])
En regardant la colonne % Time, nous avons constaté que ** 90% ou plus du temps de traitement de ʻupdate_ui` était passé sous l'instruction for **.
Une itération dure moins de 1 000 secondes, ce qui signifie que la surcharge est lourde.
Réécrivez la boucle for précédente avec Cython. L'une des raisons pour lesquelles Python est lent est qu'il est typé dynamiquement. Puisque le type est vérifié à chaque fois qu'une variable est référencée, les programmes avec de nombreuses références de variable ne peuvent pas ignorer le temps requis pour cette opération.
Si vous écrivez en utilisant Cython, vous pouvez définir le type de variable comme le langage C. Le type n'étant pas confirmé un par un, on peut s'attendre à une accélération considérable.
Déclarez les variables avec cdef. Définissez les types de toutes les variables utilisées dans le calcul.
fastupdfn.pyx
import numpy as np
cimport numpy as np
cimport cython
DOUBLE = np.float64
ctypedef np.float64_t DOUBLE_t
cpdef c_upd(np.ndarray[DOUBLE_t, ndim=2] U,
np.ndarray[DOUBLE_t, ndim=2] V,
double mult,
double lr,
double reg,
unsigned int u,
unsigned int i,
unsigned int j,
unsigned int factors):
cdef unsigned int f
cdef double grad_u, grad
for f in xrange(factors):
grad_u = V[i, f] - V[j, f]
U[u, f] -= lr * (mult * grad_u + reg * U[u, f])
grad = U[u, f]
V[i, f] -= lr * (mult * grad + reg * V[i, f])
V[j, f] -= lr * (-mult * grad + reg * V[j, f])
return U, V
L'appelant est réécrit comme suit.
MFbpr.py
import fastupd #ajouter à
class MFbpr(Recommender):
"""
Omission
"""
def update_ui(self, u, i):
# sample a negative item(uniformly random)
j = np.random.randint(self.itemCount)
while self.trainMatrix[u, j] != 0:
j = np.random.randint(self.itemCount)
# BPR update rules
y_pos = self.predict(u, i) # target value of positive instance
y_neg = self.predict(u, j) # target value of negative instance
mult = -self.partial_loss(y_pos - y_neg)
#Appelez l'implémentation Cython
self.U, self.V = fastupd.c_upd(self.U, self.V, mult, self.lr, self.reg, u, i, j, self.factors)
Vous devez également avoir un setup.py pour compiler votre implémentation Cython.
setup.py
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext
setup(
cmdclass={'build_ext': build_ext},
ext_modules=[Extension("fastupd", ["fastupdfn.pyx"])]
)
Compilez lorsque vous êtes prêt. Compilez avec la commande suivante.
> python setup.py build_ext --inplace
Je le ferai.
> python exec_bpr.py
Data yelp.rating
#Users 25677, #newUser: 588
#Items 25815
#Ratings 627775.0 (train), 73167(test), 10056(#newTestRatings)
Run for BPR.
Iter=0 [38.7308020592] [-]loss: 624282.459815 [8.64863014221]
Iter=1 [36.7822458744] [-]loss: 616740.942017 [8.62252616882]
Iter=2 [35.8996829987] [-]loss: 609119.520253 [7.9108710289]
Iter=3 [35.1236720085] [-]loss: 600992.740207 [8.14179396629]
Iter=4 [34.9632918835] [-]loss: 591877.909123 [8.81325411797]
Il faut moins de 40 secondes pour exécuter une itération. Il est ** 3 à 4 fois plus rapide que le premier **.
Le résultat de «line_profiler» est également affiché.
> kernprof -l -v exex_bpr.py
Data yelp.rating
#Users 25677, #newUser: 588
#Items 25815
#Ratings 627775.0 (train), 73167(test), 10056(#newTestRatings)
Run for BPR.
Iter=0 [66.7851500511] [-]loss: 624400.680806 [7.92221903801]
Iter=1 [62.5339269638] [-]loss: 616866.244211 [7.85720801353]
Iter=2 [65.6408250332] [-]loss: 609235.226048 [8.48338794708]
Iter=3 [66.0613160133] [-]loss: 601140.035318 [8.52119803429]
Iter=4 [66.5882000923] [-]loss: 592026.927719 [8.32318806648]
Wrote profile results to exex_bpr.py.lprof
Timer unit: 1e-06 s
Total time: 164.139 s
File: MFbpr.py
Function: update_ui at line 93
Line # Hits Time Per Hit % Time Line Contents
==============================================================
93 @profile
94 def update_ui(self, u, i):
95 # sample a negative item(uniformly random)
96 3066856 17642519 5.8 10.7 j = np.random.randint(self.itemCount)
97 3069840 79530375 25.9 48.5 while self.trainMatrix[u, j] != 0:
98 2984 15027 5.0 0.0 j = np.random.randint(self.itemCount)
99
100 # BPR update rules
101 3066856 17651846 5.8 10.8 y_pos = self.predict(u, i) # target value of positive instance
102 3066856 10985781 3.6 6.7 y_neg = self.predict(u, j) # target value of negative instance
103 3066856 18993291 6.2 11.6 mult = -self.partial_loss(y_pos - y_neg)
104
105 3066856 19320147 6.3 11.8 self.U, self.V = fastupd.c_upd(self.U, self.V, mult, self.lr, self.reg, u, i, j, self.factors)
La part de la mise à jour de la matrice qui a dépensé à l'origine plus de 90% a été réduite à 11,8%. Vous pouvez voir l'effet de Cython.
Le profilage avec cPrifile et line_profiler a trouvé un goulot d'étranglement dans le traitement et l'a amélioré avec Cython.
Je viens de réécrire un endroit, mais c'est un peu moins de quatre fois plus rapide.
Au fait, j'ai mis le code avec Cython appliqué dans la branche w_cython de github. Il pourrait bientôt être fusionné avec master.
La partie d'instruction for met à jour les éléments de la matrice indépendamment, afin qu'elle puisse être exécutée complètement en parallèle. Cython a une fonction appelée prange () qui exécute le traitement de l'instruction for dans plusieurs threads, il est donc possible de l'améliorer un peu en appliquant ceci.
Recommended Posts