学习平台:得到
课程名称:算法通识16讲
老师:吴晶晨
学习周期:2021.4.8—2021.4.21
一句话描述:给外行人讲清什么是算法和算法工程师
一、认识算法
01 | 本质:到底什么是算法?
- 算法对明确性有极其严苛的要求:算法是什么? / 什么是算法? 这是两个问题
- 算法是什么?在算法科学家眼里,这个问题很简单,算法就是有输入、有输出的解决问题的计算步骤。
- 什么是算法?要理解计算机与人的核心差异:算法要求极其明确。当一个解决方案足够明确,必然可以让这个算法无数次再现,同一个算法,相同的输入必然可以得到相同的输出。不会因为执行的计算机不同、人不同,就导致不同的结果。
- 模型化是算法优势的本质: 表面上,这是红娘牵线问题、商品推荐问题、搜索引擎问题,但在算法工程师的眼里,这全是“距离”问题。这就是模型化。模型化最大的价值,就是赋予算法超乎寻常的问题迁移能力。
- 模型就是一个问题脱去现实描述外衣之后的逻辑内核。同样一种逻辑内核可以在不同的问题中穿梭,来描述不同的现实关系。正是这种穿梭的能力,让算法能在不同领域中快速迁移。
- 算法没有好坏之分,背后都是人的思想:
- “K临近算法” 用在肿瘤判断的 “男女歧视” ,就可以被理解,用在简历筛选问题上就难以被接受。
- 所以,不要对算法评判对错、评判好坏,算法的模型只是人思想的体现,如果算法出了问题,请回到人身上找问题
- 算法永远不会完美,在这里,我借用统计学家乔治·博克斯的一句名言:“所有的模型都是错误的,但有些是有用的。”算法也一样,没有好坏,有用就好
02 | 复杂度:怎样判断算法的效率高不高?
- 时间复杂度是衡量算法效率最主要的工具
- 时间复杂度也是一种指标,能够督促算法工程师不断改进算法,降低时间复杂度,提高效率。
- 评价算法效率的两个难题:① 单纯衡量时间,就忽略了 ”硬件因素“ ② 当算法解决问题所花时间无穷大时,用绝对时间就没法比较了。
- 教科书定义:时间复杂度是算法中某些基本操作的总数量,随着算法输入的规模而增长的函数关系。
- 基本操作的总数量:搬石头
- 输入的规模:金字塔高度
- 函数关系:图纸
- 而算法工程师的工作就是找到更好的“图纸”,找到效率更高、时间复杂度更低的算法
- 降低时间复杂度方法一:空间换时间
- 例:建立索引
- 面对时间复杂度,牺牲一些存储空间,换来更快的搜索速度一定是非常划算的
- 降低时间复杂度的方法二:分治思想
- 例:储存声音——波(太慢)——压缩:频率——傅里叶变换(太慢)——快速傅里叶变换(可行)
- 例:1+2+…+100——直接算(太慢)——高斯等差数列求和公式(可行)
03 | 启发:什么样的算法是巧妙的算法?
成功地建立贴近现实的模型,同时保持问题的可解性,是评价数学模型巧妙的一个重要角度。
- 例:找到美国大选不投票的人,设计太复杂就解不出来了,太粗糙又失去意义。
很多问题输入规模大到计算机也没法处理。这时我们需要谨慎地取舍,把问题规模降低到算法可以处理的范围。
- 例:“德州扑克” 问题:所有的可能性共有10的71次方那么多,比宇宙中原子的数量稍微少点儿,因此无法计算,但近几年的 “德州扑克算法” 就解决了这个问题。
算法经常采用迭代的方法局部逼近问题答案、如何保证收敛和收敛效率体现了算法设计师的巧妙。
- 例:小明穿蓝 / 黄衣服更受小美喜欢?—-> 为两个颜色设计随机数,哪个大就穿哪个—->这同样也是推荐算法的内核。
如果把这三个角度合在一起,你会发现,巧妙的算法常常有一个特点,就是背后的思想符合人的直觉。算法工程师厉害的一个原因,就是能把直觉的思路以一种明确的方式表达出来,转换成算法,然后攻克复杂问题。
04 | 反思:计算机能不能避免人的错误?
算法不能对问题负责——算法是工具,就算手里的锤子,锤子能钉钉子,但锤子不知道钉钉子要解决什么问题。
- 例:亚马逊一本40美元的教材书,两家二手书店的标价竟然分别173万美元和219万美元
- 例:对人说安全驾驶可以,对自动驾驶汽车说 “安全驾驶” 不行
算法不能对数据负责——如果数据就是垃圾,算法再好也白搭
- 例:检测糖尿病的仪器,把冰红茶样本放进去会显示已患糖尿病。
- 例:回到特斯拉的例子,为什么当时会撞上大货车,算法没有提出警示,立刻刹车呢?就是输入数据出了问题。自动驾驶仪错把天空的颜色和大货车车体的颜色混为了一体了,以至于没有意识到大货车是障碍物,所以没有减速和刹车
- 例:IBM公司有个沃森机器学习诊断系统,无法获得好的数据,因此没办法学习。
- 如果数据就是垃圾,算法再好用也白搭
算法不能对解释负责——算法科学家有时宁可放弃一定的准确性,也会去选择那些容易被解释和接受的算法
- 例:用算法看病,张三的检测报告说 “你得癌症了” ,但又说不清楚哪里的问题,张三肯定接受不了。
- 例:对于智能医疗诊断系统来说,到底可不可行?① 如果他的诊断和医生一样—->算法没用 ② 如果它的诊断和医生不一样,它又不能解释 —->算法没用
- 可以说,算法只能提供解决方案,不能提供解释。这是目前,人类抉择是否相信算法最大的困境。也就是说,这个问题,不只体现在医疗领域
二、设计算法
05 | 算法蓝图:怎样设计一个算法?
初学算法的人很容易掉进一个误区,认为懂的算法越多,就越厉害,这是不对的。算法是解决问题的工具,我们学习算法的目标是解决问题,让计算机更快更好地工作,这光靠算法懂得多可做不到。
打个比方,学英语肯定要背单词,很多学生能背1万个单词,可写作能力还是中学水平,而厉害的作家只用3000个常用单词就可以写出文学名著。我们现在想提高写作水平,不是比谁单词背得多,而是得提高写作能力。
怎么提高写作能力呢?算法工程师有一套用算法解决问题的标准流程,我管它叫“算法蓝图”,这一讲就说说什么是算法蓝图。
第一,明确问题——不明确问题会导致算法在设计中走很多不必要的弯路
首先是明确问题。等等,咱们都要讲设计算法了,怎么上来先谈明确问题?问题应该早就清楚了呀?
我负责地告诉你,还真不一定。我遇到过不少“武断”的算法工程师,做预测就要用回归分析,给产品分类就要上K临近算法,给用户推荐就要用神经网络,他们真的搞清楚问题是什么了吗?
其实产品经理和工程师可能都没错,只是需要在设计算法之前,就先明确问题,对问题的“方向”和“边界”先达成共识,再开始谈算法怎么实现
怎么算明确问题呢?我们可以从三个要素入手,明确目的、明确限制条件、明确评价标准
① 明确目的。对目的的描述可以有很多种,比如“匹配到所有的打车乘客”和“尽可能快地匹配到更多乘客”,或者“让车辆利用率达到最大”,这都是不一样的,究竟要选哪种目的需要在一开始就确立下来。
② 明确限制条件。比如,“每个乘客等待时间不能超过10分钟”,“市区乘客不能超过1分钟”,等等,要把量化的指标确立下来。能不能准确、快速判断限制条件的合理性,是非常考验一位算法工程师水平的。
③ 要明确评价标准。 标准的维度可以有不同的设定,比如时间、成本、收益等,但不可以没有。没有标准就无法判断问题是不是最终被解决了。
第二,建立模型——数学模型是对现实问题的近似和抽象,能够建立起计算机算法和问题之间的桥梁,为算法的效果进行预先估计
NBA球队都热衷于追求速度快。进攻速度快,投篮次数多,得分概率就大,赢面也就越大。这么说好像没问题,但换个视角看,投篮多的同时也会让对手篮板的机会增加,也会增加对手的投篮机会。
如果对手命中率更高,那快速推进比赛会不会更容易输掉比赛呢?
好像有可能。要解决这个问题,就不能直接上算法,而需要建立数学模型。
现实问题是没办法直接交给计算机的,我们需要一个数学模型来与计算机建立“桥梁”,可以说,建立模型的过程,也是把现实问题转化成算法问题的过程,用另一套语言来重新描述问题。
有时候描述一个问题,还可能需要多种数学模型的组合,而这些模型有层次,甚至会互相依赖,合在一起才完成“桥梁”的搭建,真正用数学语言描述了现实问题。
回到篮球比赛这个问题,怎么建模呢?如果是我,我会用“随机游走”模型来描述篮球比赛。
随机游走,是描述事物随机性变动的一种模型,比如觅食的动物走来走去的路径,股票价格上下的波动,分子在气体中的移动轨迹,都可以用随机游走模型来描述。而类似的思路也可以用来描述篮球比分。
大概思路是这样的:假设每次进球得分都简化成2分,两个球队的比分之间的差,就是一个不断变化的随机数X。如果A队得分,随机数就加2分,如果B队得分,随机数就减2分。
那么在这个模型里,只要我们知道两个球队每次进攻的进球概率,就可以计算出N个回合之后,随机数X是个什么样子,也就是两个球队分差的概率分布,这是跟回合N是有关的。
拿到概率分布,很容易就可以确立战术,在我们队进球率低于对方的时候,打的节奏越快,比赛回合数N越大,比分落后的可能性也就越大。相反也是一个道理,如果我们的进球率高于对方,节奏越快,赢的机会也就越大。
这是随机游走模型告诉我们的答案,至于这个答案是不是真的靠谱呢?还要拿到赛场上去试试才知道。
总之,提出一个问题,直接设计算法、编写程序需要大量的成本,如果没有模型也就对结果没有办法进行预估,有了数学模型,才能实现推理、预估或者预测。所以,在设计算法之前,一定要建立数学模型。
第三,选择算法——达成目标的好坏和时间复杂度决定了算法的选择
- 但请注意,数学模型并不是对现实问题的完美描述,建模的过程,也是大量细节被抽象掉的过程,在算法迭代中,模型迭代是非常重要的一环
- 等差数列求和的问题。高斯的算法非常好,只靠数学推导,就可以用时间复杂度极低的算法来解决问题,可以说是完美的算法,那么这类问题可能就不考虑其他算法了。
- 可遗憾的是,大多时候并不存在最优的算法,没有所谓的“唯一解”。有时候可能因为算法复杂度还不够低,有时候可能是还没设计出最好的算法。于是,算法工程师不可避免地要在不同算法之间做出选择。
- 算法各有优劣,算法工程师在选择的时候会考虑时间复杂度,也要考虑达成目标水平的高低,等等。
- 如何选出最适合的算法,是算法工程师面对的又一个重要挑战。那么,高手通常会怎么选择算法呢?第七讲我再给你详细讲解。
06 | 建立模型:如何把显示映射进计算机?
- 建模就是把复杂的现实问题,转化成数学语言的过程
- 数学模型无法描述全部客观现实,这就需要算法工程师做出取舍,找到最贴合现实问题的数学描述。
- 算法工程师会遵循三个步骤,不断迭代找出适合的模型
- 第一,确定假设,找到核心变量和关系,舍弃不重要的细节,把模糊问题,明确化。定量化。
- 例:在预测地球未来人口的模型中,我们先要搞清楚,需要得到一个什么精度的预测结果,如果精度要求不高,我们假设未来不会发生世界大战、计划生育政策等。
- 第二,验证模型,不断和现实问题作比较,验证是否足够贴合现实问题。
- 用常识验证:① 地球人口会一直以指数增长 ② 地球人口增长到一定程度就不会增长 。显然 ② 更符合常识。
- 把模型放在过去的数据上,验证是否准确
- 模型验证并不是总有固定的方法,有时候我们需要奇思妙想,打破常规思维才行。【例:开普勒日心说】
- 第三,权衡可行性,找到一个又能准确描述现实,又能有效求解的模型。
- 一个模型是不是最优选择,不仅要看模型是不是靠谱,还要看是否能实现
- 线性回归 / 神经网络 ≈ 小孩子画画 / 达芬奇画画 ≈ “豆浆油条” / 蒙娜丽莎,更多的细节,求解也更难
- 所以说,虽然模型的选择过程存在主观性,没有统一的标准说怎样才是最好。但它有一个底线,那就是模型必须能求得有效解
- 第一,确定假设,找到核心变量和关系,舍弃不重要的细节,把模糊问题,明确化。定量化。
07 | 算法选择:选择算法最终要的考量是什么?
今天对算法的认识已经不仅仅是问题、模型、算法了,还有数据。数据重新定义了我们对模型的思考方式,这也是今天算法工程师非常关注的一个维度。
模型和算法并不是一一对应的关系,建模不等于就可以完成算法选择
- 例:背包问题:尽快装走最值钱的东西;搬家扔什么;预算有限投放广告选择哪些渠道。
- 对于背包问题,可以选择的算法有很多↓↓↓
- “暴力算法”:可以把所有宝物放进背包所有的组合情况,全都计算一遍。选出价值最高的,又满足背包容量的组合
- “分支定界法”:还可以先选定第一件宝物,考虑“带还是不带走它”。无论这个决定怎么做,我们都做了一次分情况讨论。原来要从n个宝物里做选择的问题,就被转化成要从n-1个宝物里做选择。问题规模就变小了
- “基因算法”:这个名称的由来,是因为它的思路模仿了大自然中遗传变异的过程,把不同的宝物组合看成不同的DNA序列,让它们根据一定的规律相互交叉、繁衍,最终选出适者生存的那一个
在选择算法的时候,最重要的就是对质量和效率两个关键指标的权衡
- 没有免费的午餐定理——在很多算法问题当中,没有哪个算法是绝对最好的。要找到最适合的算法,一定要权衡算法在不同场景中的利弊
- 指标:① 时间复杂度 ② 解决问题的质量
- 算法工程师很在意算法解决问题的质量。而在时间复杂度和解决问题的质量水平之中的权衡,就成了算法选择的重中之重
- 只是绝大多数问题都不存在唯一解或者绝对正确的解,需要算法工程师不断根据场景、根据目标,在质量和效率之间做出合理的权衡,选出最合适的算法。
进阶:优秀的算法工程师还会考虑对算法的影响,更加偏好那些数据敏感度低,限制条件少,对数据依赖小的算法
除了质量和效率,一名优秀的算法工程师还会有更进一步的考量,就是数据。
我们经常会遇到这样的情况,数据并不准确。
数据敏感度低:算法工程师通常更青睐那些对数据错漏有容忍度的算法,就算个别数据存在问题,也不会对算法结果造成太大影响。
限制条件少: 给某些用户投广告的成本是负数,啥意思呢?就是说给他推送广告,不光不花钱,还赚钱。要有这样的好事,当然要给这些人多多推广告才对啊。可问题是,贪心算法这时候就失效了。
因为贪心算法是按投资回报比排名的,但如果成本是负数,投资回报比也是负数,这些用户在贪心法中的排名就会到最后。也就是说,用贪心算法永远都选不到他们。
这你就发现了吧,贪心算法在背包问题当中,要求广告成本和收益都是正数。
这就是一些算法的限制条件问题,它们只在某些条件下能够发挥作用。那么算法工程师在选择算法的时候,也会考虑到限制条件,如果限制条件太严格,数据又不满足,就要考虑那些对限制条件要求比较低的算法了。
对数据依赖小: 数据不够怎么办?
AlphaGo打败李世石的版本就依赖了大量的人类棋谱数据,但之后的AlphaGo Zero可以直接与自己对弈,省掉了对大量数据的依赖。
假如有两个算法,用1亿张图片训练出了A算法,准确率达到95%,那就远远不如,用100张图片训练的B算法,准确率达到90%。
三、算法策略
08 | 迭代:怎样一步步接近答案?
迭代,是一步一步重复某个固定操作,逐步接近答案的策略
例:科学家用App找车
迭代算法就是通过循环重复某个固定的操作,每一步以前一步的结果为出发点,逐步逼近问题的答案。
迭代算法能有效运行,有两个条件必须满足:一个是算法必须收敛,一个是不动点必须唯一
芝加哥所有其他给史教授发出干扰信号的汽车,都是不动点。史教授站在任何一个不动点上面,无论他向哪个方向前进,App上显示的距离都会增加。算法会让史教授待在原地不要动。只要史教授最开始没站在自己车的位置上,那就永远找不到自己的车,因为迭代过程卡住了。所以说,使用迭代算法的时候,算法工程师需要对不动点的数量进行一个分析。如果我们能确认不动点只有一个,那么迭代算法就总能收敛到想要的结果。如果多于一个,我们就不能保证得到想要的答案。
但有人可能会问,为什么我们想要找的答案只有一个,迭代算法会有多个不动点呢?
这跟迭代算法的步骤,问题自身的结构有关,有点复杂,咱们就不具体说明了。你只要记住多个不动点问题,是使用迭代算法时需要克服的困难就好了。
比如说,机器学习算法中对最优参数的选取就面临这个问题。如果某组参数是不动点,但却不是最好的,更新参数的迭代算法就会卡住,从而得不到最优的参数配置。
迭代算法的运行速度快,是因为它放弃了一点点解决问题的质量,换来了大幅的速度提升
09 | 分治:怎样拆解问题,逐个击破?
- 分治算法是通过回溯,不断分解同样的问题,直到问题小得可以直接解决,再把小问题的解合并成原来问题的解的算法策略。
- 例:假设你是中国网球公开赛的总裁判。今年的比赛,有64位选手参加。而你的任务是执法比赛,决出冠军。你可以偷懒,外包两个裁判去判分……
- 确保要解决的问题能分解成原问题类似的子问题,并且这些子问题之间互相独立,这时分治策略才能奏效。
- 例:背包问题,就不能用分治法
- 如果分解问题和合并结果不复杂,分治策略能减少算法的复杂度。
- 例:计算游戏子弹是否击中头部,可以将所有子弹一分为二
- 分治策略开启了并行计算的大门,利用多CPU硬件上的优势,可以减少算法的运行时间。
- 例:因为子问题互相独立,所以可以并行计算,而迭代则不行
10 | 动态规划:怎样从小问题出发,逐级解决大问题?
- 动态规划指的是既是多步骤的决策优化问题,也是解决这些问题的算法方法
- 例:比如说咱俩现在要做一个游戏。桌上有一堆糖果,你我轮流从当中取走几颗。每次至少取一颗,最多取三颗。谁拿到最后一颗糖果谁赢。假设这时候桌上还有50颗糖果,轮到你来取了,你会取几颗呢?
- 动态规划算法是在多步骤的策略优化问题满足最优子结构的时候,用以始为终、以小建大的方向解决问题的算法策略。
- 动态规划的效率会受“维度爆炸”的影响。
11 | 分支定界:怎样决定谁是 “ 被淘汰者 ”
- 组合优化是一类特别难解决的问题,它的搜索空间大,我们很难确定谁是最优解。
- 例:给整个北京市建立20个充电站,怎样最优?
- 分支定界法是把分支、定界、剪枝三个过程结合在一起,减小搜索空间,保证找到组合优化问题的最优解的算法策略。
- “定界”就是估计某个子搜索空间中最优解的上界的过程。
- “剪枝”是当某个子搜索空间能获得的目标上界,比不上某个已知的可行方案,就直接把这个子空间淘汰的过程
- 用算法领域的话来说,分治需要对问题的“输入”进行分解,而分支需要对问题“解的搜索空间”进行分解。
- 要让分支定界高效,从根本上是要进行有效的剪枝。为了进一步提升分支定界法的效率,我们可以使用提前停止策略。
分支定界为什么能节省计算时间?
因为它主要解决了“维度爆炸”的问题,先在某个维度上分支,只在这个单一维度来二选一,进而换到第二个维度二选一,而不是综合所有维度一一对比,因此节省了计算时间。
12 | 启发式:放弃最优解之后,怎么办?
遇到特别复杂的组合优化问题时,如果找不到最优解,我们可以转而使用启发式算法,找到不错的可行解。
- 旅行商问题:想要旅行中国30个算法,怎样规划路线更合理。
启发式算法是人们通过对问题的理解,以某一套规则制定出来的一类算法。
元启发式算法是通过人们对自然或者人类解决问题时通用逻辑的观察和模拟,总结出来的一系列通用的启发式算法。
例:基因算法,利用的是遗传中“适者生存”的道理,把适应度低的解淘汰掉。
蚁群算法,是利用蚁群信息素的概念,对网络问题进行求解。
粒子群算法,模拟鸟类觅食的过程,可以对最优解的位置进行搜索。
13 | 蒙特克罗:丢失确定性之后,怎么办?
- 对问题中的随机事件进行取样,为有限个样本进行独立计算,最后把每个样本结果进行统计的策略叫蒙特卡洛算法。
- 例:早餐店备货难题。
- 蒙特卡罗方法最适用于随机变量多,计算逻辑复杂的问题。
- 随机模拟不是万能的。它会占用大量的计算资源,依赖于参数的正确性,并且对解释问题本质没有太大帮助。
- 例:(依赖参数正确性)预测美国总统大选 X
- 例:(对解释问题本质没有太大帮助)备货难题的本质是:对多备货带来的浪费成本和少备货带来的顾客流失成本之间的平衡。
四、算法前沿
14 | 机器学习:机器到底在学什么?
让机器自己学习
机器学习算法是一系列让计算机主动学习的算法。它们最适合用在人类没法用明确规则进行解决的问题上。
有一个关于机器学习的经典案例,我们不能不提它。
2012年,美国明尼苏达州的一位父亲,怒气冲冲地投诉了塔吉特超市的市场部。因为超市给他还在上高中的女儿,发了各种婴儿衣服、婴儿床的广告。超市想卖婴儿用品想疯了吗,要对未成年的女孩兜售?
这位父亲万万没想到的是,她的女儿确实怀孕了。只不过,塔吉特超市的机器学习算法,赶在这位父亲之前知道到了这一点。
怎么回事呢?原来,塔吉特超市有各个消费者的消费记录。算法能根据消费习惯对消费者进行分类,找到他们某些行为和生活中大事件的相关性。
比如说,一位用户同时买了无香型的润肤露和钙镁锌营养品,那她或者她的家人就有很大可能已经在妊娠期了。
机器学习学到了很多人类没教过、自己也不懂的事物细节。
- AlphaGo 的 第二局的第 37 手棋,AlphaGo走出了一招世界顶尖棋手都不会走的一步棋。
机器学习学到的是事物之间的复杂关系。
15 | 学习策略:机器学习如何获得知识?
- 机器学习模拟了不同的学习模式,学习模式不同,学到的知识也不一样,但也许能解决的问题是一致的。
- 机器学习得到的知识传回给人类并不容易,但又很必要,我们还在探索更好的传回方法。
16 | 算法思维:怎么和算法工程师打交道?
- 很多人关注的是眼下问题的特定结果,而算法工程师更在意通用方案,解决更多更广泛的问题。
- 学会拿数据和算法工程师沟通。数据越多,质量越高,算法工程师对你要解决问题的兴趣也越高。
- 和算法工程师最好的互动方式,就是一起在抽象模型和显示场景中来回转换。