演算法筆記 - Function

Function

Numeric Function

函數的概念,請見本站文件「Function」。此處僅專注於輸入輸出都是數值的函數。

Function可以畫成圖形

函數畫成圖形,容易觀察理解。窮舉各種輸入,分別計算輸出,把輸入與輸出化作座標位置。

輸入變數,一個可以畫成曲線,二個可以畫成曲面,三個就只能用空氣濃度來呈現輸出數值了,四個以上只能用幻想的。

輸出變數,一個容易作圖,兩個以上此處不介紹。

Plot3D[(x-3)*(x-3)*(x-3)*(y-1)*(y-1)*2*x*y, {x, -0.1, 4.4}, {y, -0.2, 1.5}, PlotRange -> {-3, 3}, Boxed -> False, Axes -> False, ColorFunction -> "SolarColors"]

容易計算的函數類型

Linear Function:線性函數。變數的加法、減法、倍率所組成。特色是可以改寫成矩陣形式。請參考本站文件「Matrix」。

例如f(x) = 2x、f(x,y) = 2x + y。

又例如f(x, y) = 2(x - y) + 3(x + 2y)。

Affine Function:仿射函數。變數暨常數的加法、減法、倍率所組成。可以想成是線性函數又平移,不必穿過原點。

例如f(x) = 2x + 1、f(x,y) = 2x + y - 3。

又例如f(x, y) = 5((x - 1) - (3x + 2y) + 5⋅3) - 2。

Polynomial Function:多項式函數。變數暨常數的加法、減法、乘法所組成。請參考本站文件「Polynomial」。

例如f(x) = 3x² + 2x + 1、f(x,y) = 3x² + 2y² + xy + y - 3。

又例如f(x, y) = y((x - 1) ⋅ (3x + 2y) + 5⋅3) - 2。

Function的用途

計算機只會計算數字。要讓電腦代替人腦處理真實世界的問題,首先要將人腦的抽象想法,一一對應到電腦的具體數值。

人腦感知到的事物,文字、色彩、聲音、圖片、形狀,透過人為的規則,化作數值。

人腦感知到的「事物」,在電腦裡就成了「數據」。人腦考慮的「各種可能性」與「流程規則」,在電腦裡就成了「各種輸入輸出」與「函數」。

例如人腦的「改變形狀」,在電腦裡就成了「數據代入函數」。

Function運算(主角是數據)

          noun            verb
--------  --------------  -----------
求值      evalutation     evaluate
求解      resolution      resolve
求根      root finding    find root
最佳化    optimization    optimize
內插      interpolation   interpolate
迴歸      regression      regress
變換      transformation  transform
重新表示  representation  represent

求值:已知輸入、求得輸出。

求解:已知輸出、求得輸入。

種什麼因,得什麼果  ---> 函數、方程式
結果是什麼      ---> 求值
原因是什麼      ---> 求解

求根:輸出是零的地方,求得輸入與輸出。

最佳化(求極值):輸出最大、最小的地方,求得輸入與輸出。

事物的詳細情況    --->  輸入
事物的好壞優劣    --->  輸出
沒有效果的情況    ---> 求根
效果最好或最差的情況 ---> 最佳化

內插:已知一部分的輸入與輸出,求得函數。

迴歸:已知一部分的輸入與輸出,求得差不多的函數。

觀察世間萬物之關聯  --->  一部分的輸入與輸出
找出前因後果     ---> 內插、迴歸
進而預測因果     ---> 內插、迴歸,之後再求值、求解、……

變換:已知輸入,設計函數,求得輸出。

重新表示:已知大量輸入,設計函數,求得大量輸出。

世間萬物       ---> 數據
世間萬物的變化    ---> 變換、重新表示

Function運算(主角是函數)

函數就和實數、複數一樣,有著各種運算。

運用函數運算,擷取函數的資訊、修改函數的內容。

這個小節收錄了各種數學領域的函數運算。上個小節則可以視作計算學領域的函數運算。

收錄內容很多,讀者不必急於一時學會。當做休閒娛樂,隨興看看就好。真有需要時,四處查一查。

■ logic
     	operation (noun)     	operation (verb)     	result (noun)
-----	-------------------- 	-------------------- 	------------------
( )  	evaluation      求值 	evaluate      求值   	value       值
=    	substitution    代入 	substitute    代入   	expression  式
∘    	composition     複合 	compose       複合   	composite function
⁻¹   	inversion      反演 	inverse       反演   	inverse function

■ arithmetic
-----	-------------------- 	-------------------- 	------------------
+    	addition        加法 	add           加     	sum         和
-    	subtraction     減法 	subtract      減     	difference  差
⋅    	multiplication  乘法 	multiply      乘     	product     積
/    	division        除法 	divide        除     	quotient    商

■ calculus
-----	-------------------- 	-------------------- 	------------------
d/dx 	differentiation 微分 	differentiate 微     	derivative  導數
∫ dx 	integration     積分 	integrate     積     	integral    積分

■ analysis
-----	-------------------- 	-------------------- 	------------------
⟪ , ⟫	                     	                     	dot product 點積
∗    	                     	                     	convolution 摺積
‖ ‖  	                     	                     	norm        範數

■ comparison
-----	--------------------	-------------------- 	------------------
=    	                    	equal than    等於   	true/false  真/假
>    	                    	greater than  大於   	true/false  真/假
<    	                    	smaller than  小於   	true/false  真/假

■ optimization
-----	-------------------- 	-------------------- 	------------------
max  	maximization  最大化 	maximize      最大化 	maximum     最大值
min  	minimization  最小化 	minimize      最小化 	minimum     最小值
sup  	                     	                     	supremum    最小上界
inf  	                     	                     	infimum     最大下界

求值

給定輸入數值,計算輸出數值。

                          x = 1
          sin x   cos y   y = 0.5              sin 1   cos 0.5
f(x, y) = ————— + —————  ========> f(1, 0.5) = ————— + ——————— = 2.56
            y       x                           0.5       1

代入

輸入變數替換為其他變數,得到新函數。

                          x = s+2
          sin x   cos y   y = t/2            sin(s+2)   cos(t/2)
f(x, y) = ————— + —————  ========> g(s, t) = ———————— + ————————
            y       x                           t/2       s+2   

複合

如果經常接連求值,那麼可以預先把函數複合在一起,得到複合函數,節省計算時間!

兩個函數
f(x) = x² + x + 1
g(x) = -x + 2

輸入數值是1的時候,計算先通過g函數、再通過f函數的輸出數值
g(1)           = -1 + 2     = 1
f(g(1)) = f(1) = 1² + 1 + 1 = 3

輸入數值是2的時候,計算先通過g函數、再通過f函數的輸出數值
g(2)           = -2 + 2     = 0
f(g(2)) = f(0) = 0² + 0 + 1 = 1
如果預先讓函數複合的話
(f ∘ g)(x) = f(g(x))
           = (-x + 2)² + (-x + 2) + 1 
           = x² - 5x + 7

那麼就可以節省計算時間
(f ∘ g)(1) = 1² - 5 + 7   = 3
(f ∘ g)(2) = 2² - 10 + 7  = 1

反演

如果經常求解,那麼可以預先把函數反演,得到反函數,節省計算時間!

一個函數
f(x) = log₂(x - 2)

輸出數值是1的時候,嘗試求得輸入x
f(x) = log₂(x - 2) = 1
            x - 2  = pow₂(1)
            x - 2  = 2¹
            x - 2  = 2
            x      = 2 + 2
            x      = 4
如果預先讓函數反演的話
f⁻¹(x) = 2ˣ + 2

那麼就可以節省計算時間
f⁻¹(1) = 2¹ + 2 = 4

加減乘除

如果經常要把兩個函數的輸出加在一起,那麼可以預先把兩個函數加在一起,得到新函數,節省計算時間!

兩個函數
f(x) = x² + x + 1
g(x) = -x + 2

輸入數值是1的時候,計算所有函數輸出數值的總和
f(1)        = 1² + 1 + 1 = 3
g(1)        = -1 + 2     = 1
f(1) + g(1) = 3 + 1      = 4

輸入數值是2的時候,計算所有函數輸出數值的總和
f(2)        = 2² + 2 + 1 = 7
g(2)        = -2 + 2     = 0
f(2) + g(2) = 7 + 0      = 7
如果預先讓函數相加的話
(f + g)(x) = f(x) + g(x)
           = (x² + x + 1) + (-x + 2)
           = x² + 3

那麼就可以節省計算時間
(f + g)(1)  = 1² + 3     = 4
(f + g)(2)  = 2² + 3     = 7

加減乘除概念相仿,其餘運算就不多提了。

微分、積分

微分:輸出差距除以輸入差距。曲線的斜率。

積分:輸出加總乘以輸入差距。曲線下的面積。

詳情請見本站文件「Function」。

點積、摺積

【不知道怎麼畫成圖片】

點積:兩個函數相乘、積分、求值(輸入正無限大)。

摺積:很多次點積,其中一個函數左右翻面、一直位移。

詳情請見本站文件「Sequence」。

範數

輸出的大小。

如果輸出變數有很多個,那麼範數有許多種設定方式。最常見的方式是「平方和開根號」,換句話說「自點積開根號」,彷彿向量的長度。

詳情請見本站文件「Transformation」。

等於、大於、小於

等於:兩個曲線,處處一樣高。

大於:第一個曲線,處處都較高。

小於:第一個曲線,處處都較低。

如果輸出變數有很多個,那麼可以用範數比大小。

最大值、最小值

最大值:一個曲線的最高處。最大的輸出。

最小值:一個曲線的最低處。最小的輸出。

詳情請見本站文件「Optimization」。

最小上界、最大下界

最小上界:多個曲線的最大值。

最大下界:多個曲線的最小值。

Level Set(Under Construction!)

Level Set(Contour)

http://paulbourke.net/papers/conrec/

連續可微函數的等高線,可以是一條封閉曲線、一條開放曲線、多條上述曲線。

甚至曲線各處粗細不一。

f(x,y)是一群等高線。f(x,y) = 0是一個等高線。f(x,y) ≥ 0是一群等高線,形成區域,區分內部外部。

等高線,無限微小、無限綿密、無限多,填滿整個空間。

一、函數:等高線彼此不相交。

二、連續:等高線沒有端點。等高線升高降低,宛如膨脹消泄。

三、可微:等高線沒有尖角。等高線每一點只有唯一一條切線。

極值位於兩個等高線的交集。注意到極值可能不只一個。

一、函數:兩個等高線,若等高、又最高,則交集是極值。

二、連續:兩個等高線,只會內接或外接,不會交叉。

三、可微:兩個等高線,交會之處,每一點只有唯一一條切線。

切線的垂直方向,就是梯度方向。

Nodal Set(Root)

高度為零的等高線。目前是個謎。

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

Homogeneous Coordinate

添加一個維度,高度固定,即是等高線。

容易計算的函數類型

Monotone Function:單調函數。遞增、遞減。

Convex Function:凸函數。斜率是單調函數,遞增是凸、遞減是凹。

Quasiconvex Function:擬凸函數。等高線是凸的,遞增是擬凸、遞減是擬凹。

Unimodal Function:單峰函數。先遞增(減)再遞減(增)。

https://www.desmos.com/calculator/bjfgiws8ku
https://mjo.osborne.economics.utoronto.ca/index.php/tutorial/index/1/qcc/t
f(a,x) = ax  在第一三象限是擬凹函數、第二四象限是擬凸函數
https://www.desmos.com/calculator/vkru83pare

[A,X] = meshgrid(-10:0.5:10,-10:10);
Z = A .* X;
surf(A,X,Z)

Multivariate Contour

多變量函數沒有等高線,取而代之的是箭矢圖。

多變量函數的單調函數、凸函數、擬凸函數、單峰函數,似乎沒什麼人研究,個個都模糊曖昧。

Streamline

電力線是另一種製圖方式,電流大小是電力線多寡,電流方向是電力線走向。

真實世界當中,無法先觀測電勢、再推導電場,而是先觀測電場、再逆推電勢。

真實世界當中,電流是梯度場,氣流不是梯度場。氣流無法逆推氣勢。

單調函數【尚待確認】

一維箭矢圖有個特性:遞增函數(斜率處處大於零),箭矢自零散開。遞減函數(斜率處處小於零),箭矢聚集至零。

多維箭矢圖則是:散度處處大於零,箭矢自零散開。散部處處小於零,箭矢聚集至零。

散開的地方稱作源,聚集的地方稱作匯。當函數起起伏伏、而且很多地方是零,就有許多源匯。正負無限大的地方也是源匯。

儘管源匯很吸睛,不過沒什麼用途就是了。

Monotone Linear Function

遞增數列,就是數字越來越大。遞增陣列,就是數字往右往下越大、往左往上越小。

遞增函數,就是數字越來越大。遞增二元函數,就是數字往右上的各種方向都越來越大。

變數推廣成許多個,推廣成向量,則用向量長度比大小。然而向量長度沒有負數,沒辦法越來越小。因此有人改用向量內積比大小:正數(向量轉彎幅度少於±90˚)代表更大,負數代表更小。意義扭曲了。

                           f(y) - f(x)
function f is monotone iff ――――――――――― >= 0   斜率大於零,分子分母同號
                              y - x

multivariate function f is monotone iff (y-x) dot (f(y)-f(x)) >= 0
                                                  ^^^^^^^^^^^
                                          f(y-x) when f is linear
點積大於零,分子分母同號(轉彎幅度少於±90˚,被定義成向量變大。)

線性遞增函數Ax:從原點出發(線性函數必過原點)。等價於A是正半定矩陣,特徵值是正數或零。

嚴格遞增則是正定函數。特徵值都是正數,沒有零。

註:「單調矩陣」與「遞增矩陣」這些詞彙已經被古人賦予其他意義,因此大家仍稱呼為正半定矩陣。

linear multivariate function Ax is monotone iff A is positive semidefinite.

vector field is monotone iff jacobian matrix is positive semidefinite everywhe
re.
函數(向量場)的斜率(雅可比矩陣、梯度、一次微分)是正數或零(半正定矩陣),就是單調遞增函數。

Diagonally Dominant Matrix

gauss-seidel = coordinate descent (change of basis) ???
diagonally dominant = unimodal/convex ???
positive diagonally dominant => postive definite => convex
diagonally dominant matrix <---> Lipschitz function ???

https://en.wikipedia.org/wiki/Modified_Richardson_iteration
https://books.google.com.tw/books?id=KVfSBwAAQBAJ&pg=PA105

既然f(x)梯度下降法等價於g(x) = x + w f'(x)不動點遞推法
那麼這兩個東西一定有關係

|f(b) - f(a)| / |b - a| <= 1
|f(a) + f(b)| <= |a + b|  其中一個變數變號