Average Number

Weighted Average

兩數,依照比例(權重),各取一部分,加總,得到「加權平均值」。

加權平均值介於兩數之間。調整權重,可以得到兩數之間的每一種數字。

x = w x₁ + (1-w) x₂   (0 ≤ w ≤ 1)

推廣到多數。加權平均值介於最大值和最小值之間。

x = w₁x₁ + w₂x₂ + ... + wₙxₙ   (w₁ + ... + wₙ = 1)

推廣到高維度。加權平均值介於凸包之間。

[x]      [x₁]      [x₂]            [xₙ]
[y] = w₁ [y₁] + w₂ [y₂] + ... + wₙ [yₙ]   (w₁ + ... + wₙ = 1)
[z]      [z₁]      [z₂]            [zₙ]

其實只是每個維度分開處理
x = w₁ x₁ + w₂ x₂ + ... + wₙ xₙ
y = w₁ y₁ + w₂ y₂ + ... + wₙ yₙ
z = w₁ z₁ + w₂ z₂ + ... + wₙ zₙ

權重推廣成任意數。每個權重另外除以權重總和。

     (w₁)       (w₂)         (w₃)
      a          b            c        ax₁ + bx₂ + cx₃
x = ————— x₁ + —————  x₂ +  ————— x₃ = ———————————————
    a+b+c      a+b+c        a+b+c         a + b + c   
          a₁                       aₙ
x = ————————————— x₁ + ... + ————————————— xₙ
    a₁ + ... + aₙ            a₁ + ... + aₙ

    a₁ x₁ + ... + aₙ xₙ
  = ———————————————————
       a₁ + ... + aₙ   

數字推廣成任意事物。加權平均值無所不在。

主角    加權平均值
--------  ----------
質點    重心
溶液    混和濃度
機率    期望值
座標點   凸包範圍
函數點   線性內插
線性代數  線性組合
三原色   人類眼中的彩色

加權平均值的精髓:多數化作一數。

Floating Number

Random Variable與Distribution

現實世界的數值,通常是浮動數值,不是精準數值。數值具有多種可能性,有時高一點,有時低一點。

工程師活用了區間的概念,描述浮動數值。例如食品包裝經常見到的500±20,表示數值可能是區間[480,520]的其中一個。

工程師命名為「誤差範圍」。好用,但是太過陽春。

數學家活用了比例、函數兩個概念,描述浮動數值。我們可以自由控制要出現那些數值,個別的數值(離散)、一段範圍的數值(連續)。我們甚至可以個別調整每一種數值的出現程度高低。

數學家命名為「隨機變數」。這個名稱經常造成誤解,事實上這根本不隨機。理想的名稱應是「浮動數字」。

兩個隨機變數可以加減乘除,但是計算過程非常複雜:試誤法,針對一個答案,窮舉各種得到此答案的方式,累加機率。

     add: X+Y  (convolution)
subtract: X-Y  (convolution)
multiply: XY   (Dirichlet convolution)
  divide: X/Y

數學家定義了一些簡易指標,可以迅速獲知隨機變數的重點。

一個隨機變數的
平均值 mean        : E[X]
均方值 mean square : E[X^2]
變異數 variance    : E[(X-E[X])^2]

兩個隨機變數的
共相關數   correlation             : E[XY]
共變異數   covariance              : E[(X-E[X])(Y-E[Y])]
共相關係數 correlation coefficient : CoVar[X,Y] / sqrt(Var[X]) / sqrt(Var[Y])

由於隨機變數的四則運算非常複雜,數學家鮮少討論隨機變數的四則運算,轉而討論隨機變數的指標的四則運算。出乎意料地優雅。

E[X+Y] = E[X] + E[Y]
E[X⋅Y] = E[X] ⋅ E[Y]   if X and Y are independnet
E[X+k] = E[X] + k
E[X⋅k] = E[X] ⋅ k
Var[X+Y] = Var[X] + Var[Y] + CoVar[X,Y]
Var[X-Y] = Var[X] + Var[Y] - CoVar[X,Y]
CoVar[X,Y] = 0   if X and Y are independnet
Var[X+k] = Var[X]
Var[X⋅k] = Var[X] ⋅ k²

至於「每一種數值的出現程度高低」的函數,數學家命名為「分布」。數學家創造了許多經典的分布,數學性質極強。例如兩個常態分布隨機變數,相加減還是常態分布。相乘除就不是。

uniform distribution
Gaussian distribution (normal distribution)
binomial distribution
Poisson distribution

大學的機率課程已經談過這些東西,此處只做重點歸納。

隨機變數的精髓:一數蘊含多數。

Mixture Distribution(Mixture Model)

數個隨機變數,浮動出現其中一個隨機變數。兩層隨機變數。

其實就是數個分布函數的加權平均值,因而稱作「混合分布」。想一想為什麼。

混合分布是計算學家的最愛。用幾個經典的分布,調整平均數、變異數,以及權重,組合出具有曼妙曲線的分布。

經典的混合分布,像是數個常態分布的加權平均值,稱做「高斯混合模型Gaussian Mixture Model」。

Weighted Average of Random Variables

真實世界當中,數字通常不精準,數字通常有誤差。引入機率分布,讓每個數字擁有浮動範圍,是個不錯的辦法。例如讓每個數字套用常態分布。

浮動數字的加權平均值,我不清楚是否有人研究。如果只有兩個數字,而且權重都是0.5,加權平均值就是摺積。值得一提的是,兩個常態分布的摺積仍是常態分布,平均數、變異數很好推算:

http://www.tina-vision.net/docs/memos/2003-003.pdf

Floating Sequence

Random Variable

理想的名稱應是「浮動數字」,但是數學家卻稱做「隨機變數」,事實上這根本不隨機。經典的隨機變數:

uniform random variable
binomial random variable
Gaussian random variable
Poisson random variable

Random Process(Stochastic Process)

理想的名稱應是「浮動數列」與「浮動函數」,但是數學家卻稱做「隨機過程」,事實上這根本不隨機。經典的隨機過程:

Gaussian process:每個隨機變數都是高斯分布,每個隨機變數組合都是多維高斯分布。
Wiener process:高斯過程的積分。就是「布朗運動」。
Markov process:以先前幾個隨機變數的數值,決定下一個隨機變數。
Ornstein-Uhlenbeck process:每個隨機變數都是高斯分布,隨機變數之間有相關。
martingale:最新的K個隨機變數,期望值是定值。

隨機過程兩大主要應用:

一、讓數列和函數具有浮動範圍、彈性範圍、緩衝範圍。例如「Gaussian Process Regression」、「Hidden Markov Model」。

二、亂跳的數列和函數。例如「CIR Model」。

Random Field

https://mathematica.stackexchange.com/questions/4829/ https://mathematica.stackexchange.com/questions/144443/ GaussianRandomField[ size : (_Integer?Positive) : 256, dim : (_Integer?Positive) : 2, Pk_: Function[k, k^-3]] := Module[ {Pkn, fftIndgen, noise, amplitude, s2}, Pkn = Compile[{{vec, _Real, 1}}, With[{nrm = Norm[vec]}, If[nrm == 0, 0, Sqrt[Pk[nrm]]]], CompilationOptions -> {"InlineExternalDefinitions" -> True}]; s2 = Quotient[size, 2]; fftIndgen = ArrayPad[Range[0, s2], {0, s2 - 1}, "ReflectedNegation"]; noise = Fourier[RandomVariate[NormalDistribution[], ConstantArray[size, dim]]]; amplitude = Outer[Pkn[{##}] &, Sequence @@ ConstantArray[N @ fftIndgen, dim]]; InverseFourier[noise * amplitude] ] ListPlot3D[GaussianRandomField[128, 2] // Chop, Mesh -> None, Boxed -> False, Axes -> False, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-2, 2}]] &) ] data = GaussianRandomField[16, 2] // Chop; ListPointPlot3D[data, PlotStyle -> {PointSize[Large], Black}, Boxed -> False, Axes -> False] ListPointPlot3D[data, Filling -> Bottom, FillingStyle -> Directive[Gray, Thick], Boxed -> False, Axes -> False]

推廣成多變量函數。空間處處有浮動數字、甚至浮動數列。

理想的名稱應是「浮動陣列」與「浮動場」,但是數學家卻稱做「隨機場」,事實上這根本不隨機。經典的隨機場:

Gaussian random field:每個隨機變數都是高斯分布,
                       每個隨機變數組合都是多維高斯分布。
Markov random field:以相鄰的隨機變數的數值,決定本處的隨機變數。
Gibbs random field:馬可夫隨機場,而且隨機變數皆是正數。

隨機場兩大主要應用:

一、隨機地形、紋路。例如「Matérn Covariance Function」。

二、圖片分割、生成。例如「Markov Random Field」。

Random Process的頻譜

隨機過程,實施「傅立葉轉換」,從時域變頻域。

普通的隨機過程:無解析解,頻譜混亂。

滿足wide-sense stationary條件的隨機過程:有解析解。兩兩的共相關數,可求得頻譜。具備傅立葉轉換的相關數學特性,諸如線性、摺積乘法對偶、能量守恆(Parseval's theorem)。

然而,滿足wss條件的隨機過程,就是每個數字幾乎一樣的數列。缺乏討論意義,也無法解決現實問題。數學家目前僅發現wss條件,尚未發現更具討論意義的條件。

Martingale

https://en.wikipedia.org/wiki/Doob_martingale
https://en.wikipedia.org/wiki/Azuma's_inequality

When analyzing sums, random walks, or other additive functions of independent
random variables, one can often apply the central limit theorem, law of large
numbers, Chernoff's inequality, Chebyshev's inequality or similar tools. When
analyzing similar objects where the differences are not independent, the main
tools are martingales and Azuma's inequality.

Azuma's inequality applied to the Doob martingale gives the method of bounded
differences (MOBD) which is common in the analysis of randomized algorithms.

Random Number

Random Number

「隨機數」、「亂數」。我們習慣一口氣取大量隨機數。

1694 19262 3252 4541 20 28590 6191 814 30047 9007 29380 1639 23559

什麼樣子叫做Random呢?目前沒有定論!

大家習慣把Random解讀為「沒有規律」、「不可預測」、「亂」,但是沒有人能明確描述詳細內容。

大致能想到的有:

一、數字的分布:每個數字都可能出現。
二、數字的排版:數字沒有特殊造型。
三、數字的擾動:數字歪了,多了點、少了點。
四、次序的更動:下個數字不知道是哪一個。

相關的數學概念有:

一、Inversion 逆序對
二、Entropy 熵
三、Discrepancy
四、Normal Number 正規數
五、Point Process 點程序

Pseudorandom Number

計算機只能接受明確指令,人類只好使用明確數學公式、明確演算法來製造隨機數。隨機數具有規律、可以預測,於是早期文獻稱做「偽隨機數」、「偽亂數」。

儘管隨機數具有規律、可以預測,我們還是可以努力讓隨機數「看起來似乎很亂」,讓人一時無法預測。但由於缺乏「亂」的明確定義,所以無法精準評比優劣。一切都是靠感覺,很不科學。

C的內建函式庫,提供了隨機數。可惜不是均勻分布uniform distribution,時常為人詬病。

C++的內建函式庫,提供了健全的隨機數。

演算法(Linear Congruential Generator)

先備知識是「餘數」。

以數學式子xnext = (((x ⋅ a) + b) % n);不斷製造隨機數。

當n是質數,則0到n-1恰好各出現一次,呈均勻分布。不過當n不是質數,就很難說了,必須小心設定a b n才行。

缺點:每n個數字循環出現,可以預測。實務上會讓n很大,以避開缺點。

C語言的rand()即是此演算法。

演算法(Xorshift)

先備知識是「有限域」。

餘數系統,將整數推廣成餘數多項式。二進位數字視作餘數多項式,餘數多項式加法、乘法化作xor、shift。細節請自行查詢。

演算法(Mersenne Twister)

我沒有研究。細節請自行查詢。

2D Random Number

二維隨機數,更加講究排版,衍生許多演算法。

       regular:排列整齊。缺點是太過整齊,具有明顯紋路。
       uniform:均勻分布。缺點是不夠整齊,偶有空白小格。
      jittered:regular + uniform,每小格任取一點。
                宏觀整齊適中,微觀仍不夠整齊,常常靠太近。
        n-rook:n個城堡不互相攻擊。奇爛無比。
multi-jittered:每小格實施n-rook。稍微改善小處不夠整齊的問題。
  Poisson disk:每一點到其他點的最短距離為定值d。整齊。慢。
best candidate:每一點到先前點的最短距離盡量長。不太整齊。快。
    Hammersley:(i, i的二進位鏡射)。整齊適中。超快!
        Halton:(i的a進位鏡射, i的b進位鏡射),a與b互質。超快!
         Sobol:我沒有研究。

演算法(Poisson Disk Sampling)

每回合在圓形聯集的邊界上隨機生一點。自訂圓半徑。

演算法(Best Candidate Sampling)

每回合隨機生k個候選點,留下最遠的那一點。

演算法(Hammersley Sequence)

(i, i的二進位鏡射)。

i | i₍₂₎ |Φ(i)₍₂₎| Φ(i)
--|------|-------|------
1 |    1 | .1    | .5
2 |   10 | .01   | .25
3 |   11 | .11   | .75
4 |  100 | .001  | .125
5 |  101 | .101  | .635
6 |  110 | .011  | .325
7 |  111 | .111  | .875
8 | 1000 | .0001 | .0625

Φ(i): radical inverse of integer i

演算法(Halton Sequence)

(i的a進位鏡射, i的b進位鏡射),a與b互質。

演算法(Sobol Sequence)

http://web.maths.unsw.edu.au/~fkuo/sobol/joe-kuo-notes.pdf

演算法(Recursive Wang Tile)

整數隨機數調整範圍

一種隨機數,放大、位移,調整範圍。

random(0, 2) + 3 = random(3, 5)
random(0, 2) - 3 = random(-3, -1)
random(0, 2) × 3 = random(0, 6)

多種隨機數,分別做為每個位數,仍是均勻分布!需要調整成十進位,很麻煩。

random(0, 2) * 10 + random(0, 9) ---> random(0, 29)

浮點數隨機數調整範圍

一種隨機數,縮放、位移,調整範圍。

uniform(0, 2) + 3 = uniform(3, 5)
uniform(0, 2) - 3 = uniform(-3, -1)
uniform(0, 2) × 3 = uniform(0, 6)
uniform(0, 2) ÷ 3 = uniform(0, 2/3)

多種隨機數,相加、相乘,不再是均勻分布!別亂用。

uniform(0, 2) + uniform(0, 3) ≠ uniform(0, 5)
uniform(0, 2) × uniform(0, 3) ≠ uniform(0, 6)

一維隨機數,位於線段。可以變成圓形、半圓形。

二維隨機數,位於正方形。可以變成矩形、三角形、四邊形、多邊形、圓盤、球面、半球面。

Graphics3D[{PointSize[Large], Point[RandomPoint[Ball[], 200]]}, Boxed->False] Graphics3D[{PointSize[Large], Point[SpherePoints[200]]}, Boxed->False] u1 := RandomReal[{0,1}]; u2 := RandomReal[{0,1}]; f[{u1_, u2_}] := {Sqrt[u1]*Cos[2*Pi*u2], Sqrt[u1]*Sin[2*Pi*u2], Sqrt[1-u1]}; pts = f /@ Table[{u1, u2}, {200}]; Graphics3D[{PointSize[Large], Point /@ pts}, Boxed->False]

變換時必須注意面積變化、密度變化,以確保均勻。例如正方形變圓盤:長變成幅角、寬變成半徑平方。若忘了開根號,則內密外疏。

順帶一提,後面章節Sampling的演算法,似乎也都可以用於調整形狀。不過我還沒想清楚。

Random Sequence

Random Sequence

古代數學家沒有仔細區分「浮動:有規矩」和「隨機:無規矩」的差別,把兩者都命名為隨機,混淆視聽。大家搞不清楚狀況的情況下,大家一直沒有深入研究隨機數列的演算法。

將就方式是1D Random Number。然而數字輪輪循環,很蠢。

將就方式是2D Random Number投影到一維。然而沒有任何理論根據,純粹憑感覺。

Sampling

Sampling

「取樣」。創造大量數字,符合指定分布。

使用均勻分布的隨機數,製作指定分布的隨機數。

UVa 12109

演算法(Importance Sampling)

均勻分布的隨機數,根據指定分布高低來複製數字。高處數量多,低處數量少。

缺點:很多數字相同、數量是整數而比例不精確、難以控制總數量。糟透了。

若起初是其他分布的隨機數,則指定分布除以隨機數分布,以比值高低來複製數字。

演算法(Inversion Sampling)

均勻分布的隨機數,代入「分布的積分的倒函數」,就得到該分布的隨機數。

若起初是其他分布的隨機數,則先變成均勻分布,再變成指定分布。

演算法(Rejection Sampling)

二維隨機數(x,p),在分布曲線下就保留,在分布曲線上就捨棄,x即為所求。相當直覺的方法。

缺點:一、很多隨機數沒有用處,白算了。二、下一個輸出,延遲時間不穩定。有時一下就得到,有時一直得不到。

減少空白處,增加使用率。想辦法建立一個上界函數upper(x),略大於等於分布,做為p的上界。

每個位置x的上界都不同,導致p有密有疏、有多有少;為了讓p均勻等量,x必須符合上界函數的分布。(上界函數除以曲線下方面積,面積調成1,就變成了分布。)

然而上界函數往往難想。這招往往難用。

演算法(Metropolis-Hasting Sampling)

原理源自Markov Chain:

https://zhuanlan.zhihu.com/p/21112618

http://www.jianshu.com/p/27829d842fbc

直接講結論:隨機挑起點,隨機挑下一步。以分布高低比例,決定去或留。需要多少隨機數,就做多少回合。

步伐大小:可以採用任意分布,但是必須左右對稱。

去留判斷:一、下一步分布更高時:既然此處已取樣,分布更高的地方,也應該取樣,以符合分布高低。二、下一步分布更小時:依照比例高低來取樣,抽中原處的機會較高,抽中下一步的機會較低。

此演算法改善了先前缺點。遺珠之憾是隨機數有地緣關係。

演算法(Gibbs Sampling)

推廣到高維度。每次只沿一個維度走或停,每個維度隨機輪流一遍,再重新隨機輪流一遍,不斷下去。

演算法(Box-Muller Transform)

均勻分布變常態分布。因為常態分布的數學式子太長、計算時間太久,所以發明了快而不準的演算法。欲速則不達。

演算法(Central Limit Thorem)

任意分布變常態分布。中央極限定理:任意一個分布,取樣取多了,樣本們的平均值是一個浮動數字,呈現常態分布。

速度更快,準度更低。

Hash Function

Hash Function

「雜湊函數」。輸入輸出都是數字的函數,但是有著形形色色的變種:限寬、均勻、保距、量化、混亂、單向、編碼。大家視情況需要,混用多個變種。

各種變種仍在發展中,以下只簡介。

1. hash function

限寬。限制輸出範圍。簡易方式是mod運算。

用途是縮減數字範圍。

2. uniform hash function

均勻。輸出數字使用機率均等。簡易方式是mod最大公因數。

用途是均勻分散儲存。知名應用是hash table。

3. isometric mapping / locality-sensitive hashing

保距。所有數對,變換前的差異,大致等於變換後的差異。簡易方式是線性變換。

同樣道理,還可以發明保長、保角、保秩、保序等變種。

用途是以雜湊值估計相似度。

4. quantization / projection

量化。刪除數字的細節,降低精確度。簡易方式是floor運算。

用途是簡化數字。知名演算法是PCA、KNN。

5. random hash function

混亂。輸出是固定的隨機數。簡易方式是以輸入數字生成隨機數、隨機排列。

6. cryptographic hash function

單向。難以從輸出推算輸入。簡易方式是餘數連乘、三角函數。

用途是密碼、摘要、簽章,讓外人難以偽造變換前的原始資料。知名演算法如SHA、MD5。

請見本站文件「Encryption」。

7. coding

編碼。輸入不是數字,而是其他元件,例如字串。簡易方式是先化作多項式、再化作數字。

用途是建立索引表,知名演算法如murmur。

請見本站文件「String」。