Calculer les paires de distance en un lot, sans les reproduire tenseur dans Tensorflow?

Je veux calculer les combinaisons carré de la distance d'un lot de fonctionnalité dans Tensorflow. J'ai une simple mise en œuvre à l'aide de + et * les opérations par
carrelage du tenseur d'origine :

def pairwise_l2_norm2(x, y, scope=None):
    with tf.op_scope([x, y], scope, 'pairwise_l2_norm2'):
        size_x = tf.shape(x)[0]
        size_y = tf.shape(y)[0]
        xx = tf.expand_dims(x, -1)
        xx = tf.tile(xx, tf.pack([1, 1, size_y]))

        yy = tf.expand_dims(y, -1)
        yy = tf.tile(yy, tf.pack([1, 1, size_x]))
        yy = tf.transpose(yy, perm=[2, 1, 0])

        diff = tf.sub(xx, yy)
        square_diff = tf.square(diff)

        square_dist = tf.reduce_sum(square_diff, 1)

        return square_dist

Cette fonction prend en entrée deux matrices de taille (m,d) et (n,d), et de calculer la distance au carré entre chaque vecteur ligne. La sortie est une matrice de taille (m,n) avec élément " d_ij = dist(x_i, y_j)'.

Le problème est que j'ai un gros lot et de la haute dim fonctions "m, n, d' reproduisant le tenseur de consommer beaucoup de mémoire.
Je suis à la recherche d'une autre façon de mettre en œuvre ce sans augmentation de l'utilisation de la mémoire et juste que le magasin de la distance finale tenseur. Sorte de double boucle du tenseur d'origine.

Il n'est pas évident que votre code est en train de faire 'par paires distance d'un lot de la fonctionnalité". Pouvez-vous préciser la fonction que vous voulez le faire de façon plus formelle? Aussi, avez-vous considéré tf.squared_difference
- Je mettre à jour la question de l'expliquer. Si vous mettez un lot de fonctionnalités que l'entrée de cette fonction, il faut calculer la distance entre ses lignes.

InformationsquelleAutor jrabary | 2016-05-03

python tensorflow

51

Vous pouvez utiliser de l'algèbre linéaire pour le transformer en matrice de la fpo. Notez que ce que vous avez besoin de la matrice D où a[i] est le ième ligne de la matrice d'origine et
```
D[i,j] = (a[i]-a[j])(a[i]-a[j])'
```
Vous pouvez réécrire en
```
D[i,j] = r[i] - 2 a[i]a[j]' + r[j]
```
Où r[i] est le carré de la norme de iième ligne de la matrice d'origine.

Dans un système qui prend en charge la norme les règles de la radiodiffusion vous pouvez traiter r comme un vecteur colonne et écrire D comme
```
D = r - 2 A A' + r'
```
Dans TensorFlow vous pouvez écrire ce que
```
A = tf.constant([[1, 1], [2, 2], [3, 3]])
r = tf.reduce_sum(A*A, 1)

# turn r into column vector
r = tf.reshape(r, [-1, 1])
D = r - 2*tf.matmul(A, tf.transpose(A)) + tf.transpose(r)
sess = tf.Session()
sess.run(D)
```
résultat
```
array([[0, 2, 8],
       [2, 0, 2],
       [8, 2, 0]], dtype=int32)
```
- Je vous remercie. Je comprends mieux pourquoi la radiodiffusion est intéressant.
- Savez-vous si cette approche est préférable à l'utilisation tf.expand_dims à exploiter la radiodiffusion et ensuite utiliser tf.squared_difference?
- Pas sûr. Il y a un transpose dans ma solution qui est coûteux. Si vous postez une solution comme une autre réponse que j'ai pu comparer la performance sur la grande matrice
- posté!
- Je ne sais pas combien d'amélioration de la performance de cette offre, mais tf.matmul a des arguments pour la transposition de tableaux à la volée (transpose_a et transpose_b).
InformationsquelleAutor Yaroslav Bulatov
12

À l'aide de squared_difference:
```
def squared_dist(A): 
    expanded_a = tf.expand_dims(A, 1)
    expanded_b = tf.expand_dims(A, 0)
    distances = tf.reduce_sum(tf.squared_difference(expanded_a, expanded_b), 2)
    return distances
```
Une chose que j'ai remarqué, c'est que cette solution à l'aide de tf.squared_difference me donne de mémoire (OOM) pour de très grands vecteurs, alors que l'approche par @YaroslavBulatov ne l'est pas. Donc, je pense que la décomposition de l'opération génère une plus petite empreinte mémoire (qui je pensais squared_difference serait mieux gérer sous le capot).
- merci pour l'information que l'autre solution est moins gourmande en mémoire. bon à savoir ça. +1 pour la réponse très
- Cette solution est également moins de calcul efficace. Mais c'est très utile quand il n'y a pas de possibilité d'utiliser la matrice de multiplication (par exemple pour la distance absolue)
InformationsquelleAutor Yamaneko

Ici est un plus générale de la solution de deux tenseurs de coordonnées A et B:

def squared_dist(A, B):
  assert A.shape.as_list() == B.shape.as_list()

  row_norms_A = tf.reduce_sum(tf.square(A), axis=1)
  row_norms_A = tf.reshape(row_norms_A, [-1, 1])  # Column vector.

  row_norms_B = tf.reduce_sum(tf.square(B), axis=1)
  row_norms_B = tf.reshape(row_norms_B, [1, -1])  # Row vector.

  return row_norms_A - 2 * tf.matmul(A, tf.transpose(B)) + row_norms_B

Noter que c'est le carré de la distance. Si vous voulez changer la distance Euclidienne, effectuer une tf.sqrt sur le résultat. Si vous voulez le faire, n'oubliez pas d'ajouter une petite constante pour compenser la virgule flottante instabilités: dist = tf.sqrt(squared_dist(A, B) + 1e-6).

InformationsquelleAutor Augustin

Si vous voulez calculer les autres méthode , puis changer l'ordre de la tf modules.

def compute_euclidean_distance(x, y):
    size_x = x.shape.dims[0]
    size_y = y.shape.dims[0]
    for i in range(size_x):
        tile_one = tf.reshape(tf.tile(x[i], [size_y]), [size_y, -1])
        eu_one = tf.expand_dims(tf.sqrt(tf.reduce_sum(tf.pow(tf.subtract(tile_one, y), 2), axis=1)), axis=0)
        if i == 0:
            d = eu_one
        else:
            d = tf.concat([d, eu_one], axis=0)
return d

InformationsquelleAutor Hyunguk Choi

Vous devez vous connecter pour publier un commentaire.