官方微信 手机版
手机动态码快速登录 登录 注册

光学喵-光学课堂 › 首页 ›资讯 › 查看内容

算法初识

2021-12-20 10:40| 发布者：Davis| 查看：1335| 评论：0|原作者: 小小光08

摘要：本文介绍了算法的本质和模型化，以及如何衡量算法的效率。同时还提到了巧妙算法的三个角度：效用选择模型、减小问题规模和探索与利用。最后，谈论了算法不能做的三件事情，其中包括自动驾驶汽车的限制。
 
01 本质：到底什么是算法？
算法就是有输入、有输出的解决问题的计算步骤。
算法对明确性有极其严苛的要求。
算法要求极其明确。当一个解决方案足够明确，必然可以让这个算法无数次再现，同一个算法，相同的输入必然可以得到相同的输出。不会因为执行的计算机不同、人不同，就导致不同的结果。
能不能复现也是衡量算法明确性的标准。
当你有一个问题要交给算法解决，就要不断明确每个细节，保证算法执行之后能够复现。所以本质上来说，算法就是一套通过确定性保证解决问题的工具。
模型化是算法优势的本质
什么叫模型化?简单来说，模型化就是对不同的问题，用同样的方式来看待，用同一套算法来解决。
模型化最大的价值，就是赋予算法超乎寻常的问题迁移能力。
算法没有好坏之分，背后都是人的思想。
所以，不要对算法评判对错、评判好坏，算法的模型只是人思想的体现，如果算法出了问题，请回到人身上找问题。
算法永远不会完美，统计学家乔治·博克斯有一句名言:“所有的模型都是错误的，但有些是有用的。”算法也一样，没有好坏，有用就好。
 
02复杂度:怎样判断算法的效率高不高?
评价算法效率的两个难题：
第一个难题，“硬件依赖”。
第二个难题，“无穷大”的难题。当算法的输入规模，趋近于无穷大的时候，算法解决问题所花的时间也趋近于无穷大。
面对这两个难题，我们需要另一种度量算法效率的工具。既能比较不同算法之间的效率高低，还不需要依赖于计算机的硬件水平。这个度量工具，叫作“时间复杂度”。
时间复杂度是度量算法效率最主要的工具。
什么是时间复杂度呢?教科书说，时间复杂度是算法中某些基本操作的总数量，随着算法输入的规模而增长的函数关系。
算法工程师的工作就是找到效率更高、时间复杂度更低的算法。
降低时间复杂度的方法之一：空间换时间。
空间复杂度，也是衡量算法效率的一个标准。
什么是空间复杂度呢?和时间复杂度差不多，也是一种函数关系，是算法占据的空间资源，随着输入规模变大而增长的函数关系。
所以，空间复杂度的概念就是衡量不同算法在运算的时候，需要占据空间资源的大小。有意思的是，在计算机里空间和时间是可以互换的。
面对时间复杂度，牺牲些存储空间，换来更快的搜索速度一定是非常划算的。
降低时间复杂度的方法之二：分治思想。
1965年，美国数学家库利和图基采用“分治”的思想，发明了快速傅立叶变换，可以把时间复杂度降了一个量级。
 
03启发:什么样的算法是巧妙的算法?
效用选择模型：近似现实且保持可解性。
算法是用数学公式表达的计算方法，和现实之间有一条鸿沟。而数学模型是连接这两端的桥。
如果数学模型建立得过于粗糙，把实际问题中的重点漏掉了，算法得到的结果也就不能重新应用回现实。而如果一个数学模型非常贴近现实，却没有有效的算法能帮助求解，那也没有用。
所以，能不能合理地近似现实，同时保持可解性，是算法工程师评价一个模型是不是巧妙的重要角度。
减小问题规模：降到计算机可以处理的规模
能减小规模的算法有很多，它们背后的思想都是通过舍弃了少量信息，把一个大到不能计算的问题减小到了计算机可以处理的规模。这也是算法工程师说一个算法巧妙的重要角度。
探索与利用:迭代得到结果
在算法问题中，不能一蹴而就得到答案的情况有很多，需要不停地探索与利用。
这时算法能不能通过不断迭代，最终得到解决方案，同时又能保证很高的效率，也是算法工程师评价它巧不巧妙的重要角度。
如果把这三个角度合在一起，巧妙的算法常常有一个特点，就是背后的思想符合人的直觉。算法工程师厉害的一个原因，就是能把直觉的思路以一种明确的方式表达出来，转换成算法，然后攻克复杂问题。
 
04反思:计算机能不能避免人的错误?
算法不能做三件事:
第一，算法不能对问题负责
算法用于自动驾驶，一辆自动驾驶汽车说,“请你安全驾驶”，它听不懂什么叫“安全”。你只能给它设置，如果其他车辆以100公里的时速靠，车距小于5米，就要减速或者避让。它能做的只有识别外界环境，比如与其他车的车距、交通信号的变换、障碍物等等。算法把这些作为判断因素，决定该加速、减速、并线，还是紧急刹车。
算法是工具，就像手里的锤子，锤子能钉钉子盖房子，但锤子不知道盖房子要解决什么问题。
如果你跟锤子说去盖个房子，它不会，你也不能怪锤子。
所以，人可以使用算法做事。但实际问题和算法能做的事情之间是有间隙的，算法不懂间隙是什么，只有人能处理间隙，所以算法不能对问题负责。
第二，算法不能对数据负责
算法需要有输入、有输出、有计算过程。虽然说算法需要定义输入和输出，但算法执行的主要是计算过程。换句话说,算法只能负责“算”，其他的管不了。
数据科学领域有这么一句话：“Garbage in，garbage out”，垃圾进、垃圾出，形容数据问题特别贴切。如果数据就是垃圾，算法再好用也白搭。
第三，算法不能对解释负责。
可以说，算法只能提供解决方案，不能提供解释。这是目前，人类抉择是否相信算法最大的困境。
我们再说回自动驾驶这件事。自动驾驶虽然不会犯人类的那些错误，但会面临新的问题。比如，识别错误、定位错误、死机等等。
算法复杂程度不同，意味着算法解释性水平也不同，这时候就需要算法设计者自己权衡。不得不说，有时候为了缓解这个矛盾，算法科学家会宁可放弃一定的准确性，也会去选择那些更容易被解释和接受的算法。
 
05算法蓝图：怎样设计一个算法？
1明确问题
在设计算法之前，就先明确问题，对问题的“方向”和“边界”先达成共识，再开始谈算法怎么实现。
怎么算明确问题呢?
我们可以从三个要素入手，明确目的、明确限制条件、明确评价标准。
首先是，明确目的。对目的的描述可以有很多种，究竟要选哪种目的，需要在一开始就确立下来。
其次，要明确限制条件。要把量化的指标确立下来。
有时候，我们想实现的目标和限制条件是不相容的。
能不能准确、快速判断限制条件的合理性，是非常考验一位算法工程师水平的。
接下来，要明确评价标准，也就是问题得以解决的标准是什么。
评价标准一定是必不可少的，没有标准就无法判断问题是不是最终被解决了。
2 建立模型
现实问题是没办法直接交给计算机的，我们需要一个数学模型来与计算机建“桥梁”，可以说，建立模型的过程，也是把现实问题转化成算法问题的过程，用另一套语言来重新描述问题。
有时候描述一个问题，还可能需要多种数学模型的组合，而这些模型有层次，甚至会互相依赖，合在一起才完成“桥梁”的搭建，真正用数学语言描述了现实问题。
总之，提出一个问题，直接设计算法、编写程序需要大量的成本，如果没有模型也就对结果没有办法进行预估，有了数学模型，才能实现推理、预估或者预测。所以，在设计算法之前，一定要建立数学模型。
但要注意，数学模型并不是对现实问题的完美描述，建模的过程，也是大量细节被抽象掉的过程，在算法迭代中，模型迭代是非常重要的一环。
3算法选择
同样的数学问题，不同的算法效率很不一样。
算法各有优劣,算法工程师在选择的时候会考虑时间复杂度，也要考虑达成目标水平的高低，等等。如何选出最适合的算法，是算法工程师面对的又一个重要挑战。
 
06建立模型：如何把现实映射进计算机？
1确定假设
我们先要搞清楚，需要得到一个什么精度的预测结果。如果我们想要的精度很低，那只需要一个简单、容易计算的模型。这时候，我们就需要对问题进行最大程度的简化。
确定假设，其实是一步步确立重要变量、核心关系的过程。舍弃不重要的细节，把模糊的问题，明确化、量化，这样就把一个复杂的现实问题，转化成了计算机可以理解，算法可以处理的数学问题。
2验证模型
模型的验证不是一成不变的，我们得从多角度来论证，有时候还需要点儿奇思妙想。
验证模型的思路，需要通过不断和现实问题做比较，就可以迭代出更合适的模型，把现实问题尽可能无损地映射进计算机里。
3权衡：要贴近现实、也要容易求解
一个模型是不是最优选择，不仅要看模型是不是靠谱，还要看是否能实现。
对准确性要求高，通常就意味着变量多、逻辑复杂、数据不可得等困难。
同时，一个复杂的模型对算法也提出了更高的要求，要么是成本上的，要么是复杂度上。复杂的模型或多或少，都带来更复杂的解法。
这就像是神经网络模型，模型的结构复杂，能捕捉的细节多，但求解起来就更难。
所以说，虽然模型的选择过程存在主观性，没有统一的标准说怎样才是最好。但它有一个底线，那就是模型必须能求得有效解。
如果你的模型需要没有的数据或者没有有效的算法解决，那么模型再好，逼近现实问题程度再高也没用。在解决问题的时候，不能光追求模型准确，还要权衡它的可行性高低，最终找到一个又能准确描述现实，又能有效求解的模型。
 
07算法选择：选择算法最重要的考量是什么？
1关系：模型与算法并非一一对应
同样一个模型，可以对应的算法却很多。
所以在开始选择算法之前，我们先要认识到，模型和算法的关系，并不是一一对应的。一个数学模型仍然可以被多个算法求解，同样，一个算法也可以用来求解多个数学模型。
所以，建模不等于就完成了算法选择，最终能不能把问题有效解决，找到合适的算法仍然至关重要。
2选择：质量与效率的权衡
算法工程师喜欢引用大卫·沃伯特( David h.Wolpert,计算机学家)提出的一个定理，叫“没有免费的午餐”定理。就是说，在很多算法问题当中，没有哪个算法是绝对最好的。要找到最适合的算法，一定要权衡算法在不同场景中的利弊。
所以说，算法工程师很在意算法解决问题的质量。而在时间复杂度和解决问题的质量水平之中的权衡，就成了算法选择的重中之重。
不过，在具体问题中，权衡算法并没有明确的标准。
3进阶：算法工程师的更多考量
实际应用的时候，算法工程师通常更青睐那些对数据错漏有容忍度的算法，就算个别数据存在问题，也不会对算法结果造成太大影响。
算法工程师在选择算法的时候，也会考虑到限制条件，如果限制条件太严格，数据又不满足，就要考虑那些对限制条件要求比较低的算法了。
今天对算法的认识已经不仅仅是问题、模型、算法了，还有数据。数据重新定义了我们对模型的思考方式，这也是今天算法工程师非常关注的一个维度。
 
08 迭代：怎样一步步接近答案？
1迭代：一步一步重复操作，接近答案
迭代算法就是通过循环重复某个固定的操作，每步以前一步的结果为出发点，逐步逼近问题答案的算法。
2确保迭代策略有效的条件
迭代算法很有用，但它也不是万能的。它能有效，但有条件。
能趋近于一个结果，这用算法工程师的专业术语来说，就是“算法可以收敛”。这是使用迭代算法需要确认的第一个条件。
在迭代算法里面，有多个不动点的问题。所谓不动点，就是每次迭代计算不会进行改变的点。
所以说，使用迭代算法的时候，算法工程师需要对不动点的数量进行一个分析。如果我们能确认不动点只有一个，那么迭代算法就总能收敛到想要的结果。如果多于一个，我们就不能保证得到想要的答案。
3为什么迭代算法更快？
迭代策略允许在寻找问题解的过程里，总是有那么点误差。但这个误差减小的速度很快，所以迭代算法的速度也很快。
在解决很多科学、工程领域的大规模线性方程问题时，虽然也有精确求解的算法，但科学家或者工程师还是经常会用迭代算法，就是因为它更快。
 
09 分治：怎样拆解问题，逐个击破？
算法领域，有一种分治算法，采用了把大问题分解成小问题的策略来进行计算。
1分治算法：拆大为小的回溯算法
分治算法是通过回溯，不断分解同样的问题，直到问题小到可以直接解决，然后再把小问题的解，合并成原来问题解的算法策略。
2保证分治算法有效的条件
我们要确保问题可以分解成和原问题类似的子问题，并且这些子问题之间还相互独立，这时分治策略才能奏效。
分治中的两个重要操作，分解和合并，不是免费的。如果它们自身就要耗费很多次计算，那很可能分治策略提升不了效率，也不算是奏效了。
3分治算法能更快的特殊之处
减少基本操作的个数，这属于在“软件”上对算法效率进行提升。分治算法，还可以通过巧妙地利用“硬件”，让效率进一步提升。这就是“并行计算”。
并行计算能让多个计算机的CPU同时为解决一个问题出力，但并不能减少总的操作数量。
并不是所有算法都可以用并行计算的。迭代算法要求每一步以前一步的结果作为出发点，按步骤、按顺序进行计算。如果让一个CPU计算前面的步骤，第二个CPU计算后面的步骤，两个CPU不能同时工作，就不是并行计算。
分治算法因为能把问题分解成独立的部分，所以和并行计算是天然的好朋友。
 
10 动态规划：怎样从小问题出发，逐级解决大问题？
“动态规划”中，“动态”指的是多个步骤，而“规划”指的就是决策。“动态规划”这个词既指多步骤的决策优化问题，也代表解决这类问题的算法方法。
1问题的解决思路：以终为始，以小建大
 “以终为始,以小建大”的解决思路，就是我们要先得到小问题的解，再构建出大问题的解。
2动态规划算法的结构：最优子结构
我们在面对一个多步骤的决策问题时，某一步决策的最优，包含且依赖于对更小规模问题的最优策略，这就是最优子结构。
这个结构很重要。如果一个问题满足了这个结构，那就说明我们可以从解决小问题开始，慢慢构建对大问题的解。
动态规划算法，就是在多步骤的决策优化问题满足最优子结构的时候，用以终为始、以小建大的思想解决问题的算法策略。
动态规划在实际中出现的频率非常高。
3动态规划策略有效的条件
算法工程师不一定会精确求解所有的子问题，很可能只求解其中的一部分，而且是非精确求解，对另外的子问题的解，只进行一个估计。这样虽然不能得到完美的最优决策，得到的结果也是足够好的。
 
11 分支定界：怎样决定谁是“被淘汰者”？
1组合优化：谁是最优的答案
更好的方法是，把那些不重要的分支都去掉，而只留下少量的分支，再把有限、少量的结果进行比较。釆用这样的策略而设计出来的算法，就叫分支定界法。
2分支定界:分支、定界、剪枝
分支就是把问题解的不同可能性，分开去考虑。
把所有部署方案组成的搜索空间，分成了相互不重叠的两部分，这个过程就是分支。
分支的目的是淘汰一些解。要想淘汰，就得依赖“定界”和“剪枝”。
“定界”就是估计某个子搜索空间中最优解的上界的过程。“剪枝”是当某个子搜索空间能获得的目标上界，比不上某个已知的可行方案，就直接把这个子空间淘汰的过程。把它们合在一起，就是分支定界法。
3如何让分支定界法更高效
分支定界算法效果好不好，主要取决于我们能多有效地进行剪枝。
如果我们只进行分支，不进行剪枝，那就和把整个搜索空间全部算一遍没有区别，计算的
效率没有提高。这也就是为什么，为了让分支定界法高效运行，算法工程师探索了各种各样的方法，目的就是多多地进行剪枝。
算法工程师有个策略叫“提前停止”，特别有用。
“提前停止”就是在没找到问题最优解的时候，提前停止对最优解的搜索。
在实际问题中，参数的测量或者估计往往没有那么准确。即使找到最优解，应用到实际中，可能也有偏差。这样的话，我们完全可以提前停止算法运行。虽然舍弃了所谓的最优解，但却大大地节省了算法运行的时间。
 
12 启发式：放弃最优解之后，怎么办？
1启发式算法：基于人类直觉认识的算法
启发式算法是人们通过对问题的理解，以某一套规则制定出来的一类算法。启发式算法通常放弃了最优解，但却能得到还不错的可行解。
这里有一个值得我们注意的地方。一个适用于旅行商问题的启发式算法，是不能用在别的问题上面的。启发式算法是针对特定问题设计出来的，需要具体问题具体分析。这是启发式算法的一个重要特征。
2元启发式算法：基于对自然认识的算法
元启发式算法，这里的“元”在英文中对应的单词是meta，代表的是“超越、关于”的意思。所以元启发式算法可以理解为，比普通启发式算法高一层，是产生启发式算法的算法思想。
元启发式算法在不同问题上可以通用。
元启发式算法还有一个很有趣的特点，就是它们对自然中逻辑的借用。
比如说基因算法，利用的是遗传中“适者生存”的道理，把适应度低的解淘汰掉。
蚁群算法，是利用蚁群信息素的概念，对网络问题进行求解。
粒子群算法，模拟鸟类觅食的过程，可以对最优解的位置进行搜索。
元启发式算法是通过对自然运作的逻辑观察，或者对人类解决问题时通用逻辑的观察，总结出来的一系列通用启发式算法。
3什么时候采用启发式算法
其实不到迫不得已，算法工程师并不会用启发式算法。
它有两个缺点：
第一，启发式算法对最优解没有保证。
第二，启发式算法好不好用，是一个试错的过程。
所以，在找不到最优解的时候，我们可以退而求其次，用启发式算法来求解。但启发式算法又是把双刃剑，带来好处的同时，又会增添一些新的烦恼。
 
13 蒙特卡罗：丢失确定性之后，怎么办？
1蒙特卡罗方法：对现实世界进行随机模拟
蒙特卡罗方法是一种模拟算法，每个样本都代表着一次对现实的模拟。我们用有限次的模拟，替代了所有平行宇宙的可能性。
蒙特卡罗方法就是对问题中的随机事件进行取样，为有限个样本进行独立计算，最后把样本结果进行统计的策略。
2蒙特卡罗适用的问题
蒙特卡罗方法最适用于随机变量多，计算逻辑复杂的问题。
3使用蒙特卡罗的注意事项
第一，蒙特卡罗方法是对问题的估算，而不是精确计算。
第二，蒙特卡罗方法的成功，非常依赖参数和模型的正确。
第三，蒙特卡罗方法，会减小我们发现问题本质的机会。
随机模拟不是万能的，它会占用大量计算资源，依赖于参数的正确性，并且对揭示问题本质没有太大帮助。

14 机器学习：机器到底在学什么？
1人不会教，就让计算机自己学
机器学习算法，就是一系列人们制定的、让计算机自主学习的算法，它们最适合用在人类没法用明确规则进行解决的问题上。
机器学习学到了很多人类没教过、自己也不懂的事物细节。
2机器学习到底学的是什么？
机器学习算法学习的对象是，事物与事物之间的复杂关系，尤其是关系中的某种模式特征。
利用机器学习算法学习事物之间的因果性和重要关联，我们可以更好地决策。
机器学习算法可以帮助我们筛选出重要信息，找到最有意义的那部分信息和它们的组合。
 
15 学习策略：机器学习如何获得知识？
1同样的能力可以基于不同的知识
从算法的角度来看，机器学习算法产生的知识，是运行一套算法得到的结果，而算法运行的过程是学习的过程。
知识是一种我们对信息以及事物之间关系的理解，而能力是把知识应用到实际中的本领。有知识不代表有能力，但没有知识就没能力。
即便两个算法能做到的事情是一样的，它们背后的学习机制也是不一样的。我们在算法领域，把它们称为不同的机器学习模型。
2得到知识的方法：不同的学习模型
K邻近算法模型，这种学习算法是完全基于记忆的。也就是说，学习的过程就是记忆的过程。实际中的算法实现，也就是把历史数据存下来，方便将来进行比对。
决策树模型，通过数据归纳，总结出条件判断的学习模式。实际应用中的决策树模型可以很复杂，但背后的本质很简单，就是每个特征和要学习的对象进行相关性的比较，相关性高的放在条件判断里，低的扔掉。
神经网络模型，是通过模拟神经信号的传递，以及神经对外界不同信息反应强弱不同的过程。这个算法中并没有真正的神经，也没有神经反应的强弱。取而代之的是大量的参数，参数越接近于零，说明它所代表的特征越不重要。AlphaGo的学习模型，就是神经网络模型。
这三种学习模型，模拟了三种不同的学习过程，但并没有把学习过程的种类完备掉。人们对“该怎么学习”这个问题，有不同的认识。但无论这些认识是什么，算法学家都可以通过模拟这个学习的过程，设计出不同的机器学习算法。
3怎么把获得的知识传授给人类
算法并不对问题负责。有些问题事关重大，在这些问题上使用机器学习算法，我们就必须搞清楚算法学会的知识到底是什么，让它把获得的知识教还给我们。
这件事，特别特别难。难在两个地方。
第一个难点是，机器学习对知识的表达方式和人类不一样。人类看到这些算法产生的知识，理解起来很难，有的甚至根本没法理解。
第二个难点，是记忆力和算力的问题。这一条很好理解。算法依赖计算机，能记住的数据量太大了，人类的记忆力是做不到的。即使记忆力无限，人脑的算力也和算法差得太远。
 


路过
雷人
握手
鲜花
鸡蛋
收藏 邀请

最新评论

相关分类

图文热点

热门推荐

  • 汇集知识碎片，解决技术难题
  • 互相帮助、共同成长
  • 总有一个人知道你问题的答案
关于我们
网站介绍
招贤纳士
联系我们
站点地图
新手上路
客服中心
网站地图
新手帮助
用户协议
业务合作
广告服务
业务合作
友情链接
赞助投资
网站服务
企业入驻
代理业务
问答商城
账号申诉

官方公众号

官方客服

Copyright © 2020-2023, 光学课堂.

浙ICP备20017518号-3
Archiver|手机版|小黑屋|
联系客服 关注微信 访问手机版 返回顶部