机器学习与逻辑编程

gentle2008 2019-03-14

展开全文

你可能没有想到，机器学习（machine learning）和逻辑编程（logic programming）有一种奇妙的关系，在我眼里她们就像亲姐妹。

很多人都了解机器学习，可是很少有人理解逻辑编程。在这篇短文里，我简要介绍一下逻辑编程是什么，然后讲讲它与机器学习的相似之处。也许你会从中得到某种启发。

逻辑编程是什么

说到逻辑编程（logic programming），人们不禁想到 Prolog 之类晦涩的逻辑式编程语言。有些人上本科的时候被迫学过 Prolog，但从来不知道它有何意义。毕业之后再听到 logic programming 这个词，就只剩下敬畏和茫然，或者觉得是没用的老古董。

逻辑编程由于它自身的局限性而没能广泛应用，但它是很美的东西。逻辑编程的有些思想已经悄悄应用到了最先进的编程语言之中。比如所谓“类型推导”（type inference），基本就是逻辑编程的思想。不理解逻辑编程，你会很难理解这些东西，总觉得高深莫测。

所以不要让功利心限制了你的想象力。最近研究机器学习，我发现逻辑编程与机器学习之间有着有趣而隐秘的关系。这些古老的思想，再次在我这里显示出它的光辉。

其实逻辑编程的原理可以被很轻松的解释清楚，而不需要理解 Prolog。要理解逻辑编程是什么，你只需要看一个很简单的例子：

有一个未知数 X，我们不知道它是多少，但我们知道：

X + 2 = 5

请问 X 是几？

用自然语言总是显得不够精确，所以我现在用一种叫 miniKanren 的逻辑式语言来把上面的问题写出来：

(run* (x)               ; 求 X 所有可能的值
  (exists (x)           ; 存在一个未知数 X
    (== (+ x 2) 5)))    ; 目标：X+2=5

请注意这段代码与上面的中文描述之间的一一对应关系。如果你不理解这代码也别担心，继续往下看。

逻辑语言系统会给你结果：X 等于 3。请注意，这段代码里面始终没有出现 5 - 2 这样直接的表达式。我们只是告诉系统 X + 2 = 5 这个“目标”，然后询问 X 的值。也就是说，我们只是向系统描述了我们“要什么”，而没有告诉它“怎么做”。我们没有具体说要怎么得到结果，系统却知道去计算 5 - 2。

这种编程方式也叫“描述式”（descriptive）编程，它不能用其它几乎所有编程语言来表达（C, C++, Python, Java, Go, Scala, Haskell, Rust, Swift…）。原因在于，使用普通的编程语言，你不能把“未知数”当成一个值来进行演算。

在我们的例子里面，X 的值是未知数，所以当普通语言看到 X + 2 这样的表达式，它就无法运行。它会报错：使用未初始化的变量 X。也就是说，你必须先知道 X 的值，你才能说 X + 2。

但在像 Prolog 这样的逻辑式语言里面，“未知数”是可以被作为一个正常的值来进行计算的。它们可以被传递到其它函数里，可以被放进数据结构，可以进行复杂的逻辑组合操作，就像你在操作一个普通的数字或者字符串一样。

逻辑式程序中一般会有一个（或者多个）“目标”（goal）。目标一般是一个判断表达式，也就是说它的值是布尔类型（boolean）。这里我们的例子里只有一个目标，就是“X + 2 = 5”。也就是说，我们想要 X 加上 2 等于 5。

当逻辑式语言看到了目标，就把目标记下来。最后程序员开始提问：X 是几？这时候，逻辑语言的运行系统开始进行“反向计算”，找到未知数的值，使得目标的值为“真”（true）。在我们的例子里，系统会告诉你：X 等于 3。

为什么叫做“反向计算”呢？因为

我们先声明了未知变量 X，
然后我们提出目标 X + 2 = 5

对于复杂一点的程序，1 和 2 之间可能还有其它的代码。我们最后的问题，却是问最开头声明的变量 X 等于几，所以系统从最后面的目标 X + 2 = 5 出发，“反向”推导出 X 的值。

这就是为什么研究逻辑式编程的人把这种操作叫做“反向计算”。也许你会觉得这个例子完全不能说明逻辑编程的价值，那我给你一个稍微复杂点的例子吧：

有一个未知数 X，我们不知道它是多少，但我们知道：

4 * (X + 1) = 24

请问 X 是几？

对应的 miniKanren 代码：

(run* (x)
  (exists (x)
    (== (* 4 (+ x 1)) 24)))

如果你想深入理解逻辑式编程，我建议你看看 Dan Friedman 的书『The Reasoned Schemer』。但目前你了解到的这些，应该足以读完这篇文章。

机器学习与逻辑编程的相似点

你可能已经明白了逻辑编程是什么。下面我们来看看它跟机器学习有什么关系。

首先我们看到逻辑编程有“目标”（goal），比如 X + 2 = 5。在机器学习中有一个对应的东西，那就是误差函数（loss function）。只不过逻辑编程的 goal 是个等式，而机器学习的 loss function 是个函数。

逻辑编程系统会为你选择未知数的值，从而精确地“满足”这个 goal。而机器学习的目标呢，是要为你选择未知数的值，最小化这个 loss function，使得误差最小。看到相似之处了吗？所以，机器学习可以被看成是“在连续空间中的近似的逻辑编程”，而逻辑编程可以被看成是“在离散空间中的精确的机器学习”。

逻辑编程有“反向计算”，机器学习有“反向传递”(back propagation)，而它们的工作方式，有着惊人的相似之处。只不过机器学习因为是连续空间的，所以需要使用微积分的原理，而不只是简单的逻辑组合。

实际上逻辑编程必须先进行正向计算，构造出含有未知数的结构，然后进行所谓“unification”，求出未知数的值。而机器学习也类似，你必须进行一遍正向计算（forward pass），然后才能进行 back propagation，求出导数，并且更新“weight”的值。

逻辑编程的“未知数”（比如 X），对应了机器学习的 weight。实际上，机器学习的 weight 本质就是“未知数”。你需要得到它们的值，使得 loss function 最小，但一开头你不知道它们是什么，所以你给它们一些随机的初始值，让系统开始正向计算。机器学习的 weight 和逻辑编程的未知数如此的相似，它们可以被作为普通的值，与输入进行计算操作（Conv 等操作），直至你遇到 goal 或者 loss function，然后你掉头回去调整未知数的值……

机器学习框架是程序语言

所以呢，我看到了它与编程语言的优雅知识之间的联系，看到了它是对于“计算”概念的一种扩展。机器学习把“计算”和“微积分”有趣地融合在了一起。

实际上，你可以把机器学习的各种框架（framework）看成是新的编程语言，它们不同于 Python 或者 C 一类的过程式语言，而更像 Prolog 这样的逻辑式语言。这些语言会自动对代码求导，优化未知参数，使得误差最小。如果要起一个名字，也许可以把它们叫做“可求导编程语言”（differentiable programming language）。

写 framework 的工作，实质上是设计编程语言，解释器，编译器。而有些 framework 所谓的“计算图”，实质就是编译器中的 data-flow graph 或者 control-flow graph 一类的东西，所以你可以用相关的方式进行处理。

PL 理论可以指导机器学习框架的设计。不同的框架对应着编程语言里面的不同设计。比如，动态语言和静态语言的差别，对应着 Pytorch 和 TensorFlow 的动态计算图和静态计算图的区别。所以编程语言曾经犯过的错误，都将在机器学习框架中体现出来，不管它们的设计者是否意识到它们与编程语言之间的联系。

目前这些语言还处于初级阶段，表达力比较弱，有各种不完善的地方。由于机器学习解决的是连续的数值问题，机器学习的“模型”一般要很简单才行，否则很可能出现学习不收敛的情况。所以我还不知道编程语言的很多概念能否顺利的迁移到机器学习上面。

但目前看来有一些很明显的对应关系和发展趋势：

Feed-forward 网络，比如 CNN 一类的，对应了编程语言中最简单的表达式，或者叫“纯函数”。其中没有递归，也没有副作用。它只能处理图像一类具有固定长度的数据。
RNN（LSTM）对应的是程序语言里含有单个递归（循环）的函数。由于递归函数对应的是“递归数据结构”，这就是为什么 RNN 可以处理文本这类线性“链表”数据。
Neural Turing Machine 及其后续的研究 Differentiable Neural Computer，试图把更广阔的编程概念引入到机器学习里面，处理任意复杂的数据结构，比如图结构。

编程语言和机器学习的这个联系，是优雅而让人回味的。