黑盒函數的探索

06-01

黑盒函數的探索

來自專欄數學人生

黑盒函數的定義

在工程上和實際場景中，黑盒函數（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{-bpmsqrt{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 步直到達到最大迭代次數或者最理想的精度為止。

牛頓法（Newtons 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 ightarrow 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},0leq ileq n}$ 這 $n+1$ 個樣本。根據 Weierstrass 逼近定理可以知道：

閉區間上的連續函數可以用多項式級數一致逼近；
閉區間上的周期為 $2pi$ 的連續函數可以用三角函數級數一致逼近。

用數學符號來描述就是：

[Weierstrass 逼近定理] 假設 $f(x)$ 是閉區間 $[a,b]$ 連續的實函數。對於任意的 $epsilon>0,$ 存在一個多項式 $p(x)$ 使得對於任意的 $xin[a,b],$ 有 $|f(x)-p(x)|<epsilon.$

因此，如果要計算黑盒函數的最大值和最小值，可以使用一個多項式去擬合這 $n+1$ 個點，於是計算這個多項式的最大值與最小值即可。

Lagrange 插值公式

按照之前的符號，如果我們擁有 $n+1$ 個樣本 ${(x_{i},y_{i}), 0leq ileq n},$ 那麼我們可以找到一個多項式 $p(x)$ 使得 $p(x_{i}) = y_{i}$ 對每一個 $0leq ileq n$ 都成立。根據計算，可以得到該多項式是：

$p(x) = sum_{i=0}^{n}igg(prod_{0leq jleq n, j eq i}frac{x-x_{j}}{x_{i}-x_{j}}igg)y_{i}.$

於是，要計算黑盒函數的最大值與最小值，就可以轉化成計算 $p(x)$ 的最大值與最小值。

除了數學方法之外，機器學習中有一種演算法叫做啟發式優化演算法，也是用來計算黑盒函數的最大值和最小值的，例如粒子群演算法與模擬退火演算法等。

粒子群演算法（Particle Swarm Optimization）

PSO 最初是為了模擬鳥群等動物的群體運動而形成的一種優化演算法。PSO 演算法是假設有一個粒子群，根據群體粒子和單個粒子的最優效果，來調整每一個粒子的下一步行動方向。假設粒子的個數是 $N_{p},$ 每一個粒子 $old{x}_{i}in mathbb{R}^{n}$ 都是 $n$ 維歐幾里德空間裡面的點，同時需要假設粒子的速度 $old{v}_{i}inmathbb{R}^{n}.$ 在每一輪迭代中，需要更新兩個最值，分別是每一個粒子在歷史上的最優值和所有粒子在歷史上的最優值，分別記為 $old{x}_{i}^{*}$ （ $1leq i leq N_{p}$ ）和 $old{x}^{g}.$ 在第 $t+1$ 次迭代的時候，