[PYTHON] Dérivation et implémentation d'équations de mise à jour pour la décomposition de facteurs tensoriels non négatifs
Code que j'ai écrit
C'est un résultat enfantin, mais je fais Publier le code sur Github.
Les références
- [1] Hirokazu Kameoka: Introduction à la décomposition des facteurs matriciels non négatifs - avec le traitement du signal acoustique comme sujet - (Vous pouvez comprendre NMF visuellement)
- [2] Hiroshi Sawada: Principes de base de la décomposition des facteurs matriciels non négatifs NMF et son application à l'analyse des données / signaux (Article de commentaire NMF facile à comprendre)
- [3] Suite / Reconnaissance de formes facile à comprendre - Introduction à l'apprentissage non supervisé -
- [4] Tatsufumi Matsubayashi et al.: Analyse de la sélection des marques dans le comportement d'achat par décomposition par facteur tenseur non négatif (Il décrit comment utiliser NTF pour les données réelles)
- [5] Koh Takeuchi et al.: Non-negative Multiple Tensor Factorization (Bien qu'il s'agisse d'un article NTF étendu, il est également utile pour comprendre NTF)
La littérature [1,2,4,5] est actuellement disponible gratuitement sur Internet, elle est donc fortement recommandée pour ceux qui sont pauvres comme eux (ceux qui ne peuvent pas télécharger librement les articles). En particulier, pour ceux qui ne comprennent pas la factorisation matricielle non négative (NMF) avant la factorisation tensorielle non négative (NTF), la littérature [1] [2] est disponible. C'est très facile à comprendre, je recommande donc de le lire avant cet article. La référence [3] a une expansion mathématique très polie, qui est la plus facile à comprendre dans le livre d'estimation bayésienne, qui est également recommandée.
Ma compréhension approximative
Décomposition du facteur tenseur non négatif Le NTF révisé est un calcul de décomposition qui se rapproche d'un tenseur avec un produit tensoriel non négatif de bas rang. N'ayez pas peur de vous méprendre, au niveau secondaire, vous pouvez factoriser une matrice de grande taille dans une matrice de petite taille avec chaque composante supérieure ou égale à 0. Les tensols sont des extensions des concepts de scalaires, de vecteurs et de matrices, qui peuvent être paraphrasés respectivement comme des tenseurs d'ordre 0, des tenseurs du 1er ordre et des tenseurs du 2ème ordre. Largement utilisé dans divers domaines de recherche, le NMF est un NTF limité au tenseur du deuxième étage.
Même une énorme quantité de données que les humains ne peuvent pas comprendre à première vue peut être décomposée en tenseurs de bas rang en appliquant NTF pour extraire les relations entre plusieurs facteurs, ce qui rend le format de données facile à comprendre pour les humains. Pour une compréhension intuitive, ce qui suit est une image de poinçon montrant que le tenseur du troisième ordre $ X $ peut être approximativement décomposé en trois tenseurs d'ordre inférieur $ T, U, V $ (matrice, vecteur, etc.). ..
NMF ne pouvait extraire les relations entre les facteurs que dans les données bidimensionnelles. D'autre part, NTF peut extraire les relations entre les facteurs par le nombre d'ordres du tenseur, il est donc possible d'analyser des relations plus compliquées. Cela signifie également que les données difficiles à visualiser dans quatre dimensions ou plus peuvent être visualisées indirectement sous la forme de tendances.
NTF est basé sur la minimisation de la distance (fonction de coût) entre le tenseur d'origine et le tenseur reconstruit à partir du produit des vecteurs approchés. Toute méthode peut être utilisée pour résoudre cette minimisation de distance, mais la solution converge efficacement en répétant le calcul de la valeur attendue du tenseur approché et la minimisation de la fonction de coût lors de son utilisation. C'est connu (pas besoin de calculer la matrice inverse, qui tend à être une décomposition tenseur!), Et cette approche est souvent utilisée. En d'autres termes, en pratique, si vous connaissez cette formule de mise à jour, vous pourrez analyser les données à l'aide de NTF.
Dérivation de la formule de mise à jour
Pour ceux qui utilisent l'apprentissage automatique comme un simple outil tel que NTF, le processus de conversion des formules mathématiques ici a tendance à être négligé, mais l'extension de l'algorithme en concevant et modélisant la fonction de coût en fonction des caractéristiques des données C'est une connaissance essentielle à gérer. J'ai donc fait de mon mieux pour développer la formule avec ma propre compréhension.
En gros, lorsque la différenciation partielle de la fonction de coût devient 0, la formule de mise à jour est dérivée en prenant la valeur minimale de la fonction de coût.
Définition de la fonction de coût
La divergence $ \ Beta $ est souvent utilisée pour les fonctions de coût, mais cette fois nous allons nous concentrer sur sa forme spéciale, la divergence KL généralisée. Soit $ u_ {ki_ {r}} ^ {(r)} $ le vecteur obtenu en décomposant le tenseur de l'ordre $ R $. $ (K = 1,2, ..., K)
\hat{x}_{\bf i} = \sum_{k=1}^{K} \prod_{r=1}^{R}
u_{ki_{r}}^{(r)}
\quad ({\bf i} = i_{1}i_{2}...i_{R} \in L) \quad (1)
La fonction de coût basée sur la divergence KL généralisée est la suivante.
D(X, \hat{X})
= \sum_{{\bf i} \in L}(
x_{\bf i}\log\frac{x_{\bf i}}{\hat{x}_{\bf i}}
- x_{\bf i} + \hat{x}_{\bf i}) \quad (2)
Cette fonction de coût est 0 lorsque le tenseur $ X $ à approximer et le tenseur $ \ hat {X} $ à approximer correspondent exactement. En substituant l'équation (1) à l'équation (2) et en convertissant la fraction de $ \ log $ en somme, on obtient l'équation suivante.
D(X, \hat{X})
= \sum_{{\bf i} \in L}(
x_{\bf i}\log x_{\bf i}
- x_{\bf i}\log \sum_{k=1}^{K}
\prod_{r=1}^{R} u_{ki_{r}}^{(r)}
- x_{\bf i} + \sum_{k=1}^{K}
\prod_{r=1}^{R} u_{ki_{r}}^{(r)}) \quad (3)
Différenciation partielle de la fonction de coût
Je veux faire une différenciation partielle rapide de l'équation (3) avec $ u_ {ki_ {r}} ^ {(r)}
h_{k{\bf i}}^{0} = \frac{
\prod_{r=1}^{R} u_{ki_{r}}^{0(r)}
}{
\hat{x}_{\bf i}^{0}
} \quad (4)
Définissez une variable qui a la propriété $ \ sum_ {k = 1} ^ {K} h_ {k {\ bf i}} = 1, h_ {k {\ bf i}} \ geq 0 $. Ici, 0 sur l'épaule droite de chaque variable indique qu'elle est avant la mise à jour. Pour le deuxième terme de l'équation (3), ajoutez $ h_ {k {\ bf i}} / h_ {k {\ bf i}} (= 1) $ composé de l'équation (4) à * Jensen * En utilisant l'inégalité de, la limite supérieure du deuxième terme ayant la forme de somme-log ($ \ sum_ {k} \ log f_ {k} (u_ {k {\ bf i}}) $) comme suit. Peut être dérivé.
- x_{\bf i} \log \sum_{k=1}^{K}
h_{k{\bf i}}^{0}
\frac{\prod_{r=1}^{R} u_{ki_{r}}^{(r)}}
{h_{k{\bf i}}^{0}} \leq - x_{\bf i}
\sum h_{k{\bf i}}^{0} \log
\frac{\prod_{r=1}^{R} u_{ki_{r}}^{(r)}}
{h_{k{\bf i}}^{0}} \quad (5)
En remplaçant l'équation (5) par l'équation (3), la limite supérieure de la fonction de coût peut être dérivée comme indiqué dans l'équation suivante.
D(X, \hat{X}) \leq
\sum_{{\bf i} \in L}(
x_{\bf i}\log x_{\bf i}
- x_{\bf i} \sum h_{k{\bf i}}^{0} \log \frac{\prod_{r=1}^{R} u_{ki_{r}}^{(r)}}
{h_{k{\bf i}}^{0}}
- x_{\bf i} + \sum_{k=1}^{K}
\prod_{r=1}^{R} u_{ki_{r}}^{(r)}) \\
= \sum_{{\bf i} \in L}(
- x_{\bf i} \sum h_{k{\bf i}} \log \prod_{r=1}^{R} u_{ki_{r}}^{(r)}
+ \sum_{k=1}^{K}
\prod_{r=1}^{R} u_{ki_{r}}^{(r)}
+ C)
\quad (6)
Ici, les termes qui n'incluent pas $ u_ {ki_ {r}} ^ {(r)} $ deviennent 0 dans le processus de la différenciation partielle suivante, ils sont donc résumés par le terme constant $ C $. Afin de minimiser la limite supérieure de cette fonction de coût, l'équation suivante est obtenue en définissant l'équation (6) sur 0, qui est partiellement différenciée par $ u_ {ki_ {r}} ^ {(r)} $.
0 = \sum_{{\bf i} \in L_{-r}} (
- x_{\bf i}
\frac{h_{k{\bf i}}^{0}}{u_{ki_{r}}^{(r)}} +
\prod_{\substack{r=1 \\ \bar{r} \neq r} }^{R}
u_{ki_{\bar{r}}}^{(\bar{r})}
) \quad (7)
Où $ L_ {-r} $ est ($ \ bar {\ bf i} = i_ {1} ... i_ {r-1} i_ {r + 1} ... i_ {R} \ in L_ C'est un ensemble appelé {-r} $). L'équation de mise à jour suivante peut être obtenue en réorganisant l'équation (7) pour $ u_ {ki_ {r}} ^ {(r)} $ en utilisant également l'équation (4).
u_{ki_{r}}^{(r)} = u_{ki_{r}}^{0(r)} \cdot
\frac{
\sum_{\bar{\bf i} \in L_{-r}}
(x_{\bar{\bf i}}
/ \hat{x}_{\bar{\bf i}}^{0})
\prod_{\substack{\bar{r}=1 \\ \bar{r} \neq r} }^{R}
u_{ki_{\bar{r}}}^{0(\bar{r})}
}{
\sum_{\bar{\bf i} \in L_{-r}}
\prod_{\substack{\bar{r}=1 \\ \bar{r} \neq r} }^{R}
u_{ki_{\bar{r}}}^{(\bar{r})}
} \quad (8)
$ U_ {ki_ {r}} ^ {(r)} $ obtenu en minimisant la limite supérieure de la fonction de coût est défini comme $ h_ {k {\ bf i}} ^ {0} $, et la limite supérieure de la fonction de coût est ensuite définie. Une mise à jour séquentielle qui minimise la valeur produit un minimum de $ D (X, \ hat {X}) $. $ {\ Bf u} _ {k} ^ {(r)} $ au moment où la valeur minimale est obtenue est un tenseur approximatif obtenu en factorisant le tenseur d'origine.
la mise en oeuvre
Implémenté avec Python + Numpy. Utilisez pip``` pour supprimer la bibliothèque manquante. Pour ceux qui sont nouveaux dans Python + Numpy, il est difficile de devenir accro à l'utilisation de Anaconda, qui inclut divers packages depuis le début.
Si les données d'entrée sont une matrice, le NTF, ou NMF, du tenseur du second ordre est également possible. Je montrerai le code uniquement pour la partie d'expression de mise à jour importante.
ntf.py
class NTF():
#Diverses autres fonctions membres, etc. sont omises...
def updateBasedOnGKLD(self, x, factor, index):
# Create tensor partly.
element = self.kronAlongIndex(factor, index)
# Summation
element = element.reshape(self.preshape[index])
estimation = self.createTensorFromFactors()
boost = x/(estimation + EPS)
numer = self.sumAlongIndex(boost*element, factor, index)
denom = np.sum(element)
return numer/(denom + EPS)
def kronAlongIndex(self, factor, index):
element = np.array([1])
for i1 in factor[:index]:
element = np.kron(element, i1)
for i1 in factor[index + 1:]:
element = np.kron(element, i1)
return element
def sumAlongIndex(self, value, factor, index):
for _ in np.arange(index):
value = np.sum(value, axis=0)
for _ in np.arange(index + 1, len(factor)):
value = np.sum(value, axis=1)
return value
def createTensorFromFactors(self):
tensor = self.composeTensor(self.factor)
tensor = np.sum(tensor, axis=0)
return tensor.reshape(self.shape)
#La fonction qui est la substance de composeTensor.
def composeTensorSerially(self, element):
return map(self.kronAll, element)
def kronAll(self, factor):
element = np.array([1])
for i1 in factor:
element = np.kron(element, i1)
return element
Bien qu'il s'agisse de Python, il existe de nombreuses déclarations `` pour '' et cela semble sale, mais il est délicat de s'en tenir à ici, alors je le laisse tranquille. \ # Si vous savez écrire magnifiquement ou comment écrire à une vitesse explosive, veuillez pull request.
Expérience
J'ai fait une expérience (ou plutôt une démo) de regroupement de nombres aléatoires créés à partir d'une distribution gaussienne.
Conditions expérimentales
Nous avons pulvérisé 100 échantillons dans l'espace 3D, respectivement, sur la base des deux distributions gaussiennes suivantes.
| ID | moyenne | Distribué |
|---|---|---|
| A | (10, 10, 20) | |
| B | (30, 30, 30) |
C'est un corps qui est déjà connu pour avoir des échantillons semés à partir de deux grappes, et bien qu'il s'agisse d'une pompe d'allumette, le nombre de bases est de 2. En d'autres termes, le tenseur du 3ème ordre est décomposé en un vecteur approché à 2 bases.
Exécutez run_ntf_demo_3rd_order_2bases.py pour retester. De plus, un code qui vous permet d'essayer la même expérience avec différents paramètres (par exemple, l'ordre des tenseurs, le numéro de base, etc.) est également disponible avec un nom tel que [run_ntf_demo_ \ *. Py](https://github.com/drumichiro/ nmf-et-ntf / blob / master / run_ntf_demo_4th_order_2bases.py).
résultat
La distribution (tenseur) de l'échantillon reconstruit par le produit de Kronecker à partir du vecteur approximatif est indiquée sur le côté droit de la figure ci-dessous. La distribution de l'échantillon d'origine est également présentée à gauche pour comparaison. Veuillez noter que les valeurs attribuées à chaque axe sont des indices pour chaque case divisée, de sorte que la moyenne et la fraction indiquées dans les conditions expérimentales ne correspondent pas.
| Distribution de l'échantillon original | Distribution d'échantillons reconstruits à partir de vecteurs d'approximation |
|---|---|
 |
 |
Vous pouvez voir que les distributions des deux échantillons sont proches. Le vecteur d'approximation utilisé pour reconstruire la distribution de l'échantillon est le suivant.
L'axe horizontal est l'axe des facteurs. L'axe vertical est l'axe de la base, mais vous pouvez voir qu'une distribution gaussienne est distribuée à chaque base. Eh bien, avec ce genre de sentiment, j'ai pu confirmer que le code était assemblé tel quel.
Supplément
NTF appliqué à l'historique d'achat des coupons. Ceci est un exemple plus pratique, veuillez donc voir ici si vous le souhaitez.
Recommended Posts