黑盒优化简介

luxifa

1、几种优化问题的例子

1.1 线性回归的最小二乘解

给定数据集 D={(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\cdots,(\mathbf{x}_m,y_m)} ,其中 \mathbf{x}_i =(x_{i1};x_{i2};,\cdots,x_{id}),y_i \in \mathbb{R}. “线性回归”试图学得一个线性模型以尽可能准确地预测实值输出标记，即线性回归试图学的如下的线性函数
\begin{equation*} f(\mathbf{x}_i=\boldsymbol{\omega}^T\mathbf{x}_i + b), \end{equation*}\\  
使得 f(\mathbf{x}_i）\simeq y_i .我们记 \hat{\boldsymbol{\omega}}=(\boldsymbol{\omega};b) ,相应的，把数据集 D 表示为一个 m\times(d+1) 大小的矩阵 \mathbf{X} ,其中每行对应于一个样本，该行的前 d 个元素对应于样本的 d 个属性值，每个样本的最后一个属性横置为1，然后把标记也写为向量形式 \mathbf{y}=(y_1;y_2;\cdots;y_m) .若矩阵 \mathbf{X}^T\mathbf{X} 为满秩矩阵或正定矩阵，令 \hat{\mathbf{x}}_i=(\mathbf{x}_i,1) 则我们可以求出线性回归问题的解析表达式如下所示:
\begin{equation*} f(\hat{\mathbf{x}}_i) = \hat{\mathbf{x}}(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}. \end{equation*}\\  
可以看出对于简单的线性回归问题，我们可以求出其最优解的解析表达式.能求出一个优化问题最优解的解析表达式意味着一方面我们在全局范围内找到了这一优化问题的全局最优解，另一方面我们可以避开迭代算法等计算代价相对庞大的近似求解算法(在这里只考虑最简单的线性回归问题，不考虑矩阵不可逆的情形，也不考虑矩阵求逆的计算量).
1.2 反向传播与梯度算法

线性模型，例如线性回归和逻辑回归，由于其能够求出其解析解或者使用凸优化算法进行迭代找到最优解，因此在很多问题上得到了广泛的应用.然而，线性模型也有很致命的缺陷，那就是模型的表达能力被限制的线性函数里，所以其无法拟合输入和输出之间的非线性映射关系.可以通过将线性模型作用在输入属性的一个非线性变换后的结果 \phi(\mathbf{x}) 上或者通过核方法、手工构造的方法以及深度神经网络的方法来构造隐含的非线性映射.
神经网络函数与线性模型的一个重要区别在于其非线性结构使得多数我们感兴趣的代价函数变得非凸。这意味着我们对这类问题的优化求解通常采用迭代的基于梯度的优化，仅仅使得代价函数达到一个非常小的值；而不是像线性模型那样求解其最优解的解析表达式或像逻辑回归和支持向量机那样设计一个全局收敛的迭代算法。深度网络中的反向传播算法没有全局收敛性保证并且往往对迭代初始点的选择敏感。优化深度网络模型的方法大多是对最简单的梯度下降算法的改进。各种算法都利用了代价函数梯度的一步步反向传播从而迭代地优化神经网络的权重值.
1.3 神经网络中的超参数调整

神经网络中除了需要优化网络的权重值，其他比如网络的类型(如全连接网络、卷积神经网络、循环神经网络)，损失函数中的超参数设置(如正则化系数的设置)，网络的初始化策略,优化迭代方法的选择都对最后的性能有着非常大的影响。这些参数不能通过反向传播算法进行优化，我们常常将其称为超参数。模型的性能关于超参数的不可微性使得梯度算法难以用来对超参数进行优化，简单的对超参数进行的网格搜索算法和随机搜索算法需要耗费大量的代价(大量的计算资源消耗和大量的金钱成本)。我们从以下三点阐述寻找一个自动化对神经网络中超参数进行优化的方法具有很大的研究价值:(1)减少在应用机器学习算法中人的参与.这样可以将人类从繁琐的调参过程中解放出来，大大降低优化一个深度网络的工作量.(2)提升机器学习算法的性能.通过参数优化技术有望找到更优的超参数配置从而提高机器学习算法的性能。(3)提高机器学习算法的可复现性以及不同算法之前比较的公平性。大量的机器学习算法通过在特定任务上的精心调参使得其在当前任务获得极好的性能，这一方面使得复现这一实验结果比较困难，另一方面不同的算法性能的比较似乎受限于不同研究人员的调参水平。因此通过统一的参数调试方法的构建可以提高机器学习算法的可复现性以及算法之间比较的公平性。
超参数的自动选择具有很大的吸引力然而其作为优化问题的高度复杂性使得设计一个有效的优化方法十分困难.(1)评估函数的计算代价十分昂贵.在深度学习中的训练过程需要一个庞大的数据集并且网络往往拥有庞大的参数规模，这使得对超参数的单独一组值的性能评价就非常昂贵.(2)不同超参数的取值情况十分复杂.可以是正则化参数这种连续值，网络的深度以及每层的单元数这种整数值，也可以是是否采用dropout这种二值数据，也可以是采用何种优化方法这种集合数据.(3)我们通常不能求得性能函数关于超参数的梯度信息.这也就是说，我们通过在传统优化问题中用到的性质比如凸性和光滑性无法在这一类问题中使用.(4)当训练数据集规模较小时，我们无法对算法的泛化误差进行优化.
2、何为黑盒优化

非形式化的来说，一个黑盒函数 f 可以理解为从 \mathbb{R}^n 到 \mathbb{R} 的一个映射.但是映射关系 f 的解析表达式及工作方式未知，我们只能通过不断地将数据输入到黑盒函数中然后通过得到的输出值来猜测黑盒函数的结构信息.下图表示一个黑盒问题的映射关系.



图1 黑盒函数示意图

与黑盒优化问题相对应的优化问题便是白盒优化问题。白盒问题要么优化问题的具体形式已知(如线性回归和SVM),要么虽然表达式的形式未知，但是我们可以利用目标对优化参数的梯度进行迭代(如深度网络，尽管深度网络也常被看做一个黑盒).这里的黑盒优化指的是优化目标的具体表达式及其梯度信息均未知的优化问题，因此我们无法利用优化目标的本身特性求得其全局最优解，也无法直接利用参数的梯度信息.
除了深度网络的超参数优化问题之外，深度强化学习中智能体与环境的交互问题也可以看做一个黑盒优化问题.在model-free强化学习问题中,我们不对智能体所处的环境进行建模.在这种情形下,我们将环境当做一个黑盒,智能体通过不断尝试动作来从这个黑盒中获得奖励值,最后的优化目标是使累计获得的奖励值最大.下图展示了强化学习问题的一般步骤.



图2 强化学习示意图(无模型强化学习问题中的环境是一个黑盒).

3、黑盒优化的简单方法

3.1 网格搜索法

网格搜索(grid search)是最基本的黑盒优化方法,其也被称为全因子设计(full factorial design).用户为每一个要优化的参数执行一个有限的值集,然后在这些参数的笛卡尔积所构成的网格上进行性能评估.因为需要评估的次数随参数数量的增加呈现指数增长,因此这种方法很难被用到参数数量多的高维黑盒优化场合.此外我们若对网格取得非常密集(每个参数对应的取值集合的基数过大),则在参数数量不多的情形下也需要庞大的计算代价.



图3 当模型中有一个重要参数和一个不重要参数时网格搜索和随机搜索的比较(可以看出同样是进行9次性能评估,随机搜索能够搜索更多的重要参数上所对应的值).

3.2 随机搜索法

一个简单的可以替代网格搜索的方法是随机搜索(random search)法.顾名思义,随机搜索在参数的可能取值中随机抽出来进行性能评估,知道我们给定的计算资源耗尽为止.当其中一些参数比另一些参数重要得多时,随机搜索算法往往比网格搜索方法更有效.只管上来说,当我们对 N 个参数总共进行 B 次性能评价时,网格搜索只能对每个参数只能评价其在 B^{1/N} 个位置上的性能,而随机搜索则能对每个点都评估其取 B 个不同值的性能.这一示意图如图3所示.
由于随机搜索算法没有对机器学习算法进行任何假设并且在给定足够的计算资源的情况下其能够逼近模型的最优解,因此其是评价一个黑盒优化算法的一个有用的基准线.随机搜索算法常常与更复杂的优化算法相结合来提升算法的收敛速率以及增加模型的探索性.由于随机优化算法能够对整个参数空间进行搜索,因此其常被用来初始化一些更为复杂的算法.
其他黑盒优化的方法有遗传算法,进化算法等基于种群的算法.
4、机器学习中的不确定性

4.1 何为不确定性

我们标准的回归和分类模型不能够捕捉到不确定性来介绍机器学习问题中面临的不确定性.在分类任务中,模型输出的高概率值(如softmax输出的高概率值)往往被错误的解释为模型对当前分类结果的置信度.事实上,一个具有极大概率输出值的模型依然可能具有很高的不确定性.如下图所示的一个理想化的二分类任务,训练数据全部处于图中的两条竖着的灰色虚线之间,那么在阴影区域由于并没有训练样本所以在这一区域我们无法对估计的函数值进行调整.尽管分类器在点 x^* 处以概率1判断其属于类别1,但是由于其处于模型的不确定区域中,因而其输出具有很高的不确定性.



图4 一个理想二分类问题的softmax的输入函数f(x)和输出函数\sigma(f(x))(训练样本集中在两条竖虚线之间,灰色区域代表由于没有训练样本所以无法对曲线f(x)进行调整的不确定性区域. x*表示不确定区域中的一个点,在这一点,分类器以概率1输出其属于类别1).

在这个例子中,对模型的测试中出现了与训练数据偏差较大的数据,由于并没有与在这些未见过的数据的范围内对模型进行训练,从而不能够保证模型能够给我们一个值得信赖的分类结果.总的来说,主要有以下几个方面会使得模型预测的结果呈现不确定性:(1)噪声数据.我们的观测数据是带有噪声的,这可能是由于测量误差或者其他可能影响观测的因素导致的.在噪声数据上对模型进行拟合会给模型的预测带来不确定性.(2)模型参数的不确定性.众多机器学习算法尤其是深度学习算法,其模型会有大量的参数,并且不同的参数组合都能够很好的拟合训练数据.我们去选择那种参数的组合去实际应用其实面临模型参数的不确定性问题.(3)模型结构的不确定性.我们无法判断我们应该使用何种网络结构来使得模型更能适应当前的问题.
4.2 不确定性的重要性

在模型给出分类结构的同时给出其对当前结果的不确定性置信度是十分重要的.这是因为在一些诸如疾病检测和自动驾驶等领域,当机器学习算法做出决策时还应给出当前决策可能所面临的风险,因此从这种观点来看,对机器学习模型不确定性的研究属于人工智能安全性的研究范围.
4.3 黑盒优化问题中的不确定性

黑盒优化问题其巨大的计算代价限制了其训练数据的规模,因此如何根据模型的不确定程度来指导我们对模型性能进行更为有效的评估至关重要.贝叶斯优化理论是对黑盒问题进行全局优化并且给出模型不确定性的一种前沿方法,其有两个关键的组成部分:一个概率代理模型(probabilistic surrogate model)和一个确定下一步评估哪个点的获取函数(acquisition function).在每次迭代中,通过目前位置所有的观测值对代理函数进行拟合.然后根据概率模型的预测分布来确定不同候选点对减少模型不确定性所起到的作用来权衡对当前模型的探索与利用(是通过采样新的数据来进一步降低模型的不确定性还是利用当前的模型进行预测).与需要昂贵评估代价的黑盒函数相比,这里的获取函数的计算成本较低,从而可以对该获取函数进行优化.
下图是通过高斯过程代理函数来对一个一维问题进行贝叶斯优化的例子.我们的目标是使得阴影范围(模型的不确定性)尽量小.途中显示我们通过优化获取函数找到其一个最优值来影响后续的数据点的采样情况.(关于该例子的更详细介绍参见参考文献)



图5 一维函数上的贝叶斯优化过程示例.

4.3 高斯过程与不确定性

定义1(随机过程):设 (\Omega,\mathcal{F,P}) 为一概率空间,另设集合 T 为一指标集合.如果对于所有 t\in T ,均有一随机变量 \xi_t(\omega) 定义于概率空间 (\Omega,\mathcal{F,P}) ,则集合 \{\xi_t(\omega)|t\in T\} 为一随机过程.
在随机过程中的指标集合 T 常常是时间的集合.因此随机过程常常被用来描述随时间变化的随机现象比方说:人一生中身高的变化,股票在一天中的价格变化,某路段一天的车流量变化等.如果指标集合 T 至多可列,那么称为离散时间;如果 T 是一个实数区间,则称为连续时间.随机过程可分为:离散时间离散状态,离散时间连续状态,连续时间离散状态,连续时间连续状态.
高斯过程的相关定义如下.
定义2：若随机过程 \xi_t(\omega) 的任意 n 维 (n=1,2,\cdots) 分布都是正态分布,则称该随机过程为高斯随机过程或正态过程.
定理1：\{\xi_t(\omega)|t\in T\} 是高斯过程的充要条件是其任意有限多个元素的线性组合是正态随机变量.
定理2：设已给指标集合 T=[0,+\infty) ,实值函数 m(t) 及对称非负定的二元实值函数 K(s,t),s,t\in T ,则存在概率空间 (\Omega,\mathcal{F,P}) 及定义在其上的实正态过程 \{\xi_t(\omega)|t\in T\} ,其均值为 m(t) ,协方差矩阵为 K(s,t) .
定义3：称随机过程 \{\xi_t(\omega)|t\in T\} 为独立过程,如对任意 n 及 t_1,t_2,\cdots,t_n\ge 0, 随机变量 \xi_{t_1}(\omega),\xi_{t_2}(\omega),\cdots,\xi_{t_n}(\omega) 相互独立.
定理3：正态过程 \{\xi_t(\omega)|t\in T\} 独立的充要条件是 K(s,t)=0,s\ne t.
高斯过程是一个用来度量模型不确定性的很好的工具,其在贝叶斯优化理论中起着至关重要的作用,前文提到的利用高斯过程进行一维函数上的贝叶斯优化就是一个很好的度量模型不确定性的一个例子.
参考文献: