ktt算法 约化_推荐系统的多目标优化(4)-PE-LTR
目錄：
[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,
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 完整代碼
通過簡單實驗，發現帕累托最優容易在迭代過程中收斂到閾值，如果不設置閾值，則容易最后優化一個單獨的任務。
總結
以上是生活随笔為你收集整理的ktt算法 约化_推荐系统的多目标优化(4)-PE-LTR的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： linux同名文件夹覆盖_第一天：Lin
- 下一篇： padding和卷积的区别_池化、池化与