在Python中什么是高维体积估计的好实现？

Question

我想在Python中估计一个高维形状的体积。我有一个甲骨文，用来询问我是否在形状内。我处于高维（至少32*32=1024维）。理想情况下，我不想亲自实施，因为：

1. 似乎技术性很强，论文范围在https://arxiv.org/pdf/1401.0120.pdf之间，而且似乎非专家很容易出错
2. 这似乎是一个标准的数学问题（在高维中估计体积），因此假设一个比我在python中所能破解的代码更好的优化代码似乎是明智的。在

有人知道什么是解决这个问题的好方法吗？我是否应该着手实施我在论文中提到的那个？在

---

不确定数学技术约束是什么，但是：

1. 我可以访问一个预言，它说+1或-1，这取决于我是否在形状内部。在
2. 我想估计凸形的形状

现在我只是想尝试一种类似于：

1. 决定一个真正的出价球，最有可能包含我想估计的形状
2. 采样多个点（很高兴知道需要采样多少个对我的形状有一个很好的估计）

然而，由于这似乎是一个微妙的技术领域，如果可以避免的话，我宁愿不要太老套（尤其是如果我能从理论上保证样品的质量）

---

发布问题前的相关链接：

• https://www.quora.com/unanswered/What-are-the-fastest-algorithms-to-implement-in-practice-that-estimate-high-dimensional-volumes
• https://arxiv.org/pdf/1401.0120.pdf
• https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html
• https://cstheory.stackexchange.com/questions/9573/computing-volume-of-high-dimensional-convex-polyhedra
• http://www.qhull.org/

Answer 1

这就是你的问题的答案：你需要多少个样本点来估计某个高维区域的体积。在

假设集合K包含在某个封闭集合B中，该集合B的体积已知为1，且不损失一般性。用V表示K的未知体积。让f（x）表示K的指示函数：如果x在K中，则f（x）=1；如果x不在K中，则f（x）=0。（抱歉，stackoverflow上没有乳胶）。在

显然，V正是期望值E[f（x）]，这也是概率p[f（x）=1]，其中随机变量x在B中均匀地随机抽取。此外，方差var（f（x））正好是V（1-V），它在0和0.25之间有界。在

对于x₁，…，x_n在B中均匀独立地绘制，考虑S_n=（f（x₁）+。。。+中心极限定理认为S_n是渐近正态分布n（V，var（f（x））/n，因此S_n的标准差为sqrt（V（1-V）/n）。因此，如果您希望绝对精度ε（即| S_n-V |≤ε），概率p=0.99999998027（即6个标准差），则应取n=36V（1-V）/ε²。在

特别是当V很小时，你需要一个相对公差，即ε=δV。然后，你需要n=36（1-V）/（Vδ²）。在

你在这里看到的问题是，当V很小的情况下，很难获得精确的精度，但造成这种情况的原因是维数的诅咒，它粗略地说，在维度d中，V很可能是O（10^-d）

例如，如果K是在边1的立方体B内接的半径为1/2的球体，那么V大约是（πe/（2d））^d/2/sqrt（dπ），如果你想要一个小于100%的相对误差，那么你只需要n=O（d^d/2）的样本。在