Dernière fois a été modifié. Le contenu est comme indiqué ci-dessous.
Réduction de l'utilisation de la mémoire
Introduction de la gestion des erreurs
L'accélération viendra plus tard.
Premièrement, l'implémentation précédente est très gourmande en mémoire. La cause est que P (z | x, y) est calculé dans l'étape E de l'algorithme EM. Puisque nous avons simplement créé un tableau tridimensionnel, si nous ne le créons pas, l'utilisation de la mémoire sera considérablement réduite.
Plus précisément, regardons la formule de mise à jour pour P (x | z) à l'étape M. Puisque le dénominateur est juste normalisé, nous ne considérons que la molécule.
P\left( x | z \right)Molécule= \sum_{y} N_{x, y} P \left( z | x, y \right)
Remplacez par la formule de mise à jour P (z | x, y) à l'étape E.
\begin{equation}
P\left( x | z \right)Molécule= \sum_{y} N_{x, y} \frac{P\left( z \right)P\left( x | z \right)P\left( y | z \right)}{\sum_{z} P\left( z \right)P\left( x | z \right)P\left( y | z \right)} \tag{1}
\end{equation}
Je vais implémenter cette expression, mais je ne veux pas faire tourner l'instruction for, donc j'utilise einsum de numpy.
numpy.einsum()
La fonction einsum est une réduction d'Einstein. C'est difficile à comprendre, voici donc un exemple.
P(x,y) = \sum_{z}P(z)P(x|z)P(y|z)
Lorsque vous implémentez
Pxy = numpy.einsum('k,ki,kj->ij', Pz, Px_z, Py_z)
Ce sera.
L'équation (1) est implémentée en utilisant cette fonction einsum, mais elle est difficile à implémenter telle quelle, donc l'équation est transformée comme suit.
P\left( x | z \right)Molécule= \sum_{y} \frac{N_{x, y}}{\sum_{z} P\left( z \right)P\left( x | z \right)P\left( y | z \right)} P\left( z \right)P\left( x | z \right)P\left( y | z \right)
Si vous implémentez ceci, cela ressemblera à ceci.
tmp = N / numpu.einsum('k,ki,kj->ij', Pz, Px_z, Py_z)
Px_z = numpy.einsum('ij,k,ki,kj->ki', tmp, Pz, Px_z, Py_z)
Nous verrons plus tard combien d'utilisation de la mémoire en a été réduite.
Je l'ai implémenté en utilisant la fonction einsum,
tmp = N / numpu.einsum('k,ki,kj->ij', Pz, Px_z, Py_z)
Considérez la gestion des erreurs lorsque divisée par 0 po. Le fait que ce dénominateur soit 0 signifie que pour certains x et y,
\sum_{z}P(z)P(x|z)P(y|z) = 0
Donc, aucune valeur négative ne sort, donc pour certains x et y et tous les z,
P(z)P(x|z)P(y|z) = 0
Est établi. En d'autres termes, l'étape E de l'algorithme EM est la suivante.
\begin{eqnarray}
P(z|x,y) & = & \frac{P\left( z \right)P\left( x | z \right)P\left( y | z \right)}{\sum_{z} P\left( z \right)P\left( x | z \right)P\left( y | z \right)}
& = & 0
\end{eqnarray}
Par conséquent, l'élément divisé par 0 est défini sur 0.
Où dans numpy
1 / 0 = inf
0 / 0 = nan
Donc, en utilisant respectivement numpy.isinf et numpy.isnan
tmp = N / numpu.einsum('k,ki,kj->ij', Pz, Px_z, Py_z)
tmp[numpy.isinf(tmp)] = 0
tmp[numpy.isnan(tmp)] = 0
Px_z = numpy.einsum('ij,k,ki,kj->ki', tmp, Pz, Px_z, Py_z)
Ce sera.
En résumé, la mise en œuvre globale est la suivante.
plsa.py
import numpy as np
class PLSA(object):
def __init__(self, N, Z):
self.N = N
self.X = N.shape[0]
self.Y = N.shape[1]
self.Z = Z
# P(z)
self.Pz = np.random.rand(self.Z)
# P(x|z)
self.Px_z = np.random.rand(self.Z, self.X)
# P(y|z)
self.Py_z = np.random.rand(self.Z, self.Y)
#Normalisation
self.Pz /= np.sum(self.Pz)
self.Px_z /= np.sum(self.Px_z, axis=1)[:, None]
self.Py_z /= np.sum(self.Py_z, axis=1)[:, None]
def train(self, k=200, t=1.0e-7):
'''
Répétez les étapes E et M jusqu'à ce que la probabilité logarithmique converge
'''
prev_llh = 100000
for i in xrange(k):
self.em_algorithm()
llh = self.llh()
if abs((llh - prev_llh) / prev_llh) < t:
break
prev_llh = llh
def em_algorithm(self):
'''
Algorithme EM
P(z), P(x|z), P(y|z)Mise à jour
'''
tmp = self.N / np.einsum('k,ki,kj->ij', self.Pz, self.Px_z, self.Py_z)
tmp[np.isnan(tmp)] = 0
tmp[np.isinf(tmp)] = 0
Pz = np.einsum('ij,k,ki,kj->k', tmp, self.Pz, self.Px_z, self.Py_z)
Px_z = np.einsum('ij,k,ki,kj->ki', tmp, self.Pz, self.Px_z, self.Py_z)
Py_z = np.einsum('ij,k,ki,kj->kj', tmp, self.Pz, self.Px_z, self.Py_z)
self.Pz = Pz / np.sum(Pz)
self.Px_z = Px_z / np.sum(Px_z, axis=1)[:, None]
self.Py_z = Py_z / np.sum(Py_z, axis=1)[:, None]
def llh(self):
'''
Probabilité du journal
'''
Pxy = np.einsum('k,ki,kj->ij', self.Pz, self.Px_z, self.Py_z)
Pxy /= np.sum(Pxy)
lPxy = np.log(Pxy)
lPxy[np.isinf(lPxy)] = -1000
return np.sum(self.N * lPxy)
Un dépassement inférieur peut se produire lors du calcul de la vraisemblance logarithmique, ce qui entraîne log (0) = -inf. Comme la valeur minimale du nombre à virgule flottante double précision est d'environ 4,94e-324, elle est inférieure à log (4,94e-324) = -744,4, donc -1000 est approximativement entré.
Utilisez memory_profiler pour mesurer la réduction de l'utilisation de la mémoire. Je l'ai mesuré avec le script suivant.
memory_profile.py
import numpy as np
from memory_profiler import profile
X = 1000
Y = 1000
Z = 10
@profile
def main():
from plsa import PLSA
plsa = PLSA(np.random.rand(X, Y), Z)
plsa.em_algorithm()
llh = plsa.llh()
if __name__ == '__main__':
main()
Dans le cas de X = 1000, Y = 1000, Z = 10, dans l'implémentation précédente,
$ python profile_memory_element_wise_product.py
Filename: profile_memory_element_wise_product.py
Line # Mem usage Increment Line Contents
================================================
10 15.9 MiB 0.0 MiB @profile
11 def main():
12 15.9 MiB 0.0 MiB from plsa_element_wise_product import PLSA
13 23.9 MiB 8.0 MiB plsa = PLSA(np.random.rand(X, Y), Z)
14 108.0 MiB 84.1 MiB plsa.e_step()
15 184.5 MiB 76.5 MiB plsa.m_step()
16 199.8 MiB 15.3 MiB llh = plsa.llh()
Dans cette implémentation,
$ python profile_memory_einsum.py
Filename: profile_memory_einsum.py
Line # Mem usage Increment Line Contents
================================================
10 15.8 MiB 0.0 MiB @profile
11 def main():
12 15.8 MiB 0.0 MiB from plsa_einsum import PLSA
13 23.7 MiB 7.9 MiB plsa = PLSA(np.random.rand(X, Y), Z)
14 40.7 MiB 16.9 MiB plsa.em_algorithm()
15 48.4 MiB 7.8 MiB llh = plsa.llh()
Dans le cas de X = 5000, Y = 5000, Z = 10, dans l'implémentation précédente,
$ python profile_memory_element_wise_product.py
Filename: profile_memory_element_wise_product.py
Line # Mem usage Increment Line Contents
================================================
10 15.9 MiB 0.0 MiB @profile
11 def main():
12 15.9 MiB 0.0 MiB from plsa_element_wise_product import PLSA
13 207.6 MiB 191.7 MiB plsa = PLSA(np.random.rand(X, Y), Z)
14 2115.4 MiB 1907.8 MiB plsa.e_step()
15 2115.5 MiB 0.1 MiB plsa.m_step()
16 2115.5 MiB 0.0 MiB llh = plsa.llh()
Dans cette implémentation,
$ python profile_memory_einsum.py
Filename: profile_memory_einsum.py
Line # Mem usage Increment Line Contents
================================================
10 15.7 MiB 0.0 MiB @profile
11 def main():
12 15.7 MiB 0.0 MiB from plsa_einsum import PLSA
13 207.5 MiB 191.7 MiB plsa = PLSA(np.random.rand(X, Y), Z)
14 233.0 MiB 25.6 MiB plsa.em_algorithm()
15 233.1 MiB 0.0 MiB llh = plsa.llh()
En résumé, l'utilisation totale de la mémoire est
| la mise en oeuvre | X=1000,Y=1000,Z=10 | X=5000,Y=5000,Z=10 |
|---|---|---|
| Dernière implémentation | 199.8 MiB | 2115.5 MiB |
| Cette implémentation | 48.4 MiB | 233.1 MiB |
Cependant, si nous limitons cela à l'algorithme EM et à la partie calcul de la vraisemblance logarithmique,
| la mise en oeuvre | X=1000,Y=1000,Z=10 | X=5000,Y=5000,Z=10 |
|---|---|---|
| Dernière implémentation | 175.9 MiB | 1907.9 MiB |
| Cette implémentation | 24.7 MiB | 25.6 MiB |
On peut voir que la quantité de mémoire utilisée dans cette implémentation n'a guère augmenté. Avec cela, même si le nombre de données augmente, je n'ai pas peur de la mémoire.
La fonction einsum est pratique, mais il faut beaucoup de temps pour calculer les trois ou quatre à la fois comme cette fois. Pour mon MacBook, il a fallu environ 8,7 secondes pour calculer la probabilité log et l'algorithme EM une fois à X = 5000, Y = 5000, Z = 10. Ce n'est pas réaliste et doit être amélioré, mais il y en aura d'autres à une date ultérieure.
«C'est plus long que prévu.
――La fonction einsum est également utile.
Recommended Posts