Mise à jour séquentielle de la co-distribution pour la dérivation et l'implémentation des expressions

Déclencheur

Un membre du même laboratoire m'a demandé si je souhaitais mettre à jour séquentiellement la matrice distribuée co-distribuée, mais y a-t-il un bon moyen? J'ai trouvé cet article . Ici, nous dérivons la formule pour la mise à jour séquentielle de la moyenne et de la distribution. Veuillez consulter le site concerné pour plus de détails sur cette partie. Ici, nous allons dériver la formule de co-distribution, qui n'a pas été mentionnée en détail sur ce site, et calculer la matrice de distribution-co-distribution en Python3.

Dérivation de la covariance

Confirmation des caractères et expressions importantes

Notez les caractères et les expressions relationnelles à utiliser avant de dériver. Cela transforme beaucoup, donc si vous ne le comprenez pas en suivant la formule, revenez ici et réfléchissez-y.

Les données x=(x_1,x_2,\ ...\ ,x_n),\ y=(y_1,y_2,\ ...\ ,y_n)

Moyenne des données \overline{x_n}=\frac{1}{n}\sum_{i=1}^nx_i\ ,\ \overline{y_n}=\frac{1}{n}\sum_{i=1}^ny_i

Co-distribué s_{xy}^{n}=\frac{1}{n}\sum_{i=1}^n{\left(x_i\ -\ \overline{x_n}\ \right)\left(y_i\ -\ \overline{y_n}\ \right)}

Formule graduelle pour la valeur moyenne \overline{x_{n+1}}\ -\ \overline{x_{n}}\ =\ \frac{1}{n+1}\left(x_{n+1}\ -\ \overline{x_n}\right)\cdots\star

Dérivation de l'équation graduelle de covariance

Maintenant le sujet principal! Je vais jouer avec la formule d'ici, mais soyez patient! Calculez $ M_ {n + 1} -M_n $ avec $ M_n = ns_ {xy} ^ n $. Si cela est obtenu, l'équation graduelle de la covariance peut être facilement obtenue.

\begin{align}
M_{n+1}-M_n &= \sum_{i=1}^{n+1}\left(x_i\ -\ \overline{x_{n+1}}\ \right)\left(y_i\ -\ \overline{y_{n+1}}\ \right) -\sum_{i=1}^n\left(x_i\ -\ \overline{x_n}\ \right)\left(y_i\ -\ \overline{y_n}\ \right)\\
            &= \sum_{i=1}^{n+1}\left(x_iy_i\ -\ x_i\overline{y_{n+1}}\ -\ \overline{x_{n+1}}y_i\ +\ \overline{x_{n+1}}\ \overline{y_{n+1}}\right)\\
            &\ -\sum_{i=1}^n\left(x_iy_i\ -\ x_i\overline{y_{n}}\ -\ \overline{x_{n}}y_i\ +\ \overline{x_{n}}\ \overline{y_{n}}\right)\\
            &=x_{n+1}y_{n+1}\ +\ (n+1)\overline{x_{n+1}}\ \overline{y_{n+1}}\ -\ n\overline{x_n}\ \overline{y_n}\\
            &\ -\underline{\left(\overline{y_{n+1}}\sum_{i=1}^{n+1}x_i\ +\ \overline{x_{n+1}}\sum_{i=1}^{n+1}y_i\ -\ \overline{y_{n}}\sum_{i=1}^nx_i\ -\ \overline{x_{n}}\sum_{i=1}^ny_i\right)}\cdots\ast
\end{align}

Au fait, est-ce que tout va bien jusqu'à présent? Calculons ici avec la partie soulignée comme (1). Pour plus de simplicité, nous présenterons les deux personnages suivants. A_n=\sum_{i=1}^nx_i\ ,\ B_n=\sum_{i=1}^ny_i Débarrassons-nous de (1)!

\begin{align}
(1) &=\overline{y_{n+1}}\ A_{n+1}\ +\ \overline{x_{n+1}}\ B_{n+1}\ -\ \overline{y_n}\ A_n\ -\ \overline{x_n}\ B_n\\
    &=2\left(\frac{1}{n+1}A_{n+1}B_{n+1}\ -\ \frac{1}{n}A_nB_n\right)\\
    &=2\left\{(n+1)\ \overline{x_{n+1}}\ \overline{y_{n+1}}\ -\ n\ \overline{x_n}\ \overline{y_n}\right\}
\end{align}

Oui, c'est propre! Remplaçons cela par la partie soulignée.

\begin{align}
\ast&=x_{n+1}y_{n+1}\ +\ (n+1)\ \overline{x_{n+1}}\ \overline{y_{n+1}}\ -\ n\ \overline{x_n}\ \overline{y_n}-2\left\{(n+1)\ \overline{x_{n+1}}\ \overline{y_{n+1}}\ -\ n\ \overline{x_n}\ \overline{y_n}\right\}\\
    &=x_{n+1}y_{n+1}\ -(n+1)\ \overline{x_{n+1}}\ \overline{y_{n+1}}\ +\ n\ \overline{x_n}\ \overline{y_n}\\
    &=x_{n+1}y_{n+1}\ -(n+1)\underline{\left(\overline{x_{n+1}}\ \overline{y_{n+1}}\ -\ \overline{x_n}\ \overline{y_n}\right)}\ -\ \overline{x_n}\ \overline{y_n}\cdots\ast\ast
\end{align}

Le deuxième soulignement. Nous calculerons ici comme (2).

\begin{align}
(2)&=\left(\overline{x_{n+1}}\ -\ \overline{x_n}\right)\left(\overline{y_{n+1}}\ -\ \overline{y_n}\right)+\overline{x_{n+1}}\ \overline{y_n}+\overline{x_{n}}\ \overline{y_{n+1}}\ -2\ \overline{x_{n}}\ \overline{y_n}\\
   &=\left(\overline{x_{n+1}}\ -\ \overline{x_n}\right)\left(\overline{y_{n+1}}\ -\ \overline{y_n}\right)+\overline{y_n}\left(\overline{x_{n+1}}\ -\overline{x_n}\right)+\overline{x_n}\left(\overline{y_{n+1}}\ -\overline{y_n}\right)\\
   &=\frac{x_{n+1}-\overline{x_n}}{n+1}\cdot \frac{y_{n+1}-\overline{y_n}}{n+1}+ \overline{y_n}\ \frac{x_{n+1}-\overline{x_n}}{n+1}+\overline{x_n}\ \frac{y_{n+1}-\overline{y_n}}{n+1}\ (\because\ \star)\\
   &=\frac{1}{n+1}\left\{ \frac{1}{n+1}\left(x_{n+1}-\overline{x_n}\right)\left(y_{n+1}-\overline{y_n}\right)+\overline{y_n}\ \left(x_{n+1}-\overline{x_n}\right)+\overline{x_n}\ \left(y_{n+1}-\overline{y_n}\right)\right\}
\end{align}

Le but est juste au coin!

\begin{align}
\ast\ast&=x_{n+1}y_{n+1}\ -\frac{1}{n+1}\left(x_{n+1}-\overline{x_n}\right)\left(y_{n+1}-\overline{y_n}\right)-\overline{y_n}\ \left(x_{n+1}-\overline{x_n}\right)-\overline{x_n}\ \left(y_{n+1}-\overline{y_n}\right)-\overline{x_n}\ \overline{y_n}\\
        &=\frac{n}{n+1}\ x_{n+1}y_{n+1}\ -\ \frac{n}{n+1}\ x_{n+1}\overline{y_n}\ -\ \frac{n}{n+1}\ \overline{x_n}\ y_{n+1}\ +\frac{n}{n+1}\ \overline{x_n}\ \overline{y_n}\\
        &=\frac{n}{n+1}\ \left(x_{n+1}\ -\ \overline{x_n}\right)\ \left(y_{n+1}\ -\ \overline{y_n}\right)
\end{align}

Ceci termine la transformation principale. Je ferai la finition finale.

M_{n+1}-M_n=\frac{n}{n+1}\left(x_{n+1}\ -\ \overline{x_n}\right)\left(y_{n+1}\ -\ \overline{y_n}\right)\\
\therefore\ M_{n+1} = \frac{n}{n+1}\left(x_{n+1}\ -\ \overline{x_n}\right)\left(y_{n+1}\ -\ \overline{y_n}\right)\ +\ M_n\\
\therefore\ s_{xy}^{n+1}\ =\ \frac{n}{(n+1)^2}\left(x_{n+1}\ -\ \overline{x_n}\right)\left(y_{n+1}\ -\ \overline{y_n}\right)\ +\ \frac{n}{n+1}s_{xy}^n

Ceci complète la formule progressive.

Implémenté en Python

Maintenant que nous avons une expression graduelle, implémentons-la en Python. Cette fois, nous allons l'implémenter sous la motivation que "les vecteurs sont donnés séquentiellement et nous voulons trouver la matrice de variance-co-distribution de l'ensemble de vecteurs".

import numpy as np

def calc(next_val,times,var_cov_mat=None):
    '''
Faites le calcul
    '''
    if times > 1:
        #Mise à jour de la matrice de co-distribution de distribution
        var_cov_mat = np.outer(next_val,n_mean)*(times/(times+1)**2) + var_cov_mat*times/(times+1)
    else:
        #Définir l'état initial, matrice co-distribuée distribuée = matrice unitaire
        var_cov_mat = np.identity(len(next_val))

    return next_mean, var_cov_mat

Ceci termine. Après cela, vous pouvez obtenir la matrice distribuée co-distribuée de manière séquentielle en insérant de plus en plus de données.

Vérification

Cette fois, nous utiliserons un vecteur de 512 dimensions. Chaque composant du vecteur a reçu au hasard un nombre supérieur ou égal à 0 et inférieur à 1. La méthode de comparaison consiste à regarder la transition de l'erreur quadratique moyenne pour chaque composant de la matrice obtenue par la méthode ci-dessus et la matrice calculée par numpy une fois. Cliquez ici pour les résultats. MSE_test3.png

Le calcul de 500 fois est effectué en un peu plus de 4 secondes, et il est en train de passer à environ 0,06.

Résumé

Cette fois, nous avons dérivé une expression graduelle de co-distribution qui permet la mise à jour séquentielle de la co-distribution et l'avons implémentée en Python. Je pense que les résultats du calcul sont bien écrits, mais si quelqu'un dit "Je pourrais l'écrire plus joliment!", Faites-le moi savoir. En ce qui concerne la mise en œuvre, comme je l'ai écrit dans la première introduction, je suis partie de l'endroit où j'ai reçu la consultation, et je la mets en œuvre sous une forme qui reflète le contenu de la consultation que j'ai reçue, donc si vous voulez la mettre en œuvre sous une autre forme, la première moitié J'espère que vous pourrez l'implémenter en utilisant la partie expression.

A partir de maintenant, cela n'a plus rien à voir avec la ligne principale, mais cette transformation de formule a été assez difficile. Si vous êtes intéressé par la transformation de formule, il peut être judicieux de remplir les trous dans la partie ci-dessus. J'avais l'intention de le remplir très soigneusement, donc si vous pensez qu'il n'y a pas de place pour le remplir, il peut être intéressant de le calculer vous-même dès le début.

Site référencé

Mise à jour séquentielle de la distribution

Recommended Posts

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
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
Dérivation de la distribution t multivariée et implémentation de la génération de nombres aléatoires par python
Implémentation du filtre à particules par Python et application au modèle d'espace d'états
Mise en œuvre et expérience de la méthode de clustering convexe
Explication et implémentation de l'algorithme Decomposable Attention
J'ai essayé de notifier la mise à jour de "Hameln" en utilisant "Beautiful Soup" et "IFTTT"
Créez un environnement python pour apprendre la théorie et la mise en œuvre de l'apprentissage profond
J'ai essayé d'informer Slack de la mise à jour de Redmine
Comparaison d'exemples d'implémentation de k-means de scikit-learn et pyclustering
Script pour tweeter avec des multiples de 3 et des nombres avec 3 !!
Implémentation de l'arbre TRIE avec Python et LOUDS
Liste de code Python à déplacer et à mémoriser
Explication de la distance d'édition et de l'implémentation en Python
[Introduction à Python] Utilisation de base des expressions lambda
J'ai essayé de notifier la mise à jour de "Devenir romancier" en utilisant "IFTTT" et "Devenir un romancier API"
J'ai essayé d'automatiser la mise à jour de l'article du blog Livedoor avec Python et sélénium.