2
$\begingroup$

TLDR: given two tensors $t_1$ and $t_2$, both with shape $(c,h,w),$ how shall the distance between them be measured?


More Info: I'm working on a project in which I'm trying to distinguish between an anomalous sample (specifically from MNIST) and a "regular" sample (specifically from CIFAR10). The solution I chose is to consider the feature maps that are given by ResNet and use kNN. More specifically:

  • I embed the entire CIFAR10_TRAIN data to achieve a dataset that consists of activations with dimension $(N,c,h,w)$ where $N$ is the size of CIFAR_TRAIN
  • I embed $2$ new test samples $t_C$ and $t_M$ from CIFAR10_TEST and MNIST_TEST respectively (both with shape $(c,h,w)$), same as I did with the training data.
  • (!) I find the k-Nearest-Neighbours of $t_C$ and $t_M$ w.r.t the embedding of the training data
  • I calculate the mean distance between the $k$ neighbors
  • Given some predefined threshold, I classify $t_C$ and $t_M$ as regular or anomalous, hoping that the distance for $t_M$ would be higher, as it represents O.O.D sample.

Notice that in (!) I need some distance measure, but this is not trivial as these are tensors, not vectors.


What I've Tried: a trivial solution is to flatten the tensor to have shape $(c\cdot h\cdot w)$ and then use basic $\ell_2$, but the results turned out pretty bad. (could not distinguish regular vs anomalous in this case). Hence: Is there a better way of measuring this distance?

$\endgroup$

1 Answer 1

2
$\begingroup$

You could try an earthmovers distance (https://en.m.wikipedia.org/wiki/Earth_mover%27s_distance) in 2d or 3d over the image? For example you could do this, but call sequentially (https://discuss.pytorch.org/t/implementation-of-squared-earth-movers-distance-loss-function-for-ordinal-scale/107927/2) The idea would be something like this (untested and written on my cell phone):

def cumsum_3d(a):
    a = torch.cumsum(a, -1)
    a = torch.cumsum(a, -2)
    a = torch.cumsum(a, -3)
    return a

def norm_3d(a):
    return a / torch.sum(a, dim=(-1,-2,-3), keepdim=True)

def emd_3d(a, b):
    a = norm_3d(a)
    b = norm_3d(b)
    return torch.mean(torch.square(cumsum_3d(a) - cumsum_3d(b)), dim=(-1,-2,-3))

This should also work with batched data. I would also try normalizing the images first (so they each sum to 1) unless you want to account for changes in intensity.

$\endgroup$
7
  • $\begingroup$ can this function be used within torch.cdist, to account for pairwise distances of every pair? $\endgroup$ Jul 5 at 12:11
  • $\begingroup$ It looks like torch.cdist only supports different values of p for the L_p distance. It doesn’t look like it supports applying a function to all pairs. Sounds like you want to make a kernel matrix? You could use something like pytorch.org/docs/stable/generated/torch.combinations.html and then stack the 0,1 elements from the tuples into two tensors, then run this? $\endgroup$ Jul 5 at 13:53
  • 1
    $\begingroup$ Or better you could flatten after doing the 3d cumsum in the example above. Then you could use cdist with p=2 to replace the subtract and square steps. You would give the function your list of per-sample flattened cumsum tensors (samples x flat) twice. Then that would be all pairwise distances with something kind of like an EMD. $\endgroup$ Jul 5 at 13:56
  • $\begingroup$ Wow, this has worked tremendously well. I highly appreciate your response. $\endgroup$ Jul 5 at 14:18
  • $\begingroup$ Nice! Glad I could help. $\endgroup$ Jul 5 at 14:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .