科技

【CS188課程筆記翻譯(1)】

譯者注:本文譯自伯克利CS188人工智慧導論課程第一章筆記,譯者已獲得課程教師Pieter Abbeel許可進行翻譯和釋出。本文由Yizong Xing翻譯完成,Ruoyi Chou對本文的語言措辭等進行了嚴謹的校對,提出許多寶貴的修改建議。

原文如下

在人工智慧中,目前的主要問題是建立一個理性(rational) agent,一個有特定目標或偏好並會針對這些目標試圖執行一系列操作(actions)來得到最優解的實體。理性agent存在於為給定的agent示例而量身定製的特定環境中。舉一個簡單的例子,一個西洋棋agent的環境就是它用來與對手對弈的虛擬棋盤,而對應的操作就是棋子的移動。一個環境和其中的agents一起創造了一個世界。

反射(reflex)agent不會考慮它的操作的後果,而只是根據世界的當前狀態而選擇一個操作。而計劃(planning)agent則有一個世界模型並用這個模型來模擬執行不同的操作,遠遠勝過了反射agent。於是,agent就能確定操作的假想結果並選擇最佳操作。這樣的模擬“智慧”在這個意義上符合人類在任何情況下嘗試決定最佳動作的行為——預測。

為了建立一個理性計劃agent,我們需要一種方法來對agent存在的環境進行數學表達。為此,我們必須正式表達一個搜尋問題(search problem)——給定agent的當前狀態(state)(它在環境中的配置),我們如何儘可能最好地達到一個滿足目標的新狀態?講一個問題公式化需要四個前提:

要解決一個搜尋問題,首先要考慮它的起始狀態,然後用後繼函式探索它的狀態空間,反覆計算不同狀態的後繼直到得到一個目標狀態,這時我們就能確定一條連線起始狀態和目標狀態的路徑(一般稱為計劃路徑(plan))。由一個既定的策略(strategy)來決定我們考慮不同狀態的順序。很快我們將介紹策略的種類及其效能。

在我們繼續討論如何解決搜尋問題之前,有必要強調一下世界狀態(world state)和搜尋狀態(search state)的區別。世界狀態包含一個給定狀態的所有資訊,而搜尋狀態僅包含對計劃(主要是為了空間效率)必要的資訊。我們將介紹本課程的一大亮點——吃豆人Pacman來解釋這些概念。這個遊戲很簡單:吃豆人必須探索一個迷宮,吃掉所有的的小豆子並且不被遊蕩的惡靈吃掉。如果它吃了大豆子,它將在一段時間內無敵並且能吃掉惡靈賺取分

路徑規劃的狀態包含的資訊比光碟行動要少,因為在光碟行動中我們必須儲存一大批布林值用來表示在給定狀態中每個豆子有沒有被吃掉。一個世界狀態還有可能包含更多的資訊,比如吃豆人走過的總距離,或者吃豆人在它的當前位置(x,y)和豆子布林值上到達過的所有地方這些潛在的編碼資訊。

我們定義變數和它們分別的取值種數如下:

現在我們已經構建了狀態空間的概念並用了四個部件來完整地定義了一個狀態空間,我們馬上就可以開始著手解決搜尋問題了。現在我們缺少的最後一塊拼圖就是狀態空間圖和搜尋樹。

與狀態空間圖不同,我們要講的下一個結構,搜尋樹(search trees)對於一個狀態出現的次數沒有限制。這是因為雖然搜尋樹也是一類用結點表示狀態、用邊表示狀態之間操作的圖,每個結點/狀態並不僅僅代表它本身,同時也代表了狀態空間圖中連通起始狀態和給定狀態的整個路徑(或計劃)。觀察下面的狀態空間圖和與其對應的搜尋樹:

狀態空間圖中標紅的路徑(S → d → e → r → f → G)在對應的搜尋樹中表示為從起始狀態S到標紅狀態G的路徑。同理,狀態空間圖中從起始節點到其他任意節點的每條路徑在搜尋樹中都表示為從根節點S到另一節點對應的子孫節點的路徑。由於從一個狀態到另一個狀態通常會有多種方案,搜尋樹中狀態會出現多次。由此,搜尋樹的規模大於等於對應的狀態空間圖。

我們已經確定了即使是簡單問題的狀態空間圖也有相當大的規模,於是問題來了——如果這些結構大到無法再記憶體中表示,我們如何對它們進行有效計算呢?答案就在後繼函式中——我們只儲存即刻處理的狀態,並用相應的後繼函式根據需求來計算新的狀態。通常,搜尋問題是用搜索樹來解決的。在樹中,我們每次觀察那幾個非常小心地儲存選擇的節點,反覆地用其後繼來替換節點,直到我們到達一個目標狀態。有許多種方法可以用來決定在搜尋樹中迭代替換節點的順序,現在我們將介紹這些方法。

尋找從起始狀態到目標狀態的計劃的標準協議(standard protocol)是保持來自於搜尋樹的部分計劃的邊緣(outer fringe)。通過移除一個與部分計劃對應的節點(用給定的策略來選擇)並用它所有的子節點代替它,我們不斷地擴充套件(expand)我們的邊緣。用子節點代替邊緣上的元素,相當於丟棄一個長度為n的計劃並考慮所有源於它的長度為(n+1)的計劃。我們繼續這一操作,直到最終將目標從邊緣移除為止。此時我們得出結論,與移除的目標狀態相對應的部分計劃其實就是從起始狀態到目標狀態的一條路徑。實際上,這類演算法的大多數實現都對父節點、到節點的距離和節點內部的資訊進行編碼。我們剛剛介紹的這一過程就是樹搜尋(tree search),它的虛擬碼如下:

當我們不知道目標狀態在搜尋樹中的的位置時,我們只能從屬於未知搜尋(uninformed search)的技術中選擇用於樹搜尋的策略。我們將依次介紹三種策略:深度優先搜尋DFS、廣度優先搜尋BFS和一致代價搜尋UCS。同時,我們還會介紹它們的一些基本性質,內容如下:

作為對一致代價搜尋的最後說明,必須注意上面列出的三種策略本質上是相同的——只是在擴充套件策略上有所區別,上面給出的樹搜尋虛擬碼捕捉到了它們的相似之處。

一致代價搜尋很棒,因為它兼顧了完備性和最優性。但它也可能會相當的慢,因為它在搜尋一個目標時向所有方向擴充套件。如果我們對於我們應該搜尋的方向有一定的瞭解,我們就能顯著提高效能並更快地達到目標。這就是有資訊搜尋。

上圖表示了曼哈頓距離幫助解決的鬆弛問題——假設吃豆人想到達迷宮的左下角,它在計算了假設沒有牆的情況下從吃豆人現在的位置到目標位置的距離。這個距離是鬆弛搜尋問題中的精確(exact)距離,而相應的在實際的搜尋問題中的是估計(estimated)目標距離。有了啟發式搜尋,在我們的agent中實現邏輯變得很簡單,這使它們在決定執行哪個操作時能“偏好”在估計中離目標狀態比較近的擴充套件狀態。這個偏好的概念非常有用,並且在以下兩種搜尋演算法中都有利用到它:貪婪搜尋和A*搜尋。

現在我們已經討論了啟發式搜尋以及它在貪婪和A*搜尋中應用的,接下來我們來花些時間討論一下一個好的啟發式是由什麼構成的。為此,我們首先重新定義UCS、貪婪搜尋和A*中用於確定優先順序佇列順序的方法,定義如下:

於是,這樣的一個啟發式將A*退化為了BFS,所有代價都相等了。我們之前已經說明了,BFS在邊的權重不恆定的通常情況下不能保證是最優的。

定理. 對於一個給定的搜尋問題,如果一個啟發式函式h滿足可納性約束,使用含有h的A*樹搜尋能得到最優解。

證明. 假設兩個可以到達的目標狀態,最優目標A和次優目標B在一個給定的搜尋問題的搜尋樹中。因為可以從初始狀態到達A,A的某個祖先節點n(有可能是A本身)現在一定在邊緣上。用以下三個陳述,我們可以斷定n會在B之前被選來擴充套件:

由此,我們知道n在B之前被擴充套件。因為我們已經證明了對任意n均有這個結論,我們能得出結論:A所有的祖先(包括A自己)都在B之前擴充套件。

我們在上面發現樹搜尋有一個問題,那就是有些情況下它可能會找不到解,在狀態空間圖中陷入同一個環中無限地搜尋下去。即使是在我們的搜尋技術不涉及這樣一個無限迴圈的情況下,因為有多個路徑能到達同一個點,我們經常會多次訪問同一個節點。這導致工作量指數上升,而自然地解決方案只是簡單地跟蹤哪些狀態已經擴充套件過,並且永遠不再擴充套件它們。更明確地講,在使用你選擇的方法的同時維持一個“封閉”的擴充套件節點集。然後,確保每一個節點在擴充套件前不在這個集合中,並且在擴充套件後將其加入集合裡。經過這種優化的樹搜尋稱為圖搜尋(graph search),其虛擬碼如下:

注意在實現時,很重要的一點是將封閉集儲存為一個不相交集合而不是一個佇列。將它儲存為佇列需要花費O(n)個操作來檢查資格(membership),這會抵消圖搜尋本來的優勢。關於圖搜尋,另一個需要注意的是即使是在可納的啟發式下,它也會破壞A*的最優性。思考一下下面這個簡單的狀態空間圖和相應的搜尋樹,啟發值和權重都已標出:

在上面這個例子中,最佳路徑顯然是S→A→C→G,得到總路徑代價為1+1+3=5.僅有的另一條到達目標的路徑,S→B→C→G的代價為1+2+3=6.然而,因為節點A的啟發值比B大得多,節點C首先作為節點B的孩子沿著次優路徑擴充套件。然後它才被放入“封閉”集,所以A*在把它當做A的孩子訪問它時無法重新擴充套件它,導致它永遠無法找到最優解。於是,為了維持A*搜尋下的完備性和最優性,我們需要一個比可納性更強的性質,一致性(consistency)。一致性的核心思想在於,我們不僅僅強制讓啟發式演算法低估從任意給定節點到目標的總距離,還低估了圖中每一條邊的代價/權重。由啟發式函式度量的邊的代價只是兩個連線的節點的啟發值的差異。一致性約束的數學表示如下:

定理. 對於一個給定的搜尋問題,如果啟發式函式h滿足一致性約束,對這個搜尋問題使用有h的A*圖搜尋能得到一個最優解。

證明.為了證明上述理論,我們先證明在使用一個有恆定啟發式的A*圖搜尋時,無論何時我們移除一個節點來進行擴充套件,我們都已經找到了通往那個節點的最佳路徑。

使用一致性約束,我們能展示根據任何計劃節點的f(n)值都不會下降。定義兩個節點n和n’,n’是n的後繼。那麼:

這與我們之前證明在可納性約束下的A*樹搜尋具有最優性是一個道理。於是,我們能得到結論:在一致性啟發式下A*圖搜尋具有最優性。

下面這個由三個節點構成的網路是一個可納但不一致的啟發式例子:

現在我們已經建立了可納性和一致性的性質以及它們在保持A*搜尋的最優性中扮演的角色,我們能夠回到我們最初的問題,建立“好”的啟發式以及如何比較啟發式之間的優劣。衡量這個的標準就是優勢(dominance)。如果啟發式a相對於啟發式b而言有優勢,那麼對狀態空間圖中的所有節點,a的估計目標距離都比b要好。數學表示為

在本章筆記中,我們討論了搜尋問題,我們將其分為了四個部分:狀態空間、後繼函式、起始狀態和目標狀態。有多種走索技術可以用於解決搜尋問題,包括但不限於我們在CS188中學習的5種:

前三種搜尋技術都屬於無資訊搜尋(uninformed search),而後兩種都是通過啟發式(heuristics)來估計目標距離並完善效能的有資訊搜尋(informed search)。

note 1 筆記完。

Reference:科技日報

看更多!請加入我們的粉絲團

轉載請附文章網址

不可錯過的話題