无偏（随机？）选择算法

Question

问题： 有X个属性，所有属性均为0到1之间的浮点数。
选择一个属性的成本是固定的C（与将其保留在0处相反）
属性的成本与其值成比例（无论是指数还是线性）。 如果给定预算B，我该如何进行不偏（随机？）的子集属性选择？

假设“成本”函数类似于以下内容：（指数版本）

cost = C*sgn(x) + ke^(ax)
0 <= x <= 1
Constants: C, k, a

我的第一个想法是某种优化问题，但实际上没有什么可以最大化/最小化的东西。我想你可以将其视为尽可能接近B的解决方案。然而这并不太合理，因为我不是在寻找“最佳”解决方案，任何足够接近B的解决方案都可以。

然后，我开始研究随机抽样，这似乎是最相似的问题。我发现了一些称为随机加权抽样的东西，看起来很有前途，但我不确定“预算”如何适应其中。

我不需要非常精确或保证独立的结果。也许我过于复杂化了？在这个阶段，我只是寻找一些可以在Java或类似语言中快速实现的简单方法。

编辑：我按照下面的建议，在math.stackexchange.com发布了问题here。我认为我在那里更清楚地表达了我想要实现的内容。

- moevi

---

问题对我来说不太清楚。您是希望随机选择时不考虑成本吗？那么只需进行随机洗牌，然后从第一个元素开始选择，直到您的预算范围内即可。 - ron

它应该考虑成本。基本上，我希望它选择一些具有不同“强度”的属性，从而在属性的强度之间（由于成本呈指数级增长）和属性数量之间（由于属性的恒定成本）创建平衡。选择可以包含一些强大的属性或许多弱的属性，或者介于两者之间的任何东西。希望这样说得清楚。 - moevi

将所有属性的成本相加，归一化到<0;1>，从<0;1>中获取一个随机数，选择该数字所在范围内的属性。如果已选择的属性成本小于预算，则重复此过程。 - MarianP

“fair”这个词汇的意思并不清晰，也不确定你是否有严谨的定义。能否详细说明一下？ - Tom Anderson

听起来像是背包问题。 - Rostislav Matl

Answer 1

在这里，您可以使用最大熵原理来指导。http://en.wikipedia.org/wiki/Principle_of_maximum_entropy。基本上，有一个巨大的X分配集合，其中一些（非常小的）子集将完全满足您的预算。您希望从该满足分配集合中均匀随机选择。

不幸的是，虽然这为我提供了一个清晰和有原则的思考问题的方向，但我实际上不知道如何有效地从该集合中进行抽样。

- Rob Neuhaus

Answer 2

MarianP的评论似乎有正确的方向。例如，如果您有3个权重分别为1、3和6的属性，则可以在脑海中将长度为1 + 3 + 6 = 10的线段分成三段：

+-+---+------+
|0|123|456789| 
+-+---+------+

然后使用范围为（0,9）的骰子掷骰子，并选择被骰子击中的部分（属性）。从集合中删除该属性，并使用已过滤出预算的新属性集进行递归处理。

这样可以更高概率地选择较长序列（较重的属性）。

- ron

---

那为什么应该被认为是“公平”的呢？ - 6502

@6502：您有什么疑虑吗？任务是根据它们的权重选择不同的元素。这是一种公平的选择方法。预算超支的元素应定期删除，因为即使它们被滚动到，也无法选择它们。 - ron

Answer 3

在这里，我尝试并开始使用一种效率低下的过程，满足随机性的一个视图，并用更有效的过程替换它。

1）低效 - 我假设您有一个属性列表及其相关成本。考虑所有可能的属性集 - 如果有N个属性，则将有2^N个这样的集合。从中考虑适合您预算的属性集的集合。从这个较小的（但可能仍然很大）集合中随机选择一组属性。

2）可能的实现。我假设成本都是中等大小的整数，或者您可以接受将它们舍入到此范围内所涉及的不准确性。现在，您可以建立一个数组A，其中A [i]是创建总成本为i的集合的方法数。考虑到0个属性，A [0] = 1。现在考虑成本为3的属性。目前A的唯一非零元素是A [0]。这给了您另一种生成A [0 + 3 = 3]的方法，因此您可以设置A [3] = 1 + A [0]。通过依次考虑每个属性，您可以设置A [i] =使用这些属性创建成本为i的集合的方法数。

一旦你构建了数组，考虑每个属性，从成本B开始。通过从成本>=B的费用中按比例采样创建一个费用为C的集合的方式数量来选择一个精确的费用C。现在依次考虑每个属性。给定一个成本为c的属性，如果它大于当前成本C，则丢弃它。如果不是，则考虑A[C]和A[C-c]，并以与它们的大小成比例的概率之间进行选择。如果你选择A[C]，你将丢弃该属性。如果你选择A[C-c]，则将该属性包含在随机集合中。

也许有一种不需要将其舍入为整数的等效方法，可以使用http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm - 也许我会坐下来考虑这个问题。

是的-这个从Metropolis-Hastings很容易得出。基本上，您可以从任何有效集合开始 - 如空集，运行大量Metropolis-Hastings步骤，并希望结果混合得足够好，以便所得到的集合根据您的分布几乎是随机的。如果您想要另一个随机样本，请再次运行它通过更多M-H步骤。

在Wikipedia条目的语言中，P（x'）= P（x_t）= 1。要计算Q（x_t；x'），您需要决定如何从一组移动到另一组。如果按成本排列属性，则可以计算出给定一组的总成本，您可以确定可以添加到其中的剩余属性数量-例如，进行二进制切割以计算便宜的资产数量，并使用某种平衡树来计算已选择的此类属性数量。因此，您可以计算出可以添加到当前集合中的不同属性数，当然您也可以减去任何现有属性。如果步骤是要添加或删除单个属性，则知道从x_t出发的不同方式有多少种，您还可以为x'执行类似的计算。因此，Q（x'; x_t）为1 /（从x_t出去的方法数），Q（x_t; x'）为1 /（从x'出去的方法数），一旦您决定是否移动，如果您决定移动，则会随机选择这些方法之一离开x_t。

- mcdowella