精华内容
下载资源
问答
  • 3.8.1梯度法 ...采用梯度法求解的基本思想 对感知器算法 式中的w(k)、xk随迭代次数k而变,是变量。 定义一个对错误分类敏感的准则函数J(w, x)。先任选一个初始权向量w(1),计算准则函数J的梯...

    3.8.1梯度法

    定义:

    梯度是一个向量,它的最重要性质就是指出了函数f在其自变量y增加时最大增长率的方向。

    负梯度指出f的最陡下降方向 利用这个性质,可以设计一个迭代方案来寻找函数的最小值。

    采用梯度法求解的基本思想

    对感知器算法

    式中的w(k)、xk随迭代次数k而变,是变量。 定义一个对错误分类敏感的准则函数J(w, x)。先任选一个初始权向量w(1),计算准则函数J的梯度,然后从w(1)出发,在最陡方向(梯度方向)上移动某一距离得到下一个权向量w(2) 。

    讨论

      若正确地选择了准则函数J(w,x),则当权向量w是一个解时,J达到极小值(J的梯度为零)。由于权向量是按J的梯度值减小,因此这种方法称为梯度法(最速下降法)。

      为了使权向量能较快地收敛于一个使函数J极小的解,C值的选择是很重要的。

      若C值太小,则收敛太慢; 若C值太大,则搜索可能过头,引起发散。

     

    3.8.2固定增量的逐次调整算法

     

    过程说明:

      设已由前一步迭代得到w(k)的值。 读入模式样本xk,判别wT(k)xk是否大于0。

      在示意图中,xk界定的判别界面为wT(k)xk=0。

      当w(k)在判别界面的负区域时, wT(k)xk<0。 校正: w(k+1)= w(k)+ xk ,这里取C=1。 校正后, w(k+1)向量比w(k)向量更接近于模式xk所决定的正区域。

    讨论:

      若模式是线性可分的,选择合适的准则函数J(w,x),算法就能给出解。 若模式不是线性可分的,算法的结果就会来回摆动,得不到收敛。

    作业:

    采用梯度法和准则函数 式中实数b>0,试导出两类模式的分类算法。

     3.8.3 最小平方误差(LMSE)算法

    出发点

      感知器算法只是当被分模式可用一个特定的判别界面分开时才收敛,在不可分情况下,只要计算程序不终止,它就始终不收敛。 即使在模式可分的情况下,也很难事先算出达到收敛时所需要的迭代次数。 这样,在模式分类过程中,有时候会出现一次又一次迭代却不见收敛的情况,白白浪费时间。

      为此需要知道:发生迟迟不见收敛的情况时,到底是由于收敛速度过慢造成的呢,还是由于所给的训练样本集不是线性可分造成的呢?

      最小平方误差(LMSE)算法,除了对可分模式是收敛的以外,对于类别不可分的情况也能指出来。

    几个重要的公式:

            

                       

    小结

    固定增量算法:

      实现相对简单,可直接引伸到多类模式的分类情况,但未提供模式线性可分的测试特征; LMSE算法:相对复杂,需要对XTX求逆(维数高时求逆比较困难),但对两类情况,提供了线性可分的测试特征。

     

     

    转载于:https://www.cnblogs.com/chihaoyuIsnotHere/p/9789252.html

    展开全文
  • 读完本文,你可以去力扣拿下如下题目:25.K个一组翻转链表-----------之前文章「递归反转链表一部分」讲了如何递归地反转一部分链表,有读者就问如何迭代地反转链表,这篇文章解决...对于基本数据结构的算法问题...

    读完本文,你可以去力扣拿下如下题目:

    25.K个一组翻转链表

    -----------

    之前的文章「递归反转链表的一部分」讲了如何递归地反转一部分链表,有读者就问如何迭代地反转链表,这篇文章解决的问题也需要反转链表的函数,我们不妨就用迭代方式来解决。

    本文要解决「K 个一组反转链表」,不难理解:

    1dd23c334553f4a3524215932b37e3d9.png

    这个问题经常在面经中看到,而且 LeetCode 上难度是 Hard,它真的有那么难吗?

    对于基本数据结构的算法问题其实都不难,只要结合特点一点点拆解分析,一般都没啥难点。下面我们就来拆解一下这个问题。

    一、分析问题

    首先,前文学习数据结构的框架思维提到过,链表是一种兼具递归和迭代性质的数据结构,认真思考一下可以发现这个问题具有递归性质

    什么叫递归性质?直接上图理解,比如说我们对这个链表调用 reverseKGroup(head, 2),即以 2 个节点为一组反转链表:

    b28ab7a4d746b5b38217e9c6c22599b1.png

    如果我设法把前 2 个节点反转,那么后面的那些节点怎么处理?后面的这些节点也是一条链表,而且规模(长度)比原来这条链表小,这就叫子问题

    c63fc36af810de6220a4e007c3ee8e49.png

    我们可以直接递归调用 reverseKGroup(cur, 2),因为子问题和原问题的结构完全相同,这就是所谓的递归性质。

    发现了递归性质,就可以得到大致的算法流程:

    1、先反转以 head 开头的 k 个元素

    870247fc42a873829a6458fded19a102.png

    2、将第 k + 1 个元素作为 head 递归调用 reverseKGroup 函数

    7291646d6e6ae79f2dc97b4d515a06d4.png

    3、将上述两个过程的结果连接起来

    0f0a8b5a18e785af6623ce02b14f62d3.png

    整体思路就是这样了,最后一点值得注意的是,递归函数都有个 base case,对于这个问题是什么呢?

    题目说了,如果最后的元素不足 k 个,就保持不变。这就是 base case,待会会在代码里体现。

    二、代码实现

    首先,我们要实现一个 reverse 函数反转一个区间之内的元素。在此之前我们再简化一下,给定链表头结点,如何反转整个链表?

    // 反转以 a 为头结点的链表
    ListNode reverse(ListNode a) {
        ListNode pre, cur, nxt;
        pre = null; cur = a; nxt = a;
        while (cur != null) {
            nxt = cur.next;
            // 逐个结点反转
            cur.next = pre;
            // 更新指针位置
            pre = cur;
            cur = nxt;
        }
        // 返回反转后的头结点
        return pre;
    }
    

    171769c35c2a1c1a1282c926a07dec20.gif

    这次使用迭代思路来实现的,借助动画理解应该很容易。

    「反转以 a 为头结点的链表」其实就是「反转 a 到 null 之间的结点」,那么如果让你「反转 ab 之间的结点」,你会不会?

    只要更改函数签名,并把上面的代码中 null 改成 b 即可:

    /** 反转区间 [a, b) 的元素,注意是左闭右开 */
    ListNode reverse(ListNode a, ListNode b) {
        ListNode pre, cur, nxt;
        pre = null; cur = a; nxt = a;
        // while 终止的条件改一下就行了
        while (cur != b) {
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        // 返回反转后的头结点
        return pre;
    }
    

    PS:我认真写了 100 多篇原创,手把手刷 200 道力扣题目,全部发布在 labuladong的算法小抄,持续更新。建议收藏,按照我的文章顺序刷题,掌握各种算法套路后投再入题海就如鱼得水了。

    现在我们迭代实现了反转部分链表的功能,接下来就按照之前的逻辑编写 reverseKGroup 函数即可:

    ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        // 区间 [a, b) 包含 k 个待反转元素
        ListNode a, b;
        a = b = head;
        for (int i = 0; i < k; i++) {
            // 不足 k 个,不需要反转,base case
            if (b == null) return head;
            b = b.next;
        }
        // 反转前 k 个元素
        ListNode newHead = reverse(a, b);
        // 递归反转后续链表并连接起来
        a.next = reverseKGroup(b, k);
        return newHead;
    }
    

    解释一下 for 循环之后的几句代码,注意 reverse 函数是反转区间 [a, b),所以情形是这样的:

    810e0cbe797d6b8a5a7f521367e247d5.png

    递归部分就不展开了,整个函数递归完成之后就是这个结果,完全符合题意:

    60c2f92ed4015c0fcaa014fe92cad185.png

    三、最后说两句

    从阅读量上看,基本数据结构相关的算法文章看的人都不多,我想说这是要吃亏的。

    大家喜欢看动态规划相关的问题,可能因为面试很常见,但就我个人理解,很多算法思想都是源于数据结构的。我们公众号的成名之作之一,「学习数据结构的框架思维」就提过,什么动规、回溯、分治算法,其实都是树的遍历,树这种结构它不就是个多叉链表吗?你能处理基本数据结构的问题,解决一般的算法问题应该也不会太费事。

    那么如何分解问题、发现递归性质呢?这个只能多练习,也许后续可以专门写一篇文章来探讨一下,本文就到此为止吧,希望对大家有帮助!

    _____________

    我的 在线电子书 有 100 篇原创文章,手把手带刷 200 道力扣题目,建议收藏!对应的 GitHub 算法仓库 已经获得了 70k star,欢迎标星!

    展开全文
  • 梯度下降算法

    2021-04-15 16:01:14
    本文将从一个下山的场景开始,先提出梯度下降算法的基本思想,进而从数学上解释梯度下降算法的原理,解释为什么要用梯度,最后实现一个简单的梯度下降算法的实例! 2. 基本思想 假设我们爬山,如果想最快的上到山顶...

    1. 概述

    梯度下降(gradient descent)在机器学习中应用十分的广泛,不论是在线性回归还是Logistic回归中,它的主要目的是通过迭代找到目标函数的最小值,或者收敛到最小值。 本文将从一个下山的场景开始,先提出梯度下降算法的基本思想,进而从数学上解释梯度下降算法的原理,解释为什么要用梯度,最后实现一个简单的梯度下降算法的实例!

    2.梯度下降法

    首先我们要思考一个问题

    1. 梯度下降是干什么的?
      梯度下降的目的就是求函数的极小值点,例如在 矩阵分解 或是 线性回归 学习中都要用到梯度下降算法最后我会举例来告诉大家,梯度下降都如何应用
    2. 我们为什么要学习?
      假设函数y=f(x1,x2,…,xn) 只有一个极小点。初始给定参数为 X(x10,x20,…,xn0)。从这个点如何搜索才能找到原函数的极小值点?
      梯度下降算法就可以为我们解决上述问题

    梯度下降其实就是我们学习人工智能算法的一个基本算法,譬如我们小学开始接触数学时候我们学习加减乘除,最基本的算法

    2.1场景设定

    我们设定场景来帮助理解
    梯度下降法的基本思想可以类比为一个下山的过程。

    假设这样一个场景:一个人被困在山上,需要从山上下来(找到山的最低点,也就是山谷)。但此时山上的浓雾很大,导致可视度很低;因此,下山的路径就无法确定,必须利用自己周围的信息一步一步地找到下山的路。这个时候,便可利用梯度下降算法来帮助自己下山。怎么做呢,首先以他当前的所处的位置为基准,寻找这个位置最陡峭的地方,然后朝着下降方向走一步,然后又继续以当前位置为基准,再找最陡峭的地方,再走直到最后到达最低处;同理上山也是如此,只是这时候就变成梯度上升算法了
    在这里插入图片描述

    2.2梯度下降

    梯度下降的基本过程就和下山的场景很类似。

    首先,我们有一个可导的函数。这个函数就代表着一座山。我们的目标就是找到这个函数的最小值,也就是山底。根据之前的场景假设,最快的下山的方式就是找到当前位置最陡峭的方向,然后沿着此方向向下走,对应到函数中,就是找到给定点的梯度 ,然后朝着梯度相反的方向,就能让函数值下降的最快!因为梯度的方向就是函数之变化最快的方向(在后面会详细解释)

    所以,我们重复利用这个方法,反复求取梯度,最后就能到达局部的最小值,这就类似于我们下山的过程。而求取梯度就确定了最陡峭的方向,也就是场景中测量方向的手段。那么为什么梯度的方向就是最陡峭的方向呢?首先梯度是什么

    2.2.1 梯度

    • 一阶函数里梯度就是表示某一函数在该点处的方向导数沿 着该方向取得较大值,即函数在当前位置的导数
      如果函数为一元函数,梯度就是该函数的导数。
      在这里插入图片描述
      如果为二元函数,梯度定义为:
      在这里插入图片描述

    在这里插入图片描述

    • 多元函数中,如上图我们可以看到,梯度就是分别对每个变量进行偏导,然后用逗号分割开,梯度是用<>包括起来,说明梯度其实一个向量,向量有方向,梯度的方向就指出了函数在给定点的上升最快的方向。

    这也就说明了为什么我们需要千方百计的求取梯度!我们需要到达山底,就需要在每一步观测到此时最陡峭的地方,梯度就恰巧告诉了我们这个方向。梯度的方向是函数在给定点上升最快的方向,那么梯度的反方向就是函数在给定点下降最快的方向, 这正是我们所需要的。所以我们只要沿着梯度的方向一直走,就能走到局部的最低点!

    2.3 数学解释

    2.3.1 核心公式

    在这里插入图片描述
    此公式的意义是:f 是关于Θ的一个函数,我们当前所处的位置为Θ0点,要从这个点走到 f 的最小值点,也就是山底。首先我们先确定前进的方向,也就是梯度的反向,然后走一段距离的步长,也就是η,走完这个段步长,就到达了Θ这个点!

    2.3.1 η

    • η 在梯度下降算法中被称作为学习率或者步长,意味着我们可以通过η来控制每一步走的距离,步长太大走的就容易偏离路线,其实就是不要走太快,错过了最低点。同时也要保证不要走的太慢,导致太阳下山了,还没有走到山下。所以η的选择在梯度下降法中往往是很重要的!η不能太大也不能太小,太小的话,可能导致迟迟走不到最低点,太大的话,会导致错过最低点!
      步长η大小问题我们暂时不论,文末思考问题里有解释

    2.3.2 负梯度

    • 为了使函数下降最快,我们需要让函数朝着负梯度方向下,我们在前文提到,梯度的方向实际就是函数在此点上升最快的方向, 而我们需要朝着下降最快的方向走,自然就是负的梯度的方向,所以此处需要加上负号;那么如果时上坡,也就是梯度上升算法,当然就不需要添加负号了。

    2.4梯度下降法的一般步骤

    在这里插入图片描述

    上述第4步,除了设定阈值外也可选择一定的迭代次数进行迭代

    2.5实例

    2.5.1一元函数梯度下降

    为了我们更好理解梯度下降算法,先看几个例子吧!
    在这里插入图片描述

    在这里插入图片描述
    这是我手工推到的例子
    在这里插入图片描述

    2.5.2代码实现(python)

    #f(x)=x^2
    # -*- coding: utf-8 -*-
    import numpy as np
    import matplotlib.pyplot as plt
    #定义原函数f(x)=x^2
    def f(x):
        return np.power(x, 2)
    #定义函数求导公式1
    def d_f_1(x):
        return 2.0 * x
    #定义函数求导公式2
    def d_f_2(f, x, delta=1e-4):
        return (f(x+delta) - f(x-delta)) / (2 * delta)
    xs = np.arange(-10, 11)# 限制自变量x的范围
    plt.plot(xs, f(xs))#绘图
    plt.show()
    learning_rate = 0.1# 学习率(步长)
    max_loop = 30# 迭代次数
    x_init = 10.0# x初始值
    x = x_init
    lr = 0.01# ε值,不过我们下面用的是迭代次数限制
    for i in range(max_loop):
        # d_f_x = d_f_1(x)
        d_f_x = d_f_2(f, x)
        x = x - learning_rate * d_f_x
        print(x)
     
    
    print('initial x =', x_init)
    print('arg min f(x) of x =', x)
    print('f(x) =', f(x))
    

    运行结果如下

    每次迭代,x的更新值
    在这里插入图片描述

    在这里插入图片描述

    理解,但简单的一元函数已经不多见啦,当涉及多元函数时候我们的算法如何进行呢?(其实万变不离其宗)

    最大的变化就是在求函数梯度时我们求得是多元函数偏导数学知识,如果没学过,先学习

    2.5.3多元函数梯度下降

    我们结合线性回归来举例子运用多元函数梯度下降算法
    (线性回归我做成了新板块内容,下面是链接)
    https://blog.csdn.net/m0_56689123/article/details/115771086?spm=1001.2014.3001.5501

    2.5.4矩阵分解梯度下降

    我们再结合矩阵分解实例来运用梯度下降
    https://blog.csdn.net/m0_56689123/article/details/115421220?spm=1001.2014.3001.5501

    3.梯度下降存在的问题

    1. 当靠近极小值时收敛速度减慢
    2. 下降过程可能会出现 “之字形” 地下降

    1.首先我们思考为什么梯度下降法在计算函数极小值时靠近极小值时收敛速度减慢?

    在这里插入图片描述
    我们可以看到x的收敛速度减慢了,收敛速度其实也可以看成每次迭代更新x,前后x的差值,即Δχ\Delta\chi。这是因为梯度下降过程中每次x更新后梯度值(也就是导数值)减小了,因此靠近极小值时收敛速度减慢,下看公式进行理解

    在这里插入图片描述
    其实 η\eta\cdot\bigtriangledownf(θ0\theta_{0})=Δχ\Delta\chi

    2.当我们设定的步长参数较大或者较小时会出现以下情况。
    在这里插入图片描述

    η\eta过大就会出现之字形的下降路线,η\eta过小时下降缓慢,所以我们在给定步长参数时让步长参数尽量适中。

    展开全文
  • 2.梯度下降算法的基本思想 2.1场景假设 我们从一个下山的场景先来理解一下梯度下降算法的基本思想: 假设这样一个场景:一个人被困在山上,需要从山上下来(找到山的最低点,也就是山谷)。但此时山上的浓雾很大,...

    1.概念

    梯度下降是干什么的?

    它的主要目的就是通过迭代找到目标函数的最小值。

    2.梯度下降算法的基本思想

    2.1场景假设

    我们从一个下山的场景先来理解一下梯度下降算法的基本思想:

    假设这样一个场景:一个人被困在山上,需要从山上下来(找到山的最低点,也就是山谷)。但此时山上的浓雾很大,导致可视度很低。因此,下山的路径就无法确定,他必须利用自己周围的信息去找到下山的路径。这个时候,他就可以利用梯度下降算法来帮助自己下山。

    具体来说就是,以他当前的所处的位置为基准,寻找这个位置最陡峭的地方,然后朝着山的高度下降的地方走,同理,如果我们的目标是上山,也就是爬到山顶,那么此时应该是朝着最陡峭的方向往上走。然后每走一段距离,都反复采用同一个方法,最后就能成功的抵达山谷。

    2.2梯度下降算法的理解

    梯度下降的基本过程就和下山的场景很类似。

    首先,我们有一个可微分的函数。这个函数就代表着一座山。我们的目标就是找到这个函数的最小值,也就是山底。根据之前的场景假设,最快的下山的方式就是找到当前位置最陡峭的方向,然后沿着此方向向下走,对应到函数中,就是找到给定点的梯度 ,然后朝着梯度相反的方向,就能让函数值下降的最快!

    因为梯度的方向就是函数变化最快的方向,所以,我们重复利用这个方法,反复求取梯度,最后就能到达局部的最小值,这就类似于我们下山的过程。而求取梯度就确定了最陡峭的方向,也就是场景中测量方向的手段。

     

    小知识:那么为什么梯度的方向就是最陡峭的方向呢?

    梯度的本意是一个向量(矢量),表示某一函数在该点处的方向导数沿着该方向取得最大值,即函数在该点处沿着该方向(此梯度的方向)变化最快,变化率最大(为该梯度的模)。

    接下来,我们从微分开始讲起:

    2.2.1微分

    1.微分是什么,如何理解?

    可以有不同的角度,最常用的两种是:

    • 函数图像中,某点的切线的斜率
    • 函数的变化率

    2.微分的例子

    # 单变量的微分:

    # 多变量的微分(即分别对每个变量进行求微分):

    2.2.2梯度

    梯度实际上就是多变量微分的一般化。

    例如:

    我们可以看到,梯度就是分别对每个变量进行微分,然后用逗号分割开,梯度是用<>包括起来,说明梯度其实一个向量。

    梯度的意义:

    • 在单变量的函数中,梯度其实就是函数的微分,代表着函数在某个给定点的切线的斜率
    • 在多变量函数中,梯度是一个向量,向量有方向,梯度的方向就指出了函数在给定点的上升最快的方向

    所以这也就说明了为什么我们需要千方百计的求取梯度!我们需要到达山底,就需要在每一步观测到此时最陡峭的地方,梯度就恰巧告诉了我们这个方向。

    梯度的方向是函数在给定点上升最快的方向,那么梯度的反方向就是函数在给定点下降最快的方向,这正是我们所需要的。所以我们只要沿着梯度的方向一直走,就能走到局部的最低点!

    3.梯度下降算法的数学解释

    下面我们就开始从数学上解释梯度下降算法的计算过程和思想!

    此公式的意义是:

    J是关于Θ的一个函数,我们当前所处的位置为Θ0点,要从这个点走到J的最小值点,也就是山底。首先我们先确定前进的方向,也就是梯度的反向,然后走一段距离的步长,也就是α,走完这个段步长,就到达了Θ1这个点!

    下面就这个公式的几个常见的疑问:

    • α是什么含义?
      α在梯度下降算法中被称作为学习率或者步长,意味着我们可以通过α来控制每一步走的距离,以保证不要步子跨的太大,其实就是不要走太快,错过了最低点。同时也要保证不要走的太慢,导致太阳下山了,还没有走到山下。所以α的选择在梯度下降法中往往是很重要的!α不能太大也不能太小,太小的话,可能导致迟迟走不到最低点,太大的话,会导致错过最低点!

     

    • 为什么要梯度要乘以一个负号?
      梯度前加一个负号,就意味着朝着梯度相反的方向前进!我们在前文提到,梯度的方向实际就是函数在此点上升最快的方向!而我们需要朝着下降最快的方向走,自然就是负的梯度的方向,所以此处需要加上负号

    4.梯度下降算法的实例

    我们已经基本了解了梯度下降算法的计算过程,那么我们就来看几个梯度下降算法的小实例,例如下图:

    比如刚才的多变量函数下降,可以用python编写程序检验一下

    def f(x,y):
        return x*x+y*y
    def g(x):
        return 2*x
    x=1
    y=3
    for i in range(2000):
        x=x-0.1*g(x)
        y=y-0.1*g(y)
        print(f(x,y))

    5.代码实现

    下面我们将用python实现一个简单的梯度下降算法。场景是一个简单的线性回归的例子:假设现在我们有一系列的点,如下图所示:

    我们将用梯度下降法来拟合出这条直线!

    首先,我们需要定义一个代价函数,在此我们选用均方误差代价函数(也称平方误差代价函数)

    此公式中

    (1)m是数据集中数据点的个数,也就是样本数
    (2)½是一个常量,这样是为了在求梯度的时候,二次方乘下来的2就和这里的½抵消了,自然就没有多余的常数系数,方便后续的计算,同时对结果不会有影响
    (3)y 是数据集中每个点的真实y坐标的值,也就是类标签
    (4)h 是我们的预测函数(假设函数),根据每一个输入x,根据Θ 计算得到预测的y值,即

    我们可以根据代价函数看到,代价函数中的变量有两个,所以是一个多变量的梯度下降问题,求解出代价函数的梯度,也就是分别对两个变量进行微分

    明确了代价函数和梯度,以及预测的函数形式。我们就可以开始编写代码了。但在这之前,需要说明一点,就是为了方便代码的编写,我们会将所有的公式都转换为矩阵的形式,python中计算矩阵是非常方便的,同时代码也会变得非常的简洁。
    为了转换为矩阵的计算,我们观察到预测函数的形式

    我们有两个变量,为了对这个公式进行矩阵化,我们可以给每一个点x增加一维,这一维的值固定为1,这一维将会乘到Θ0上。这样就方便我们统一矩阵化的计算

    然后我们将代价函数和梯度转化为矩阵向量相乘的形式

     

    首先,我们需要定义数据集和学习率

    from numpy import *
    # 数据集大小 即20个数据点
    m = 20
    # x的坐标以及对应的矩阵
    X0 = ones((m, 1))  # 生成一个m行1列的向量,也就是x0,全是1
    X1 = arange(1, m+1).reshape(m, 1)  # 生成一个m行1列的向量,也就是x1,从1到m
    X = hstack((X0, X1))  # 按照列堆叠形成数组,其实就是样本数据
    # 对应的y坐标
    Y = array([
        3, 4, 5, 5, 2, 4, 7, 8, 11, 8, 12,
        11, 13, 13, 16, 17, 18, 17, 19, 21
    ]).reshape(m, 1)
    # 学习率
    alpha = 0.01

    接下来我们以矩阵向量的形式定义代价函数和代价函数的梯度

    # 定义代价函数
    def cost_function(theta, X, Y):
        diff = dot(X, theta) - Y  # dot() 数组需要像矩阵那样相乘,就需要用到dot()
        return (1/(2*m)) * dot(diff.transpose(), diff)
    
    
    # 定义代价函数对应的梯度函数
    def gradient_function(theta, X, Y):
        diff = dot(X, theta) - Y
        return (1/m) * dot(X.transpose(), diff)

    最后就是算法的核心部分,梯度下降迭代计算

    # 梯度下降迭代
    def gradient_descent(X, Y, alpha):
        theta = array([1, 1]).reshape(2, 1)
        gradient = gradient_function(theta, X, Y)
        while not all(abs(gradient) <= 1e-5):
            theta = theta - alpha * gradient
            gradient = gradient_function(theta, X, Y)
        return theta
    
    
    optimal = gradient_descent(X, Y, alpha)
    print('optimal:', optimal)
    print('cost function:', cost_function(optimal, X, Y)[0][0])
    

    当梯度小于1e-5时,说明已经进入了比较平滑的状态,类似于山谷的状态,这时候再继续迭代效果也不大了,所以这个时候可以退出循环!
    所拟合出的直线如下:

    全部代码如下:

    from numpy import *
    # 数据集大小 即20个数据点
    m = 20
    # x的坐标以及对应的矩阵
    X0 = ones((m, 1))  # 生成一个m行1列的向量,也就是x0,全是1
    X1 = arange(1, m+1).reshape(m, 1)  # 生成一个m行1列的向量,也就是x1,从1到m
    X = hstack((X0, X1))  # 按照列堆叠形成数组,其实就是样本数据
    # 对应的y坐标
    Y = array([
        3, 4, 5, 5, 2, 4, 7, 8, 11, 8, 12,
        11, 13, 13, 16, 17, 18, 17, 19, 21
    ]).reshape(m, 1)
    # 学习率
    alpha = 0.01
    
    
    # 定义代价函数
    def cost_function(theta, X, Y):
        diff = dot(X, theta) - Y  # dot() 数组需要像矩阵那样相乘,就需要用到dot()
        return (1/(2*m)) * dot(diff.transpose(), diff)
    
    
    # 定义代价函数对应的梯度函数
    def gradient_function(theta, X, Y):
        diff = dot(X, theta) - Y
        return (1/m) * dot(X.transpose(), diff)
    
    
    # 梯度下降迭代
    def gradient_descent(X, Y, alpha):
        theta = array([1, 1]).reshape(2, 1)
        gradient = gradient_function(theta, X, Y)
        while not all(abs(gradient) <= 1e-5):
            theta = theta - alpha * gradient
            gradient = gradient_function(theta, X, Y)
        return theta
    
    
    optimal = gradient_descent(X, Y, alpha)
    print('optimal:', optimal)
    print('cost function:', cost_function(optimal, X, Y)[0][0])
    
    
    # 根据数据画出对应的图像
    def plot(X, Y, theta):
        import matplotlib.pyplot as plt
        ax = plt.subplot(111)  # 这是我改的
        ax.scatter(X, Y, s=30, c="red", marker="s")
        plt.xlabel("X")
        plt.ylabel("Y")
        x = arange(0, 21, 0.2)  # x的范围
        y = theta[0] + theta[1]*x
        ax.plot(x, y)
        plt.show()
    
    
    plot(X1, Y, optimal)
    

    我基本上是基于下面的链接https://www.jianshu.com/p/c7e642877b0e和https://blog.csdn.net/qq_41800366/article/details/86583789进行的学习,写这篇也就是为了给自己加深一下印象。

    展开全文
  • 本文将从一个下山的场景开始,先提出梯度下降算法的基本思想,进而从数学上解释梯度下降算法的原理,解释为什么要用梯度,最后将此算法应用于具体的拟合直线的线性回归中。2 梯度下降算法2.1场景假设想象一...
  • 随机并行梯度下降(Stochastic Parallel Gradient Descent,简称SPGD)算法优点:参数简单、收敛性和稳定性较好,并且容易实现基本思想:选取目标函数负梯度方向(最速下降方向)作为每步迭代的搜索方向,沿此方向前进...
  • 1. 概述 梯度下降(gradient descent)在机器学习中应用... 本文将从一个下山的场景开始,先提出梯度下降算法的基本思想,进而从数学上解释梯度下降算法的原理,解释为什么要用梯度,最后实现一个简单的梯度下降算...
  • 敏捷在软件开发过程中是一个非常著名的术语,它背后的基本思想很简单:快速构建一些东西,然后得到一些反馈,根据反馈做出改变,重复此过程。目标是让产品更贴合用,让用户做出反馈,以获得设计开发出的产品与优秀的...
  • 迭代法是求方程近似根一个重要方法,也是计算方法中一种基本方法,它的算法简单,是用于求方程或方程组近似根一种常用的算法设计方法。 牛顿迭代法是求方程根重要方法之一,其最大优点是在方程f(x) = 0...
  • 敏捷在软件开发过程中是一个非常著名的术语,它背后的基本思想很简单:快速构建一些东西,然后得到一些反馈,根据反馈做出改变,重复此过程。目标是让产品更贴合用,让用户做出反馈,以获得设计开发出的产品与优秀的...
  • 本文将从一个下山的场景开始,先提出梯度下降算法的基本思想,进而从数学上解释梯度下降算法的原理,解释为什么要用梯度,最后实现一个简单的梯度下降算法的实例! 2. 梯度下降算法 2.1 场景假设 梯度下降法的基本思...
  • 基本思想:从某些初始解出发,迭代寻找最优参数值,每次迭代中在当前点计算梯度,根据函数值下降最快方向确定搜索方向,梯度为0则达到局部极小。 J是代价函数,w是权重,b是一个常数类似于阈值,当我们从一个...
  • 本文将从一个下山的场景开始,先提出梯度下降算法的基本思想,进而从数学上解释梯度下降算法的原理,解释为什么要用梯度,最后实现一个简单的梯度下降算法的实例! 2.场景假设 梯度下降法的基本思想可以类比为一个...
  • 本文将从一个下山的场景开始,先提出梯度下降算法的基本思想,进而从数学上解释梯度下降算法的原理,解释为什么要用梯度,最后实现一个简单的梯度下降算法的实例! 2.梯度下降算法 2.1场景假设 梯度下降法的基本思想...
  • svm随机次梯度下降算法-pegasos

    万次阅读 2017-04-10 21:22:45
    基本思想使用随机梯度下降直接解SVM原始问题。摘要本文研究和分析了基于随机梯度下降的SVM优化算法,简单且高效。(Ο是渐进上界,Ω是渐进下界)本文证明为获得一定准确率精度ϵ \epsilon所需的迭代次数满足O(1ϵ...
  • 牛顿迭代优化

    2017-01-12 16:23:13
    引用zhiyong_will博主的工作,仅进行小范围修改 ...牛顿法的基本思想是利用迭代点处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近似,然后把二次模型的极小点作为新的迭代点,并
  • 敏捷在软件开发过程中是一个非常著名的术语,它背后的基本思想很简单:快速构建一些东西,然后得到一些反馈,根据反馈做出改变,重复此过程。目标是让产品更贴合用,让用户做出反馈,以获得设计开发出的产品与优秀的...
  • 感知器算法

    2017-12-23 21:21:00
    这种算法的基本思想是: 对于初始的或者迭代中的增广权矢量W,用训练模式检验其合理性。当不合理时,对其进行校正,利用梯度下降法。梯度下降法也是人工神经网络中线性阈值神经元的学习算法。 感知器算法的基本步骤...
  • 伪逆学习算法伪逆学习算法(PIL)伪逆学习算法基本思想伪逆学习算法优点伪逆学习算法分析伪逆矩阵举例 伪逆学习算法(PIL) 一种训练前馈神经网络快速算法。 深层多层神经网络训练通常使用梯度下降的变种算法。但是...
  • 模拟退火算法

    2021-03-01 13:32:34
    它有四个基本概念:(1)目标函数,对于最大值问题,使目标函数乘以-1即可(2)温度,它随着算法的迭代逐步下降。一方面,温度用于限制SA产生的新解与当前解之间的距离,即SA的搜索范围;另一方面,温度决定了SA以多...
  • 浅谈梯度算法

    2020-07-12 14:58:19
    ​ 将梯度下降算法的过程可以类比人从山顶以最快的方法下山的过程。这座山就是所给的函数,然后确定目标找到这个函数的最小值(就是山底)。方向导数最大值即与梯度方向相同。故函数值随着下山人的位置变化(减少)...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 157
精华内容 62
关键字:

下降迭代算法的基本思想