[关闭]
@yy125 2017-09-04T09:27:22.000000Z 字数 9179 阅读 112

算法=逻辑+控制

AI

Robert Kowalski是一位逻辑学家和计算机科学家，从70年代末到整个80年代致力于数据库的研究，并在用计算机证明数学定理等当年的重要应用上，颇有建树，尤其是在逻辑、控制和算法等方面提出了革命性的理论，极大地影响了从数据库，到编程语言，直至今日的人工智能。

算法=逻辑+控制

其流传最广的理论之一，是用谓词条件逻辑的短句形式（clausal form)，来阐明和对比解决问题的模型，并用于设计编程语言和如何解决实际问题，PROLOG语言即是这些理论的具体实践。

正如他在《算法=逻辑+控制一文》里指出的，算法包括两部分：
i） 逻辑， 即需要完成什么？
ii）控制： 如何完成？
算法的效率往往可以通过提高控制部分的效率，而无须改变逻辑部分，也就无需改变算法的意义。
举个阶乘的例子： X(n)！= X(n) * X(n-1) * X(n-2) * X(n-3)* ... * 3 * 2 * 1.
逻辑部分用来定义阶乘：
1. 1是0的阶乘；
2. 如果v是x的阶乘，且u=v*(x+1)，那么u是x+1的阶乘。
用这个定义，既可以从上往下地将x+1的阶乘缩小为先计算x的阶乘，再将结果乘以1 （Recursive，递归），也可以由下而上逐个计算一系列阶乘的结果 （iteration，遍历）。

控制部分用来描述如何使用逻辑。最粗略的看法可以认为“控制”是解决问题的策略，而不会改变算法的意义，因为算法的意义是由逻辑决定的。对同一个逻辑，使用不同控制，所得到的算法，本质是等价的，因为他们解决同样的问题，并得到同样的结果。因此，我们可以通过逻辑分析，来提高算法的效率，保持它的逻辑，而更好地使用这一逻辑。比如，有时用自上而下的控制替代自下而上，能提高效率。而将自上而下的顺序执行改为并行执行，也会提高效率。
算法的逻辑和控制都会影响效率。 而逻辑和算法的界限也不是一刀切。同一个算法可以按A=L1+C1或A=L2+C2来分析。 第一个分析里认为是逻辑的部分，第二个分析会算作控制。

一般来说，我们分析时，偏向于将能提高效率的部分，算作控制。

将逻辑用于解决问题

70年代末，如何用计算机证明数学定理，吸引了很多研究者。 这也是编程理论得到大力发展的阶段。比如，用计算机证明四色定律等等——美国的地图就是用这样的计算机算法确定的涂色方案。
当时，学者们所关心的，是如何开发出既灵活，又可扩展到解决新问题的程序？ 语言、语义、控制、算法之间的关系怎样？
作为逻辑学者，Robert Kowalski认为，逻辑研究的是如何从假设推导结论，不管这些假设是否正确，也不管所需要解决的问题是什么。因此希望用逻辑学的思路，通过逻辑、目标、执行等概念来设计程序。

谓词条件逻辑（Predicate Logic)

Kowalski所使用的是谓词条件逻辑（Predicate Logic）。 这和传统逻辑不一样的地方在于，传统逻辑认为下面的两个断言完全不一样：
A. 范冰冰是美女;
B. 张静初是美女。
而谓词条件逻辑增加了两个概念： 谓词和量化。 比如“是美女”是谓词，A和B有一样的谓词。 而张静初和范冰冰是变量a的不同值。这个做法正源自逻辑学的逻辑形式。比如：
QQ截图20170830073748.png-13.4kB
方框、椭圆框和叶形框分别代表3个变量。三个子句的句式和联系是逻辑形式，这个逻辑形式是“形式正确”（formally valid)，因为方框，椭圆框和叶形框里无论取任何值，只要保证第1，2句正确，那么第三句就一定正确，不可能找出反例。
因此，谓词条件逻辑将子句进一步分解成谓词和参数，可以进一步求解让子句正确和错误的参数值，把逻辑问题变成计算问题，并由此诞生了语法（syntax, 即哪些符号和表达式是合法的），和语义（semantics, 即这些符号和表达式的意义是什么？）

子句、逻辑、查询和执行

所谓子句（Clause），是具有主谓宾，并意义完整的最短句子，不能进一步拆分。 Kowalski用子句形式来表现谓词条件逻辑，造就了PROLOG语言。比如sibling(X,Y):-parent_child(Z,X),parent_child(Z,Y)是典型的子句逻辑，读作“sibling(X,Y)为真，如果parent_child(Z,X)且parent_child(Z,Y)。” 其中，"sibling(X,Y)"称为“头”（Head）， ":-"之后部分称为“体”（Body）。

让我们仔细看看这种早期的AI语言。PROLOG里有三大概念： 逻辑、查询（Query）和执行。

逻辑

PROLOG的代码主体是“逻辑”，是用子句描述关系。子句可以有多个条件和多个结果，比如, 其中是结论，是条件。 一个特例是，最多有一个结论的子句：，称之为Horn子句。这也是逻辑编程里所用的。具体来分，有四种Horn子句：
1. 断言： ,比如mother_child(trude, sally)，意思是trude是sally的母亲，为真；
2. 过程声明：, 即如果都为真，则为真；
3. 否定：，即且且为假；
4. : 否定；

纯Prolog的子句包括规则(rule)和事实（fact)。parent_child(X, Y) :- father_child(X, Y)属于规则, ":-"即是上面提到的“<——”，读作“if”， 这语句的意思是：parent_child(X,Y)为真，如果facther_child(X,Y)为真。
mother_child(trude, sally)属于事实：意思是mother_child(trude,sally)为真。
Prolog里也允许某些命令型语句，比如在屏幕上打印某个字符。　

  1. mother_child(trude, sally).
  3. father_child(tom, sally).
  4. father_child(tom, erica).
  5. father_child(mike, tom).
  7. sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).
  9. parent_child(X, Y) :- father_child(X, Y).
  10. parent_child(X, Y) :- mother_child(X, Y).

查询(Query)

通过某个查询，来执行程序。这个查询也称之为Query，或者Goal（目标，或后面提到的“所要做的”）。比如查询erica是不是sally的兄弟姐妹，答案是“YES"。

  1. ?- sibling(sally, erica).
  2. YES

Goal这个称谓也体现Kowalski的逻辑学思维模式，下面会继续讲到。

执行

正如Kowalski谈到的：“可以用一系列子句来描述我们所看到的世界，并通过证明这些子句的正确与否，来推导出所要做的（目标或Goal）的正确与否。”

当用户提交查询（Query），即开始“执行”。这也就是控制部分，分为自上而下，和由下而上。用自上而下的控制策略，将否定形式的目标（），分解成子目标，逐步往下。并通过SLD等求解策略，找到能推翻否定的变量值，进而求解。
具体过程如下：
1. 要证明“？- sibling(sally, erica)”，就是要找到Z，满足(parent_child(Z,sally)）且 parent_child(Z,erica)为真。
2. 要找到parent_child(Z, sally)，第一个可能性是father_child(Z, sally)， 第二个可能性是mother_child(Z, sally)。我们先从father_child(Z, sally)试试。
3. 因为father_child(tom, sally)， 所以Z=tom；
4. Z=tom是否满足parent_child(Z,erica)？ 根据father_child(tom, erica)，为真。
5. 该查询成功返回“YES”。 因为没有求变量值，所以不返回变量值。

可以看作一个搜索树，要遍历所有可能的计算。比如第二步的father_child之外，还有mother_child。 如果father_child)这步计算得不出结果，需要回撤追踪（backtracking）其他分支。
自上而下的解决策略，意味着将目标（query）分解成子目标，直到所有子目标都能通过最初的断言求解。但这样的分解势必产生无关的分支，比如第二步会产生mother_child(Z,sally)。 因此需要配合某些过程（proof procedures)来加以解决，比如Prolog里的SLD Resolution借助搜索树来实现。

正如Kowalski提到的，“编程语言应把逻辑和控制区分开，在执行机制上提供更强大的求解功能”，PROLOG提供了一些革命性的执行手段，比如不确定性(non-determinism)，并行，和按规律匹配的过程调用（Procedure call by pattern-matching)等。
什么是不确定性呢？ C是确定性语言，每个执行步骤的下一步都有且仅有一步。而Prolog的下一步可能有多种不同步骤。 比如要获得平方根：

  1. a_sqrt(X,Y) :-
  2.         X > 0,
  3.         Y is sqrt(X).
  4. a_sqrt(X,Y) :-
  5.         X > 0,
  6.         Y is -sqrt(X).

同一个过程，有两个不同的定义，每个定义都包括两个子句。 编译器会警告，但仍然会通过。

过程调用（Procedural Interpretation)

让我们放大看看子句如何转化为过程（Procedure）。
1. 过程，即 ；
2. 过程名，即B，是结论，也代表该过程求解的问题；
3. 过程体，即，是一组过程调用；
4. 目标，即，完全由过程调用组成。
满足一定条件时，目标里的会调用过程。
注意，
1. 过程体是一个集合的调用，而不是一个序列的调用，因此可以按任何顺序调用或者并行调用；
2. 多个过程B可能和过程体中的某个调用同名，找到正确的过程是个搜索问题。可以通过按顺序、并行或用更复杂的办法尝试不同的过程来解决；
3. 过程B的参数可变，是由过程调用所决定。 因此如果某个过程B，是用来测试某个关系对某些个体是否成立时，这个过程也可以用来找到哪些个体能让该关系成立。

逻辑和控制的关系

前面提到，通过自下而上和从上到下两种控制策略处理同样的逻辑形式，可以产生不同的表现。 而信息也可以采用不同的逻辑形式表现，不同的表现形式能比不同的控制更大地影响效率。以排序为例，排序的一种定义逻辑可以是： 

  1. 对x排序，产生y <——— 将x重新排列产生y, 且y是有序的。

无论用那种控制，排序效率都不够高。然而，让我们换一种逻辑，采用经典的quicksort来定义，即：
QQ截图20170902095622.png-9.5kB
即使采用最简单的自上而下的顺序控制，效率也很好。
和“重新排列”、“有序”等谓词一样，这种quicksort里的"emtpy","first","rest", "partition", "appending"等谓词也可以独立定义，和“排序”的定义无关。 所以，Kowaslki认为，应先定义逻辑部分，再定义控制部分。逻辑部分和所需解决的问题有关，不仅决定算法的意义，而且会影响算法的效率。

控制部分指明解决问题的策略，将影响算法的行为，而不影响其意义。在以往的逻辑编程（logic programming)体系里，控制部分从属于逻辑部分，既可以由开发者用单独的关于控制的语言进行开发，也可以由系统自行决定。比如数据库查询，系统会完全自行决定控制策略。他认为，能更好地描述控制的语言更适合于高级的程序员，他们可以更好地控制计算机来达到更高效率。

数据结构

数据结构也属于逻辑。好的程序应该将数据结构和过程（procedure)分开，过程会查询和处理数据结构。因此，数据结构可以单独改变，而不影响上层的过程。通过用更有效的数据结构，能改善算法，而且更高层次的程序也可以先开发，再确定数据结构。

让我们看看加上数据结构的quicksort算法，和前面完全和数据结构无关的quicksort有什么区别。
我们定义一个数据结构：

  1. null为空<—
  2. cons(x,y)的第一个元素是x <—
  3. cons(x,y）的其他元素是y <—

之前的quicksort算法也需要定义"emtpy", "first"和"rest"等谓词，而加上该数据结构后，程序可以变得更高效：

  1. 对nil排序得到nil<—
  2. 对cons(x1,x2)排序得到y <— 用x1将x2分为两段，分别记为u和v,
  3.                           对u排序得到u1，
  4.                           对v排序得到v1,
  5.                           将u1后面加上cons（x1,v')得到y.

将数据结构分离出来，也让程序更加可读，否则数据结构和过程混在一起还需要提供额外的文档。

自上而下的过程调用

最简单的自上而下是顺序执行。通过协程（Coroutine)或相互通信的并行进程，通常可以改善算法。比如如果按顺序执行这样的排序：

  1. 对x排序，产生y <— 将x重新排列产生y, 且y是有序的。

程序会先对x重新排列，然后对结果测试，看顺序是否正确。通过协程(Coroutine)的方式来执行调用，程序可以一个元素一个元素地进行重新排列。每当产生一个元素时，暂停产生其他元素，直到能确保该元素和前面已完成的部分的排序正确，再往下进行。

同样，quicksort算法里的调用既可以顺序进行，也可以并行。一旦确定了x2中的第一个元素，即可对x2开始分段。对产生的u,v两段的排序也可以并行执行——只要u,v各自的第一个元素产生，即可并行开始。只要得到u1的第一个元素和u排好序的部分，即可开始合并。

将逻辑和控制部分分离，和将程序和数据分离类似。把程序和数据分开，更容易区分数据的功能，和如何完成这些功能。 把逻辑和控制分开，也更容易区分程序要做什么（逻辑部分），和如何做（控制部分），也更容易确定程序的执行是否正确。

自上而下和由下而上

程序员往往用自上而下的方式实现递归。 但是自上而下并不总是更高效，比如斐波那契数列就更适合由下而上：

  1. 第0个斐波那契数字是1 <—；
  2. 第1个斐波那契数字是1 <—；
  3. 第u+2个斐波那契数字是x <—；
  4.     第u+1个斐波那契数字是y <—；
  5.     第u个斐波那契数字是z <—；
  6.     x=y+z;

自上而下的计算是树形，节点是过程调用，数量按u的指数上升，而由下而上的计算步骤数是按u线性增长。 同时，自上而下所占的空间和u成正比，而由下而上只需要存储两个断言和常数大小的数据。

评估不同过程的策略

当多个过程都能产生同样的结论，就无法仅靠逻辑部分来从多个进程里筛选出正确结果，因此就需要遍历算法，来从多个选择中逐一筛选。
虽然所有的遍历都可以用递归定义+自上而下执行来替代，某些遍历更适合看作自下而上地执行递归定义，比如前面提到的自下而上地计算阶乘。 还有些遍历可以看作一种控制方式，从多个选择里进行顺序搜索。比如下面这个例子，假设：

  1. Parent (Zeus, Ares)<—；
  2. Parent (Hera, Ares)<—；
  3. Parent (Ares, Harmonia)<—；
  4. Parent (Semele, Dionisius)<—；
  5. Parent (Zeus, Dionisius)<—；

Parent(Zeus, Ares)的意思是Zeus是Ares的父或母。如果要找Zeus的孙子或孙女u：

  1. <— Grandparent (Zeus, u)；

用传统编程，需要借助一个二维数组和两个遍历的循环，一个嵌套在另一个里。当找完Zeus的孙子或孙女后，跳出。 自上而下地执行也类似，按顺序一个个地调用过程，逐个尝试可能的过程，寻找Zeus的孙子或孙女.
对传统的遍历搜索的逻辑分析不涉及递归，而涉及到从多个选择里顺序搜索，这和执行不确定性(non-deterministic)的程序所采用的回溯追踪（backtracking)的策略类似。
和关系型数据库的数据模型类似，用子句来代表数据，而不是用独立的”项“（terms)。数据是个体间的关系。 传统数据结构里，数据按独立的“项”来表示时，开发者需要在程序和查询（Query）的逻辑部分写清楚如何存储和访问。用关系（子句）来描述和存储数据时，开发者只需要在逻辑部分描述数据，而让控制部分去管理存储和访问。
这在数据库里很常用。好处是今后控制部分的存储和访问的机制即使改变，或者改善，对于用户来说，逻辑部分的数据也不受影响。
访问数据的搜索策略是否合适，取决于数据存储的结构。顺序搜索的遍历方式适合于按列表或数组形式存储的数据。而对于其他数据结构，比如哈希表、二进制树、语义网络等，更适合其他搜索策略。

路径寻找算法的两种分析

同一个算法可以用不同方式分析：

  1. A=L1+C1=L2+C2

在一个分析里，某些行为由控制部分决定，比如C1，在另一个分析力可能由逻辑部分决定，比如L2。路径寻找可以说明同样的算法如何用不同的方式分析。 如何找到下图中从A到Z的路径？
image.png-7.2kB

第一种算法引入一个谓语条件子句，表示可以到达x. 因此，上题需要两个子句来解决：
1. 可以到达A： ；
2. 不可能到达Z：，并希望找到能推翻这个结论的值；
从A到B的线路可以由代表，即如果能到A，则能到B。
因此，上图变为：
image.png-9.3kB
这就需要两种不同的控制策略，一种从A出发向前搜索所有路径。这是从下而上； 另一种是从Z出发向后搜索，是自上而下。 从A和Z同时出发进行搜索，结合了自上而下和从下而上两种推导。 是每次找一条路径，还是同时找所有路径，要看所用的搜索策略。
另一种分析，我们用代表可以从x到达y，除了目标子句和描述子句，因此逻辑部分只需要一个子句。
image.png-9kB
无论是从A出发，还是从Z出发，都是自上而下地从目标开始：<—。 先求解，再求解是向前搜索，而先求解，再求解是向后搜索，先求解，再求解则是向后搜索。在两组问题里采用协程（Coroutine)就能实现双向搜索。从已知的路径图条件出发，从下至上的推导，当发现x到y有路径时，也能产生一条直接连接。

结论

Kowalski的《算法=逻辑+控制》指出，同样的算法，常常用不同的形式展现。第一种是在逻辑部分加入一个简洁明确的语句，比如某种能解决问题的知识。然后在控制部分用复杂的策略来解决问题； 第二种是在逻辑部分加入复杂的逻辑，而在控制部分用简单的策略来解决问题。
70年代末，虽然数据库已经逐渐将控制和逻辑分开，而编程语言还没有进行区分。 开发者将逻辑和控制都编写在同一语言里，而执行部分仅仅会用最初级的解决问题的功能。 如果编程语言能把逻辑和控制区分开，在执行机制上能提供更强大的问题解决功能，像用计算机证明数学定律（intelligent theoretem-proving）的系统那样， 那么程序将更加正确、更容易改善，也更容易应用到新的问题上。

后记

Kowalski的一直从事这方面研究，并一直致力于更适应人工智能的理论和模式研究， 2015年Kowalski在里斯本的ICAART里讲到自己关于AI的理论，他认为有智者（Intelligent Agent,包括人和机器)涵盖了三个概念：它所观察到的（Observation)，所相信的(Belief)和所应该做的(Goal)。有智者的的任务是，通过不断地观察，确保自己所应该做的（Goal）是正确的。

它所应该做的，比它所相信的更重要。将它所要做的和所相信的按某种逻辑联系起来，即是计算逻辑(Computational Logic)。通过观察——思考——决策——行动的周期，计算逻辑将它所相信的和它要做的联系起来。

这一理念主要区别于基于规则的生产系统（Production rule system)。 后者一般由If...then这样的“规则”组成，本身没有逻辑。比如，一个典型的基于规则的生产系统是这样的：
Goal(所应该做的)是:fire(t)——>Elimination(t+1)和Escape(t+2); （当时刻t着火时， t+1时去灭火，t+2时逃跑）;
当某天真的着火了，
所观察到的Observation:fire(1);
所采取的行动Action: Escape(3)
这虽然达到了通过观察，采取正确行动的目的，但是对人类复杂的世界过于简单：如果遇到的不是火，而是小偷怎么办？
因此，可以改为：
所要做的(Goal):threat(t)——>Elimination(t+1)和Escape(t+2); （当时刻t遇到危险时， t+1时去消灭之，t+2时逃跑）;
所相信的(Belief): threat(t)<——fire(t);
当某天真的着火了：
所观察到的Observation:fire(1);
行动Action: Escape(3)
今后随着所相信的增长，小偷、小强、地震都认为是threat, 这样，对观察到的更多情况，也能采取正确的行动。

因此，有智者应该有计算逻辑，将它“所相信的”（Belief），结合它所观察到的，去做它“应该做的”（目标，Goal）。虽然有智者所要做的比所相信的重要，但所相信的能帮助他们做正确的事。
将“所相信的(Belief)”和“所应该做的(Goal)”区分开，在数据库里很常见。
比如，Manager(x)——> Employee(x): 如果x是Manager, 那么x是employee, 这是数据库所相信的，即视图。
一致性约束就是数据库所应该做的目标，比如检查以下的约束:
manager(X)——> 是否存在Y，并存在supervises（X，Y）的关系？
employee(x),employer(x)——>为假；
supervises(X,Y),supervises(X',Y)——> X=X'

所以，Kowaski认为，*关系型数据库比某些AI系统更聪明，因为他们明确地知道所要做的和所相信的之间的区别和重要性。 因为数据库将所相信的和所要做的用逻辑表示，而AI系统常用规则（Production Rules）*来描述。
因此，他将“所相信的”（逻辑编程）和“所应该做的”（一致性约束）结合起来，产生了循证式逻辑编程（Abducible Logic Programming）。有兴趣的同学可以继续研究。

Forward and backward reasoning. s
QQ截图20170901072700.png-20.4kB

What's missing?
QQ截图20170901072700.png-37.5kB
思考可以用一个框架来总结，无论思考采取什么行动，所要做的是什么，还是相信什么。
思考包括搜索(search)，和推断（inference)
我们先找一个对象，再cong
当着火时，

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注