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。

AI筆記40 - NLP

Text classification

naive bayes是最常見的text classification方法。

記得naive bayes有個naive前題假設，就是每個feature vector中的 element都是彼此獨立的，所以joint conditional probability = 個別的conditional probability的乘積：

有了上面這個前提，就能利用bayes theorem反推：

這些都是用data中的frequencies去model，這邊可以用m-estimate方法來修正feature出現次數過少的問題。

應用到text classification，首先data主體稱為corpus (document)，我們定義document中每一個字的位置為一個attribute，而其value就是那個位置所在的字。我們要舉出另一個假設就是任何word wk出現在corpus中的機率跟任何位置( x1, x2, .... ) 都獨立無關：

cj是training example的label分類的某個class j，上面的意思是 觀察到某個分類cj的前提下，wk在任何位置（x1, x2, .... ) 出現的機率都是相等。

這是一個合理的假設，當然可能對某些文件會例外。這樣我們就不用算出個別的p(x1=wk|cj）的機率，可能也很難算得出來。

一個好的text classifier m-estimate可以如下：

假設所有的label成cj的training examples 總共有nj個word positions，我們對此分母加上字彙的數量避免divided by zero，分子則是wk出現在分母範圍內的次數 + 1，避免某些p(wk|cj)為零。

Naive Bayes Text Classifier演算法

1. 首先演算法接受examples, 就是一些已經分類成set C 的documents，然後對這些examples找出重要的單元 (tokens)，然後組成一個pertinent vocabulary V。

2.計算兩個貝氏定理需要的機率:

(a) P(cj) :每個class出線的機率
(b) P(wk |cj): conditional probability of word wk given observing cj。

對所有的class cj in C:
(a) 把所有的class cj的documents都從examples找出來，稱為docsj
(b) model P(cj): 用被分類成class cj的documents的數目，除以總共的examples (all documents)數量

(c) 製作class cj的corpus: 也就是把所有docsj 組合成單一document，稱為textj
(d) 找出textj所有出現在vocabulary的word的positions（occurrences)，其數量為nj
(e) 對所有的word wk in vocabulary V:

• 找出wk出現在textj的次數
• 計算P(wk |cj): 記得用m-estimate:

training完畢， 接下來就可以做bayes classification:
(a) 假設input一個新的document Doc
(b) 找出所有不同位置的文字ai
(c) 找出這些文字屬於vocabulary V的位置 positions
(d) 找出Doc的class cDoc。之前講過利用逼近公式如下：

在text classification就是：

範例

假設我們有六個句子（看成6個documents)，已經分類成TV和radio兩大類：

這些documents裡面，我們假設pertinent vocabulary:

對TV class：
我們已經找出所有TV class的documents (sentences)，可以看成單一個corpus

P(TV class) =

這個corpus有9個vocabulary words occurrences，包括TV programs interesting TV Kids TV TV radio waves。
所以nTV = 9

再來分別計算出此corpus中所有vocabulary words出現的頻率，用m-estimate來model P(wk | TV):

同樣的步驟也apply在class Radio上，最後得出以下的結論：

這樣我們已經有了naive bayes的所有材料了，可以predict!

假設有一個新的sentence (document)如下：

我們先找出此document中出現的vocabulary words，只有radio和TV
根據naive bayes classifier，我們要算出:

以上兩個probability最大者，就是這個新的document所屬的class。

Probabilistic Language Model

用機率來model natural language，例如看到 "Did you call your ..." ，下一句比較有可能會是"mom"之類的，但很不可能是 "dinosaur"這種無厘頭的字眼，所以這邊會用probabilistic approach，當然也是在建築在大量的文字資料上面，可以寫成條件機率如下：

所以這類的機率模型就是在看到相連的n個字當作training樣本，如果在新的sample看到前面n-1個字的話，就能預測後面第n個字出現的機率。這類model稱為n-gram model。

根據bayes theorem, 我們需要這n個字依序出現的joint probability，所以問題是要怎麼從corpus中評估出這個機率?

還好這個在機率課中有學過，見此篇: https://fu-sheng-wang.blogspot.tw/2016/12/probability4-conditional-probability.html

所以這個joint probability 可以利用multiplication rule拆成幾個conditional probability的乘積:

另一個問題又來了，這些conditional probability要怎麼計算，而且數量可能相當多。
N-gram model利用可以只利用n = 2 (稱為bigram) 來逼近 n-gram:

AI筆記39 - Unsupervised Learning

K-means clustering

直接上演算法，BJ4:

K-means的最大問題在於:
1. 我們得事先知道k = ? 某些paper提供找出k的值。
2. 沒有理論基礎，無法分析目前結果好壞? 簡單常見可以用inner cluster distance vs intra cluster distance來衡量，前者必須小，後者必須大。
3. curse of dimensionality:高維度feature之間的distance變得沒太大意義，也不知其真正的涵義為何。
4. Non-circular shapes? 採用其他的cluster方法囉。

Association Rules

這個算是data mining?
在一個大的dataset中，歸納出一些常出現的patterns，根據這些patterns再引申出關聯性的rules(例如 A -> B 如果 (A,B) 被發現為pair出現的pattern)。這在推薦者系統很常利用這種技巧。

AI筆記38 - Neural Networks

Perceptron複習一下

perceptron是最簡單的NN，每個sample i的每個feature被weighted and summed，最後經過step function來classify，至於weights要怎麼獲得才是重點。

training過程就是iteratively調整weighted sum function形成的hyperplane，直到找到一個最小錯誤者。不過perceptron只能對linear separable data做分類，他只能產出linear separator。

Enhance Perceptron: using a Sigmoid function

perceptron只能對linear separable data運作，要升級的話(可以找出nonlinear separator的話)，嘗試把step function換掉。因為step function不可微分，所以不能用gradient descent的方法去找。如果把perceptron的step function換成sigmoid function:

所以我們的升級版perceptron: (sigmoid function在perceptron又稱為activation function)

Multilayer Perceptrons

sigmoid function在z -> 10 和 z -> -10 的時候就已經趨近1 或 0:

所以我們可以用這個數學特性，來看我們的perceptron怎麼做兩個feature的logical OR:

首先可以看到我們要產生相對應的truth table，藉由上述的sigmoid的趨近1和0的特性，只要能兜出上面這個truth table就完成了x1和x2 feature的logical OR:

所以我們可以w0 = -10, w1 = 20, w2 = 20，這是一組解。所以g(z) =

利用上述的觀念，也可以做出NAND, AND:

再來就是要真正做multilayer perceptron，因為XOR必須要靠上面這三個elementary perceptron來形成更複雜的功能，用truth table可以確認XOR 等同於 最右邊這欄compound propositions:

這形成一個MLP:

組合成一個output layer，公式就是把上一個layer的output丟進來:

Backpropagation Algorithm

這種multilayer的NN要怎麼把每一layer中的weights找出最佳解來? 有一種方法叫做backward propagation of errors，利用gradient descent來minimize squared prediction error。

注意我們這邊討論的NN結構都是沒有loop的，也就是上一層的layer不會接受下一層的layer當作input，這樣的單向input結構稱為 feedfoward NN。

所以名詞不要搞混了，餵食input單向，所以稱為feedfoward。在output layer得到了某個prediction，當然不可能100%正確，跟training sample的ground truth y比較過後，把錯誤的量逆向propagate回去，讓每個layer都能修正其錯誤(learn weights)，稱為backpropagation of errors:

注意output layer的neuron可能有多個! 例如做k-classification。

所以error可以計算如下
中文是input sample e 且有 weights w 的 NN，造成的total error E = 1/2 * (所有k個output neurons的output Ok與true label yk的平方差)，1/2是為了之後計算好算:

這邊搞不懂的是為什麼會有Yk? 不是只有一個y? 我應該沒搞清楚某些東西。

好吧 anyway @@...
有了這個total error的定義，接下來要做gradient descent來minimize error:

wij是兩個前後相連的layer i  和 layer j 之間的weight，delta wij意即我們要descent的量，等於是一個learning rate alpha 乘上 某個偏微分，這邊因為不太懂，先不做解釋，之後有遇到再說吧。

總之就是以下這個圖說明了multilayer perceptron的運作方式: