白露 | 机器学习中的退火算法

“凉风至，白露生，寒蝉鸣”，随着秋风送爽，2024年的白露节气如期而至。白露的到来，标志着昼夜温差逐渐加大，秋意渐浓，草木开始泛黄，气候从炎热逐渐转向凉爽。

白露是一个自然界温度慢慢下降的过程，借用这一节气的特征，在此给大家介绍机器学习中一种重要的优化算法——退火算法。

退火算法简介

退火算法（Simulated Annealing, SA）是一种基于物理退火过程的概率优化算法，在机器学习模型的参数优化中展现了独特的价值。它的灵感来自物理学中的退火过程：材料在加热到高温后被缓慢冷却，使其逐渐达到能量最低的稳定状态。该过程中的“温度”概念被引入到优化算法中，通过接受偶尔的次优解来避免局部最优（Local Optimum），逐步逼近全局最优解（Global Optimum）。这种能有效避免局部最优解，找到全局最优解的特性，特别适用于复杂的非凸优化问题（Non-Convex Optimization Problem, NCOP）。

目标函数的最小化

在机器学习中，优化问题通常表现为目标函数的最小化。例如，对于神经网络，目标函数通常是损失函数，其形式可以表示为： $f(x)=\frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, \hat{y}_{i}\right)$ 其中， $L\left(y_{i}, \hat{y}_{i}\right)$ 是模型预测值 $\hat{y}_{i}$ 与真实值 ${y}_{i}$ 之间的损失， $N$ 是样本数。损失函数 $f(x)$ 是一个复杂的非凸函数，可能包含多个局部极小值（local minima）。

算法步骤

1. 初始化：设置初始解 $x_0$ 和初始温度 $T_0$ 。

2. 邻域搜索：在当前解 $x$ 的邻域内随机生成一个新解 $x'$ 。

3. 接受准则：计算目标函数值 $f(x)$ 和 $f(x')$ ，并依据概率 $P$ 决定是否接受新解：

$P(\text { accept })=\left\{\begin{array}{ll} 1, & \text { if } f\left(x^{\prime}\right)<f(x) \\ \exp \left(-\frac{f\left(x^{\prime}\right)-f(x)}{T}\right), & \text { if } f\left(x^{\prime}\right) \geq f(x) \end{array}\right.$ 4. 更新温度：根据冷却策略（如线性、指数或对数冷却）更新温度 $T$ ： $T_{k+1}=\alpha T_k, \alpha \in (0,1)$ 5. 终止条件：当迭代次数达到预设值或温度降至最低阈值（threshold）时终止。

退火算法在机器学习中的应用

退火算法在机器学习中的应用范围广泛，尤其在解决高维度、非凸的优化问题时表现出色。例如，它被用来优化深度神经网络（Deep Neural Networks, DNNs）的训练过程、选择支持向量机（Support Vector Machine, SVM）的参数、执行聚类分析（Clustering Analysis）以及进行特征选择（Feature Selection）。神经网络的训练过程涉及大量参数的优化，其损失函数形状复杂，存在多个局部极小值。传统的梯度下降法可能会陷入这些局部极小值。退火算法通过其独特的概率接受准则，在高温阶段允许接受较差的解，避免早期陷入局部最优，并逐步收敛到全局最优解。

图1. 不同冷却策略下的损失函数优化过程

优势与局限性

优势

全局优化能力：退火算法能有效跳出局部极小值，进行全局搜索。
适应性强：不依赖梯度信息，适用于非凸和高维问题。
简单易实现：相对其他复杂优化算法，退火算法实现简单，调参需求较少。

局限性

计算成本高：需要频繁评估目标函数，特别在高维空间中计算复杂度高。
对冷却策略敏感：算法性能对冷却策略的选择非常敏感。冷却过快可能导致过早收敛到次优解，而过慢则增加计算时间。
收敛速度较慢：相比基于梯度的优化算法，退火算法的收敛速度较慢，尤其在大型数据集和复杂模型中。

结束语

退火算法通过模拟物理退火过程，在机器学习优化中提供了强大的全局搜索能力。尽管存在计算开销大、收敛速度慢等局限性，但其在复杂非凸优化问题中的表现尤为突出。未来的研究方向包括优化冷却策略、加快收敛速度以及探索其在更多机器学习任务中的应用等。

参考文献

[1] Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.

[2] Černý, V. (1985). Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm. Journal of Optimization Theory and Applications, 45(1), 41-51.

[3] Ingber, L. (1989). Very Fast Simulated Re-Annealing. Mathematical and Computer Modelling, 12(8), 967-973.

[4] Bertsimas, D., & Tsitsiklis, J. (1993). Simulated Annealing. Statistical Science, 8(1), 10-15.

[5] Rutenbar, R. A. (1989). Simulated Annealing Algorithms: An Overview. IEEE Circuits and Devices Magazine, 5(1), 19-26.

文 | 伍汝杰

图 | 朱成轩

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

内容中包含的图片若涉及版权问题，请及时与我们联系删除

白露 | 机器学习中的退火算法

评论