|
|
本帖最后由 Sareth 于 2021-1-31 22:06 编辑
《算法之美》摘录
1.最优停止理论
37%定则(选取候选人)
见好就收时机(在有失败风险时如何适时退出)
最优停车位置(距离目的地约1.5公立时选择停车位)
2.探索与利用
(选择探索新鲜事物,还是选择现有已知的最好,通常取决于人的剩余时间)
*探索本身就有收益
*遗憾是将我们的实际行为与事后认定的最佳行为进行比较后得到的产物。
*每次拉下老虎机把手时遗憾的数量以对数速率增加(前十次造成的遗憾与后90次造成的一样多)
*如果采取了一种遗憾最少化算法,就有望减少每年新增的遗憾数量。
*上限置信区间算法,(面对不确定性时的乐观主义)乐观主义是防范遗憾的最有效措施。
*互联网是全世界规模最大的对照实验
*“胜者优先”算法,提高已成功选项的选取概率
*只要事物在不断变化,探索就不该偃旗息鼓(现实中更多的是不安分的老虎机,获胜几率、回报率会有变化)
*童年是人生的探索阶段,孩童的探索行为与玩老虎机的赌徒行为本质并无不同。
*理性的做法是强调探索的重要性
*当人们生命接近终点时,他们希望更多地关注对他们来说最重要的人。
3.排序
*排序的规模越大,难度越大
*冒泡排序,插入排序两种传统排序法没有很好的效率
*合并排序✓
*桶排序+插入排序✓
*提前预估未来的用途,很多时候排序的费时得不偿失
*冒泡排序效率差,但抗噪能力强,比较计数排序容错能力更强
*动物族群中会自发地进行地位排序的斗争,每位新成员都会接受排序的洗礼
*使用一个统一的指标基数进行排序,是现代社会成立的必须
4.缓存
*需要保存什么,怎么保存
*现代电子设备普遍有6层分级存储器体系
*最优缓存清理策略:缓存已满时,将未来最长时间内不会再次使用的数据从缓存中清理出去。
*清理方式
a.随机清理
b.先进先出FIFO
c.最近最少使用LRU(最有效)(时间局部性,与计算机解决问题的方式相关)
*最接近于未卜先知的做法是假定历史会重演
*图书馆适用b与c的缓存原则
*预测千人的购买行为时,大数定律就会生效
*给自己的生活不同四级缓存,公共仓库-家中地下室-衣橱-小柜子
*最近最少原则同样适用于电脑文档整理(把最新使用的文件放到文件夹最左侧)
*大脑的记忆能力基本上是无限的,但大脑的搜索时间是有限的
*现实本身有一个同艾宾浩斯曲线相符的遗忘趋势
*衰老带来的不是记忆力衰退,而是知识变多而带来的信息管理难度
5.时间调度理论
*安排时间是有必要的
*最早到期日原则(先处理到期日最早的任务)
*最短加工时间原则(优先处理耗时短的任务)
*“权值”,每项任务所带来的利益数额,或单位时间重要性(重要优先值参考标准)
*重要的不止是把事做好,更重要的是把权值更高的事做好,要学会忽略扰乱生活的琐事和无效信息
*优先级反转,最高优先级任务时常会被不断冒出的中低优先级任务抢先次序
*从后往前的顺序建立时间表,把到期日最后的任务排在日程表的最后
*用“猜测”代替“计划”,并放轻松,你并不需要日程表,只需要一个代办事项清单
*开启一项工作以及切换工作本身就会耗时,持续工作16个小时比持续工作8小时的效率远不止2倍(但这不该是压榨的借口)
*当同时执行过多的任务时,人和电脑都可能会宕机。防止的方法,一是提供更多的代办事项存储空间,二是学会说不
*假使不知道哪个任务优先度更高,可以选择直接先做起来,这能省去排序所消耗的时间和精力
*你应该尽可能长时间停留在一个任务上,而不是将你的反应降低到最低可接受的限度以下(参考操作系统的交互,你会反感不好好给你反馈的电脑)
*等到固定时间间隔进行一次
6.贝叶斯法则
*根据结果来对概率做出估计
*拉普拉斯定理:
如果买n张彩票共w张中奖,那么中奖率就是中奖数加1,除以所购买的数目加2,
即(w+1)/(n+2)
*无信息先验预测:(无先验信息时)将已存在的事物预计存续时间翻倍
*正态分布(高斯分布)
*拥有最多新流量的事物就会是最知名的(最大的城市、最有声望的公司、最多人追随的名人)。(幂律分布)
*将正态分布作为贝叶斯法则的先验
*幂率先验,相乘法则
正态分布,平均法则
厄兰先验,相加法则
*做出准确预测最好的方法,是准确地了解你所预测的事。(过去经验的积累)
*“棉花糖实验”中,孩子们对未来的预期,会显著影响他们抵抗诱惑的能力。
*人会更多地诉说有趣的,不寻常的事,这影响了我们经验统计的判断。
(媒体对事件的报道并不与其在世界上发生的频率相符)
7.过度拟合
*对一件事的优劣对比(左边列出好处,右边列出坏处,好坏权衡相削后得出最后的选择)
*并非使用一个更复杂的模型就会更好。
*当我们处理经常遇到的数据噪声或估算不准时,过度拟合就会随时构成危险
*我们拥有的数据与我们想要的预测之间的差距无处不在。
*过度拟合在生活中随处可见:
味觉喜欢脂肪、糖、盐(重要营养物质,但导致肥胖)
过度健身,使用类固醇
击剑运动因为电子计分设备而偏离击剑运动本身
公司绩效考核...
学校考试
警官模拟训练导致留下致命习惯动作
*用交叉验证检验过度拟合:
对学生进行标准化考试,随后抽调一两个学生进行差样化测试(写文章、口头考试等),
当考试成绩提升,但差样化测试成绩下降,则证明学生的技能对考试本身出现过度拟合
*用套锁算法惩罚复杂性
*已知信息越少,就约需要用简单的办法,防止过渡拟合
8.松弛
(在高难度与低难度之间选取一个合适的)
*把离散问题放宽为一个连续问题,再把结果中不到0.5的分数看做概率
*拉格朗日松弛算法:将一些不可能的事降级为惩罚,将匪夷所思的变成不可取的。
9.随机
*抽样分析可以给出答案,而其他方法可能无法做到(只是可能不精确)
*米勒-拉宾素数测试
*用多个随机数来验证式子是否正确
*蒙特卡罗算法:抽样调查
*确定性:“我们要做的是想出一个答案来节省你的时间和空间,并权衡第三个纬度:错误概率。
*贪婪算法:一种只考虑当前利益的算法。(并不有效)
*

*指数退避算法(2,4,8,16):为避免信号冲突而使用的方法(已成为处理几乎所有网络故障或不可靠性的默认方式)
*日常生活中的指数退避:一周,两周,四周,八周....(而不是连续尝试几次后完全放弃),永远不会完全放弃(有限耐心,无限仁慈的方法)
*传输控制协议AIMD,和式增加,积式减少(每次加一点,失控时减半)
*“彼得原理”:晋升或出局
*反馈语:一个糟糕的听众往往会毁掉一个故事
*缓存膨胀:排队区拥挤导致延迟。用“尾部丢弃”法减少膨胀。生活中的缓存膨胀无处不在。
*显式拥塞通知(ECN)
*对于大文件,带宽是关键;人际间的应用而言,快速的周转时间更重要。
11.博弈论
*递归:预测他人的预测,思想模拟正在模拟思想的思想(无穷无尽的循环)
*扑克牌水平:第一级为我知道,第二级为你知道我知道,第三级为我知道你知道我知道...“你真的只希望比对手高一个水平”
*纳什均衡策略:在剪刀石头布对决中,随机平均地乱出可能获得更多的胜率。
*不能想当然地认为游戏参与者能够发现或达到游戏的均衡,游戏设计者不能用均衡来预测玩家的行为
*囚徒困境。调和率:衡量合作和竞争之间的差距。
*公地悲剧:每个个体的利己行为最终导致坏的结果
*修改并制定规则,来改变坏的平衡
*道德是个体的群居本能-尼采
*信息瀑布:在正确的环境下,一群行为完全理性、完全正确的行为者,仍然可以成为有效的无限错误信息的牺牲品。“一旦一个人决定盲目追随他的前人,不依赖自己的信息信号,他的行为会对所有后来的决策者毫无意义。”(潮流,羊群行为)
*维克瑞拍卖:“密封投标”,出价第二高者胜(最好的策略为以你评估的“真正价值”竞标)
*“他人即地狱”:不要被他人的想法左右
去寻找那些诚实策略占优的游戏! |
评分
-
查看全部评分
|
|
|
|
|