Neulich habe ich einen Empfehlungsalgorithmus namens Bayesian Personalized Ranking (BPR) implementiert.
X = U \cdot V^T
Ich werde zusammenfassen, was ich damals als Memorandum versucht habe. Die in diesem Artikel verwendete Technik und der Code BPR geben eine Matrixzerlegung einer Benutzer-x-Elementmatrix an. Zerlegt die Benutzer x Artikelmatrix $ X $ in die Benutzer x Faktormatrix $ U $ und die Artikel x Faktormatrix $ V $. Informationen zur Lösung dieses Problems finden Sie im [Originalpapier] von BPR (http://arxiv.org/abs/1205.2618). Ich habe diese Technik wie folgt implementiert. $ X $ ist in scipy.sparse.lil_matrix definiert. Die zerlegten $ U $ und $ V $ sind numpy.array.
Der Ablauf besteht darin, das für das Training verwendete Beispiel zu booten und dann $ U und V $ zu aktualisieren.
Für diesen Code möchte ich buildModel () verbessern, das der lernende Teil des Modells ist.
MFbpr.py
class MFbpr(Recommender):
'''
Konstruktor und andere Verarbeitung
'''
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):
'''
Der Prozess des Ladens von Daten
'''
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()
Die gesamte Codemenge ist auf github verfügbar.
Ich werde es vorerst versuchen.
Es ist Ubuntu mit 2G-Speicher und 2 Prozessoren, die auf VirtualBox basieren.
Die erste Schlüsselklammer ist die Zeit, die für eine Iteration (en) benötigt wurde, und die letzte Schlüsselklammer ist die Zeit, die zur Berechnung der Verluste benötigt wurde.
> 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]
Obwohl ich ungefähr 600.000 Samples berechne, halte ich 130 Sekunden pro Iteration für zu lang.
Beginnen wir mit der Identifizierung der Teile, die lange dauern.
Verwenden Sie den Python-Profiler "cProfile", um die Verarbeitungsgeschwindigkeit zu messen.
python -m cProfile -s cumulative ***.py
Wenn Sie ausführen, wird die zeitaufwändige Verarbeitung in absteigender Reihenfolge angezeigt.
> 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)
Am Ende der Zeile "Sortiert nach: kumulative Zeit" werden die Funktionsnamen und die für die Verarbeitung erforderliche Zeit aufgelistet. Wenn Sie sich das ansehen, können Sie sehen, dass die Funktion "update_ui" 3.067.088 Mal aufgerufen wird und insgesamt 535,383 Sekunden dauert.
(Nun, es ist nur natürlich, dass nur update_ui in buildModel aufgerufen wird ...)
Aufgrund des Overheads von cProfile ist die Ausführungszeit einer Iteration länger als zuvor.
Mit line_profiler können Sie die Funktion von Interesse Zeile für Zeile messen. Sie können es mit pip installieren.
> pip install line_profiler
Um mit line_profiler zu profilieren, müssen Sie der betrachteten Funktion einen @ profile -Dekorator hinzufügen.
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])
Alles was Sie tun müssen, ist es mit dem Befehl kernprof auszuführen.
> 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])
In der Spalte "% Time" haben wir festgestellt, dass ** 90% oder mehr der Verarbeitungszeit von "update_ui" unter der for-Anweisung ** verbracht wurden.
Eine Iteration dauert weniger als 1.000 Sekunden, was bedeutet, dass der Overhead hoch ist.
Schreiben Sie die vorherige for-Schleife mit Cython neu. Einer der Gründe, warum Python langsam ist, ist die dynamische Typisierung. Da der Typ jedes Mal überprüft wird, wenn auf eine Variable verwiesen wird, können Programme mit vielen Variablenreferenzen die für diesen Vorgang erforderliche Zeit nicht ignorieren.
Wenn Sie mit Cython schreiben, können Sie den Variablentyp wie die Sprache c definieren. Da der Typ nicht einzeln bestätigt wird, ist mit einer erheblichen Beschleunigung zu rechnen.
Deklarieren Sie Variablen mit cdef. Definieren Sie die Typen aller in der Berechnung verwendeten Variablen.
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
Der Anrufer wird wie folgt umgeschrieben.
MFbpr.py
import fastupd #hinzufügen
class MFbpr(Recommender):
"""
Unterlassung
"""
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)
#Rufen Sie die Cython-Implementierung auf
self.U, self.V = fastupd.c_upd(self.U, self.V, mult, self.lr, self.reg, u, i, j, self.factors)
Sie benötigen außerdem eine setup.py, um Ihre Cython-Implementierung zu kompilieren.
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"])]
)
Kompilieren Sie, wenn Sie bereit sind. Kompilieren Sie mit dem folgenden Befehl.
> python setup.py build_ext --inplace
Ich werde das machen.
> 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]
Die Ausführung einer Iteration dauert weniger als 40 Sekunden. Es ist 3-4 mal schneller als das erste **.
Das Ergebnis von line_profiler wird ebenfalls veröffentlicht.
> 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)
Der Teil des Matrix-Updates, der ursprünglich mehr als 90% ausgegeben hat, wurde auf 11,8% reduziert. Sie können die Wirkung von Cython sehen.
Die Profilerstellung mit "cPrifile" und "line_profiler" hat einen Verarbeitungsengpass festgestellt und mit "Cython" verbessert. Ich habe nur einen Ort umgeschrieben, aber es ist etwas weniger als viermal schneller.
Übrigens habe ich den Code mit Cython in den Zweig w_cython von github eingefügt. Es kann bald in Master zusammengeführt werden.
Der for-Anweisungsteil aktualisiert die Elemente der Matrix unabhängig voneinander, sodass sie vollständig parallel ausgeführt werden kann. Cython hat eine Funktion namens "prange ()", die die Verarbeitung der for-Anweisung in mehreren Threads ausführt, sodass es möglicherweise möglich ist, sie durch Anwenden dieser Anweisung ein wenig zu verbessern.
Recommended Posts