黑盒函数的探索

黑盒函数的定义

在工程上和实际场景中，黑盒函数（black box function）指的是只知道输入和输出对应关系，而不知道它的内部结构，同时也不能写出具体表达式的一类函数。正如下图所示，每次给定一组输入，通过黑盒函数的计算，都能够得到一组输出的值，但是却无法写出 Black box 函数的精确表达式。

与之相反的是函数或者系统称之为白盒函数（open system），它不仅能够根据具体的输入获得相应的输出，还能够知道该函数的具体表达式和细节描述。例如 $f(x) = \sin(x)$ 和 $f(x) = \ln(x)$ 等都是白盒函数。

黑盒函数的研究对象

无论是白盒函数还是黑盒函数，都有很多的学术界人士和工业界人士去研究。通常来说，对于一个函数 $f(x)$ 而言，我们都可以研究该函数的以下性质：

最大值与最小值，i.e. $\max f(x)$ 和 $\min f(x).$
根，i.e. $\{x:f(x) = 0\}.$
函数的单调性与凹凸性等。

对于具有明显表达式的函数，例如 $f(x) = \sin(x)$ 等，我们能够使用的方法和技巧都很多，其方法包括但不限于导数，积分，Taylor 级数等等。但是对于黑盒函数，我们能够使用的方法和技巧就会一定的限制。本文将从如何研究一个函数的根，最大值和最小值等方向入手，逐步向大家展示黑盒函数研究中所遇到的数学与机器学习方法。

黑盒函数的根

对于多项式 $p(x) = a_{n}x^{n}+\cdots + a_{0}$ 而言，多项式的根指的是使得 $p(x)=0$ 的 $x$ 的解。特别的，对于二次多项式而言，也就是 $ax^{2} +bx+c=0,$ 它的根可以表示为：

$x = \frac{-b\pm\sqrt{b^{2}-4ac}}{2a}.$

对于一般函数 $f(x)$ 而言，它的根指的是 $\{x:f(x)=0\}$ 这个集合。下面我们来介绍一下如何计算一个函数的根。

二分法

在数学分析中，介值定理（Intermediate value theorem）描述了连续函数在两点之间的连续性，具体描述是：

[介值定理] 如果连续函数 $f(x)$ 的定义域包含 $[a,b],$ 而且通过 $(a,f(a))$ 与 $(b,f(b))$ 两点，它也必定通过区间 $[a,b]$ 内的任意一点 $(c,f(c)),$ 其中 $a<c<b.$

从介值定理可以得到，如果我们知道 $f(x_{1})<0$ 和 $f(x_{2})>0,$ 那么必定存在 $x_{0} \in (x_{1},x_{2})$ 使得 $f(x_{0})=0.$ 根据这个定理，我们可以提出二分法来计算函数的根。

如果要计算 $f(x) = 0$ 的解，其一般步骤是：

先找到一个区间 $[a,b],$ 使得 $f(a)f(b)<0;$
求这个区间的中点 $m=(a+b)/2,$ 并求出 $f(m)$ 的取值；
如果 $f(m)=0,$ 那么 $m$ 就是函数的根；如果 $f(m)f(a)>0,$ 就选择 $[m,b]$ 为新的区间，否则选择 $[a,m]$ 为新的区间；
重复第 2 步和第 3 步直到达到最大迭代次数或者最理想的精度为止。

牛顿法（Newton’s Method）

牛顿法的大致思想是：选择一个接近 $f(x)$ 零点的初始点 $x_{0},$ 计算这个点相应的函数取值 $f(x_{0})$ 与导数值 $f'(x_{0}),$ 然后写出通过点 $(x_{0},f(x_{0}))$ 的切线方程，并且计算出该切线与横轴的交点 $x_{1}.$ i.e.

$x_{1} = x_{0} - f(x_{0})/f'(x_{0}).$

我们可以不停地重复以上过程，就得到一个递推公式：

$x_{n+1}= x_{n}-f(x_{n})/f'(x_{n}).$

在一定的条件下，牛顿法必定收敛。也就是说 $x_{n}$ 随着 $n$ 趋近于无穷，将会趋近于 $f(x)=0$ 的解。

割线法

根据导数的定义：

$f'(x_{0}) = \lim_{x\rightarrow x_{0}}\frac{f(x)-f(x_{0})}{x-x_{0}}$

可以得到，当 $x$ 靠近 $x_{0}$ 的时候，可以用右侧的式子来估计导数值，i.e.

$f'(x_{0}) \approx \frac{f(x)-f(x_{0})}{x-x_{0}}.$

当我们不能够计算 $f(x)$ 的导数的时候，就可以用上式来代替。

于是，割线法与牛顿法的迭代公式非常相似，写出来就是：

$x_{n+1} = x_{n} - \frac{x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}f(x_{n}).$

在这里，割线法需要两个初始值 $x_{0}$ 与 $x_{1},$ 并且它们距离函数 $f(x)=0$ 的根越近越好。

备注

对于黑盒函数而言，我们是不知道它们的表达式的，因此以上的方法和技巧在黑盒函数的使用上就有限制。例如牛顿法是需要计算函数的导数值的，因此不适用在这个场景下。但是对于二分法与割线法，只需要计算函数在某个点的取值即可，因此可以用来寻找黑盒函数的根。

黑盒函数的最大值与最小值

对于能够写出表达式的函数而言，如果要寻找 $f(x)$ 的最大值与最小值，可以计算 $f(x)$ 的导数 $f'(x),$ 然后令 $f'(x) =0,$ 就可以得到函数的临界点（critical point），再根据周围的点导数的性质即可判断这个点是否是局部最大值或者局部最小值。

Weierstrass 逼近定理

对于黑盒函数而言，通常来说我们只知道一组输入和相应的输出值。如果只考虑一维的情况而言，那就是 $\{(x_{i},y_{i})\in \mathbb{R}^{2},0\leq i\leq n\}$ 这 $n+1$ 个样本。根据 Weierstrass 逼近定理可以知道：

闭区间上的连续函数可以用多项式级数一致逼近；
闭区间上的周期为 $2\pi$ 的连续函数可以用三角函数级数一致逼近。

用数学符号来描述就是：

[Weierstrass 逼近定理] 假设 $f(x)$ 是闭区间 $[a,b]$ 连续的实函数。对于任意的 $\epsilon>0,$ 存在一个多项式 $p(x)$ 使得对于任意的 $x\in[a,b],$ 有 $|f(x)-p(x)|<\epsilon.$

因此，如果要计算黑盒函数的最大值和最小值，可以使用一个多项式去拟合这 $n+1$ 个点，于是计算这个多项式的最大值与最小值即可。

Lagrange 插值公式

按照之前的符号，如果我们拥有 $n+1$ 个样本 $\{(x_{i},y_{i}), 0\leq i\leq n\},$ 那么我们可以找到一个多项式 $p(x)$ 使得 $p(x_{i}) = y_{i}$ 对每一个 $0\leq i\leq n$ 都成立。根据计算，可以得到该多项式是：

$p(x) = \sum_{i=0}^{n}\bigg(\prod_{0\leq j\leq n, j\neq i}\frac{x-x_{j}}{x_{i}-x_{j}}\bigg)y_{i}.$

于是，要计算黑盒函数的最大值与最小值，就可以转化成计算 $p(x)$ 的最大值与最小值。

除了数学方法之外，机器学习中有一种算法叫做启发式优化算法，也是用来计算黑盒函数的最大值和最小值的，例如粒子群算法与模拟退火算法等。

粒子群算法（Particle Swarm Optimization）

PSO 最初是为了模拟鸟群等动物的群体运动而形成的一种优化算法。PSO 算法是假设有一个粒子群，根据群体粒子和单个粒子的最优效果，来调整每一个粒子的下一步行动方向。假设粒子的个数是 $N_{p},$ 每一个粒子 $\bold{x}_{i}\in \mathbb{R}^{n}$ 都是 $n$ 维欧几里德空间里面的点，同时需要假设粒子的速度 $\bold{v}_{i}\in\mathbb{R}^{n}.$ 在每一轮迭代中，需要更新两个最值，分别是每一个粒子在历史上的最优值和所有粒子在历史上的最优值，分别记为 $\bold{x}_{i}^{*}$ （ $1\leq i \leq N_{p}$ ）和 $\bold{x}^{g}.$ 在第 $t+1$ 次迭代的时候，