L.A. 1 - linear equations

linear combination

vector的寫法：

vector length的符號：

所以norm operator = length

unit vector:

把linear combination of vectors寫成矩陣A乘以vector x：

這個反過來解讀可以說是 A "acts on" x，把vector x內的component轉化成另一個vector x'，例如A可以是一個difference matrix:

國高中教的矩陣乘法其實只是為了方便運算，沒有linear combination的概念在內，採用dot product形式：

Invertible matrix

Ax = b，通常已知matrix A和vector x
如果反過來知道matrix A和b，如果能求出x，則說matrix A is invertible ，會有一個對應的A^(-1) matrix：

Linear Equations

某個system of linear equations:

linear意思是變數之間只有加法，不會有乘法出現。

可以看成兩條線交會：

或是把係數看成vectors，則解相當於這兩個vectors的linear combination:

linear equations 寫成matrix form，正確解讀就是所有係數vectors組成的matrix A，其linear combination = b。

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

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!!!!!!!!!!!!!!!!!!!!!