纯干货 | 机器学习中梯度下降法的分类及对比分析(附源码)

本文涉及的产品
云原生大数据计算服务 MaxCompute,5000CU*H 100GB 3个月
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
简介: 本文详细介绍了基于使用数据量的多少,时间复杂度以及算法准确率的不同类型的梯度下降法,并详细说明了3种梯度下降法的比较。
更多深度文章,请关注:https://yq.aliyun.com/cloud

HackerEarth,一家来自印度的创业公司,旨在帮助开发者通过线上编程竞赛获得工作机会。和Github类似,它提供一个多种编程语言的代码交流平台。而HackerEarth blog 上多刊登一些跟大数据、人工智能、机器学习、算法及编程竞赛相关的博文。

f5e6e0bcd0a1d12d75f80446b773999e5b1750dd

引言

      梯度下降法 (Gradient Descent Algorithm,GD) 是为目标函数J(θ),如代价函数(cost function), 求解全局最小值(Global Minimum)的一种迭代算法。本文会详细讨论按照准确性和耗费时间(accuracy and time consuming factor)将梯度下降法进行分类。这个算法在机器学习中被广泛用来最小化目标函数,如下图所示。

ee0ae16bbac1db584fbdf744e5f517cca85c3b7e

为什么使用梯度下降法

      我们使用梯度下降法最小化目标函数J(θ)。在使用梯度下降法时,首先初始化参数值,然后一直改变这些值,直到得到全局最小值。其中,我们计算在每次迭代时计算代价函数的导数,然后使用如下公式同时更新参数值:

a5b40dac8c48a93c6e0b9c0725bf8c81fe10ba8d

α表示学习速率(learning rate)。

在本文中,考虑使用线性回归linear regression)作为算法实例,当然梯度下降法也可以应用到其他算法,如逻辑斯蒂回归(Logistic regression)和 神经网络(Neural networks)。在线性回归中,我们使用如下拟合函数(hypothesis function):

cc57b6c6b85dce36eb7cd93d6db9bcfb50b4d7ee

其中, fb4b7ce517e248004c59fb559578e54a4a9482f4是参数,a65bfc1e47ff7322dfe5ce55cf7f8bb891259a01 是输入特征。为了求解线性回归模型,需要找到合适的参数使拟合函数能够更好地适合模型,然后使用梯度下降最小化代价函数J(θ)

代价函数(普通的最小平方差,ordinary least square error)如下所示

b2cbb904e3bc0a7044c0a5fa0f8bc2ecdcf622ca

代价函数的梯度(Gradient of Cost function):

4429e2f2d132d5207f67f09e94b22819c90dc1fa

参数与代价函数关系如下图所示:

1e5064d9ee7749bab10f650a8d3b00db8979c28e

梯度下降法的工作原理

下面的伪代码能够解释其详细原理:
1. 初始化参数值
2. 迭代更新这些参数使目标函数J(θ)不断变小。

梯度下降法的类型

基于如何使用数据计算代价函数的导数,梯度下降法可以被定义为不同的形式(various variants)。确切地说,根据使用数据量的大小the amount of data),时间复杂度time complexity)和算法的准确率accuracy of the algorithm),梯度下降法可分为:

1.       批量梯度下降法Batch Gradient Descent, BGD);

2.       随机梯度下降法Stochastic Gradient Descent, SGD);

3.       小批量梯度下降法Mini-Batch Gradient Descent, MBGD)。

批量梯度下降法原理

      这是梯度下降法的基本类型,这种方法 使用整个数据集( the complete dataset )去计算代价函数的梯度 。每次使用全部数据计算梯度去更新参数, 批量梯度下降法会很慢 ,并且很难处理不能载入内存( don’t fit in memory )的数据集。在随机初始化参数后,按如下方式计算代价函数的梯度:

e73e9a24fa64e4fb81246d312e0a1e6af5742cb9

其中,m是训练样本(training examples)的数量。

Note:

     1. 如果训练集有3亿条数据,你需要从硬盘读取全部数据到内存中;

     2. 每次一次计算完求和后,就进行参数更新;

     3.   然后重复上面每一步;

     4. 这意味着需要较长的时间才能收敛

     5. 特别是因为磁盘输入/输出(disk I/O)是系统典型瓶颈,所以这种方法会不可避免地需要大量的读取。

2cce4e74db8b0834f57cbaab8abe4ab7249305f3

上图是每次迭代后的等高线图,每个不同颜色的线表示代价函数不同的值。运用梯度下降会快速收敛到圆心,即唯一的一个全局最小值。

批量梯度下降法不适合大数据集。下面的Python代码实现了批量梯度下降法:


1.	import numpy as np  
2.	import random  
3.	def gradient_descent(alpha, x, y, ep=0.0001, max_iter=10000):  
4.	    converged = False  
5.	    iter = 0  
6.	    m = x.shape[0] # number of samples  
7.	  
8.	    # initial theta  
9.	    t0 = np.random.random(x.shape[1])  
10.	    t1 = np.random.random(x.shape[1])  
11.	  
12.	    # total error, J(theta)  
13.	    J = sum([(t0 + t1*x[i] - y[i])**2 for i in range(m)])  
14.	  
15.	    # Iterate Loop  
16.	    while not converged:  
17.	        # for each training sample, compute the gradient (d/d_theta j(theta))  
18.	        grad0 = 1.0/m * sum([(t0 + t1*x[i] - y[i]) for i in range(m)])   
19.	        grad1 = 1.0/m * sum([(t0 + t1*x[i] - y[i])*x[i] for i in range(m)])  
20.	        # update the theta_temp  
21.	        temp0 = t0 - alpha * grad0  
22.	        temp1 = t1 - alpha * grad1  
23.	      
24.	        # update theta  
25.	        t0 = temp0  
26.	        t1 = temp1  
27.	  
28.	        # mean squared error  
29.	        e = sum( [ (t0 + t1*x[i] - y[i])**2 for i in range(m)] )   
30.	  
31.	        if abs(J-e) <= ep:  
32.	            print 'Converged, iterations: ', iter, '!!!'  
33.	            converged = True  
34.	      
35.	        J = e   # update error   
36.	        iter += 1  # update iter  
37.	      
38.	        if iter == max_iter:  
39.	            print 'Max interactions exceeded!'  
40.	            converged = True  
41.	  
42.	    return t0,t1 

随机梯度下降法原理

    批量梯度下降法被证明是一个较慢的算法,所以,我们可以选择随机梯度下降法达到更快的计算。随机梯度下降法的第一步是随机化整个数据集。在每次迭代仅选择一个训练样本去计算代价函数的梯度,然后更新参数。即使是大规模数据集,随机梯度下降法也会很快收敛。随机梯度下降法得到结果的准确性可能不会是最好的,但是计算结果的速度很快。在随机化初始参数之后,使用如下方法计算代价函数的梯度:
bac171a0ee9ae8ea7e1241d0f5c49cae19f35704

这里m表示训练样本的数量。

如下为随机梯度下降法的伪码:

       1. 进入内循环(inner loop);

       2. 第一步:挑选第一个训练样本并更新参数,然后使用第二个实例;

       3. 第二步:选第二个训练样本,继续更新参数;

       4. 然后进行第三步…直到第n步;

       5. 直到达到全局最小值

如下图所示,随机梯度下降法不像批量梯度下降法那样收敛,而是游走到接近全局最小值的区域终止

179a3f7ba6d43967171a3c042712f193a9375df5

小批量梯度下降法原理

 小批量梯度下降法是最广泛使用的一种算法,该算法每次使用m个训练样本(称之为一批)进行训练,能够更快得出准确的答案。小批量梯度下降法不是使用完整数据集,在每次迭代中仅使用m个训练样本去计算代价函数的梯度。一般小批量梯度下降法所选取的样本数量在50256个之间,视具体应用而定。

1.这种方法减少了参数更新时的变化,能够更加稳定地收敛。

2.同时,也能利用高度优化的矩阵,进行高效的梯度计算。

随机初始化参数后,按如下伪码计算代价函数的梯度:
6ab4dc834ad914cd762f4c6b71ad84a6a2072681
这里b表示一批训练样本的个数,m是训练样本的总数。

Notes:

1. 实现该算法时,同时更新参数

c944184d2a723235b3d10c20e2d47eb04cc18079

2. 学习速率α(也称之为步长)如果α过大,算法可能不会收敛;如果α比较小,就会很容易收敛。

993031773399242fc846b90fbe097ef0b68dd40e

3. 检查梯度下降法的工作过程。画出迭代次数与每次迭代后代价函数值的关系图,这能够帮助你了解梯度下降法是否取得了好的效果。每次迭代后J(θ)应该降低,多次迭代后应该趋于收敛。

8ea2d3d604748b11018d054efcfdbf455116b416

93a9bbaa880631a57a7b439941afc12fe70fa0b5

4. 不同的学习速率在梯度下降法中的效果

d8ec456ab02fb7c20059e1dff1346abc04030272

总结

本文详细介绍了不同类型的梯度下降法。这些算法已经被广泛应用于神经网络。下面的图详细展示了3种梯度下降法的比较。

b9270bdb89b892bae231e61ee2cb29634cfedc0a



以上为译文

本文由北邮@爱可可-爱生活 老师推荐,阿里云云栖社区组织翻译。

文章原标题《3 Types of Gradient Descent Algorithms for Small & Large Data Sets》,由HackerEarth blog发布。

译者:李烽 ;审校:段志成-海棠

文章为简译,更为详细的内容,请查看原文。中文译制文档下载见此。

相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps&nbsp;
相关文章
|
25天前
|
机器学习/深度学习 算法 数据可视化
机器学习模型中特征贡献度分析:预测贡献与错误贡献
本文将探讨特征重要性与特征有效性之间的关系,并引入两个关键概念:预测贡献度和错误贡献度。
76 3
|
5天前
|
机器学习/深度学习 数据可视化 算法
机器学习中的回归分析:理论与实践
机器学习中的回归分析:理论与实践
|
6天前
|
机器学习/深度学习 数据采集 算法
【Python篇】从零到精通:全面分析Scikit-Learn在机器学习中的绝妙应用
【Python篇】从零到精通:全面分析Scikit-Learn在机器学习中的绝妙应用
21 2
|
3天前
|
机器学习/深度学习 算法
【机器学习】揭秘GBDT:梯度提升决策树
【机器学习】揭秘GBDT:梯度提升决策树
|
25天前
|
机器学习/深度学习 存储 人工智能
文本情感识别分析系统Python+SVM分类算法+机器学习人工智能+计算机毕业设计
使用Python作为开发语言,基于文本数据集(一个积极的xls文本格式和一个消极的xls文本格式文件),使用Word2vec对文本进行处理。通过支持向量机SVM算法训练情绪分类模型。实现对文本消极情感和文本积极情感的识别。并基于Django框架开发网页平台实现对用户的可视化操作和数据存储。
30 0
文本情感识别分析系统Python+SVM分类算法+机器学习人工智能+计算机毕业设计
|
2月前
|
机器学习/深度学习 人工智能 数据处理
【人工智能】项目实践与案例分析:利用机器学习探测外太空中的系外行星
探测外太空中的系外行星是天文学和天体物理学的重要研究领域。随着望远镜观测技术的进步和大数据的积累,科学家们已经能够观测到大量恒星的光度变化,并尝试从中识别出由行星凌日(行星经过恒星前方时遮挡部分光线)引起的微小亮度变化。然而,由于数据量巨大且信号微弱,传统方法难以高效准确地识别所有行星信号。因此,本项目旨在利用机器学习技术,特别是深度学习,从海量的天文观测数据中自动识别和分类系外行星的信号。这要求设计一套高效的数据处理流程、构建适合的机器学习模型,并实现自动化的预测和验证系统。
48 1
【人工智能】项目实践与案例分析:利用机器学习探测外太空中的系外行星
|
1月前
|
机器学习/深度学习 存储 数据挖掘
Hologres 与机器学习的融合:为实时分析添加预测性分析功能
【9月更文第1天】随着数据科学的发展,企业越来越依赖于从数据中获取洞察力来指导决策。传统的数据仓库主要用于存储和查询历史数据,而现代的数据仓库如 Hologres 不仅提供了高性能的查询能力,还能够支持实时数据分析。将 Hologres 与机器学习技术相结合,可以在实时数据流中引入预测性分析,为企业提供更深入的数据洞见。本文将探讨如何将 Hologres 与机器学习集成,以便实现实时的预测性分析。
64 4
|
2月前
|
机器学习/深度学习 数据可视化 搜索推荐
【python机器学习】python电商数据K-Means聚类分析可视化(源码+数据集+报告)【独一无二】
【python机器学习】python电商数据K-Means聚类分析可视化(源码+数据集+报告)【独一无二】
|
2月前
|
机器学习/深度学习 数据采集 数据可视化
基于机器学习的一线城市租房价格预测分析与实现,实现三种算法预测
本文通过数据采集、处理、特征选择和机器学习建模,对一线城市租房价格进行预测分析,比较了随机森林、一元线性回归和多元线性回归模型,并发现随机森林模型在预测租房价格方面表现最佳,为租房市场参与者提供决策支持。