目录：
[toc]
1. 提出背景
电商场景下，需要同时优化GMV和CTR，但这两个优化目标并不是严格相关的，甚至是冲突的。当CTR/GMV最优时，另一个可能是次优甚至是不好的。
因此，该问题可以看作是寻找帕累托最优的问题来处理。现有的帕累托优化方法有两种，一种是启发式搜索(heuristic search)，缺点是不能保证帕累托最优；另一种是标量化方法(scalarization)，缺点是需要手动指定权重。
帕累托最优(Pareto Optimum)：也称为帕累托效率(Pareto Efficiency)。形象解释的话，在该状态下，“从此以后，非损人不能利己”。
作者在KKT条件下提出PE-LTR(Pareto-Efficient Learning to Rank)，有LTR过程优化多个目标。
2. PE-LTR
该算法偏向于理论证明，本节先对算法整体步骤进行描述，然后对其中的关键步骤进行推导。
2.1 算法描述
定义多目标问题的目标函数：
其中，$ L_i(\theta)$ 为单目标的损失函数，$w_i$ 为该目标的权值，满足$\sum_{i=1}^Kw_i=1,w_i \geq c_i$。
用SGD更新参数$\theta$ ：
通过 PECsolver算法 更新 k 个 $w_i$，算法如下；
定义帕累托最优条件(Pareto Efficient Condition)：
将$w_i=\hat w_i+c_i$代入，得到等价的松弛问题：
通过 求解定理 (后面推导中给出) 和投影，得到非负最小二乘问题：
通过求解最小二乘问题，得到所有 $w_i$ 的值。
聚合得到损失：
2.2 基于KTT的求解定理推导
上文中的公式
可以改写为：
拉格朗日函数：
偏导数为0，得：
可以改写为：
得解：
3. 实验结果
3.1 实验数据
开源了一个数据集：EC-REC，包含展现、点击、购买三种标签，700w条。
3.2 实验结果
对照方法：
LambdaMART：一种LTR方法，实验中只考虑点击来排序，不考虑购买。
LETORIF ：最大化 GMV 的LTR方法，采用 price*CTR*CVR 进行排序， CTR 和 CVR 由两个单独模型预测。
MTL-REC ：即ESMM，排序模型也是 price*CTR*CVR，底层emb共享。
CXR-RL ：使用强化学习技术来优化 CXR(CTR和CVR的组合)，从而实现 CTR 和 CVR 之间的平衡。
PO-EA ：一种多目标优化方法，用演化算法生成权重，寻找帕累托有效的解。
PO-EA-CTR ，PO-EA-GMV： 由 PO-EA 生成的两个解决方案，分别针对 CTR 和 GMV。
PE-LTR-CTR，PE-LTR-GMV： 由 PE-LTR 生成的两个解决方案，分别针对 CTR 和 GMV。
评价指标：
用NDCG，MAP评估CTR；
用改造的G-NDCG，G-MAP评估GMV；
实验结果：
在低CTR损失下，最优化了GMV，整体效果最佳；
相较于ESMM，PE-LTR用一个模型联合学习点击和购买，而ESMM用两个模型来学习点击和购买，后者可能会导致不一致性；
4. 代码复现
帕累托最优本身等价于对任务赋予合理的权值，不改变模型。单加权取得两位数的指标收益，有些夸张，不确定是否存在计算陷阱问题；所以对原文进行复现。
4.1 求解定理实现
输入：权值w，阈值c，梯度矩阵G
说明：完成论文中附录定理的求解，得到 hat_w
def pareto_step(w, c, G):
"""
ref:http://ofey.me/papers/Pareto.pdf
K : the number of task
M : the dim of NN's params
:param W: # (K,1)
:param C: # (K,1)
:param G: # (K,M)
:return:
"""
GGT = np.matmul(G, np.transpose(G)) # (K, K)
e = np.mat(np.ones(np.shape(w))) # (K, 1)
m_up = np.hstack((GGT, e)) # (K, K+1)
m_down = np.hstack((np.transpose(e), np.mat(np.zeros((1, 1))))) # (1, K+1)
M = np.vstack((m_up, m_down)) # (K+1, K+1)
z = np.vstack((-np.matmul(GGT, c), 1 - np.sum(c))) # (K+1, 1)
hat_w = np.matmul(np.matmul(np.linalg.inv(np.matmul(np.transpose(M), M)), M), z) # (K+1, 1)
hat_w = hat_w[:-1] # (K, 1)
hat_w = np.reshape(np.array(hat_w), (hat_w.shape[0],)) # (K,)
c = np.reshape(np.array(c), (c.shape[0],)) # (K,)
new_w = ASM(hat_w, c)
return new_w
4.2 有效集求解非负最小二乘
输入：求得的解hat_w，阈值c
说明：根据ASM和阈值的约束，求解得到满足条件的 new_w
from scipy.optimize import minimize
from scipy.optimize import nnls
def ASM(hat_w, c):
"""
ref:
http://ofey.me/papers/Pareto.pdf,
/questions/33385898/how-to-include-constraint-to-scipy-nnls-function-solution-so-that-it-sums-to-1
:param hat_w: # (K,)
:param c: # (K,)
:return:
"""
A = np.array([[0 if i != j else 1 for i in range(len(c))] for j in range(len(c))])
b = hat_w
x0, _ = nnls(A, b)
def _fn(x, A, b):
return np.linalg.norm(A.dot(x) - b)
cons = {'type': 'eq', 'fun': lambda x: np.sum(x) + np.sum(c) - 1}
bounds = [[0., None] for _ in range(len(hat_w))]
min_out = minimize(_fn, x0, args=(A, b), method='SLSQP', bounds=bounds, constraints=cons)
new_w = min_out.x + c
return new_w
4.3 完整代码
通过简单实验，发现帕累托最优容易在迭代过程中收敛到阈值，如果不设置阈值，则容易最后优化一个单独的任务。
如果觉得《ktt算法 约化_推荐系统的多目标优化(4)-PE-LTR》对你有帮助，请点赞、收藏，并留下你的观点哦！
