Transformation(Under Construction!)

楔子

計算機當中,凡事皆須化作數值,因此資料又稱數據。

文字、聲音、圖片、模型,皆透過特定規則化作數值。

把數值們表示成一個向量,當作輸入,套用函數進行變換,得到輸出。如此一來就得到了新的文字、聲音、圖片、模型。

Transformation

「變換」。數據套用函數,轉換姿態。數據產生變化。

大家習慣使用「線性變換」。優點是線性變換只有加法與倍率,相當單純,擁有高速演算法。缺點是單純導致功效不彰。期待大家發明更特別的變換!

目前的研究熱點有兩大方向:一、線性變換的多重複合:類神經網路;二、複變函數與場:波函數。

Inverse Transformation

「反向變換」。以反函數實施變換。把經過變換的東西,還原為原始樣貌。

求得反函數之後,就很容易實施反向變換了。然而目前沒有演算法可以求得反函數!除了少數特例:一元一次多項式函數,以移項求得反函數;線性變換,以高斯喬登消去法求得反函數;數學家發明的特殊函數,以推理方式求得反函數,例如傅立葉轉換。

Dual Transformation

原函數、反函數,兩者恰好相同。變換兩次等同變換零次。這種情況下的變換稱作「對偶變換」。

例如f(x) = -x與f⁻¹(x) = -x。又例如f(x) = 1/x與f⁻¹(x) = 1/x。

Representation

轉換前後,數據內涵保持相同,換個角度看世界。這種情況下的變換稱作「重新表示」。

一般是指擁有反向變換的轉換,或者保留某些特性的轉換,例如保距、保角。

對應運算【尚無正式名稱】

針對一個變換,輸入和輸出有時候擁有某些對應運算。

例如f(x) = 2ˣ,輸入相加等同輸出相乘。我們可以先相加、再變換,也可以先變換、再相乘,效果相同。

存在反向變換時,對應運算可以用來設計演算法。

例如f(x) = 2ˣ與f⁻¹(x) = log₂x,。數字變小,比較好算。

存在對偶變換時,對應運算必定互相對稱。稱做「對偶運算」。

例如補集函數f(A) = Aᶜ,輸入交集等同輸出聯集,輸入聯集也等同輸出交集。對偶運算是交集對聯集。

有時候原函數、反函數,兩者幾乎相同,也會產生對偶運算。

例如正向傅立葉轉換、逆向傅立葉轉換,差異在於除與乘。對偶運算是乘法對摺積。

備註

函數是「對應」與「變換」兩種概念的結合。

先前介紹的主題皆是「對應」,著重於函數本身的姿態。包括了微積分、場、求根、求解、最佳化、內插、迴歸、聚類、分類。

此處介紹的主題皆是「變換」,著重於輸入輸出的姿態。

Metric(Under Construction!)

長度(Length)

現實世界,考慮一個東西有多少份量;化為數學,就是考慮一個東西的長度是多少。

此處的長度,是數學術語,不是物理學術語。此處的長度,是指份量多寡,不是指拉成直線、公分公尺。

長度有時候又稱為絕對值。

長度函數(Norm)

長度在數學中擁有嚴謹定義:

一、有些東西長度為零,p(A) = 0。
二、一個東西均勻放大縮小,其長度也隨著放大縮小,p(k⋅A) = |k|⋅p(A)。
三、兩個東西拼裝起來,其長度只會短少或保持一樣,p(A + B) ≤ p(A) + p(B)。

常見的長度函數:

L₀-Norm:非零的數量。
L₁-Norm:先相加、再轉正數。
L₂-Norm:先平方和、再平方根。
L∞-Norm:最大值。

常見的元件:

一個數值的長度:用絕對值計算長度。
一個向量的長度:有多種公式,請參考「Vector Norm」。
        最經典的是平方長度:先平方和、再平方根。
一個矩陣的長度:有多種公式,請參考「Matrix Norm」。

距離(Distance)

現實世界,考慮兩個東西有多相似;化為數學,就是考慮兩個東西的距離有多接近。

UVa 10508 11085 ICPC 5132

距離函數(Metric)

距離在數學中擁有嚴謹定義:

一、兩個一樣的東西,距離等於零,d(A,A) = 0。
二、A到B的距離等於B到A的距離,d(A,B) = d(B,A)。
三、三角不等式,ABC三個東西,兩邊和大於等於第三邊,
  d(A,B) + d(B,C) ≥ d(A,C)
  d(A,C) + d(B,C) ≥ d(A,B)
  d(A,B) + d(A,C) ≥ d(B,C)

常見的距離函數:

Euclidean Distance(L₂):直線距離。
Taxicab Distance(L₁):垂直、水平移動的距離。
Hamming Distance(L₀):相對應維度,數值相異的維度個數。

常見的元件:

兩個數值的距離:用減法與絕對值計算距離。
兩個向量的距離:以「Minkowski Distance」計算距離。
兩串數列的距離:以「Levenshtein Distance」計算距離。
        演算法是「Dynamic Time Warping」。
兩串字串的距離:字串類似數列,同上。
兩串訊號的距離:以「Linear Predictive Coding」重新表示訊號,
        或者以「Fourier Transform」重新表示訊號,
        再用數學公式計算距離。 
兩條曲線的距離:以「Fréchet Distance」計算距離。
兩群點的距離:以「Hausdorff Distance」或者「Matching Distance」計算距離。
兩個集合的距離:以「Jaccard Index」或者「Sørensen–Dice Index」計算距離。
兩棵樹的距離:以「Tree Distance」計算距離。
兩張圖的距離:以「Graph Kernel」計算距離。

保長(Length Preserving)

變換前後,任一點長度維持不變,稱做保長變換。

舉例來說,旋轉、鏡射是保長變換;平移、縮放、投影不是保距變換。

保距(Isometry)(Distance Preserving)

變換前後,任兩點距離維持不變,稱做保距變換。

舉例來說,平移、旋轉、鏡射是保距變換;縮放、投影不是保距變換。

保角(Conformal)(Angle Preserving)

變換前後,任相鄰三點夾角維持不變,稱做保角變換。

平移、旋轉、鏡射、整體縮放是保角變換。投影不是保角變換。

除了實數函數,大家也討論複數函數。舉例來說,四則運算、倒數、平方、平方根是保角變換,而且格線呈現曲線。

保長則保距,保距則保角。

核函數(Kernel)

資料變換之後的距離函數。「統計機器學習」領域胡亂造詞。

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

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

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

Coordinate(Under Construction!)

集合(Set)、元組(Tuple)

多物視作一物。差別在於:

集合的元素不分先後,無視重複元素。採用大括號。

元組的元素區分先後,允許重複元素。採用小括號。

set       tuple
{4,5,7}   (5,4,7)
{1,2,3}   (1,1,2,2,3,3)
{}        ()

向量(Vector)

多數視作一物。

向量的數值區分先後,允許重複元素。採用中括號。

由於線性變換的緣故,向量寫成直的。

vector    vector
[ 5 ]     [5 4 7]ᵀ
[ 4 ] 
[ 7 ]

空間(Space)

空間即是集合,並且裝備特殊技能。開外掛的集合。

常見的集合元件,諸如幾何的「點」、代數的「向量」。

  topological space 拓樸空間 一堆點,裝備鄰居        彈性形狀
       metric space 距離空間 一堆點,裝備距離        相似程度
    Euclidean space 歐氏空間 一堆點,裝備長、角、平移、旋轉 幾何圖形
       vector space 向量空間 一堆向量,裝備加法、倍率    加權平均
inner product space 內積空間 一堆向量,裝備加法、倍率、內積 相對方位

此處的空間,是數學術語,不是物理學術語。此處的空間,是指一堆東西,不是指立體容積。

座標(Coordinate)

空間裡每個元素,分別設定獨一無二的tuple。一種設定方式稱作一種「座標系coordinate system」,tuple的一個欄位稱做一種「座標coordinate」。

大家習慣令不同元素擁有不同座標、相鄰元素擁有相鄰座標、座標欄位數量符合維度大小。

預設座標系:直角座標系

大家熟知的一維數線、二維平面、三維空間,都是歐式空間。大家熟知的直角座標系,其實是歐式空間的其中一種座標系。

典型座標系

tuple每個數字,設定成角度、長度、縮放倍率。

 Cartesian coordinates 直角座標 長度、…     任意維
     polar coordinates 極座標  長度、角度    二維
    sphere coordinates 球座標  長度、角度、角度 三維
  cylinder coordinates 圓柱座標 長度、長度、角度 三維
projective coordinates 齊次座標 長度、…、倍率  二維以上

http://b.bbi.com.tw/Gossiping/1J67W85o.html

製圖時,畫出格線,容易辨認座標系。

座標系寫成函數組

{ Fx R3->R1: (x,y,z) -> x
{ Fy R3->R1: (x,y,z) -> y
{ Fz R3->R1: (x,y,z) -> z

有了預設座標系,各種座標系得以寫成函數組。一個函數求得一個維度的座標:輸入地點,輸出座標數值。

函數組是一對一函數(擁有反函數),不同地點擁有不同座標;函數組是連續函數,相鄰地點擁有相鄰座標。

[plot into graph]

cartesian coordinates  identity函數
{ x' = x
{ y' = y

polar coordinates
{ r = sqrt(xx + yy)
{ t = tan(y/x)

other
{ x' = x
{ y' = x/365
{ z' = log10(y)

更換座標系

一個座標系變成另一個座標系。可以拆成兩個步驟:先找反函數、再套用函數。

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

數學當中,座標系是替點貼標籤,座標系轉換是更換標籤,不會改變點。計算學當中,直角座標系是將點化作數值,座標系轉換是一種變換,用來改變點。

特殊座標系

空間元素還可以改成其他元件,訂立其他座標。這裡就不多提了。

數據可以畫成圖形

運用各種座標系,得到各種外觀。

前面鋪陳甚多,其實只是為了想介紹這件事。

scatter plot。

Basis(Under Construction!)

加權平均值(Weighted Average)

可以利用加權平均值創造座標系。請見本站文件「Weighted Average Coordinates」。

基底(Basis)

使用單一數值作為座標軸。

使用數列作為座標軸。

使用函數作為座標軸。

核(Kernel)

函數版本的基底。

積分變換(Integral Transform)

函數版本的線性組合。權重從實數倍率推廣成函數點積。

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

Homogeneous Coordinates(Under Construction!)

齊次座標(Homogeneous Coordinates)

請讀者非常熟悉計算幾何觀點線性代數觀點的二維幾何變換。

點是過原點直線,點的座標是過原點直線的方向向量。直線是過原點平面,直線的座標是過原點平面的法向量。兩點外積得連線,是兩條過原點直線的方向向量的外積,得兩線形成之平面的法向量。兩線外積得交點,是兩個過原點平面的法向量的外積,得平面相交之直線的方向向量。

線ax+by+c=0 ---> (a,b,c)      三個座標值一齊乘上任意倍率,仍等價
點(x,y)     ---> (x,y,1)      三個座標值一齊乘上任意倍率,仍等價
點p在線l上  ---> p dot l = 0
線l穿過點p  ---> l dot p = 0
兩線交點    ---> l1 cross l2
兩點連線    ---> p1 cross p2
兩線平行    ---> l1 cross l2 = (a,b,0)

Polar Coordinates(Under Construction!)

極座標轉換(Polar Coordinates)

z = ‖z‖ (z/‖z‖)
‖z‖ is length
z/‖z‖ is angle
複數 垂直座標  轉換機制  極座標   轉換名稱  時間複雜度
一一 一一一一一 一一一一一 一一一一一 一一一一一 一一一一一
數字 實部、虛部 長度、角度 幅長、幅角 極座標轉換 O(1)
函數 實部、虛部 複數波   強度、相位 傅立葉轉換 O(NlogN)
e^x 輸入相加=輸出相乘
fft 輸入點積=輸出摺積

複數平面,垂直座標變極座標(實部虛部變幅長幅角),可以推廣成函數。傅立葉轉換。

有些問題在垂直座標很難算,在頻域座標卻很好算。複數乘法變長度相乘、角度相加。數列摺積變數列乘法。

Radial Function

X and F(X) ⇨ Angle and Radius【查無專有名詞】

繪製函數圖形,除了水平延展,還可以迴轉周旋。

函數輸入視作從X軸出發的角度,函數輸出視作從原點出發的長度。

利用三角函數sin和cos找到繪製地點。

當函數輸出是負值,則無法畫出函數圖形。三種解法:一、乾脆不畫。二、負值變正值、換顏色。三、穿越原點,跑到對面,角度相差180度。

角度可以改成x的倍率,修改轉速。

運用周旋,得以製作許多特殊圖形。

Periodicity ⇨ Closed

有個值得一提的案例是週期函數:固定間距、不斷重複的函數。

角度改成x的適當倍率,使得一個間距(或者其倍數)剛好轉一圈,函數圖形頭尾銜接,得到封閉曲線。

Angle and Radius ⇨ X and F(X)【查無專有名詞】

任意的封閉曲線,想要從周旋變成延展,就必須滿足函數的規定:找到內部一點作為原點,任意放射線與曲線的交點只有一點。之後即可視作一般函數進行處理。

不是函數的封閉曲線,想要滿足函數的規定,我只知道一種解法是平滑化:每一個點,取其鄰點,求平均值。實施足夠次數,似乎就會變成函數。實施無限次,最後就會變成圓形,其概念類似於流形與圓的映射。我不清楚這部分是否有人研究。

不是函數的一般曲線,我不清楚怎麼轉換。

函數輸入是兩個變數

函數輸入是兩個變數(或者一個複數),視作旋轉角度和俯仰角度,得到三維空間的表面。

f[u_,v_] := Sin[u]Sin[v]+2; ParametricPlot3D[{f[u,v]Cos[v/5]Cos[u/5], f[u,v]Cos[v/5]Sin[u/5], f[u,v]Sin[v/5]}, {u, 0, 40}, {v, 0, 40}, Boxed -> False, Axes -> False, Mesh -> None, PlotPoints -> 70, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-2, 2}]] &) ]

進階主題是「球諧函數」。傅立葉轉換的基底(各種頻率的複數波),進行轉換,得到球諧函數。

函數輸出是兩個變數

函數輸出是兩個變數(或者一個複數),視作水平距離和垂直距離,得到三維空間的線。

ParametricPlot3D[{Sin[x] Cos[x*10], Sin[x] Sin[x*10], x}, {x, 0, 9}, Boxed -> False, Axes -> False, PlotStyle -> {RGBColor[192,0,0], Thick}]

進階主題是「柱諧函數」。