Tree-structured Parzen Estimator（TPE）：一种基于贝叶斯优化的高效超参数优化算法

Tree-structured Parzen Estimator（TPE）是一种基于贝叶斯优化的高效超参数优化算法，适用于机器学习模型的性能提升。以下是TPE采样器的原理介绍：

贝叶斯优化框架

贝叶斯优化是一种用于优化未知函数的技术，它基于观察结果进行优化。它通过概率模型（也称为代理模型）来近似目标函数，并利用采集函数（acquisition function）来决定下一个评估点，以提高优化效率。

TPE的核心思想

TPE与基于高斯过程（GP）的贝叶斯优化方法不同，它不是直接对给定输入 $x$ 和输出 $y$ 的后验概率分布 $p(y|x)$ 进行建模，而是分别对条件概率分布 $p(x|y)$ 和边缘概率分布 $p(y)$ 进行建模。这种方法避免了对目标函数本身先验分布的指定，使得TPE在处理复杂、高维的搜索空间时更加灵活。

概率密度的建模

TPE使用两个密度函数来定义 $p(x|y)$： - $l(x)$：使用观测空间 $\{x^{(i)}\}$ 来建立，该观测空间对应的损失 $f(x^{(i)})$ 小于阈值 $y^*$。 - $g(x)$：使用剩下的观测来建立。

TPE通过贝叶斯公式来计算后验概率分布 $p(y|x)$，并选择 $l(x)/g(x)$ 最大化时对应的超参数作为下一组搜索值。

采集函数

TPE选择期望改进（Expected Improvement, EI）作为采集函数。EI量化了新点 $x$ 相对于当前最佳已知值 $y^*$ 的改进量。EI的计算公式为： $$EI(x) = \mathbb{E} \left[ \max (y^* - y, 0) \right] = \int_{-\infty}^{\infty} \max (y^* - y, 0) p(y|x)dy$$ 其中，$y^*$ 是到目前为止观察到的最好（最小）值，$p(y|x)$ 是代理模型。

Parzen窗估计器

TPE使用Parzen窗估计器（也称为核密度估计器）来估计 $l(x)$ 和 $g(x)$。对于连续值，Parzen窗估计器使用截断的高斯分布来近似密度函数；对于离散或分类值，则使用加权直方图来估计密度。

迭代过程

在每次迭代中，TPE算法执行以下步骤： 1. 随机采样一组超参数，评估目标函数并记录结果。 2. 根据设定的分位数 $\gamma$，将观测值分为“好”分布 $l(x)$ 和“坏”分布 $g(x)$。 3. 使用Parzen窗估计器分别估计 $l(x)$ 和 $g(x)$。 4. 计算每个候选点的EI，并选择EI最大的点作为下一个评估点。

通过这种方式，TPE能够在尽可能少的迭代次数内找到全局最优解，同时自适应地调整参数搜索空间的大小。