A1筆記 42 - Planning Graphs for PDDL

Relaxing Problems

一個problem可以被所謂“relaxed"，意指把忽略某些problem定義的條件，變成一個更好解決的問題，而且在relaxation的過程中，可以自動產生admissible domain-independent heuristics來幫助解題。

Heuristics for planning

PDDL是使用factored representation來表現state，所以某一些factor fluents的組合可以拿掉(所謂拿掉就是某個state的ground fluent用variable取代）變成一個relaxed representation，意即problem也被relaxed了。這樣我們能夠程式化做relaxation，而相對應的heuristics會從中長出，這樣能夠達成 domain-independent heuristics。

如果search過程是一個graph，這相當於把一些相同屬性的node group起來變成一個更大的abstract node，形成一個更abstract graph。所以graph變簡單了，因為抵達goal state的path可能大大縮短（對abstract graph而言）。

另一個可能縮短抵達goal state的方式就是在search graph中加入edge，直接跳過某些nodes，這在PDDL裡面可以由忽略action的precondition來達到，因為這意味著所有的action都對所有的states applicable，這事實上產生了所謂“ignore precondition heuristics”，這是最relaxing problem的方法之一，一但任何action都能apply在任何state，則從initial state抵達某個goal state的過程，相當於只要考慮action effects是否能滿足此goal state包含的fluents。(這變成一個set cover problem，其實是NP-hard，但是有不一定保證admissible的greedy algorithm可以linear time approximate）。

如果只忽略action precondition的subset，也能達到relaxing problem的效果，在PDDL裡面，action schema已經清楚列出action preconditions，所以這個relaxation能夠程式化，不需要人腦介入。

Planning Graphs

簡單來說planning graph就是一個admissible planning heuristics，用來估計從initial state抵達某個state G所需要的步數 ，不過planning graph不能回答從initial state出發是否一定能抵達G，但是它可以確認“無法從initial state抵達G"的情況，因為一但graph建立完成，如果goal state沒有出現在graph中，表示這個problem是無解的。

舉一例來說：

planning graph是一個directed graph，有以下state->action交錯的level 結構：

基本上就是state level -> action level -> state level -> action level ... ，action壹定要applicate to it parent state，然後child state就是action result，一直循環下去直到actions再也產生不了新的states（上圖中的S2和S1一樣），此時我們稱graph leveled-off。

當然某個state也可以選擇不作動(no-op)，稱為persistent action，這樣state就會原封不動複製再下一個state。

上圖中某些level會有灰線連接不同的actions或fluents，這表示“disjoint"，不能同時發生的，或說"mutually exclusive" or "mutex"。

簡單來說，每個level Si包含了所有Action Ai-1能夠造成的fluents / terms / literals，而且也包含了哪些fluents互斥的關係。同樣的，每個level Ai也包含了所有可以對state Si-1 作動的actions (包括no-op)，以及記錄所有互斥的actions。

Mutex relation

對mutex actions來說，定義如下：

對mutex literals來說，除了是彼此的negation之外，另一個可能就是mutex actions造成的literals勢必也是mutex literals，因為不可能同時發生此兩個actions。

planning graph的size growth = polynomial。

Level sum heuristics using planning graphs

level cost: 從initial state s出發，抵達某個literal gi第一次出現的state，經過的level count 就稱為level cost，其實就是graph中的state level index（記住applicable action level index與其parent state level index相同）。

level sum heuristics: 為了使用heuristics來簡化問題，我們使用"subgoal independence assumption"這個假設為前提，其意義是一個問題可以分解成獨立的許多小問題分別獨立解決，而total cost = sum(這些所有小問題的cost)。在這個前提下，我們可以用sum of level costs來逼近真正問題的解決cost，因為每次一但發現了某個goal literal，相當於解決了一個subgoal，而且也知道其cost。最終goal literals = 聯集(這些分別的goal literals)，cost = sum of level costs。

我們的例子中，goal literals包括：

根據建立的planning graph，Have(Cake) 的level cost = 0，而 Eaten(Cake)的level cost = 1，所以此goal的level sum = 0 + 1 = 1。不過如果對照planning graph，正確的cost實際上是兩個actions才能抵達：

不過本來這個heurisitics只能說是admissible，本來就不是true cost。

A1筆記 41 - Planning Domain Definition Language (PDDL)

Classical Planning

之前提過search agents，這當然也是planning的一種，不過這依賴domain knowledge，因為state是完全atomic的，也就是state不能參數化，一個獨特的representation只能表現一個state。

logical agents不需要domain specific knowledge也能plan，但是依賴ground truth(knowledge base)的inference，ground truth可能多到無法計數。

這邊要提的是可以參數化表現的state，利用所謂的PDDL語言（Planning Domain Definition Language)。

PDDL States

這邊先介紹一個名詞 fluent，意指某個為真的boolean value，用來描述某個state的variable。
所以一個state其實就是一堆fluents的交集(這種表示方法稱為factored representation，相對於不能拆成變數組合的atomic representation，例如用64個int組成的array來表現8-queens state)，例如某個包裹運送的state可能是以下兩個fluents的聯集：

fluents必須是atoms (terms)，不能是變數組成。

PDDL Actions

Actions類似以下的action schema:

一個所謂的ground action，意即不能有任何變數，所以一個ground action中的所有變數必須被atoms替換掉：

precondition可以看成是某個state s的truth subset，用邏輯術語來說就是s entails precondition of a:

當precondition對s來說成立的時候，我們說action a is applicable。

PDDL Result Function

action的effect相當於對state s的一個正負子集合，把相對於s中的負的fluents去掉，加上正的fluents。

PDDL Initial State和Goal Test

initial state必須要是atoms，也就是要明確，不能參雜變數去形容。但是goal倒是可以參雜變數，主要是可能多個atom替代的變數都滿足我們的goal需求，例如飛去SFO或是飛去LAX都是goal可以接受的atoms。Goal就是一個precondition，所以是一堆正或負literals的交集。

goal test:
所謂的找到goal，意思是發現一系列的actions，使得抵達某個state s entails goal。記住goal 也就一堆literals的交集，所以當所有goal中的literals都出現在s中，且都為真，那代表此state s也符合goal這個precondition了。

假設goal為：

對某個state s進行goal test:

會發現s entails goal，則此s為goal state (蠻幽默的，僅管rich and famous，達到目標了但是.....miserable)。


另外state:

entails goal:

Cargo Example

下圖是一個cargo planning problem:

Forware Search algorithm (progression) 

從initial state出發，探討所有actions造成的new states，然後再繼續重複此動作，所以ground actions (把所有參數填入所有實際可填的組合）可能會多到爆，意即branching factors太大了。

所以forward search通常需要domain heurisitics來縮減search space。

Backward search (regression)

從goal往回找，所以只會沿著能抵達goal的路徑（relevant states)前溯。不過這必須要有辦法知道如何前溯。PDDL state和action因為有特別寫入preconditions和effects，所以讓regression變得可能：

對前一個可能的relevant state g'來說，g'可能原本就有a的positive effects Add(a) 也可能沒有，但是g拿掉Add(a)得出的state保證是一個最低限度未受到action a影響的relevant state。

此外action a要能被g' apply的前提是 g' entails a的precondition，所以g'最低限度要包含所有Precond(a)中的fluents。

那為何不用把action a帶來的false fluents Neg(a)加回去g'呢？因為g'可能有也可能沒有Neg(a)中的fluents，如果g'沒有的話，把Neg(a)放回去有可能會造成g' 不entails Precond(a)。

舉例來說，假設goal state要包含此fluent:

則從這個fluent去找會造成包含這個fluent 的result的action，其中（沒有之一）就是：

plane p'是變數，因為任意plane組成的unload ground action都可以抵達goal state。

藉由regression，我們可以找一個合法的g':

如果要再regress到前一個g''，我們不用急著去把各個atomic plane帶入p' ，這會讓search branching factor增大，可以繼續讓p'保持變數，這樣branching factor完全不改變。這就是PDDL的好處。不過使用變數反而難以找出好的heuristics（是效能的關鍵），所以目前主流系統還是使用forward search。

了解gradient descent背後的數學

了解gradient descent背後的數學

machine learning中常用到的gradient descent是多變數微分的應用，這篇筆記算是把背後的數學意義記錄下來。前面幾段是基礎知識，如果已經懂了，可以直接跳到後面directional derivative去看。

R^3是一個set，包含R^3的定義

R^3是一個set，包含所有不同順序的ordered 3-tuple的點：

cross product (vector product) of 2 vectors

定義如下：

這是在找出同時垂直於兩個vectors形成的平面的向量，所以還是另一個向量！

determinant （這只是一個運算元）

order 2定義：

order 3定義：

general定義就是 ai * （去掉自己row和col的所有數字的縮小版determinant)

我們可以把3-d vector cross product用determinant重寫：

或者寫成同一個determinant，但此時ai變成vectors，所以算出來的determinants也是vectors:

2-variable function

z=f(x,y)，畫圖在R^3可能長這樣：

如果x和y都是一次的，也沒有相乘，則是一個linear function，在R^3中會是一個平面：

例如： f(x,y) = 6 - 3x - 2y

例如: z = 4x^2 + y^2。橫切面是橢圓形 (ellipses)，縱切面是拋物線(parabolas)。

另外幾個例子

等高線圖 (level curve / contour)

這個其實就是z的多個橫切面投影在xy平面上的圖，常見的有等高線圖之類的。

Derivative

先說定義：

如果以single variable function來說的話，f'(a) 是f(x)在x=a的地方的切線的斜率：

物理上的意義是“改變的速率” (rate of change)。
假設某y = f(x)，所以當x改變的量為delta x = x2 - x1，y改變的量即為 f(x2) - f(x1)，所以改變的幅度：

這稱為y對x的平均改變速度 (average rate of change of y with respect to x)。這是一個平均的概念。

如果delta x趨近於零，也就是當x改變了能夠想像的最小程度，則上式就是“瞬間” instantaneous rate of change with respect to x1

也就是所謂的 derivative f'(x1)

看圖可以理解這就是在x1的切線斜率：

距離公式s(t)，瞬間速度是s'(t) ＝ 距離這個變量的“rate of change" ，對時間這個變量來說。（白話文：時間t的改變造成距離s改變的程度）。

derivatives of two-variable function

假設有一個function z = f(x,y)在R^3中是一個曲面s:

如果我們固定y = b，則相當於形成一個function z = f(x,b)，這就是上圖中S的縱切面形成的曲線C1。同理如果固定x = a，會形成曲線方程式 z = f(a, y) = C2

這兩條曲線各自有自己的在P點的切線T1和T2，其斜率為z在P點的導數。
對C1來說，在P點的切線T1的斜率意味著 x=a且y=b的時候，x的改變造成z的改變的rate of change。

同理對C2來說，則是x = a且y = b的時候，y的改變造成z的改變的rate of change。

我們定義partial derivatives functions為：

有很多種表達法 @@

所以T1, T2的斜率就是fx(a,b) 和 fy(a,b)。

general case: directional derivative

解讀partial derivatives的意義：

這是一個等溫線圖，溫度I = f(lat,lon)。所以f_lat ＠ Reno的意思就是從Reno出發的話，溫度相對於緯度（距離）的變化速度（rate of change)，f_long也是類似的意思。

但是看等溫線圖可以發現溫度呈現越東南越高的狀況，也就是任一方向的溫度相對於距離的rate of change有可能是正負值。

假設此f在3d空間中形成一個surface S:

如果我們任意選擇一個方向（向量u)，對S立下一個垂直切面，則此切面會與S交會在curve C。此C上的u方向上的交點P(x0,y0,z0)，其切線為T。要怎麼找到此T的切線斜率？

另取C上另一點Q使得PQ組成一向量，則此向量PQ在xy平面的投影向量為h*u，則PQ的斜率可以用：

對PQ斜率取極限值就是T的切線斜率，這就是derivative的定義，但是在這邊是f在u方向上的derivative:

所以f_x和f_y其實只是某兩個特例的directional derivative，剛好在standard basis vector i和j的方向而已。

上圖其實也暗示了directional derivative其實可以拆成i和j方向的兩個分量，意思是所有的directional derivative都可以用f_x和f_y表示：

Gradient vector function

theorem 3可以寫成dot product形式：

u前面這個vector function，有一個特殊名稱，叫做"gradient" of f：

所以gradient是所有standard basis vector方向上的partial derivative合成的vector function。

所以反過來看，也可以說directional vector是gradient在u方向上的投影：

延伸到多變數：

舉例來說：

按照directional derivative和gradient的關係，可以先找出f的gradient vector function:

再來算出f在(2,-1)時的gradient vector:

再來就可以算出directional derivative，這就是gradient在u方向上的投影，但是題目中的v不是unit vector，所以還要將之轉換成unit vector，算出來的答案才會正確：

如何找出最大的directional derivative?

在machine learning中常常用到的optimization方法之一就是gradient descent，為了要快速收斂找到model f的minimum cost，我們需要在f形成的surface S上，從某一個初始點找到切線斜率（directional derivative, rate of change of f respect to 某個feature)最大（最陡）的方向去下降（descent)，所以如何找出最大的directional derivative是我們好奇的。

這很簡單可以找出來：所有方向中的derivative只有與gradient的方向一致 (夾角為零）時，rate of change最大：

舉例來說，假設有一個function f:

f在(2,0)的gradient:

此f在PQ方向上的directional derivative:

但是根據理論，directional derivative在gradient的方向上最大：

這邊用length of gradient vector，相當於gradient dot <1,2> unit vector ＝ 1* (1/根號(5)) + 2*/(2/根號(5)) = 5/根號(5) = 根號(5)

此範例在3d空間長這樣：（藍色向量就是gradient在xy平面的投影）

比較有趣的事（但是符合預期），gradient vector的方向與level curve垂直，這很合理，垂直（跳）下山比繞山路(同高度緩降）螺旋向下快多了，這就是所謂的gradient descent，或稱為steepest descent:

在不同的點都可以看到與level curve垂直，下圖是某function 的gradient vector field的圖：

有了以上的理解，就可以知道machine learning中的gradient descent是怎麼來的了。