1

我目前正在实施一种优化算法，该算法需要我从几组中进行采样而不进行替换。虽然我在 MATLAB 中编码，但这本质上是一个 CS 问题。

情况如下：

我有有限数量的集合（A，B，C），每个集合都有有限但可能不同数量的元素（a1,a2...a8，b1,b2...b10，c1, c2...c25）。我还有每个集合的概率向量，其中列出了该集合中每个元素的概率（即对于集合A， P_A = [p_a1 p_a2... p_a8] 其中 sum(P_A) = 1）。我通常使用这些为每个集合创建一个概率生成函数，给定一个介于 0 到 1 之间的统一数字，可以从该集合中吐出一个元素（即函数 P_A(u)，给定 u = 0.25，将选择a2 )。

我希望从集合A、B和C中进行抽样而不进行替换。每个“完整样本”是来自每个不同集合的元素序列，即 ( a1, b3, c2 )。请注意，完整样本的空间是A、B和C中元素的所有排列的集合。在上面的例子中，这个空间是 ( a1,a2...a8 ) x ( b1,b2...b10 ) x ( c1, c2...c25 ) 并且有 8*10*25 = 2000 个唯一的“完整样品”在我的空间。

不替换此设置进行采样的烦人部分是，如果我的第一个样本是 ( a1, b3, c2 )，那么这并不意味着我不能再次对元素a1进行采样- 这只是意味着我无法对完整序列进行采样 ( a1, b3, c2 ) 再次。另一个烦人的部分是我正在使用的算法要求我对我没有采样的元素的所有排列进行函数评估。

我现在可以使用的最好方法是跟踪抽样案例。这有点低效，因为我的采样器被迫拒绝之前采样过的任何案例（因为我在没有更换的情况下进行采样）。然后，我对未采样的情况进行函数评估，方法是使用嵌套的 for 循环遍历每个排列（ax, by, cz ），并且仅在（ ax, by, cz）的组合不包含在采样中时才进行函数评估案例。同样，这有点低效，因为我必须“检查”每个排列（ax, by, cz）是否已经被采样。

我将不胜感激有关此问题的任何建议。特别是，我正在寻找一种无需替换即可采样并跟踪未明确列出完整样本空间的未抽样案例的方法（我通常使用 10 个集合，每个集合包含 10 个元素，因此列出完整样本空间需要 10 ^10 x 10 矩阵）。我意识到这可能是不可能的，尽管找到有效的方法可以让我证明算法的真正局限性。

4

2 回答 2

2

您真的需要跟踪所有未抽样的案例吗？即使您有一个 1×10 10向量，该向量存储了一个逻辑值true 或 false，指示该排列是否已被采样，这仍然需要大约 10 GB 的存储空间，并且 MATLAB 可能会抛出“如果您尝试创建该大小的变量，则会出现内存不足”错误或使您的整个机器急速停止。

要考虑的替代方法是为您已经采样的排列存储一个稀疏的指标向量。让我们考虑一下您的较小示例：

A = 1:8;
B = 1:10;
C = 1:25;
nA = numel(A);
nB = numel(B);
nC = numel(C);
beenSampled = sparse(1,nA*nB*nC);

1×2000 稀疏矩阵beenSampled一开始是空的（即它包含全零），我们将在给定索引处为每个采样排列添加一个。我们可以使用函数RANDI获得一个新的样本排列，为我们提供A、B和C新值集的索引：

indexA = randi(nA);
indexB = randi(nB);
indexC = randi(nC);

beenSampled然后我们可以使用函数SUB2IND将这三个索引转换为一个唯一的线性索引：

index = sub2ind([nA nB nC],indexA,indexB,indexC);

现在我们可以测试索引元素，beenSampled看看它的值是 1（即我们已经对其进行了采样）还是 0（即它是一个新样本）。如果它已经被采样，我们重复上面找到一组新索引的过程。一旦我们有了一个尚未采样的排列，我们就可以对其进行处理：

while beenSampled(index)
  indexA = randi(nA);
  indexB = randi(nB);
  indexC = randi(nC);
  index = sub2ind([nA nB nC],indexA,indexB,indexC);
end
beenSampled(index) = 1;
newSample = [A(indexA) B(indexB) C(indexC)];
%# ...do your subsequent processing...

如果您最终只对所有可能排列的一小部分进行采样，则使用稀疏数组将为您节省大量空间。对于较小的排列总数，例如上面的示例，我可能只使用逻辑向量而不是稀疏向量。

于 2011-03-16T20:40:31.357 回答
0

检查randi函数的matlab文档；您只想将它​​与length从每个向量中选择随机条目的函数结合使用。跟踪每个采样向量应该像将其连接到矩阵一样简单；

current_values = [5 89 45];  % lets say this is your current sample set
used_values = [used_values; current_values];
% wash, rinse, repeat
于 2011-03-16T18:50:16.893 回答