这一讲我将介绍两种求极值的方式,一种是你比较熟悉的求导法,另一种便是更厉害的梯度下降法,这里梯度下降法将与代码结合,去轻松解决非常复杂的业务难题。
想要找到一个复杂业务的最优解,就先需要找到影响这个事情的关键因素,以及关键因素之间的关系,而这个过程就是形式化定义的过程,把问题形式化定义后,再去追逐收益的最大化。
“形式化定义”,就是用函数去表达需要用文字描述的问题。也就是说,在做决策之前,需要把你的动作、收益、风险,用函数建立起联系。
我们举一个实际公司业务的例子。假设你在一个电商公司,负责用户营销红包的投放工作。很明显,对于一件商品,你投放给用户的红包金额越高,用户购买这件商品的可能性越大。然而投放红包的金额越高,利润空间也越小。
那么问题来了,对于一件商品,投放多少金额的红包,能让你的利润最大呢?
要想解决这个问题,就需要先对问题进行形式化定义。假设,用户购买商品的概率与投放的补贴金额的关系为 p(x)。因此,投放金额为 x 的红包额后,商品的利润可以定义为
r(x) = p(x)×(m - x - c)
其中,m 为商品的原价,c 为商品的成本价。
有了形式化定义之后,才可以进行业务策略的优化,也就是追逐收益最大化。
“追逐收益最大化”就是求解这个函数的最值,可能是最大值、也可能是最小值。
仍以红包投放为例,要找到能让利润最大的红包金额,你需要用到数学中求解函数极值的知识,也就是计算 max r(x)。
关于某个函数求解极值的问题,我们从中学就开始接触了。那时候我们求解的方法是,令目标函数的一阶导数为零,并求解方程的解,这种方法称作求导法。
【例题1】假设你是某电商公司营销系统的工程师。你们某个商品的购买概率和补贴额的关系为,p(x) = 0.05 x + 0.2。该商品原价 m 为 16 元,成本价 c 为 8 元,求利润最大的补贴额应该是多少?
【解析】商品的利润函数为 r(x) = p(x)×(m - x - c) = (0.05x + 0.2)×(16 - x - 8) = -0.05x2 + 0.2x + 1.6,利用高中的数学求导法,令 r(x) 的导函数为零并解方程,则有:
r’(x) = -0.1x+0.2 = 0
解得,x = 2 元。
除了求导法,对于这个问题,你还可以开发出如下的代码来求解:
def getSubsidy(k,b,m,c):
rx = [-k, k*(m-c)-b, b*(m-c)]
rpx = [-2*k, k*(m-c)-b]
return -rpx[1]/rpx[0]
这样,可以在主函数中,通过 getSubsidy(0.05,0.2,16,8) 来调用,就得到了利润最大的补贴额。
刚才的例子在解方程时,遇到的是个二阶多项式方程,我们利用高中知识就能完成。
然而,实际的业务环境中,遇到的往往是非常复杂的函数。例如,你们公司 BI 同事经过深度分析业务数据得到,商品的购买概率和补贴额的关系为 p(x) = 2÷(1+e-x) - 1。
那么,此时 r(x) = p(x)×(m - x - c) = (2÷(1+e-x) - 1)×(16 - x - 8),建立一阶导数为零的方程为:
这时候就傻眼了,这么复杂的方程怎么解呢?接下来,我们介绍梯度下降算法来求解。
对于一个函数,它的导数的含义是斜率,这也是高中数学知识之一。例如某个函数 f(x),在某个点 x0 的 导数为 f’(x0) = k0。那么 k0,就是函数 f(x) 在 x0 处切线的斜率,如下图:
既然 k0 是斜率,我们很容易得出这样的结论:如果k0为正数,那么函数值在 x0 附近就是呈现“上升”趋势;反之,如果 k0 是负数,函数值在 x0 附近就是呈现“下降”趋势。
围绕这个性质,我们就可以通过多轮迭代,逐步去逼近函数的极值点,如下图:
我们把这个过程用数学语言来重新描述。先来定义一下函数的梯度,对于函数 f(x,y),常用 ▽f(x,y) 来表示函数的梯度。其中 x、y 表示函数有两个或多个自变量,是个多元函数。梯度本身是个向量,表示的是函数在自变量构成的空间中,变化率最快的方向,其计算式为:
可见,如果函数 f(x) 是个一元函数,梯度和导数就非常近似了。区别只在于前者是向量,后者是标量。
至于为什么梯度是函数变化率最快的方向,需要依赖泛函分析相关的知识来证明,证明的过程会比较复杂。如果你感兴趣,可以自己在网上找一些资料进行补充学习。在这里,我们记住这个性质就好了。
有了梯度,我们就能找到函数变化率最快的方向。通过这个方向,就能指挥我们朝哪个方向去更新参数,来找到函数的极值,这就是梯度下降算法。
我们对梯度下降法的原理进行分析。
第 1 步,是把一些要用的公式预先推导出来。
第 2 步,计算当前点的梯度,找到当前点变化率最快的方向。
第 3 步,(xtemp,ytemp) = (xtemp,ytemp) - a×▽f(xtemp,ytemp) 表达的含义是,从当前的点,朝着这个变化率最快方向的反方向,移动一小步后,来更新当前点,这里有两个要点:
最后第 4 步,就是当迭代到极值附近时,就终止条件的判断了。
了解完梯度下降法是怎么回事后,接着我们就用梯度下降法来编程,对先前的问题进行求解。
【例题2】按照之前,我们得到的商品利润函数 r 和补贴金额 x 的关系为 r(x) = p(x)×(m - x - c) = (2/(1+e-x) - 1)×(16 - x - 8)。下面利用梯度下降法,求解让利润最大的补贴额 x*。
【解析】
按照梯度下降法的流程来计算,首先需要写出目标函数 r(x) 的梯度函数,
设置学习率 a 为 0.01,最大迭代次数 1000,然后就需要利用 xtemp = xtemp - a×▽r(xtemp) 来逐轮迭代。
这样整体的代码如下:
import math
def grad(x):
fenzi1 = (-1+9*math.exp(-x)-x*math.exp(-x))*(1+math.exp(-x))
fenzi2 = -(8-x)*(1-math.exp(-x))*math.exp(-x)
fenmu = math.pow(1+math.exp(-x),2)
return (fenzi1 - fenzi2) / fenmu
def main():
a = 0.01
maxloop = 1000
xtemp = 0.1
for _ in range(maxloop):
g = grad(xtemp)
if g < 0.00005:
break
xtemp = xtemp + a*g
print xtemp
if __name__ == '__main__':
main()
程序运行的结果为 2.42017943599。可见,当补贴金额 x = 2.42 元时,利润 r(x) = 4.67 元为最大利润。
为了验证计算结果是否正确,我们可以把利润函数、购买概率函数的曲线打印出来进行观察,如下图。图中,横轴是折扣金额,定义域是[0,8],0 和 8 分别代表补贴额为零时的不打折,和补贴额等于原价减去成本时的不赚钱。
蓝色线代表的是购买概率,是个单调递增的非线性函数。而橙色曲线则是 r(x) 利润函数,图中的定性结论是,r(x) 在 x = 2.4 左右时可以取得最大值约为 4.7,这与我们用梯度下降法计算的结果是一致的。
最后,我们总结一下梯度下降法和求导法的区别和差异,如下表所示:
从计算过程而言,两种方法都需要对目标函数进行求导(求梯度)。求导法的计算量虽然少,但它的难度就在于必须求解出导数为零的方程。这样,在无法写出解析解的场景下,求导法就无能为力了。梯度下降法需要进行多轮的迭代计算,显然计算量是更多的。但每一轮的计算仅仅是带入梯度函数求个梯度值,再更新下自变量。计算量虽然多,难度却很低。对于无法写出解析解的方程,它一样是适用的。
相对求导法,梯度下降法显然是更厉害的算法。不过,它也有一些局限性:
在这一课时,我们学习的是如何从复杂业务环境中找到最优解。
这需要你利用行业经验和领域知识,对问题进行函数的形式化定义,接着就是对目标函数求解最值的过程。
对于求解方法,我们着重学习了梯度下降法。相比求导法而言,梯度下降法的适用性更广、计算更简单,但计算量相对更多。就梯度下降法本身而言,它的局限性是依赖学习率、终止条件、初始值等参数的配置,并且只适用于凸函数。
© 2019 - 2023 Liangliang Lee. Powered by gin and hexo-theme-book.