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

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.). ..

ntf_overview.png

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) $ (i_ { r} = 1,2, ..., I_ {r}) $ (r = 1,2, ..., R) $. Ici, $ K $ est le nombre de bases (le nombre de vecteurs dans chaque dimension utilisée pour l'approximation), et $ I_ {r} $ est le nombre d'éléments dans chaque vecteur. $ i_ {r} $ est un indice de l'élément de chaque vecteur. Lorsque $ L $ est un ensemble du nombre d'éléments dans chaque dimension, le tenseur obtenu par le produit de Kronecker des vecteurs est le suivant.

\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)} , mais le deuxième terme est log-sum ( \ log \ sum_ {k} f_ {k} La différenciation partielle est difficile car elle se présente sous la forme de (u_ {k {\ bf i}}) $). Donc,

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) 5 \times E_{3}
B (30, 30, 30) 5 \times E_{3}

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
ntf_demo_source_tensor.png ntf_demo_reconstruct.png

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. ntf_demo_factors.png 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

Dérivation et implémentation d'équations de mise à jour pour la décomposition de facteurs tensoriels non négatifs
Mise à jour séquentielle de la co-distribution pour la dérivation et l'implémentation des expressions
Explication et mise en œuvre de SocialFoceModel
Dérivation de l'algorithme EM et exemple de calcul pour le tirage au sort
Implémentation de Scale-Space pour SIFT
Explication et mise en œuvre de PRML Chapitre 4
Introduction et mise en œuvre de JoCoR-Loss (CVPR2020)
Explication et implémentation de l'algorithme ESIM
Introduction et mise en œuvre de la fonction d'activation
Explication et mise en œuvre du perceptron simple
[Calcul scientifique / technique par Python] Dérivation de solutions analytiques pour équations quadratiques et cubiques, formules, sympy
Dérivation de la distribution t multivariée et implémentation de la génération de nombres aléatoires par python
Mise en œuvre et expérience de la méthode de clustering convexe
Implémentation et description à l'aide de XGBoost pour les débutants
Explication et implémentation de l'algorithme Decomposable Attention
Visualisation de l'apprentissage NMF (Non-Negative Matrix Factor Decomposition)