精华内容
下载资源
问答
  • 优化算法通用框架

    2019-04-14 21:46:02
    深度学习优化算法经历了 SGD -> SGDM -> NAG ->AdaGrad -> AdaDelta -> Adam ->...1.优化算法通用框架 首先定义:待优化参数:w ,目标函数: f(w),初始学习率α。而后,开始进行...

    https://mp.weixin.qq.com/s/xm4MuZm-6nKTn2eE3eNOlg

    深度学习优化算法经历了 SGD -> SGDM -> NAG ->AdaGrad -> AdaDelta -> Adam -> Nadam这样的发展历程。

    1.优化算法通用框架

    首先定义:待优化参数:w ,目标函数: f(w),初始学习率 α。而后,开始进行迭代优化。在每个epoch t:

    1. 计算目标函数关于当前参数的梯度: 

     

     2. 根据历史梯度计算一阶动量和二阶动量:

    度量历史参数更新频率,恒大于0的,而且参数更新越频繁,二阶动量越大,学习率就越小。

     3. 计算当前时刻的下降梯度: 

    4. 根据下降梯度进行更新:  

     

    掌握了这个框架,你可以轻轻松松设计自己的优化算法。

    我们拿着这个框架,来照一照各种玄乎其玄的优化算法的真身。步骤3、4对于各个算法都是一致的,主要的差别就体现在1和2上。

    用该框架来梳理所有的优化算法: 

    2.固定学习率的优化算法

    SGD

    先来看SGD。SGD没有动量的概念,也就是说:

    代入步骤3,可以看到下降梯度就是最简单的

    SGD最大的缺点是下降速度慢,而且可能会在沟壑的两边持续震荡,停留在一个局部最优点。

    SGD with Momentum

    为了抑制SGD的震荡,SGDM认为梯度下降过程可以加入惯性。下坡的时候,如果发现是陡坡,那就利用惯性跑的快一些。SGDM全称是SGD with momentum,在SGD基础上引入了一阶动量:

    一阶动量是各个时刻梯度方向的指数移动平均值,约等于最近 1/(1-β1) 个时刻的梯度向量和的平均值。

    也就是说,t 时刻的下降方向,不仅由当前点的梯度方向决定,而且由此前累积的下降方向决定。β1的经验值为0.9,这就意味着下降方向主要是此前累积的下降方向,并略微偏向当前时刻的下降方向。想象高速公路上汽车转弯,在高速向前的同时略微偏向,急转弯可是要出事的。

    SGD with Nesterov Acceleration

    SGD 还有一个问题是困在局部最优的沟壑里面震荡。想象一下你走到一个盆地,四周都是略高的小山,你觉得没有下坡的方向,那就只能待在这里了。可是如果你爬上高地,就会发现外面的世界还很广阔。因此,我们不能停留在当前位置去观察未来的方向,而要向前一步、多看一步、看远一些。

    (source: http://cs231n.github.io/neural-networks-3)

    这一方法也称为NAG,即 Nesterov Accelerated Gradient,是在SGD、SGD-M 的基础上的进一步改进,改进点在于步骤 1。我们知道在时刻 t 的主要下降方向是由累积动量决定的,自己的梯度方向说了也不算,那与其看当前梯度方向,不如先看看如果跟着累积动量走了一步,那个时候再怎么走。因此,NAG在步骤 1,不计算当前位置的梯度方向,而是计算如果按照累积动量走了一步,那个时候的下降方向: 

    然后用下一个点的梯度方向,与历史累积动量相结合,计算步骤 2 中当前时刻的累积动量。

    3 自适应学习率的优化算法

    此前我们都没有用到二阶动量。二阶动量的出现,才意味着“自适应学习率”优化算法时代的到来。SGD及其变种以同样的学习率更新每个参数,但深度神经网络往往包含大量的参数,这些参数并不是总会用得到(想想大规模的embedding)。

    对于经常更新的参数,我们已经积累了大量关于它的知识,不希望被单个样本影响太大,希望学习速率慢一些;对于偶尔更新的参数,我们了解的信息太少,希望能从每个偶然出现的样本身上多学一些,即学习速率大一些。

    AdaGrad

    怎么样去度量历史更新频率呢?那就是二阶动量——该维度上,迄今为止所有梯度值的平方和:

    我们再回顾一下步骤3中的下降梯度:

    可以看出,此时实质上的学习率由变成了。 一般为了避免分母为0,会在分母上加一个小的平滑项。因此是恒大于0的,而且参数更新越频繁,二阶动量越大,学习率就越小。

    这一方法在稀疏数据场景下表现非常好。但也存在一些问题:因为单调递增的,会使得学习率单调递减至0,可能会使得训练过程提前结束,即便后续还有数据也无法学到必要的知识。

    AdaDelta / RMSProp

    由于AdaGrad单调递减的学习率变化过于激进,我们考虑一个改变二阶动量计算方法的策略:不累积全部历史梯度,而只关注过去一段时间窗口的下降梯度。这也就是AdaDelta名称中Delta的来历。

    修改的思路很简单。前面我们讲到,指数移动平均值大约就是过去一段时间的平均值,因此我们用这一方法来计算二阶累积动量:

    这就避免了二阶动量持续累积、导致训练过程提前结束的问题了。

    Adam

    谈到这里,Adam和Nadam的出现就很自然而然了——它们是前述方法的集大成者。我们看到,SGD-M在SGD基础上增加了一阶动量,AdaGrad和AdaDelta在SGD基础上增加了二阶动量。把一阶动量和二阶动量都用起来,就是Adam了——Adaptive + Momentum。

    SGD的一阶动量:

    加上AdaDelta的二阶动量:

    优化算法里最常见的两个超参数就都在这里了,前者控制一阶动量,后者控制二阶动量。

    Nadam

    最后是Nadam。我们说Adam是集大成者,但它居然遗漏了Nesterov,这还能忍?必须给它加上——只需要按照NAG的步骤1来计算梯度:

    这就是Nesterov + Adam = Nadam了。

    说到这里,大概可以理解为什么说 Adam / Nadam 目前最主流、最好用的算法了。无脑用Adam/Nadam,收敛速度嗖嗖滴,效果也是杠杠滴。

    那为什么Adam还老招人黑,被学术界一顿鄙夷?难道只是为了发paper灌水吗?

    (二)Adam的两宗罪

    “一代又一代的研究者们为了我们能炼(xun)好(hao)金(mo)丹(xing)可谓是煞费苦心。从理论上看,一代更比一代完善,Adam/Nadam已经登峰造极了,为什么大家还是不忘初心SGD呢?”

    以上内容中,我们用一个框架来回顾了主流的深度学习优化算法。可以看到,一代又一代的研究者们为了我们能炼(xun)好(hao)金(mo)丹(xing)可谓是煞费苦心。从理论上看,一代更比一代完善,Adam/Nadam已经登峰造极了,为什么大家还是不忘初心SGD呢?

    举个栗子。很多年以前,摄影离普罗大众非常遥远。十年前,傻瓜相机开始风靡,游客几乎人手一个。智能手机出现以后,摄影更是走进千家万户,手机随手一拍,前后两千万,照亮你的美(咦,这是什么乱七八糟的)。但是专业摄影师还是喜欢用单反,孜孜不倦地调光圈、快门、ISO、白平衡……一堆自拍党从不care的名词。技术的进步,使得傻瓜式操作就可以得到不错的效果,但是在特定的场景下,要拍出最好的效果,依然需要深入地理解光线、理解结构、理解器材。

    优化算法大抵也如此。在上一篇中,我们用同一个框架让各类算法对号入座。可以看出,大家都是殊途同归,只是相当于在SGD基础上增加了各类学习率的主动控制。如果不想做精细的调优,那么Adam显然最便于直接拿来上手。

    但这样的傻瓜式操作并不一定能够适应所有的场合。如果能够深入了解数据,研究员们可以更加自如地控制优化迭代的各类参数,实现更好的效果也并不奇怪。毕竟,精调的参数还比不过傻瓜式的SGD,无疑是在挑战顶级研究员们的炼丹经验!

    最近,不少paper开怼Adam,我们简单看看都在说什么:

    04 Adam罪状一:可能不收敛

    这篇是正在深度学习领域顶级会议之一 ICLR 2018 匿名审稿中的一篇论文《On the Convergence of Adam and Beyond》,探讨了Adam算法的收敛性,通过反例证明了Adam在某些情况下可能会不收敛。

    回忆一下上文提到的各大优化算法的学习率:

    其中,SGD没有用到二阶动量,因此学习率是恒定的(实际使用过程中会采用学习率衰减策略,因此学习率递减)。AdaGrad的二阶动量不断累积,单调递增,因此学习率是单调递减的。因此,这两类算法会使得学习率不断递减,最终收敛到0,模型也得以收敛。

    但AdaDelta和Adam则不然。二阶动量是固定时间窗口内的累积,随着时间窗口的变化,遇到的数据可能发生巨变,使得 可能会时大时小,不是单调变化。这就可能在训练后期引起学习率的震荡,导致模型无法收敛。

    这篇文章也给出了一个修正的方法。由于Adam中的学习率主要是由二阶动量控制的,为了保证算法的收敛,可以对二阶动量的变化进行控制,避免上下波动。

    通过这样修改,就保证了 

     从而使得学习率单调递减。

    05 Adam罪状二:可能错过全局最优解

    深度神经网络往往包含大量的参数,在这样一个维度极高的空间内,非凸的目标函数往往起起伏伏,拥有无数个高地和洼地。有的是高峰,通过引入动量可能很容易越过;但有些是高原,可能探索很多次都出不来,于是停止了训练。

    之前,Arxiv上的两篇文章谈到这个问题。

    第一篇就是前文提到的吐槽Adam最狠的UC Berkeley的文章《The Marginal Value of Adaptive Gradient Methods in Machine Learning》。文中说到,同样的一个优化问题,不同的优化算法可能会找到不同的答案,但自适应学习率的算法往往找到非常差的答案(very poor solution)。他们设计了一个特定的数据例子,自适应学习率算法可能会对前期出现的特征过拟合,后期才出现的特征很难纠正前期的拟合效果。但这个文章给的例子很极端,在实际情况中未必会出现。

    另外一篇是《Improving Generalization Performance by Switching from Adam to SGD》,进行了实验验证。他们CIFAR-10数据集上进行测试,Adam的收敛速度比SGD要快,但最终收敛的结果并没有SGD好。他们进一步实验发现,主要是后期Adam的学习率太低,影响了有效的收敛。他们试着对Adam的学习率的下界进行控制,发现效果好了很多。

    于是他们提出了一个用来改进Adam的方法:前期用Adam,享受Adam快速收敛的优势;后期切换到SGD,慢慢寻找最优解。这一方法以前也被研究者们用到,不过主要是根据经验来选择切换的时机和切换后的学习率。这篇文章把这一切换过程傻瓜化,给出了切换SGD的时机选择方法,以及学习率的计算方法,效果看起来也不错。

    这个算法挺有趣,下一篇我们可以来谈谈,这里先贴个算法框架图:

    06 到底该用Adam还是SGD?

    所以,谈到现在,到底Adam好还是SGD好?这可能是很难一句话说清楚的事情。去看学术会议中的各种paper,用SGD的很多,Adam的也不少,还有很多偏爱AdaGrad或者AdaDelta。可能研究员把每个算法都试了一遍,哪个出来的效果好就用哪个了。毕竟paper的重点是突出自己某方面的贡献,其他方面当然是无所不用其极,怎么能输在细节上呢?

    而从这几篇怒怼Adam的paper来看,多数都构造了一些比较极端的例子来演示了Adam失效的可能性。这些例子一般过于极端,实际情况中可能未必会这样,但这提醒了我们,理解数据对于设计算法的必要性。优化算法的演变历史,都是基于对数据的某种假设而进行的优化,那么某种算法是否有效,就要看你的数据是否符合该算法的胃口了。

    算法固然美好,数据才是根本。

    另一方面,Adam之流虽然说已经简化了调参,但是并没有一劳永逸地解决问题,默认的参数虽然好,但也不是放之四海而皆准。因此,在充分理解数据的基础上,依然需要根据数据特性、算法特性进行充分的调参实验。

    少年,好好炼丹吧。

    (三)优化算法的选择与使用策略

    “ 在前面两篇文章中,我们用一个框架梳理了各大优化算法,并且指出了以 Adam 为代表的自适应学习率优化算法可能存在的问题。那么,在实践中我们应该如何选择呢?本文介绍 Adam + SGD 的组合策略,以及一些比较有用的 tricks.”

    07 不同算法的核心差异:下降方向

    从第一篇的框架中我们看到,不同优化算法最核心的区别,就是第三步所执行的下降方向:

    这个式子中,前半部分是实际的学习率(也即下降步长),后半部分是实际的下降方向。SGD算法的下降方向就是该位置的梯度方向的反方向,带一阶动量的SGD的下降方向则是该位置的一阶动量方向。自适应学习率类优化算法为每个参数设定了不同的学习率,在不同维度上设定不同步长,因此其下降方向是缩放过(scaled)的一阶动量方向。

    由于下降方向的不同,可能导致不同算法到达完全不同的局部最优点。《An empirical analysis of the optimization of deep network loss surfaces》 这篇论文中做了一个有趣的实验,他们把目标函数值和相应的参数形成的超平面映射到一个三维空间,这样我们可以直观地看到各个算法是如何寻找超平面上的最低点的。

    上图是论文的实验结果,横纵坐标表示降维后的特征空间,区域颜色则表示目标函数值的变化,红色是高原,蓝色是洼地。他们做的是配对儿实验,让两个算法从同一个初始化位置开始出发,然后对比优化的结果。可以看到,几乎任何两个算法都走到了不同的洼地,他们中间往往隔了一个很高的高原。这就说明,不同算法在高原的时候,选择了不同的下降方向。

    08 Adam+SGD 组合策略

    正是在每一个十字路口的选择,决定了你的归宿。如果上天能够给我一个再来一次的机会,我会对那个女孩子说:SGD!

    不同优化算法的优劣依然是未有定论的争议话题。据我在paper和各类社区看到的反馈,主流的观点认为:Adam等自适应学习率算法对于稀疏数据具有优势,且收敛速度很快;但精调参数的SGD(+Momentum)往往能够取得更好的最终结果。

    那么我们就会想到,可不可以把这两者结合起来,先用Adam快速下降,再用SGD调优,一举两得?思路简单,但里面有两个技术问题:

    1. 什么时候切换优化算法?——如果切换太晚,Adam可能已经跑到自己的盆地里去了,SGD再怎么好也跑不出来了。

    2. 切换算法以后用什么样的学习率?——Adam用的是自适应学习率,依赖的是二阶动量的累积,SGD接着训练的话,用什么样的学习率?

    上一篇中提到的论文 Improving Generalization Performance by Switching from Adam to SGD 提出了解决这两个问题的思路。

    首先来看第二个问题,切换之后的学习率。

    Adam的下降方向是

    而SGD的下降方向是

    SGD下降方向必定可以分解为Adam下降方向及其正交方向上的两个方向之和,那么其在Adam下降方向上的投影就意味着SGD在Adam算法决定的下降方向上前进的距离,而在Adam下降方向的正交方向上的投影是 SGD 在自己选择的修正方向上前进的距离。

    (图片来自原文,这里p为Adam下降方向,g为梯度方向,r为SGD的学习率。)

    如果SGD要走完Adam未走完的路,那就首先要接过Adam的大旗——沿着 方向走一步,而后在沿着其正交方向走相应的一步。

    这样我们就知道该如何确定SGD的步长(学习率)了——SGD在Adam下降方向上的正交投影,应该正好等于Adam的下降方向(含步长)。也即:

    解这个方程,我们就可以得到接续进行SGD的学习率:

    为了减少噪声影响,我们可以使用移动平均值来修正对学习率的估计:

    这里直接复用了Adam的 beta 参数。

    然后来看第一个问题,何时进行算法的切换。

    作者提出的方法很简单,那就是当 SGD的相应学习率的移动平均值基本不变的时候,即:

    每次迭代完都计算一下SGD接班人的相应学习率,如果发现基本稳定了,那就SGD以为学习率接班前进。不过,这一时机是不是最优的切换时机,作者并没有给出数学证明,只是通过实验验证了效果,切换时机还是一个很值得深入研究的话题。

    09 优化算法的常用tricks

    最后,分享一些在优化算法的选择和使用方面的一些tricks。

    1.首先,各大算法孰优孰劣并无定论。

    如果是刚入门,优先考虑 SGD+Nesterov Momentum或者Adam.(Standford 231n : The two recommended updates to use are either SGD+Nesterov Momentum or Adam)

    2. 选择你熟悉的算法——这样你可以更加熟练地利用你的经验进行调参。

    3.充分了解你的数据——如果模型是非常稀疏的,那么优先考虑自适应学习率的算法。

    4. 根据你的需求来选择——在模型设计实验过程中,要快速验证新模型的效果,可以先用Adam进行快速实验优化;在模型上线或者结果发布前,可以用精调的SGD进行模型的极致优化。

    5. 先用小数据集进行实验。有论文研究指出,随机梯度下降算法的收敛速度和数据集的大小的关系不大。(The mathematics of stochastic gradient descent are amazingly independent of the training set size. In particular, the asymptotic SGD convergence rates are independent from the sample size. [2])因此可以先用一个具有代表性的小数据集进行实验,测试一下最好的优化算法,并通过参数搜索来寻找最优的训练参数。

    6. 考虑不同算法的组合。先用Adam进行快速下降,而后再换到SGD进行充分的调优。切换策略可以参考本文介绍的方法。

    7. 数据集一定要充分的打散(shuffle)。这样在使用自适应学习率算法的时候,可以避免某些特征集中出现,而导致的有时学习过度、有时学习不足,使得下降方向出现偏差的问题。

    8. 训练过程中持续监控训练数据和验证数据上的目标函数值以及精度或者AUC等指标的变化情况。对训练数据的监控是要保证模型进行了充分的训练——下降方向正确,且学习率足够高;对验证数据的监控是为了避免出现过拟合。

    9. 制定一个合适的学习率衰减策略。可以使用定期衰减策略,比如每过多少个epoch就衰减一次;或者利用精度或者AUC等性能指标来监控,当测试集上的指标不变或者下跌时,就降低学习率。

    展开全文
  • 1、优化算法通用框架 定义; 待优化参数w,目标函数:f(w), 初始学习率αα \alpha ,开始进行迭代优化,在每个epoch t 中,一般会有四个步骤: 计算目标函数关于当前参数梯度:gt=∇f(wt)gt=∇f(wt) g_t = \...

    1、优化算法通用框架

    定义; 待优化参数w,目标函数:f(w), 初始学习率α,开始进行迭代优化,在每个epoch t 中,一般会有四个步骤:

    • 计算目标函数关于当前参数的梯度:
      gt=f(wt)
    • 根据历史梯度计算第一阶动量和第二阶动量:
      mt=ϕ(g1,g2,g3.....,gt)
      Vt=φ(g1,g2,g3.....,gt)
    • 计算当前时刻的下降梯度:
      ηt+1=αmt/Vt
    • 根据下降梯度进行更新:
      wt+1=wtηt

    2、常见的优化算法有哪些?

    优化算法一般有两类,一种是固定学习率的优化算法,另一种是自适应学习率的优化算法。
    1. 固定学习学习率的优化算法:
    SGD,SGD是没有动量的概念,也就是

    mt=gt
    Vt=I2
    带入步骤3,
    η=αgt
    SGD最大的缺点是下降速度慢,而且可能会在沟壑的两边持续震荡,停留在一个局部最优点
    SGD with Momentum: 为了抑制SGD的震荡,SGDM认为梯度下降过程可以加入惯性。下坡的时候,如果发现是陡坡,那就利用惯性跑的快一些。SGDM全称是SGD with momentum,在SGD基础上引入了一阶动量:
    mt=β1mt1+(1β1)gt

    SGD with Nesterow Acceleration (NAG): 改进点在于步骤1。我们知道在时刻t的主要下降方向是由累积动量决定的,自己的梯度方向说了也不算,那与其看当前梯度方向,不如先看看如果跟着累积动量走了一步,那个时候再怎么走。因此,NAG在步骤1,不计算当前位置的梯度方向,而是计算如果按照累积动量走了一步,那个时候的下降方向
    gt=f(wtαmt1/Vt1)
    然后用下一个点的梯度方向,与历史累积动量相结合,计算步骤2中当前时刻的累积动量。



    2. 自适应学习率的优化算法:

    • AdaGrad
      怎么去变量历史更新频率呢? 那就是二阶动量——该维度上,迄今为止所有梯度值的平方和:

      Vt=t=1ngt2
      参照框架步骤3:ηt+1=αmt/Vt可以看出,此时实质上的学习率由α变成了α/Vt。 一般为了避免分母为0,会在分母上加一个小的平滑项。因此Vt是恒大于0的,而且参数更新越频繁,二阶动量越大,学习率就越小。

      缺点:这一方法在稀疏数据场景下表现非常好。但也存在一些问题:因为是单调递增的,会使得学习率单调递减至0,可能会使得训练过程提前结束,即便后续还有数据也无法学到必要的知识。

    • AdaDelta / RMsProp
      由于AdaGrad单调递减的学习率变化过于激进,我们考虑一个改变二阶动量计算方法的策略:不累积全部历史梯度,而只关注过去一段时间窗口的下降梯度。这也就是AdaDelta名称中Delta的来历。
      修改的思路很简单。前面我们讲到,指数移动平均值大约就是过去一段时间的平均值,因此我们用这一方法来计算二阶累积动量:

      Vt=β2Vt1+(1β2)gt2

      避免了二阶动量持续累积,导致训练过程提前结束的问题。

    • Adam
      SGD-M在SGD基础上增加了一阶动量,AdaGrad和AdaDelta在SGD基础上增加了二阶动量。把一阶动量和二阶动量都用起来,就是Adam了——Adaptive + Momentum。
      SGD的一阶动量:mt=β1mt1+(1β1)gt
      加上AdaDelta的二阶动量:Vt=β2Vt1+(1β2)gt2
      β1β2是优化算法里常见的两个超参数,前者控制一阶动量,后者控制二阶动量。实际过程:β1=0.9β2=0.999,初始化过程中m0=0,V0=0
      这个时候我们看到,在初期,都会接近于0,这个估计是有问题的。因此我们常常根据下式进行误差修正:

      mt^=mt/(1β1t)
      Vt^=Vt/(1β2t)

    • Nadam
      改进步骤一:gt=f(wtα/Vt)
      Nesterov + Adam = Nadam,经常有人说 Adam / Nadam 目前最主流、最好用的优化算法了

    3、优化算法常用的调参技巧

    首先,各大算法孰优孰劣并无定论。如果是刚入门,优先考虑 SGD+Nesterov Momentum或者Adam.(Standford 231n : The two recommended updates to use are either SGD+Nesterov Momentum or Adam)

    • 选择你熟悉的算法——这样你可以更加熟练地利用你的经验进行调参。
    • 充分了解你的数据——如果模型是非常稀疏的,那么优先考虑自适应学习率的算法。
    • 根据你的需求来选择——在模型设计实验过程中,要快速验证新模型的效果,可以先用Adam进行快速实验优化;在模型上线或者结果发布前,可以用精调的SGD进行模型的极致优化。
    • 先用小数据集进行实验。有论文研究指出,随机梯度下降算法的收敛速度和数据集的大小的关系不大。(The mathematics of stochastic gradient descent are amazingly independent of the training set size. In particular, the asymptotic SGD convergence rates are independent from the sample size. [2])因此可以先用一个具有代表性的小数据集进行实验,测试一下最好的优化算法,并通过参数搜索来寻找最优的训练参数。
    • 考虑不同算法的组合。先用Adam进行快速下降,而后再换到SGD进行充分的调优。切换策略可以参考本文介绍的方法。
    • 数据集一定要充分的打散(shuffle)。这样在使用自适应学习率算法的时候,可以避免某些特征集中出现,而导致的有时学习过度、有时学习不足,使得下降方向出现偏差的问题。
    • 训练过程中持续监控训练数据和验证数据上的目标函数值以及精度或者AUC等指标的变化情况。对训练数据的监控是要保证模型进行了充分的训练——下降方向正确,且学习率足够高;对验证数据的监控是为了避免出现过拟合。
    • 制定一个合适的学习率衰减策略。可以使用定期衰减策略,比如每过多少个epoch就衰减一次;或者利用精度或者AUC等性能指标来监控,当测试集上的指标不变或者下跌时,就降低学习率。
    • 对于稀疏数据,尽量使用学习率可自适应的优化方法,不用手动调节,而且最好采用默认值
    • SGD通常训练时间更长,但是在好的初始化和学习率调度方案的情况下,结果更可靠
    • 如果在意更快的收敛,并且需要训练较深较复杂的网络时,推荐使用学习率自适应的优化方法。

    来自知乎专栏:机器学习炼丹记
    作者:Juliuszh
    参考文献:
    [1] Stanford CS231n Convolutional Neural Networks for Visual Recognition
    [2] Stochastic Gradient Descent Tricks.
    [3] Efficient BackProp

    展开全文
  • 为了提高多目标优化算法的求解性能,提出一种启发式的基于种群的全局搜索与局部搜索相结合的多目标进化算法混合框架.该框架采用模块化、系统化的设计思想,不同模块可以采用不同策略构成不同的算法.采用经典的改进非...
  • 算法优化的思考框架

    2019-03-08 19:30:04
    芯片和指令集层面 特定芯片SDK,例如,PowerSDK neon指令集(32 bit/64 bit) 操作系统层面 CPU亲和操作(set_affinity) 线程调度方案设计,例如,锁作用域精准设置 ...算法设计层面 ...
    1. 芯片和指令集层面
    • 特定芯片的SDK,例如,PowerSDK
    • neon指令集(32 bit/64 bit)
    1. 操作系统层面
    • CPU亲和操作(set_affinity)
    • 线程调度方案设计,例如,锁的作用域的精准设置
    1. 第三方依赖库层面
    • 库编译选项,例如
      • OpenCV的neon编译设置
      • g2o的OpenMP编译设置
      • Eigen的并行编译设置
    1. 算法设计层面
    展开全文
  • AI 前线导读: 在推荐系统中,多目标优化一直是热门话题,阿里针对推荐中多目标优化问题提出了一种基于帕累托效率的优化算法框架,并应用在电商推荐场景中,对 GMV 和 CTR 多个目标同时优化,线上实验效果好于 ...
    c66dd055b61e88ad239544c20b1aa28f.png 论文作者| Xiao Lin,Hongjie Chen 等 编译 | 吴少杰 编辑 | Natalie AI 前线导读: 在推荐系统中,多目标优化一直是热门话题,阿里针对推荐中的多目标优化问题提出了一种基于帕累托效率的优化算法框架,并应用在电商推荐场景中,对 GMV 和 CTR 多个目标同时优化,线上实验效果好于 LambdaMART 以及基于强化学习的 CXR-RL 等算法。该论文已经被 RecSys 2019 会议录用, 本文是 AI 前线第 96 篇论文导读,我们将对这项研究工作进行详细解读。更多优质内容请关注微信公众号“AI 前线”(ID:ai-front) 介    绍

    推荐系统在电商平台中扮演着至关重要的角色,推荐算法(例如,Learning To Rank )会为用户生成个性化的推荐列表,可以防止用户信息过载。通常,算法需要精心设计来满足多个目标。然而,同时优化多个目标非常困难,其核心难点在于不同目标之间经常存在冲突。在电商推荐中,点击率(CTR)和成交总额(GMV)是两个并不完全一致但都很重要的目标。为了验证这种不一致性,我们从一个真实的电商平台收集了一周的在线数据,并绘制了当 CTR 上升时 GMV 的变化趋势图。根据图 1,CTR 与 GMV 的趋势变化不完全一致,当 CTR 最优或 GMV 最优时,另一个目标可能是次优的,甚至是不好的。

    因此,如果一个解被认为是两个目标的最优解,那么意味着其中一个目标在不伤害另一个目标的情况下很难进一步改进。这种最优性在多目标优化中得到了广泛的认可,被称为帕累托效率或帕累托最优性。在帕累托效率的情况下,只有当解 A 在所有目标上都优于解 B 时,解 A 才被认为优于解 B。帕累托效率的目标是在不受其他目标支配的情况下找到最优解。

    50e0461ac9c9d93998a841b2b7429d8b.png

    现有的帕累托优化方法分两类:启发式搜索和标量化。演化算法是启发式搜索方法中最热门的。然而,启发式搜索并不能保证帕累托有效性,它只能保证得到的解不被对方支配(但仍然可以被帕累托有效解支配)。与启发式搜索方法不同,标量化方法是通过目标函数的加权和将多目标问题转化为单目标问题。然后通过合适的标量,优化重构的目标函数来获得帕累托有效解。目标函数的标量化权重通常是手动确定的,因此帕累托有效性仍然无法保证。总而言之,现有的演化算法和标量化算法难以保证帕累托有效解。最近,Karush Kuhn Tucker(KKT)条件被证明可用于指导标量化。我们尝试在 KKT 条件下构建算法,并提出了一种新的算法框架,在理论保证的前提下,生产标量化的权重。

    具体地说,我们提出了一个帕累托有效的算法框架“PE-LTR”,它用 LTR 过程优化多个目标。为了给每个用户生成候选的 item,考虑到多目标,PE -LTR 对候选 item 进行排序,使得这种排序是帕累托有效的。假设每一个目标都存在相应的可微公式,我们采用标量化技术将不同的目标协同成一个单目标函数。如前所述,除非仔细选择权重,否则标量化技术不能保证帕累托有效性。因此,我们提出了一个标量化权值的条件,保证该解是帕累托有效的。该条件等价于一个约束优化问题,并且我们提出了一个算法,它可以通过两步解决该问题。首先通过放宽约束来简化问题,从而得到解析解,然后通过实施投影过程(projection procedure)得到可行解。以 PE-LTR 为基础,依据服务提供者的需求,我们提供方法来生成帕累托边界(Pareto Frontier)和特定的推荐。为了生成帕累托边界,通过均匀设置目标标量权重的边界来运行“PE-LTR”算法框架。为了生成特定的推荐,可以使用适当的边界运行一次 PE-LTR,或者首先生成帕累托边界,然后在特定的公平性度量下选择一个“合适”的解。

    在本文中,应用该框架来优化电商推荐的两个重要目标,即 GMV 和 CTR。对于电商平台,主要目标是提升 GMV,但 CTR 需要做出很大的牺牲很大,从长远来看,会使平台的活跃用户(DAU)减少。因此,我们的目标是在同时考虑这两个目标的前提下,找到帕累托有效解。我们分别为 GMV 和 CTR 提出了两个可微分公式,并应用 PE-LTR 框架来生成帕累托最优解。我们在一个真实的电商推荐系统上进行了大量的实验,并将结果与最新的最佳的方法进行了比较。在线和离线实验结果都表明,我们的解优于其他基线,并且我们的解几乎是帕累托有效的。

    这项工作的主要贡献是:

    (1)我们提出了一个通用的帕累托有效性算法框架(PE-LTR)用于多目标推荐。该框架既不依赖于模型,也不依赖于目标,显示了其强大的可伸缩性。

    (2)我们提出了一个 two-step 算法,它理论上保证了帕累托有效性。尽管该算法是建立在标量化技术之上的,但与其他的标量化方法相比,它的不同之处是有理论保证并且标量化权重是自动学习,而不是手动分配。

    (3)以 PE-LTR 为基础,提出了如何生成帕累托边界和特定的推荐。具体地说,我们建议在使用适当的公平度量下从帕累托边界中选择一个合适的推荐。

    (4)我们使用电商推荐作为 PE-LTR 的一个特例,并在一个真实的推荐系统上进行了广泛的在线和离线实验。结果表明,我们的算法优于其他最先进的方法,所产生的解是帕累托有效的。

    (5)我们开源了一个大规模的电商推荐数据集 EC-REC,其中包含展现、点击和购买的真实记录。据我们所知,没有一个公共数据集同时包含三个标签和足够多的特征,这个数据集可以用于进一步的研究。

    提出的框架

    在这一部分中,我们首先简要介绍帕累托有效性的概念,然后具体介绍所提出框架的细节,即帕累托有效学习排序(PE-LTR)。假定多个目标对应有不同的损失函数,首先我们提出一个能保证帕累托有效解的条件,证明了该条件等价于约束二次规划问题。然后,我们又提出了一个两步算法来解决该问题。此外,我们还提供了用 PE-LTR 生成帕累托边界和特定推荐的方法。

    预备知识

    首先,简要介绍帕累托有效性的相关概念。帕累托有效性是多目标优化的一个重要概念,即给定一个系统,该系统的目标是最小化一系列目标函数 f1,...,fK,帕累托有效性是一种状态,在不损害其他多个目标的情况下,不可能再改善其中一个目标。

    定义 3.1  两个解的结果表示为 si=(fi1,...,fiK) 和 sj=(fj1,..,fjK),仅在 fi1≤fj1,fi2≤fj2,...fiK≤fjK(对于最小化目标)情况下,si 支配 sj。

    帕累托效率的概念建立在支配的定义之上:

    定义 3.2 如果没有其他的解 sj=(fj1,..,fjK) 支配 si,解 si=(fi1,...,fiK) 就是帕累托有效解。

    因此,在不损害其他目标的情况下,一个解是非帕累托有效性解,它仍可以至少在一个目标上提升,并且在多目标优化中总是可以得到帕累托有效解。值得一提的是,帕累托有效解并不是唯一的,所有这些解的集合都被称为“帕累托边界”。

    基于帕累托有效的学习排序算法

    为了实现帕累托最优解,我们提出了一种利用标量化技术优化多目标的学习排序方案。假设在给定的推荐系统中存在 k 个目标,模型 F(θ) 需要同时优化这些目标,其中θ表示模型参数。在不失一般性的情况下,我们假设对于 K 个目标存在 K 个不同的损失函数。

    给定公式,优化第 i 个目标等价于最小化 Li(θ)。然而,同时优化这 K 目标是非常复杂的,因为对于一个目标的最优解通常对于另一个目标是次优的。因此,我们使用标量化技术将多个目标合并成单个目标。确切地说,我们利用ωi 聚合损失函数:

    288b5c655ffb73e3c3371884e054284e.png

    其中,w1+w2+...+wK=1,wi≥0。在真实的场景下,目标可能有不同的优先级。在我们的案例中,我们假定约束被添加到目标中是预先定义的约束边界。例如,wi≥ci,其中 ci 是一个在 0-1 之间的常量,c1+c2+...ci+..+cK≤1。

    尽管只有一个目标公式,除非分配适当的权重,否则不能保证问题的解是帕累托有效的。但是,我们得到的标量化权重的条件,可以确保解是帕累托有效的。

    3.2.1 帕累托有效条件

    为了得到多目标的帕累托有效解,我们试图最小化聚合损失函数。模型参数的 KKT 条件 (Karush-Kuhn-Tucher 条件):

    5c1a5ea20b5c50ba0ab7cbf5e487ae2d.png

    满足此条件的解称为帕累托平稳解。该条件可转化为以下优化问题:

    92bc778d108fffde9bb64e79bc94ffbe.png

    已经证明该优化问题的解是 0,使得满足 KKT 条件,或者解能指导梯度方向来最小化所有损失函数。如果满足 KKT 条件,则解是帕累托平稳的,并且在现实和温和条件下也能做到帕累托有效性。在此条件上,我们提出了一个算法框架 PE-LTR,其细节在算法 1 中给出了说明。

    85d45b74f5b134dea839704fb0708682.png

    该框架以均匀的标量加权开始,然后交替地更新模型参数和标量权重。PE-LTR 的核心部分是 PECsolver,它通过求解问题(1)中的条件来产生标量化权值。注意,该条件是一个复杂的二次规划问题,我们给出了在算法 2 中 PECsolver 的详细过程。

    a27c7903fc04d9c1ff41f5b118d81979.png

    值得一提的是,算法框架不依赖于损失函数或模型结构的特定公式。任何带有梯度的模型和公式都可以很容易地应用到框架中。尽管算法在批处理中采用随机梯度下降法,但该算法为梯度下降的收敛提供了理论保证。

    3.2.2   二次规划算法

    将ωi^ 表示为ωi-ci,帕累托有效条件变为:

    6d07ca7c3557e3e0efbc6484d99f82d9.png

    帕累托有效条件等价于问题 1,然而,由于它的二次规划形式,解决这个问题并不是一个轻而易举的任务。因此,我们提出了一个两步算法,作为帕累托有效条件求解的工具。该算法在算法 2 中有详细说明。我们首先通过只考虑等式约束来松散问题,然后用解析解来解决松弛问题。然后,我们引入一个投影过程,从在所有约束下的可行解的集合中生成一个有效解。

    当除了等式约束,忽略所有其他约束时:

    e4f9c4990a3be63b8e5274efe2c29b98.png

    松弛问题的解由定理 3.3 给出。

    55b64f056ec72ae1e7510fc41b72b2df.png

    然而,因为省略了非负性约束,问题 3 的解ω*^ 可能是无效的。因此,我们执行以下投影步骤以获得有效的解。

    10e403fec92eacce6f5952519be91154.png

    这个问题是一个非负最小二乘问题,并且可以很容易地用有效集方法求解。由于篇幅的限制,我们省略了问题 3 算法的细节。算法 2 的复杂度主要由伪逆 (pseudo-inverse) 运算决定,它与目标数目有关。通常目标的数量是有限的,因此算法 2 的运行时间是可忽略不计的,在线实验也证实了这一点。

    帕累托边界生成与解的选择

    多目标优化可以用于寻找一个特定的帕累托解,或者被用来生成一组解来构造帕累托边界。在本节中,我们将介绍用算法 1 生成解的细节。

    帕累托边界生成

    在算法 1 中,给定不同目标的边界,我们可以得到帕累托最优解。然而,存在一些场景,我们期望有一系列的帕累托最优解存在,即帕累托边界。这对于算法框架来说很简单,我们将不同的值设置到各个目标的不同边界上执行算法 1 就可以得到。

    为了得到帕累托边界,我们执行多次算法 1,并且在每个运行中用适当的边界生成的解产生帕累托最优解。我们适当地选择边界,以便均匀分布的帕累托点可以生成一个好的均价分布近似的帕累托边界。

    解的选择

    在期望单个推荐的情况下,我们需要选择一个特定的帕累托最优解。当不同目标的优先级可用时,我们可以通过为目标设置适当的边界来获得适当的帕累托有效推荐并执行一次算法 1。

    当优先级不可用时,我们可以首先生成帕累托边界并选择一个对目标公平的解。无论是在经济学理论还是在推荐系统背景下,公平都有几种不同的定义。最直观的度量之一是 Least Misery,它集中在最“悲惨”的目标上,在我们的例子中,一个“Least Misery”的推荐是最小化目标损失函数的最大值:

    c64ff3b60724bc95e6b7a8d97b9b5187.png

    另一个常用的度量是公平边际效用,即选择一个解,其中优化一个目标的成本几乎等于其他目标的收益:

    413f2ff5cddf34b8966ddeab0e6ea445.png

    给定一个生成的帕累托边界,方程 5 或者 6 的最小值的解,被选择作为最后的推荐,这取决于公平性的选择。

    电商推荐的特殊性

    在 PE-LTR 算法框架的基础上,我们详细介绍了其在电商推荐中的具体应用。电商推荐中最重要的两个目标是 GMV 和 CTR。对于电商平台,GMV 通常是首要目标。然而,CTR 是评估用户体验的一个重要指标,长远来看影响平台的扩大。因此,我们的目标是考虑两个目标的前提下,找到一个推荐是帕累托最优的。

    考虑到在现实环境中,LTR 模型以流数据为输入,在线更新其参数。因此,在线的 LTR 模型通常遵循 point-wise 的排序方案。我们将问题描述为二元分类问题,并针对这两个目标分别设计两个不同的损失函数。

    在电商推荐系统中,用户反馈可以大致分为三种类型:展现、点击和购买。假定表示一个实例为 (xj,yj,zj),j∈ [1,...,N],给定 point-wise 的排序模型 F(θ),我们提出优化这两个目标,即 CTR 和 GMV。对于 CTR 优化,我们的目标是最小化:

    28d487fa6dbd83c3ad7b1f6d407a4b71.png

    对于 GMV 优化,我们的目标是最小化:

    04a718776222f00f56bfb483ff1744ba.png

    其中 h(price(j))是关于 price(j) 的凹单调非递减函数,price(j) 表示 xj 中 item 的价格。在我们的公式中,我们选择 h(price(j))=log(price(j))。我们假设 p(zj=1,yj=1)与模型 F(θ) 参数无关。因此,给定一个模型 F(θ) 和 Lctr(θ,x,y,z)和 Lgmv(θ,x,y,z)的表达式,电商推荐问题变成:

    1ec1ea385cc87e68dbc72a50a4aa1b5a.png

    注意,提出的框架不依赖于特定的模型结构或损失公式,只要模型有梯度,它就可以工作。因此,CTR 和 GMV 损失的计算公式不是本文的重点,而更为精心设计的计算公式可以应用到这个框架中。

    此外,我们没有关注特定的 LTR 模型,而是使用三种不同的典型模型进行比较,即 LR、DNN 和 WDL。DNN 模型是一个三层 MLP,在 wide&deep 模型中具有与深部结构相同的结构。对于所有的神经网络组件,我们选择 tanh 作为每个隐藏层的激活函数,而最后一层采用线性函数作为输出。在实验 5 中对三种不同模型进行了比较。

    实    验

    在本节中,我们将介绍实验的详细细节,旨在回答以下研究问题:

    (1)与目前最先进的以 CTR/GMV 导向的方法和多目标推荐算法相比,该框架的性能如何?

    (2)就单一推荐和帕累托边界而言,提出框架的帕累托效率如何?

    (3)从模型选择的角度来看,提出框架的可伸缩性如何?

    为了回答这些研究问题,我们在一个流行的电商网站上对真实世界的数据集进行了广泛的实验,包括在线和离线实验。

    数据集

    据我们所知,没有一个公开的电商数据集包含这些重要的特征,例如同一时间的价格、标签的展现、点击和购买。因此,我们从一个流行的电商平台收集了一个真实的数据集 EC-REC 。由于在线数据量巨大,我们收集了一周的数据,并为离线实验采集了超过 700 万个展现样本,数据集将公开,以支持未来的研究。同时,利用 PE-LTR 为用户服务,我们对在线实验进行了 A/B 测试。这些特性来自于用户画像和 item 画像,例如用户的购买力和 item 的平均购买次数。

    实验设置

    我们进行了离线和在线实验来验证所提框架的有效性,并以最先进的方法作为比较的基准。

    6.2.1 基线

    我们选择最新的推荐方法进行比较,基线可以分为三类:典型方法(CF、LambdaMART)、以 GMV 导向的方法(LETORIF、MTL-REC)和优化两个目标的方法(CXR-RL、PO-EA)。

    • ItemCF 基于 item 的协同过滤。
    • LambdaMART 是最先进的学习排序方法。一个 MART 模型用于优化 NDCG 的 loss。然而,LambdaMART 只关注点击相关性,而购买不考虑。
    • LETORIF 是最大化 GMV 的学习排序方法,并采用 price*CTR*CVR 进行排序,其中 CTR 和 CVR 是两个单独的模型进行预测。
    • MTL-REC 采用多任务学习技术对 CTR 和 CVR 模型进行训练。两个模型共享相同的用户和 item 嵌入和类似的神经网络结构。排序模型也是 price*CTR*CVR。
    • CXR-RL 是一种最近基于值感知的推荐算法,它同时优化了 CTR 和 CVR。CXR 设计为 CTR 和 CVR 的组合。CXR-RL 使用强化学习技术来优化 CXR,从而实现 CTR 和 CVR 之间的平衡。
    • PO-EA 是一种最先进的多目标推荐方法,旨在寻找帕累托有效的解。PO-EA 假定不同的基础算法在目标上具有不同的优势。它用多个初等算法给出的分数,用演化算法生成权重。基础算法包括 LETORIF-CTR、LETORIF、CXR-RL、PE-LTR-CTR 和 PE-LTR-GMV。LETORIF-CTR 是指 LETORIF 中的 CTR 模型。PE-LTR-CTR 和 PE-LTR-GMV 都是 PE-LTR 模型,在模型中加入边界约束,对 CTR 和 GMV 进行相应的优化。两个 LTR 模型被用作基础算法,以便与 PE-LTR 进行公平比较。
    • PO-EA-CTR ,PO-EA-GMV 由 PO-EA 生成的两个解决方案,分别针对 CTR 和 GMV。
    • PE-LTR-CTR,PE-LTR-GMV 由 PE-LTR 生成的两个解决方案,分别针对 CTR 和 GMV。
    6.2.2 实验设置

    我们采用了两种典型的 IR 测量方法来评估 CTR,即 NDCG 和 MAP。同时,我们为这两个指标提出了两种 GMV 变体:

    114a1b35a64491296a05831a2fbb377c.png

    其中 Q(R) 表示 item 购买集合,pay(i)=0/1 表示在第 i 次 rank 中 item 是否被购买,price'(i) 表示第 i 次 rank 中 item 的价格,G-IDCG@K 表示 G-DCG@K 中最大的可能值。G-NDCG@K 考虑了在排序列表中位置偏差的 GMV,偏好高 ranking 的 item 被购买,而 G-MAP 考虑在推荐列表中购买数量。对于用户没有购买记录的,两个度量指标的值都是 0。

    离线实验结果 6.3.1  对比基准线

    为了回答最初的研究问题,我们在表 2 中对 NDCG、MAP 和 GMV 相关度量进行了比较。

    PE-LTR 是从具有公平边际效用的帕累托边界选择模型,PO-EA 是具有在 CTR 指标方面跟 PE-LTR 可比的模型。如表所示,PE-LTR 在所有 GMV 相关指标上都优于其他方法,在 CTR 相关指标上也优于 LambdaMART。与 Item-CF 和 LambdaMART 相比,PE-LTR 可以获得更高的 G-NDCG 和 G-MAP。这是合理的,因为 PE-LTR 联合优化了 GMV 和 CTR,而 GMV 在 Item-CF 和 LambdaMART 中没有优化。同时,PE-LTR 实现了与 LambdaMART 相当的 NDCG 和 MAP。在对 Web 搜索基准中,LambdaMART 通常是性能非常好的方法。这说明了我们的框架的有效性,它不仅优化了 GMV,而且保证了高 CTR。

    74405108e4a9f2c05d48f3ff6b3de1a0.png

    与 LETORIF、MTL-REC、CXR-RL 和 PO-EA 相比,PE-LTR 可以实现更高的 G-NDCG 和 G-MAP,并且成本更低。这背后有几个原因:

    • 首先,与 LETORIF 和 MTL-REC 相比,PE-LTR 使用一个模型来联合学习两个目标,这允许模型同时学习点击和购买;而在 LETORIF 和 MTL-REC 中,两个单独的模型或组件被设计用于点击和购买,这可能导致一些不一致性。
    • 其次,与 CXR-RL 和 PO-EA 相比,PE-LTR 以帕累托有效的方式协调两个目标。CXR-RL 优化了两个目标,但以非帕累托有效的方式。同时,虽然 PO-EA 试图用寻找帕累托有效解,但它只能保证最终解是从一系列互不支配的解中选择出来的。

    在图 2 中,我们进一步绘制了 PO-EA 和 PE-LTR 的 NDCG 与 G-NDCG 曲线(由于篇幅限制,我们只在本文的图中绘制了 G-NDCG 和 NDCG,结果与 MAP 和 G-MAP 相似)。如图表所示,PO-EA 所产生的任何解都不受 PO-EA 中的另一个支配,并且情况与 PE-LTR 相同。然而,我们观察到 PE-LTR 的曲线高于 PO-EA 的曲线,这意味着 PO-EA 的解主要是由 PE-LTR 生成的解。注意两个 PE-LTR 算法已经被用作 PO-EA 的基本组成部分,比较表明,所提出的框架更能生成帕累托有效解。

    d87e98073cb22841d6b1ddc955ca5b69.png

    此外,电商平台中的真实数据可能不遵循典型的假设。在 PE-LTR 中,标量权重在每个批次中调整,能够在训练过程中动态地调整训练数据。同时,PO-EA 需要几个经过训练的算法来聚合,这使得它更难满足在线学习环境的要求。

    我们进一步比较了排名第一的推荐的质量。由于用户通常更关注排名靠前的 item,因此排名靠前的指标在推荐中更为重要,结果如图 3 所示。如图所示,PE-LTR 在 GMV 相关指标上优于其他基线,且损失 CTR 较少。这说明了帕累托效率在现实推荐系统中的重要性。单独优化一个目标可能会严重损害其他目标。因此,有必要同时考虑多个目标,帕累托效率推荐使得以较低的损失 CTR 下实现高 GMV 成为可能。

    5d981b558a71477e7f26268808811d15.png

    6.3.2  PE-LTR 的帕累托效率

    为了回答第二个研究问题,我们首先通过运行算法 1 生成 CTR 和 GMV 损失的帕累托边界,并在图 2 中绘制帕累托边界。可以看出,在不同的约束条件下,损失基本上遵循帕累托效率,即没有一个点比其他点同时达到更低的 CTR 和 GMV 损失。当模型更关注 CTR 时,CTR 损失较低,GMV 损失较高,反之亦然。这与该框架的帕累托有效标量方案相吻合。

    然后比较了不同选择策略下 PE-LTR 的解。我们预先定义了 CTR 和 GMV 的两组边界:(ω(ctr)≥0,omega(gmv)≥0.8)和(ω(ctr)≥0.8,omega(gmv)≥0.0),得到了两个分别聚焦于 GMV 和 CTR 的 PE-LTR(PE-LTR-GMV 和 PE-LTR-CTR)。然后从帕累托边界选择两个具有 LM 公平和 MU 公平的 PE-LTR(PE-LTR-LM 和 PE-LTR-MU)。我们在图 4 中绘制了这些 PE-LTR 之间的比较。

    046894a436ec437d87acc1b6936e161a.png

    PE-LTR-CTR 和 PE-LTR-GMV 与被添加到目标的约束性能是一致的。因此,当 GMV 和 CTR 的优先级可用时(即 GMV 或 CTR 优先),可以通过相应地设置边界来实现推荐。当优先级不可用时,可以通过从具有最高公平性的帕累托边界中进行选择来实现公平解决。尽管所选择的 PE-LTR(PE-LTR-LM 和 PE-LTR-MU)在所有指标上都不是最好的,但它在两个目标之间实现了相对良好的权衡。将 PE-LTR-LM 与 PE-LTR-MU 进行比较,我们认为 LM 和 MU 公平性选择的两个推荐是相对平衡的。在 GMV 中,PE-LTR-MU 优于 PE-LTR-LM,而在 CTR 中,PE-LTR-LM 稍好。

    6.3.3  PE-LTR 的可扩展性

    为了回答第三个研究问题,我们进行了实验,从模型选择方面展示了可伸缩性。我们使用 LR、DNN 和 WDL 作为 PE-LTR 框架中的模型,模型的详细内容见第 5 节。我们为模型设置了相同的边界,结果如图 5 所示。

    9f3db95edd9dd9eb57f2423d369b5841.png

    从结果来看,模型选择对 PE-LTR 的性能有重要影响。在三个 PE-LTR 变体中,PE-LTR-WDL 优于其余的,PE-LTR-DNN 优于 PE-LTR-LR。这是因为神经网络能捕获比线性模型更复杂的特征之间的关系。Wide&Deep 的模型将神经网络和线性模型结合到一个模型中,使推荐更好地泛化和记忆。因此,PE-LTR 能够适应不同的模型,更强的模型可以带来更好的性能。这也说明了 PE-LTR 的潜力,其性能可以通过更精心设计的模型进一步提高。

    在线实验结果

    我们在真实的电商平台上进行了 3 天在线实验。在线实验中,仅考虑 CTR 的方法会严重伤害 GMV。因此,只考虑 CTR 的方法不包括在在线实验中。

    在线实验中我们关注四个度量指标,即 CTR(点击率)、IPV(单个页面查看)、PAY(购买量)和 GMV(成交总额)。我们计算了三天的平均性能,结果见表 3。由于用户数量众多,结果具有统计上的显著性。我们使用 LETORIF 作为基线,并在表中给出比较方法在 LETORIF 上的提升。

    301bee931b78bf0cdfadc8ecc68b4b73.png

    从结果观察到,我们的方法在四个度量上优于其他基线。这与离线实验的结果基本吻合。请注意,PE-LTR 在较高的 CTR 下实现了 GMV 的显著提升,这说明帕累托有效推荐的优势。同时,PO-EA 要求离线模型来聚合需要,不能在线学习权重,使实验效果不好。

    结    论

    本文研究的是推荐中多目标优化的问题。我们提出了一个通用的算法框架,在理论保证下生成帕累托有效解。同时,我们提出了一个保证帕累托有效性的理论条件和一个两步算法,它可以进一步适应目标约束。我们将该框架应用在电商推荐上同时优化 GMV 和 CTR,并在一个真实的电商推荐系统上进行了大量的实验,实验结果验证了该框架的有效性。同时,该框架不依赖于模型和目标,显示了强大的可伸缩性。

    论文原文链接:

    https://dl.acm.org/citation.cfm?id=3346998


    8dd0669312539ab53febd74f00b4a3d5.gif

    你也「在看」吗??

    展开全文
  • 基于Hadoop框架的大数据集连接优化算法
  • 一个框架看懂优化算法 一一个框架看懂优化算法 说到优化算法入门级必从 SGD 学起老司机则会告诉你更好还有 AdaGrad / AdaDelta 或者直接无脑用 Adam 可是看看学术界最新 paper却发现一众大神还在 用着入门级 ...
  • MLJTuning.jl:用于MLJ机器学习框架的超参数优化算法
  • Part.5 研究结论 基于狮群的社会结构和NSGA-II的框架,提出了一种新的双目标狮子群算法(LPA),并以基本测试问题和西江流域的水库调度问题为例,评价了该方法在双目标优化中的有效性。得出如下结论: (1)LPA在双目标...
  • 前言前段时间一直在用自己写遗传算法框架测试算法优化力场参数效果,但是跑起来效率很慢,因为适应度函数需要调用多次力场程序计算能量,但是还是比我预想中慢我也没有及时对程序进行profiling和优化。...
  • 一篇化工方面论文,是利用遗传算法进行优化的
  • GeneticAlgorithms是一个简单且轻量级的框架,用于遵循遗传算法模型来实现优化启发式算法。 遗传算法模仿进化,选择和“适者生存”的自然过程。 该框架是直观的,并且与Java 1.5 SDK及更高版本很好地集成在一起。
  • 首先,介绍整个优化算法的基本框架;然后将目前用的主流优化算法进行讲解,带领大家了解优化算法从SGD到Adam及Nadam的转变。基本框架为什么这些算法是能串讲的呢?因为这些算法都是相通的。为什么是相通的呢?因为...
  • Evolutionary Stochastic Gradient Descent for Optimization of Deep ...本文介绍由IBM Research AIXiaodong Cui等作者于NeurIPS 2018发表一个基于种群进化随机梯度下降深度神经网络优化算法框架[1]。 随机...
  • 粒子群优化算法的基本框架4. 对粒子群优化算法中惯性权重的认识5. 粒子群优化算法举例——求解旅行商问题6. 参考文献  同进化算法(见博客《[Evolutionary Algorithm] 进化算法简介》,进化算法是受生物进化机制...
  • 由于本文公式较多,简书不支持公式...优化算法的框架如下所示: $$ w_{t+1} = w_t - \eta_t \ \eta_t = \cfrac{\alpha}{\sqrt{V_t}} \cdot m_t $$ 其中,$w_i$为i时刻的权值,$\eta_i$为i时刻的优化量;$\alpha$为学...
  • 优化算法

    2020-11-25 10:35:50
    优化算法顾名思义就是求解参数方法,比如在机器学习中,定义好了损失函数如何求解模型参数,这时候就是用优化算法来解决。常见的优化算法有:坐标轴上升、坐标轴下降、牛顿法、拟牛顿法、最小二乘法、拉格朗日...
  • 遗传算法框架GAFT优化小记

    千次阅读 2017-10-10 09:16:05
    前段时间一直在用自己写遗传算法框架测试算法优化力场参数效果,但是跑起来效率很慢,因为适应度函数需要调用多次力场程序计算能量,但是还是比我预想中慢我也没有及时对程序进行profiling和优化。...
  • 由于演化算法求解多目标优化问题所得结果是一个优化解集——Pareto最优集,而现有演化算法收敛性分析只适合针对单目标...用有限马尔科夫链给出了演化算法求解多目标优化问题收敛性分析框架,并给出了一个分析实例。
  • 工学硕士学位论文 基于改进 QPSO算法的钢管砼框架 结构设计优化 摘 要 钢管砼结构具有诸多优点且能够适应当代建筑向着大跨高耸重载等方 向发展的需要逐渐成为高层建筑大跨度结构地下结构的主要结构形式之一 具有十分...
  • 正文对GAFT进行性能分析(Profiling)关于如何对Python程序进行性能分析生成分析报告并可视化分析报告,我在之前一篇博客里《Python优化第一步: 性能分析实践》进行了详细介绍,这里我就直接分析了。为了能针对...
  • 首先,介绍整个优化算法的基本框架;然后将目前用的主流优化算法进行讲解,带领大家了解优化算法从SGD到Adam及Nadam的转变。 基本框架 为什么这些算法是能串讲的呢?因为这些算法都是相通的。为什么是相通的呢?因为...
  • SLAM后端优化算法的研究 摘要随着虚拟现实和自动驾驶的飞速发展同时定位与地图创建sLAM是近几年研究的热点也是各领域实现智能化的...其次阐述了基于图优化算法的整体框架关键技术着重介绍了在欧式空间以及流形空间优化
  • 该算法将蚂蚁优化算法纳入文化算法的框架,组成基于蚂蚁优化算法的主群体和信念的两大空间。在知识和群体层面使用双重进化机制支持问题的求解和知识的提取,从而充分利用精英蚂蚁所携带的特征信息,在很大程度上提高...
  • 贝叶斯框架下去雾算法的优化,诸杏子,苏红旗,近年来,由于雾霾天气的频繁出现,图像的户外视觉系统受到了严重的影响,导致图像质量严重退化,影响了图像的特征判断和识别。在
  • 常见优化算法实现 这里实现主要算法有: 一维搜索方法: 黄金分割法 二次差值法 多维搜索算法 最速下降法 partan加速最速下降法 共轭梯度法 牛顿法 拟牛顿法 使用函数表示一个用于优化目标,包括其梯度函数和...
  • 人工蜂群算法的框架简化与算子改进,袁亚杰,马英红,在保留了求解高维函数优化问题的标准人工蜂群算法的核心特点的基础上,本文对算法的流程框架做了很大的简化,取消了作用不明显的

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,082
精华内容 1,232
关键字:

优化算法的框架