Answers.Body: <p>You could try an <a href="https://en.m.wikipedia.org/wiki/Earth_mover%27s_distance" rel="nofollow noreferrer">earth mover distance</a> in 2d  or 3d over the image? For example you could follow <a href="https://discuss.pytorch.org/t/implementation-of-squared-earth-movers-distance-loss-function-for-ordinal-scale/107927/2" rel="nofollow noreferrer">this</a> example, but call it sequentially. The idea would be something like the following (untested and written on my cell phone):</p>
  <pre><code>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))
  </code></pre>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-05T12:11:57.810Z
Answers.Text: can this function be used within torch.cdist, to account for pairwise distances of every pair?
Answers.UserDisplayName: Hadar Sharvit
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-05T13:53:40.510Z
Answers.Text: 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 https://pytorch.org/docs/stable/generated/torch.combinations.html and then stack the 0,1 elements from the tuples into two tensors, then run this?
Answers.UserDisplayName: John St. John
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-05T13:56:09.793Z
Answers.Text: 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.
Answers.UserDisplayName: John St. John
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-05T14:18:22.820Z
Answers.Text: Wow, this has worked tremendously well. I highly appreciate your response.
Answers.UserDisplayName: Hadar Sharvit
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-05T14:27:57.310Z
Answers.Text: Nice! Glad I could help.
Answers.UserDisplayName: John St. John
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-05T15:30:30.593Z
Answers.Text: You could do the same process using torch.cdist and the embedding output (before classification layer) of a ResNET or whatever pretrained/frozen image model. You might want to divide each embedded vector by its norm first though so you have a cosine similarity rather than a pure l2 if you do that though. Embeddings from a good image model should be better than emd, but I bet emd is a pretty good baseline.
Answers.UserDisplayName: John St. John
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-04T20:41:35.980Z
Answers.LastActivityDate: 2023-05-24T20:13:13.543Z
Answers.LastEditDate: 2023-05-24T20:13:13.543Z
Answers.UserDisplayName: John St. John
Body: <p><strong>TLDR</strong>: given two tensors <span class="math-container">$t_1$</span> and <span class="math-container">$t_2$</span>, both with shape <span class="math-container">$(c,h,w),$</span> how shall the distance between them be measured?</p>
  <hr />
  <p><strong>More Info</strong>: I'm working on a project in which I'm trying to distinguish between an anomalous sample (specifically from <code>MNIST</code>) and a &quot;regular&quot; sample (specifically from <code>CIFAR10</code>). The solution I chose is to consider the feature maps that are given by <code>ResNet</code> and use <em>kNN</em>. More specifically:</p>
  <ul>
  <li>I embed the entire <code>CIFAR10_TRAIN</code> data to achieve a dataset that consists of activations with dimension <span class="math-container">$(N,c,h,w)$</span> where <span class="math-container">$N$</span> is the size of <code>CIFAR_TRAIN</code></li>
  <li>I embed <span class="math-container">$2$</span> new test samples <span class="math-container">$t_C$</span> and <span class="math-container">$t_M$</span> from <code>CIFAR10_TEST</code> and <code>MNIST_TEST</code> respectively (both with shape <span class="math-container">$(c,h,w)$</span>), same as I did with the training data.</li>
  <li>(<strong>!</strong>) I find the <em>k-Nearest-Neighbours</em> of <span class="math-container">$t_C$</span> and <span class="math-container">$t_M$</span> w.r.t the embedding of the training data</li>
  <li>I calculate the mean distance between the <span class="math-container">$k$</span> neighbors</li>
  <li>Given some predefined threshold, I classify <span class="math-container">$t_C$</span> and <span class="math-container">$t_M$</span> as regular or anomalous, hoping that the distance for <span class="math-container">$t_M$</span> would be higher, as it represents O.O.D sample.</li>
  </ul>
  <p>Notice that in (<strong>!</strong>) I need some distance measure, but this is not trivial as these are tensors, not vectors.</p>
  <hr />
  <p><strong>What I've Tried</strong>: a trivial solution is to flatten the tensor to have shape <span class="math-container">$(c\cdot h\cdot w)$</span> and then use basic <span class="math-container">$\ell_2$</span>, but the results turned out pretty bad. (could not distinguish regular vs anomalous in this case). Hence: <em>Is there a better way of measuring this distance</em>?</p>
  
Tags: <features><feature-extraction><metric><anomaly-detection><tensor>
Title: How to calculate a meaningful distance between multidimensional tensors
UserDisplayName: Hadar Sharvit
ThreadText: # How to calculate a meaningful distance between multidimensional tensors
  
  (Asked by: username_0 on 2022-07-04)
  
  **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*?
  
  **Tags:** features, feature-extraction, metric, anomaly-detection, tensor
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-07-04. Score: 2 | Accepted answer
  
  You could try an earth mover distance in 2d  or 3d over the image? For example you could follow this example, but call it sequentially. The idea would be something like the following (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.
  
  > **Comments:**
  > **username_0**: can this function be used within torch.cdist, to account for pairwise distances of every pair?  
  > **username_1**: 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 https://pytorch.org/docs/stable/generated/torch.combinations.html and then stack the 0,1 elements from the tuples into two tensors, then run this?  
  > **username_1**: 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.  
  > **username_0**: Wow, this has worked tremendously well. I highly appreciate your response.  
  > **username_1**: Nice! Glad I could help.  
  > **username_1**: You could do the same process using torch.cdist and the embedding output (before classification layer) of a ResNET or whatever pretrained/frozen image model. You might want to divide each embedded vector by its norm first though so you have a cosine similarity rather than a pure l2 if you do that though. Embeddings from a good image model should be better than emd, but I bet emd is a pretty good baseline.  
  
  ---
  
  