算法通识

这是一篇关于算法通识的思维导图，主要内容包括：算法要求极其严苛的明确性，算法的优势在于模型化，时间复杂度是工具，越贴近现实的模型评价越高，有些问题规模（数据）大到算法也无法处理，算法经常迭代，算法不负责，算法解决问题的基本蓝图，选择算法最重要的考量是什么，怎样一步步接近答案，怎样拆解问题，逐个击破，怎样从小问题出发，逐级解决大问题。

算法通识

• 算法要求极其严苛的明确性
• 算法的优势在于模型化
  • 有了模型可以在不同领域快速迁移
• 时间复杂度是工具
  • 可以用来衡量、比较算法
    • 比如一分钟算出来和一天算出来
  • 时间也是一种指标
    • 帮助工程师不断改进
    • 同时降低复杂度，提高效率
  • 想要降低复杂度
    • 可以用空间换时间
      • 比如原来一台服务器扩充为十台
• 越贴近现实的模型评价越高
  • 比如投票算法中的线性效用模型
• 有些问题规模（数据）大到算法也无法处理
  • 这个时候要把问题规模降低到算法可处理范围
  • 例
    • 德州扑克
      • 52张牌
      • 每个于家下注四轮
      • 可能的组合是10的71次方
    • 解
      • 手里两张手牌
        • 梅花K
        • 黑桃K
      • 相同情况
        • 红桃K
        • 方片K
      • 这样可以把要处理的总数据减小了6倍
• 算法经常迭代
  • 通过不停的调整算法参数
    • 进而逐步逼近真相相近的参数
• 算法不负责
  • 不对问题负责
    • 负责的是开发（使用）工具的人
  • 不对数据负责
    • 如果给的是垃圾数据，再好的算法也白搭
  • 不对解释负责
    • 算法科学家有时宁可放弃一定的准确性
    • 去选择那些更容易被解释和接受的算法
• 算法解决问题的基本蓝图
  • 明确问题
  • 建立模型
    • 建模就是把复杂的现实问题，转化成数学语言的过程
  • 选择算法
    • 算法和模型不是一一对应关系
    • 选择算法时的两个关键指标
      • 质量
      • 效率
      • 更进一步，考虑数据对算法的影响
  • 迭代
    • 三步骤
      • 第一步，确定假设
        • 找到核心变量，舍弃不重要的细节，把模糊的问题，明确化、定量化。
      • 第二步，验证模型
        • 不断和现实问题做比较，验证模型是否足够贴合现实问题
      • 第三步，权衡可行性
        • 权衡可行性，找到一个能准确描述现实，又能有效求解的模型
    • 迭代算法
      • 两个条件
        • 一是收敛
        • 二是不动点必须唯一
      • 运算速度快，是因为放弃了一点点解决问题的质量
        • 换来的是大幅的速度提升
  • 建模
    • 就是把复杂的现实问题，转化成数学语言的过程
  • 选择模型时不能光追求模型的准确性，同时也要权衡它的可行性高低
• 选择算法最重要的考量是什么
  • 算法和模型不是一一对应关系，建模不等于就可以完成算法选择
  • 最重要的就是对质量和效率两个关键指标的权衡
  • 优秀的算法工程师还是考虑数据对算法的影响，更加偏好那些数据敏感度低，限制条件少，对数据依赖小的算法
• 怎样一步步接近答案
  • 迭代
    • 是一步一步重复某个固定操作，逐步接近答案的策略
  • 迭代算法有效运行的两个必须满足条件
    • 算法必须收敛
    • 不动点必须唯一
  • 迭代算法的运算速度快，是因为它放弃了一点点解决问题的质量，换来了大幅的速度提升
    • 例：最后的结果是无限接近于事实但不绝对
• 怎样拆解问题，逐个击破
  • 分法算法
    • 是把同样的问题进行不断分解，直到问题小得可以直接解决
    • 再把小问题的解合并成原来的问题解
  • 确保要解决的问题能分解成与原问题类似 的子问题，并且这些子问题之间相互独立，这时分治策略才能奏效
  • 如果分解问题和合并结果计算不复杂，分治策略能减小算法的复杂度。
  • 分治策略开启了并行计算的大门，利用多CPU硬件上的优势，可以减少算法的运行时间
• 怎样从小问题出发，逐级解决大问题
  • 动态规划
    • 指的是既是多步骤的决策优化问题，也是解决这类问题的算法方法
    • 是在多步骤的决策优化问题满足最优子结构的时候 ，用以终为始、以小建大的方向 解决问题的算法策略
    • 动态规划的效率会受“维度爆炸的影响”
• 怎样决定谁是“被淘汰者”
  • 组合优化是一类特别难解决的问题，它的搜索空间大，我们很难确定谁是最优解
  • 分支定界法
    • 是把分支、定界、剪枝三个过程结合在一起，减小搜索空间，保证找到组合优化问题最优解的算法策略
    • 要让分支定界法高效，从根本上是要进行有效的剪枝。为了进一步提升分支定界法的效率，我们可以使用提前停止的策略。
• 放弃最优解之后，怎么办？
  • 特别复杂的组合优化问题，如果找不到最优解，可以使用启发式算法，找到不错的可行解。
  • 启发式算法
    • 是人们通过对问题的理解，以某一套规则制定出来的一类算法
    • 元启发式算法是通过人们对自然或者人类解决问题时通用逻辑的观察和模拟，总结出来的一系列通用启发式算法
    • 启发式算法是针对特定问题设计出来的，需要具体问题具体分析。
      • 启发算法重要特征
  • 不到迫不得已，算法工程师并不会用它
    • 启发式算法对最优解没有保证
    • 启发式算法好不好用，是一个试错的过程
    • 子主题 3
• 丢失确定性之后，怎么办？
  • 蒙特卡罗方法
    • 对问题的随机事件进行取样，为有限个样本进行独立计算，最后把每个样本结果进行统计的策略
    • 最适用随机变量多，计算逻辑复杂的问题
    • 随机模拟不是万能的，它会占用大量的计算资源，依赖于参数的正确性，并且对提示问题本质没有太大帮助
• 机器到底在学什么？
  • 机器学习算法
    • 让计算机自主学习的算法。它们最适用在人类没法用明确规则进行解决的问题上
    • 机器学习学到了很多人类没教过、自己也不懂的事物细节
    • 机器 学习学到的是事物之间的复杂关系
• 机器学习如何获得知识？
  • 机器学习模拟了不同的学习模式，学习模式不同，学到的知识也不一样，但也许能解决的问题是一致的
  • 机器学习得到的知识传回给人类并不容易，但又很必要，我们还在探索更好的传回方法
• 怎么和算法工程师打交道？
  • 很多人关注的是眼下问题的特定结果，而算法工程师更在意能用方案，解决更多更广泛的问题
  • 学会拿数据和算法工程师沟通。数据越多，质量越高，算法工程师对你要解决问题的兴趣也越高。
  • 和算法工程师最好的互动方式，就是一起在抽象模型和现实场景当中来回转换。
• 基因算法
• 分支定界法
• 暴力算法
• 深层神经网络模型
• 线性回归