生成(伪)随机高维函数的算法

Question

我不是指生成随机数的函数，而是生成 随机函数的算法

“高维数”是指函数是多变量的，例如一个100-dim函数有100个不同的变量。

假设区域是0,1，我们需要生成一个函数f:0,1^n->0,1。这个函数是从某一类函数中选择的，所以选择这些函数的概率是相同的。(这类函数可以是所有连续的，也可以是K阶导数，以便于算法实现。)

由于闭区间域上的函数是不可数无限的，所以我们只要求算法是伪随机的。

有多项式时间算法来解决这个问题吗？

我只想给这个问题添加一个可能的算法(但由于它的指数时间复杂性而不可行)。这个算法是由第一个提出这个问题的朋友提出的：

该算法可以简单地描述如下。首先，假设维数d=1。考虑区间i= a；b上的光滑函数。首先，我们将域a；b划分为N个小区间。对于每个区间Ii，我们生成一个随机数fi，它生活在某些特定分布(高斯分布或均匀分布)中。最后，我们做了级数( ai；fi)的插值，其中ai是Ii的一个特征点(例如，我们可以选择ai作为Ii的中间点)。插值后得到一条光滑曲线，它可以看作是生活在函数空间Cma；b中的一维随机函数构造。

这仅仅是说算法不需要那么正式和严格，而只是提供一些有用的东西。

Answer 1

所以，如果我做得对，你需要函数从向量返回标量；

我看到的最简单的方法是使用点积

• 例如，让n成为您需要的维度
• 因此，创建包含范围内的随机系数的随机向量a[n]，<0,1>
• 所有系数之和为1

1. create `float a[n]`
2. feed it with positive random numbers (no zeros)
3. compute the sum of `a[i]`
4. divide `a[n]` by this sum

​

• 现在，函数y=f(x[n])很简单
• y=dot(a[n],x[n])=a[0]*x[0]+a[1]*x[1]+...+a[n-1]*x[n-1]
• 如果我没有遗漏一些东西，目标范围应该是<0,1>
• 如果x==(0,0,0,..0)那么y=0;
• 如果x==(1,1,1,..1)那么y=1;

如果您需要更复杂的东西，请使用高次多项式

• 有点像y=dot(a0[n],x[n])*dot(a1[n],x[n]^2)*dot(a2[n],x[n]^3)...
• 其中x[n]^2的意思是(x[0]*x[0],x[1]*x[1],...)

Booth方法使函数具有相同的“方向”

• 如果任何x[i]上升，那么y也会上升
• 如果您想要更改该值，则必须允许a[]的负值。
• 但是，要使这一工作，您需要添加一些抵消y从负值.
• 而a[]规范化过程将更加复杂一些。
• 因为你需要寻找最小，最大的值.
• 更简单的选项是添加随机标志向量m[n]来处理
• 如果应该使用m[i]而不是x[i]，则将标记1-x[i]
• 这样上面的一切都会保持原样..。
• 您可以创建更多类型的映射，使其更易实现。

Answer 2

如果你真的想要生成每一个连续的函数，这不仅很难，而且是不可能的。

对于一维情况，您可以通过查看系统 (也参见维基)来创建一个有用的近似。这给出了一个区间上连续函数的Schauder基.这类基只覆盖整个向量空间，如果包含基向量的无限线性组合。因此，你可以通过在此基础上建立随机线性组合来创建一些随机函数，但一般来说，你不能以这种方式创建由无限数量的基向量表示的函数。

编辑以响应您的更新：

似乎选择一个K阶的随机多项式函数(对于K次可微函数类)对您来说就足够了，因为这些函数中的任何一个都可以(围绕给定的点)被其中之一近似(参见泰勒定理)。选择一个随机多项式函数很容易，因为你可以选择K随机实数作为你的多项式的系数。(注意，这将不返回类似abs(X)的函数)