讀古今文學網 > 人工智能的進化 > 第8章 符號與符號處理 >

第8章 符號與符號處理

這一章名為「符號與符號處理」,實際是介紹計算機科學。計算機科學始於艾倫·圖靈的圖靈機研究(見On computable numbers, with an application to the Entscheidungsproblem)。有些學者推崇非符號形式的人工智能(例如文章Connectionist AI, symbolic AI, and the brain),但他們實際談論的依然是符號處理,只不過是在用數字代表符號(如符號代數中的例子),而非使用非數字概念(如符號邏輯中的例子)。

這兩個例子談到的問題是計算機科學的核心,且非常有趣。一道題可以有多種解答方法,並且屬性各不相同,計算機科學家花了大量時間和精力研究算法,即題的各種解答方法(參見Algorithmics: The Spirit of Computing)。

在符號代數中,求解方程組的標準算法是高斯消元(Gaussian Elimination)(參見Schaum』s outline of theory and problems of linear algebra)。其屬性是,對於具有n個變量的n個方程,通過大約n3步可以求得一個解。這就是說,即使方程組裡有成百上千萬個變量,依然能夠解決。

但在符號邏輯當中,目前為止最好的算法可能就是DPLL(數字鎖相環,可參見文章Satisfiability solvers的例子)。邏輯問題存在有n個變量,求解大約需要2n步The intractability of resolution。(而證明這點則需要根據消解規則,對DPLL進行變體(A machine-oriented logic based on the resolution principle),文中已經提到)。這就是說,即使是最快的計算機,對於只有100個變量的邏輯問題也無能為力。

這又引出了兩個問題。首先,我們在想是否會有比DPLL更好的算法。在數學領域,這個問題的精確版就是著名的P=NP問題,這個問題由斯蒂芬·庫克(Stephen Cook)於20世紀70年代首次提出(參見The complexity of theorem-proving procedures)。從那時起到現在,雖然已有成千上萬名計算機科學家和數學家竭盡全力,試圖攻克難題,但是依然沒有答案。由於這個問題與其他眾多題目息息相關,因此被視為計算機科學領域最為重要的開放問題(參見文章The status of the P versus NP problem)。

第二個問題涉及前一章提到的長尾現象。DPLL的工作方式是系統性地搜索邏輯上的所有可能。有趣的是,在隨機構建的測試當中,DPLL執行此類操作所需的步驟卻都很少。實際上,上述測試所需的步驟與上一章中的長尾數字非常相似。因為樣本測試案例越多,平均值就越高,所以在實踐中,根本不可能估算出DPLL所要求的步數。有關詳情,請參閱Heavy-tailed phenomena in satisfiability and constraint satisfaction problems一文。

如果需要其他材料來教孩子系統學習這些程序,請參考Computational thinking一文。