『终极算法』摘抄笔记-是否存在终极算法

『终极算法』摘抄笔记-是否存在终极算法

同样的算法做不同的事情

朴素贝叶斯算法是一个可以用短方程来表达的学习算法。只要提供患者病历的数据库,包括病人症状、检查结果,或者他们是否有什么特殊情况,朴素贝叶斯算法就可在一秒之内做出诊断,而且往往比那些花几年在医学院学习的医生还要强。该算法还可应用于学习垃圾邮件过滤器,乍一看这和医疗诊断毫无关系。

最近邻算法的用途十分广泛,从笔迹识别到控制机器人手,以及推荐你可能喜欢的书籍或者电影。

决策树学习算法也同样擅长决定你的信用卡申请是否应被通过、寻找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个单位长度的路线。
我们可以随便画几条线说就是它了,只要我们人品好,计算之后路径长度98,比100小。于是答案出来了,存在比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) 进行许可。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×