xinyin025/learn.lianglianglee.com
1
0
Fork 0
mirror of https://github.com/zhwei820/learn.lianglianglee.com.git synced 2025-09-17 08:46:40 +08:00
Code Issues Actions Packages Projects Releases Wiki Activity
master
learn.lianglianglee.com/专栏/程序员的数学课/05 求极值：如何找到复杂业务的最优解？.md.html
周伟 0f006e4e9b add
2022-05-11 18:57:05 +08:00

877 lines
24 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

<!DOCTYPE html>
<!-- saved from url=(0046)https://kaiiiz.github.io/hexo-theme-book-demo/ -->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1.0, user-scalable=no">
<link rel="icon" href="/static/favicon.png">
<title>05 求极值：如何找到复杂业务的最优解？.md.html</title>
<!-- Spectre.css framework -->
<link rel="stylesheet" href="/static/index.css">
<!-- theme css & js -->
<meta name="generator" content="Hexo 4.2.0">
</head>
<body>
<div class="book-container">
<div class="book-sidebar">
<div class="book-brand">
<a href="/">
<img src="/static/favicon.png">
<span>技术文章摘抄</span>
</a>
</div>
<div class="book-menu uncollapsible">
<ul class="uncollapsible">
<li><a href="/" class="current-tab">首页</a></li>
</ul>
<ul class="uncollapsible">
<li><a href="../">上一级</a></li>
</ul>
<ul class="uncollapsible">
<li>
<a href="/专栏/程序员的数学课/00 开篇词 数学，编程能力的营养根基.md.html">00 开篇词 数学，编程能力的营养根基.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/01 从计数开始，程序员必知必会的数制转换法.md.html">01 从计数开始，程序员必知必会的数制转换法.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/02 逻辑与沟通，怎样才能讲出有逻辑的话？.md.html">02 逻辑与沟通，怎样才能讲出有逻辑的话？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/03 用数学决策，如何规划好投入、转化和产出？.md.html">03 用数学决策，如何规划好投入、转化和产出？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/04 万物可数学，经典公式是如何在生活中应用的？.md.html">04 万物可数学，经典公式是如何在生活中应用的？.md.html</a>
</li>
<li>
<a class="current-tab" href="/专栏/程序员的数学课/05 求极值：如何找到复杂业务的最优解？.md.html">05 求极值：如何找到复杂业务的最优解？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/06 向量及其导数：计算机如何完成对海量高维度数据计算？.md.html">06 向量及其导数：计算机如何完成对海量高维度数据计算？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/07 线性回归：如何在离散点中寻找数据规律？.md.html">07 线性回归：如何在离散点中寻找数据规律？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/08 加乘法则：如何计算复杂事件发生的概率？.md.html">08 加乘法则：如何计算复杂事件发生的概率？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/09 似然估计：如何利用 MLE 对参数进行估计？.md.html">09 似然估计：如何利用 MLE 对参数进行估计？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/10 信息熵：事件的不确定性如何计算？.md.html">10 信息熵：事件的不确定性如何计算？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/11 灰度实验：如何设计灰度实验并计算实验的收益？.md.html">11 灰度实验：如何设计灰度实验并计算实验的收益？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/12 统计学方法：如何证明灰度实验效果不是偶然得到的？.md.html">12 统计学方法：如何证明灰度实验效果不是偶然得到的？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/13 复杂度：如何利用数学推导对程序进行优化？.md.html">13 复杂度：如何利用数学推导对程序进行优化？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/14 程序的循环：如何利用数学归纳法进行程序开发？.md.html">14 程序的循环：如何利用数学归纳法进行程序开发？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/15 递归：如何计算汉诺塔问题的移动步数？.md.html">15 递归：如何计算汉诺塔问题的移动步数？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/16 二分法：如何利用指数爆炸优化程序？.md.html">16 二分法：如何利用指数爆炸优化程序？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/17 动态规划：如何利用最优子结构解决问题？.md.html">17 动态规划：如何利用最优子结构解决问题？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/18 AI 入门：利用 3 个公式搭建最简 AI 框架.md.html">18 AI 入门：利用 3 个公式搭建最简 AI 框架.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/19 逻辑回归：如何让计算机做出二值化决策？.md.html">19 逻辑回归：如何让计算机做出二值化决策？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/20 决策树：如何对 NP 难复杂问题进行启发式求解？.md.html">20 决策树：如何对 NP 难复杂问题进行启发式求解？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/21 神经网络与深度学习：计算机是如何理解图像、文本和语音的？.md.html">21 神经网络与深度学习：计算机是如何理解图像、文本和语音的？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/22 面试中那些坑了无数人的算法题.md.html">22 面试中那些坑了无数人的算法题.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/23 站在生活的十字路口，如何用数学抉择？.md.html">23 站在生活的十字路口，如何用数学抉择？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/24 结束语 数学底子好，学啥都快.md.html">24 结束语 数学底子好，学啥都快.md.html</a>
</li>
</ul>
</div>
</div>
<div class="sidebar-toggle" onclick="sidebar_toggle()" onmouseover="add_inner()" onmouseleave="remove_inner()">
<div class="sidebar-toggle-inner"></div>
</div>
<script>
function add_inner() {
let inner = document.querySelector('.sidebar-toggle-inner')
inner.classList.add('show')
}
function remove_inner() {
let inner = document.querySelector('.sidebar-toggle-inner')
inner.classList.remove('show')
}
function sidebar_toggle() {
let sidebar_toggle = document.querySelector('.sidebar-toggle')
let sidebar = document.querySelector('.book-sidebar')
let content = document.querySelector('.off-canvas-content')
if (sidebar_toggle.classList.contains('extend')) { // show
sidebar_toggle.classList.remove('extend')
sidebar.classList.remove('hide')
content.classList.remove('extend')
} else { // hide
sidebar_toggle.classList.add('extend')
sidebar.classList.add('hide')
content.classList.add('extend')
}
}
function open_sidebar() {
let sidebar = document.querySelector('.book-sidebar')
let overlay = document.querySelector('.off-canvas-overlay')
sidebar.classList.add('show')
overlay.classList.add('show')
}
function hide_canvas() {
let sidebar = document.querySelector('.book-sidebar')
let overlay = document.querySelector('.off-canvas-overlay')
sidebar.classList.remove('show')
overlay.classList.remove('show')
}
</script>
<div class="off-canvas-content">
<div class="columns">
<div class="column col-12 col-lg-12">
<div class="book-navbar">
<!-- For Responsive Layout -->
<header class="navbar">
<section class="navbar-section">
<a onclick="open_sidebar()">
<i class="icon icon-menu"></i>
</a>
</section>
</header>
</div>
<div class="book-content" style="max-width: 960px; margin: 0 auto;
overflow-x: auto;
overflow-y: hidden;">
<div class="book-post">
<p id="tip" align="center"></p>
<div><h1>05 求极值：如何找到复杂业务的最优解？</h1>
<p>这一讲我将介绍两种求极值的方式，一种是你比较熟悉的求导法，另一种便是更厉害的梯度下降法，这里梯度下降法将与代码结合，去轻松解决非常复杂的业务难题。</p>
<p>想要找到一个复杂业务的最优解，就先需要找到影响这个事情的关键因素，以及关键因素之间的关系，而这个过程就是形式化定义的过程，把问题形式化定义后，再去追逐收益的最大化。</p>
<h3>形式化定义</h3>
<p><strong>“形式化定义”，就是用函数去表达需要用文字描述的问题</strong>。也就是说，在做决策之前，需要把你的动作、收益、风险，用函数建立起联系。</p>
<p>我们举一个实际公司业务的例子。假设你在一个电商公司，负责用户营销红包的投放工作。很明显，对于一件商品，你投放给用户的红包金额越高，用户购买这件商品的可能性越大。然而投放红包的金额越高，利润空间也越小。</p>
<p>那么问题来了，对于一件商品，投放多少金额的红包，能让你的利润最大呢？</p>
<p>要想解决这个问题，就需要<strong>先对问题进行形式化定义</strong>。假设，用户购买商品的概率与投放的补贴金额的关系为 p(x)。因此，投放金额为 x 的红包额后，商品的利润可以定义为</p>
<blockquote>
<p>r(x) = p(x)×(m - x - c)</p>
</blockquote>
<p>其中，m 为商品的原价，c 为商品的成本价。</p>
<p>有了形式化定义之后，才可以进行业务策略的优化，也就是追逐收益最大化。</p>
<h3>追逐收益最大化</h3>
<p>“追逐收益最大化”就是求解这个函数的最值，可能是最大值、也可能是最小值。</p>
<p>仍以红包投放为例，要找到能让利润最大的红包金额，你需要用到数学中求解函数极值的知识，也就是计算 max r(x)。</p>
<p>关于某个函数求解极值的问题，我们从中学就开始接触了。那时候我们求解的方法是，令目标函数的一阶导数为零，并求解方程的解，这种方法称作<strong>求导法</strong>。</p>
<p>【例题1】假设你是某电商公司营销系统的工程师。你们某个商品的购买概率和补贴额的关系为，p(x) = 0.05 x + 0.2。该商品原价 m 为 16 元，成本价 c 为 8 元，求利润最大的补贴额应该是多少？</p>
<p>【解析】商品的利润函数为 r(x) = p(x)×(m - x - c) = (0.05x + 0.2)×(16 - x - 8) = -0.05x2 + 0.2x + 1.6，利用高中的数学求导法，令 r(x) 的导函数为零并解方程，则有：</p>
<p>r'(x) = -0.1x+0.2 = 0</p>
<p>解得，x = 2 元。</p>
<p>除了求导法，对于这个问题，你还可以开发出如下的代码来求解：</p>
<pre><code>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]
</code></pre>
<p>这样，可以在主函数中，通过 getSubsidy(0.05,0.2,16,8) 来调用，就得到了利润最大的补贴额。</p>
<h3>方程解不出来怎么办？</h3>
<p>刚才的例子在解方程时，遇到的是个二阶多项式方程，我们利用高中知识就能完成。</p>
<p>然而，实际的业务环境中，遇到的往往是非常复杂的函数。例如，你们公司 BI 同事经过深度分析业务数据得到，商品的购买概率和补贴额的关系为 p(x) = 2÷(1+e-x) - 1。</p>
<p>那么，此时 r(x) = p(x)×(m - x - c) = (2÷(1+e-x) - 1)×(16 - x - 8)，建立一阶导数为零的方程为：</p>
<p><img src="assets/Ciqc1F-lLfWALksbAACzxQp45Og350.png" alt="图片1.png" /></p>
<p>这时候就傻眼了，这么复杂的方程怎么解呢？接下来，我们介绍<strong>梯度下降算法</strong>来求解。</p>
<h3>梯度下降法</h3>
<p>对于一个函数，它的<strong>导数的含义是斜率</strong>，这也是高中数学知识之一。例如某个函数 f(x)，在某个点 x0 的 导数为 f'(x0) = k0。那么 k0，就是函数 f(x) 在 x0 处切线的斜率，如下图：</p>
<p><img src="assets/Ciqc1F-qVZKAS8jJAABcDXkImPQ292.png" alt="2.png" /></p>
<p>既然 k0 是斜率，我们很容易得出这样的结论：如果k0为正数，那么函数值在 x0 附近就是呈现“上升”趋势；反之，如果 k0 是负数，函数值在 x0 附近就是呈现“下降”趋势。</p>
<p>围绕这个性质，我们就可以通过多轮迭代，逐步去逼近函数的极值点，如下图：</p>
<p><img src="assets/CgqCHl-qVZ6AOlJUAABz4DaT__M220.png" alt="3.png" /></p>
<p>我们把这个过程用数学语言来重新描述。先来定义一下函数的梯度，对于函数 f(x,y)，常用 ▽f(x,y) 来表示函数的梯度。其中 x、y 表示函数有两个或多个自变量，是个多元函数。梯度本身是个向量，表示的是函数在自变量构成的空间中，变化率最快的方向，其计算式为：</p>
<p><img src="assets/Ciqc1F-qVaqATraDAAD0x8r1kug105.png" alt="4.png" /></p>
<p>可见，如果函数 f(x) 是个一元函数，梯度和导数就非常近似了。区别只在于前者是向量，后者是标量。</p>
<blockquote>
<p>至于为什么梯度是函数变化率最快的方向，需要依赖泛函分析相关的知识来证明，证明的过程会比较复杂。如果你感兴趣，可以自己在网上找一些资料进行补充学习。在这里，我们记住这个性质就好了。</p>
</blockquote>
<p>有了梯度，我们就能找到函数变化率最快的方向。通过这个方向，就能指挥我们朝哪个方向去更新参数，来找到函数的极值，这就是梯度下降算法。</p>
<p><img src="assets/Ciqc1F-ovdOAHnpsAANEdznZKzw098.png" alt="WechatIMG388.png" /></p>
<p>我们对梯度下降法的原理进行分析。</p>
<p>第 1 步，是把一些要用的公式预先推导出来。</p>
<p>第 2 步，计算当前点的梯度，找到当前点变化率最快的方向。</p>
<p>第 3 步，(xtemp,ytemp) = (xtemp,ytemp) - a×▽f(xtemp，ytemp) 表达的含义是，从当前的点，朝着这个变化率最快方向的反方向，移动一小步后，来更新当前点，这里有两个要点：</p>
<ul>
<li>之所以是“反方向”，是因为我们要求解的是函数的极小值；如果是极大值，就不是反方向了，公式中的“负号”就要修改为“正号”。</li>
<li>“移动一小步”的实现，一般用学习率 a 来控制。通常 a 不会很大，比如设置为 0.1、0.05 等等。如果 a 过大，则可能会出现移动后“跳过”极值的可能；如果 a 过小，无非就是迭代次数多一些而已。这一步是梯度下降法最关键的步骤。</li>
</ul>
<p>最后第 4 步，就是当迭代到极值附近时，就终止条件的判断了。</p>
<p>了解完梯度下降法是怎么回事后，接着我们就用梯度下降法来编程，对先前的问题进行求解。</p>
<p>【例题2】按照之前，我们得到的商品利润函数 r 和补贴金额 x 的关系为 r(x) = p(x)×(m - x - c) = (2/(1+e-x) - 1)×(16 - x - 8)。下面利用梯度下降法，求解让利润最大的补贴额 x*。</p>
<p>【解析】</p>
<p>按照梯度下降法的流程来计算，首先需要写出目标函数 r(x) 的梯度函数，</p>
<p><img src="assets/Ciqc1F-qVcyAKSCrAABh6x1GG7Y355.png" alt="5.png" /></p>
<p>设置学习率 a 为 0.01，最大迭代次数 1000，然后就需要利用 xtemp = xtemp - a×▽r(xtemp) 来逐轮迭代。</p>
<p>这样整体的代码如下：</p>
<pre><code>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 &lt; 0.00005:
break
xtemp = xtemp + a*g
print xtemp
if __name__ == '__main__':
main()
</code></pre>
<p>程序运行的结果为 2.42017943599。可见，当补贴金额 x = 2.42 元时，利润 r(x) = 4.67 元为最大利润。</p>
<p>为了验证计算结果是否正确，我们可以把利润函数、购买概率函数的曲线打印出来进行观察，如下图。图中，横轴是折扣金额，定义域是[0,8]，0 和 8 分别代表补贴额为零时的不打折，和补贴额等于原价减去成本时的不赚钱。</p>
<p>蓝色线代表的是购买概率，是个单调递增的非线性函数。而橙色曲线则是 r(x) 利润函数，图中的定性结论是，r(x) 在 x = 2.4 左右时可以取得最大值约为 4.7，这与我们用梯度下降法计算的结果是一致的。</p>
<p><img src="assets/Ciqc1F-lLlKAcy43AAGmXbmOED4877.png" alt="图片6.png" /></p>
<p>最后，我们总结一下梯度下降法和求导法的区别和差异，如下表所示：</p>
<p><img src="assets/CgqCHl-lLlqAYAhhAAEvzMkgSOE792.png" alt="图片7.png" /></p>
<p>从计算过程而言，两种方法都需要对目标函数进行求导（求梯度）。<strong>求导法</strong>的计算量虽然少，但它的难度就在于<strong>必须求解出导数为零的方程</strong>。这样，在无法写出解析解的场景下，求导法就无能为力了。<strong>梯度下降法</strong>需要进行多轮的迭代计算，显然计算量是更多的。但每一轮的计算仅仅是带入梯度函数求个梯度值，再更新下自变量。计算量虽然多，难度却很低。对于无法写出解析解的方程，它一样是适用的。</p>
<p>相对求导法，梯度下降法显然是更厉害的算法。不过，它也有一些<strong>局限性</strong>：</p>
<ul>
<li>它需要配置一些算法参数，如学习率、停止条件等。如果配置不好，可能会导致算法失效。例如，在本课时的例子中，如果学习率不小心设置为 0.7 以上，结果就不再是 2.42 了。这是因为学习率过高，导致了每一次迭代自变量“移动的步伐太大”，而频繁跨越最值无法收敛。</li>
<li>它要求目标函数为凸函数，否则就有可能会收敛到局部最优。
例如下面的双峰函数便不是凸函数。幸运的是，实际业务环境中很少会遇到非凸的函数。如果真的遇到非凸的函数，一个可行的方法是，采用随机初始化 xtemp，并多次执行梯度下降法求解。</li>
</ul>
<p><img src="assets/CgqCHl-qVduAL6wWAABuccARt0M254.png" alt="6.png" /></p>
<h3>小结</h3>
<p>在这一课时，我们学习的是如何从复杂业务环境中找到最优解。</p>
<p>这需要你利用行业经验和领域知识，对问题进行函数的形式化定义，接着就是对目标函数求解最值的过程。</p>
<p>对于求解方法，我们着重学习了梯度下降法。相比求导法而言，梯度下降法的适用性更广、计算更简单，但计算量相对更多。就梯度下降法本身而言，它的局限性是依赖学习率、终止条件、初始值等参数的配置，并且只适用于凸函数。</p>
</div>
</div>
<div>
<div style="float: left">
<a href="/专栏/程序员的数学课/04 万物可数学，经典公式是如何在生活中应用的？.md.html">上一页</a>
</div>
<div style="float: right">
<a href="/专栏/程序员的数学课/06 向量及其导数：计算机如何完成对海量高维度数据计算？.md.html">下一页</a>
</div>
</div>
</div>
</div>
</div>
</div>
<a class="off-canvas-overlay" onclick="hide_canvas()"></a>
</div>
<script defer src="https://static.cloudflareinsights.com/beacon.min.js/v652eace1692a40cfa3763df669d7439c1639079717194" integrity="sha512-Gi7xpJR8tSkrpF7aordPZQlW2DLtzUlZcumS8dMQjwDHEnw9I7ZLyiOj/6tZStRBGtGgN6ceN6cMH8z7etPGlw==" data-cf-beacon='{"rayId":"70997bc72f0f3cfa","version":"2021.12.0","r":1,"token":"1f5d475227ce4f0089a7cff1ab17c0f5","si":100}' crossorigin="anonymous"></script>
</body>
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-NPSEEVD756"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag() {
dataLayer.push(arguments);
}
gtag('js', new Date());
gtag('config', 'G-NPSEEVD756');
var path = window.location.pathname
var cookie = getCookie("lastPath");
console.log(path)
if (path.replace("/", "") === "") {
if (cookie.replace("/", "") !== "") {
console.log(cookie)
document.getElementById("tip").innerHTML = "<a href='" + cookie + "'>跳转到上次进度</a>"
}
} else {
setCookie("lastPath", path)
}
function setCookie(cname, cvalue) {
var d = new Date();
d.setTime(d.getTime() + (180 * 24 * 60 * 60 * 1000));
var expires = "expires=" + d.toGMTString();
document.cookie = cname + "=" + cvalue + "; " + expires + ";path = /";
}
function getCookie(cname) {
var name = cname + "=";
var ca = document.cookie.split(';');
for (var i = 0; i < ca.length; i++) {
var c = ca[i].trim();
if (c.indexOf(name) === 0) return c.substring(name.length, c.length);
}
return "";
}
</script>
</html>
Reference in New Issue View Git Blame Copy Permalink