推荐系统的多目标优化(4)-PE-LTR

A Pareto-Eficient Algorithm for Multiple Objective Optimization in E-Commerce Recommendation

Posted by weber on May 4, 2020

论文:A Pareto-Efficient Algorithm for Multiple Objective Optimization in E-Commerce Recommendation,RecSys,2019,阿里

目录: [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 算法描述

  1. 定义多目标问题的目标函数:

    其中,$ L_i(\theta)$ 为单目标的损失函数,$w_i$ 为该目标的权值,满足$\sum_{i=1}^Kw_i=1,w_i \geq c_i$。

  2. 用SGD更新参数$\theta$ :

  3. 通过 PECsolver算法 更新 k 个 $w_i$,算法如下;

    • 定义帕累托最优条件(Pareto Efficient Condition):

  • 将$w_i=\hat w_i+c_i$代入,得到等价的松弛问题:

  • 通过 求解定理 (后面推导中给出) 和投影,得到非负最小二乘问题:

  • 通过求解最小二乘问题,得到所有 $w_i$ 的值。

  1. 聚合得到损失:

2.2 基于KTT的求解定理推导

上文中的公式

可以改写为:

拉格朗日函数:

偏导数为0,得:

可以改写为:

得解:

3. 实验结果

3.1 实验数据

开源了一个数据集:EC-REC,包含展现、点击、购买三种标签,700w条。

3.2 实验结果

image-20200601174959409

对照方法:

  • 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,
    https://stackoverflow.com/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 完整代码

通过简单实验,发现帕累托最优容易在迭代过程中收敛到阈值,如果不设置阈值,则容易最后优化一个单独的任务。

完整代码在:github.com/weberrr/PE-LTR