CA——Deep-Neural-Auction(DNA)

Deep Neural Auction, 简称 DNA

参考链接：
- 原始论文：Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertising, Alibaba, KDD 2021
- 博客：KDD 2021 | Neural Auction: 电商广告中的端到端机制优化方法

问题定义

和 DeepGSP 类似，DNA拍卖问题形式化定义为：
$$
\begin{align}
\mathop{\text{maximize}}_{\mathbf{\mathcal{M}}} &\mathbb{E}_{\mathbf{b} \sim \mathcal{D}}\Big[\sum_{j=1}^L \lambda_j\times f_j(\mathbf{b};\mathbf{\mathcal{M}})\Big]\\
\text{s.t.} &\text{Incentive Compatibility (IC) constraint}, \\
&\text{Individual Rationality (IR) constraint},
\end{align}
$$
- $\mathbf{b}$：广告主出价向量
- $L$：优化目标数
- $\mathcal{D}$：广告主出价分布, $\mathbf{b}$ 是从分布 $\mathcal{D}$ 中采样得到的
- $\lambda_j$：目标权重，是用于控制目标之间重要性的权重因子，可调整目标重要性
- 注：相对 DeepGSP 论文的定义，这里增加了激励兼容(IC)和个体理性约束(IR)，其中个体理性约束是指竞拍者的效用不为负 $u_i = v_i - p_i \ge 0$

Deep Neural Auction 基本思路

分配规则和计费规则

基本思路：按照经典GSP的基本原理，先按照 Rank Score 进行非递减的顺序排序，然后竞胜者按照获得该位置所需要的最小价格计费
分配规则 $\mathcal{R}$ ：按照 Rank Score 排序(Rank Score 是关于出价 bid 非递减的函数)，$r_i(b_i)$，排序中最靠前的 Top-K 个广告主赢得 K 个广告位
计费规则 $\mathcal{P}$ ： $p_i = r_i^{-1}(r_{i+1}(b_{i+1}))$

DNA与传统拍卖模型的区别

DNA与传统拍卖模型的区别对照示意图

经济学属性

Definition 2.1 (Incentive Compatibility)

原始论文表述：

An auction mechanism is IC if it is in the best interest of each advertiser $i$ to truthfully reveal her maximum willing-to-pay price, i.e., $b_i = m_i$.
理解：一个拍卖机制是激励兼容的，意味着每个广告主的最佳利益就是真实的表达他愿意支付的最大出价
注：最大愿意支付价格，即 maximum willing-to-pay price，用 $m_i$ 表示

Definition 2.2 (Value Maximizer)

论文中，作者引入了价值最大化类型广告主（Value Maximizer），同时讨论了，价值最大化类型广告主和效用最大化类型广告主的区别（Utility Maximizer）
讨论：传统经典的拍卖机制，比如 VCG 拍卖或者 Myerson 拍卖，都假定了广告主是效用最大化的类型（Utility Maximizer），即广告主的目标是为了最大化其拟线性效用（Quasi-linear Utility），形式化的定义为： $u_i = v_i - p_i$。然而，作者观察到工业界的电商平台中，这种效用最大化模型不再能建模广告主的行为范式，比如，淘宝广告平台中，oCPC 和 MCB 这两种广告主，他们的目标都是在指定约束下，最大化他们的点击量/转化量，这种类型的广告主会使用自动出价服务，基于当前竞拍环境，为每个请求/PV计算并报告他们的最大 willing-to-pay 价格，这种行为范式可以建模为价值最大化（Value Maximizer）
- 注：MCB一般是指多约束，论文中主要指预算约束+PPA（pay-per-acquisition）或PPC（pay-per-click）约束
原文定义表述：

A value maximizer $i$ optimizes value $v_i$ while keeping payment $p_i$ below her maximum willing-to-pay $m_i$; when value is equal, a lower $p_i$ is preferred
理解：价值最大化类型的竞拍者的目标是在愿意支付的成本约束下（$p_i \le m_i$），最大化拿量；当量相等时，更倾向于更低的价格
在多位置拍卖系统中，在计费不超过最大愿意支付价格 $m_i$ 的情况下，广告主会更喜欢争取更高的位置；同时，在价值量 $v_i$ 相同的情况下，广告主更倾向于支付更低的价格
个人理解：Value Maximizer 只是表象，本质上，广告主的最终目标应该也是 Utility Maximizer（即利润最大化），只是这个效用包含了广告主毛利等私有信息，这部分信息是未知的

IC和IR

激励兼容满足等价于下面两个约束满足：
- Monotonicity: An advertiser would win the same or a higher slot if she reports a higher bid;
- Critical price: The payment for the winning advertiser is the minimum bid that she needs to report to maintain the same slot
个体理性约束：当满足IC要求的两个约束时，个体理性约束自然满足的，因为IC约束中隐含着 $p_i \le m_i$

Deep Neural Auction

整体架构

整体架构图
整体包含三个主要部分：Set Encoder, Context-Aware Rank Score Function, Differentiable Sorting Engine

Set Encoder

用于从整个竞价队列中提取特征，Set Encoder的输出会作为特征输入后续的其他模块
可以用于解决 ambiguity issue，该问题的定义是：在同一个拍卖中，相同的特征可能获得不同的结果：

The second challenge is data efficiency. The current learningbased approaches [20, 39] usually require a large number of samples to learn the optimal auction due to an ambiguity issue we observed in the data from auctions. It is a common case that an advertiser with the same feature profile can result in different outcomes in distinct auctions, e.g., wins in one auction but loses in another, due to the change of the auction context, e.g., the competition from the other advertisers.
编码过程
$$
\begin{align}
h_i &= \sigma(\phi_1(\mathbf{x}_i)) \\
\mathbf{h} &=\{h_i\}_{i=1}^N \\
h_i^\prime &= \sigma(\phi_2(\text{avgpool}(\mathbf{h}_{-i})))
\end{align}
$$
- 其中 $\{\mathbf{x}_i\}_{i=1}^N$ 表示候选广告， $\mathbf{h}_{-i}$ 表示出去广告 $i$ 后的其他广告特征

Context-Aware Rank Score Function

分配规则

输入是单个广告特征和Set Encoder输出的降价队列特征，用于计算 Rank Score 分数
其网络表示如下：
$$rankScore = r(b_i, \mathbf{x}_i^\prime)$$
- 其中 $\mathbf{x}_i^\prime = (\mathbf{x}_i, h_i^\prime)$
为了保证单调性，使用了一种两层的 MinMax 网络：设置 Q 组函数，每次包含 Z 个线性函数：
$$ r_i = \min_{q\in[Q]} \max_{z \in [Z]} (e^{w_{qz}}\times b_i + w^\prime_{qz}\times \mathbf{x}_i^\prime + \alpha_{qz})$$
- 单调性保证：任意给定 $w$ 和 $z$，都存在一个线性函数 $f_{qz}$：$f_{qz}(b_i, \mathbf{x}_i^\prime) = e^{w_{qz}} \times b_i + w^\prime_{qz}\times \mathbf{x}_i^\prime + \alpha_{qz}$，显然该线性函数关于出价 $b_i$ 单调，此时对多个单调的线性函数取 Max 操作不会改变单调性，继续取 Min 操作也不会改变单调性（ $b_i$ 增加时，任意函数 $f_{qz}(b_i, \mathbf{x}_i^\prime)$ 的最大最小值也都在增加）
- 函数拟合能力：上面的 MIN-MAX 函数理论上可以近似任意的函数（详情见：Monotone and partially monotone neural networks）

计费规则

计费逻辑如下：
$$ p_i = \max_{z\in[Z]}\min_{q\in[Q]} e^{-w_{qz}}(r_{i+1} -\alpha_{qz} - w_{qz}^\prime \times \mathbf{x}_i^\prime) $$
问题：这里的反函数是错的，理论上应该是下面的表达才对(TODO：待确认)：
$$ p_i = \min_{z\in[Z]}\max_{q\in[Q]} e^{-w_{qz}}(r_{i+1} -\alpha_{qz} - w_{qz}^\prime \times \mathbf{x}_i^\prime) $$
- 可以举例并画出函数图像说明： $f(x) = \max(2x, x+1)$ 的反函数是 $f^{-1}(y) = \min(\frac{1}{2}y, y-1)$

Differentiable Sorting Engine

输入 Rank Score 分数，进行可微分排序，并执行计费操作，包含 Differentialble Sorting Operator 和 Allocation & Pricing 两部分
设未排序的 Rank Score 分数集合为 $\mathbf{r} = [r_1, r_2, \cdots, r_N]^T$，令 $\text{argsort}(\mathbf{r})$ 为 $\mathbf{r}$ 降序排列的序号，则可以定义排列矩阵 $M_r \in \{0,1\}^{N\times N}$：
$$M_r[k,i]=
\begin{cases}
1& \text{if}\ i=\text{argsort}(\mathbf{r})[k]\\
0& \text{otherwise}
\end{cases}$$
进一步地，可以用下面的等价形式表示：
$$M_r[k,i]=
\begin{cases}
1& \text{if}\ i=\text{argmax}(c_k)\\
0& \text{otherwise}
\end{cases}$$
- 其中 $c_k = (N+1-2k)\mathbf{r} - A_r\mathbb{I}$, $A_r[i,j] = |r_i - r_j|$ 表示两个元素对之间的 Rank Score 差的绝对值， $\mathbb{I}$ 表示值全为1的列向量 $\mathbb{I}=[1,1,\cdots,1]^T$
- 这一步表述来自论文：Stochastic Optimization of Sorting Networks via Continuous Relaxations, Stanford University, ICLR 2019 的 Corollary 3 和附录 B.1 B.2，详细验证代码见附录
于是，对 $\text{argmax}$ 进一步做放松（放松为 $\text{softmax}$ ），则有
$$\hat{M}_r[k,:] = \text{softmax}(\frac{c_k}{\tau})$$
- $\tau > 0$ 表示温度系数，当 $\tau \to 0$ 时，$\hat{M}_r \to M_r$
- 理解：用 $\text{softmax}$ 来替换 $\text{argmax}$ 做放松可以理解为将 100% 的确定性选择概率变成了带随机性的选择概率
- $\hat{M}_r$ 也被作者称为行随机的排列矩阵（ row-stochastic permutation matrix ）
此时，如果将按照 Rank Score 降序排列后，按照反函数计费规则计费的结果表达为 $\mathbf{p} = [p_1, p_2, \cdots, p_N]^T$ ，则有 Top-K 广告的付费金额为：
$$ f_{\text{pay}} = \hat{M}_r[1:K,:]\cdot \mathbf{p} $$
- 理解：这里 $f_{\text{pay}}$ 是一个 K 行的向量，分别代表 Top-K 的支付值

端到端训练实现

主要损失函数

前K个位置拍卖的性能指标可以表达为：
$$
\begin{align}
\text{整体性能指标} &= \hat{M}_r[1:k,:] \cdot F_{\text{all}} \\
F_{\text{all}} &= [\sum_{l=1}^L\lambda_l\times f_l^1,\sum_{l=1}^L\lambda_l\times f_l^2,\cdots,\sum_{l=1}^L\lambda_l\times f_l^N]^T
\end{align}
$$
- 其中 $F_{\text{all}}$ 表示所有广告的性能指标向量
- 理解：$\hat{M}_r[1:k,:]$ 表示前 K 个位置展示 $N$ 个广告的概率，$\hat{M}_r[1:k,:] \cdot F_{\text{all}}$ 是一个 K 维向量，表示前 K 个位置的性能指标
因此，训练时最小化前K个位置的负目标性能指标和，即下面整体目标损失函数即可：
$$\mathcal{L}_{\text{tgt}} = \sum_{i=1}^K \hat{M}_r[i,:] \cdot F_{\text{all}}$$
- 注：由于排序改变会影响计费（论文中也称计费为 Revenue），作者使用 $f_{\text{pay}} = \hat{M}_r[1:K,:]\cdot \mathbf{p}$ 来近似代替前 K 个位置的计费（问题：这个计费的 Top-K 排序也是按照 Rank Score 降序排列得到的吧，一旦 Rank Score 发生了变化， Top-K 广告也要变化的，计费不用变化吗？）
- 无论如何都会出现不稳定问题(计费 Revenue 的值依赖着 Rank Score 的求逆)，以下是来自阿里官方账号的讲解 KDD 2021 | Neural Auction: 电商广告中的端到端机制优化方法的内容：
  
  仔细观察这两个 loss 的形式不难发现，$\mathcal{L}_{\text{tgt}}$ 的优化其实就是使网络产生的 rankscore 与在用户真实行为上计算出的多目标最优排序一致，但由于 revenue 的计算还是依赖于网络 rankscore 的求逆，导致 rankscore 之间的 distance 又会被显式优化，这给模型训练带来了一些不稳定的因素（离线实验中我们也确实观察到了）；而 $\mathcal{L}_{\text{ce}}$ 由于只纠正序的准确性，不涉及广告 rankscore 之间 distance 的学习，它的训练过程较为稳定。我们的经验是：如果优化目标仅有 revenue，那么 $\mathcal{L}_{\text{tgt}}$ 任务可以独立训练，最终会收敛（尽管其 learning curve 存在一些毛刺）；如果优化多个目标之间权衡，那么 $\mathcal{L}_{\text{tgt}}$ 的权重要和 $\mathcal{L}_{\text{ce}}$ 在同一水平，或者先全局优化 $\mathcal{L}_{\text{ce}}$ 学好 allocation，再引入 $\mathcal{L}_{\text{tgt}}$ 精细化优化 revenue
  值得注意的是，工业界广告系统的真实反馈通常是稀疏的，算法日志中有用户行为的数据占比可能较低。为了使训练信号更加稠密、提高模型学习的效率，我们将用户反馈与预估值进行了融合，在有用户行为的数据上使用后验校准技术来纠正预估值，再进一步构造两个 loss，提高了训练的稳定性

辅助损失函数

借助用户真实反馈来构建辅助损失，让出现最优排序的概率越大越好，辅助损失函数的形式如下：
$$ \mathcal{L}_{\text{ce}} = -\frac{1}{N} \sum_{k=1}^N \sum_{i=1}^N \mathbb{I}{(M_y[k,i]=1)} \log \hat{M}_r[k,i] $$
- 其中 $\mathbb{I}(\cdot) $ 是指示函数
- 注：$M_y[k,i]$ 表示按照真实反馈算出来的 ground-truth 排序矩阵（问题：无法观察到同一个请求不同排列的反馈吧，使用如何确定这个是最优的排列？除非用预估值或模拟器，如果用预估值的话，和普通GSP分配方式有何区别？）

附录：可微分排序argsort到argmax转换证明

证明

参考论文 Stochastic Optimization of Sorting Networks via Continuous Relaxations, Stanford University, ICLR 2019 的 Corollary 3 和附录 B.1 B.2

代码验证

验证代码如下：

import numpy as np

def generate_rank_matrix_original(r):
    """
    通过 argsort 生成排列矩阵 M_r^{(1)}
    """
    N = len(r)
    # argsort 返回的是从小到大排序的索引，我们需要降序排序
    sorted_indices = np.argsort(-r)
    Mr = np.zeros((N, N), dtype=int)
    for k in range(N):
        i = sorted_indices[k]
        Mr[k, i] = 1
    return Mr

def generate_rank_matrix_equiv(r):
    """
    通过等价定义生成排列矩阵 M_r^{(2)}
    """
    N = len(r)
    # 计算 A_r 矩阵: |r_i - r_j|
    A_r = np.abs(r.reshape(-1, 1) - r.reshape(1, -1))  # Shape: (N, N)
    # print(A_r)
    # 生成全1向量 I
    I = np.ones(N)

    Mr = np.zeros((N, N), dtype=int)

    for k in range(1, N + 1):
        # 计算 (N +1 - 2k)*r
        term1 = (N + 1 - 2 * k) * r
        # 计算 A_r @ I
        term2 = A_r @ I
        # 计算 c_k
        c_k = term1 - term2
        # 找到 argmax(c_k)
        # 如果有多个最大值，argmax 返回第一个
        i_max = np.argmax(c_k)
        Mr[k - 1, i_max] = 1
    return Mr

def verify_equivalence(r):
    Mr_original = generate_rank_matrix_original(r)
    Mr_equiv = generate_rank_matrix_equiv(r)
    print("Rank Score Vector r:")
    print(r)
    print("\n排列矩阵 M_r^{(1)} (原始定义):")
    print(Mr_original)
    print("\n排列矩阵 M_r^{(2)} (等价定义):")
    print(Mr_equiv)
    print("\n是否相同:", np.array_equal(Mr_original, Mr_equiv))
    print("-" * 50)

def main():
    np.random.seed(42)  # 为了结果可重复

    # # 测试案例1: 简单的已排序向量
    # r1 = np.array([5, 4, 3, 2, 1])
    # verify_equivalence(r1)

    # 测试案例2: 随机向量
    # r2 = np.random.rand(10)
    # verify_equivalence(r2)
    #
    # # 测试案例4: 含有负数的向量
    # r4 = np.array([3, -1, 4, -5, 2])
    # verify_equivalence(r4)

if __name__ == "__main__":
    main()

测试结果

Rank Score Vector r:
[ 3 -1  4 -5  2]

排列矩阵 M_r^{(1)} (原始定义):
[[0 0 1 0 0]
[1 0 0 0 0]
[0 0 0 0 1]
[0 1 0 0 0]
[0 0 0 1 0]]

排列矩阵 M_r^{(2)} (等价定义):
[[0 0 1 0 0]
[1 0 0 0 0]
[0 0 0 0 1]
[0 1 0 0 0]
[0 0 0 1 0]]

是否相同: True

说明两者确实等价