高斯过程偏好学习

第 16 章把“你更喜欢哪一个？”的回答转化为似然，即概率单位选择模型：按照这一模型，偏好某个选项的概率随两个选项效用之差的增大而增大。这种似然导致后验不再是高斯分布，第 17 章介绍了相应的处理方法。本章借助第 8 章的高斯过程先验把两者结合起来。有了这一先验，针对几十个设计的几十个回答就能为每个设计提供信息，包括从未展示过的设计。

由此得到的就是 Chu 与 Ghahramani（2005）的模型。二十年后，它已成为偏好贝叶斯优化的默认模型，第 19 章中的图运行的也是这一模型。本章先建立模型，推导拟合方法，再用于预测，然后讨论回归模型中不曾出现的两个问题：一是比较根本无法提供哪些信息；二是比较了哪些对，会如何影响比较所能提供的信息。

18.1 模型 #

人对定义域 $\X$ 中的设计有潜在效用 $g$。设计可以是海报的颜色、外骨骼控制器的参数、照片滤镜的设置。为效用赋予高斯过程先验，

于是在获得任何回答之前，任意有限个设计的效用都服从联合高斯分布，协方差由核函数 $k$ 给出（第 7 章）。核函数体现了一个关键假设：在 $\X$ 中相近的设计，效用也相近。正是这一假设，使得从少量回答中学习成为可能。

数据由 $n$ 个不同设计 $\vx_1, \dots, \vx_n$ 之间的 $m$ 个回答组成。第 $k$ 个回答表明设计 $v_k$ 优于设计 $u_k$，这里 $v_k$ 与 $u_k$ 是设计在列表中的下标。同一设计可以出现在多个回答中，因此 $n$ 至多为 $2m$，通常还要小得多。将各设计处的效用排成向量 $\vf = (g(\vx_1), \dots, g(\vx_n))^\T$，其先验为 $\N(\mathbf{0}, \mK)$，其中 $[\mK]_{ij} = k(\vx_i, \vx_j)$。每个回答服从 Thurstone 第五种情形（式（16.2）），且给定效用时各回答相互独立：

Chu 与 Ghahramani（2005）推导这一似然的方式与第 16.3 节完全相同：先设想一个理想的判断者，只要 $g(\vx_{v_k}) \ge g(\vx_{u_k})$ 就偏好 $v_k$；再给每个潜在值叠加方差为 $\sigma^2$ 的独立高斯噪声。噪声尺度 $\sigma$ 与核函数的长度尺度、幅度一样，都是超参数。

$\vf$ 的后验即式（17.1）：高斯先验乘以式（18.1）后归一化。这一后验不是高斯分布，Chu 与 Ghahramani（2005）用第 17.2 节的 Laplace 近似代替它。此后，新设计处的预测与回归完全相同，直接由高斯过程得到：给定 $\vf$，其他任何位置的效用都服从条件高斯分布。

同一模型还可以从另一个角度理解。似然只依赖于差值，因此可以定义一个以选项对为自变量的函数 $h(\vx, \vx') = g(\vx) - g(\vx')$，把每个回答视为该对上的二元标签。$h$ 是 $g$ 的线性变换，因而本身也是高斯过程，其协方差为

将两个差值的协方差逐项展开即得此式。Houlsby 等人（2011）（预印本）推导出这一偏好核（preference kernel），并据此得出结论：Chu 与 Ghahramani 的模型“等价于采用某一类特定核函数的 GPC”，即定义在选项对上的高斯过程分类。因此，分类问题的全部工具，包括第 17 章中的各种近似方法，都适用于这一模型。

这类偏好学习很早就应用于真人。Brochu 等人（2007）采用同样的 Thurstone 模型，让人在渲染出的样例之间做选择，以此帮助他们找到计算机图形学所需的材质外观。此后，该模型又结合 Laplace 近似，用于根据用户的比较和序数标签学习用户偏好的外骨骼步态（Li 等，2021）。第 24 章与第 25 章完整演示了两个此类问题的求解过程。

18.2 拟合模型 #

拟合模型，就是求出后验众数 $\hat\vf$ 以及众数处的曲率。式（17.4）给出了适用于任意似然的 Newton 步，所需的只是似然的梯度和负 Hessian 矩阵 $\mW$。对比较数据，这两者具有特定的结构，本章后文的许多结论都源于此，因此下面给出完整推导。记 $s = \sqrt{2}\,\sigma$；对第 $k$ 个回答，记 $z_k = (f_{v_k} - f_{u_k})/s$，$\mathbf{a}_k = \mathbf{e}_{v_k} - \mathbf{e}_{u_k}$，该向量在获胜选项处为 $+1$，在落败选项处为 $-1$，其余位置为 0，从而 $z_k = \mathbf{a}_k^\T\vf/s$。

下面逐个分量解读式（18.2）。对每个设计，它每赢得一个回答，梯度就将其推高 $\lambda(z_k)/s$；每输掉一个回答，梯度就将其压低同样的量。回答越出乎意料，推力越大：当 $z$ 取很大的负值，即按当前效用本应是落败选项获胜时，$\lambda(z)$ 近似按 $-z$ 增长；回答在意料之中时，它趋于零。矩阵 $\mW$ 的对角元是各设计所参与回答的权重之和，非对角元是两个设计之间回答的权重之和的相反数。这正是比较图（comparison graph）的加权图 Laplace 矩阵（weighted graph Laplacian）；比较图以设计为节点，以已回答的对为边。其含义留待第 18.5 节讨论。

由此可直接得到两个推论。其一，每个 $\mathbf{a}_k$ 的分量之和为零，故梯度的分量之和也为零，即 $\mathbf{1}^\T\nabla\ell = 0$，且 $\mW\mathbf{1} = \mathbf{0}$：所有效用同时增加同一个量，任何回答的概率都不变。其二，权重依赖于 $\vf$，因此每个 Newton 步都要重新计算 $\mW$。

有了这两项，拟合过程即为下面的算法。本书图形代码中的 fitPreference 实现的就是这一算法。

初始时每个 $z_k = 0$，在模型看来每个回答都如同抛硬币，所有权重都等于 $\lambda(0)^2/s^2 = (2/\pi)/s^2$。因此第一步对所有回答一视同仁，后续各步再按各回答实际的意外程度重新加权。在本章的图中，拟合在五至十三步内收敛。每步需求解一个 $n \times n$ 线性方程组，代价为 $O(n^3)$，与回归相同。

在众数处，对数后验的梯度为零：$\nabla\ell(\hat\vf) - \mK^{-1}\hat\vf = \mathbf{0}$，因此

即 Chu 与 Ghahramani（2005）的式（11）。向量 $\hat{\bm\beta}$ 相当于回归中的 $\bm\alpha = \mK^{-1}\vy$（式（8.4））：每个设计对应一个权重，胜出多于模型预期的设计权重为正，落败的设计权重为负。

同样的计算还给出 Laplace 模型证据式（17.5）。Chu 与 Ghahramani（2005）最大化的正是这一证据，优化变量为核函数超参数和 $\sigma$（其式（12））；BoTorch 拟合偏好模型的方式与此相同（第 18.6 节）。

import numpy as np
from scipy.stats import norm

def terms(f, duels, s):
    """Gradient and negative Hessian of the pairwise probit log-likelihood."""
    n = len(f)
    grad, W = np.zeros(n), np.zeros((n, n))
    for i, j in duels:                        # 设计 i 优于设计 j
        z = (f[i] - f[j]) / s
        lam = np.exp(norm.logpdf(z) - norm.logcdf(z))   # phi(z) / Phi(z)
        grad[i] += lam / s
        grad[j] -= lam / s
        w = lam * (z + lam) / s**2
        W[i, i] += w; W[j, j] += w; W[i, j] -= w; W[j, i] -= w
    return grad, W

def fit_preference(K, duels, sigma=0.1, iters=50):
    n, s = len(K), np.sqrt(2) * sigma
    f = np.zeros(n)
    for _ in range(iters):
        grad, W = terms(f, duels, s)
        f_new = K @ np.linalg.solve(np.eye(n) + W @ K, W @ f + grad)
        done = np.max(np.abs(f_new - f)) < 1e-8
        f = f_new
        if done:
            break
    grad, W = terms(f, duels, s)              # 众数处的 beta 与 W
    return f, grad, W

18.3 预测偏好 #

求得众数和曲率后，$\vf$ 的 Laplace 后验为高斯分布 $\N(\hat\vf, (\mK^{-1} + \hat\mW)^{-1})$，新设计处的效用预测便归结为高斯条件化，与第 8.1 节相同。对新设计 $\vx$，记 $\vk(\vx)$ 为它与各已比较设计之间的先验协方差。

这与 Chu 与 Ghahramani（2005）的式（17）、式（18）一致，也与 Rasmussen 与 Williams 给出的分类预测方程（Rasmussen 与 Williams，2006，第 3 章）一致，只是以比较数据得到的 $\hat\mW$ 代替了其中的对角矩阵。第 4 步的第二种形式不可或缺：$\hat\mW$ 是图 Laplace 矩阵，总有零特征值，因此 $\hat\mW^{-1}$ 不存在。

偏好优化器最常用到的量，是人偏好新设计 $\vx$ 而非另一个新设计 $\vx'$ 的概率。在 Laplace 近似下，两个潜在值服从联合高斯分布，均值为 $\mu, \mu'$，方差为 $\sigma^2(\vx), \sigma^2(\vx')$；协方差 $c$ 由同一公式得到，只需把右侧换成 $\vk(\vx')$。二者之差的均值为 $\mu - \mu'$，方差为 $\sigma^2(\vx) + \sigma^2(\vx') - 2c$，代入式（16.6）得

即 Chu 与 Ghahramani（2005）的式（19）。协方差 $c$ 不可忽略。两个相近设计的潜在值高度相关，二者之差的不确定性因而远小于其中任何一个值；即使模型不确定任何一个设计有多好，也可以对二者的顺序相当有把握。

下图在贯穿全书的示例目标函数上运行这一模型，即第 11 章中的双峰函数。模拟用户以该函数为效用，每次比较的回答带有少量概率单位噪声；比较哪些对由你选择。图上方的比较图为每个回答画一条弧。

可以尝试以下几点：

• 按两次“随机十对”。图中初始只有六个回答，不足以找到任何一个峰。再增加 20 个回答后，均值曲线呈现出两个峰，最大值位于 $x = 0.72$，紧邻位于 0.73 的真实最大值。每次比较只在其两端处移动曲线，并通过核函数影响两端的邻域。
• 观察区间带。区间带在已比较的设计附近收窄，但整体上仍然很宽，即使有 20 个回答，也仍约为 $\pm 1$。这并非模型失效，原因见第 18.4 节。
• 查看最后一次预测。最初几个回答的预测概率较为分散，一些获胜选项事先被预测会落败（概率低于一半）；之后，多数获胜选项的预测概率在 0.8 或以上。出乎意料的回答使曲线移动最大，因为其 $\lambda(z)$ 较大。
• 改变长度尺度。当 $\ell = 0.03$ 时，每个回答只形成一个局部凸起，附近没有比较的地方，曲线都回落到零附近。当 $\ell = 0.5$ 时，曲线过于僵硬，无法同时容纳两个峰，最大值落在错误的位置。
• 反复按“最优对随机”。此时每一对都包含当前最优设计，比较图成为星形。最优设计周围的区域学得很好，其余区域学得很差。同样的模式还会出现在第 19.3 节的擂主与挑战者规则中，以及 EUBO 向当前最优点坍缩的现象中（第 19.6 节）。

18.3.1 二维及更高维 #

从式（18.1）到式（18.5），所有公式都与输入维度无关：设计只通过核函数、以距离的形式进入模型。下图在二维设计空间上运行同一模型，模拟用户的效用为 Branin 函数。这是一个标准测试函数，沿一条弯曲的山谷有三个同样好的最大值；此处将其缩放到单位正方形上，并使数值越大越好。

可以尝试以下几点：

• 对照左图与中图。只用 17 个设计之间的 20 个随机对，后验均值就恢复了山谷的大致形状。在默认抽取下，后验均值对 89% 的已比较设计对排序正确，在整个正方形上与隐藏效用的秩一致性为 0.87；多按几次“重新抽取”，可见该一致性在约 0.4 至 0.9 之间变化。
• 查看右图。不确定性在比较过的设计处最低，在任何比较都未触及的角落最高。
• 切换到“星形”。每个回答都涉及同一个中心设计。中心设计与其他设计的比较关系得到了学习，但其他设计之间从未相互比较，模型在这种布局下表现最差：30 次抽取的平均结果是 81% 的对排序正确，秩一致性为 0.63；随机对则分别为 85% 和 0.71。
• 切换到“孤立对”。此时二十个回答涉及 40 个设计，分属 20 个互不相连的分量。每个回答确定了两个设计的顺序，但不直接说明它们与其他对之间的关系，因此对与对之间的偏移只能来自核函数。核函数如此光滑时，这种做法可行：30 次抽取中，模型仍对 82% 的对排序正确；40 个设计对正方形的覆盖优于 17 个设计，因此模型在正方形上的秩一致性略高（0.79）。
• 将长度尺度缩短到 0.08。此时核函数对设计之间的关联减弱。孤立对的正确排序比例降至 76%，随机对降至 82%：先验对设计之间的关联越弱，就越需要依靠回答本身来建立关联。

维度更高时，模型的表现如何？同一段代码可以给出答案。表 18.1 给出一项示意性计算：在单位立方体中取 40 个随机设计，由噪声为 $\sigma = 0.1$ 的模拟用户回答其间的 $m$ 个随机对，使用长度尺度为 0.52 的径向基函数核（BoTorch 默认先验的众数，第 18.6 节），重复 20 次。效用取 3 维和 6 维的 Hartmann 函数（两个标准基准），以及嵌入 20 维空间的 6 维 Hartmann 函数，其中 14 个输入不起作用。“核函数值”一列是两个设计之间的平均先验相关系数。

有两个规律值得注意。一是模型对新设计的把握随维度增加而崩溃：在 20 维中，按核函数衡量，随机设计彼此相距太远（平均核函数值为 0.006），每个回答几乎只能提供其自身两个设计的信息。二是模型对已见过的设计的排序，在每个维度上都随回答增多而持续改善，因为这些设计由直接比较排序。若让长度尺度随输入个数 $d$ 增长，取 $0.3\sqrt{d}$，20 维中的平均核函数值可提高到 0.41，但新设计上的秩相关系数仅提高到 0.19、0.30 和 0.28：问题出在 14 个不起作用的输入上，而所有输入共用同一长度尺度的核函数（各向同性核）无法忽略它们。这些结果只来自一个示意性设置，并非基准测试（推断）。它们提示了高维偏好贝叶斯优化为何既依赖核函数的结构，例如每个输入各有一个长度尺度（第 9.2 节），也依赖比较对的选择（第 19 章）；相关研究见第 30 章。

18.4 哪些量可以识别 #

图 18.1 中的区间带在 20 个回答之后仍然很宽；而有 20 个观测的回归模型，其区间带会在每个观测处收窄。差别不在于近似，而在于比较能够测量什么。

平移。每个回答的概率都依赖于效用之差，因此给所有效用加上同一常数 $c$，即 $\vf \mapsto \vf + c\mathbf{1}$，似然不变。在式（18.2）中，这体现为 $\mathbf{1}^\T\nabla\ell = 0$ 和 $\mW\mathbf{1} = \mathbf{0}$：任何回答都不会沿方向 $\mathbf{1}$ 施加推力，也不会在该方向上增加曲率。关于整体水平的信息只来自先验，后验因而保留了先验对整体水平的不确定性；正是这部分为所有设计共有的不确定性使区间带一直很宽。下图展示同一模型，但区间带改为针对 $g(\vx)$ 减去其在定义域上平均值后的量，这是比较能够测量的量。