来自张量的随机索引（从张量进行替换采样）

Question

我正在尝试操纵不同神经网络的各个权重以查看它们的性能如何下降。作为这些实验的一部分，我需要从它们的权重张量中进行运行domly 采样，我将其理解为有放回采样（在统计意义上）。然而，由于它是高维的，我一直对如何以公平的方式做到这一点感到困惑。以下是我考虑这个问题的方法和研究：

这之前是通过 selecting 一个运行dom 层然后 selecting 一个运行dom 权重在该层中实现的（忽略选择运行dom 权重的实现）。由于层大小不同，我们发现权重采样不均匀。
我考虑如果按照张量的numpy.shape采样会怎么样；但是，我现在意识到这遇到了与上述相同的问题。

考虑像这样的运行k 2 张量会发生什么：
```
[[*, *, *],
 [*, *, *, *]]
```
选择一行运行domly 然后从该行中选择一个值会导致不公平的 selection。如果您能够断言这种情况永远不会发生，则此方法可能会起作用，但它远非通用解决方案。

请注意实际上是以这种方式实现的。
我发现有人建议展平张量并使用 numpy.random.choice 到 select 运行domly 来自一维数组。这是一个简单的解决方案，除了我不知道如何将展平的张量反转回其原始形状。此外，扁平化数百万个权重将是一个有点慢的实现。
我发现有人在讨论tf.random.multinomial ，但我不太了解它是否适用。
我运行进入 this paper about resevoir sampling，但又一次，它超出了我的理解范围。
我发现 another paper 专门讨论张量和采样技术，但它更让我头疼。
一个队友发现 this other paper 谈到运行dom 从张量采样，但它只适用于运行k 3 个张量。

对了解如何执行此操作有帮助吗？我在 Python 与 Keras 一起工作，但我会采用任何存在形式的算法。提前谢谢你。

Answer 1

在我忘记记录我们得出的解决方案之前，我将谈谈我看到的实现此解决方案的两种不同途径：

对张量的标量元素使用 total ordering。这有效地枚举了您的元素，即展平它们。但是，您可以在保持原始形状的同时执行此操作。考虑这个伪代码（在 Python-like 语法中）：
```
def sample_tensor(tensor, chosen_index: int) -> Tuple[int]:
    """Maps a chosen random number to its index in the given tensor.

    Args:
        tensor: A ragged-array n-tensor.
        chosen_index: An integer in [0, num_scalar_elements_in_tensor).
    Returns:
        The index that accesses this element in the tensor.

    NOTE: Entirely untested, expect it to be fundamentally flawed.
    """
    remaining = chosen_index
    for (i, sub_list) in enumerate(tensor):
        if type(sub_list) is an iterable:
            if |sub_list| > remaining:
                remaining -= |sub_list|
            else:
                return i joined with sample_tensor(sub_list, remaining)
        else: 
            if len(sub_list) <= remaining:
                return tuple(remaining)
```
首先，我知道这不是一个可靠的算法。这个想法是倒计时，直到你到达你的元素，并为索引簿记。

我们需要在这里做出重要的假设。 1) 所有列表最终将只包含标量。 2) 直接后果是，如果列表包含列表，则假定它也不包含同一级别的标量。（停下来说服自己接受（2）。）

我们也需要在这里做一个重要的说明：我们无法测量任何给定列表中标量的数量，除非该列表由标量均匀组成。为了避免在每个点都测量这个幅度，我上面的算法应该重构为先下降，然后减去。

这个算法有一些后果：
- 它是最快解决问题的整个风格。如果你想写一个函数 f: [0, total_elems) -> Tuple[int]，你 必须知道 在张量的总排序中前面的标量元素的数量。这在 Theta(l) 处有效绑定，其中 l 是张量中列表的数量（因为我们可以在标量列表上调用 len）。
- 慢。与采样具有定义形状的更好的张量相比，太慢。
这引出了一个问题：我们能做得更好吗？看下一个解决方案。
使用一个probability distribution in conjunction with numpy.random.choice。这里的想法是，如果我们提前知道标量的分布已经是什么样子，我们就可以在张量下降的每个级别上公平地采样。这里的难题是构建这个发行版。

我不会为此编写伪代码，但会列出一些目标：
- 这只能调用一次来构建数据结构。
- 该算法需要结合迭代和递归技术来分别 a) 为兄弟列表构建分布和 b) 为后代构建分布。
- 该算法需要将索引映射到对应于兄弟列表的概率分布（请注意上面讨论的假设）。 确实需要知道任意sub-tensor中的元素数量。
- 在列表仅包含标量的较低级别，我们可以通过仅存储所述列表中的元素数量来简化（而不是存储从一维数组中随机选择标量的概率）。
- 您可能需要 2-3 个函数：一个将概率分布用于 return 索引的函数，一个构建分布对象的函数，可能还有一个仅计算元素以帮助构建分布的函数.
这在 O(n) 处也更快，其中 n 是张量的等级。我确信这是最快的算法，但我没有时间尝试证明它。

您可以选择将分布存储为有序字典，将概率映射到另一个字典或一维数组中的元素数。我认为这可能是最明智的结构。

注意 (2) 实际上与 (1) 相同，但我们 pre-compute 了解张量的密度。

希望对您有所帮助。

来自张量的随机索引（从张量进行替换采样）

Random Index from a Tensor (Sampling with Replacement from a Tensor)

random

python-3.x

keras

tensor