## 同样的算法做不同的事情 朴素贝叶斯算法是一个可以用短方程来表达的学习算法。只要提供患者病历的数据库，包括病人症状、检查结果，或者他们是否有什么特殊情况，朴素贝叶斯算法就可在一秒之内做出诊断，而且往往比那些花几年在医学院学习的医生还要强。该算法还可应用于学习垃圾邮件过滤器，乍一看这和医疗诊断毫无关系。 最近邻算法的用途十分广泛，从笔迹识别到控制机器人手，以及推荐你可能喜欢的书籍或者电影。 决策树学习算法也同样擅长决定你的信用卡申请是否应被通过、寻找 DNA 中的绞接点，以及下棋时指导下一步该怎么走。 在机器学习领域，如果提供适当的数据来让机器学习，那么相同的算法既可以处理信用卡申请，也可以下棋。实际上大量的机器学习应用仅仅由几个算法来负责。 终极算法假设：所有知识，无论是过去的、现在的还是未来的，都有可能通过单个通用学习算法来从数据中获得。 有没有这种算法，可以接收任何数据及假设并输出隐藏其中的知识？当然，我们得限制假设的可能性，否则如果把整个目标知识都以假设形式赋予算法，那就是在作弊。我们可以通过限制输入的规模、要求假设弱于当前学习算法等方法，来实现这个目的。 大脑负责我们能感知以及想象的一切。如果某物存在，但大脑无法对其进行学习，那么我们就不知道它的存在。我们可能只是没看见它，或者认为它是随机出现的。 不管怎样，如果将大脑放入计算机中运行，那个算法就能掌握我们能学会的一切。因此发明终极算法的一种途径（可以说是最流行的一种）就是对人脑进行逆向解析。 生物多样性源于自然选择机制。而计算机科学家对该机制非常熟悉：我们通过反复研究尝试许多备选方法来解决问题，选择并改进最优方案，并尽可能多地尝试这些步骤。进化论是一种算法。上帝创造的不是物种，而是创造物种的算法。 利用足够多的数据，一种简单的算法能掌握什么？关于这个问题最经典的例子就是进化论。输入进化论这个算法的信息是所有存在过的、活着的生物的经历以及命运（对现在的算法来说是大数据）。这个进化论算法已经在地球上最强大的计算机运行了 300 多万年——这台强大的计算机就是地球自己。 在物理学中，适用于不同数量的方程往往可以用来描述发生在不同领域的现象，例如量子力学、电磁学、流体动力学。波动方程、扩散方程、泊松方程表明：一旦我们在某个领域发现它们，也很快能在其他领域发现它们；一旦我们在某个领域懂得解开它们，也能在所有领域将它们解开。 此外，所有这些方程都很简单，涉及几个和空间、时间有关的数量的相同导数。很容易想象，它们都是主方程的几个例子，而终极算法要做的，就是用不同的数据集来将它实例化。 根据一个统计学流派的观点，所有形式的学习都是基于一个简单的公式——贝叶斯定理。贝叶斯定理会告诉我们每当看到新的证据后，如何更新已有的想法。一种简单的贝叶斯学习算法对世界进行一系列假设，由此开始进行学习。当它看到新的数据时，与该数据匹配的假设更有可能会成立（或者不可能成立）。 贝叶斯定理就是将数据变成知识的机器。据贝叶斯统计学派的观点，贝叶斯定理是将数据变成知识的唯一正确方法。如果该学派的观点正确，贝叶斯定理要么就是终极算法，要么就是推动终极算法发展的动力。 在计算机科学中，P 和 NP 是两类最重要的问题。如果我们能有效解决它，那么这个问题就属于 P；如果我们能有效找到其解决方案，那么这个问题属于 NP。著名的 P=NP 的问题就是，能有效找到的问题是否可以得到有效解决。因为 NP 完全问题，回答这个问题需要的只是证明某个 NP 完全问题可被有效解决（或者无法被有效解决）。 关于什么是 P 问题，NP 问题和 NPC 问题这里做一点补充。 首先，解释一下时间复杂度的概念。时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。即对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。 不管数据多大，程序处理花的时间始终不变，即具有 O(1) 的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是 O(n)，比如找 n 个数中的最大值；而像冒泡排序、插入排序等，数据扩大 2 倍，时间变慢 4 倍的，属于 O(n^ 2) 的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是 O(a^ n) 的指数级复杂度，甚至 O(n!) 的阶乘级复杂度。 时间复杂度可以分为两个级别。一种是 O(1),O(log(n)),O(n^ a) 等，我们把它叫做多项式级的复杂度，因为它的规模 n 出现在底数的位置；另一种是 O(a^ n) 和 O(n!) 型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。 P 类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于 P 问题。 NP 问题是指可以在多项式的时间里验证一个解的问题。NP 问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。 例如在需要枚举时，我们可以首先进行猜测。求最短路径的问题中问从起点到终点是否有一条小于 100 个单位长度的路线。 至于这道题是怎么做出来的，就是因为我们找到了一个比 100 小的解。在这个题中找一个解很困难，但验证一个解很容易。验证一个解只需要 O(n) 的时间复杂度，也就是说我可以花 O(n) 的时间把我猜的路径的长度加出来。只要猜的好就一定能在多项式的时间里解决这个问题。猜到的方案总是最优的，不满足题意的方案也不会来骗我去选它。这就是 NP 问题。 接下来是 NPC 问题，即存在这样一个 NP 问题，所有的 NP 问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的 NP 问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的 NPC 问题，也就是 NP-完全问题。NPC 问题的出现使整个 NP 问题的研究得到了飞跃式的发展。 NPC 问题的定义非常简单。同时满足下面两个条件的问题就是 NPC 问题。首先，它得是一个 NP 问题；然后，所有的 NP 问题都可以约化到它。证明一个问题是 NPC 问题也很简单。先证明它至少是一个 NP 问题，再证明其中一个已知的 NPC 问题能约化到它。 弄明白蛋白质如何折叠成特定形状；通过 DNA 来重新构建一系列物种的进化史；在命题逻辑中证明定理；利用交易成本来发现市场中的套利机会；按照给定回报率找出最安全的投资组合、到达几个城市的捷径、微芯片上元件的最佳布局方案、生态系统中传感器的最佳布局、自旋玻璃门最低的能量状态；安排好航班、课程、工厂工作；最优化资源分配、城市交通流、社会福利，以及提高你的俄罗斯方块分数。这些都属于 NP 完全问题。 NP 完全问题，意思是如果你能有效解决其中一个问题，就能有效解决所有 NP 类问题，包括相互间的问题。谁会猜到，这些表面上看起来迥然不同的问题，会是同一个问题？如果它们真的是同一个问题，就可以说一种算法能学会解决所有问题（或更准确地说，所有能有效解决的例子）。 我们寻找终极算法的过程是复杂且活跃的，因为在机器学习领域存在不同思想的学派，主要学派包括符号学派、联结学派、进化学派、贝叶斯学派、类推学派。 本文作者：思考问题的熊 版权声明：本博客所有文章除特别声明外，均采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 (CC BY-NC-ND 4.0) 进行许可。 如果你对这篇文章感兴趣，欢迎通过邮箱或者微信订阅我的 「熊言熊语」会员通讯，我将第一时间与你分享肿瘤生物医药领域最新行业研究进展和我的所思所学所想，点此链接即可进行免费订阅。是否存在终极算法
神经学科的证据
进化学科的证据
物理学科的证据
统计学的证据
计算机科学的证据
我们可以随便画几条线说就是它了，只要我们人品好，计算之后路径长度 98，比 100 小。于是答案出来了，存在比 100 小的路径。后续
· 分享链接 https://kaopubear.top/blog/2018-02-17-TheMasterAlgorithm1/