Representation

Representation / Factorization

「重新表示」。數據套用函數,轉換成其他姿態,重新呈現。

「分解」。重新表示的反向操作,揭露數據原本姿態。

重新表示:已知原數據,求新數據、求函數。

分解:已知新數據,求原數據、求函數。

當函數擁有反函數,只要移項一下,重新表示、分解其實是同一個問題,沒有主從之分。

Matrix Representation / Matrix Factorization

當函數是矩陣,則有三種套用函數的方式。

一、矩陣乘在數據左邊:數據們實施線性變換。

二、矩陣乘在數據右邊:數據們的加權平均值。

三、矩陣相加:數據們加上誤差。

數據可以是一維,甚至多維。數據可以是一筆,甚至多筆。

一筆數據是一個直條。當矩陣乘在左邊,原數據與新數據從左往右依序一一對應。當矩陣乘在右邊,權重與新數據一一對應。當矩陣相加,原數據、新數據、誤差一一對應。

不熟悉線性代數的讀者,請見本站文件「Basis」,複習一下「矩陣切成直條」的觀點。

備註

representation通常是指「數據的等價呈現方式」,而不是這裡提到的「數據套用函數變成新數據」。

factorization通常是指「乘法的反向操作」,而不是這裡提到的「新數據分解成函數和原數據」。

這裡的定義源自機器學習領域,而該領域常常胡亂造詞。按理應當另造新詞,然而我並未發現更適切的詞彙,只好姑且沿用。

備註

矩陣乘法其實是函數複合。多個矩陣連乘,併成一個矩陣,這是「函數複合composition」。一個矩陣,拆成多個矩陣連乘,這是「函數分解decomposition」。函數複合的反向操作是函數分解。

儘管representation factorization外觀如同composition decomposition,但是其意義是數據、而非函數。本質略有差異。

Error(Loss)

Y = AX。誤差定為‖Y - AX‖²,矩陣元素平方和。

Optimization

設定誤差之後,矩陣分解問題變成了最佳化問題!請見本站文件「Matrix Factorization」。

大家習慣令矩陣元素非負,符合實際情況,稱作「非負矩陣分解Nonnegative Matrix Factorization」。

最佳解缺乏實際意義。大家習慣修改誤差函數,獲得其他功效。

Kernel NMF:修改誤差函數,改成kernel,讓數據形狀改變。
Sparse NMF:修改誤差函數,將L₂ norm改成L₀ norm,讓數據形狀盡量稀疏。
Regularized NMF:追加目標函數。例如追加xᵀLx,讓數據形狀盡量平滑。
                 稱做Laplacian Regularization。

Kernel Representation(Under Construction!)

Kernel Representation

數據預先實施變換。

Representation(Feature Mapping)

Kernel Principal Component Analysis

PCA:

maximize vᵀXXᵀv   subject to vᵀv = 1
maximize vᵀXXᵀv - λ(vᵀv - 1)           Lagrange multiplier
solve XXᵀv = λv                        derivative = 0

數據預先實施變換的PCA:

maximize vᵀΦ(X)Φ(X)ᵀv     st vᵀv = 1   transformation: Φ(X)
maximize vᵀΦ(X)Φ(X)ᵀv - λ(vᵀv - 1)     Lagrange multiplier
solve Φ(X)Φ(X)ᵀv = λv                  derivative = 0
solve Φ(X)Φ(X)ᵀΦ(X)w = λΦ(X)w          kernel trick: v = Φ(X)w
solve Φ(X)ᵀΦ(X)w = λw                  drop Φ(X)
solve K(X)w = λw                       kernel: K(X) = Φ(X)ᵀΦ(X)

變換函數、核函數不是線性函數,不能寫成矩陣乘法ΦX與KX,只能寫成函數求值Φ(X)與K(X)。至於Φ(X)與K(X)都是矩陣。

不設計變換函數Φ(X),設計核函數K(X),精簡計算步驟。

設計核函數K(X),求得最大的特徵值暨特徵向量。w不必還原成v,意思到了就好,精簡計算步驟。

數據減去平均值

數據實施變換之後,數據中心挪至原點。

maximize vᵀΦ(X)Φ(X)ᵀv     st vᵀv = 1   transformation: Φ(X)
maximize vᵀΦ'(X)Φ'(X)ᵀv   st vᵀv = 1   centering: Φ'(X) = Φ(X)C
maximize vᵀΦ'(X)Φ'(X)ᵀv - λ(vᵀv - 1)   Lagrange multiplier
solve Φ'(X)Φ'(X)ᵀv = λv                derivative = 0
solve Φ'(X)Φ'(X)ᵀΦ'(X)w = λΦ'(X)w      kernel trick: v = Φ'(X)w
solve Φ'(X)ᵀΦ'(X)w = λw                drop Φ'(X)
solve K'(X)w = λw                      kernel: K'(X) = Φ'(X)ᵀΦ'(X)

仍是Kernel PCA。新核函數等於原核函數的橫條直條中心化。

{ Φ'(X) = Φ(X)C
{ K(X) = Φ(X)ᵀΦ(X)
K'(X) = Φ'(X)ᵀΦ'(X) = CᵀΦ(X)ᵀΦ(X)C = CᵀK(X)C

Kernel Trick

K = Φ(X)ᵀΦ(X)是兩兩點積,Gram Matrix。

K = Φ(X)ᵀΦ(X)習慣設計成兩兩距離平方,Squared Distance Matrix。

距離平方矩陣的橫條直條中心化是內積矩陣的-2倍。

原核函數可以設計成距離平方函數。新核函數可以設計成內積矩陣的-2倍。

如此一來,原核函數不受位移影響(兩向量同減一向量,距離不變),也不受中心化影響(兩向量同減平均值,距離不變)。

如此一來,數據中心事先挪至原點,答案不變。位移不影響答案。然並卵。

K(XC) = K(X)
Φ(XC)ᵀΦ(XC) = Φ(X)ᵀΦ(X)

Kernel Laplacian Analysis【尚無正式名稱】

LA:

minimize vᵀLv   subject to vᵀv = 1
minimize vᵀLv - λ(vᵀv - 1)           Lagrange multiplier
solve Lv = λv                        derivative = 0

核函數硬湊上去:

minimize vᵀΦ(X)Φ(X)ᵀv   st vᵀv = 1   L = Φ(X)Φ(X)ᵀ
solve K(X)w = λw                     kernel: K(X) = Φ(X)ᵀΦ(X)

運用K-nearest Neighbor或其他方法建立Incidence Matrix,做為Φ(X)。

延伸閱讀:核函數(Kernel)

數據變換之後的距離平方函數(假定是L₂-Norm)。【尚待確認】

優點:數據不需先變換、再求距離。數據直接代入核函數即可,一次搞定。缺點:想知道變換函數,必須將核函數重新整理成點積運算的格式(假定是L₂-Norm)。

經典的核函數是radial basis function kernel、heat kernel。

註:kernel到處撞名──方程組的根、函數版本的基底、數據變換之後的距離函數。它們之間毫無關聯。數學家、物理學家、統計學家活在平行時空所導致的。

Kernel Classification

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

先變換、再分類。數據套用變換函數重新呈現,然後尋找分界線。讓新數據的分界線是直線,而原數據的分界線是曲線。

函數決定曲線造型。但是如何挑選函數呢?首先你要學會通靈。

Kernel Trick

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

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

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

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

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

Sparse Representation(Under Construction!)

Sparse Representation

數據維度盡量少,座標數值盡量都是零。距離函數從L₂ norm改成L₀ norm。

Sparse Principal Component Analysis

PCA追加稀疏性。

PCA改成最佳化問題:令新舊數據的距離平方總和盡量小,限制是新座標軸必須正規正交。

採用regularization,藉由調整參數,以控制距離遠近程度、正規正交程度。regularization所求得的新座標軸通常不是正規正交。然而座標軸歪斜一些也無妨,說不定能讓新舊數據距離平方和更小,找到更擬合數據的座標軸。

min ‖ X - B̌B̌ᵀX ‖²                      subject to B̌ᵀB̌ = I
min ‖ X - B̌B̌ᵀX ‖² + α ( ‖ B̌ ‖² - I )   (α ≥ 0)
min ‖ X - B̌B̌ᵀX ‖² + α ‖ B̌ ‖²           (α ≥ 0)

乍看很理想,不過事情還沒有結束。先前提到,正確答案的左邊乘上任意的正規正交矩陣,仍是正確答案。由於答案眾多,於是再增加稀疏性限制:令新座標軸的L₁ norm總和盡量小。

min ‖ X - B̌B̌ᵀX ‖₂²  + α ‖ B̌ ‖₂²  + β ‖ B̌ ‖₁    (α, β ≥ 0)

新座標軸B̌越靠近標準座標軸I,L₁ norm就越小。而B̌是正規正交矩陣,幾何意義是旋轉暨鏡射。也就是說,這是令旋轉角度盡量小、盡量不旋轉數據。

Laplacian Sparse Coding

Sparse Coding追加Dirichlet Energy Minimization。

Separable Representation(Under Construction!)

Separable Representation

https://arxiv.org/abs/1401.5226

《Algorithmic Aspects of Machine Learning》

Separable Matrix:每個直條j,皆存在橫條i,該橫條僅(i,j)處不為零。

Separable NMF:好像有多項式時間演算法。

數據盡量貼近座標軸、遠離座標軸?ICA和non-gaussianity?

一側為1、一側為0,得到最大割?

max xᵀLx + sum gauss(xi)   subject to ‖x‖² = 1

Bayesian Inference(Under Construction!)

Class / Label

Bayesian Classification

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

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

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

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

discrete choice model
softmax
sigmoid / logistic
https://stats.stackexchange.com/questions/204484/

演算法(Naive Bayes Classifier)

備忘

統計學基礎問題。

https://web.cs.hacettepe.edu.tr/~aykut/classes/spring2018/cmp784/slides/lec10-deep_generative_models-part-I_1.pdf
conditional probability 只關注某一塊子集合  代入身分建立視點
Bayes' theorem 切換視點
independence 即便到了子集合裡面比例也一樣,換句話說,在宇集合內很均勻
             p_xy(x,y) = p_x|y(x,y) p_y(y) = p_x(x) p_y(y)
             p_x|y(x,y) = p_x(x)
correlation 正比反比關係
causation   因果關係
association 上述所有東西的泛稱
central limit theorem 加在一起,平均值接近常態分布
Lévy-Cramér theorem 多個獨立變數,當總和是常態分布,則各自是常態分布
Darmois-Skitovitch theorem 線性組合互相獨立,必是常態分布