representation

representation

「重新表示」。換個視角看世界。數據實施變換,改變姿態。

任何一個變換,皆可充作重新表示。例如直角座標變極座標(座標系轉換),例如時域變頻域(傅立葉轉換)。

重新表示有兩種形式。

變換形式:已知原數據,求新數據、求函數。
分解形式:已知新數據,求原數據、求函數。(比較常用)

如果擁有反向變換,那麼兩種形式等價。變換函數移項到等號另一側,得到另一種形式。

向量的重新表示

線性組合:直條的加權平均。(圖例是分解形式)
線性近似:橫條的一一點積。(圖例是變換形式)

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

建立座標軸,向量重新表示為座標值,座標值形成新的向量。

以分解形式為例,向量視作結果,座標軸和座標值視作原因。原因導致結果。我們的目標是找到座標軸和座標值、找到原因。

函數的重新表示

離散向量改成連續函數。就這樣。

順帶一提,函數版本的線性近似,即是「積分轉換integral transform」。座標軸融合成一個二元連續函數,即是「積分核integral kernel」。

工程數學教科書經常出現積分轉換。例如傅立葉轉換就是積分轉換,各種頻率的複弦波就是積分核。

矩陣的重新表示

左乘:數據們實施線性變換。原數據與新數據一一對應。(圖例是變換形式)
右乘:數據們的加權平均數。權重與新數據一一對應。(圖例是變換形式)

例如主成分分析就是左乘(變換形式)。

最佳化

重新表示化作最佳化問題。

min ‖y - Ax‖²          向量的重新表示y = Ax(此例是分解形式)
A,x
min ‖Y - AX‖ꜰ²         矩陣的重新表示Y = AX(此例是分解形式)
A,X

重新表示是困難的問題。同時找到變換函數、變換結果,未知數太多了,最佳化結果總是淪於瞎猜。大家追加各式各樣的限制條件,想方設法讓最佳化結果變得有意義,卻依然淪於瞎猜。

sparse representation

sparse representation

零越多越好。數學式子通常寫成L₀ norm最佳化。

min ‖y - Ax‖ꜰ² + α ‖A‖₀ + β ‖x‖₀     (α ≥ 0 and β ≥ 0)
A,x

向量視作結果,座標軸和座標值視作原因。盡量簡化座標軸、盡量減少使用座標軸,盡量讓原因單純。

當α = 0,演算法是分塊座標下降法。我沒有學會。

《Online Dictionary Learning for Sparse Coding》

sparse matrix factorization

一個矩陣分解成兩個非負矩陣相乘。

min ‖M - AB‖ꜰ² + α ‖A‖₀ + β ‖B‖₀     (α ≥ 0 and β ≥ 0)
A,B

演算法請見本站文件「matrix factorization」。

factorization machine

擬合方程式的交叉項,重新表示為矩陣分解。

交叉項(點積)是相關程度。收集兩兩相關程度,形成矩陣。分解矩陣,推敲原始事物。

sparse principal component analysis

PCA的數學式子有兩種等價寫法,這裡採用第二種。

一、令交叉投影的長度平方總和盡量大。追加限制條件:主成分必須正規正交。

max ‖YᵀX‖ꜰ²   subject to YᵀY = I
 Y

二、令新舊數據的距離平方總和盡量小。追加限制條件:主成分必須正規正交。

min ‖X - YYᵀX‖ꜰ²   subject to YᵀY = I
 Y

限制條件併入目標函數。【尚待確認】

min ‖X - YYᵀX‖ꜰ² + α (‖Y‖ꜰ² - n)     (α ≥ 0)
 Y
min ‖X - YYᵀX‖ꜰ² + α ‖Y‖ꜰ²           (α ≥ 0)
 Y

正確答案的左邊乘上任意的正規正交矩陣,仍是正確答案。為了得到唯一解,再追加限制條件:主成分盡量稀疏。

min ‖X - YYᵀX‖ꜰ² + α ‖Y‖ꜰ² + β ‖Y‖₀   (α, β ≥ 0)
 Y

convex relaxation:L₀ norm改成L₁ norm,方便最佳化。

min ‖X - YYᵀX‖ꜰ² + α ‖Y‖ꜰ² + β ‖Y‖⁎   (α, β ≥ 0)
 Y

Y是正規正交矩陣,幾何意義是旋轉暨鏡射。Y越接近I,L₁ norm就越小。也就是說,旋轉角度盡量小、盡量不旋轉數據。

separable representation

separable representation

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

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

《Algorithmic Aspects of Machine Learning》

kernel method

kernel method

數據實施變換,讓數據變漂亮,方便分群、分類、擬合、對齊、嵌入、……。

但是如何挑選函數呢?一一試驗、碰碰運氣,別無他法。

x̕ = φ(x)
transformation: φ(x)
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"];

一筆數據的誤差,習慣採用距離平方。計算誤差時,數據套用變換函數、距離平方函數,兩個步驟,有點煩。

投機取巧的方式:變換函數、距離平方函數,合併成「數據變換之後的距離平方函數」,簡稱「核函數kernel」。

kernel: k(x,y) = ‖φ(x) - φ(y)‖²

距離平方,恰好由點積組成。於是也有人採用「數據變換之後的點積函數」,簡稱「核函數kernel」。

‖φ(x) - φ(y)‖² = (φ(x) ∙ φ(x)) + (φ(y) ∙ φ(y)) - 2 (φ(x) ∙ φ(y))
kernel: k(x,y) = φ(x) ∙ φ(y)

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

優點:精簡計算步驟,降低時間複雜度。尤其是低維度變高維度的情況下,核函數可以繞過高維度,直接得到距離平方或者點積。

缺點:從核函數無法得知變換函數。不過不知道也沒關係,分群、分類、擬合、對齊、嵌入、……的結果看起來漂亮就好了。

RBF kernel:  k(x,y) = exp(-‖x-y‖² / σ²)                σ is variance
heat kernel: k(x,y) = exp(-‖x-y‖² / 4t) / (4πt)ⁿ⸍²     t is time

先前所有主題,通通可以來個kernel。諸如kernel k-means、kernel SVM、kernel PCA、kernel NMF。學術界有陣子非常流行這種灌水文章,最後弄假成真,kernel變成了教科書的標準配備。

方程組的根、積分變換的座標軸、數據變換之後的距離平方函數,通通叫做kernel。它們之間毫無關聯。

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)

數據實施變換之後,數據減去平均數的PCA:

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)

K̄(X)等於K(X)的橫條直條中心化。

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

設計核函數K,精簡計算步驟。

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

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

Bayesian inference

Bayesian inference

引入機率、允許浮動。

用條件機率成立觀點,用貝式定理切換視角。

Gaussian clustering(EM clustering)

每個群集各是一個常態分布。平均數(群集中心)、變異數(群集尺寸與疏密)各自不同。

設定常態分布數量(群集數量)、設定權重(群集尺寸)。常態分布們的加權平均,融合成一個分布──Gaussian mixture model。

實施估計,估計方式採用maximum likelihood,演算法採用EM algorithm。

Bayesian classification(naive Bayes classifier)

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

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

p(Cₖ|xᵢ)     unknown, even xᵢ is known

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

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

p(xᵢ|Cₖ) = p(Cₖ|xᵢ) p(xᵢ) / p(Cₖ)     known, when Cₖ is known

貝氏分類:針對一個類別,讓機率乘積盡量大。

  argmax prod p(Cₖ|xᵢ)
     Cₖ   i
= argmax prod p(Cₖ) p(xᵢ|Cₖ) / p(xᵢ)
     Cₖ   i
= argmax p(Cₖ) prod p(xᵢ|Cₖ)         when p(xᵢ) is uniform distributed
     Cₖ         i

各種類別融合成一個mixture model。

  argmax sum prod p(Cₖ|xᵢ)
     C    k   i
= argmax sum prod p(Cₖ) p(xᵢ|Cₖ) / p(xᵢ)
     C    k   i
= argmax sum prod p(Cₖ) p(xᵢ|Cₖ)     when p(xᵢ) is uniform distributed
     C    k   i
= argmax prod p(xᵢ|C)                mixture distribution
     C    i

Cₖ視作群集。

p(xᵢ|Cₖ)習慣設計成鐘形函數,例如高斯分布。偏離群集中心太遠,超過一定距離,群集關係迅速減弱。功能如同核函數。

p(Cₖ)習慣設定成均勻分布。功能如同權重。

p(xᵢ)習慣假定為均勻分布,各種數據出現數量均等。用來緩和sampling bias。

如果採用Gaussian mixture model,那麼Gaussian clustering與Bayesian classification完全相同。

probabilistic principal component analysis

走火入魔。大家自己看著辦吧。