优化昂贵的功能

数据挖掘 机器学习 特征选择 优化
2022-02-03 22:56:49

我正在尝试一些不同的技术来优化 Boosted Gradient Regressor,方法是使用进化编程技术来尝试找到最有效的特征集。到目前为止,我已经取得了一些不错的结果(能够删除 65% 的特征并提高了准确性),但我对每个 epoch 的运行成本(就时间而言)印象不深。目前,这是一个非常昂贵的优化问题,2^79因为最多有 79 个特征可供选择,这6.0446291e+23可能是特征排列。

到目前为止,我的种群中的每个个体都有一个二进制编码的基因,其中1= 使用此功能,并且0= 不使用此功能。通过使用所选特征运行增强回归器来评估群体中的每个个体,然后计算 RMSLE。在优化功能大约 3 小时后,我开始看到良好的结果(我没有进行任何并行计算)。

我一直在做一些研究,以尝试“预测”我的增强回归器的性能,而无需实际评估其性能。到目前为止,我发现了以下技术:

  1. 问题逼近。我可以看到这在某些特定情况下是如何有用的,但由于我无法真正降低评估我的提升回归量的准确性的复杂性,这似乎无关紧要。
  2. 函数逼近。我认为这是一个非常有趣的技术。他们的整个前提是在不需要实际评估函数的情况下近似个人的适应度
  3. 健身传承。这似乎也很有趣,也许是上面列出的最有效的方法?个体被聚集到特定的组中,然后每个集群的“代表”个体对其适应度进行评估,然后通过距离测量来近似剩余个体的适应度。

不过,我可以看到这些技术存在一些问题。如果使用的特征组合与输出没有线性关系,那么函数逼近肯定很难逼近个人的潜在适应度吗?我对进一步看什么有点难过。

1个回答

根据两篇论文(有限评估进化算法(LEEA)有限评估合作协同进化差分进化算法(LECCDE)),您可以通过将算法应用于小批量而不是整个数据集来近似进化算法的结果就像在 SGD(随机梯度下降)中一样。这显着减少了计算时间(在 LECCDE 论文中,MNIST 数据集上的 ANN 大约是 25 倍)。

根据Prellberg 2018 Limited Evaluation Evolutionary Optimization的说法,LE 算法的训练时间仍然是随机梯度下降的 Adam 变体的 10 倍。在您的情况下,无法计算梯度。

第一篇论文 (LEEA) 中提出了对进化算法的以下更改:

  1. 在确保预期输出的多样性的同时使用小批量。

LEEA 中的理想 mini-batch 大小通过实验确定为 2。 ...为了在 minibatch 中应用多样性的概念,输出范围被分成两个大小相等的部分,并选择示例以使每个 mini-batch 包含一个示例范围的两个部分。在每一代开始时随机生成一个新的小批量。

  1. 使用祖先适应度进行评估。

f'=(f_p1 + f_p2)/2*(1-d) + f。

其中 f' 是个体的修正适应度。f 是个人对当前小批量的适应度。f_pn 是父母 n 的适应度。d 是一个常数衰减值。

第二篇论文(LECCDE)指出了使用有限评估算法的以下加速:

LECCDE 与 CCDE 的不同数据集:

Dataset    Parameters   Speedup             Accuracy
WBC        1652          1.10 times faster  1.2% worse
ESR        9052          2.05 times faster  0.3% worse
HAR        28406         4.00 times faster  0.2% worse
MNIST      47710        25.3  times faster  unknown