Parlez de l'amélioration du goulot d'étranglement des algorithmes d'apprentissage automatique avec Cython

À propos de cet article

introduction

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.

Techniques et code utilisés dans cet article

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.

Essayez de courir

Je vais l'essayer pour le moment.

Réglage

Les données

--Nombre d'utilisateurs: 25677 --Nombre d'articles: 25815 --Nombre de notes (nombre d'échantillons avec notes): 627775

Hyper paramètres

--Nombre de facteurs: 64

Environnement d'exécution

C'est ubuntu avec une mémoire 2G et 2 processeurs basés sur VirtualBox.

Résultat d'exécution

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.

Profilage

Profilage global

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.

Profilage ligne par ligne

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.

Accélérez avec Cython

la mise en oeuvre

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

Courir

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.

Résumé

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.

prime?

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

Parlez de l'amélioration du goulot d'étranglement des algorithmes d'apprentissage automatique avec Cython
Une histoire sur l'apprentissage automatique avec Kyasuket
Apprentissage automatique sur le surapprentissage
L'apprentissage automatique appris avec Pokemon
Apprentissage automatique avec Python! Préparation
À propos de la matrice mixte d'apprentissage automatique
Démineur d'apprentissage automatique avec PyTorch
Algorithme d'apprentissage automatique (perceptron simple)
Commencer avec l'apprentissage automatique Python
Algorithme d'apprentissage automatique (machine vectorielle de support)
Essayez le machine learning à la légère avec Kaggle
Algorithme d'apprentissage automatique (régression logistique)
<Course> Machine learning Chapitre 6: Algorithme 2 (k-means)
Algorithme d'apprentissage automatique (prise en charge de l'application de machine vectorielle)
J'ai essayé l'apprentissage automatique avec liblinear
Apprentissage automatique par python (1) Classification générale
Algorithme d'apprentissage automatique (analyse de régression unique)
SVM essayant l'apprentissage automatique avec scikit-learn
Algorithme d'apprentissage automatique (méthode de descente de gradient)
Machine learning d'inspiration quantique avec des réseaux de tenseurs
Mémo d'apprentissage "Scraping & Machine Learning avec Python"
Vulkan compute avec Python avec VkInline et pense à l'apprentissage automatique GPU et plus
Une histoire sur l'automatisation du mahjong en ligne (Jakutama) avec OpenCV et l'apprentissage automatique
[Exemple d'amélioration de Python] Apprentissage de Python avec Codecademy
Algorithme d'apprentissage automatique (généralisation de la régression linéaire)
Prédire la demande de puissance avec l'apprentissage automatique, partie 2
Amplifiez les images pour l'apprentissage automatique avec Python
Apprentissage automatique avec python (2) Analyse de régression simple
Algorithme d'apprentissage automatique (implémentation de la classification multi-classes)
Notes personnelles et liens sur l'apprentissage automatique ① (Machine learning)
Résumé de la classification et de la mise en œuvre des algorithmes d'apprentissage automatique
Apprentissage automatique avec Pytorch sur Google Colab
Algorithme d'apprentissage automatique (résumé de régression linéaire et régularisation)
Construction d'environnement AI / Machine Learning avec Python
[Python] Introduction facile à l'apprentissage automatique avec python (SVM)
Une histoire sur l'apprentissage automatique simple avec TensorFlow
Apprentissage automatique à partir de Python Personal Memorandum Part2
Algorithme EM modèle mixte gaussien [apprentissage automatique statistique]
Apprentissage automatique à partir de Python Personal Memorandum Part1
[Python] Collectez des images avec Icrawler pour l'apprentissage automatique [1000 feuilles]
Apprentissage automatique à partir de zéro (apprentissage automatique appris avec Kaggle)
À propos du contenu de développement de l'apprentissage automatique (exemple)
J'ai commencé l'apprentissage automatique avec le prétraitement des données Python
Histoire de l'analyse de données par apprentissage automatique
Créer un environnement d'apprentissage automatique Python avec des conteneurs