ML►ml 传统方法►supervised

维特比算法

动态规划

这是个递归问题
递归思想就是：把问题分解成规模更小，但和原问题有着相同解法的问题。
但是递归低效
递归：1-T的最优，依赖2-T最优,…依赖T-1到T的最优。但是T-1到T的最优是无法

要解决的问题

top1路径：很简单，所有候选到当前帧的cost，M*N的矩阵。
topN路径: 不仅仅考虑跳到当前点的最有路径，全局保留。存在的问题是有些点被剪掉了。可以考虑

HMM 示例

模型

全连接 - 指数级 - 朴素递归法

重复计算子问题

<script src=https://www.gstatic.com/charts/loader.js>

复杂度 $ O(N^{T}) $

这里N=3，T=3。

注意

  • 总路径数：$ N^{T}=3^{3}=9 $
  • 边的数目：$ N \times N \times T=3 \times 3 \times 3=9 $

维特比算法只是对边进行了复用。

最优路径 - 维特比算法

<script src=https://www.gstatic.com/charts/loader.js>

全局最优：line0
贪心算法会找到 line1

维特比是少计算了？剪枝了？还是并未少计算，只是复用了前面的计算结果。

维特比并未少计算，只是去除了冗余计算量而已。

例如路径 1 7 10

k-best 维特比

通常的维特比算法，如果要取top-k最优路径，那么只能在最后一层取topk，前面默认只缓存top-1。

这样导致所取的top-k并非全局最优top-k。

剪枝算法

top1问题

维特比算法复杂度是 NNT

T上不能缩减，我们只能在N上做手脚。

  1. 时间点t，只取top N
  2. 累积路径，只取
  3. 路径总数上限

topK问题

为了和N区分，这里采用topM。

通常的做法：

剪枝的做法：

FAQ

beam

beam=4指的是n还是似然值。还是当前点的路径数目，剪纸。
当前帧剪纸，比如top 15. log似然当前最优是100，100-12.

平滑

有些转移概率为0的，是否需要平滑？

看具体情况。有些状态根本调不到下一个状态。音素上的跳转概率并没平滑。

每帧出top 60，那么就是60^N的路径，但是有top_thresho.

lattice free

什么鬼？

lattice freee是和传统的鉴别训练区分。latice 网格，传统只给top1。
鉴别性，音素错误率，等准则在训练中要体现。全局性的错误率，softmax只提供了单帧错误率。

Math►-运筹学-动态规划►启发式算法

模拟退火

说文解字

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。

讲得真好啊。

模拟退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。

可以证明，模拟退火算法所得解依概率收敛到全局最优解。

退火、正火、淬火和回火

  • 淬火硬化
    • 淬cuì火，俗称蘸（zhàn）火，金属和玻璃的一种热处理工艺。把合金制品或玻璃加热到一定温度，随即在含有矿物质的水、油或空气中急速冷却，一般用以提高合金的硬度和强度。淬火可增强钢与铸铁的强度和硬度。急速冷却的速率也会影响物质表面硬度和心部硬度。淬火后物质会变脆，所以通常会再进行回火处理，目的是降低物质的脆度。螺丝、齿轮、转动轴、金属块等物品常使用淬火处理。

      淬火后得到马氏体，组织变硬，也就是晶粒变得粗大。
  • 回火可以稍微降低硬度和强度，使钢不太脆
    • 淬火后，钢变硬但是太脆了，动不动就断，那么好，我们在加热它，这个温度要温和的多了，然后再慢慢冷却下来，目的是组织变得细小，记住，晶粒细小的组织性能好，放在钢上，就是硬度高、强度大、塑形好。
  • 退火
    • 将钢加热、保温后缓慢冷却

为什么不模拟淬火呢？急速冷却一下。

简介

模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。

模拟退火算法描述：

  • 若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解)，则总是接受该移动
  • 若J( Y(i+1) )< J( Y(i) ) (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）

随着温度T的降低，P(dE)会逐渐降低。

我们将一次向较差解的移动看做一次温度跳变过程，我们以概率P(dE)来接受这样的移动。

参考

https://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html

Math►-运筹学-动态规划►常见问题

路径搜索算法

算法 en 简介 时间复杂度 全局最优解 缺陷 应用场合
全搜索 ( N^T ) √ 指数级
维特比算法 Viterbi T*N^2 √ 深度T影响不大，N影响比较大。比如seq2seq中的N是词典大小。因此可采用近似算法 常用于HMM模型，分词、中文输入法
束搜索 beam search 属于贪心算法思想 beam search是一种启发式搜索，没有条件限制，都可以用，利用定义好的代价来剪枝，需要创建一个搜索树，因此每一个结点都与前面所有的父亲结点连接，生成很多结点在搜索树上，而DP是计算最优子问题的结果，保存在一个中间表中。 TNbeam_size 当beam_size=N时，就是Viterbi算法 × seq2seq，
贪心 greedy search T*N ×

全局最优

Viterbi算法

近似算法

  • 贪心，每一步都贪心。
  • 束搜索（beam search）就是引入了类似贪心的策略（每一步都贪心的保留一部分当前最好的结果）
Math►-运筹学-动态规划►启发式算法

启发式算法

说文解字

Heuristic 启发式的；探索的。

  • 启发法(Heuristics):是凭经验的解题方法,也可称经验规则。

人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案

看上去有点类似streaming，有点像markov

  • 特点:不能保证问题一定得到解决,但却常常有效解决问题。

来源 定位 在算法中的位置

决方法， 有2类， 分别是 确定方式和近似方式（ Exact Method， Approximate Method）

对于优化问题的解决方法， 有2类， 分别是 确定方式和近似方式（ Exact Method， Approximate Method）

对于优化问题. 根据条件，和限制， 可以描绘出一个解集空间（Solution Space）， 确定算法， 只可用在解集空间很小的问题， 但对于NP hard 问题， 可行时间内在个空间中找到 全局最优解（Global Optimum ） 的可能性很小 （ 几乎不可能）。 故需要使用近似算法（Approximate Method） 在有限时间内来寻找一个近似最优解。 近似方法分为两种 分别为 近似算法（Approximate Algorithms） 和启发式算法（ Heuristic Algorithms)。 近似算法通常可得到一个有质量保证的解。 然而 启发式算法通常可找到在传统解决问题的经验中找到寻求一种面向问题的策略， 之后用这种策略来在可行时间内寻找一个相对比较好的解，但对解的质量没有保证。

https://www.zhihu.com/question/28874818/answer/67504126

简介

启发式就是能快速出结果的算法，出来的结果一般是可用的，但是不能保证全局最优，也不能保证算法的完备性。全局最优容易理解，完备性是说能这个算法能不能找到所有的解，或者干脆判定此问题无解。

启发式方法（试探法）是一种帮你寻求答案的技术，但它给出的答案是具有偶然性的（subject to chance），因为启发式方法仅仅告诉你该如何去找，而没有告诉你要找什么。它并不告诉你该如何直接从A 点到达B 点，它甚至可能连A点和B点在哪里都不知道。实际上，启发式方法是穿着小丑儿外套的算法：它的结果不太好预测，也更有趣，但不会给你什么30 天无效退款的保证。

启发式方法 VS 算法

启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。但由于这种方法具有尝试错误的特点，所以也有失败的可能性。科学家的许多重大发现，常常是利用极为简单的启发式规则。

驾驶汽车到达某人的家，写成算法是这样的：沿167 号高速公路往南行至Puyallup；从South Hill Mall 出口出来后往山上开4.5 英里；在一个杂物店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是North Cedar 路714 号。

用启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里。这里每个人都认识我们——肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共电话亭给我们打电话，我们会出来接你。

算法和启发式方法之间的差别很微妙，两个术语的意思也有一些重叠。就本书的目的而言，它们之间的差别就在于其距离最终解决办法的间接程度：算法直接给你解决问题的指导，而启发式方法则告诉你该如何发现这些指导信息，或者至少到哪里去寻找它们。

ss

对于优化问题. 根据条件，和限制， 可以描绘出一个解集空间（Solution Space）， 确定算法， 只可用在解集空间很小的问题， 但对于NP hard 问题， 可行时间内在个空间中找到 全局最优解（Global Optimum ） 的可能性很小 （ 几乎不可能）。 故需要使用近似算法（Approximate Method） 在有限时间内来寻找一个近似最优解。 近似方法分为两种 分别为 近似算法（Approximate Algorithms） 和启发式算法（ Heuristic Algorithms)。 近似算法通常可得到一个有质量保证的解。 然而 启发式算法通常可找到在传统解决问题的经验中找到寻求一种面向问题的策略， 之后用这种策略来在可行时间内寻找一个相对比较好的解，但对解的质量没有保证。

启发式算法的发展

启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，取得了巨大的成就。

  • 40年代：由于实际需要，提出了启发式算法（快速有效）。
  • 50年代：逐步繁荣，其中贪婪算法和局部搜索 等到人们的关注。
  • 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规 模的问题仍然无能为力（收敛速度慢）。
  • 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略………..Holland的遗传算法出现了（GEnetic Algorithm）再次引发了人们研究启发式算法的兴趣。
  • 80年代以后：模拟退火算法（SiMUlated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。
  • 最近比较热或刚热过去的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms）， 拟人拟物算法，量子算法等。

　　各个算法的思想这就不再详细给出，为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。这里要说明的是：启发式算法得到的解只是近似最优解（近似到什么程度，只有根据具体问题才能给出）. 二十一世纪的最大的数学难题NP？=P，如果NP=P启发式算法就不在有存在的意义。

群体智能算法就是启发式算法；研究的重点就是如何平衡局部搜索与全局搜索；有效逃离局部最优解；

近几年比较活跃的算法有如下：

  • 仿动物类的算法：粒子群优化，蚂蚁优化，鱼群算法，蜂群算法等；
  • 仿植物类的算法：向光性算法，杂草优化算法，等等；仿人类的算法有：
  • 和声搜索算法是较好的算法；近年开始研究情感计算的人较多。

实际应用时差分进化算法较有优势。关于粒子群算法，理论成熟，应用广泛。

Shi Cheng: 上面提到的算法，应该属于元启发式算法 meta-heuristics algorithms

疑问

那，梯度下降是贪心算法吗？

贪心算法是启发式算法吗？

贪心算法是一种启发式算法，它企图寻求局部最优解，容易陷入局部最优的困境。

梯度下降法也是启发式咯？

启发式搜索与传统基于梯度信息的方法

启发式搜索在机器学习优化中的研究有哪些？

什么算法不是启发式算法？

启发式方法并不告诉你该如何直接从A 点到达B 点，而是仅仅告诉你该如何去找。
按照这个意思，梯度下降法、神经网络、
机器学习算法 是不是 基本都是启发式方法？

决策树不是启发式的吧，

哪些机器学习算法 是启发式算法咯？

#

所以后来有了元启发式算法，如蚁群算法，模拟退火算法，禁忌算法等等，这类算法通过一些策略，某种程度上可以跳出局部最优解，从而寻求更好的全局最优解。

各类启发式算法概述

优胜劣汰是大自然的普遍规律，它主要通过选择和变异来实现。选择是优化的基本思想，变异（多样化）是随机搜索或非确定搜索的基本思想。“优胜劣汰”是算法搜索的核心，根据“优胜劣汰”策略的不同，可以获得不同的超启发式算法。超启发式算法的主要思想来自于人类经过长期对物理、生物、社会的自然现象仔细的观察和实践，以及对这些自然现象的深刻理解，逐步向大自然学习，模仿其中的自然现象的运行机制而得到的。

  • 遗传算法：是根据生物演化，模拟演化过程中基因染色体的选择、交叉和变异得到的算法。在进化过程中，较好的个体有较大的生存几率。
  • 模拟退火：是模拟统计物理中固体物质的结晶过程。在退火的过程中，如果搜索到好的解接受；否则，以一定的概率接受不好的解（即实现多样化或变异的思想），达到跳出局部最优解得目的。
  • 神经网络：模拟大脑神经处理的过程，通过各个神经元的竞争和协作，实现选择和变异的过程。
  • 禁忌搜索：模拟人的经验，通过禁忌表记忆最近搜索过程中的历史信息，禁忌某些解，以避免走回头路，达到跳出局部最优解的目的。
  • 蚂蚁算法：模拟蚂蚁的行为，拟人拟物，向蚂蚁的协作方式学习。

这几种超启发式算法都有一个共同的特点：从随机的可行初始解出发，才用迭代改进的策略，去逼近问题的最优解。他们的基本要素：

　　（1）随机初始可行解；

　　（２）给定一个评价函数（常常与目标函数值有关）；

　　（３）邻域，产生新的可行解；

　　（４）选择和接受解得准则；

　　（５）终止准则。

　　其中（４）集中反映了超启发式算法的克服局部最优的能力。

启发式算法的不足和如何解决方法：

参考

others►医疗

肩周炎

什么是肩周炎

又称粘连性肩关节囊炎

如何鉴定肩周炎

如何治疗

如何保养

黏连，就要解黏连。正确锻炼、拉伸

最好有个打印版

经典视频

-

ML►app►Reinforcement Learning

AlphaGo背后的搜索算法：蒙特卡罗树搜索

深度学习 + 增强学习

启发式算法

蒙特卡洛树搜索

“蒙特卡洛树搜索”是一种启发式的搜索策略，能够基于对搜索空间的随机抽样来扩大搜索树，从而分析围棋这类游戏中每一步棋应该怎么走才能够创造最好机会。

一位名叫苏椰的知乎用户举了这样一个例子，以通俗的语言进行了解释：假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个……我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法：尽量找好的，但不保证是最好的。

需要说明的是，蒙特卡罗树搜索并不是只有一种算法，而是一类算法。其中最流行的算法之一就是UCT（upper confidence bounds applied to trees）。

占坑

alphago为什么不采用维特比算法？

因为alphago的路径搜索，跟markov不同。

markov有个状态转移矩阵，有限状态。围棋的状态空间太大，没办法用状态转移矩阵来衡量吧？

alpha-zero

ML►app►Reinforcement Learning

星际争霸

游戏简介

三种种族，多兵种协同(海陆空)，包围、埋伏、
多地形(坡) 战争迷雾 金钱

deep mind 策略

#

计算机优势

apm高，即使计算机胜了，也并非表示策略更优。

所以需要在apm<=人的情况下，与人公平竞争。

缺陷

现在的计算机，能耗太高。人只需要一碗饭。芯片能耗。