WNJXYKの博客

本文利用 Pareto Efficiency 的相关技术应用到推荐系统中，来解决推荐系统中不同优化指标不一致的问题，最终能够求得一个 Pareto Frontier 供用户选择想要的指标性能组合。

Pareto Frontier

相关定义

问题定义：
给定一个系统，期望最小化一系列目标函数：\(f_1, f_2,\ldots,f_K\)。

定义 1：Pareto Dominated
给定两个解 \(s_{i}=\left(f_{1}^{i}, \ldots, f_{K}^{i}\right)\) 与 \(s_{j}=\left(f_{1}^{j}, \ldots, f_{K}^{j}\right)\)，我们称 \(s_i\) 能够支配 \(s_j\) 当且仅当 \(\bigcap_{k=1}^K f_k^j \leq f_k^i\) 条件满足。

定义 2: Pareto Efficient
如果一组解 \(s_{i}=\left(f_{1}^{i}, \ldots, f_{K}^{i}\right)\) 是帕累托高效的，当且仅当不存在另一组解 \(s_{j}=\left(f_{1}^{j}, \ldots, f_{K}^{j}\right)\) 能够支配 \(s_i\)。

定义 2: Pareto Frontier
满足帕累托高效的解并不惟一，因此，由满足帕累托高效条件的解组成的集合被称为帕累托前沿。

Pareto Efficient 的优化方法

求解 Pareto Efficient 解的方式存在多种，例如：演化算法、标量化技术。

本文使用可以优化的标量化技术，即，利用不同的权重 \(w_i\) 将不同的优化损失 \(\mathcal{L}_{i}(\theta), \forall i \in\{1, \ldots, K\}\) 加权成为一个汇总损失进行优化：

\[\mathcal{L}(\boldsymbol{\theta})=\sum_{i=1}^{K} \omega_{i} \mathcal{L}_{i}(\boldsymbol{\theta})
\]

其中，\(\sum_{i=1}^{K} \omega_{i}=1 \text { and } \omega_{i} \geq 0, \forall i \in\{1, \ldots, K\}\)。

可以证明在满足某些条件且权重 \(\omega_{i}\) 设置合理时，基于汇总损失优化得到的模型是帕累托高效的。因此，求得一组合理的权重 \(\omega_{i}\)，是多目标优化任务的关键。

进一步，我们可以对于优化任务中 \(\omega_{i}\) 的范围进行限制，来描述用户期望的帕累托高效解。例如：利用一组权重 \(c_i\) 来设置不同优化目标的重要性下限，即，使权重满足要求 \(\omega_{i} \geq c_{i}, \forall i \in\{1, \ldots, K\}\) 且 \(\forall i \in\{1, \ldots, K\}, 0\leq c_i\leq 1\) 且 \( \sum_{i=1}^K c_i \leq 1\)。

Pareto Efficient 条件

当模型参数 \(\theta\) 汇总损失函数满足 KKT 条件时：

\[\sum_{i=1}^{K} \omega_{i}=1, \quad \exists \omega_{i} \geq c_{i}, \quad i \in\{1, \ldots, K\} \text { and } \sum_{i=1}^{K} \omega_{i} \nabla_{\theta} \mathcal{L}_{i}(\theta)=0
\]

我们称这样的解为 Pareto Stationary，即，帕累托驻点。因此，可以形成如下的优化问题：

\[\begin{aligned}
\min & \sum_{i=1}^{K} \omega_{i} \|\nabla_{\boldsymbol{\theta}} \mathcal{L}_{i}(\boldsymbol{\theta})\|_{2}^{2} \\
\text { s.t. } & \sum_{i=1}^{K} \omega_{i}=1, \omega_{i} \geq c_{i}, \forall i \in\{1, \ldots, K\}
\end{aligned}
\]

如文章 Ozan Sener, Vladlen Koltun:Multi-Task Learning as Multi-Objective Optimization. NeurIPS 2018: 525-536 所述，在满足 KKT 条件与某些较为实际的条件时，帕累托驻点也可以成为帕累托高效解。

Pareto Efficient

基于上述条件，本文提出了通用的 Pareto Efficient 求解算法。

也就是首先将 \(\omega_i\) 设置为均匀分布，然后迭代地利用 \(\omega_i\) 优化模型参数 \(\theta\) 并根据模型参数进一步求解 \(\omega_i\)。

其中，PECsolver，也就是通过参数求解 \(\omega_i\) 的过程形成一个二次规划问题：

\[\begin{aligned}
\min &\left\|\sum_{i=1}^{K}\left(\hat{\omega}_{i}+c_{i}\right) \nabla_{\boldsymbol{\theta}} \mathcal{L}_{i}(\boldsymbol{\theta})\right\|_{2}^{2} \\
\text { s.t. } &\sum_{i=1}^{K} \hat{\omega}_{i}=1-\sum_{i=1}^{K} c_{i}, \hat{\omega}_{i} \geq 0, \forall i \in\{1, \ldots, K\}
\end{aligned}
\]

在本文中，先通过求解无约束的问题：

\[\min .\left\|\sum_{i=1}^{K}\left(\hat{\omega}_{i}+c_{i}\right) \nabla_{\boldsymbol{\theta}} \mathcal{L}_{i}(\theta)\right\|_{2}^{2} \text { s.t. } \sum_{i=1}^{K} \hat{\omega}_{i}=1-\sum_{i=1}^{K} c_{i}
\]

原文中给出了这个无约束的规划问题的闭式解：

再将其通过投影的方式投影回参数空间中：

\[\min .\left\|\tilde{\omega}-\hat{\omega}^{*}\right\|_{2}^{2} \text { s.t. } \sum_{i=1}^{K} \tilde{\omega}_{i}=1, \tilde{\omega}_{i} \geq 0, \forall i \in\{1, \ldots, K\}
\]

推荐系统中的使用方法

在推荐系统中 CTR 与 GMV 是两个相关性不强的评价指标，因此，形成了一个多目标优化任务。本文首先使用上述求解此多目标问题的 Pareto Frontier，然后，再根据用户的需求从前沿中选择一组合适的参数 \(\omega_i\) 形成汇总目表式对问题进行优化。