当你拥有一大堆输入/输出对时,你如何找到函数的定义？

Question

假设您获得了输入/输出对的列表:

f 0 = 0
f 1 = 2
f 2 = 1
f 3 = -1
f 4 = 0
f 5 = 0
f 6 = -76
f 7 = -3
f 8 = 3
f 9 = -1
f 10 = -1
f 11 = -6
f 12 = -1
f 13 = -1
f 14 = 4
f 15 = -2
f 16 = -10
f 17 = 0
f 18 = 0
f 19 = -1
f 20 = 2
f 21 = 3
f 22 = 0
f 23 = 4
f 24 = 2
f 25 = -1
f 26 = 0
f 27 = 0
f 28 = -4
f 29 = -2
f 30 = -14

现在假设您被要求找到f使用适当的小数学公式而不是枚举值的定义.也就是说,答案应该是f x = floor(tan(x*x-3))(或类似的),因为这是一个对每个输入都是正确的小公式.你会怎么做？

Answer 1

所以让我们简化吧.你想要一个这样的功能

f 1 = 10
f 2 = 3
f 3 = 8

存在用于立即找到满足这些要求的多项式函数的公式.特别是

f x = 6 * x * x - 25 * x + 29

作品.事实证明,如果你有任何功能的图表

{ (x_1, y_1), (x_2, y_2), ..., (x_i, y_i) }

您可以立即构建一个与这些输入和输出完全匹配的多项式.

所以,鉴于存在这样的多项式,你永远不会解决你的问题(找到一个特定的解决方案floor(tan(x*x-3))),而不会强制执行更多约束.特别是,如果你不以某种方式取缔或惩罚多项式,那么我总是会把它们交给你.

一般而言,您想要做的是(a)定义搜索空间和(b)定义适应度量,也称为损失函数.如果您的搜索空间有限,那么您可以立即获得一个解决方案:根据您的损失函数对搜索空间的每个元素进行排名,并从最佳解决方案中随机选择.

你所要求的听起来要困难得多 - 如果你正在寻找所有可能程序的空间,那么这个空间是难以置信的大.除非我们严重限制自己或接受近似,否则无法全面搜索它是不可能的.其次,我们必须非常了解您的损失函数以及它与搜索空间的交互方式,因为我们希望通过这个广阔的空间进行智能猜测.

你提到了遗传算法 - 他们经常为这种工作而受到称赞,事实上它们可以成为一种在具有不确定损失函数的大空间中进行搜索的方法,但它们也会在成功时失败.真正熟练使用遗传算法来解决问题的人将花费他们所有的时间来设计搜索空间和损失函数,以将算法指向有意义的答案.

如果你小心的话,这可以用于一般程序.事实上,这是去年ICFP编程竞赛的主题.特别是,在此页面上搜索"2013年ICFP竞赛规则"以查看设置.