精华内容
下载资源
问答
  • 前向算法(Forward Algorithm)

    万次阅读 2012-10-16 10:39:48
    本文直接举实例说明ForwardAlgorithm (前向算法) 由马尔科夫模型MM可知:对于一个系统,由一个状态转至另一个状态的转换过程中,存在着转移概率,并且这种转移概率可以依据其紧接的前一种状态推算出来,与该系统的...

    本文直接举实例说明ForwardAlgorithm (前向算法)

    由马尔科夫模型MM可知:对于一个系统,由一个状态转至另一个状态的转换过程中,存在着转移概率,并且这种转移概率可以依据其紧接的前一种状态推算出来,与该系统的原始状态和此次转移前的马尔可夫过程无关。

    隐马尔可夫模型(HiddenMarkov modelsHMM)是马尔可夫链的一种,它的状态不能直接观察到,但能通过观测向量序列观察到,每个观测向量都是通过某些概率密度分布表现为各种状态,每一个观测向量是由一个具有相应概率密度分布的状态序列产生。

     

    假设连续观察3天的海藻湿度为(Dry,Damp, Soggy),求出该观察序列的概率。天气只有三类(Sunny,Cloudy, Rainy),而且海藻湿度和天气有一定的关系。

    已知:

    1.      隐藏的状态:Sunny, Cloudy, Rainy;海藻湿度有四类{Dry,Dryish, Damp, Soggy }

    2.      观察状态序列:{ Dry, Damp, Soggy };

    3.      初始状态序列:Sunny(0.63), Cloudy(0.17),Rainy(0.20);

    4.      状态转移矩阵:

     

     

    Sunny

    Cloudy

    Rainy

    Sunny

    0.5

    0.375

    0.125

    Cloudy

    0.25

    0.125

    0.625

    Rainy

    0.25

    0.375

    0.375

    Cloudy(昨天)->Sunny(今天)的概率是0.25;

    Sunny(昨天)->Rainy(今天)的概率是0.125.

     

    5.      混淆矩阵(海藻湿度与天气的相关性):

     

     

    Dry

    Dryish

    Damp

    Soggy

    Sunny

    0.6

    0.2

    0.15

    0.05

    Cloudy

    0.25

    0.25

    0.25

    0.25

    Rainy

    0.05

    0.10

    0.35

    0.50

    观察到海藻湿度Dry,则当天Sunny的概率是0.6;Cloudy的概率是0.25;而当天Rainy的概率是0.05.

     

    How to calculate the probability of this observation list?

    即统计P(observation|Sunny, Sunny, Sunny)+P(observation| Sunny, Sunny, Cloudy)+ P(observation| Sunny,Sunny, Rainy)+ P(observation| Sunny, Cloudy, Sunny) + P(observation| Sunny, Cloudy,Cloudy) + P(observation| Sunny, Cloudy, Rainy) + …

    总共的可能性有3^3种。

    实际由于马尔科夫模型,我们得知其实第二天的状况只取决于第一天,第三天的天气已经与第一天的天气没有关系了。

    我们可以先求P(Day1-Sunny),P(Day1-Cloudy), P(Day1-Rainy),Day1的海藻湿度是Dry.

    P(Day1-Sunny) = 0.63*0.6;

    P(Day1-Cloudy)=0.17*0.25;

    P(Day1-Rain)=0.20*0.05;

    继续求P(Day2-Sunny), P(Day2-Cloudy),P(Day2-Rainy), Day2的海藻湿度是Damp.

    P(Day2-Suny)= (P(Day1-Sunny)*0.5 + P(Day1-Cloudy)*0.25 +P(Day1-Rainy)*0.25)* 0.15

    P(Day2-Cloudy) = (P(Day1-Sunny)*0.375+ P(Day1-Cloudy)*0.125 + P(Day1-Rainy)*0.625) * 0.25

    P(Day2-Rainy) =(P(Day1-Sunny)*0.125+ P(Day1-Cloudy)*0.625 + P(Day1-Rainy)*0.375)* 0.35

    同理继续求第三日的各天气概率,Day3的海藻湿度是Soggy.

    P(Day3-Suny)= (P(Day2-Sunny)*0.5 + P(Day1-Cloudy)*0.25 +P(Day1-Rainy)*0.25)* 0.05

    P(Day3-Cloudy) = (P(Day2-Sunny)*0.375+ P(Day1-Cloudy)*0.125 + P(Day1-Rainy)*0.625) * 0.25

    P(Day3-Rainy) =(P(Day2-Sunny)*0.125+ P(Day1-Cloudy)*0.625 + P(Day1-Rainy)*0.375)* 0.50

    推出:

    P(observation list) =P(Day3-Sunny)+P(Day3-Cloudy)+P(Day3-Rainy) = 0.030319

     

    参考:

    http://luyifanlife.blog.163.com/blog/static/20024105720126272311612/

     

    展开全文
  • HMM前向后向算法

    千次阅读 2018-06-12 21:52:09
    HMM前向后向算法HMM的三个基本问题中,对于HMM参数的学习是最难的。对于给定的观测序列O,如何估计模型参数使得P(O|λ)最大。目前为止,可能并不存在一种方法使得P(O|λ)最大,但是接下里的前向后向算法是能够使上述...

    HMM前向后向算法

    HMM的三个基本问题中,对于HMM参数的学习是最难的。对于给定的观测序列O,如何估计模型参数使得P(O|λ)最大。目前为止,可能并不存在一种方法使得P(O|λ)最大,但是接下里的前向后向算法是能够使上述问题得到局部最优。

    首先:假设给定模型λ和观测序列,计算观测序列出现的概率P(O|λ)。令隐含状态序列I={i1,i2...iT};观测序列是O={O1,O2,...OT},计算联合概率P(O,I|λ),然后将所有可能的I进行求和,就是P(O|λ)。

    隐含状态序列I的概率是:

    当固定隐含状态I和给定模型参数时,观测序列为O={O1,O2,...OT}的概率是P(O|I,λ)


    O和I同时出现的概率是:


    对所有的I进行求和:


    ---------(1)

    (1)  式计算量太大,于是才有之前的前向算法和后向算法。

     

     

    给定模型λ和观测序列O,在t时刻处于状态qi的概率:

    而且还有:

    回顾一下:前向概率的定义:

    给定HMM的参数λ,定义到t时刻的部分观测序列o1,o2..ot,且状态是qi的概率为前向概率:

    后向概率的定义:


    给定HMM的参数λ,在t时刻状态为qi的条件下,t+1到T的观测序列ot+1,ot+2..oT的概率为后向概率:

    P(it=qi,O|λ)的意思是:在给定HMM的参数λ,观测序列是O(O1,O2,...OT),在t时刻的状态为qi的概率。换句话理解就是:从1~t时刻,t时刻的状态为qi,输出是(O1,O2,...Ot),的概率,然后t时刻之后,在t时刻状态为qi,输出序列是(ot+1,ot+2..oT)的概率。

    1~t时刻的,输出是(O1,O2,...Ot),的概率:这不就是前向概率的定义么?

    t时刻之后,在t时刻状态为qi输出序列是(ot+1,ot+2..oT)的概率,这不就是后向概率么?

    于是就有:

    结合公式(1),(3),(6),可以得到:


    ----------(7)

    1.        

    给定模型参数λ和观测序列O,t时刻是qi,t+1时刻是qj的概率是:

    类似于公式(3):

     

    的意思是在给定HMM的参数下,观测序列是O,t时刻的状态是qi,t+1时刻的状态是qj的概率。

    这个概率=P(1~t时刻的输出序列O1,O2,...Ot,t时刻是qi|λ)*P(qi转移到t+1时刻的qj)*P(t+1时刻之后输出序列是ot+2,ot+3..oT|t+1时刻是qj, λ)*P(t+1时刻输出是Ot+1):

    这里面有好几个乘积,逐一解释:

    P(1~t时刻的输出序列O1,O2,...Ot,t时刻是qi|λ):这不就是t时刻的前向概率αt(i)么?

    P(qi转移到t+1时刻的qj):这不就是转移概率aij么?

    P(t+1时刻之后输出序列是ot+2,ot+3..oT|t+1时刻是qj,λ):这不就是t+1时刻的后向概率βt+1(i)么?

    (注意:t+1时刻的后续输出序列是ot+2,ot+3..oT,即下标是从t+2开始,不是t+1开始,请仔细理解后向概率的定义)

    前面少了Ot+1这个时间点的观测序列,因此要补上P(t+1时刻输出是Ot+1),而这个不就是bj(Ot+1)么?

    因此:

    从而根据(8),(9),(10)可以变换为:


    -----------(11)

    ---------(12)

    (12)式表示观测序列是O时,状态i出现的期望

    ---------(13)

    (13)式表示观测序列是O时,由状态i转移的期望

    ----------(14)

    (14)式表示观测序列是O时,由状态i转移到j的期望.

     

    2.       前向-后向算法(baum-welch)

    这里主要来推导非监督情况下的baum-welch算法。

    在只有观测序列时(只有O是已知的),如何估计HMM的参数λ使得P(O|λ)最大,前面已经讲过了,由于没有办法找到一种方法使得P(O|λ)全局收敛,baum-welch算法只能是局部最优。

    在公式(1)中有:

    观测序列是O (o1,o2,...oT),隐含状态是I{i1,i2.....iT},完全数据是(O,I)={ o1,o2,...oT , i1,i2.....iT}完全数据的对数似然函数是log(O,I|λ)。HMM的参数学习算法可以通过EM算法来实现。

    E-step:

    确定Q函数,即隐含变量的期望:


    ----------(16)

    (不太懂这个公式是如何计算来的)

    由于:

    ----------(17)

    因此有:


    ----------(18)

    M-step:

    极大化来计算参数A,B,π。

    对(18)式的三项分别进行极大化.

    第一项:

    其中:

    于是,写成拉格朗日函数如下:


    ----------(19)

    对(19)式求偏导:

    ----------(20)

    于是可以计算出:

    -----------(21)

    同时求和可以得到:

    ----------(22)

    将等式(22)带入到等式(21)中有:

    ----------(23)

    等式(18)第二项:

    -----------(24)

    约束条件是:

    同样让(24)变成拉格朗日函数式:

    ------------(25)

    做法与第一项最大化一致,最后计算的结果是:

    ----------(26)

    第三项:

    -----------(27)

    约束条件是:

    类似的,构建拉格朗日函数:

    ----------(28)

    对bj进行求偏导,并且令求偏导之后的函数为0,

    ----------(29)

    对于(29),如果t时刻,

    同时对j求和,然后可以计算得到:

    在时,(29)时左边才有意义,否则就是0,用来表示这种情况,于是可以计算bj

    以上(23),(26),(30)就是我们最终要的东西。

    再进一步:

    仔细看一下(23)和(7),这俩不是一回事儿么?(23)分子不就是说在给定λ情况下,观测序列是O,在t时刻是i的概率么?于是有,只不过现在t=1而已:

    ----------(31)

    同理:

    ----------(32)

    ----------(33)

    至此,baum-welch算法就已经推导完成了。

     


    展开全文
  • HMM——前向后向算法

    千次阅读 2015-09-19 20:29:14
    前向后向算法或者Baum-Welch,不太好理解

    1. 前言

    解决HMM的第二个问题:学习问题, 已知观测序列,需要估计模型参数,使得在该模型下观测序列 P(观测序列 | 模型参数)最大,用的是极大似然估计方法估计参数。

    根据已知观测序列和对应的状态序列,或者说只有观测序列,将学习过程分为监督和无监督学习方法

    主要参考《李航统计学习》、《PRML》

    2. 监督学习方法

    给定了s个长度相同的观测序列和对应的状态序列(相当于有s个样本,所有样本长度一样)


    然后我们需要做的就是统计三种频率:

    ① 在样本中,从t 时刻的各状态转移到 t+1时刻的各状态的频率,比如第一个状态转移到第二个状态共有3次,第2个状态转移到第三个状态共有10次,等。。。。。

    据此能够推导出状态转移概率


    ② 在样本中,每对(某个状态j,某个观测k)出现的频率,就是状态为j 观测为k的概率,即混淆矩阵


    ③在样本中,统计s个样本中初始状态为 的频率就是初始状态概率πi

    缺点就是:监督学习需要人工标注训练数据,代价高

    3.前向-后向算法

    3.1 目标

    其它称呼有:Baum-Welch算法

    主要针对只有观测序列没有对应的状态序列的情况

    这一部分在《统计学习方法》中推导的非常好,主要利用的是拉格朗日乘子法求解

    已知:训练数据是S个长度为T的观测序列,没有对应的状态序列

    求解:学习隐马尔科夫的参数,包括:转移矩阵、混淆矩阵、初始概率

    思路:

    因为HMM中引入了隐状态,所以设隐状态序列为I,那么HMM就可以当做一个具有隐变量的概率模型:


    其实这个式子就有点像一种边缘概率:


    只不过将这个概率加了一个条件,是在HMM的模型参数下计算的,就变成了条件概率。

    求解的时候利用E-M算法求解即可(EM中,E代表expectation,是求期望;M代表的是maximization,求极大;合起来EM算法就被称为期望值最大化算法)

    3.2 EM步骤简述

    摘自《统计学习方法》

    输入:观测变量数据Y,隐变量数据Z,联合分布 P(Y, Z | θ),条件分布 P( Z | Y , θ)

    输出:模型参数 θ

    步骤:

    ① 选择参数初值,开始迭代

    ② E步:记为第 i 次迭代参数θ的估计值,在第 i+1 次迭代E步,计算


    第二个等式的第二项是给定观测数据Y和当前的估计参数下隐变量数据Z的条件概率分布

    ③ M步:求使得极大化的θ,确定第 i+1 次迭代的参数的估计值


    ④ 重复第②和③步,直到收敛

    3.3求解HMM模型参数

    (1) 确定完全数据的对数似然函数

    观测数据:

    隐藏数据:

    完全数据:

    完全数据的对数似然函数就是

    ②EM算法之E:求Q函数


    式子中是HMM模型参数的当前估计值,λ 是要极大化的HMM模型参数

    对于前面一半,根据概率有向图的联合概率分布,我们知道



    两式相乘就可以得到:


    根据P(O,I | λ)可以将 Q 函数可以改写为:


    式中的求和是对所有训练数据的序列长度T进行的

    ③ EM算法之M:极大化Q函数求解模型参数π、A、B

    观察E步骤的式子发现三个参数刚好分别在三项中,所以单独对每一项求解就行了

    第一步先求π:

    注意,π只与初始状态有关,第一项可以写成


    意思就是在模型参数已知的条件下,初始时候的各种状态以及对应的初始观测的概率的和

    限制条件就是对于某种观测,初始的所有状态,其概率和为1,例如,第一天观测为晴天时候,海藻的干燥、湿润、潮湿三个状态概率和为1


    那么就可以根据拉格朗日乘法计算了,设


    那么令其偏导数等于零


    对 i 求和得到


    再带回偏导为0的式子中得到


    第二步求转移矩阵A

    将第二项改写为


    找到约束条件为


    意思就是上一个隐状态到当前所有隐状态的转移概率和为1,比如今天是晴天,那么到明天得隐状态转移:晴天->多云,晴天->雨天,晴天->晴天的概率和为1

    依旧根据拉格朗日乘子法得到


    第三步求混淆矩阵

    将第三项改写为


    找到约束条件为


    也就是说一个隐状态对应的所有观测概率和为1,比如天气为晴天的时候,对应的海藻干燥、湿润、潮湿的概率和为1

    但是有一个需要注意的是只有当观测状态为当前所求导的状态时候,的偏导数才不为0,其实也就相当于的时候才是偏导不为0,书中用表示,最终偏导以后求得:


    3.4 Baum-Welch算法

    该求得都求了,那么具体的HMM模型参数估计算法就是:

    输入:观测数据

    输出:HMM的模型参数

    (1) 初始化:

    对n=0,选取得到模型

    (2) 递推,对n=1,2,...

    分别计算上面的三个偏导

    (3) 计算到最后一次迭代就得到最终结果了


    后续分析一下HMM的代码再另行添加

    展开全文
  • 前向后向算法

    千次阅读 多人点赞 2018-08-21 15:58:12
     后向算法依旧是解决概率计算问题,只不过是两种计算方式,计算结果应该是和前向算法相同,可以用例1验证一下,如下:  例2( 后向算法 ),考虑盒子和球模型 ,状态集合 ,观测集合 ,并且有: 设 , ,...

    https://blog.csdn.net/Hearthougan/article/details/77930786

     本文是自己学习隐马尔科夫模型的一个总结,为了自己以后方便查阅,也算作是李航老师的《统计学习方法》的一个总结,若有疑问,欢迎讨论。

    推荐阅读知乎上Yang Eninala写的《如何用简单易懂的例子解释隐马尔可夫模型?》,写的非常好。我会联系两者,来作为自己的一篇学习笔记。

        隐马尔可夫模型: 隐马尔可夫模型是关于时序的概率模型,描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列,再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列,称为状态序列(state sequence),每个状态生成一个观测,而由此产生的观测的随机序列,称为观测序列(observation sequenoe )。序列的每一个位置又可以看作是一个时刻。

    隐马尔科夫模型的3个基本问题:

         (1)概率计算问题。给定模型和观测序列,计算在模型下的观测序列出现的概率

        (2)学习问题。已知观测序列,估计模型参数,使得在该模型下观测序列概率最大。

        (3)预测问题,也称为解码(decoding)问题。已知模型参数和观测序列,求对给定观测序列前提下,条件概率最大的状态序列。即给定观测序列,求最有可能的对应的状态序列。

    概率计算问题:
    1、 直接计算方法
        这种方法说白了就是暴力搜索,枚举每一种状态序列,然后在根据状态序列求出观测序列的概率。
        思想很简单,可以这么想:假如我们现在已知状态序列为,那么根据状态序列S,求观测序列的概率,不就是相应的输出概率的连乘么!满足假设的状态序列总共有种,然后对所有假设的状态得出的概率相加,即为。细化如下:

        状态序列的概率是

     


        对已经假设的状态序列,观测序列,的概率是

     

        观测序列O和状态序列S同时出现的概率是:

        最后,对所有的状态序列S求和,即可得到观测序列O的概率

        对于实现上式,很简单,个for循环即可枚举所有的状态,然后计算每种状态对应的观测概率,时间复杂度是O(T),因此要直接计算的话,总的时间复杂度为,当数据量稍微大一点,具体实施就不太可能,因此要实现HMM的第一个问题,就要换一种方法。

    2、前向算法:

        给定隐马尔可夫模型,定义到时刻t部分观测序列且状态为的概率为前向概率,记作

        可以递推地求得前向概率及观测序列概率

        这个可以这么理解,已知选每种骰子的概率,每种骰子的输出概率,那么前t次掷骰子,掷出的点数为,并且第t用的骰子是,的概率是就是

    (1)初值:

    【第一次掷的是骰子是,掷出的点数为的概率,其中表示开始的时候选用骰子的概率】

     

    (2)递推:

    【第t+1次用骰子,掷出的概率】

        上式方括号中,表示第t次使用骰子掷出点数的的概率,,表示前t次掷出点数为的概率×第t+1次使用骰子的概率。

        由于第t次骰子的种类有N种,因此,第t+1次使用,而前一次,也就是第t次,使用的骰子有N种可能,即如下图:

    (3)终止:

        根据(2)的递推式子可以求出,表示第T次使用可以产生序列,i仍有N中可能所以相加即为最终的结果。

        例子1(前向算法):考虑盒子和球模型,状态集合,观测集合,并且有:

    ,试用前向算法计算

    根据上面我们描述的算法,一步一步地计算,

    (1)计算初值:

    (2)递推:

         当时:

        当时:

    3、后向算法

        给定隐马尔可夫模型,定义在时刻t部状态为的条件下,从的部分观测序列为的概率为后向概率,记作:

    可以递推地求得后向概率及观测序列概率

       可以这么理解,已知第t次掷骰子所用的骰子是,那么它表示的就是从次到第次的看到的点数为:的概率。

    (1)初值

    【解释:已知最后一次所用的骰子为,那么第次之后,为任意值的概率,故而为1】

    (2)递推

    (3)终止

        后向算法依旧是解决概率计算问题,只不过是两种计算方式,计算结果应该是和前向算法相同,可以用例1验证一下,如下:

        例2(后向算法),考虑盒子和球模型,状态集合,观测集合,并且有:

    ,试用后向算法计算。
        我们仍然根据上面的算法描述,一步一步地计算,

    (1)计算初值

        当

    (2)递推

        当时:

        当

    (3)终止

     

    可以根绝前向算法和后向算法的定义,将两种计算方式结合起来,如下:

     

    https://blog.csdn.net/u012771351/article/details/53113377

    那么前向算法和后向算法之间联系

    我们来推导一下:

    从结论我们不难看出,在t时刻如果知道了状态为qi,那么可以将这个t之前和之后阻断,最后变换成前向概率和后向概率。

    那么我们就可以求单个状态的概率了:

    这样的话我么你从t=1一直计算到t=T,我们就可以得到每个时刻最有可能的那个状态,但是这样子做对么?

    我认为是不对的,原因是每一个时刻最有可能最终组成的状态序列是不一定存在的,打个比方说,全市高考,我选出每个学科的最高分,那么我就说这是第一名的各科成绩,显然是不一定的,那么正确的做法是什么呢?我们将在后边的Viterbi算法中介绍。

     

    进一步思考:如果要求了t时刻状态为i,t+1时刻状态为j的联合概率呢?

    最终结果是:

    这里把联合概率这块拿出来只是让大家更直观的感觉这个前后向概率而已,跟我们整体的HMM模型框架无关。

    展开全文
  • 前向-后向算法(Forward-backward algorithm)

    万次阅读 2015-11-30 11:31:03
     与HMM模型相关的“有用”的问题是评估(前向算法)和解码(维特比算法)——它们一个被用来测量一个模型的相对适用性,另一个被用来推测模型隐藏的部分在做什么(“到底发生了”什么)。可以看出它们都依赖于隐...
  • 1. 前向传播算法 所谓的前向传播算法就是:将上一层的输出作为下一层的输入,并计算下一层的输出,一直到运算到输出层为止。 从上面可以看出,使用代数法一个个的表示输出比较复杂,而如果使用矩阵法则比较的简洁...
  • 算法

    万次阅读 2018-02-08 00:13:09
    1.算法定义 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出...
  • 加法模型与前向分布算法

    千次阅读 2017-10-07 20:37:07
    加法模型和前向分布算法  如下图所示的便是一个加法模型  其中,称为基函数,称为基函数的参数,称为基函数的系数。  在给定训练数据及损失函数的条件下,学习加法模型成为经验风险极小化...
  • 大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...
  • 维特比算法(Viterbi Algorithm)   找到可能性最大的隐藏序列 通常我们都有一个特定的HMM,然后根据一个可观察序列去找到最可能生成这个可观察序列的隐藏序列。   1.穷举搜索 我们可以在下图中看到每个状态和...
  • 程序员那些必须掌握的排序算法(上)

    万次阅读 多人点赞 2019-08-17 16:03:39
    算法也是一个争论了很久的话题,程序员到底该不该掌握算法?不同的人有不同的答案,而事实上,很多公司都对算法有一定的要求,有些公司直接在面试的时候便会要求面试者手写算法题。这就对程序员的技术要求产生了很大...
  • Dijkstra算法(迪杰斯特拉算法

    万次阅读 多人点赞 2019-06-24 18:06:30
    对比算法好坏需要考虑的因素 执行算法所耗费的时间 ...迪杰斯特拉算法的主要特点是以起始点为中心外层层扩展,直到扩展到终点为止。 迪杰斯特拉算法的成功率是最高的,因为它每次必能搜索到最优路径。但迪杰...
  • 剪枝算法和后剪枝算法区别

    万次阅读 2017-11-26 11:10:19
    (二)预剪枝:预剪枝就是在树的构建过程(只用到训练集),设置一个阈值,使得当在当前分裂节点中分裂和分裂后的误差超过这个阈值则分列,否则不进行分裂操作。(三)后剪枝:(1)后剪枝是在用训练集构建好一颗...
  • 前向最大匹配算法1.1 前向最大匹配算法的原理2. 后向最大匹配算法2.1 后向最大匹配算法的原理3. 双向最大匹配算法3.1 双向最大匹配算法的原理 1. 前向最大匹配算法 1.1 前向最大匹配算法的原理 首先,我们分词的...
  • 今天就先介绍一下dijskra算法,同时说一下队列优化和存图方式之链式向星。 Dijskra算法: 该算法的提出时间啊,相关历史啊,发明者啊啥的我也不一一介绍了,这对于我们理解该算法并没有什么卵用。我直接用最简洁的...
  • Dijkstra算法原理

    万次阅读 多人点赞 2017-02-19 22:46:13
    Dijkstra算法 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性...
  • 在使用某个密码算法前需要先注册,然后才能使用。密码算法索引值的获取步骤 步骤1. 利用int register_cipher(const struct ltc_cipher_descriptor *cipher)注册算法 步骤2. 利用int find_cipher(const char *name)...
  • 最优化算法之粒子群算法(PSO)

    万次阅读 多人点赞 2018-08-03 10:26:45
    一、粒子群算法的概念   粒子群优化算法(PSO:Particle swarm optimization) 是一种进化计算技术(evolutionary computation)。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想:是通过群体中个体之间的...
  • 智能优化算法:麻雀搜索算法-附代码

    万次阅读 多人点赞 2020-09-27 16:34:00
    2020智能优化算法:麻雀搜索算法-附代码 文章目录2020智能优化算法:麻雀搜索算法-附代码1.算法原理2.算法结果3.参考文献4.Matlab代码 摘要:麻雀搜索算法(Sparrow Search Algorithm, SSA)是于2020年提出的。SSA ...
  • 由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,...
  • 算法 BF算法

    千次阅读 2018-04-18 17:29:35
    BF算法是字符匹配的一种算法,也称暴力匹配算法算法思想:从主串s1的pos位置出发,与子串s2第一位进行匹配若相等,接着匹配后一位字符若不相等,则返回到s1一次匹配位置的后一位,接着与s2的起始位进行匹配直到与...
  • 前向逐步回归算法 前向逐步回归算法属于一种贪心算法,即每一步都尽可能减少误差。一开始,所有的权重都设置为1,然后每一步所做的决策是对某个权重增加或减少一个很小的值。  观察每次循环得到的回归系数,一段...
  • 页面置换算法-CLOCK置换算法及其改进版算法

    万次阅读 多人点赞 2018-12-29 13:31:51
    页面置换算法中的LRU算法最接近理想情况下的OPT算法,但是实现起来比较困难且开销较大,所以很多设计者试图用开销比较小的算法接近LRU算法,CLOCK算法就是其中一种。 1.简单的CLOCK算法是通过给每一个访问的页面...
  • 算法算法评价

    万次阅读 多人点赞 2019-07-05 20:42:11
    一、算法的基本概念 算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。具有以下性质: 1.有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都可在有穷时间内...
  • 数据挖掘算法——常用分类算法总结

    万次阅读 多人点赞 2019-06-17 10:55:22
    常用分类算法总结分类算法总结NBC算法LR算法SVM算法ID3算法C4.5 算法C5.0算法KNN 算法ANN 算法 分类算法总结 分类是在一群已经知道类别标号的样本中,训练一种分类器,让其能够对某种未知的样本进行分类。分类算法...
  • Dijkstra算法

    万次阅读 2021-02-17 12:18:58
    迪科斯彻算法使用了广度优先搜索解决非负权有图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。 该算法的输入包含了一个有权重的有图 G,以及G中的一个...
  • | 深度学习之卷积神经网络(CNN)的模型结构)中,我们对CNN的模型结构做了总结,这里我们就在CNN的模型基础上,看看CNN的前向传播算法是什么样子的。重点会和传统的DNN比较讨论。 深度学习系列 深度学习之DNN...
  • 夜深人静写算法(三)- 初等数论入门

    万次阅读 多人点赞 2017-12-28 15:33:22
    初等数论:扩展欧几里得算法,中国剩余定理,欧拉函数,容斥原理,大数判素

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,794,622
精华内容 1,917,848
关键字:

前向算法