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的運作方式:

AI筆記37 - Ensemble methods

最近十年的ML方法: ensemble

ensemble methods 把多個independent weak classifiers的預測結果透過"majority voting"節合在一起。所謂的weak classifier就是預測結果至少比random好一些，但也僅只於此。

一組training data怎麼產生多個independent weak classifiers? 以下3個strategies可以利用:

Boosting

假設某個training data set可以每次透過modification產生一組新的samples，用不論何種方法來train某個classifier Gm(x):

最後把這些classifiers依據performance來給予相對應的weight，然後計算weight sum (就是所謂的民主投票，majority voting....):

alpha值就是看boost algorithm怎麼找出來了，sign的意思是可能label是 {+1, -1}的時候。

關鍵點怎麼modify training samples? 根據每一次找出的Gm(x)，我們都可以先找出預測錯誤的samples，例如以下黑圈是G1(x)找出錯誤的:

所以要modify這些error samples，給他們某種更大的weight  wi(怎麼計算?)，用來train G2(x)，這會讓G2在focus在predict這些samples時更多著墨 (how?)。

原本的prediction error rate是數人頭算平均:

但是weighted (modified)sample的prediction error rate要把算weighted average:

之前說的alpha就根據errm來算出:

Adaboost 演算法

如下:

舉例來說明會比較簡單。假設有某個簡單的binary classifier:

xi 是j-dimensional feature vector，而classifier是利用某個threshold t來判斷vector i中的某個jth element 是否該判斷成1 or -1 class，基本上是一個很簡單的classifier(本來要打很低能，這個classifier稱為stump)。

現在如果d = 10，有2000個training samples +10000個testing samples，來比較一下adaboost是否有所改善?

下圖是random classifier, stmup classifier boosted, 以及244-node decision tree的error rate比較，random classifier error rate可以預見會是0.5，而完整的244-node decision tree error rate還有0.24，可是stump classifier經過400個iterations之後可以把error rate降低到0.05以下!

三個臭皮匠 勝過豬哥亮?!

事實上adaboost是一種選擇最優feature的實驗過程，選出較好的feature時，就給大的weight，這在最後combined classification會有明顯的貢獻。例如以下是某個email spam classifier的每個feature以及其adaboost alpha weights:

Bootstrapping & Bagging

又是惱人的名詞解釋。

bootstrapping是一種sampling方式，而boosting就是靠bootstrapping來從training data中resample並且modify成新的training sample給下一個training iteration使用。

這邊所謂的modify strategy就是randomly distort data by resampling


Bagging是個複合字 = Bootstrap Aggregation。簡單說很類似boosting:

詳情還是請洽ML course!!!!!!!!!!!!!!!!!!!!!

AI筆記36 - Forward/Backward Chaining , First Order Logic

另一個inference 達到completeness的方法

resolution演算法雖然證明sound and complete，但是其實是exponential running time，跟model checking也是一樣的，因為這涉及了所有KB senetences的pairwaise resolution。

另一個較為簡單的linear time方法稱為forward chaining 以及 backward chaining，這是利用modus ponens運作在horn clauses的方法。記得horn clause是以下形式：

如果線上面的clause都為真，則q可以被implied為真：

Forward Chaining

假設KB中都是literal和horn clauses，例如以下：

想要證明KB entails Q?
我們可以把KB用以下的圖表示：

每個節點代表一個implication，這邊都是兩個facts conjunction implies another fact。所以節點可以標上是有幾個facts在premise中　（implication的箭號左邊部分）:

forward chaining就是從任何一個非目標節點，開始刪除節點上的數字，例如A && B implies L，但是KB中有fact A，所以實際上A &&B節點數字2 可以刪減成1，意即B 單獨就可以implies L：

同時跟A有關的節點也都可以減1。

接下來跟B有關的節點也可以減1，因為KB中有B :

Ｌ現在不需要A &&B去imply也成立了，所以跟L有關的節點也可以繼續減去 1 propagate下去：

最終P也變成fact，所以Q當然也是fact，這整個過程就是horn clause implication的拆除：

Backward Chaining

這是先從Q出發，檢視imply Q的horn clause，然後再一一推回去相關的clause，直到抵達facts A和B (也就是沒有horn clause anymore)，這時再forward check是否能真的推回到Q。

等於graph先從Q往下找factds，找到後再往上檢查到Q。

由於課堂中只是簡單帶過，就不多說了。

backward chaining比forward chaining花費的時間可能比forward chaining來的少，因為他是goal-driven，不是像forward chaining一樣亂槍打鳥。

First-order Logic (first-order意指relation是指object之間，而不是更高層次的relation之間）

比較接近真實語言，多了壹些propositional logic沒有的元素：
1. constants: 用來比對的atoms或是symbols
2. variables: 可以bind meaning的entity
3. functions： 用來描述幾個entity之間的關係
4. 一些符號：數學上都常見，例如所有的 存在一個 之類的

舉例來說：
如果Fly(x) 的意思是 x會飛
bird(x)的意思是 x是鳥
則以下句子代表：所有鳥都會飛

還有幾個例子，都很好理解：

AI筆記35 - Resolution & CNF

Proof by resolution

再來舉Wumpus world來說明怎麼做Proof by resolution.
首先我們有以下的KB:

player一開始在1,1，後來跑到2,1，再來跑到1,2，觀察到以上的KB中的sentences。
在infer過程中，會出現一個特殊的form:

可以看到 P11 OR P22 OR P31   AND  -P22

這是一個conjunction (AND) 連結兩個 OR形成的clause （右邊-P22 也可以看成 -P22 OR True)
但是-P22和　P22互斥，由於-P22為True，則P22只能為False。

這邊　-P22 和 P22 這兩個element "resolved" ，做了一個resolution，形成了一個新的true的sentence: P11 OR P31，稱為一個"resolvent"。

當然最後可以得出KB entails P31，因為player在1,1出發，而那邊沒有pit：

以上resolution過程稱為 "unit resolution"，general form如下：

Conjunctive Normal Form (CNF)

unit resolution可以延伸到更general的兩個clause:

以上兩個clauses都同時為真，這種由兩個disunction clauses組成的AND 關係，稱為CNF，例如：

如果對這種CNF apply resolution rule，一定會找出sound and complete inference results。

IFF Implication proposition轉換成CNF

假設有一個iff proposition:

iff proposition可以先拆成兩個方向的implication：

然後implication 和 -a OR b是logically equivalent:

不過右邊還不是完全的disjunction，採用demorgan's law把negation符號展開：

並且用分配律把所有Disjunction clause用conjunction 連接:

這樣就完成了我們的CNF。

Resolution algorithm (proof by contradiction)

以下是一個利用CNF form來做resolution的演算法：

為了要檢視是否KB entails alpha，演算法假設KB  entails -alpha 成立，如果發現矛盾代表KB entails alpha，為什麼要採用反證法？

因為這樣才有辦法用之前提到的unit resolution，才能做resolution。
所以如果沒有任何resolvents出現，代表KB && -alpha所形成的CNF中任意兩個 clause無法resolve出任何東西，亦即KB　&& -alpha沒有產出新的sentence，當然就證明 KB 不entail -alpha，意即反證KB entails alpha。


舉例來說，我們想知道某個KB是否entails alpha:

要用此演算法，我們得假設KB entails -alpha，意即 KB &&-alpha成立：

先把KB && -alpha寫成 CNF:

光是第一個和第二個clause就能產出兩個resolvents，就按照演算法iteratively試著做resolution。
最後發現 -alpha這個clause無法和已經resolve出來的所有新的sentences找出resolvent，代表 KB &&-alpha not satisfying，意即 KB entails alpha。