Clustering

同聲相應,同氣相求;水流濕,火就燥,雲從龍,風從虎。《易傳》

Cluster

所有數據進行分組,相似數據歸類於同一組,一筆數據只屬於某一組,每一組稱作一個「群集」。

如何定義所謂的相似呢?方法很多:距離越近,推定為越相似;鄰居越密集,推定為越相似。

群集演算法的基本原理,一類是近朱者赤、近墨者黑,不斷將數據重新分組;另一類是不斷切割群集,表示成樹狀圖。

演算法(K-Means Clustering)(Lloyd-Max Algorithm)

http://etrex.blogspot.tw/2008/05/k-mean-clustering.html

一、群集數量推定為K,隨機散佈K個點作為群集中心(常用既有的點)。

二、每一點分類到距離最近的群集中心(常用直線距離)。

三、重新計算每一個群集中心(常用平均值)。

重複二與三,直到群集不變、群集中心不動為止。最後形成群集中心的Voronoi Diagram。

時間複雜度為O(NKT),N是數據數量,K是群集數量,T是重複次數。我們無法預先得知群集數量、重複次數。數據分布情況、群集中心的初始位置,都會影響重複次數,運氣成份很大。

缺點是群集不能重疊、群集分界不能是曲線和折線、極端數據容易使群集中心偏移、一開始難以決定群集數量與群集中心、數據分布呈甜甜圈時群集中心可能永不停住。

演算法(K-Means++ Clustering)

https://mycourses.aalto.fi/mod/resource/view.php?id=153957

改良K-Means Clustering步驟一。逐一設定K個群集中心。計算每一個點到已設定的群集中心的最短距離,以最短距離的n次方做為機率大小,決定下一個群集中心。距離越遠,機率越大。

0次方等同隨機散佈,K-Means。2次方是K-Means++。∞次方等同找最遠點,Farthest-point Traversal,效果最好。

優點是群集中心比較分散,不容易擠在一起。

演算法(Linde-Buzo-Gray Clustering)

首先隨機設定一個群集中心(常用平均值)。不斷讓群集中心往反方向分裂成兩倍數量(常用少量移動、群集內最遠點對),並且重新實施K-Means Clustering。

優點是不用煩惱群集中心的初始位置。

演算法(EM Clustering)(Gaussian Mixture Model)

假設每個群集各是一個常態分布,平均數、變異數可以相異。

首先設定群集數量(常態分布數量)。然後將所有常態分布融合成一個分布,實施估計,估計方式採用Maximum Likelihood,演算法採用EM Algorithm。名稱是這樣來的。

融合數個常態分布成為一個分布,即Gaussian Mixture Model,替每個常態分布設定不同比重。

優點是考慮了群集尺寸與疏密。

演算法(K-Nearest Neighbor Clustering)

每一點各自找到距離最近的K個點作為鄰居,採多數決歸類到群集。如果距離超過了自訂臨界值,找不足K個鄰居,就替該點創造一個新的群集。

優點是不用煩惱群集數量,缺點是群集鬆散。

演算法(Jarvis-Patrick Clustering)

每一點各自找到距離最近的K個點做為鄰居。當a和b彼此都是鄰居,或者a和b至少有K'個相同鄰居(K'是自訂臨界值,K' ≤ K),則a和b歸類到同一個群集。

優點是不用煩惱群集數量、群集形狀。

演算法(DBSCAN)

https://en.wikipedia.org/wiki/DBSCAN

演算法(Nearest Neighbor Chain)

https://en.wikipedia.org/wiki/Nearest-neighbor_chain_algorithm

演算法(Minimum Spanning Tree)

運用「Minimum Spanning Tree」的瓶頸性質。實施Kruskal's Algorithm,每次新添的邊,若距離不超過threshold,則邊的兩端就視作同一個群集。

演算法(Minimum Cut Tree)

運用「Minimum Cut Tree」的瓶頸性質。然而最小割是距離最近而不是距離最遠,無法用於分離群集,所以就把一個割的權重修改為:

 ∑ w(i, j) ÷ min(|S|, |S|)
i∈S
j∈S

詳情請讀者請自行上網搜尋資料。

Classification

師曠之聰,不以六律,不能正五音。《孟子》

Classification

Clustering:未知群集(分類),找到群集(分類)。某些演算法會順便找到分界線,例如K-Means Clustering。

Classification:已知群集(分類),找到分界線。

群聚與隔離,一體兩面。相似數據群聚,相異數據也漸漸隔離。最後出現了群聚中心,也出現了隔離界線。

不同類別的數據稍微黏在一起,仍然可以找到大致的分界線。如果不同類別的數據幾乎混在一起(例如太極圖案),那麼分界線沒有任何意義。

找到分界線之後,對於一筆新的數據,就利用分界線來決定其類別──這就是Classification的主要功能。

如何應用Classification?

Classification應用十分廣泛,是世上最實用的演算法之一,也是當前的研究熱點之一。

比如說,讓電腦揀土豆。一粒土豆是一筆數據,(土豆重量,土豆顏色)是其數值。

首先,取一百粒土豆,個別以儀器測量其數值,然後人工進行分類,分為良與劣兩類。這些數據全數輸入到電腦當中。

接著,利用任何一種Classification的演算法,找到良與劣的分界線。

最後,每一粒新產的土豆,以儀器自動測量其數值,再用演算法判斷數值在分界線的哪一側,就能判斷出土豆的良劣了。

應用Classification需要考量的關鍵點

這整套自動辨識的流程當中,我們需要考量的有:

一、我們要挑選哪些特徵?例如重量、顏色、形狀等等。

二、我們要如何將特徵化為數值?例如用磅秤得到重量數值,用攝影機得到顏色數值,用影像處理演算法得到形狀數值。

三、我們要取哪些土豆當作樣本?這跟統計學有關。

四、我們如何提升分類的正確率?這跟統計學有關。

五、我們如何從分界線當中發現新的性質?例如重量越重則土豆越優、形狀越圓則土豆越優之類的。

Error

Regression讓所有間距平方和盡量小。Clustering讓最大間距盡量小。Classification讓最小間距盡量大。三者都是針對間距進行Optimization。

Point-set Function【尚無專有名詞】

Regression、Clustering、Classification可以看做是「點集合函數」最佳化。函數輸入是一個點集合,代表數據們;函數輸出是一個數值,代表誤差總和。

後面章節的演算法們,雖然掛名為Classification演算法,但是本質都是「點集合函數最佳化演算法」。更換一下誤差函數,即可解決Regression、Clustering、Classification,甚至其他問題。

注意到,凸函數最佳化,有著高速演算法,有著唯一的極值。我們往往把誤差函數設計成凸函數。

點到點距離、點到直線距離,恰是凸函數。凸函數的平方,仍是凸函數。多個凸函數相加、取最大值,仍是凸函數。

Linear Classification

Linear Classification

以直線當作分界線。

數據的維度可以推廣到三維以上,此時分界線就成了分界面、分界體等等。分界物是數據維度減少一維(hyperplane)。

雖然可以視作計算幾何問題,但是當維度太高的時候,計算相當複雜,難以快速求得精確解。因此採用了數值方法的套路。

演算法(Perceptron)

不考慮分界線到數據的距離。分界線只要分開數據即可。

分界線是一條直線ax+by+c=0。想判斷一筆數據(x₁,y₁)位於分界線的哪一側,就將(x₁,y₁)代入到直線方程式,計算ax₁+by₁+c,如果大於零就是在正側,小於零就是在反側,等於零就是在分界線上。

每一筆數據都代入計算,不見得都能正確分類。我們必須調整分界線的位置,也就是調整a b c三個參數。該如何調整才好呢?我們可以利用最佳化的思維。

設定誤差是「正確結果、分類結果不相符的數據筆數」,誤差越小越好。為了方便統計誤差,將結果定為數值0和1。正確結果:數據共兩類,第一類數據定為0,第二類數據定為1。分類結果:數據在線上、在反側定為0,數據在正側定為1。

如此一來,統計誤差,只需數值運算、無需邏輯運算。正確結果和分類結果先相減再平方,等於0即相符,等於1即不相符。

0和1顛倒設定也沒關係,a b c的計算結果多了負號而已。

 N                     2
 ∑  [gᵢ - u(axᵢ+byᵢ+c)]
i=1

gᵢ          : correct    result of data i (0 or 1)
u(axᵢ+byᵢ+c): classified result of data i (0 or 1)
u           : unit step function          (0 or 1)

最佳化演算法採用Gradient Descent:往梯度最陡的方向逐步移動。首先推導梯度,也就是分別對a b c三個變數進行偏微分:

∂   N                     2
――  ∑  [gᵢ - u(axᵢ+byᵢ+c)]  =  ∑ [gᵢ - u(axᵢ+byᵢ+c)] ⋅ -2xᵢ
∂a i=1
                            =  ∑ errorᵢ ⋅ -2xᵢ

∂   N                     2
――  ∑  [gᵢ - u(axᵢ+byᵢ+c)]  =  ∑ [gᵢ - u(axᵢ+byᵢ+c)] ⋅ -2yᵢ
∂b i=1
                            =  ∑ errorᵢ ⋅ -2yᵢ

∂   N                     2
――  ∑  [gᵢ - u(axᵢ+byᵢ+c)]  =  ∑ [gᵢ - u(axᵢ+byᵢ+c)] ⋅ -2
∂c i=1
                            =  ∑ errorᵢ ⋅ -2

一開始a b c設定成任意值。a b c不斷往梯度最陡的方向移動一段距離,朝最小值前進:

     [ 0 ]
w0 = [ 0 ]  一開始a b c設定成任意值
     [ 0 ]
                 [ ∑ errorᵢ ⋅ -2xᵢ ]               [ ∑ errorᵢ ⋅ xᵢ ]
wt+1 = wt - rate [ ∑ errorᵢ ⋅ -2yᵢ ] = wt + 2 rate [ ∑ errorᵢ ⋅ yᵢ ]
                 [ ∑ errorᵢ ⋅ -2   ]               [ ∑ errorᵢ      ]

通常會把2併入rate。或者一開始設定誤差函數多乘一個1/2,來把2消掉。

推廣成online演算法,依序處理每一筆數據,一次一筆。

                   [ errorᵢ ⋅ xᵢ ]
wt+1 = wt + 2 rate [ errorᵢ ⋅ yᵢ ]
                   [ errorᵢ      ]

通常會把2併入rate。或者一開始設定誤差函數多乘一個1/2,來把2消掉。

公式非常簡潔!這就是為什麼使用這種誤差設定方式、使用Gradient Descent的原因。這是前人努力試驗出來的最簡潔的方式。

當數據可分為兩半,則誤差呈單峰函數,Gradient Descent不會卡在區域極值。證明方式是逐次加入一筆數據。【尚待確認】

換句話說,當數據可分為兩半,而且rate適中(太小導致攤在山腰、太大導致越過山頂),則此演算法一定可以找到正確的分界線。當數據不可分為兩半,則此演算法毫無用武之地。

「一筆數據代入直線方程式」這件事,通常畫成理工味道十足的圖。這個東西有個古怪名稱叫做perceptron:

所有輸入乘上權重、相加起來,經過unit step function,最後輸出0或1(也有人輸出+1或-1)。

函數不一定得是unit step function。有些時候需要輸出實數,就可以改成sigmoid function。

UVa 11289 ICPC 3581

演算法(Support Vector Machine)

考慮分界線到數據的距離。分界線位於正中央,兩類數據相隔越遠越好。準確來說,分界線到兩類數據的最短距離均等、最短距離越大越好。

舉例來說,二維的情況下,兩類數據各自求凸包,分界線是凸包之間最近點對的中垂線,或者分界線平行於凸包上某一條邊。

但是當維度太高的時候,難以計算凸包、中垂超平面。只好採用數值方法的套路。

分界線是一條直線ax+by+c=0。想計算一筆數據(x₁,y₁)到分界線的距離,就將(x₁,y₁)代入到點與直線距離公式,計算(ax₁+by₁+c) / sqrt(a²+b²)。距離有正負號,如果大於零就是在正側,小於零就是在反側,等於零就是在分界線上。

間距線是兩條直線ax+by+c=1和ax+by+c=-1(已將截距縮放為1)。想計算間距線到分界線的距離,就將間距線上任意一點代入到點與直線距離公式(顯然分子是1和-1)。如此便得到半個間距。

每一筆數據到分界線的距離,都必須大於等於半個間距。而且每一筆數據都要選對邊。

當數據可以分成兩半,採用regularization:最大化間距,限制是全部數據都分對。

為了方便判斷距離,數據標記為-1和+1(本應是0和1)。為了避免除以零,改為最小化間距的倒數(本應是負數)。為了方便最佳化,再取平方變成凸函數。

針對此誤差式子的最佳化演算法是Sequential Minimal Optimization,請讀者自行查詢。

https://www.csie.ntu.edu.tw/~cjlin/libsvm/

                                                             s
classifer: px+qy+r=0   margin: px+qy+r=±s   half-width: ――――――――――― 
                                                        sqrt(p²+q²)

let a = p/s, b = q/s, c = r/s, remove variable s.

                                                             1
classifer: ax+by+c=0   margin: ax+by+c=±1   half-width: ――――――――――― 
                                                        sqrt(a²+b²)

         1                      axᵢ+byᵢ+c         1
max ―――――――――――   subject to { ――――――――――― ≥ ――――――――――― ⋅ gᵢ } for all i
    sqrt(a²+b²)                sqrt(a²+b²)   sqrt(a²+b²)

         1
max ―――――――――――   subject to { axᵢ+byᵢ+c ≥ gᵢ } for all i
    sqrt(a²+b²)

min sqrt(a²+b²)   subject to { axᵢ+byᵢ+c ≥ gᵢ } for all i

min   (a²+b²)     subject to { axᵢ+byᵢ+c ≥ gᵢ } for all i

min   (a²+b²)     + ∑ αᵢ [ (axᵢ+byᵢ+c) - gᵢ ]   (αᵢ ≥ 0)

當數據不能分成兩半,採用scalarization:最大化間距,最小化分錯的數據數量。記得調整成凸函數。不過沒人這樣做。

         1
max ―――――――――――  ,  min ∑ [ axᵢ+byᵢ+c < gᵢ ]
    sqrt(a²+b²)

min α (a²+b²) + β ∑ [u(gᵢ - (axᵢ+byᵢ+c))]²   (α ≥ 0, β ≥ 0)

有人刪去unit step函數,把β設定成1,稱做Least Squares Support Vector Machine。有點莫名其妙。

min α (a²+b²) + β ∑ [gᵢ - (axᵢ+byᵢ+c)]²   (α ≥ 0, β = 1)

Inlier / Outlier

真實世界的數據並非完美,常有例外。

無彈性的定義:全部數據分為inlier和outlier;inlier是分對的數據,outlier 是分錯的數據。

有彈性的定義:全部數據分為inlier和outlier;inlier是距離分界線太近的數據、以及分對的數據,outlier是距離分界線太遠又分錯的數據。

順帶一提,當數據無法分兩半,常見的手法是:無視彈性範圍內的數據,並且限制其數量上限。可以透過regularization處理。

演算法(AdaBoost)(Adaptive Boosting)

實施分類演算法,分錯的數據,複製並增加其數量,再繼續實施分類演算法。這使得誤差大幅增加,使得分界線大幅靠近分錯的數據,進而迅速減少分錯的數據。

增加倍率:分對的數量除以分錯的數量。數量不必是整數。

AdaBoost好處多多。分類過程中,分界線的移動步伐變大了,提早找到正確分界線。分類結束後,每筆數據的數量,可以看成是出錯程度,可依此判斷outlier。分類結束後,如果數據無法正確分兩半,就以每回合的分界線的平均,推定是最理想的分界線。

AdaBoost儘管缺乏理論根據,儘管名字怪異,卻非常實用。

演算法(Gradient Boosting)

實施分類演算法,得到分界線。然後不斷微調分界線。

挑出分錯的數據,另外實施分類演算法,得到微調用的分界線。當前分界線,加上微調用的分界線,完成一次微調。重複這些步驟,直到分錯的數據足夠少,或者是誤差總和足夠小。

微調用的分界線,可以乘上倍率。注意到倍率太大就不是微調了,而倍率太小就失去調整效果了。

概念宛如Gradient Descent,故取名Gradient。概念宛如Adaptive Boosting,故取名Boosting。

Polynomial Classification

Polynomial Classification

以多項式曲線、多項式曲面當作分界線。

根據工程師的實驗,數據套用函數重新呈現、分界線是直線,原始數據、分界線是曲線,前者比後者的效果更好──儘管目前還沒有嚴謹的數學證明。因此這裡就不介紹分界線是曲線的情況了。

Representation(Feature Map)

classifier center = (24,22) radius = 10, #(data) = 13 + 7 = 21 p = {{17,8},{21,8},{27,8},{33,10},{37,15},{39,22},{36,30},{30,35},{21,35},{12,32},{12,28},{7,22},{10,14},{18,15},{24,16},{28,18},{16,19},{18,24},{24,23},{31,25},{27,29}}; f[x_] := (x-24)*(x-24); g[y_] := (y-22)*(y-22); h[x_,y_] := Sqrt[2]*(x-24)*(y-22); q = Transpose[{ f[ p[[All,1]] ], g[ p[[All,2]] ], Apply[h, p, {1}] }]; ListPointPlot3D[{q[[1;;13]], q[[14;;21]]}, BoxRatios -> {1,1,1}, PlotStyle -> PointSize[Large]] c = Classify[q -> {"A","A","A","A","A","A","A","A","A","A","A","A","A","B","B","B","B","B","B","B","B"}, "Decision", Method->"SupportVectorMachine"];

http://cseweb.ucsd.edu/classes/sp13/cse151-a/Kernels.pdf

數據套用函數、增加維度,重新呈現。新數據的分界線是直線,則原數據的分界線是曲線。

但是如何挑選函數呢?首先你要學會通靈。

點與直線距離,時間複雜度從O(D)變成O(D'),D是原數據的維度,D'是新數據的維度。

Kernel

http://www.robots.ox.ac.uk/~az/lectures/ml/

實施分類演算法,每回合都要重新累計誤差總和:每筆數據先套用函數重新呈現、再計算點與直線距離。

兩個步驟,有點煩。有個投機取巧方式稱作kernel trick:不設計函數、不推導距離,而是改為設計「數據套用函數之後的距離函數」。關於距離函數,請參考本站文件「Metric」。

分界線的參數a b c,其中a b可以表示成新數據的加權平均值(新數據根據其類別額外乘上+1或-1)。點與直線距離,其中一部分變成了新數據與新數據的點積,即是kernel。

點與直線距離,運用kernel,只需原數據、無需新數據,時間複雜度為O(ND),D是原數據的維度。當原維度遠小於新維度,kernel trick就有好處,可以很快算好誤差總和。

Underfitting / Overfitting

用單純的函數去區分複雜的數據們,顯然分類的不太完美。

用複雜的函數去區分單純的數據們,顯然事情被搞複雜了。

如果我們不清楚數據的性質,也就無法抉擇函數了。那麼,該如何了解數據的性質呢?這屬於宗教信仰的範疇,就此打住。

Hierarchical Classification

Hierarchical Classification

數據往往無法順利地一分為二,數據往往有兩種以上類別,先前的演算法往往毫無用武之地。

解法是階層架構、樹狀圖,稱作「決策樹Decision Tree」。

另一種解法是一連串測試,稱作「蕨Fern」。奇葩的名稱。蕨是決策樹的簡易版本:同一層節點,共用同一條分界線。

演算法(Decision Tree)(Classification Tree)

援引「k-Dimensional Tree」的精神,用於分類。

貪心法。選擇分類效果最好的分界線,將數據分兩份。兩份數據分頭遞迴下去,直到不同類別的數據都被分開為止。

每次選擇分界線時,窮舉各種分界線走向(窮舉每個維度),窮舉各種分界線位置(窮舉每筆數據),從中找到分類效果最好者。

分界線兩側的數據,分頭計算混亂程度。兩個混亂程度,求加權平均值(權重是數據數量),做為分類效果。數值越低,效果越好。

混亂程度有兩種評估方式:一、Gini impurity:各個類別的數據比例,兩兩相乘(不乘自身),總和越小越好;二、information gain:各個類別的數據比例,求熵,總和越小越好。

兩種方式都沒有科學根據。通常使用第一種,比較好算。

不採用清澈程度、卻採用混亂程度,這般迂迴曲折,是因為清澈程度不好揣摩、而混亂程度容易具體實現。

Gini impurity:  ∑ [ p(Ci) p(Cj) ] = 1 - ∑ [ p(Ci) p(Ci) ]
               i≠j                      i

information gain: - ∑ [ p(Ci) log₂ p(Ci) ]
                    i

  Ci :第i種類別的數據集合。
p(Ci):第i種類別的數據數量,除以所有類別的數據總數量。也就是比例。

因為是貪心法,所以分界線配置往往不是最精簡的、分界線數量往往不是最少的。

時間複雜度為O(DNNN)。運用「掃描線」為O(DNNlogN)。當運氣很好,數據的數量每次都剛好對半分,為O(DN(logN)^2)。

一、窮舉D個維度、窮舉N筆數據,找到分界線。
二、針對一條分界線,判斷每筆數據位於哪一側,需時O(N)。
三、兩側數據,分頭計算C種類別之間的混亂程度,需時O(C)。C通常視作常數。
四、分界線數量最少0條(數據只有唯一一種類別)。
  分界線數量最多N-1條(每次都分出一筆數據)。
  分界線數量就是節點數量。

演算法(Random Forest)

選擇分界線時,改為隨機窮舉一小部分,可以省時。

接著,製造大量的樹,刪除相似的樹。多數決。就這樣子。

隨機的副作用是分不乾淨。不過為了避免overfitting,也就沒必要分乾淨。而多數決不但抑制了副作用,同時也改良了分界線。

演算法(Random Ferns)

樹改成蕨。可以省時。可以省程式碼。

Predefined Classifier【尚無專有名詞】

預先設置一些分界線,每次找分界線時,就考慮這些分界線。如此一來,分界線就不必是鉛直線、水平線,分界線可以是任意圖形。甚至多條分界線可以合成一種分界線。

當數據有兩種以上類別,先運用Linear Classification,兩兩之間求分界線;再運用Hierarchical Classification,選取適當的分界線,建立階層架構。

Graphical Classification(Under Construction!)

楔子

Neuron與Perceptron

生物學家、醫學家研究動物,發現了動物藉由神經來接收與傳達訊息,神經的基本單位是「神經元」。後來又發現,動物的大腦由大量神經元構成。

計算學家、數學家仿照神經元,發明了「感知器」,用來分類和預測事物。後來又發現,感知器其實就是線性分類器。

於是科學家大膽猜測:大腦似乎是一大堆線性分類器,思考似乎是一連串線性分類!科學家正在深入研究當中。

人格、行為、情緒、本能、直覺、天分、三觀、智力、智慧,這些抽象的心理概念,也許就是一堆線性分類器。

一大堆Neuron與Perceptron

神經元、感知器能做什麼事?

數學家發現感知器可以分類。一個感知器,製造筆直的分界線。一連串感知器,得以兜出各式各樣的分類效果,製造曲折的分界線。

這個發現相當重要。適當地排列組合感知器,就擁有辨識能力。大腦的辨識能力很可能源自於此!

數學家發現感知器可以算數學。一層可兜出邏輯運算NOT和AND和OR,兩層可兜出邏輯運算XOR和XNOR。進一步從邏輯運算兜出數值運算。進一步從數值運算兜出演算法。

這個發現相當重要。適當地排列組合感知器,就擁有判斷能力、計算能力。大腦的判斷能力、計算能力很可能源自於此!

大腦擁有大量神經元,應該得以進行非常深奧的推理,甚至超越邏輯所能描述的現象。例如由愛生恨、愛之深責之切、愛到深處無怨尤,大腦經常產出超乎理性的結論。

然而科學家迄今還不知道大腦的詳細結構。比如說「由愛生恨」的神經元如何連結呢?沒有人知道!科學家正在克服這個問題。

http://zhuanlan.zhihu.com/p/20561464

Artificial Neural Network

「人工神經網路」、「類神經網路」。大量感知器串聯成網路,建立階層架構,模仿大腦!

然而我們往往不知道人工神經網路該兜成什麼樣子。於是大家捨難取易──選擇特定款式,藉由調整權重,達到分類效果。人工神經網路的經典款式如:

Feedforward Neural Network
Recurrent Neural Network
Spiking Neural Network
Convolutional Neural Network
Restricted Boltzmann Machine

真實神經網路,神經元會增生、死亡、重新連結。人工神經網路,格式固定,感知器不會增生、死亡、重新連結,分類效果較差。

為什麼不改成動態版本呢?因為時間複雜度。動態版本的計算量更加巨大,而現今計算機的計算力仍嫌不足。

近況

人工神經網路的潛力,遠遠超越目前的演算法,遠遠超越我們以窮舉法、分治法、動態規劃、貪心法所設計出來的演算法。最近電腦打敗人類圍棋冠軍,正是使用人工神經網路,棋風宛如真人。

http://www.zhihu.com/question/39905662/answer/88895000

學術單位正在研究人工神經網路的功效,公司行號正在製作人工神經網路的晶片。又由於分散式計算的崛起,計算機的計算力增加了,使得人工神經網路的研究略有進展。人工神經網路正夯。

http://www.zhihu.com/question/24825159/answer/29427405

各個領域的專家,也開始關注神經系統。關鍵字如neuroscience、neural computing、neural engineering,請讀者自行研究。

遠景

人工神經網路應該可以效仿編譯器自舉。我們總是用人腦設計演算法,既然人腦是神經元構成的網路、演算法是感知器構成的網路,理所當然我們能用人工神經網路設計人工神經網路。

學以致用、神來之筆,這些抽象的心理概念,也許就是自舉。

邏輯運算 → 數值運算 → 分類運算 → 算法

古人發明了邏輯運算(藉由電路),再用邏輯運算兜出數值運算(藉由二進位),再用數值運算兜出演算法(藉由流程圖)。至此是地球人的最新進度。

目前計算學家正在嘗試:用數值運算兜出分類運算(藉由數值方法),再用分類運算兜出演算法(藉由神經元)。讓我們拭目以待!

演算法(Feedforward Neural Network)

http://playground.tensorflow.org/

一層一層鋪起,容易計算。

http://www4.rgu.ac.uk/files/chapter3%20-%20bp.pdf
http://colah.github.io/posts/2015-08-Backprop/

一、憑感覺設定層數、設定每一層的perceptron數量。
  沒人知道正確數量應該是多少。
二、輸入一筆數據之後,更新每一個perceptron的所有入邊的權重:
  由於必須拿到output error才能更新,所以要從output層往回更新。
  (backpropagation名稱由此而來。)
三、計算一個perceptron的output error:
  針對一個出邊,「出邊的權重」乘上「出邊的perception的output error」,
  然後所有出邊算得的,通通加起來。

不斷輸入資料、輸出結果,逐步調整每個perceptron的分界線,最後得到一個分類器。

http://colah.github.io/posts/2014-03-NN-Manifolds-Topology/
1. 把每一層的功能想做是 representation
2. sigmoid/tanh 的用途是讓 representation 有著形變效果
3. 引入流形的相關知識,嘗試判斷是否可以找到分界線
一種多層次的 sparse coding 的機制

範例:分辨上下

000011 111100 000011 010111 101111 110110 111101 001111 000000 000110
011110 000110 001110 011001 101001 110110 100111 011001 011100 001100
110000 000001 111000 001111 111111 011100 111111 000000 000110 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
111000 011100 110000 011111 011110 011110 011110 011110 111110 111110
001111 110111 111110 110001 111111 110011 010110 110011 101011 100111
000001 000001 000011 110000 011111 000001 011110 111110 111001 111110
http://www.webpages.ttu.edu/dleverin/neural_network/neural_networks.html
輸入值、初始值、層數會影響收斂結果
輸入值太小、學習率太大  兩邊會分不開
初始值一開始接近零  就會爆炸  原因不清楚

第一層的perceptron有row個,每個perceptron的輸入變數有col個,輸入值是各個pixel。
第二層只有一個perceptron,輸入變數col個,來自上一層

範例:分辨數字

http://archive.ics.uci.edu/ml/datasets/Optical+Recognition+of+Handwritten+Digits

ICPC 4359

演算法(Recurrent Neural Network)

製造迴圈。好處是建立餘韻,壞處是難以調整權重。

知名版本如LSTM Neural Network。

演算法(Convolutional Neural Network)

請先參考本站文件「Image Filtering」。

http://cs231n.stanford.edu/syllabus.html
http://www.vision.rwth-aachen.de/media/course/WS/2015/computer-vision/cv15-part16-categorization4.pdf
http://people.eecs.berkeley.edu/~rbg/index.html
http://girlswhocode.thenew123.com/news_748240.htm
dropout 去掉一些沒用的點
pooling 取總和或最大值

備忘

個人推測ReLU的主要功能是改變最佳化演算法的細節,而非數據的Representation。也就是說,只要調整最佳化演算法,就不需要ReLU。

另一方面,由於我們無法預測數據分布,因此任何事先指定的Representation(例如sigmoid和kernel trick)都是沒有意義的。添加機率(例如貝氏學習)也是同樣沒有意義的。

個人推測正確的解法是:改變函數之間的輸入輸出連接方式。從最簡單的函數開始(例如線性變換),以函數的複合來得到各種特別的函數,或說是特別的Representation。

一個值得關注的地方是將各種Representation視作模組,經過適當突變(改變單一函數)、適當排列組合(改變階層架構)之後,可以得到更有用的模組。就好比人類發明機器的歷史過程。人類的智力架構可能也類似於此。

一個函數的輸出的重新排列組合,可以視作鏡射變換,鏡射變換是一個線性變換。至於函數之間的輸入輸出連接方式的重新排列組合,可以視作函數們複合一個線性變換。反過來說,函數的複合具備了重新排列組合的功效,而階層最佳化自然能找到適當的排列組合。

我就一介民科。以上僅供參考。

Bayesian Classification(Under Construction!)

Bayesian Classification

迄今都是假定一筆數據只有唯一一種類別。

現在推廣成一筆數據有多種類別,類別是浮動數字,每種類別的機率高低都不同。

對調主角與配角,切換視角,一種類別也就有多筆數據,數據是浮動數字,每種數據的機率高低都不同。

貝式定理可以用來切換視角。

Linear Discriminative Analysis

援引「Principal Component Analysis」的精神,用於分類。

尋找一組新座標軸,讓數據投影到座標軸之後,各類數據的平均值的變異數盡量大(異類盡量散開),各類數據各自的變異數盡量小(同類盡量聚集)。

個人推測kernel trick (representer theorem)、spectral transform、Ax² optimization有著某種關聯。數據有了類別。

Neighborhood Component Analysis

援引「Principal Component Analysis」的精神,用於分類。

找到一個轉換矩陣,讓新數據同類相聚。統計同類數據之間的兩兩距離總和,令距離越近越好。距離定義成有向距離:相離最近的K個鄰居所構成的softmax函數的平方。因為難以預測新數據的鄰居關係,所以姑且採用原數據的鄰居關係。

https://en.wikipedia.org/wiki/Neighbourhood_components_analysis