头歌实践教学平台：数据科学与大数据技术导论（十三）

十三、数据科学导论——数学基础之优化第1关模型优化基础任务描述模型优化在一些复杂的训练模型中是不可避免的本关主要是让大家对模型优化的方法有个基本的了解。本关任务根据相关知识完成右侧选择题任务。相关知识我们每个人都会在我们的生活或者工作中遇到各种各样的最优化问题比如每个企业和个人都要考虑的一个问题“在一定成本下如何使利润最大化”等。最优化方法是一种数学方法它是研究在给定约束之下如何寻求某些因素的量以使某一或某些指标达到最优的一些学科的总称。随着学习的深入我们会发现学习和工作中遇到的大多问题都可以建模成一种最优化模型进行求解比如我们现在学习的机器学习算法大部分的机器学习算法的本质都是建立优化模型通过最优化方法对目标函数或损失函数进行优化从而训练出最好的模型。什么是模型优化模型优化问题为某种特定的情形寻找最佳模型。举个例子给定数据集上的模型残差最小时即为“最佳”。实际应用举例用多项式函数建模一台家用电器的功耗和运转时间之间的关系。(1) 使用一次函数建模ykxd(2) 使用二次函数建模实际上二次函数可能是或者等等。(3) 使用三次函数建模假设我们选择三次函数建模那么怎么判定哪一个是最优化模型呢我们通常采用函数残差作为评价标准。也就是说在中哪个函数哪组参数 [w,p,q,t] 最好这就是最优化问题确定了 wpqt 之后我们就确定了最终的模型。常见的模型优化方法常见的最优化方法有梯度下降法梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向因为该方向为当前位置的最快下降方向所以也被称为是“最速下降法“最速下降法越接近目标值步长越小前进越慢。牛顿法和拟牛顿法牛顿法是一种在实数域和复数域上近似求解方程的方法拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的 Hessian 矩阵的逆矩阵的缺陷它使用正定矩阵来近似 Hessian 矩阵的逆从而简化了运算的复杂度。共轭梯度法共轭梯度法是介于最速下降法与牛顿法之间的一个方法它仅需利用一阶导数信息但克服了最速下降法收敛慢的缺点又避免了牛顿法需要存储和计算海塞矩阵并求逆的缺点共轭梯度法不仅是解决大型线性方程组最有用的方法之一也是解大型非线性最优化最有效的算法之一。启发式优化方法启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时利用过去的经验选择已经行之有效的方法而不是系统地以确定的步骤去寻求答案。启发式优化方法种类繁多包括经典的模拟退火方法遗传算法蚁群算法以及粒子群算法等等。解决约束优化问题 - 拉格朗日乘数法。作为一种优化算法拉格朗日乘子法主要用于解决约束优化问题它的基本思想就是通过引入拉格朗日乘子来将含有 n 个变量和 k 个约束条件的约束优化问题转化为含有 nk 个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。在下面的关卡中我们会详细介绍使用最为频繁的梯度下降法。编程要求根据相关知识按照要求完成右侧选择题任务。测试说明平台会对你选择的答案进行判断全对则通过测试。开始你的任务吧祝你成功第2关梯度下降任务描述本关任务使用梯度下降拟合输入数据 xy 。相关知识从事数据科学工作时常常会面临这样的需要为某种特定的情形寻找最佳模型。“最佳”常常会被解读为某种类似于“最小化模型残差”或者“最大化数据的可能性”。换句话说它代表了优化某种问题的解决方案。这意味着我们需要解决一连串的最优化问题。我们采用的方法是一种叫作梯度下降 gradient descent 的技术。梯度下降的思想假设我们拥有某个函数 f 这个函数输入一个实数向量输出一个实数。一个简单的例子如下def sum_of_squares(v):return sum(v_i ** 2 for v_i in v)我们常常需要最大化或最小化这个函数。这意味着我们需要找出能计算出最大或最小可能值的输入 v。对我们的函数来说梯度给出了输入值的方向在这个方向上函数增长得最快。相应地最大化函数的算法首先从一个随机初始点开始计算梯度在梯度方向上跨越一小步再从一个新的初始点开始重复这个过程。同样你也可以在相反方向上逐步最小化函数如下图所示需要注意如果一个函数有一个全局最小点那么梯度下降很可能会找到它。但是函数有多个局部)最小点那么梯度下降可能找不到这个点但是可以通过多尝试一些初始点来重复运行。如果一个函数没有最小点计算也许会陷入死循环。估算梯度如果 f 是单变量函数那么它在 x 点的导数衡量了当 x 发生变化时f(x) 变化了多少。导数通过差商的极限来定义def difference_quotient(f, x, h):return (f(x h) - f(x)) / h其中 h 趋近于 0 。如上图所示导数就是在点 (x, f (x)) 的切线的斜率而差商就是通过点 (x, f (x)) 和点 (xh, f (xh)) 的割线的斜率。当 h 越来越小割线与切线就越来越接近。很多函数可以精确地计算导数比如平方函数 square def square(x):#计算平方return x * x它的导数为def derivative(x):return 2 * xpython 中无法直接运算极限但可以通过计算一个很小的变动 e 的差商来估算微分。import matplotlib.pyplot as pltfrom functools import partialplt.rcParams[font.sans-serif][simhei]plt.rcParams[font.family]sans-serifplt.rcParams[axes.unicode_minus]False #画图可中文derivative_estimate partial(difference_quotient, square, h0.00001)# 绘出导入matplotlib.pyplot作为plt的基本相同的形态x range(-10,10)plt.title(精确的导数值与估计值)plt.plot(x, list(map(derivative, x)), rx, labelActual) # 用 x 表示plt.plot(x, list(map(derivative_estimate, x)), b, labelEstimate) # 用 表示plt.legend(loc9)plt.show()当 f 是一个多变量函数时它有多个偏导数每个偏导数表示仅有一个输入变量发生微小变化时函数 f 的变化。我们把导数看成是其第 i 个变量的函数其他变量保持不变以此来计算它第 i 个偏导数def partial_difference_quotient(f, v, i, h):w [v_j (h if j i else 0) # 只对v的第i个元素增加hfor j, v_j in enumerate(v)]return (f(w) - f(v)) / h再以同样的方法估算它的梯度函数def estimate_gradient(f, v, h0.00001):return [partial_difference_quotient(f, v, i, h)for i, _ in enumerate(v)]选择正确步长尽管向梯度的反向移动的逻辑已经清楚了但移动多少还不明了。事实上选择合适的步长更像艺术而非科学。主流的选择方法有使用固定步长随时间增长逐步减小步长在每一步中通过最小化目标函数的值来选择合适的步长。随机梯度下降法通常而言我们有一些 target_fn 函数需要对其进行最小化也有梯度函数 gradient_fn 。比如函数 target_fn 可能代表模型的残差它是参数的函数。我们可能需要找到能使残差尽可能小的参数。此外假设我们以某种方式为参数 theta_0 设定了某个初始值那么可以如下使用批量梯度下降def minimize_batch(target_fn, gradient_fn, theta_0, tolerance0.000001):step_sizes [100, 10, 1, 0.1, 0.01, 0.001, 0.0001, 0.00001]theta theta_0 # 设定theta为初始值target_fn safe(target_fn) # target_fn的安全版value target_fn(theta) # 我们试图最小化的值while True:gradient gradient_fn(theta)next_thetas [step(theta, gradient, -step_size)for step_size in step_sizes]# 选择一个使残差函数最小的值next_theta min(next_thetas, keytarget_fn)next_value target_fn(next_theta)# 当“收敛”时停止if abs(value - next_value) tolerance:return thetaelse:theta, value next_theta, next_value有时候我们需要最大化某个函数这只需要最小化这个函数的负值相应的梯度函数也需取负def negate(f):return lambda *args, **kwargs: -f(*args, **kwargs)def negate_all(f):return lambda *args, **kwargs: [-y for y in f(*args, **kwargs)]def maximize_batch(target_fn, gradient_fn, theta_0, tolerance0.000001):return minimize_batch(negate(target_fn),negate_all(gradient_fn),theta_0,tolerance)在每一步梯度计算中都会搜索整个数据集这使每一步都会耗费很长的时间。现在这些残差函数常常具有可加性意味着整个数据集上的预测残差恰好是每个数据点的预测残差之和。在这种情形下我们转而使用一种称为随机梯度下降的技术它每次仅计算一个点的梯度这个计算会反复循环直到达到一个停止点。在每个循环中我们都会在整个数据集上按照一个随机序列迭代def in_random_order(data):indexes [i for i, _ in enumerate(data)] # 生成索引列表random.shuffle(indexes) # 随机打乱数据for i in indexes: # 返回序列中的数据yield data[i]我们对每个数据点都会进行一步梯度计算。这种方法留有这样一种可能性即也许会在最小值附近一直循环下去所以每当停止获得改进我们都会减小步长并最终退出:def minimize_stochastic(target_fn, gradient_fn, x, y, theta_0, alpha_00.01):data zip(x, y)theta theta_0 # 初始值猜测alpha alpha_0 # 初始步长min_theta, min_value None, float(inf) # 迄今为止的最小值iterations_with_no_improvement 0# 如果循环超过100次仍无改进停止while iterations_with_no_improvement 100:value sum( target_fn(x_i, y_i, theta) for x_i, y_i in data )if value min_value:# 如果找到新的最小值记住它# 并返回到最初的步长min_theta, min_value theta, valueiterations_with_no_improvement 0alpha alpha_0else:# 尝试缩小步长否则没有改进iterations_with_no_improvement 1alpha * 0.9# 在每个数据点上向梯度方向前进一步for x_i, y_i in in_random_order(data):gradient_i gradient_fn(x_i, y_i, theta)theta vector_subt\fract(theta, scalar_multiply(alpha, gradient_i))return min_theta随机化通常比批处理化快很多。当然我们也希望获得最大化的结果def maximize_stochastic(target_fn, gradient_fn, x, y, theta_0, alpha_00.01):return minimize_stochastic(negate(target_fn),negate_all(gradient_fn),x, y, theta_0, alpha_0)编程要求请仔细阅读右侧代码结合相关知识在 Begin-End 区域内进行代码补充根据输入数据 xy 使用批梯度下降计算出 ab 的值。公式为ya∗xb测试说明平台会对你编写的代码进行测试为了评判准确请将结果四舍五入转换为整数测试输入[5,9,12,35,21,16,7,33][25, 37, 46, 115, 73, 58, 31, 109]预期输出310开始你的任务吧祝你成功def student(x, y):epsilon 0.00001 # 迭代阀值当两次迭代损失函数之差小于该阀值时停止迭代alpha 0.001 # 把学习率从0.01改成0.001防止梯度爆炸溢出a 0b 0m len(x)error0 0error1 0max_iter 100000 # 增加最大迭代次数防止死循环iter_count 0# ********* Begin *********#while iter_count max_iter:grad_a 0grad_b 0total_loss 0.0for i in range(m):predict a * x[i] berr predict - y[i]grad_a err * x[i]grad_b errtotal_loss err ** 2grad_a 2 / m * grad_agrad_b 2 / m * grad_berror1 total_loss / m# 收敛条件if abs(error1 - error0) epsilon:breakerror0 error1# 更新参数a a - alpha * grad_ab b - alpha * grad_biter_count 1a round(a)b round(b)print(a)print(b)# ********* End *********#有任何问题都可以随时关注私信