AM：作為啟發式搜索的機器數學發現
人工智慧發展至今的半個多世紀以來，機器發現（machine discovery）一直是一個重大主題。機器發現，指的是運用機械化方法以進行科學發現的工作，又稱為機械化科學發現（mechanization of scientific discovery）、自動科學發現（automating scientific discovery）、計算機科學發現（computational scientific discovery）。無疑可以說，把目標直接朝向科學的機器發現是人工智慧領域的一種非凡努力。
機器發現的兩個要點是：其一，運用機械化的方法；其二，本身目的是為了進行科學發現。也就是說，並非「有計算機參與進行科學發現的工作」都是機器發現。編製程序的目的和作用不能夠僅僅是計算（比如：實驗室中用計算機來分析數據），它必須在科學理論的架構中起到關鍵作用，比如：自動（或人機互動地）得出關鍵「概念」、「定理」、「猜想」等體現了人類才思的東西。
人工智慧專家已在數學、物理學、化學、生物學、天文學等各科門類完成了許多機器發現程序，這些程序豐富和發展了科學研究方法，同時也提供一些極好的案例，以檢驗和補充已有的科學方法論。本文擬分析一個著名的機器數學發現程序：AM（Automated Mathematician，簡稱AM），該程序由利奈特（D. B. Lenat）於1970年代中期編寫完成，是一個在初等數論和集合論方面搜索概念和猜想的計算機程序，它的成功使得利奈特在年僅25歲時就享譽整個人工智慧領域。
本文考察的是：AM做出了什麼數學發現？AM程序是如何實現的？AM的發現方法是什麼？如何評價AM？
AM發現了什麼
AM是一個數學理論自動生成程序。我們知道，概念、定理和公理是數學理論的基礎結構，而數學猜想是數學研究的重要方法。重要的數學猜想往往對數學發展起著舉足輕重的作用，眾所周知的哥德巴赫猜想就是一個例子。數學家所做的工作主要是：定義數學概念，提出數學定理和數學猜想，並對它們進行證明。
與之相應，當前的機器數學發現程序大多分為兩類：理論自動生成程序（Automated theory formation program）與定理機器證明程序（machine theorem-proving program）。後者指向「證明」，即用機械化的方法來證明一些已有的數學猜想和定理，我國著名數學家吳文俊院士的工作就屬於幾何定理的機器證明；而前者主要指向「發現」本身，即用機械化的方法得出合理的數學概念、猜想和定理，本文所論及的AM是第一個理論自動生成程序。由於數學理論自動生成領域20多年來一直未有重大進展和理論突破，AM至今仍然是最著名的經典數學理論自動生成程序。
AM在集合論和初等數論領域中進行探索而自動得出了大量的數學新概念和新猜想。集合論和數論是數學的兩個重要的基礎分支。集合論主要研究集合之間的關係（相等、包含），集合運算（交、並、補、差、對稱差）以及運算規律（交換律、結合律、分配律、吸收律、德 · 摩根律）；而初等數論主要研究自然數的性質、數與數之間的關係和數列等。
AM程序在開始運行時，只給定了115個簡單的集合論概念，如集合、相等、包含、交、並、差、除等。從這些概念出發，在數論領域運算了幾個小時後，AM最後成功地發現了200個新概念，其中半數可以作為有意義的概念而為數學家所接受。
下面談一談AM所完成的數學發現的總體情況。
AM經過探索而發現了大部分明顯的集合論上的關係（如德·摩根定律：）。AM自動建立了猜想，如「一個集合永遠不能是自身的元素」和建立新集合鏈的過程中「將一個集合插入自身」。經初期探索後，AM認定，把「相等」這一概念一般化是有價值的，從而發現了「同樣大小」（same-size-as）這一關係。基於此發現而產生了「自然數」概念，且隨後AM很快又建立了大部分簡單的算術運算。由於加法是作為集合併的類比而提出的，而乘法相應於重複的替換，所以當AM發現它們相關（即N+N=2×N）時十分驚奇，此後AM以三種其他方式重新發現了乘法：作為加法的重複，作為集合的笛卡兒乘積的數字類比，以及使用兩集合之並的冪集的基數，此時發現了數的4次冪和4次方根。完全平方數和完全四次方數的概念也被分離出來。奇數、偶數、取倍、取半、整數平方根等許多有趣的數值運算和數類被發現。
AM由乘法的結合律和交換律知道，乘法可取一組數作為它的自變數，在定義乘法的逆操作時，將這一性質定義為：「任意一組大於1的數，它們的乘積是X」。這恰是對數X因子分解的定義。具有最少個數因子的數就是所謂的素數。素數對是以奇妙的方式發現的：通過限制加法的定義域和值域為素數（即取在素數中的解）而得到。算術基本定理（即每個整數都有唯一質因數分解）和哥德巴赫猜想（大於2的偶數是兩素數之和）是通過對稱方式猜想到的。通常數用一維表示，這裡代之以作為一組素數的表示。然而AM未能提出指數的記法。在增加一些幾何概念後，AM開始發現某些更廣泛的聯繫，提出了相應於平行、等量、相似、全等、平移、旋轉等概念和許多沒有一般名稱的概念的新定義，來代替對線段、角、三角形相等的定義。AM還發現了哥德巴赫猜想的一個巧妙的幾何解釋，即已知角度是素數的所有角，則0°至180°所有角都可近似地表示為這些角中的兩個之和。
從以上可看到，AM得出的重要理論——無論是素數、哥德巴赫猜想還是算術基本定理——都是數學史上已有的概念和猜想，其之所以被稱為「新」，是對AM程序本身而言的。也就是說，AM所做的工作不是機器數學發現（discovery），而是機器數學再發現（rediscovery）。
通過日誌機制實現非定向的啟發式搜索——如何發現？
機器用於發現，其實就是設計出不同的發現程序。而不同的程序，從某種意義上說就是不同的演算法（algorithm）和不同的啟發式（heuristic）。所謂演算法，就是解題的系統步驟，比如乘法表給出的加減乘除規則。而啟發式，就是能夠減少、排除搜索路徑的任何合理經驗知識。其實人類在解決問題時常常會使用到啟發式。比如：科學家在根據實驗數據構造定理時，會憑直覺嘗試一些數學形式，而不是嘗試所有的數學形式，那同時也不可能窮盡。
作為一個啟發式搜索程序，AM有自己顯著的特點。
1. 理論驅動的發現程序
AM是一個典型的理論驅動發現程序。AM最初除提供了115個集合論概念外，還被賦予了250條啟發式。概念和啟發式形成了一個理論系統，AM的運行就基於這一理論系統來進行。程序從這115個概念出發，通過啟發式選擇搜索路徑而得出新的數學理論：獲取新概念，研究概念的性質以及概念與概念之間的關係從而得出猜想。AM輸入的初始條件和輸出的結果都不是數據，而是理論。
通過與數據驅動程序的對比可以幫助我們更好地理解這一點。典型的數據驅動發現程序是蘭利（P. W. Langley）、西蒙（H. A. Simon）等開發的6個版本的BACON程序。以BACON.1為例，該程序的目標是再發現開普勒行星運動第三定律。BACON.1的初始時給定了開普勒當年觀測行星記錄下來的原始數據，並被賦予了相關啟發式。程序通過啟發式的引導而反覆檢驗數據，直至得出定律。可以看到，BACON.1的運行基於原始數據組成的資料庫來進行。
在科學史上，數據驅動和理論驅動的科學發現例子都存在。歐氏幾何公理體系的建立是理論驅動，而歐姆定律的發現則為數據驅動。這兩種方法都對科學發現起著推動作用。
2. 框架表示法
為了構建理論系統，AM採取了框架表示法：每個概念都被賦予一個框架表示（frame），每一個框架有25個側面（facet）或稱為槽（slot），如「名稱」、「定義」、「實例」、「價值」等，而每一個側面沒有、有一個或有許多入口（entry）。其中的「價值」側面尤為值得注意，它對一個概念是否值得探索給出了一個數值評價，該值會隨著程序的運行而隨時改變。
以「集合」概念為例圖示如下。
「集合」概念的框架表示圖
在AM最初的115個概念中，大部分概念的大部分側面都是空的，它給AM提供了一個確定的但卻是巨大的搜索「空間」，並由250個啟發式來引導，以試圖填滿這些空側面。有些啟發式被用於選取某個特定概念中的某個特定側面，作為下一步探索的對象。而另外一些啟發式，則實際用於尋找一些關於被選側面的合適的信息。還有一些啟發式促使AM注意已知概念之間的簡單關係，定義出有希望的新概念：考察並估計每一個概念的價值。
3. 日誌機制與最佳優先任務
在編製任何機器發現程序時，最重要的就是如何通過啟發式來控制程序的搜索任務，否則，程序很可能將大量的時間和空間用來執行意義不大的任務，甚至陷入搜索空間爆炸性增長的無窮任務中無法停止。
AM程序的運行是通過任務日誌（agenda）機制選取最佳優先任務來控制的。日誌機制是頂層、全局的控制結構，而啟發式是底層、局部的控制結構。所謂日誌，是系統所要執行的任務和為什麼這個任務是合乎情理的一個全局表。任務集有一個優先排序。一個單一的任務可能指導AM定義一個新的概念，探索一個已有概念的某些側面，去檢測一些經驗數據以總結出規律來，等等。程序重複地從日誌選擇最佳優先任務，將它從日誌中移出來，並嘗試找出相關的啟發式以實現任務。
所謂最佳優先任務，是日誌中按「興趣值」（interesting）排序最高值的任務。因為在日誌上會同時有4000個任務，AM必須花費很多時間決定首先應該做什麼。概念、概念的各個側面以及關於概念的行為都被數值化，以表明它們的價值。只要啟發式往日誌上加入一個任務，都會提出一些理由（例如：「如果關於該概念有一些有趣的猜想，那麼該概念就是有趣的。」「如果在許多次嘗試後，只找到了幾個實例，那麼該概念就是無趣的。」，等等），並用恰當的「興趣值」表示任務的行為、概念或側面為什麼是有趣的。AM然後用關於這些理由的數值進行加權總和來計算該項任務的興趣值。
4. 非定向性的合情空間移動啟發式搜索
大多數機器發現程序都是定向的，也即目標確定的。比如：費根鮑姆（E. Feigenbaum）等人開發的DENRAL程序是要根據有機化合物的分子式和質譜圖來判斷分子結構，而前面提到的BACON.1程序其設計目的就是要再發現開普勒行星運動第三定律。
與以上程序不同，AM的程序設計是非定向的，也就是說沒有給定的任務目標。在給定了115個集合論初始概念後，AM就按照自身的啟發式運行，既沒有規定它必須發現的概念、猜想，也沒有規定其探索領域。正因為如此，在運行一段時間之後，AM的探索領域自動地由集合論轉向初等數論，在該領域得到了許多概念和猜想。AM的領域轉換以及得出的數學發現都未必是程序設計者原本預期，甚至其中還有一個定理設計者過去不曾了解——最大分數定理。
正由於AM程序獨特的非定向性，使得它的啟發式搜索性質也很不一樣。在通常的典型啟發式搜索中，由於程序的任務目標是設定的，因而啟發式主要的作用就是限制搜索空間以排除「不合情任務」，而選擇執行「合情任務」，從而使程序逐漸逼近、最終實現給定的任務目標。在此種情形下，啟發式都被隱含地定義為一個「不合情移動限制器」。DENDRAL程序以及大部分遊戲對弈程序就都是如此。
然而，AM程序的搜索空間原本是無目標的，也就不存在「合情任務」和「不合情任務」之間的差別。因此，AM的啟發式自身隱含地定義了AM所有可以考慮的可能任務，而這些任務只要一經產生就是合情的。AM必須自己生成和找到任務，並自己負責管理自己的時間，以不把過多的時間浪費在無價值的行為上。在此情形下，AM的啟發式被定義為「合情移動生成器」。可以看出，在前一種啟發式搜索中，去掉一個啟發式將拓展搜索空間；而在AM中去掉一個啟發式將縮減搜索空間。
下面舉例說明AM是如何通過啟發式來拓展自身的合情搜索空間的。請看以下一條啟發式：
「如果是一個函數，其功能是將A的元素轉換為B的元素，而B是有序的（ordered），那麼，只考慮A中那些被轉換為B的邊緣元素，它構成了A的一個有趣的子集。」假如是「相交」，這條啟發式所說的邊緣元素就是指「不相交的集合」和「最大重合的兩個集合」。那麼，這條啟發式很可能會促使我們探索這兩種合情的邊緣元素，而定義得出「不相交」的概念，以及「相關子集」的概念。就這樣，AM從初始概念「相交」出發，在啟發式的引導下搜索，此次任務終止於兩個新概念的發現上。
再比如是「除」，這條啟發式所說的邊緣元素就是指沒有除數因子的數，只有一個除數因子的數，具有兩個除數因子和具有三個除數因子的數。那麼，這條啟發式很可能會促使我們逐一探索這幾種邊緣元素。在另一些啟發式的作用下，將0—1000的每一個數進行計算，放入適當的集合中。由於前兩個集合太小（都為1），消去這兩個集合，而第三個集合實際上就是「素數」集合。在此次任務中，M從初始概念「除」出發，在啟發式的引導下進行合情搜索，終止於「素數」概念的發現上。
5. AM的人機交互工作
AM程序的運行實際上是一個人機交互的過程。在人工智慧專家確定了初始概念和啟發式之後，AM就開始自動搜索最佳優先任務，而此時，程序的使用者一直通過列印輸出在對AM的探索進行觀察。無論在哪一個階段，使用者如果發現了自己感興趣的概念或猜想，他都可以即時打斷AM，通過賦予某一特定概念一個名稱的方式告訴它此概念是有趣的。這樣，AM就會提高該概念的興趣值，改變日誌上的任務排序，從而「能夠從一個方向或另一個方向轉變程序」。
目前，大部分機器發現程序自身都無法鑒別其輸出結果的真正價值，必須藉助人的介入，AM也正是如此。並且，正由於AM的探索是非定向的，這一點就顯得尤為突出。非定向的探索具有很大的未知性，事先根本無法在計算機程序中建立足以涵蓋其探索領域的知識庫，從而在原則上也就無法讓機器自己鑒別了。
正如利奈特本人所言：「AM發揮作用的最好實例只有通過人類開發才得以實現。」人機交互作用會使人和機器在發現的過程中彼此取長補短，讓人利用機器的計算和邏輯優勢，從而高效率地做出科學發現。
作為自動數學家的
AM——合情推理方法
1.是否存在數學發現方法？
利奈特將AM的程序設計思想描述為：「圍繞關於數學家實際上如何從事研究的一個特定模型而建造。」也就是要模擬數學家進行數學發現時所運用的方法，發明一位自動數學家（Automated Mathematician）以機械化地實現數學發現，這也是AM程序的名稱由來。那麼實際上，是否存在數學發現的機械化步驟方法呢？
著名數學家龐加萊（H.Poincaré）則將數學發現歸之於神秘的無意識過程的突然和偶然產生，他曾一再斷言：數學發現依賴於數學家非凡的數的直覺和想像。波普爾(K.Popper)也認為猜想的提出靠的是創造性的頭腦，比如愛因斯坦的神秘性直覺這種 「非理性因素」 。由此，他們把如何提出數學發現當作心理學研究的範疇。拉卡托斯（I.Lakatos）將「原始猜想——證明與反駁——改進了的猜想——……」這一批判性的持續漸進過程當作數學發現的邏輯，但他並未回答原始猜想從何而來，而是把它排除在數學發現的方法之外，從而根本否定了數學發現邏輯。以上看法都不認為存在數學發現的機械化步驟方法，因而都不鼓勵把數學發現呈現為自動的啟發式搜索。
然而，還有一些數學家和哲學家認為，雖然沒有十拿九穩的數學發現方法，但也有一定的規律可循。其中，著名數學家波利亞（G. Polya）尤為強調合情推理在數學發現中的作用：「我們借論證推理來肯定我們的數學知識，而借合情推理來為我們的猜想提供依據。」他的合情推理提供了自動啟發式搜索的可能性。
2.動機、合情推理與啟發式搜索
波利亞提出，合情推理主要包括「一般化」、「特殊化」、「類比」和「歸納」。他分別描述或定義了這幾種方法：「歸納」推理是合情推理的一種特殊情況，是科學家處理經驗的方法；「一般化」是從對象的一個給定集合進而考慮這個給定集合的更大集合；「特殊化」是從對象的一個給定集合，轉而考慮包含在這個集合內的較小的集合；「類比」是某種明確表述了的類型之間的相似性。「一般化」、「特殊化」和「類比」所提供的是發現的動機，它們在「歸納」中協調運用，從而發現新概念和新猜想。
可以看到，波利亞的合情推理恰恰被AM程序當作其重要的方法而運用。在AM的概念框架表示中，一般化、特殊化、類比被內在地規定為是概念的側面。以前面圖示的「集合」概念為例：側面3為「一般化」，其填充的是包容了「集合」概念的「無序結構」等概念；側面4為「特殊化」，其填充的是比「集合」概念小的「空集」、「非空集」等概念。
針對概念的「一般化」、「特殊化」、「類比」填充側面，AM有相應的啟發式，以引導和生成這些側面的理論拓展。現在，只從眾多的啟發式中擷取一二進行說明。「特殊化」：如果存在某一猜想為「所有X的元素也是Y的元素」，就創造一個新概念，此概念是X和Y的特殊化，定義為X與Y的合取；「類比」：當填充涉及概念C的猜想時，如果C與D類似，那就定義關於D的猜想。
通過諸如此類的啟發式搜索，AM獲得了進行發現的動機，會有意地注意能「一般化」、「特殊化」和「類比」的概念，從而實現其在合情空間的移動；之後，程序會根據另外一些啟發式計算每一側面的經驗數據，自動歸納出數學概念和猜想。
問題和爭論——
AM的發現、方法和創造性
關於AM有很多爭論，批評者嚴肅地置疑了AM的幾乎所有方面：AM的程序設計者是否忠實地描述了自己的程序？AM是否做出了數學發現？AM的方法是否有不合理之處？AM是否有創造性？
人工智慧專家瑞奇（Ritchie）和漢納（Hanna）兩人尤其批評了利奈特對自己工作的描述不夠精確，並懷疑他誇大了AM做出數學發現的能力。他們認為，利奈特在出版物中對AM的探討大多基於這樣的假設：用一個非常簡單、一致、基於概念的搜索過程，該程序已經「發現」了各種各樣的數學概念。正是由於他有意簡單化和迴避一些問題，使得非常難以評價AM的工作。他們指出，AM運行中最重要的中心事件是它「發現」了自然數。如果沒有這一突破性進展，進一步的素數、哥德巴赫猜想等更深刻的「發現」都無法得出。然而，利奈特並沒有用什麼篇幅來全面分析自然數是如何進入AM的考慮中的，只是輕鬆地讓使用者為之命名而對程序施加影響。我們看到，如果自然數概念的確應該不會被發現，這就會推翻AM的一切成功論斷。他們還斷言：在發現素數之前，AM用了一個很少使用的啟發式來潛在地幫助發展素數概念。利奈特本人曾對他們的此項批評做出了否定的回應，但依舊沒有正面說明這一問題；然而，由於計算機程序本身的龐大和複雜性，除了程序設計者之外很難有人能完全弄明白程序的細節，兩位人工智慧專家也未能徹底否證他。
吉利斯（D. Gillies）曾經對所有機器再發現程序提出質疑：模擬科學家進行再發現很難避免要發現的結論會預先暗含於程序設計之中。這一點對AM來說尤其是一個難題，AM所探索出來的「自然數」是如此基本、運用如此廣泛的一個概念，很難說沒有蘊含於程序設計所使用的LISP語言之中。
那麼，迄今在數學發現領域公認最有創造力的AM程序實際上具有創造性嗎？
博登（M. A. Boden）把創造性定義為，產生既新奇又有價值的觀點（ideas）。而新奇性的定義應該是既相對於個人過去所涉及的觀點，又相對於整個人類歷史。前者關係到的是P型創造性（P-creativity，P指的是心理學意義上的），後者關係到的是H型創造性（H-creativity，H指的是歷史上的）。H型創造性以P型創造性為前提，因為如果有人提出了歷史上新奇的觀點，它必然對所有個人來說都是新的。AM沒有發現任何數學史上的新理論，自然不具有H型創造性，但是它的確產生了許多有趣的P型創造性觀點——對利奈特本人來說是新奇的觀點，甚至有一個他過去一無所知（最大分數定理）。
然而，博登指出：第一，AM過於低效，最終得出的一大堆觀點其實都是無價值的；第二，正如前面所提到的，AM用了一個很少使用的啟發式來幫助發現素數；第三，AM的過程是人機交互的，有創造性也不是機器的創造性，而是使用者的；第四，程序設計使用的LISP語言的句法悄悄地包含了AM的P型創造性。由此，博登否認了AM具有創造性。
作者：張錦志（北京大學科學與社會研究中心）
來源：《中國數學會通訊》2016年第1期
TAG:中國數學會 |