Transformation

Transformation

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

一維數據,套用函數。二維以上數據,套用函數組(或者解讀成多變量函數)。每筆數據皆套用同一個函數。

1D → 1D       2D → 2D            1D → 3D         3D → 1D
x' = 2x + 1   { x' = x + y       { x' = 2x + 1   x' = x + yz
              { y' = x² + y²     { y' = 3x + 2
                                 { z' = 5x + 3
1D → 1D       2D → 2D            1D → 3D         3D → 1D
y = 2x + 1    { y₁ = x₁ + x₂     { y₁ = 2x + 1   y = x₁ + x₂x₃
              { y₂ = x₁² + x₂²   { y₂ = 3x + 2
                                 { y₃ = 5x + 3

至於每筆數據套用不同函數,目前無人討論。這類變換,可以想成是擁有if判斷式的函數,每筆數據根據判斷結果實施不一樣的行為。可是數學家不討論這種函數,只討論連續、可微。

至於增生數據、消滅數據,目前亦無人討論。

Inverse Transformation

「反向變換」。數據再套用反函數。數據打回原形。

原函數存在反函數,才能反向變換。

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

Dual Transformation

「對偶變換」。原函數、反函數,兩者恰好相同。數據套用函數,亦等同套用反函數。變換兩次等同變換零次。

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

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

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

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

存在反向變換時,運算可以繞路。

例如f(x) = log₂x與f⁻¹(x) = 2ˣ。輸入相乘等同輸出相加。我們可以直接相乘,也可以正向變換、相加、反向變換。

Dual Operation

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

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

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

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

Representation

「重新表示」。換個角度看世界。數據變換之後,內涵保持相同,資訊沒有佚失。

任何一個變換,只要擁有反向變換,皆可充作重新表示。不過大家習慣把這個詞彙用於意想不到、大開眼界的變換,例如直角座標系變極座標系,例如時域變頻域(傅立葉轉換)。

Linear Transformation

Linear Transformation / Affine Transformation

「線性變換」。變換時,採用線性函數。

「仿射變換」。變換時,採用仿射函數。

線性函數是加性函數暨倍性函數。加性函數:輸入相加等同輸出相加。倍性函數:輸入倍率等同輸出倍率。

仿射函數是線性函數納入常數加法。

linear function f:          affine function g:
1. f(x+y) = f(x) + f(y)     1. f(x+y) = f(x) + f(y)
2. f(kx) = k f(x)           2. f(kx) = k f(x)
                            3. g(x) = f(x) + c

線性函數特例、仿射函數特例

線性函數與仿射函數五花八門。大家習慣採用其中一種特例。

線性函數特例:變數加變數、變數乘常數,只含這兩種運算的函數。

仿射函數特例:變數加變數、變數乘常數、變數加常數,只含這三種運算的函數。

仿射函數特例可以輕易簡化成線性函數特例:新添一個變數,乘在常數項,只能代入1。

linear function     affine function         non-affine function
{ x' = x + 2y       { x' = x + 2y + 1       { x' = xy
{ y' = 2(x + y)     { y' = 2(x + y + 5)     { y' = sin(x) + cos(y)

大家經常使用線性變換。優點是只有加法與倍率,相當單純,擁有漂亮數學性質,擁有高速演算法。缺點是單純導致功效不彰。

期待大家發明更特別的變換!目前的研究熱點有兩大方向:一、線性函數的多重複合:人工神經網路;二、複變函數與場:波函數。

經典的線性變換、仿射變換

單一數據的變換:平移translate、縮放scale、旋轉rotate、投影project、鏡射reflect。

請見本站文件「Transformation」。

全體數據的變換:主成分分析PCA、獨立成分分析ICA、主成分追蹤PCS。

請見本站文件「Representation」。

局部數據的變換:均值mean filter、差分difference filter、加權平均weighted average filter。

請見本站文件「Filter」。

UVa 12303

X-Preserving Transformation

X-Preserving Transformation【尚無正式名稱】

「保X變換」。數據變換之後,特性X保持相同。

所謂的特性,就是替數據設立指數、指標,例如長度、距離、角度、中位數、平均數、變異數。

排列組合關鍵字,得到一些經典問題:

一、給定數據與指標。存在哪些變換,使得指標保持相同?
二、給定數據與變換。數據變換之後,哪些指標保持相同?
三、如何發掘好用的新指標?

目前大家沒有特別好的點子。以下只介紹一些陽春的點子。

長度(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)

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

此處的距離,是數學術語,不是物理學術語。此處的距離,是指差異份量多寡,不是指公分公尺。

距離函數(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(A,B) + d(B,C)。

常見的距離函數:

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

常見的元件:

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

UVa 10508 11085 ICPC 5132

距離函數(Divergence)

不滿足上述定義的距離函數,嚴謹起見,大家另起一名divergence。由於該詞彙已經用於多變量函數的散度運算,簡單起見,大家經常假借舊名distance。

常見的元件:

兩個函數點(凸函數)的距離:以「Bregman Divergence」計算距離。
兩個分布的距離:以「Kullback-Leibler Divergence」計算距離。

保長(Length Preserving)

變換的形容詞。任一點,變換前後,長度保持相同。

旋轉、鏡射是保長變換;平移、縮放、投影不是保長變換。

保距(Isometry)(Distance Preserving)

變換的形容詞。任兩點,變換前後,距離保持相同。

平移、旋轉、鏡射是保距變換;縮放、投影不是保距變換。

保角(Conformal)(Angle Preserving)

變換的形容詞。任相鄰三點,變換前後,夾角保持相同。

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

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

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

延伸閱讀:核函數(Kernel)

數據變換之後的距離函數。機器學習領域胡亂造詞。

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

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

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

延伸閱讀:Geometric Transformation

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

用於改變物體形狀的變換,通稱「幾何變換」。細分成剛體變換、相似形變換、投影變換、……。

X-Invariant Transformation

X-Invariant Transformation

「X不變變換」。數據經過X修改,變換之後,結果保持相同。

所謂的修改,就是數據的運算、變換,例如取絕對值、取整數、取餘數、平移、縮放、旋轉。

X-preserving transformation: x--->x' , X(x) = X(x')
X-invariant transformation:  x--->x' , X(x)--->x'

事實上,所謂的特性、所謂的修改,本質都是函數。保X變換:輸入輸出套用函數,結果一致,能夠保存精髓。X不變變換:輸入套用函數,輸出仍然一致,能夠容忍異常。

註:X Preserving Transform的X稱作「不變量Invariant」。X Invariant Transformation故意採用相同單字,混淆視聽。

Coordinate

集合(Set)、元組(Tuple)

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

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

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

set       tuple
{4,5,7}   (5,4,7)
{1,2,3}   (1,1,2,2,3,3)
{●,▲,■}   (●,■,▲,◆,▲)
{}        ()

空間(Space)

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

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

常見的空間元件:幾何的「點」、代數的「向量」。

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

座標(Coordinate)

空間裡每個元素,分別設定獨一無二的tuple,tuple裡面是數字。一種設定方式稱作一種「座標系coordinate system」。tuple的一個欄位稱做一種「座標coordinate」。中文則習慣把所有欄位合稱「座標coordinates」。

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

Euclidean Space Coordinate

歐氏空間的直角座標系(Cartesian Coordinate System)

大家熟知的一維數線、二維平面、三維空間,都是歐氏空間。

歐氏空間的點,無限多、無限小、無限綿密,不易製圖。製圖時,不會畫點,而是意思意思畫座標軸。

挑選任意一點做為原點,挑選任意方向做為X軸方向,其餘座標軸互相垂直,滿足右手座標系。

歐氏空間的其他經典的座標系

大家熟知的直角座標系,其實是歐氏空間的其中一種座標系。

tuple的每個欄位,設定成長度、角度,得到其他座標系。

  Cartesian coordinate system 直角座標系 長度、……     任意維
      polar coordinate system 極座標系  長度、角度    二維
  spherical coordinate system 球座標系  長度、角度、角度 三維
cylindrical coordinate system 圓柱座標系 長度、長度、角度 三維

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

UVa 12323

座標系寫成函數組

以直角座標系當作預設座標系,各種座標系得以寫成函數組。一個函數求得一個維度的座標。

函數組是一對一函數:不同地點擁有不同座標。函數組是連續函數:相鄰地點擁有相鄰座標。函數組的輸入變數與輸出變數一樣多:座標欄位數量符合維度大小。

更換座標系(Coordinate System Transformation)

拆成兩步驟:先套用舊座標系的反函數組、再套用新座標系的函數組。

數學當中,更換座標系是重新貼標籤,不會改變點。計算學當中,更換座標系是變換,用來改變數據。

延伸閱讀:利用加權平均值創造座標系

請見本站文件「Weighted Average Coordinates」。

Hilbert Space Coordinate

內積空間的線性組合座標系

內積空間的任意向量,皆能充作座標軸的標準單位,稱作基底。

發動特殊技能加法與倍率,分解向量,成為基底的線性組合。外觀彷彿加權平均值。權重大小,就是座標。

基底必須線性獨立,才能順利分解各種向量。

內積空間的投影座標系

內積空間的任意向量,皆能充作座標軸的標準單位,目前沒有正式名稱,也許可以稱作基底。

發動特殊技能內積,投影向量至基底。投影量大小,就是座標。

基底必須線性獨立,才能順利分解各種向量。

備註

線性組合座標系:平行於座標軸投影。投影座標系:垂直投影。

矩陣轉置視作對偶變換,那麼對偶運算是加權平均對大量內積。

內積空間的元件是數列

向量空間的元件、內積空間的元件,叫做向量。請見本站文件「Linear Algebra」。

此處的向量,是數學術語,不是物理學術語。此處的向量,是指擁有加法運算與倍率運算的元件,不是指合力分力。

內積空間的元件,通常設定成有限長度數列。書寫方式是將數字縱向排列,採用中括號。大家應該都知道,就不多提了。

內積空間的元件是函數

投影座標系當中,座標軸的標準單位又稱作「核kernel」,求得座標又稱做「積分轉換Integral Transform」。

例如傅立葉轉換就是積分轉換,以各種頻率的複數波當作核。