MATLAB / General CS：从多个集合中进行替换而无需替换（+跟踪未采样案例的情况）

[poster]

我目前正在实现一种优化算法，该算法需要我采样而不用从多个集合中进行替换。尽管我在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矩阵）。我意识到这可能是不可能的，尽管找到有效的方法可以证明算法的真正局限性。



回答：

您是否真的需要跟踪所有未抽样的案例？即使您有一个10×1的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); 2000年1月1日稀疏矩阵beenSampled是空的（即，它包含所有零），并且我们将为每个采样的排列在给定的索引处添加一个1。我们可以使用函数RANDI来获得新的样本排列，以为我们提供新值集的A ， B和C索引：

indexA = randi(nA); indexB = randi(nB); indexC = randi(nC); 然后，我们可以使用函数SUB2IND将这三个索引转换为单个唯一线性索引，并将其beenSampled为benSampled ：

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... 如果只打算对所有可能排列的一小部分进行采样，那么使用稀疏数组将为您节省大量空间。对于较小的排列总数，例如上面的示例，我可能只使用逻辑向量而不是稀疏向量。



更多&回答...